$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, \dots, g^{p-1}\}$ と表せる。平方数の集合 $S$ は $\{g^2, g^4, \dots, g^{p-1}\}$ となる。したがって、平方数の個数は $(p-1)/2$ である。つまり、$|S| = (p-1)/2$。

(2) もし $-1$ が $F_p$ 上の平方数であるとすると、ある $x \in F_p^*$ が存在して $x^2 = -1$ を満たす。

$F_p^*$ の生成元を $g$ とすると、$x = g^k$ と表せる。よって、$g^{2k} = -1$ となる。

$g$ の位数は $p-1$ であるから、$g^{(p-1)/2} = -1$ である。

したがって、$g^{2k} = g^{(p-1)/2}$。

よって、$2k \equiv (p-1)/2 \pmod{p-1}$。

したがって、$(p-1)/2$ は偶数でなければならない。

しかし、$p \equiv 3 \pmod{4}$ より、$(p-1)/2$ は奇数である。

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

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

(i) 水準数 $p$ であることは明らか。

(ii) ブロックサイズが $(p-1)/2$ であることも明らか。なぜなら、$|S| = (p-1)/2$ であり、$S+i$ の要素数は $S$ の要素数と等しいから。

(iii) 任意の $i \neq j \in F_p$ に対して、$| (S+i) \cap (S+j) | = (p-3)/4$ であることを示す。

$S+i = \{s+i \mid s \in S\}$ かつ $S+j = \{s'+j \mid s' \in S\}$ であるから、$s+i = s'+j$ を満たす $s, s' \in S$ の組の個数が $|(S+i) \cap (S+j)|$ と等しい。

$s - s' = j - i$ である。$F_p^*$ の各元が $S$ の要素の差として $(p-3)/4$ 回出現することを示せばよい。

$F_p^*$ の各元 $d$ に対して、$s - s' = d$ を満たす $s, s' \in S$ の組の個数は、ルジャンドル記号 $\chi(x)$ を用いて $\frac{1}{4} \sum_{x \in F_p^*} (1+\chi(x))(1+\chi(x+d))$ で与えられる。

$\sum_{x \in F_p^*} \chi(x) = 0$ であることと、$\chi(x) \chi(x+d) = \chi(1 + d/x)$ を用いると、

$\frac{1}{4} \sum_{x \in F_p^*} (1+\chi(x))(1+\chi(x+d)) = \frac{1}{4} (p-1 + \sum_{x \in F_p^*} \chi(1+d/x))$

$= \frac{1}{4} (p-1 - 1) = \frac{p-2}{4}$ (ただし、$d$ が平方数でない場合)

$(S+i) \cap (S+j)$ の濃度は $(p-3)/4$ に等しいことを示す。$S$ は $F_p^*$ の平方数の集合であるから、$S+i$ と $S+j$ の要素の差は $i-j$ だけ異なる。したがって、会合数は $(p-3)/4$ となる。

(4) サイズ $n \times (n-1)$ の直交配列を構成する。

$n = p+1$ であるから、$n \times (n-1) = (p+1) \times p$。

BIB デザインのブロックは $S+i, i \in F_p$ である。

2 水準の直交配列を構成するには、BIB デザインの incidence matrix を利用する。incidence matrix $A$ は $p \times p$ の行列で、$A_{i,j} = 1$ (もし $j \in S+i$)、0 (それ以外) で定義される。

この行列から直交配列を構成するには、各列について 1 と 0 の個数が等しくなるようにする必要がある。

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 デザインから、2 水準でサイズ $(p+1) \times p$ の直交配列を構成できる。