On the computation of the class number of an algebraic number field

Johannes Buchmann, Hywel C Williams

Mathematics of Computation · 1989 · 23 citations · 10 references

DOIFull text

Open access

Concepts

Abstract

It is shown how the analytic class number formula can be used to produce an algorithm which efficiently computes the class number <italic>h</italic> of an algebraic number field <italic>F</italic>. The method assumes the truth of the Generalized Riemann Hypothesis in order to estimate the residue of the Dedekind zeta function of <italic>F</italic> at <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="s equals 1"> <mml:semantics> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">s = 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> sufficiently well that <italic>h</italic> can be determined unambiguously. Given the regulator <italic>R</italic> of <italic>F</italic> and a known divisor <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h Superscript asterisk"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>h</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{h^ \ast }</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of <italic>h</italic>, it is shown that this technique will produce the value of <italic>h</italic> in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis StartAbsoluteValue d Subscript upper F Baseline EndAbsoluteValue Superscript 1 plus epsilon Baseline slash left-parenthesis h Superscript asterisk Baseline upper R right-parenthesis squared right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>F</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>h</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> </mml:mrow> <mml:mi>R</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(|{d_F}{|^{1 + \varepsilon }}/{({h^ \ast }R)^2})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> elementary operations, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d Subscript upper F"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>F</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{d_F}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the discriminant of <italic>F</italic>. Thus, if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h greater-than StartAbsoluteValue d Subscript upper F Baseline EndAbsoluteValue Superscript 1 slash 8"> <mml:semantics> <mml:mrow> <mml:mi>h</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>F</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>8</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">h &gt; |{d_F}{|^{1/8}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, then the complexity of computing <italic>h</italic> (with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h Superscript asterisk Baseline equals 1"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>h</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> </mml:mrow> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">{h^ \ast } = 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula>) is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis StartAbsoluteValue d Subscript upper F Baseline EndAbsoluteValue Superscript 1 slash 4 plus epsilon Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>F</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>4</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(|{d_F}{|^{1/4 + \varepsilon }})</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.

References

10