Mirko Fiacchini

Gilles Millérioux

Fast input-free observers for LPV discrete-time systems

This paper deals with fast input-free partial state estimation for discrete-time LPV systems through functional observers. The system inputs are assumed to be unknown and then the observers reduce to functions of finite sequences of the output only. The existence of the observer is proved by resorting to both the notion of inverse system and the concept of maximal A-invariant subspaces. A constructive approach to derive the explicit equations of the observer is provided. An example illustrates the efficiency and the computational aspects of the method.

I. INTRODUCTION

Reconstructing the state vector of a system from its accessible outputs is an important issue in automatic control, in particular for state feedback control law synthesis or diagnosis. In order to estimate the state of a system, it may be assumed that all system inputs are measurable. On the other hand, for systems with some unmeasurable inputs, specific methods should be used. A first solution is to assume that the unmeasurable quantities satisfy a given dynamics. That amounts to modeling the unknown inputs as the response of a suitable a priori chosen dynamical system. An augmented system is then constructed and an observer estimates the augmented state. On the other hand, we may face the situation when the inputs are completely unknown and not measurable. In such a case, we can resort to an unknown input, also called input-free, state reconstruction. The issue of designing such observers goes back to the 70's with a pioneering work [START_REF] Guidorzi | On wonham stabilizability condition in the synthesis of observers for unknown-input systems[END_REF].

In this paper, we are interested in functional nonasymptotic input-free observers. Functional observers are observers which aim at reconstructing a particular (often linear) function of the state (possibly of the input as well). Functional observers for linear systems have been widely addressed since the pioneering work [START_REF] Luenberger | Observers for multivariable systems[END_REF]. A complete framework providing necessary and sufficient conditions of stability and design procedure has been reported in [START_REF] Darouach | Existence and design of functional observers for linear systems[END_REF]. The books [START_REF] Chen | Linear System Theory and Design[END_REF] and more recently [START_REF] Trinh | Functional Observers for Dynamical Systems[END_REF] present a state of the art of research in this field. The consideration of nonlinear discretetime systems with unknown inputs is rather scarce and motivate the present work. The concept of non-asymptotic reconstruction (with known or unknown inputs) has been mainly investigated through the algebraic framework. In short, algebraic observability means that, each state variable can be expressed as an algebraic function of the output, the input (if known) and a finite number of shifts in the discretetime case [START_REF] Sontag | On the observability of polynomial systems, i: Finite-time problems[END_REF] [START_REF] Germundsson | A constructive approach to algebraic observability[END_REF]. Let us notice that different terms are used in the literature to define the same concept: non-asymptotic, dead-beat, finite-time, fast.

The approach proposed in this paper for the design of dead-beat functional observer is based on results of settheory for control, in particular the concept of invariance. Invariance of a set or a subspace of the state space is related to many classical topic in control, such as stability, Lyapunov theory, constrained control. Invariance and settheoretic methods in control appeared at the end of the sixties, see the pioneering work [START_REF] Bertsekas | Infinite-time reachability of state-space regions by using feedback control[END_REF], and they raised an increasing interest in the last decades, see in particular the recent monograph [START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF] and references therein for an exhaustive overview on the topic. The characterization of invariant subspaces, strongly related also with the properties of controllability and observability, has been treated in [START_REF] Basile | Controlled and conditioned invariant subspaces in linear system theory[END_REF]- [START_REF] Basile | Controlled and Conditioned Invariants in Linear system Theory[END_REF]. More recently, invariant subspaces have been used in the context of LPV systems in [START_REF] Balas | Invariant subspaces for lpv systems and their applications[END_REF], and for unknow input state estimation for a particular class of nonlinear continuous-time systems, see [START_REF] Hammouri | Unknown input observer for state affine systems: A necessary and sufficient condition[END_REF]. This paper deals with discrete-time LPV systems with unknown inputs. The objective is two-fold. First, we want to derive existence conditions under which a given state variable (or a linear combination of the state variables) can be expressed as a function of a finite number of shifted outputs. This in accordance with algebraic observability. Secondly, we aim at providing an explicit solution to the problem, that is deriving the equations of the state reconstructor.

The outline of the paper is the following. Section II is devoted to the problem statement, namely the issue of fast input-free reconstruction. In Section III, the existence of the reconstructor is proved and its equations are derived. The the notions of inverse system and invariant subspaces are used. Two approaches are presented. Computational issues are addressed in Section IV. Finally, an example illustrates the efficiency and the computational aspects of the method. Notation: N is the set of natural numbers. Given n ∈ N denote N n = {x ∈ N : 1 ≤ x ≤ n} and Nn = N n ∪ {0}. We denote with x (i) the i-th entry of the vector x. Notation P i denotes the i-th element of a set of matrices and x k is the realization of the time-dependent vector x at time k. We assume the convention that ∏ d i=0 P i = P d . . . P 0 . For a matrix X, X † stands for the classical Moore-Penrose generalized inverse of X.

II. PROBLEM STATEMENT

Consider discrete-time LPV systems obeying

x k+1 = A(θ k )x k + B(θ k )u k y k = C(θ k )x k + D(θ k )u k (1)
where x k ∈ R n is the state vector, u k ∈ R m is the control input, y k ∈ R p is the output vector. The matrices A ∈ R n×n , B ∈ R n×m , C ∈ R p×n and D ∈ R p×m depend on the parameter vector θ k ∈ R t belonging to a known set Ω θ , possibly unbounded. We are interested in the following issue. Problem 1: Given G ∈ R q×n , provide a condition for the existence of a function f θ such that

Gx k = f θ (y k+t 1 , . . . , y k+t 2 ), (2)
for every k ≥ 0, every x k ∈ R n and every possible realization of the parameter θ k ∈ Ω θ , with appropriate integers t 1 , t 2 .

It is noteworthy to point out that this problem is rather general. Indeed, if G is the matrix which selects a part of the components of the state vector, the problem boils down to an analysis issue, that is checking whether the components of x k are algebraically observable. If G is the identity matrix, the problem amounts to check whether the system is algebraically observable. Furthermore, any explicit solution to Problem 1 provides f θ and t 1 , t 2 , besides guaranteeing their existence. Then a fast input-free observer is obtained for reconstructing either a part or the full state or a linear combination of its elements, depending on the structure of G.

A. Inverse system

The proposed approach to solve Problem 1 rests on the notion of inverse system of (1) whose definition and structure are borrowed from [START_REF] Sundaram | Designing stable inverters and state observers for switched linear systems with unknown inputs[END_REF]. Define

O(θ k:k+i ) =        C(θ k ) C(θ k+1 )A(θ k ) . . . C(θ k+i ) i-1 ∏ l=0 A(θ k+l )        , (3)
the vectors

y k:k+i = y T k , y T k+1 , . . . , y T k+i T , θ k:k+i = θ T k , θ T k+1 , . . . , θ T k+i T ,
and the matrix I m×r = I m 0 m×(m•r) . Define also M(θ k:k+i ) in the following recursive way

M(θ k:k+i )= D(θ k ) 0 p×m•(i-1) O(θ k:k+i )B(θ k ) M(θ k+1:k+i ) , with M(θ k:k ) = D(θ k ).
Definition 1: An inverse system of (1) is a system for which, when driven by a sequence of output y k of (1), the trajectory of its state vector xk coincides with the trajectory x k of (1) (possibly up to a delay r referred to as inherent delay) whenever both state vectors share the same initialization.

A straightforward extension of the inverse system, given in [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF], [START_REF] Sundaram | Designing stable inverters and state observers for switched linear systems with unknown inputs[END_REF] for switched linear ones, obeys for LPV systems the following state space description

xk+r+1 = P θ (θ k:k+r ) xk+r + Q θ (θ k:k+r )y k:k+r , (4)
with

P θ (θ k:k+r ) = A(θ k ) -Q θ (θ k:k+r )O(θ k:k+r ), Q θ (θ k:k+r ) = B(θ k )I m×r M † (θ k:k+r ). (5)
Following the same lines as in [15] [19], defining e k = x k -xk+r as the state error reconstruction, it can be shown, from ( 1) and ( 4) that

e k+1 = P θ (θ k:k+r )e k , (6)
under the conditions of invertibility, [START_REF] Sundaram | Designing stable inverters and state observers for switched linear systems with unknown inputs[END_REF]. Hence, if e 0 = 0, that is xr = x 0 , then e k = 0 and so xk+r = x k for any k > 0, in accordance with Definition 1. The matrix P θ (θ k:k+r ) corresponds to the inverse dynamics. Hence, Problem 1 can be reformulated as follows.

Problem 2: Given G ∈ R q×n , provide a condition for the existence of a function f θ such that

G xk = f θ (y k+t ′ 1 , . . . , y k+t ′ 2 ), (7)
for every k ≥ 0, every xk ∈ R n and every possible realization of the parameter θ k ∈ Ω θ , with appropriate integers t ′ 1 , t ′ 2 .

III. DESCRIPTION OF THE APPROACH

First, notice that the parametric dependence of the matrices in ( 4) and ( 5) with respect to θ k:k+r ∈ Ω r+1 θ is not linear in general. However, given the set Ω θ , there always exists a function p such that the system (4) depends linearly on the parameter ρ k defined as ρ k = p(θ k:k+r ). A set Ω ρ ⊆ R d such that ρ k ∈ Ω ρ if θ k:k+r ∈ Ω r+1 θ can always be determined as well. To simplify the notation, we define

P(ρ k ) = P θ (θ k:k+r ), Q(ρ k ) = Q θ (θ k:k+r ), ȳk = y k:k+r .
Following the considerations above, the assumption below can be posed.

Assumption 1: Suppose that P(ρ k ) depends on the parameter ρ k ∈ Ω ρ as

P(ρ k ) = d ∑ i=0 P i ρ (i) k .
Hereafter, unless otherwise stated, Assumption 1 will hold. Remark 1: Notice that no assumptions are done on Ω θ , then nor on Ω ρ . In fact Ω ρ can be whatever subset in the space of the parameter ρ. Furthermore, the approach could be easily generalized to more general parameter dependencies, polynomial ones for instance.

A sufficient condition for Problem 2 to have a solution follows.

Proposition 1: There is a solution to Problem 2 with t ′ 1 = -Kr -1 and t ′ 2 = -1 if K and P i , for i ∈ Nd , are such that

G K ∏ k=0 P i k = 0, (8)
for all I = [i 0 , . . . , i K ] T ∈ NK+1 d .
Proof: By definition we have

G xk+r+1 = G ∑ i 0 ∈ Nd ρ (i 0 ) k P i 0 xk+r + GQ(ρ k ) ȳk , G xk+r+2 = G ∑ I ∈ N2 d 1 ∏ l=0 ρ (i l ) k+l P i l xk+r + GQ(ρ k+1 ) ȳk+1 + +G ∑ I ∈N 1 d ρ (i 0 ) k P i 0 Q(ρ k ) ȳk , • • • G xk+r+K+1 = G ∑ I ∈ NK+1 d K ∏ l=0 ρ (i l ) k+l P i l xk+r + GQ(ρ k+K ) ȳk+K + +G K-1 ∑ j=0 ∑ I ∈ N j+1 d K ∏ l=K-j ρ (i l ) k+l P i l Q(ρ k+K-1-j ) ȳk+K-1-j , where I = [i 0 , . . . , i k ] T ∈ Nk+1 d for all k ∈ NK . If for every I ∈ NK+1 d condition (8) holds, then Gx k+K+1 = G xk+r+K+1 = GQ(ρ k+K ) ȳk+K + +G K-1 ∑ j=0 ∑ I ∈ N j+1 d K ∏ l=K-j ρ (i l ) k+l P i l Q(ρ k+K-1-j ) ȳk+K-1-j .
(9) Finally, after a suitable shift, we get that (9) completes the proof and shows that f θ involves the output y k+l (and the parameter θ k+l ) for -K -r -1 ≤ l ≤ -1.

Remark 2: Some sequence among all the admissible ones are not allowed since, by definition, P(ρ i+1 ) is not independent with respect to P(ρ i ). Such sequences could be discarded from the analysis.

In the following, two computation-oriented conditions for (8) to hold are presented. They involve the concept of invariant subspaces. First we introduce the concept of Ainvariant subspace, see the monograph [START_REF] Basile | Controlled and Conditioned Invariants in Linear system Theory[END_REF] for details.

Definition 2 (A-invariant subspace): Given a linear transformation

A : R n → R n an A-invariant is a subspace V ⊆ R n such that AV ⊆ V .
Given the parameter-dependent family of linear transformations

A(ρ) : R n → R n , for ρ ∈ Ω ρ , a subspace V ⊆ R n is a robust A-invariant if A(ρ)V ⊆ V , ∀ρ ∈ Ω ρ .
Geometrically, V is an A-invariant subspace if every trajectory starting inside it, remains confined within it.

Proposition 2: Given a linear transformation A : R n → R n , its kernel ker (A) is an A-invariant.

Proof: Denote with T a basis matrix of ker (A). By definition (see [START_REF] Basile | Controlled and Conditioned Invariants in Linear system Theory[END_REF]), ker (A) is A-invariant for the linear transformation A : R n → R n if and only if there exists a matrix

X such that AT = T X. ( 10
)
Since T is a basis of ker (A) it follows that AT = 0, and then (10) holds merely posing X = 0. Definition 3: Given P(ρ k ) as in Assumption 1, define

P = d i=0 ker P T i .
Moreover, denote with M ∈ R n×g a basis matrix of P and N ∈ R n×(n-g) a basis of its complement. Notice that the definition of P above involves the transposes of the matrices P i for all i ∈ Nd .

Proposition 3: The set P as in Definition 3 is A-invariant for the parameter-dependent system given by

z k+1 = P T (ρ k )z k with P T (ρ k ) = d ∑ i=0 ρ (i) k P T i = P(ρ k ) T . ( 11
)
Proof: From Proposition 2, P is an A-invariant for every P T i with i ∈ Nd and M a basis matrix of P. By definition, P is A-invariant also for the system whose dynamics is given by [START_REF] Guidorzi | On wonham stabilizability condition in the synthesis of observers for unknown-input systems[END_REF] if and only if there exists X such that

0 = d ∑ i=0 ρ (i) k P T i M = MX,
that holds posing X = 0.

A. Kernel-based approach

A sufficient condition for Proposition 1 to hold, and hence an admissible solution to Problem 2, follows.

Proposition 4: Consider the system (4), the set P and the matrix M as in Definition 3. If G ∈ R q×n is such that the columns of G T are in P, i.e. there is X ∈ R d×g such that G = XM T , then there exists a solution of Problem 2 with K = 1.

Proof: The result stems directly from definition of P, as if the rows of G are in P then

GP i = 0, ∀i ∈ Nd ,
and then the condition (8), sufficient for solving the Problem 2, holds with K = 1. The result in Proposition 4 is implicitly based on the fact that the set P is an A-invariant for the system (4) as proved in Proposition 3. On the other hand, this condition requires that the dynamics of the system (4) would reach the particular A-invariant subspace in one step. This is obviously restrictive but provides an interesting insight on the problem and a clue on its possible alternative as shown below.

B. A-invariant-based approach

An alternative to Proposition 4 for condition [START_REF] Darouach | Existence and design of functional observers for linear systems[END_REF] to hold is now provided.

Definition 4: Let Assumption 1 hold for the system (4). Denote with G the maximal A-invariant subspace for P i , for i ∈ Nd , contained in ker (G), with g = dim (G ), T ∈ R n×g its basis matrix and T ∈ R n×h a matrix such that T = [ T , T ] ∈ R n×n is nonsingular.

An interesting property, based on the results presented in [START_REF] Basile | Controlled and Conditioned Invariants in Linear system Theory[END_REF], is the fact that the dynamics of a system on every Ainvariant subspace can be decoupled by the dynamics on complementary subspace.

Proposition 5: Let Assumption 1 hold for the system (4) and consider G and T as in Definition 4. Then G is Ainvariant for P(ρ k ) and there exist P(ρ k ) ∈ R g×g , P(ρ k ) ∈ R g×h and P(ρ k ) ∈ R h×h , linear in ρ k such that:

P(ρ k ) = T P(ρ k ) P(ρ k ) 0 P(ρ k ) T -1 , (12)
for every ρ k ∈ Ω ρ .

Proof: First notice that, by definition of A-invariant subspaces, if G is an A-invariant for all P i with i ∈ Nd then it is A-invariant for every single P i . This implies that for all i ∈ Nd there exist Pi ∈ R g×g , Pi ∈ R g×h , Pi ∈ R h×h and T ∈ R g×g , T ∈ R h×h such that

P i = [ T T ] Pi Pi 0 Pi [ T T ] -1 , (13)
with T basis of G , see Theorem 3.2.1 in [START_REF] Basile | Controlled and Conditioned Invariants in Linear system Theory[END_REF]. Posing

P(ρ k ) = d ∑ i=0 Pi ρ (i) k , P(ρ k ) = d ∑ i=0 Pi ρ (i) k , P(ρ k ) = d ∑ i=0 Pi ρ (i) k , then (12)
holds and G is a robust A-invariant for P(ρ k ) according to [START_REF] Germundsson | A constructive approach to algebraic observability[END_REF]. We must further consider the concept of nilpotent semigroups to derive the result which finally solves Problem 2. Let us first recall some basics related to nilpotent semigroups.

Definition 5 (Semigroup): A semigroup S is a set together with an associative internal law. It is said to be finite if it has a finite number of elements. If S is a set of matrices, the associative internal law is the matrix multiplication. We denote by 0 the absorbing element of a semigroup when it exists.

Definition 6 (Nilpotent semigroup): A semigroup S with an absorbing element 0 is said to be nilpotent if there is a positive integer t such that the internal law applied to any t elements of S is always equal to 0. The smallest integer t is called the nilpotency class of S . If S is a set of matrices, applying the internal low to any t elements of S amounts to performing the product of t matrices of S . The absorbing element is in this case the null matrix.

Let us notice that the property of nilpotency for a semigroup is less conservative than a closely related property often encountered in control (see [START_REF] Liberzon | Basic problems in stability and design of switched systems[END_REF]), namely, solvability of a Lie algebra.

Theorem 1: Let Assumption 1 hold for the system (4) and consider G and T as in Definition 4. If Pi for all i ∈ Nd generate a nilpotent semigroup of class t then, Problem 2 is solved with K = t.

Proof: By construction, T is a basis of the A-invariant subspace G that is contained in ker (G) then G T = 0. Hence, for all I = [i 0 , . . . , i K ] T ∈ NK d , we have

G K ∏ k=0 P i k = G K ∏ k=0 T Pi k Pi k 0 Pi k T -1 = = G[ T , T ] K ∏ k=0 Pi k Pi k 0 Pi k T -1 = = K ∏ k=0 [ 0 q×g , G T ] Pi k Pi k 0 Pi k T -1 = = 0 q×g , G T K ∏ k=0 Pi k T -1 = 0.
The last equality precisely stems from the fact that Pi with i ∈ Nd generate a nilpotent semigroup of class K. Thus condition ( 8) is satisfied for all I = [i 0 , . . . , i K ] T ∈ NK d , which is sufficient for the existence of a solution to Problem 2. Furthermore, the solution is explicit since the function f θ , that is the input-free reconstructor, obeys [START_REF] Dubi | An algorithmic approach to simultaneous triangularization[END_REF] in this case.

Remark 3: It can be shown, see [START_REF] Parriaux | Nilpotent semigroups for the characterization of flat outputs of discrete-time switched linear and lpv systems[END_REF], that the condition is also necessary for at least two particular cases: when the inherent delay r is equal to zero or if it is equal to one and that C is constant. These two cases encompass a large class of systems.

Remark 4: Clearly, the class of nilpotency t, and so K is smaller than or equal to h, that is the dimension of the subspace complementary to G in R n . Then, the bigger the dimension of G , the smaller such a bound, in general. Moreover, notice that for lower values of q, number of rows of G, the dimension of G can be higher and then the dimension of matrices Pi is smaller. This is conceptually reasonable, as the smaller is the partial state to be estimated, the smaller is the subspace within which the system dynamics must converge to zero in finite time.

IV. COMPUTATIONAL ISSUES In this section, we provide some insights on the computational procedures for obtaining the A-invariant subspaces (Proposition 5) and for determining whether a set of matrices generates a nilpotent semigroup (Theorem 1). According to Definition 2, a subspace V is A-invariant for a linear system if its image through the linear transformation is contained in V . Well established results on how to generate A-invariant subspaces have been presented in literature, see in particular [START_REF] Basile | Controlled and Conditioned Invariants in Linear system Theory[END_REF]. We recall here the basic ideas and we provide some practical details on the computation.

First, for a linear system whose dynamics is given by the linear transformation A : R n → R n , two trivial A-invariant subspaces contained in R n are the origin and the space R n . In general, one can be interested either in the minimal Ainvariant containing a given subspace or the maximal Ainvariant contained in a subspace. The latter case enters our concern. Denoting with J the maximal A-invariant contained in the subspace V , J is computed as illustrated below.

Algorithm 1: Given the subspace V ⊆ R n and the linear transformation A : R n → R n the maximal A-invariant subspace J is provided by the following iteration:

J 0 = V , J i+1 = V ∩ A -1 J i , i = 0, . . . , n. (14)
The algorithm stops after a finite number of iterations n, whose upper bound is n -1. In particular, the iteration can be stopped as soon as J i+1 = J i .

Remark 5: Notice that, with a slight abuse of notation, the meaning of the symbol A -1 does not denote the inverse of matrix A, but it is the operator that associates to a subspace its inverse image, that is, given the subspace J i ⊆ R n :

A -1 J i = {x ∈ R n : Ax ∈ J i }.
Indeed, it is worth pointing out that the inverse image of a subspace can be computed also for linear transformation given by noninvertible matrices, as in our case. For instance, the inverse image of the origin is given by the kernel of A.

Remark 6: It can be proved that the same sequence of subspaces J i with i = 0, . . . , n is generated by the iteration:

J i+1 = J i ∩ A -1 J i , i = 0, . . . , n. ( 15
)
Remark 7: The Algorithm 1, either implementing the iteration ( 14) or [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF], is based, substantially, on the computation of the intersection between subspaces and of the inverse image of a subspace. We provide hereafter a sketch of the procedure. Consider two subspaces V ∈ R n and U ∈ R n , whose basis matrices are V ⊆ R n×v and U ⊆ R n×u . The subspace V ∩ A -1 U is given by the vectors x ∈ R n that can be expressed as a linear combination of the columns of V and their image through A as a linear combination of those of U. Then, in practice, x ∈ V ∩ A -1 U if there exists y ∈ R v and z ∈ R u such that x = V y and Ax = Uz, that means such that AV y = Uz. Hence, V ∩ A -1 U can be obtained by computing the kernel of [AV, U].

Interestingly for our purpose, the Algorithm 1 can be extended to the case of LPV systems, see [START_REF] Balas | Invariant subspaces for lpv systems and their applications[END_REF], [START_REF] Basile | Controlled and Conditioned Invariants in Linear system Theory[END_REF]. In general, given a linear transformation A(ρ) depending on the parameter ρ, the maximal A-invariant subspace, referred to as robust, containing V is given by the following algorithm.

Algorithm 2: Given the subspace V ⊆ R n and the linear parameter dependent transformation A(ρ) : R n → R n , with ρ ∈ Ω ρ the maximal robust A-invariant subspace J is provided by the following iteration:

J 0 = V , J i+1 = J 0 ∩ ρ∈Ω ρ A(ρ) -1 J i , i = 0, . . . , n.
Similarly to the linear case, the algorithm stops after a finite number n of iterations, smaller or equal than n -1. The problem for computing robust A-invariant subspaces appears when the set Ω ρ is uncountable. Approximation methods are available. For the case of finite Ω ρ , the Algorithm 2 provides the maximal robust A-invariant contained in V after a finite number of operations. This is precisely the case for LPV systems considered in Assumption 1, for which the Algorithm 2 delivers the A-invariant after a finite number of iterations.

As for the computational aspects regarding the nilpotency property, we must recall the Levitsky's theorem (Theorem 2.1.7 stated in [START_REF] Radjavi | Simultaneous Triangularization[END_REF]).

Theorem 2 (Levitsky's theorem): Any semigroup of nilpotent matrices can be triangularized.

In other words, all the matrices of a same nilpotent semigroup can be triangularized by means of a common change of basis. The triangularization can be performed for example with the algorithm given in [START_REF] Dubi | An algorithmic approach to simultaneous triangularization[END_REF]. Such an algorithm is quite appealing since it allows the triangularization to be performed with a complexity which is linear with respect to the number of matrices and polynomial with respect to the dimension (see details for flat ouput characterization purposes in [START_REF] Parriaux | Nilpotent semigroups for the characterization of flat outputs of discrete-time switched linear and lpv systems[END_REF]).

V. ILLUSTRATIVE EXAMPLE

We consider the LPV system (1) whose dynamics is given by the following matrices

A =   -4 1 0 θ k 0 1 -2 0 0   , B =   0 1 1   , C =   1 0 0   T , D = 0.
This system is a SISO one. Hence, since D = 0, CB = 0 and CA(θ k )B = 0 for all k, it can be inferred that the inherent delay is r = 2. Hence, the related inverse systems (4) is characterized (see ( 5)) by the parameter-dependent matrix (1) k = 0. A basis of the kernel is given by the vectors [0, 1, 0] T and [0, 0, 1] T . Let us check whether Theorem 1 is fulfilled. To do so, and as explained in Section IV, we must resort to Algorithm 2. Iteration [START_REF] Millérioux | Flatness of switched linear discrete-time systems[END_REF] leads to a sequence of subspaces J i , illustrated in Figure 1, and provides the maximal robust A-invariant subspace J in ker(G). The basis of J is T = [0, 0, 1] T . After computing the orthogonal basis T , the affine LPV subsystem related to the orthogonal subspace is computed according to Proposition 5 and is given by matrices P0 = -4 1 -16 4 , P1 = 0 0 0 0 .

P(θ k ) =   -4 1 0 -16 4 0 -14 -θ k 4 -1   , that is affine in θ k ∈ R.
It turns out that Theorem 1 is fulfilled because P0 and P1 are both nilpotent (necessary condition) and generate a nilpotent semigroup with class of nilpotency t = 1. Hence, K = 1.

We obtain the same result if we consider Problem 2 with G = [0, 1, 0]. Actually, it is worth noticing that the same J is obtained for every G whose columns lie in the subspace spanned by [1, 0, 0] T and [0, 1, 0] T . As stressed in the proof of Theorem 1, an explicit solution to Problem 2 can be obtained through [START_REF] Dubi | An algorithmic approach to simultaneous triangularization[END_REF]. Finally, by a direct consequence of the definition of the inverse system, the equality xk+r = x k applies and we can thereby directly infer an explicit solution to Problem 1. By considering respectively G = [1, 0, 0] and G = [0, 1, 0], the function f θ of the reconstructor obeys

x (1) k = y k x (2) k = y k+1 + 4y k ( 16
)
The result is obvious for x [START_REF] Balas | Invariant subspaces for lpv systems and their applications[END_REF] k that is for G = [1, 0, 0]. Summarizing, it has been shown that the first two components of x k are algebraically observable and ( 16) gives an explicit fast input-free observer. Now, considering G = [0, 0, 1], it turns out that, after applying the Algorithm 2, the resulting maximal robust A-invariant contained in the kernel of G, that is J , is the origin, see Figure 2. As it turns out, Theorem 1 is not fulfilled because the resulting matrices P 0 and P 1 do not generate a nilpotent semigroup. In fact, this is explained by noticing that P 0 is not nilpotent, having an eigenvector 1.

VI. CONCLUSIONS

An approach for testing algebraic observability and designing fast input-free state reconstructors for discrete-time LPV systems has been presented. The existence conditions have been derived. They are based on the notion of inverse system, invariant subspaces and nilpotent semigroups. The proof is constructive since it provides a way of deriving the equations of the reconstructor. The results apply for SISO and MIMO systems and without restriction on the relative degree. The results sound interesting to more general cases like LPV systems with polynomial dependence or LDI systems.

JFig. 1 .

 1 Fig. 1. Sequence of subspaces J i and J for G = [1, 0, 0]. Consider Problem 2 with G = [1, 0, 0]. Then the kernel of G is the plane x

1 GFig. 2 .

 12 Fig. 2. Sequence of subspaces J i and J for G = [0, 0, 1].

This work was partially supported by the CPER MISN Région Lorraine (AOC Project 2011), Fédération Charles Hermite, ESSTIN and INRIA.


Bryna Kra
email: kra@math.northwestern.edu

A POINT OF VIEW ON GOWERS UNIFORMITY NORMS

Gowers norms have been studied extensively both in the direct sense, starting with a function and understanding the associated norm, and in the inverse sense, starting with the norm and deducing properties of the function. Instead of focusing on the norms themselves, we study associated dual norms and dual functions. Combining this study with a variant of the Szemerédi Regularity Lemma, we give a decomposition theorem for dual functions, linking the dual norms to classical norms and indicating that the dual norm is easier to understand than the norm itself. Using the dual functions, we introduce higher order algebras that are analogs of the classical Fourier algebra, which in turn can be used to further characterize the dual functions.

Introduction

In his seminal work on Szemerédi's Theorem, Gowers [START_REF] Gowers | A new proof of Szemerédi's Theorem[END_REF] introduced uniformity norms U(d) for each integer d ≥ 1, now referred to as Gowers norms or Gowers uniformity norms, that have played an important role in the developments in additive combinatorics over the past ten years. In particular, Green and Tao [START_REF] Green | The primes contain arbitrarily long arithmetic progressions[END_REF] used Gowers norms as a tool in their proof that the primes contain arbitrarily long arithmetic progressions; shortly thereafter, they made a conjecture [START_REF] Green | Linear Equations in the Primes[END_REF], the Inverse Conjecture for the Gowers norms, on the algebraic structures underlying these norms. Related seminorms were introduced by the authors [START_REF] Host | Nonconventional averages and nilmanifolds[END_REF] in the setting of ergodic theory, and the ergodic structure theorem provided a source of motivation in the formulation of the Inverse Conjecture. For each integer d ≥ 1 and δ > 0, Green and Tao introduce a class F (d, δ) of "(d -1)-step nilsequences of bounded complexity," which we do not define here, and then showed:

Inverse Theorem for Gowers Norms (Green, Tao, and Ziegler [START_REF] Green | An inverse theorem for the Gowers U s+1 [N ] norm[END_REF]). For each integer d ≥ 1 and δ > 0, there exists a constant C = C(d, δ) > 2000 Mathematics Subject Classification. 11B30. The first author was partially supported by the Institut Universitaire de France and the second author by NSF grant 0900873. 0 such that for every function f on Z/NZ with |f | ≤ 1 and f U (d) ≥ δ, there exists g ∈ F (d, δ) with g; f ≥ C.

Another approach was later developed by Szegedy, outlined in the announcement [START_REF] Camarena | Nilspaces, nilmanifolds and their morphisms[END_REF] for the article [START_REF] Szegedy | On higher order Fourier analysis[END_REF].

We are motivated by the work of Gowers in [START_REF] Gowers | Decompositions, approximate structure, transference, and the Hahn-Banach Theorem[END_REF]. Several ideas come out of this work, in particular the motivation that there are advantages to working with algebra norms. The Gowers norms U(d) are classically defined in Z/NZ, but we choose to work in a general compact abelian group. For most of the results presented here, we take care to distinguish between the group Z/NZ and the interval [1, . . . , N], of the natural numbers N. On the other hand, for applications in additive combinatorics, the results are often more directly proved without this separation. This is a conscious choice that allows us to separate what about Gowers norms is particular to the combinatorics of Z/NZ and what is more general. In summary, our point of view is that of harmonic analysis, rather than combinatorial.

More generally, the Gowers norms can be defined on a nilmanifold. This is particularly important in the ergodic setting, where analogous seminorms were defined by the authors in [START_REF] Host | Nonconventional averages and nilmanifolds[END_REF] in an arbitrary measure preserving system; these seminorms are exactly norms when the space is a nilmanifold. While we restrict ourselves to abelian groups in this article, most of the results can be carried out in the more general setting of a nilmanifold without significant changes.

Instead of focusing on the Gowers norms themselves, we study the associated dual norms that fit within this framework , as well as the associated dual functions. Moreover, in the statement of the Inverse Theorem, and more generally in uses of the Gowers norms, one typically assumes that the functions are bounded by 1. In the duality point of view, instead we study functions in the dual space itself, allowing us to consider functions that are within a small L 1 error from functions in this space. This allows us to restrict ourselves to dual functions of functions in a certain L p class (Theorem 3.8). In particular, the further development of the material on dual functions leads us to a new decomposition result for anti-uniform functions of the type favored in additive combinatorics.

This leads to a rephrasing of the Inverse Theorem in terms of dual functions (see Section 2.2 for precise meanings of the term) in certain L p classes, and in this form the Gowers norms do not appear explicitly (Section 3.3). This reformulates the Inverse Theorem more in a classical analysis context.

The dual functions allow us to introduce algebras of functions on the compact abelian group Z. For d = 2, this corresponds to the classical Fourier algebra. Finding an interpretation for the higher order uniformity norms is hard and no analogs of Fourier analysis with simple formulas, such as Parseval, exist. For d > 2, the higher order Fourier algebras are analogs of the classical case of the Fourier algebra. These algebras allow us to further describe the dual functions. Starting with a dual function of level d, we find that it lies in the Fourier algebra of order d, giving us information on its dual norm U(d) * , and by an approximation result, we gain further insight into the original function.

The main result of the paper is a theorem on compactness (Theorem 5.2) of dual functions, obtained by applying a variation of the Szemerédi Regularity Lemma. Roughly speaking, the theorem states that within a given error, all shifts of a dual function of degree d are well approximated by elements of a module of bounded rank on the ring of dual functions of degree d -1. This property is reminiscent of the uniform almost periodicity norms introduced by Tao [START_REF] Tao | A quantitative ergodic theory proof of Szemerédi's theorem[END_REF] and close to some combinatorial properties used, in particular, in [START_REF] Green | An inverse theorem for the Gowers U s+1 [N ] norm[END_REF].

Acknowledgement: We thank the referee for a careful reading that considerably improved the article.

Gowers norms: definition and elementary bounds

2.1. Notation. Throughout, we assume that Z is a compact abelian group and let µ denote Haar measure on Z. If Z is finite, then µ is the uniform measure; the classical case to keep in mind is when Z = Z N = Z/NZ and the measure of each element is 1/N.

All functions are implicitly assumed to be real valued. When Z is infinite, we also implicitly assume that all functions and sets are measurable. For 1 ≤ p ≤ ∞, • p denotes the L p (µ) norm; if there is a need to specify a different measure ν, we write • L p (ν) .

We fix an integer d ≥ 1 throughout and the dependence on d is implicit in all statements.

We have various spaces of various dimensions: 1, d, 2 d . Ordinary letters t are reserved for spaces of one dimension, vector notation t for dimension d, and bold face characters t for dimension 2 d .

If f is a function on Z and t ∈ Z, we write f t for the function on Z defined by

f t (x) = f (x + t), where x ∈ Z. If f is a µ-integrable function on Z, we write E x∈Z f (x) = f (x) dµ(x).
We use similar notation for multiple integrals. If f and g are functions on Z, we write f ; g = E x∈Z f (x)g(x), assuming that the integral on the right hand side is defined.

If d is a positive integer, we set

V d = {0, 1} d . Elements of V d are written as ǫ = ǫ 1 ǫ 2 • • • ǫ d , without commas or paren- theses. Writing 0 = 00 • • • 0 ∈ V d , we set V d = V d \ { 0}. For x ∈ Z 2 d , we write x = (x ǫ : ǫ ∈ V d ). For ǫ ∈ V d and t = (t 1 , t 2 , . . . , t d ) ∈ Z d we write ǫ • t = ǫ 1 t 1 + ǫ 2 t 2 + • • • + ǫ d t d .

2.2.

The uniformity norms and the dual functions: definitions. The uniformity norms, or Gowers norms,

f U (d) , d ≥ 2, of a function f ∈ L ∞ (µ) are defined inductively by f U (1) = E x f (x)| and for d ≥ 2, f U (d) = E t f.f t 2 d-1 U (d-1) 1/2 d . Note that • U (1)
is not actually a norm. (See [START_REF] Gowers | A new proof of Szemerédi's Theorem[END_REF] for more on these norms and [START_REF] Host | Nonconventional averages and nilmanifolds[END_REF] for a related seminorm in ergodic theory.) If there is ambiguity as to the underlying group Z, we write • U (d,Z) . These norms can also be defined by closed formulas:

(1)

f 2 d U (d) = E x∈Z, t∈Z d ǫ∈V d f (x + ǫ • t).
We rewrite this formula. Let Z d be the subset of Z 2 d defined by

(2)

Z d = (x + ǫ • t : ǫ ∈ V d ) : x ∈ Z, t ∈ Z d .
This set can be viewed as the "set of cubes of dimension d" (see, for example, [START_REF] Gowers | A new proof of Szemerédi's Theorem[END_REF] or [START_REF] Host | Nonconventional averages and nilmanifolds[END_REF]). It is easy to check that Z d is a closed subgroup of Z 2 d . Let µ d denote its Haar measure. Then Z d is the image of

Z d+1 = Z × Z d under the map (x, t) → (x + ǫ • t : ǫ ∈ V d ). Furthermore, µ d is the image of µ × µ × . . . × µ (taken d + 1 times) under the same map. If f ǫ , ǫ ∈ V d , are functions in L ∞ (µ), then E x∈Z, t∈Z d ǫ∈V d f ǫ (x + ǫ • t) = Z d ǫ∈V d f ǫ (x ǫ ) dµ d (x).
In particular, for f ∈ L ∞ (µ),

(3)

f 2 d U (d) = Z d ǫ∈V d f (x ǫ ) dµ d (x).
Associating the coordinates of the set V d with the coordinates of the Euclidean cube, we have that the measure µ d is invariant under permutations that are associated to the isometries of the Euclidean cube. These permutations act transitively on V d . For d = 2, by Parseval's identity we have that

(4) f U (2) = f ℓ 4 ( Z) ,
where Z is the dual group of Z and f is the Fourier transform of f . For d ≥ 3, no analogous simple formula is known and the interpretation of the Gowers uniformity norms is more difficult. A deeper understanding of the higher order norms is, in part, motivation for the current work. We make use of the "Cauchy-Schwarz-Gowers Inequality" (CSG) (see [START_REF] Gowers | A new proof of Szemerédi's Theorem[END_REF]) used in the proof of the subadditivity of Gowers norms:

Cauchy-Schwarz-Gowers Inequality. Let f ǫ , ǫ ∈ V d , be 2 d func- tions belonging to L ∞ (µ). Then (CSG) E x∈Z, t∈Z d f ǫ (x + ǫ • t) = Z d ǫ∈V d f ǫ (x ǫ ) dµ d (x) ≤ ǫ∈{0,1} d f ǫ U (d) .
Applying the Cauchy-Schwarz-Gowers Inequality with half of the functions equal to f and the other half equal to the constant 1, we deduce that

f U (d+1) ≥ f U (d) for every f ∈ L ∞ (µ). Definition 2.1. For f ∈ L ∞ (µ), define the dual function D d f on Z by (5) D d f (x) = E t∈Z d ǫ∈ V d f (x + ǫ • t).
It follows from the definition that (6)

f 2 d U (d) = D d f ; f . More generally, we define: Definition 2.2. If f ǫ ∈ L ∞ for ǫ ∈ V d , we write (7) D d (f ǫ : ǫ ∈ V d )(x) = E t∈Z d ǫ∈ V d f ǫ (x + ǫ • t).
We call such a function the cubic convolution product of the functions f ǫ .

There is a formal similarity between the cubic convolution product and the classic convolution product; for example,

D 2 (f 01 , f 10 , f 11 )(x) = E t 1 t 2 ∈Z f 01 (x + t 1 )f 10 (x + t 2 )f 11 (x + t 1 + t 2 ).
2.3. Elementary bounds. For ǫ ∈ V d and α ∈ {0, 1}, we write ǫα = ǫ 1 . . . ǫ d α ∈ V d+1 , maintaining the convention that such elements are written without commas or parentheses. Thus

V d+1 = { ǫ0 : ǫ ∈ V d } ∪ { ǫ1 : ǫ ∈ V d }.
The image of Z d+1 under each of the two natural projections on Z 2 d is Z d , and the image of the measure µ d+1 under these projections is

µ d . Lemma 2.3. Let f ǫ , ǫ ∈ V d , be 2 d -1 functions in L ∞ (µ). Then for all x ∈ Z, (8) D d (f ǫ : ǫ ∈ V d )(x) ≤ ǫ∈ V d f ǫ 2 d-1 .
In particular, for every f ∈ L ∞ (µ),

D d f ∞ ≤ f 2 d -1 2 d-1 . Proof. (9)
Without loss, we can assume that all functions are nonnegative. We proceed by induction on d ≥ 2.

For nonnegative f 01 , f 10 and

f 11 ∈ L ∞ (µ), D 2 (f 01 , f 10 , f 11 )(x) = E t 1 ∈Z f 01 (x + t 1 )E t 2 ∈Z f 10 (x + t 2 )f 11 (x + t 1 + t 2 ) ≤ E t 1 ∈Z f 01 (x + t 1 ) f 10 2 f 11 2 ≤ f 01 2 f 10 2 f 11 2 .
This proves the case d = 2. Assume that the result holds for some d ≥ 2. Let f ǫ , ǫ ∈ V d+1 , be nonnegative and belong to L 2 d (µ) . Then

D d+1 (f ǫ : ǫ ∈ V d+1 )(x) = E s∈Z d η∈ V d f η0 (x + η • s)E u∈Z θ∈V d f θ1 (x + θ • s + u) .
For every s ∈ Z d and every x ∈ Z, by the Hölder Inequality,

E u∈Z θ∈V d f θ1 (x + θ • s + u) ≤ θ∈V d f θ1 2 d .
On the other hand, by the induction hypothesis, for every x ∈ Z,

E s∈Z d η∈ V d f η0 (x + η • s) ≤ η∈ V d f η0 2 d-1 ≤ η∈ V d f η0 2 d
and (8) holds for d + 1.

Corollary 2.4. Let f ǫ , ǫ ∈ V d , be 2 d functions belonging to L ∞ (µ). Then (10) E x∈Z, t∈Z d ǫ∈V d f ǫ (x + ǫ • t) ≤ ǫ∈V d f ǫ 2 d-1 .
In particular, for

f ∈ L ∞ (µ), (11) f
U (d) ≤ f 2 d-1 .
By the corollary, the definition (1) of the Gowers norm U(d) can be extended by continuity to the space L 2 d-1 (µ), and if f ∈ L 2 d-1 (µ), then the integrals defining f U (d) in Equation (1) exist and (11) holds. Using similar reasoning, if f ǫ , ǫ ∈ V d , are 2 d functions belonging to L 2 d-1 (µ), then the integral on the left hand side of (10) exists, the Cauchy-Schwarz-Gowers (CSG) remains valid, and [START_REF] Lovász | Szemerédi's lemma for the analyst[END_REF] holds. If we have 2 d-1 functions in L 2 d-1 (µ), then Inequality (8) remains valid. Similarly, the definitions and results extend to D d f and to cubic convolution products for functions belonging to L 2 d-1 (µ).

The bounds given here (such as [START_REF] Szegedy | On higher order Fourier analysis[END_REF]) can be improved and made sharp. In particular, one can show that

f U (d) ≤ f 2 d /(d+1) and Df ∞ ≤ f 2 d -1
(2 d -1)/d . We omit the proofs, as they are not used in the sequel.

When Z is infinite, we define the uniform space of level d to be the completion of L ∞ (µ) under the norm U(d). As d increases, the corresponding uniform spaces shrink. A difficulty is that the uniform space may contain more than just functions. For example, if Z = T := R/Z, the uniform space of level 2 consists of distributions T on T whose Fourier transform

T satisfies n∈Z | T (n)| 4 < +∞. Corollary 2.5. Let f ǫ , ǫ ∈ V d , be 2 d functions on Z and let α ∈ V d . Assume that f α ∈ L 1 (µ) and f ǫ ∈ L 2 d-1 (µ) for ǫ = α. Then E x∈Z, t∈Z d ǫ∈V d f ǫ (x + ǫ • t) ≤ f α 1 ǫ∈V d ǫ = α f ǫ 2 d-1 .
Proof. The left hand side is equal to

Z d f α (x α ) ǫ∈V d ǫ = α f ǫ (x ǫ ) dµ d (x)
Using the symmetries of the measure µ d , we can reduce to the case that α = 0, and then the result follows from Lemma 2.3.

We note for later use:

Lemma 2.6. For every f ∈ L 2 d-1 (µ), D d f (x) is a continuous function on Z. More generally, if f ǫ , ǫ ∈ V d are 2 d -1 functions belonging to L 2 d-1 (µ), then the cubic convolution product D d (f ǫ : ǫ ∈ V d )(x) is a continuous function on Z.
Proof. By density and [START_REF] Host | Nonconventional averages and nilmanifolds[END_REF], it suffices to prove the result when f ǫ ∈ L ∞ (µ) for every ǫ ∈ V d . Furthermore, we can assume that |f ǫ | ≤ 1 for every ǫ ∈ V d . Let g be the function on Z defined in the statement. For x, y ∈ Z, we have that

|g(x) -g(y)| ≤ ǫ∈ V d f ǫ,x -f ǫ,y 1
and the result follows.

Duality

3.1. Anti-uniform spaces. Consider the space L 2 d-1 (µ) endowed with the norm U(d). By [START_REF] Szegedy | On higher order Fourier analysis[END_REF], the dual of this normed space can be viewed as a subspace of L 2 d-1 /(2 d-1 -1) (µ), with the duality given by the pairing •; • . Following Green and Tao [START_REF] Green | The primes contain arbitrarily long arithmetic progressions[END_REF], we define Definition 3.1. The anti-uniform space of level d is defined to be the dual space of L 2 d-1 (µ) endowed with the norm U(d). Functions belonging to this space are called anti-uniform functions of level d.

The norm on the anti-uniform space given by duality is called the antiuniform norm of level d and is denoted by

• * U (d) .
Obviously, when Z is finite, then every function on Z is an antiuniform function.

It follows from the definitions that

f * U (d+1) ≤ f * U (d)
for every f ∈ L ∞ (µ). Thus, as d increases, the corresponding antiuniform spaces increase. More explicitly, a function g

∈ L 2 d-1 /(2 d-1 -1) (µ) is an anti-uniform function of level d if sup | g; f | : f ∈ L 2 d-1 (µ), f U (d) ≤ 1 < +∞.
In this case, g * U (d) is defined to be equal to this supremum. Again, in case there may be ambiguity as to the underlying space Z, we write

• * U (d,Z) .
We conclude:

Corollary 3.2. For every anti-uniform function g of level d, g * U (d) ≥ g 2 d-1 /(2 d-1 -1) .
For d = 2, the anti-uniform space consists of functions g ∈ L 2 (µ) with g ℓ 4/3 ( Z) finite, and for these functions, [START_REF] Camarena | Nilspaces, nilmanifolds and their morphisms[END_REF] g * U (2) = g ℓ 4/3 ( Z) . This example illustrates that the • * U (d) can not be bounded by the norm

• 2 d-1 /(2 d-1 -1)
, meaning that there is no bound for the converse direction of Corollary 3.2.

The dual spaces allow us to give an equivalent reformulation of the Inverse Theorem in terms of dual norms. By a dual formulation, we mean the determination of a family F ′ (d, δ), for each integer d ≥ 1 and each δ > 0, of "(d -1)-step nilsequences of bounded complexity" that satisfies the following statement:

Inverse Theorem, Dual Form. For each integer d ≥ 1 and each δ > 0, every function g on Z N with g * U (d) ≤ 1 can be written as

g = h + ψ with h ∈ F ′ (d, δ) and ψ 1 ≤ δ.
Remark 3.3. Note that the the function g is not assumed to be bounded.

We show that this formulation is equivalent to the Inverse Theorem, with simple and explicit relations between the classes F (d, δ) and F ′ (d, δ), but with different relations in each direction.

Proof. First assume the Inverse Theorem and let F = F (d, δ) be the class of nilsequences and C = C(d, δ) be as in its formulation. Let

K = F + B L 1 (µ) (C),
where F denotes the convex hull of F and the second term is the ball of radius C in L 1 (µ). Let g be a function with | g; h | ≤ C for all h ∈ K. In particular, |g| ≤ 1 and | g; h | ≤ C for all h ∈ K. By the Inverse Theorem, we have that g U (d) < δ. By the Hahn-Banach Theorem,

K ⊃ B U (d) * (C/δ), the ball of radius C/δ in the anti-uniform norm of level d. Thus B U (d) * (1) ⊂ (δ/C) F + B L 1 (µ) (δ).
Taking F ′ (d, δ) to be (δ/C) F, we have the statement. Conversely, assume the Dual Form. Say that

F ′ = F ′ (d, δ/2) is the convex hull of F 0 = F 0 (d, δ). Assume that f satisfies |f | ≤ 1 and f U (d) ≥ δ.
Then there exists g with g * U (d) ≤ 1 and g; f ≥ δ. By the Dual Form, there exists h ∈ F ′ and ψ with ψ 1 < δ/2 such that

g = h + ψ. Since δ ≤ g; f = h + ψ; f = h; f + ψ; f and ψ; f < δ/2, we have that h; f < δ/2. Since h ∈ F ′ , there exists h ′ ∈ F 0 with h ′ ; f > δ/2 and
we have the statement of the Inverse Theorem.

Dual functions and anti

-uniform spaces. Lemma 3.4. Let f ǫ , ǫ ∈ V d , belong to L 2 d-1 (µ). Then D d (f ǫ : ǫ ∈ V d ) * U (d) ≤ ǫ∈ V d f ǫ 2 d-1 .
Proof. For every h ∈ L 2 d-1 (µ), we have that

h; g = E x∈Z, t∈Z d h(x + 0 • t) ǫ∈ V d f ǫ (x + ǫ • t) ≤ h U (d) • ǫ∈ V d f ǫ ≤ h U (d) • ǫ∈ V d f ǫ 2 d-1
by the Cauchy-Schwarz-Gowers Inequality (CSG) and Inequality [START_REF] Szegedy | On higher order Fourier analysis[END_REF].

In particular, for f ∈ L 2 d-1 (µ), we have that

D d f * U (d) ≤ f 2 d -1 U (d) .
On the other hand, by (6),

f 2 d U (d) = D d f ; f ≤ D d f * U (d) • f U (d) and thus D d f * U (d) ≥ f 2 d -1 U (d)
. We conclude:

Proposition 3.5. For every f ∈ L 2 d-1 (µ), D d f * U (d) = f 2 d -1 U (d) .
While the following proposition is not used in the sequel, it gives a helpful description of the anti-uniform space: Proposition 3.6. The unit ball of the anti-uniform space of level d is the closed convex hull in

L 2 d-1 /(2 d-1 -1) (µ) of the set D d f : f ∈ L 2 d-1 (µ), f U (d) ≤ 1 .
Proof. The proof is a simple application of duality.

Let

B ⊂ L 2 d-1 /(2 d-1 -1) (µ) be the unit ball of the anti-uniform norm • * U (d) .
Let K be the convex hull of the set in the statement and let K be its closure in

L 2 d-1 /(2 d-1 -1) (µ).
By Proposition 3.5, for every

f with f U (d) ≤ 1, we have D d f ∈ B. Since B is convex, K ⊂ B. Furthermore, B is contained in the unit ball of L 2 d-1 /(2 d-1 -1) (µ) and is a weak* compact subset of this space. Therefore, B is closed in L 2 d-1 /(2 d-1 -1) (µ) and K ⊂ B.
We check that K ⊃ B. If this does not hold, there exists g ∈

L 2 d-1 /(2 d-1 -1) (µ) satisfying g * U (d) ≤ 1 and g / ∈ K. By the Hahn- Banach Theorem, there exists f ∈ L 2 d-1 (µ) with f ; h ≤ 1 for every h ∈ K and f ; g > 1. This last property implies that f U (d) > 1. Taking φ = f -1 U (d) • f , we have that φ U (d) = 1 and D d φ ∈ K. Thus by the first property of f , D d φ; f ≤ 1. But D d φ; f = f -2 d +1 U (d) D d f ; f = f U (d)
and we have a contradiction.

It can be shown that when Z is finite, the set appearing in Proposition 3.6 is already closed and convex: Proposition 3.7. Assume Z is finite. Then the set

D d f : f U (d) ≤ 1
is the unit ball of the anti-uniform norm.

We omit the proof of this result, as the proof (for finite Z) is similar to that of Theorem 3.8 below, which seems more useful. For the general case, the analogous statement is not as clear because the "uniform space" does not consist only of functions.

3.3.

Approximation results for anti-uniform functions. We now use the vocabulary reviewed and developed to prove the following decomposition theorem: Theorem 3.8. Assume d ≥ 1 is an integer. For every anti-uniform function g with g * U (d) = 1, integer k ≥ d -1, and δ > 0, the function g can be written as g = D d f + h, where

f 2 k ≤ 1/δ; f U (d) ≤ 1; h 2 k /(2 k -1) ≤ δ.
As in the Dual Form of the Inverse Theorem, we do not assume that the function g is bounded.

Proof. Fix k ≥ d -1 and δ > 0. For f ∈ L 2 k (µ), define (13) |||f ||| = f 2 k U (d) + δ 2 k f 2 k 2 k 1/2 k if k ≥ d; f 2 d U (d) + δ 2 d f 2 d 2 d-1 1/2 d if k = d -1. Since f U (d) ≤ f 2 d-1 ≤ f 2 k for every f ∈ L 2 k (µ), |||f ||| is well defined on L 2 k (µ) and ||| • ||| is a norm on this space, equivalent to the norm • 2 k . Let ||| • ||| * be the dual norm of ||| • |||: for g ∈ L 2 k /(2 k -1) (µ), |||g||| * = sup f ; g : f ∈ L 2 k (µ), |||f ||| ≤ 1 .
This dual norm is equivalent to the norm

• 2 k /(2 k -1) . Since |||f ||| ≥ f U (d) for every f ∈ L 2 k (µ), we have that |||g||| * ≤ g * U (d) for every g ∈ L 2 k /(2 k -1) (µ). Fix an anti-uniform function g with g * U (d) ≤ 1. Since |||f ||| ≥ f U (d) for any f , we have that c := |||g||| * ≤ g * U (d) ≤ 1. Set g ′ = c -1 g, and so |||g ′ ||| * = 1. Since the norm ||| • ||| is equivalent to the norm • 2 k and the Banach space (L 2 k (µ), • 2 k ) is reflexive, the Banach space (L 2 k (µ), ||| • |||) is also reflexive. This means that (L 2 k (µ), |||•|||) is the dual of the Banach space (L 2 k /(2 k -1) (µ), ||| • ||| * ). Therefore, there exists f ′ ∈ L 2 k (µ) with |||f ′ ||| = 1 and g ′ ; f ′ = 1.
By definition [START_REF] Tao | A quantitative ergodic theory proof of Szemerédi's theorem[END_REF]

of |||f ′ |||, (14) f ′ U (d) ≤ 1 and f ′ 2 k ≤ 1/δ.
Assume first that k ≥ d. (At the end, we explain the modifications needed to cover the case k = d -1.) By ( 3), [START_REF] Green | An inverse theorem for the Gowers U 4 norm[END_REF], and the symmetries of the measure µ d , for every φ ∈ L 2 k (µ) and every t ∈ R,

(15) f ′ + tφ 2 d U (d) = f ′ 2 d U (d) + 2 d t D d f ′ ; φ + o(t)
, where by o(t) we mean any function such that o(t)/t → 0 as t → 0.

Raising this to the power 2 k-d , we have that

f ′ + tφ 2 k U (d) = f ′ 2 k U (d) + 2 k t f ′ 2 k -2 d U (d) D d f ′ ; φ + o(t).
On the other hand,

f ′ + tφ 2 k 2 k = f ′ 2 k 2 k + 2 k t f ′2 k -1 ; φ + o(t).
Combining these expressions and using the definition (13) of |||f ′ + tφ||| and of |||f ′ |||, we have that

|||f ′ + tφ||| 2 k = f ′ + tφ 2 k U (d) + δ 2 k f ′ + tφ 2 k 2 k =|||f ′ ||| 2 k + 2 k t f ′ 2 k -2 d U (d) D d f ′ ; φ + δ 2 k 2 k t f ′2 k -1 ; φ + o(t) =1 + 2 k t f ′ 2 k -2 d U (d) D d f ′ ; φ + δ 2 k 2 k t f ′2 k -1 ; φ + o(t)
. Raising this to the power 1/2 k , we have that

|||f ′ + tφ||| = 1 + t f ′ 2 k -2 d U (d) D d f ′ ; φ + δ 2 k t f ′2 k -1 ; φ + o(t)
. Since for every φ ∈ L 2 k (µ) and every t ∈ R we have

1 + t g ′ ; φ = g ′ ; f ′ + tφ ≤ |||f ′ + tφ|||, it follows that 1 + t g ′ ; φ ≤ 1 + t f ′ 2 k -2 d U (d) D d f ′ ; φ + δ 2 k t f ′2 k -1 ; φ + o(t)
. Since this holds for every t, we have

g ′ ; φ = f ′ 2 k -2 d U (d) D d f ′ ; φ + δ 2 k f ′2 k -1 ; φ .
Since this holds for every φ, we conclude that

g ′ = f ′ 2 k -2 d U (d) D d f ′ + δ 2 k f ′2 k -1 . Thus g = c f ′ 2 k -2 d U (d) D d f ′ + cδ 2 k f ′2 k -1 . Set f = c f ′ 2 k -2 d U (d) 1/(2 d -1) f ′ and h = cδ 2 k f ′2 k -1 . Then g = D d f + h
and by [START_REF] Tao | Additive combinatorics[END_REF],

f U (d) ≤ 1 ; f 2 k ≤ 1/δ h 2 k /(2 k -1) = cδ 2 k f ′ 2 k -1 2 k ≤ δ.
Finally, if k = d -1, for every φ ∈ L 2 k (µ) and every t ∈ R, we still have that (15) holds, and

f ′ + tφ 2 d 2 d-1 = f ′ 2 d 2 d-1 + 2 d t f ′ 2 d-1 2 d-1 f ′2 d-1 -1 ; φ + o(t). Thus |||f ′ + tφ||| = 1 + t D d f ′ ; φ + δ 2 d f ′ 2 d-1 2 d-1 f ′2 d-1 -1 ; φ + o(t).
As above, we deduce that

g ′ = D d f ′ + δ 2 d f ′ 2 d-1 2 d-1 f ′2 d-1 -1 . Taking f = c 1/(2 d -1) f ′ and h = cδ 2 d f ′ 2 d-1 2 d-1 f ′2 d-1 -1 , we have the statement.
When Z is finite, we can say more: Theorem 3.9. Assume that Z is finite. Given a function g with g * U (d) = 1 and δ > 0, the function g can be written as

g = D d f + h, where f ∞ ≤ 1/δ; f U (d) ≤ 1; h 1 ≤ δ.
Proof. By Theorem 3.8, for every k ≥ d -1 we can write

g = D d f k + h k , where f k 2 k ≤ 1/δ; h k 2 k /(2 k -1) ≤ δ; f k U (d) ≤ 1. Let N = |Z|. Since f k 2 k ≤ 1/δ, it follows that f k ∞ ≤ N/δ. Sim- ilarly, h k ∞ ≤ Nδ.
By passing to a subsequence, since the functions are uniformly bounded we can therefore assume that f k → f and that

h k → h pointwise as k → +∞. Thus D d f k → D d f pointwise and so g = D d f + h. Since f k U (d) → f U (d) , it follows that f U (d) ≤ 1. For every k ≥ d -1, we have that h k 1 ≤ h k 2 k /(2 k -1) ≤ δ. Since h k 1 → h 1 , it follows that h 1 ≤ δ. For ℓ ≥ k ≥ d -1, f ℓ 2 k ≤ f ℓ 2 ℓ ≤ 1/δ.
Taking the limit as ℓ → +∞, we have that f 2 k ≤ 1/δ for every k ≥ d -1 and so f ∞ ≤ 1/δ. Question 3.10. Does Theorem 3.9 also hold when Z is infinite?

We conjecture that the answer is positive, but the proof given does not cover this case.

3.4. Applications. Theorems 3.8 and 3.9 give insight into the U(d) norm, connecting it to the L p norms. For example, we have: Corollary 3.11. Let φ be a function with φ ≤ 1 and φ U (d) = θ > 0. Then for every p ≥ 2 d-1 , there exists a function f such that

f p ≤ 1 and D d f ; φ > (θ/2) 2 d . Furthermore, if Z is finite, there exists a function f with f ∞ ≤ 1 and D d f ; φ > (θ/2) 2 d .
Note that for finite Z, this last statement is reminiscent of the Inverse Theorem.

Proof. It suffices to prove the result when p = 2 k for some integer k ≥ d -1. There exists g with g * U (d) = 1 and g; φ = θ. Taking δ = θ/2 in Theorem 3.8, we have the first statement. For the second statement, we apply Theorem 3.9. Theorem 3.9 leads to another reformulation of the Inverse Theorem, without any explicit reference to the Gowers norms. Once again, we mean the determination of a family F ′′ (d, δ), for each d ≥ 1 and δ > 0, satisfying:

Inverse Theorem, Reformulated Version. For every δ > 0 and every function φ on Z N with φ ∞ ≤ 1, the function D d φ can be written as D d φ = g + h with g ∈ F ′′ (d, δ) and h 1 ≤ δ.

We show that the statement is equivalent to the Dual Form of the Inverse Theorem, with simple and explicit relations between the families F ′ (d, δ) and F ′′ (d, δ), again with different relations in each direction.

ψ 1 ≤ δ/2. Define F ′ = F ′ (d, δ) to be equal to (2/δ) 2 d -1 F ′′ (d, η),
where η is a positive constant to be defined later and F ′′ (d, η) is as in the Reformulated Version. By the Reformulated Version,

D d h = f + ψ, with f ∈ F ′ and ψ 1 ≤ (2/δ) 2 d -1 η. Then g = f + φ + ψ with f ∈ F ′ and φ + ψ 1 ≤ δ/2 + (2/δ) 2 d -1 η.
Taking η = (δ/2) 2 d , we have the result.

3.5. Anti-uniformity norms and embeddings. This section is a conjectural, and somewhat optimistic, exploration of the possible uses of the theory of anti-uniform norms developed here. The main interest is not the sketches of proofs included, but rather the questions posed and the directions that we conjecture may be approached using these methods.

Definition 3.12. If G is a (d -1)-step nilpotent Lie group and Γ is a discrete, cocompact subgroup of G, the compact manifold X = G/Γ is (d -1)-step nilmanifold.
The natural action of G on X by left translations is written as (g, x) → g.x for g ∈ G and x ∈ X.

We recall the following "direct" result (a converse to the Inverse Theorem), proved along the lines of arguments in [START_REF] Host | Nonconventional averages and nilmanifolds[END_REF]: Proposition 3.13 (Green and Tao [START_REF] Green | An inverse theorem for the Gowers U 3 -norm, with applications[END_REF], Proposition 12.6). Let X = G/Γ be a (d -1)-step nilmanifold, x ∈ X, g ∈ G, F be a continuous function on X, and N ≥ 2 be an integer. Let f be a function on Z N with |f | ≤ 1. Assume that for some η > 0,

E 0≤n<N f (n)F (g n • x) ≥ η.
Then there exists a constant c = c(X, F, η) > 0 such that

f U (d) ≥ c.
The key point is that the constant c depends only on X, F , and η, and not on f , N, g or x.

Remark 3.14. In [START_REF] Green | An inverse theorem for the Gowers U 3 -norm, with applications[END_REF], the average is taken over the interval [-N/2, N/2] instead of [0, N), but the proof of Proposition 3.13 is the same for the modified choice of interval.

A similar result is given in Appendix G of [START_REF] Green | An inverse theorem for the Gowers U 4 norm[END_REF], and proved using simpler methods, but there the conclusion is about the norm f U (d,Z N ′ ) , where N ′ is sufficiently large with respect to N.

By duality, Proposition 3.13 can be rewritten as Proposition 3.15. Let X = G/Γ, x, g, F be as in Proposition 3.13. Let N ≥ 2 be an integer and let h denote the function n → F (g n • x) restricted to [0, N) and considered as a function on Z N . Then for every η > 0, we can write h = φ + ψ where φ and ψ are functions on Z N with φ * U (d) ≤ c(X, F, η) and ψ 1 ≤ η. Proposition 3.13 does not imply that h * U (d) is bounded independent of N, and using [START_REF] Camarena | Nilspaces, nilmanifolds and their morphisms[END_REF], one can easily construct a counterexample for d = 2 and X = T. On the other hand, for d = 2 we do have that h * U (d) is bounded independent of N when the function F is sufficiently smooth. Recalling that the Fourier series of a continuously differentiable function on T is absolutely convergent and directly computing using Fourier coefficients, we have: Proposition 3.16. Let F be a continuously differentiable function on T and let α ∈ T. Let N ≥ 2 be an integer and let h denote the restriction of the function n → F (α n ) to [0, N), considered as a function on

Z N . Then h * U (2) ≤ c F ℓ 1 (Z)
, where c is a universal constant.

A similar result holds for functions on T k . It is natural to ask whether a similar result holds for d > 2. For the remained of this section, we assume that every nilmanifold X is endowed with a smooth Riemannian metric. For k ≥ 1, we let C k (X) denote the space of k-times continuously differentiable functions on X, endowed with the usual norm • C k (X) . We ask if the dual norm is bounded independent of N: Question 3.17. Let X = G/Γ be a (d -1)-step nilmanifold. Does there exist an integer k ≥ 1 and a positive constant c such that for all choices of a function F ∈ C k (X), g ∈ G, x ∈ X and integer N ≥ 2, writing h for the restriction to [0, N) of the function n → F (g n • x), considered as a function on Z N , we have

h * U (d) ≤ c F C k (X) ?
Definition 3.18. If g ∈ G and x ∈ X are such that g N • x = x, we say that the map n → g n • x is an embedding of Z N in X.

Proposition 3.19. The answer to Question 3.17 is positive under the additional hypothesis that n → g n • x is an embedding of Z N in X, meaning that

g N • x = x.
The proof of this proposition is similar to that of Proposition 5.6 in [START_REF] Host | Uniformity norms on ℓ ∞ and applications[END_REF] and so we omit it.

More generally, we can phrase these results and the resulting question for groups other than Z N . We restrict ourselves to the case of T, as the extension to T k is clear. By the same argument used for Proposition 3.13, we have: Proposition 3.20. Let X = G/Γ be a (d-1)-step nilmanifold, x ∈ X, u be an element in the Lie algebra of G, and F be a continuous function on X. Let f be a function on T with |f | ≤ 1. Assume that for some η > 0 we have

f (t)F exp(tu) • x dt ≥ η,
where we identify T with [0, 1) in this integral. Then there exists a constant c = c(X, F, η) > 0 such that

f U (d) ≥ c.
By duality, Proposition 3.20 can be rewritten as Proposition 3.21. Let X = G/Γ, x, u, F , and c = c(X, F, η) be as in Proposition 3.20. Let h denote the restriction of the function t → F exp(tu) • x) to [0, 1), considered as a function on T. Then for every η > 0, we can write h = φ + ψ, where φ and ψ are functions on T with φ * U (d) ≤ c and ψ 1 ≤ η. We also pose the analog of Question 3.17 for the group T: Question 3.22. Let X = G/Γ be a (d -1)-step nilmanifold. Does there exist an integer k ≥ 1 and a positive constant c such that for all choices of a function F ∈ C k (X), u in the Lie algebra of G, and x ∈ X, writing h for the restriction of the function t → F exp(tu) • x to [0, 1), considered as a function on T, we have

h * U (d) ≤ c F C k (X) ? Analogous to Proposition 3.
19, the answer to this question is positive under the additional hypothesis that t → exp(tu) • x is an embedding of T in X, meaning that exp(u) • x = x.

Multiplicative structure

4.1. Higher order Fourier Algebras. In light of Theorem 3.8, the family of functions g on Z of the form g = D d f for f ∈ L 2 k (µ) for some k ≥ d -1 is an interesting one for further study. More generally, we also consider cubic convolution products for functions f ǫ , ǫ ∈ V d , belonging to L 2 k (µ) for some k ≥ d -1. We restrict ourselves to the case k = d -1, as it gives rise to interesting algebras. Definition 4.1. For an integer d ≥ 1, define K(d) to be the convex hull of

D d (f ǫ : ǫ ∈ V d ) : f ǫ ∈ L 2 d-1 (µ) for every ǫ ∈ V d and ǫ∈ V d f ǫ 2 d-1 ≤ 1 .
By Lemma 2.6, K(d) is included in the algebra C(Z) of continuous functions on Z and, by [START_REF] Host | Nonconventional averages and nilmanifolds[END_REF], it is included in the unit ball of C(Z) for the uniform norm.

Define K(d) to be the closure of K(d) in C(Z) under the uniform norm.

Define A(d) to be the linear subspace of C(Z) spanned by K(d), endowed with the norm • A(d) such that K(d) is its unit ball.

We call A(d) the Fourier algebra of order d.

We begin with some simple remarks. Clearly, for d ≥ 2, if Z is a finite group, then K(d) = K(d), and every function on Z belongs to A(d).

It follows from the definitions that A(1) consists of the constant functions with the norm • A(1) being absolute value.

For every g ∈ A(d), again by using [START_REF] Host | Nonconventional averages and nilmanifolds[END_REF] we have that (16) g ∞ ≤ g A(d) .

By Lemma 3.4, we have that g belongs to that anti-uniform space of level d and that

g * U (d) ≤ g A(d) . Lemma 4.2. Let K c (d) to be the convex hull of D d (f ǫ : ǫ ∈ V d ) : f ǫ ∈ C(Z) for every ǫ ∈ V d and ǫ∈ V d f ǫ 2 d-1 ≤ 1 . Then K(d) is the closure of K c (d) in C(Z) under the uniform norm.
Let (g n ) be a sequence in A(d) such that g n A(d) is bounded. If g n converges uniformly to some function g, then g ∈ A(d) and g A(d) ≤ sup n g n A(d) .

The space A(d) endowed with the norm • A(d) is a Banach space.

Proof. By density, the first statement follows immediately from Inequality (16). The second statement follows immediately from the definition.

Let h n be a sequence in A(d) with n h n A(d) < +∞. We have to show that the series n h n converges in A(d). By (16), the series converges uniformly. Set h to be the sum of the series. By the second part of the lemma, h belongs to A(d) and h A(d) ≤ n g n A(d) . Applying the same argument again, we obtain that for every N, h -

N n=1 h n A(d) = ∞ n=N +1 h n A(d) ≤ ∞ n=N +1 h n A(d)
and the result follows.

4.2. The case d = 2. We give a further description for d = 2, relating these notions to classical objects Fourier analysis.

By definition, V 2 = {01, 10, 11}. Every function g defined as a cubic convolution product of

f ǫ , ǫ ∈ V 2 , satisfies ξ∈ Z | g(ξ)| 2/3 = ξ∈ Z ǫ∈ V 2 | f ǫ (ξ)| 2/3 (17) ≤ ǫ∈ V 2 ξ∈ Z | f ǫ (ξ)| 2 1/3 = ǫ∈ V 2 f ǫ 2/3 2 . Thus ξ∈ Z | g(ξ)| ≤ ǫ∈ V 2 f ǫ 2 .
It follows that for g ∈ A(2), we have that

ξ∈ Z | g(ξ)| ≤ g A(2) .
On the other hand, let g be a continuous function on Z with ξ∈ Z | g(ξ)| < +∞. This function can be written as (in this example, we make an exception to our convention that all functions are real-valued)

g(x) = ξ∈ Z g(ξ) ξ(x) = ξ∈ Z g(ξ)E t 1 ,t 2 ∈Z ξ(x + t 1 )ξ(x + t 2 )ξ(x + t 1 + t 2 ).
By Lemma 4.2, we have that g ∈ A(2) and g A(2) ≤ ξ∈ Z | g(ξ)|.

We summarize these calculations: (18)

gg ′ A(d) ≤ g A(d) g ′ A(d) .
Proof. By the first part of Lemma 4.2 and density, it suffices to show that when

g(x) = D d (f ǫ : ǫ ∈ V d )(x) and g ′ (x) = D d (f ′ ǫ : ǫ ∈ V d )(x),
with f ǫ and f ′ ǫ ∈ C(Z) for every ǫ ∈ V d and with

ǫ∈ V d f ǫ 2 d-1 ≤ 1 and ǫ∈ V d f ′ ǫ 2 d-1 ≤ 1, we have gg ′ ∈ A(d) and gg ′ A(d) ≤ 1. Rewriting, we have that g(x)g ′ (x) = E s∈Z d E t∈Z d ǫ∈ V d f ǫ (x + ǫ • t) f ′ ǫ (x + ǫ • s) Letting u = s -t, this becomes g(x)g ′ (x) = E u∈Z d E t∈Z d ǫ∈ V d f ǫ (x + ǫ • t) f ′ ǫ (x + ǫ • u + ǫ • t) = E u∈Z d E t∈Z d ǫ∈ V d f ǫ . f ′ ǫ, ǫ• u )(x + ǫ • t) = E u∈Z d g ( u) (x),
where

g ( u) (x) := D d f ǫ . f ′ ǫ, ǫ• u : ǫ ∈ V d (x) = E t∈Z d ǫ∈ V d f ǫ . f ′ ǫ, ǫ• u (x + ǫ • t). ( 19
)
We claim that (20)

E u∈Z d ǫ∈ V d f ǫ . f ′ ǫ, ǫ• u 2 d-1 ≤ ǫ∈V d f ǫ 2 d-1 f ′ ǫ 2 d-1 ≤ 1.
Namely,

E u∈Z d ǫ∈ V d f ǫ • f ′ ǫ, ǫ• u 2 d-1 = E u 1 ,...,u d-1 ∈Z ǫ∈ V d ǫ d =0 f ǫ • f ′ ǫ,ǫ 1 u 1 +•••+ǫ d-1 u d-1 2 d-1 E u d ∈Z f ǫ • f ′ ǫ,ǫ 1 u 1 +•••+ǫ d-1 u d-1 +u d 2 d-1 ≤ E u 1 ,...,u d-1 ∈Z ǫ∈ V d ǫ d =0 f ǫ • f ′ ǫ,ǫ 1 u 1 +•••+ǫ d-1 u d-1 2 d-1 ǫ∈ V d ǫ d =1 E u d ∈Z f ǫ • f ′ ǫ,ǫ 1 u 1 +•••+ǫ d-1 u d-1 +u d 2 d-1 2 d-1 1/2 d-1
.

But, for all u 1 , u 2 , . . . , u d-1 ∈ Z and every ǫ ∈ V d with ǫ d = 1,

E u d ∈Z f ǫ . f ′ ǫ,ǫ 1 u 1 +•••+ǫ d-1 u d-1 +u d 2 d-1 2 d-1 = E v∈Z f ǫ . f ′ ǫ,v 2 d-1 2 d-1 = f ǫ 2 d-1 2 d-1 f ′ ǫ 2 d-1 2 d-1 . On the other hand, E u 1 ,...,u d-1 ∈Z ǫ∈ V d ǫ d =0 f ǫ . f ′ ǫ,ǫ 1 u 1 +•••+ǫ d-1 u d-1 2 d-1 ≤ ǫ∈ V d ǫ d =0 E u 1 ,...,u d-1 ∈Z f ǫ . f ′ ǫ,ǫ 1 u 1 +•••+ǫ d-1 u d-1 2 d-1 2 d-1 1/2 d-1
.

But, for ǫ ∈ V d with ǫ d = 0, we have that ǫ 1 , . . . , ǫ d-1 are not all equal to 0 and

E u 1 ,...,u d-1 ∈Z f ǫ . f ′ ǫ,ǫ 1 u 1 +•••+ǫ d-1 u d-1 2 d-1 2 d-1 =E w∈Z f ǫ . f ′ ǫ,w 2 d-1 2 d-1 = f ǫ 2 d-1 2 d-1 f ′ ǫ 2 d-1 2 d-1 .

Combining these relations, we have proved claim (20).

On the other hand, since by assumption each of the functions

( u, x) → f ǫ (x)f ′ ǫ, ǫ• u (x) is continuous on Z d × Z, we have that each of the func- tions u → f ǫ . f ′ ǫ, ǫ• u 2 d-1 is continuous on Z d .
Moreover, by the definition (19) of the functions g ( u) , it follows that the function ( u, x) → g ( u) (x) is also continuous on Z d ×Z (see also Corollary 2.4 and Lemma 2.6).

Therefore, for every δ > 0, there exists a finite subset { u 1 , . . . , u n } of Z d and non-negative numbers λ 1 , . . . , λ n with n j=1 λ j = 1 such that

gg ′ - n j=1 λ j g ( u j ) ∞ = sup x∈Z E u∈Z d g ( u) (x) - n j=1 λ j g ( u j ) (x) < δ; E u∈Z d ǫ∈ V d f ǫ . f ′ ǫ, ǫ• u 2 d-1 - n j=1 λ j ǫ∈ V d f ǫ . f ′ ǫ, ǫ• u j 2 d-1 < δ,
and combining this with (20), we now have that

n j=1 λ j ǫ∈ V d f ǫ . f ′ ǫ, ǫ• u j 2 d-1 < 1 + δ.
Therefore, the function n j=1 λ j g ( u j ) belongs to the set (1 + δ)K(d). Letting δ tend to 0, we conclude that gg ′ belongs to K(d) and in particular, gg ′ ∈ A(d) and gg ′ A(d) ≤ 1. 4.4. Tao's uniform almost periodicity norms. In [START_REF] Tao | A quantitative ergodic theory proof of Szemerédi's theorem[END_REF], Tao introduced a sequence of norms, the uniform almost periodicity norms, that also play a dual role to the Gowers uniformity norms: Definition 4.5 (Tao [13]). For f : Z → C, define f UAP 0 (Z) to be equal to |c| if f is equal to the constant c, and to be infinite otherwise. For d ≥ 1, define f UAP d+1 (Z) to be the infimum of all constants M > 0 such that for all n ∈ Z,

T n f = ME h∈H (c n,h g h ),
for some finite nonempty set H, collection of functions

(g h ) h∈H from Z to C satisfying g h L ∞ (Z) ≤ 1, collection of functions (c n,h ) n∈Z,h∈H from Z to C satisfying c n,h UAP d (Z) ≤ 1,

and a random variable h taking values in H.

When the underlying group is clear, we omit it from the notation and write

f UAP d (Z) = f UAP d .
Remark 4.6. The definition given in [START_REF] Tao | A quantitative ergodic theory proof of Szemerédi's theorem[END_REF] implicitly assumes that Z is finite; to extend to the case that Z is infinite, take H to be an arbitrary probability space and view the functions g h and c n,h as random variables.

Tao shows that this defines finite norms UAP d for d ≥ 1 and that for finite Z, the uniformly almost periodic functions of order d (meaning functions for which the UAP d norm is bounded) form a Banach algebra:

f g UAP d ≤ f UAP d g UAP d .
The UAP d-1 and A(d) norms are related: both are algebra norms and they satisfy similar properties, such as

f UAP d-1 ≥ f * U (d) and f A(d) ≥ f * U (d)
. For d = 2, the two norms are in fact the same (an exercise in [START_REF] Tao | Additive combinatorics[END_REF] due to Green and shown in Section 4.2 below). However, in general we do not know if they are equal:

Question 4.7. For a function f : Z → C, is f A(d) = f UAP d-1 for all d ≥ 2?
In particular, while the UAP norms satisfy

f UAP(d-1) ≥ f UAP(d)
for all d ≥ 2, we do not know if the same inequality holds for the norms A(d).

F (x) = ǫ∈V d f ǫ (x ǫ ) with f ǫ ∈ L 2 d (µ)
for every ǫ and

ǫ∈V d f ǫ 2 d ≤ 1.
By the remark following [START_REF] Szegedy | On higher order Fourier analysis[END_REF],

M(d) is included in the unit ball of L 2 (µ d ). Define M (d) to be the closure of M(d) in L 2 (µ d ).
Define the space D(d) of decomposable functions to be the linear span of M (d), endowed with the norm Lemma 4.9. Let M c (d) to be the convex hull of the family of functions on Z d that can be written as

• D(d) such that M (d) is the unit ball. We have that D(d) ⊂ L 2 (µ d ) and that F L 2 (µ d ) ≤ F D(d) for every F ∈ D(d).
(22) F (x) = ǫ∈V d f ǫ (x ǫ ) with f ǫ ∈ C(Z)
for every ǫ and

ǫ∈V d f ǫ 2 d ≤ 1. Then M(d) is the closure of M c (d) in L 2 (µ d ). Let (F n ) be a sequence in D(d) such that F n D(d) is bounded. If F n converges to some function F in L 2 (µ d ), then F ∈ D(d) and F D(d) ≤ sup n F n D(d) .
The space D(d) endowed with the norm • D(d) is a Banach space.

The proof of this lemma is nearly identical to that of Lemma 4.2 and so we omit it. 4.6. Diagonal translations. Definition 4.10. For t ∈ Z, we write t ∆ = (t, t, . . . , t) ∈ Z d . The map x → x + t ∆ is called the diagonal translation by t.

Let I(d) denote the subspace of L 2 (µ d ) consisting of functions invariant under all diagonal translations. The orthogonal projection π on I(d) is given by

πF (x) = E t∈Z F (x + t ∆ ). Proposition 4.11. If F ∈ D(d), then πF ∈ D(d) and πF D(d) ≤ F D(d) . Furthermore, πF ∈ L ∞ (µ d ) and πF L ∞ (µ d ) ≤ F D(d) .
In particular, functions

F ∈ D(d) ∩ I(d) are bounded on Z d and satisfy F ∞ ≤ F D(d) .
Proof. We start by proving the second statement. We begin with the case that F is defined as in (21). Rewriting the definition of πF (x), we have that for every x ∈ Z d ,

|πF (x)| = E t∈Z ǫ∈V d f ǫ,x ǫ (t) ≤ ǫ∈V d f ǫ,x ǫ 2 d ≤ 1 and thus πF L ∞ (µ d ) ≤ 1. This bound remains valid if F belongs to the convex hull M(d) of functions of this type. Assume now that F belongs to M (d). Let (F n ) be a sequence in M(d) converging to F in L 2 (µ d ).
We have that πF n L ∞ (µ d ) ≤ 1 for every n, and since the map

π is continuous in the L 2 (µ d )-norm, πF n → πF in L 2 (µ d ). It follows that πF L ∞ (µ d ) ≤ 1.
This proves the announced result.

We now prove the first statement of the proposition, assuming first that the function F has the form given in (22). We rewrite the definition of πF as πF

(x) = E t∈Z ǫ∈V d f ǫ,t (x ǫ ).
Proceeding as in the proof of Theorem 4.4, we approximate the integral E t in the uniform norm by a finite average that belongs to M(d). We deduce that πF ∈ M (d). By density and since π is continuous in the L 2 -norm, the same result holds for every F ∈ M (d), completing the proof of the statement. The last statement follows immediately from the previous two. First consider the case that F and G are product of continuous functions. More precisely, assume that

F (x) = ǫ∈V d f ǫ (x ǫ ), G(x) = ǫ∈V d g ǫ (x ǫ ),
where f ǫ and g ǫ belong to C(Z) for every ǫ ∈ V d and

ǫ∈V d f ǫ 2 d ≤ 1 and ǫ∈V d g ǫ 2 d ≤ 1. Then (F.πG)(x) = E t∈Z ǫ∈V d (f ǫ .g ǫ,t )(x ǫ ) = E t∈Z H (t) (x),
where

H (t) (x) := ǫ∈V d (f ǫ .g ǫ,t )(x ǫ ).
Furthermore,

E t∈Z ǫ∈V d f ǫ .g ǫ,t 2 d ≤ ǫ∈V d E t∈Z f ǫ .g ǫ,t 2 d 2 d 1/2 d = ǫ∈V d f ǫ 2 d g ǫ 2 d ≤ 1.
We now proceed as in the end of the proof of Theorem 4.4. For every δ > 0, choose an integer n ≥ 1, a finite subset {t 1 , . . . , t n } of Z, and non-negative λ 1 , . . . , λ n with n j=1 λ j = 1 such that

(F • πG)(x) - n j=1 λ j H (t j ) (x) = (E t∈Z H (t) (x) - n j=1 λ j H (t j ) (x) < δ for every x ∈ Z d and n j=1 λ j ǫ∈V d f ǫ • g ǫ,t j 2 d < δ + E t∈Z ǫ∈V d f ǫ • g ǫ,t 2 d ≤ 1 + δ.
This last bound implies that the function sum n j=1 λ j H (t j ) belongs to (1 + δ)M(d) and by the preceding bound, we have that the function

(F • πG) ∈ M (d).
The same results holds when F and G belong to M c (d). Assume now that F and G belong to M (d). By the first part of Lemma 4.9, there exist sequences

(F n ) and (G n ) in M c (d) with F n → F and G n → G in L 2 (µ d ).
By the second part of Proposition 4.11, πG n L ∞ (µ d ) ≤ 1 for every n and πG L ∞ (µ d ) ≤ 1.

Since

F n → F in L 2 (µ d ), we have that (F n -F ) • πG → 0 in L 2 (µ d ). Since πG n -πG → 0 in L 2 (µ d )
, by passing to a subsequence we can assume that πG n -πG → 0 µ d -almost everywhere. For every n ∈ N, we have that |F (πG n -πG)| 2 ≤ 4|F | 2 and thus by the Lebesgue Dominated Convergence Theorem,

F (πG n -πG) L 2 (µ d ) → 0. Finally, F n • πG n converges to F • πG in L 2 (µ d ) and F • πG ∈ M (d)
, completing the proof of Theorem 4.12.

5.

A result of finite approximation 5.1. A decomposition theorem. For a probability space (X, µ), we assume throughout that it belongs to one of the two following classes:

• µ is nonatomic. We refer to this case as the infinite case.

• X is finite and µ is the uniform probability measure on X. We refer to this case as the finite case.

This is not a restrictive assumption: Haar measure on a compact abelian group always falls into one of these two categories.

As usual, all subsets or partitions of X are implicitly assumed to be measurable. Definition 5.1. Let m ≥ 2 be an integer and let (X 1 , . . . , X m ) be a partition of the probability space (X, µ). The partition is almost uniform if:

• In the infinite case, µ(X i ) = 1/m for every i. • In the finite case, |X i | = ⌊|X|/m⌋ or ⌈|X|/m⌉ for every i.

The main result of this paper is: Theorem 5.2. Let d ≥ 1 be an integer and let δ > 0. There exists an integer M = M(d, δ) ≥ 2 and a constant C = C(d, δ) > 0 such that the following holds: if f ǫ , ǫ ∈ V d+1 , are 2 d+1 -1 functions belonging to

L 2 d (µ) with f ǫ L 2 d (µ) ≤ 1 and φ(x) = D d+1 (f ǫ : ǫ ∈ V d+1 )(x),
then for every δ > 0 there exist an almost uniform partition (X 1 , . . . , X m ) of Z with m ≤ M sets, a nonnegative function ρ on Z, and for 1 ≤ i ≤ m and every t ∈ Z, a function φ

(t) i on Z such that (i) ρ L 2 (µ) ≤ δ; (ii) φ (t) i ∞ ≤ 1 and φ (t) i A(d) ≤ C for every i and every t; (iii) φ(x + t) - m i=1 1 X i (x)φ (t) i (x) ≤ ρ(x) for all x, t ∈ Z.
Combining this theorem with an approximation result, this leads to a deeper understanding of properties of the dual norm. Remark 5.5. Theorem 5.2 holds for d = 1, keeping in mind that A(1) consists of constant functions and that • A(1) is the absolute value. In this case, the results can be proven directly and we sketch this approach. In Section 4.2, we showed that the Fourier coefficients of the function φ satisfy

ξ∈ Z | φ(ξ)| 2/3 ≤ 1.
Let ψ be the trigonometric polynomial obtained by removing the Fourier coefficients in φ that are less than δ 3 . The error term satisfies φψ ∞ ≤ δ and so the function ρ in the theorem can be taken to be the constant δ. There are at most 1/δ 2 characters ξ such that ψ(ξ) = 0. Taking a finite partition such that each of these characters is essentially constant on each set in the partition, we have that for every t, the function φ t is essentially constant on each piece of the partition.

A counterexample. The function φ belongs to A(d+1), with φ A(d+1) ≤ 1. But Theorem 5.2 can not be extended to all functions belonging to A(d + 1), even for d = 1. Meaning, the conclusion of the theorem does not remain valid for the family of functions belonging to the unit ball A(2). We explain this point further.

Assume instead that the conclusion remains valid for functions in the unit ball A(2). Take Z = T, δ = 1/10, let M = M(1, δ) be associated to δ as in the statement, and let θ = 1/2M. Define φ to be the triangular function over the base [-θ, θ]:

φ(x) =    1 - |x| θ if |x| < θ; 0 otherwise.
Then the Fourier coefficients of φ are non-negative and

φ A(2) = n∈Z φ(n) = φ(0) = 1. Let m ≤ M, (X i : 1 ≤ i ≤ M), φ (t)
i and ρ be associated to φ and δ as in the statement. Recalling that A(1) consists only of constant functions and using part (iii), we have that for every

1 ≤ i ≤ m and x, x ′ ∈ X i , |φ(x + t) -φ(x ′ + t)| ≤ ρ(x) + ρ(x ′ ) for every t ∈ T.
Taking t = -x and using the definition of φ, it follows that for all

x, x ′ ∈ X i with |x -x ′ | ≥ θ, the sum ρ(x) + ρ(x ′ ) ≥ 1. Therefore, defining F i = {x ∈ X i : ρ(x) < 1/2}, for all x, x ′ ∈ F i , |x -x ′ | < θ.
This implies that F i is included in an interval of length θ, and we conclude that

µ({x ∈ T : ρ(x) ≥ 1/2}) ≥ m(1/m -θ) ≥ 1 -Mθ = 1/2.
This contradicts ρ 2 ≤ δ = 1/10. Remark 5.6. On the other hand, for A(2), we have a weaker form of the Theorem 5.2. Maintaining the same notation, for φ A(2) ≤ 1, part (iii) of the conclusion becomes that for every t, the left hand side of the equation has L 2 (µ) norm bounded by δ.

Before turning to the proof of Theorem 5.2, we need some definitions, notation, and further results. Throughout the remainder of this section, we assume that an integer d ≥ 1 is fixed, and the dependence of all constants on d is implicit in all statements. For notational convenience, we study functions belonging to A(d + 1) instead of A(d). Let ν be a measure on Z D such that each of its projections on Z is equal to µ.

Let P be a partition of Z. An atom of the product partition P × . . . × P (D times) of Z D is called a rectangle of P.

A P-function on Z D is a function f that is constant on each rectangle of P.

For a function F on Z D , we define F P to be the P-function obtained by averaging over each rectangle with respect to the measure ν: for every x ∈ Z D , if R is the rectangle containing x, then

F P (x) =    1 ν(R) F dν if ν(R) = 0; 0 if ν(R) = 0.
An m-step function is a P-function for some partition P into at most m sets.

As with d, we assume that the integer D is fixed throughout and omit the explicit dependencies of the statements and constants on D.

We make use of the following version of the Regularity Lemma, a modification of the analytic version of Szemerédi's Regularity Lemma in [START_REF] Lovász | Szemerédi's lemma for the analyst[END_REF]: We defer the proof to Appendix A. In the remainder of this section, we carry out the proof of Theorem 5.2.

5.

3. An approximation result for decomposable functions. We return to our usual definitions and notation. We fix d ≥ 1 and apply the Regularity Lemma to the probability space (Z, µ), D = 2 d and the probability measure µ d on Z 2 d .

In this section, we show an approximation result that allows to pass from weak to strong approximations:

F -F P L 2 (µ d ) ≤ (Cθ c + θ) 1/2 .
We first prove a result that allows us to pass from sets to functions: By possibly changing the constant C, we can further assume that the functions f ǫ are all non-negative. For ǫ ∈ {0, 1} d , set

f ′ ǫ (x) = min f ǫ (x), η and f ′′ ǫ (x) = f ǫ -f ′ ǫ (x).
Thus the average of (24) can be written as a sum of 2 d averages, which we deal with separately. a) We first show that (26)

E x∈Z d (F -F P )(x) ǫ∈V d f ′ ǫ (x ǫ ) ≤ η 2 d θ.
For u ∈ R + , write A( ǫ, u) = {x ∈ Z : f ǫ (x) ≤ u}.

For each ǫ ∈ {0, 1} d , we have that b) Assume now that for each ǫ ∈ {0, 1} d , the function g ǫ is equal either to f ′ ǫ or to f ′′ ǫ , and that there exists α ∈ {0, 1} d with g α = f ′′ ǫ . We show that E x∈Z d (F -F P )(x)

f ′ ǫ (x) =
ǫ∈V d g ǫ (x ǫ ) ≤ 2η -2 d +1 .
Since |F -F P | ≤ 2 and the functions g ǫ are nonnegative, it suffices to show that

E x∈Z d ǫ∈{0,1} d g ǫ (x ǫ ) ≤ η -2 d +1 .
By Corollary 2.5, the left hand side is bounded by

ǫ∈V d ǫ = α g ǫ 2 d-1 • g α 1 ≤ g α 1 = 1 f α >η (x)f α (x) ≤ f α 2 d µ{x ∈ Z : f α (x) ≥ η} (2 d -1)/2 d ≤ η -2 d +1 ,
and we have the statement.

c) The left hand side of ( 24) is thus bounded by

η 2 d θ + 2(2 d -1)η -2 d +1 .
Taking η = θ -1/(2 d+1 -1) , we obtain the bound (24).

We now use this to prove the proposition:

Proof of Proposition 5. For x ∈ Z d , define

G(x) = ǫ∈ V d f ǫ0 (x) = ǫ∈ V d f ǫ0 (x ǫ )
and

F (x) = π ǫ∈V d f ǫ1 (x) = E u∈Z ǫ∈V d f ǫ1 (x ǫ + u).
For x ∈ Z, we have

φ(x) = E s∈Z d ǫ∈ V d f ǫ0 (x + ǫ • s) E u∈Z ǫ∈V d f ǫ1 (x + ǫ • s + u) = P(G • F ).
Recall that for t ∈ Z, φ t is the function on Z defined by φ t (x) = φ(x + t).

For t ∈ Z and x ∈ Z d , define

G t ∆ (x) = G(x + t ∆ ) = ǫ∈ V d f ǫ0 (x ǫ + t).
Since the function F is invariant under diagonal translations, for x, t ∈ Z we have that Let δ > 0. Let c and C be as in Proposition 5.9 and let θ > 0 be such that (Cθ c + θ) 1/2 < δ. Let P and F P be associated to F and θ as in the Regularity Lemma. Let P = (A 1 , . . . , A m ).

φ t (x) = P(G t ∆ • F )(x).
For x, t ∈ Z, we have that φ t (x) = P(G t ∆ • (F -F P )) + P(G t ∆ • F P )

and we study the two parts of this sum separately.

b) Bounding the rest. Define ρ(x) = P(F -F P ) 2 1/2 .

We have that ρ 2 = P(F -F P ) 2 1/2 L 1 (µ d ) ≤ (F -F P ) 2 1/2 L 1 (µ d ) = F -F P L 2 (µ d ) ≤ δ, where the last inequality follows from Proposition 5.9.

Moreover,

P(G t ∆ • (F -F P )) ≤ P(G 2 t ∆ ) 1/2 • P(F -F P ) 2 1/2 ≤ ρ(x)
by ( 27) and Lemma 2.3.

c) The main term. We write elements of {1, . . . , m} 2 d as j = (j ǫ : ǫ ∈ V d ).

For j = (j ǫ : ǫ ∈ V d ) ∈ {1, . . . , m} 2 d , write

R j = ǫ∈V d A j ǫ .
The function F P is equal to a constant on each rectangle R j . Let c j denote this constant. We have that |c j | ≤ 1.

For 1 ≤ i ≤ m and t, x ∈ Z, define φ and derive a contradiction (the other bound is proved similarly).

Define a new function U ′′ on Z D . Set U ′′ = 0 = U ′ outside G D . Let R be a product of good sets. The functions F * and F P are constant on R and thus the function F * -F P is constant on R. Define U ′′ on R to be equal to 1 if this constant is positive and to be -1 if this constant is negative. Then U ′′ (F * -F P ) ≥ U ′ (F -F P ) on R and so U ′′ (F * -F P ) dν ≥ U ′ (F * -F P ) dν > ε.

On the other hand, U ′′ is a P-function and so by definition of F P , U ′′ (F -F P ) dν = 0 and

U ′′ (F * -F ) dν > ε.
But U ′′ is an m-step function with |U ′′ | ≤ 1 and by (29) this integral is < ε, leading to a contradiction.

Proof.

  First assume the Dual Form. Given φ with φ ∞ ≤ 1, we have that φ U (d) ≤ 1 and thus D d φ * U (d) ≤ 1. By the Dual Form, D d φ = h + ψ, where h ∈ F ′ (d, δ) and ψ 1 ≤ δ, which is exactly the Reformulated Version. Conversely, assume the Reformulated Version. Let g ∈ B U (d) * (1), where B U (d) * (1) denotes the ball of radius 1 in anti-uniform norm of level d. Then by Theorem 3.8, g = D d h + ψ, where h ∞ ≤ 2/δ and

Proposition 4 . 3 .Theorem 4 . 4 .

 4344 The space A(2) coincides with the Fourier algebra A(Z) of Z:A(Z) := g ∈ C(Z) : ξ∈ Z | g(ξ)| < +∞ and, for g ∈ A(Z), g A(2) = g A(Z), which is equal by definition to the sum of the series.4.3. A(d) is an algebra of functions. The Banach space A(d) is invariant under pointwise multiplication and • A(d) is an algebra norm, meaning that for all g, g ′ ∈ A(d),

4. 5 .

 5 Decomposable functions on Z d . Recall that Z d is the subgroup of Z 2 d defined in (2) and µ d is its Haar measure. Elements x ∈ Z d are written as x = (x ǫ : ǫ ∈ V d ). Definition 4.8. Let M(d) be the convex hull of the family of functions on Z d that can be written as (21)

  If Z is a finite group, then every function on Z d belongs to D(d) and M (d) = M(d).

Theorem 4 . 12 .

 412 For F ∈ D(d) and G ∈ D(d) ∩ I(d), we have that F G belongs to D(d) and that F G D(d) ≤ F D(d) G D(d) . In particular, D(d)∩I(d), endowed with pointwise multiplication and the norm • B(d) , is a Banach algebra. Proof. Since πG = G when G ∈ D(d) ∩ I(d), it suffices to show that for all F, G ∈ D(d), we have F.π(G) ∈ D(d) and (23) F.πG D(d) ≤ F D(d) G D(d) .

Remark 5 . 3 .

 53 In fact we show a bit more: each function φ(t)i is the sum of a bounded number of functions that are cubic convolution products of functions whose L 2 d-1 (µ) norms are bounded by 1.Remark 5.4. The function φ in the statement of Theorem 5.2 satisfies |φ| ≤ 1 and thus 0 ≤ ρ ≤ 2.

5. 2 .

 2 Regularity Lemma. Definition 5.7. Fix an integer D ≥ 2. Let (Z, µ) be a probability space of one of the two types considered in Definition 5.1.

Theorem 5 . 8 (

 58 Regularity Lemma, revisited). For every D and δ > 0, there exists M = M(D, δ) such that if (X, µ) and ν are as in Definition 5.7, then for every function F on Z D with |F | ≤ 1, there is an almost uniform partition P of Z into m ≤ M sets such that for every m-step function U on Z D with |U| ≤ 1, U(F -F P ) dν ≤ δ .

Proposition 5 . 9 .

 59 Let F be a function on Z d belonging to D(d) with F D(d) ≤ 1 and F L ∞ (µ d ) ≤ 1. Let θ > 0 and P be the partition of Z associated to F and θ by the Regularity Lemma (Theorem 5.8). Then there exist constants C = C(d) > 0 and c = c(d) > 0 such that

Lemma 5 . 10 .

 510 Assume that F is a function on Z d with F L ∞ (µ d ) ≤ 1. Let θ > 0 and let P be the partition of Z associated to F and θ by the Regularity Lemma (Theorem 5.8). If f ǫ , ǫ ∈ V d , are functions on Z satisfying f ǫ 2 d ≤ 1 for every ǫ, then(24) E x∈Z d (F -F P )(x)ǫ∈V d f ǫ (x ǫ ) ≤ Cθ c , where c = c(d) and C = C(d) are positive constants. In other words, writing • * D(d) for the dual norm of the norm • D(d) , we have that F -F P * D(d) ≤ Cθ c . Proof. Let η > 0 be a parameter, with its value to be determined. By construction, P is an almost uniform partition of Z into m < M(η) pieces and the function F = F P satisfies (25) |E Z d U(F -F P )| ≤ η for every m-step function U on Z d with |U| ≤ 1. We show (24).

η 0 1 A

 1 ( ǫ,u) (x) du and so the average of the left hand side of (26) is the integral overu = (u ǫ : ǫ ∈ V d ) ∈ [0, η] 2 d of E x∈Z d (F -F P )(x) ǫ∈V d 1 A( ǫ,u ǫ ) (x ǫ ).By (25), for each u ∈ [0, η] 2 d , the absolute value of this average is bounded by θ. Integrating, we obtain the bound (26).

9 . 5 . 4 .

 954 Since F belongs to D(d) with F D(d) ≤ 1, it follows from the definition of this norm and from Lemma 5.10 that|E x∈Z d (F -F P )(x)F (x)| ≤ Cθ c .On the other hand, F P is an m-step function and by the property of the partition P given in the Regularity Lemma(Theorem 5.8), we have that|E x∈Z d (F -F P )(x)F P (x)| ≤ θ. Finally, E x∈Z d (F -F P )(x) 2 ≤ Cθ c + θ. Proof of Theorem 5.2.We maintain the notation and hypotheses from the statement of Theorem 5.2. a) A decomposition. Define P : L 1 (µ d ) → L 1 (µ) to be the operator of conditional expectation. The most convenient definition of this operator is by duality: for h ∈ L ∞ (µ) andH ∈ L 1 (µ d ), Z h(x) P H(x) dµ(x) = Z d h(x 0 )H(x) dµ d (x). Recall that P H L 1 (µ d ) ≤ H L 1 (µ d ) .By definition, whenH(x) = ǫ∈V d f ǫ (x ǫ ),where the functions f ǫ belong to L 2 d-1 (µ) , then (27) P H(x) = E t∈Z d ǫ∈V d f ǫ (x + ǫ • t).

By Proposition 4 . 11 ,

 411 the function F ∈ D(d) and F D(d) ≤ 1. Thus F L ∞ (µ d ) ≤ 1.

id j 0 =i c j ǫ∈ V d 1 Ad j 0 =i c j ǫ∈ V d 1 A

 11 (x) := E s∈Z d j∈{1,...,m} 2 j ǫ (x + ǫ • s).φ ǫ0 (x + ǫ • s).Since distinct rectangles are disjoint, it follows that j∈{1,...,m}2 j ǫ (x + ǫ • s).φ ǫ0 (x + ǫ • s) ≤ ǫ∈ V d |φ ǫ0 (x + ǫ • s)|. Thus |φ (t) i (x)| ≤ 1.On the other hand, the function φ (t) iis the sum of m 2 d -1 functions belonging to A(d) with norm ≤ 1 and thusφ (t) i A(d) ≤ C = M 2 d -1 . We claim that (28) P (G t ∆ • F P ) = m i=1 1 A i (x)φ (t) i (x).

From the definitions, we have that

Grouping together all terms of the sum with j 0 = i and using (27), we obtain (28). This completes the proof of Theorem 5.2.

Further directions

We have carried out this study of Gowers norms and associated dual norms in the setting of compact abelian groups. This leads to a natural question: what is the analog of the Inverse Theorem for groups other than Z N ? What would be the generalization for other finite groups or for infinite groups such as the torus, or perhaps even for totally disconnected (compact abelian) groups?

In Section 3.5, we give examples of functions with small dual norm, obtained by embedding in a nilmanifold. One can ask if this process is general: does one obtain all functions with small dual norm, up to a small error in L 1 in this way? In particular, for Z N this would mean that in the Inverse Theorem we can replace the family F (d, δ) by a family of nilsequences with "bounded complexity" that are periodic, with period N, meaning that they all come from embeddings of Z N in a nilmanifold.

By the computations in Section 4.2, we see a difference between A(2) and the dual functions: the cubic convolution product f of functions belonging to

Appendix A. Proof of the regularity lemma

We make use of the following version of the Regularity Lemma in a Hilbert space introduced in [10]:

Lemma A.1 (Lovasz and Szegedy [START_REF] Lovász | Szemerédi's lemma for the analyst[END_REF]). Let K 1 , K 2 , . . . be arbitrary nonempty subsets of a Hilbert space H with inner product •, • and norm • H . Then for every ε > 0 and f ∈ H, there exists k ≤ ⌈1/ε 2 ⌉ and f i ∈ K i , i = 1, . . . , k and γ 1 , . . . , γ k ∈ R such that for every

For the proof of Theorem 5.8, we follow the proof of the strong form of the Regularity Lemma in [START_REF] Lovász | Szemerédi's lemma for the analyst[END_REF].

Proof of Theorem 5.8. We only consider the infinite case, as the proof in the finite case is similar.

Choose a sequence of integers s(1) < s(2) < . . . such that

for each i ∈ N and such that D/ε < s(1).

For every i, let K i consist of s(i)-step functions. By Lemma A.1, there exists k ≤ ⌈1/ε 2 ⌉ and there exists an s(1) . . . s(k)-

and refine the partition defining F * into a partition S = {S 1 , . . . , S m } into m sets. Then F * is an S-function and the bound (29) remains valid for every m-step function U.

Partition each set S i into subsets of measure 1/m 2 and a remainder set of measure less than 1/m 2 . Take the union of all these remainder sets and partition this union into sets of measure 1/m 2 . Thus we obtain a partition P = {A 1 , . . . , A m 2 } of Z into m 2 sets of equal measure.

At least m 2 -m of these m 2 sets are good, meaning that the set is included in some set of the partition S. Let G denote the union of these good sets and call it the good part of Z. We have that

We claim that if U is an m-step function with |U| ≤ 1, then U(F -F P ) dν ≤ 4ε.

To show this, set U

Moreover, U ′ is an m-step function with |U ′ | ≤ 1 and by hypothesis,

Thuswe are reduced to showing that U ′ (F * -F P ) dν ≤ ε.

Instead, we assume that U ′ (F * -F P ) dν > ε