\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/\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 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)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}