Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\Lambda$ be an $n$ dimensional sublattice of the integer lattice $\mathbb{Z}^n$. The quotient $\mathbb{Z}^n/\Lambda$ has order $\sqrt{\det{\Lambda}}$.

What is the best/standard way to compute a set of coset representatives for this quotient?

Edit: I initially forgot to take the square root of $\det{\Lambda}$, which is likely the reason for KCronrad's initial comment.

share|improve this question
    
Pedantic point: the quotient has order the absolute value of the determinant. –  KConrad May 12 '10 at 3:02
1  
Hi, Robby. If you have a Z-basis for the lattice, can you use a "lower-left" rule on the fundamental parallelopiped spanned by the basis? Meaning the points of Z^n internal, then on lower left faces. I don't know, I just made it up. –  Will Jagy May 12 '10 at 3:02
4  
One thing you might try to do is find a basis e_1,...,e_n of Z^n and positive integers a_1,...,a_n such that a_1e_1,...,a_ne_n is a basis of your lattice. Then Z^n/Lambda is represented by sums c_1e_1 + ... + c_ne_n with c_i running from 0 to a_i - 1. A suitable normal form associated to any matrix whose columns are a known basis of the lattice should let you read off what the a_i's (and e_i's?) are. –  KConrad May 12 '10 at 3:04
1  
It might help if you explain how you are actually being "given" the lattice: as the solution space to a system of linear equations, as the dual to some other lattice,... –  KConrad May 12 '10 at 3:07
2  
While (as Keith suggests) you can use the Smith normal form, you can also use the Hermite normal form. Find (using integer row operations) a generator matrix for $\Lambda$ which is upper triangular. If the diagonal entries are $d_1,\dots,d_n$ then coset reps are the $\sum a_i e_i$ where $0\le a_i < | d_i|$. –  Robin Chapman May 12 '10 at 7:01
show 4 more comments

1 Answer

up vote 3 down vote accepted

As KConrad suggested (why only in the comments?), Smith's normal formal is your best bet. Its running time is insensitive to $m=|{\mathbb Z}^n/\Lambda |$ (unless you need to use arbitrary long entries in your matrix) and behaves as $n^3$.

You may also try coset enumeration, whose running time is usually unbounded but may be bounded in this case by something like $(mn)^2$.

share|improve this answer
    
Well, I guess you get the brownie points then :) –  Robby McKilliam May 12 '10 at 9:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.