グラフ理論で2次多項式の判別式を考える

222

概要

今回は、グラフ理論を使って2次方程式の判別式に関するちょっとした小ネタを紹介します。
以降 $F$ を有限体、 $F (x, y)$ を $F$ 上の対称式とし、グラフ $G (F)$ を、頂点集合 $V (G (F))$ を $F$ 、辺集合 $E (G (F))$ を ${{x, y} ∣ F (x, y) = 0}$ とする(単純とは限らない)無向グラフとします。

根の個数

$r o o t_{x} (f (x))$ を $f (x) = 0$ の解の個数とする。

判別式

$D_{x} (f (x))$ を、 $f (x)$ を $x$ の多項式と見たときの判別式とする。

握手の補題

$G (F)$ に握手の補題を適用することで、次の定理が得られる。

$\sum_{x \in F} r o o t_{y} (F (x, y)) + r o o t_{x} (F (x, x)) \equiv 0 (\mod 2)$

これを $F (x, y)$ が2次対称式のときに適用すると、次の結果が得られる。

$F (x, y)$ が2次対称式のとき、 $D_{y} (F (x, y))$ と $F (x, x)$ が $x$ についての2次多項式になるなら
$D_{x} (F (x, x)) = 0 \Leftrightarrow D_{x} (D_{y} (F (x, y))) = 0$

$G (F)$ を考える。 $x \in F$ の次数が奇数となるのは以下の2つの場合のみである。

$y$ についての方程式 $F (x, y) = 0$ が $y = x$ でない重解を持つ(このとき $x$ は次数 $1$ の頂点)
$F (x, x) = 0$ で, $y = x$ が $y$ についての方程式 $F (x, y) = 0$ の重解とならない。(このとき $x$ はあるループの端点で、ループでない辺にも接続しているので次数 $3$ )

$S = {x ∣ F (x, y) = 0 が重解を持つ}$ 、 $T = {x ∣ F (x, x) = 0}$ とすると、上の前者の場合は $S ∖ T$ 、後者の場合は $T ∖ S$ である。
握手の補題より $| S ∖ T | + | T ∖ S | \equiv 0 (\mod 2)$ だから
$| S | + | T | = | S ∖ T | + | T ∖ S | + 2 | S \cap T |$
$\equiv | S ∖ T | + | T ∖ S | \equiv 0 (\mod 2)$ なので $| S | \equiv | T | (\mod 2)$ である。
2次多項式 $f (x) = 0$ の解が奇数個 $\Leftrightarrow$ $D_{x} (f) = 0$ なので,
$D_{x} (F (x, x)) = 0 \Leftrightarrow | T | \equiv 1 (\mod 2)$
$\Leftrightarrow | S | \equiv 1 (\mod 2) \Leftrightarrow D_{x} (D_{y} (F (x, y))) = 0$