Juliaで有限体を扱ってみたいなら...
Juliaで森博嗣さんのビリヤード問題な完全差集合の問題を解きたい
そのためには先ず, 有限体をJuliaで扱えるようになる必要がある。
とはいえ, Nemo.jpというパッケージがあるので先ずはそのパッケージでの有限体の扱いに慣れるところから。
Nemo.jpを用いる
JuliaのインストールやJuliaを用いる環境としてのJupyter Notebookの導入などは様々にwebに指南があるのでここでは詳細は省く。
この記事を書いてる環境は2024.6.22.現在で
マシンはMacBookPro(2023.11.M3,16GB), OSはMacOSX14.5なSonoma.
JuliaのVERSIONは1.10.4, Nemo は, 0.45.5
using Nemo
Packageが導入できていれば, Jupyter Notebookでは次のように表示されます。
Welcome to Nemo version building
Nemo comes with absolutely no warranty whatsoever
では実際に有限体を使ってみましょう。
Nemoで有限体を設定する
有限体とは何か？
「位数が有限である体を有限体（またはガロア体）と言います。」
「大雑把に言うと，四則演算ができる有限集合のことです。」
と某「高校数学の美しい物語」には書いてあります。まぁ慣れていない人にはそれで十分かも。
具体的には例えばGF(2)で位数2のガロア体を表すとして,
GF(2)の要素の数は位数と表現されそれが2なので通常は
Nemoでは
F2 = GF(2)
のようにして有限（ガロア）体F2を指定します。
すると,
Prime field of characteristic 2
のように表示され, F2を用いる準備ができます。
ここでF2を表示させようとして,
F2
としても先ほどと同じ
Prime field of characteristic 2
という表示しか返ってきません。
そこで例えば,
for a ∈ F2
print(a,", ")
end
とすると,
0,1,
のように, 想定していた通りのF2の要素というか元を表示して返してくれます。
尚, 「∈」は「集合に元が含まれる」という記号ですが, jupyter notebookの場合は,
「\in」と打ち込んでからtabキーを押すと「∈」に変えて使えます（有り難く便利です）。
a in F2でも同様（というか本来はこちら？）にできますが, 見易いので「∈」を用いています。
有限体の拡大体も
ビリヤード問題を解くには, 拡大体が必要になります。
F4 = GF(2,2)
で, 位数
Finite field of degree 2 and characteristic 2
のように表示されます。(拡大)次数
有限体は位数が素数の冪乗であれば存在することが分かっています。
Wikipediaには
係数一変数多項式環 \mathbf{F}_2 を考える。 \mathbf{F}_2[x]
その既約多項式の生成する素イデアル f(x) = x^2 + x + 1 は、 (f(x)) がPIDなので、特に極大イデアル。したがって剰余環 \mathbf{F}_2[x] は 4 個の元からなる体である。 \mathbf{F}_4 = \mathbf{F}_2[x]/(f(x))
変数の自然な全射による像を x とおくと、 ω と表せ、その演算は関係式 \mathbf{F}_4 = \{0,\ 1,\ ω,\ ω^2\} から定まる。 ω^2 + ω + 1 = 0
とあり, 「素イデアル」や「自然な全射」など初心者には分かり難い表記はあるものの, 既約多項式によって拡大される事は理解できるかも。
ここで先ほどと同様にF4の中身を見たいとなると,
for a ∈ F4
print(a,", ")
end
とすれば良いわけですが, 実際に打ち込んでみると
0, 1, o, o + 1,
と返ってきます。oって何？って感じですが, これはWikipediaの解説にある
いやいや普通
F4 = GF(2,2,"ω")
とすれば,
この「ω」も「∈」同様で「\omega」と打ち込んでからtabキーを押すと「ω」に変わって使えます。
こうしておいて,
for a ∈ F4
print(a,", ")
end
とすれば,
0, 1, ω, ω + 1,
と返してくれるわけです。
では, 既約多項式について確認してみましょう
そもそも既約多項式とは何でしょう。
既約多項式とは「それ以上因数分解できない多項式」といえば良いでしょうか。
例えば, GF(2)を係数とする多項式環で1次の既約多項式は,
では2次だとどうでしょうか。
「GF(2)を係数とする多項式環」なので係数は
だから, 2次の多項式は
此の内
残るは
此の内,
係数がGF(2)なので,
最後の
色々と手法はあるようですが, 最も単純なのは, 合成できる多項式を列挙して確認する方法です。
つまり,
のように, 合成できる多項式を全部確認するという手法で, 此の表に現れない
ちなみに
defining_polynomial(F4)
とすると, F4の生成多項式（既約多項式の一つ）が表示されますが,
x^2 + x + 1
と返ってきます。
3次の既約多項式についてはどうしましょうか
先程と同様に, 3次の合成できる多項式を確認すれば良いでしょう。
そして, 「GF(2)を係数とする3次の多項式」は
（...もう此の程度で見て確認するのは困難かも...）
結局どうすれば既約多項式が確認できるか...
結局,
コレをJuliaで実装してみましょう。
この実装の前に少し確認をしておきましょう。
例えば,
F8=GF(2,3,"ω")
として,
Finite field of degree 3 and characteristic 2
となり,
defining_polynomial(F8)
に対しては,
x^3 + x + 1
と返ってきて,
for a ∈ F8
print(a,", ")
end
に対しては,
0, 1, ω, ω + 1, ω^2, ω^2 + 1, ω^2 + ω, ω^2 + ω + 1,
となります。
生成多項式である既約多項式は3次になるわけです。
ではやってみたコードを。
先ずは,
all_perm(x, n) = vec(map(collect, Iterators.product(ntuple(_ -> x, n)...)))
という重複順列を列挙するall_perm(配列,項数)というfunctionを拵えます。
その上で,
p,n=2,2
Fp = GF(p,n,"α")
S, x = Fp["x"]
println(Fp,", ",S)
Fpl=[]
for a in Fp
push!(Fpl,a)
end
println(Fpl)
のようにして, 有限体を配列Fplにセットして, その配列を係数とした多項式を列挙していきます。
alst=[]
m=3
for i=1:m-1
push!(alst,[])
end
for i=1:round(Int8,m/2)
for a ∈ all_perm(Fpl, i)
f=x^i
for j=1:i
f=f+a[j]*x^(j-1)
end
push!(alst[i],f)
end
end
l=length(alst)
blst=[]
for i=1:m-l
for a ∈ alst[i],b ∈ alst[l-i+1]
push!(blst,a*b)
end
end
unique!(blst)
clst=[]
for a ∈ all_perm(Fpl, m)
f=x^m
for j=1:m
f=f+a[j]*x^(j-1)
end
push!(clst,f)
end
dlst=[]
for c ∈ clst
if !(c ∈ blst)
push!(dlst,c)
end
end
println(dlst)
Any[x^3 + α, x^3 + α + 1, x^3 + x + 1, x^3 + αx + 1, x^3 + (α + 1)x + 1, x^3 + x^2 + 1, x^3 + x^2 + x + α, x^3 + x^2 + x + α + 1, x^3 + x^2 + αx + α + 1, x^3 + x^2 + (α + 1)x + α, x^3 + αx^2 + 1, x^3 + αx^2 + x + α + 1, x^3 + αx^2 + αx + α, x^3 + α*x^2 + (α + 1)x + α, x^3 + αx^2 + (α + 1)*x + α + 1, x^3 + (α + 1)*x^2 + 1, x^3 + (α + 1)*x^2 + x + α, x^3 + (α + 1)x^2 + αx + α, x^3 + (α + 1)x^2 + αx + α + 1, x^3 + (α + 1)*x^2 + (α + 1)*x + α + 1]
Discussion