問題

自然数 $n$ および $2n = a^2 + b^2 + c^2 + d^2$ を満たす自然数 $a, b, c, d$ が与えられる。 自然数 $s, x, y, z$ であって $n = s^2 + x^2 + y^2 + z^2$ を満たすものを求めよ。

解法

A (提出したやつ)

$y, z$ のみで作れる自然数を $\sim 10^7$ ぐらいまで列挙しておく。 その後 $s \approx \sqrt{n}$ と $x \approx \sqrt{n - s^2}$ をいい感じに全探索する。 計算量は $O(\sqrt{n})$ ぐらい。

B (たぶん想定)

$a, b, c, d$ の情報を使って $O(1)$ で解ける。

$a, b, c, d$ の偶奇を考えると、偶数と奇数はそれぞれ偶数個ずつある。 つまり、偶偶偶偶、偶偶奇奇、奇奇奇奇、のいずれか。 一般性を失わず $a, b$ の偶奇が等しくかつ $a \le b$ と仮定してよい。 ここで $s = \frac{b - a}{2}$ かつ $x = \frac{b + a}{2}$ とすると、 $s, x$ は共に自然数でかつ $s^2 + x^2 = \frac{a^2 + b^2}{2}$ が言える。 これを $c, d$ についても行なえば $n$ が作れる。

C (https://cs.stackexchange.com/questions/68501/finding-the-sum-of-four-squares)

これは Legendre’s three-square theorem:

任意の自然数 $n \in \mathbb{N}$ に対し、 \(\exists x, y, z \in \mathbb{N}. ~ n = x^2 + y^2 + z^2 \hspace{1em} \iff \hspace{1em} \lnot \exists a, b \in \mathbb{N}. ~ n = 4^a (8b + 7)\)

を使った Lagrange’s four-square theorem:

任意の自然数 $N \in \mathbb{N}$ に対し、 $\exists s, x, y, z. ~ n = s^2 + x^2 + y^2 + z^2$

の証明を利用して、$a, b, c, d$ の情報を使わずに $O(\sqrt{N})$ で解く解法である。 Legendre’s three-square theorem を認めた上で、まず Lagrange’s four-square theorem の証明を見る。

証明:
$N$ に関する数学的帰納法で示す。 $N = 0$ かどうかと $4 \mid N$ かどうかで場合分け:

  • $N = 0$ の場合:
    $s = x = y = z = 0$ とすればよい。
  • $N \ne 0$ かつ $4 \mid N$ の場合:
    帰納法の仮定により $\frac{N}{4} = s^2 + x^2 + y^2 + z^2$ な $s, x, y, z$ がある。$N = (2s)^2 + (2x)^2 + (2y)^2 + (2z)^2$ である。

  • $4 \not\mid N$ の場合:
    Legendre’s three-square theorem を使うことにすると、 $N - s^2$ が $\lnot \exists a, b \in \mathbb{N}. ~ N - s^2 = 4^a (8b + 7)$ となるような $s$ を見つければよい。 これには、常に $4^a (8b + 7) \equiv 0, 4, 7 \pmod{8}$ であるので、 $N - s^2 \equiv 0, 4, 7 \pmod{8}$ な $s$ を見つければよい。 そこで $N \bmod 8$ で場合分け:

    • $N \equiv 0, 4 \pmod{8}$ の場合:
      $4 \not\mid N$ の仮定があるのでありえない。
    • $N \equiv 1, 5 \pmod{8}$ の場合:
      $\lfloor \sqrt{N} \rfloor$ と $\lfloor \sqrt{N} \rfloor - 1$ のうち偶数の方を $s = 2s’$ とする。 $s^2 = 4s’^2 \equiv 0, 4 \pmod{8}$ であるので $N - s^2 \equiv 1, 5 \pmod{8}$ である。
    • $N \equiv 2, 3, 6, 7 \pmod{8}$ の場合:
      $\lfloor \sqrt{N} \rfloor$ と $\lfloor \sqrt{N} \rfloor - 1$ のうち奇数の方を $s = 2s’ + 1$ とする。 $s^2 = (2s’ + 1)^2 = 4s’^2 + 4s’ + 1 \equiv 1 \pmod{8}$ であるので $N - s^2 \equiv 1, 2, 5, 6 \pmod{8}$ である。 $\fbox{}$

この証明中で定まる $s$ を取る。 すると $N - s^2$ は高々 $\sqrt{N}$ 程度である。 このとき $x, y, z$ を全探索することを考える。 $x, y$ をそれぞれ高々 $\sqrt[4]{N}$ 程度まですべて考え $N - s^2 - x^2 - y^2$ が平方数かどうか判定すればよい。 よって全体で $O(\sqrt{N})$ で $x, y, z$ が見つかる。

メモ

  • こういう一発ギャグを解けないのどうにかしたい

リンク