3
$\begingroup$

A conjecture by Erdos states that if a sequence $(a_n)$ of natural numbers is "big" in the sense that $$\sum_{n\in \Bbb{N}}\frac{1}{a_n} = \infty$$ then $(a_n)$ contains arithmetric progressions of arbitrarily large lengths. Contrapositively, this is to say that for all $k\in \Bbb{N}$, if $(a_n)$ avoids any arithmetic progressions of length $k$, then its sum of reciprocals is finite. This conjecture is unsolved even for $k = 3$.

If one wanted to create a sequence that "maximizes" its sum of reciprocals while avoiding APs of length $3$, one naive approach would be to start the sequence with $1$, then have each subsequent term be the smallest number that does not create an AP of length three with the previous terms. This sequence is OEIS 3278.

My questions are as follows: are there any sequences (that we know of) which avoid APs of length three while having a larger sum of reciprocals than OEIS 3278? And do we know of any such sequence which grows more slowly (asymptotically speaking) than OEIS 3278? Thank you.

$\endgroup$
  • $\begingroup$ Your first question is not clear, or you missed something. By construction that sequence is maximal in that sense. $\endgroup$ – ReverseFlow Jul 3 '16 at 12:42
  • 1
    $\begingroup$ @ReverseFlow If that were the case, since the sequence's sum of reciprocals converges, then the conjecture would be solved for $k=3$ (and a similar proof would be simple for all other $k$), which it is not. $\endgroup$ – florence Jul 3 '16 at 12:45
  • $\begingroup$ What are the limitations on the sequence? For example, are $\{1,2,4,3,20\}$ and $\{1, 3, 2, 4, 20\}$ considered sequences with no AP of length 3? $\endgroup$ – ReverseFlow Jul 5 '16 at 0:41
  • $\begingroup$ @ReverseFlow Neither of those would count. Really, it would've been clearer if I phrased this in terms of sets of natural numbers. $\endgroup$ – florence Jul 5 '16 at 0:44
  • $\begingroup$ In writing a proof to answer your first question in the negative I found one sequence which answers it in the positive. Namely, just take sequence OEIS 3278 and move every number at index $k$ to index $2k$ and copy the same value at index $2k+1$. Every element repeats once, it is still avoids AP3 and the sum is double the previous one. Assuming $k$ starts at $0$. $\endgroup$ – ReverseFlow Jul 6 '16 at 2:25
2
$\begingroup$

I think the answer is affirmative. Erdos and Turan showed in $1936$ that an integer Cantor set (that gives our Szekeres' sequence) is free of $3$-AP, but later ($1946$) Behrend, Salem and Spencer showed that there is a much "denser" subset of $\mathbb{N}$ with the same property, and Behrend's construction was further refined by Elkin in $2008$. This survey of Ben Green and Julia Wolf is a nice reference.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ One should be careful to note that the two notions of density are not exactly equivalent. The reciprocal sum is heavily biased towards the inclusion of small values, which favours greedy algorithms more than natural density does. As an admittedly crude analogy, in the case of primitive sets (where no integer divides another), the densest subset of $[1,2N]$ is $[N+1,2N]$ but this is far from giving the best reciprocal sum (the greedy algorithm gives the set of primes). $\endgroup$ – Erick Wong Jul 3 '16 at 17:02
  • $\begingroup$ @ErickWong: (+1) to your insightful comment :) $\endgroup$ – Jack D'Aurizio Jul 3 '16 at 17:03
  • 1
    $\begingroup$ Thank you very much. So this partially settles my second question; the paper showed that given a natural number $N$, there is a subset of ${1,...,N}$. which is 3-AP avoiding and (generally) has greater density than the Szekere sequence. Does it therefore follow that there is an infinite set of natural numbers which grows more slowly than the Szekere sequence? $\endgroup$ – florence Jul 4 '16 at 2:23
  • 1
    $\begingroup$ @florence Yes, the key is that given a construction such as Behrend's which achieves $f(N)$ elements, you can take an arbitrary subset of $\{1,\ldots,N\}$ which avoids 3-APs and extend it to a subset of $\{1,\ldots,3N\}$ that has $f(N)$ additional elements (by choosing them from $[2N+1,3N]$ which doesn't interact with $[1,N]$). In this way one can go from a finite construction to an infinite sequence while only losing a constant factor of density. $\endgroup$ – Erick Wong Jul 9 '16 at 0:13
  • $\begingroup$ @ErickWong I find this question, and both your comments very interesting, hopefully this wasn't too long ago! First, while Behrend's construction may ensure a higher natural density than the greedy algorithm, does that answer OP's first question? In other words, does that construction (or any other) have a higher sum of reciprocals than greedy? Second, in your first comment you state that "the greedy algorithm gives the set of primes"... what is meant by that? $\endgroup$ – Romain S Aug 10 '18 at 4:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.