Может ли любое положительное действительное число быть аппроксимировано как $2^m/3^n$ с участием $(m,n)$ достаточно большой?

Jan 12 2021

Гипотеза.
Существуют положительные целые числа$(m,n)$ достаточно большой, чтобы для любого положительного действительного числа $r$ и заданная ошибка $\epsilon$ : $$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Это предположение подтверждается численными данными. я пытался$r = \sqrt{2}$ а также $\epsilon = 10^{-3}$.
Ниже представлена небольшая программа на Delphi Pascal с сопроводительным выводом.
Но .. может кто-нибудь доказать эту гипотезу?

программа отдельно;

проверка процедуры (r: double; eps: double);
вар
  двойной;
  m, n: целое число;
начинать
  а: = 1;
  m: = 0; n: = 0;
  в то время как правда
  начинать
    если a <r, то
    начинать
      m: = m + 1;
      а: = а * 2;
    конец еще начало
      п: = п + 1;
      а: = а / 3;
    конец;
    если abs (ra) <eps, то Break;
  конец;
  Writeln (r, '= 2 ^', m, '/ 3 ^', n, '=', a);
конец;

начинать
  тест (sqrt (2), 1.E-3);
конец.

Выход:

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

ОБНОВИТЬ.
Ответ lhf действительно выглядит очень кратким доказательством. Но для меня - физика на пенсии по образованию - это немного за гранью понимания.
Кроме того, он оставляет нетронутыми некоторые проблемы. Например, можно спросить, есть ли оценки для$m$ а также $n$ когда $r$ а также $\epsilon$ дано.

Примечание. Вопрос также можно сформулировать так: может ли любое положительное действительное число быть аппроксимировано как$3^m/2^n$ с участием $(m,n)$достаточно большой? Это то же самое, что разрешить отрицательные целые числа в исходной формулировке. В этой форме она показывает некоторое сходство с известной проблемой Коллатца .

РЕДАКТИРОВАТЬ.
Как показывают ответы, подход с логарифмами может быть более эффективным:

программа Андерс;

процедура proef (r: double; eps: double);
вар
  a, l2, l3, lr: двойной;
  m, n: целое число;
начинать
  l2: = ln (2); l3: = ln (3);
  lr: = ln (r); а: = 0;
  m: = 0; n: = 0;
  в то время как правда
  начинать
    a: = m * l2 - n * l3 - lr;
    если abs (a) <eps, то Break;
    если a <0, то m: = m + 1, иначе n: = n + 1;
  конец;
  Writeln (r, '= 2 ^', m, '/ 3 ^', n, '=', exp (a) * r);
конец;

начинать
  proef (sqrt (2), 1.E-3);
  proef (sqrt (2), 1.E-9);
конец.

Выход:

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

Первая строка вывода почти идентична результату, полученному ранее.
Последняя строка вывода показывает, что последний подход действительно более эффективен.
Ошибка играет одинаковую роль в обоих подходах. Ну да ладно, почти. Давайте посмотрим на места, где бывают перерывы. Первая программа:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$ Вторая программа: $$ -\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 $$ Так $\epsilon$в первой программе - абсолютная ошибка, а$\epsilon$во второй программе - относительная ошибка.

Продолжение рассказа:
Можно ли использовать дерево Штерна-Броко для лучшего схождения$2^m/3^n$?

Ответы

4 PM2Ring Jan 13 2021 at 06:37

Да, всегда есть решения $(m, n)$ для любого положительного реального $r$ а также $\epsilon$ для $$\left| r - \frac{2^m}{3^n} \right| < \epsilon$$И есть гораздо более эффективный способ найти эти решения, чем пошагово$m$ а также $n$ значения один за другим.

У нас есть $$r \approx 2^m/3^n$$ Логарифмируя, $$\log r \approx m\log 2 - n\log 3$$ $$\log r/\log 2\approx m - n\log 3 / \log 2$$ т.е. $$\log_2 r\approx m - n\log_2 3$$

[Между прочим, $$1 = \frac m{\log_2r}-\frac n{\log_3r}$$ что является строкой в $(m,n)$ самолет с $m$ перехватить $\log_2r$ а также $n$ перехватить $-\log_3r$. Мы хотим узнать, когда эта строка приближается к целому числу$(m, n)$ точки решетки].

Мы можем найти рациональные приближения к обоим логарифмам с основанием 2 с любой желаемой точностью. Однако, чтобы удовлетворить это уравнение с целым числом $m$ а также $n$, знаменатели наших приближений должны быть соизмеримыми.

Позволять $$\log_2 r = f \approx s/t$$ а также $$\log_2 3 \approx p/q$$ с дробями в наименьших числах, т.е. $\gcd(s,t)=gcd(p,q)=1$.

потом $$\frac st = m - n \frac pq$$ $$sq = (qm - pn)t$$ Таким образом $t|sq$. Но$s$ & $t$ взаимно просты, следовательно $t|q$.

Позволять $q=tk$. $$f \approx \frac st = \frac{sk}{tk}=\frac{sk}{q}=\frac dq$$ для некоторого целого числа $d$.

Итак, для данного приближения $\frac pq$ к $\log_2 3$, наилучшие рациональные приближения к $f$ со соразмерными знаменателями $\frac{d_0}q$ а также $\frac{d_1}q$, где $d_0=\lfloor fq\rfloor$ а также $d_1=\lceil fq\rceil$. Это,$$\frac{d_0}q \le f \le \frac{d_1}q$$ Если $f$ рационально (например, когда $r=\sqrt 2$), тогда $d_0$ а также $d_1$ может быть равным.

Итак, для данного $p$ & $q$ нам просто нужно найти целые числа $m$ & $n$ которые решают наше исправленное уравнение $$\frac dq = m - n \frac pq$$ $$d=qm-pn$$ для обоих $d_0$ а также $d_1$. Есть решения для любых целых$d$ так как $p$ & $q$взаимно просты. И эти решения можно найти с помощью расширенного алгоритма Евклида .

Но нам также нужно найти подходящие $p$ & $q$. Это можно сделать, используя подходящие дроби разложения непрерывной дроби$\log_2 3$. Стандартный алгоритм вычисления непрерывной дроби тесно связан с расширенным алгоритмом Евклида, и, как объясняется в статье в Википедии (в теореме 3), если$n$-я сходящаяся дробь непрерывной дроби равна $\frac{h_n}{k_n}$ тогда $$k_nh_{n-1} - k_{n-1}h_n = (-1)^n$$ что позволяет нам найти $m$ а также $n$ без выполнения отдельного расчета алгоритма Евклида.

Непрерывная дробь сходящаяся $\frac hk$ ряда $x$ дает наилучшие рациональные приближения к $x$ для любого знаменателя $\le k$. Ошибка$$\left|x - \frac hk\right| \le \frac 1{k^2}$$и часто бывает намного лучше. Напротив, ошибка приближения$\frac hk$ со «случайным» знаменателем (т. е. не сходящейся непрерывной дробью) обычно составляет около $\frac 1{2k}$.

К сожалению, из-за необходимости соизмеримых знаменателей в наших приближениях к двум логарифмам мы не получаем полную $\frac 1{k^2}$доброта. Но мы обычно лучше, чем$\frac 1{k}$.

Итак, чтобы найти решения с лучшей ошибкой, чем заданная $\epsilon$, нам просто нужно посмотреть на подходящие к $\log_2 3$ со знаменателями в районе $\frac 1\epsilon$.

Вот код Sage / Python, который выполняет эту задачу. Sage - это набор математических библиотек, созданных на основе популярного языка программирования Python. Он имеет арифметику произвольной точности и средства для выполнения символьной алгебры, но я (в основном) избегал функций Sage в этом коде (кроме арифметики произвольной точности), чтобы упростить перенос на другие языки, если это необходимо; Я также избегал большинства «питонизмов», за исключением способности Python возвращать несколько значений из функции.

# 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

Вот результат этой программы, ищущей решения с $\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

А вот и живая версия, с которой вы можете поиграть на сервере SageMath. Мой код не хранится на сервере, он закодирован в URL-адресе.

Если вы получаете странное поведение с маленьким $\epsilon$попробуйте увеличить номер bitsглобальной переменной (вверху файла). Значение по умолчанию 53 должно быть подходящим для$\epsilon > 10^{-8}$или так. Вам также может потребоваться увеличить depthнепрерывную дробь.

FWIW, $\log_2 3$весьма важен в математической теории музыки равномерно темперированных гамм . Стандартная 12-тональная шкала использует сходящуюся$19/12$.

11 lhf Jan 12 2021 at 00:05

Позволять $G= \mathbb Z \log 2 + \mathbb Z \log 3$. потом$G$ является аддитивной подгруппой в $\mathbb R$. С$\log 2 / \log 3$ иррационально, $G$не может быть циклическим [1] и поэтому должен быть плотным [2]. Следовательно,$\log r$ произвольно аппроксимируется элементами $G$.

[1] Если $G = \mathbb Z \theta $, тогда $\log 2 = a \theta$ а также $\log 3 = b \theta$ и другие $\log 2 / \log 3 = a/b $ рационально.

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

HandeBruijn Jan 31 2021 at 03:32

Эвристика другого доказательства

Лемма 1.
Дроби$2^m/3^n$ все между $r/3$ а также $2r$.
Доказательство.
По программе - как указано в вопросе. Любая дробь меньше, чем$r$ умножается на $2$, так $r.2$является верхней оценкой этих дробей. Любая дробь больше, чем$r$ делится на $3$, так $r/3$является нижней оценкой этих дробей. Других дробей быть не может, кроме момента начала итераций.$$ r/3 < \frac{2^m}{3^n} < 2r $$ Лемма 2.
В последовательности$2^m/3^n \to r$нет двух одинаковых дробей.
Доказательство.
Предположим, что у нас есть$2^{m_1}/3^{n_1} = 2^{m_2}/3^{n_2}$.
Различают три случая:

$m_1 \neq m_2$ а также $n_1 = n_2$. потом$2^{m_1} = 2^{m_2}$ следовательно $m_1 = m_2$. Противоречие.
$n_1 \neq n_2$ а также $m_1 = m_2$. потом$1/3^{n_1} = 1/3^{n_2}$ следовательно $n_1 = n_2$. Противоречие.
$m_1 \neq m_2$ а также $n_1 \neq n_2$. Тогда у нас есть:$$ \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)} $$ Но $\,\ln(3)/\ln(2)\,$не рациональное число. Противоречие.

Итак, у нас есть набор дробей, все разные, но они должны укладываться в интервал $\,]r/3,2r[\,$. Это означает, что фракции переполняются. Представим картину итерационного процесса в логарифмической версии. Красная линия обозначена$\,\color{red}{\ln(3)y=\ln(2)x-\ln(r)}\,$, маленькие кружки - дроби, нанесенные на сетку $\,m/n \to (m,n)\,$, массивные черные точки - доли в итерационном процессе, при увеличении $m$ а также $n$с приращениями по одному. Область итераций ограничена:$\,\color{blue}{-\ln(2)\lt\ln(3)y-\ln(2)x+\ln(r)\lt\ln(3)}\,$. В нашем случае$r = 100$. Обратите внимание на последовательность в начале.

Похоже, что рядом с красной линией должно быть несколько дробей, соответствующих действительному числу. $r$обсуждаемый.
Как мы можем быть уверены в этом? Сделаем картину скопления аппроксимаций.$a$ в интервале $\,]r/3,2r[\,$, логарифмическая шкала: $$ a = m\ln(2)-n\ln(3)-\ln(r) \quad \mbox{with} \quad -\ln(3) < a < \ln(2) $$ Красная линия - это то место, где $a = 0$, желаемое значение.

Дальнейшие численные / графические эксперименты показывают, что распределение фракций кажется равномерным . В поисках дальнейшего подтверждения этого мы сделали следующее, говоря в терминах (Delphi) Pascal:

запуск программы;

интервал процедуры (var A, B: double);
вар
  h: двойной;
начинать
  A: = Случайно; B: = Случайно;
  если A> B, то
  начинать
    h: = B; В: = А; A: = h;
  конец;
конец;

процедура proef (r: double);
const
  veel: integer = 1000000000;
вар
  x, l2, l3, lr, A, B: двойной;
  m, n, tel, t: целое число;
начинать
  l2: = ln (2); l3: = ln (3);
  lr: = ln (r);
  интервал (A, B);
  А: = -l3 + A * (l2 + l3);
  В: = -l3 + B * (l2 + l3);
  m: = 0; n: = 0;
  тел: = 0; t: = 0;
  в то время как тел <вел делать
  начинать
    x: = m * l2 - n * l3 - lr;
    если x <0, то m: = m + 1, иначе n: = n + 1;
    если (-l3 <x) и (x <+ l2), то tel: = tel + 1;
    если (A <x) и (x <B), то t: = t + 1;
  конец;
  Writeln ((BA) / (l2 + l3), '=', t / tel);
конец;

начинать
  Случайный; Случайный;
  proef (1000);
  proef (0,001);
  proef (sqrt (2));
  proef (1 / sqrt (2));
  в то время как правда
    proef (случайный);
конец.

Объяснение. Делайте случайные интервалы$\,]A,B[\,$ внутри $\,]-\ln(3),+\ln(2)[\,$. Длина последнего интервала составляет$\,\ln(3)+\ln(2)=\ln(6)\,$, длины первых равны $\,(B-A)\,$. Подсчитайте (логарифмы$x$ фракций $\,(2^n/3^n)/r\,$в обоих интервалах. Позволять$N$ быть общим числом (тел) итераций и $n$ быть количеством (t) итераций в $\,]A,B[\,$. Тогда распределение приближений$x$является однородным , если и только если:$$ \lim_{N\to\infty}\frac{n}{N} = \frac{B-A}{\ln(6)} $$Давай проверим. Выведите после миллиарда итераций каждую строку: