Testing forbidden order-pattern properties on hypergrids

We study testing $π$-freeness of functions $f:[n]^d\to\mathbb{R}$, where $f$ is $π$-free if there there are no $k$ indices $x_1\prec\cdots\prec x_k\in [n]^d$ such that $f(x_i)<f(x_j)$ and $π(i) < π(j)$ for all $i,j \in [k]$, where $\prec$ is the natural partial order over $[n]^d$. Given $ε\in(0,1)$, $ε$-testing $π$-freeness asks to distinguish $π$-free functions from those which are $ε$-far -- meaning at least $εn^d$ function values must be modified to make it $π$-free. While $k=2$ coincides with monotonicity testing, far less is known for $k>2$. We initiate a systematic study of pattern freeness on higher-dimensional grids. For $d=2$ and all permutations of size $k=3$, we design an adaptive one-sided tester with query complexity $O(n^{4/5+o(1)})$. We also prove general lower bounds for $k=3$: every nonadaptive tester requires $Ω(n)$ queries, and every adaptive tester requires $Ω(\sqrt{n})$ queries, yielding the first super-logarithmic lower bounds for $π$-freeness. For the monotone patterns $π=(1,2,3)$ and $(3,2,1)$, we present a nonadaptive tester with polylogarithmic query complexity, giving an exponential separation between monotone and nonmonotone patterns (unlike the one-dimensional case). A key ingredient in our $π$-freeness testers is new erasure-resilient ($δ$-ER) $ε$-testers for monotonicity over $[n]^d$ with query complexity $O(\log^{O(d)}n/(ε(1-δ)))$, where $0<δ<1$ is an upper bound on the fraction of erasures. Prior ER testers worked only for $δ=O(ε/d)$. Our nonadaptive monotonicity tester is nearly optimal via a matching lower bound due to Pallavoor, Raskhodnikova, and Waingarten (Random Struct. Algorithms, 2022). Finally, we show that current techniques cannot yield sublinear-query testers for patterns of length $4$ even on two-dimensional hypergrids.