An old conjecture in additive combinatorics asks: what is the largest sum-free subset of any set of N positive integers? Here the word "largest" should be understood in terms of cardinality. In this talk, I will discuss some recent progress on this conjecture, and the analogous conjecture on (k,l)-sum-free sets. The main method we used is Fourier analysis.
Let A be a subset of the d dimensional integer lattice and NA be the N-fold sumset. In 1992, Khovanskii proved that |NA| can be written as a polynomial in |A| of degree at most d, provided N is sufficiently large. We provide an effective bound for "sufficiently large", and discuss some related results.
We will discuss some old and new problems and results, mostly of Ramsey-theoretical and number-theoretical nature, which involve the additive and multiplicative structures in ℕ.
Let F be a finite subset of ℤd. We say that F is a translational tile of ℤd if it is possible to cover ℤd by translates of F with no overlaps. Given a finite subset F of ℤd, could we determine whether F is a translational tile in finite time? Suppose that F does tile, does it admit a periodic tiling? A well known argument of Wang shows that these two questions are closely related. In the talk, we will discuss this relation and present some new results, joint with Terence Tao, on the rigidity of tiling structures in ℤ2, and their applications to decidability.
A net is a subset of [0,1]d containing the expected number of points in every large dyadic subcube. Nets are one of the central objects in discrepancy theory, with numerous applications in numerical algorithms. In this talk, I will discuss a construction of sets that instead contain approximately correct number of points in every large dyadic subcube, and how these can be used to construct sets in ℝd without large convex holes.
We discuss some new lower bounds for the Erdős box problem, the problem of estimating the extremal number of the complete d-partite d-uniform hypergraph with two vertices in each part, thereby improving on work of Gunderson, Rödl and Sidorenko.
We discuss a new upper bound for sets with no square differences. This is joint work with T. Bloom.
Erdős and Szemerédi made the (still open) conjecture that for a finite set of natural numbers, A, either the sumset A+A, or else the productset AA, must be nearly as large as possible. A slightly different interpretation is that either A+A is large or log(A)+log(A) is large, where log(A) is the image of A under the (convex) logarithm function. This phenomenon is in fact more general, and extends to arbitrary convex functions f: if f has non-vanishing second derivative, then either A+A or else f(A)+f(A) is large. In recent work with Roche-Newton and Rudnev, we show that this growth persists when f has further non-vanishing derivatives.
Dual functions, known in ergodic theory as multiple correlation sequences, are an important but poorly-understood class of functions in additive combinatorics. An example of such a function is one that, given a subset A and element d, counts the number of arithmetic progressions in A with common difference d. To make progress on an equally poorly understood probabilistic version of Szemerédi's theorem with random common differences, it has been suggested to determine if dual functions can be decomposed in terms of "higher-order characters" (polynomial phases or nilsequences) plus a small error function. Conjectured bounds for Szemerédi's theorem with random differences were motivated by an apparent expectation that the error can always be taken to have small L∞ norm. It turns out that this is too much to hope for. In this talk we discuss counterexamples to such decompositions, ideas of which originate from coding theory.
Fix a word w in a free group on r generators. A w-random permutation in the symmetric group SN is obtained by sampling r independent uniformly random permutations σ1, . . .,σr ∈ SN and evaluating w(σ1, . . .,σr). Such w-random permutations have surprisingly rich structure with relation to deep results in geometric group theory. I'll survey some of this structure, state some conjectures, and explain how it is related to evaluating the spectral gap of random Schreier graphs of SN.
Let G1, . . ., Gk be vector spaces over a prime field 𝔽p. We say that a map Φ defined on a subset of the product G1 × . . . × Gk is a Freiman multi-homomorphism if Φ is a Freiman homomorphism in every principal direction (i.e. when xi in Gi is fixed for each i except one direction d, the map that sends element xd to Φ(x1,..., xk) is a Freiman homomorphism, where we allow those xd for which (x1,..., xk) is in the domain of Φ). It turns out that a Freiman multi-homomorphism defined on a dense subset of G1 × . . . × Gk necessarily coincides with a global multiaffine map at many points. In this talk we discuss the proof of this fact and some applications, which include a quantitative inverse theorem for the Gowers uniformity norms (in finite vector spaces in the case of large characteristic).
We show that the set of integers n for which n | (2n)!/(n!)2 has a positive asymptotic density, answering a question of Pomerance. The proof uses a mix of ideas from harmonic analysis and the anatomy of integers, and is joint work with Sergei Konyagin.
This video is part of the Webinar in Additive Combinatorics series, and this is their YouTube channel.
A subspace of 𝔽2n is called cyclically covering if every vector in 𝔽2n has a cyclic shift which is inside the subspace. Let h2(n) denote the largest possible codimension of a cyclically covering subspace of 𝔽2n. We show that h2(p) = 2 for every prime p such that 2 is a primitive root modulo p, which, assuming Artin’s conjecture, answers a question of Peter Cameron from 1991. In this talk, I will try to explain how we reduce the problem to a problem on finding odd subgraphs in which each vertex has odd outdegree in directed Cayley graphs, how additive combinatorics comes to the rescue and which open problems I would like to see solved. This is joint work with James Aaronson and Tom Johnston.
Hardy and Littlewood (1923) conjectured that for any integers x, y ≥ 2,
π(x + y) ≤ π(x) + π(y). (1)
Let us call a set {b1, . . . , bk} of integers admissible if for each prime p there is some congruence class mod p which contains none of the integers bi. The prime k-tuple conjecture states that if a set {b1, . . . , bk} is admissible, then there exist infinitely many integers n for which all the numbers n + b1, . . . , n + bk are primes.
Let x be a positive integer and ρ*(x) be the maximum number of integers in any interval (y, y +x] (with no restriction on y) that are relatively prime to all positive integers ≤ x. The prime k-tuple conjecture implies that
maxy≥x (π(x + y) − π(y)) = lim supy≥x (π(x + y) − π(y)) = ρ*(x).
Hensley and Richards (1974) proved that
ρ*(x) − π(x) ≥ (log 2 − o(1)) x (log x)−2 (x → ∞).
Therefore, (1) is not compatible with the prime k-tuple conjecture. Using a construction of Schinzel we show that
ρ*(x) − π(x) ≥ (log 2 − o(1)) x (log x)−2 log log log x (x → ∞).
We develop a sparse graph regularity method that applies to graphs with few 4-cycles, including new counting and removal lemmas for 5-cycles in such graphs. Some applications include:
• Every n-vertex graph with no 5-cycle can be made triangle-free by deleting o(n3/2) edges.
• For r ≥ 3, every n-vertex r-graph with girth greater than 5 has o(n3/2) edges.
• Every subset of [n] without a non-trivial solution to the equation x1 + x2 + 2x3 = x4 + 3x5 has size o(√n).
In 2016, Tao formulated a conjecture on the Gowers uniformity of the Möbius function in short intervals, which he showed to be equivalent to both the (logarithmic) Chowla and Sarnak conjectures. I will discuss work where we prove this conjecture for intervals of length X𝜺. I will then discuss applications to superpolynomial word complexity for the Liouville sequence and to a new averaged version of Chowla's conjecture.
Zaremba's conjecture belongs to the area of continued fractions. It predicts that for any given positive integer q there is a positive a, a less than q, (a,q)=1 such that all partial quotients bj in its continued fractions expansion a/q = 1/b1+1/b2 +... + 1/bs are bounded by five. At the moment the question is widely open although the area has a rich history of works by Korobov, Hensley, Niederreiter, Bourgain and many others. We survey certain results concerning this hypothesis and show how growth in groups helps to solve different relaxations of Zaremba's conjecture. In particular, we show that a deeper hypothesis of Hensley concerning some Cantor-type set with the Hausdorff dimension strictly greater than 1/2 takes place for the so-called modular form of Zaremba's conjecture.
Understanding approximate minimisers for isoperimetric problems is of fundamental importance in Combinatorics, Analysis and Geometry. We will survey some recent progress on these problems in three settings: the Extremal Combinatorics setting of the discrete cube (joint with Eoin Long), the Additive Combinatorics setting of Cayley digraphs on lattices (joint with Ben Barber, Joshua Erde and Alexander Roberts) and the Discrete Analysis setting of Boolean functions with small influence, with applications to sharp thresholds and Extremal Combinatorics via the Junta Method (joint with Noam Lifshitz, Eoin Long and Dor Minzer).
A subset D of a finite cyclic group ℤ/mℤ is called a perfect difference set if every nonzero element of ℤ/mℤ can be written uniquely as the difference of two elements of D. If such a set exists, then a simple counting argument shows that m=n2+n+1 for some non-negative integer n. Singer constructed examples of perfect difference sets in ℤ/(n2+n+1)ℤ whenever n is a prime power, and it is an old conjecture that these are the only such n for which a perfect difference set exists. In this talk, I will discuss a proof of an asymptotic version of this conjecture: the number of n<N for which ℤ/(n2+n+1)ℤ contains a perfect difference set is ~N/log(N).
In this talk, I will discuss recent work on pointwise ergodic theorems along bilinear polynomial ergodic averages (joint with M. Mirek and T. Tao) and its connections to additive combinatorics.
