Erdős #20 — sunflower conjecture, exponential bound for f(n,k)

Statement

Let $f(n,k)$ be minimal such that every family $\mathcal{F}$ of $n$-uniform sets with $|\mathcal{F}| \geq f(n,k)$ contains a $k$-sunflower (a $k$-sunflower, or $\Delta$-system, is a collection of $k$ sets whose pairwise intersections all coincide with one fixed set $B$). Is it true that $$f(n,k) < c_k^n$$ for some constant $c_k > 0$ (depending on $k$ but not on $n$)? This is the Erdős–Rado sunflower conjecture. Erdős specifically offered the \$1000 for the case $k=3$ alone, "which he expected 'contains the whole difficulty'" (erdosproblems.com/20, citing [Er81]).

Facts

- Prize \$1000; status open, and per erdosproblems.com/20 explicitly "cannot be resolved with a finite computation" (it is a statement for all $n$ simultaneously). - Falsifiable: no — there is no finite computation that settles it either way; it needs a genuine proof (an upper bound $f(n,k) \leq c_k^n$ for all $n$) or a genuine disproof (a family of superexponential size, again for infinitely many $n$). - Origin: Erdős and Rado, "Intersection theorems for systems of sets" (1960) [ErRa60] proved the foundational sunflower lemma; Erdős restated/emphasized the conjecture repeatedly [Er65b],[Er69],[Er71,p.104],[Er73],[Er78,p.35],[Er81],[Er90],[Er95],[Er97c],[Er97d],[Va99,3.63]. \$1000 offered specifically for $k=3$ in [Er81]. - Known results / best bounds (chain fully cross-checked against thomasbloom.org/notes/sunflowers.html, the site owner's own technical writeup, and the primary papers): - Erdős–Rado 1960 [ErRa60]: $f(n,k) \leq (k-1)^n n!$. - Spencer 1977 [Sp]: $f(n,k) \ll_k (1+o(1))^n n!$ (constant improved, same $n!$-type growth). - Kostochka 1997 [Ko97], https://www.erdosproblems.com/20: improved the $k=3$ bound to $\left(\frac{\log\log\log n}{\log\log n}\right)^n n!$ — i.e. $o(n!)$ but still $n^{(1-o(1))n}$; Erdős paid Kostochka a \$100 consolation prize for this. - Alweiss, Lovett, Wu, Zhang (ALWZ) 2019/2020 — arXiv:1908.08483, STOC 2020: dramatic breakthrough, $f(n,k) < (Ck\log n \log\log n)^n$ for an absolute constant $C>1$; first bound of shape $(\text{polylog }n)^n$, i.e. genuinely subexponential-in-the-exponent-base. Proved via a "robust sunflower" / random-restriction technique (the $R$-spread lemma). Widely covered, e.g. gilkalai.wordpress.com/2019/08/23. - Refinements (all independent, within ~2 months of ALWZ): Rao [Ra20], arXiv:1909.04774 (an entropy/coding-theoretic reproof via Shannon's noiseless coding theorem); Frankston–Kahn–Narayanan–Park [FKNP19], arXiv:1910.13433 ("Thresholds versus fractional expectation-thresholds", Annals of Math. 194 (2021), proves a conjecture of Talagrand and derives the sunflower bound as a corollary); Bell–Chueluecha–Warnke [BCW21] ("Note on sunflowers", Discrete Math. 344 (2021)) — together giving the current record: $$f(n,k) < (Ck\log n)^n$$ for an absolute constant $C>1$ — i.e. the $\log\log n$ factor was removed, leaving a single $\log n$. This is confirmed as the current best general bound by thomasbloom.org/notes/sunflowers.html and by Rao's 2026 survey (below). - Streamlined presentations: a "two chains" entropy proof (theorydish.blog/2021/05/19), and lecture notes by M. Stoeckl (mstoeckl.com/notes/research/sunflower_notes.html) presenting the same $(Ck\log n)^n$ bound with an explicit constant $C=64$. - Fukuyama 2018 (arXiv:1809.10318) gave, specifically for $k=3$, a bound $(cn^{3/4})^n$ — predates and is now superseded (for $k=3$) by the $(Ck\log n)^n$ general bound. - Fukuyama 2025/2026 (arXiv:2510.19037, "Sunflower bound with a sub-logarithmic base", submitted Oct 2025, revised Dec 2025): claims $f(n,k) \leq \left(\frac{ck^2\ln n}{\ln\ln n}\right)^n$, i.e. a further $\log\log n$-factor improvement to the base, for a general absolute constant $c$. This is the most recent claimed refinement found (as of this research pass, mid-2026); I did not find independent verification/citation of it beyond the arXiv listing itself, so treat as unverified-but-recent. - Lower bound (unimproved since Erdős–Rado, per thomasbloom.org/notes/sunflowers.html): the simple product construction $X(f) = \{(x,f(x)): x\in[k]\}$ over all functions $f:[n]\to[k-1]$ gives $f(n,k) > (k-1)^n$. The gap between $(k-1)^n$ lower bound and $(Ck\log n)^n$ upper bound is exactly the $\log n$ factor — closing it (to a constant-base bound, i.e. removing the $\log n$) is precisely the open conjecture. - Opposite regime solved: Kostochka–Rödl–Talysheva 1999 [KRT99]: for $n$ fixed and $k\to\infty$, $f(n,k) = (1+O_n(k^{-1/2^n}))\,k^n$ — this regime is "basically solved" (thomasbloom.org). - Deep technique connection: Rao's technical proposition (arXiv:1909.04774, and Rao's 2026 survey arXiv:2509.14790) shows the same "$R$-spread + random-partition" machinery that proves the sunflower bound is, essentially verbatim, the machinery Park and Pham used to prove the Kahn–Kalai (expectation-threshold) conjecture (arXiv:2203.17207, Annals of Math. 2022) — a landmark, previously-hard theorem in probabilistic combinatorics. Terence Tao independently recast Rao's proof via Shannon entropy (blog post, referenced in thomasbloom.org's notes). This is the single strongest piece of "derivation fuel": the same spread/entropy technique cracked two famous, structurally distinct-looking conjectures within a few years of each other. - A structurally different but closely related conjecture is fully resolved: the "weak"/Erdős–Szemerédi sunflower conjecture (bounding a 3-sunflower-free family of *arbitrary* subsets of $[n]$, i.e. bounding by the size of the universe rather than by uniform set-size) was proved via the polynomial method / slice rank technique that resolved the cap-set problem: Naslund & Sawin, arXiv:1606.09575 (2016), building explicitly on Croot–Lev–Pach and Ellenberg–Gijswijt's cap-set proof, show a sunflower-free family of subsets of $[n]$ has size $\leq 3(n+1)C^n$ for $C = 3/2^{2/3} \approx 1.89$ — Alon–Shpilka–Umans had earlier observed that an exponential cap-set-type bound implies this. thomasbloom.org's notes flag this explicitly as "recently a bound like $(2-c)^n$ was proved for $k=3$" for the weak version, contrasted with the still-open uniform (#20) version. This is a different problem from #20 (no fixed $n$-uniformity), but is the clearest existing proof-of-concept that a polynomial-method attack fully resolves a sibling sunflower-type question. - Related problems: no other erdosproblems.com-numbered problem was confirmed via the page's own reference list as directly linked (no explicit "See also [M]" was present on erdosproblems.com/20 at fetch time); adjacent numbers #19 and #21 were checked directly and are unrelated topics (chromatic number of edge-disjoint $K_n$-unions; intersecting-family covering). erdos/21 is a different intersecting-family extremal problem but not sunflower-specific.

Literature state

Confirmed open as of this pass (2026-07): erdosproblems.com/20 itself states OPEN, and every independent source checked (Bloom's own technical notes, Rao's brand-new 2026 JLMS survey "The story of sunflowers" arXiv:2509.14790, and the primary 2019-2021 papers) agrees the general conjecture $f(n,k) < c_k^n$ is unresolved, including the specially-prized $k=3$ case. The literature is not silently sitting on a resolution — this is one of the most actively worked "near-miss" problems in extremal combinatorics, with a fast-moving sequence of constant/log-factor improvements from 2019 (ALWZ) through late 2025/early 2026 (Fukuyama's sub-logarithmic-base claim, arXiv:2510.19037, revised Dec 2025).

Key papers, each read directly: - ALWZ 2019, arXiv:1908.08483 — the breakthrough that took the bound from $n^{(1+o(1))n}$-type to $(\text{polylog }n)^n$-type. - Rao 2020, arXiv:1909.04774 — "Coding for Sunflowers", an information-theoretic reproof, essentially sharp for robust sunflowers. - Frankston–Kahn–Narayanan–Park 2019, arXiv:1910.13433 — proves Talagrand's fractional expectation-threshold conjecture; sunflower bound is a corollary; this is the paper that also seeded the eventual full Kahn–Kalai resolution. - Naslund–Sawin 2016, arXiv:1606.09575 — resolves the *weak* Erdős–Szemerédi sunflower variant via the cap-set polynomial method; NOT the same problem as #20 but the nearest fully-solved analog. - Park–Pham 2022, arXiv:2203.17207 — proves the Kahn–Kalai conjecture using spread-family machinery genealogically identical to the sunflower-bound proofs (per Rao's survey and Tao's blog commentary). - Rao 2025, arXiv:2509.14790 ("The story of sunflowers", JLMS 2026) — a brand-new (Sept 2025 / published 2026) survey giving a short elementary proof of the current best robust-sunflower bound and explicitly reviewing the state of the conjecture; this is the most current authoritative status check available. - Fukuyama, arXiv:1809.10318 (2018) and arXiv:2510.19037 (2025, rev. Dec 2025) — a lone-author line of incremental improvements to the base of the exponent; the 2025 claim (sub-logarithmic base) is the newest development found but was not independently cross-cited in this pass, so its correctness/impact is unverified here.

No AI-system involvement found: the github.com/teorth/erdosproblems wiki "AI contributions to Erdős problems" page was checked directly and does not mention problem #20 or the sunflower conjecture, despite documenting several other 2026 GPT/AI-assisted Erdős-problem results (e.g. #1196, a primitive-sets problem, solved by GPT-5.4 Pro in 2026). This suggests #20 has not yet been a target of, or has resisted, the current wave of AI-assisted attacks — plausibly because it needs a genuinely new combinatorial idea to remove the $\log n$ factor, not a search or a routine bound-chase.

Attack surface

- Mode: derivation+formalization (this is not finite-search: it is asking for either (a) a proof that removes the residual $\log n$ factor from $f(n,k) < (Ck\log n)^n$, turning it into $f(n,k) < c_k^n$, or (b) a construction beating $(k-1)^n$ i.e. proving the conjecture false). Pure literature-resolution is also live: the recent Fukuyama arXiv:2510.19037 claim, if correct and not yet fully absorbed by the community, is a concrete "verify + push forward" literature target rather than a from-scratch derivation. - Concrete first experiment (not "solve it" — a tractable first move): (1) formally verify Fukuyama's arXiv:2510.19037 sub-logarithmic-base claim against the ALWZ/Rao/BCW machinery — reproduce the proof line-by-line, check whether the claimed $\ln n/\ln\ln n$ base genuinely improves on BCW's $\log n$, and whether it has since been cited/refuted (none found here); (2) mine Rao's spread-family framework (arXiv:1909.04774, arXiv:2509.14790) for whether the exact same technique that gave Park–Pham the *full* Kahn–Kalai resolution (not just a log-factor improvement, but an exact-up-to-constant threshold theorem) can be specialized back to sunflowers to remove the residual $\log n$ — this is the single most promising derivation angle because the two problems are already proven to share the identical core lemma (Rao's "$\mathcal{G}(W)$" construction). - Oracle: for a full proof, correctness must be checked by human/formal peer review (this is not machine-verifiable in the small); Lean formalization efforts exist for adjacent Erdős-problem infrastructure (google-deepmind/formal-conjectures has a stub file FormalConjectures/ErdosProblems/20.lean, per erdosproblems.com/20's external links) so a candidate proof could in principle be targeted at that Lean stub for mechanical verification of specific finite lemmas (e.g. the $R$-spread lemma for fixed small $k$), though the full asymptotic-in-$n$ statement is not machine-checkable outright. For a disproof, the oracle is mechanical: exhibit an explicit family of $n$-uniform sets of size $\geq \omega(c_k^n)$ for every constant $c_k$ (as $n\to\infty$) with no $k$-sunflower, and verify sunflower-freeness by brute force for finite prefixes. - Feasibility: famous and hard — this has resisted 65+ years of direct attack and is widely regarded (per Erdős's own quote "I really do not see why this question is so difficult", and per its treatment as a flagship problem in Rao's 2026 survey) as needing a genuinely new idea, not incremental refinement, to close the $\log n$ gap. However, unlike many Erdős problems, this one has an unusually *active, fast, and well-documented improvement sequence right up to late 2025* (Fukuyama), plus a proven structural bridge to the just-resolved (2022) Kahn–Kalai conjecture — meaning the surrounding technique landscape is unusually rich and current. Realistic near-term contribution: literature-resolution (verify/extend Fukuyama 2025, or explicitly work out whether Park–Pham's exact threshold-vs-expectation-threshold machinery can be pushed to remove sunflower's $\log n$), not a from-scratch full proof.

Related

- erdos/21 — adjacent intersecting-family extremal problem (same combinatorics-of-set-families neighborhood, not sunflower-specific; checked directly, distinct question). - Kahn–Kalai conjecture — threshold vs. expectation-threshold for monotone properties — Park & Pham's 2022 proof (arXiv:2203.17207) uses the identical spread-family/random-partition core lemma as the ALWZ/Rao sunflower bound; the strongest "technique already generalizes" evidence for #20. - Cap-set problem — max progression-free subset of F_3^n — Croot–Lev–Pach / Ellenberg–Gijswijt polynomial method (2016), whose direct application by Naslund–Sawin (arXiv:1606.09575) fully resolved the structurally-adjacent "weak"/Erdős–Szemerédi sunflower conjecture; nearest fully-solved sibling problem, different technique family from the spread-family line. - R-spread set families (ALWZ/Rao's central reduction device) — the $R$-spread hypothesis (ALWZ/Rao's central technical device): a family is $R$-spread if no fixed subset is contained in more than an $R^{-|X|}$ fraction of its members; reduces the sunflower search to finding disjoint sets in spread families. - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — Shannon-entropy / coding-theoretic reproof technique (Rao arXiv:1909.04774; Tao's blog recasting) giving sharp constants for the spread-family lemma. - Kahn–Kalai expectation-threshold vs. threshold-probability conjecture (Park–Pham theorem) — expectation-threshold vs. threshold probability for monotone properties; proved by Park–Pham (2022) using sunflower-genealogy spread techniques. - Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) — slice rank / Croot-Lev-Pach / Ellenberg-Gijswijt method; solved the cap-set problem and, via Naslund-Sawin, the weak sunflower conjecture, but has NOT (per literature found here) been applied to the uniform (#20) version. - Δ-system / sunflower — the core combinatorial object — synonym/formal name for sunflower in the set-theory literature; the core combinatorial object of the whole problem family.