Yet another post on a.p. free set bounds

The last few weeks have seen amazing results in additive combinatorics, where following a breakthrough by Croot, Lev and Pach, several longstanding open questions have been resolved using short simple proofs. I haven’t been following this progress, but fortunately Bobby Kleinberg gave an excellent talk yesterday in our reading group about some of these works, and their relations to TCS questions such as approaches for fast matrix multiplication. Since the proofs are short and these results also been extensively blogged about, what follows is mainly for my own benefit.

Among other things, Bobby showed the proof of the following result, that demonstrates much of those ideas:

Theorem: (Ellenberg and Gijswijt, building on Croot-Lev-Pach) There exists an absolute constant $\epsilon>0$ such that for every $A \subseteq {\mathbb{F}}_3^n$ , if $|A|> (3-\epsilon)^n$ then $A$ contains a 3-term arithmetic progression.

To put this in perspective, up till a few weeks ago, the best bounds were of the form $3^n/n^{1+\epsilon}$ and were shown using fairly complicated proofs, and it was very reasonable to assume that a bound of the form $3^{n-o(n)}$ is the best we can do. Indeed, an old construction of Behrend shows that this is the case in other groups such as the integers modulo some large $N$ or ${\mathbb{F}}_p^n$ where $p$ is some large value depending on $n$ . The proof generalizes to ${\mathbb{F}}_q$ for every constant prime $q$ (and for composite order cyclic groups as well).

The proof is extremely simple. It seems to me that it can be summarized to two observations:

Due to the algebraic structure of the problem, one can “interpolate” in some sense a $3$ -a.p. free set $A$ with a polynomial of degree that is a half as small than you would expect otherwise.
Due to concentration of measure phenomena in finite fields, this constant multiplicative factor makes a huge difference. There are values $d$ for which polynomials of degree $d$ make up all but an exponentially small fraction of the functions from ${\mathbb{F}}_3^n$ to ${\mathbb{F}}$ , while polynomials of degree $d/2$ only constitute an exponentially small fraction of these functions.

Let’s now show the proof. Assume towards a contradiction that $A\subseteq {\mathbb{F}}_3$ satisfies $|A|\geq (3-\epsilon)^n$ ( $\epsilon$ can be some sufficiently small constant, $\epsilon=0.1$ will do) but there do not exist three distinct points $a,c,b \in A$ that form a $3$ -a.p. (i.e., such that $c-a = b-c$ or, equivalently, $a+b = 2c$ ).

Let $L(d)$ be the number of $n$ -variate monomials over ${\mathbb{F}}_3$ where each variable has individual degree at most $2$ (higher degree can be ignored modulo $3$ ) and the total degree is at most $n$ . Note that there are $3^n$ possible monomials where each degree is at most two, and their degree ranges from $0$ to $2n$ , where by concentration of measure most of them have degree roughly $n$ . Indeed, using the Chernoff bound we can see that if $\epsilon>0$ is a sufficiently small constant, we can pick some $\delta>0$ such that if $d = (2-\delta)n$ then $L(d) \geq 3^n - 0.1(3-\epsilon)^n$ but $L(d/2) \leq 0.1(3-\epsilon)^n$ (to get optimal results, one sets $d$ to be roughly $4n/3$ and derives $\epsilon$ from this value).

Now, if we choose $d$ in that manner, then we can find a polynomial $P:{\mathbb{F}}_3^n\rightarrow{\mathbb{F}}$ of degree at most $d$ that vanishes on $\overline{A} = {\mathbb{F}}_3^n \setminus A$ but is non zero on at least $|A|/2$ points. Indeed, finding such a polynomial amounts to solving a set of $3^n - |A|/2$ linear equations in $L(d)\geq 3^n - 0.1|A|$ variables.¹ Define the $|A|\times |A|$ matrix $M$ such that $M_{a,b}= P((a+b)/2)$ . Since the assumption that $|A| \geq (3-\epsilon)^n$ implies that $L(d/2) \leq 0.1|A|$ , the theorem follows immediately from the following two claims:

Claim 1: ${\mathrm{rank}}(M) \geq |A|/2$ .

Claim 2: ${\mathrm{rank}}(M) \leq 2L(d/2)$ .

Claim 1 is fairly immediate. Since $A$ is $3$ -a.p. free, for every $a\neq b$ , $(a+b)/2$ is not in $A$ and hence $M$ is zeros on all the off diagonal elements. On the other hand, by the way we chose it, $M$ has at least $|A|/2$ nonzeroes on the diagonal.

For Claim 2, we expand $P((a+b)/2)$ as a polynomial of degree $d$ in the two variables $a$ and $b$ , and write $M=M'+M''$ where $M'$ corresponds to the part of this polynomial where the degree in $a$ is at most $d/2$ and $M''$ corresponds to the part where the degree in $a$ is larger and hence the degree in $b$ is at most $d/2$ . We claim that both ${\mathrm{rank}}(M')$ and ${\mathrm{rank}}(M'')$ are at most $L(d/2)$ . Indeed, we can write $M'_{a,b}$ as $\sum_{\alpha} C_{\alpha} a^{\alpha} P_\alpha(b)$ for some coefficients $C_\alpha\in {\mathbb{F}}_3$ and polynomials $P_\alpha$ , where $\alpha$ indexes the $L(d/2)$ monomials in $a$ of degree at most $d/2$ . But this shows that $M'$ is a sum of at most $L(d/2)$ rank one matrices and hence ${\mathrm{rank}}(M')\leq L(d/2)$ . The same reasoning shows that ${\mathrm{rank}}(M'') \leq L(d/2)$ thus completing the proof of Claim 2 and the theorem itself.

More formally, we can argue that the set of degree $d$ polynomials that vanish on $\overline{A}$ has dimension at least $L(d)-|\overline{A}| \geq 0.9|A|$ and hence it contains a polynomial with at least this number of nonzero values.↩

	James Cross on GPT as an “Intelligence…
	Thoughts on AI safet… on AI will change the world, but…
	Anonymous on An alarming trend in K-12 Math…
	Interview about this… on Men in Computer Science
	Interview about this… on The Swiss Army Knife of C…

Yet another post on a.p. free set bounds

Published by Boaz Barak

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by Boaz Barak

Leave a Reply Cancel reply