Has this weak version of Erdős Conjecture on arithmetic progressions been proven, or is it still an open problem?

204 Views Asked by At

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}. $$

1

There are 1 best solutions below

0
On 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.$$