A (complex, semi-definite) inner product space is a complex vector space {V} equipped with a sesquilinear form {\langle, \rangle: V \times V \rightarrow {\bf C}} which is conjugate symmetric, in the sense that {\langle w, v \rangle = \overline{\langle v, w \rangle}} for all {v,w \in V}, and non-negative in the sense that {\langle v, v \rangle \geq 0} for all {v \in V}. By inspecting the non-negativity of {\langle v+\lambda w, v+\lambda w\rangle} for complex numbers {\lambda \in {\bf C}}, one obtains the Cauchy-Schwarz inequality

\displaystyle |\langle v, w \rangle| \leq |\langle v, v \rangle|^{1/2} |\langle w, w \rangle|^{1/2};

if one then defines {\|v\| := |\langle v, v \rangle|^{1/2}}, one then quickly concludes the triangle inequality

\displaystyle \|v + w \| \leq \|v\| + \|w\|

which then soon implies that {\| \|} is a semi-norm on {V}. If we make the additional assumption that the inner product {\langle,\rangle} is positive definite, i.e. that {\langle v, v \rangle > 0} whenever {v} is non-zero, then this semi-norm becomes a norm. If {V} is complete with respect to the metric {d(v,w) := \|v-w\|} induced by this norm, then {V} is called a Hilbert space.

The above material is extremely standard, and can be found in any graduate real analysis course; I myself covered it here. But what is perhaps less well known (except inside the fields of additive combinatorics and ergodic theory) is that the above theory of classical Hilbert spaces is just the first case of a hierarchy of higher order Hilbert spaces, in which the binary inner product {f, g \mapsto \langle f, g \rangle} is replaced with a {2^d}-ary inner product {(f_\omega)_{\omega \in \{0,1\}^d} \mapsto \langle (f_\omega)_{\omega \in \{0,1\}^d}} that obeys an appropriate generalisation of the conjugate symmetry, sesquilinearity, and positive semi-definiteness axioms. Such inner products then obey a higher order Cauchy-Schwarz inequality, known as the Cauchy-Schwarz-Gowers inequality, and then also obey a triangle inequality and become semi-norms (or norms, if the inner product was non-degenerate). Examples of such norms and spaces include the Gowers uniformity norms {\| \|_{U^d(G)}}, the Gowers box norms {\| \|_{\Box^d(X_1 \times \ldots \times X_d)}}, and the Gowers-Host-Kra seminorms {\| \|_{U^d(X)}}; a more elementary example are the family of Lebesgue spaces {L^{2^d}(X)} when the exponent is a power of two. They play a central role in modern additive combinatorics and to certain aspects of ergodic theory, particularly those relating to Szemerédi’s theorem (or its ergodic counterpart, the Furstenberg multiple recurrence theorem); they also arise in the regularity theory of hypergraphs (which is not unrelated to the other two topics).

A simple example to keep in mind here is the order two Hilbert space {L^4(X)} on a measure space {X = (X,{\mathcal B},\mu)}, where the inner product takes the form

\displaystyle \langle f_{00}, f_{01}, f_{10}, f_{11} \rangle_{L^4(X)} := \int_X f_{00}(x) \overline{f_{01}(x)} \overline{f_{10}(x)} f_{11}(x)\ d\mu(x).

In this brief note I would like to set out the abstract theory of such higher order Hilbert spaces. This is not new material, being already implicit in the breakthrough papers of Gowers and Host-Kra, but I just wanted to emphasise the fact that the material is abstract, and is not particularly tied to any explicit choice of norm so long as a certain axiom are satisfied. (Also, I wanted to write things down so that I would not have to reconstruct this formalism again in the future.) Unfortunately, the notation is quite heavy and the abstract axiom is a little strange; it may be that there is a better way to formulate things. In this particular case it does seem that a concrete approach is significantly clearer, but abstraction is at least possible.

Note: the discussion below is likely to be comprehensible only to readers who already have some exposure to the Gowers norms.

— 1. Definition of a higher order Hilbert space —

Let {V, W} be complex vector spaces. Then one can form the (algebraic) tensor product {V \otimes W}, which can be defined as the vector space spanned by formal tensor products {v \otimes w}, subject to the constraint that the tensor product is bilinear (i.e. that {v \otimes (w_1+w_2) = (v \otimes w_1) + (v \otimes w_2)}, {v \otimes cw = c (v \otimes w)}, and similarly with the roles of {v} and {w} reversed). More generally, one can define the tensor product {\bigotimes_{\omega \in \Omega} V_\omega} of any finite family of complex vector spaces {V_\omega}.

Given a complex vector space {V}, one can define its complex conjugate {\overline{V}} to be the set of formal conjugates {\{ \overline{v}: v \in V \}} of vectors in {V}, with the vector space operations given by

\displaystyle 0 := \overline{0}

\displaystyle \overline{v} + \overline{w} := \overline{v+w}

\displaystyle c \overline{v} := \overline{\overline{c} v}.

The map {v \mapsto \overline{v}} is then an antilinear isomorphism from {V} to {\overline{V}}. We adopt the convention that {\overline{\overline{v}} = v}, thus {v \mapsto \overline{v}} is also an antilinear isomorphism from {\overline{V}} to {V}. (One can work with real higher order Hilbert spaces instead of complex ones, in which case the conjugation symbols can be completely ignored.)

For inductive reasons, it is convenient to use finite sets {A} of labels, rather than natural numbers {d}, to index the order of the systems we will be studying. In any case, the cardinality {|A|} of the set of labels will be the most important feature of this set.

Given a complex vector space {V} and a finite set {A} of labels, we form the tensor cube {V^{[A]}} to be

\displaystyle V^{[A]} := \bigotimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} V,

where {{\mathcal C}} is the conjugation map {V \mapsto \overline{V}}, and {|\omega| := \sum_{i \in A} \omega_i} when {\omega = (\omega_i)_{i \in A}}; thus for instance {V^{[\{\}]} = V}, {V^{[\{1\}]} \equiv V \otimes \overline{V}} is spanned by tensor products {v_0 \otimes \overline{v_1}} with {v_0, v_1 \in V}, {V^{[\{1,2\}]} \equiv V \otimes \overline{V} \otimes \overline{V} \otimes V} is spanned by tensor products {v_{00} \otimes \overline{v_{01}} \otimes \overline{v_{10}} \otimes v_{11}} with {v_{00}, v_{01}, v_{10}, v_{11} \in V}, and so forth. (It would be better to order the four factors {v_{00}, v_{01}, v_{10}, v_{11}} in a square pattern, rather than linearly as is done here, but we have used the inferior linear ordering here for typographical reasons.)

Given any finite set {A} of labels and any {i \in A}, one can form an identification

\displaystyle V^{[A]} \equiv V^{[A \backslash \{i\}]} \otimes \overline{V^{[A \backslash \{i\}]}}

by identifying a tensor product {\bigotimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} v_\omega} in {V^{[A]}} with

\displaystyle (\bigotimes_{\omega' \in \{0,1\}^{A \backslash i}} {\mathcal C}^{|\omega'|} v_{(\omega',0)}) \otimes \overline{(\bigotimes_{\omega' \in \{0,1\}^{A \backslash i}} {\mathcal C}^{|\omega'|} v_{(\omega',1)})}

where, for {\omega' \in \{0,1\}^{A \backslash i}} and {\omega_i \in \{0,1\}}, {(\omega',\omega_i)} denotes the element of {\{0,1\}^A} that agrees with {\omega'} on {A \backslash i} and equals {\omega_i} on {i}. We refer to this identification as {\otimes_i}, thus

\displaystyle \otimes_i: V^{[A \backslash \{i\}]} \otimes \overline{V^{[A \backslash \{i\}]}} \rightarrow V^{[A]}

is an isomorphism, and one can define the {i^{th}} tensor product {v \otimes_i \overline{w} \in V^{[A]}} of two elements {v, w \in V^{[A \backslash \{i\}]}}. Thus for instance, if {v = v_0 \otimes \overline{v_1}} and {w = w_0 \otimes \overline{w_1}} are elements of {V^{[\{1\}]}}, then

\displaystyle v \otimes_2 \overline{w} = v_0 \otimes \overline{v_1} \otimes \overline{w_0} \otimes w_1

using the linear ordering conventions used earlier. If we instead view {v, w} as elements of {V^{[\{2\}]}} rather than {V^{[\{1\}]}}, then

\displaystyle v \otimes_1 \overline{w} = v_0 \otimes \overline{w_0} \otimes \overline{v_1} \otimes w_1.

A (semi-)definite inner product {\langle, \rangle} on a complex vector space {V} can be viewed as a linear functional {\langle \rangle: V \otimes \overline{V} \rightarrow {\bf C}} on {V^{[\{1\}]} = V \otimes \overline{V}} obeying a conjugation symmetry and positive (semi-)definiteness property, defined on tensor products {v \otimes \overline{w}} as {\langle v \otimes \overline{w} \rangle := \langle v, w \rangle}. With this notation, the conjugation symmetry axiom becomes

\displaystyle \langle w \otimes \overline{v} \rangle := \overline{\langle v \otimes \overline{w} \rangle}

and the positive semi-definiteness property becomes

\displaystyle \langle v \otimes \overline{v} \rangle \geq 0

with equality iff {v=0} in the definite case.

Now we can define a higher order inner product space.

Definition 1 Let {A} be a finite set of labels. A (semi-definite) inner product space of order {A} is a complex vector space {V}, together with a linear functional {\langle \rangle_A: V^{[A]} \rightarrow {\bf C}} that obeys the following axiom:

  • (Splitting axiom) For every {i \in A}, {\langle \rangle_A} is a semi-definite classical inner product {\langle \rangle_{A \backslash \{i\}}} on {V^{[A \backslash \{i\}]} \otimes \overline{V^{[A \backslash \{i\}]}}}, which we identify with {V^{[A]}} using {\otimes_i} as mentioned above.

We say that the inner product space is positive definite if one has {\langle \bigotimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} v \rangle_A > 0} whenever {v \in V} is non-zero. (Note from the splitting axiom that one already has the non-strict inequality. But the positive definiteness property is weaker than the assertion that each of the classical inner products)

For instance, if {A} is the empty set, then an inner product space of order {A} is just a complex vector space {V} equipped with a linear functional {v \mapsto \langle v \rangle_A} from {V} to {{\bf C}} (which one could interpret as an expectation or a trace, if one wished). If {A} is a singleton set, then an inner product space of order {A} is the same thing as a classical inner product space.

If {A = \{1,2\}}, then an inner product space of order {A} is a complex vector space {V} equipped with a linear functional {\langle \rangle_A: V \otimes \overline{V} \otimes \overline{V} \otimes V}, which in particular gives rise to a quartisesquilinear (!) form

\displaystyle (v_{00}, v_{01}, v_{10}, v_{11}) \mapsto \langle v_{00} \otimes \overline{v_{01}} \otimes \overline{v_{10}} \otimes v_{11} \rangle_A

which is a classical inner product in two different ways, thus for instance we have

\displaystyle \langle v_{00} \otimes \overline{v_{01}} \otimes \overline{v_{10}} \otimes v_{11} \rangle_A = \langle v_{00} \otimes \overline{v_{01}}, v_{10} \otimes \overline{v_{11}} \rangle_{\{2\}}

for {v_{00}, v_{01}, v_{10}, v_{11} \in V} and some classical inner product {\langle, \rangle_{\{2\}}} on {V^{[\{2\}]}}, and similarly

\displaystyle \langle v_{00} \otimes \overline{v_{01}} \otimes \overline{v_{10}} \otimes v_{11} \rangle_A = \langle v_{00} \otimes \overline{v_{10}}, v_{01} \otimes \overline{v_{11}} \rangle_{\{1\}}

for some classical inner product {\langle,\rangle_{\{1\}}} on {V^{[\{1\}]}}.

— 2. Examples —

Let us now give the three major (and inter-related) examples of inner product spaces of higher order: the Gowers uniformity spaces, that arise in additive combinatorics; the Gowers box spaces, which arise in hypergraph regularity theory, and the Gowers-Host-Kra spaces, which arise in ergodic theory. We also remark on the much simpler example of the Lebesgue spaces of dyadic exponent.

The first example is the family of Gowers uniformity spaces {U^A(G)}, which we will define for simplicity on a finite additive group {G} (one can also define this norm more generally on finite subsets of abelian groups, and probably also nilpotent groups, but we will not do so here). Here {A} is a finite set of labels; in applications one usually sets {A := \{1,\ldots,d\}}, in which case one abbreviates {U^{\{1,\ldots,d\}}(G)} as {U^d(G)}. The space {U^A(G)} is the space of all functions {f: G \rightarrow {\bf C}}, and so {U^A(G)^{[A]}} can be canonically identified with the space of functions {F: G^{\{0,1\}^A} \rightarrow {\bf C}}. To make {U^A(G)} into an inner product space of order {A}, we define

\displaystyle \langle F \rangle_A := \mathop{\bf E}_{x \in G^{[A]}} F(x)

where {G^{[A]}} is the subgroup of {G^{\{0,1\}^A}} consisting of the parallelopipeds

\displaystyle G^{[A]} := \{ ( x + \sum_{i \in A} \omega_i h_i )_{\omega \in \{0,1\}^A}: x \in G, h_i \in G \hbox{ for all } i \in A \}.

This is clearly a linear functional. To verify the splitting axiom, one observes the identity

\displaystyle \langle F_0 \otimes_i \overline{F_1} \rangle_A = \mathop{\bf E}_{h_j \in G \hbox{ for } j \in A \backslash \{i\}} \mathop{\bf E}_{x,h_i \in G}

\displaystyle F_0( ( x + \sum_{j \in A \backslash \{i\}} \omega_j h_j )_{\omega \in \{0,1\}^{A\backslash \{i\}}} )

\displaystyle \overline{F_1}( ( x + h_i + \sum_{j \in A \backslash \{i\}} \omega_j h_j )_{\omega \in \{0,1\}^{A\backslash \{i\}}} )

for any {i \in A} and {F_0, F_1 \in U^A(G)^{[A \backslash \{i\}]}}. The right-hand side is then a semi-definite classical inner product on {U^A(G)^{[A \backslash \{i\}]}}; the semi-definiteness becomes more apparent if one makes the substitution {(x,y) := (x,x+h_i)}.

Specialising to tensor products, we obtain the Gowers inner product

\displaystyle \langle \otimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} f_\omega \rangle_A = \mathop{\bf E}_{x \in G, h_i \in G \forall i \in A} \prod_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} f_\omega(x + \sum_{i=1}^A \omega_i h_i ).

Thus, for instance, when {A = \{1,2\}},

\displaystyle \langle f_{00} \otimes \overline{f_{01}} \otimes \overline{f_{10}} \otimes f_{11} \rangle_A =

\displaystyle \mathop{\bf E}_{x, h_1, h_2 \in G} f_{00}(x) \overline{f_{10}}(x+h_2) \overline{f_{10}}(x+h_1) f_{11}(x+h_1+h_2).

The second example is the family of the (incomplete) Gowers box spaces {\Box^A \cap L^\infty( X )}, defined on a Cartesian product {X := \prod_{i \in A} X_i} of a family {X_i = (X_i, {\mathcal B}_i, \mu_i)} of measure spaces indexed by a finite set {A}. To avoid some minor technicalities regarding absolute integrability, we assume that all the measure spaces have finite measure (the theory also works in the {\sigma}-finite case, but we will not discuss this here). This space is the space of all bounded measurable functions {f \in L^\infty( X )} (here, for technical reasons, it is best not to quotient out by almost everywhere equivalence until later in the theory). The tensor power {L^\infty( X )^{[A]}} can thus be identified with a subspace of {L^\infty( X^{\{0,1\}^A} )} (roughly speaking, this is the subspace of “elementary functions”). We can then define an inner product of order {A} by the formula

\displaystyle \langle F \rangle = \int_X \int_X F( ((x_{\omega_i,i})_{i \in A})_{\omega \in \{0,1\}^A} )\ d\mu(x_0) d\mu(x_1)

for all {F \in L^\infty( X )^{[A]} \subset L^\infty( X^{\{0,1\}^A} )}, where {x_0 = (x_{0,i})_{i \in A}} and {x_1 = (x_{0,i})_{i \in A}} are integrated using product measure {\mu := \prod_{i \in A} \mu_i}.

The verification of the splitting property is analogous to that for the Gowers uniformity spaces. Indeed, there is the identity

\displaystyle \langle F_0 \otimes_i \overline{F_1} \rangle_A = \int_{X^{(i)}} \int_{X^{(i)}} \int_{X_i} \int_{X_i}

\displaystyle F_0( ( ( ( x_{\omega'_j,j} )_{j \in A \backslash \{i\}}, x_{0,i} ) )_{\omega' \in A \backslash \{i\}}

\displaystyle \overline{F_1}( ( ( ( x_{\omega'_j,j} )_{j \in A \backslash \{i\}}, x_{1,i} ) )_{\omega' \in A \backslash \{i\}}

\displaystyle d\mu_i(x_{0,i}) d\mu_i(x_{1,i}) d \mu^{(i)}(x^{(i)}_0) d \mu^{(i)}(x^{(i)}_1)

for all {i \in A} and {F_0, F_1 \in L^\infty( X )^{[A \backslash \{i\}]} \subset L^\infty( X^{\{0,1\}^{A \backslash \{i\}}} )}, where {X^{(i)} := \prod_{j \in A \backslash \{i\}} X_j}, {\mu^{(i)} := \prod_{j \in A \backslash \{i\}} \mu_j}, and {x^{(i)}_a = (x_{a,j})_{j \in A \backslash \{i\}}} for {a=0,1}. From this formula one can verify the inner product property without much trouble (the main difficulty here is simply in unpacking all the notation).

The third example is that of the (incomplete) Gowers-Host-Kra spaces {U^A \cap L^\infty(X)}. Here, {X = (X, {\mathcal B}, \mu)} is a probability space with an invertible measure-preserving shift {T}, which of course induces a measure-preserving action {n \mapsto T^n} of the integers {{\bf Z}} on {X}. (One can replace the integers in the discussion that follows by more general nilpotent amenable groups, but we will stick to integer actions for simplicity.) It is often convenient to also assume that the measure {\mu} is ergodic, though this is not strictly required to define the semi-norms. The space here is {L^\infty(X)}; the power {L^\infty(X)^{[A]}} is then a subspace of {L^\infty(X^{\{0,1\}^A})}. One can define the Host-Kra measure {\mu^{[A]}} on {X^{[A]}} for any finite {A} by the following recursive procedure. Firstly, when {A} is empty, then {\mu^{[A]}} is just {\mu}. If instead {A} is non-empty, then pick an element {i \in A} and view {X^{[A]}} as the Cartesian product of {X^{[A \backslash \{i\}]}} with itself. The shift {T} acts on {X}, and thus acts diagonally on {X^{[A \backslash \{i\}]}} by acting on each component separately. It is not hard to show inductively from the construction that we are about to give that {\mu^{[A \backslash \{i\}]}} is invariant with respect to this diagonal shift, which we will call {T^{[A \backslash \{i\}]}}. The product {\sigma}-algebra {{\mathcal B}^{[A \backslash \{i\}]}} has an invariant factor {({\mathcal B}^{[A \backslash \{i\}]})^{T^{[A \backslash \{i\}]}}} with respect to this shift. We then define {\mu^{[A]}} to be the relative product of {\mu^{[A \backslash \{i\}]}} with itself relative to this invariant factor. One can show that this definition is independent of the choice of {i}, and that the form

\displaystyle \langle F \rangle_A := \int_{X^{[A]}} F\ d\mu^{[A]}

is an inner product of order {A}; see the paper of Host and Kra for details.

A final (and significantly simpler) example of a inner product space of order {A} is the Lebesgue space {L^{2^{|A|}}(X)} on some measure space {X = (X,{\mathcal B},\mu)}, with inner product

\displaystyle \langle F \rangle_A := \int_X F( (x,\ldots,x) )\ d\mu(x)

where {x \mapsto (x,\ldots,x)} is the diagonal embedding from {X} to {X^{[A]} \equiv X^{2^{|A|}}}. For tensor products, this inner product takes the form

\displaystyle \langle \bigotimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} f_\omega \rangle_A = \int_X \prod_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} f_\omega\ d\mu,

thus for instance when {A = \{1,2\}},

\displaystyle \langle f_{00} \otimes \overline{f_{01}} \otimes \overline{f_{10}} \otimes f_{11} \rangle_A = \int_X f_{00} \overline{f_{01}} \overline{f_{10}} f_{11}\ d\mu.

We leave it as an exercise to the reader to show {L^{2^{|A|}}(X)} is indeed an inner product space of order {A}. This example is (the completion of) the Gowers-Host-Kra space in the case when the shift {T} is trivial.

We also remark that given an inner product space {(V, \langle \rangle_A)} of some order {A}, given some subset {B} of {A}, and given a fixed vector {v_*} in {V}, one can define a weighted inner product space {(V, \langle \rangle_{B,v_*})} of order {B} by the formula

\displaystyle \langle F \rangle_{B,v_*} := \langle F \otimes \bigotimes_{\omega \in \{0,1\}^A \backslash \{0,1\}^B} {\mathcal C}^{|\omega|} v_* \rangle_A

for all {F \in V^{[B]}}, where {\{0,1\}^B} is embedded in {\{0,1\}^A} by extension by zero and the tensor product on the right-hand side is defined in the obvious manner. One can check that this is indeed a weighted inner product space. This is a generalisation of the classical fact that every vector {v_*} in an inner product space {V} naturally defines a linear functional {w \mapsto \langle w, v_* \rangle} on {V}. In the case of the Gowers uniformity spaces with {v_* := 1}, this construction takes {U^A(G)} to {U^B(G)}; similarly for the Gowers box spaces.

— 3. Basic theory —

Let {V} be an inner product space of order {A} for some finite non-empty {A}. The splitting axiom tells us that

\displaystyle \langle F_0 \otimes_i \overline{F_1} \rangle_A = \langle F_0, F_1 \rangle_{A \backslash \{i\}}

for all {i \in A}, {F_0, F_1 \in V^{[A \backslash \{i\}]}}, and some inner product {\langle, \rangle} on {X^{[A \backslash \{i\}]}}. In particular one has

\displaystyle \langle F \otimes_i \overline{F} \rangle_A \geq 0

for all {F \in V^{[A \backslash \{i\}]}}, as well as the classical Cauchy-Schwarz inequality

\displaystyle |\langle F_0 \otimes_i \overline{F_1} \rangle_A| \leq |\langle F_0 \otimes_i \overline{F_0} \rangle_A|^{1/2} |\langle F_1 \otimes_i \overline{F_1} \rangle_A|^{1/2}.

If we specialise this inequality to the tensor products

\displaystyle F_a := \bigotimes_{\omega' \in \{0,1\}^{A \backslash \{i\}}} {\mathcal C}^{|\omega'|} v_{a,\omega'}

for various {v_{a,\omega'} \in V}, one concludes that

\displaystyle |\langle \bigotimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} v_\omega \rangle_A| \leq \prod_{a \in \{0,1\}} |\langle \bigotimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} v_{a,\omega'} \rangle_A|^{1/2}

where we write {\omega = (\omega_i, \omega')} for some {\omega_i \in\{0,1\}} and {\omega' \in \{0,1\}^{A \backslash \{i\}}}. If we iterate this inequality once for each {i \in A}, we obtain the Cauchy-Schwarz-Gowers inequality

\displaystyle |\langle \bigotimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} v_\omega \rangle_A| \leq \prod_{\omega \in \{0,1\}^A} \|v_\omega\|_A

where

\displaystyle \| v \|_A := |\langle \bigotimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} v \rangle_A|^{1/2^{|A|}}.

The quantity {\|v\|_A} is clearly non-negative and homogeneous. We also have the Gowers triangle inequality

\displaystyle \|v_0+v_1\|_A \leq \|v_0\|_A + \|v_1\|_A,

which makes {\|\|_A} a semi-norm (and in fact a norm, if the inner product space was positive definite). To see this inequality, we first raise both sides to the power {2^{|A|}}:

\displaystyle \|v_0+v_1\|_A^{2^{|A|}} \leq (\|v_0\|_A + \|v_1\|_A)^{2^{|A|}}.

The left-hand side can be expanded as

\displaystyle |\langle \bigotimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} (v_0+v_1) \rangle_A|

which after expanding out using linearity and the triangle inequality, can be bounded by

\displaystyle \sum_{\alpha \in \{0,1\}^{\{0,1\}^A}} |\langle \bigotimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} v_{\alpha_\omega} \rangle_A|

which by the Cauchy-Schwarz-Gowers inequality can be bounded in turn by

\displaystyle \sum_{\alpha \in \{0,1\}^{\{0,1\}^A}} \prod_{\omega \in \{0,1\}^A} \| v_{\alpha_\omega} \|_A

which can then be factored into {(\|v_0\|_A + \|v_1\|_A)^{2^{|A|}}} as required.

Note that when {A} is a singleton set, the above argument collapses to the usual derivation of the triangle inequality from the classical Cauchy-Schwarz inequality. It is also instructive to see how this collapses to one of the standard proofs of the triangle inequality for {L^{2^k}(X)} using a large number of applications of the Cauchy-Schwarz inequality.

In analogy with classical Hilbert spaces, one can define a Hilbert space of order {A} to be an inner product space {V} of order {A} which is both positive definite and complete, so that the norm {\| \|_A} gives {V} the structure of a Banach space. A typical example is {U^2(G)} for a finite abelian {G}, which is the space of all functions {f: G \rightarrow {\bf C}} with the norm

\displaystyle \|f\|_{U^2(G)} = \|\hat f\|_{\ell^4(\hat G)}

where {\hat G} is the Pontraygin dual of {G} (i.e. the space of homomorphisms {\xi: x \mapsto \xi \cdot x} from {G} to {{\bf R}/{\bf Z}}) and {\hat f(\xi) := \mathop{\bf E}_{x \in G} f(x) e(-\xi \cdot x)} is the Fourier transform. Thus we see that {\ell^4(\hat G)} is a Hilbert space of order {2}. More generally, {L^{2^k}(X)} for any measure space {X} and any {k \geq 0} can be viewed as a Hilbert space of order {k}.

The Gowers norms {U^d(G)} and Gowers-Host-Kra norms {U^d(X)} coincide in the model case when {X=G={\bf Z}/N{\bf Z}} is a cyclic group with uniform measure and the standard shift {T: x \mapsto x+1}. Also, the Gowers norms {U^d(G)} can be viewed as a special case of the box norms via the identity

\displaystyle \|f\|_{U^d(G)} := \| f \circ s \|_{\Box^d(G^d)}

where {s: G^d \rightarrow G} is the summation operation {s(x_1,\ldots,x_d) := x_1+\ldots+x_d}.

Just as classical inner product spaces can be made positive definite by quotienting out the norm zero elements, and then made into a classical Hilbert space by metric completion, inner product spaces of any order can also be made positive definite and completed. One can apply this procedure for instance to obtain the completed Gowers box spaces {\Box^A(X)} and the completed Gowers-Host-Kra spaces {U^A(X)} (which become {L^{2^{|A|}}(X)} when the shift {T} is trivial). These spaces are related, but not equal, to their Lebesgue counterparts {L^p(X)}; for instance for the Gowers-Host-Kra spaces in the ergodic setting, a repeated application of Young’s inequality reveals the inequalities

\displaystyle \|f\|_{U^{A}(X)} \leq \|f\|_{L^{2^{|A|}/(|A|+1)}(X)} \leq \|f\|_{L^\infty(X)},

and so {U^A(X)} contains a (quotient) of {L^{2^{|A|}/(|A|+1)}(X)}.

The null space of the Gowers-Host-Kra norm {U^A(X)} in {L^\infty(X)} in the ergodic case is quite interesting; it turns out to be the space {L^\infty({\mathcal Z}_{< |A|})^\perp} of bounded measurable functions {f} whose conditional expectation {\mathop{\bf E}(f|{\mathcal Z}_{<|A|}} on the characteristic factor {{\mathcal Z}_{< |A|}} of order {|A|-1} of {X} vanishes; in particular, {L^\infty({\mathcal Z}_{<|A|})} becomes a dense subspace of {U^A(X)}, embedded injectively. It is a highly non-trivial and useful result, first obtained by Host and Kra), that {{\mathcal Z}_{<|A|}} is the inverse limit of all nilsystem factors of step at most {|A|-1}; this is the ergodic counterpart of the inverse conjecture for the Gowers norms.

— 4. The category of higher order inner product spaces —

The higher order Hilbert spaces {L^1(X), L^2(X), L^4(X), L^8(X), \ldots} are related to each other via Hölder’s inequality; the pointwise product of two {L^4} functions is in {L^2}, the product of two {L^8} functions is in {L^4}, and so forth. Furthermore, the inner products on all of these spaces are can be connected to each other via the pointwise product.

We can generalise this concept, giving the class of inner product spaces (of arbitrary orders) the structure of a category.

Definition 2 Let {B \subseteq A} be finite sets, and let {V_B = (V_B, \langle \rangle_B)}, {V_A = (V_A, \langle \rangle_A)} be inner product spaces of order {B, A} respectively. An isometry {\phi} from {V_A} to {V_B} is a linear map

\displaystyle \phi: \bigotimes_{\omega \in \{0,1\}^{A \backslash B}} {\mathcal C}^{|\omega|} V_A \rightarrow V_B

which preserves the inner product in the sense that

\displaystyle \langle \bigotimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} v_\omega \rangle_A

\displaystyle = \langle \bigotimes_{\omega' \in \{0,1\}^B} {\mathcal C}^{|\omega'|} \phi( \bigotimes_{\omega'' \in \{0,1\}^{A \backslash B}} {\mathcal C}^{|\omega''|} v_{(\omega',\omega'')} ) \rangle_B,

where {\omega', \omega'' \rightarrow (\omega',\omega'')} is the obvious concatenation map from {\{0,1\}^{B} \times \{0,1\}^{A \backslash B}} to {\{0,1\}^A}.

Given an isometry {\phi} from {V_A} to {V_B}, and an isometry {\psi} from {V_B} to {V_C} for some {C \subset B \subset A}, one can form the composition

\displaystyle \psi \circ \phi: \bigotimes_{\omega \in \{0,1\}^{A \backslash C}} {\mathcal C}^{|\omega|} V_A \rightarrow V_C

by the formula

\displaystyle \psi \circ \phi( \bigotimes_{\omega \in \{0,1\}^{A \backslash C}} {\mathcal C}^{|\omega|} v_\omega )

\displaystyle := \psi( \bigotimes_{\omega' \in \{0,1\}^{B \backslash C}} {\mathcal C}^{|\omega'|} \phi( \bigotimes_{\omega'' \in \{0,1\}^{A \backslash B}} {\mathcal C}^{|\omega''|} v_{(\omega',\omega'')}))

and extending by linearity; one can verify that this continues to be an isometry, and that the class of inner product spaces of arbitrary order together with isomorphisms form a category.

When {A=B} is a singleton set, the above concept collapses to the classical notion of an isometry for inner product spaces. Of course, one could specialise to the subcategory of higher order Hilbert spaces if desired. The inner product on a higher order inner product space can now be interpreted as an isometry from that space to the space {{\bf C}} (viewed as an inner product space of order {\emptyset}), and is the unique such isometry; in the language of category theory, this space {{\bf C}} becomes the terminal object of the category.

A model example of an isometry is the sesquilinear product map {f, g \mapsto f \overline{g}}, which is an isometry from {L^{2^d}(X)} to {L^{2^{d-1}}(X)} for any {d \geq 1}. For the Gowers-Host-Kra norms, the map {f, g \mapsto f \otimes \overline{g}} is an isometry from {U^d(X^{[k]})} to {U^{d-1}(X^{[k+1]})} for any {d \geq 2} and {k \geq 0}.

To see analogous isometries for the Gowers uniformity norms, one has to generalise these norms to the “non-ergodic” setting when one does not average the shift parameter {h} over the entire group {G}, but on a subgroup {H}. Specifically, for finite additive groups {H \leq G} and functions {f_\omega: G \rightarrow {\bf C}} with {\omega \in \{0,1\}^A}, define the local Gowers inner product

\displaystyle \langle \otimes_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} f_\omega \rangle_{U^A(G,H)} = \mathop{\bf E}_{x \in G, h_i \in H \forall i \in A} \prod_{\omega \in \{0,1\}^A} {\mathcal C}^{|\omega|} f_\omega(x + \sum_{i=1}^A \omega_i h_i ).

By foliating {G} into cosets of {H}, one can express this local Gowers inner product as an amalgam of the ordinary Gowers inner product and a Lebesgue inner product. For instance, one has the identity

\displaystyle \|f\|_{U^A(G,H)} = (\sum_{y \in G/H} \| f(\cdot+y) \|_{U^A(H)}^{2^{|A|}})^{1/2^{|A|}}.

We define the inner product space {U^A(G,H)} to be the space of functions from {G} to {{\bf C}} with the above inner product. Given any {j \in A}, we can then create an isometry {\Delta = \Delta_j} from {U^A(G,H)} to {U^{A \backslash \{j\}}( G \times H, H )} by defining

\displaystyle \Delta( f, f' )( x, h ) := f(x+h) \overline{f'(x)}.

(This isometry does not ostensibly depend on {j}, except through the labels of the inner product of the target space {U^{A \backslash \{j\}}( G \times H, H )} of the isometry.)

One can obtain analogous isometries for the Gowers box norms after similarly generalising to “non-ergodic” settings; we leave this as an exercise to the interested reader.

Actually, the “derivative maps” from inner product spaces {V_A} of order {A} to those of order {A \backslash \{j\}} can be constructed abstractly. Indeed, one can view {V_A \otimes \overline{V_A}} as an inner product space of order {A \backslash \{j\}} with the inner product defined on tensor products by

\displaystyle \langle \bigotimes_{\omega' \in \{0,1\}^{A \backslash \{j\}}} {\mathcal C}^{|\omega'|} ( v_{\omega',0} \otimes \overline{v_{\omega',1}} ) \rangle_{A \backslash \{j\}}

\displaystyle := \langle \bigotimes_{(\omega',\omega_j) \in \{0,1\}^A} {\mathcal C}^{|(\omega',\omega_j)|} v_{\omega',\omega_j} \rangle_A

and then the map {v, w \mapsto v \otimes \overline{w}} is an isometry. One can iterate this construction and obtain a cubic complex of inner product spaces

\displaystyle V_B := \bigotimes_{\omega \in \{0,1\}^{A \backslash B}} {\mathcal C}^{|\omega|} V_A

of order {B} for each {B \subset A}, together with a commuting system of derivative isometries {\Delta} from {V_B} to {V_{B \backslash \{j\}}} for each {j \in B \subset A}.

Conversely, one can use cubic complexes to build higher order inner product spaces:

Proposition 3 Let {A} be a finite set. For each {B \subset A}, suppose that we have a vector space {V_B} equipped with a {\{0,1\}^B}-sesquilinear form

\displaystyle \langle \rangle_B: \bigotimes_{\omega\in \{0,1\}^B} {\mathcal C}^{|\omega|} V_B \rightarrow {\bf C}

and suppose that for each {j \in B} one has a sesquilinear product

\displaystyle \Delta_{B \rightarrow B \backslash \{j\}}: V_B \otimes \overline{V_B} \rightarrow V_{B \backslash \{j\}}

obeying the compatibility conditions

\displaystyle \langle \bigotimes_{\omega\in \{0,1\}^B} {\mathcal C}^{|\omega|} v_\omega \rangle_B

\displaystyle = \langle \bigotimes_{\omega' \in \{0,1\}^{B \backslash \{j\}}} \Delta_{B \rightarrow B \backslash \{j\}}( v_{(\omega',0)}, v_{(\omega',1)} ) \rangle_{B \backslash \{j\}}

whenever {v_\omega \in V_B} for all {\omega \in \{0,1\}^B}. Suppose also that the form {\langle \rangle_{\{j\}}} is a classical inner product on {V_{\{j\}}} for every {j \in A}. Then for each {B \subset A}, {V_B} is an inner product space of order {j}, and the maps {\Delta_{B \rightarrow B \backslash \{j\}}} become isometries.

This proposition is established by an easy induction on the cardinality of {B}. Note that we do not require the derivative maps {\Delta_{B \rightarrow B \backslash \{j\}}} to commute with each other, although this is almost always the case in applications.

[Update, May 20: added section on cubic complexes.]