Arithmetic Sequences in Finite Set

Question

Consider a finite set $S\subset \mathbb{N}_{\geq 1}$ which contains no arithmetic sequences of length greater than $l$. For each arithmetic sequence of length $l$ contained in $S$, place the greatest element of this arithmetic sequence in a new set, which we call $\overline{S}$. For what values of $l$ is it possible for $$|S\setminus \overline{S}|<|\overline{S}|$$ For $l=3$, the set $A=\{1, 17, 41, 52, 69, 79, 81, 86, 87, 89, 92, 93, 94\}$ (which has no arithmetic sequences of length $4$) has $\overline{A}=\{81, 86, 87, 89, 92, 93, 94\}$, so the inequality can be satisfied. However, it seems like finding such a set should not be possible for $l\geq4$, but I can't find a nice proof.

Answer 1

There exists a set $S$ with the properties you want for every value of $l$. Here are a few examples for the smaller values of $l$:

• For $l=2$: $|S \setminus \bar{S}|=1 < |\bar{S}|=2$ $$ S= \{1,2,4\}$$ $$ \bar{S}= \{2,4\}$$
• For $l=3$: $|S \setminus \bar{S}|=3 < |\bar{S}|=4$ $$ S= \{1, 2, 3, 5, 6, 8, 9\}$$ $$ \bar{S}= \{3, 5, 8, 9\}$$
• For $l=4$: $|S \setminus \bar{S}|=6 < |\bar{S}|=7$ $$ S= \{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16\}$$ $$ \bar{S}= \{4, 8, 9, 12, 13, 14, 16\}$$
• For $l=5$: $|S \setminus \bar{S}|=16 < |\bar{S}|=17$ $$ S= \{1, 2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, 17, 18, 19, 20, 22, 23, 24, 25, 26, 33, 34, 35, 36, 37, 39, 43, 44, 45, 46, 47\}$$ $$ \bar{S}= \{5, 9, 13, 17, 22, 23, 24, 25, 26, 33, 34, 37, 43, 44, 45, 46, 47\}$$
• For $l=6$: $|S \setminus \bar{S}|=15 < |\bar{S}|=16$ $$ S= \{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\}$$ $$ \bar{S}= \{6, 12, 13, 18, 19, 20, 24, 25, 26, 27, 30, 31, 32, 33, 34, 36\}$$
• For $l=7$: $|S \setminus \bar{S}|=78 < |\bar{S}|=79$ , $\max(S)=239$
• For $l=8$: $|S \setminus \bar{S}|=109 < |\bar{S}|=110$ , $\max(S)=335$
• For $l=9$: $|S \setminus \bar{S}|=213 < |\bar{S}|=214$ , $\max(S)=633$
• For $l=10$: $|S \setminus \bar{S}|=45 < |\bar{S}|=46$ , $\max(S)=100$

As the sets become rather large I left out the lasts few examples. These are the first sets I encountered in the following procedure.

We start for the chosen value of $l$ with the set $S=\{1,2,\dots,l-1\}$ which does not contain an arithmetic sequence of length $l$. (Optional $\bar{S}=\{l-1\}$). We also use an index $n=l$. Now we can use the following algorithm:

1. Add $n$ to the set $S$

2. Check wether there is any arithmetic sequence of length $l$ in $S$ that ends in $n$. If that is the case we remove $n$ from $S$, if not we have a new set that does not contain any arithmetic sequences of length $l$ or longer.

3. Optional: If $n$ was accepted we can check whether there is any arithmetic sequence of length $l-1$ in $S$ that ends in $n$. If that is so, we add $n$ to $\bar{S}$.

4. Increase $n$ by one and go back to step 1.

After that it is only repeating until the number of elements in $\bar{S}$ exceeds half the size of $S$.

I have not tried to prove the existence of such a set for any value of $l$, but I see no obvious reason why they would seize to exist for larger values of $l$. It should also be noted that there might very well be sets with the required properties that are smaller in size and of which the largest element in $S$ is less than the algorithm above gives.

It is, however, possible to construct a set for any value of $l$ in a systematic fashion. Hereto we start with the following sets: $$S_0 = {1}$$ $$\bar{S}_0 = \emptyset$$ and apply the following iterative scheme: $$S_{n+1} = \cup_{k=0}^{l-1} \left[ S_n + k \Delta_n \right]$$ $$S_{n+1} = \cup_{k=0}^{l-2} \left[ \bar{S}_n + k \Delta_n \right] \cup \left[S_n + (l-1) \Delta_n\right]$$ where $\Delta_n$ is not unique but should be large enough to avoid any problems with generating additional sequences. It is sufficient to choose $\Delta_n \geq 2 \max(S_{n-1})-1$.

We find that $$|S_n| = l^n$$ $$|\bar{S}_n| = l^n - (l-1)^n$$ and if we choose $$\Delta_n = (2l-1)^{n-1}$$ the largest element in $S_n$ is given by $$\max(S_n) = \frac{(2 l-1)^n +1}{2}$$.

From this it follows that for $|S_n\setminus \bar{S}_n| < |\bar{S}_n|$ we require $(l-1)^n < l^n - (l-1)^n$, which means $$n>- \frac{\ln 2}{\ln(1- \frac{1}{l})}$$.

For the case $l=3$ we would obtain the set $$S=\{1,2,3,~~6,7,8,~~11,12,13\}$$ and for $l=4$ we get $$S=\left\{\begin{array}{llll} 1,2,3,4, & 8,9,10,11, & 15,16,17,18, & 22,23,24,25,\\ 50,51,52,53, & 57,58,59,60,& 64,65,66,67, & 71,72,73,74,\\ 99,100,101,102,&106,107,108,109,&113,114,115,116,& 120,121,122,123,\\ 148,149,150,151,&155,156,157,158,&162,163,164,165,& 169,170,171,172 \end{array} \right\}$$.

And finally, we get that $$\frac{|\bar{S}_n|}{|S_n|} = 1 - \left( 1 - \frac{1}{l}\right)^n$$ and hence $$\lim_{n\rightarrow \infty} \frac{|\bar{S}_n|}{|S_n|} = 1.$$