We consider the problem of testing if a given function f: F2n → F2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al. [AKKLR] proposed and analyzed a natural 2d+1-query test for this property and showed that it accepts every degree d polynomial with probability 1, while rejecting functions that are Ω(1)-far with probability Ω(1/(d 2d)). We give an asymptotically optimal analysis of their test showing that it rejects functions that are (even only) Ω(2d)-far with Ω(1)-probability (so the rejection probability is a universal constant independent of d and n).
Our proof works by induction on n, and yields a new analysis of even the classical Blum-Luby-Rubinfeld [BLR] linearity test, for the setting of functions mapping F2n to F2. The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by [GT,LMS].
Our result gives a new relationship between the (d+1)st-Gowers norm of a function and its maximal correlation with degree d polynomials. For functions highly correlated with degree d polynomials, this relationship is asymptotically optimal. Our improved analysis of the AKKLR-test also improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson [VW]. Finally, the optimality of our result also implies a ``query-hierarchy'' result for property testing of linear-invariant properties: For every function q(n), it gives a linear-invariant property that is testable with O(q(n))-queries, but not with o(q(n))-queries, complementing an analogous result of [GKNR08] for graph properties.