Define the size, possibly $\infty$, of a set $S\subseteq \mathbb{N}$ as $|S|=\sum\limits_{n\in S} \frac{1}{n}$. Then the Erdős-Turan conjecture states that if $|S|=\infty$, S must contain arbitrarily long APs (arithmetic progressions).

Q1: has anyone conjectured that for each $k>0$ there must be a finite constant $c_k$ such that: $S$ is $k$-free $\implies |S|\le c_k$? ($k$-free meaning that $S$ is free from APs of length $k$.) Related: Q6 below.

Q2: if so are there explicit (and somewhat tight) formulas for $c_k$? A plausible one to me would appear $c_k=k\log(k)$.

Q3: currently, are the largest known $k$-free sets the greedy ones? I'd be very curious to see a counterexample here! Some greedy sets are in OEIS:

k=3: A003278, size $\approx 3.007938999898936$

k=4: A005837, size $\approx 4.285$

k=5: A020655, size $\approx 7.8723048$

k=7: A020658, size $\approx 13.497609$

Q4 & Q5: if $k$ is prime, the greedy $k$-free set mentioned above is very easily proved to be $1+\{n\in \mathbb{N}_0 \mid \text{the base-} k \text{ expansion of } n \text{ does not contain the digit } k-1\}$. Is there any description of the sets, even partial, when $k$ is not prime? (In particular for $k=4$, which already seems to be quite impenetrable.) Is there a formula for the sizes, in terms of well known constants and functions, at least when $k$ is prime? Euristically I observed that for prime $k$, the sizes approach $k\log(k)$ (from below?) as $k \rightarrow\infty$.

Q6: the OEIS page for $k=3$ (A003278) links to this paper claiming to settle Q1 for $k=3$. I couldn't follow it, but I notice that the result is not mentioned in the Wikipedia article, nor in this slightly later paper by Thomas F. Bloom... So is the former paper not correct, or even not to be taken seriously? (By the way, a first edition of Newman's Analytic number theory, referred to therein, is freely available on the Internet Archive Library.)

  • 1
    $\begingroup$ I think that in your Q1, you mean for the implication to go the other way. Otherwise it's too easy: of course for any $k$, there are sets of arbitrarily small "size" containing length-$k$ progressions: for example, there are lots of length-$4$ progressions in the set $[10^6,10^6+3] \cup [10^{12},10^{12}+3] \cup \dots$. $\endgroup$ – Will Brian Apr 12 '18 at 13:13
  • 2
    $\begingroup$ Tim Gowers's answer here seems relevant: mathoverflow.net/questions/13230/… $\endgroup$ – Will Brian Apr 12 '18 at 13:18
  • $\begingroup$ @WillBrian: you are absolutely right! $\endgroup$ – Yaakov Baruch Apr 12 '18 at 13:31
  • $\begingroup$ @WillBrian: thank you for the pointer to Gower's sensible point. Even though it doesn't answer my question it does manage to reduce the "gap" between problem and solution in a way, by making my question definitely less interesting. $\endgroup$ – Yaakov Baruch Apr 12 '18 at 13:43
  • $\begingroup$ ... Gowers's... $\endgroup$ – Yaakov Baruch Apr 12 '18 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.