Pith. sign in

REVIEW 3 major objections 3 minor 33 references

Quantitative analytic stable regularity

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

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

Pith's one-line read This paper proves quantitative stable regularity for real-valued functions, with polynomial bounds.

desk verdict A genuinely new quantitative regularity theorem for [0,1]-valued functions; the tree-level proofs are strong and self-contained, but the headline ladder theorems depend on an unpublished companion. read the letter →

arxiv 2607.21762 v1 pith:MNMHJYSM submitted 2026-07-23 math.LO math.CO

G. Conant , C. Terry This is my paper · ORCID
classification math.LOmath.CO MSC 03C45
keywords stableregularityquantitativeboundsreal-valuedfunctionstreesladdersequipartitionsalmostconstantanalyticsymmetry
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 establishes explicit, polynomial-size versions of stable regularity lemmas for functions f:X×Y→[0,1]. It shows that if f and its transpose omit certain tree-like configurations (the analytic analogue of stability), then both X and Y can be partitioned into very few pieces such that every pair of pieces is almost constant — meaning f is nearly constant on the product. The number of pieces grows only polynomially in 1/ε, where ε is the accuracy. This makes a previously non-quantitative theorem explicit and efficient, and transfers the stable regularity phenomenon from graphs to real-valued functions.

What carries the argument

The central objects are (t,δ)-trees — sequences of rows, columns, and thresholds encoding a δ-separation along a binary tree — and weakly (δ,ε)-good sets, which require that each fiber function is δ-constant off a small exceptional set, on average. The analytic symmetry lemma (Lemma 2.6) asserts that a weakly good pair (A,B) is 4ε-almost (δ1+δ2)-constant; it carries the argument by turning local goodness into global near-constancy. A second mechanism is the random-sampling refinement (Theorem 4.1) that converts partitions of weakly good sets into equipartitions while preserving goodness.

What would settle it

Construct a finite function that omits (t,δ)-trees but for which every equipartition into fewer than, say, 2^{c/ε} parts contains a pair that is not ε-almost (δ+δ')-constant; this would refute the polynomial bound. Alternatively, exhibit a function admitting a ((2k choose k)−1, 2δ)-tree but no (k,δ)-ladder to test the companion theorem on which the ladder versions depend.

Watch

Extended reading notes

Core claim

Theorem 1.13: if f:X×Y→[0,1] omits (t,δ)-trees and its transpose f^opp omits (t',δ')-trees, then for sufficiently large finite X,Y there are equipartitions into ℓ1<62(17/ε)^{t'+1} and ℓ2<62(17/ε)^{t+1} parts such that every pair (X_i,Y_j) is ε-almost (δ+δ')-constant with respect to f. There is a companion version with f-definable partitions and roughly (9/ε)^{2t} parts. The proof runs through an 'analytic symmetry lemma' showing that weakly good pairs are almost constant.

Load-bearing premise

The ladder versions of the results rely on a companion theorem stating that a function admitting a large tree also admits a ladder; if that transfer theorem fails, the stated polynomial bounds for ladder-omitting functions lose their proof.

Editorial extensions

If this is right

  • If correct, every finite function omitting trees admits equipartitions with O_ε((1/ε)^{2t}) parts, making stable regularity polynomial in 1/ε.
  • The f-definable version gives a parallel bound and shows the partition pieces themselves have low descriptive complexity.
  • The result improves the known qualitative theorem by replacing the unspecified bound with explicit polynomial bounds and shrinking the constant-slack 10δ to 4δ (or δ+δ' in the tree formulation).
  • The removal of VC-theory from the equipartitioning step suggests the method applies to arbitrary functions, not just those with bounded covering numbers.

Reading between the lines

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

  • The equivalence between omitted trees and bounded sequential fat-shattering dimension noted in the paper links these regularity bounds to a learning-theoretic quantity; one might expect the polynomial bounds to transfer to sample-complexity statements.
  • The 'weakly good' notion may be useful beyond stability: it shows equipartitioning of almost-constant pieces is possible under average-case sparsity, which could apply to approximate versions of other tame regularity lemmas.
  • The constants 62 and 17 are artifacts of the proof; the true optimal blow-up rate for this problem is left open, and the paper's own example shows the δ+δ' term cannot be improved within this strategy.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper proves quantitative stable regularity lemmas for finite [0,1]-valued functions. It introduces analytic versions of ladders and trees, defines (weakly) good sets for functions, and proves an analytic symmetry lemma (Lemma 2.6) showing that weakly good pairs are almost constant. The self-contained core consists of Theorem 1.13(a), giving f-definable partitions with polynomial bounds for functions omitting trees, and Theorem 1.13(b), giving equipartitions via a new random-sampling argument for weakly good sets. The headline ladder theorems, Theorems 1.9 and 1.10, are then deduced from Theorem 1.13 using Theorem 1.12, which is cited to the companion paper [15]. The appendices compare the results with Chavarria-Conant-Pillay [11] and discuss covering-number approaches.

Significance. If the results are correct, this is a substantial advance: it provides polynomial bounds for stable analytic regularity, extending Malliaris-Shelah from graphs to real-valued functions and giving the first explicit quantitative version of the qualitative theorem from [11]. The paper has notable strengths: the proof of Theorem 1.13 and Lemma 2.6 is detailed and appears checkable; the bounds are explicit; Example 2.7 shows the δ1+δ2 term in Lemma 2.6 is tight; and the weak-goodness/equipartitioning mechanism in Section 4 is an interesting toolbox that avoids VC-theory. However, the ladder versions of the main theorems are conditional on Theorem 1.12, stated as a result of an unpublished companion paper. As currently presented, the paper's abstract-level claims therefore cannot be fully verified from the manuscript alone.

major comments (3)
  1. [§1.7, Theorem 1.12] Theorems 1.9 and 1.10 are the ladder versions advertised in the abstract and introduction, but their proofs depend entirely on Theorem 1.12, cited as [15, Theorem 1.11] from a companion paper 'in preparation'. This theorem is load-bearing: without it, the implications from omitted trees to omitted ladders fail, and Theorems 1.9 and 1.10 have no proof. The manuscript should either include a self-contained proof of Theorem 1.12 or explicitly present Theorems 1.9/1.10 as conditional on [15]. The same issue affects Remark 1.14 and the deductions in §1.7.
  2. [Appendix A, Proposition A.6 and Theorem A.10] The claimed quantitative consequences for the Chavarria-Conant-Pillay theorems rely on Proposition A.6 and Theorem A.10, both cited to [15]. For example, Theorem A.9 uses Proposition A.6(a) to bound ladders in f^opp, and Theorem A.11 uses Theorem A.10. These are not proved in the manuscript. If the appendix is meant to be part of the paper's contribution, these dependencies need to be either proved or clearly marked as conditional on [15].
  3. [Definition 3.1 and Remark A.7] The notion of 'f-definable' is stated without any bound on Boolean complexity. In a finite setting, with arbitrary thresholds allowed, this notion becomes very weak: every union of equivalence classes of points with identical rows is f-definable. The authors acknowledge this in Remark A.7, but the theorem statements in Section 1.6 and Theorem 1.13(a) do not carry any complexity bound. Since the paper's aim is quantitative, the Boolean complexity of the partitions should be tracked, or the definability claim should be qualified. As written, the 'f-definable' feature of the main theorems is not a quantitative assertion.
minor comments (3)
  1. [Theorems 1.10, 1.13(b), 5.1, 5.2] The 'sufficiently large' hypotheses are not quantified. The proofs show that the required lower bounds depend on the parameters, but for a quantitative paper it would be helpful to state this dependence explicitly, or at least to say that the bounds are independent of |X| and |Y| once the threshold is met.
  2. [Remark 1.14(2)] There is a grammatical typo: 'or 2(δ+δ′) term Theorems 1.9 and 1.10' should read 'or the 2(δ+δ′) term in Theorems 1.9 and 1.10'.
  3. [§1.6, after Theorem 1.9] The claim that Theorem 1.9 implies Theorem 1.7(a) uses Proposition A.6(a), which is introduced much later in Appendix A and is itself cited to [15]. A forward reference and a short explanation of how the f^opp ladder bound is obtained would help the reader.

Circularity Check

1 steps flagged · score 4.0 of 10

Ladder-version main theorems import the key tree-to-ladder transfer from the authors' own unpublished companion paper; the tree theorems themselves are self-contained.

  1. self citation load bearing [§1.7 (Theorem 1.12; Proofs of Theorems 1.9 and 1.10); also relied on in Appendix A (Theorem A.9)]
    "In particular, the following is one of the main results of our companion paper. Theorem 1.12 ([15, Theorem 1.11]). Given k≥1 and δ>0, if f:X×Y→[0,1] admits a ((2k choose k)−1,2δ)-tree, then f admits a (k,δ)-ladder. ... Proof of Theorem 1.9. Theorems 1.13(a) and 1.12 immediately yield the statement..."

    The ladder-form main results are not established by this paper's own lemmas: Theorem 1.9's proof explicitly reduces to 'Theorems 1.13(a) and 1.12 immediately yield the statement,' and Theorem 1.10 likewise. Theorem 1.12 is a tree-to-ladder transfer with the exact parameter regime needed for the polynomial bounds, and it is stated as a main result of the authors' own companion paper [15], which is listed as 'in preparation.' Thus the claimed polynomial-bound ladder theorems rest on a load-bearing self-citation rather than on a proof contained here. This is not a definitional reduction, and the tree versions (Theorems 1.13(a),(b)) are proved self-contained, so the circularity is partial rather than total.

full rationale

No fitted-input-called-prediction or self-definitional circularity appears. The internal derivation chain for the tree versions is explicit and self-contained: Proposition 2.2 gives the separation lemma; Lemma 2.6 (analytic symmetry lemma) is proved directly from the definitions with a contradiction/AM-GM argument, and its sharpness is checked by an internal example (Example 2.7); Lemma 3.3 and Corollaries 3.4/3.5 build good f-definable sets from omitted trees; Theorem 4.1 refines weakly good partitions into equipartitions using only Hoeffding's inequality; Section 5 applies these to prove Theorem 1.13(b). None of these steps assumes the conclusion. The external qualitative theorem [11] is used only for motivation and comparison, not as a premise. The one genuine dependency is Theorem 1.12, imported from the authors' own companion paper [15], listed as 'in preparation'; it is essential for the ladder versions Theorems 1.9 and 1.10, and for the quantitative comparisons in Appendix A. Since the central tree-theoretic content is independently proven but the claimed ladder package is not fully self-contained, the appropriate score is 4 rather than 0-2, and certainly not 6+, because the paper itself identifies the tree versions as the actual main results and the ladder statements as corollaries modulo Theorem 1.12.

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

No numbers are fitted to data. The theorem parameters (k,k',δ,δ',ε,t,t') are quantified hypotheses; the constants 9, 17, 62, 527 arise from checkable algebra and are not tuned to observations. The definitions of weakly good sets, analytic ladders, and analytic trees are proof devices, not new postulates requiring independent evidence.

assumptions (4)
  • ad hoc to paper Theorem 1.12: omitting ((2k choose k)−1, 2δ)-trees implies omitting (k,δ)-ladders.
    Unproved here; cited from companion paper [15] (in preparation). Used in the deductions of Theorems 1.9 and 1.10.
  • standard math Hoeffding's inequality for sampling without replacement.
    Used as Proposition 4.2 to control averages of functions under random equipartitions.
  • domain assumption Finiteness and [0,1]-valued codomain of f, with ladders/trees defined on finite sets.
    All results are stated for finite X,Y and f:X×Y→[0,1]; the hypotheses 'omits (t,δ)-trees' or 'omits (k,δ)-ladders' are domain assumptions.
  • domain assumption 'Sufficiently large' in Theorems 1.10, 1.13(b), 5.1, 5.2.
    The proofs require |X|,|Y| large enough for the exponential inequality in Lemma 4.6; the threshold is not quantified in the theorem statements.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantitative analytic stable regularity." pith.science (2026). https://pith.science/paper/MNMHJYSM

@misc{pith2026260721762,
  author       = {Pith},
  title        = {Pith review of: Quantitative analytic stable regularity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MNMHJYSM}},
  note         = {Machine review of arXiv:2607.21762}
}
read the original abstract

We prove quantitative stable regularity lemmas for binary real-valued functions, extending the work of Malliaris and Shelah for stable graphs. The statements of our results are modeled after non-quantitative theorems for stable functions due to Chavarria, Conant, and Pillay. One of the key tools in our quantitative proof is an "analytic symmetry lemma", which gives a function-theoretic analogue of the fact that a pair of good sets in a graph has density close to 0 or 1. We also develop a function-theoretic treatment of Malliaris and Shelah's random sampling method for refining partitions consisting of good sets into equipartitions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 6 linked inside Pith

  1. [15]

    ,Encoding orders and trees in real-valued functions, in preparation

  2. [11]

    Chavarria, G

    N. Chavarria, G. Conant, and A. Pillay,Continuous stable regularity, J. Lond. Math. Soc. (2)109 (2024), no. 1, Paper No. e12822, 36. MR 4680211

    2024

  3. [1]

    Ackerman, C

    N. Ackerman, C. Freer, and R. Patel,Stable regularity for relational structures, arXiv:1712.09305 (2017)

    arXiv 2017

  4. [2]

    Aiyer, Y

    S. Aiyer, Y. Mansour, S. Moran, H. Shao, and T. Waknine,Scale-sensitive shattering: Learnability and evaluability at optimal scale, arXiv:2605.13684 (2026)

    arXiv 2026

  5. [3]

    N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler,Scale-sensitive dimensions, uniform conver- gence, and learnability, J. ACM44(1997), no. 4, 615–631. MR 1481318

    1997

  6. [4]

    N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy,Efficient testing of large graphs, Combinatorica20 (2000), no. 4, 451–476. MR 1804820

    2000

  7. [5]

    N. Alon, E. Fischer, and I. Newman,Efficient testing of bipartite graphs for forbidden induced subgraphs, SIAM J. Comput.37(2007), no. 3, 959–976. MR 2341924

    2007

  8. [6]

    Anderson,Generically Stable Measures and Distal Regularity in Continuous Logic, arXiv:2310.06787 (2023)

    A. Anderson,Generically Stable Measures and Distal Regularity in Continuous Logic, arXiv:2310.06787 (2023)

    arXiv 2023

Show all 33 references
  1. [7]

    Anderson and M

    A. Anderson and M. Benedikt,From Learnable Objects to Learnable Random Objects, arXiv:2504.00847, Journal of Machine Learning Research (2026), accepted

    2026 arXiv

  2. [8]

    Bardenet and O.-A

    R. Bardenet and O.-A. Maillard,Concentration inequalities for sampling without replacement, Bernoulli 21(2015), no. 3, 1361–1385. MR 3352047

    2015

  3. [9]

    Ben Yaacov, A

    I. Ben Yaacov, A. Berenstein, C. W. Henson, and A. Usvyatsov,Model theory for metric structures, Model theory with applications to algebra and analysis. Vol. 2, London Math. Soc. Lecture Note Ser., vol. 350, Cambridge Univ. Press, Cambridge, 2008, pp. 315–427. MR 2436146 (2009j:03061)

    2008

  4. [10]

    Ben Yaacov and A

    I. Ben Yaacov and A. Usvyatsov,Continuous first order logic and local stability, Trans. Amer. Math. Soc.362(2010), no. 10, 5213–5259. MR 2657678

    2010

  5. [12]

    Chernikov and S

    A. Chernikov and S. Starchenko,Regularity lemma for distal structures, J. Eur. Math. Soc. (JEMS)20 (2018), no. 10, 2437–2466. MR 3852184

    2018

  6. [13]

    ,Definable regularity lemmas for NIP hypergraphs, Q. J. Math.72(2021), no. 4, 1401–1433. MR 4350155

    2021

  7. [14]

    Conant and C

    G. Conant and C. Terry,Pseudofinite proofs of the stable graph regularity lemma, Model Theory: Se- lected Lectures from the 2021 Thematic Program, Fields Institute Communications, vol. 92, Springer Nature Switzerland, 2026, pp. 45–61

    2021

  8. [16]

    Daskalakis and N

    C. Daskalakis and N. Golowich,Fast rates for nonparametric online learning: from realizability to learning in games, STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, [2022]©2022, pp. 846–859. MR 4490045 15Recall that by Exampl...

    2022

  9. [17]

    Fox and L

    J. Fox and L. M. Lov´ asz,A tight lower bound for Szemer´ edi’s regularity lemma, Combinatorica37 (2017), no. 5, 911–951. MR 3737374

    2017

  10. [18]

    W. T. Gowers,Lower bounds of tower type for Szemer´ edi’s uniformity lemma, Geom. Funct. Anal.7 (1997), no. 2, 322–337. MR 1445389

    1997

  11. [19]

    Green and T

    B. Green and T. Tao,An arithmetic regularity lemma, an associated counting lemma, and applications, An irregular mind, Bolyai Soc. Math. Stud., vol. 21, J´ anos Bolyai Math. Soc., Budapest, 2010, pp. 261–

    2010

  12. [20]

    Hodges,Encoding orders and trees in binary relations, Mathematika28(1981), no

    W. Hodges,Encoding orders and trees in binary relations, Mathematika28(1981), no. 1, 67–71

    1981

  13. [21]

    Hoeffding,Probability inequalities for sums of bounded random variables, J

    W. Hoeffding,Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58(1963), 13–30. MR 144363

    1963

  14. [22]

    Kalyanasundaram and A

    S. Kalyanasundaram and A. Shapira,A Wowzer-type lower bound for the strong regularity lemma, Proc. Lond. Math. Soc. (3)106(2013), no. 3, 621–649. MR 3048552

    2013

  15. [23]

    Lov´ asz and B

    L. Lov´ asz and B. Szegedy,Szemer´ edi’s lemma for the analyst, Geom. Funct. Anal.17(2007), no. 1, 252–270. MR 2306658

    2007

  16. [24]

    ,Regularity partitions and the topology of graphons, An irregular mind, Bolyai Soc. Math. Stud., vol. 21, J´ anos Bolyai Math. Soc., Budapest, 2010, pp. 415–446. MR 2815610

    2010

  17. [25]

    Malliaris and S

    M. Malliaris and S. Shelah,Regularity lemmas for stable graphs, Transactions of the American Mathe- matical Society366(2014), no. 3, 1551–1585

    2014

  18. [26]

    Malliaris and A

    M. Malliaris and A. Pillay,The stable regularity lemma revisited, Proc. Amer. Math. Soc.144(2016), no. 4, 1761–1765

    2016

  19. [27]

    Pillay,Domination and regularity, Bull

    A. Pillay,Domination and regularity, Bull. Symb. Log.26(2020), no. 2, 103–117

    2020

  20. [28]

    Rakhlin, K

    A. Rakhlin, K. Sridharan, and A. Tewari,Sequential complexities and uniform martingale laws of large numbers, Probab. Theory Related Fields161(2015), no. 1-2, 111–153. MR 3304748

    2015

  21. [29]

    Szemer´ edi,Regular partitions of graphs, Probl` emes combinatoires et th´ eorie des graphes (Colloq

    E. Szemer´ edi,Regular partitions of graphs, Probl` emes combinatoires et th´ eorie des graphes (Colloq. In- ternat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–

    1976

  22. [30]

    Tao,Structure and randomness in combinatorics, FOCS 2007 lecture notes, available at:https: //arxiv.org/abs/0707.4269

    T. Tao,Structure and randomness in combinatorics, FOCS 2007 lecture notes, available at:https: //arxiv.org/abs/0707.4269

    2007 arXiv

  23. [31]

    Discrete Math.1(2006), no

    ,Szemer´ edi’s regularity lemma revisited, Contrib. Discrete Math.1(2006), no. 1, 8–28. MR 2212136

    2006

  24. [32]

    Terry and J

    C. Terry and J. Wolf,Irregular triads in 3-uniform hypergraphs, arXiv:2111.01737 (2021)

    2021 arXiv

  25. [33]

    Zhao,Graph theory and additive combinatorics—exploring structure and randomness, Cambridge University Press, Cambridge, 2023

    Y. Zhao,Graph theory and additive combinatorics—exploring structure and randomness, Cambridge University Press, Cambridge, 2023. MR 4603631 Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago Email address:gconant@uic.edu Department of M...

    2023

Pith tools

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