pith. sign in

arxiv: 2411.07030 · v3 · submitted 2024-11-11 · 💻 cs.CC · cs.CG· cs.DM· cs.DS· math.CO

Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra

Grigorii Dakhno , Dmitry Gribanov , Nikita Kasianov , Anastasiia Kats , Andrey Kupavskii , Nikita Kuz'min , Stanislav Moiseev This is my paper

Pith reviewed 2026-05-23 17:36 UTC · model grok-4.3

classification 💻 cs.CC cs.CGcs.DMcs.DSmath.CO
keywords hyperplanes avoiding probleminteger points countingL1 norm boundcombinatorial nullstellensatzpolyhedraNP-hardnessnormal fan triangulationsubset sum
0
0 comments X

The pith

A vector of L1 norm at most (m+n)/2 avoids any m hyperplanes in n dimensions and can be found deterministically in O(n m) time.

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

The paper establishes that the hyperplanes avoiding problem always has an integer solution vector whose L1 norm is bounded by (m + n)/2. This bound is tight and the vector can be constructed by a deterministic algorithm that uses only O(n m) operations. The construction relies on a new algorithmic version of the Combinatorial Nullstellensatz. The result replaces earlier randomized guarantees of size n m and Barvinok's much larger exponential bounds. The same subroutine yields a faster algorithm for counting integer points in a polytope whose normal fan has triangulation size ν and whose constraint matrix has bounded rank-order subdeterminants.

Core claim

The hyperplanes avoiding problem admits a solution x in Z^n with L1 norm at most (m + n)/2 for any m hyperplanes in n dimensions, and such an x can be constructed deterministically in O(n m) time. This bound is sharp, and the same problem is NP-hard for any p-norm. As a consequence, integer point counting in a polytope given by m inequalities in n variables can be done in O(ν² n³ Δ³) time, where ν is the size of the largest triangulation of the normal fan and Δ bounds the rank-order subdeterminants.

What carries the argument

Algorithmic variant of the Combinatorial Nullstellensatz used to select coordinates that produce an L1-bounded integer vector missing all given hyperplanes.

If this is right

  • The hyperplanes avoiding problem always possesses a feasible L1 solution of size at most (m + n)/2 that is computable in quadratic time.
  • Integer-point counting in polyhedra inherits an O(ν² n³ Δ³) algorithm when the normal fan triangulation size is ν and subdeterminants are bounded by Δ.
  • Counting remains polynomial for polyhedra of bounded codimension, including the unbounded subset-sum problem.
  • The NP-hardness result rules out efficient exact minimization of the avoiding vector under any p-norm.
  • Barvinok-style counting procedures can replace their hyperplane-avoidance step with this deterministic linear-time routine.

Where Pith is reading between the lines

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

  • When the normal fan of a polytope admits small triangulations, the new bound makes exact counting feasible in moderate dimensions.
  • The linear dependence on m and n suggests that the same technique may tighten other enumeration algorithms that rely on hyperplane avoidance.
  • Although exact minimization is hard for other norms, the L1 construction might still serve as a starting point for approximation schemes.

Load-bearing premise

An algorithmic variant of the Combinatorial Nullstellensatz can be invoked to produce the claimed L1-bounded avoiding vector in O(n m) time.

What would settle it

A concrete collection of m hyperplanes in n dimensions for which every integer avoiding vector has L1 norm strictly larger than (m + n)/2, or an instance on which the claimed O(n m) algorithm returns no vector of that size.

read the original abstract

In our work, we consider the problem of computing a vector $x \in Z^n$ of minimum $\|\cdot\|_p$-norm such that $a^\top x \not= a_0$, for any vector $(a,a_0)$ from a given subset of $Z^n$ of size $m$. In other words, we search for a vector of minimum norm that avoids a given finite set of hyperplanes, which is natural to call as the $\textit{Hyperplanes Avoiding Problem}$. This problem naturally appears as a subproblem in Barvinok-type algorithms for counting integer points in polyhedra. We show that: 1) With respect to $\|\cdot\|_1$, the problem admits a feasible solution $x$ with $\|x\|_1 \leq (m+n)/2$, and show that such solution can be constructed by a deterministic polynomial-time algorithm with $O(n \cdot m)$ operations. Moreover, this inequality is the best possible. This is a significant improvement over the previous randomized algorithm, which computes $x$ with a guaranty $\|x\|_{1} \leq n \cdot m$. The original approach of A.~Barvinok can guarantee only $\|x\|_1 = O\bigl((n \cdot m)^n\bigr)$. To prove this result, we use a newly established algorithmic variant of the Combinatorial Nullstellensatz; 2) The problem is NP-hard with respect to any norm $\|\cdot\|_p$, for $p \in \bigl(R_{\geq 1} \cup \{\infty\}\bigr)$. 3) As an application, we show that the problem to count integer points in a polytope $P = \{x \in R^n \colon A x \leq b\}$, for given $A \in Z^{m \times n}$ and $b \in Q^m$, can be solved by an algorithm with $O\bigl(\nu^2 \cdot n^3 \cdot \Delta^3 \bigr)$ operations, where $\nu$ is the maximum size of a normal fan triangulation of $P$, and $\Delta$ is the maximum value of rank-order subdeterminants of $A$. As a further application, it provides a refined complexity bound for the counting problem in polyhedra of bounded codimension. For example, in the polyhedra of the Unbounded Subset-Sum problem.

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

3 major / 2 minor

Summary. The paper introduces the Hyperplanes Avoiding Problem: given m hyperplanes in Z^n defined by integer (a, a0), find an integer vector x minimizing ||x||_p such that a^T x ≠ a0 for all given hyperplanes. It claims (1) a tight L1 bound ||x||1 ≤ (m+n)/2 achievable by a deterministic O(n m)-time algorithm via a new algorithmic variant of the Combinatorial Nullstellensatz (improving prior randomized n m and Barvinok's exponential bounds); (2) NP-hardness for any p-norm with p ≥ 1 or ∞; (3) an application yielding an O(ν² n³ Δ³)-time algorithm for counting integer points in a polytope given by A x ≤ b, with further refinements for bounded-codimension cases such as unbounded subset-sum.

Significance. If the new algorithmic Nullstellensatz variant and its reduction to the L1 bound are correct, the result supplies a deterministic, near-linear improvement on a key subproblem in Barvinok-type counting algorithms, directly tightening complexity for polyhedra of bounded codimension and offering a parameter-free combinatorial guarantee that could propagate to other enumeration tasks.

major comments (3)
  1. [Abstract / proof of claim 1] The headline L1 bound and O(n m) deterministic algorithm (abstract, claim 1) rest entirely on the newly introduced algorithmic variant of the Combinatorial Nullstellensatz. The manuscript must supply the precise statement of this variant, the explicit reduction from hyperplane avoidance to the variant, and the step-by-step complexity analysis showing that the construction runs in O(n m) operations; without these details the claimed improvement over the prior randomized n m guarantee cannot be verified.
  2. [Abstract / proof of claim 1] The assertion that ||x||1 ≤ (m+n)/2 is best possible requires an explicit matching lower-bound construction (a family of m hyperplanes in dimension n forcing every avoiding integer vector to have L1-norm at least (m+n)/2). This construction should be exhibited and shown to be compatible with the algorithmic variant.
  3. [Application to counting (claim 3)] In the application section, the derivation of the O(ν² n³ Δ³) bound for integer-point counting must be spelled out: how the new L1 guarantee is invoked inside the normal-fan triangulation, how the rank-order subdeterminant Δ enters the running time, and why the quadratic dependence on ν appears.
minor comments (2)
  1. [Abstract] Notation for the hyperplane set and the norm p should be introduced once and used consistently; the abstract mixes “a subset of Z^n of size m” with later references to A ∈ Z^{m×n}.
  2. [Abstract / claim 2] The NP-hardness claim (claim 2) should state the precise reduction source and the dimension in which hardness holds, to clarify whether it applies already for fixed small n.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and valuable suggestions for improving the clarity of our results. We address each major comment below and will revise the manuscript to incorporate the requested details, statements, and derivations.

read point-by-point responses

  1. Referee: [Abstract / proof of claim 1] The headline L1 bound and O(n m) deterministic algorithm (abstract, claim 1) rest entirely on the newly introduced algorithmic variant of the Combinatorial Nullstellensatz. The manuscript must supply the precise statement of this variant, the explicit reduction from hyperplane avoidance to the variant, and the step-by-step complexity analysis showing that the construction runs in O(n m) operations; without these details the claimed improvement over the prior randomized n m guarantee cannot be verified.

    Authors: We agree that the precise statement of the algorithmic variant, the explicit reduction, and the detailed complexity analysis are necessary for full verification. In the revised manuscript we will add a dedicated subsection containing: (i) the exact statement of the algorithmic Combinatorial Nullstellensatz variant as a standalone theorem, (ii) the step-by-step reduction from the hyperplane-avoidance instance to an instance of the variant, and (iii) a line-by-line accounting of the arithmetic operations establishing the O(n m) bound. This will make the deterministic improvement over the prior randomized guarantee transparent. revision: yes

  2. Referee: [Abstract / proof of claim 1] The assertion that ||x||1 ≤ (m+n)/2 is best possible requires an explicit matching lower-bound construction (a family of m hyperplanes in dimension n forcing every avoiding integer vector to have L1-norm at least (m+n)/2). This construction should be exhibited and shown to be compatible with the algorithmic variant.

    Authors: We will include an explicit matching lower-bound construction in the revised version. The construction consists of a concrete family of m hyperplanes in dimension n for which every integer vector avoiding all of them satisfies ||x||1 ≥ (m+n)/2; we will also verify that this family is compatible with the algorithmic variant (i.e., the variant produces a vector attaining the bound). revision: yes

  3. Referee: [Application to counting (claim 3)] In the application section, the derivation of the O(ν² n³ Δ³) bound for integer-point counting must be spelled out: how the new L1 guarantee is invoked inside the normal-fan triangulation, how the rank-order subdeterminant Δ enters the running time, and why the quadratic dependence on ν appears.

    Authors: We agree that the derivation should be expanded. In the revised manuscript we will add a self-contained paragraph (or short subsection) that: (i) explains how the new L1-norm guarantee is substituted into the enumeration step of the normal-fan triangulation, (ii) shows the precise dependence of the per-cone running time on the maximum rank-order subdeterminant Δ, and (iii) derives the quadratic factor in ν from the number of cones generated by the triangulation and the per-cone cost. This will make the overall O(ν² n³ Δ³) bound fully traceable. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on independent internal lemma

full rationale

The central L1 bound ||x||1 ≤ (m+n)/2 and O(n m) algorithm are derived via a newly established algorithmic variant of the Combinatorial Nullstellensatz, presented as a separate result in the paper rather than a self-referential definition or fitted input. No equations or steps reduce the claimed bound or runtime to the target quantity by construction. The NP-hardness result and polytope counting application are likewise independent of any self-referential loop. This matches the default expectation of a self-contained derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The L1 result rests on an unexpanded algorithmic form of the Combinatorial Nullstellensatz; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption Algorithmic variant of the Combinatorial Nullstellensatz sufficient to construct the claimed avoiding vector
    Invoked to establish both existence and the O(n m) deterministic algorithm for the L1 case.

pith-pipeline@v0.9.0 · 6023 in / 1274 out tokens · 56556 ms · 2026-05-23T17:36:45.147167+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

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

    Aliev, I., De Loera, J.A., Eisenbrand, F., Oertel, T., Wei smantel, R.: The support of integer optimal solutions. SIAM Journal on Optimization 28(3), 2152–2157 (2018). https://doi.org/10.1137/17M1162792

    work page doi:10.1137/17m1162792 2018

  2. [2]

    In: International Conference on Inte ger Programming and Combinatorial Optimization

    Aliev, I., Celaya, M., Henk, M.: Sparsity and integrality gap transference bounds for integer programs. In: International Conference on Inte ger Programming and Combinatorial Optimization. pp. 1–13. Springer (2024)

    work page 2024

  3. [3]

    SI AM Journal on Optimization 20(6), 2978–2993 (2010)

    Aliev, I., Henk, M.: Feasibility of integer knapsacks. SI AM Journal on Optimization 20(6), 2978–2993 (2010)

    work page 2010

  4. [4]

    Alon, N.: Combinatorial nullstellensatz. Combinatoric s, Probability and Comput- ing 8(1-2), 7–29 (1999) 12 Authors Suppressed Due to Excessive Length m Sampling Our algorithm 2000 1496,8 30,4 2100 1544,4 32 2200 1594,6 30,2 2300 1643,4 27,8 2400 1695 31 2500 1744 31,8 2600 1794 35 2700 1843,8 33,6 2800 1893,6 37,4 2900 1945,8 40 3000 1994 34 Table 1: The...

    work page 1999

  5. [5]

    Periodica Mathematica Hungarica 43, 93–103 (2002)

    Bárány, I., Harcos, G., Pach, J., Tardos, G.: Covering lat tice points by subspaces. Periodica Mathematica Hungarica 43, 93–103 (2002)

    work page 2002

  6. [6]

    European Math ematical Society, ETH- Zentrum, Zürich, Switzerland (2008)

    Barvinok, A.: Integer Points in Polyhedra. European Math ematical Society, ETH- Zentrum, Zürich, Switzerland (2008)

    work page 2008

  7. [7]

    New Perspect

    Barvinok, A., Pommersheim, J.: An algorithmic theory of l attice points in polyhe- dra. New Perspect. Algebraic Combin. 38 (1999)

    work page 1999

  8. [8]

    In: Proceedings of 1 993 IEEE 34th Annual Foundations of Computer Science

    Barvinok, A.: A polynomial time algorithm for counting in tegral points in polyhedra when the dimension is fixed. In: Proceedings of 1 993 IEEE 34th Annual Foundations of Computer Science. pp. 566–5 72 (1993). https://doi.org/10.1109/SFCS.1993.366830

    work page doi:10.1109/sfcs.1993.366830 1993

  9. [9]

    Rutgers The State University of New Jersey, School of Graduate Studies (2013)

    Gnang, E.K.: Computational aspects of the combinatorial Nullstellensatz method via a polynomial approach to matrix and hypermatrix algebra . Rutgers The State University of New Jersey, School of Graduate Studies (2013)

    work page 2013

  10. [10]

    arXiv pre print arXiv:2310.13788 (2024) Hyperplanes A voiding Problem and Integer Points Counting i n Polyhedra 13

    Gribanov, D., Malyshev, D., Pardalos, P., N, Z.: A new and faster representation for counting integer points in parametric polyhedra. arXiv pre print arXiv:2310.13788 (2024) Hyperplanes A voiding Problem and Integer Points Counting i n Polyhedra 13

    work page arXiv 2024

  11. [11]

    arXiv:2110.0173 2 [cs.CC] (2023)

    Gribanov, D., Shumilov, I., Malyshev, D.: A faster algor ithm for counting the in- teger points number in δ-modular polyhedra (corrected version). arXiv:2110.0173 2 [cs.CC] (2023)

    work page arXiv 2023

  12. [12]

    J ournal of Global Opti- mization pp

    Gribanov, D., Shumilov, I., Malyshev, D., Zolotykh, N.: Faster algorithms for sparse ilp and hypergraph multi-packing/multi-cover problems. J ournal of Global Opti- mization pp. 1–35 (2024)

    work page 2024

  13. [13]

    Optimization Letters 16(7), 1991–2018 (2022)

    Gribanov, D.V., Zolotykh, N.Y.: On lattice point counti ng in δ- modular polyhedra. Optimization Letters 16(7), 1991–2018 (2022). https://doi.org/10.1007/s11590-021-01744-x

    work page doi:10.1007/s11590-021-01744-x 1991

  14. [14]

    Siberian Electronic Mathematical Rep orts (2022)

    Gribanov, D., V., Malyshev, D., S.: A faster algorithm fo r counting the integer points number in δ-modular polyhedra. Siberian Electronic Mathematical Rep orts (2022). https://doi.org/10.33048/semi.2022.19.051

    work page doi:10.33048/semi.2022.19.051 2022

  15. [15]

    Springer Science & Business Media, New York (2009)

    Lasserre, J.B.: Linear and integer programming vs linea r integration and counting: a duality viewpoint. Springer Science & Business Media, New York (2009)

    work page 2009