An optimal lower bound for monotonicity testing over hypergrids

For positive integers n, d, consider the hypergrid [n]d with the coordinate-wise product partial ordering denoted by prec. A function f: [n]d mapsto mathbbN is monotone if forall x prec y, f(x) ≤ f(y). A function f is eps-far from monotone if at least an eps-fraction of values must be changed to make f monotone. Given a parameter eps, a monotonicity tester must distinguish with high probability a monotone function from one that is eps-far. We prove that any (adaptive, two-sided) monotonicity tester for functions f:[n]d mapsto mathbbN must make Omega(eps-1dlog n - eps-1log eps-1) queries. Recent upper bounds show the existence of O(eps-1d log n) query monotonicity testers for hypergrids. This closes the question of monotonicity testing for hypergrids over arbitrary ranges. The previous best lower bound for general hypergrids was a non-adaptive bound of Omega(d log n).