Re: [sage-devel] Lattice, RealLattice, ComplexLattice, VectorSpaceLattice: a bikeshed question

[John Cremona]

There are different objects all called lattices in different contexts.
Let's start by acknowledging that we are not talking about some kind
of poset -- though there will be others for whom that is what the word
"lattice" means.

Following Lenstra (see his article on Lattices in the Buhler &
Stevenhagen MSRI book on Algorithmic Number Theory) a lattice is a
discrete subgroup of a euclidean vector space. That could be either
R^n or C^n: both really do arise (for example the period lattice of an
elliptic curve is a lattice in C). Given this definition one would
expect a lattice L of rank r in an ambiant vector space V of dimension
n to be given by r independent elements of V (if V is complex they
only have to be R-linearly independent) so by a d x r matrix A (if we
identify V with R^d or C^d) whose columns span L.

Or one could give the Gram matrix G (A^t * A (in the real case), which
is real and positive definite. You definitely need to be able to
define a lattice just by its Gram matrix; theoretically one can go
from such a G via a factorization G=A^t * A to a basis representation
(not unique).

But since a lattice is a free abelian group of rank r and hence
isomorphic (as a group) to Z^r it is also common to take the
underlying set as just Z^r and then give it the required lattice
structore by defining a (positive definite) quadratic form on Z^r.
This need not be integer-valued, of course, and if we call its Gram
matrix G we can get back to a basis definition of the lattice as
before.

All this is given in detail in Lenstra's article (see especially
section 4, on Represeting Lattices).

I would hope that our Lattice class could allow for all of these.
Different algorithms (e.g. different forms of LLL) require integers
bases, or not, or work on Gram matrices, and I would like it if our
class converted between these as needed.

that's enough for now: of course, number theorists would also use
"lattice" for a generalization of the above, e.g. if R is an integral
domain contained in a field K then an R-submodule of K^d would be
called an R-lattice in the vector space V=K^d if it satisfied some
easy conditions. In the previous case we had (R,K) = (Z,R) but
(Z_p,Q_p) is also used a lot theoretically.

I hope that Martin does not already regret asking thew question! I
recommend airing this in sage-algebra and sage-nt so have copied them
in.

John

PS Martin, in your patch you show your age by the lines

+# Sage: System for Algebra and Geometry Experimentation
+#
+# Copyright (C) 2014 Martin Albrecht <martinr...@googlemailc.om>
## NB typo here!


On 3 April 2014 14:58, Martin Albrecht <martinr...@googlemail.com> wrote:
> Hi all,
>
> I have a "what colour should the bike shed be" question. At
>
> http://trac.sagemath.org/ticket/15976
>
> a few new classes are introduced for lattices as discrete subgroups of some
> vectors spaces. The only one somewhat function is the one over the integers,
> aptly called IntegerLattice. However, while we're at it, we might as well
> introduce a base class for other such lattices as well (and a general
> constructor). How should it be called?
>
> Suggestions so far:
>
> Lattice -> to general?
> RealLattice -> but people might want complex lattices as well
> VectorSpaceLattice -> what do people think?
>
> Suggest away!
>
> Cheers,
> Martin
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[Dima Pasechnik]

On 2014-04-03, Ursula Whitcher <whit...@uwec.edu> wrote:

>
>
> On Thursday, April 3, 2014 9:28:41 AM UTC-5, John Cremona wrote:
>>
>>
>> Or one could give the Gram matrix G (A^t * A (in the real case), which
>> is real and positive definite. You definitely need to be able to
>> define a lattice just by its Gram matrix; theoretically one can go
>> from such a G via a factorization G=A^t * A to a basis representation
>> (not unique).
>>
>>

> There are situations where it is very useful to allow Gram matrices which
> are *not* positive definite.
I suppose you mean to say that one allows non-Euclidean scalar
products.
(for many people here a Gram matrix is a matrix of form VV^T, and may
sound confusing...)

> In particular, both the negative definite and
> indefinite cases arise when doing computations in algebraic geometry
> involving K3 surfaces. There are some nice results of Nikulin on existence
> and uniqueness of lattice embeddings that only apply to the indefinite case.

they also arise in the theory of reflection groups, cf e.g.
http://en.wikipedia.org/wiki/II25,1

This brings up yet another suggestion for the name of the class:
"InnerProductSpaceLattice" :-)

>
> Anyone want to team up with me and spend a week in July (the first
> month I realistically have time, sigh) implementing some of this?


>
> --Ursula.
>

[David Kohel]

Dear all,

First of all, in the context of modules there should be no confusion about
the terminology "lattice" (as opposed to a lattice poset in combinatorics).
There is little doubt that modules with bilinear pairings are ubiquitous in
mathematics, but precisely that poses problems with differing conventions
for the differing domains of mathematics.

Before someone goes too far in reinventing the wheel, I should point out
that a datastructure for lattices already exists since 2007-2008. Around
this time (at a Sage days), I think I also looked into linking in some
lattice
reduction algorithms (LLL & BKZ), but they never migrated upstream to Sage.

The concept of a quadratic module (or bilinear module), encompasses
definite, indefinite, isotropic and non-isotropic "lattices", whereas the
terminology lattice depends on the interests of the author and is often
restricted to positive definite quadratic modules, possibily with a fixed
embedding in RR^n.

A = MatrixSpace(ZZ,2)([[1,0],[0,-1]])
M = FreeModule(ZZ,2,inner_product_matrix=A)
M.ambient_vector_space()
B = M.basis()
M.gram_matrix()
M0 = M.submodule([ M.0 ])
M1 = M.submodule([ M.1 ])
M0.inner_product_matrix()
M0.gram_matrix()

The definitions of inner product matrix and Gram matrix are that
the inner product matrix A is the Gram matrix of the ambient module
(supposing that a module M is embedded in and "ambient" free
module R^n), and the Gram matrix is the V A V^t with respect to
the basis of M. Assuming R is an integral domain with field of
fractions K, then the ambient vector space is the tensor product
with K (with canonical embedding), which is a quadratic space.
Inside this space one can carry out intersections and sums of
(sub)lattices.

The FreeModule constructor gives the default Euclidean inner
product matrix (the identity):

sage: M = FreeModule(ZZ,3)
sage: M.inner_product_matrix()
[1 0 0]
[0 1 0]
[0 0 1]
sage: L = M.submodule_with_basis([ M([1,1,1]), M([1,-1,0]), M([1,0,-1]) ])
sage: L.gram_matrix()
[3 0 0]
[0 2 1]
[0 1 2]

So there will be no surprises if a user creates a FreeModule without
specifying an inner product. It comes with the default "dot product"
as inner product.

There is a convention problem of where to divide by 2 (when 2 is not a
zero divisor) in this construction. If q: V -> V is a quadratic form, then
one can define <u,v> = q(u+v) - q(u) - q(v) in which case one recovers
q(u) = 1/2 <u,u>. Other authors prefer to put the 1/2 in the definition
of <u,v> so that q(u) = <u,v>. If one works only with the bilinear form
<u,v> determined by v A v^t, then then we avoid addressing this
choice of convention. (However, if one defines a "norm" or "length",
this is usually defined as ||u|| = sqrt(q(u)), and the normalization
convention changes this value by a sqrt(2).)

At present, I personally don't think there is a need to introduce new
datatypes to represent the various quadratic modules (over PID's) or
quadratic spaces (over fields). Someone could just write a "Lattice"
function which makes a call to FreeModule with the correct syntax,
so that users find the existing constructor.

The question of categories arises, however, since the usual choice
of morphisms of quadratic modules (and quadratic spaces) are
the isometries (morphisms preserving the inner product). There
should be a category of quadratic modules in which it is checked
that the morphisms preserve this additional structure.

In my view, the functionality that is missing is determining if a given
ZZ-module (extend to your favorite subrings of RR if you like) is
(positive) definite, isotropic, etc.,

L.is_definite()
L.is_positive_definite()
L.is_isotropic()

then the application of LLL, BKZ, or other reduction algorithms
(the output should be a module with basis having the new reduced
basis, as a submodule of the input module). There are also
indefinite versions of LLL which could apply to indefinite lattices.

Note that the pari LLL function doesn't return the LLL reduced
basis, but the transformation matrix U determining the isometry
with the LLL reduced object. This is linked in somewhere in
Sage, and the output is not what one expects.

Regarding the various combinations of rings, one might define
concepts of "exact" and "integral" lattices. Here being exact is
an implementation-side question, and there are two:

1. Is the specification of the basis elements exact (e.g. the basis
elements of M might be given in RR^n to some approximation
with precision). An example is the Minkowski lattice of an
order or ideal in a number field. The coordinates do not have
exact representations, but the inner product [matrix] is exact
[= the identity].

2. Is the specification of the pairing (e.g. in a real field) exact?
An example is the height pairing on an elliptic curve E/K (= a
number field); on E(K)/E(K)_tors, the height is known only to
some fixed precision.

The two examples given above allow the precision to be extended
at will (for some cost), but in both, testing for zero in the codomain
of the inner product is not an exact operation. The algorithmic
functionality needs to be suitably adapted to these cases (which is
an argument for different subclasses). As a case in point, in the
first setting, given an element in RR^n close to an element L, its
membership in L can not be exactly decided.

Regarding integral, even in the setting of exact lattices over R
with exact inner products, there is the question of whether the
image of the pairing is in K (the field of fractions) or R, and
whether this is just due to the convention of the factor 1/2
between inner product and quadratic form.

I should also point out that there is code for quadratic forms,
but the conventions are very local, and even if it represents
an equivalent category, I don't think much can be recycled
for use with quadratic modules.

In the longer view, there would be significant interest in
Hermitian lattices and lattices over number rings R (which
are not necessarily free modules) or group rings, etc., in
which an ZZ-bilinear inner product may satisfy certain
compatibility operations with the number ring or group
(e.g. being R-linear with respect to a choice of embedding
in RR or the group acting by isometries).

Cheers,

David

[David Kohel]

Hi Martin,
 

I asked about it because it seems no one seems to have touched those data
structures in years and because I failed to interact with it the way I wanted.
In my world I think of a lattice as given by a basis and my bases are over the
integers. I failed to construct that. However, revisiting that, it seems I was
an idiot and I merely need:

sage: ZZn = FreeModule(ZZ, 10)
sage: B = random_matrix(ZZ, 10, 10) # <- my basis
sage: L = ZZn.submodule(B)
 
I guess I could move my new class (specialising to ZZ) at
http://trac.sagemath.org/ticket/15976 to fit into there and add a short-hand
constructor?

Probably the constructor you want (to preserve the data of B) is:

sage: L = ZZn.submodule_with_basis(B)

and the LLL or BKZ reductions should use this constructor to
return a submodule (equal to the original) with the preferred
reduced basis.

I had hoped that someone would pick up the quadratic module
class and add functionality.  In Magma the lattice class was (in
my view) too rigid in not admitting lattices which were anything
but positive definite, and -- even over the integers -- in order to
implement local invariants (over ZZ_p) using the general free
modules class.  This would be fine if lattices were a special
subtype of the general class, but they don't (or didn't) behave
the same as other free modules.

--David