Pith. sign in

REVIEW 3 major objections 8 minor 16 references

The ineffectiveness of the regularity lemma for bounded degree graphs

T0 review · 3 major / 8 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read For graphs of maximum degree at least 3, no computable size bound exists for approximating them by smaller graphs.

desk verdict Settles Lovász's bounded-degree regularity question negatively with a clean reduction; the only real soft spot is the unquantified error transfer in Appendix A, which looks repairable. read the letter →

arxiv 2505.06215 v3 pith:NXPIGQZJ submitted 2025-05-09 math.CO math.LO

Clark Lyons , Grigory Terlov , Zoltán Vidnyánszky This is my paper · ORCID
classification math.COmath.LO MSC 05C8003D35
keywords regularitylemmaboundeddegreegraphsneighborhoodstatisticssoficvaluesundecidabilitySchreierAldous-Lyonsconjecturecomputability
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

The paper proves that bounded-degree graph regularity is ineffective: for any maximum degree at least 3, there is no computable function that takes an accuracy $\varepsilon$ and a radius $r$ and returns a size bound for a graph approximating any bounded-degree graph up to $\varepsilon$ error in its $r$-neighborhood statistics. An effective bound of this kind is exactly what was sought after the existence of a nonconstructive bound was established. The proof works by encoding Turing machine halting into the local statistics of Schreier graphs, so that a computable approximation bound would yield an algorithm deciding halting. This answers a question posed in the graph limits literature and draws a direct consequence from a recent refutation of the Aldous–Lyons conjecture.

What carries the argument

The machinery is the $r$-neighborhood statistic $u_r(F_\bullet,G)$—the fraction of vertices whose radius-$r$ ball is isomorphic to a given rooted graph—together with the sofic value $\mathrm{val}_{\mathrm{sof}}(T)=\sup_G \mathbb{E}_{v\in V(G)}[T(\mathrm{Stab}(v))]$ of a continuous rational function $T$ on the space of subsets of a free group. The $r$-neighborhood statistic is what the regularity bound must approximate; the sofic value is what a computable bound would let one compute from above. The link is that $T(\mathrm{Stab}(v))$ is constant on rooted edge-labeled neighborhoods of radius $r$, so an $\varepsilon$-approximation of all $r$-neighborhood statistics forces an approximation of $\mathrm{val}_{\mathrm{sof}}(T)$. The remaining piece is Lemma 7's explicit local encoding of finite graphs as $F_2$ Schreier graphs and of $F_d$ Schreier graphs as degree-$3$ graphs, which makes the two noncomputability statements equivalent.

What would settle it

Run the encoding on a concrete never-halting Turing machine: compute the rational function $T_M$ and its sofic value; if $\mathrm{val}_{\mathrm{sof}}(T_M)>1-\lambda_M$ for a machine that never halts, or if no positive rational $\lambda_M$ exists, the quoted Theorem 8 is false and the argument fails. Alternatively, exhibit a computable $N_\Delta(\varepsilon,r)$ for some $\Delta \ge 3$ satisfying the neighborhood-statistics approximation; by the paper's own reduction that would yield a decision procedure for halting, so testing any proposed computable bound on a family of graphs whose statistics encode a known non-halting machine would settle the claim.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3: for every $\Delta \ge 3$, any function $N_\Delta(\varepsilon,r)$ that bounds the vertex count of a degree-$\le \Delta$ graph $G'$ with $|u_r(F_\bullet,G)-u_r(F_\bullet,G')|<\varepsilon$ for every rooted graph $F_\bullet$ of radius $\le r$ is noncomputable. The proof first establishes the analogous statement for $F_d$ Schreier graphs with $d \ge 2$: any such regularity bound $N^*_d$ is noncomputable, because from such a bound one can enumerate rational upper bounds for the sofic value of a continuous rational function on the space of subgroups, and the quoted undecidability theorem says that the halting problem can be encoded into whether that sofic value equals $1$ or is bounded away from $1$. Lemma 7 transfers the statement between ordinary bounded-degree graphs and Schreier graphs by local encodings in both directions, with the caveat that the error transfer says “$\varepsilon_0$ small enough and $r_0$ large enough” without explicit quantitative control.

Load-bearing premise

The whole argument rests on a quoted theorem, not proved in this paper, that the halting problem can be computably encoded into whether a rational function on subgroups of a free group has sofic value $1$ or is bounded away from $1$ by a rational gap; if that theorem's gap is not uniform or its proof has a gap, the noncomputability conclusion collapses, and a secondary fragile point is the unquantified “$\varepsilon_0$ small enough and $r_0$ large enough” step in the graph–Schreier encoding lemma.

Editorial extensions

If this is right

  • A negative answer to the question whether the bounded-degree regularity lemma can be made effective: no algorithm can output $N_\Delta(\varepsilon,r)$ for any $\Delta \ge 3$.
  • Any attempt to construct approximating graphs by brute-force search over possible sizes must fail in principle: one cannot know when the search has covered all possible neighborhood statistics.
  • The equivalence in Theorem 13 reframes nonexistence of a computable bound as nonexistence of a computable local-statistic decision function, giving a concrete decision problem whose undecidability would independently refute the Aldous–Lyons conjecture.
  • The noncomputability transfers to Schreier graphs of free groups on $d \ge 2$ generators, so the obstacle is not specific to the unlabeled graph formulation.
  • If the Aldous–Lyons conjecture had been true, a computable bound would have existed, so the failure of the conjecture and the ineffectiveness of the regularity lemma are intertwined.

Reading between the lines

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

  • If the quoted undecidability theorem is robust, the result likely extends to other local statistics, such as frequencies of small subgraphs or expected spectral measures, since the encoding is local; the paper itself leaves these extensions open.
  • The unquantified “$\varepsilon_0$ small, $r_0$ large” step in Lemma 7 is the natural place to seek a self-contained proof: making those choices explicit with computable bounds would bypass the full depth of the subgroup-test machinery.
  • The density phase-transition question suggests there may be an intermediate density at which the regularity bound jumps from computable to noncomputable; testing families of graphs with density tending to zero could reveal where the barrier appears.
  • A consequence the authors do not spell out is that any practical algorithm for sampling or approximating bounded-degree graphs must settle for heuristic guarantees or a different error notion, since no effective bound can exist.
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 / 8 minor

Summary. The paper proves that for any Δ≥3, no computable function N_Δ(ε,r) can bound the size of a graph G′ of maximum degree Δ needed to approximate the r-neighborhood statistics of an arbitrary bounded-degree graph G to within ε. This gives a negative answer to a question posed by Lovász. The proof proceeds by translating the problem into the setting of F_d Schreier graphs and showing that a computable regularity bound would yield computable rational upper bounds for sofic values of continuous rational functions on P(F_d). Combining this with the Bowen–Chapman–Lubotzky–Vidick undecidability theorem, which supplies a computable map from Turing machines M to functions T_M with a rational gap λ_M, the authors derive a decision procedure for the halting problem and obtain the claimed non-computability (Theorem 3 via Theorem 6 and Lemma 7). The paper also proves a converse observation: a positive solution to the Aldous–Lyons conjecture would have implied a computable bound on N_Δ(ε,r). Additional sections reformulate the result as a decision problem about local statistics and list open problems.

Significance. The result is a clean and important corollary of the recent resolution of the Aldous–Lyons conjecture and answers a question of Lovász in the negative. The core reduction (Theorem 6 from Theorem 8) is rigorous and checkable: the inequality β_{T,Θ} ≤ val_sof(T) ≤ β_{T,Θ}+Θ is correctly derived, and the halting criterion 'M halts iff β_{T,Θ} > 1−λ_M' is sound. The paper is honest about its reliance on the external BCLV/BCV theorem and about the fact that a mere counterexample to Aldous–Lyons would not have sufficed. The equivalences in Lemma 7 and Theorem 13, together with the decision-problem reformulation, add conceptual value. The manuscript ships a clearly written proof with no fitted parameters and no circularity; the main weakness is the informal quantitative decoding step in Lemma 7, which is evidently repairable but should be tightened before publication.

major comments (3)
  1. [Appendix A, proof of Lemma 7] The error-transfer step in the two decoding directions is asserted only via 'choosing ε0 small enough and r0 large enough.' This is the least secure step in the paper. In particular, the decoding map from a Schreier graph G to its encoded graph G* and back involves vertices that are not part of good cycles or good gadgets; the fraction of such vertices in the approximant G*′ or Ĝ′ is bounded by ε0 only if the property 'being part of a good cycle' is locally determined with a uniform radius and if the error in local statistics transfers to the fraction of good vertices with a controlled constant. The radius and the Lipschitz constant of the decoding are not quantified. Since the claimed computability of N_Δ from N*_d (and vice versa) depends on this quantitative transfer, I ask the authors to spell out the explicit (or at least explicit-in-principle) bounds in the proof of Lemma 7, producing a fully checkable chain from ε0, r0 to ε, r.
  2. [Section 2, Theorem 8] The entire argument rests on the quoted BCLV/BCV theorem that there is a computable map from Turing machines M to continuous rational functions T_M and rational λ_M>0 with val_sof(T_M)=1 iff M halts and val_sof(T_M) ≤ 1−λ_M otherwise. This theorem is not proved in the paper. The authors should state precisely the form of the theorem they use, justify that the hypotheses of the cited theorems are satisfied (e.g., that the output T_M is a continuous rational-valued function on P(F_d) and that λ_M is rational and computable), and indicate whether the computability of the map is explicitly proved in [BCLV24, BCV24] or requires a routine check. As written, the paper's main theorem inherits any gap in this external premise.
  3. [Section 3, Remark 11] The claim that a positive answer to the Aldous–Lyons conjecture would have implied a computable bound on N*_d(ε,r) is stated informally. The argument is that a brute-force search through finite F_d Schreier graphs would eventually find an ε-cover, and Theorem 10 would certify the cover in finite time. This is plausible, but the proof should spell out why the search is guaranteed to terminate uniformly in ε and r: one needs to know that for the specific r and ε the finite ε-net can be found among F_d Schreier graphs with at most some computable number of vertices, or that the enumeration order plus Theorem 10 provides a finite-time halting certificate. Otherwise the 'if' direction is not fully demonstrated. This is a minor gap in an auxiliary result, but it should be fixed or explicitly stated as a heuristic remark.
minor comments (8)
  1. [Section 1, equation (1)] The notation B_r(v) is used before it is formally defined; please define the radius-r ball of a vertex explicitly.
  2. [Section 2, after Definition 5] There is a typo: the bound should be N*_d(ε,r), not N*(ε,r).
  3. [Section 2, Theorem 6] For clarity, state explicitly that the non-computability is over all pairs (ε,r) with ε>0 and r∈N, as is implicit in the definition of a regularity bound.
  4. [Section 3, before Theorem 10] The equality U*_{d,r}(IRS_d) = ⋂_k U*_{d,r}(P-IRS_d(k)) is stated without proof; it follows from the definition of IRS_d as a decreasing intersection, but a sentence of justification would help.
  5. [Section 4, proof of Theorem 13] In the converse direction, please ensure that the ε/2-ball in the definition of S is taken in the ℓ∞ metric and clarify that the enumeration is over graphs of maximum degree at most Δ.
  6. [Section 5, Problem 15] The phrase 'as the density decreases, the bound in Theorem 1 would increase' is informal; Theorem 1 gives a bound that does not depend on density. Perhaps the authors mean that for intermediate-density approximations the bounding function would have to grow unboundedly as the density parameter tends to the sparse regime.
  7. [Appendix A, Figure 2] The figure is schematic; it may help to add a precise description of the gadget used to encode a directed edge (lengths, which vertices are connected to which labels) in the caption or in the text.
  8. [References] The paper cites [Alo] as '(unpublished)'. This is acceptable, but since the reader may want to verify Theorem 2, please also cite the published source [Zha23, Theorem 4.8.4] as done in the text.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 3 is a genuine contradiction argument using an external undecidability theorem, not a derivation whose conclusion is built into its inputs.

full rationale

The paper's main claim, Theorem 3, is obtained by assuming a computable Schreier regularity bound N*d(epsilon,r) and deriving, in the proof of Theorem 6, uniform rational upper bounds beta_{T,Theta} on sofic values of continuous rational functions. These bounds are then combined with the external BCLV/BCV theorem (Theorem 8), which provides a computable map from Turing machines to continuous rational functions T_M and rational gaps lambda_M such that val_sof(T_M)=1 if M halts and val_sof(T_M)<=1-lambda_M otherwise. The contradiction is clean: with Theta=lambda_M/2, equation (2) would make M halt iff beta_{T,Theta} > 1 - lambda_M, yielding a decision procedure for the halting problem. The target claim is never assumed in the proof, and no fitted parameter is renamed as a prediction. Lemma 7, despite its unquantified 'choosing epsilon0 small enough and r0 large enough' step, is an encoding/decoding equivalence between graph regularity bounds and Schreier regularity bounds; this is a structural reduction, not a circular one, though the quantitative error transfer in Appendix A is under-specified. The dependence on Theorem 8 is external, from non-overlapping authors, and is quoted as a known theorem; that is legitimate support, not a self-citation chain. There is also no self-definitional step, no uniqueness theorem imported from the present authors, and no ansatz smuggled in via citation. The paper is self-contained against external benchmarks, so the appropriate finding is no significant circularity.

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

No free parameters or invented entities in the sense of fitted constants or new physical objects. The central claim depends on the external undecidability theorem of BCLV, on the compactness existence argument, and on the local encodings of Appendix A. These are the items a reader must grant to accept the proof.

assumptions (4)
  • domain assumption Theorem 8 (BCLV/BCV): for every d ≥ 2 there is a computable map from Turing machines M to continuous rational functions T_M ∈ T_d and rational λ_M > 0 such that val_sof(T_M) = 1 if M halts and val_sof(T_M) ≤ 1 − λ_M otherwise.
    This undecidability statement is the logical engine of the paper. It is quoted from [BCLV24, Theorems 1.13 and 7.3] and [BCV24, Theorem 1.1] and not proved here; the entire diagonalization rests on it.
  • standard math Total boundedness of the space of r-neighborhood statistics of bounded-degree graphs in [0,1]^{F_Δ(r)}
    Used to prove existence of N_Δ(ε,r) (Section 2, following Theorem 2) and its Schreier analogue; this is the compactness input that guarantees a bound exists even though it is noncomputable.
  • domain assumption Local encodings between graphs and F_d Schreier graphs preserve r-neighborhood statistics up to small error, with control achieved by taking ε0 small and r0 large (Appendix A, Lemma 7).
    The transfer from Theorem 6 to Theorem 3 depends on these encodings; the paper sketches the gadgets and asserts error control without explicit quantitative bounds.
  • standard math Church-Turing thesis and standard encoding of finite graphs as strings
    The noncomputability arguments require the standard model of computation and the existence of a computable bijection between graphs and natural numbers; this is implicit throughout Section 2 and Theorem 10.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The ineffectiveness of the regularity lemma for bounded degree graphs." pith.science (2026). https://pith.science/paper/NXPIGQZJ

@misc{pith2026250506215,
  author       = {Pith},
  title        = {Pith review of: The ineffectiveness of the regularity lemma for bounded degree graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NXPIGQZJ}},
  note         = {Machine review of arXiv:2505.06215}
}
abstract

We show that for any $\Delta \geq 3$, there is no bound computable from $(\varepsilon, r)$ on the size of a graph required to approximate a graph of maximum degree at most $\Delta$ up to $\varepsilon$ error in $r$-neighborhood statistics. This provides a negative answer to a question posed by Lov\'asz. Our result is a direct consequence of the recent celebrated work of Bowen, Chapman, Lubotzky, and Vidick, which refutes the Aldous-Lyons conjecture.

Figures

Figures reproduced from arXiv: 2505.06215 by the authors.

Figure 1
Figure 1. Example of encoding a graph as an F2 Schreier graph. For the converse direction let G be an Fd Schreier graph. We encode this into a simple graph Gˆ of maximum degree 3. For each vertex v of G and each ℓ ∈ {a1, . . . , ad, a−1 1 , . . . , a−1 d } we have a [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Example of the encoding of a directed edge Both of these encodings are defined uniquely up to the choice of cyclic ordering at each vertex. Additionally, both encodings are injective maps and therefore do not lose information. It will be important in the following proof that both of these encodings are defined locally, and that they can both be decoded with small errors in the space of neighborhood statistics. Proof… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 12 canonical work pages

  1. [1]

    Processes on unimodular random networks

    David Aldous and Russell Lyons. Processes on unimodular random networks. Electronic Journal of Probability , 12:1454 -- 1508, 2007

    work page 2007

  2. [2]

    (unpublished)

    Noga Alon. (unpublished)

    work page

  3. [3]

    The A ldous-- L yons conjecture i: Subgroup tests, 2024

    Lewis Bowen, Michael Chapman, Alexander Lubotzky, and Thomas Vidick. The A ldous-- L yons conjecture i: Subgroup tests, 2024. https://arxiv.org/abs/2408.00110

    arXiv 2024

  4. [4]

    The A ldous-- L yons conjecture ii: Undecidability, 2024

    Lewis Bowen, Michael Chapman, and Thomas Vidick. The A ldous-- L yons conjecture ii: Undecidability, 2024. https://arxiv.org/abs/2501.00173

    arXiv 2024

  5. [5]

    Action convergence of operators and graphs

    \'A gnes Backhausz and Bal \'a zs Szegedy. Action convergence of operators and graphs. Canadian Journal of Mathematics , 74(1):72--121, 2022

    work page 2022

  6. [6]

    On invariant S chreier structures

    Jan Cannizzo. On invariant S chreier structures. Enseign. Math. , 60(3-4):397--415, 2014

    work page 2014

  7. [7]

    Quick approximation to matrices and applications

    Alan Frieze and Ravindran Kannan. Quick approximation to matrices and applications. Combinatorica , 19:175--220, 02 1999

    work page 1999

  8. [8]

    Convergence of graphs with intermediate density

    P \'e ter Frenkel. Convergence of graphs with intermediate density. Transactions of the American Mathematical Society , 370(5):3363--3404, 2018

    work page 2018

Show all 16 references
  1. [9]

    Some topics in the dynamics of group actions on rooted trees

    Rostislav I Grigorchuk. Some topics in the dynamics of group actions on rooted trees. Proceedings of the Steklov Institute of Mathematics , 273(1):64--175, 2011

    2011

  2. [10]

    Jonathan L. Gross. Every connected regular graph of even degree is a S chreier coset graph. J. Combinatorial Theory Ser. B , 22(3):227--232, 1977

    1977

  3. [11]

    On the density of triangles and squares in regular finite and unimodular random graphs

    Viktor Harangi. On the density of triangles and squares in regular finite and unimodular random graphs. Combinatorica , 33(5):531--548, 2013

    2013

  4. [12]

    MIP*=RE , 2022

    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*=RE , 2022. https://arxiv.org/abs/2001.04383

    2022 arXiv

  5. [13]

    Large networks and graph limits , volume 60

    L \'a szl \'o Lov \'a sz. Large networks and graph limits , volume 60. American Mathematical Soc., 2012

    2012

  6. [14]

    There is an equivalence relation whose von N eumann algebra is not C onnes embeddable, 2025

    Aareyan Manzoor. There is an equivalence relation whose von N eumann algebra is not C onnes embeddable, 2025. https://arxiv.org/abs/2502.06697

    2025 arXiv

  7. [15]

    Invariant S chreier decorations of unimodular random networks

    L \'a szl \'o M \'a rton T \'o th. Invariant S chreier decorations of unimodular random networks. Ann. H. Lebesgue , 4:1705--1726, 2021

    2021

  8. [16]

    Graph Theory and Additive Combinatorics: Exploring Structure and Randomness

    Yufei Zhao. Graph Theory and Additive Combinatorics: Exploring Structure and Randomness . Cambridge University Press, 2023

    2023

Pith tools

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