Introduction
The Shortest Vector Problem (SVP) asks for the minimum ℓ p \ell_p ℓ p norm of a nonzero vector in a given integer lattice. It is the central computational problem on lattices, with applications to algorithms and cryptography [AEVZ02; Pei16]. For finite ℓ p \ell_p ℓ p norms, the hardness of SVP was long known only under randomized reductions, and removing this randomness has been a major challenge.
In the classical setting of NP-hardness, this challenge has recently been met. Van Emde Boas [vEmd81] proved that SVP in the ℓ ∞ \ell_\infty ℓ ∞ norm is NP-hard and conjectured the same for the Euclidean norm. Ajtai [3 ] proved this conjecture under randomized reductions, and subsequent work proved the hardness of approximating SVP in every finite ℓ p \ell_p ℓ p norm, again under randomized reductions [31 , 29 , 24 , 32 ] . The first deterministic hardness results for SVP in finite ℓ p \ell_p ℓ p norms appeared only recently. For every p > 2 p > 2 p > 2 , Hair and Sahai [27 ] proved that approximating SVP is NP-hard under deterministic polynomial-time reductions, later even within polynomial factors [26 ] , and Hecht and Safra [28 ] proved hardness under deterministic subexponential-time reductions. Hair and Sahai [25 ] then extended hardness under subexponential-time reductions to every finite ℓ p \ell_p ℓ p norm. Wan [Wan26b] resolved the conjecture of van Emde Boas: for every p ≥ 1 p \ge1 p ≥ 1 , approximating SVP in the ℓ p \ell_p ℓ p norm within any factor below 2 1 / p 2^{1/p} 2 1/ p is NP-hard under deterministic polynomial-time reductions. Wan [Wan26a] later extended this result to every constant factor in every finite ℓ p \ell_p ℓ p norm.
The situation is, however, different in parameterized complexity. A problem with a parameter k k k is fixed-parameter tractable (FPT) if it can be solved in time f ( k ) ⋅ n O ( 1 ) f(k) \cdot n^{O(1)} f ( k ) ⋅ n O ( 1 ) for some computable function f f f , where n n n is the input length. The standard evidence that a problem is not FPT is its W[1]-hardness under FPT reductions, which plays the role of NP-hardness [16 CFK+15] . For SVP, the natural parameter is the distance threshold d d d , and exhaustive search over the integer vectors with at most d p d^p d p nonzero coordinates solves SVP in time ( d n ) O ( d p ) (dn)^{O(d^p)} ( d n ) O ( d p ) . Downey, Fellows, Vardy, and Whittle [DFVW99] asked whether SVP is W[1]-hard, together with the same question for the parameterized Minimum Distance Problem (MDP) on linear codes, whose natural parameter is also the distance threshold k k k ; in their framework, W[1]-hardness refers to the standard deterministic FPT reductions. For binary codes, MDP is equivalent to the k k k -Even Set problem, whose fixed-parameter tractability remained a central open problem in parameterized complexity for almost two decades [16 ] .
Bhattacharyya, Bonnet, Egri, Ghoshal, Karthik C. S., Lin, Manurangsi, and Marx [BBE+21] answered both questions under randomized reductions. They proved that, for every p > 1 p > 1 p > 1 , approximating SVP in the ℓ p \ell_p ℓ p norm within some constant factor is W[1]-hard, and that approximating MDP over F 2 \mathbb{F}_2 F 2 within any constant factor is W[1]-hard. Bennett, Cheraghchi, Guruswami, and Ribeiro [7 ] extended these results to SVP in every finite ℓ p \ell_p ℓ p norm and to MDP over every finite field, again under randomized reductions. Both works asked for deterministic reductions [BBE+21, Section 8], and Bennett, Cheraghchi, Guruswami, and Ribeiro [7 ] called finding them a groundbreaking contribution. Hirahara and Ogitsuka [23 ] gave one-sided-error reductions, which always map NO instances to NO instances, for MDP within every constant factor and for SVP within every factor below 2 1 / p 2^{1/p} 2 1/ p . They then derandomized these reductions under the assumption that some problem solvable in time 2 O ( n ) 2^{O(n)} 2 O ( n ) requires nondeterministic circuits of size 2 Ω ( n ) 2^{\Omega(n)} 2 Ω ( n ) . For MDP, Guruswami and Ren [21 ] very recently gave an unconditional deterministic reduction, using an elementary construction based on Reed–Muller codes. For SVP, no unconditional deterministic reduction was known.
Our Results
We prove the parameterized hardness of SVP under deterministic reductions. For a constant γ ≥ 1 \gamma\ge1 γ ≥ 1 , the promise problem γ \gamma γ -GapSVPp _p p asks us to distinguish integer lattices that contain a nonzero vector of ℓ p \ell_p ℓ p norm at most d d d from those in which every nonzero vector has norm greater than γ d \gamma d γ d ; the parameter is d d d (see Definition 2.2 ).
Theorem 1.1. For every computable1 real p ≥ 1 p \ge1 p ≥ 1 and every constant γ ∈ [ 1 , 2 1 / p ) \gamma\in[1,2^{1/p}) γ ∈ [ 1 , 2 1/ p ) , γ \gamma γ -GapSVPp _p p is W[1]-hard under deterministic FPT many-one reductions.
Theorem 1.1 answers the question of Downey, Fellows, Vardy, and Whittle [DFVW99] for SVP with deterministic reductions, as well as the question of [BBE+21; BCGR24]: it gives the first deterministic reduction that proves the W[1]-hardness of SVP without any assumption. Previously, even for exact SVP in the Euclidean norm, W[1]-hardness under deterministic reductions was known only under the circuit lower-bound assumption of [23 ] . Its range of approximation factors is the same as that of the one-sided-error reductions of [23 ] and of the deterministic NP-hardness for general p p p in [Wan26b].
Combined with an improved version of the tensor-product amplification of Wan [Wan26a], our approach extends to every constant factor.
Theorem 1.2. For every computable real p ≥ 1 p \ge1 p ≥ 1 and every constant γ ≥ 1 \gamma\ge1 γ ≥ 1 , γ \gamma γ -GapSVPp _p p is W[1]-hard under deterministic FPT many-one reductions.
Theorem 1.2 is the parameterized analogue of the deterministic NP-hardness of [Wan26a]. For p > 1 p > 1 p > 1 , its range of approximation factors matches that of the randomized reduction of [7 ] ; for p = 1 p = 1 p = 1 , it goes beyond their range, which consists of the factors below 2. We prove Theorem 1.2 in Section A: we reduce from the Maximum Likelihood Decoding Problem using the construction of Theorem 3.2 , and then amplify the gap by taking tensor powers.
The same method applies to MDP. For a constant γ ≥ 1 \gamma\ge1 γ ≥ 1 , the problem γ \gamma γ -GapMDPq _q q asks us to distinguish linear codes over F q \mathbb{F}_q F q that contain a nonzero codeword of Hamming weight at most k k k from those in which every nonzero codeword has weight greater than γ k \gamma k γ k (see Definition 2.5 ).
Theorem 1.3. For every prime power q ≥ 2 q \ge2 q ≥ 2 and every constant γ ≥ 1 \gamma\ge1 γ ≥ 1 , γ \gamma γ -GapMDPq _q q is W[1]-hard under deterministic FPT many-one reductions.
Guruswami and Ren [21 ] proved Theorem 1.3 with a different, elementary construction, starting from the exact nearest codeword problem. In their reduction, the output threshold grows exponentially with the input threshold k k k . In ours, it grows linearly: before the final amplification, our reduction maps the approximate nearest codeword problem with threshold k k k to MDP with threshold ( 4 p − 1 ) k (4p - 1)k ( 4 p − 1 ) k over F p \mathbb{F}_p F p (Theorem 4.4 ).
Guruswami and Ren also mention a reduction with a linear threshold and essentially the same parameters as ours, which GPT-6 discovered using algebraic geometry, but they did not include it because they had not carefully verified its proof [21 Footnote 1] . Our main technical contribution is to identify a finite-field version of the implicit function theorem (see Lemma 2.19 ) as the key idea underlying the algebraic argument, and to give a short proof using standard facts about curves over finite fields.
Technical Overview
Our reductions build directly on those of Hirahara and Ogitsuka [23 ] . Hirahara and Ogitsuka build on the reductions of Bennett, Cheraghchi, Guruswami, and Ribeiro [7 ] , which adapt the approach developed by Khot [29 ] for proving NP-hardness of SVP to the parameterized setting. Hirahara and Ogitsuka guarantee soundness deterministically, leaving randomness only for completeness. We make completeness deterministic as well. Thus, our approach can be viewed as a derandomized version of Khot’s approach. In these approaches, the reduction to SVP starts from its inhomogeneous version, the Closest Vector Problem (CVP). Similarly, the reduction to the Minimum Distance Problem starts from its inhomogeneous version, the Nearest Codeword Problem (NCP). We explain the reduction for SVP and then the changes for MDP.
The Reduction for the Shortest Vector Problem
Previous randomized approach. We briefly recall the reduction of Hirahara and Ogitsuka [23 ] , on which our reduction is based. It starts from an instance ( B , t , d ) (B,t,d) ( B , t , d ) of CVP with approximation factor γ \gamma γ , where B ∈ Z m × n B \in\mathbb{Z}^{m \times n} B ∈ Z m × n is a basis matrix, t ∈ Z m t \in\mathbb{Z}^m t ∈ Z m is a target vector, and d d d is a positive integer. This problem asks whether there exists x ∈ Z n x \in\mathbb{Z}^n x ∈ Z n with ∥ B x − t ∥ p ≤ d \lVert Bx - t\rVert_p \le d ∥ B x − t ∥ p ≤ d . In a NO instance, not only t t t but every nonzero integer multiple of t t t is far from the lattice: ∥ B x − ℓ t ∥ p > γ d \lVert Bx - \ell t\rVert_p > \gamma d ∥ B x − ℓ t ∥ p > γ d for every x ∈ Z n x \in\mathbb{Z}^n x ∈ Z n and every nonzero integer ℓ \ell ℓ . The problem remains W[1]-hard with this stronger NO condition. The reduction uses a locally dense lattice with basis A A A and center s s s . Informally, a locally dense lattice refers to a lattice with many lattice points lying in a ball centered at s s s whose radius is smaller than the length of a shortest nonzero lattice vector. In [7 , 23 ] , the basis A \mathbf{A} A is constructed deterministically so that the lattice it generates has minimum norm greater than γ d \gamma d γ d . The center s \mathbf{s} s is chosen randomly to obtain many short vectors A y − s \mathbf{A}\mathbf{y}-\mathbf{s} Ay − s .
For a suitable prime q > γ d q>\gamma d q > γ d and an integer β > γ d \beta>\gamma d β > γ d , the output lattice consists of vectors of the form
( B 0 − t 0 0 A − s 0 0 0 1 0 β P B β R A − β ( P t + R s ) β q I ) ( x y ℓ z ) = ( B x − ℓ t A y − ℓ s ℓ β ( P ( B x − ℓ t ) + R ( A y − ℓ s ) + q z ) ) , \begin{pmatrix}
\mathbf{B} & \mathbf{0} & -\mathbf{t} & \mathbf{0}\\
\mathbf{0} & \mathbf{A} & -\mathbf{s} & \mathbf{0}\\
\mathbf{0} & \mathbf{0} & 1 & \mathbf{0}\\
\beta\mathbf{P}\mathbf{B} & \beta\mathbf{R}\mathbf{A} & -\beta(\mathbf{P}\mathbf{t}+\mathbf{R}\mathbf{s}) & \beta q\mathbf{I}
\end{pmatrix}
\begin{pmatrix}
\mathbf{x}\\
\mathbf{y}\\
\ell\\
\mathbf{z}
\end{pmatrix}
=
\begin{pmatrix}
\mathbf{B}\mathbf{x}-\ell\mathbf{t}\\
\mathbf{A}\mathbf{y}-\ell\mathbf{s}\\
\ell\\
\beta\bigl(\mathbf{P}(\mathbf{B}\mathbf{x}-\ell\mathbf{t})+\mathbf{R}(\mathbf{A}\mathbf{y}-\ell\mathbf{s})+q\mathbf{z}\bigr)
\end{pmatrix}, B 0 0 β PB 0 A 0 β RA − t − s 1 − β ( Pt + Rs ) 0 0 0 β q I x y ℓ z = Bx − ℓ t Ay − ℓ s ℓ β ( P ( Bx − ℓ t ) + R ( Ay − ℓ s ) + q z ) ,
where x , y , z \mathbf{x},\mathbf{y},\mathbf{z} x , y , z are integer vectors and ℓ \ell ℓ is an integer. Here P \mathbf{P} P is a deterministically constructed parity-check matrix that maps every nonzero integer vector of ℓ p \ell_p ℓ p norm at most γ d \gamma d γ d to a nonzero vector modulo q q q . The matrix R \mathbf{R} R is chosen randomly, and both matrices are represented by integer entries. The coefficient ℓ \ell ℓ multiplies both targets, and the last block vanishes for some integer vector z \mathbf{z} z if and only if
P ( B x − ℓ t ) + R ( A y − ℓ s ) = 0 ( m o d q ) . \mathbf{P}(\mathbf{B}\mathbf{x}-\ell\mathbf{t})+\mathbf{R}(\mathbf{A}\mathbf{y}-\ell\mathbf{s})=0 \pmod q. P ( Bx − ℓ t ) + R ( Ay − ℓ s ) = 0 ( mod q ) .
To prove completeness, let x \mathbf{x} x satisfy ∥ B x − t ∥ p ≤ d \lVert\mathbf{B}\mathbf{x}-\mathbf{t}\rVert_p\le d ∥ Bx − t ∥ p ≤ d . By the local density, with high probability over the random choice of s \mathbf{s} s , there are many integer vectors y \mathbf{y} y for which A y − s \mathbf{A}\mathbf{y}-\mathbf{s} Ay − s is short. Since there are many such short vectors, with high probability over the random choice of R \mathbf{R} R , one of them is mapped to the required vector, that is,
R ( A y − s ) = − P ( B x − t ) ( m o d q ) . (1) \mathbf{R}(\mathbf{A}\mathbf{y}-\mathbf{s})=-\mathbf{P}(\mathbf{B}\mathbf{x}-\mathbf{t}) \pmod q. \tag*{(1)} R ( Ay − s ) = − P ( Bx − t ) ( mod q ) . (1)
Setting ℓ = 1 \ell=1 ℓ = 1 and choosing z \mathbf{z} z so that the last block vanishes gives a short nonzero output vector.
Soundness holds for every choice of s \mathbf{s} s and R \mathbf{R} R [23 Theorem 3.9] , so randomness is needed only for completeness.
Our approach: deterministic reduction with locally dense lattices. Our reduction is obtained from the reduction of Hirahara and Ogitsuka [23 ] by a specific choice of P \mathbf{P} P and R \mathbf{R} R and by removing the columns β q I \beta q\mathbf{I} β q I . Let Λ \Lambda Λ be the lattice generated by A \mathbf{A} A , and fix an ordered list S S S of its coordinates. We write v ∣ S \mathbf{v}|_S v ∣ S for the restriction of a vector v \mathbf{v} v to the coordinates in S S S , in the specified order, and A S \mathbf{A}_S A S for the corresponding rows of A \mathbf{A} A . We take P = I \mathbf{P}=\mathbf{I} P = I and let R \mathbf{R} R be the negative of the restriction map to S S S , that is, R v = − v ∣ S \mathbf{R}\mathbf{v}=-\mathbf{v}|_S Rv = − v ∣ S . Thus R \mathbf{R} R is no longer random, and we also choose the center s \mathbf{s} s deterministically, with s ∣ S = 0 \mathbf{s}|_S=0 s ∣ S = 0 . With these choices, Equation (1) becomes
( A y − s ) ∣ S = B x − t ( m o d q ) (\mathbf{A}\mathbf{y}-\mathbf{s})|_S=\mathbf{B}\mathbf{x}-\mathbf{t} \pmod q ( Ay − s ) ∣ S = Bx − t ( mod q ) .
Since we remove the columns β q I \beta q\mathbf{I} β q I , which account for the reduction modulo q q q , we require this to hold as an equality of integer vectors:
( A y − s ) ∣ S = B x − t . (\mathbf{A}\mathbf{y}-\mathbf{s})|_S=\mathbf{B}\mathbf{x}-\mathbf{t}. ( Ay − s ) ∣ S = Bx − t .
To satisfy this for every YES instance without randomness, every short vector in Z m \mathbb{Z}^m Z m must be the restriction to S S S of some short vector in Λ − s \Lambda-\mathbf{s} Λ − s . In [23 ] , a locally dense lattice consists only of the basis A \mathbf{A} A and the center s \mathbf{s} s , and the random matrix R \mathbf{R} R is responsible for satisfying Equation (1) . We instead include the list S S S in our locally dense lattice and construct s \mathbf{s} s and S S S deterministically so that the restriction to S S S plays this role.
Accordingly, our locally dense lattice consists of a lattice Λ \Lambda Λ whose minimum ℓ p \ell_p ℓ p norm is greater than γ d \gamma d γ d , a center s \mathbf{s} s , and an ordered list S S S of coordinates with s ∣ S = 0 \mathbf{s}|_S=0 s ∣ S = 0 , such that every short vector in Z m \mathbb{Z}^m Z m is the restriction to S S S of a short vector in Λ − s \Lambda-\mathbf{s} Λ − s :
For every u ∈ Z m with ∥ u ∥ p ≤ d , some w ∈ Λ − s with ∥ w ∥ p ≤ W satisfies w ∣ S = u . (2) \text{For every }\mathbf{u}\in\mathbb{Z}^m\text{ with }\lVert\mathbf{u}\rVert_p\le d,\text{ some }\mathbf{w}\in\Lambda-\mathbf{s}\text{ with }\lVert\mathbf{w}\rVert_p\le W\text{ satisfies }\mathbf{w}|_S=\mathbf{u}. \tag*{(2)} For every u ∈ Z m with ∥ u ∥ p ≤ d , some w ∈ Λ − s with ∥ w ∥ p ≤ W satisfies w ∣ S = u . (2)
Condition Equation (2) is our counterpart of Equation (1) . Taking u = B x − t u = \mathbf{B}x - t u = B x − t , it guarantees the equality above for every x x x with ∥ B x − t ∥ p ≤ d \lVert\mathbf{B}x - t\rVert_p \le d ∥ B x − t ∥ p ≤ d , without any randomness.
For an integer β > γ d \beta> \gamma d β > γ d , given a locally dense lattice ( Λ , s , S ) (\Lambda, s, S) ( Λ , s , S ) satisfying Equation (2) as advice, the reduction deterministically outputs a lattice consisting of vectors of the form
( B 0 − t 0 A − s 0 0 1 β B − β A S − β t ) ( x y ℓ ) = ( B x − ℓ t A y − ℓ s ℓ β ( B x − ℓ t − A S y ) ) , \begin{pmatrix}
\mathbf{B} & 0 & -t \\
0 & \mathbf{A} & -s \\
0 & 0 & 1 \\
\beta\mathbf{B} & -\beta\mathbf{A}S & -\beta t
\end{pmatrix}
\begin{pmatrix}
x\\
y\\
\ell
\end{pmatrix}
=
\begin{pmatrix}
\mathbf{B}x-\ell t\\
\mathbf{A}y-\ell s\\
\ell\\
\beta(\mathbf{B}x-\ell t-\mathbf{A}S y)
\end{pmatrix}, B 0 0 β B 0 A 0 − β A S − t − s 1 − β t x y ℓ = B x − ℓ t A y − ℓ s ℓ β ( B x − ℓ t − A S y ) ,
where x , y x,y x , y are integer vectors and ℓ \ell ℓ is an integer.
To prove completeness, consider a YES instance of CVP and let x x x satisfy ∥ B x − t ∥ p ≤ d \lVert\mathbf{B}x-t\rVert_p \le d ∥ B x − t ∥ p ≤ d . Apply Equation (2) with u ← B x − t u \leftarrow\mathbf{B}x-t u ← B x − t . The resulting vector w w w can be written as A y − s \mathbf{A}y-s A y − s for an integer vector y y y . Since s ∣ S = 0 s|_S=0 s ∣ S = 0 , the equality w ∣ S = B x − t w|_S=\mathbf{B}x-t w ∣ S = B x − t gives A S y = B x − t \mathbf{A}S y=\mathbf{B}x-t A S y = B x − t . With ℓ = 1 \ell=1 ℓ = 1 , the last block vanishes. The output vector is then nonzero because its third block is ℓ = 1 \ell=1 ℓ = 1 , and the p p p th power of its norm is ∥ B x − t ∥ p p + ∥ A y − s ∥ p p + 1 ≤ d p + W + 1 \lVert\mathbf{B}x-t\rVert_p^p+\lVert\mathbf{A}y-s\rVert_p^p+1\le d^p+W+1 ∥ B x − t ∥ p p + ∥ A y − s ∥ p p + 1 ≤ d p + W + 1 .
Soundness does not require Equation (2) ; it uses only the minimum norm bound for Λ \Lambda Λ and the inequality β > γ d \beta>\gamma d β > γ d . Consider a NO instance of CVP and an output vector of norm at most γ d \gamma d γ d . The promise of CVP forces ℓ = 0 \ell=0 ℓ = 0 , since otherwise ∥ B x − ℓ t ∥ p > γ d \lVert\mathbf{B}x-\ell t\rVert_p>\gamma d ∥ B x − ℓ t ∥ p > γ d . Then A y = 0 \mathbf{A}y=0 A y = 0 , because it belongs to Λ \Lambda Λ , has norm at most γ d \gamma d γ d , and every nonzero vector in Λ \Lambda Λ has norm greater than γ d \gamma d γ d . The last block is now β B x \beta\mathbf{B}x β B x . Since B x \mathbf{B}x B x is an integer vector, this block is either zero or has norm at least β > γ d \beta>\gamma d β > γ d . Thus B x = 0 \mathbf{B}x=0 B x = 0 , so every block is zero, proving soundness. It remains to construct ( Λ , s , S ) (\Lambda,s,S) ( Λ , s , S ) deterministically in time f ( d ) m O ( 1 ) f(d)m^{O(1)} f ( d ) m O ( 1 ) , with W W W bounded by a function of d d d alone.
Deterministic construction of locally dense lattices. We provide a technical overview of the deterministic construction of locally dense lattices required above. For an integer k ≥ 2 k\ge2 k ≥ 2 and a sufficiently large prime q > 2 k q>2k q > 2 k , we use the Reed–Solomon lattice of Bennett and Peikert [8 ] ,
Λ = { v ∈ Z F q : ∑ z ∈ F q v z z j = 0 ( m o d q ) for every 0 ≤ j < k } . (3) \Lambda=\left\{v\in\mathbb{Z}^{\mathbb{F}_q}:\sum_{z\in\mathbb{F}_q}v_z z^j=0\pmod q\text{ for every }0\le j<k\right\}. \tag*{(3)} Λ = ⎩ ⎨ ⎧ v ∈ Z F q : z ∈ F q ∑ v z z j = 0 ( mod q ) for every 0 ≤ j < k ⎭ ⎬ ⎫ . (3)
Field elements label the coordinates, while the vector entries are integers. It was shown in [8 ] that the minimum distance of Λ \Lambda Λ in the ℓ p \ell_p ℓ p norm is at least ( 2 k ) 1 / p (2k)^{1/p} ( 2 k ) 1/ p .
We construct the center s s s and the ordered list S S S of m m m coordinates satisfying Equation (2) with W = k − 1 + 2 d p W=k-1+2d^p W = k − 1 + 2 d p . Fix distinct points y 1 , … , y k − 1 , x 1 , … , x m ∈ F q y_1,\ldots,y_{k-1},x_1,\ldots,x_m\in\mathbb{F}_q y 1 , … , y k − 1 , x 1 , … , x m ∈ F q . Set S = ( x 1 , … , x m ) S=(x_1,\ldots,x_m) S = ( x 1 , … , x m ) and s = − ∑ ℓ = 1 k − 1 e y ℓ s=-\sum_{\ell=1}^{k-1}e_{y_\ell} s = − ∑ ℓ = 1 k − 1 e y ℓ , where e ξ e_\xi e ξ is the unit vector at coordinate ξ ∈ F q \xi\in\mathbb{F}_q ξ ∈ F q . For clarity, we reorder the coordinates in each vector display below to show where the entries are placed. The center has the form
s = ( 0 , … , 0 ⏟ x 1 , … , x m , − 1 , … , − 1 ⏟ y 1 , … , y k − 1 , 0 , … , 0 ⏟ remaining coordinates ) T . s=\left( \underbrace{0,\ldots,0}_{x_1,\ldots,x_m},\underbrace{-1,\ldots,-1}_{y_1,\ldots,y_{k-1}},\underbrace{0,\ldots,0}_{\text{remaining coordinates}}\right)^T. s = x 1 , … , x m 0 , … , 0 , y 1 , … , y k − 1 − 1 , … , − 1 , remaining coordinates 0 , … , 0 T .
In particular, s ∣ S = 0 s|_S=0 s ∣ S = 0 .
For u = 0 u=0 u = 0 , we may take w = − s w=-s w = − s . Then w ∈ Λ − s w\in\Lambda-s w ∈ Λ − s , w ∣ S = u w|_S=u w ∣ S = u , and ∥ w ∥ p p = k − 1 ≤ W \lVert w\rVert_p^p=k-1\le W ∥ w ∥ p p = k − 1 ≤ W , as required in Equation (2) . Now fix a nonzero u u u with ∥ u ∥ p ≤ d \lVert u\rVert_p\le d ∥ u ∥ p ≤ d , and let I = { i : u i ≠ 0 } I=\{i:u_i\ne0\} I = { i : u i = 0 } . We seek a vector of the form
w = ∑ ℓ = 1 k − 1 e z ℓ + ∑ i ∈ I u i ( e x i − e x i + τ ) , z 1 , … , z k − 1 , τ ∈ F q . w=\sum_{\ell=1}^{k-1}e_{z_\ell}+\sum_{i\in I}u_i(e_{x_i}-e_{x_i+\tau}),\qquad z_1,\ldots,z_{k-1},\tau\in\mathbb{F}_q. w = ℓ = 1 ∑ k − 1 e z ℓ + i ∈ I ∑ u i ( e x i − e x i + τ ) , z 1 , … , z k − 1 , τ ∈ F q .
The second sum places u \mathbf{u} u on S S S together with a copy of − u -\mathbf{u} − u shifted by τ \tau τ , and we seek τ \tau τ and the positions { z ℓ } 1 ≤ ℓ < k \{z_\ell\}_{1\le\ell<k} { z ℓ } 1 ≤ ℓ < k so that s + w ∈ Λ \mathbf{s}+\mathbf{w}\in\Lambda s + w ∈ Λ . The required restriction and norm bound follow if the positions z ℓ z_\ell z ℓ and x i + τ x_i+\tau x i + τ are distinct and outside S S S . In this case, w \mathbf{w} w has the form
w = ( u 1 , … , u m ⏟ x 1 , … , x m , 1 , … , 1 ⏟ z 1 , … , z k − 1 , ( − u i ) i ∈ I ⏟ ( x i + τ ) i ∈ I , 0 , … , 0 ⏟ remaining coordinates ) T . \mathbf{w}=\left(\underbrace{u_1,\ldots,u_m}_{x_1,\ldots,x_m},\underbrace{1,\ldots,1}_{z_1,\ldots,z_{k-1}},\underbrace{(-u_i)_{i\in I}}_{(x_i+\tau)_{i\in I}},\underbrace{0,\ldots,0}_{\text{remaining coordinates}}\right)^{T}. w = x 1 , … , x m u 1 , … , u m , z 1 , … , z k − 1 1 , … , 1 , ( x i + τ ) i ∈ I ( − u i ) i ∈ I , remaining coordinates 0 , … , 0 T .
Consequently,
w ∣ S = u , ∥ w ∥ p p = k − 1 + 2 ∥ u ∥ p p ≤ k − 1 + 2 d p . \mathbf{w}|_S=\mathbf{u},\qquad\|\mathbf{w}\|_p^p=k-1+2\|\mathbf{u}\|_p^p\le k-1+2d^p. w ∣ S = u , ∥ w ∥ p p = k − 1 + 2∥ u ∥ p p ≤ k − 1 + 2 d p .
For vectors of this form, the condition s + w ∈ Λ \mathbf{s}+\mathbf{w}\in\Lambda s + w ∈ Λ is equivalent to k − 1 k-1 k − 1 polynomial equations in the coordinate labels. The condition in Equation (3) for j = 0 j=0 j = 0 holds automatically because the entries of s + w \mathbf{s}+\mathbf{w} s + w sum to zero. The remaining conditions are f j ( z 1 , … , z k − 1 , τ ) = 0 f_j(z_1,\ldots,z_{k-1},\tau)=0 f j ( z 1 , … , z k − 1 , τ ) = 0 for 1 ≤ j < k 1\le j<k 1 ≤ j < k , where
f j ( Z 1 , … , Z k − 1 , Y ) = ∑ ℓ = 1 k − 1 ( Z ℓ j − y ℓ j ) − ∑ i ∈ I u i ( ( x i + Y ) j − x i j ) . f_j(Z_1,\ldots,Z_{k-1},Y)=\sum_{\ell=1}^{k-1}(Z_\ell^j-y_\ell^j)-\sum_{i\in I}u_i\left((x_i+Y)^j-x_i^j\right). f j ( Z 1 , … , Z k − 1 , Y ) = ℓ = 1 ∑ k − 1 ( Z ℓ j − y ℓ j ) − i ∈ I ∑ u i ( ( x i + Y ) j − x i j ) .
These equations have a common zero ξ = ( y 1 , … , y k − 1 , 0 ) \xi=(y_1,\ldots,y_{k-1},0) ξ = ( y 1 , … , y k − 1 , 0 ) . At this point, the entries u i u_i u i and − u i -u_i − u i occupy the same coordinates and cancel, leaving w = − s \mathbf{w}=-\mathbf{s} w = − s and w ∣ S = 0 \mathbf{w}|_S=0 w ∣ S = 0 . Our goal is to find another common zero for which the field elements z 1 , … , z k − 1 z_1,\ldots,z_{k-1} z 1 , … , z k − 1 and x i + τ x_i+\tau x i + τ (i ∈ I i\in I i ∈ I ) are all distinct and lie outside S S S . We express these requirements by one more polynomial g g g , which is nonzero only when they hold. Let E = { x b − x i : b ∈ [ m ] , i ∈ I } E=\{x_b-x_i:b\in[m],\,i\in I\} E = { x b − x i : b ∈ [ m ] , i ∈ I } and define
g ( Z 1 , … , Z k − 1 , Y ) = Y ∏ e ∈ E ∖ { 0 } ( Y − e ) ∏ ℓ = 1 k − 1 ∏ b = 1 m ( Z ℓ − x b ) ∏ 1 ≤ ℓ < ℓ ′ < k ( Z ℓ − Z ℓ ′ ) ∏ ℓ = 1 k − 1 ∏ i ∈ I ( Z ℓ − x i − Y ) . g(Z_1,\ldots,Z_{k-1},Y)=Y\prod_{e\in E\setminus\{0\}}(Y-e)\prod_{\ell=1}^{k-1}\prod_{b=1}^{m}(Z_\ell-x_b)\prod_{1\le\ell<\ell'<k}(Z_\ell-Z_{\ell'})\prod_{\ell=1}^{k-1}\prod_{i\in I}(Z_\ell-x_i-Y). g ( Z 1 , … , Z k − 1 , Y ) = Y e ∈ E ∖ { 0 } ∏ ( Y − e ) ℓ = 1 ∏ k − 1 b = 1 ∏ m ( Z ℓ − x b ) 1 ≤ ℓ < ℓ ′ < k ∏ ( Z ℓ − Z ℓ ′ ) ℓ = 1 ∏ k − 1 i ∈ I ∏ ( Z ℓ − x i − Y ) .
It is straightforward to verify that g ( ξ ) = 0 g(\xi)=0 g ( ξ ) = 0 . If g ( z 1 , … , z k − 1 , τ ) ≠ 0 g(z_1,\ldots,z_{k-1},\tau)\ne0 g ( z 1 , … , z k − 1 , τ ) = 0 , the factors involving only Y Y Y ensure that x i + τ ∉ S x_i+\tau\notin S x i + τ ∈ / S for every i ∈ I i\in I i ∈ I . The remaining products ensure, respectively, that the z ℓ z_\ell z ℓ lie outside S S S , that they are distinct from one another, and that none equals x i + τ x_i+\tau x i + τ for any i ∈ I i\in I i ∈ I . The elements x i + τ x_i+\tau x i + τ are distinct from one another because the x i x_i x i are distinct. Over the real numbers, the implicit function theorem would let us move τ \tau τ slightly away from 0 0 0 and adjust z 1 , … , z k − 1 z_1,\ldots,z_{k-1} z 1 , … , z k − 1 so that the equations still hold, provided that the Jacobian matrix with respect to Z 1 , … , Z k − 1 Z_1,\ldots,Z_{k-1} Z 1 , … , Z k − 1 is invertible at ξ \xi ξ . For small nonzero τ \tau τ , the conditions above would then hold as well. A finite field has no notion of a small change, so we instead use the following finite-field version of the implicit function theorem.
Lemma 1.4 (Informal; see Lemma 2.19 ). Let f 1 , … , f n ∈ F Q [ X 1 , … , X n ] f_1,\ldots,f_n\in\mathbb{F}_Q[X_1,\ldots,X_n] f 1 , … , f n ∈ F Q [ X 1 , … , X n ] have a common zero ξ ∈ F Q n \xi\in\mathbb{F}_Q^n ξ ∈ F Q n at which their Jacobian matrix is invertible. If Q Q Q is large compared with the degrees of f 1 , … , f n f_1,\ldots,f_n f 1 , … , f n , then there exists x ∈ F Q n x\in\mathbb{F}_Q^n x ∈ F Q n with f 1 ( x ) = ⋯ = f n − 1 ( x ) = 0 f_1(x)=\cdots=f_{n-1}(x)=0 f 1 ( x ) = ⋯ = f n − 1 ( x ) = 0 and f n ( x ) ≠ 0 f_n(x)\ne0 f n ( x ) = 0 .
We now verify the Jacobian condition in Lemma 1.4 . The Jacobian matrix of f 1 , … , f k − 1 f_1,\ldots,f_{k-1} f 1 , … , f k − 1 with respect to Z 1 , … , Z k − 1 Z_1,\ldots,Z_{k-1} Z 1 , … , Z k − 1 at ξ \xi ξ is
( j y ℓ j − 1 ) 1 ≤ j , ℓ < k , \left(jy_\ell^{j-1}\right)_{1\le j,\ell<k}, ( j y ℓ j − 1 ) 1 ≤ j , ℓ < k ,
which is invertible because the y ℓ y_\ell y ℓ are distinct and q > k q>k q > k . Only the factor Y Y Y in g g g vanishes at ξ \xi ξ . Thus g ( ξ ) = 0 g(\xi)=0 g ( ξ ) = 0 , ∂ g / ∂ Y \partial g/\partial Y ∂ g / ∂ Y is nonzero at ξ \xi ξ , and every ∂ g / ∂ Z ℓ \partial g/\partial Z_\ell ∂ g / ∂ Z ℓ vanishes there. Together, these facts show that the Jacobian of f 1 , … , f k − 1 , g f_1,\ldots,f_{k-1},g f 1 , … , f k − 1 , g with respect to Z 1 , … , Z k − 1 , Y Z_1,\ldots,Z_{k-1},Y Z 1 , … , Z k − 1 , Y is invertible at ξ \xi ξ .
For sufficiently large q q q , applying Lemma 1.4 to f 1 , … , f k − 1 , g f_1,\ldots,f_{k-1},g f 1 , … , f k − 1 , g gives a common zero x = ( z 1 , … , z k − 1 , τ ) x=(z_1,\ldots,z_{k-1},\tau) x = ( z 1 , … , z k − 1 , τ ) of the f j f_j f j 's at which g ≠ 0 g\ne0 g = 0 . The resulting vector w \mathbf{w} w belongs to Λ − s \Lambda-s Λ − s and satisfies
w ∣ S = u , ∥ w ∥ p p = k − 1 + 2 ∥ u ∥ p p ≤ k − 1 + 2 d p , \mathbf{w}|_S=u,\qquad\|\mathbf{w}\|_p^p=k-1+2\|u\|_p^p\le k-1+2d^p, w ∣ S = u , ∥ w ∥ p p = k − 1 + 2∥ u ∥ p p ≤ k − 1 + 2 d p ,
as required in Equation (2) .
Finally, we explain why the construction takes FPT time. Once the prime q q q is chosen, we form the k × q k\times q k × q matrix ( z j ) 0 ≤ j < k , z ∈ F q (z^j)_{0\le j<k,z\in\mathbb{F}_q} ( z j ) 0 ≤ j < k , z ∈ F q that defines Λ \Lambda Λ . Gaussian elimination over F q \mathbb{F}_q F q reduces the defining congruences to a form from which we can construct an integer basis of Λ \Lambda Λ . We also choose m + k − 1 m+k-1 m + k − 1 distinct field elements and use them to define s s s and S S S as above. These computations take time polynomial in q q q . For sufficiently large γ \gamma γ , we choose k k k as a function of d d d just above ( γ d ) p / 2 (\gamma d)^p/2 ( γ d ) p /2 , so that k > d p k>d^p k > d p and ( 2 k ) 1 / p > γ d (2k)^{1/p}>\gamma d ( 2 k ) 1/ p > γ d . The resulting approximation factor γ d / ( k + 3 d p ) 1 / p \gamma d/(k+3d^p)^{1/p} γ d / ( k + 3 d p ) 1/ p approaches 2 1 / p 2^{1/p} 2 1/ p as γ \gamma γ grows. For every u ∈ Z m u\in\mathbb{Z}^m u ∈ Z m with ∥ u ∥ p ≤ d \|u\|_p\le d ∥ u ∥ p ≤ d , its support I = { i ∈ [ m ] : u i ≠ 0 } I=\{i\in[m]:u_i\ne0\} I = { i ∈ [ m ] : u i = 0 } has size ∣ I ∣ ≤ d p < k |I|\le d^p<k ∣ I ∣ ≤ d p < k . The degrees of the f j f_j f j are 1 , … , k − 1 1,\ldots,k-1 1 , … , k − 1 , while deg g = O ( k m + k 2 ) \deg g=O(km+k^2) deg g = O ( k m + k 2 ) . By Lemma 1.4 , the required field size is therefore at most a function of k k k times m m m . We can thus choose a prime q ≤ f ( k ) m q\le f(k)m q ≤ f ( k ) m that works for every such u u u . Finding such a prime and carrying out the construction take time polynomial in q q q , giving a total running time of f ( d ) m O ( 1 ) f(d)m^{O(1)} f ( d ) m O ( 1 ) .
Wan [Wan26b] also constructs locally dense lattices from Reed–Solomon codes deterministically, and counts the points of higher-dimensional varieties using Deligne’s theorem. Our lemma needs only the Weil bound for curves [37 CM06] . In return, it requires the field size to exceed a fixed power of the product of the degrees of f 1 , … , f n − 1 f_1,\ldots,f_{n-1} f 1 , … , f n − 1 . The parameterized setting can afford this, because these degrees depend only on the parameter.
The Reduction for the Minimum Distance Problem
We apply an idea similar to that used for lattices to codes to establish the W[1]-hardness of MDP. More specifically, our reduction builds on that of Hirahara and Ogitsuka [23 ] , and we deterministically construct a locally dense code , the coding analogue of a locally dense lattice. Informally, many codewords lie in a Hamming ball centered at s s s whose radius is smaller than the minimum distance of the code.
To reduce NCP to MDP, we use selected coordinates of the locally dense code to represent the difference between an input codeword and the target. Given an NCP instance ( G , t , k ) (G,t,k) ( G , t , k ) with m m m coordinates, we construct a code generated by A A A , a center s s s , and an ordered list S S S of m m m coordinates, with s ∣ S = 0 s|_S=0 s ∣ S = 0 . For every x x x satisfying ∥ G x − t ∥ 0 ≤ k \|Gx-t\|_0\le k ∥ G x − t ∥ 0 ≤ k , there must be a vector A y − s Ay-s A y − s that is nonzero, has Hamming weight bounded by a fixed multiple of k k k , and satisfies
( A y − s ) ∣ S = G x − t . (Ay-s)|_S=Gx-t. ( A y − s ) ∣ S = G x − t .
Since s ∣ S = 0 s|_S=0 s ∣ S = 0 , this equality gives G x − t − A S y = 0 Gx-t-A_Sy=0 G x − t − A S y = 0 . We require A y − s Ay-s A y − s to be nonzero even when G x = t Gx=t G x = t , so that the output contains a nonzero codeword in this case as well.
The reduction replaces multiplication by a large integer with repetition of coordinates. Multiplication by a nonzero field element preserves Hamming weight, whereas repeating each coordinate multiplies the weight by the number of repetitions. In a YES instance, the repeated coordinates are copies of the entries of G x − t − A S y Gx-t-A_Sy G x − t − A S y and are therefore zero. We choose the number of repetitions so that any nonzero entry in these coordinates makes the output weight exceed the NO threshold. A nonzero coefficient of the target can be divided out without changing Hamming weight, so the NO condition of NCP applies to that case.
Constructing the locally dense codes. We construct the locally dense code from an extended BCH code over a fixed prime field F p \mathbb{F}_p F p . Let K K K be a sufficiently large extension field of F p \mathbb{F}_p F p , and let D D D be the chosen distance bound. Codeword entries belong to F p \mathbb{F}_p F p , while coordinates are indexed by K K K . We define
C = { c ∈ F p K : ∑ z ∈ K c z = 0 , ∑ z ∈ K c z z j = 0 ( 1 ≤ j < D , p ∤ j ) } . \mathcal{C}=\left\{c\in\mathbb{F}_p^K:\sum_{z\in K}c_z=0,\quad\sum_{z\in K}c_z z^j=0\quad(1\leq j<D,\ p\nmid j)\right\}. C = { c ∈ F p K : z ∈ K ∑ c z = 0 , z ∈ K ∑ c z z j = 0 ( 1 ≤ j < D , p ∤ j ) } .
Here we omit the equations for positive exponents divisible by p p p . Since c z p = c z c_z^p=c_z c z p = c z for every c z ∈ F p c_z\in\mathbb{F}_p c z ∈ F p , we have
( ∑ z ∈ K c z z j ) p = ∑ z ∈ K c z z p j . \left(\sum_{z\in K}c_z z^j\right)^p=\sum_{z\in K}c_z z^{pj}. ( z ∈ K ∑ c z z j ) p = z ∈ K ∑ c z z p j .
Applying this identity repeatedly gives all the omitted equations. Thus, the code is the same as the one defined by imposing the moment equations for every exponent 0 ≤ j < D 0\leq j<D 0 ≤ j < D , and its minimum distance is unchanged.
We use the same expression for w \mathbf{w} w as in the lattice construction, now with coefficients in the prime field and one added unit vector for each remaining positive exponent. The coordinates of s + w \mathbf{s}+\mathbf{w} s + w sum to zero, so only the moment equations with positive exponents remain to be satisfied. Omitting the redundant equations reduces the number of added unit vectors and hence the upper bound on the Hamming weight of w \mathbf{w} w . Choosing the BCH distance sufficiently large compared with k k k then gives a constant gap between the YES and NO thresholds.
We choose the support of s \mathbf{s} s so that the Jacobian with respect to the variables Z ℓ Z_\ell Z ℓ is invertible at the known solution. As in the lattice construction, each Z ℓ Z_\ell Z ℓ specifies the coordinate at which an added unit vector is placed. For the remaining positive exponents j j j , the derivatives j Z j − 1 jZ^{j-1} j Z j − 1 are linearly independent polynomials. Evaluating them over a sufficiently large extension field gives a matrix of full row rank. We select independent columns by Gaussian elimination and use their indices as the support of s \mathbf{s} s .
The polynomial g g g only needs to prevent the added terms from changing the entries on S S S . We choose it so that g ≠ 0 g\ne0 g = 0 forces the coordinates occupied by the translated negative of G x − t \mathbf{G}\mathbf{x}-\mathbf{t} Gx − t and by the added unit vectors to lie outside S S S . These coordinates may coincide with one another, since such coincidences cannot increase Hamming weight. For a nonzero difference G x − t \mathbf{G}\mathbf{x}-\mathbf{t} Gx − t , the lemma above therefore guarantees a vector w \mathbf{w} w of Hamming weight at most a fixed multiple of k k k such that s + w \mathbf{s}+\mathbf{w} s + w belongs to the code and w ∣ S = G x − t \mathbf{w}|_S=\mathbf{G}\mathbf{x}-\mathbf{t} w ∣ S = Gx − t . When the difference is zero, we take w = − s \mathbf{w}=-\mathbf{s} w = − s . As before, the field size bound allows us to construct A A A , s \mathbf{s} s , and S S S in deterministic FPT time.
All fixed finite fields and any constant approximation factor. We extend the result to every fixed finite field and every constant approximation factor by extending the coefficient field and taking tensor powers. Viewing the same generator matrix over an extension field preserves its minimum distance. The minimum distance of a tensor product of codes is the product of their minimum distances, so a constant number of tensor factors amplifies the gap to any prescribed constant.
Related Work
Ajtai–Micciancio’s approach uses locally dense lattices to prove the classical NP-hardness of SVP. The notion of a locally dense lattice used in our reductions is a variant of the one used in this approach. However, the existing constructions in this approach do not directly apply to the parameterized setting considered here [23 Section 1.2] . This approach originated in the work of Ajtai [3 ] , whose construction uses a variant of the Schnorr–Adleman prime number lattice. Micciancio [31 ] used a simpler variant of this lattice to prove NP-hardness of approximating SVP under randomized reductions with one-sided error. Micciancio [32 ] later constructed locally dense lattices by applying “Construction D” [12 ] to a nested sequence of extended binary BCH codes and obtained such reductions for every constant approximation factor in the Euclidean norm. Bennett and Peikert [8 ] gave a simpler construction by applying “Construction A” [12 ] to Reed–Solomon codes. Recently, Wan [Wan26b; Wan26a] derandomized this approach by deterministically constructing a suitable center and projection for these Reed–Solomon lattices.
Dumer, Micciancio, and Sudan [18 ] adapted Ajtai–Micciancio’s approach to linear codes, using locally dense codes to prove NP-hardness of approximating MDP under randomized reductions. Cheng and Wan [13 ] derandomized this reduction using Reed–Solomon codes concatenated with Hadamard codes. They explicitly constructed a center and a coordinate projection satisfying the properties required by the reduction. Micciancio [33 ] later gave a general deterministic construction that transforms binary codes with sufficiently large relative minimum distance into locally dense binary codes. His construction uses tensor products and produces an explicit center and coordinate projection, providing another way to derandomize the reduction of Dumer, Micciancio, and Sudan.
Khot [29 ] developed another approach to proving NP-hardness of approximating SVP, combining locally dense lattices with random sparsification. His construction uses lattices obtained from binary BCH codes. Haviv and Regev [24 ] subsequently showed that standard tensor products of the lattices arising in Khot’s reduction can amplify the approximation gap.
Variants of Khot’s approach have also been used to establish fine-grained hardness of SVP. Aggarwal and Stephens-Davidowitz [5 ] showed that, under randomized Gap-ETH, for every fixed p > 2 p > 2 p > 2 , there is a constant approximation factor greater than one for which SVP in the ℓ p \ell_p ℓ p norm admits no algorithm whose running time is subexponential in the lattice rank. Aggarwal, Gupta, Morolia, and Zhang [2 ] later obtained analogous lower bounds under randomized ETH.2 The locally dense lattices used in these reductions still have many lattice points close to a common center, but the required local density condition differs from those discussed above. Specifically, the number of lattice points in a ball around the center must be exponentially larger than the number in a slightly larger ball around the origin. The radius of the ball around the center need not be smaller than the length of a shortest nonzero lattice vector.
Open Problems
Theorems 1.1 and 1.2 concern constant approximation factors. In the classical setting, Hair and Sahai [26 ] proved that, for every p > 2 p > 2 p > 2 , SVP in the ℓ p \ell_p ℓ p norm is NP-hard to approximate within a polynomial factor under deterministic reductions. A natural question is whether γ \gamma γ -GapSVPp _p p remains W[1]-hard when γ \gamma γ grows polynomially with the rank of the lattice.
Another open problem is to make Lemma 1.4 constructive, that is, to give an efficient algorithm that finds a point x x x with f 1 ( x ) = ⋯ = f n − 1 ( x ) = 0 f_1(x) = \cdots= f_{n-1}(x) = 0 f 1 ( x ) = ⋯ = f n − 1 ( x ) = 0 and f n ( x ) ≠ 0 f_n(x) \ne0 f n ( x ) = 0 .
Organization. § 2 gives the preliminaries and proves the key Lemma 2.19 in § 2.5 . § 4 proves Theorem 1.1 , our main result on SVP, and § 5 proves Theorem 1.3 , our main result on MDP. Section A extends the result on SVP to every constant factor and proves Theorem 1.2 .
Preliminaries
Notation
For a positive integer n n n , write [ n ] = { 1 , … , n } [n] = \{1,\ldots,n\} [ n ] = { 1 , … , n } . We regard vectors as column vectors, even when their coordinates are written as a tuple. For a matrix A \mathbf{A} A , we write A i j A_{ij} A ij for its entry in row i i i and column j j j . The notation ( a i j ) i ∈ I , j ∈ J (a_{ij})_{i\in I,j\in J} ( a ij ) i ∈ I , j ∈ J denotes the matrix with rows indexed by I I I , columns indexed by J J J , and entry a i j a_{ij} a ij in row i i i and column j j j . We write 0 \mathbf{0} 0 for a zero vector and 0 \mathbf{0} 0 for a zero matrix, with dimensions determined by context. The matrix I n I_n I n is the n × n n \times n n × n identity matrix. In a block matrix, matrices and column vectors are placed side by side or one above another, with matching dimensions. For a finite set T T T and a field K K K , K T K^T K T denotes vectors with entries in K K K indexed by T T T ; Z T \mathbb{Z}^T Z T denotes integer vectors indexed by T T T . For z ∈ T z \in T z ∈ T , the vector e z ∈ K T e_z \in K^T e z ∈ K T has entry 1 1 1 at z z z and 0 0 0 elsewhere; the same notation denotes the corresponding vector in Z T \mathbb{Z}^T Z T . The support of v v v is { z : v z ≠ 0 } \{z : v_z \ne0\} { z : v z = 0 } , and its cardinality ∥ v ∥ 0 \lVert v\rVert_0 ∥ v ∥ 0 is its Hamming weight. For a real vector, ∥ v ∥ p = ( ∑ z ∣ v z ∣ p ) 1 / p \lVert v\rVert_p = \left(\sum_z |v_z|^p\right)^{1/p} ∥ v ∥ p = ( ∑ z ∣ v z ∣ p ) 1/ p for 1 ≤ p < ∞ 1 \le p < \infty 1 ≤ p < ∞ , and ∥ v ∥ ∞ = max z ∣ v z ∣ \lVert v\rVert_\infty= \max_z |v_z| ∥ v ∥ ∞ = max z ∣ v z ∣ .
For an ordered list S = ( x 1 , … , x m ) S = (x_1,\ldots,x_m) S = ( x 1 , … , x m ) of distinct coordinates, put v ∣ S = ( v x 1 , … , v x m ) v|_S = (v_{x_1},\ldots,v_{x_m}) v ∣ S = ( v x 1 , … , v x m ) . For a set of vectors V V V , write V − s = { v − s : v ∈ V } V - s = \{v-s : v \in V\} V − s = { v − s : v ∈ V } . When V V V is a linear code or a lattice, this translate is a coset. The Kronecker product G ⊗ A \mathbf{G} \otimes\mathbf{A} G ⊗ A is the block matrix whose ( i , j ) (i,j) ( i , j ) block is G i j A G_{ij}\mathbf{A} G ij A ; G ⊗ ℓ \mathbf{G}^{\otimes\ell} G ⊗ ℓ denotes the Kronecker product of ℓ \ell ℓ copies of G \mathbf{G} G .
A real number is computable if an algorithm, given r ∈ Z > 0 r \in\mathbb{Z}_{>0} r ∈ Z > 0 , returns a rational approximation with error at most 2 − r 2^{-r} 2 − r .
Finite fields and polynomials
For a prime power q q q , F q \mathbb{F}_q F q denotes the field with q q q elements. For prime p p p , F p = Z / p Z \mathbb{F}_p = \mathbb{Z}/p\mathbb{Z} F p = Z / p Z . A field extension K / F K/F K / F is a field K K K containing F F F as a subfield. Its degree is the dimension of K K K as a vector space over F F F . An F F F -basis of K K K expresses each element of K K K uniquely as an F F F -linear combination of the basis elements. The field F q s \mathbb{F}_{q^s} F q s is an extension of F q \mathbb{F}_q F q of degree s s s .
For a field K K K and variables X 1 , … , X r X_1,\ldots,X_r X 1 , … , X r , the ring K [ X 1 , … , X r ] K[X_1,\ldots,X_r] K [ X 1 , … , X r ] consists of polynomials in these variables with coefficients in K K K . For a tuple of variables X = ( X 1 , … , X r ) X = (X_1,\ldots,X_r) X = ( X 1 , … , X r ) , write K [ X ] = K [ X 1 , … , X r ] K[X] = K[X_1,\ldots,X_r] K [ X ] = K [ X 1 , … , X r ] and f ( X ) = f ( X 1 , … , X r ) f(X) = f(X_1,\ldots,X_r) f ( X ) = f ( X 1 , … , X r ) for f ∈ K [ X ] f \in K[X] f ∈ K [ X ] . For a nonzero polynomial f ∈ K [ X 1 , … , X r ] f \in K[X_1,\ldots,X_r] f ∈ K [ X 1 , … , X r ] , its total degree deg f \deg f deg f is the largest sum of exponents among its monomials with nonzero coefficient. For i ∈ [ r ] i \in[r] i ∈ [ r ] , its degree in X i X_i X i , denoted by deg X i f \deg_{X_i} f deg X i f , is the largest exponent of X i X_i X i among those monomials. We set deg 0 = deg X 0 = − ∞ \deg0 = \deg_X 0 = -\infty deg 0 = deg X 0 = − ∞ . For elements a 1 , … , a r ∈ K a_1,\ldots,a_r \in K a 1 , … , a r ∈ K , the value f ( a 1 , … , a r ) f(a_1,\ldots,a_r) f ( a 1 , … , a r ) is obtained by substituting a i a_i a i for X i X_i X i for every i ∈ [ r ] i \in[r] i ∈ [ r ] . A common zero of several polynomials is a tuple at which all of them vanish. An affine linear polynomial in K [ X 1 , … , X r ] K[X_1,\ldots,X_r] K [ X 1 , … , X r ] has the form a 0 + ∑ i = 1 r a i X i a_0+\sum_{i=1}^r a_iX_i a 0 + ∑ i = 1 r a i X i , where a 0 , … , a r ∈ K a_0,\ldots,a_r \in K a 0 , … , a r ∈ K . It is nonconstant if at least one a i a_i a i with i ≥ 1 i \ge1 i ≥ 1 is nonzero.
For a polynomial f ∈ K [ X 1 , … , X r ] f \in K[X_1,\ldots,X_r] f ∈ K [ X 1 , … , X r ] , the formal partial derivative ∂ f / ∂ X i \partial f/\partial X_i ∂ f / ∂ X i is obtained term by term, treating the other variables as constants and using ∂ X i a / ∂ X i = a X i a − 1 \partial X_i^a/\partial X_i = aX_i^{a-1} ∂ X i a / ∂ X i = a X i a − 1 for a ≥ 1 a \ge1 a ≥ 1 and ∂ 1 / ∂ X i = 0 \partial1/\partial X_i = 0 ∂ 1/ ∂ X i = 0 . The coefficient a a a is interpreted in K K K . For polynomials f 1 , … , f r ∈ K [ X 1 , … , X n ] f_1,\ldots,f_r \in K[X_1,\ldots,X_n] f 1 , … , f r ∈ K [ X 1 , … , X n ] and a point ξ ∈ K n \xi\in K^n ξ ∈ K n , their Jacobian matrix at ξ \xi ξ is the r × n r \times n r × n matrix
( ∂ f i ∂ X j ( ξ ) ) i ∈ [ r ] , j ∈ [ n ] \left(\frac{\partial f_i}{\partial X_j}(\xi)\right)_{i\in[r],j\in[n]} ( ∂ X j ∂ f i ( ξ ) ) i ∈ [ r ] , j ∈ [ n ]
For distinct a 1 , … , a r ∈ K a_1,\ldots,a_r \in K a 1 , … , a r ∈ K , the Vandermonde matrix ( a j i − 1 ) i , j ∈ [ r ] (a_j^{i-1})_{i,j\in[r]} ( a j i − 1 ) i , j ∈ [ r ] has determinant ∏ i < j ( a j − a i ) ≠ 0 \prod_{i<j}(a_j-a_i) \ne0 ∏ i < j ( a j − a i ) = 0 . A nonzero univariate polynomial is monic if its leading coefficient is 1. A nonconstant polynomial f ∈ K [ X 1 , … , X r ] f \in K[X_1,\ldots,X_r] f ∈ K [ X 1 , … , X r ] is irreducible over K K K if it cannot be written as a product of two nonconstant polynomials in K [ X 1 , … , X r ] K[X_1,\ldots,X_r] K [ X 1 , … , X r ] . For a nonzero polynomial f ∈ K [ X ] f \in K[X] f ∈ K [ X ] and a root a ∈ K a \in K a ∈ K , the multiplicity of a a a is the largest integer e ≥ 1 e \ge1 e ≥ 1 such that ( X − a ) e (X-a)^e ( X − a ) e divides f f f . For a nonconstant polynomial g ∈ F q [ X ] g \in\mathbb{F}_q[X] g ∈ F q [ X ] , the quotient ring F q [ X ] / ( g ) \mathbb{F}_q[X]/(g) F q [ X ] / ( g ) consists of polynomials modulo g g g , with addition and multiplication modulo g g g . If g g g is irreducible of degree s s s , this quotient is a field with q s q^s q s elements, represented by polynomials of degree less than s s s .
Lattice and Coding Problems
We recall the basic definitions of parameterized promise problems. For details on parameterized complexity, see [16 , 15 , 14 ] .
Definition 2.1 (Parameterized promise problems). A parameterized promise problem is a pair of disjoint languages Π = ( Π Y E S , Π N O ) \Pi=(\Pi_{\mathrm{YES}},\Pi_{\mathrm{NO}}) Π = ( Π YES , Π NO ) over Σ ∗ × N \Sigma^* \times\mathbb{N} Σ ∗ × N . An instance of Π \Pi Π is a pair ( x , k ) ∈ Σ ∗ × N (x,k)\in\Sigma^* \times\mathbb{N} ( x , k ) ∈ Σ ∗ × N , where k k k is called the parameter . The set Π Y E S ∪ Π N O \Pi_{\mathrm{YES}}\cup\Pi_{\mathrm{NO}} Π YES ∪ Π NO is called the promise .
Given a matrix B ∈ Z m × n \mathbf{B} \in\mathbb{Z}^{m\times n} B ∈ Z m × n , the lattice generated by its columns is L = L ( B ) : = { B z : z ∈ Z n } ⊆ Z m \mathcal{L}=\mathcal{L}(\mathbf{B}):=\{\mathbf{B}z:z\in\mathbb{Z}^n\}\subseteq\mathbb{Z}^m L = L ( B ) := { B z : z ∈ Z n } ⊆ Z m . When the columns of B \mathbf{B} B are linearly independent, B \mathbf{B} B is referred to as a lattice basis for L ( B ) \mathcal{L}(\mathbf{B}) L ( B ) . For p ∈ [ 1 , ∞ ] p\in[1,\infty] p ∈ [ 1 , ∞ ] , the length of a shortest nonzero lattice vector, measured in the ℓ p \ell_p ℓ p norm, is given by λ 1 ( p ) ( L ) : = min v ∈ L ∖ { 0 } ∥ v ∥ p \lambda_1^{(p)}(\mathcal{L}):=\min_{v\in\mathcal{L}\setminus\{0\}}\|v\|_p λ 1 ( p ) ( L ) := min v ∈ L ∖ { 0 } ∥ v ∥ p . Given a target vector t ∈ R m \mathbf{t}\in\mathbb{R}^m t ∈ R m , its distance from the lattice is denoted by dist p ( L , t ) : = min v ∈ L ∥ v − t ∥ p \operatorname{dist}_p(\mathcal{L},\mathbf{t}):=\min_{v\in\mathcal{L}}\|v-\mathbf{t}\|_p dist p ( L , t ) := min v ∈ L ∥ v − t ∥ p .
The Shortest Vector Problem (SVP) is the problem of finding a shortest nonzero vector in a lattice, given a basis matrix of the lattice as input. Here, we consider an approximate version of the parameterized decision problem in which a parameter is given as an additional input, and the goal is to determine whether the length of a shortest nonzero lattice vector is at most the parameter.
Definition 2.2 (γ \gamma γ -GapSVPp _p p , [19 ] ). For p ≥ 1 p\ge1 p ≥ 1 and γ ≥ 1 \gamma\ge1 γ ≥ 1 , the parameterized promise problem γ \gamma γ -approximate Shortest Vector Problem (γ \gamma γ -GapSVPp _p p ) is defined as follows. Instances are pairs ( B , d ) (\mathbf{B},d) ( B , d ) , where B ∈ Z m × n \mathbf{B}\in\mathbb{Z}^{m\times n} B ∈ Z m × n is a lattice basis of L ( B ) \mathcal{L}(\mathbf{B}) L ( B ) , and d ∈ Z > 0 d\in\mathbb{Z}_{>0} d ∈ Z > 0 is a distance parameter such that
( B , d ) (\mathbf{B},d) ( B , d ) is a YES instance if λ 1 ( p ) ( L ( B ) ) ≤ d \lambda_1^{(p)}(\mathcal{L}(\mathbf{B}))\le d λ 1 ( p ) ( L ( B )) ≤ d ;
( B , d ) (\mathbf{B},d) ( B , d ) is a NO instance if λ 1 ( p ) ( L ( B ) ) > γ d \lambda_1^{(p)}(\mathcal{L}(\mathbf{B}))>\gamma d λ 1 ( p ) ( L ( B )) > γ d .
The parameter of interest is d d d .
To establish a reduction to SVP, we next define its inhomogeneous version, the Closest Vector Problem (CVP). In this definition, we require that, for NO instances, every nonzero integer multiple of the target vector is far from every lattice vector.
Definition 2.3 (γ \gamma γ -GapCVPp _p p , [7 ] ). For p ≥ 1 p\ge1 p ≥ 1 and γ ≥ 1 \gamma\ge1 γ ≥ 1 , the parameterized promise problem γ \gamma γ -approximate Closest Vector Problem (γ \gamma γ -GapCVPp _p p ) is defined as follows. Instances are tuples ( B , t , d ) (\mathbf{B},\mathbf{t},d) ( B , t , d ) , where B ∈ Z m × n \mathbf{B}\in\mathbb{Z}^{m\times n} B ∈ Z m × n is a lattice basis of L ( B ) \mathcal{L}(\mathbf{B}) L ( B ) , t ∈ Z m \mathbf{t}\in\mathbb{Z}^m t ∈ Z m is a target vector, and d ∈ Z > 0 d\in\mathbb{Z}_{>0} d ∈ Z > 0 is a distance parameter such that
( B , t , d ) (\mathbf{B},t,d) ( B , t , d ) is a YES instance if dist p ( L ( B ) , t ) ≤ d \operatorname{dist}_{p}(\mathcal{L}(\mathbf{B}),t) \le d dist p ( L ( B ) , t ) ≤ d ;
( B , t , d ) (\mathbf{B},t,d) ( B , t , d ) is a NO instance if dist p ( L ( B ) , w t ) > γ d \operatorname{dist}_{p}(\mathcal{L}(\mathbf{B}),wt) > \gamma d dist p ( L ( B ) , w t ) > γ d for all w ∈ Z \ { 0 } w \in\mathbb{Z}\backslash\{0\} w ∈ Z \ { 0 } .
The parameter of interest is d d d .
The following theorem states the W[1]-hardness of CVP under deterministic reductions.
Theorem 2.4 ([BBE+21, Theorem 7.2] and [7 Theorem 2.11] ). For any real numbers γ ≥ 1 \gamma\ge1 γ ≥ 1 and p ≥ 1 p \ge1 p ≥ 1 , γ \gamma γ -GapCVPp _p p is W[1]-hard under deterministic FPT many-one reductions.
For a matrix G ∈ F q m × n \mathbf{G} \in\mathbb{F}_q^{m \times n} G ∈ F q m × n , the linear code generated by the columns of G \mathbf{G} G is C = C ( G ) : = { G x : x ∈ F q n } ⊆ F q m C = \mathcal{C}(\mathbf{G}) := \{\mathbf{G}x : x \in\mathbb{F}_q^n\} \subseteq\mathbb{F}_q^m C = C ( G ) := { G x : x ∈ F q n } ⊆ F q m . A parity-check matrix for C C C is a matrix H \mathbf{H} H with C = ker H C = \ker\mathbf{H} C = ker H . The tensor product of two codes generated by G \mathbf{G} G and A \mathbf{A} A is the code generated by G ⊗ A \mathbf{G} \otimes\mathbf{A} G ⊗ A . The minimum distance of a nonzero linear code C ⊆ F q m C \subseteq\mathbb{F}_q^m C ⊆ F q m is λ ( C ) : = min c ∈ C \ { 0 } ∥ c ∥ 0 \lambda(C) := \min_{c \in C \backslash\{0\}} \lVert c \rVert_0 λ ( C ) := min c ∈ C \ { 0 } ∥ c ∥ 0 . We use the convention λ ( { 0 } ) : = + ∞ \lambda(\{0\}) := +\infty λ ({ 0 }) := + ∞ . For a target vector t ∈ F q m t \in\mathbb{F}_q^m t ∈ F q m , we write dist ( C , t ) : = min c ∈ C ∥ c − t ∥ 0 \operatorname{dist}(C,t) := \min_{c \in C} \lVert c-t \rVert_0 dist ( C , t ) := min c ∈ C ∥ c − t ∥ 0 .
The Minimum Distance Problem (MDP) is defined as follows. MDP can be viewed as the coding-theoretic counterpart of SVP.
Definition 2.5 (γ \gamma γ -GapMDPq _q q , [18 ] ). For γ ≥ 1 \gamma\ge1 γ ≥ 1 and a prime power q ≥ 2 q \ge2 q ≥ 2 , the parameterized promise problem γ \gamma γ -approximate Minimum Distance Problem over F q \mathbb{F}_q F q (γ \gamma γ -GapMDPq _q q ) is defined as follows. Instances are pairs ( G , k ) (\mathbf{G},k) ( G , k ) , where G ∈ F q m × n \mathbf{G} \in\mathbb{F}_q^{m \times n} G ∈ F q m × n is a generator matrix of C ( G ) \mathcal{C}(\mathbf{G}) C ( G ) , and k ∈ Z > 0 k \in\mathbb{Z}_{>0} k ∈ Z > 0 is a distance parameter such that
( G , k ) (\mathbf{G},k) ( G , k ) is a YES instance if λ ( C ( G ) ) ≤ k \lambda(\mathcal{C}(\mathbf{G})) \le k λ ( C ( G )) ≤ k ;
( G , k ) (\mathbf{G},k) ( G , k ) is a NO instance if λ ( C ( G ) ) > γ k \lambda(\mathcal{C}(\mathbf{G})) > \gamma k λ ( C ( G )) > γ k .
The parameter of interest is k k k .
Similarly to CVP, we next define the Nearest Codeword Problem (NCP), the inhomogeneous version of MDP.
Definition 2.6 (γ \gamma γ -GapNCPq _q q , [18 ] ). For γ ≥ 1 \gamma\ge1 γ ≥ 1 and a prime power q ≥ 2 q \ge2 q ≥ 2 , the parameterized promise problem γ \gamma γ -approximate Nearest Codeword Problem over F q \mathbb{F}_q F q (γ \gamma γ -GapNCPq _q q ) is defined as follows. Instances are tuples ( G , t , k ) (\mathbf{G},t,k) ( G , t , k ) , where G ∈ F q m × n \mathbf{G} \in\mathbb{F}_q^{m \times n} G ∈ F q m × n is a generator matrix of C ( G ) \mathcal{C}(\mathbf{G}) C ( G ) , t ∈ F q m t \in\mathbb{F}_q^m t ∈ F q m is a target vector, and k ∈ Z > 0 k \in\mathbb{Z}_{>0} k ∈ Z > 0 is a distance parameter such that
( G , t , k ) (\mathbf{G},t,k) ( G , t , k ) is a YES instance if dist ( C ( G ) , t ) ≤ k \operatorname{dist}(\mathcal{C}(\mathbf{G}),t) \le k dist ( C ( G ) , t ) ≤ k ;
( G , t , k ) (\mathbf{G},t,k) ( G , t , k ) is a NO instance if dist ( C ( G ) , t ) > γ k \operatorname{dist}(\mathcal{C}(\mathbf{G}),t) > \gamma k dist ( C ( G ) , t ) > γ k .
The parameter of interest is k k k .
The W[1]-hardness of NCP under deterministic reductions is also known.
Theorem 2.7 ([BBE+21, Theorem 5.1, adapted] and [7 Theorem 2.7] ). For any real number γ ≥ 1 \gamma\ge1 γ ≥ 1 and any prime power q ≥ 2 q \ge2 q ≥ 2 , γ \gamma γ -GapNCPq _q q is W[1]-hard under deterministic FPT many-one reductions.
Algorithms for finite fields, primes, and lattice bases
Our reductions require finite fields of suitable sizes and bases for lattices defined by linear congruences. We give deterministic algorithms for these tasks and record the bounds needed to ensure FPT running time.
We represent extension fields using irreducible polynomials. The following standard result guarantees that such a polynomial exists for every positive degree.
Lemma 2.8 ([30 ] ). For every prime power q q q and every integer s ≥ 1 s \ge1 s ≥ 1 , there exists a monic irreducible polynomial of degree s s s over F q \mathbb{F}_q F q .
For our purposes, it is enough to construct the field in time polynomial in its number of elements. The following lemma gives such a construction and shows when the required field computations take FPT time.
Lemma 2.9. Fix a prime power q q q . There exists a deterministic algorithm that, given s ∈ Z > 0 s \in\mathbb{Z}_{>0} s ∈ Z > 0 , constructs a representation of F q s \mathbb{F}_{q^s} F q s in time q O ( s ) q^{O(s)} q O ( s ) . In this representation, field arithmetic takes s O ( 1 ) s^{O(1)} s O ( 1 ) time, and all field elements can be enumerated in time q O ( s ) q^{O(s)} q O ( s ) .
Moreover, let f : Z > 0 → Z > 0 f:\mathbb{Z}_{>0} \to\mathbb{Z}_{>0} f : Z > 0 → Z > 0 be computable and let c ∈ Z > 0 c \in\mathbb{Z}_{>0} c ∈ Z > 0 be fixed. If k , m , s ∈ Z > 0 k,m,s \in\mathbb{Z}_{>0} k , m , s ∈ Z > 0 satisfy q s ≤ f ( k ) m c q^s \le f(k)m^c q s ≤ f ( k ) m c , then constructing the field, enumerating its elements, and performing a number of field operations polynomial in q s q^s q s and s s s take f 1 ( k ) m O ( 1 ) f_1(k)m^{O(1)} f 1 ( k ) m O ( 1 ) time for a computable function f 1 f_1 f 1 . The function f 1 f_1 f 1 and the constant in the exponent depend only on q q q , f f f , c c c , and the fixed polynomial bound on the number of field operations.
Proof. We represent F q s \mathbb{F}_{q^s} F q s as F q [ X ] / ( g ) \mathbb{F}_q[X]/(g) F q [ X ] / ( g ) for a monic irreducible polynomial g ∈ F q [ X ] g \in\mathbb{F}_q[X] g ∈ F q [ X ] of degree s s s . Such a polynomial exists by Lemma 2.8. Enumerate the monic polynomials of degree s s s over F q \mathbb{F}_q F q in a fixed order. For each candidate, test whether it is divisible by a monic polynomial of degree between 1 1 1 and ⌊ s / 2 ⌋ \lfloor s/2 \rfloor ⌊ s /2 ⌋ , by enumerating all such polynomials and computing the remainders. A polynomial of degree s s s is reducible if and only if it has a divisor in this range, so the first candidate that passes these tests is irreducible. There are q s q^s q s candidates and at most q s q^s q s possible divisors for each candidate, and each division takes s O ( 1 ) s^{O(1)} s O ( 1 ) time. Thus the search takes q O ( s ) q^{O(s)} q O ( s ) time.
Inverses are computed by the extended Euclidean algorithm. Field arithmetic takes s O ( 1 ) s^{O(1)} s O ( 1 ) time because q q q is fixed. Enumerating the q s q^s q s coefficient vectors of length s s s enumerates all field elements in time q O ( s ) q^{O(s)} q O ( s ) .
Any fixed polynomial in q s q^s q s and s s s , together with the preceding search time, is at most ( q s ) O ( 1 ) (q^s)^{O(1)} ( q s ) O ( 1 ) because s ≤ q s s \le q^s s ≤ q s . Under q s ≤ f ( k ) m c q^s \le f(k)m^c q s ≤ f ( k ) m c , this is f 1 ( k ) m O ( 1 ) f_1(k)m^{O(1)} f 1 ( k ) m O ( 1 ) for a computable function f 1 f_1 f 1 with the stated dependence. □
We next explain how to find a prime larger than a given bound. Bertrand’s postulate guarantees that such a prime exists below twice that bound, and deterministic primality testing allows us to find one by checking the candidates in order.
Lemma 2.10 (Bertrand’s postulate). For every integer T ≥ 2 T \ge2 T ≥ 2 , there is a prime Q Q Q with T < Q < 2 T T < Q < 2T T < Q < 2 T .
Theorem 2.11 ([4 ] ). There is a deterministic algorithm that, given an integer N ≥ 2 N \ge2 N ≥ 2 , decides whether N N N is prime in time ( log N ) O ( 1 ) (\log N)^{O(1)} ( log N ) O ( 1 ) .
We can therefore find a prime by testing the integers in the interval in increasing order. The next lemma gives the running time and the condition under which it is FPT.
Lemma 2.12. There exists a deterministic algorithm that, given an integer T ≥ 2 T \ge2 T ≥ 2 , finds a prime Q Q Q with T < Q < 2 T T < Q < 2T T < Q < 2 T in time T O ( 1 ) T^{O(1)} T O ( 1 ) . Moreover, let f : Z > 0 → Z > 0 f:\mathbb{Z}_{>0} \to\mathbb{Z}_{>0} f : Z > 0 → Z > 0 be computable and let c ∈ Z > 0 c \in\mathbb{Z}_{>0} c ∈ Z > 0 be fixed. If d , m ∈ Z > 0 d,m \in\mathbb{Z}_{>0} d , m ∈ Z > 0 satisfy T ≤ f ( d ) m c T \le f(d)m^c T ≤ f ( d ) m c , then the algorithm runs in time f 1 ( d ) m O ( 1 ) f_1(d)m^{O(1)} f 1 ( d ) m O ( 1 ) for a computable function f 1 f_1 f 1 depending only on f f f and c c c .
Proof. We find the required prime by testing the integers in the specified interval in increasing order. By Lemma 2.10 , the interval contains a prime. For each candidate, apply Theorem 2.11 , which takes ( log T ) O ( 1 ) (\log T)^{O(1)} ( log T ) O ( 1 ) time. There are fewer than T T T candidates, so the search takes T O ( 1 ) T^{O(1)} T O ( 1 ) time. Substituting T ≤ f ( d ) m c T \le f(d)m^c T ≤ f ( d ) m c gives the stated bound f 1 ( d ) m O ( 1 ) f_1(d)m^{O(1)} f 1 ( d ) m O ( 1 ) .
For prime q q q , an integer lift of a vector or matrix over F q \mathbb{F}_q F q is an integer vector or matrix with the given entries modulo q q q . Reduction modulo q q q is applied entrywise. Finally, we explain how to compute an integer basis for a lattice defined by linear congruences modulo a prime.
Lemma 2.13. Let q q q be prime and let M ∈ F q r × n \mathbf{M} \in\mathbb{F}_q^{r \times n} M ∈ F q r × n . A basis of the lattice
{ v ∈ Z n : M ( v m o d q ) = 0 } \{\mathbf{v} \in\mathbb{Z}^n : \mathbf{M}(\mathbf{v} \bmod q)=0\} { v ∈ Z n : M ( v mod q ) = 0 } can be computed deterministically in time polynomial in r r r , n n n , log q \log q log q .
Proof. Gaussian elimination, followed by a permutation of columns and deletion of zero rows, puts the matrix in the form [ I h C ] [\mathbf{I}_h\ \mathbf{C}] [ I h C ] , where h h h is its rank. In that coordinate order a basis is
( q I h − C ^ 0 I n − h ) \begin{pmatrix}
q\mathbf{I}_h & -\widehat{\mathbf{C}} \\
\mathbf{0} & \mathbf{I}_{n-h}
\end{pmatrix} ( q I h 0 − C I n − h )
where C ^ \widehat{\mathbf{C}} C is the integer lift of C \mathbf{C} C with entries in { 0 , … , q − 1 } \{0,\ldots,q-1\} { 0 , … , q − 1 } . Indeed, the congruence says exactly that v 1 = − C ^ v 2 + q z \mathbf{v}_1=-\widehat{\mathbf{C}}\mathbf{v}_2+q\mathbf{z} v 1 = − C v 2 + q z for an integer vector z \mathbf{z} z . The displayed columns are independent, and undoing the coordinate permutation on every basis vector restores the original coordinate order. The rank-zero case gives I n \mathbf{I}_n I n . All matrix entries have O ( log q ) O(\log q) O ( log q ) bits.
:::
Rational points near a nonsingular solution
This subsection proves Lemma 2.19 , our substitute for the implicit function theorem over finite fields. We know a common zero ξ \xi ξ of polynomials f 1 , … , f n f_1,\ldots,f_n f 1 , … , f n over a finite field at which their Jacobian matrix is invertible, and we need a common zero of f 1 , … , f n − 1 f_1,\ldots,f_{n-1} f 1 , … , f n − 1 at which f n f_n f n does not vanish. Over the real numbers, the implicit function theorem would give a curve through ξ \xi ξ on which f 1 , … , f n − 1 f_1,\ldots,f_{n-1} f 1 , … , f n − 1 stay zero and f n f_n f n is nonzero near ξ \xi ξ except at ξ \xi ξ . Over a finite field, we find such a curve algebraically, show that it is defined over the finite field, and count its points. The subsection assumes no background in algebraic geometry: we define every notion that we use. Besides basic linear algebra and finite fields, we use without proof only Fact 2.14 , Fact 2.15 , Fact 2.17 , Theorem 2.18 , and the Frobenius descent criterion [20 Example 1.4.2, p. 31] , stated in Lemma 2.16 (ii).
Algebraic sets and curves. Throughout this subsection, K = F q K=\mathbb{F}_q K = F q , and K ‾ \overline{K} K is an algebraic closure of K K K ; every z ∈ K ‾ z \in\overline{K} z ∈ K lies in the finite field K ( z ) K(z) K ( z ) . An algebraic set is the set V ( h 1 , … , h s ) V(h_1,\ldots,h_s) V ( h 1 , … , h s ) of common zeros in K ‾ n \overline{K}^n K n of polynomials h 1 , … , h s ∈ K ‾ [ X 1 , … , X n ] h_1,\ldots,h_s \in\overline{K}[X_1,\ldots,X_n] h 1 , … , h s ∈ K [ X 1 , … , X n ] . Finite sets, finite unions, and finite intersections of algebraic sets are algebraic sets; for instance, V ( g ) ∪ V ( h ) = V ( g h ) V(g)\cup V(h)=V(gh) V ( g ) ∪ V ( h ) = V ( g h ) . An algebraic set W W W is defined over K K K if it equals V ( h 1 , … , h s ) V(h_1,\ldots,h_s) V ( h 1 , … , h s ) for some h 1 , … , h s ∈ K [ X 1 , … , X n ] h_1,\ldots,h_s \in K[X_1,\ldots,X_n] h 1 , … , h s ∈ K [ X 1 , … , X n ] , and W ( K ) = W ∩ K n W(K)=W\cap K^n W ( K ) = W ∩ K n is its set of K K K -rational points. An algebraic set is irreducible if it is nonempty and is not the union of two proper algebraic subsets.
Fact 2.14 (see [22 Section 4.1] ). Every nonempty algebraic set V V V is the union of finitely many irreducible algebraic subsets, none of which contains another. These subsets are uniquely determined by V V V , and they are called the irreducible components of V V V .
Every irreducible algebraic subset Z Z Z of V V V lies in some component C i C_i C i , since Z Z Z is irreducible and is the union of the algebraic sets Z ∩ C i Z \cap C_i Z ∩ C i . Hence the components of V V V are exactly its maximal irreducible algebraic subsets. An irreducible algebraic set defined over K K K is called absolutely irreducible over K K K . A curve in an algebraic closure is an infinite algebraic set all of whose proper algebraic subsets are finite;3 a curve is irreducible, since the union of two finite sets is finite. A line is an example of a curve.
Degree. For a curve C C C , the degree is the largest number of points in which C C C meets an affine hyperplane that does not contain C C C . We need only the following properties of the degree of a general algebraic set.
Fact 2.15 (see [CM06, Section 2] and [22 Section 4.1 and Lemma 4.2] ). Every algebraic set V ⊆ K ‾ n V \subseteq\overline{K}^{n} V ⊆ K n has a degree deg V ∈ Z ≥ 0 \deg V \in\mathbb{Z}_{\ge0} deg V ∈ Z ≥ 0 , which for a curve is the number defined above, with the following properties.
(i) The degree of a finite set is its number of points.
(ii) The degree of V V V is the sum of the degrees of its irreducible components.
(iii) For every nonconstant polynomial h h h , we have deg V ( h ) ≤ deg h \deg V(h) \leq\deg h deg V ( h ) ≤ deg h .
(iv) (Bézout’s inequality ) For all algebraic sets V V V and W W W , we have deg ( V ∩ W ) ≤ deg V ⋅ deg W \deg(V \cap W) \leq\deg V \cdot\deg W deg ( V ∩ W ) ≤ deg V ⋅ deg W .
The Frobenius map. The Frobenius map σ ( z ) = z Q \sigma(z) = z^{Q} σ ( z ) = z Q is an automorphism of K ‾ \overline{K} K (it is injective and maps each finite field K ( z ) K(z) K ( z ) into itself), and its fixed points are exactly the Q Q Q roots of Z Q − Z Z^{Q} - Z Z Q − Z , namely the elements of K K K . We apply σ \sigma σ to points coordinatewise, and we write h σ h^{\sigma} h σ for the polynomial obtained by applying σ \sigma σ to the coefficients of h h h . The following lemma recognizes algebraic sets defined over K K K .
Lemma 2.16. (i) We have σ ( V ( h 1 , … , h s ) ) = V ( h 1 σ , … , h s σ ) \sigma(V(h_1,\ldots,h_s)) = V(h_1^{\sigma},\ldots,h_s^{\sigma}) σ ( V ( h 1 , … , h s )) = V ( h 1 σ , … , h s σ ) , and σ \sigma σ maps the irreducible components of every algebraic set W W W onto those of σ ( W ) \sigma(W) σ ( W ) . If W W W is defined over K K K , then σ ( W ) = W \sigma(W) = W σ ( W ) = W .
(ii) Conversely, every algebraic set W W W with σ ( W ) = W \sigma(W) = W σ ( W ) = W is defined over K K K .
Proof. (i) Since σ \sigma σ is a ring automorphism, we have σ ( h ( x ) ) = h σ ( σ ( x ) ) \sigma(h(x)) = h^{\sigma}(\sigma(x)) σ ( h ( x )) = h σ ( σ ( x )) , so h i ( x ) = 0 h_i(x) = 0 h i ( x ) = 0 if and only if h i σ ( σ ( x ) ) = 0 h_i^{\sigma}(\sigma(x)) = 0 h i σ ( σ ( x )) = 0 ; this gives the identity. Hence σ \sigma σ and σ − 1 \sigma^{-1} σ − 1 map algebraic sets to algebraic sets, and σ \sigma σ is a bijection between the algebraic subsets of W W W and those of σ ( W ) \sigma(W) σ ( W ) that preserves unions and inclusions. It therefore maps maximal irreducible algebraic subsets to maximal irreducible algebraic subsets. If h i ∈ K [ X 1 , … , X n ] h_i \in K[X_1,\ldots,X_n] h i ∈ K [ X 1 , … , X n ] , then h i σ = h i h_i^{\sigma} = h_i h i σ = h i , and hence $\sigma(W) = W.
(ii) Since W W W is an algebraic subset of K ‾ n \overline{K}^{n} K n and σ ( W ) = W \sigma(W) = W σ ( W ) = W , we apply [20 Example 1.4.2, p. 31] with k ← K ‾ k \leftarrow\overline{K} k ← K , q ← Q q \leftarrow Q q ← Q , and X ← W X \leftarrow W X ← W to conclude that W W W is defined over K K K . □
Preliminaries
The Jacobian criterion and the Weil bound. Over the real numbers, if polynomials h 1 , … , h r h_1,\ldots,h_r h 1 , … , h r have a common zero b b b at which their Jacobian matrix has rank r r r , the implicit function theorem and the rank theorem (cf. [36 Theorem 9.32] ) show that near b b b their common zero set is a single smooth piece with n − r n-r n − r degrees of freedom. The Jacobian criterion is the algebraic counterpart of this picture; we need the cases of one and zero degrees of freedom.
Fact 2.17 (Jacobian criterion). Let h 1 , … , h r ∈ K ‾ [ X 1 , … , X n ] h_1,\ldots,h_r\in\overline{K}[X_1,\ldots,X_n] h 1 , … , h r ∈ K [ X 1 , … , X n ] , and let b ∈ K ‾ n b\in\overline{K}^{n} b ∈ K n be a common zero of them at which their Jacobian matrix has rank r r r .
(a) If r = n − 1 r=n-1 r = n − 1 , then b b b lies on exactly one irreducible component of V ( h 1 , … , h r ) V(h_1,\ldots,h_r) V ( h 1 , … , h r ) , and this component is a curve.
(b) If r = n r=n r = n , then b b b lies on exactly one irreducible component of V ( h 1 , … , h r ) V(h_1,\ldots,h_r) V ( h 1 , … , h r ) , namely { b } \{b\} { b } .
Fact 2.17 is a standard result in algebraic geometry.4 The Weil bound below says that a curve defined over K K K has about as many K K K -rational points as a line defined over K K K , which has exactly Q Q Q .
Theorem 2.18 (Weil bound; [CM06, Theorem 7.1], case of dimension one; see also [22 Theorem 4.6] ). Let C ⊆ K ‾ n C\subseteq\overline{K}^{n} C ⊆ K n be a curve that is defined over K = F Q K=\mathbb{F}_Q K = F Q , and hence absolutely irreducible over K K K , and let δ \delta δ be its degree in the sense of Fact 2.15. If Q > 4 δ 2 Q>4\delta^2 Q > 4 δ 2 , then
∣ C ( K ) ∣ − Q ≤ ( δ − 1 ) ( δ − 2 ) Q + 5 δ 13 / 3 . \lvert C(K)\rvert-Q\leq(\delta-1)(\delta-2)\sqrt{Q}+5\delta^{13/3}. ∣ C ( K )∣ − Q ≤ ( δ − 1 ) ( δ − 2 ) Q + 5 δ 13/3 .
We now prove the lemma.
Lemma 2.19. Let K = F Q K=\mathbb{F}_Q K = F Q , let n ≥ 2 n\geq2 n ≥ 2 , and let f 1 , … , f n ∈ K [ X 1 , … , X n ] f_1,\ldots,f_n\in K[X_1,\ldots,X_n] f 1 , … , f n ∈ K [ X 1 , … , X n ] be nonconstant polynomials with Δ = ∏ i = 1 n − 1 deg f i \Delta=\prod_{i=1}^{n-1}\deg f_i Δ = ∏ i = 1 n − 1 deg f i . Suppose that ξ ∈ K n \xi\in K^n ξ ∈ K n satisfies
f 1 ( ξ ) = ⋯ = f n ( ξ ) = 0 f_1(\xi)=\cdots=f_n(\xi)=0 f 1 ( ξ ) = ⋯ = f n ( ξ ) = 0 and that the Jacobian matrix of f 1 , … , f n f_1,\ldots,f_n f 1 , … , f n at ξ \xi ξ is invertible. If Q > 9 Δ 5 Q>9\Delta^5 Q > 9 Δ 5 and Q > 9 Δ deg f n Q>9\Delta\deg f_n Q > 9Δ deg f n , then there exists x ∈ K n x\in K^n x ∈ K n such that
f 1 ( x ) = ⋯ = f n − 1 ( x ) = 0 , f n ( x ) ≠ 0. f_1(x)=\cdots=f_{n-1}(x)=0,\qquad f_n(x)\ne0. f 1 ( x ) = ⋯ = f n − 1 ( x ) = 0 , f n ( x ) = 0.
Proof. Let V = V ( f 1 , … , f n − 1 ) V=V(f_1,\ldots,f_{n-1}) V = V ( f 1 , … , f n − 1 ) . We will find a curve C ⊆ V C\subseteq V C ⊆ V defined over K K K and show that C C C has more K K K -rational points than zeros of f n f_n f n .
Step 1: a curve through $\xi. The first n − 1 n-1 n − 1 rows of the invertible Jacobian matrix at ξ \xi ξ are linearly independent, and they form the Jacobian matrix of f 1 , … , f n − 1 f_1,\ldots,f_{n-1} f 1 , … , f n − 1 . By Fact 2.17(a), the point ξ \xi ξ lies on exactly one irreducible component C C C of V V V , and C C C is a curve.
Step 2: the curve C C C is defined over $K. Since V V V is defined over K K K , Lemma 2.16(i) shows that σ ( C ) \sigma(C) σ ( C ) is an irreducible component of σ ( V ) \sigma(V) σ ( V ) , which is exactly V V V . It contains σ ( ξ ) = ξ \sigma(\xi)=\xi σ ( ξ ) = ξ , since ξ ∈ K n \xi\in K^n ξ ∈ K n , so σ ( C ) = C \sigma(C)=C σ ( C ) = C because the point ξ \xi ξ lies on exactly one irreducible component. By Lemma 2.16(ii), the curve C C C is defined over K K K .5 Step 3: the polynomial f n f_n f n has few zeros on C C C . By Fact 2.17 (b), applied to all n n n polynomials, the only irreducible component of V ( f 1 , … , f n ) V(f_1,\ldots,f_n) V ( f 1 , … , f n ) containing ξ \xi ξ is { ξ } \{\xi\} { ξ } . If f n f_n f n vanished on all of C C C , then C C C would be an irreducible algebraic subset of V ( f 1 , … , f n ) V(f_1,\ldots,f_n) V ( f 1 , … , f n ) containing ξ \xi ξ , so C ⊆ { ξ } C \subseteq\{\xi\} C ⊆ { ξ } , which is impossible because C C C is infinite. Hence C ∩ V ( f n ) C \cap V(f_n) C ∩ V ( f n ) is a proper algebraic subset of C C C , and thus finite. Let δ = deg C \delta= \deg C δ = deg C . By Fact 2.15 (i), (iv), and (iii), the set C ∩ V ( f n ) C \cap V(f_n) C ∩ V ( f n ) has at most deg C ⋅ deg V ( f n ) ≤ δ deg f n \deg C \cdot\deg V(f_n) \leq\delta\deg f_n deg C ⋅ deg V ( f n ) ≤ δ deg f n points. Similarly, by (iv) and (iii), the set V = V ( f 1 ) ∩ ⋯ ∩ V ( f n − 1 ) \mathcal{V} = V(f_1) \cap\cdots\cap V(f_{n-1}) V = V ( f 1 ) ∩ ⋯ ∩ V ( f n − 1 ) has degree at most Δ \Delta Δ , and by (ii), so does its component C C C ; that is, δ ≤ Δ \delta\leq\Delta δ ≤ Δ . Since ξ ∈ C ∩ V ( f n ) \xi\in C \cap V(f_n) ξ ∈ C ∩ V ( f n ) , we also have 1 ≤ δ deg f n 1 \leq\delta\deg f_n 1 ≤ δ deg f n , so δ ≥ 1 \delta\geq1 δ ≥ 1 .
Step 4: the curve C C C has many points in K n K^n K n . Since 1 ≤ δ ≤ Δ 1 \leq\delta\leq\Delta 1 ≤ δ ≤ Δ , we have Q > 9 Δ 5 ≥ 4 δ 2 Q > 9\Delta^5 \geq4\delta^2 Q > 9 Δ 5 ≥ 4 δ 2 , ( δ − 1 ) ( δ − 2 ) ≤ Δ 2 (\delta- 1)(\delta- 2) \leq\Delta^2 ( δ − 1 ) ( δ − 2 ) ≤ Δ 2 , and δ 13 / 3 ≤ Δ 5 \delta^{13/3} \leq\Delta^5 δ 13/3 ≤ Δ 5 . By Step 2, Theorem 2.18 applies to C C C and gives
∣ C ( K ) ∣ ≥ Q − Δ 2 Q − 5 Δ 5 > Q − Q 3 − 5 Q 9 = Q 9 > Δ deg f n . |C(K)| \geq Q - \Delta^2\sqrt{Q} - 5\Delta^5 > Q - \frac{Q}{3} - \frac{5Q}{9} = \frac{Q}{9} > \Delta\deg f_n. ∣ C ( K ) ∣ ≥ Q − Δ 2 Q − 5 Δ 5 > Q − 3 Q − 9 5 Q = 9 Q > Δ deg f n .
where we used Q > 3 Δ 2 \sqrt{Q} > 3\Delta^2 Q > 3 Δ 2 and 5 Δ 5 < 5 Q / 9 5\Delta^5 < 5Q/9 5 Δ 5 < 5 Q /9 , which follow from Q > 9 Δ 5 Q > 9\Delta^5 Q > 9 Δ 5 , and the assumption Q > 9 Δ deg f n Q > 9\Delta\deg f_n Q > 9Δ deg f n . By Step 3, some x ∈ C ( K ) x \in C(K) x ∈ C ( K ) is not a zero of f n f_n f n , and f 1 ( x ) = ⋯ = f n − 1 ( x ) = 0 f_1(x) = \cdots= f_{n-1}(x) = 0 f 1 ( x ) = ⋯ = f n − 1 ( x ) = 0 because C ⊆ V C \subseteq\mathcal{V} C ⊆ V .
A Deterministic Reduction from CVP to SVP
We prove Theorem 1.1 by constructing a deterministic reduction from CVP to SVP. We observe that the reduction of Hirahara and Ogitsuka [23 ] becomes deterministic if we can deterministically construct a locally dense lattice, as defined below, in FPT time. Our construction uses the Reed–Solomon lattice of Bennett and Peikert [8 ] .
Definition 3.1 (Locally dense lattice). Let p ≥ 1 p \geq1 p ≥ 1 , let m , d , D , W m, d, D, W m , d , D , W be positive integers, and let q q q be prime. Let H ∈ F q r × N \mathbf{H} \in\mathbb{F}_q^{r \times N} H ∈ F q r × N , let s ∈ Z N \mathbf{s} \in\mathbb{Z}^N s ∈ Z N , and let S S S be an ordered list of m m m distinct coordinates. Put
L = { v ∈ Z N : H ( v m o d q ) = 0 } . L = \{v \in\mathbb{Z}^N : \mathbf{H}(v \bmod q) = 0\}. L = { v ∈ Z N : H ( v mod q ) = 0 } . The tuple ( q , H , s , S ) (q, \mathbf{H}, \mathbf{s}, S) ( q , H , s , S ) is a locally dense lattice with parameters ( p , m , d , D , W ) (p,m,d,D,W) ( p , m , d , D , W ) if
(i) λ 1 ( p ) ( L ) > D \lambda_1^{(p)}(L) > D λ 1 ( p ) ( L ) > D ;
(ii) s ∣ S = 0 \mathbf{s}|_S = 0 s ∣ S = 0 ;
(iii) for every u ∈ Z m u \in\mathbb{Z}^m u ∈ Z m with ∥ u ∥ p ≤ d \lVert u \rVert_p \leq d ∥ u ∥ p ≤ d , there exists w ∈ L − s w \in L - \mathbf{s} w ∈ L − s such that
w ∣ S = u , ∥ w ∥ p p ≤ W . w|_S = u, \qquad\lVert w \rVert_p^p \leq W. w ∣ S = u , ∥ w ∥ p p ≤ W . Here W W W bounds the p p p th power of the norm, while d d d and D D D are norm thresholds. The equality w ∣ S = u w|_S = u w ∣ S = u in condition (iii) is over the integers. Since L L L contains q q q times every unit vector, condition (i) implies q > D q > D q > D .
A Non-Uniform Reduction Using a Locally Dense Lattice
The following reduction is essentially based on the observation that the reduction of Hirahara and Ogitsuka gives a non-uniform reduction when a locally dense lattice is provided as advice. For fixed constants of the reduction, the same locally dense lattice can be used for all instances with the same m m m and d d d .
Theorem 3.2 ([23 proof of Theorem 3.9 in the full version, adapted] ). Fix p ≥ 1 p \ge1 p ≥ 1 , γ ′ ≥ 1 \gamma' \ge1 γ ′ ≥ 1 , and integers γ ≥ 2 \gamma\ge2 γ ≥ 2 , c ≥ 1 c \ge1 c ≥ 1 with γ c < γ \gamma^c < \gamma γ c < γ . There is a deterministic algorithm that, given an instance ( B , t , d ) (\mathbf{B},t,d) ( B , t , d ) of γ \gamma γ -GapCVPp _p p with B ∈ Z m × n \mathbf{B} \in\mathbb{Z}^{m \times n} B ∈ Z m × n and a locally dense lattice ( q , H , s , S ) (q,\mathbf{H},s,S) ( q , H , s , S ) with parameters ( p , m , d , γ d , W ) (p,m,d,\gamma d,W) ( p , m , d , γ d , W ) satisfying
d p + W + 1 ≤ ( c d ) p , (4) d^p + W + 1 \le(cd)^p, \tag*{(4)} d p + W + 1 ≤ ( c d ) p , (4) outputs an instance of γ ′ \gamma' γ ′ -GapSVPp _p p with parameter d ′ = c d d' = cd d ′ = c d , preserving both YES and NO instances. Its running time is polynomial in the total input length, including the representation of the supplied locally dense lattice.
Proof. We first construct the output instance. Set D = γ d D = \gamma d D = γ d and β = D + 1 \beta= D + 1 β = D + 1 . Use Lemma 2.13 to compute an integer basis A ∈ Z N × N \mathbf{A} \in\mathbb{Z}^{N \times N} A ∈ Z N × N of the lattice L L L represented by q q q and H \mathbf{H} H . Let A S \mathbf{A}_S A S consist of the rows of A \mathbf{A} A indexed by S S S , in the specified order. Output ( B ′ , d ′ ) (\mathbf{B}',d') ( B ′ , d ′ ) , where
B ′ = ( B 0 − t 0 A − s 0 0 1 β B − β A S − β t ) , d ′ = c d . (5) \mathbf{B}' =
\begin{pmatrix}
\mathbf{B} & 0 & -t \\
0 & \mathbf{A} & -s \\
0 & 0 & 1 \\
\beta\mathbf{B} & -\beta\mathbf{A}_S & -\beta t
\end{pmatrix},
\qquad d' = cd. \tag*{(5)} B ′ = B 0 0 β B 0 A 0 − β A S − t − s 1 − β t , d ′ = c d . (5) Compared with [23 ] , we omit the columns β q I m \beta q\mathbf{I}_m β q I m , since the local density condition in Definition 3.1 holds as an equality over the integers.
We show that the columns of B ′ \mathbf{B}' B ′ are linearly independent, so that B ′ \mathbf{B}' B ′ is a lattice basis. Consider a linear combination of its columns that is zero. The third block forces the coefficient of the column containing − t -t − t and − s -s − s to be zero. Since B \mathbf{B} B and A \mathbf{A} A have linearly independent columns, the first two blocks then force the coefficients of their columns to be zero.
Next, we show completeness. Suppose that ∥ B x − t ∥ p ≤ d \lVert\mathbf{B}x-t\rVert_p \le d ∥ B x − t ∥ p ≤ d for some x ∈ Z n x \in\mathbb{Z}^n x ∈ Z n . Since L ( A ) = L \mathcal{L}(\mathbf{A}) = L L ( A ) = L , the local density condition in Definition 3.1 gives y ∈ Z N y \in\mathbb{Z}^N y ∈ Z N such that
∥ A y − s ∥ p p ≤ W , ( A y − s ) ∣ S = B x − t . \lVert\mathbf{A}y-s\rVert_p^p \le W,\qquad(\mathbf{A}y-s)|_S = \mathbf{B}x-t. ∥ A y − s ∥ p p ≤ W , ( A y − s ) ∣ S = B x − t . Since s ∣ S = 0 s|_S = 0 s ∣ S = 0 , the last equality gives A S y = B x − t \mathbf{A}_S y = \mathbf{B}x-t A S y = B x − t . Therefore,
B ′ ( x y 1 ) = ( B x − t A y − s 1 0 ) . \mathbf{B}'
\begin{pmatrix}
x\\
y\\
1
\end{pmatrix}
=
\begin{pmatrix}
\mathbf{B}x-t\\
\mathbf{A}y-s\\
1\\
0
\end{pmatrix}. B ′ x y 1 = B x − t A y − s 1 0 . This vector is nonzero because its third block is 1 1 1 . By Equation (4) , the p p p th power of its norm satisfies
∥ B x − t ∥ p p + ∥ A y − s ∥ p p + 1 ≤ d p + W + 1 ≤ ( c d ) p . \lVert\mathbf{B}x-t\rVert_p^p+\lVert\mathbf{A}y-s\rVert_p^p+1 \le d^p+W+1 \le(cd)^p. ∥ B x − t ∥ p p + ∥ A y − s ∥ p p + 1 ≤ d p + W + 1 ≤ ( c d ) p . Thus the output is a YES instance with parameter d ′ = c d d' = cd d ′ = c d .
We now show soundness. Suppose that ( B , t , d ) (\mathbf{B},t,d) ( B , t , d ) is a NO instance. By Definition 2.3 , this means that
dist p ( L ( B ) , ℓ t ) > D ( ℓ ∈ Z ∖ { 0 } ) . \operatorname{dist}_p(\mathcal{L}(\mathbf{B}),\ell t) > D \qquad(\ell\in\mathbb{Z} \setminus\{0\}). dist p ( L ( B ) , ℓ t ) > D ( ℓ ∈ Z ∖ { 0 }) . Assume for contradiction that L ( B ′ ) \mathcal{L}(\mathbf{B}') L ( B ′ ) contains a nonzero vector of norm at most D D D . Using s ∣ S = 0 s|_S = 0 s ∣ S = 0 , we can write this vector as
( B x − ℓ t A y − ℓ s ℓ β ( B x − ℓ t − ( A y − ℓ s ) ∣ S ) ) \begin{pmatrix}
\mathbf{B}x-\ell t\\
\mathbf{A}y-\ell s\\
\ell\\
\beta\bigl(\mathbf{B}x-\ell t-(\mathbf{A}y-\ell s)|_S\bigr)
\end{pmatrix} B x − ℓ t A y − ℓ s ℓ β ( B x − ℓ t − ( A y − ℓ s ) ∣ S )
for some x ∈ Z n x \in\mathbb{Z}^{n} x ∈ Z n , y ∈ Z N y \in\mathbb{Z}^{N} y ∈ Z N , and ℓ ∈ Z \ell\in\mathbb{Z} ℓ ∈ Z . If ℓ ≠ 0 \ell\ne0 ℓ = 0 , the first block has norm
∥ B x − ℓ t ∥ p ≥ dist p ( L ( B ) , ℓ t ) > D . \lVert\mathbf{B}x-\ell t\rVert_{p} \ge\operatorname{dist}_{p}(\mathcal{L}(\mathbf{B}),\ell t)>D. ∥ B x − ℓ t ∥ p ≥ dist p ( L ( B ) , ℓ t ) > D .
This contradicts the assumed norm bound, so ℓ = 0 \ell=0 ℓ = 0 .
The case ℓ = 0 \ell=0 ℓ = 0 also leads to a contradiction. The second block is now A y ∈ L \mathbf{A}y \in L A y ∈ L and has norm at most D D D . Since λ 1 ( p ) ( L ) > D \lambda_{1}^{(p)}(L)>D λ 1 ( p ) ( L ) > D , we must have A y = 0 \mathbf{A}y=0 A y = 0 . The last block is therefore β B x \beta\mathbf{B}x β B x , and every coordinate in it is an integer multiple of β > D \beta>D β > D . The assumed norm bound therefore forces that block to be zero, so B x = 0 \mathbf{B}x=0 B x = 0 . All blocks are now zero, contrary to the choice of a nonzero vector. Therefore,
λ 1 ( p ) ( L ( B ′ ) ) > D = γ d > γ ′ c d . \lambda_{1}^{(p)}(\mathcal{L}(\mathbf{B}'))>D=\gamma d>\gamma'cd. λ 1 ( p ) ( L ( B ′ )) > D = γ d > γ ′ c d .
We finally bound the running time. The matrix B ′ \mathbf{B}' B ′ has N + 2 m + 1 N+2m+1 N + 2 m + 1 rows and n + N + 1 n+N+1 n + N + 1 columns. By Lemma 2.13 , computing A \mathbf{A} A takes time polynomial in the dimensions of H \mathbf{H} H and log q \log q log q . Forming B ′ \mathbf{B}' B ′ also takes time polynomial in the total input length, and the bit lengths of all its entries are polynomial in that length. Thus the reduction has the claimed running time. □
A Deterministic FPT Construction of Locally Dense Lattices
In this section, we give a deterministic FPT algorithm that constructs a locally dense lattice as defined in Definition 3.1 . Our construction uses a Reed–Solomon lattice. We use the following lower bound on its minimum norm to verify condition (i) of Definition 3.1 . The proof of the minimum distance in [8 Theorem 3.1 in the full version] applies without change to extension fields under the characteristic assumption below. We include the proof for completeness.
Lemma 3.3 ([8 Theorem 3.1 in the full version, adapted] ). Let k ≥ 2 k \ge2 k ≥ 2 be an integer, let q > 2 k q>2k q > 2 k be prime, and let Q = q s Q=q^{s} Q = q s for an integer s ≥ 1 s \ge1 s ≥ 1 . The lattice
L Q , k = { v ∈ Z F Q : ∑ z ∈ F Q v z z j = 0 in F Q ( 0 ≤ j < k ) } (6) L_{Q,k}=\left\{v\in\mathbb{Z}^{\mathbb{F}_{Q}}:\sum_{z\in\mathbb{F}_{Q}}v_z z^j=0\text{ in }\mathbb{F}_{Q}\quad(0\le j<k)\right\} \tag*{(6)} L Q , k = ⎩ ⎨ ⎧ v ∈ Z F Q : z ∈ F Q ∑ v z z j = 0 in F Q ( 0 ≤ j < k ) ⎭ ⎬ ⎫ (6) satisfies
λ 1 ( p ) ( L Q , k ) ≥ ( 2 k ) 1 / p , λ ( L Q , k mod q ) ≥ k + 1 \lambda_{1}^{(p)}(L_{Q,k})\ge(2k)^{1/p},\qquad\lambda(L_{Q,k}\mathbin{\operatorname{mod}}q)\ge k+1 λ 1 ( p ) ( L Q , k ) ≥ ( 2 k ) 1/ p , λ ( L Q , k mod q ) ≥ k + 1 for every real p ≥ 1 p\ge1 p ≥ 1 . The integer coefficients are interpreted in F q ⊆ F Q \mathbb{F}_{q}\subseteq\mathbb{F}_{Q} F q ⊆ F Q . The equation for j = 0 j=0 j = 0 uses z 0 = 1 z^{0}=1 z 0 = 1 for every z ∈ F Q z\in\mathbb{F}_{Q} z ∈ F Q .
Proof. We first bound the minimum ℓ 1 \ell_{1} ℓ 1 norm. Suppose that 0 ≠ v ∈ L Q , k 0\ne v\in L_{Q,k} 0 = v ∈ L Q , k satisfies ∥ v ∥ 1 < 2 k \lVert v\rVert_{1}<2k ∥ v ∥ 1 < 2 k . The equation for j = 0 j=0 j = 0 gives ∑ z v z ≡ 0 ( m o d q ) \sum_{z}v_z\equiv0\pmod q ∑ z v z ≡ 0 ( mod q ) . Since ∣ ∑ z v z ∣ ≤ ∥ v ∥ 1 < 2 k < q \left|\sum_{z}v_z\right|\le\lVert v\rVert_{1}<2k<q ∣ ∑ z v z ∣ ≤ ∥ v ∥ 1 < 2 k < q , we have ∑ z v z = 0 \sum_{z}v_z=0 ∑ z v z = 0 over the integers. Form two multisets of elements of F Q \mathbb{F}_{Q} F Q : for each positive entry v z v_z v z , put v z v_z v z copies of z z z in the first multiset, and for each negative entry v z v_z v z , put − v z -v_z − v z copies of z z z in the second. Their cardinalities are equal, say to h h h , and 2 h = ∥ v ∥ 1 < 2 k 2h=\lVert v\rVert_{1}<2k 2 h = ∥ v ∥ 1 < 2 k . The case h = 0 h=0 h = 0 would give v = 0 v=0 v = 0 , so 1 ≤ h < k 1\le h<k 1 ≤ h < k .
The equations for j = 1 , … , h j=1,\ldots,h j = 1 , … , h in Equation (6) say that these multisets have equal power sums through degree h h h . Since the characteristic q q q exceeds h h h , Newton’s identities recover their elementary symmetric functions from these power sums. The monic polynomials having the elements of the two multisets as roots, counted with multiplicity, are therefore equal. Unique factorization in F Q [ X ] \mathbb{F}_{Q}[X] F Q [ X ] implies that the two multisets are equal. This is impossible because the positive and negative
supports of v v v are disjoint and h ≥ 1 h \ge1 h ≥ 1 . Thus λ 1 ( 1 ) ( L Q , k ) ≥ 2 k \lambda_1^{(1)}(L_{Q,k}) \ge2k λ 1 ( 1 ) ( L Q , k ) ≥ 2 k . For every integer vector v v v and every real p ≥ 1 p \ge1 p ≥ 1 , we have ∥ v ∥ p p ≥ ∥ v ∥ 1 \lVert v\rVert_p^p \ge\lVert v\rVert_1 ∥ v ∥ p p ≥ ∥ v ∥ 1 . This gives λ 1 ( p ) ( L Q , k ) ≥ ( 2 k ) 1 / p \lambda_1^{(p)}(L_{Q,k}) \ge(2k)^{1/p} λ 1 ( p ) ( L Q , k ) ≥ ( 2 k ) 1/ p .
Next, suppose that a nonzero word of L Q , k L_{Q,k} L Q , k mod q q q has support { z 1 , … , z h } \{z_1,\ldots,z_h\} { z 1 , … , z h } of size h ≤ k h \le k h ≤ k . The first h h h equations in Equation (6) have coefficient matrix
( z i j ) 0 ≤ j < h , 1 ≤ i ≤ h . (z_i^j)_{0 \le j < h,\ 1 \le i \le h}. ( z i j ) 0 ≤ j < h , 1 ≤ i ≤ h .
This Vandermonde matrix is invertible over F Q \mathbb{F}_Q F Q because the z i z_i z i are distinct. All coefficients on the support must therefore be zero, a contradiction. This proves λ ( L Q , k m o d q ) ≥ k + 1 \lambda(L_{Q,k}\bmod q) \ge k+1 λ ( L Q , k mod q ) ≥ k + 1 .
Taking s = 1 s=1 s = 1 gives the lattice L q , k L_{q,k} L q , k over the prime field F q \mathbb{F}_q F q .
We now choose the shift s s s and the coordinates S S S so that the Reed–Solomon lattice satisfies the local density condition. The following theorem gives a deterministic construction for the integer parameters specified below.
Theorem 3.4. Fix p ≥ 1 p \ge1 p ≥ 1 . Let m , d , D , h , k m,d,D,h,k m , d , D , h , k be positive integers satisfying
D ≥ 2 , k ≥ 2 , d p ≤ h , D p < 2 k , (7) D \ge2,\qquad k \ge2,\qquad d^p \le h,\qquad D^p < 2k, \tag*{(7)} D ≥ 2 , k ≥ 2 , d p ≤ h , D p < 2 k , (7) and put W = k − 1 + 2 h W=k-1+2h W = k − 1 + 2 h . There is a deterministic algorithm that, on input ( m , d , D , h , k ) (m,d,D,h,k) ( m , d , D , h , k ) , constructs a locally dense lattice ( q , H , s , S ) (q,\mathbf{H},s,S) ( q , H , s , S ) with parameters ( p , m , d , D , W ) (p,m,d,D,W) ( p , m , d , D , W ) . The algorithm outputs the prime q q q , the matrix H \mathbf{H} H , the vector s s s , and the coordinates in S S S . Its running time and output size are bounded by f ( d + D + h + k ) ( m + 1 ) O ( 1 ) f(d+D+h+k)(m+1)^{O(1)} f ( d + D + h + k ) ( m + 1 ) O ( 1 ) for a computable function f f f , with an exponent independent of d , D , h , k d,D,h,k d , D , h , k .
Proof. We first choose the prime field that indexes the coordinates of the lattice. Put L = k − 1 L=k-1 L = k − 1 and use Lemma 2.12 to choose a prime q q q with T < q < 2 T T<q<2T T < q < 2 T , where
T = 1 + max { 2 k , D , m + L , 9 ( L ! ) 5 , 9 L ! ( 1 + ( L + h ) m + L h + ( L 2 ) ) } . (8) T=1+\max\left\{2k,D,m+L,9(L!)^5,9L!\left(1+(L+h)m+Lh+\binom{L}{2}\right)\right\}. \tag*{(8)} T = 1 + max { 2 k , D , m + L , 9 ( L ! ) 5 , 9 L ! ( 1 + ( L + h ) m + L h + ( 2 L ) ) } . (8)
For z ∈ F q z\in\mathbb{F}_q z ∈ F q , let e z ∈ Z F q e_z\in\mathbb{Z}^{\mathbb{F}_q} e z ∈ Z F q have entry 1 at z z z and entry 0 at every other coordinate.
We next construct the matrix H \mathbf{H} H , the vector s s s , and the ordered list of coordinates S S S . Index the coordinates by F q \mathbb{F}_q F q and define H = ( z j ) 0 ≤ j < k , z ∈ F q \mathbf{H}=(z^j)_{0\le j<k,\ z\in\mathbb{F}_q} H = ( z j ) 0 ≤ j < k , z ∈ F q , with z 0 = 1 z^0=1 z 0 = 1 for every z z z . Then { v ∈ Z F q : H ( v m o d q ) = 0 } \{v\in\mathbb{Z}^{\mathbb{F}_q}:\mathbf{H}(v\bmod q)=0\} { v ∈ Z F q : H ( v mod q ) = 0 } is the lattice L q , k L_{q,k} L q , k in Equation (6) . Since q > m + L q>m+L q > m + L , we can choose distinct elements y 1 , … , y L , x 1 , … , x m ∈ F q y_1,\ldots,y_L,x_1,\ldots,x_m\in\mathbb{F}_q y 1 , … , y L , x 1 , … , x m ∈ F q using a fixed enumeration of F q \mathbb{F}_q F q . Set
s = − ∑ ℓ = 1 L e y ℓ , S = ( x 1 , … , x m ) . s=-\sum_{\ell=1}^{L}e_{y_\ell},\qquad S=(x_1,\ldots,x_m). s = − ℓ = 1 ∑ L e y ℓ , S = ( x 1 , … , x m ) .
Thus s ∣ S = 0 s|_S=0 s ∣ S = 0 . The algorithm outputs ( q , H , s , S ) (q,\mathbf{H},s,S) ( q , H , s , S ) . When considering membership in S S S , we identify S S S with its underlying set { x 1 , … , x m } \{x_1,\ldots,x_m\} { x 1 , … , x m } .
We first verify the minimum distance condition in Definition 3.1 .
Claim 1. The lattice L q , k L_{q,k} L q , k satisfies λ 1 ( p ) ( L q , k ) > D \lambda_1^{(p)}(L_{q,k})>D λ 1 ( p ) ( L q , k ) > D .
Proof of Claim 1. We apply Lemma 3.3 with Q = q Q=q Q = q to bound the minimum norm. Its hypotheses hold because k ≥ 2 k\ge2 k ≥ 2 and q > 2 k q>2k q > 2 k . Together with D p < 2 k D^p<2k D p < 2 k , it gives λ 1 ( p ) ( L q , k ) ≥ ( 2 k ) 1 / p > D \lambda_1^{(p)}(L_{q,k})\ge(2k)^{1/p}>D λ 1 ( p ) ( L q , k ) ≥ ( 2 k ) 1/ p > D .
We now construct, for each u ∈ Z m u \in\mathbb{Z}^m u ∈ Z m with ∥ u ∥ p ≤ d \lVert u\rVert_p \le d ∥ u ∥ p ≤ d , a vector w ∈ L q , k − s w \in L_{q,k}-s w ∈ L q , k − s satisfying
w ∣ S = u , ∥ w ∥ p p ≤ W , w|_S=u,\qquad\lVert w\rVert_p^p \le W, w ∣ S = u , ∥ w ∥ p p ≤ W ,
as required by condition (iii) of Definition 3.1 . If u = 0 u=0 u = 0 , choose w = − s w=-s w = − s . Then w + s = 0 ∈ L q , k w+s=0\in L_{q,k} w + s = 0 ∈ L q , k , w ∣ S = 0 w|_S=0 w ∣ S = 0 , and ∥ w ∥ p p = L ≤ W \lVert w\rVert_p^p=L\le W ∥ w ∥ p p = L ≤ W . For the rest of the proof, fix u ≠ 0 u\ne0 u = 0 and put I = { i ∈ [ m ] : u i ≠ 0 } I=\{i\in[m]:u_i\ne0\} I = { i ∈ [ m ] : u i = 0 } . Since the entries of u u u are integers, every nonzero entry satisfies ∣ u i ∣ p ≥ 1 |u_i|^p\ge1 ∣ u i ∣ p ≥ 1 , so
1 ≤ ∣ I ∣ ≤ ∑ i = 1 m ∣ u i ∣ p ≤ d p ≤ h . 1\le|I|\le\sum_{i=1}^{m}|u_i|^p\le d^p\le h. 1 ≤ ∣ I ∣ ≤ i = 1 ∑ m ∣ u i ∣ p ≤ d p ≤ h .
For any z 1 , … , z L , τ ∈ F q z_1,\ldots,z_L,\tau\in\mathbb{F}_q z 1 , … , z L , τ ∈ F q , define
w = ∑ ℓ = 1 L e z ℓ + ∑ i ∈ I u i ( e x i − e x i + τ ) ∈ Z F q . (9) w=\sum_{\ell=1}^{L}e_{z_\ell}+\sum_{i\in I}u_i(e_{x_i}-e_{x_i+\tau})\in\mathbb{Z}^{\mathbb{F}_q}. \tag*{(9)} w = ℓ = 1 ∑ L e z ℓ + i ∈ I ∑ u i ( e x i − e x i + τ ) ∈ Z F q . (9)
The additions in the coordinate indices are taken in F q \mathbb{F}_q F q , while the coefficients of w w w are integers. We obtain the required norm bound whenever the coordinate indices in Equation (9) are pairwise distinct. If the elements in the list z 1 , … , z L , ( x i ) i ∈ I , ( x i + τ ) i ∈ I z_1,\ldots,z_L,(x_i)_{i\in I},(x_i+\tau)_{i\in I} z 1 , … , z L , ( x i ) i ∈ I , ( x i + τ ) i ∈ I are pairwise distinct, then the nonzero entries of w w w are L L L copies of 1 1 1 and one copy each of u i u_i u i and − u i -u_i − u i for every i ∈ I i\in I i ∈ I . Hence
∥ w ∥ p p = L + 2 ∑ i ∈ I ∣ u i ∣ p ≤ k − 1 + 2 h = W . \lVert w\rVert_p^p=L+2\sum_{i\in I}|u_i|^p\le k-1+2h=W. ∥ w ∥ p p = L + 2 i ∈ I ∑ ∣ u i ∣ p ≤ k − 1 + 2 h = W .
We derive the equations equivalent to w ∈ L q , k − s w\in L_{q,k}-s w ∈ L q , k − s . By Equation (6) , the condition for j = 0 j=0 j = 0 is
∑ z ∈ F q ( w z + s z ) = 0 ( m o d q ) . \sum_{z\in\mathbb{F}_q}(w_z+s_z)=0\pmod q. z ∈ F q ∑ ( w z + s z ) = 0 ( mod q ) .
This condition holds for every choice of z 1 , … , z L , τ ∈ F q z_1,\ldots,z_L,\tau\in\mathbb{F}_q z 1 , … , z L , τ ∈ F q , since
∑ z ∈ F q ( w z + s z ) = ∑ ℓ = 1 L ( 1 − 1 ) + ∑ i ∈ I u i ( 1 − 1 ) = 0 \sum_{z\in\mathbb{F}_q}(w_z+s_z)=\sum_{\ell=1}^{L}(1-1)+\sum_{i\in I}u_i(1-1)=0 z ∈ F q ∑ ( w z + s z ) = ℓ = 1 ∑ L ( 1 − 1 ) + i ∈ I ∑ u i ( 1 − 1 ) = 0
over the integers. By Equation (6) , the remaining conditions are
∑ z ∈ F q ( w z + s z ) z j = 0 ( m o d q ) ( 1 ≤ j ≤ L ) . \sum_{z\in\mathbb{F}_q}(w_z+s_z)z^j=0\pmod q\qquad(1\le j\le L). z ∈ F q ∑ ( w z + s z ) z j = 0 ( mod q ) ( 1 ≤ j ≤ L ) .
We interpret the integer coefficients in F q \mathbb{F}_q F q when evaluating these sums. For each 1 ≤ j ≤ L 1\le j\le L 1 ≤ j ≤ L and ℓ ∈ [ L ] \ell\in[L] ℓ ∈ [ L ] , we have
∑ z ∈ F q ( e z ℓ ) z z j = z ℓ j , \sum_{z\in\mathbb{F}_q}(e_{z_\ell})_z z^j=z_\ell^j, z ∈ F q ∑ ( e z ℓ ) z z j = z ℓ j ,
since e z ℓ e_{z_\ell} e z ℓ has entry 1 1 1 at z ℓ z_\ell z ℓ and entry 0 0 0 at every other coordinate. Applying the same calculation to each term of w + s w+s w + s gives
∑ z ∈ F q ( w z + s z ) z j = ∑ ℓ = 1 L ( z ℓ j − y ℓ j ) + ∑ i ∈ I u i ( x i j − ( x i + τ ) j ) = ∑ ℓ = 1 L ( z ℓ j − y ℓ j ) − ∑ i ∈ I u i ( ( x i + τ ) j − x i j ) . \begin{aligned}
\sum_{z\in\mathbb{F}_q}(w_z+s_z)z^j
=\sum_{\ell=1}^{L}(z_\ell^j-y_\ell^j)+\sum_{i\in I}u_i\left(x_i^j-(x_i+\tau)^j\right) \\
&=\sum_{\ell=1}^{L}(z_\ell^j-y_\ell^j)-\sum_{i\in I}u_i\left((x_i+\tau)^j-x_i^j\right).
\end{aligned} z ∈ F q ∑ ( w z + s z ) z j = ℓ = 1 ∑ L ( z ℓ j − y ℓ j ) + i ∈ I ∑ u i ( x i j − ( x i + τ ) j ) = ℓ = 1 ∑ L ( z ℓ j − y ℓ j ) − i ∈ I ∑ u i ( ( x i + τ ) j − x i j ) .
Let Z 1 , … , Z L , Y Z_1,\ldots,Z_L,Y Z 1 , … , Z L , Y be variables over F q \mathbb{F}_q F q . Therefore, w + s ∈ L q , k \mathbf{w}+\mathbf{s}\in L_{q,k} w + s ∈ L q , k if and only if ( z 1 , … , z L , τ ) (z_1,\ldots,z_L,\tau) ( z 1 , … , z L , τ ) satisfies
∑ ℓ = 1 L ( Z ℓ j − y ℓ j ) − ∑ i ∈ I u i ( ( x i + Y ) j − x i j ) = 0 ( 1 ≤ j ≤ L ) , (10) \sum_{\ell=1}^{L}(Z_{\ell}^{j}-y_{\ell}^{j})-\sum_{i\in I}u_i\left((x_i+Y)^j-x_i^j\right)=0 \qquad(1\le j\le L), \tag*{(10)} ℓ = 1 ∑ L ( Z ℓ j − y ℓ j ) − i ∈ I ∑ u i ( ( x i + Y ) j − x i j ) = 0 ( 1 ≤ j ≤ L ) , (10)
where the coefficients u i u_i u i are interpreted in F q \mathbb{F}_q F q .
To ensure w ∣ S = u \mathbf{w}|_S=\mathbf{u} w ∣ S = u and ∥ w ∥ p p ≤ W \|\mathbf{w}\|_p^p\le W ∥ w ∥ p p ≤ W , we introduce a polynomial g g g . Its nonzero values will ensure that every z ℓ z_\ell z ℓ and every x i + τ x_i+\tau x i + τ with i ∈ I i\in I i ∈ I lies outside S S S and that all coordinate indices in Equation (9) are pairwise distinct. Set
E = { x b − x i : i ∈ I , b ∈ [ m ] } . E=\{x_b-x_i:i\in I,\ b\in[m]\}. E = { x b − x i : i ∈ I , b ∈ [ m ]} .
Since I ≠ ∅ I\ne\varnothing I = ∅ , we have 0 ∈ E 0\in E 0 ∈ E and ∣ E ∣ ≤ h m |E|\le hm ∣ E ∣ ≤ hm . Define the polynomial g ∈ F q [ Z 1 , … , Z L , Y ] g\in\mathbb{F}_q[Z_1,\ldots,Z_L,Y] g ∈ F q [ Z 1 , … , Z L , Y ] by
g ( Z 1 , … , Z L , Y ) = Y ∏ e ∈ E ∖ { 0 } ( Y − e ) ∏ ℓ = 1 L ∏ b = 1 m ( Z ℓ − x b ) ⋅ ∏ 1 ≤ ℓ < ℓ ′ ≤ L ( Z ℓ − Z ℓ ′ ) ∏ ℓ = 1 L ∏ i ∈ I ( Z ℓ − x i − Y ) . (11) \begin{aligned}
g(Z_1,\ldots,Z_L,Y)={}&Y\prod_{e\in E\setminus\{0\}}(Y-e)\prod_{\ell=1}^{L}\prod_{b=1}^{m}(Z_\ell-x_b)\\
&\cdot\prod_{1\le\ell<\ell'\le L}(Z_\ell-Z_{\ell'})\prod_{\ell=1}^{L}\prod_{i\in I}(Z_\ell-x_i-Y). \tag*{(11)}
\end{aligned} g ( Z 1 , … , Z L , Y ) = Y e ∈ E ∖ { 0 } ∏ ( Y − e ) ℓ = 1 ∏ L b = 1 ∏ m ( Z ℓ − x b ) ⋅ 1 ≤ ℓ < ℓ ′ ≤ L ∏ ( Z ℓ − Z ℓ ′ ) ℓ = 1 ∏ L i ∈ I ∏ ( Z ℓ − x i − Y ) . (11)
The empty product is defined to be 1.
Claim 2. For every z 1 , … , z L , τ ∈ F q z_1,\ldots,z_L,\tau\in\mathbb{F}_q z 1 , … , z L , τ ∈ F q with g ( z 1 , … , z L , τ ) ≠ 0 g(z_1,\ldots,z_L,\tau)\ne0 g ( z 1 , … , z L , τ ) = 0 , we have
z ℓ ∉ S ( ℓ ∈ [ L ] ) , x i + τ ∉ S ( i ∈ I ) , z_\ell\notin S\quad(\ell\in[L]),\qquad x_i+\tau\notin S\quad(i\in I), z ℓ ∈ / S ( ℓ ∈ [ L ]) , x i + τ ∈ / S ( i ∈ I ) , z ℓ ≠ z ℓ ′ ( 1 ≤ ℓ < ℓ ′ ≤ L ) , z ℓ ≠ x i + τ ( ℓ ∈ [ L ] , i ∈ I ) . z_\ell\ne z_{\ell'}\quad(1\le\ell<\ell'\le L),\qquad z_\ell\ne x_i+\tau\quad(\ell\in[L],\ i\in I). z ℓ = z ℓ ′ ( 1 ≤ ℓ < ℓ ′ ≤ L ) , z ℓ = x i + τ ( ℓ ∈ [ L ] , i ∈ I ) . Consequently, the vector in Equation (9) satisfies w ∣ S = u \mathbf{w}|_S=\mathbf{u} w ∣ S = u and ∥ w ∥ p p ≤ W \|\mathbf{w}\|_p^p\le W ∥ w ∥ p p ≤ W .
Proof of Claim 2. We first show that z ℓ ∉ S z_\ell\notin S z ℓ ∈ / S for every ℓ ∈ [ L ] \ell\in[L] ℓ ∈ [ L ] . Since g ( z 1 , … , z L , τ ) ≠ 0 g(z_1,\ldots,z_L,\tau)\ne0 g ( z 1 , … , z L , τ ) = 0 , every factor of g g g is nonzero at ( z 1 , … , z L , τ ) (z_1,\ldots,z_L,\tau) ( z 1 , … , z L , τ ) . The factors Z ℓ − x b Z_\ell-x_b Z ℓ − x b therefore give z ℓ ≠ x b z_\ell\ne x_b z ℓ = x b for every ℓ ∈ [ L ] \ell\in[L] ℓ ∈ [ L ] and b ∈ [ m ] b\in[m] b ∈ [ m ] . Since S S S consists of x 1 , … , x m x_1,\ldots,x_m x 1 , … , x m , this proves z ℓ ∉ S z_\ell\notin S z ℓ ∈ / S .
We next show that x i + τ ∉ S x_i+\tau\notin S x i + τ ∈ / S for every i ∈ I i\in I i ∈ I . The factor Y Y Y gives τ ≠ 0 \tau\ne0 τ = 0 , and the factors Y − e Y-e Y − e give τ ≠ e \tau\ne e τ = e for every e ∈ E ∖ { 0 } e\in E\setminus\{0\} e ∈ E ∖ { 0 } . Thus τ ∉ E \tau\notin E τ ∈ / E . For every i ∈ I i\in I i ∈ I and b ∈ [ m ] b\in[m] b ∈ [ m ] , the definition of E E E gives x b − x i ∈ E x_b-x_i\in E x b − x i ∈ E . Hence τ ≠ x b − x i \tau\ne x_b-x_i τ = x b − x i , which implies x i + τ ≠ x b x_i+\tau\ne x_b x i + τ = x b . Therefore x i + τ ∉ S x_i+\tau\notin S x i + τ ∈ / S for every i ∈ I i\in I i ∈ I .
The remaining factors give the other two groups of inequalities. The factors Z ℓ − Z ℓ ′ Z_\ell-Z_{\ell'} Z ℓ − Z ℓ ′ give z ℓ ≠ z ℓ ′ z_\ell\ne z_{\ell'} z ℓ = z ℓ ′ whenever ℓ < ℓ ′ \ell<\ell' ℓ < ℓ ′ . The factors Z ℓ − x i − Y Z_\ell-x_i-Y Z ℓ − x i − Y give z ℓ ≠ x i + τ z_\ell\ne x_i+\tau z ℓ = x i + τ for every ℓ ∈ [ L ] \ell\in[L] ℓ ∈ [ L ] and i ∈ I i\in I i ∈ I .
We now show that w ∣ S = u \mathbf{w}|_S=\mathbf{u} w ∣ S = u over the integers. The vectors e z ℓ \mathbf{e}_{z_\ell} e z ℓ and e x i + τ \mathbf{e}_{x_i+\tau} e x i + τ have entry 0 at every coordinate in S S S , as their indices lie outside S S S . By Equation (9) , the entries of w \mathbf{w} w on S S S are therefore the same as those of ∑ i ∈ I u i e x i \sum_{i\in I}u_i\mathbf{e}_{x_i} ∑ i ∈ I u i e x i . Since x 1 , … , x m x_1,\ldots,x_m x 1 , … , x m are distinct, this gives w x b = u b w_{x_b}=u_b w x b = u b for every b ∈ I b\in I b ∈ I . For b ∈ [ m ] ∖ I b\in[m]\setminus I b ∈ [ m ] ∖ I , the sum has entry 0 at x b x_b x b , and u b = 0 u_b=0 u b = 0 by the definition of I I I . Thus w x b = u b w_{x_b}=u_b w x b = u b for every b ∈ [ m ] b\in[m] b ∈ [ m ] , which proves w ∣ S = u \mathbf{w}|_S=\mathbf{u} w ∣ S = u .
We finally show that ∥ w ∥ p p ≤ W \|\mathbf{w}\|_p^p\le W ∥ w ∥ p p ≤ W . The elements x i x_i x i with i ∈ I i\in I i ∈ I are distinct, and adding the same τ \tau τ preserves distinctness. Together with the inequalities proved above, this shows that all coordinate indices in Equation (9) are pairwise distinct. The preceding norm calculation therefore gives ∥ w ∥ p p ≤ W \|\mathbf{w}\|_p^p\le W ∥ w ∥ p p ≤ W .
To complete the construction of w w w , it is enough to show that there exists a point ( z 1 , … , z L , τ ) ∈ R q L + 1 (z_1,\ldots,z_L,\tau) \in\mathbb{R}_q^{L+1} ( z 1 , … , z L , τ ) ∈ R q L + 1 satisfying Equation (10) and g ( z 1 , … , z L , τ ) ≠ 0 g(z_1,\ldots,z_L,\tau) \ne0 g ( z 1 , … , z L , τ ) = 0 , where g g g is defined in Equation (11) . For such a point, the vector w w w defined in Equation (9) belongs to L q , k − s L_{q,k}-s L q , k − s . By Claim 2, it also satisfies w ∣ S = u w|_S=u w ∣ S = u and ∥ w ∥ p p ≤ W \lVert w\rVert_p^p \le W ∥ w ∥ p p ≤ W . We prove that such a point exists by applying Lemma 2.19 .
We first show that ξ = ( y 1 , … , y L , 0 ) \xi=(y_1,\ldots,y_L,0) ξ = ( y 1 , … , y L , 0 ) is a common zero of the left sides of Equation (10) and g g g . At ξ \xi ξ , we have Z ℓ = y ℓ Z_\ell=y_\ell Z ℓ = y ℓ for every ℓ ∈ [ L ] \ell\in[L] ℓ ∈ [ L ] and Y = 0 Y=0 Y = 0 . Thus every left side in Equation (10) is zero, since both Z ℓ j − y ℓ j Z_\ell^j-y_\ell^j Z ℓ j − y ℓ j and ( x i + Y ) j − x i j (x_i+Y)^j-x_i^j ( x i + Y ) j − x i j are zero at this point. Since g g g has the factor Y Y Y , we also have g ( ξ ) = 0 g(\xi)=0 g ( ξ ) = 0 .
We next show that the Jacobian matrix of these L + 1 L+1 L + 1 polynomials is invertible at ξ \xi ξ . We order the L L L left sides by increasing j j j , followed by g g g , and use the variable order ( Z 1 , … , Z L , Y ) (Z_1,\ldots,Z_L,Y) ( Z 1 , … , Z L , Y ) . For the left side indexed by j j j , the derivative with respect to Z ℓ Z_\ell Z ℓ is j Z ℓ j − 1 jZ_\ell^{j-1} j Z ℓ j − 1 , whose value at ξ \xi ξ is j y ℓ j − 1 jy_\ell^{j-1} j y ℓ j − 1 . Thus the upper left block is
( 1 1 ⋯ 1 2 y 1 2 y 2 ⋯ 2 y L ⋮ ⋮ ⋱ ⋮ L y 1 L − 1 L y 2 L − 1 ⋯ L y L L − 1 ) . \begin{pmatrix}
1 & 1 & \cdots& 1\\
2y_1 & 2y_2 & \cdots& 2y_L\\
\vdots& \vdots& \ddots& \vdots\\
Ly_1^{L-1} & Ly_2^{L-1} & \cdots& Ly_L^{L-1}
\end{pmatrix}. 1 2 y 1 ⋮ L y 1 L − 1 1 2 y 2 ⋮ L y 2 L − 1 ⋯ ⋯ ⋱ ⋯ 1 2 y L ⋮ L y L L − 1 .
This is a Vandermonde matrix with its j j j th row multiplied by j j j . The elements y 1 , … , y L y_1,\ldots,y_L y 1 , … , y L are distinct, and 1 , … , L 1,\ldots,L 1 , … , L are nonzero in F q \mathbb{F}_q F q because q > L q>L q > L . Hence this block is invertible.
We use the factor Y Y Y in g g g to compute the last row of the Jacobian matrix. Each derivative of g g g with respect to Z ℓ Z_\ell Z ℓ still has the factor Y Y Y , so
∂ g ∂ Z ℓ ( ξ ) = 0 ( ℓ ∈ [ L ] ) . \frac{\partial g}{\partial Z_\ell}(\xi)=0 \qquad(\ell\in[L]). ∂ Z ℓ ∂ g ( ξ ) = 0 ( ℓ ∈ [ L ]) .
When differentiating g g g with respect to Y Y Y , every term except the one obtained by differentiating the first factor Y Y Y still contains Y Y Y and is zero at ξ \xi ξ . Therefore,
∂ g ∂ Y ( ξ ) = ∏ e ∈ E ∖ { 0 } ( − e ) ∏ ℓ = 1 L ∏ b = 1 m ( y ℓ − x b ) ⋅ ∏ 1 ≤ ℓ < ℓ ′ ≤ L ( y ℓ − y ℓ ′ ) ∏ ℓ = 1 L ∏ i ∈ I ( y ℓ − x i ) ≠ 0. \frac{\partial g}{\partial Y}(\xi)=\prod_{e\in E\setminus\{0\}}(-e)\prod_{\ell=1}^{L}\prod_{b=1}^{m}(y_\ell-x_b)\cdot\prod_{1\le\ell<\ell'\le L}(y_\ell-y_{\ell'})\prod_{\ell=1}^{L}\prod_{i\in I}(y_\ell-x_i)\ne0. ∂ Y ∂ g ( ξ ) = e ∈ E ∖ { 0 } ∏ ( − e ) ℓ = 1 ∏ L b = 1 ∏ m ( y ℓ − x b ) ⋅ 1 ≤ ℓ < ℓ ′ ≤ L ∏ ( y ℓ − y ℓ ′ ) ℓ = 1 ∏ L i ∈ I ∏ ( y ℓ − x i ) = 0.
Every factor in this expression is nonzero because e ≠ 0 e\ne0 e = 0 and the elements y 1 , … , y L , x 1 , … , x m y_1,\ldots,y_L,x_1,\ldots,x_m y 1 , … , y L , x 1 , … , x m are distinct. The Jacobian matrix thus has an invertible upper left block, a zero lower left block, and a nonzero lower right entry, so it is invertible.
We now check the remaining assumptions of Lemma 2.19 concerning the degrees and the size of F q \mathbb{F}_q F q . For each 1 ≤ j ≤ L 1\le j\le L 1 ≤ j ≤ L , every term on the left side of Equation (10) has degree at most j j j , and the coefficient of Z 1 j Z_1^j Z 1 j is 1 1 1 . Its degree is therefore exactly j j j , and the product of these degrees is L ! L! L ! . Since g g g is a product of linear factors, we have
deg g = 1 + ∣ E ∖ { 0 } ∣ + L m + ( L 2 ) + L ∣ I ∣ ≤ 1 + ( L + h ) m + L h + ( L 2 ) . \begin{aligned}
\deg g &= 1+|E\setminus\{0\}|+Lm+\binom{L}{2}+L|I|\\
&\le1+(L+h)m+Lh+\binom{L}{2}.
\end{aligned} deg g = 1 + ∣ E ∖ { 0 } ∣ + L m + ( 2 L ) + L ∣ I ∣ ≤ 1 + ( L + h ) m + L h + ( 2 L ) .
All L + 1 L+1 L + 1 polynomials are nonconstant. Our choice of q q q in Equation (8) gives
q > 9 ( L ! ) 5 , q>9(L!)^5, q > 9 ( L ! ) 5 ,
q > 9 L ! ( 1 + ( L + h ) m + L h + ( L 2 ) ) ≥ 9 L ! deg g . q>9L!\left(1+(L+h)m+Lh+\binom{L}{2}\right)\ge9L!\deg g. q > 9 L ! ( 1 + ( L + h ) m + L h + ( 2 L ) ) ≥ 9 L ! deg g .
We can now apply Lemma 2.19 to obtain the required point. We use the L L L left sides of Equation (10) , followed by g g g , as the polynomials in the lemma, with variables ( Z 1 , … , Z L , Y ) (Z_1,\ldots,Z_L,Y) ( Z 1 , … , Z L , Y ) . In this application, n = L + 1 = k ≥ 2 n=L+1=k\ge2 n = L + 1 = k ≥ 2 , Q = q Q=q Q = q , Δ = L ! \Delta=L! Δ = L ! , and f n = g f_n=g f n = g . The lemma gives a point ( z 1 , … , z L , τ ) ∈ F q L + 1 (z_1,\ldots,z_L,\tau)\in\mathbb{F}_q^{L+1} ( z 1 , … , z L , τ ) ∈ F q L + 1 satisfying Equation (10) and g ( z 1 , … , z L , τ ) ≠ 0 g(z_1,\ldots,z_L,\tau)\ne0 g ( z 1 , … , z L , τ ) = 0 .
The point given by the lemma completes the construction of w \mathbf{w} w for the fixed nonzero vector u \mathbf{u} u . Together with the case u = 0 \mathbf{u}=0 u = 0 treated above, this proves condition (iii) of Definition 3.1 . Claim 1 and s ∣ S = 0 \mathbf{s}|_S=\mathbf{0} s ∣ S = 0 give the other two conditions.
We finally bound the running time and the size of the output. The algorithm finds q q q , computes the matrix H \mathbf{H} H , and outputs q q q , H \mathbf{H} H , S S S , and s \mathbf{s} s . Since L = k − 1 L=k-1 L = k − 1 , the bound in Equation (8) gives
T ≤ f 0 ( d + D + h + k ) ( m + 1 ) T\le f_0(d+D+h+k)(m+1) T ≤ f 0 ( d + D + h + k ) ( m + 1 )
for a computable function f 0 f_0 f 0 . By Lemma 2.12 , finding a prime q q q with T < q < 2 T T<q<2T T < q < 2 T takes time polynomial in T T T . The matrix H \mathbf{H} H has k k k rows and q q q columns, and each entry has O ( log q ) O(\log q) O ( log q ) bits. Computing this matrix and choosing s \mathbf{s} s and S S S take time polynomial in q q q and the integer parameters. The output size satisfies the same bound. Therefore, after increasing the computable function if necessary, both the running time and the output size are at most f ( d + D + h + k ) ( m + 1 ) O ( 1 ) f(d+D+h+k)(m+1)^{O(1)} f ( d + D + h + k ) ( m + 1 ) O ( 1 ) , with an exponent independent of d , D , h , k d,D,h,k d , D , h , k .
Finishing the Proof
We now combine the reduction with the deterministic construction of a locally dense lattice. To obtain any fixed approximation factor γ ′ < 2 1 / p \gamma' < 2^{1/p} γ ′ < 2 1/ p , we choose the parameters so that the constructed lattice satisfies the minimum norm condition and the bound in Equation (4) . The following theorem gives the resulting deterministic FPT reduction from γ \gamma γ -GapCVPp _p p to γ ′ \gamma' γ ′ -GapSVPp _p p .
Theorem 3.5. Fix a computable real p ≥ 1 p\ge1 p ≥ 1 and a constant γ ′ ∈ [ 1 , 2 1 / p ) \gamma'\in[1,2^{1/p}) γ ′ ∈ [ 1 , 2 1/ p ) . There are integers γ ≥ 2 \gamma\ge2 γ ≥ 2 , c ≥ 1 c\ge1 c ≥ 1 and a deterministic FPT many-one reduction from γ \gamma γ -GapCVPp _p p to γ ′ \gamma' γ ′ -GapSVPp _p p . The output parameter is d ′ = c d d'=cd d ′ = c d , where d d d is the input parameter.
Proof. We first choose fixed integers γ \gamma γ and c c c that give the required approximation factor. Choose them so that
γ ≥ 2 , c ≥ 1 , γ p / 2 + 8 ≤ c p , γ ′ c < γ . (12) \gamma\ge2,\qquad c\ge1,\qquad\gamma^{p/2}+8\le c^p,\qquad\gamma'c<\gamma. \tag*{(12)} γ ≥ 2 , c ≥ 1 , γ p /2 + 8 ≤ c p , γ ′ c < γ . (12)
Such integers exist because, as γ \gamma γ tends to infinity through the positive integers,
⌈ ( γ p / 2 + 8 ) 1 / p ⌉ γ ⟶ 2 − 1 / p < 1 γ ′ . \frac{\left\lceil(\gamma^{p/2}+8)^{1/p}\right\rceil}{\gamma}\longrightarrow2^{-1/p}<\frac{1}{\gamma'}. γ ⌈ ( γ p /2 + 8 ) 1/ p ⌉ ⟶ 2 − 1/ p < γ ′ 1 .
Thus, for all sufficiently large integers γ \gamma γ , taking c = ⌈ ( γ p / 2 + 8 ) 1 / p ⌉ c=\left\lceil(\gamma^{p/2}+8)^{1/p}\right\rceil c = ⌈ ( γ p /2 + 8 ) 1/ p ⌉ satisfies the conditions in Equation (12) . Fix one such pair γ , c \gamma,c γ , c for the reduction.
We next compute the integer parameters needed to construct the locally dense lattice. Given an instance ( B , t , d ) (\mathbf{B},t,d) ( B , t , d ) of γ \gamma γ -GapCVPp _p p with B ∈ Z m × n \mathbf{B}\in\mathbb{Z}^{m\times n} B ∈ Z m × n , put D = γ d D=\gamma d D = γ d and choose integers h , k h,k h , k with
d p ≤ h < d p + 3 2 , D p / 2 < k < D p / 2 + 3 2 . (13) d^p\le h<d^p+\frac{3}{2},\qquad D^{p/2}<k<D^{p/2}+\frac{3}{2}. \tag*{(13)} d p ≤ h < d p + 2 3 , D p /2 < k < D p /2 + 2 3 . (13)
To compute these integers, first approximate d p d^p d p and D p / 2 D^{p/2} D p /2 from above by rational numbers, with a positive error less than 1 / 2 1/2 1/2 in each case. Taking the ceilings of these rational numbers gives h h h and k k k satisfying the displayed inequalities. Since p p p is computable and γ \gamma γ is fixed, this computation takes time bounded by a computable function of d d d .
We verify that these parameters satisfy the assumptions of Theorem 3.4 . Since D = γ d ≥ 2 D=\gamma d\ge2 D = γ d ≥ 2 and p ≥ 1 p\ge1 p ≥ 1 , we have D p / 2 ≥ 1 D^{p/2}\ge1 D p /2 ≥ 1 . Thus k > D p / 2 k>D^{p/2} k > D p /2 implies k ≥ 2 k\ge2 k ≥ 2 and D p < 2 k D^p<2k D p < 2 k . Our choice of h h h also gives d p ≤ h d^p\le h d p ≤ h . Apply Theorem 3.4 to construct a locally dense lattice with parameters ( p , m , d , D , W ) (p,m,d,D,W) ( p , m , d , D , W ) , where W = k − 1 + 2 h W=k-1+2h W = k − 1 + 2 h .
We now verify the norm bound needed to apply Theorem 3.2 . By Equation (13) , we have
d p + W + 1 = d p + k + 2 h < D p / 2 + 3 d p + 9 / 2 ≤ ( γ p / 2 + 8 ) d p ≤ ( c d ) p . \begin{aligned}
d^p+W+1 &= d^p+k+2h\\
&< D^p/2+3d^p+9/2\\
&\le(\gamma^p/2+8)d^p\\
&\le(cd)^p.
\end{aligned} d p + W + 1 = d p + k + 2 h < D p /2 + 3 d p + 9/2 ≤ ( γ p /2 + 8 ) d p ≤ ( c d ) p .
Here the second inequality uses D = γ d D=\gamma d D = γ d and d p ≥ 1 d^p\ge1 d p ≥ 1 , and the last inequality follows from Equation (12) . Therefore Equation (4) holds. Apply the algorithm in Theorem 3.2 to the input instance and the constructed locally dense lattice. That theorem guarantees that both YES and NO instances are preserved and that the output parameter is c d cd c d .
We finally show that the total running time is FPT. The parameters D D D , h h h , k k k depend only on d d d and the fixed constants and are bounded by a computable function of d d d . The time needed to construct the locally dense lattice and the size of its representation are therefore bounded by f p , γ ( d ) ( m + 1 ) O ( 1 ) f_{p,\gamma}(d)(m+1)^{O(1)} f p , γ ( d ) ( m + 1 ) O ( 1 ) for a computable function f p , γ f_{p,\gamma} f p , γ . The algorithm in Theorem 3.2 takes time polynomial in the input length and the size of the constructed locally dense lattice, including the bit lengths of the integer entries. After increasing f p , γ f_{p,\gamma} f p , γ if necessary, the total running time is bounded by f p , γ ( d ) f_{p,\gamma}(d) f p , γ ( d ) times a polynomial in the input length, with an exponent independent of d d d . Both algorithms are deterministic, and the output parameter c d cd c d depends only on d d d .
Combining this reduction with the hardness of CVP proves Theorem 1.1 .
Proof of Theorem 1.1 . We obtain the claimed hardness of SVP by composing the reductions. Fix a computable real p ≥ 1 p\ge1 p ≥ 1 and a constant 1 ≤ γ ′ < 2 1 / p 1\le\gamma'<2^{1/p} 1 ≤ γ ′ < 2 1/ p . Choose the integer γ \gamma γ from Theorem 3.5 . By Theorem 2.4 , the problem γ \gamma γ -GapCVPp _p p is W[1]-hard under deterministic FPT many-one reductions. Composing these reductions with the reduction in Theorem 3.5 proves that γ ′ \gamma' γ ′ -GapSVPp _p p is W[1]-hard under deterministic FPT many-one reductions.
A Deterministic Reduction from NCP to MDP
We now show that the approach of § 4 also gives the W[1]-hardness of MDP under deterministic reductions. We observe that the reduction of Hirahara and Ogitsuka [23 Theorem 3.5] becomes deterministic if we can deterministically construct a locally dense code, as defined below, in FPT time. We work over a prime field and extend scalars at the end.
Definition 4.1 (Locally dense code). Let p p p be prime and let m m m , k k k , D D D , r r r be positive integers. Let C \mathcal{C} C be a linear code over F p \mathbb{F}_p F p with N N N coordinates, let s ∈ F p N s\in\mathbb{F}_p^N s ∈ F p N , and let S S S be an ordered list of m m m distinct coordinates. The tuple ( C , s , S ) (\mathcal{C},s,S) ( C , s , S ) is an ( m , k , D , r ) (m,k,D,r) ( m , k , D , r ) -locally dense code if
(i) λ ( C ) > D \lambda(\mathcal{C})>D λ ( C ) > D ;
(ii) s ∣ S = 0 s|_S=0 s ∣ S = 0 ;
(iii) for every u ∈ F p m u \in\mathbb{F}_p^m u ∈ F p m with ∥ u ∥ 0 ≤ k \lVert u\rVert_0 \le k ∥ u ∥ 0 ≤ k , there is a nonzero w ∈ C − s w \in C-s w ∈ C − s such that ∥ w ∥ 0 ≤ r \lVert w\rVert_0 \le r ∥ w ∥ 0 ≤ r and w ∣ S = u w|_S=u w ∣ S = u .
We represent C C C by a parity-check matrix over F p \mathbb{F}_p F p .
A Non-Uniform Reduction Using a Locally Dense Code
The following reduction is essentially based on the observation that the reduction of Hirahara and Ogitsuka gives a non-uniform reduction when a locally dense code is provided as advice. For fixed p p p , the same locally dense code can be used for all instances with the same m m m and k k k .
Theorem 4.2 ([23 proof of Theorem 3.5 in the full version, adapted] ). Fix a prime p p p . There is a deterministic algorithm that, given an instance ( G , t , k ) (G,t,k) ( G , t , k ) of ( 4 p ) (4p) ( 4 p ) -GapNCPp _p p with G ∈ F p m × n G \in\mathbb{F}_p^{m \times n} G ∈ F p m × n and an ( m , k , 4 p k , ( 4 p − 2 ) k ) (m,k,4pk,(4p-2)k) ( m , k , 4 p k , ( 4 p − 2 ) k ) -locally dense code ( C , s , S ) (C,s,S) ( C , s , S ) , outputs an instance of 4 p 4 p − 1 \frac{4p}{4p-1} 4 p − 1 4 p -GapMDPp _p p with parameter ( 4 p − 1 ) k (4p-1)k ( 4 p − 1 ) k , preserving both YES and NO instances. If the supplied parity-check matrix of C C C has h h h rows and N N N columns, the algorithm runs in time ( m + n + N + h + k ) O ( 1 ) (m+n+N+h+k)^{O(1)} ( m + n + N + h + k ) O ( 1 ) .
Proof. We first construct the output instance. Set D = 4 p k D=4pk D = 4 p k and r = ( 4 p − 2 ) k r=(4p-2)k r = ( 4 p − 2 ) k . From the supplied parity-check matrix H \mathbf{H} H , compute a basis of ker H \ker\mathbf{H} ker H by Gaussian elimination. Use these basis vectors as the columns of A ∈ F p N × n ′ \mathbf{A} \in\mathbb{F}_p^{N \times n'} A ∈ F p N × n ′ , so that C ( A ) = C C(\mathbf{A})=C C ( A ) = C . Let A S \mathbf{A}_S A S consist of the rows of A \mathbf{A} A indexed by S S S , in the specified order. Let E ∈ F p ( D + 1 ) m × m \mathbf{E} \in\mathbb{F}_p^{(D+1)m \times m} E ∈ F p ( D + 1 ) m × m be the matrix that repeats each coordinate D + 1 D+1 D + 1 times. Multiplication by E \mathbf{E} E therefore multiplies the Hamming weight by D + 1 D+1 D + 1 . Output ( G ′ , k ′ ) (G',k') ( G ′ , k ′ ) , where
G ′ = ( G 0 − t 0 A − s E G − E A S − E t ) , k ′ = k + r = ( 4 p − 1 ) k . (14) G'=\begin{pmatrix}
G & 0 & -t\\
0 & \mathbf{A} & -s\\
\mathbf{E}G & -\mathbf{E}\mathbf{A}_S & -\mathbf{E}t
\end{pmatrix}, \qquad k'=k+r=(4p-1)k. \tag*{(14)} G ′ = G 0 E G 0 A − E A S − t − s − E t , k ′ = k + r = ( 4 p − 1 ) k . (14)
We next show completeness. Suppose that ∥ G x − t ∥ 0 ≤ k \lVert Gx-t\rVert_0 \le k ∥ G x − t ∥ 0 ≤ k for some x ∈ F p n x \in\mathbb{F}_p^n x ∈ F p n . Since C ( A ) = C C(\mathbf{A})=C C ( A ) = C , the local density condition in Definition 4.1 gives y ∈ F p n ′ y \in\mathbb{F}_p^{n'} y ∈ F p n ′ such that
A y − s ≠ 0 , ∥ A y − s ∥ 0 ≤ r , ( A y − s ) ∣ S = G x − t . \mathbf{A}y-s \ne0, \qquad\lVert\mathbf{A}y-s\rVert_0 \le r, \qquad(\mathbf{A}y-s)|_S=Gx-t. A y − s = 0 , ∥ A y − s ∥ 0 ≤ r , ( A y − s ) ∣ S = G x − t .
Since s ∣ S = 0 s|_S=0 s ∣ S = 0 , the last equality gives A S y = G x − t \mathbf{A}_S y=Gx-t A S y = G x − t . Therefore,
G ′ ( x y 1 ) = ( G x − t A y − s 0 ) . G'\begin{pmatrix}x\\y\\1\end{pmatrix}
=
\begin{pmatrix}
Gx-t\\
\mathbf{A}y-s\\
0
\end{pmatrix}. G ′ x y 1 = G x − t A y − s 0 .
This codeword is nonzero because A y − s ≠ 0 \mathbf{A}y-s\ne0 A y − s = 0 . Its weight is at most k + r = k ′ k+r=k' k + r = k ′ .
We now show soundness. Suppose that dist ( C ( G ) , t ) > D \operatorname{dist}(C(G),t)>D dist ( C ( G ) , t ) > D . Assume for contradiction that C ( G ′ ) C(G') C ( G ′ ) contains a nonzero codeword of weight at most D D D . Using s ∣ S = 0 s|_S=0 s ∣ S = 0 , we can write this codeword as
( G x − b t A y − b s E ( G x − b t − ( A y − b s ) ∣ S ) ) \begin{pmatrix}
Gx-bt\\
\mathbf{A}y-bs\\
\mathbf{E}(Gx-bt-(\mathbf{A}y-bs)|_S)
\end{pmatrix} G x − b t A y − b s E ( G x − b t − ( A y − b s ) ∣ S )
for some x ∈ F p n x \in\mathbb{F}_p^n x ∈ F p n , y ∈ F p n ′ y \in\mathbb{F}_p^{n'} y ∈ F p n ′ , and b ∈ F p b \in\mathbb{F}_p b ∈ F p . If b ≠ 0 b\ne0 b = 0 , multiplication by b − 1 b^{-1} b − 1 does not change Hamming weight, so the first block has weight
∥ G x − b t ∥ 0 = ∥ G ( b − 1 x ) − t ∥ 0 ≥ dist ( C ( G ) , t ) > D . \lVert Gx-bt\rVert_0=\lVert G(b^{-1}x)-t\rVert_0\ge\operatorname{dist}(C(G),t)>D. ∥ G x − b t ∥ 0 = ∥ G ( b − 1 x ) − t ∥ 0 ≥ dist ( C ( G ) , t ) > D .
This contradicts the assumed weight bound, so b = 0 b = 0 b = 0 .
The case b = 0 b = 0 b = 0 also leads to a contradiction. The second block is now A y ∈ C Ay \in C A y ∈ C and has weight at most D D D . Since λ ( C ) > D \lambda(C) > D λ ( C ) > D , we must have A y = 0 Ay = 0 A y = 0 . The last block is therefore E G x EGx E G x . Since the whole codeword is nonzero, we must have G x ≠ 0 Gx \ne0 G x = 0 . Thus the last block has weight
∥ E G x ∥ 0 = ( D + 1 ) ∥ G x ∥ 0 ≥ D + 1 , \lVert EGx\rVert_{0} = (D + 1)\lVert Gx\rVert_{0} \ge D + 1, ∥ E G x ∥ 0 = ( D + 1 ) ∥ G x ∥ 0 ≥ D + 1 ,
again contradicting the assumed weight bound. Therefore λ ( C ( G ′ ) ) > D = 4 p 4 p − 1 k ′ \lambda(C(G^{\prime})) > D = \frac{4p}{4p-1}k^{\prime} λ ( C ( G ′ )) > D = 4 p − 1 4 p k ′ .
We finally bound the running time. The matrix G ′ G^{\prime} G ′ has m + N + ( D + 1 ) m m + N + (D + 1)m m + N + ( D + 1 ) m rows and n + n ′ + 1 n + n^{\prime} + 1 n + n ′ + 1 columns, where n ′ ≤ N n^{\prime} \le N n ′ ≤ N . Since p p p is fixed and D = 4 p k D = 4pk D = 4 p k , computing A A A by Gaussian elimination and forming G ′ G^{\prime} G ′ take ( m + n + N + h + k ) O ( 1 ) (m + n + N + h + k)^{O(1)} ( m + n + N + h + k ) O ( 1 ) time.
A Deterministic FPT Construction of Locally Dense Codes
In this section, we give a deterministic FPT algorithm that constructs a locally dense code as defined in Definition 4.1 . Our construction uses an extended BCH code.
Theorem 4.3. Fix a prime p p p . Given positive integers k , m k, m k , m , a deterministic algorithm constructs an ( m , k , 4 p k , ( 4 p − 2 ) k ) (m, k, 4pk, (4p - 2)k) ( m , k , 4 p k , ( 4 p − 2 ) k ) -locally dense code ( C , s , S ) (C, s, S) ( C , s , S ) . The coordinates of C C C are indexed by an explicitly represented extension field K / F p K/\mathbb{F}_{p} K / F p , and S = ( x 1 , … , x m ) S = (x_{1}, \ldots, x_{m}) S = ( x 1 , … , x m ) consists of distinct elements of K K K . The algorithm outputs a parity-check matrix for C C C , the vector s s s , and the coordinates in S S S . The field size and running time are bounded by f p ( k ) ( m + 1 ) O ( 1 ) f_{p}(k)(m + 1)^{O(1)} f p ( k ) ( m + 1 ) O ( 1 ) for a computable function f p f_{p} f p , with an exponent independent of k k k .
Proof. We first choose the field that indexes the coordinates of the code. Put
D = 4 p k , J = { j : 1 ≤ j < D , p ∤ j } , L = ∣ J ∣ = 4 ( p − 1 ) k . D = 4pk,\qquad J = \{j : 1 \le j < D,\ p \nmid j\},\qquad L = \lvert J\rvert= 4(p - 1)k. D = 4 p k , J = { j : 1 ≤ j < D , p ∤ j } , L = ∣ J ∣ = 4 ( p − 1 ) k .
Let Π J = ∏ j ∈ J j \Pi_{J} = \prod_{j \in J} j Π J = ∏ j ∈ J j . Choose the smallest power Q Q Q of p p p satisfying
Q > max { D , m + L , 9 Π J 5 , 9 Π J ( 1 + ( L + k ) m ) } , Q > \max\{D,\ m + L,\ 9\Pi_{J}^{5},\ 9\Pi_{J}(1 + (L + k)m)\}, Q > max { D , m + L , 9 Π J 5 , 9 Π J ( 1 + ( L + k ) m )} ,
and construct K = F Q K = \mathbb{F}_{Q} K = F Q using Lemma 2.9 . For z ∈ K z \in K z ∈ K , let e z ∈ F p K e_{z} \in\mathbb{F}_{p}^{K} e z ∈ F p K have entry 1 at z z z and entry 0 at every other coordinate.
Next, we construct the output consisting of a code C C C , a vector s s s , and an ordered list of coordinates S S S . We define the code C C C by
C = { c ∈ F p K : ∑ z ∈ K c z = 0 , ∑ z ∈ K c z z j = 0 ( j ∈ J ) } . (15) C = \left\{c \in\mathbb{F}_{p}^{K} : \sum_{z \in K} c_{z} = 0,\quad\sum_{z \in K} c_{z}z^{j} = 0\quad(j \in J)\right\}. \tag*{(15)} C = { c ∈ F p K : z ∈ K ∑ c z = 0 , z ∈ K ∑ c z z j = 0 ( j ∈ J ) } . (15)
Expanding each equation over K K K in the chosen F p \mathbb{F}_{p} F p -basis of K K K yields a parity-check matrix over F p \mathbb{F}_{p} F p . To construct s s s and S S S , consider the matrix whose rows are indexed by J J J , columns are indexed by y ∈ K y \in K y ∈ K , and ( j , y ) (j,y) ( j , y ) -entry is j y j − 1 jy^{j-1} j y j − 1 . Its rows are linearly independent over K K K . Indeed, a nontrivial linear dependence among the rows would give a polynomial of degree at most D − 2 D - 2 D − 2 that vanishes at every element of K K K . This polynomial would be nonzero because its monomials have distinct exponents and each j ∈ J j \in J j ∈ J is nonzero in K K K . This is impossible because D − 2 < Q D - 2 < Q D − 2 < Q . Using Gaussian elimination with the fixed enumeration of K K K , select L L L linearly independent columns and denote their indices by y 1 , … , y L y_{1}, \ldots, y_{L} y 1 , … , y L . Then
( j y ℓ j − 1 ) j ∈ J , ℓ ∈ [ L ] is invertible. (16) \left(jy_{\ell}^{j-1}\right)_{j \in J,\ell\in[L]}
\text{ is invertible.} \tag*{(16)} ( j y ℓ j − 1 ) j ∈ J , ℓ ∈ [ L ] is invertible. (16)
Since Q > m + L Q>m+L Q > m + L , we can choose the first m m m distinct elements x 1 , … , x m x_1,\ldots,x_m x 1 , … , x m outside { y 1 , … , y L } \{y_1,\ldots,y_L\} { y 1 , … , y L } in the same enumeration. Set
S = ( x 1 , … , x m ) , s = − ∑ ℓ = 1 L e y ℓ . S=(x_1,\ldots,x_m),\qquad\boldsymbol{s}=-\sum_{\ell=1}^{L}e_{y_\ell}. S = ( x 1 , … , x m ) , s = − ℓ = 1 ∑ L e y ℓ .
Thus s ∣ S = 0 \boldsymbol{s}|_S=0 s ∣ S = 0 . When considering membership in S S S , we identify S S S with its underlying set { x 1 , … , x m } \{x_1,\ldots,x_m\} { x 1 , … , x m } .
We prove the required minimum distance of C C C .
Claim 1. The code in Equation (15) satisfies λ ( C ) > D \lambda(C)>D λ ( C ) > D .
Proof of Claim 1. Suppose for contradiction that there exists a nonzero codeword c ∈ C ∖ { 0 } \boldsymbol{c}\in C\setminus\{0\} c ∈ C ∖ { 0 } with support { z 1 , … , z t } \{z_1,\ldots,z_t\} { z 1 , … , z t } , where 1 ≤ t ≤ D 1\leq t\leq D 1 ≤ t ≤ D . For each 1 ≤ b < t 1\leq b<t 1 ≤ b < t , write b = p e j b=p^e j b = p e j with p ∤ j p\nmid j p ∤ j . Since j ≤ b < D j\leq b<D j ≤ b < D , we have j ∈ J j\in J j ∈ J . By Equation (15) , we have
∑ i = 1 t c z i z i j = 0. \sum_{i=1}^{t}c_{z_i}z_i^j=0. i = 1 ∑ t c z i z i j = 0.
Taking the p e p^e p e -th power of both sides gives
∑ i = 1 t c z i z i j p e = ∑ i = 1 t c z i z i b = 0 , \sum_{i=1}^{t}c_{z_i}z_i^{jp^e}=\sum_{i=1}^{t}c_{z_i}z_i^b=0, i = 1 ∑ t c z i z i j p e = i = 1 ∑ t c z i z i b = 0 ,
since K K K has characteristic p p p and c z i ∈ F p c_{z_i}\in\mathbb{F}_p c z i ∈ F p . Together with ∑ i = 1 t c z i = 0 \sum_{i=1}^{t}c_{z_i}=0 ∑ i = 1 t c z i = 0 , these equations can be written as
( 1 1 ⋯ 1 z 1 z 2 ⋯ z t ⋮ ⋮ ⋱ ⋮ z 1 t − 1 z 2 t − 1 ⋯ z t t − 1 ) ( c z 1 c z 2 ⋮ c z t ) = 0. \begin{pmatrix}
1 & 1 & \cdots& 1\\
z_1 & z_2 & \cdots& z_t\\
\vdots& \vdots& \ddots& \vdots\\
z_1^{t-1} & z_2^{t-1} & \cdots& z_t^{t-1}
\end{pmatrix}
\begin{pmatrix}
c_{z_1}\\
c_{z_2}\\
\vdots\\
c_{z_t}
\end{pmatrix}
=0. 1 z 1 ⋮ z 1 t − 1 1 z 2 ⋮ z 2 t − 1 ⋯ ⋯ ⋱ ⋯ 1 z t ⋮ z t t − 1 c z 1 c z 2 ⋮ c z t = 0.
The Vandermonde matrix is invertible because the z i z_i z i are distinct. Thus every c z i c_{z_i} c z i is zero, contrary to the choice of c \boldsymbol{c} c . □
We now construct, for each u ∈ F p m \boldsymbol{u}\in\mathbb{F}_p^m u ∈ F p m with ∥ u ∥ 0 ≤ k \|\boldsymbol{u}\|_0\leq k ∥ u ∥ 0 ≤ k , a vector w ∈ C − s \boldsymbol{w}\in C-\boldsymbol{s} w ∈ C − s satisfying
w ∣ S = u , 0 < ∥ w ∥ 0 ≤ ( 4 p − 2 ) k , \boldsymbol{w}|_S=\boldsymbol{u},\qquad0<\|\boldsymbol{w}\|_0\leq(4p-2)k, w ∣ S = u , 0 < ∥ w ∥ 0 ≤ ( 4 p − 2 ) k ,
as required by condition (iii) of Definition 4.1 . If u = 0 \boldsymbol{u}=0 u = 0 , choose w = − s \boldsymbol{w}=-\boldsymbol{s} w = − s . Then w + s = 0 ∈ C \boldsymbol{w}+\boldsymbol{s}=0\in C w + s = 0 ∈ C , w ∣ S = 0 \boldsymbol{w}|_S=0 w ∣ S = 0 , and 0 < ∥ w ∥ 0 = L ≤ ( 4 p − 2 ) k 0<\|\boldsymbol{w}\|_0=L\leq(4p-2)k 0 < ∥ w ∥ 0 = L ≤ ( 4 p − 2 ) k . For the rest of the proof, fix u ≠ 0 \boldsymbol{u}\neq0 u = 0 and put T = { i ∈ [ m ] : u i ≠ 0 } T=\{i\in[m]:u_i\neq0\} T = { i ∈ [ m ] : u i = 0 } , so that 1 ≤ ∣ T ∣ ≤ k 1\leq|T|\leq k 1 ≤ ∣ T ∣ ≤ k . For any z 1 , … , z L , τ ∈ K z_1,\ldots,z_L,\tau\in K z 1 , … , z L , τ ∈ K , define
w = ∑ ℓ = 1 L e z ℓ + ∑ i ∈ T u i ( e x i − e x i + τ ) . (17) \boldsymbol{w}=\sum_{\ell=1}^{L}e_{z_\ell}+\sum_{i\in T}u_i(e_{x_i}-e_{x_i+\tau}). \tag*{(17)} w = ℓ = 1 ∑ L e z ℓ + i ∈ T ∑ u i ( e x i − e x i + τ ) . (17)
The support of w \boldsymbol{w} w is contained in the set of indices appearing in this expression. Hence, for every choice of these field elements,
∥ w ∥ 0 ≤ L + 2 ∣ T ∣ ≤ L + 2 k = ( 4 p − 2 ) k . \|\boldsymbol{w}\|_0\leq L+2|T|\leq L+2k=(4p-2)k. ∥ w ∥ 0 ≤ L + 2∣ T ∣ ≤ L + 2 k = ( 4 p − 2 ) k .
We derive the equations equivalent to w ∈ C − s w \in C - s w ∈ C − s . By Equation (15) , the first condition for w + s ∈ C w+s \in C w + s ∈ C is
∑ z ∈ K ( w z + s z ) = 0. \sum_{z\in K}(w_z+s_z)=0. z ∈ K ∑ ( w z + s z ) = 0.
This condition holds for every choice of z 1 , … , z L , τ ∈ K z_1,\ldots,z_L,\tau\in K z 1 , … , z L , τ ∈ K , since
∑ z ∈ K ( w z + s z ) = ∑ ℓ = 1 L ( 1 − 1 ) + ∑ i ∈ T u i ( 1 − 1 ) = 0. \sum_{z\in K}(w_z+s_z)=\sum_{\ell=1}^{L}(1-1)+\sum_{i\in T}u_i(1-1)=0. z ∈ K ∑ ( w z + s z ) = ℓ = 1 ∑ L ( 1 − 1 ) + i ∈ T ∑ u i ( 1 − 1 ) = 0.
By Equation (15) , the remaining conditions for w + s ∈ C w+s \in C w + s ∈ C are
∑ z ∈ K ( w z + s z ) z j = 0 ( j ∈ J ) . \sum_{z\in K}(w_z+s_z)z^j=0\qquad(j\in J). z ∈ K ∑ ( w z + s z ) z j = 0 ( j ∈ J ) .
For each j ∈ J j\in J j ∈ J and ℓ ∈ [ L ] \ell\in[L] ℓ ∈ [ L ] , we have
∑ z ∈ K ( e z ℓ ) z z j = z ℓ j , \sum_{z\in K}(e_{z_\ell})_z z^j=z_\ell^j, z ∈ K ∑ ( e z ℓ ) z z j = z ℓ j ,
since e z ℓ e_{z_\ell} e z ℓ has entry 1 at z ℓ z_\ell z ℓ and entry 0 at every other coordinate. Applying the same calculation to each term of w + s w+s w + s gives
∑ z ∈ K ( w z + s z ) z j = ∑ ℓ = 1 L ( z ℓ j − y ℓ j ) + ∑ i ∈ T u i ( x i j − ( x i + τ ) j ) = ∑ ℓ = 1 L ( z ℓ j − y ℓ j ) − ∑ i ∈ T u i ( ( x i + τ ) j − x i j ) . \begin{aligned}
\sum_{z\in K}(w_z+s_z)z^j=\sum_{\ell=1}^{L}(z_\ell^j-y_\ell^j)+\sum_{i\in T}u_i\left(x_i^j-(x_i+\tau)^j\right) \\
&=\sum_{\ell=1}^{L}(z_\ell^j-y_\ell^j)-\sum_{i\in T}u_i\left((x_i+\tau)^j-x_i^j\right).
\end{aligned} z ∈ K ∑ ( w z + s z ) z j = ℓ = 1 ∑ L ( z ℓ j − y ℓ j ) + i ∈ T ∑ u i ( x i j − ( x i + τ ) j ) = ℓ = 1 ∑ L ( z ℓ j − y ℓ j ) − i ∈ T ∑ u i ( ( x i + τ ) j − x i j ) .
Let Z 1 , … , Z L , Y Z_1,\ldots,Z_L,Y Z 1 , … , Z L , Y be variables over K K K . Therefore, w + s ∈ C w+s\in C w + s ∈ C if and only if ( z 1 , … , z L , τ ) (z_1,\ldots,z_L,\tau) ( z 1 , … , z L , τ ) satisfies
∑ ℓ = 1 L ( Z ℓ j − y ℓ j ) − ∑ i ∈ T u i ( ( x i + Y ) j − x i j ) = 0 ( j ∈ J ) . (18) \sum_{\ell=1}^{L}(Z_\ell^j-y_\ell^j)-\sum_{i\in T}u_i\left((x_i+Y)^j-x_i^j\right)=0\qquad(j\in J). \tag*{(18)} ℓ = 1 ∑ L ( Z ℓ j − y ℓ j ) − i ∈ T ∑ u i ( ( x i + Y ) j − x i j ) = 0 ( j ∈ J ) . (18)
To ensure w ∣ S = u w|_S=u w ∣ S = u , we introduce a polynomial g g g such that g ( z 1 , … , z L , τ ) ≠ 0 g(z_1,\ldots,z_L,\tau)\ne0 g ( z 1 , … , z L , τ ) = 0 implies z ℓ ∉ S z_\ell\notin S z ℓ ∈ / S for every ℓ ∈ [ L ] \ell\in[L] ℓ ∈ [ L ] and x i + τ ∉ S x_i+\tau\notin S x i + τ ∈ / S for every i ∈ T i\in T i ∈ T . Set
E = { x b − x i : i ∈ T , b ∈ [ m ] } . E=\{x_b-x_i:i\in T,\ b\in[m]\}. E = { x b − x i : i ∈ T , b ∈ [ m ]} .
Since T ≠ ∅ T\ne\varnothing T = ∅ , we have 0 ∈ E 0\in E 0 ∈ E and ∣ E ∣ ≤ k m |E|\le km ∣ E ∣ ≤ k m . Define the polynomial g ∈ K [ Z 1 , … , Z L , Y ] g\in K[Z_1,\ldots,Z_L,Y] g ∈ K [ Z 1 , … , Z L , Y ] by
g ( Z 1 , … , Z L , Y ) = Y ∏ e ∈ E ∖ { 0 } ( Y − e ) ∏ ℓ = 1 L ∏ b = 1 m ( Z ℓ − x b ) . (19) g(Z_1,\ldots,Z_L,Y)=Y\prod_{e\in E\setminus\{0\}}(Y-e)\prod_{\ell=1}^{L}\prod_{b=1}^{m}(Z_\ell-x_b). \tag*{(19)} g ( Z 1 , … , Z L , Y ) = Y e ∈ E ∖ { 0 } ∏ ( Y − e ) ℓ = 1 ∏ L b = 1 ∏ m ( Z ℓ − x b ) . (19)
An empty product is 1.
Claim 2. For every z 1 , … , z L , τ ∈ K z_1,\ldots,z_L,\tau\in K z 1 , … , z L , τ ∈ K with g ( z 1 , … , z L , τ ) ≠ 0 g(z_1,\ldots,z_L,\tau)\ne0 g ( z 1 , … , z L , τ ) = 0 , we have
z ℓ ∉ S ( ℓ ∈ [ L ] ) , x i + τ ∉ S ( i ∈ T ) . z_\ell\notin S\qquad(\ell\in[L]),\qquad x_i+\tau\notin S\qquad(i\in T). z ℓ ∈ / S ( ℓ ∈ [ L ]) , x i + τ ∈ / S ( i ∈ T ) . The vector in Equation (17) consequently satisfies w ∣ S = u w|_S=u w ∣ S = u and w ≠ 0 w\ne0 w = 0 .
Proof of Claim 2. We first show that z ℓ ∉ S z_{\ell} \notin S z ℓ ∈ / S for every ℓ ∈ [ L ] \ell\in[L] ℓ ∈ [ L ] . Since g ( z 1 , … , z L , τ ) ≠ 0 g(z_1,\ldots,z_L,\tau) \ne0 g ( z 1 , … , z L , τ ) = 0 , every factor of g g g is nonzero at ( z 1 , … , z L , τ ) (z_1,\ldots,z_L,\tau) ( z 1 , … , z L , τ ) . The factors Z ℓ − x b Z_{\ell}-x_b Z ℓ − x b therefore give z ℓ ≠ x b z_{\ell} \ne x_b z ℓ = x b for every ℓ ∈ [ L ] \ell\in[L] ℓ ∈ [ L ] and b ∈ [ m ] b \in[m] b ∈ [ m ] . Since S S S consists of x 1 , … , x m x_1,\ldots,x_m x 1 , … , x m , we have z ℓ ∉ S z_{\ell} \notin S z ℓ ∈ / S for every ℓ ∈ [ L ] \ell\in[L] ℓ ∈ [ L ] .
We next show that x i + τ ∉ S x_i+\tau\notin S x i + τ ∈ / S for every i ∈ T i \in T i ∈ T . The factor Y Y Y gives τ ≠ 0 \tau\ne0 τ = 0 , and the factors Y − e Y-e Y − e give τ ≠ e \tau\ne e τ = e for every e ∈ E ∖ { 0 } e \in E \setminus\{0\} e ∈ E ∖ { 0 } . Thus τ ∉ E \tau\notin E τ ∈ / E . For every i ∈ T i \in T i ∈ T and b ∈ [ m ] b \in[m] b ∈ [ m ] , the definition of E E E gives x b − x i ∈ E x_b-x_i \in E x b − x i ∈ E . Hence τ ≠ x b − x i \tau\ne x_b-x_i τ = x b − x i , which implies x i + τ ≠ x b x_i+\tau\ne x_b x i + τ = x b . Therefore x i + τ ∉ S x_i+\tau\notin S x i + τ ∈ / S for every i ∈ T i \in T i ∈ T .
We now show that w ∣ S = u w|_S=u w ∣ S = u and w ≠ 0 w \ne0 w = 0 . The vectors e z ℓ e_{z_{\ell}} e z ℓ and e x i + τ e_{x_i+\tau} e x i + τ have entry 0 at every coordinate in S S S , as their indices lie outside S S S . By Equation (17) , the entries of w w w on S S S are therefore the same as those of ∑ i ∈ T u i e x i \sum_{i\in T}u_i e_{x_i} ∑ i ∈ T u i e x i . Since x 1 , … , x m x_1,\ldots,x_m x 1 , … , x m are distinct, this gives w x b = u b w_{x_b}=u_b w x b = u b for every b ∈ T b \in T b ∈ T . For b ∈ [ m ] ∖ T b \in[m]\setminus T b ∈ [ m ] ∖ T , the sum has entry 0 at x b x_b x b , and u b = 0 u_b=0 u b = 0 by the definition of T T T . Thus w x b = u b w_{x_b}=u_b w x b = u b for every b ∈ [ m ] b \in[m] b ∈ [ m ] , which proves w ∣ S = u w|_S=u w ∣ S = u . Since u ≠ 0 u \ne0 u = 0 , we also have w ≠ 0 w \ne0 w = 0 .
To complete the construction of w w w , it is enough to show that there exists a point ( z 1 , … , z L , τ ) ∈ K L + 1 (z_1,\ldots,z_L,\tau)\in K^{L+1} ( z 1 , … , z L , τ ) ∈ K L + 1 satisfying Equation (18) and g ( z 1 , … , z L , τ ) ≠ 0 g(z_1,\ldots,z_L,\tau)\ne0 g ( z 1 , … , z L , τ ) = 0 , where g g g is defined in Equation (19) . For such a point, the vector w w w defined in Equation (17) belongs to C − s C-s C − s and satisfies ∥ w ∥ 0 ≤ ( 4 p − 2 ) k \|w\|_0\le(4p-2)k ∥ w ∥ 0 ≤ ( 4 p − 2 ) k . By Claim 2, it also satisfies w ∣ S = u w|_S=u w ∣ S = u and w ≠ 0 w\ne0 w = 0 . We prove that such a point exists by applying Lemma 2.19.
We first show that ξ = ( y 1 , … , y L , 0 ) \xi=(y_1,\ldots,y_L,0) ξ = ( y 1 , … , y L , 0 ) is a common zero of the left sides of Equation (18) and g g g . At ξ \xi ξ , we have Z ℓ = y ℓ Z_{\ell}=y_{\ell} Z ℓ = y ℓ for every ℓ ∈ [ L ] \ell\in[L] ℓ ∈ [ L ] and Y = 0 Y=0 Y = 0 . Thus every left side in Equation (18) is zero, since both Z ℓ j − y ℓ j Z_{\ell}^{j}-y_{\ell}^{j} Z ℓ j − y ℓ j and ( x i + Y ) j − x i j (x_i+Y)^j-x_i^j ( x i + Y ) j − x i j are zero at this point. Since g g g has the factor Y Y Y , we also have g ( ξ ) = 0 g(\xi)=0 g ( ξ ) = 0 .
We next show that the Jacobian matrix of these L + 1 L+1 L + 1 polynomials is invertible at ξ \xi ξ . We order the L L L left sides by increasing j ∈ J j\in J j ∈ J , followed by g g g , and use the variable order ( Z 1 , … , Z L , Y ) (Z_1,\ldots,Z_L,Y) ( Z 1 , … , Z L , Y ) . For the left side indexed by j j j , the derivative with respect to Z ℓ Z_{\ell} Z ℓ is j Z ℓ j − 1 jZ_{\ell}^{j-1} j Z ℓ j − 1 , whose value at ξ \xi ξ is j y ℓ j − 1 jy_{\ell}^{j-1} j y ℓ j − 1 . Thus the upper left block is the invertible matrix in Equation (16) . Each derivative of g g g with respect to Z ℓ Z_{\ell} Z ℓ still has the factor Y Y Y , so
∂ g ∂ Z ℓ ( ξ ) = 0 ( ℓ ∈ [ L ] ) . \frac{\partial g}{\partial Z_{\ell}}(\xi)=0 \qquad(\ell\in[L]). ∂ Z ℓ ∂ g ( ξ ) = 0 ( ℓ ∈ [ L ]) .
When differentiating g g g with respect to Y Y Y , every term except the one obtained by differentiating the first factor Y Y Y still contains Y Y Y and is zero at ξ \xi ξ . Therefore,
∂ g ∂ Y ( ξ ) = ∏ e ∈ E ∖ { 0 } ( − e ) ∏ ℓ = 1 L ∏ b = 1 m ( y ℓ − x b ) ≠ 0 , \frac{\partial g}{\partial Y}(\xi)=\prod_{e\in E\setminus\{0\}}(-e)\prod_{\ell=1}^{L}\prod_{b=1}^{m}(y_{\ell}-x_b)\ne0, ∂ Y ∂ g ( ξ ) = e ∈ E ∖ { 0 } ∏ ( − e ) ℓ = 1 ∏ L b = 1 ∏ m ( y ℓ − x b ) = 0 ,
since e ≠ 0 e\ne0 e = 0 and y ℓ ≠ x b y_{\ell}\ne x_b y ℓ = x b . The Jacobian matrix thus has an invertible upper left block, a zero lower left block, and a nonzero lower right entry, so it is invertible.
We now check the remaining assumptions of Lemma 2.19 concerning the degrees and the size of K K K . For each j ∈ J j\in J j ∈ J , every term on the left side of Equation (18) has degree at most j j j , and the coefficient of Z 1 j Z_1^j Z 1 j is 1. Its degree is therefore exactly j j j , and the product of these degrees is ∏ J \prod_J ∏ J . Since g g g is a product of linear factors, we have
deg g = 1 + ∣ E ∖ { 0 } ∣ + L m ≤ 1 + ( L + k ) m . \deg g=1+|E\setminus\{0\}|+Lm\le1+(L+k)m. deg g = 1 + ∣ E ∖ { 0 } ∣ + L m ≤ 1 + ( L + k ) m .
All L + 1 L+1 L + 1 polynomials are nonconstant. Our choice of Q Q Q gives
Q > 9 Π J 5 , Q > 9 Π J ( 1 + ( L + k ) m ) ≥ 9 Π J deg g . Q>9\Pi_J^5,\qquad Q>9\Pi_J\bigl(1+(L+k)m\bigr)\ge9\Pi_J\deg g. Q > 9 Π J 5 , Q > 9 Π J ( 1 + ( L + k ) m ) ≥ 9 Π J deg g .
We can now apply Lemma 2.19 to obtain the required point. We use the L L L left sides of Equation (18) , followed by g g g , as the polynomials in the lemma, with variables ( Z 1 , … , Z L , Y ) (Z_1,\ldots,Z_L,Y) ( Z 1 , … , Z L , Y ) . In this application, n = L + 1 ≥ 2 n=L+1\ge2 n = L + 1 ≥ 2 , Δ = Π J \Delta=\Pi_J Δ = Π J , and f n = g f_n=g f n = g . The lemma gives a point ( z 1 , … , z L , τ ) ∈ K L + 1 (z_1,\ldots,z_L,\tau)\in K^{L+1} ( z 1 , … , z L , τ ) ∈ K L + 1 satisfying Equation (18) and g ( z 1 , … , z L , τ ) ≠ 0 g(z_1,\ldots,z_L,\tau)\ne0 g ( z 1 , … , z L , τ ) = 0 .
The point given by the lemma completes the construction of w \mathbf{w} w for the fixed nonzero vector u \mathbf{u} u . Together with the case u = 0 \mathbf{u}=0 u = 0 treated above, this proves condition (iii) of Definition 4.1 . Claim 1 and s ∣ S = 0 \mathbf{s}|_S=\mathbf{0} s ∣ S = 0 give the other two conditions.
We finally bound the running time and the size of the output. The algorithm constructs K K K , computes the parity-check matrix and the matrix used to select y 1 , … , y L y_1,\ldots,y_L y 1 , … , y L , and outputs the parity-check matrix, S S S , and s \mathbf{s} s . Since Q Q Q is the smallest power of p p p satisfying the required inequality, we have
Q ≤ p max { D , m + L , 9 Π J 5 , 9 Π J ( 1 + ( L + k ) m ) } . Q \le p\max\{D,\ m+L,\ 9\Pi_J^5,\ 9\Pi_J(1+(L+k)m)\}. Q ≤ p max { D , m + L , 9 Π J 5 , 9 Π J ( 1 + ( L + k ) m )} .
Since D D D , L L L , and Π J \Pi_J Π J depend only on p p p and k k k , this gives Q ≤ f p ( k ) ( m + 1 ) Q\le f_p(k)(m+1) Q ≤ f p ( k ) ( m + 1 ) for a computable function f p f_p f p . The parity-check matrix has at most 1 + L log p Q 1+L\log_p Q 1 + L log p Q rows and Q Q Q columns. The matrix used to select y 1 , … , y L y_1,\ldots,y_L y 1 , … , y L has L L L rows and Q Q Q columns. Computing these matrices and selecting the coordinates require a number of field operations polynomial in Q Q Q , since D , L , m < Q D,L,m<Q D , L , m < Q . By Lemma 2.9 , constructing K K K , enumerating its elements, and performing these operations take time polynomial in Q Q Q . The output size is also polynomial in Q Q Q . Therefore, after increasing f p f_p f p if necessary, both the running time and the output size are at most f p ( k ) ( m + 1 ) O ( 1 ) f_p(k)(m+1)^{O(1)} f p ( k ) ( m + 1 ) O ( 1 ) , where the exponent does not depend on k k k .
Finishing the Proof
We first obtain a deterministic FPT reduction from NCP to MDP over prime fields. The reduction in Theorem 4.2 takes a locally dense code as additional input, and Theorem 4.3 constructs such a code deterministically in FPT time.
Theorem 4.4. For every fixed prime p p p , there is a deterministic FPT many-one reduction from ( 4 p ) (4p) ( 4 p ) -GapNCPp _p p to 4 p 4 p − 1 \frac{4p}{4p-1} 4 p − 1 4 p -GapMDPp _p p . The output parameter is ( 4 p − 1 ) k (4p-1)k ( 4 p − 1 ) k , where k k k is the input parameter.
Proof. We construct the reduction by applying the two algorithms in sequence. Given an instance ( G , t , k ) (\mathbf{G},t,k) ( G , t , k ) of ( 4 p ) (4p) ( 4 p ) -GapNCPp _p p with G ∈ F p m × n \mathbf{G}\in\mathbb{F}_p^{m\times n} G ∈ F p m × n , use Theorem 4.3 to construct an ( m , k , 4 p k , ( 4 p − 2 ) k ) (m,k,4pk,(4p-2)k) ( m , k , 4 p k , ( 4 p − 2 ) k ) -locally dense code ( C , s , S ) (C,\mathbf{s},S) ( C , s , S ) . Apply the algorithm in Theorem 4.2 to ( G , t , k ) (\mathbf{G},t,k) ( G , t , k ) and ( C , s , S ) (C,\mathbf{s},S) ( C , s , S ) . That theorem guarantees that both YES and NO instances are preserved and that the output parameter is ( 4 p − 1 ) k (4p-1)k ( 4 p − 1 ) k .
We next show that the total running time is FPT. The time needed to construct the locally dense code and the size of its representation are bounded by f p ( k ) ( m + 1 ) O ( 1 ) f_p(k)(m+1)^{O(1)} f p ( k ) ( m + 1 ) O ( 1 ) for a computable function f p f_p f p . The algorithm in Theorem 4.2 takes time polynomial in m + n + k m+n+k m + n + k and the size of the constructed locally dense code. Thus, after increasing f p f_p f p if necessary, the total running time is bounded by f p ( k ) ( m + n ) O ( 1 ) f_p(k)(m+n)^{O(1)} f p ( k ) ( m + n ) O ( 1 ) , with an exponent independent of k k k . Both algorithms are deterministic, and for fixed p p p the output parameter ( 4 p − 1 ) k (4p-1)k ( 4 p − 1 ) k depends only on k k k .
To transfer hardness from F p \mathbb{F}_p F p to F q \mathbb{F}_q F q with q = p a q=p^a q = p a , we view the same generator matrix over F q \mathbb{F}_q F q . The following lemma shows that this preserves the minimum distance and hence both YES and NO instances of MDP.
Lemma 4.5. Let q = p a q=p^{a} q = p a , where p p p is prime and a ≥ 1 a\ge1 a ≥ 1 is an integer, and let G \mathbf{G} G be a matrix over F p \mathbb{F}_{p} F p . The code generated by the columns of G \mathbf{G} G has the same minimum distance whether the linear combinations are taken over F p \mathbb{F}_{p} F p or over F q \mathbb{F}_{q} F q .
Proof. Allowing coefficients from F q \mathbb{F}_{q} F q cannot increase the minimum distance. Indeed, every linear combination of the columns of G \mathbf{G} G with coefficients in F p \mathbb{F}_{p} F p is also one with coefficients in F q \mathbb{F}_{q} F q . To prove the reverse inequality, we show that every nonzero codeword over F q \mathbb{F}_{q} F q gives a nonzero codeword over F p \mathbb{F}_{p} F p of no greater weight. Express a nonzero codeword over F q \mathbb{F}_{q} F q as a linear combination of the columns of G \mathbf{G} G . Expand the coefficients of this linear combination in an F p \mathbb{F}_{p} F p -basis of F q \mathbb{F}_{q} F q . Since G \mathbf{G} G has entries in F p \mathbb{F}_{p} F p , collecting the terms for each basis element gives a codeword over F p \mathbb{F}_{p} F p . At least one of these codewords is nonzero, since the original codeword is nonzero. If a coordinate of the original codeword is zero, linear independence of the basis implies that the same coordinate is zero in each of these codewords. Thus each has support contained in that of the original codeword, and a nonzero one has no greater weight. This proves the reverse inequality. If G \mathbf{G} G generates the zero code, it does so over both fields, and both minimum distances are + ∞ +\infty + ∞ by our convention.
To complete the proof of Theorem 1.3 , we use tensor powers to obtain hardness for every constant approximation factor. This step uses the fact that the minimum distance of a tensor product of two nonzero linear codes is the product of their minimum distances.
Proof of Theorem 1.3 . We first establish hardness for the factor 4 p / ( 4 p − 1 ) 4p/(4p-1) 4 p / ( 4 p − 1 ) over the fixed field F q \mathbb{F}_{q} F q , where q = p a q=p^{a} q = p a and p p p is prime. By Theorems 2.7 and 4.4 , the problem 4 p / ( 4 p − 1 ) 4p/(4p-1) 4 p / ( 4 p − 1 ) -GapMDPp _p p is W[1]-hard under deterministic FPT many-one reductions. By Lemma 4.5 , viewing the same generator matrix over F q \mathbb{F}_{q} F q preserves the minimum distance. This step is deterministic, takes polynomial time, and leaves the parameter unchanged. Thus the same hardness result holds over F q \mathbb{F}_{q} F q .
We next prove the formula for the minimum distance of a tensor product. View a nonzero codeword in the tensor product of two nonzero linear codes as a matrix whose columns belong to the first code and whose rows belong to the second. At least one column is nonzero, so the number of nonzero rows is at least the minimum distance of the first code. Each nonzero row has weight at least the minimum distance of the second code. The total weight is therefore at least the product of the two minimum distances. For the reverse inequality, choose a codeword of minimum weight from each code and take their tensor product. Its weight is exactly the product of the two minimum distances.
We now construct a reduction to γ \gamma γ -GapMDPq _q q for any fixed γ ≥ 1 \gamma\ge1 γ ≥ 1 . Since 4 p / ( 4 p − 1 ) > 1 4p/(4p-1)>1 4 p / ( 4 p − 1 ) > 1 , we can choose a positive integer ℓ \ell ℓ such that
( 4 p 4 p − 1 ) ℓ ≥ γ . \left(\frac{4p}{4p-1}\right)^{\ell}\ge\gamma. ( 4 p − 1 4 p ) ℓ ≥ γ .
Map an instance ( G , k ) (\mathbf{G},k) ( G , k ) of 4 p 4 p − 1 \frac{4p}{4p-1} 4 p − 1 4 p -GapMDPq _q q to ( G ⊗ ℓ , k ℓ ) (\mathbf{G}^{\otimes\ell},k^{\ell}) ( G ⊗ ℓ , k ℓ ) . We show that this map preserves both YES and NO instances. Repeatedly applying the formula for the minimum distance of a tensor product shows that, for a YES instance,
λ ( C ( G ⊗ ℓ ) ) = λ ( C ( G ) ) ℓ ≤ k ℓ . \lambda(\mathcal{C}(\mathbf{G}^{\otimes\ell}))=\lambda(\mathcal{C}(\mathbf{G}))^{\ell}\le k^{\ell}. λ ( C ( G ⊗ ℓ )) = λ ( C ( G ) ) ℓ ≤ k ℓ .
For a NO instance whose code is nonzero, we have
λ ( C ( G ⊗ ℓ ) ) = λ ( C ( G ) ) ℓ > ( 4 p 4 p − 1 ) ℓ k ℓ ≥ γ k ℓ . \lambda(\mathcal{C}(\mathbf{G}^{\otimes\ell}))=\lambda(\mathcal{C}(\mathbf{G}))^{\ell}>\left(\frac{4p}{4p-1}\right)^{\ell}k^{\ell}\ge\gamma k^{\ell}. λ ( C ( G ⊗ ℓ )) = λ ( C ( G ) ) ℓ > ( 4 p − 1 4 p ) ℓ k ℓ ≥ γ k ℓ .
A zero input code remains zero and is therefore also mapped to a NO instance. We finally check the running time and the output parameter. If G G G has m m m rows and n n n columns, then G ⊗ ℓ G^{\otimes\ell} G ⊗ ℓ has m ℓ m^\ell m ℓ rows and n ℓ n^\ell n ℓ columns. Since ℓ \ell ℓ depends only on the fixed constants p p p and γ \gamma γ , the output matrix and parameter can be computed deterministically in polynomial time. The new parameter is k ℓ k^\ell k ℓ , which depends only on k k k . Combining this reduction with the hardness result established above proves the theorem.
AI Methodology
The deterministic constructions of locally dense codes and locally dense lattices were discovered by GPT-5.5 in response to prompts based on ideas for obtaining such constructions, building on the results in § 4.1 and § 5.1 . Initially, the constructions and their proofs relied on complex concepts from algebraic geometry. The authors subsequently obtained simpler constructions and proofs with the assistance of GPT-5.6 and GPT-6. The authors verified the correctness and originality of all content, including references.
W [ 1 ] W[1] W [ 1 ] -hardness of SVP for any constant approximation factor
In this section, we show that SVP is W [ 1 ] W[1] W [ 1 ] -hard to approximate within every constant factor for every p ≥ 1 p \ge1 p ≥ 1 . We reduce from the Maximum Likelihood Decoding Problem over a prime field, in two steps. First, we embed an MLD instance into a lattice using the block construction of Theorem 3.2 . This produces a gap of roughly 2 between YES and NO instances, together with a lower bound on the minimum distance of the lattice modulo the prime. Second, we amplify the gap by taking tensor powers, following Wan [Wan26a].
MLD is the parity-check formulation of NCP. For p > 1 p > 1 p > 1 , Bennett, Cheraghchi, Guruswami, and Ribeiro [7 ] use a randomized reduction from NCP over F 2 \mathbb{F}_2 F 2 to SVP in the ℓ p \ell_p ℓ p norm and then take tensor powers to obtain hardness for every constant approximation factor. In the following definition, we additionally require that a YES instance has a binary solution.
Definition A.1 (γ \gamma γ -GapMLDq _q q , [BBE+21]). For γ ≥ 1 \gamma\ge1 γ ≥ 1 and a prime q q q , the parameterized promise problem γ \gamma γ -approximate Maximum Likelihood Decoding Problem (MLD) over F q \mathbb{F}_q F q (γ \gamma γ -GapMLDq _q q ) is defined as follows. Instances are tuples ( M , t , k ) (M,t,k) ( M , t , k ) , where M ∈ F q r × m M \in\mathbb{F}_q^{r \times m} M ∈ F q r × m is a parity-check matrix of ker M \ker M ker M , t ∈ F q r t \in\mathbb{F}_q^r t ∈ F q r is a target vector, and k ∈ Z > 0 k \in\mathbb{Z}_{>0} k ∈ Z > 0 is a distance parameter such that
( M , t , k ) (M,t,k) ( M , t , k ) is a YES instance if there exists x ∈ { 0 , 1 } m x \in\{0,1\}^m x ∈ { 0 , 1 } m such that M x = t Mx=t M x = t and ∥ x ∥ 0 ≤ k \lVert x\rVert_0 \le k ∥ x ∥ 0 ≤ k ;
( M , t , k ) (M,t,k) ( M , t , k ) is a NO instance if ∥ x ∥ 0 > γ k \lVert x\rVert_0 > \gamma k ∥ x ∥ 0 > γ k for all x ∈ F q m x \in\mathbb{F}_q^m x ∈ F q m with M x = t Mx=t M x = t .
The parameter of interest is k k k .
Theorem A.2 ([BBE+21, Theorems 4.2, 4.9, and 5.4, adapted]). Fix a constant γ ≥ 1 \gamma\ge1 γ ≥ 1 , and let k ↦ q ( k ) k \mapsto q(k) k ↦ q ( k ) be any computable function whose values are prime. Then γ \gamma γ -GapMLDq ( k ) _{q(k)} q ( k ) is W [ 1 ] W[1] W [ 1 ] -hard under deterministic FPT many-one reductions.
The reductions in [BBE+21] produce YES instances with binary solutions. Their output parameter is determined before the field is chosen, so the prime may be any computable function of this parameter without affecting the FPT running time.
In our reduction, the prime q q q is fixed in advance as a function of the parameter k k k . The construction in Theorem 3.4, however, chooses a prime that grows with m m m . We therefore index the coordinates of the Reed–Solomon lattice by an extension field of F q \mathbb{F}_q F q .
Theorem A.3. Let m m m , h ≥ 1 h \ge1 h ≥ 1 and k ≥ 2 k \ge2 k ≥ 2 be integers, and let q > 2 k q > 2k q > 2 k be a prime. There is a deterministic algorithm that, given m , h , k , q m,h,k,q m , h , k , q , runs in time f ( q + h + k ) ⋅ ( m + 1 ) O ( 1 ) f(q+h+k)\cdot(m+1)^{O(1)} f ( q + h + k ) ⋅ ( m + 1 ) O ( 1 ) for a computable function f f f and outputs a matrix H ∈ F q r × N \mathbf{H}\in\mathbb{F}_q^{r\times N} H ∈ F q r × N , a vector s ∈ Z N \mathbf{s}\in\mathbb{Z}^N s ∈ Z N , and an ordered list S S S of m m m distinct coordinates. The output satisfies the following conditions, where L = { v ∈ Z N : H ( v m o d q ) = 0 } L=\{\mathbf{v}\in\mathbb{Z}^N:\mathbf{H}(\mathbf{v}\bmod q)=\mathbf{0}\} L = { v ∈ Z N : H ( v mod q ) = 0 } .
(i) λ 1 ( 1 ) ( L ) ≥ 2 k \lambda_1^{(1)}(L)\ge2k λ 1 ( 1 ) ( L ) ≥ 2 k and λ ( L m o d q ) ≥ k + 1 \lambda(L\bmod q)\ge k+1 λ ( L mod q ) ≥ k + 1 .
(ii) s ∣ S = 0 \mathbf{s}|_S=\mathbf{0} s ∣ S = 0 .
(iii) For every u ∈ Z m \mathbf{u}\in\mathbb{Z}^m u ∈ Z m with ∥ u ∥ 0 ≤ h \|\mathbf{u}\|_0\le h ∥ u ∥ 0 ≤ h , there exists w ∈ L − s \mathbf{w}\in L-\mathbf{s} w ∈ L − s with w ∣ S = u \mathbf{w}|_S=\mathbf{u} w ∣ S = u such that
∥ w ∥ p p = k − 1 + 2 ∥ u ∥ p p \|\mathbf{w}\|_p^p=k-1+2\|\mathbf{u}\|_p^p ∥ w ∥ p p = k − 1 + 2∥ u ∥ p p for every real p ≥ 1 p\ge1 p ≥ 1 .
The output of Theorem 3.4 also satisfies (i)–(iii).
Proof. Let T T T be the integer defined in Equation (8) with L L L replaced by k − 1 k-1 k − 1 and D D D replaced by 2 2 2 . Since the maximum in Equation (8) contains 2 k > 2 2k>2 2 k > 2 , the integer T T T depends only on m m m , h h h , and k k k . For the same reason, T T T equals the integer used in the proof of Theorem 3.4 whenever D p < 2 k D^p<2k D p < 2 k , since then D ≤ D p < 2 k D\le D^p<2k D ≤ D p < 2 k .
We first describe the construction. Let a ≥ 1 a\ge1 a ≥ 1 be the least integer such that Q : = q a > T Q:=q^a>T Q := q a > T , and set N = Q N=Q N = Q . Set L : = L Q , k L:=L_{Q,k} L := L Q , k as defined in Equation (6) , with coordinates indexed by F Q \mathbb{F}_Q F Q . We construct a parity-check matrix H \mathbf{H} H for L m o d q L\bmod q L mod q over F q \mathbb{F}_q F q as follows. Fix an F q \mathbb{F}_q F q -basis of F Q \mathbb{F}_Q F Q and replace each row ( z j ) z ∈ F Q (z^j)_{z\in\mathbb{F}_Q} ( z j ) z ∈ F Q , for 0 ≤ j < k 0\le j<k 0 ≤ j < k , by the a a a rows of its coordinates in this basis. Here z 0 = 1 z^0=1 z 0 = 1 for every z ∈ F Q z\in\mathbb{F}_Q z ∈ F Q . The resulting matrix H \mathbf{H} H has k a ka k a rows and N N N columns. By Equation (6) , an integer vector v \mathbf{v} v belongs to L L L if and only if H ( v m o d q ) = 0 \mathbf{H}(\mathbf{v}\bmod q)=\mathbf{0} H ( v mod q ) = 0 . Since Q > T > m + k − 1 Q>T>m+k-1 Q > T > m + k − 1 , we can choose distinct elements y 1 , … , y k − 1 , x 1 , … , x m ∈ F Q y_1,\ldots,y_{k-1},x_1,\ldots,x_m\in\mathbb{F}_Q y 1 , … , y k − 1 , x 1 , … , x m ∈ F Q in a fixed enumeration of F Q \mathbb{F}_Q F Q . Set
s = − ∑ ℓ = 1 k − 1 e y ℓ , S = ( x 1 , … , x m ) . \mathbf{s}=-\sum_{\ell=1}^{k-1}\mathbf{e}_{y_\ell},\qquad S=(x_1,\ldots,x_m). s = − ℓ = 1 ∑ k − 1 e y ℓ , S = ( x 1 , … , x m ) .
The algorithm outputs H \mathbf{H} H , s \mathbf{s} s , and S S S .
Conditions (i) and (ii) follow directly from the construction. Condition (i) is Lemma 3.3 applied to Q = q a Q=q^a Q = q a , whose hypotheses hold because k ≥ 2 k\ge2 k ≥ 2 and q > 2 k q>2k q > 2 k . Condition (ii) holds because the elements y ℓ y_\ell y ℓ and x i x_i x i are distinct.
We now prove condition (iii). Fix u ∈ Z m \mathbf{u}\in\mathbb{Z}^m u ∈ Z m with ∥ u ∥ 0 ≤ h \|\mathbf{u}\|_0\le h ∥ u ∥ 0 ≤ h , and put I = { i ∈ [ m ] : u i ≠ 0 } I=\{i\in[m]:u_i\ne0\} I = { i ∈ [ m ] : u i = 0 } . We construct w ∈ L − s \mathbf{w}\in L-\mathbf{s} w ∈ L − s with w ∣ S = u \mathbf{w}|_S=\mathbf{u} w ∣ S = u whose nonzero entries are exactly k − 1 k-1 k − 1 entries equal to 1 1 1 together with u i u_i u i and − u i -u_i − u i for each i ∈ I i\in I i ∈ I . Such a vector satisfies ∥ w ∥ p p = k − 1 + 2 ∑ i ∈ I ∣ u i ∣ p = k − 1 + 2 ∥ u ∥ p p \|\mathbf{w}\|_p^p=k-1+2\sum_{i\in I}|u_i|^p=k-1+2\|\mathbf{u}\|_p^p ∥ w ∥ p p = k − 1 + 2 ∑ i ∈ I ∣ u i ∣ p = k − 1 + 2∥ u ∥ p p for every real p ≥ 1 p\ge1 p ≥ 1 . If I = ∅ I=\varnothing I = ∅ , then w = − s \mathbf{w}=-\mathbf{s} w = − s has the required form.
Suppose that I ≠ ∅ I\ne\varnothing I = ∅ . We repeat the argument in the proof of Theorem 3.4 with F Q \mathbb{F}_Q F Q in place of F q \mathbb{F}_q F q and k − 1 k-1 k − 1 in place of L L L . For z 1 , … , z k − 1 , τ ∈ F Q z_1,\ldots,z_{k-1},\tau\in\mathbb{F}_Q z 1 , … , z k − 1 , τ ∈ F Q , define w \mathbf{w} w by Equation (9) . The computation in that proof shows that w ∈ L − s \mathbf{w}\in L-\mathbf{s} w ∈ L − s if and only if ( z 1 , … , z k − 1 , τ ) (z_1,\ldots,z_{k-1},\tau) ( z 1 , … , z k − 1 , τ ) satisfies Equation (10) over F Q \mathbb{F}_Q F Q . Define g g g by Equation (11) over F Q \mathbb{F}_Q F Q . By the argument of Claim 2, if g ( z 1 , … , z k − 1 , τ ) ≠ 0 g(z_1,\ldots,z_{k-1},\tau)\ne0 g ( z 1 , … , z k − 1 , τ ) = 0 , then all coordinate indices in Equation (9) are pairwise distinct and the indices z ℓ z_\ell z ℓ and x i + τ x_i+\tau x i + τ lie outside S S S . In this case, w ∣ S = u \mathbf{w}|_S=\mathbf{u} w ∣ S = u and the nonzero entries of w \mathbf{w} w are as described above.
It remains to find a point satisfying Equation (10) at which g g g is nonzero. We apply Lemma 2.19 over F Q \mathbb{F}_Q F Q to the k − 1 k-1 k − 1 left sides of Equation (10) followed by g g g , exactly as in the proof of Theorem 3.4 . The point ( y 1 , … , y k − 1 , 0 ) (y_1,\ldots,y_{k-1},0) ( y 1 , … , y k − 1 , 0 ) is a common zero of these k ≥ 2 k\ge2 k ≥ 2 polynomials. The Jacobian matrix is
::: invertible at this point, because F Q \mathbb{F}_{Q} F Q has characteristic q > k − 1 q > k - 1 q > k − 1 and the elements y ℓ y_{\ell} y ℓ and x i x_{i} x i are distinct. The product of the degrees of the first k − 1 k - 1 k − 1 polynomials is Δ = ( k − 1 ) ! \Delta= (k - 1)! Δ = ( k − 1 )! . The bound on deg g \deg g deg g in that proof uses only ∣ I ∣ ≤ h |I| \le h ∣ I ∣ ≤ h , so it holds here as well. Since Q > T Q > T Q > T , we therefore have Q > 9 Δ 5 Q > 9\Delta^{5} Q > 9 Δ 5 and Q > 9 Δ deg g Q > 9\Delta\deg g Q > 9Δ deg g . Lemma 2.19 gives the required point.
We next show that the output of Theorem 3.4 also satisfies conditions (i)--(iii). The construction there chooses a prime q q q with T < q < 2 T T < q < 2T T < q < 2 T . For this q q q , the least a a a with q a > T q^{a} > T q a > T is a = 1 a = 1 a = 1 . The construction then defines H \mathbf{H} H , s s s , and S S S exactly as above. Thus its output coincides with the output of our algorithm on input ( m , h , k , q ) (m,h,k,q) ( m , h , k , q ) .
We finally bound the running time. By Equation (8) , we have T ≤ f 0 ( h + k ) ( m + 1 ) T \le f_{0}(h + k)(m + 1) T ≤ f 0 ( h + k ) ( m + 1 ) for a computable function f 0 f_{0} f 0 . The minimality of a a a gives q a − 1 ≤ T q^{a-1} \le T q a − 1 ≤ T , so Q ≤ q T Q \le qT Q ≤ q T . We construct F Q = F q [ X ] / ( g 0 ) \mathbb{F}_{Q} = \mathbb{F}_{q}[X]/(g_{0}) F Q = F q [ X ] / ( g 0 ) for a monic irreducible g 0 ∈ F q [ X ] g_{0} \in\mathbb{F}_{q}[X] g 0 ∈ F q [ X ] of degree a a a by the search in the proof of Lemma 2.9 . Here q q q is part of the input, but each division in that search takes time polynomial in a a a and log q \log q log q , so the search takes time polynomial in Q Q Q . Using the F q \mathbb{F}_{q} F q -basis 1 , X , … , X a − 1 1,X,\ldots,X^{a-1} 1 , X , … , X a − 1 , we compute all entries of H \mathbf{H} H in time polynomial in Q Q Q and k k k . Choosing s s s and S S S also takes time polynomial in Q Q Q . The point given by Lemma 2.19 is used only in the analysis and is not computed. Thus the running time and the output size are polynomial in Q + k ≤ q f 0 ( h + k ) ( m + 1 ) + k Q + k \le qf_{0}(h + k)(m + 1) + k Q + k ≤ q f 0 ( h + k ) ( m + 1 ) + k , and hence bounded by f ( q + h + k ) ( m + 1 ) O ( 1 ) f(q + h + k)(m + 1)^{O(1)} f ( q + h + k ) ( m + 1 ) O ( 1 ) for a computable function f f f .
In particular, for every real p ≥ 1 p \ge1 p ≥ 1 and all integers d ≥ 1 d \ge1 d ≥ 1 and D ≥ 2 D \ge2 D ≥ 2 with d p ≤ h d^{p} \le h d p ≤ h and D p < 2 k D^{p} < 2k D p < 2 k , the tuple ( q , H , s , S ) (q,\mathbf{H},s,S) ( q , H , s , S ) is a locally dense lattice with parameters ( p , m , d , D , k − 1 + 2 h ) (p,m,d,D,k - 1 + 2h) ( p , m , d , D , k − 1 + 2 h ) . Indeed, ∥ u ∥ p ≤ d \lVert u\rVert_{p} \le d ∥ u ∥ p ≤ d implies ∥ u ∥ 0 ≤ ∥ u ∥ p p ≤ h \lVert u\rVert_{0} \le\lVert u\rVert_{p}^{p} \le h ∥ u ∥ 0 ≤ ∥ u ∥ p p ≤ h , and ∥ v ∥ p ≥ ∥ v ∥ 1 ≥ 2 k > D p \lVert v\rVert_{p} \ge\lVert v\rVert_{1} \ge2k > D^{p} ∥ v ∥ p ≥ ∥ v ∥ 1 ≥ 2 k > D p for every nonzero v ∈ L v \in L v ∈ L .
We now turn to tensor products. For integer lattices U = L ( B 1 ) U = \mathcal{L}(\mathbf{B}_{1}) U = L ( B 1 ) and V = L ( B 2 ) V = \mathcal{L}(\mathbf{B}_{2}) V = L ( B 2 ) , the tensor product U ⊗ V U \otimes V U ⊗ V is the lattice generated by B 1 ⊗ B 2 \mathbf{B}_{1} \otimes\mathbf{B}_{2} B 1 ⊗ B 2 . Equivalently, it is the lattice generated by the vectors u ⊗ v u \otimes v u ⊗ v with u ∈ U u \in U u ∈ U and v ∈ V v \in V v ∈ V , so it does not depend on the choice of bases. We write U ⊗ j U^{\otimes j} U ⊗ j for the tensor product of j j j copies of U U U . If the columns of B 1 \mathbf{B}_{1} B 1 and B 2 \mathbf{B}_{2} B 2 are linearly independent, then so are those of B 1 ⊗ B 2 \mathbf{B}_{1} \otimes\mathbf{B}_{2} B 1 ⊗ B 2 . We use the following two lemmas from the second version of [Wan26a].
Lemma A.4 ([Wan26a], Lemma 2.1). Let C 1 C_{1} C 1 and C 2 C_{2} C 2 be linear codes over F q \mathbb{F}_{q} F q . If λ ( C 1 ) ≥ D 1 \lambda(C_{1}) \ge D_{1} λ ( C 1 ) ≥ D 1 and λ ( C 2 ) ≥ D 2 \lambda(C_{2}) \ge D_{2} λ ( C 2 ) ≥ D 2 , then λ ( C 1 ⊗ C 2 ) ≥ D 1 D 2 \lambda(C_{1} \otimes C_{2}) \ge D_{1}D_{2} λ ( C 1 ⊗ C 2 ) ≥ D 1 D 2 .
Lemma A.5 ([Wan26a], Lemma 4.2). Let U U U and V V V be integer lattices, and write a nonzero vector of U ⊗ V U \otimes V U ⊗ V as a matrix X X X with rows indexed by the coordinates of U U U and columns indexed by the coordinates of V V V . If X X X has rank r r r over the reals, there are linearly independent vectors u 1 , … , u r ∈ U u_{1},\ldots,u_{r} \in U u 1 , … , u r ∈ U and linearly independent vectors v 1 , … , v r ∈ V v_{1},\ldots,v_{r} \in V v 1 , … , v r ∈ V such that
X = ∑ i = 1 r u i v i T . X = \sum_{i=1}^{r} u_{i}v_{i}^{\mathsf{T}}. X = i = 1 ∑ r u i v i T .
The following amplification lemma improves the argument of [Wan26a], Section 5 to the ℓ 1 \ell_{1} ℓ 1 norm. Since ∥ z ∥ p ≥ ∥ z ∥ 1 \lVert z\rVert_{p} \ge\lVert z\rVert_{1} ∥ z ∥ p ≥ ∥ z ∥ 1 for every integer vector z z z , the ℓ 1 \ell_{1} ℓ 1 bound yields a bound for every p ≥ 1 p \ge1 p ≥ 1 .
Lemma A.6. For every integer b ≥ 4 b \ge4 b ≥ 4 , one can compute an even integer T ≥ 2 T \ge2 T ≥ 2 such that the following holds. Let L L L be a nonzero integer lattice, let K ≥ 2 K \ge2 K ≥ 2 be an integer, and let q > 2 ( b K T ) 2 q > 2(bKT)^{2} q > 2 ( b K T ) 2 be prime. If λ 1 ( 1 ) ( L ) ≥ 2 K \lambda_{1}^{(1)}(L) \ge2K λ 1 ( 1 ) ( L ) ≥ 2 K and λ ( L m o d q ) ≥ K \lambda(L \bmod q) \ge K λ ( L mod q ) ≥ K , then for every real p ≥ 1 p \ge1 p ≥ 1 ,
( λ 1 ( p ) ( L ⊗ T ) ) p ≥ b K T . \left(\lambda_{1}^{(p)}\left(L^{\otimes T}\right)\right)^{p} \ge bK^{T}. ( λ 1 ( p ) ( L ⊗ T ) ) p ≥ b K T .
Proof. Let η = 1 / ( 2 ( 8 b + 1 ) 2 ) \eta= 1/(2(8b+1)^2) η = 1/ ( 2 ( 8 b + 1 ) 2 ) , and let T T T be the least even integer T ≥ 2 T \ge2 T ≥ 2 such that 2 ( 1 + η ) T − 1 ≥ b 2(1+\eta)^{T-1} \ge b 2 ( 1 + η ) T − 1 ≥ b . For 1 ≤ j ≤ T 1 \le j \le T 1 ≤ j ≤ T , let a j = min { b , 2 ( 1 + η ) j − 1 } a_j = \min\{b, 2(1+\eta)^{j-1}\} a j = min { b , 2 ( 1 + η ) j − 1 } . Then a 1 = 2 a_1 = 2 a 1 = 2 , a T = b a_T = b a T = b , and a j + 1 ≤ ( 1 + η ) a j ≤ 2 a j a_{j+1} \le(1+\eta)a_j \le2a_j a j + 1 ≤ ( 1 + η ) a j ≤ 2 a j for 1 ≤ j < T 1 \le j < T 1 ≤ j < T . Since ∥ z ∥ p p ≥ ∥ z ∥ 1 \lVert z\rVert_p^p \ge\lVert z\rVert_1 ∥ z ∥ p p ≥ ∥ z ∥ 1 for every integer vector z z z , it suffices to prove that
λ 1 ( 1 ) ( L ⊗ j ) ≥ a j K j ( 1 ≤ j ≤ T ) , (20) \lambda_1^{(1)}(L^{\otimes j}) \ge a_jK^j \qquad(1 \le j \le T), \tag*{(20)} λ 1 ( 1 ) ( L ⊗ j ) ≥ a j K j ( 1 ≤ j ≤ T ) , (20)
because the case j = T j=T j = T is the claim. We proceed by induction on j j j . The case j = 1 j=1 j = 1 is the assumption λ 1 ( 1 ) ( L ) ≥ 2 K \lambda_1^{(1)}(L) \ge2K λ 1 ( 1 ) ( L ) ≥ 2 K .
Before the induction step, we relate the codes obtained from L L L and its tensor powers. Let B \mathbf{B} B be a basis of L L L , and let C = L m o d q \mathcal{C}=L\bmod q C = L mod q , which is the code generated by B m o d q \mathbf{B}\bmod q B mod q . Since L ⊗ j L^{\otimes j} L ⊗ j is generated by B ⊗ j \mathbf{B}^{\otimes j} B ⊗ j and B ⊗ j m o d q = ( B m o d q ) ⊗ j \mathbf{B}^{\otimes j}\bmod q=(\mathbf{B}\bmod q)^{\otimes j} B ⊗ j mod q = ( B mod q ) ⊗ j , we have
L ⊗ j m o d q = C ⊗ j . L^{\otimes j}\bmod q=\mathcal{C}^{\otimes j}. L ⊗ j mod q = C ⊗ j .
Since λ ( C ) ≥ K \lambda(\mathcal{C})\ge K λ ( C ) ≥ K , repeated application of Lemma A.4 gives λ ( C ⊗ j ) ≥ K j \lambda(\mathcal{C}^{\otimes j})\ge K^j λ ( C ⊗ j ) ≥ K j .
Fix 1 ≤ j < T 1\le j<T 1 ≤ j < T and assume Equation (20) for j j j . Suppose for contradiction that some nonzero x ∈ L ⊗ ( j + 1 ) = L ⊗ L ⊗ j x\in L^{\otimes(j+1)}=L\otimes L^{\otimes j} x ∈ L ⊗ ( j + 1 ) = L ⊗ L ⊗ j satisfies ∥ x ∥ 1 < a j + 1 K j + 1 \lVert x\rVert_1<a_{j+1}K^{j+1} ∥ x ∥ 1 < a j + 1 K j + 1 . Write L ⊆ Z N L\subseteq\mathbb{Z}^N L ⊆ Z N , and view x x x as an N × N j N\times N^j N × N j matrix X \mathbf{X} X whose rows are indexed by the coordinates of the first factor L L L and whose columns are indexed by the coordinates of L ⊗ j L^{\otimes j} L ⊗ j . By the definition of tensor product, x x x is an integer combination of tensors of the form u v T uv^{\mathsf T} u v T , where u ∈ L u\in L u ∈ L and v ∈ L ⊗ j v\in L^{\otimes j} v ∈ L ⊗ j , therefore every column of X \mathbf{X} X lies in L L L and the transpose of every row lies in L ⊗ j L^{\otimes j} L ⊗ j . Writing ∥ X ∥ 1 \lVert\mathbf{X}\rVert_1 ∥ X ∥ 1 for the sum of the absolute values of the entries, we have
∥ X ∥ 1 = ∥ x ∥ 1 < a j + 1 K j + 1 ≤ b K j + 1 . (21) \lVert\mathbf{X}\rVert_1=\lVert x\rVert_1<a_{j+1}K^{j+1}\le bK^{j+1}. \tag*{(21)} ∥ X ∥ 1 = ∥ x ∥ 1 < a j + 1 K j + 1 ≤ b K j + 1 . (21)
We consider the following two cases.
Suppose first that X \mathbf{X} X has rank one over the reals. By Lemma A.5 , we have X = u v T \mathbf{X}=uv^{\mathsf T} X = u v T for nonzero vectors u ∈ L u\in L u ∈ L and v ∈ L ⊗ j v\in L^{\otimes j} v ∈ L ⊗ j . The induction hypothesis then gives
∥ X ∥ 1 = ∥ u ∥ 1 ∥ v ∥ 1 ≥ 2 K ⋅ a j K j ≥ a j + 1 K j + 1 , \lVert\mathbf{X}\rVert_1=\lVert u\rVert_1\lVert v\rVert_1\ge2K\cdot a_jK^j\ge a_{j+1}K^{j+1}, ∥ X ∥ 1 = ∥ u ∥ 1 ∥ v ∥ 1 ≥ 2 K ⋅ a j K j ≥ a j + 1 K j + 1 ,
contrary to Equation (21) .
Suppose next that X \mathbf{X} X has rank at least two over the reals. We first find two short columns of X \mathbf{X} X that are linearly independent modulo q q q . By its rank, some 2 × 2 2\times2 2 × 2 minor of X \mathbf{X} X has a nonzero integer determinant Δ \Delta Δ . Every entry of X \mathbf{X} X has absolute value at most ∥ X ∥ 1 \lVert\mathbf{X}\rVert_1 ∥ X ∥ 1 , so Equation (21) and j + 1 ≤ T j+1\le T j + 1 ≤ T give
0 < ∣ Δ ∣ ≤ 2 ∥ X ∥ 1 2 < 2 ( b K j + 1 ) 2 ≤ 2 ( b K T ) 2 < q . 0<|\Delta|\le2\lVert\mathbf{X}\rVert_1^2<2(bK^{j+1})^2\le2(bK^T)^2<q. 0 < ∣Δ∣ ≤ 2 ∥ X ∥ 1 2 < 2 ( b K j + 1 ) 2 ≤ 2 ( b K T ) 2 < q .
Hence Δ ≢ 0 ( m o d q ) \Delta\not\equiv0\pmod q Δ ≡ 0 ( mod q ) , and the two rows of X \mathbf{X} X through this minor are linearly independent modulo q q q . Call a column of X \mathbf{X} X long if its ℓ 1 \ell_1 ℓ 1 norm exceeds b K bK b K . By Equation (21) , fewer than K j K^j K j columns are long. Note that the two rows remain linearly independent modulo q q q after the long columns are deleted. Otherwise, some F q \mathbb{F}_q F q -linear combination of the two rows modulo q q q is nonzero but vanishes on every column that is not long, so it has fewer than K j K^j K j nonzero entries. This contradicts with the minimum distance of L ⊗ j m o d q = C ⊗ j L^{\otimes j}\bmod q=\mathcal{C}^{\otimes j} L ⊗ j mod q = C ⊗ j , which is λ ( C ⊗ j ) ≥ K j \lambda(\mathcal{C}^{\otimes j})\ge K^j λ ( C ⊗ j ) ≥ K j . Thus the columns that are not long span a space of dimension at least two modulo q q q . We obtain two columns u , v ∈ L u,v\in L u , v ∈ L of X \mathbf{X} X that are linearly independent modulo q q q and satisfy ∥ u ∥ 1 , ∥ v ∥ 1 ≤ b K \lVert u\rVert_1,\lVert v\rVert_1\le bK ∥ u ∥ 1 , ∥ v ∥ 1 ≤ b K .
We next show that the common support of u u u and v v v is large. Let J = { i ∈ [ N ] : ( u i , v i ) ≠ ( 0 , 0 ) } J=\{i\in[N]:(u_i,v_i)\ne(0,0)\} J = { i ∈ [ N ] : ( u i , v i ) = ( 0 , 0 )} . Since u m o d q u\bmod q u mod q is a nonzero codeword of C \mathcal{C} C supported in J J J , we have ∣ J ∣ ≥ K |J|\ge K ∣ J ∣ ≥ K . Let t t t be the number of indices i ∈ J i\in J i ∈ J with ∣ u i ∣ > 4 b |u_i|>4b ∣ u i ∣ > 4 b or ∣ v i ∣ > 4 b |v_i|>4b ∣ v i ∣ > 4 b . Each such index contributes at least 4 b + 1 4b+1 4 b + 1 to ∥ u ∥ 1 + ∥ v ∥ 1 ≤ 2 b K \lVert u\rVert_1+\lVert v\rVert_1\le2bK ∥ u ∥ 1 + ∥ v ∥ 1 ≤ 2 b K , so t < K / 2 ≤ ∣ J ∣ / 2 t<K/2\le|J|/2 t < K /2 ≤ ∣ J ∣/2 . At the remaining indices of J J J , the pair ( u i , v i ) (u_i,v_i) ( u i , v i ) is a nonzero integer pair in [ − 4 b , 4 b ] 2 [-4b,4b]^2 [ − 4 b , 4 b ] 2 . There are fewer than ( 8 b + 1 ) 2 (8b+1)^2 ( 8 b + 1 ) 2 such pairs, by an average principle, some pair ( c 1 , c 2 ) ≠ ( 0 , 0 ) (c_1,c_2)\ne(0,0) ( c 1 , c 2 ) = ( 0 , 0 ) occurs at no fewer than ∣ J ∣ / ( 2 ( 8 b + 1 ) 2 ) = η ∣ J ∣ |J|/(2(8b+1)^2)=\eta|J| ∣ J ∣/ ( 2 ( 8 b + 1 ) 2 ) = η ∣ J ∣ indices. Consider the codeword ( c 2 u − c 1 v ) m o d q (c_2u-c_1v)\bmod q ( c 2 u − c 1 v ) mod q of C C C . Since ∣ c 1 ∣ , ∣ c 2 ∣ ≤ 4 b < q |c_1|,|c_2|\le4b<q ∣ c 1 ∣ , ∣ c 2 ∣ ≤ 4 b < q , the pair ( c 1 , c 2 ) (c_1,c_2) ( c 1 , c 2 ) is nonzero modulo q q q , ( c 2 u − c 1 v ) m o d q (c_2u-c_1v)\bmod q ( c 2 u − c 1 v ) mod q is nonzero codeword of C C C by the linear independence of u u u and v v v modulo q q q . It remains zero outside J J J and at every index i i i with ( u i , v i ) = ( c 1 , c 2 ) (u_i,v_i)=(c_1,c_2) ( u i , v i ) = ( c 1 , c 2 ) . Hence
K ≤ ∥ ( c 2 u − c 1 v ) m o d q ∥ 0 ≤ ( 1 − η ) ∣ J ∣ , so ∣ J ∣ ≥ K 1 − η ≥ ( 1 + η ) K . K\le\lVert(c_2u-c_1v)\bmod q\rVert_0\le(1-\eta)|J|,\qquad\text{so}\qquad|J|\ge\frac{K}{1-\eta}\ge(1+\eta)K. K ≤ ∥( c 2 u − c 1 v ) mod q ∥ 0 ≤ ( 1 − η ) ∣ J ∣ , so ∣ J ∣ ≥ 1 − η K ≥ ( 1 + η ) K .
For each i ∈ J i\in J i ∈ J , (the transpose of) row i i i of X \mathbf{X} X is a nonzero vector of L ⊗ j L^{\otimes j} L ⊗ j , Its transpose is a nonzero vector of L ⊗ j L^{\otimes j} L ⊗ j , so it has ℓ 1 \ell_1 ℓ 1 norm at least a j K j a_jK^j a j K j by the induction hypothesis. Summing over i ∈ J i\in J i ∈ J gives
∥ X ∥ 1 ≥ ∣ J ∣ a j K j ≥ ( 1 + η ) a j K j + 1 ≥ a j + 1 K j + 1 , \lVert X\rVert_1\ge|J|a_jK^j\ge(1+\eta)a_jK^{j+1}\ge a_{j+1}K^{j+1}, ∥ X ∥ 1 ≥ ∣ J ∣ a j K j ≥ ( 1 + η ) a j K j + 1 ≥ a j + 1 K j + 1 ,
contrary to Equation (21) . This completes the induction. □
We now give the reduction. It uses the lattice of Theorem A.3 in the block matrix of Theorem 3.2 . In addition, we repeat the last block of rows K + 1 K+1 K + 1 times. A lattice vector that violates the MLD constraints modulo q q q then has at least K + 1 K+1 K + 1 nonzero coordinates modulo q q q , which gives the bound on the minimum distance modulo q q q required in Lemma A.6 .
Theorem A.7. Fix a computable real p ≥ 1 p\ge1 p ≥ 1 and a constant γ ≥ 1 \gamma\ge1 γ ≥ 1 . There are an integer c ≥ 2 c\ge2 c ≥ 2 , a computable function k ↦ q ( k ) k\mapsto q(k) k ↦ q ( k ) whose values are prime, and a deterministic FPT many-one reduction from ( 2 c ) (2c) ( 2 c ) -GapMLDq ( k ) _{q(k)} q ( k ) to γ \gamma γ -GapSVPp _p p . The output distance parameter depends only on the input parameter k k k .
Proof. We first fix the constants. Choose an integer b ≥ 4 b\ge4 b ≥ 4 with b > ( 3 γ ) p b>(3\gamma)^p b > ( 3 γ ) p , and let T T T be the even integer given by Lemma A.6 . Since T T T is fixed and ( 1 + 2 / c ) T → 1 (1+2/c)^T\to1 ( 1 + 2/ c ) T → 1 as c → ∞ c\to\infty c → ∞ , we can choose an integer c ≥ 2 c\ge2 c ≥ 2 such that
( 3 γ ) p ( 1 + 2 / c ) T < b . (22) (3\gamma)^p(1+2/c)^T<b. \tag*{(22)} ( 3 γ ) p ( 1 + 2/ c ) T < b . (22)
Both choices can be made using a fixed integer upper bound on ( 3 γ ) p (3\gamma)^p ( 3 γ ) p . Given k k k , put K = c k K=ck K = c k , and let q ( k ) q(k) q ( k ) be the prime returned by the algorithm in Lemma 2.12 on input 2 ( b K T ) 2 2(bKT)^2 2 ( b K T ) 2 . Thus q ( k ) > 2 ( b K T ) 2 > 2 K q(k)>2(bKT)^2>2K q ( k ) > 2 ( b K T ) 2 > 2 K .
We next construct the output instance. Let ( M , t , k ) (M,t,k) ( M , t , k ) be the input, write q = q ( k ) q=q(k) q = q ( k ) , and let M ∈ F q n × m M\in\mathbb{F}_q^{n\times m} M ∈ F q n × m and t ∈ F q n t\in\mathbb{F}_q^n t ∈ F q n . We may assume m ≥ 1 m\ge1 m ≥ 1 , since adding a zero column to M M M preserves both cases of the promise. Apply the algorithm in Theorem A.3 to ( m , k , K , q ) (m,k,K,q) ( m , k , K , q ) , that is, with h = k h=k h = k and with K K K in place of k k k . This is possible because K ≥ 2 K\ge2 K ≥ 2 and q > 2 K q>2K q > 2 K . Let H H H , s s s , and S S S be its outputs, let N N N be the number of columns of H H H , and put Λ = { v ∈ Z N : H ( v m o d q ) = 0 } \Lambda=\{v\in\mathbb{Z}^N:H(v\bmod q)=0\} Λ = { v ∈ Z N : H ( v mod q ) = 0 } . By conditions (i) and (ii) of that theorem,
λ 1 ( 1 ) ( Λ ) ≥ 2 K , λ ( Λ m o d q ) ≥ K + 1 , s ∣ S = 0. \lambda_1^{(1)}(\Lambda)\ge2K,\qquad\lambda(\Lambda\bmod q)\ge K+1,\qquad s|_S=0. λ 1 ( 1 ) ( Λ ) ≥ 2 K , λ ( Λ mod q ) ≥ K + 1 , s ∣ S = 0.
Use Lemma 2.13 to compute an integer basis A ∈ Z N × N \mathbf{A}\in\mathbb{Z}^{N\times N} A ∈ Z N × N of Λ \Lambda Λ , and let A S \mathbf{A}_S A S consist of the rows of A \mathbf{A} A indexed by S S S , in the specified order. We identify M M M and t t t with their integer lifts with entries in { 0 , … , q − 1 } \{0,\ldots,q-1\} { 0 , … , q − 1 } . Set β = 2 K \beta=2K β = 2 K , let E ∈ Z ( K + 1 ) r × r \mathbf{E}\in\mathbb{Z}^{(K+1)r\times r} E ∈ Z ( K + 1 ) r × r consist of K + 1 K+1 K + 1 copies of I r I_r I r stacked vertically, and form
B ′ = ( A − s 0 0 1 0 β E M A S − β E t β q E ) \mathbf{B}'=
\begin{pmatrix}
\mathbf{A} & -s & 0\\
0 & 1 & 0\\
\beta\mathbf{E}M\mathbf{A}_S & -\beta\mathbf{E}t & \beta q\mathbf{E}
\end{pmatrix} B ′ = A 0 β E M A S − s 1 − β E t 0 0 β q E
The columns of B ′ \mathbf{B}' B ′ are linearly independent. Indeed, in a vanishing linear combination, the second block forces the coefficient of the middle column to be zero. The first block then forces the coefficients of the first N N N columns to be zero, since A \mathbf{A} A is invertible. The remaining coefficients are zero because E \mathbf{E} E has linearly independent columns. Hence ( B ′ ) ⊗ T (\mathbf{B}')^{\otimes T} ( B ′ ) ⊗ T is a basis of L ( B ′ ) ⊗ T \mathcal{L}(\mathbf{B}')^{\otimes T} L ( B ′ ) ⊗ T .
To choose the distance parameter, put R = ( K + 2 k ) T / p R=(K+2k)^{T/p} R = ( K + 2 k ) T / p . Since p p p is computable, we can compute a rational number a a a with ∣ a − R ∣ < 1 / 4 |a-R|<1/4 ∣ a − R ∣ < 1/4 , and we set d ′ = ⌈ a + 1 / 4 ⌉ d'=\lceil a+1/4\rceil d ′ = ⌈ a + 1/4 ⌉ . Since R ≥ 1 R\ge1 R ≥ 1 , this gives
R ≤ d ′ < R + 3 / 2 < 3 R . (23) R \le d' < R+3/2 < 3R. \tag*{(23)} R ≤ d ′ < R + 3/2 < 3 R . (23)
The reduction outputs ( ( B ′ ) ⊗ T , d ′ ) ((\mathbf{B}')^{\otimes T},d') (( B ′ ) ⊗ T , d ′ ) .
We now prove completeness. Suppose that the input is a YES instance, and take x ∈ { 0 , 1 } m \mathbf{x}\in\{0,1\}^{m} x ∈ { 0 , 1 } m with ∥ x ∥ 0 ≤ k \|\mathbf{x}\|_{0}\le k ∥ x ∥ 0 ≤ k and M x = t \mathbf{M}\mathbf{x}=\mathbf{t} Mx = t over F q \mathbb{F}_{q} F q . By condition (iii) of Theorem A.3 , there exists y ∈ Z N \mathbf{y}\in\mathbb{Z}^{N} y ∈ Z N with ( A y − s ) ∣ S = x (\mathbf{A}\mathbf{y}-\mathbf{s})|_{S}=\mathbf{x} ( Ay − s ) ∣ S = x and
∥ A y − s ∥ p p = K − 1 + 2 ∥ x ∥ p p = K − 1 + 2 ∥ x ∥ 0 , \|\mathbf{A}\mathbf{y}-\mathbf{s}\|_{p}^{p}=K-1+2\|\mathbf{x}\|_{p}^{p}=K-1+2\|\mathbf{x}\|_{0}, ∥ Ay − s ∥ p p = K − 1 + 2∥ x ∥ p p = K − 1 + 2∥ x ∥ 0 ,
where the last equality uses x ∈ { 0 , 1 } m \mathbf{x}\in\{0,1\}^{m} x ∈ { 0 , 1 } m . Since s ∣ S = 0 \mathbf{s}|_{S}=0 s ∣ S = 0 , we have A S y = x \mathbf{A}_{S}\mathbf{y}=\mathbf{x} A S y = x over the integers. Since M x ≡ t ( m o d q ) \mathbf{M}\mathbf{x}\equiv\mathbf{t}\pmod q Mx ≡ t ( mod q ) , the vector z = ( t − M x ) / q \mathbf{z}=(\mathbf{t}-\mathbf{M}\mathbf{x})/q z = ( t − Mx ) / q is integral, and
v : = B ′ ( y 1 z ) = ( A y − s 1 0 ) . \mathbf{v}:=\mathbf{B}'\begin{pmatrix}\mathbf{y}\\1\\\mathbf{z}\end{pmatrix}
=\begin{pmatrix}\mathbf{A}\mathbf{y}-\mathbf{s}\\1\\\mathbf{0}\end{pmatrix}. v := B ′ y 1 z = Ay − s 1 0 .
The vector v \mathbf{v} v is nonzero, and ∥ v ∥ p p = 1 + ∥ A y − s ∥ p p = K + 2 ∥ x ∥ 0 ≤ K + 2 k \|\mathbf{v}\|_{p}^{p}=1+\|\mathbf{A}\mathbf{y}-\mathbf{s}\|_{p}^{p}=K+2\|\mathbf{x}\|_{0}\le K+2k ∥ v ∥ p p = 1 + ∥ Ay − s ∥ p p = K + 2∥ x ∥ 0 ≤ K + 2 k . Hence v ⊗ T \mathbf{v}^{\otimes T} v ⊗ T is a nonzero vector of the output lattice with
∥ v ⊗ T ∥ p = ( ∥ v ∥ p ) T ≤ ( K + 2 k ) T / p = R p ≤ ( d ′ ) p . \|\mathbf{v}^{\otimes T}\|_{p}=(\|\mathbf{v}\|_{p})^{T}\le(K+2k)^{T/p}=R^{p}\le(d')^{p}. ∥ v ⊗ T ∥ p = ( ∥ v ∥ p ) T ≤ ( K + 2 k ) T / p = R p ≤ ( d ′ ) p .
Thus the output is a YES instance.
We next prove soundness. Suppose that the input is a NO instance. We verify the two hypotheses of Lemma A.6 for the lattice L ( B ′ ) \mathcal{L}(\mathbf{B}') L ( B ′ ) . Every vector of L ( B ′ ) \mathcal{L}(\mathbf{B}') L ( B ′ ) has the form
\begin{pmatrix}
\mathbf{A}\mathbf{y}-\ell\mathbf{s}\\
\ell\\
\beta\mathbf{E}(\mathbf{M}\mathbf{A}_{S}\mathbf{y}-\ell\mathbf{t}+q\mathbf{z})
\end{pmatrix},
\qquad\mathbf{y}\in\mathbb{Z}^{N},\quad\ell\in\mathbb{Z},\quad\mathbf{z}\in\mathbb{Z}^{r}. \tag*{(24)}\end{pmatrix}
The NO condition controls the first block in the following way. If M A S y = ℓ t \mathbf{M}\mathbf{A}_{S}\mathbf{y}=\ell\mathbf{t} M A S y = ℓ t over F q \mathbb{F}_{q} F q and ℓ ≢ 0 ( m o d q ) \ell\not\equiv0\pmod q ℓ ≡ 0 ( mod q ) , then ℓ − 1 ( A S y m o d q ) \ell^{-1}(\mathbf{A}_{S}\mathbf{y}\bmod q) ℓ − 1 ( A S y mod q ) is a solution of M x = t \mathbf{M}\mathbf{x}=\mathbf{t} Mx = t over F q \mathbb{F}_{q} F q . Since s ∣ S = 0 \mathbf{s}|_{S}=0 s ∣ S = 0 , the NO condition then gives
∥ ( A y − ℓ s ) ∣ S m o d q ∥ 0 = ∥ A S y m o d q ∥ 0 > 2 c k = 2 K . (25) \|(\mathbf{A}\mathbf{y}-\ell\mathbf{s})|_{S}\bmod q\|_{0}=\|\mathbf{A}_{S}\mathbf{y}\bmod q\|_{0}>2ck=2K. \tag*{(25)} ∥ ( Ay − ℓ s ) ∣ S mod q ∥ 0 = ∥ A S y mod q ∥ 0 > 2 c k = 2 K . (25)
We first show that λ 1 ( 1 ) ( L ( B ′ ) ) ≥ 2 K \lambda_{1}^{(1)}(\mathcal{L}(\mathbf{B}'))\ge2K λ 1 ( 1 ) ( L ( B ′ )) ≥ 2 K . Suppose that the vector in Equation (24) has ℓ 1 \ell_{1} ℓ 1 norm less than 2 K 2K 2 K . Every entry of its last block is a multiple of β = 2 K \beta=2K β = 2 K , so that block is zero. Since E \mathbf{E} E has linearly independent columns, we get M A S y − ℓ t + q z = 0 \mathbf{M}\mathbf{A}_{S}\mathbf{y}-\ell\mathbf{t}+q\mathbf{z}=0 M A S y − ℓ t + q z = 0 , and in particular M A S y = ℓ t \mathbf{M}\mathbf{A}_{S}\mathbf{y}=\ell\mathbf{t} M A S y = ℓ t over F q \mathbb{F}_{q} F q . If q ∤ ℓ q\nmid\ell q ∤ ℓ , then Equation (25) gives more than 2 K 2K 2 K nonzero entries in the first block, which is impossible. Thus q ∣ ℓ q\mid\ell q ∣ ℓ , and since ∣ ℓ ∣ < 2 K < q |\ell|<2K<q ∣ ℓ ∣ < 2 K < q , we get ℓ = 0 \ell=0 ℓ = 0 . The first block is then a vector of Λ \Lambda Λ of ℓ 1 \ell_{1} ℓ 1 norm less than 2 K 2K 2 K , so it is zero as well. Hence the vector is zero.
We next show that λ 1 ( L ( B ′ ) m o d q ) ≥ K + 1 \lambda_{1}(\mathcal{L}(\mathbf{B}')\bmod q)\ge K+1 λ 1 ( L ( B ′ ) mod q ) ≥ K + 1 . Suppose that the vector in Equation (24) is nonzero modulo q q q . If M A S y ≠ ℓ t \mathbf{M}\mathbf{A}_{S}\mathbf{y}\ne\ell\mathbf{t} M A S y = ℓ t over F q \mathbb{F}_{q} F q , then the last block has at least K + 1 K+1 K + 1 nonzero coordinates modulo q q q , because β \beta β is nonzero modulo q q q and E \mathbf{E} E repeats every coordinate K + 1 K+1 K + 1 times. If M A S y = ℓ t \mathbf{M}\mathbf{A}_{S}\mathbf{y}=\ell\mathbf{t} M A S y = ℓ t over F q \mathbb{F}_q F q and q ∤ ℓ q \nmid\ell q ∤ ℓ , then the first block has more than 2 K 2K 2 K nonzero coordinates modulo q q q by Equation (25) . In the remaining case, the second and last blocks vanish modulo q q q . The first block therefore reduces to a nonzero codeword of Λ \Lambda Λ mod q q q , which has Hamming weight at least K + 1 K+1 K + 1 .
Since q > 2 ( b K T ) 2 q > 2(bK^{T})^2 q > 2 ( b K T ) 2 , Lemma A.6 applies to L ( B ′ ) \mathcal{L}(\mathbf{B}') L ( B ′ ) . Together with K ( 1 + 2 / c ) = K + 2 k K(1+2/c)=K+2k K ( 1 + 2/ c ) = K + 2 k , Equation (22) , and Equation (23) , it gives
( λ 1 ( p ) ( L ( B ′ ⊗ T ) ) ) p ≥ b K T > ( 3 γ ) p ( K + 2 k ) T = ( 3 γ R ) p > ( γ d ′ ) p . \left(\lambda_1^{(p)}\left(\mathcal{L}(\mathbf{B}'^{\otimes T})\right)\right)^p \ge bK^T > (3\gamma)^p(K+2k)^T = (3\gamma R)^p > (\gamma d')^p. ( λ 1 ( p ) ( L ( B ′ ⊗ T ) ) ) p ≥ b K T > ( 3 γ ) p ( K + 2 k ) T = ( 3 γ R ) p > ( γ d ′ ) p .
Thus the output is a NO instance.
We finally bound the running time. The constants b b b , T T T , and c c c depend only on p p p and γ \gamma γ , and K K K , q q q , and d ′ d' d ′ are computable from k k k alone. By Theorem A.3 , computing H \mathbf{H} H , s s s , and S S S takes time f ( q + k + K ) ( m + 1 ) O ( 1 ) f(q+k+K)(m+1)^{O(1)} f ( q + k + K ) ( m + 1 ) O ( 1 ) for a computable function f f f . By Lemma 2.13 , computing A \mathbf{A} A takes time polynomial in the dimensions of H \mathbf{H} H and log q \log q log q . The matrix B ′ \mathbf{B}' B ′ has N + 1 + ( K + 1 ) r N+1+(K+1)r N + 1 + ( K + 1 ) r rows and N + 1 + r N+1+r N + 1 + r columns, and its entries are obtained by integer matrix multiplication. Since T T T is a constant, writing down ( B ′ ) ⊗ T (\mathbf{B}')^{\otimes T} ( B ′ ) ⊗ T takes time polynomial in the encoding length of B ′ \mathbf{B}' B ′ . Hence the reduction is deterministic and runs in FPT time with parameter k k k . □
Thus, we obtain the desired result.
Proof of Theorem 1.2 . Fix p p p and γ \gamma γ , and take c c c and k ↦ q ( k ) k \mapsto q(k) k ↦ q ( k ) from Theorem A.7 . By Theorem A.2 , ( 2 c ) (2c) ( 2 c ) -GapMLDq ( k ) _{q(k)} q ( k ) is W[1]-hard under deterministic FPT many-one reductions. Composing these reductions with the reduction in Theorem A.7 proves the theorem. □