  We show that there exist properties that are maximally hard for testing,
while still admitting PCPPs with a proof size very close to linear.
Specifically, for every fixed $\ell$, we construct a property
$\mathcal{P}^{(\ell)}\subseteq\{0,1\}^n$ satisfying the following: Any testing
algorithm for $\mathcal{P}^{(\ell)}$ requires $\Omega(n)$ many queries, and yet
$\mathcal{P}^{(\ell)}$ has a constant query PCPP whose proof size is $O(n\cdot
\log^{(\ell)}n)$, where $\log^{(\ell)}$ denotes the $\ell$ times iterated log
function (e.g., $\log^{(2)}n = \log \log n$). The best previously known upper
bound on the PCPP proof size for a maximally hard to test property was $O(n
\cdot \mathrm{poly}\log{n})$.
  As an immediate application, we obtain stronger separations between the
standard testing model and both the tolerant testing model and the
erasure-resilient testing model: for every fixed $\ell$, we construct a
property that has a constant-query tester, but requires
$\Omega(n/\log^{(\ell)}(n))$ queries for every tolerant or erasure-resilient
tester.
