最も点と直線の数が少ない二次元射影幾何

PG(2,2)

ref Coxeterの記号法

lineは7本

円も含める

e.g. [100]

点Pがファの平面の点であるとき、P\in\mathrm{PG}(2,2)のように表記する

e.g. (1,0,0)\in\mathrm{PG}(2,2)

「Q\in\mathrm{PG}(2,q)」のような表記を見たときに、「Qは点である」ということを思い出したい

点は7個

e.g. 111

具体例

上図の3点100, 101, 001から成るlineを[abc]((a, b, c)\ne (0,0,0))とすると、

abcと3点の内積が0なので、[abc] = [010]と分かる

PG(2,q)のlineの定義を使っている

もっと具体的に書くと、以下の方程式を解いてa,b,cを求めている

a1+b0+c0=0

a1+b0+c1=0

a0+b0+c1=0

更に、上述の条件より(a,b,c)\ne(0,0,0)

これよりa=0,b=1,c=0

今、生成行列Gを

m(100) =m(010) =m(001) = 1

m(111) = 2

m(110) =m(011) =m(101) = 0

で定義する

ここに恣意はある #??

定理19.3とか？(和がn=5になる)

各lineの重複度を

m([010]) =m(100) +m(101) +m(001) = 1 + 0 + 1 = 2のようにカウントしていくと、

最終的に(a_0, a_2, a_3) = (1,3,3)を得る

例えばa_2=3は、重複度2のlineが3本あるという意味

以下の定理19.4よりGが生成する[5,3,d]_2符号Cの重み分布は

(A_5,A_3,A_2,A_0)=(1,3,3,1)となり

具体的に書くと

A_{n-0}=A_5=(q-1)1

A_{n-2}=A_3=(q-1)3

A_{n-3}=A_2=(q-1)3

A_{n-5}=A_0=(q-1)a_5=q-1 #??

であり、q=2,n=5なので。

d=2とわかる

なぜならば定理19.3

つまりd=n-3=5-3=2

\max\{m(l)|l: \mathrm{line} \;\mathrm{in} \;\mathrm{PG}(2,q)\}は(1,3,3)の中のmaxなので3

定理19.4

a_iから、符号の重み分布を調べる

A_{n-i}=(q-1)a_i　

補足

A_iは、Hamming重みがiである符号語の個数

a_i=|\{l:\mathrm{line}|m(l)=i\}|　

lineの重み分布みたいなやつ

例: (a_0, a_2, a_3) = (1,3,3)のとき

例えばa_2=3は、重複度2のlineが3本あるという意味

ファノ平面を使って生成行列を構成する

例: [11,3,6]_2符号\mathcal{C}の生成行列Gを構成する

定理19.3より、以下の2つが言える

ref PG(2, q)#600645571982700000018030

①7点の重複度の総和は11

②m(l)\le5

ファノ平面の図的に、点は3種類に分けられる

三角形の頂点(3つ)

三角形の辺の中点(3つ)

円の中心(1つ)

同じ者同士は対等であると考えられる

なので、①より11を7に分けるなら以下のパターンしか考えられない

3つの 2 、3つの 1 、1つの 2

これで総和は11=2*3+1*3+2*1

ここで問題になるのは、3つの 1 と 2 を頂点と辺のどちらにするかだが、②を使えば決まる

三角形の頂点(3つ)→2

三角形の辺の中点(3つ)→1

円の中心(1つ)→2

書き込むと

生成行列を構成する

各点を、重複度の個数分、並べればいい

∵重複度の定義

例えば点100の重複度は2なので、100を2個並べる

結果的に以下が得られる

G=\begin{pmatrix}1&1&0&0&0&0&1&1&0&1&1 \\ 0&0&1&1&0&0&1&0&1&1&1 \\ 0&0&0&0&1&1&0&1&1&1&1\end{pmatrix}

順番は関係ない。等価なものになる

まとめると

Gは、k\times nだが、

nはn=\sum_{P\in\mathrm{PG}(2,q)}m(P)から来てる

つまり、q^2+q+1個分の重複度がわかっていれば求まる

qは\mathrm{PG}(2,q)で与えられる

kは符号の形式[n,k,d]_qから与えられているはず

例題

PG(2,q)の全ての点を列として1つずつ並べてできる行列Gを生成行列とする[n,3,d]_q符号\mathcal{C}の長さnと最小距離dとA_dを求めよ

解答

以下の性質がわかっている

①Gはk\times n行列

∵生成行列の定義

②「PG(2,q)の全ての点を列として1つずつ並べてできる行列Gを生成行列とする」

∵問題文

③PG(2, q)の点の個数はq^2+q+1個

∵PG(2, q)の性質

④n=\sum_{P\in\mathrm{PG}(2,q)}m(P)

∵ 定理19.3

つまりq^2+q+1個の重複度の総和

これらより、PG(2,q)の各点の重複度は1であることがわかる

なぜなら、①②より、点の個数とGの列数(つまりn)が等しくなることがわかる

これと③より、n=q^2+q+1

これと④より、各点の重複度は1

以下の性質より、各lineの重複度が得られる

⑤上の議論

⑥各lineはq+1個の点を含む

∵PG(2, q)の性質

⑦lineの重複度m(l)=\sum_{P\in l}m(P)

∵ lineの重複度の定義

これらより、任意のlineの重複度はm(l)=q+1

よって、⑧a_{q+1}=q^2+q+1

よって最小距離dは

⑨d=n-\max\{m(l)|l: \mathrm{line} \;\mathrm{in} \;\mathrm{PG}(2,q)\}=n-(q+1)=(q^2+q+1)-(q+1)=q^2

∵ 定理19.3

また、d=n-(q+1)(∵ ⑨の途中式)と、⑧と、定理19.4より、

A_d=(q-1)a_{q+1}=(q-1)(q^2+q+1)=q^3-1