Skip to main content
MathOverflow

Return to Answer

added 234 characters in body
Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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 ordermeans that we can be described, itlocate 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. IIf $b$ is rational there will assume that you canbe a need to break ties as you wish as long as future choices are consistent with this. That amountsIt seems right to saying that $b$ , if rational, is "really" $b=u/v+\epsilon$ where $\epsilon$ is a nonzero quantitydo this consistently (positivealways favor the expression with larger $q$ or negativevice versa.) so infinitesimalHowever that it, and even $10^{100}\epsilon$ are irrelevant except when breaking tieshas 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 requiresallows 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.

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

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). This order can be described, it depends on good approximations to $b$ by rational numbers with small denominators. I will assume that you can break ties as you wish as long as future choices are consistent with this. That amounts to saying that $b$ , if rational, is "really" $b=u/v+\epsilon$ where $\epsilon$ is a nonzero quantity (positive or negative) so infinitesimal that it, and even $10^{100}\epsilon$ are irrelevant except when breaking ties.

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

I don't know if things are quite as precise for reals $b$ with less regular continued fraction expansions. It may be that saying $0$ is in position $0$ works a little better.

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.

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

added 127 characters in body
Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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). This order can be described, it depends on good approximations to $b$ by rational numbers with small denominators. I will assume that you can break ties as you wish as long as future choices are consistent with this. That amounts to saying that $b$ , if rational, is "really" $b=u/v+\epsilon$ where $\epsilon$ is a nonzero quantity (positive or negative) so infinitesimal that it, and even $10^{100}\epsilon$ are irrelevant except when breaking ties.

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 kb$$0 \le p \le \lfloor kb \rfloor$ and $0 \le q \le k,$ while a random expressionand the expressions meeting thosethese 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 equally likely to be too big or not to be.no larger than $kb.$ So indeed every upper bound requires 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.

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). This can be described it depends on good approximations to $b$ by rational numbers with small denominators. I will assume that you can break ties as you wish as long as future choices are consistent with this. That amounts to saying that $b$ , if rational, is "really" $b=u/v+\epsilon$ where $\epsilon$ is a nonzero quantity (positive or negative) so infinitesimal that it, and even $10^{100}\epsilon$ are irrelevant except when breaking ties.

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 kb$ and $0 \le q \le k,$ while a random expression meeting those conditions is equally likely to be too big or not to be. So indeed every upper bound requires 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.

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). This order can be described, it depends on good approximations to $b$ by rational numbers with small denominators. I will assume that you can break ties as you wish as long as future choices are consistent with this. That amounts to saying that $b$ , if rational, is "really" $b=u/v+\epsilon$ where $\epsilon$ is a nonzero quantity (positive or negative) so infinitesimal that it, and even $10^{100}\epsilon$ are irrelevant except when breaking ties.

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

Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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). This can be described it depends on good approximations to $b$ by rational numbers with small denominators. I will assume that you can break ties as you wish as long as future choices are consistent with this. That amounts to saying that $b$ , if rational, is "really" $b=u/v+\epsilon$ where $\epsilon$ is a nonzero quantity (positive or negative) so infinitesimal that it, and even $10^{100}\epsilon$ are irrelevant except when breaking ties.

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 kb$ and $0 \le q \le k,$ while a random expression meeting those conditions is equally likely to be too big or not to be. So indeed every upper bound requires 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. It may be that saying $0$ is in position $0$ works a little better.