$p = n - 1$ を4で割ると3余る素数とし、$F_p^* = F_p \setminus \{0\}$ とする。以下の問いに答えよ。 (1) $F_p$ 上の零でない平方数の集合を $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\}$ とする。以下の問いに答えよ。

(1) $F_p$ 上の零でない平方数の集合を $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, g^2, ..., g^{p-1} = 1\}$ と表せる。$F_p$ 上の零でない平方数とは、$F_p^*$ の要素 $x^2$ の形をしているものである。

$F_p^*$ の要素を2乗したものは $g^2, g^4, ..., g^{2(p-1)}$ となる。$g^{2(p-1)} = (g^{p-1})^2 = 1$ である。$p-1$ は偶数なので、$2(p-1) = p-1 + (p-1)$ となる。

よって、$F_p^*$ の要素を2乗したものの個数は $(p-1)/2$ 個である。したがって、$|S| = (p-1)/2$ である。

(2)

$p$ は4で割ると3余る素数なので、$p = 4k + 3$ と書ける。

もし $-1$ が $F_p$ 上の平方数であるとすると、$x^2 = -1$ となる $x \in F_p$ が存在する。このとき、$x^{p-1} = x^{4k+2} = (x^2)^{2k+1} = (-1)^{2k+1} = -1$ となる。

しかし、$F_p^*$ の任意の要素 $x$ に対して、$x^{p-1} = 1$ が成り立つので矛盾する。

したがって、$-1$ は $F_p$ 上の平方数ではない。

(3)

$\{S + i \mid i \in F_p\}$ が BIB デザインをなすことを示すためには、以下の3つの条件を示す必要がある。

(a) 各ブロックのサイズが等しいこと。

(b) 各要素が同じ回数だけ現れること。

(c) 任意の2つの要素が同じ回数だけ同時に現れること。

(a) $S + i = \{s + i \mid s \in S\}$ なので、$|S + i| = |S| = (p-1)/2$ であり、すべてのブロックのサイズは $(p-1)/2$ で等しい。

(b) $i \in F_p$ を固定する。$i$ を含むブロックは $S + j$ の形で、$j \in F_p$ であるもの。この数は、ある $s \in S$ が存在して $s + j = i$ を満たす $j$ の個数に等しい。つまり、$j = i - s$ となる $j$ の個数。$s \in S$ は $(p-1)/2$ 個なので、$i$ を含むブロックの個数は $(p-1)/2$ となり、各要素は同じ回数だけ現れる。

(c) 異なる2つの要素 $i, j \in F_p$ を固定する。$i, j$ を含むブロックの個数、すなわち $i, j$ が同時に現れる回数を求める。$i, j \in S + k$ となる $k \in F_p$ の個数を求めることになる。$S + k$ の要素は $s + k$ の形で表される。$i = s_1 + k$、$j = s_2 + k$ となる $s_1, s_2 \in S$ が存在する必要がある。よって、$i - j = s_1 - s_2$ となる。$i - j$ が $S$ の要素の差として $(p-3)/4$ 回出現することが示されれば、会合数が $(p-3)/4$ である BIB デザインとなる。ヒントにあるように、$F_p^*$ の各元が $S$ の要素の差として $(p-3)/4$ 回出現することを確かめる。

$d \neq 0$ を $F_p^*$ の任意の要素とする。$s_1 - s_2 = d$ となる $s_1, s_2 \in S$ の組 $(s_1, s_2)$ の個数を求める。$S$ は平方数の集合なので、この差が $S$ の要素の差として何回現れるかを計算する。詳細は省略するが、$p = 4k + 3$ のとき、この差の出現回数は $(p-3)/4$ となる。

(4)

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

BIB デザインの各ブロックに対応する列を考える。各列は $n$ 個の要素を持ち、その値は $0$ または $1$ である。$i$ 番目の要素が $1$ であるのは、$i$ が対応するブロックに含まれている場合、そうでなければ $0$ である。このようにして構成された行列は、サイズ $n \times p$ となる。

問題ではサイズ $n \times (n-1)$ の直交配列を構成する必要がある。そこで、$p = n-1$ を利用する。BIB デザインのブロックに対応する列を考える。各列は $n$ 個の要素を持ち、その値は $0$ または $1$ である。$i$ 番目の要素が $1$ であるのは、$i$ が対応するブロックに含まれている場合、そうでなければ $0$ である。こうしてできた $n \times p = n \times (n-1)$ の行列は直交配列となる。

各行の和は $(p-1)/2$ で一定であり、任意の2列は $(p-3)/4$ 回だけ同時に $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) (3)の BIB デザインから構成される $n \times (n-1)$ の行列は直交配列である