Universal-Cover Isomorphism Algorithms for Cube Complexes

Research-attempt provenance

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.

A cube complex glues Euclidean cubes along faces by their stated identifications. Nonpositive curvature is the usual local link condition. The universal cover is its simply connected covering complex; isomorphism preserves the chosen cubical structure.

Statement recorded in the supplied source.

Is there an algorithm that, given two finite nonpositively curved cube complexes, decides whether their universal covers are isomorphic? [S2]

Scope qualification.

The distinction between cubical isomorphism and metric isometry is not made explicit by the supplied question; the source's convention is required.

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

Short English statement

Decide whether two finite nonpositively curved cube complexes have isomorphic universal covers.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30006621 (OWR-14299911-023). 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 Median Geometry and Applications $2026$, Oberwolfach Reports, DOI 10.4171/owr/2026/8, pp. 487--540 https://doi.org/10.4171/owr/2026/8.
• S3 OWR report https://ems.press/content/serial-article-files/53603. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30006621 and source code OWR-14299911-023 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

Problem 10 on printed p. 532 of the primary report asks about finite nonpositively curved cube complexes and explicitly records that the graph case is known through color refinement. The graph algorithm reconstructed below is therefore known special-case mathematics. Its failure to account for higher-dimensional cells is tested by an explicit pair of cube complexes.

Research attempt: A finite graph-cover algorithm and the missing cube data

First let $G,H$ be finite connected simple graphs. The universal cover of a graph, rooted over a vertex $r$, is the tree of finite nonbacktracking walks starting at $r$: an edge either appends one step without immediately reversing the last step or removes the last step. Each vertex other than the root has one predecessor, so this graph is connected and has no cycles; projection to the walk endpoint gives a local bijection of incident edges, hence a covering tree.

Construct a finite state system from all directed edges $(u,v)$ of $G$ and $H$, together with a root state for one fixed vertex $r$ of $G$ and root states for every vertex of $H$. A directed-edge state $(u,v)$ has successors $(v,w)$ for all neighbors $w\ne u$. A root state at $v$ has successors $(v,w)$ for every neighbor. These successor trees are exactly the forward branches of the rooted covering trees. Let $D$ be the total number of states; $D\geq1$ includes isolated one-vertex graphs.

Initially give all states the same color. Repeatedly assign a common canonical new color to the pair consisting of the old color and the multiset of successor colors. Two states have equal colors after $t$ rounds if and only if their rooted successor trees truncated at depth $t$ are isomorphic. The proof is induction: at the next depth, rooted trees are isomorphic precisely when their child subtrees can be paired by equal isomorphism types. Retaining the old color is redundant for this characterization but makes refinement explicit.

Every strict refinement increases the number of color classes, at most $D$, so stability occurs after at most $D$ rounds. At stability, equally colored states have equal successor-color multisets. Choose a bijection pairing their successors by color, then do the same recursively at each paired descendant. These choices give compatible isomorphisms at every depth, whose union is an isomorphism of the infinite rooted trees. Conversely a rooted tree isomorphism preserves every finite-depth color. Thus stable equality is equivalent to rooted universal-cover isomorphism.

Finally compare the fixed root state of $G$ with every root state of $H$. An unrooted cover isomorphism sends the chosen lift of $r$ to a lift of some vertex $v$ of $H$, producing one of these rooted comparisons. The covering tree rooted at any lift of $v$ has the same nonbacktracking-walk description, by unique lifting of paths. Conversely a successful rooted comparison is already an unrooted isomorphism. This proves a finite decision algorithm for this graph subclass. With at most $D$ successors per state, sorting and comparing signatures each round gives a coarse bound $O(D^3\log(D+1))$ elementary comparisons.

Why the one-skeleton algorithm cannot solve the cube problem.

Take the boundary of a square as a one-dimensional cube complex, and the filled square as a two-dimensional cube complex. Their one-skeleta are identical four-cycles. Both are nonpositively curved in the link sense: at a boundary vertex of the one-dimensional complex the link is two isolated vertices, a flag complex; at a vertex of the filled square the link is a single edge, also flag. The boundary has universal cover an infinite path, as is seen by unwinding successive edges. The filled square is contractible by linear contraction to its center, hence is its own universal cover. These covers are not isomorphic, even in dimension. Any algorithm discarding the square cell sees the same input in both cases and cannot distinguish them. A general procedure must incorporate cell incidence and its consequences for lifted paths, beyond this finite directed-edge refinement.

Verification and adversarial audit

The state set includes root states explicitly, allowing different root valences and the one-vertex graph. Stable finite colors are promoted to a genuine infinite-tree isomorphism by compatible child bijections, not only agreement of finite ball counts. The unrooted comparison quantifies over every possible projected target root. The counterexample checks the flag-link condition on both cube complexes.

Audit corrections.

Preserved the distinction between graph covers and cube-complex covers and justified the finite-to-infinite isomorphism step explicitly.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The original algorithmic problem for general finite NPC cube complexes remains unresolved. The source already identifies the graph case as known; the explicit cell-loss counterexample prevents crediting a graph-only algorithm as a solution.

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

Model and contributor disclosure

Codex GPT-6 completed written-proof review of this attempt at its declared scope; this is model-assisted review, not independent human proof checking.

Material model collaboration.

Root Codex GPT-6 supplied the finite directed-edge/root refinement algorithm, its infinite-tree and unrooted correctness proof, and the square-boundary versus filled-square obstruction. The gpt-6-astra author inspected and reworked these arguments; this is model-assisted mathematical work, 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.