Finite Analogs of Szemerédi's Theorem
By Paul Raff and Doron Zeilberger
[Appeared in "Gems in Experimental Mathematics"
(Contemporary Mathematics series (AMS) v. 517 (2010), T. Amdeberhan, L. Medina, and V. Moll, eds., 313-319.]
.pdf
.ps
.tex
Written: July 13, 2009.
One of the "deepest" theorems in mathematics is Endre Szemerédi's
theorem about the inevitability of arithmetical progressions.
Here we try to nibble at it, by doing "finite" analogs.
This is already interesting for its own sake, but
we believe that it has the potential to lead to
extermely interesting sharpening of the currently
rather weak bounds. Let's hope!
Added Aug. 13, 2024 Giorgio Parisi asked about words w, in the alphabet {0,1}, let's call them
(k,D)-Parisi words that have the property that w repeated infinitey many times avoids arithmetical progressions of length k with spacing ≤ D,
thereby approximating Szemeredi words, following the densities in the paper. So we wrote an extension of
the Maple package, ENDREplus.txt, that produced them.
For the output for k=3 and D up to 13 (skipping 12),
the input file, that produced the
output file.
The sets are up to circular rotations.
Maple and Mathematica Packages
Important: This article is accompanied by
Sample Input and Output for the Maple package ENDRE
-
In order to get the statements for the explicit expressions for R3,d(N),
the size of the maximal subset of [1,N] avoiding 3-term arithmetical progressions
with spacings ≤ d+1, for d between 0 and 6
the input
gives the output.
-
In order to get the statements for the explicit expressions for R4,d(N),
the size of the maximal subset of [1,N] avoiding 4-term arithmetical progressions
with spacings ≤ d+1, for d between 0 and 4
the input
gives the output.
-
In order to get the generating functions (in t), as well as the first 30 terms,
and the estimated asymptotics, of the counting sequences enumerating
n-letter binary words w[1]...w[n] such that there does not exist an i between 1 and n and
a d between 1 and D, such that w[i]w[i+d]w[i+2d]w[i+3d]=1010
(D=1..5)
the input
gives the output.
-
In order to get the generating functions (in t), as well as the first 30 terms,
and the estimated asymptotics, of the counting sequences enumerating
n-letter binary words w[1]...w[n] such that there does not exist an i between 1 and n and
a d between 1 and D, such that neither
w[i]w[i+d]w[i+2d]w[i+3d]=0000 nor
w[i]w[i+d]w[i+2d]w[i+3d]=1111 ,
(D=1..4)
the input
gives the output.
-
In order to find out which of the generalized single patterns of length 3
(with spacings between 0 and 5) is hardest to avoid, and which is easiest to avoid,
as well as complete generating functions, and asymptotics, for each such pattern
the input
gives the output.
-
In order to find out which of the generalized single patterns of length 4
(with spacings between 0 and 3) is hardest to avoid, and which is easiest to avoid,
as well as complete generating functions, and asymptotics, for each such pattern
the input
gives the output.
-
In order to find out which of the generalized single patterns of length 5
(with spacings between 0 and 2) is hardest to avoid, and which is easiest to avoid,
as well as complete generating functions, and asymptotics, for each such pattern
the input
gives the output.
-
In order to get a completely computer-generated but HUMAN-READABLE
statement and PROOF of the explicit expression (as a piece-wise linear function)
in n, for the number of n-letter binary words, in the alphabet {0,1} that
avoid 111, 1_1_1, and 1_ _ 1 _ _ 1, the
the input
gives the output.
Doron Zeilberger's List of Papers
Doron Zeilberger's Home Page