A Complete Dichotomy for $L_{\mathrm{\infty }}$ Permutation Removal

We study the removal problem for permutation patterns under the normalized $L_{\mathrm{\infty }}$ earth mover’s distance. We prove a complete dichotomy. Let $$\mathcal{E}=\{(12),(21),(132),(213),(231),(312)\}\mathrm{.}$$ If $\sigma \in \mathcal{E}$, then every permutation of length $n$ that is $\epsilon$-far from being $\sigma$-free contains at least $\epsilon (n-1)$ copies of $\sigma$; for $0<\epsilon \le 1\mathrm{/}16$, this is sharp up to a constant factor for all sufficiently large $n$. If $\sigma \in S_k\setminus \mathcal{E}$, then for every sufficiently large $n$ there is a permutation of length $n$ that is $1\mathrm{/}(8k)$-far from being $\sigma$-free and contains exactly one copy of $\sigma$. Thus the usual positive-density removal conclusion fails for every nontrivial permutation pattern, but the sparse behavior is completely characterized: the minimum number of copies is linear for exactly six patterns and is one for all others. Consequently, no canonical one-sided tester that rejects only after finding a forbidden copy can have query complexity independent of the permutation length.