The S(A) Function

Equation 2.2 above introduced the Seysen measure function $S(A) = \sum_{i=1}^n \Vert\bold{b_i}\Vert^2 \Vert\bold{b_i^*}\Vert^2$; the entire operation of Seysen's lattice basis reduction algorithm centers on this quantization of relative reduction of two bases of lattice L. It is natural to question whether Seysen measures are indeed a reasonable means of ranking different lattice bases. We mention here some of the theoretical evidence which suggests that ranking lattice bases by their Seysen measure is appropriate. The use of the quantity $\Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert$ derives from elementary n-dimensional geometry. Recall the definition of the dual lattice $B^*=(\bold{b_1^*},\ldots{},\bold{b_n^*})$ of lattice B:

$$(\bold{b_i},\bold{b_j^*}) = \delta_{i,j}, \quad\text{for } 1 \leq i,j \leq n,$$

where $\delta_{i,j}$ is the Dirac delta function ( $\delta_{i,j} = 1$ if i = j, $\delta_{i,j} = 0$ otherwise). Now, fix i and notice that
 $$\begin{align}\left( \bold{b_i}, \bold{b_i^*} \right) & = 1, \notag \\ \Vert\bo... ...\bold{b_i}\Vert \Vert\bold{b_i^*}\Vert & = \frac{1}{\cos(\alpha)}, \end{align}$$
where $\alpha$ is the angle between $\bold{b_i}$ and $\bold{b_i^*}$. (Note that $-\tfrac{\pi}{2} \leq \alpha \leq \tfrac{\pi}{2}$ beacuse of the way in which $\bold{b_i^*}$ is defined.) Let S_i denote the (n-1)-dimensional hyperplane spanned by the basis vectors $\bold{b_1},\ldots{},\bold{b_{i-1}},\bold{b_{i+1}},\ldots{},\bold{b_n}$. Notice that $\bold{b_i^*}$ is perpendicular to S_i by definition. Thus, given that $\alpha$ is the angle between $\bold{b_i}$ and $\bold{b_i^*}$, the angle between $\bold{b_i}$ and S_i is $\pi - \alpha$. Thus, if $\beta = \pi - \alpha$, Equation 2.5 becomes

$$\Vert\bold{b_i}\Vert \Vert\bold{b_i^*}\Vert = \frac{1}{\sin(\beta)}.$$

If basis vector $\bold{b_i}$ is relatively dependent of the other vectors $\bold{b_j}, 1 \leq j \leq n, j \neq i$, then the angle between $\bold{b_i}$ and the hyperplane S_i will be relatively small, and thus $\frac{1}{\sin(\beta)}$ will be large. Conversely, if $\bold{b_i}$ is relatively independent of the other basis vectors, $\beta$ will be close to $\frac{\pi}{2}$ radians, and the product $\Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert$ will be close to one^2.1. These geometric arguments lead directly to a measure which is a function of the products $\Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert$ where $1 \leq i \leq n$. Since $\vert\beta_i\vert \leq \tfrac{\pi}{2}$, we could choose the function $S_1(A) = \sum \Vert\bold{b_i}\Vert \Vert\bold{b_i^*}\Vert = \sum \tfrac{1}{\sin(\beta_i)}$ as the measure function. Unfortunately, as Section 2.4.4 points out below, there is no simple formula for finding the optimal value of $\lambda$ for a row move involving the basis vectors $\bold{b_i}$ and $\bold{b_j}$. Seysen is able to avoid these computational difficulties by using
$$\begin{align*}S(A) & = \sum_{i=1}^n \Vert\bold{b_i}\Vert^2 \Vert\bold{b_i^*}\Vert^2, \\ & = \sum_{i=1}^n \frac{1}{\sin^2(\beta_i)}, \end{align*}$$
as the measure function, which does yield a simple formula for $\lambda$. Since $\sin(\beta_i) \in [0,1]$, the squared terms in the S(A) function are guaranteed to be larger on a term-by-term basis than the corresponding terms in the S₁(A) sum. Thus, if lattice basis B₁ has smaller measure than basis B₂ using the S₁ measure function, B₁ will also have smaller measure than B₂ when compared using the Seysen measure S. An additional advantage to using a function of the $\Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert$ product terms is that bounds exists on the size of the individual terms. In [17] Håstad and Lagarias show that the following bound applies for some primal basis B and dual basis B^* of a given lattice:

$$\max_{1 \leq i \leq n} \left\{ \Vert\bold{b_i}\Vert, \Vert\bold{b_i^*} \Vert\right\} \leq \exp(O(n^{\frac{1}{3}})).$$ (2.5)

This bound immediately implies that there exists a basis of L with Seysen measure bounded by $\exp(O(n^{\tfrac{1}{3}}))$, since:
$$\begin{align*}\max_{1 \leq i \leq n} \left\{ \Vert\bold{b_i}\Vert, \Vert\bold{b_... ...xp(O(n^{\frac{1}{3}})), \\ S(A) & \leq \exp(O(n^{\frac{1}{3}})). \end{align*}$$
Seysen shows in [38] that the bound in Equation 2.6 may be improved to

$$\max_{1 \leq i \leq n} \left\{ \Vert\bold{b_i}\Vert, \Vert\bold{b_i^*} \Vert\right\} \leq \exp(O((\ln n)^2)),$$ (2.6)

which reduces the bound on S(A) for an S-reduced lattice to:
$$\begin{align*}\sum_{i=1}^n \Vert\bold{b_i}\Vert\Vert\bold{b_i^*}\Vert & \leq n \... ...\exp(\ln n) \exp(O((\ln n)^2), \\ S(A) & \leq \exp(O((\ln n)^2). \end{align*}$$
To date, this is the best known bound on the Seysen-measure of an S-reduced lattice basis. However, as is the case with the LLL algorithm, in some cases Seysen's algorithm produces S₂-reduced lattice bases which have measures much lower than the theoretical bound.