gpt 6 astra ultra attempt on CS-18

Research-attempt provenance

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 Unique Games instance assigns labels from a finite alphabet to graph vertices, with each edge imposing a permutation relation on the endpoint labels. Its value is the largest fraction of satisfiable edges. The standard conjecture asks whether, for every positive tolerance, a sufficiently large alphabet makes distinguishing near-unit value from near-zero value NP-hard.

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. This repeats the Unique Games target already represented by canonical source records 43 and 30001374.

Source-record limitation: Duplicate Unique Games target, already present under IDs 43 and 30001374.

Related catalogue records: 43, 30001374. Separate source IDs are preserved for their provenance.

Statement recorded in the supplied source.

Is the Unique Games constraint-satisfaction problem computationally hard as asserted by the Unique Games Conjecture? [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

Ask whether nearly satisfiable permutation-constraint instances are hard to distinguish from ones with very low satisfiable value.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30001938 (OWR-11451-013). 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 $2012$, Oberwolfach Reports, DOI 10.4171/owr/2011/53, pp. 3003--3076 https://doi.org/10.4171/owr/2011/53.
• S3 Unique Games research https://arxiv.org/abs/2404.16024.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Preparation and review.

The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30001938 and code OWR-11451-013 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Related canonical identities: 43, 30001374. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Literature and context check

The primary report's Steurer discussion on printed pages 3060--3061 concerns algorithms and SDP hierarchies for Unique Games. The retained record repeats the broader conjecture under separate IDs. This attempt proves a simple exact-consistency algorithm and constructs elementary high- and low-value examples; no approximation-gap hardness reduction or resolution of the Unique Games Conjecture is claimed.

Research attempt: Exact-consistency propagation and the gap to promise hardness

Deciding whether every edge can be satisfied

Let an undirected graph have alphabet $[q]$, with each oriented edge $uv$ carrying a permutation $\pi_{uv}$ and the reverse edge its inverse. Satisfaction means $\ell(v)=\pi_{uv}(\ell(u))$. For each connected component choose a root and a spanning tree. For each of the $q$ possible root labels, propagate labels uniquely along that tree and check every remaining edge. This finds a completely satisfying assignment if one exists: any such assignment has one of the tried root labels and is forced along the tree. Conversely every assignment accepted by the checks satisfies every edge. The work is $O(q(|V|+|E|))$ permutation evaluations and comparisons with explicitly represented permutations. Components are handled independently, so one does not enumerate combinations of their root choices.

Every forest is satisfiable by this construction. A connected graph with $m\geq1$ edges and $n$ vertices has an assignment satisfying at least its $n-1$ tree edges, hence value at least $(n-1)/m$. An isolated vertex is automatically satisfiable and requires no ratio. This is useful near a tree but need not be useful in dense graphs.

Unsatisfiable instances can have value arbitrarily near one

On a cycle of length $m\geq3$ with binary alphabet, put equality constraints on all but one edge and inequality on the last. Full consistency is impossible because traversing the cycle would both preserve and flip the root label. Assigning all vertices the same label violates just the inequality edge, so the optimum value is exactly $(m-1)/m$. Thus the exact-consistency algorithm cannot settle the conjectured promise distinction between near-one and near-zero values: rejecting perfect satisfaction is consistent with values tending to one.

Elementary existence of low-value instances

Fix $0<\beta<1$ and choose $q$ with $\log2<\tfrac12\beta\log q$. On the complete graph on $n$ vertices, choose edge permutations independently and uniformly, using one orientation per edge. For a fixed labeling each edge is satisfied with probability $1/q$, independently. If at least $\beta m$ edges are satisfied, some set of $\lceil\beta m\rceil$ edges are all satisfied. A union bound over edge subsets and all $q^n$ labelings gives \[ \Pr(\exists\text{ labeling of value at least }\beta) \leq q^n2^m q^{-\lceil\beta m\rceil} \leq\exp\left(n\log q+m\log2-\beta m\log q\right). \] For $m=n(n-1)/2>2n/\beta$, this is strictly less than one. Hence there exist instances of value below $\beta$. All permutations can in principle be enumerated to find one, but this argument gives no efficient explicit construction or reduction from an NP-complete problem.

The high-value and low-value families prove that the two promise regimes are mathematically nonempty. Producing both kinds separately does not establish computational difficulty of distinguishing them. A polynomial reduction with both completeness and soundness parameters, for the conjecture's full tolerance quantifiers, remains the missing step.

Verification and adversarial audit

The propagation algorithm tries all root labels and checks non-tree edges, rather than assuming local consistency implies global consistency. The odd parity around a cycle gives exactly one necessary unsatisfied edge. The random low-value proof uses independence across edges for a fixed labeling and a subsequent union bound over labelings; it does not incorrectly assume different labelings' events are independent.

Audit corrections.

Separated perfect-consistency testing from near-perfect promise approximation and distinguished existence of hard-looking instances from a hardness reduction.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The Unique Games Conjecture and its duplicated source target remain unresolved here. Exact satisfiability, elementary density bounds and existence of separated-value examples are auxiliary results, not promise-gap hardness or a contradiction to the conjecture.

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 calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46369 (consulted 2026-10-11).

Model and contributor disclosure

The parent Codex GPT-6 model has reviewed the written mathematical arguments at their declared scopes. This is model-assisted review, not independent human verification. OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.