Aperiodicity and subword complexity in the binary expansion of powers of three

数値の秘密の生活：バイナリ・パターンの旅

あなたは、混沌とした街の中でパターンを見つけ出そうとしている探偵だと想像してください。数学の世界において、この街は数体系であり、混沌とは、数字が異なる言語で書かれたときの姿のことです。私たちは通常、10進法（0から9までの10個の数字）を用いて「10進数」を話しますが、コンピュータは「バイナリ（2進法）」、つまり0と1という2つの数字だけで作られた言語を話します。例えば「3」という数字を何度も何度も繰り返し掛け合わせると（3, 9, 27, 81...）、非常に大きな数字の列が得られます。これらの巨大な数字をバイナリ形式で書くと、0と1が長く、ギザギザした文字列のように見えます。

数学者たちは長い間、こう疑問に思ってきました。「これらの0と1の文字列には、隠れたリズムがあるのだろうか、それとも完全にランダムなのだろうか？」という疑問です。この問いは、整数の深く、しばしば神秘的な性質を研究する「数論」と呼ばれる分野に属しています。ここでの重要な概念は「周期性（periodicity）」です。周期的なパターンとは、数インチごとに同じ花が繰り返される壁紙のデザインのようなものです。もしある数字のバイナリ・コードに周期があれば、それはある地点を過ぎた後、0と1のパターンがループする曲のように、完璧に繰り返し始めることを意味します。もう一つの重要な概念は「複雑性（complexity）」であり、これはパターンの中にどれほど多くの異なる「塊（チャンク）」が存在するかを測定するものです。もし文字列が単純であれば、その塊の種類は少なくなります。もし複雑であれば、非常に多様な塊が存在することになります。これらのパターンを理解することは、3の累乗のような数字が本当に混沌としているのか、それとも私たちがまだ発見していない秘密の秩序を隠し持っているのかを知る助けとなります。

論文の発見：バイナリ・コードにおける混沌

この論文において、数学者のラルフ・ステファン（Ralf Stephan）は、3の累乗（$3^m$）のバイナリ展開について調査しています。彼は非常に具体的な問いを投げかけています。「これらの数字が大きくなればなるほど、バイナリの桁は最終的に繰り返しのループに落ち着くのか、それとも乱雑で予測不可能なままなのか？」という問いです。

この論文は、主に2つのことを証明しており、どちらも3の累乗のバイナリ・コードが極めて混沌としており、単純な反復によって制御されることを拒んでいることを裏付けています。

第一に、「ノー・ループ（ループなし）」の規則：
著者は、あなたがどのような固定された繰り返しパターン（例えば、5桁ごと、あるいは100桁ごとのパターン）を見つけようとしても、3の累乗のバイナリ・コードは最終的にそのパターンを破ることを証明しています。それはまるで、野生動物に完璧な円を描いて行進させようとするようなものです。どれほど長く待ったとしても、その動物は最終的に列から外れてしまいます。論文は、$m$（累乗数）が大きくなるにつれて、この周期性を「破る」回数がどのように増えていくかを示しています。具体的には、これらの「破れ」の数は、おおよそ $\frac{\log m}{\log \log m}$ のように増加します。

比喩を使って説明しましょう。3の累乗のバイナリの桁を、長い踊り子の列だと想像してください。もしあなたが彼らに繰り返しのステップ（周期）を踏ませようとしても、論文は、列が長くなればなるなるほど、必然的にステップを間違える踊り子が増えることを証明しています。論文では、これら「ミス」の数を計算しており、数字が大きくなるにつれてその数が増えることを示しています。つまり、ダンスが決して完璧で退屈なループに落ち着くことはないのです。たとえ、対数 $m$ の固定された累乗と同じ深さのダンスフロアの窓を覗いたとしても、完璧な繰り返しパターンは見つかりません。

第二に、「最大多様性」の規則：
二つ目の発見は、バイナリ・コードの中にどれほど多くの異なる「塊」が存在するかについてです。もしバイナリ文字列の小さな切り抜き（例えば10桁の長さ）を取ったとき、0と1の組み合わせが何種類見つかるでしょうか？ 論文は、十分に大きな3の累乗に対して、長さ $n$ の異なる塊の数は少なくとも $n + 1$ であることを証明しています。

日常的な言葉で言えば、これはバイナリ・コードが低次において「最大限に複雑」であることを意味します。それは単にランダムなのではなく、豊かにランダムなのです。もし長さ $n$ の文字列がある場合、最も単純なパターン（完璧なループのようなもの）は、わずか $n$ 種類の塊しか持ちません。しかし、$3^m$ は少なくとも $n + 1$ を持っています。それは、どんなにシャッフルしても、退屈ではないと見なされるために必要な最小限の数よりも、常に一つ多いユニークな手札を生み出し続けるトランプのデッキのようなものです。これは、3の累乗の低次桁が、無限ではない範囲において、可能な限り多様で予測不可能なものであることを証明しています。

どの程度確かなのか？
著者はこれらの結果に対して非常に自信を持っています。この論文は単に推測したりシミュレーションを行ったりしているのではなく、厳密な数学的証明を提供しています。その論理は、「対数における線形形式（linear forms in logarithms）」と呼ばれる強力なツールに依拠しています。これは、もしパターンが単純であったならば、その数値が不可能に小さくなるか矛盾が生じることを示す、数学的な拡大鏡のような役割を果たします。また、論文では、これらの証明が「Lean 4」と呼ばれるコンピュータプログラムによって形式的に検証され、論理的なステップにエラーがないようダブルチェックされていることにも触れています。したがって、3の累乗のバイナリ展開が非周期的であり、完全な部分語複雑性（full subword complexity）を持つことは確実です。

要約すると、この論文は、3の累乗が数の世界における究極の反逆者であることを伝えています。それらは予測可能なリズムに陥ることを拒み、そのバイナリ・コードは、数字が大きくなるにつれてより複雑になる、ユニークで非反復的なパターンの宝庫なのです。