A Distance Amplification Lemma for Monotonicity

We show a procedure that, given oracle access to a function $f\text{\hspace{0.17em}⁣}:\{0,1{\}}^n\to \{0,1\}$, produces oracle access to a function $f^{\mathrm{\prime }}\text{\hspace{0.17em}⁣}:\{0,1{\}}^{n^{\mathrm{\prime }}}\to \{0,1\}$ such that if $f$ is monotone, then $f^{\mathrm{\prime }}$ is monotone, and if $f$ is $\epsilon$-far from monotone, then $f^{\mathrm{\prime }}$ is $\mathrm{\Omega }(1)$-far from monotone. Moreover, $n^{\mathrm{\prime }}\le n{2}^{O(1\mathrm{/}\epsilon )}$ and each oracle query to $f^{\mathrm{\prime }}$ can be answered by making $2^{O(1\mathrm{/}\epsilon )}$ oracle queries to $f$. Our lemma is motivated by a recent result of [Chen, Chen, Cui, Pires, Stockwell, arXiv:2511.04558], who showed that for all $c>0$ there exists ${\epsilon }_c>0$, such that any (even two-sided, adaptive) algorithm distinguishing between monotone functions and ${\epsilon }_c$-far from monotone functions, requires $\mathrm{\Omega }(n^{1\mathrm{/}2-c})$ queries. Combining our lemma with their result implies a similar result, except that the distance from monotonicity is an absolute constant $\epsilon >0$, and the lower bound is $\mathrm{\Omega }(n^{1\mathrm{/}2-o(1)})$ queries.