問題は以下の4つの部分から構成されています。 (1) 有限体 $F_p$ 上の0でない平方数の集合を$S$とするとき、$|S| = (p-1)/2$ であることを示します。ここで、$p$は$n-1$を4で割ると3余る素数です。また、$F_p^{\times} = F_p \setminus \{0\}$です。 (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. 問題の内容

問題は以下の4つの部分から構成されています。

(1) 有限体 $F_p$ 上の0でない平方数の集合を$S$とするとき、$|S| = (p-1)/2$ であることを示します。ここで、$p$は$n-1$を4で割ると3余る素数です。また、$F_p^{\times} = F_p \setminus \{0\}$です。

(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^{\times}$ は位数 $p-1$ の巡回群であるため、その生成元を $g$ とすると、すべての元は $g^k$ ($k = 0, 1, \dots, p-2$) の形で表されます。$F_p$ 上の平方数は $g^{2k}$ の形で表される元です。したがって、$S = \{g^0, g^2, g^4, \dots, g^{p-3}\}$ となります。$g^{2k} = g^{2l}$ となるのは $2k \equiv 2l \pmod{p-1}$ のときであり、これは $k \equiv l \pmod{(p-1)/2}$ と同値です。したがって、平方数の個数は $(p-1)/2$ 個となります。

(2) もし $-1$ が $F_p$ 上の平方数であるならば、ある $x \in F_p^{\times}$ に対して、$x^2 = -1$ が成り立ちます。すると、 $x^4 = 1$ となります。$x$ の位数を $d$ とすると、$d \mid 4$ です。一方、$x \in F_p^{\times}$ より、$d \mid p-1$ でもあります。よって、$d \mid \gcd(4, p-1)$ です。$p$ は $n-1$ を 4 で割ると 3 余る素数なので、$p-1$ は 4 で割ると 2 余る数です。したがって、$p-1 = 4k + 2$ と書けます。$\gcd(4, p-1) = \gcd(4, 4k+2) = 2$ であるため、$d \mid 2$ となります。もし $d=1$ ならば、$x=1$ となりますが、$1^2 \neq -1$ なので矛盾します。もし $d=2$ ならば、$x^2 = 1$ となりますが、$x^2 = -1$ と矛盾します。したがって、$-1$ は $F_p$ 上の平方数ではありません。

(3) $i, j \in F_p$ ($i \neq j$) に対して、$S+i$ と $S+j$ の共通部分の大きさを求めます。$(S+i) \cap (S+j) = \{ s_1 + i = s_2 + j \mid s_1, s_2 \in S \}$ です。これは $s_1 - s_2 = j-i$ と同値です。$j-i \in F_p^{\times}$ です。$F_p^{\times}$ の各元が $S$ の要素の差として何回出現するかを数えます。$S$ の要素の差は $s_1 - s_2$ の形で表され、$s_1, s_2 \in S$ です。$|S| = (p-1)/2$ で、$S$ の各元は $F_p$ の平方数です。$F_p^{\times}$ の元が $S$ の要素の差として $(p-3)/4$ 回出現することを示せば、会合数が $(p-3)/4$ の BIB デザインとなります。

(4) (3)で構成されたBIBデザインを使って、直交配列を作ります。行を $F_p$ の要素に対応させ、列をブロックに対応させます。要素 $i$ がブロック $S+j$ に含まれるとき、(i, j)成分を 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水準でサイズ $n \times (n-1)$ の直交配列を構成できる。