pith. sign in

arxiv: 1907.07886 · v1 · pith:X34ISISXnew · submitted 2019-07-18 · 🧮 math.OC

Sparsity of integer solutions in the average case

Timm Oertel , Joseph Paat , Robert Weismantel This is my paper

Pith reviewed 2026-05-24 19:55 UTC · model grok-4.3

classification 🧮 math.OC
keywords sparsityinteger programmingaverage caseCarathéodory numberEhrhart polynomialslatticesstandard form
0
0 comments X

The pith

Integer programs in standard form have feasible solutions with O(m) nonzero entries on average under mild assumptions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors study the sparsity of feasible integer solutions when the constraint matrix is fixed and the right-hand side vector varies. They prove that, under relatively mild assumptions on the matrix, the average number of nonzero entries in a feasible solution is O(m), where m is the number of equations. This contrasts with the worst case, which can require more nonzeros. The proof relies on ideas from group theory, lattices, and Ehrhart polynomials. A corollary provides improved bounds on the integer Carathéodory number when the determinants of the data are small.

Core claim

For a problem in standard form with m equations, there exist LP feasible solutions with at most m many nonzero entries. We show that under relatively mild assumptions, integer programs in standard form have feasible solutions with O(m) many nonzero entries, on average. Our proof uses ideas from the theory of groups, lattices, and Ehrhart polynomials. From our main theorem we obtain the best known upper bounds on the integer Caratheodory number provided that the determinants in the data are small.

What carries the argument

Average-case analysis of the number of nonzeros in feasible integer solutions over varying right-hand sides, using group, lattice, and Ehrhart polynomial techniques.

If this is right

  • The integer Carathéodory number has improved upper bounds when determinants are small.
  • Feasible solutions to integer programs are typically sparse, with O(m) nonzeros on average.
  • The result applies to standard-form integer programs with fixed constraint matrices.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Such average sparsity may explain why certain heuristic methods for integer programming perform well in practice.
  • The approach could be extended to other measures of solution complexity beyond the number of nonzeros.
  • If the mild assumptions are satisfied by random matrices, this suggests a typical-case guarantee for sparsity.

Load-bearing premise

The constraint matrix meets relatively mild assumptions enabling the group, lattice, and Ehrhart arguments to establish the O(m) average sparsity bound.

What would settle it

Construct a matrix satisfying the mild assumptions for which the average number of nonzero entries over many right-hand side vectors is larger than any constant times m.

read the original abstract

We examine how sparse feasible solutions of integer programs are, on average. Average case here means that we fix the constraint matrix and vary the right-hand side vectors. For a problem in standard form with m equations, there exist LP feasible solutions with at most m many nonzero entries. We show that under relatively mild assumptions, integer programs in standard form have feasible solutions with O(m) many nonzero entries, on average. Our proof uses ideas from the theory of groups, lattices, and Ehrhart polynomials. From our main theorem we obtain the best known upper bounds on the integer Caratheodory number provided that the determinants in the data are small.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims that for integer programs in standard form with m equality constraints, under relatively mild assumptions on the constraint matrix A, the average (over feasible right-hand sides b) of the minimal support size of a nonnegative integer solution x to Ax = b is O(m). The argument relies on the structure of the integer kernel (via groups and lattices) combined with Ehrhart theory to bound the measure of b for which all integer solutions require support larger than O(m). A corollary yields improved upper bounds on the integer Carathéodory number when the determinants appearing in the data are small.

Significance. If the central theorem holds under the stated assumptions, the result supplies a quantitative average-case sparsity guarantee that improves on known worst-case bounds and provides a new application of Ehrhart polynomials to counting 'bad' right-hand sides. The Carathéodory-number corollary is a concrete payoff when determinants are bounded. The approach is technically distinctive and could influence both theory and the design of heuristics that exploit typical sparsity.

major comments (2)
  1. [§1 (main theorem)] §1 (main theorem statement): the 'relatively mild assumptions' on A that enable the lattice/Ehrhart counting argument are invoked to obtain the O(m) average bound but are not stated with sufficient precision in the theorem itself; without an explicit list (e.g., full row rank, bounded determinant of basis submatrices, or properties of the lattice generated by the columns), it is impossible to verify whether the assumptions are indeed mild or to check the scope of the result.
  2. [Proof of main theorem] Proof of the main theorem (around the Ehrhart-polynomial counting step): the argument that the proportion of b requiring support > C m is o(1) as the right-hand-side norm grows relies on the degree and leading coefficient of the Ehrhart polynomial of the relevant polytope; the manuscript must exhibit the precise polynomial degree used and confirm that it yields a vanishing density independent of the particular lattice, otherwise the O(m) claim does not follow.
minor comments (2)
  1. [Abstract] The abstract and introduction should clarify whether 'average' refers to the expectation of the minimal support size or to the support size of a typical solution drawn from some distribution over b.
  2. [Preliminaries] Notation for the integer kernel and the associated group should be introduced once and used consistently; currently the transition between lattice and group language is abrupt.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestions. We address the two major comments below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§1 (main theorem)] §1 (main theorem statement): the 'relatively mild assumptions' on A that enable the lattice/Ehrhart counting argument are invoked to obtain the O(m) average bound but are not stated with sufficient precision in the theorem itself; without an explicit list (e.g., full row rank, bounded determinant of basis submatrices, or properties of the lattice generated by the columns), it is impossible to verify whether the assumptions are indeed mild or to check the scope of the result.

    Authors: We agree that the assumptions require an explicit list in the theorem statement. In the revision we will state them precisely: A has full row rank m, every m×m basis submatrix has determinant bounded by a fixed constant D, and the lattice generated by the columns of A has index bounded by a constant depending only on D. These are the standard mild conditions under which the lattice/Ehrhart argument applies. revision: yes

  2. Referee: [Proof of main theorem] Proof of the main theorem (around the Ehrhart-polynomial counting step): the argument that the proportion of b requiring support > C m is o(1) as the right-hand-side norm grows relies on the degree and leading coefficient of the Ehrhart polynomial of the relevant polytope; the manuscript must exhibit the precise polynomial degree used and confirm that it yields a vanishing density independent of the particular lattice, otherwise the O(m) claim does not follow.

    Authors: The counting argument uses the Ehrhart polynomial of an m-dimensional polytope (the fundamental parallelepiped intersected with the relevant coset). Its degree is exactly m and its leading coefficient equals the volume of the fundamental domain, which is positive and finite for any fixed lattice of bounded index. The 'bad' right-hand sides lie in a finite union of lower-dimensional cosets whose counting function has degree at most m−1; the ratio of the two counting functions therefore tends to zero as ||b||→∞, independently of the concrete lattice. We will add this explicit degree and asymptotic comparison to the proof. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation uses external lattice/Ehrhart machinery

full rationale

The paper fixes A and averages over b, invoking group/lattice structure plus Ehrhart polynomials to count the measure of b where minimal support exceeds O(m). These are standard external results (not derived or fitted inside the paper). The small-determinant hypothesis is stated only for the derived Carathéodory corollary. No equation reduces by construction to a fitted input, no self-citation is load-bearing for the central claim, and no ansatz is smuggled via prior work by the same authors. The argument is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review; no free parameters, invented entities, or non-standard axioms are identifiable from the given text.

axioms (1)
  • standard math Standard properties of groups, lattices, and Ehrhart polynomials
    Invoked to establish the average-case bound

pith-pipeline@v0.9.0 · 5631 in / 1033 out tokens · 32189 ms · 2026-05-24T19:55:19.428250+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    SIAM Journal on Optimization 28, 2152–2157 (2018)

    Aliev, I., De Loera, J., Eisenbrand, F., Oertel, T., Weis mantel, R.: The support of integer optimal solutions. SIAM Journal on Optimization 28, 2152–2157 (2018)

    work page 2018

  2. [2]

    SIAM Journal on Applied Algebra and Geometry 1, 239–253 (2017)

    Aliev, I., De Loera, J., Oertel, T., O’Neil, C.: Sparse so lutions of linear diophantine equations. SIAM Journal on Applied Algebra and Geometry 1, 239–253 (2017)

    work page 2017

  3. [3]

    In: Eisenbrand F., Koenemann J

    Aliev, I., Henk, M., Oertel, T.: Integrality gaps of inte ger knapsack problems. In: Eisenbrand F., Koenemann J. (eds) Integer Programming a nd Combinatorial Optimization. Lecture Notes in Computer Science. pp. 808–8 16 (2017)

    work page 2017

  4. [4]

    Prentice Hall, New Jersey (1991)

    Artin, M.: Algebra. Prentice Hall, New Jersey (1991)

    work page 1991

  5. [5]

    Barvinok, A.: A Course in Convexity, vol. 54. American Ma thematical Society, Providence, Rhode Island (2002)

    work page 2002

  6. [6]

    Journal f¨ ur die reine und angewandte Mathematik 510, 151 – 178 (2004)

    Bruns, W., Gubeladze, J.: Normality and covering proper ties of affine semigroups. Journal f¨ ur die reine und angewandte Mathematik 510, 151 – 178 (2004)

    work page 2004

  7. [7]

    Jour nal f¨ ur die reine und angewandte Mathematik 510, 179–185 (1999)

    Bruns, W., Gubeladze, J., Henk, M., Martin, A., Weismant el, R.: A counterexam- ple to an integer analogue of Carath´ eodory’s theorem. Jour nal f¨ ur die reine und angewandte Mathematik 510, 179–185 (1999)

    work page 1999

  8. [8]

    Journal of Combinatorial Theory, Series B 40(1), 63–70 (1986)

    Cook, W., Fonlupt, J., Schrijver, A.: An integer analogu e of Carath´ eodory’s the- orem. Journal of Combinatorial Theory, Series B 40(1), 63–70 (1986)

    work page 1986

  9. [9]

    Mathematics of Operations Research pp

    Dyer, M., Frieze, A.: Probabilistic analysis of the mult idimensional knapsack prob- lem. Mathematics of Operations Research pp. 564–568 (1989)

    work page 1989

  10. [10]

    Operations Research Letters 34, 564–568 (2006)

    Eisenbrand, F., Shmonin, G.: Carath´ eodory bounds for integer cones. Operations Research Letters 34, 564–568 (2006)

    work page 2006

  11. [11]

    Proceedings of the National Academy of Sciences 53, 260–265 (1965)

    Gomory, R.: On the relation between integer and noninte ger solutions to linear programs. Proceedings of the National Academy of Sciences 53, 260–265 (1965)

    work page 1965

  12. [12]

    In: Proceedings of the 1st Integer Programming and Combinat orial Optimization Conference

    Seb˝ o, A.: Hilbert bases, Carath´ eodory’s theorem andcombinatorial optimization. In: Proceedings of the 1st Integer Programming and Combinat orial Optimization Conference. pp. 431–455 (1990) A Proof of Theorem 2 We construct both matrices A and B using a submatrix ˜A, which we construct first. Let d ∈ Z≥ 1 and p1 < ... < p d be prime. For i ∈ { 1,...,d }...

    work page 1990