  We consider the problem of testing if a given function f : F_2^n -> F_2 is
close to any degree d polynomial in n variables, also known as the Reed-Muller
testing problem. The Gowers norm is based on a natural 2^{d+1}-query test for
this property. Alon et al. [AKKLR05] rediscovered this test and showed that it
accepts every degree d polynomial with probability 1, while it rejects
functions that are Omega(1)-far with probability Omega(1/(d 2^{d})). We give an
asymptotically optimal analysis of this test, and show that it rejects
functions that are (even only) Omega(2^{-d})-far with Omega(1)-probability (so
the rejection probability is a universal constant independent of d and n). This
implies a tight relationship between the (d+1)st Gowers norm of a function and
its maximal correlation with degree d polynomials, when the correlation is
close to 1. Our proof works by induction on n and yields a new analysis of even
the classical Blum-Luby-Rubinfeld [BLR93] linearity test, for the setting of
functions mapping F_2^n to F_2. The optimality follows from a tighter analysis
of counterexamples to the "inverse conjecture for the Gowers norm" constructed
by [GT09,LMS08]. Our result has several implications. First, it shows that the
Gowers norm test is tolerant, in that it also accepts close codewords. Second,
it improves the parameters of an XOR lemma for polynomials given by Viola and
Wigderson [VW07]. Third, it implies a "query hierarchy" result for property
testing of affine-invariant properties. That is, for every function q(n), it
gives an affine-invariant property that is testable with O(q(n))-queries, but
not with o(q(n))-queries, complementing an analogous result of [GKNR09] for
graph properties.
