%szemeredi.tex:
%%a Plain TeX file by Paul Raff and Doron Zeilberger (x pages)
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
Finite Versions of Szemer\'edi's Theorem on Arithmetical Progressions
}
\rm
\bigskip
\centerline{ {\it
Paul RAFF{$^1$} and
Doron 
ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt [praff,zeilberg]  at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}[praff,zeilberg]} .
First version: June 3, 2009.
Accompanied by Maple package {\eighttt ENDRE} and Mathematica package
downloadable from the authors' websites.
Supported in part by the NSF.
}
}

{\bf Introduction}

One of the crowning achievements of combinatorics and number theory ([S]) is

{\bf Szemer\'edi's Theorem}: For any positive integer $k$, and any positive integer $n$,
let $S_k(n)$ be the size of the largest subset of $[1,n]$ that {\it avoids}
arithmetical progressions of size $k$. Then
$$
\lim_{ n \rightarrow \infty}  {{S_k(n)} \over {n}}  \, = 0  \quad .
$$
The exact rate of convergence is not known, but quite a few Fields-medalists (Bourgain, Gowers, Tao) are trying to make
it quantitative, but their results are (probably) far from sharp.

In this article, we offer yet-another-approach, that we believe does have the potential, eventually, to tackle the ``deep questions'',
and at any rate, is of independent interest. Let's study ``{\it finite}'' versions of Szemer\'edi's theorem.

Fix $k$ (the size of the arithmetic progression) and $d$, a positive integer, and let
$f_{k,d}(n)$ be the cardinality of the largest subset of $\{1,2, \dots , n\}$ that avoids
arithmetic progressions of size $k$ whose {\it difference} is $\leq d$. In other words
$f_{k,d}(n)$ is the size of largest subset of $\{1,2, \dots, n \}$, that does not contain
any subset of the form
$$
\{ a, a+j,  a+2j, \dots,   a+(k-1)j \}
$$
and $j \leq d$. We will see below that $f_{k,d}(n)$ is eventually periodic, in the sense that
there exist a period  $P=P_{k,d}$  and an integer $Q=Q_{k,d}$ such that, starting at a $N_{k,d}$
$$
f_{k,d}(Pm+i)=Qm+\alpha_i \quad , \quad i=1 \dots P \quad
$$
with certain $\alpha_i$ with $0 \leq \alpha_i \leq Q$. 
We will present fully implemented algorithms to conjecture $P_{k,d}$, $Q_{k,d}$, and the $\alpha_i$'s, and
then prove that the conjecture is true (completely automatically).
In particular, we would have
$$
C_{k,d} := \lim_{n \rightarrow \infty} {{f_{k,d}(n)} \over {n}} = {{Q_{k,d}} \over {P_{k,d}} } \quad.
$$
Another way of stating Szemer\'edi's theorem is 
$$
\lim_{ d \rightarrow \infty} C_{k,d} \, = \, 0 \quad .
$$
Hopefully more extensive computations would give, for specific $k=3,4, \dots$ (and perhaps eventually for general $k$)
a {\it trend}, that may give experimental insight
about the rate of convergence of $C_{k,d}$. We also believe that our approach may suggest a novel rigorous approach
that may eventually yield rigorous lower and upper bounds on $C_{k,d}$, by studying, in general terms,
the appropriate system of equations defined below, that determine $P_{k,d}$, $Q_{k,d}$, and hence $C_{k,d}$.
This, in turn, may enable to improve the current lower and upper bounds for the behaviour of $S_k(n)$ itself.





{\bf References}

[S] E. Szemer\'edi, {\it On sets of integers containing no k elements in arithmetic progression}, Acta Arithmetica {\bf 27} 199-245.

\end









