The main objective of this paper is to prove new necessary conditions to the existence of KAM tori. To do so, we develop a set of explicit a-priori estimates for smooth solutions of Hamilton-Jacobi equations, using a combination of methods from viscosity solutions, KAM and Aubry-Mather theories. These estimates are valid in any space dimension, and can be checked numerically to detect gaps between KAM tori and Aubry-Mather sets. We apply these results to detect non-integrable regions in several...