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!

Maple and Mathematica Packages

• Maple Package

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...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...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