gpt 6 astra ultra attempt on CS-330

Boolean quadric volume: small exact cases, simplex packing, and a failed pairwise model

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.

$x_i\in\{0,1\}$ and $y_{ij}=x_ix_j$ describe the vertices before taking their convex hull. Volume is $d$-dimensional Lebesgue measure in the displayed coordinate space.

A polyhedron is an intersection of finitely many closed affine half-spaces; a polytope is a bounded polyhedron. Its faces are its intersections with supporting hyperplanes.

A Boolean function maps $\{0,1\}^n$ to $\{0,1\}$. A Boolean circuit is an acyclic network of logical gates; a formula is a circuit with no sharing of intermediate gate outputs. Size and depth measure its number of gates and longest gate path.

Statement recorded in the supplied source.

For $n\geq2$, let $P_n$ be the Boolean quadric polytope, the convex hull in dimension $d=n(n+1)/2$ of the $0/1$ points satisfying $y_{ij}=x_ix_j$ for $i<j$. Find a formula or nontrivial upper and lower bounds for the $d$-dimensional volume of $P_n$. [S2]

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-21.

Short English statement

Compute or sharply bound the volume of the Boolean quadric polytope.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30002965 (OWR-13941-005). 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 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.
• S3 Lee--Morris--Speakman, Volume Computation for Sparse Boolean Quadric Relaxations https://arxiv.org/abs/1703.02444.
• S4 Ko--Lee--Steingrímsson, Volume of Relaxed Boolean-quadric Polytopes https://doi.org/10.1016/0012-365X(95)00343-U. 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 $n\geq2$, let $P_n$ be the Boolean quadric polytope, the convex hull in dimension $d=n(n+1)/2$ of the $0/1$ points satisfying $y_{ij}=x_ix_j$ for $i<j$. Find a formula or nontrivial upper and lower bounds for the $d$-dimensional volume of $P_n$.

Coordinates and source baseline

Write $v(a)=(a_i,a_i a_j)_{i<j}$ for $a\in\{0,1\}^n$ and $d=n(n+1)/2$. All volumes below are ordinary $d$-dimensional Lebesgue volumes in these coordinates, not normalized lattice volumes. Lee's report, printed pages 2737--2738, already gives an upper bound from a standard relaxation and explicitly asks for a significant improvement or a useful lower bound. The following elementary constructions do not claim such a general improvement or novelty; they test simplex packing and local models.

A unimodular simplex and an elementary packing bound

The $d+1$ vertices $v(0)$, all $v(e_i)$, and all $v(e_i+e_j)$ form a full-dimensional simplex $S_0$ of volume $1/d!$. With $v(0)$ as origin, first list the singleton columns and then the pair columns. Their coordinate matrix has block form $\left(\begin{smallmatrix}I& B\\0&I\end{smallmatrix}\right)$: each pair column has exactly its own $y_{ij}$ coordinate one. Its determinant is one, proving both dimension and volume.

Flipping any subset of Boolean coordinates induces an affine unimodular map of the entire $x,y$ coordinate space. More explicitly, for a bit vector $c$ put $s_i=1-2c_i$, so \[ x'_i=c_i+s_i x_i,\qquad y'_{ij}=c_i c_j+c_i s_jx_j+c_j s_i x_i+s_i s_jy_{ij}. \] The linear part is block triangular with diagonal entries $s_i$ and $s_i s_j$, so its determinant has absolute value one. On Boolean vertices it realizes bit flips, hence preserves $P_n$. Let $S_c$ be the image of $S_0$. Its $x$ projection lies in the Hamming-centered real ball $\sum_i|x_i-c_i|\le2$, since $S_0$ is a convex combination of vertices of weight at most two. If two centers have Hamming distance at least five, these projected balls are disjoint by the triangle inequality. The associated full simplices are therefore disjoint.

Greedily choose centers in $\{0,1\}^n$, each time removing every vertex within Hamming distance four of the chosen one. This removes at most $B_4(n)=\sum_{j=0}^{\min(4,n)}\binom nj$ centers per step. When all $2^n$ vertices have been removed, the number selected is at least $\lceil2^n/B_4(n)\rceil$, and the selected centers have mutual distance at least five. Adding the volumes of their disjoint simplices yields \[ \operatorname{vol}_d(P_n)\ge \frac{\lceil2^n/B_4(n)\rceil}{d!}. \] This is a baseline packing bound; no assertion that it improves the best known lower bounds is made. The greedy enumeration itself can be exponential.

Exact volumes in dimensions three and six

For $n=2$ the preceding simplex is the whole polytope, so $\operatorname{vol}_3(P_2)=1/6$. For $n=3$, there are eight vertices and dimension six. Their unique affine dependence, up to scale, is \[ \sum_{a:\,|a|\text{ even}}v(a)= \sum_{a:\,|a|\text{ odd}}v(a),\qquad 4=4 \quad\text{for the affine coefficients}. \] Each coordinate appears equally often on both sides. Uniqueness follows because the seven vertices of weights at most two are the affinely independent simplex just proved. Appending a leading one to each vertex gives a $7\times8$ matrix of rank seven. The vector of its signed $7\times7$ minors is in its kernel: expansion of a determinant with a repeated row proves this coordinate by coordinate. Its kernel is the displayed parity relation, and the minor omitting $111$ has absolute value one. Hence every seven-vertex simplex has determinant of absolute value one and volume $1/6!$.

The four simplices obtained by omitting one odd vertex cover $P_3$ with pairwise disjoint interiors. To see coverage, start with any convex representation on all eight vertices. Subtract the minimum of the four odd coefficients from each odd coefficient and add it to each even coefficient. The parity relation preserves both the point and the sum of coefficients, all coefficients stay nonnegative, and at least one odd coefficient is zero. For disjoint interiors, an interior point of one such simplex has a unique representation on its seven vertices, with the omitted odd coefficient zero and all others positive. Any other representation differs by a multiple of the parity relation. Making a different odd coefficient zero would require subtracting a positive quantity from all odd coefficients, making the first zero coefficient negative. Thus it cannot lie in the interior of a different simplex. Boundaries have six-dimensional measure zero, being contained in finitely many lower-dimensional affine hyperplanes. Consequently \[ \operatorname{vol}_6(P_3)=4/6!=1/180. \] The exact script algebra_checks.py independently evaluated all eight seven-vertex determinants using rational elimination and obtained absolute value one in each case. The written proof does not rely on that enumeration.

What pairwise constraints miss

A tempting factorization treats every pair as an independent copy of $P_2$. For three variables, the point $x_1=x_2=x_3=1/2$, $y_{12}=y_{13}=y_{23}=0$ satisfies each pair's inequalities $0\le y_{ij}\le\min(x_i,x_j)$ and $y_{ij}\ge x_i+x_j-1$. But the valid inequality \[ 1-x_1-x_2-x_3+y_{12}+y_{13}+y_{23}\ge0 \] is violated there. Validity follows by evaluating at Boolean weight $k$: its value is $1-k+\binom k2$, which is nonnegative for $k=0,1,2,3$; linearity extends it to the convex hull. Thus pairwise consistency does not supply global volume independence.

A valid but weak product upper bound can still be obtained from disjoint coordinate blocks. Partition the $n$ indices into triples and one remainder of size $r\in\{0,1,2\}$. Projection onto a triple's six internal coordinates lies in $P_3$; if $r=2$ its three internal coordinates lie in $P_2$, and if $r=1$ its single coordinate lies in $[0,1]$. All cross-block $y$ coordinates lie in $[0,1]$. Therefore containment in the product gives \[ \operatorname{vol}_d(P_n)\le(1/180)^{\lfloor n/3\rfloor} \begin{cases}1/6,&r=2,\\1,&r=0\text{ or }1.\end{cases} \] This loses most cross-block structure and is not promoted as a significant improvement over the source's existing relaxation bound.

Audit and remaining scope

The primary abstract arXiv:1703.02444 is by Lee and Skipper; the preserved catalogue author label differs. It discusses sparse graphs and relaxations, not a general complete-graph formula. Only its abstract was inspected. The audit checked the factor $d!$, bit-flip determinants, packing separation, and the complete four-simplex argument for $P_3$. These are known-style auxiliary bounds and low-dimensional calculations. A substantiated new asymptotic bound or general volume formula remains absent.

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 general formula or substantiated new improvement over established volume bounds is obtained; the exact small cases and elementary packing/product estimates are baseline calculations.

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; the relevant original question and surrounding mathematical discussion were read in the cached primary report on 11 October 2026. https://doi.org/10.4171/owr/2015/46.
• Jon Lee and Daphne Skipper, Volume computation for sparse boolean quadric relaxations, version 4; primary abstract and actual authors inspected, general paper proof not audited. https://arxiv.org/abs/1703.02444.

Final status

Unresolved in this attempt. No general formula or substantiated new improvement over established volume bounds is obtained; the exact small cases and elementary packing/product estimates are baseline calculations.