Timeline for Computing a set of coset representatives for $\mathbb{Z}^n / \Lambda$
Current License: CC BY-SA 2.5
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 12, 2010 at 20:41 | history | edited | Robby McKilliam | CC BY-SA 2.5 |
added 138 characters in body
|
| May 12, 2010 at 9:18 | vote | accept | Robby McKilliam | ||
| May 12, 2010 at 9:01 | answer | added | Bugs Bunny | timeline score: 3 | |
| May 12, 2010 at 8:59 | comment | added | Robby McKilliam | Thanks Robin! I realised this as I was reading about the Smith normal form. There exist polynomial time algorithms to compute the Smith and the Hermite normal forms so this certainly answers my question. | |
| May 12, 2010 at 7:01 | comment | added | Robin Chapman | 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|$. | |
| May 12, 2010 at 3:42 | comment | added | Robby McKilliam | However, you just made me realize that this probably has something to do with the Smith normal form. Thanks! | |
| May 12, 2010 at 3:41 | comment | added | Robby McKilliam | In particular cases (say when $\Lambda$ is a rectangular lattice) the solution is obvious. However, I don't really want to start making assumptions about $\Lambda$ , I want to know if there is an algorithm (preferably something fast, like $poly(n)|\mathbb{Z}^N/\Lambda|$) that works in all cases. I can think of an algorithm that works (I think it is similar to what Will is suggesting), but it requires a number of operations that is exponential in $n$, even if $|\mathbb{Z}^N/\Lambda|$ is polynomial in $n$. | |
| May 12, 2010 at 3:38 | comment | added | Robby McKilliam | @KConrad: $\det{\Lambda}$ is the determinant of the Gram matrix, it is always positive. | |
| May 12, 2010 at 3:07 | comment | added | KConrad | 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,... | |
| May 12, 2010 at 3:04 | comment | added | KConrad | 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. | |
| May 12, 2010 at 3:02 | comment | added | Will Jagy | 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. | |
| May 12, 2010 at 3:02 | comment | added | KConrad | Pedantic point: the quotient has order the absolute value of the determinant. | |
| May 12, 2010 at 2:41 | history | asked | Robby McKilliam | CC BY-SA 2.5 |