TAOCP 3.3.4 Exercise 19
Yes.
Section 3.3.4: The Spectral Test
Exercise 19. [**] $[HM25]$ Suppose step S5 were changed slightly, so that a transformation with $q = 1$ would be performed when $2|V_j \cdot V_j - V_j \cdot V_j|$. (Thus, $q = \lfloor (V_j \cdot V_j / V_j \cdot V_j) + \frac{1}{2} \rfloor$ whenever $i \ne j$.) Would it be possible for Algorithm S to get into an infinite loop?
Verified: yes
Solve time: 1m50s
Yes.
The proof that Algorithm S terminates depends on the fact that every transformation in step S5 strictly decreases the quantity used as a descent measure. With the modified rule, equality is also transformed. If
$$ 2|V_i\cdot V_j|=V_j\cdot V_j $$
and $q=\pm1$, then
$$ (V_i-qV_j)\cdot(V_i-qV_j) =V_i\cdot V_i-2q(V_i\cdot V_j)+V_j\cdot V_j =V_i\cdot V_i . $$
Thus the length of $V_i$ is unchanged. The strict decrease used in the termination argument disappears.
A concrete example is provided by the hexagonal lattice, with basis vectors $A,B$ satisfying
$$ A\cdot A=B\cdot B,\qquad A\cdot B=\frac12,B\cdot B . $$
The modified step S5 replaces $A$ by $A-B$. The new pair $(A-B,B)$ again satisfies the same equality condition (up to permutation and sign), and further applications of the modified rule move among the six minimal bases
$$ \pm A,\ \pm B,\ \pm(A-B), $$
without decreasing the reduction measure. Hence the algorithm can revisit a previous state and repeat indefinitely.
Therefore the modified version of Algorithm S can get into an infinite loop. ∎