Linear Bounds for Minimally Integer-Infeasible Systems

Repeated integer-infeasibility question: a sharp exponential family that fails fixed determinants

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

The constraint matrix $A$ is integral, with rows defining the displayed inequalities. Integer-infeasible means $P\cap\mathbb Z^n=\varnothing$; minimally integer-infeasible means deleting any one inequality produces a set containing an integer point. Full-dimensional means that $P$ has nonempty interior in $\mathbb R^n$. The parameter $\Delta$ is the maximum absolute determinant among all square submatrices of $A$.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The supplied registry flags this extraction as unrecoverable. It is displayed as a literal source fragment; the definitions provide context rather than a replacement formal statement.

Source-record limitation: Source flags the statement as unrecoverable: The official report confirms that this is a duplicate extraction of the minimally integer-infeasible systems problem retained in OWR-8415356-014. No separate clean mathematical statement is supplied; this source ID preserves its provenance.

Related catalogue records: 30004903. Separate source IDs are preserved for their provenance. The source text below is rendered literally where necessary; damaged formulas and composite extracts are not silently repaired into a new mathematical claim. The supplied catalogue marks this record as unrecoverable. Its extract and terminology are documented, but a complete original problem has not been reconstructed.

Statement recorded in the supplied source.

Can we upper bound m as a linear function of n, provided that ∆ is con- stant? Open Problem: Integer infeasible subsystems Robert Weismantel (joint work with Marcel Celaya) [S2]

Source status.

The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

The supplied fragment concerns linear Bounds for Minimally Integer-Infeasible Systems. Its complete mathematical target is not recovered.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004904 (OWR-8415356-015). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications 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 JCTA bounded-subdeterminant bounds https://doi.org/10.1016/j.jcta.2024.106003.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

Can we upper bound m as a linear function of n, provided that ∆ is con- stant? Open Problem: Integer infeasible subsystems Robert Weismantel (joint work with Marcel Celaya)

Duplicate scope and attempted counterexample family

This is the trailing duplicate of the minimally integer-infeasible systems question in record 30004903. The original context on printed page 2943 supplies the omitted matrix, integrality and full-dimensionality hypotheses. We test a natural exponential-facet construction against the crucial fixed-subdeterminant condition. The family has all the other required properties but fails that condition, so it does not disprove the source question.

An exact minimally integer-infeasible system.

For $n\ge2$ and every sign vector $\sigma\in\{-1,1\}^n$, include the inequality \[ 2\sigma\cdot x\le2p(\sigma)-1, \qquad p(\sigma)=|\{i:\sigma_i=1\}|. \] There are $2^n$ integral rows. Writing $c=(1/2,\ldots,1/2)$, the inequalities become $\sigma\cdot(x-c)\le(n-1)/2$ for every sign vector. The maximum of $\sigma\cdot y$ over all signs is $\sum_i|y_i|$, obtained by choosing the sign of each coordinate independently. Thus their intersection is exactly \[ P=\{x:\sum_i|x_i-1/2|\le(n-1)/2\}. \] It has nonempty interior because the center satisfies every inequality strictly and the radius is positive. Every integer coordinate has distance at least $1/2$ from $1/2$, so every integer vector has total distance at least $n/2$ and lies outside $P$.

For each row $\sigma$, let $z_\sigma$ have coordinate one where $\sigma_i=1$ and zero otherwise. It violates its own row, since $2\sigma\cdot z_\sigma=2p(\sigma)$. For another sign vector $\tau$, let $h$ be the number of positions where it differs from $\sigma$. Directly counting positive and negative positions gives $\tau\cdot z_\sigma=p(\tau)-h$. If $\tau\ne\sigma$ then $h\ge1$, whence $2\tau\cdot z_\sigma\le2p(\tau)-2<2p(\tau)-1$. Thus deleting row $\sigma$ admits the integer point $z_\sigma$. Every row is essential and the system is minimally integer-infeasible, with $m=2^n$ and entries all in $\{-2,2\}$.

The determinant promise destroys this counterexample route.

Bounded entries are not bounded subdeterminants. For $n=2^s$, define the sign matrix $H_1=(1)$ and recursively \[ H_{2r}=\begin{pmatrix}H_r&H_r\\H_r&-H_r\end{pmatrix}. \] Block multiplication shows inductively that $H_nH_n^T=nI$. Taking determinants gives $|\det H_n|=n^{n/2}$. Its rows are sign vectors and are distinct, since nonzero orthogonal rows cannot coincide. Consequently the full constraint matrix contains the square row submatrix $2H_n$, whose determinant has magnitude $2^n n^{n/2}$. Therefore its maximum subdeterminant $\Delta$ tends to infinity along these dimensions, even though every entry has magnitude two.

The exponential number of essential inequalities proves only that one cannot replace the source's bound on every minor by a bound on individual coefficients. The inequality $m\le nf(\Delta)+g(\Delta)$ allows arbitrary growth in $\Delta$, so this family with growing $\Delta$ contradicts no such bound. A valid negative construction would need infinitely many dimensions with one common determinant bound; no such construction is obtained here.

Audit

The original source paragraph and duplicate provenance were inspected. The audit checked full-dimensionality, integrality of right sides, every deleted-row witness and the actual large minor, not just entry bounds. All arguments are exact hand calculations; no determinant enumeration was run. This is a classical-style sharp parity family used to diagnose a failed counterexample route, not a new independent problem or a disproof of the original fixed-$\Delta$ question.

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. The exponential essential-inequality family has unbounded higher minors, so it cannot resolve the original fixed-Delta linear-bound question.

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. The exponential essential-inequality family has unbounded higher minors, so it cannot resolve the original fixed-Delta linear-bound question.

Minimal integer infeasibility: a complete parity bound and where determinant information is lost

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.

The constraint matrix $A$ is integral, with rows defining the displayed inequalities. Integer-infeasible means $P\cap\mathbb Z^n=\varnothing$; minimally integer-infeasible means deleting any one inequality produces a set containing an integer point. Full-dimensional means that $P$ has nonempty interior in $\mathbb R^n$. The parameter $\Delta$ is the maximum absolute determinant among all square submatrices of $A$.

Statement recorded in the supplied source.

Let $P=\{x\in\mathbb R^n:Ax\leq b\}$ be full-dimensional and minimally integer-infeasible, and let $\Delta$ be the maximum absolute subdeterminant of $A$. Do functions $f$ and $g$ exist such that the number $m$ of inequalities satisfies $m\leq nf(\Delta)+g(\Delta)$? [S2]

Scope qualification.

The source's subdeterminant-parameter setting uses an integral constraint matrix. The functions $f,g$ are independent of $n,m$ and the particular system; their quantitative growth is not prescribed in the supplied question.

Source status.

The supplied catalogue labels this record open. 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

Bound the number of essential inequalities excluding every integer point in terms of dimension and subdeterminant size.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004903 (OWR-8415356-014). 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

Let $P=\{x\in\mathbb R^n:Ax\leq b\}$ be full-dimensional and minimally integer-infeasible, and let $\Delta$ be the maximum absolute subdeterminant of $A$. Do functions $f$ and $g$ exist such that the number $m$ of inequalities satisfies $m\leq nf(\Delta)+g(\Delta)$?

A witness-expansion route

The target asks for a bound linear in dimension when every minor is bounded. We reconstruct the general exponential parity bound, including the facet-witness construction needed to make the midpoint argument valid, and locate the exact place where it fails to use the determinant promise. This is a rederivation of the classical integer Helly mechanism, not a new linear bound.

Deletion witnesses and an integer-free enlargement.

Write the original inequalities as $a_i\cdot x\le b_i$, with $a_i,b_i$ integral, and suppose deleting any one row admits an integer point $z_i$. Thus $z_i$ satisfies all rows except possibly row $i$. Since the full system has no integer point, $a_i\cdot z_i\ge b_i+1$. Start with enlarged right sides $c_i=b_i+1/2$. The open system $a_i\cdot x<c_i$ for every $i$ still contains no integer point: for an integer point these strict inequalities imply $a_i\cdot x\le b_i$ by integrality. Moreover $z_i$ satisfies all the other enlarged inequalities strictly, since $a_j\cdot z_i\le b_j<c_j$ for $j\ne i$.

Process indices $i=1,\ldots,m$. At its step consider the nonempty set of integer points satisfying all current inequalities other than $i$ strictly. It is nonempty because it contains the original $z_i$: right sides have only increased. Their integer values $a_i\cdot z$ are bounded below by the current $c_i$, since a smaller value would put $z$ in the integer-free open system. Hence these values have a smallest integer $t_i$, attained by some point $y_i$. Replace $c_i$ by $t_i$. This is an enlargement, and it preserves absence of integer points in the open system by the definition of the minimum. The point $y_i$ now lies on boundary $i$ and strictly inside every other current inequality. Later right-side increases preserve those strict inequalities, so in the final system \[ a_i\cdot y_i=c_i, \qquad a_j\cdot y_i<c_j\quad(j\ne i). \] Each step is an existence construction; no efficient search for the minimizing integer point is asserted.

The parity argument, now valid.

If two of the $m$ points $y_i,y_j$ were congruent coordinatewise modulo two, their midpoint $u=(y_i+y_j)/2$ would be integral. For row $i$ one endpoint is on its boundary and the other is strictly below it, so the midpoint satisfies that row strictly. The same holds for row $j$, and every other row is strict at both endpoints. Thus $u$ belongs to the final open system, contradicting integer-freeness. The points occupy distinct classes of $\mathbb Z^n/2\mathbb Z^n$, of which there are $2^n$. Consequently $m\le2^n$. The proof does not actually need full-dimensionality beyond the original setting's promise.

Why directly averaging the original witnesses is invalid.

Original deletion witnesses are outside their own halfspace, rather than on its boundary. For a row $i$, one witness may violate it by more than the slack of another, so their midpoint need not satisfy it. An explicit full-dimensional example with integral data is $3x\le2$ and $-3x\le-1$. The interval $[1/3,2/3]$ is full-dimensional in one dimension, integer-free and minimal. Deletion witnesses can be chosen as $z_1=10$ and $z_2=0$, both even, but their midpoint five still violates the first inequality. Thus parity of arbitrary deletion witnesses alone cannot prove the theorem. The boundary construction is essential.

The determinant gap.

The proof above counts all $2^n$ parity classes and never uses $\Delta$. Merely observing that entries of $A$ lie in $[-\Delta,\Delta]$ gives at best $(2\Delta+1)^n$ possible rows, again exponential. Repeated rows are unnecessary in a minimal system: the weaker of two identical-left-side inequalities is redundant, and equal ones can also be deleted. But deleting duplicates does not turn that exponential row count into the requested linear bound. A useful extension must constrain the possible facet-witness or row configurations using the bounds on all higher minors, not just parity or entry sizes. No such argument is established here.

Audit

The primary question on printed page 2943 was inspected, including integrality of both $A$ and $b$. The audit checked existence and attainment of each integer minimum in the enlargement, strictness of all other facets, preservation under later steps, and the distinction between open enlarged systems and the closed original one. All steps are hand proofs, with no integer-feasibility oracle or finite enumeration used. The requested linear-in-$n$ bound for fixed general $\Delta$ remains unresolved in this attempt.

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. The complete classical exponential parity bound uses no higher-minor information; the missing determinant-sensitive argument needed for a linear bound is not supplied.

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. The complete classical exponential parity bound uses no higher-minor information; the missing determinant-sensitive argument needed for a linear bound is not supplied.