1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ what paper would that be? $\endgroup$
    – Will Jagy
    Commented Mar 16, 2023 at 17:56
  • $\begingroup$ @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. $\endgroup$ Commented Mar 16, 2023 at 18:09

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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}$? $\endgroup$ Commented Mar 31, 2023 at 11:54
  • $\begingroup$ 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)} \}$? $\endgroup$ Commented Mar 31, 2023 at 12:03
  • $\begingroup$ 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? $\endgroup$ Commented Mar 31, 2023 at 17:50
  • $\begingroup$ Yes, in hindsight I understand it should be incorrect. Thanks again. $\endgroup$ Commented Mar 31, 2023 at 18:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .