$F_p$を有限体、$S$を$F_p$の部分集合とする。$x, y \in F_p$に対して、$x - i \in S$かつ$y - i \in S$を満たすような$i$の個数を考える。これは$|(x-S) \cap (y-S)|$と表される。この値が常に$(p-3)/4$となる理由を説明する。

1. 問題の内容

$F_p$を有限体、$S$を$F_p$の部分集合とする。$x, y \in F_p$に対して、$x - i \in S$かつ$y - i \in S$を満たすような$i$の個数を考える。これは$|(x-S) \cap (y-S)|$と表される。この値が常に$(p-3)/4$となる理由を説明する。

2. 解き方の手順

まず、$S$がどのような集合であるかについて考察する必要がある。

$S$ が、平方剰余全体からなる集合であると仮定する。つまり、$S = \{ x^2 \pmod{p} \mid x \in F_p \}$ とする。

$x-i \in S$ かつ $y-i \in S$ を満たす$i$の個数を求める。

$x-i$ と $y-i$ がどちらも平方剰余であるということである。

これは、$x-i = u^2$ および $y-i = v^2$ となる $u, v \in F_p$ が存在することを意味する。

これらの式から、$i$ を消去すると、

$x - u^2 = y - v^2$

$x - y = u^2 - v^2 = (u-v)(u+v)$

となる。$x$ と $y$ が与えられたとき、この式を満たす $u$ と $v$ の組の数を求める必要がある。

$x - y = 0$ の場合 ($x = y$ の場合)、 $u^2 = v^2$ となり、$u = v$ または $u = -v$ となる。 $u$ は$p$個の値を取りうるので、平方剰余となる確率は約$p/2$であるから、 このとき、$x - i$ が平方剰余となる$i$の個数は約$(p+1)/2$となる。

$x - y \neq 0$ の場合、$x-y = (u-v)(u+v)$を解く。

$a = u-v$ と $b = u+v$ とおくと、$x-y = ab$ となる。

$u = (a+b)/2$ と $v = (b-a)/2$ となる。

$x-y = ab$ となるような $(a,b)$ の組は $p-1$ 個ある。

$a, b$ が決まれば、$u, v$ が決まる。

$u^2$ と $v^2$ が平方剰余である確率を考えると、$u^2$ と $v^2$ が平方剰余である確率はそれぞれ約 $1/2$ なので、$u^2$ と $v^2$ が同時に平方剰余である確率は約 $1/4$ となる。

したがって、$i$ の個数は約 $(p-1)/4$ となる。

$p = 3$ の場合は、$S = \{0,1\}$ となる。$x-i \in S$ かつ $y-i \in S$ となる $i$ の個数は、$x=y$ のとき2,$x\neq y$のとき1となる。

$(p-3)/4 = 0$ なので、$(p-3)/4$ になるわけではない。

問題文の条件では、この値が常に $(p-3)/4$ になるという制約が加わっているため、一般的な平方剰余の議論だけでは説明できない。$S$の選び方、もしくは$x,y$の選び方に制限がある可能性があります。

3. 最終的な答え

問題文の条件だけでは、なぜ $|(x-S) \cap (y-S)|$ が常に $(p-3)/4$ となるかを特定することはできません。$S$の定義または$x,y$に対する追加の制約が必要です。