Suppose that A is a finite, non-empty subset of a cyclic group of either infinite or prime order. We show that if the difference set A-A is 'not too large', then there is a non-zero group element with at least as many as (2+o(1))|A|2/|A-A| representations as a difference of two elements of A; that is, the second largest number of representations is, essentially, twice the average. Here the coefficient 2 is best possible.
For a subset A of a finite-dimensional vector space over a finite field, It is known that 2A-2A must contain a subgroup of density that is quasi-polynomial in the density of A. We show an analogue result for the special linear group over a finite field, except we achieve a polynomial density for the subgroup. The main tool used is a new hyper-contractive estimate for the special linear group, that has origins in the study of 2-to-2 games.
A central question in additive combinatorics is to understand how large arithmetic progression-free sets can be. In this talk, I will focus on this question for high-dimensional generalization of arithmetic progressions (AP) known as corners. A (2-dimensional) corner is a triple of the form (x,y),(x+d,y),(x,y+d) for some d>0 in [N] × [N]. Extending this definition to higher dimensions, a k-dimensional corner in [N]k is a (k+1)-tuple defined similarly for some d. While it is known that corner-free sets have a vanishingly small density, the precise bounds on their size remain unknown. Until recently, the best-known corner-free sets were derived from constructions of AP-free sets: a construction of a 3-term AP-free set by Behrend from 1946, and a generalization by Rankin for k-term APs in 1961. New results by Linial and Shraibman (CCC 2021) and Green (New Zealand Journal of Mathematics 2021) changed this picture; they improved the upper bound for k=2 by adopting a communication complexity point of view.
I will discuss our recent work where we employ the same perspective of communication complexity and obtain the first improvement on the upper bound of the size of high-dimensional (k>2) corner-free sets since the original construction of Rankin.
Suppose that N is large and that A is a subset of {1,..,N} which does not contain two elements x, y with x - y equal to p-1, p a prime. Then A has cardinality at most N1 - c, for some absolute and positive c. I will discuss the history of this kind of question as well as some aspects of the proof of the stated result.
Ruzsa asked whether there exist Fourier-uniform subsets of ℤ/Nℤ with very few 4-term arithmetic progressions (4-AP). The standard pedagogical example of a Fourier-uniform set with a "wrong" density of 4-APs actually has 4-AP density much higher than random. Can it instead be much lower than random? Gowers constructed Fourier uniform sets with 4-AP density at most α4+c. It remains open whether a superpolynomial decay is possible. We will discuss this question and some variants. We relate it to an arithmetic Ramsey question: can one No(1)-color of [N] avoiding symmetrically-colored 4-APs?
We show that for every positive integer k there are positive constants C and c such that if A is a subset of {1, 2, ..., n} of size at least C n1/k, then, for some d ≤ k-1, the set of subset sums of A contains a homogeneous d-dimensional generalized arithmetic progression of size at least c|A|d+1. This strengthens a result of Szemerédi and Vu, who proved a similar statement without the homogeneity condition. As an application, we make progress on the Erdős-Straus non-averaging sets problem, showing that every subset A of {1, 2, ..., n} of size at least n√2 - 1 + o(1) contains an element which is the average of two or more other elements of A. This gives the first polynomial improvement on a result of Erdős and Sárközy from 1990.
It is an open question as to whether the prime numbers contain the sum A+B of two infinite sets of natural numbers A, B (although results of this type are known assuming the Hardy-Littlewood prime tuples conjecture). Using the Maynard sieve and the Bergelson intersectivity lemma, we show the weaker result that there exist two infinite sequences a1 < a2 < ... and b1 < b2 < ... such that ai + bj is prime for all i < j. Equivalently, the primes are not 'translation-finite' in the sense of Ruppert. As an application of these methods we show that the orbit closure of the primes is uncountable.
It is an open question as to whether the prime numbers contain the sum A+B of two infinite sets of natural numbers A, B (although results of this type are known assuming the Hardy-Littlewood prime tuples conjecture). Using the Maynard sieve and the Bergelson intersectivity lemma, we show the weaker result that there exist two infinite sequences a 1 < a 2 < ... and b 1 < b 2 < ... such that ai + bj is prime for all i < j. Equivalently, the primes are not "translation-finite" in the sense of Ruppert. As an application of these methods we show that the orbit closure of the primes is uncountable.
In a joint work with Daniel Fiorilli, we develop a new method to prove lower bounds of some moments related to the distribution of primes in arithmetic progressions. We shall present main results and explain some aspects of the proofs. To prove our results, we assume GRH but we succeed to avoid linearly independence on zeroes hypothesis.
We discuss some recent progress on the model-theoretic problem of classifying the reducts of the complex field (with named parameters and up to interdefinability). The tools we use include Castle’s recent solution of the Restricted Trichotomy Conjecture in characteristic 0 and a generalized sumproduct result from additive combinatorics.
In late 2021, Bloom resolved an old conjecture of Erdős and Graham, showing that in any subset of the positive integers of positive density, there exists a solution to 1/n1 + 1/n2 + ... + 1/nk = 1 with all ni distinct. We discuss the formal verification of this proof in the Lean theorem prover, including prerequisites from analytic number theory and Fourier analysis, and an instance of the circle method. This is joint work with Thomas Bloom.
Given several real numbers α1,...,αk, how well can you simultaneously approximate all of them by rationals which each have the same square number as a denominator? Schmidt gave a clever iterative argument which showed that this can be done moderately well.
By using a general principle of 'little non-trivial additive structure in rationals' and some ideas from additive combinatorics and the geometry of numbers, I'll describe how this can be improved to give a close-to-optimal answer when k is large.
A famous conjecture of Littlewood states that the Fourier transform of every set of N integers has l1 norm at least log(N), up to a constant multiplicative factor. This was proved independently by McGehee-Pigno-Smith and Konyagin in the 1980s. This lower bound is the best possible, as it is achieved by an arithmetic progression. An interesting question, especially from the perspective of additive combinatorics, is the 'inverse problem': what can we say about sets which are close to optimal, say with l1 norm at most 100 log(N)? I will discuss can inverse result of this type, showing that (in a certain sense) such sets are approximately the union of O(1) sets with small doubling.
It is well known that if a finite set of integers A tiles the integers by translations, then the translation set must be periodic, so that the tiling is equivalent to a factorization A+B=ZM of a finite cyclic group. Coven and Meyerowitz (1998) proposed a characterization of all finite tiles in terms of the cyclotomic divisors of associated mask polynomials, and proved it when the tiling period M has at most two distinct prime factors. In joint work with Itay Londner, we extended it to the case when M=(pqr)2, where p,q,r are distinct primes. The methods we developed can be applied to other questions that hinge on cyclotomic divisibility, ranging from number theory to harmonic analysis and geometric measure theory. In particular, Caleb Marshall and I were able to use cyclotomic divisibility methods to prove new Favard length estimates for product Cantor sets. The talk will provide an introduction to this group of problems.
In many recent works, analysis and number theory go beyond working side by side and team up in an interconnected back and forth interplay to become a powerful force. Here I describe two distinct meetings of the pair, which result in sharp counts for equilateral triangles in Euclidean space and statistics for how often a random polynomial has Galois group not isomorphic to the full symmetric group.
In Bernoulli bond percolation, one defines a random subgraph of a given connected graph G by deleting or retaining edges of G independently at random, each edge being retained with the same probability p. When G is infinite, a central and classical question is whether there exists a choice of p strictly less than 1 such that this random subgraph has infinite connected components. When G is finite, a natural analogue is to ask whether there exists a choice of p bounded away from 1 such that the random subgraph contains a connected component containing at least half (or 1% or 99%) of the vertices of G. Tom Hutchcroft and I recently showed that such a p exists provided G is not close to a cycle in some sense, confirming most cases of a conjecture of Benjamini (2001). I will give an overview of the proof, and go into some detail on certain aspects of it that have a distinctly additive combinatorial flavour.
We prove that the size of the product set of any finite arithmetic progression A in integers of size N is at least N2/(log N)c+o(1), where c=1-(1+loglog 2)/(log 2). This matches the bound in the celebrated Erdos multiplication table problem, up to a factor of (log N)o(1) and thus confirms a conjecture of Elekes and Ruzsa. If instead A is relaxed to be a subset of a finite arithmetic progression in integers with positive constant density, we prove that the size of the product set is at least N2/(log N)2log2-1 + o(1). This solves the typical case of another conjecture of Elekes and Ruzsa on the size of the product set of a set A whose sum set is of size O(|A|).This is joint work with Yunkun Zhou.
(Joint with Jacob Fox, Matthew Kwan) Classical anti-concentration results show "random walks in ℝd with BIG independent steps can't concentrate in balls much better than they can concentrate on individual points". Model-theoretic definable sets include boolean combinations of subsets of ℝd defined using equalities and inequalities of arbitrary compositions of polynomials, ex, ln(x) and analytic functions restricted to compact boxes. For example, the intersection of esin(1/(1+(xyz)2))+x2y+zy ≥ 0 and xyz=5 in ℝ3. In this talk, I will discuss recent results which show "random walks in ℝd with ARBITRARY independent steps can't concentrate in definable sets not containing line segments much better than they can concentrate on individual points". Time permitting, I will discuss how these results extend to other groups like GLd(ℝ).
In 2001 Croot resolved an old conjecture of Erdős and Graham, proving that in any finite colouring of the positive integers there is a (non-trivial) monochromatic solution to 1/n1+...+1/nk = 1 with all ni distinct. A natural generalisation, also conjectured by Erdos and Graham, is that in fact any set of positive density contains such a solution. We will discuss the proof of this conjecture, which extends Croot's method, and uses Fourier analysis coupled with elementary number theoretic and combinatorial arguments.
A key tool in modern additive combinatorics, going back to Gowers' proof of Szemeredi's theorem, is that counts of linear configurations are controlled by Gowers norms. For example, if S and T are two dense sets and |S-T|Uk-1 is small then S and T have roughly the same number of k-term arithmetic progressions. Like many other core arguments in the field, this is proven by (k-1) applications of the Cauchy--Schwarz inequality. Generalizations of this statement quickly become subtle. For example, linear configurations (x, x+z, x+y, x+y+z, x+2y+3z, 2x+3y+6z) are controlled by the U2-norm (i.e., by normal Fourier analysis) but it is not at all straightforward to prove this just with Cauchy--Schwarz; whereas controlling (x, x+z, x+y, x+y+z, x+2y+3z, 13x+12y+9z) requires the U3-norm (i.e., quadratic Fourier analysis). A conjecture of Gowers and Wolf (resolved combining work of Gowers--Wolf, Green--Tao, Hatami--Hatami--Lovett and Altman) gives a condition to determine the smallest Uk-norm required for a given configuration, but the proofs require deep structure theorems and (unlike Cauchy--Schwarz arguments) give very weak bounds. In this talk, I will describe how it is (sometimes) possible to find the missing Cauchy--Schwarz arguments by "mining proofs". The equality cases of these inequalities correspond (it turns out) to facts about functional equations. For example, the k-term progression case states the following: if f1,...,fk are functions such that f1(x)+f2(x+h)+...+fk(x+(k-1)h) = 0 for all x,h, then each fi must be a polynomial of degree at most k-2. This statement is not completely obvious but has a short elementary proof. Given such an elementary proof (at least, one of a special type), we can recover an iterated Cauchy--Schwarz proof of the corresponding inequality -- albeit a very long and complicated one that would be hard to discover by hand. This answers the Gowers--Wolf question with polynomial bounds, and hopefully other questions where the availability of complicated Cauchy--Schwarz arguments is a limiting factor.
