$p = n-1$ は4で割ると3余る素数、$F_p^* = F_p \setminus \{0\}$ とする。以下の4つのステップで問題を解く。 (1) $F_p$ 上の0でない平方数の集合を $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\}$ とする。以下の4つのステップで問題を解く。

(1) $F_p$ 上の0でない平方数の集合を $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^0, g^1, g^2, ..., g^{p-2} \}$ と表せる。平方数は $g^{2k}$ の形をしているので、$S = \{g^0, g^2, ..., g^{p-3} \}$ となり、 $|S| = (p-1)/2$ が示される。

(2) $-1$ が $F_p$ 上の平方数であると仮定すると、ある $x \in F_p$ が存在して $x^2 = -1$ となる。$F_p^*$ の生成元を $g$ とすると、$x = g^k$ と書ける。よって、$(g^k)^2 = -1$、つまり $g^{2k} = -1$ となる。オイラーの規準より、$g^{(p-1)/2} \equiv -1 \pmod{p}$ であるから、$g^{2k} \equiv g^{(p-1)/2} \pmod{p}$。したがって、$2k \equiv (p-1)/2 \pmod{p-1}$ が成り立つ。これは $(p-1)/2$ が偶数であることを意味するが、$p \equiv 3 \pmod{4}$ より $(p-1)/2$ は奇数となり矛盾する。よって、$-1$ は $F_p$ 上の平方数ではない。

(3) $\{S+i \mid i \in F_p \}$ が BIB デザインであることを示す。

- 水準数 $p$ は明らか。

- ブロックサイズは $|S| = (p-1)/2$ より $(p-1)/2$。

- 各 $i, j \in F_p, i \neq j$ に対して、$i, j$ が $(p-3)/4$ 回会合することを示す。つまり、 $|(S+i) \cap (S+j)| = (p-3)/4$ を示す。

$k = i-j$ とおく。$S+i = \{s+i \mid s \in S\}$、 $S+j = \{s+j \mid s \in S\}$ であり、$|(S+i) \cap (S+j)| = |\{s_1, s_2 \in S \mid s_1 + i = s_2 + j\}| = |\{s_1, s_2 \in S \mid s_1 - s_2 = j - i = -k\}| = |\{s_1, s_2 \in S \mid s_2 - s_1 = k\}|$ となる。したがって、$S$ の元の差として $k$ が何回現れるかを数えればよい。$k \neq 0$ で、$S$ の元の差として $(p-3)/4$ 回現れることが示されれば、BIB デザインである。

(4) BIB デザインからの直交配列の構成は、定理7.1に従えば良い。

BIBデザインの incidence matrix を $N$ とする。$N$ の行を直交配列の列とする。列は $n$ 個あり、各列は2つの水準（0か1）を持ち、各列の長さは $n-1$ である。incidence matrix のサイズは $n \times n(n-1)/2$ であり、直交配列のサイズは $n \times n(n-1)/2$ である。

問題文ではサイズ $n \times (n-1)$ の直交配列を求められているので、BIB デザインにおけるブロック数を $n-1$ になるように制限すれば良い。しかしながら、一般的な BIB デザインから直交配列を構成する場合は、このような制限は必要ない。

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) (3)のBIBデザインから、2水準でサイズ $n \times (n-1)$ の直交配列を構成できる (具体的な構成方法は定理7.1を参照)。