\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P29}{20(4)}{2013}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{longtable}
\usepackage{amsthm}
\usepackage{hyperref}
%\usepackage{algorithm}
%\usepackage{algpseudocode}

\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{conj}{Conjecture}
\newtheorem{coro}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{exmp}{Example}
\newtheorem{ques}{Question}
\newtheorem{obs}{Observation}

\renewcommand{\geq}{\geqslant}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\parens}[1]{\left(#1\right)}
\newcommand{\arr}[1]{\left[#1\right]}
\renewcommand{\leq}{\leqslant}
\newcommand{\ang}[1]{\big\langle#1\big\rangle}
\newcommand{\smallfloor}[1]{\lfloor#1\rfloor}
\newcommand{\floor}[1]{\Big\lfloor#1\Big\rfloor}
\newcommand{\ceil}[1]{\Big\lceil#1\Big\rceil}


\newcommand{\ignore}[1]{\relax\ignorespaces}

\title{\bf Unique Sequences Containing No $\boldsymbol{k}$-Term Arithmetic Progressions}
\author{Tanbir Ahmed\\
\small Department of Computer Science and Software Engineering\\[-0.8ex]
\small Concordia University, Montr\'eal, Canada\\
\small \texttt{ta\_ahmed@cs.concordia.ca}\\
\and
Janusz Dybizba\'nski\\
\small Institute of Informatics\\[-0.8ex]
\small University of Gda\'nsk, Poland\\
\small \texttt{jdybiz@inf.ug.edu.pl}\\
\and
Hunter Snevily\footnote{Hunter Snevily has passed away on November 11, 2013 after his long struggle with Parkinson's disease. 
We have lost a good friend and colleague. He will be greatly missed and remembered.
}\\
\small Department of Mathematics\\[-0.8ex]
\small University of Idaho - Moscow, Idaho, USA\\
\small \texttt{snevily@uidaho.edu}\\
}

\date{\dateline{Dec 22, 2012}{Dec 5, 2013}{Dec 17, 2013}\\
\small Mathematics Subject Classifications: 11B25}

\begin{document}
\maketitle

\raggedbottom

\begin{abstract}
In this paper, we are concerned with calculating $r(k,n)$, the length of the longest $k$-Ap free subsequences in $1,2,\ldots,n$. We prove the basic inequality $r(k,n) \leq n- \smallfloor{m/2}$, 
where $n=m(k-1) + r$ and $r<k-1$. 
We also discuss a generalization of a famous conjecture of Szekeres (as appears in Erd{\H o}s and Tur\'an \cite{erdos-turan})  and describe a simple greedy algorithm that appears to give an optimal $k$-AP free sequence 
infinitely often. We provide many exact values of $r(k,n)$ in the Appendix.
\end{abstract}

\section{Introduction}
Let $\ang{n}$ denote the sequence $1,2,\ldots,n$.
A subsequence of $\ang{n}$ is called \emph{$k$-AP free}
if it does not contain any $k$-term arithmetic progression.
Define the following:
\begin{eqnarray*}
r(k,n) & = & \text{length of the longest $k$-AP free subsequences in $\ang{n}$},\\
S(k,n) & = & \set{S \subseteq\set{1,2,\ldots,n}: \text{$S$ is $k$-AP free and $|S|=r(k,n)$}},\\
b(k, n) & = & |S(k,n)|.\\
\end{eqnarray*}
The study of the function $r(3,n)$ was initiated by Erd\H{o}s and Tur\'an \cite{erdos-turan}.
They determined the values of $r(3,n)$ for $n\leq 23$ and $n=41$, proved for $n\geq 8$
that $$r(3,2n)\leq n$$ 
and conjectured that $$\lim_{n\rightarrow\infty}r(3,n)/n=0,$$ which
was proved in 1975 by Szemeredi \cite{szemeredi}. Erd\H{o}s and Tur\'an also conjectured that
$r(3,n)<n^{1-c}$, which was shown to be false by Salem and Spencer \cite{salem-spencer}, who proved
$$r(3,n)>n^{1-c/\log\log{n}},$$ which was further improved by Behrend \cite{behrend} to
$$r(3,n)>n^{1-c/\sqrt{\log{n}}}.$$
Recently, Elkin \cite{elkin} has further improved this lower bound 
by a factor of $\Theta(\sqrt{\log{n}})$.
The first non-trivial upper bound was due to Roth \cite{roth} who proved
$$r(3,n)<cn/\log\log{n}.$$

Sharma \cite{sharma} showed that Erd\H{o}s and Tur\'an gave the wrong value of $r(3,20)$
and determined the values of $r(3,n)$ for $n\leq 27$ and $41\leq n\leq 43$. Recently, 
Dybizba\'nski \cite{dybizbanski} has computed the exact values of $r(3,n)$ for all $n\leq 123$
and proved for $n\geq 16$ that $$r(3, 3n)\leq n.$$ 

\subsection{Szekeres' conjecture}
Erd\H{o}s and Tur\'an \cite{erdos-turan} noted that there is no 3-term arithmetic progression in the sequence 
of all numbers $n, 0\leq n\leq {1\over 2}(3^t-1)$, which do not contain the digit 2 in the ternary scale. 
Hence for every $t\geq 1$, $$r\left(3, (3^t+1)/2\right)\geq 2^t$$
as we obtain the 3-AP-free sequence of length $2^t$ in $\ang{(3^t+1)/2}$ by adding
1 to each of those numbers that does not contain digit 2 in the ternary scale.
Szekeres conjectured that for every $t\geq 1$, $$r\left(3, (3^t+1)/2\right)=2^t,$$
and more generally, for any $t$ and any prime $p$,
$$r\left(p, {(p-2)p^t+1 \over p-1}\right)=(p-1)^t.$$

A generalization of Szekeres' conjecture will be given in Section \ref{sec-uniqueness}.

\section{A basic inequality for $r(k,n)$}
Let $ap(k,n)$ denote the set of all $k$-APs from the numbers $1,2,\ldots,n$. 
Let $ap(k,n;v)$ denote the set of all $k$-APs, each containing $v$, from the numbers $1,2,\ldots,n$. 
Let $c(k,n)$ and $c(k,n;v)$ denote $|ap(k,n)|$ and $|ap(k,n;v)|$, respectively.
Let $c_i(k,n;v)$ be the number of $k$-APs, each containing $v$ as the $i$-th element in the AP,
from the numbers $1,2,\ldots,n$. 
Also define $c_{max}(k,n)$ as the maximum of $c(k,n;x)$ over $x=1,2,\ldots,n$.

\ignore{
Define the following:
\begin{eqnarray*}
ap(k,n) & = & \set{S\subseteq\set{1,2,\ldots,n}: \text{$S$ is a $k$-AP}},\\
        %= \text{Set of $k$-APs in $1,2,\ldots,n$};\\
c(k,n) & = & |ap(k,n)|,\\
      %= \text{Number of $k$-APs in $1,2,\ldots,n$};\\
ap(k,n;v) & = & \set{S\in ap(k,n): v\in S},\\
          %&=& \text{Set of $k$-APs in $1,2,\ldots,n$, each containing integer $v$};\\ 
c(k,n;v)  & = & |ap(k,n;v)|,\\
          %&=& \text{Number of $k$-APs in $1,2,\ldots,n$, each containing integer $v$};\\ 
c_i(k,n;v) & = & |\set{S\in ap(k,n;v): \text{$v$ is the $i$-th element in $S$}}|,\\
           %&=& \text{Number of $k$-APs in $1,2,\ldots,n$, each containing $v$ as the $i$-th element};\\ 
c_{max}(k,n) & = & \max\set{c(k,n;x): 1\leq x\leq n}. 
\end{eqnarray*}
%The average  cost of an element $e$ in a sequence $S\in S(k,n)$ 
%is therefore $cost(k,n,S)/r(k,n)$. 
}

In this section, we determine an exact expression for $c(k,n)$ and an upper-bound for $c_{max}(k,n)$ 
to obtain a basic inequality for $r(k,n)$.
The following observation is crucial for the proofs in this paper:

\begin{obs}\label{obs-1}
$$
c_j(k,n;x) = \left\{
\begin{array}{ll}
\smallfloor{(n-x)/(k-1)}, & \text{if $j=1$};\\
\smallfloor{(x-1)/(k-1)}, & \text{if $j=k$};\\
\min\set{\floor{{(n-x)\over(k-j)}}, \floor{{(x-1)\over(j-1)}}}, & \text{otherwise.}
\end{array}
\right.
$$
and $c(k,n;x)=\sum_{j=1}^kc_j(k,n;x)$.
\end{obs}

\begin{exmp}
Consider $k=4$ and $n=17$. 
Here, $r(4,17)=11$ with an example $S = \set{1,2,4,5,6,10,12,13,15,16,17}\in S(4,17)$.

\footnotesize
\begin{center}
\begin{tabular}{l|rrrrrrrrrrrrrrrrrr|}
$j/x$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17\\
\hline 
1 & 5 & 5 & 4 & 4 & 4 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 1 & 1 & 0 & 0 & 0\\
2 & 0 & 1 & 2 & 3 & 4 & 5 & 5 & 4 & 4 & 3 & 3 & 2 & 2 & 1 & 1 & 0 & 0\\
3 & 0 & 0 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 4 & 3 & 2 & 1 & 0\\
4 & 0 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 2 & 3 & 3 & 3 & 4 & 4 & 4 & 5 & 5\\
\hline
$c(4,17;x)$ & 5 & 6 & 7 & 9 & 11 & 11 & 13 & 12 & 12 & 12 & 13 & 11 & 11 & 9 & 7 & 6 & 5
\end{tabular}
\end{center}
\normalsize

Here $c(4,17; x)= c_1(4,17;x)+c_2(4,17;x)+c_3(4,17;x)+c_4(4,17;x)$. 
For example, $c(4,17;13)=1+2+4+4$ due to the following 4-APs
in $ap(4,17)$ that contain $13$, namely $ap(4,17;13)$: 

\begin{center}
$\begin{array}{llll}
\set{13,14,15,16}, & \set{12,13,14,15}, & \set{11,13,15,17}, & \set{5,9,13,17}, \\
\set{7,10,13,16}, & \set{9,11,13,15}, & \set{11,12,13,14}, & \set{1,5,9,13}, \\
\set{4,7,10,13}, & \set{7,9,11,13}, & \set{10,11,12,13}. & 
\end{array}$
\end{center}
\end{exmp}




\begin{obs}\label{obs-2}
For $x=1,2,\ldots,\smallfloor{n/2}$, $c(k,n;x)=c(k,n;n-x+1)$, that is,
the sequence $c(k,n;x)$ with $x=1,2,\ldots,n$ is symmetric. 
\begin{proof}
We have the following cases:
\begin{itemize}
\item [$(a)$] For $j=1$, using Observation \ref{obs-1}, we have 
$$c_1(k,n;x) = \floor{{n-x\over k-1}} = \floor{{(n-x+1)-1\over k-1}} = c_k(k,n;n-x+1).$$
\item [$(b)$] For other values of $j$,
\begin{itemize}
  \item [$(i)$] If $\smallfloor{(n-x)/(k-j)}\leq \smallfloor{(x-1)/(j-1)}$, then taking $x'=n-x+1$ and $j'=k-j+1$, and using Observation \ref{obs-1},
$$c_j(k,n;x) = \floor{{(n-x)\over(k-j)}} = \floor{{(n-x+1)-1\over (k-j+1)-1}}= \floor{{(x'-1) \over (j'-1)}} = c_{j'}(k,n;x').$$

The last equality follows from the fact that
$$\floor{{(x'-1) \over (j'-1)}} \leq \floor{{(x-1)\over(j-1)}}=\floor{{(n-x')\over(k-j')}}.$$

\item [$(ii)$] If $\smallfloor{(n-x)/(k-j)} > \smallfloor{(x-1)/(j-1)}$, then (similar as $(i)$) 
$$c_j(k,n;x) = c_{k-j+1}(k,n;n-x+1).$$
\end{itemize}
\end{itemize}

%From Observation \ref{obs-1}, $c_1(n,k;x) = c_k(n,k;n-x+1)$.
\ignore{
For other values of $j$,
if $\smallfloor{(n-x)/(k-j)}\leq \smallfloor{(x-1)/(j-1)}$, then taking $x'=n-x+1$ and $j'=k-j+1$,
$$c_j(k,n;x) = \floor{{(n-x)\over(k-j)}} = \floor{{(n-x+1)-1\over (k-j+1)-1}}= \floor{{(x'-1) \over (j'-1)}} = c_{j'}(k,n;x').$$

The last equality follows from the fact that
$$\floor{{(x'-1) \over (j'-1)}} \leq \floor{{(x-1)\over(j-1)}}=\floor{{(n-x')\over(k-j')}}.$$

Similarly, if $\smallfloor{(n-x)/(k-j)} > \smallfloor{(x-1)/(j-1)}$, then
$$c_j(k,n;x) = c_{k-j+1}(k,n;n-x+1).$$
}
Therefore, $c(k,n;x)$ with $x=1,2,\ldots,n$ is symmetric.
\end{proof}
\end{obs}

\begin{lemma}\label{lemma-1}
Given positive integers $k$ and $n$, let $2\leq j\leq k-1$, $n=m(k-1)+r$ with $0\leq r\leq k-2$.
Then $c_j(k,n;x)$ equals
\begin{itemize}
\item [$(a)$] $\smallfloor{(x-1)/(j-1)}$ if $x=1,2,\ldots,m(j-1)$,
\item [$(b)$] $\smallfloor{(n-x)/(k-j)}$ if $x=n-m(k-j)+1,n-m(k-j)+2,\ldots,n$,
\item [$(c)$] $m$ otherwise, that is, for $x=m(j-1)+1,\ldots,n-m(k-j)$. 
\end{itemize}
\begin{proof}
\begin{itemize}
\item [$(a)$] Take $y\leq m(j-1)$ and assume $$c_j(k,n;y)=\smallfloor{(n-y)/(k-j)},$$ that is,
$\smallfloor{(n-y)/(k-j)}<\smallfloor{(y-1)/(j-1)}$.

Since $y\leq m(j-1)$, we have $(y-1)\leq m(j-1)-1$, and hence $$\floor{{y-1\over j-1}} \leq m-1.$$
%Now we have, $\smallfloor{(y-1)/(j-1)} \leq m-1$, and

Again, since $y\leq m(j-1)$, we have 
%\begin{eqnarray*}
%y \leq m(j-1)
% & &
$$n-y \geq n-m(j-1) = m(k-j)+r,$$
% &\Rightarrow & \floor{{n-y\over k-j}} \geq m. 
%\end{eqnarray*}
which implies
$$\floor{{n-y\over k-j}} \geq m.$$

Now, we have the following contradiction
$$m \leq \floor{{n-y\over k-j}} < \floor{{y-1\over j-1}} \leq m-1.$$

\item [$(b)$] Take $y\geq n-m(k-j)+1$ and assume $$c_j(k,n;y)=\smallfloor{(y-1)/(j-1)},$$ that is,
$\smallfloor{(n-y)/(k-j)}>\smallfloor{(y-1)/(j-1)}$.
Similar reasoning as (a) leads to a contradiction.
\item [$(c)$] Here, $n-m(k-j)$ can be written as $m(j-1)+r$ and $m(j-1)+1$ can be written as $n-m(k-j)-(r-1)$.
There are exactly $r$ elements in $m(j-1)+1,\ldots,n-m(k-j)$, and for any $x$ in this range,
$$c_j(k,n;x) = \smallfloor{(x-1)/(j-1)} = \smallfloor{(n-x)/(k-j)} = m.$$
\end{itemize}
\end{proof}
\end{lemma}

\begin{lemma}\label{lemma-2}
Given positive integers $k$ and $n$, let $n=m(k-1)+r$ with $0\leq r\leq k-2$.
Denote a sequence $a,a,\ldots,a$ with $a$ repeated $b$ times as $a^b$, and consider $a^0$ to be an empty sequence.  
Then for $1\leq j\leq k$, the sequence $c_j(k,n;x)$ with $1\leq x\leq n$ has the form
$$0^{j-1}1^{j-1}\cdots(m-1)^{j-1}m^r(m-1)^{k-j}(m-2)^{k-j}\cdots 0^{k-j}.$$
\begin{proof}
Using Observation \ref{obs-1}, 
we have for $j=1$: 
$$c_1(k,n;x) = \floor{{n-x \over k-1}} = \floor{m+{r-x\over k-1}} = m+\floor{{r-x\over k-1}},$$ 
and more specifically,
\begin{eqnarray*}
c_1(k,n;x) &=& 
\left\{
\begin{array}{ll}
m, & \text{for $x=1,2,\ldots,r$};\\
(m-1), & \text{for $x=r+1,r+2,\ldots,r+(k-1)$};\\
(m-2), & \text{for $x=r+(k-1)+1,r+(k-1)+2,\ldots,r+2(k-1)$};\\
 & \vdots, \\
1, & \text{for $x=r+(m-2)(k-1)+1,\ldots,n-(k-1)$};\\
0, & \text{for $x=r+(m-1)(k-1)+1,\ldots,n$}.
\end{array}
\right.
\end{eqnarray*}
Hence, the sequence $c_1(k,n;x)$ with $x=1,2,\ldots,n$ is
$$m^r(m-1)^{k-1}(m-2)^{k-1}\cdots{1}^{k-1}{0}^{k-1}.$$

Similarly, for $j=k$, we have
$$c_k(k,n;x) = \floor{{x-1\over k-1}},$$
and more specifically,
\begin{eqnarray*}
c_k(k,n;x) &=& 
\left\{
\begin{array}{ll}
0, & \text{for $x=1,2,\ldots,k-1$};\\
1, & \text{for $x=(k-1)+1,(k-1)+2,\ldots,2(k-1)$};\\
2, & \text{for $x=2(k-1)+1,2(k-1)+2,\ldots,3(k-1)$};\\
 & \vdots, \\
(m-2), & \text{for $x=(m-2)(k-1)+1,\ldots,(m-1)(k-1)$};\\
(m-1), & \text{for $x=(m-1)(k-1)+1,\ldots,m(k-1)$};\\
m, & \text{for $x=m(k-1)+1,\ldots,n$}.
\end{array}
\right.
\end{eqnarray*}
and hence the sequence $c_k(k,n;x)$ with $x=1,2,\ldots,n$ is
$$0^{k-1}1^{k-1}\cdots(m-2)^{k-1}(m-1)^{k-1}m^r.$$ 

For $2\leq j\leq k-1$, by Lemma \ref{lemma-1}, we have

\footnotesize
\begin{longtable}{c|c}%\caption{Row-structure for $c(k,n)$}\\
\hline
$x$ & $c_j(k,n;x)$\\
\hline
$1,2,\ldots,j-1$ & $\smallfloor{(x-1)/(j-1)}=0$\\
$(j-1)+1,(j-1)+2,\ldots,2(j-1)$ & $\smallfloor{(x-1)/(j-1)}=1$\\
%$2(j-1)+1,2(j-1)+2,\ldots,3(j-1)$ & $\smallfloor{(x-1)/(j-1)}=2$\\
$\vdots$ & $\vdots$ \\
$(m-2)(j-1)+1,(m-2)(j-1)+2,\ldots,(m-1)(j-1)$ & $\smallfloor{(x-1)/(j-1)}=m-2$\\
$(m-1)(j-1)+1,(m-1)(j-1)+2,\ldots,m(j-1)$ & $\smallfloor{(x-1)/(j-1)}=m-1$\\
\hline
$m(j-1)+1,m(j-1)+2,\ldots,n-m(k-j)$ & $m$\\
\hline
$n-m(k-j)+1,\ldots,n-(m-1)(k-j)$ & $\smallfloor{(n-x)/(k-j)}=m-1$\\
$n-(m-1)(k-j)+1,\ldots,n-(m-2)(k-j)$ & $\smallfloor{(n-x)/(k-j)}=m-2$\\
$\vdots$ & $\vdots$ \\
$n-2(k-j)+1,n-2(k-j)+2,\ldots,n-(k-j)$ & $\smallfloor{(n-x)/(k-j)}=1$\\
$n-(k-j)+1,n-(k-j)+2,\ldots,n$ & $\smallfloor{(n-x)/(k-j)}=0$\\
\hline
\end{longtable}
\normalsize

Hence, we get the sequence $c_j(k,n;x)$ for $x=1,2,\ldots,n$ as
$$0^{j-1}1^{j-1}\cdots(m-1)^{j-1}m^r(m-1)^{k-j}(m-2)^{k-j}\cdots 0^{k-j}.$$
\end{proof}
\end{lemma}

\begin{coro}\label{coro-1a}
Given positive integers $k$ and $n$, let $m=\smallfloor{n/(k-1)}$ and $n=m(k-1)+r$. Then
$$c(k,n) = {m\choose 2}(k-1)+mr.$$
\begin{proof}
From the definition  of $c_1(k,n;x)$ in Lemma \ref{lemma-2}, for $1\leq x\leq n$, we have,
\begin{eqnarray*}
c(k,n) & = & \sum_{x=1}^{n-k+1}c_1(k,n;x)\\
       &=& \sum_{x=1}^rc_1(k,n;x)+  
        \left[\sum_{x=r+1}^{r+(k-1)}c_1(k,n;x)+\right. \\
       && \left.\sum_{x=r+(k-1)+1}^{r+2(k-1)}c_1(k,n;x)+\cdots+
        \sum_{x=r+(m-2)(k-1)+1}^{n-k+1=n-(k-1)=r+(m-1)(k-1)}c_1(k,n;x)\right]\\
       & = & mr + [(m-1)+(m-2)+\cdots+2+1](k-1)\\
       & = & {m\choose 2}(k-1)+mr. 
\end{eqnarray*}
\end{proof}
\end{coro}

\begin{coro}\label{coro-2a}
Given positive integers $k$ and $n$, let $n=m(k-1)+r$ with $r<k-1$ and $1\leq j\leq k$. Then
for $x=1,2,\ldots,n$, $$c_j(k,n;x)\leq m.$$
\begin{proof}
Follows from Lemmas \ref{lemma-1} and \ref{lemma-2}.
\end{proof}
\end{coro}

Trivially, $c_{max}(k,n)\leq mk$. The following Corollary slightly improves the bound.

\begin{coro}\label{coro-3a}
Given positive integers $k$ and $n$, let $n=m(k-1)+r$ with $r<k-1$ and $1\leq j\leq k$. Then
$$c_{max}(k,n) \leq m(k-1)$$

\begin{proof}
For any $x \in\set{1,2,\ldots,n}$, 
using the definitions of $c_1(k,n;x)$ and $c_k(k,n;x)$ from Lemma \ref{lemma-2},
we have, 
%the following values of $c_1(k,n;x)+c_k(k,n;x)$ using Lemma \ref{lemma-2}.

\footnotesize
\begin{longtable}{c|c}
\hline
$x$ & $c_1(k,n;x)+c_k(k,n;x)$\\
\hline
$1,2,\ldots,r$ & $m+0=m$ \\
$r+0(k-1)+1,r+0(k-1)+2,\ldots,k-1$ & $(m-1)+0=m-1$\\
$1+(k-1),2+(k-1),\ldots,r+1(k-1)$ & $(m-1)+1=m$\\
$r+1(k-1)+1,r+1(k-1)+2,\ldots,2(k-1)$ & $(m-2)+1=m-1$\\
$1+2(k-1),2+2(k-1),\ldots,r+2(k-1)$ & $(m-2)+2=m$\\
$\vdots$ & $\vdots$\\
$r+(m-2)(k-1)+1, r+(m-2)(k-1)+2,\ldots,(m-1)(k-1)$ & $1+(m-2)=m-1$\\
$1+(m-1)(k-1),2+(m-1)(k-1),\ldots,r+(m-1)(k-1)$ & $1+(m-1)=m$\\
$r+(m-1)(k-1)+1, r+(m-1)(k-1)+2,\ldots,m(k-1)$ & $0+(m-1)=m-1$\\
$1+m(k-1),2+m(k-1),\ldots,r+m(k-1)$, & $0+m=m$\\
\hline
\end{longtable}
\normalsize

Hence, using $c_1(k,n;x)+c_k(k,n;x)\leq m$ and $c_j(k,n;x)\leq m$ (by Corollary \ref{coro-2a}) for $1\leq j\leq k$, we have
\begin{eqnarray*}
c(k,n;x) &=& c_1(k,n;x)+c_k(k,n;x)+\sum_{j=2}^{k-1}c_j(k,n;x) \\
         &\leq& m+m(k-2) = m(k-1).
\end{eqnarray*}
Therefore, $c_{max}(k,n) \leq m(k-1)$. 
\end{proof}

\end{coro}

It can be observed that the upper bound in Corollary \ref{coro-3a} is the best possible for $c_{max}(k,n)$.
The following theorem gives an upper bound of $r(k,n)$,
which is very close to actual values (see Appendix \ref{app-3} for experimental results). 

%Let $c_{max}(k,n)$ denote $\max\set{c(k,n;x): 1\leq x\leq n}$, 
%which by Corollary \ref{coro-3a}
%$$c_{max}(k,n)\leq m(k-1).$$

\begin{theorem}
\label{thm1}
Given positive integers $k$ and $n$, let $m=\smallfloor{n/(k-1)}$ and $n=m(k-1)+r$ where $r<k-1$.
Then $$r(k,n) \leq n - \smallfloor{m/2}.$$

\begin{proof}
Using Corollaries \ref{coro-2a} and \ref{coro-3a}, we have
\begin{eqnarray*}
r(k,n) & \leq & n - \ceil{{c(k,n) \over c_{max}(k,n)}} \\
       & \leq & n - \ceil{{m(m-1)(k-1)/2+mr \over m(k-1)}} \\   
       & = & n - \ceil{{m-1\over 2}+{r\over k-1}} = n - f(m,k,r), \text{(say)}
\end{eqnarray*}

It can be observed that
\begin{eqnarray*}
f(m,k,r) &=& \left\{
\begin{array}{ll}
y+1, & \text{if $m=2y+1$};\\
y, & \text{if $m=2y$ and $2r\leq k-1$}; \\
y+1, & \text{if $m=2y$ and $2r > k-1$}.
\end{array}
\right.
\end{eqnarray*}

Hence, $$r(k,n) \leq n - \smallfloor{m/2}.$$
\end{proof}
\end{theorem}

\begin{conj}\label{conj-periodic}
For every positive integer $k\geq 3$ and positive integer $n$, 
%the maximum value of $c(k,n;x)$ over $x=1,2,\ldots,n$ 
$c_{max}(k,n)$ is eventually periodic.
\end{conj}

For example, for $k=5$, the length of the period is $24$ and 
the periodic increase in the value of $c_{max}(k,n)$ is $20$, as
indicated in the following table:

%\newpage

\footnotesize
\begin{longtable}{c|c||c|c||c|c||c|c||c|c||c} 
\hline
$n$ & $c_{max}(5,n)$ & $n$ & $c_{max}(5,n)$ & $n$ & $c_{max}(5,n)$ & $n$ & $c_{max}(5,n)$ & $n$ & $c_{max}(5,n)$ \\
\hline
25 & 20 & 49 & 40 & 73 & 60 & 97 & 80 & 121 & 100 & $\cdots$ \\
26 & 20 & 50 & 40 & 74 & 60 & 98 & 80 & 122 & 100 & $\cdots$ \\
27 & 20 & 51 & 40 & 75 & 60 & 99 & 80 & 123 & 100 & $\cdots$ \\
28 & 21 & 52 & 41 & 76 & 61 & 100 & 81 & 124 & 101 & $\cdots$ \\
29 & 22 & 53 & 42 & 77 & 62 & 101 & 82 & 125 & 102 & $\cdots$ \\
30 & 22 & 54 & 42 & 78 & 62 & 102 & 82 & 126 & 102 & $\cdots$ \\
$\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ &$\vdots$   & $\vdots$ & $\vdots$ & $\vdots$  \\
47 & 37 & 71 & 57 & 95 & 77 & 119 & 97 & 143 & 117 & $\cdots$ \\
48 & 37 & 72 & 57 & 96 & 77 & 120 & 97 & 144 & 117 & $\cdots$ \\
\hline
\end{longtable}
\normalsize

%\begin{lemma}
%For $i\geq 2$ and $1\leq j\leq 24$, $$c_{max}(5,24i+j) = c_{max}(5, (i-1)24+j)+20.$$
%\end{lemma}

\begin{conj}\label{conj-column-sum}
Given an odd positive integer $k$, the size of the largest subset $U$ of 
$\set{1,2,\ldots,n}$ for any positive integer $n$, 
with each $x\in U$ having the same $c(k,n;x)$,
is bounded from above by a constant $f(k)\leq k^2$. 
\end{conj}

The implications of Conjecture \ref{conj-column-sum} being true is as follows:

Let $w = c_{max}(k,n)$ and consider the largest $\ell$ such that
$$g(k,\ell,w)=f(k)\parens{w+(w-1)+\cdots+\parens{w-(\ell-1)}}$$
has the property $c(k,n)-g(k,\ell,w)\geq f(k)\ell(\ell-1)/2$.
Then

\begin{eqnarray*}
r(k,n) &\leq & n - \ceil{{c(k,n)\over w}} \leq n - \ceil{{g(k,\ell,w)+f(k)\ell(\ell-1)/2\over w}} \\ 
       &=& n - f(k)\ell.
\end{eqnarray*}

See Appendix \ref{app-1} for data supporting Conjectures \ref{conj-periodic} and \ref{conj-column-sum}.

\section{Unimodality lemmas}
A sequence is called \emph{unimodal}
if it is first increasing and then decreasing.
In this section, we prove some lemmas on sequences regarding $c(k,n;x)$ for $k\geq 3$.

\begin{lemma}
Given positive integers $k$ and $n$,  
for any $j\in\set{2,3,\ldots,k-1}$, 
the sequence $c_j(k,n;x)$ with $x=1,2,\ldots,n$
is unimodal.
\begin{proof}
Follows directly from Lemma \ref{lemma-2}.
\end{proof} 
\end{lemma}

\begin{lemma}
The sequence $c(3,n;i)$ with $i=1,2,\ldots,n$ is unimodal.
\begin{proof}
From Observation \ref{obs-1}, 
$$
c_j(3,n; x) = \left\{
\begin{array}{ll}
\smallfloor{(n-x)/2}, & \text{if $j=1$};\\
x-1, & \text{if $j=2$ and $x\leq\smallfloor{n/2}$};\\
n-x, & \text{if $j=2$ and $x>\smallfloor{n/2}$};\\
\smallfloor{(x-1)/2}, & \text{if $j=3$}.\\
\end{array}
\right.
$$

By Observation \ref{obs-2}, $c(3,n;i)$ equals $c(3,n;n-i+1)$ for $i=1,2,\ldots,\smallfloor{n/2}$.

Now, we consider the following two cases:
\begin{enumerate}
\item ($n=2m$). For $i=1,2,\ldots,m-1$, we have
$$c_2(3,n; i+1) = c_2(3,n;i)+1,$$
and also for $i=1,2,\ldots,m$,
\begin{eqnarray*}
c_1(3,n;i) + c_3(3,n;i) & = & \floor{{2m-i \over 2}} +\floor{{i-1\over 2}}
                        = \floor{m-{i\over 2}}+\floor{{i\over 2}-{1\over 2}}. 
\end{eqnarray*}
If $i=2j$ ($j\geq 1$), then 
\begin{eqnarray*}
c_1(3,n;i) + c_3(3,n;i) & = & (m-j)+\floor{j-{1\over 2}} = (m-j) + (j-1) = m-1. 
\end{eqnarray*}
If $i=2j+1$ ($j\geq 0$), then 
\begin{eqnarray*}
c_1(3,n;i) + c_3(3,n;i) & = & \floor{m-j-{1\over 2}}+\floor{{(2j+1)-1\over 2}} \\
                        & = & (m-j-1) + j = m-1. 
\end{eqnarray*}
Therefore, for $i=1,2,\ldots,m-1$, 
$$c(3,n;i+1)= (m-1)+c_2(3,n;i)+1 = c(3,n;i)+1.$$

\item ($n=2m+1$). For $i=1,2,\ldots,m$, we have
$$c_2(3,n; i+1) = c_2(3,n;i)+1,$$
and also 
\begin{eqnarray*}
c_1(3,n;i) + c_3(3,n;i) & = & \floor{{2m+1-i \over 2}} +\floor{{i-1\over 2}}
                        = \floor{m+{1\over 2}-{i\over 2}}+\floor{{i\over 2}-{1\over 2}}. 
\end{eqnarray*}
If $i=2j$ ($j\geq 1$), then 
\begin{eqnarray*}
c_1(3,n;i) + c_3(3,n;i) & = & \floor{m+{1\over 2}-j}+\floor{j-{1\over 2}} = (m-j) + (j-1) = m-1. 
\end{eqnarray*}
If $i=2j+1$ ($j\geq 0$), then 
\begin{eqnarray*}
c_1(3,n;i) + c_3(3,n;i) & = & \floor{m+{1\over 2}-j-{1\over 2}}+\floor{{(2j+1)-1\over 2}} \\
                        & = & (m-j) + j = m. 
\end{eqnarray*}
Therefore, for $i=1,2,\ldots,m$, 
\begin{itemize}
\item If $i$ is odd, then
\begin{eqnarray*}
c(3,n;i+1) & = & c_1(3,n;i+1)+c_2(3,n;i+1)+c_3(3,n;i+1) \\
           & = & c_2(3,n;i)+1 +(m-1) = c_2(3,n;i)+m \\
           & = & c_2(3,n;i)+c_1(3,n;i)+c_3(3,n;i) = c(3,n;i).
\end{eqnarray*}
\item If $i$ is even, then
\begin{eqnarray*}
c(3,n;i+1) & = & c_1(3,n;i+1)+c_2(3,n;i+1)+c_3(3,n;i+1)\\
           & = & c_2(3,n;i)+1 +m = c_2(3,n;i)+(m-1)+2 \\
           & = & c_2(3,n;i)+c_1(3,n;i)+c_3(3,n;i)+2 = c(3,n;i)+2.
\end{eqnarray*}
\end{itemize}
\end{enumerate}
Hence, $c(3,n;i)$ with $i=1,2,\ldots,n$ is unimodal.
\end{proof}
\end{lemma}

\begin{lemma}
For $k\geq 4$, there are infinitely many $n$ such that the sequence $c(k,n;i)$
with $i=1,2,\ldots,n$ is unimodal. 
\begin{proof}
We show that 
$c(k, n; i)$ for $1\leq i\leq n$ with $n=lcm\set{1,2,\ldots,k-1}\cdot{m}$ (where $m\geq 1$) is unimodal. 
Since $n$ is even, $n/2$ is an integer.
By Observation \ref{obs-2}, the sequence $c(k, n; i)$ with $1\leq i\leq n$ is symmetric.
So assume $i\leq n/2$.
Let $lcm\set{1,2,\ldots,k-1}$ be equal to $h_r\cdot r$ with $2\leq r\leq k-1$, and
$i\equiv s\pmod{k-1}$ with $t=\smallfloor{i/(k-1)}$.  
Now,
\begin{eqnarray*}
c_1(k,n;i) & = & \floor{{(n-i)\over(k-1)}} = \floor{mh_{k-1}-{i \over (k-1)}} = \floor{mh_{k-1}-t-{s\over k-1}}\\
c_1(k,n;i+1) & = &  \floor{{(n-i-1)\over(k-1)}} = \floor{mh_{k-1}-{i+1 \over (k-1)}} = \floor{mh_{k-1}-t-{s+1\over k-1}}
\end{eqnarray*}

Therefore, 
$$
c_1(k,n;i+1) = \left\{
\begin{array}{ll}
c_1(k,n;i)-1, & \text{if $s=0$;}\\
c_1(k,n;i), & \text{otherwise}.
\end{array}
\right.
$$ 
Similarly,
$$
c_k(k,n;i+1) = \left\{
\begin{array}{ll}
c_k(k,n;i)+1, & \text{if $s=0$;}\\
c_k(k,n;i), & \text{otherwise}.
\end{array}
\right.
$$ 

Hence, $c_1(k,n;i)+c_k(k,n;i)$ remains constant for $1\leq i\leq n$.

Again, for $1\leq i \leq n/2$, we have 
$$i-1 \leq n-i.$$

For $2\leq j\leq k-1$, we want to show
$$c_j(k,n;i+1)+c_{k-j+1}(k,n;i+1)\geq c_j(k,n;i)+c_{k-j+1}(k,n;i).$$


Assume $j>\smallfloor{k/2}$.
This implies $k-j\leq j-1$. Since $i-1 \leq n-i$, we have 
$$\floor{{(i-1)\over(j-1)}}\leq \floor{{(n-i)\over (k-j)}}.$$
So for $1\leq i\leq n/2-1$, and considering $i\equiv s \pmod{j-1}$ and $t=\smallfloor{i/(j-1)}$,
we have,
\begin{eqnarray*}
c_j(k,n;i+1) & = & \floor{{i\over j-1}} = t\\
c_j(k,n;i) & = & \floor{{i-1\over j-1}} = \floor{t+{s-1\over j-1}} = 
\left\{
\begin{array}{ll}
t-1, & \text{if $s=0$};\\
t, & \text{if $s\geq 1$}.
\end{array}
\right.
\end{eqnarray*}

Take $j'=k-j+1$, and then $j'-1\leq k-j'$.
If $\smallfloor{(i-1)/(j'-1)}\leq \smallfloor{(n-i)/(k-j')}$, then
$$0\leq c_{j'}(k,n;i+1)-c_{j'}(k,n;i)\leq 1,$$
else
\begin{eqnarray*}
c_{j'}(k,n;i) &=& \floor{{n-i\over k-j'}} = \floor{{n-i\over j-1}} = \floor{mh_{j-1}-t-{s\over j-1}}\\
              &=& 
\left\{
\begin{array}{ll}
(mh_{j-1}-t), & \text{if $s=0$};\\
(mh_{j-1}-t-1), & \text{otherwise}.\\
\end{array}
\right.\\
c_{j'}(k,n;i+1) & = & \floor{{n-i-1\over k-j'}} = \floor{mh_{j-1}-t-{s+1\over j-1}}=(mh_{j-1}-t-1)
\end{eqnarray*}

Therefore, $$c_j(k,n;i+1)+c_{j'}(k,n;i+1)\geq c_j(k,n;i)+c_{j'}(k,n;i).$$

So the sequence $c(k,n;x)$ with $1\leq x\leq n/2$ is non-decreasing and hence
the sequence $c(k,n;x)$ with $1\leq x\leq n$ is unimodal for infinitely many $n$. 
\end{proof}
\end{lemma}




\section{Uniqueness conjectures}\label{sec-uniqueness}
In this section, we generalize Szekeres' conjecture and provide a construction for the lower bound.
We also provide a construction algorithm for $r(k,n)$.
Define 
$$J(k,L) = \set{(n,m): n\leq L, r(k,n)=m \text{ and } b(k,n)=1}.$$

We have the following experimental data, based on which we formulate Conjectures \ref{conj-1} and \ref{conj-2}:
\begin{eqnarray*}
J(3,123) & = & \parbox[t]{4in}{\{$(2,2), (5,4), (14,8), (30,12), (41,16), (74,22), (84,24), (104,28)$, $(114,30), (122,32)$\},}\\
J(5,105) & = & \set{(2,2),(3,3),(4,4),(9,8),(14,12),(19,16),(44,32),(69,48),(94,64)},\\
J(7,139) & = & \parbox[t]{4in}{\{$(2,2), (3,3), (4,4), (5,5), (6,6), (13,12), (20,18), (27,24), (34,30)$, 
$(41,36), (90,72), (139,108)$\},}\\
J(11,117) & = & \parbox[t]{4in}{\{$(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),(10,10),(21,20)$,
$(32,30),(43,40),(54,50),(65,60),(76,70),(87,80),(98,90),(109,100)$\},}\\
J(13,161) & = & \parbox[t]{4in}{\{$(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),(10,10),(11,11)$,
$(12,12),(25,24),(38,36),(51,48),(64,60),(77,72),(90,84),(103,96)$, $(116,108),(129,120),(142,132),(155,144)$\}.}
\end{eqnarray*}


%$$J(3,67) = \set{(2,2), (5,4),(14,8), (30,12),(41,16)},$$
%$$J(5,105)=\set{(2,2),(3,3),(4,4),(9,8),(14,12),(19,16),(44,32),(69,48),(94,64)},$$
%$$J(7,139)=\parbox[t]{4in}{\{(2,2), (3,3), (4,4), (5,5), (6,6), (13,12), (20,18), (27,24), (34,30), (41,36), (90,72), (139,108)\}}$$

%Based on experimental data, we generalize the Szekeres' conjecture as follows:

\begin{conj}[The Uniqueness Conjecture]\label{conj-1}
Consider a prime $p\geq 3$ and an integer $t\geq 1$. % $1\leq i\leq p-1$, and $t\geq 1$. %$x = [(p-2)p^t+1]/(p-1)$.                                                                            
Then for $1\leq i\leq p-1$,
$$r\left(p, {(ip-i-1)p^t+1 \over (p-1)}\right)= i\cdot(p-1)^t,$$
and
$b\left(p, x\right)=1$
where $1\leq x\leq p-2$ or else $$x={(ip-i-1)p^t+1 \over (p-1)}.$$
\end{conj}

It can be observed that Szekeres' conjecture is a special case
of Conjecture \ref{conj-1} with $i=1$.

\begin{conj}[Strong Uniqueness Conjecture]\label{conj-2}
Consider a prime $p>3$ and an integer $t\geq 1$. Then
$b(p, x)=1$ if and only if $1\leq x\leq p-2$
or else $$x = {(ip-i-1)p^t+1 \over (p-1)}$$
with $1\leq i\leq p-1$.
\end{conj}

See Appendix \ref{app-3} for data supporting Conjectures \ref{conj-1} and \ref{conj-2}.

\subsection{Construction for the lower-bound of Conjecture \ref{conj-1}}
For a prime $p>3$ and $1\leq i\leq p-1$, take $$n={(ip-i-1)p^t+1 \over p-1} = ip^t-p^{t-1}-p^{t-2}-\cdots-p-1.$$
We can construct a $p$-AP free subset of $\set{1,2,\ldots,n}$ of size $i\cdot(p-1)^t$ as follows:

\begin{eqnarray*}
T_0 &=& \set{1,2,\ldots,n},\\
T_1 &=& T_0 - \set{j : j\equiv{0}\pmod{p}} = T_0 - S_0,\\
T_2 &=& T_1 - \set{j_1p^2-p+j_2 : 1\leq j_1\leq \smallfloor{n/p^2}, 1\leq j_2\leq p-1} = T_1 - S_1, \\
T_3 &=& T_2 - \set{j_1p^3-p^2+j_2p-j_3 : 1\leq j_1\leq \smallfloor{n/p^3}, 1\leq j_2,j_3\leq p-1} = T_2 - S_2,\\
T_4 &=& T_3 - \set{j_1p^4-p^3+j_2p^2-j_3p+j_4 : 1\leq j_1\leq \smallfloor{n/p^4}, 1\leq j_2,j_3,j_4\leq p-1}\\
    &=& T_3 - S_3,\\
    &\vdots,&\\
T_t %&=& T_{t-1} - \set{j_1p^t-p^{t-1}+\cdots+(-1)^{t-1}j_{t-1}p+(-1)^tj_t: 1\leq j_1\leq \smallfloor{n/p^t}, 1\leq j_2,j_3,\ldots,j_t\leq p-1}\\
    &=& T_{t-1} - \set{j_1p^t-p^{t-1}+\sum_{\ell=2}^tp^{t-\ell}j_\ell(-1)^\ell: 1\leq j_1\leq \smallfloor{n/p^t}, 1\leq j_2,j_3,\ldots,j_t\leq p-1}\\
%\cdots+(-1)^{t-1}j_{t-1}p+(-1)^tj_t: 1\leq j_1\leq \smallfloor{n/p^t}, 1\leq j_2,j_3,\ldots,j_t\leq p-1}\\
    &=& T_{t-1}-S_{t-1}.
\end{eqnarray*}

It can be observed that
\begin{eqnarray*}
|S_0| &=& \smallfloor{n/p} = ip^{t-1}-p^{t-2}-\cdots-p-2,\\
|S_1| &=& (p-1)\smallfloor{n/p^2} = (p-1)\parens{ip^{t-2}-p^{t-3}-\cdots-p-2},\\
|S_2| &=& (p-1)^2\smallfloor{n/p^3} = (p-1)^2\parens{ip^{t-3}-p^{t-4}-\cdots-p-2},\\
      &\vdots,&\\
|S_{t-1}| &=& (p-1)^{t-1}\smallfloor{n/p^t} = (p-1)^{t-1}(i-1).
\end{eqnarray*}

\begin{lemma}
The $S_\ell$'s for $0\leq \ell\leq t-1$ are disjoint.
\begin{proof}
Each element in $S_0$ is divisible by $p$, and no element in any other $S_\ell$ is divisible by $p$.
So $S_0$ is disjoint from every other $S_\ell$.
For $2\leq \ell\leq t-1$,
$$S_\ell = \set{(xp+(-1)^{\ell-1}j_{\ell+1}) \in T_0 : x\in S_{\ell-1}, 1\leq j_{\ell+1}\leq p-1},$$
and hence $S_\ell\cap S_u=\emptyset$ for $1\leq u\leq \ell-1$.
\end{proof}
\end{lemma}

\begin{lemma}
For a prime $p>3$ and $1\leq i\leq p-1$, $$|T_t| = i\cdot(p-1)^t.$$

\begin{proof}
We can write the summation $\sum_{j=0}^{t-1}|S_j|$ as follows:
\begin{eqnarray*}
\sum_{j=0}^{t-1}|S_j| &=& ip^{t-1}\parens{\sum_{a=0}^{t-1}{a\choose 0}} + \cdots
                                                                        + (-1)^{\ell-1}ip^{t-\ell}\parens{\sum_{a=\ell-1}^{t-1}{a\choose \ell-1}}
                                                                        + \cdots -i - \sum_{\ell=0}^{t-1}p^\ell,\\
                      &=& ip^{t-1}{t\choose 1} + \cdots
                                                                        + (-1)^{\ell-1}ip^{t-\ell}{t\choose \ell}
                                                                        + \cdots -i - \sum_{\ell=0}^{t-1}p^\ell,\\
                      &=& i\sum_{\ell=1}^t{t\choose \ell}p^{t-\ell}(-1)^{\ell-1}-\sum_{\ell=0}^{t-1}p^\ell.
\end{eqnarray*}

The fact $$\sum_{a=\ell-1}^{t-1}{a\choose \ell-1}={t \choose \ell}$$ can be easily proven using induction on $t$ and
using the fact that $${t\choose\ell}+{t\choose\ell-1}={t+1\choose \ell}.$$
Now, we have
\begin{eqnarray*}
|T_t| &=& n-\sum_{j=0}^{t-1}|S_j|,\\
      &=& ip^t-\sum_{\ell=0}^{t-1}p^\ell -\parens{i\sum_{\ell=1}^t{t\choose \ell}p^{t-\ell}(-1)^{\ell-1}-\sum_{\ell=0}^{t-1}p^\ell},\\
      &=& ip^t+i\sum_{\ell=1}^t{t\choose \ell}p^{t-\ell}(-1)^{\ell} = i\cdot(p-1)^t.
\end{eqnarray*}
\end{proof}
\end{lemma}

\begin{lemma}\label{lemma-Xd}
Given a prime $p>3$,
$n=ip^t-\sum_{\ell=0}^{t-1}p^\ell$ with $1\leq i\leq p-1$, and the set $T=\set{1,2,\ldots,n}$;
the set $T_1$
contains no $p$-AP with
$$d \in \set{1 \leq d_1 \leq \smallfloor{(n-1) / (p-1)}: d_1 \not\equiv{0}\pmod{p}}.$$
\begin{proof}
Assume $T_1$ contains a $p$-AP $a,a+d,\ldots,a+(p-1)d$. Here
$a\not\equiv{0}\pmod{p}$.
Suppose $a\equiv{j}\pmod{p}$ for some $1\leq j\leq p-1$.
Then $a+d(p-z)\equiv 0\pmod{p}$ for some $1\leq z\leq p-1$ when
$dz\equiv{j}\pmod{p}$.

For each $d\in \set{1\leq d_1\leq \smallfloor{(n-1)/(p-1)}: d_1\not\equiv{0}\pmod{p}}$,
$$\bigcup_{z=1}^{p-1}\set{dz\pmod{p}}=\set{1,2,\ldots,p-1}$$
and so there exists $1\leq z\leq p-1$ for any $1\leq j \leq p-1$ such that
$dz\equiv{j}\pmod{p}$. But,
this is a contradiction as there is no number in $T_1$ which is divisible by $p$.
Hence $T_1$ contains no $p$-AP with $d\in \set{1\leq d_1\leq \smallfloor{(n-1)/(p-1)}: d_1\not\equiv{0}\pmod{p}}$.
\end{proof}
\end{lemma}

\begin{lemma}
The set $T_t$ is $p$-AP free.
\begin{proof}
By construction, $T_t$ contains no $p$-AP with $d\in\set{1,p,p^2,\ldots,p^t}$.
By Lemma \ref{lemma-Xd}, $T_t$ does not contain a $p$-AP with any other $d$.
Hence $T_t$ is $p$-AP free.
\end{proof}
\end{lemma}


\subsection{A construction algorithm for $r(k,n)$}
In this section, we propose a greedy algorithm for
construction of $k$-AP free subsequence of $1,2,\ldots,n$.
We call this algorithm \emph{Bi-symmetric Greedy Algorithm} (BGA) as
it builds a fully symmetric subsequence that is $k$-AP free.
\begin{enumerate}
\item Take $T = \set{1,n}$.
\item Choose the smallest $j\in \set{1,2,\ldots,n}-T$ such that $T\cup\set{j,n-j+1}$
is $k$-AP free. Set $T = T\cup\set{j,n-j+1}$.
\item Repeat step 2 until no such $j$ can be found.
\item Output $T$.
\end{enumerate}

Clearly,
$$r(k,n) \geq |BGA(k,n)|.$$

From experimental data, we have the following observation:

\begin{obs}
Consider a prime $p>3$. Then
$|BGA(p,x)|=x$ if $1\leq x\leq p-2$, or else
for $1\leq i\leq p-1$ and $t\geq 1$,
$$\left|BGA\left(p, {(ip-i-1)p^t+1 \over (p-1)}\right)\right| = i\cdot(p-1)^t.$$
\end{obs}
See Appendix \ref{app-2} for supporting data.


\section*{Acknowledgements}
The authors would like to thank the anonymous referee and the Editor for helpful comments and suggestions. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\begin{thebibliography}{9}
\bibitem{behrend} F. A. Behrend, On Sets of Integers Which Contain No Three Terms in Arithmetic Progression,
\emph{Proc. Nat. Acad. Sci. USA}, \textbf{32} (1946), 331--332.

\bibitem{dybizbanski} J. Dybizba\'nski, Sequences containing no 3-term arithmetic progressions,
\emph{Elec. J. of Comb.}, \textbf{19(2)} (2012), \#P15.

\bibitem{elkin} M. Elkin, An Improved Construction of Progression-Free Sets,
\emph{Israeli J. Math.}, \textbf{184}, (2011), 93--128.

\bibitem{erdos-turan} P. Erd\H{o}s and P. Tur\'an, On some sequence of integers, \emph{J. London Math. Soc.},
\textbf{11} (1936), 261--264.

\bibitem{roth} K. F. Roth, On certain set of integers, \emph{J. London Math. Soc.}, \textbf{28} (1953), 104--109.

\bibitem{salem-spencer} R. Salem and D. C. Spencer, On Sets of Integers Which Contain No Three Terms in
Arithmetic Progression, \emph{Proc. Nat. Acad. Sci. USA}, \textbf{28} (1942), 561--563.

\bibitem{sharma} A. Sharma, Sequences of Integers Avoiding 3-term Arithmetic Progressions,
\emph{Elec. J. of Comb.}, \textbf{19} (2012), \#P27.

\bibitem{szemeredi} E. Szemeredi, On sets of integers containing no $k$ elements in arithmetic progression,
\emph{Acta Arithmetica}, \textbf{27} (1975), 199--245.    
\end{thebibliography}

\newpage
\appendix
\section{Computed values}\label{app-1}

\footnotesize
\indent\indent $f(3)=4$, $c_{max}(3,n-4)=c_{max}(3,n)+4$ for $n\ge 8$
\begin{longtable}{c|c|c||c|c|c||c|c|c||c} 
\hline
$n$ & $c_{max}(3,n)$ & $|U|$ & $n$ & $c_{max}(3,n)$ & $|U|$ & $n$ & $c_{max}(3,n)$ & $|U|$ &  \\
\hline
4 & 2 & 2 & 8 & 6 & 2 & 12 & 10 & 2 & $\cdots$ \\
5 & 4 & \bf{4} & 9 & 8 & \bf{4} & 13 & 12 & \bf{4} & $\cdots$ \\
6 & 4 & 2 & 10 & 8 & 2 & 14 & 12 & 2 & $\cdots$ \\
7 & 5 & \bf{4} & 11 & 9 & \bf{4} & 15 & 13 & \bf{4} & $\cdots$ \\
\hline
\end{longtable}
$f(5)=8$, $c_{max}(5,n-24)=c_{max}(5,n)+20$ for $n\ge 62$
\begin{longtable}{c|c|c||c|c|c||c|c|c||c} 
\hline
$n$ & $c_{max}(5,n)$ & $|U|$ & $n$ & $c_{max}(5,n)$ & $|U|$ & $n$ & $c_{max}(5,n)$ & $|U|$ &  \\
\hline
38 & 29 & 6 & 62 & 49 & 6 & 86 & 69 & 6 & $\cdots$ \\
39 & 30 & 6 & 63 & 50 & 6 & 87 & 70 & 6 & $\cdots$ \\
40 & 31 & 6 & 64 & 51 & 6 & 88 & 71 & 6 & $\cdots$ \\
41 & 32 & 6 & 65 & 52 & 6 & 89 & 72 & 6 & $\cdots$ \\
42 & 33 & \bf{8} & 66 & 53 & \bf{8} & 90 & 73 & \bf{8} & $\cdots$ \\
$\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ &$\vdots$   & $\vdots$ & $\vdots$   \\
60 & 47 & 4 & 84 & 67 & 4 & 108 & 87 & 4 & $\cdots$ \\
61 & 49 & \bf{8} & 85 & 69 & \bf{8} & 109 & 89 & \bf{8} & $\cdots$ \\
\hline
\end{longtable}
$f(7)=14$, $c_{max}(7,n-120)=c_{max}(7,n)+94$ for $n\ge 467$
\begin{longtable}{c|c|c||c|c|c||c|c|c||c} 
\hline
$n$ & $c_{max}(7,n)$ & $|U|$ & $n$ & $c_{max}(7,n)$ & $|U|$ & $n$ & $c_{max}(7,n)$ & $|U|$ &  \\
\hline
347 & 268 & 10 & 467 & 362 & 10 & 587 & 456 & 10 & $\cdots$ \\
348 & 269 & 10 & 468 & 363 & 10 & 588 & 457 & 10 & $\cdots$ \\
349 & 270 & 10 & 469 & 364 & 10 & 589 & 458 & 10 & $\cdots$ \\
350 & 271 & 10 & 470 & 365 & 10 & 590 & 459 & 10 & $\cdots$ \\
$\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ &$\vdots$   & $\vdots$ & $\vdots$   \\
358 & 278 & \bf{14} & 478 & 372 & \bf{14} & 598 & 466 & \bf{14} & $\cdots$ \\
$\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ &$\vdots$   & $\vdots$ & $\vdots$   \\
465 & 361 & 10 & 585 & 455 & 10 & 705 & 549 & 10 & $\cdots$ \\
466 & 361 & \bf{14} & 586 & 455 & \bf{14} & 706 & 549 & \bf{14} & $\cdots$ \\
\hline
\end{longtable}
$f(9)=20$, $c_{max}(9,n-6720)=c_{max}(9,n)+5104$ for $n\ge 13365$
\begin{longtable}{c|c|c||c|c|c||c|c|c||c} 
\hline
$n$ & $c_{max}(9,n)$ & $|U|$ & $n$ & $c_{max}(9,n)$ & $|U|$ & $n$ & $c_{max}(9,n)$ & $|U|$ &  \\
\hline
6645 & 5043 & 14 & 13365 & 10147 & 14 & 20085 & 15251 & 14 & $\cdots$ \\
6646 & 5045 & 14 & 13366 & 10149 & 14 & 20086 & 15253 & 14 & $\cdots$ \\
6647 & 5045 & 16 & 13367 & 10149 & 16 & 20087 & 15253 & 16 & $\cdots$ \\
6648 & 5045 & 14 & 13368 & 10149 & 14 & 20088 & 15253 & 14 & $\cdots$ \\
$\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ &$\vdots$   & $\vdots$ & $\vdots$   \\
6691 & 5078 & \bf{20} & 13411 & 10182 & \bf{20} & 20131 & 15286 & \bf{20} & $\cdots$ \\
$\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ & $\vdots$  & $\vdots$ &$\vdots$   & $\vdots$ & $\vdots$   \\
13363 & 10146 & 14 & 20083 & 15250 & 14 & 26803 & 20354 & 14 & $\cdots$ \\
13364 & 10146 & 16 & 20084 & 15250 & 16 & 26804 & 20354 & 16 & $\cdots$ \\
\hline
\end{longtable}
$f(11)=26$, $f(13)=36$
\normalsize

\section{BGA results}\label{app-2}
$$p=3$$
\footnotesize
$t=1$, $i=1$, $|BGA(3,2)|=2$\\
$BGA(3,2)|=\{1, 2\}$\\
$t=2$, $i=1$, $|BGA(3,5)|=4$\\
$BGA(3,5)|=\{1, 2, 4, 5\}$\\
$t=3$, $i=1$, $|BGA(3,14)|=8$\\
$BGA(3,14)|=\{1, 2, 4, 5, 10, 11, 13, 14\}$\\
$t=4$, $i=1$, $|BGA(3,41)|=16$\\
$BGA(3,41)|=\{1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41\}$\\
$t=5$, $i=1$, $|BGA(3,122)|=32$\\
$BGA(3,122)|=\{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\}$\\
$t=6$, $i=1$, $|BGA(3,365)|=64$\\
$BGA(3,365)|=\{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, 244, 245, 247, 248, 253, 254, 256, 257, 271, 272, 274, 275, 280, 281, 283, 284, 325, $\\$326, 328, 329, 334, 335, 337, 338, 352, 353, 355, 356, 361, 362, 364, 365\}$\\
$t=7$, $i=1$, $|BGA(3,1094)|=128$\\
$BGA(3,1094)|=\{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, 244, 245, 247, 248, 253, 254, 256, 257, 271, 272, 274, 275, 280, 281, 283, 284, 325, $\\$326, 328, 329, 334, 335, 337, 338, 352, 353, 355, 356, 361, 362, 364, 365, 730, 731, 733, 734, 739, 740, 742, 743,$\\$ 757, 758, 760, 761, 766, 767, 769, 770, 811, 812, 814, 815, 820, 821, 823, 824, 838, 839, 841, 842, 847, 848, 850,$\\$ 851, 973, 974, 976, 977, 982, 983, 985, 986, 1000, 1001, 1003, 1004, 1009, 1010, 1012, 1013, 1054, 1055, 1057,$\\$ 1058, 1063, 1064, 1066, 1067, 1081, 1082, 1084, 1085, 1090, 1091, 1093, 1094\}$\\
\normalsize

$$p=5$$
\footnotesize
$t=1$, $i=1$, $|BGA(5,4)|=4$\\
$BGA(5,4)|=\{1, 2, 3, 4\}$\\
$t=1$, $i=2$, $|BGA(5,9)|=8$\\
$BGA(5,9)|=\{1, 2, 3, 4, 6, 7, 8, 9\}$\\
$t=1$, $i=3$, $|BGA(5,14)|=12$\\
$BGA(5,14)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14\}$\\
$t=2$, $i=1$, $|BGA(5,19)|=16$\\
$BGA(5,19)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19\}$\\
$t=2$, $i=2$, $|BGA(5,44)|=32$\\
$BGA(5,44)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, $\\$42, 43, 44\}$\\
$t=2$, $i=3$, $|BGA(5,69)|=48$\\
$BGA(5,69)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, $\\$42, 43, 44, 51, 52, 53, 54, 56, 57, 58, 59, 61, 62, 63, 64, 66, 67, 68, 69\}$\\
$t=3$, $i=1$, $|BGA(5,94)|=64$\\
$BGA(5,94)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41,$\\$ 42, 43, 44, 51, 52, 53, 54, 56, 57, 58, 59, 61, 62, 63, 64, 66, 67, 68, 69, 76, 77, 78, 79, 81, 82, 83, 84, 86, 87, 88, 89,$\\$ 91, 92, 93, 94\}$\\
$t=3$, $i=2$, $|BGA(5,219)|=128$\\
$BGA(5,219)|=\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, $\\$42, 43, 44, 51, 52, 53, 54, 56, 57, 58, 59, 61, 62, 63, 64, 66, 67, 68, 69, 76, 77, 78, 79, 81, 82, 83, 84, 86, 87, 88, 89,$\\$ 91, 92, 93, 94, 126, 127, 128, 129, 131, 132, 133, 134, 136, 137, 138, 139, 141, 142, 143, 144, 151, 152, 153, 154,$\\$ 156, 157, 158, 159, 161, 162, 163, 164, 166, 167, 168, 169, 176, 177, 178, 179, 181, 182, 183, 184, 186, 187, 188,$\\$ 189, 191, 192, 193, 194, 201, 202, 203, 204, 206, 207, 208, 209, 211, 212, 213, 214, 216, 217, 218, 219\}$\\
\normalsize

$$p=7$$
\footnotesize
$t=1$, $i=1$, $|BGA(7,6)|=6$\\
$BGA(7,6)|=\{1, 2, 3, 4, 5, 6\}$\\
$t=1$, $i=2$, $|BGA(7,13)|=12$\\
$BGA(7,13)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13\}$\\
$t=1$, $i=3$, $|BGA(7,20)|=18$\\
$BGA(7,20)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20\}$\\
$t=1$, $i=4$, $|BGA(7,27)|=24$\\
$BGA(7,27)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27\}$\\
$t=1$, $i=5$, $|BGA(7,34)|=30$\\
$BGA(7,34)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33,$\\$ 34\}$\\
$t=2$, $i=1$, $|BGA(7,41)|=36$\\
$BGA(7,41)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33,$\\$ 34, 36, 37, 38, 39, 40, 41\}$\\
$t=2$, $i=2$, $|BGA(7,90)|=72$\\
$BGA(7,90)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33,$\\$ 34, 36, 37, 38, 39, 40, 41, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76,$\\$ 78, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 90\}$\\
$t=2$, $i=3$, $|BGA(7,139)|=108$\\
$BGA(7,139)|=\{1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33,$\\$ 34, 36, 37, 38, 39, 40, 41, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76,$\\$ 78, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 90, 99, 100, 101, 102, 103, 104, 106, 107, 108, 109, 110, 111, 113, 114,$\\$ 115, 116, 117, 118, 120, 121, 122, 123, 124, 125, 127, 128, 129, 130, 131, 132, 134, 135, 136, 137, 138, 139\}$\\
\normalsize

$$p=11$$
\footnotesize
$t=1$, $i=1$, $|BGA(11,10)|=10$\\
$BGA(11,10)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$\\
$t=1$, $i=2$, $|BGA(11,21)|=20$\\
$BGA(11,21)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21\}$\\
$t=1$, $i=3$, $|BGA(11,32)|=30$\\
$BGA(11,32)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32\}$\\
$t=1$, $i=4$, $|BGA(11,43)|=40$\\
$BGA(11,43)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43\}$\\
$t=1$, $i=5$, $|BGA(11,54)|=50$\\
$BGA(11,54)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54\}$\\
$t=1$, $i=6$, $|BGA(11,65)|=60$\\
$BGA(11,65)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65\}$\\
$t=1$, $i=7$, $|BGA(11,76)|=70$\\
$BGA(11,76)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, $\\$67, 68, 69, 70, 71, 72, 73, 74, 75, 76\}$\\
$t=1$, $i=8$, $|BGA(11,87)|=80$\\
$BGA(11,87)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, $\\$67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87\}$\\
$t=1$, $i=9$, $|BGA(11,98)|=90$\\
$BGA(11,98)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, $\\$67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98\}$\\
$t=2$, $i=1$, $|BGA(11,109)|=100$\\
$BGA(11,109)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, $\\$67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 100,$\\$ 101, 102, 103, 104, 105, 106, 107, 108, 109\}$\\
$t=2$, $i=2$, $|BGA(11,230)|=200$\\
$BGA(11,230)|=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31,$\\$ 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, $\\$67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 100,$\\$ 101, 102, 103, 104, 105, 106, 107, 108, 109, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 133, 134, 135, 136,$\\$ 137, 138, 139, 140, 141, 142, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 155, 156, 157, 158, 159, 160, 161, $\\$162, 163, 164, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186,$\\$ 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 210, 211, 212,$\\$ 213, 214, 215, 216, 217, 218, 219, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230\}$\\
\normalsize
\newpage
\section{Computed values of $r(k,n)$}\label{app-3}

\footnotesize

\begin{longtable}{c|c|c|c|c||c|c|c|c|c} 
\hline
$n$ & $b(n)$ & lower bound & $r(3,n)$ & upper bound  & $n$ & $b(n)$ & lower bound & $r(3,n)$  & upper bound  \\
& & $|BGA(3,n)|$ &  & (Theorem~\ref{thm1}) &  &  & $|BGA(3,n)|$ & & (Theorem~\ref{thm1}) \\
\hline
4 & 2 & 2 & 3 & 3 & 54 & 2 & 16 & 18 & 41 \\
5 & 1 & 4 & 4 & 4 & 58 & 2 & 16 & 19 & 44\\
9 & 4 & 4 & 5 & 7 & 63 & 2 & 16 & 20 & 48\\
11 & 7 & 6 & 6 & 9 & 71 & 4 & 18 & 21 & 54\\
13 & 6 & 6 & 7 & 10 & 74 & 1 & 18 & 22 & 56\\
14 & 1 & 8 & 8 & 11 & 82 & 10 & 18 & 23 & 62\\
20 & 2 & 8 & 9 & 15 & 84 & 1 & 18 & 24 & 63\\
24 & 2 & 8 & 10 & 18 & 92 & 14 & 22 & 25 & 69\\
26 & 2 & 10 & 11 & 20 & 95 & 8 & 24 & 26 & 72\\
30 & 1 & 10 & 12 & 23 & 100 & 2 & 24 & 27 & 75\\
32 & 2 & 12 & 13 & 24 & 104 & 1 & 24 & 28 & 78\\
36 & 2 & 12 & 14 & 27 & 111 & 6 & 26 & 29 & 84\\
40 & 20 & 14 & 15 & 30 & 114 & 1 & 28 & 30 & 86\\
41 & 1 & 16 & 16 & 31 & 121 & 70 & 30 & 31 & 91\\
51 & 14 & 16 & 17 & 39 & 122 & 1 & 32 & 32 & 92\\
\hline
\end{longtable}

\begin{longtable}{c|c|c|c|c||c|c|c|c|c} 
\hline
$n$ & $b(n)$ & lower bound & $r(4,n)$ & upper bound  & $n$ & $b(n)$ & lower bound & $r(4,n)$  & upper bound  \\
& & $|BGA(4,n)|$ &  & (Theorem~\ref{thm1}) &  &  & $|BGA(4,n)|$ & & (Theorem~\ref{thm1}) \\
\hline
5 & 3 & 4 & 4 & 5 & 30 & 2 & 16 & 18 & 25\\
6 & 2 & 4 & 5 & 5 & 33 & 6 & 16 & 19 & 28\\
8 & 4 & 6 & 6 & 7 & 34 & 2 & 18 & 20 & 29\\
9 & 2 & 6 & 7 & 8 & 37 & 6 & 18 & 21 & 31\\
10 & 1 & 8 & 8 & 9 & 40 & 14 & 18 & 22 & 34\\
13 & 3 & 9 & 9 & 11 & 43 & 38 & 18 & 23 & 36\\
15 & 2 & 8 & 10 & 13 & 45 & 2 & 20 & 24 & 38\\
17 & 10 & 10 & 11 & 15 & 48 & 2 & 20 & 25 & 40\\
19 & 24 & 12 & 12 & 16 & 50 & 3 & 22 & 26 & 42\\
21 & 10 & 12 & 13 & 18 & 53 & 12 & 22 & 27 & 45\\
23 & 12 & 13 & 14 & 20 & 54 & 1 & 24 & 28 & 45\\
25 & 2 & 14 & 15 & 21 & 58 & 6 & 26 & 29 & 49\\
27 & 8 & 14 & 16 & 23 & 60 & 1 & 26 & 30 & 50\\
28 & 4 & 14 & 17 & 24				 &  & & & & \\
\hline
\end{longtable}
\newpage
\begin{longtable}{c|c|c|c|c||c|c|c|c|c} 
\hline
$n$ & $b(n)$ & lower bound & $r(5,n)$ & upper bound  & $n$ & $b(n)$ & lower bound & $r(5,n)$  & upper bound  \\
& & $|BGA(5,n)|$ &  & (Theorem~\ref{thm1}) &  &  & $|BGA(5,n)|$ & & (Theorem~\ref{thm1}) \\
\hline
6 & 4 & 4 & 5 & 6 & 52 & 2 & 32 & 35 & 46\\
7 & 3 & 6 & 6 & 7 & 54 & 1300 & 32 & 36 & 48\\
8 & 2 & 6 & 7 & 7 & 56 & 3508 & 32 & 37 & 49\\
9 & 1 & 8 & 8 & 8 & 57 & 1736 & 36 & 38 & 50\\
11 & 6 & 8 & 9 & 10 & 58 & 768 & 32 & 39 & 51\\
12 & 4 & 10 & 10 & 11 & 59 & 256 & 40 & 40 & 52\\
13 & 2 & 8 & 11 & 12 & 61 & 512 & 36 & 41 & 54\\
14 & 1 & 12 & 12 & 13 & 62 & 192 & 38 & 42 & 55\\
16 & 4 & 12 & 13 & 14 & 63 & 64 & 38 & 43 & 56\\
17 & 3 & 12 & 14 & 15 & 64 & 16 & 36 & 44 & 56\\
18 & 2 & 14 & 15 & 16 & 66 & 32 & 40 & 45 & 58\\
19 & 1 & 16 & 16 & 17 & 67 & 12 & 40 & 46 & 59\\
24 & 40 & 16 & 17 & 21 & 68 & 4 & 42 & 47 & 60\\
25 & 2 & 16 & 18 & 22 & 69 & 1 & 48 & 48 & 61\\
27 & 70 & 18 & 19 & 24 & 76 & 2012 & 42 & 49 & 67\\
28 & 12 & 18 & 20 & 25 & 77 & 1202 & 44 & 50 & 68\\
29 & 2 & 20 & 21 & 26 & 78 & 640 & 44 & 51 & 69\\
31 & 5 & 20 & 22 & 28 & 79 & 256 & 48 & 52 & 70\\
33 & 266 & 22 & 23 & 29 & 81 & 768 & 44 & 53 & 71\\
34 & 81 & 24 & 24 & 30 & 82 & 432 & 48 & 54 & 72\\
36 & 236 & 24 & 25 & 32 & 83 & 216 & 48 & 55 & 73\\
37 & 115 & 26 & 26 & 33 & 84 & 81 & 52 & 56 & 74\\
38 & 48 & 24 & 27 & 34 & 86 & 216 & 50 & 57 & 76\\
39 & 16 & 28 & 28 & 35 & 87 & 108 & 52 & 58 & 77\\
41 & 32 & 26 & 29 & 36 & 88 & 48 & 50 & 59 & 77\\
42 & 12 & 28 & 30 & 37 & 89 & 16 & 56 & 60 & 78\\
43 & 4 & 30 & 31 & 38 & 91 & 32 & 54 & 61 & 80\\
44 & 1 & 32 & 32 & 39 & 92 & 12 & 56 & 62 & 81\\
49 & 2 & 32 & 33 & 43 & 93 & 4 & 56 & 63 & 82\\
51 & 18 & 32 & 34 & 45 & 94 & 1 & 64 & 64 & 83\\
\hline
\end{longtable}
\newpage
\begin{longtable}{c|c|c|c|c||c|c|c|c|c} 
\hline
$n$ & $b(n)$ & lower bound & $r(7,n)$ & upper bound  & $n$ & $b(n)$ & lower bound & $r(7,n)$  & upper bound  \\
& & $|BGA(7,n)|$ &  & (Theorem~\ref{thm1}) &  &  & $|BGA(7,n)|$ & & (Theorem~\ref{thm1}) \\
\hline
8 & 6 & 6 & 7 & 8 & 51 & 76 & 38 & 40 & 47\\
9 & 5 & 8 & 8 & 9 & 52 & 22 & 38 & 41 & 48\\
10 & 4 & 8 & 9 & 10 & 53 & 2 & 40 & 42 & 49\\
11 & 3 & 10 & 10 & 11 & 55 & 242 & 42 & 43 & 51\\
12 & 2 & 10 & 11 & 11 & 56 & 8 & 42 & 44 & 52\\
13 & 1 & 12 & 12 & 12 & 57 & 4 & 42 & 45 & 53\\
15 & 12 & 12 & 13 & 14 & 59 & 218 & 44 & 46 & 55\\
16 & 9 & 14 & 14 & 15 & 60 & 54 & 46 & 47 & 55\\
17 & 6 & 13 & 15 & 16 & 61 & 10 & 46 & 48 & 56\\
18 & 4 & 16 & 16 & 17 & 63 & 32 & 48 & 49 & 58\\
19 & 2 & 16 & 17 & 18 & 64 & 14 & 48 & 50 & 59\\
20 & 1 & 18 & 18 & 19 & 65 & 2 & 50 & 51 & 60\\
22 & 8 & 18 & 19 & 21 & 67 & 19807 & 52 & 52 & 62\\
23 & 6 & 20 & 20 & 22 & 68 & 10294 & 52 & 53 & 63\\
24 & 4 & 20 & 21 & 22 & 69 & 4103 & 54 & 54 & 64\\
25 & 3 & 20 & 22 & 23 & 71 & 18522 & 54 & 55 & 66\\
26 & 2 & 20 & 23 & 24 & 72 & 11541 & 56 & 56 & 66\\
27 & 1 & 24 & 24 & 25 & 73 & 6914 & 54 & 57 & 67\\
29 & 6 & 22 & 25 & 27 & 74 & 3888 & 56 & 58 & 68\\
30 & 5 & 24 & 26 & 28 & 75 & 1944 & 56 & 59 & 69\\
31 & 4 & 24 & 27 & 29 & 76 & 729 & 60 & 60 & 70\\
32 & 3 & 24 & 28 & 30 & 78 & 2918 & 58 & 61 & 72\\
33 & 2 & 26 & 29 & 31 & 79 & 1621 & 62 & 62 & 73\\
34 & 1 & 30 & 30 & 32 & 80 & 864 & 60 & 63 & 74\\
36 & 6 & 30 & 31 & 33 & 81 & 432 & 60 & 64 & 75\\
37 & 5 & 28 & 32 & 34 & 82 & 192 & 62 & 65 & 76\\
38 & 4 & 30 & 33 & 35 & 83 & 64 & 66 & 66 & 77\\
39 & 3 & 32 & 34 & 36 & 85 & 192 & 64 & 67 & 78\\
40 & 2 & 30 & 35 & 37 & 86 & 80 & 64 & 68 & 79\\
41 & 1 & 36 & 36 & 38 & 87 & 32 & 66 & 69 & 80\\
46 & 18 & 36 & 37 & 43 & 88 & 12 & 68 & 70 & 81\\
48 & 9 & 36 & 38 & 44 & 89 & 4 & 66 & 71 & 82\\
50 & 392 & 36 & 39 & 46 & 90 & 1 & 72 & 72 & 83\\
\hline
\end{longtable}
\newpage
\begin{longtable}{c|c|c|c|c||c|c|c|c|c} 
\hline
$n$ & $b(n)$ & lower bound & $r(11,n)$ & upper bound  & $n$ & $b(n)$ & lower bound & $r(11,n)$  & upper bound  \\
& & $|BGA(11,n)|$ &  & (Theorem~\ref{thm1}) &  &  & $|BGA(11,n)|$ & & (Theorem~\ref{thm1}) \\
\hline
12 & 10 & 10 & 11 & 12 & 61 & 5 & 54 & 56 & 58\\
13 & 9 & 12 & 12 & 13 & 62 & 4 & 52 & 57 & 59\\
14 & 8 & 12 & 13 & 14 & 63 & 3 & 54 & 58 & 60\\
15 & 7 & 14 & 14 & 15 & 64 & 2 & 56 & 59 & 61\\
16 & 6 & 14 & 15 & 16 & 65 & 1 & 60 & 60 & 62\\
17 & 5 & 16 & 16 & 17 & 67 & 10 & 56 & 61 & 64\\
18 & 4 & 16 & 17 & 18 & 68 & 9 & 58 & 62 & 65\\
19 & 3 & 18 & 18 & 19 & 69 & 8 & 58 & 63 & 66\\
20 & 2 & 18 & 19 & 19 & 70 & 7 & 62 & 64 & 67\\
21 & 1 & 20 & 20 & 20 & 71 & 6 & 62 & 65 & 68\\
23 & 30 & 20 & 21 & 22 & 72 & 5 & 60 & 66 & 69\\
24 & 25 & 22 & 22 & 23 & 73 & 4 & 62 & 67 & 70\\
25 & 20 & 21 & 23 & 24 & 74 & 3 & 62 & 68 & 71\\
26 & 16 & 24 & 24 & 25 & 75 & 2 & 66 & 69 & 72\\
27 & 12 & 24 & 25 & 26 & 76 & 1 & 70 & 70 & 73\\
28 & 9 & 26 & 26 & 27 & 78 & 10 & 66 & 71 & 75\\
29 & 6 & 25 & 27 & 28 & 79 & 9 & 66 & 72 & 76\\
30 & 4 & 28 & 28 & 29 & 80 & 8 & 68 & 73 & 76\\
31 & 2 & 28 & 29 & 30 & 81 & 7 & 68 & 74 & 77\\
32 & 1 & 30 & 30 & 31 & 82 & 6 & 68 & 75 & 78\\
34 & 20 & 30 & 31 & 33 & 83 & 5 & 72 & 76 & 79\\
35 & 16 & 32 & 32 & 34 & 84 & 4 & 72 & 77 & 80\\
36 & 12 & 32 & 33 & 35 & 85 & 3 & 74 & 78 & 81\\
37 & 9 & 32 & 34 & 36 & 86 & 2 & 74 & 79 & 82\\
38 & 6 & 34 & 35 & 37 & 87 & 1 & 80 & 80 & 83\\
39 & 5 & 34 & 36 & 38 & 89 & 10 & 76 & 81 & 85\\
40 & 4 & 36 & 37 & 38 & 90 & 9 & 78 & 82 & 86\\
41 & 3 & 36 & 38 & 39 & 91 & 8 & 76 & 83 & 87\\
42 & 2 & 38 & 39 & 40 & 92 & 7 & 80 & 84 & 88\\
43 & 1 & 40 & 40 & 41 & 93 & 6 & 80 & 85 & 89\\
45 & 10 & 39 & 41 & 43 & 94 & 5 & 80 & 86 & 90\\
46 & 9 & 40 & 42 & 44 & 95 & 4 & 82 & 87 & 91\\
47 & 8 & 40 & 43 & 45 & 96 & 3 & 80 & 88 & 92\\
48 & 7 & 42 & 44 & 46 & 97 & 2 & 80 & 89 & 93\\
49 & 6 & 42 & 45 & 47 & 98 & 1 & 90 & 90 & 94\\
50 & 5 & 44 & 46 & 48 & 100 & 10 & 84 & 91 & 95\\
51 & 4 & 43 & 47 & 49 & 101 & 9 & 84 & 92 & 96\\
52 & 3 & 44 & 48 & 50 & 102 & 8 & 88 & 93 & 97\\
53 & 2 & 46 & 49 & 51 & 103 & 7 & 86 & 94 & 98\\
54 & 1 & 50 & 50 & 52 & 104 & 6 & 88 & 95 & 99\\
56 & 10 & 48 & 51 & 54 & 105 & 5 & 90 & 96 & 100\\
57 & 9 & 50 & 52 & 55 & 106 & 4 & 90 & 97 & 101\\
58 & 8 & 50 & 53 & 56 & 107 & 3 & 92 & 98 & 102\\
59 & 7 & 50 & 54 & 57 & 108 & 2 & 92 & 99 & 103\\
60 & 6 & 52 & 55 & 57 & 109 & 1 & 100 & 100 & 104\\
\hline
\end{longtable}
\normalsize



\end{document}
