Practical applications of algebraic number theory?

Question

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.

Added:

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.

Added again:

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.

Answer 1

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.

Answer 2

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 ).

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

The Bellows Conjecture was not named after someone named Bellows, but after the physical device for pumping air. There are polyhedra that can flex if their faces are rigid but you let them bend along their edges, so the dihedral angles are not fixed. The Bellows Conjecture was that a polyhedron that can flex does not change its volume.

This was proved by Sabitov for spherical polyhedra, and by Connelly, Sabitov, and Walz in general in three dimensions, by showing that the volume is integral over an extension of the rationals by the edge lengths by considering the places of that field.

Answer 8

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 :)