A Motivated Rendition of the Ellenberg-Gijswijt Gorgeous proof that the Largest Subset of F3n with No
Three-Term Arithmetic Progression is O(cn), with c=2.75510461302363300022127...
By Doron Zeilberger
.pdf
.ps
.tex
(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org )
Written: July 6, 2016
Inspired by the
Croot-Lev-Pach
breakthrough,
Jordan Ellenberg and Dion Gijswijt have recently
amazed the combinatorial world by
proving that the largest size of a subset of F3n with no 3-term arithmetic progressions is exponentially less than
3n (and more generally, for Fqn, qn),
Here we give a motivated, top-down, rendition of their beautiful proof, that aims to make it appreciated by a wider
audience.
Maple package
-
Fqn.txt,
a Maple package to compute the sequences (and their asympototics) that feature as upper bounds for
the size of subsets of Fqn with no 3-term arithematic progressions.
Sample Input and Output Files for the Maple package Fqn.txt
-
If you want to see the sequences, recurrence, and asymptotics for F3n
the input file generates the
output file.
-
If you want to see the sequences, recurrence, and asymptotics for F4n
the input file generates the
output file.
-
If you want to see the sequences, recurrence, and asymptotics for F5n
the input file generates the
output file.
-
If you want to see the sequences, recurrence, and asympototics for F7n
the input file generates the
output file.
-
If you want to see the sequences, recurrence, and asympototics for F8n
the input file generates the
output file.
-
If you want to see the sequences, recurrence, and asympototics for F9n
the input file generates the
output file.
-
If you want to see the sequences, recurrence, and asympototics for F11n
the input file generates the
output file.
-
If you want to see the sequences, recurrence, and asympototics for F13n
the input file generates the
output file.
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page