# Practical applications of algebraic number theory?

I'm interested in learning about any applications, the more worldly the better*. Pointing to a nice reference on the number field sieve, for example, would be fine. However, let me mention one direction I would be especially grateful to learn about.

In my introductory course, I like to spend some time on the perspective that algebraic number theory is the study of sophisticated multiplications on $\mathbb{Q}^n$ (an algebraic number field $F$ of degree $n$) and on $\mathbb{Z}^n$ (the ring of algebraic integers in $F$). This is in part because I still find it amazing that a little bit of abstract algebra (of irreducible polynomials) enables us to construct such things systematically**. But I also believe at least half-seriously that this is the view through which the general public will gradually learn about algebraic numbers, until the time they're taught in primary schools several thousand years hence. After all, we have ourselves witnessed the remarkable ascent of multiplication on $\mathbb{F}_2^n$, a set whose initial practical use was entirely devoid of algebraic content, as a powerful tool for information processing.

After such grandiose reflection, I can't help but wonder: are multiplicative structures on $n$-tuples of integers provided by algebraic number theory already of some practical use? A superficial google search uncovered nothing. But surely, there must be something? I would love to be able to mention some examples to my students.

As I write, one class of examples occurs to me. Algebraic integers can be used to construct arithmetic groups, which I understand can be applied in a number of ways. Perhaps someone can comment knowledgeably on that. But something direct that could at least vaguely be explained in an undergraduate course would be even better.

Such was the depth of my ignorance that I didn't even know about number field codes until Victor Protsak pointed to them in his answer. Thanks to him, I stumbled upon a short survey by Lenstra. To get the gist of it, one need only read this quote:

'The new codes are the analogues, for number fields, of the codes constructed by Goppa and Tsfasman from curves over finite fields.'

The time-worn analogy continues to prosper.

In order to avoid misleading people with the word 'prosper,' I should say that Lenstra has many negative things to say about these codes. For example,

'If the generalized Riemann hypothesis is true our codes are, asymptotically speaking, not as good as those of Goppa and Tsfasman Also, the latter codes are linear and non-mixed.'

My original question still stands.

*I do not wish, however, to give the impression of a firm belief in the division between pure and applied mathematics.

** To appreciate this, one need only spend a little time on a direct approach using the multi-linear algebra of structure constants.

-
Community wiki? –  Qiaochu Yuan May 17 '10 at 6:32
Qiaochu: Done. –  Minhyong Kim May 17 '10 at 10:55
Keith: It's a pretty easy course I have in mind. Basic definitions; no local techniques; ending with computations of class groups. Perhaps the unit theorem if we have time. But the examples can require more background if necessary. Whatever comes up, I can try to process it into a form suitable for my course. –  Minhyong Kim May 17 '10 at 10:57
Unknown: I apologize in advance if this sounds like a dismissive question, but is it your impression that the reference you point to is serious science? It could well be, but I'm just asking out of ignorance and because Im too lazy to check. –  Minhyong Kim May 17 '10 at 20:09

Your requirements are quite stringent! As you know well, ANT is a couple of layers removed from "practice". In general, I find that the methods deriving from the development of algebraic number theory eventually lead to incomparably more applications than any of the standard ANT theorems themselves. Just a few examples that quickly spring to mind: Gauss reduction of quadratic forms → shortest lattice vectors → LLL; Dirichlet units → Minkowski geometry of numbers → convex geometry; class groups and unit groups → finitely generated abelian groups → (pick your favorite application of group theory, e.g. in abelian harmonic analysis). I would try to project this deeper idea over the immediate payoff. Also, unsurprisingly, "elementary" number theory presents more immediate applications, e.g. to cryptography and specifically, to primality testing and factorization.

But enough of philosophy! Here a few concrete applications:

1. Construction of codes and dense lattice packings using multiplicative groups of global fields by Rosenbloom and Tsfasman (Invent. Math. paper or see Tsfasman's survey "Global fields, codes and sphere packings").

2. Margulis arithmeticity theorem: not only are algebraic integers useful in constructing discrete groups, but after imposing certain conditions (an irreducible lattice in a higher rank semisimple Lie group), all of them arise in this way! These lattices have been used in constructing Ramanujan graphs and superconcentrators and to uniform distribution of points on spheres (admittedly, arithmetic of the field is rather secondary: you can get good constructions starting from a group over Z).

3. Lind's theorem on realizability of any Perron–Frobenius integer as the leading eigenvalues of a positive integer matrix. Since log λ is the entropy, this does have semi-practical consequences (cf the textbook of Lind and Marcus).

4. Lucas–Lehmer primality test, Lucas and Fibonacci pseudoprimes, Grantham's Frobenius test. This strides the border between elementary and algebraic number theory, which may actually be an advantage in an undergraduate class!

I'd be curious to know how do they jibe with your goals.

-
Very nice list! I like especially 1. The rest, as you point out, do not really make use of algebraic number theory in a sharp way for the applications. One of my motivations was in fact the perceived discrepancy between the possibilities for elementary number theory and even a little more machinery. –  Minhyong Kim May 17 '10 at 10:41
Thanks! Yes, 2 and 3 are there specifically to illustrate your dictum that "sophisticated multiplication on $Z^n$" is just the right structure to consider for some applications. Margulis arithmeticity, in particular, gives an amazing conclusion from seemingly weak hypotheses. –  Victor Protsak May 17 '10 at 19:52
Victor's remark about class groups and unit groups leading to general concepts about finite and f.g. abelian groups is a very good one. The unit groups were historically the first "abstract" examples of f.g. abelian groups, making Dirichlet's structure theorem for them a template for the general theory. Class groups were the first examples of finite abelian groups beyond modular arithmetic. I'm less confident about the direction Dirichlet units (1846) --> Geom. of Numbers (1890s). Minkowski may have been aiming at other goals, i.e., open problems at the time and not known theorems. –  KConrad May 17 '10 at 21:13
I love how we can consider this list a list of "practical applications". –  Samuel Reid May 13 '12 at 1:21

Algorithms for computing with real algebraic numbers (in particular, (i) computing the sign of an algebraic real A presented, for instance, as a pair of a minimal polynomial P $\in \mathbb{Z}[x]$ for A and an interval with rational endpoints containing A and no other real roots of P, and (ii) computing the sign of a polynomial evaluated at algebraic real numbers presented in form (i)) are critical components of some modern quantifier elimination based decision procedures for real algebra such as cylindrical algebraic decomposition. These procedures are used in a number of areas: formal verification of hardware, software and bioware (including control systems and other hybrid' systems with both discrete and continuous dynamics), robot motion planning, correctly displaying algebraic curves on computers, testing the stability of initial and initial-boundary value problems, and formalised mathematics.

--

[Some references on cylindrical algebraic decomposition (CAD)]

Caviness, B. F. and Johnson, J. R. (Eds.). Quantifier Elimination and Cylindrical Algebraic Decomposition. New York: Springer-Verlag, 1998. (The CAD bible' - Collins's festschrift.)

Collins, G. E. "Quantifier Elimination for the Elementary Theory of Real Closed Fields by Cylindrical Algebraic Decomposition." Lect. Notes Comput. Sci. 33, 134-183, 1975.

Collins, G. E. "Quantifier Elimination by Cylindrical Algebraic Decomposition--Twenty Years of Progress." In Quantifier Elimination and Cylindrical Algebraic Decomposition (Ed. B. F. Caviness and J. R. Johnson). New York: Springer-Verlag, pp. 8-23, 1998.

--

[Some references on applications of CAD: there are many, I only post a few]

(robot motion planning)

S. Lindemann and S. LaValle. "Computing Smooth Feedback Plans Over Cylindrical Algebraic Decompositions." In Proceedings of Robotics: Science and Systems, 2006.

(formal verification of systems)

M. Adlaide and O. Roux. "Using Cylindrical Algebraic Decomposition for the Analysis of Slope Parametric Hybrid Automata." In Proceedings of the 6th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, 2000.

(formalised mathematics)

A. Mahboubi, "Programming and certifying the CAD algorithm inside the Coq system." In Mathematics: Algorithms, Proofs. Volume 05021 of Dagstuhl Seminar Proceedings, Schloss Dagstuhl, 2005.

(display of algebraic curves)

D.S. Arnon. "Topologically reliable display of algebraic curves." SIGGRAPH Comput. Graph. 17, 3 (Jul. 1983), 219-227.

--

Also, many open problems in metric geometry actually fall within the theory of real closed fields (RCF), and thus can in principle be decided by the CAD algorithm. The issue is one of complexity. Due to Davenport-Heintz, it is known that real quantifier elimination is inherently doubly exponential in the dimension (number of variables) of the input formula. Thus, for the case of RCF, decidable in principle does not mean decidable in practice. Nevertheless, it is a fascinating state of affairs. Complexity aside, here are some examples:

All kissing problems for n-dimensional hyperspheres are in principle decidable by CAD and other real algebra decision methods.

Due to L. Fejes Toth, Kepler's conjecture is known to be equivalent to a single RCF sentence, and thus could be decided by CAD as well. In the formalisation of his proof of the Kepler conjecture, Thomas Hales has isolated a large collection of RCF sentences which appear as lemmata in his proof and which he believes should be amenable to specialised RCF decision methods. See T. Hales's A Collection of Problems in Elementary Geometry'' ( flyspeck.googlecode.com/files/collection_geom.pdf ).

-
Is there a good reference on these matters? –  Minhyong Kim May 17 '10 at 19:51
Hi, Minhyong. I've added a few references. I hope this helps! –  Grant Olney Passmore May 17 '10 at 22:16

Algebraic number theory is used in design theory, with numerous applications to statistics. See for instance B. Schmidt, Characters and cyclotomic fields in finite geometry, and T. Beth, D. Jungnickel, and H. Lenz, Design Theory, Vol. I, second edition.

-
That's interesting. Because I don't have access to a library right now, could I trouble you to confirm that algebraic numbers are used in an active way? One of the titles would indicate this. However, it's not clear that the key role is played by algebraic number fields rather than just finite fields, which I guess have been applied for a while to designs. As the other part of the title might suggest, cyclotomic fields could be coming up only as character values. This is also interesting of course, but perhaps the structure theory of the fields have only marginal importance? –  Minhyong Kim May 17 '10 at 19:49

Here are some references with applications. The first one is not about algebraic number theory but deserves to be consulted by anyone who wants to find a list of ways that simple concepts in number theory have a quasi-wide range of practical uses. The other second and third references are uses of actual algebraic number theory.

1. Schroeder's "Number Theory in Science and Communication" has many examples of ways in which elementary number theory can be applied (not just to cryptography).

2. Mollin's book "Algebraic Number Theory" is a very basic course and each chapter ends with an application of number rings in the direction of primality testing or integer factorization.

3. Chapter 16 of Washington's book on cyclotomic fields (2nd ed.) starts with a section on the use of Jacobi sums in primality testing.

Suitable references to the role of primality testing and integer factorization in cryptography can convey the practical interest in such methods.

-
Yes, although it's not algebraic number theory, I really liked Schroeder's book. I agree that 2 and 3 should definitely be in this collection. –  Minhyong Kim May 17 '10 at 22:28

Do diophantine equations count? Examples abound, but I'm particularly fond, for pedagogical reasons, of one in Stark's An Introduction to Number Theory. He "solves" $x^2+47=y^3$ by assuming that arithmetic with numbers of the form $a+b\sqrt{-47}$ is just like arithmetic with integers, and finds the only solutions are $x=\pm500$, $y=63$. Then he points out that somehow we've missed $x=\pm13$, $y=6$. That motivates a discussion of unique factorization, etc.

-
Thanks for your input. But I have say, not really. Applications within pure mathematics itself are as numerous as the grains of sand on the beaches of Syracuse! –  Minhyong Kim May 17 '10 at 10:36

I guess that the most special number field sieve (working with a quadratic or cubic number field) can definitely be explained at a very elementary level. Pollard's first example used, if I recall it correctly, the field generated by a cube root of 2.

-

It has been already mentioned by Victor Protsak the existence of application to coding theory (Tsfasman's & K works). But let me mention yet another application to this field which is more recent and being under development at the present.

One may see papers by F. Oggier, G. Rekaya-Ben Othman, J.-C. Belfiore, E. Viterbo: e.g. this one : http://arxiv.org/abs/cs/0604093.

Unfortunately I do not fully understand the idea but let me give brief comments.

Consider multi-antenna transmission and receiver (MIMO for short http://en.wikipedia.org/wiki/Mimo ) , this means we have vector (x1...x_{transmit antenna number} ) and received vector Y=(y_1... y_{receive antenna number} ).

The received signal is Y= H X + noise. where H - matrix of size receive antenna by transmit antenna, noise - is random noise vector.

The nature of our signal is discreete so we should choose some LATTICE in C^{transmit antenna} and actually sent signal is one the lattice points - not an arbitrary vector. Of course, it is not full lattice but truncated to some finite area due to power constraint.

So the problem is to select what kind of lattices are suitable for the best quality of transmission ? Moral of these papers that we should choose lattices of algebraic integeres in specifically selected algebraic fields like $Z(\sqrt n_1, \sqrt n_2) \subset Q(\sqrt n_1, \sqrt n_2)$.

PS

Actually I am significalntly over-simplifying the situation. We should also take into account time dimension. The the actual space is NOT C^{transmit antenna}, but C^{transmit antenna * N}, where N is block length which we choose. This is related to the so-called "space-time codes" http://en.wikipedia.org/wiki/Space%E2%80%93time_block_code

PSPS The story of space time codes starts from the so-called Alamouti code http://en.wikipedia.org/wiki/Space%E2%80%93time_block_code#Alamouti.27s_code

Looking on the matrix in Wikipedia you can immediately reconginze the quaternions presented by the 2x2 complex matrices. Let me mention that it is mandatory for implematation in 3G smartphones. So we can say that smartphones know quaternions :)

If these works will be succussful every smartphone will "know" algebraic number theory :)

-
Frédérique Oggier : Algebraic methods for channel coding. Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL, no 3182 (2005), may be a good starting point to read biblion.epfl.ch/EPFL/theses/2005/3182/EPFL_TH3182.pdf or library.epfl.ch/theses/?nr=3182 –  Alexander Chervov May 14 '12 at 11:41

My questions the other day were related to working with algebraic numbers. The problem I am working on has practical applications in coding theory, in astronomy and in radar work.

-