Shortest orthogonal integer vectors and their cross product

Question

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

Answer 1

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)

Answer 2

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|<v_3$ and $|q_i|<v_2$. 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$.