{"id":"7785b5e7-178f-407b-95fe-06c8f931b75c","arxiv_id":"2505.01628","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every K≥3, random K-XOR game instances switch from almost surely satisfiable to almost surely unsatisfiable at exactly the K-XORSAT threshold c*_K.","lead":"Random K-XOR games are systems of binary linear equations whose variables are split into K equal blocks, with each equation drawing one variable from each block. This paper proves that the equation-to-block-size ratio where these systems become almost surely unsolvable is exactly the known K-XORSAT threshold.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.1.1 is asserted for k=1 without proof, yet all of Theorem 5.0.1 and the satisfiable side of the main theorem depend on it; PS16's Lemma 4.1 is stated for k≥3. This is the load-bearing gap.","rationale":"I read the paper in good faith and checked the main architecture. The second-moment method, the reduction of solvability to the 2-core, and the maintenance-of-uniformity argument in Section 6 are credible and internally consistent. The key numerical negativity claims for J_K are supported partly by analytic arguments and partly by an unpublished interval-arithmetic notebook; for K>=7 the small-alpha and large-alpha bounds are analytic, and the interval arithmetic affects only finitely many small K. The weakest point is indeed Lemma 3.1.1. PS16's Lemma 4.1 is stated for k>=3, and the paper extends it to k=1 by assertion. Every later bound on E[Z^(ell)] multiplies k=1 versions of this lemma across K blocks, so the entire satisfiable-side 2-core estimate, and therefore the equality of thresholds, rests on this unproved extension. The reader's weakest_assumption identifies the same concern. No internal contradiction or obvious counterexample was found; rather, the paper needs a complete proof of the k=1 case or a citation to a proof. The per-part 2-core concentration taken from [BWZ11] is a secondary extension, and the unpublished notebook is a reproducibility issue, not the core logical gap. For these reasons I recommend keeping the conditional verdict: accept only after the k=1 proof is supplied (and ideally after the notebook is made public).","tokens_in":23756,"tokens_out":37701,"duration_ms":402167,"concrete_test":"Independently re-derive Lemma 3.1.1 for k=1. For the ensemble of functions f:[m]->[n] with all fiber sizes at least 2, write the probability that a fixed l-subset S is critical as a coefficient extraction: P(S critical) = [x^l y^{m-l}] ( sum_{d even, e>=0, d+e>=2} x^d y^e/(d!e!) )^n divided by the total-count coefficient [z^m] (sum_{t>=2} z^t/t!)^n, times the factorial ratio l!(m-l)!/m!. Saddle-point this exact expression and compare the resulting exponential rate with n H_1(alpha,zeta;c) from Eq. (3.1.1), for c=3, alpha in {0.01, 0.1, beta_K, 0.5}, and zeta = zeta_sqrt and zeta = zeta_lin. If the rates differ, Lemma 3.1.1 fails and Theorem 5.0.1 has no valid proof under the current argument.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim that the K-XORGAME threshold equals the K-XORSAT threshold depends on the satisfiable side of the 2-core theorem (Theorem 1.2.2(1)). That side is proved by the second-moment estimate E[sum_ell Z^(ell)_{m,n}] = O(m^{2-K}) in Theorem 5.0.1. Theorem 5.0.1 is obtained by applying Lemma 3.1.1 to each of the K 1-XORSAT blocks. Lemma 3.1.1, however, asserts that Pittel--Sorkin's Lemma 4.1, stated for k>=3, extends to k=1, with the proof being one sentence: the proof in [PS16] works equally well with k>=1 as it does with k>=3. No step of that argument is reproduced, and the k=1 ensemble is combinatorially different: rows are one-hot functions from m rows to n columns, and the 2-core condition forces every column to have degree at least 2. The saddle-point estimate for this ensemble, including the parity condition that a fixed l-subset is critical, needs its own verification. If the resulting exponential rate differs from H_1(alpha,zeta;c) in Eq. (3.1.1), then Proposition 3.0.1, Theorem 5.0.1, and hence Theorem 1.2.2(1) and the satisfiable side of Theorem 1.2.1 are unsupported. The 2-core translation in Section 6 and the second-moment identity in Section 2 are internally consistent; the specific weak point is that the only proof of the k=1 bound is an unsupported assertion. This is a gap, not a known counterexample, and it is exactly the sort of gap that conditional acceptance should require closing.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24127,"tokens_out":7274,"duration_ms":73311,"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":[{"comment":"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.","section":"Section 3.1, Lemma 3.1.1"},{"comment":"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.","section":"Section 6.3, Lemma 6.3.1, Eq. (6.3.1)"},{"comment":"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.","section":"Section 4, Lemmas 4.2.3 and 4.3.1; reference [HH25]"}],"minor_comments":[{"comment":"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.","section":"Section 1.1.2, bullet list"},{"comment":"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).","section":"Equation (3.0.1)"},{"comment":"The sentence beginning 'To ensure Psi_{m,n} is nonempty, m >= 2n_j must hold' is repeated verbatim; please delete the duplicate.","section":"Section 2.2"},{"comment":"In the proof of Lemma 6.4.1 the phrase 'we shows the uniform distribution' should be 'we show the uniform distribution'.","section":"Section 6.4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is close to a publishable proof of an attractive result, but the three gaps identified in the major comments are exactly the kind that a conditional acceptance should require to be closed. I recommend asking the authors to supply a full proof of Lemma 3.1.1, a detailed per-block concentration argument in Lemma 6.3.1, and a publicly accessible version of the interval-arithmetic notebook. If these are provided and the remaining typos are fixed, the paper should be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline here is that the paper delivers what it claims: it proves the K-XORGAME satisfiability threshold exists and equals the K-XORSAT threshold, confirming the conjecture from [WHZ22]. That is a new result, not a re-run of Pittel–Sorkin; the J_K saddle analysis, the piecewise ζ choice, and the 2-core translation are genuinely new machinery.\n\nThe paper does a lot right. The maintenance-of-uniformity proof in Section 6.4 is clean and short. The use of BWZ11 is appropriate, and the reduction from unconstrained games to 2-cores is logical. The presentation is mostly honest about what is and is not checked, which is refreshing.\n\nNow the soft spots, in descending order of weight.\n\nThe big one is Lemma 3.1.1. It states that Pittel–Sorkin's Lemma 4.1 extends to k=1, with the proof being one sentence asserting the argument “works equally well.” That is not a proof, and this is not a cosmetic issue. The k=1 ensemble is a random 2-core matrix with one 1 per row—a random function from rows to columns conditioned on column degree at least 2. The combinatorial probability that a fixed row set is critical, and the saddle-point estimate, need their own verification. Theorem 5.0.1 relies directly on Lemma 3.1.1, and the satisfiable side of the main theorem hangs on Theorem 5.0.1. So the central claim is supported by an unproved assertion. There is no reason to think the claim is false, but it is exactly the sort of thing that must be checked before the result is accepted.\n\nSecond, Lemma 6.3.1 asserts a per-block 2-core size concentration that [BWZ11] supposedly contains in proof. The paper explains why the differential equations are identical for each block, but it does not give the concentration argument. This may be fine, but it needs to be written out or cited precisely.\n\nThird, the interval arithmetic in [HH25] is “available upon request.” The rigorous numerical bounds in Lemmas 4.2.3, 4.2.4, and 4.3.1 cannot be verified from the preprint. The notebook should be posted.\n\nThere are also minor typos; for example, Eq (3.0.1) writes α ln(α/ζ2) where (1−α) ln((1−α)/ζ2) is required.\n\nNo fatal error jumped out. The architecture is credible, and the main theorem is likely true. But the paper is not ready as-is. A referee should ask for a complete proof of Lemma 3.1.1, a public notebook, and the per-part core concentration. Then it would be a solid contribution.\n\nRecommendation: worth serious peer review, conditional on those repairs. I'd bring it to a reading group because the reduction is instructive.","headline":"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.","tokens_in":24681,"tokens_out":4191,"would_cite":true,"duration_ms":38972,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C65","60C05","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The satisfiability threshold for random K-XOR games exists and equals the K-XORSAT threshold for every K≥3.","keywords":["K-XOR games","satisfiability threshold","XORSAT","random constraint satisfaction","second moment method","critical row sets","2-core","K-partite hypergraphs"],"falsifier":"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.","tokens_in":23505,"feed_emoji":"🎲","tokens_out":19223,"duration_ms":156565,"temperature":0.7,"pith_summary":"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.","feed_headline":"Random K-XOR games share XORSAT's exact threshold","feed_subtitle":"A proof shows the satisfiability threshold of random K-XOR games is exactly the known K-XORSAT threshold c*_K.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the k-XORSAT threshold theorem, the second-moment/critical-row-set identity used in Lemma 2.1.1, and the Lemma 4.1 bound whose k=1 extension Lemma 3.1.1 assumes.","marker":"[PS16]"},{"why":"Provides the 2-core size asymptotics for random r-partite hypergraphs quoted as Lemma 6.3.1, giving the post-core ratio ˘m/˘n_j = Q(μ).","marker":"[BWZ11]"},{"why":"Supplies the concentration inequalities used to show each block of the 2-core has the same asymptotic size.","marker":"[Wor95]"},{"why":"The companion computation whose interval arithmetic proves the negativity of J_K on the remaining intervals for K=3 and K=4,5,6.","marker":"[HH25]"},{"why":"Gives the bound on Q' used in Lemma 6.2.1 to order Q^{-1}(K) against the minimum of h_K.","marker":"[CD20]"},{"why":"Origin of the critical-row-set approach relating the second moment of the solution count to zero-sum row subsets.","marker":"[Kol99]"}],"fun_headline_variants":["K-XOR games match XORSAT's exact threshold","Exact threshold proven for random K-XOR games","K-XOR games share XORSAT threshold","Threshold equality: K-XOR games and XORSAT","Proof: K-XOR games hit XORSAT threshold"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["K-XOR games match XORSAT's exact threshold","Exact threshold proven for random K-XOR games","K-XOR games share XORSAT threshold","Threshold equality: K-XOR games and XORSAT","Proof: K-XOR games hit XORSAT threshold"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00023,"raw_usage":{"total_tokens":1471,"prompt_tokens":926,"completion_tokens":545,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":542,"completion_tokens_details":{"reasoning_tokens":467}},"tokens_in":542,"tokens_out":545,"duration_ms":4894,"temperature":1.0,"reasoning_tokens":467,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:15:42.500621+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}