# Generating vectors in a non-orthogonal 3D lattice with increasing magnitude

I am trying to build an algorithm to generate a sequence of lattice vectors $\mathbf{v}_n$ in 3D such that:

(a) the first vector $|\mathbf{v}_1|$ is the shortest vector of the lattice

(b) for all $i \in \mathbb{Z}^{+}$, $\mathbf{v}_{i+1}$ is the shortest lattice vector greater than $\mathbf{v}_{i}$

So the sequence $\mathbf{v}_n$ not only contains lattice vectors of increasing magnitude but also has the property that there does not exist any lattice vector $\mathbf{v}$ such that $|\mathbf{v}_i| < |\mathbf{v}| < |\mathbf{v}_{i+1}|$ for all $i \in \{1, 2, 3, \ldots \}$.

The basis vectors of the general non-orthogonal 3D lattice may be denoted as $\mathbf{a}$, $\mathbf{b}$ and $\mathbf{c}$. Note that the basis vectors have been passed through an LLL algorithm, so they are short and as close to orthogonal as possible (https://en.wikipedia.org/wiki/Lattice_reduction). The magnitude of the lattice vector $\mathbf{v}$ is:

$|\mathbf{v}|^2 = \mathbf{v}^T \mathbf{v} = \left[ u\mathbf{a}, \, u\mathbf{b}, u\mathbf{c} \right]^T \left[ u\mathbf{a}, \, u\mathbf{b}, u\mathbf{c} \right]$

where $u, v, w \in \mathbb{Z}$ and are the components of the vector $\mathbf{v}$ in the lattice.

I was able to get a simple solution for 2D with orthogonal basis vectors but I was not able to think of any good solution even in 2D for non-orthogonal vectors. I wanted to post this question to see if this is a well-known problem (or some variant of a well-known problem) or if anyone had already thought about something like this before.

For the Gram matrix (specified by Will Jaggy):

$\left( \begin{array}{ccc} 2 & 0 & 1 \\ 0 & 2 & 1 \\ 1 & 1 & 5 \end{array} \right)$

the first 20 shortest vectors will be:

-1     0     0
0    -1     0
0     1     0
1     0     0
-1    -1     0
-1     1     0
1    -1     0
1     1     0
0     0    -1
0     1    -1
1     0    -1
1     1    -1
-1    -1     1
-1     0     1
0    -1     1
0     0     1
-2     0     0
0    -2     0
0     2     0
2     0     0


The square of the Euclidean norms, i.e. $||v||^2$,for the first 20 vectors are: 2, 2, 2, 2, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 8, 8, 8, 8

• Srikanth, I put a 3 by 3 Gram matrix in my answer. What this indicates, for basis vectors $a,b,c$ is that $a \cdot a = 2,$ $b \cdot b = 2,$ $c \cdot c = 5,$ $b \cdot c = 1,$ $c \cdot a = 1,$ $a \cdot b = 0.$ Please find the first ten items that you would want for your sequence, and edit those into your question. I currently have little idea what you want, and I suspect you are attempting to get an algorithm for a task you have never done by some slow method. Commented Jul 4, 2015 at 20:00
• I added the first 20 vectors in the sequence for the Gram Matrix you specified. The code I use is very inefficient and not guaranteed to give the right answer but it works in most cases. I just create a 3D-mesh of points, e.g. $u, v, w \in [-10, 10]$ and I gave you the first 20 vectors after sorting the distances for all the generated vectors. This will clearly not work well for skewed bases. Thank you. Commented Jul 4, 2015 at 20:37
• I can finally make one substantial comment: in order to find all $|v|^2$ up to some bound $M,$ we get a guaranteed search by using lagrange multipliers to maximize $|u|,$ $|v|,$ $|w|,$ under the constraint i mentioned, $$X^T G X \leq M$$ Commented Jul 4, 2015 at 20:42
• @Will: Interesting.. Just so we are on the same page, I will first find max $|u|$, $|v|$, and $|w|$ using Lagrange multipliers with the constraint $X^T G X \leq M$. Then I will check the norms for all the vectors with $u \in [-|u|, |u|]$, $v \in [-|v|, |v|]$ and $w \in [-|w|, |w|]$ and pick all the vectors satisfying the constraint $X^T G X \leq M$. I agree that this will give me all the vectors $|v|^2$ up to some bound $M$. Commented Jul 4, 2015 at 20:58
• Yes, and the gradient of $X^T G X,$ written as a column vector, is $2 G X.$ The gradient of, say, $u,$ is $(1,0,0)^T.$ Anyway, the main computation for Lagrange is to find $G^{-1}$ and go from there. It is also fine to use the adjoint matrix for $G,$ as it is just a multiple of the inverse. Commented Jul 4, 2015 at 21:07

Here is a guaranteed way to find all vectors with squared norm up to some bound $M.$ Find the Gram matrix $G$ of the lattice. Write the squared norm of any column vector as $X^T G X,$ where the entries of $X$ are the coefficients of the basis vectors. Note that the set $$X^T G X \leq M$$ is an ellipsoid. If we call $X = (u,v,w),$ the gradient of the function $u$ is just $e_1 = (1,0,0)^T.$ In order to find the maximum possible $u$ on the ellipsoid, just solve Lagrange multipliers. Written as a column vector, the gradient of $X^T G X$ is just $$2 G X.$$ As a result, the only important matrix calculation here is finding $G^{-1};$ it is satisfactory to use the adjoint matrix of $G,$ because that is just a multiple of the inverse.

In total, to get all vectors with squared norm up to some $M,$ we can just use Lagrange multipliers to give a firm upper bound for $|u|,$ another upper bound for $|v|,$ another upper bound for $|w|.$ This defines a rectangular brick shape that completely contains the ellipsoid.

FROM MY BIG BOOK O' QUADRATIC FORMS

Jonathan Hanke once asked me how I got nice bounds on the variables in programming a computer search on the ellipsoid $T(x,y,z) \leq M$ for some large positive $M,$ where $T(x,y,z) = a x^2 + b y^2 + c z^2 + d y z + e z x + f x y$
is a positive ternary. Well, $$T(x,y,z) = \left( x \: y \: z \right) \cdot \left( \begin{array}{rrr} a & f/2 & e/2\\ f/2 & b & d/2\\ e/2 & d/2 & c \end{array} \right) \cdot \left( \begin{array}{c} x \\ y\\ z \end{array} \right) .$$ It is simple enough to confirm that the gradient of $T,$ written as a column vector, is $$\nabla T(x,y,z) = \left( \begin{array}{c} 2 a x + f y + e z \\ f x + 2 b y + d z \\ e x + d y + 2 c z \end{array} \right) = 2 \left( \begin{array}{rrr} a & f/2 & e/2\\ f/2 & b & d/2\\ e/2 & d/2 & c \end{array} \right) \cdot \left( \begin{array}{c} x \\ y\\ z \end{array} \right) .$$

We are going to use the method of Lagrange multipliers. It follows from the compactness of the ellipsoid $T \leq M$ (the Gram matrix has positive eigenvalues) that any of the variables $x,y,z$ achieves its maximum. It follows from the strict convexity of the ellipsoid that these maxima are achieved at boundary points where $T = M.$ Finally it follows from the smoothness of the boundary that Lagrange multipliers will locate all such points.

Give a name $F$ to the matrix, so $$F = \left( \begin{array}{rrr} a & f/2 & e/2\\ f/2 & b & d/2\\ e/2 & d/2 & c \end{array} \right) .$$

We need the other gradients, $$\nabla x = \left( \begin{array}{c} 1\\ 0 \\ 0 \end{array} \right) = e_1, \nabla y = \left( \begin{array}{c} 0\\ 1 \\ 0 \end{array} \right) = e_2, \nabla z = \left( \begin{array}{c} 0\\ 0 \\ 1 \end{array} \right) = e_3 .$$

So, given $$X = \left( \begin{array}{c} x\\ y \\ z \end{array} \right) ,$$

we are solving the system $$\begin{array}{ccc} 2 F X & = & \lambda e_i \\ X' F X &= &M \end{array}$$ $X' = (x \: y \: z)$ being the transpose of $X.$

The matrix $F$ has an inverse that we will cleverly name $F^{-1}.$ So we find $$X =\left( \frac{\lambda}{2} \right) F^{-1} e_i .$$

The fraction doesn't help or hurt, so we will name $t = \left( \frac{\lambda}{2} \right)$ and get $$X =t F^{-1} e_i .$$

Notice that $F$ and so $F^{-1}$ are symmetric. Next we use $X' F X = M,$ or $t {e_i}' F^{-1} F F^{-1} e_i t = M,$ whence $t {e_i}' F^{-1} e_i t = M.$ Now ${e_i}' F^{-1} e_i$ is the $i,i$ entry of $F^{-1},$ which we write as $F^{-1}_{ii}.$ So we find $$t^2F^{-1}_{ii} = M.$$ or $$t = \sqrt{ \frac{M}{ F^{-1}_{ii}} }.$$

Recalling $X =t F^{-1} e_i$ gives us $$X = \left( \begin{array}{c} t F^{-1}_{1i}\\ t F^{-1}_{2i} \\ t F^{-1}_{3i} \end{array} \right) ,$$

So, maximizing $x_1 = x, x_2 = y, x_3 = z$ leads us to the value $$x_i = t F^{-1}_{ii} = \sqrt{ \frac{M}{ F^{-1}_{ii}} } F^{-1}_{ii} ,$$ or $$x_i = \sqrt{ M F^{-1}_{ii} }$$

In conclusion, $$| x | \leq \sqrt{ M F^{-1}_{11}}, \hspace{7mm} | y | \leq \sqrt{ M F^{-1}_{22}}, \hspace{7mm} | z | \leq \sqrt{ M F^{-1}_{33}}.$$

If supreme efficiency is needed, one then fixes, say, a value of $z,$ and notes that the ellipsoid section described is an ellipse. The Lagrange multiplier method can be repeated to find, say, the maximum and minimum of $y,$ which are no longer of the same absolute value. Finally, with values of $y,z$ chosen, bounds on $x$ come from the quadratic formula.

I worked up an example to illustrate the possible need. What follows is an ellipsoid of revolution of a cigar shape, long in the direction of the vector (1,1,1) and narrow in any orthogonal direction. As a result, the volume of the cube given by the bounds $| x | \leq \sqrt{ M F^{-1}_{11}}, | y | \leq \sqrt{ M F^{-1}_{22}}, | z | \leq \sqrt{ M F^{-1}_{33}}$ is quite large compared with the volume of the ellipsoid. The volume of the ellipsoid is very close to the number of integer triples to be checked that satisfy $T(x,y,z) \leq M.$ Think about it.

Given a large integer $W > 0,$ let $$\begin{array}{ccc} T(x,y,z) & = & ( x + y + z)^2 + 3 W ( x - y)^2 + W ( x + y - 2 z)^2\\ & = & ( 4 W + 1)(x^2 + y^2 + z^2) - (4 W - 2) (y z + z x + x y). \end{array}$$ In the ellipsoid $T \leq 9 W^2,$ we find the integer point $(W,W,W),$ at a distance of $\sqrt{ W^2 + W^2 + W^2 } = W \sqrt{3}$ from the origin. However, in the plane $x + y + z = 0,$ we get a circular section of the ellipsoid, and letting $t$ now be the distance of a point from the origin, taking $x = t / \sqrt{2} , y = -t / \sqrt{2} , z = 0$ tells us that $\sqrt{ x^2 + y^2 + z^2 } \leq \sqrt{\frac{3 W}{2}}.$ Anyway much smaller than $W \sqrt{3}.$

As to the comparison of volumes, the cube given by the raw $x,y,z$ bounds has volume at least $8 W^3,$ being at least $2 W$ on a side. Using the discriminant recipe $\Delta = 4 a b c + d e f - a d^2 - b e^2 - c f^2$ gives $\Delta = 432 W^2.$ The volume of the ellipsoid $T \leq M$ should be $$\frac{8 \pi M^{3/2}}{ 3 \sqrt{\Delta}} .$$ With $T \leq 9 W^2,$ we have $M = 3 W^2,$ so the ellipsoid has volume $2 \pi \sqrt{3} W^2.$ Finally the volume of the cube divided by the volume of the cigar is $$\frac{4 W}{\pi \sqrt{3}} = \left( \frac{4}{\pi \sqrt{3}} \right) W,$$ a bit larger than $\frac{11 W}{ 15}.$

END O' EXCERPT

There are roughly 1000 positive ternary forms for which all represented numbers (all lattice norms) are known, with proofs. In every other case, it is a matter of luck. What that means for you is that your task can be done up to some finite bound without difficulty, it is a finite check because the form is positive definite, the Gram matrix has a minimum eigenvalue and so on, but no infinite sequence, no algorithm.

I have always used Schiemann's reduction in my articles. This is a slight refinement of Eisenstein's reduction that moves all positive ternary forms into a single cone in $\mathbb R^6.$

$$\left( \begin{array}{ccc} 2 & 0 & 1 \\ 0 & 2 & 1 \\ 1 & 1 & 5 \end{array} \right)$$
Just so you know, the form I specify is in the same genus as $x^2 + y^2 + 16 z^2.$ As you can see from Dickson's book below, we know exactly what numbers occur as squared norms of vectors in the $(1,1,16)$ lattice. The extra ingredient I put in, on purpose, that the form with the Gram matrix above also fails to represent $1,25,169,...,$ indeed any $m^2$ where all prime factors $p$ of $m$ satisfy $p \equiv 1 \pmod 4.$