Families of functionals representing Sobolev norms

We obtain new characterizations of the Sobolev spaces $\dot W^{1,p}(\mathbb{R}^N)$ and the bounded variation space $\dot{BV}(\mathbb{R}^N)$. The characterizations are in terms of the functionals $\nu_{\gamma} (E_{\lambda,\gamma/p}[u])$ where \[ E_{\lambda,\gamma/p}[u]= \Big\{(x,y )\in \mathbb{R}^N \times \mathbb{R}^N \colon x \neq y, \, \frac{|u(x)-u(y)|}{|x-y|^{1+\gamma/p}}>\lambda\Big\} \] and the measure $\nu_{\gamma}$ is given by $\mathrm{d} \nu_\gamma(x,y)=|x-y|^{\gamma-N} \mathrm{d} x \mathrm{d} y$. We provide characterizations which involve the $L^{p,\infty}$-quasi-norms $\sup_{\lambda>0} \lambda \, \nu_{\gamma} (E_{\lambda,\gamma/p}[u]) ^{1/p}$ and also exact formulas via corresponding limit functionals, with the limit for $\lambda\to\infty$ when $\gamma>0$ and the limit for $\lambda\to 0^+$ when $\gamma<0$. The results unify and substantially extend previous work by Nguyen and by Brezis, Van Schaftingen and Yung. For $p>1$ the characterizations hold for all $\gamma \neq 0$. For $p=1$ the upper bounds for the $L^{1,\infty}$ quasi-norms fail in the range $\gamma\in [-1,0) $; moreover in this case the limit functionals represent the $L^1$ norm of the gradient for $C^\infty_c$-functions but not for generic $\dot W^{1,1}$-functions. For this situation we provide new counterexamples which are built on self-similar sets of dimension $\gamma+1$. For $\gamma=0$ the characterizations of Sobolev spaces fail; however we obtain a new formula for the Lipschitz norm via the expressions $\nu_0(E_{\lambda,0}[u])$.