{"id":"53e6c5a5-b790-40b5-8905-0559153b3d85","arxiv_id":"2506.14219","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A random Bernoulli subset of any finite group of order N has VC-dimension (1+o(1)) log_r N with high probability, where r = 1/min(p,1-p).","lead":"Random subsets of large finite groups have a shattering size essentially equal to log_r N, with r fixed by the sampling bias. This settles a question about random Cayley graphs and supports conjectures about number-theoretic graphs such as Paley graphs.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's verdict of ACCEPT is justified. I independently checked the parameter bookkeeping and probabilistic estimates in Sections 3 and 4. The only place a concern could arise is the external Lemma 6, exactly as the reader identified; however, it is a standard published result and is correctly applied. The minor inequality typo in Step 3 is not load-bearing because the intended bound holds with a constant factor. Since I found no flaw that would change the verdict, the appropriate output is a non-finding with no change to the reader's decision. I mark partial agreement because the reader's weakest assumption points to Lemma 6, and I agree that is the only external dependency, but I do not regard it as a genuine threat to correctness.","tokens_in":10234,"tokens_out":21200,"duration_ms":207747,"concrete_test":"Verify Lemma 6 against the original source [5, Corollary 3.2] to confirm it is stated for arbitrary finite groups and arbitrary subsets S (not only abelian or symmetric cases), and redo the Step 3 expectation calculation with the corrected identity p^{k-10} = p^{-10} p^k to confirm the O(k^{-2}) bound; if both hold, the upper bound stands as written after the typo fix.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After a careful step-by-step check, the central argument of Theorem 1 is sound. The lower bound (Section 3) correctly combines Lemma 5's disjoint-translate packing with a product estimate to show that any fixed k-set U is shattered with probability 1 - O(1/N^eta). The upper bound (Section 4) correctly applies Lemma 6 to cover G by m ≪ k^3 translates of S^{-1}, decomposes T_A into m families with disjoint translates, and uses Chernoff's inequality to show the probability of shattering any U of size k is e^{-C k^6}; the final union bound over C(N,k) choices is absorbed because k^6 dominates k^2 log r. The only externally sourced ingredient is Lemma 6 (Bollobás–Janson–Riordan), which is standard and is applied exactly as intended. I found one minor typo in Step 3: the line 'E X_v ≤ k^{10} p^k' should read 'E X_v ≤ k^{10} p^{k-10} = p^{-10} k^{10} p^k'; since p is fixed, the constant p^{-10} is absorbed and the O(k^{-2}) mean bound still holds. This is cosmetic and does not affect the proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10427,"tokens_out":16524,"duration_ms":168276,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"§3, Step 1"},{"comment":"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.","section":"§4, Step 3"},{"comment":"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)'.","section":"§1.3"},{"comment":"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'.","section":"§1.3"},{"comment":"There are minor typographical errors, e.g. 'susbsets' for 'subsets' and 'The VC-dimension of the F' for 'The VC-dimension of F'.","section":"§1.1"},{"comment":"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.","section":"§3"}],"recommendation":"minor_revision","confidential_remarks":"The central proof checks out; my only concerns are local typos and one reversed inequality exponent in Section 3 that is immediately fixable and does not affect the argument. The reliance on Lemma 6 from [5] is acceptable for the field, but if the editors prefer full self-containedness, the authors could be asked to include a brief proof of that covering lemma. I do not see this as an obstacle to acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result is genuinely new: for Bernoulli(p) random subsets A of any finite group G, the VC-dimension of the translate family T_A (equivalently, the neighborhood family of the random Cayley graph) is (1+o(1)) log_r N with r = 1/min(p,1-p). This is the first such law of large numbers that is uniform over all finite groups, and it answers a question from McDonald–Sahay–Wyman. The proof is clean and the bookkeeping checks out. The lower bound uses a simple greedy packing plus a union bound; the upper bound is the clever part, coupling the Bollobás–Janson–Riordan covering lemma with a pigeonhole argument and Chernoff concentration to show that any fixed k-set is shattered with probability e^{-C k^6}. The conjectural discussion in Section 1.3 is honest: the authors explicitly distinguish what follows from their theorem and what is a plausible analogue, and they flag the disagreement with Conjecture 1.5 of [18] and propose an alternative. That is a useful contribution, not an overreach. I also appreciate the remark that the p → 0 regime is not addressed; they say so plainly. The only issue I found is a minor typo in Step 3 of Section 4: the displayed E X_v should be p^{k-10}, not p^k, and the subsequent bound should absorb p^{-10}. This is cosmetic and does not affect the argument. The citation to [5] for the covering lemma is appropriate, and the use of that lemma is exactly as intended. Overall, this is a solid, well-written paper that delivers what it promises. It is not groundbreaking—the result is what one would expect from the coupon-collector analogy—but it is the right theorem, proved rigorously, and it sharpens the conjectural landscape for Paley and power-residue graphs. Anyone working on VC-dimension or random Cayley graphs will want to know this. It deserves a serious referee and, with the typo corrected, publication.","headline":"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.","tokens_in":10977,"tokens_out":1951,"would_cite":true,"duration_ms":21068,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D40","05C80","05C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["VC-dimension","random subsets","finite groups","Cayley graphs","covering lemmas","Bernoulli sampling","Paley graphs","law of large numbers"],"falsifier":"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.","tokens_in":10016,"feed_emoji":"🎲","tokens_out":16537,"duration_ms":128790,"temperature":0.7,"pith_summary":"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.","feed_headline":"Random subsets of finite groups have VC-dimension log_r N","feed_subtitle":"Answers a question about Paley-graph VC-dimension and predicts a similar law for power-residue sets.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the covering lemma (Lemma 6) used in the upper-bound proof, ensuring any subset of size ell can be covered by at most (N/ell)(log ell + 1) translates; without it the covering step breaks.","marker":"[5]"},{"why":"The motivating paper that raised the question of the VC-dimension of random Cayley graphs and Paley graphs; it supplies the conjectures and partial progress that Theorem 2 answers.","marker":"[18]"},{"why":"Defines the VC-dimension of a graph and provides the random graph analogue whose behaviour the result mirrors.","marker":"[4]"},{"why":"Provides the Chernoff bound used to control the probability that a fixed subfamily of translates cuts out many subsets in the upper-bound step.","marker":"[29]"}],"fun_headline_variants":["Random subsets of finite groups: VC-dim = log_r N","Random Cayley graphs have VC-dimension log_r N","Law of large numbers for VC-dimension in groups","Answers McDonald-Sahay-Wyman VC-dim question","Random group subsets: VC-dim ~ log_r N"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Random subsets of finite groups: VC-dim = log_r N","Random Cayley graphs have VC-dimension log_r N","Law of large numbers for VC-dimension in groups","Answers McDonald-Sahay-Wyman VC-dim question","Random group subsets: VC-dim ~ log_r N"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001033,"raw_usage":{"total_tokens":4291,"prompt_tokens":826,"completion_tokens":3465,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":442,"completion_tokens_details":{"reasoning_tokens":3386}},"tokens_in":442,"tokens_out":3465,"duration_ms":27822,"temperature":1.0,"reasoning_tokens":3386,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:18:42.244461+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"On covering by translates of a set","cited_arxiv_id":null,"evidence_quote":"Supplies the covering lemma (Lemma 6) used in the upper-bound proof, ensuring any subset of size ell can be covered by at most (N/ell)(log ell + 1) translates; without it the covering step breaks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The motivating paper that raised the question of the VC-dimension of random Cayley graphs and Paley graphs; it supplies the conjectures and partial progress that Theorem 2 answers."},{"cited_title":"The Vapnik- Chervonenkis dimension of a random graph","cited_arxiv_id":null,"evidence_quote":"Defines the VC-dimension of a graph and provides the random graph analogue whose behaviour the result mirrors."},{"cited_title":"High-dimensional probability, volume 47 of Cambridge Se- ries in Statistical and Probabilistic Mathematics","cited_arxiv_id":null,"evidence_quote":"Provides the Chernoff bound used to control the probability that a fixed subfamily of translates cuts out many subsets in the upper-bound step."}],"review_version":1}