Extension Complexity of Inscribed Fixed-Dimensional Polytopes

Inscribed extensions: slack factorization and why small ordinary rank does not suffice

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 inscribed polytope has all its vertices on one Euclidean sphere. An extension of $P$ is a polyhedron $Q$ together with an affine map projecting $Q$ onto $P$. Extension complexity is the minimum number of inequalities in any such description of $Q$; equations do not count as inequalities. The dimension $d$ is fixed and the constant in $O(\sqrt n)$ may depend on $d$.

Statement recorded in the supplied source.

For every fixed $d\geq2$, does every $d$-dimensional polytope with $n$ vertices on a common sphere have extension complexity $O(\sqrt n)$? [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

Bound how many inequalities are needed in a higher-dimensional description of an inscribed polytope.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004900 (OWR-8415356-006). 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 every fixed $d\geq2$, does every $d$-dimensional polytope with $n$ vertices on a common sphere have extension complexity $O(\sqrt n)$?

Attempt through slack matrices

The primary report asks for every fixed dimension and every inscribed polytope, rather than only a random inscribed polytope. We examine whether the low algebraic rank of its slack matrix proves a short extension. The construction below identifies the extra positivity condition needed and gives a complete obstruction to omitting it.

A nonnegative factorization gives an extension.

Let $P=\operatorname{conv}\{v_1,\ldots,v_n\} =\{x:Ax\le b\}$ be a full-dimensional polytope and put $S_{ij}=b_i-a_i^Tv_j$. Suppose $S=TU$, where both factors are entrywise nonnegative and $T$ has $q$ columns. Define \[ Q=\{(x,y):Ax+Ty=b,\ y\in\mathbb R^q_{\ge0}\}. \] Every projected point of $Q$ satisfies $Ax\le b$, since $Ty\ge0$, and is therefore in $P$. Conversely each vertex $v_j$ lifts with $y=U_{*,j}$ because $Av_j+TU_{*,j}=b$. Convex combinations of these lifts give every point of $P$. Thus the projection is exactly $P$, using only $q$ inequalities besides equations. Finding a nonnegative factorization of inner size $O(\sqrt n)$ would therefore supply the desired bound.

Ordinary rank is much easier: writing rows $(b_i,-a_i^T)$ and columns $(1,v_j)^T$ shows $\operatorname{rank}S\le d+1$. Those factors need not be nonnegative. Discarding that requirement invalidates the implication $Ty\ge0$, so the same formula no longer proves a valid extension.

A complete general lower bound showing the distinction.

The one-vertex case has the trivial bound $1\le2^q$. For $n\ge2$, any extension of a polytope with $n$ vertices described by $q$ inequalities has $n\le2^q$. Here equations may be present and the extension may be unbounded. To prove the claim, for each vertex $v$ choose an objective on $P$ uniquely maximized at $v$. Such an objective exists directly: the compact convex hull of the other vertices does not contain $v$; let $z$ be its closest point to $v$. Differentiating squared distance along the segment from $z$ to any other point $u$ of that hull gives $(v-z)\cdot(u-z)\le0$. Hence the vector $v-z$ strictly separates $v$ from that hull. Pulling this objective back to the extension gives a nonempty exposed face $F_v$ projecting to $v$. Different vertices give different faces.

Every nonempty face of a polyhedron is determined by which of its $q$ defining inequalities hold identically as equalities. For a direct verification in the present exposed-face case, choose a point $x$ in the face at which exactly those common equalities are tight. If every inequality is identically tight, choose any point of the nonempty face. Otherwise obtain such a point by averaging, for each inequality not identically tight, a face point with positive slack. If $y$ in the polyhedron satisfies all the common equalities, then for sufficiently small $t>0$ the point $z=x+t(x-y)$ is feasible: common equalities are preserved and each remaining positive slack at $x$ allows a small perturbation. Since $x$ is a strict convex combination of $y,z$, and the defining linear objective is maximal at $x$, both $y,z$ maximize it too. Thus $y$ lies in the face, proving the characterization. There are at most $2^q$ subsets of inequalities, which proves $n\le2^q$ and $q\ge\log_2 n$.

Regular $n$-gons have all vertices on a circle and ordinary slack rank at most three, yet this bound makes their extension complexities unbounded as $n$ grows. Consequently small ordinary rank, even with the inscribed hypothesis, does not imply an extension with that many inequalities. This does not refute an $O(\sqrt n)$ extension, which is much larger than the lower bound just proved.

The missing step and a baseline construction.

Every $n$-vertex polytope has an $n$-inequality extension using $\lambda_j\ge0$, $\sum_j\lambda_j=1$ and $x=\sum_j\lambda_jv_j$, by the definition of convex hull. The source's random-polytope and planar results do not turn this into a worst-case fixed-dimensional bound by themselves. The route above requires a nonnegative factorization exploiting the common sphere or another explicit construction with the desired size; neither is supplied here.

Audit

The primary discussion on printed pages 2928--2929 was inspected. The audit allows unbounded extensions and uncounted equations in the face argument, and distinguishes ordinary factorization from nonnegative factorization. The reported planar theorem is source context, not a theorem independently proved in this attempt. No factorization search or polytope computation was performed and no current-status or novelty claim is made.

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 exact nonnegative-factorization route is proved, but the common-sphere hypothesis has not yielded a sufficiently small nonnegative factorization or another worst-case extension.

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 exact nonnegative-factorization route is proved, but the common-sphere hypothesis has not yielded a sufficiently small nonnegative factorization or another worst-case extension.