Integer Programming with Bounded Subdeterminants

Bounded subdeterminants: rational vertices and two exponential enumeration traps

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

An integer program optimizes a linear objective over $\{x\in\mathbb Z^n:Ax\leq b\}$ with finitely encoded integer constraint data. A square subdeterminant is the determinant of any square submatrix of $A$. The parameter $\Delta$ bounds their absolute values and is fixed independently of the dimensions. Polynomial time means polynomial in the total binary input length, including $b$ and the objective.

Statement recorded in the supplied source.

For a fixed integer $\Delta\geq3$, can integer programs whose constraint matrices have every square subdeterminant bounded in absolute value by $\Delta$ be solved in polynomial time? [S2]

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Determine whether a constant bound on every constraint subdeterminant makes integer programming polynomial-time solvable.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004899 (OWR-8415356-004). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2022$, Oberwolfach Reports, DOI 10.4171/owr/2021/53, pp. 2893--2954 https://doi.org/10.4171/owr/2021/53.
• S3 Combinatorial Optimization, Oberwolfach Reports 53/2021, primary report PDF https://ems.press/content/serial-article-files/46931. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

For a fixed integer $\Delta\geq3$, can integer programs whose constraint matrices have every square subdeterminant bounded in absolute value by $\Delta$ be solved in polynomial time?

Attempted finite-denominator algorithm

Every square minor is bounded by a fixed $\Delta$, so in particular each entry of $A$ is bounded. It is tempting to enumerate the few possible fractional vertex types or search a bounded integer box. We derive the genuine denominator statement and then show why neither enumeration argument has a polynomial input-length bound.

Vertex denominators are bounded.

At a vertex $x$ of a full-dimensional polyhedron $Ax\le b$, the active row vectors span $\mathbb R^n$. Otherwise choose nonzero $h$ orthogonal to all active rows. Because there are finitely many inactive inequalities, both $x+th$ and $x-th$ remain feasible for sufficiently small $t>0$: choose $t$ below every positive slack divided by the corresponding nonzero directional absolute value. Then $x$ is their midpoint and is not a vertex, a contradiction. Choose $n$ independent active rows, forming an integer nonsingular matrix $B$. The equality $Bx=b_B$ gives $x=B^{-1}b_B=\operatorname{adj}(B)b_B/\det B$. The adjugate entries and $b_B$ are integral. Thus each coordinate denominator divides the nonzero integer $\det B$, whose absolute value is at most $\Delta$. In particular all vertices lie in $D^{-1}\mathbb Z^n$ for $D=\operatorname{lcm}(1,\ldots,\Delta)$. This does not imply a bounded number of vertices or nearby lattice points, or that coordinatewise rounding preserves inequalities.

Fractional-vertex rounding fails already at determinant three.

Minimize $x+y$ subject to \[ 2x+y\ge1,\qquad x+2y\ge1,\qquad0\le x,y\le1. \] The linear optimum is $(1/3,1/3)$ with value $2/3$: adding the first two inequalities gives $x+y\ge2/3$, and that point attains it. The constraint rows are $(-2,-1),(-1,-2),(1,0),(0,1),(-1,0),(0,-1)$. All one-by-one minors have absolute value at most two; the two special rows have determinant three, a special row and a coordinate row give absolute determinant at most two, and two coordinate rows give at most one. Hence every square minor is bounded by three. Rounding both coordinates down gives $(0,0)$, which violates both covering constraints. Rounding both up gives $(1,1)$ of value two, whereas $(1,0)$ and $(0,1)$ are feasible integer points of value one and no integer value below one is feasible. Even this small denominator does not make either uniform rounding rule an exact integer optimizer.

Enumerating all vertices or all box points is not enough.

The cube $[0,1]^n$ has exactly $2^n$ vertices: a point with a coordinate strictly between zero and one is a midpoint of a small coordinate perturbation, whereas a zero-one point cannot be a nontrivial convex combination of other cube points, coordinate by coordinate. Its matrix consists of rows $\pm e_i$ and all minors belong to $\{0,1,-1\}$: a square submatrix with a zero row or repeated nonzero column position has determinant zero; otherwise it is a signed permutation matrix. Thus even the stronger determinant-one promise permits exponentially many vertices. Listing all LP bases or vertices is not polynomial.

Likewise the one-dimensional interval $0\le x\le B$ has a determinant-one constraint matrix and $B+1$ integer points. If $B$ is binary encoded, listing them is exponential in $\log B$. These simple instances are themselves easy to optimize; they disprove only the proposed enumeration bounds, not polynomial solvability of the promised class. A residue-class list of size $D^n$ also has no polynomial bound at fixed $D>1$. We do not claim that all those residue patterns can independently occur under the full minor promise; using this loose list already loses the desired running time.

Audit

The primary bounded-subdeterminant discussion on printed page 2912 was inspected. It treats two nonzeros per row as an additional hypothesis, which is not silently imposed here. The audit checked all minor sizes in the two-variable example, full-dimensionality, binary input length and the distinction between determinant bounds and coordinate bounds. No integer-programming solver or vertex enumerator was run. An algorithm exploiting the global restrictions among all minors, rather than the displayed loose enumerations, remains to be supplied.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. Bounded vertex denominators do not justify rounding or polynomial enumeration; no general fixed-Delta integer-programming algorithm is constructed.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 53/2021, Combinatorial Optimization, original question and surrounding discussion read from the primary PDF text on 11 October 2026. Historical statements are not a current-status survey. https://ems.press/content/serial-article-files/46931.

Final status

Unresolved in this attempt. Bounded vertex denominators do not justify rounding or polynomial enumeration; no general fixed-Delta integer-programming algorithm is constructed.