Si può approssimare un reale positivo come $2^m/3^n$insieme a $(m,n)$abbastanza grande?
Congetturare.
Esistono numeri interi positivi$(m,n)$abbastanza grande, tale che per qualsiasi numero reale positivo$r$e un dato errore$\epsilon$:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Ci sono prove numeriche per questa congettura. Ho provato$r = \sqrt{2}$e$\epsilon = 10^{-3}$.
Di seguito è riportato un piccolo programma Delphi Pascal con l'output di accompagnamento.
Ma .. qualcuno può provare la congettura?
programma a parte;
procedura test(r : double; eps : double); var un doppio; m,n : intero; inizio a := 1; m := 0; n := 0; mentre vero fare inizio se a < r allora inizio m := m + 1; a := a * 2; fine altrimenti inizia n := n + 1; a := a / 3; fine; se abs(ra) < eps allora Break; fine; Scriviln(r,' = 2^',m,'/3^',n,' =',a); fine;
inizio test(sqrt(2),1.E-3); fine.
Produzione:
1.41421356237310E+0000 = 2^243/3^153 = 1.41493657935359E+0000
AGGIORNARE.
La risposta di lhf sembra una prova molto concisa. Ma per me - come fisico in pensione per istruzione - è un po' oltre la comprensione.
Inoltre, lascia inalterati alcuni problemi. Ci si potrebbe chiedere ad esempio se ci sono preventivi per$m$e$n$quando$r$e$\epsilon$sono dati.
Nota. La domanda può anche essere formulata come: qualsiasi reale positivo può essere approssimato come$3^m/2^n$insieme a$(m,n)$abbastanza grande? Che equivale a consentire numeri interi negativi con la formulazione originale. In questa forma, mostra una certa somiglianza con il (in)famoso problema di Collatz .
MODIFICARE.
Come suggerito dalle risposte, un approccio con logaritmi potrebbe essere più efficace:
programma anders;
procedura proef(r : double; eps : double); var a,l2,l3,lr : doppio; m,n : intero; inizio l2 := ln(2); l3 := ln(3); lr := ln(r); a := 0; m := 0; n := 0; mentre vero fare inizio a := m*l2 - n*l3 - lr; se abs(a) < eps allora Break; se a < 0 allora m := m + 1 altrimenti n := n + 1; fine; Scriviln(r,' = 2^',m,'/3^',n,' =',exp(a)*r); fine;
inizio proef(sqrt(2),1.E-3); proef(sqrt(2),1.E-9); fine.
Produzione:
1.41421356237310E+0000 = 2^243/3^153 = 1.41493657935356E+0000 1.41421356237310E+0000 = 2^911485507/3^575083326 = 1.41421356125035E+0000
La prima riga nell'output è quasi identica al risultato ottenuto in precedenza.
L'ultima riga dell'output mostra che quest'ultimo approccio è effettivamente più efficace.
L'errore gioca lo stesso ruolo in entrambi gli approcci. Vabbè, quasi. Diamo un'occhiata ai luoghi in cui si trovano i 'Break's. Primo programma:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Secondo programma:$$ -\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 $$Così$\epsilon$nel primo programma è un errore assoluto , mentre$\epsilon$nel secondo programma è un errore relativo .
Storia continua su:
L'albero di Stern-Brocot può essere impiegato per una migliore convergenza di$2^m/3^n$?
Risposte
Sì, ci sono sempre soluzioni$(m, n)$per qualsiasi reale positivo$r$e$\epsilon$per$$\left| r - \frac{2^m}{3^n} \right| < \epsilon$$E c'è un modo molto più efficiente per trovare quelle soluzioni che passare attraverso$m$e$n$valori uno per uno.
abbiamo$$r \approx 2^m/3^n$$Prendendo i logaritmi,$$\log r \approx m\log 2 - n\log 3$$ $$\log r/\log 2\approx m - n\log 3 / \log 2$$cioè,$$\log_2 r\approx m - n\log_2 3$$
[Per inciso,$$1 = \frac m{\log_2r}-\frac n{\log_3r}$$che è una linea nel$(m,n)$aereo con$m$intercettare$\log_2r$e$n$intercettare$-\log_3r$. Vogliamo trovare quando quella riga passa vicino a intero$(m, n)$punti del reticolo].
Possiamo trovare approssimazioni razionali per entrambi i logaritmi in base 2 con la precisione desiderata. Tuttavia, per soddisfare quell'equazione con intero $m$e$n$, i denominatori delle nostre approssimazioni devono essere proporzionati.
Permettere$$\log_2 r = f \approx s/t$$e$$\log_2 3 \approx p/q$$con le frazioni in termini più bassi, cioè$\gcd(s,t)=gcd(p,q)=1$.
Quindi$$\frac st = m - n \frac pq$$ $$sq = (qm - pn)t$$così$t|sq$. Ma$s$&$t$sono coprimi, quindi$t|q$.
Permettere$q=tk$.$$f \approx \frac st = \frac{sk}{tk}=\frac{sk}{q}=\frac dq$$per qualche numero intero$d$.
Quindi, per una data approssimazione$\frac pq$a$\log_2 3$, le migliori approssimazioni razionali a$f$con denominatori proporzionati sono$\frac{d_0}q$e$\frac{d_1}q$, dove$d_0=\lfloor fq\rfloor$e$d_1=\lceil fq\rceil$. Questo è,$$\frac{d_0}q \le f \le \frac{d_1}q$$Se$f$è razionale (es. quando$r=\sqrt 2$), poi$d_0$e$d_1$può essere uguale.
Quindi per un dato di fatto$p$&$q$dobbiamo solo trovare numeri interi$m$&$n$che risolvono la nostra equazione rivista$$\frac dq = m - n \frac pq$$ $$d=qm-pn$$per entrambi$d_0$e$d_1$. Ci sono soluzioni per qualsiasi numero intero$d$perché$p$&$q$sono coprimi. E queste soluzioni possono essere trovate usando l' algoritmo euclideo esteso .
Ma dobbiamo anche trovare adatto$p$&$q$. Ciò può essere fatto utilizzando i convergenti dell'espansione continua della frazione di$\log_2 3$. L'algoritmo standard per calcolare una frazione continua è strettamente correlato all'algoritmo euclideo esteso e, come spiega l'articolo di Wikipedia (nel Teorema 3), se il$n$esimo convergente di una frazione continua è$\frac{h_n}{k_n}$poi$$k_nh_{n-1} - k_{n-1}h_n = (-1)^n$$che ci permette di trovare$m$e$n$senza eseguire un calcolo dell'algoritmo euclideo separato.
La frazione continua convergente$\frac hk$di un numero$x$fornisce le migliori approssimazioni razionali a$x$per qualsiasi denominatore$\le k$. L'errore è$$\left|x - \frac hk\right| \le \frac 1{k^2}$$e spesso può essere molto meglio. Al contrario, l'errore per un'approssimazione$\frac hk$con un denominatore "casuale" (cioè, non una frazione continua convergente) è generalmente intorno$\frac 1{2k}$.
Sfortunatamente, a causa della necessità di denominatori proporzionati nelle nostre approssimazioni ai due logaritmi, non otteniamo il pieno$\frac 1{k^2}$bontà. Ma generalmente miglioriamo di$\frac 1{k}$.
Quindi per trovare soluzioni con un errore migliore di un dato$\epsilon$, dobbiamo solo guardare i convergenti a$\log_2 3$con denominatori nelle vicinanze di$\frac 1\epsilon$.
Ecco del codice Sage / Python che esegue tale attività. Sage è una raccolta di librerie matematiche basate sul popolare linguaggio di programmazione Python. Ha un'aritmetica di precisione arbitraria e funzionalità per eseguire l'algebra simbolica, ma ho (per lo più) evitato le funzionalità di Sage in questo codice (a parte l'aritmetica di precisione arbitraria), per semplificare il porting in altri linguaggi, se lo si desidera; Ho anche evitato la maggior parte dei "pitonismi", a parte la capacità di Python di restituire più valori da una funzione.
# 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
Ecco l'output di quel programma, alla ricerca di soluzioni con$\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
Ed ecco una versione live con cui puoi giocare sul server SageMath. Il mio codice non è memorizzato sul server, è codificato nell'URL.
Se ottieni un comportamento strano con il piccolo$\epsilon$, prova ad aumentare il numero della bitsvariabile globale (nella parte superiore del file). L'impostazione predefinita di 53 dovrebbe essere ok$\epsilon > 10^{-8}$o giù di lì. Potrebbe anche essere necessario aumentare la depthfrazione continua.
FWW,$\log_2 3$è piuttosto importante nella teoria musicale matematica delle scale equamente temperate . La scala standard a 12 toni utilizza il convergente$19/12$.
Permettere$G= \mathbb Z \log 2 + \mathbb Z \log 3$. Quindi$G$è un sottogruppo additivo di$\mathbb R$. Da quando$\log 2 / \log 3$è irrazionale,$G$non può essere ciclico [1] e quindi deve essere denso [2]. Perciò,$\log r$è arbitrariamente approssimato da elementi di$G$.
[1] Se$G = \mathbb Z \theta $, poi$\log 2 = a \theta$e$\log 3 = b \theta$e così$\log 2 / \log 3 = a/b $è razionale.
[2] Vedihttps://math.stackexchange.com/a/889775/589
Euristica di un'altra dimostrazione
Lemma 1.
Le frazioni$2^m/3^n$sono tutti in mezzo$r/3$e$2r$.
Prova.
Secondo il programma - come mostrato nella domanda. Qualsiasi frazione inferiore a$r$viene moltiplicato per$2$, così$r.2$è un limite superiore per queste frazioni. Qualsiasi frazione maggiore di$r$è diviso per$3$, così$r/3$è un limite inferiore per queste frazioni. Non possono esserci altre frazioni, tranne quando iniziano le iterazioni.$$ r/3 < \frac{2^m}{3^n} < 2r $$ Lemma 2.
Nella sequenza$2^m/3^n \to r$non ci sono due frazioni uguali.
Prova.
Supponiamo di averlo$2^{m_1}/3^{n_1} = 2^{m_2}/3^{n_2}$.
Si distinguono tre casi:
- $m_1 \neq m_2$e$n_1 = n_2$. Quindi$2^{m_1} = 2^{m_2}$quindi$m_1 = m_2$. Contraddizione.
- $n_1 \neq n_2$e$m_1 = m_2$. Quindi$1/3^{n_1} = 1/3^{n_2}$quindi$n_1 = n_2$. Contraddizione.
- $m_1 \neq m_2$e$n_1 \neq n_2$. Poi abbiamo:$$ \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)} $$Ma$\,\ln(3)/\ln(2)\,$non è un numero razionale. Contraddizione.
Quindi quello che abbiamo sono un mucchio di frazioni, tutte diverse, ma devono rientrare nell'intervallo$\,]r/3,2r[\,$. Ciò significa che le frazioni diventano affollate. Facciamo un'immagine del processo di iterazione, versione logaritmica. La linea rossa è data da$\,\color{red}{\ln(3)y=\ln(2)x-\ln(r)}\,$, i cerchietti sono frazioni, mappate su una griglia$\,m/n \to (m,n)\,$, i punti massicciamente riempiti di nero sono le frazioni nel processo di iterazione, mentre aumentano$m$e$n$con incrementi uno alla volta. Il dominio delle iterazioni è limitato da:$\,\color{blue}{-\ln(2)\lt\ln(3)y-\ln(2)x+\ln(r)\lt\ln(3)}\,$. Nel nostro caso$r = 100$. Attenzione alla sequenza all'inizio.
Quindi sembra che ci debbano essere parecchie frazioni vicino alla linea rossa, che rappresentano il numero reale$r$in questione.
Come possiamo essere sicuri di questo? Facciamo un'immagine dell'affollamento delle approssimazioni$a$nell'intervallo$\,]r/3,2r[\,$, scala logaritmica:$$ a = m\ln(2)-n\ln(3)-\ln(r) \quad \mbox{with} \quad -\ln(3) < a < \ln(2) $$La linea rossa è dove$a = 0$, il valore desiderato.
Ulteriori esperimenti numerici/grafici rivelano che la distribuzione delle frazioni sembra essere uniforme . Pur cercando ulteriore conferma di ciò, abbiamo fatto quanto segue, parlando in termini di (Delphi) Pascal:
visione del programma;
intervallo di procedura(var A,B : double); var h : doppia; inizio A := Casuale; B := Casuale; se A > B allora inizio h := B; B := A; A := h; fine; fine;
procedura proef(r : double); cost velo : intero = 1000000000; var x,l2,l3,lr,A,B : doppio; m,n,tel,t : numero intero; inizio l2 := ln(2); l3 := ln(3); lr := ln(r); intervallo(A,B); A := -l3 + A*(l2+l3); B := -l3 + B*(l2+l3); m := 0; n := 0; tel := 0; t := 0; mentre tel < veel do inizio x := m*l2 - n*l3 - lr; se x < 0 allora m := m + 1 altrimenti n := n + 1; se (-l3 < x) e (x < +l2) allora tel := tel + 1; se (A < x) e (x < B) allora t := t + 1; fine; Scriviln((BA)/(l2+l3),' = ',t/tel); fine;
inizio Casuale; Casuale; prof(1000); prof(0,001); proef(sqrt(2)); proef(1/sqrt(2)); mentre vero fare proef (casuale); fine.
Spiegazione. Crea intervalli casuali$\,]A,B[\,$dentro$\,]-\ln(3),+\ln(2)[\,$. La lunghezza di quest'ultimo intervallo è$\,\ln(3)+\ln(2)=\ln(6)\,$, le lunghezze del primo sono$\,(B-A)\,$. Conta i (logaritmi$x$delle) frazioni$\,(2^n/3^n)/r\,$in entrambi gli intervalli. Permettere$N$essere il numero totale (tel) di iterandi e$n$essere il numero (t) di iterandi in$\,]A,B[\,$. Poi la distribuzione delle approssimazioni$x$è uniforme se e solo se:$$ \lim_{N\to\infty}\frac{n}{N} = \frac{B-A}{\ln(6)} $$Controlliamo. Output dopo un miliardo di iterazioni per riga:
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 = ....
Ma come possiamo dimostrare che è una distribuzione uniforme?