Dapatkah setiap real positif didekati sebagai $2^m/3^n$dengan $(m,n)$cukup besar?

Question

Dugaan.
Ada bilangan bulat positif$(m,n)$cukup besar, sehingga untuk sembarang bilangan real positif$r$dan kesalahan yang diberikan$\epsilon$:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Ada bukti numerik untuk dugaan ini. saya telah mencoba$r = \sqrt{2}$dan$\epsilon = 10^{-3}$.
Di bawah ini adalah sedikit program Delphi Pascal dengan output yang menyertainya.
Tapi .. ada yang bisa membuktikan dugaannya?

program terpisah;

prosedur tes(r : ganda; eps : ganda);
var
  a : ganda;
  m,n : bilangan bulat;
mulai
  a := 1;
  m := 0; n := 0;
  sementara benar lakukan
  mulai
    jika a < r maka
    mulai
      m := m + 1;
      a := a * 2;
    akhiri yang lain mulai
      n := n + 1;
      a := a / 3;
    akhir;
    jika abs(ra) < eps maka Break;
  akhir;
  Writeln(r,' = 2^',m,'/3^',n,' =',a);
akhir;

mulai
  tes(sqrt(2),1.E-3);
akhir.

Keluaran:

1,41421356237310E+0000 = 2^243/3^153 = 1,41493657935359E+0000

MEMPERBARUI.
Jawaban oleh lhf memang terlihat seperti bukti yang sangat ringkas. Tapi bagi saya - sebagai pensiunan fisikawan pendidikan - itu sedikit di luar pemahaman.
Selain itu, ia meninggalkan beberapa masalah yang tidak tersentuh. Seseorang mungkin bertanya misalnya apakah ada perkiraan untuk$m$dan$n$Kapan$r$dan$\epsilon$diberikan.

Catatan. Pertanyaannya juga dapat dirumuskan sebagai: Dapatkah setiap real positif didekati sebagai$3^m/2^n$dengan$(m,n)$cukup besar? Yang sama dengan mengizinkan bilangan bulat negatif dengan formulasi asli. Dalam bentuk ini, ini menunjukkan beberapa kemiripan dengan masalah Collatz (dalam) yang terkenal .

EDIT.
Seperti yang disarankan oleh jawaban, pendekatan dengan logaritma bisa lebih efektif:

program anders;

prosedur proef(r : dobel; eps : dobel);
var
  a,l2,l3,lr : dobel;
  m,n : bilangan bulat;
mulai
  l2 := ln(2); l3 := ln(3);
  lr := ln(r); a := 0;
  m := 0; n := 0;
  sementara benar lakukan
  mulai
    a := m*l2 - n*l3 - lr;
    jika abs(a) < eps maka Break;
    jika a < 0 maka m := m + 1 lain n := n + 1;
  akhir;
  Writeln(r,' = 2^',m,'/3^',n,' =',exp(a)*r);
akhir;

mulai
  proef(sqrt(2),1.E-3);
  proef(sqrt(2),1.E-9);
akhir.

Keluaran:

1,41421356237310E+0000 = 2^243/3^153 = 1,41493657935356E+0000
 1,41421356237310E+0000 = 2^911485507/3^575083326 = 1,41421356125035E+0000

Baris pertama dalam output hampir identik dengan hasil yang diperoleh sebelumnya.
Baris terakhir dalam output menunjukkan bahwa pendekatan terakhir memang lebih efektif.
Kesalahan memainkan peran yang sama dalam kedua pendekatan. Yah, hampir. Mari kita lihat tempat-tempat di mana 'Break's berada. Program pertama:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Program kedua:$$ -\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 $$Jadi$\epsilon$pada program pertama adalah kesalahan mutlak , sedangkan$\epsilon$dalam program kedua adalah kesalahan relatif .

Melanjutkan cerita di:
Dapatkah pohon Stern-Brocot digunakan untuk konvergensi yang lebih baik?$2^m/3^n$?

Answer 1

Ya, selalu ada solusi$(m, n)$untuk setiap real positif$r$dan$\epsilon$untuk$$\left| r - \frac{2^m}{3^n} \right| < \epsilon$$Dan ada cara yang jauh lebih efisien untuk menemukan solusi tersebut daripada melangkah melalui$m$dan$n$nilai satu per satu.

Kita punya$$r \approx 2^m/3^n$$Mengambil logaritma,$$\log r \approx m\log 2 - n\log 3$$ $$\log r/\log 2\approx m - n\log 3 / \log 2$$yaitu,$$\log_2 r\approx m - n\log_2 3$$

[Kebetulan,$$1 = \frac m{\log_2r}-\frac n{\log_3r}$$yang merupakan garis dalam$(m,n)$pesawat dengan$m$mencegat$\log_2r$dan$n$mencegat$-\log_3r$. Kami ingin mencari kapan garis itu mendekati bilangan bulat$(m, n)$titik kisi].

Kita dapat menemukan aproksimasi rasional untuk kedua logaritma basis 2 tersebut hingga presisi yang diinginkan. Namun, untuk memenuhi persamaan itu dengan bilangan bulat $m$dan$n$, penyebut dari aproksimasi kita harus sepadan.

Membiarkan$$\log_2 r = f \approx s/t$$dan$$\log_2 3 \approx p/q$$dengan pecahan berada dalam suku terkecil, yaitu,$\gcd(s,t)=gcd(p,q)=1$.

Kemudian$$\frac st = m - n \frac pq$$ $$sq = (qm - pn)t$$Dengan demikian$t|sq$. Tetapi$s$&$t$adalah koprima, maka$t|q$.

Membiarkan$q=tk$.$$f \approx \frac st = \frac{sk}{tk}=\frac{sk}{q}=\frac dq$$untuk beberapa bilangan bulat$d$.

Jadi, untuk pendekatan yang diberikan$\frac pq$ke$\log_2 3$, pendekatan rasional terbaik untuk$f$dengan penyebut yang sepadan adalah$\frac{d_0}q$dan$\frac{d_1}q$, di mana$d_0=\lfloor fq\rfloor$dan$d_1=\lceil fq\rceil$. Itu adalah,$$\frac{d_0}q \le f \le \frac{d_1}q$$Jika$f$adalah rasional (misalnya, ketika$r=\sqrt 2$), kemudian$d_0$dan$d_1$mungkin setara.

Jadi untuk yang diberikan$p$&$q$kita hanya perlu mencari bilangan bulat$m$&$n$yang menyelesaikan persamaan revisi kami$$\frac dq = m - n \frac pq$$ $$d=qm-pn$$untuk keduanya$d_0$dan$d_1$. Ada solusi untuk bilangan bulat apa pun$d$karena$p$&$q$adalah koprima. Dan solusi tersebut dapat ditemukan dengan menggunakan algoritma Euclidean yang diperluas .

Tapi kita juga perlu menemukan yang cocok$p$&$q$. Itu dapat dilakukan dengan menggunakan konvergen dari ekspansi pecahan lanjutan dari$\log_2 3$. Algoritme standar untuk menghitung pecahan lanjutan terkait erat dengan algoritme Euclidean yang diperluas, dan seperti yang dijelaskan dalam artikel Wikipedia (dalam Teorema 3), jika$n$konvergen ke th dari pecahan lanjutan adalah$\frac{h_n}{k_n}$kemudian$$k_nh_{n-1} - k_{n-1}h_n = (-1)^n$$yang memungkinkan kita untuk menemukan$m$dan$n$tanpa melakukan perhitungan algoritma Euclidean terpisah.

Konvergen pecahan lanjutan$\frac hk$dari sebuah angka$x$memberikan pendekatan rasional terbaik untuk$x$untuk setiap penyebut$\le k$. Kesalahannya adalah$$\left|x - \frac hk\right| \le \frac 1{k^2}$$dan seringkali bisa jauh lebih baik. Sebaliknya, kesalahan untuk aproksimasi$\frac hk$dengan penyebut "acak" (yaitu, bukan pecahan konvergen lanjutan) umumnya sekitar$\frac 1{2k}$.

Sayangnya, karena kebutuhan penyebut yang sepadan dalam pendekatan kami untuk dua logaritma, kami tidak mendapatkan penuh$\frac 1{k^2}$kebaikan. Tapi kami umumnya menjadi lebih baik dari$\frac 1{k}$.

Jadi untuk menemukan solusi dengan kesalahan yang lebih baik daripada yang diberikan$\epsilon$, kita hanya perlu melihat konvergen untuk$\log_2 3$dengan penyebut di sekitar$\frac 1\epsilon$.

Berikut adalah beberapa kode Sage/Python yang melakukan tugas itu. Sage adalah kumpulan perpustakaan matematika yang dibangun di atas bahasa pemrograman Python yang populer. Ini memiliki aritmatika presisi arbitrer, dan fasilitas untuk melakukan aljabar simbolis, tetapi saya (kebanyakan) menghindari fitur Sage dalam kode ini (terlepas dari aritmatika presisi arbitrer), untuk mempermudah port ke bahasa lain, jika diinginkan; Saya juga menghindari sebagian besar "Pythonisms", selain dari kemampuan Python untuk mengembalikan banyak nilai dari suatu fungsi.

# 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

Inilah output dari program itu, mencari solusi dengan$\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

Dan ini adalah versi langsung yang dapat Anda mainkan di server SageMath. Kode saya tidak disimpan di server, itu dikodekan dalam URL.

Jika Anda mendapatkan perilaku aneh dengan kecil$\epsilon$, coba tambah jumlah bitsvariabel global (di bagian atas file). Pengaturan default 53 seharusnya baik-baik saja untuk$\epsilon > 10^{-8}$atau lebih. Anda mungkin juga perlu meningkatkan depthpecahan lanjutan.

---

FWIW,$\log_2 3$agak penting dalam teori musik matematika dari tangga nada yang sama-sama marah . Tangga nada 12 nada standar menggunakan konvergen$19/12$.

Answer 2

Membiarkan$G= \mathbb Z \log 2 + \mathbb Z \log 3$. Kemudian$G$adalah subgrup tambahan dari$\mathbb R$. Sejak$\log 2 / \log 3$tidak rasional,$G$tidak bisa siklik [1] dan harus padat [2]. Karena itu,$\log r$secara sewenang-wenang didekati oleh elemen dari$G$.

[1] Jika$G = \mathbb Z \theta $, kemudian$\log 2 = a \theta$dan$\log 3 = b \theta$dan sebagainya$\log 2 / \log 3 = a/b $adalah rasional.

[2] Lihathttps://math.stackexchange.com/a/889775/589

Answer 3

Heuristik dari bukti lain

Lemma 1.
Pecahan$2^m/3^n$semua berada di antara$r/3$dan$2r$.
Bukti.
Menurut program - seperti yang ditampilkan dalam pertanyaan. Setiap pecahan yang lebih kecil dari$r$dikalikan dengan$2$, jadi$r.2$adalah batas atas untuk pecahan ini. Setiap pecahan yang lebih besar dari$r$dibagi dengan$3$, jadi$r/3$adalah batas bawah untuk pecahan ini. Tidak boleh ada pecahan lain, kecuali saat iterasi dimulai.$$ r/3 < \frac{2^m}{3^n} < 2r $$ Lemma 2.
Dalam urutan$2^m/3^n \to r$tidak ada dua pecahan yang sama.
Bukti.
Misalkan kita memiliki$2^{m_1}/3^{n_1} = 2^{m_2}/3^{n_2}$.
Tiga kasus dibedakan:

1. $m_1 \neq m_2$dan$n_1 = n_2$. Kemudian$2^{m_1} = 2^{m_2}$karenanya$m_1 = m_2$. Kontradiksi.
   
2. $n_1 \neq n_2$dan$m_1 = m_2$. Kemudian$1/3^{n_1} = 1/3^{n_2}$karenanya$n_1 = n_2$. Kontradiksi.
   
3. $m_1 \neq m_2$dan$n_1 \neq n_2$. Kemudian kita memiliki:$$ \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)} $$Tetapi$\,\ln(3)/\ln(2)\,$bukan bilangan rasional. Kontradiksi.
   

Jadi yang kita miliki adalah sekelompok pecahan, semuanya berbeda, tetapi mereka harus sesuai dengan interval$\,]r/3,2r[\,$. Ini berarti pecahan menjadi ramai. Mari kita buat gambaran proses iterasi, versi logaritma. Garis merah diberikan oleh$\,\color{red}{\ln(3)y=\ln(2)x-\ln(r)}\,$, lingkaran kecil adalah pecahan, dipetakan pada grid$\,m/n \to (m,n)\,$, titik-titik terisi hitam besar adalah pecahan dalam proses iterasi, sambil meningkat$m$dan$n$dengan kenaikan satu per satu. Domain iterasi dibatasi oleh:$\,\color{blue}{-\ln(2)\lt\ln(3)y-\ln(2)x+\ln(r)\lt\ln(3)}\,$. Dalam kasus kami$r = 100$. Perhatikan urutan di awal.

Jadi sepertinya pasti ada beberapa pecahan di dekat garis merah, yang mewakili bilangan asli$r$dalam pertanyaan.
Bagaimana kita bisa yakin tentang ini? Mari kita membuat gambar dari crowding dari aproksimasi$a$dalam interval$\,]r/3,2r[\,$, skala logaritmik:$$ a = m\ln(2)-n\ln(3)-\ln(r) \quad \mbox{with} \quad -\ln(3) < a < \ln(2) $$Garis merah dimana$a = 0$, nilai yang diinginkan.

Eksperimen numerik/grafis lebih lanjut mengungkapkan bahwa distribusi pecahan tampaknya seragam . Sambil mencari konfirmasi lebih lanjut tentang hal ini, kami telah melakukan hal berikut, berbicara dalam istilah (Delphi) Pascal:

pilihan program;

interval prosedur(var A,B : double);
var
  h : ganda;
mulai
  J := Acak; B := Acak;
  jika A > B maka
  mulai
    j := B; B := A; A := j;
  akhir;
akhir;

prosedur proef(r : ganda);
konstan
  velg : bilangan bulat = 1000000000;
var
  x,l2,l3,lr,A,B : dobel;
  m,n,tel,t : bilangan bulat;
mulai
  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;
  telp := 0; t := 0;
  sementara tel < veel do
  mulai
    x := m*l2 - n*l3 - lr;
    jika x < 0 maka m := m + 1 lain n := n + 1;
    jika (-l3 < x) dan (x < +l2) maka telp := telp + 1;
    jika (A < x) dan (x < B) maka t := t + 1;
  akhir;
  Writeln((BA)/(l2+l3),' = ',t/tel);
akhir;

mulai
  Acak; Acak;
  bukti(1000);
  bukti(0.001);
  bukti(persegi(2));
  bukti(1/persegi(2));
  sementara benar lakukan
    proef(Acak);
akhir.

Penjelasan. Buat interval acak$\,]A,B[\,$di dalam$\,]-\ln(3),+\ln(2)[\,$. Panjang interval yang terakhir adalah$\,\ln(3)+\ln(2)=\ln(6)\,$, panjang yang pertama adalah$\,(B-A)\,$. Hitung (logaritma$x$dari) pecahan$\,(2^n/3^n)/r\,$di kedua interval. Membiarkan$N$menjadi jumlah total (tel) dari iterand dan$n$menjadi jumlah (t) iterand dalam$\,]A,B[\,$. Kemudian distribusi perkiraan$x$seragam jika dan hanya jika:$$ \lim_{N\to\infty}\frac{n}{N} = \frac{B-A}{\ln(6)} $$Mari kita periksa. Output setelah satu miliar iterasi setiap baris:

6.58467502100393E-0001 = 6.584675000000000E-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 = ....

Tetapi bagaimana kita dapat membuktikan bahwa itu adalah distribusi yang seragam?