Let $\Lambda \subset \mathbb{Z}^n$ be a proper sublattice (so that $\Lambda \ne \mathbb{Z}^n$). We say that $\Lambda$ is cyclically generated if there exists a matrix $M \in \text{GL}_n(\mathbb{Z})$ and an element $\mathbf{u} \in \mathbb{Z}^n$ such that $\Lambda$ is equal the $\mathbb{Z}$-span of $\{\mathbf{u}, M \mathbf{u}, M^2 \mathbf{u}, \cdots \}$. Is it true that all proper sublattices are cyclically generated? If so, how would one prove this, and if not, what's a counterexample?
$\begingroup$
$\endgroup$
11
asked Jun 19, 2020 at 20:16
-
3$\begingroup$ I'm pretty sure the answer is yes, but my solution seems inelegant. Specifically: we can assume WLOG that the sublattice is generated by elements that are multiples $d_i \vec{e}_i$ of the standard basis vectors, and such that $d_1 | d_2 | \dots | d_n$. Then we can choose $M$ to be bidiagonal with $1$ on the diagonal and $\frac{d_{i + 1}}{d_i}$ below the diagonal, and $d_1 \vec{e}_1$ will be cyclic. $\endgroup$– user44191Commented Jun 19, 2020 at 22:20
-
1$\begingroup$ @StanleyYaoXiao You can make such an assumption because $\Lambda = A \Lambda'$ for some $A \in GL_n(\mathbb{Z})$ and $\Lambda'$ of the form specified; if $M', u'$ are a cyclic pair for $\Lambda'$, then $u := Au', M := A M' A^{-1}$ is a cyclic pair for $\Lambda$. And such an $A$ and $\Lambda'$ are guaranteed by Smith normal form. $\endgroup$– user44191Commented Jun 19, 2020 at 22:30
-
1$\begingroup$ @StanleyYaoXiao It's worth mentioning that the simple case of $M$ being a suitable permutation matrix ("cyclic rotation operator") leads to the case of cyclic lattices, which are known to not include all lattices. One can generalize the notation of cyclic lattices to ideal lattices, where I believe $M$ is the companion matrix of some polynomial, and again gets a strict subset of all lattices. $\endgroup$– Mark Schultz-WuCommented Jun 19, 2020 at 23:45
-
1$\begingroup$ @Mark fascinating! I didn't know the notion of 'ideal lattices' have been developed. If you have more references on them please let me know, perhaps via email if you don't mind. $\endgroup$– Stanley Yao XiaoCommented Jun 19, 2020 at 23:52
-
1$\begingroup$ If you send $M$ to $g Mg^{-1}$ and $u$ to $gu$ then the matrix $N$ whose columns are $u, Mu, M^2u,\dots, M^{n-1} u$ a becomes $g N$. That gives you the row operations. $\endgroup$– Will SawinCommented Jun 20, 2020 at 0:12
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
Some standard latticework allows us to write $\Lambda = \text{im}(A)$ for some $n$ by $n$ matrix $A$ (with nonzero determinant). Using Smith normal form, there are some $U, V \in GL_n(\mathbb{Z})$ such that $UAV = D$, where $D$ is a diagonal matrix with diagonal elements $d_1 | d_2 | \dots | d_n$.
Write $\vec{e}_i$ for each of the standard basis vectors. Then let $\vec{u} := U^{-1} d_1 \vec{e}_1$, and let $M := U^{-1}BU$, where $B$ is the bidiagonal matrix with all $1$s on the diagonal, and $\frac{d_{i + 1}}{d_i}$ on the subdiagonal. Note that $det(B) = 1$, and so $B \in GL_n(\mathbb{Z})$; correspondingly, so is $M$. I claim that $(\vec{u}, M)$ is a cyclic pair for $\Lambda$.
Proof: Write $\vec{v}_i := U^{-1} d_i \vec{e}_i$ for each $i$. Note that $\vec{u} = \vec{v}_1$. Then each $\vec{v}_i \in \text{im}(U^{-1}D) = \text{im}(U^{-1}DV^{-1}) = \text{im}(M) = \Lambda$; further, it's not hard to see that they generate $\Lambda$ (by the same reasoning taken backwards).
We can check that $M \vec{v}_i = U^{-1}BU U^{-1} d_i \vec{e}_i = U^{-1} B d_i \vec{e}_i = U^{-1} (d_i \vec{e}_i + d_{i + 1} \vec{e}_{i + 1}) = \vec{v}_i + \vec{v}_{i + 1}$ for $1 \leq i < n$. Noting the base case that $\vec{v}_1 = \vec{u}$, we can use induction to see that $\vec{v}_{i + 1} = M \vec{v}_i - \vec{v}_i \in \text{span}(\{M^j \vec{u}\}_{j = 0}^i)$. As the $\{\vec{v}_i\}$ are a generating set, $\text{span}(\{M^j \vec{u}\}_{j = 0}^{n - 1}) = \Lambda$, and we are done.
