グラフ理論で2次多項式の判別式を考える
概要
今回は、グラフ理論を使って2次方程式の判別式に関するちょっとした小ネタを紹介します。
以降$\mathbb{F}$を有限体、$F(x,y)$を$\mathbb{F}$上の対称式とし、グラフ$G(F)$を、頂点集合$V(G(F))$を$\mathbb{F}$、辺集合$E(G(F))$を$\{ \{ x,y \} \mid F(x,y)=0 \}$とする(単純とは限らない)無向グラフとします。
$root_x(f(x))$を$f(x) = 0$の解の個数とする。
$D_x(f(x))$を、$f(x)$を$x$の多項式と見たときの判別式とする。
握手の補題
$G(F)$に握手の補題を適用することで、次の定理が得られる。
$$\sum_{x\in \mathbb{F}} root_y(F(x,y)) + root_x(F(x,x)) \equiv 0 \pmod 2$$
これを$F(x,y)$が2次対称式のときに適用すると、次の結果が得られる。
$F(x,y)$が2次対称式のとき、$D_y(F(x,y))$が$x$についての2次多項式になるなら
$D_x(F(x,x)) = 0 \Leftrightarrow D_x(D_y(F(x,y))) = 0$
$G(F)$を考える。$x \in \mathbb{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 \mid F(x,y)=0 が重解を持つ \}$、$T=\{ x \mid F(x,x)=0 \}$とすると、上の前者の場合は$S \setminus T$、後者の場合は$T \setminus S$である。
握手の補題より$|S \setminus T| + |T \setminus S| \equiv 0 \pmod 2$だから
$|S| + |T| = |S \setminus T| + |T \setminus S| + 2|S\cap T|$
$\equiv |S \setminus T| + |T \setminus S| \equiv 0 \pmod 2$なので$|S| \equiv |T| \pmod 2$である。
2次多項式$f(x) = 0$の解が奇数個$\Leftrightarrow$$D_x(f) = 0$なので,
$D_x(F(x,x)) = 0 \Leftrightarrow |T| \equiv 1 \pmod 2 $
$\Leftrightarrow |S| \equiv 1 \pmod 2 \Leftrightarrow D_x(D_y(F(x,y))) = 0$
この定理は実際に判別式を計算してみれば明らかだが、グラフ理論を用いて多項式の性質を調べることができるという点で興味深い。
終わりに
この議論を一般の体・$n$次対称式・$n$変数対称式に拡張する方法があれば知りたいです。