Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
These are author-recorded arguments by Plasma AI for the three-petal case of Problem 20, in the spread form of the editable proof sketch. Lemma 1 and Corollary 2 are a routine form of the slice-rank argument of Naslund–Sawin's Theorem 5, combined with the colouring in the proof of Alon–Shpilka–Umans' Theorem 2.6; no novelty is claimed for them. The later sections apply them to the links of the spread reduction and to the obstruction families of this folder. No literature search beyond the held sources has been made for those applications, and none of this has been independently reviewed. Nothing here settles Problem 20: the conclusions are fixed-universe estimates, statements about particular families, and a precise description of what remains.
Words and the slice-rank bound
Let be finite sets, . A word family is a subset . Three distinct words form a -sunflower when in every coordinate their entries are all equal or pairwise distinct. As in the linear word note, the word represents the -set , and the word sunflowers are exactly the set sunflowers among these sets. For write and .
Lemma 1. Let contain no -sunflower and put . Then
where is the elementary symmetric polynomial of degree . More generally, let , write , and let be the family of inclusion-maximal sets with . Then . With and every nonempty, this gives
Proof. Work over . For symbols put , where is the indicator. Its value is , which is in , when ; it is when exactly two of the symbols agree, and when all three differ. On define
Then . If are not all equal, some coordinate holds exactly two equal entries, so . For two equal words and a third word this is any coordinate where the third differs. For three distinct words it holds because they do not form a sunflower. Thus is a diagonal tensor with nonzero diagonal, and by the slice-rank lemma of Tao, stated as Lemma 6 in Naslund and Sawin's paper, its slice rank equals .
Expanding the product writes as a signed sum, over pairwise disjoint , of the functions . The word enters through the coordinates , the word through , and through . Since
one of the three sets has weight at most ; assign the term to that variable. A term assigned to equals, on , for some functions . If , then on the function is the sum of over the that restrict to . Choosing with for each , all terms assigned to lie in a space of slices of dimension at most , and similarly for and . So the slice rank is at most .
For unit weights consists of the -sets, and gives the elementary symmetric bound. For and ,
For a common alphabet of symbols the second bound is . It is weaker than Naslund and Sawin's bound , whose character expansion drops the trivial character. Two features matter below. The projection form depends on itself rather than on the alphabets: if, for every set of coordinates, the fibers of on have average size larger than , then contains a -sunflower, however large its alphabets are. The weighted form depends on the geometric mean of the alphabet sizes, so a few large alphabets cost little.
Families on few points
Corollary 2. Let be a family of -sets, , whose members lie in a set of points, and suppose has no -sunflower. Put and
Then
and for every . Consequently as , with .
Proof. Colour the points uniformly at random with colours. A member receives distinct colours with probability , so some colouring makes at least members rainbow. Let be the points of colour and send a rainbow member to the word whose -th entry is its point of colour . Distinct members give distinct words. For two rainbow members, the intersection consists of the points at which their words agree. So three rainbow members have equal pairwise intersections exactly when their words have equal pairwise agreement sets, that is, when every coordinate is all equal or all distinct. Lemma 1 and Maclaurin's inequality for nonnegative , with , give .
For the constant, gives , and for ; at the same binomial bound is . Write .
- If with , then and , since .
- If with , then , and . So , since .
- If with , then and , and is times . So , since .
Finally , and , so , and .
Spread links are unbalanced
Proposition 3. Let and , so that suffices. Every family of more than sets of size , all contained in a set of at most points, contains a -sunflower.
Proof. Otherwise Corollary 2 gives , that is, . Since and , this gives , a contradiction.
The hypothesis asks nothing about spread or cores. Its use is in the link reduction, link 1 of the sketch. Let be a family of -sets with more than members and no -sunflower, where . The link at an inclusion-maximal with is a family of -sets, , with , in which every point lies in at most members. Counting incidences, its members cover a set of points. Proposition 3 with then forces
The link is a counterexample to SF() at rate . So the links that the reduction produces from counterexamples use, on average, more than points per element of a member, while absolute spread alone forces only more than . The estimate places no restriction on the core of the sunflower it finds. The obstructions of L214 and L215, which defeat matchings and bounded cores, do not affect it. It is still a fixed-universe estimate: it says nothing about links on more points, which is where the whole difficulty of SF() now lies.
An intersecting normal form
Proposition 4. Let be a family of -sets with no -sunflower, let , and for let
Each is an intersecting family of -sets with no -sunflower, , and if is absolutely -spread then so is every . Consequently, if for some every intersecting, absolutely -spread family of -sets without a -sunflower has at most members, for every , then SF() holds with .
Proof. The members with are determined by , so the count holds. Suppose have and disjoint parts outside . Then , so are three distinct members, because , with all pairwise intersections equal to : a -sunflower. So is intersecting. If three members of have common pairwise intersection , the corresponding members of have common pairwise intersection . For a nonempty outside , $|F^{(A)}U|\le|F{A\cup U}|\le c^{n-|A|-|U|}$, which is absolute -spread. For the consequence, an absolutely -spread family of -sets with no -sunflower has at most members.
Conversely, Problem 20 for with base gives the hypothesis for every , spread or not. With link 2 of the sketch, the target for is therefore equivalent to the statement that, for some , every intersecting, absolutely -spread family of -sets without a -sunflower has at most members. In that normal form every sunflower has a nonempty core, and the size rate is within the factor of the spread rate. For petals the same traces have no pairwise disjoint members. The reduction is elementary and is not claimed to be new.
Families the slice-rank bound certifies
The robust-sunflower barrier family. The lemma of Alweiss–Lovett–Wu–Zhang that makes their robust-sunflower bound sharp gives, for large , a family of -sets with at least members and no -robust sunflower. Its proof takes disjoint blocks of points with and a family of transversals of them. So no size below forces a -robust sunflower, and a proof of Problem 20 cannot run through such robust sunflowers alone. The slice-rank bound has no such limit on these families.
Example 5. Let and . Every family of transversals of blocks of at most points each, with at least members, contains a -sunflower.
Proof. The transversals are words over the blocks. If there were no -sunflower, Lemma 1 would give , hence . As gives , the left side is at least , which forces , false for .
With , the barrier family above satisfies these hypotheses for every with . The thresholds are not optimized; the point is that the published barrier to the robust-sunflower method is not a barrier to this one.
Sections. Let be a family on a set , let , and let be a partition of into nonempty parts. The section consists of the members of that lie in and are unions of parts. The quotient of such a member is .
Lemma 6. The map is injective on the section, and is the union of the parts in . Hence, for every , members of the section form a -sunflower exactly when their quotients do. The same holds for a section of a link , and a -sunflower of the link lifts to one of whose core contains .
Proof. A member of the section is the union of its quotient, and distinct parts are disjoint, so intersections of members are the unions of the intersections of their quotients. Equal pairwise intersections of members are therefore equivalent to equal pairwise intersections of quotients. A sunflower of the link with core gives the sunflower with core .
Call a section certificate of a link , possibly empty, a section of , and a set of quotients with a common number of parts that is larger than the bound of Corollary 2 for and . By Corollary 2 and Lemma 6, a certificate yields a -sunflower of .
Example 7. In the family of L214, , fix for every point of the outer ground set an inner member of , and take the parts . A member is a union of parts exactly when for every , so the section is a copy of whose quotient is itself. Its link at the center is the full product of the blocks , a word family with words over alphabets of symbols. For it has three pairwise disjoint words, a sunflower with core . Lemma 1 also detects a sunflower there from the number of words and the alphabet sizes alone once , which holds for every when is large, because . For , this center link also exceeds the bound of Corollary 2, since and , and hence gives a section certificate in the narrower sense defined above. In the families of L215, sections whose parts are inner triangle-power members reduce to these. The sunflowers were already known (obstruction note); the point is that sections reach them although the families are intersecting and their point counts lie far beyond the range of Proposition 3.
Thinned families and unit-core links
The absolute families of L214 come from a random thinning, under which the sections of Example 7 retain almost nothing. The sunflowers survive in links at single parts.
Proposition 8. Let be an -uniform family on , let form a -sunflower with core , and let be a nonempty -uniform family with . Let keep every member of independently with probability . Then, with probability at least , contains a -sunflower whose core is for some members ; when is a single point this core is a single part.
Proof. Fix for . For each , the members of with outer set and fiber over every number , since the fibers over are free, and these three classes are disjoint. One retained member from each class gives a -sunflower with the stated core: the outer sets meet pairwise exactly in , where all three fibers agree. Each class is missed with probability .
Every block family with has such sunflowers. For , three pairwise disjoint transversals of give the members , with core . For every , three members of the second kind with a common have core . So Proposition 8 applies to random thinnings of every substitution power in this folder whose outer family is a block family, including those of L214, L215 and the varying-scale construction of the refined obstruction note, with a bound that depends on the retention probability.
Corollary 9. Let , , , , and . Let keep every member of independently with probability , the thinning in Lemma 4 of the proof of L214.
- Every section of Example 7 contains fewer than one member of in expectation.
- Put . With probability at least , every section of Example 7 contains fewer than members of simultaneously.
- With probability at least , contains a -sunflower whose core is a single part , with the first center of the outer block family and an inner member.
- Hence, with positive probability, has more than members, is absolutely -spread and intersecting, contains such a sunflower, and has fewer than members in each of those sections.
Proof. As , . Here , so , and by L214's Lemma 1 and with . A section of Example 7 holds members of , so it retains in expectation, using . As and , this is at most .
For the simultaneous assertion, let be the number of outer points. There are at most choices of the section, where and . Using and gives
The mean for each fixed section obeys the bound above, so . Indeed , , , and . The binomial tail bound then gives . A union bound over all sections, followed by , yields
Finally gives for .
Apply Proposition 8 with , the sunflower with core , and . Then
Since and , $(m+1)\log r-\log(2\rho)\ge m\log16-\log34 \ge2m$, and with and the exponent is at least . The proof of L214's Lemma 4 bounds the probability that by and the probability that spread fails by , and . Every subfamily of is intersecting.
The same count works far below the rate of L214. Keep every member of independently with probability , for any with . Then , because
so by Proposition 8 the result contains a -sunflower with probability at least . Random subfamilies of these powers therefore keep a sunflower at rates barely above ; a family that hides its sunflowers must be thinned in a correlated way.
The sunflower of Proposition 8 is a matching in the link at the parts over , found through the projection of that link onto the outer family: three members whose outer sets meet only in are disjoint outside the core, whatever their other inner fibers. On the simultaneous event of Corollary 9, even choosing a section of Example 7 after seeing leaves fewer than members. Neither its whole quotient, of rank , nor its link at the first-center part, of rank , can then exceed the count bounds used in Example 7. For either rank , the bound of Corollary 2 is at least ; the unweighted bound of Lemma 1 has the same lower bound for a nonempty family. Some such sections can nevertheless contain a few sunflower members. In particular, the three members selected in Proposition 8 fit into one adaptively chosen section, since their outer petals are disjoint and their core fibers agree.
Disjointness lifts from such projections, while sunflowers with nonempty cores do not in general, since a common outer point can carry different inner fibers. So exact sections certify the unthinned families, while for the thinned ones the sunflower comes from a projected matching; whether another link inside those sections, or a different section, certifies the thinned families is not decided here. Projected matchings after taking links at unions of parts supply an additional certificate for these thinned families.
Where the engine stops
The single-scale window. For a word family of coordinates with words over alphabets of symbols, the alphabet bound of Lemma 1 decides nothing once , that is, roughly once ; the projection form still applies when the projections to coordinates are far from injective. The hitting lemma behind Bell–Chueluecha–Warnke's Lemma 2 needs spread . Take a uniformly random subfamily of with words, an integer and . A cylinder fixing coordinates holds of its words in expectation, and for constant , large and beyond the window, neither the alphabet bound nor the hitting lemma applies. Such families are not plausible counterexamples: the expected number of ordered triples of pairwise disjoint words among them is , about , far more than when . The complete second-moment calculation shows that the matching probability tends to one at every fixed rate , uniformly over alphabets when the requested sample size is available. Thus the random-family side is proved, while its extension to adversarially correlated families remains open.
The residual. Let . A counterexample to SF() at rate is an absolutely -spread family of -sets with more than members and no -sunflower. By Proposition 4 one of its traces is an intersecting, absolutely -spread family of -sets, , with more than members and no -sunflower. Let be the number of points its members cover. Proposition 3 at rate , with , rules out and then gives . By Corollary 2 and Lemma 6 it has no section certificate in any link. The thinned substitution powers of Corollary 9 are intersecting, absolutely spread and large, like the families of this class. In those powers, the sections of Example 7 can fail to give the displayed counting certificates even though a matching in a projected unit-core link finds a sunflower. Since a -sunflower is a matching in the link at its core, SF() is equivalent to the statement that every family in this class has three pairwise disjoint members in some link. That is a reformulation, not a reduction; its use is to name the families that no known certificate reaches.
What would advance. A dichotomy of the following kind would prove SF():
- (R) an alphabet-independent pseudorandomness condition on a link, under which counting gives three pairwise disjoint members, or a condition that counts sunflowers with arbitrary cores;
- (S) when the condition fails, a passage to a link, section or projection whose matchings or sunflowers lift, with a controlled increment in an explicit invariant, so that the process ends in case (R) or in a certificate after boundedly many steps per scale.
Any such statement must handle four test cases at once: random families (by (R)); the unthinned substitution powers (by sections); the thinned powers of Corollary 9 (by projected matchings); and the maximal-rate chain obstruction, whose union of two intersecting parts requires keeping both parts. Counting inside a single link is not enough by itself: the families of L214 have no disjoint pair at all in the empty link, at every rate, and their sunflowers lie in other links. The agreement-statistics note supplies concrete Fourier criteria for (R), including a criterion on a binary affine span that permits nonempty cores. It also proves that the aggregate pair-agreement profile does not determine sunflower behavior. The structural implication (S), and therefore the dichotomy, remains open.
The bound of Lemma 1 is for three petals. For the analogous coordinate function contains terms such as that involve every variable, and no saving of this kind is established here.