Problems in additive and extremal combinatorics

Lead Research Organisation: University of Cambridge
Department Name: Pure Maths and Mathematical Statistics

Abstract

This research will focus on a cluster of related problems and concepts that belong to additive combinatorics, an area of mathematics at the interface between analytic number theory, extremal combinatorics, harmonic analysis, dynamical systems, and group theory. The common feature of the problems is that they tend to be of a combinatorial flavour, and fairly easy to state, and that the right approach to these problems is usually to bring in tools from other areas. Over the last twenty years or so, this has led to a very fruitful cross-fertilization, and also to a number of very interesting questions, some of which will be attempted during this thesis.

Publications

10 25 50
publication icon
Karam T (2024) Simple proofs for lattice coverings and sparse tensors

 
Description The work that I undertook during my Ph.D. has primarily led to four results involving tensors, polynomials on finite fields, and Ramsey theory,

The first topic to which I made a contribution, in individual work, is that of ranks of tensors. It is a standard fact of linear algebra that every rank-k matrix contains a k x k submatrix with rank k, and I have generalised an asymptotic version of this fact to higher-order tensors and to a wide class of notions of rank, comprising several of the notions of rank that frequently arise in combinatorics, such as the tensor rank, the slice rank and the partition rank: if an order-d tensor has high rank then there exist subsets X_1,..,X_d of the coordinate sets, each with bounded size, such that the subtensor obtained by restricting the original tensor to its entries in the box X_1 x .. x X_d has high rank. I have furthermore shown that under a natural assumption we can moreover take the sets X_1,..,X_d to be pairwise disjoint.

Secondly, in joint work with Timothy Gowers I extended a result of Green and Tao from 2007 on the equidistribution of polynomials. Green and Tao had originally showed that if a low-degree polynomial F_p^n -> F_p on a finite prime field does not take every value with approximately the same frequency, then the polynomial has bounded rank, that is, it can be expressed as a function of a bounded number of polynomials of strictly smaller degree. We showed that a similar result holds if we only consider the distribution of the polynomial on S^n for some non-empty subset S of F_p: if the polynomial is not approximately equidistributed when restricted to S^n, then it coincides on S^n with a polynomial with bounded rank.

In a third project, Gowers and I proved approximation results on sets defined by systems of conditions in vector spaces over F_p, generalising qualitatively the fact that the size of a non-empty solution set of a system of linear equations is determined by the dimension of the linear subspace spanned by the linear forms involved in the system. For instance, we showed that even if we only look for solutions inside the cube {0,1}^n and merely have conditions rather than equations, then the following property is still satisfied: if the solution set (inside the cube) of a system of linear conditions is dense, then it can be internally approximated by the solution set (inside the cube) of a system of conditions with bounded size. We also proved a similar but slightly weaker result for systems of polynomial conditions.

Finally, Gowers and I showed that modular obstructions cannot be used to build counterexamples to the polynomial density Hales-Jewett conjecture, a central open problem in Ramsey theory which if positively settled would in particular imply as special cases two important results in the area: the polynomial Szemeredi theorem and the density Hales-Jewett theorem.
Exploitation Route My papers end with a reasonably large number of questions raised by the results and proofs, and we can hope that some of them will eventually be answered. Besides these, there are several unfinished projects which are to some extent related to the work produced during my Ph.D., and which could potentially lead to interesting results, that would then in turn be of use to others. Also, the fact that the results pertain to properties of central objects and tools in combinatorics makes it likely that future discoveries will eventually follow.

This work, including my individual work, has been cited in papers by very good mathematicians, discussed at top international workshops and conferences, and I have received expressions of interest in my results and proof techniques.

The main motivations of this work are from pure mathematics, and I expect that its likely applications, at least in the short term, will be to pure mathematics as well. Because several of the main results specialise to statements in the Boolean cube {0,1}^n, they may turn out to have applications in computer science, although that is speculation.
Sectors Other