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.
You must be logged in to post a comment.