Reused writeup on Math-5947 (gpt pro 5.2)

Erdős Problem 857 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/857

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/857.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/857.tex.

FORMAL RESTATEMENT.

Fix integers $n\ge 1$ and $k\ge 2$. Write $[n]=\{1,2,\dots,n\}$. A $k$-sunflower (also called a $k$-$\Delta$-system) is a collection of sets $S_1,\dots,S_k\subseteq[n]$ such that there exists a set $C\subseteq[n]$ with \[ S_i\cap S_j = C\quad\text{for all }1\le i<j\le k. \] (Equivalently: all pairwise intersections are equal as sets.)

Let $m(n,k)$ be the least integer $m$ with the property that every family $\mathcal F$ of $m$ distinct subsets of $[n]$ contains a $k$-sunflower.

Ambiguity note. The problem statement says "any collection of sets $A_1,\dots,A_m$" without explicitly forbidding repetitions. If repetitions are allowed then $m(n,k)$ changes by at most a factor of $k$ (because $k$ equal copies already form a $k$-sunflower). Since the asymptotic question in $n$ is about exponential growth, we formalise the standard distinct-family version above.

Edge cases: $k=2$ (every two sets form a $2$-sunflower) and $n$ small.

QUICK LITERATURE/CONTEXT CHECK.

The problem statement itself records that for $k=3$ there is an exponential upper bound $m(n,3) \le (3/2^{2/3})^{(1+o(1))n}$ due to Naslund--Sawin, and mentions relations to the cap set problem. Per the integrity rule, in what follows we do not use any unstated literature results.

ATTACK PLAN.

Two basic directions that are fully provable from scratch:

$1$ Lower bounds: build explicit sunflower-free families $\mathcal F\subseteq 2^{[n]}$.

$2$ Upper bounds: prove the classical Erdős--Rado sunflower lemma for $r$-uniform families, then apply it to each layer $\binom{[n]}{r}$ and sum over $r$.

We also run a tiny brute-force search for small $n,k$ to sanity-check the definitions.

WORK.

Fast reality check (small $n$ by brute force).

For distinct families $\mathcal F\subseteq 2^{[n]}$, define $F(n,k)$ to be the maximum size of a $k$-sunflower-free family; then $m(n,k)=F(n,k)+1$.

A brute-force search over all families for $n\le 4$ gives: \[ \begin{array}{c|ccc} n & m(n,2) & m(n,3) & m(n,4) \\\hline 1 & 2 & - & - \\ 2 & 2 & 4 & 5 \\ 3 & 2 & 6 & 8 \\ 4 & 2 & 9 & 13 \end{array} \] (where "-" means $k>2^n$ so the distinct-family version cannot force a $k$-sunflower).

Lemma 857.1 (Chains are sunflower-free for $k\ge 3$).

Lemma. Let $k\ge 3$ and let $\mathcal C$ be a family of distinct subsets of $[n]$ that is totally ordered by inclusion (i.e. a chain). Then $\mathcal C$ contains no $k$-sunflower.

Proof. Assume for contradiction that distinct sets $S_1,\dots,S_k\in\mathcal C$ form a $k$-sunflower. Since $\mathcal C$ is totally ordered by inclusion, after reindexing we may assume \[ S_1 \subset S_2 \subset \cdots \subset S_k. \] Because $S_1\subset S_2$, we have $S_1\cap S_2 = S_1$. Similarly, $S_1\cap S_3=S_1$. But also $S_2\cap S_3 = S_2$ because $S_2\subset S_3$. Since the sets are distinct, $S_2\ne S_1$, so $S_2\cap S_3 \ne S_1\cap S_2$. Thus the pairwise intersections are not all equal, contradicting that $S_1,\dots,S_k$ is a sunflower. $\square$

Corollary. For every $n\ge 1$ and $k\ge 3$, we have $m(n,k)\ge (n+1)+1 = n+2$, because the chain $\varnothing \subset \{1\} \subset \{1,2\} \subset \cdots \subset [n]$ has size $n+1$ and is $k$-sunflower-free by the lemma. $\square$

Lemma 857.2 (Erdős--Rado sunflower lemma, $r$-uniform case).

Lemma (Sunflower lemma). Fix integers $r\ge 1$ and $k\ge 2$. Let $\mathcal F$ be a family of distinct $r$-element sets (i.e. $r$-uniform). If \[ |\mathcal F| > (k-1)^r\, r! , \] then $\mathcal F$ contains a $k$-sunflower.

Proof. We prove by induction on $r$.

Base case $r=1$. Then every set in $\mathcal F$ is a singleton. If $|\mathcal F|\ge k$, pick any $k$ distinct singletons. Any two distinct singletons have intersection $\varnothing$, so all pairwise intersections are equal to $\varnothing$; hence they form a $k$-sunflower with core $\varnothing$. Since $|\mathcal F|>(k-1)^1\cdot 1!=k-1$ implies $|\mathcal F|\ge k$, the base case holds.

Induction step. Assume $r\ge 2$ and the statement holds for $(r-1)$-uniform families. Assume for contradiction that $\mathcal F$ is $r$-uniform, $k$-sunflower-free, and $|\mathcal F|>(k-1)^r r!$.

Choose a maximal subfamily $\{S_1,\dots,S_t\}\subseteq\mathcal F$ of pairwise disjoint sets (maximal by inclusion). Then $t\le k-1$, because if $t\ge k$ then $S_1,\dots,S_k$ are pairwise disjoint, so their pairwise intersections are all $\varnothing$, hence they form a $k$-sunflower (core $\varnothing$), contradicting sunflower-freeness.

For each $i\in\{1,\dots,t\}$ define \[ \mathcal F_i := \{T\in\mathcal F : T\cap S_i\ne\varnothing\}. \] Because the disjoint family $\{S_i\}$ is maximal, every $T\in\mathcal F$ intersects at least one $S_i$, hence \[ \mathcal F \subseteq \bigcup_{i=1}^t \mathcal F_i, \] and therefore \[ |\mathcal F| \le \sum_{i=1}^t |\mathcal F_i|. \] Fix $i$. For each $x\in S_i$, let \[ \mathcal F(x) := \{T\in\mathcal F : x\in T\}. \] Every $T\in\mathcal F_i$ contains at least one element of $S_i$, so $\mathcal F_i \subseteq \bigcup_{x\in S_i} \mathcal F(x)$. Hence by the union bound, \[ |\mathcal F_i| \le \sum_{x\in S_i} |\mathcal F(x)|. \] Now fix an element $x$. Consider the $(r-1)$-uniform family \[ \mathcal F_x := \{T\setminus\{x\} : T\in\mathcal F,\ x\in T\}. \] This has size $|\mathcal F_x|=|\mathcal F(x)|$. If $|\mathcal F(x)|>(k-1)^{r-1}(r-1)!$, then by the induction hypothesis $\mathcal F_x$ contains a $k$-sunflower $U_1,\dots,U_k$. Then $U_1\cup\{x\},\dots,U_k\cup\{x\}$ are distinct sets in $\mathcal F$ whose pairwise intersections are \[(U_i\cup\{x\})\cap (U_j\cup\{x\}) = (U_i\cap U_j)\cup\{x\}, \] which is independent of $i\ne j$ because $U_i\cap U_j$ is independent of $i\ne j$. Thus $\mathcal F$ would contain a $k$-sunflower, contradicting sunflower-freeness. Therefore for every element $x$ we must have \[ |\mathcal F(x)| \le (k-1)^{r-1}(r-1)!. \] Returning to the bound on $|\mathcal F_i|$, we obtain \[ |\mathcal F_i| \le \sum_{x\in S_i} (k-1)^{r-1}(r-1)! = |S_i|\,(k-1)^{r-1}(r-1)!. \] Since $|S_i|=r$, this gives \[ |\mathcal F_i| \le r\,(k-1)^{r-1}(r-1)! = (k-1)^{r-1}\, r!. \] Finally, since $t\le k-1$, \[ |\mathcal F| \le \sum_{i=1}^t |\mathcal F_i| \le t\,(k-1)^{r-1} r! \le (k-1)\,(k-1)^{r-1} r! = (k-1)^r r!. \] This contradicts the assumption $|\mathcal F|>(k-1)^r r!$. Hence such $\mathcal F$ cannot exist; the sunflower lemma follows. $\square$

Corollary 857.3 (A concrete upper bound for $m(n,k)$).

Corollary. For all $n\ge 1$ and $k\ge 2$, \[ m(n,k) \le 1 + \sum_{r=0}^n (k-1)^r r!. \]

Proof. Let $\mathcal F\subseteq 2^{[n]}$ be a family with no $k$-sunflower. For each $r$, let $\mathcal F^{(r)}=\{S\in\mathcal F: |S|=r\}$. Then each $\mathcal F^{(r)}$ is $r$-uniform and $k$-sunflower-free, so by Lemma 857.2, $|\mathcal F^{(r)}|\le (k-1)^r r!$. Summing over $r=0,1,\dots,n$ gives $|\mathcal F|\le \sum_{r=0}^n (k-1)^r r!$. Therefore the minimal $m(n,k)$ forcing a sunflower satisfies $m(n,k)\le 1+\sum_{r=0}^n (k-1)^r r!$. $\square$

VERIFICATION.

• Lemma 857.1 uses only the chain property and distinctness; the contradiction uses the two smallest sets in the chosen subfamily, so it works for any $k\ge 3$.
• In Lemma 857.2, the only place maximality of the disjoint family $\{S_i\}$ is used is to assert every $T\in\mathcal F$ intersects some $S_i$.
• Endpoints: the problem statement uses the literal "pairwise have the same intersection", which matches our definition.
• Small-case computation (for $n\le 4$) is consistent with the trivial fact $m(n,2)=2$.

FINAL. UNRESOLVED.

(i) Strongest proved partial results. We proved the explicit lower bound $m(n,k)\ge n+2$ for all $k\ge 3$ (chain construction), and the explicit upper bound $m(n,k)\le 1+\sum_{r=0}^n (k-1)^r r!$ (sunflower lemma by uniform layers). We also computed exact values for $m(n,k)$ for $n\le 4$ and $k\in\{2,3,4\}$.

(ii) First gap. Determine the correct exponential growth rate of $m(n,k)$ as $n\to\infty$ for fixed $k\ge 3$; in particular, decide whether $m(n,k)\le c_k^n$ for some $c_k<2$ and give sharp $c_k$.

(iii) Top 3 next moves. $1$ Strengthen the layer-by-layer bound by exploiting interactions between layers (the present upper bound is dominated by the $r=n$ term and is extremely loose). $2$ For $k=3$, attempt to reproduce a polynomial-method style argument directly in $2^{[n]}$ to recover a $c^n$ upper bound with $c<2$. $3$ Compute $F(n,k)$ exactly for $n=5,6$ (via SAT/ILP) to guess extremal structures.

(iv) What a minimal counterexample would look like. A near-extremal sunflower-free family would have size close to the best possible exponential base (if it exists), likely exhibiting product/tensor structure across coordinates (since tensoring preserves sunflower-freeness and stabilises exponential growth rates).

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.