1
$\begingroup$

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.

enter image description here

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!

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you, Heterotic! This is fascinating. I don't know much about the HNF, so I will need some time to understand this completely and extend it to the 3D problem. This should definitely speed-up my calculations. I will test it out and will let you know about the outcome... Thanks again! $\endgroup$ – Srikanth Mar 6 '16 at 21:40
  • $\begingroup$ I used the steps you mentioned for generating sub-lattices of volume $V=3$ in a 3D lattice and it matches perfectly with my very inefficient code that enumerates all possible solutions. This is perfect! Thanks! $\endgroup$ – Srikanth Mar 6 '16 at 23:37
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thank you, Jonas! Absolutely! I completely agree with you... I am looking for a code that can efficiently enumerate the solutions. Also, the other solutions that you specified with $k+1$ and $k-1$ also satisfy the area condition but they can be expressed as a linear combination of one of the solutions already provided. So the three solutions provided are a "unique" set. There are no more solutions that cannot be expressed as a linear combinations of one of the already provided solutions. E.g., If k=5, then the vectors you provided can be expressed as a linear combination of the second solution $\endgroup$ – Srikanth Mar 5 '16 at 0:06
  • $\begingroup$ @Srikanth Actually, one solution suffices, for each $n$. Any other solution will have columns that are linear combinations of the columns in that particular solution. $\endgroup$ – John B Mar 5 '16 at 0:09
  • $\begingroup$ Is that true? Hmm... For example, I cannot express the second solution $S_2 = [[2,0];[0,1]]$ as an integer combination of the vectors of the first solution $S_1 = [[1,1];[1,-1]]$. In fact, the matrix $S_2 \cdot S_1^{-1}$ has non-integer components $=[[1,0];[0,-0.5]]$. Am I missing something here? $\endgroup$ – Srikanth Mar 5 '16 at 0:14
  • $\begingroup$ @Srikanth Ah, you meant linear combination with integer coefficients. I meant real coefficients. $\endgroup$ – John B Mar 5 '16 at 0:17
  • $\begingroup$ Oh... sorry about that! I should have made that clear. As I had mentioned, I am not a mathematician.. so definitely lack the rigor! I will add this part in my question. It is an interesting problem for me... the fact that there is a small set of finite number of solutions for each value for the area (in 2D) or volume (in 3D). Hope this would be an interesting question for you as well! $\endgroup$ – Srikanth Mar 5 '16 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.