$p = n - 1$ が 4 で割ると 3 余る素数であるとする。$F_p^* = F_p \setminus \{0\}$ とする。このとき、以下の問いに答えよ。 (1) $F_p$ 上の 0 でない平方数の集合を $S$ とおく。$|S| = (p - 1) / 2$ であることを示せ。 (2) $-1$ は $F_p$ 上の平方数でないことを示せ。（ヒント：$F_p^*$ の生成元に着目する） (3) $S + i = \{s + i | s \in S\}$ とおく。このとき $\{S + i | i \in F_p\}$ は、水準数 $p$, ブロックサイズ $(p - 1) / 2$, 会合数 $(p - 3) / 4$ の BIB デザインをなすことを示せ。（ヒント：$F_p^*$ の各元が $S$ の要素の差として $(p - 3) / 4$ 回出現することを上手に確かめたい） (4) (3) の BIB デザインから、2 水準でサイズ $n \times (n - 1)$ の直交配列を構成せよ。

1. 問題の内容

$p = n - 1$ が 4 で割ると 3 余る素数であるとする。$F_p^* = F_p \setminus \{0\}$ とする。このとき、以下の問いに答えよ。

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

(2) $-1$ は $F_p$ 上の平方数でないことを示せ。（ヒント：$F_p^*$ の生成元に着目する）

(3) $S + i = \{s + i | s \in S\}$ とおく。このとき $\{S + i | i \in F_p\}$ は、水準数 $p$, ブロックサイズ $(p - 1) / 2$, 会合数 $(p - 3) / 4$ の BIB デザインをなすことを示せ。（ヒント：$F_p^*$ の各元が $S$ の要素の差として $(p - 3) / 4$ 回出現することを上手に確かめたい）

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

2. 解き方の手順

(1) $F_p^*$ の要素は $p - 1$ 個である。$x \mapsto x^2$ という写像を考えると、この写像の像が平方数の集合 $S$ に対応する。$F_p^*$ は巡回群なので、生成元 $g$ を用いて $g^k$ と表せる。このとき、$x = g^k$ が平方数であるための必要十分条件は $k$ が偶数であることである。したがって、平方数の個数は $(p - 1) / 2$ 個である。つまり、$|S| = (p - 1) / 2$ である。

(2) $p \equiv 3 \pmod{4}$ であるから、$p = 4k + 3$ と書ける。$-1$ が $F_p$ 上の平方数であると仮定すると、ある $x \in F_p$ が存在して、$x^2 = -1$ となる。このとき、$x^{p - 1} = x^{4k + 2} = (x^2)^{2k + 1} = (-1)^{2k + 1} = -1$ となる。一方、フェルマーの小定理より、$x^{p - 1} \equiv 1 \pmod{p}$ である。したがって、$-1 \equiv 1 \pmod{p}$ となり、$p | 2$ が得られるが、$p$ は素数なので、$p = 2$ となる。しかし、$p \equiv 3 \pmod{4}$ より、$p > 2$ であるから矛盾する。したがって、$-1$ は $F_p$ 上の平方数ではない。

(3) $\{S + i | i \in F_p\}$ が BIB デザインをなすことを示す。まず、水準数は $p$ である。各ブロック $S + i$ のサイズは $|S| = (p - 1) / 2$ である。次に、任意の $i, j \in F_p$ ($i \neq j$) に対して、$S + i$ と $S + j$ の共通要素の個数が $(p - 3) / 4$ であることを示す必要がある。

$S+i$ と $S+j$ の共通要素とは、$s_1 + i = s_2 + j$ となる $s_1, s_2 \in S$ が存在することである。これは $s_1 - s_2 = j - i$ と同値である。つまり、$j - i$ が $S$ の要素の差で $(p - 3) / 4$ 回出現することを示せばよい。$S$ の要素の差とは、$s_1 - s_2$ ($s_1, s_2 \in S$) の形をした要素のことである。$F_p$ の各元は、 $S$ の要素の差として $(p - 3) / 4$ 回出現するという仮定より、$j-i$ は$S$の要素の差として$(p-3)/4$回出現する。したがって、$\{S + i | i \in F_p\}$ は、水準数 $p$, ブロックサイズ $(p - 1) / 2$, 会合数 $(p - 3) / 4$ の BIB デザインをなす。

(4) BIB デザインから直交配列を構成する。BIB デザインの incidence matrix $N$ を考える。$N$ は $p \times p$ 行列で、$(i, j)$ 成分は $j \in S + i$ なら 1, そうでなければ 0 である。この $N$ を用いて、サイズ $n \times (n - 1)$ の直交配列を構成したい。$p = n - 1$ であり、水準数2の直交配列を作りたい。

行は $n$ 個、列は $n - 1 = p$ 個とする。各行は 2 水準（例えば0と1）で埋める。

$N$の$(i, j)$成分を直交配列の$(i, j)$成分にコピーする。

3. 最終的な答え

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

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

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

(4) (3)の incidence matrix $N$ の $(i, j)$ 成分を直交配列の $(i, j)$ 成分とすることでサイズ $n \times (n - 1)$ の直交配列が構成できる。