gpt 6 astra ultra attempt on CS-730

Few-variable semidefinite programs: Newton costs and an infeasibility obstruction

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 semidefinite program optimizes a linear objective subject to affine constraints and positive-semidefinite matrix variables. Symmetry reduction uses invariant subspaces or group orbits to decrease its effective dimensions.

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 program class, input access, required accuracy, and runtime improvement are not specified.

Source-record limitation: Faster symmetry-reduced SDP algorithms are requested without an input class, accuracy, or runtime target.

Statement recorded in the supplied source.

Can the small number of variables in symmetry-reduced semidefinite programs be exploited to obtain faster algorithms? [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

Exploit symmetry-reduced semidefinite formulations to speed up optimization.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004864 (OWR-8415352-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 Geometry and Optimization in Quantum Information $2022$, Oberwolfach Reports, DOI 10.4171/owr/2021/49, pp. 2665--2720 https://doi.org/10.4171/owr/2021/49.
• 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 the small number of variables in symmetry-reduced semidefinite programs be exploited to obtain faster algorithms?

The actual source setting

Gribling's contribution, printed pages 2689--2691, concerns symmetry-reduced noncommutative moment relaxations for mutually unbiased bases. Its table contains very few scalar variables but large matrix blocks, and its final question asks whether that further reduction can be exploited algorithmically. Thus a generic claim that a small variable count makes an SDP small would miss the feature motivating the question. We attempt the log-determinant Newton route, count the costs that survive, and check feasibility issues relevant to proving nonexistence. No improvement for the source moment hierarchy is claimed.

What a small variable count does reduce

Suppose a reduced real symmetric pencil is explicitly supplied as \[ F(x)=A_0+\sum_{j=1}^p x_jA_j =\bigoplus_{k=1}^K F_k(x),\qquad F_k(x)\in\mathbb R^{b_k\times b_k}. \] The same arguments use adjoints for complex Hermitian pencils. At a strictly feasible point set $\Phi(x)=-\log\det F(x)$. Its gradient and Hessian are \[ \partial_i\Phi=-\operatorname{tr}(F^{-1}A_i),\qquad \partial_i\partial_j\Phi= \operatorname{tr}(F^{-1}A_iF^{-1}A_j). \] To justify them, diagonalize $F^{-1/2}AF^{-1/2}$ in $\log\det(F+tA)=\log\det F+\log\det(I+tF^{-1/2}AF^{-1/2})$. Differentiating the resulting sum of logarithms gives the first formula. Differentiating $F^{-1}F=I$ gives $\partial_jF^{-1}=-F^{-1}A_jF^{-1}$ and hence the second. For $A_v=\sum_i v_iA_i$, \[ v^T\nabla^2\Phi\,v =\operatorname{tr}((F^{-1/2}A_vF^{-1/2})^2)\ge0, \] since a symmetric matrix has real eigenvalues and the trace of its square is their squared sum.

A direct dense-arithmetic implementation factors the blocks and forms $F_k^{-1}A_{j,k}$ by triangular solves with matrix right-hand sides. This costs $O((p+1)\sum_k b_k^3)$ operations. The $p^2$ trace products cost $O(p^2\sum_k b_k^2)$, and a nonsingular Newton system in $p$ variables costs $O(p^3)$ by Gaussian elimination. These are straightforward upper counts for this implementation, not lower bounds or an optimal algorithm. Small $p$ helps the last two terms but does not by itself remove block factorization. Also, linear dependence among pencil directions can make the Hessian singular, requiring redundant directions to be removed or an additional optimization prescription. No bit-complexity or iteration bound follows from these local formulas.

A tractable subcase and a surviving input cost

If a simultaneous orthogonal diagonalizing basis for all $A_j$ is supplied, positivity of $F(x)$ is equivalent to one scalar linear inequality for each diagonal coordinate. This follows because conjugation preserves quadratic-form positivity and a diagonal matrix is PSD exactly when every diagonal entry is nonnegative. Thus this promised case becomes an LP in $p$ variables, with $\sum_kb_k$ inequalities. The source's noncommuting blocks do not come with this promise.

Even one variable can retain a linear dependence on the input length. Given $a_i\in\{0,1\}$ for $1\le i\le B$, minimizing $t$ subject to $\operatorname{diag}(t-a_1,\ldots,t-a_B)\succeq0$ has optimum $\max_i a_i$. A deterministic exact entry-query algorithm must inspect all $B$ entries on the zero input: otherwise changing an unread entry to one leaves its transcript unchanged and changes the answer. For randomized bounded-error algorithms, choose the zero input with probability $1/2$ and a uniformly chosen single-one input with probability $1/2$. Fix the algorithmic coins. On the all-zero transcript at most $q$ locations are inspected; with probability $1-q/B$ a single one avoids them. Conditional on avoiding them, the same answer cannot correctly distinguish both inputs. Minimizing the average error on that transcript gives an unconditional error at least $(1-q/B)/2$. Averaging the coins preserves the bound, so error at most $1/3$ on every input requires $q\ge B/3$. This is a classical input-access obstruction, not a quantum lower bound or a lower bound for the specially structured MUB coefficients. It rules out a complexity guarantee depending only on the number of scalar variables for arbitrary supplied pencils.

Why the barrier route does not decide all source-style tasks

A feasible SDP can have no strictly feasible point: the pencil $\operatorname{diag}(t,-t)$ is PSD only at $t=0$, while its log-determinant barrier is undefined everywhere. Thus feasibility cannot simply be equated with finding a barrier minimizer.

An elementary strict infeasibility certificate consists of a PSD matrix $Y$ such that \[ \operatorname{tr}(YA_j)=0\ (1\le j\le p),\qquad \operatorname{tr}(YA_0)<0. \] For a PSD $F(x)$ this is impossible, since $\operatorname{tr}(YF(x))=\operatorname{tr}(Y^{1/2}F(x)Y^{1/2})\ge0$, whereas the certificate makes it negative. But these certificates need not exist for an infeasible pencil. Consider the one-variable example \[ F(t)=\begin{pmatrix}0&1\\1&t\end{pmatrix}. \] Its determinant is $-1$, so it is never PSD. Yet if $Y=\left(\begin{smallmatrix}a&b\\b&c\end{smallmatrix}\right)\succeq0$ annihilates the coefficient of $t$, then $c=0$, and PSD forces $b=0$: otherwise $a+2bs$ takes a negative value on vectors $(1,s)$. Hence $\operatorname{tr}(YA_0)=2b=0$, so no strict certificate of the displayed form exists. The pencil approaches PSD matrices arbitrarily closely: replacing its $(1,1)$ entry by $\delta>0$ and choosing $t=1/\delta$ gives nonnegative principal diagonal entries and determinant zero, hence a PSD matrix, at entrywise distance $\delta$. This verifies the weak-infeasibility mechanism directly.

Audit and precise gap

The attempted Newton reduction supplies a small linear system but still requires large-block matrix work and additional handling of singular or empty interiors. The audit checked that arithmetic counts are upper counts, that the classical lower bound uses an explicit input family, and that a strict dual certificate is not assumed complete. No claim is made that the source's particular MUB pencils realize the pathological examples. Exploiting their extra representation structure, obtaining a runtime improvement, and controlling accuracy remain open in this attempt. 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. No faster algorithm or accuracy/bit-complexity bound for the source symmetry-reduced MUB moment hierarchy is obtained. Few variables leave large blocks, input access and feasibility degeneracies to handle.

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.

• OWR49/2021, Geometry and Optimization in Quantum Information; primary source passages read from cached report, with precise pages identified in each manuscript. https://doi.org/10.4171/owr/2021/49.

Final status

Unresolved in this attempt. No faster algorithm or accuracy/bit-complexity bound for the source symmetry-reduced MUB moment hierarchy is obtained. Few variables leave large blocks, input access and feasibility degeneracies to handle.