Subexponential Completeness Testing for Voronoi Cell Representatives

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 cell representative is a chosen member of a cell orbit under $\Gamma$. Completeness means that every $d$-cell orbit has a representative in the proposed collection. A Voronoi cell complex decomposes the relevant space using the source's Voronoi construction.

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 representation, size parameter, and fixed-versus-variable cell dimension are not specified.

Source-record limitation: The complex/input encoding and size parameter for subexponential complexity are absent.

Statement recorded in the supplied source.

Given a Voronoi cell complex $\operatorname{Vor}_\Gamma$ and a proposed set $C_d$ of representatives of its $d$-cells modulo $\Gamma$, is there a subexponential-time algorithm for deciding whether $C_d$ is complete? [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

Test completeness of the proposed cell representatives in subexponential time.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003267 (OWR-15173-004). 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 Mini-Workshop: Computations in the Cohomology of Arithmetic Groups $2017$, Oberwolfach Reports, DOI 10.4171/owr/2016/52, pp. 2941--2973 https://doi.org/10.4171/owr/2016/52.
• S3 OWR 52 preliminary report https://orbilu.uni.lu/bitstream/10993/29499/1/preliminary_OWR_2016_52.pdf.
• 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 30003267 and code OWR-15173-004 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. 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

Problem 4 in the primary OWR 52/2016 problem session, p. 2971, was read. It asks for subexponential completeness checking but does not specify an encoding, size parameter, or fixed dimension regime. The argument below is a conditional finite-orbit certificate and a failed shortcut. It does not assume without proof that every required Voronoi orbit graph is connected or efficiently enumerable.

Research attempt: Orbit-adjacency closure and an incomplete homology test

A conditional closure certificate.

Let a graph $X$ carry a group action by graph automorphisms. Assume the graph on vertex orbits is connected. Given a nonempty finite set $C$ of orbit representatives, suppose two additional procedures are available: an exhaustive finite list of neighbors of each representative, and an exact orbit-equivalence test. Then $C$ represents every orbit if and only if every neighbor of every member of $C$ is equivalent to a member of $C$.

Necessity is immediate. For sufficiency, if an orbit outside $C$ exists, connect it to an orbit represented in $C$ by a finite path in the orbit graph. Its first edge leaving the represented set comes from some edge $(u,v)$ of $X$, with $u$ equivalent to a representative $c$. Choose a group element sending $u$ to $c$; it sends $v$ to a neighbor of $c$ in the outside orbit, contradicting the assumed exhaustive check. This proof does not require a bound on the number of outside orbits.

If $|C|=M$, the neighbor lists have length at most $D$, listing costs at most $T_N$ per representative, and one equivalence test costs at most $T_E$, the naive certificate costs at most \[ O(MT_N+M^2DT_E). \] Duplicate representatives do not invalidate the criterion, though they waste time. A canonical-form dictionary could improve the membership step, but its construction cost cannot be discarded. If the orbit graph is disconnected, the criterion fails: one whole component passes it while omitting another. In a Voronoi application, the vertices of $X$ would be the desired $d$-cells and the adjacency would need an actual connectedness theorem; an arbitrary face adjacency is not automatically suitable.

Why homological consistency is weaker than completeness.

Let $K$ be a triangular circle, with three vertices and three edges. Let $L$ be obtained by adjoining one new vertex $w$ and one edge joining $w$ to a vertex of $K$. Then $K$ is a proper subcomplex of $L$, but both have Euler characteristic zero and the same integral homology. To see this directly, in the chain complex of $L$ the boundary of the new edge is $w-v$. Replace the vertex basis vector $w$ by $w-v$. The new edge and this new vertex basis vector form a direct two-term summand with boundary multiplication by $1$, leaving the complex of $K$. That summand has zero homology. Thus even exact homology and Euler-characteristic agreement need not certify that every cell was listed. This finite example is an obstruction to a proposed criterion, not a claimed Voronoi counterexample.

The cost cannot be inferred from closure alone.

In a neighbor-query model, even connected graphs can hide a missing leaf at any unchecked listed vertex. On a base path with $M$ listed vertices, an algorithm declaring completeness without querying some vertex's entire neighbor list cannot distinguish the path from the same path with an unlisted leaf attached at that vertex. Therefore exact completeness checking on this family needs at least $M$ such queries in the worst case. This is consistent with polynomial time in an explicit list, but gives no subexponential bound in a different group-rank parameter when $M$ itself may be exponential.

Verification and adversarial audit

The first-exit proof was checked against nontrivial stabilizers, repeated representatives, an infinite orbit graph, and a disconnected graph. The homology example is proved by an explicit integral basis change and does not rely solely on a picture. The query obstruction changes an unchecked adjacency list and keeps the graph connected; no claim is made that this arbitrary graph family arises from the source's Voronoi complexes.

Audit corrections.

Kept the graph certificate conditional and separated it from the arithmetic geometry. Rejected equality of Euler characteristic or homology as a stand-alone completeness certificate.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The relevant orbit graph, its connectedness, exhaustive neighbor enumeration, orbit testing, and their dependence on the intended input size remain to be supplied for the source. A polynomial bound in an already explicit representative list is not automatically subexponential in arithmetic rank. No general Voronoi completeness algorithm meeting the original target is established.

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/46655 (consulted 2026-10-11).

Model and contributor disclosure

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, repository-format review, and written-proof review of this attempt; 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.