Pith. sign in

REVIEW 6 minor 30 references

The VC-dimension of random subsets of finite groups

T0 review · 0 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read For a Bernoulli-random subset of any finite group of order N, the VC-dimension of its translates is almost surely (1+o(1)) log_r N.

desk verdict A short, correct paper that proves the expected law of large numbers for VC-dimension of random translates in finite groups and sharpens a conjecture; the referee will find only a harmless typo. read the letter →

arxiv 2506.14219 v1 pith:7CWOWOTJ submitted 2025-06-17 math.CO math.NTmath.PR

Brad Rodgers , Anurag Sahay This is my paper · ORCID
classification math.COmath.NTmath.PR MSC 05D4005C8005C25
keywords VC-dimensionrandomsubsetsfinitegroupsCayleygraphscoveringlemmasBernoullisamplingPaleylawoflargenumbers
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

For a finite group $G$ of order $N$, pick each element independently with probability $p$. The paper proves a law of large numbers for the VC-dimension of the set system of left translates $\{tA : t \in G\}$: almost surely, it equals $(1+o(1)) \log_r N$, where $r = \min(p,1-p)^{-1}$. In particular, when $p=1/2$ the VC-dimension is asymptotically $\log_2 N$, essentially the maximum possible for any set system on $N$ points. The same result holds for the random Cayley graph on $G$ generated by $A$. This answers a question raised for Paley graphs and confirms that random translate families have a sharply predictable shattering behaviour in every finite group.

What carries the argument

The argument is carried by two combinatorial lemmas applied to an arbitrary subset $U$ of $G$ of size $k$. Lemma 5 (proved in the paper by a greedy maximal construction) finds a set $S$ of at least $N/k^2$ group elements such that the translates $s_1U, \dots, s_\ell U$ are pairwise disjoint, giving an approximate tiling of $G$. Lemma 6 (a covering lemma from the literature) says that any subset $S$ of size $\ell$ can be completed to a cover of $G$ by at most $(N/\ell)(\log \ell + 1)$ of its translates. The lower bound uses the approximate tiling to obtain independent copies of the sampling on disjoint blocks, then shows that every binary pattern appears; the upper bound splits the full family of translates into $m \ll k^3$ subfamilies via the covering lemma, applies a union bound and Chernoff's inequality to each, and concludes with a combinatorial count of subsets of size $k$.

What would settle it

A concrete check: for $G = \mathbb{Z}/N\mathbb{Z}$ with $N = 2^m$ and $p = 1/2$, enumerate the translates of a Bernoulli sample and test shattering for $k = m \pm C\log m$; if for some moderate $m$ the empirical VC-dimension falls outside $\log_2 N \pm 10\log_2\log_2 N$ with probability not tending to 0, the theorem's quantitative form fails.

Watch

Extended reading notes

Core claim

Theorem 1 states that for fixed $0<p<1$, with $r = [\min(p,1-p)]^{-1}$, for any finite group $G$ of order $N$ and $A$ a Bernoulli($p$) random subset, $|\operatorname{VCdim}(A) - \log_r N| \le 10\log_r\log_r N$ with probability $1 - O(1/N^{\eta})$ for every fixed $\eta > 0$. Thus $\operatorname{VCdim}(A) = (1+o(1))\log_r N$ asymptotically almost surely. Since the neighbourhood family of the Cayley graph $\operatorname{Cay}(G,A)$ is exactly the family of translates of $A$, the same statement describes the VC-dimension of a random Cayley graph (Theorem 2). The proof splits into a lower bound, showing that a set of size slightly less than $\log_r N$ is shattered with high probability, and an upper bound, showing that no set of size slightly larger is shattered; both rest on tiling $G$ approximately by disjoint translates of the set in question, and the upper bound additionally uses a covering lemma supplied by the literature.

Load-bearing premise

The load-bearing premise is the cited covering lemma (Lemma 6), which guarantees that any subset of a finite group can be covered by few translates; if that lemma failed, the upper-bound argument would collapse, though the lemma is standard and published.

Editorial extensions

If this is right

  • For $p = 1/2$ and $G = \mathbb{Z}/N\mathbb{Z}$, the random Cayley graph model has VC-dimension asymptotically $\log_2 N$, lending quantitative support to the conjecture, raised in the paper's motivation, that Paley graphs satisfy the same law.
  • The bound is uniform over all groups of order $N$, so the law of large numbers holds for any sequence of finite groups, abelian or not.
  • The statement transfers automatically to the variant of VC-dimension defined with the restricted translate family and to Cayley sum graphs, because those set families differ from the translate family by at most 1.
  • At $p=1/2$ the VC-dimension is essentially as large as the trivial upper bound $\log_2 N$, showing that random translate families saturate the maximum in the balanced case.

Reading between the lines

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

  • The proof's reliance only on tiling and covering suggests the same $(1+o(1))\log_r N$ law should hold when $A$ is sampled uniformly from all subsets of size $d = pN$, a model the paper explicitly leaves open.
  • The coupon-collector analogy at the end of the paper hints at a limiting distribution for $\operatorname{VCdim}(A) - \log_r N$ after suitable normalization; this is not proved here but is a natural next question.
  • If $p = p(N)$ tends to 0 slowly, the estimate likely persists; following the proof with a slowly decaying $p$ would give a quantitative range, which the paper does not specify.
  • For higher-power residue sets in $\mathbb{Z}/N\mathbb{Z}$, the paper's Conjecture 4 predicts VC-dimension asymptotic to $\log_r N$, in contrast to an earlier conjecture of $\log_2 N$; a numerical computation for small $r$-th power sets could test this.
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

0 major / 6 minor

Summary. The paper studies the VC-dimension of the set system formed by left translates of a Bernoulli(p) random subset A of a finite group G of order N, equivalently the VC-dimension of the corresponding random Cayley graph. The main theorem (Theorems 1 and 2) states that, for fixed p, with r = 1/min(p,1-p), one has |VCdim(A) - log_r N| <= 10 log_r log_r N with probability 1 - O(1/N^eta) for any fixed eta, uniformly over all finite groups. The lower bound is proved in Section 3 using a greedy packing of disjoint translates and a union bound; the upper bound in Section 4 uses the Bollobás-Janson-Riordan covering lemma, a pigeonhole argument, and Chernoff's inequality. The paper also discusses consequences for Paley graphs and higher-power-residue Cayley graphs, proposing an alternative to a conjecture of McDonald-Sahay-Wyman.

Significance. If correct, this is a clean and sharp law of large numbers for the VC-dimension of random algebraic set systems, answering a question raised in [18]. The proof is elementary and explicit, with constants uniform over all finite groups, and the probability bounds are strong enough for Borel-Cantelli applications. The lower and upper bounds are both fully proved, and the speculative part about deterministic residue graphs is clearly separated from the proven random statement. The only external ingredient is a standard covering lemma of Bollobás-Janson-Riordan, cited from [5] and applied exactly as intended. These are notable strengths: the result is uniform, the argument is self-contained modulo that lemma, and the conjectural discussion is honest about the distinction between random and deterministic behavior.

minor comments (6)
  1. [§3, Step 1] The displayed bound '(1 - r^{-k})^{ell+1}' should read '(1 - r^{-k})^ell'. Since 1 - r^{-k} < 1, the exponent ell+1 gives a smaller quantity, so as written the inequality is in the wrong direction; replacing it by the ell-th power leaves the subsequent estimate unchanged.
  2. [§4, Step 3] The formula for the expectation should be E X_v = C(k,10) p^{k-10} (1-p)^{10}, not C(k,10) p^{k-10} (1-p^{10}). The proof is unaffected because the missing factor is absorbed into the p-dependent constant.
  3. [§1.3] In the sentence 'for r in N, r >= 3 such that 3 N ≡ 1 (mod r)', the '3' appears spurious; in view of footnote 3 the intended condition is 'N ≡ 1 (mod r)'.
  4. [§1.3] The phrase 'we conjecture that alpha(r) = alpha(r) = log_r 2' contains a duplicated left-hand side; it should presumably be 'alpha(r) = log_r 2'.
  5. [§1.1] There are minor typographical errors, e.g. 'susbsets' for 'subsets' and 'The VC-dimension of the F' for 'The VC-dimension of F'.
  6. [§3] The reduction to p <= 1/2 is asserted by symmetry; a one-line justification via VCdim(A) = VCdim(G\A) would improve readability, since the proof relies on this reduction.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the theorem is proven from a proved tiling lemma, a cited external covering lemma, and Chernoff's inequality; no fitted quantity is renamed as a prediction.

full rationale

The main claim (Theorem 1) is derived by a direct probabilistic argument. The lower bound (Section 3) uses Lemma 5, proved in the paper by a greedy maximal packing of disjoint translates, and the upper bound (Section 4) uses Lemma 6, the Bollobás–Janson–Riordan covering lemma, which is cited as an external standard result from [5] and applied exactly as stated. Neither lemma is defined in terms of VC-dimension or of the random subset A, and neither is fitted to the data being predicted. The remaining ingredients are the Chernoff bound and elementary union bounds. The conjectures in Section 1.3 about Paley graphs and higher-power residues are explicitly consequences or analogues of the random model, not inputs to the proof. The only self-citation is [18] (McDonald–Sahay–Wyman), used to frame the question and conjectures; Theorem 1 does not depend on any claim from [18]. All other cited results (e.g., [5], [29]) are independent published tools. There is no fitted parameter renamed as a prediction and no assertion whose validity reduces by construction to its own input. A minor typo in the displayed expectation in Step 3 (k^{10} p^k rather than k^{10} p^{k-10}) is cosmetic because p is fixed and does not affect the stated bound.

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

The proof is essentially self-contained: Lemma 5 is proved in the paper, and the only unproved inputs are two classical external results, the Bollobas-Janson-Riordan covering lemma and the Chernoff bound. No quantities are fitted to data, and no new mathematical objects are postulated.

assumptions (2)
  • standard math Bollobas-Janson-Riordan covering lemma (Lemma 6): for any S subset G with |S| = ell, there exists T with |T| <= (N/ell)(log ell + 1) and G = S T.
    External theorem cited as Corollary 3.2 of [5]; the upper bound in Step 3 of Section 4 depends on it to cover G with m << k^3 translates.
  • standard math Chernoff bound for sums of independent Bernoulli random variables, as given in Vershynin [29, Theorem 2.3.1].
    Used in Step 3 of Section 4 to bound the probability that X_1 + ... + X_ell >= k^6 when the expectation is O(k^{-2}).

how reviews work

0 comments
Cite this review

Pith. "Pith review of The VC-dimension of random subsets of finite groups." pith.science (2026). https://pith.science/paper/7CWOWOTJ

@misc{pith2026250614219,
  author       = {Pith},
  title        = {Pith review of: The VC-dimension of random subsets of finite groups},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7CWOWOTJ}},
  note         = {Machine review of arXiv:2506.14219}
}
abstract

For a random subset of a finite group $G$ of cardinality $N$, we consider the VC-dimension of the family of its translates (equivalently the VC-dimension of a random Cayley graph) and prove a law of large numbers as $N\rightarrow\infty$. This answers a question of McDonald--Sahay--Wyman.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 28 canonical work pages

  1. [18]

    Brian McDonald, Anurag Sahay, and Emmett L. Wyman. The VC dimension of quadratic residues in finite fields. Discrete Math., 348(1):Paper No. 114192, 13, 2025. 2, 3, 4, 5

    work page 2025

  2. [5]

    On covering by translates of a set

    B´ ela Bollob´ as, Svante Janson, and Oliver Riordan. On covering by translates of a set. Random Structures Algorithms, 38(1-2):33–67, 2011. 7

    work page 2011

  3. [1]

    The chromatic number of random Cayley graphs

    Noga Alon. The chromatic number of random Cayley graphs. European J. Combin., 34(8):1232–1243, 2013. 4

    work page 2013

  4. [2]

    Efficient arithmetic regularity and removal lemmas for induced bipartite patterns

    Noga Alon, Jacob Fox, and Yufei Zhao. Efficient arithmetic regularity and removal lemmas for induced bipartite patterns. Discrete Anal., pages Paper No. 3, 14, 2019. 2

    work page 2019

  5. [3]

    Random Cayley graphs and expanders

    Noga Alon and Yuval Roichman. Random Cayley graphs and expanders. Ran- dom Structures Algorithms , 5(2):271–284, 1994. 4

    work page 1994

  6. [4]

    The Vapnik- Chervonenkis dimension of a random graph

    Martin Anthony, Graham Brightwell, and Colin Cooper. The Vapnik- Chervonenkis dimension of a random graph. volume 138, pages 43–56. 1995. 14th British Combinatorial Conference (Keele, 1993). 3

    work page 1995

  7. [6]

    F. R. K. Chung, R. L. Graham, and R. M. Wilson. Quasi-random graphs. Combinatorica, 9(4):345–362, 1989. 4

    work page 1989

  8. [7]

    Conant, A

    G. Conant, A. Pillay, and C. Terry. Structure and regularity for subsets of groups with finite VC-dimension. J. Eur. Math. Soc. (JEMS) , 24(2):583–621,

    work page

Show all 30 references
  1. [8]

    Approximate subgroups with bounded VC- dimension

    Gabriel Conant and Anand Pillay. Approximate subgroups with bounded VC- dimension. Math. Ann., 388(1):1001–1043, 2024. 1, 2

    2024

  2. [9]

    On the clique number of random Cayley graphs and related topics.preprint, arXiv:2412.21194,

    David Conlon, Jacob Fox, Huy Tuan Pham, and Liana Yepremyan. On the clique number of random Cayley graphs and related topics.preprint, arXiv:2412.21194,

    arXiv

  3. [10]

    Erd˝ os and A

    P. Erd˝ os and A. R´ enyi. On a classical problem of probability theory. Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl., 6:215–220, 1961. 12

    1961

  4. [11]

    A semi-algebraic version of Zarankiewicz’s problem

    Jacob Fox, J´ anos Pach, Adam Sheffer, Andrew Suk, and Joshua Zahl. A semi-algebraic version of Zarankiewicz’s problem. J. Eur. Math. Soc. (JEMS) , 19(6):1785–1810, 2017. 1

    2017

  5. [12]

    Erd˝ os-Hajnal conjecture for graphs with bounded VC-dimension

    Jacob Fox, J´ anos Pach, and Andrew Suk. Erd˝ os-Hajnal conjecture for graphs with bounded VC-dimension. Discrete Comput. Geom., 61(4):809–829, 2019. 1, 3

    2019

  6. [13]

    Bounded VC-dimension implies the Schur-Erd˝ os conjecture.Combinatorica, 41(6):803–813, 2021

    Jacob Fox, J´ anos Pach, and Andrew Suk. Bounded VC-dimension implies the Schur-Erd˝ os conjecture.Combinatorica, 41(6):803–813, 2021. 1, 3

    2021

  7. [14]

    Counting sets with small sumset, and the clique number of random Cayley graphs

    Ben Green. Counting sets with small sumset, and the clique number of random Cayley graphs. Combinatorica, 25(3):307–326, 2005. 4

    2005

  8. [15]

    Counting sets with small sumset and applications

    Ben Green and Robert Morris. Counting sets with small sumset and applications. Combinatorica, 36(2):129–159, 2016. 4

    2016

  9. [16]

    Improved inci- dence bounds over arbitrary finite fields via the VC-dimension theory

    Alex Iosevich, Thang Pham, Steven Senger, and Michael Tait. Improved inci- dence bounds over arbitrary finite fields via the VC-dimension theory. European THE VC-DIMENSION OF RANDOM SUBSETS OF FINITE GROUPS 14 J. Combin. , 118:Paper No. 103928, 9, 2024. 1

    2024

  10. [17]

    S. V. Konyagin and I. D. Shkredov. On subgraphs of random Cayley sum graphs. European J. Combin., 70:61–74, 2018. 4

    2018

  11. [19]

    Tam´ as F. M´ ori. On the waiting time till each of some given patterns occurs as a run. Probab. Theory Related Fields, 87(3):313–323, 1991. 12

    1991

  12. [20]

    Tam´ as F. M´ ori. Covering with blocks in the non-symmetric case. J. Theoret. Probab., 8(1):139–164, 1995. 12

    1995

  13. [21]

    Extractors in Paley graphs: a random model

    Rudi Mrazovi´ c. Extractors in Paley graphs: a random model. European J. Combin., 54:154–162, 2016. 4

    2016

  14. [22]

    The generalised coupon collector problem

    Peter Neal. The generalised coupon collector problem. J. Appl. Probab. , 45(3):621–629, 2008. 12

    2008

  15. [23]

    VC- dimension and pseudo-random graphs

    Thang Pham, Steven Senger, Michael Tait, and Nguyen Thu-Huyen. VC- dimension and pseudo-random graphs. Discrete Appl. Math., 365:231–246, 2025. 3

    2025

  16. [24]

    Understanding machine learning: From theory to algorithms

    Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms . Cambridge university press, 2014. 1

    2014

  17. [25]

    Convolutions of sets with bounded VC-dimension are uniformly continuous

    Olof Sisask. Convolutions of sets with bounded VC-dimension are uniformly continuous. Discrete Anal., pages Paper No. 1, 25, 2021. 1, 2

    2021

  18. [26]

    Terry and J

    C. Terry and J. Wolf. Stable arithmetic regularity in the finite field model. Bull. Lond. Math. Soc. , 51(1):70–88, 2019. 1

    2019

  19. [27]

    Higher-order generalizations of stability and arithmetic regularity

    Caroline Terry and Julia Wolf. Higher-order generalizations of stability and arithmetic regularity. preprint, arXiv:2111.01739, 2023. 1, 2

    2023

  20. [28]

    V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity , pages 11–30. Springer, Cham, 2015. Reprint of Theor. Probability Appl. 16 (1971), 264–280. 1

    1971

  21. [29]

    High-dimensional probability, volume 47 of Cambridge Se- ries in Statistical and Probabilistic Mathematics

    Roman Vershynin. High-dimensional probability, volume 47 of Cambridge Se- ries in Statistical and Probabilistic Mathematics . Cambridge University Press, Cambridge, 2018. An introduction with applications in data science, With a foreword by Sara van de Geer. 11

    2018

  22. [30]

    VC-dimensions of random function classes

    Bernard Ycart and Joel Ratsaby. VC-dimensions of random function classes. Discrete Math. Theor. Comput. Sci. , 10(1):113–128, 2008. 3 THE VC-DIMENSION OF RANDOM SUBSETS OF FINITE GROUPS 15 Email address: brad.w.rodgers@gmail.com Department of Mathematics and Statistics, Queen’...

    2008

Pith tools

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