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

1. 問題の内容

$p$ を $n-1$ を 4 で割ると 3 余る素数とし、$\mathbb{F}_p^{\times} = \mathbb{F}_p \setminus \{0\}$ とする。以下の手順で定理 7.1 を示せ。

(1) $\mathbb{F}_p$ 上の零でない平方数の集合を $S$ とおく。$|S| = (p-1)/2$ であることを示せ。

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

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

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

2. 解き方の手順

(1) $\mathbb{F}_p^{\times}$ は位数 $p-1$ の巡回群であるから、生成元 $g$ が存在する。このとき、$S$ は $\mathbb{F}_p^{\times}$ の平方数の集合なので、$S = \{g^2, g^4, \dots, g^{p-1}\}$ と表せる。したがって、$S$ の要素数は $(p-1)/2$ である。よって、$|S| = (p-1)/2$ である。

(2) $p \equiv 3 \pmod{4}$ であるから、$p = 4k + 3$ と書ける。もし $-1$ が $\mathbb{F}_p$ 上の平方数だとすると、ある $x \in \mathbb{F}_p^{\times}$ が存在して $x^2 = -1$ となる。$\mathbb{F}_p^{\times}$ は位数 $p-1$ の巡回群であるから、$x = g^m$ と書ける。よって、$g^{2m} = -1$ となる。したがって、$g^{2m} = g^{(p-1)/2}$ となるので、$2m \equiv (p-1)/2 \pmod{p-1}$。つまり、$4m \equiv p-1 \pmod{2(p-1)}$。

$p=4k+3$ を代入すると、$4m \equiv 4k+2 \pmod{8k+4}$ となる。これは $4m = 4k+2 + l(8k+4)$ となる整数 $l$ が存在することを意味する。つまり、$4m = 4k+2 + 8kl + 4l$。しかし、左辺は 4 の倍数だが、右辺は 2 を法として 0 にならない。したがって、$4m \equiv 4k+2 \pmod{8k+4}$ は成立しない。よって、$-1$ は $\mathbb{F}_p$ 上の平方数ではない。

(3) $v=p, k = (p-1)/2, \lambda=(p-3)/4$ を示す。$\{S+i | i\in \mathbb{F}_p\}$ で定義される incidence matrix $N$ を考える。$N N^T = \lambda J + (k-\lambda)I$ を示す。 $S+i$ のブロックサイズは $|S| = (p-1)/2$ なので、$k = (p-1)/2$。$S+i$ と $S+j$ ($i \ne j$) に共通して含まれる要素の数は $\lambda = (p-3)/4$ であることを示す。$a \in S+i$ かつ $a \in S+j$ とすると、ある $s_1, s_2 \in S$ が存在して $a = s_1 + i = s_2 + j$ となる。したがって、$s_1 - s_2 = j-i$ である。$S$ は $\mathbb{F}_p^{\times}$ の平方数全体からなる集合なので、$S = \{x^2 | x \in \mathbb{F}_p^{\times}\}$ と書ける。従って、$j-i$ が $S$ の要素の差として $(p-3)/4$ 回現れることを示せばよい。

$d \in \mathbb{F}_p^{\times}$ とする。$s_1 - s_2 = d$ を満たす $s_1, s_2 \in S$ の組 $\langle s_1, s_2 \rangle$ が何組あるかを数える。$s_1 - s_2 = d$ より、$s_1 = s_2 + d$。つまり、$s_2+d$ も $S$ の要素である必要がある。ここで、$s_2 = x^2$ と置くと、$x^2 + d = y^2$ となる $x, y \in \mathbb{F}_p^{\times}$ が存在するかどうかを調べる必要がある。つまり、$d = y^2 - x^2 = (y-x)(y+x)$ を満たす $x, y \in \mathbb{F}_p^{\times}$ が何組あるかを数える。$u = y-x, v = y+x$ と置くと、$d = uv$。よって、$u$ を定めると $v = d/u$ が決まる。$y = (u+v)/2, x = (v-u)/2$ なので、$u+v$ と $v-u$ がともに偶数であれば $x, y \in \mathbb{F}_p$ が求まる。

$x = (v-u)/2$ と $y = (u+v)/2$ がともに 0 でないとき、 $u \ne v$ かつ $u \ne -v$ が必要。$v=d/u$ より、$u \ne d/u$ かつ $u \ne -d/u$、つまり $u^2 \ne d$ かつ $u^2 \ne -d$。$u^2 = d$ または $u^2=-d$ となる $u$ はそれぞれ高々 2 つしか存在しない。$p=4k+3$ より $-1$ は平方数ではないので、$d$ と $-d$ が同時に平方数になることはない。よって、$S$ の要素の差として $\mathbb{F}_p^{\times}$ の各元は $(p-3)/4$ 回現れる。従って、$\lambda = (p-3)/4$ である。

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

BIB デザインの incidence matrix を $N$ とし、その要素 $n_{ij}$ が 1 なら対応する直交配列の要素を 1 とし、0 なら 0 とする。BIB デザインのパラメータは $v=p$, $k=(p-1)/2$, $\lambda=(p-3)/4$ である。ここで、$n=p-2 = v-2$ に注意する。この直交配列の行列は $n \times (n-1)$ である。

3. 最終的な答え

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

(2) $-1$ は $\mathbb{F}_p$ 上の平方数ではない

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

(4) (3) で得られた BIB デザインからサイズ $n \times (n-1)$ の直交配列を構成できる。