$p = n-1$ を4で割ると3余る素数とし、$F_p^* = F_p \setminus \{0\}$ とする。 (1) $F_p$ 上の零でない平方数の集合を $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$ 上の零でない平方数の集合を $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$ の巡回群である。その生成元を $g$ とすると、$F_p^* = \{g^0, g^1, g^2, \dots, g^{p-2}\}$ である。

$F_p$ 上の零でない平方数の集合 $S$ は、$\{g^0, g^2, g^4, \dots, g^{p-3}\}$ と表せる。これは $p-1$ 個の要素のうち偶数乗のものだけなので、その個数は $(p-1)/2$ である。よって $|S| = (p-1)/2$ である。

(2) $p \equiv 3 \pmod{4}$ より、$p = 4k+3$ と書ける。$g$ は $F_p^*$ の生成元なので、$-1$ が平方数であると仮定すると、ある整数 $x$ が存在して $x^2 \equiv -1 \pmod{p}$ となる。

$x^2 \equiv -1 \pmod{p}$ より、$x^{p-1} \equiv (x^2)^{(p-1)/2} \equiv (-1)^{(p-1)/2} \equiv (-1)^{(4k+2)/2} \equiv (-1)^{2k+1} \equiv -1 \pmod{p}$ となる。しかし、フェルマーの小定理より、$x^{p-1} \equiv 1 \pmod{p}$ でなければならないので矛盾する。したがって、$-1$ は $F_p$ 上の平方数ではない。

(3) $S+i = \{s+i | s \in S\}$ である。この集合はブロックサイズ $|S| = (p-1)/2$ を持つ。$\{S+i | i \in F_p\}$ が BIB デザインとなることを示す。

$F_p$ の任意の2つの異なる要素 $x, y$ をとる。これらの要素が $S$ の要素の差として何回現れるかを考える。つまり、$s_1, s_2 \in S$ で $s_1 - s_2 \equiv x-y \pmod{p}$ となる組 $(s_1, s_2)$ の個数を求める。

$x-y \neq 0$ であることに注意する。$F_p^*$ の各元は $S$ の要素の差として $(p-3)/4$ 回現れることを示す必要がある。

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

BIB デザインの各ブロック $S+i$ を列に対応させる。各ブロック $S+i$ に対して、要素 $x \in F_p$ が $S+i$ に含まれるとき、その列の $x$ 行目に 1 を、そうでないときに 0 を書き込む。これにより、$p \times p$ の行列が得られる。$p = n-1$ という条件より、直交配列のサイズは $n \times (n-1)$ である必要があるので、少し修正を加える必要がある。

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) の BIB デザインから、2水準でサイズ $n \times (n-1)$ の直交配列を構成する。（詳細な構成方法は省略）