Operator solutions of linear systems and small cancellation

Lu-Ming Zhang; William Slofstra

arxiv: 2412.10305 · v2 · pith:BG2JMUEZnew · submitted 2024-12-13 · 🪐 quant-ph · math.CO· math.GR

Operator solutions of linear systems and small cancellation

William Slofstra , Lu-Ming Zhang This is my paper

Pith reviewed 2026-05-23 06:45 UTC · model grok-4.3

classification 🪐 quant-ph math.COmath.GR

keywords quantum solutionslinear systemssmall cancellationnonlocal gamescommuting-operator strategiesgraph girthincidence systemsoperator solutions

0 comments

The pith

Graphs with min degree 3 and girth 6 (or degree 4 and girth 4) have quantum operator solutions for their incidence systems over every Z_p.

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

The paper proves that any graph meeting one of two degree-girth pairs produces an incidence system that admits operator solutions over Z_p, for arbitrary vertex weights and any p at least 2. These solutions may live in infinite-dimensional Hilbert spaces and are constructed inductively once small-cancellation conditions are verified. A reader cares because the same systems, when p is an odd prime, yield linear-system nonlocal games that possess perfect commuting-operator strategies yet lack perfect classical strategies. The argument therefore supplies an explicit combinatorial source of quantum-classical separations in a well-studied class of games.

Core claim

If a graph has minimum vertex degree at least d and girth at least g for (d,g) equal to (3,6) or (4,4), then the incidence system of the graph admits a (possibly infinite-dimensional) quantum solution over Z_p for every choice of vertex weights and every integer p greater than or equal to 2. In particular, when p is an odd prime the corresponding linear-system nonlocal game has a perfect commuting-operator strategy but no perfect classical strategy.

What carries the argument

The incidence system of the graph, presented so that the girth guarantees small-cancellation hypotheses and thereby permits an inductive construction of operator solutions.

If this is right

The incidence systems give linear-system nonlocal games with perfect commuting-operator strategies but no perfect classical strategies when p is an odd prime.
Quantum solutions exist for every choice of vertex weights once the graph meets the degree-girth condition.
Solutions may be realized in infinite-dimensional spaces.
The same combinatorial condition produces examples for every prime modulus p at least 2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The construction may extend to other degree-girth pairs if analogous small-cancellation arguments can be found.
The resulting games supply infinite families of examples separating classical from commuting-operator value in linear-system games.
One could test whether the operator solutions remain finite-dimensional for particular graphs or weights.

Load-bearing premise

The girth condition is enough to ensure the small-cancellation hypotheses hold for the presentation coming from the incidence system.

What would settle it

Exhibit a graph satisfying one of the two (d,g) pairs whose incidence system over some Z_p admits no operator solution for some choice of weights.

Figures

Figures reproduced from arXiv: 2412.10305 by Lu-Ming Zhang, William Slofstra.

**Figure 1.** Figure 1: The graph K33 with edges oriented from top to bottom, and a picture for the incidence system of K33 corresponding to the double cover of K33. to allow other vertex and edge sets, and index the rows and columns of I(D) by the vertices and edges respectively. In this case, we use vertex set W = {1, 2, 3, a, b, c}. The Mermin-Peres magic square is the incidence system I(K33)x = b, where b ∈ Z W is a vector wi… view at source ↗

**Figure 2.** Figure 2: If two vertices in a common face have the same label x, then we can contract the vertices to a single vertex to get a picture with the same phase but fewer vertices. v e1 e2 e ′ a(e ′ ) = a(e1) v e3 e1 e2 f1 a(f1) = a(e1) f2 a(f2) = a(e2) [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: If v has two or three incident edges with the same label, then we can delete v and replace the incident edges with the dotted edges to get a smaller picture with the same phase. Proof. For part (a), if s(e) = t(e) = v, then e contributes x a(e) h(e) · x −a(e) h(e) = 1 to the product in Equation (2.1), and hence P \ e will be a picture with the same phase. So if P is minimal, then P does not have loops. Sim… view at source ↗

**Figure 4.** Figure 4: If we have a cycle where all edges have the same label, we can delete one of the edges and adjust a(ei) for the remaining edges ei to get a picture with the same phase. v is incident to three edges e1, e2, and e3, then a(e1) + a(e2) + a(e3), and we can again delete v and replace e1, e2, and e3 with two edges f1 and f2 such that s(f1) = s(e1), s(f2) = s(e2), t(f1) = t(f2) = s(e3), h(f1) = h(f2) = h(e1), a(f… view at source ↗

**Figure 5.** Figure 5: The graph D17, which does not have a planar 2-cover. c 3 1 a d 4 2 4 2 b a 1 3 1 3 c 2 4 b d b c a d [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗

**Figure 6.** Figure 6: A picture showing that J 2|b| = 1 in Γp(I(D17), b). k(v) = b(h(v)). With these labellings, P is a picture for Γp(I(D17), b) with phase 2|b|. If |b| = 1, then this picture shows that J 2 = 1 in Γp(I(D17), b) for all 2 ≤ p ≤ +∞, even though D17 does not have a planar 2-cover. Note that if v is a vertex of P, then h(NP (v)) ⊆ ND17 (h(v)), so hV is a graph homomorphism from P to D17. If v is one of the vertice… view at source ↗

read the original abstract

We show that if a graph has minimum vertex degree at least d and girth at least g, where (d, g) is (3, 6) or (4, 4), then the incidence system of the graph has a (possibly infinite-dimensional) quantum solution over $\mathbb{Z}_p$ for every choice of vertex weights and integer $p \geq 2$. In particular, there are linear systems over $\mathbb{Z}_p$, for $p$ an odd prime, such that the corresponding linear system nonlocal game has a perfect commuting-operator strategy, but no perfect classical strategy.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a uniform existence result for commuting-operator solutions to weighted linear systems over any Z_p using small cancellation on graphs with girth 4 or 6.

read the letter

This paper shows that graphs with min degree 3 and girth 6, or min degree 4 and girth 4, produce incidence systems that have operator solutions over Z_p for every choice of vertex weights and every p at least 2. The payoff is a supply of linear-system nonlocal games that admit perfect commuting-operator strategies but no perfect classical ones, at least for odd primes p. The uniform claim across all weights and all p looks new; most prior examples fix the coefficients or the modulus. The method relies on small cancellation to build the solutions inductively from the group presentation of the incidence relations. That technique is standard for these problems and fits the setting. The girth condition is meant to keep cycles long enough that the relators satisfy the needed overlap bounds. The stress-test concern about weights creating bad cancellations is reasonable in principle, but the paper states the result holds for arbitrary weights, so the length estimates must account for the coefficients. If the full argument checks the pieces after weighting, the claim stands. A minor soft spot is that the abstract gives no explicit small-cancellation constant or sample calculation, but that is normal at this stage. Readers working on quantum strategies for linear systems or on explicit separations in nonlocal games will get concrete families they can use. The work is coherent on its own terms and engages the relevant literature on operator solutions and small cancellation. It deserves a serious referee.

Referee Report

2 major / 2 minor

Summary. The paper claims that graphs with minimum vertex degree at least 3 and girth at least 6, or minimum degree 4 and girth 4, have incidence systems that admit (possibly infinite-dimensional) quantum solutions over Z_p for every choice of vertex weights and every integer p >= 2. This is proved via small-cancellation arguments on the group presentation arising from the incidence system, yielding in particular linear systems over odd primes with perfect commuting-operator strategies but no perfect classical strategies.

Significance. If the central existence result holds, the work supplies an explicit combinatorial criterion (degree and girth) guaranteeing quantum solutions to linear systems independent of weights, which may produce new families of nonlocal games separating classical and quantum strategies. The application of small-cancellation theory to construct operator solutions is a technical strength that could be reusable beyond this setting.

major comments (2)

[Abstract, paragraph 1; main theorem statement (likely Theorem 1.1 or §3)] The central claim requires that the girth conditions suffice to ensure the small-cancellation hypotheses (presumably C'(λ) with λ < 1/6) hold for the relator set arising from arbitrary integer vertex weights. Because weights enter the coefficients of the relators, it is possible for certain weight choices to create overlaps or cancellations whose total length exceeds the small-cancellation threshold even when the underlying graph girth is large; the manuscript must explicitly verify that no such weight produces a violating relator, as this is load-bearing for the 'for every choice of vertex weights' statement.
[Section developing the small-cancellation argument and inductive construction] The inductive construction of the operator solution (presumably in the section developing the small-cancellation argument) assumes the presentation satisfies the required cancellation condition uniformly in the weights. If the proof only treats the geometric girth and does not bound the effect of coefficients on piece lengths, the induction step fails for some weights and the existence result does not follow.

minor comments (2)

[Introduction or §2] Notation for the incidence system and the precise form of the relators (variables on vertices/edges, weighted equations over Z_p) should be introduced with an explicit example early in the paper to make the translation from graph to presentation transparent.
[Statement of main theorem] The paper should clarify whether the quantum solutions are required to be finite-dimensional or whether the infinite-dimensional case is the only one guaranteed; this affects the interpretation for nonlocal games.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need to make the uniformity of the small-cancellation condition with respect to arbitrary weights fully explicit. We agree that this point is load-bearing for the main theorem and will revise the manuscript to supply the missing verification.

read point-by-point responses

Referee: The central claim requires that the girth conditions suffice to ensure the small-cancellation hypotheses (presumably C'(λ) with λ < 1/6) hold for the relator set arising from arbitrary integer vertex weights. Because weights enter the coefficients of the relators, it is possible for certain weight choices to create overlaps or cancellations whose total length exceeds the small-cancellation threshold even when the underlying graph girth is large; the manuscript must explicitly verify that no such weight produces a violating relator, as this is load-bearing for the 'for every choice of vertex weights' statement.

Authors: We agree that an explicit verification is required. The relators arise from cycles in the incidence graph; their underlying generator sequences are fixed by the graph, while the weights appear only as exponents on those generators. Because distinct vertices correspond to distinct generators, overlaps (pieces) can only occur along common paths in the graph. The girth condition therefore bounds the maximal piece length independently of the weights. Relator lengths grow linearly with the sum of the absolute values of the weights, so the ratio of piece length to relator length remains strictly less than 1/6 for any nonzero integer weights. In the revision we will add a short lemma stating this bound and confirming that no weight choice violates the C'(1/6) condition. revision: yes
Referee: The inductive construction of the operator solution (presumably in the section developing the small-cancellation argument) assumes the presentation satisfies the required cancellation condition uniformly in the weights. If the proof only treats the geometric girth and does not bound the effect of coefficients on piece lengths, the induction step fails for some weights and the existence result does not follow.

Authors: The inductive step invokes the small-cancellation condition at each stage; once the condition is verified to hold uniformly (as described in the response to the first comment), the induction proceeds for every choice of weights. We will insert a clarifying paragraph immediately before the induction, referencing the new lemma on piece-length bounds, so that the dependence on weights is stated explicitly rather than left implicit. revision: yes

Circularity Check

0 steps flagged

No circularity; existence claim rests on independent small-cancellation verification for girth-bounded graphs

full rationale

The derivation asserts that graphs of min-degree d and girth g in {(3,6),(4,4)} yield incidence presentations whose small-cancellation hypotheses hold for arbitrary integer vertex weights, permitting an inductive construction of operator solutions over Z_p. This is a standard mathematical claim whose validity depends on whether the girth bound controls relator overlaps even after coefficients are inserted by the weights; the abstract and described structure contain no self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations. The result is therefore self-contained against external small-cancellation theory and graph combinatorics rather than reducing to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only; no free parameters, invented entities, or non-standard axioms are visible. The claim rests on standard facts from graph theory and operator algebras plus the small-cancellation technique whose details are not provided.

pith-pipeline@v0.9.0 · 5620 in / 1141 out tokens · 22510 ms · 2026-05-23T06:45:42.697460+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 1 internal anchor

[1]

3, 243--246

Dan Archdeacon, A K uratowski theorem for the projective plane , Journal of Graph Theory 5 (1981), no. 3, 243--246

work page 1981
[2]

Martin Bridson and Andre Haefliger, Metric S paces of N on- P ositive C urvature , Grundlehren der mathematischen W issenschaften, Springer Berlin, Heidelberg, 1999

work page 1999
[3]

01, 012202

Richard Cleve, Li Liu, and William Slofstra, Perfect commuting-operator strategies for linear system games, Journal of Mathematical Physics 58 (2017), no. 01, 012202

work page 2017
[4]

Characterization of Binary Constraint System Games

Richard Cleve and Rajat Mittal, Characterization of Binary Constraint System Games , Automata, Languages , and Programming , Lecture Notes in Computer Science , no. 8572, Springer Berlin Heidelberg, 2014, arXiv:1209.2729, pp. 320--331

work page internal anchor Pith review Pith/arXiv arXiv 2014
[5]

Ho Yiu Chung, Cihan Okay, and Igor Sikora, Simplicial techniques for operator solutions of linear constraint systems, Topology and its Applications 348 (2024), 108883

work page 2024
[6]

Josse van Dobben de Bruyn , in preparation

work page
[7]

Josse van Dobben de Bruyn and David Roberson, Connections between solution groups, harmonic homomorphisms, and N egami's conjecture , in preparation

work page
[8]

1, P1.54

David Ellis and Nathan Linial, On R egular H ypergraphs of H igh G irth , The Electronic Journal of Combinatorics 21 (2014), no. 1, P1.54

work page 2014
[9]

Markus Frembs, Cihan Okay, and Ho Yiu Chung, No state-independent contextuality can be extracted from contextual measurement-based quantum computation with qudits of odd prime dimension, preprint (2022), arXiv:2209.14018

work page arXiv 2022
[10]

Glover, John P

Henry H. Glover, John P. Huneke, and Chin San Wang, 103 graphs that are irreducible for the projective plane, Journal of Combinatorial Theory, Series B 27 (1979), no. 3, 332--370

work page 1979
[11]

4, 525--536

Petr Hlin e n\' y , 20 Y ears of N egami’s P lanar C over C onjecture , Graphs and Combinatorics 26 (2010), no. 4, 525--536

work page 2010
[12]

Lyndon and P.E

R.C. Lyndon and P.E. Schupp, Combinatorial G roup T heory , Classics in Mathematics, Springer, 1977

work page 1977
[13]

David Mermin, Simple unified form for the major no-hidden-variables theorems, Physical Review Letters 65 (1990), no

N. David Mermin, Simple unified form for the major no-hidden-variables theorems, Physical Review Letters 65 (1990), no. 27, 3373--3376

work page 1990
[14]

Negami, Enumeration of P rojective-planar E mbeddings of G raphs , Discrete Mathematics 62 (1986), 299--306

S. Negami, Enumeration of P rojective-planar E mbeddings of G raphs , Discrete Mathematics 62 (1986), 299--306

work page 1986
[15]

4, 378--384

, Graphs which have no finite planar covering, Bulletin of the Institute of Mathematics Academia Sinica 15 (1988), no. 4, 378--384

work page 1988
[16]

, The spherical genus and virtually planar graphs, Discrete Mathematics 70 (1988), 159--168

work page 1988
[17]

Cihan Okay and Robert Raussendorf, Homotopical approach to quantum contextuality, Quantum 4 (2020), 217

work page 2020
[18]

Asher Peres, Two simple proofs of the K ochen- S pecker theorem , Journal of Physics A: Mathematical and General 24 (1991), no. 4, L175

work page 1991
[19]

4, 1119--1162

Connor Paddock, Vincent Russo, Turner Silverthorne, and William Slofstra, Arkhipov s theorem, graph minors, and linear system nonlocal games , Algebraic Combinatorics 6 (2023), no. 4, 1119--1162

work page 2023
[20]

Hammam Qassim and Joel Wallman, Classical vs quantum satisfiability in linear constraint systems modulo an integer, Journal of Physics A: Mathematical and Theoretical 53 (2020), 385304

work page 2020
[21]

Seymour, Graph minors

Neil Robertson and Paul D. Seymour, Graph minors. XX . W agner's conjecture , Journal of Combinatorial Theory, Series B 92 (2004), no. 2, 325--357

work page 2004
[22]

Hamish Short, Diagrams and G roups , The G eometry of the W ord P roblem for F initely G enerated G roups, Birkh \"a user Basel, Basel, 2007

work page 2007
[23]

William Slofstra, The set of quantum correlations is not closed, Forum of Mathematics, Pi 7 (2019), E1

work page 2019
[24]

, Tsirelson’s problem and an embedding theorem for groups arising from no n-local games, Journal of the American Mathematical Society 33 (2020), 1--56

work page 2020

[1] [1]

3, 243--246

Dan Archdeacon, A K uratowski theorem for the projective plane , Journal of Graph Theory 5 (1981), no. 3, 243--246

work page 1981

[2] [2]

Martin Bridson and Andre Haefliger, Metric S paces of N on- P ositive C urvature , Grundlehren der mathematischen W issenschaften, Springer Berlin, Heidelberg, 1999

work page 1999

[3] [3]

01, 012202

Richard Cleve, Li Liu, and William Slofstra, Perfect commuting-operator strategies for linear system games, Journal of Mathematical Physics 58 (2017), no. 01, 012202

work page 2017

[4] [4]

Characterization of Binary Constraint System Games

Richard Cleve and Rajat Mittal, Characterization of Binary Constraint System Games , Automata, Languages , and Programming , Lecture Notes in Computer Science , no. 8572, Springer Berlin Heidelberg, 2014, arXiv:1209.2729, pp. 320--331

work page internal anchor Pith review Pith/arXiv arXiv 2014

[5] [5]

Ho Yiu Chung, Cihan Okay, and Igor Sikora, Simplicial techniques for operator solutions of linear constraint systems, Topology and its Applications 348 (2024), 108883

work page 2024

[6] [6]

Josse van Dobben de Bruyn , in preparation

work page

[7] [7]

Josse van Dobben de Bruyn and David Roberson, Connections between solution groups, harmonic homomorphisms, and N egami's conjecture , in preparation

work page

[8] [8]

1, P1.54

David Ellis and Nathan Linial, On R egular H ypergraphs of H igh G irth , The Electronic Journal of Combinatorics 21 (2014), no. 1, P1.54

work page 2014

[9] [9]

Markus Frembs, Cihan Okay, and Ho Yiu Chung, No state-independent contextuality can be extracted from contextual measurement-based quantum computation with qudits of odd prime dimension, preprint (2022), arXiv:2209.14018

work page arXiv 2022

[10] [10]

Glover, John P

Henry H. Glover, John P. Huneke, and Chin San Wang, 103 graphs that are irreducible for the projective plane, Journal of Combinatorial Theory, Series B 27 (1979), no. 3, 332--370

work page 1979

[11] [11]

4, 525--536

Petr Hlin e n\' y , 20 Y ears of N egami’s P lanar C over C onjecture , Graphs and Combinatorics 26 (2010), no. 4, 525--536

work page 2010

[12] [12]

Lyndon and P.E

R.C. Lyndon and P.E. Schupp, Combinatorial G roup T heory , Classics in Mathematics, Springer, 1977

work page 1977

[13] [13]

David Mermin, Simple unified form for the major no-hidden-variables theorems, Physical Review Letters 65 (1990), no

N. David Mermin, Simple unified form for the major no-hidden-variables theorems, Physical Review Letters 65 (1990), no. 27, 3373--3376

work page 1990

[14] [14]

Negami, Enumeration of P rojective-planar E mbeddings of G raphs , Discrete Mathematics 62 (1986), 299--306

S. Negami, Enumeration of P rojective-planar E mbeddings of G raphs , Discrete Mathematics 62 (1986), 299--306

work page 1986

[15] [15]

4, 378--384

, Graphs which have no finite planar covering, Bulletin of the Institute of Mathematics Academia Sinica 15 (1988), no. 4, 378--384

work page 1988

[16] [16]

, The spherical genus and virtually planar graphs, Discrete Mathematics 70 (1988), 159--168

work page 1988

[17] [17]

Cihan Okay and Robert Raussendorf, Homotopical approach to quantum contextuality, Quantum 4 (2020), 217

work page 2020

[18] [18]

Asher Peres, Two simple proofs of the K ochen- S pecker theorem , Journal of Physics A: Mathematical and General 24 (1991), no. 4, L175

work page 1991

[19] [19]

4, 1119--1162

Connor Paddock, Vincent Russo, Turner Silverthorne, and William Slofstra, Arkhipov s theorem, graph minors, and linear system nonlocal games , Algebraic Combinatorics 6 (2023), no. 4, 1119--1162

work page 2023

[20] [20]

Hammam Qassim and Joel Wallman, Classical vs quantum satisfiability in linear constraint systems modulo an integer, Journal of Physics A: Mathematical and Theoretical 53 (2020), 385304

work page 2020

[21] [21]

Seymour, Graph minors

Neil Robertson and Paul D. Seymour, Graph minors. XX . W agner's conjecture , Journal of Combinatorial Theory, Series B 92 (2004), no. 2, 325--357

work page 2004

[22] [22]

Hamish Short, Diagrams and G roups , The G eometry of the W ord P roblem for F initely G enerated G roups, Birkh \"a user Basel, Basel, 2007

work page 2007

[23] [23]

William Slofstra, The set of quantum correlations is not closed, Forum of Mathematics, Pi 7 (2019), E1

work page 2019

[24] [24]

, Tsirelson’s problem and an embedding theorem for groups arising from no n-local games, Journal of the American Mathematical Society 33 (2020), 1--56

work page 2020