# Computing a minimal sublattice containing two other sublattices, GCD of a lattice

I've been trying to read a paper regarding the analogue of a GCD for lattices, but I'm not sure I understand how to decipher this notion. This is given in Section 3.1 when the author discusses the 'height' of a substitution.

Let $$\Gamma=\mathbb{Z}^d$$ be the standard lattice. Given two sublattices, $$\Gamma_1,\Gamma_2\subseteq \Gamma$$, the GCD of the two lattices is the smallest lattice $$\hat{\Gamma}\subseteq \Gamma$$ containing both $$\Gamma_1$$ and $$\Gamma_2$$.

From what I understood, when $$\Gamma=\mathbb{Z}$$, one can relate a number $$n$$ to the lattice by $$\Gamma(n):=\{ m\in \mathbb{Z}: m=k\cdot n \quad \text{for some} \; k\in \mathbb{Z} \}.$$

Then the GCD of the lattices $$\Gamma(n_1)$$ and $$\Gamma(n_2)$$, is the lattice $$\Gamma\big( \gcd(n_1,n_2) \big)$$.

However I understand relatively well how to find out what the gcd is for a pair of numbers by the Euclidean algorithm, but can\is there an analogue for this notion in lattices of full rank? Is there a way to find a GCD of two lattices by some basic manipulation of their basis?

• what paper would that be? Commented Mar 16, 2023 at 17:56
• @WillJagy The paper is "Multidimensional constant-length substitution sequences" by Natalie Priebe Frank, and the definition is given in section 3.1. I'm trying to understand how to compute this new lattice for examples I am interested in. Commented Mar 16, 2023 at 18:09

For any lattice, we can generally define a canonical form for its basis in the Hermite normal form. It is an analogue of reduced echelon form for vectors over $$\mathbb Z$$. Then, finding a canonical basis for $$\hat \Gamma$$ seems to be the same as finding the Hermite normal form for the union of bases of $$\Gamma_1$$ and $$\Gamma_2$$.

Algorithmically, you can reduce any basis to the Hermite normal form in a way that is very similar to the Gauss method for matrices over $$\mathbb R$$, but you use Euclidean algorithm instead of division to get the GCD on the leading entries in every row.

So, if you have a two rows

$$\begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \end{pmatrix},$$

you can perform the extended Euclidean algorithm on $$a_{11}$$ and $$a_{21}$$, repeating the operations on the whole rows, until one of them is equal to $$\gcd(a_{11}, a_{21})$$, and the other to $$0$$. After that you do the same for other columns, until the Hermite normal form is achieved. This approach allows to generalize Gauss method to any Euclidean domain.

• Thank you for your answer. So if, for example, I have a lattice $\Gamma_1=m_1\mathbb{Z}\oplus ...\oplus m_d\mathbb{Z}$ and $\Gamma_2 = p_1\mathbb{Z}\oplus ... \oplus p_d\mathbb{Z}$, the GCD lattice should be $\hat{\Gamma}=\gcd\{m_1,p_1\}\mathbb{Z}\oplus ...\oplus \gcd\{m_d,p_d\} \mathbb{Z}$? Commented Mar 31, 2023 at 11:54
• And for lattices $\Gamma_1,\Gamma_2\subseteq \mathbb{Z}^d$, with basis $(a_1^{(1)},...,a_d^{(1)}),...,(a_1^{(m_1)},...,a_d^{(m_1)})$ and $(b_1^{(1)},...,b_d^{(1)}),...,(b_1^{(m_2)},...,b_d^{(m_1)})$ accordingly, the GCD lattice should be $\hat{\Gamma}=c_1\mathbb{Z}\oplus... \oplus c_d \mathbb{Z}$, with $c_j=\gcd\{ a_j^{(1)},...,a_j^{(m_1)},b_j^{(1)},...,b_j^{(m_2)} \}$? Commented Mar 31, 2023 at 12:03
• The first claim seems to be correct, if I understand the notation correctly. The second one doesn't seem true, though... E.g. consider the lattice in $\mathbb Z^2$ with the basis $\left\{ \begin{pmatrix}1 \\ 2 \end{pmatrix},\begin{pmatrix}2 \\ 0 \end{pmatrix} \right\}$ and its gcd with itself? Commented Mar 31, 2023 at 17:50
• Yes, in hindsight I understand it should be incorrect. Thanks again. Commented Mar 31, 2023 at 18:57