フィールズ賞 2022と符号理論

2022年7月5日
国際数学者会議にて
フィールズ賞の受賞者が発表されました。

数学界のノーベル賞に例えられる権威ある賞です。
ただし、40歳以下限定である、若手の賞という側面もあります。

2022年の受賞者は4名。
そのうち1名が女性でした。
女性のフィールズ賞受賞者は2人目。
彼女の名前はマリナ。マリナ・ヴィヤゾフスカ。

受賞理由は、球の充填問題を大きく前進させたこと。

球の充填問題とは、
 同じ大きさのボールを沢山詰める方法を求めよ
という問題です。

空間の次元によって答えが異なります。
 2次元版なら、机の上に10円玉を沢山並べる方法。
 3次元版なら、箱の中にボールを沢山並べる方法。
彼女より前は、1,2,3,4次元まで答えがわかっていました。
ただし、3次元版の答えが分かったのは最近で、
分かるまで350年かかったという難問。

マリナ・ヴィヤゾフスカさんは、
8次元版と24次元版を解決
という偉業を達成したのです。
凄い!

さて、なぜこの話に萩原が飛びついているかというと、
 符号理論と関係が濃いから。

座標の値を、
 実数体から有限体に変えた問題が
  符号理論の目的である
   誤り訂正符号の符号語を増やすこと
なんです。
言い換えると
 通信効率を上げること
なんです。

ちなみに実数体版と違って有限体版だと、
 次元だけでなく、
 球の半径によって
答えが変わります。

さらに実数体版と違うのは、
 空間全てを埋め尽くせることがある
という摩訶不思議な現象が発生します。
そのような埋め方を、符号理論では
 完全符号
と呼びます。

これらだけでも繋がりとして魅力的ですが、
もっと踏み込んだ繋がりもあります。
それが、
 拡張ハミング符号とE8格子
 拡張Golay符号とリーチ格子
です。
 
拡張ハミング符号と拡張Golay符号は誤り訂正符号と呼ばれる対象です。

その昔ハードディスクの誤り訂正に使われていた「ハミング符号」に
ひと手間加えたのが拡張ハミング符号。
千葉大の数学・情報数理学科では、ハミング符号を3年生で学びます。

かなり昔ですが、宇宙探査機でも通信方式に使われていた「Golay符号」に
ひと手間加えたものが拡張Golay符号。
ごめん、千葉大の数学・情報数理学科では僕が教えてない。来年から教えようかな。

ハミング符号は7次元空間の半径1の球により、
Golay符号は23次元空間の半径3の球により
それぞれ二元体版の球の充填問題の解になっています。
つまり、どちらも完全符号です。

ひと手間加えることで
拡張ハミング符号は 8(=7+1)次元空間に、
各行Golay符号は 24(=23+1)次元空間に、
それぞれ1次元ずつ大きくなります。


拡張ハミング符号に更に手を加えると
 E8格子、
拡張Golay符号に更に手を加えると
 リーチ格子、
と呼ばれる数学構造を構成できます。
実数座標を持つ空間上に点をポツポツ置いた雰囲気の構造です。

拡張ハミング符号の符号長8に由来して、
 E8格子の次元が8になります。
拡張Golay符号の符号長24に由来して、
 リーチ格子の次元が24になります。
このE8格子とリーチ格子の各点に球の中心を配置したものが、
 同じ大きさのボールを沢山詰める方法
になっていました。

8次元版では、
 E8格子が活用できる
という予想が以前から知られていましたが、
最後の一手を
マリナ・ヴィヤゾフスカさんが
仕上げたのです。

さらに、
24次元版で
 リーチ格子が活用できることも、
マリナ・ヴィヤゾフスカさんらのグループが
解決しました。
 
符号理論に関係するフィールズ賞。
嬉しいですなー。

余談ですが、
フィールズ賞授賞式の数日前、
会場付近を散歩してました。

式典会場とは全く知らず(笑

仕事でヘルシンキ(フィンランド)に行ってました。
符号理論のシンポジウムでした。

Tooloという地域にホテルをとって、
Aalto大学のメインキャンパスであるEspooへ。

 

Aalto大学Espoo。大学のロゴは A!
キャンパス内で見かける日本語。ちなみに、千葉大とアールト大学芸術デザイン校は大学間協定を結んでます。
国際シンポジウム ISIT202

帰国後、授賞式の中継を見ていたら、
 会場が
 Aalto大学Tooloキャンパス
だったという。
ちょっと惜しい感じ!!!

Tooloキャンパスのすぐ傍に、
観光名所
 岩の教会(Rock Church)。
現地の言葉で
 テンペリアウキオ
があります。
側壁が岩で、天井が木で作られた不思議な教会。

テンペリアウキオ内部の
写真を撮ってきました。

岩の教会:テンペリアウキオ:Rock Church

写真右下の方に、なにやらオブジェがあったので、3Dスキャンしてきました。

テンペリアウキオの何か

余談が続きましたが
マリナさんを含め、受賞者の皆さん
おめでとうございます!


削除符号論文メモ:2022/04/05

タイトル:Constructions of ℓ-Adic t-Deletion-Correcting Quantum Codes
著者名:Ryutaroh MATSUMOTO; Manabu HAGIWARA
雑誌名:IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
号数:Volume E105.A, Issue 3
DOI:https://doi.org/10.1587/transfun.2021EAP1034

Abstract:We propose two systematic constructions of deletion- correcting codes for protecting quantum inforomation. The first one works with qudits of any dimension ℓ, which is referred to as ℓ-adic, but only one deletion is corrected and the constructed codes are asymptotically bad. The second one corrects multiple deletions and can construct asymptotically good codes. The second one also allows conversion of stabilizer-based quantum codes to deletion-correcting codes, and entanglement assistance.

削除符号論文メモ:2022/01/18

タイトル: Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
著者名: Ryan Gabrys, Venkatesan Guruswami, Joao Ribeiro, Ke Wu
アクセス: https://arxiv.org/pdf/2112.09971.pdf

Abstract: We consider the problem of designing low-redundancy codes in settings where one must correct deletions in conjunction with substitutions or adjacent transpositions; a combination of errors that is usually observed in DNA-based data storage. One of the most basic versions of this problem was settled more than 50 years ago by Levenshtein, who proved that binary Varshamov-Tenengolts codes correct one arbitrary edit error, i.e., one deletion or one substitution, with
nearly optimal redundancy. However, this approach fails to extend to many simple and natural variations of the binary single-edit error setting. In this work, we make progress on the code design problem above in three such variations…



タイトル: Constructions of asymptotically optimal codebooks with respect to Welch bound and Levenshtein bound
著者名: G Wang, DM Xu, FW Fu
ジャーナル: Advances in Mathematics of Communications, 2021
アクセス: https://www.aimsciences.org/article/doi/10.3934/amc.2021065

Abstract: Codebooks with small maximum cross-correlation amplitudes are used to distinguish the signals from different users in code division multiple access communication systems. In this paper, several classes of codebooks are introduced, whose maximum cross-correlation amplitudes asymptotically achieve the corresponding Welch bound and Levenshtein bound. Specially, a class of optimal codebooks with respect to the Levenshtein bound is obtained. These classes of codebooks are constructed by selecting certain rows deterministically from circulant matrices, Fourier matrices and Hadamard matrices, respectively. The construction methods and parameters of some codebooks provided in this paper are new.