Choosing $\lambda$ Values

We now consider the choice of $\lambda$ values in Seysen's basis reduction algorithm. Assume that S(A) is as in Equation 2.3 above, and that only two-vector row moves are considered (i.e. transformation matrices of the form $T_{i,j}^\lambda$ for integer values of i,j and $\lambda$). We first show that

$$\lambda = \frac{1}{2}\left(\frac{a_{i,j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}}\right),$$ (2.7)

yields the maximum possible reduction in S(A) for fixed values of i and j where $\lambda \in {\Bbb R}$. Further, we show that if we require $\lambda \in {\Bbb Z}$, then

$$\lambda = \left\lceil \frac{1}{2}\left(\frac{a_{i,j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}}\right) \right\rfloor,$$ (2.8)

is indeed the value which yields the best possible reduction in the Seysen measure of the lattice basis. Let i,j be fixed integers with $1 \leq i,j \leq n$; $\bold{b_i}, \bold{b_j}, \bold{b_i^*}$ and $\bold{b_j^*}$ are the basis vectors on which we will perform a row move. Without loss of generality, we assume that $\lambda\bold{b_i}$ will be added to $\bold{b_j}$ and $\lambda\bold{b_j^*}$ will be subtracted from $\bold{b_i^*}$. Define $\bold{b_j'}$ and $\bold{{b_i^*}'}$ to be the values of $\bold{b_j}$ and $\bold{b_i^*}$ after the row move is performed:
$$\begin{align*}\bold{b_j'} & = \bold{b_j} + \lambda\bold{b_i}, \\ \bold{{b_i^*}'} & = \bold{b_i^*} - \lambda\bold{b_j^*}. \end{align*}$$
Let A and A^* be the quadratic forms associated with the lattice and its dual before the row move occurs, and let A' and A^*' be the associated quadratic forms after the row move. Then
$$\begin{align*}A' & = T_{j,i}^\lambda \;A \;T_{i,j}^\lambda, \\ {A^*}' & = T_{i,j}^{-\lambda} \;A^* \;T_{j,i}^{-\lambda}. \end{align*}$$
Now, given that $T_{i,j}^\lambda$ transition matrices have exactly one off-diagonal nonzero entry, it is easy to see that A' differs from A only in the values in the $i^{\text{th}}$ row, the $j^{\text{th}}$ row, the $i^{\text{th}}$ column, and the $j^{\text{th}}$ column. The same is also true for A^*'. Since the Seysen measure function S(A) only depends upon the diagonal elements in A and A^*, we know that
 $$\begin{align}S(A') - S(A) & = \sum_{i=1}^n a_{i,i}' {a_{i,i}^*}' - \sum_{i=1}^n ... ...' + a_{j,j}'{a_{j,j}^*}' - a_{i,i} a_{i,i}^* - a_{j,j} a_{j,j}^*. \end{align}$$
When A is right-multiplied by $T_{i,j}^\lambda$, the $i^{\text{th}}$ column of A is added to the $j^{\text{th}}$ column of A. When this matrix is subsequently left-multiplied by $T_{j,i}^\lambda$, the $i^{\text{th}}$ row is added to the $j^{\text{th}}$ row. Thus, after these two transformations, the value of a_i,i is unchanged, but

$$a_{j,j}' = a_{j,j} + 2 \lambda a_{i,j} + \lambda^2 a_{i,i}.$$ (2.9)

If we perform a similar analysis in the dual quadratic form A^*, we find that

$${a_{i,i}^*}' = a_{i,i}^* - 2 \lambda a_{i,j}^* + \lambda^2 a_{j,j}^*.$$ (2.10)

Using Equations 2.12 and 2.13, Equation 2.11 becomes:
$$\begin{align*}S(A') - S(A) & = a_{i,i} \left( a_{i,i}^* - 2 \lambda a_{i,j}^* + ... ...j}^* + 2 \lambda a_{i,j} a_{j,j}^* - 2 \lambda a_{i,i} a_{i,j}^*. \end{align*}$$
Differentiating with respect to $\lambda$ and setting the result equal to 0, we find that:
$$\begin{align*}\frac{\partial}{\partial \lambda} \left(S(A') - S(A)\right) & = 4\... ...( \frac{a_{i,j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}} \right ). \end{align*}$$
Thus, if $\lambda$ could take on any real value, for fixed i and j the minimum value of S(A') is obtained with $\lambda = \frac{1}{2}\left(\frac{a_{i,j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}}\right)$. We have shown that the minimum value of S(A) with $\lambda \in {\Bbb R}$ is obtained when $\lambda$ satisfies Equation 2.8. Our goal now is to show that if $\lambda$ is restricted to integer values, Equation 2.9 yields that value of $\lambda$ for which S(A) is minimized. Let
$$\begin{align*}\lambda & = \lambda_z + \lambda_r, \quad\text{where } \lambda_z \i... ...(i,j,\lambda) & = S(T_{j,i}^\lambda \;A \;T_{i,j}^\lambda) - S(A). \end{align*}$$
We know that for fixed i,j, $\lambda = \frac{1}{2}\left(\frac{a_{i,j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}}\right)$ minimizes the value of $\Delta$. Furthermore, as $\Delta$ is a quadratic function of $\lambda$, at least one of $\lambda_z$ and $\lambda_z + 1$ must minimize $\Delta$ for fixed, integer values of $\lambda$. Consider $\Delta(i,j,\lambda_z)$ and $\Delta(i,j,\lambda_z+1)$:
$$\begin{align*}\begin{split} \Delta(i,j,\lambda_z) & = 2 \lambda_z^2 a_{i,i} a_{... ...j,j}^* + 2 a_{i,j} a_{j,j}^* - 2 a_{i,i} a_{i,j}^*, \end{split} \end{align*}$$
Thus,

$$\Delta(i,j,\lambda_z + 1) - \Delta(i,j,\lambda_z) = 4 \lambda... ...i,i} a_{j,j}^* + 2 a_{i,j} a_{j,j}^* - 2 a_{i,i} a_{i,j}^*.$$ (2.11)

As S(A) is a non-negative valued function which we want to minimize, we are interested in large, negative $\Delta$ values (i.e. $\vert\Delta\vert$ should be large, $\Delta < 0$). Thus, if Equation 2.14 is > 0, we should choose $\lambda = \lambda_z$; similarly, if Equation 2.14 is < 0, set $\lambda = \lambda_z + 1$. When is Equation 2.14 greater than zero?
$$\begin{align*}\Delta(i,j,\lambda_z + 1) - \Delta(i,j,\lambda_z) & > 0, \\ \Lon... ...frac{1}{2}, \\ \Longrightarrow \quad \lambda_r & < \tfrac{1}{2}. \end{align*}$$
Thus, if $\lambda_r < \tfrac{1}{2}$, then Equation 2.14 is positive, and we should choose $\lambda' = \lambda_z$. If $\lambda > \tfrac{1}{2}$, Equation 2.14 is negative, and we should set $\lambda' = \lambda_z + 1$. Thus,
$$\begin{align*}\lambda' & = \left\lceil \lambda_z + \lambda_r \right\rfloor, \\ ... ...j}^*}{a_{j,j}^*} - \frac{a_{i,j}}{a_{i,i}}\right) \right\rfloor, \end{align*}$$
which proves Equation 2.9.