Pith. sign in

REVIEW 3 major objections 4 minor 2 references

The Satisfiability Threshold for K-XOR Games

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The satisfiability threshold for random K-XOR games exists and equals the K-XORSAT threshold for every K≥3.

desk verdict A serious, mostly sound proof that the random K-XOR game threshold equals K-XORSAT's, held back by an unproved k=1 extension and an unreleased notebook. read the letter →

arxiv 2505.01628 v1 pith:VXMG55XP submitted 2025-05-02 math.CO

Jared A. Hughes , J. William Helton This is my paper · ORCID
classification math.CO MSC 05C8005C6560C0505D40
keywords K-XORgamessatisfiabilitythresholdXORSATrandomconstraintsatisfactionsecondmomentmethodcriticalrowsets2-coreK-partitehypergraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that random $K$-XOR games, in which $m$ equations over $K$ blocks of $n$ binary variables each are drawn uniformly, have a sharp satisfiability threshold and that this threshold is exactly the known threshold of the classical $K$-XORSAT problem. Concretely, for $K\ge 3$, if the equation-to-variable ratio $m/n$ lies strictly between $2$ and $c^*_K = h_K(Q^{-1}(K))$, a random instance is satisfiable with probability tending to 1, while above $c^*_K$ it is unsatisfiable with probability tending to 1. Since a perfect classical strategy for a $K$-XOR game is exactly a solution to these linear equations over $\mathbb{Z}_2$, the result determines when random games of this kind admit perfect classical strategies. The proof works through the 2-core of the associated $K$-partite $K$-uniform hypergraph and a second-moment estimate on critical row sets, and it confirms the classical part of a conjecture, inspired by quantum experiments, that the classical 3XOR threshold coincides with the 3XORSAT threshold.

What carries the argument

The engine is the second-moment method on the number of solutions, paired with critical row sets. For a random matrix $A$ and an independent uniform right-hand side $s$, the number $N$ of solutions to $Ax=s$ satisfies $\mathbb{E}[N^2]/\mathbb{E}[N]^2 = \mathbb{E}[X]+1$, where $X$ counts the non-empty subsets of rows of $A$ that sum to zero modulo 2 (Lemma 2.1.1, taken from [PS16]); hence $\mathbb{E}[X]\to 0$ forces satisfiability with probability $1-o(1)$. For 2-core $K$-XORGAME matrices, the paper bounds the expected number $Z^{(\ell)}_{m,n}$ of critical row sets of size $\ell$ by an exponential expression governed by a rate function $J_K(\alpha,\zeta;c)$, then proves $J_K$ is negative on $(0,1]$ through a piecewise choice of the curve $\zeta$: $\zeta_{\mathrm{sqrt}}(\alpha)=(\sqrt{\alpha/(K-1)},1-\alpha)$ near $\alpha=0$, $\zeta_{\mathrm{lin}}(\alpha)=(\alpha,1-\alpha)$ on $[0.99\beta_K,1/2]$, the constant pair $(1-\hat{\delta}_K(c),\hat{\delta}_K(c))$ near $\alpha=1$, and a reflection for $\alpha\ge 1/2$. This yields the total bound $\sum_{\ell=2}^m \mathbb{E}[Z^{(\ell)}_{m,n}] = O(m^{2-K})$, making the satisfiability probability $1-O(m^{2-K})$. The final bridge applies the 2-core size estimates of [BWZ11] and Proposition 6.4.2, a new direct proof that the 2-core of a uniformly random $K$-partite hypergraph is uniform conditioned on its size.

What would settle it

Check the claimed transition directly: for $K=3$ and large $n$, the satisfiability fraction of uniformly random $K$-XORGAME equations should drop sharply near $c^*_3\approx 2.75381$; at the proof level, the $k=1$ extension of the zero-sum-subset bound from [PS16] must also survive a direct check of its exponential rate, since without it Lemma 3.1.1 is unsupported.

Watch

Extended reading notes

Core claim

The central claim, Theorem 1.2.1, is that for $K\ge 3$ the satisfiability threshold for uniformly random $K$-XORGAME equations exists and equals $c^*_K = h_K(Q^{-1}(K))$, where $Q(z)=z(e^z-1)/(e^z-1-z)$ and $h_K(\mu)=\mu/(e^{-\mu}(e^{\mu}-1))^{K-1}$. When $2<\lim m/n<c^*_K$ the system $\Gamma x=s$ is asymptotically almost surely (a.a.s.) satisfiable, and when $\lim m/n>c^*_K$ it is a.a.s. unsatisfiable. The paper reaches this by first proving Theorem 1.2.2, a threshold for random 2-core $K$-XORGAME equations: satisfiable with probability $1-O(m^{2-K})$ when the per-block ratios satisfy $2<\lim m/n_j<K$, and unsatisfiable with probability $O(2^{-(m-|n|)})$ when $\lim m/n_j>K$. It then transfers this to the unconstrained setting using known asymptotics for the size of the 2-core of a random $r$-partite hypergraph together with a maintenance-of-uniformity lemma showing that the 2-core is uniformly distributed conditioned on its size.

Load-bearing premise

The whole estimate rests on the unproven assertion, stated in the proof of Lemma 3.1.1, that the bound on expected zero-sum row subsets from [PS16], proved there for equations with at least three variables per row, remains valid for one variable per row; if that extension fails, the second-moment control of the paper has no support.

Editorial extensions

If this is right

  • For every $K\ge 3$, the satisfiability probability of a uniformly random $K$-XORGAME equation jumps sharply at $c^*_K$: it is $1-o(1)$ for $2<\lim m/n<c^*_K$ and $o(1)$ for $\lim m/n>c^*_K$.
  • In the 2-core model the transition occurs at per-block ratio $K$, with explicit probabilities $1-O(m^{2-K})$ below the threshold and $O(2^{-(m-|n|)})$ above it.
  • The threshold satisfies $c^*_K/K\to 1$ as $K\to\infty$ (for example $c^*_3\approx 2.75381$ and $c^*_9\approx 8.99888$), so for large $K$ a random game stays satisfiable up to nearly one equation per variable in each block.
  • Because a perfect classical strategy for a $K$-XOR game is exactly a solution of the linear system, the theorem determines the classical-strategy satisfiability threshold for random 3XOR games: it equals the 3XORSAT threshold.
  • Equivalently, the result is a sharp phase transition for coloring a random $K$-uniform $K$-partite hypergraph so that each hyperedge receives a prescribed parity of red vertices.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The maintenance-of-uniformity proposition is proved by a counting argument that does not trace the peeling dynamics, so the same direct proof should extend to other random hypergraph ensembles, such as constrained or weighted edge models, where a sequential peeling argument is harder to run.
  • Since $c^*_K/K\to 1$, the effective constraint per block is asymptotically one equation per variable; this suggests that for large $K$ the blocks behave nearly independently and that per-block analyses capture the transition to leading order.
  • The paper is purely classical: its methods say nothing about quantum perfect strategies, so the conjectured equality of the quantum and classical thresholds for 3XOR games remains open and would need separate techniques.
  • A directly testable finite-size prediction follows from the explicit error $O(m^{2-K})$ below the threshold: the transition width should shrink polynomially with exponent $2-K$, which simulations of random $K$-XOR games could check.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proves that the satisfiability threshold for uniformly tiled K-XORGAME equations exists for K>=3 and equals the K-XORSAT threshold c*_K = h_K(Q^{-1}(K)). The proof proceeds by (1) reducing satisfaction of the full system to satisfaction of its 2-core, (2) showing that for a uniformly random 2-core K-XORGAME matrix the expected number of critical row sets is O(m^{2-K}) when the ratio m/n_i lies in (2,K), via a second-moment argument built on an extension of a lemma of Pittel and Sorkin, and (3) translating the 2-core ratios to the original problem using the core-size results of Botelho, Wormald, and Ziviani together with a maintenance-of-uniformity lemma. The paper also contains interval-arithmetic verification for the negativity of the relevant rate function for K=3,4,5,6.

Significance. If fully verified, the result is significant: it establishes the exact sharp satisfiability threshold for a natural random family of XOR games and identifies it with the classical K-XORSAT threshold. The proof has a clean conceptual structure, and the maintenance-of-uniformity result is a useful standalone contribution. The derivation is parameter-free: the threshold is computed from the 2-core threshold and the previously known core-size formula, and no constant is fitted to data. The second-moment/critical-row-set framework is elegant and the paper is honest about its use of external theorems and numerical verification. However, three load-bearing pieces are not yet fully supported in the manuscript, so the central claim is currently conditional on those gaps being closed.

major comments (3)
  1. [Section 3.1, Lemma 3.1.1] The extension of [PS16, Lemma 4.1] from k>=3 to k=1 is asserted in a single sentence: 'The proof in [PS16] works equally well with k>=1 as it does with k>=3.' No step of the argument is reproduced, and the k=1 ensemble is combinatorially different: rows are one-hot functions, the 2-core condition forces every column to have degree at least 2, and the probability that a fixed row subset of size ell is critical must be re-derived for this ensemble. Because Lemma 3.1.1 is applied K times in the proof of Proposition 3.0.1, and because Theorem 5.0.1, Theorem 1.2.2(1), and the satisfiable side of Theorem 1.2.1 all rest on the resulting O(m^{2-K}) bound, this is a load-bearing gap. The authors should either supply a complete proof of Lemma 3.1.1 or give a detailed reduction to the k>=3 argument of [PS16], including the saddle-point estimate and the parity condition for critical row sets.
  2. [Section 6.3, Lemma 6.3.1, Eq. (6.3.1)] The per-part 2-core vertex counts n_j are asserted to follow from the proof of [BWZ11, Theorem 3], but the quoted theorem is stated only for the total number of vertices and edges. The claim that each block has n_j = e^{-mu}(e^mu - 1 - mu)n(1+o(1)) is essential: the proof of Theorem 1.2.1 compares the limits mhat/n_j with K for each j individually. The concentration argument for each block must be written out rather than attributed to the proof of [BWZ11]. In particular, the differential-equation step referenced to [Wor95] needs to be made explicit for the per-block variables, since this is the passage that turns 'the equations for each block are identical' into a rigorous a.a.s. statement for each block.
  3. [Section 4, Lemmas 4.2.3 and 4.3.1; reference [HH25]] The negativity of J_K on the intervals not covered by analytic arguments relies on rigorous interval arithmetic collected in the Mathematica notebook [HH25], which is listed as 'Available upon request'. This is load-bearing for K=4,5,6 in Lemma 4.2.3 and for K=3 in Lemma 4.3.1, and it feeds directly into Proposition 4.4.3 and Theorem 5.0.1. A proof that depends on a notebook that the reader cannot access is not currently verifiable. The authors should provide the notebook as ancillary material, or include in the paper the complete interval-enclosure data (stopping criteria, subdivision counts, and the verified bounds) so that the numerical component can be independently checked.
minor comments (4)
  1. [Section 1.1.2, bullet list] The two inequalities in the displayed threshold statement are reversed: it should read 'If m/n < c*_K then a.a.s. satisfiable' and 'If m/n > c*_K then a.a.s. unsatisfiable', matching Theorem 1.2.1.
  2. [Equation (3.0.1)] The second logarithmic term appears to be missing the factor (1-alpha); for consistency with Eq. (3.1.2), it should read (1-alpha) ln((1-alpha)/zeta_2) instead of alpha ln(alpha/zeta_2). Please correct the displayed formula (and check that Eq. (3.1.1) has the analogous missing parentheses).
  3. [Section 2.2] The sentence beginning 'To ensure Psi_{m,n} is nonempty, m >= 2n_j must hold' is repeated verbatim; please delete the duplicate.
  4. [Section 6.4] In the proof of Lemma 6.4.1 the phrase 'we shows the uniform distribution' should be 'we show the uniform distribution'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the K-XORGAME threshold is derived from external 2-core asymptotics and an independent 2-core satisfiability theorem, with no fitted constant or load-bearing self-citation.

full rationale

The paper's derivation of c*_K is not equivalent to its inputs. The threshold formula c*_K = h_K(Q^{-1}(K)) is obtained by combining the external core-size asymptotics of [BWZ11] (Lemma 6.3.1), which gives the limiting 2-core ratio Q(mu), with Theorem 1.2.2, the paper's own 2-core satisfiability criterion at ratio below or above K. The equality with the K-XORSAT threshold is then a consequence of this chain, not an assumption: no constant is fitted from simulation data, and the earlier same-group experiments [WHZ22] are cited only as motivation and play no role in the proof. The proof does depend on Lemma 3.1.1, which extends Pittel-Sorkin's Lemma 4.1 from k>=3 to k>=1 by a one-sentence assertion rather than a reproduced argument; this is a proof gap and a correctness risk, but not circularity, because the cited external bound has independent content and does not contain the paper's target theorem as an input. Similarly, the interval arithmetic verifications are delegated to the authors' own notebook [HH25]; this raises reproducibility concerns but is not a case of the result being assumed by definition. No step in the derivation reduces the central claim to its own statement, so the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The proof introduces no fitted constants and no new entities. It rests on external results: Pittel-Sorkin's XORSAT machinery (extended to k=1 by assertion), Botelho-Wormald-Ziviani's 2-core sizes for random r-partite hypergraphs, and unpublished interval arithmetic.

assumptions (4)
  • domain assumption [PS16] Lemma 4.1 extends to k=1: the upper bound on E[Y^{(ℓ)}_{m,n,k}] for 2-core boolean matrices with k ones per row holds when k=1.
    Invoked in Section 3.1 to bound each block of a K-XORGAME 2-core; the paper asserts the k≥3 proof transfers to k=1 without giving the argument.
  • domain assumption [BWZ11] Theorem 3 correctly gives the asymptotic size of the 2-core of a random K-partite K-uniform hypergraph, including the per-part concentrations derived in Lemma 6.3.1.
    Used in Section 6.5 to translate the original ratio m/n into the 2-core ratios m̄/n̄_j via Q(µ_K(c)); per-part concentration is claimed to follow from Wormald's differential equations in the cited proof but is not stated explicitly in [BWZ11].
  • ad hoc to paper The Mathematica interval arithmetic checks in [HH25] are correct for K=3,4,5,6.
    The notebook is not publicly provided ('available upon request'), so the numerical verification cannot be independently checked from the preprint.
  • domain assumption Uniform generation of K-XORGAME matrices (one 1 per row in each block) is the appropriate model for random K-XOR game instances and matches the hypergraph model in [BWZ11].
    The equivalence between the random matrix model and the random K-partite K-uniform hypergraph model, stated in Section 6.1, underlies the cores translation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Satisfiability Threshold for K-XOR Games." pith.science (2026). https://pith.science/paper/VXMG55XP

@misc{pith2026250501628,
  author       = {Pith},
  title        = {Pith review of: The Satisfiability Threshold for K-XOR Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VXMG55XP}},
  note         = {Machine review of arXiv:2505.01628}
}
abstract

A $K$-XORGAME system corresponds to a $K$-XORSAT system with the additional restriction that the variables divide uniformly into $K$ blocks. This forms a system of $m$ equations with $K n$ unknowns over $\mathbb{Z}_2$, and a perfect strategy corresponds to a solution to these equations. Equivalently, such equations correspond to colorings of a $K$-uniform $K$-partite hypergraph. This paper proves that the satisfiability threshold of $m/n$ for $K$-XORGAME problems exists and equals the satisfiability threshold for $K$-XORSAT.

Figures

Figures reproduced from arXiv: 2505.01628 by the authors.

Figure 4.1
Figure 4.1. JK(α, ζlin; c) = 1 c LK(α, c) plotted over α ∈ [βK, 1] for c = K ∈ {4, 5, 6}. Lemma 4.2.4. If K ≥ 7, then LK(α, K) < −0.016 for all α ∈ [0.99βK, α∗ K]. Proof. If 0 < α ≤ α ∗ K ≤ 1 2 , then from Equation 5.24 of [PS16], LK(α, K) ≤ H(α) + ln 1 + e −2Kα 2 . (4.2.4) Let αK = 0.99βK and αK = α ∗ K. Note 0 < βK < α∗ K < 1 2 . [PS16] shows αK = α ∗ K is decreasing in K, so αK ≤ α ∗ 7 . Differentiation of ln(KβK) shows KβK … view at source ↗
Figure 4.2
Figure 4.2. JK(α, ζlin(α); c) plotted for c = 2.02, 2.1, 2.3, 2.6, 2.99 and K = 4 over α ∈ [0.99βK, 1]. Table of Contents 12 Index [PITH_FULL_IMAGE:figures/full_fig_p012_4_2.png] view at source ↗
Figure 4.3
Figure 4.3. for a diagram of these rectangles and see the verbal discussion of each one. 2a 2b 3 α 0 0.07 0.99βK 1/2 0.4 λ 0 2.0 2.149... 2.15 Q(λ) 2 3 [PITH_FULL_IMAGE:figures/full_fig_p014_4_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

2 extracted references · 1 canonical work pages

  1. [1]

    For Experiments With Entangled Photons, Establishing the Violation of Bell Inequalities and Pioneering Quantum Information Science

    [Nob22] The Nobel Committee for Physics. “For Experiments With Entangled Photons, Establishing the Violation of Bell Inequalities and Pioneering Quantum Information Science”. In: The Nobel Prizes (2022). [P´ er+08] David P´ erez-Garc´ ıa et al. “Unbounded violation of tripartite Bell in- equalities”. In: Communications in Mathematical Physics 279.2 (2008)...

    arXiv 2022

  2. [2022]

    Satisfiability Phase Transtion for Random Quantum 3XOR Games

    arXiv: 2209.04655 [quant-ph] . [Wor95] Nicholas C. Wormald. “Differential Equations for Random Processes and Random Graphs”. In: The Annals of Applied Probability 5.4 (1995), pp. 1217–1235. doi: 10.1214/aoap/1177004612 . url: https://doi. org/10.1214/aoap/1177004612. Table of Contents 26 Index 7 Appendix: Minor details–For Web Only 7.1 Proof of βK upper b...

    work page Pith review arXiv 1995

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.