pith. sign in

arxiv: 1906.12097 · v1 · pith:4CXWOO4Tnew · submitted 2019-06-28 · 🧮 math.QA · math.CO

Existence of quantum symmetries for graphs on up to seven vertices: a computer based approach

Christian Eder , Viktor Levandovskyy , Julien Schanz , Simon Schmidt , Andreas Steenpass , Moritz Weber This is my paper

Pith reviewed 2026-05-25 13:43 UTC · model grok-4.3

classification 🧮 math.QA math.CO
keywords quantum automorphism groupsfinite graphsGröbner basesquantum symmetriescomputer algebraWoronowicz quantum groupsautomorphism groups
0
0 comments X

The pith

Graphs whose classical automorphism group has order one or two have no quantum symmetries beyond the classical ones, at least up to seven vertices.

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

The paper determines, for every connected undirected graph on at most seven vertices, whether its quantum automorphism algebra is commutative. It does so by running Gröbner basis calculations that decide commutativity of the algebra generated by the quantum permutation matrices compatible with the graph's adjacency matrix. The computation reveals that commutativity holds exactly when the ordinary automorphism group has size one or two. A reader would care because this supplies an explicit, checkable obstruction to the appearance of genuinely quantum symmetries in a complete enumeration of small graphs where manual inspection is infeasible.

Core claim

Using Gröbner basis techniques implemented in GAP together with the SINGULAR LETTERPLACE package, the authors show that the quantum automorphism algebra of any connected graph on at most seven vertices is commutative if and only if the classical automorphism group has order one or two; in all other cases within this range the algebra is non-commutative, indicating the presence of quantum symmetries.

What carries the argument

Gröbner basis computation on the quantum automorphism algebra, which tests whether the algebra generated by the matrix coefficients satisfying the quantum permutation and adjacency relations is commutative.

Load-bearing premise

The specific Gröbner basis implementation correctly decides commutativity of the quantum automorphism algebra for every graph in the set examined.

What would settle it

A single connected graph on at most seven vertices whose classical automorphism group has order one or two yet whose quantum automorphism algebra is found to be non-commutative by an independent method, or a graph whose classical group is larger than order two yet whose algebra is commutative.

read the original abstract

The symmetries of a finite graph are described by its automorphism group; in the setting of Woronowicz's quantum groups, a notion of a quantum automorphism group has been defined by Banica capturing the quantum symmetries of the graph. In general, there are more quantum symmetries than symmetries and it is a non-trivial task to determine when this is the case for a given graph: The question is whether or not the algebra associated to the quantum automorphism group is commutative. We use Gr\"obner base computations in order to tackle this problem; the implementation uses GAP and the SINGULAR package LETTERPLACE. We determine the existence of quantum symmetries for all connected, undirected graphs without multiple edges and without self-edges, for up to seven vertices. As an outcome, we infer within our regime that a classical automorphism group of order one or two is an obstruction for the existence of quantum symmetries.

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.

Referee Report

2 major / 3 minor

Summary. The manuscript describes a computational enumeration, using non-commutative Gröbner basis calculations implemented via GAP and the SINGULAR LETTERPLACE package, to decide commutativity of the quantum automorphism algebra (in the sense of Banica) for every connected simple undirected graph on at most seven vertices. From the results the authors conclude that |Aut(G)| = 1 or 2 constitutes an obstruction to the existence of quantum symmetries (i.e., forces the algebra to be commutative).

Significance. If the computations are correct, the work supplies a complete, finite classification for all graphs in the stated range and supplies concrete evidence for the stated obstruction. The exhaustive computer-assisted approach itself is a methodological contribution to the study of quantum automorphism groups of graphs.

major comments (2)
  1. [§4 and §5] §4 (Computational method) and the results tables in §5: the central obstruction claim rests entirely on the correctness of the LETTERPLACE Gröbner-basis decisions for commutativity. The manuscript gives no explicit source code, no listing of the precise algebra presentation (generators and relations derived from the adjacency matrix), and no statement of the monomial ordering or termination criteria employed; without these the computations cannot be independently reproduced or cross-checked for the critical graphs with |Aut(G)| ≤ 2.
  2. [§5] §5 (Results): while the paper reports that all graphs with |Aut(G)| = 1 or 2 yield commutative algebras, it does not indicate whether any independent verification (different computer-algebra system, hand check for the smallest graphs, or comparison with known quantum automorphism groups) was performed for even a single such graph; this verification gap directly affects the load-bearing inference.
minor comments (3)
  1. [Abstract, §1] The abstract and introduction use both “Gröbner base” and “Gröbner basis”; standardize to the latter throughout.
  2. [§2] A reference to Banica’s original definition of the quantum automorphism group of a graph should be added in §2.
  3. [§5] The manuscript should state the total number of connected simple graphs on ≤7 vertices that were examined and the number that fall into the |Aut(G)| ≤ 2 class.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on reproducibility and verification. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§4 and §5] §4 (Computational method) and the results tables in §5: the central obstruction claim rests entirely on the correctness of the LETTERPLACE Gröbner-basis decisions for commutativity. The manuscript gives no explicit source code, no listing of the precise algebra presentation (generators and relations derived from the adjacency matrix), and no statement of the monomial ordering or termination criteria employed; without these the computations cannot be independently reproduced or cross-checked for the critical graphs with |Aut(G)| ≤ 2.

    Authors: We agree that the manuscript lacks the details required for independent reproduction. In the revised version we will add a public repository link containing the GAP/SINGULAR LETTERPLACE scripts, give explicit generators-and-relations presentations for all graphs with |Aut(G)| ≤ 2, state the monomial ordering (degree-reverse-lexicographic), and describe the termination criteria used for the Gröbner-basis computations. revision: yes

  2. Referee: [§5] §5 (Results): while the paper reports that all graphs with |Aut(G)| = 1 or 2 yield commutative algebras, it does not indicate whether any independent verification (different computer-algebra system, hand check for the smallest graphs, or comparison with known quantum automorphism groups) was performed for even a single such graph; this verification gap directly affects the load-bearing inference.

    Authors: We acknowledge that the manuscript does not report independent verification. For graphs on at most four vertices the commutativity statements can be checked directly by hand or with other computer-algebra systems and are consistent with known results in the literature; we will add a short subsection describing these checks. For the remaining graphs the exhaustive enumeration rests on the Gröbner-basis method itself. revision: yes

Circularity Check

0 steps flagged

No circularity: exhaustive external computation yields empirical obstruction

full rationale

The paper enumerates all connected simple graphs on ≤7 vertices and uses external GAP/SINGULAR LETTERPLACE non-commutative Gröbner bases to decide commutativity of the quantum automorphism algebra for each. The reported obstruction (|Aut(G)|=1 or 2 implies commutativity) is a direct post-processing observation on the computed outcomes. No self-definitional equations, fitted parameters renamed as predictions, load-bearing self-citations, or ansatzes appear; the derivation chain consists of external software calls against an explicit finite set.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard definitions of Woronowicz quantum groups and Banica's quantum automorphism groups for graphs, plus the correctness of the cited computer-algebra packages. No free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Quantum automorphism groups are defined via Woronowicz's compact quantum groups and Banica's construction for graphs.
    Background framework taken from the quantum groups literature.

pith-pipeline@v0.9.0 · 5694 in / 1055 out tokens · 30929 ms · 2026-05-25T13:43:13.225721+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

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

  1. [1]

    Quantum automorphism groups of homogeneous graphs

    Teodor Banica. Quantum automorphism groups of homogeneous graphs. J. Funct. Anal. , 224(2):243--280, 2005

    work page 2005

  2. [2]

    Quantum automorphism groups of finite graphs

    Julien Bichon. Quantum automorphism groups of finite graphs. Proc. Amer. Math. Soc. , 131(3):665--673, 2003

    work page 2003

  3. [3]

    Blackadar

    B. Blackadar. Operator algebras , volume 122 of Encyclopaedia of Mathematical Sciences . Springer-Verlag, Berlin, 2006. Theory of C^* -algebras and von Neumann algebras, Operator Algebras and Non-commutative Geometry, III

    work page 2006

  4. [4]

    Singular 4-1-2 --- A computer algebra system for polynomial computations

    Wolfram Decker, Gert-Martin Greuel, Gerhard Pfister, and Hans Sch\"onemann. Singular 4-1-2 --- A computer algebra system for polynomial computations. http://www.singular.uni-kl.de, 2019

    work page 2019

  5. [5]

    Melanie B. Fulton. The quantum automorphism group and undirected trees, 2006. Thesis (Ph.D.)--Virginia Polytechnic Institute and State University

    work page 2006

  6. [6]

    GAP -- Groups, Algorithms, and Programming, Version 4.10.1 , 2019

    The GAP Group. GAP -- Groups, Algorithms, and Programming, Version 4.10.1 , 2019

    work page 2019

  7. [7]

    a user Advanced Texts: Basler Lehrb\

    Jos\' e M. Gracia-Bond\' a, Joseph C. V\' a rilly, and H\' e ctor Figueroa. Elements of noncommutative geometry . Birkh\" a user Advanced Texts: Basler Lehrb\" u cher. [Birkh\" a user Advanced Texts: Basel Textbooks]. Birkh\" a user Boston, Inc., Boston, MA, 2001

    work page 2001

  8. [8]

    Singular:Letterplace --- A singular subsystem for non-commutative finitely presented algebras

    Viktor Levandovskyy, Karim Abou Zeid, and Hans Sch\"onemann. Singular:Letterplace --- A singular subsystem for non-commutative finitely presented algebras. http://www.singular.uni-kl.de, 2019

    work page 2019

  9. [9]

    Nonlocal Games and Quantum Permutation Groups

    Martino Lupini, Laura Mancinska, and David Roberson. Nonlocal games and quantum permutation groups. arXiv:1712.01820 , 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  10. [10]

    Compact quantum groups and their representation categories , volume 20 of Cours Sp\' e cialis\' e s [Specialized Courses]

    Sergey Neshveyev and Lars Tuset. Compact quantum groups and their representation categories , volume 20 of Cours Sp\' e cialis\' e s [Specialized Courses] . Soci\' e t\' e Math\' e matique de France, Paris, 2013

    work page 2013

  11. [11]

    Quantum automorphisms of folded cube graphs

    Simon Schmidt. Quantum automorphisms of folded cube graphs. arXiv:1810.11284 , 2018

    work page arXiv 2018

  12. [12]

    On the quantum symmetry of distance-transitive graphs

    Simon Schmidt. On the quantum symmetry of distance-transitive graphs. arXiv:1906.06537 , 2019

    work page arXiv 1906

  13. [13]

    Quantum symmetries of graph C^* -algebras

    Simon Schmidt and Moritz Weber. Quantum symmetries of graph C^* -algebras. Canad. Math. Bull. , 61(4):848--864, 2018

    work page 2018

  14. [14]

    Quantum groups with partial commutation relations

    Roland Speicher and Moritz Weber. Quantum groups with partial commutation relations. to appear in Indiana Journal of Mathematics , 2019

    work page 2019

  15. [15]

    An invitation to quantum groups and duality

    Thomas Timmermann. An invitation to quantum groups and duality . EMS Textbooks in Mathematics. European Mathematical Society (EMS), Z\" u rich, 2008. From Hopf algebras to multiplicative unitaries and beyond

    work page 2008

  16. [16]

    Quantum symmetry groups of finite spaces

    Shuzhou Wang. Quantum symmetry groups of finite spaces. Comm. Math. Phys. , 195(1):195--211, 1998

    work page 1998

  17. [17]

    Introduction to compact (matrix) quantum groups and B anica- S peicher (easy) quantum groups

    Moritz Weber. Introduction to compact (matrix) quantum groups and B anica- S peicher (easy) quantum groups. Proc. Indian Acad. Sci. Math. Sci. , 127(5):881--933, 2017

    work page 2017

  18. [18]

    S. L. Woronowicz. Compact matrix pseudogroups. Comm. Math. Phys. , 111(4):613--665, 1987

    work page 1987