Bất kỳ thực dương nào có thể được gần đúng như $2^m/3^n$ với $(m,n)$ đủ lớn?
Phỏng đoán.
Tồn tại các số nguyên dương$(m,n)$ đủ lớn, sao cho bất kỳ số thực dương nào $r$ và một lỗi nhất định $\epsilon$ : $$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Có bằng chứng số cho phỏng đoán này. Tôi đã thử$r = \sqrt{2}$ và $\epsilon = 10^{-3}$.
Dưới đây là một chương trình Delphi Pascal nhỏ với đầu ra đi kèm.
Nhưng .. ai đó có thể chứng minh phỏng đoán không?
chương trình ngoài;
kiểm tra thủ tục (r: double; eps: double); var a: gấp đôi; m, n: số nguyên; bắt đầu a: = 1; m: = 0; n: = 0; trong khi đúng thì làm bắt đầu nếu a <r thì bắt đầu m: = m + 1; a: = a * 2; kết thúc khác bắt đầu n: = n + 1; a: = a / 3; kết thúc; if abs (ra) <eps then Break; kết thúc; Writeln (r, '= 2 ^', m, '/ 3 ^', n, '=', a); kết thúc;
bắt đầu test (sqrt (2), 1.E-3); kết thúc.
Đầu ra:
1.41421356237310E + 0000 = 2 ^ 243/3 ^ 153 = 1.41493657935359E + 0000
CẬP NHẬT.
Câu trả lời của lhf trông giống như một bằng chứng rất ngắn gọn. Nhưng đối với tôi - với tư cách là một nhà vật lý học đã nghỉ hưu - thì điều đó hơi vượt quá khả năng hiểu của tôi.
Hơn nữa, nó để lại một số vấn đề chưa được xử lý. Người ta có thể hỏi ví dụ như liệu có ước tính cho$m$ và $n$ khi nào $r$ và $\epsilon$ được tặng.
Ghi chú. Câu hỏi cũng có thể được xây dựng dưới dạng: Liệu bất kỳ số thực dương nào có thể được gần đúng như$3^m/2^n$ với $(m,n)$đủ lớn? Điều này cũng giống như cho phép số nguyên âm với công thức ban đầu. Trong hình thức này, nó cho thấy một số điểm tương đồng với (trong) bài toán Collatz nổi tiếng .
BIÊN TẬP.
Theo gợi ý của các câu trả lời, một cách tiếp cận với logarit có thể hiệu quả hơn:
chương trình vàers;
thủ tục proef (r: double; eps: double); var a, l2, l3, lr: gấp đôi; m, n: số nguyên; bắt đầu l2: = ln (2); l3: = ln (3); lr: = ln (r); a: = 0; m: = 0; n: = 0; trong khi đúng thì làm bắt đầu a: = m * l2 - n * l3 - lr; if abs (a) <eps then Break; if a <0 then m: = m + 1 else n: = n + 1; kết thúc; Writeln (r, '= 2 ^', m, '/ 3 ^', n, '=', exp (a) * r); kết thúc;
bắt đầu proef (sqrt (2), 1.E-3); proef (sqrt (2), 1.E-9); kết thúc.
Đầu ra:
1.41421356237310E + 0000 = 2 ^ 243/3 ^ 153 = 1.41493657935356E + 0000 1.41421356237310E + 0000 = 2 ^ 911485507/3 ^ 575083326 = 1.41421356125035E + 0000
Dòng đầu tiên trong đầu ra gần giống với kết quả thu được trước đó.
Dòng cuối cùng trong kết quả cho thấy rằng cách tiếp cận thứ hai thực sự hiệu quả hơn.
Lỗi đóng vai trò như nhau trong cả hai cách tiếp cận. Ồ, gần như vậy. Chúng ta hãy nhìn vào những nơi mà 'Break's là. Chương trình đầu tiên:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$ Chương trình thứ hai: $$ -\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 $$ Vì thế $\epsilon$trong chương trình đầu tiên là một lỗi tuyệt đối , trong khi$\epsilon$trong chương trình thứ hai là một lỗi tương đối .
Tiếp tục câu chuyện tại:
Liệu cây Stern-Brocot có thể được sử dụng để hội tụ tốt hơn$2^m/3^n$?
Trả lời
Có, luôn có các giải pháp $(m, n)$ cho bất kỳ thực tích cực nào $r$ và $\epsilon$ cho $$\left| r - \frac{2^m}{3^n} \right| < \epsilon$$Và có một nhiều cách hiệu quả hơn để tìm những giải pháp hơn bước qua$m$ và $n$ từng giá trị một.
Chúng ta có $$r \approx 2^m/3^n$$ Tính logarit, $$\log r \approx m\log 2 - n\log 3$$ $$\log r/\log 2\approx m - n\log 3 / \log 2$$ I E, $$\log_2 r\approx m - n\log_2 3$$
[Tình cờ, $$1 = \frac m{\log_2r}-\frac n{\log_3r}$$ đó là một dòng trong $(m,n)$ máy bay với $m$ chặn lại $\log_2r$ và $n$ chặn lại $-\log_3r$. Chúng tôi muốn tìm khi nào dòng đó chuyển gần đến số nguyên$(m, n)$ điểm mạng tinh thể].
Chúng ta có thể tìm các giá trị gần đúng hợp lý cho cả logarit cơ số 2 đó với độ chính xác mong muốn. Tuy nhiên, để thỏa mãn phương trình đó với số nguyên $m$ và $n$, mẫu số của các giá trị gần đúng của chúng ta phải tương xứng.
Để cho $$\log_2 r = f \approx s/t$$ và $$\log_2 3 \approx p/q$$ với các phân số ở mức thấp nhất, tức là, $\gcd(s,t)=gcd(p,q)=1$.
Sau đó $$\frac st = m - n \frac pq$$ $$sq = (qm - pn)t$$ Như vậy $t|sq$. Nhưng$s$ & $t$ là coprime, do đó $t|q$.
Để cho $q=tk$. $$f \approx \frac st = \frac{sk}{tk}=\frac{sk}{q}=\frac dq$$ cho một số số nguyên $d$.
Vì vậy, đối với một giá trị gần đúng nhất định $\frac pq$ đến $\log_2 3$, các giá trị gần đúng hợp lý tốt nhất để $f$ với mẫu số tương xứng là $\frac{d_0}q$ và $\frac{d_1}q$, Ở đâu $d_0=\lfloor fq\rfloor$ và $d_1=\lceil fq\rceil$. Đó là,$$\frac{d_0}q \le f \le \frac{d_1}q$$ Nếu $f$ là hợp lý (ví dụ: khi $r=\sqrt 2$), sau đó $d_0$ và $d_1$ có thể bằng nhau.
Vì vậy, cho một $p$ & $q$ chúng ta chỉ cần tìm số nguyên $m$ & $n$ giải phương trình đã sửa đổi của chúng tôi $$\frac dq = m - n \frac pq$$ $$d=qm-pn$$ cho cả hai $d_0$ và $d_1$. Có các giải pháp cho bất kỳ số nguyên nào$d$ bởi vì $p$ & $q$là đồng chuẩn. Và các giải pháp đó có thể được tìm thấy bằng cách sử dụng thuật toán Euclid mở rộng .
Nhưng chúng ta cũng cần tìm $p$ & $q$. Điều đó có thể được thực hiện bằng cách sử dụng các hàm chuyển đổi của việc mở rộng phân số liên tục của$\log_2 3$. Thuật toán tiêu chuẩn để tính toán một phân số liên tục có liên quan chặt chẽ với thuật toán Euclid mở rộng và như bài báo Wikipedia giải thích (trong Định lý 3), nếu$n$hội tụ thứ của một phân số tiếp tục là $\frac{h_n}{k_n}$ sau đó $$k_nh_{n-1} - k_{n-1}h_n = (-1)^n$$ điều này cho phép chúng tôi tìm thấy $m$ và $n$ mà không cần thực hiện một phép tính toán Euclidean riêng biệt.
Phân số tiếp tục hội tụ $\frac hk$ của một số $x$ đưa ra giá trị xấp xỉ hợp lý tốt nhất cho $x$ cho bất kỳ mẫu số nào $\le k$. Lỗi là$$\left|x - \frac hk\right| \le \frac 1{k^2}$$và nó thường có thể tốt hơn nhiều. Ngược lại, sai số cho một giá trị gần đúng$\frac hk$ với mẫu số "ngẫu nhiên" (tức là, không phải là hội tụ phân số liên tục) thường xung quanh $\frac 1{2k}$.
Thật không may, vì nhu cầu về mẫu số tương xứng trong các phép tính gần đúng của chúng tôi với hai logarit, chúng tôi không nhận được đầy đủ $\frac 1{k^2}$lòng tốt. Nhưng chúng tôi nói chung trở nên tốt hơn$\frac 1{k}$.
Vì vậy, để tìm ra các giải pháp với lỗi tốt hơn một $\epsilon$, chúng ta chỉ cần nhìn vào những người chuyển đổi sang $\log_2 3$ với các mẫu số trong khu vực lân cận $\frac 1\epsilon$.
Đây là một số mã Sage / Python thực hiện nhiệm vụ đó. Sage là một tập hợp các thư viện toán học được xây dựng dựa trên ngôn ngữ lập trình Python phổ biến. Nó có số học chính xác tùy ý và các phương tiện để thực hiện đại số ký hiệu, nhưng tôi (hầu hết) đã tránh các tính năng Sage trong mã này (ngoài số học chính xác tùy ý), để giúp dễ dàng chuyển sang các ngôn ngữ khác, nếu muốn; Tôi cũng đã tránh hầu hết các "Pythonisms", ngoài khả năng của Python để trả về nhiều giá trị từ một hàm.
# 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
Đây là đầu ra của chương trình đó, tìm kiếm các giải pháp với $\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
Và đây là phiên bản trực tiếp mà bạn có thể chơi trên máy chủ SageMath. Mã của tôi không được lưu trữ trên máy chủ, nó được mã hóa trong URL.
Nếu bạn có những hành vi kỳ lạ với nhỏ $\epsilon$, hãy thử tăng số lượng bitsbiến toàn cục (ở đầu tệp). Cài đặt mặc định là 53 sẽ ổn đối với$\epsilon > 10^{-8}$hoặc là. Bạn cũng có thể cần phải tăng depthphân số tiếp tục.
FWIW, $\log_2 3$khá quan trọng trong lý thuyết âm nhạc toán học về các thang âm đều . Thang âm 12 tiêu chuẩn sử dụng hội tụ$19/12$.
Để cho $G= \mathbb Z \log 2 + \mathbb Z \log 3$. Sau đó$G$ là một nhóm phụ phụ gia của $\mathbb R$. Từ$\log 2 / \log 3$ là phi lý, $G$không thể là chu kỳ [1] và vì vậy phải dày đặc [2]. Vì thế,$\log r$ được ước lượng tùy ý bởi các phần tử của $G$.
[1] Nếu $G = \mathbb Z \theta $, sau đó $\log 2 = a \theta$ và $\log 3 = b \theta$ và vì thế $\log 2 / \log 3 = a/b $ là hợp lý.
[2] Xem https://math.stackexchange.com/a/889775/589
Heuristics của một bằng chứng khác
Bổ đề 1.
Phân số$2^m/3^n$ tất cả đều ở giữa $r/3$ và $2r$.
Bằng chứng.
Theo chương trình - như hiển thị trong câu hỏi. Bất kỳ phân số nào nhỏ hơn$r$ được nhân với $2$, vì thế $r.2$là giới hạn trên cho các phân số này. Bất kỳ phân số nào lớn hơn$r$ được chia bởi $3$, vì thế $r/3$là giới hạn dưới cho các phân số này. Không thể có phân số nào khác, ngoại trừ khi bắt đầu lặp lại.$$ r/3 < \frac{2^m}{3^n} < 2r $$ Bổ đề 2.
Trong dãy$2^m/3^n \to r$không có hai phân số nào giống nhau.
Bằng chứng.
Giả sử rằng chúng ta có$2^{m_1}/3^{n_1} = 2^{m_2}/3^{n_2}$.
Ba trường hợp được phân biệt:
- $m_1 \neq m_2$ và $n_1 = n_2$. Sau đó$2^{m_1} = 2^{m_2}$ vì thế $m_1 = m_2$. Sự mâu thuẫn.
- $n_1 \neq n_2$ và $m_1 = m_2$. Sau đó$1/3^{n_1} = 1/3^{n_2}$ vì thế $n_1 = n_2$. Sự mâu thuẫn.
- $m_1 \neq m_2$ và $n_1 \neq n_2$. Sau đó chúng tôi có:$$ \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)} $$ Nhưng $\,\ln(3)/\ln(2)\,$không phải là một số hữu tỉ. Sự mâu thuẫn.
Vì vậy, những gì chúng ta có là một loạt các phân số, tất cả đều khác nhau, nhưng chúng phải vừa với khoảng $\,]r/3,2r[\,$. Điều này có nghĩa là các phân số trở nên đông đúc. Hãy làm một bức tranh về quá trình lặp, phiên bản logarit. Đường màu đỏ được đưa ra bởi$\,\color{red}{\ln(3)y=\ln(2)x-\ln(r)}\,$, vòng tròn nhỏ là phân số, được ánh xạ trên lưới $\,m/n \to (m,n)\,$, massively black filled dots are the fractions in the iteration process, while increasing $m$ and $n$ with increments one at a time. The iterations domain is limited by: $\,\color{blue}{-\ln(2)\lt\ln(3)y-\ln(2)x+\ln(r)\lt\ln(3)}\,$. In our case $r = 100$. Mind the sequence at the start.
So it seems that there must be quite some fractions nearby the red line, rerpesenting the real number $r$ in question.
How can we be sure about this? Let's make picture of the crowding of the approximations $a$ in the interval $\,]r/3,2r[\,$, logarithmic scale: $$ a = m\ln(2)-n\ln(3)-\ln(r) \quad \mbox{with} \quad -\ln(3) < a < \ln(2) $$ The red line is where $a = 0$, the desired value.
Further numerical/graphical experiments reveal that the distribution of the fractions seems to be uniform. While seeking further confirmation of this we have done the following, speaking in terms of (Delphi) Pascal:
program opnieuw;
procedure interval(var A,B : double); var h : double; begin A := Random; B := Random; if A > B then begin h := B; B := A; A := h; end; end;
procedure proef(r : double); const veel : integer = 1000000000; var x,l2,l3,lr,A,B : double; m,n,tel,t : integer; begin l2 := ln(2); l3 := ln(3); lr := ln(r); interval(A,B); A := -l3 + A*(l2+l3); B := -l3 + B*(l2+l3); m := 0; n := 0; tel := 0; t := 0; while tel < veel do begin x := m*l2 - n*l3 - lr; if x < 0 then m := m + 1 else n := n + 1; if (-l3 < x) and (x < +l2) then tel := tel + 1; if (A < x) and (x < B) then t := t + 1; end; Writeln((B-A)/(l2+l3),' = ',t/tel); end;
begin Random; Random; proef(1000); proef(0.001); proef(sqrt(2)); proef(1/sqrt(2)); while true do proef(Random); end.
Explanation. Make random intervals $\,]A,B[\,$ inside $\,]-\ln(3),+\ln(2)[\,$. The length of the latter interval is $\,\ln(3)+\ln(2)=\ln(6)\,$, the lenghs of the former are $\,(B-A)\,$. Count the (logarithms $x$ of the) fractions $\,(2^n/3^n)/r\,$ in both intervals. Let $N$ be the total number (tel) of iterands and $n$ be the number (t) of iterands in $\,]A,B[\,$. Then the distribution of the approximations $x$ is uniform if and only if: $$ \lim_{N\to\infty}\frac{n}{N} = \frac{B-A}{\ln(6)} $$ Let's check. Output after a billion iterations each line:
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 = ....
But how can we prove that it is a uniform distribution?