Proof of Rademacher's Theorem in $\mathbb{R}^n$

We use the notation of the statement. Being Lipschitz, $f$ is continuous from $(\mathbb{R}^{n},d_{E})$ to $(\mathbb{R},d_{\mathbb{R}})$ by A Lipschitz Map is Uniformly Continuous and Continuous, where $d_{\mathbb{R}}(s,t)=|s-t|$ is the absolute value metric. For $1\le i\le n$ let $e_{i}$ be the standard basis vector of $\mathbb{R}^{n}$ whose $i$th coordinate is $1$ and whose other coordinates are $0$, and for $y\in\mathbb{R}^{n}$ and real $s\neq0$ put $\Delta^{i}_{s}(y)=(f(y+se_{i})-f(y))/s$.

A norm inequality used twice. For a natural number $q\ge1$ and $v=(v_{1},\dots,v_{q})\in\mathbb{R}^{q}$ we have

$$\lVert v\rVert\le\sigma_{q}\max_{1\le k\le q}|v_{k}| ,$$

where $\sigma_{q}$ is the constant of the setting, satisfying $\sigma_{q}^{2}=q$. Indeed, by claim 1 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square and Difference, Dot Product, and Orthogonality in $\mathbb{R}^n$, $\lVert v\rVert^{2}=\sum_{k=1}^{q}v_{k}^{2}\le q\bigl(\max_{k}|v_{k}|\bigr)^{2}=\bigl(\sigma_{q}\max_{k}|v_{k}|\bigr)^{2}$, and both $\lVert v\rVert$ and $\sigma_{q}\max_{k}|v_{k}|$ are nonnegative. The inequality between the squares forces the asserted one: if instead $\sigma_{q}\max_{k}|v_{k}|<\lVert v\rVert$ held, then multiplying this inequality by itself, which is legitimate for nonnegative numbers, would give $(\sigma_{q}\max_{k}|v_{k}|)^{2}<\lVert v\rVert^{2}$, a contradiction.

Step 1 (The exceptional set). For $1\le i\le n$ let $E_{i}$ be the set of points at which $\partial_{i}f$ exists. By The Partial Derivatives of a Lipschitz Function on $\mathbb{R}^n$ Exist Almost Everywhere (i) each $\mathbb{R}^{n}\setminus E_{i}$ is a Borel null set, so by Null Set of a Measure and claim 2 of Basic Properties of a Measure it satisfies $\lambda_{n}(\mathbb{R}^{n}\setminus E_{i})=0$. Put $E=\bigcap_{i=1}^{n}E_{i}$; then $\mathbb{R}^{n}\setminus E=\bigcup_{i=1}^{n}(\mathbb{R}^{n}\setminus E_{i})$ is Borel, since a $\sigma$-algebra contains the union of finitely many of its members, and it is null by claim 5 of Elementary Properties of Lebesgue Outer Measure on $\mathbb{R}^n$.

Since $f$ is continuous, Borel Structure of the Set Where a Partial Derivative Exists applies for each index $i$; write $E^{(i)}_{j,k}$ for the set denoted $E_{j,k}$ there when it is applied with that index.

Write $\mathbb{Q}$ for the rational numbers. For $k\in\mathbb{N}$, $\mathbf{j}=(j_{1},\dots,j_{n})$ with every $j_{i}\in\mathbb{N}$, and $\mathbf{q}=(q_{1},\dots,q_{n})$ with every $q_{i}\in\mathbb{Q}$, put

$$G(k,\mathbf{j},\mathbf{q})=\Bigl\{\,y\in E\;:\;y\in E^{(i)}_{j_{i},k}\ \text{and}\ |\partial_{i}f(y)-q_{i}|\le\tfrac{1}{k}\ \text{ for every }i\text{ with }1\le i\le n\,\Bigr\}.$$

By The Integers and the Rational Numbers are Countable and Products and Powers of Countable Sets the set of triples $(k,\mathbf{j},\mathbf{q})$ is countable, so these sets form a countable family. For each triple, The Lebesgue Density Theorem in $\mathbb{R}^n$ (i) shows that the set of those $y\in G(k,\mathbf{j},\mathbf{q})$ which are not density points of $G(k,\mathbf{j},\mathbf{q})$ is null; let $Z$ be the union of these sets over all triples, a null set by claim 5 of Elementary Properties of Lebesgue Outer Measure on $\mathbb{R}^n$. The set $(\mathbb{R}^{n}\setminus E)\cup Z$ is then null, so by Null Set of a Measure there is $N\in\mathcal{B}(\mathbb{R}^{n})$ with $(\mathbb{R}^{n}\setminus E)\cup Z\subseteq N$ and $\lambda_{n}(N)=0$.

Fix $x\in\mathbb{R}^{n}\setminus N$ for the rest of Steps 2 and 3. Then $x\in E$, so all $n$ partial derivatives of $f$ exist at $x$ and $Df(x)$ is defined; and $x$ is a density point of every set $G(k,\mathbf{j},\mathbf{q})$ containing it.

Step 2 (Choice of a good set). Let $\varepsilon\in\mathbb{R}$ with $0<\varepsilon$, and put $C=n\,2^{n}$. Choose

$$\delta_{1}=\min\Bigl\{1,\ \frac{\varepsilon}{4Ln(C+1)+4}\Bigr\},$$

a positive real number with $\delta_{1}\le1$ and $2Ln(C+1)\delta_{1}\le\varepsilon/2$, and use The Archimedean Property of the Real Numbers to choose $k\in\mathbb{N}$ with $1/k<\varepsilon/(6n)$, so that $3n/k\le\varepsilon/2$.

For each $i$, since $x\in E_{i}$, Borel Structure of the Set Where a Partial Derivative Exists (iii) provides $j_{i}\in\mathbb{N}$ with $x\in E^{(i)}_{j_{i},k}$, and The Rational Numbers are Dense in the Real Numbers provides $q_{i}\in\mathbb{Q}$ with $|\partial_{i}f(x)-q_{i}|\le1/k$. Write $G=G(k,\mathbf{j},\mathbf{q})$; then $x\in G$, so $x$ is a density point of $G$.

We record the key property of $G$: for every $z\in G$, every $i$ with $1\le i\le n$ and every $s\in\mathbb{R}$ with $0<|s|\le1/j_{i}$,

$$\bigl|f(z+se_{i})-f(z)-s\,\partial_{i}f(x)\bigr|\le\frac{3|s|}{k}. \tag{$\ast$}$$

Indeed $z\in E_{i}\cap E^{(i)}_{j_{i},k}$, so Borel Structure of the Set Where a Partial Derivative Exists (iv) gives $|\Delta^{i}_{s}(z)-\partial_{i}f(z)|\le1/k$, while $|\partial_{i}f(z)-q_{i}|\le1/k$ and $|\partial_{i}f(x)-q_{i}|\le1/k$ give $|\partial_{i}f(z)-\partial_{i}f(x)|\le2/k$ by claim 5 of Properties of the Absolute Value in an Ordered Field; adding and multiplying by $|s|$ gives $(\ast)$.

By Near a Density Point Every Direction Meets the Set Closely (i), applied to $G$, to the density point $x$ and to $\delta_{1}$, there is $\rho\in\mathbb{R}$ with $0<\rho$ such that for every $w\in\mathbb{R}^{n}$ with $0<\lVert w-x\rVert<\rho$ there is $g\in G$ with $\lVert g-w\rVert\le\delta_{1}\lVert w-x\rVert$. Put

$$\delta=\min\Bigl\{\tfrac{1}{j_{1}},\dots,\tfrac{1}{j_{n}},\ \frac{\rho}{2C+2}\Bigr\},$$

a positive real number.

Step 3 (The telescoping estimate). Let $h\in\mathbb{R}^{n}$ with $\lVert h\rVert<\delta$. If $h=0$ the asserted inequality is trivial, so assume $h\neq0$ and put $\eta=\lVert h\rVert$, so $0<\eta<\delta$. Write $h=(h_{1},\dots,h_{n})$, so that $h=\sum_{p=1}^{n}h_{p}e_{p}$ and $|h_{p}|\le\eta$ for every $p$ by claim 4 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square.

Define points $z_{0},\dots,z_{n}$ and $w_{1},\dots,w_{n}$ recursively: $z_{0}=x$, and for $1\le p\le n$ put $w_{p}=z_{p-1}+h_{p}e_{p}$ and let $z_{p}=w_{p}$ if $w_{p}=x$, while if $w_{p}\neq x$ let $z_{p}\in G$ satisfy $\lVert z_{p}-w_{p}\rVert\le\delta_{1}\lVert w_{p}-x\rVert$. In either case

$$z_{p}\in G\qquad\text{and}\qquad\lVert z_{p}-w_{p}\rVert\le\delta_{1}\lVert w_{p}-x\rVert . \tag{$\ast\ast$}$$

We must check that this recursion is legitimate, that is, that $\lVert w_{p}-x\rVert<\rho$ whenever $w_{p}\neq x$. Put $c_{p}=\lVert z_{p}-x\rVert$, so $c_{0}=0$. For $1\le p\le n$, the triangle inequality (claim 6 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square) and claim 5 of that lemma give

$$\lVert w_{p}-x\rVert\le c_{p-1}+|h_{p}|\,\lVert e_{p}\rVert=c_{p-1}+|h_{p}|\le c_{p-1}+\eta ,$$

and then $c_{p}\le\lVert w_{p}-x\rVert+\lVert z_{p}-w_{p}\rVert\le(1+\delta_{1})\lVert w_{p}-x\rVert\le 2(c_{p-1}+\eta)$, using $\delta_{1}\le1$. By induction $c_{p}\le\eta\sum_{l=1}^{p}2^{l}$ for $1\le p\le n$, and $\sum_{l=1}^{p}2^{l}=2^{p+1}-2\le n\,2^{n}=C$ for $1\le p\le n$; hence $c_{p}\le C\eta$ and

$$\lVert w_{p}-x\rVert\le c_{p-1}+\eta\le(C+1)\eta\qquad(1\le p\le n).$$

Since $\eta<\delta\le\rho/(2C+2)$ we get $\lVert w_{p}-x\rVert\le(C+1)\eta<\rho/2<\rho$, as required. (Each application of the recursion uses only the already constructed $z_{p-1}$, so the estimates above are available at the moment they are needed.)

From $z_{p}=z_{p-1}+h_{p}e_{p}+(z_{p}-w_{p})$ and $h=\sum_{p}h_{p}e_{p}$ we get $z_{n}=(x+h)+\sum_{p=1}^{n}(z_{p}-w_{p})$, so by the triangle inequality and $(\ast\ast)$,

$$\lVert x+h-z_{n}\rVert\le\sum_{p=1}^{n}\lVert z_{p}-w_{p}\rVert\le\delta_{1}\sum_{p=1}^{n}\lVert w_{p}-x\rVert\le\delta_{1}\,n\,(C+1)\,\eta .$$

Moreover

$$f(x+h)-f(x)=\sum_{p=1}^{n}\bigl(f(w_{p})-f(z_{p-1})\bigr)+\sum_{p=1}^{n}\bigl(f(z_{p})-f(w_{p})\bigr)+\bigl(f(x+h)-f(z_{n})\bigr),$$

because the first two sums together telescope to $f(z_{n})-f(z_{0})=f(z_{n})-f(x)$.

We estimate the three parts. If $h_{p}\neq0$ then $0<|h_{p}|\le\eta<\delta\le1/j_{p}$, so $(\ast)$ applied with $z=z_{p-1}\in G$, the index $p$ and $s=h_{p}$ gives $|f(w_{p})-f(z_{p-1})-h_{p}\partial_{p}f(x)|\le3|h_{p}|/k\le3\eta/k$; if $h_{p}=0$ then $w_{p}=z_{p-1}$ and both $f(w_{p})-f(z_{p-1})$ and $h_{p}\partial_{p}f(x)$ are $0$. Since $\sum_{p=1}^{n}h_{p}\partial_{p}f(x)=Df(x)\cdot h$ by Difference, Dot Product, and Orthogonality in $\mathbb{R}^n$, summing gives

$$\Bigl|\sum_{p=1}^{n}\bigl(f(w_{p})-f(z_{p-1})\bigr)-Df(x)\cdot h\Bigr|\le\frac{3n\eta}{k}.$$

The Lipschitz hypothesis and $(\ast\ast)$ give

$$\sum_{p=1}^{n}\bigl|f(z_{p})-f(w_{p})\bigr|\le L\sum_{p=1}^{n}\lVert z_{p}-w_{p}\rVert\le L\,\delta_{1}\,n\,(C+1)\,\eta ,$$

and likewise $|f(x+h)-f(z_{n})|\le L\lVert x+h-z_{n}\rVert\le L\,\delta_{1}\,n\,(C+1)\,\eta$. Adding the three estimates,

$$\bigl|f(x+h)-f(x)-Df(x)\cdot h\bigr|\le\frac{3n}{k}\,\eta+2L\,\delta_{1}\,n\,(C+1)\,\eta\le\frac{\varepsilon}{2}\eta+\frac{\varepsilon}{2}\eta=\varepsilon\,\lVert h\rVert ,$$

by the choices of $k$ and $\delta_{1}$. This proves claim 1.

Step 4 (Claims 2 and 3). Let $x$ be as in claim 1 and let $A$ be the matrix with one row and $n$ columns given by $A_{1i}=\partial_{i}f(x)$. By Matrix-Vector Product the product $Ah$ is the point of $\mathbb{R}^{1}$ whose single coordinate is $\sum_{i=1}^{n}A_{1i}h_{i}=Df(x)\cdot h$, and by claim 1 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square the Euclidean norm of a point of $\mathbb{R}^{1}$ is the absolute value of its coordinate, both being the unique nonnegative real number whose square is the square of that coordinate. Hence the inequality of claim 1 reads $\lVert f(x+h)-f(x)-Ah\rVert\le\varepsilon\lVert h\rVert$ for $\lVert h\rVert<\delta$, and since $x+h\in\mathbb{R}^{n}$ always, Differentiability at a Point for Functions Between Euclidean Spaces shows that $f$ is differentiable at $x$ with derivative matrix $A$. Claim 2 of The Derivative Is the Jacobian Matrix, and Is Unique identifies $A$ with the Jacobian matrix. This is claim 2.

For claim 3, if $Df(x)=0$ then $\lVert Df(x)\rVert=0\le L$ by claim 3 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square. Otherwise $0<\lVert Df(x)\rVert$ by that same claim. Let $\varepsilon>0$ and let $\delta$ be as in claim 1. Choose $t\in\mathbb{R}$ with $0<t$ and $t\lVert Df(x)\rVert<\delta$, and put $h=t\,Df(x)$, so $\lVert h\rVert=t\lVert Df(x)\rVert<\delta$ by claim 5 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square and $Df(x)\cdot h=t\lVert Df(x)\rVert^{2}$ by claim 1 of that lemma. Then, by claim 1 of the present theorem and the Lipschitz hypothesis,

$$t\lVert Df(x)\rVert^{2}\le\bigl|f(x+h)-f(x)\bigr|+\varepsilon\lVert h\rVert\le L\lVert h\rVert+\varepsilon\lVert h\rVert=(L+\varepsilon)\,t\,\lVert Df(x)\rVert .$$

Dividing by the positive number $t\lVert Df(x)\rVert$ gives $\lVert Df(x)\rVert\le L+\varepsilon$, and since $\varepsilon>0$ was arbitrary, $\lVert Df(x)\rVert\le L$.

Step 5 (Claim 4). We first prove the following assertion about real-valued maps, in which $V$ and $g$ are fresh letters: if $V\subseteq\mathbb{R}^{n}$ is open and $g:V\to\mathbb{R}$ is locally Lipschitz on $V$, then the set of those $x\in V$ at which $g$ is not differentiable is null. To lighten the notation we write $U$ and $T$ for $V$ and $g$ in the four paragraphs that follow, so that $T$ is real-valued there; the letters resume their meaning from the statement afterwards. Let $\mathcal{C}$ be the set of pairs $(p,r)$ with $p\in\mathbb{R}^{n}$ having all coordinates rational, $r\in\mathbb{Q}$ with $0<r$, $\bar{B}(p,r)\subseteq U$, and the restriction of $T$ to $\bar{B}(p,r)$ Lipschitz with some constant. By The Integers and the Rational Numbers are Countable and Products and Powers of Countable Sets the set $\mathcal{C}$ is countable.

We claim $U=\bigcup_{(p,r)\in\mathcal{C}}B(p,r)$. Each $B(p,r)\subseteq\bar{B}(p,r)\subseteq U$. Conversely let $x\in U$; by local Lipschitz continuity there are $r_{x},L_{x}\in\mathbb{R}$ with $0<r_{x}$, $0\le L_{x}$, $\bar{B}(x,r_{x})\subseteq U$ and $T$ Lipschitz with constant $L_{x}$ on $\bar{B}(x,r_{x})$. By The Rational Numbers are Dense in the Real Numbers choose $r\in\mathbb{Q}$ with $r_{x}/4<r<r_{x}/2$, and choose rational numbers $p_{1},\dots,p_{n}$ with $|p_{i}-x_{i}|<r_{x}/(4\sigma_{n})$ for every $i$; then $p=(p_{1},\dots,p_{n})$ satisfies $\lVert p-x\rVert<r_{x}/4$ by the norm inequality recorded at the start. Hence $\lVert p-x\rVert<r$, so $x\in B(p,r)$; and if $y\in\bar{B}(p,r)$ then $\lVert y-x\rVert\le\lVert y-p\rVert+\lVert p-x\rVert\le r+r_{x}/4<r_{x}$, so $\bar{B}(p,r)\subseteq\bar{B}(x,r_{x})\subseteq U$ and $T$ is Lipschitz with constant $L_{x}$ on $\bar{B}(p,r)$. Thus $(p,r)\in\mathcal{C}$ and $x\in B(p,r)$.

Fix $(p,r)\in\mathcal{C}$ and let $L'$ be a Lipschitz constant for $T$ on the nonempty set $\bar{B}(p,r)$. By McShane Extension of a Real-Valued Lipschitz Function on a Metric Space (i), McShane Extension of a Real-Valued Lipschitz Function on a Metric Space (ii) and McShane Extension of a Real-Valued Lipschitz Function on a Metric Space (iii), applied in the metric space $(\mathbb{R}^{n},d_{E})$, there is $F:\mathbb{R}^{n}\to\mathbb{R}$ which is Lipschitz with constant $L'$ and agrees with $T$ on $\bar{B}(p,r)$. Applying claims 1 and 2 of the present theorem to $F$ in place of $f$ and $L'$ in place of $L$, there is a Borel set $N'$ with $\lambda_{n}(N')=0$ such that $F$ is differentiable at every point of $\mathbb{R}^{n}\setminus N'$.

Let $x\in B(p,r)\setminus N'$ and let $A'$ be the derivative matrix of $F$ at $x$. Since $B(p,r)$ is open there is $\delta_{2}>0$ with $B(x,\delta_{2})\subseteq B(p,r)$. Given $\varepsilon>0$, take the smaller of $\delta_{2}$ and the radius supplied by the differentiability of $F$ at $x$; for $h$ with $0<\lVert h\rVert$ less than that number we have $x+h\in B(p,r)\subseteq U$, so $T(x+h)=F(x+h)$ and $T(x)=F(x)$, whence $\lVert T(x+h)-T(x)-A'h\rVert\le\varepsilon\lVert h\rVert$. Thus $T$ is differentiable at $x$. Consequently the set of those $x\in B(p,r)$ at which $T$ is not differentiable is contained in $N'$ and hence null, and the set of those $x\in U$ at which $T$ is not differentiable, being contained in the union over the countable set $\mathcal{C}$ of these sets, is null by claim 5 of Elementary Properties of Lebesgue Outer Measure on $\mathbb{R}^n$.

This proves the assertion about real-valued maps. Now let $U$, $m$ and $T:U\to\mathbb{R}^{m}$ again be as in the statement of claim 4, and let $T_{1},\dots,T_{m}$ be the coordinate functions of $T$, as in Jacobian Matrix of a Function Between Euclidean Spaces. By claim 4 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square, $|T_{k}(y)-T_{k}(z)|\le\lVert T(y)-T(z)\rVert$ for all $y,z$, so each $T_{k}$ is locally Lipschitz on $U$ with the same local constants as $T$. By the assertion about real-valued maps just proved, for each $k$ the set $M_{k}$ of points of $U$ at which $T_{k}$ is not differentiable is null; put $M=\bigcup_{k=1}^{m}M_{k}$, a null set by claim 5 of Elementary Properties of Lebesgue Outer Measure on $\mathbb{R}^n$.

Let $x\in U\setminus M$ and let $A$ be the matrix with $m$ rows and $n$ columns given by $A_{ki}=\partial_{i}T_{k}(x)$, which is defined by claim 1 of The Derivative Is the Jacobian Matrix, and Is Unique applied to each $T_{k}$. Let $\varepsilon>0$. For each $k$, differentiability of $T_{k}$ at $x$ together with claim 2 of the present theorem, applied to $T_{k}$, provides $\delta_{k}>0$ such that $|T_{k}(x+h)-T_{k}(x)-\sum_{i=1}^{n}A_{ki}h_{i}|\le(\varepsilon/\sigma_{m})\lVert h\rVert$ whenever $\lVert h\rVert<\delta_{k}$; let $\delta$ be the smallest of $\delta_{1},\dots,\delta_{m}$ and of a radius for which $x+h\in U$ whenever $\lVert h\rVert<\delta$, which exists because $U$ is open. For $h$ with $0<\lVert h\rVert<\delta$ put $v=T(x+h)-T(x)-Ah$; by Matrix-Vector Product its $k$th coordinate is $T_{k}(x+h)-T_{k}(x)-\sum_{i}A_{ki}h_{i}$, so $|v_{k}|\le(\varepsilon/\sigma_{m})\lVert h\rVert$ for every $k$ and therefore $\lVert v\rVert\le\sigma_{m}\max_{k}|v_{k}|\le\varepsilon\lVert h\rVert$ by the norm inequality recorded at the start. Hence $T$ is differentiable at $x$ with derivative matrix $A$, and the set of points of $U$ at which $T$ is not differentiable is contained in $M$ and so is null.

Finally, at any $x\in U$ at which $T$ is differentiable, claim 1 of The Derivative Is the Jacobian Matrix, and Is Unique says that the entry in row $k$ and column $i$ of the derivative matrix is $\partial_{i}T_{k}(x)$. This completes claim 4.