1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Pedantic point: the quotient has order the absolute value of the determinant. $\endgroup$
    – KConrad
    May 12, 2010 at 3:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – Will Jagy
    May 12, 2010 at 3:02
  • 4
    $\begingroup$ 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. $\endgroup$
    – KConrad
    May 12, 2010 at 3:04
  • 1
    $\begingroup$ 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,... $\endgroup$
    – KConrad
    May 12, 2010 at 3:07
  • 2
    $\begingroup$ 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|$. $\endgroup$ May 12, 2010 at 7:01

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Well, I guess you get the brownie points then :) $\endgroup$ May 12, 2010 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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