Jacques MARTINET To BILL & KARIM
January 25th, 2012
NOTE on some FUNCTIONS "qf..." which could be added to PARI.
PRELIMINARY REMARK. Besides GP-codes, I use external programs,
notably AUTO which gives generators of the automorphism group of an
integral lattice. The output needs more generators than in Aachen,
too bad ! Also the by-program for orbits has been lost. There are
many subtleties of Plesken-Souvignier, for instance the "fingerprint"
which orders conveniently the basis, sparing much time this way.
To have good programs for groups/orbits (and analogues for codes)
would be very interesting.
All what follows concerns Euclidean lattices -- but computers only
recognize quadratic forms! In practice one consider integral lattices
(<===> L \subset L^* <===> integral quad. forms;
sometimes only rationality is needed
(i.e., proportionality to an integral lattice).
Typically, the dual L^* of L is not integral except for unimodular L.
I generally replace L^* by L' with Gram matrix d1/a where a
is the Gram matrix for a basis of L over Z and d1 is the annihilator
of L^*/L. In my everyday calculation I make use of Batut's "Carac"
which outputs [det,[s(L),min L],[s(L'),min L'],[Smith(L^*/L)]] :
*****************************
{Carac(a) =
local(n,q,sm,k);
n=#a;q=qfsign(a);
if(q[1]1,[matdet(a),kn2(a),kn2(q/a),sm],[1,k=kn2(a),k,sm]));
}
*****************************
Bien su^r un tel folklore n'est peut-e^tre pas a` mettre dans PARI !
For short: {rlll(a) = local(u); u=qflllgram(a,1); u~*a*u;}
{diag(a)=vector(#a,k,a[k,k])}
FUNCTION 1. Even sublattice 1. Here is Batut's program which I have
================= updated and to which I have added a reduction
*****************************
\\ srp=sous-r\'eseau pair; LLL-reduced form: esl=even sub-lattice
{esl(a)=
local(d,n,k,b,u,c,v);
d=diag(a);n=length(a);
k=1;while((k<=n)&&(d[k]%2==0),k++);
if(k<=n,b=exch(a,1,k);
\\ exch(a,i,j);exchanges lines and columns i and j in an n X n matrix
d=diag(b);u=matid(n);u[1,1]=2;
for(k=2,n,if(d[k]%2,u[1,k]=1));c=u~*b*u,c=a);
v=qflllgram(c,1);
v~*c*v;}
*****************************
FUNCTIONs 1bis. Useful: besides the above exch(a,i,j), I have
an exchc (resp. exchr) acting ON columns (resp. rows)
FUNCTION 2. Even sublattice 2. It might be useful to produce a Gram matrix
================== preserving as far as we can the initial data
I suggest an esl2(a) running as follows:
local(n=#a,v=vector(n,i,a[i,i]%2,b,m);
if(v==0,return(a),b=a); THEN:
compute the largest m<=n s.t. v[m]=1;
if(m (m+1,...,n,m) on lines and columns, getting b;
Finally, for(i=1,m-1,replace b[i,] by b[i,]-b[n,]);return(b)
FUNCTION 3. Tensor products. (Helas, tout de mon cru.)
================
*****************************
{tensor(a,b) =
local(n1=#a,n2=#b,n=n1*n2,c);
c=matrix(n,n,i,j,0);
for(i2=1,n2,for(j2=1,n2,for(i1=1,n1,for(j1=1,n1,i=i1+n1*(i2-1);j=j1+n1*(j2-1);c[i,j]=a[i1,j1]*b[i2,j2]))));c;}
*****************************
FUNCTION 3bis. Exterior powers. LOST
================
N.B. This has some importance. EXAMPLE: the smallest degree of a
represention of O_8^+(2) (resp. Co_1) is 28 (resp. 276).
This can be obtained as Ext^2(\E_8), of degree 8,
(resp. Ext^2(Leech, of degree 24).
FUNCTION 3. Enlargement of a lattice. Data: L of dimension n by a Gram
========================= matrix a, and a Z/dZ-code C.
Outputs the lattice generated by the basis elements (e_i) and
the (\sum a_i e_i)/d when $(a_i) runs through the words of C.
FUNCTION 4. Vectors of given norm. Data: L of dimension n by a Gram
====================== matrix a.
Let f(m)=qfminim(a,m,0)[1]/2. Then one can calculate s(m)=f(m)-f(m-1),
then extract from qfminim(a,m,f(m))[3] the s(m) convenient terms.
(J'ai un code pour \c ca, mais autant que vous le fassiez bien
directement vous-me^mes.)
FUNCTION 5. Lattices modulo 2. (Perhaps less important.) To find
================== representatives for L mod 2L
having the smallest possible norm.
Theoretical basis: my paper at J. Algbra,
"Reduction Modulo 2 and 3 of Euclidean Lattices", and its
complement "__,II at Contemporary Math.
(On my homepage, "recent journal publications and preprints".)
1. Let m=min L. One needs to consider all norms N<=2m, and in this
range, x congr. y mod 2 ===> y=+-x or N(y)=N(x)=2m & y \perp x.
Thus there are $r<=n such vectors x_1,...,x_r of norm 2m vectors
congruent to a given x, and the system {x_i+-x_j, j\ne i}
is a root system of type D_r (scaled to norm m).
1bis. If m is odd (recall that L is integral), one needs all norms
up to 2m+1, and other congruences occur only among vectors of norm 2m+1
(at most 2m+2 such pairs).
3. Beyond m (or m+1 if m is odd), to test congruences with
vectors of norm N,N-4,..., and N, until one obtains 2^n-1 classes.
NOTE. FUNCTION 4 is useful, and so could be an efficient orbits program.
FUNCTION 5bis. Lattices modulo 3. ???
==================
NOTE. J'ai bosse' a` Luminy et jusqu'a` hier sur le cas des re'seaux
de racines mod 2 et 3 pour Marie-Jos\'e Bertin, a` propos de surfaces
K_3 et de leurs pe'riodes, en relation avec l'article de Niemeier
qui classe les re'seaux unimodulaires pairs de dimension 24.
FUNCTION 6. Re'seaux de racines (dans un re'seau entier donne').
===================
This is the part of the theory which interests those who classify
integral lattices, for which I have a program of Batut. These people
call "root lattice" an integral lattice which is generated by norm-2 vectors.
[Autre point de vue : voir FUNCTION 7.]
Theoretical basis:
1. (Eichler, Kneser). A Euclidean lattice is an orthogonal sum
of irreducible lattices (uniquely up to the ordering
of its irreducible components).
2. (easy). If L is integral and x\in L has norm 1, then
L=Z x\perp (x^\perp\cap L).
3. (Witt). A root lattice is an orthogonal sum of irreducible
lattices generated by root systems of type
A_m (m>=1), D_m (m>=4) or E_n (n=6,7,8).
Batut's outputs to "rs(a)" takes typically the form " 2A2 D4 I3",
which means that L contains A_2 \perp A_2 \perp D_4 \perp Z^3.
I send apart Batut's program.
REMARK. The root system may be larger, e.g B_n come with Z^n,
G_2 with A_2, ...
FUNCTION 7. The roots of a lattice. Nothing implemented, needs first
======================= theoretical considerations.
A root in a lattice L is a primitive vector r
(rm x, x\in l ===> m=+-1), such that the reflection along r
(that is, with respect to the hyperplane (R x)^\perp)
preserves the lattice.
(This is a root system in the sense of Old Nick Bourbaki, except that
we identify a space with its dual via a scalar product.)
One could ask to list the roots, or the roots systems, this time
no longer restricting ourselves to systems having a single norm.
THE (provisional) END