Number Balancing is as hard as Minkowski’s Theorem and
Shortest Vector

arXiv:1611.08757v2 [cs.DM] 29 Nov 2016

Rebecca Hoberg∗

Harishchandra Ramadas†

Thomas Rothvoss‡

Xin Yang§

University of Washington, Seattle, WA 98195

Abstract
The number balancing (NBP) problem is the following:
real numbers a1 , . . . , an ∈ [0, 1], find
P given P
two disjoint subsets I1 , I2 ⊆ [n] so that the difference | i∈I1 ai − i∈I2 ai | of their sums is minimized.
An application√ of the pigeonhole principle shows that there is always a solution where the difference
is at most O( 2nn ). Finding the minimum, however, is NP-hard. In polynomial time, the differencing
algorithm by Karmarkar and Karp from 1982 can produce a solution with difference at most n−Θ(log n) ,
but no further improvement has been made since then.
In this paper, we show a relationship between NBP and Minkowski’s Theorem. First we show that an
approximate oracle for Minkowski’s Theorem gives an approximate NBP oracle. Perhaps more surprisingly, we show that an approximate NBP oracle gives an approximate Minkowski oracle. In particular,
we
√
prove that any polynomial time algorithm that guarantees a solution of difference at most 2 n /2n would
give a polynomial approximation for Minkowski as well as a polynomial factor approximation algorithm
for the Shortest Vector Problem.

1

Introduction

One of six basic NP-complete problems of Garey and Johnson [GJ97] is the partition problem that for a
list of numbers a1 , . . . , an asks whether there is a partition of the indices so that the sums of the numbers
in both partitions coincide. Partition and related problems like knapsack, subset sum and bin packing
are some of the fundamental classical problems in theoretical computer science with numerous practical
applications; see for example the textbooks [MT90, KPP04] and the article of Mertens [Mer06]. In this
paper, we study a variant called the number balancing
(NBP), where the goal is to find two disjoint
P problemP
subsets I1 , I2 ⊆ {1, . . . , n} so that the difference | i∈I1 ai − i∈I2 ai | is minimized. Equivalently, given a
n
vector of numbers
a = (a1 , . . . , an ) ∈ [0, 1]n , we want to find a vector of signs x ∈ {−1, 0, 1} \ {0} so that
Pn
|ha, xi| = | i=1 xi ai | is minimized. Woeginger and Yu [WY92] studied this problem under the name “equalsubset-sum” and showed that it is NP-hard to decide whether there are two disjoint subsets that sum up to
the exact same value. This version has also been extensively studied in combinatorics [Lun88, Boh96, LY11].
On the positive side, it is not hard to prove that there is always a solution
P with exponentially small error.
Suppose that a1 , . . . , an ∈ [0, 1]. Consider the list of 2n many numbers ni=1 ai xi for all x ∈ {0, 1}n. All
these numbers fall into
intervalP[0, n], hence by the pigeonhole principle, we can find two distinct vectors
Pthe
n
n
x, x′ ∈ {0, 1}n with | i=1 ai xi − i=1 ai x′i | ≤ 2nn−1 . Then x − x′ gives the desired solution. Note that the
√

bound can be slightly improved to O( 2nn ) by using the fact that due to concentration of measure effects, for
∗ Email:

rahoberg@uw.edu
ramadas@uw.edu
‡ Email: rothvoss@uw.edu. Supported by NSF grant 1420180 with title “ Limitations of convex relaxations in combinatorial
optimization”, an Alfred P. Sloan Research Fellowship and a David & Lucile Packard Foundation Fellowship.
§ Email: yx1992@uw.edu
† Email:

1

Pn
√
a constant fraction of vectors x ∈ {0, 1}n, the sums i=1 ai xi fall into an interval of length n (instead of
n).
However, since these arguments rely on the pigeonhole principle, they are non-constructive. Restricting
the non-constructive argument to polynomially many “pigeons” provides a simple polynomial time algorithm
1
to find at least an x ∈ {−1, 0, 1}n \ {0} with | ha, xi | ≤ poly(n)
for an arbitrarily small polynomial. Interestingly, the only known polynomial time algorithm that gives a better guarantee is Karmarkar and Karp’s
differencing algorithm [KK82] which provides the bound | ha, xi | ≤ n−c log(n) for some constant c > 0. Their
algorithm uses a recursive scheme; find Θ(n) pairs of numbers ai of distance at most Θ( n1 ) and create an
instance consisting of their differences, then recurse.
Pn
This leads to the natural question: Given a1 , . . . , an ∈ [0, 1], what upper bound on | i=1 ai xi | can be
guaranteed if x ∈ {−1, 0, 1}n \ {0} is to be chosen in polynomial time?
While answering this question directly seems out of reach, it appears that NBP falls into a class of
problems where good solutions exist due to the pigeonhole principle, such as the Shortest Vector Problem
or Minkowski’s Theorem.PRecall that given linearly independent vectors b1 , . . . , bn ∈ Rn , a (full rank)
n
lattice is the set Λ := { i=1 λi bi : λi ∈ Z ∀i = 1, . . . , n}. The set {b1 , . . . , bn } is called a basis for
Λ and we define det(Λ) := | det(B)|. The Shortest vector problem then consists of finding a non-zero
vector in Λ that minimizes the Euclidean norm. The famous LLL-algorithm [LLL82] can find a 2n/2 approximation in polynomial time (the generalized block reduction method of Schnorr [Sch87] brings the
factor down to 2n log log(n)/ log(n) ). As a rarity in theoretical computer√science, the shortest vector problem
admits (NP ∩ coNP)-certificates for a value that is at most a factor O( n) away from the optimum [AR05],
while the best known hardness lies at a subpolynomial bound of nΘ(1/ log log n) √
[HR07]. Using the pigeonhole
principle one can show that a lattice Λ contains a vector of length at most O( n) · det(Λ)1/n . Interestingly,
a polynomial time algorithm that achieves this bound would imply an O(n)-approximation algorithm even
for worst-case lattices [Ajt96], enough to break lattice-based cryptosystems [LLJS90].
Minkowski’s Theorem tells us that any symmetric convex body K ⊆ Rn of volume at least 2n must
intersect Zn \ {0}, see for example [Mat02]. This theorem is proven by placing translates of 12 K at any
lattice point and then inferring an overlap due to the pigeonhole principle. Again, one can consider the
algorithmic question: given a symmetric convex body K with volume at least 2n , for what factor ρ can one be
guaranteed to find an x ∈ (ρK) ∩ (Zn \ {0}) in polynomial time? We would like to point out that this factor
ρ is within a polynomial factor of the shortest vector approximability using the fact that there
√ is a linear
transformation sandwiching K between two Euclidean balls whose radius differs by a factor of n [Joh48].
It is not hard to use an exact oracleP
for Minkowski’s Theorem to find a good number balancing solution,
n
since the body K := {x ∈ (−2, 2) : | i=1 xi ai | ≤ Θ( 2nn )} has a volume of 2n . However, it is not clear
how we could use an approximate oracle. For example, it is known that the LLL-algorithm can be used
toPfind a nonzero integer vector x ∈ ρK for a factor of ρ = poly(n) · 2n/2 . While the error guarantee of
n
| i=1 ai xi | ≤ poly(n) · 2−n/2 outperforms the Karmarkar-Karp algorithm, we only know that kxk∞ < 2ρ,
which means that x will not be a valid solution if ρ > 11 . This leads us to the next question: what factor
ρ is needed for Minkowski’s Theorem to improve over Karmarkar-Karp’s bound ? Again, we should mention
that a poly(n)-approximation for Minkowski is not known to be inconsistent with NP 6= P.
We have seen that in a certain sense the Shortest Vector Problem and Minkowski’s Theorem are generalizations of number balancing. This brings us to the question about the reverse: given an oracle that solves
NBP within an exponentially small error, can this give a non-trivial oracle for the Shortest Vector Problem
or Minkowski’s Theorem?

1.1

Contribution

In this work, we provide some answers to the questions raised above, by relating the complexity of the number
balancing problem to Minkowski’s Theorem. For ρ ≥ 1, we define a ρ-approximation for the Minkowski
problem as a polynomial time algorithm that on input2 of a symmetric convex set K ⊆ Rn with voln (K) > 2n ,
1 If

P
−Θ(εn) , but this breaks down if ρ ≥ 2.
ρ ≤ 2 − ε, then one can still obtain an error of | n
i=1 ai xi | ≤ 2
will specify in the text, how the body K is represented.

2 We

2

finds a vector in (ρ · K) ∩ (Zn \ {0}). Moreover, for δ > 0 we define a δ-approximation for the number
partitioning problem as a polynomial time algorithm that receives a ∈ [0, 1]n as input and produces a vector
x ∈ {−1, 0, 1}n \ {0} with | ha, xi | ≤ δ. We provide the following reduction:
Theorem 1. Suppose there is a ρ-approximation for Minkowski’s problem for polytopes K with O(n) facets.
Θ(1/ρ)
Then there is a δ-approximation for number balancing where δ := 2−n
In fact, it suffices to have such an oracle for the linear transformation of a cube, which is equivalent to
an oracle for SVP in the k · k∞ norm.
Theorem 2. Suppose that there is a polynomial time algorithm that given a lattice Λ ⊆ Rn with det(Λ) ≤ 1
finds a non-zero vector x ∈ Λ of length kxk∞ ≤ ρ. Then there is δ-approximation for number balancing
Θ(1/ρ)
where δ := 2−n
.
Recall that voln ([−1, 1]n ) = 2n and hence for such a lattice there is always an x ∈ Λ \ {0} with kxk∞ ≤ 1.
In particular an oracle for ρ ≤ c′ log(n)/ log log(n) would imply an improvement over Karmarkar-Karp’s
algorithm, where c′ > 0 is a small enough constant. Again, we would like to stress that the NP-hardness
bounds of [HR07] for Shortest Vector do not apply for such lattices where a solution is guaranteed to exist.
Finally, we can also prove that an oracle with exponentially small error for number balancing would
provide approximations for Minkowski’s Theorem and Shortest Vector:
√

Theorem 3. Suppose that there is a δ-approximation for number balancing with δ ≤ 2 n /2n . Then there is
an O(n5 )-approximation for Minkowski’s problem. Here it suffices to have a separation oracle for the convex
body K ⊆ Rn .

2

Reducing Number Balancing to Minkowski’s Theorem

In this section we will show how to solve NBP with an oracle for Minkowski’s Theorem. The idea is to
consider a hypercube intersected with the constraint |ha, xi| ≤ δ, and to show that this set has large enough
volume. If we have an exact Minkowski oracle, this gives us x ∈ {−1, 0, 1}n \ {0} as desired. Here we state
a more general version which uses only a ρ-approximate Minkowski oracle, and then show how we can use
this more general version to solve NBP with a weaker bound.
Theorem 4. Suppose we have a ρ-approximate Minkowski oracle, and let k > 0 be any positive integer.
Then, for any a ∈ [0, 1]n , there is a polynomial time algorithm to find x ∈ Zn \ {0} with kxk∞ ≤ k and so
n−1

ρ
.
that | ha, xi | ≤ n k+1
Proof. For ease of notation, let
δ := n



ρ
k+1

n−1

.

Now consider the body

n



k+1 k+1
: | ha, xi | ≤ δ .
,
x∈ −
ρ
ρ
Obviously this is a symmetric convex body. For α ∈ [−δ, δ], consider the (n − 1)-dimensional slice
n



k+1 k+1
K(α) := x ∈ −
: ha, xi = α
,
ρ
ρ
K :=

of it. Let us consider the (n − 1)-dimensional volume voln−1 (K(α)) of that slice. Then we can write the
volume of K as
Z δ
voln−1 (K(α)) dα.
voln (K) =
−δ

3

Moreover



2(k + 1)
ρ

n


n Z n(k+1)
ρ
k+1 k+1
voln−1 (K(α)) dα.
= voln −
=
,
n(k+1)
ρ
ρ
− ρ

. By symmetry voln−1 (K(α)) = voln−1 (K(−α)). Moreover, by
since the slices are empty if |α| > n(k+1)
ρ
convexity of K, for α ≥ 0, the quantity voln−1 (K(α)) is monotonically non-increasing. Thus
voln (K) =

Z

δ

−δ

voln−1 (K(α)) dα ≥ 

δ
n(k+1)
ρ

·

Z

n(k+1)
ρ

− n(k+1)
ρ

voln−1 (K(α)) dα = 

δ
n(k+1)
ρ

·



2(k + 1)
ρ

n

.


n−1
ρ
Now, using the fact that δ = n (k+1)
, we get voln (K) ≥ 2n . Hence, using our ρ-approximate
Minkowski oracle, we can find a vector
x ∈ (ρK ∩ Zn ) \ {0} = ((−(k + 1), (k + 1))n ∩ Zn ) \ {0}.
In particular, this gives x ∈ Zn with |ha, xi| ≤ n



ρ
k+1

n−1

and kxk∞ ≤ k.

√
The bound in Theorem 4 can be strengthened by a n factor by using concentration of measure arguments. We omit this here.
Now suppose, for instance, that we have a (2 − ǫ)-approximate oracle for some ǫ ∈ (0, 1]. Then we can
pick k = 1 and get

n−1


2−ǫ
ǫ(n − 1)
|ha, xi| ≤ n
= 2−Θ(ǫn) ,
≤ n · exp −
2
2
with kxk∞ ≤ 1 and x ∈ Zn \ {0}. However, this line of arguments breaks down if we only have access to a
ρ-approximation for ρ ≥ 2 as these would in general not produce feasible solutions for number balancing.
It turns out that we can design a recursive self-reduction. The main technical argument is to transform
an algorithm that finds x ∈ Zn \ {0} with kxk∞ ≤ k, into an algorithm that finds vectors x ∈ Zn \ {0} with
kxk∞ ≤ k2 , with a bounded decay in the error |ha, xi|. Applying this recursively gives the following lemma.
Lemma 5. Suppose that there is a polynomial-time algorithm that for any a′ ∈ [−1, 1]n finds a vector
log n
x′ ∈ {−k, . . . , k}n \ {0} with | ha′ , x′ i | ≤ 2−n . If k ≤ 6 log
log n , then there is also a polynomial time
1

algorithm that for any a ∈ [−1, 1]n finds a vector x ∈ Zn with | ha, xi | ≤ 2−n 3k and x ∈ {−1, 0, 1}n \ {0}.

√ The way we do the self-reduction is the following. We partition our set of n numbers into subsets of size
n. First, for each subset ℓ, we find a number bℓ 6= 0 for which we can (approximately) express bℓ , 2bℓ , . . . , kbℓ
as linear combinations of elements of that subset using only coefficients in {−⌊ k2 ⌋, . . . ⌊ k2 ⌋}. We then run our
P√n
assumed algorithm on b1 , . . . , b√n to obtain y ∈ {−k, . . . , k}n with hb, yi = ℓ=1 yℓ bℓ being small. Since
each of the summands can be expressed more efficiently in terms of our original set of numbers, we obtain a
good solution x with coefficients in {−⌊ k2 ⌋, . . . ⌊ k2 ⌋}.
The following two lemmas go through this argument more precisely. The first gives a condition under
which we can find a more efficient coefficient representation for a number β. In the second, we will show
that an application of the assumed algorithm will actually allow us to satisfy this condition, and so we are
able to construct the stronger oracle. Note that the interesting parameter choice is r := ⌈k/2⌉, so that the
size of the coefficients is halved.
P
Lemma 6. Let r, k ∈ N be parameters with r < k. Let α1 , . . . , αk ∈ R so that ki=1 i · αi = 0 and abbreviate
Pk
β := αr + . . . + αk . Then {j · β | j = −k, . . . , k} ⊆ { i=1 λi αi | λi ∈ Z and |λi | ≤ max{r − 1, k − r} for i =
1, . . . , k}.

4

Proof. By symmetry it suffices to consider j ≥ 0. For j ∈ {0, . . . , r − 1}, we can obviously write
j · β = j · αr + . . . + j · αk .
Now consider j ∈ {r, . . . , k}. The trick is to use that
r·β+

r−1
X
i=1

i · αi +

k
X
i=r

(i − r) · αi =

k
X
i=1

i · αi = 0

Then
j · β = (j − r) · β + r · β =

r−1
X
i=1

⇒

(−i) · αi +

r·β =
k
X
i=r

k
r−1
X
X
(r − i) · αi .
(−i) · αi +
i=1

i=r

[(j − r) + (r − i)] ·αi
|
{z
}
=j−i

If we inspect the size of the used coefficients, then for i ∈ {1, . . . , r − 1} we have | − i| ≤ r − 1 and for
i ∈ {r, . . . , k} we have |j − i| ≤ k − r.
Pk
Note that if we have the weaker assumption of | i=1 i · αi | ≤ δ, then for any j ∈ {0, . . . , k} one can find
Pk
coefficients λi with |j · β − i=1 λi αi | ≤ δ.

Lemma 7. Let k, r ∈ N be parameters with 0 < r < k. Let f : N → R be a non-negative function such that
f (n) ≥ 4 log n. Suppose that there is a polynomial-time algorithm that for any a′ ∈ [−1, 1]n finds a vector
x′ ∈ {−k, . . . , k}n \ {0} with | ha′ , x′ i | ≤ 2−f (n) . Then there is √
also a polynomial time algorithm that for
any a ∈ [−1, 1]n finds a vector x ∈ Zn \ {0} with | ha, xi | ≤ 2−f ( n)/2 and kxk∞ ≤ max{r − 1, k − r}.
√
Proof. Let a ∈ [−1, 1]n be the given vector of numbers. Split [n] into blocks I1 , . . . , I√n each of size |Iℓ | = n.
n
For each block I√
ℓ we use the oracle to find a vector xℓ ∈ {−k, . . . , k} \ {0} with supp(xℓ ) ⊆ Iℓ so that
−f ( n)
. If for any ℓ one has kxℓ k∞ ≤ r − 1, then we simply return x := xℓ and are done.
| ha, xℓ i | ≤ 2
P
Otherwise, we write the vector as xℓ = ki=1 i · xℓ,i with vectors xℓ,1 , . . . , xℓ,k ∈ {−1, 0, 1}n. Note that these
vectors will have disjoint support and supp(xℓ,1 ), . . . , supp(xℓ,k ) ⊆ Iℓ . Moreover we know that for every ℓ
there is at least one index i ∈ {r, . . . , k} with xℓ,i 6= 0.
√
√
Pk
Now define a vector b ∈ R n with bℓ := i=r ha, xℓ,i i. Note that if for any ℓ we have |bℓ | ≤ 2−f ( n) ,
√
Pk
then we can set x = i=r xℓ,i and we are done. Therefore we may assume that |bℓ | > 2√−f ( n) for all ℓ.
√
n
Also note that
n. We run the oracle
∞
√ ≤
√ kbk
√ again to find a vector y ∈ {−k, . . . , k} \ {0} so that
| hb, yi | ≤ n · 2−f ( n) . For each block ℓ ∈ [ n] we can use Lemma 6 to find integer coefficients λℓ,i with
|λℓ,i | ≤ max{r − 1, k − r} so that
yℓ · bℓ −

k
X
i=1

λℓ,i · ha, xℓ,i i ≤ 2−f (

We define

√
n)

.

√

x :=

n k
X
X

λℓ,i xℓ,i .

ℓ=1 i=1

Then kxk∞ ≤ max{r − 1, k − r} since the √xℓ,i ’s have disjoint support and kxℓ,i k∞ ≤ 1 for all ℓ, i. Moreover,
since there is some yℓ 6= 0 and |bℓ | > 2−f ( n) , we have x 6= 0.
Finally we inspect that
√

| ha, xi | ≤ | hy, bi | +

2

n
X
ℓ=1

yℓ bℓ −

k
X
i=1

√
√
√
λℓ,i ha, xℓ,i i ≤ 2 n · 2−f ( n) ≤ 2−f ( n)/2 .

√
√
2
4
The last line comes from the fact that when f (n) ≥ 4 log n, we have 2 n ≤ 2 3 log n = 2 3 log n ≤
.

√
1
3 f ( n)

5

Now we can apply Lemma 7 recursively to prove Lemma 5.
Proof of Lemma 5. For k ∈ N, take r = ⌈k/2⌉, then Lemma 7 says any a ∈ [−1, 1]n , if we have a x ∈
{−k,√. . . , k}n such that | ha, xi | ≤ 2−f (n) , we can obtain x′ ∈ {−⌊k/2⌋, . . . , ⌊k/2⌋}n such that | ha, x′ i | ≤
−t
′′
2−f ( n)/2 . Repeat this procedure for t := ⌈log k⌉ times, if f (n2 ) ≥ 4 log n, we will get x ∈ {−1, 0, 1}n
2−t

t

such that | ha, x′′ i | ≤ 2−f (n )/2 .
So we can take f (n) = n as appearing in Lemma 7. Note that when k ≤

log( 12 logloglogn n ),

log n
6 log log n ,

so

−t

−t

f (n2 ) = n2

log n
− log( 1
)
2 log log n

≥ n2

t = ⌈log k⌉ ≤

= log2 n ≥ 4 log n.

Then the condition in Lemma 7 is satisfied, and the bound we get is
2−t

2−f (n

)/2t

2−t

= 2−(n

)/2t

≤ 2−

Here we use the fact that t = ⌈log k⌉ ≤ log 2k, and when k ≤

1
n 2k
2k

1

≤ 2−n 3k .

1 log n
6 log log n ,

1

we have

n 2k
2k

1

≥ n 3k .

Using Lemma 5, we are now able to prove Theorem 1:
Θ(1/ρ)

O(1)

log n
−n
Proof of Theorem 1. If ρ ≥ 48 log
= 2− log
n. By choosing a proper constant on
log n , then 2
the exponent, this can be achieved with the Karmarkar-Karp algorithm. So we only need to work with
log n
ρ < 48 log
log n .

n−1
ρ
log n
If we take k = 3ρ, then Theorem 4 implies | ha, xi | ≤ n k+1
≤ 2−n . Moreover, k = 3ρ ≤ 16 log
log n ,
1

Θ(1/ρ)

and hence the condition of Lemma 5 is satisfied. Then the bound given by Lemma 5 is 2−n 3k ≤ 2−n

.

Instead of using an oracle for Minkowski’s Theorem one can directly use an oracle for the Shortest Vector
Problem in the k · k∞ norm. We need the following theorem:
Theorem 8. Suppose that there is a polynomial time algorithm that given a lattice Λ ⊆ Rn with det(Λ) ≤ 1
finds a non-zero vector x ∈ Λ of length kxk∞ ≤ ρ. Then, for any a ∈ [0, 1]n , there is a polynomial time
algorithm to find x ∈ Zn \ {0} with kxk∞ ≤ k and so that | ha, xi | ≤ 2nkρ( kρ )n .
Proof. When ρ( kρ )n ≥ 12 , we have 2nkρ( kρ )n ≥ 1, in which case x = (1, 0, · · · , 0) trivially does the job. We
can hence assume that ρ( kρ )n < 21 .
Let In be the n×n identity matrix and consider the lattice Λ generated by the (n+1)×(n+1)-dimensional
matrix


ρ
In
0
k
B :=
.
1
k n T
( kρ )n
2nk ( ρ ) a
Note that det(B) = 1. Let x ∈ Λ be the vector returned by the algorithm. Then y := B −1 x ∈ Zn+1 .
Since kxk∞ ≤ ρ and x = By, we have |yi | ≤ k for i = 1, . . . , n. Moreover,
 n
 n
 n
 n X
n
n
X
1
k
k
1
k
k
+
yi ai ≥ |yn+1 |
−
y i ai
ρ ≥ |xn+1 | = yn+1
ρ
2nk
ρ
ρ
2nk
ρ
i=1
i=1
 n
 n
|yi |≤k
k
1 k
≥ |yn+1 |
−
,
ρ
2 ρ
which implies |yn+1 | ≤ 12 + ρ( kρ )n . Since ρ( ρk )n < 21 and yn+1 ∈ Z, we must have yn+1 = 0.
 n
n
Pn
Pn
1
k
Therefore,
yi ai = |xn+1 | ≤ ρ, and hence | i=1 yi ai | ≤ 2nkρ kρ , so the vector
i=1 2nk ρ
(y1 , . . . , yn ) does the job.

6

Now using Lemma 5 and Theorem 8 we are able to prove Theorem 2:
Proof of Theorem 2. The proof mirrors that of Theorem 1. We start by choosing k = 3ρ in Theorem 8,
which gives us | ha, xi | ≤ 2−n and kxk∞ ≤ 3ρ. As we argued in the proof of Theorem 1, we may assume
log n
log n
that ρ < 48 log
log n . This gives us k ≤ 16 log log n and we can, as before, apply Lemma 5.

3

Reducing Minkowski’s Theorem to Number Balancing

In this section we show how an oracle for number balancing can be used to design an algorithm to approximate
Minkowski’s problem. More precisely, given a large enough symmetric convex body K, we will be able to
find a vector x ∈ Zn ∩ ρK \ {0} where ρ is a polynomial
in n. The first helpful insight is that each such
√
convex body can be approximated within a factor of n using an ellipsoid [Lov90, MG12]. Recall that an
ellipsoid is a set of the form
n
n
o
X
1
2
E = x ∈ Rn |
· hx, ai i ≤ 1
(1)
2
λ
i=1 i
with an orthonormal basis a1 , . . . , an ∈ Rn defining the axes and positive coefficients λ1 , . . . , λn > 0 that
describe the lengths of the axes 3 . Overall, our reduction will operate in two steps:
(i) By combining John’s Theorem with lattice basis reduction, we can show that it suffices to find integer
points in an ellipsoid that is well-rounded, meaning that the lengths of the axes are bounded.
(ii) We show that a number balancing oracle allows a self-reduction to a generalized form where inner
products with n vectors have to be minimized and additionally the solution space is Zn instead of
{−1, 0, 1}n.
We begin by proving (ii) and postpone (i) until the end of this section.

3.1

A self-reduction to a generalized form of number balancing

The main technical result of this section is the following reduction:
Theorem 9. Suppose there is a δ-approximation for number balancing with error parameter δ = ρ(n)
2n and
n/2
n
ρ(n) ≤ 2 . Then Q
there is a polynomial time algorithm that on input a1 , . . . , an ∈ [0, 1] and 0 < λ1 ≤
n
. . . ≤ λn ≤ 2n with i=1 λi ≥ 1, finds a vector x ∈ Zn \ {0} with
√

|hx, ai i| ≤ O(n4 ) · λi · ρ(4n2 )1/n

∀i = 1, . . . , n.

In particular if ρ(n) ≤ 2 n , then the right hand side in Theorem 9 simplifies to just O(n4 ) · λi . We will
show this by introducing two extensions of the number balancing oracle. The first extension gives a weaker
bound in terms of the error parameter, but allows for multiple vectors in [0, 1]n . In the second extension, we
extend the range of coefficients from {−1, 0, 1} to {−Q, . . . , Q} which leads to a much stronger error bound.
Lemma 10. Suppose there is a δ-approximation for number balancing. Then there isQ
a polynomial time
algorithm that given an input a1 , . . . , ak ∈ [0, 1]n and parameters δ1 , . . . , δk ≤ 21 with ki=1 δi ≥ δ finds a
vector x ∈ {−1, 0, 1}n \ {0} with |hai , xi| ≤ 2n2 δi for all i = 1, . . . , k.
Proof. The idea is that we will discretize all of the vectors and then run our oracle on their sum. The vector
that we obtain will then have small inner product with all of the ai . To define
Q the discretization ãi , round
elements of ai down to the nearest multiple
of
2nδ
,
and
then
multiply
by
i
j<i δj . Defining ãi this way,
Q
notice that for all i we have |hãi , xi| ≤ n j<i δj .
3 Strictly

speaking, the length of axis i is 2λi , but we will continue calling λi the “axis length”.

7

Now let c = ã1 + . . . + ãk . By our oracle, we can find x ∈ {−1, 0, 1}n \ {0} with |hc, xi| ≤ δ. We have
Y
Y
|hã1 , xi| ≤ |hã2 , xi| + . . . + |hãk , xi| + |hc, xi| ≤ nδ1 + n
δj + . . . + n
δj
j≤2

j≤k



1
1
≤ nδ1 · 1 + + . . . + k < 2nδ1 .
2
2
Therefore |hã1 , xi| = 0. Similarly, for 1 < i ≤ k, if |hã1 , xi|, . . . , |hãi−1 , xi| = 0, then we have
Y
|hãi , xi| ≤ |hãi+1 , xi| + . . . + |hãk , xi| + |hc, xi| < 2n
δj ,
j≤i

Q

and hence |hãi , xi| = 0 for all i. Notice that by definition of ãi we have k j<i δj ai − ãi k∞ ≤ 2n
Q
Q
Therefore |h j<i δj ai , xi| ≤ 2n2 j≤i δj , and so we can conclude that |hai , xi| ≤ 2n2 δi .

Q

j≤i δj .

Now we come to a second reduction that takes the oracle constructed in Lemma 10 as a starting point:

Lemma 11. Assume there exists a f (n)-approximation for number balancing. Let a1 , . . . , ak ∈ [0, 1]n be
Q
given with parameters δ1 , . . . , δk ≤ 12 and a number Q that is a power of 2 and satisfies ki=1 δi ≥ f (n log Q).
Then in polynomial time we can find a vector x ∈ {−Q, . . . , Q}n \ {0} with |hai , xi| ≤ δi Q · 2(n log Q)2 for
all i = 1, . . . , k.
Proof. For each i, we define bi ∈ [0, 1]n log Q by bi (j, ℓ) = ai (j)2−ℓ for j = 1, . . . , n and ℓ = 1, . . . , log Q. Since
Qk
y ∈ {−1, 0, 1}n log Q \{0} with |hbi , yi| ≤ δi ·2(n log Q)2 .
i=1 δi ≥ f (n log Q), we can apply Lemma 10 to find
P
log Q
Now define x ∈ {−Q, . . . , Q}n \ {0} by xj := Q ℓ=1 2−ℓ yjℓ . Then for i = 1, . . . , k we have
δi · (2n log Q)2 ≥ |hbi , yi| =

and rearranging gives the claim.

n log
XQ
X

yjℓ 2−ℓ ai (j) =

j=1 ℓ=1

|

{z

=xj /Q

1
· |hai , xi|
Q

}

Finally we come to the proof of Theorem 9.
Theorem 9. SupposeQthat the oracle has parameter f (n) = ρ(n)/2n . Suppose that a1 , . . . , an ∈ [0, 1]n and
n
λ1 , . . . , λn > 0 with i=1 λi ≥ 1. We choose Q := 24n , which is aQpower of 2. Define δi = λi · f (n log Q)1/n .
3n/2
Note that δi ≤ 2
· f (4n2 )1/n ≤ 21 since f (n) ≤ 2−n/2 . Then ni=1 δi ≥ f (n log Q), and so by Lemma 11
we can find y ∈ {−Q, . . . , Q}n \ {0} with
|hai , yi| ≤ Qδi · 2(n log Q)2

3.2

≤ Qλi · f (n log Q)1/n · 2(n log Q)2
= λi · ρ(4n2 )1/n · 2 · (4n2 )2 .

A reduction to well-rounded ellipsoids

Using John’s Theorem [Joh48], the convex body K in Theorem 3 can be approximated by an ellipsoid E
as defined in Eq. (1). The natural approach will then be to apply Theorem 9 to the axes of the ellipsoid.
However, it will be crucial that the lengths of the axes of the ellipsoid are bounded by 2O(n) . We will now
argue how to make an arbitrary ellipsoid well rounded.
Let us denote λmax (E ) := max{λi : i = 1, . . . , n} as the maximum length of an axis. Recall that a
matrix U ∈ Rn×n is unimodular if U ∈ Zn×n and |det(U )| = 1. In particular, the linear map T : Rn → Rn
8

with T (x) = U x is a bijection on the integer lattice, meaning that T (Zn ) = Zn . It turns out that one
can use the lattice basis reduction method by Lenstra, Lenstra and Lovász [LLL82] to find a unimodular
linear transformation that “regularizes” any given ellipsoid. Note that it suffices to work with the regularized
ellipsoid T (E ) since voln (T (E )) = voln (E ) and if we find a point x ∈ (ρT (E )) ∩ Zn , then by linearity
T −1 (x) ∈ ρE and T −1 (x) ∈ Zn .
P
Given b1 , . . . , bn ∈ Rn we define the Gram-Schmidt orthogonalization iteratively as b̂j = bj − i<j µij b̂i ,
P
hb ,b̂ i
where µij = kb̂j ki2 . Notice that we can then write bj = b̂j + i<j µij b̂i . In particular, suppose B is the
i 2

matrix with columns b1 , . . . , bn and B̂ is the matrix with columns b̂1 , . . . , b̂n . Then B = B̂V for an upper
triangular matrix V with ones along the diagonal and Vij = µij for i < j.

Definition 1. Let B ∈ Rn×n be a lattice basis and let µij be the coefficients from Gram-Schmidt orthogonalization. The basis is called LLL reduced if
• (Coefficient-reduced): |µij | ≤

1
2

for all 1 ≤ i < j ≤ n.

• (Lovász condition): kb̂i k22 ≤ 2kb̂i+1 k22 for i = 1, ..., n − 1.
LLL reduction has been widely used in diverse fields such as integer programming and cryptography
[NV10]. One property of the LLL reduced basis is that the eigenvalues of the corresponding matrix B are
bounded away from 0:
Lemma 12. Let B denote the matrix with columns b1 , . . . , bn . If b1 , . . . , bn is an LLL-reduced basis with
kbi k2 ≥ 1 for all i, then kBxk2 ≥ 2−3n/2 · kxk2 for all x ∈ Rn .
Proof. Let B̂ denote the Gram-Schmidt orthogonalization of B, with columns b̂1 , . . . , b̂n . Now, for any k,
we can use the properties of LLL reduction to gain the following bound (proposition (1.7) in [LLL82]).
1 ≤ kbk k22 = kb̂k k2 +

X
i<k


1 X k−i 
· kb̂k k22 ≤ 2k · kb̂k k22 .
2
µ2ik kb̂i k22 ≤ 1 +
4
i<k

In particular, kb̂k k2 ≥ 2−n for all k = 1, . . . , n. Now let V be the matrix so that B = B̂V , and let x ∈ Rn
with kxk2 = 1. Let k denote the largest index with |xk | ≥ 2−k . Then
|(V x)k | = xk +

X
j>k

µkj xj ≥ |xk | −

1X
1 X −j
|xj | ≥ 2−k −
2 ≥ 2−n .
2
2
j>k

j>k

Now, by the orthogonality of b̂1 , . . . , b̂n , we have
kBxk22 = kB̂V xk22 =

n
X
i=1

(V x)2i kb̂i k22 ≥ |(V x)k |2 · 2−n ≥ 2−3n .

Taking square roots gives the claim.
Lemma 13. Let E = {x ∈ Rn : kAxk22 ≤ 1} be an ellipsoid. Then in polynomial time, we can find
(1) either a vector x ∈ E ∩ Zn
(2) or a linear transformation T so that T (x) = U x for a unimodular matrix U and λmax (T (E )) ≤ 23n/2 .
Proof. Use the algorithm of [LLL82] to find a unimodular matrix U such that B = AU is LLL reduced. Let
b1 , . . . , bn denote the columns of B. Notice that if kbi k2 ≤ 1, then A−1 bi ∈ E ∩ Zn , and so we are done. So
assume now that kbi k2 ≥ 1 for all i.

9

Define T (x) = U −1 x, and notice that T (E ) = {x ∈ Rn : kBxk22 ≤ 1}. We then have
λmax (f (E )) = max kxk2 =
x∈f (E )

max kxk2 = max

kBxk2 ≤1

x6=0

kxk2
≤ 23n/2 ,
kBxk2

where the last inequality follows from Lemma 12.
Finally we can prove one of our main results, Theorem 3.
Theorem 3. Let K ⊆ Rn be a convex body with voln (K) ≥ 2n . We compute an ellipsoid4 E = {x ∈ Rn |
Pn 1
2
1
1√
√
i=1 λ2 hx, ai i ≤ 1} so that 5 n E ⊆ K ⊆ 5 nE . Then
i

2n · 5n · n−n/2 ≤ voln (K) · 5n · n−n/2 ≤ voln (E ) = vol(B(0, 1)) ·
|
{z
}
≤5n n−n/2

n
Y

λi .

i=1

Q
and hence ni=1 λi ≥ 1. We apply Lemma 13 to either find an integer point in E and we are done, or we
find a unimodular transformation T so that the ellipsoid Ẽ := T (E ) has all axes of length at most 2O(n) .
P
Suppose the latter case happens. We write Ẽ = {x ∈ Rn | ni=1 λ̃12 hx, ãi i2 ≤ 1} and observe that still
i
Qn
λ̃
≥
1
as
the
volume
of
the
ellipsoid
has
not
changed.
We
make use of the δ-approximation for
i
i=1
the number balancing problem to apply Theorem 9 to the vectors ãP
1 , . . . , ãn and parameters λ̃1 , . . . , λ̃n
n
2
and obtain a vector x ∈ Zn \ {0} with | hãi , xi | ≤ λ̃i · O(n4 ). Then i=1 λ̃12 hai , xi ≤ O(n9 ) and hence
i
x ∈ O(n4.5 ) · E˜. Then T −1 (x) ∈ (O(n5 ) · K) ∩ (Zn \ {0}).

References
[Ajt96]

M. Ajtai. Generating hard instances of lattice problems. In Proceedings of the 28th STOC, pages
99–108. ACM, 1996.

[AR05]

D. Aharonov and O. Regev. Lattice problems in NP cap conp. J. ACM, 52(5):749–765, 2005.

[Boh96]

T. Bohman. A sum packing problem of erdös and the conway-guy sequence. Proceedings of the
AMS, 124(12):3627–3636, 1996.

[GJ97]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman, 1997.

[HR07]

I. Haviv and O. Regev. Tensor-based hardness of the shortest vector problem to within almost
polynomial factors. pages 469–477, 2007.

[Joh48]

F. John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays
Presented to R. Courant on his 60th Birthday, January 8, 1948, pages 187–204. Interscience Publishers, Inc., New York, N. Y., 1948.

[KK82]

N. Karmarkar and R. Karp. The differencing method of set partitioning. Technical report, CS
Division, UC Berkeley, 1982. http://digitalassets.lib.berkeley.edu/techreports/ucb/text/CSD-83113.pdf.

[KPP04] H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack problems. Springer, 2004.
√
that there exists an ellipsoid that approximates K within a factor of n and if K is a polytope with m facets, then
this ellipsoid can be found in time polynomial in n and m. However, if one only has a separation oracle for K, then the best
factor achievable in polynomial time is n.
4 Note

10

[LLJS90] J. Lagarias, H. Lenstra Jr, and C. Schnorr. Korkin-zolotarev bases and successive minima of a
lattice and its reciprocal lattice. Combinatorica, 10(4):333–348, 1990.
[LLL82] A. Lenstra, H. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.
[Lov90]

L. Lovász. Geometric algorithms and algorithmic geometry. American Mathematical Society, 1990.

[Lun88]

W. Lunnon. Integer sets with distinct subset-sums. Mathematics of Computation, 50(181):297–320,
1988.

[LY11]

V. Lev and R. Yuster. On the size of dissociated bases. the electronic journal of combinatorics,
18(1):P117, 2011.

[Mat02] J. Matousek. Lectures on Discrete Geometry. Springer-Verlag New York, Inc., Secaucus, NJ, USA,
2002.
[Mer06]

S. Mertens. The easiest hard problem: Number partitioning. Computational Complexity and
Statistical Physics, 125(2):125–139, 2006.

[MG12]

A. Schrijver M. Grötschel, L. Lovász. Geometric algorithms and combinatorial optimization, volume 2, pages 122–125. Springer, 2012.

[MT90]

S. Martello and P. Toth. Knapsack Problems: Algorithms and Computer Implementations. John
Wiley & Sons, Inc., New York, NY, USA, 1990.

[NV10]

P. Nguyen and B. Vallée. The lll algorithm. Information Security and, 2010.

[Sch87]

C. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput.
Sci., 53:201–224, 1987.

[WY92]

G. Woeginger and Z. Yu. On the equal-subset-sum problem. Information Processing Letters,
42(6):299–302, 1992.

11

