A reformulation of Erdős conjecture on arithmetic progressions

Question

Erdős conjecture on arithmetic progressions states that if $S$ is a set of positive integers such that $c(S):=\sum_{n \in S} \frac{1}{n} = \infty$ (large set), then $ \forall \ell \ge 3$ the set $S$ contains an arithmetic progression of length $\ell$. In other words, this conjecture states that for all set $S$ of positive integers, if $\exists \ell \ge 3$ such that $S$ contains no arithmetic progression of length $\ell$, then $c(S) < \infty$.

Let $\ell \ge 3$ and $S_{\ell}$ be the lexicographically earliest (strictly) increasing sequence of positive integers that contains no arithmetic progression of length $\ell$. We identify $S_{\ell}$ with its set of terms. According to Erdős conjecture, we should have $c_{\ell}:=c(S_{\ell}) < \infty$. But intuitively, $S_{\ell}$ is the worst set with no arithmetic progression of length $\ell$ to deal with Erdős conjecture. This leads to:

Main Question: Is Erdős conjecture equivalent to $c_{\ell} < \infty$ for all $\ell \ge 3$?

Let $\ell \ge 3$ and $S$ be a set of positive integers with no arithmetic progression of length $\ell$.

Stronger Question 1: Is it true that $c(S) \le c_{\ell}$?
Answer: No, see the comment of Andrés E. Caicedo citing this paper of J. Wróblewski (see below).

Stronger Question 2: Is it true that $c(S) < c_{\ell}$ or $c(S) \sim c_{\ell}$?

---

Note that OEIS includes the sequences $S_{\ell}$ for all $\ell \in \{3,4,\dots,10 \}$:

• $S_3$: $1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, \dots$ (A003278)
• $S_4$: $ 1, 2, 3, 5, 6, 8, 9, 10, 15, 16, 17, 19, 26, 27, 29, 30, \dots$ (A005837)
  $\vdots$
• $S_{10}$: $1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, \dots$ (A020664)

Ralf Stephan put the following formula in A003278:
If $S_3(n)=b(n+1)$ then $b(0)=1$, $b(2n)=3b(n)-2$ and $b(2n+1)=3b(n)-1$.
It follows that $S_3(n)$ grows like $n^{\alpha}$ with $\alpha:=\frac{\log(3)}{\log(2)}$, so that $c_3<\infty$.

Moreover, $c_3 = \sum_{n=1}^{N}S_3(n)^{-1}+ O(N^{1-\alpha})$. We computed (after the comment of Bullet51) $∑_{n=1}^{10^8}S_3(n) = 3.007886\dots$, whereas $10^{8(1-\alpha)} = 0.0000209\dots$.
Now, Wróblewski's paper states that $ 3.00793<c_3<3.00794.$

Bonus Question: What is the exact value of $c_3$?

We also computed (using OEIS b-files) $\sum_{n=1}^{10^5}S_4(n)^{-1} = 4.1911..$, $\sum_{n=1}^{10^5}S_{10}(n)^{-1} = 7.7326..$, but we don't know how good they are as approximations of $c_4$ and $c_{10}$ respectively.

Bonus Question ${\ell}$: What is a good approximation and/or the exact value of $c_{\ell}$?

The above recursive formula for $S_3(n)$ matches with its graph of "Cantor flavor". Now for $\ell >3$, the graph seems to lose this flavor (see here), so that we can no more expect such a recursive formula.

Question of Sylvain Julien: Is $c_{\ell}$ an increasing function of $\ell$?
More strongly: Is it true that $ℓ≤ℓ′$ implies $S_ℓ(n)≥S_{ℓ′}(n)$ for all $n≥1$?

---

Wróblewski's paper provides a set $S$ of positive integers with no arithmetic progression of length $3$ and with $c(S)>3.00849$. That's why the answer to Stronger Question 1 is no, but the Stronger Question 2 and Main Question are still open (to me).

Let $\mathcal{A}_{\ell}$ be the set of sets of positive integers with no arithmetic progression of length $\ell$, and let $a_{\ell}:=\sup_{S \in \mathcal{A}_{\ell}}(c(S))$. Now my belief is that $a_{\ell} < \infty$, that $a_{\ell} \sim c_{\ell}$, but also that there is no $S \in \mathcal{A}_{\ell}$ with $c(S) = a_{\ell}$. I believe that a proof of $a_3<\infty$ should be hard but reachable, on the other side, I believe that the exact value of $a_3$ or even a good approximation (with say 10 digits) is not reachable with the current knowledge/technics. What could be reachable is to break records, starting by the above old record (July 1984) of Wróblewski.

Is Wróblewski's record broken today? If yes:
What is the largest $c(S)$ known today, with $S \in \mathcal{A}_3$? (same question for every fixed $\ell > 3$)

Thomas' answer suggests a set $S$ of Moser (1953), but we don't even know if $c(S)>c_3$.

Answer 1

This question is basically asking how good greedy-type constructions of sets without long arithmetic progressions can be. The answer is actually pretty terrible.

Firstly, as you note, if $f_k(n)$ is the number of elements of your $S_k$ sequence $\leq n$ then one can show that $f_k(n) \ll n^{a_k}$ for some constant $a_k<1$. It follows that $c_k <\infty$ for all $k\geq 3$.

This does not really help with the Erdős conjecture since, contrary to your intuition, these are definitely not the 'worst' sets to deal with.

Salem and Spencer were the first to construct very large sets without arithmetic progressions -- for any $n$ they construct $A\subset \{1,\ldots,n\}$ without a $3$ term arithmetic progression of size $n^{1-o(1)}$. This was later improved by Behrend who had a different construction which gives

$$ \lvert A\rvert \geq \exp(-O(\sqrt{\log n})) n.$$

Note that still $\sum_{n\in A}\frac{1}{n}<\infty$, which we expect, but it grows much faster than any of the $c_\ell$ you mention.

Over 70 years later, this construction of Behrend remains the best known (although there have been slight improvements by Elkin and Green-Wolf, they do not affect the shape of the bound above).

Rankin generalised Behrend's construction to longer arithmetic progressions.

One may object that this is not constructing an infinite sequence (since the construction of $A$ depends on $n$). Fortunately, there is a construction of Moser of an infinite sequence with a similar growth rate to Behrend's sequence.

So to answer your questions - yes, they are equivalent in that they're both true, but $c_\ell <\infty$ is known, and doesn't really shed any light on the Erdős conjecture since the sequences you mention are far from the worst case.

(NB - the Behrend construction is so elegant it must be described here - note that the points on a high-dimensional sphere can't contain a three-term arithmetic progression since any line intersects in at most 2 points. Take some high-dimensional sphere with many integer points, then project down into one-dimension in a way thay doesn't create any new progressions).

Answer 2

I asked Prof. Jaroslaw Wróblewski by email, below is his answer (reproduced with his authorization):

I do not know of any new results regarding searching a set $B$ in $\mathcal{A}_3$ [the set of sets of positive integers with no arithmetic progression of length $3$] with large $c(B)$. However since I wasn't interested in the subject for years, I may not be a good source of information. I am sure however, that such a set can be constructed easily with help of nowadays computers - my 35 year old construction was made virtually by hand and a limited access to a computer was used only to get a good estimate of the sum of reciprocals.

I have been collecting results regarding large (i.e. having many elements) non-avereging finite sets and the best results known to me are here: http://www.math.uni.wroc.pl/~jwr/non-ave.htm

As for $a_3$ [$:=\sup_{S \in \mathcal{A}_{3}}(c(S))$], I am afraid it is impossible to have an educated guess on that. Note that Szekeres's sequence seems to be the best possible before you see a construction which can improve it. So I may give only my speculations which have value of tea leaves reading:

1. I feel that most likely $a_3$ is finite, but only slightly larger than $3$.

2. Less likely, but reasonable is that $a_3 = \infty$.

3. I feel that it is rather unlikely that $a_3$ is finite, but significantly larger than $3$. The reason for that is the following: Szekeres's sequence is the best one for a quite long run. There are sets that are better, but they are better far away (on large numbers). If they give finite sum of reciprocals, then this is sum of reciprocals of large numbers, so it is likely to be very small (assuming it is finite) - most accidental sets of large numbers have small or infinite sum of reciprocals - a set of large numbers with large but finite sum of reciprocals can be easily constructed (must have a very specific density of terms), but is rather unlikely to appear accidentally as a set arising in a problem not direcly related to such a sum.