$p = n - 1$ を4で割ると3余る素数とし、$F_p^* = F_p \setminus \{0\}$ とする。 (1) $F_p$ 上の零でない平方数の集合を$S$とおく。$|S| = (p - 1) / 2$ であることを示す。 (2) $-1$ は $F_p$ 上の平方数でないことを示す。 (3) $S + i := \{ s + i \mid s \in S \}$ とおく。このとき $\{ S + i \mid i \in F_p \}$ は、水準数 $p$, ブロックサイズ $(p - 1) / 2$, 会合数 $(p - 3) / 4$ の BIB デザインをなすことを示す。 (4) (3) の BIB デザインから、2水準でサイズ $n \times (n - 1)$ の直交配列を構成する。

1. 問題の内容

$p = n - 1$ を4で割ると3余る素数とし、$F_p^* = F_p \setminus \{0\}$ とする。

(1) $F_p$ 上の零でない平方数の集合を$S$とおく。$|S| = (p - 1) / 2$ であることを示す。

(2) $-1$ は $F_p$ 上の平方数でないことを示す。

(3) $S + i := \{ s + i \mid s \in S \}$ とおく。このとき $\{ S + i \mid i \in F_p \}$ は、水準数 $p$, ブロックサイズ $(p - 1) / 2$, 会合数 $(p - 3) / 4$ の BIB デザインをなすことを示す。

(4) (3) の BIB デザインから、2水準でサイズ $n \times (n - 1)$ の直交配列を構成する。

2. 解き方の手順

(1) $F_p^*$ は位数 $p-1$ の巡回群である。その生成元を $g$ とすると、$F_p^* = \{ g, g^2, \dots, g^{p-1} = 1 \}$ である。$F_p^*$ の元のうち平方数であるものは、ある $x \in F_p^*$ に対して $x^2$ の形をしているものである。すなわち、$g^2, g^4, \dots, g^{p-1}$ である。したがって、平方数は $(p - 1) / 2$ 個存在する。よって、$|S| = (p - 1) / 2$。

(2) $-1$ が $F_p$ 上の平方数であると仮定すると、ある $x \in F_p^*$ が存在して $x^2 = -1$ となる。したがって、$x^4 = 1$。$x$ の位数を $m$ とすると、$m$ は 4 を割り切る。すなわち、$m = 1, 2, 4$。もし $m = 1$ ならば $x = 1$ であり、$x^2 = 1 = -1$ となるが、これは $p = 2$ の場合にしか起こり得ない。しかし、$p$ は4で割ると3余る素数なので、$p \ge 3$ であり、これは矛盾。もし $m = 2$ ならば $x = -1$ であり、$x^2 = 1 = -1$ となるが、これも $p = 2$ の場合にしか起こり得ないため矛盾。したがって、$m = 4$ である。

$F_p^*$ の位数は $p - 1$ であるから、$x$ の位数は $p - 1$ を割り切らなければならない。したがって、4 は $p - 1$ を割り切る。しかし、$p$ は4で割ると3余る数なので、$p - 1$ は4で割ると2余る。これは矛盾。したがって、$-1$ は $F_p$ 上の平方数ではない。

(3) $\{ S + i \mid i \in F_p \}$ が水準数 $p$, ブロックサイズ $(p - 1) / 2$ であることは明らか。

$i \ne j$ に対して、$(S + i) \cap (S + j)$ の濃度が $(p - 3) / 4$ であることを示す。$s_1 + i = s_2 + j$ となる $s_1, s_2 \in S$ が存在するための $i, j$ の組の個数を数えれば良い。これは、$s_1 - s_2 = j - i$ となる $s_1, s_2$ の組の個数を数えることに相当する。すなわち、$S$ の要素の差として $j - i$ が何回現れるかを数えれば良い。

$p$ は4で割ると3余る素数なので、$F_p^*$ の元のうち平方数であるものとそうでないものは $(p - 1) / 2$ 個ずつ存在する。$z$ が $F_p^*$ の零でない元であるとき、$z$ が $S$ の要素の差として $(p - 3) / 4$ 回出現することを言えばよい。これは、ヒントにある通りである。$S+i$ は $p$ 個あり、$i$ を動かすと $p$ 個の $S+i$ が得られる。二つの異なる $S+i$ と $S+j$ は $(p-3)/4$ 個の要素を共有する。したがって、会合数は $(p-3)/4$ である。

(4) (3) の BIB デザインから、以下のように $n \times (n - 1)$ の直交配列を構成する。$n=p+1$ である。

行：$F_p \cup \{\infty \}$ の要素をラベルとする。

列：$F_p$ の要素のペア $(i,j)$ で $i \ne j$ となるものをラベルとする。列の数は $p(p-1) = (n-1)(n-2)$ である。

(i,j) 列の i 行目の要素は、もし $i \in S+j$ ならば 0, そうでなければ 1 とする。

(i,j) 列の $\infty$ 行目の要素は、全ての $i \in F_p$ に対して要素の値が異なるように選ぶ。

この配列は直交配列である。

3. 最終的な答え

(1) $|S| = (p - 1) / 2$

(2) $-1$ は $F_p$ 上の平方数ではない

(3) $\{ S + i \mid i \in F_p \}$ は水準数 $p$, ブロックサイズ $(p - 1) / 2$, 会合数 $(p - 3) / 4$ の BIB デザインをなす

(4) サイズ $n \times (n - 1)$ の直交配列を構成可能