The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic, well-studied, yet unsolved question in property testing. We are given query access to $f:[k]^n \mapsto \R$
(for some ordered range $\R$).
The hypergrid/cube has a natural partial order given by coordinate-wise ordering, denoted by $\prec$.
A function is \emph{monotone} if for all pairs $x \prec y$,
$f(x) \leq f(y)$. The distance to monotonicity, $\eps_f$, is the minimum fraction of values of $f$
that need to be changed to make $f$ monotone.
For $k=2$ (the boolean hypercube), the usual tester is the \emph{edge tester}, which
checks monotonicity on adjacent pairs of domain points.
It is known that the edge tester using $O(\eps^{-1}n\log|\R|)$
samples can distinguish a monotone function from one where $\eps_f > \eps$.
On the other hand, the best lower bound for monotonicity testing over general $\R$ is $\Omega(n)$.
We resolve this long standing open problem and prove that $O(n/\eps)$ samples suffice
for the edge tester. For hypergrids, existing testers require $O(\eps^{-1}n\log k\log |\R|)$ samples.
We give
a (non-adaptive) monotonicity tester for hypergrids running in $O(\eps^{-1} n\log k)$ time,
recently shown to be optimal.
Our techniques lead to optimal property testers (with the same running time) for the natural \emph{Lipschitz property}
on hypercubes and hypergrids. (A $c$-Lipschitz function
is one where $|f(x) - f(y)| \leq c\|x-y\|_1$.)
In fact, we give a general unified proof for $O(\eps^{-1}n\log k)$-query testers for a class of ``bounded-derivative" properties that contains both monotonicity and Lipschitz.

Better presentation and notation; much cleaner proofs;

The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic, well-studied, yet unsolved question in property testing. We are given query access to $f:[k]^n \mapsto R$
(for some ordered range $R$). The hypergrid/cube has a natural partial order given by coordinate-wise ordering, denoted by $\prec$. A function is \emph{monotone} if for all pairs $x \prec y$, $f(x) \leq f(y)$. The distance to monotonicity, $\varepsilon_f$, is the minimum fraction of values of $f$
that need to be changed to make $f$ monotone.

For $k=2$ (the boolean hypercube), the usual tester is the \emph{edge tester}, which
checks monotonicity on adjacent pairs of domain points.
It is known that the edge tester using $O(\varepsilon^{-1}n\log|R|)$
samples can distinguish a monotone function from one where $\varepsilon_f > \varepsilon$.
On the other hand, the best lower bound for monotonicity testing over the hypercube is $\min(|R|^2,n)$.
This leaves
a quadratic gap in our knowledge, since $|R|$ can be $2^n$.
We resolve this long standing open problem and prove that $O(n/\varepsilon)$ samples suffice
for the edge tester. For hypergrids, known testers require $O(\varepsilon^{-1}n\log k\log |R|)$ samples, while
the best known (non-adaptive) lower bound is $\Omega(\varepsilon^{-1} n\log k)$. We give
a (non-adaptive) monotonicity tester for hypergrids running in $O(\varepsilon^{-1} n\log k)$ time.

Our techniques lead to optimal property testers (with the same running time) for the natural \emph{Lipschitz property}
on hypercubes and hypergrids. (A $c$-Lipschitz function
is one where $|f(x) - f(y)| \leq c\|x-y\|_1$.)
In fact, we give a general unified proof for $O(\varepsilon^{-1}n\log k)$-query testers for a class of ``bounded-derivative" properties,
a class containing both monotonicity and Lipschitz.

New results on hypergrids

The problem of monotonicity testing of the boolean hypercube is a classic well-studied, yet unsolved
question in property testing. We are given query access to $f:\{0,1\}^n \mapsto R$
(for some ordered range $R$). The boolean hypercube ${\cal B}^n$ has a natural partial order, denoted by $\prec$ (defined by the product of
coordinate-wise ordering). A function is \emph{monotone} if all pairs $x \prec y$ in ${\cal B}^n$,
$f(x) \leq f(y)$. The distance to monotonicity, $\varepsilon_f$, is the minimum fraction of values of $f$
that need to be changed to make $f$ monotone. It is known that the edge tester
using $O(n\log |R|/\varepsilon)$ samples can distinguish a monotone function from one where $\varepsilon_f > \varepsilon$.
On the other hand, the best lower bound for monotonicity testing is $\min(|R|^2,n)$. This leaves
a quadratic gap in our knowledge, since $|R|$ can be $2^n$.

We prove that the edge tester only requires $O(n/\varepsilon)$ samples (regardless of $R$), resolving this question.
Our technique is quite general, and we get optimal edge testers for the Lipschitz property.
We prove a very general theorem showing that edge testers work for a class of ``bounded-derivative"
properties, which contains both monotonicity and Lipschitz.