\section{Introduction} \label{sec:intro}

Given query access to a function $f: {\mathbf D} \mapsto {\mathbf R}$, the field of \emph{property testing}~\cite{RS96,GGR98} deals
with the problem of determining properties of $f$ without reading all of it.
Monotonicity testing~\cite{GGLRS00} is a classic problem in property testing. Consider a function $f: {\mathbf D} \mapsto {\mathbf R}$,
where ${\mathbf D}$ is some partial order given by ``$\prec$", and ${\mathbf R}$ is a total order. The function $f$ is monotone
if for all $x \prec y$ (in ${\mathbf D}$), $f(x) \leq f(y)$. The \emph{distance to monotonicity} of $f$ is the minimum
fraction of values that need to be modified to make $f$ monotone. More precisely, define the distance between functions
$d(f,g)$ as $|\{x: f(x) \neq g(x)\}|/|{\mathbf D}|$. Let ${\cal M}$ be the set of all monotone functions.
Then the distance to monotonicity of $f$ is $\min_{g \in {\cal M}} d(f,g)$.

A function is called $\varepsilon$-far from monotone if the distance to monotonicity is at least $\varepsilon$.
A \emph{property tester for monotonicity} is a, possibly randomized, algorithm that takes as input a distance parameter $\varepsilon \in (0,1)$, error parameter $\delta \in [0,1]$, 
and query access to an arbitrary $f$. If $f$ is monotone, then the tester must accept with probability $>1-\delta$.
If it is $\varepsilon$-far from monotone, then the tester rejects with probability $>1-\delta$. (If neither, then the tester
is allowed to do anything.) The aim is to design a property tester using as few queries as possible.
A tester is called \emph{one-sided} if it always accepts a monotone function. A tester is called \emph{non-adaptive}
if the queries made do not depend on the function values. The most general tester is an adaptive two-sided tester.

Monotonicity testing has a rich history and the hypergrid domain, $[n]^d$, has received special attention.
The boolean hypercube ($n=2$) and the total order ($d=1$) are special instances of hypergrids.
Following a long line of work~\cite{EKK+00, GGLRS00,DGLRRS99,LR01,FLNRRS02,AC04,E04,HK04,PRR04,ACCL04,BRW05,BBM11}, 
previous work of the authors~\cite{ChSe13} shows the existence of $O(\varepsilon^{-1} d\log n)$-query
monotonicity testers. Our result is a matching adaptive lower bound that is optimal in all parameters
(for unbounded range functions).
This closes the
question of monotonicity testing for unbounded ranges on hypergrids.
This is also the first adaptive bound for monotonicity testing on general hypergrids.

\begin{theorem} \label{thm:main}
Any (adaptive, two-sided) monotonicity tester for functions $f:[n]^d \mapsto \mathbb{N}$ requires $\Omega(\varepsilon^{-1} d\log n - \varepsilon^{-1}\log \varepsilon^{-1})$ queries.
\end{theorem}

\subsection{Previous work} \label{sec:prev}

The problem of monotonicity testing was introduced by Goldreich et al~\cite{GGLRS00}, with an $O(n/\varepsilon)$
tester for functions $f:\{0,1\}^n \mapsto \{0,1\}$. The first tester for general hypergrids was given
by Dodis et al~\cite{DGLRRS99}. The upper bound of $O(\varepsilon^{-1} d\log n)$ for monotonicity testing was recently proven
in~\cite{ChSe13}. We refer the interested reader to the introduction of~\cite{ChSe13} for a more detailed history of previous upper bounds.

There have been numerous lower bounds for monotonicity testing. We begin by summarizing the state of the art.
The known adaptive lower bounds are $\Omega(\log n)$ for the total order $[n]$ by Fischer~\cite{E04},
and $\Omega(d/\varepsilon)$ for the boolean hypercube $\{0,1\}^d$ by Brody~\cite{Br13}. For general hypergrids,
Blais, Raskhodnikova, and Yaroslavtsev~\cite{BlJh+12} recently proved the first result, a non-adaptive lower bound of $\Omega(d\log n)$.
\Thm{main} is the first adaptive bound for monotonicity testing on hypergrids and is optimal (for arbitrary ranges) in all parameters.

Now for the chronological documentation. The first lower bound was the non-adaptive bound of $\Omega(\log n)$ for the total order $[n]$ by Ergun et al~\cite{EKK+00}.
This was extended by Fischer~\cite{E04} to an (optimal) adaptive bound. For the hypercube domain $\{0,1\}^d$,
Fischer et al~\cite{FLNRRS02} proved the first non-adaptive lower bound of $\Omega(\sqrt{d})$. (This was proven
even for the range $\{0,1\}$.) This was improved to $\Omega(d/\varepsilon)$ by Br\"{i}et et al~\cite{BCG+10}.
Blais, Brody, and Matulef~\cite{BBM11} gave an ingenious reduction from communication complexity
to prove an adaptive, two-sided bound of $\Omega(d)$. (Honing this reduction, Brody~\cite{Br13} improved this bound to $\Omega(d/\varepsilon)$.)
The non-adaptive lower bounds of Blais, Raskhodnikova, and Yaroslavtsev~\cite{BlJh+12} were also achieved
through communication complexity reductions.

We note that our theorem only holds when the range is $\mathbb{N}$, while some previous results hold for restricted
ranges. The results of~\cite{BBM11, Br13} provide lower bounds for range $[\sqrt{d}]$.
The non-adaptive bound of~\cite{BlJh+12} holds even when the range is $[nd]$. In that sense,
the communication complexity reductions provide stronger lower bounds than our result.

\subsection{Main ideas} \label{sec:ideas}

The starting point of this work is the result of Fischer~\cite{E04}, an adaptive lower bound for monotonicity
testing for functions $f:[n] \mapsto \mathbb{N}$. He shows that adaptive testers can be converted to comparison-based
testers, using Ramsey theory arguments. A comparison-based tester for $[n]$ can be easily converted to a non-adaptive
tester, for which an $\Omega(\log n)$ bound was previously known. We make a fairly simple observation. The main part of Fischer's proof
actually goes through for functions over \emph{any partial order}, so it suffices to prove lower bounds
for comparison-based testers. (The reduction to non-adaptive testers only holds for $[n]$.)

We then prove a comparison-based lower bound of $\Omega(\varepsilon^{-1} d\log n - \varepsilon^{-1}\log \varepsilon^{-1})$
for the domain $[n]^d$. 
As usual, Yao's minimax lemma allows us to prove determinstic lower bounds over some distribution of functions.
The major challenge in proving (even non-adaptive) lower bounds for monotonicity is that the tester might make decisions
based on the actual values that it sees. Great care is required to construct a distribution over functions
whose monotonicity status cannot be decided by simply looking at the values.
But a comparison-based tester has no such power, and
optimal lower bounds over all parameters can be obtained with a fairly clean distribution.

\section{The reduction to comparison based testers} \label{sec:prelim}

Consider the family of functions $f: {\mathbf D} \mapsto {\mathbf R}$, where ${\mathbf D}$ is some partial order, and ${\mathbf R}\subseteq \mathbb{N}$.
We will assume that $f$ always takes distinct values, so $\forall x,y, f(x) \neq f(y)$. Since we are proving
lower bounds, this is no loss of generality.

\begin{definition} \label{def:tester}
An algorithm ${\cal A}$ is a \emph{$(t,\varepsilon,\delta)$-monotonicity tester}
if ${\cal A}$ has the following properties. For any $f:{\mathbf D}\mapsto {\mathbf R}$, the algorithm ${\cal A}$ makes $t$ (possibly randomized) queries to $f$
and then outputs either ``accept" or ``reject". If $f$ is monotone, then ${\cal A}$ accepts with probability $>1-\delta$.
If $f$ is $\varepsilon$-far from monotone, then ${\cal A}$ rejects with probability $>1-\delta$.
\end{definition}
\def{\tt acc}{{\tt acc}}
\def{\tt rej}{{\tt rej}}
\def{\mathbf x}{{\mathbf x}}
\def{\mathbf a}{{\mathbf a}}

Given a positive integer $s$, let ${\mathbf D}^s$ denote the collection of {\em ordered}, $s$-tupled vectors with each entry in ${\mathbf D}$.
We define two symbols {\tt acc}~ and {\tt rej}, and denote ${\mathbf D}' = {\mathbf D} \cup \{{\tt acc}, {\tt rej}\}$.
Any $(t,\varepsilon,\delta)$-tester can be completely specified by the following family of functions.
For all $s\leq t$, ${\mathbf x}\in {\mathbf D}^s$, $y\in {\mathbf D}'$, we consider a function $p^y_{\mathbf x}:{\mathbf R}^s \mapsto [0,1]$, with the semantic that for any ${\mathbf a}\in {\mathbf R}^s$, $p^y_{\mathbf x}({\mathbf a})$ denotes the probability the tester queries $y$ as the $(s+1)$th query, given that the 
first $s$ queries are ${\mathbf x}_1,\ldots,{\mathbf x}_s$ and $f({\mathbf x}_i) = {\mathbf a}_i$ for $1\leq i\leq s$. By querying ${\tt acc},{\tt rej}$ we imply returning accept or reject. These functions satisfy the following properties.

\begin{align}
& \forall s \leq t,~ \forall{\mathbf x}\in {\mathbf D}^s,~ \forall {\mathbf a} \in {\mathbf R}^s,~ \sum_{y \in {\mathbf D}'} p^y_{\mathbf x}({\mathbf a}) = 1 \label{eqn:dist}\\
& \forall {\mathbf x}\in {\mathbf D}^t,~ \forall y \in {\mathbf D},~ \forall {\mathbf a} \in {\mathbf R}^t,~ p^y_{\mathbf x}({\mathbf a}) = 0 \label{eqn:time}
\end{align}
\Eqn{dist} ensures the decisions of the tester at step $(s+1)$ must form a probability distribution. \Eqn{time} implies that the tester makes at most $t$ queries.

For any positive integer $s$, let ${\mathbf R}^{(s)}$ denote {\em unordered} sets of ${\mathbf R}$ of cardinality $s$. For reasons that will soon become clear, we introduce new functions as follows. For each $s$,  ${\mathbf x}\in {\mathbf D}^s$, $y\in {\mathbf D}'$, and {\em each permutation} $\sigma:[s]\mapsto [s]$, we associate functions $q^y_{{\mathbf x},\sigma}:{\mathbf R}^{(s)} \mapsto [0,1]$, with the semantic
$$\textrm{ For any set $S = (a_1 < a_2 < \cdots < a_s) \in {\mathbf R}^{(s)}$, } ~~~~q^y_{{\mathbf x},\sigma}(S) := p^y_{\mathbf x}(a_{\sigma(1)},\ldots,a_{\sigma(s)})$$

That is, $q^y_{{\mathbf x},\sigma_s}(S)$ sorts the answers in $S$ in increasing order, permutes it according to $\sigma$, and passes the permuted ordered tuple to $p^y_{\mathbf x}$. Any adaptive tester can be specified by these functions. The important point to note is that they are finitely many such functions; their number is upper bounded by $(t|{\mathbf D}|)^{t+1}$. These $q$-functions allow us to define comparison based testers.


\begin{definition} \label{def:comp}
A monotonicity tester ${\cal A}$ is \emph{comparison-based} if for all $s$,${\mathbf x}\in {\mathbf D}^s,y\in{\mathbf D}'$, and permutations $\sigma:[s]\mapsto[s]$, the function $q^y_{{\mathbf x},\sigma}$ is a constant function on ${\mathbf R}^{(s)}$. 
In other words, the $(s+1)$th decision of the tester given that the first $s$ questions is ${\mathbf x}$, depends only on the {\em ordering} of the answers received, and not on the values of the answers.
\end{definition}

The following theorem is implicit in the work of Fischer~\cite{E04}.

\begin{theorem} \label{thm:fischer} Suppose there exists a $(t,\varepsilon,\delta)$-monotonicity tester
for functions $f: {\mathbf D} \mapsto \mathbb{N}$. Then there exists a comparison-based $(t,\varepsilon,2\delta)$-monotonicity tester
for functions $f: {\mathbf D} \mapsto \mathbb{N}$.
\end{theorem}

This implies that a comparison-based lower bound suffices for proving a general lower bound on monotonicity testing.
We provide a proof of the above theorem in the next section for completeness.

\subsection{Performing the reduction} \label{sec:comp}

We basically present Fischer's argument, observing that ${\mathbf D}$ can be any partial order. 
A monotonicity tester is called \emph{discrete} if the corresponding functions $p^y_{{\mathbf x}}$ can
only take values in $\{i/K \ | \ 0 \leq i \leq K\}$ for some finite $K$. Note that this implies the functions $q^y_{{\mathbf x},\sigma}$ also take discrete values.

\begin{claim} \label{clm:discrete} Suppose there exists a $(t,\varepsilon,\delta)$-monotonicity tester ${\cal A}$
for functions $f: {\mathbf D} \mapsto \mathbb{N}$. Then there exists a discrete $(t,\varepsilon,2\delta)$-monotonicity tester for these functions.
\end{claim}
\def\hat{p}{\hat{p}}

\begin{proof} We do a rounding on the $p$-functions. Let $K = 100t|{\mathbf D}|^{t}/\delta^2$.
Start with the $p$-functions of the $(t,\varepsilon,\delta)$-tester ${\cal A}$.
For $y \in {\mathbf D} \cup {\tt acc}$, ${\mathbf x}\in{\mathbf D}^s$, ${\mathbf a}\in {\mathbf R}^s$, let 
$\hat{p}^y_{{\mathbf x}}({\mathbf a})$ be the largest value in $\{i/K \ | \ 0 \leq i \leq K\}$
at most $p^y_{\mathbf x}({\mathbf a})$. 
Set $\hat{p}^{\tt rej}_{\mathbf x}({\mathbf a})$ so that \Eqn{dist} is maintained. 

Note that for  $y \in {\mathbf D} \cup {\tt acc}$, if $p^y_{\mathbf x}({\mathbf a}) > 10|{\mathbf D}|t/(\delta K)$, then 
$$ \left(1 - \frac{\delta}{10|{\mathbf D}|t}\right) p^y_{\mathbf x}({\mathbf a}) ~ \leq ~\hat{p}^y_{\mathbf x}({\mathbf a})~ \leq ~p^y_{\mathbf x}({\mathbf a}).$$
Furthermore, $\hat{p}^{\tt rej}_{\mathbf x}({\mathbf a}) \geq p^{\tt rej}_{\mathbf x}({\mathbf a})$.

The $\hat{p}$-functions describe a new discrete tester ${\cal A}'$ that makes at most $t$ queries. We argue that ${\cal A}'$ is a $(t,\varepsilon,2\delta)$-tester.
Given a function $f$ that is either monotone or $\varepsilon$-far from monotone, 
consider a sequence of queries $x_1,\ldots,x_s$ after which ${\cal A}$ returns a {\em correct} decision $\aleph$. 
Call such a sequence good, and let $\alpha$ denote the probability this occurs. We know that the sum of probabilities over all good query sequences is at least $(1-\delta)$. Now,
$$\alpha := p^{x_1}\cdot ~p^{x_2}_{x_1}(f(x_1)) \cdot~ p^{x_3}_{(x_1,x_2)}(f(x_1),f(x_2))\cdots \cdot~ p^{\aleph}_{(x_1,\ldots,x_s)}(f(x_1),\ldots,f(x_s))$$

Two cases arise. suppose all of the probabilities in the RHS are $\geq 10t/\delta K$. Then, the probability of this good sequence arising in ${\cal A}'$ is at least $(1-\delta/10t)^t\alpha \geq \alpha(1-\delta/2)$.
Otherwise, suppose some probability in the RHS is $<10t/\delta K$. Then the total probability mass on such good sequences in ${\cal A}$ is atmost $10t/\delta K\cdot|{\mathbf D}|^t \leq \delta/2$.
Therefore, the probability of good sequences in ${\cal A}'$ is at least $(1-3\delta/2)(1-\delta/2) \geq 1-2\delta$.
That is, ${\cal A}'$ is a $(t,\varepsilon,2\delta)$ tester.
\end{proof}

\ignore{
Henceforth, we focus on discrete testers. We use the notation
$S^{(k)}$ for sets of size $k$ in $S$.
As defined, the $p$-functions have a domain $\mathbb{N}^s$, but it will be preferable to replace this with $\mathbb{N}^{(s)}$. 
This will
need some additional notation. Consider $\sigma_s: [s] \mapsto [s]$. Let ${\bf K}$ denote the
discrete set of possible probability values.
\begin{align}
& \forall s \leq t, \forall x_1, x_2, \ldots, x_s \in D, y \in D', \forall \sigma_s: [s] \mapsto [s], \ p_{y, x_1, x_2, \ldots, x_s,\sigma_s}: \mathbb{N}^{(s)} \mapsto {\bf K} \nonumber \\
& \forall s \leq t, \forall x_1, x_2, \ldots, x_s \in D, \forall S \in \mathbb{N}^{(s)}, \sum_{y \in D'} p_{y, x_1, x_2, \ldots, x_s}(S) = 1 \nonumber\\
& \forall x_1, x_2, \ldots, x_t, y \in D, \forall S \in \mathbb{N}^{(t)}, \forall \sigma_t:[t] \mapsto [t], \ p_{y, x_1, x_2, \ldots, x_t, \sigma_t}(S) = 0 \nonumber
\end{align}

Note that any element of $\mathbb{N}^s$ can be mapped to an element of $\mathbb{N}^{(s)}$ and function $\sigma_s$.
More precisely, suppose the function $p_{y, x_1, x_2, \ldots, x_s, \sigma_s}$ has the argument $\{v_1, v_2, \ldots, v_s\}$,
where the $v_i$'s are in sorted order. The output value is the probability of selection $y$ as the next query
when $f(x_1) = v_{\sigma(1)}$, $f(x_2) = v_{\sigma(2)}$, $\ldots, f(x_s) = v_{\sigma(s)}$. So the tester formulation
of the previous section can be converted to this form, and hence any property tester can represented
by this finite family of functions.

The notion of a comparison-based tester becomes quite clean now. The functions $p_{y, x_1, x_2, \ldots, x_s,\sigma_s}$
are constant functions iff the tester is comparison-based. 


\begin{claim} \label{clm:map} Consider some explicit strictly monotone function $\phi: \mathbb{N} \mapsto \mathbb{N}$. Consider the tester ${\cal A}'$
that, given input function $f$, actually runs ${\cal A}$ on $\phi \circ f$. Then ${\cal A}'$ is a $(t,\varepsilon,2\delta)$ tester.
\end{claim}

\begin{proof} Since $\phi$ is a strictly monotone function, the distance to monotonicity of $f$ and $\phi \circ f$
are identical. If $f$ is monotone or $\varepsilon$-far from monotone, the probability that ${\cal A}$ errors of $\phi \circ f$
is at most $2\delta$.
\end{proof}
}
\def{\tt col}{{\tt col}}


We introduce some Ramsey theory terminology.
For any positive integer $i$, a {\em finite} coloring of $\mathbb{N}^{(i)}$ is a function ${\tt col}_i:\mathbb{N}^{(i)} \mapsto \{1,\ldots,C\}$
for some finite number $C$. An infinite set $X\subseteq \mathbb{N}$ is called {\em monochromatic} w.r.t  ${\tt col}_i$ if for all sets $A,B \in X^{(i)}$, ${\tt col}_i(A) = {\tt col}_i(B)$. A {\em $k$-wise} finite coloring of $\mathbb{N}$ is a collection of $k$ colorings
${\tt col}_1,\ldots,{\tt col}_k$. (Note that each coloring is over different sized tuples.) 
An infinite set $X\subseteq \mathbb{N}$ is $k$-wise monochromatic if $X$ is monochromatic w.r.t. all the ${\tt col}_i$'s.

The following is a simple variant of Ramsey's original theorem.
(We closely follow the proof of Ramsey's theorem as given in Chap V1, Theorem 4 of~\cite{Bol00}.)


\begin{theorem} \label{thm:ramsey} For any $k$-wise  finite coloring of $\mathbb{N}$,
there is an infinite $k$-wise monochromatic set $X\subseteq \mathbb{N}$.
\end{theorem}
\begin{proof} We proceed by induction on $k$. If $k = 1$, then this is trivially true; let $X$ be
the maximum color class. Since the coloring is finite, $X$ is infinite.
We will now iteratively construct an infinite set of $\mathbb{N}$ via induction.

Start with $a_0$ being the minimum element in $\mathbb{N}$. Consider a $(k-1)$-wise coloring of $(\mathbb{N} \setminus \{a_0\})$
${\tt col}'_1,\ldots,{\tt col}'_{k-1}$, where ${\tt col}'_i(S) := {\tt col}_{i+1}(S\cup a_0)$.
By the induction hypothesis, there exists an infinite $(k-1)$-wise monochromatic
set $A_0\subseteq \mathbb{N}\setminus\{a_0\}$ with respect to coloring ${\tt col}'_i$s. 
That is, for $1\leq i\leq k$, and any set $S,T\subseteq A_0$ with $|S|=|T|=i-1$, we have 
${\tt col}_i(a_0\cup S)={\tt col}_i(a_0\cup T) = C^0_i$, say.
\def{\mathbf C}{{\mathbf C}}
Denote the collection of these colors as a vector ${\mathbf C}_0 = (C^0_1, C^0_2, \ldots, C^0_k)$.

 Subsequently, let $a_1$ be the minimum element in $A_0$, and consider the $(k-1)$-wise coloring ${\tt col}'$ of $(A_0 \setminus \{a_1\})$ where ${\tt col}'_i(S) = {\tt col}_{i+1}(S \cup \{a_1\})$ for $S\subseteq A_0\setminus\{a_1\}$.
Again, the induction hypothesis yields an infinite $(k-1)$-wise monochromatic set $A_1$ as before, and similarly the vector ${\mathbf C}_1$. 
Continuing this procedure, 
we get an infinite sequence $a_0, a_1, a_2, \ldots$ of natural numbers, an infinite sequence
of vectors of $k$ colors ${\mathbf C}_0, {\mathbf C}_1, \ldots$, and an infinite nested sequence of infinite sets $A_0 \supset A_1 \supset A_2 \ldots$.
Every $A_r$ contains $a_s, \forall s > r$ and by construction, any set $(\{a_r\} \cup S)$, $S\subseteq A_r$, $|S|=i-1$, 
has color $C^i_r$. Since there are only finitely many colors, some vector of colors occurs infinitely often as ${\mathbf C}_{r_1}, {\mathbf C}_{r_2}, \ldots$. The corresponding
infinite sequence of elements $a_{r_1}, a_{r_2}, \ldots$ is $k$-wise monochromatic.
\end{proof}



\begin{proof} (of \Thm{fischer}) 
Suppose there exists a $(t,\varepsilon,\delta)$-tester for functions $f:{\mathbf D}\mapsto \mathbb{N}$. We need to show there is a comparison-based $(t,\varepsilon,2\delta)$-tester for such functions.

By \Clm{discrete}, there is a discrete $(t,\varepsilon,2\delta)$-tester ${\cal A}$. Equivalently, we have the functions $q^y_{{\mathbf x},\sigma}$ as described in the previous section.
We now describe a $t$-wise finite coloring of $\mathbb{N}$. 
Consider $s \in [t]$.
Given a set $A\subseteq \mathbb{N}^{(s)}$, ${\tt col}_s(A)$ is a vector indexed by $(y,{\mathbf x},\sigma)$, where $y\in D'$, ${\mathbf x}\in D^s$, and $\sigma$ is a $s$-permutation, whose entry is $q^y_{{\mathbf x},\sigma}(A)$.
The domain is finite, so the number of dimensions is finite.
Since the tester is discrete, the number of possible colors entries is finite.  
Applying \Thm{ramsey}, we know the existence of a $t$-wise monochromatic infinite set ${\mathbf R}\subseteq \mathbb{N}$. We have the property that for any $y,{\mathbf x},\sigma$, and any two sets $A,B \in {\mathbf R}^{(s)}$, we have $q^y_{{\mathbf x},\sigma}(A) = q^y_{{\mathbf x},\sigma}(B)$. That is, the algorithm ${\cal A}$ is a comparison based tester for functions with range ${\mathbf R}$. 



Consider the strictly monotone map $\phi: \mathbb{N} \mapsto {\mathbf R}$, where $\phi(b)$ is the $b$th element of ${\mathbf R}$  in sorted order. Now given any function $f:{\mathbf D}\mapsto \mathbb{N}$, consider the function $\phi\circ f:{\mathbf D}\mapsto {\mathbf R}$. 
Consider an algorithm ${\cal A}'$ which on input $f$ runs ${\cal A}$ on $\phi\circ f$. More precisely, whenever ${\cal A}$ queries a point $x$, it gets answer $\phi\circ f(x)$.  Observe that if $f$ is monotone (or $\varepsilon$-far from monotone), then so is $\phi\circ f$, and therefore, the algorithm ${\cal A}'$ is a $(t,\varepsilon,2\delta)$-tester of $\phi\circ f$. Since the range of $\phi\circ f$ is ${\mathbf R}$,  
${\cal A}'$ is comparison-based.
\end{proof}%

\section{Lower bounds} \label{sec:dist}

\def\widetilde{f}{\widetilde{f}}
\def{\tt val}{{\tt val}}
We assume that $n$ is a power of $2$, set $\ell:=\log_2 n$, and think of $[n]$ as $\{0,1,\ldots,n-1\}$. 
For any number $0 \leq z < n$, we think of the binary representation as $z$ as an $\ell$-bit vector $(z_1, z_2, \ldots, z_\ell)$,
where $z_1$ is the least significant bit.

Consider the following canonical, one-to-one mapping $\phi: [n]^d \mapsto \{0,1\}^{d\ell}$.
For any $\vec{y} = (y_1, y_2, \ldots, y_d) \in [n]^d$, we concatenate their binary representations in order 
to get a $d\ell$-bit vector $\phi(\vec{y})$. Hence, we can transform a function $f:\{0,1\}^{d\ell}\mapsto \mathbb{N}$
into a function $\widetilde{f}:[n]^d \mapsto \mathbb{N}$ by defining $\widetilde{f}(\vec{y}) := f(\phi(\vec{y}))$.

We will now describe a distribution of functions over the boolean hypercube with equal mass on monotone and $\varepsilon$-far from monotone functions. The key property is that for a function drawn from this distribution, any deterministic comparison based algorithm errs in classifying it with non-trivial probability. 
This property will be used in conjunction with the above mapping to get our final lower bound.


\subsection{The hard distribution} \label{sec:hard}

We focus on functions $f:\{0,1\}^m \mapsto \mathbb{N}$. (Eventually, we set $m = d\ell$.)
Given any $x \in \{0,1\}^m$, we let ${\tt val}(x) :=  \sum_{i = 1}^{m} 2^{i-1} x_i$ denote the number for which $x$ is the binary representation. Here, $x_1$ denotes the least significant bit of $x$. 

For convenience, we let $\varepsilon$ be a power of $1/2$.
For $k \in \{1,\ldots,\frac{1}{2\varepsilon}\}$, we let  
$$S_k := \{x: {\tt val}(x) \in [2(k-1)\varepsilon 2^m, 2k\varepsilon 2^m-1)~~\}.$$
Note that $S_k$'s partition the hypercube, with each $|S_k| = \eps2^{m+1}$.
In fact, each $S_k$ is a subhypercube of dimension $m' := m+1-\log(1/\varepsilon)$, with the minimal element having all zeros in the $m'$ least significant bits, and the maximal element having all ones in those.

We describe a distribution ${\cal F}_{m,\varepsilon}$ on functions. 
The support of ${\cal F}_{m,\varepsilon}$ consists $f(x) = 2{\tt val}(x)$,
and $\frac{m'}{2\varepsilon}$ functions indexed as $g_{j,k}$ with $j\in [m']$ and $k\in[\frac{1}{2\varepsilon}]$, defined as follows.
$$ g_{j,k}(x) = 
\left\{ 
\begin{array} {l l}
2{\tt val}(x) - 2^{j} - 1& \quad \textrm{if $x_j = 1$ and $x \in S_k$}\\
2{\tt val}(x) & \quad \textrm{otherwise} 
\end{array} \right.
$$

The distribution ${\cal F}_{m,\varepsilon}$ puts probability mass $1/2$ on the function $f=2{\tt val}$ and $\frac{\varepsilon}{m'}$ on each of the $g_{j,k}$'s. 
All these functions take distinct values on their domain.
Note that $2{\tt val}$ induces a total order on $\{0,1\}^m$.\smallskip

\noindent
\textbf{The distinguishing problem:} Given query access to a random function $f$ from ${\cal F}_{m,\varepsilon}$, we want a deterministic comparison-based algorithm
that declares that $f = 2{\tt val}(x)$ or $f \neq 2{\tt val}(x)$. We refer to any such algorithm as a \emph{distinguisher}. 
Naturally, we say that the distinguisher errs on $f$ if it's declaration is wrong.
Our main lemma is the following.

\begin{lemma} \label{lem:main-hard} Any deterministic comparison-based distinguisher that makes less than $\frac{m'}{8\varepsilon}$ queries errs
with probability at least $1/8$.
\end{lemma}

\noindent
The following proposition allows us to focus on {\em non-adaptive} comparison based testers. 

\begin{proposition}	\label{prop:comp}
Given any deterministic comparison-based distinguisher ${\cal A}$ for ${\cal F}_{m,\varepsilon}$ that makes at most $t$ queries, there exists a deterministic {\em non-adaptive} comparison-based distinguisher ${\cal A}'$ making at most $t$ queries whose probability of error on ${\cal F}_{m,\varepsilon}$ is at most that of ${\cal A}$.
\end{proposition}
\def{\tt ans}{{\tt ans}}
\begin{proof}
We represent ${\cal A}$ as a comparison tree. For any path in ${\cal A}$, the total number of distinct domain points involved in comparisons is at most $t$.
Note that $2{\tt val}(x)$ is a total order, since for any $x,y$ either ${\tt val}(x) < {\tt val}(y)$ or vice versa.
For any comparison in ${\cal A}$, there is an outcome inconsistent with this ordering. (An outcome ``$f(x) < f(y)$"
where ${\tt val}(x) > {\tt val}(y)$ is inconsistent with the total order.)
We construct a comparison tree ${\cal A}'$
where we simply reject whenever a comparison is inconsistent with the total order, and otherwise mimics ${\cal A}$. 
The comparison tree of ${\cal A}'$ has an error probability at most that of ${\cal A}$ (since it may reject a few $f\neq 2{\tt val}$), and is just a path. Hence, it
can be modeled as a non-adaptive distinguisher. We query upfront all the points involving points on this path, and make the relevant comparisons
for the output.
\end{proof}




\def{\tt val}{{\tt val}}

\noindent
Combined with \Prop{comp}, the following lemma completes the proof of \Lem{main-hard}.
\begin{lemma}\label{lem:hard}
Any deterministic, non-adaptive, comparison-based distinguisher ${\cal A}$ making fewer than $t \leq \frac{m'}{8\varepsilon}$ queries, errs with probability at least $1/8$.
\end{lemma}
\begin{proof}


Let $X$ be the set of points queried by the distinguisher. Set $X_k =: X \cap S_k$; these form a partition of $X$.
We say that a pair of points $(x,y)$ \emph{captures} the (unique) coordinate $j$, if $j$ is the largest
coordinate where $x_j \neq y_j$. (By largest coordinate, we refer to the value of the index.)
For a set $Y$ of points, we say $Y$ captures coordinate $j$ if there is a pair in $Y$ that captures $j$.

\begin{claim}\label{clm:viol}
For any $j,k$, if the algorithm distinguishes between ${\tt val}$ and $g_{j,k}$, then $X_k$ captures $j$.
\end{claim}
\begin{proof} 
If the algorithm distinguishes between ${\tt val}$ and $g_{j,k}$, there must exist $(x,y)\in X$ such that
 ${\tt val}(x) < {\tt val}(y)$ and $g_{j,k}(x) > g_{j,k}(y)$. We claim that $x$ and $y$ capture $j$; this will also imply they lie in the same $S_{k'}$ since the $m-j$ most significant bit of $x$ and $y$ are the same.


Firstly, observe that we must have $y_j = 1$ and $x_j = 0$; otherwise, $g_{j,k}(y) - g_{j,k}(x) \geq 2({\tt val}(y) - {\tt val}(x)) > 0$ contradicting the supposition. Now suppose $(x,y)$ don't capture $j$ implying there exists $i>j$ which is the largest coordinate at which they differ. Since ${\tt val}(y)>{\tt val}(x)$ we have $y_i=1$ and $x_j=0$. Therefore,
we have $$g_{j,k}(y) - g_{j,k}(x) \geq 2({\tt val}(y)-{\tt val}(x)) - 2^{j} - 1
\geq (2^i + 2^j) - \sum_{1 \leq r < i} 2^r - 2^j - 1 > 0.$$
So, $x,y$ capture $j$ and lie in the same $S_{k'}$. If $k'\neq k$, then again $g_{j,k}(y) - g_{j,k}(x) = 2({\tt val}(y)-{\tt val}(x)) > 0$. Therefore, $X_k$ captures $j$.
\end{proof}

\noindent
The following claim allows us to complete the proof of the lemma.
\begin{claim}\label{clm:cap} A set $Y$ captures at most $|Y|-1$ coordinates.
\end{claim}

\begin{proof} We prove by induction on $|Y|$. When $|Y| = 2$, this is trivially true.
Otherwise, pick the largest coordinate $j$ captured by $Y$ and let $Y_0 =\{y: y_j = 0\}$ and $Y_1 = \{y:y_j = 1\}$. 
By induction, $Y_0$ captures at most $|Y_0|-1$ coordinates, and $Y_1$ captures at most $|Y_1| -1$ coordinates.
Pairs $(x,y)\in Y_0\times Y_1$ only capture coordinate $j$. Therefore, the total number of captured coordinates is at most $|Y_0| - 1 + |Y_1| - 1 + 1 = |Y| - 1$.
\end{proof}

\noindent

If $|X| \leq m'/8\varepsilon$, then there exist at least $1/4\varepsilon$ values of $k$
such that $|X_k| \leq m'/2$. 
By \Clm{cap}, each such $X_k$ captures at most $m'/2$ coordinates.
Therefore, there exist at least 
$\frac{1}{4\varepsilon}\cdot\frac{m'}{2} = \frac{m'}{8\varepsilon}$ functions $g_{j,k}$'s that are indistinguishable from the monotone function $2{\tt val}$ to a comparison-based procedure
that queries $X$. 
This implies the distinguisher must err (make a mistake on either these $g_{j,k}$'s or $2{\tt val}$) with probability at least $\min(\frac{\varepsilon}{m'}\cdot\frac{m'}{8\varepsilon}, 1/2) = 1/8$.
\end{proof}

\subsection{The final bound}
\def{\tt val}{{\tt val}}

Recall, given  function $f:\{0,1\}^{d\ell}\mapsto \mathbb{N}$, we have 
the function $\widetilde{f}:[n]^d \mapsto \mathbb{N}$ by defining $\widetilde{f}(\vec{y}) := f(\phi(\vec{y}))$.
We start with the following observation

\begin{proposition}\label{prop:dist}
The function $\widetilde{2{\tt val}}$ is monotone and
every $\widetilde{g_{j,k}}$ is $\varepsilon/2$-far from being monotone.
\end{proposition}

\begin{proof} Let $\vec{u}$ and $\vec{v}$ be elements in $[n]^d$ such that $\vec{u} \prec \vec{v}$.
We have ${\tt val}(\phi(\vec{u})) < {\tt val}(\phi(\vec{v}))$, so $\widetilde{2{\tt val}}$ is monotone.
For the latter, it suffices to exhibit a matching of violated pairs of cardinality $\eps2^{d\ell}$ for $\widetilde{g_{j,k}}$. This is 
given by pairs $(\vec{u},\vec{v})$ where $\phi(\vec{u})$ and $\phi(\vec{v})$ only differ in their
$j$th coordinate, and are both contained in $S_k$. Note that these pairs are comparable in $[n]^d$
and are violations.
\end{proof}


\begin{theorem}\label{thm:hc}
Any $(t,\varepsilon/2,1/16)$-monotonicity tester for $f:[n]^d\mapsto \mathbb{N}$, must have $t\geq \frac{d\log n - \log(1/\varepsilon)}{8\varepsilon}$.
\end{theorem}

\begin{proof} By \Thm{fischer}, it suffices to show this for comparison-based $(t,\varepsilon/2,1/8)$ testers.
By Yao's minimax lemma, it suffices to produce a distribution ${\cal D}$ over functions $f:[n]^d\mapsto \mathbb{N}$ such
that any deterministic comparison-based $(t,\varepsilon/2,1/8)$-monotonicity tester for ${\cal D}$ must have $t\geq s$,
where $s := \frac{d\log n - \log(1/\varepsilon)}{8\varepsilon}$.

Consider the distribution ${\cal D}$ where we generate $f$ from ${\cal F}_{m,\varepsilon}$ and output $\widetilde{f}$. 
Suppose $t < s$. By \Prop{dist}, the deterministic comparison based monotonicity tester acts as a determinisitic comparison-based distinguisher
for ${\cal F}_{m,\varepsilon}$
making fewer than $s$ queries, contradicting \Lem{hard}.
\end{proof}

\section{Conclusion}
In this paper, we exhibit a lower bound of $\Omega(\varepsilon^{-1}d\log n - \varepsilon^{-1}\log \varepsilon^{-1})$ queries on adaptive, two-sided monotonicity testers for functions $f:[n]^d \mapsto \mathbb{N}$, matching the upper bound of $O(\varepsilon^{-1}d\log n)$ queries of~\cite{ChSe13}. Our proof hinged on two things: that for monotonicity on any partial order one can focus on comparison-based testers, and a lower bound on comparison-based testers for the hypercube domain.  Some natural questions are left open. Can one focus on some restricted class of testers for the Lipschitz property, and more generally, can one prove adaptive, two-sided lower bounds for the Lipschitz property testing on the hypergrid/cube? 
Currently, a $\Omega(d\log n)$-query non-adaptive lower bound is known for the problem~\cite{BlJh+12}.
Can one prove comparison-based lower bounds for monotonicity testing on a general $N$-vertex poset? For the latter problem, there is a $O(\sqrt{N/\varepsilon})$-query non-adaptive tester, and a $\Omega(N^{\frac{1}{\log\log N}})$-query non-adaptive, two-sided error lower bound~\cite{FLNRRS02}.
Our methods do not yield any results for bounded ranges, but there are significant gaps in our understanding for that regime. 
For monotonicity testing of boolean functions $f:\{0,1\}^n \mapsto \{0,1\}$, the best adaptive lower bound
of $\Omega(\log n)$, while the best non-adaptive bound is $\Omega(\sqrt{n})$~\cite{FLNRRS02}. 

\bibliographystyle{alpha}
