Project III 2022-23
Supervised by Dan Evans
Lattices and the Geometry of Numbers
Here’s an easy-looking question: what’s the largest possible area of a convex, centrally symmetric region \(\Omega\subset\mathbb{R}^2\) where the only point in \(\Omega\) with integer coordinates is the origin? (By convex, we mean the line segment connecting any two points \({\bf a}\), \({\bf b}\in\Omega\) is also contained in \(\Omega\) and by centrally symmetric we mean \({\bf a}\in\Omega\) if and only if \(-{\bf a}\in\Omega\).)
A first guess might be the nicest symmetric convex shape, i.e. all points \((x,y)\) with \[x^2+y^2<1\] which we all know has area \(\pi\approx 3.14\).
Perhaps surprisingly, we can do better with a less symmetric shape. The ellipse on the right is given by \[x^2+xy+y^2<1\]
and with a little coordinate geometry shennanigans, we work out this has area \(2\pi/\sqrt{3}\approx 3.63\).
After a bit of thought, we quickly realise there’s a much more obvious guess - just draw the square of all points with coordinates strictly between \(-1\) and \(1\), giving area \(4\).
But we could also try the parallelogram on the right. This also has area \(4\) and maybe suggests how to prove this is indeed the maximum area. (Think about stacking \(2\times 2\) square tiles.)
And what if we try to avoid a different lattice rather than the integer lattice \(\mathbb{Z}^2\)? And what about the same question in higher dimensions?
The Geometry of Numbers is a subject, initiated by Minkowski, which considers the implications of this and similar questions concerning how a “discrete object” such as a lattice might intersect a “continuous object” such as a convex set. More generally, lattices occur in many areas across mathematics, such as crystallography, coding theory, cryptography, computational number theory, as well as some subjects that don’t begin with the letter c.
Here’s a selection of inter-related areas this project might consider:
Lattice point enumeration: for instance, Gauss’s Circle Problem considers how many pairs of integers \((x,y)\) satisfy \(x^2+y^2\leq r^2\). Intuitively, for large \(r\) this should be roughly the area of the circle \(\pi r^2\) since there’s one point per unit square. But how big is the error in this approximation? Along other lines, one can consider enumerating lattice points in polygons, leading to Pick’s Formula and higher dimensional analogues.
Integral quadratic forms: the Geometry of Numbers gives a way to understand quadratic forms, like \(x^2+y^2\) and \(x^2+xy+y^2\) above, or ones with more variables like \(w^2+x^2+y^2+z^2\). For instance, it gives neat proofs of Fermat’s theorem on sums of two squares and Lagrange’s four square theorem as well as more advanced results such as the 15 and 290 theorems.
Diophantine approximation: how well can one approximate irrational numbers with rational numbers? This is a very big subject and the Geometry of Numbers gives one approach.
Algebraic Number Theory: the ring of integers in an algebraic number field can be viewed as a lattice in a natural way and Minkowski’s theorem gives a nice way to approach them. In particular, this enables us to bound norms of ideals, show that ideal class groups are finite and determine the structure of unit groups. These results come up in Number Theory III and in this project we could develop the theory further.
Sphere packing. Finding the densest packing of non-overlapping equal circles in \(\mathbb{R}^2\) is quite a tough problem. It’s somewhat easier if we assume the centres of the circles are arranged in a lattice and Lagrange showed the hexagonal lattice is optimal in 1773. In higher dimensions, packing questions are notoriously difficult. A proof of the Kepler conjecture for spheres in \(\mathbb{R}^3\) only arrived in 1998 and very recently the same question has been spectacularly resolved in \(8\) and \(24\) dimensions. When the centres of the spheres are on a lattice, things are a bit more manageable but even so, few precise answers are known. Some of the best general bounds for high dimensions use ideas from the Geometry of Numbers.
The LLL algorithm. A lattice is the set of all integer linear combinations of a basis in a vector space. But there are many choices of basis which give the same lattice and some bases are better than others. The LLL algorithm reduces a given basis into one consisting of short, nearly orthogonal vectors (similarly to the Gram-Schmidt process). This is a remarkably useful thing to do and has many applications in areas such as algorithmic number theory and cryptanalysis.
Prerequisites and Corequisites
Elementary Number Theory II is essential. Number Theory III would also be highly useful for applications in Algebraic Number Theory and studying quadratic forms. Cryptography and Codes III could also be useful, depending on the direction you choose.
References
As well as the above Wikipedia links, some references include:
The Geometry of Numbers (library link) by Olds, Lax and Davidoff is a readable account covering some of the basic ideas as a starting point.
An Introduction to the Theory of Numbers (library link) by G. H. Hardy and E. M. Wright. One of the sacred texts in number theory, with a chapter on Geometry of Numbers.
An Introduction to the Geometry of Numbers (library link) by Cassels is the classic reference for the subject - not for the faint-hearted!
Roots to Research: a vertical development of mathematical problems (library link) by Sally and Sally contains a good chapter on Lattice point geometry.
Exploring the Number Jungle (library link) by Burger also contains a nice introduction in chapters 13 and 14.
Algebraic Number Theory and Fermat’s Last Theorem (library link) by Stewart and Tall. This is one of the standard references for Number Theory III and gives a very clear account of the applications in Algebraic Number Theory.
An Introduction to Mathematical Cryptography (library link) by Hoffstein, Pipher and Silverman. This book contains a lengthy chapter on applications of lattices in cryptography, including the LLL algorithm.
Contact details
If you have any questions, feel free to drop me a message at daniel.evans@durham.ac.uk