Optimal Non-Binary Single-Track Gray Code

回転する車輪（自転車の車輪や巨大な工業用扇風機のようなもの）を追跡しているところを想像してみてください。あなたは、その車輪がどの瞬間にどこにあるのかを正確に知りたいと考えています。これを行うために、エンジニアは車輪にストライプ（縞模様）を描き、センサーを使ってそれを読み取ります。標準的な数え方を使用すると、車輪が2つの数字のちょうど中間にあるとき、複数のストライプが同時に変化してしまうため、コンピューターが車輪の位置を誤解するという「グリッチ（不具合）」が発生し、混乱を招くことがあります。

これを解決するために、数学者たちはグレイコード（Gray code）と呼ばれる特別な種類のコードを発明しました。これは、次の数字へ移動するときに、一度にたった一つのことしか変えてはいけないというルールを持つ秘密の言語のようなものです。それは、一度に2段飛ばしでジャンプするのではなく、一度に一段ずつ昇り降りすることしか許されない梯子を登るようなものです。これにより、もしセンサーが少し揺れても、大きな混乱ではなく、ごく小さな、無害な間違いとして処理されるようになります。

さて、超精密な車輪を作りたいのですが、すべてのセンサーに対して別々のトラックを用意するためのスペースが足りないとしましょう。そこで、**シングルトラック・グレイコード（Single-Track Gray Codes）**が登場します。多くの異なるトラックを持つ代わりに、情報を一つのトラックに凝縮し、それをコピーしてずらしながら配置します。これは、コードが書かれた一本の長いリボンを車輪に巻き付け、センサーが異なる開始点からそれを読み取るようなものです。魔法のようなことに、この一本のリボンは、異なる角度から読み取られたとしても、「一度に一つのことしか変えない」というルールを依然として守っています。

長い間、科学者たちはこれらを単純な「はい／いいえ」（バイナリ）システムのために作る方法は知っていましたが、あらゆるサイズの車輪に対して、特に、すべての位置を飛ばすことなく表示できるような仕組みを作る方法については、壁に突き当たっていました。また、0、1、2、3、4といった数字を使用するより複雑なシステム（非バイナリ・システム）において、これらを機能させることにも苦労していました。

---

この論文は、その壁を打ち破るためのものです。T. Etzion率いる著者たちは、3や5といった素数をアルファベットサイズ（基数）として使用するシステムに対して、これらの特別な「シングルトラック」コードを構築する方法を解明しました。彼らは単に推測したのではなく、数学的なマシン——再帰的なレシピ——を構築することで、これらのコードが特定のサイズ（$p$が3または5であるときの$p^t$の長さ）において確実に存在することを証明しました。

以下に、いくつかの遊び心のある比喩を用いた、彼らの手法の物語を紹介します。

構成要素： 「自己双対（Self-Dual）」のリボン

コードを構築するために、著者らは特別な材料を必要としました。数字のパターンが描かれた長い紙の帯を想像してください。次に、「魔法の鏡」を想像してください。この鏡は、すべての数字に1を加えます（つまり、0は1になり、1は2になり、2は0へと循環します）。

通常、元の帯と鏡に映した帯を見比べると、それらは全く別物に見えます。しかし、著者らが求めたのは、鏡像を適切な量だけずらすと、元の帯と全く同じに見えるような特別な帯でした。彼らはこれを**自己双当シーケンス（Self-Dual Sequences: SDS）**と呼んでいます。これらは、特定の種類の魔法のような変換の下で、完璧に対称性を持つリボンのようなものです。

この論文は、3または5の記号を使用するシステムにおいて、これら無限に供給可能なリボンを作成できることを証明しています。彼らはステップ・バイ・ステップのレシピを示しました。小さなリボンを取り、そこにいくらかの「風味」（$Z$や$Y$と呼ばれる数学的な言葉）を加えれば、ほら、より大きな完璧なリボンができあがります。これはフラクタルのようです。小さなパターンを取り、ルールを適用すれば、そのパターンは成長し、依然としてその特別な対称性を保ったまま、より大きなパターンへと進化します。

組立ライン： リボンの縫い合わせ

リボンを手に入れただけでは、戦いの半分しか終わっていません。それらを特定の順序で並べる必要があります。もしリボンをただ積み重ねてしまったら、センサーは混乱してしまいます。

著者らは、次のリボンへ移動するときに、コード内のたった一つの位置だけが変化するように、これらのリボンを配置しなければなりませんでした。これが最も難しい部分です。それは、カードの束を並べるようなものです。カードを一枚入れ替えるたびに、そのカードの値だけを変えることができ、かつ、決して途中で行き詰まることなく、最終的にスタート地点へとループして戻ってこなければなりません。

3（三分位システム）および5（五分位システム）について、著者らはこれを行う方法を見つけ出しました。彼らは巧妙な「マージ（結合）」テクニックを用いました。いくつかのリボンのグループがあると想像してください。いくつかのグループは非常に似通っており、ほんのわずかな一点だけが異なります。著者らは、二つのグループを取り、その差がある正確な場所を見つけ出し、それらを編み合わせることで、より大きなグループを作り上げながら、「一度に一つのことしか変えない」というルールを維持する方法を示しました。

彼らは、3または5の累乗に基づくサイズ（$3^2, 3^3, 5^2$など）において、これらのリボンを縫い合わせてフルピリオド（全周期）のコードを形成する方法が常に存在することを証明しました。これは、このコードが、欠落することなくあらゆる可能な位置（$m^{m^t}$個のコードワード）を表現できることを意味します。

彼らが「しなかった」こと（そして排除したこと）

この論文が述べているのではない、ということも知っておくことは重要です。

• それはあらゆる数字のための魔法の杖ではない： 著者らは、バイナリ・システム（0と1のみを使用する場合）では、$n=2$以外のサイズでフルピリオドのシングルトラック・コードを作ることはできないと明言しています。彼らは、より大きなバイナリの車輪に対して、それが不可能であることを証明しました。
• まだすべての素数のためのものではない： 著者らは、3と5については証明しましたが、より大きな素数（7、11、13など）については、まだ「種（シード）」となるリボンを見つけていないことを認めています。彼らは、レシピ自体は機能するはずだと考えていますが、まず最初に始めるべきパターンを見つける必要があると考えています。
• ほとんどの場合、非素数のためのものではない： サイズ4の具体的な例は示していますが、彼らの主要で厳密な証明は、素数のためのものです。

結論

この論文は、これらのコードが存在する可能性を示唆しているだけではありません。3と5に基づく無限のサイズのファミリーに対して、それらが存在することを証明しています。彼らは、数学的な「設計図」（再帰的構成）と、（$p=3$および$p=5$のための）「スターターキット」（種）を提供しました。

好奇心旺盛なティーンエイジャーや、高速センサーを設計しているエンジニアにとって、これは大きな出来事です。これは、新しいクラスの機械のすべてにおいて、より小さく、より精密で、エラーが起きにくいエンコーダーを作ることができるようになることを意味します。著者らは、適切な数学的ツールがあれば、以前は不可能だと思われていた方法で情報を整理できることを示し、新たな扉を開きました。彼らは単に干し草の山の中から針を見つけたのではありません。干し草の山が3と5で作られている限り、無限の干し草の山から針を見つけ出すことができる「機械」を構築したのです。