Source author record

W. T. Gowers

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.NT Artificial Intelligence math.FA math.GR

Catalog footprint

Research overview

15works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Equidistribution of high-rank polynomials with variables restricted to subsets of $\mathbb{F}_p$

Let $p$ be a prime and let $S$ be a non-empty subset of $\mathbb{F}_p$ . Generalizing a result of Green and Tao on the equidistribution of high-rank polynomials over finite fields, we show that if $P: \mathbb{F}_p^n \rightarrow \mathbb{F}_p$ is a polynomial and its restriction to $S^n$ does not take each value with approximately the same frequency, then there exists a polynomial $P_0: \mathbb{F}_p^n \rightarrow \mathbb{F}_p$ that vanishes on $S^n$ , such that the polynomial $P-P_0$ has bounded rank. Our argument uses two black boxes: that a tensor with high partition rank has high analytic rank and that a tensor with high essential partition rank has high disjoint partition rank.

preprint2021arXiv

Partial associativity and rough approximate groups

Suppose that a binary operation $\circ$ on a finite set $X$ is injective in each variable separately and also associative. It is easy to prove that $(X,\circ)$ must be a group. In this paper we examine what happens if one knows only that a positive proportion of the triples $(x,y,z)\in X^3$ satisfy the equation $x\circ(y\circ z)=(x\circ y)\circ z$ . Other results in additive combinatorics would lead one to expect that there must be an underlying "group-like" structure that is responsible for the large number of associative triples. We prove that this is indeed the case: there must be a proportional-sized subset of the multiplication table that approximately agrees with part of the multiplication table of a metric group. We also present an example that suggests that our result cannot be strengthened to yield a dense subset that agrees with part of the multiplication table of a group.

preprint2020arXiv

A uniform set with fewer than expected arithmetic progressions of length 4

An example is presented of a subset $A$ of $\mathbb Z_N$ of density $α$ such that the largest non-trivial Fourier coefficient of the characteristic function of $A$ is very small, but the probability that a random arithmetic progression (mod $N$ ) of length 4 lies in $A$ is significantly smaller than $α^4$ .

preprint2020arXiv

Generalizations of the Ruzsa-Szemerédi and rainbow Turán problems for cliques

Considering a natural generalization of the Ruzsa-Szemerédi problem, we prove that for any fixed positive integers $r,s$ with $r<s$ , there are graphs on $n$ vertices containing $n^{r}e^{-O(\sqrt{\log{n}})}=n^{r-o(1)}$ copies of $K_s$ such that any $K_r$ is contained in at most one $K_s$ . We also give bounds for the generalized rainbow Turán problem $\operatorname{ex}(n, H,$ rainbow- $F)$ when $F$ is complete. In particular, we answer a question of Gerbner, Mészáros, Methuku and Palmer, showing that there are properly edge-coloured graphs on $n$ vertices with $n^{r-1-o(1)}$ copies of $K_r$ such that no $K_r$ is rainbow.

preprint2020arXiv

Improved bounds for the Erdős-Rogers function

The Erdős-Rogers function $f_{s,t}$ measures how large a $K_s$ -free induced subgraph there must be in a $K_t$ -free graph on $n$ vertices. While good estimates for $f_{s,t}$ are known for some pairs $(s,t)$ , notably when $t=s+1$ , in general there are significant gaps between the best known upper and lower bounds. We improve the upper bounds when $s+2\leq t\leq 2s-1$ . For each such pair we obtain for the first time a proof that $f_{s,t}\leq n^{α_{s,t}+o(1)}$ with an exponent $α_{s,t}<1/2$ , answering a question of Dudek, Retter and Rödl.

preprint2016arXiv

Freiman homomorphisms on sparse random sets

A result of Fiz Pontiveros shows that if $A$ is a random subset of $\mathbb{Z}_N$ where each element is chosen independently with probability $N^{-1/2+o(1)}$ , then with high probability every Freiman homomorphism defined on $A$ can be extended to a Freiman homomorphism on the whole of $\mathbb{Z}_N$ . In this paper we improve the bound to $CN^{-2/3}(\log N)^{1/3}$ , which is best possible up to the constant factor.

preprint2016arXiv

Generalizations of Fourier analysis, and how to apply them

This is a survey of the use of Fourier analysis in additive combinatorics, with a particular focus on situations where it cannot be straightforwardly applied, but needs to be generalized first. Sometimes very satisfactory generalizations exist, while sometimes we have to make do with theories that have some of the desirable properties of Fourier analysis but not all of them. In the latter case, there are intriguing hints that there may be more satisfactory theories yet to be discovered. This article grew out of the Colloquium Lectures at the Joint Meeting of the AMS and the MAA, given in Seattle in January 2016.

preprint2016arXiv

Inverse and stability theorems for approximate representations of finite groups

The $U^2$ norm gives a useful measure of quasirandomness for real- or complex-valued functions defined on finite (or, more generally, locally compact) groups. A simple Fourier-analytic argument yields an inverse theorem, which shows that a bounded function with a large $U^2$ norm defined on a finite Abelian group must correlate significantly with a character. In this paper we generalize this statement to functions that are defined on arbitrary finite groups and that take values in M $_n(\mathbb C)$ . The conclusion now is that the function correlates with a representation -- though with the twist that the dimension of the representation is shown to be within a constant of $n$ rather than being exactly equal to $n$ . There are easy examples that show that this weakening of the obvious conclusion is necessary. The proof is much less straightforward than it is in the case of scalar functions on Abelian groups. As an easy corollary, we prove a stability theorem for near representations. It states that if $G$ is a finite group and $f:G\to$ M $_n(\mathbb C)$ is a function that is close to a representation in the sense that $f(xy)-f(x)f(y)$ has a small Hilbert-Schmidt norm (also known as the Frobenius norm) for every $x,y\in G$ , then there must be a representation $ρ$ such that $f(x)-ρ(x)$ has small Hilbert-Schmidt norm for every $x$ . Again, the dimension of $ρ$ need not be exactly $n$ , but it must be close to $n$ . We also obtain stability theorems for other Schatten $p$ -norms. A stability theorem of this kind was obtained for the operator norm by Grove, Karcher and Ruh in 1974 and in a more general form by Kazhdan in 1982. (For the operator norm, the dimension of the approximating representation is exactly $n$ .)

preprint2015arXiv

Combinatorial theorems in sparse random sets

We develop a new technique that allows us to show in a unified way that many well-known combinatorial theorems, including Turán's theorem, Szemerédi's theorem and Ramsey's theorem, hold almost surely inside sparse random sets. For instance, we extend Turán's theorem to the random setting by showing that for every $ε> 0$ and every positive integer $t \geq 3$ there exists a constant $C$ such that, if $G$ is a random graph on $n$ vertices where each edge is chosen independently with probability at least $C n^{-2/(t+1)}$ , then, with probability tending to $1$ as $n$ tends to infinity, every subgraph of $G$ with at least $(1 - \frac{1}{t-1} + ε) e(G)$ edges contains a copy of $K_t$ . This is sharp up to the constant $C$ . We also show how to prove sparse analogues of structural results, giving two main applications, a stability version of the random Turán theorem stated above and a sparse hypergraph removal lemma. Many similar results have recently been obtained independently in a different way by Schacht and by Friedgut, Rödl and Schacht.

preprint2015arXiv

Erdős and Arithmetic Progressions

This is a short survey article written for the Erdős centennial conference in Budapest in 2013. The main two topics covered are Szemerédi's theorem and its ramifications, and the Erdős discrepancy problem. There is an emphasis on what we do not yet know, so much of the article is somewhat speculative.

preprint2013arXiv

A fully automatic problem solver with human-style output

This paper describes a program that solves elementary mathematical problems, mostly in metric space theory, and presents solutions that are hard to distinguish from solutions that might be written by human mathematicians. The program is part of a more general project, which we also discuss.

preprint2013arXiv

On the KŁR conjecture in random graphs

The KŁR conjecture of Kohayakawa, Łuczak, and Rödl is a statement that allows one to prove that asymptotically almost surely all subgraphs of the random graph G_{n,p}, for sufficiently large p : = p(n), satisfy an embedding lemma which complements the sparse regularity lemma of Kohayakawa and Rödl. We prove a variant of this conjecture which is sufficient for most known applications to random graphs. In particular, our result implies a number of recent probabilistic versions, due to Conlon, Gowers, and Schacht, of classical extremal combinatorial theorems. We also discuss several further applications.

preprint2010arXiv

Linear forms and quadratic uniformity for functions on $\mathbb{F}_p^n$

We give improved bounds for our theorem in [GW09], which shows that a system of linear forms on $\mathbb{F}_p^n$ with squares that are linearly independent has the expected number of solutions in any linearly uniform subset of $\mathbb{F}_p^n$ . While in [GW09] the dependence between the uniformity of the set and the resulting error in the average over the linear system was of tower type, we now obtain a doubly exponential relation between the two parameters. Instead of the structure theorem for bounded functions due to Green and Tao [GrT08], we use the Hahn-Banach theorem to decompose the function into a quadratically structured plus a quadratically uniform part. This new decomposition makes more efficient use of the $U^3$ inverse theorem [GrT08].

preprint2008arXiv

Decompositions, approximate structure, transference, and the Hahn-Banach theorem

This paper is partly a survey of certain kinds of results and proofs in additive combinatorics, and partly a discussion of how useful the finite-dimensional Hahn-Banach theorem can be. The most interesting single result is probably a simpler proof of a key step in the proof of the Green-Tao theorem, but several other applications of the method are given. A similarly simplified proof of the Green-Tao transference principle was obtained independently (and expressed in a rather different language) by Reingold, Trevisan, Tulsiani and Vadhan.

preprint2007arXiv

The true complexity of a system of linear equations

It is well-known that if a subset A of a finite Abelian group G satisfies a quasirandomness property called uniformity of degree k, then it contains roughly the expected number of arithmetic progressions of length k, that is, the number of progressions one would expect in a random subset of G of the same density as A. One is naturally led to ask which degree of uniformity is required of A in order to control the number of solutions to a general system of linear equations. Using so-called "quadratic Fourier analysis", we show that certain linear systems that were previously thought to require quadratic uniformity are in fact governed by linear uniformity. More generally, we conjecture a necessary and sufficient condition on a linear system L which guarantees that any subset A of F_p^n which is uniform of degree k contains the expected number of solutions to L.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

W. T. Gowers

Research overview

Is this your work?

15 publications

Equidistribution of high-rank polynomials with variables restricted to subsets of $\mathbb{F}_p$

Partial associativity and rough approximate groups

A uniform set with fewer than expected arithmetic progressions of length 4

Generalizations of the Ruzsa-Szemerédi and rainbow Turán problems for cliques

Improved bounds for the Erdős-Rogers function

Freiman homomorphisms on sparse random sets

Generalizations of Fourier analysis, and how to apply them

Inverse and stability theorems for approximate representations of finite groups

Combinatorial theorems in sparse random sets

Erdős and Arithmetic Progressions

A fully automatic problem solver with human-style output

On the KŁR conjecture in random graphs

Linear forms and quadratic uniformity for functions on $\mathbb{F}_p^n$

Decompositions, approximate structure, transference, and the Hahn-Banach theorem

The true complexity of a system of linear equations

See the researcher in context

Building this map preview

W. T. Gowers

Research overview

Is this your work?

15 publications

Equidistribution of high-rank polynomials with variables restricted to subsets of Fp\mathbb{F}_pFp​

Partial associativity and rough approximate groups

A uniform set with fewer than expected arithmetic progressions of length 4

Generalizations of the Ruzsa-Szemerédi and rainbow Turán problems for cliques

Improved bounds for the Erdős-Rogers function

Freiman homomorphisms on sparse random sets

Generalizations of Fourier analysis, and how to apply them

Inverse and stability theorems for approximate representations of finite groups

Combinatorial theorems in sparse random sets

Erdős and Arithmetic Progressions

A fully automatic problem solver with human-style output

On the KŁR conjecture in random graphs

Linear forms and quadratic uniformity for functions on Fpn\mathbb{F}_p^nFpn​

Decompositions, approximate structure, transference, and the Hahn-Banach theorem

The true complexity of a system of linear equations

See the researcher in context

Building this map preview

Equidistribution of high-rank polynomials with variables restricted to subsets of $\mathbb{F}_p$

Linear forms and quadratic uniformity for functions on $\mathbb{F}_p^n$