Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
正定値二次形式の類数を計算する Ruby スクリプト
# 正定値二次形式の類を列挙するプログラム
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.