¿Se puede aproximar cualquier real positivo como $2^m/3^n$con $(m,n)$¿lo suficientemente grande?

Jan 12 2021

Conjetura.
existen enteros positivos$(m,n)$lo suficientemente grande, tal que para cualquier número real positivo$r$y un error dado$\epsilon$:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Hay evidencia numérica para esta conjetura. Yo he tratado$r = \sqrt{2}$y$\epsilon = 10^{-3}$.
A continuación se muestra un pequeño programa de Delphi Pascal con la salida que lo acompaña.
Pero.. alguien puede probar la conjetura?

programa aparte;

prueba de procedimiento (r: doble; eps: doble);
variable
  un doble;
  m,n : entero;
empezar
  un := 1;
  metro := 0; n := 0;
  mientras que cierto
  empezar
    si a < r entonces
    empezar
      metro := metro + 1;
      un := un * 2;
    terminar si no empezar
      norte := norte + 1;
      un := un / 3;
    final;
    si abs(ra) < eps entonces Romper;
  final;
  Writeln(r,' = 2^',m,'/3^',n,' =',a);
final;

empezar
  prueba (raíz cuadrada (2), 1.E-3);
final.

Producción:

1.41421356237310E+0000 = 2^243/3^153 = 1.41493657935359E+0000

ACTUALIZAR.
La respuesta de lhf parece una prueba muy concisa. Pero para mí, como físico jubilado por educación, es un poco más allá de la comprensión.
Además, deja algunas cuestiones intactas. Cabría preguntarse, por ejemplo, si existen estimaciones de$m$y$n$Cuándo$r$y$\epsilon$son dados.

Nota. La pregunta también se puede formular como: ¿Se puede aproximar cualquier real positivo como$3^m/2^n$con$(m,n)$¿lo suficientemente grande? Que es lo mismo que permitir números enteros negativos con la formulación original. De esta forma, muestra cierto parecido con el (in)famoso problema de Collatz .

EDITAR.
Como sugieren las respuestas, un enfoque con logaritmos podría ser más efectivo:

anders del programa;

procedimiento proef(r : doble; eps : doble);
variable
  a,l2,l3,lr : doble;
  m,n : entero;
empezar
  l2 := ln(2); l3 := ln(3);
  lr := ln(r); un := 0;
  metro := 0; n := 0;
  mientras que cierto
  empezar
    a := m*l2 - n*l3 - lr;
    si abs(a) < eps entonces Romper;
    si a < 0 entonces m := m + 1 si no n := n + 1;
  final;
  Writeln(r,' = 2^',m,'/3^',n,' =',exp(a)*r);
final;

empezar
  prueba(raíz cuadrada(2),1.E-3);
  prueba(raíz cuadrada(2),1.E-9);
final.

Producción:

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

La primera línea de la salida es casi idéntica al resultado obtenido anteriormente.
La última línea del resultado muestra que el último enfoque es más efectivo.
El error juega el mismo papel en ambos enfoques. Bueno, casi. Echemos un vistazo a los lugares donde están los 'Break's. primer programa:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Segundo programa:$$ -\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 $$Entonces$\epsilon$en el primer programa es un error absoluto , mientras que$\epsilon$en el segundo programa es un error relativo .

Continuación de la historia en:
¿Se puede emplear el árbol Stern-Brocot para una mejor convergencia de$2^m/3^n$?

Respuestas

4 PM2Ring Jan 13 2021 at 06:37

Sí, siempre hay soluciones.$(m, n)$para cualquier real positivo$r$y$\epsilon$por$$\left| r - \frac{2^m}{3^n} \right| < \epsilon$$Y hay una manera mucho más eficiente de encontrar esas soluciones que pasar por$m$y$n$valores uno a uno.

Tenemos$$r \approx 2^m/3^n$$Tomando logaritmos,$$\log r \approx m\log 2 - n\log 3$$ $$\log r/\log 2\approx m - n\log 3 / \log 2$$es decir,$$\log_2 r\approx m - n\log_2 3$$

[De paso,$$1 = \frac m{\log_2r}-\frac n{\log_3r}$$que es una línea en el$(m,n)$avion con$m$interceptar$\log_2r$y$n$interceptar$-\log_3r$. Queremos encontrar cuando esa línea pasa cerca de entero$(m, n)$puntos de red].

Podemos encontrar aproximaciones racionales a ambos logaritmos de base 2 con cualquier precisión deseada. Sin embargo, para satisfacer esa ecuación con entero $m$y$n$, los denominadores de nuestras aproximaciones deben ser proporcionales.

Dejar$$\log_2 r = f \approx s/t$$y$$\log_2 3 \approx p/q$$con las fracciones en términos más bajos, es decir,$\gcd(s,t)=gcd(p,q)=1$.

Luego$$\frac st = m - n \frac pq$$ $$sq = (qm - pn)t$$Por lo tanto$t|sq$. Pero$s$&$t$son coprimos, por lo tanto$t|q$.

Dejar$q=tk$.$$f \approx \frac st = \frac{sk}{tk}=\frac{sk}{q}=\frac dq$$por algún entero$d$.

Entonces, para una aproximación dada$\frac pq$para$\log_2 3$, las mejores aproximaciones racionales a$f$con denominadores proporcionales son$\frac{d_0}q$y$\frac{d_1}q$, donde$d_0=\lfloor fq\rfloor$y$d_1=\lceil fq\rceil$. Es decir,$$\frac{d_0}q \le f \le \frac{d_1}q$$Si$f$es racional (por ejemplo, cuando$r=\sqrt 2$), luego$d_0$y$d_1$puede ser igual.

Así que para un dado$p$&$q$solo necesitamos encontrar números enteros$m$&$n$que resuelven nuestra ecuación revisada$$\frac dq = m - n \frac pq$$ $$d=qm-pn$$para ambos$d_0$y$d_1$. Hay soluciones para cualquier número entero.$d$porque$p$&$q$son coprimos. Y esas soluciones se pueden encontrar utilizando el algoritmo euclidiano extendido .

Pero también necesitamos encontrar$p$&$q$. Eso se puede hacer usando los convergentes de la expansión en fracción continua de$\log_2 3$. El algoritmo estándar para calcular una fracción continua está estrechamente relacionado con el algoritmo euclidiano extendido, y como explica ese artículo de Wikipedia (en el Teorema 3), si el$n$El convergente de una fracción continua es$\frac{h_n}{k_n}$luego$$k_nh_{n-1} - k_{n-1}h_n = (-1)^n$$que nos permite encontrar$m$y$n$sin hacer un cálculo de algoritmo euclidiano por separado.

La fracción continua convergente$\frac hk$de un numero$x$da las mejores aproximaciones racionales a$x$para cualquier denominador$\le k$. el error es$$\left|x - \frac hk\right| \le \frac 1{k^2}$$ya menudo puede ser mucho mejor. Por el contrario, el error de una aproximación$\frac hk$con un denominador "aleatorio" (es decir, no una fracción continua convergente) es generalmente alrededor$\frac 1{2k}$.

Desafortunadamente, debido a la necesidad de denominadores proporcionales en nuestras aproximaciones a los dos logaritmos, no obtenemos el total$\frac 1{k^2}$bondad. Pero generalmente somos mejores que$\frac 1{k}$.

Entonces, para encontrar soluciones con mejor error que un dado$\epsilon$, solo tenemos que mirar los convergentes para$\log_2 3$con denominadores en la vecindad de$\frac 1\epsilon$.

Here is some Sage / Python code that performs that task. Sage is a collection of mathematical libraries built on top of the popular Python programming language. It has arbitrary precision arithmetic, and facilities for performing symbolic algebra, but I've (mostly) avoided Sage features in this code (apart from the arbitrary precision arithmetic), to make it easier to port to other languages, if desired; I've also avoided most "Pythonisms", apart from Python's ability to return multiple values from a function.

# 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

Here's the output of that program, searching for solutions with $\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

And here is a live version that you can play with on the SageMath server. My code isn't stored on the server, it's encoded in the URL.

If you get weird behaviour with small $\epsilon$, try increasing the number of the bits global variable (at the top of the file). The default setting of 53 should be ok for $\epsilon > 10^{-8}$ or so. You may also need to increase the depth of the continued fraction.

FWIW, $\log_2 3$ is rather important in the mathematical music theory of equally-tempered scales. The standard 12 tone scale uses the convergent $19/12$.

11 lhf Jan 12 2021 at 00:05

Let $G= \mathbb Z \log 2 + \mathbb Z \log 3$. Then $G$ is an additive subgroup of $\mathbb R$. Since $\log 2 / \log 3$ is irrational, $G$ cannot be cyclic [1] and so must be dense [2]. Therefore, $\log r$ is arbitrarily approximated by elements of $G$.

[1] If $G = \mathbb Z \theta $, then $\log 2 = a \theta$ and $\log 3 = b \theta$ and so $\log 2 / \log 3 = a/b $ is rational.

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

HandeBruijn Jan 31 2021 at 03:32

Heuristics of a another proof

Lemma 1.
The fractions $2^m/3^n$ are all between $r/3$ and $2r$.
Proof.
According to the program - as displayed in the question. Any fraction smaller than $r$ is multiplied by $2$, so $r.2$ is an upper bound for these fractions. Any fraction greater than $r$ is divided by $3$, so $r/3$ is a lower bound for these fractions. There can be no other fractions, except when the iterations start. $$ r/3 < \frac{2^m}{3^n} < 2r $$ Lemma 2.
In the sequence $2^m/3^n \to r$ there are no two fractions the same.
Proof.
Suppose that we have $2^{m_1}/3^{n_1} = 2^{m_2}/3^{n_2}$.
Three cases are distinguished:

$m_1 \neq m_2$ and $n_1 = n_2$. Then $2^{m_1} = 2^{m_2}$ hence $m_1 = m_2$. Contradiction.
$n_1 \neq n_2$ and $m_1 = m_2$. Then $1/3^{n_1} = 1/3^{n_2}$ hence $n_1 = n_2$. Contradiction.
$m_1 \neq m_2$ and $n_1 \neq n_2$. Then we have: $$ \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)} $$ But $\,\ln(3)/\ln(2)\,$ is not a rational number. Contradiction.

So what we have is a bunch of fractions, all different, but they must fit within the interval $\,]r/3,2r[\,$. This means that the fractions become crowded. Let's make a picture of the iteration process, logarithmic version. The red line is given by $\,\color{red}{\ln(3)y=\ln(2)x-\ln(r)}\,$, small circles are fractions, mapped on a grid $\,m/n \to (m,n)\,$, puntos masivamente rellenos de negro son las fracciones en el proceso de iteración, al tiempo que aumentan$m$y$n$con incrementos uno a la vez. El dominio de las iteraciones está limitado por:$\,\color{blue}{-\ln(2)\lt\ln(3)y-\ln(2)x+\ln(r)\lt\ln(3)}\,$. En nuestro caso$r = 100$. Cuidado con la secuencia al principio.

Entonces parece que debe haber bastantes fracciones cerca de la línea roja, representando el número real$r$en cuestión.
¿Cómo podemos estar seguros de esto? Hagamos una foto del hacinamiento de las aproximaciones.$a$en el intervalo$\,]r/3,2r[\,$, escala logarítmica:$$ a = m\ln(2)-n\ln(3)-\ln(r) \quad \mbox{with} \quad -\ln(3) < a < \ln(2) $$La línea roja es donde$a = 0$, el valor deseado.

Otros experimentos numéricos/gráficos revelan que la distribución de las fracciones parece ser uniforme . Mientras buscamos más confirmación de esto, hemos hecho lo siguiente, hablando en términos de (Delphi) Pascal:

opción de programa;

intervalo de procedimiento (var A,B: doble);
variable
  h : doble;
empezar
  A := Aleatorio; B := Aleatorio;
  si A > B entonces
  empezar
    h := B; B := A; A := h;
  final;
final;

procedimiento proef(r : doble);
constante
  vela : entero = 1000000000;
variable
  x,l2,l3,lr,A,B : doble;
  m,n,tel,t : entero;
empezar
  l2 := ln(2); l3 := ln(3);
  lr := ln(r);
  intervalo(A,B);
  A := -l3 + A*(l2+l3);
  B := -l3 + B*(l2+l3);
  metro := 0; n := 0;
  teléfono := 0; t := 0;
  mientras que tel <veel do
  empezar
    x := m*l2 - n*l3 - lr;
    si x < 0 entonces m := m + 1 si no n := n + 1;
    si (-l3 < x) y (x < +l2) entonces tel := tel + 1;
    si (A < x) y (x < B) entonces t := t + 1;
  final;
  Writeln((BA)/(l2+l3),' = ',t/tel);
final;

empezar
  Aleatorio; Aleatorio;
  prueba(1000);
  prueba(0.001);
  prueba(raíz cuadrada(2));
  prueba(1/raíz cuadrada(2));
  mientras que cierto
    prueba (aleatorio);
final.

Explicación. Hacer intervalos aleatorios$\,]A,B[\,$en el interior$\,]-\ln(3),+\ln(2)[\,$. La longitud de este último intervalo es$\,\ln(3)+\ln(2)=\ln(6)\,$, las longitudes de los primeros son$\,(B-A)\,$. Cuente los (logaritmos$x$de las) fracciones$\,(2^n/3^n)/r\,$en ambos intervalos. Dejar$N$sea el número total (tel) de iterandos y$n$sea el número (t) de iterandos en$\,]A,B[\,$. Entonces la distribución de las aproximaciones$x$es uniforme si y solo si:$$ \lim_{N\to\infty}\frac{n}{N} = \frac{B-A}{\ln(6)} $$Vamos a revisar. Salida después de mil millones de iteraciones en cada línea: