n次方程式の判別式の項数

京大、16次方程式の判別式計算に成功 | エンタープライズ | マイコミジャーナル

たぶんここに書いた話と同じです。

n次方程式の判別式の具体的表示（1） - 桃の天然水
n次方程式の判別式の具体的表示（2） - 桃の天然水

判別式は、根の差積を自乗したものなので、n次方程式ならn(n - 1)次式になります。3次方程式で考えると、判別式は6次で、各係数が根の1,2,3次になるので、この組合せで6次になるものを数えます。aを1次、bを2次、cを3次としてそうなるのは、

a⁶ a⁴b a³c a²c² abc b³ c²

の7項です。判別式には実際には5項が使われています。
この計算をするには母関数を使います。

(1 + x + x² + … + x⁶)(1 + x² + x⁴ + x⁶)(1 + x³ + x⁶)
= 1 + x + 2x² + 3x³ + 4x⁴ + 5x⁵ + 7x⁶ + …

で各係数が組合せの数になります。6次になる組合せは7つということになります。16次もこのようにすれば簡単に求められます。

type Poly = Array[Long]

def series(n :Int) =
	(0 to M).map(k => if(k % n == 0) 1L else 0L).toArray

def mul(f :Poly, g :Poly) = {
	val h = new Array[Long](M + 1)
	for(i <- 0 to M; j <- 0 to M - i if g(i) != 0)
		h(i+j) += f(j) * g(i)
	h
}

val N = 3
val M = N * (N - 1)
val f = (1 to N).map(series).reduceLeft(mul(_, _))
println (f.toList)		// 676491536028

約6700億項くらいになります。記事によると実際の項数は38億くらいで、かなり0の係数が多いんですね。

これって、一般的に多項式の行列の逆行列を求めるのが速くなったんでしょうか。この問題特有だとそんなに意味がないかも。