Gowers norms for automatic sequences

Gowers norms for automatic sequences, Discrete Analysis 2023:4, 62 pp.

There are several situations in additive and extremal combinatorics where it is useful to decompose an object $X$ into a “structured” part $S(X)$ and a “quasirandom” part $Q(X)$. If one understands the structured objects sufficiently well, one can then prove facts about $X$ (such as the approximate number of substructures of a given kind) by proving corresponding facts about $S(X)$ and then arguing that $Q(X)$ behaves like a random perturbation that does not have a large effect on what one has proved. For instance, one way to think about the number of triangles in a random (or random-like) graph of density 1/2 is to set $G(x,y)$ to be 1 if $xy$ is an edge and 0 otherwise, and then to decompose $G$ into a structured part – the constant function 1/2 – and a quasirandom part – the function $f(x,y)=G(x,y)-1/2$. The constant function 1/2 can be thought of as a weighted graph where every edge has weight 1/2, and the weighted count of triangles is then $\frac 18\binom n3$. If the values of $f$ are suitably uncorrelated, then because the expectation of $f$ is 0, adding $f$ has only a small effect on this estimate.

A measure of quasirandomness that has proved to be useful for additive problems is that of Gowers uniformity. If $G$ is a finite Abelian group and $f:G\to\mathbb C$, then for each $a\in G$ we write $\partial_af$ for the function $\partial_af(x)=f(x)\overline{f(x-a)}$. Then the $U^k$-norm, or $k$th uniformity norm, of $f$ is defined by the formula
$$\|f\|_{U^k}^{2^k}=\mathbb E_{x,a_1,\dots,a_k}\partial_{a_1}\dots\partial_{a_k}f(x).$$
It is not trivial that this defines a norm, but for $k\geq 2$ it does. (For $k=1$ it is still a seminorm.) A deep theorem of Green and Tao, building on an inverse theorem, proved with Ziegler, which gives a structural description of bounded functions with large $k$th uniformity norm for some $k$, allows one to decompose any bounded function on $\mathbb Z_n$ into a structured part, a part that is small in $L_2$, and a part with small $U^k$ norm. The structure here depends on $k$: it is a certain type of nilsequence of degree $k-1$. Rather than define this, we mention that a key example of such a sequence is a function of the form $f(x)=\exp(2\pi i\pi(x))$, where $\pi$ is a polynomial of degree $k-1$. This type of result is referred to as an arithmetic regularity lemma.

The purpose of this paper is to show that for a class of functions known as automatic sequences, it is considerably easier to obtain a decomposition of the above kind, and much stronger results can be proved.

An automatic sequence is any sequence that can be defined in the following way. One begins with a finite state automaton, which is a machine with a finite collection $S$ of states that takes finite sequences as input, where the sequences take values in some alphabet $\Sigma$. Each state $s\in S$ is a function from $\Sigma$ to $S$, and one of the states, $s_0$, is designated as the initial state. If the input to the automaton is the sequence $(x_1,\dots,x_r)$, then we can define a sequence of states $s_1,\dots,s_r$ inductively by $s_i=s_{i-1}(x_i)$. That is, we start by feeding the value $x_1$ to the initial state $s_0$, which yields a state $s_1$. Then $s_1$ is applied to $x_1$, giving a state $s_2$, and so on. At the end of this process we obtain a final state $s_k$, to which an output function is applied, which is simply a function from $S$ to some set $\Omega$ of possible outputs.

To obtain a sequence from a finite-state automaton, we can write every positive integer in base $k$ for some $k$, and calculate the output when the finite-state automaton is applied to each such representation in turn. (There are some small issues concerning leading zeros, but these can be dealt with in a satisfactory way. See the paper for details.)

A simple example of an automatic sequence is the Morse sequence, the $n$th term of which is defined to be the parity of the number of 1s in the binary expansion of $n$ (if we start with $n=0$). This can be defined using a machine with two states. Each state sends 0 to itself and 1 to the other state, and the output function is 0 for the initial state and 1 for the other state.

In general, the class of automatic sequences is restricted enough to have strong properties that are not shared by arbitrary sequences, but wide enough to be interesting and to exhibit many different behaviours.

The main result of the paper asserts that every automatic sequence has a very efficient decomposition into a structured part and a quasirandom part. As with the Green-Tao arithmetic regularity lemma, quasirandomness is measured by uniformity norms, with the difference that instead of having one result for each uniformity norm, the conclusion is that the quasirandom part is small in all the uniformity norms, where “small” has a very strong sense: the uniformity norm of the first $n$ terms of the sequence has a power decay in $n$.

As for the structured part, if the automaton is strongly connected, which means that every state can get to every other state, given a suitable sequence, then it is rationally almost periodic, meaning that for every $\epsilon>0$ there is a periodic sequence that agrees with it except on a set of density at most $\epsilon$. In the general case, the structured part is built in a simple way out of three basic types of sequence: periodic sequences, sequences $(s_n)$ that depend only on the first few digits of the base-$k$ expansion of $n$ for some $k$, and sequences that depend only on the last few digits of the base-$k$ expansion for some $k$.

While nilsequences and polynomial phase functions provide us with many explicit examples of functions with small $U^k$ norm for some given $k$, it is not so easy to find examples that have small $U^k$ norm for all $k$, so one nice consequence of this work is to provide a wide class of such examples.

Another consequence is to show that for automatic sequences a result of Green and Tao about popular progression differences can be greatly strengthened. Green and Tao showed that for every set $A\subset\mathbb\{1,2,\dots,n\}$ of positive density $\alpha$ there are differences $d_3$ and $d_4$ such that the the number of arithmetic progressions in $A$ with common difference $d_i$ is at least $\alpha^i-\epsilon$, but that this result fails for progressions of length 5 and above. If $A$ is given by an automatic sequence, the result holds with much better bounds (Green and Tao’s proof yields tower-type bounds, which were shown to be necessary by Fox and Pham, compared with power-type bounds here) and it holds for progressions of all lengths.