An arithmetic-progression-free subset with more than 256 elements of $\{0,1,2,...,3^8-1\}$

Question

We say that a set $ A \subset \mathbb{R}$ with $|A|\geq 3$ is free if for every $a, b, c \in A$, $a\neq b$ we have $a+ b \neq 2c$.

Show that $\{0, 1, 2, \ldots , 3^8 − 1\}$ contains a free subset with more than $256$ elements.

I tried to use a greedy algorithm but I didn't have a clear idea.

Answer 1

A free subset of 256 Cantor numbers

The hints are in the problem statement. "$256=2^8$ cannot be a coincidence ". Moreover, the given numbers are the first consecutive $3^8$ natural numbers.

Let us consider an integral variant of "Cantor numbers", numbers that have only $0$ or $1$ when they are represented in base $3$, i.e. there are no $2$. More formally, let $$ A=\left\{\sum_{i=0}^7a_i3^i\mid a_i\in\{0,1\}\right\}.$$

Suppose $a,b,c\in A$, $a+b=2c$. Consider the equality in base $3$. Since each digit of $a$ or $b$ or $c$ is at most $1$, there is no carry in the addition of $a+b$ nor in the multiplication of $2c$. Hence the equality holds at each place.

• If $c$ is $0$ at some place, then both $a$ and $b$ must be $0$ at the same place.
• If $c$ is $1$ at some place, then both $a$ and $b$ must be $1$ at the same place.

Hence $a=b=c$. That means $A$ is a free set.

By the way, $A$ is what you will find by the greedy algorithm, as also described in Mike Earnest's answer.

One more number

$|A|=2^8$, since there are $2$ options for each $a_i$. This just falls short of the requirement "more than $256$", however.

Let us tweak a bit at the large end of $A$ to make a bigger set.

Consider $$ B=(A\setminus\{(11111111)_3\})\cup\{(22222221)_3, (22222222)_3\}.$$ $|B|=|A|-1+2=2^8+1>256$.

Suppose $a,b,c\in B$, $a+b=2c$. Since $A$ is free, (at least) one of $a,b,c$ must be in $\{(22222221)_3,(22222222)_3\}$.

• It is $c$.
  Then $a=2c-b$ $\ge2\times (22222221)_3 -(22222222)_3$ $=(22222220)_3$. Since the biggest element in $A$ is $(11111111)_3$, $a\in\{(22222221)_3, (22222222)_3\}$. By symmetry, so is $b$. So is $c$. Hence $a=b=c$.
• It is not $c$.
  WOLG, let it be $a$. Since $c$ is at most $(11111110)_3$ and $a$ is at least $(22222221)_3$, we have $2c<a\le a+b$. This contradicts with $a+b=2c$.

Hence $B$ is free. Our proof is complete.

A free subset of 320 numbers

Here is a free subset of $320$ numbers.

$$ C=E\cup\ F$$ where $E=\{3^6\ell+d \mid \ell\in\{0,1,3\}, d\in D\}$,
$F=\{3^8-1-3^6\ell-d \mid \ell\in\{0,1\}, d\in D\}$,
$\displaystyle{ D=\left\{\sum_{i=0}^5a_i3^i\mid a_i\in\{0,1\}\right\}}$.

$C$ looks like $\{0, 1, 3, 4, 9, 10, 12, 13,$ $27, 28, \cdots, 3^8-10,$ $3^8-5, 3^8-4, 3^8-2, 3^8-1\}.$

$C$ can be obtained by bidirectional greedy selection, alternating between going forwards from $0$ and going backwards from $3^8-1$. This algorithm/construction can be generalized when the exponent $8$ is replaced by any integer $\ge3$.

$|C|=|D|\times(3+2)=2^6\times5=320$
$\displaystyle{ E\subset\left\{\sum_{i=0}^7a_i3^i\mid a_i\in\{0,1\}\right\}}$ is free.
$F=3^8-1-\displaystyle{\left\{\sum_{i=0}^6a_i3^i\mid a_i\in\{0,1\}\right\}}$ is free.
Let $m_E=0$ be the smallest element in $E$ and $M_E=(10111111)_3$ the biggest element.
Let $m_F=3^8-(1111111)_3$ be the smallest element in $F$ and $M_F=3^8-1$ the biggest element.
We have $2M_E<m_E+m_F \le a +b \le M_E+M_F < 2m_F$ for any $a\in E$, $b\in F$.
Hence $C$ is free.

Answer 2

The greedy algorithm works well. Proceed down the natural numbers in the order $0,1,2,\dots$, and include every element that does not cause a three-term arithmetic progression with two earlier elements. For example, you include $0$, then you include $1$, but you exclude $2$, because $0-1-2$ is a three-term AP. You then include $3$, include $4$, exclude $5$ because of $1-3-5$, exclude $6$ because of $0-3-6$, and so on. It is not too much work; for example, in order to check whether $32$ can be added, you just need to check $16$ previous pairs. That is, you can add $32$ as long as $(30,31)$ are not both present, and same for $(28,30),(26,29)$, and so on down to $(0,16)$.

Here is the result:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
^ ^ x ^ ^ x x x x ^ ^  x  ^  ^  x  x  x  x  x  x  x  

21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
x  x  x  x  x  x  ^  ^  x  ^  ^  x  x  x  x  ^  ^

Of course, you cannot use the greedy approach to get all the way up to $3^8-1$, but fortunately by now, a pattern has started to emerge. All of the included entries come in pairs. Furthermore, these pairs themselves come in pairs, separated by a single x. Then, these pairs-of-pairs themselves come in pairs, separated by four x's. For example, the sequence from $0$ to $4$ is an exact repeat of the sequence from $9$ to $13$. The longer you go, the more patterns you can find like this; the next example is that the sequence from $0$ to $13$ is an exact repeat of the sequence from $27$ to $37$. After staring at these repeats for long enough, you can see how related they are to powers of $3$, and then start to guess how to describe the general pattern.

I hope that this is enough for you to get started. It is a really beautiful pattern, so I want to give you the chance to discover it for yourself.