# If $a_n>0;\ a_n\to 0,$ is there an enumeration $\{ x_n \}_{n\in\mathbb{N}}$ of $\mathbb{Q}\cap (0,1]$ such that $a_1 x_1 > a_2 x_2 > a_3 x_3\ldots\ ?$

alternative-proofgeneral-topologyproblem solvingproof-writingreal-analysis

Suppose $$\ a_n>0\ \forall n\in\mathbb{N}\$$ with $$\ a_n\to 0.\$$

Proposition: There exists a bijective enumeration $$\ \{ x_n \}_{n\in\mathbb{N}}\$$ of $$\ \mathbb{Q}\cap (0,1],\$$ such that $$\ a_1 x_1 > a_2 x_2 > a_3 x_3 \ldots\ .$$

I have many ideas of how to prove this, although I am finding it tricky to actually write out a proof. I was wondering if there are particularly simple/straightforward proofs of this. I'm also just interested in seeing different ideas and methods for how to prove this…

I'll start posting one or more of my proofs once I've formalised them… but they are to do with the peaks and troughs of $$\ a_n\$$ like in the Lemma to the proof of B-W. The peaks form a decreasing sequence which gives a good starting point for a proof. The troughs also give a decreasing sequence which gives a good starting point for a proof.

By "trough" here, I mean, a point $$\ a_k\$$ such that $$\ ia_k.$$

I do not know if there is a nice, elegant formula for the sequence $$x = (x_n)_n$$, but I do believe that it is possible. Here is a collection of comments roughly outlining an algorithm to produce $$x$$.

First, imagine that there is an agreed-upon enumeration $$q = (q_n)_n$$ of $$(0,1]\cap \mathbb Q$$ to start from. The idea is that we will draw elements from $$q$$ whenever we need them, and whenever an element is drawn it will be removed from $$q$$. Then, whenever we have the freedom to choose any rational we like, we always choose the element of $$q$$ with the lowest index not yet selected. In this way, after infinitely many choices, we can be sure that every rational was selected exactly once.

I will also here only consider the case where $$a = (a_n)_n$$ is a strictly decreasing sequence. Any sequence which converges to zero must have a strictly decreasing subsequence (as you observed), so if you must cover the case where $$a$$ is not decreasing, you could pick out the decreasing subsequence $$a_{n_i}$$, build $$x_{n_i}$$ according to the following paragraphs, and between indices $$n_i$$ and $$n_{i+1}$$ you might pick elements for $$x$$ arbitrarily according to the condition $$a_\ell x_\ell > a_{\ell+1} x_{\ell+1}$$ (drawing and eliminated rationals from $$q$$ as described above). This all has to be done in order (inductively), so that you never double-use a rational.

So assume $$a$$ is strictly decreasing. Imagine now we are in the middle of our inductive construction; we have been handed $$x_1$$ (really $$x_i$$) and we wish to produce $$x_2$$ (really $$x_{i+1}$$). The possible values that $$x_2$$ can take are limited by the condition $$a_1x_1> a_2x_2$$; we must have

$$\frac{a_1}{a_2} x_1 > x_2.$$

Note that $$a_1 > a_2$$ by assumption, in which case $$a_1/a_2 > 1$$ and so $$(a_1/a_2)x_1$$ is a little bit bigger than $$x_1$$. Therefore, $$x_2$$ need not necessarily be smaller than $$x_1$$ ($$x$$ need not be a decreasing sequence), but it cannot be so much bigger than $$x_1$$ either. We must draw $$x_2$$ from the interval $$\big(0,(a_1/a_2)x_1\big)$$.

In the easy case, $$(a_1/a_2)x_1 \geq 1$$ and so $$x_2$$ can be any rational we like from $$(0,1]$$. This is when we draw the element of $$q$$ with the lowest index not yet selected, and move on to finding $$x_3$$ from $$x_2$$. But in the other case, when $$(a_1/a_2)x_1 < 1$$, that is when we have to worry.

Here is an illustration of a hypothetical case. The orange region indicates where we may draw $$x_2$$ from and still satisfy the desired condition.

What is worrying about this case is the fact that we don't have access to the whole interval. What if it is impossible to enumerate the rationals greater than $$(a_1/a_2)x_1$$ now?

Though that isn't the case; if we pick a rational between $$x_1$$ and $$(a_1/a_2)x_1$$ (near the right boundary of our orange interval), then the next rational $$x_3$$ will be at most $$(a_2/a_3)x_2$$ - a slightly larger window than before!

The idea is that we can always do this; we may choose a string of $$x$$'s which is increasing up to the point where our window of possibilities encompasses the whole interval $$(0,1]$$. Then, for the next $$x$$, we pick the $$q$$-smallest rational not yet picked, and repeat the process.

But is it really always possible? The worst case is that this process is somehow bounded; that no matter how many $$x$$'s we select, right up against the edge of what we can possibly select, there will be some rationals close to $$1$$ which we will never have access to, even after infinitely many draws. I claim that this process is NOT bounded, that we CAN climb as high as we like, no matter what.

What is the highest possible value that could be selected for $$x_2$$? At most, it is $$x_2 = (a_1/a_2)x_1$$. Then, the highest possible value for $$x_3$$ would be $$(a_2/a_3)x_2$$ which simplifies to $$(a_1/a_3)x_1$$. In general, the highest possible value $$x_n$$ could reach is

$$x_n \leq \Big(\frac{a_1}{a_n}\Big)x_1$$

plus or minus a negligible amount, as we must be sure to actually choose rational values of $$x$$ (and the $$a$$'s may be irrational). Then observe: as $$a$$ converges to zero, $$(1/a_n)_n$$ converges to infinity, and therefore there is an $$n$$ where $$a_1x_1/a_n \geq 1$$.

This (hopefully) demonstrates that it is possible to construct such an $$x$$, though you may be able to simplify/optimize the above construction.

Edit: I don't think that this demonstrates that it is possible to find $$x$$ when $$a$$ is not a decreasing sequence, as what I mentioned before (picking elements in between indices of a decreasing subsequence) doesn't necessarily work if you need coordination over many consecutive indices.