Thanks, David -- a very clear and (as) concise (as possible) account! John
On 4 April 2014 09:34, David Kohel <[email protected]> wrote: > 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 <[email protected]> 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-nt" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send an email to [email protected]. > Visit this group at http://groups.google.com/group/sage-nt. > > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-nt" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send an email to [email protected]. Visit this group at http://groups.google.com/group/sage-nt. For more options, visit https://groups.google.com/d/optout.
