# A geometric approach to second-order differentiability of convex functions

Daniel Azagra  Departamento de Análisis Matemático y Matemática Aplicada,
Facultad Ciencias Matemáticas, Universidad Complutense, 28040, Madrid, Spain.
<EMAIL_ADDRESS>,  Anthony Cappello  Department of Mathematics, University
of Pittsburgh, 301 Thackeray Hall, Pittsburgh, PA 15260, USA<EMAIL_ADDRESS>and  Piotr Hajłasz  Department of Mathematics, University of Pittsburgh, 301
Thackeray Hall, Pittsburgh, PA 15260, USA<EMAIL_ADDRESS>
###### Abstract.

We show a new, elementary and geometric proof of the classical Alexandrov
theorem about the second order differentiability of convex functions. We also
show new proofs of recent results about Lusin approximation of convex
functions and convex bodies by $C^{1,1}$ convex functions and convex bodies.

###### Key words and phrases:

Convex function, convex body, Alexandrov theorem, Lusin property, Lipschitz
gradient

###### 2020 Mathematics Subject Classification:

26B25, 28A75, 41A30, 52A20, 52A27, 53C45

P.H. was supported by NSF grant DMS-2055171 and by Simons Foundation grant
917582\.

##  1\. Introduction

The aim of this paper is to provide a new, elementary and geometric proof of
the following classical theorem of Alexandrov [1]. For a history of the
theorem and a list of known proofs, see [9].

######  Theorem 1.1.

If $f:\mathbb{R}^{n}\to\mathbb{R}$ is convex, then it is differentiable a.e.
and at almost every point where $f$ is differentiable, there is a symmetric
matrix denoted by $D^{2}f(x)$ such that

$\lim_{y\to
x}\frac{f(y)-f(x)-Df(x)(y-x)-\frac{1}{2}(y-x)^{T}D^{2}f(x)(y-x)}{|y-x|^{2}}=0.$
(1)

Our proof is so simple and geometric in nature that its concept can be
described in just a few sentences. All notation used in the Introduction will
be explained in Section 2.

Consider the set $W(\delta)$, the union of all closed balls of radius
$\delta>0$ contained in the epigraph of $f$. The set $W(\delta)$ is convex and
it is the epigraph of a convex function $g$. Clearly, $g\geq f$. Using
elementary and geometric arguments we show that if $\delta>0$ is sufficiently
small, then the set $W(\delta)$ touches the graph of $f$ along a set that is
large in the sense of measure. More precisely, for every $R>0$ and every
$\varepsilon>0$, there is $\delta>0$ such that

$|\\{x\in B^{n}(0,R):\,f(x)\neq g(x)\\}|<\varepsilon.$

Since the convex set $W(\delta)$ is the union of balls of fixed radius, it is
well known and easy to prove that the boundary of $W(\delta)$ is of class
$C^{1,1}_{\rm loc}$, and hence $g\in C^{1,1}_{\rm loc}$, i.e., the gradient of
$g$ is locally Lipschitz continuous. Since $g\in C^{1,1}_{\rm loc}$, it
follows from the Rademacher theorem that $g$ is twice differentiable almost
everywhere in the classical sense. Now it remains to observe that at almost
all points $x$ such that $f(x)=g(x)$, $f$ is twice differentiable in the sense
of (1). Namely, this is true whenever $x$ is a density point of the set
$\\{f=g\\}$ and $g$ is twice differentiable at $x$. In that case (1) is
satisfied with $D^{2}f(x):=D^{2}g(x)$.

There is also a second version of the Alexandrov theorem which says that the
subdifferential $\partial f$ is differentiable a.e.

######  Theorem 1.2.

If $f:\mathbb{R}^{n}\to\mathbb{R}$ is convex, then for all
$x\in\mathbb{R}^{n}$ where $f$ is twice differentiable as in (1), we have

$\lim_{y\to x}\sup_{\sigma_{y}\in\partial
f(y)}\frac{|\sigma_{y}-Df(x)-D^{2}f(x)(y-x)|}{|y-x|}=0.$ (2)

The usual way to prove Theorem 1.1 is to show Theorem 1.2 first and conclude
Theorem 1.1 from it. In our approach we will prove Theorem 1.1 directly and we
will conclude Theorem 1.2 as a corollary.

The argument described above also leads to new and elementary proofs of the
following recent results [5, Theorem 1.4, Corollary 1.7, Theorem 1.12 and
Corollary 1.13].

######  Theorem 1.3.

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a convex function. Then, for every
measurable set $A\subset\mathbb{R}^{n}$ of finite Lebesgue measure, and for
every $\varepsilon>0$, there exists a convex function $g\in
C^{1,1}(\mathbb{R}^{n})$ such that

$|\\{x\in A:\,f(x)\neq g(x)\\}|<\varepsilon.$

######  Theorem 1.4.

Let $K$ be a convex body in $\mathbb{R}^{n}$. Then for every $\varepsilon>0$,
there is a convex body $W\subset K$, such that $\partial W\in C^{1,1}$ and

$\mathcal{H}^{n-1}(\partial K\triangle\partial W)<\varepsilon.$

In fact, there is $\delta_{o}>0$ such that for every
$\delta\in(0,\delta_{o})$, the set $W$ defined as the union of all closed
balls of radius $\delta$ that are contained in $K$ satisfies the claim of the
theorem.

A convex body is a compact convex set $K\subset\mathbb{R}^{n}$ with non-empty
interior. Notation $A\triangle B$ stands for the symmetric difference of the
sets $A$ and $B$, that is, $A\triangle B:=(A\setminus B)\cup(B\setminus A),$
and $\mathcal{H}^{s}$ denotes the $s$-dimensional Hausdorff measure.

######  Theorem 1.5.

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a convex function, and assume that
$f\not\in C^{1,1}_{{\rm loc}}(\mathbb{R}^{n})$. Then the following conditions
are equivalent:

  1. (1)

For every $\varepsilon>0$ there exists a convex function $g\in C^{1,1}_{\rm
loc}(\mathbb{R}^{n})$ such that

$|\\{x\in\mathbb{R}^{n}:f(x)\neq g(x)\\}|<\varepsilon.$

  2. (2)

The function $f$ is essentially coercive.

Moreover, if $f$ is essentially coercive, we can find $g$ satisfying $g\geq
f$.

We call a convex function $f:\mathbb{R}^{n}\to\mathbb{R}$ essentially coercive
if there exists a linear function $\ell:\mathbb{R}^{n}\to\mathbb{R}$ such that
$\lim_{|x|\to\infty}\left(f(x)-\ell(x)\right)=\infty$; this is equivalent to
saying that the epigraph of $f$ does not contain lines, see [7, Theorem 1.11].
Here and in what follows by a line we mean a set isometric to $\mathbb{R}$ so
half-line is not a line.

######  Theorem 1.6.

Let $S$ be a convex hypersurface of $\mathbb{R}^{n}$, and assume that $S$ is
not of class $C^{1,1}_{{\rm loc}}$. Then the following assertions are
equivalent:

  1. (1)

For every $\varepsilon>0$ there exists a convex hypersurface $S_{\varepsilon}$
of $\mathbb{R}^{n}$ of class $C^{1,1}_{\rm loc}$ such that
$\mathcal{H}^{n-1}\left(S\triangle S_{\varepsilon}\right)<\varepsilon$.

  2. (2)

$S$ does not contain any line.

We call the boundary $\partial W$ of a closed convex set $W$ with nonempty
interior (not necessarily bounded) a convex hypersurface, and we say that it
is of class $C^{1,1}_{\rm loc}$ if it is locally a graph of a $C^{1,1}$
function (if the set $W$ is unbounded, we will say that $W$ is an unbounded
convex body).

######  Remark 1.7.

It follows from the proof that if $S=\partial W$, where $W$ is a (possibly
unbounded) convex body that contains no lines, then there exists a (possibly
unbounded) convex body $W_{\varepsilon}\subset W$ such that
$S_{\varepsilon}:=\partial W_{\varepsilon}\in C^{1,1}_{\textrm{loc}}$ and
$\mathcal{H}^{n-1}\left(S\triangle S_{\varepsilon}\right)<\varepsilon$.

From Theorem 1.6 we will also deduce the following new generalization of
Theorem 1.5 for convex functions defined on arbitrary open convex subsets of
$\mathbb{R}^{n}$.

######  Theorem 1.8.

Let $U\subset\mathbb{R}^{n}$ be open and convex, and let $f:U\to\mathbb{R}$ be
a convex function, such that $f\not\in C^{1,1}_{\rm loc}(U)$. Then, the
following statements are equivalent:

  1. (1)

For every $\varepsilon>0$ there exists a convex function $g\in C^{1,1}_{\rm
loc}(U)$ such that

$|\\{x\in U:f(x)\neq g(x)\\}|<\varepsilon.$ (3)

  2. (2)

The graph of $f$ does not contain any line of $\mathbb{R}^{n+1}$.

Moreover, if the graph of $f$ contains no lines, we can find $g$ satisfying
$g\geq f$.

######  Remark 1.9.

It was recently proved in [4] that if $f:U\to\mathbb{R}$ is locally strongly
convex, then there is a locally strongly convex function $g\in C^{2}(U)$ that
satisfies (3) (and other estimates). The proof is however, much more
difficult.

The original proofs of Theorems 1.3, 1.4 and 1.5 used the Whitney extension
theorem for convex functions [6, 8, 3], and the Alexandrov Theorem 1.1. Our
proofs presented here are elementary and avoid these tools. As explained
above, the proofs are based on a simple geometric idea that is also used in
our proof of Alexandrov’s theorem.

We will prove Theorem 1.4 first and we will use it as a main tool in the
proofs of Theorems 1.1 and 1.3. Indeed, the brief description of the proof of
Theorem 1.1 presented above is based on the approximation of the epigraph of
$f$ by the convex set $W(\delta)$ of class $C^{1,1}_{\rm loc}$ and this is
strictly related to Theorem 1.4.

Except Section 7, our exposition is elementary and self-contained. We have
made an effort to make it accessible to anyone with basic knowledge of real
analysis, and no knowledge in convex analysis is required.

The paper is structured as follows. In Section 2 we fix notation and recall
basic definitions and facts needed to understand the paper. All results
mentioned in this section are well known. In Section 3 we prove Theorem 1.4
and then we use it to prove Corollary 3.10 which is a version of Theorem 1.3.
This corollary will play a central role in the proofs of Theorems 1.1, 1.3 and
1.5. Theorems 1.1 and 1.3 are proved in Sections 4 and 6 respectively. In
Section 5 we prove Theorem 1.2 as a direct consequence of Theorem 1.1. This
proof is independent of all other sections of the paper and it can be read
independently. In Section 7 we present the proofs of Theorems 1.5, 1.6, and
1.8.

We made an effort to make different parts of the paper as independent as
possible. Section 3 is needed in Sections 4, 6 and 7, but the content in
Sections 4, 6 and 7 of the paper stands alone and is not dependent on one
another. Similarly Section 5 is independent of any other part of the paper.

##  2\. Preliminaries

In this brief section we will explain notation and basic facts needed in the
paper. This section will also clarify necessary prerequisites. By no means the
definitions and facts presented here are detailed. The reader may find missing
details in standard textbooks.

Balls in $\mathbb{R}^{n}$ are denoted by $B(x,r)$ or $B^{n}(x,r)$. The unit
sphere in $\mathbb{R}^{n}$ that is centered at the origin is denoted by
$\mathbb{S}^{n-1}$. The interior of a set $A$ is denoted by
$\operatorname{int}A$. An interval in $\mathbb{R}^{n}$ with endpoints
$x,y\in\mathbb{R}^{n}$ is denoted by $[x,y]$. The scalar product of vectors
$u,v\in\mathbb{R}^{n}$ is denoted by $\langle u,v\rangle$.

The Lebesgue measure of $A\subset\mathbb{R}^{n}$ is denoted by $|A|$. We say
that $x\in\mathbb{R}^{n}$ is a density point of a measurable set
$A\subset\mathbb{R}^{n}$ if $\frac{|A\cap B(x,r)|}{|B(x,r)|}\to 1$ as $r\to
0^{+}$. It follows from the Lebesgue differentiation theorem that almost all
points $x\in A$ are density points of $A$.

The Hausdorff measure is denoted by $\mathcal{H}^{s}$. It follows from the
definition that if $f$ is $L$-Lipschitz, then $\mathcal{H}^{s}(f(A))\leq
L^{s}\mathcal{H}^{s}(A)$. If $A\subset\mathbb{R}^{n}$, $\lambda>0$ and
$\lambda A=\\{\lambda x:\,x\in A\\}$ is the dilation of $A$ by the factor
$\lambda$, then $\mathcal{H}^{s}(\lambda A)=\lambda^{s}\mathcal{H}^{s}(A)$.
$\mathcal{H}^{n}$ coincides with the Lebesgue measure in $\mathbb{R}^{n}$.

We say that $f\in C^{1,1}(U)$ ($f\in C^{1,1}_{\rm loc}(U)$), if
$U\subset\mathbb{R}^{n}$ is open, $f\in C^{1}(U)$, and $Df$ is Lipschitz
(locally Lipschitz) continuous on $U$. If $f\in C^{1,1}(B^{n}(0,R))$, then it
follows that

$|f(y)-f(x)-Df(x)(y-x)|\leq M|y-x|^{2}\quad\text{for all }x,y\in B^{n}(0,R),$
(4)

where $M$ is the Lipschitz constant of $Df$. Indeed, we can write
$f(y)-f(x)=Df(\xi)(y-x)$ for some $\xi\in[x,y]$ and (4) follows. This
inequality implies that if $f\in C^{1,1}_{\rm loc}(U)$, where
$U\subset\mathbb{R}^{n}$ is open, then

$f(y)=f(x)+Df(x)(y-x)+O(|y-x|^{2})\quad\text{for all }x,y\in U.$ (5)

We say that the boundary of a bounded domain $U\subset\mathbb{R}^{n}$ is of
class $C^{1,1}$ if it is locally a graph of a $C^{1,1}$ function.

We use notation $\nabla f(x)$ for the gradient vector while $Df(x)$ is the
linear derivative. With this notation we have $Df(x)v=\langle\nabla
f(x),v\rangle$.

If $W\subset\mathbb{R}^{n}$ is a closed convex set, then it is easy to see
that for every $x\in\mathbb{R}^{n}$, there is a unique point denoted by
$\pi_{W}(x)$ such that

$\pi_{W}(x)\in
W\qquad\text{and}\qquad|x-\pi_{W}(x)|=\operatorname{dist}(x,W).$ (6)

Clearly, if $x\not\in W$, then $\pi_{W}(x)\in\partial W$. The next result is
well known see e.g., [11, Proposition 3.1.3] or [16, Theorem 1.2.1].

######  Lemma 2.1.

$\pi_{W}:\mathbb{R}^{n}\to W$ is $1$-Lipschitz.

The convex hull of a set $A\subset\mathbb{R}^{n}$ (defined as the intersection
of all convex sets containing $A$, or equivalently, as the set of all convex
combinations of points of $A$) is denoted by $\operatorname{co}(A)$. Every
closed and convex set $W\subset\mathbb{R}^{n}$ is the intersection of all
closed half-spaces that contain $W$. In fact, for every $x\in\partial W$ there
is a half-space $H_{x}$ such that $W\subset H_{x}$ and $x\in T_{x}\cap W$,
where $T_{x}=\partial H_{x}$. The hyperplane $T_{x}$ is called a hyperplane
supporting $W$ at $x$. Thus for every $x\in\partial W$, there is a hyperplane
supporting $W$ at $x$, but such a hyperplane is not necessarily unique. This
implies that if $U\subset\mathbb{R}^{n}$ is open and convex and
$f:U\to\mathbb{R}$ is convex, then for every $x\in U$ there is
$v\in\mathbb{R}^{n}$ such that $f(y)\geq f(x)+\langle v,y-x\rangle$ for all
$y\in U$. Indeed, on the right hand side we have an equation of the supporting
hyperplane of the convex epigraph $\operatorname{epi}(f)=\\{(x,y)\in
U\times\mathbb{R}:\,x\in U,\ y\geq f(x)\\}$. The set of all such $v$ is
denoted by $\partial f(x)$ and called the subdifferential of $f$ at $x$. Thus
$\partial f(x)\neq\varnothing$ for any $x\in U$. If in addition $f$ is
differentiable at $x_{o}$, then $\partial f(x_{o})=\\{\nabla f(x_{o})\\}$
i.e., $f(y)\geq f(x_{o})+Df(x_{o})(y-x_{o})$ meaning that the tangent
hyperplane to the graph of $f$ at $x_{o}$ is the unique hyperplane supporting
the epigraph of $f$ at $(x_{o},f(x_{o}))$. Convex functions are locally
Lipschitz continuous and hence they are differentiable a.e. by the Rademacher
theorem, so $\partial f(x)=\\{\nabla f(x)\\}$ for almost all $x\in U$. In fact
we will prove the a.e. differentiability of convex functions directly and
without any reference to the Rademacher theorem, see Corollary 3.6 and Remark
3.7, but we will need the Rademacher theorem in the proof of Theorem 1.1,
because we will need to know that the gradient of a convex function $g\in
C^{1,1}$ is differentiable a.e.

##  3\. Proof of Theorem 1.4

We will precede the proof with auxiliary results.

For a convex body $K\subset\mathbb{R}^{n}$ and $r>0$ we define the inner
parallel convex body by

$K_{r}:=\\{x\in K:\,\operatorname{dist}(x,\partial K)\geq r\\}.$

######  Lemma 3.1.

$K_{r}$ is convex for any $r>0$.

###### Proof.

Let $x,y\in K_{r}$. We need to show that $[x,y]\subset K_{r}$. Clearly,
$\mkern 1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu(x,r),\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu(y,r)\subset K$ and for
any $z\in[x,y]$, $\mkern 1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern
1.5mu(z,r)\subset\operatorname{co}(\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu(x,r)\cup\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu(y,r))\subset K,$ so
$\operatorname{dist}(z,\partial K)\geq r$, $z\in K_{r}$, and hence
$[x,y]\subset K_{r}$. ∎

Let $r_{o}=\sup_{x\in K}\operatorname{dist}(x,\partial K)$. Clearly
$K_{r}=\varnothing$ for $r>r_{o}$. $K_{r_{o}}\neq\varnothing$, but it has
empty interior. However, for $r\in(0,r_{o})$, $K_{r}$ has non-empty interior,
so $K_{r}$ is a convex body only for $r\in(0,r_{o})$.

For a convex body $K$ and $r>0$ we also define

$K(r):=\bigcup\\{\mkern 1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern
1.5mu(x,r):\,\mkern 1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern
1.5mu(x,r)\subset K\\}.$ (7)

It is easy to see that $K(r)$ is convex and compact (it can be empty).
Moreover, if $K$ contains a ball of radius $r_{o}$, then for any
$r\in(0,r_{o}]$, $K(r)$ has non-empty interior and hence $K(r)$ is a convex
body.

######  Lemma 3.2.

If a convex body $K$ contains a ball of radius $r_{o}$, then for all
$r\in(0,r_{o})$, $K_{r}$ is a convex body, and

$\mathcal{H}^{n-1}(\partial K_{r})\leq\mathcal{H}^{n-1}(\partial K\cap\partial
K(r)).$ (8)

###### Proof.

Clearly, for $r\in(0,r_{o})$, $K_{r}$ has non-empty interior, so it is a
convex body by Lemma 3.1. Observe that (see (6))

$\pi_{K_{r}}(\partial K\cap\partial K(r))=\partial K_{r}.$ (9)

Indeed, if $z\in\partial K_{r}$, then there is $x\in\partial K$, such that
$|x-z|=r$. Therefore, $x\in\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu(z,r)\subset K$, and
hence $x\in K(r)$. Thus, $x\in\partial K\cap\partial K(r)$,
$|x-z|=r\geq\operatorname{dist}(x,K_{r})$, and hence $z=\pi_{K_{r}}(x)$. Now,
(8) follows from (9) and the fact that $\pi_{K_{r}}$ is $1$-Lipschitz (Lemma
2.1). ∎

The next beautiful result is due to McMullen [15]. While it can be concluded
from Alexandrov’s theorem, we present here a direct and surprisingly
elementary proof which is a small modification of McMullen’s argument. In
fact, Lemma 3.3 will play an important role in our proof of Alexandrov’s
theorem.

######  Lemma 3.3.

If $K\subset\mathbb{R}^{n}$ is a convex body, then $\lim_{r\to
0^{+}}\mathcal{H}^{n-1}(\partial K\setminus\partial K(r))=0.$

######  Remark 3.4.

Lemma 3.3 has the following geometric interpretation: for almost all
$x\in\partial K$, there is a closed ball $\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu\subset K$ touching the
boundary of $K$ at $x$, i.e., $x\in\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu$.

###### Proof.

Without loss of generality we may assume that $\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu(0,r_{o})\subset K$. If
$r\in(0,r_{o})$, then $0$ belongs to the interior of $K_{r}$. For $\lambda>0$
we define

$\lambda K_{r}:=\\{\lambda z:\,z\in K_{r}\\},$

that is, $\lambda K_{r}$ is a dilation of $K_{r}$. For $r\in(0,r_{o})$, let

$\lambda(r):=\inf\\{\lambda>0:\,K\subset\lambda K_{r}\\}.$

Clearly, $K\subset\lambda(r)K_{r}$. It is easy to see that the function
$r\mapsto\lambda(r)$ is non-decreasing and $\lambda(r)\to 1$ as $r\to 0^{+}$.
Indeed, for any $\varepsilon>0$,
$(1+\varepsilon)^{-1}K\subset\operatorname{int}K$, and hence
$\delta:=\operatorname{dist}((1+\varepsilon)^{-1}K,\partial K)>0$, so for all
$r\in(0,\delta]$

$(1+\varepsilon)^{-1}K\subset K_{r},\qquad\text{i.e.,}\qquad
K\subset(1+\varepsilon)K_{r}.$

In other words $1\leq\lambda(r)\leq 1+\varepsilon$ for all $0<r\leq\delta$
proving that $\lambda(r)\to 1$ as $r\to 0^{+}$.

It is easy to see that $\pi_{K}(\partial(\lambda(r)K_{r}))=\partial K$ (see
(6)). Indeed, if $x\in\partial K$ and $\nu(x)$ is the outer unit normal vector
to a supporting hyperplane of $K$ at $x$, then there is $t\geq 0$ such that
$z:=x+t\nu(x)\in\partial(\lambda(r)K_{r})$ and it easily follows that
$\pi_{K}(z)=x$. Since $\pi_{K}$ is $1$-Lipschitz and it maps
$\partial(\lambda(r)K_{r})$ onto $\partial K$, we have that

$\begin{split}\mathcal{H}^{n-1}(\partial
K)&\leq\mathcal{H}^{n-1}(\partial(\lambda(r)K_{r}))=\lambda(r)^{n-1}\mathcal{H}^{n-1}(\partial
K_{r})\leq\lambda(r)^{n-1}\mathcal{H}^{n-1}(\partial K\cap\partial K(r))\\\
&\leq\lambda(r)^{n-1}\mathcal{H}^{n-1}(\partial
K)\to\mathcal{H}^{n-1}(\partial K)\quad\text{as }r\to 0^{+}.\end{split}$

Therefore, $\mathcal{H}^{n-1}(\partial K\cap\partial
K(r))\to\mathcal{H}^{n-1}(\partial K)$, as $r\to 0^{+}$. This completes the
proof of Lemma 3.3. ∎

######  Lemma 3.5.

Let $f,g:B^{n}(0,R)\to\mathbb{R}$ be convex functions. If $g\in C^{1,1}$,
$f\leq g$ and $f(x)=g(x)$ for some $x\in B^{n}(0,R)$, then $f$ is
differentiable at $x$, $Df(x)=Dg(x)$ and

$f(y)=f(x)+Df(x)(y-x)+O(|y-x|^{2}).$ (10)

###### Proof.

If $v\in\partial f(x)$, then clearly, $v\in\partial g(x)$ and hence $v=\nabla
g(x)$. Therefore, the result follows from the estimate

$f(x)+\langle\nabla g(x),y-x\rangle\leq f(y)\leq g(y)=f(x)+\langle\nabla
g(x),y-x\rangle+O(|y-x|^{2}),$

where in the last equality we used (5) and the fact that $g(x)=f(x)$. ∎

######  Corollary 3.6.

If $f:\mathbb{R}^{n}\to\mathbb{R}$ is convex, then it is differentiable a.e.
Moreover

$f(y)=f(x)+Df(x)(y-x)+O(|y-x|^{2})\qquad\text{for almost all
$x\in\mathbb{R}^{n}$.}$ (11)

###### Proof.

Since the boundary of a ball is parameterized by a smooth convex function,
Lemma 3.5 implies (11) whenever there is a ball in the epigraph of $f$ that
touches the graph of $f$ at $(x,f(x))$ and it follows from Lemma 3.3 that it
is true for almost all $x$. ∎

######  Remark 3.7.

Note that the proof of Corollary 3.6 does not use Rademacher’s theorem.
Moreover, the estimate (11), is stronger than the a.e. differentiability of
$f$ that would follow from an application of Rademacher’s theorem. We will not
need Corollary 3.6 in this paper.

The following result, was proven in a more general form in the unpublished
work [14, Theorem 1, p. 32]. It is also mentioned without any proof or
reference in [13]. Although a detailed proof can be found in [10, Proposition
2.4.3], the origin of the result is not referenced in this work.

######  Lemma 3.8.

A convex body $W$ has $C^{1,1}$ boundary if and only if there is $r>0$ such
that $W=W(r)$.

######  Remark 3.9.

In other words a convex body $W$ has boundary of class $C^{1,1}$ if and only
if there is $r>0$ such that $W$ is the union of closed balls of radius $r$.

We will only prove the implication from right to left, that is we will prove
that if $W=W(r)$, then $\partial W$ is of class $C^{1,1}$. This is the only
implication that we need in the proof of Theorem 1.4. For the proof of the
implication from left to right, see [10, Proposition 2.4.3]. We will present
two proofs. The first proof is sketched only and it uses the implicit function
theorem. The second one is detailed and it does not use the implicit function
theorem.

###### First proof.

It is very elementary and easy to prove that if $K\subset\mathbb{R}^{n}$ is
compact and convex, then the function
$d^{2}_{K}(x)=\operatorname{dist}(x,K)^{2}$ is differentiable and $\nabla
d^{2}_{K}(x)=2(x-\pi_{K}(x))$, see [11, p. 181]. Since the function $\pi_{K}$
is Lipschitz by Lemma 2.1, we have that $d_{K}^{2}\in C^{1,1}$ and all points
in $\mathbb{R}^{n}\setminus K$ are regular so for $t>0$,
$\\{x:\,\operatorname{dist}(x,K)=t\\}=(d_{K}^{2})^{-1}(t^{2})$ is a
$C^{1,1}$-submanifold of $\mathbb{R}^{n}$ and hence it is locally a graph of a
$C^{1,1}$ function by the implicit function theorem. It remains to observe
that $\partial
W(r)=\\{x\in\mathbb{R}^{n}:\,\operatorname{dist}(x,W_{r})=r\\}$. ∎

###### Second proof.

Thus, we assume that for each $p\in\partial W$ there is $h(p)\in W$ such that
$p\in\mkern 1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern
1.5mu(h(p),r)\subset W$. It follows that the hyperplane $T_{p}$ tangent to the
ball $\mkern 1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu(h(p),r)$ at
$p$ is the unique hyperplane supporting $W$ at $p$.

Note that $\operatorname{dist}(h(p),\partial W)=r$ implies that $h(p)\in
W_{r}$, so $|p-h(p)|=r=\operatorname{dist}(p,W_{r})$, and hence
$h(p)=\pi_{W_{r}}(p)$ (see (6)).

The inner unit normal vector to $T_{p}$ is given by

$\nu(p)=\frac{h(p)-p}{r}=\frac{\pi_{W_{r}}(p)-p}{r}$

and Lemma 2.1 implies that the function $\nu:\partial W\to\mathbb{S}^{n-1}$ is
Lipschitz continuous:

$|\nu(p)-\nu(q)|\leq\frac{|\pi_{W_{r}}(p)-\pi_{W_{r}}(q)|+|p-q|}{r}\leq\frac{2}{r}|p-q|.$

This in turn, implies that the boundary $\partial W$ is of class $C^{1,1}$.
Indeed, choose any point $p_{o}\in\partial W$ and choose a Euclidean
coordinate system $(x_{1},\ldots,x_{n})=(x^{\prime},x_{n})$ such that
$p_{o}=0$ and $T_{p_{o}}=\\{x_{n}=0\\}$. Then $\partial W$ in a neighborhood
$U=B^{n-1}(0,\frac{r}{2})$ of $p_{o}=0$ is a graph of a function
$x_{n}=f(x^{\prime})$ i.e.,
$p(x^{\prime}):=(x^{\prime},f(x^{\prime}))\in\partial W$. Since for
$x^{\prime}\in U$, the graph of $f$ lies above $T_{p(x^{\prime})}$ and below
$\mkern 1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern
1.5mu(h(p(x^{\prime})),r)$, it follows from geometric considerations (as in
the proof of Corollary 3.6) that $f$ is differentiable at $x^{\prime}$ and
$T_{p(x^{\prime})}$ is the tangent hyperplane to the graph of $f$ at
$p(x^{\prime})$. Note also that $|\nabla f|\leq M$ on $U$ for some $M>0$,
because the tangent hyperplane to the graph of $f$ cannot intersect with
$B(h(0),r)$. It remains to show that $\nabla f$ is Lipschitz continuous in
$U$.

The inner unit normal vector in terms of $\nabla f$ is given by

$\nu(p(x^{\prime}))=\frac{(-\nabla f(x^{\prime}),1)}{\sqrt{1+|\nabla
f(x^{\prime})|^{2}}},\qquad\text{so}\qquad\pi(\nu(p(x^{\prime}))=\frac{-\nabla
f(x^{\prime})}{\sqrt{1+|\nabla f(x^{\prime})|^{2}}},$

where $\pi:\mathbb{R}^{n}\to\mathbb{R}^{n-1}$,
$\pi(x^{\prime},x_{n})=x^{\prime}$ is the orthogonal projection. Since
$\Psi(\Phi(z))=z$ for all $z\in\mathbb{R}^{n-1}$, where
$\Psi(z)=-z/\sqrt{1-|z|^{2}}$ and $\Phi(z)=-z/\sqrt{1+|z|^{2}}$, it follows
that

$\nabla f(x^{\prime})=\Psi\left(\frac{-\nabla f(x^{\prime})}{\sqrt{1+|\nabla
f(x^{\prime})|^{2}}}\right)=\Psi(\pi(\nu(x^{\prime},f(x^{\prime}))))\quad\text{for
$x^{\prime}\in U$.}$

This proves Lipschitz continuity of $\nabla f$ in $U$, as a composition of
Lipschitz functions. The only issue could be the Lipschitz continuity of
$\Psi$: it is a smooth function defined for $|z|<1$, but it is unbounded.
However, this does not cause any problems here, because

$\left|\frac{-\nabla f(x^{\prime})}{\sqrt{1+|\nabla
f(x^{\prime})|^{2}}}\right|\leq\frac{M}{\sqrt{1+M^{2}}}<1.$

∎

###### Proof of Theorem 1.4.

Let $K\subset\mathbb{R}^{n}$ be a convex body. According to Lemma 3.3, for
every $\varepsilon>0$ there is $\delta_{o}>0$ such that for any
$\delta\in(0,\delta_{o})$, $\mathcal{H}^{n-1}(\partial K\setminus\partial
K(\delta))<\varepsilon/2$. Since $K(\delta)\subset K$, it is easy to see that
$\pi_{K(\delta)}(\partial K)=\partial K(\delta)$, so $\pi_{K(\delta)}(\partial
K\setminus\partial K(\delta))=\partial K(\delta)\setminus\partial K$ and Lemma
2.1 yields $\mathcal{H}^{n-1}(\partial K(\delta)\setminus\partial
K)\leq\mathcal{H}^{n-1}(\partial K\setminus\partial K(\delta))$. Therefore,
$\mathcal{H}^{n-1}(\partial K\triangle\partial K(\delta))<\varepsilon$. Since
the boundary of $K(\delta)$ is of class $C^{1,1}$ by Lemma 3.8, $W:=K(\delta)$
satisfies the claim of the theorem. ∎

The next result is a direct consequence of Theorem 1.4 and it is a version of
Theorem 1.3. We will use Corollary 3.10 in the proofs of Theorems 1.1, 1.3,
and 1.5.

######  Corollary 3.10.

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a convex function. Then for every $R>0$
and $\varepsilon>0$, there is a convex function $g\in C^{1,1}(B^{n}(0,R))$
such that $g\geq f$ and

$|\\{x\in B^{n}(0,R):\,f(x)\neq g(x)\\}|<\varepsilon.$ (12)

###### Proof.

Let $M:=\sup_{\mkern 1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern
1.5mu^{n}(0,2R)}f(x)$ and define

$W:=\\{(x,y)\in\mkern 1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern
1.5mu^{n}(0,2R)\times\mathbb{R}:\,f(x)\leq y\leq M+2R\\}.$

That is, $W$ is an $(n+1)$-dimensional convex body bounded by the graph of
$f$, the cylinder $\partial B^{n}(0,2R)\times\mathbb{R}$ and the hyperplane
$y=M+2R$. According to Lemma 3.3, there is $\delta<R$ such that

$\mathcal{H}^{n}(\partial W\setminus\partial W(\delta))<\varepsilon.$

Since $W(\delta)$ is the union of closed balls of radius $\delta<R$ that are
contained in $W$, it follows that

$\mkern 1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern
1.5mu^{n}(0,2R)\times\\{M+R\\}\subset W(\delta),$

i.e., the intersection of $W(\delta)$ with the hyperplane $y=M+R$ is an
$n$-dimensional closed ball of radius $2R$. Thus, if
$\pi:\mathbb{R}^{n+1}\to\mathbb{R}^{n}$ is the orthogonal projection,
$\pi(W(\delta))=\mkern 1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern
1.5mu^{n}(0,2R)$, and hence for $x\in\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu^{n}(0,2R)$, we can
define

$g(x):=\inf\\{y:\,(x,y)\in W(\delta)\\}.$

That is, the function $g:\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu^{n}(0,2R)\to\mathbb{R}$
parametrizes the bottom part of the boundary of $W(\delta)$. According to
Lemma 3.8, the boundary of $W(\delta)$ is of class $C^{1,1}$ so $g\in
C^{1,1}_{\rm loc}(B^{n}(0,2R))$ and hence $g$ is a convex function in
$C^{1,1}(B^{n}(0,R))$. Since $W(\delta)$ is contained in $W$ and hence in the
epigraph of $f$, it follows that $g\geq f$.

Observe that

$\\{x\in{B}^{n}(0,R):\,f(x)\neq g(x)\\}\subset\pi(\partial W\setminus\partial
W(\delta))$

and hence

$|\\{x\in B^{n}(0,R):\,f(x)\neq g(x)\\}|\leq|\pi(\partial W\setminus\partial
W(\delta))|\leq\mathcal{H}^{n}(\partial W\setminus\partial
W(\delta))<\varepsilon,$

because the orthogonal projection does not increase the Hausdorff measure and
$\mathcal{H}^{n}$ coincides with the Lebesgue measure in $\mathbb{R}^{n}$. ∎

##  4\. Proof of Theorem 1.1

######  Lemma 4.1.

Suppose that $f,g:B^{n}(0,R)\to\mathbb{R}$ are convex, $f\leq g$, and $g\in
C^{1,1}(B^{n}(0,R))$. Then for almost all $x_{o}\in\\{f=g\\}$ we have

$f(x)=f(x_{o})+Df(x_{o})(x-x_{o})+\frac{1}{2}(x-x_{o})^{T}D^{2}g(x_{o})(x-x_{o})+o(|x-x_{o}|^{2}).$
(13)

######  Remark 4.2.

Note that $D^{2}g(x_{o})$ in (13) is not a typo. Also, we do not need the
assumption that $g$ is convex or $C^{1,1}$. With a small modification, the
proof works under the assumption that $f\leq g\in C^{1}$ and $Dg$ is
differentiable at $x_{o}$.

###### Proof.

It follows from Lemma 3.5 that $f$ is differentiable at every point of the set
$\\{f=g\\}$ and that $Df=Dg$ in $\\{f=g\\}$. Since $Dg$ is Lipschitz
continuous, $Dg$ is differentiable a.e. by Rademacher’s theorem. Therefore, it
suffices to prove the result whenever $x_{o}\in\\{f=g\\}$ is a density point
of that set and $Dg$ is differentiable at $x_{o}$.

To simplify notation, without loss of generality, we may assume that
$x_{o}=0$, and we need to prove that

$f(x)-f(0)-Df(0)x-\frac{1}{2}x^{T}D^{2}g(0)x=o(|x|^{2}).$

Since $f(0)=g(0)$ and $Df(0)=Dg(0)$, the left hand side equals

$(f(x)-g(x))+\left(g(x)-g(0)-Dg(0)x-\frac{1}{2}x^{T}D^{2}g(0)x\right)=(f(x)-g(x))+o(|x|^{2}).$

We used here the fact that $g$ is twice differentiable at $0$ (Taylor’s
theorem with the Peano remainder). Thus it remains to show that
$g(x)-f(x)=o(|x|^{2})$.

Since $0$ is a density point of the set $\\{f=g\\}$, for any $x$ we can find
$y\in\\{f=g\\}$ such that $|x-y|=o(|x|)$. For if not, there is $\varepsilon>0$
and $x_{k}\to 0$ such that
$B(x_{k},\varepsilon|x_{k}|)\cap\\{f=g\\}=\varnothing$ and that contradicts
the fact that $0$ is a density point of $\\{f=g\\}$.

Clearly, $f(y)=g(y)$ and $Df(y)=Dg(y)$ by Lemma 3.5. Therefore,

$f(x)\geq f(y)+Df(y)(x-y)=g(y)+Dg(y)(x-y),$

where the inequality is a consequence of convexity of $f$. Since $f\leq g$,
the above inequality and (4) yield

$0\leq g(x)-f(x)\leq g(x)-g(y)-Dg(y)(x-y)\leq M|x-y|^{2}=o(|x|^{2}).$

The proof is complete. ∎

###### Proof of Theorem 1.1.

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be convex. Let $R>0$ and $\varepsilon>0$
and let $g$ be as in Corollary 3.10. It follows from Lemma 4.1 that for almost
all $x\in\\{f=g\\}$, (1) is satisfied with $D^{2}f(x):=D^{2}g(x)$. Hence (1)
holds true in $B(0,R)$ outside a set of measure less than $\varepsilon$. Since
it is true for any $R>0$ and $\varepsilon>0$, it follows that (1) is satisfied
almost everywhere. ∎

##  5\. Proof of Theorem 1.2

If $f$ is twice differentiable at $0$ as in (1), then we have

$f(x)=f(0)+Df(0)x+\frac{1}{2}x^{T}D^{2}f(0)x+R(x)=f(0)+Df(0)x+\langle
Ax,x\rangle+R(x),$

where $A=\frac{1}{2}D^{2}f(0)$ and $R(x)=o(|x|^{2})$. Note that

$a(r):=\sup_{0<|x|\leq 2r}\frac{|R(x)|}{|x|^{2}}\to 0\qquad\text{as $r\to
0^{+}$.}$

Moreover,

$|R(x)|\leq a\Big{(}\frac{|x|}{2}\Big{)}\,|x|^{2}\leq a(|x|)|x|^{2}.$

###### Proof of Theorem 1.2.

Let $f$ be twice differentiable at $x$ as in (1). We need to prove (2).
Without loss of generality we may assume that $x=0$, and hence we need to
prove that

$\lim_{x\to 0}\frac{\sigma_{x}-Df(0)-D^{2}f(0)x}{|x|}=0\quad\text{for any
}\sigma_{x}\in\partial f(x).$

For $x,y\neq 0$, we have

$f(x)=f(0)+Df(0)x+\langle Ax,x\rangle+R(x),\quad f(y)=f(0)+Df(0)y+\langle
Ay,y\rangle+R(y).$

Since $f(x)+\langle\sigma_{x},y-x\rangle\leq f(y)$, we have

$\langle\sigma_{x},y-x\rangle\leq f(y)-f(x)=Df(0)(y-x)+\langle
A(x+y),y-x\rangle+R(y)-R(x).$

We used here the fact that $A$ is symmetric and hence $\langle
Ax,y\rangle=\langle Ay,x\rangle$. Let

$y=x+w,\quad\text{where}\quad w=\sqrt{a(|x|)}\,|x|z,\ |z|=1.$

Then

$\langle\sigma_{x},w\rangle\leq Df(0)w+\langle A(2x+w),w\rangle+R(y)-R(x),$
$\langle\sigma_{x}-Df(0)-2Ax,w\rangle\leq\langle Aw,w\rangle+R(y)-R(x).$

If $|x|$ is sufficiently small, then $a(|x|)\leq 1$ and hence $|w|\leq|x|$, so
$|y|\leq 2|x|$. Therefore,

$|R(y)|\leq a\Big{(}\frac{|y|}{2}\Big{)}\,|y|^{2}\leq
4a(|x|)|x|^{2},\qquad|R(y)-R(x)|\leq 5a(|x|)|x|^{2}.$

Taking the supremum over all $z$ with $|z|=1$ we get

$|\sigma_{x}-Df(0)-2Ax|\sqrt{a(|x|)}|x|\leq|A|a(|x|)|x|^{2}+5a(|x|)|x|^{2},$

and hence

$\frac{|\sigma_{x}-Df(0)-2Ax|}{|x|}\leq(|A|+5)\sqrt{a(|x|)}\to 0\quad\text{as
$x\to 0$.}$

Since $2A=D^{2}f(0)$, the result follows. ∎

##  6\. Proof of Theorem 1.3

One of the differences between Corollary 3.10 and Theorem 1.3 is that the
function $g$ in Corollary 3.10 is defined on the ball $B^{n}(0,R)$ only and
the main step in the proof of Theorem 1.3 will be to show that the function
$g$ can be extended from a ball $B^{n}(0,R-\delta)$ to a convex function of
class $C^{1,1}(\mathbb{R}^{n})$. We will do it by gluing the function $g$ with
a quadratic function of the form $a|x|^{2}-b$ and we need to know how to glue
convex functions while maintaining their smoothness.

The maximum of two convex functions

$\max\\{u,v\\}=\frac{u+v+|u-v|}{2}$

is convex, but even if $u,v\in C^{\infty}$, the maximum $\max\\{u,v\\}$ need
not be $C^{1}$. To overcome this difficulty, we will use the so called smooth
maximum that was introduced in [2].

Let $\theta\in C^{\infty}(\mathbb{R})$ be such that $\theta(t)=|t|$ if and
only if $|t|\geq 1$, $\theta$ is convex, $\theta(t)=\theta(-t)$ for all $t$,
and $1$-Lipschitz.

It easily follows that $\theta(t)>0$ for all $t$ and $|\theta^{\prime}(t)|<1$
if and only if $|t|<1$. Then, we define the smooth maximum function
$\mathcal{M}:\mathbb{R}^{2}\to\mathbb{R}$ as,

$\mathcal{M}(x,y):=\frac{x+y+\theta(x-y)}{2}.$

It is easy to see that $\mathcal{M}$ is smooth, convex and

$\mathcal{M}(x,y)=\max\\{x,y\\}\quad\text{whenever}\quad|x-y|\geq 1.$ (14)

It is also not difficult to prove that $\mathcal{M}(x,y)$ is non-decreasing in
$x$ and $y$, because partial derivatives of $\mathcal{M}$ are non-negative,
see [2, Lemma 2.1(viii)]. This observation and convexity of $\mathcal{M}$
yield (see [2, Proposition 2.2(i)])

######  Lemma 6.1.

If $u,v:U\to\mathbb{R}$ are convex functions defined in an open convex set
$U\subset\mathbb{R}^{n}$, then $\mathcal{M}(u,v):U\to\mathbb{R}$ is convex.

It is also obvious that if $u,v\in C^{1,1}_{\rm loc}(U)$, then
$\mathcal{M}(u,v)\in C^{1,1}_{\rm loc}(U)$.

We will use the smooth maximum to prove the following extension result.

######  Proposition 6.2.

Let $h\in C^{1,1}_{\rm loc}(B^{n}(0,R))$ be a convex function. Then, for every
$r\in(0,R)$, there is a convex function $H\in C^{1,1}(\mathbb{R}^{n})$, such
that

$H(x)=h(x)\quad\text{whenever }|x|\leq r.$ (15)

######  Remark 6.3.

If $h\in C^{k}$, $k\in\mathbb{N}\cup\\{\infty\\}$, then $H\in
C^{k}(\mathbb{R}^{n})$. The proof remains the same.

###### Proof.

Choose $\rho\in(r,R)$ and let

$m:=\inf_{|x|\leq r}h,\qquad M:=\sup_{|x|=\rho}h.$

Then, we can find $a,b>0$ such that the function $q(x):=a|x|^{2}-b$ satisfies

$q(x)<m-1\qquad\text{if }|x|\leq r$ (16) $q(x)>M+1\qquad\text{if }|x|=\rho,$
(17)

and we define

$H(x):=\begin{cases}\mathcal{M}(h(x),q(x))&\text{if }|x|\leq\rho,\\\
q(x)&\text{if }|x|>\rho.\end{cases}$

It follows from (16) that $h(x)>q(x)+1$ if $|x|\leq r$, so by (14), we have
$H(x)=\mathcal{M}(h(x),q(x))=h(x)$ if $|x|\leq r$ and the condition (15) is
satisfied. It follows from (17) that there is $\varepsilon>0$ such that
$q(x)>h(x)+1$ if $\rho\leq|x|\leq\rho+\varepsilon$ and hence by (14),
$\mathcal{M}(h(x),q(x))=q(x)$ when $\rho\leq|x|\leq\rho+\varepsilon$.
Therefore, the convex functions $q(x)\in C^{1,1}(\mathbb{R}^{n})$ and
$\mathcal{M}(h(x),q(x))\in C^{1,1}_{\rm loc}(B^{n}(0,R))$ coincide in the
annulus $\rho\leq|x|\leq\rho+\varepsilon$ and hence $H$ is convex in
$\mathbb{R}^{n}$ with $H\in C^{1,1}_{\rm loc}(\mathbb{R}^{n})$. Since $H=q\in
C^{1,1}$ outside the compact ball $\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu^{n}(0,\rho)$, it follows
that $H\in C^{1,1}(\mathbb{R}^{n})$. ∎

###### Proof of Theorem 1.3.

Let $R>0$ be such that $|A\setminus\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern
1.5mu^{n}(0,R)|<\varepsilon/2$. According to Corollary 3.10 there is a convex
function $\widetilde{g}\in C^{1,1}(B^{n}(0,2R))$ such that

$|\\{x\in B^{n}(0,2R):\,f(x)\neq\widetilde{g}(x)\\}|<\frac{\varepsilon}{2}.$

Now, Proposition 6.2 yields a convex function $g\in C^{1,1}(\mathbb{R}^{n})$
such that $g(x)=\widetilde{g}(x)$ for $x\in\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu^{n}(0,R)$ and we have

$|\\{x\in A:\,f(x)\neq g(x)\\}|\leq|A\setminus\mkern
1.7mu\overline{\mkern-1.7muB\mkern-1.5mu}\mkern 1.5mu^{n}(0,R)|+|\\{x\in
B^{n}(0,R):\,f(x)\neq\widetilde{g}(x)\\}|<\varepsilon.$

∎

##  7\. Proofs of Theorems 1.5, 1.6 and 1.8

This section is less self-contained than the others. The proof of the
implication $(1)\Rightarrow(2)$ in Theorem 1.5 is easy and we will not show it
here; see [5, Proposition 1.10 and Theorem 2.5]. The implication
$(2)\Rightarrow(1)$ in Theorem 1.5 is equivalent to the following result.

######  Theorem 7.1.

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a convex function such that
$\lim_{|x|\to\infty}f(x)=+\infty$. Then for every $\varepsilon>0$ there exists
a convex function $g:\mathbb{R}^{n}\to\mathbb{R}$ of class $C^{1,1}_{{\rm
loc}}(\mathbb{R}^{n})$ such that $g\geq f$ and
$|\\{x\in\mathbb{R}^{n}:f(x)\neq g(x)\\}|<\varepsilon$.

Next, we give a proof of Theorem 7.1 that greatly simplifies the one provided
by [5]. Its main ingredients are Corollary 3.10 above and the following lemma
(whose elementary proof can be found in [3, Lemma 5.3], which in turn is a
refinement of the result of [12]).

######  Lemma 7.2.

Let $\varphi:\mathbb{R}^{n}\to\mathbb{R}$ be a continuous function such that
$\lim_{|x|\to\infty}\varphi(x)=+\infty$ and such that for every $R>0$ there
exists $C_{R}>0$ so that for every $x,h\in B^{n}(0,R)$ we have

$\varphi(x+h)+\varphi(x-h)-2\varphi(x)\leq C_{R}|h|^{2}.$

Then the function $F=\operatorname{conv}(\varphi)$ has a similar property: for
every $R>0$ there exists $C^{\prime}_{R}>0$ such that for every $x,h\in
B^{n}(0,R)$ we have

$F(x+h)+F(x-h)-2F(x)\leq C^{\prime}_{R}|h|^{2}.$

Therefore $F\in C^{1,1}_{\rm loc}(\mathbb{R}^{n})$.

Here $\operatorname{conv}(\varphi)$ denotes the convex envelope of $\varphi$,
defined as the supremum of all convex functions less than or equal to
$\varphi$.

###### Proof of Theorem 7.1..

By Corollary 3.10, for every $k\in\mathbb{N}$ we can find a convex function
$g_{k}\in C^{1,1}(B^{n}(0,2k))$ such that $f\leq g_{k}$ and

$|\\{x\in B^{n}(0,2k):\,f(x)\neq g_{k}(x)\\}|<\varepsilon/2^{k}.$

For every $k\in\mathbb{N}$, let $\theta_{k}:(k-2,k+1)\to[0,\infty)$ be a
$C^{\infty}$ convex function such that:

  1. (1)

$\theta_{k}(t)=0$ iff $k-1\leq t\leq k$;

  2. (2)

$\lim_{t\to(k-2)^{+}}\theta_{k}(t)=+\infty$, and

  3. (3)

$\lim_{t\to(k+1)^{-}}\theta_{k}(t)=+\infty$.

Define $\varphi_{k}:\mathbb{R}^{n}\to(-\infty,+\infty]$ by

$\varphi_{k}(x)=g_{k}(x)+\theta_{k}(|x|)\textrm{ if }k-2<|x|<k+1,\textrm{ and
}\varphi_{k}(x)=+\infty\textrm{ otherwise.}$

When $n\geq 2$ and $k\geq 2$, the function $\varphi_{k}$ is not convex, but we
do not need it to be.

Note that $\varphi_{k}(x)=g_{k}(x)$ on the annulus $A_{k}:=\\{x:k-1\leq|x|\leq
k\\}$ (or ball in the special case $k=1$), and consider
$\varphi:\mathbb{R}^{n}\to\mathbb{R}$ defined by
$\varphi(x)=\inf_{k\in\mathbb{N}}\varphi_{k}(x).$ It is clear that

$f\leq\varphi\textrm{ on }\mathbb{R}^{n},\textrm{ and }\varphi\leq
g_{k}\textrm{ on }A_{k},\textrm{ for each }k\in\mathbb{N},$

and in particular $\lim_{|x|\to\infty}\varphi(x)=+\infty,$ though $\varphi$ is
finite everywhere. As a matter of fact, it is easily seen that $\varphi$ is
locally the minimum of at most three continuous functions, and therefore it is
continuous on $\mathbb{R}^{n}$. More precisely, for each $k\in\mathbb{N}$ we
have that

$\varphi(x)=\min\\{\varphi_{k-1}(x),\varphi_{k}(x),\varphi_{k+1}(x)\\}\textrm{
for every }x\in A_{k}.$

Moreover, since $\lim_{|x|\to k^{-}}\varphi_{k-1}(x)=+\infty=\lim_{|x|\to
k^{+}}\varphi_{k+2}(x)$ and $\varphi_{k}$ and $\varphi_{k+1}$ are bounded and
$C^{1,1}$ on a neighborhod of the sphere $\\{x:|x|=k\\}$, there exist some
$M_{k},\delta_{k}>0$ such that
$\varphi(x)=\min\\{\varphi_{k}(x),\varphi_{k+1}(x)\\}$ and
$\varphi_{j}(x+h)+\varphi_{j}(x-h)-2\varphi_{j}(x)\leq M_{k}|h|^{2}$ for all
$k-\delta_{k}\leq|x|\leq k+\delta_{k}$, $|h|\leq\delta_{k}$, and $j=k,k+1$.
These inequalities easily follow from (4). This implies that

$\varphi(x+h)+\varphi(x-h)-2\varphi(x)\leq M_{k}|h|^{2}$

for all $k-\delta_{k}\leq|x|\leq k+\delta_{k}$, and $|h|\leq\delta_{k}$.
Similarly, there exist $M_{k}^{\prime},\delta_{k}^{\prime}>0$ such that
$\varphi(x)=\min\\{\varphi_{k-1}(x),\varphi_{k}(x),\varphi_{k+1}(x)\\}$ and
$\varphi_{j}(x+h)+\varphi_{j}(x-h)-2\varphi_{j}(x)\leq M_{k}^{\prime}|h|^{2}$
for all $k-1+\delta_{k-1}-\delta_{k}^{\prime}\leq|x|\leq
k-\delta_{k}+\delta_{k}^{\prime}$, $|h|\leq\delta_{k}^{\prime}$, and
$j=k-1,k,k+1$, implying that

$\varphi(x+h)+\varphi(x-h)-2\varphi(x)\leq M_{k}^{\prime}|h|^{2}$

for all $k-1+\delta_{k-1}-\delta_{k}^{\prime}\leq|x|\leq
k-\delta_{k}+\delta_{k}^{\prime}$, and $|h|\leq\delta_{k}^{\prime}$. Since
every ball is contained in a finite union of sets $A_{k}$, these estimates
imply that for every $R>0$ there exist $C_{R}>0$ and $\delta_{R}>0$ so that
for every $x\in B^{n}(0,R)$ and $|h|<\delta_{R}$ we have

$E_{h}(x):=\varphi(x+h)+\varphi(x-h)-2\varphi(x)\leq C_{R}|h|^{2}.$ (18)

On the other hand, for $\delta_{R}\leq|h|\leq R$, we obviously have
$E_{h}(x)\leq 4M\leq\widetilde{C_{R}}|h|^{2},$ where $M:=\sup_{z\in
B(0,2R)}\varphi(z)$ and $\widetilde{C_{R}}=4M/\delta_{R}^{2}$. So by replacing
$C_{R}$ with $\max\\{C_{R},\widetilde{C_{R}}\\}$ we certainly have

$\varphi(x+h)+\varphi(x-h)-2\varphi(x)\leq C_{R}|h|^{2}\quad\text{for all
}x,h\in B^{n}(0,R).$ (19)

Therefore, (19) and Lemma 7.2, imply that the function
$g:=\operatorname{conv}(\varphi)$ is of class $C^{1,1}_{\rm loc}$ (and it
obviously satisfies $f\leq g\leq\varphi$). Since $|\\{x\in
B^{n}(0,2k):\,f(x)\neq g_{k}(x)\\}|<\varepsilon/2^{k}$ and $f\leq
g\leq\varphi\leq g_{k}$ on $A_{k}$, it follows that $|\\{x\in A_{k}:\,f(x)\neq
g(x)\\}|<\varepsilon/2^{k}$ for every $k\in\mathbb{N}$, which implies that
$|\\{x\in\mathbb{R}^{n}:f(x)\neq g(x)\\}|\leq\varepsilon$. ∎

###### Proof of Theorem 1.6..

For the proof of the implication (1)$\Rightarrow$(2), see [5, Corollary 1.13].
Regarding the implication (2)$\Rightarrow$(1), the same proof as in [5,
Corollary 1.13] gives us a (possibly unbounded) convex body $W_{\varepsilon}$
with boundary $S_{\varepsilon}$ such that
$W_{\varepsilon}=\frac{1}{t_{0}}g^{-1}(-\infty,t_{0}]$ for some
$t_{0}\in(1,2)$ and some convex function $g\in C^{1,1}_{\rm
loc}(\mathbb{R}^{n})$ such that $\mathcal{H}^{n-1}(S\setminus
S_{\varepsilon})<\varepsilon/2$, $S=\partial W$, and $\mu\leq g$, where $\mu$
is the Minkowski functional of $W$, hence $W_{\varepsilon}\subset W$.

Now it suffices to show that
$\pi_{W_{\varepsilon}}(S)=S_{\varepsilon}$,111This is very easy if $W$ is
bounded and we used this fact in the proof of Theorem 1.4., where
$\pi_{W_{\varepsilon}}$ is the nearest point projection defined in (6),
because this fact and Lemma 2.1 will imply
$\mathcal{H}^{n-1}(S_{\varepsilon}\setminus S)\leq\mathcal{H}^{n-1}(S\setminus
S_{\varepsilon}),$ and hence $\mathcal{H}^{n-1}\left(S_{\varepsilon}\triangle
S\right)<\varepsilon$.

Therefore, it remains to show that if $x\in S_{\varepsilon}$, then there is
$z\in S$ such that $\pi_{W_{\varepsilon}}(z)=x$. Let $\nu(x)$ be the unit
outward normal to $S_{\varepsilon}$ at $x$. It suffices to show that the ray
$R_{x}:=\\{x+t\nu(x):\,t\geq 0\\}$ intersects $S$ at some point $z$, because
clearly, $\pi_{W_{\varepsilon}}(z)=x$. Suppose to the contrary that $R_{x}$
does not intersect with $S$ i.e. $R_{x}\subset\operatorname{int}W$. The
tangent hyperplane to $S_{\varepsilon}$ at $x$ is defined by
$T_{x}:=\\{x+v:\langle v,\nu(x)\rangle=0\\}$ and clearly $S_{\varepsilon}\cap
F_{x}=\varnothing$, where $F_{x}:=\\{x+v:\langle v,\nu(x)\rangle>0\\}$ is an
open half-space bounded by $T_{x}$. Since $x\in\operatorname{int}W$, there is
$\delta>0$ such that $D_{2\delta}\subset\operatorname{int}W$, where
$D_{2\delta}:=\\{x+v\in T_{x}:\,|v|<2\delta\\}$ is the ball in $T_{x}$
centered at $x$ and of radius $2\delta$. Since $D_{2\delta}\cup
R_{x}\subset\operatorname{int}W$, it follows from the convexity of $W$ that
$C_{x}\subset\operatorname{int}W$, where $C_{x}:=\\{p+t\nu(x):\,p\in\partial
D_{\delta},\ t>0\\}$ is the side surface of a half-cylinder.

Since $S$ does not contain any line, it follows that $W$ does not contain any
line (cf. the argument at the beginning of the proof of Theorem 1.8).
Therefore, for any $p\in R_{x}$, and any unit vector $v$ parallel to $T_{x}$,
the lines $L_{p,v}:=\\{p+tv:\,t\in\mathbb{R}\\}$ must intersect $S$ at least
at one point. Denote all such points in $S$ by $A$. Since $A\subset F_{x}$,
$F_{x}\cap S_{\varepsilon}=\varnothing$, we have that $A\subset S\setminus
S_{\varepsilon}$. It is easy to see that $\mathcal{H}^{n-1}(A)=\infty$ and
hence $\mathcal{H}^{n-1}(S\setminus S_{\varepsilon})=\infty$ which is a
contradiction. To show that $\mathcal{H}^{n-1}(A)=\infty$, note that the
radial projection $\pi$ of $A$ onto $C_{x}$ along lines $L_{p,v}$ is
$1$-Lipschitz and hence $\mathcal{H}^{n-1}(A)\geq\mathcal{H}^{n-1}(\pi(A))$.
Now, for each two antipodal points in each sphere of radius $\delta$ in
$C_{x}$ that is parallel to $T_{x}$, at least one belongs to $\pi(A)$. The
mapping $\Phi:C_{x}\to C_{x}$ that maps points in $C_{x}$ to antipodal points
is an isometry of $C_{x}$. Hence
$\mathcal{H}^{n-1}(\pi(A))=\mathcal{H}^{n-1}(\Phi(\pi(A))$. Therefore,

$2\mathcal{H}^{n-1}(A)\geq
2\mathcal{H}^{n-1}(\pi(A))\geq\mathcal{H}^{n-1}(\pi(A)\cup\Phi(\pi(A)))=\mathcal{H}^{n-1}(C_{x})=\infty.$

The proof is complete. ∎

###### Proof of Theorem 1.8.

If an unbounded convex body $V$ contains a line $L$, then since $V$ is closed,
it is easy to see that $V$ contains all lines parallel to $L$ that intersect
with $V$. In particular $\partial V$ is the union of lines parallel to $L$.

(2)$\Rightarrow$(1). Let us define $V_{f}$ as the closure of the epigraph of
$f$, then $V_{f}$ is an unbounded convex body in $\mathbb{R}^{n+1}$. Since the
graph of $f$ does not contain a line, $\partial V_{f}$ does not contain any
line and we may apply Theorem 1.6 and Remark 1.7 to find a
$C^{1,1}_{\textrm{loc}}$ convex body $W\subseteq V_{f}$ such that
$\mathcal{H}^{n}(\partial V_{f}\setminus\partial W)<\varepsilon$. Since the
projection $\pi:\mathbb{R}^{n}\times\mathbb{R}\to\mathbb{R}^{n}$ is
1-Lipschitz, it follows that $g(x):=\inf\\{y:(x,y)\in W\\}$ is a
$C^{1,1}_{\textrm{loc}}$ convex function such that $g\geq f$, $|\\{x\in
U:g(x)\neq f(x)\\}|<\varepsilon$. Note that $g$ is finite on all of $U$.
Indeed, let $A:=\\{x\in U:g(x)<\infty\\}$; we understand that $g(x)=\infty$ if
the line $\\{(x,t):t\in\mathbb{R}\\}$ does not intersect $W$. The set $A$ is
convex because $W$ is convex. If $A\neq U$ then, for some $x_{0}\in U$, some
number $c$ and some linear function $\ell:\mathbb{R}^{n}\to\mathbb{R}$, we
have $\ell(x_{0})\geq c\geq\ell(x)$ for all $x\in A$, implying that for all
$x\in U\cap\ell^{-1}(c,\infty)$ the vertical line $\\{(x,t):t\in\mathbb{R}\\}$
does not intersect $W$. But it is easy to see that the set $\partial
V_{f}\cap\\{(x,t):x\in\mkern 1.7mu\overline{\mkern-1.7muU\mkern-1.5mu}\mkern
1.5mu\cap\ell^{-1}(c,\infty)\\}$ has infinite Hausdorff $n$-dimensional
measure, therefore it must intersect $\partial W$. Hence $g(x)=f(x)<\infty$
for some $x\in U\cap\ell^{-1}(c,\infty)$, a contradiction.

(1)$\Rightarrow$(2). Suppose to the contrary that $f$ satisfies (1) and that
the graph of $f$ contains a line $L$. Then, as we observed above, the graph of
$f$ is the union of lines parallel to $L$. Thus, $U$ is the union of lines
parallel to $\pi(L)$ and clearly, $f$ is affine on each such a line. Now, an
argument similar to the proof of [5, Proposition 1.10] yields that if
$g:U\to\mathbb{R}$ is a convex function such that $|\\{x:f(x)\neq
g(x)\\}|<\infty$, then $g=f$. Hence $g\not\in C^{1,1}_{\rm loc}$, because
$f\not\in C^{1,1}_{\rm loc}$ and we arrive to a contradiction with (1). ∎

## References

  * [1] Alexandroff, A.D.: Almost everywhere existence of the second differential of a convex function and some properties of convex surfaces connected with it. (Russian) Leningrad State Univ. Annals [Uchenye Zapiski] Math. Ser. 6, (1939), 3–35.
  * [2] Azagra, D.: Global and fine approximation of convex functions. Proc. Lond. Math. Soc. (3) 107 (2013), no. 4, 799–824.
  * [3] Azagra, D.: Locally $C^{1,1}$ convex extensions of 1-jets. Rev. Mat. Iberoam. 38 (2022), no. 1, 131–174.
  * [4] Azagra, D., Drake, M., Hajłasz, P.: $C^{2}$-Lusin approximation of strongly convex functions. Preprint 2023.
  * [5] Azagra, D., Hajłasz, P.: Lusin-type properties of convex functions and convex bodies. J. Geom. Anal. 31 (2021), 11685–11701.
  * [6] Azagra, D., Le Gruyer, E., Mudarra, C.: Explicit formulas for $C^{1,1}$ and $C^{1,\omega}_{\rm cov}$ extensions of $1$-jets in Hilbert and superreflexive spaces. J. Funct. Anal. 274 (2018), 3003–3032.
  * [7] Azagra, D., Mudarra, C.: Global geometry and $C^{1}$ convex extensions of $1$-jets. Anal. PDE 12 (2019), 1065–1099.
  * [8] Azagra, D., Mudarra, C.: Whitney extension theorems for convex functions of the classes $C^{1}$ and $C^{1,\omega}$. Proc. Lond. Math. Soc. 114 (2017), 133–158.
  * [9] Bianchi, G., Colesanti, A., Pucci, C.: On the second differentiability of convex surfaces. Geom. Dedicata 60 (1996), 39–48.
  * [10] Hörmander, L.: Notions of Convexity. Progress in Mathematics Series, 127 Birkhäuser Boston, Boston, M.A. 1994
  * [11] Hiriart-Urruty, J.-B., Lemaréchal, C.: Fundamentals of convex analysis. Grundlehren Text Editions. Springer-Verlag, Berlin, 2001.
  * [12] Kirchheim, B., Kristensen, J.: Differentiability of Convex Envelopes. C. R. Acad. Sci. Paris Sér. I Math. 333(8), 725 - 728 (2001), 11685-11701.
  * [13] Kiselman, C. O.: Regularity classes for operations in convexity theory. Kodai Math. J. 15 (1992), 354–374.
  * [14] Lucas, K.: Submanifolds of dimension $n-1$ in $E^{n}$ with normals satisfying a Lipschitz condition. Thesis (Ph.D.)–University of Kansas. 1957. Studies in Eigenvalue Problems, Technical Report 18, Dept of Mathematics, University of Kansas, 1957, Sect. 2.
  * [15] McMullen, P.: On the inner parallel body of a convex body. Israel J. Math. 19 (1974), 217–219.
  * [16] Schneider, R.: Convex bodies: the Brunn-Minkowski theory. Second expanded edition. Encyclopedia of Mathematics and its Applications, 151. Cambridge University Press, Cambridge, 2014.


done non-deterministically in a polynomial space in $Q$.

To show (2), we need to analyse the proof of [8, Theorem 19]. The set of paths
in a VASS from a configuration $(s,\vec{v}_{1})$ to $(t,\vec{v}_{2})$ can be
infinite, but it can be finitely presented with _path schemes_. A _path
scheme_ is a regular expression $\rho$ over transitions of a VASS such that
every sequence of transitions matching $\rho$ is a path in the VASS. It has
been shown that there exists a finite set $S$ of path schemes of the form
$\alpha_{0}\beta_{1}^{*}\ldots\beta_{k}^{*}\alpha_{k}$, where
$\alpha_{0},\ldots,\alpha_{k}$ are paths and $\beta_{0},\ldots,\beta_{k}$ are
cycles, such that (i) each path scheme in $S$ has a polynomially bounded
length in the size of VASS, (ii) for all configurations $(s,\vec{v}_{1})$,
$(t,\vec{v}_{2})$, if there is a path from $(s,\vec{v}_{1})$ to
$(t,\vec{v}_{2})$, then there is a path that matches some path scheme from
$S$. Next, it has been shown that for every path scheme
$\alpha_{0}\beta_{1}^{*}\ldots\beta_{k}^{*}\alpha_{k}=\rho\in S$, there is a
system of linear Diophantine equations $\mathcal{E}_{\rho}$ such that
$\mathcal{E}_{\rho}$ has a solution $x_{1},\ldots,x_{k}$ if and only if
$\alpha_{0}\beta_{1}^{x_{1}}\ldots\beta_{k}^{x_{k}}\alpha_{k}$ is a path from
$(s,\vec{v}_{1})$ to $(t,\vec{v}_{2})$. For each such a system of linear
Diophantine equations $\mathcal{E}_{\rho}$, the set of all its solutions has a
special form. Let $cone(P_{\rho})$ be the set of linear combinations of
vectors from $P$ with non-negative integer coefficients. Then, the set of
solution of $\mathcal{E}_{\rho}$ is of the form $B_{\rho}+cone(P_{\rho})$,
where $B_{\rho},P_{\rho}$ are sets of vectors whose coefficients are (a)
exponentially bounded in the dimension, (b) polynomially bounded in the size
of VASS (with the dimension fixed). It follows that if $\Pi$ is non-empty, one
of the following holds:

  1. [(1)]

  2. 1.

For some path scheme
$\rho=\alpha_{0}\beta_{1}^{*}\ldots\beta_{k}^{*}\alpha_{k}$, sets
$B_{\rho},P_{\rho}$ are non-empty ( $\mathcal{E}_{\rho}$ has infinitely many
solutions), and for some $\vec{u}=(u_{1},\ldots,u_{k})$, the sum of the value
$\lambda_{j}[\pi]$ over paths $\beta_{1}^{u_{1}},\ldots,\beta_{k}^{u_{k}}$ is
negative, and hence the minimum is $-\infty$,

  3. 2.

Otherwise, the minimum exists and it is realized by some path $\pi$ matching
some path scheme $\rho=\alpha_{0}\beta_{1}^{*}\ldots\beta_{k}^{*}\alpha_{k}$
such that $\pi=\alpha_{0}\beta_{1}^{x_{1}}\ldots\beta_{k}^{x_{k}}\alpha_{k}$,
where $(x_{1},\ldots,x_{k})\in B_{\rho}$. Observe that it does not pay off to
incorporate vectors from $P_{\rho}$ as they cannot decrease the value of
$\lambda_{j}[\pi]$. Finally, observe that the size of such a path $\pi$ is
polynomial in the size of VASS if the dimension of the VASS is fixed and it is
exponential in the dimension.

From (1) and (2), we derive bounds $b_{1}(G,Q)<b_{2}(G,Q)$, which are
polynomial in $G$ and exponential in $Q$ such that if the minimum of
$\lambda_{j}[\pi]$ over path in $\Pi$ exists, then it is realized by some path
of length bounded by $b_{1}(G,Q)$. However, if there is a path $\pi\in\Pi$ of
length between $b_{1}(G,Q)$ and $b_{2}(G,Q)$, with $\lambda_{j}[\pi]$ lower
than the value of any path shorter than $b_{1}(G,Q)$, then the minimum is
infinite. Since NL and PSPACE are closed under the complement and bounded
alternation (only two conditions need to be checked), both conditions can be
checked in non-deterministically in polynomial space in $Q$ and logarithmic
space in $G$. The case of the maximum is symmetric. ∎

###  8.2 Language OPhys. Rev. A

Assume $O=\,\mathrel{{\lambda_{1}}{:=}{t_{1}}}$, …,
$\mathrel{{\lambda_{n}}{:=}{t_{n}}}$ has depth $s$. We show by induction on
$s$ that the values of the labellings of a graph $G[O]$ can be non-
deterministically computed in space polynomial in $O$.

######  Lemma 13.

Let $s$ be fixed. For a graph $G$ and $O$ of depth $s$ the value of each
labelling of $G[O]$ can be non-deterministically computed in polynomial space
in $O$ and logarithmic space in $G$.

The proof studies all the possible constructors of terms. In the case of
subqueries, we apply the inductive assumption, i.e., Theorem 8 for a query
with fewer auxiliary labellings. The case of the minimum follows from (2) of
Lemma 12, i.e., $\min_{p\in\Pi}\lambda_{i}[p]$ is either $-\infty$, $+\infty$
or exponential in $Q$ and polynomial in $G$. Therefore, it can be computed
using Lemma 12 and the bisection method. The case for the maximum is
symmetric. Finally, the application of a function symbol to terms or ranges
can be implemented in the expected complexity.

###### Proof.

The proof is by induction on $s$. The basis of induction, $s=0$, is trivial.
Assume that for $s$ the lemma statement and Lemma 9 hold. We show that it
holds for $s+1$. Consider a graph $G$, ontologies $O$, and $O^{\prime}=\,O$,
$\,\mathrel{{\lambda_{1}}{:=}{t_{1}}}$, …,
$\mathrel{{\lambda_{s}}{:=}{t_{k}}}$ such that
$\lambda_{1},\ldots,\lambda_{k}$ are independent, i.e., $t_{1},\ldots,t_{k}$
do not refer to labellings $\lambda_{1},\ldots,\lambda_{k}$.

We show that the value of each $t_{i}$ can be non-deterministically computed
in polynomial space in $O$ and logarithmic space in $G$. We start the
computation from the bottom, the leaves, and show that the values of leaves
can be non-deterministically computed in polynomial space in $O$ and
logarithmic space in $G$. Indeed, leaves are of one of the following forms:
$c\mid\lambda(\vec{y})\mid[Q(\vec{y})]\mid\min_{\lambda,\pi}Q(\vec{y},\pi)\mid\max_{\lambda,\pi}Q(\vec{y},\pi)\mid
y=y$. The cases of $c$ and $y=y$ are trivial. For leaves of the form
$\lambda(\vec{y})$, we know that $\lambda$ is either a graph labelling or it
is from $O$ and hence we use the inductive assumption of this lemma. Finally,
for leaves of the form $[Q(\vec{y})]$, $\min_{\lambda,\pi}Q(\vec{y},\pi)$ and
$\max_{\lambda,\pi}Q(\vec{y},\pi)$, it follows from Lemma 9 applied
inductively for $s$.

The internal nodes of $t_{i}$ are of the form
$f(t_{1}(\vec{y}),\dots,t_{k}(\vec{y}))$ or $f^{\prime}(\\{t(x)\colon
t(x,\vec{y})\\})$. Having the values of subterms
$t_{1}(\vec{y}),\dots,t_{k}(\vec{y})$, the value
$f(t_{1}(\vec{y}),\dots,t_{k}(\vec{y}))$ can be computed in logarithmic in
length of $\vec{x}$ and values in $\vec{x}$, i.e., we require space
$max(\log(|t_{1}(\vec{y})|),\ldots,\log(|t_{k}(\vec{y})|))+\log(k)+C$, where
$C$ is a constant. Similarly, to compute $f^{\prime}(\\{t(x)\colon
t(x,\vec{y})\\})$, we require space
$max_{x}(\log(|t_{1}(x,\vec{y})|)+\log(|G|)+C$, where $C$ is a constant. It
follows that to compute the value of $t_{i}$, we require space
$|t_{i}|(\log|G|+C)\cdot M$, where $C$ is the maximal constant taken over all
$f\in{\mathcal{F}}$ (which is fixed), and $M$ is the maximum over space
requirements of the leaves, which is logarithmic in $G$ and polynomial in
$t_{i}$.

Since all labellings $\lambda_{1},\ldots,\lambda_{k}$ are independent, the
result follows. ∎

Finally, we sketch the proof of Lemma 9.

###### Proof.

(of Lemma 9) The proof is by induction on $s$. Lemma 11 and Lemma 12 imply the
basis of induction. Next, assume that this lemma holds for $s$. Consider an
query LET $O$ IN $Q^{\prime}$, with $0pt(O)=s+1$ and a graph $G$. We first
build a QAM $M^{Q^{\prime}}$ as in Lemma 11. Since $M^{Q^{\prime}}$ may refer
to labellings from $O$, not defined in $G$, we change it so that whenever it
wants to access a value of one of the labellings defined in $O$, it instead
runs a procedure guaranteed by Lemma 13. Lemma 13 holds because this lemma
holds for $s$. Finally, we use Lemma 12 to determine the result. ∎

##  9 Conclusions

We defined a new graphical query language for databases, OPhys. Rev. A. Among
its advantages are good expressive power, modularity and reasonable
complexity.

We demonstrated the expressive power of OPhys. Rev. A in two ways. We
presented examples of natural properties and OPhys. Rev. A queries expressing
them in an organised, modular way. We also showed that OPhys. Rev. A strictly
subsumes ECRPQ+LC. Despite the additional expressive power, the complexity of
the query evaluation problem for OPhys. Rev. A matches the complexity for
ECRPQ.

## References

  * [1] Renzo Angles, Marcelo Arenas, Pablo Barceló, Peter A. Boncz, George H. L. Fletcher, Claudio Gutierrez, Tobias Lindaaker, Marcus Paradies, Stefan Plantikow, Juan F. Sequeda, Oskar van Rest, and Hannes Voigt.  G-CORE: A core for future graph query languages.  In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, pages 1421–1432. ACM, 2018.
  * [2] Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan Reutter, and Domagoj Vrgoč.  Foundations of modern query languages for graph databases.  ACM Comput. Surv., 50(5):68:1–68:40, 2017.
  * [3] Marcelo Arenas, Georg Gottlob, and Andreas Pieris.  Expressive languages for querying the semantic web.  In PODS 2014, pages 14–26. ACM, 2014.
  * [4] Alessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Zakharyaschev.  DL-lite in the light of first-order logic.  In Proceedings of the national conference on artificial intelligence, volume 22, page 361. AAAI Press; MIT Press, 2007.
  * [5] Pablo Barceló.  Querying graph databases.  In Proceedings of the 32nd Symposium on Principles of Database Systems (PODS13), pages 175–188, 2013.
  * [6] Pablo Barceló, Gaëlle Fontaine, and Anthony W. Lin.  Expressive path queries on graph with data.  Logical Methods in Comp. Sci., 11(4), 2015.
  * [7] Pablo Barceló, Leonid Libkin, Anthony W. Lin, and Peter T. Wood.  Expressive languages for path queries over graph-structured data.  ACM Transactions on Database Systems, 37:31:1–31:46, 2012.
  * [8] Michael Blondin, Alain Finkel, Stefan Göller, Christoph Haase, and Pierre McKenzie.  Reachability in two-dimensional vector addition systems with states is pspace-complete.  In 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS15), pages 32–43, 2015.
  * [9] Mikołaj Bojańczyk, Claire David, Anca Muscholl, Thomas Schwentick, and Luc Segoufin.  Two-variable logic on data words.  ACM Trans. Comput. Log., 12(4):27, 2011.
  * [10] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati.  Data complexity of query answering in description logics.  In Proceedings 10th International Conference on Principles of Knowledge Representation and Reasoning (KR06), volume 6, pages 260–270, 2006.
  * [11] Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi.  Containment of conjunctive regular path queries with inverse.  In Proceedings of the 7th International Conference Principles of Knowledge Representation and Reasoning (KR00), pages 176–185, 2000.
  * [12] Mariano Consens and Alberto Mendelzon.  GraphLog: a visual formalism for real life recursion.  In Proceedings of the 9th Symp. on Principles of Database Systems (PODS90), pages 404–416, 1990.
  * [13] Mariano Consens and Alberto Mendelzon.  Low complexity aggregation in GraphLog and Datalog.  Theor. Comp. Sci., 116(1):95–116, 1993.
  * [14] Isabel F. Cruz, Alberto O. Mendelzon, and Peter T. Wood.  A graphical query language supporting recursion.  In Proc. of the ACM Special Interest Group on Management of Data (SIGMOD87), pages 323–330, 1987.
  * [15] Isabel F. Cruz, Alberto O. Mendelzon, and Peter T. Wood.  G+: recursive queries without recursion.  In Expert Database Conf., pages 645–666, 1988.
  * [16] Richard Cyganiak, Markus Lanthaler, and David Wood.  RDF 1.1 concepts and abstract syntax.  W3C Recommendation, 2014.
  * [17] DB-Engines Ranking, 2018.
  * [18] Stéphane Demri, Ranko Lazic, and David Nowak.  On the freeze quantifier in Constraint LTL: Decidability and complexity.  Inf. Comput., 205(1):2–24, 2007.
  * [19] Calvin C. Elgot and Jorge E. Mezei.  On relations defined by generalized finite automata.  IBM J. Res. Dev., 9(1):47–68, January 1965.
  * [20] Diego Figueira and Leonid Libkin.  Path logics for querying graphs: Combining expressiveness and efficiency.  In Proceedings of the 30th Annual Symposium on Logic in Computer Science (LICS15), pages 329–340, 2015.
  * [21] Diego Figueira and Leonid Libkin.  Synchronizing relations on words.  Theory Comput. Syst., 57(2):287–318, 2015.
  * [22] Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor.  Cypher: An evolving query language for property graphs.  In Proceedings of the 2018 International Conference on Management of Data, SIGMOD 2018, pages 1433–1445, 2018.
  * [23] Christiane Frougny and Jacques Sakarovitch.  Synchronized Rational Relations of Finite and Infinite Words.  Theor. Comp. Sci., 108:45–82, 1993.
  * [24] Maciej Graboń, Jakub Michaliszyn, Jan Otop, and Piotr Wieczorek.  Querying data graphs with arithmetical regular expressions.  In Proceedings of the 25rd International Joint Conference on Artificial Intelligence (IJCAI16). AAAI Press, 2016.
  * [25] Steve Harris and Andy Seaborne.  SPARQL 1.1 Query Language.  W3C Recommendation, 2013.
  * [26] Jelle Hellings, Bart Kuijpers, Jan Van den Bussche, and Xiaowang Zhang.  Walk logic as a framework for path query languages on graph databases.  In Proceedings of the 16th International Conference on Database Theory (ICDT13), pages 117–128, 2013.
  * [27] Michael Kaminski and Nissim Francez.  Finite-memory automata.  Theor. Comput. Sci., 134(2):329–363, 1994.
  * [28] Felix Klaedtke and Harald Rueß.  Monadic second-order logics with cardinalities.  In Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, pages 681–696, 2003.
  * [29] Anthony C. Klug.  Equivalence of relational algebra and relational calculus query languages having aggregate functions.  J. ACM, 29(3):699–717, 1982.
  * [30] Eryk Kopczyński and Anthony Widjaja To.  Parikh images of grammars: Complexity and applications.  In Proceedings of the 25th Symposium on Logic in Comp. Sci. (LICS10), pages 80–89, 2010.
  * [31] Leonid Libkin, Wim Martens, and Domagoj Vrgoč.  Querying graphs with data.  J. ACM, 63(2):14:1–14:53, March 2016.
  * [32] Leonid Libkin, Juan L. Reutter, Adrián Soto, and Domagoj Vrgoc.  Trial: A navigational algebra for RDF triplestores.  ACM Trans. Database Syst., 43(1):5:1–5:46, 2018.
  * [33] Leonid Libkin, Tony Tan, and Domagoj Vrgoč.  Regular expressions for data words.  Journal of Computer and System Sciences, 81(7):1278 – 1297, 2015\.
  * [34] Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski.  Pregel: A system for large-scale graph processing.  In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD ’10, pages 135–146, 2010.
  * [35] Alberto Mendelzon and Peter Wood.  Finding regular simple paths in graph databases.  SIAM Journal on Computation, 24(6):1235–1258, 1995.
  * [36] Jakub Michaliszyn, Jan Otop, and Piotr Wieczorek.  Querying best paths in graph databases.  In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, pages 43:1–43:15, 2017.
  * [37] Frank Neven, Thomas Schwentick, and Victor Vianu.  Finite state machines for strings over infinite alphabets.  ACM Trans. Comput. Log., 5(3):403–435, 2004.
  * [38] Cypher Query Language Reference. Version 9, 2017.
  * [39] Eric Prud’hommeaux and Andy Seaborne.  SPARQL Query Language for RDF.  W3C Recommendation, 2008.
  * [40] Bruno Scarpellini.  Complexity of subcases of Presburger arithmetic.  Transactions of the American Mathematical Society, 284(1):203–218, 1984.
  * [41] Luc Segoufin.  Automata and logics for words and trees over an infinite alphabet.  In Proceedings of the 20th Int. Workshop on Computer Science Logic (CSL06), pages 41–57, 2006.
  * [42] The Neo4j Team.  The Neo4j Manual v3.4., 2018.
  * [43] Oskar van Rest, Sungpack Hong, Jinha Kim, Xuming Meng, and Hassan Chafi.  Pgql: A property graph query language.  In Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems, GRADES ’16. Association for Computing Machinery, 2016.
  * [44] Peter T. Wood.  Query languages for graph databases.  SIGMOD Record, 41(1):50–60, 2012.