有限幾何とデザイン：射影平面・直交 Latin 方陣・Steiner 系を有限体と符号から作る

0. この記事の要点

「点と直線だけからなる世界」を、有限個の元しかない体の上で作ると、どの 2 点を通る直線もちょうど 1 本、どの 2 直線もちょうど 1 点で交わる、という均一な構造が現れます。この記事では、その構造の点や直線を数え、同じ「均一な交わり」が、36 人の士官を並べるパズル（Latin 方陣）や、誤り訂正符号の符号語の配置にも現れることを、証明つきで確かめます。読み終えると、これらの対象がなぜ有限体から作れるのか、どんな数え上げの条件で存在しない場合が分かるのかを説明できるようになります。

• $\mathbb{F}_q^n$ の $k$ 次元部分空間の個数は Gauss 二項係数 $\binom{n}{k}_q$ です。射影空間 $\mathrm{PG}(n, q)$ の点・直線・超平面の個数はここから出ます。$\mathrm{PG}(2, q)$ は、$q^2 + q + 1$ 個の点と同数の直線をもつ位数 $q$ の射影平面です。
• 公理的な射影平面には位数 $n$ が定まり、点も直線も $n^2 + n + 1$ 個、各直線上に $n + 1$ 点です。直線を 1 本除くとアフィン平面になり、逆に無限遠直線を足すと戻ります。
• $t$-$(v, k, \lambda)$ デザインは $s \le t$ に対して $s$-デザインでもあり、整除条件が存在の必要条件になります。$2$-デザインではブロックの数 $b$ が点の数 $v$ 以上です（Fisher の不等式）。
• 位数 $n$ の互いに直交する Latin 方陣は $n - 1$ 個以下で、$n - 1$ 個あることと位数 $n$ の射影平面があることは同値です。素数冪 $q$ では $L_a(x, y) = ax + y$ で $q - 1$ 個作れます。
• Hadamard 行列の位数は $1, 2$ か $4$ の倍数です。$q \equiv 3 \pmod 4$ の素数冪に対し、平方剰余から位数 $q + 1$ の Hadamard 行列が作れます（Paley）。
• 二元 Hamming 符号の重み $3$ の符号語の台は $\mathrm{PG}(r-1, 2)$ の直線で、Steiner 3 重系をなします。拡大 Golay 符号 $G_{24}$ の重み $8$ の符号語 $759$ 個の台は Steiner 系 $S(5, 8, 24)$ です（台とは、符号語で $0$ でない座標の集合のことです）。

この記事で使う事前知識

• 部分空間・基底・次元: ベクトル空間の中でそれ自身がベクトル空間になる部分集合が部分空間で、その大きさを測るのが次元です。→ 基底、次元
• 双対符号: 符号の全語と内積がすべて $0$ になる語の全体。射影空間の双対性（点と超平面の入れ替え）に使います。→ 双対符号
• Hamming 符号: 検査行列の列が $0$ でないベクトルの全体になっている符号。→ Hamming 符号
• 行列式: 正方行列が正則かどうかを判定する量。Fisher の不等式の証明で使います。→ 行列式
• 二項係数: $n$ 個から $k$ 個を選ぶ選び方の数。二重数え上げで繰り返し使います。→ 二項係数
• 平方剰余: 整数 $a$ が、ある整数の 2 乗と $p$ を法として等しいこと。Paley の構成で使います。→ 平方剰余

1. 動機

符号理論で繰り返し現れたのは、「有限集合の部分集合の族で、互いの交わり方が均一なもの」でした。Hamming 符号の検査行列の列は $\mathbb{F}_q^r$ の 1 次元部分空間の全体で、最小重みの符号語は「一次従属な 3 列」、つまり一直線上に並ぶ 3 点に対応します。Golay 符号の最小重みの符号語は、どの 2 つも多くの座標を共有しないように配置されています。この「均一な交わり」を符号から切り離して研究するのが、有限幾何とデザインの理論です。

もとは別々の問題でした。Kirkman（1850）の「15 人の女生徒を 3 人ずつ並べて 7 日間散歩させ、どの 2 人もちょうど 1 回だけ同じ列になるようにせよ」という問題、Euler（1782）の「6 つの連隊の 6 つの階級の士官 36 人を、各行・各列に連隊も階級も重複なく並べられるか」という問題、Fisher（1930 年代）の農事試験の配置の問題です。これらは、点と直線、Latin 方陣、ブロックデザインという言葉で述べると、同じ対象の別の見方であることが分かります。そして、その存在を保証する道具が有限体であり、非存在を示す道具が数え上げと線形代数です。

この章では、数え上げ（とくに二重数え上げ）と $\mathbb{F}_q$ 上の線形代数の 2 つだけを使って、これらの対象の基本定理を証明し、最後に Hamming 符号と Golay 符号が具体的なデザインを与えることを確かめます。前の章との関係は次のとおりです。

この章の定理	使う前の章の定理
射影空間の双対性（定理 2.4）	第 3 章の $\dim C^{\perp} = n - k$、$(C^{\perp})^{\perp} = C$
Paley の構成（定理 6.4）	第 1 章の平方元の個数と Euler の規準
Hamming 符号と直線（定理 7.2）	第 3 章の Hamming 符号
$S(5, 8, 24)$ と $S(5, 6, 12)$（定理 7.3、系 7.4）	第 5 章の Golay 符号の最小距離と重み多項式

2. 有限体上のアフィン空間と射影空間

2.1. 部分空間の数え上げ

定義 2.1（アフィン空間 AG(n, q) と射影空間 PG(n, q)）↗

• アフィン空間 $\mathrm{AG}(n, q)$ とは、$\mathbb{F}_q^n$ を点の集合とし、部分空間 $U$ の平行移動 $a + U$（$a \in \mathbb{F}_q^n$）をアフィン部分空間とする幾何をいう。$\dim U = 1$ のものを直線、$\dim U = n - 1$ のものを超平面という。
• 射影空間 $\mathrm{PG}(n, q)$ とは、$\mathbb{F}_q^{n+1}$ の $1$ 次元部分空間を点、$2$ 次元部分空間を直線、$n$ 次元部分空間を超平面とし、包含関係を「点が直線の上にある」などの接続関係とする幾何をいう。一般に $\mathbb{F}_q^{n+1}$ の $k + 1$ 次元部分空間を $k$ 次元の射影部分空間という。

定義 2.2（Gauss 二項係数）↗

$0 \le k \le n$ に対し

$$\binom{n}{k}_q = \prod_{i=0}^{k-1}\frac{q^{\,n-i} - 1}{q^{\,k-i} - 1}$$

と定める（$k = 0$ のときは $1$）。

命題 2.3（部分空間の個数）✓

$\mathbb{F}_q^n$ の $k$ 次元部分空間の個数は $\binom{n}{k}_q$ である。

証明の方針は「同じものを 2 通りに数える」ことです。$k$ 個の一次独立なベクトルの組（順序つき）を、(a) 一つずつ選んでいく数え方と、(b) 先に張る部分空間を決めてからその基底として選ぶ数え方で数え、両者を比べて部分空間の個数を割り算で出します。たとえば $q = 2$、$n = 2$、$k = 1$ なら、$0$ でないベクトルは $3$ 個で、各 $1$ 次元部分空間には基底（$0$ でない元）が $1$ 個ずつなので、部分空間は $3$ 個です。

証明（命題 2.3）

$\mathbb{F}_q^n$ の一次独立なベクトルの順序つきの組 $(v_1, \ldots, v_k)$ の個数を 2 通りに数えます。

$v_1, \ldots, v_{i-1}$ が一次独立のとき、それらが張る空間は、係数の組と元が 1 対 1 に対応するので（命題 5.2［ベクトル空間と線形変換］）$q^{i-1}$ 個の元からなり、$v_i$ はその外から選びます。よって組の個数は

$$(q^n - 1)(q^n - q)\cdots(q^n - q^{k-1})$$

です。一方、組 $(v_1, \ldots, v_k)$ はそれが張る $k$ 次元部分空間 $U$ の順序つき基底で、同じ計算を $U$（元の個数 $q^k$）の中で行うと、1 つの $U$ の順序つき基底は $(q^k - 1)(q^k - q)\cdots(q^k - q^{k-1})$ 個です。$k$ 次元部分空間の個数を $N$ とすると

$$N = \prod_{i=0}^{k-1}\frac{q^n - q^i}{q^k - q^i} = \prod_{i=0}^{k-1}\frac{q^{n-i} - 1}{q^{k-i} - 1}$$

です（分母分子を $q^i$ で割った）。

∎

分母 $(q^k - 1)(q^k - q)\cdots(q^k - q^{k-1})$ は一般線形群 $\mathrm{GL}_k(\mathbb{F}_q)$ の位数です。上の証明は、$\mathrm{GL}_n(\mathbb{F}_q)$ が $k$ 次元部分空間の全体に推移的に作用することを使って、軌道と安定化群の関係（定理 2.4［群の作用と Sylow の定理］）から数えることもできます。また、各因子は $q \to 1$ で $(n - i)/(k - i)$ に近づくので、$\binom{n}{k}_q \to \binom{n}{k}$ です。Gauss 二項係数は「$n$ 元集合の $k$ 元部分集合」の $q$ 類似です。

2.2. 射影空間の点と直線

定理 2.4（PG(n, q) の点・直線・超平面）✓

$n \ge 2$ とする。$\mathrm{PG}(n, q)$ について次が成り立つ。

1. 点は $\dfrac{q^{n+1} - 1}{q - 1} = q^n + q^{n-1} + \cdots + 1$ 個、超平面も同数、直線は $\binom{n+1}{2}_q = \dfrac{(q^{n+1} - 1)(q^n - 1)}{(q^2 - 1)(q - 1)}$ 本ある。
2. 相異なる 2 点を通る直線はちょうど 1 本あり、各直線の上にはちょうど $q + 1$ 個の点がある。
3. 各点を通る直線は $\dfrac{q^n - 1}{q - 1}$ 本ある。
4. （双対性）$U \mapsto U^{\perp}$ は、$\mathbb{F}_q^{n+1}$ の $k$ 次元部分空間の全体から $n + 1 - k$ 次元部分空間の全体への全単射で、包含関係を逆転する。とくに点と超平面が入れ替わる。

証明（定理 2.4）

(1) 命題 2.3 を $\mathbb{F}_q^{n+1}$ と $k = 1, 2, n$ に使います。$\binom{n+1}{1}_q = (q^{n+1} - 1)/(q - 1)$ で、$k = n$ のときは積の因子が $i = 0, \ldots, n-1$ で $\frac{q^{n+1-i} - 1}{q^{n-i} - 1}$、順に約分して $\frac{q^{n+1} - 1}{q - 1}$ です。

(2) 相異なる点 $\langle u\rangle, \langle v\rangle$ について、$u, v$ は比例しないので一次独立で、両方を含む $2$ 次元部分空間は $\langle u, v\rangle$ だけです。直線 $L$（$2$ 次元部分空間）の上の点は $L$ の $1$ 次元部分空間で、命題 2.3 から $\binom{2}{1}_q = (q^2 - 1)/(q - 1) = q + 1$ 個です。

(3) 点 $P$ を固定します。$P$ 以外の点は $\frac{q^{n+1} - 1}{q - 1} - 1 = \frac{q(q^n - 1)}{q - 1}$ 個で、(2) により各点は $P$ を通るちょうど 1 本の直線の上にあり、$P$ を通る各直線は $P$ 以外に $q$ 個の点を含みます。よって $P$ を通る直線は $\frac{q^n - 1}{q - 1}$ 本です。

(4) $U^{\perp} = \{ x : x \cdot u = 0\ (u \in U) \}$ は、$U$ を符号とみたときの双対符号です。$\dim U^{\perp} = n + 1 - \dim U$、$(U^{\perp})^{\perp} = U$ なので（定理 3.5［線形符号］）、$U \mapsto U^{\perp}$ は次元 $k$ と $n + 1 - k$ の部分空間の間の全単射で、逆写像も同じ形です。$U \subseteq W$ なら定義から $W^{\perp} \subseteq U^{\perp}$ です。

∎

双対性により、射影空間についての定理は「点」と「超平面」、「含む」と「含まれる」を入れ替えても成り立ちます。たとえば (2) の双対は、$n = 2$ のとき「相異なる 2 直線はちょうど 1 点で交わり、各点をちょうど $q + 1$ 本の直線が通る」です。

3. 射影平面とアフィン平面

3.1. 公理と $\mathrm{PG}(2, q)$

定義 3.1（射影平面）↗

点の集合 $\mathcal{P}$ と、直線と呼ばれる $\mathcal{P}$ の部分集合の族 $\mathcal{L}$ の組が射影平面であるとは、次の 3 条件を満たすことをいう。

• (P1) 相異なる 2 点を含む直線がちょうど 1 本ある。
• (P2) 相異なる 2 直線はちょうど 1 点で交わる。
• (P3) どの 3 点も同一直線上にない 4 点がある。

(P3) は、すべての点が 1 本の直線上にあるような退化した例を除くための条件です。

定理 3.2（PG(2, q) は射影平面）✓

$\mathrm{PG}(2, q)$ は射影平面で、各直線の上に $q + 1$ 個の点がある。点も直線も $q^2 + q + 1$ 個である。

証明（定理 3.2）

(P1) と個数は 定理 2.4 の 1 と 2 です（$n = 2$ では直線が超平面）。(P2): 相異なる $2$ 次元部分空間 $U, W \subseteq \mathbb{F}_q^3$ について、$U + W$ は $U$ を真に含むので $3$ 次元で、和の次元公式（命題 5.8［ベクトル空間と線形変換］）から $\dim(U \cap W) = 2 + 2 - 3 = 1$ です。つまり 2 直線はちょうど 1 点を共有します。(P3): 標準基底 $e_1, e_2, e_3$ と $e_1 + e_2 + e_3$ のうち、どの 3 個も一次独立なので、対応する 4 点のどの 3 点も 1 つの $2$ 次元部分空間に入りません。

∎

例 3.3（Fano 平面 PG(2, 2)）

$q = 2$ のとき、点は $\mathbb{F}_2^3$ の $0$ でない 7 個のベクトル、直線は「和が $0$ になる 3 点」$\{a, b, a + b\}$ の 7 本です。各直線上に 3 点、各点を 3 本の直線が通ります。これを Fano 平面といいます。7 個の点を $[7, 4, 3]$ Hamming 符号の座標とみると、7 本の直線はちょうど重み $3$ の符号語の台です（定理 7.2）。

Fano 平面。7 個の点は F₂³ の 0 でないベクトル、7 本の直線は三角形の 3 辺、3 本の中線、内接円（110, 101, 011 を通る）である。どの直線上の 3 点も、ベクトルとしての和が 0 になる。

3.2. 射影平面の位数

公理だけから、$\mathrm{PG}(2, q)$ と同じ数え上げが出てきます。

定理 3.4（射影平面の位数）✓

射影平面 $(\mathcal{P}, \mathcal{L})$ に対し、整数 $n \ge 2$ があって次が成り立つ。この $n$ を射影平面の位数という。

1. 各直線の上にちょうど $n + 1$ 個の点がある。
2. 各点をちょうど $n + 1$ 本の直線が通る。
3. 点は $n^2 + n + 1$ 個、直線も $n^2 + n + 1$ 本ある。

証明の方針は、公理 (P1)〜(P3) だけを使って、点と直線の本数が「どの直線にも同じ数の点がある」形に揃うことを示すことです。まず、直線の外の点 $P$ を 1 つ固定すると、$P$ を通る直線と、その直線の点が 1 対 1 に対応します（第 1 段）。これで 2 つの直線の点の個数を比べられます。第 2 段は、その比較に使う「どちらの直線の上にもない点」の存在を示す背理法で、少し長いですが、4 点 $A, B, C, D$ から作った交点 $E$ が矛盾を生む、という 1 点だけを追えば十分です。

証明（定理 3.4）

(P3) の 4 点を $A, B, C, D$ とします。相異なる点 $X, Y$ を通る直線を $XY$ と書きます。

第 1 段: 点 $P$ が直線 $\ell$ の上にないとき、$\ell$ の点と $P$ を通る直線は 1 対 1 に対応する。 $\ell$ の点 $X$ に直線 $PX$ を対応させます。逆に $P$ を通る直線 $m$ は $\ell$ と異なるので、(P2) により $\ell$ とちょうど 1 点 $m \cap \ell$ で交わります。(P1) から、この 2 つの対応は互いに逆です。

第 2 段: どの 2 直線 $\ell, m$ に対しても、どちらの上にもない点がある。 すべての点が $\ell \cup m$ の上にあると仮定します。$A, B, C, D$ のどの 3 点も同一直線上にないので、$\ell$ の上に高々 2 点、$m$ の上に高々 2 点です。4 点すべてが $\ell \cup m$ の上にあるので、$\ell \ne m$ で、ちょうど 2 点ずつ乗っています。$A, B \in \ell$、$C, D \in m$ としてよく、4 点のどれも $\ell$ と $m$ の両方には乗っていません（たとえば $A \in m$ なら $A, C, D$ が $m$ の上に並びます）。$E = AC \cap BD$ とします（$AC \ne BD$ です。等しければ 4 点が同一直線上にあります）。$E \in \ell$ とすると、$AC \ne \ell$（$C \notin \ell$）なので $E = AC \cap \ell = A$ で、$A \in BD$ となり $A, B, D$ が同一直線上に並んで矛盾します。$E \in m$ としても、同様に $E = AC \cap m = C$、$C \in BD$ となって矛盾します。よって $E$ は $\ell \cup m$ の上になく、仮定に反します。

第 3 段: (1) の証明。 2 直線 $\ell, m$ に対し、第 2 段の点 $P$ を取ると、第 1 段から $\ell$ の点の個数も $m$ の点の個数も「$P$ を通る直線の本数」に等しく、互いに等しい。この共通の値を $n + 1$ とおきます。直線 $AB$ の上には $A$、$B$ と $AB \cap CD$ があり、この 3 点は相異なります（$AB \cap CD = A$ なら $A, C, D$ が同一直線上）。よって $n + 1 \ge 3$ です。

第 4 段: (2) の証明。 点 $P$ に対し、$P$ を通らない直線があります。実際、$AB$、$AC$、$CD$ のすべてが $P$ を通るなら、$P = AB \cap AC = A$ で、$A \in CD$ となって矛盾します。その直線を $\ell$ とすると、第 1 段から $P$ を通る直線は $\ell$ の点と同数の $n + 1$ 本です。

第 5 段: (3) の証明。 点 $P$ を固定します。$P$ 以外の点は、(P1) により $P$ を通るちょうど 1 本の直線の上にあり、$P$ を通る $n + 1$ 本の直線はそれぞれ $P$ 以外に $n$ 個の点を含みます。よって点は $1 + (n + 1)n = n^2 + n + 1$ 個です。点と直線の組 $(X, \ell)$ で $X \in \ell$ となるものを 2 通りに数えると、$(n^2 + n + 1)(n + 1) = |\mathcal{L}|(n + 1)$ なので、直線も $n^2 + n + 1$ 本です。

∎

$\mathrm{PG}(2, q)$ の位数は $q$ です。したがって、素数冪 $q$ ごとに位数 $q$ の射影平面があります。

3.3. アフィン平面

定義 3.5（アフィン平面）↗

点の集合 $\mathcal{P}$ と、直線と呼ばれる $\mathcal{P}$ の部分集合の族 $\mathcal{L}$ の組がアフィン平面であるとは、次を満たすことをいう。2 直線が等しいか交わらないとき平行という。

• (A1) 相異なる 2 点を含む直線がちょうど 1 本ある。
• (A2) 直線 $\ell$ とその上にない点 $P$ に対し、$P$ を通り $\ell$ と交わらない直線がちょうど 1 本ある。
• (A3) 同一直線上にない 3 点がある。

$\mathrm{AG}(2, q)$ はアフィン平面です（直線 $a + \langle u\rangle$ と平行な直線は $a' + \langle u\rangle$）。

命題 3.6（射影平面とアフィン平面の対応）✓

1. 位数 $n$ の射影平面から、1 本の直線 $\ell_{\infty}$ とその上の点をすべて取り除くと、アフィン平面が得られる。
2. 逆に、どのアフィン平面も、ある射影平面から (1) の操作で得られる。
3. したがって、アフィン平面には整数 $n \ge 2$（位数）が定まり、各直線の上に $n$ 個の点があり、点は $n^2$ 個、直線は $n^2 + n$ 本で、平行という関係による直線の同値類（平行類）は $n + 1$ 個、各平行類は $n$ 本の直線からなり、点の集合を分割する。

証明の全体像は次のとおりです。(1) は射影平面から直線 1 本を抜いてアフィン平面の公理を確かめるだけです。(2) は逆向きで、アフィン平面の「平行な直線の組（平行類）」ごとに無限遠の点を 1 つ足し、それらを並べた直線 $\ell_{\infty}$ を足すと射影平面に戻る、という構成です。ここで平行が同値関係であること（同じ平行類に分けられること）を最初に示し、そのあと射影平面の 3 公理を順に確かめます。(3) は (1) と (2) から数が出るだけです。

証明（命題 3.6）

(1) 残った点を「アフィン点」、$\ell_{\infty}$ 以外の直線からその $\ell_{\infty}$ 上の点（(P2) によりちょうど 1 個）を除いたものを「アフィン直線」と呼びます。(A1) は (P1) から従います。(A2): アフィン直線 $m$ とその上にないアフィン点 $P$ に対し、$P$ を通るアフィン直線が $m$ とアフィン点を共有しないことは、もとの射影平面で 2 直線の交点が $\ell_{\infty}$ の上にあること、すなわちその直線が点 $m \cap \ell_{\infty}$ を通ることと同値です。$P$ と $m \cap \ell_{\infty}$ を通る直線は (P1) によりちょうど 1 本です。(A3): アフィン点 $P$ を取ります（点は $n^2 + n + 1 > n + 1$ 個あります）。$P$ を通る直線は $n + 1 \ge 3$ 本あり、そのうち 2 本 $m_1, m_2$ の上に $P$ と異なるアフィン点 $X_1, X_2$ が取れます（各直線のアフィン点は $n \ge 2$ 個）。$P, X_1, X_2$ が同一直線上にあれば $m_1 = m_2$ となるので、この 3 点は同一直線上にありません。

(2) アフィン平面 $(\mathcal{P}, \mathcal{L})$ が与えられたとします。

平行は同値関係である。 反射律と対称律は定義から成り立ちます。$\ell$ と $m$、$m$ と $k$ が平行で、$\ell$ と $k$ が点 $P$ を共有するとします。$P \in m$ なら、$\ell$ と $m$ は点を共有するので等しく、同様に $m = k$ で、$\ell = k$ です。$P \notin m$ なら、$\ell$ と $k$ はともに $P$ を通り $m$ と交わらない直線なので、(A2) により $\ell = k$ です。よって $\ell$ と $k$ は平行です。

射影平面を作る。 平行類ごとに新しい点（無限遠点）を 1 つ用意し、直線 $\ell$ の平行類の無限遠点を $[\ell]$ と書きます。新しい点の集合を、もとの点と無限遠点の全体とし、新しい直線を、$\ell \cup \{[\ell]\}$（$\ell \in \mathcal{L}$）と、無限遠点全体の集合 $\ell_{\infty}$ とします。

(P1) を確かめます。もとの 2 点を通る新しい直線は、(A1) の直線を延ばしたもの 1 本だけです（$\ell_{\infty}$ はもとの点を含みません）。もとの点 $P$ と無限遠点 $[m]$ を通るのは、$P$ を通り $m$ と平行な直線（$P \in m$ なら $m$ 自身、そうでなければ (A2) の直線）を延ばしたものちょうど 1 本です。2 つの無限遠点を通るのは $\ell_{\infty}$ だけです（延ばした直線は無限遠点を 1 つしか含みません）。

(P2) を確かめます。延ばした 2 直線は、もとの直線が平行でなければもとの点を共有し（(A1) により 1 点だけ）、無限遠点は異なります。平行で異なるなら、もとの点は共有せず、無限遠点を共有します。延ばした直線と $\ell_{\infty}$ は、その直線の無限遠点 1 つだけを共有します。

(P3) を確かめます。(A3) の 3 点を $A, B, C$ とします。$C$ を通り $AB$ と平行な直線 $k$ と、$B$ を通り $AC$ と平行な直線 $k'$ を取ります。$k$ と $k'$ が平行なら、平行の推移律から $AB$ と $AC$ が平行になり、$A$ を共有するので等しく、(A3) に反します。よって $k$ と $k'$ は 1 点 $D$ で交わります。$D \notin AB$（$k$ は $AB$ と交わりません。$C \notin AB$ だからです）、同様に $D \notin AC$ です。$D \in BC$ とすると、$D \ne C$ なら $k$ は 2 点 $C, D$ を通るので $k = BC$ で、$B \in k$ が $k \cap AB = \varnothing$ に反します。$D = C$ なら $C \in k'$ が $k' \cap AC = \varnothing$ に反します。したがって $A, B, C, D$ のどの 3 点も同一直線上にありません。

こうして得られた射影平面から $\ell_{\infty}$ とその上の点を除くと、もとのアフィン平面に戻ります。

(3) (2) の射影平面の位数を $n$ とすると（定理 3.4）、各アフィン直線の点は $(n + 1) - 1 = n$ 個、点は $(n^2 + n + 1) - (n + 1) = n^2$ 個、直線は $(n^2 + n + 1) - 1$ 本です。平行類は $\ell_{\infty}$ の点と 1 対 1 に対応するので $n + 1$ 個です。1 つの平行類の直線は互いに交わらず、(A2) によりどの点もその類の直線にちょうど 1 本乗るので、点の集合を $n$ 点ずつに分割し、$n^2/n = n$ 本あります。

∎

例 3.7（PG(2, 3) の 13 点 13 直線と AG(2, 3)）

$q = 3$ では、$\mathrm{PG}(2, 3)$ は $13$ 個の点と $13$ 本の直線をもち、各直線上に $4$ 点、各点を $4$ 本の直線が通ります。点を $(x : y : z)$（$\mathbb{F}_3^3$ の $0$ でないベクトルを $\pm 1$ 倍で同一視）と書き、直線 $z = 0$ を無限遠直線とすると、残る $9$ 点 $(x : y : 1)$ が $\mathrm{AG}(2, 3)$ です。$\mathrm{AG}(2, 3)$ の $12$ 本の直線は $4$ つの平行類（傾き $0, 1, 2, \infty$）に $3$ 本ずつ分かれます。

これは Kirkman の問題の小さい版の解になっています。9 人を 3 人ずつ 3 列に並べて 4 日間散歩させ、どの 2 人もちょうど 1 回だけ同じ列になるようにできます（各日が 1 つの平行類）。もとの 15 人 7 日の問題にも解があり、$\mathrm{PG}(3, 2)$ の $35$ 本の直線を、$15$ 点を分割する $5$ 本ずつの組 $7$ つに分けることで得られます。

注意 3.8（射影平面の位数についての非存在定理）

知られている射影平面の位数はすべて素数冪です。非存在については次の 2 つが知られています。どちらもこの章の道具では証明できないので、定理としては立てません。

• Bruck–Ryser–Chowla の定理: $n \equiv 1, 2 \pmod 4$ で位数 $n$ の射影平面があれば、$n$ は 2 つの平方数の和である。したがって位数 $6$、$14$、$21$、$22$ の射影平面はない。証明は接続行列の関係式 $NN^{\mathsf{T}} = nI + J$ を有理数体上の二次形式の同値として読むもので、Lagrange の四平方和定理を使います（Bruck–Ryser 1949、参考文献 [3]）。
• 位数 $10$ の射影平面は存在しない（Lam–Thiel–Swiercz 1989、参考文献 [4]）。$10 = 1^2 + 3^2$ なので上の定理では排除できず、符号の重み分布による絞り込みと大規模な計算機探索で示されました。

位数 $12$ の射影平面があるかどうかは分かっていません。

4. デザイン

4.1. $t$-デザインと整除条件

定義 4.1（t-デザイン・Steiner 系）↗

$1 \le t \le k \le v$、$\lambda \ge 1$ を整数とする。$v$ 元集合 $X$（元を点という）と、$X$ の $k$ 元部分集合の族 $\mathcal{B}$（元をブロックという）の組が $t$-$(v, k, \lambda)$ デザインであるとは、$X$ のどの $t$ 元部分集合も、ちょうど $\lambda$ 個のブロックに含まれることをいう。

• $\lambda = 1$ のとき Steiner 系といい、$S(t, k, v)$ と書く。$S(2, 3, v)$ を Steiner 3 重系という。
• $t = 2$、$k < v$ のとき釣合い型不完備ブロック計画（BIBD）という。ブロックの個数を $b$、1 点を含むブロックの個数を $r$ と書く。
• $t = 2$ で $b = v$ のとき対称デザインという。

位数 $n$ の射影平面は、直線をブロックとして $S(2, n + 1, n^2 + n + 1)$ で、対称デザインです。位数 $n$ のアフィン平面は $S(2, n, n^2)$ です。

定理 4.2（t-デザインは s-デザインでもある）✓

$(X, \mathcal{B})$ を $t$-$(v, k, \lambda)$ デザインとし、$0 \le s \le t$ とする。$X$ のどの $s$ 元部分集合 $S$ についても、$S$ を含むブロックの個数は

$$\lambda_s = \lambda\,\binom{v - s}{t - s}\Big/\binom{k - s}{t - s}$$

である。とくに $\lambda_s$ はすべて整数でなければならず、$s \ge 1$ のとき $(X, \mathcal{B})$ は $s$-$(v, k, \lambda_s)$ デザインである。

証明（定理 4.2）

$s$ 元集合 $S$ を固定し、$S$ を含むブロックの個数を $N_S$ とします。$S \subseteq T \subseteq B$、$|T| = t$、$B \in \mathcal{B}$ を満たす組 $(T, B)$ を 2 通りに数えます。先に $T$ を選ぶと、$S$ を含む $t$ 元集合は $\binom{v - s}{t - s}$ 個で、それぞれを含むブロックは $\lambda$ 個です。先に $B$ を選ぶと、$S$ を含むブロックは $N_S$ 個で、それぞれの中で $S$ を含む $t$ 元集合は $\binom{k - s}{t - s}$ 個です。よって

$$\lambda\binom{v - s}{t - s} = N_S\binom{k - s}{t - s}$$

で、$N_S$ は $S$ によらず $\lambda_s$ に等しくなります。

∎

系 4.3（2-デザインの基本関係式）✓

$2$-$(v, k, \lambda)$ デザインのブロックの個数 $b$ と、1 点を含むブロックの個数 $r$ について

$$r(k - 1) = \lambda(v - 1), \qquad bk = vr$$

が成り立つ。

証明（系 4.3）

定理 4.2 で $t = 2$ とすると、$r = \lambda_1 = \lambda(v - 1)/(k - 1)$、$b = \lambda_0 = \lambda\binom{v}{2}/\binom{k}{2} = \lambda v(v-1)/(k(k-1))$ です。第 1 式は $r$ の式そのもの、第 2 式は $bk = \lambda v(v - 1)/(k - 1) = vr$ です。

∎

例 4.4（整除条件で存在しないことが分かる例）

$S(5, 8, 24)$ があれば、$\lambda_s = \binom{24 - s}{5 - s}/\binom{8 - s}{5 - s}$ は $s = 0, 1, \ldots, 5$ で $759, 253, 77, 21, 5, 1$ となり、すべて整数です（存在は 定理 7.3 で示します）。一方、たとえば $S(2, 3, 8)$ は $r = \lambda_1 = 7/2$ が整数でないので存在しません。整除条件は必要条件であって十分条件ではありません（演習 8.3）。

4.2. Fisher の不等式

$2$-$(v, k, \lambda)$ デザインの点を $x_1, \ldots, x_v$、ブロックを $B_1, \ldots, B_b$ とし、$v \times b$ 行列 $N$ を、$x_i \in B_j$ のとき $N_{ij} = 1$、そうでないとき $0$ で定めます。これを接続行列といいます。

補題 4.5（aI + bJ の行列式）✓

$K$ を体、$a, c \in K$、$J_v$ を全成分が $1$ の $v$ 次正方行列とすると、$\det(aI_v + cJ_v) = a^{v-1}(a + vc)$ である。

証明（補題 4.5）

$M = aI_v + cJ_v$ は対角成分が $a + c$、それ以外が $c$ です。第 $2, \ldots, v$ 行から第 $1$ 行を引くと、第 $i$ 行（$i \ge 2$）は第 $1$ 成分が $-a$、第 $i$ 成分が $a$、他は $0$ になります。次に第 $2, \ldots, v$ 列を第 $1$ 列に加えると、第 $1$ 行の第 $1$ 成分は $(a + c) + (v - 1)c = a + vc$、第 $i$ 行（$i \ge 2$）の第 $1$ 成分は $-a + a = 0$ になります。これらの操作で行列式は変わらず（命題 4.3［行列式とその性質］）、得られた行列は対角成分が $a + vc, a, \ldots, a$ の上三角行列なので、行列式はその積です（命題 3.3［行列式とその性質］）。

∎

定理 4.6（Fisher の不等式）✓

$2$-$(v, k, \lambda)$ デザインで $k < v$ ならば、$b \ge v$ である。

証明の方針は、点とブロックの接続を $0$ と $1$ の表（接続行列 $N$）にし、$N$ とその転置の積 $NN^{\mathsf{T}}$ の $(i, i')$ 成分が「点 $x_i$ と $x_{i'}$ を両方含むブロックの数」になることを使います。2-デザインの条件から、この数は対角では $r$、対角以外ではつねに $\lambda$ なので、$NN^{\mathsf{T}}$ は単純な形になり、行列式が $0$ でないことが分かります。行列式が $0$ でなければ、$N$ の列の数 $b$ が行の数 $v$ より小さいことはあり得ません。

証明（定理 4.6）

$NN^{\mathsf{T}}$ の $(i, i')$ 成分は、$x_i$ と $x_{i'}$ をともに含むブロックの個数です。$i = i'$ なら $r$、$i \ne i'$ なら $\lambda$ なので

$$NN^{\mathsf{T}} = (r - \lambda)I_v + \lambda J_v$$

です。補題 4.5 と 系 4.3 の $r + \lambda(v - 1) = r + r(k - 1) = rk$ から

$$\det(NN^{\mathsf{T}}) = (r - \lambda)^{v-1}\bigl(r - \lambda + v\lambda\bigr) = rk\,(r - \lambda)^{v-1}$$

です。$k < v$ と $r(k - 1) = \lambda(v - 1)$ から $r > \lambda$（$k \ge 2$ なので $k - 1 \ge 1$ で、$v - 1 > k - 1$）なので、$\det(NN^{\mathsf{T}}) \ne 0$ で、$NN^{\mathsf{T}}$ は $\mathbb{Q}$ 上の正則行列です（定理 7.1［行列式とその性質］）。

$b < v$ と仮定します。$NN^{\mathsf{T}}$ が定める線形写像 $\mathbb{Q}^v \to \mathbb{Q}^v$ の像は、$N$ が定める線形写像 $\mathbb{Q}^b \to \mathbb{Q}^v$ の像に含まれ、後者の次元は $b$ 以下です（定理 7.3［ベクトル空間と線形変換］）。すると $NN^{\mathsf{T}}$ は全射でなく、正則であることに反します。

∎

純粋に組合せ的な主張が、行列の階数の比較で証明されました。この「線形代数の方法」は極値組合せ論で広く使われます。

系 4.7（対称デザインのブロックの交わり）✓

対称な $2$-$(v, k, \lambda)$ デザイン（$b = v$、$k < v$）では、$r = k$ で、相異なる 2 つのブロックはちょうど $\lambda$ 個の点を共有する。

証明（系 4.7）

$bk = vr$ と $b = v$ から $r = k$ です。$N$ は $v$ 次正方行列で、$\det(N)^2 = \det(NN^{\mathsf{T}}) \ne 0$（定理 6.1［行列式とその性質］、命題 3.3［行列式とその性質］、定理 4.6 の証明）なので $N$ は正則です。各点は $r = k$ 個のブロックに含まれるので $NJ = kJ$、各ブロックは $k$ 点を含むので $JN = kJ$ です。$NJ = kJ$ の両辺に $N^{-1}$ を掛けると $N^{-1}J = k^{-1}J$ です。よって

$$N^{\mathsf{T}}N = N^{-1}(NN^{\mathsf{T}})N = N^{-1}\bigl((k - \lambda)I + \lambda J\bigr)N = (k - \lambda)I + \lambda N^{-1}(JN) = (k - \lambda)I + \lambda k\,N^{-1}J = (k - \lambda)I + \lambda J$$

です。$N^{\mathsf{T}}N$ の $(j, j')$ 成分は $|B_j \cap B_{j'}|$ なので、$j \ne j'$ のとき $|B_j \cap B_{j'}| = \lambda$ です。

∎

射影平面では $\lambda = 1$ で、これは公理 (P2) です。一般の対称デザインでも「点とブロックを入れ替えたもの」が再びデザインになる、というのがこの系の内容です。

定義 4.8（差集合）↗

位数 $v$ のアーベル群 $A$ の $k$ 元部分集合 $D$ が $(v, k, \lambda)$ 差集合であるとは、$A$ の $0$ でないどの元 $g$ も、$g = d - d'$（$d, d' \in D$）の形にちょうど $\lambda$ 通りに表されることをいう。

例 4.9（(7, 3, 1) と (11, 5, 2) の差集合）

$D$ が差集合のとき、平行移動 $D + g$（$g \in A$）をブロックとすると対称な $2$-$(v, k, \lambda)$ デザインが得られます。相異なる点 $x, y$ がともに $D + g$ に属するのは、$d = x - g$、$d' = y - g$ がともに $D$ に属するときで、$d - d' = x - y$ を満たす $(d, d')$ は $\lambda$ 組、それぞれが $g = x - d$ を 1 つ決めるからです。$k < v$ のとき、$v$ 個の平行移動は相異なります。$0$ でない差 $d - d'$（$d \ne d'$）は $k(k-1)$ 個で、$v - 1$ 個の元が $\lambda$ 回ずつ現れるので $\lambda(v - 1) = k(k - 1)$、したがって $\lambda < k$ です。もし $g \ne g'$ で $D + g = D + g'$ なら、各 $d \in D$ について $d + (g - g') \in D$ となり、$g - g'$ が差として $k$ 通りに表されて $\lambda < k$ に反します。

• $\mathbb{Z}/7\mathbb{Z}$ の $D = \{1, 2, 4\}$。差は $2 - 1 = 1$、$4 - 2 = 2$、$4 - 1 = 3$ とその符号を変えた $6, 5, 4$ で、$1, \ldots, 6$ がちょうど 1 回ずつ現れます。$(7, 3, 1)$ 差集合で、得られるデザインは Fano 平面です。
• $\mathbb{Z}/11\mathbb{Z}$ の $D = \{1, 3, 4, 5, 9\}$。$20$ 個の差を書き出すと、$1 = 4 - 3 = 5 - 4$、$2 = 3 - 1 = 5 - 3$、$3 = 4 - 1 = 1 - 9$、$4 = 5 - 1 = 9 - 5$、$5 = 9 - 4 = 3 - 9$ で、残りの $6, \ldots, 10$ はこれらの符号を変えたものなので、どの元もちょうど 2 回ずつ現れます。$(11, 5, 2)$ 差集合で、$2$-$(11, 5, 2)$ 対称デザインを与えます。

どちらの $D$ も、$7$、$11$ を法とする平方剰余の全体です。$q \equiv 3 \pmod 4$ の素数冪で $\mathbb{F}_q$ の $0$ でない平方元の全体が差集合になることは、定理 6.4 の計算（補題 6.3 の 4）と同じ内容です。

5. 直交 Latin 方陣

5.1. 定義と上界

定義 5.1（Latin 方陣・直交・MOLS）↗

$n$ 元集合 $\Sigma$ の元を成分とする $n$ 次正方行列 $L$ が位数 $n$ の Latin 方陣であるとは、各行と各列に $\Sigma$ のすべての元がちょうど 1 回ずつ現れることをいう。位数 $n$ の Latin 方陣 $L, L'$ が直交するとは、$n^2$ 個のセル $(i, j)$ に対する成分の対 $(L(i, j), L'(i, j))$ がすべて相異なること（したがって $\Sigma \times \Sigma'$ のすべての対がちょうど 1 回ずつ現れること）をいう。どの 2 つも直交する Latin 方陣の組を MOLS（mutually orthogonal Latin squares）といい、位数 $n$ の MOLS の最大個数を $N(n)$ と書く。

Euler の 36 士官問題は「位数 $6$ の直交する Latin 方陣の対はあるか」、すなわち $N(6) \ge 2$ かという問いです。

定理 5.2（MOLS の個数の上界）✓

$n \ge 2$ ならば $N(n) \le n - 1$ である。

証明（定理 5.2）

$L_1, \ldots, L_s$ を記号 $\{1, \ldots, n\}$ の位数 $n$ の MOLS とします。1 つの方陣の記号を全単射で付け替えても、Latin 方陣であることも他の方陣との直交性も保たれます。そこで各 $L_m$ の記号を付け替えて、第 $1$ 行を $1, 2, \ldots, n$ にします。

セル $(2, 1)$ の成分 $a_m = L_m(2, 1)$ を考えます。第 $1$ 列にはすでにセル $(1, 1)$ に $1$ があるので $a_m \ne 1$ です。$m \ne m'$ で $a_m = a_{m'} = a$ とすると、対 $(L_m, L_{m'})$ はセル $(2, 1)$ とセル $(1, a)$ の両方で $(a, a)$ となり、直交性に反します。よって $a_1, \ldots, a_s$ は $\{2, \ldots, n\}$ の相異なる元で、$s \le n - 1$ です。

∎

5.2. 射影平面との同値性

定理 5.3（MOLS の完全系と射影平面）✓

$n \ge 2$ について、次は同値である。

1. $N(n) = n - 1$、すなわち位数 $n$ の MOLS が $n - 1$ 個ある。
2. 位数 $n$ のアフィン平面がある。
3. 位数 $n$ の射影平面がある。

証明の方針は、アフィン平面の各平行類を 1 つの「方向」と見て、そのうち 2 方向（$\Pi_0$ と $\Pi_{\infty}$）を行と列の番号づけに使い、残りの方向を Latin 方陣の記号に使う、というものです。(2) $\Rightarrow$ (1) では、平面から方陣を作ります。(1) $\Rightarrow$ (2) では逆に、方陣のセルを点、行・列・同じ記号の位置を直線と見ます。

証明（定理 5.3）

(2) $\Leftrightarrow$ (3) は 命題 3.6 です。

(2) $\Rightarrow$ (1): 位数 $n$ のアフィン平面の $n + 1$ 個の平行類を $\Pi_0, \Pi_{\infty}, \Pi_1, \ldots, \Pi_{n-1}$ とし、各平行類の $n$ 本の直線に $1, \ldots, n$ の番号を付けます（命題 3.6 の 3）。異なる平行類の 2 直線は平行でないので交わり、(A1) により交点はちょうど 1 つです。各点 $X$ は、$\Pi_0$ の直線 1 本と $\Pi_{\infty}$ の直線 1 本に乗り、その番号の対 $(i, j)$ を $X$ の座標とすると、点とセル $(i, j)$ が 1 対 1 に対応します。$1 \le m \le n - 1$ に対し、$L_m(i, j)$ を「点 $(i, j)$ を通る $\Pi_m$ の直線の番号」と定めます。

• $L_m$ は Latin 方陣です。第 $i$ 行は $\Pi_0$ の $i$ 番の直線の上の点で、$\Pi_m$ の各直線はこの直線とちょうど 1 点で交わるので、各記号がちょうど 1 回現れます。列についても同様です。
• $m \ne m'$ なら $L_m$ と $L_{m'}$ は直交します。$\Pi_m$ の $a$ 番の直線と $\Pi_{m'}$ の $a'$ 番の直線はちょうど 1 点で交わるので、対 $(a, a')$ はちょうど 1 つのセルに現れます。

よって $n - 1$ 個の MOLS があり、定理 5.2 と合わせて $N(n) = n - 1$ です。

(1) $\Rightarrow$ (2): $L_1, \ldots, L_{n-1}$ を記号 $\{1, \ldots, n\}$ の MOLS とします。点を $n^2$ 個のセルとし、直線を次の $n + 1$ 種類（各 $n$ 本）とします。行 $\{(i, j) : j\}$（$\Pi_0$）、列 $\{(i, j) : i\}$（$\Pi_{\infty}$）、そして各 $m$ と記号 $a$ に対する $\{(i, j) : L_m(i, j) = a\}$（$\Pi_m$）。各直線は $n$ 点からなり、同じ種類の直線はセルの集合を分割します。異なる種類の 2 直線はちょうど 1 点で交わります（行と列は明らか。行または列と $\Pi_m$ の直線は Latin 方陣の性質、$\Pi_m$ と $\Pi_{m'}$ の直線は直交性）。

(A1): 点 $P$ を通る直線は各種類にちょうど 1 本、計 $n + 1$ 本で、どの 2 本も $P$ だけを共有します。これらは $P$ 以外に $(n + 1)(n - 1) = n^2 - 1$ 個の相異なる点を含むので、$P$ 以外のすべての点がちょうど 1 本に乗ります。(A2): 直線 $\ell$ とその上にない $P$ について、$P$ を通る直線のうち $\ell$ と異なる種類のものは $\ell$ と交わり、同じ種類のもの（1 本）は $\ell$ と交わりません。(A3): セル $(1, 1), (1, 2), (2, 1)$ のうち前の 2 つを通る直線は第 $1$ 行だけで、$(2, 1)$ を含みません。こうしてアフィン平面が得られ、各直線は $n$ 点なので位数は $n$ です。

∎

定理 5.4（素数冪の位数の MOLS）✓

$q$ を素数冪とすると $N(q) = q - 1$ である。具体的には、行と列を $\mathbb{F}_q$ の元で番号づけ、$a \in \mathbb{F}_q^{\times}$ に対して

$$L_a(x, y) = ax + y \qquad (x, y \in \mathbb{F}_q)$$

とおくと、$\{ L_a : a \in \mathbb{F}_q^{\times} \}$ は $q - 1$ 個の MOLS である。

証明（定理 5.4）

$L_a$ が Latin 方陣であること: $x$ を固定すると $y \mapsto ax + y$ は $\mathbb{F}_q$ の全単射、$y$ を固定すると $a \ne 0$ なので $x \mapsto ax + y$ も全単射です。直交性: $a \ne b$ とし、$(s, t) \in \mathbb{F}_q^2$ を任意に取ります。連立方程式 $ax + y = s$、$bx + y = t$ は、辺々引いて $(a - b)x = s - t$ から $x = (s - t)/(a - b)$、$y = s - ax$ とただ 1 つの解をもちます。よって対 $(s, t)$ はちょうど 1 つのセルに現れます。$q - 1$ 個の MOLS ができたので $N(q) \ge q - 1$ で、定理 5.2 から等号です。

∎

$L_a$ の記号 $c$ の位置 $\{ (x, y) : ax + y = c \}$ は $\mathrm{AG}(2, q)$ の傾き $-a$ の直線です。定理 5.3 の対応で、この MOLS は $\mathrm{AG}(2, q)$ と $\mathrm{PG}(2, q)$ に対応します。

例 5.5（F₄ から作る位数 4 の MOLS 3 個）

$\mathbb{F}_4 = \{0, 1, \omega, \omega^2\}$（$\omega^2 = \omega + 1$）の元を順に $0, 1, 2, 3$ と書きます。加法は $1 + 2 = 3$、$1 + 3 = 2$、$2 + 3 = 1$、$a + a = 0$ で、$\omega$ 倍は $0, 1, 2, 3 \mapsto 0, 2, 3, 1$、$\omega^2$ 倍は $0, 1, 2, 3 \mapsto 0, 3, 1, 2$ です。行を $x$、列を $y$ として

$$L_1 = \begin{pmatrix} 0&1&2&3\\ 1&0&3&2\\ 2&3&0&1\\ 3&2&1&0 \end{pmatrix},\qquad L_{\omega} = \begin{pmatrix} 0&1&2&3\\ 2&3&0&1\\ 3&2&1&0\\ 1&0&3&2 \end{pmatrix},\qquad L_{\omega^2} = \begin{pmatrix} 0&1&2&3\\ 3&2&1&0\\ 1&0&3&2\\ 2&3&0&1 \end{pmatrix}$$

です。3 つとも $L_1$ の行を並べ替えたものになっています。$L_1$ と $L_{\omega}$ を重ねると、第 2 行は $(1,2), (0,3), (3,0), (2,1)$、第 3 行は $(2,3), (3,2), (0,1), (1,0)$ となり、$16$ 個の対がすべて異なることが確かめられます。なお、$\mathbb{Z}/4\mathbb{Z}$ の加法表（巡回 Latin 方陣）には直交する相手がありません。体の構造を使うことが本質的です。

5.3. 積の構成と符号との対応

命題 5.6（MacNeish の積の構成）✓

$m, n \ge 2$ に対し $N(mn) \ge \min(N(m), N(n))$ である。したがって $n = p_1^{e_1}\cdots p_l^{e_l}$（素因数分解）ならば $N(n) \ge \min_i\,(p_i^{e_i} - 1)$ である。

証明（命題 5.6）

位数 $m$ の Latin 方陣 $A$（記号集合 $\Sigma$）と位数 $n$ の Latin 方陣 $B$（記号集合 $\Sigma'$）に対し、行と列を対 $(i, i')$、$(j, j')$ で番号づけた位数 $mn$ の方陣

$$(A \otimes B)\bigl((i, i'), (j, j')\bigr) = \bigl(A(i, j),\ B(i', j')\bigr) \in \Sigma \times \Sigma'$$

を作ります。行 $(i, i')$ を固定すると、$j \mapsto A(i, j)$ と $j' \mapsto B(i', j')$ がそれぞれ全単射なので、$(j, j') \mapsto (A(i, j), B(i', j'))$ も全単射です。列についても同様で、$A \otimes B$ は Latin 方陣です。

$A_1, A_2$ が直交し、$B_1, B_2$ が直交するとします。$A_1 \otimes B_1$ と $A_2 \otimes B_2$ を重ねたとき、対 $\bigl((a_1, b_1), (a_2, b_2)\bigr)$ が現れるセルは、$(A_1(i, j), A_2(i, j)) = (a_1, a_2)$ かつ $(B_1(i', j'), B_2(i', j')) = (b_1, b_2)$ を満たすもので、直交性からそれぞれ $(i, j)$ と $(i', j')$ がただ 1 つ定まります。よって $A_1 \otimes B_1$ と $A_2 \otimes B_2$ は直交します。$s = \min(N(m), N(n))$ とし、MOLS $A_1, \ldots, A_s$ と $B_1, \ldots, B_s$ を取れば、$A_1 \otimes B_1, \ldots, A_s \otimes B_s$ は位数 $mn$ の MOLS です。

後半は、前半を繰り返し使い、定理 5.4 の $N(p_i^{e_i}) = p_i^{e_i} - 1$ を代入したものです。

∎

$n \not\equiv 2 \pmod 4$ なら、$n$ の素数冪の因子はどれも $3$ 以上なので $N(n) \ge 2$ です。Euler が解けなかった $n = 6$ は、この構成が何も与えない最初の場合（$\min(2 - 1, 3 - 1) = 1$）です。

命題 5.7（MOLS と最小距離 s + 1 の符号）✓

$n \ge 2$、$s \ge 1$ とする。位数 $n$ の MOLS が $s$ 個あることと、$n$ 元集合 $\Sigma$ の上の長さ $s + 2$ の符号 $C \subseteq \Sigma^{s+2}$ で、$|C| = n^2$、最小距離 $s + 1$ のものがあることは同値である。

証明（命題 5.7）

長さ $s + 2$ の符号で「最小距離が $s + 1$ 以上」とは、相異なる 2 語が高々 1 個の座標でしか一致しないこと、言い換えると、どの 2 個の座標への射影 $C \to \Sigma^2$ も単射であることです。$|C| = n^2 = |\Sigma^2|$ のときは、これらの射影がすべて全単射であることと同値です。このとき、ある座標で一致する相異なる 2 語があるので、最小距離はちょうど $s + 1$ です。

MOLS $L_1, \ldots, L_s$（行・列・記号を $\Sigma$ で番号づける）から符号を作ります。

$$C = \bigl\{\, (i,\ j,\ L_1(i, j),\ \ldots,\ L_s(i, j)) : i, j \in \Sigma \,\bigr\}$$

とおくと $|C| = n^2$ です。座標 $(1, 2)$ への射影は明らかに全単射です。座標 $(1, m + 2)$ への射影が全単射であることは「$L_m$ の各行に各記号がちょうど 1 回現れる」こと、座標 $(2, m + 2)$ については列の同じ性質、座標 $(m + 2, m' + 2)$ については $L_m$ と $L_{m'}$ の直交性です。

逆に、そのような符号 $C$ があれば、座標 $(1, 2)$ への射影が全単射なので、各 $(i, j)$ に対し $(i, j)$ で始まる語がちょうど 1 つあり、その第 $m + 2$ 座標を $L_m(i, j)$ と定めます。上の言い換えを逆にたどると、$L_1, \ldots, L_s$ は MOLS です。

∎

Singleton 限界は、長さ $N$、最小距離 $d$ の $q$ 元符号の語数が $q^{N - d + 1}$ 以下であることを述べます。上の符号は $N = s + 2$、$d = s + 1$、語数 $n^2 = n^{N - d + 1}$ で等号を達成する、次元 $2$ にあたる MDS 符号です。$n = q$ が素数冪のとき、$k = 2$ の Reed–Solomon 符号 $\{ (f(a))_{a \in \mathbb{F}_q} : \deg f < 2 \}$ は $[q, 2, q - 1]_q$ 符号で（定理 5.2［巡回符号・BCH 符号・Reed–Solomon 符号］）、多項式の変数を $T$ として $f(T) = y + xT$ と書けば、座標 $a \ne 0$ の成分 $f(a) = ax + y$ が $L_a(x, y)$ です（座標 $0$ の成分は $y$）。定理 5.4 の MOLS は Reed–Solomon 符号を方陣の形に並べ直したものにほかなりません。

注意 5.8（36 士官問題と Euler の予想）

$N(6) = 1$、つまり位数 $6$ の直交する Latin 方陣の対は存在しません（Tarry 1900。場合分けによる全数調査）。Euler は $n \equiv 2 \pmod 4$ のすべてで $N(n) = 1$ と予想しましたが、Bose・Shrikhande・Parker（1960、参考文献 [5]）は $n \ne 2, 6$ のすべての $n$ で $N(n) \ge 2$ であることを示し、予想は $n = 6$ を除いて誤りでした。これらは証明が長いので、ここでは紹介にとどめます。

6. Hadamard 行列

定義 6.1（Hadamard 行列）↗

成分がすべて $\pm 1$ の $n$ 次正方行列 $H$ が $HH^{\mathsf{T}} = nI_n$ を満たすとき、位数 $n$ の Hadamard 行列という。すなわち、相異なる 2 行が $\mathbb{R}^n$ の通常の内積で直交する $\pm 1$ 行列である。

列や行を $-1$ 倍しても、並べ替えても、Hadamard 行列のままです（行どうしの内積は列の $-1$ 倍で変わりません）。$\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ は位数 $2$ の Hadamard 行列です。

命題 6.2（Hadamard 行列の位数）✓

位数 $n$ の Hadamard 行列があれば、$n = 1$、$n = 2$、または $n$ は $4$ の倍数である。

証明（命題 6.2）

$n \ge 3$ とします。第 $1$ 行の成分が $-1$ である列を $-1$ 倍して、第 $1$ 行をすべて $+1$ にします。第 $2$ 行と第 $3$ 行の成分の対が $(+, +)$、$(+, -)$、$(-, +)$、$(-, -)$ である列の個数をそれぞれ $a, b, c, d$ とします。第 $1$ 行と第 $2$ 行、第 $1$ 行と第 $3$ 行、第 $2$ 行と第 $3$ 行の直交性はそれぞれ

$$a + b = c + d, \qquad a + c = b + d, \qquad a + d = b + c$$

です。第 1 式から第 2 式を引くと $b - c = c - b$ で $b = c$、すると第 1 式から $a = d$、第 3 式から $2a = 2b$ で $a = b$ です。よって $a = b = c = d$ で、$n = a + b + c + d = 4a$ です。

∎

逆に、$4$ の倍数のすべての位数で Hadamard 行列が存在するかどうかは未解決です（Hadamard 予想）。次の定理は、無限個の位数で存在を保証します。

$q$ を奇数の素数冪とし、$\mathbb{F}_q$ の平方指標 $\chi : \mathbb{F}_q \to \{0, 1, -1\}$ を、$\chi(0) = 0$、$a$ が $0$ でない平方元なら $\chi(a) = 1$、平方元でなければ $\chi(a) = -1$ と定めます。$q$ が素数 $p$ のときは Legendre 記号（定義 3.2［原始根と平方剰余の相互法則］）です。

補題 6.3（平方指標の性質）✓

$q$ を奇数の素数冪、$\chi$ を $\mathbb{F}_q$ の平方指標とする。

1. $\chi(ab) = \chi(a)\chi(b)$（$a, b \in \mathbb{F}_q$）。
2. $\sum_{x \in \mathbb{F}_q}\chi(x) = 0$。
3. $q \equiv 3 \pmod 4$ ならば $\chi(-1) = -1$。
4. $c \in \mathbb{F}_q^{\times}$ に対し $\sum_{x \in \mathbb{F}_q}\chi(x)\chi(x + c) = -1$。

証明（補題 6.3）

(1) $a$ または $b$ が $0$ なら両辺とも $0$ です。$a, b \ne 0$ のとき、$\chi(a)$ は $\mathbb{F}_q$ の元 $a^{(q-1)/2} \in \{1, -1\}$ と同じ符号です（命題 6.2［有限体の構造］ の 1。$q$ が奇数なので $\mathbb{F}_q$ で $1 \ne -1$）。$(ab)^{(q-1)/2} = a^{(q-1)/2}b^{(q-1)/2}$ から主張が従います。

(2) $\mathbb{F}_q^{\times}$ の平方元は $(q - 1)/2$ 個、平方元でないものも $(q - 1)/2$ 個です（命題 6.1［有限体の構造］ の 2）。

(3) $-1$ が平方元であることは $q \equiv 1 \pmod 4$ と同値です（命題 6.2［有限体の構造］ の 2）。

(4) $x = 0$ の項は $0$ です。$x \ne 0$ のとき、$x + c = x(1 + cx^{-1})$ と (1)、$\chi(x)^2 = 1$ から

$$\chi(x)\chi(x + c) = \chi(x)^2\chi(1 + cx^{-1}) = \chi(1 + cx^{-1})$$

です。$x$ が $\mathbb{F}_q^{\times}$ を動くとき $cx^{-1}$ も $\mathbb{F}_q^{\times}$ を動き、$y = 1 + cx^{-1}$ は $1$ 以外のすべての元を 1 回ずつ取ります。よって和は $\sum_{y \ne 1}\chi(y) = 0 - \chi(1) = -1$ です（(2) を使った）。

∎

定理 6.4（Paley の構成）✓

$q \equiv 3 \pmod 4$ を素数冪とすると、位数 $q + 1$ の Hadamard 行列がある。

証明の方針は、$\mathbb{F}_q$ の元の組 $(a, b)$ に $\chi(b - a)$ を成分とする $q$ 次の行列 $Q$ を作り、その縁に $1$ の行と列を足して $\pm 1$ 行列 $H$ にすることです。$QQ^{\mathsf{T}}$ の計算が鍵で、そこで補題の 4（$\chi(x)\chi(x + c)$ の和が $-1$）が使われます。この $-1$ が対角以外の成分に出て、足した行と列の分とちょうど打ち消し合い、$HH^{\mathsf{T}}$ が単位行列の定数倍になります。

証明（定理 6.4）

行と列を $\mathbb{F}_q$ の元で番号づけた $q$ 次正方行列 $Q = (\chi(b - a))_{a, b \in \mathbb{F}_q}$ を考えます。補題 6.3 から次が分かります。

• $Q^{\mathsf{T}} = -Q$。$\chi(a - b) = \chi(-1)\chi(b - a) = -\chi(b - a)$ だからです（補題の 1 と 3）。
• $Q\boldsymbol{1} = 0$（$\boldsymbol{1}$ は全成分が $1$ の列ベクトル）。第 $a$ 成分は $\sum_b\chi(b - a) = \sum_x\chi(x) = 0$ です（補題の 2）。
• $QQ^{\mathsf{T}} = qI - J$。$(a, a')$ 成分は $\sum_b\chi(b - a)\chi(b - a')$ で、$x = b - a$ とおくと $\sum_x\chi(x)\chi(x + (a - a'))$ です。$a = a'$ なら $\sum_x\chi(x)^2 = q - 1$、$a \ne a'$ なら $-1$ です（補題の 4）。

$q + 1$ 次正方行列

$$S = \begin{pmatrix} 0 & \boldsymbol{1}^{\mathsf{T}} \\ -\boldsymbol{1} & Q \end{pmatrix}, \qquad H = I_{q+1} + S$$

を作ります。$S^{\mathsf{T}} = -S$ で、

$$SS^{\mathsf{T}} = \begin{pmatrix} 0 & \boldsymbol{1}^{\mathsf{T}} \\ -\boldsymbol{1} & Q \end{pmatrix}\begin{pmatrix} 0 & -\boldsymbol{1}^{\mathsf{T}} \\ \boldsymbol{1} & Q^{\mathsf{T}} \end{pmatrix} = \begin{pmatrix} \boldsymbol{1}^{\mathsf{T}}\boldsymbol{1} & (Q\boldsymbol{1})^{\mathsf{T}} \\ Q\boldsymbol{1} & J + QQ^{\mathsf{T}} \end{pmatrix} = \begin{pmatrix} q & 0 \\ 0 & qI_q \end{pmatrix} = qI_{q+1}$$

です。よって

$$HH^{\mathsf{T}} = (I + S)(I + S^{\mathsf{T}}) = I + S + S^{\mathsf{T}} + SS^{\mathsf{T}} = (q + 1)I_{q+1}$$

です。$S$ の対角成分は $0$（$\chi(0) = 0$）、それ以外の成分は $\pm 1$ なので、$H = I + S$ の成分はすべて $\pm 1$ です。

∎

例 6.5（位数 12 の Hadamard 行列）

$q = 11$ とします。$11$ を法とする平方剰余は $\{1, 3, 4, 5, 9\}$ なので、$\chi(0), \chi(1), \ldots, \chi(10)$ は

$$0,\ +,\ -,\ +,\ +,\ +,\ -,\ -,\ -,\ +,\ -$$

です。$Q$ はこれを第 $0$ 行とし、右に 1 つずつ巡回的にずらした行を並べた巡回行列で、定理 6.4 の $H = I + S$ は位数 $12$ の Hadamard 行列です。$12$ は $2$ の冪ではないので、$\begin{pmatrix}H&H\\H&-H\end{pmatrix}$ を繰り返す構成（Sylvester の構成。位数は $2^m$）では得られない最初の位数です。$q = 3, 7, 11, 19, 23, 27, \ldots$ から位数 $4, 8, 12, 20, 24, 28, \ldots$ が得られます。

系 6.6（Hadamard 符号は Plotkin 限界の等号を達成する）✓

位数 $n \ge 4$ の Hadamard 行列があれば、長さ $n - 1$、語数 $n$、最小距離 $n/2$ の二元符号がある。この符号は、長さ $N$、最小距離 $d$（$2d > N$）の二元符号の語数 $M$ についての Plotkin 限界 $M \le 2d/(2d - N)$ の等号を達成する。

証明（系 6.6）

$H$ を位数 $n$ の Hadamard 行列とします。第 $1$ 成分が $-1$ である行を $-1$ 倍して、第 $1$ 列をすべて $+1$ にします。行を $-1$ 倍しても、他の行との内積は符号が変わるだけで $0$ のままなので、Hadamard 行列のままです。相異なる 2 行は直交するので、成分が一致する列と一致しない列が $n/2$ 個ずつあります。第 $1$ 列では一致しているので、第 $1$ 列を除いた長さ $n - 1$ の行どうしは、ちょうど $n/2$ 個の座標で異なります。$+1$ を $0$、$-1$ を $1$ に置き換えると、$n$ 語からなる長さ $N = n - 1$、最小距離 $d = n/2$ の二元符号が得られます。

$2d - N = n - (n - 1) = 1 > 0$ で、Plotkin 限界（定理 5.6［線形符号］）の右辺は $2d/(2d - N) = n$ です。語数 $M = n$ はこれに一致します。

∎

7. 符号とデザイン

7.1. 幾何から作る符号

符号 $C$ の語 $c$ の台を $\operatorname{supp}(c) = \{ i : c_i \ne 0 \}$ と書きます。符号の最小重みの語の台を集めたものがデザインになるとき、それを符号の台デザインといいます。

命題 7.1（単体符号・1 次 Reed–Muller 符号と幾何）✓

1. $r \ge 2$、$n = (q^r - 1)/(q - 1)$ とし、$\mathrm{PG}(r - 1, q)$ の各点の代表ベクトル $p_1, \ldots, p_n \in \mathbb{F}_q^r$ を列に並べた行列を生成行列とする符号（単体符号）を考える。その符号語は $c_u = (u \cdot p_1, \ldots, u \cdot p_n)$（$u \in \mathbb{F}_q^r$）で、$u \ne 0$ のとき $c_u$ が $0$ になる座標は超平面 $u^{\perp}$ の上の点に対応し、$\operatorname{wt}(c_u) = q^{r-1}$ である。すなわち、$0$ でない符号語の台は超平面の補集合である。
2. $m \ge 1$ とし、座標を $\mathrm{AG}(m, 2) = \mathbb{F}_2^m$ の点で番号づけた二元符号 $\mathrm{RM}(1, m) = \{\, (u \cdot x + \beta)_{x \in \mathbb{F}_2^m} : u \in \mathbb{F}_2^m,\ \beta \in \mathbb{F}_2 \,\}$ （1 次 Reed–Muller 符号）は $[2^m, m + 1, 2^{m-1}]_2$ 符号で、重み $2^{m-1}$ の符号語の台の全体は、$\mathrm{AG}(m, 2)$ のアフィン超平面の全体と一致する。

証明（命題 7.1）

(1) 生成行列の第 $i$ 行は $(p_{1, i}, \ldots, p_{n, i})$ なので、$u$ を係数とする行の一次結合の第 $j$ 成分は $\sum_iu_ip_{j, i} = u \cdot p_j$ です。$u \ne 0$ のとき、$u \cdot p_j = 0$ は点 $\langle p_j\rangle$ が $r - 1$ 次元部分空間 $u^{\perp}$ に含まれることと同値で、そのような点は $u^{\perp}$ の $1$ 次元部分空間の個数 $(q^{r-1} - 1)/(q - 1)$ だけあります（命題 2.3）。よって

$$\operatorname{wt}(c_u) = \frac{q^r - 1}{q - 1} - \frac{q^{r-1} - 1}{q - 1} = q^{r-1}$$

です。

(2) $(u, \beta) \mapsto (u \cdot x + \beta)_x$ は線形で、像が $0$ なら $x = 0$ で $\beta = 0$、$x = e_i$ で $u_i = 0$ なので単射です。よって次元は $m + 1$ です。$u = 0$ の語は全 $0$ か全 $1$ です。$u \ne 0$ のとき、$x \mapsto u \cdot x$ は $\mathbb{F}_2^m$ から $\mathbb{F}_2$ への全射な線形写像で、次元定理（定理 7.3［ベクトル空間と線形変換］）から核は $m - 1$ 次元、各値の逆像は $2^{m-1}$ 点です。語 $(u \cdot x + \beta)_x$ の台は $\{ x : u \cdot x = \beta + 1 \}$ で、これは $m - 1$ 次元部分空間 $u^{\perp}$ の平行移動、つまりアフィン超平面で、重みは $2^{m-1}$ です。$m \ge 2$ なら全 $1$ の語の重み $2^m$ はこれより大きく、$m = 1$ のときは符号が全空間で最小距離は $1 = 2^0$ なので、いずれも最小距離は $2^{m-1}$ です。逆に、アフィン超平面は $m - 1$ 次元部分空間 $U$ の平行移動で、$U^{\perp}$ は $1$ 次元で $(U^{\perp})^{\perp} = U$ なので（定理 3.5［線形符号］）、$U^{\perp}$ の $0$ でない元 $u$ について $U = u^{\perp}$ です。するとこのアフィン超平面は $\{ x : u \cdot x = \gamma \}$ の形なので、$\beta = \gamma + 1$ の語の台です。

∎

(1) は、第 3 章で示した「単体符号の $0$ でない符号語の重みはすべて $q^{r-1}$」の幾何的な意味です。どの 2 つの符号語も同じ距離だけ離れているのは、どの超平面も同じ数の点を含むからです。

7.2. Hamming 符号と Steiner 3 重系

定理 7.2（Hamming 符号の重み 3 の符号語）✓

$r \ge 2$、$n = 2^r - 1$ とし、二元 Hamming 符号 $C$ の座標を、検査行列の列である $\mathbb{F}_2^r$ の $0$ でないベクトル、すなわち $\mathrm{PG}(r - 1, 2)$ の点で番号づける。このとき、重み $3$ の符号語の台の全体は $\mathrm{PG}(r - 1, 2)$ の直線の全体と一致し、Steiner 3 重系 $S(2, 3, 2^r - 1)$ をなす。重み $3$ の符号語は $(2^r - 1)(2^{r-1} - 1)/3$ 個ある。

証明（定理 7.2）

検査行列の列は $\mathbb{F}_2^r$ の $0$ でないベクトルの全体で（定理 6.2［線形符号］）、語 $c$ が符号語であることは $\sum_{a \in \operatorname{supp}(c)}a = 0$ と同値です。台が 3 点 $\{a, b, c\}$ の語が符号語であることは $a + b + c = 0$、すなわち $c = a + b$ と同値です。これは $\{0, a, b, a + b\}$ が $2$ 次元部分空間であること、つまり $\{a, b, a + b\}$ が $\mathrm{PG}(r - 1, 2)$ の直線（$q + 1 = 3$ 点からなる）であることと同値です。

相異なる 2 点を通る直線はちょうど 1 本なので（定理 2.4 の 2）、直線の全体は $S(2, 3, 2^r - 1)$ です。直線の本数は $\binom{r}{2}_2 = (2^r - 1)(2^{r-1} - 1)/3$ です（命題 2.3）。

∎

$r = 3$ では、$[7, 4, 3]$ 符号の重み $3$ の語 $7$ 個が Fano 平面の $7$ 本の直線です（第 5 章 で求めた重み多項式 $x^7 + 7x^4y^3 + 7x^3y^4 + y^7$ と合います）。

7.3. Golay 符号と $S(5, 8, 24)$

定理 7.3（拡大 Golay 符号と Steiner 系 S(5, 8, 24)）✓

拡大 Golay 符号 $G_{24}$ の重み $8$ の符号語 $759$ 個の台をブロックとすると、$24$ 個の座標の上の Steiner 系 $S(5, 8, 24)$ が得られる。

証明（定理 7.3）

$G_{24}$ の最小距離は $8$（定理 5.7［重み多項式と MacWilliams 恒等式・Golay 符号］）、重み $8$ の符号語は $759$ 個です（系 5.8［重み多項式と MacWilliams 恒等式・Golay 符号］）。

5 点を共有する 2 つのブロックは無い。 重み $8$ の相異なる符号語 $c, c'$ の台が $5$ 点以上を共有するとします。二元符号なので $\operatorname{wt}(c + c') = 8 + 8 - 2|\operatorname{supp}(c) \cap \operatorname{supp}(c')| \le 6$ で、$c + c'$ は $0$ でない符号語なので最小距離 $8$ に反します。とくに、相異なる符号語の台は相異なり、ブロックは $759$ 個です。

数え上げ。 各ブロックは $\binom{8}{5} = 56$ 個の $5$ 元部分集合を含み、上で示したことから、異なるブロックが含む $5$ 元部分集合に重複はありません。よって、いずれかのブロックに含まれる $5$ 元部分集合は $759 \cdot 56 = 42504$ 個です。一方、$24$ 点の $5$ 元部分集合は全部で

$$\binom{24}{5} = \frac{24 \cdot 23 \cdot 22 \cdot 21 \cdot 20}{120} = 42504$$

個です。したがって、どの $5$ 元部分集合もちょうど 1 つのブロックに含まれます。

∎

$4$ 以下の $t$ で $t$-デザインの例はいくらでも作れますが、$t = 5$ の Steiner 系は長いあいだこの $S(5, 8, 24)$ と次の $S(5, 6, 12)$（Witt 1938）だけが知られていました。この 2 つの自己同型群が Mathieu 群 $M_{24}$ と $M_{12}$ です。

系 7.4（拡大三元 Golay 符号と Steiner 系 S(5, 6, 12)）✓

拡大三元 Golay 符号 $G_{12}$ の重み $6$ の符号語 $264$ 個の台は $132$ 個の相異なる $6$ 元集合で、これらをブロックとすると Steiner 系 $S(5, 6, 12)$ が得られる。

証明（系 7.4）

$G_{12}$ の最小距離は $6$（定理 5.11［重み多項式と MacWilliams 恒等式・Golay 符号］）、重み $6$ の符号語は $264$ 個です（系 5.12［重み多項式と MacWilliams 恒等式・Golay 符号］）。

重み $6$ の符号語 $c, c'$ の台 $T, T'$ が $5$ 点以上を共有するとします。共有する座標では $c_i, c'_i \in \{1, -1\}$ なので、$c_i = c'_i$ か $c_i = -c'_i$ です。共有する $5$ 個以上の座標のうち、少なくとも $3$ 個で同じほうが成り立ちます。$c_i = c'_i$ が $3$ 個以上で成り立つなら $c - c'$、$c_i = -c'_i$ が $3$ 個以上で成り立つなら $c + c'$ を考えると、この語は $T \cup T'$ の外で $0$、さらにその $3$ 個以上の座標でも $0$ なので、重みは $|T \cup T'| - 3 \le 7 - 3 = 4$ 以下です（$|T \cup T'| = 12 - |T \cap T'| \le 7$）。最小距離が $6$ なのでこの語は $0$ で、$c' = \pm c$ です。

したがって、台が $5$ 点以上を共有する重み $6$ の符号語は互いに $\pm 1$ 倍で、とくに台が等しいのは $c$ と $-c$ だけです。台は $264/2 = 132$ 個あり、相異なる 2 つの台が共有する点は $4$ 個以下です。各台は $\binom{6}{5} = 6$ 個の $5$ 元部分集合を含み、重複はないので、合計 $132 \cdot 6 = 792 = \binom{12}{5}$ 個です。よって、どの $5$ 元部分集合もちょうど 1 つのブロックに含まれます。

∎

例 7.5（S(5, 8, 24) から S(4, 7, 23) と S(3, 6, 22) を導く）

$t$-$(v, k, \lambda)$ デザインで 1 点 $x$ を固定し、$x$ を含むブロックから $x$ を除いたものを新しいブロックとすると、残りの $v - 1$ 点の上の $(t-1)$-$(v - 1, k - 1, \lambda)$ デザインになります。$x$ を含まない $t - 1$ 元集合 $T$ を含む新しいブロックは、$T \cup \{x\}$ を含むもとのブロックと 1 対 1 に対応するからです。

$S(5, 8, 24)$ にこれを使うと $S(4, 7, 23)$ が得られ、ブロックの個数は $\lambda_1 = 253$ です。これは $G_{23}$ の重み $7$ の符号語 $253$ 個の台です（固定した点をパリティ検査の座標に取った場合）。もう一度使うと $S(3, 6, 22)$（ブロックは $\lambda_2 = 77$ 個）が得られます。さらに続けると $S(2, 5, 21)$ で、ブロックは $\lambda_3 = 21$ 個、これは位数 $4$ の射影平面のパラメータです。

例 7.6（PG(2, q) の接続グラフは 4 サイクルを含まない）

$\mathrm{PG}(2, q)$ の点と直線を頂点とし、点 $P$ が直線 $\ell$ の上にあるとき $P$ と $\ell$ を辺で結んだ二部グラフを考えます。頂点は $2(q^2 + q + 1)$ 個、各頂点の次数は $q + 1$ で、辺は $(q + 1)(q^2 + q + 1)$ 本です。長さ $4$ の閉路があれば、相異なる 2 点がともに相異なる 2 直線の上にあることになり、(P1) に反します。よってこのグラフは $4$ サイクルを含みません。頂点数を $N$ とすると辺の数はおよそ $(N/2)^{3/2}$ で、「$4$ サイクルを含まない $N$ 頂点のグラフの辺の数は $N^{3/2}$ の定数倍以下」という極値グラフ理論の上界が、定数倍を除いて最良であることを示す構成になっています。

8. 演習

演習 8.1易

$\mathrm{PG}(3, 2)$ の点・直線・平面の個数、1 点を通る直線の本数、1 本の直線を含む平面の個数を求めよ。

解答

定理 2.4 で $n = 3$、$q = 2$ とします。点は $2^4 - 1 = 15$ 個、平面（超平面）も $15$ 個、直線は $\binom{4}{2}_2 = \frac{(2^4 - 1)(2^3 - 1)}{(2^2 - 1)(2 - 1)} = \frac{15 \cdot 7}{3} = 35$ 本です。1 点を通る直線は $(2^3 - 1)/(2 - 1) = 7$ 本です。直線 $L$ を含む平面は、双対性により $L^{\perp}$（$2$ 次元）に含まれる $1$ 次元部分空間と 1 対 1 に対応し、$2 + 1 = 3$ 個です。検算として、直線と平面の接続の組を数えると $35 \cdot 3 = 105 = 15 \cdot 7$（各平面は Fano 平面で $7$ 本の直線を含む）で合います。

演習 8.2標準

Steiner 3 重系 $S(2, 3, v)$ が存在すれば、$v \equiv 1$ または $3 \pmod 6$ であることを示せ。

解答

系 4.3 で $k = 3$、$\lambda = 1$ とすると、$r = (v - 1)/2$、$b = vr/3 = v(v - 1)/6$ がともに整数でなければなりません。$r$ が整数なので $v$ は奇数で、$v \equiv 1, 3, 5 \pmod 6$ です。$v \equiv 5 \pmod 6$ のとき $v(v - 1) \equiv 5 \cdot 4 = 20 \equiv 2 \pmod 6$ で $b$ が整数になりません。よって $v \equiv 1, 3 \pmod 6$ です。$v = 2^r - 1$ は、$r$ が偶数なら $3 \pmod 6$、奇数なら $1 \pmod 6$ で、定理 7.2 と合っています。

演習 8.3標準

$2$-$(16, 6, 1)$ デザインは、定理 4.2 の整除条件を満たすが存在しないことを示せ。

解答

$r = \lambda(v - 1)/(k - 1) = 15/5 = 3$、$b = vr/k = 16 \cdot 3/6 = 8$ はともに整数で、整除条件は満たされます。しかし $k = 6 < v = 16$ で $b = 8 < 16 = v$ なので、Fisher の不等式（定理 4.6）に反します。よって存在しません。直接にも分かります。1 点 $x$ を含むブロックは $3$ 個で、それぞれ $x$ 以外に $5$ 点を含み、$\lambda = 1$ からこれらは重複しないので、$x$ 以外の $15$ 点をちょうど覆います。$x$ を含まないブロック $B$ は、$x$ を含む $3$ 個のブロックとそれぞれ高々 $1$ 点しか共有できないので、$|B| \le 3$ となり $k = 6$ に反します。ところが $b = 8 > 3$ なので、$x$ を含まないブロックが必要です。

演習 8.4標準

$n \ge 3$ を奇数とする。$\mathbb{Z}/n\mathbb{Z}$ の上で $L_1(x, y) = x + y$、$L_2(x, y) = 2x + y$ とおくと、これらは直交する Latin 方陣であることを示せ。$n$ が偶数のとき、どこが成り立たなくなるか。

解答

$L_1$ は加法表で Latin 方陣です。$L_2$ は、$x$ を固定すれば $y \mapsto 2x + y$ が全単射、$y$ を固定すれば $x \mapsto 2x + y$ が、$n$ が奇数で $2$ が $\mathbb{Z}/n\mathbb{Z}$ の単元であることから全単射です。直交性: $x + y = s$、$2x + y = t$ から $x = t - s$、$y = 2s - t$ とただ 1 つに決まります。よって $N(n) \ge 2$ です（定理 5.4 の証明の $a = 1, 2$ の場合で、$a$ と $a - b$ が単元であることだけを使っています）。$n$ が偶数のときは $2$ が単元でなく、$x \mapsto 2x + y$ が全単射でないので $L_2$ は Latin 方陣になりません。

参考文献

1. J. H. van Lint, R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press, 2001 — デザイン、Latin 方陣、Hadamard 行列、射影幾何、符号とデザインの各章。
2. P. J. Cameron, J. H. van Lint, Designs, Graphs, Codes and their Links, London Mathematical Society Student Texts 22, Cambridge University Press, 1991.
3. R. H. Bruck, H. J. Ryser, “The nonexistence of certain finite projective planes”, Canadian Journal of Mathematics 1 (1949), 88–93.
4. C. W. H. Lam, L. Thiel, S. Swiercz, “The non-existence of finite projective planes of order 10”, Canadian Journal of Mathematics 41 (1989), 1117–1123.
5. R. C. Bose, S. S. Shrikhande, E. T. Parker, “Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture”, Canadian Journal of Mathematics 12 (1960), 189–203.
6. F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977 — 第 2 章（Hadamard 行列・デザインと Golay 符号）、第 6 章（符号・デザイン・完全符号）。