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

Rebecca Hoberg, Harishchandra Ramadas, Thomas Rothvoss, Xin Yang

Abstract

The Number Balancing Problem (NBP) asks for two disjoint subsets of a given set of real numbers $a_1, \ldots, a_n \in [0, 1]$ such that the difference between their sums is minimized. While the pigeonhole principle guarantees the existence of a solution with a difference as small as $O(\frac{\sqrt{n}}{2^n})$, finding the minimum is NP-hard. For decades, the best known polynomial-time approach has been the 1982 Karmarkar-Karp differencing algorithm, which achieves a difference of $n^{-\Theta(\log n)}$. This paper establishes a deep, bidirectional relationship between NBP and Minkowski's Theorem. We demonstrate that an approximate oracle for Minkowski's Theorem provides an approximate NBP oracle and, more significantly, that a sufficiently accurate NBP oracle can solve the Shortest Vector Problem (SVP) and Minkowski's problem within polynomial factors. Specifically, any polynomial-time algorithm guaranteeing a solution of at most $2^{\sqrt{n}} / 2^{n}$ would imply a polynomial approximation for these fundamental lattice problems.

Introduction

The Number Balancing Problem (NBP) is a classic variation of the subset-sum and partition problems. Formally, given a vector $a = (a_1, \dots, a_n) \in [0, 1]^n$, we seek a non-zero vector $x \in \{-1, 0, 1\}^n$ that minimizes the absolute value of the inner product $|\langle a, x \rangle|$.

This problem sits at a fascinating intersection of combinatorics and computational complexity. On one hand, non-constructive proofs (the pigeonhole principle) tell us that extremely good balances exist. On the other hand, the algorithmic gap is massive: the difference between the $2^{-n}$ scale guaranteed by theory and the $n^{-\log n}$ scale achievable by the Karmarkar-Karp algorithm has remained unbridged for over thirty years. This research clarifies why this gap exists by linking NBP to the geometry of numbers.

The Geometric Connection: Minkowski’s Theorem

The authors reframe NBP through the lens of Minkowski’s Theorem, a cornerstone of lattice theory. Minkowski’s Theorem states that any centrally symmetric convex body in $\mathbb{R}^n$ with a sufficiently large volume must contain a non-zero integer point.

In the context of NBP, the problem can be viewed as searching for an integer point (the sign vector $x$) within a specific geometric region—a "slab" defined by the hyperplane $\langle a, x \rangle = 0$. The paper establishes two primary reductions that prove NBP is essentially as difficult as finding short vectors in a lattice.

1. From Minkowski to NBP

The first reduction shows that an oracle capable of finding integer points in symmetric convex bodies (an approximate Minkowski oracle) can be used to solve NBP. By constructing a convex body that represents the constraints of the number balancing problem, the authors prove that the existence of a balancing vector is a direct consequence of Minkowski’s volume arguments. This provides a geometric upper bound on the achievable balance.

2. From NBP to Minkowski (The Hardness of NBP)

The more striking contribution is the reverse reduction. The authors prove that if one could find a "high-quality" solution to NBP in polynomial time, one could also solve the Shortest Vector Problem (SVP) in the $L_\infty$ norm.

To achieve this, the authors employ several sophisticated mathematical tools:

  • John’s Theorem: Used to approximate arbitrary convex bodies with ellipsoids.
  • LLL Lattice Reduction: Used to "regularize" these ellipsoids into a form where NBP techniques can be applied.
  • Recursive Self-Reduction: The authors developed a technique to boost a moderately successful NBP solver. By repeatedly applying an NBP oracle to smaller sub-problems, they can refine a coarse balance into an extremely precise one, eventually revealing the shortest vector in a general lattice.

Key Results and Complexity Implications

The paper provides explicit bounds on the hardness of NBP relative to lattice problems:

  • Theorem 1: A $\rho$-approximation for Minkowski’s problem yields a $\delta$-approximation for NBP, where the error $\delta$ is exponentially small: $2^{-n^{\Theta(1/\rho)}}$.
  • Theorem 3: Any polynomial-time algorithm guaranteeing an NBP solution with an error at most $2^{\sqrt{n}}/2^n$ would provide an $O(n^5)$-approximation for Minkowski’s problem.

These results suggest that the difficulty of improving the Karmarkar-Karp algorithm is not merely a technical hurdle but is tied to the fundamental hardness of lattice-based problems. Since many modern post-quantum cryptographic protocols rely on the hardness of SVP, this equivalence suggests that NBP is a "hard" problem in a very formal, cryptographic sense.

Conclusion

By establishing NBP as being "as hard as Minkowski," this research provides a new geometric framework for understanding subset-sum variations. It explains the long-standing stagnation in algorithmic improvements for NBP and identifies the specific precision threshold ($2^{\sqrt{n}}/2^n$) where number balancing becomes equivalent to the Shortest Vector Problem. Future work may focus on whether this hardness extends to the "moderately good" regime—solutions that are better than $n^{-\log n}$ but not yet at the exponential threshold required for the current reduction.

Summary updated

Abstract

The number balancing (NBP) problem is the following: given real numbers $a_1,\ldots,a_n \in [0,1]$, find two disjoint subsets $I_1,I_2 \subseteq [n]$ so that the difference $|\sum_{i \in I_1}a_i - \sum_{i \in I_2}a_i|$ 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(\frac{\sqrt{n}}{2^n})$. 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^{-\Theta(\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^{\sqrt{n}} / 2^{n}$ would give a polynomial approximation for Minkowski as well as a polynomial factor approximation algorithm for the Shortest Vector Problem.
BibTeX
@inproceedings{hoberg2017number,
  author = {Rebecca Hoberg and Harishchandra Ramadas and Thomas Rothvoss and Xin Yang},
  title = {{Number Balancing is as hard as Minkowski's Theorem and Shortest Vector}},
  booktitle = {IPCO},
  year = {2017},
  url = {https://openreview.net/forum?id=9qby16kKX4},
}
Figure