正の実数は次のように近似できますか $2^m/3^n$ と $(m,n)$ 十分大きい？
推測。
正の整数が存在します$(m,n)$ 十分な大きさで、正の実数に対して $r$ と与えられたエラー $\epsilon$ ： $$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$この推測には数値的な証拠があります。私が試してみました$r = \sqrt{2}$ そして $\epsilon = 10^{-3}$。
以下は、出力を伴う小さなDelphiPascalプログラムです。
しかし..誰かが推測を証明することができますか？
離れてプログラム;
プロシージャテスト（r：ダブル; eps：ダブル）; var a：ダブル; m、n：整数; ベギン a：= 1; m：= 0; n：= 0; 本当ですが ベギン a <rの場合、 ベギン m：= m + 1; a：= a * 2; 終了その他開始 n：= n + 1; a：= a / 3; 終わり; abs（ra）<epsの場合、Break; 終わり; Writeln（r、 '= 2 ^'、m、 '/ 3 ^'、n、 '='、a）; 終わり;
ベギン test（sqrt（2）、1.E-3）; 終わり。
出力：
1.41421356237310E + 0000 = 2 ^ 243/3 ^ 153 = 1.41493657935359E + 0000
更新。lhf
による答えは非常に簡潔な証拠のように見えます。しかし、私にとって-教育によって引退した物理学者として-それは理解を少し超えています。さらに、いくつかの問題はそのままです。たとえば、
$m$ そして $n$ いつ $r$ そして $\epsilon$ 与えられます。
注意。質問は次のように定式化することもできます。正の実数は次のように近似できますか。$3^m/2^n$ と $(m,n)$十分大きい？これは、元の定式化で負の整数を許可することと同じです。この形式では、（不）有名なコラッツ問題にいくらか類似していることを示しています。
編集。
回答で示唆されているように、対数を使用したアプローチの方が効果的である可能性があります。
プログラムアンダース;
プロシージャproef（r：double; eps：double）; var a、l2、l3、lr：double; m、n：整数; ベギン l2：= ln（2）; l3：= ln（3）; lr：= ln（r）; a：= 0; m：= 0; n：= 0; 本当ですが ベギン a：= m * l2-n * l3-lr; abs（a）<epsの場合、Break; a <0の場合m：= m + 1 else n：= n + 1; 終わり; Writeln（r、 '= 2 ^'、m、 '/ 3 ^'、n、 '='、exp（a）* r）; 終わり;
ベギン proef（sqrt（2）、1.E-3）; proef（sqrt（2）、1.E-9）; 終わり。
出力：
1.41421356237310E + 0000 = 2 ^ 243/3 ^ 153 = 1.41493657935356E + 0000 1.41421356237310E + 0000 = 2 ^ 911485507/3 ^ 575083326 = 1.41421356125035E + 0000
出力の最初の行は、前に取得した結果とほぼ同じです。
出力の最後の行は、後者のアプローチが実際により効果的であることを示しています。
エラーは、両方のアプローチで同じ役割を果たします。まあ、ほとんど。'Break'sがある場所を見てみましょう。最初のプログラム：$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$ 2番目のプログラム： $$ -\epsilon < m\ln(2) - n\ln(3) - \ln(r) < +\epsilon \\ \ln(1-\epsilon) < \ln\left(\frac{2^m/3^n}{r}\right) < \ln(1+\epsilon) \\ -\epsilon < \frac{2^m/3^n}{r} - 1 < +\epsilon \\ \left| r - \frac{2^m}{3^n} \right| < \epsilon.r $$ そう $\epsilon$最初のプログラムでは絶対誤差ですが、$\epsilon$2番目のプログラムでは相対誤差です。
続きの話：
スターン・ブロコットの木を採用して、$2^m/3^n$？
回答
はい、常に解決策があります $(m, n)$ 正の実数 $r$ そして $\epsilon$ にとって $$\left| r - \frac{2^m}{3^n} \right| < \epsilon$$そして、ステップスルーするよりもはるかに効率的な方法でこれらのソリューションを見つけることができます$m$ そして $n$ 値を1つずつ。
我々は持っています $$r \approx 2^m/3^n$$ 対数を取る、 $$\log r \approx m\log 2 - n\log 3$$ $$\log r/\log 2\approx m - n\log 3 / \log 2$$ すなわち、 $$\log_2 r\approx m - n\log_2 3$$
[ちなみに、 $$1 = \frac m{\log_2r}-\frac n{\log_3r}$$ これはの行です $(m,n)$ 平面 $m$ 傍受 $\log_2r$ そして $n$ 傍受 $-\log_3r$。その線が整数に近づくときを見つけたい$(m, n)$ 格子点]。
これらの2を底とする対数の両方に対して、任意の精度で有理近似を見つけることができます。ただし、その方程式を整数で満たすには $m$ そして $n$、近似の分母は釣り合っている必要があります。
しましょう $$\log_2 r = f \approx s/t$$ そして $$\log_2 3 \approx p/q$$ 分数は最低条件です、すなわち、 $\gcd(s,t)=gcd(p,q)=1$。
その後、 $$\frac st = m - n \frac pq$$ $$sq = (qm - pn)t$$ したがって、 $t|sq$。だが$s$ ＆ $t$ 互いに素であるため、 $t|q$。
しましょう $q=tk$。 $$f \approx \frac st = \frac{sk}{tk}=\frac{sk}{q}=\frac dq$$ いくつかの整数の場合 $d$。
したがって、与えられた近似に対して $\frac pq$ に $\log_2 3$、への最良の有理近似 $f$ 相応の分母があります $\frac{d_0}q$ そして $\frac{d_1}q$、 どこ $d_0=\lfloor fq\rfloor$ そして $d_1=\lceil fq\rceil$。あれは、$$\frac{d_0}q \le f \le \frac{d_1}q$$ 場合 $f$ 合理的である（例えば、 $r=\sqrt 2$）、次に $d_0$ そして $d_1$ 等しいかもしれません。
だから与えられた $p$ ＆ $q$ 整数を見つける必要があります $m$ ＆ $n$ 修正された方程式を解く $$\frac dq = m - n \frac pq$$ $$d=qm-pn$$ 両方のための $d_0$ そして $d_1$。任意の整数の解決策があります$d$ なぜなら $p$ ＆ $q$互いに素です。そして、それらの解決策は、拡張ユークリッドアルゴリズムを使用して見つけることができます。
しかし、適切なものを見つける必要もあります $p$ ＆ $q$。これは、連分数展開の収束を使用して行うことができます。$\log_2 3$。連分数を計算するための標準アルゴリズムは、拡張ユークリッドアルゴリズムと密接に関連しており、ウィキペディアの記事で説明されているように（定理3）、$n$連分数の収束は $\frac{h_n}{k_n}$ その後 $$k_nh_{n-1} - k_{n-1}h_n = (-1)^n$$ それは私たちが見つけることを可能にします $m$ そして $n$ 個別のユークリッドアルゴリズム計算を行わずに。
連分数収束 $\frac hk$ 数の $x$ に最良の有理近似を与える $x$ 分母の場合 $\le k$。エラーは$$\left|x - \frac hk\right| \le \frac 1{k^2}$$そしてそれはしばしばはるかに良くなることができます。対照的に、近似の誤差$\frac hk$ 「ランダムな」分母（つまり、連分数の収束ではない）は、一般的に約 $\frac 1{2k}$。
残念ながら、2つの対数の近似には相応の分母が必要なため、完全なものは得られません。 $\frac 1{k^2}$良さ。しかし、私たちは一般的に$\frac 1{k}$。
したがって、与えられたよりも良いエラーのある解決策を見つけるために $\epsilon$、私たちは収束を見る必要があります $\log_2 3$ の近くの分母と $\frac 1\epsilon$。
これは、そのタスクを実行するSage / Pythonコードです。Sageは、人気のあるPythonプログラミング言語の上に構築された数学ライブラリのコレクションです。任意精度の算術演算と記号代数を実行する機能がありますが、必要に応じて他の言語への移植を容易にするために、このコードでは（任意精度の算術演算を除いて）Sage機能を（ほとんど）避けました。関数から複数の値を返すPythonの機能を除いて、ほとんどの「Pythonism」も避けました。
# Numeric precision. Standard IEEE 754 binary64
# numbers (aka doubles) have 53 bits of precision.
bits = 53
# Limit the length of the continued fraction
depth = 20
def dio(q, p, x, y, d):
""" Given q, p, x, y: q*x - p*y == 1,
find the smallest m, n > 0:
q*m - p*n == d
"""
m = x * d
n = y * d
u = min(m // p, n // q)
m -= u * p
n -= u * q
assert q*m - p*n == d
return m, n
log2 = log(2).n(bits)
log3 = log(3).n(bits)
def func(m, n):
""" Calculate 2**m / 3**n """
# The naive form is too slow for large args,
# and chews up a lot of RAM because it uses
# arbitrary precision integer arithmetic.
# So we use logs instead.
#return (2**m / 3**n).n(bits)
return exp(m * log2 - n * log3).n(bits)
def cont_frac(f, depth):
""" Build lists of the convergents of
the continued fraction of f
"""
f = f.n(bits)
num = [0, 1]
den = [1, 0]
for i in range(depth):
a = floor(f)
n = num[-2] + a * num[-1]
d = den[-2] + a * den[-1]
#print(a, n, d)
num.append(n)
den.append(d)
f -= a
if f < 1e-10:
break
f = 1 / f
return num, den
num, den = cont_frac(log(3, 2), depth)
@interact
def main(r=sqrt(2), epsilon=1/1000):
print("r:", r.n(bits))
f = log(r, 2)
s = 1
digits = 2
for i in range(3, depth+2):
s = -s
p = num[i]
q = den[i]
x = num[i-1] * s
y = den[i-1] * s
assert q*x - p*y == 1
fq = f * q
d0 = floor(fq)
d1 = ceil(fq)
print(f"\n{i}: {p} / {q}, {d0} {d1}")
dseq = [d0]
if d0 < d1:
dseq = [d0, d1]
else:
dseq = [d0]
for d in dseq:
m, n = dio(q, p, x, y, d)
v = func(m, n)
eps = abs(r - v).n(bits)
if eps > 0:
digits = 1 - floor(log(eps, 10))
print(f"m: {m}, n: {n}")
print(f"v: {v:.{digits}f}, eps: {eps:.3e}")
if eps < epsilon:
return
これがそのプログラムの出力であり、 $\epsilon=10^{-6}$：
r: 1.41421356237310
3: 2 / 1, 0 1
m: 0, n: 0
v: 1.00, eps: 4.142e-1
m: 1, n: 0
v: 2.00, eps: 5.858e-1
4: 3 / 2, 1 1
m: 2, n: 1
v: 1.333, eps: 8.088e-2
5: 8 / 5, 2 3
m: 2, n: 1
v: 1.333, eps: 8.088e-2
m: 7, n: 4
v: 1.58, eps: 1.660e-1
6: 19 / 12, 6 6
m: 10, n: 6
v: 1.4047, eps: 9.550e-3
7: 65 / 41, 20 21
m: 10, n: 6
v: 1.4047, eps: 9.550e-3
m: 56, n: 35
v: 1.440, eps: 2.603e-2
8: 84 / 53, 26 27
m: 10, n: 6
v: 1.4047, eps: 9.550e-3
m: 75, n: 47
v: 1.4209, eps: 6.645e-3
9: 485 / 306, 153 153
m: 243, n: 153
v: 1.41494, eps: 7.230e-4
10: 1054 / 665, 332 333
m: 812, n: 512
v: 1.41343, eps: 7.844e-4
m: 243, n: 153
v: 1.41494, eps: 7.230e-4
11: 24727 / 15601, 7800 7801
m: 12891, n: 8133
v: 1.414196, eps: 1.800e-5
m: 11837, n: 7468
v: 1.414257, eps: 4.373e-5
12: 50508 / 31867, 15933 15934
m: 12891, n: 8133
v: 1.414196, eps: 1.800e-5
m: 37618, n: 23734
v: 1.4142213, eps: 7.728e-6
13: 125743 / 79335, 39667 39668
m: 88126, n: 55601
v: 1.4142110, eps: 2.546e-6
m: 37618, n: 23734
v: 1.4142213, eps: 7.728e-6
14: 176251 / 111202, 55601 55601
m: 88126, n: 55601
v: 1.4142110, eps: 2.546e-6
15: 301994 / 190537, 95268 95269
m: 88126, n: 55601
v: 1.4142110, eps: 2.546e-6
m: 213869, n: 134936
v: 1.4142162, eps: 2.637e-6
16: 16785921 / 10590737, 5295368 5295369
m: 8241964, n: 5200100
v: 1.414213479, eps: 8.295e-8
そして、これがSageMathサーバーで遊べるライブバージョンです。私のコードはサーバーに保存されておらず、URLにエンコードされています。
あなたが小さなで奇妙な行動をした場合 $\epsilon$、bits（ファイルの先頭にある）グローバル変数の数を増やしてみてください。デフォルト設定の53は問題ないはずです$\epsilon > 10^{-8}$とか、ぐらい。depth連分数を増やす必要がある場合もあります。
FWIW、 $\log_2 3$平均律の数学的音楽理論ではかなり重要です。標準の12音スケールは収束を使用します$19/12$。
しましょう $G= \mathbb Z \log 2 + \mathbb Z \log 3$。その後、$G$ の加法サブグループです $\mathbb R$。以来$\log 2 / \log 3$ 不合理です、 $G$循環することはできません[1]ので、密にする必要があります[2]。したがって、$\log r$ の要素によって任意に近似されます $G$。
[1]もし $G = \mathbb Z \theta $、その後 $\log 2 = a \theta$ そして $\log 3 = b \theta$ など $\log 2 / \log 3 = a/b $ 合理的です。
[2]を参照してください https://math.stackexchange.com/a/889775/589
別の証明のヒューリスティック
補題1.
分数$2^m/3^n$ すべての間にあります $r/3$ そして $2r$。
証明。
プログラムによると-質問に表示されているように。より小さい分数$r$ を掛ける $2$、 そう $r.2$これらの分数の上限です。より大きい任意の分数$r$ で割る $3$、 そう $r/3$これらの分数の下限です。反復が開始されるときを除いて、他の分数はあり得ません。$$ r/3 < \frac{2^m}{3^n} < 2r $$ 補題2.
順番に$2^m/3^n \to r$同じ2つの分数はありません。
証明。
私たちが持っていると仮定します$2^{m_1}/3^{n_1} = 2^{m_2}/3^{n_2}$。
3つのケースが区別されます。
- $m_1 \neq m_2$ そして $n_1 = n_2$。その後、$2^{m_1} = 2^{m_2}$ したがって、 $m_1 = m_2$。矛盾。
- $n_1 \neq n_2$ そして $m_1 = m_2$。その後、$1/3^{n_1} = 1/3^{n_2}$ したがって、 $n_1 = n_2$。矛盾。
- $m_1 \neq m_2$ そして $n_1 \neq n_2$。次に、次のようになります。$$ \ln\left(\frac{2^{m_1}}{3^{n_1}}\right) = \ln\left(\frac{2^{m_2}}{3^{n_2}}\right) \quad \Longrightarrow \\ (m_1-m_2)\ln(2) - (n_1-n_2)\ln(3) = 0 \quad \Longrightarrow \\ \frac{m_1-m_2}{n_1-n_2} = \frac{\ln(3)}{\ln(2)} $$ だが $\,\ln(3)/\ln(2)\,$有理数ではありません。矛盾。
つまり、私たちが持っているのは、すべて異なる分数の束ですが、それらは間隔内に収まる必要があります $\,]r/3,2r[\,$。これは、分数が混雑することを意味します。反復プロセスの対数バージョンの図を作成しましょう。赤い線はによって与えられます$\,\color{red}{\ln(3)y=\ln(2)x-\ln(r)}\,$、小さな円は分数であり、グリッドにマッピングされます $\,m/n \to (m,n)\,$、大量に黒く塗りつぶされたドットは、反復プロセスの一部であり、増加します $m$ そして $n$一度に1つずつ増分します。反復ドメインは次の制限があります。$\,\color{blue}{-\ln(2)\lt\ln(3)y-\ln(2)x+\ln(r)\lt\ln(3)}\,$。私たちの場合には$r = 100$。開始時にシーケンスに注意してください。
したがって、実数を表す赤い線の近くにかなりの分数があるはずです。 $r$問題の。
どうすればこれを確信できますか？近似の混雑の写真を作りましょう$a$ 間隔で $\,]r/3,2r[\,$、対数目盛： $$ a = m\ln(2)-n\ln(3)-\ln(r) \quad \mbox{with} \quad -\ln(3) < a < \ln(2) $$ 赤い線はどこにあります $a = 0$、目的の値。
さらなる数値/グラフ実験により、分数の分布が均一であるように見えることが明らかになりました。これをさらに確認するために、（Delphi）Pascalの観点から次のことを行いました。
プログラムopnieuw;
プロシージャ間隔（var A、B：double）; var h：ダブル; ベギン A：=ランダム; B：=ランダム; A> Bの場合 ベギン h：= B; B：= A; A：= h; 終わり; 終わり;
プロシージャproef（r：double）; const veel：整数= 1000000000; var x、l2、l3、lr、A、B：ダブル; m、n、tel、t：整数; ベギン l2：= ln（2）; l3：= ln（3）; lr：= ln（r）; 間隔（A、B）; A：= -l3 + A *（l2 + l3）; B：= -l3 + B *（l2 + l3）; m：= 0; n：= 0; tel：= 0; t：= 0; tel <veel do ベギン x：= m * l2-n * l3-lr; x <0の場合、m：= m + 1、それ以外の場合、n：= n + 1; if（-l3 <x）and（x <+ l2）then tel：= tel + 1; （A <x）および（x <B）の場合、t：= t + 1; 終わり; Writeln（（BA）/（l2 + l3）、 '='、t / tel）; 終わり;
ベギン ランダム; ランダム; proef（1000）; proef（0.001）; proef（sqrt（2））; proef（1 / sqrt（2））; 本当ですが proef（ランダム）; 終わり。
説明。ランダムな間隔を作る$\,]A,B[\,$ 内部 $\,]-\ln(3),+\ln(2)[\,$。後者の間隔の長さは$\,\ln(3)+\ln(2)=\ln(6)\,$、前者の長さは $\,(B-A)\,$。（対数を数える$x$ の）分数 $\,(2^n/3^n)/r\,$両方の間隔で。しましょう$N$ iterandsの総数（tel）であり、 $n$ のイテランドの数（t）である $\,]A,B[\,$。次に、近似の分布$x$次の場合にのみ均一です。$$ \lim_{N\to\infty}\frac{n}{N} = \frac{B-A}{\ln(6)} $$確認しよう。各行を10億回繰り返した後の出力：
6.58467502100393E-0001 = 6.58467500000000E-0001 3.98733151378110E-0001 = 3.98733149000000E-0001 1.56895805848762E-0001 = 1.56895804000000E-0001 5.34354087430984E-0002 = 5.34354050000000E-0002 4.04224734520540E-0001 = 4.04224734000000E-0001 2.33572337077931E-0001 = 2.33572341000000E-0001 4.06758418539539E-0001 = 4.06758418000000E-0001 1.46495995344594E-0001 =...。
しかし、それが一様分布であることをどのように証明できますか？