Let $l$ be an odd prime number and $\zeta$ be a primitive $l$-th root of unity in $\mathbb{C}$. Let $K = \mathbb{Q}(\zeta)$. Let $A$ be the ring of algebraic integers in $K$. Let $\alpha \in A$. How can one compute efficiently the norm of $\alpha$ by hand or by using a calculator?

EDIT[Jul 28, 2012] The question asks an efficient algorithm. There are computer software doing this. I think, however, knowing its algorithm is more enlightening than using it as a blackbox.

EDIT Let $l = 19$. Let $\alpha = 1 + \zeta + \zeta^6$. I computed $N(\alpha) = 191$ by hand. It took me over a half day.

  • $\begingroup$ @Makoto Note that are freely available software systems for performing computations in algebraic number theory, e.g. Pari. $\endgroup$ – Bill Dubuque Jul 27 '12 at 22:42
  • $\begingroup$ @BillDubuque Yes, I know. I'd like to know its algorithm. $\endgroup$ – Makoto Kato Jul 27 '12 at 22:58
  • 5
    $\begingroup$ @Makoto The algorithms are described in Henri Cohen's A Course in Computational Algebraic Number Theory. You can also read the source code. $\endgroup$ – Bill Dubuque Jul 27 '12 at 23:03
  • $\begingroup$ @BillDubuque Thanks. Since I don't have the book at hand, it'd be nice that someone would post the algorithm. It does not need to be the same as that of the book. $\endgroup$ – Makoto Kato Jul 27 '12 at 23:22
  • 3
    $\begingroup$ What's the reason for the downvotes? Unless you make it clear, I can't improve my question. $\endgroup$ – Makoto Kato Jul 28 '12 at 0:10

There are standard techniques using determinants, resultants, etc, depending on what representation one is using for elements. Various methods are described below in an excerpt from Henri Cohen's A Course in Computational Algebraic Number Theory - one of the standard references on computational algebraic number theory. There is no need to do this by hand since there are many freely available software systems capable of algebraic number theory, e.g. the system Pari by Cohen's group at Bordeaux, which implements most of the algorithms described in his book.

enter image description here enter image description here

  • $\begingroup$ Thanks, Bill. While I don't doubt the above method can be used to compute the norm of a cyclotomic integer, my guess is that there could be more efficient algorithm than that. A cyclotomic number field has special properties that other number fields don't have. Perhaps one could use some of those properties to compute the norm of an element of such a field. $\endgroup$ – Makoto Kato Jul 28 '12 at 2:26
  • 2
    $\begingroup$ @Makoto I didn't realize that you seek for optimizations specific to cyclotomic fields. Many examples of manual computations are in Harold Edwards book Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory. However, I don't recommend spending much time on such hand calculations since what little insight can be gained from such can be gained much quicker using software. Nowadays all experimental number theorists employ computer vs. manual computations. It allows one to gather much more substantial empirical evidence, e.g. look up the Cohen-Lenstra heuristic on class groups. $\endgroup$ – Bill Dubuque Jul 28 '12 at 2:50
  • $\begingroup$ I agree that a computer should be used in experimental number theory. However, I'm more interested in the algorithms than experimental number theory. I apologize if I gave you an impression otherwise. $\endgroup$ – Makoto Kato Jul 28 '12 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.