Tout réel positif peut-il être approximé comme $2^m/3^n$avec $(m,n)$assez large?
Conjecture.
Il existe des entiers positifs$(m,n)$assez grand, tel que pour tout nombre réel positif$r$et une erreur donnée$\epsilon$:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Il existe des preuves numériques de cette conjecture. j'ai essayé$r = \sqrt{2}$et$\epsilon = 10^{-3}$.
Vous trouverez ci-dessous un petit programme Delphi Pascal avec la sortie qui l'accompagne.
Mais .. quelqu'un peut-il prouver la conjecture?
programme à part;
test de procédure(r : double; eps : double); var un double; m,n : entier; commencer un := 1; m := 0; n := 0; alors que vrai faire commencer si a < r alors commencer m := m + 1; une := une * 2; fin sinon commencer n := n + 1; un := un / 3; finir; si abs(ra) < eps alors Break ; finir; Writeln(r,' = 2^',m,'/3^',n,' =',a); finir;
commencer test(sqrt(2),1.E-3); finir.
Sortir:
1.41421356237310E+0000 = 2^243/3^153 = 1.41493657935359E+0000
METTRE À JOUR.
La réponse de lhf ressemble à une preuve très concise. Mais pour moi - en tant que physicien à la retraite de formation - c'est un peu au-delà de l'entendement.
De plus, cela laisse quelques problèmes intacts. On pourrait se demander par exemple s'il existe des estimations pour$m$et$n$lorsque$r$et$\epsilon$sont donnés.
Noter. La question peut également être formulée comme suit : tout réel positif peut-il être approché comme$3^m/2^n$avec$(m,n)$assez large? Ce qui revient à autoriser les entiers négatifs avec la formulation d'origine. Sous cette forme, il présente une certaine ressemblance avec le (très) célèbre problème de Collatz .
ÉDITER.
Comme suggéré par les réponses, une approche avec des logarithmes pourrait être plus efficace :
programmes anders ;
procédure proef(r : double; eps : double); var a,l2,l3,lr : double; m,n : entier; commencer l2 := ln(2); l3 := ln(3); lr := ln(r); un := 0; m := 0; n := 0; alors que vrai faire commencer a := m*l2 - n*l3 - lr; si abs(a) < eps alors Break ; si a < 0 alors m := m + 1 sinon n := n + 1; finir; Writeln(r,' = 2^',m,'/3^',n,' =',exp(a)*r); finir;
commencer proef(sqrt(2),1.E-3); proef(sqrt(2),1.E-9); finir.
Sortir:
1.41421356237310E+0000 = 2^243/3^153 = 1.41493657935356E+0000 1.41421356237310E+0000 = 2^911485507/3^575083326 = 1.41421356125035E+0000
La première ligne de la sortie est presque identique au résultat obtenu précédemment.
La dernière ligne de la sortie montre que cette dernière approche est en effet plus efficace.
L'erreur joue le même rôle dans les deux approches. Eh bien, presque. Jetons un coup d'œil aux endroits où se trouvent les 'Break's. Premier programme :$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Deuxième programme :$$ -\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 $$Alors$\epsilon$dans le premier programme est une erreur absolue , alors que$\epsilon$dans le second programme est une erreur relative .
Histoire continue à :
L'arbre de Stern-Brocot peut-il être utilisé pour une meilleure convergence de$2^m/3^n$?
Réponses
Oui, il y a toujours des solutions$(m, n)$pour tout réel positif$r$et$\epsilon$pour$$\left| r - \frac{2^m}{3^n} \right| < \epsilon$$Et il existe un moyen beaucoup plus efficace de trouver ces solutions que de parcourir$m$et$n$valeurs une à une.
Nous avons$$r \approx 2^m/3^n$$Prendre des logarithmes,$$\log r \approx m\log 2 - n\log 3$$ $$\log r/\log 2\approx m - n\log 3 / \log 2$$c'est à dire,$$\log_2 r\approx m - n\log_2 3$$
[Incidemment,$$1 = \frac m{\log_2r}-\frac n{\log_3r}$$qui est une ligne dans$(m,n)$avion avec$m$intercepter$\log_2r$et$n$intercepter$-\log_3r$. Nous voulons trouver quand cette ligne passe près de l'entier$(m, n)$points de réseau].
Nous pouvons trouver des approximations rationnelles de ces deux logarithmes de base 2 avec n'importe quelle précision souhaitée. Cependant, pour satisfaire cette équation avec un entier $m$et$n$, les dénominateurs de nos approximations doivent être commensurables.
Laisser$$\log_2 r = f \approx s/t$$et$$\log_2 3 \approx p/q$$avec les fractions étant dans les termes les plus bas, c'est-à-dire,$\gcd(s,t)=gcd(p,q)=1$.
Puis$$\frac st = m - n \frac pq$$ $$sq = (qm - pn)t$$Ainsi$t|sq$. Mais$s$&$t$sont premiers entre eux, donc$t|q$.
Laisser$q=tk$.$$f \approx \frac st = \frac{sk}{tk}=\frac{sk}{q}=\frac dq$$pour un entier$d$.
Ainsi, pour une approximation donnée$\frac pq$pour$\log_2 3$, les meilleures approximations rationnelles de$f$avec des dénominateurs proportionnels sont$\frac{d_0}q$et$\frac{d_1}q$, où$d_0=\lfloor fq\rfloor$et$d_1=\lceil fq\rceil$. C'est-à-dire,$$\frac{d_0}q \le f \le \frac{d_1}q$$Si$f$est rationnel (par exemple, lorsque$r=\sqrt 2$), ensuite$d_0$et$d_1$peut être égal.
Donc pour un donné$p$&$q$il suffit de trouver des entiers$m$&$n$qui résolvent notre équation révisée$$\frac dq = m - n \frac pq$$ $$d=qm-pn$$pour les deux$d_0$et$d_1$. Il existe des solutions pour tout entier$d$car$p$&$q$sont premiers entre eux. Et ces solutions peuvent être trouvées en utilisant l' algorithme euclidien étendu .
Mais nous devons également trouver$p$&$q$. Cela peut être fait en utilisant les convergentes du développement en fraction continue de$\log_2 3$. L'algorithme standard pour calculer une fraction continue est étroitement lié à l'algorithme euclidien étendu, et comme l'explique cet article de Wikipedia (dans le théorème 3), si le$n$ième convergent d'une fraction continue est$\frac{h_n}{k_n}$ensuite$$k_nh_{n-1} - k_{n-1}h_n = (-1)^n$$ce qui nous permet de trouver$m$et$n$sans faire un calcul d'algorithme euclidien séparé.
La fraction continue convergente$\frac hk$d'un nombre$x$donne les meilleures approximations rationnelles de$x$pour tout dénominateur$\le k$. L'erreur est$$\left|x - \frac hk\right| \le \frac 1{k^2}$$et c'est souvent beaucoup mieux. En revanche, l'erreur pour une approximation$\frac hk$avec un dénominateur "aléatoire" (c'est-à-dire, pas une fraction continue convergente) est généralement d'environ$\frac 1{2k}$.
Malheureusement, en raison du besoin de dénominateurs proportionnés dans nos approximations des deux logarithmes, nous n'obtenons pas le plein$\frac 1{k^2}$bonté. Mais nous faisons généralement mieux que$\frac 1{k}$.
Donc, pour trouver des solutions avec une meilleure erreur qu'une donnée$\epsilon$, il suffit de regarder les convergentes pour$\log_2 3$avec des dénominateurs au voisinage de$\frac 1\epsilon$.
Voici du code Sage/Python qui effectue cette tâche. Sage est une collection de bibliothèques mathématiques construites sur le langage de programmation populaire Python. Il a une arithmétique de précision arbitraire et des installations pour effectuer de l'algèbre symbolique, mais j'ai (principalement) évité les fonctionnalités de Sage dans ce code (à part l'arithmétique de précision arbitraire), pour faciliter le portage vers d'autres langages, si vous le souhaitez ; J'ai également évité la plupart des "Pythonismes", mis à part la capacité de Python à renvoyer plusieurs valeurs à partir d'une fonction.
# 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
Voici la sortie de ce programme, la recherche de solutions avec$\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
Et voici une version live avec laquelle vous pouvez jouer sur le serveur SageMath. Mon code n'est pas stocké sur le serveur, il est encodé dans l'URL.
Si vous obtenez un comportement bizarre avec de petits$\epsilon$, essayez d'augmenter le numéro de la bitsvariable globale (en haut du fichier). Le réglage par défaut de 53 devrait convenir pour$\epsilon > 10^{-8}$ou alors. Vous devrez peut-être également augmenter la valeur depthde la fraction continue.
FWW,$\log_2 3$est assez important dans la théorie musicale mathématique des gammes à tempérament égal . L'échelle standard à 12 tons utilise la convergence$19/12$.
Laisser$G= \mathbb Z \log 2 + \mathbb Z \log 3$. Puis$G$est un sous-groupe additif de$\mathbb R$. Depuis$\log 2 / \log 3$est irrationnel,$G$ne peut pas être cyclique [1] et doit donc être dense [2]. Donc,$\log r$est arbitrairement approximée par des éléments de$G$.
[1] Si$G = \mathbb Z \theta $, ensuite$\log 2 = a \theta$et$\log 3 = b \theta$et donc$\log 2 / \log 3 = a/b $est rationnel.
[2] Voirhttps://math.stackexchange.com/a/889775/589
Heuristique d'une autre preuve
Lemme 1.
Les fractions$2^m/3^n$sont tous entre$r/3$et$2r$.
Preuve.
Selon le programme - comme indiqué dans la question. Toute fraction inférieure à$r$est multiplié par$2$, alors$r.2$est une borne supérieure pour ces fractions. Toute fraction supérieure à$r$est divisé par$3$, alors$r/3$est une borne inférieure pour ces fractions. Il ne peut y avoir d'autres fractions, sauf au début des itérations.$$ r/3 < \frac{2^m}{3^n} < 2r $$ Lemme 2.
Dans la séquence$2^m/3^n \to r$il n'y a pas deux fractions identiques.
Preuve.
Supposons que nous ayons$2^{m_1}/3^{n_1} = 2^{m_2}/3^{n_2}$.
Trois cas sont distingués :
- $m_1 \neq m_2$et$n_1 = n_2$. Puis$2^{m_1} = 2^{m_2}$Par conséquent$m_1 = m_2$. Contradiction.
- $n_1 \neq n_2$et$m_1 = m_2$. Puis$1/3^{n_1} = 1/3^{n_2}$Par conséquent$n_1 = n_2$. Contradiction.
- $m_1 \neq m_2$et$n_1 \neq n_2$. Ensuite nous avons:$$ \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)} $$Mais$\,\ln(3)/\ln(2)\,$n'est pas un nombre rationnel. Contradiction.
Nous avons donc un tas de fractions, toutes différentes, mais elles doivent tenir dans l'intervalle$\,]r/3,2r[\,$. Cela signifie que les fractions deviennent entassées. Faisons une image du processus d'itération, version logarithmique. La ligne rouge est donnée par$\,\color{red}{\ln(3)y=\ln(2)x-\ln(r)}\,$, les petits cercles sont des fractions, cartographiés sur une grille$\,m/n \to (m,n)\,$, les points remplis massivement de noir sont les fractions du processus d'itération, tout en augmentant$m$et$n$avec des incréments un à la fois. Le domaine des itérations est limité par :$\,\color{blue}{-\ln(2)\lt\ln(3)y-\ln(2)x+\ln(r)\lt\ln(3)}\,$. Dans notre cas$r = 100$. Attention à la séquence au début.
Il semble donc qu'il doit y avoir pas mal de fractions à proximité de la ligne rouge, représentant le nombre réel$r$Dans la question.
Comment pouvons-nous en être sûrs ? Faisons image de l'encombrement des approximations$a$dans l'intervalle$\,]r/3,2r[\,$, échelle logarithmique:$$ a = m\ln(2)-n\ln(3)-\ln(r) \quad \mbox{with} \quad -\ln(3) < a < \ln(2) $$La ligne rouge est où$a = 0$, la valeur souhaitée.
D'autres expériences numériques/graphiques révèlent que la distribution des fractions semble être uniforme . Tout en cherchant une confirmation supplémentaire de cela, nous avons fait ce qui suit, parlant en termes de (Delphi) Pascal :
avis de programme ;
procédure intervalle(var A,B : double); var h : double ; commencer A := Aléatoire ; B := Aléatoire ; si A > B alors commencer h := B; B := A ; A := h; finir; finir;
procédure proef(r : double); constante veel : entier = 1000000000; var x,l2,l3,lr,A,B : double ; m,n,tel,t : entier; commencer l2 := ln(2); l3 := ln(3); lr := ln(r); intervalle(A,B); A := -l3 + A*(l2+l3); B := -l3 + B*(l2+l3); m := 0; n := 0; tel := 0; t := 0; tandis que tel < veel do commencer x := m*l2 - n*l3 - lr ; si x < 0 alors m := m + 1 sinon n := n + 1; si (-l3 < x) et (x < +l2) alors tel := tel + 1; si (A < x) et (x < B) alors t := t + 1; finir; Writeln((BA)/(l2+l3),' = ',t/tel); finir;
commencer Aléatoire; Aléatoire; preuve(1000); proef(0.001); proef(sqrt(2)); proef(1/sqrt(2)); alors que vrai faire preuve(aléatoire); finir.
Explication. Faire des intervalles aléatoires$\,]A,B[\,$à l'intérieur$\,]-\ln(3),+\ln(2)[\,$. La longueur de ce dernier intervalle est$\,\ln(3)+\ln(2)=\ln(6)\,$, les longueurs des premières sont$\,(B-A)\,$. Comptez les (logarithmes$x$des) fractions$\,(2^n/3^n)/r\,$dans les deux intervalles. Laisser$N$soit le nombre total (tel) d'iterands et$n$soit le nombre (t) d'iterands dans$\,]A,B[\,$. Alors la distribution des approximations$x$est uniforme si et seulement si :$$ \lim_{N\to\infty}\frac{n}{N} = \frac{B-A}{\ln(6)} $$Allons vérifier. Sortie après un milliard d'itérations chaque ligne :
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 = ....
Mais comment prouver qu'il s'agit d'une distribution uniforme ?