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.
An LMS online lecture course in combinatorial number theory.
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.
You must be logged in to post a comment.