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

Rachel Greenfeld and I have just uploaded to the arXiv our announcement “A counterexample to the periodic tiling conjecture“. This is an announcement of a longer paper that we are currently in the process of writing up (and hope to release in a few weeks), in which we disprove the periodic tiling conjecture of Grünbaum-Shephard and Lagarias-Wang. This conjecture can be formulated in both discrete and continuous settings:

Conjecture 1 (Discrete periodic tiling conjecture) Suppose that ${F \subset {\bf Z}^d}$ is a finite set that tiles ${{\bf Z}^d}$ by translations (i.e., ${{\bf Z}^d}$ can be partitioned into translates of ${F}$). Then ${F}$ also tiles ${{\bf Z}^d}$ by translations periodically (i.e., the set of translations can be taken to be a periodic subset of ${{\bf Z}^d}$).

Conjecture 2 (Continuous periodic tiling conjecture) Suppose that ${\Omega \subset {\bf R}^d}$ is a bounded measurable set of positive measure that tiles ${{\bf R}^d}$ by translations up to null sets. Then ${\Omega}$ also tiles ${{\bf R}^d}$ by translations periodically up to null sets.

The discrete periodic tiling conjecture can be easily established for ${d=1}$ by the pigeonhole principle (as first observed by Newman), and was proven for ${d=2}$ by Bhattacharya (with a new proof given by Greenfeld and myself). The continuous periodic tiling conjecture was established for ${d=1}$ by Lagarias and Wang. By an old observation of Hao Wang, one of the consequences of the (discrete) periodic tiling conjecture is that the problem of determining whether a given finite set ${F \subset {\bf Z}^d}$ tiles by translations is (algorithmically and logically) decidable.

On the other hand, once one allows tilings by more than one tile, it is well known that aperiodic tile sets exist, even in dimension two – finite collections of discrete or continuous tiles that can tile the given domain by translations, but not periodically. Perhaps the most famous examples of such aperiodic tilings are the Penrose tilings, but there are many other constructions; for instance, there is a construction of Ammann, Grümbaum, and Shephard of eight tiles in ${{\bf Z}^2}$ which tile aperiodically. Recently, Rachel and I constructed a pair of tiles in ${{\bf Z}^d}$ that tiled a periodic subset of ${{\bf Z}^d}$ aperiodically (in fact we could even make the tiling question logically undecidable in ZFC).

Our main result is then

Theorem 3 Both the discrete and continuous periodic tiling conjectures fail for sufficiently large ${d}$. Also, there is a finite abelian group ${G_0}$ such that the analogue of the discrete periodic tiling conjecture for ${{\bf Z}^2 \times G_0}$ is false.

This suggests that the techniques used to prove the discrete periodic conjecture in ${{\bf Z}^2}$ are already close to the limit of their applicability, as they cannot handle even virtually two-dimensional discrete abelian groups such as ${{\bf Z}^2 \times G_0}$. The main difficulty is in constructing the counterexample in the ${{\bf Z}^2 \times G_0}$ setting.

The approach starts by adapting some of the methods of a previous paper of Rachel and myself. The first step is make the problem easier to solve by disproving a “multiple periodic tiling conjecture” instead of the traditional periodic tiling conjecture. At present, Theorem 3 asserts the existence of a “tiling equation” ${A \oplus F = {\bf Z}^2 \times G_0}$ (where one should think of ${F}$ and ${G_0}$ as given, and the tiling set ${A}$ is known), which admits solutions, all of which are non-periodic. It turns out that it is enough to instead assert the existence of a system

$\displaystyle A \oplus F^{(m)} = {\bf Z}^2 \times G_0, m=1,\dots,M$

of tiling equations, which admits solutions, all of which are non-periodic. This is basically because one can “stack” together a system of tiling equations into an essentially equivalent single tiling equation in a slightly larger group. The advantage of this reformulation is that it creates a “tiling language”, in which each sentence ${A \oplus F^{(m)} = {\bf Z}^2 \times G_0}$ in the language expresses a different type of constraint on the unknown set ${A}$. The strategy then is to locate a non-periodic set ${A}$ which one can try to “describe” by sentences in the tiling language that are obeyed by this non-periodic set, and which are “structured” enough that one can capture their non-periodic nature through enough of these sentences.

It is convenient to replace sets by functions, so that this tiling language can be translated to a more familiar language, namely the language of (certain types of) functional equations. The key point here is that the tiling equation

$\displaystyle A \oplus (\{0\} \times H) = G \times H$

for some abelian groups ${G, H}$ is precisely asserting that ${A}$ is a graph

$\displaystyle A = \{ (x, f(x)): x \in G \}$

of some function ${f: G \rightarrow H}$ (this sometimes referred to as the “vertical line test” in U.S. undergraduate math classes). Using this translation, it is possible to encode a variety of functional equations relating one or more functions ${f_i: G \rightarrow H}$ taking values in some finite group ${H}$ (such as a cyclic group).

The non-periodic behaviour that we ended up trying to capture was that of a certain “${p}$-adically structured function” ${f_p: {\bf Z} \rightarrow ({\bf Z}/p{\bf Z})^\times}$ associated to some fixed and sufficiently large prime ${p}$ (in fact for our arguments any prime larger than ${48}$, e.g., ${p=53}$, would suffice), defined by the formula

$\displaystyle f_p(n) := \frac{n}{p^{\nu_p(n)}} \hbox{ mod } p$

for ${n \neq 0}$ and ${f_p(0)=1}$, where ${\nu_p(n)}$ is the number of times ${p}$ divides ${n}$. In other words, ${f_p(n)}$ is the last non-zero digit in the base ${p}$ expansion of ${n}$ (with the convention that the last non-zero digit of ${0}$ is ${1}$). This function is not periodic, and yet obeys a lot of functional equations; for instance, one has ${f_p(pn) = f_p(n)}$ for all ${n}$, and also ${f_p(pn+j)=j}$ for ${j=1,\dots,p-1}$ (and in fact these two equations, together with the condition ${f_p(0)=1}$, completely determine ${f_p}$). Here is what the function ${f_p}$ looks like (for ${p=5}$):

It turns out that we cannot describe this one-dimensional non-periodic function directly via tiling equations. However, we can describe two-dimensional non-periodic functions such as ${(n,m) \mapsto f_p(An+Bm+C)}$ for some coefficients ${A,B,C}$ via a suitable system of tiling equations. A typical such function looks like this:

A feature of this function is that when one restricts to a row or diagonal of such a function, the resulting one-dimensional function exhibits “${p}$-adic structure” in the sense that it behaves like a rescaled version of ${f_p}$; see the announcement for a precise version of this statement. It turns out that the converse is essentially true: after excluding some degenerate solutions in which the function is constant along one or more of the columns, all two-dimensional functions which exhibit ${p}$-adic structure along (non-vertical) lines must behave like one of the functions ${(n,m) \mapsto f_p(An+Bm+C)}$ mentioned earlier, and in particular is non-periodic. The proof of this result is strongly reminiscent of the type of reasoning needed to solve a Sudoku puzzle, and so we have adopted some Sudoku-like terminology in our arguments to provide intuition and visuals. One key step is to perform a shear transformation to the puzzle so that many of the rows become constant, as displayed in this example,

and then perform a “Tetris” move of eliminating the constant rows to arrive at a secondary Sudoku puzzle which one then analyzes in turn:

It is the iteration of this procedure that ultimately generates the non-periodic ${p}$-adic structure.

Let ${G}$ be a finite set of order ${N}$; in applications ${G}$ will be typically something like a finite abelian group, such as the cyclic group ${{\bf Z}/N{\bf Z}}$. Let us define a ${1}$-bounded function to be a function ${f: G \rightarrow {\bf C}}$ such that ${|f(n)| \leq 1}$ for all ${n \in G}$. There are many seminorms ${\| \|}$ of interest that one places on functions ${f: G \rightarrow {\bf C}}$ that are bounded by ${1}$ on ${1}$-bounded functions, such as the Gowers uniformity seminorms ${\| \|_k}$ for ${k \geq 1}$ (which are genuine norms for ${k \geq 2}$). All seminorms in this post will be implicitly assumed to obey this property.

In additive combinatorics, a significant role is played by inverse theorems, which abstractly take the following form for certain choices of seminorm ${\| \|}$, some parameters ${\eta, \varepsilon>0}$, and some class ${{\mathcal F}}$ of ${1}$-bounded functions:

Theorem 1 (Inverse theorem template) If ${f}$ is a ${1}$-bounded function with ${\|f\| \geq \eta}$, then there exists ${F \in {\mathcal F}}$ such that ${|\langle f, F \rangle| \geq \varepsilon}$, where ${\langle,\rangle}$ denotes the usual inner product

$\displaystyle \langle f, F \rangle := {\bf E}_{n \in G} f(n) \overline{F(n)}.$

Informally, one should think of ${\eta}$ as being somewhat small but fixed independently of ${N}$, ${\varepsilon}$ as being somewhat smaller but depending only on ${\eta}$ (and on the seminorm), and ${{\mathcal F}}$ as representing the “structured functions” for these choices of parameters. There is some flexibility in exactly how to choose the class ${{\mathcal F}}$ of structured functions, but intuitively an inverse theorem should become more powerful when this class is small. Accordingly, let us define the ${(\eta,\varepsilon)}$-entropy of the seminorm ${\| \|}$ to be the least cardinality of ${{\mathcal F}}$ for which such an inverse theorem holds. Seminorms with low entropy are ones for which inverse theorems can be expected to be a useful tool. This concept arose in some discussions I had with Ben Green many years ago, but never appeared in print, so I decided to record some observations we had on this concept here on this blog.

Lebesgue norms ${\| f\|_{L^p} := ({\bf E}_{n \in G} |f(n)|^p)^{1/p}}$ for ${1 < p < \infty}$ have exponentially large entropy (and so inverse theorems are not expected to be useful in this case):

Proposition 2 (${L^p}$ norm has exponentially large inverse entropy) Let ${1 < p < \infty}$ and ${0 < \eta < 1}$. Then the ${(\eta,\eta^p/4)}$-entropy of ${\| \|_{L^p}}$ is at most ${(1+8/\eta^p)^N}$. Conversely, for any ${\varepsilon>0}$, the ${(\eta,\varepsilon)}$-entropy of ${\| \|_{L^p}}$ is at least ${\exp( c \varepsilon^2 N)}$ for some absolute constant ${c>0}$.

Proof: If ${f}$ is ${1}$-bounded with ${\|f\|_{L^p} \geq \eta}$, then we have

$\displaystyle |\langle f, |f|^{p-2} f \rangle| \geq \eta^p$

and hence by the triangle inequality we have

$\displaystyle |\langle f, F \rangle| \geq \eta^p/2$

where ${F}$ is either the real or imaginary part of ${|f|^{p-2} f}$, which takes values in ${[-1,1]}$. If we let ${\tilde F}$ be ${F}$ rounded to the nearest multiple of ${\eta^p/4}$, then by the triangle inequality again we have

$\displaystyle |\langle f, \tilde F \rangle| \geq \eta^p/4.$

There are only at most ${1+8/\eta^p}$ possible values for each value ${\tilde F(n)}$ of ${\tilde F}$, and hence at most ${(1+8/\eta^p)^N}$ possible choices for ${\tilde F}$. This gives the first claim.

Now suppose that there is an ${(\eta,\varepsilon)}$-inverse theorem for some ${{\mathcal F}}$ of cardinality ${M}$. If we let ${f}$ be a random sign function (so the ${f(n)}$ are independent random variables taking values in ${-1,+1}$ with equal probability), then there is a random ${F \in {\mathcal F}}$ such that

$\displaystyle |\langle f, F \rangle| \geq \varepsilon$

and hence by the pigeonhole principle there is a deterministic ${F \in {\mathcal F}}$ such that

$\displaystyle {\bf P}( |\langle f, F \rangle| \geq \varepsilon ) \geq 1/M.$

On the other hand, from the Hoeffding inequality one has

$\displaystyle {\bf P}( |\langle f, F \rangle| \geq \varepsilon ) \ll \exp( - c \varepsilon^2 N )$

for some absolute constant ${c}$, hence

$\displaystyle M \geq \exp( c \varepsilon^2 N )$

as claimed. $\Box$

Most seminorms of interest in additive combinatorics, such as the Gowers uniformity norms, are bounded by some finite ${L^p}$ norm thanks to Hölder’s inequality, so from the above proposition and the obvious monotonicity properties of entropy, we conclude that all Gowers norms on finite abelian groups ${G}$ have at most exponential inverse theorem entropy. But we can do significantly better than this:

• For the ${U^1}$ seminorm ${\|f\|_{U^1(G)} := |{\bf E}_{n \in G} f(n)|}$, one can simply take ${{\mathcal F} = \{1\}}$ to consist of the constant function ${1}$, and the ${(\eta,\eta)}$-entropy is clearly equal to ${1}$ for any ${0 < \eta < 1}$.
• For the ${U^2}$ norm, the standard Fourier-analytic inverse theorem asserts that if ${\|f\|_{U^2(G)} \geq \eta}$ then ${|\langle f, e(\xi \cdot) \rangle| \geq \eta^2}$ for some Fourier character ${\xi \in \hat G}$. Thus the ${(\eta,\eta^2)}$-entropy is at most ${N}$.
• For the ${U^k({\bf Z}/N{\bf Z})}$ norm on cyclic groups for ${k > 2}$, the inverse theorem proved by Green, Ziegler, and myself gives an ${(\eta,\varepsilon)}$-inverse theorem for some ${\varepsilon \gg_{k,\eta} 1}$ and ${{\mathcal F}}$ consisting of nilsequences ${n \mapsto F(g(n) \Gamma)}$ for some filtered nilmanifold ${G/\Gamma}$ of degree ${k-1}$ in a finite collection of cardinality ${O_{\eta,k}(1)}$, some polynomial sequence ${g: {\bf Z} \rightarrow G}$ (which was subsequently observed by Candela-Sisask (see also Manners) that one can choose to be ${N}$-periodic), and some Lipschitz function ${F: G/\Gamma \rightarrow {\bf C}}$ of Lipschitz norm ${O_{\eta,k}(1)}$. By the Arzela-Ascoli theorem, the number of possible ${F}$ (up to uniform errors of size at most ${\varepsilon/2}$, say) is ${O_{\eta,k}(1)}$. By standard arguments one can also ensure that the coefficients of the polynomial ${g}$ are ${O_{\eta,k}(1)}$, and then by periodicity there are only ${O(N^{O_{\eta,k}(1)}}$ such polynomials. As a consequence, the ${(\eta,\varepsilon)}$-entropy is of polynomial size ${O_{\eta,k}( N^{O_{\eta,k}(1)} )}$ (a fact that seems to have first been implicitly observed in Lemma 6.2 of this paper of Frantzikinakis; thanks to Ben Green for this reference). One can obtain more precise dependence on ${\eta,k}$ using the quantitative version of this inverse theorem due to Manners; back of the envelope calculations using Section 5 of that paper suggest to me that one can take ${\varepsilon = \eta^{O_k(1)}}$ to be polynomial in ${\eta}$ and the entropy to be of the order ${O_k( N^{\exp(\exp(\eta^{-O_k(1)}))} )}$, or alternatively one can reduce the entropy to ${O_k( \exp(\exp(\eta^{-O_k(1)})) N^{\eta^{-O_k(1)}})}$ at the cost of degrading ${\varepsilon}$ to ${1/\exp\exp( O(\eta^{-O(1)}))}$.
• If one replaces the cyclic group ${{\bf Z}/N{\bf Z}}$ by a vector space ${{\bf F}_p^n}$ over some fixed finite field ${{\bf F}_p}$ of prime order (so that ${N=p^n}$), then the inverse theorem of Ziegler and myself (available in both high and low characteristic) allows one to obtain an ${(\eta,\varepsilon)}$-inverse theorem for some ${\varepsilon \gg_{k,\eta} 1}$ and ${{\mathcal F}}$ the collection of non-classical degree ${k-1}$ polynomial phases from ${{\bf F}_p^n}$ to ${S^1}$, which one can normalize to equal ${1}$ at the origin, and then by the classification of such polynomials one can calculate that the ${(\eta,\varepsilon)}$ entropy is of quasipolynomial size ${\exp( O_{p,k}(n^{k-1}) ) = \exp( O_{p,k}( \log^{k-1} N ) )}$ in ${N}$. By using the recent work of Gowers and Milicevic, one can make the dependence on ${p,k}$ here more precise, but we will not perform these calcualtions here.
• For the ${U^3(G)}$ norm on an arbitrary finite abelian group, the recent inverse theorem of Jamneshan and myself gives (after some calculations) a bound of the polynomial form ${O( q^{O(n^2)} N^{\exp(\eta^{-O(1)})})}$ on the ${(\eta,\varepsilon)}$-entropy for some ${\varepsilon \gg \eta^{O(1)}}$, which one can improve slightly to ${O( q^{O(n^2)} N^{\eta^{-O(1)}})}$ if one degrades ${\varepsilon}$ to ${1/\exp(\eta^{-O(1)})}$, where ${q}$ is the maximal order of an element of ${G}$, and ${n}$ is the rank (the number of elements needed to generate ${G}$). This bound is polynomial in ${N}$ in the cyclic group case and quasipolynomial in general.

For general finite abelian groups ${G}$, we do not yet have an inverse theorem of comparable power to the ones mentioned above that give polynomial or quasipolynomial upper bounds on the entropy. However, there is a cheap argument that at least gives some subexponential bounds:

Proposition 3 (Cheap subexponential bound) Let ${k \geq 2}$ and ${0 < \eta < 1/2}$, and suppose that ${G}$ is a finite abelian group of order ${N \geq \eta^{-C_k}}$ for some sufficiently large ${C_k}$. Then the ${(\eta,c_k \eta^{O_k(1)})}$-complexity of ${\| \|_{U^k(G)}}$ is at most ${O( \exp( \eta^{-O_k(1)} N^{1 - \frac{k+1}{2^k-1}} ))}$.

Proof: (Sketch) We use a standard random sampling argument, of the type used for instance by Croot-Sisask or Briet-Gopi (thanks to Ben Green for this latter reference). We can assume that ${N \geq \eta^{-C_k}}$ for some sufficiently large ${C_k>0}$, since otherwise the claim follows from Proposition 2.

Let ${A}$ be a random subset of ${{\bf Z}/N{\bf Z}}$ with the events ${n \in A}$ being iid with probability ${0 < p < 1}$ to be chosen later, conditioned to the event ${|A| \leq 2pN}$. Let ${f}$ be a ${1}$-bounded function. By a standard second moment calculation, we see that with probability at least ${1/2}$, we have

$\displaystyle \|f\|_{U^k(G)}^{2^k} = {\bf E}_{n, h_1,\dots,h_k \in G} f(n) \prod_{\omega \in \{0,1\}^k \backslash \{0\}} {\mathcal C}^{|\omega|} \frac{1}{p} 1_A f(n + \omega \cdot h)$

$\displaystyle + O((\frac{1}{N^{k+1} p^{2^k-1}})^{1/2}).$

Thus, by the triangle inequality, if we choose ${p := C \eta^{-2^{k+1}/(2^k-1)} / N^{\frac{k+1}{2^k-1}}}$ for some sufficiently large ${C = C_k > 0}$, then for any ${1}$-bounded ${f}$ with ${\|f\|_{U^k(G)} \geq \eta/2}$, one has with probability at least ${1/2}$ that

$\displaystyle |{\bf E}_{n, h_1,\dots,h_k \i2^n G} f(n) \prod_{\omega \in \{0,1\}^k \backslash \{0\}} {\mathcal C}^{|\omega|} \frac{1}{p} 1_A f(n + \omega \cdot h)|$

$\displaystyle \geq \eta^{2^k}/2^{2^k+1}.$

We can write the left-hand side as ${|\langle f, F \rangle|}$ where ${F}$ is the randomly sampled dual function

$\displaystyle F(n) := {\bf E}_{n, h_1,\dots,h_k \in G} f(n) \prod_{\omega \in \{0,1\}^k \backslash \{0\}} {\mathcal C}^{|\omega|+1} \frac{1}{p} 1_A f(n + \omega \cdot h).$

Unfortunately, ${F}$ is not ${1}$-bounded in general, but we have

$\displaystyle \|F\|_{L^2(G)}^2 \leq {\bf E}_{n, h_1,\dots,h_k ,h'_1,\dots,h'_k \in G}$

$\displaystyle \prod_{\omega \in \{0,1\}^k \backslash \{0\}} \frac{1}{p} 1_A(n + \omega \cdot h) \frac{1}{p} 1_A(n + \omega \cdot h')$

and the right-hand side can be shown to be ${1+o(1)}$ on the average, so we can condition on the event that the right-hand side is ${O(1)}$ without significant loss in falure probability.

If we then let ${\tilde f_A}$ be ${1_A f}$ rounded to the nearest Gaussian integer multiple of ${\eta^{2^k}/2^{2^{10k}}}$ in the unit disk, one has from the triangle inequality that

$\displaystyle |\langle f, \tilde F \rangle| \geq \eta^{2^k}/2^{2^k+2}$

where ${\tilde F}$ is the discretised randomly sampled dual function

$\displaystyle \tilde F(n) := {\bf E}_{n, h_1,\dots,h_k \in G} f(n) \prod_{\omega \in \{0,1\}^k \backslash \{0\}} {\mathcal C}^{|\omega|+1} \frac{1}{p} \tilde f_A(n + \omega \cdot h).$

For any given ${A}$, there are at most ${2np}$ places ${n}$ where ${\tilde f_A(n)}$ can be non-zero, and in those places there are ${O_k( \eta^{-2^{k}})}$ possible values for ${\tilde f_A(n)}$. Thus, if we let ${{\mathcal F}_A}$ be the collection of all possible ${\tilde f_A}$ associated to a given ${A}$, the cardinality of this set is ${O( \exp( \eta^{-O_k(1)} N^{1 - \frac{k+1}{2^k-1}} ) )}$, and for any ${f}$ with ${\|f\|_{U^k(G)} \geq \eta/2}$, we have

$\displaystyle \sup_{\tilde F \in {\mathcal F}_A} |\langle f, \tilde F \rangle| \geq \eta^{2^k}/2^{k+2}$

with probability at least ${1/2}$.

Now we remove the failure probability by independent resampling. By rounding to the nearest Gaussian integer multiple of ${c_k \eta^{2^k}}$ in the unit disk for a sufficiently small ${c_k>0}$, one can find a family ${{\mathcal G}}$ of cardinality ${O( \eta^{-O_k(N)})}$ consisting of ${1}$-bounded functions ${\tilde f}$ of ${U^k(G)}$ norm at least ${\eta/2}$ such that for every ${1}$-bounded ${f}$ with ${\|f\|_{U^k(G)} \geq \eta}$ there exists ${\tilde f \in {\mathcal G}}$ such that

$\displaystyle \|f-\tilde f\|_{L^\infty(G)} \leq \eta^{2^k}/2^{k+3}.$

Now, let ${A_1,\dots,A_M}$ be independent samples of ${A}$ for some ${M}$ to be chosen later. By the preceding discussion, we see that with probability at least ${1 - 2^{-M}}$, we have

$\displaystyle \sup_{\tilde F \in \bigcup_{j=1}^M {\mathcal F}_{A_j}} |\langle \tilde f, \tilde F \rangle| \geq \eta^{2^k}/2^{k+2}$

for any given ${\tilde f \in {\mathcal G}}$, so by the union bound, if we choose ${M = \lfloor C N \log \frac{1}{\eta} \rfloor}$ for a large enough ${C = C_k}$, we can find ${A_1,\dots,A_M}$ such that

$\displaystyle \sup_{\tilde F \in \bigcup_{j=1}^M {\mathcal F}_{A_j}} |\langle \tilde f, \tilde F \rangle| \geq \eta^{2^k}/2^{k+2}$

for all ${\tilde f \in {\mathcal G}}$, and hence y the triangle inequality

$\displaystyle \sup_{\tilde F \in \bigcup_{j=1}^M {\mathcal F}_{A_j}} |\langle f, \tilde F \rangle| \geq \eta^{2^k}/2^{k+3}.$

Taking ${{\mathcal F}}$ to be the union of the ${{\mathcal F}_{A_j}}$ (applying some truncation and rescaling to these ${L^2}$-bounded functions to make them ${L^\infty}$-bounded, and then ${1}$-bounded), we obtain the claim. $\Box$

One way to obtain lower bounds on the inverse theorem entropy is to produce a collection of almost orthogonal functions with large norm. More precisely:

Proposition 4 Let ${\| \|}$ be a seminorm, let ${0 < \varepsilon \leq \eta < 1}$, and suppose that one has a collection ${f_1,\dots,f_M}$ of ${1}$-bounded functions such that for all ${i=1,\dots,M}$, ${\|f_i\| \geq \eta}$ one has ${|\langle f_i, f_j \rangle| \leq \varepsilon^2/2}$ for all but at most ${L}$ choices of ${j \in \{1,\dots,M\}}$ for all distinct ${i,j \in \{1,\dots,M\}}$. Then the ${(\eta, \varepsilon)}$-entropy of ${\| \|}$ is at least ${\varepsilon^2 M / 2L}$.

Proof: Suppose we have an ${(\eta,\varepsilon)}$-inverse theorem with some family ${{\mathcal F}}$. Then for each ${i=1,\dots,M}$ there is ${F_i \in {\mathcal F}}$ such that ${|\langle f_i, F_i \rangle| \geq \varepsilon}$. By the pigeonhole principle, there is thus ${F \in {\mathcal F}}$ such that ${|\langle f_i, F \rangle| \geq \varepsilon}$ for all ${i}$ in a subset ${I}$ of ${\{1,\dots,M\}}$ of cardinality at least ${M/|{\mathcal F}|}$:

$\displaystyle |I| \geq M / |{\mathcal F}|.$

We can sum this to obtain

$\displaystyle |\sum_{i \in I} c_i \langle f_i, F \rangle| \geq |I| \varepsilon$

for some complex numbers ${c_i}$ of unit magnitude. By Cauchy-Schwarz, this implies

$\displaystyle \| \sum_{i \in I} c_i f_i \|_{L^2(G)}^2 \geq |I|^2 \varepsilon^2$

and hence by the triangle inequality

$\displaystyle \sum_{i,j \in I} |\langle f_i, f_j \rangle| \geq |I|^2 \varepsilon^2.$

On the other hand, by hypothesis we can bound the left-hand side by ${|I| (L + \varepsilon^2 |I|/2)}$. Rearranging, we conclude that

$\displaystyle |I| \leq 2 L / \varepsilon^2$

and hence

$\displaystyle |{\mathcal F}| \geq \varepsilon^2 M / 2L$

giving the claim. $\Box$

Thus for instance:

• For the ${U^2(G)}$ norm, one can take ${f_1,\dots,f_M}$ to be the family of linear exponential phases ${n \mapsto e(\xi \cdot n)}$ with ${M = N}$ and ${L=1}$, and obtain a linear lower bound of ${\varepsilon^2 N/2}$ for the ${(\eta,\varepsilon)}$-entropy, thus matching the upper bound of ${N}$ up to constants when ${\varepsilon}$ is fixed.
• For the ${U^k({\bf Z}/N{\bf Z})}$ norm, a similar calculation using polynomial phases of degree ${k-1}$, combined with the Weyl sum estimates, gives a lower bound of ${\gg_{k,\varepsilon} N^{k-1}}$ for the ${(\eta,\varepsilon)}$-entropy for any fixed ${\eta,\varepsilon}$; by considering nilsequences as well, together with nilsequence equidistribution theory, one can replace the exponent ${k-1}$ here by some quantity that goes to infinity as ${\eta \rightarrow 0}$, though I have not attempted to calculate the exact rate.
• For the ${U^k({\bf F}_p^n)}$ norm, another similar calculation using polynomial phases of degree ${k-1}$ should give a lower bound of ${\gg_{p,k,\eta,\varepsilon} \exp( c_{p,k,\eta,\varepsilon} n^{k-1} )}$ for the ${(\eta,\varepsilon)}$-entropy, though I have not fully performed the calculation.

We close with one final example. Suppose ${G}$ is a product ${G = A \times B}$ of two sets ${A,B}$ of cardinality ${\asymp \sqrt{N}}$, and we consider the Gowers box norm

$\displaystyle \|f\|_{\Box^2(G)}^4 := {\bf E}_{a,a' \in A; b,b' \in B} f(a,b) \overline{f}(a,b') \overline{f}(a',b) f(a,b).$

One possible choice of class ${{\mathcal F}}$ here are the indicators ${1_{U \times V}}$ of “rectangles” ${U \times V}$ with ${U \subset A}$, ${V \subset B}$ (cf. this previous blog post on cut norms). By standard calculations, one can use this class to show that the ${(\eta, \eta^4/10)}$-entropy of ${\| \|_{\Box^2(G)}}$ is ${O( \exp( O(\sqrt{N}) )}$, and a variant of the proof of the second part of Proposition 2 shows that this is the correct order of growth in ${N}$. In contrast, a modification of Proposition 3 only gives an upper bound of the form ${O( \exp( O( N^{2/3} ) ) )}$ (the bottleneck is ensuring that the randomly sampled dual functions stay bounded in ${L^2}$), which shows that while this cheap bound is not optimal, it can still broadly give the correct “type” of bound (specifically, intermediate growth between polynomial and exponential).

Asgar Jamneshan and myself have just uploaded to the arXiv our preprint “The inverse theorem for the ${U^3}$ Gowers uniformity norm on arbitrary finite abelian groups: Fourier-analytic and ergodic approaches“. This paper, which is a companion to another recent paper of ourselves and Or Shalom, studies the inverse theory for the third Gowers uniformity norm

$\displaystyle \| f \|_{U^3(G)}^8 = {\bf E}_{h_1,h_2,h_3,x \in G} \Delta_{h_1} \Delta_{h_2} \Delta_{h_3} f(x)$

on an arbitrary finite abelian group ${G}$, where ${\Delta_h f(x) := f(x+h) \overline{f(x)}}$ is the multiplicative derivative. Our main result is as follows:

Theorem 1 (Inverse theorem for ${U^3(G)}$) Let ${G}$ be a finite abelian group, and let ${f: G \rightarrow {\bf C}}$ be a ${1}$-bounded function with ${\|f\|_{U^3(G)} \geq \eta}$ for some ${0 < \eta \leq 1/2}$. Then:
• (i) (Correlation with locally quadratic phase) There exists a regular Bohr set ${B(S,\rho) \subset G}$ with ${|S| \ll \eta^{-O(1)}}$ and ${\exp(-\eta^{-O(1)}) \ll \rho \leq 1/2}$, a locally quadratic function ${\phi: B(S,\rho) \rightarrow {\bf R}/{\bf Z}}$, and a function ${\xi: G \rightarrow \hat G}$ such that

$\displaystyle {\bf E}_{x \in G} |{\bf E}_{h \in B(S,\rho)} f(x+h) e(-\phi(h)-\xi(x) \cdot h)| \gg \eta^{O(1)}.$

• (ii) (Correlation with nilsequence) There exists an explicit degree two filtered nilmanifold ${H/\Lambda}$ of dimension ${O(\eta^{-O(1)})}$, a polynomial map ${g: G \rightarrow H/\Lambda}$, and a Lipschitz function ${F: H/\Lambda \rightarrow {\bf C}}$ of constant ${O(\exp(\eta^{-O(1)}))}$ such that

$\displaystyle |{\bf E}_{x \in G} f(x) \overline{F}(g(x))| \gg \exp(-\eta^{-O(1)}).$

Such a theorem was proven by Ben Green and myself in the case when ${|G|}$ was odd, and by Samorodnitsky in the ${2}$-torsion case ${G = {\bf F}_2^n}$. In all cases one uses the “higher order Fourier analysis” techniques introduced by Gowers. After some now-standard manipulations (using for instance what is now known as the Balog-Szemerédi-Gowers lemma), one arrives (for arbitrary ${G}$) at an estimate that is roughly of the form

$\displaystyle |{\bf E}_{x \in G} {\bf E}_{h,k \in B(S,\rho)} f(x+h+k) b(x,k) b(x,h) e(-B(h,k))| \gg \eta^{O(1)}$

where ${b}$ denotes various ${1}$-bounded functions whose exact values are not too important, and ${B: B(S,\rho) \times B(S,\rho) \rightarrow {\bf R}/{\bf Z}}$ is a symmetric locally bilinear form. The idea is then to “integrate” this form by expressing it in the form

$\displaystyle B(h,k) = \phi(h+k) - \phi(h) - \phi(k) \ \ \ \ \ (1)$

for some locally quadratic ${\phi: B(S,\rho) \rightarrow {\bf C}}$; this then allows us to write the above correlation as

$\displaystyle |{\bf E}_{x \in G} {\bf E}_{h,k \in B(S,\rho)} f(x+h+k) e(-\phi(h+k)) b(x,k) b(x,h)| \gg \eta^{O(1)}$

(after adjusting the ${b}$ functions suitably), and one can now conclude part (i) of the above theorem using some linear Fourier analysis. Part (ii) follows by encoding locally quadratic phase functions as nilsequences; for this we adapt an algebraic construction of Manners.

So the key step is to obtain a representation of the form (1), possibly after shrinking the Bohr set ${B(S,\rho)}$ a little if needed. This has been done in the literature in two ways:

• When ${|G|}$ is odd, one has the ability to divide by ${2}$, and on the set ${2 \cdot B(S,\frac{\rho}{10}) = \{ 2x: x \in B(S,\frac{\rho}{10})\}}$ one can establish (1) with ${\phi(h) := B(\frac{1}{2} h, h)}$. (This is similar to how in single variable calculus the function ${x \mapsto \frac{1}{2} x^2}$ is a function whose second derivative is equal to ${1}$.)
• When ${G = {\bf F}_2^n}$, then after a change of basis one can take the Bohr set ${B(S,\rho)}$ to be ${{\bf F}_2^m}$ for some ${m}$, and the bilinear form can be written in coordinates as

$\displaystyle B(h,k) = \sum_{1 \leq i,j \leq m} a_{ij} h_i k_j / 2 \hbox{ mod } 1$

for some ${a_{ij} \in {\bf F}_2}$ with ${a_{ij}=a_{ji}}$. The diagonal terms ${a_{ii}}$ cause a problem, but by subtracting off the rank one form ${(\sum_{i=1}^m a_{ii} h_i) ((\sum_{i=1}^m a_{ii} k_i) / 2}$ one can write

$\displaystyle B(h,k) = \sum_{1 \leq i,j \leq m} b_{ij} h_i k_j / 2 \hbox{ mod } 1$

on the orthogonal complement of ${(a_{11},\dots,a_{mm})}$ for some coefficients ${b_{ij}=b_{ji}}$ which now vanish on the diagonal: ${b_{ii}=0}$. One can now obtain (1) on this complement by taking

$\displaystyle \phi(h) := \sum_{1 \leq i < j \leq m} b_{ij} h_i h_k / 2 \hbox{ mod } 1.$

In our paper we can now treat the case of arbitrary finite abelian groups ${G}$, by means of the following two new ingredients:

• (i) Using some geometry of numbers, we can lift the group ${G}$ to a larger (possibly infinite, but still finitely generated) abelian group ${G_S}$ with a projection map ${\pi: G_S \rightarrow G}$, and find a globally bilinear map ${\tilde B: G_S \times G_S \rightarrow {\bf R}/{\bf Z}}$ on the latter group, such that one has a representation

$\displaystyle B(\pi(x), \pi(y)) = \tilde B(x,y) \ \ \ \ \ (2)$

of the locally bilinear form ${B}$ by the globally bilinear form ${\tilde B}$ when ${x,y}$ are close enough to the origin.
• (ii) Using an explicit construction, one can show that every globally bilinear map ${\tilde B: G_S \times G_S \rightarrow {\bf R}/{\bf Z}}$ has a representation of the form (1) for some globally quadratic function ${\tilde \phi: G_S \rightarrow {\bf R}/{\bf Z}}$.

To illustrate (i), consider the Bohr set ${B(S,1/10) = \{ x \in {\bf Z}/N{\bf Z}: \|x/N\|_{{\bf R}/{\bf Z}} < 1/10\}}$ in ${G = {\bf Z}/N{\bf Z}}$ (where ${\|\|_{{\bf R}/{\bf Z}}}$ denotes the distance to the nearest integer), and consider a locally bilinear form ${B: B(S,1/10) \times B(S,1/10) \rightarrow {\bf R}/{\bf Z}}$ of the form ${B(x,y) = \alpha x y \hbox{ mod } 1}$ for some real number ${\alpha}$ and all integers ${x,y \in (-N/10,N/10)}$ (which we identify with elements of ${G}$. For generic ${\alpha}$, this form cannot be extended to a globally bilinear form on ${G}$; however if one lifts ${G}$ to the finitely generated abelian group

$\displaystyle G_S := \{ (x,\theta) \in {\bf Z}/N{\bf Z} \times {\bf R}: \theta = x/N \hbox{ mod } 1 \}$

(with projection map ${\pi: (x,\theta) \mapsto x}$) and introduces the globally bilinear form ${\tilde B: G_S \times G_S \rightarrow {\bf R}/{\bf Z}}$ by the formula

$\displaystyle \tilde B((x,\theta),(y,\sigma)) = N^2 \alpha \theta \sigma \hbox{ mod } 1$

then one has (2) when ${\theta,\sigma}$ lie in the interval ${(-1/10,1/10)}$. A similar construction works for higher rank Bohr sets.

To illustrate (ii), the key case turns out to be when ${G_S}$ is a cyclic group ${{\bf Z}/N{\bf Z}}$, in which case ${\tilde B}$ will take the form

$\displaystyle \tilde B(x,y) = \frac{axy}{N} \hbox{ mod } 1$

for some integer ${a}$. One can then check by direct construction that (1) will be obeyed with

$\displaystyle \tilde \phi(x) = \frac{a \binom{x}{2}}{N} - \frac{a x \binom{N}{2}}{N^2} \hbox{ mod } 1$

regardless of whether ${N}$ is even or odd. A variant of this construction also works for ${{\bf Z}}$, and the general case follows from a short calculation verifying that the claim (ii) for any two groups ${G_S, G'_S}$ implies the corresponding claim (ii) for the product ${G_S \times G'_S}$.

This concludes the Fourier-analytic proof of Theorem 1. In this paper we also give an ergodic theory proof of (a qualitative version of) Theorem 1(ii), using a correspondence principle argument adapted from this previous paper of Ziegler, and myself. Basically, the idea is to randomly generate a dynamical system on the group ${G}$, by selecting an infinite number of random shifts ${g_1, g_2, \dots \in G}$, which induces an action of the infinitely generated free abelian group ${{\bf Z}^\omega = \bigcup_{n=1}^\infty {\bf Z}^n}$ on ${G}$ by the formula

$\displaystyle T^h x := x + \sum_{i=1}^\infty h_i g_i.$

Much as the law of large numbers ensures the almost sure convergence of Monte Carlo integration, one can show that this action is almost surely ergodic (after passing to a suitable Furstenberg-type limit ${X}$ where the size of ${G}$ goes to infinity), and that the dynamical Host-Kra-Gowers seminorms of that system coincide with the combinatorial Gowers norms of the original functions. One is then well placed to apply an inverse theorem for the third Host-Kra-Gowers seminorm ${U^3(X)}$ for ${{\bf Z}^\omega}$-actions, which was accomplished in the companion paper to this one. After doing so, one almost gets the desired conclusion of Theorem 1(ii), except that after undoing the application of the Furstenberg correspondence principle, the map ${g: G \rightarrow H/\Lambda}$ is merely an almost polynomial rather than a polynomial, which roughly speaking means that instead of certain derivatives of ${g}$ vanishing, they instead are merely very small outside of a small exceptional set. To conclude we need to invoke a “stability of polynomials” result, which at this level of generality was first established by Candela and Szegedy (though we also provide an independent proof here in an appendix), which roughly speaking asserts that every approximate polynomial is close in measure to an actual polynomial. (This general strategy is also employed in the Candela-Szegedy paper, though in the absence of the ergodic inverse theorem input that we rely upon here, the conclusion is weaker in that the filtered nilmanifold ${H/\Lambda}$ is replaced with a general space known as a “CFR nilspace”.)

This transference principle approach seems to work well for the higher step cases (for instance, the stability of polynomials result is known in arbitrary degree); the main difficulty is to establish a suitable higher step inverse theorem in the ergodic theory setting, which we hope to do in future research.

Rachel Greenfeld and I have just uploaded to the arXiv our preprint “Undecidable translational tilings with only two tiles, or one nonabelian tile“. This paper studies the following question: given a finitely generated group ${G}$, a (periodic) subset ${E}$ of ${G}$, and finite sets ${F_1,\dots,F_J}$ in ${G}$, is it possible to tile ${E}$ by translations ${a_j+F_j}$ of the tiles ${F_1,\dots,F_J}$? That is to say, is there a solution ${\mathrm{X}_1 = A_1, \dots, \mathrm{X}_J = A_J}$ to the (translational) tiling equation

$\displaystyle (\mathrm{X}_1 \oplus F_1) \uplus \dots \uplus (\mathrm{X}_J \oplus F_J) = E \ \ \ \ \ (1)$

for some subsets ${A_1,\dots,A_J}$ of ${G}$, where ${A \oplus F}$ denotes the set of sums ${\{a+f: a \in A, f \in F \}}$ if the sums ${a+f}$ are all disjoint (and is undefined otherwise), and ${\uplus}$ denotes disjoint union. (One can also write the tiling equation in the language of convolutions as ${1_{\mathrm{X}_1} * 1_{F_1} + \dots + 1_{\mathrm{X}_J} * 1_{F_J} = 1_E}$.)

A bit more specifically, the paper studies the decidability of the above question. There are two slightly different types of decidability one could consider here:

• Logical decidability. For a given ${G, E, J, F_1,\dots,F_J}$, one can ask whether the solvability of the tiling equation (1) is provable or disprovable in ZFC (where we encode all the data ${G, E, F_1,\dots,F_J}$ by appropriate constructions in ZFC). If this is the case we say that the tiling equation (1) (or more precisely, the solvability of this equation) is logically decidable, otherwise it is logically undecidable.
• Algorithmic decidability. For data ${G,E,J, F_1,\dots,F_J}$ in some specified class (and encoded somehow as binary strings), one can ask whether the solvability of the tiling equation (1) can be correctly determined for all choices of data in this class by the output of some Turing machine that takes the data as input (encoded as a binary string) and halts in finite time, returning either YES if the equation can be solved or NO otherwise. If this is the case, we say the tiling problem of solving (1) for data in the given class is algorithmically decidable, otherwise it is algorithmically undecidable.

Note that the notion of logical decidability is “pointwise” in the sense that it pertains to a single choice of data ${G,E,J,F_1,\dots,F_J}$, whereas the notion of algorithmic decidability pertains instead to classes of data, and is only interesting when this class is infinite. Indeed, any tiling problem with a finite class of data is trivially decidable because one could simply code a Turing machine that is basically a lookup table that returns the correct answer for each choice of data in the class. (This is akin to how a student with a good memory could pass any exam if the questions are drawn from a finite list, merely by memorising an answer key for that list of questions.)

The two notions are related as follows: if a tiling problem (1) is algorithmically undecidable for some class of data, then the tiling equation must be logically undecidable for at least one choice of data for this class. For if this is not the case, one could algorithmically decide the tiling problem by searching for proofs or disproofs that the equation (1) is solvable for a given choice of data; the logical decidability of all such solvability questions will ensure that this algorithm always terminates in finite time.

One can use the Gödel completeness theorem to interpret logical decidability in terms of universes (also known as structures or models) of ZFC. In addition to the “standard” universe ${{\mathfrak U}}$ of sets that we believe satisfies the axioms of ZFC, there are also other “nonstandard” universes ${{\mathfrak U}^*}$ that also obey the axioms of ZFC. If the solvability of a tiling equation (1) is logically undecidable, this means that such a tiling exists in some universes of ZFC, but not in others.

(To continue the exam analogy, we thus see that a yes-no exam question is logically undecidable if the answer to the question is yes in some parallel universes, but not in others. A course syllabus is algorithmically undecidable if there is no way to prepare for the final exam for the course in a way that guarantees a perfect score (in the standard universe).)

Questions of decidability are also related to the notion of aperiodicity. For a given ${G, E, J, F_1,\dots,F_J}$, a tiling equation (1) is said to be aperiodic if the equation (1) is solvable (in the standard universe ${{\mathfrak U}}$ of ZFC), but none of the solutions (in that universe) are completely periodic (i.e., there are no solutions ${\mathrm{X}_1 = A_1,\dots, \mathrm{X}_J = A_J}$ where all of the ${A_1,\dots,A_J}$ are periodic). Perhaps the most well-known example of an aperiodic tiling (in the context of ${{\bf R}^2}$, and using rotations as well as translations) come from the Penrose tilings, but there are many others besides.

It was (essentially) observed by Hao Wang in the 1960s that if a tiling equation is logically undecidable, then it must necessarily be aperiodic. Indeed, if a tiling equation fails to be aperiodic, then (in the standard universe) either there is a periodic tiling, or there are no tilings whatsoever. In the former case, the periodic tiling can be used to give a finite proof that the tiling equation is solvable; in the latter case, the compactness theorem implies that there is some finite fragment of ${E}$ that is not compatible with being tiled by ${F_1,\dots,F_J}$, and this provides a finite proof that the tiling equation is unsolvable. Thus in either case the tiling equation is logically decidable.

This observation of Wang clarifies somewhat how logically undecidable tiling equations behave in the various universes of ZFC. In the standard universe, tilings exist, but none of them will be periodic. In nonstandard universes, tilings may or may not exist, and the tilings that do exist may be periodic (albeit with a nonstandard period); but there must be at least one universe in which no tiling exists at all.

In one dimension when ${G={\bf Z}}$ (or more generally ${G = {\bf Z} \times G_0}$ with ${G_0}$ a finite group), a simple pigeonholing argument shows that no tiling equations are aperiodic, and hence all tiling equations are decidable. However the situation changes in two dimensions. In 1966, Berger (a student of Wang) famously showed that there exist tiling equations (1) in the discrete plane ${E = G = {\bf Z}^2}$ that are aperiodic, or even logically undecidable; in fact he showed that the tiling problem in this case (with arbitrary choices of data ${J, F_1,\dots,F_J}$) was algorithmically undecidable. (Strictly speaking, Berger established this for a variant of the tiling problem known as the domino problem, but later work of Golomb showed that the domino problem could be easily encoded within the tiling problem.) This was accomplished by encoding the halting problem for Turing machines into the tiling problem (or domino problem); the latter is well known to be algorithmically undecidable (and thus have logically undecidable instances), and so the latter does also. However, the number of tiles ${J}$ required for Berger’s construction was quite large: his construction of an aperiodic tiling required ${J = 20426}$ tiles, and his construction of a logically undecidable tiling required an even larger (and not explicitly specified) collection of tiles. Subsequent work by many authors did reduce the number of tiles required; in the ${E=G={\bf Z}^2}$ setting, the current world record for the fewest number of tiles in an aperiodic tiling is ${J=8}$ (due to Amman, Grunbaum, and Shephard) and for a logically undecidable tiling is ${J=11}$ (due to Ollinger). On the other hand, it is conjectured (see Grunbaum-Shephard and Lagarias-Wang) that one cannot lower ${J}$ all the way to ${1}$:

Conjecture 1 (Periodic tiling conjecture) If ${E}$ is a periodic subset of a finitely generated abelian group ${G}$, and ${F}$ is a finite subset of ${G}$, then the tiling equation ${\mathrm{X} \oplus F = E}$ is not aperiodic.

This conjecture is known to be true in two dimensions (by work of Bhattacharya when ${G=E={\bf Z}^2}$, and more recently by us when ${E \subset G = {\bf Z}^2}$), but remains open in higher dimensions. By the preceding discussion, the conjecture implies that every tiling equation with a single tile is logically decidable, and the problem of whether a given periodic set can be tiled by a single tile is algorithmically decidable.

In this paper we show on the other hand that aperiodic and undecidable tilings exist when ${J=2}$, at least if one is permitted to enlarge the group ${G}$ a bit:

Theorem 2 (Logically undecidable tilings)
• (i) There exists a group ${G}$ of the form ${G = {\bf Z}^2 \times G_0}$ for some finite abelian ${G_0}$, a subset ${E_0}$ of ${G_0}$, and finite sets ${F_1, F_2 \subset G}$ such that the tiling equation ${(\mathbf{X}_1 \oplus F_1) \uplus (\mathbf{X}_2 \oplus F_2) = {\bf Z}^2 \times E_0}$ is logically undecidable (and hence also aperiodic).
• (ii) There exists a dimension ${d}$, a periodic subset ${E}$ of ${{\bf Z}^d}$, and finite sets ${F_1, F_2 \subset G}$ such that tiling equation ${(\mathbf{X}_1 \oplus F_1) \uplus (\mathbf{X}_2 \oplus F_2) = E}$ is logically undecidable (and hence also aperiodic).
• (iii) There exists a non-abelian finite group ${G_0}$ (with the group law still written additively), a subset ${E_0}$ of ${G_0}$, and a finite set ${F \subset {\bf Z}^2 \times G_0}$ such that the nonabelian tiling equation ${\mathbf{X} \oplus F = {\bf Z}^2 \times E_0}$ is logically undecidable (and hence also aperiodic).

We also have algorithmic versions of this theorem. For instance, the algorithmic version of (i) is that the problem of determining solvability of the tiling equation ${(\mathbf{X}_1 \oplus F_1) \uplus (\mathbf{X}_2 \oplus F_2) = {\bf Z}^2 \times E_0}$ for a given choice of finite abelian group ${G_0}$, subset ${E_0}$ of ${G_0}$, and finite sets ${F_1, F_2 \subset {\bf Z}^2 \times G_0}$ is algorithmically undecidable. Similarly for (ii), (iii).

This result (together with a negative result discussed below) suggest to us that there is a significant qualitative difference in the ${J=1}$ theory of tiling by a single (abelian) tile, and the ${J \geq 2}$ theory of tiling with multiple tiles (or one non-abelian tile). (The positive results on the periodic tiling conjecture certainly rely heavily on the fact that there is only one tile, in particular there is a “dilation lemma” that is only available in this setting that is of key importance in the two dimensional theory.) It would be nice to eliminate the group ${G_0}$ from (i) (or to set ${d=2}$ in (ii)), but I think this would require a fairly significant modification of our methods.

Like many other undecidability results, the proof of Theorem 2 proceeds by a sequence of reductions, in which the undecidability of one problem is shown to follow from the undecidability of another, more “expressive” problem that can be encoded inside the original problem, until one reaches a problem that is so expressive that it encodes a problem already known to be undecidable. Indeed, all three undecidability results are ultimately obtained from Berger’s undecidability result on the domino problem.

The first step in increasing expressiveness is to observe that the undecidability of a single tiling equation follows from the undecidability of a system of tiling equations. More precisely, suppose we have non-empty finite subsets ${F_j^{(m)}}$ of a finitely generated group ${G}$ for ${j=1,\dots,J}$ and ${m=1,\dots,M}$, as well as periodic sets ${E^{(m)}}$ of ${G}$ for ${m=1,\dots,M}$, such that it is logically undecidable whether the system of tiling equations

$\displaystyle (\mathrm{X}_1 \oplus F_1^{(m)}) \uplus \dots \uplus (\mathrm{X}_J \oplus F_J^{(m)}) = E^{(m)} \ \ \ \ \ (2)$

for ${m=1,\dots,M}$ has no solution ${\mathrm{X}_1 = A_1,\dots, \mathrm{X}_J = A_J}$ in ${G}$. Then, for any ${N>M}$, we can “stack” these equations into a single tiling equation in the larger group ${G \times {\bf Z}/N{\bf Z}}$, and specifically to the equation

$\displaystyle (\mathrm{X}_1 \oplus F_1) \uplus \dots \uplus (\mathrm{X}_J \oplus F_J) = E \ \ \ \ \ (3)$

where

$\displaystyle F_j := \biguplus_{m=1}^M F_j^{(m)} \times \{m\}$

and

$\displaystyle E := \biguplus_{m=1}^M E^{(m)} \times \{m\}.$

It is a routine exercise to check that the system of equations (2) admits a solution in ${G}$ if and only if the single equation (3) admits a equation in ${G \times {\bf Z}/N{\bf Z}}$. Thus, to prove the undecidability of a single equation of the form (3) it suffices to establish undecidability of a system of the form (2); note here how the freedom to select the auxiliary group ${G_0}$ is important here.

We view systems of the form (2) as belonging to a kind of “language” in which each equation in the system is a “sentence” in the language imposing additional constraints on a tiling. One can now pick and choose various sentences in this language to try to encode various interesting problems. For instance, one can encode the concept of a function ${f: {\bf Z}^2 \rightarrow G_0}$ taking values in a finite group ${G_0}$ as a single tiling equation

$\displaystyle \mathrm{X} \oplus (\{0\} \times G_0) = {\bf Z}^2 \times G_0 \ \ \ \ \ (4)$

since the solutions to this equation are precisely the graphs

$\displaystyle \mathrm{X} = \{ (n, f(n)): n \in {\bf Z}^2 \}$

of a function ${f: {\bf Z}^2 \rightarrow G_0}$. By adding more tiling equations to this equation to form a larger system, we can start imposing additional constraints on this function ${f}$. For instance, if ${x+H}$ is a coset of some subgroup ${H}$ of ${G_0}$, we can impose the additional equation

$\displaystyle \mathrm{X} \oplus (\{0\} \times H) = {\bf Z}^2 \times (x+H) \ \ \ \ \ (5)$

to impose the additional constraint that ${f(n) \in x+H}$ for all ${n \in {\bf Z}^2}$, if we desire. If ${G_0}$ happens to contain two distinct elements ${1, -1}$, and ${h \in {\bf Z}^2}$, then the additional equation

$\displaystyle \mathrm{X} \oplus (\{0,h\} \times \{0\}) = {\bf Z}^2 \times \{-1,1\} \ \ \ \ \ (6)$

imposes the additional constraints that ${f(n) \in \{-1,1\}}$ for all ${n \in {\bf Z}^2}$, and additionally that

$\displaystyle f(n+h) = -f(n)$

for all ${n \in {\bf Z}^2}$.

This begins to resemble the equations that come up in the domino problem. Here one has a finite set of Wang tiles – unit squares ${T}$ where each of the four sides is colored with a color ${c_N(T), c_S(T), c_E(T), c_W(T)}$ (corresponding to the four cardinal directions North, South, East, and West) from some finite set ${{\mathcal C}}$ of colors. The domino problem is then to tile the plane with copies of these tiles in such a way that adjacent sides match. In terms of equations, one is seeking to find functions ${c_N, c_S, c_E, c_W: {\bf Z}^2 \rightarrow {\mathcal C}}$ obeying the pointwise constraint

$\displaystyle (c_N(n), c_S(n), c_E(n), c_W(n)) \in {\mathcal W} \ \ \ \ \ (7)$

for all ${n \in {\bf Z}^2}$ where ${{\mathcal W}}$ is the set of colors associated to the set of Wang tiles being used, and the matching constraints

$\displaystyle c_S(n+(0,1)) = c_N(n); \quad c_W(n+(1,0)) = c_E(n) \ \ \ \ \ (8)$

for all ${{\bf Z}^2}$. As it turns out, the pointwise constraint (7) can be encoded by tiling equations that are fancier versions of (4), (5), (6) that involve only one unknown tiling set ${{\mathrm X}}$, but in order to encode the matching constraints (8) we were forced to introduce a second tile (or work with nonabelian tiling equations). This appears to be an inherent feature of the method, since we found a partial rigidity result for tilings of one tile in one dimension that obstructs this encoding strategy from working when one only has one tile available. The result is as follows:

Proposition 3 (Swapping property) Consider the solutions to a tiling equation

$\displaystyle \mathrm{X} \oplus F = E \ \ \ \ \ (9)$

in a one-dimensional group ${G = {\bf Z} \times G_0}$ (with ${G_0}$ a finite abelian group, ${F}$ finite, and ${E}$ periodic). Suppose there are two solutions ${\mathrm{X} = A_0, \mathrm{X} = A_1}$ to this equation that agree on the left in the sense that

$\displaystyle A_0 \cap (\{0, -1, -2, \dots\} \times G_0) = A_1 \cap (\{0, -1, -2, \dots\} \times G_0).$

For any function ${\omega: {\bf Z} \rightarrow \{0,1\}}$, define the “swap” ${A_\omega}$ of ${A_0}$ and ${A_1}$ to be the set

$\displaystyle A_\omega := \{ (n, g): n \in {\bf Z}, (n,g) \in A_{\omega(n)} \}$

Then ${A_\omega}$ also solves the equation (9).

One can think of ${A_0}$ and ${A_1}$ as “genes” with “nucleotides” ${\{ g \in G_0: (n,g) \in A_0\}}$, ${\{ g \in G_0: (n,g) \in A_1\}}$ at each position ${n \in {\bf Z}}$, and ${A_\omega}$ is a new gene formed by choosing one of the nucleotides from the “parent” genes ${A_0}$, ${A_1}$ at each position. The above proposition then says that the solutions to the equation (9) must be closed under “genetic transfer” among any pair of genes that agree on the left. This seems to present an obstruction to trying to encode equation such as

$\displaystyle c(n+1) = c'(n)$

for two functions ${c, c': {\bf Z} \rightarrow \{-1,1\}}$ (say), which is a toy version of the matching constraint (8), since the class of solutions to this equation turns out not to obey this swapping property. On the other hand, it is easy to encode such equations using two tiles instead of one, and an elaboration of this construction is used to prove our main theorem.

In the modern theory of higher order Fourier analysis, a key role are played by the Gowers uniformity norms ${\| \|_{U^k}}$ for ${k=1,2,\dots}$. For finitely supported functions ${f: {\bf Z} \rightarrow {\bf C}}$, one can define the (non-normalised) Gowers norm ${\|f\|_{\tilde U^k({\bf Z})}}$ by the formula

$\displaystyle \|f\|_{\tilde U^k({\bf Z})}^{2^k} := \sum_{n,h_1,\dots,h_k \in {\bf Z}} \prod_{\omega_1,\dots,\omega_k \in \{0,1\}} {\mathcal C}^{\omega_1+\dots+\omega_k} f(x+\omega_1 h_1 + \dots + \omega_k h_k)$

where ${{\mathcal C}}$ denotes complex conjugation, and then on any discrete interval ${[N] = \{1,\dots,N\}}$ and any function ${f: [N] \rightarrow {\bf C}}$ we can then define the (normalised) Gowers norm

$\displaystyle \|f\|_{U^k([N])} := \| f 1_{[N]} \|_{\tilde U^k({\bf Z})} / \|1_{[N]} \|_{\tilde U^k({\bf Z})}$

where ${f 1_{[N]}: {\bf Z} \rightarrow {\bf C}}$ is the extension of ${f}$ by zero to all of ${{\bf Z}}$. Thus for instance

$\displaystyle \|f\|_{U^1([N])} = |\mathop{\bf E}_{n \in [N]} f(n)|$

(which technically makes ${\| \|_{U^1([N])}}$ a seminorm rather than a norm), and one can calculate

$\displaystyle \|f\|_{U^2([N])} \asymp (N \int_0^1 |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)|^4\ d\alpha)^{1/4} \ \ \ \ \ (1)$

where ${e(\theta) := e^{2\pi i \alpha}}$, and we use the averaging notation ${\mathop{\bf E}_{n \in A} f(n) = \frac{1}{|A|} \sum_{n \in A} f(n)}$.

The significance of the Gowers norms is that they control other multilinear forms that show up in additive combinatorics. Given any polynomials ${P_1,\dots,P_m: {\bf Z}^d \rightarrow {\bf Z}}$ and functions ${f_1,\dots,f_m: [N] \rightarrow {\bf C}}$, we define the multilinear form

$\displaystyle \Lambda^{P_1,\dots,P_m}(f_1,\dots,f_m) := \sum_{n \in {\bf Z}^d} \prod_{j=1}^m f_j 1_{[N]}(P_j(n)) / \sum_{n \in {\bf Z}^d} \prod_{j=1}^m 1_{[N]}(P_j(n))$

(assuming that the denominator is finite and non-zero). Thus for instance

$\displaystyle \Lambda^{\mathrm{n}}(f) = \mathop{\bf E}_{n \in [N]} f(n)$

$\displaystyle \Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}}(f,g) = (\mathop{\bf E}_{n \in [N]} f(n)) (\mathop{\bf E}_{n \in [N]} g(n))$

$\displaystyle \Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+2\mathrm{r}}(f,g,h) \asymp \mathop{\bf E}_{n \in [N]} \mathop{\bf E}_{r \in [-N,N]} f(n) g(n+r) h(n+2r)$

$\displaystyle \Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+\mathrm{r}^2}(f,g,h) \asymp \mathop{\bf E}_{n \in [N]} \mathop{\bf E}_{r \in [-N^{1/2},N^{1/2}]} f(n) g(n+r) h(n+r^2)$

where we view ${\mathrm{n}, \mathrm{r}}$ as formal (indeterminate) variables, and ${f,g,h: [N] \rightarrow {\bf C}}$ are understood to be extended by zero to all of ${{\bf Z}}$. These forms are used to count patterns in various sets; for instance, the quantity ${\Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+2\mathrm{r}}(1_A,1_A,1_A)}$ is closely related to the number of length three arithmetic progressions contained in ${A}$. Let us informally say that a form ${\Lambda^{P_1,\dots,P_m}(f_1,\dots,f_m)}$ is controlled by the ${U^k[N]}$ norm if the form is small whenever ${f_1,\dots,f_m: [N] \rightarrow {\bf C}}$ are ${1}$-bounded functions with at least one of the ${f_j}$ small in ${U^k[N]}$ norm. This definition was made more precise by Gowers and Wolf, who then defined the true complexity of a form ${\Lambda^{P_1,\dots,P_m}}$ to be the least ${s}$ such that ${\Lambda^{P_1,\dots,P_m}}$ is controlled by the ${U^{s+1}[N]}$ norm. For instance,
• ${\Lambda^{\mathrm{n}}}$ and ${\Lambda^{\mathrm{n}, \mathrm{n} + \mathrm{r}}}$ have true complexity ${0}$;
• ${\Lambda^{\mathrm{n}, \mathrm{n} + \mathrm{r}, \mathrm{n} + \mathrm{2r}}}$ has true complexity ${1}$;
• ${\Lambda^{\mathrm{n}, \mathrm{n} + \mathrm{r}, \mathrm{n} + \mathrm{2r}, \mathrm{n} + \mathrm{3r}}}$ has true complexity ${2}$;
• The form ${\Lambda^{\mathrm{n}, \mathrm{n}+2}}$ (which among other things could be used to count twin primes) has infinite true complexity (which is quite unfortunate for applications).
Roughly speaking, patterns of complexity ${1}$ or less are amenable to being studied by classical Fourier analytic tools (the Hardy-Littlewood circle method); patterns of higher complexity can be handled (in principle, at least) by the methods of higher order Fourier analysis; and patterns of infinite complexity are out of range of both methods and are generally quite difficult to study. See these recent slides of myself (or this video of the lecture) for some further discussion.

Gowers and Wolf formulated a conjecture on what this complexity should be, at least for linear polynomials ${P_1,\dots,P_m}$; Ben Green and I thought we had resolved this conjecture back in 2010, though it turned out there was a subtle gap in our arguments and we were only able to resolve the conjecture in a partial range of cases. However, the full conjecture was recently resolved by Daniel Altman.

The ${U^1}$ (semi-)norm is so weak that it barely controls any averages at all. For instance the average

$\displaystyle \Lambda^{2\mathrm{n}}(f) = \mathop{\bf E}_{n \in [N], \hbox{ even}} f(n)$

is not controlled by the ${U^1[N]}$ semi-norm: it is perfectly possible for a ${1}$-bounded function ${f: [N] \rightarrow {\bf C}}$ to even have vanishing ${U^1([N])}$ norm but have large value of ${\Lambda^{2\mathrm{n}}(f)}$ (consider for instance the parity function ${f(n) := (-1)^n}$).

Because of this, I propose inserting an additional norm in the Gowers uniformity norm hierarchy between the ${U^1}$ and ${U^2}$ norms, which I will call the ${U^{1^+}}$ (or “profinite ${U^1}$“) norm:

$\displaystyle \| f\|_{U^{1^+}[N]} := \frac{1}{N} \sup_P |\sum_{n \in P} f(n)| = \sup_P | \mathop{\bf E}_{n \in [N]} f 1_P(n)|$

where ${P}$ ranges over all arithmetic progressions in ${[N]}$. This can easily be seen to be a norm on functions ${f: [N] \rightarrow {\bf C}}$ that controls the ${U^1[N]}$ norm. It is also basically controlled by the ${U^2[N]}$ norm for ${1}$-bounded functions ${f}$; indeed, if ${P}$ is an arithmetic progression in ${[N]}$ of some spacing ${q \geq 1}$, then we can write ${P}$ as the intersection of an interval ${I}$ with a residue class modulo ${q}$, and from Fourier expansion we have

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_P(n) \ll \sup_\alpha |\mathop{\bf E}_{n \in [N]} f 1_I(n) e(\alpha n)|.$

If we let ${\psi}$ be a standard bump function supported on ${[-1,1]}$ with total mass and ${\delta>0}$ is a parameter then

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_I(n) e(\alpha n)$

$\displaystyle \ll |\mathop{\bf E}_{n \in [-N,2N]; h, k \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N})$

$\displaystyle 1_I(n+h+k) f(n+h+k) e(\alpha(n+h+k))|$

$\displaystyle \ll |\mathop{\bf E}_{n \in [-N,2N]; h, k \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N}) 1_I(n+k) f(n+h+k) e(\alpha(n+h+k))|$

$\displaystyle + \delta$

(extending ${f}$ by zero outside of ${[N]}$), as can be seen by using the triangle inequality and the estimate

$\displaystyle \mathop{\bf E}_{h \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N}) 1_I(n+h+k) - \mathop{\bf E}_{h \in [-N,N]} \frac{1}{\delta} \psi(\frac{h}{\delta N}) 1_I(n+k)$

$\displaystyle \ll (1 + \mathrm{dist}(n+k, I) / \delta N)^{-2}.$

After some Fourier expansion of ${\delta \psi(\frac{h}{\delta N})}$ we now have

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_P(n) \ll \frac{1}{\delta} \sup_{\alpha,\beta} |\mathop{\bf E}_{n \in [N]; h, k \in [-N,N]} e(\beta h + \alpha (n+h+k))$

$\displaystyle 1_P(n+k) f(n+h+k)| + \delta.$

Writing ${\alpha h + \alpha(n+h+k)}$ as a linear combination of ${n, n+h, n+k}$ and using the Gowers–Cauchy–Schwarz inequality, we conclude

$\displaystyle \mathop{\bf E}_{n \in [N]} f 1_P(n) \ll \frac{1}{\delta} \|f\|_{U^2([N])} + \delta$

hence on optimising in ${\delta}$ we have

$\displaystyle \| f\|_{U^{1^+}[N]} \ll \|f\|_{U^2[N]}^{1/2}.$

Forms which are controlled by the ${U^{1^+}}$ norm (but not ${U^1}$) would then have their true complexity adjusted to ${0^+}$ with this insertion.

The ${U^{1^+}}$ norm recently appeared implicitly in work of Peluse and Prendiville, who showed that the form ${\Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}, \mathrm{n}+\mathrm{r}^2}(f,g,h)}$ had true complexity ${0^+}$ in this notation (with polynomially strong bounds). [Actually, strictly speaking this control was only shown for the third function ${h}$; for the first two functions ${f,g}$ one needs to localize the ${U^{1^+}}$ norm to intervals of length ${\sim \sqrt{N}}$. But I will ignore this technical point to keep the exposition simple.] The weaker claim that ${\Lambda^{\mathrm{n}, \mathrm{n}+\mathrm{r}^2}(f,g)}$ has true complexity ${0^+}$ is substantially easier to prove (one can apply the circle method together with Gauss sum estimates).

The well known inverse theorem for the ${U^2}$ norm tells us that if a ${1}$-bounded function ${f}$ has ${U^2[N]}$ norm at least ${\eta}$ for some ${0 < \eta < 1}$, then there is a Fourier phase ${n \mapsto e(\alpha n)}$ such that

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \gg \eta^2;$

this follows easily from (1) and Plancherel’s theorem. Conversely, from the Gowers–Cauchy–Schwarz inequality one has

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \ll \|f\|_{U^2[N]}.$

For ${U^1[N]}$ one has a trivial inverse theorem; by definition, the ${U^1[N]}$ norm of ${f}$ is at least ${\eta}$ if and only if

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n)| \geq \eta.$

Thus the frequency ${\alpha}$ appearing in the ${U^2}$ inverse theorem can be taken to be zero when working instead with the ${U^1}$ norm.

For ${U^{1^+}}$ one has the intermediate situation in which the frequency ${\alpha}$ is not taken to be zero, but is instead major arc. Indeed, suppose that ${f}$ is ${1}$-bounded with ${\|f\|_{U^{1^+}[N]} \geq \eta}$, thus

$\displaystyle |\mathop{\bf E}_{n \in [N]} 1_P(n) f(n)| \geq \eta$

for some progression ${P}$. This forces the spacing ${q}$ of this progression to be ${\ll 1/\eta}$. We write the above inequality as

$\displaystyle |\mathop{\bf E}_{n \in [N]} 1_{n=b\ (q)} 1_I(n) f(n)| \geq \eta$

for some residue class ${b\ (q)}$ and some interval ${I}$. By Fourier expansion and the triangle inequality we then have

$\displaystyle |\mathop{\bf E}_{n \in [N]} e(-an/q) 1_I(n) f(n)| \geq \eta$

for some integer ${a}$. Convolving ${1_I}$ by ${\psi_\delta: n \mapsto \frac{1}{N\delta} \psi(\frac{n}{N\delta})}$ for ${\delta}$ a small multiple of ${\eta}$ and ${\psi}$ a Schwartz function of unit mass with Fourier transform supported on ${[-1,1]}$, we have

$\displaystyle |\mathop{\bf E}_{n \in [N]} e(-an/q) (1_I * \psi_\delta)(n) f(n)| \gg \eta.$

The Fourier transform ${\xi \mapsto \sum_n 1_I * \psi_\delta(n) e(- \xi n)}$ of ${1_I * \psi_\delta}$ is bounded by ${O(N)}$ and supported on ${[-\frac{1}{\delta N},\frac{1}{\delta N}]}$, thus by Fourier expansion and the triangle inequality we have

$\displaystyle |\mathop{\bf E}_{n \in [N]} e(-an/q) e(-\xi n) f(n)| \gg \eta^2$

for some ${\xi \in [-\frac{1}{\delta N},\frac{1}{\delta N}]}$, so in particular ${\xi = O(\frac{1}{\eta N})}$. Thus we have

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \gg \eta^2 \ \ \ \ \ (2)$

for some ${\alpha}$ of the major arc form ${\alpha = \frac{a}{q} + O(1/\eta)}$ with ${1 \leq q \leq 1/\eta}$. Conversely, for ${\alpha}$ of this form, some routine summation by parts gives the bound

$\displaystyle |\mathop{\bf E}_{n \in [N]} f(n) e(-\alpha n)| \ll \frac{q}{\eta} \|f\|_{U^{1^+}[N]} \ll \frac{1}{\eta^2} \|f\|_{U^{1^+}[N]}$

so if (2) holds for a ${1}$-bounded ${f}$ then one must have ${\|f\|_{U^{1^+}[N]} \gg \eta^4}$.

Here is a diagram showing some of the control relationships between various Gowers norms, multilinear forms, and duals of classes ${{\mathcal F}}$ of functions (where each class of functions ${{\mathcal F}}$ induces a dual norm ${\| f \|_{{\mathcal F}^*} := \sup_{\phi \in {\mathcal F}} \mathop{\bf E}_{n \in[N]} f(n) \overline{\phi(n)}}$:

Here I have included the three classes of functions that one can choose from for the ${U^3}$ inverse theorem, namely degree two nilsequences, bracket quadratic phases, and local quadratic phases, as well as the more narrow class of globally quadratic phases.

The Gowers norms have counterparts for measure-preserving systems ${(X,T,\mu)}$, known as Host-Kra seminorms. The ${U^1(X)}$ norm can be defined for ${f \in L^\infty(X)}$ as

$\displaystyle \|f\|_{U^1(X)} := \lim_{N \rightarrow \infty} \int_X |\mathop{\bf E}_{n \in [N]} T^n f|\ d\mu$

and the ${U^2}$ norm can be defined as

$\displaystyle \|f\|_{U^2(X)}^4 := \lim_{N \rightarrow \infty} \mathop{\bf E}_{n \in [N]} \| T^n f \overline{f} \|_{U^1(X)}^2.$

The ${U^1(X)}$ seminorm is orthogonal to the invariant factor ${Z^0(X)}$ (generated by the (almost everywhere) invariant measurable subsets of ${X}$) in the sense that a function ${f \in L^\infty(X)}$ has vanishing ${U^1(X)}$ seminorm if and only if it is orthogonal to all ${Z^0(X)}$-measurable (bounded) functions. Similarly, the ${U^2(X)}$ norm is orthogonal to the Kronecker factor ${Z^1(X)}$, generated by the eigenfunctions of ${X}$ (that is to say, those ${f}$ obeying an identity ${Tf = \lambda f}$ for some ${T}$-invariant ${\lambda}$); for ergodic systems, it is the largest factor isomorphic to rotation on a compact abelian group. In analogy to the Gowers ${U^{1^+}[N]}$ norm, one can then define the Host-Kra ${U^{1^+}(X)}$ seminorm by

$\displaystyle \|f\|_{U^{1^+}(X)} := \sup_{q \geq 1} \frac{1}{q} \lim_{N \rightarrow \infty} \int_X |\mathop{\bf E}_{n \in [N]} T^{qn} f|\ d\mu;$

it is orthogonal to the profinite factor ${Z^{0^+}(X)}$, generated by the periodic sets of ${X}$ (or equivalently, by those eigenfunctions whose eigenvalue is a root of unity); for ergodic systems, it is the largest factor isomorphic to rotation on a profinite abelian group.

The (classical) Möbius function ${\mu: {\bf N} \rightarrow {\bf Z}}$ is the unique function that obeys the classical Möbius inversion formula:

Proposition 1 (Classical Möbius inversion) Let ${f,g: {\bf N} \rightarrow A}$ be functions from the natural numbers to an additive group ${A}$. Then the following two claims are equivalent:
• (i) ${f(n) = \sum_{d|n} g(d)}$ for all ${n \in {\bf N}}$.
• (ii) ${g(n) = \sum_{d|n} \mu(n/d) f(d)}$ for all ${n \in {\bf N}}$.

There is a generalisation of this formula to (finite) posets, due to Hall, in which one sums over chains ${n_0 > \dots > n_k}$ in the poset:

Proposition 2 (Poset Möbius inversion) Let ${{\mathcal N}}$ be a finite poset, and let ${f,g: {\mathcal N} \rightarrow A}$ be functions from that poset to an additive group ${A}$. Then the following two claims are equivalent:
• (i) ${f(n) = \sum_{d \leq n} g(d)}$ for all ${n \in {\mathcal N}}$, where ${d}$ is understood to range in ${{\mathcal N}}$.
• (ii) ${g(n) = \sum_{k=0}^\infty (-1)^k \sum_{n = n_0 > n_1 > \dots > n_k} f(n_k)}$ for all ${n \in {\mathcal N}}$, where in the inner sum ${n_0,\dots,n_k}$ are understood to range in ${{\mathcal N}}$ with the indicated ordering.
(Note from the finite nature of ${{\mathcal N}}$ that the inner sum in (ii) is vacuous for all but finitely many ${k}$.)

Comparing Proposition 2 with Proposition 1, it is natural to refer to the function ${\mu(d,n) := \sum_{k=0}^\infty (-1)^k \sum_{n = n_0 > n_1 > \dots > n_k = d} 1}$ as the Möbius function of the poset; the condition (ii) can then be written as

$\displaystyle g(n) = \sum_{d \leq n} \mu(d,n) f(d).$

Proof: If (i) holds, then we have

$\displaystyle g(n) = f(n) - \sum_{d

for any ${n \in {\mathcal N}}$. Iterating this we obtain (ii). Conversely, from (ii) and separating out the ${k=0}$ term, and grouping all the other terms based on the value of ${d:=n_1}$, we obtain (1), and hence (i). $\Box$

In fact it is not completely necessary that the poset ${{\mathcal N}}$ be finite; an inspection of the proof shows that it suffices that every element ${n}$ of the poset has only finitely many predecessors ${\{ d \in {\mathcal N}: d < n \}}$.

It is not difficult to see that Proposition 2 includes Proposition 1 as a special case, after verifying the combinatorial fact that the quantity

$\displaystyle \sum_{k=0}^\infty (-1)^k \sum_{d=n_k | n_{k-1} | \dots | n_1 | n_0 = n} 1$

is equal to ${\mu(n/d)}$ when ${d}$ divides ${n}$, and vanishes otherwise.

I recently discovered that Proposition 2 can also lead to a useful variant of the inclusion-exclusion principle. The classical version of this principle can be phrased in terms of indicator functions: if ${A_1,\dots,A_\ell}$ are subsets of some set ${X}$, then

$\displaystyle \prod_{j=1}^\ell (1-1_{A_j}) = \sum_{k=0}^\ell (-1)^k \sum_{1 \leq j_1 < \dots < j_k \leq \ell} 1_{A_{j_1} \cap \dots \cap A_{j_k}}.$

In particular, if there is a finite measure ${\nu}$ on ${X}$ for which ${A_1,\dots,A_\ell}$ are all measurable, we have

$\displaystyle \nu(X \backslash \bigcup_{j=1}^\ell A_j) = \sum_{k=0}^\ell (-1)^k \sum_{1 \leq j_1 < \dots < j_k \leq \ell} \nu( A_{j_1} \cap \dots \cap A_{j_k} ).$

One drawback of this formula is that there are exponentially many terms on the right-hand side: ${2^\ell}$ of them, in fact. However, in many cases of interest there are “collisions” between the intersections ${A_{j_1} \cap \dots \cap A_{j_k}}$ (for instance, perhaps many of the pairwise intersections ${A_i \cap A_j}$ agree), in which case there is an opportunity to collect terms and hopefully achieve some cancellation. It turns out that it is possible to use Proposition 2 to do this, in which one only needs to sum over chains in the resulting poset of intersections:

Proposition 3 (Hall-type inclusion-exclusion principle) Let ${A_1,\dots,A_\ell}$ be subsets of some set ${X}$, and let ${{\mathcal N}}$ be the finite poset formed by intersections of some of the ${A_i}$ (with the convention that ${X}$ is the empty intersection), ordered by set inclusion. Then for any ${E \in {\mathcal N}}$, one has

$\displaystyle 1_E \prod_{F \subsetneq E} (1 - 1_F) = \sum_{k=0}^\ell (-1)^k \sum_{E = E_0 \supsetneq E_1 \supsetneq \dots \supsetneq E_k} 1_{E_k} \ \ \ \ \ (2)$

where ${F, E_0,\dots,E_k}$ are understood to range in ${{\mathcal N}}$. In particular (setting ${E}$ to be the empty intersection) if the ${A_j}$ are all proper subsets of ${X}$ then we have

$\displaystyle \prod_{j=1}^\ell (1-1_{A_j}) = \sum_{k=0}^\ell (-1)^k \sum_{X = E_0 \supsetneq E_1 \supsetneq \dots \supsetneq E_k} 1_{E_k}. \ \ \ \ \ (3)$

In particular, if there is a finite measure ${\nu}$ on ${X}$ for which ${A_1,\dots,A_\ell}$ are all measurable, we have

$\displaystyle \mu(X \backslash \bigcup_{j=1}^\ell A_j) = \sum_{k=0}^\ell (-1)^k \sum_{X = E_0 \supsetneq E_1 \supsetneq \dots \supsetneq E_k} \mu(E_k).$

Using the Möbius function ${\mu}$ on the poset ${{\mathcal N}}$, one can write these formulae as

$\displaystyle 1_E \prod_{F \subsetneq E} (1 - 1_F) = \sum_{F \subseteq E} \mu(F,E) 1_F,$

$\displaystyle \prod_{j=1}^\ell (1-1_{A_j}) = \sum_F \mu(F,X) 1_F$

and

$\displaystyle \nu(X \backslash \bigcup_{j=1}^\ell A_j) = \sum_F \mu(F,X) \nu(F).$

Proof: It suffices to establish (2) (to derive (3) from (2) observe that all the ${F \subsetneq X}$ are contained in one of the ${A_j}$, so the effect of ${1-1_F}$ may be absorbed into ${1 - 1_{A_j}}$). Applying Proposition 2, this is equivalent to the assertion that

$\displaystyle 1_E = \sum_{F \subseteq E} 1_F \prod_{G \subsetneq F} (1 - 1_G)$

for all ${E \in {\mathcal N}}$. But this amounts to the assertion that for each ${x \in E}$, there is precisely one ${F \subseteq E}$ in ${{\mathcal n}}$ with the property that ${x \in F}$ and ${x \not \in G}$ for any ${G \subsetneq F}$ in ${{\mathcal N}}$, namely one can take ${F}$ to be the intersection of all ${G \subseteq E}$ in ${{\mathcal N}}$ such that ${G}$ contains ${x}$. $\Box$

Example 4 If ${A_1,A_2,A_3 \subsetneq X}$ with ${A_1 \cap A_2 = A_1 \cap A_3 = A_2 \cap A_3 = A_*}$, and ${A_1,A_2,A_3,A_*}$ are all distinct, then we have for any finite measure ${\nu}$ on ${X}$ that makes ${A_1,A_2,A_3}$ measurable that

$\displaystyle \nu(X \backslash (A_1 \cup A_2 \cup A_3)) = \nu(X) - \nu(A_1) - \nu(A_2) \ \ \ \ \ (4)$

$\displaystyle - \nu(A_3) - \nu(A_*) + 3 \nu(A_*)$

due to the four chains ${X \supsetneq A_1}$, ${X \supsetneq A_2}$, ${X \supsetneq A_3}$, ${X \supsetneq A_*}$ of length one, and the three chains ${X \supsetneq A_1 \supsetneq A_*}$, ${X \supsetneq A_2 \supsetneq A_*}$, ${X \supsetneq A_3 \supsetneq A_*}$ of length two. Note that this expansion just has six terms in it, as opposed to the ${2^3=8}$ given by the usual inclusion-exclusion formula, though of course one can reduce the number of terms by combining the ${\nu(A_*)}$ factors. This may not seem particularly impressive, especially if one views the term ${3 \mu(A_*)}$ as really being three terms instead of one, but if we add a fourth set ${A_4 \subsetneq X}$ with ${A_i \cap A_j = A_*}$ for all ${1 \leq i < j \leq 4}$, the formula now becomes

$\displaystyle \nu(X \backslash (A_1 \cup A_2 \cup A_3 \cap A_4)) = \nu(X) - \nu(A_1) - \nu(A_2) \ \ \ \ \ (5)$

$\displaystyle - \nu(A_3) - \nu(A_4) - \nu(A_*) + 4 \nu(A_*)$

and we begin to see more cancellation as we now have just seven terms (or ten if we count ${4 \nu(A_*)}$ as four terms) instead of ${2^4 = 16}$ terms.

Example 5 (Variant of Legendre sieve) If ${q_1,\dots,q_\ell > 1}$ are natural numbers, and ${a_1,a_2,\dots}$ is some sequence of complex numbers with only finitely many terms non-zero, then by applying the above proposition to the sets ${A_j := q_j {\bf N}}$ and with ${\nu}$ equal to counting measure weighted by the ${a_n}$ we obtain a variant of the Legendre sieve

$\displaystyle \sum_{n: (n,q_1 \dots q_\ell) = 1} a_n = \sum_{k=0}^\ell (-1)^k \sum_{1 |' d_1 |' \dots |' d_k} \sum_{n: d_k |n} a_n$

where ${d_1,\dots,d_k}$ range over the set ${{\mathcal N}}$ formed by taking least common multiples of the ${q_j}$ (with the understanding that the empty least common multiple is ${1}$), and ${d |' n}$ denotes the assertion that ${d}$ divides ${n}$ but is strictly less than ${n}$. I am curious to know of this version of the Legendre sieve already appears in the literature (and similarly for the other applications of Proposition 2 given here).

If the poset ${{\mathcal N}}$ has bounded depth then the number of terms in Proposition 3 can end up being just polynomially large in ${\ell}$ rather than exponentially large. Indeed, if all chains ${X \supsetneq E_1 \supsetneq \dots \supsetneq E_k}$ in ${{\mathcal N}}$ have length ${k}$ at most ${k_0}$ then the number of terms here is at most ${1 + \ell + \dots + \ell^{k_0}}$. (The examples (4), (5) are ones in which the depth is equal to two.) I hope to report in a later post on how this version of inclusion-exclusion with polynomially many terms can be useful in an application.

Actually in our application we need an abstraction of the above formula, in which the indicator functions are replaced by more abstract idempotents:

Proposition 6 (Hall-type inclusion-exclusion principle for idempotents) Let ${A_1,\dots,A_\ell}$ be pairwise commuting elements of some ring ${R}$ with identity, which are all idempotent (thus ${A_j A_j = A_j}$ for ${j=1,\dots,\ell}$). Let ${{\mathcal N}}$ be the finite poset formed by products of the ${A_i}$ (with the convention that ${1}$ is the empty product), ordered by declaring ${E \leq F}$ when ${EF = E}$ (note that all the elements of ${{\mathcal N}}$ are idempotent so this is a partial ordering). Then for any ${E \in {\mathcal N}}$, one has

$\displaystyle E \prod_{F < E} (1-F) = \sum_{k=0}^\ell (-1)^k \sum_{E = E_0 > E_1 > \dots > E_k} E_k. \ \ \ \ \ (6)$

where ${F, E_0,\dots,E_k}$ are understood to range in ${{\mathcal N}}$. In particular (setting ${E=1}$) if all the ${A_j}$ are not equal to ${1}$ then we have

$\displaystyle \prod_{j=1}^\ell (1-A_j) = \sum_{k=0}^\ell (-1)^k \sum_{1 = E_0 > E_1 > \dots > E_k} E_k.$

Morally speaking this proposition is equivalent to the previous one after applying a “spectral theorem” to simultaneously diagonalise all of the ${A_j}$, but it is quicker to just adapt the previous proof to establish this proposition directly. Using the Möbius function ${\mu}$ for ${{\mathcal N}}$, we can rewrite these formulae as

$\displaystyle E \prod_{F < E} (1-F) = \sum_{F \leq E} \mu(F,E) 1_F$

and

$\displaystyle \prod_{j=1}^\ell (1-A_j) = \sum_F \mu(F,1) 1_F.$

Proof: Again it suffices to verify (6). Using Proposition 2 as before, it suffices to show that

$\displaystyle E = \sum_{F \leq E} F \prod_{G < F} (1 - G) \ \ \ \ \ (7)$

for all ${E \in {\mathcal N}}$ (all sums and products are understood to range in ${{\mathcal N}}$). We can expand

$\displaystyle E = E \prod_{G < E} (G + (1-G)) = \sum_{{\mathcal A}} (\prod_{G \in {\mathcal A}} G) (\prod_{G < E: G \not \in {\mathcal A}} (1-G)) \ \ \ \ \ (8)$

where ${{\mathcal A}}$ ranges over all subsets of ${\{ G \in {\mathcal N}: G \leq E \}}$ that contain ${E}$. For such an ${{\mathcal A}}$, if we write ${F := \prod_{G \in {\mathcal A}} G}$, then ${F}$ is the greatest lower bound of ${{\mathcal A}}$, and we observe that ${F (\prod_{G < E: G \not \in {\mathcal A}} (1-G))}$ vanishes whenever ${{\mathcal A}}$ fails to contain some ${G \in {\mathcal N}}$ with ${F \leq G \leq E}$. Thus the only ${{\mathcal A}}$ that give non-zero contributions to (8) are the intervals of the form ${\{ G \in {\mathcal N}: F \leq G \leq E\}}$ for some ${F \leq E}$ (which then forms the greatest lower bound for that interval), and the claim (7) follows (after noting that ${F (1-G) = F (1-FG)}$ for any ${F,G \in {\mathcal N}}$). $\Box$

Laura Cladek and I have just uploaded to the arXiv our paper “Additive energy of regular measures in one and higher dimensions, and the fractal uncertainty principle“. This paper concerns a continuous version of the notion of additive energy. Given a finite measure ${\mu}$ on ${{\bf R}^d}$ and a scale ${r>0}$, define the energy ${\mathrm{E}(\mu,r)}$ at scale ${r}$ to be the quantity

$\displaystyle \mathrm{E}(\mu,r) := \mu^4\left( \{ (x_1,x_2,x_3,x_4) \in ({\bf R}^d)^4: |x_1+x_2-x_3-x_4| \leq r \}\right) \ \ \ \ \ (1)$

where ${\mu^4}$ is the product measure on ${({\bf R}^d)^4}$ formed from four copies of the measure ${\mu}$ on ${{\bf R}^d}$. We will be interested in Cantor-type measures ${\mu}$, supported on a compact set ${X \subset B(0,1)}$ and obeying the Ahlfors-David regularity condition

$\displaystyle \mu(B(x,r)) \leq C r^\delta$

for all balls ${B(x,r)}$ and some constants ${C, \delta > 0}$, as well as the matching lower bound

$\displaystyle \mu(B(x,r)) \geq C^{-1} r^\delta$

when ${x \in X}$ whenever ${0 < r < 1}$. One should think of ${X}$ as a ${\delta}$-dimensional fractal set, and ${\mu}$ as some vaguely self-similar measure on this set.

Note that once one fixes ${x_1,x_2,x_3}$, the variable ${x_4}$ in (1) is constrained to a ball of radius ${r}$, hence we obtain the trivial upper bound

$\displaystyle \mathrm{E}(\mu,r) \leq C^4 r^\delta. \ \ \ \ \ (2)$

If the set ${X}$ contains a lot of “additive structure”, one can expect this bound to be basically sharp; for instance, if ${\delta}$ is an integer, ${X}$ is a ${\delta}$-dimensional unit disk, and ${\mu}$ is Lebesgue measure on this disk, one can verify that ${\mathrm{E}(\mu,r) \sim r^\delta}$ (where we allow implied constants to depend on ${d,\delta}$. However we show that if the dimension is non-integer, then one obtains a gain:

Theorem 1 If ${0 < \delta < d}$ is not an integer, and ${X, \mu}$ are as above, then

$\displaystyle \mathrm{E}(\mu,r) \lesssim_{C,\delta,d} r^{\delta+\beta}$

for some ${\beta>0}$ depending only on ${C,\delta,d}$.

Informally, this asserts that Ahlfors-David regular fractal sets of non-integer dimension cannot behave as if they are approximately closed under addition. In fact the gain ${\beta}$ we obtain is quasipolynomial in the regularity constant ${C}$:

$\displaystyle \beta = \exp\left( - O_{\delta,d}( 1 + \log^{O_{\delta,d}(1)}(C) ) \right).$

(We also obtain a localised version in which the regularity condition is only required to hold at scales between ${r}$ and ${1}$.) Such a result was previously obtained (with more explicit values of the ${O_{\delta,d}()}$ implied constants) in the one-dimensional case ${d=1}$ by Dyatlov and Zahl; but in higher dimensions there does not appear to have been any results for this general class of sets ${X}$ and measures ${\mu}$. In the paper of Dyatlov and Zahl it is noted that some dependence on ${C}$ is necessary; in particular, ${\beta}$ cannot be much better than ${1/\log C}$. This reflects the fact that there are fractal sets that do behave reasonably well with respect to addition (basically because they are built out of long arithmetic progressions at many scales); however, such sets are not very Ahlfors-David regular. Among other things, this result readily implies a dimension expansion result

$\displaystyle \mathrm{dim}( f( X, X) ) \geq \delta + \beta$

for any non-degenerate smooth map ${f: {\bf R}^d \times {\bf R}^d \rightarrow {\bf R}^d}$, including the sum map ${f(x,y) := x+y}$ and (in one dimension) the product map ${f(x,y) := x \cdot y}$, where the non-degeneracy condition required is that the gradients ${D_x f(x,y), D_y f(x,y): {\bf R}^d \rightarrow {\bf R}^d}$ are invertible for every ${x,y}$. We refer to the paper for the formal statement.

Our higher-dimensional argument shares many features in common with that of Dyatlov and Zahl, notably a reliance on the modern tools of additive combinatorics (and specifically the Bogulybov-Ruzsa lemma of Sanders). However, in one dimension we were also able to find a completely elementary argument, avoiding any particularly advanced additive combinatorics and instead primarily exploiting the order-theoretic properties of the real line, that gave a superior value of ${\beta}$, namely

$\displaystyle \beta := c \min(\delta,1-\delta) C^{-25}.$

One of the main reasons for obtaining such improved energy bounds is that they imply a fractal uncertainty principle in some regimes. We focus attention on the model case of obtaining such an uncertainty principle for the semiclassical Fourier transform

$\displaystyle {\mathcal F}_h f(\xi) := (2\pi h)^{-d/2} \int_{{\bf R}^d} e^{-i x \cdot \xi/h} f(x)\ dx$

where ${h>0}$ is a small parameter. If ${X, \mu, \delta}$ are as above, and ${X_h}$ denotes the ${h}$-neighbourhood of ${X}$, then from the Hausdorff-Young inequality one obtains the trivial bound

$\displaystyle \| 1_{X_h} {\mathcal F}_h 1_{X_h} \|_{L^2({\bf R}^d) \rightarrow L^2({\bf R}^d)} \lesssim_{C,d} h^{\max\left(\frac{d}{2}-\delta,0\right)}.$

(There are also variants involving pairs of sets ${X_h, Y_h}$, but for simplicity we focus on the uncertainty principle for a single set ${X_h}$.) The fractal uncertainty principle, when it applies, asserts that one can improve this to

$\displaystyle \| 1_{X_h} {\mathcal F}_h 1_{X_h} \|_{L^2({\bf R}^d) \rightarrow L^2({\bf R}^d)} \lesssim_{C,d} h^{\max\left(\frac{d}{2}-\delta,0\right) + \beta}$

for some ${\beta>0}$; informally, this asserts that a function and its Fourier transform cannot simultaneously be concentrated in the set ${X_h}$ when ${\delta \leq \frac{d}{2}}$, and that a function cannot be concentrated on ${X_h}$ and have its Fourier transform be of maximum size on ${X_h}$ when ${\delta \geq \frac{d}{2}}$. A modification of the disk example mentioned previously shows that such a fractal uncertainty principle cannot hold if ${\delta}$ is an integer. However, in one dimension, the fractal uncertainty principle is known to hold for all ${0 < \delta < 1}$. The above-mentioned results of Dyatlov and Zahl were able to establish this for ${\delta}$ close to ${1/2}$, and the remaining cases ${1/2 < \delta < 1}$ and ${0 < \delta < 1/2}$ were later established by Bourgain-Dyatlov and Dyatlov-Jin respectively. Such uncertainty principles have applications to hyperbolic dynamics, in particular in establishing spectral gaps for certain Selberg zeta functions.

It remains a largely open problem to establish a fractal uncertainty principle in higher dimensions. Our results allow one to establish such a principle when the dimension ${\delta}$ is close to ${d/2}$, and ${d}$ is assumed to be odd (to make ${d/2}$ a non-integer). There is also work of Han and Schlag that obtains such a principle when one of the copies of ${X_h}$ is assumed to have a product structure. We hope to obtain further higher-dimensional fractal uncertainty principles in subsequent work.

We now sketch how our main theorem is proved. In both one dimension and higher dimensions, the main point is to get a preliminary improvement

$\displaystyle \mathrm{E}(\mu,r_0) \leq \varepsilon r_0^\delta \ \ \ \ \ (3)$

over the trivial bound (2) for any small ${\varepsilon>0}$, provided ${r_0}$ is sufficiently small depending on ${\varepsilon, \delta, d}$; one can then iterate this bound by a fairly standard “induction on scales” argument (which roughly speaking can be used to show that energies ${\mathrm{E}(\mu,r)}$ behave somewhat multiplicatively in the scale parameter ${r}$) to propagate the bound to a power gain at smaller scales. We found that a particularly clean way to run the induction on scales was via use of the Gowers uniformity norm ${U^2}$, and particularly via a clean Fubini-type inequality

$\displaystyle \| f \|_{U^2(V \times V')} \leq \|f\|_{U^2(V; U^2(V'))}$

(ultimately proven using the Gowers-Cauchy-Schwarz inequality) that allows one to “decouple” coarse and fine scale aspects of the Gowers norms (and hence of additive energies).

It remains to obtain the preliminary improvement. In one dimension this is done by identifying some “left edges” of the set ${X}$ that supports ${\mu}$: intervals ${[x, x+K^{-n}]}$ that intersect ${X}$, but such that a large interval ${[x-K^{-n+1},x]}$ just to the left of this interval is disjoint from ${X}$. Here ${K}$ is a large constant and ${n}$ is a scale parameter. It is not difficult to show (using in particular the Archimedean nature of the real line) that if one has the Ahlfors-David regularity condition for some ${0 < \delta < 1}$ then left edges exist in abundance at every scale; for instance most points of ${X}$ would be expected to lie in quite a few of these left edges (much as most elements of, say, the ternary Cantor set ${\{ \sum_{n=1}^\infty \varepsilon_n 3^{-n} \varepsilon_n \in \{0,1\} \}}$ would be expected to contain a lot of ${0}$s in their base ${3}$ expansion). In particular, most pairs ${(x_1,x_2) \in X \times X}$ would be expected to lie in a pair ${[x,x+K^{-n}] \times [y,y+K^{-n}]}$ of left edges of equal length. The key point is then that if ${(x_1,x_2) \in X \times X}$ lies in such a pair with ${K^{-n} \geq r}$, then there are relatively few pairs ${(x_3,x_4) \in X \times X}$ at distance ${O(K^{-n+1})}$ from ${(x_1,x_2)}$ for which one has the relation ${x_1+x_2 = x_3+x_4 + O(r)}$, because ${x_3,x_4}$ will both tend to be to the right of ${x_1,x_2}$ respectively. This causes a decrement in the energy at scale ${K^{-n+1}}$, and by carefully combining all these energy decrements one can eventually cobble together the energy bound (3).

We were not able to make this argument work in higher dimension (though perhaps the cases ${0 < \delta < 1}$ and ${d-1 < \delta < d}$ might not be completely out of reach from these methods). Instead we return to additive combinatorics methods. If the claim (3) failed, then by applying the Balog-Szemeredi-Gowers theorem we can show that the set ${X}$ has high correlation with an approximate group ${H}$, and hence (by the aforementioned Bogulybov-Ruzsa type theorem of Sanders, which is the main source of the quasipolynomial bounds in our final exponent) ${X}$ will exhibit an approximate “symmetry” along some non-trivial arithmetic progression of some spacing length ${r}$ and some diameter ${R \gg r}$. The ${r}$-neighbourhood ${X_r}$ of ${X}$ will then resemble the union of parallel “cylinders” of dimensions ${r \times R}$. If we focus on a typical ${R}$-ball of ${X_r}$, the set now resembles a Cartesian product of an interval of length ${R}$ with a subset of a ${d-1}$-dimensional hyperplane, which behaves approximately like an Ahlfors-David regular set of dimension ${\delta-1}$ (this already lets us conclude a contradiction if ${\delta<1}$). Note that if the original dimension ${\delta}$ was non-integer then this new dimension ${\delta-1}$ will also be non-integer. It is then possible to contradict the failure of (3) by appealing to a suitable induction hypothesis at one lower dimension.

Ben Green and I have updated our paper “An arithmetic regularity lemma, an associated counting lemma, and applications” to account for a somewhat serious issue with the paper that was pointed out to us recently by Daniel Altman. This paper contains two core theorems:

• An “arithmetic regularity lemma” that, roughly speaking, decomposes an arbitrary bounded sequence ${f(n)}$ on an interval ${\{1,\dots,N\}}$ as an “irrational nilsequence” ${F(g(n) \Gamma)}$ of controlled complexity, plus some “negligible” errors (where one uses the Gowers uniformity norm as the main norm to control the neglibility of the error); and
• An “arithmetic counting lemma” that gives an asymptotic formula for counting various averages ${{\mathbb E}_{{\bf n} \in {\bf Z}^d \cap P} f(\psi_1({\bf n})) \dots f(\psi_t({\bf n}))}$ for various affine-linear forms ${\psi_1,\dots,\psi_t}$ when the functions ${f}$ are given by irrational nilsequences.

The combination of the two theorems is then used to address various questions in additive combinatorics.

There are no direct issues with the arithmetic regularity lemma. However, it turns out that the arithmetic counting lemma is only true if one imposes an additional property (which we call the “flag property”) on the affine-linear forms ${\psi_1,\dots,\psi_t}$. Without this property, there does not appear to be a clean asymptotic formula for these averages if the only hypothesis one places on the underlying nilsequences is irrationality. Thus when trying to understand the asymptotics of averages involving linear forms that do not obey the flag property, the paradigm of understanding these averages via a combination of the regularity lemma and a counting lemma seems to require some significant revision (in particular, one would probably have to replace the existing regularity lemma with some variant, despite the fact that the lemma is still technically true in this setting). Fortunately, for most applications studied to date (including the important subclass of translation-invariant affine forms), the flag property holds; however our claim in the paper to have resolved a conjecture of Gowers and Wolf on the true complexity of systems of affine forms must now be narrowed, as our methods only verify this conjecture under the assumption of the flag property.

In a bit more detail: the asymptotic formula for our counting lemma involved some finite-dimensional vector spaces ${\Psi^{[i]}}$ for various natural numbers ${i}$, defined as the linear span of the vectors ${(\psi^i_1({\bf n}), \dots, \psi^i_t({\bf n}))}$ as ${{\bf n}}$ ranges over the parameter space ${{\bf Z}^d}$. Roughly speaking, these spaces encode some constraints one would expect to see amongst the forms ${\psi^i_1({\bf n}), \dots, \psi^i_t({\bf n})}$. For instance, in the case of length four arithmetic progressions when ${d=2}$, ${{\bf n} = (n,r)}$, and

$\displaystyle \psi_i({\bf n}) = n + (i-1)r$

for ${i=1,2,3,4}$, then ${\Psi^{[1]}}$ is spanned by the vectors ${(1,1,1,1)}$ and ${(1,2,3,4)}$ and can thus be described as the two-dimensional linear space

$\displaystyle \Psi^{[1]} = \{ (a,b,c,d): a-2b+c = b-2c+d = 0\} \ \ \ \ \ (1)$

while ${\Psi^{[2]}}$ is spanned by the vectors ${(1,1,1,1)}$, ${(1,2,3,4)}$, ${(1^2,2^2,3^2,4^2)}$ and can be described as the hyperplane

$\displaystyle \Psi^{[2]} = \{ (a,b,c,d): a-3b+3c-d = 0 \}. \ \ \ \ \ (2)$

As a special case of the counting lemma, we can check that if ${f}$ takes the form ${f(n) = F( \alpha n, \beta n^2 + \gamma n)}$ for some irrational ${\alpha,\beta \in {\bf R}/{\bf Z}}$, some arbitrary ${\gamma \in {\bf R}/{\bf Z}}$, and some smooth ${F: {\bf R}/{\bf Z} \times {\bf R}/{\bf Z} \rightarrow {\bf C}}$, then the limiting value of the average

$\displaystyle {\bf E}_{n, r \in [N]} f(n) f(n+r) f(n+2r) f(n+3r)$

as ${N \rightarrow \infty}$ is equal to

$\displaystyle \int_{a_1,b_1,c_1,d_1 \in {\bf R}/{\bf Z}: a_1-2b_1+c_1=b_1-2c_1+d_1=0} \int_{a_2,b_2,c_2,d_2 \in {\bf R}/{\bf Z}: a_2-3b_2+3c_2-d_2=0}$

$\displaystyle F(a_1,a_2) F(b_1,b_2) F(c_1,c_2) F(d_1,d_2)$

which reflects the constraints

$\displaystyle \alpha n - 2 \alpha(n+r) + \alpha(n+2r) = \alpha(n+r) - 2\alpha(n+2r)+\alpha(n+3r)=0$

and

$\displaystyle (\beta n^2 + \gamma n) - 3 (\beta(n+r)^2+\gamma(n+r))$

$\displaystyle + 3 (\beta(n+2r)^2 +\gamma(n+2r)) - (\beta(n+3r)^2+\gamma(n+3r))=0.$

These constraints follow from the descriptions (1), (2), using the containment ${\Psi^{[1]} \subset \Psi^{[2]}}$ to dispense with the lower order term ${\gamma n}$ (which then plays no further role in the analysis).

The arguments in our paper turn out to be perfectly correct under the assumption of the “flag property” that ${\Psi^{[i]} \subset \Psi^{[i+1]}}$ for all ${i}$. The problem is that the flag property turns out to not always hold. A counterexample, provided by Daniel Altman, involves the four linear forms

$\displaystyle \psi_1(n,r) = r; \psi_2(n,r) = 2n+2r; \psi_3(n,r) = n+3r; \psi_4(n,r) = n.$

Here it turns out that

$\displaystyle \Psi^{[1]} = \{ (a,b,c,d): d-c=3a; b-2a=2d\}$

and

$\displaystyle \Psi^{[2]} = \{ (a,b,c,d): 24a+3b-4c-8d=0 \}$

and ${\Psi^{[1]}}$ is no longer contained in ${\Psi^{[2]}}$. The analogue of the asymptotic formula given previously for ${f(n) = F( \alpha n, \beta n^2 + \gamma n)}$ is then valid when ${\gamma}$ vanishes, but not when ${\gamma}$ is non-zero, because the identity

$\displaystyle 24 (\beta \psi_1(n,r)^2 + \gamma \psi_1(n,r)) + 3 (\beta \psi_2(n,r)^2 + \gamma \psi_2(n,r))$

$\displaystyle - 4 (\beta \psi_3(n,r)^2 + \gamma \psi_3(n,r)) - 8 (\beta \psi_4(n,r)^2 + \gamma \psi_4(n,r)) = 0$

holds in the former case but not the latter. Thus the output of any purported arithmetic regularity lemma in this case is now sensitive to the lower order terms of the nilsequence and cannot be described in a uniform fashion for all “irrational” sequences. There should still be some sort of formula for the asymptotics from the general equidistribution theory of nilsequences, but it could be considerably more complicated than what is presented in this paper.

Fortunately, the flag property does hold in several key cases, most notably the translation invariant case when ${\Psi^{[1]}}$ contains ${(1,\dots,1)}$, as well as “complexity one” cases. Nevertheless non-flag property systems of affine forms do exist, thus limiting the range of applicability of the techniques in this paper. In particular, the conjecture of Gowers and Wolf (Theorem 1.13 in the paper) is now open again in the non-flag property case.

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.