Abstract
This paper establishes new, significantly tighter theoretical bounds on the sparsity of solutions to linear Diophantine equations and integer programs. By integrating the theory of finite Abelian groups with the geometry of numbers, the authors demonstrate that sparse integer solutions are guaranteed to exist under specific conditions and can be computed in polynomial time. The core innovation lies in the introduction of the truncated prime $\Omega$-function, which provides a more refined measure of sparsity than traditional logarithmic bounds.
Introduction
In fields ranging from wireless communications to error-correcting codes, the search for "sparse" solutions—those where the majority of entries are zero—is a fundamental challenge. Formally, this involves minimizing the $\ell_0$-norm of a solution vector $x$ subject to $Ax = b$. While this problem is well-studied over the real numbers within the framework of compressed sensing, finding the sparsest solution over the integers (linear Diophantine systems) or non-negative integers (integer programming) is significantly more complex. In fact, determining the absolute sparsest non-negative integer solution is known to be NP-hard.
This research addresses a foundational question: If a system $Ax = b$ is known to have an integer solution, what is the guaranteed upper bound on its sparsity? Previous theoretical bounds typically relied on logarithmic functions of matrix determinants. This paper sharpens these results by leveraging deeper number-theoretic properties and the structural geometry of lattices and semigroups.
Methodology
The authors move beyond generic real-valued analysis, employing a three-pillared approach rooted in discrete mathematics:
1. Finite Abelian Group Theory
The authors represent the quotient group $\mathbb{Z}^m / \mathcal{L}(A)$, where $\mathcal{L}(A)$ is the lattice generated by the columns of matrix $A$, as a finite Abelian group. By applying the Fundamental Theorem of Finite Abelian Groups, they bound the size of non-redundant generator sets. This algebraic constraint directly translates to a limit on the number of non-zero entries required to represent a solution vector.
2. The Truncated Prime $\Omega$-Function
A pivotal contribution of this work is the introduction of the truncated prime $\Omega$-function, denoted as $\Omega_m(z)$. Unlike standard logarithms that grow steadily, $\Omega_m(z)$ counts the number of prime factors of an integer $z$ (with a threshold $m$). Because most integers do not possess a large number of distinct prime factors, $\Omega_m(z)$ grows much more slowly on average—roughly at the scale of $\log \log z$. This allows for much tighter bounds than the $\log_2$ terms used in prior literature.
3. Geometry of Numbers
For the specific case of "knapsack" problems (systems consisting of a single linear equation), the authors utilize Minkowski’s First Theorem. By analyzing the volume of hyper-parallelepipeds, they prove the existence of sparse integer vectors within specific convex sets, providing a geometric foundation for their algebraic results.
Key Insights and Results
Theoretical Bounds
The paper provides explicit bounds for both general integer solutions (lattices) and non-negative integer solutions (semigroups):
- Lattice Sparsity: For a system $Ax = b$ with $m$ equations, there exists an integer solution $x$ such that: $$\|x\|_0 \leq m + \Omega_m \left( \frac{|\det(A_\tau)|}{\text{gcd}(A)} \right)$$
- Integer Programming Sparsity: If the columns of $A$ "positively span" the space (allowing any point to be reached via non-negative combinations), the bound is: $$\|x\|_0 \leq 2m + \Omega_m \left( \frac{|\det(A_\tau)|}{\text{gcd}(A)} \right)$$
- Knapsack Improvement: For a single equation $a^\top x = b$ with positive coefficients, the authors proved a solution exists with sparsity $\|x\|_0 \leq 1 + \lfloor \log_2(\min\{a_i\}/\text{gcd}(a)) \rfloor$, confirming a long-standing conjecture in the field.
Constructibility
Beyond existence proofs, the authors demonstrate that these sparse solutions are computationally accessible. If a non-singular submatrix $A_\tau$ is available, a solution satisfying these new sparsity bounds can be constructed in polynomial time using standard algorithms for Hermite Normal Forms and Diophantine systems.
Discussion and Future Work
While these results represent a significant advancement, several avenues for future research remain. The tighter bounds for integer programming are contingent on the "positively spanning" geometric condition; if the cone generated by the matrix columns is highly restrictive, these bounds may require further refinement.
Additionally, the authors introduce the concept of the Integer Carathéodory Rank (ICR)—the maximum sparsity required to represent any element within a semigroup. They pose an open question regarding whether computing the ICR is NP-hard even for single-row matrices. Finally, the paper suggests a potential deep connection between these sparsity bounds and the "Frobenius Coin Problem," suggesting that the number theory of partitions may hold further keys to optimizing integer sparsity.
Summary updated