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

1. 問題の内容

$p$ を $n-1$ を4で割ると3余る素数とし、$F_p^\times = F_p \setminus \{0\}$ とする。以下のことを示す。

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

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

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

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

2. 解き方の手順

(1) $F_p^\times$ は位数 $p-1$ の巡回群である。生成元を $g$ とすると、$F_p^\times = \{g, g^2, \dots, g^{p-1}\}$ と表せる。$F_p$ 上の零でない平方数の集合 $S$ は、$\{g^2, g^4, \dots, g^{p-1}\}$ と表せるので、$|S| = (p-1)/2$ である。

(2) もし $-1$ が $F_p$ 上の平方数であるとすると、$x^2 = -1$ となる $x \in F_p$ が存在する。このとき、$x = g^k$ となる整数 $k$ が存在する。よって、$(g^k)^2 = -1$ すなわち $g^{2k} = -1$ となる。$p \equiv 3 \pmod{4}$ より $p = 4m + 3$ と書ける。すると $g^{2m+1}$ が $F_p^\times$ の生成元となる。ここで $F_p^\times$ の位数は $p-1 = 4m+2$ であるから、$-1 = g^{(p-1)/2} = g^{2m+1}$ である。したがって、$g^{2k} = g^{2m+1}$ となり、$2k \equiv 2m+1 \pmod{4m+2}$ が成り立つ。しかし、左辺は偶数であり、右辺は奇数であるため、これは矛盾する。したがって、$-1$ は $F_p$ 上の平方数ではない。

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

水準数は $p$ である。

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

各 $S+i$ は $S$ を平行移動させたものなので、ブロックサイズは $(p-1)/2$ である。

$F_p$ の各元 $x$ は、$S$ の要素の差として $(p-3)/4$ 回出現することを示す。

$S = \{s^2 \mid s \in F_p^\times\}$ である。

$x = a-b$ となる $a, b \in S$ の組の数を考える。

$x$ を固定し、$a = s^2, b = t^2$ とおく。すると、$x = s^2 - t^2$ となる。

$s^2 - t^2 = (s-t)(s+t) = x$ である。

$s-t = u$ とおくと、$s+t = x/u$ となり、$s = (u + x/u)/2, t = (x/u - u)/2$ となる。

$s, t$ が $F_p^\times$ の要素であるためには、$u \ne 0, x/u \ne 0, u+x/u \ne 0, x/u - u \ne 0$ である必要がある。

したがって、$u \ne 0, x \ne 0, u^2 \ne -x, u^2 \ne x$ である。

$p \equiv 3 \pmod{4}$ より $-1$ は平方数ではないので、$x$ と $-x$ の少なくとも一方は平方数ではない。

したがって、$u^2 \ne x$ か $u^2 \ne -x$ のどちらかが成り立つ。

$u^2 \ne x$ のとき、方程式 $u^2 = x$ は解を持たない。

このとき、$u$ の取り得る値は $p-1$ 個ある。

$S$ の要素の差として $x$ が現れる回数は $(p-1)/2 - 1$ であり、$(p-3)/4$ 回出現する。

従って、$\{S+i \mid i \in F_p\}$ は会合数 $(p-3)/4$ の BIB デザインをなす。

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

BIB デザインの incidence matrix $N$ を考える。$N$ は $p \times p$ の行列であり、$N_{ij} = 1$ if $j \in S+i$, $N_{ij} = 0$ otherwise である。

$N$ の各列の和は $(p-1)/2$ である。

$N$ の各行の和も $(p-1)/2$ である。

$N N^T = \lambda J + r I$ である。ここで、$r = (p-1)/2$ であり、$\lambda = (p-3)/4$ である。

$n \times (n-1)$ の直交配列を作るためには、$n$ を $p$ で置き換える。

サイズは $p \times (p-1)$ となる。

2水準の直交配列を作るためには、$N$ の要素 1 を 0 に、0 を 1 に置き換える。

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)$ の2水準直交配列は、(3)のBIBデザインのincidence matrixから構成できる。具体的にはincidence matrixの要素を0と1で反転させる。