Convergent sub-sequences of reciprocals of large sets using greedy algorithm.

Question

Let $A\subset\mathbb{N} $ be large, that is $\displaystyle\sum_{n\in A} \frac{1}{n}\ $ diverges. Write $\ A = \{ a_1, a_2, a_3, \ldots \};\ a_1 < a_2 < a_3 < \ldots. $

Let $x\in\mathbb{R}_{>0},$ and define:

• $a_1(x)$ to be the least positive member of $A$ such that $\displaystyle \frac{1}{a_1(x)} < x.$
• For each $n\geq 1, $ let $a_n(x)$ be the least positive member of $A$ greater than $a_{n-1}(x)$ such that $\displaystyle\sum_{k=1}^{n} \frac{1}{a_k(x)} < x. $ (greedy algorithm).

Prove or disprove: $\exists\ N\in\mathbb{N}$ such that $a_N(x) \geq a_{N-1}(x)(a_{N-1}(x)-1) + 1.$

Or does there exist an $x>0$ such that this is not true?

I think that for $A=\mathbb{N}$ this is true. In fact for this case, I think $\exists\ N$ such that $\ a_n(x) \geq a_{n-1}(x)(a_{n-1}(x)-1) + 1\ \forall\ n\geq N.$ This comes from the fact that, for example, $\frac{1}{11} + \frac{1}{(11)(10)} = \frac{1}{10}.$

But if $A \neq \mathbb{N},$ for example $A=\mathbb{P},$ then we cannot say that $\frac{1}{11} + \frac{1}{(11)(7)} = \frac{1}{7}:$ indeed, the left-hand side is less than the right-hand side. So how to proceed?

Answer 1

The conjecture is false. For a counterexample, let $A_m = [5^m, 2\cdot 5^m) \cap \Bbb Z$ and set $A=\bigcup_{m=1}^\infty A_n$. Note that $\sum_{k\in A_m} \frac1k \sim \log 2$ for each $m$, and so $A$ is large. Now choose $$ x=\sum_{m=1}^\infty \biggl( \frac1{5^m}+\frac1{5^m+1} \biggr) \approx 0.465062. $$ Then the greedy algorithm produces the "obvious" sequence $(a_n(x)) = (5^1,5^1+1,5^2,5^2+1,5^3,5^3+1,\ldots)$. Confirming this assertion uses the upper bound $$ \sum_{m=\ell}^\infty \biggl( \frac1{5^m}+\frac1{5^m+1} \biggr) < \sum_{m=\ell}^\infty \biggl( \frac1{5^m}+\frac1{5^m} \biggr) = \frac1{2\cdot 5^\ell}, $$ so that the element chosen after $a_{2m-1}(x) = 5^m$ and $a_{2m}(x)=5^m+1$ cannot come from $A_m$.