1
$\begingroup$

The Lenstra–Lenstra–Lovász (LLL) algorithm is a famous one for lattice reduction. But concerning its application, I am always baffled by one point.

The algorithm applies equally well to irrational and rational numbers, right? But, it seems that in the literature, people always confine themselves to the rational case. That is, the initial basis vectors are always like $[101, 394, 5677]$, but never $[\sqrt{2}, \sqrt{345}, \sqrt{13}]$.

One should note that the irrational case is the most generic case, as in the Diophantine approximation problem.

$\endgroup$
  • $\begingroup$ Maybe, because there are no irrational numbers outside of symbolic computations? $\endgroup$ – Bort Mar 22 '17 at 14:31
4
$\begingroup$

I am by no means an expert on LLL, but I have worked with it before. Please correct me if this answer is in some way incorrect.

Define a basis $\beta = \{v_1,v_2,\ldots,v_n\}$ for $\mathbb{R}^n$. Then the lattice $L$ generated by $\beta$ is the set of integer linear combinations of $\beta$:

$$ L = \{ m_1v_1 + \cdots + m_nv_n : m_i \in \mathbb{Z} \} $$

This means the $\beta$-coordinate representation of vectors in $L$ are entirely integers.

The basis $B$ is a set of vectors in $L$ that spans $L$ by integer linear combinations of the vectors in $B$. Since each of the vectors in $B$ are in $L$, they must have integer coordinates with respect to $\beta$, but they may not have integer entries as vectors in $\mathbb{R}^n$.

To make this concrete, consider the lattice $L$ spanned by $\beta = \{ (\sqrt{2},0), (0,\sqrt{3}) \}$. Then $B = \{(\sqrt{2},0),(\sqrt{2},\sqrt{3}) \}$ is a basis for $L$. Note that the vectors in $B$ have irrational entries. The coordinates of $(\sqrt{2},0)$ in the basis $\beta$ is $(1,0)$ and the coordinates of $(\sqrt{2},\sqrt{3})$ in $\beta$ is $(1,1)$. So while the vectors in $B$ do not have integer values, they do have integer coordinates with respect to the basis $\beta$.

$\endgroup$

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.