  The Khintchine recurrence theorem asserts that on a measure preserving
system, for every set $A$ and $\varepsilon>0$, we have $\mu(A\cap T^{-n}A)\geq
\mu(A)^2-\varepsilon$ for infinitely many $n\in \mathbb{N}$. We show that there
are systems having under-recurrent sets $A$, in the sense that the inequality
$\mu(A\cap T^{-n}A)< \mu(A)^2$ holds for every $n\in \mathbb{N}$. In
particular, all ergodic systems of positive entropy have under-recurrent sets.
On the other hand, answering a question of V.~Bergelson, we show that not all
mixing systems have under-recurrent sets. We also study variants of these
problems where the previous strict inequality is reversed, and deduce that
under-recurrence is a much more rare phenomenon than over-recurrence. Finally,
we study related problems pertaining to multiple recurrence and derive some
interesting combinatorial consequences.
