Source-linked AI summary
The complexity of computing the covering radius of a Euclidean lattice
Frank Vallentin
TL;DR
The note studies the complexity of deciding the covering radius of a Euclidean lattice. It reduces quantified 3-SAT to this problem using a perturbation-based lattice construction, and proves that the covering radius problem is ΠP₂-complete.
Problem
The note asks how computationally difficult it is to decide whether a Euclidean lattice's covering radius is at most a given threshold.
Source: §1 · p. 1Method
A polynomial-time reduction from quantified 3-SAT uses perturbed lattices to translate a max–min quadratic gap into a covering-radius gap.
Source: §1 · p. 2, §3.2 · p. 5, §4 · p. 6Results
The covering radius problem is ΠP₂-complete.
Source: §1 · p. 1Takeaways & Limitations
The note establishes a completeness classification for the exact Euclidean covering radius problem at the second level of the polynomial hierarchy.
Source: §1 · p. 1
Abstract
from arXiv · showhide
In this note, we prove that the covering radius problem for Euclidean lattices is complete for the second level of the polynomial hierarchy. The note also documents the author's first experiment with generative AI as a tool for mathematical research.
1. Introduction
The note studies the complexity of deciding whether a Euclidean lattice has covering radius at most a given threshold. It proves that this problem is ΠP₂-complete, using a polynomial-time reduction from quantified 3-SAT.
1. Introduction
- The covering radius problem is ΠP₂-complete.The decision problem asks whether μ(BZ^n) ≤ r for an invertible rational matrix B and positive rational r.Source: §1 · p. 1
- Prior work established CRP membership in ΠP₂ and hardness results for other ℓp norms, but exact Euclidean hardness remained open.Guruswami, Micciancio, and Regev established membership; Bennett and Ly emphasized the open exact Euclidean case.Source: §1 · p. 1
- The reduction from quantified 3-SAT proceeds through a max–min quadratic optimization problem and a family of perturbed lattices.The construction perturbs orthogonal direct sums of copies of D4 and Z, then proves the reduction correct.Source: §1 · p. 2
2. Quantified 3-SAT and quadratic optimization
The reduction starts from quantified 3-SAT, asking whether every assignment to universal variables admits an existential assignment satisfying all clauses. It encodes clause violations with a max–min quadratic objective whose values separate YES and NO instances.
2. Quantified 3-SAT and quadratic optimization
- Quantified 3-SAT asks whether every assignment to universal variables X admits an assignment to existential variables Y satisfying all clauses.A NO instance has an assignment to X for which every assignment to Y violates at least one clause.Source: §2 · p. 2
- The reduction restricts to hard instances with p ≥ 1, m ≥ 1, and exactly three literals on distinct variables in every clause.Clause simplifications and padding preserve formula truth while enforcing these conditions.Source: §2 · p. 2
- Minimizing each clause's quadratic term gives 9 when all three literals are false and 1 otherwise, so the sum records clause violations.Each clause receives its own auxiliary variable Zj, which occurs in only one summand.Source: §2 · p. 2
- The max–min value equals m for a YES instance and is at least m + 8 for a NO instance.The objective separates the two quantified 3-SAT cases by a gap of at least eight.Source: §2 · p. 3
3. Lattices and perturbations
The section identifies deep holes through the Voronoi geometry of D4, then shows that small linear perturbations of a product lattice yield a max–min quadratic characterization of its squared covering radius, up to controlled error.
3.1. The geometry of the root lattice D4.
- The D4 Voronoi cell is the regular 24-cell, whose 24 unit-norm vertices are deep holes and fall into three classes modulo D4 translation.These facts give µ(D4)=1.Source: §3.1 · p. 3
- For each u∈{0,+,−}, the eight nearest lattice points to cu form a regular cross-polytope.Source: §3.1 · p. 3
3.2. The perturbation lemma.
- The deep holes of L0 are represented by hu=(cu1,…,cup,1/2,…,1/2), with each ui∈{0,+,−}.The proof selects a maximum-coefficient Voronoi vertex in each D4 summand and the nearer endpoint in each Z summand, then applies the triangle inequality.Source: §3.2 · pp. 4–5
- A(T) is the largest squared distance to TL0 attained at images of L0’s deep holes.The images are indexed by u∈{0,+,−}^p.Source: §3.2 · p. 4
- Under the perturbation bounds, a nearest point to each image of a deep hole remains the image of one of its original nearest lattice points.The proof separates the original nearest displacements from all others using their squared-distance gap.Source: §3.2 · p. 4
- If ∥T−I∥₂≤ε≤1/(100d), then µ(TL0)² equals R plus a max–min quadratic value up to error at most 17ε²d².Here R=d/4, and the quadratic term is max_u min_v∈Su 2v⊤Nv.Source: §3.2 · pp. 4–5
4. Proof of the main theorem. The Reduction.
The reduction encodes quantified 3-SAT in lattice geometry and uses a small perturbation to create a covering-radius gap. The disclosure recounts the role of generative AI in finding and refining the proof.
4. Proof of the main theorem. The Reduction.
- The reduction’s max–min objective has value ηΦ = 0 for YES formulas and ηΦ ≥ 1 for NO formulas, turning the clause gap into a covering-radius gap.Source: §4 · p. 6
4.1. A homogeneous quadratic encoding.
- The quadratic encoding selects vectors for universal assignments and uses existential and auxiliary coordinates in clause squares, whose minimized values count violated clauses.Source: §4 · p. 6, §4.1 · p. 7
4.2. The perturbation and the covering-radius gap.
- The quadratic form is scaled by δ = 1/(100d^6) to form T = I + δHΦ; the proof checks T is invertible before applying the perturbation bound.Source: §4.2 · p. 8
- YES instances satisfy µ(TL0)^2 < R − 2δ, while NO instances satisfy µ(TL0)^2 ≥ R + 4δ, separating the covering-radius cases.Source: §4.2 · p. 8
Disclosure of AI usage
- The author reports that AI first produced a cold-spot hardness proof, then helped adapt it to CRP; the author later simplified the proof and took responsibility for the note.Source: Disclosure of AI usage · p. 9