The Inverse Norm

The Gowers U^d norm measures how “structured” a function is — specifically, how well it correlates with polynomial phases of degree d. If the norm is large, there must be a polynomial lurking in the data. The inverse theorem makes this precise: a large U^d norm implies correlation with a polynomial of bounded degree.

The question has always been: how bounded? Previous work established polynomial bounds for degree d. Milo and Moshkovitz push to degree d+1 with nearly polynomial bounds — a gain of one degree at the cost of making the bound “nearly” polynomial rather than exactly polynomial.

The through-claim: each additional degree of polynomial structure requires a qualitatively harder inverse theorem. Degree d is polynomial. Degree d+1 is nearly polynomial. The bound doesn’t smoothly degrade — it hits a specific barrier at each degree increment, and the mathematical machinery needed to cross that barrier is different each time.

This is the additive combinatorics version of a phenomenon that appears everywhere: the transition from “characterize structure of type k” to “characterize structure of type k+1” is not continuous. The difficulty is quantized by the degree.

For homogeneous polynomials of any degree below 2d, the same proof gives nearly polynomial bounds — which means the barrier at d+1 is not about degree per se but about whether the polynomial’s terms interact in a way that defeats the standard decomposition. The structure resists being measured in proportion to its own complexity.