Project description

There could be Lattice_generic class that derives from the existing FreeModule. It would act as the base for arbitrary R-lattices, where R is a ring in some field K and the lattice is over a K-vector space. Deriving from Lattice there would be a class LatticeZZ that represents general Z-lattices (with integer coefficients). An even more specific class could be Lattice_embedded_in_RR that deals with lattices embeddable in RR^n. This would be the class where most algorithms that are currently planned would be implemented. Lattice_embedded_in_RR would store the base of the lattice as a matrix. If most algorithms deal with special cases for 2-dimensional lattices, it could make sense to introduce another specialization Lattice_embedded_in_RR2 (deriving from Lattice_embedded_in_RR) for speedups.

A factory function Lattice could return an instance of the appropriate concrete class, given either a matrix representation of the base of the lattice, a quadratic form, or an order in an algebraic number field (lattices via the Minkowski map --> geometry of numbers).

To find a "good" base of a lattice, the Lenstra-Lenstra-Lovász (LLL) algorithm can be used. To use it over rational and especially real numbers, Ticket #12051 has to be resolved. There are already quite elaborated ideas on how to do this, so this would be a reasonable first step. Maybe the implementation can even be extended further to deal with real interval arithmetic, too.

To calculate vectors of short length in a lattice, the Fincke-Pohst algorithm can be implemented. It is described in the paper "Improved methods for calculating vectors of short length in a lattice, including a complexity analysis" by U. Fincke and M. Pohst (J. Math. Comp 44, 1985). It can be implemented in two variants, one returning all vectors of a given maximum length, and one generating shortest vectors after another (using Python's yield to create a generator that can be iterated over). There is an existing function qfminim in PARI that implements Fincke-Pohst; depending on benchmarks, it might be used, it will however not be possible to get a generator function out of it, which will require a Python or Cython implementation.

Calculations of lattice invariants (e.g. the discriminant) should be straight-forward. This could be realized in the more general LatticeZZ class. More advanced invariants such as the theta series require Fincke-Pohst to already be implemented.

A core part of the project would be the calculation of the Voronoi cell of a lattice. There are many algorithms that calculate Voronoi decompositions, but few are specifically targeted towards the special structure of lattices. The diamond-cutting algorithm is one of them and would be a reasonable choice for the task (paper "Computing the Voronoi cell of a lattice: the diamond-cutting algorithm" by E. Viterbo and E. Biglieri, IEEE Trans. Information Theory 42, 1996), but other algorithms specifically targeted to special cases could be considered as well. The implementation could use existing functions to deal with half spaces in Sage, possibly also including visualizations of them.

Computing the closest lattice point given a vector in RR^n could be implemented using "brute-force search" in a very first step and for the most general case. A more advanced method can use the Voronoi cell (paper "A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations" by D. Micciancio, P. Voulgaris, Proc. 42nd ACM Symp. Theory of Comput., 2010), an approach that might prove useful for other problems as well. Even more specialized algorithms not using the Voronoi cell could be implemented optionally.

All algorithms (specifically Fincke-Pohst, Voronoi cell, closest lattice point) might benefit from an implementation in Cython. Whether this is necessary will be decided after doing benchmarks with pure-Python implementations.

Further optional extension could deal with lattices over Dedekind domains. Most importantly, this would involve implementing support for working with modules over such domains via pseudo-bases. This would, for example, be useful for ideal arithmetic in quaternion algebras.