Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Let qq be a prime power, n≥1n\ge1 an integer, A1,…,AnA_1,\ldots,A_n finite-dimensional vector spaces over Fq\mathbb F_q, and CC a linear subspace of A1⊕⋯⊕AnA_1\oplus\cdots\oplus A_n. A word c=(c1,…,cn)c=(c_1,\ldots,c_n) represents the nn-element set S(c)={(i,ci):1≤i≤n}S(c)=\{(i,c_i):1\le i\le n\}, and distinct words represent distinct sets. A kk-sunflower consists of kk distinct sets whose pairwise intersections all equal one set, which may be empty. For every integer k≥3k\ge3 and every a∈A1⊕⋯⊕Ana\in A_1\oplus\cdots\oplus A_n, if the nn-uniform family

F={S(c):c∈a+C}\mathcal F=\{S(c):c\in a+C\}

contains no kk-sunflower, then

∣F∣=∣C∣<k2n.\lvert\mathcal F\rvert=\lvert C\rvert<k^{2n}.

More precisely, dim⁡C<n⌈log⁡qk⌉\dim C<n\lceil\log_qk\rceil and ∣C∣≤qn⌈log⁡qk⌉−1\lvert C\rvert\le q^{n\lceil\log_qk\rceil-1}; if q≥kq\ge k, then C={0}C=\{0\} and F\mathcal F has one member. The bound comes from a subspace theorem: for every integer s≥1s\ge1, if dim⁡C≥sn\dim C\ge sn, there is an ss-dimensional subspace UU of CC on which each coordinate projection is zero or injective, and for every aa the qsq^s sets S(c)S(c), c∈a+Uc\in a+U, form a qsq^s-sunflower.

Covers. The special case of Problem 20 for affine linear word families: the nn-uniform families {S(c):c∈a+C}\{S(c):c\in a+C\} above, over any finite field Fq\mathbb F_q and with coordinate alphabets AiA_i of any finite dimension. For every k≥3k\ge3, every such family with at least k2nk^{2n} members contains a kk-sunflower, and the base k2k^2 does not depend on the field or on the alphabet dimensions. The result does not bound f(n,k)f(n,k), which ranges over all nn-uniform families: a family need not have this form, and passing from an arbitrary word family to its affine span can introduce new words and new sunflowers. Families outside the class are not addressed, and the general question is not settled by this claim.

Credit. The independent-representative criterion in the proof is the classical linear version of Hall's condition; the proof gives it in full and uses no external theorem. No novelty is claimed for that criterion or for the structured bound without a fuller literature comparison.

Standing. L268 is author-recorded at tier 0: a complete noncomputational argument, without independent examination or a Lean proof. Catalog acceptance is pending.

Depends on. L268 (tier 0), which consumes no other native claim and no external theorem.