正定値二次形式の類数を計算する Ruby スクリプト

class_number.rb

# 正定値二次形式の類を列挙するプログラム
# created by Junpei Tsuji <http://tsujimotter.info>

require 'prime'
require 'set'

# a, b, c を係数とする二次形式 f(x, y) = ax^2 + bxy + cy^2 を表すクラス
class QuadraticForm
	def initialize a,b,c
		@a = a
		@b = b
		@c = c
	end

	# 変数 x, y に代入して，二次形式 f(x, y) の値を返すメソッド
	def apply(x,y)
		@a*x*x + @b*x*y + @c*y*y
	end

	# 行列 [[p, q], [r, s]] によって変換された二次形式を返す関数
	def trans p,q,r,s 
		new_a = (@a*p*p + @c*r*r + @b*p*r)
		new_c = (@a*q*q + @c*s*s + @b*q*s)
		new_b = (2*@a*p*q + 2*@c*r*s + @b*(p*s + q*r))

		QuadraticForm.new new_a,new_b,new_c
	end


	# 二次形式の式を文字列で返すメソッド
	def to_s
		str = ""
		if @a == 1 then
			str += "x^2"
		else
			str += "#{@a}x^2"
		end

		if @b == 1 then
			str += "+xy"
		elsif @b == -1 then
			str += "-xy"
		elsif @b > 0 then
			str += "+#{@b}xy"
		elsif @b < 0 then
			str += "-#{-@b}xy"
		end

		if @c == 1 then
			str += "+y^2"	
		else
			str += "+#{@c}y^2"	
		end

		str
	end

end



# 判別式が d であるような正定値二次形式の同値類の代表元を，すべての同値類について列挙する関数
#   ただし，出力は QuadraticForm オブジェクトの配列として返し，
#   その要素は，各同値類の代表元を reduced form としてとったものである
def classesOfDiscriminant d 
	classes = []

	# a <= \sqrt(-d/3) となる正の整数 a を列挙
	a = 1 
	while a <= Math::sqrt(-d/3.0)

		# |b| <= a となる非負整数 |b| を列挙
		(0..a).each do |b_abs|

			r = (b_abs**2 - d).modulo(4*a)

			# c が整数のとき
			if r == 0 then
				c = (b_abs**2 - d) / (4*a)


				# reduced form の条件より
				if a <= c then

					# reduced form は primitive
					# すなわち，a, b, c は互いに素
					if a.gcd(b_abs).gcd(c) == 1 then

						# b > 0 の場合
						b = b_abs
						reducedform = QuadraticForm.new a,b,c
						classes.push reducedform

						# b < 0 の場合
						if b_abs != 0 && !(b_abs == a || a == c) then
							b = -b_abs
							reducedform = QuadraticForm.new a,b,c
							classes.push reducedform
						end

					end

				end


			end

		end

		a += 1
	end

	classes
end




puts "D, h(D), C(D)"

# 判別式が -3 から -163 までの間の類数を計算する
(1..163).each do |i|
	# 正定値二次形式扱いたいので，判別式 D < 0 のときだけに限定して考える
	d = -i

	# 判別式 D が D ≡ 0, 1 (mod 4) のときだけ考える
	if d.modulo(4) == 0 || d.modulo(4) == 1 then

		c_d = classesOfDiscriminant(d)	# 類群
		h_d = c_d.size					# 類数

		print "#{d}, #{h_d}, "

		# 類群の代表元（の二次形式）を列挙する
		c_d.each_with_index do |f, i|
			print "[#{f.to_s}]"

			if i < h_d-1 then
				print ","
			end
		end

		puts ""
	end

end


# デバッグ用に，判別式 D = -236364091 = -4・59091023 + 1 の類数を計算する
=begin
c_d = classesOfDiscriminant(-236364091)
h_d = c_d.size

puts h_d #=> 3732
=end



# 二次形式の変換のテスト
=begin
f = QuadraticForm.new 1,0,5
g = f.trans 1,1,0,1

puts f #=> "x^2+5y^2"
puts g #=> "x^2+2xy+6y^2"
=end