on the set of numbers generated by integer linear combination of two real numbers.

Question

Let $b > a > 0$ be two real numbers. I am interested in the set of numbers $X(p,q) = p a + q b$ with $p,q$ positive integers. Basically this is the set $a \mathbb{N} + b \mathbb{N}$.

What can we say about this set? Can it be indexed in an ordered fashion,i.e. each element would write as:

$X(j) = a p(j) + b q(j)$ with $X(j+1) > X(j)$

Now there are some particular cases where there is an integer relation between $a$ and $q$ that I have started working out. However, the original problem from which this question occurs makes no assumptions about $a$ and $b$ and can therefore be assumed to be unrelated.

I am sorry if I sound naive or ignorant, I would be glad if any reference or further reading material is given.

Answer 1

Yes, the set $X = a\mathbb{N} + b\mathbb{N}$ is order-isomorphic to $\mathbb{N}$.

For any positive real $k$ the set $X\cap [0,k]$ is finite. Indeed, to have $ap+bq \leq k$ for $p,q\in\mathbb{N}$ we must have $ap\leq k$ and $bq\leq k$, so only finitely many values of $p$ and $q$ yield elements of $X\cap [0,k]$.

Therefore $Y_i = X\cap [i-1,i)$ is finite for each $i\in\mathbb{N}$. Enumerate $X$ by enumerating $Y_1$, then $Y_2$, then $Y_3$, etc. You hit all elements of $X$ in order this way.

Answer 2

We can assume that $1=a \lt b.$ Consider the set of expressions $p+qt$ with $p,q \ge 0$ integers. Substituting $t=b$ makes these real numbers with a certain order (and ties to be broken when $b$ is rational). I will show that the position of an expression $p+qt$ with value $x=p+qb$ will be very close to $\frac{(x+b)(x+1)}{2b}.$ This means that we can locate the position of an expression or figure out what is in position $P$ without running through all the smaller values. The order depends on good approximations to $b$ by rational numbers with small denominators. If $b$ is rational there will be a need to break ties. It seems right to do this consistently (always favor the expression with larger $q$ or vice versa.) However that has no effect on the positions of everything else.

In answer to your first question, consider all the expressions with value up to $kb.$ The number of these will be quite close to $\frac{(k+1)(kb+1)}{2}$ since $p+qb \le kb$ requires $0 \le p \le \lfloor kb \rfloor$ and $0 \le q \le k,$ and the expressions meeting these conditions naturally pair up (maybe with one self paired) so that each pair has sum $\lfloor kb\rfloor+kb.$ Hence just one member of each pair is no larger than $kb.$ So indeed every upper bound allows only a finite number of terms. To estimate the position of a positive real number $x$ (integer or arbitrary) we can substitute $k=\frac{x}{b}$ to get an estimated position of $\frac{(x+b)(x+1)}{2b}.$ We will see below that this is quite accurate.

It is instructive to consider first the question of recovering $t$ from an initial segment of the order. Suppose I have chosen $b$ but refuse to reveal to you the exact value. But, I will tell you that the first $45$ terms in the order are as below.

$0, {\Large 1, t, 2}, 1+t, {\Large 2t, 3}, 2+t, 1+2t, {\Large 4, 3t}, 3+t, 2+2t, 5, 1+3t, 4+t, 4t, 3+2t, $$6, 2+3t,5+t, 1+4t, 4+2t, {\Large 7, 5t}, 3+3t, 6+t, 2+4t, 5+2t, 8, 1+5t, 4+3t,$$ 7+t, 6t, 3+4t, 6+2t, 9, 2+5t, 5+3t, 8+t, 1+6t, 4+4t, 7+2t, {\Large 7t, 10}$

I have emphasized the only terms whose location actually gives new information: those where $0+qt$ comes immediately before or after a term $p+0b.$ This is because the relative order of $v+wt$ and $x+yt$ dedends only on if $v-x$ comes before or after $(y-w)b.$ (I don't consider that a complete explanation.)

From $1,t,2$ we can see that $t \in (1,\infty)$ and then that $t\in (1,2).$ That alone determines the next term. From $2t,3$ (and what we already know), we discover $t \in(1,3/2)$ and now we can predict things until terms $10$ and $11$ where $4,3t$ reveal $t \in(4/3,3/2).$ That determines everything up to terms $24$ and $25$ where $7,5t$ yields $t \in (7/5,3/2).$ And that determines the remaining order until terms $44$ and $45$ when $7t,10$ reveals $t\in(7/5,10/7) \approx (1.4,1.43)$

At this stage you might suspect that $b=\sqrt{2} \approx 1.41421356.$ You will never know for sure just from seeing more of the order. But if you are correct (OK, I admit it, you are!) then the next new information will be $(12t,17)$, $(24,17t)$, $(41,29t)$,$(41t,58)$,$(70t,99)$,$(140,99t)$ which occur at positions $117,225,630,1239,3550,7050.$

Note that the estimate I gave above for the position of $x=140$ was $\frac{(x+b)(x+1)}{2b}\approx 7049.649$ while the estimated position for $kb=99\sqrt{2}\approx 140.00714$ was $\frac{(k+1)(kb+1)}{2}\approx 7050.357.$ The actual positions are $7050$ and $7051.$

Taking $b=\sqrt{2}$ made things pleasant because the continued fraction is very regular. $$ \sqrt{2}= 1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}} $$ The "official" sequence of convergents to $\sqrt{2}$ is $\infty=1/0,1/1,3/2,7/5,17/12,41/29,99/70,\cdots$ The approximations we found were $0/1,1/1,2/1,3/2,4/3,7/5,10/7,17/12\cdots$ where the extra terms result from a kind of naive addition from the official sequence. For a value $b$ with a more complex continued fraction ,things would be somewhat more involved, but not too much so. I think that if there is a denominator $d$ in the continued fraction then there are $d-1$ intermediate values. For example the continued fraction for $ \sqrt{13} \gt 3$ has a denominators which repeat $1, 1, 1, 1, 6.$ These correspond, the first time through, to $4,7/2,11/3,18/5,119/33.$ The fractions which affect the initial order of the series $p+qt$ are those above augmented by the $6-1=5$ values $29/8,47/13,65/18,83/23,101/28$ between $18/5$ and $119/33.$

So I have given a formula to estimate where a number $x$ will land. It may need adjustments by $1$ in places, but looks good.

If instead we want to know what appears in position $P$, then the two forms of the expression can be used with the quadratic formula to get estimates $kb$ and $N$ for what can fall there. The $k$ and $N$ will not be integers but both $kb$ and $N$ will be equal and very close to the value of the actual number in that position. To write it in the form $p+qb$ we need to know how to move forward or back.

Looking back at the sequence above, the jumps between consecutive terms starting at $2+2t,5$ are ${ \small 3-2 t,3 t-4,3-2 t,3 t-4,3-2 t,3-2 t,3 t-4,3-2 t,3 t-4, 3-2 t,3-2 t,}$${ \small 5 t-7,3-2 t,3-2 t,3 t-4,3-2 t,3-2 t,5 t-7,3-2 t,3-2 t,5 t-7, 3-2 t,}$${\small 3-2 t,3-2 t,5 t-7,3-2 t,3-2 t, \small 5 t-7,3-2 t,3-2 t,5 t-7,10-7 t,5 t-7}$ So it seems possible to say what the sequence of jumps is.

For example the value at position $P$ is estimated to be $x=\frac{-b-1+\sqrt{(b-1)^2+8Pb}}{2}.$ For $P=5000$ and $b=\sqrt{2}$ that comes to $117.713785.$ A similar calculation suggests that $83.23621565\sqrt{2} \approx 117.713785$ should fall in that place. So we might work backward from the position $5025$ of $118$ or forward from the position $4972$ of $83\sqrt{2}$ to discover that in positions $4999,{\Large 5000},5001$ are $88+21\sqrt{2} \approx 117.69848$ then ${\Large 47+50\sqrt{2} \approx 117.7106781}$ and finally $6+79\sqrt{2} \approx 117.72287.$ So we have arrived at a value as accurate as can be expected for that position.

If we want the position of $x=20+13\sqrt{2}$ then the estimate is position $\frac{(x+\sqrt{2})(x+1)}{2\sqrt{2}} \approx 554.186$ And in positions $554,{\Large 555},556$ are $3+25\sqrt{2} \approx 38.3553$ then ${\Large 20+13\sqrt{2} \approx 38.3848}$ and finally $37+\sqrt{2} \approx 38.4142.$

I don't know if things are quite as precise for reals $b$ with less regular continued fraction expansions. I don't think that the formulas will loose accuracy if $b$ is large, only the fractional part matters. I did not check something like $b=468/113-\pi \approx 1.000000266764.$

Answer 3

See the 2007 article by John Kieffer: https://www.researchgate.net/publication/4332261_Fast_Generation_of_Tunstall_Codes The continued fraction method works in all cases.