28 views

Skip to first unread message

Apr 3, 2014, 10:28:41 AM4/3/14

to SAGE devel, sage-a...@googlegroups.com, sage-nt

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.

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.

Apr 3, 2014, 6:56:11 PM4/3/14

to sage-a...@googlegroups.com, sage-...@googlegroups.com, sag...@googlegroups.com

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

> 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.

>

>

>

> 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
>

> 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).

>>

>>

> 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.

>

Apr 4, 2014, 4:34:57 AM4/4/14

to sage-a...@googlegroups.com, sage-...@googlegroups.com, sag...@googlegroups.com

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

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

Apr 4, 2014, 8:40:24 AM4/4/14

to sage-...@googlegroups.com, martinr...@googlemail.com, sage-a...@googlegroups.com, sag...@googlegroups.com

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

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu