The Cap Set problem
We presented Meshulam’s bound for the maximum number of elements in a subset A of not containing a triple x,y,x of distinct elements whose sum is 0.
The theorem is analogous to Roth’s theorem for 3-term arithmetic progressions and, in fact, it is a sort of purified analog to Roth’s proof, as some difficulties over the integers are not presented here. There are two ingredients in the proof: One can be referred to as the “Hardy-Littlewood circle method” and the other is the “density increasing” argument.
We first talked about density-increasing method and showed how KKL’s theorem for influence of sets follows from KKL’s theorem for the maximum individual influence. I mentioned what is known about influence of large sets and what is still open. (I will devote to this topic a separate post.)
Then we went over Meshulam’s proof in full details. A good place to see a detailed sketch of the proof is in this post What is difficult about the cap-set problem? on Gowers’ blog.
Let me copy Tim’s sketch over here:
Sketch of proof (from Gowers’s blog).
Next, here is a brief sketch of the Roth/Meshulam argument. I am giving it not so much for the benefit of people who have never seen it before, but because I shall need to refer to it. Recall that the Fourier transform of a function is defined by the formula
where is short for stands for and is short for Now
(Here stands for since there are solutions of ) By the convolution identity and the inversion formula, this is equal to
Now let be the characteristic function of a subset of density Then Therefore, if contains no solutions of (apart from degenerate ones — I’ll ignore that slight qualification for the purposes of this sketch as it makes the argument slightly less neat without affecting its substance) we may deduce that
Now Parseval’s identity tells us that
from which it follows that
Recall that The function is constant on each of the three hyperplanes (here I interpret as an element of ). From this it is easy to show that there is a hyperplane such that for some absolute constant (If you can’t be bothered to do the calculation, the basic point to take away is that if then there is a hyperplane perpendicular to on which has density at least where is an absolute constant. The converse holds too, though you recover the original bound for the Fourier coefficient only up to an absolute constant, so non-trivial Fourier coefficients and density increases on hyperplanes are essentially the same thing in this context.)
Thus, if contains no arithmetic progression of length 3, there is a hyperplane inside which the density of is at least If we iterate this argument times, then we can double the (relative) density of If we iterate it another times, we can double it again, and so on. The number of iterations is at most so by that time there must be an arithmetic progression of length 3. This tells us that we need lose only dimensions, so for the argument to work we need or equivalently
We discussed error-correcting codes. A binary code C is simply a subset of the discrete n-dimensional cube. This is a familiar object but in coding theory we asked different questions about it. A code is linear if it forms a vector space over The minimal distance of a code is the minimum Hamming distance between two distinct elements, and in the case of linear codes it is simply the minimum weight of a non-zero element of the codes. We mentioned codes over larger alphabets, spherical codes and even codes in more general metric spaces. Error-correcting codes are among the most glorious applications of mathematics and their theory is related to many topics in pure mathematics and theoretical computer science.
1) An extremal problem for codes: What is the maximum size of a binary code of length n with minimal distance d. We mentioned the volume (or Hamming) upper bound and the Gilbert-Varshamov lower bound. We concentrated on the case of codes of positive rate.
2) Examples of codes: We mentioned the Hamming code and the Hadamard code and considered some of their basic properties. Then we mentioned the long code which is very important in the study of Hardness of computation.
3) Linearity testing. Linearity testing is closely related to the Hadamard code. We described Blum-Luby-Rubinfeld linearity test and analyzed it. This is very similar to the Fourier theoretic formula and argument we saw last time for the cap problem.
We start to describe Delsartes linear Programming method to be continued next week.