python-lll-lattice-basis-reduction-exact-rational-gso

Answer

The solution is complete and verified. Here's a summary of what was diagnosed and delivered.

Deliverable

SOLUTION.md — self-contained markdown with title, root-cause analysis, full exact-rational LLL implementation, and a verification section.

Supporting files used to produce/verify it: - lll_exact.py — the exact-rational LLL (Fraction-based GSO, classical size reduction, exact Lovász test, unimodular certificate U). - test_lll.py — runnable test suite.

Both code blocks embedded in SOLUTION.md are byte-identical to these files (diff-checked).

Root cause

LLL's control flow is a sequence of exact rational predicates: |mu| > 1/2, nearest_int(mu), and B[k] ≥ (delta − mu²)·B[k−1]. Evaluating them in float64 lets rounding flip a swap decision. Since termination relies on the integer potential Π B[i] strictly decreasing at each swap, one flipped comparison causes cycles or non-reduced output.

I searched for and confirmed a concrete failure:

b1 = (2N, 0, 0),  b2 = (N-1, N, N+1),  N = 10^9
exact Lovász margin = +2  (>0, no swap)
float64 margin      = -256.0 (<0, wrong swap)

This is exactly the rounding mechanism that makes naive implementations loop on harder/near-degenerate instances.

Fix

Never leave the rationals: use fractions.Fraction for mu, B, b*, and the working basis. Round-half-away-from-zero is done on an exact Fraction, and the Lovász test is an exact comparison. Carry an integer matrix U (starts as I) through every row operation/swap, so working_basis == U @ input holds at every intermediate step, with |det U| = 1 checked by Bareiss.

Verification (all pass)

• Classic 3×3 hard lattice → LLL-reduced + valid certificate.
• Near-degenerate basis with tiny later GSO norms.
• The N = 10^9 float-flip case → exact code decides correctly.
• 3000 randomized full-rank and rectangular bases (entries up to 10^6, delta ∈ [0.30, 1.00]): all LLL-reduced, all certificates valid, covolume preserved for square bases.
• delta outside (1/4, 1] rejected.

Run with python3 test_lll.py (≈28 s, FAILURES: 0).