大学数学基礎解説

文献あり

ラテン方格とアフィン平面

ブロックデザイン,組合せ論,シュタイナーシステム

フィッシャー不等式

算術三角形

自己同型群と拡大・縮小

アフィン平面
1. 相互直交ラテン方格

シュタイナー三重系
1. STSの直積

マシュー群 $M_{11}$ と $M_{12}$

構成したシュタイナーシステム

(2,3,7) , (2,3,9)
(2,4,16)NEW, (2,5,25)NEW
(3,4,8)

本筋から逸れる証明は折畳んでいる場合があるが, クリックで開くことができる.

導入

　 $1$ 行目を $\begin{matrix} 1 & 2 & 3 \end{matrix}$ に固定すると, $3 \times 3$ ラテン方格は2通りしかない.
$(2, 1)$ 成分に入るのは $2$ または $3$ で
$\begin{array}{r} L_{1} = \begin{array}{ccc} 1 & 2 & 3 \\ 2 \end{array}, L_{2} = \begin{array}{ccc} 1 & 2 & 3 \\ 3 \end{array} \end{array}$
ここまで書くと, 残りは数独の要領で確定する.
$\begin{array}{r} L_{1} = \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{array}, L_{2} = \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 3 & 1 \end{array} \end{array}$
このように $1$ 行目を"自然な"順序で固定したラテン方格を標準形と呼ぶ.
　これら2つのラテン方格には興味深い性質がある.
$\begin{array}{r} (L_{1}, L_{2}) = \begin{array}{ccc} (1, 1) & (2, 2) & (3, 3) \\ (2, 3) & (3, 1) & (1, 2) \\ (3, 2) & (1, 3) & (2, 1) \end{array} \end{array}$
これは2つのラテン方格を重ねて, 順序対を取ったもので, 左の成分のみを見ると $L_{1}$ が, 右の成分のみを見ると $L_{2}$ が見て取れる.
　 $1, 2, 3$ の順序対は $3^{2} = 9$ 通りあるが, そのすべてが $(L_{1}, L_{2})$ に過不足なく現れていることがすぐに確認できる.
　また
$\begin{array}{r} A = \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array} \end{array}$
と
$\begin{array}{r} L_{1} = \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{array}, L_{2} = \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 3 & 1 \end{array} \end{array}$
を見比べて, $L_{1}$ において成分が $1$ であるマスを $A$ から切り取ると, $(1, 6, 8)$ が, 同様に成分が $2, 3$ のマスからはそれぞれ $(2, 4, 9), (3, 5, 7)$ が得られる.
$L_{2}$ からも同様にして, 同じ成分の場所を $A$ から切り抜くと, $(1, 5, 9), (2, 6, 7), (3, 4, 8)$ が得られる.
また, $A$ の $1$ 行目の数字は $(1, 2, 3)$ , $2, 3$ 行目の数字はそれぞれ $(4, 5, 6), (7, 8, 9)$ で, $1, 2, 3$ 列目の数字は $(1, 4, 7), (2, 5, 8), (3, 6, 9)$ であり, 以上で掘り出した $12$ 個の3つ組
$\begin{array}{r} (1, 2, 3), (4, 5, 6), (7, 8, 9), \\ (1, 4, 7), (2, 5, 8), (3, 6, 9), \\ (1, 6, 8), (2, 4, 9), (3, 5, 7), \\ (1, 5, 9), (2, 6, 7), (3, 4, 8) \end{array}$
は位数 $3$ のアフィン平面 $S (2, 3, 9)$ をなしている.
　上記の性質を持つようなラテン方格を記述するため, ラテン方格の直交なるものを導入する.

定義と構成

ラテン方格の直交とMOLS

$L_{1}, L_{2}$ を $n \times n$ の異なるラテン方格, $L_{1} (i, j), L_{2} (i, j)$ をそれぞれ $L_{1}, L_{2}$ の $(i, j)$ 成分 $(1 \leq i, j \leq n)$ としたとき, 順序対 $(L_{1} (i, j), L_{2} (i, j))$ が各 $i, j$ に対してすべて異なっているとき, $L_{1}$ と $L_{2}$ は直交しているという.
$k$ 個の $n \times n$ ラテン方格の集合 ${L_{i}}_{i = 1, \dots, k}$ に関して, 任意の2つのラテン方格が直交しているとき, ${L_{k}}$ をMOLS (Mutually Orthogonal Latin Squares)または相互直交ラテン方格と呼び, $k - M O L S (n)$ と表記する.

　次はほとんど明らか.

${L_{k}}$ を $n \times n$ 標準形MOLSとしたとき, $k \leq n - 1$ .

標準形MOLSであるから, すべての $L_{k}$ の $1$ 行目は $[\begin{matrix} 1 & 2 & \dots & n \end{matrix}]$ だと考えてよい. よって, ${L_{k}}$ のどのラテン方格も $(2, 1)$ 成分には $1$ 以外が入り, $L_{i}, L_{j} \in {L_{k}} (1 \leq i < j \leq k)$ に対して, $L_{i} (2, 1) = L_{j} (2, 1) = m (1 < m \leq n)$ だとすると,
$\begin{array}{rcl} (L_{i} (2, 1), L_{j} (2, 1)) & = & (m, m) \\ = & (L_{i} (1, m), L_{j} (1, m)) \end{array}$
となり, $L_{i}$ と $L_{j}$ が直交していることに矛盾する. したがって, ${L_{k}}$ のラテン方格の $(2, 1)$ 成分にはすべて異なる数字が入るため, $k \leq n - 1$ .

MOLSの完全集合

上の定理で等号が成り立つ, 即ち $n - 1 - M O L S (n)$ のことを $M O L S (n)$ の完全集合と呼ぶことがある.

位数が素冪のMOLSの完全集合

$q$ を素冪, $F_{q} = {0 = α_{0}, 1 = α_{1}, α_{2}, \dots, α_{q - 1}}$ を有限体とすると, $k = 1, 2, \dots, q - 1$ に対して
$\begin{array}{r} L_{k} (i, j) = α_{k} α_{i - 1} + α_{j - 1} \end{array}$
と定められる集合 ${L_{k}}$ は $M O L S (q)$ の完全集合をなす.

[i] (各 $k$ に対して $L_{k}$ がラテン方格であること)
各行の成分がすべて異なることは明らか.
各列について, $F_{q}^{\times}$ は位数 $q - 1$ の巡回群であるから, 成分はすべて異なる.

[ii] (MOLSであること)
$k_{1}, k_{2} = 1, 2, \dots, q - 1, k_{1} \neq k_{2}$ に対して, $L_{k_{1}} (i, j) = L_{k_{1}} (i^{'}, j^{'}) \land L_{k_{2}} (i, j) = L_{k_{2}} (i^{'}, j^{'})$ とすると
$\begin{array}{r} {\begin{matrix} α_{k_{1}} α_{i - 1} + α_{j - 1} = α_{k_{1}} α_{i^{'} - 1} + α_{j^{'} - 1} \\ α_{k_{2}} α_{i - 1} + α_{j - 1} = α_{k_{2}} α_{i^{'} - 1} + α_{j^{'} - 1} \end{matrix} \\ (α_{k_{1}} - α_{k_{2}}) α_{i - 1} = (α_{k_{1}} - α_{k_{2}}) α_{i^{'} - 1} \end{array}$
$α_{k_{1}} \neq α_{k_{2}}$ より $α_{i - 1} = α_{i^{'} - 1}$ .
よって, $α_{j - 1} = α_{j^{'} - 1}$ となり, $L_{k_{1}}$ と $L_{k_{2}}$ は直交する.

例. $F_{4}$ と $F_{5}$

$F_{4}$

$F_{4} = {0, 1, ω, \overset{―}{ω}}$ として, 1行目を $[\begin{matrix} 0 & 1 & ω & \overset{―}{ω} \end{matrix}]$ で固定すると
$\begin{array}{r} ω [\begin{matrix} 0 \\ 1 \\ ω \\ \overset{―}{ω} \end{matrix}] = [\begin{matrix} 0 \\ ω \\ \overset{―}{ω} \\ 1 \end{matrix}], \overset{―}{ω} [\begin{matrix} 0 \\ 1 \\ ω \\ \overset{―}{ω} \end{matrix}] = [\begin{matrix} 0 \\ \overset{―}{ω} \\ 1 \\ ω \end{matrix}] \end{array}$
であるから
$\begin{array}{cccccccccccc} 0 & 1 & ω & \overset{―}{ω} & 0 & 1 & ω & \overset{―}{ω} & 0 & 1 & ω & \overset{―}{ω} \\ 1 & 0 & \overset{―}{ω} & ω & ω & \overset{―}{ω} & 0 & 1 & \overset{―}{ω} & ω & 1 & 0 \\ ω & \overset{―}{ω} & 0 & 1 & \overset{―}{ω} & ω & 1 & 0 & 1 & 0 & \overset{―}{ω} & ω \\ \overset{―}{ω} & ω & 1 & 0 & 1 & 0 & \overset{―}{ω} & ω & ω & \overset{―}{ω} & 0 & 1 \end{array}$
となる.

$F_{5}$

$F_{5} = Z / 5 Z$ であるから, 1行目の $[\begin{matrix} 0 & 1 & 2 & 3 & 4 \end{matrix}]$ を横にスライドしていくと, MOLSが得られる.
左に一つスライドして,
$\begin{array}{cccccccccc} 0 & 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 & 0 \\ 2 & 3 & 4 & 0 & 1 \\ 3 & 4 & 0 & 1 & 2 \\ 4 & 0 & 1 & 2 & 3 \end{array}$
左に二つスライドして,
$\begin{array}{cccccccccc} 0 & 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 0 & 1 \\ 4 & 0 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4 & 0 \\ 3 & 4 & 0 & 1 & 2 \end{array}$
以下同様に
$\begin{array}{cccccccccc} 0 & 1 & 2 & 3 & 4 & 0 & 1 & 2 & 3 & 4 \\ 3 & 4 & 0 & 1 & 2 & 4 & 0 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4 & 0 & 3 & 4 & 0 & 1 & 2 \\ 4 & 0 & 1 & 2 & 3 & 2 & 3 & 4 & 0 & 1 \\ 2 & 3 & 4 & 0 & 1 & 1 & 2 & 3 & 4 & 0 \end{array}$
という具合で, $4 - M O L S (5)$ が得られる.

MOLSとアフィン平面

位数 $n$ のアフィン平面 $S (2, n, n^{2})$ が存在するための必要十分条件は, $M O L S (n)$ の完全集合が存在することである.

(必要)

$S : = S (2, n, n^{2}) = S (Ω, B)$ の $n + 1$ 個の平行類を $H, V, P_{1}, P_{2}, \dots, P_{n - 1}$ , これらに含まれる直線を
$\begin{array}{rcl} H & = & {H_{1}, H_{2}, \dots, H_{n}} \\ V & = & {V_{1}, V_{2}, \dots, V_{n}} \\ P_{1} & = & {p_{11}, p_{12}, \dots, p_{1 n}} \\ P_{2} & = & {p_{21}, p_{22}, \dots, p_{2 n}} \\ ⋮ \\ P_{n - 1} & = & {p_{n - 1, 1}, p_{n - 1, 2}, \dots, p_{n - 1, n}} \end{array}$
とする.
$\begin{array}{r} 1 \leq^{\forall} i, j \leq n, H_{i} \cap V_{j} \neq \emptyset \end{array}$
が成り立つことから,
$\begin{array}{rcl} f : H \times V & ⟶ & {1, 2, \dots, n} \times {1, 2, \dots, n} \\ (H_{i}, H_{j}) & ⟼ & (i, j) \end{array}$
は全単射である. よって, 平行類 $P_{1}$ に対して,
$\begin{array}{r} L_{P_{1}} (i, j) = k ⟺ H_{i} \cap V_{j} = p_{1 k} \end{array}$
と定めれば, $L_{P_{1}}$ は $n \times n$ ラテン方格である.
他の平行類 $P_{2}, \dots, P_{n - 1}$ に対しても同様にラテン方格が構成でき, 結果的に $L_{P_{1}}$ 含め $n - 1$ 個のラテン方格が組み上がる. 後はこれらが互いに直交していることを確認すればよい.
平行類 $P_{1}, P_{2}$ から構成されたラテン方格 $L_{P_{1}}, L_{P_{2}}$ について,
$\begin{array}{rcl} (L_{P_{1}} (i, j), L_{P_{2}} (i, j)) & \neq & (L_{P_{1}} (i^{'}, j^{'}), L_{P_{2}} (i^{'}, j^{'})) \\ ⟺ L_{P_{1}} (i, j) \neq L_{P_{1}} (i^{'}, j^{'}) & \lor & L_{P_{2}} (i, j) \neq L_{P_{2}} (i^{'}, j^{'}) \\ ⟺ L_{P_{1}} (i, j) = L_{P_{1}} (i^{'}, j^{'}) & \Rightarrow & L_{P_{2}} (i, j) \neq L_{P_{2}} (i^{'}, j^{'}) \end{array}$
$l \in P_{1}$ が $(i, j), (i^{'}, j^{'})$ を通るとする. 任意の2直線は 2点以上交点を持てないため, $(i, j), (i^{'}, j^{'})$ を通るような $l^{'} \in P_{2}$ は存在しない. したがって,
$\begin{array}{rcl} L_{P_{1}} (i, j) = L_{P_{1}} (i^{'}, j^{'}) & \Rightarrow & L_{P_{2}} (i, j) \neq L_{P_{2}} (i^{'}, j^{'}) \end{array}$
が成り立ち, $n - 1$ 個のラテン方格はMOLSの完全集合をなす.
(十分)
必要条件の議論を逆に辿ればよい.

例. $S (2, 4, 16)$ と $S (2, 5, 25)$

　同じ色のセルを選択すれば, ブロックが得られる.

$S (2, 4, 16)$

$\begin{array}{r} \begin{array}{cccccccccccc} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{array} \begin{array}{cccccccccccc} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{array} \\ \begin{array}{cccccccccccc} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{array} \begin{array}{cccccccccccc} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{array} \begin{array}{cccccccccccc} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{array} \end{array}$

$S (2, 5, 25)$

$\begin{array}{r} \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{array} \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{array} \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{array} \\ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{array} \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{array} \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{array} \end{array}$

参考文献

[1]

Joy Morris, Mutually Orthogonal Latin Squares (MOLS), 閲覧日 2025年6月13日, https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_(Morris)/04%3A_Design_Theory/16%3A_Latin_Squares/16.02%3A_Mutually_Orthogonal_Latin_Squares_(MOLS)

投稿日：6日前

更新日：3日前

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

パトポス

1612

有限群論　好きな群は6次対称群

他の人のコメント

コメントはありません。

読み込み中

パトポス

ラテン方格とアフィン平面

導入
定義と構成
例. $F_{4}$ と $F_{5}$
MOLSとアフィン平面
例. $S (2, 4, 16)$ と $S (2, 5, 25)$
参考文献

ラテン方格とアフィン平面

導入

定義と構成

例. F4とF5

F4

F5

MOLSとアフィン平面

例. S(2,4,16)とS(2,5,25)

S(2,4,16)

S(2,5,25)

参考文献

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

例. $F_{4}$ と $F_{5}$

$F_{4}$

$F_{5}$

例. $S (2, 4, 16)$ と $S (2, 5, 25)$

$S (2, 4, 16)$

$S (2, 5, 25)$