Magma - 東北大学 大学院 情報科学研究科 数学教室

Magma へ貢献できること
原田 昌晃
山形大学理学部
「Magma で開く数学の世界」高知大学
(２０１２年７月２２日)
1 / 13
Magma ユーザーとして (自己紹介を兼ねて)
Magma との出会い：
第３９回 代数学シンポジウム (愛媛大、１９９４年)
中村 憲、最近の計算機代数の理論と応用
Magma を使い始めた時期：
博士課程 (岡山大) の１年か２年のとき (１９９４年か
１９９５年)
Magma を使うメリット：
代数系の幅広い分野をカバーする統合ソフト
（昔は扱う分野は少なかった）
最先端のアルゴリズムが実装されている場合が多い
（昔はかなり遅かった）
Magma に関するイベント：
原田–木田, 「Magma」, 数学セミナー（特集：数学を発
展させるコンピュータソフト）, ２０１０年９月号
研究集会「Magma で広がる数学の世界」
（２０１０年１０月, 九州大, 木田–原田–横山）.
2 / 13
本題：ユーザーが Magma へ貢献できることは？
(1) Magma の良さを周辺の方に伝える
（→ユーザーの多いシステムに）
(2) バグを Magma の開発グループへ報告
（→信頼あるシステムに）
「公式サイト」→「FAQ」→「How do I report a bug?」
(3) ユーザー作成の関数を Magma の開発グループへ提供
（→魅力あるシステムに）
(4) データベースを Magma の開発グループへ提供
（→魅力あるシステムに）
(3) と (4) について John Cannon (開発グループの代表者)
と相談した内容を報告したい.
3 / 13
ユーザー作成の関数を Magma への提供
John Cannon にユーザー作成の関数の提供について尋ねた：
¶
³
【John Cannon からの回答】
We strongly encourage users to propose code they have
written become part of the official release of Magma.
We have many such contributions already and this source
is important to the expansion of the system.
Our users have all sorts of expertise that we ourselves lack.
µ
´
Magma 開発グループは, ユーザー作成の関数の提供を歓迎
している (特に, 開発グループに専門家がいない分野)
例：Lattice(C, "A"): code C から lattice を構成する関数
「codes over Fp 」→「codes over Z/kZ」
(p: 素数, k: 整数 (k ≥ 2))
結論：汎用性のある関数の場合は問い合わせを！
4 / 13
データベースの Magma への提供例の紹介
Harada–Munemasa, “Database of self-dual codes”:
www.math.is.tohoku.ac.jp/~munemasa/selfdualcodes.htm
２００７年１２月より self-dual code の分類結果を
データベースとして提供
扱っている内容：
以下のタイプの self-dual code について分類が終わって
いる全ての長さの分類結果のデータを提供
(最新の分類結果を反映させてデータベースを更新中)
Self-dual codes over Fp (p = 2, 3, 5, 7)
Hermitian self-dual codes over F4
Self-dual codes over Z/kZ (k = 4, 6, 8, 9, 10)
5 / 13
データのフォーマット：Magma
Magma のユーザーであればダウンロードすればすぐに
データを使うことが出来る
→【これで十分？】
問題点：
code の個数が多い場合, 読み込むのに非常に時間が掛
かり, メモリを消費
例えば, (長さ 40 の binary self-dual code の) あるケースは
1511827 個あり, ファイルのサイズは約 2.4GB
ファイルの読み込み：
Total time: 173700.989 seconds, (約４８時間)
Total memory usage: 21169.28MB
(
)
Intel Core i7 3960X 3.30GHz (4.7 GHz にクロックアップ)
メモリ: 32GB, SSD: 120GB.
6 / 13
２００７年１２月：
分類結果をデータベースとして提供開始
２０１１年４月：
Magma のデータベースとして取り込めないかと John
Cannon に尋ねたところ, 欲しいデータの一つだったの
是非行いたいとの回答
この時点で打診した理由：
「長さ 40 の binary doubly even self-dual code」の分類
が完成した (→「後半」でこの辺りを簡単に説明)
一つ前のスライドでの問題点について：
John Cannon から Magma がデータベースとして取り
込めばこの問題点は解決される (作業のメリットあり)
現時点：
まだデータベースにはなっていない (作業の順番待ち？)
結論：データベースを構築されている方, 問い合わせを！
7 / 13
数学の話を：Binary doubly even self-dual code の分類について
F2 = {0, 1}: 位数 2 の有限体
C: binary [n, k] code ⇐⇒ Fn2 の k 次元部分空間
def
n を C の長さとよぶ
以下 C を長さ n の binary code とする
¶
【code (符号) とは】
³
起源は情報科学 (C. Shannon (1948))
通信路における符号化 (encoding) の数理モデルとして定義さ
れた組合せ構造 (と思える)
他の分野との関連：格子, 有限群, 不変式環など
(例えば Leech 格子, マシュー単純群の (簡単な) 構成).
µ
´
8 / 13
x = (x1 , . . . , xn ) の weight wt(x) ⇐⇒ #{i | xi 6= 0}
def
C: self-dual ⇐⇒ C = C ⊥ (= {x ∈ Fn2 | x · y = 0 (∀y ∈ C)})
def
C: self-dual ⇒ wt(x) ≡ 0 (mod 2) (∀x ∈ C)
C: self-dual
C: doubly even
C: singly even
⇐⇒ wt(x) ≡ 0 (mod 4) (∀x ∈ C)
def
⇐⇒ ∃x ∈ C s.t. wt(x) ≡ 2 (mod 4)
def
(Gleason–Pierce Theorem (1969))
C: self-dual code ⇐⇒ n ≡ 0 (mod 2)
C: doubly even self-dual code ⇐⇒ n ≡ 0 (mod 8)
(Gleason Theorem (1970)).
doubly even self-dual code の例: 長さ 24 の Golay code
9 / 13
最近の分類の進展について
C, C 0 : 同値 (C ∼
= C 0 ) ⇐⇒ ∃σ ∈ Sn s.t. C σ = C 0
def
(Sn : n 次対称群, C σ = {xσ | x ∈ C})
Cn : 全ての長さ n の doubly even self-dual code の集合
Dn : Cn / ∼
= の各同値類の代表元の集合
(互いに非同値な長さ n の doubly even self-dual code の集合)
doubly even self-dual code の分類結果
長さ n
8
16
24
32
40
#Dn
1
2
9
85
94343
Reference
Pless (1972)
Pless (1972)
Pless–Sloane (1975)
Conway–Pless–Sloane (1992)
Betsumiya–H–Munemasa (201x)
10 / 13
分類のアルゴリズム (Mass formula)
C の automorphism group Aut(C) = {σ ∈ Sn | C σ = C}
Mass formula (MacWilliams–Sloane–Thompson (1972)):
n
−2
2
⇒
∏
(2i + 1) = #Cn
i=0
||
∑
n!
# Aut(C)
C∈D
n
n!
( # Aut(C)
= #{D ∈ Cn | C ∼
= D})
分類のアルゴリズム：
n!
非同値な doubly even self-dual code の構成を # Aut(C)
の
和が #Cn に達するまで繰り返す.
11 / 13
Example (長さ 16 の分類)
(「公式サイト」→「Documentation」→「Handbook」→)
「Coding Theory」→「Linear codes over finite fields」
長さ 16 の非同値な doubly even self-dual code を 2 つ
構成
> e8:=ExtendCode(QRCode(GF(2),7));
> J:=Matrix(GF(2),8,[1:i in [1..8^2]]);
> I:=IdentityMatrix(GF(2),8);
> C:=[DirectSum(e8,e8),LinearCode(HorizontalJoin(I,J+I))];
> [IsSelfDual(x) and IsDoublyEven(x): x in C];
[ true, true ]
> IsEquivalent(C[1],C[2]);
false
これ以外に存在しないことを mass formula で確認
> &*[2^i+1: i in [0..(16/2)-2]]
> eq &+[Factorial(16)/#AutomorphismGroup(x): x in C];
true
12 / 13
おわりに
今後も Magma が魅力あるシステムとして成長し続け
るために, 今回, ユーザーが出来ることについて考えて
みました.
新しい関数を作ったりデータベースを構築されている
方がおられると思います. Magma の開発グループに問
い合わせをしてみて下さい.
ご清聴ありがとうございました
13 / 13