4
$\begingroup$

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 MathStackExchange

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ let $r_3(N)$ denote the maximal cardinality of a salem-spencer subset of $\{1,\dots,N\}$. clearly $2^{r_3(N)}$ is a lower bound for your question. meanwhile, by container method shenanigans, I believe it is known that $C_\epsilon 2^{(1+\epsilon)r_3(N)}$ is an upper bound. $\endgroup$
    – Zach Hunter
    Commented Feb 18 at 12:10
  • 1
    $\begingroup$ @ZachHunter can you please share the reference in which you found the upper bounds... $\endgroup$
    – Sayan Dutta
    Commented Feb 20 at 14:30

2 Answers 2

Reset to default
4
$\begingroup$

Let $r_3(N)$ denote the maximum cardinality of a $3$-AP subset of $\{1,\dots,N\}$. It clear that $T(N)\ge 2^{r_3(N)}$.

Meanwhile, it was proved by Balogh, Liu, and Sharifzadeh that we have $T(N) \le 2^{C r_3(N)}$ for some constant $C$ link. The proof uses the hypergraph container method; it is my understanding is that when there are extremal constructions that "outperform the deletion method" (i.e., beat the naive probabilistic construction), then such a result should always hold.

Originally, I thought that the '$C$' could be taken to be '$1+\epsilon$', but apparently this is too optimistic for various related counting problems (I thank Rajko Nenadov for explaining this to me).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the answer (+1)! $\endgroup$
    – Sayan Dutta
    Commented Mar 11 at 17:33
3
$\begingroup$

Fix a smallish integer $m$, and assume for simplicity that $n$ is a multiple of $m$. Break $\{1,\dots,n\}$ into $n/m$ consecutive intervals of $m$ consecutive integers each. Each such interval must itself be a Salem–Spencer set. So if we let $f(m)$ be the number of Salem–Spencer subsets of $\{1,\dots,m\}$, the number of Salem–Spencer subsets of $\{1,\dots,n\}$ will be at most $f(m)^{n/m} = \bigl( f(m)^{1/m} \bigr)^n$.

The first $40$ values of $f(m)$ are listed in the OEIS sequence entry, and $f(m)^{1/m}$ is observed to decrease. Even taking $m=7$ yields the bound $\bigl( f(7)^{1/7} \bigr)^n = \bigl( 65^{1/7} \bigr)^n \approx 1.81546^n$, which is already better than the tribonacci bound. Taking $m=40$ (the last entry listed) yields the upper bound $$ \bigl( f(40)^{1/40} \bigr)^n = \bigl( 27{,}893{,}419^{1/40} \bigr)^n \approx 1.5351^n $$ for the number of Salem–Spencer subsets of $\{1,\dots,n\}$ (at least when $n$ is a multiple of $40$, but making this more general will lose only a constant factor in front of the exponential bound).

Improve this answer
$\endgroup$
7
  • $\begingroup$ Nice observation (+1)! $\endgroup$
    – Sayan Dutta
    Commented Feb 19 at 8:57
  • $\begingroup$ Btw, since you wrote that $f(m)^{1/m}$ is observed to decrease, the reason is as you yourself pointed out, $f(n)\le f(m)^{n/m}\implies f(n)^{1/n}\le f(m)^{1/m}$ $\endgroup$
    – Sayan Dutta
    Commented Feb 19 at 9:03
  • 2
    $\begingroup$ $f(n)^{1/n}$ goes to 1 by Roth theorem $\endgroup$
    – Fedor Petrov
    Commented Feb 19 at 9:11
  • 2
    $\begingroup$ @SayanDutta The given argument shows only that $f(n)^{1/n} \le f(m)^{1/m}$ when $n$ is a multiple of $m$. $\endgroup$
    – Sean Eberhard
    Commented Feb 19 at 9:33
  • 4
    $\begingroup$ The size of any such set is $o(n)$, thus the number of such sets is $\sum_{k=0}^{o(n)}{n\choose k}=e^{o(n)}$. $\endgroup$
    – Fedor Petrov
    Commented Feb 19 at 10:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .