Algebraic Complexity of Borel Constraint Problems

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 finite relational structure $D$ consists of a finite set and specified relations. A homomorphism preserves every relation; the product $D^4$ has coordinatewise relations. A Borel CSP instance has a standard Borel space of variables and Borel relations of the prescribed signature; a solution is a Borel homomorphism into $D$. The notation $\operatorname{CSP}_B(D)$ denotes the source decision problem for coded instances. A $\boldsymbol{\Sigma}^1_2$ set is a projection of a coanalytic set; completeness uses the coding and reductions of the cited descriptive-set-theoretic formulation. The displayed identity is required for every $a,r,e\in D$.

Statement recorded in the supplied source.

For a finite relational structure $D$, absence of a homomorphism $f:D^4\to D$ satisfying $f(a,r,e,a)=f(r,a,r,e)$ makes $\operatorname{CSP}_B(D)$ $\boldsymbol{\Sigma}^1_2$-complete. Is the converse true? Can Borel complexity, efficient local solvability for directed graphs, and extension to all locally checkable labelings be characterized algebraically? [S2]

Scope qualification.

The first sentence records the supplied antecedent theorem, rather than claiming it is an open conjecture. The converse is the definite question; the remaining characterization directions retain the source-specific graph and reduction conventions.

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

Does the absence of the stated four-variable algebraic operation exactly characterize the hardest Borel constraint problems, and can the same algebra explain local solvability?

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30005027 (OWR-9790359-008). 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 Mini-Workshop: Descriptive Combinatorics, LOCAL Algorithms and Random Processes $2023$, Oberwolfach Reports, DOI 10.4171/owr/2022/8, pp. 429--455 https://doi.org/10.4171/owr/2022/8.
• S3 LCLs in rooted trees https://doi.org/10.1007/s00446-022-00435-9. 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 30005027 and source code OWR-9790359-008 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

I read Thornton's primary discussion on page 450, including the displayed four-variable identity and the precise one-way complexity theorem. The question is about the complexity of the set of Borel-solvable instances, not whether all classically satisfiable instances have Borel solutions. The example below is a concrete obstruction to confusing those two assertions; it is not a counterexample to the requested converse.

Research attempt: A Siggers operation with a measurable-selection obstruction

A template satisfying the identity.

Let $D=\{0,1\}$ with the binary disequality relation. Define $f(x_1,x_2,x_3,x_4)=x_2\mathbin\oplus x_3\mathbin\oplus x_4$, where $\oplus$ is addition modulo two. A related pair of tuples in $D^4$ differs in every coordinate. Complementing all three used inputs complements their XOR, so $f$ preserves disequality and is a homomorphism $D^4\to D$. Moreover \[ f(a,r,e,a)=r\oplus e\oplus a=f(r,a,r,e). \] Finite CSP instances for this template are ordinary bipartiteness problems: assign one vertex color zero in each component and propagate the opposite color across edges; an inconsistency is an odd closed walk and certifies unsatisfiability. On a finite graph this breadth-first procedure terminates in linear time in its vertices and edges, and if it has no inconsistency every edge has opposite endpoint colors.

A product-shift fact with a direct proof.

On $\Omega=\{0,1\}^{\mathbb Z}$ with independent fair-coordinate product measure $\mu$, let $T$ be the coordinate shift. The map $T^2$ is ergodic. Here is the needed proof. Events determined by finitely many coordinates become independent of their $T^{2j}$ translates once the coordinate sets are disjoint. Every measurable event can be approximated in measure by such events: the class of approximable events contains finite-coordinate events, is closed under complements, and is closed under countable unions by first taking a finite union whose difference in measure from the full union is small. This proves the claim for the sigma algebra they generate, and null-set completion does not change it. Approximating two events and using $\mu(E\mathbin\triangle F)$ to bound the error in an intersection proves $\mu(E\cap T^{-2j}E)\to\mu(E)^2$. If $E$ is $T^2$-invariant up to null sets, the left side equals $\mu(E)$; hence $\mu(E)\in\{0,1\}$.

A Borel instance with no measurable solution.

Remove the periodic sequences from $\Omega$. They form a countable null set: for each positive period there are finitely many periodic binary sequences, and each individual sequence has probability zero because specifying $N$ coordinates has probability $2^{-N}$. On the remaining invariant Borel set, join $x$ to $Tx$. Each component is a bi-infinite path. If a measurable proper two-coloring $c$ existed, then $c(Tx)=1-c(x)$ and $c(T^2x)=c(x)$. The event $E=\{c=0\}$ would be $T^2$-invariant, hence have measure zero or one by the proved fact. Shift invariance and the color flip would also give $\mu(E)=1-\mu(E)$, a contradiction. In ordinary set theory with choice the graph is two-colorable by selecting a representative in each orbit and assigning the parity of its shift index. The missing measurable representative is precisely what the finite propagation argument does not furnish.

This example simultaneously has an explicit required algebraic operation, tractable finite instances, and a classically solvable Borel instance without a Borel solution. None of these facts determines whether the set of codes for its Borel-solvable instances is $\boldsymbol\Sigma^1_2$-complete. That descriptive complexity assertion has different quantifiers and requires a reduction or an upper-class theorem, neither supplied here.

Verification and adversarial audit

The operation was evaluated on both sides of the source identity and checked against the product relation. Periodic points are removed to make every orbit free. The measure obstruction rules out even measurable colorings, and hence Borel ones, without confusing ordinary choice-based solvability with Borel selection. The distinction from the source converse is stated explicitly.

Audit corrections.

Avoided presenting lack of a Borel coloring as a counterexample to a complexity-class converse. Supplied the ergodicity argument and the precise four-ary operation instead of invoking an unspecified tractability principle.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The route falsifies a tempting but stronger interpretation of an algebraic criterion. It proves no upper bound on the descriptive complexity of $\operatorname{CSP}_B(D)$, no converse dichotomy, and no algebraic characterization of directed LOCAL algorithms or all LCLs.

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/46944 (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. 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.