Reductions between short vector problems and simultaneous approximation
Daniel E. Martin
math.NT 52C07, 11H06, 68W25


Short vector problems and simultaneous approximation]Reductions between short vector problems and simultaneous approximation

This research was supported by NSF-CAREER CNS-1652238 under the supervision of PI Dr. Katherine E. Stange.


University of California, Davis, CA, United States
dmartin@math.ucdavis.edu

[2010]Primary: 52C07, 11H06, 68W25.






In 1982, Lagarias showed that solving the approximate Shortest Vector Problem also solves the problem of finding good simultaneous Diophantine approximations <cit.>. Here we provide a deterministic, dimension-preserving reduction in the reverse direction. It has polynomial time and space complexity, and it is gap-preserving under the appropriate norms. We also give an alternative to the Lagarias algorithm by first reducing the version of simultaneous approximation in <cit.> to one with no explicit range in which a solution is sought.

[
    Daniel E. Martin
    December 30, 2023
=====================





§ INTRODUCTION


Our primary result is to show that a short vector problem reduces deterministically and with polynomial complexity to a single simultaneous approximation problem as presented in the definitions below. We use min^× to denote the nonzero minimum, {}∈(-1/2,1/2]^n to denote the fractional part of ∈^n, and [x] to denote the set {1,...,⌊ x⌋} for x∈.

A short vector problem takes input α∈[1,∞) and nonsingular M∈_n(). A valid output is _0∈^n with 0<M_0≤αmin^×_∈^nM. Let svp denote an oracle for such a problem.

A good Diophantine approximation problem takes input α,N∈[1,∞) and ∈^n. A valid output is q_0∈[α N] with {q_0}≤αmin_q∈[N]{q}. Let gda denote an oracle for such a problem.

Our reduction asserts that if we can find short vectors in a very restricted family of lattices then we can find them in general, since behind a good Diophantine approximation problem is the lattice generated by ^n and one additional vector, .

Literature more commonly refers to a short vector problem as a shortest vector problem when α = 1 and an approximate shortest vector problem otherwise (often unrestricted to sublattices of ^n, though we have lost no generality). A brief exposition can be found in <cit.>. See <cit.> or <cit.> for a more comprehensive overview, <cit.> for a focus on cryptographic applications, <cit.> for a summary of hardness results, and <cit.> for relevance and potential applications to post-quantum cryptography. 

Regarding simultaneous approximation, Brentjes highlights several algorithms in <cit.>. For a sample of applications to attacking clique and knapsack-type problems see <cit.>, <cit.>, and <cit.>. Examples of cryptosystems built on the hardness of simultaneous approximation are <cit.>, <cit.>, and <cit.>. This version is taken from <cit.> and <cit.>.

The reduction, given in Algorithm <ref>, preserves the gap α when the ℓ_∞-norm is used for both problems. This means the short vector problem defined by α and M is solved by calling gda(α,, N) for some ∈^n and N∈. It reverses a 1982 result of Lagarias, which reduces a good Diophantine approximation problem to svp. (See Theorem B in <cit.>, which refers to the problem as good simultaneous approximation. We borrow its name from <cit.> and <cit.>.) Though there is an important contextual distinction: <cit.> relates simultaneous approximation under the ℓ_∞-norm to lattice reduction under the ℓ_2-norm, whereas all reductions in this paper assume a consistent norm. 

Under Lagarias' (and the most common) setup —the ℓ_∞-norm for gda and the ℓ_2-norm for svp—we are not the first to go the other direction. In a seminar posted online from July 1, 2019, Agrawal presented an algorithm achieving this reduction which was complete less some minor details <cit.>. Tersely stated, he takes an upper triangular basis for a sublattice of ^n and transforms it inductively, using integer combinations and rigid rotations with two basis vectors at time, into a lattice (a rotated copy of the original) whose short vectors can be found via simultaneous approximation. The short vector problem defined by α and M gets reduced to gda(α/√(2n),,N), called multiple times in order to account for the unknown minimal vector length which is used to determine . 

In contrast, the reduction here takes a completely different approach. It finds a sublattice which is nearly scaled orthonormal, so that only one additional vector is needed to generate the original lattice. This extra vector is the input for gda. We note that when switching between norms, our reduction is also not gap-preserving. To use Algorithm <ref> to solve a short vector problem with respect to the ℓ_2-norm via gda with respect to the ℓ_∞-norm, the latter must be executed with the parameter α/√(n) to account for the maximum ratio of nonzero norms _2/_∞.

The relationship between the two problems in Definitions <ref> and <ref> will be studied through the following intermediary.

A simultaneous approximation problem takes input α∈[1,∞) and ∈^n. A valid output is q_0∈ with 0 < {q_0}≤αmin^×_q∈{q}. Let sap denote an oracle for such a problem.

This problem prohibits only the trivial solution, the least common denominator of 's entries, while “N" in a good Diophantine approximation problem is generally more restrictive.

Section <ref> explores the relationship between the two versions of simultaneous approximation given in Definitions <ref> and <ref>. Among the results, only Proposition <ref> in Subsection <ref> is required to verify the final reduction of a short vector problem to either version of simultaneous approximation. Subsection <ref> contains Algorithm <ref>. It reduces a good Diophantine approximation problem to polynomially many sap calls, each executed with the parameter α/3.06. So while this reduction is not gap-preserving, the inflation is independent of the input.

Section <ref> reduces both versions of simultaneous approximation to svp. It begins with Algorithm <ref>, which solves Definition <ref>'s version. We remark at the end of Subsection <ref> how this reduction adapts to the inhomogeneous forms of these problems, meaning the search for q_0∈ or _0∈^n that makes q_0 - or M_0 - small for some ∈^n. (In this case the latter is known as the approximate closest vector problem, exposited in chapter 18 of <cit.>, for example.) Then Subsection <ref> combines Algorithms <ref> and <ref> to solve Definition <ref>'s version of simultaneous approximation using svp. This is our alternative to the Lagarias reduction.

Finally, Algorithm <ref> in Section <ref> reduces a short vector problem to gda or sap. It also adapts to the inhomogeneous versions of svp and sap (not gda, as mentioned at the end of Subsection <ref>). In Corollary <ref> we observe that Algorithm <ref> facilitates a simpler proof that gda is NP-hard under an appropriate bound on α, a result first obtained in <cit.>. Then we combine Algorithms <ref> and <ref> in Subsection <ref> to solve a simultaneous approximation problem with gda. In particular, we give all six reductions among the defined problems, as shown in the diagram below.

l0.41


    

    [scale = 2.9]
    (0,0,0) node (0) sap;
    (1.1,-0.4,0) node (1) gda;
    (0.896,0.793,0) node (2) svp;
    (0.07,0.76,0) node (3) Alg <ref>;
    (0.07,0.63,0) node (4) <ref>;
    (0.95,0.26,0) node (5) Alg <ref>;
    (0.95,0.13,0) node (6) <ref>;
    (1.44,0.25,0) node (7) <ref>;
    (0.45,0.42,0) node (8) Alg <ref>;
    (0.45,0.29,0) node (9) <ref>;
    (0.54,-0.10,0) node (10) Alg <ref>;
    (0.54,-0.23,0) node (11) <ref>;
    (0.25,-0.515,0) node (12) <ref>;
    
    
    [bend right=49,-Stealth[round,scale=1.3], dashed] (0) to (1);
    [bend right=49,-Stealth[round,scale=1.3]] (1) to (2);
    [bend right=49,-Stealth[round,scale=1.3], dashed] (2) to (0);
    [bend left=20,-Stealth[round,scale=1.3]] (0) to (2);
    [bend left=20,-Stealth[round,scale=1.3], dashed] (2) to (1);
    [bend left=20,-Stealth[round,scale=1.3]] (1) to (0);
    
    Algorithm and subsection numbers for reductions.


The two reductions in Figure <ref> without algorithm numbers are achieved by following the two arrows that combine to give the same source and target. Dashed arrows indicate a norm restriction. Each must be executed under either the ℓ_1, ℓ_2, or ℓ_∞-norm. However, we point out in Subsection <ref> how the restriction can be alleviated to any ℓ_p-norm provided we accept additional gap inflation by a constant arbitrarily close to 1.

The results are summarized by the following table. It uses m and d to denote the maximal magnitude among input integers and the least common denominator of the input vector, respectively. The matrix or vector dimension is n, and p defines the norm. Trivial cases that cause logarithms to equal 0 are ignored. Column descriptions follow.









Operations: Big-O bound on the number of arithmetic operations per oracle call. 

Integers: Big-O bound on the length of integers used throughout the reduction.

Inflation: Maximum gap inflation. For example, to solve a good Diophantine approximation problem with some α using Algorithm <ref>, sap is called with α/3.06.

Calls: Upper bound on the number of required calls to the oracle.



§ VERSIONS OF SIMULTANEOUS APPROXIMATION




 §.§ SAP to GDA
 Rather than give a complete reduction from a simultaneous approximation problem to gda, which is postponed until the end of Subsection <ref>, the purpose of this subsection is to observe a condition on the input that makes these two versions of simultaneous approximation nearly equivalent.

Suppose the i^th coordinate of  is of the form x_i=1/d, where d∈ makes d∈^n. Under an ℓ_p-norm, gda(α,,N) solves the simultaneous approximation problem defined by α n^1/p and  with N = d/2α.

Let q_min∈ [d/2] be such that {q_min} is the nonzero minimum. A vector's fractional part is in (-1/2,1/2]^n, making its length at most n^1/p/2. So we may assume that {q_min} < 1/2α, since otherwise every integer in [N] = [d/2α] solves the simultaneous approximation problem defined by α n^1/p and .

Under an ℓ_p-norm, {q_min} is an upper bound for its i^th coordinate, q_min/d. Combined with the assumption {q_min} < 1/2α, this gives q_min∈ [d/2α]=[N], which implies min_q∈[N]{q}≤min^×_q∈{q}. And because α N < d, it is guaranteed that gda(α,,N) is not a multiple of d.

Note that without an assumption on  like the one used in this proposition, there is no natural choice for N that makes gda solve a simultaneous approximation problem. If we set it too small, say with N < d/2, then min_q∈[N]{q} may be unacceptably larger than min^×_q∈{q}, potentially making gda's approximation poor. If we set it too large, say with N ≥ d/α, then gda may return d, which is not a valid output for the initial simultaneous approximation problem.

To get around this, our strategy is to first reduce a simultaneous approximation problem to svp with Algorithm <ref>. Then in Algorithm <ref>, which reduces a short vector problem to sap, we are careful to produce an input vector for the oracle that satisfies the hypothesis of Proposition <ref> in order to admit gda.



 §.§ GDA to SAP
 Let d continue to denote the least common denominator of . The problem faced in this reduction is that outputs for a good Diophantine approximation problem are bounded by α N, which may be smaller than d/2. This leaves no guarantee that sap(α,), call this integer d_1∈[d/2], is a solution. But knowing that  is very near a rational vector _1 with least common denominator d_1 allows us to call sap again, now on _1 to get d_2∈[d_1/2]. This is the least common denominator of some _2 near _1, and we continue in this fashion until the output is at most α N. To get d_i∈[d_i-1/2], we adopt the convention that modular reduction returns an integer with magnitude at most half the modulus.









The output of Algorithm <ref> solves the initial good Diophantine approximation problem.

Let d_i and _i denote the values of d and  after i while loop iterations have been completed. In particular, d_0 and _0 are defined by the input. Also let I+1 be the total number of iterations executed, so the output is d_I+1. 

The triangle inequality gives 
    {d_I+1}≤{d_I+1_I} + d_I+1∑_i=1^I_i - _i-1.
 With λ_i=min_q∈[N]{q_i}, the choice of d_I+1 bounds the first summand by αλ_I/c, where c=3.06 in the algorithm but is left undetermined for now. Similarly, the choice of d_i=sap(α/c,_i-1) and the fact that d_i-1 > α N≥ N make 
    _i - _i-1={d_i_i-1}/d_i≤αmin^×_q∈{q_i-1}/cd_i≤αλ_i-1/cd_i.
 So to bound (<ref>) it must be checked that the λ_i's are not too large. To this end, fix some i≤ I and let q_min∈[N] satisfy {q_min_i-1} = λ_i-1. Then we have the following upper bound on λ_i, where the three inequalities are due to the triangle inequality, inequality (<ref>), and q_min≤ N < d_I/α≤ d_i/2^I-iα, respectively: 
    {q_min_i}≤λ_i-1 + q_min_i - _i-1≤λ_i-1(1 + α q_min/cd_i)< λ_i-1(1 + 1/2^I-ic).
 Inductively, this gives 
    λ_i<λ_0∏_j=1^i(1 + 1/2^I-jc).
 Now the three numbered inequalities above can be combined to get 
    {d_I+1}≤α d_I+1/c∑_i=0^Iλ_i/d_i+1≤α/c∑_i=0^Iλ_i/2^I-i≤αλ_0/c∑_i=0^I1/2^I-i∏_j=1^i(1 + 1/2^I-jc).
 Thus the output approximation quality, {d_I+1}, is at most αmin_q∈[N]{q} =αλ_0 provided c satisfies 
    1≥1/c∑_i=0^∞1/2^i∏_j=i^∞(1 + 1/2^jc).
 This justifies our choice of c=3.06 in line 3.

Let m>1 be the maximum magnitude among integers defining , and let d>1 be its least common denominator. The reduction in Algorithm <ref> requires an initial O(nlog m) operations plus O(n) operations for each call to sap, of which there are at most ⌈log_2(d/α N)⌉, on integers of length O(nlog m).

Repeatedly applying the Euclidean algorithm computes d with O(nlog m) operations on integers of length O(nlog m). Modular reduction in line 3 decreases each successive least common denominator by at least a factor of 1/2. This bounds the number of while loop iterations by ⌈log_2(d/α N)⌉.



§ REDUCING TO SVP


First we restrict attention to Definition <ref>'s version of simultaneous approximation (sap) in Algorithm <ref>. Then we will compare the combination with Algorithm <ref> to Lagarias' reduction in <cit.> from Definition <ref>'s version (gda).



 §.§ SAP to SVP
 Here we replace the n+1 vectors associated to simultaneous approximation, namely  and a basis for ^n, with n vectors generating the same lattice. There are algorithms for which this is a byproduct, like Pohst's modified (to account for linearly dependent vector inputs) LLL algorithm <cit.> or Kannan and Bachem's Hermite normal form algorithm <cit.>. But as a consequence of achieving additional basis properties, they are more complicated and require more operations than necessary. We briefly present an alternative because the improved time complexity is relevant to the next subsection.









The output of Algorithm <ref> solves the initial simultaneous approximation problem.

First note that a in line 2 exists. As d is the least common denominator, gcd(dx_1,...,dx_n) and d are coprime. So take a to be divisible by those primes which divide gcd(dx_1,...,dx_n-1) but not dx_n. Also, since a is an integer, the new value of  defines the same simultaneous approximation problem as the input.

Coprime entries means d extends to some M∈SL_n(). (One method is mentioned in the next proof.) The columns of dM generate d^n, so the same is true if we only scale the last n-1 columns by d. In particular, the columns of the new M in line 4 generate d and d^n, which in turn generate each column. Thus M defines a basis for the original simultaneous approximation lattice scaled by d.

Finally, the last n-1 columns of M are vectors in d^n, so that Msvp(α,M)≡svp(α,M)_1d mod d^n. This verifies that svp(α,M)_1 is the integer we seek.

Let m>1 be the maximum magnitude among integers defining . The reduction in Algorithm <ref> requires O((n+log m)^2) operations on integers of length O(nlog m).

As with Algorithm <ref>, line 1 requires O(nlog m) operations on and resulting in integers of length O(nlog m).

Skipping line 2 for now, the i^th column (for i≥ 2) of M in line 3 can be set to 
    (b_1dx_1/gcd(dx_1,...,dx_i-1),...,b_1dx_i-1/gcd(dx_1,...,dx_i-1),b_2,0,...,0)
 (transposed), where b_2gcd(dx_1,...,dx_i-1)-b_1dx_i = gcd(dx_1,...,dx_i). The determinant of the top, left i× i minor is then gcd(dx_1,...,dx_i) by induction. To find b_1 and b_2 we execute the Euclidean algorithm on gcd(d_ix_1,...,d_ix_i-1) and d_ix_i, where d_i=lcd(x_1,...,x_i). But gcd(d_ix_1,...,d_ix_i-1) is at most m times gcd(d_i-1x_1,...,d_i-1x_i-1), which divides the greatest common divisor of the numerators of x_1,...,x_i-1. So for each i the Euclidean algorithm needs O(log m) operations.

Before computing the last column of M, we find a in line 2 to ensure a determinant of 1. As discussed in the last proof, we can start with a=gcd(dx_1,...,dx_n-1) and replace it with a / gcd(a,dx_n) until nothing changes. This requires O(log a) = O(log m) executions of the Euclidean algorithm, each taking O(log m) operations.

Scaling all but the first column by d in line 4 takes O(n^2) operations.

We remark that this algorithm adapts to inhomogeneous forms of these problems. To find q_0∈ with {q_0 - }≤αmin_q∈^×{q - } when q - ∈^n has no solution, we can perform the same reduction and finish by calling an oracle which solves the approximate closest vector problem defined by α, M, and d.



 §.§ GDA to SVP
 Combining Algorithms <ref> and <ref> gives an alternative to the Lagarias reduction from good Diophantine approximation to svp in <cit.>. We execute Algorithm <ref>, but use Algorithm <ref> to compute sap(α/3.06,) in line 3. By Proposition <ref>, this requires at most ⌈log_2(d/α N)⌉ calls to svp. And Proposition <ref> states that each call requires O((n+log m)^2) operations on integers of length O(nlog m).0pt 

Recall that switching from ℓ_2 to ℓ_∞ decreases a nonzero norm by at most a factor of 1/√(n). In particular, by executing this combination of Algorithms <ref> and <ref> with respect to the ℓ_2-norm, we get an ℓ_∞ solution to the initial good Diophantine approximation problem provided we use α/3.06√(n) for svp.

Lagarias achieves this reduction with the now well-known trick from <cit.> of reducing the lattice generated by ^n and , bumped up a dimension by putting 0 in every (n+1)^th coordinate but 's. The ideal value for the last coordinate of , which is guessed at using ⌊ n+log_2dN⌋ calls of the form svp(α/√(5n), M) for varying M, is min_q∈[N]{q}/N. (The gap inflation approaches √(n) as our guesses get better.) The Lagarias reduction requires an initial O(nlog m) arithmetic operations to compute the least common denominator, then only one additional operation per call. The integers involved have input length O(log m^nN). 

Whether the benefit of fewer calls to svp outweighs the increased operations per call depends on the complexity of the oracle. Ours is an asymptotic improvement when the number of operations performed by svp exceeds O((n+log m)^2). 






§ REDUCING TO GDA OR SAP





We focus first on the reduction to sap.



 §.§ Intuition
 Consider an input matrix M∈_n() for a short vector problem. Let d =  M, and let _1,...,_n denote the standard basis vectors for ^n. If there were one vector, call it ∈^n, for which the set {M, d_1,...,d_n} generated the columns of M, our reduction would just amount to finding it. This is exactly the setup for simultaneous approximation: n+1 vectors, n of which are scaled orthonormal. A solution could be obtained by doing simultaneous approximation on M/d, scaling the resulting short vector by d, and applying M^-1 (to comply with Definition <ref>). Unfortunately, unless n≤ 2 or d = ±1, such a  does not exist. Indeed, the adjugate matrix, M = d M^-1, has at most rank 1 over /p for a prime p dividing d. So at least n-1 additional vectors are required to have full rank modulo p, a prerequisite to having full rank over . But asking that M generate the columns of M alongside d_1,...,d_n is equivalent to asking that  generate ^n alongside the columns of M. 

What mattered is the matrix with columns d_1,...,d_n being scaled orthonormal. As such, multiplying by it or its inverse has no effect on a vector's relative length. So we plan to find a different set of n column vectors—a set for which just one additional M is needed to generate the original lattice—which is nearly scaled orthonormal, making the effect of its corresponding matrix multiplication on α negligible. The initial short vector problem becomes a search for an integer combination of M and these columns, say _1,...,_n. We can then solve the simultaneous approximation problem defined by α and [_1 ⋯ _n]^-1M. This works as long as multiplying by [_1 ⋯ _n] changes the ratio between the lengths of the shortest vector and our output by less than whatever is afforded by the fact that lattice norms form a discrete set. 

An arbitrary lattice may have all of its scaled orthonormal sublattices contained in d^n. So as candidates for the matrix [_1 ⋯ _n], we look for something of the form cd Id + MA = M(c  M + A) for some c∈ and A∈_n(). If the entries of A are sufficiently small, then multiplication by cd Id + MA has a similar effect on relative vector norms as multiplying by cd Id, which has no effect.

We will tailor our choice of c and A so that a coordinate of the simultaneous approximation vector, (c  M + A)^-1, is 1/ (c  M + A). This admits Proposition <ref> and hence gda.



 §.§ SVP to GDA or SAP
 Algorithm <ref> uses the following.

For polynomials f_1=∑_if_1,ix^i and f_2=∑_if_2,ix^i with maximum degree d, let C(f_1,f_2) denote the matrix of their coefficients, 
    [          f_1,d                             0          f_2,d                             0; 0pt[0.8][0.3]⋮ 0pt[0.8][0.3]⋱                0pt[0.8][0.3]⋮ 0pt[0.8][0.3]⋱               ;          f_1,1              ⋯          f_1,d          f_2,1              ⋯          f_2,d;          f_1,0              ⋯        f_1,d-1          f_2,0              ⋯        f_2,d-1;                0pt[0.8][0.3]⋱ 0pt[0.8][0.3]⋮                0pt[0.8][0.3]⋱ 0pt[0.8][0.3]⋮;              0                         f_1,0              0                         f_2,0 ].


The matrix above can determine when f_1 and f_2 are coprime over (x) in lieu of polynomial long division, where coefficient growth is exponential without complicated mitigations as in <cit.>. We demonstrate this now to give some clarity to the meaning behind lines 5 and 6 of Algorithm <ref>.

Let f_1,f_2∈[x], not both constant. As an ideal in [x], (f_1,f_2) contains C(f_1,f_2), which is nonzero if and only if f_1 and f_2 have no common root in the algebraic closure of .

Let d=max( f_1, f_2). Consider the vector in ^2d whose only (perhaps) nonzero entry is C(f_1,f_2) in the last coordinate. This is the image under C(f_1,f_2) of some nonzero integer vector. We can split the entries of this vector down the middle to get coefficients for g_1,g_2∈[x] that have degree at most d-1 and satisfy C(f_1,f_2)=f_1g_1+f_2g_2∈ (f_1,f_2). 

Plugging a common root of f_1 and f_2 into this last equation, should one exist, shows that C(f_1,f_2)=0. Conversely, suppose f_1g_1+f_2g_2=0 and that f_1 = d≥ 1. Then g_2 must be nonzero to avoid the same being true of g_1, contradicting our choice of nonzero coefficient vector. But g_2 has degree at most d-1. So f_1g_1=-f_2g_2 implies that at least one of f_1's d roots must be shared by f_2.

For a matrix M, let M_i,j denote the entry in its i^th row and j^th column, and let _i denote its top, left i× i minor.

Line 1 of the next algorithm requires knowing the position of a nonzero entry in the input matrix, and line 8 requires knowing the maximum magnitude among entries. For notational convenience, we assume that M_n,1 is the nonzero maximum. 



Let us turn to the for loop, which builds the matrix Subsection <ref> called A.

For i=2,...,n, there is some j≤ 2i-2 satisfying the criterion of line 5 in the for loop iteration corresponding to i.

When i=2 we are asked to find j for which the linear polynomials M_1,1 and M_2,1 + p^j do not share a root (by Lemma <ref>). The constant term of M_1,1 is p by line 2, meaning it has at most one root. So asking that j≤ 2i-2 = 2 gives enough space to avoid the at-most-one value of j that fails. Now suppose i≥ 3 and that the claim holds for i-1. Let M be its value after line 4 in the for loop iteration corresponding to i, and let f_1=( _i-1)_i-1,1 and f_2=( _i-1)_i-1,2.

By assumption there are g_1,g_2∈[x] with g_1f_1 + g_2f_2 =  C(f_1,f_2)≠ 0. Fix an integer j, and let h_1 = ( _i)_i,1 - p^jf_1 and h_2 = ( _i)_i,2 - p^jf_2, the polynomials we hope to make coprime with the appropriate choice of j. We have 
    [  f_2 -f_1;  g_1  g_2 ][ h_1; h_2 ]=[                  f_2( _i)_i,1-f_1( _i)_i,2; g_1( _i)_i,1+g_2( _i)_i,2 - p^j C(f_1,f_2) ].
 In the column on the right, where we now focus our attention, p^j has been isolated.

For each root of the top polynomial, there is at most one value of j that makes it a root of the bottom. Thus it suffices to show that f_2( _i)_i,1-f_1( _i)_i,2 is not the zero polynomial. Then its degree, which is at most 2i-3, bounds how many values of j can make the right-side polynomials share a root. As this occurs whenever h_1 and h_2 share a root, Lemma <ref> would complete the proof.

To show that f_2( _i)_i,1-f_1( _i)_i,2 is nonzero, we compute its constant term from the following matrix: 
    [       p       0       ⋯       0       0       0; p+p^j_2       p                       0       0;       p   p^j_3                               0;       ⋮               ⋱                       ⋮;       p       0         p^j_i-1       p       0;       p       0       ⋯       0     p^j       p ].
 These are the constants in _i after adding p^j in the i,i-1 position—the main diagonal comes from line 2, the first column comes from line 4, and the second diagonal comes from line 5. To compute h_1 or h_2, we use cofactor expansion along the bottom row after deleting the last column and the first or second row. The (i-2)×(i-2) minor determinants that are multiplied by the bottom row constant p^j are exactly f_1 and f_2 up to a sign. What remains sums to ( _i)_i,1 or ( _i)_i,2. So the constant terms of ( _i)_i,1, ( _i)_i,2, and f_2 are p^i-1, 0, and p to the power 1+j_3+⋯ j_i-1, respectively. This makes p to the power i+j_3+⋯ +j_i-1 the constant term of f_2( _i)_i,1-f_1( _i)_i,2.

We remark that by using a large integer instead of x in line 2, the for loop could successively make pairs of integers coprime rather than polynomials. Then the Euclidean algorithm could test j in line 5; determinants involving polynomial entries need not be computed. We might expect such an algorithm to require O(n^3log M_n,1n) operations (this uses that the average ratio with Euler's phi function, φ(n)/n, is a positive constant), but the provable worst case is bad. The best current asymptotic upper bound on the size of the interval that must be sieved or otherwise searched to find j is due to Iwaniec <cit.>. It only limits the algorithm to O(n^7log M_n,1n) operations. We favored the polynomial approach because of an easier bound on j (Lemma <ref>) and a better provable worst case (Theorem <ref>).   

The next lemma allows the vector in line 10 to pass as  from Subsection <ref>.

With M denoting its value in line 9, gcd((adj M)_n,1,(adj M)_n,2)=1. 

By Lemma <ref>, it suffices to prove gcd(( M)_n,1,( M)_n,2,c)=1 with c as in line 6. Now let c' be c/p^j or p+1 as in line 7. Recall the constant terms displayed in (<ref>), which show that ( M)_n,2 is a power of p modulo c'. This implies gcd(( M)_n,1,( M)_n,2,c) is a power of p since p∤ c'. But the constants added throughout the for loop are multiples of p. So before substituting for x, only the leading coefficient of ( M)_n,1 might have been nonzero modulo p. With M now the original input matrix, the leading term is M_n,1 M^n-2x^n-1. By line 1 this is coprime to p whenever the same is true of the integer substituted for x.

Let M be the input matrix, let c^j be as in line 8, and let A be such that c^jadj M + A is Algorithm <ref>'s value of M in line 9. Then MA_op < (2nM_n,1)^3n/5n under any ℓ_p-norm.

The operator norm is max_=1MA. Using _∞≤ 1 gives 
    MA≤ nMA_∞≤ n^2max_i,j∈[n]|(MA)_i,j|.
 

We refer back to (<ref>), which displays the entries of A when i = n. Lemma <ref> says0pt 

j_i≤ 2i-2, so the entries of MA are bounded in magnitude by 
    max_i,j∈[n]|M_i,j|max(np+p^2,p+p^2n-2)≤ 2M_n,1p^2n-2≤ 2M_n,1^3p^2n-2.
 (Recall that n≥ 2 for this inequality.) Here np+p^2 comes from the first column of A, and p+p^2n-2 comes from the (n-1)^th column. 

Now we turn to the size of p. If x∈ is such that x#, the product of primes not exceeding x, is larger than M_n,1| M|, then it must be that p< x. Rosser and Schoenfeld's lower bound on Chebyshev's theta function, ϑ(x)=∑_p≤ xlog p, gives ϑ(x) > 0.231x when x≥ 2 <cit.>. For the determinant we use Hadamard's bound: | M|≤ (M_n,1√(n))^n <cit.>. So take x=(log M_n,1^3nn^n)/0.462 (note that x≥ 2 even when n=2 and M_n,1=1, allowing for the Rosser-Schoenfeld bound) to get 
    log x# =ϑ(x) > 0.231x=12log M_n,1^3nn^n≥log M_n,1^n+1n^n/2≥log M_n,1| M|.
 

Combining p<x with (<ref>) and (<ref>) gives MA_op < 2M_n,1^3n^2x^2n-2. We must show that this is less than the stated bound of (2nM_n,1)^3n/5n. To do this, raise both expressions to the power 1/(n-1) and use (5/4)^1/(n-1)≤ 5/4. This simplifies the desired inequality to (log M_n,1^3n)^2<1.366M_n,1^3n, which is true.

Under the ℓ_1, ℓ_2, or ℓ_∞-norm, the output of Algorithm <ref> solves the initial short vector problem.

 There are two parts to the proof: 1) showing that the algorithm replaces the columns of M with n+1 vectors that define the same lattice, n of them being nearly scaled orthonormal, and 2) showing that nearly scaled orthonormal is as good as being scaled orthonormal. Throughout the proof, let M be the input matrix, let c^j be as in line 8, let M' be Algorithm <ref>'s value of M in line 9, and let A=M'-c^j M be the matrix of constants added throughout the for loop (as used in Lemma <ref> and as shown in (<ref>) when i=n). 

For part 1), with = (b_1,b_2,0,...,0) from line 10, Lemma <ref> gives 
    =M'^-1=(x_1,x_2,...,1)/ M'.
 By Cramer's rule <cit.>, the 1 in the last coordinate is the determinant after replacing the last column of M' by , so that these n columns generate ^n. This in turn shows that the columns of MM' and M generate the input lattice. Also note by Proposition <ref>, that a coordinate of M' being 1 allows for gda in place of sap with N set to n^1/p M'/2α and α scaled by 1/n^1/p. 

Instead of finding a short integer combination of M and the columns of 
    MM'=c^j M Id + MA,
 Algorithm <ref> uses (MM')^-1(M)= and the columns of (MM')^-1(MM')=Id. Then MM'{q_0} is proposed as a short vector. It is indeed an element of the original lattice as the coordinates of M'{q_0}≡ q_0 mod ^n are all integers. But it must be checked is that MM'{q_0} is short whenever {q_0} is. Part 2) of the proof is to make precise the insignificance of the second matrix summand, MA, in (<ref>). We begin by computing how much multiplication by the full matrix in (<ref>) is allowed to inflate the gap without invalidating the output of gda or sap.

By Minkowski's theorem <cit.>, the magnitude of the shortest vector in the original lattice with respect to the ℓ_∞-norm is not more than | M|^1/n. So under an ℓ_p-norm with p∈, the shortest vector has some magnitude, say λ, with (n^1/p| M|^1/n)^p≥λ^p∈. In particular, n| M|^2/n≥λ^2∈ when p∈{1,2,∞}. Now, if ∈^n is such that M^2 < (a^2λ^2+1)/b^2, then it must be that M≤ aλ/b since there are no integers strictly between (aλ/b)^2 and (a^2λ^2+1)/b^2. Thus multiplication by MM' may harmlessly inflate the gap between the norms of our output vector and shortest vector by anything less than 
    √(a^2λ^2+1)/bαλ = √(a^2λ^2+1)/aλ≥√(a^2n| M|^2/n+1)/a√(n)| M|^1/n.


Scaling does not affect the ratio of vector norms, so to determine the effect of multiplication by (<ref>) it suffices to consider the matrix 
    Id + MA/c^j M
 instead. If _min is a shortest nonzero vector in the simultaneous approximation lattice generated by ^n and , then a shortest vector after applying (<ref>) to this lattice has norm at least (1 - MA_op/|c^j M|)_min. Similarly, the vector {q_0} obtained using q_0 from line 11 increases in norm by at most a factor of (1 + MA_op/|c^j M|). Combining this with our conclusion regarding (<ref>) shows that it suffices to verify the following inequality holds: 
    1+MA_op/|c^j M|/1 - MA_op/|c^j M|≤√(a^2n| M|^2/n+1)/a√(n)| M|^1/n.


Now solve for |c^j| to get a lower bound of 
    √(a^2n| M|^2/n+1)+a√(n)| M|^1/n/√(a^2n| M|^2/n+1)-a√(n)| M|^1/n·MA_op/| M|< (5a^2n| M|^2/n)MA_op/| M|.


Ignoring the powers of | M| on the right-hand side since 2/n≤ 1, we see that j in line 8 is chosen to make the bound above agree exactly with Lemma <ref>.

Let m=max(a^1/n^3,M_n,1). The reduction in Algorithm <ref> requires O(n^4log mn) operations on integers of length O(n^4log mn).

We will use that finding determinants, adjugates, inverses, or characteristic polynomials of n× n matrices with entry magnitudes bounded by m requires O(n^3) operations on integers of length O(nlog mn). For example, see Danilevskii's method for the characteristic polynomial <cit.> and the Bareiss algorithm for the others <cit.>. Note that we may then compute determinants of matrices with linear polynomial entries in O(n^3) operations provided the matrix of linear terms or the matrix of constant terms is invertible.

In the proof of Lemma <ref> we showed that the prime p from line 1 is less than (log M_n,1^3nn^n)/0.462. So finding it does not contribute to asymptotic complexity.

Now consider the for loop, where we must avoid recomputing the determinant in line 5 for each value of j in order to meet the prescribed bound on operations.

Let i≥ 3 and fix some notation: M is its value after line 4, f_1=( _i-1)_i-1,1 and f_2=( _i-1)_i-1,2, g_1 and g_2 have degree at most i-3 and f_1g_1+f_2g_2= C(f_1,f_2)≠ 0, and for some j, h_1=( _i)_i,1 - p^jf_1 and h_2=( _i)_i,2 - p^jf_2. Note for computing ( _i)_i,2 that the constant term matrix is not invertible (see (<ref>)), which may also be true of the linear term matrix. Because this complicates combining the Bareiss and Danivelskii algorithms, we could find ( _i)_i,2 indirectly by computing h_2 for two values of j that produce an invertible constant term matrix (recall from (<ref>) that f_2 has nonzero constant term), then solve for it.

Call the polynomials in the resulting column vector below h'_1 and h'_2: 
    [  f_2+p^jg_1x^2i-3 -f_1+p^jg_2x^2i-3;               g_1               g_2 ][ h_1; h_2 ]

 
    =[ f_2( _i)_i,1-f_1( _i)_i,2 - p^j C(f_1,f_2)x^2i-3;     g_1( _i)_i,1 + g_2( _i)_i,2 - p^j C(f_1,f_2) ].



Remark that if j makes h'_1 and h'_2 avoid a common root, it does so for h_1 and h_2.

View C(h'_1,h'_2) as a matrix with linear polynomial entries where p^j is the variable. This variable only appears in the leading term of h'_1 and the constant term of h'_2. So p^j only occurs on the main diagonal of C(h'_1,h'_2), where its coefficient is nonzero. In particular, the polynomial C(h'_1,h'_2) can be found in O(n^3) operations. Substituting different values of p^j into this polynomial until one is nonzero avoids repeatedly finding determinants. And note that we still need only test up to j=2i-2 as stated in Lemma <ref> because the determinant of the matrix in (<ref>) is a constant (a unit in (x)). Thus each for loop iteration requires O(n^3) operations.0pt 

The integers composing the linear polynomial matrix entries that begin each for loop iteration are small powers of p=O(nlog M_n,1n) and entries in the adjugate of the input matrix, M. By Hadamard's bound they are thus O(nlog M_n,1n) in length. Hadamard's bound also applies to the coefficients of ( _i)_i,1 and ( _i)_i,2, making their lengths O(n^2log M_n,1n). And it applies again to make C(( _i)_i,1, ( _i)_i,2)) have length O(n^3log M_n,1n). This is our bound on the length of c in line 6 and hence the length of c in line 7. The length of c^j in line 8 is then O(max(log a^2(2M_n,1n)^3n, log |c|))=O(n^3log mn), with the maximum accommodating the ceiling function. Then a final application of Hadamard's bound for lines 9 and 10 makes integer lengths O(n^4log mn). This is therefore a bound on the number of operations required by the Euclidean algorithm in line 9.

In <cit.>, Dinur proves the NP-hardness of short vector problems under the ℓ_∞-norm when α=n^c/loglog n for some c>0 by giving a direct reduction from the Boolean satisfiability problem (sat). As a consequence, Theorems <ref> and <ref> prove the same for both good Diophantine approximation and simultaneous approximation problems. (There is no gap inflation for gda in line 11 under the ℓ_∞-norm.)0pt 

Good Diophantine approximation and simultaneous approximation problems are NP-hard under the ℓ_∞-norm with α=n^c/loglog n for some c>0.

This result is known for good Diophantine approximation <cit.>, though the reduction sat→svp→gda completed here is simpler. Chen and Meng adapt the work of Dinur as well as Rössner and Seifert <cit.> to reduce sat to finding short integer vectors that solve a homogeneous system of linear equations (hls) via an algorithm from <cit.>, which changes the problem to finding pseudo-labels for a regular bipartite graph (psl). The number of equations in the hls system is then decreased to one (now called sir), wherefrom a reduction to gda has been known <cit.>. Each link, sat→psl→hls→sir→gda, is gap-preserving under the ℓ_∞-norm.

Short vector problems are only known to be NP-hard under the ℓ_∞-norm. But there are other hardness results under a general ℓ_p-norm for which Theorems <ref> and <ref> can be considered complementary. See <cit.> for an exposition.

Another corollary is the reduction from a simultaneous approximation problem to gda, giving the final row of Table <ref>. By Proposition <ref>, Algorithm <ref> results in one call to svp with integers of length O(nlog m), where we can take m to be the maximum magnitude among a^1/n^4 (still α=a/b) and the integers defining . Then Theorem <ref> implies the reduction to gda requires O(n^4log m^nn)=O(n^5log m) (absorbing the operations required by Algorithm <ref>) on integers of length O(n^5log m).



 §.§ Further discussion
 The last algorithm was restricted to an ℓ_p-norm for p∈{1,2,∞}. So we will discuss what happens with a more general approach.

Multiplication by MM', shown in (<ref>), may change the gap between the length of the shortest vector in the simultaneous approximation lattice and that of the vector output by gda or sap. That this potential inflation does not invalidate our output relies on the set of vector norms being discrete and α being rational—facts that were exploited to produce the expression in (<ref>). The idea behind that paragraph is to find a nonempty interval (αλ, α'λ), where λ=min^×_∈^nM, that contains no norms from the lattice defined by M (or even ^n for the interval tacitly given in the proof). This creates admissible inflation, α'/α, which is (<ref>).

The purpose of restricting to ℓ_1, ℓ_2, or ℓ_∞ is to facilitate finding this interval. Knowing that (bαλ)^2∈ for some b∈ simplifies the search for α'. The same is true for any ℓ_p-norm with p∈. But the immediate analogs of (<ref>), (<ref>), and (<ref>) lead to a replacement for the very last bound used in the proof of the form 
    (5pa^pn| M|^p/n)MA_op/2| M|.
 This makes the number of operations needed to execute line 9 depend exponentially on the input length log p (though it is still polynomial for any fixed p). We have not taken into account, however, the possibility of a nontrivial lower bound for the difference between large consecutive integers which are sums of n perfect p^th powers. Such a bound would allow for a longer interval, (αλ, α'λ), that provably contains no lattice norms.

These arguments are all in effort to perfectly preserve the gap when reducing to sap or, when p=∞, gda. The situation clarifies if a small amount of inflation is allowed. To solve a short vector problem with gap α using sap with gap α' < α, inequality (<ref>) becomes 
    1+MA_op/|c^j M|/1 - MA_op/|c^j M|≤α/α'.
 We still need to substitute a power of c for x in line 8 for the purpose of Lemma <ref>. Given these two constraints, it is sufficient to take M← M(c^j) for 
    j=⌈log_|c|(α + α')MA_op/(α - α')| M|⌉,
 which can be made more explicit with Lemma <ref>. There is no need to insist that α is rational or impose a restriction on p∈[1,∞] defining the norm.

As a final note, the reduction to sap again adapts to inhomogeneous forms of these problems while the reduction to gda does not. If ∈^n, then the algorithm (which now reduces the closest vector problem) can end by solving the simultaneous approximation problem of finding q_0∈ with {q_0-(MM')^-1}≤αmin_q∈^×{q-(MM')^-1}, using the matrix from (<ref>). But unless we know that the last coordinate (where the 1 is located in (<ref>)) of (MM')^-1 is an integer, there is no clear modification to Proposition <ref> that permits the use of gda.

plain


