Number of Salem–Spencer subsets of $\{1,2,3,\dots ,n\}$

Question

I was wondering about sets that do not contain any $3$-term AP, and came to know that the official name of such a set is Salem–Spencer set. I was considering the question of counting the number of Salem–Spencer subsets of $\{1,2,3,\dots ,n\}$ for a given $n$. This is listed in OEIS A051013.

However, neither on OEIS, nor on anywhere else could I find any literature dealing with the specific question at hand. So, my question is whether anyone knows of any formula (recursive or otherwise) for the number of Salem–Spencer subsets of $\{1,2,3,\dots ,n\}$ for a given $n$.

I tried my hand at a recursion technique and tried to use the fact that such a set either ends with $n$ or it doesn't. So, we have $$T(n)=T(n-1) + S(n)$$ where $T(n)$ is the number of Salem–Spencer subsets of $\{1,2,3,\dots ,n\}$ and $S(n)$ is the number of Salem–Spencer subsets of $\{1,2,3,\dots ,n\}$ containing $n$.

These $S(n)$'s are listed in OEIS A334893 (with the specific cases listed in OEIS A334892) but there's no formula for these to be seen.

Even if an exact result is not available, I would like to know whether it is possible to get any asymptotic results or even any useful bounds$^{*}$. Even references which may be helpful are welcome.

$[^*]$ A set that avoids a $3$-AP is also a set that avoids three consecutive numbers, which is known to be the Tribonacci numbers. So, the term useful bounds is to be read as bounds better than this.

Also posted on MathOverflow

Answer 1

Let $r_3(n)$ be the maximum size of a Salem-Spencer set of $[n]$. Then the number $N$ of Salem-Spencer set of $[n]$is trivially bounded by $$2^{r_3(n)}\leq N \leq \sum_{k=1}^{r_3(n)} \binom{n}{k} \leq n^{r_3(n)}.$$ The lower bound is because any subset of a Salem-Spencer set is Salem-Spencer, so there are at least $2^{r_3(n)}$ such sets. The upper bounds is because any Salem-Spencer set has size at most $r_3(n)$.

In other words, we have $$r_3(n) \ll \log_2 N \ll r_3(n) \log n.$$ With our current knowledge of $r_3(n)$, I think we cannot do much better. Indeed, the SOTA (state-of-the-art) bound for $r_3(n)$ is something like $$\frac{n}{2^{c\log^{1/9} n}} \geq_{\text{Kelley-Meka-Bloom-Sisask}} r_3(n) \geq_{\text{Behrend}} \frac{n}{2^{c\log^{1/2} n}}.$$ where $c$ denotes some positive constant. Note that the lower and upper bounds are much further than a factor of $\log n$ apart! Thus, the best we can write down, without a major breakthrough on $r_3(n)$, is something like $$\frac{n}{2^{c\log^{1/9} n}} \geq \log_2 N \geq \frac{n}{2^{c\log^{1/2} n}}$$ (I absorbed the $\log n$ into the denominator.)

For example, if you manage to prove something like $$\log_2 N \geq \frac{n}{2^{c\log^{1/3} n}}$$ then this would immediately imply (with a different constant $c$) $$r_3(n) \geq \frac{n}{2^{c\log^{1/3} n}}$$ which would probably net you a paper in the Annals :-)

Here is a list of results referenced:

Behrend's lower bound can be found in any standard textbook discussing Roth's theorem. See e.g. here or here.

Kelley-Meka's paper. (Proves $\frac{n}{2^{c\log^{1/11} n}} \geq r_3(n)$. not published, but all experts agree it is correct.)

Bloom-Sisask's improvement. (not published. Replace $1/11$ with $1/9$.)