Gowers norm

In mathematics, in the field of additive combinatorics, a Gowers norm or uniformity norm is a class of norms on functions on a finite group or group-like object which quantify the amount of structure present, or conversely, the amount of randomness. They are used in the study of arithmetic progressions in the group. They are named after Timothy Gowers, who introduced it in his work on Szemerédi's theorem.

Definition

Let

f

{\displaystyle f}

be a complex-valued function on a finite abelian group

G

{\displaystyle G}

and let

J

{\displaystyle J}

denote complex conjugation. The Gowers

d

{\displaystyle d}

-norm is

‖

f

‖

U

d

(

G

)

2

d

=

∑

x

,

h

1

,

…

,

h

d

∈

G

∏

ω

1

,

…

,

ω

d

∈

{

0

,

1

}

J

ω

1

+

⋯

+

ω

d

f

(

x

+

h

1

ω

1

+

⋯

+

h

d

ω

d

)

.

{\displaystyle \Vert f\Vert _{U^{d}(G)}^{2^{d}}=\sum _{x,h_{1},\ldots ,h_{d}\in G}\prod _{\omega _{1},\ldots ,\omega _{d}\in \{0,1\}}J^{\omega _{1}+\cdots +\omega _{d}}f\left({x+h_{1}\omega _{1}+\cdots +h_{d}\omega _{d}}\right)\ .}

Gowers norms are also defined for complex-valued functions f on a segment

[

N

]

=

0

,

1

,

2

,

.

.

.

,

N

−

1

{\displaystyle [N]={0,1,2,...,N-1}}

, where N is a positive integer. In this context, the uniformity norm is given as

‖

f

‖

U

d

[

N

]

=

‖

f

~

‖

U

d

(

Z

/

N

~

Z

)

/

‖

1

[

N

]

‖

U

d

(

Z

/

N

~

Z

)

{\displaystyle \Vert f\Vert _{U^{d}[N]}=\Vert {\tilde {f}}\Vert _{U^{d}(\mathbb {Z} /{\tilde {N}}\mathbb {Z} )}/\Vert 1_{[N]}\Vert _{U^{d}(\mathbb {Z} /{\tilde {N}}\mathbb {Z} )}}

, where

N

~

{\displaystyle {\tilde {N}}}

is a large integer,

1

[

N

]

{\displaystyle 1_{[N]}}

denotes the indicator function of [N], and

f

~

(

x

)

{\displaystyle {\tilde {f}}(x)}

is equal to

f

(

x

)

{\displaystyle f(x)}

for

x

∈

[

N

]

{\displaystyle x\in [N]}

and

0

{\displaystyle 0}

for all other

x

{\displaystyle x}

.