\documentclass[12pt]{article}  

\usepackage{e-jc}
\usepackage{amsthm,amsmath,amssymb}
\specs{P15}{19(2)}{2012}

%\sloppy

\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{con}[thm]{Conjecture}
\newtheorem{alg}[thm]{Algorithm}
\newtheorem{pro}[thm]{Property}
\newtheorem{problem}[thm]{Problem}
\newtheorem{lem}[thm]{Lemma}

\title{Sequences~containing~no~3-term~arithmetic~progressions}

\author{Janusz Dybizba\'nski\\
\small Institute of Informatics \\[-0.8ex]
\small University of Gda\'nsk, Poland\\
\small \texttt{jdybiz@inf.ug.edu.pl}
}

\date{\dateline{Feb 22, 2012}{Apr 12, 2012}{Apr 27, 2012}\\
\small Mathematics Subject Classifications: 11B25}

\begin{document}
\maketitle

\begin{abstract}
A subsequence of the sequence $(1,2,...,n)$ is called a
3-$AP$-free sequence if it does not contain any three term arithmetic progression.
By $r(n)$ we denote the length of the longest such 3-$AP$-free sequence. The exact
values of the function $r(n)$ were known, for $n\leq 27$ and $41\leq n \leq 43$.
In the present paper we determine, with a use of computer, the exact values,
for all $n\leq 123$.
The value $r(122)=32$ shows that the Szekeres' conjecture holds for $k=5$.
\end{abstract}

\section{Introduction}
Let $\langle n \rangle$ denote the sequence $(1,2,...,n)$. A subsequence
$(a_1, \dots,a_k)$ of $\langle n \rangle$ is called a 3-$AP$-free sequence if it
does not contain any three elements $a_p$, $a_q$, $a_r$ such that
$a_q-a_p=a_r-a_q$, or in other words if it does not contain any three term
arithmetic progression. By $r(n)$ we denote the length of the longest
3-$AP$-free sequences in $\langle n \rangle$.
Sometimes (see~\cite{beh}) the problem is equivalently presented in the set version.
A subset $S \subset \{1,2,...,n\}$ is called a 3-$AP$-free if  $a+c\ne 2b$, for every 
distinct terms $a,b,c\in S$. 
The cardinality of the largest such subset $S$ is equal to $r(n)$.


% Set version of this problem is defined similarly. A subset $A \subset %\{1,2,...,n\}$ is called a 3-$AP$-free if it does not contain a non trivial %3-term arithmetic progression. Cardinality of the largest such subset is equal %to $r(n)$.
% and such longest  $A$ sequences are called optimal.
The study of the function $r(n)$ was initiated by Erd\H{o}s and
Tur\'an~\cite{erd}. They determined the values $r(n)$, for $n\leq 23$ and $n=41$ (see Table~\ref{tbold}), proved that $r(2N)\leq N$, for $n\geq 8$, and conjectured that $\lim_{n\rightarrow \infty} r(n)/n = 0$. This conjecture was proved in 1975 by Szemeredi~\cite{sze}. Erd\H{o}s and Tur\'an also conjectured that $r(n)<n^{1-c}$, which was shown to be false by Salem and Spencer~\cite{sal} who proved $r(n)>n^{1-c/\log\log{n}}$. The later result was improved by Behrend~\cite{beh}, who showed that $r(n)>n^{1-c/\sqrt{\log{n}}}$. The first non trivial upper bound was due by Roth~\cite{rot} who proved $r(n)<\frac{cn}{\log\log{n}}$.

Recently Sharma~\cite{sha} showed that Erd\H{o}s and
Tur\'an gave the wrong value of $r(20)$ and determined the values of $r(n)$,
for $n\leq 27$ and $41\leq n \leq 43$ (see Tables~\ref{tbold} and~\ref{tb1}).
Erd\H{o}s and Tur\'an~\cite{erd} noted that there is no three term
arithmetic progression
in the sequence of all numbers $n$, $0\le n\le {\frac{1}{2}}(3^k-1)$, which
do not contain the digit 2 in the ternary scale. Hence, if we add 1 to
each of these numbers, we obtain the 3-$AP$-free sequence of length $2^k$ in
$\langle {\frac{1}{2}}(3^k+1) \rangle$. Thus, we have
\begin{lem}
\label{lem4}
$r({\frac{1}{2}}(3^k+1))\ge 2^k$, for every $k\ge 1$.
\end{lem}
The Szekeres' conjecture (see \cite{erd}) says that
$r(\frac{1}{2}(3^k+1))=2^k$.
The values given in \cite{erd,sha} (see Tables~\ref{tbold} and~\ref{tb1}) show that
the  conjecture  is true for $k\le 4$. The Szekeres' conjecture  has several
interesting implications described in~\cite{erd,sze}.
In the sequel we shall need the following lemmas from \cite{erd,sha}.

\begin{lem}
\label{lem5}
If $(a_1,...,a_k)$ is a 3-$AP$=free sequence in $\langle n \rangle$ and $j<a_1$,
then also $(a_1-j,...,a_k-j)$ is a 3-$AP$-free sequence in $\langle n \rangle$.
\end{lem}

\begin{lem}
\label{lem3}
$r(n+m)\leq r(n)+r(m)$.
\end{lem}

\begin{lem}
\label{lem1}
$r(n)\leq r(n+1) \leq r(n)+1$. 
\end{lem}
If $r(n-1)<r(n)$ then we call $n$ a jump node. Whenever $r(n-2)<r(n-1)<r(n)$ we call $n$ a double jump.
\begin{lem}
\label{lem2}
Three consecutive numbers cannot be jump nodes.
\end{lem}

In this paper we determine, using computer, exact values of $r(n)$, for all
$n\leq 123$. 
The value $r(122)=32$ shows that the Szekeres' conjecture holds
for $k=5$. 
We also determined, for each jump node $n\le 123$, $b(n)$ --- the number of the longest 
3-$AP$-free sequences in $\langle n \rangle$, and an example of the longest 3-$AP$-free sequence
(see Tables~\ref{tb1} and ~\ref{tb2}).

\section{Algorithm}
In order to determine values of the function $r(n)$ we have designed a
simple decision algorithm. This algorithm answers the question whether
there is a 3-$AP$-free sequence of length $k$ in $\langle n \rangle$. The algorithm uses the values $r(m)$, for $m<n$.

\begin{alg}
\label{alg1}
\bf INPUT \normalfont: $2\leq k \leq n\;$ --- natural numbers\\
\bf OUTPUT \normalfont: YES if there exists 3-$AP$-free sequence of length $k$ in $\langle n \rangle$; NO otherwise.
\end{alg}
\vspace{-1cm}
\texttt{\begin{tabbing}
1 : $a_1$:=1; $a_2$:=2; l:=2;\\
2 : APseq := ($a_1,a_2$)\\
3 : rep\=eat\\
4 :\>   if \=APseq contains no 3-term arithmetic progression then\\
5 :\>   \>      APseq := $(a_1,a_2,...,a_l,a_l+1)$\\
6 :\>   \>      l := l + $1$\\
7 :\>   else\\
8 :\>   \>      whi\=le (l>1) and (r(n-$a_l$) < k-l+$1$) \\
9 :\>   \>      \>      l := l - $1$;\\
10:\>   \>      APseq := $(a_1,a_2,...,a_{l-1},a_l+1)$\\
11: until ($a_1 \ne 1$) or  3-$AP$-free sequence of length k is found\\
12: if 3-$AP$-free sequence of length k is found, then return YES\\
13: if ($a_1 \ne 1$), then return NO\\
\end{tabbing}}

The algorithm looks for a 3-$AP$-free sequence of length $k$ in $\langle n \rangle$.
It starts (lines 1--2) with the  sequence (1,2) of length $l=2$.
At the beginning of each round of the ``repeat --- until'' loop (lines 3--11)
the algorithm considers the sequence APseq $=(a_1,\dots,a_{l-1},a_l)$ of length
$l\ge 2$. First, it checks if the sequence contains a 3-term arithmetic
progression. If not, then it adds the element $a_l+1$ at the end of the sequence
(lines 5--6). If APseq contains an arithmetic progression, then it looks for the
next sequence to consider (lines 8--10). The first candidate is the sequence
$(a_1,\dots,a_{l-1},a_l+1)$, but if   $r(n-a_l)<k-l+1$, it is not possible to
find remaining $k-l+1$ elements in the sequence $(a_l+1,\dots,n)$ without
arithmetic progression. In this case the algorithm sets $l:=l-1$ and checks if
the sequence $(a_1,\dots,a_{l-1}+1)$ will be good, and so on. The algorithm
exits the main loop if it finds a 3-$AP$-free sequence of the length $k$,
or if $a_1>1$. In the later case it returns the answer NO, because, by
Lemma~\ref{lem5}, it suffices to consider sequences which start with 1.


\section{Results}
\begin{table}[b!]
\begin{center}
\begin{tabular}{|r|r|r|l|}
\hline
$n$ & $r(n)$ & $b(n)$ & example of the longest 3-$AP$-free sequence\\
\hline
\hline
$1$ & $1$ & $1$ & 1\\
\hline
$2$ & $2$ & $1$ & 1 2\\
\hline
$4$ & $3$ & $2$ & 1 2 4 \\
\hline
$5$ & $4$ & $1$ & 1 2 4 5 \\
\hline
$9$ & $5$ & $4$ & 1 2 4 8 9 \\
\hline
$11$ & $6$ & $7$ & 1 2 4 5 10 11 \\
\hline
$13$ & $7$ & $6$ & 1 2 4 5 10 11 13 \\
\hline
$14$ & $8$ & $1$ & 1 2 4 5 10 11 13 14 \\
\hline
$20$ & $9$ & $2$ & 1 2 6 7 9 14 15 18 20 \\
\hline
$24$ & $10$ & $2$ & 1 2 5 7 11 16 18 19 23 24 \\
\hline
$26$ & $11$ & $2$ & 1 2 5 7 11 16 18 19 23 24 26\\
\hline
\end{tabular}
\caption{Values of $r(n)$, $b(n)$, and examples of the longest 3-$AP$-free sequences, for
jump nodes $n\leq 26$,
obtained in~\cite{erd,sha}. b(n) denotes the number of the longest 3-AP-free sequences in $\langle n \rangle$}
\label{tbold}
\end{center}
\end{table}

We have used Algorithm~\ref{alg1} to determine the values of the function
$r(n)$, for all $n\leq 120$. 
Observe that if we know the value $r(n)$, then we can obtain $r(n+1)$
after one application of the algorithm with the input $n+1$ and $k=r(n)+1$.
All computations took about 30h on personal computer.
We have got the value $r(120)=30$. By Lemma~\ref{lem4}, $r(122)\ge 32$, thus
by Lemma~\ref{lem1}, $r(121)=31$ and $r(122)=32$. Finally, by
Lemma~\ref{lem2}, $r(123)=32$.

Tables~\ref{tbold},~\ref{tb1} and~\ref{tb2} present:
 the value of $r(n)$, the value of $b(n)$ --- the number of the longest 3-$AP$-free sequences,
and an example of the longest 3-$AP$-free sequence in $\langle n \rangle$, for each jump node $n\le 123$.
Table~\ref{tbold} contains the  
results obtained by Erd\H{o}s and
Tur\'an~\cite{erd} and    
by Sharma~\cite{sha}.
The values for $n<20$ 
were given by Erd\H{o}s and
Tur\'an. They also gave the wrong value $r(20)=8$ and based on this value 
proved $r(41)=16$. Sharma gave the correct value of $r(20)=9$ and a new proof of $r(41)=16$.
Our calculations confirm the values given by Erdos and Turan, for $n<20$, and those given by 
Sharma, for $20\leq n\leq 27$ and $41\leq n\leq 43$ (including the correction of the value $r(20)=9$). Tables~\ref{tb1} and~\ref{tb2} contain the results for $n\geq 30$.
As we have mentioned above, the value r(41)=16 was given in [2,5], the others are new.\\

%Tables~\ref{tbold},~\ref{tb1} and~\ref{tb2} present:
% the value of $r(n)$, the value of $b(n)$ --- the number of the longest %3-$AP$-free sequences,
%and an example of the longest 3-$AP$-free sequence in $\langle n \rangle$, for %each jump node $n\le 123$.
% Table~\ref{tbold} contains the previous results obtained by Erd\H{o}s and
%Tur\'an~\cite{erd} and    
%by Sharma~\cite{sha}.
%The values for $n<20$ were given by Erd\H{o}s and Tur\'an. 
%The also gave the wrong value $r(20)=8$.
% Our calculations confirm the values given by Sharma,
%including $r(20)=9$~\cite{sha}. Tables ~\ref{tb1} and ~\ref{tb2} contain our %new results.

%Tables~\ref{tbold},~\ref{tb1} and~\ref{tb2} present the exact value of $r(n)$ %and an example of the longest 3-$AP$-free sequence in $\langle n \rangle$, for %every jump node $n\leq 123$. Values presented in Table~\ref{tbold} confirmed %previous results including Sharma correction of the value $r(20)$ claimed by %Erd\H{o}s and Tur\'an.

\begin{table}[htb]
\begin{center}
\begin{tabular}{|r|r|r|l|}
\hline
$n$ & $r(n)$ & $b(n)$ & example of the longest 3-$AP$-free sequence\\
\hline
\hline
$30$ & $12$ & $1$ & 1 3 4 8 9 11 20 22 23 27 28 30\\
\hline
$32$ & $13$ & $2$ & 1 2 4 8 9 11 19 22 23 26 28 31 32\\
\hline
$36$ & $14$ & $2$ & 1 2 4 8 9 13 21 23 26 27 30 32 35 36\\
\hline
$40$ & $15$ & $20$ & 1 2 4 5 10 11 13 14 28 29 31 32 37 38 40\\
\hline
$41$ & $16$ & $1$ & 1 2 4 5 10 11 13 14 28 29 31 32 37 38 40 41\\
\hline
$51$ & $17$ & $14$ & 1 2 4 5 10 13 14 17 31 35 37 38 40 46 47 50 51\\
\hline
$54$ & $18$ & $2$ & 1 2 5 6 12 14 15 17 21 31 38 39 42 43 49 51 52 54\\
\hline
$58$ & $19$ & $2$ & 1 2 5 6 12 14 15 17 21 31 38 39 42 43 49 51 52 54 58 \\
\hline
$63$ & $20$ & $2$ & 1 2 5 7 11 16 18 19 24 26 38 39 42 44 48 53 55 56 61 63 \\
\hline
$71$ & $21$ & $4$ & 1 2 5 7 10 17 20 22 26 31 41 46 48 49 53 54 63 64 68 69 71\\
\hline
$74$ & $22$ & $1$ & 1 2 7 9 10 14 20 22 23 25 29 46 50 52 53 55 61 65 66 68 73 74\\
\hline
$82$ & $23$ & $10$ & 1 2 4 8 9 11 19 22 23 26 28 31 49 57 59 62 63 66 68 71 78 81 82\\
\hline
\end{tabular}
\caption{Values of $r(n)$, $b(n)$, and examples of the longest 3-$AP$-free sequences, for
jump nodes $27 \leq n\leq 82$. The value r(41)=16 was given in~\cite{erd,sha}.}
\label{tb1}
\end{center}
\end{table}

\begin{table}[t]
\begin{center}
\begin{tabular}{|r|r|r|l|}
\hline
$n$ & $r(n)$ & $b(n)$ & example of the longest 3-$AP$-free sequence\\
\hline
\hline
$84$ & $24$ & $1$ & 1 3 4 8 9 16 18 21 22 25 30 37 48 55 60 63 64 67 69 76 \\
     &   &    & 77 81 82 84 \\

\hline
$92$ & $25$ & $14$ & 1 2 6 8 9 13 19 21 22 27 28 39 58 62 64 67 68 71 73 81\\
 &    & & 83 86 87 90 92\\
\hline
$95$ & $26$ & $8$ & 1 2 4 5 10 11 22 23 25 26 31 32 55 56 64 65 67 68 76 77 \\
 &    & & 82 83 91 92 94 95 \\
\hline
$100$ & $27$ & $2$ & 1 3 6 7 10 12 20 22 25 26 29 31 35 62 66 68 71 72 75 77\\
 &   & & 85 87 90 91 94 96 100 \\
\hline
$104$ & $28$ & $1$ & 1 5 7 10 11 14 16 24 26 29 30 33 35 39 66 70 72 75 76 79 \\
 &    & & 81 89 91 94 95 98 100 104 \\
\hline
$111$ & $29$ & $6$ & 1 2 5 6 13 15 19 26 27 30 31 38 42 44 66 68 72 77 80 81 \\
 &    & & 84 89 93 95 99 104 107 108 111 \\

\hline
$114$ & $30$ & $1$ & 1 2 4 9 12 13 18 19 28 30 31 33 40 45 46 69 70 75 82 84 \\
 &    & & 85 87 96 97 102 103 106 111 113 114 \\

\hline
$121$ & $31$ & $70$ & 1 2 4 5 10 11 13 14 28 29 31 32 37 38 40 41 82 83 85 86 \\
 &    & & 91 92 94 95 109 110 112 113 118 119 121 \\
\hline
$122$ & $32$ & $1$ & 1 2 4 5 10 11 13 14 28 29 31 32 37 38 40 41 82 83 85 86 \\
 &   &  & 91 92 94 95 109 110 112 113 118 119 121 122 \\
\hline
\end{tabular}
\caption{Values of $r(n)$, $b(n)$, and examples of the longest 3-$AP$-free sequences, for jump nodes $83 \leq n\leq 123$}
\label{tb2}
\end{center}
\end{table}

\section{Discussion and open problems}
Sharma~\cite{sha} asks if every $T_k={\frac{1}{2}}(3^k+1)$ is a jump node.
Our calculations and previous results show that, for $k\le 5$,
every $T_k$ is a double jump and there is only
one longest 3-$AP$-free sequence in $\langle T_k \rangle$, just the one described
before Lemma~\ref{lem4}. We wonder if this is true for other $k$?

Using the values from Table~\ref{tb1} and~\ref{tb2}
and a simple induction argument similar to the one described in \cite{erd}
we can prove that $r(3n) \leq n$, for every $n\ge 16$.
Indeed,  we know that $r(3n)\le n$, for every $16\le n\le 31$, and $r(48)=16$.
For $n\ge 32$, we have $r(3n)=r(3(n-16)+48)\le r(3(n-16))+r(48)\le n-16+16=n$.

\newpage

\begin{thebibliography}{10}

\bibitem{beh} Behrend F.A.
	\newblock On Sets of Integers Which Contain No Three Terms in Arithmetic Progression.
	\newblock {\em Proc. Nat. Acad. Sci. USA}, 32:331--332, 1946.

\bibitem{erd} Erd\H{o}s P., Tur\'an P.  
	\newblock On some sequences of integer.
	\newblock {\em J. London Math. Soc.}, 11:261--264, 1936.
\bibitem{rot} Roth K. F.
	\newblock On certain set of integers.
	\newblock {\em J. London Math. Soc.}, 28:104--109, 1953.

\bibitem{sal} Salem R., Spencer D. C.
	\newblock On Sets of Integers Which Contain No Three Terms in Arithmetic Progression.
	\newblock {\em Proc. Nat. Acad. Sci. USA}, 28:561--563, 1942.

\bibitem{sha} Sharma A. 
	\newblock Sequences of Integers Avoiding 3-term Arithmetic Progressions.
	\newblock {\em Elec. J. of Comb.}, 19:\#P27, 2012.
\bibitem{sze} Szemeredi E.  
	\newblock On sets of integers containing no $k$ elements in arithmetic progression.
	\newblock {\em Acta Arithmetica}, 27:199--245, 1975.

%\bibitem{erd2} Erd\H{o}s P., Tur\'an P., On some sequences of integer, \emph{J. %London Math. Soc.} \textbf{11} (1936) 261--264.
%\bibitem{sha2} Sharma A., Sequences of Integers Avoiding 3-term Arithmetic %Progressions, \emph{Elec. J. of Comb.} \textbf{19} (2012) \#P27.
%\bibitem{sze2} Szemeredi E., On sets of integers containing no $k$ elements in %arithmetic progression, Acta Arithmetica XXVII (1975) 199--245.
\end{thebibliography}



\end{document}


