{"id":"75d76999-a6e1-411d-a437-8b685ecaa6ae","arxiv_id":"2505.06215","paper_version":3,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every maximum degree Δ ≥ 3, no computable function of the error ε and radius r bounds the size of a graph that reproduces r-neighborhood statistics up to ε.","lead":"For graphs with maximum degree at least 3, there is no computable way to bound the size of a small graph that mimics the local statistics of any bounded-degree graph, answering a question of Lovász in the negative. The proof piggybacks on the recent undecidability-based refutation of the Aldous-Lyons conjecture, showing that a computable bound would solve the halting problem.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main reduction is sound; the load-bearing dependency is the quoted BCLV/BCV undecidability theorem, with a secondary gap in Lemma 7's quantitative decoding step. No fatal flaw found; verdict unchanged.","rationale":"After independent scrutiny, the central reduction in Theorem 6 is sound: the finite radius r determined by the support K of T, the approximation of val(T,G) from r-neighborhood statistics, the brute-force maximization β_T,Θ, and the halting test β_T,Θ > 1 − λ_M all line up. The main risk is external: Theorem 8 is a deep recent result, and the paper is transparent about relying on it. That is a dependency, not an internal inconsistency. The only internal gap is the unquantified error transfer in Lemma 7. I checked the decoding maps: they are local, and the degree-weighted versus vertex-weighted statistics can be inverted with Lipschitz constants bounded in terms of Δ and d, so the gap is fillable. Thus the concern does not change the reader's ACCEPT verdict. A revision could usefully add explicit bounds or a more detailed reference for Lemma 7, but the central mathematical claim stands as presented.","tokens_in":10277,"tokens_out":31172,"duration_ms":355189,"concrete_test":"Re-derive the second half of Lemma 7 with explicit error bounds: choose r0 = C(d)·r and ε0 = ε/(C(d)·|F*_d(r)|) for a sufficiently large C(d), and prove that for every rooted graph F• of radius r, |u*_r(F•,G) − u*_r(F•,G′)| < ε whenever u_{r0}(·,Ĝ) and u_{r0}(·,Ĝ′) are ε0-close. If such explicit bounds cannot be exhibited, the reduction from a graph regularity bound to a Schreier regularity bound fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing assumption is Theorem 8: a computable map from Turing machines to continuous rational functions T_M on P(F_d) with a rational gap λ_M. Theorem 6 is a clean contradiction: a hypothetical computable Schreier regularity bound yields uniform upper bounds β_T,Θ on sofic values, which would decide halting via the condition β_T,Θ > 1 − λ_M. If Theorem 8 is misquoted or false, the main claim collapses; the paper cites [BCLV24, BCV24] and does not prove it. A secondary, internal soft spot is Lemma 7 in Appendix A. The direction used for Theorem 3 encodes an F_d Schreier graph G as a degree-3 graph Ĝ, applies the hypothetical graph regularity bound, and decodes the approximant back to a Schreier graph. The proof only says 'choosing ε0 small enough and r0 large enough' to make the error transfer work. This requires showing that the local maps between rooted balls in G and decoded G′ are Lipschitz with constants independent of the graph; the degree-weighted to vertex-weighted counting in the decoding is never quantified. This is standard and evidently repairable, but as written it is the least secure internal step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10499,"tokens_out":3571,"duration_ms":31325,"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":[{"comment":"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.","section":"Appendix A, proof of Lemma 7"},{"comment":"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.","section":"Section 2, Theorem 8"},{"comment":"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.","section":"Section 3, Remark 11"}],"minor_comments":[{"comment":"The notation B_r(v) is used before it is formally defined; please define the radius-r ball of a vertex explicitly.","section":"Section 1, equation (1)"},{"comment":"There is a typo: the bound should be N*_d(ε,r), not N*(ε,r).","section":"Section 2, after Definition 5"},{"comment":"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.","section":"Section 2, Theorem 6"},{"comment":"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.","section":"Section 3, before Theorem 10"},{"comment":"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 Δ.","section":"Section 4, proof of Theorem 13"},{"comment":"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.","section":"Section 5, Problem 15"},{"comment":"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.","section":"Appendix A, Figure 2"},{"comment":"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.","section":"References"}],"recommendation":"accept","confidential_remarks":"The paper is a well-written short note that answers a question of Lovász using the recent BCLV/BCV breakthrough. The main theorem is likely correct, and the proof is transparent. The main weakness is the quantitative control in Lemma 7, which is standard but deserves a full proof. The external dependence on [BCLV24, BCV24] is unavoidable and the authors are upfront about it. I see no obstacle to publication after the minor polishing described in the report. The novelty is modest but appropriate for a note of this type, and the paper is suitable for the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe bottom line: this short paper shows that for any Δ ≥ 3 there is no computable bounded-degree regularity bound, answering a question Lovász explicitly posed. The proof is a clean diagonalization against the BCLV/BCV undecidability theorem. If you work on graph limits or local convergence, this is worth your time.\n\nWhat's new: the non-computability result itself, which does not appear in BCLV. They also notice the converse direction—a positive Aldous–Lyons answer would have implied a computable bound (Remark 11)—and they convert non-computability into a local-statistic decision problem (Section 4). These are genuine additions, not restatements.\n\nThe core reduction (Theorem 6 from Theorem 8) is rigorous and easy to check. The inequality β ≤ val_sof(T) ≤ β + Θ is correct, and the halting criterion 'M halts iff β > 1 − λ_M' is sound. The paper is transparent that the load-bearing external input is the BCLV theorem, and cites it precisely. No circularity; no fitted parameters; no invented entities. The citation pattern looks appropriate.\n\nThe soft spot is Appendix A. Lemma 7's proof of the equivalence between graph and Schreier regularity bounds says 'choosing ε0 small enough and r0 large enough' to make the error transfer work, but never quantifies it. You need to show that the local encoding/decoding maps are Lipschitz with constants independent of the graph, and the degree-weighted versus vertex-weighted counting in the decoding is not pinned down. This is the least secure internal step. My reading is that it is standard and repairable, but as written it is a gap in an otherwise clean argument. The main theorem does not collapse; it depends on the external BCLV theorem, which is quoted rather than proved, and that is the right division of labor.\n\nWho is this for: anyone following the Aldous–Lyons saga or interested in effective versions of Szemerédi-type statements. It deserves a serious referee; the referee should focus on Appendix A and check the BCLV statement is quoted accurately. I'd bring it to reading group and would cite it if I were writing in this area.\n\nRecommendation: send it to peer review. The paper is concise, honest, and the main claim is important.","headline":"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.","tokens_in":11079,"tokens_out":2245,"would_cite":true,"duration_ms":22108,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","03D35"],"pacs":[],"model":"deepseek-v4-flash","headline":"For graphs of maximum degree at least 3, no computable size bound exists for approximating them by smaller graphs.","keywords":["regularity lemma","bounded degree graphs","neighborhood statistics","sofic values","undecidability","Schreier graphs","Aldous-Lyons conjecture","computability"],"falsifier":"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.","tokens_in":10069,"feed_emoji":"🚫","tokens_out":9683,"duration_ms":92385,"temperature":0.7,"pith_summary":"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.","feed_headline":"No computable bound for approximating bounded-degree graphs","feed_subtitle":"Even when the maximum degree is fixed, the required approximation size cannot be computed from accuracy and radius.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"This reference supplies the undecidability theorem that encodes Turing machine halting into sofic values of continuous rational functions; the proof of Theorem 6 contradicts the computability of such values.","marker":"[BCLV24]"},{"why":"This companion reference provides the full undecidability statement and the subgroup-test framework on which Theorem 8 rests.","marker":"[BCV24]"},{"why":"This reference poses the question on page 358 whether the regularity bound can be made effective, which Theorem 3 answers negatively, and supplies the graph limit background.","marker":"[Lov12]"},{"why":"This reference states Alon's theorem that a nonconstructive bound $N_\\Delta(\\varepsilon,r)$ exists, the object whose computability is in question, obtained from total boundedness of the space of neighborhood statistics.","marker":"[Zha23]"},{"why":"This reference provides the dense-graph analogue with explicit computable bounds and the weak regularity lemma method that motivates the bounded-degree question.","marker":"[FK99]"},{"why":"This reference defines the Aldous–Lyons conjecture; the quoted refutation of it is the source of the undecidability used here.","marker":"[AL07]"},{"why":"This reference is cited for the classical fact that finite graphs can be encoded as Schreier coset graphs, the basis of Lemma 7's equivalence between the two versions of the theorem.","marker":"[Gro77]"}],"fun_headline_variants":["No computable bound for approximate bounded-degree graphs","Graph size bound uncomputable for bounded-degree approximation","Bounded-degree approximation: no recursive size bound","Approximating bounded-degree graphs: bound noncomputable","Regularity lemma has no computable bound for bounded degree"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["No computable bound for approximate bounded-degree graphs","Graph size bound uncomputable for bounded-degree approximation","Bounded-degree approximation: no recursive size bound","Approximating bounded-degree graphs: bound noncomputable","Regularity lemma has no computable bound for bounded degree"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000638,"raw_usage":{"total_tokens":2895,"prompt_tokens":857,"completion_tokens":2038,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":473,"completion_tokens_details":{"reasoning_tokens":1962}},"tokens_in":473,"tokens_out":2038,"duration_ms":16358,"temperature":1.0,"reasoning_tokens":1962,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:47:10.527580+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}