Polynomial Complexity of Greedy Lattice Reduction

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

Polynomial time means a number of elementary steps bounded by a polynomial in the encoded input length. A decision problem is in $\mathrm{NP}$ if yes-instances have polynomial-length certificates verifiable in polynomial time; NP-hardness is under polynomial-time reductions.

A lattice generated by independent vectors $b_1,\ldots,b_d$ is $L=\{\sum_i z_i b_i:z_i\in\mathbb Z\}$. SVP seeks a shortest nonzero lattice vector; SIVP seeks $d$ independent short vectors, with approximation measured against the relevant successive minimum.

Statement recorded in the supplied source.

Does the greedy lattice-reduction algorithm have polynomial-time complexity in every dimension $d\geq6$? [S2]

Scope qualification.

The exact greedy algorithm and bit-complexity model are those of the source; polynomial dependence on dimension alone is not substituted for polynomial dependence on encoded input size.

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Determine whether the specified greedy lattice reduction algorithm runs in polynomial time in every dimension at least six.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30000164 (OWR-782-005). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Gitter und Anwendungen $2005$, Oberwolfach Reports, DOI 10.4171/owr/2005/01, pp. 5--67 https://doi.org/10.4171/owr/2005/01.
• S3 Nguyen--Stehle, lattice reduction https://perso.ens-lyon.fr/damien.stehle/downloads/PubANTS6.pdf. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30000164 and source code OWR-782-005 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The report's greedy-reduction discussion was consulted together with Nguyen--Stehle's primary paper Low-Dimensional Lattice Basis Reduction Revisited, especially its algorithm in Figure 4. The paper gives stronger low-dimensional analyses; those proofs are not reproduced or claimed as new. The following studies the same closest-vector and reinsertion loop on an integer basis. Counting calls to a closest-vector routine is separated from the cost of implementing those calls.

Research attempt: Integer descent and the missing bit-complexity bound

The loop and an elementary termination bound

Let $b_1,\ldots,b_d\in\mathbb Z^m$ be independent and ordered by nondecreasing Euclidean length. Set $k=2$. Find a closest vector $c$ to $b_k$ in the lattice generated by $b_1,\ldots,b_{k-1}$, and replace $b_k$ by $b_k-c$. If its new length is at least $\lVert b_{k-1}\rVert$, increase $k$ by one. Otherwise insert the changed vector at its length rank $k'<k$, shift the intervening vectors right, and set $k=k'+1$. Stop when $k=d+1$. Any fixed convention among equal lengths suffices. Subtracting a prefix lattice vector and permuting preserve the lattice and independence.

The integer potential $P=\sum_i\lVert b_i\rVert_2^2$ cannot increase: $c=0$ is an available competitor in every closest-vector call, and permutation leaves $P$ unchanged. Before a backward reinsertion the old vector's length was at least that of its predecessor; after the shortening it is strictly less than that predecessor. Thus its squared length, and hence $P$, drops by at least one. All nonzero integer vectors have squared length at least one, so the number $D$ of backward-reinsertion events is at most $P_0-d$.

Let $U$ count the iterations which increase $k$. A backward event changes $k$ by a value in $[-(d-2),0]$. The net change from $2$ to $d+1$ is $d-1$, whence \[ U\leq d-1+(d-2)D,\qquad U+D\leq(d-1)(1+D)\leq d(1+P_0). \] This also proves termination: infinitely many iterations would require either infinitely many backward events, contradicting the potential bound, or infinitely many increases of the bounded index. If the initial vector lengths are at most $B$, the number of closest-vector calls is at most $d(1+dB^2)$.

Why this does not establish polynomial bit complexity

Coordinates of magnitude $B$ require only order $\log(2+B)$ bits each. A bound polynomial in $B$ can therefore be exponential in the encoded input length, even at fixed dimension. The estimate also treats exact closest-vector computation as a subroutine and proves no polynomial cost for it when dimension varies. Clearing denominators for rational input gives an integer basis and finite termination, but can enlarge the numerical potential substantially; it does not repair this gap.

A tempting refinement would require a uniform multiplicative decrease at every nontrivial shortening. It fails already for the integer basis \[ b_1=(2,0),\qquad b_2=(2,M),\qquad M\geq2. \] The exact closest prefix vector is $(2,0)$, and the new second vector is $(0,M)$. Its squared length ratio is $M^2/(M^2+4)$, tending to one. The total potential ratio is $(M^2+4)/(M^2+8)$, also tending to one. Thus no fixed decrease factor follows from a successful closest-vector subtraction alone. This example ends promptly; it is not evidence of a long execution. A polynomial analysis would need an amortized geometric invariant or stronger structural control over the backward events, together with a bit-cost analysis of the subroutine. Those are precisely the missing steps in this attempted descent route.

Verification and adversarial audit

The argument counts a reinsertion with $k'=k-1$ as a backward event even though the reset index is unchanged; strict potential descent still holds. Ties without shortening cause an index increase and cannot create an infinite loop. The example has independent integer columns and an exact closest vector, including $M=2$, where the post-shortening lengths tie. No exponential lower bound on the actual algorithm is inferred from an exponential upper bound.

Audit corrections.

Distinguished fixed-dimensional and varying-dimensional costs, closest-vector calls and their implementation, and numerical magnitude versus bit length.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

This is a rederivation of elementary finite termination and a numerical-size bound, plus a counterexample to a proposed per-step contraction premise. It does not establish or refute polynomial running time for any of the requested dimensions $d\geq6$, and does not replace the source's algorithm by a different reduction method.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/45975 (consulted 2026-10-11).
• https://perso.ens-lyon.fr/damien.stehle/downloads/lowdim-final.pdf (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.