2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I retagged your question. Note that if b is a rational multiple of a, then by rescaling you are just looking at the semigroup generated by two positive integers, and this is IIRC an example of a "numerical" subgroup, quite a lot is known (cf. "postage stamp" problems) $\endgroup$
    – Yemon Choi
    Feb 14, 2013 at 19:35

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.