# Shortest orthogonal integer vectors and their cross product

Question:
Given an arbitrary non-zero vector $v \in \mathbb{Z}^3$ with $\gcd(v) = 1$, there exist linear independent non-zero vectors $f, s \in \mathbb{Z}^3$ orthogonal to $v$ and minimal with respect to the Euclidean norm. Their cross product must be a scalar multiple of $v$, say $f \times s = \lambda v$. Obviously $\lambda \in \mathbb{Z}$, but is $\lambda = \pm 1$?

With help from Rodrigo de Azevedo I made progress.
This answer provably provides two basis vectors spanning the lattice of vectors orthogonal to $v$.
Then an algorithm due to Lagrange finds the shortest two basis vectors $f$ and $s$, given any two basis vectors $b$ and $c$ :

if $\lVert b \rVert < \lVert c \rVert$:
$\quad$ $b, c := c, b$
while $\lVert c \rVert < \lVert b \rVert$:
$\quad$ $b, c := c, b - \lfloor \frac{\langle\,b,c\,\rangle }{{\lVert c \rVert}^2}\, \rceil c$
return $b, c$

Here $\lVert \cdot \rVert$ denotes the Euclidean norm, $\lfloor \cdot \rceil$ the nearest integer function and $\langle\,\cdot, \cdot\,\rangle$ the dot product.

On my computer checking 10000 random vectors takes roughly 5 minutes. So far I haven't found a counterexample.

Motivation:
Consider the homogeneous diophantine equation $$v_1x_1+v_2x_2+v_3x_3=0$$ over $\mathbb{Z}$ with $v$ given and $\gcd(v)=1$.
A version of Siegel's lemma states, that there exist two non-trivial linear independent solutions $f, s$, such that $$\max(|f_i|) \max(|s_i|) \leq \lVert v \rVert.$$ Since $$|\lambda| \lVert v \rVert = \lVert f \times s \rVert \leq \lVert f \rVert \lVert s \rVert < 3 \max(|f_i|) \max(|s_i|) \leq 3 \lVert v \rVert,$$ we have $|\lambda| \leq 2$. I was hoping for either an example with $|\lambda| = 2$ or an intuitive explanation why $|\lambda|$ always equals $1$.

• No. That's not required.
– vuur
Commented Dec 26, 2016 at 19:27
• No. I use sage. Did you find a counterexample? Anyway, if you wrote something in Mathematica, or have an idea how to code something, I'd be interested to know about it.
– vuur
Commented Dec 28, 2016 at 10:45
• Minimal with respect to the Euclidean norm. Doesn't that mean $\gcd(f) = 1$ and $\gcd(s) = 1$ as well? (Sorry if the answer is trivially yes or no: integer number theory is not really my thing) Commented Dec 28, 2016 at 15:21
• Yes, that's true.
– vuur
Commented Dec 28, 2016 at 15:27

## 2 Answers

Given a nonzero integer vector $\mathrm v = (v_1, v_2, v_3)$ with $\mbox{gcd} (v_1, v_2, v_3) = 1$, we would like to find two linearly independent nonzero integer vectors that are orthogonal to $\mathrm v$ and whose Euclidean norm is minimal.

Let $\mathrm x = (x_1, x_2, x_3)$ be a general point in $\mathbb R^3$. If $\mathrm x \perp \mathrm v$, then $\langle \mathrm v, \mathrm x \rangle = 0$. Hence,

$$v_1 x_1 + v_2 x_2 + v_3 x_3 = 0$$

defines the plane orthogonal to $\mathrm v$. Assuming that $v_1 \neq 0$, this plane is parametrized by

$$\begin{bmatrix} x_1\\ x_2\\ x_3\end{bmatrix} = \begin{bmatrix} -\frac{v_2}{v_1} & -\frac{v_3}{v_1}\\ 1 & 0\\ 0 & 1\end{bmatrix} \begin{bmatrix} t_1\\ t_2\end{bmatrix}$$

where $t_1, t_2 \in \mathbb R$. If $v_1 = 0$, then we reorder the left-hand side of $v_1 x_1 + v_2 x_2 + v_3 x_3 = 0$ so that the terms with nonzero coefficients come first. Do recall that at least one of $v_1, v_2, v_3$ is nonzero.

If the parameters are integer multiples of $v_1$, i.e., $t_i = v_1 z_i$, we obtain the parametrization of a $2$-dimensional lattice in $\mathbb Z^3$

$$\begin{bmatrix} x_1\\ x_2\\ x_3\end{bmatrix} = \underbrace{\begin{bmatrix} -v_2 & -v_3\\ v_1 & 0\\ 0 & v_1\end{bmatrix}}_{=: \mathrm B} \begin{bmatrix} z_1\\ z_2\end{bmatrix}$$

where $z_1, z_2 \in \mathbb Z$. Let $\mathrm b_1$ and $\mathrm b_2$ denote the two columns of $\mathrm B$. Note that $\mathrm b_1 \perp \mathrm v$ and $\mathrm b_2 \perp \mathrm v$. The aforementioned $2$-dimensional lattice is defined by

$$\mathcal L (\mathrm B) := \{ \mathrm B \mathrm z \mid \mathrm z \in \mathbb Z^2 \} = \{ z_1 \mathrm b_1 + z_2 \mathrm b_2 \mid z_1, z_2 \in \mathbb Z \} = \Bigg\{ \begin{bmatrix} -v_2 z_1 - v_3 z_2\\ v_1 z_1\\ v_1 z_2\end{bmatrix} : z_1, z_2 \in \mathbb Z \Bigg\}$$

We say that the lattice is generated by $\mathrm B$ and that $\mathrm b_1$ and $\mathrm b_2$ are basis vectors. These basis vectors are not unique, however. Via lattice reduction, we find basis vectors $\hat{\mathrm{b}}_1$ and $\hat{\mathrm{b}}_2$ that are "short" and "nearly orthogonal". I believe that $\hat{\mathrm{b}}_1$ and $\hat{\mathrm{b}}_2$ will be the shortest vectors in the lattice.

Sage has both NTL and fplll, both of which have implementations of lattice reduction algorithms, such as the famous LLL algorithm.

Let $\hat{\mathrm{B}}$ be the $3 \times 2$ matrix whose columns are $\hat{\mathrm{b}}_1$ and $\hat{\mathrm{b}}_2$. There is a $2 \times 2$ unimodular matrix $\mathrm U$ such that $\hat{\mathrm{B}} = \mathrm B \mathrm U$. Since $\mathrm B$ has full column rank, matrix $\mathrm U$ is given by $\mathrm U = \left( \mathrm B^{\top} \mathrm B \right)^{-1} \mathrm B^{\top} \hat{\mathrm{B}}$.

# Example

Let $\mathrm v = (1,2,3)$. Hence,

$$\mathrm B = \begin{bmatrix} -2 & -3\\ 1 & 0\\ 0 & 1\end{bmatrix}$$

Let us look for lattice points inside the Euclidean sphere of radius $\| \mathrm b_1 \|_2 = \sqrt{5}$ and centered at the origin. The $2$-dimensional lattice generated by $\mathrm B$, a segment of the plane generated by $\mathrm B$ and the aforementioned Euclidean sphere are depicted below

By visual inspection, we find four nonzero lattice points in the sphere. These are

$$\hat{\mathrm{b}}_1 := \begin{bmatrix} 1\\ 1\\ -1\end{bmatrix} \qquad \qquad \qquad \hat{\mathrm{b}}_2 := \begin{bmatrix} 2\\ -1\\ 0\end{bmatrix}$$

and $-\hat{\mathrm{b}}_1$ and $-\hat{\mathrm{b}}_2$. Note that $\hat{\mathrm{b}}_1 \perp \mathrm v$ and that $\hat{\mathrm{b}}_2 \perp \mathrm v$. Their cross product is

$$\hat{\mathrm{b}}_1 \times \hat{\mathrm{b}}_2 = \begin{bmatrix} -1\\ -2\\ -3\end{bmatrix} = - \mathrm v$$

and their angle is

$$\arcsin \left(\frac{\|\hat{\mathrm{b}}_1 \times \hat{\mathrm{b}}_2\|_2}{\|\hat{\mathrm{b}}_1\|_2 \|\hat{\mathrm{b}}_2\|_2}\right) = \arcsin \left(\sqrt{\frac{14}{15}}\right) \approx 75^{\circ}$$

whereas the angle formed by $\mathrm b_1$ and $\mathrm b_2$ is

$$\arccos \left(\frac{\langle \mathrm b_1, \mathrm b_2\rangle}{\| \mathrm b_1 \|_2 \| \mathrm b_2 \|_2}\right) = \arccos \left(\frac{6}{\sqrt{50}}\right) \approx 32^{\circ}$$

Thus, $\hat{\mathrm{b}}_1$ and $\hat{\mathrm{b}}_2$ are shorter and closer to orthogonality than $\mathrm b_1$ and $\mathrm b_2$, as expected. Lastly,

$$\mathrm U = \left( \mathrm B^{\top} \mathrm B \right)^{-1} \mathrm B^{\top} \hat{\mathrm{B}} = \begin{bmatrix} 1 & -1\\ -1 & 0\end{bmatrix}$$

Hence,

$$\hat{\mathrm{b}}_1 = \mathrm b_1 - \mathrm b_2 \qquad \qquad \qquad \hat{\mathrm{b}}_2 = -\mathrm b_1$$

# Code

The following Python script generates the lattice.txt file (to be imported by Grapher) and determines which lattice points are in the sphere of radius $\sqrt 5$:

f = open('lattice.txt','w')

for z1 in range(-10,11):
for z2 in range(-10,11):
f.write(str(-2*z1-3*z2)+', '+str(z1)+', '+str(z2)+'\n')
if (-2*z1-3*z2)**2 + z1**2 + z2**2 <= 5:
print (-2*z1-3*z2,z1,z2)

f.close()


Its output is:

(2, -1, 0)
(-1, -1, 1)
(0, 0, 0)
(1, 1, -1)
(-2, 1, 0)

• Thank you for your answer. I am probably overlooking something, but even if I believe that $\hat{\mathrm{b}}_1$ and $\hat{\mathrm{b}}_2$ are the shortest vectors, I don't see where you justify that their vector product has $\gcd=1$.
– vuur
Commented Dec 28, 2016 at 16:17
• Their vector product is $-\mathrm v$, which has GCD = 1. Commented Dec 28, 2016 at 16:20
• Could you explain why that holds in general? I trust that it works in your example
– vuur
Commented Dec 28, 2016 at 16:22
• Does it actually hold in general? Have you tried in Sage to generate many $\mathrm v$ vectors, form a $\mathrm B$ matrix for each of them, use LLL to find a reduced basis and then compute the cross product of the basis vectors? Commented Dec 28, 2016 at 16:26
• We don't know yet!
– vuur
Commented Dec 28, 2016 at 20:42

As an extension to the Rodrigo de Azevedo's answer, it must be mentioned that the $$b_1$$ and $$b_2$$ vectors, selected as $$(-v_2,v_1,0)$$ and $$(-v_3,0,v_1)$$, do not generally produce the right results by just using the lattice reduction. To generate correct source vectors for that purpose, it is needed to first find out 2 integers $$p$$ and $$q$$ so that $$p v_2+q v_3 = GCD(v_2,v_3) v_1$$. This can be made by applying GCD method, and produces two different solutions $$(p_1,q_1)$$ and $$(p_2,q_2)$$, when $$|p_i| and $$|q_i|. In fact, if $$p_1 > 0$$ and $$q_1 < 0$$, then $$p_2 = p_1 - v_3 < 0$$ and $$q_2 = q_1 + v_2 > 0$$. Then you calculate new $$b_1' = (p_1 b_1+q_1 b_2)/v_1$$ and $$b_2' = (p_2 b_1+q_2 b_2)/v_1$$. The division is possible because all the corresponding values are multiples of $$v_1$$. The lattice reduction may now be performed using $$b_1'$$ and $$b_2'$$, and assumedly produces the right results. (Note that in the practical example (1,2,3) this extra step was avoided by using $$v_1$$ = 1).

Let us consider a general case $$(v_1,v_2,v_3) = (aef,bdf,cde)$$, where $$a$$, $$b$$, $$c$$, $$d$$, $$e$$, and $$f$$ are positive integers having no pairwise common factors. We note that $$GCD(v_2,v_3) = d$$, $$GCD(v_1,v_3) = e$$, and $$GCD(v_1,v_2) = f$$, but $$GCD(v_1,v_2,v_3) = 1$$. We get $$b_1 = (bd,-ae,0)$$ and $$b_2 = (cd,0,-af)$$, where we have divided the values with their common factors $$f$$ and $$e$$, respectively. Now we find out $$p$$ and $$q$$ so that $$pb + qc = a$$, where $$0 < p < c$$ and $$0 < |q| < b$$. The candidates for shortest orthogonals are then $$b_1'= (pb_1+qb_2)/a = (d,-pe,-qf)$$ and $$b_2'=((p-c)b_1+(q+b)b_2)/a = (d,-(p-c)e,-(q+b)f)$$. Both are orthogonal to $$(v_1,v_2,v_3)$$ and $$b_1' × b_2' = (ef(pb+qc),bdf,cde) = (aef,bdf,cde) = (v_1,v_2,v_3)$$. This candidate pair thus fulfills the condition $$λ=±1$$.

Note that by exchanging the roles of $$v_1$$, $$v_2$$, and $$v_3$$ we (may) get more candidate pairs, which may (or may not) be even shorter, but still fulfilling the condition $$λ=±1$$.

• Welcome to MSE. I suggest that you use $\times$ instead of $*$ for the product. Commented Nov 29, 2020 at 8:33