Complexity of Extremality Testing in Infinite Group Problems

Extremality testing: finite active constraints and a succinct large-denominator family

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.

A valid function yields an inequality satisfied by the infinite-group feasible solutions. It is minimal if no pointwise smaller valid function exists and extreme if it cannot be the average of two distinct valid functions. Pseudopolynomial runtime may depend on parameter magnitudes rather than their bit lengths.

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 representation of the valid function and size parameters of the baseline algorithm are source-specific.

Source-record limitation: The baseline algorithm, function representation, and numerical complexity parameters to be optimized are absent.

Statement recorded in the supplied source.

Is the pseudo-polynomial running time of the known algorithms for testing extremality of minimal valid functions in the single-row infinite group problem best possible? [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-21.

Short English statement

Determine whether the cited extremality-testing runtime can be improved.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30002723 (OWR-13353-006). 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 $2015$, Oberwolfach Reports, DOI 10.4171/owr/2014/51, pp. 2873--2932 https://doi.org/10.4171/owr/2014/51.
• S3 Basu--Hildebrand--Koeppel, one-row test https://arxiv.org/abs/1206.2079.
• S4 General two-dimensional test https://arxiv.org/abs/2501.05582.
• S5 Infinite group relaxation survey https://arxiv.org/abs/1410.8584.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

Is the pseudo-polynomial running time of the known algorithms for testing extremality of minimal valid functions in the single-row infinite group problem best possible?

Source scope and attempted finite reduction

Koppe's report, printed pages 2898--2900, discusses rational piecewise-linear functions and the common denominator $q$. It states an oversampling theorem for continuous minimal functions with breakpoints and right-hand side in $q^{-1}\mathbb Z$: fixed oversampling factor at least three relates infinite to finite extremality. We do not prove or assume this theorem as a completed algorithm here. Even granting that bridge, the resulting grid has order $q$ points, whereas the rational breakpoints can have only order $\log q$ bits. Discontinuous and irrational representations require their own hypotheses.

Here is the exact finite linear-algebra step, stated in its explicit scope. On the cyclic group $\mathbb Z/N\mathbb Z$, fix $b\ne0$ and consider the polytope $P$ of vectors $p=(p_r)$ satisfying \[ p_0=0,\quad p_b=1,\quad p_r\ge0,\quad p_r+p_{b-r}=1,\quad p_r+p_s-p_{r+s}\ge0\quad(r,s\in\mathbb Z/N\mathbb Z). \] All subscripts are taken modulo $N$. This system implies $0\le p_r\le1$. Its members yield valid inequalities for every finitely supported nonnegative integer configuration of residue sum $b$: repeated subadditivity bounds its cost below by $p_b=1$. The symmetry equations make each such vector minimal among nonnegative valid vectors below it. Indeed the configuration containing $r$ and $b-r$ has cost at least one under any dominated valid vector, while its cost under $p$ is one; both coordinate deficits must vanish. This argument also covers $r=b-r$ with a repeated element.

For a supplied rational $p\in P$, form homogeneous equations for all displayed equalities active at $p$, together with the homogeneous versions of all permanent equalities. Then $p$ is a vertex of this explicitly defined $P$ if and only if their only solution $h$ is zero. If $h\ne0$, all inactive inequalities have positive slack; because there are finitely many of them, choose $\delta>0$ smaller than slack divided by $|a^Th|$ for each nonzero inactive directional change. The two points $p\pm\delta h$ lie in $P$ and are distinct, so $p$ is not a vertex. Conversely, if $p$ is the midpoint of distinct $u,v\in P$, every active linear inequality at $p$ must be active at both endpoints, since two nonnegative slacks cannot average to zero. Thus $h=u-v\ne0$ solves all homogeneous equations. A nontrivial convex combination can also be converted to a midpoint of a shorter segment, so this is exactly the vertex criterion. There are $N$ unknowns and $O(N^2)$ rows. Exact elimination is polynomial in their explicit rational encoding: minors are sums of at most $N!$ products, so their bit lengths grow by at most a polynomial in $N$ and input bit length. This does not remove dependence on $N$, nor establish the unproved infinite-to-finite correspondence for every source representation.

Large denominators do not themselves force slow decisions

We give a complete known two-slope extremality proof to test the possible inference that a denominator $q$ alone implies an $\Omega(q)$ lower bound. For any $0<f<1$, let $\pi_f$ be one-periodic, with \[ \pi_f(t)=\begin{cases}t/f,&0\le t\le f,\$1-t)/(1-f),&f\le t\le1. \end{cases} \] A valid function here is nonnegative and gives total cost at least one for every finite multiset of reals whose sum is congruent to $f$ modulo one. The definition matches the normalized nonnegative infinite-group setting being used in this auxiliary proof.

First, $\pi_f$ is valid. Define $\psi(t)=\max(t/f,-t/(1-f))$. As a maximum of two linear forms it satisfies $\psi(u+v)\le\psi(u)+\psi(v)$. For $0\le t<1$, the minimum $\min_{z\in\mathbb Z}\psi(t+z)$ is the lesser of $t/f$ and $(1-t)/(1-f)$: other positive lifts are larger than $t$, and other negative lifts have larger absolute value than $t-1$. These two values cross at $f$. Thus this minimum is exactly $\pi_f(t)$, and choosing minimizing lifts for $u,v$ proves periodic subadditivity. Since $\pi_f(f)=1$, repeated subadditivity proves validity. Directly from its two pieces, $\pi_f(t)+\pi_f(f-t)=1$ modulo one, which also proves minimality by the two-element argument above.

Suppose $\pi_f=(\rho_1+\rho_2)/2$ with nonnegative valid functions $\rho_j$. They need not be assumed continuous, piecewise linear or subadditive. For any feasible multiset on which $\pi_f$ has total cost exactly one, validity and averaging force both $\rho_j$ costs to be exactly one. The tight pairs $(r,f-r)$ and $(r,f-r-k)$ for every integer $k$ also force $\rho_j(f-r)=\rho_j(f-r-k)$, so the competitors are one-periodic without assuming it. In particular $\rho_j(f)=1$ and $\rho_j(0)=0$ (the latter also follows from nonnegativity). For $x,y\ge0$, $x+y\le f$, both multisets $(x,y,f-x-y)$ and $(x+y,f-x-y)$ have $\pi_f$-cost one. Subtracting their forced equalities yields $\rho_j(x)+\rho_j(y)=\rho_j(x+y)$. Nonnegativity makes $\rho_j$ monotone on $[0,f]$ under this truncated additivity. Integer subdivision gives $\rho_j(af/b)=a/b$ for $0\le a\le b$. Approximating any $x/f$ above and below by rational numbers and using monotonicity squeezes $\rho_j(x)=x/f$.

For the other interval set $h_j(t)=\rho_j(-t\bmod1)$, $0\le t\le1-f$. Then $h_j(1-f)=1$. If $t,u\ge0$ and $t+u\le1-f$, the multisets $(-t,-u,f+t+u)$ and $(-(t+u),f+t+u)$ both have residue sum $f$ and $\pi_f$-cost one. Their equalities give truncated additivity of $h_j$. The same nonnegative rational-subdivision argument gives $h_j(t)=t/(1-f)$. The two intervals cover the group, so $\rho_1=\rho_2=\pi_f$. This proves extremality against all nonnegative valid functions in this normalized setting.

For $f=1/q$, $q\ge2$, the two pieces and slopes $q,-q/(q-1)$ have $O(\log q)$-bit descriptions. Membership in this explicit family can be checked by rational equality and order tests in polynomial bit time, and the proof immediately certifies extremality. Thus enumerating the full $q$-grid is unnecessary on this family. No inference about arbitrary piecewise-linear inputs follows.

Adversarial audit and remaining scope

The Basu--Hildebrand--Koppe paper's primary abstract and the survey abstract were inspected for the rational-piecewise-linear setting. Their full algorithms and the oversampling theorem are not independently reproved here. The finite vertex criterion and the two-slope argument are known mechanisms, proved explicitly to isolate the missing global compression step. The audit did not assume regularity of the hypothetical splitting functions, did not promote finite-polytope vertices to infinite extremality without a bridge, and did not infer a denominator lower bound from the cost of one algorithm. No numerical computation or theorem prover was used.

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. The coordinating Codex (GPT-6; exact serving revision not exposed) also provided a separate model-assisted written-proof review of this manuscript. This is not independent human verification. 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 optimal bit complexity of general source extremality testing is not determined; finite-grid elimination remains pseudopolynomial and the fast two-slope certificate covers only an explicit family.

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 51/2014; original source passage and surrounding definitions read in the cached primary report on 11 October 2026. https://doi.org/10.4171/owr/2014/51.
• Basu, Hildebrand and Koppe, Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem I; primary abstract inspected for representation and algorithm scope. https://arxiv.org/abs/1206.2079.
• Basu, Hildebrand and Koppe, Light on the Infinite Group Relaxation; primary survey abstract inspected, not the entire algorithmic proof. https://arxiv.org/abs/1410.8584.

Final status

Unresolved in this attempt. The optimal bit complexity of general source extremality testing is not determined; finite-grid elimination remains pseudopolynomial and the fast two-slope certificate covers only an explicit family.