gpt 6 astra ultra attempt on CS-689

Convexification bundle: closure matters and unrestricted oracle search is exhaustive

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 separating inequality holds for the target integer hull and is violated by a specified outside point. A Chvatal-Gomory cut rounds an appropriate rational combination of linear constraints to an integer-valid bound; RLT forms valid products of bounded constraints.

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 notation $q\in\mathbb R[x]^k$ and $q$ is SOS is ambiguous, and several practical targets lack quantitative criteria. The bundle is retained verbatim, without silently selecting one subproblem or defining the omitted SOS hierarchy.

Source-record limitation: The SOS denominator hierarchy is malformed: its notation is not defined, and zero multipliers make the written condition trivial without the omitted nontriviality restriction.

Statement recorded in the supplied source.

Are the intermediate SOS sets $\Sigma^k_{n,d}=\{p:\exists q\in\mathbb{R}[x]^k,\ q\text{ is SOS and }pq\text{ is SOS}\}$ convex? What is the complexity of selecting $s_i\in S_i$ such that $0\in\operatorname{conv}\{s_0,\ldots,s_d\}$? What are the complexities of finding a separating Chvátal–Gomory inequality and of integer quadratic optimization in dimension $3$? What practical rules govern combined SDP and RLT cuts? What practical algorithm solves evaluation-oracle mixed-integer optimization? Is the convex hull of a polyhedron minus finitely many polyhedra polyhedral? Which convex mixed-integer classes admit exact convexification? [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

Resolve all the stated convexification, selection, cutting-plane, and oracle-optimization questions.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30002962 (OWR-13941-002). 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 Mixed-integer Nonlinear Optimization: A Hatchery for Modern Mathematics $2016$, Oberwolfach Reports, DOI 10.4171/owr/2015/46, pp. 2701--2766 https://doi.org/10.4171/owr/2015/46.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

Are the intermediate SOS sets $\Sigma^k_{n,d}=\{p:\exists q\in\mathbb{R}[x]^k,\ q\text{ is SOS and }pq\text{ is SOS}\}$ convex? What is the complexity of selecting $s_i\in S_i$ such that $0\in\operatorname{conv}\{s_0,\ldots,s_d\}$? What are the complexities of finding a separating Chvátal–Gomory inequality and of integer quadratic optimization in dimension $3$? What practical rules govern combined SDP and RLT cuts? What practical algorithm solves evaluation-oracle mixed-integer optimization? Is the convex hull of a polyhedron minus finitely many polyhedra polyhedral? Which convex mixed-integer classes admit exact convexification?

Scope recovered from the report

The workshop list, printed page 2708, gives distinct SOS, colorful selection, cutting-plane, oracle, and convexification questions. In particular the colorful selection source assumes $0\in\operatorname{conv}S_i$ for every finite color class, a promise omitted from the shortened catalogue. The SOS expression omits a nonzero multiplier condition: if zero is permitted, $q=0$ makes both $q$ and $pq$ sums of squares for every $p$. That literal observation cannot answer the intended denominator hierarchy. We attempt the precisely stated polyhedral set-difference component and then test the unrestricted oracle model.

Ordinary convex hull need not be a closed polyhedron

With the usual convention that a polyhedron is a finite intersection of closed affine half-spaces, take $P=[0,1]\subset\mathbb R$ and remove the polyhedron $Q=\{0\}$. Then $P\setminus Q=(0,1]$ is already convex and is not closed, so its convex hull is not a polyhedron. A finite intersection of closed sets is closed, proving the last implication. This is a counterexample to that literal component, not a resolution of all the other questions in the bundle. It also shows why replacing the convex hull by the closed convex hull would change the statement.

The closed-hull version, with proof.

For any polyhedron $P$ minus finitely many polyhedra $Q_1,\ldots,Q_r$, the closed convex hull is polyhedral (possibly empty). Write each $Q_i$ by finitely many weak linear inequalities. A point outside $Q_i$ violates at least one of them strictly. Distributing these finite choices expresses $P\setminus\bigcup_iQ_i$ as a finite union of cells, each given by weak linear inequalities for $P$ and selected strict linear inequalities. If one $Q_i$ is the whole space the difference is empty; discard empty cells. For a nonempty cell, its closure is obtained by changing its strict inequalities to weak ones. One inclusion follows by continuity. For the other, let $p$ be a fixed point satisfying all strict inequalities and let $x$ satisfy their weak versions together with the constraints of $P$. For $0<t\le1$, $(1-t)x+tp$ satisfies all required strict inequalities and approaches $x$. Thus the closure of each nonempty cell is a polyhedron $R_i$.

It remains to prove that the closed convex hull of a finite union of nonempty polyhedra is polyhedral. Write $R_i=\{x:A_ix\le b_i\}$ and introduce \[ \lambda_i\ge0,\quad \sum_i\lambda_i=1,\quad A_i v_i\le\lambda_i b_i,\quad x=\sum_i v_i. \] The projection $H$ is a polyhedron. Indeed, eliminating a variable from a finite weak linear system preserves that form: constraints with positive and negative coefficients yield finitely many comparisons of its lower and upper bounds; constraints with zero coefficient remain; if only one sign is present, a sufficiently large value in the appropriate direction meets those bounds. Repeated elimination proves the projection assertion and hence closedness. Every convex combination of points in the $R_i$ has this lift, so its closure is contained in $H$.

Conversely take a feasible lift and choose any $p_i\in R_i$. For $\eta>0$, replace \[ \lambda_i\quad\hbox{by}\quad \lambda_i^\eta=\frac{\lambda_i+\eta}{1+r'\eta},\qquad v_i\quad\hbox{by}\quad v_i^\eta=\frac{v_i+\eta p_i}{1+r'\eta}, \] where $r'$ is the number of remaining nonempty polyhedra. All new weights are positive and sum to one, and $A_i v_i^\eta\le\lambda_i^\eta b_i$. Thus $v_i^\eta/\lambda_i^\eta\in R_i$, and $x^\eta=\sum_i v_i^\eta$ is a convex combination approaching $x$. This proves $H$ is exactly the closed convex hull. Finally, replacing the finite cells by their closures does not change their closed convex hull: each closure is contained in any closed convex set containing the cells, and the reverse containment is immediate. The stated closed-hull result follows.

An exact oracle-model obstruction

Let the feasible integer set be $\{0,\ldots,N-1\}$, encoded by binary bounds, and impose no structure on an evaluation-oracle objective $f$. A deterministic algorithm that computes the exact minimum value must query all $N$ points in the worst case. Run it against the all-zero function. If it stops without querying $a$, change only $f(a)$ to $-1$. The query transcript and output are identical, but the minimum value changes from zero to $-1$. Hence one of the two outputs must be wrong. This also shows exponential dependence on the bit length $\log N$ can be unavoidable for this unrestricted model.

For finding a minimizer with randomization, consider the family $f_a$ with unique minimum $-1$ at $a$ and zero elsewhere, with $a$ uniform. For a deterministic procedure making at most $q$ queries, follow its all-zero transcript. It discovers the marked point only for the at most $q$ indices queried on that transcript; if discovery never occurs, its final output can be the right answer for at most one further index. Its success averaged over $a$ is at most $(q+1)/N$. Averaging this inequality over random seeds proves the same bound for every randomized procedure, and therefore some input has success no greater than this average. A uniform success guarantee of $2/3$ requires $q\ge2N/3-1$. This argument assumes neither convexity nor Lipschitz control; it is not a lower bound for promised convex oracle problems. Such promises are precisely what the broad practical question would need to add.

Adversarial audit and gaps

The audit kept ordinary and closed convex hulls separate, removed empty cells before taking closures, and handled unbounded polyhedra by an explicit limiting argument. For oracle search it retained the zero-transcript argument under adaptivity and did not use a seed-dependent adversary as a randomized lower bound. These known mechanisms settle restricted literal components only. They do not decide the intended SOS hierarchy, colorful-selection complexity, Chvatal--Gomory separation, three-dimensional integer quadratic optimization, practical SDP--RLT design, or every exact mixed-integer convexification class. No 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. Several literal or restricted components are clarified, but the intended SOS, selection, cutting-plane, quadratic, practical-oracle, and general convexification bundle remains unresolved.

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 46/2015, open-problem session pp. 2707--2708 and the pooling discussion pp. 2715--2716; exact passages inspected in the primary report. https://doi.org/10.4171/owr/2015/46.

Final status

Unresolved in this attempt. Several literal or restricted components are clarified, but the intended SOS, selection, cutting-plane, quadratic, practical-oracle, and general convexification bundle remains unresolved.