You are currently browsing the tag archive for the ‘sunflowers’ tag.

I’ve just uploaded to the arXiv my paper The Ionescu-Wainger multiplier theorem and the adeles“. This paper revisits a useful multiplier theorem of Ionescu and Wainger on “major arc” Fourier multiplier operators on the integers (or lattices ), and strengthens the bounds while also interpreting it from the viewpoint of the adelic integers (which were also used in my recent paper with Krause and Mirek).

For simplicity let us just work in one dimension. Any smooth function then defines a discrete Fourier multiplier operator for any by the formula

where is the Fourier transform on ; similarly, any test function defines a continuous Fourier multiplier operator by the formula where . In both cases we refer to as the*symbol*of the multiplier operator .

We will be interested in discrete Fourier multiplier operators whose symbols are supported on a finite union of arcs. One way to construct such operators is by “folding” continuous Fourier multiplier operators into various target frequencies. To make this folding operation precise, given any continuous Fourier multiplier operator , and any frequency , we define the discrete Fourier multiplier operator for any frequency shift by the formula

or equivalently More generally, given any finite set , we can form a multifrequency projection operator on by the formula thus This construction gives discrete Fourier multiplier operators whose symbol can be localised to a finite union of arcs. For instance, if is supported on , then is a Fourier multiplier whose symbol is supported on the set .There are a body of results relating the theory of discrete Fourier multiplier operators such as or with the theory of their continuous counterparts. For instance we have the basic result of Magyar, Stein, and Wainger:

Proposition 1 (Magyar-Stein-Wainger sampling principle)Let and .

- (i) If is a smooth function supported in , then , where denotes the operator norm of an operator .
- (ii) More generally, if is a smooth function supported in for some natural number , then .

When the implied constant in these bounds can be set to equal . In the paper of Magyar, Stein, and Wainger it was posed as an open problem as to whether this is the case for other ; in an appendix to this paper I show that the answer is negative if is sufficiently close to or , but I do not know the full answer to this question.

This proposition allows one to get a good multiplier theory for symbols supported near cyclic groups ; for instance it shows that a discrete Fourier multiplier with symbol for a fixed test function is bounded on , uniformly in and . For many applications in discrete harmonic analysis, one would similarly like a good multiplier theory for symbols supported in “major arc” sets such as

and in particular to get a good Littlewood-Paley theory adapted to major arcs. (This is particularly the case when trying to control “true complexity zero” expressions for which the minor arc contributions can be shown to be negligible; my recent paper with Krause and Mirek is focused on expressions of this type.) At present we do not have a good multiplier theory that is directly adapted to the classical major arc set (1) (though I do not know of rigorous negative results that show that such a theory is not possible); however, Ionescu and Wainger were able to obtain a useful substitute theory in which (1) was replaced by a somewhat larger set that had better multiplier behaviour. Starting with a finite collection of pairwise coprime natural numbers, and a natural number , one can form the major arc type set where consists of all rational points in the unit circle of the form where is the product of at most elements from and is an integer. For suitable choices of and not too large, one can make this set (2) contain the set (1) while still having a somewhat controlled size (very roughly speaking, one chooses to consist of (small powers of) large primes between and for some small constant , together with something like the product of all the primes up to (raised to suitable powers)).In the regime where is fixed and is small, there is a good theory:

Theorem 2 (Ionescu-Wainger theorem, rough version)If is an even integer or the dual of an even integer, and is supported on for a sufficiently small , then

There is a more explicit description of how small needs to be for this theorem to work (roughly speaking, it is not much more than what is needed for all the arcs in (2) to be disjoint), but we will not give it here. The logarithmic loss of was reduced to by Mirek. In this paper we refine the bound further to

when or for some integer . In particular there is no longer any logarithmic loss in the cardinality of the set .The proof of (3) follows a similar strategy as to previous proofs of Ionescu-Wainger type. By duality we may assume . We use the following standard sequence of steps:

- (i) (Denominator orthogonality) First one splits into various pieces depending on the denominator appearing in the element of , and exploits “superorthogonality” in to estimate the norm by the norm of an appropriate square function.
- (ii) (Nonconcentration) One expands out the power of the square function and estimates it by a “nonconcentrated” version in which various factors that arise in the expansion are “disjoint”.
- (iii) (Numerator orthogonality) We now decompose based on the numerators appearing in the relevant elements of , and exploit some residual orthogonality in this parameter to reduce to estimating a square-function type expression involving sums over various cosets .
- (iv) (Marcinkiewicz-Zygmund) One uses the Marcinkiewicz-Zygmund theorem relating scalar and vector valued operator norms to eliminate the role of the multiplier .
- (v) (Rubio de Francia) Use a reverse square function estimate of Rubio de Francia type to conclude.

The main innovations are that of using the probabilistic decoupling method to remove some logarithmic losses in (i), and recent progress on the Erdos-Rado sunflower conjecture (as discussed in this recent post) to improve the bounds in (ii). For (i), the key point is that one can express a sum such as

where is the set of -element subsets of an index set , and are various complex numbers, as an average where is a random partition of into subclasses (chosen uniformly over all such partitions), basically because every -element subset of has a probability exactly of being completely shattered by such a random partition. This “decouples” the index set into a Cartesian product which is more convenient for application of the superorthogonality theory. For (ii), the point is to efficiently obtain estimates of the form where are various non-negative quantities, and a sunflower is a collection of sets that consist of a common “core” and disjoint “petals” . The other parts of the argument are relatively routine; see for instance this survey of Pierce for a discussion of them in the simple case .In this paper we interpret the Ionescu-Wainger multiplier theorem as being essentially a consequence of various quantitative versions of the Shannon sampling theorem. Recall that this theorem asserts that if a (Schwartz) function has its Fourier transform supported on , then can be recovered uniquely from its restriction . In fact, as can be shown from a little bit of routine Fourier analysis, if we narrow the support of the Fourier transform slightly to for some , then the restriction has the same behaviour as the original function, in the sense that

for all ; see Theorem 4.18 of this paper of myself with Krause and Mirek. This is consistent with the uncertainty principle, which suggests that such functions should behave like a constant at scales .The quantitative sampling theorem (4) can be used to give an alternate proof of Proposition 1(i), basically thanks to the identity

whenever is Schwartz and has Fourier transform supported in , and is also supported on ; this identity can be easily verified from the Poisson summation formula. A variant of this argument also yields an alternate proof of Proposition 1(ii), where the role of is now played by , and the standard embedding of into is now replaced by the embedding of into ; the analogue of (4) is now whenever is Schwartz and has Fourier transform supported in , and is endowed with probability Haar measure.The locally compact abelian groups and can all be viewed as projections of the adelic integers (the product of the reals and the profinite integers ). By using the Ionescu-Wainger multiplier theorem, we are able to obtain an adelic version of the quantitative sampling estimate (5), namely

whenever , is Schwartz-Bruhat and has Fourier transform supported on for some sufficiently small (the precise bound on depends on in a fashion not detailed here). This allows one obtain an “adelic” extension of the Ionescu-Wainger multiplier theorem, in which the operator norm of any discrete multiplier operator whose symbol is supported on major arcs can be shown to be comparable to the operator norm of an adelic counterpart to that multiplier operator; in principle this reduces “major arc” harmonic analysis on the integers to “low frequency” harmonic analysis on the adelic integers , which is a simpler setting in many ways (mostly because the set of major arcs (2) is now replaced with a product set ).
A family of sets for some is a sunflower if there is a *core set* contained in each of the such that the *petal sets* are disjoint. If , let denote the smallest natural number with the property that any family of distinct sets of cardinality at most contains distinct elements that form a sunflower. The celebrated Erdös-Rado theorem asserts that is finite; in fact Erdös and Rado gave the bounds

*sunflower conjecture*asserts in fact that the upper bound can be improved to . This remains open at present despite much effort (including a Polymath project); after a long series of improvements to the upper bound, the best general bound known currently is for all , established in 2019 by Rao (building upon a recent breakthrough a month previously of Alweiss, Lovett, Wu, and Zhang). Here we remove the easy cases or in order to make the logarithmic factor a little cleaner.

Rao’s argument used the Shannon noiseless coding theorem. It turns out that the argument can be arranged in the very slightly different language of Shannon entropy, and I would like to present it here. The argument proceeds by locating the core and petals of the sunflower separately (this strategy is also followed in Alweiss-Lovett-Wu-Zhang). In both cases the following definition will be key. In this post all random variables, such as random sets, will be understood to be discrete random variables taking values in a finite range. We always use boldface symbols to denote random variables, and non-boldface for deterministic quantities.

Definition 1 (Spread set)Let . A random set is said to be -spread if one has for all sets . A family of sets is said to be -spread if is non-empty and the random variable is -spread, where is drawn uniformly from .

The core can then be selected greedily in such a way that the remainder of a family becomes spread:

Lemma 2 (Locating the core)Let be a family of subsets of a finite set , each of cardinality at most , and let . Then there exists a “core” set of cardinality at most such that the set has cardinality at least , and such that the family is -spread. Furthermore, if and the are distinct, then .

*Proof:* We may assume is non-empty, as the claim is trivial otherwise. For any , define the quantity

Let be the set (3). Since , is non-empty. It remains to check that the family is -spread. But for any and drawn uniformly at random from one has

Observe that , and the probability is only non-empty when are disjoint, so that . The claim follows.In view of the above lemma, the bound (2) will then follow from

Proposition 3 (Locating the petals)Let be natural numbers, and suppose that for a sufficiently large constant . Let be a finite family of subsets of a finite set , each of cardinality at most which is -spread. Then there exist such that is disjoint.

Indeed, to prove (2), we assume that is a family of sets of cardinality greater than for some ; by discarding redundant elements and sets we may assume that is finite and that all the are contained in a common finite set . Apply Lemma 2 to find a set of cardinality such that the family is -spread. By Proposition 3 we can find such that are disjoint; since these sets have cardinality , this implies that the are distinct. Hence form a sunflower as required.

Remark 4Proposition 3 is easy to prove if we strengthen the condition on to . In this case, we have for every , hence by the union bound we see that for any with there exists such that is disjoint from the set , which has cardinality at most . Iterating this, we obtain the conclusion of Proposition 3 in this case. This recovers a bound of the form , and by pursuing this idea a little further one can recover the original upper bound (1) of Erdös and Rado.

It remains to prove Proposition 3. In fact we can locate the petals one at a time, placing each petal inside a random set.

Proposition 5 (Locating a single petal)Let the notation and hypotheses be as in Proposition 3. Let be a random subset of , such that each lies in with an independent probability of . Then with probability greater than , contains one of the .

To see that Proposition 5 implies Proposition 3, we randomly partition into by placing each into one of the , chosen uniformly and independently at random. By Proposition 5 and the union bound, we see that with positive probability, it is simultaneously true for all that each contains one of the . Selecting one such for each , we obtain the required disjoint petals.

We will prove Proposition 5 by gradually increasing the density of the random set and arranging the sets to get quickly absorbed by this random set. The key iteration step is

Proposition 6 (Refinement inequality)Let and . Let be a random subset of a finite set which is -spread, and let be a random subset of independent of , such that each lies in with an independent probability of . Then there exists another -spread random subset of whose support is contained in the support of , such that and

Note that a direct application of the first moment method gives only the bound

but the point is that by switching from to an equivalent we can replace the factor by a quantity significantly smaller than .One can iterate the above proposition, repeatedly replacing with (noting that this preserves the -spread nature of ) to conclude

Corollary 7 (Iterated refinement inequality)Let , , and . Let be a random subset of a finite set which is -spread, and let be a random subset of independent of , such that each lies in with an independent probability of . Then there exists another random subset of with support contained in the support of , such that

Now we can prove Proposition 5. Let be chosen shortly. Applying Corollary 7 with drawn uniformly at random from the , and setting , or equivalently , we have

In particular, if we set , so that , then by choice of we have , hence In particular with probability at least , there must exist such that , giving the proposition.It remains to establish Proposition 6. This is the difficult step, and requires a clever way to find the variant of that has better containment properties in than does. The main trick is to make a conditional copy of that is conditionally independent of subject to the constraint . The point here is that this constrant implies the inclusions

and Because of the -spread hypothesis, it is hard for to contain any fixed large set. If we could apply this observation in the contrapositive to we could hope to get a good upper bound on the size of and hence on thanks to (4). One can also hope to improve such an upper bound by also employing (5), since it is also hard for the random set to contain a fixed large set. There are however difficulties with implementing this approach due to the fact that the random sets are coupled with in a moderately complicated fashion. In Rao’s argument a somewhat complicated encoding scheme was created to give information-theoretic control on these random variables; below the fold we accomplish a similar effect by using Shannon entropy inequalities in place of explicit encoding. A certain amount of information-theoretic sleight of hand is required to decouple certain random variables to the extent that the Shannon inequalities can be effectively applied. The argument bears some resemblance to the “entropy compression method” discussed in this previous blog post; there may be a way to more explicitly express the argument below in terms of that method. (There is also some kinship with the method of dependent random choice, which is used for instance to establish the Balog-Szemerédi-Gowers lemma, and was also translated into information theoretic language in these unpublished notes of Van Vu and myself.)
## Recent Comments