For positive integers nd , consider the hypergrid [n]d with the coordinate-wise product partial ordering denoted by . A function f:[n]dN is monotone if xy, f(x)f(y).A function f is -far from monotone if at least an -fraction of values must be changed to makef monotone. Given a parameter , a \emph{monotonicity tester} must distinguish with high probability a monotone function from one that is -far.

We prove that any (adaptive, two-sided) monotonicity tester for functions f:[n]dN must make(−1dlogn−−1log−1) queries. Recent upper bounds show the existence of O(−1dlogn)query monotonicity testers for hypergrids. This closes the question of monotonicity testing for hypergridsover arbitrary ranges. The previous best lower bound for general hypergrids was a non-adaptive boundof (dlogn).