SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules

SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules

arXiv:2609.01469v1 [cs.CC] 1 Sep 2026

Jiaqi Liu

Yansong Feng

Yanbin Pan

State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Beijing, China {ljqi,fengyansong,panyanbin}@amss.ac.cn

Abstract Let q range over primes congruent to 3 modulo 4. Let ζq be a primitive qth root of unity, and put K = Q(ζq ), with ring of integers OK = Z[ζq ]. We prove that the decision version of the Shortest Vector Problem (SVP) in the ℓ2 -norm is NP-complete on full-rank free submodules of 2 OK by a deterministic polynomial-time many-one reduction from Exact Cover by 3-Sets (X3C). The module rank is fixed at two. As a Z-lattice, the module has rank 2(q − 1), which grows with q. The main obstacle is closure under the action of OK . A module containing a nonzero vector also contains every scalar multiple of that vector by a nonzero element of OK , and some of these multiples may be shorter. Three ideas overcome this obstacle. First, we map the Bennett–Peikert Reed–Solomon lattice to a principal cyclotomic ideal and use Wan’s point-count estimates to prove that a coset of this ideal contains many binary coefficient representatives. Second, a checker based on a quadratic Gauss sum turns the X3C equations into a canonical squared norm. Third, the checker and a second module coordinate combine with a separation bound for ideal cosets to rule out every unintended vector created by the OK -action. Each constructed instance consists of a prime q ≡ 3 (mod 4), two integral generators whose 2 × 2 generator matrix has nonzero determinant, and an integer squared threshold. The construction also gives NP-hardness of search-SVP under polynomial-time Turing reductions.

1

Introduction

A lattice L ⊆ Rm is the set of all integer linear combinations of linearly independent vectors. Given a basis of L, the decision shortest vector problem (SVP) asks whether the lattice contains a nonzero vector of squared norm at most a given threshold. Its search version asks for a shortest nonzero lattice vector. In 1981, Van Emde Boas asked whether exact SVP is NP-hard [vEB81]. Later, Ajtai’s breakthrough result established that exact Euclidean SVP is NP-hard under randomized reductions [Ajt98]. For Euclidean SVP, later randomized reductions gave hardness within 1 + n−ε for √ every fixed ε > 0, within every constant below 2, and within every constant factor [CN98, Mic01, Kho05, Mic12]. Stronger randomized-time assumptions yield superconstant and almost-polynomial factors [Kho05, HR12]. However, a deterministic NP-hardness proof for exact Euclidean SVP remained open for decades. Along one route, Hair and Sahai used probabilistically checkable proofs (PCPs) to obtain deterministic hardness for ℓp -norms with p > 2 and, under a subexponential-time assumption, approximation hardness for every finite p [HS26b, HS26a]. In two recent preprints, Wan proved deterministic hardness for every constant approximation factor in the Euclidean norm [Wan26a], extending an √ earlier result for factors below 2, including the exact problem [Wan26b]. At an intuitive level, Micciancio’s local-density program asks for an explicit lattice L and a coset t + L containing many points of norm strictly below λ1 (L) [Mic01, Mic12]. The minimum of L protects the soundness gap, while the abundance of short coset points allows the reduction to encode a solution to the input problem. For derandomization, these points must realize every prescribed assignment on a designated set of coordinates. Bennett and Peikert proposed a transparent candidate by lifting Reed–Solomon codes [BP23]. Wan used finite-field point counts to prove that an explicit Reed–Solomon coset has the required representatives with prescribed coordinates [Wan26b]. Wan’s result supplies the local-density statement needed for deterministic hardness results for general lattices in the ℓ2 -norm. It does not by itself show that the reduction remains sound when the output is required to have a prescribed cyclotomic module structure. Under the canonical embedding of a number field, ideals yield ideal lattices [LPR13a]. Higherrank modules similarly yield module lattices [LS15, FPMS22]. The ring action supports compact representations and fast arithmetic [HPS98, LPR13b], underlies Ring-LWE and ModuleLWE [LPR13a, LS15], and enables specialized algorithms for module lattices [LPMSW19]. This algebraic structure is no longer just a theoretical design choice. In 2024, NIST standardized ML-KEM (FIPS 203), a module-lattice-based scheme derived from CRYSTALS–Kyber and based on Module-LWE [BDK+ 18, Nat24b]. It also standardized ML-DSA (FIPS 204), derived from CRYSTALS–Dilithium and relying on Module-LWE and a variant of Module-SIS [DKL+ 18, Nat24a]. The cryptographic importance of module lattices has motivated broad work on structured lattices. Prior work studies cyclic-lattice problems [Mic07], module unique-SVP and NTRU [FPMS22], probabilistic reductions for approximation problems from arbitrary modules to free modules [MMPMT23], worst-case to average-case reductions for the approximate shortest independent vectors problem (SIVP) at fixed module rank under the Extended Riemann Hypothesis [dBPTW26], and the geometry of shortest vectors in random modules [GSVV25]. To the best of our knowledge, none of these results establishes NP-hardness of exact Euclidean SVP for rank-two modules under deterministic polynomial-time reductions. Most closely related to the present question, a recent preprint proves that exact Euclidean decision-CVP is NP-complete on coefficient lattices of nonzero principal ideals in power-of-two cyclotomic rings, with a lift to principal cyclic ideal lattices [LFP26]. This leads to the question addressed in this work: Is Euclidean SVP NP-hard for rank-two modules over cyclotomic rings? 2 . We answer this question affirmatively, even for full-rank free submodules of OK 1

1.1

Our result

For every prime q ≡ 3 (mod 4), let ζ := ζq be a primitive qth root of unity. Write K := Q(ζ) and OK := Z[ζ]. For x = (x1 , x2 ) ∈ K 2 , define ∥x∥2 :=

X

|σ(x1 )|2 + |σ(x2 )|2

σ:K,→C 2 is called full rank if it has finite index for the canonical product norm. An OK -submodule M ⊆ OK 2 in OK . We consider the following decision problem. An input consists of a prime q ≡ 3 (mod 4), 2 with det[ m m ] ̸= 0, and an integer S ≥ 0. Each of the four ring two vectors m1 , m2 ∈ OK 1 2 coordinates of m1 and m2 is specified by its q − 1 integer coefficients in the basis 1, ζ, . . . , ζ q−2 . For M := OK m1 + OK m2 , the question is whether

λ1 (M)2 ≤ S. We call this problem decision-SVP in the ℓ2 -norm on rank-two cyclotomic modules. The determinant 2 generated by two vectors. condition makes M a full-rank free submodule of OK Theorem 1.1. As q ranges over primes congruent to 3 modulo 4, decision-SVP in the ℓ2 -norm on rank-two cyclotomic modules is NP-complete. The hardness holds under deterministic polynomialtime many-one reductions. Our reduction is from Exact Cover by 3-Sets (X3C), which is NP-complete [GJ79]. Given an X3C instance, the reduction outputs a tuple (q, m1 , m2 , S) of the form above. Here q ≡ 3 (mod 4) 2 generate the output module and have nonzero determinant, and S is an is prime, m1 , m2 ∈ OK integer squared threshold. The tuple has polynomial encoding length. The generator construction and the denominator-clearing argument appear in Section 5.3. Section 5.4 chooses q and computes an integer basis whose Euclidean lattice is isometric to the canonically embedded output module. This basis is used by the NP verifier and the search reduction. 2 . As a Z-lattice, the The output module is a full-rank free submodule of the rank-two module OK output module has rank 2(q − 1). The same construction also gives the search consequence stated below. This is a worst-case hardness result in which the cyclotomic ring varies with q. The theorem does not establish hardness for a single fixed cyclotomic ring, for the power-of-two cyclotomic family, on average, or through a cryptographic security reduction. Corollary 1.2. As q ranges over primes congruent to 3 modulo 4, search-SVP in the ℓ2 -norm on full-rank free rank-two OK -module lattices is NP-hard. The hardness holds under polynomial-time Turing reductions.

1.2

Proof overview

Our goal is to give a deterministic polynomial-time reduction from X3C to decision-SVP on ranktwo modules over cyclotomic rings. Before clearing denominators, the reduction constructs an intermediate rank-two OK -module M ⊂ K 2 and a squared threshold S such that λ1 (M)2 ≤ S

⇐⇒

the X3C instance is positive.

2 and an integer squared A common integer scaling later produces the integral output module in OK threshold without changing this equivalence. The main challenge is to prove the strict lower bound λ1 (M)2 > S for every negative instance despite closure under multiplication by OK .

2

X3C asks whether a given matrix A ∈ {0, 1}M ×n admits a vector ξ ∈ {0, 1}n satisfying Aξ = 1M ,

(1)

where 1M is the all-one vector in {0, 1}M . The proof of the reduction has three layers. First, it extends ξ to a binary coefficient vector x and evaluates x at ζ to obtain an element of one fixed ideal coset in OK . Second, it transforms this element into an X3C checker expression whose squared norm measures Aξ − 1M . Third, it places the checker expression in a rank-two module. Writing a module vector as an OK -linear combination of the two generators introduces a coefficient w ∈ OK for the second generator. Completeness uses the intended choice w = 1, whereas soundness must control every possible w ∈ OK . The ideal coset. The first step embeds ξ ∈ {0, 1}n into x = (xa )a∈Fq ∈ {0, 1}Fq . The reduction chooses distinct field elements α1 , . . . , αn ∈ Fq and stores ξj in the coordinate xαj . Let ζ := ζq be a primitive qth root of unity and put π := 1 − ζ. For a chosen integer k, define a := π k OK . For x = (xa )a∈Fq ∈ ZFq , evaluation at ζ gives the corresponding ring element vx :=

X

xa ζ a ∈ OK .

a∈Fq

By Theorem 3.2, which uses the Bennett–Peikert minimum bound [BP23], evaluation maps the Reed–Solomon lattice to a and λ1 (a)2 ≥ 2kq. Wan’s point-count estimate [Wan26b], in the uniform form of Theorem 3.4, supplies many binary vectors whose ring elements lie in a fixed coset. The reduction chooses one coset c + a. By Lemma 3.3 and Theorem 3.4, every ξ ∈ {0, 1}n has many extensions x ∈ {0, 1}Fq such that vx ∈ c + a,

X

xa = h,

xαj = ξj

(1 ≤ j ≤ n),

a∈Fq

where h is the prescribed Hamming weight. Thus xαj = ξj stores ξ in designated coordinates of x, while vx places the resulting ring element in the fixed ideal coset. This encoding does not yet test Equation (1). The X3C checker. The second step encodes Equation (1) in the canonical norm. The reduction constructs U, V ∈ K. By Theorem 4.4, every weight-h binary vector x, with ξj = xαj , satisfies ∥U vx − V ∥2 = B0 + 2∥Aξ − 1M ∥22 + E(x).

(2)

Here B0 depends only on the constructed instance, and E(x) ≥ 0 collects the additional terms not determined by ξ. Thus U vx − V is the checker value whose squared norm encodes the residual Aξ − 1M . We call a representative x clean if it satisfies the correlation conditions in Section 4.3, and these conditions imply E(x) = 0. The uniform coset count in Theorem 3.4 and the union bound in the proof of Theorem 4.5 show that every ξ ∈ {0, 1}n has a clean coefficient vector x with vx ∈ c + a. Consequently, an exact cover gives squared checker norm B0 , whereas every binary coefficient vector in a negative instance has squared checker norm at least B0 + 2. The rank-two module. The third step places the checker value in a module. Choose a positive integer Γ to control the second module coordinate. Define the rank-two OK -submodule of K 2 M := OK (U π k , 0) + OK (U c − V, −Γ) ⊂ K 2 . 3

Every vector in M has the unique form v(z, w) := U (π k z + wc) − V w, −Γw ,

z, w ∈ OK .

(3)

When w = 1 and π k z + c = vx , the first coordinate is the checker value U vx − V . For arbitrary w, the element π k z + wc lies in wc + a, and the first coordinate is U (π k z + wc) − V w. The second coordinate contributes Γ2 ∥w∥2 to the squared norm. Set S := B0 + Γ2 (q − 1). If ξ is an exact cover, choose a clean coefficient vector x and write vx = π k z + c. Taking w = 1 in Equation (3) then gives ∥v(z, 1)∥2 = S. Soundness under multiplication. It remains to control all vectors in this module when the X3C instance is negative. The main issue is possible cancellation between U (π k z + wc) and V w. Set y := π k z + wc ∈ wc + a. Then ∥y∥ ≥ dist(wc, a). The stability estimate in Lemma 5.1 gives an explicit ν = o(1) and the following lower bound for the squared norm of the module vector. ∥U y − V w∥2 + Γ2 ∥w∥2 ≥ (1 − ν) ∥y∥2 + Γ2 ∥w∥2 .

(4)

This inequality transfers the geometric bounds from the ideal cosets to the module. The argument considers four cases. (i) If w = 0, Part (iii) of Lemma 4.3 gives ∥U y∥ ≥ ∥y∥. This preserves the lower bound for the minimum of a and puts every nonzero vector above S. (ii) If w is a root of unity, write y = wu with u ∈ c + a. Multiplication by w is an isometry. Let x be the integral coefficient representative of u from Lemma 3.6. If x is binary, the checker identity gives a squared first-coordinate norm at least B0 + 2 in a negative instance. If x is not binary, Lemma 3.6 gives ∥u∥2 ≥ H + 2q. Applying Equation (4) to u and 1 therefore puts the module vector above S. (iii) If w is not a root of unity and 0 < ∥w∥2 ≤ 3q, Theorem 3.8 separates wc from a, while Lemma 3.9 gives ∥w∥2 ≥ 2q − 4. These bounds and Equation (4) put the module vector above S. (iv) If w is not a root of unity and ∥w∥2 > 3q, the coordinate −Γw alone puts the module vector above S. Organization. Section 2 recalls Euclidean lattices, prime cyclotomic rings, X3C, and Sidon sequences, and records the power-sum estimates used to count binary representatives in ideal cosets. Section 3 maps the lifted Reed–Solomon lattice to a principal cyclotomic ideal, proves the fixed-coordinate count, and establishes the norm-separation bounds used for soundness. Section 4 constructs the X3C checker and proves the existence of clean completions. Section 5 gives the main reduction. It assembles the rank-two module, proves completeness and soundness, clears denominators, and establishes the claimed input representations and complexity bounds.

2

Preliminaries

Notation. For a positive integer r, write [r] := {1, . . . , r}. For a prime q, let Fq denote the finite field with q elements, and let F× q := Fq \ {0} denote its multiplicative group. Vectors and matrices are represented in bold, e.g., v for a vector and A for a matrix, while their scalar coordinates are not. We use ∥ · ∥2 for the ℓ2 -norm and 1r for the vector of ones in Rr . 4

Hasse derivatives. We will use Hasse derivatives in Section 3 to recognize when a polynomial P has a zero of prescribed order at X = 1. Let F be a field, let f (X) = di=0 ci X i ∈ F [X], and let j ≥ 0 be an integer. The jth Hasse derivative of f is [j]

D f (X) :=

d X i=j

!

i ci X i−j , j

where each integer binomial
coefficient is read as an element of F . We also use the binomial
polynomials X0 := 1 and Xj := X(X − 1) · · · (X − j + 1)/j! ∈ F [X] for j ≥ 1 whenever j! ̸= 0 in F . For b ∈ F and an integer k ≥ 1, we say that b is a zero of order at least k when (X − b)k divides f (X). The following standard characterization will be used [LN97]: (X − b)k | f (X)

2.1

⇐⇒

D[j] f (b) = 0

(0 ≤ j < k).

(5)

Euclidean lattices

A Euclidean lattice of rank n is a discrete additive subgroup L ⊆ Rm of the form L = L(B) := BZn , where B ∈ Rm×n has linearly independent columns. These columns form a basis. The first minimum of L is the length of a shortest nonzero lattice vector: λ1 (L) = min ∥v∥2 . 0̸=v∈L

For computational problems, the basis B ∈ Qm×n is given explicitly. Exact decision-SVP also receives a nonnegative rational squared threshold ∆ and asks whether λ1 (L(B))2 ≤ ∆. The problem belongs to NP: a YES certificate is a nonzero integer coefficient vector for a short lattice point. Standard cofactor bounds give a certificate of polynomial bit length, and exact rational arithmetic checks both membership and the squared norm. See, e.g., [MG02]. The corresponding search-SVP problem takes a full-column-rank basis B and outputs a shortest nonzero vector of L(B).

2.2

Prime cyclotomic fields and module lattices

Cyclotomic field. Fix an odd prime q for the remainder of the construction, and let ζ := ζq ∈ C be a primitive qth root of unity. We suppress the subscript q after fixing the prime and put K := Q(ζ),

OK := Z[ζ],

π := 1 − ζ.

Here OK is the ring of integers of K. The elements 1, ζ, . . . , ζ q−2 form an integral basis of K, so [K : Q] = q − 1. The prime q is totally ramified in OK , and hence (q) = (π)q−1 [Was97]. Whenever a ∈ Fq occurs as an exponent of ζ, we identify it with its unique integer representative in P {0, . . . , q − 1}. A representation v = a∈Fq ca ζ a with ca ∈ Q is called a q-coordinate expression for P v. Its q coefficients are indexed by Fq and need not be unique, because a∈Fq ζ a = 0. By contrast, the expression of v in the power basis 1, ζ, . . . , ζ q−2 is unique.

5

Canonical embedding. For v ∈ K, write v for its complex conjugate. In particular, ζ = ζ −1 . a For a ∈ F× q , let σa : K ,→ C be the embedding defined by σa (ζ) = ζ . These are all the embeddings of K. The field trace is X TrK/Q (v) := σa (v). a∈F× q

The canonical embedding sends v to (σa (v))a∈F× . For each integer s ≥ 1, we equip K s with the real q inner product ⟨x, y⟩ := Re

s X X

σa (xi )σa (yi )

i=1 a∈F× q

and its induced product norm ∥x∥2 := ⟨x, x⟩ =

s X

TrK/Q (xi xi ).

i=1

For s = 1, this is the canonical norm on K: ∥v∥2 =

X

|σa (v)|2 = TrK/Q (vv).

a∈F× q

The roots of unity in K are exactly ±ζ j for 0 ≤ j < q [Was97]. If ε is a root of unity, then ∥εx − εy∥ = ∥x − y∥ for all x, y ∈ K s . Thus multiplication by ε is an isometry. In particular, it preserves distances. Module lattices. For an integer s ≥ 1, an OK -module lattice in K s is a finitely generated OK -submodule M ⊆ K s , equipped with the componentwise canonical embedding and the product norm. It has full rank if its K-span is K s . When s = 1, a nonzero ideal a ⊆ OK gives a module lattice in K called an ideal lattice. Both module and ideal lattices are discrete additive subgroups of their real spans. In this paper, we only use free module lattices of full rank. If m1 , . . . , ms ∈ K s are linearly independent over K, then M = OK m1 + · · · + OK ms is free of module rank s, has full rank, and has Z-rank s(q − 1). The square matrix with columns m1 , . . . , ms has nonzero determinant precisely when these vectors are linearly independent over K. s , then full rank is equivalent to finite index in O s . If M ⊆ OK K The first minimum of an ideal lattice or module lattice is the length of its shortest nonzero vector in the canonical or product norm. For v ∈ K and an ideal lattice a, define dist(v, a) := min ∥v − y∥. y∈a

Coefficient representatives.

For z = (za )a∈Fq ∈ Qq , write [z] :=

X

za ζ a ∈ K.

a∈Fq

If z ∈ Zq , then [z] ∈ OK , and we call z an integral coefficient representative of [z]. Since Φq (X) = 1 + X + · · · + X q−1 is the minimal polynomial of ζ, two integral coefficient vectors represent the same element precisely when they differ by an integer multiple of 1q . The following identity converts the canonical inner product and norm into calculations with these q coefficients. 6

Lemma 2.1. For all rational coefficient vectors x, y ∈ Qq , !

⟨[x], [y]⟩ = q

X

X

xa ya −

a

! X

xa

a

ya .

a

In particular, for every z ∈ Zq , !2 2

∥[z]∥ = q

X

X

za2 −

a

za

=

a

X

(za − zb )2 .

a<b

Proof. For a, b ∈ Fq , additive-character orthogonality gives ( X

ζ

t(a−b)

=

t∈F× q

q − 1, −1,

a = b, a ̸= b.

Hence, for rational coefficient vectors x and y, !

⟨[x], [y]⟩ = q

X

xa ya −

a

X

x a yb = q

X

a,b

Taking x = y = z gives the norm identity. Expanding

2.3

x a ya −

a

X

xa

! X

a a<b (za − zb )

P

yb .

b 2 gives its final form.

X3C and Sidon sequences

An Exact Cover by 3-Sets (X3C) instance consists of a universe [M ] and three-element sets C1 , . . . , Cn ⊆ [M ]. Its incidence matrix A ∈ {0, 1}M ×n is defined by Aij = 1 when i ∈ Cj and Aij = 0 otherwise. A selection vector ξ ∈ {0, 1}n specifies a choice of sets, with ξj = 1 exactly when Cj is selected. We call ξ an X3C witness if Aξ = 1M . This equality says that every universe element belongs to exactly one selected set. The instance is positive exactly when it has an X3C witness. X3C is NP-complete [GJ79]. A universe element is isolated if it belongs to none of the sets Cj . An instance with an isolated element is negative. After handling this case separately, every row of A is nonzero and M ≤ 3n. Adjoining a disjoint three-element block together with its unique set preserves the answer, so we may also assume n ≥ 1. To index the n selection bits, we choose distinct nonnegative integers whose nonzero ordered differences are all distinct. Such a sequence is called a Sidon sequence. The following lemma gives a deterministic construction with largest entry O(n2 ). Lemma 2.2. For every n ≥ 1, one can deterministically compute integers 0 ≤ α1 < · · · < αn =: α⋆ ,

α⋆ = O(n2 ),

such that all nonzero ordered differences αℓ − αj , j ̸= ℓ, are distinct. Proof. Use the deterministic quadratic-residue Sidon construction of Erdős and Turán [ET41]. For an explicit construction and the verification of the directed-difference property, see also Liu–Feng– Pan [LFP26]. 7

2.4

Power-sum estimates

Let q be prime, let 2 ≤ k < m, and let b = (b1 , . . . , bk−1 ) ∈ Fk−1 . Define the power-sum solution set q (

Xk,m (b) :=

z = (z1 , . . . , zm ) ∈ Fm q :

m X

)

zrj = bj

(1 ≤ j < k) .

r=1

The following proposition records the uniform point-count bounds used below. Proposition 2.3 ([Wan26b]). Let q be prime and suppose that 2 ≤ k ≤ m − 2 < q − 2. For every b ∈ Fk−1 , the following estimates hold. q (i) 1 |Xk,m (b)| − q m−k+1 ≤ (2k)m q (m−k+2)/2 . 2 (ii) For distinct i, ℓ ∈ [m], 1 {z ∈ Xk,m (b) : zi = zℓ } − q m−k ≤ (2k)m−1 q (m−k+2)/2 . 2 (iii) For i ∈ [m] and a ∈ Fq , 1 {z ∈ Xk,m (b) : zi = a} − q m−k ≤ (2k)m−1 q (m−k+1)/2 . 2 All three estimates are uniform in b, and the last two are also uniform in the displayed choices of indices and field elements. Proof. Wan [Wan26b, Propositions 5.2 and 6.2] proves part (i) and proves part (ii) for z1 = z2 , respectively. The statements in that paper use one particular vector of prescribed power sums b. The displayed estimates and their proofs depend only on q, k, and m, so they hold uniformly for every b. For distinct i, ℓ ∈ [m], a permutation of the m coordinates sends the condition zi = zℓ to z1 = z2 P j and leaves each equation m r=1 zr = bj unchanged. Therefore Wan’s estimate for z1 = z2 proves part (ii) for every pair i ̸= ℓ. For part (iii), fix zi = a and delete that coordinate. The remaining m − 1 variables satisfy P j j r̸=i zr = bj − a for 1 ≤ j < k. Applying Wan’s first point-count estimate to these m − 1 variables proves part (iii).

3

Reed–Solomon lattices and ideal cosets

The first step of the reduction stores an X3C selection vector ξ ∈ {0, 1}n in designated coordinates P of a longer vector x ∈ {0, 1}Fq . Evaluation at ζ maps x to [x] = a∈Fq xa ζ a ∈ OK . The checker in Section 4 operates on fixed-weight binary vectors and reads xαj = ξj as the selection bits. Hence every ξ must admit a weight-h extension x whose evaluation lies in one fixed ideal coset. This coset is independent of ξ. The ideal is designed to have a large minimum, so that a nonzero ideal element cannot produce an unintended short vector. This section obtains such an ideal from a lifted Reed–Solomon lattice [BP23], proves that the required binary extensions exist even after their designated coordinates are fixed, and establishes the additional norm bounds needed for nonbinary representatives and scalar multiples. 8

3.1

From lattice to ideal

We first transfer an ℓ2 -minimum bound for the lifted Reed–Solomon lattice to a principal ideal of OK . Fix an ordering Fq = {a1 , . . . , aq } and index the coordinates of Zq accordingly. For 1 ≤ k < q, define   1 1 ··· 1  a a2 · · · aq   1   2 2 2  a a · · · a  q  ∈ Fk×q 2 Hq (k) :=  1 . q .. ..  ..  ..  .  . . .  ak−1 ak−1 ··· 1 2

ak−1 q

When Hq (k) is applied to z ∈ Zq , we first reduce the coordinates of z modulo q. The matrix Hq (k) defines the lifted Reed–Solomon lattice Lq,k := {z ∈ Zq : Hq (k)z = 0} . Lemma 3.1 ([BP23, Theorem 14]). Let q be prime and 1 ≤ k ≤ q/2. Then the first minimum of Lq,k with respect to the ℓ2 -norm ∥ · ∥2 satisfies λ1 (Lq,k )2 ≥ 2k. q T Write 1⊥ q := {z ∈ R : 1q z = 0}. To express the lattice equations and evaluation at ζ in the q same ring, associate z ∈ Z with

fz :=

X

za X a ∈ Z[X]/(X q − 1).

a∈Fq

Every element of this quotient has a unique degree-< q representative, which we use to define its coefficients and its reduction f¯ ∈ Fq [X] modulo q. Let φ : Z[X]/(X q − 1) −→ OK ,

X 7−→ ζ,

be the ring homomorphism given by evaluation at ζ. Its kernel is generated by Φq (X) = 1 + X + · · · + X q−1 , and φ(fz ) = [z]. Theorem 3.2. For 1 ≤ k ≤ q/2, {[z] : z ∈ Lq,k } = aq,k := π k OK . Moreover, the map z 7→ [z] restricts to an additive-group isomorphism Lq,k ∩ 1⊥ q −→ aq,k . Consequently, with respect to the canonical norm, λ1 (aq,k )2 ≥ 2kq. X Proof. Since k < q, the polynomials 1, X, . . . , X k−1 and X0 , X1 , . . . , k−1 are related by an invertible triangular change of basis over Fq . Hence the defining equations of Lq,k are equivalent to

D[j] f¯z (1) = 0

(0 ≤ j < k), 9

because D[j] f¯z (1) = a za aj in Fq . The multiplicity criterion in Equation (5) and the identity X q − 1 = (X − 1)q in Fq [X] therefore give P

{fz : z ∈ Lq,k } = q, (X − 1)k ◁ Z[X]/(X q − 1).

Applying φ gives the ideal (q, π k ). Total ramification gives (q) = (π q−1 ), so this image is (π k ) = aq,k since k ≤ q − 1. Furthermore, Φq (X) ≡ (X − 1)q−1 (mod q), so ker(φ) = (Φq ) is contained in (q, (X − 1)k ). Since φ((q, (X − 1)k )) = aq,k , it follows that φ−1 (aq,k ) = q, (X − 1)k

in Z[X]/(X q − 1).

(6)

To prove surjectivity of the restricted map, fix v ∈ aq,k . By Equation (6), choose f ∈ (q, (X − 1)k ) with φ(f ) = v. Then f (1) ∈ qZ, and g := f −

f (1) Φq q

remains in (q, (X − 1)k ), satisfies φ(g) = v, and has coefficient sum zero. Thus g = fz for some z ∈ Lq,k ∩ 1⊥ q . For injectivity, suppose that z ∈ Lq,k ∩ 1⊥ q and [z] = 0. The degree-< q representative of fz vanishes at ζ, so it equals ℓΦq for some ℓ ∈ Z. Its coefficient sum is zero, whereas Φq (1) = q. Thus ℓ = 0 and z = 0. Finally, every nonzero v ∈ aq,k has a unique nonzero z ∈ Lq,k ∩ 1⊥ q with v = [z]. By Lemmas 2.1 and 3.1, ∥v∥2 = q∥z∥22 ≥ 2kq, which proves the minimum bound.

3.2

Binary representatives in ideal cosets

For x ∈ Zq , its syndrome Hq (k)x ∈ Fkq has the coordinate indexed by j equal to a∈Fq xa aj modulo q for 0 ≤ j < k. When x is binary, these coordinates are the power sums of the positions a for which xa = 1. Lemma 3.3 identifies the vectors with fixed syndrome and coefficient sum with one coset of aq,k . P

Lemma 3.3. Assume 1 ≤ k ≤ q/2. Let u = (u0 , . . . , uk−1 ) ∈ Fkq , and let s ∈ Z have residue u0 modulo q. There exists xu,s ∈ Zq such that Hq (k)xu,s = u,

1T q xu,s = s.

Moreover, evaluation at ζ induces a bijection {x ∈ Zq : Hq (k)x = u, 1T q x = s} −→ [xu,s ] + aq,k ,

x 7−→ [x].

Thus every element of this ideal coset has a unique representative with syndrome u and coefficient sum s. Proof. A Vandermonde k × k minor of Hq (k) has determinant 1≤i<j≤k (aj − ai ) ̸= 0 in Fq . Hence the matrix has rank k. Choose x0 ∈ Zq whose reduction modulo q satisfies Hq (k)x0 = u over Fq . Its coefficient sum is congruent to u0 , and hence to s modulo q. The vector 1q belongs to Lq,k : its zeroth P power sum is q = 0 in Fq , and a∈Fq aj = 0 for 1 ≤ j < k < q − 1. Moreover, [1q ] = 0. Therefore Q

10

adding a suitable integer multiple of 1q to x0 gives a vector xu,s with the required coefficient sum without changing its syndrome or its image at ζ. Every other vector with syndrome u and coefficient sum s differs from xu,s by an element of Lq,k ∩ 1⊥ q . The restricted isomorphism in Theorem 3.2 now gives the stated bijection. We use the following parameters to specialize Proposition 2.3. For every sufficiently large prime q, put $ %   q 1/1000 201k k := , T := ⌊q 1/2000 ⌋. (7) , h := 2 200 These integers can be computed without real-number approximations. The value k is the largest nonnegative integer satisfying (2k)1000 ≤ q, and T is the largest nonnegative integer satisfying T 2000 ≤ q. Fixed-degree integer-root algorithms compute k and T in time polynomial in log q, after which integer division gives h. Here k is the number of rows of Hq (k). For each vector x ∈ {0, 1}Fq considered below, h is its weight, and T is the maximum number of its coordinates whose values may be fixed in advance. The relevant scale relations are T = o(k), h = (201/200)k + O(1), and h = o(q). Set H := h(q − h), L := 2kq. (8) By Lemma 2.1, every x ∈ {0, 1}Fq of weight h satisfies ∥[x]∥2 = H. By Theorem 3.2, every nonzero element of aq,k has canonical squared norm at least L. For a prescribed syndrome u = (u0 , . . . , uk−1 ), let P ⊆ Fq be the position set indexing the coordinates fixed in advance, and let η ∈ {0, 1}P specify their values. Define F(u; P, η) := {x ∈ {0, 1}Fq : Hq (k)x = u, 1T q x = h, x|P = η}. The first row of Hq (k) forces u0 = h in Fq . Theorem 3.4. For every sufficiently large prime q, every u ∈ Fkq with u0 = h, every position set P P ⊆ Fq with |P | ≤ T , and every η ∈ {0, 1}P , put t := a∈P ηa . Then q h−t−k+1 |F(u; P, η)| = Θ (h − t)!

!

.

(9)

Both the threshold for q and the implied constants are uniform in u, P , and η. Proof. Fix u, P , and η, and put m0 := h − t. By Equation (7), all sufficiently large q satisfy k + 2 ≤ m0 < q − 2. The fixed coordinates contain exactly t ones. Subtract their contribution by defining u′j := uj −

X

ηa aj

(1 ≤ j < k).

(10)

a∈P

Every x ∈ F(u; P, η) has exactly m0 coordinates outside P equal to one. Ordering their positions gives a tuple (z1 , . . . , zm0 ) ∈ (Fq \ P )m0 such that zi ̸= zℓ for every i ̸= ℓ and m0 X j

zi = u′j

(1 ≤ j < k).

(11)

i=1

Conversely, every pairwise distinct tuple in (Fq \ P )m0 satisfying Equation (11) determines a unique vector by setting xzi = 1, setting x|P = η, and setting all remaining coordinates to zero. The equation for j = 0 follows from u0 = h. Hence the number of these ordered tuples is m0 ! |F(u; P, η)|. 11

Let A count the tuples satisfying Equation (11) without requiring their entries to be pairwise distinct or to lie outside P . After the shift in Equation (10), part (i) of Proposition 2.3 gives A = q m0 −k+1 (1 + o(1)). We bound the excluded tuples in two cases. Case I (collision). For fixed i < ℓ, part (ii) of Proposition 2.3 shows that the number of solutions with zi = zℓ is O(q m0 −k ). P Case II (entry in P ). For fixed i and a ∈ P , substituting zi = a in Equation (11) gives r̸=i zrj = u′j − aj for 1 ≤ j < k. Part (iii) of Proposition 2.3 shows that the number of solutions with zi = a is O(q m0 −k ). The explicit error bounds in Proposition 2.3 are uniform in the prescribed power-sum vector (u′j )1≤j<k . For the parameters in Equation (7), each relative error is at most (2k)m0 q −(m0 −k−2)/2 = q −Ω(k) = o(1). Thus the estimate for A, the bound for zi = zℓ , and the bound for zi = a are uniform over all shifted power-sum vectors (u′j )1≤j<k
and all choices of i, ℓ, and a. The union bound over m20 equalities zi = zℓ and m0 |P | equalities zi = a with a ∈ P shows that the nonnegative difference satisfies 0 ≤ A − m0 ! |F(u; P, η)| = O (m20 + m0 |P |)q m0 −k .

After division by the main term q m0 −k+1 , this error is O((m20 + m0 |P |)/q) = o(1) by the scale relations following Equation (7). Together with the estimate for A, this gives m0 ! |F(u; P, η)| = q m0 −k+1 (1 + o(1)). Substituting m0 = h − t proves Equation (9). Corollary 3.5. Let u, P, η, and t be as in Theorem 3.4. For r ∈ {1, 2}, let Q ⊆ Fq \ P have size r ′ and satisfy |P | + r ≤ T . Put P ′ := P ∪ Q and extend η to η ′ ∈ {0, 1}P by setting ηa′ = 1 for every a ∈ Q. Then |F(u; P ′ , η ′ )| = O ((h/q)r ) . (12) |F(u; P, η)| The implied constant is uniform in u, P , η, and Q. Proof. For all sufficiently large q, t + r ≤ |P | + r ≤ T < h, so h − t − r ≥ 0. The numerator in Equation (12) counts exactly the vectors in F(u; P, η) that equal one at every coordinate in Q. Applying Theorem 3.4 to the numerator and denominator gives |F(u; P ′ , η ′ )| (h − t)! = O q −r |F(u; P, η)| (h − t − r)! 

3.3



= O ((h/q)r ) .

Norm separation

The preceding count supplies the intended binary representatives. To use their ideal coset in the module construction, we must rule out shorter representatives with nonbinary coefficients and short points arising from nonzero scalar multiples.

12

Lemma 3.6. Let u ∈ Fkq satisfy u0 = h, and let x′ ∈ Zq have syndrome u and coefficient sum h. Put c′ := [x′ ]. Every v ∈ c′ + aq,k has a unique integral coefficient representative z ∈ Zq satisfying [z] = v,

X

Hq (k)z = u,

za = h.

a

If z ∈ {0, 1}Fq , then it has weight h and ∥v∥2 = H. Otherwise, ∥v∥2 ≥ H + 2q. Proof. The existence and uniqueness of z follow directly from Lemma 3.3. By Lemma 2.1, ∥v∥2 = q

X

za2 − h2 = H + q

a

X

za (za − 1).

a

For every integer za , the quantity za (za − 1) is a nonnegative even integer. The sum is zero exactly when every za ∈ {0, 1}, and is otherwise at least two. This proves the stated claim. We next choose c so that wc remains separated from aq,k for every nonzero w ∈ OK with ∥w∥2 ≤ 3q. Define c ∈ OK and c + aq,k by k , 2

 

m :=

c := h + π m .

(13)

The scalar summand h fixes the coefficient sum at h, since h + (1 − X)m evaluates to h at X = 1. The term π m , with m = ⌊k/2⌋, balances the two orders of vanishing, m and k − m, that arise from the π k -divisibility condition. Thus each of the two sparse-polynomial arguments below retains k/2 + O(1) orders of vanishing. Let c ∈ Zq be the coefficient vector of h + (1 − X)m . Then [c] = c, and its syndrome uc := Hq (k)c ∈ Fkq satisfies (uc )0 = h. Thus Lemma 3.3 identifies the vectors of syndrome uc and coefficient sum h with the coset c + aq,k . The proof of Theorem 3.8 combines a sparse integral coefficient representative with a bound on the multiplicity of a sparse polynomial at X = 1. The next lemma records both facts. Lemma 3.7. The following statements hold. (i) If v ∈ OK and ∥v∥2 < q 2 /4, then v has an integral coefficient representative with at most 2∥v∥2 /q nonzero coefficients. (ii) If F (X) =

s X

ci X ai ∈ Fq [X]

i=1

is nonzero, where every ci ̸= 0 and the exponents ai ∈ {0, . . . , q − 1} are distinct, then its order of vanishing at X = 1 is at most s − 1. Proof. For (i), choose a coefficient vector z = (za )a∈Fq ∈ Zq with [z] = v. If no value occurs among the coordinates za more than q/2 times, then at least q 2 /4 unordered pairs have unequal coordinates, contradicting the last expression in Lemma 2.1. Subtract the most frequent coordinate value from every za . This does not change [z] = v. Let s be the number of nonzero coefficients in the resulting representative. The preceding argument gives s < q/2. Each pair formed by a nonzero coordinate and a zero coordinate gives sq ∥v∥2 ≥ s(q − s) ≥ , 2 13

which proves (i). For (ii), multiplicity at least s would make the first s Hasse derivatives vanish at one. The resulting homogeneous system has determinant det

ai j

!!

1≤i<ℓ≤s (aℓ − ai ) , Qs−1 j=0 j!

Q

= 0≤j<s, 1≤i≤s

which is nonzero in Fq : the exponents are distinct, and s ≤ q makes every factorial in the denominator nonzero. Hence every ci would vanish, a contradiction. With b := 1/100, the next theorem separates every short nonzero multiple of c from aq,k . Theorem 3.8. For all sufficiently large primes q, every nonzero w ∈ OK with ∥w∥2 ≤ 3q satisfies dist(wc, aq,k )2 > bL. Proof. We prove the theorem by contradiction. Suppose that there exist a nonzero w ∈ OK with ∥w∥2 ≤ 3q and an element e ∈ wc + aq,k such that ∥e∥2 ≤ bL = 2bkq. For sufficiently large q, both 2bkq and 3q are below q 2 /4. By part (i) of Lemma 3.7, choose integral coefficient representatives ze and zw of e and w with at most 4bk and 6 nonzero coefficients, respectively. Put fe := fze and fw := fzw . Since φ(h + (1 − X)m ) = c and e − wc ∈ aq,k , Equation (6) gives fe − fw h + (1 − X)m ∈ q, (X − 1)k .

Reducing modulo q and using X q − 1 = (X − 1)q in Fq [X] gives f¯e − hf¯w ≡ f¯w (1 − X)m

(mod (X − 1)k ).

(14)

In particular, f¯e − hf¯w is divisible by (X − 1)m . For sufficiently large k, this polynomial has at most 4bk + 6 ≤ m nonzero coefficients. Part (ii) of Lemma 3.7 therefore forces f¯e − hf¯w = 0 in Fq [X]. It follows from Equation (14) that f¯w has a zero of order at least k − m at X = 1. This polynomial is nonzero. Otherwise, zw = qz′ for some z′ ∈ Zq . Since [z′ ] = w/q = ̸ 0, the vector z′ is not constant. At least q − 1 pairs of its coordinates therefore differ, and Lemma 2.1 gives ∥w∥2 = q 2 ∥[z′ ]∥2 ≥ q 2 (q − 1) > 3q. Since f¯w has at most six nonzero coefficients, part (ii) of Lemma 3.7 bounds its order of vanishing at X = 1 by 5. This is impossible because k − m → ∞. We finally record the norm gap between roots of unity and all other nonzero elements of OK . Lemma 3.9. For every nonzero w ∈ OK , either w = ±ζ j for some j, in which case ∥w∥2 = q − 1, or ∥w∥2 ≥ 2q − 4. Proof. If ∥w∥2 ≥ q 2 /4, then ∥w∥2 ≥ 2q − 4. Otherwise, part (i) of Lemma 3.7 gives an integral coefficient representative with exactly s < q/2 nonzero coefficients. If s ≥ 2, every pair formed by one nonzero coordinate and one zero coordinate contributes to ∥w∥2 ≥ s(q − s) ≥ 2(q − 2). If s = 1, then w = tζ j for a nonzero integer t. The cases t = ±1 are precisely the roots of unity, whereas |t| ≥ 2 gives squared norm at least 4(q − 1). 14

4

The X3C checker

Section 3 supplies weight-h binary representatives in fixed ideal cosets. For such a representative x, put vx := [x] and let ξj := xαj . This section constructs U, V ∈ K so that the squared norm of the checker value U vx − V records the residual Aξ − 1M , up to a baseline independent of x and a nonnegative error term. In Section 4.3, we define clean completions for which this error term vanishes. The final corollary records the conclusions used in Section 5.

4.1

Separated offsets

For a selection vector ξ ∈ {0, 1}n and each i ∈ [M ], define Ri := {j ∈ [n] : i ∈ Cj }

si :=

and

X

ξj = (Aξ)i .

j∈Ri

Thus si is the number of selected sets containing i, and ξ is an exact cover exactly when si = 1 for every i. The quantity encoded by the checker is 2∥Aξ − 1M ∥22 = 2 |

M X

M X

i=1

i=1

(s2i − si ) − 2 {z

quadratic

}

si +2M.

(15)

| {z } linear

Define the incidence set I := {(i, j) ∈ [M ] × [n] : j ∈ Ri }. Every set Cj contains three elements. We assume here that M, n ≥ 1 and that every universe element lies in at least one set. These conditions are enforced by the preprocessing in Section 5.4. Under these assumptions, W := |I| = 3n, M ≤ W. (16) Let 0 ≤ α1 < · · · < αn = α⋆ be the Sidon positions from Lemma 2.2. The coordinate indexed by αj will store the selection bit for Cj , so we call αj a witness position. For a, b ∈ Fq , the offset from a to b is the cyclic difference b − a ∈ Fq . We separate the offsets associated with different rows of A. Define τ := 2α⋆ + 1, βi := τ i (i ∈ [M ]), dij := βi − αj ((i, j) ∈ I). (17) Here βi is the position assigned to row i of A, and dij is the offset from the witness position αj to βi . We choose q large enough that q > 4βM = 4τ M. (18) We use two types of offsets. The witness offsets are the cyclic differences between distinct witness positions: Dwit := {αℓ − αj : j, ℓ ∈ [n], j ̸= ℓ}. By the Sidon property and q > 4βM > 2α⋆ , these differences remain distinct modulo q. The bad offsets are the cross-row differences and the sums of the offsets dij : Dbad := {dij − drℓ : (i, j), (r, ℓ) ∈ I, i ̸= r} ∪ {dij + drℓ : (i, j), (r, ℓ) ∈ I}. In the norm expansion, each witness offset carries a product ξj ξℓ from the quadratic term in Equation (15). Every correlation at a bad offset contributes instead to E(x). To preserve the products at witness offsets while eliminating the correlations at bad offsets, the two offset sets must be disjoint. The next lemma proves this separation and bounds the number of bad offsets. 15

Lemma 4.1. Under the bound in Equation (18), the 2W residues dij and −dij , for (i, j) ∈ I, are nonzero and pairwise distinct. Moreover, 0∈ / Dbad ,

|Dbad | = O(W 2 ) = O(n2 ).

Dbad ∩ Dwit = ∅,

Proof. For every (i, j) ∈ I, α⋆ + 1 = β1 − α⋆ ≤ dij ≤ βM < q/4, so dij is nonzero modulo q. Fix distinct (i, j), (r, ℓ) ∈ I. Case 1: i = r. dij − diℓ = αℓ − αj ̸= 0, |dij − diℓ | ≤ α⋆ . Case 2: i ̸= r. dij − drℓ = βi − βr + αℓ − αj = τ (i − r) + αℓ − αj . Consequently, α⋆ + 1 ≤ |dij − drℓ | ≤ τ (M − 1) + α⋆ = βM − α⋆ − 1. For all (i, j), (r, ℓ) ∈ I, one also has 2α⋆ + 2 = 2β1 − 2α⋆ ≤ dij + drℓ ≤ 2βM . Together with q > 4βM , these bounds place the same-row differences, cross-row differences, and sums strictly inside (−q/2, q/2), so reduction modulo q creates no new equalities. The difference bounds separate residues of the same sign, and the sum bound separates residues of opposite signs. Thus the 2W residues dij and −dij are nonzero and pairwise distinct. Every witness offset is represented in [−α⋆ , α⋆ ]. By contrast, every cross-row difference and every sum in Dbad has a representative in (−q/2, q/2) with absolute value greater than α⋆ . Hence 0 ∈ / Dbad 2 and Dbad ∩ Dwit = ∅. The two sets in the definition of Dbad contain at most O(W ) = O(n2 ) offsets.

4.2

Checker elements and norm formula

Assume throughout this subsection that q ≡ 3 (mod 4). Fix x ∈ {0, 1}Fq of weight h and put vx := [x] :=

X

xa ζ a .

a∈Fq

P

Define ξj := xαj and let si := j∈Ri ξj as in Section 4.1. By Lemma 2.1 and Equation (8), ∥vx ∥2 = H. For d ∈ Fq , define the cyclic correlation of x at offset d by Cx (d) :=

X

xa xa+d .

a∈Fq

The indices lie in Fq , so a + d is computed modulo q. Thus Cx (d) counts the ordered pairs (a, a + d) ∈ F2q for which xa = xa+d = 1. The preceding decomposition separates the target into quadratic and linear parts. We first define p, whose shifted monomials encode the quadratic part through cyclic correlations. A Gauss sum is then used to define U , so that the quadratic contribution enters ∥U vx ∥2 and multiplication by U does not decrease the canonical norm. Next, D encodes the linear part, and V combines both parts in ∥U vx − V ∥2 . 16

Quadratic term.

Using the separated offsets dij , define ζ dij + ζ −dij ∈ OK .

X

p :=

(i,j)∈I

By Lemma 4.1, the displayed q-coordinate expression for p = p has 2W terms with pairwise distinct exponents. Same-row differences produce witness offsets, while the other differences and sums produce bad offsets. The resulting additional correlations are collected in E(x) below. The element U . Let χ be the quadratic character of Fq . Thus χ is 1 on nonzero squares, −1 on nonsquares, and 0 at zero. Define the quadratic Gauss sum ϑ :=

X

χ(a)ζ a ∈ OK .

a∈Fq

Lemma 4.2. The Gauss sum ϑ satisfies ϑ = −ϑ,

ϑϑ = q,

ϑ2 = −q.

Proof. Since q ≡ 3 (mod 4), one has χ(−1) = −1. Conjugation followed by a 7→ −a therefore gives ϑ = −ϑ. Since χ(0) = 0, writing a = tb in ϑϑ gives ϑϑ =

X

X

χ(t)

t∈F× q

ζ (t−1)b = q.

b∈F× q

The inner sum is q − 1 for t = 1 and −1 otherwise. Combining ϑϑ = q with ϑ = −ϑ gives ϑ2 = −q. Using Lemma 4.2, define U := 1 +

ϑp ∈ K. q

(19)

Lemma 4.3. The element U has the following properties. (i) U U = 1 + p2 /q. (ii) For every embedding σ : K ,→ C, |σ(U )|2 = 1 + σ(p)2 /q ≥ 1. In particular, U ̸= 0. (iii) For every y ∈ K, one has ∥U y∥ ≥ ∥y∥. Proof. Since p = p, Lemma 4.2 gives U U = 1 + p2 /q, proving (i). The value σ(p) is real for every embedding σ, so applying σ to (i) gives (ii). Summing the lower bound in (ii) over all embeddings proves (iii). Linear term.

Define D := −3

n X

ζ αj ∈ OK .

j=1

Each selected set contributes to three row sums, which motivates the coefficient −3. Part (ii) of Lemma 4.3 gives U ̸= 0, so define V := −

D D =− ∈ K. q − ϑp qU 17

(20)

Norm formula. We call U vx − V ∈ K the checker value. The correlations in q −1 ∥pvx ∥2 that are not determined by the counts si are collected in the following term: E(x) := 2

M X X

Cx (αℓ − αj ) − ξj ξℓ

i=1 j,ℓ∈Ri j̸=ℓ

X

+2

X

Cx (βi − βt − αj + αℓ )

(21)

i,t∈[M ] j∈Ri i̸=t ℓ∈Rt

X

+2

X

Cx (βi + βt − αj − αℓ ).

i,t∈[M ] j∈Ri ℓ∈Rt

The three lines record, respectively, the additional same-row correlations, the cross-row difference correlations, and the sum-offset correlations. Theorem 4.4. Assume that q ≡ 3 (mod 4). For every x ∈ {0, 1}Fq of weight h, define ξ ∈ {0, 1}n by ξj := xαj for j ∈ [n]. Then ∥U vx − V ∥2 = B0 + 2∥Aξ − 1M ∥22 + E(x), where B0 := H + ∥V ∥2 + 2W h − 2M +

(22)

2hW − 4h2 W 2 q

(23)

is a rational quantity determined by the constructed checker and independent of x. Moreover, E(x) ≥ 0 for every binary x. Proof. Quadratic term. For a ∈ Fq , define ya :=

X

(xa−dij + xa+dij ).

(i,j)∈I

Then pvx = a ya ζ a . Each of the 2W shifted copies of x has coefficient sum h, so For r, s ∈ Fq , cyclic reindexing gives P

X

xa−r xa−s = Cx (r − s),

P

a ya = 2W h.

Cx (−r) = Cx (r).

a∈Fq

For e = (i, j) and f = (t, ℓ) in I, write de := dij and df := dtℓ . Expanding preceding identities gives X a∈Fq

ya2 = 2W h + 2

X

Cx (de − df ) + 2

e,f ∈I e̸=f

X

2 a ya and using the

P

Cx (de + df ).

e,f ∈I

The diagonal products contribute 2W h, and the remaining correlations fall into three classes. Case 1: de − df with e = ̸ f and i = t. Here e = (i, j) and f = (i, ℓ), so j ̸= ℓ and dij − diℓ = αℓ − αj . P P Since j,ℓ∈Ri ξj ξℓ = s2i − si , this class contributes 2 i (s2i − si ) together with the first line of j̸=ℓ

Equation (21). Case 2: de − df with i = ̸ t. Here dij − dtℓ = βi − βt − αj + αℓ . These terms form the second line of Equation (21). 18

Case 3: de + df . For all (i, j), (t, ℓ) ∈ I, one has dij + dtℓ = βi + βt − αj − αℓ . These terms form the third line of Equation (21). Combining the diagonal term and the three cases yields X

ya2 = 2W h + 2

a

M X

(s2i − si ) + E(x).

i=1

For j ̸= ℓ, the difference Cx (αℓ − αj ) − ξj ξℓ counts the ordered pairs (a, a + αℓ − αj ) ̸= (αj , αℓ ) for which xa = xa+αℓ −αj = 1. The remaining two lines of Equation (21) are sums of correlation counts. Thus E(x) ≥ 0. P Using Lemma 2.1 and a ya = 2W h, we obtain ! 2

∥pvx ∥ = q 2W h + 2

X

(s2i − si ) + E(x)

− 4W 2 h2 .

i

Linear term. The coefficient sum of D is −W . Since each selected set contains three universe P P elements, 3 j ξj = i si . Hence Lemma 2.1 gives ⟨vx , D⟩ = −3q

X

ξj + hW = −q

j

X

si + hW.

i

Combining the terms. Part (i) of Lemma 4.3, the definition of V , the equality ∥vx ∥2 = H, and the two preceding identities give 2 1 ∥U vx − V ∥2 = H + ∥pvx ∥2 + ⟨vx , D⟩ + ∥V ∥2 q q X 2hW − 4h2 W 2 = H + ∥V ∥2 + 2W h + + 2 (s2i − 2si ) + E(x) q i = B0 + 2

X

(si − 1)2 + E(x).

i

Since si = (Aξ)i , the last line is Equation (22). The formula for B0 is independent of x, and B0 ∈ Q because ∥V ∥2 = TrK/Q (V V ).

4.3

Clean completions

Put P := {α1 , . . . , αn }. For each selection vector ξ ∈ {0, 1}n , define η ξ ∈ {0, 1}P by ηαξ j := ξj . For u ∈ Fkq with u0 = h, a completion of ξ with syndrome u is a vector x ∈ F(u; P, η ξ ). Thus x is binary, has weight h and syndrome u, and satisfies xαj = ξj for every j ∈ [n]. A completion x is clean if Cx (αℓ − αj ) = ξj ξℓ

(j, ℓ ∈ [n], j ̸= ℓ),

Cx (d) = 0

(d ∈ Dbad ).

(24)

The first equality allows only the ordered pair (αj , αℓ ) to contribute at the witness offset αℓ − αj . This ordered pair contributes ξj ξℓ . The second equality excludes every ordered pair at a bad offset. Hence every term in Equation (21) vanishes and E(x) = 0. The next theorem combines Theorem 3.4 with the fixed-coordinate bound in Corollary 3.5 to prove that a clean completion always exists.

19

Theorem 4.5. Suppose that q is a sufficiently large prime, n + 2 ≤ T , and Equation (18) holds. For every syndrome u ∈ Fkq with u0 = h, and every ξ ∈ {0, 1}n , there is a clean completion x ∈ {0, 1}Fq such that X Hq (k)x = u, xa = h, xαj = ξj (j ∈ [n]). a

Proof. Write F := F(u; P, η ξ ). By Theorem 3.4, one has |F| > 0. For a set Q ⊆ Fq \ P of one or two additional coordinates, put FQ := {x ∈ F : xa = 1 for every a ∈ Q}. Applying Corollary 3.5 gives |FQ | = O((h/q)|Q| ). |F| Case 1: d = αℓ − αj ∈ Dwit . By Lemma 2.2 and Equation (18), (αj , αℓ ) is the unique ordered pair in P at offset d. This ordered pair contributes ξj ξℓ to Cx (d). For every a = ̸ αj , the first equality in Equation (24) requires xa xa+d = 0, and at least one of a, a + d lies outside P . Case 2: d ∈ Dbad . The second equality in Equation (24) requires xa xa+d = 0 for every a ∈ Fq . By Lemma 4.1, d ∈ / Dwit and d ̸= 0. Thus no ordered pair in P has offset d, so at least one of a, a + d lies outside P . Every required zero product from the two cases has at least one endpoint outside P . If exactly one endpoint lies outside P , no completion violates the condition when the endpoint in P is fixed to zero. When the endpoint in P is fixed to one, the violating completions lie in FQ with |Q| = 1 and occupy an O(h/q) fraction of F. If both endpoints lie outside P , the corresponding fraction is O((h/q)2 ). The definition of Dwit and Lemma 4.1 give |Dwit ∪ Dbad | = O(n2 ). For each of these offsets, at most 2n ordered pairs have exactly one endpoint outside P , and at most q have both endpoints outside P . A union bound shows that the number of completions violating at least one required zero-product condition is at most ! n3 h n2 h2 O + |F|. q q Since n ≤ T = O(q 1/2000 ) and h = O(q 1/1000 ), the relative factor is o(1). Therefore some completion in F is clean. We summarize the checker bounds used in Section 5. Corollary 4.6. For every sufficiently large prime q ≡ 3 (mod 4) satisfying n + 2 ≤ T and the bound in Equation (18), the following statements hold. (i) Every x ∈ {0, 1}Fq of weight h, with ξj := xαj , satisfies ∥U vx − V ∥2 ≥ B0 + 2∥Aξ − 1M ∥22 . (ii) For the center c and syndrome uc defined in Section 3, every ξ ∈ {0, 1}n has a clean completion x ∈ F(uc ; P, η ξ ) such that vx ∈ c + aq,k ,

∥U vx − V ∥2 = B0 + 2∥Aξ − 1M ∥22 .

(25)

Proof. Part (i) follows directly from Theorem 4.4. For part (ii), choose x by Theorem 4.5 with u = uc . Cleanliness gives E(x) = 0, so Equation (22) gives the norm equality in Equation (25). The vectors x and c have syndrome uc and coefficient sum h. Hence Lemma 3.3 gives vx = [x] ∈ c + aq,k . 20

5

The rank-two reduction

Let q ≡ 3 (mod 4) be prime. This section assembles the checker and the ideal coset into a rank-two module and chooses the scale Γ for its second coordinate. Let U, V ∈ K be the checker elements constructed in Section 4.2 for the given X3C instance. The reduction uses the ideal a := aq,k = π k OK and the center c ∈ OK from Equation (13). Until Section 5.4, assume that M, n ≥ 1, that every universe element occurs in at least one set, that n + 2 ≤ T , and that Equation (18) holds. That subsection enforces these conditions when choosing q and handles isolated elements separately. The center c fixes the ideal coset whose representatives encode X3C selections. The elements U and V test the X3C equations in the first coordinate. The integer Γ weights the second coordinate. Before clearing denominators, define the generators and their span by m1 := (U π k , 0),

m2 := (U c − V, −Γ),

M := OK m1 + OK m2 ⊂ K 2 . Lemma 4.3 gives U = ̸ 0, and the choice of Γ below is positive. Hence every vector in M has the unique form
v(z, w) := U (π k z + wc) − V w, −Γw , z, w ∈ OK . (26) When w = 1 and π k z + c = vx for some x ∈ {0, 1}Fq , the first coordinate is the checker value U vx − V . Part (ii) of Corollary 4.6 guarantees the existence of such a clean completion for the completeness branch w = 1. The reduction does not compute this completion. Part (i) gives a lower bound for every binary coefficient vector. The second coordinate contributes Γ2 ∥w∥2 to the squared norm. For soundness, we consider separately w = 0, roots of unity, and elements that are not roots of unity.

5.1

Gap parameters

Recall from Equation (8) that every x ∈ {0, 1}Fq of weight h satisfies ∥vx ∥2 = H = h(q − h), and that L is the lower bound on the squared norm of a nonzero element of a. By Equation (16), W = 3n. The constant b = 1/100 ispused in Theorem 3.8, and B0 is defined in Equation (23). Let Γ be the nearest positive integer to 99L/(200(q − 1)), with ties rounded upward. Then Γ can be computed exactly in time polynomial in log q. s

Γ=

√ 99L + O(1) = Θ( k). 200(q − 1)

(27)

√ Squaring the estimate in Equation (27) gives Γ2 = 99k/100 + O( k). Since L = 2kq, the error √ contributes O(q k) = o(L) after multiplication by q − 1. Define F := Γ2 (q − 1) =

198 L + o(L) = Θ(L), 400

S := B0 + F,

ν :=

W . qΓ

(28)

A root of unity w contributes Γ2 ∥w∥2 = F through the second coordinate, so S is the completeness threshold. The parameter ν bounds the cancellation caused by V w. Lemma 5.1. Under the standing assumptions of this section, for every sufficiently large prime q ≡ 3 (mod 4), one has B0 > 0, 0 < ν < 1, and (1 − ν)(H + 2q + F ) > S,

S < L,

(1 − ν) bL + Γ2 (2q − 4) > S,

3F > S.

21

Moreover, every y, w ∈ K satisfy the stability estimate ∥U y − V w∥2 + Γ2 ∥w∥2 ≥ (1 − ν) ∥y∥2 + Γ2 ∥w∥2 .

(29)

Proof. The definitions of h and L, together with k = o(q), give h=

201 k + O(1), 200

H=

201 L + o(L). 400

The estimate for Γ2 preceding Equation (28) also gives Γ2 (2q − 4) = (99/100)L + o(L). For every embedding σ : K ,→ C, Part (ii) of Lemma 4.3 gives |σ(qU )| = q|σ(U )| ≥ q. The triangle inequality gives |σ(D)| ≤ W . Since V = −D/(qU ), it follows that max |σ(V )| ≤ σ

W , q

∥V ∥2 ≤

W2 (q − 1)W 2 < . q2 q

Since W = 3n = O(T ) and M ≤ W , the checker formula in Equation (23) and the scale relations following Equation (7) give √ |B0 − H| = o(q), νL = O(W k) = o(q). In particular, B0 > 0 and 0 < ν < 1 for large q. Since q = o(L), the same estimates give B0 = (201/400)L + o(L) and S = (399/400)L + o(L). Therefore, (1 − ν)(H + 2q + F ) − S = 2q + o(q) > 0, (1 − ν) bL + Γ2 (2q − 4) − S =

1 L + o(L) > 0, 400

1 L + o(L) > 0, 400 39 3F − S = L + o(L) > 0. 80 L−S =

For the first line, expanding S = B0 + F cancels the F terms. The remaining error is o(q) because B0 − H = o(q) and ν(H + 2q + F ) = O(νL) = o(q). This proves every assertion of the lemma except the stability estimate. For the stability estimate, the bound maxσ |σ(V )| ≤ W/q gives ∥V w∥ ≤ (W/q)∥w∥ = νΓ∥w∥. Hence 2|⟨U y, V w⟩| ≤ ν∥U y∥2 + ν −1 ∥V w∥2 ≤ ν∥U y∥2 + νΓ2 ∥w∥2 . Using this inequality together with ∥U y∥ ≥ ∥y∥ from Part (iii) of Lemma 4.3, we obtain ∥U y − V w∥2 + Γ2 ∥w∥2 ≥ (1 − ν)∥U y∥2 + ∥V w∥2 + (1 − ν)Γ2 ∥w∥2 ≥ (1 − ν) ∥y∥2 + Γ2 ∥w∥2 ,

which is Equation (29).

5.2

Completeness and soundness

Theorem 5.2. For every sufficiently large prime q ≡ 3 (mod 4), the following implications hold for every X3C instance such that each universe element occurs in at least one set, n + 2 ≤ T , and Equation (18) holds: ∃ξ ∈ {0, 1}n : Aξ = 1M

=⇒

λ1 (M)2 ≤ S,

∀ξ ∈ {0, 1}n : Aξ ̸= 1M

=⇒

λ1 (M)2 > S.

22

Proof. Completeness. Suppose Aξ = 1M . Part (ii) of Corollary 4.6 gives a clean x ∈ {0, 1}Fq such that vx ∈ c + a and ∥U vx − V ∥2 = B0 . Hence vx = π k z + c for some z ∈ OK . Taking w = 1 in Equation (26) gives ∥v(z, 1)∥2 = B0 + Γ2 ∥1∥2 = B0 + Γ2 (q − 1) = S. Soundness. Assume that the X3C instance is negative, and consider any nonzero v(z, w) ∈ M. Case 1: w = 0. Then z ̸= 0. Lemma 4.3 and Theorem 3.2 give ∥v(z, 0)∥2 = ∥U π k z∥2 ≥ ∥π k z∥2 ≥ L > S, where the final inequality follows from Lemma 5.1. Case 2: w is a root of unity. Write w = ±ζ a for some a ∈ Fq . Since wa = a, the element u := w−1 π k z + c belongs to c + a, and π k z + wc = wu. The first coordinate is w(U u − V ). Since multiplication by w is an isometry and ∥w∥2 = q − 1, both subcases below satisfy ∥v(z, w)∥2 = ∥U u − V ∥2 + F . By Lemma 3.6, u has a unique integral coefficient representative x ∈ Zq with coefficient sum h. (a) If x ∈ {0, 1}Fq , the coefficient-sum condition shows that x has weight h. Define ξj := xαj for j ∈ [n]. Since the instance is negative, ∥Aξ − 1M ∥22 ≥ 1. Thus Corollary 4.6 yields ∥v(z, w)∥2 = ∥U u − V ∥2 + Γ2 (q − 1) ≥ B0 + 2 + F = S + 2 > S. / {0, 1}Fq , then Lemma 3.6 gives ∥u∥2 ≥ H + 2q. Apply Equation (29) to the arguments (b) If x ∈ u and 1, and then use the inequality (1 − ν)(H + 2q + F ) > S from Lemma 5.1: ∥v(z, w)∥2 = ∥U u − V ∥2 + F ≥ (1 − ν)(H + 2q + F ) > S. Case 3: w is not a root of unity and 0 < ∥w∥2 ≤ 3q. Put y := π k z + wc. Since π k z ∈ a, the coset-separation bound in Theorem 3.8 gives ∥y∥2 ≥ dist(wc, a)2 > bL. Because w is not a root of unity, Lemma 3.9 also gives ∥w∥2 ≥ 2q − 4. The stability estimate and
the inequality (1 − ν) bL + Γ2 (2q − 4) > S from Lemma 5.1 imply ∥v(z, w)∥2 > (1 − ν) bL + Γ2 (2q − 4) > S.

Case 4: w is not a root of unity and ∥w∥2 > 3q. The second coordinate alone gives ∥v(z, w)∥2 ≥ Γ2 ∥w∥2 > 3qΓ2 > 3F > S, using the last inequality in Lemma 5.1. These cases exhaust every nonzero module vector.

5.3

Integral module and encoding length

The generators of M may have denominators. We multiply both generators by a common positive integer. This scales every squared norm and the threshold by the same square and preserves the gap.

23

A common denominator. Put r := q − ϑp = qU ∈ OK \ {0}, the denominator of V in Equation (20). Let Y Nr := σa (r) ∈ Z \ {0}, ρ := q|Nr |. a∈F× q

Every σa permutes the factors defining Nr , so Nr is rational. It is also an algebraic integer and Q σa (r) ∈ OK . Using therefore lies in Z. Since σ1 is the identity embedding, Nr /r = a∈F× q \{1} Equations (19) and (20), ρU = |Nr |(q + ϑp) ∈ OK ,

ρV = −qD

|Nr | ∈ OK . r

(30)

Define 2 ci := ρmi ∈ OK m

(i ∈ {1, 2}),

c := OK m c 1 + OK m c2 , M

Sb := ρ2 S.

(31)

Its generator matrix !

b = B

ρU π k ρ(U c − V ) 0 −ρΓ

2×2 ∈ OK ,

c is therefore a full-rank has determinant −ρ2 ΓU π k ̸= 0. By the module-lattice facts in Section 2, M 2 c c free submodule of OK . Since M = ρM and λ1 (M) = ρλ1 (M), Theorem 5.2 yields b c 2 ≤ S, positive X3C =⇒ λ1 (M) c 2 > S. b negative X3C =⇒ λ1 (M)

Integral threshold.

(32)

Since ρV ∈ OK , ρ2 ∥V ∥2 = ∥ρV ∥2 = TrK/Q ((ρV )ρV )

is an integer. Every denominator q in Equation (23) is cleared because ρ2 /q = qNr2 ∈ Z. Hence Sb ∈ Z. Since ρ > 0 and S > 0, we have Sb = ρ2 S > 0. c constructed above, we bound the power-basis coefficients Encoding length. For the module M of its two generators and the bit length of Sb polynomially in q and the X3C input length. By Equation (31), the generator bounds amount to controlling ρU π k , ρ(U c − V ), and ρΓ. In view of Equation (30), the only new quantities requiring estimates are Nr and the power-basis coefficients of Nr /r. Write

r=

q−2 X

ri ζ i ,





Br := max 1, max |ri | . i

i=0

Since q ≡ 3 (mod 4), one has χ(−1) = −1. Using ζ q−1 = −(1 + ζ + · · · + ζ q−2 ), we obtain ϑ=

q−2 X

χ(a)ζ a − ζ q−1 = 1 +

a=1

q−2 X

(1 + χ(a))ζ a .

a=1

Thus the power-basis coefficients of ϑ lie in {0, 1, 2} and are efficiently computable from a(q−1)/2 mod q. The power-basis coefficient bounds for p, D, and ϑ are therefore 1, 3, and 2, respectively. In q-coordinates, p has 2W nonzero coefficients and every coefficient of ϑ has absolute value at most one. Each coefficient of ϑp is therefore a sum of at most 2W coefficients of ϑ. Hence the coefficients of ϑp are bounded by 2W in q-coordinates and by 4W in the power basis. Consequently, Br ≤ q + 4W. 24

Let Mr ∈ Z(q−1)×(q−1) be the matrix of multiplication by r in the power basis 1, ζ, . . . , ζ q−2 . For 0 ≤ j ≤ q − 2, the column indexed by j is the coefficient vector of rζ j . First use ζ q = 1 to reduce its exponents to 0, . . . , q − 1. The resulting powers are distinct, and the only power outside the power basis is ζ q−1 . Replacing this term with ζ q−1 = −(1 + ζ + · · · + ζ q−2 ) shows that every entry of Mr is a sum of at most two terms of the form ±ri . Hence every entry has √ absolute value at most 2Br , and every row has ℓ2 -norm at most 2 q − 1 Br . Over C, the eigenvalues of multiplication by r are the conjugates σa (r) for a ∈ F× q . Consequently, the determinant identity and Hadamard’s determinant bound give det(Mr ) =

Y

σa (r) = Nr ,

 p

|Nr | ≤ 2 q − 1 Br

q−1

.

(33)

a∈F× q

We also need to control the coefficients of Nr /r. Its multiplication matrix is Nr M−1 r . For (j,i) 1 ≤ i, j ≤ q − 1, let Mr be the matrix obtained from Mr by deleting row j and column i. The cofactor formula for the inverse gives Nr M−1 = (−1)i+j det M(j,i) . r r ij

√ Every row of this (q − 2) × (q − 2) matrix has ℓ2 -norm at most 2 q − 2 Br . A second application of Hadamard’s bound therefore shows that  p

Nr M−1 ≤ 2 q − 2 Br r ij

q−2

.

(34)

Applying Nr M−1 r to the coefficient vector of 1 shows that its first column is the power-basis coefficient vector of Nr /r. Thus Equations (33) and (34) show that Nr and every coefficient of Nr /r have
bit length O q(log Br + log q) . The matrix Mr is computable from the coefficients of r. Standard polynomial-time exact integer linear algebra computes its determinant and the first column of its adjugate, and hence computes Nr and the coefficients of Nr /r within these bounds. The bound Br ≤ q + 4W and Equation (33) show that ρ = q|Nr | has polynomial bit length. The coefficients of π k and c = h + π ⌊k/2⌋ have O(k) bit length, and Γ has O(log k) bit length by Equation (27). Addition and multiplication in the power basis use q − 1 integer coefficients and increase their bit lengths by only a polynomial amount. Since the next subsection chooses q polynomially bounded in the X3C input length, the two generators in Equation (31) are computable in deterministic polynomial time and have polynomial encoding length. The bit-length bound for ρ and the coefficient bounds for ρV , together with Equations (23) and (28), show that Sb has bit length polynomial in q and the X3C input length. It is also computable in deterministic polynomial time. Compute ∥ρV ∥2 from the power-basis coefficients of ρV using Lemma 2.1, and then compute Sb = ρ2 S from Equations (23) and (28) using exact integer arithmetic.

5.4

Prime choice and Euclidean input

For an X3C instance with an isolated universe element, the reduction outputs the fixed module lattice over Z[ζ3 ] generated by (2, 0) and (0, 2), with squared threshold 1. Its squared minimum is 8 > 1, so this is a NO instance. For every remaining instance, adjoin a disjoint three-element block together with its unique set, as in Section 2. This answer-preserving preprocessing ensures M, n ≥ 1. We retain the notation M , n, and A for the resulting instance, in which every universe element occurs in at least one set. 25

Let ℓ be the bit length of this preprocessed X3C instance, and recall from Equation (7) that T is the number of coordinates that may be prescribed. By the prime number theorem for arithmetic progressions [IK04, Equation (17.2)], choose an absolute integer X0 exceeding the threshold implicit in Theorem 5.2 and large enough that every interval [Y, 2Y ] with Y ≥ X0 contains a prime congruent to 3 modulo 4. Since n = O(ℓ) for this explicit encoding, Lemma 2.2 and Equations (16) and (17) give 4τ M = O(n3 ) = O(ℓ3 ). Since T = ⌊q 1/2000 ⌋, an absolute constant C0 can therefore be chosen so that every q ≥ (ℓ + 2)C0 satisfies n + 2 ≤ T and the inequality in Equation (18). Put n

l

X := max X0 , (ℓ + 2)C0

mo

.

By the defining property of X0 , the interval [X, 2X] contains a prime congruent to 3 modulo 4. The reduction scans the integers in this interval that are congruent to 3 modulo 4 and applies deterministic primality testing [AKS04]. It finds a prime q ≡ 3 (mod 4) with q = ℓO(1) in deterministic polynomial time. It remains to represent the canonical norm by the standard coordinate ℓ2 -norm. Let d := q − 1. Using the integral basis of OK from Section 2, consider the vectors ci , ζ tm

0 ≤ t < d,

i ∈ {1, 2},

c Let C ∈ Z2d×2d be the matrix whose columns are their power-basis which form a Z-basis of M. c M coefficient vectors. q To realize the canonical inner product, let Eq ∈ Z(2)×d be an oriented incidence matrix of the complete graph on q vertices with one vertex column deleted. Its Gram matrix is T ET q Eq = qId − 1d 1d .

Thus Lemma 2.1 gives the following integer basis matrix: q

2(2)×2d B := (I2 ⊗ Eq )CM , c∈Z

(35)

c The Gram identity above shows that I2 ⊗ Eq has full column The lattice L(B) is isometric to M. b ̸= 0 shows that C has full rank. Hence B has full column rank. Its dimensions rank, while det(B) c M and encoding length are polynomial in ℓ.

5.5

Proof of the main theorem

2 and Proof of Theorem 1.1. Every output of the reduction is a full-rank free OK -submodule of OK hence has module rank two. As a Z-lattice, each output has rank 2(q − 1). For NP-hardness, consider the two branches in Section 5.4. If the input has an isolated universe element, then both the input and the fixed output are negative. Otherwise, the reduction maps the preprocessed X3C instance to b On this branch, the construction is deterministic and runs in polynomial time. The c1 , m c2 , S). (q, m 2 and have nonzero determinant, and Equation (32) proves the exact two module generators lie in OK YES–NO equivalence. For the polynomial-time computable integer matrix B in Equation (35), the c lattice L(B) is isometric to the canonically embedded module M. For membership in NP, first parse the encoded string and check the coefficient format, the nonnegative integer threshold, primality, q ≡ 3 (mod 4), and the nonzero determinant condition. Reject the input if any check fails. For a valid input, apply the coefficient-matrix construction in Section 5.4 to the input generators m1 , m2 . This produces in polynomial time an integer matrix B such that L(B) is isometric to the module lattice defined by the input generators. The nonzero K-determinant guarantees that B has full column rank. The standard verifier for decision-SVP from Section 2 then applies. This proves Theorem 1.1.

26

Proof of Corollary 1.2. Given an X3C instance, first check for an isolated universe element. If one exists, return NO without calling the oracle. Otherwise, apply the answer-preserving preprocessing above, carry out the reduction, and construct the integer basis B from Section 5.4. The lattice L(B) c ⊆ O 2 . A search-SVP oracle therefore returns a is isometric to the full-rank free module lattice M K shortest nonzero vector y ∈ L(B). By Equation (32), the X3C instance is positive exactly when b Thus at most one oracle call decides X3C in polynomial time, which proves the claimed ∥y∥22 ≤ S. Turing hardness. AI disclosure. GPT-5.6 Sol Ultra discovered the proof through an iterative conversation conducted in a single session. The discussion began by asking whether the locally dense lattices that Bennett and Peikert construct from Reed–Solomon codes for approximate SVP [BP23] could be adapted to module lattices. The model first found a randomized reduction by combining this construction with Wan’s point-count estimates [Wan26b], and then developed the deterministic reduction proved in this paper. The authors independently verified every mathematical claim and proof, checked every use of the cited references, simplified and refined the argument, and wrote the final manuscript. The authors take full responsibility for the paper.

References [Ajt98]

Miklós Ajtai. The shortest vector problem in L2 is NP-hard for randomized reductions. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pages 10–19. ACM, 1998.

[AKS04]

Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of Mathematics, 160(2):781–793, 2004.

[BDK+ 18]

Joppe W. Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS–Kyber: A CCA-secure module-lattice-based KEM. In 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pages 353–367. IEEE, 2018.

[BP23]

Huck Bennett and Chris Peikert. Hardness of the (approximate) shortest vector problem: A simple proof via Reed–Solomon codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), volume 275 of LIPIcs, pages 37:1–37:20, 2023.

[CN98]

Jin-Yi Cai and Ajay Nerurkar. Approximating the SVP to within a factor (1 + 1/ dimε ) is NP-hard under randomized reductions. In Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC), pages 46–55. IEEE Computer Society, 1998.

[dBPTW26]

Koen de Boer, Aurel Page, Radu Toma, and Benjamin Wesolowski. Average hardness of SIVP for module lattices of fixed rank. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), pages 814–822. ACM, 2026.

[DKL+ 18]

Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium: A lattice-based digital signature scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(1):238–268, 2018.

[ET41]

Paul Erdős and Pál Turán. On a problem of Sidon in additive number theory, and on some related problems. Journal of the London Mathematical Society, 16(4):212–215, 1941.

[FPMS22]

Joël Felderhoff, Alice Pellet-Mary, and Damien Stehlé. On module unique-SVP and NTRU. In Advances in Cryptology—ASIACRYPT 2022, pages 709–740. Springer, 2022.

[GJ79]

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

27

[GSVV25]

Nihar Gargava, Vlad Serban, Maryna Viazovska, and Ilaria Viglino. Module lattices and their shortest vectors. arXiv:2510.12893, 2025.

[HPS98]

Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. In Algorithmic Number Theory (ANTS-III), volume 1423 of Lecture Notes in Computer Science, pages 267–288. Springer, 1998.

[HR12]

Ishay Haviv and Oded Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Theory of Computing, 8(23):513–531, 2012.

[HS26a]

Isaac M. Hair and Amit Sahai. Deterministic hardness of approximation for SVP in all finite ℓp norms. CoRR, abs/2604.01451, 2026. Accepted to FOCS 2026.

[HS26b]

Isaac M. Hair and Amit Sahai. SVPp is deterministically NP-hard for all p > 2, even to 1−ε approximate within a factor of 2log n . In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), pages 1716–1727. ACM, 2026.

[IK04]

Henryk Iwaniec and Emmanuel Kowalski. Analytic Number Theory, volume 53 of American Mathematical Society Colloquium Publications. American Mathematical Society, 2004.

[Kho05]

Subhash Khot. Hardness of approximating the shortest vector problem in lattices. Journal of the ACM, 52(5):789–808, 2005.

[LFP26]

Jiaqi Liu, Yansong Feng, and Yanbin Pan. Exact CVP is NP-complete for principal cyclotomic ideals. CoRR, abs/2608.23828, 2026.

[LN97]

Rudolf Lidl and Harald Niederreiter. Finite Fields. Cambridge University Press, 2 edition, 1997.

[LPMSW19] Changmin Lee, Alice Pellet-Mary, Damien Stehlé, and Alexandre Wallet. An LLL algorithm for module lattices. In Advances in Cryptology—ASIACRYPT 2019, pages 59–90. Springer, 2019. [LPR13a]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. Journal of the ACM, 60(6):43:1–43:35, 2013.

[LPR13b]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. A toolkit for ring-LWE cryptography. In Advances in Cryptology—EUROCRYPT 2013, pages 35–54. Springer, 2013.

[LS15]

Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3):565–599, 2015.

[MG02]

Daniele Micciancio and Shafi Goldwasser. Complexity of Lattice Problems: A Cryptographic Perspective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, 2002.

[Mic01]

Daniele Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. SIAM Journal on Computing, 30(6):2008–2035, 2001.

[Mic07]

Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity, 16(4):365–411, 2007.

[Mic12]

Daniele Micciancio. Inapproximability of the shortest vector problem: Toward a deterministic reduction. Theory of Computing, 8(22):487–512, 2012.

[MMPMT23] Gabrielle De Micheli, Daniele Micciancio, Alice Pellet-Mary, and Nam Tran. Reductions from module lattices to free module lattices, and application to dequantizing module-LLL. In Advances in Cryptology—CRYPTO 2023, Part V, pages 836–865. Springer, 2023. [Nat24a]

National Institute of Standards and Technology. Module-Lattice-Based Digital Signature Standard. Federal Information Processing Standards Publication NIST FIPS 204, U.S. Department of Commerce, 2024.

28

[Nat24b]

National Institute of Standards and Technology. Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication NIST FIPS 203, U.S. Department of Commerce, 2024.

[vEB81]

Peter van Emde Boas. Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Mathematical Institute, University of Amsterdam, 1981.

[Wan26a]

Daqing Wan. Euclidean SVP is deterministically NP-hard to approximate within any constant factor. CoRR, abs/2608.12664, 2026.

[Wan26b]

Daqing Wan. NP-hardness of SVP in euclidean space. CoRR, abs/2603.27398, 2026.

[Was97]

Lawrence C. Washington. Introduction to Cyclotomic Fields, volume 83 of Graduate Texts in Mathematics. Springer, 2 edition, 1997.

29

Related documents

• Bass Numbers of Veronese Submodules and Lifting the Frobenius Trace#442261
• On a parity result for the symmetric square of modular forms with congruent residual representations#1156154
• Unique mutation cycles of nucleus-extension quivers#1048413
• Universal norms and de Rham representations#996678
• On Donkin's Tilting Module Conjecture IV: New Frontiers#1071268