1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Commented Jul 4, 2015 at 20:00
  • $\begingroup$ 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. $\endgroup$
    – Srikanth
    Commented Jul 4, 2015 at 20:37
  • $\begingroup$ 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 $$ $\endgroup$
    – Will Jagy
    Commented Jul 4, 2015 at 20:42
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Srikanth
    Commented Jul 4, 2015 at 20:58
  • $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Commented Jul 4, 2015 at 21:07

1 Answer 1

1
$\begingroup$

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.$

http://link.springer.com/article/10.1007%2Fs002080050086

http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=6992372

Tell you what: by any means available to you, please find the first ten entries in an acceptable sequence for the lattice with the following Gram matrix:

$$ \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.$

enter image description here

$\endgroup$
5
  • $\begingroup$ Hi Will... I have to admit, I am not a math major and I tried to read the papers from the links you have provided and failed to link it to my question. I did some more online research and found this question to be very relevant to what I am looking for: math.stackexchange.com/questions/9792/…. The problem in this link is in 2D and I am looking for something in 3D. I am looking for a finite sequence of vectors. If you could explain the algorithm, that will be great help. $\endgroup$
    – Srikanth
    Commented Jul 4, 2015 at 19:38
  • $\begingroup$ @Srikanth, so, what is your actual major? And why do you want this sequence of vectors? $\endgroup$
    – Will Jagy
    Commented Jul 4, 2015 at 19:45
  • $\begingroup$ I will get you the 10-shortest vectors in the next hour or so as I am in the process of developing some brute-force code. Also, I am a material science major. My materials are crystalline, which means that the atoms sit on a prescribed lattice. The short vectors have some nice properties for simulating a phenomena that I am interested in. $\endgroup$
    – Srikanth
    Commented Jul 4, 2015 at 20:09
  • $\begingroup$ Thanks, Will... Your answer is very helpful. $\endgroup$
    – Srikanth
    Commented Jul 5, 2015 at 4:38
  • $\begingroup$ The more I read it, the more I appreciate your answer and how well written it is. Excellent! Thank you. $\endgroup$
    – Srikanth
    Commented Jul 5, 2015 at 14:44

You must log in to answer this question.

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