{"id":"0b795277-7af9-4fe0-9a23-5ed5505c1a8f","arxiv_id":"2411.19734","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New upper bounds for bootstrap percolation on hypercubes: an AI-inspired construction improves the second-order term for r at least 5, and a 122-element percolating set is found for the 13-dimensional cube with threshold 4.","lead":"Using a generative AI search method (PatternBoost), the authors found new small percolating sets for bootstrap percolation on hypercubes. The patterns inspired a mathematical construction that improves the upper bound on the minimum percolating set size for all thresholds r at least 5, and a concrete 122-vertex set for the 13-cube with threshold 4.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 2.1's claimed improvement depends on existence of exact Steiner systems, which holds only for d in divisibility-restricted residue classes; the abstract overstates this as an unqualified improvement over bounds valid for all large d.","rationale":"The central contribution of the paper is Proposition 2.1's improved second-order coefficient, and the abstract's claim rests on it. The proof is a valid conditional construction: exact F1 plus a 2-fold Rödl cover F2 plus all (r−3)-sets. The most vulnerable point is not the percolation argument but the existence of the exact Steiner system. Keevash's theorem supplies such systems only under divisibility conditions; for a fixed r, these conditions exclude infinitely many d (e.g., for r=5, d ≡ 0 or 4 mod 5). Since the previous bounds (1) and (2) are not conditional in this way, the paper's unqualified 'slightly improve the best existing upper bound' overstates what is proved. This is a scope/correctness concern, not an internal contradiction. The AI 122-set is less load-bearing because the set itself is printed in full; one can verify percolation with a short script, and failure there would not affect Proposition 2.1. Therefore I uphold the reader's CONDITIONAL verdict: the theorem should be stated with its design-existence hypothesis prominently, and the abstract should say the improvement applies when such designs exist.","tokens_in":9348,"tokens_out":15268,"duration_ms":123954,"concrete_test":"For r=5, use Lucas's theorem to show that 5 divides C(d,4) iff d ≡ 1, 2, or 3 (mod 5); hence any d ≡ 0 or 4 (mod 5) violates the first divisibility condition for an exact S(4,5,d). Write a short script to enumerate all d ≤ 10^4 satisfying the full divisibility conditions for S(4,5,d) and compute the proportion. If the proportion is strictly less than 1, the claimed improvement is confined to a proper subsequence of dimensions, confirming that the abstract must be revised to state the design-existence condition explicitly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 2.1 is correct as a conditional statement, but its hypothesis—existence of an exact Steiner system S(r-1,r,d)—is satisfied only for d in certain residue classes modulo a constant depending on r; Keevash's theorem requires the standard divisibility conditions. For fixed r, infinitely many d fail these conditions. For example, when r=5, Lucas's theorem gives 5 ∤ C(d,4) whenever d ≡ 0 or 4 (mod 5), so no exact S(4,5,d) exists for those d. The prior upper bounds (1) and (2) hold for all sufficiently large d, so for non-admissible d the new construction yields no improvement and the best bound remains (2). The abstract's claim to 'slightly improve the best existing upper bound' is therefore not established for all large d and is misleading without qualification. The 122-vertex example is less load-bearing because the full list is printed and percolation is checkable by direct simulation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9550,"tokens_out":11816,"duration_ms":88443,"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":[{"comment":"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.","section":"Abstract and Section 2.1, Proposition 2.1"},{"comment":"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.","section":"Section 2.2, reward expression"},{"comment":"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.","section":"Section 3, Figure 1"}],"minor_comments":[{"comment":"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).","section":"Section 2.2"},{"comment":"The citation 'Rödl's result []' has an empty reference marker; it should be [9].","section":"Proof of Proposition 2.1"},{"comment":"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.","section":"Proposition 2.1"},{"comment":"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.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The paper's headline claim should be tempered in the abstract: the mathematical core is a correct but conditional statement, and the ML component is an application of the authors' own PatternBoost pipeline. With the scope qualified and a verifier supplied, this is a reasonable note for a journal that welcomes short construction papers; I do not see any circularity or fitted-parameter concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: the paper's real content is Proposition 2.1, a new upper bound on the second-order term of m(Q_d,r), but only for d where an exact Steiner system S(r-1,r,d) exists. The abstract omits that condition, which makes the headline claim broader than what is proven. Fix that and you have a solid short note.\n\nWhat's new: the construction combines an exact Steiner system for the leading term with a Röd-type double covering of (r-2)-sets and all (r-3)-sets. The counting checks out and the percolation argument is sound. For r >= 5 it beats both the Morrison-Noel and the earlier exact-Steiner bound whenever the design exists. The 122-vertex percolating set in Q_13 with r=4 is a genuine finite-case improvement, and the full list is printed, so a reader can verify it by running the process directly.\n\nSoft spots: the Steiner-system caveat is not cosmetic. Keevash's theorem gives such designs only under divisibility conditions; for fixed r, infinitely many d fail them. So the improvement over (1) and (2) is along a subsequence, not for all large d. The abstract should say that. The AI pipeline is described at the level of a sketch—no code, no hyperparameters, no verification script. That's forgivable for a note, but the authors should at least provide a minimal checker for the claimed 122-set. There's also no citation of any prior AI-based constructions in combinatorics beyond PatternBoost itself, which is fine; self-citation is not an issue here since the 122-set is new.\n\nThe paper is honest on its own terms: the proposition is explicitly conditional, and the AI claim is presented as an empirical discovery, not a fitted prediction. No circularity.\n\nBottom line: it's a small but correct step in a narrow area. Read it if you work on bootstrap percolation or on AI-assisted search in extremal combinatorics. It deserves a serious referee; a light revision should add the d-qualification to the abstract and ideally release verification code.","headline":"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.","tokens_in":10088,"tokens_out":3976,"would_cite":false,"duration_ms":33309,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B05","05C65","60K35"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["bootstrap percolation","hypercube","percolating sets","Steiner systems","covering designs","generative AI","local search","extremal combinatorics"],"falsifier":"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.","tokens_in":9151,"feed_emoji":"🧊","tokens_out":12819,"duration_ms":96610,"temperature":0.7,"pith_summary":"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.","feed_headline":"New construction shrinks hypercube percolation gap","feed_subtitle":"A conditional upper bound improves the second-order term, while an AI search finds a 122-vertex percolating set in Q_13.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces r-neighbor bootstrap percolation, the process whose percolating sets the paper minimizes.","marker":"[4]"},{"why":"Supplies the previous two-family covering construction and the upper bound (1) that Proposition 2.1 improves.","marker":"[2]"},{"why":"Gives the recursive upper bound (2) and the lower bound (3) against which the new bound is measured.","marker":"[8]"},{"why":"Provides the existence of exact Steiner systems used as the top layer of the construction.","marker":"[7]"},{"why":"Supplies the near-optimal covering theorem used to build the middle layer F2 with small second-order size.","marker":"[9]"},{"why":"Describes the generative-AI pattern-recognition pipeline adapted to find the 122-vertex set.","marker":"[5]"}],"fun_headline_variants":["AI finds 122-vertex percolating set in Q_13","Improved upper bound for hypercube percolation","PatternBoost tightens percolation bound on hypercubes","Conditional bound improves hypercube percolation gap","Hypercube percolation gap narrowed by AI"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["AI finds 122-vertex percolating set in Q_13","Improved upper bound for hypercube percolation","PatternBoost tightens percolation bound on hypercubes","Conditional bound improves hypercube percolation gap","Hypercube percolation gap narrowed by AI"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000519,"raw_usage":{"total_tokens":2449,"prompt_tokens":812,"completion_tokens":1637,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":428,"completion_tokens_details":{"reasoning_tokens":1557}},"tokens_in":428,"tokens_out":1637,"duration_ms":8885,"temperature":1.0,"reasoning_tokens":1557,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:53:09.497654+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Chalupa, P","cited_arxiv_id":null,"evidence_quote":"Introduces r-neighbor bootstrap percolation, the process whose percolating sets the paper minimizes."},{"cited_title":"Bootstrap percolation in high dimen- sions","cited_arxiv_id":null,"evidence_quote":"Supplies the previous two-family covering construction and the upper bound (1) that Proposition 2.1 improves."},{"cited_title":"Extremal bounds for bootstrap percolation in the hypercube","cited_arxiv_id":null,"evidence_quote":"Gives the recursive upper bound (2) and the lower bound (3) against which the new bound is measured."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the near-optimal covering theorem used to build the middle layer F2 with small second-order size."}],"review_version":1}