Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

A Note on Small Percolating Sets on Hypercubes via Generative AI

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

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

Pith's one-line read This paper proves a conditional improvement to the second-order upper bound for the minimum percolating set on the hypercube, and reports a generative-AI-found 122-vertex set that percolates in Q_13 with r=4.

desk verdict A correct conditional improvement in the second-order term of the hypercube percolation bound, with an abstract that overstates its range of validity; the 122-set is a real but under-verified artifact. read the letter →

arxiv 2411.19734 v1 pith:I56EEGC3 submitted 2024-11-29 cs.LG cs.DM

Gergely Bérczi , Adam Zsolt Wagner This is my paper · ORCID
classification cs.LGcs.DM MSC 05B0505C6560K35
keywords bootstrappercolationhypercubepercolatingsetsSteinersystemscoveringdesignsgenerativeAIlocalsearchextremalcombinatorics
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 studies the minimum size m(Q_d,r) of an initial infected set that percolates the d-dimensional hypercube under r-neighbor bootstrap percolation. It proves that when an exact Steiner system S(r-1,r,d) exists, one can build percolating sets of size at most (1/r) binom(d,r-1) + (2/(r-1)+o(1)) binom(d,r-2), improving the second-order coefficient over the previous best upper bounds for every r >= 5. This matters because the best known lower bound has the same leading term, so the construction cuts the remaining gap to 2 $d^{{r-2}}$/r! + $\Omega$($d^{{r-3}}$). The paper also applies a generative-AI search pipeline to find a concrete 122-vertex percolating set in the 13-dimensional hypercube for r=4, smaller than the 124 found by local search alone.

What carries the argument

The argument is carried by a three-layer covering construction F1 ∪ F2 ∪ F3. The top layer F1 is an exact Steiner system S(r-1,r,d), a family of r-subsets hitting every (r-1)-subset exactly once; the middle layer F2 is a family of (r-1)-subsets covering every (r-2)-subset at least twice, with near-optimal size; the bottom layer F3 is all (r-3)-subsets. In the bootstrap process each (r-2)-set sees r-2 infected (r-3)-neighbors plus at least two infected (r-1)-neighbors, so it becomes infected; each (r-1)-set then sees r-1 infected (r-2)-neighbors plus one infected r-neighbor from F1; once all (r-1)-sets are infected, percolation follows. For the machine-learning result, the machinery is a pipeline of random local search, filtering of small percolating sets, training a small transformer-based generative model on them, and using local search again on the model's outputs, which produced the 122-vertex example.

What would settle it

A reader can settle the mathematical claim by taking r=5 and a dimension d with an exact S(4,5,d), building the three-layer set, and simulating the bootstrap process to see whether Q_d fully percolates; for the AI claim, the same reader can run r=4 bootstrap simulation from the 122 listed vertices in Q_13 and check whether all 8192 vertices are infected.

Watch

Extended reading notes

Core claim

The central claim is Proposition 2.1: if there is a family of r-subsets of [d] covering every (r-1)-subset exactly once, then m(Q_d,r) <= (1/r) binom(d,r-1) + (2/(r-1)+o(1)) binom(d,r-2), which expands to $d^{{r-1}}$/r! + $d^{{r-2}}$(6-r+4/(r-1))/(2r(r-2)!) + $\Omega$($d^{{r-3}}$). The proof uses the exact Steiner system as the top layer, a near-optimal family of (r-1)-sets covering every (r-2)-set at least twice as the middle layer, and all (r-3)-subsets as the bottom layer; each layer becomes infected one step after the one below it, and then the whole hypercube percolates. Separately, the paper claims that the 122 vertices listed in Figure 1 form a percolating set in Q_13 for r=4, that percolation completes in 68 steps, and that over 1,000 similar 122-vertex sets were found.

Load-bearing premise

The sharper upper bound only applies to dimensions where an exact Steiner system exists, and the 122-vertex claim rests on the paper's assertion that the listed set actually percolates, since no verifier code is provided.

Editorial extensions

If this is right

  • For every fixed r >= 5 and every dimension d admitting an exact Steiner system S(r-1,r,d), the new upper bound has second-order coefficient (6-r+4/(r-1))/(2r(r-2)!) and leaves a gap of only 2 d^{r-2}/r! + Omega(d^{r-3}) to the known lower bound.
  • The layered construction is a template: replacing exactness of the top layer by an approximate design changes the main term, while the middle and bottom layers determine the second-order term, and further layers only affect lower-order terms.
  • The 122-vertex set in Q_13 with r=4 is claimed to percolate in 68 steps and improves the 124-vertex best found by local search alone at the same parameters.
  • The paper reports more than 1,000 distinct 122-vertex percolating sets, all independent, with percolation times between 50 and 100 steps, indicating the found example is not a one-off fluke.

Reading between the lines

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

  • If exact Steiner systems are available for all sufficiently large dimensions satisfying the arithmetic conditions required by the existence theorem, then the improved second-order coefficient becomes unconditional on that whole congruence class; extending it to every large d would require a family of r-subsets covering every (r-1)-subset with error only o(d^{r-2}).
  • The repeated finding that the smallest sets are independent suggests that extremal percolating sets may always be independent in this regime, a property that could be built into future search heuristics.
  • The outcome at d=13, r=4 suggests running the same generative pipeline at nearby parameters to test whether further improvements below the Steiner-based bound appear, or whether 122 is the true minimum for that instance.
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 / 4 minor

Summary. The paper studies r-neighbor bootstrap percolation on the d-dimensional hypercube Q_d and the minimum size m(Q_d, r) of a percolating set. The main theoretical result (Proposition 2.1) is an upper bound m(Q_d, r) <= (1/r) binom(d, r-1) + (2/(r-1)+o(1)) binom(d, r-2) under the assumption that an exact Steiner system S(r-1, r, d) exists; for such d and r >= 5 this improves the d^{r-2} coefficient of the earlier upper bounds (1) and (2). The paper also reports an AI-assisted search (PatternBoost) that found a 122-vertex percolating set in Q_13 for r = 4, improving the authors' own local-search bound of 124 for that case.

Significance. If Proposition 2.1 is read with its hypothesis made explicit, it is a genuine though modest improvement: for the admissible d it lowers the second-order term and narrows the gap to the Morrison-Noel lower bound to 2 d^{r-2}/r! + Omega(d^{r-3}). The proof is short, transparent, and uses standard tools (Rödl's theorem and exact designs) with no fitted parameters. The 122-set in Figure 1 is a concrete, falsifiable artifact. The main weaknesses are that the advertised scope is wider than the theorem's hypothesis and that the computational claim is not accompanied by a verifier or code.

major comments (3)
  1. [Abstract and Section 2.1, Proposition 2.1] The claim that the construction improves the best existing upper bound for all r >= 5 is not established. The hypothesis of Proposition 2.1 is the existence of an exact Steiner system S(r-1, r, d), which Keevash's theorem provides only for d satisfying certain divisibility conditions. For fixed r, infinitely many d fail those conditions; for example, for r = 5, Lucas's theorem gives 5 does not divide binom(d, 4) when d is congruent to 0 or 4 modulo 5, so no exact S(4,5,d) exists. The prior bounds (1) and (2) hold for all sufficiently large d, so for non-admissible d the construction yields no second-order improvement. The abstract and the opening paragraph of Section 2.1 should qualify the result as holding for d in the admissible residue classes, or state it explicitly as an improvement along a subsequence.
  2. [Section 2.2, reward expression] The displayed formula Reward = -#active vertices + 2 x (active count - |Q_d|) simplifies to active count - 2|Q_d|, which contains no penalty for the number of chosen seed vertices, contradicting the surrounding text that says the reward subtracts a count of vertices to encourage fewer vertices. This makes the local-search step ambiguous and hinders reproducibility. Please correct the formula or the description; likely the first term should count the number of selected vertices in the candidate set rather than the number of vertices that eventually percolate.
  3. [Section 3, Figure 1] The 122-vertex percolating set is printed in full, which is good, but no code, verification script, or certificate is provided, and the text only states that percolation took 68 steps. Since this computational finding is a central advertised output of the PatternBoost pipeline, the paper should include a verifier (or a link to code) so that the percolation claim can be checked independently and machine-verified.
minor comments (4)
  1. [Section 2.2] The phrase 'improve lower bounds for the minimum size of percolating sets' should be 'improve upper bounds', since finding smaller percolating sets gives better upper bounds on m(Q_d, r).
  2. [Proof of Proposition 2.1] The citation 'Rödl's result []' has an empty reference marker; it should be [9].
  3. [Proposition 2.1] The statement should specify the asymptotic regime more precisely (r fixed, d tending to infinity) and state any lower bound on d needed for the final step that all (r-1)-sets percolate; the assertion requires d sufficiently large relative to r.
  4. [Figure 1] The vertex list in Figure 1 is unwieldy in print; a supplementary file or a machine-readable link would make the artifact easier to use and verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper-bound construction is a hand proof using external theorems (Keevash designs, Rödl coverings), and the AI-discovered 122-vertex set is fully listed and independently checkable.

full rationale

The derivation chain in Proposition 2.1 is self-contained conditional mathematics. The input is an exact Steiner system S(r-1, r, d), whose existence is imported from Keevash's external theorem, plus a Rödl near-perfect covering for (r-2)-subsets; the percolation argument is a direct two-stage counting proof. No parameter is fitted to the target bound, and the claimed bound is not defined in terms of the construction's size. The main caveat—that the improved second-order coefficient is only established for d where the exact design exists—is a scope/correctness concern, not circularity. The machine-learning portion reports a specific 122-vertex set in Figure 1 that is explicitly listed; percolation of that set is a finite, externally checkable computation, so it is an empirical discovery rather than a fitted input. Reference [5] (PatternBoost) is a coauthor self-citation, but it is used only as a methodological pointer, and the paper's central mathematical claim does not rest on it. Hence no circular step.

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

The central theorem rests on two external existence results (Keevash and Rodl) and a standard percolation argument. The AI pipeline introduces no free parameters in the mathematical claim; its hyperparameters are search heuristics, not part of the theorem.

assumptions (3)
  • domain assumption Existence of an exact Steiner system S(r-1, r, d), a collection of r-subsets covering every (r-1)-subset exactly once, for the given d.
    Invoked in Proposition 2.1; guaranteed by Keevash's theorem only for d satisfying divisibility conditions, so the bound is conditional on such d.
  • standard math Rodl's covering theorem: there is a family of (r-1)-subsets covering every (r-2)-subset at least twice with size (2/(r-1)+o(1)) binom(d, r-2).
    Used to choose F2 in Proposition 2.1; it is an external theorem, not proved in the paper.
  • standard math In the r-neighbor bootstrap process, once all (r-1)-subsets of [d] are infected, the whole hypercube becomes infected.
    Used in the final step of the proof of Proposition 2.1; follows from the standard argument that the collection of all (r-1)-sets percolates.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Note on Small Percolating Sets on Hypercubes via Generative AI." pith.science (2026). https://pith.science/paper/I56EEGC3

@misc{pith2026241119734,
  author       = {Pith},
  title        = {Pith review of: A Note on Small Percolating Sets on Hypercubes via Generative AI},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I56EEGC3}},
  note         = {Machine review of arXiv:2411.19734}
}
read the original abstract

We apply a generative AI pattern-recognition technique called PatternBoost to study bootstrap percolation on hypercubes. With this, we slightly improve the best existing upper bound for the size of percolating subsets of the hypercube.

Figures

Figures reproduced from arXiv: 2411.19734 by the authors.

Figure 1
Figure 1. A percolating set of size 122 for d = 13, r = 4. Percolation process took 68 steps Here are some observations on the more than 1,000 percolating sets of size 122 that were identified: 1. Percolation Steps: The percolation process from the initial set to full percolation takes between 50 and 100 steps for each set. There is no clear reason for this range, nor is it evident whether finding sets that percolate faster i… view at source ↗
Figure 2
Figure 2. Percolation speed shows an exponential growth [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Percolation process of a 122 element subset in 68 steps. Percolated nodes are colored [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?

    cs.LG 2025-01 conditional novelty 6.0 of 10

    A neural network relaxation of geometric coloring constraints produced new plane colorings, including an almost 5-coloring covering all but 3.74% of the plane, improving known bounds for Hadwiger-Nelson variants.

  2. Formal Mathematical Reasoning: A New Frontier in AI

    cs.AI 2024-12 conditional novelty 5.0 of 10

    Machine-checkable formal proof should become the backbone of AI mathematics, and a five-task, five-level capability roadmap can measure progress toward that goal.

Reference graph

Works this paper leans on

9 extracted references · 6 canonical work pages · cited by 2 Pith papers

  1. [1]

    Balogh and B

    J. Balogh and B. Bollob´ as. Bootstrap percolation on the hypercube. Probability Theory and Related Fields, 134(4):624–648, 2006

    work page 2006

  2. [2]

    Bootstrap percolation in high dimen- sions

    J´ ozsef Balogh, B´ ela Bollob´ as, and Robert Morris. Bootstrap percolation in high dimen- sions. Combinatorics, Probability and Computing, 19(5-6):643–692, 2010

    work page 2010

  3. [3]

    Linear algebra and bootstrap percolation

    J´ ozsef Balogh, B´ ela Bollob´ as, Robert Morris, and Oliver Riordan. Linear algebra and bootstrap percolation. Journal of Combinatorial Theory, Series A, 119(6):1328–1335, 2012

    2012

  4. [4]

    Chalupa, P

    J. Chalupa, P. L. Leath, and G. R. Reich. Bootstrap percolation on a Bethe lattice. Journal of Physics C: Solid State Physics, 12(1):L31–L35, 1979

    work page 1979

  5. [5]

    Patternboost: Constructions in mathematics with a little help from AI

    Fran¸ cois Charton, Jordan S Ellenberg, Adam Zsolt Wagner, and Geordie Williamson. Patternboost: Constructions in mathematics with a little help from AI. arXiv preprint arXiv:2411.00566, 2024

    arXiv 2024

  6. [6]

    On a limit theorem in combinatorial analysis

    Paul Erdos and Haim Hanani. On a limit theorem in combinatorial analysis. Publ. Math. Debrecen, 10(10-13):2–2, 1963

    work page 1963

  7. [7]

    P. Keevash. The existence of designs. arXiv preprint arXiv:1401.3665v1, January 2014. https://arxiv.org/abs/1401.3665v1

    arXiv 2014

  8. [8]

    Extremal bounds for bootstrap percolation in the hypercube

    Natasha Morrison and Jonathan A Noel. Extremal bounds for bootstrap percolation in the hypercube. Journal of Combinatorial Theory, Series A, 156:61–84, 2018

    work page 2018

Show all 9 references
  1. [9]

    V. R¨ odl. On a packing and covering problem.European Journal of Combinatorics, 6(1):69– 78, 1985. 8

    1985

Pith tools

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