Unique sub-lattices of a given volume

Question

I have an interesting problem from my research that I have been struggling to solve. I am not a mathematician so please bear with me. The question is as follows:

The way I think about a lattice is as an array of points. So I have a three-dimensional lattice of integers, i.e. the basis vectors are along the $x$, $y$ and $z$ axes and are of length 1. I want to compute the unique sub-lattices that have a volume that is $N$ times the volume of the unit cell.

If the question is not entirely clear, I have an example for a two-dimensional lattice for which I was able to find solutions when $N$ is reasonably small. So, suppose I start with a 2D lattice - i.e. the basis vectors are $(1,0)$ and $(0,1)$, shown in the figure below. I want to find all unique the two-vector combinations $\vec{a}$ and $\vec{b}$, such that area of the parallelogram subtended by these two vectors is $N=2$. There will be infinite solutions but there will be a unique set of basis-vectors that describe all the solutions. The unique set of solutions is such that any one of the set of vectors (from the solutions) cannot be expressed as a linear integer combination of any other set. The example below should help clarify this further. I am attaching a figure that shows the unique set of these vectors for both $N=2$ and $N=3$ in a 2D lattice.

In the figure, the unique set of basis vectors are shown and the corresponding parallelograms are shaded to show the fact that the area is (i) twice and (ii) three times the area of the smallest cell.

The vectors for $N=2$ are the following:

1) $\vec{a} = [1, 1]$; $\vec{b}= [1,-1]$

2) $\vec{a} = [2, 0]$; $\vec{b}= [0,1]$

3) $\vec{a} = [1, 0]$; $\vec{b}= [0,2]$

Any other solution in the lattice could be expressed as a linear integer combination of one of the sets of the basis vectors. I am looking for the unique set of solutions, which is finite! There are three solutions for A=2 and four unique solutions for A=3.

I got this solution using a MATLAB code that iteratively solves for all possible vectors, so it is very slow and the code runs out of memory for larger values of $N$. Given that there are such simple solutions for this problem, I couldn't stop but wonder if there is some property of lattices that I could use to efficiently arrive at these solutions.

Edit1: Alternatively, it would be great if anyone could hint me towards an efficient code that may generate all possible three-vector combinations, with volume $V$, in a 3D lattice of suppose $n\times n \times n$ lattice points. I have code that is $O(n^4)$, and hence, is very slow!

Any help is greatly appreciated. Thank you!

Answer 1

Hermite Normal Form will help greatly with this problem. The basis of any lattice has a unique representation in this form. For example the vectors for $N=2$ mentioned in the question, when considered as the rows of a matrix, give rise to the following matrices:

1)

\begin{equation} \left( \begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array} \right) \sim HNF\sim \left( \begin{array}{cc} 1 & 1 \\ 0 & 2 \end{array} \right) \end{equation}

2) \begin{equation} \left( \begin{array}{cc} 2 & 0 \\ 0 & 1 \end{array} \right) \text{ (already in HNF)} \end{equation}

3) \begin{equation} \left( \begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array} \right)\text{ (already in HNF)} \end{equation}

This form is very helpful here, because the restriction on the volume is a restriction on the determinant and the determinant of a matrix in HNF is the product of the elements on the diagonal. After this introduction here is the algorithm that solves the problem. I will state it in general and present the example for the $N=n=2$ case above:

Step1: Split $N$ as a product of $n$ integers in all possible ways, without ignoring the order. For our example, this gives

$$2=2*1\text{ or } 1*2$$

Step2: Write the above as the diagonal elements of an upper triangular matrix, with the upper elements undetermined yet. This gives:

\begin{equation} \left( \begin{array}{cc} 2 & a \\ 0 & 1 \end{array} \right) , \left( \begin{array}{cc} 1 & b \\ 0 & 2 \end{array} \right) \end{equation}

Step3: Write down all possible values for the undetermined elements. The restrictions come from the HNF form: They must be non-negative integers and for a given element x on the diagonal, all the elements above it must be genuinely smaller than x. In our example, this means that $a=0$ and $b=0$ or $1$ reproducing the three lattices given above.

Answer 2

A set of $n$ vectors in $\mathbb R^n$ with integer entries defines a parallelepiped of volume $V$ if and only if they are the columns of a $n\times n$ matrix with integral entries and determinant $\pm V$. You can then consider the particular case when $n=3$.

For example, when $n=2$, your vectors $a$ and $b$ are the columns of the matrices $$ \begin{pmatrix}1 & 1 \\1 & -1\end{pmatrix},\quad \begin{pmatrix}2 & 0 \\0 & 1\end{pmatrix},\quad \begin{pmatrix}1 & 0 \\0 & 2\end{pmatrix}, $$ all with determinant $\pm2$. Another example would be say $$ \begin{pmatrix}k+1 & 1 \\k-1 & 1\end{pmatrix}. $$

PS: You can ask whether it is possible to "enumerate" efficiently the matrices for a given $n$, but beyond $n=2$ it is unlikely to be able to write something helpful.