A complex Hadamard matrix of order 94

この論文では、Kharaghani と Seberry の基本ブロック構成法を修正し、特定の奇数次巡回行列を用いて複素ハダマード行列を構成する方法を示し、特に $p=47$ の場合の計算機支援探索により、94 次複素ハダマード行列の存在を初めて証明しました。

要約

94 階の「完璧なパズル」が見つかった話

～数学の難問を解決した、コンピューターと人間のタッグ～

この論文は、数学の「ハダマール行列（Hadamard matrix）」という、一見すると難しそうなパズルを解いたというお話しです。特に、**「94 階（94×94）」**という巨大なパズルを、これまで誰も完成させたことのない方法で初めて完成させたという、画期的な成果を報告しています。

これを一般の方にもわかりやすく説明するために、いくつかの比喩を使って解説しましょう。

1. 何を作ろうとしているのか？「完璧なバランスのテーブル」

まず、ハダマール行列とは何か想像してみてください。
それは、94 行 94 列の巨大な表（マス目）です。それぞれのマスには「＋1」か「－1」が入っています。

この表のすごいところは、**「どの行とどの行を比べても、お互いが完全に干渉し合わない（直交する）」**という性質を持っている点です。
例えば、2 人の人が同じテーブルで話しているとき、お互いの声が全く混ざらず、クリアに聞こえるような状態です。
この「完璧なバランス」を保つ表は、通信技術や暗号、実験の設計など、現代社会の裏側で非常に重要な役割を果たしています。

2. 過去の壁：「47 階の壁」

この表を作るには、いくつかの「部品（ブロック）」を組み立てる必要があります。
以前から、**「47 階（47×47）」**というサイズの部品を 4 つ集めて、それらを組み合わせることで「94 階」の表を作れることが知られていました。

しかし、ここには大きな壁がありました。

• 従来の方法： 4 つの部品はすべて「対称的（左右対称）」である必要がありました。
• 現実： 47 階の「完全な対称部品」は、実は存在しないことが証明されていました。
  • これは、「47 階のレゴブロックで、左右対称の形をしたピースが見つからない」というような状態です。
  • そのため、94 階の表を作ることは「不可能」だと思われていたのです。

3. 新発想：「鏡と回転」の魔法

著者のフェレンツ・ショッロシさんは、この壁を打破するために、「組み立て方（レシピ）」を少し変えるという大胆なアイデアを思いつきました。

• 従来のレシピ： 「4 つとも対称な部品」が必要。
• 新しいレシピ： 「2 つは対称で、残りの 2 つは鏡像（裏返し）や回転をさせたもの」でも大丈夫。

これを料理に例えると、これまで「4 つとも同じ形をした卵」しか使えなかったレシピでしたが、「2 つはそのままの卵、残りの 2 つは卵をひっくり返した形（鏡像）でも大丈夫」という新しいルールを見つけたようなものです。
これにより、47 階の部品が見つからなくても、94 階の表が作れる可能性が生まれました。

4. 実戦：コンピューターによる「宝探し」

新しいレシピが見つかったとしても、実際に「47 階の部品（2 つは対称、2 つは自由）」が存在するかどうかは、手作業では探せません。あまりにも組み合わせが多すぎるからです。

そこで著者さんは、コンピューターに頼りました。

• 探検隊： コンピューターが、47 階の部品候補となる無数のパターンを次々と生成しました。
• フィルター： 条件（特定の数学的なルール）を満たすものだけを厳選しました。
• 大発見： 約 80 億回以上の試行の後、ついに**「条件を満たす 4 つの部品」**が見つかりました！

これは、砂漠の砂粒の中から、特定の形をした 4 つの砂粒を、偶然ではなく計算によって見つけたようなものです。

5. 結果：94 階の「完璧なパズル」完成

見つかった部品を、新しいレシピ（定理 4）に当てはめて組み立てると、見事**「94 階のハダマール行列」**が完成しました。

• 意義： これまで「94 階の表は作れない」と思われていた領域を、初めて開拓しました。
• 次の目標： この成功は、さらに大きな「118 階（59 階の部品を使う場合）」などの難問にも挑戦する道を開きました。

まとめ

この論文は、**「既存のルールでは不可能だと思われていたことを、新しい視点（レシピの変更）と、強力なコンピューターの力（宝探し）によって実現した」**という物語です。

数学の世界では、小さな数字（47）の組み合わせが、巨大なシステム（94）の完成を左右します。著者さんは、その鍵となる「部品」を、従来の常識にとらわれずに探し出し、世界に新しい「完璧なバランスの表」をもたらしました。

これは、単なる数字遊びではなく、将来の通信技術や科学の発展につながる、非常に重要な一歩なのです。

技術概要

フェレンツ・ゾロシ（Ferenc Szöllősi）による論文「A COMPLEX HADAMARD MATRIX OF ORDER 94（94 次複素ハダマード行列）」の技術的サマリーを以下に示します。

1. 研究の背景と問題設定

• ハダマード行列の定義: 実ハダマード行列 $H$ は、要素が $\{-1, 1\}$ であり、$HH^T = nI_n$ を満たす $n$ 次正方行列です。複素ハダマード行列は、要素が $\{-1, -i, 1, i\}$ であり、行同士が複素直交する行列です。
• ウィリアムソン法と課題: 従来の実ハダマード行列の構成法としてウィリアムソン法があり、4 つの対称な巡回 $\{-1, 1\}$ 行列（ウィリアムソン行列）を用いて $4p$次の行列を構成します。しかし、$p=35$や$p=47$ などの特定の次数では、ウィリアムソン行列が存在しないことが知られています。
• 複素ハダマード行列への拡張: カラガニとセベリー（Kharaghani & Seberry）は、ウィリアムソン行列を用いて $2p$次の複素ハダマード行列を構成する手法を示しました。しかし、$p=47$ の場合、ウィリアムソン行列が存在しないため、この手法を直接適用することはできませんでした。
• 本研究の目的: $p=47$（すなわち $2p=94$）の次数において、複素ハダマード行列を初めて構成することです。

2. 手法と理論的枠組み

本研究は、既存の構成法を改良し、コンピュータ支援探索を組み合わせるアプローチを取っています。

理論的改良（Goethels–Seidel 配列の修正）

• 既存の限界: 従来のカラガニ・セベリーの構成法（定理 3）では、4 つのブロック行列がすべて互いに「友好的（amicable）」である必要があり、通常は対称な巡回行列を要求します。$p=47$ では対称なウィリアムソン行列が存在しないため、このアプローチは失敗します。
• 新しい構成定理（定理 4）: 著者は、Kharaghani-Seberry の構成法を修正し、**「少なくとも 2 つのブロック行列が対称であればよく、残りは巡回行列であればよい」**という新しい構成法を提案しました。
  • 具体的には、$A, B$ を対称な巡回 $\{-1, 1\}$ 行列、$C, D$ を巡回 $\{-1, 1\}$ 行列とし、これらが特定の条件（式 (1)）を満たす場合、以下の $2p$次行列$K$ が複素ハダマード行列となります。
  • この構成では、後対角行列 $R$ を用いて $C$ と $D$ を変換し、対称性を保ちつつ柔軟性を高めています。
  • 条件: $A, B$ は対称、$C, D$ は巡回、かつ $AA^T + BB^T + CC^T + DD^T = 4pI_p$。

探索アルゴリズム（第 3 章）

• 対象: 次数 $p=47$ において、対称性が $(ssxx)$（2 つが対称、2 つは任意）の巡回行列の組 $(A, B, C, D)$ を見つけること。
• 制約条件の活用:
  • 行和 $\sigma_A, \sigma_B, \sigma_C, \sigma_D$ に関する制約（式 (2): $\sum \sigma^2 = 4p$）。
  • 巡回行列の固有値に関する制約（式 (3): 行和の絶対値の上限）。
• ハッシュベースの探索:
  1. 対称行列 $A, B$ の候補を生成し、その周期性自己相関ベクトル $I(a), I(b)$ を計算。
  2. 和 $\Sigma = I(a) + I(b)$ を計算し、そのノルムが閾値 $B$ 以下の場合、ハッシュ関数 $h(\Sigma)$ を用いて辞書に格納。
  3. 対称行列ではない $C, D$ の候補をランダムに生成し、$-\Delta = I(c) + I(d)$ を計算。
  4. 辞書に $\Delta$ が存在するか検索し、一致すれば $(A, B, C, D)$ の組を復元。
• 計算リソース: $p=47$ において、約 $8 \times 10^9$ 回の試行を行い、約 20GB のメモリと 1 日強の計算時間を要しました。

3. 主要な成果

• 定理 1 の証明: 上記の理論的構成（定理 4）と、コンピュータ探索によって発見された $p=47$ における具体的な巡回行列の組（例 1 および例 2）を組み合わせることで、94 次の複素ハダマード行列の存在を初めて証明しました。
• 発見された行列の具体例:
  • 例 1: 行和 $(\sigma_A, \sigma_B, \sigma_C, \sigma_D) = (3, 7, 7, 9)$。自己相関和のノルムは 796。
  • 例 2: 行和 $(\sigma_A, \sigma_B, \sigma_C, \sigma_D) = (-1, -5, 9, 9)$。自己相関和のノルムは 1116。
  • これらの行列は、0 を -1 に置き換えた 47 行の行列から巡回シフトによって生成されます。

4. 意義と今後の展望

• 未解決問題の解決: $p=47$ における複素ハダマード行列の構成は長年の未解決問題でした。本研究は、ウィリアムソン行列が存在しない次数でも、対称性の要件を緩和することで構成可能であることを示しました。
• 構成法の一般化: 本研究で提案された「2 つの対称行列のみでよい」という構成法は、他の次数や、より少ない対称性を持つ行列（例：1 つのみ対称）の探索にも応用可能です。
• 今後の課題:
  • $p=59$（118 次）など、より大きな次数への拡張。
  • 超計算資源と高度な探索アルゴリズムの組み合わせによる、より広範な次数での行列発見。
  • 対称性の要件をさらに緩和した構成法のさらなる改良。

まとめ

この論文は、組合せ数学における重要な未解決問題である「94 次複素ハダマード行列の存在」を、既存の構成法の理論的改良と大規模なコンピュータ探索によって解決した画期的な研究です。特に、ウィリアムソン行列の存在しない次数においても、対称性の要件を部分的に緩和する新しい構成枠組みを確立した点が、今後のハダマード行列研究に大きな影響を与えると考えられます。