  An $\epsilon$-test for any non-trivial property (one for which there are both
satisfying inputs and inputs of large distance from the property) should use a
number of queries that is at least inversely proportional in $\epsilon$.
However, to the best of our knowledge there is no reference proof for this
intuition. Such a proof is provided here. It is written so as to not require
any prior knowledge of the related literature, and in particular does not use
Yao's method.
