I'm trying to find a subset $\ A\ $ of $\ \mathbb{N}\ $ that disproves Erdős Conjecture on Arithmetic progressions.
If we instead write $\ A\ $ as a (strictly) increasing sequence of integers, $\ (x_n)_n.\ $ My question is, has it been proven that, if $\ y_n = x_{n+1} – x_n\ $ is non-decreasing, then $\ x_n\ $ cannot be a counter-example to Erdős Conjecture? In particular, I was thinking about such sequences with the further property that there are infinitely many $\ n\in\mathbb{N}\ $ such that $\ x_n \geq 2 x_{n-1},\ $ because then at least we can be sure that these $\ x_n\ $ do not make arithmetic progressions of length three with any two $\ x_{k_1},\ x_{k_2} \ $ if $\ k_1,k_2 < n.$
I cannot think of how to disprove that such sequences (with or without the further property) can be both a "large set", and also have a maximum length arithmetic progression, but maybe there is a relatively simple proof, possibly using the pigeonhole principle, or maybe this hasn't been proven yet?
Best Answer
If $y_n$ is increasing, $y_n\geq n+y_0$ for all $n$, so $x_n\geq \frac{n(n-1)}{2}+ny_0 + x_0$.
$x_n$ is of quadratic growth, so the sum of reciprocals converges, thus it can't be a counter-example.
If $y_n$ is only non-decreasing, we need to have a constant $c$ that bounds the number of consecutive identical values, otherwise, we would get arbitrarily long constant sequences of $y$ values, so arbitrarily long arithmetic progressions of $x$ values.
We have: $$x_{n+c} = \sum_{k=0}^{c-1} y_{n+k} + x_n \geq cy_{n} + x_n$$
Let $w_n = x_{cn}$.
$$w_{n+1} = x_{cn+c} \geq cy_{cn} + x_{cn} = cy_{cn} + w_n$$
But $y_{cn}$ must be strictly increasing, so we get that the sum of the reciprocals of $(x_{cn})_n$ is converging.
We have: $$\sum_{n=0}^{+\infty} \frac{1}{x_n} \leq \sum_{n=0}^{+\infty} \frac{1}{x_{c\left\lceil \frac{n}{c} \right\rceil}} = c\sum_{k=1}^{+\infty}\frac{1}{x_{ck}}$$ Hence the convergence.