Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small.

*(English)*Zbl 1425.11019This paper represents without a doubt one of the most important breakthroughs in discrete mathematics in 2016. This is despite (or possibly to some extent because of) its relative brevity and elementary nature.

Given a finite abelian group \(G\), let \(r_k(G)\) denote the cardinality of a largest subset of \(G\) containing no non-trivial \(k\)-term arithmetic progression. The case when \(k=3\) and \(G\) is an \(n\)-dimensional vector space over a finite field of small fixed characteristic \(p\) is considered a toy problem for Roth’s problem in the integers [B. Green, in: Surveys in combinatorics 2005, Lond. Math. Soc. Lect. Note Ser. 327, 1–27 (2005; Zbl 1155.11306)], but it is also of independent interest to the design theory and theoretical computer science communities, amongst others.

R. Meshulam [J. Comb. Theory, Ser. A 71, No. 1, 168–172 (1995; Zbl 0832.11006)] proved that \[ r_3(\mathbb F^n_3) \ll 3^n/n, \] using a Fourier iteration argument going back to [K. F. Roth, J. Lond. Math. Soc. 28, 104–109 (1953; Zbl 0050.04002)] which is now considered standard in the field. Nudging this upper bound toward the lower bound of \[ 3^{0.72485n} \approx 2.2174^n\] provided by a construction of Y. Edel [Des. Codes Cryptography 31, No. 1, 5–14 (2004; Zbl 1057.51005)] has proved surprisingly difficult. It was only in 2012 that M. D. Bateman and N. H. Katz [J. Am. Math. Soc. 25, No. 2, 585–613 (2012; Zbl 1262.11010)], in a paper that is by many considered a technical tour de force, managed to improve the exponent of the denominator from \(1\) to \(1+\varepsilon\) for some small but explicit \(\varepsilon >0\).

Finite abelian groups \(G\) of even order were first considered by V. F. Lev J. Number Theory 104, No. 1, 162–169 (2004; Zbl 1043.11022)], who adapted Meshulam’s proof to show that \[ r_3(G) < 2|G|/\mathrm{rank}(2G). \] T. Sanders [Anal. PDE 2, No. 2, 211–234 (2009; Zbl 1197.11017)] improved upon this for the specific group \(G=(\mathbb Z/4\mathbb Z)^n\), showing that \[ r_3((\mathbb Z/4\mathbb Z)^n) \ll 4n/(n\log^\varepsilon n) \] for some absolute constant \(\varepsilon >0\), using a more sophisticated (but still Fourier-analytic) iteration technique.

The main result of the present paper is the following.

Theorem. Let \(n\ge 1\) and suppose that \(A\subseteq(\mathbb Z/4\mathbb Z)^n\) contains no non-trivial arithmetic progression of length \(3\). Then \[ |A| \le 4^{\gamma n} \] for a constant \(0<\gamma<1\).

Specifically, the constant \(\gamma\approx 0.926\) is obtained as the maximum over \(0<\varepsilon <1/4\) of \(\tfrac12(H(0.5-\varepsilon)+H(2\varepsilon))\), where \(H\) is the binary entropy function.

This result is of significance for at least two reasons: first, it represents an exponential improvement over previous work, bringing the upper bound for the first time within reasonable reach of the lower bound; second, it spawned a flurry of further results in the immediate aftermath of its publication. Arguably the most important of these to date is the paper by J. S. Ellenberg and D. C. Gijswijt [Ann. Math. (2) 185, No. 1, 339–343 (2017; Zbl 1425.11020)], which reduces the upper bound on \(r_3(\mathbb F^n_3)\) to roughly \(2.756^n\), alongside a handful of others that had not been formally published at the time that this review was written.

The core contribution of Croot, Lev and Pach is the realisation that a version of the polynomial method can be used to tackle Roth-type problems in certain finite abelian groups. For a comprehensive survey on the polynomial method, its variants and their applications, see [T. C. Tao, EMS Surv. Math. Sci. 1, No. 1, 1–46 (2014; Zbl 1294.05044)]. One recent application that stands out – having surfaced as unexpectedly as the result of the present paper – is the resolution of the finite-field Kakeya conjecture by Z. Dvir [J. Am. Math. Soc. 22, No. 4, 1093–1097 (2009; Zbl 1202.52021)].

The key ingredient in the proof of the above theorem is the following simple linear-algebraic lemma, also used in the aforementioned subsequent work of Ellenberg and Gijswijt: If \(P\) is a multilinear polynomial in \(n\) variables of total degree at most \(d\) over a field \(F\) such that \(P(a-b)=0\) for all \(a\ne b\in A\), then \(P(-a)\) cannot be non-zero for too many elements \(a\in A\).

This lemma can be used to prove that if \(A\) is a progression-free subset of \(\mathbb Z/4\mathbb Z)^n\) then there are few \(F_n\)-cosets containing many elements of \(A\), where \(F_n\) denotes the subgroup of \(\mathbb Z/4\mathbb Z)^n\) generated by its involutions (which is isomorphic to \((\mathbb Z/4\mathbb Z)^n))\). From this the bound on the size of \(A\) follows essentially by averaging and the tensor-power trick.

Given a finite abelian group \(G\), let \(r_k(G)\) denote the cardinality of a largest subset of \(G\) containing no non-trivial \(k\)-term arithmetic progression. The case when \(k=3\) and \(G\) is an \(n\)-dimensional vector space over a finite field of small fixed characteristic \(p\) is considered a toy problem for Roth’s problem in the integers [B. Green, in: Surveys in combinatorics 2005, Lond. Math. Soc. Lect. Note Ser. 327, 1–27 (2005; Zbl 1155.11306)], but it is also of independent interest to the design theory and theoretical computer science communities, amongst others.

R. Meshulam [J. Comb. Theory, Ser. A 71, No. 1, 168–172 (1995; Zbl 0832.11006)] proved that \[ r_3(\mathbb F^n_3) \ll 3^n/n, \] using a Fourier iteration argument going back to [K. F. Roth, J. Lond. Math. Soc. 28, 104–109 (1953; Zbl 0050.04002)] which is now considered standard in the field. Nudging this upper bound toward the lower bound of \[ 3^{0.72485n} \approx 2.2174^n\] provided by a construction of Y. Edel [Des. Codes Cryptography 31, No. 1, 5–14 (2004; Zbl 1057.51005)] has proved surprisingly difficult. It was only in 2012 that M. D. Bateman and N. H. Katz [J. Am. Math. Soc. 25, No. 2, 585–613 (2012; Zbl 1262.11010)], in a paper that is by many considered a technical tour de force, managed to improve the exponent of the denominator from \(1\) to \(1+\varepsilon\) for some small but explicit \(\varepsilon >0\).

Finite abelian groups \(G\) of even order were first considered by V. F. Lev J. Number Theory 104, No. 1, 162–169 (2004; Zbl 1043.11022)], who adapted Meshulam’s proof to show that \[ r_3(G) < 2|G|/\mathrm{rank}(2G). \] T. Sanders [Anal. PDE 2, No. 2, 211–234 (2009; Zbl 1197.11017)] improved upon this for the specific group \(G=(\mathbb Z/4\mathbb Z)^n\), showing that \[ r_3((\mathbb Z/4\mathbb Z)^n) \ll 4n/(n\log^\varepsilon n) \] for some absolute constant \(\varepsilon >0\), using a more sophisticated (but still Fourier-analytic) iteration technique.

The main result of the present paper is the following.

Theorem. Let \(n\ge 1\) and suppose that \(A\subseteq(\mathbb Z/4\mathbb Z)^n\) contains no non-trivial arithmetic progression of length \(3\). Then \[ |A| \le 4^{\gamma n} \] for a constant \(0<\gamma<1\).

Specifically, the constant \(\gamma\approx 0.926\) is obtained as the maximum over \(0<\varepsilon <1/4\) of \(\tfrac12(H(0.5-\varepsilon)+H(2\varepsilon))\), where \(H\) is the binary entropy function.

This result is of significance for at least two reasons: first, it represents an exponential improvement over previous work, bringing the upper bound for the first time within reasonable reach of the lower bound; second, it spawned a flurry of further results in the immediate aftermath of its publication. Arguably the most important of these to date is the paper by J. S. Ellenberg and D. C. Gijswijt [Ann. Math. (2) 185, No. 1, 339–343 (2017; Zbl 1425.11020)], which reduces the upper bound on \(r_3(\mathbb F^n_3)\) to roughly \(2.756^n\), alongside a handful of others that had not been formally published at the time that this review was written.

The core contribution of Croot, Lev and Pach is the realisation that a version of the polynomial method can be used to tackle Roth-type problems in certain finite abelian groups. For a comprehensive survey on the polynomial method, its variants and their applications, see [T. C. Tao, EMS Surv. Math. Sci. 1, No. 1, 1–46 (2014; Zbl 1294.05044)]. One recent application that stands out – having surfaced as unexpectedly as the result of the present paper – is the resolution of the finite-field Kakeya conjecture by Z. Dvir [J. Am. Math. Soc. 22, No. 4, 1093–1097 (2009; Zbl 1202.52021)].

The key ingredient in the proof of the above theorem is the following simple linear-algebraic lemma, also used in the aforementioned subsequent work of Ellenberg and Gijswijt: If \(P\) is a multilinear polynomial in \(n\) variables of total degree at most \(d\) over a field \(F\) such that \(P(a-b)=0\) for all \(a\ne b\in A\), then \(P(-a)\) cannot be non-zero for too many elements \(a\in A\).

This lemma can be used to prove that if \(A\) is a progression-free subset of \(\mathbb Z/4\mathbb Z)^n\) then there are few \(F_n\)-cosets containing many elements of \(A\), where \(F_n\) denotes the subgroup of \(\mathbb Z/4\mathbb Z)^n\) generated by its involutions (which is isomorphic to \((\mathbb Z/4\mathbb Z)^n))\). From this the bound on the size of \(A\) follows essentially by averaging and the tensor-power trick.

Reviewer: Julia Wolf

##### Citations:

Zbl 1155.11306; Zbl 0832.11006; Zbl 0050.04002; Zbl 1057.51005; Zbl 1262.11010; Zbl 1043.11022; Zbl 1197.11017; Zbl 1425.11020; Zbl 1294.05044; Zbl 1202.52021
PDF
BibTeX
XML
Cite

\textit{E. Croot} et al., Ann. Math. (2) 185, No. 1, 331--337 (2017; Zbl 1425.11019)

Full Text:
DOI

**OpenURL**

##### References:

[1] | M. Bateman and N. H. Katz, ”New bounds on cap sets,” J. Amer. Math. Soc., vol. 25, iss. 2, pp. 585-613, 2012. · Zbl 1262.11010 |

[2] | T. F. Bloom, ”A quantitative improvement for Roth’s theorem on arithmetic progressions,” J. Lond. Math. Soc., vol. 93, iss. 3, pp. 643-663, 2016. · Zbl 1364.11024 |

[3] | J. Bourgain, ”On triples in arithmetic progression,” Geom. Funct. Anal., vol. 9, iss. 5, pp. 968-984, 1999. · Zbl 0959.11004 |

[4] | T. C. Brown and J. P. Buhler, ”A density version of a geometric Ramsey theorem,” J. Combin. Theory Ser. A, vol. 32, iss. 1, pp. 20-34, 1982. · Zbl 0476.51008 |

[5] | P. Frankl, R. L. Graham, and V. Rödl, ”On subsets of abelian groups with no \(3\)-term arithmetic progression,” J. Combin. Theory Ser. A, vol. 45, iss. 1, pp. 157-161, 1987. · Zbl 0613.10043 |

[6] | D. R. Heath-Brown, ”Integer sets containing no arithmetic progressions,” J. London Math. Soc., vol. 35, iss. 3, pp. 385-394, 1987. · Zbl 0589.10062 |

[7] | V. F. Lev, ”Progression-free sets in finite abelian groups,” J. Number Theory, vol. 104, iss. 1, pp. 162-169, 2004. · Zbl 1043.11022 |

[8] | V. F. Lev, ”Character-free approach to progression-free sets,” Finite Fields Appl., vol. 18, iss. 2, pp. 378-383, 2012. · Zbl 1284.11020 |

[9] | F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam: North-Holland Publ. Co., 1977. · Zbl 0369.94008 |

[10] | R. Meshulam, ”On subsets of finite abelian groups with no \(3\)-term arithmetic progressions,” J. Combin. Theory Ser. A, vol. 71, iss. 1, pp. 168-172, 1995. · Zbl 0832.11006 |

[11] | K. Roth, ”Sur quelques ensembles d’entiers,” C. R. Acad. Sci. Paris, vol. 234, pp. 388-390, 1952. · Zbl 0046.04302 |

[12] | K. Roth, ”On certain sets of integers,” J. London Math. Soc., vol. 28, pp. 104-109, 1953. · Zbl 0050.04002 |

[13] | T. Sanders, ”Roth’s theorem in \(\mathbb Z^n_4\),” Anal. PDE, vol. 2, iss. 2, pp. 211-234, 2009. · Zbl 1197.11017 |

[14] | T. Sanders, ”On certain other sets of integers,” J. Anal. Math., vol. 116, pp. 53-82, 2012. · Zbl 1280.11009 |

[15] | T. Sanders, ”On Roth’s theorem on progressions,” Ann. of Math., vol. 174, iss. 1, pp. 619-636, 2011. · Zbl 1264.11004 |

[16] | E. Szemerédi, ”Integer sets containing no arithmetic progressions,” Acta Math. Hungar., vol. 56, iss. 1-2, pp. 155-158, 1990. · Zbl 0721.11007 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.