Erd?s Conjecture – Status of Weak Version on Arithmetic Progressions

arithmetic-progressionsdivergent-serieserdos-conjectureopen-problempigeonhole-principle

This question is motivated by Erdős conjecture on arithmetic progressions. It is a weaker version of Erdős Conjecture, but I do not know how to prove it.

Erdős conjecture on arithmetic progressions states that, "If $A$ is a large set, then $A$ contains arithmetic progressions of every length."

The following conjecture states that, "If $A$ is a large set, then $A$ contains quasi-arithmetic progressions of every length."

If $A\subset \mathbb{N}$ is a large set in the sense that

$$ \sum_{n\in A} \frac{1}{n} = \infty,$$

then for every $k\in\mathbb{N},$ there exists $r,s\in\mathbb{R}_{\geq 1},\ $ and $\ \lbrace{a_1, a_2,\ldots, a_k\rbrace} \subset A,\ $ such that

$$ a_j \in [r + (j-1)s, r + js ] \quad \forall\ j\in \lbrace{1,\ldots, k\rbrace}. $$

Best Answer

Here is a short proof of this result. Suppose $A$ does not satisfy the conclusion of the theorem for some $k$.

Claim: for every interval $I$ of length $k^s$, the cardinality of $A \cap I$ is at most $(k - 1)^s$.

Proof: Induction on $s$. The base case $s = 1$ is trivial. For the induction step, let $I = [r, r + k^s)$ and $I_i = [r + i k^{s - 1}, r + (i + 1) k^{s - 1})$. By the assumption, one of $I_0, \cdots, I_{k - 1}$ does not contain any $A$. Now use induction hypothesis on the rest of the $I_i$'s. $\square$

Now note that $$\sum_{a \in A} \frac{1}{a} = \sum_i \sum_{a \in A \cap [k^{i - 1}, k^i)} \frac{1}{a} \leq \sum_i \frac{(k - 1)^i}{k^{i - 1}} < \infty.$$