You are currently browsing the category archive for the ‘math.CO’ category.

Rachel Greenfeld and I have just uploaded to the arXiv our paper “The structure of translational tilings in ${{\bf Z}^d}$“. This paper studies the tilings ${1_F * 1_A = 1}$ of a finite tile ${F}$ in a standard lattice ${{\bf Z}^d}$, that is to say sets ${A \subset {\bf Z}^d}$ (which we call tiling sets) such that every element of ${{\bf Z}^d}$ lies in exactly one of the translates ${a+F, a \in A}$ of ${F}$. We also consider more general tilings of level ${k}$ ${1_F * 1_A = k}$ for a natural number ${k}$ (several of our results consider an even more general setting in which ${1_F * 1_A}$ is periodic but allowed to be non-constant).

In many cases the tiling set ${A}$ will be periodic (by which we mean translation invariant with respect to some lattice (a finite index subgroup) of ${{\bf Z}^d}$). For instance one simple example of a tiling is when ${F \subset {\bf Z}^2}$ is the unit square ${F = \{0,1\}^2}$ and ${A}$ is the lattice ${2{\bf Z}^2 = \{ 2x: x \in {\bf Z}^2\}}$. However one can modify some tilings to make them less periodic. For instance, keeping ${F = \{0,1\}^2}$ one also has the tiling set

$\displaystyle A = \{ (2x, 2y+a(x)): x,y \in {\bf Z} \}$

where ${a: {\bf Z} \rightarrow \{0,1\}}$ is an arbitrary function. This tiling set is periodic in a single direction ${(0,2)}$, but is not doubly periodic. For the slightly modified tile ${F = \{0,1\} \times \{0,2\}}$, the set

$\displaystyle A = \{ (2x, 4y+2a(x)): x,y \in {\bf Z} \} \cup \{ (2x+b(y), 4y+1): x,y \in {\bf Z}\}$

for arbitrary ${a,b: {\bf Z} \rightarrow \{0,1\}}$ can be verified to be a tiling set, which in general will not exhibit any periodicity whatsoever; however, it is weakly periodic in the sense that it is the disjoint union of finitely many sets, each of which is periodic in one direction.

The most well known conjecture in this area is the Periodic Tiling Conjecture:

Conjecture 1 (Periodic tiling conjecture) If a finite tile ${F \subset {\bf Z}^d}$ has at least one tiling set, then it has a tiling set which is periodic.

This conjecture was stated explicitly by Lagarias and Wang, and also appears implicitly in this text of Grunbaum and Shepard. In one dimension ${d=1}$ there is a simple pigeonhole principle argument of Newman that shows that all tiling sets are in fact periodic, which certainly implies the periodic tiling conjecture in this case. The ${d=2}$ case was settled more recently by Bhattacharya, but the higher dimensional cases ${d > 2}$ remain open in general.

We are able to obtain a new proof of Bhattacharya’s result that also gives some quantitative bounds on the periodic tiling set, which are polynomial in the diameter of the set if the cardinality ${|F|}$ of the tile is bounded:

Theorem 2 (Quantitative periodic tiling in ${{\bf Z}^2}$) If a finite tile ${F \subset {\bf Z}^2}$ has at least one tiling set, then it has a tiling set which is ${M{\bf Z}^2}$-periodic for some ${M \ll_{|F|} \mathrm{diam}(F)^{O(|F|^4)}}$.

Among other things, this shows that the problem of deciding whether a given subset of ${{\bf Z}^2}$ of bounded cardinality tiles ${{\bf Z}^2}$ or not is in the NP complexity class with respect to the diameter ${\mathrm{diam}(F)}$. (Even the decidability of this problem was not known until the result of Bhattacharya.)

We also have a closely related structural theorem:

Theorem 3 (Quantitative weakly periodic tiling in ${{\bf Z}^2}$) Every tiling set of a finite tile ${F \subset {\bf Z}^2}$ is weakly periodic. In fact, the tiling set is the union of at most ${|F|-1}$ disjoint sets, each of which is periodic in a direction of magnitude ${O_{|F|}( \mathrm{diam}(F)^{O(|F|^2)})}$.

We also have a new bound for the periodicity of tilings in ${{\bf Z}}$:

Theorem 4 (Universal period for tilings in ${{\bf Z}}$) Let ${F \subset {\bf Z}}$ be finite, and normalized so that ${0 \in F}$. Then every tiling set of ${F}$ is ${qn}$-periodic, where ${q}$ is the least common multiple of all primes up to ${2|F|}$, and ${n}$ is the least common multiple of the magnitudes ${|f|}$ of all ${f \in F \backslash \{0\}}$.

We remark that the current best complexity bound of determining whether a subset of ${{\bf Z}}$ tiles ${{\bf Z}}$ or not is ${O( \exp(\mathrm{diam}(F)^{1/3+o(1)}))}$, due to Biro. It may be that the results in this paper can improve upon this bound, at least for tiles of bounded cardinality.

On the other hand, we discovered a genuine difference between level one tiling and higher level tiling, by locating a counterexample to the higher level analogue of (the qualitative version of) Theorem 3:

Theorem 5 (Counterexample) There exists an eight-element subset ${F \subset {\bf Z}^2}$ and a level ${4}$ tiling ${1_F * 1_A = 4}$ such that ${A}$ is not weakly periodic.

We do not know if there is a corresponding counterexample to the higher level periodic tiling conjecture (that if ${F}$ tiles ${{\bf Z}^d}$ at level ${k}$, then there is a periodic tiling at the same level ${k}$). Note that it is important to keep the level fixed, since one trivially always has a periodic tiling at level ${|F|}$ from the identity ${1_F * 1 = |F|}$.

The methods of Bhattacharya used the language of ergodic theory. Our investigations also originally used ergodic-theoretic and Fourier-analytic techniques, but we ultimately found combinatorial methods to be more effective in this problem (and in particular led to quite strong quantitative bounds). The engine powering all of our results is the following remarkable fact, valid in all dimensions:

Lemma 6 (Dilation lemma) Suppose that ${A}$ is a tiling of a finite tile ${F \subset {\bf Z}^d}$. Then ${A}$ is also a tiling of the dilated tile ${rF}$ for any ${r}$ coprime to ${n}$, where ${n}$ is the least common multiple of all the primes up to ${|F|}$.

Versions of this dilation lemma have previously appeared in work of Tijdeman and of Bhattacharya. We sketch a proof here. By the fundamental theorem of arithmetic and iteration it suffices to establish the case where ${r}$ is a prime ${p>|F|}$. We need to show that ${1_{pF} * 1_A = 1}$. It suffices to show the claim ${1_{pF} * 1_A = 1 \hbox{ mod } p}$, since both sides take values in ${\{0,\dots,|F|\} \subset \{0,\dots,p-1\}}$. The convolution algebra ${{\bf F}_p[{\bf Z}^d]}$ (or group algebra) of finitely supported functions from ${{\bf Z}^d}$ to ${{\bf F}_p}$ is a commutative algebra of characteristic ${p}$, so we have the Frobenius identity ${(f+g)^{*p} = f^{*p} + g^{*p}}$ for any ${f,g}$. As a consequence we see that ${1_{pF} = 1_F^{*p} \hbox{ mod } p}$. The claim now follows by convolving the identity ${1_F * 1_A = 1 \hbox{ mod } p}$ by ${p-1}$ further copies of ${1_F}$.

In our paper we actually establish a more general version of the dilation lemma that can handle tilings of higher level or of a periodic set, and this stronger version is useful to get the best quantitative results, but for simplicity we focus attention just on the above simple special case of the dilation lemma.

By averaging over all ${r}$ in an arithmetic progression, one already gets a useful structural theorem for tilings in any dimension, which appears to be new despite being an easy consequence of Lemma 6:

Corollary 7 (Structure theorem for tilings) Suppose that ${A}$ is a tiling of a finite tile ${F \subset {\bf Z}^d}$, where we normalize ${0 \in F}$. Then we have a decomposition

$\displaystyle 1_A = 1 - \sum_{f \in F \backslash 0} \varphi_f \ \ \ \ \ (1)$

where each ${\varphi_f: {\bf Z}^d \rightarrow [0,1]}$ is a function that is periodic in the direction ${nf}$, where ${n}$ is the least common multiple of all the primes up to ${|F|}$.

Proof: From Lemma 6 we have ${1_A = 1 - \sum_{f \in F \backslash 0} \delta_{rf} * 1_A}$ for any ${r = 1 \hbox{ mod } n}$, where ${\delta_{rf}}$ is the Kronecker delta at ${rf}$. Now average over ${r}$ (extracting a weak limit or generalised limit as necessary) to obtain the conclusion. $\Box$

The identity (1) turns out to impose a lot of constraints on the functions ${\varphi_f}$, particularly in one and two dimensions. On one hand, one can work modulo ${1}$ to eliminate the ${1_A}$ and ${1}$ terms to obtain the equation

$\displaystyle \sum_{f \in F \backslash 0} \varphi_f = 0 \hbox{ mod } 1$

which in two dimensions in particular puts a lot of structure on each individual ${\varphi_f}$ (roughly speaking it makes the ${\varphi_f \hbox{ mod } 1}$ behave in a polynomial fashion, after collecting commensurable terms). On the other hand we have the inequality

$\displaystyle \sum_{f \in F \backslash 0} \varphi_f \leq 1 \ \ \ \ \ (2)$

which can be used to exclude “equidistributed” polynomial behavior after a certain amount of combinatorial analysis. Only a small amount of further argument is then needed to conclude Theorem 3 and Theorem 2.

For level ${k}$ tilings the analogue of (2) becomes

$\displaystyle \sum_{f \in F \backslash 0} \varphi_f \leq k$

which is a significantly weaker inequality and now no longer seems to prohibit “equidistributed” behavior. After some trial and error we were able to come up with a completely explicit example of a tiling that actually utilises equidistributed polynomials; indeed the tiling set we ended up with was a finite boolean combination of Bohr sets.

We are currently studying what this machinery can tell us about tilings in higher dimensions, focusing initially on the three-dimensional case.

Abdul Basit, Artem Chernikov, Sergei Starchenko, Chiu-Minh Tran and I have uploaded to the arXiv our paper Zarankiewicz’s problem for semilinear hypergraphs. This paper is in the spirit of a number of results in extremal graph theory in which the bounds for various graph-theoretic problems or results can be greatly improved if one makes some additional hypotheses regarding the structure of the graph, for instance by requiring that the graph be “definable” with respect to some theory with good model-theoretic properties.

A basic motivating example is the question of counting the number of incidences between points and lines (or between points and other geometric objects). Suppose one has ${n}$ points and ${n}$ lines in a space. How many incidences can there be between these points and lines? The utterly trivial bound is ${n^2}$, but by using the basic fact that two points determine a line (or two lines intersect in at most one point), a simple application of Cauchy-Schwarz improves this bound to ${n^{3/2}}$. In graph theoretic terms, the point is that the bipartite incidence graph between points and lines does not contain a copy of ${K_{2,2}}$ (there does not exist two points and two lines that are all incident to each other). Without any other further hypotheses, this bound is basically sharp: consider for instance the collection of ${p^2}$ points and ${p^2+p}$ lines in a finite plane ${{\bf F}_p^2}$, that has ${p^3+p^2}$ incidences (one can make the situation more symmetric by working with a projective plane rather than an affine plane). If however one considers lines in the real plane ${{\bf R}^2}$, the famous Szemerédi-Trotter theorem improves the incidence bound further from ${n^{3/2}}$ to ${O(n^{4/3})}$. Thus the incidence graph between real points and lines contains more structure than merely the absence of ${K_{2,2}}$.

More generally, bounding on the size of bipartite graphs (or multipartite hypergraphs) not containing a copy of some complete bipartite subgraph ${K_{k,k}}$ (or ${K_{k,\dots,k}}$ in the hypergraph case) is known as Zarankiewicz’s problem. We have results for all ${k}$ and all orders of hypergraph, but for sake of this post I will focus on the bipartite ${k=2}$ case.

In our paper we improve the ${n^{3/2}}$ bound to a near-linear bound in the case that the incidence graph is “semilinear”. A model case occurs when one considers incidences between points and axis-parallel rectangles in the plane. Now the ${K_{2,2}}$ condition is not automatic (it is of course possible for two distinct points to both lie in two distinct rectangles), so we impose this condition by fiat:

Theorem 1 Suppose one has ${n}$ points and ${n}$ axis-parallel rectangles in the plane, whose incidence graph contains no ${K_{2,2}}$‘s, for some large ${n}$.
• (i) The total number of incidences is ${O(n \log^4 n)}$.
• (ii) If all the rectangles are dyadic, the bound can be improved to ${O( n \frac{\log n}{\log\log n} )}$.
• (iii) The bound in (ii) is best possible (up to the choice of implied constant).

We don’t know whether the bound in (i) is similarly tight for non-dyadic boxes; the usual tricks for reducing the non-dyadic case to the dyadic case strangely fail to apply here. One can generalise to higher dimensions, replacing rectangles by polytopes with faces in some fixed finite set of orientations, at the cost of adding several more logarithmic factors; also, one can replace the reals by other ordered division rings, and replace polytopes by other sets of bounded “semilinear descriptive complexity”, e.g., unions of boundedly many polytopes, or which are cut out by boundedly many functions that enjoy coordinatewise monotonicity properties. For certain specific graphs we can remove the logarithmic factors entirely. We refer to the preprint for precise details.

The proof techniques are combinatorial. The proof of (i) relies primarily on the order structure of ${{\bf R}}$ to implement a “divide and conquer” strategy in which one can efficiently control incidences between ${n}$ points and rectangles by incidences between approximately ${n/2}$ points and boxes. For (ii) there is additional order-theoretic structure one can work with: first there is an easy pruning device to reduce to the case when no rectangle is completely contained inside another, and then one can impose the “tile partial order” in which one dyadic rectangle ${I \times J}$ is less than another ${I' \times J'}$ if ${I \subset I'}$ and ${J' \subset J}$. The point is that this order is “locally linear” in the sense that for any two dyadic rectangles ${R_-, R_+}$, the set ${[R_-,R_+] := \{ R: R_- \leq R \leq R_+\}}$ is linearly ordered, and this can be exploited by elementary double counting arguments to obtain a bound which eventually becomes ${O( n \frac{\log n}{\log\log n})}$ after optimising certain parameters in the argument. The proof also suggests how to construct the counterexample in (iii), which is achieved by an elementary iterative construction.

A family ${A_1,\dots,A_r}$ of sets for some ${r \geq 1}$ is a sunflower if there is a core set ${A_0}$ contained in each of the ${A_i}$ such that the petal sets ${A_i \backslash A_0, i=1,\dots,r}$ are disjoint. If ${k,r \geq 1}$, let ${\mathrm{Sun}(k,r)}$ denote the smallest natural number with the property that any family of ${\mathrm{Sun}(k,r)}$ distinct sets of cardinality at most ${k}$ contains ${r}$ distinct elements ${A_1,\dots,A_r}$ that form a sunflower. The celebrated Erdös-Rado theorem asserts that ${\mathrm{Sun}(k,r)}$ is finite; in fact Erdös and Rado gave the bounds

$\displaystyle (r-1)^k \leq \mathrm{Sun}(k,r) \leq (r-1)^k k! + 1. \ \ \ \ \ (1)$

The sunflower conjecture asserts in fact that the upper bound can be improved to ${\mathrm{Sun}(k,r) \leq O(1)^k r^k}$. 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

$\displaystyle \mathrm{Sun}(k,r) \leq O( r \log(kr) )^k \ \ \ \ \ (2)$

for all ${k,r \geq 2}$, 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 ${k=1}$ or ${r=1}$ in order to make the logarithmic factor ${\log(kr)}$ 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 ${R > 1}$. A random set ${{\bf A}}$ is said to be ${R}$-spread if one has

$\displaystyle {\mathbb P}( S \subset {\bf A}) \leq R^{-|S|}$

for all sets ${S}$. A family ${(A_i)_{i \in I}}$ of sets is said to be ${R}$-spread if ${I}$ is non-empty and the random variable ${A_{\bf i}}$ is ${R}$-spread, where ${{\bf i}}$ is drawn uniformly from ${I}$.

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 ${(A_i)_{i \in I}}$ be a family of subsets of a finite set ${X}$, each of cardinality at most ${k}$, and let ${R > 1}$. Then there exists a “core” set ${S_0}$ of cardinality at most ${k}$ such that the set

$\displaystyle J := \{ i \in I: S_0 \subset A_i \} \ \ \ \ \ (3)$

has cardinality at least ${R^{-|S_0|} |I|}$, and such that the family ${(A_j \backslash S_0)_{j \in J}}$ is ${R}$-spread. Furthermore, if ${|I| > R^k}$ and the ${A_i}$ are distinct, then ${|S_0| < k}$.

Proof: We may assume ${I}$ is non-empty, as the claim is trivial otherwise. For any ${S \subset X}$, define the quantity

$\displaystyle Q(S) := R^{|S|} |\{ i \in I: S \subset A_i\}|,$

and let ${S_0}$ be a subset of ${X}$ that maximizes ${Q(S_0)}$. Since ${Q(\emptyset) = |I| > 0}$ and ${Q(S)=0}$ when ${|S| >k}$, we see that ${0 \leq |S_0| \leq K}$. If the ${A_i}$ are distinct and ${|I| > R^k}$, then we also have ${Q(S) \leq R^k < |I| = Q(\emptyset)}$ when ${|S|=k}$, thus in this case we have ${|S_0| < k}$.

Let ${J}$ be the set (3). Since ${Q(S_0) \geq Q(\emptyset)>0}$, ${J}$ is non-empty. It remains to check that the family ${(A_j \backslash S_0)_{j \in J}}$ is ${R}$-spread. But for any ${S \subset X}$ and ${{\bf j}}$ drawn uniformly at random from ${J}$ one has

$\displaystyle {\mathbb P}( S \subset A_{\bf j} \backslash S_0 ) = \frac{|\{ i \in I: S_0 \cup S \subset A_i\}|}{|\{ i \in I: S_0 \subset A_i\}|} = R^{|S_0|-|S_0 \cup S|} \frac{Q(S)}{Q(S_0)}.$

Since ${Q(S) \leq Q(S_0)}$ and ${|S_0|-|S_0 \cup S| \geq - |S|}$, we obtain the claim $\Box$

In view of the above lemma, the bound (2) will then follow from

Proposition 3 (Locating the petals) Let ${r, k \geq 2}$ be natural numbers, and suppose that ${R \geq C r \log(kr)}$ for a sufficiently large constant ${C}$. Let ${(A_i)_{i \in I}}$ be a finite family of subsets of a finite set ${X}$, each of cardinality at most ${k}$ which is ${R}$-spread. Then there exist ${i_1,\dots,i_r \in I}$ such that ${A_{i_1},\dots,A_{i_r}}$ is disjoint.

Indeed, to prove (2), we assume that ${(A_i)_{i \in I}}$ is a family of sets of cardinality greater than ${R^k}$ for some ${R \geq Cr \log(kr)}$; by discarding redundant elements and sets we may assume that ${I}$ is finite and that all the ${A_i}$ are contained in a common finite set ${X}$. Apply Lemma 2 to find a set ${S_0 \subset X}$ of cardinality ${|S_0| < k}$ such that the family ${(A_j \backslash S_0)_{j \in J}}$ is ${R}$-spread. By Proposition 3 we can find ${j_1,\dots,j_r \in J}$ such that ${A_{j_1} \backslash S_0,\dots,A_{j_r} \backslash S_0}$ are disjoint; since these sets have cardinality ${k - |S_0| > 0}$, this implies that the ${j_1,\dots,j_r}$ are distinct. Hence ${A_{j_1},\dots,A_{j_r}}$ form a sunflower as required.

Remark 4 Proposition 3 is easy to prove if we strengthen the condition on ${R}$ to ${R > k(r-1)}$. In this case, we have ${\mathop{\bf P}_{i \in I}( x \in A_i) < 1/k(r-1)}$ for every ${x \in X}$, hence by the union bound we see that for any ${i_1,\dots,i_j \in I}$ with ${j \leq r-1}$ there exists ${i_{j+1} \in I}$ such that ${A_{i_{j+1}}}$ is disjoint from the set ${A_{i_1} \cup \dots \cup A_{i_j}}$, which has cardinality at most ${k(r-1)}$. Iterating this, we obtain the conclusion of Proposition 3 in this case. This recovers a bound of the form ${\mathrm{Sun}(k,r) \leq (k(r-1))^k+1}$, 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 ${{\bf V}}$ be a random subset of ${X}$, such that each ${x \in X}$ lies in ${{\bf V}}$ with an independent probability of ${1/r}$. Then with probability greater than ${1-1/r}$, ${{\bf V}}$ contains one of the ${A_i}$.

To see that Proposition 5 implies Proposition 3, we randomly partition ${X}$ into ${{\bf V}_1 \cup \dots \cup {\bf V}_r}$ by placing each ${x \in X}$ into one of the ${{\bf V}_j}$, ${j=1,\dots,r}$ 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 ${j=1,\dots,r}$ that each ${{\bf V}_j}$ contains one of the ${A_i}$. Selecting one such ${A_i}$ for each ${{\bf V}_j}$, we obtain the required disjoint petals.

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

Proposition 6 (Refinement inequality) Let ${R > 1}$ and ${0 < \delta < 1}$. Let ${{\bf A}}$ be a random subset of a finite set ${X}$ which is ${R}$-spread, and let ${{\bf V}}$ be a random subset of ${X}$ independent of ${{\bf A}}$, such that each ${x \in X}$ lies in ${{\bf V}}$ with an independent probability of ${\delta}$. Then there exists another random subset ${{\bf A}'}$ of ${X}$ with the same distribution as ${{\bf A}}$, such that ${{\bf A}' \backslash {\bf V} \subset {\bf A}}$ and

$\displaystyle {\mathbb E} |{\bf A}' \backslash {\bf V}| \leq \frac{5}{\log(R\delta)} {\mathbb E} |{\bf A}|.$

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

$\displaystyle {\mathbb E} |{\bf A} \backslash {\bf V}| \leq (1-\delta) {\mathbb E} |{\bf A}|,$

but the point is that by switching from ${{\bf A}}$ to an equivalent ${{\bf A}'}$ we can replace the ${1-\delta}$ factor by a quantity significantly smaller than ${1}$.

One can iterate the above proposition, repeatedly replacing ${{\bf A}, X}$ with ${{\bf A}' \backslash {\bf V}, X \backslash {\bf V}}$ (noting that this preserves the ${R}$-spread nature ${{\bf A}}$) to conclude

Corollary 7 (Iterated refinement inequality) Let ${R > 1}$, ${0 < \delta < 1}$, and ${m \geq 1}$. Let ${{\bf A}}$ be a random subset of a finite set ${X}$ which is ${R}$-spread, and let ${{\bf V}}$ be a random subset of ${X}$ independent of ${{\bf A}}$, such that each ${x \in X}$ lies in ${{\bf V}}$ with an independent probability of ${1-(1-\delta)^m}$. Then there exists another random subset ${{\bf A}'}$ of ${X}$ with the same distribution as ${{\bf A}}$, such that

$\displaystyle {\mathbb E} |{\bf A}' \backslash {\bf V}| \leq (\frac{5}{\log(R\delta)})^m {\mathbb E} |{\bf A}|.$

Now we can prove Proposition 5. Let ${m}$ be chosen shortly. Applying Corollary 7 with ${{\bf A}}$ drawn uniformly at random from the ${(A_i)_{i \in I}}$, and setting ${1-(1-\delta)^m = 1/r}$, or equivalently ${\delta = 1 - (1 - 1/r)^{1/m}}$, we have

$\displaystyle {\mathbb E} |{\bf A}' \backslash {\bf V}| \leq (\frac{5}{\log(R\delta)})^m k.$

In particular, if we set ${m = \lceil \log kr \rceil}$, so that ${\delta \sim \frac{1}{r \log kr}}$, then by choice of ${R}$ we have ${\frac{5}{\log(R\delta)} < \frac{1}{2}}$, hence

$\displaystyle {\mathbb E} |{\bf A}' \backslash {\bf V}| < \frac{1}{r}.$

In particular with probability at least ${1 - \frac{1}{r}}$, there must exist ${A_i}$ such that ${|A_i \backslash {\bf V}| = 0}$, giving the proposition.

It remains to establish Proposition 6. This is the difficult step, and requires a clever way to find the variant ${{\bf A}'}$ of ${{\bf A}}$ that has better containment properties in ${{\bf V}}$ than ${{\bf A}}$ does. The main trick is to make a conditional copy ${({\bf A}', {\bf V}')}$ of ${({\bf A}, {\bf V})}$ that is conditionally independent of ${({\bf A}, {\bf V})}$ subject to the constraint ${{\bf A} \cup {\bf V} = {\bf A}' \cup {\bf V}'}$. The point here is that this constrant implies the inclusions

$\displaystyle {\bf A}' \backslash {\bf V} \subset {\bf A} \cap {\bf A}' \subset \subset {\bf A} \ \ \ \ \ (4)$

and

$\displaystyle {\bf A}' \backslash {\bf A} \subset {\bf V}. \ \ \ \ \ (5)$

Because of the ${R}$-spread hypothesis, it is hard for ${{\bf A}}$ to contain any fixed large set. If we could apply this observation in the contrapositive to ${{\bf A} \cap {\bf A}'}$ we could hope to get a good upper bound on the size of ${{\bf A} \cap {\bf A}'}$ and hence on ${{\bf A} \backslash {\bf V}}$ 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 ${{\bf V}}$ to contain a fixed large set. There are however difficulties with implementing this approach due to the fact that the random sets ${{\bf A} \cap {\bf A}', {\bf A}' \backslash {\bf A}}$ are coupled with ${{\bf A}, {\bf V}}$ 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 thefold 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.)

In the modern theory of additive combinatorics, a large role is played by the Gowers uniformity norms ${\|f\|_{U^k(G)}}$, where ${k \geq 1}$, ${G = (G,+)}$ is a finite abelian group, and ${f: G \rightarrow {\bf C}}$ is a function (one can also consider these norms in finite approximate groups such as ${[N] = \{1,\dots,N\}}$ instead of finite groups, but we will focus on the group case here for simplicity). These norms can be defined by the formula

$\displaystyle \|f\|_{U^k(G)} := (\mathop{\bf E}_{x,h_1,\dots,h_k \in G} \Delta_{h_1} \dots \Delta_{h_k} f(x))^{1/2^k}$

where we use the averaging notation

$\displaystyle \mathop{\bf E}_{x \in A} f(x) := \frac{1}{|A|} \sum_{x \in A} f(x)$

for any non-empty finite set ${A}$ (with ${|A|}$ denoting the cardinality of ${A}$), and ${\Delta_h}$ is the multiplicative discrete derivative operator

$\displaystyle \Delta_h f(x) := f(x+h) \overline{f(x)}.$

One reason why these norms play an important role is that they control various multilinear averages. We give two sample examples here:

Proposition 1 Let ${G = {\bf Z}/N{\bf Z}}$.

• (i) If ${a_1,\dots,a_k}$ are distinct elements of ${G}$ for some ${k \geq 2}$, and ${f_1,\dots,f_k: G \rightarrow {\bf C}}$ are ${1}$-bounded functions (thus ${|f_j(x)| \leq 1}$ for all ${j=1,\dots,k}$ and ${x \in G}$), then

$\displaystyle \mathop{\bf E}_{x, h \in G} f_1(x+a_1 h) \dots f_k(x+a_k h) \leq \|f_i\|_{U^{k-1}(G)} \ \ \ \ \ (1)$

for any ${i=1,\dots,k}$.

• (ii) If ${f_1,f_2,f_3: G \rightarrow {\bf C}}$ are ${1}$-bounded, then one has

$\displaystyle \mathop{\bf E}_{x, h \in G} f_1(x) f_2(x+h) f_3(x+h^2) \ll \|f_3\|_{U^4(G)} + N^{-1/4}.$

We establish these claims a little later in this post.

In some more recent literature (e.g., this paper of Conlon, Fox, and Zhao), the role of Gowers norms have been replaced by (generalisations) of the cut norm, a concept originating from graph theory. In this blog post, it will be convenient to define these cut norms in the language of probability theory (using boldface to denote random variables).

Definition 2 (Cut norm) Let ${{\bf X}_1,\dots,{\bf X}_k, {\bf Y}_1,\dots,{\bf Y}_l}$ be independent random variables with ${k,l \geq 0}$; to avoid minor technicalities we assume that these random variables are discrete and take values in a finite set. Given a random variable ${{\bf F} = F( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}$ of these independent random variables, we define the cut norm

$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} := \sup | \mathop{\bf E} {\bf F} {\bf B}_1 \dots {\bf B}_k |$

where the supremum ranges over all choices ${{\bf B}_1,\dots,{\bf B}_k}$ of random variables ${{\bf B}_i = B_i( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}$ that are ${1}$-bounded (thus ${|{\bf B}_i| \leq 1}$ surely), and such that ${{\bf B}_i}$ does not depend on ${{\bf X}_i}$.

If ${l=0}$, we abbreviate ${\| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}}$ as ${\| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k )}}$.

Strictly speaking, the cut norm is only a cut semi-norm when ${k=0,1}$, but we will abuse notation by referring to it as a norm nevertheless.

Example 3 If ${G = (V_1,V_2,E)}$ is a bipartite graph, and ${\mathbf{v_1}}$, ${\mathbf{v_2}}$ are independent random variables chosen uniformly from ${V_1,V_2}$ respectively, then

$\displaystyle \| 1_E(\mathbf{v_1},\mathbf{v_2}) \|_{\mathrm{CUT}(\mathbf{v_1}, \mathbf{v_2})}$

$\displaystyle = \sup_{\|f\|_\infty, \|g\|_\infty \leq 1} |\mathop{\bf E}_{v_1 \in V_1, v_2 \in V_2} 1_E(v_1,v_2) f(v_1) g(v_2)|$

where the supremum ranges over all ${1}$-bounded functions ${f: V_1 \rightarrow [-1,1]}$, ${g: V_2 \rightarrow [-1,1]}$. The right hand side is essentially the cut norm of the graph ${G}$, as defined for instance by Frieze and Kannan.

The cut norm is basically an expectation when ${k=0,1}$:

Example 4 If ${k=0}$, we see from definition that

$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( ; {\bf Y}_1,\dots,{\bf Y}_l )} =| \mathop{\bf E} {\bf F} |.$

If ${k=1}$, one easily checks that

$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}; {\bf Y}_1,\dots,{\bf Y}_l )} = \mathop{\bf E} | \mathop{\bf E}_{\bf X} {\bf F} |,$

where ${\mathop{\bf E}_{\bf X} {\bf F} = \mathop{\bf E}( {\bf F} | {\bf Y}_1,\dots,{\bf Y}_l )}$ is the conditional expectation of ${{\bf F}}$ to the ${\sigma}$-algebra generated by all the variables other than ${{\bf X}}$, i.e., the ${\sigma}$-algebra generated by ${{\bf Y}_1,\dots,{\bf Y}_l}$. In particular, if ${{\bf X}, {\bf Y}_1,\dots,{\bf Y}_l}$ are independent random variables drawn uniformly from ${X,Y_1,\dots,Y_l}$ respectively, then

$\displaystyle \| F( {\bf X}; {\bf Y}_1,\dots, {\bf Y}_l) \|_{\mathrm{CUT}( {\bf X}; {\bf Y}_1,\dots,{\bf Y}_l )}$

$\displaystyle = \mathop{\bf E}_{y_1 \in Y_1,\dots, y_l \in Y_l} |\mathop{\bf E}_{x \in X} F(x; y_1,\dots,y_l)|.$

Here are some basic properties of the cut norm:

Lemma 5 (Basic properties of cut norm) Let ${{\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l}$ be independent discrete random variables, and ${{\bf F} = F({\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l)}$ a function of these variables.

• (i) (Permutation invariance) The cut norm ${\| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}}$ is invariant with respect to permutations of the ${{\bf X}_1,\dots,{\bf X}_k}$, or permutations of the ${{\bf Y}_1,\dots,{\bf Y}_l}$.
• (ii) (Conditioning) One has

$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} = \mathop{\bf E} \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k )}$

where on the right-hand side we view, for each realisation ${y_1,\dots,y_l}$ of ${{\bf Y}_1,\dots,{\bf Y}_l}$, ${{\bf F}}$ as a function ${F( {\bf X}_1,\dots,{\bf X}_k; y_1,\dots,y_l)}$ of the random variables ${{\bf X}_1,\dots, {\bf X}_k}$ alone, thus the right-hand side may be expanded as

$\displaystyle \sum_{y_1,\dots,y_l} \| F( {\bf X}_1,\dots,{\bf X}_k; y_1,\dots,y_l) \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k )}$

$\displaystyle \times \mathop{\bf P}( Y_1=y_1,\dots,Y_l=y_l).$

• (iii) (Monotonicity) If ${k \geq 1}$, we have

$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} \geq \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_{k-1}; {\bf X}_k, {\bf Y}_1,\dots,{\bf Y}_l )}.$

• (iv) (Multiplicative invariances) If ${{\bf B} = B({\bf X}_1,\dots,{\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l)}$ is a ${1}$-bounded function that does not depend on one of the ${{\bf X}_i}$, then

$\displaystyle \| {\bf B} {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} \leq \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}.$

In particular, if we additionally assume ${|{\bf B}|=1}$, then

$\displaystyle \| {\bf B} {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} = \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}.$

• (v) (Cauchy-Schwarz) If ${k \geq 1}$, one has

$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} \leq \| \Box_{{\bf X}_1, {\bf X}'_1} {\bf F} \|_{\mathrm{CUT}( {\bf X}_2, \dots, {\bf X}_k; {\bf X}_1, {\bf X}'_1, {\bf Y}_1,\dots,{\bf Y}_l )}^{1/2}$

where ${{\bf X}'_1}$ is a copy of ${{\bf X}_1}$ that is independent of ${{\bf X}_1,\dots,{\bf X}_k,{\bf Y}_1,\dots,{\bf Y}_l}$ and ${\Box_{{\bf X}_1, {\bf X}'_1} {\bf F}}$ is the random variable

$\displaystyle \Box_{{\bf X}_1, {\bf X}'_1} {\bf F} := F( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )$

$\displaystyle \times \overline{F}( {\bf X}'_1, {\bf X}_2, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l ).$

• (vi) (Averaging) If ${k \geq 1}$ and ${{\bf F} = \mathop{\bf E}_{\bf Z} {\bf F}_{\bf Z}}$, where ${{\bf Z}}$ is another random variable independent of ${{\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l}$, and ${{\bf F}_{\bf Z} = F_{\bf Z}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}$ is a random variable depending on both ${{\bf Z}}$ and ${{\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l}$, then

$\displaystyle \| {\bf F} \|_{\mathrm{CUT}( {\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )} \leq \| {\bf F}_{\bf Z} \|_{\mathrm{CUT}( ({\bf X}_1, {\bf Z}), {\bf X}_2, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l )}$

Proof: The claims (i), (ii) are clear from expanding out all the definitions. The claim (iii) also easily follows from the definitions (the left-hand side involves a supremum over a more general class of multipliers ${{\bf B}_1,\dots,{\bf B}_{k}}$, while the right-hand side omits the ${{\bf B}_k}$ multiplier), as does (iv) (the multiplier ${{\bf B}}$ can be absorbed into one of the multipliers in the definition of the cut norm). The claim (vi) follows by expanding out the definitions, and observing that all of the terms in the supremum appearing in the left-hand side also appear as terms in the supremum on the right-hand side. It remains to prove (v). By definition, the left-hand side is the supremum over all quantities of the form

$\displaystyle |{\bf E} {\bf F} {\bf B}_1 \dots {\bf B}_k|$

where the ${{\bf B}_i}$ are ${1}$-bounded functions of ${{\bf X}_1, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l}$ that do not depend on ${{\bf X}_i}$. We average out in the ${{\bf X}_1}$ direction (that is, we condition out the variables ${{\bf X}_2, \dots, {\bf X}_k; {\bf Y}_1,\dots,{\bf Y}_l}$), and pull out the factor ${{\bf B}_1}$ (which does not depend on ${{\bf X}_1}$), to write this as

$\displaystyle |{\bf E} {\bf B}_1 {\bf E}_{{\bf X}_1}( {\bf F} {\bf B}_2 \dots {\bf B}_k )|,$

which by Cauchy-Schwarz is bounded by

$\displaystyle ( |{\bf E} |{\bf E}_{{\bf X}_1}( {\bf F} {\bf B}_2 \dots {\bf B}_k )|^2)^{1/2},$

which can be expanded using the copy ${{\bf X}_1}$ as

$\displaystyle |{\bf E} \Box_{{\bf X}_1,{\bf X}'_1} ({\bf F} {\bf B}_2 \dots {\bf B}_k) |^{1/2}.$

Expanding

$\displaystyle \Box_{{\bf X}_1,{\bf X}'_1} ({\bf F} {\bf B}_2 \dots {\bf B}_k) = (\Box_{{\bf X}_1,{\bf X}'_1} {\bf F}) (\Box_{{\bf X}_1,{\bf X}'_1} {\bf B}_2) \dots (\Box_{{\bf X}_1,{\bf X}'_1} {\bf B}_k)$

and noting that each ${\Box_{{\bf X}_1,{\bf X}'_1} {\bf B}_i}$ is ${1}$-bounded and independent of ${{\bf X}_i}$ for ${i=2,\dots,k}$, we obtain the claim. $\Box$

Now we can relate the cut norm to Gowers uniformity norms:

Lemma 6 Let ${G}$ be a finite abelian group, let ${{\bf x}, {\bf h}_1,\dots,{\bf h}_k}$ be independent random variables uniformly drawn from ${G}$ for some ${k \geq 0}$, and let ${f: G \rightarrow {\bf C}}$. Then

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h}_1,\dots,{\bf h}_k, {\bf x} )} \leq \|f\|_{U^{k+1}(G)} \ \ \ \ \ (2)$

and similarly (if ${k \geq 1}$)

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h}_1,\dots,{\bf h}_k; {\bf x} )} \leq \|f\|_{U^{k}(G)} \ \ \ \ \ (3)$

If ${f}$ is additionally assumed to be ${1}$-bounded, we have the converse inequalities

$\displaystyle \|f\|_{U^{k+1}(G)}^{2^{k+1}} \leq \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h}_1,\dots,{\bf h}_k, {\bf x} )} \ \ \ \ \ (4)$

and (if ${k \geq 1}$)

$\displaystyle \|f\|_{U^{k}(G)}^{2^{k}} \leq \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h}_1,\dots,{\bf h}_k; {\bf x} )}. \ \ \ \ \ (5)$

Proof: Applying Lemma 5(v) ${k}$ times, we can bound

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h_1},\dots,{\bf h_k}, {\bf x} )}$

by

$\displaystyle \| \Box_{{\bf h}_k,{\bf h}'_k} \dots \Box_{{\bf h}_1,{\bf h}'_1} (f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k)) \|_{\mathrm{CUT}( {\bf x}; {\bf h}_1, {\bf h}'_1, \dots, {\bf h}_k, {\bf h}'_k )}^{1/2^k} \ \ \ \ \ (6)$

where ${{\bf h}'_1,\dots,{\bf h}'_k}$ are independent copies of ${{\bf h}_1,\dots,{\bf h}_k}$ that are also independent of ${{\bf x}}$. The expression inside the norm can also be written as

$\displaystyle \Delta_{{\bf h}_k - {\bf h}'_k} \dots \Delta_{{\bf h}_1 - {\bf h}'_1} f({\bf x} + {\bf h}'_1 + \dots + {\bf h}'_k)$

so by Example 4 one can write (6) as

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k,h'_1,\dots,h'_k \in G} |\mathop{\bf E}_{x \in G} \Delta_{h_k - h'_k} \dots \Delta_{h_1 - h'_1} f(x+h'_1+\dots+h'_k)||^{1/2^k}$

which after some change of variables simplifies to

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k \in G} |\mathop{\bf E}_{x \in G} \Delta_{h_k} \dots \Delta_{h_1} f(x)||^{1/2^k}$

which by Cauchy-Schwarz is bounded by

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k \in G} |\mathop{\bf E}_{x \in G} \Delta_{h_k} \dots \Delta_{h_1} f(x)|^2|^{1/2^{k+1}}$

which one can rearrange as

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k,h_{k+1},x \in G} \Delta_{h_{k+1}} \Delta_{h_k} \dots \Delta_{h_1} f(x)|^{1/2^{k+1}}$

giving (2). A similar argument bounds

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_k) \|_{\mathrm{CUT}( {\bf h_1},\dots,{\bf h_k}; {\bf x} )}$

by

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k \in G} \mathop{\bf E}_{x \in G} \Delta_{h_k} \dots \Delta_{h_1} f(x)|^{1/2^k}$

which gives (3).

For (4), we can reverse the above steps and expand ${\|f\|_{U^{k+1}(G)}^{2^{k+1}}}$ as

$\displaystyle \mathop{\bf E}_{h_1,\dots,h_k \in G} |\mathop{\bf E}_{x \in G} \Delta_{h_k} \dots \Delta_{h_1} f(x)|^2$

which we can write as

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k \in G} b(h_1,\dots,h_k) \mathop{\bf E}_{x \in G} \Delta_{h_k} \dots \Delta_{h_1} f(x)|$

for some ${1}$-bounded function ${b}$. This can in turn be expanded as

$\displaystyle |\mathop{\bf E}_{h_1,\dots,h_k,x \in G} f(x+h_1+\dots+h_k) b(h_1,\dots,h_k) \prod_{i=1}^k b_i(x,h_1,\dots,h_k)|$

for some ${1}$-bounded functions ${b_i}$ that do not depend on ${h_i}$. By Example 4, this can be written as

$\displaystyle \| f({\bf x} + {\bf h_1}+\dots+{\bf h}_k) b({\bf h}_1,\dots,{\bf h}_k) \prod_{i=1}^k b_i(x,h_1,\dots,h_k) \|_{\mathrm{CUT}(; {\bf h}_1,\dots,{\bf h}_k, {\bf x})}$

which by several applications of Theorem 5(iii) and then Theorem 5(iv) can be bounded by

$\displaystyle \| f({\bf x} + {\bf h_1}+\dots+{\bf h}_k) \|_{\mathrm{CUT}( {\bf h}_1,\dots,{\bf h}_k, {\bf x})},$

giving (4). A similar argument gives (5). $\Box$

Now we can prove Proposition 1. We begin with part (i). By permutation we may assume ${i=k}$, then by translation we may assume ${a_k=0}$. Replacing ${x}$ by ${x+h_1+\dots+h_{k-1}}$ and ${h}$ by ${h - a_1^{-1} h_1 - \dots - a_{k-1}^{-1} h_{k-1}}$, we can write the left-hand side of (1) as

$\displaystyle \mathop{\bf E}_{x,h,h_1,\dots,h_{k-1} \in G} f_k(x+h_1+\dots+h_{k-1}) \prod_{i=1}^{k-1} b_i(x,h,h_1,\dots,h_{k-1})$

where

$\displaystyle b_i(x,h,h_1,\dots,h_{k-1})$

$\displaystyle := f_i( x + h_1+\dots+h_{k-1}+ a_i(h - a_1^{-1} h_1 - \dots - a_k^{-1} h_{k-1}))$

is a ${1}$-bounded function that does not depend on ${h_i}$. Taking ${{\bf x}, {\bf h}, {\bf h}_1,\dots,{\bf h}_k}$ to be independent random variables drawn uniformly from ${G}$, the left-hand side of (1) can then be written as

$\displaystyle \mathop{\bf E} f_k({\bf x}+{\bf h}_1+\dots+{\bf h}_{k-1}) \prod_{i=1}^{k-1} b_i({\bf x},{\bf h},{\bf h}_1,\dots,{\bf h}_{k-1})$

which by Example 4 is bounded in magnitude by

$\displaystyle \| f_k({\bf x}+{\bf h}_1+\dots+{\bf h}_{k-1}) \prod_{i=1}^{k-1} b_i({\bf x},{\bf h},{\bf h}_1,\dots,{\bf h}_{k-1}) \|_{\mathrm{CUT}(; {\bf h}_1,\dots,{\bf h}_{k-1}, {\bf x}, {\bf h})}.$

After many applications of Lemma 5(iii), (iv), this is bounded by

$\displaystyle \| f_k({\bf x}+{\bf h_1}+\dots+{\bf h_{k-1}}) \|_{\mathrm{CUT}({\bf h}_1,\dots,{\bf h}_{k-1}; {\bf x}, {\bf h})}$

By Lemma 5(ii) we may drop the ${{\bf h}}$ variable, and then the claim follows from Lemma 6.

For part (ii), we replace ${x}$ by ${x+a-h^2}$ and ${h}$ by ${h-a+b}$ to write the left-hand side as

$\displaystyle \mathop{\bf E}_{x, a,b,h \in G} f_1(x+a-h^2) f_2(x+h+b-h^2) f_3(x+a+(h-a+b)^2-h^2);$

the point here is that the first factor does not involve ${b}$, the second factor does not involve ${a}$, and the third factor has no quadratic terms in ${h}$. Letting ${{\bf x}, {\bf a}, {\bf b}, {\bf h}}$ be independent variables drawn uniformly from ${G}$, we can use Example 4 to bound this in magnitude by

$\displaystyle \| f_1({\bf x}+{\bf a}-{\bf h}^2) f_2({\bf x}+{\bf h}+{\bf b}-{\bf h}^2)$

$\displaystyle f_3( {\bf x}+{\bf a}+({\bf h}-{\bf a}+{\bf b})^2-{\bf h}^2 ) \|_{\mathrm{CUT}(; {\bf x}, {\bf a}, {\bf b}, {\bf h})}$

which by Lemma 5(i),(iii),(iv) is bounded by

$\displaystyle \| f_3( {\bf x}+{\bf a}+({\bf h}-{\bf a}+{\bf b})^2 - {\bf h}^2 ) \|_{\mathrm{CUT}({\bf a}, {\bf b}; {\bf x}, {\bf h})}$

and then by Lemma 5(v) we may bound this by

$\displaystyle \| \Box_{{\bf a}, {\bf a}'} \Box_{{\bf b}, {\bf b}'} f_3( {\bf x}+{\bf a}+({\bf h}-{\bf a}+{\bf b})^2 - {\bf h}^2 ) \|_{\mathrm{CUT}(;{\bf a}, {\bf a}', {\bf b}, {\bf b}', {\bf x}, {\bf h})}^{1/4}$

which by Example 4 is

$\displaystyle |\mathop{\bf E} \Box_{{\bf a}, {\bf a}'} \Box_{{\bf b}, {\bf b}'} f_3( {\bf x}+{\bf a}+({\bf h}-{\bf a}+{\bf b})^2 - {\bf h}^2 )|^{1/4}$

Now the expression inside the expectation is the product of four factors, each of which is ${f_3}$ or ${\overline{f}_3}$ applied to an affine form ${{\bf x} + {\bf c} + {\bf a} {\bf h}}$ where ${{\bf c}}$ depends on ${{\bf a}, {\bf a}', {\bf b}, {\bf b}'}$ and ${{\bf a}}$ is one of ${2({\bf b}-{\bf a})}$, ${2({\bf b}'-{\bf a})}$, ${2({\bf b}-{\bf a}')}$, ${2({\bf b}'-{\bf a}')}$. With probability ${1-O(1/N)}$, the four different values of ${{\bf a}}$ are distinct, and then by part (i) we have

$\displaystyle |\mathop{\bf E}(\Box_{{\bf a}, {\bf a}'} \Box_{{\bf b}, {\bf b}'} f_3( {\bf x}+{\bf a}+({\bf h}-{\bf a}+{\bf b})^2 - {\bf h}^2 )|{\bf a}, {\bf a}', {\bf b}, {\bf b}')| \leq \|f_3\|_{U^4({\bf Z}/N{\bf Z})}.$

When they are not distinct, we can instead bound this quantity by ${1}$. Taking expectations in ${{\bf a}, {\bf a}', {\bf b}, {\bf b}'}$, we obtain the claim. $\Box$

The analogue of the inverse ${U^2}$ theorem for cut norms is the following claim (which I learned from Ben Green):

Lemma 7 (${U^2}$-type inverse theorem) Let ${\mathbf{x}, \mathbf{h}}$ be independent random variables drawn from a finite abelian group ${G}$, and let ${f: G \rightarrow {\bf C}}$ be ${1}$-bounded. Then we have

$\displaystyle \| f(\mathbf{x} + \mathbf{h}) \|_{\mathrm{CUT}(\mathbf{x}, \mathbf{h})} = \sup_{\xi \in\hat G} \| f(\mathbf{x}) e(\xi \cdot \mathbf{x}) \|_{\mathrm{CUT}(\mathbf{x})}$

where ${\hat G}$ is the group of homomorphisms ${\xi: x \mapsto \xi \cdot x}$ is a homomorphism from ${G}$ to ${{\bf R}/{\bf Z}}$, and ${e(\theta) := e^{2\pi i \theta}}$.

Proof: Suppose first that ${\| f(\mathbf{x} + \mathbf{h}) \|_{\mathrm{CUT}(\mathbf{x}, \mathbf{h})} > \delta}$ for some ${\delta}$, then by definition

$\displaystyle |\mathop{\bf E}_{x,h \in G} f(x+h) a(x) b(h)| > \delta$

for some ${1}$-bounded ${a,b: G \rightarrow {\bf C}}$. By Fourier expansion, the left-hand side is also

$\displaystyle \sum_{\xi \in \hat G} \hat f(-\xi) \hat a(\xi) \hat b(\xi)$

where ${\hat f(\xi) := \mathop{\bf E}_{x \in G} f(x) e(-\xi \cdot x)}$. From Plancherel’s theorem we have

$\displaystyle \sum_{\xi \in \hat G} |\hat a(\xi)|^2, \sum_{\xi \in \hat G} |\hat b(\xi)|^2 \leq 1$

hence by Hölder’s inequality one has ${|\hat f(-\xi)| > \delta}$ for some ${\xi \in \hat G}$, and hence

$\displaystyle \sup_{\xi \in\hat G} \| f(\mathbf{x}) e(\xi \cdot \mathbf{x}) \|_{\mathrm{CUT}(\mathbf{x})} > \delta. \ \ \ \ \ (7)$

Conversely, suppose (7) holds. Then there is ${\xi \in \hat G}$ such that

$\displaystyle \| f(\mathbf{x}) e(\xi \cdot \mathbf{x}) \|_{\mathrm{CUT}(\mathbf{x})} > \delta$

which on substitution and Example 4 implies

$\displaystyle \| f(\mathbf{x}+\mathbf{h}) e(\xi \cdot (\mathbf{x}+\mathbf{h})) \|_{\mathrm{CUT}(;\mathbf{x}, \mathbf{h})} > \delta.$

The term ${e(\xi \cdot (\mathbf{x}+\mathbf{h}))}$ splits into the product of a factor ${e(\xi \cdot \mathbf{x})}$ not depending on ${\mathbf{h}}$, and a factor ${e(\xi \cdot \mathbf{h})}$ not depending on ${\mathbf{x}}$. Applying Lemma 5(iii), (iv) we conclude that

$\displaystyle \| f(\mathbf{x}+\mathbf{h}) \|_{\mathrm{CUT}(\mathbf{x}, \mathbf{h})} > \delta.$

The claim follows. $\Box$

The higher order inverse theorems are much less trivial (and the optimal quantitative bounds are not currently known). However, there is a useful degree lowering argument, due to Peluse and Prendiville, that can allow one to lower the order of a uniformity norm in some cases. We give a simple version of this argument here:

Lemma 8 (Degree lowering argument, special case) Let ${G}$ be a finite abelian group, let ${Y}$ be a non-empty finite set, and let ${f: G \rightarrow {\bf C}}$ be a function of the form ${f(x) := \mathop{\bf E}_{y \in Y} F_y(x)}$ for some ${1}$-bounded functions ${F_y: G \rightarrow {\bf C}}$ indexed by ${y \in Y}$. Suppose that

$\displaystyle \|f\|_{U^k(G)} \geq \delta$

for some ${k \geq 2}$ and ${0 < \delta \leq 1}$. Then one of the following claims hold (with implied constants allowed to depend on ${k}$):

• (i) (Degree lowering) one has ${\|f\|_{U^{k-1}(G)} \gg \delta^{O(1)}}$.
• (ii) (Non-zero frequency) There exist ${h_1,\dots,h_{k-2} \in G}$ and non-zero ${\xi \in \hat G}$ such that

$\displaystyle |\mathop{\bf E}_{x \in G, y \in Y} \Delta_{h_1} \dots \Delta_{h_{k-2}} F_y(x) e( \xi \cdot x )| \gg \delta^{O(1)}.$

There are more sophisticated versions of this argument in which the frequency ${\xi}$ is “minor arc” rather than “zero frequency”, and then the Gowers norms are localised to suitable large arithmetic progressions; this is implicit in the above-mentioned paper of Peluse and Prendiville.

Proof: One can write

$\displaystyle \|f\|_{U^k(G)}^{2^k} = \mathop{\bf E}_{h_1,\dots,h_{k-2} \in G} \|\Delta_{h_1} \dots \Delta_{h_{k-2}} f \|_{U^2(G)}^4$

and hence we conclude that

$\displaystyle \|\Delta_{h_1} \dots \Delta_{h_{k-2}} f \|_{U^2(G)} \gg \delta^{O(1)}$

for a set ${\Sigma}$ of tuples ${(h_1,\dots,h_{k-2}) \in G^{k-2}}$ of density ${h_1,\dots,h_{k-2}}$. Applying Lemma 6 and Lemma 7, we see that for each such tuple, there exists ${\phi(h_1,\dots,h_{k-2}) \in \hat G}$ such that

$\displaystyle \| \Delta_{h_1} \dots \Delta_{h_{k-2}} f({\bf x}) e( \phi(h_1,\dots,h_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x})} \gg \delta^{O(1)}, \ \ \ \ \ (8)$

where ${{\bf x}}$ is drawn uniformly from ${G}$.

Let us adopt the convention that ${e( \phi( _1,\dots,h_{k-2}) \cdot {\bf x} ) }$ vanishes for ${(h_1,\dots,h_{k-2})}$ not in ${\Sigma}$, then from Lemma 5(ii) we have

$\displaystyle \| \Delta_{{\bf h}_1} \dots \Delta_{{\bf h}_{k-2}} f({\bf x}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x}; {\bf h}_1,\dots, {\bf h}_{k-2})} \gg \delta^{O(1)},$

where ${{\bf h}_1,\dots,{\bf h}_{k-2}}$ are independent random variables drawn uniformly from ${G}$ and also independent of ${{\bf x}}$. By repeated application of Lemma 5(iii) we then have

$\displaystyle \| \Delta_{{\bf h}_1} \dots \Delta_{{\bf h}_{k-2}} f({\bf x}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x},{\bf h}_1,\dots, {\bf h}_{k-2})} \gg \delta^{O(1)}.$

Expanding out ${\Delta_{h_1} \dots \Delta_{h_{k-2}} f({\bf x})}$ and using Lemma 5(iv) repeatedly we conclude that

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x},{\bf h}_1,\dots, {\bf h}_{k-2})} \gg \delta^{O(1)}.$

From definition of ${f}$ we then have

$\displaystyle \| {\bf E}_{y \in Y} F_y({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x},{\bf h}_1,\dots, {\bf h}_{k-2})}$

$\displaystyle \gg \delta^{O(1)}.$

By Lemma 5(vi), we see that the left-hand side is less than

$\displaystyle \| F_{\bf y}({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}(({\bf x}, {\bf y}),{\bf h}_1,\dots, {\bf h}_{k-2})},$

where ${{\bf y}}$ is drawn uniformly from ${Y}$, independently of ${{\bf x}, {\bf h}_1,\dots,{\bf h}_{k-2}}$. By repeated application of Lemma 5(i), (v) repeatedly, we conclude that

$\displaystyle \| \Box_{{\bf h}_1, {\bf h}'_1} \dots \Box_{{\bf h}_{k-2}, {\bf h}'_{k-2}} (F_{\bf y}({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} )) \|_{\mathrm{CUT}(({\bf x},{\bf y}); {\bf h}_1,{\bf h}'_1,\dots, {\bf h}_{k-2}, {\bf h}'_{k-2})} \gg \delta^{O(1)},$

where ${{\bf h}'_1,\dots,{\bf h}'_{k-2}}$ are independent copies of ${{\bf h}_1,\dots,{\bf h}_{k-2}}$ that are also independent of ${{\bf x}}$, ${{\bf y}}$. By Lemma 5(ii) and Example 4 we conclude that

$\displaystyle |\mathop{\bf E}( \Box_{{\bf h}_1, {\bf h}'_1} \dots \Box_{{\bf h}_{k-2}, {\bf h}'_{k-2}} (F_{\bf y}({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) e( \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} )) | {\bf h}_1,{\bf h}'_1,\dots, {\bf h}_{k-2}, {\bf h}'_{k-2}) )| \gg \delta^{O(1)} \ \ \ \ \ (9)$

with probability ${\gg \delta^{O(1)}}$.

The left-hand side can be rewritten as

$\displaystyle |\mathop{\bf E}_{x \in G, y \in Y} \Delta_{{\bf h}_1 - {\bf h}'_1} \dots \Delta_{{\bf h}_{k-2} - {\bf h}'_{k-2}} F_y( x + {\bf h}'_1 + \dots + {\bf h}'_{k-2})$

$\displaystyle e( \delta_{{\bf h}_1, {\bf h}'_1} \dots \delta_{{\bf h}_{k-2}, {\bf h}'_{k-2}} \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot x )|$

where ${\delta_{{\bf h}_1, {\bf h}'_1}}$ is the additive version of ${\Box_{{\bf h}_1, {\bf h}'_1}}$, thus

$\displaystyle \delta_{{\bf h}_1, {\bf h}'_1} \phi({\bf h}_1,\dots,{\bf h}_{k-2}) := \phi({\bf h}_1,\dots,{\bf h}_{k-2}) - \phi({\bf h}'_1,\dots,{\bf h}_{k-2}).$

Translating ${x}$, we can simplify this a little to

$\displaystyle |\mathop{\bf E}_{x \in G, y \in Y} \Delta_{{\bf h}_1 - {\bf h}'_1} \dots \Delta_{{\bf h}_k - {\bf h}'_k} F_y( x ) e( \delta_{{\bf h}_1, {\bf h}'_1} \dots \delta_{{\bf h}_{k-2}, {\bf h}'_{k-2}} \phi({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot x )|$

If the frequency ${\delta_{{\bf h}_1, {\bf h}'_1} \dots \delta_{{\bf h}_{k-2}, {\bf h}'_{k-2}} \phi({\bf h}_1,\dots,{\bf h}_{k-2})}$ is ever non-vanishing in the event (9) then conclusion (ii) applies. We conclude that

$\displaystyle \delta_{{\bf h}_1, {\bf h}'_1} \dots \delta_{{\bf h}_{k-2}, {\bf h}'_{k-2}} \phi({\bf h}_1,\dots,{\bf h}_{k-2}) = 0$

with probability ${\gg \delta^{O(1)}}$. In particular, by the pigeonhole principle, there exist ${h'_1,\dots,h'_{k-2} \in G}$ such that

$\displaystyle \delta_{{\bf h}_1, h'_1} \dots \delta_{{\bf h}_{k-2}, h'_{k-2}} \phi({\bf h}_1,\dots,{\bf h}_{k-2}) = 0$

with probability ${\gg \delta^{O(1)}}$. Expanding this out, we obtain a representation of the form

$\displaystyle \phi({\bf h}_1,\dots,{\bf h}_{k-2}) = \sum_{i=1}^{k-2} \phi_i({\bf h}_1,\dots,{\bf h}_{k-2})$

holding with probability ${\gg \delta^{O(1)}}$, where the ${\phi_i: G^{k-2} \rightarrow {\bf R}/{\bf Z}}$ are functions that do not depend on the ${i^{th}}$ coordinate. From (8) we conclude that

$\displaystyle \| \Delta_{h_1} \dots \Delta_{h_{k-2}} f({\bf x}) e( \sum_{i=1}^{k-2} \phi_i(h_1,\dots,h_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x})} \gg \delta^{O(1)}$

for ${\gg \delta^{O(1)}}$ of the tuples ${(h_1,\dots,h_{k-2}) \in G^{k-2}}$. Thus by Lemma 5(ii)

$\displaystyle \| \Delta_{{\bf h}_1} \dots \Delta_{{\bf h}_{k-2}} f({\bf x}) e( \sum_{i=1}^{k-2} \phi_i({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x}; {\bf h}_1,\dots,{\bf h}_{k-2})} \gg \delta^{O(1)}.$

By repeated application of Lemma 5(iii) we then have

$\displaystyle \| \Delta_{{\bf h}_1} \dots \Delta_{{\bf h}_{k-2}} f({\bf x}) e( \sum_{i=1}^{k-2} \phi_i({\bf h}_1,\dots,{\bf h}_{k-2}) \cdot {\bf x} ) \|_{\mathrm{CUT}({\bf x}, {\bf h}_1,\dots,{\bf h}_{k-2})} \gg \delta^{O(1)}$

and then by repeated application of Lemma 5(iv)

$\displaystyle \| f({\bf x} + {\bf h}_1 + \dots + {\bf h}_{k-2}) \|_{\mathrm{CUT}({\bf x}, {\bf h}_1,\dots,{\bf h}_{k-2})} \gg \delta^{O(1)}$

and then the conclusion (i) follows from Lemma 6. $\Box$

As an application of degree lowering, we give an inverse theorem for the average in Proposition 1(ii), first established by Bourgain-Chang and later reproved by Peluse (by different methods from those given here):

Proposition 9 Let ${G = {\bf Z}/N{\bf Z}}$ be a cyclic group of prime order. Suppose that one has ${1}$-bounded functions ${f_1,f_2,f_3: G \rightarrow {\bf C}}$ such that

$\displaystyle |\mathop{\bf E}_{x, h \in G} f_1(x) f_2(x+h) f_3(x+h^2)| \geq \delta \ \ \ \ \ (10)$

for some ${\delta > 0}$. Then either ${N \ll \delta^{-O(1)}}$, or one has

$\displaystyle |\mathop{\bf E}_{x \in G} f_1(x)|, |\mathop{\bf E}_{x \in G} f_2(x)| \gg \delta^{O(1)}.$

We remark that a modification of the arguments below also give ${|\mathop{\bf E}_{x \in G} f_3(x)| \gg \delta^{O(1)}}$.

Proof: The left-hand side of (10) can be written as

$\displaystyle |\mathop{\bf E}_{x \in G} F(x) f_3(x)|$

where ${F}$ is the dual function

$\displaystyle F(x) := \mathop{\bf E}_{h \in G} f_1(x-h^2) f_2(x-h^2+h).$

By Cauchy-Schwarz one thus has

$\displaystyle |\mathop{\bf E}_{x \in G} F(x) \overline{F}(x)| \geq \delta^2$

and hence by Proposition 1, we either have ${N \ll \delta^{-O(1)}}$ (in which case we are done) or

$\displaystyle \|F\|_{U^4(G)} \gg \delta^2.$

Writing ${F = \mathop{\bf E}_{h \in G} F_h}$ with ${F_h(x) := f_1(x-h^2) f_2(x-h^2+h)}$, we conclude that either ${\|F\|_{U^3(G)} \gg \delta^{O(1)}}$, or that

$\displaystyle |\mathop{\bf E}_{x,h \in G} \Delta_{h_1} \Delta_{h_2} F_h(x) e(\xi x / N )| \gg \delta^{O(1)}$

for some ${h_1,h_2 \in G}$ and non-zero ${\xi \in G}$. The left-hand side can be rewritten as

$\displaystyle |\mathop{\bf E}_{x,h \in G} g_1(x-h^2) g_2(x-h^2+h) e(\xi x/N)|$

where ${g_1 = \Delta_{h_1} \Delta_{h_2} f_1}$ and ${g_2 = \Delta_{h_1} \Delta_{h_2} f_2}$. We can rewrite this in turn as

$\displaystyle |\mathop{\bf E}_{x,y \in G} g_1(x) g_2(y) e(\xi (x + (y-x)^2) / N)|$

which is bounded by

$\displaystyle \| e(\xi({\bf x} + ({\bf y}-{\bf x})^2)/N) \|_{\mathrm{CUT}({\bf x}, {\bf y})}$

where ${{\bf x}, {\bf y}}$ are independent random variables drawn uniformly from ${G}$. Applying Lemma 5(v), we conclude that

$\displaystyle \| \Box_{{\bf y}, {\bf y}'} e(\xi({\bf x} + ({\bf y}-{\bf x})^2)/N) \|_{\mathrm{CUT}({\bf x}; {\bf y}, {\bf y}')} \gg \delta^{O(1)}.$

However, a routine Gauss sum calculation reveals that the left-hand side is ${O(N^{-c})}$ for some absolute constant ${c>0}$ because ${\xi}$ is non-zero, so that ${N \ll \delta^{-O(1)}}$. The only remaining case to consider is when

$\displaystyle \|F\|_{U^3(G)} \gg \delta^{O(1)}.$

Repeating the above arguments we then conclude that

$\displaystyle \|F\|_{U^2(G)} \gg \delta^{O(1)},$

and then

$\displaystyle \|F\|_{U^1(G)} \gg \delta^{O(1)}.$

The left-hand side can be computed to equal ${|\mathop{\bf E}_{x \in G} f_1(x)| |\mathop{\bf E}_{x \in G} f_2(x)|}$, and the claim follows. $\Box$

This argument was given for the cyclic group setting, but the argument can also be applied to the integers (see Peluse-Prendiville) and can also be used to establish an analogue over the reals (that was first obtained by Bourgain).

Define the Collatz map ${\mathrm{Col}: {\bf N}+1 \rightarrow {\bf N}+1}$ on the natural numbers ${{\bf N}+1 = \{1,2,\dots\}}$ by setting ${\mathrm{Col}(N)}$ to equal ${3N+1}$ when ${N}$ is odd and ${N/2}$ when ${N}$ is even, and let ${\mathrm{Col}^{\bf N}(N) := \{ N, \mathrm{Col}(N), \mathrm{Col}^2(N), \dots \}}$ denote the forward Collatz orbit of ${N}$. The notorious Collatz conjecture asserts that ${1 \in \mathrm{Col}^{\bf N}(N)}$ for all ${N \in {\bf N}+1}$. Equivalently, if we define the backwards Collatz orbit ${(\mathrm{Col}^{\bf N})^*(N) := \{ M \in {\bf N}+1: N \in \mathrm{Col}^{\bf N}(M) \}}$ to be all the natural numbers ${M}$ that encounter ${N}$ in their forward Collatz orbit, then the Collatz conjecture asserts that ${(\mathrm{Col}^{\bf N})^*(1) = {\bf N}+1}$. As a partial result towards this latter statement, Krasikov and Lagarias in 2003 established the bound

$\displaystyle \# \{ N \leq x: N \in (\mathrm{Col}^{\bf N})^*(1) \} \gg x^\gamma \ \ \ \ \ (1)$

for all ${x \geq 1}$ and ${\gamma = 0.84}$. (This improved upon previous values of ${\gamma = 0.81}$ obtained by Applegate and Lagarias in 1995, ${\gamma = 0.65}$ by Applegate and Lagarias in 1995 by a different method, ${\gamma=0.48}$ by Wirsching in 1993, ${\gamma=0.43}$ by Krasikov in 1989, ${\gamma=0.3}$ by Sander in 1990, and some ${\gamma>0}$ by Crandall in 1978.) This is still the largest value of ${\gamma}$ for which (1) has been established. Of course, the Collatz conjecture would imply that we can take ${\gamma}$ equal to ${1}$, which is the assertion that a positive density set of natural numbers obeys the Collatz conjecture. This is not yet established, although the results in my previous paper do at least imply that a positive density set of natural numbers iterates to an (explicitly computable) bounded set, so in principle the ${\gamma=1}$ case of (1) could now be verified by an (enormous) finite computation in which one verifies that every number in this explicit bounded set iterates to ${1}$. In this post I would like to record a possible alternate route to this problem that depends on the distribution of a certain family of random variables that appeared in my previous paper, that I called Syracuse random variables.

Definition 1 (Syracuse random variables) For any natural number ${n}$, a Syracuse random variable ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ on the cyclic group ${{\bf Z}/3^n{\bf Z}}$ is defined as a random variable of the form

$\displaystyle \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = \sum_{m=1}^n 3^{n-m} 2^{-{\mathbf a}_m-\dots-{\mathbf a}_n} \ \ \ \ \ (2)$

where ${\mathbf{a}_1,\dots,\mathbf{a_n}}$ are independent copies of a geometric random variable ${\mathbf{Geom}(2)}$ on the natural numbers with mean ${2}$, thus

$\displaystyle \mathop{\bf P}( \mathbf{a}_1=a_1,\dots,\mathbf{a}_n=a_n) = 2^{-a_1-\dots-a_n}$

} for ${a_1,\dots,a_n \in {\bf N}+1}$. In (2) the arithmetic is performed in the ring ${{\bf Z}/3^n{\bf Z}}$.

Thus for instance

$\displaystyle \mathrm{Syrac}({\bf Z}/3{\bf Z}) = 2^{-\mathbf{a}_1} \hbox{ mod } 3$

$\displaystyle \mathrm{Syrac}({\bf Z}/3^2{\bf Z}) = 2^{-\mathbf{a}_1-\mathbf{a}_2} + 3 \times 2^{-\mathbf{a}_2} \hbox{ mod } 3^2$

$\displaystyle \mathrm{Syrac}({\bf Z}/3^3{\bf Z}) = 2^{-\mathbf{a}_1-\mathbf{a}_2-\mathbf{a}_3} + 3 \times 2^{-\mathbf{a}_2-\mathbf{a}_3} + 3^2 \times 2^{-\mathbf{a}_3} \hbox{ mod } 3^3$

and so forth. After reversing the labeling of the ${\mathbf{a}_1,\dots,\mathbf{a}_n}$, one could also view ${\mathrm{Syrac}({\bf Z}/3^n{\bf Z})}$ as the mod ${3^n}$ reduction of a ${3}$-adic random variable

$\displaystyle \mathbf{Syrac}({\bf Z}_3) = \sum_{m=1}^\infty 3^{m-1} 2^{-{\mathbf a}_1-\dots-{\mathbf a}_m}.$

The probability density function ${b \mapsto \mathbf{P}( \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = b )}$ of the Syracuse random variable can be explicitly computed by a recursive formula (see Lemma 1.12 of my previous paper). For instance, when ${n=1}$, ${\mathbf{P}( \mathbf{Syrac}({\bf Z}/3{\bf Z}) = b )}$ is equal to ${0,1/3,2/3}$ for ${x=b,1,2 \hbox{ mod } 3}$ respectively, while when ${n=2}$, ${\mathbf{P}( \mathbf{Syrac}({\bf Z}/3^2{\bf Z}) = b )}$ is equal to

$\displaystyle 0, \frac{8}{63}, \frac{16}{63}, 0, \frac{11}{63}, \frac{4}{63}, 0, \frac{2}{63}, \frac{22}{63}$

when ${b=0,\dots,8 \hbox{ mod } 9}$ respectively.

The relationship of these random variables to the Collatz problem can be explained as follows. Let ${2{\bf N}+1 = \{1,3,5,\dots\}}$ denote the odd natural numbers, and define the Syracuse map ${\mathrm{Syr}: 2{\bf N}+1 \rightarrow 2{\bf N}+1}$ by

$\displaystyle \mathrm{Syr}(N) := \frac{3n+1}{2^{\nu_2(3N+1)}}$

where the ${2}$valuation ${\nu_2(3n+1) \in {\bf N}}$ is the number of times ${2}$ divides ${3N+1}$. We can define the forward orbit ${\mathrm{Syr}^{\bf N}(n)}$ and backward orbit ${(\mathrm{Syr}^{\bf N})^*(N)}$ of the Syracuse map as before. It is not difficult to then see that the Collatz conjecture is equivalent to the assertion ${(\mathrm{Syr}^{\bf N})^*(1) = 2{\bf N}+1}$, and that the assertion (1) for a given ${\gamma}$ is equivalent to the assertion

$\displaystyle \# \{ N \leq x: N \in (\mathrm{Syr}^{\bf N})^*(1) \} \gg x^\gamma \ \ \ \ \ (3)$

for all ${x \geq 1}$, where ${N}$ is now understood to range over odd natural numbers. A brief calculation then shows that for any odd natural number ${N}$ and natural number ${n}$, one has

$\displaystyle \mathrm{Syr}^n(N) = 3^n 2^{-a_1-\dots-a_n} N + \sum_{m=1}^n 3^{n-m} 2^{-a_m-\dots-a_n}$

where the natural numbers ${a_1,\dots,a_n}$ are defined by the formula

$\displaystyle a_i := \nu_2( 3 \mathrm{Syr}^{i-1}(N) + 1 ),$

so in particular

$\displaystyle \mathrm{Syr}^n(N) = \sum_{m=1}^n 3^{n-m} 2^{-a_m-\dots-a_n} \hbox{ mod } 3^n.$

Heuristically, one expects the ${2}$-valuation ${a = \nu_2(N)}$ of a typical odd number ${N}$ to be approximately distributed according to the geometric distribution ${\mathbf{Geom}(2)}$, so one therefore expects the residue class ${\mathrm{Syr}^n(N) \hbox{ mod } 3^n}$ to be distributed approximately according to the random variable ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$.

The Syracuse random variables ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ will always avoid multiples of three (this reflects the fact that ${\mathrm{Syr}(N)}$ is never a multiple of three), but attains any non-multiple of three in ${{\bf Z}/3^n{\bf Z}}$ with positive probability. For any natural number ${n}$, set

$\displaystyle c_n := \inf_{b \in {\bf Z}/3^n{\bf Z}: 3 \nmid b} \mathbf{P}( \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = b ).$

Equivalently, ${c_n}$ is the greatest quantity for which we have the inequality

$\displaystyle \sum_{(a_1,\dots,a_n) \in S_{n,N}} 2^{-a_1-\dots-a_m} \geq c_n \ \ \ \ \ (4)$

for all integers ${N}$ not divisible by three, where ${S_{n,N} \subset ({\bf N}+1)^n}$ is the set of all tuples ${(a_1,\dots,a_n)}$ for which

$\displaystyle N = \sum_{m=1}^n 3^{m-1} 2^{-a_1-\dots-a_m} \hbox{ mod } 3^n.$

Thus for instance ${c_0=1}$, ${c_1 = 1/3}$, and ${c_2 = 2/63}$. On the other hand, since all the probabilities ${\mathbf{P}( \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = b)}$ sum to ${1}$ as ${b \in {\bf Z}/3^n{\bf Z}}$ ranges over the non-multiples of ${3}$, we have the trivial upper bound

$\displaystyle c_n \leq \frac{3}{2} 3^{-n}.$

There is also an easy submultiplicativity result:

Lemma 2 For any natural numbers ${n_1,n_2}$, we have

$\displaystyle c_{n_1+n_2-1} \geq c_{n_1} c_{n_2}.$

Proof: Let ${N}$ be an integer not divisible by ${3}$, then by (4) we have

$\displaystyle \sum_{(a_1,\dots,a_{n_1}) \in S_{n_1,N}} 2^{-a_1-\dots-a_{n_1}} \geq c_{n_1}.$

If we let ${S'_{n_1,N}}$ denote the set of tuples ${(a_1,\dots,a_{n_1-1})}$ that can be formed from the tuples in ${S_{n_1,N}}$ by deleting the final component ${a_{n_1}}$ from each tuple, then we have

$\displaystyle \sum_{(a_1,\dots,a_{n_1-1}) \in S'_{n_1,N}} 2^{-a_1-\dots-a_{n_1-1}} \geq c_{n_1}. \ \ \ \ \ (5)$

Next, observe that if ${(a_1,\dots,a_{n_1-1}) \in S'_{n_1,N}}$, then

$\displaystyle N = \sum_{m=1}^{n_1-1} 3^{m-1} 2^{-a_1-\dots-a_m} + 3^{n_1-1} 2^{-a_1-\dots-a_{n_1-1}} M$

with ${M = M_{N,n_1,a_1,\dots,a_{n_1-1}}}$ an integer not divisible by three. By definition of ${S_{n_2,M}}$ and a relabeling, we then have

$\displaystyle M = \sum_{m=1}^{n_2} 3^{m-1} 2^{-a_{n_1}-\dots-a_{m+n_1-1}} \hbox{ mod } 3^{n_2}$

for all ${(a_{n_1},\dots,a_{n_1+n_2-1}) \in S_{n_2,M}}$. For such tuples we then have

$\displaystyle N = \sum_{m=1}^{n_1+n_2-1} 3^{m-1} 2^{-a_1-\dots-a_{n_1+n_2-1}} \hbox{ mod } 3^{n_1+n_2-1}$

so that ${(a_1,\dots,a_{n_1+n_2-1}) \in S_{n_1+n_2-1,N}}$. Since

$\displaystyle \sum_{(a_{n_1},\dots,a_{n_1+n_2-1}) \in S_{n_2,M}} 2^{-a_{n_1}-\dots-a_{n_1+n_2-1}} \geq c_{n_2}$

for each ${M}$, the claim follows. $\Box$

From this lemma we see that ${c_n = 3^{-\beta n + o(n)}}$ for some absolute constant ${\beta \geq 1}$. Heuristically, we expect the Syracuse random variables to be somewhat approximately equidistributed amongst the multiples of ${{\bf Z}/3^n{\bf Z}}$ (in Proposition 1.4 of my previous paper I prove a fine scale mixing result that supports this heuristic). As a consequence it is natural to conjecture that ${\beta=1}$. I cannot prove this, but I can show that this conjecture would imply that we can take the exponent ${\gamma}$ in (1), (3) arbitrarily close to one:

Proposition 3 Suppose that ${\beta=1}$ (that is to say, ${c_n = 3^{-n+o(n)}}$ as ${n \rightarrow \infty}$). Then

$\displaystyle \# \{ N \leq x: N \in (\mathrm{Syr}^{\bf N})^*(1) \} \gg x^{1-o(1)}$

as ${x \rightarrow \infty}$, or equivalently

$\displaystyle \# \{ N \leq x: N \in (\mathrm{Col}^{\bf N})^*(1) \} \gg x^{1-o(1)}$

as ${x \rightarrow \infty}$. In other words, (1), (3) hold for all ${\gamma < 1}$.

I prove this proposition below the fold. A variant of the argument shows that for any value of ${\beta}$, (1), (3) holds whenever ${\gamma < f(\beta)}$, where ${f: [0,1] \rightarrow [0,1]}$ is an explicitly computable function with ${f(\beta) \rightarrow 1}$ as ${\beta \rightarrow 1}$. In principle, one could then improve the Krasikov-Lagarias result ${\gamma = 0.84}$ by getting a sufficiently good upper bound on ${\beta}$, which is in principle achievable numerically (note for instance that Lemma 2 implies the bound ${c_n \leq 3^{-\beta(n-1)}}$ for any ${n}$, since ${c_{kn-k+1} \geq c_n^k}$ for any ${k}$).

Just a brief post to record some notable papers in my fields of interest that appeared on the arXiv recently.

• A sharp square function estimate for the cone in ${\bf R}^3$“, by Larry Guth, Hong Wang, and Ruixiang Zhang.  This paper establishes an optimal (up to epsilon losses) square function estimate for the three-dimensional light cone that was essentially conjectured by Mockenhaupt, Seeger, and Sogge, which has a number of other consequences including Sogge’s local smoothing conjecture for the wave equation in two spatial dimensions, which in turn implies the (already known) Bochner-Riesz, restriction, and Kakeya conjectures in two dimensions.   Interestingly, modern techniques such as polynomial partitioning and decoupling estimates are not used in this argument; instead, the authors mostly rely on an induction on scales argument and Kakeya type estimates.  Many previous authors (including myself) were able to get weaker estimates of this type by an induction on scales method, but there were always significant inefficiencies in doing so; in particular knowing the sharp square function estimate at smaller scales did not imply the sharp square function estimate at the given larger scale.  The authors here get around this issue by finding an even stronger estimate that implies the square function estimate, but behaves significantly better with respect to induction on scales.
• On the Chowla and twin primes conjectures over ${\mathbb F}_q[T]$“, by Will Sawin and Mark Shusterman.  This paper resolves a number of well known open conjectures in analytic number theory, such as the Chowla conjecture and the twin prime conjecture (in the strong form conjectured by Hardy and Littlewood), in the case of function fields where the field is a prime power $q=p^j$ which is fixed (in contrast to a number of existing results in the “large $q$” limit) but has a large exponent $j$.  The techniques here are orthogonal to those used in recent progress towards the Chowla conjecture over the integers (e.g., in this previous paper of mine); the starting point is an algebraic observation that in certain function fields, the Mobius function behaves like a quadratic Dirichlet character along certain arithmetic progressions.  In principle, this reduces problems such as Chowla’s conjecture to problems about estimating sums of Dirichlet characters, for which more is known; but the task is still far from trivial.
• Bounds for sets with no polynomial progressions“, by Sarah Peluse.  This paper can be viewed as part of a larger project to obtain quantitative density Ramsey theorems of Szemeredi type.  For instance, Gowers famously established a relatively good quantitative bound for Szemeredi’s theorem that all dense subsets of integers contain arbitrarily long arithmetic progressions $a, a+r, \dots, a+(k-1)r$.  The corresponding question for polynomial progressions $a+P_1(r), \dots, a+P_k(r)$ is considered more difficult for a number of reasons.  One of them is that dilation invariance is lost; a dilation of an arithmetic progression is again an arithmetic progression, but a dilation of a polynomial progression will in general not be a polynomial progression with the same polynomials $P_1,\dots,P_k$.  Another issue is that the ranges of the two parameters $a,r$ are now at different scales.  Peluse gets around these difficulties in the case when all the polynomials $P_1,\dots,P_k$ have distinct degrees, which is in some sense the opposite case to that considered by Gowers (in particular, she avoids the need to obtain quantitative inverse theorems for high order Gowers norms; which was recently obtained in this integer setting by Manners but with bounds that are probably not strong enough to for the bounds in Peluse’s results, due to a degree lowering argument that is available in this case).  To resolve the first difficulty one has to make all the estimates rather uniform in the coefficients of the polynomials $P_j$, so that one can still run a density increment argument efficiently.  To resolve the second difficulty one needs to find a quantitative concatenation theorem for Gowers uniformity norms.  Many of these ideas were developed in previous papers of Peluse and Peluse-Prendiville in simpler settings.
• On blow up for the energy super critical defocusing non linear Schrödinger equations“, by Frank Merle, Pierre Raphael, Igor Rodnianski, and Jeremie Szeftel.  This paper (when combined with two companion papers) resolves a long-standing problem as to whether finite time blowup occurs for the defocusing supercritical nonlinear Schrödinger equation (at least in certain dimensions and nonlinearities).  I had a previous paper establishing a result like this if one “cheated” by replacing the nonlinear Schrodinger equation by a system of such equations, but remarkably they are able to tackle the original equation itself without any such cheating.  Given the very analogous situation with Navier-Stokes, where again one can create finite time blowup by “cheating” and modifying the equation, it does raise hope that finite time blowup for the incompressible Navier-Stokes and Euler equations can be established…  In fact the connection may not just be at the level of analogy; a surprising key ingredient in the proofs here is the observation that a certain blowup ansatz for the nonlinear Schrodinger equation is governed by solutions to the (compressible) Euler equation, and finite time blowup examples for the latter can be used to construct finite time blowup examples for the former.

Peter Denton, Stephen Parke, Xining Zhang, and I have just uploaded to the arXiv a completely rewritten version of our previous paper, now titled “Eigenvectors from Eigenvalues: a survey of a basic identity in linear algebra“. This paper is now a survey of the various literature surrounding the following basic identity in linear algebra, which we propose to call the eigenvector-eigenvalue identity:

Theorem 1 (Eigenvector-eigenvalue identity) Let ${A}$ be an ${n \times n}$ Hermitian matrix, with eigenvalues ${\lambda_1(A),\dots,\lambda_n(A)}$. Let ${v_i}$ be a unit eigenvector corresponding to the eigenvalue ${\lambda_i(A)}$, and let ${v_{i,j}}$ be the ${j^{th}}$ component of ${v_i}$. Then

$\displaystyle |v_{i,j}|^2 \prod_{k=1; k \neq i}^n (\lambda_i(A) - \lambda_k(A)) = \prod_{k=1}^{n-1} (\lambda_i(A) - \lambda_k(M_j))$

where ${M_j}$ is the ${n-1 \times n-1}$ Hermitian matrix formed by deleting the ${j^{th}}$ row and column from ${A}$.

When we posted the first version of this paper, we were unaware of previous appearances of this identity in the literature; a related identity had been used by Erdos-Schlein-Yau and by myself and Van Vu for applications to random matrix theory, but to our knowledge this specific identity appeared to be new. Even two months after our preprint first appeared on the arXiv in August, we had only learned of one other place in the literature where the identity showed up (by Forrester and Zhang, who also cite an earlier paper of Baryshnikov).

The situation changed rather dramatically with the publication of a popular science article in Quanta on this identity in November, which gave this result significantly more exposure. Within a few weeks we became informed (through private communication, online discussion, and exploration of the citation tree around the references we were alerted to) of over three dozen places where the identity, or some other closely related identity, had previously appeared in the literature, in such areas as numerical linear algebra, various aspects of graph theory (graph reconstruction, chemical graph theory, and walks on graphs), inverse eigenvalue problems, random matrix theory, and neutrino physics. As a consequence, we have decided to completely rewrite our article in order to collate this crowdsourced information, and survey the history of this identity, all the known proofs (we collect seven distinct ways to prove the identity (or generalisations thereof)), and all the applications of it that we are currently aware of. The citation graph of the literature that this ad hoc crowdsourcing effort produced is only very weakly connected, which we found surprising:

The earliest explicit appearance of the eigenvector-eigenvalue identity we are now aware of is in a 1966 paper of Thompson, although this paper is only cited (directly or indirectly) by a fraction of the known literature, and also there is a precursor identity of Löwner from 1934 that can be shown to imply the identity as a limiting case. At the end of the paper we speculate on some possible reasons why this identity only achieved a modest amount of recognition and dissemination prior to the November 2019 Quanta article.

Earlier this month, Hao Huang (who, incidentally, was a graduate student here at UCLA) gave a remarkably short proof of a long-standing problem in theoretical computer science known as the sensitivity conjecture. See for instance this blog post of Gil Kalai for further discussion and links to many other online discussions of this result. One formulation of the theorem proved is as follows. Define the ${n}$-dimensional hypercube graph ${Q_n}$ to be the graph with vertex set ${({\bf Z}/2{\bf Z})^n}$, and with every vertex ${v \in ({\bf Z}/2{\bf Z})^n}$ joined to the ${n}$ vertices ${v + e_1,\dots,v+e_n}$, where ${e_1,\dots,e_n}$ is the standard basis of ${({\bf Z}/2{\bf Z})^n}$.

Theorem 1 (Lower bound on maximum degree of induced subgraphs of hypercube) Let ${E}$ be a set of at least ${2^{n-1}+1}$ vertices in ${Q_n}$. Then there is a vertex in ${E}$ that is adjacent (in ${Q_n}$) to at least ${\sqrt{n}}$ other vertices in ${E}$.

The bound ${\sqrt{n}}$ (or more precisely, ${\lceil \sqrt{n} \rceil}$) is completely sharp, as shown by Chung, Furedi, Graham, and Seymour; we describe this example below the fold. When combined with earlier reductions of Gotsman-Linial and Nisan-Szegedy; we give these below the fold also.

Let ${A = (a_{vw})_{v,w \in ({\bf Z}/2{\bf Z})^n}}$ be the adjacency matrix of ${Q_n}$ (where we index the rows and columns directly by the vertices in ${({\bf Z}/2{\bf Z})^n}$, rather than selecting some enumeration ${1,\dots,2^n}$), thus ${a_{vw}=1}$ when ${w = v+e_i}$ for some ${i=1,\dots,n}$, and ${a_{vw}=0}$ otherwise. The above theorem then asserts that if ${E}$ is a set of at least ${2^{n-1}+1}$ vertices, then the ${E \times E}$ minor ${(a_{vw})_{v,w \in E}}$ of ${A}$ has a row (or column) that contains at least ${\sqrt{n}}$ non-zero entries.

The key step to prove this theorem is the construction of rather curious variant ${\tilde A}$ of the adjacency matrix ${A}$:

Proposition 2 There exists a ${({\bf Z}/2{\bf Z})^n \times ({\bf Z}/2{\bf Z})^n}$ matrix ${\tilde A = (\tilde a_{vw})_{v,w \in ({\bf Z}/2{\bf Z})^n}}$ which is entrywise dominated by ${A}$ in the sense that

$\displaystyle |\tilde a_{vw}| \leq a_{vw} \hbox{ for all } v,w \in ({\bf Z}/2{\bf Z})^n \ \ \ \ \ (1)$

and such that ${\tilde A}$ has ${\sqrt{n}}$ as an eigenvalue with multiplicity ${2^{n-1}}$.

Assuming this proposition, the proof of Theorem 1 can now be quickly concluded. If we view ${\tilde A}$ as a linear operator on the ${2^n}$-dimensional space ${\ell^2(({\bf Z}/2{\bf Z})^n)}$ of functions of ${({\bf Z}/2{\bf Z})^n}$, then by hypothesis this space has a ${2^{n-1}}$-dimensional subspace ${V}$ on which ${\tilde A}$ acts by multiplication by ${\sqrt{n}}$. If ${E}$ is a set of at least ${2^{n-1}+1}$ vertices in ${Q_n}$, then the space ${\ell^2(E)}$ of functions on ${E}$ has codimension at most ${2^{n-1}-1}$ in ${\ell^2(({\bf Z}/2{\bf Z})^n)}$, and hence intersects ${V}$ non-trivially. Thus the ${E \times E}$ minor ${\tilde A_E}$ of ${\tilde A}$ also has ${\sqrt{n}}$ as an eigenvalue (this can also be derived from the Cauchy interlacing inequalities), and in particular this minor has operator norm at least ${\sqrt{n}}$. By Schur’s test, this implies that one of the rows or columns of this matrix has absolute values summing to at least ${\sqrt{n}}$, giving the claim.

Remark 3 The argument actually gives a strengthening of Theorem 1: there exists a vertex ${v_0}$ of ${E}$ with the property that for every natural number ${k}$, there are at least ${n^{k/2}}$ paths of length ${k}$ in the restriction ${Q_n|_E}$ of ${Q_n}$ to ${E}$ that start from ${v_0}$. Indeed, if we let ${(u_v)_{v \in E}}$ be an eigenfunction of ${\tilde A}$ on ${\ell^2(E)}$, and let ${v_0}$ be a vertex in ${E}$ that maximises the value of ${|u_{v_0}|}$, then for any ${k}$ we have that the ${v_0}$ component of ${\tilde A_E^k (u_v)_{v \in E}}$ is equal to ${n^{k/2} |u_{v_0}|}$; on the other hand, by the triangle inequality, this component is at most ${|u_{v_0}|}$ times the number of length ${k}$ paths in ${Q_n|_E}$ starting from ${v_0}$, giving the claim.

This argument can be viewed as an instance of a more general “interlacing method” to try to control the behaviour of a graph ${G}$ on all large subsets ${E}$ by first generating a matrix ${\tilde A}$ on ${G}$ with very good spectral properties, which are then partially inherited by the ${E \times E}$ minor of ${\tilde A}$ by interlacing inequalities. In previous literature using this method (see e.g., this survey of Haemers, or this paper of Wilson), either the original adjacency matrix ${A}$, or some non-negatively weighted version of that matrix, was used as the controlling matrix ${\tilde A}$; the novelty here is the use of signed controlling matrices. It will be interesting to see what further variants and applications of this method emerge in the near future. (Thanks to Anurag Bishoi in the comments for these references.)

The “magic” step in the above argument is constructing ${\tilde A}$. In Huang’s paper, ${\tilde A}$ is constructed recursively in the dimension ${n}$ in a rather simple but mysterious fashion. Very recently, Roman Karasev gave an interpretation of this matrix in terms of the exterior algebra on ${{\bf R}^n}$. In this post I would like to give an alternate interpretation in terms of the operation of twisted convolution, which originated in the theory of the Heisenberg group in quantum mechanics.

Firstly note that the original adjacency matrix ${A}$, when viewed as a linear operator on ${\ell^2(({\bf Z}/2{\bf Z})^n)}$, is a convolution operator

$\displaystyle A f = f * \mu$

where

$\displaystyle \mu(x) := \sum_{i=1}^n 1_{x=e_i}$

is the counting measure on the standard basis ${e_1,\dots,e_n}$, and ${*}$ denotes the ordinary convolution operation

$\displaystyle f * g(x) := \sum_{y \in ({\bf Z}/2{\bf Z})^n} f(y) g(x-y) = \sum_{y_1+y_2 = x} f(y_1) g(y_2).$

As is well known, this operation is commutative and associative. Thus for instance the square ${A^2}$ of the adjacency operator ${A}$ is also a convolution operator

$\displaystyle A^2 f = f * (\mu * \mu)(x)$

where the convolution kernel ${\mu * \mu}$ is moderately complicated:

$\displaystyle \mu*\mu(x) = n \times 1_{x=0} + \sum_{1 \leq i < j \leq n} 2 \times 1_{x = e_i + e_j}.$

The factor ${2}$ in this expansion comes from combining the two terms ${1_{x=e_i} * 1_{x=e_j}}$ and ${1_{x=e_j} * 1_{x=e_i}}$, which both evaluate to ${1_{x=e_i+e_j}}$.

More generally, given any bilinear form ${B: ({\bf Z}/2{\bf Z})^n \times ({\bf Z}/2{\bf Z})^n \rightarrow {\bf Z}/2{\bf Z}}$, one can define the twisted convolution

$\displaystyle f *_B g(x) := \sum_{y \in ({\bf Z}/2{\bf Z})^n} (-1)^{B(y,x-y)} f(y) g(x-y)$

$\displaystyle = \sum_{y_1+y_2=x} (-1)^{B(y_1,y_2)} f(y_1) g(y_2)$

of two functions ${f,g \in \ell^2(({\bf Z}/2{\bf Z})^n)}$. This operation is no longer commutative (unless ${B}$ is symmetric). However, it remains associative; indeed, one can easily compute that

$\displaystyle (f *_B g) *_B h(x) = f *_B (g *_B h)(x)$

$\displaystyle = \sum_{y_1+y_2+y_3=x} (-1)^{B(y_1,y_2)+B(y_1,y_3)+B(y_2,y_3)} f(y_1) g(y_2) h(y_3).$

In particular, if we define the twisted convolution operator

$\displaystyle A_B f(x) := f *_B \mu(x)$

then the square ${A_B^2}$ is also a twisted convolution operator

$\displaystyle A_B^2 f = f *_B (\mu *_B \mu)$

and the twisted convolution kernel ${\mu *_B \mu}$ can be computed as

$\displaystyle \mu *_B \mu(x) = (\sum_{i=1}^n (-1)^{B(e_i,e_i)}) 1_{x=0}$

$\displaystyle + \sum_{1 \leq i < j \leq n} ((-1)^{B(e_i,e_j)} + (-1)^{B(e_j,e_i)}) 1_{x=e_i+e_j}.$

For general bilinear forms ${B}$, this twisted convolution is just as messy as ${\mu * \mu}$ is. But if we take the specific bilinear form

$\displaystyle B(x,y) := \sum_{1 \leq i < j \leq n} x_i y_j \ \ \ \ \ (2)$

then ${B(e_i,e_i)=0}$ for ${1 \leq i \leq n}$ and ${B(e_i,e_j)=1, B(e_j,e_i)=0}$ for ${1 \leq i < j \leq n}$, and the above twisted convolution simplifies to

$\displaystyle \mu *_B \mu(x) = n 1_{x=0}$

and now ${A_B^2}$ is very simple:

$\displaystyle A_B^2 f = n f.$

Thus the only eigenvalues of ${A_B}$ are ${+\sqrt{n}}$ and ${-\sqrt{n}}$. The matrix ${A_B}$ is entrywise dominated by ${A}$ in the sense of (1), and in particular has trace zero; thus the ${+\sqrt{n}}$ and ${-\sqrt{n}}$ eigenvalues must occur with equal multiplicity, so in particular the ${+\sqrt{n}}$ eigenvalue occurs with multiplicity ${2^{n-1}}$ since the matrix has dimensions ${2^n \times 2^n}$. This establishes Proposition 2.

Remark 4 Twisted convolution ${*_B}$ is actually just a component of ordinary convolution, but not on the original group ${({\bf Z}/2{\bf Z})^n}$; instead it relates to convolution on a Heisenberg group extension of this group. More specifically, define the Heisenberg group ${H}$ to be the set of pairs ${(x, t) \in ({\bf Z}/2{\bf Z})^n \times ({\bf Z}/2{\bf Z})}$ with group law

$\displaystyle (x,t) \cdot (y,s) := (x+y, t+s+B(x,y))$

and inverse operation

$\displaystyle (x,t)^{-1} = (-x, -t+B(x,x))$

(one can dispense with the negative signs here if desired, since we are in characteristic two). Convolution on ${H}$ is defined in the usual manner: one has

$\displaystyle F*G( (x,t) ) := \sum_{(y,s) \in H} F(y,s) G( (y,s)^{-1} (x,t) )$

for any ${F,G \in \ell^2(H)}$. Now if ${f \in \ell^2(({\bf Z}/2{\bf Z})^n)}$ is a function on the original group ${({\bf Z}/2{\bf Z})^n}$, we can define the lift ${\tilde f \in \ell^2(H)}$ by the formula

$\displaystyle \tilde f(x,t) := (-1)^t f(x)$

and then by chasing all the definitions one soon verifies that

$\displaystyle \tilde f * \tilde g = 2 \widetilde{f *_B g}$

for any ${f,g \in \ell^2(({\bf Z}/2{\bf Z})^n)}$, thus relating twisted convolution ${*_B}$ to Heisenberg group convolution ${*}$.

Remark 5 With the twisting by the specific bilinear form ${B}$ given by (2), convolution by ${1_{x=e_i}}$ and ${1_{x=e_j}}$ now anticommute rather than commute. This makes the twisted convolution algebra ${(\ell^2(({\bf Z}/2{\bf Z})^n), *_B)}$ isomorphic to a Clifford algebra ${Cl({\bf R}^n,I_n)}$ (the real or complex algebra generated by formal generators ${v_1,\dots,v_n}$ subject to the relations ${(v_iv_j+v_jv_i)/2 = 1_{i=j}}$ for ${i,j=1,\dots,n}$) rather than the commutative algebra more familiar to abelian Fourier analysis. This connection to Clifford algebra (also observed independently by Tom Mrowka and by Daniel Matthews) may be linked to the exterior algebra interpretation of the argument in the recent preprint of Karasev mentioned above.

Remark 6 One could replace the form (2) in this argument by any other bilinear form ${B'}$ that obeyed the relations ${B'(e_i,e_i)=0}$ and ${B'(e_i,e_j) + B'(e_j,e_i)=1}$ for ${i \neq j}$. However, this additional level of generality does not add much; any such ${B'}$ will differ from ${B}$ by an antisymmetric form ${C}$ (so that ${C(x,x) = 0}$ for all ${x}$, which in characteristic two implied that ${C(x,y) = C(y,x)}$ for all ${x,y}$), and such forms can always be decomposed as ${C(x,y) = C'(x,y) + C'(y,x)}$, where ${C'(x,y) := \sum_{i. As such, the matrices ${A_B}$ and ${A_{B'}}$ are conjugate, with the conjugation operator being the diagonal matrix with entries ${(-1)^{C'(x,x)}}$ at each vertex ${x}$.

Remark 7 (Added later) This remark combines the two previous remarks. One can view any of the matrices ${A_{B'}}$ in Remark 6 as components of a single canonical matrix ${A_{Cl}}$ that is still of dimensions ${({\bf Z}/2{\bf Z})^n \times ({\bf Z}/2{\bf Z})^n}$, but takes values in the Clifford algebra ${Cl({\bf R}^n,I_n)}$ from Remark 5; with this “universal algebra” perspective, one no longer needs to make any arbitrary choices of form ${B}$. More precisely, let ${\ell^2( ({\bf Z}/2{\bf Z})^n \rightarrow Cl({\bf R}^n,I_n))}$ denote the vector space of functions ${f: ({\bf Z}/2{\bf Z})^n \rightarrow Cl({\bf R}^n,I_n)}$ from the hypercube to the Clifford algebra; as a real vector space, this is a ${2^{2n}}$ dimensional space, isomorphic to the direct sum of ${2^n}$ copies of ${\ell^2(({\bf Z}/2{\bf Z})^n)}$, as the Clifford algebra is itself ${2^n}$ dimensional. One can then define a canonical Clifford adjacency operator ${A_{Cl}}$ on this space by

$\displaystyle A_{Cl} f(x) := \sum_{i=1}^n f(x+e_i) v_i$

where ${v_1,\dots,v_n}$ are the generators of ${Cl({\bf R}^n,I_n)}$. This operator can either be identified with a Clifford-valued ${2^n \times 2^n}$ matrix or as a real-valued ${2^{2n} \times 2^{2n}}$ matrix. In either case one still has the key algebraic relations ${A_{Cl}^2 = n}$ and ${\mathrm{tr} A_{Cl} = 0}$, ensuring that when viewed as a real ${2^{2n} \times 2^{2n}}$ matrix, half of the eigenvalues are equal to ${+\sqrt{n}}$ and half equal to ${-\sqrt{n}}$. One can then use this matrix in place of any of the ${A_{B'}}$ to establish Theorem 1 (noting that Schur’s test continues to work for Clifford-valued matrices because of the norm structure on ${Cl({\bf R}^n,I_n)}$).

To relate ${A_{Cl}}$ to the real ${2^n \times 2^n}$ matrices ${A_{B'}}$, first observe that each point ${x}$ in the hypercube ${({\bf Z}/2{\bf Z})^n}$ can be associated with a one-dimensional real subspace ${\ell_x}$ (i.e., a line) in the Clifford algebra ${Cl({\bf R}^n,I_n)}$ by the formula

$\displaystyle \ell_{e_{i_1} + \dots + e_{i_k}} := \mathrm{span}_{\bf R}( v_{i_1} \dots v_{i_k} )$

for any ${i_1,\dots,i_k \in \{1,\dots,n\}}$ (note that this definition is well-defined even if the ${i_1,\dots,i_k}$ are out of order or contain repetitions). This can be viewed as a discrete line bundle over the hypercube. Since ${\ell_{x+e_i} = \ell_x e_i}$ for any ${i}$, we see that the ${2^n}$-dimensional real linear subspace ${V}$ of ${\ell^2( ({\bf Z}/2{\bf Z})^n \rightarrow Cl({\bf R}^n,I_n))}$ of sections of this bundle, that is to say the space of functions ${f: ({\bf Z}/2{\bf Z})^n \rightarrow Cl({\bf R}^n,I_n)}$ such that ${f(x) \in \ell_x}$ for all ${x \in ({\bf Z}/2{\bf Z})^n}$, is an invariant subspace of ${A_{Cl}}$. (Indeed, using the left-action of the Clifford algebra on ${\ell^2( ({\bf Z}/2{\bf Z})^n \rightarrow Cl({\bf R}^n,I_n))}$, which commutes with ${A_{Cl}}$, one can naturally identify ${\ell^2( ({\bf Z}/2{\bf Z})^n \rightarrow Cl({\bf R}^n,I_n))}$ with ${Cl({\bf R}^n,I_n) \otimes V}$, with the left action of ${Cl({\bf R}^n,I_n)}$ acting purely on the first factor and ${A_{Cl}}$ acting purely on the second factor.) Any trivialisation of this line bundle lets us interpret the restriction ${A_{Cl}|_V}$ of ${A_{Cl}}$ to ${V}$ as a real ${2^n \times 2^n}$ matrix. In particular, given one of the bilinear forms ${B'}$ from Remark 6, we can identify ${V}$ with ${\ell^2(({\bf Z}/2{\bf Z})^n)}$ by identifying any real function ${f \in \ell^2( ({\bf Z}/2{\bf Z})^n)}$ with the lift ${\tilde f \in V}$ defined by

$\displaystyle \tilde f(e_{i_1} + \dots + e_{i_k}) := (-1)^{\sum_{1 \leq j < j' \leq k} B'(e_{i_j}, e_{i_{j'}})}$

$\displaystyle f(e_{i_1} + \dots + e_{i_k}) v_{i_1} \dots v_{i_k}$

whenever ${1 \leq i_1 < \dots < i_k \leq n}$. A somewhat tedious computation using the properties of ${B'}$ then eventually gives the intertwining identity

$\displaystyle A_{Cl} \tilde f = \widetilde{A_{B'} f}$

and so ${A_{B'}}$ is conjugate to ${A_{Cl}|_V}$.

Let ${\Omega}$ be some domain (such as the real numbers). For any natural number ${p}$, let ${L(\Omega^p)_{sym}}$ denote the space of symmetric real-valued functions ${F^{(p)}: \Omega^p \rightarrow {\bf R}}$ on ${p}$ variables ${x_1,\dots,x_p \in \Omega}$, thus

$\displaystyle F^{(p)}(x_{\sigma(1)},\dots,x_{\sigma(p)}) = F^{(p)}(x_1,\dots,x_p)$

for any permutation ${\sigma: \{1,\dots,p\} \rightarrow \{1,\dots,p\}}$. For instance, for any natural numbers ${k,p}$, the elementary symmetric polynomials

$\displaystyle e_k^{(p)}(x_1,\dots,x_p) = \sum_{1 \leq i_1 < i_2 < \dots < i_k \leq p} x_{i_1} \dots x_{i_k}$

will be an element of ${L({\bf R}^p)_{sym}}$. With the pointwise product operation, ${L(\Omega^p)_{sym}}$ becomes a commutative real algebra. We include the case ${p=0}$, in which case ${L(\Omega^0)_{sym}}$ consists solely of the real constants.

Given two natural numbers ${k,p}$, one can “lift” a symmetric function ${F^{(k)} \in L(\Omega^k)_{sym}}$ of ${k}$ variables to a symmetric function ${[F^{(k)}]_{k \rightarrow p} \in L(\Omega^p)_{sym}}$ of ${p}$ variables by the formula

$\displaystyle [F^{(k)}]_{k \rightarrow p}(x_1,\dots,x_p) = \sum_{1 \leq i_1 < i_2 < \dots < i_k \leq p} F^{(k)}(x_{i_1}, \dots, x_{i_k})$

$\displaystyle = \frac{1}{k!} \sum_\pi F^{(k)}( x_{\pi(1)}, \dots, x_{\pi(k)} )$

where ${\pi}$ ranges over all injections from ${\{1,\dots,k\}}$ to ${\{1,\dots,p\}}$ (the latter formula making it clearer that ${[F^{(k)}]_{k \rightarrow p}}$ is symmetric). Thus for instance

$\displaystyle [F^{(1)}(x_1)]_{1 \rightarrow p} = \sum_{i=1}^p F^{(1)}(x_i)$

$\displaystyle [F^{(2)}(x_1,x_2)]_{2 \rightarrow p} = \sum_{1 \leq i < j \leq p} F^{(2)}(x_i,x_j)$

and

$\displaystyle e_k^{(p)}(x_1,\dots,x_p) = [x_1 \dots x_k]_{k \rightarrow p}.$

Also we have

$\displaystyle [1]_{k \rightarrow p} = \binom{p}{k} = \frac{p(p-1)\dots(p-k+1)}{k!}.$

With these conventions, we see that ${[F^{(k)}]_{k \rightarrow p}}$ vanishes for ${p=0,\dots,k-1}$, and is equal to ${F}$ if ${k=p}$. We also have the transitivity

$\displaystyle [F^{(k)}]_{k \rightarrow p} = \frac{1}{\binom{p-k}{p-l}} [[F^{(k)}]_{k \rightarrow l}]_{l \rightarrow p}$

if ${k \leq l \leq p}$.

The lifting map ${[]_{k \rightarrow p}}$ is a linear map from ${L(\Omega^k)_{sym}}$ to ${L(\Omega^p)_{sym}}$, but it is not a ring homomorphism. For instance, when ${\Omega={\bf R}}$, one has

$\displaystyle [x_1]_{1 \rightarrow p} [x_1]_{1 \rightarrow p} = (\sum_{i=1}^p x_i)^2 \ \ \ \ \ (1)$

$\displaystyle = \sum_{i=1}^p x_i^2 + 2 \sum_{1 \leq i < j \leq p} x_i x_j$

$\displaystyle = [x_1^2]_{1 \rightarrow p} + 2 [x_1 x_2]_{1 \rightarrow p}$

$\displaystyle \neq [x_1^2]_{1 \rightarrow p}.$

In general, one has the identity

$\displaystyle [F^{(k)}(x_1,\dots,x_k)]_{k \rightarrow p} [G^{(l)}(x_1,\dots,x_l)]_{l \rightarrow p} = \sum_{k,l \leq m \leq k+l} \frac{1}{k! l!} \ \ \ \ \ (2)$

$\displaystyle [\sum_{\pi, \rho} F^{(k)}(x_{\pi(1)},\dots,x_{\pi(k)}) G^{(l)}(x_{\rho(1)},\dots,x_{\rho(l)})]_{m \rightarrow p}$

for all natural numbers ${k,l,p}$ and ${F^{(k)} \in L(\Omega^k)_{sym}}$, ${G^{(l)} \in L(\Omega^l)_{sym}}$, where ${\pi, \rho}$ range over all injections ${\pi: \{1,\dots,k\} \rightarrow \{1,\dots,m\}}$, ${\rho: \{1,\dots,l\} \rightarrow \{1,\dots,m\}}$ with ${\pi(\{1,\dots,k\}) \cup \rho(\{1,\dots,l\}) = \{1,\dots,m\}}$. Combinatorially, the identity (2) follows from the fact that given any injections ${\tilde \pi: \{1,\dots,k\} \rightarrow \{1,\dots,p\}}$ and ${\tilde \rho: \{1,\dots,l\} \rightarrow \{1,\dots,p\}}$ with total image ${\tilde \pi(\{1,\dots,k\}) \cup \tilde \rho(\{1,\dots,l\})}$ of cardinality ${m}$, one has ${k,l \leq m \leq k+l}$, and furthermore there exist precisely ${m!}$ triples ${(\pi, \rho, \sigma)}$ of injections ${\pi: \{1,\dots,k\} \rightarrow \{1,\dots,m\}}$, ${\rho: \{1,\dots,l\} \rightarrow \{1,\dots,m\}}$, ${\sigma: \{1,\dots,m\} \rightarrow \{1,\dots,p\}}$ such that ${\tilde \pi = \sigma \circ \pi}$ and ${\tilde \rho = \sigma \circ \rho}$.

Example 1 When ${\Omega = {\bf R}}$, one has

$\displaystyle [x_1 x_2]_{2 \rightarrow p} [x_1]_{1 \rightarrow p} = [\frac{1}{2! 1!}( 2 x_1^2 x_2 + 2 x_1 x_2^2 )]_{2 \rightarrow p} + [\frac{1}{2! 1!} 6 x_1 x_2 x_3]_{3 \rightarrow p}$

$\displaystyle = [x_1^2 x_2 + x_1 x_2^2]_{2 \rightarrow p} + [3x_1 x_2 x_3]_{3 \rightarrow p}$

which is just a restatement of the identity

$\displaystyle (\sum_{i < j} x_i x_j) (\sum_k x_k) = \sum_{i

Note that the coefficients appearing in (2) do not depend on the final number of variables ${p}$. We may therefore abstract the role of ${p}$ from the law (2) by introducing the real algebra ${L(\Omega^*)_{sym}}$ of formal sums

$\displaystyle F^{(*)} = \sum_{k=0}^\infty [F^{(k)}]_{k \rightarrow *}$

where for each ${k}$, ${F^{(k)}}$ is an element of ${L(\Omega^k)_{sym}}$ (with only finitely many of the ${F^{(k)}}$ being non-zero), and with the formal symbol ${[]_{k \rightarrow *}}$ being formally linear, thus

$\displaystyle [F^{(k)}]_{k \rightarrow *} + [G^{(k)}]_{k \rightarrow *} := [F^{(k)} + G^{(k)}]_{k \rightarrow *}$

and

$\displaystyle c [F^{(k)}]_{k \rightarrow *} := [cF^{(k)}]_{k \rightarrow *}$

for ${F^{(k)}, G^{(k)} \in L(\Omega^k)_{sym}}$ and scalars ${c \in {\bf R}}$, and with multiplication given by the analogue

$\displaystyle [F^{(k)}(x_1,\dots,x_k)]_{k \rightarrow *} [G^{(l)}(x_1,\dots,x_l)]_{l \rightarrow *} = \sum_{k,l \leq m \leq k+l} \frac{1}{k! l!} \ \ \ \ \ (3)$

$\displaystyle [\sum_{\pi, \rho} F^{(k)}(x_{\pi(1)},\dots,x_{\pi(k)}) G^{(l)}(x_{\rho(1)},\dots,x_{\rho(l)})]_{m \rightarrow *}$

of (2). Thus for instance, in this algebra ${L(\Omega^*)_{sym}}$ we have

$\displaystyle [x_1]_{1 \rightarrow *} [x_1]_{1 \rightarrow *} = [x_1^2]_{1 \rightarrow *} + 2 [x_1 x_2]_{2 \rightarrow *}$

and

$\displaystyle [x_1 x_2]_{2 \rightarrow *} [x_1]_{1 \rightarrow *} = [x_1^2 x_2 + x_1 x_2^2]_{2 \rightarrow *} + [3 x_1 x_2 x_3]_{3 \rightarrow *}.$

Informally, ${L(\Omega^*)_{sym}}$ is an abstraction (or “inverse limit”) of the concept of a symmetric function of an unspecified number of variables, which are formed by summing terms that each involve only a bounded number of these variables at a time. One can check (somewhat tediously) that ${L(\Omega^*)_{sym}}$ is indeed a commutative real algebra, with a unit ${[1]_{0 \rightarrow *}}$. (I do not know if this algebra has previously been studied in the literature; it is somewhat analogous to the abstract algebra of finite linear combinations of Schur polynomials, with multiplication given by a Littlewood-Richardson rule. )

For natural numbers ${p}$, there is an obvious specialisation map ${[]_{* \rightarrow p}}$ from ${L(\Omega^*)_{sym}}$ to ${L(\Omega^p)_{sym}}$, defined by the formula

$\displaystyle [\sum_{k=0}^\infty [F^{(k)}]_{k \rightarrow *}]_{* \rightarrow p} := \sum_{k=0}^\infty [F^{(k)}]_{k \rightarrow p}.$

Thus, for instance, ${[]_{* \rightarrow p}}$ maps ${[x_1]_{1 \rightarrow *}}$ to ${[x_1]_{1 \rightarrow p}}$ and ${[x_1 x_2]_{2 \rightarrow *}}$ to ${[x_1 x_2]_{2 \rightarrow p}}$. From (2) and (3) we see that this map ${[]_{* \rightarrow p}: L(\Omega^*)_{sym} \rightarrow L(\Omega^p)_{sym}}$ is an algebra homomorphism, even though the maps ${[]_{k \rightarrow *}: L(\Omega^k)_{sym} \rightarrow L(\Omega^*)_{sym}}$ and ${[]_{k \rightarrow p}: L(\Omega^k)_{sym} \rightarrow L(\Omega^p)_{sym}}$ are not homomorphisms. By inspecting the ${p^{th}}$ component of ${L(\Omega^*)_{sym}}$ we see that the homomorphism ${[]_{* \rightarrow p}}$ is in fact surjective.

Now suppose that we have a measure ${\mu}$ on the space ${\Omega}$, which then induces a product measure ${\mu^p}$ on every product space ${\Omega^p}$. To avoid degeneracies we will assume that the integral ${\int_\Omega \mu}$ is strictly positive. Assuming suitable measurability and integrability hypotheses, a function ${F \in L(\Omega^p)_{sym}}$ can then be integrated against this product measure to produce a number

$\displaystyle \int_{\Omega^p} F\ d\mu^p.$

In the event that ${F}$ arises as a lift ${[F^{(k)}]_{k \rightarrow p}}$ of another function ${F^{(k)} \in L(\Omega^k)_{sym}}$, then from Fubini’s theorem we obtain the formula

$\displaystyle \int_{\Omega^p} F\ d\mu^p = \binom{p}{k} (\int_{\Omega^k} F^{(k)}\ d\mu^k) (\int_\Omega\ d\mu)^{p-k}.$

Thus for instance, if ${\Omega={\bf R}}$,

$\displaystyle \int_{{\bf R}^p} [x_1]_{1 \rightarrow p}\ d\mu^p = p (\int_{\bf R} x\ d\mu(x)) (\int_{\bf R} \mu)^{p-1} \ \ \ \ \ (4)$

and

$\displaystyle \int_{{\bf R}^p} [x_1 x_2]_{2 \rightarrow p}\ d\mu^p = \binom{p}{2} (\int_{{\bf R}^2} x_1 x_2\ d\mu(x_1) d\mu(x_2)) (\int_{\bf R} \mu)^{p-2}. \ \ \ \ \ (5)$

On summing, we see that if

$\displaystyle F^{(*)} = \sum_{k=0}^\infty [F^{(k)}]_{k \rightarrow *}$

is an element of the formal algebra ${L(\Omega^*)_{sym}}$, then

$\displaystyle \int_{\Omega^p} [F^{(*)}]_{* \rightarrow p}\ d\mu^p = \sum_{k=0}^\infty \binom{p}{k} (\int_{\Omega^k} F^{(k)}\ d\mu^k) (\int_\Omega\ d\mu)^{p-k}. \ \ \ \ \ (6)$

Note that by hypothesis, only finitely many terms on the right-hand side are non-zero.

Now for a key observation: whereas the left-hand side of (6) only makes sense when ${p}$ is a natural number, the right-hand side is meaningful when ${p}$ takes a fractional value (or even when it takes negative or complex values!), interpreting the binomial coefficient ${\binom{p}{k}}$ as a polynomial ${\frac{p(p-1) \dots (p-k+1)}{k!}}$ in ${p}$. As such, this suggests a way to introduce a “virtual” concept of a symmetric function on a fractional power space ${\Omega^p}$ for such values of ${p}$, and even to integrate such functions against product measures ${\mu^p}$, even if the fractional power ${\Omega^p}$ does not exist in the usual set-theoretic sense (and ${\mu^p}$ similarly does not exist in the usual measure-theoretic sense). More precisely, for arbitrary real or complex ${p}$, we now define ${L(\Omega^p)_{sym}}$ to be the space of abstract objects

$\displaystyle F^{(p)} = [F^{(*)}]_{* \rightarrow p} = \sum_{k=0}^\infty [F^{(k)}]_{k \rightarrow p}$

with ${F^{(*)} \in L(\Omega^*)_{sym}}$ and ${[]_{* \rightarrow p}}$ (and ${[]_{k \rightarrow p}}$ now interpreted as formal symbols, with the structure of a commutative real algebra inherited from ${L(\Omega^*)_{sym}}$, thus

$\displaystyle [F^{(*)}]_{* \rightarrow p} + [G^{(*)}]_{* \rightarrow p} := [F^{(*)} + G^{(*)}]_{* \rightarrow p}$

$\displaystyle c [F^{(*)}]_{* \rightarrow p} := [c F^{(*)}]_{* \rightarrow p}$

$\displaystyle [F^{(*)}]_{* \rightarrow p} [G^{(*)}]_{* \rightarrow p} := [F^{(*)} G^{(*)}]_{* \rightarrow p}.$

In particular, the multiplication law (2) continues to hold for such values of ${p}$, thanks to (3). Given any measure ${\mu}$ on ${\Omega}$, we formally define a measure ${\mu^p}$ on ${\Omega^p}$ with regards to which we can integrate elements ${F^{(p)}}$ of ${L(\Omega^p)_{sym}}$ by the formula (6) (providing one has sufficient measurability and integrability to make sense of this formula), thus providing a sort of “fractional dimensional integral” for symmetric functions. Thus, for instance, with this formalism the identities (4), (5) now hold for fractional values of ${p}$, even though the formal space ${{\bf R}^p}$ no longer makes sense as a set, and the formal measure ${\mu^p}$ no longer makes sense as a measure. (The formalism here is somewhat reminiscent of the technique of dimensional regularisation employed in the physical literature in order to assign values to otherwise divergent integrals. See also this post for an unrelated abstraction of the integration concept involving integration over supercommutative variables (and in particular over fermionic variables).)

Example 2 Suppose ${\mu}$ is a probability measure on ${\Omega}$, and ${X: \Omega \rightarrow {\bf R}}$ is a random variable; on any power ${\Omega^k}$, we let ${X_1,\dots,X_k: \Omega^k \rightarrow {\bf R}}$ be the usual independent copies of ${X}$ on ${\Omega^k}$, thus ${X_j(\omega_1,\dots,\omega_k) := X(\omega_j)}$ for ${(\omega_1,\dots,\omega_k) \in \Omega^k}$. Then for any real or complex ${p}$, the formal integral

$\displaystyle \int_{\Omega^p} [X_1]_{1 \rightarrow p}^2\ d\mu^p$

can be evaluated by first using the identity

$\displaystyle [X_1]_{1 \rightarrow p}^2 = [X_1^2]_{1 \rightarrow p} + 2[X_1 X_2]_{2 \rightarrow p}$

(cf. (1)) and then using (6) and the probability measure hypothesis ${\int_\Omega\ d\mu = 1}$ to conclude that

$\displaystyle \int_{\Omega^p} [X_1]_{1 \rightarrow p}^2\ d\mu^p = \binom{p}{1} \int_{\Omega} X^2\ d\mu + 2 \binom{p}{2} \int_{\Omega^2} X_1 X_2\ d\mu^2$

$\displaystyle = p (\int_\Omega X^2\ d\mu - (\int_\Omega X\ d\mu)^2) + p^2 (\int_\Omega X\ d\mu)^2$

or in probabilistic notation

$\displaystyle \int_{\Omega^p} [X_1]_{1 \rightarrow p}^2\ d\mu^p = p \mathbf{Var}(X) + p^2 \mathbf{E}(X)^2. \ \ \ \ \ (7)$

For ${p}$ a natural number, this identity has the probabilistic interpretation

$\displaystyle \mathbf{E}( X_1 + \dots + X_p)^2 = p \mathbf{Var}(X) + p^2 \mathbf{E}(X)^2 \ \ \ \ \ (8)$

whenever ${X_1,\dots,X_p}$ are jointly independent copies of ${X}$, which reflects the well known fact that the sum ${X_1 + \dots + X_p}$ has expectation ${p \mathbf{E} X}$ and variance ${p \mathbf{Var}(X)}$. One can thus view (7) as an abstract generalisation of (8) to the case when ${p}$ is fractional, negative, or even complex, despite the fact that there is no sensible way in this case to talk about ${p}$ independent copies ${X_1,\dots,X_p}$ of ${X}$ in the standard framework of probability theory.

In this particular case, the quantity (7) is non-negative for every nonnegative ${p}$, which looks plausible given the form of the left-hand side. Unfortunately, this sort of non-negativity does not always hold; for instance, if ${X}$ has mean zero, one can check that

$\displaystyle \int_{\Omega^p} [X_1]_{1 \rightarrow p}^4\ d\mu^p = p \mathbf{Var}(X^2) + p(3p-2) (\mathbf{E}(X^2))^2$

and the right-hand side can become negative for ${p < 2/3}$. This is a shame, because otherwise one could hope to start endowing ${L(X^p)_{sym}}$ with some sort of commutative von Neumann algebra type structure (or the abstract probability structure discussed in this previous post) and then interpret it as a genuine measure space rather than as a virtual one. (This failure of positivity is related to the fact that the characteristic function of a random variable, when raised to the ${p^{th}}$ power, need not be a characteristic function of any random variable once ${p}$ is no longer a natural number: “fractional convolution” does not preserve positivity!) However, one vestige of positivity remains: if ${F: \Omega \rightarrow {\bf R}}$ is non-negative, then so is

$\displaystyle \int_{\Omega^p} [F]_{1 \rightarrow p}\ d\mu^p = p (\int_\Omega F\ d\mu) (\int_\Omega\ d\mu)^{p-1}.$

One can wonder what the point is to all of this abstract formalism and how it relates to the rest of mathematics. For me, this formalism originated implicitly in an old paper I wrote with Jon Bennett and Tony Carbery on the multilinear restriction and Kakeya conjectures, though we did not have a good language for working with it at the time, instead working first with the case of natural number exponents ${p}$ and appealing to a general extrapolation theorem to then obtain various identities in the fractional ${p}$ case. The connection between these fractional dimensional integrals and more traditional integrals ultimately arises from the simple identity

$\displaystyle (\int_\Omega\ d\mu)^p = \int_{\Omega^p}\ d\mu^p$

(where the right-hand side should be viewed as the fractional dimensional integral of the unit ${[1]_{0 \rightarrow p}}$ against ${\mu^p}$). As such, one can manipulate ${p^{th}}$ powers of ordinary integrals using the machinery of fractional dimensional integrals. A key lemma in this regard is

Lemma 3 (Differentiation formula) Suppose that a positive measure ${\mu = \mu(t)}$ on ${\Omega}$ depends on some parameter ${t}$ and varies by the formula

$\displaystyle \frac{d}{dt} \mu(t) = a(t) \mu(t) \ \ \ \ \ (9)$

for some function ${a(t): \Omega \rightarrow {\bf R}}$. Let ${p}$ be any real or complex number. Then, assuming sufficient smoothness and integrability of all quantities involved, we have

$\displaystyle \frac{d}{dt} \int_{\Omega^p} F^{(p)}\ d\mu(t)^p = \int_{\Omega^p} F^{(p)} [a(t)]_{1 \rightarrow p}\ d\mu(t)^p \ \ \ \ \ (10)$

for all ${F^{(p)} \in L(\Omega^p)_{sym}}$ that are independent of ${t}$. If we allow ${F^{(p)}(t)}$ to now depend on ${t}$ also, then we have the more general total derivative formula

$\displaystyle \frac{d}{dt} \int_{\Omega^p} F^{(p)}(t)\ d\mu(t)^p \ \ \ \ \ (11)$

$\displaystyle = \int_{\Omega^p} \frac{d}{dt} F^{(p)}(t) + F^{(p)}(t) [a(t)]_{1 \rightarrow p}\ d\mu(t)^p,$

again assuming sufficient amounts of smoothness and regularity.

Proof: We just prove (10), as (11) then follows by same argument used to prove the usual product rule. By linearity it suffices to verify this identity in the case ${F^{(p)} = [F^{(k)}]_{k \rightarrow p}}$ for some symmetric function ${F^{(k)} \in L(\Omega^k)_{sym}}$ for a natural number ${k}$. By (6), the left-hand side of (10) is then

$\displaystyle \frac{d}{dt} [\binom{p}{k} (\int_{\Omega^k} F^{(k)}\ d\mu(t)^k) (\int_\Omega\ d\mu(t))^{p-k}]. \ \ \ \ \ (12)$

Differentiating under the integral sign using (9) we have

$\displaystyle \frac{d}{dt} \int_\Omega\ d\mu(t) = \int_\Omega\ a(t)\ d\mu(t)$

and similarly

$\displaystyle \frac{d}{dt} \int_{\Omega^k} F^{(k)}\ d\mu(t)^k = \int_{\Omega^k} F^{(k)}(a_1+\dots+a_k)\ d\mu(t)^k$

where ${a_1,\dots,a_k}$ are the standard ${k}$ copies of ${a = a(t)}$ on ${\Omega^k}$:

$\displaystyle a_j(\omega_1,\dots,\omega_k) := a(\omega_j).$

By the product rule, we can thus expand (12) as

$\displaystyle \binom{p}{k} (\int_{\Omega^k} F^{(k)}(a_1+\dots+a_k)\ d\mu^k ) (\int_\Omega\ d\mu)^{p-k}$

$\displaystyle + \binom{p}{k} (p-k) (\int_{\Omega^k} F^{(k)}\ d\mu^k) (\int_\Omega\ a\ d\mu) (\int_\Omega\ d\mu)^{p-k-1}$

where we have suppressed the dependence on ${t}$ for brevity. Since ${\binom{p}{k} (p-k) = \binom{p}{k+1} (k+1)}$, we can write this expression using (6) as

$\displaystyle \int_{\Omega^p} [F^{(k)} (a_1 + \dots + a_k)]_{k \rightarrow p} + [ F^{(k)} \ast a ]_{k+1 \rightarrow p}\ d\mu^p$

where ${F^{(k)} \ast a \in L(\Omega^{k+1})_{sym}}$ is the symmetric function

$\displaystyle F^{(k)} \ast a(\omega_1,\dots,\omega_{k+1}) := \sum_{j=1}^{k+1} F^{(k)}(\omega_1,\dots,\omega_{j-1},\omega_{j+1} \dots \omega_{k+1}) a(\omega_j).$

But from (2) one has

$\displaystyle [F^{(k)} (a_1 + \dots + a_k)]_{k \rightarrow p} + [ F^{(k)} \ast a ]_{k+1 \rightarrow p} = [F^{(k)}]_{k \rightarrow p} [a]_{1 \rightarrow p}$

and the claim follows. $\Box$

Remark 4 It is also instructive to prove this lemma in the special case when ${p}$ is a natural number, in which case the fractional dimensional integral ${\int_{\Omega^p} F^{(p)}\ d\mu(t)^p}$ can be interpreted as a classical integral. In this case, the identity (10) is immediate from applying the product rule to (9) to conclude that

$\displaystyle \frac{d}{dt} d\mu(t)^p = [a(t)]_{1 \rightarrow p} d\mu(t)^p.$

One could in fact derive (10) for arbitrary real or complex ${p}$ from the case when ${p}$ is a natural number by an extrapolation argument; see the appendix of my paper with Bennett and Carbery for details.

Let us give a simple PDE application of this lemma as illustration:

Proposition 5 (Heat flow monotonicity) Let ${u: [0,+\infty) \times {\bf R}^d \rightarrow {\bf R}}$ be a solution to the heat equation ${u_t = \Delta u}$ with initial data ${\mu_0}$ a rapidly decreasing finite non-negative Radon measure, or more explicitly

$\displaystyle u(t,x) = \frac{1}{(4\pi t)^{d/2}} \int_{{\bf R}^d} e^{-|x-y|^2/4t}\ d\mu_0(y)$

for al ${t>0}$. Then for any ${p>0}$, the quantity

$\displaystyle Q_p(t) := t^{\frac{d}{2} (p-1)} \int_{{\bf R}^d} u(t,x)^p\ dx$

is monotone non-decreasing in ${t \in (0,+\infty)}$ for ${1 < p < \infty}$, constant for ${p=1}$, and monotone non-increasing for ${0 < p < 1}$.

Proof: By a limiting argument we may assume that ${d\mu_0}$ is absolutely continuous, with Radon-Nikodym derivative a test function; this is more than enough regularity to justify the arguments below.

For any ${(t,x) \in (0,+\infty) \times {\bf R}^d}$, let ${\mu(t,x)}$ denote the Radon measure

$\displaystyle d\mu(t,x)(y) := \frac{1}{(4\pi)^{d/2}} e^{-|x-y|^2/4t}\ d\mu_0(y).$

Then the quantity ${Q_p(t)}$ can be written as a fractional dimensional integral

$\displaystyle Q_p(t) = t^{-d/2} \int_{{\bf R}^d} \int_{({\bf R}^d)^p}\ d\mu(t,x)^p\ dx.$

Observe that

$\displaystyle \frac{\partial}{\partial t} d\mu(t,x) = \frac{|x-y|^2}{4t^2} d\mu(t,x)$

and thus by Lemma 3 and the product rule

$\displaystyle \frac{d}{dt} Q_p(t) = -\frac{d}{2t} Q_p(t) + t^{-d/2} \int_{{\bf R}^d} \int_{({\bf R}^d)^p} [\frac{|x-y|^2}{4t^2}]_{1 \rightarrow p} d\mu(t,x)^p\ dx \ \ \ \ \ (13)$

where we use ${y}$ for the variable of integration in the factor space ${{\bf R}^d}$ of ${({\bf R}^d)^p}$.

To simplify this expression we will take advantage of integration by parts in the ${x}$ variable. Specifically, in any direction ${x_j}$, we have

$\displaystyle \frac{\partial}{\partial x_j} d\mu(t,x) = -\frac{x_j-y_j}{2t} d\mu(t,x)$

and hence by Lemma 3

$\displaystyle \frac{\partial}{\partial x_j} \int_{({\bf R}^d)^p}\ d\mu(t,x)^p\ dx = - \int_{({\bf R}^d)^p} [\frac{x_j-y_j}{2t}]_{1 \rightarrow p}\ d\mu(t,x)^p\ dx.$

Multiplying by ${x_j}$ and integrating by parts, we see that

$\displaystyle d Q_p(t) = \int_{{\bf R}^d} \int_{({\bf R}^d)^p} x_j [\frac{x_j-y_j}{2t}]_{1 \rightarrow p}\ d\mu(t,x)^p\ dx$

$\displaystyle = \int_{{\bf R}^d} \int_{({\bf R}^d)^p} x_j [\frac{x_j-y_j}{2t}]_{1 \rightarrow p}\ d\mu(t,x)^p\ dx$

where we use the Einstein summation convention in ${j}$. Similarly, if ${F_j(y)}$ is any reasonable function depending only on ${y}$, we have

$\displaystyle \frac{\partial}{\partial x_j} \int_{({\bf R}^d)^p}[F_j(y)]_{1 \rightarrow p}\ d\mu(t,x)^p\ dx$

$\displaystyle = - \int_{({\bf R}^d)^p} [F_j(y)]_{1 \rightarrow p} [\frac{x_j-y_j}{2t}]_{1 \rightarrow p}\ d\mu(t,x)^p\ dx$

and hence on integration by parts

$\displaystyle 0 = \int_{{\bf R}^d} \int_{({\bf R}^d)^p} [F_j(y) \frac{x_j-y_j}{2t}]_{1 \rightarrow p}\ d\mu(t,x)^p\ dx.$

We conclude that

$\displaystyle \frac{d}{2t} Q_p(t) = t^{-d/2} \int_{{\bf R}^d} \int_{({\bf R}^d)^p} (x_j - [F_j(y)]_{1 \rightarrow p}) [\frac{(x_j-y_j)}{4t}]_{1 \rightarrow p} d\mu(t,x)^p\ dx$

and thus by (13)

$\displaystyle \frac{d}{dt} Q_p(t) = \frac{1}{4t^{\frac{d}{2}+2}} \int_{{\bf R}^d} \int_{({\bf R}^d)^p}$

$\displaystyle [(x_j-y_j)(x_j-y_j)]_{1 \rightarrow p} - (x_j - [F_j(y)]_{1 \rightarrow p}) [x_j - y_j]_{1 \rightarrow p}\ d\mu(t,x)^p\ dx.$

The choice of ${F_j}$ that then achieves the most cancellation turns out to be ${F_j(y) = \frac{1}{p} y_j}$ (this cancels the terms that are linear or quadratic in the ${x_j}$), so that ${x_j - [F_j(y)]_{1 \rightarrow p} = \frac{1}{p} [x_j - y_j]_{1 \rightarrow p}}$. Repeating the calculations establishing (7), one has

$\displaystyle \int_{({\bf R}^d)^p} [(x_j-y_j)(x_j-y_j)]_{1 \rightarrow p}\ d\mu^p = p \mathop{\bf E} |x-Y|^2 (\int_{{\bf R}^d}\ d\mu)^{p}$

and

$\displaystyle \int_{({\bf R}^d)^p} [x_j-y_j]_{1 \rightarrow p} [x_j-y_j]_{1 \rightarrow p}\ d\mu^p$

$\displaystyle = (p \mathbf{Var}(x-Y) + p^2 |\mathop{\bf E} x-Y|^2) (\int_{{\bf R}^d}\ d\mu)^{p}$

where ${Y}$ is the random variable drawn from ${{\bf R}^d}$ with the normalised probability measure ${\mu / \int_{{\bf R}^d}\ d\mu}$. Since ${\mathop{\bf E} |x-Y|^2 = \mathbf{Var}(x-Y) + |\mathop{\bf E} x-Y|^2}$, one thus has

$\displaystyle \frac{d}{dt} Q_p(t) = (p-1) \frac{1}{4t^{\frac{d}{2}+2}} \int_{{\bf R}^d} \mathbf{Var}(x-Y) (\int_{{\bf R}^d}\ d\mu)^{p}\ dx. \ \ \ \ \ (14)$

This expression is clearly non-negative for ${p>1}$, equal to zero for ${p=1}$, and positive for ${0 < p < 1}$, giving the claim. (One could simplify ${\mathbf{Var}(x-Y)}$ here as ${\mathbf{Var}(Y)}$ if desired, though it is not strictly necessary to do so for the proof.) $\Box$

Remark 6 As with Remark 4, one can also establish the identity (14) first for natural numbers ${p}$ by direct computation avoiding the theory of fractional dimensional integrals, and then extrapolate to the case of more general values of ${p}$. This particular identity is also simple enough that it can be directly established by integration by parts without much difficulty, even for fractional values of ${p}$.

A more complicated version of this argument establishes the non-endpoint multilinear Kakeya inequality (without any logarithmic loss in a scale parameter ${R}$); this was established in my previous paper with Jon Bennett and Tony Carbery, but using the “natural number ${p}$ first” approach rather than using the current formalism of fractional dimensional integration. However, the arguments can be translated into this formalism without much difficulty; we do so below the fold. (To simplify the exposition slightly we will not address issues of establishing enough regularity and integrability to justify all the manipulations, though in practice this can be done by standard limiting arguments.)

Joni Teräväinen and I have just uploaded to the arXiv our paper “Value patterns of multiplicative functions and related sequences“, submitted to Forum of Mathematics, Sigma. This paper explores how to use recent technology on correlations of multiplicative (or nearly multiplicative functions), such as the “entropy decrement method”, in conjunction with techniques from additive combinatorics, to establish new results on the sign patterns of functions such as the Liouville function ${\lambda}$. For instance, with regards to length 5 sign patterns

$\displaystyle (\lambda(n+1),\dots,\lambda(n+5)) \in \{-1,+1\}^5$

of the Liouville function, we can now show that at least ${24}$ of the ${32}$ possible sign patterns in ${\{-1,+1\}^5}$ occur with positive upper density. (Conjecturally, all of them do so, and this is known for all shorter sign patterns, but unfortunately ${24}$ seems to be the limitation of our methods.)

The Liouville function can be written as ${\lambda(n) = e^{2\pi i \Omega(n)/2}}$, where ${\Omega(n)}$ is the number of prime factors of ${n}$ (counting multiplicity). One can also consider the variant ${\lambda_3(n) = e^{2\pi i \Omega(n)/3}}$, which is a completely multiplicative function taking values in the cube roots of unity ${\{1, \omega, \omega^2\}}$. Here we are able to show that all ${27}$ sign patterns in ${\{1,\omega,\omega^2\}}$ occur with positive lower density as sign patterns ${(\lambda_3(n+1), \lambda_3(n+2), \lambda_3(n+3))}$ of this function. The analogous result for ${\lambda}$ was already known (see this paper of Matomäki, Radziwiłł, and myself), and in that case it is even known that all sign patterns occur with equal logarithmic density ${1/8}$ (from this paper of myself and Teräväinen), but these techniques barely fail to handle the ${\lambda_3}$ case by itself (largely because the “parity” arguments used in the case of the Liouville function no longer control three-point correlations in the ${\lambda_3}$ case) and an additional additive combinatorial tool is needed. After applying existing technology (such as entropy decrement methods), the problem roughly speaking reduces to locating patterns ${a \in A_1, a+r \in A_2, a+2r \in A_3}$ for a certain partition ${G = A_1 \cup A_2 \cup A_3}$ of a compact abelian group ${G}$ (think for instance of the unit circle ${G={\bf R}/{\bf Z}}$, although the general case is a bit more complicated, in particular if ${G}$ is disconnected then there is a certain “coprimality” constraint on ${r}$, also we can allow the ${A_1,A_2,A_3}$ to be replaced by any ${A_{c_1}, A_{c_2}, A_{c_3}}$ with ${c_1+c_2+c_3}$ divisible by ${3}$), with each of the ${A_i}$ having measure ${1/3}$. An inequality of Kneser just barely fails to guarantee the existence of such patterns, but by using an inverse theorem for Kneser’s inequality in this previous paper of mine we are able to identify precisely the obstruction for this method to work, and rule it out by an ad hoc method.

The same techniques turn out to also make progress on some conjectures of Erdös-Pomerance and Hildebrand regarding patterns of the largest prime factor ${P^+(n)}$ of a natural number ${n}$. For instance, we improve results of Erdös-Pomerance and of Balog demonstrating that the inequalities

$\displaystyle P^+(n+1) < P^+(n+2) < P^+(n+3)$

and

$\displaystyle P^+(n+1) > P^+(n+2) > P^+(n+3)$

each hold for infinitely many ${n}$, by demonstrating the stronger claims that the inequalities

$\displaystyle P^+(n+1) < P^+(n+2) < P^+(n+3) > P^+(n+4)$

and

$\displaystyle P^+(n+1) > P^+(n+2) > P^+(n+3) < P^+(n+4)$

each hold for a set of ${n}$ of positive lower density. As a variant, we also show that we can find a positive density set of ${n}$ for which

$\displaystyle P^+(n+1), P^+(n+2), P^+(n+3) > n^\gamma$

for any fixed ${\gamma < e^{-1/3} = 0.7165\dots}$ (this improves on a previous result of Hildebrand with ${e^{-1/3}}$ replaced by ${e^{-1/2} = 0.6065\dots}$. A number of other results of this type are also obtained in this paper.

In order to obtain these sorts of results, one needs to extend the entropy decrement technology from the setting of multiplicative functions to that of what we call “weakly stable sets” – sets ${A}$ which have some multiplicative structure, in the sense that (roughly speaking) there is a set ${B}$ such that for all small primes ${p}$, the statements ${n \in A}$ and ${pn \in B}$ are roughly equivalent to each other. For instance, if ${A}$ is a level set ${A = \{ n: \omega(n) = 0 \hbox{ mod } 3 \}}$, one would take ${B = \{ n: \omega(n) = 1 \hbox{ mod } 3 \}}$; if instead ${A}$ is a set of the form ${\{ n: P^+(n) \geq n^\gamma\}}$, then one can take ${B=A}$. When one has such a situation, then very roughly speaking, the entropy decrement argument then allows one to estimate a one-parameter correlation such as

$\displaystyle {\bf E}_n 1_A(n+1) 1_A(n+2) 1_A(n+3)$

with a two-parameter correlation such as

$\displaystyle {\bf E}_n {\bf E}_p 1_B(n+p) 1_B(n+2p) 1_B(n+3p)$

(where we will be deliberately vague as to how we are averaging over ${n}$ and ${p}$), and then the use of the “linear equations in primes” technology of Ben Green, Tamar Ziegler, and myself then allows one to replace this average in turn by something like

$\displaystyle {\bf E}_n {\bf E}_r 1_B(n+r) 1_B(n+2r) 1_B(n+3r)$

where ${r}$ is constrained to be not divisible by small primes but is otherwise quite arbitrary. This latter average can then be attacked by tools from additive combinatorics, such as translation to a continuous group model (using for instance the Furstenberg correspondence principle) followed by tools such as Kneser’s inequality (or inverse theorems to that inequality).