Groups with arbitrarily poor permutation stability

Henry Bradford

Pith reviewed 2026-05-10 08:46 UTC · model grok-4.3

classification 🧮 math.GR

keywords groupsstabilityfinitelypermutationarbitrarilygeneratednotionalgorithm

0 comments

The pith

Finitely generated groups exist that are permutation stable but exhibit arbitrarily bad quantitative stability, making sample-and-substitute algorithms very slow at checking relations.

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

Permutation stability asks whether permutations that almost obey a group's rules must actually come from a representation of that group. The authors define a new quantitative version of this idea that measures how bad the approximation can get. They then build an infinite family of finitely generated groups that qualify as stable under this measure, yet the quantitative bound on stability grows worse without limit as one moves through the family. The practical effect is that any algorithm trying to test whether a tuple of permutations satisfies the group's relations by sampling and substituting must use larger and larger samples, slowing the procedure dramatically. This separates the existence of stability from the existence of good quantitative control over it.

Core claim

We construct a family of finitely generated stable groups which exhibit, quantitatively, arbitrarily ``bad'' permutation stability. This means that any application of a ``sample-and-substitute'' algorithm will be very slow in ascertaining whether a given tuple of permutations satisfy the defining relations of our groups.

Load-bearing premise

That the newly proposed quantitative notion of permutation stability is a faithful and useful extension of existing stability concepts, and that the constructed family consists of groups that are stable under this notion yet possess arbitrarily bad rates.

read the original abstract

We propose a quantitative notion of permutation stability for finitely generated groups. Our notion is related to, but distinct from, the ``stability rate'' introduced by Becker and Mosheiff (which is valid within the class of finitely presented groups). We construct a family of finitely generated stable groups which exhibit, quantitatively, arbitrarily ``bad'' permutation stability. This means that any application of a ``sample-and-substitute'' algorithm will be very slow in ascertaining whether a given tuple of permutations satisfy the defining relations of our groups.

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

Bradford defines a quantitative permutation stability measure for f.g. groups distinct from Becker-Mosheiff rates and constructs examples that are stable yet arbitrarily bad under it.

read the letter

The main takeaway is that this paper introduces a quantitative version of permutation stability for finitely generated groups, separate from the stability rate defined by Becker and Mosheiff for finitely presented groups, and then produces a family of stable groups where the new measure can be made arbitrarily poor. Any sample-and-substitute procedure to check whether permutations nearly satisfy the relations will require extremely small defect before it can certify closeness to a homomorphism.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard axioms of group theory together with the new definition of quantitative permutation stability; no free parameters or invented entities are introduced in the abstract.

axioms (1)

standard math Standard axioms of group theory for finitely generated groups
The paper works entirely within the category of finitely generated groups and their permutation representations.

pith-pipeline@v0.9.0 · 5360 in / 1115 out tokens · 49289 ms · 2026-05-10T08:46:51.995349+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 2 canonical work pages

[1]

Arzhantseva, P.-A

G. Arzhantseva, P.-A. Cherix,Quantifying metric approximations of dis- crete groups.Ann. Fac. Sci. Toulouse Math (2024), 831-877

2024
[2]

Arzhantseva, L

G. Arzhantseva, L. Paunescu,Almost commuting permutations are near commuting permutations.Journal of Functional Analysis, 269, no. 3 (2015): 745-757

2015
[3]

Becker, A

O. Becker, A. Lubotzky, A. Thom,Stability and invariant random sub- groups.Duke Mathematical Journal, 168, no. 3 (2019), 2207-2234

2019
[4]

Becker, A

O. Becker, A. Lubotzky, J. Moshieff,Testability of relations between permu- tations.2021 IEEE 62nd annual symposium on foundations of computer science (FOCS). IEEE (2022)

2021
[5]

Becker, A

O. Becker, A. Lubotzky, J. Moshieff,Testability in group theory.Israel Journal of Mathematics, 256 (2023), 61–90

2023
[6]

Becker, J

O. Becker, J. Moshieff,Abelian groups are polynomially stable.Interna- tional Mathematics Research Notices, 20 (2021), 15574-15632

2021
[7]

Bowen, R

L. Bowen, R. Grigorchuk, R. Kravchenko,Invariant random subgroups of lamplighter groups.Israel Journal of Mathematics 207.2 (2015), 763-782

2015
[8]

arXiv preprint arXiv:2402.03556 , year=

H. Bradford,The inverse problem for residual finiteness growth. arXiv:2402.03556 [math.GR]

work page arXiv
[9]

Bradford,Quantifying local embeddings into finite groups.Journal of Algebra 608 (2022), 214-238

H. Bradford,Quantifying local embeddings into finite groups.Journal of Algebra 608 (2022), 214-238

2022
[10]

Bou-Rabee, B

K. Bou-Rabee, B. Seward,Arbitrarily large residual finiteness growth.J. Reine Angwe. Math. 2016 (710), 199-204

2016
[11]

Dixon, B

J.D. Dixon, B. Mortimer,Permutation groups.Graduate Texts in Mathe- matics 163, Springer Science & Business Media (2012)

2012
[12]

Dogon, A

A. Dogon, A. Levit, I. Vigdorovich,Characters of diagonal products and Hilbert-Schmidt stability.arXiv preprint arXiv:2407.11608 (2024)

work page arXiv 2024
[13]

Genevois, R

A. Genevois, R. Tessera,A note on morphisms to wreath products.athe- matical Proceedings of the Cambridge Philosophical Society (2025)

2025
[14]

Gersten, D.F

S. Gersten, D.F. Holt, T.R. Riley,Isoperimetric inequalities for nilpotent groups.Geometric and Functional Analysis 13.4 (2003), 795-814

2003
[15]

Kassabov, I

M. Kassabov, I. Pak,Groups of oscillating intermediate growth.Annals of Mathematics (2013), 1113-1145

2013
[16]

Levit, A

A. Levit, A. Lubotzky,Uncountably many permutation stable groups.Israel Journal of Mathematics 251.2 (2022), 657-678

2022
[17]

Neumann,Some remarks on infinite groups.J

B.H. Neumann,Some remarks on infinite groups.J. London Math. Soc. 12 (1937) 120-127

1937
[18]

Pittet,Isoperimetric inequalities in nilpotent groups.J

C. Pittet,Isoperimetric inequalities in nilpotent groups.J. London Math. Soc. 55.3 (1997): 588-600

1997