Gowers uniformity norms

For each binary vertex omega of an s-dimensional cube, evaluate f at the base point plus the sum of those increments selected by omega. Conjugate the value at vertices with odd coordinate sum and leave even vertices unconjugated. Average the product over all choices of base point and increments. This quantity is nonnegative and its appropriate root defines U to the s. Zero increments and coinciding vertices are included. Removing degenerate cubes would define a different statistic and would break these exact identities.

For s=1 the expression reduces to the squared magnitude of the mean, so U¹ is a seminorm and can vanish on a nonzero mean-zero function. For s at least two, the finite-group construction gives a genuine norm. Repeated Cauchy–Schwarz supplies the triangle inequality and monotonicity with s. Defining a multiplicative derivative as f(x) times the conjugate of f(x+h) gives a recursion: the next cube average is the mean of the current cube averages of these derivatives. This recursion is a useful way to audit conjugation signs.

Expand a two-dimensional cube using character inversion. Averaging over the base point and both increments forces the four frequencies to match in the conjugated pairing, leaving the sum of fourth powers of coefficient magnitudes. Thus small U² excludes a large individual Fourier coefficient. Conversely, for a bounded function Parseval controls the total squared coefficient mass, so a large U² forces some coefficient to be large. This is the inverse principle at linear order, where ordinary Fourier analysis is complete.

For an indicator, U² to the fourth power equals counting energy divided by the cube of the ambient size. For its balanced function, the trivial-frequency contribution is removed, leaving energy divided by that cube minus the fourth power of density. One must choose which function is being tested: a positive-density indicator always has its constant contribution, while pseudorandomness around that density concerns its balanced fluctuation. This distinction is especially important when using a small norm to estimate pattern-counting errors.

Over a prime field, a polynomial phase has the form exp(2πiP(x)/p). The alternating cube product is the exponential of an iterated finite difference of P, with a sign depending on the derivative convention. An s-fold difference of a polynomial of degree less than s vanishes, so such a unit-modulus phase has U to the s equal to one. In particular, a quadratic phase is perfectly visible to U³ even when its ordinary linear coefficients are individually small.

This direction does not state the full higher-order inverse theorem. In suitable high-characteristic finite-field settings, large uniformity norm is related to correlation with polynomial phases of controlled degree, but low characteristic requires more elaborate notions, and cyclic-group inverse theorems use additional objects. We use only exact phase cancellation and the elementary U² inverse argument here. Calling every function with a large U³ a single classical quadratic phase would be false. A norm detects an obstruction; identifying the entire structured component is a separate theorem.