5
$\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$
5
  • $\begingroup$ Your first question is not clear, or you missed something. By construction that sequence is maximal in that sense. $\endgroup$
    – ReverseFlowControl
    Commented Jul 3, 2016 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
    Commented Jul 3, 2016 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$
    – ReverseFlowControl
    Commented Jul 5, 2016 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
    Commented Jul 5, 2016 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$
    – ReverseFlowControl
    Commented Jul 6, 2016 at 2:25

1 Answer 1

Reset to default
4
$\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.

$\endgroup$
7
  • 3
    $\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
    Commented Jul 3, 2016 at 17:02
  • $\begingroup$ @ErickWong: (+1) to your insightful comment :) $\endgroup$
    – Jack D'Aurizio
    Commented Jul 3, 2016 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
    Commented Jul 4, 2016 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
    Commented Jul 9, 2016 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$
    – RSpeciel
    Commented Aug 10, 2018 at 4:59

You must log in to answer this question.

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