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
On 4/4/14 12:56 AM, Dima Pasechnik wrote:
On 2014-04-03, Ursula Whitcher <whitc...@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.
--
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+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
