\section*{\abstractname}%
      \else
        \small
        \list{}{%
          \settowidth{\labelwidth}{\textbf{\abstractname:}}
          \setlength{\leftmargin}{50pt}
          \setlength{\rightmargin}{50pt}
          \setlength{\itemindent}{\labelwidth}
          \addtolength{\itemindent}{\labelsep}
        }
        \item[\textbf{\abstractname:}]

      \fi}
      {\if@twocolumn\else\endlist\fi}
\fi
\makeatother


\let\oldemptyset\emptyset
\let\emptyset\varnothing





\usepackage[noabbrev]{cleveref}








\begin{document}

\begin{NoHyper}
\xdef\@thefnmark{}\@footnotetext{2020 {\it Mathematics Subject Classification.}
68T07,
41A30,
41A63,
31A30,
30E10.
}
\xdef\@thefnmark{}\@footnotetext{{\it Key words and phrases.}
Complex-valued neural networks,
Universal approximation theorem,
Deep neural networks,
Polyharmonic functions,
holomorphic functions}
\xdef\@thefnmark{}\@footnotetext{{\it Address:}
Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz~1, 1090~Vienna, Austria.}
\xdef\@thefnmark{}\@footnotetext{{\it Email address:} \texttt{felix@voigtlaender.xyz}}
\xdef\@thefnmark{}\@footnotetext{{\it Acknowledgments.}
The discussions with Götz Pfander, Dae Gwan Lee and Andrei Caragea that led to the questions
answered in this paper are greatly appreciated.
Many thanks are due to Andrei Caragea for his help in improving the presentation of this paper.}
\end{NoHyper}

\title{The universal approximation theorem\\{} for complex-valued neural networks}
\author{Felix Voigtlaender}

\date{}





\maketitle

\begin{abstract}
  We generalize the classical universal approximation theorem for neural networks
  to the case of \emph{complex-valued} neural networks.
  Precisely, we consider feedforward networks with a complex activation function
  $\sigma : \mathbb{C} \to \mathbb{C}$ in which each neuron performs
  the operation $\mathbb{C}^N \to \mathbb{C}, z \mapsto \sigma(b + w^T z)$ with weights $w \in \mathbb{C}^N$
  and a bias $b \in \mathbb{C}$, and with $\sigma$ applied componentwise.
  We \emph{completely characterize} those activation functions $\sigma$ for which the associated
  complex networks have the universal approximation property, meaning that they
  can uniformly approximate any continuous function on any compact subset of $\mathbb{C}^d$
  arbitrarily well.

  Unlike the classical case of real networks, the set of ``good activation functions''---%
  which give rise to networks with the universal approximation property---%
  differs significantly depending on whether one considers deep networks or shallow networks:
  For deep networks with at least two hidden layers, the universal approximation property holds
  as long as $\sigma$ is neither a polynomial, a holomorphic function, or an antiholomorphic function.
  Shallow networks, on the other hand, are universal if and only if
  the real part or the imaginary part of $\sigma$ is \emph{not} a polyharmonic function.
\end{abstract}



\section{Introduction}%
\label{sec:Introduction}

Deep neural networks form the backbone for the recent success \cite{LeCunDeepLearningNature}
of \emph{deep learning} in applications like image recognition \cite{KrizhevskyImagenet}
and language translation \cite{SutskeverMachineTranslation}.
The currently employed networks are mostly \emph{real-valued},
meaning that the network weights and the activation function $\sigma : \mathbb{R} \to \mathbb{R}$ are real.
But for applications in which the inputs are naturally complex-valued---for instance
for MRI fingerprinting \cite{LustigComplexNNForMRI}---complex-valued networks (CVNNs)
\cite{ArenaNNInMultidimensionalDomains} are a natural choice
and often perform better than their real-valued counterparts
\cite{LustigComplexNNForMRI,WolterComplexGatedRNNs,TrabelsiDeepComplexNetworks}.

In such a complex-valued neural network, each neuron computes a function of the form
${\mathbb{C}^N \ni z \mapsto \sigma(b + w^T z)}$ with a complex bias $b \in \mathbb{C}$
and complex weights $w \in \mathbb{C}^N$, and a complex-valued activation function
$\sigma : \mathbb{C} \to \mathbb{C}$ that is applied componentwise.
Despite having been somewhat neglected in the wake of the deep learning revolution,
such complex-valued networks are receiving increased attention in recent years
\cite{LustigComplexNNForMRI,WolterComplexGatedRNNs,TrabelsiDeepComplexNetworks,
LeCunMotivationForComplexCNNs}.

The expressivity of real-valued neural networks is by now quite well understood.
Classical results in this area of research are the \emph{universal approximation theorem}
\cite{CybenkoUniversalApproximation,HornikStinchcombeWhiteUniversal,
HornikUniversalApproximation,PinkusUniversalApproximation}%
---stating that sufficiently wide (shallow) neural networks can approximate any (continuous)
function---and more quantitative results like the bounds by Mhaskar
\cite{MhaskarSmoothActivationOptimalRate} regarding the approximation of $C^n$
functions using shallow networks with smooth activation functions.
More recent research \cite{YarotskyTraditionalReLUBounds,PetersenOptimalApproximation,
YarotskyPhaseDiagram,LuReLUFiniteDepthUniform}
has focused on similar quantitative results for \emph{deep} networks
with \emph{non-smooth} activation functions, in particular the ReLU $\varrho(z) = \max \{ 0, z \}$.
This is because deep networks perform better in applications \cite{LeCunDeepLearningNature},
and the ReLU has been shown to lead to faster training \cite{GlorotRectifierNetworks}.

Concerning the approximation properties of complex-valued networks,
on the other hand, the literature is quite scarce.
To the best of our knowledge, the only available results are purely qualitative versions
of the universal approximation theorem, and even these are only available
for very special activation functions;
see \cite{ArenaApproximationCapabilityOfComplexNeuralNetworks,ArenaMLPToApproximateComplexValuedFunctions}
and \cite[Chapter~2]{ArenaNNInMultidimensionalDomains},
as well as \cite[Chapter~5]{HiroseCliffordBook}.
We refer to \Cref{sub:RelatedWork} for a more detailed description
of these and other related articles.

Our goal in this article is to initiate a more in-depth study of the approximation properties
of these networks, by providing a \emph{full characterization} of those complex
activation functions $\sigma : \mathbb{C} \to \mathbb{C}$ which lead to network classes that are \emph{universal},
in the sense that \emph{every} continuous function $f : \mathbb{C}^d \to \mathbb{C}$ can be approximated
arbitrarily well (uniformly on compact sets) by sufficiently wide complex-valued
neural networks using the activation function $\sigma$.
For the case of \emph{real-valued} networks, such a characterization is surprisingly simple
\cite{PinkusUniversalApproximation}: these networks are universal if and only if the
activation function $\sigma : \mathbb{R} \to \mathbb{R}$ does not coincide with a polynomial (almost everywhere).
This characterization is quite natural---at least as a necessary condition---since if $\sigma$
is a polynomial of degree $N$, then each function implemented by a network with $L$ hidden layers
and activation $\sigma$ is a polynomial of degree at most $N^L$,
\emph{irrespective of the width of the network}.
This clearly rules out universality.

But as already noted in \cite{ArenaApproximationCapabilityOfComplexNeuralNetworks},
in the complex domain more subtle obstructions to universality appear.
In fact, the results in \cite{ArenaApproximationCapabilityOfComplexNeuralNetworks}
show that a \emph{holomorphic} (entire) activation function can never give rise
to universal sets of networks.
Some authors (see for instance \cite{KimApproximationWithFullyComplexNN}) have tried to circumvent
this obstruction by using holomorphic functions \emph{with singularities}
as activation functions.
However, even this approach does not succeed in general, as shown in the following result.
For a detailed discussion of the findings in \cite{KimApproximationWithFullyComplexNN},
we refer to \Cref{sub:RelatedWork}.

\begin{proposition}\label{prop:IntroHolomorphicIsBad}
  Let $D \subset \mathbb{C}$ be closed and discrete, and let $\sigma : \mathbb{C} \setminus D \to \mathbb{C}$ be holomorphic.
  A weight-tuple $\Theta = \big( (\alpha_1,w_1,b_1),\dots,(\alpha_N,w_N,b_N) \big) \in (\mathbb{C}^3)^N$
  is called \emph{admissible} if for each $j \in \{ 1,\dots,N \}$
  we have $w_j \neq 0$ or $b_j \notin D$.
  In this case, define
  \[
    D_\Theta := \bigcup_{j=1}^N \bigl\{ z \in \mathbb{C} \colon w_j z + b_j \in D \bigr\}
    \qquad \text{and} \qquad
    \Phi_\Theta : \quad
    \mathbb{C} \setminus D_\Theta \to \mathbb{C}, \quad
    z \mapsto \sum_{j=1}^N \alpha_j \, \sigma(b_j + w_j z) .
  \]
  There exists a function $f \in C_c(\mathbb{C}; \mathbb{C})$ and some $\varepsilon > 0$ satisfying
  \[
    \inf_{\substack{N \in \mathbb{N}, \\ \Theta \in (\mathbb{C}^3)^N \text{ admissible}}} \quad
      \sup_{z \in B_1(0) \setminus D_\Theta} \quad
        \bigl|f(z) - \Phi_\Theta (z)\bigr|
    \geq \varepsilon
    \qquad \text{where} \qquad
    B_1(0) = \bigl\{ z \in \mathbb{C} \colon |z| < 1 \bigr\} .
  \]
\end{proposition}

\begin{rem*}
  The assumption of admissibility ensures that the set $D_\Theta$ on which
  $\Phi_\Theta$ is not well-defined is discrete.
\end{rem*}

\begin{proof}
  Let $f \in C_c(\mathbb{C}; \mathbb{C})$ be arbitrary such that $f|_{B_1(0)}$ is not smooth;
  for instance, take ${f(z) = \max \bigl\{ 0, 1 - |z| \bigr\}}$.
  Assume towards a contradiction that the claim of the proposition fails;
  there is thus a sequence $(\Theta_n)_{n \in \mathbb{N}}$ of admissible weights such that
  if we set $D_n := D_{\Theta_n}$ and $\Phi_n := \Phi_{\Theta_n}$, then
  $\sup_{z \in B_1(0) \setminus D_{n}} |f(z) - \Phi_n(z)| \leq n^{-1} < \infty$
  for all $n \in \mathbb{N}$.

  Note that $D_n \subset \mathbb{C}$ is closed and discrete, so that $B_1(0) \cap D_n$ is finite.
  Furthermore, ${\Phi_n : \mathbb{C} \setminus D_n \to \mathbb{C}}$ is holomorphic, meaning that
  each $z \in D_n$ is an isolated singularity of $\Phi_n$.
  Because of ${|\Phi_n(z)| \leq 1 + \| f \|_{L^\infty}}$ for all $z \in B_1(0) \setminus D_n$,
  we see that $\Phi_n$ is bounded on a neighborhood of each $z \in D_n \cap B_1(0)$.
  By elementary complex analysis (see for instance \cite[Chapter~3, Theorem~3.1]{SteinComplexAnalysis})
  this implies that $\Phi_n|_{B_1(0)}$ can be extended to a holomorphic function
  $\Psi_n : B_1(0) \to \mathbb{C}$.
  By continuity (and since $B_1(0) \setminus D_n$ is dense in $B_1(0)$), we thus see
  \[
    \sup_{z \in B_1(0)}
      |f(z) - \Psi_n(z)|
    = \sup_{z \in B_1(0) \setminus D_n}
        |f(z) - \Psi_n(z)|
    = \sup_{z \in B_1(0) \setminus D_n}
        |f(z) - \Phi_n(z)|
    \leq n^{-1} ,
  \]
  so that $\Psi_n$ converges to $f$ uniformly on $B_1(0)$.
  Again by elementary complex analysis
  (see \cite[Chapter~2, Theorem~5.2 and Corollary~4.2]{SteinComplexAnalysis}),
  this implies that $f|_{B_1(0)}$ is holomorphic and hence smooth,
  contradicting our choice of $f$.
\end{proof}

\begin{remark}\label{rem:MostlyHolomorphicCanBeUniversal}
  \Cref{prop:IntroHolomorphicIsBad} only considers holomorphic functions with \emph{isolated}
  singularities; the proof crucially uses that such a singularity is either removable,
  or that otherwise the function is \emph{unbounded} on each neighborhood of the singularity.

  Still, there are \emph{universal} activation functions $\sigma : \mathbb{C} \to \mathbb{C}$ that are holomorphic
  on \emph{most} of their domain.
  To give an example, let $\mathbb{C}_- = \mathbb{C} \setminus (-\infty,0]$, and denote by
  $\operatorname{Log} : \mathbb{C}_- \to \mathbb{C}$ the principal branch of the complex logarithm,
  given by $\operatorname{Log} (r \, e^{i \theta}) = \ln(r) + i \theta$, where $r > 0$
  and $\theta \in (-\pi,\pi)$.
  Then the function
  \[
    \sigma : \quad
    \mathbb{C} \to \mathbb{C}, \quad
    z \mapsto \begin{cases}
                z \cdot \operatorname{Log}(z), & \text{if } z \in \mathbb{C}_-,  \\
                0                              & \text{otherwise}
              \end{cases}
  \]
  is holomorphic on $\mathbb{C}_-$.
  In particular, this implies that the closure of the set of discontinuities of $\sigma$
  is a subset of $(-\infty,0]$, and hence a null-set when considered as a subset of $\mathbb{C}$.
  Furthermore, $\sigma$ is locally bounded (thanks to the factor $z$ compensating the blow-up
  of the logarithm at the origin), and it is easy to see that there does \emph{not}
  exist a smooth function ${g : \mathbb{C} \to \mathbb{C}}$ satisfying $\sigma = g$ almost everywhere.
  Therefore, \Cref{thm:ShallowUniversalApproximation} below shows that the set of shallow
  complex-valued neural networks with activation function $\sigma$ has the universal approximation
  property.
\end{remark}

\Cref{prop:IntroHolomorphicIsBad} shows that the question of ``universal activation functions''
is much more subtle in the complex domain than for real networks.
Nevertheless, we explicitly characterize those activation functions $\sigma : \mathbb{C} \to \mathbb{C}$
for which the associated sets of networks have the universal approximation property;
see the next subsection.
Surprisingly, the class of ``good'' activation functions for \emph{shallow} networks
differs from the class of activation functions that yield universality for \emph{deep} networks.
This is again in stark contrast to the real-valued case.


\subsection{Our results in a nutshell}%
\label{sub:IntroductionResults}

In order to state our results concisely, we first introduce a few notations and conventions.
Similar to \cite{PinkusUniversalApproximation}, we restrict our attention to activation functions
satisfying a minimal continuity property.
Precisely, let us write $\mathcal{M}$ for the class of all functions $\sigma : \mathbb{C} \to \mathbb{C}$
that are locally bounded and such that \emph{the closure} of the set
$\{ z \in \mathbb{C} \,\colon\, \sigma \text{ not continuous at } z \}$
is a null-set, in the sense of the Lebesgue measure on $\mathbb{C} \cong \mathbb{R}^2$.

We do \emph{not} identify functions that agree almost everywhere,
since we will need to consider compositions of such functions,
and it is \emph{not} true in general that $f_1 \circ g_1 = f_2 \circ g_2$ almost everywhere
if $f_1 = f_2$ and $g_1 = g_2$ almost everywhere.
Given this convention, the following notation is natural:
For $\emptyset \neq \Omega \subset \mathbb{C}^d$ and $f : \Omega \to \mathbb{C}$, we write
\[
  \| f \|_{L^\infty(\Omega)}
  := \sup_{z \in \Omega}
       |f(z)| .
\]
We say that a set $\mathcal{F} \subset \{ f : \mathbb{C}^d \to \mathbb{C} \}$ has the
\emph{universal approximation property} if for every continuous function $\varphi : \mathbb{C}^d \to \mathbb{C}$,
every compact set $K \subset \mathbb{C}^d$ and every $\varepsilon > 0$ there exists $f \in \mathcal{F}$
satisfying $\sup_{z \in K} |\varphi(z) - f(z)| \leq \varepsilon$.

Finally, unless explicitly mentioned otherwise, smoothness and differentiability are always
understood in the sense of real variables (and \emph{not} in the sense of holomorphic functions),
under the usual identification $\mathbb{C}^d \cong \mathbb{R}^{2 d}$.

Our first main results provides a complete characterization of those activation functions
for which the associated class $\mathcal{NN}_\sigma^d \subset \{ f : \mathbb{C}^d \to \mathbb{C} \}$ of
\emph{shallow} complex-valued neural networks with activation function $\sigma$, given by
\[
  \mathcal{NN}_\sigma^d
  := \!
     \Big\{
       z \mapsto c +
                 \sum_{j=1}^N
                   a_j \, \sigma\bigl(b_j + w_j^T z\bigr)
       \,\, \colon \,\,
       N \in \mathbb{N}, \,
       a_1, b_1, \mydots, a_N, b_N, c \in \mathbb{C}
       \text{ and } w_1, \mydots, w_N \in \mathbb{C}^d
     \Big\} ,
\]
is universal.

\begin{theorem}\label{thm:ShallowUniversalApproximation}
  Let $\sigma \in \mathcal{M}$ and $d \in \mathbb{N}$ be arbitrary.
  Then the set ${\mathcal{NN}_\sigma^d \subset \{ f : \mathbb{C}^d \to \mathbb{C} \}}$ of shallow complex-valued
  neural networks with activation function $\sigma$ has the universal approximation property
  \emph{if and only if} $\sigma$ is \emph{not} almost polyharmonic.

  Here, we say that $\sigma$ is \emph{almost polyharmonic} if there exist
  $m \in \mathbb{N}$ and ${g \in C^\infty(\mathbb{C}; \mathbb{C})}$ with $\Delta^m g \equiv 0$
  such that $\sigma = g$ almost everywhere.
  Here, $\Delta = \frac{\partial^2}{\partial x^2} + \frac{\partial^2}{\partial y^2}$
  is the usual Laplace operator on $\mathbb{C} \cong \mathbb{R}^2$.
\end{theorem}

\begin{rem*}
  The theorem implies that the class of ``good'' activation functions is quite rich.
  For example, it is well-known (see for instance \cite[Remark~2]{HuilgolBiharmonicLiouville})
  that bounded polyharmonic functions are necessarily constant.
  Thus, the theorem shows that if $\sigma \in \mathcal{M}$ is bounded but not equal to a constant
  (almost everywhere), then $\mathcal{NN}_{\sigma}^d$ is universal.

  Furthermore, the theorem shows that any ``bad'' activation function $\sigma$
  necessarily has to be smooth (possibly after changing it on a null-set).
  Thus, any activation function that can not be made smooth by changing it on a null-set
  is a ``universal'' activation function.
\end{rem*}

Let us denote by $\mathcal{NN}_{\sigma,L}^d$ the set of complex-valued feedforward neural networks
with activation function $\sigma$, input dimension $d$, and $L$ hidden layers;
a precise definition is given in \Cref{def:DeepComplexNetworks} below.
The following theorem characterizes the activation functions $\sigma$
for which the deep network class $\mathcal{NN}_{\sigma,L}^d$ ($L \geq 2$) is universal.
Contrary to the real setting, there are strictly more ``universal'' activation functions
for deep networks than for shallow ones.

\begin{theorem}\label{thm:DeepUniversalApproximationIntroduction}
  Let $\sigma \in \mathcal{M}$ and assume that \emph{none} of the following properties hold:
  \begin{enumerate}[label=\alph*)]
    \item we have $\sigma (z) = p(z, \overline{z})$ for almost all $z \in \mathbb{C}$,
          where $p \in \mathbb{C}[X,Y]$ is a complex polynomial of two variables,

    \item we have $\sigma = g$ almost everywhere or $\sigma = \overline{g}$ almost everywhere,
          where $g : \mathbb{C} \to \mathbb{C}$ is an entire holomorphic function.
  \end{enumerate}
  Then, for each $L \in \mathbb{N}_{\geq 2}$ and each $d \in \mathbb{N}$, the class $\mathcal{NN}_{\sigma,L}^d$
  of deep complex-valued neural networks with activation function $\sigma$ and $L$ hidden layers
  has the universal approximation property.

  Conversely, if $\sigma : \mathbb{C} \to \mathbb{C}$ is continuous and satisfies a) or b),
  then $\mathcal{NN}_{\sigma,L}^d$ does \emph{not} satisfy the universal approximation property
  for any $d, L \in \mathbb{N}$.
\end{theorem}

\begin{rem*}
  Note that the necessary condition requires $\sigma$ to be continuous,
  whereas for the sufficient condition it is only assumed that $\sigma \in \mathcal{M}$.
  The additional continuity assumption is not simply a proof artifact.
  In fact, we will see in \Cref{exa:PathologicalUniversalSigma} that there does exist
  a discontinuous activation function $\sigma \in \mathcal{M}$ that coincides almost everywhere
  with a polynomial $p(z, \overline{z})$, but such that $\mathcal{NN}_{\sigma,L}^d$ is
  nevertheless universal for all $L \in \mathbb{N}_{\geq 2}$ (but not for $L = 1$).
  We leave it as future work to determine natural conditions on $\sigma$
  that are weaker than continuity, but under which a necessary condition
  as in the above theorem still holds.

  We would like to emphasize that any \emph{discontinuous} function $\sigma$
  satisfying (at least) one of the two conditions
  in \Cref{thm:DeepUniversalApproximationIntroduction} has to be quite pathological:
  Such a function is discontinuous, but coincides almost everywhere with a continuous function.
  In that case, it is usually much more natural to work with the ``continuous version''
  of $\sigma$ instead of with $\sigma$ itself.
\end{rem*}

\begin{remark}\label{rem:NecessityEvenL1}
  In both theorems above, it is only stated that if the conditions of the theorem fail,
  then the universal approximation property does not hold, meaning that some continuous
  function cannot be approximated by networks \emph{in the sense of locally uniform convergence}.
  In fact, the proof even shows that some \emph{compactly supported} continuous function
  cannot be approximated in $L_{\mathrm{loc}}^1 (\mathbb{C}^d)$;
  see \Cref{thm:ShallowUniversalApproximationNecessary,thm:DeepNetworksNecessaryCriterion}.
\end{remark}


\subsection{Related work}%
\label{sub:RelatedWork}


\paragraph{The classical universal approximation theorem}

There exist many versions of the universal approximation theorem for \emph{real} networks.
One of the first versions of this theorem is due to Cybenko \cite{CybenkoUniversalApproximation},
who introduced the notion of \emph{discriminatory functions} to prove his result;
see \cite[Section~2]{CybenkoUniversalApproximation}.
By standard properties in functional analysis, it follows that the set of shallow networks
using a discriminatory activation function has the universal approximation property.
What is more challenging is to prove that certain activation functions are indeed discriminatory.
Cybenko verified this for continuous functions $\sigma : \mathbb{R} \to \mathbb{R}$ satisfying
$\lim_{x \to -\infty} \sigma(x) = 0$ and $\lim_{x \to \infty} \sigma(x) = 1$;
such functions are called \emph{sigmoidal}.
A slightly modified version of this result was shown in \cite{HornikStinchcombeWhiteUniversal},
where universality was established for possibly discontinuous, non-decreasing sigmoidal
activation functions.
Hornik \cite{HornikUniversalApproximation} proved universality for arbitrary non-constant,
bounded, continuous activation functions.
Finally, dropping the assumptions of continuity, monotonicity, boundedness, and sigmoidality,
the results in \cite{PinkusUniversalApproximation} established universality
for \emph{every} non-polynomial activation function, under some minimal continuity assumptions.
More precisely, \cite{PinkusUniversalApproximation} considers locally bounded functions
$\sigma : \mathbb{R} \to \mathbb{R}$ for which the closure of the set of discontinuities of $\sigma$ is a null-set;
the class $\mathcal{M}$ of complex-valued functions that we consider is the natural
generalization of this class to the complex domain.



\paragraph{Alternative network architectures}

The classical universal approximation theorem concerns fully connected
feedforward networks of a fixed depth and arbitrary width.
Recently, several alternative network architectures have been studied as well.
For instance, \cite{LuUniversalApproximationBoundedWidth} shows that ReLU networks
with bounded width $d+4$ but \emph{depth tending to infinity} are universal approximators.
Furthermore, \cite{ResNetUniversalApproximation} shows that so-called residual networks
with one neuron per hidden layer but arbitrarily many layers are universal as well.
The universality of \emph{convolutional networks} has been studied in
\cite{ZhouCNNUniversality,ZhouCNNUniversalityDownsampling,
PetersenVoigtlaenderConvolutionalNNEquivalence,YarotskyInvariantUniversal}.
In \cite{ZhouCNNUniversality,ZhouCNNUniversalityDownsampling}, it is shown that
the usual finite-dimensional convolutional networks using many layers and
zero-padded convolutions with short filters---either with \cite{ZhouCNNUniversalityDownsampling}
or without \cite{ZhouCNNUniversality} subsampling---are universal.
The case of convolutions with periodic boundary conditions and without subsampling
is treated in \cite{PetersenVoigtlaenderConvolutionalNNEquivalence}.
Finally, Yarotsky \cite{YarotskyInvariantUniversal} studied the universality
of convolutional networks in a continuous, infinite-dimensional setting.


\paragraph{Universal approximation for complex-valued neural networks}

Some of the first articles studying the approximation properties of complex-valued neural networks
are the papers
\cite{ArenaApproximationCapabilityOfComplexNeuralNetworks,ArenaMLPToApproximateComplexValuedFunctions}
by Arena et al.
In these articles, it was observed that complex-valued networks with holomorphic activation functions
cannot be universal.
Furthermore, \cite{ArenaMLPToApproximateComplexValuedFunctions} generalized the notion
of discriminatory functions introduced in \cite{CybenkoUniversalApproximation}
to the complex domain, showing that networks with discriminatory activation functions are universal.
Again, the actual difficulty lies in verifying that a given activation function is discriminatory.
This was shown in
\cite{ArenaApproximationCapabilityOfComplexNeuralNetworks,ArenaMLPToApproximateComplexValuedFunctions}
for the function $\sigma(z) = \frac{1}{1 + \exp(-\Re z)} + \frac{i}{1 + \exp(-\Im z)}$.
The same result appears in a somewhat more accessible form in
\cite[Theorem~2.6.3]{ArenaNNInMultidimensionalDomains}.
Another activation function that has been shown to be discriminatory is $\sigma(z) = \frac{z}{1 + |z|}$.
This fact can be found in \cite[Chapter~5]{HiroseCliffordBook}, where more general
Clifford-algebra-valued networks are considered; these specialize to complex-valued networks.

Two other widely cited works on the approximation properties of complex-valued neural networks
are \cite{KimApproximationWithFullyComplexNN} and \cite{HuangExtremeLearningFullyComplex}.
Both of these articles, however, are not entirely correct.
In \cite{KimApproximationWithFullyComplexNN}, several holomorphic activation functions
with singularities are considered.
Furthermore, even the entire functions $\sin$ and $\sinh$ are proposed as activation functions.
It is then claimed in the abstract and the summary of \cite{KimApproximationWithFullyComplexNN}
that the neural network sets associated to these activation functions are universal,
in the sense that they can uniformly approximate arbitrary continuous functions
on compact subsets of $\mathbb{C}^n$.
However, as shown in \Cref{prop:IntroHolomorphicIsBad}, this is false in general.
More precisely, one can classify the activation functions
proposed in \cite{KimApproximationWithFullyComplexNN} as follows:
\begin{enumerate}
  \item Entire functions ($\sin$ and $\sinh$), or holomorphic functions with only isolated singularities
        ($\tan$ and $\tanh$).
        For these activation functions, \Cref{prop:IntroHolomorphicIsBad} shows that the associated
        neural networks are \emph{not} universal (even if one redefines them in an arbitrary
        way at the points of the singularities),
        contrary to what is claimed in \cite{KimApproximationWithFullyComplexNN}.

  \item Functions whose definition involves a branch cut,
        but which are \emph{locally bounded} on $\mathbb{C}$.
        These are $\arcsin, \arccos$, and $\arcsinh$.
        If one considers (for instance) the principal branches of these functions,
        then they are locally bounded on $\mathbb{C}$ and the closure of their set of discontinuities
        forms a null-set.
        Further, it is easy to see that \emph{none} of these functions coincides almost everywhere
        with a smooth function.
        Hence, \Cref{thm:ShallowUniversalApproximation} shows that shallow complex-valued
        neural networks with these activation functions are indeed universal.

  \item Function whose definition involves a branch cut,
        but which are \emph{not} locally bounded on $\mathbb{C}$.
        The activation functions of this type considered in \cite{KimApproximationWithFullyComplexNN}
        are $\arctan$ and $\arctanh$.
        For these functions, the theory developed in the present article is not sufficient
        to decide whether the associated complex-valued neural networks are universal or not.
        However, precisely because these activation functions are not locally bounded,
        it is questionable whether they will be useful in practice.
\end{enumerate}
We emphasize that the proofs given in \cite{KimApproximationWithFullyComplexNN}
do \emph{not} correctly prove the universality for the activation functions mentioned in
Points 2 and 3 above, as the very same proofs also (incorrectly)
show universality for the activation functions mentioned in the first point.

Furthermore, there is a mismatch between what is stated in the abstract and summary
of \cite{KimApproximationWithFullyComplexNN} and what is actually stated in the theorems.
For instance, \cite[Theorems~1-3]{KimApproximationWithFullyComplexNN} concern the density
of functions of the form
$\sum_{k=1}^m \beta_k \prod_{\ell=1}^{s_k} \sigma(\theta_{k,\ell} + w_{k,\ell}^T z)$,
which are \emph{not} shallow neural networks with activation function $\sigma$,
due to the product appearing in the definition.
Additionally, \cite[Theorems~1 and 2]{KimApproximationWithFullyComplexNN} consider the approximation
of functions defined on ${I_n = [0,1]^n}$, which has empty interior as a subset of $\mathbb{C}^n$.
For continuous functions on such domains, universal approximation by complex networks
with holomorphic activation functions \emph{is actually possible}, but this is not the
problem considered in the present article and also different from what is claimed
in the abstract and summary of \cite{KimApproximationWithFullyComplexNN}.

Finally, the article \cite{HuangExtremeLearningFullyComplex} considers so-called
\emph{extreme learning machines} with complex weights and activation functions.
These are essentially deep networks in which the weights of the ``lower layers''
are chosen randomly (according to a distribution with full support),
and only the weights on the output layer can be adjusted
in order to achieve the desired approximation.
In the real setting, it has been shown that such extreme learning machines
can almost surely approximate a given continuous function
if more and more random hidden neurons are added \cite{HuangRealELMUniversality};
the proof essentially uses the classical universal approximation in \cite{PinkusUniversalApproximation}
as a black box and shows that the statement remains true if one uses randomly chosen weights,
except on the last layer.
In \cite{HuangExtremeLearningFullyComplex}, a similar reasoning is used to argue that an
analogous result holds in the complex domain.
But for doing so, the authors cite the incorrect results from \cite{KimApproximationWithFullyComplexNN}.
Furthermore, due to the issues in \cite{KimApproximationWithFullyComplexNN} discussed above,
each ``neuron'' in the extreme learning machines considered in
\cite{HuangExtremeLearningFullyComplex} is of the form
$\prod_{\ell=1}^{s_k} \sigma(\theta_{k,\ell} + w_{k,\ell}^T z)$.
Due to the product, this disagrees with the usual definition of neural networks.
It should also be noted that no proof is given for \cite[Lemma~2.6]{HuangExtremeLearningFullyComplex},
which is an essential ingredient for the proofs in \cite{HuangExtremeLearningFullyComplex}.

In summary, to the best of our knowledge, the present article shows for the first time
that a wide class of activation functions leads to complex-valued neural networks
with the universal approximation property.
In fact, we provide a complete characterization of such activation functions,
subject to very mild local boundedness and continuity assumptions.


\subsection{Structure of this article}%
\label{sub:Structure}

After introducing some general notation, \Cref{sec:WirtingerCalculus} gives a brief
introduction to the \emph{Wirtinger calculus}, which will be essential for all that follows.
\Cref{sec:ProofSketch} paves the way for the formal and somewhat technical proofs
in \Cref{sec:Proofs}, by presenting the gist of the argument in a simplified form.
The presentation of the formal proofs in \Cref{sec:Proofs} is split into four subsections.
Considering the case of shallow networks, the first two subsections provide
a proof of \Cref{thm:ShallowUniversalApproximation}, split into separate proofs
for sufficiency and necessity.
Similarly, the last two subsections give a detailed proof of
\Cref{thm:DeepUniversalApproximationIntroduction}.
Several more technical results are deferred to the appendix.


\subsection{Notation}%
\label{sub:notation}

Throughout this article, we always consider $\mathbb{C}$ as a vector space over $\mathbb{R}$,
meaning that differentiability of a function $f : U \subset \mathbb{C}^d \to \mathbb{C}$ will refer to
\emph{real differentiability}, not differentiability in the sense of holomorphic functions,
unless explicitly mentioned otherwise.
In particular, in the context of partial derivatives
$\frac{\partial}{\partial a}, \frac{\partial}{\partial x}$, etc.,
the variables $a,x,\dots$ should always be considered as real variables.
For a function $f : U \subset \mathbb{R}^d \to \mathbb{C}$, we will use the notation $\partial_j f$
for the partial derivative of $f$ with respect to the $j$-th variable.
The same notation is used for $f : U \subset \mathbb{C} \to \mathbb{C}$,
where $f$ is identified with the real function $(x,y) \mapsto f(x + i y)$.
The sets of continuous, $n$-times continuously differentiable, or smooth complex-valued
functions on an open set $\emptyset \neq U \subset \mathbb{C}^d$ are denoted by
$C(U; \mathbb{C})$, $C^n (U; \mathbb{C})$, and $C^\infty( U; \mathbb{C})$, respectively.
The set of smooth complex-valued functions with compact support in $U$ is denoted by
$C_c^\infty(U ; \mathbb{C})$.

On $\mathbb{C}^d$, we use the Euclidean norm $|z| = \bigl(\sum_{j=1}^d |z_j|^2\bigr)^{1/2}$
as well as the maximum norm $\| z \|_{\infty} = \max_{j = 1,\dots,d} |z_j|$.
Open and closed Euclidean balls are denoted by
\[
  B_r (z)
  = \{
      w \in \mathbb{C}^d
      \colon
      |w - z| < r
    \}
  \qquad \text{and} \qquad
  \overline{B_r} (z)
  = \{
      w \in \mathbb{C}^d
      \colon
      |w - z|
      \leq r
    \} ,
\]
respectively; here, $r > 0$ and $z \in \mathbb{C}^d$.
For a subset $D \subset \mathbb{C}^d$, we will use the notation $\overline{D}$ to denote the closure of $D$.
A similar notation $\overbar{z}$ is used to denote the conjugate of a complex number $z \in \mathbb{C}$;
the context will make clear which interpretation is intended.

\smallskip{}

Given a set $\mathcal{F} \subset \{ f : \mathbb{C}^d \to \mathbb{C} \}$, we write
\begin{equation}
  \overline{\mathcal{F}}
  := \big\{
       g : \mathbb{C}^d \to \mathbb{C}
       \quad\colon\quad
       \forall \, K \subset \mathbb{C}^d \text{ compact and } \varepsilon > 0 \quad
         \exists \, f \in \mathcal{F} : \quad
           \| g - f \|_{L^\infty (K)} \leq \varepsilon
     \big\}
  \label{eq:ClosureDefinition}
\end{equation}
for the closure of $\mathcal{F}$ with respect to the topology of local uniform convergence.
Note that if $g \in \overline{\mathcal{F}}$, then there is a sequence $(f_n)_{n \in \mathbb{N}} \subset \mathcal{F}$
satisfying $f_n \to g$ locally uniformly.
Indeed, for each $n \in \mathbb{N}$ we can choose $f_n \in \mathcal{F}$ satisfying
$\| g - f_n \|_{L^\infty(\overline{B_n}(0))} \leq n^{-1}$.

We frequently use the notation $\FirstN{n} := \{ k \in \mathbb{Z} \colon 1 \leq k \leq n \}$
for $n \in \mathbb{N}_0 = \{ 0,1,2,\dots \}$; in particular, $\FirstN{0} = \emptyset$.
To signify a \emph{disjoint} union, we write $\biguplus_{j \in I} B_j$.
The Lebesgue measure on $\mathbb{R}^d$ will be denoted by $\lambda_d$ or simply by $\lambda$.
Identifying $\mathbb{C}^d \cong \mathbb{R}^{2 d}$, we also consider $\lambda_{2 d}$ as a measure on $\mathbb{C}^d$.
Finally, given a function $\sigma : \mathbb{C} \to \mathbb{C}$, we extend it to a map on $\mathbb{C}^d$
by acting componentwise: $\sigma(z_1, \dots, z_d) = \bigl(\sigma(z_1),\dots,\sigma(z_d)\bigr)$.






\section{The Wirtinger calculus and polyharmonic functions}%
\label{sec:WirtingerCalculus}

We will make heavy use of the so-called \emph{Wirtinger calculus};
\cite[§1]{KaupHolomorphicFunctionsSeveralVariables}.
Precisely, given an open set $\emptyset \neq U \subset \mathbb{C}$ and a $C^1$ function $f : U \to \mathbb{C}$,
we define the \emph{Wirtinger derivatives}
\[
  \partial f := \frac{1}{2} \big( \partial_1 f - i \, \partial_2 f \big)
  \qquad \text{and} \qquad
  \overbar{\del} f := \frac{1}{2} \big( \partial_1 f + i \, \partial_2 f \big) .
\]
In the case of functions $f = f(z,w)$ of several complex variables, we will use the notation
$\partial_w$ and $\overbar{\del}_w$ to specify the variable with respect
to which the Wirtinger derivatives are taken.

\begin{rem*}
  In the usual literature, the notation $\frac{\partial}{\partial z}$
  and $\frac{\partial}{\partial \overline{z}}$ is used instead of $\partial$
  and $\overbar{\del}$.
  We refrain from using this notation to avoid ambiguities with the notation
  for partial derivatives in the sense of real differentiability.
\end{rem*}

We will use the following properties of the Wirtinger derivatives, given e.g.~in
\cite[E.~1a]{KaupHolomorphicFunctionsSeveralVariables}:
\begin{itemize}
  \item $\partial$ and $\overbar{\del}$ are $\mathbb{C}$-linear;

  \item a function $f \in C^1(U; \mathbb{C})$ is holomorphic if and only if $\overbar{\del} f \equiv 0$,
        and in this case the complex derivative $f'$ of $f$ coincides with $\partial f$;

  \item the Wirtinger derivatives are compatible with conjugation in the sense that
        \begin{equation}
          \overline{\overbar{\del} f} = \partial \overline{f}
          \quad \text{and} \quad
          \overline{\partial f} = \overbar{\del} \, \overline{f} ;
          \label{eq:WirtingerConjugation}
        \end{equation}

  \item the product rule holds, meaning
        \[
          \partial (f \cdot g) = g \cdot \partial f + f \cdot \partial g
          \quad \text{and} \quad
          \overbar{\del} (f \cdot g)
          = g \cdot \overbar{\del} f + f \cdot \overbar{\del} g
          \quad \text{for} \quad f,g \in C^1(U; \mathbb{C});
        \]

  \item we have the following variant of the chain rule
        for $g \in C^1(U; V)$ and $f \in C^1(V; \mathbb{C})$
        with open sets $\emptyset \neq U, V \subset \mathbb{C}$:
        \begin{equation}
          \partial (f \circ g)
          = \bigl[(\partial f) \circ g\bigr] \cdot \partial g
            + \bigl[(\overbar{\del} f) \circ g\bigr] \cdot \partial \overbar{g}
          \quad \text{and} \quad
          \overbar{\del} (f \circ g)
          = \bigl[(\partial f) \circ g\bigr] \cdot \overbar{\del} g
            + \bigl[(\overbar{\del} f) \circ g\bigr] \cdot \overbar{\del} \, \overbar{g} .
          \label{eq:ChainRule}
        \end{equation}
\end{itemize}

Because of $\partial \overbar{z}^m = \overline{\overbar{\del} z^m} = 0$,
the product rule implies for $m \in \mathbb{N}_0$ and $f \in C^1(U; \mathbb{C})$ that
\(
  \partial\bigl(\overbar{z}^m \cdot f(z)\bigr)
  = f(z) \cdot \partial \overbar{z}^m
    + \overbar{z}^m \cdot \partial f(z)
  = \overbar{z}^m \cdot \partial f(z)
  .
\)
By induction (and separately considering the case $\ell = 0$), this easily shows
\begin{equation}
  \partial^\ell \bigl(\overbar{z}^m \cdot f(z)\bigr)
  = \overbar{z}^m \cdot \partial^\ell f(z)
  \quad \text{for } \ell, m \in \mathbb{N}_0 \text{ and } f \in C^\ell(U ; \mathbb{C}).
  \label{eq:SpecialProductRule}
\end{equation}

The Wirtinger calculus is closely related to the class of
\emph{polyharmonic functions}; see for instance \mbox{\cite[Pages 12--13]{BalkPolyanalyticFunctions}}.
Precisely, given an open set $\emptyset \neq U \subset \mathbb{C}$,
a (real-valued) $C^{2 m}$-function $f : U \to \mathbb{R}$ is called \emph{polyharmonic of order $m$} if
$\Delta^m f \equiv 0$, where $\Delta = \frac{\partial^2}{\partial x^2} + \frac{\partial^2}{\partial y^2}$
is the usual Laplace operator on $\mathbb{C} \cong \mathbb{R}^2$.
We will say that a complex-valued function $f : U \to \mathbb{C}$ is (complex) polyharmonic of order $m$
if both $\Re f$ and $\Im f$ are polyharmonic of order $m$.
The relation between polyharmonic functions and the Wirtinger calculus is due to the identity
\begin{equation}
  \Delta f = 4 \, \partial \overbar{\del} f
  \quad \text{for} \quad
  f \in C^2(U; \mathbb{C}) ,
  \label{eq:WirtingerLaplaceRepresentation}
\end{equation}
given in \cite[Equation~(1.7)]{BalkPolyanalyticFunctions}.




\section{The main proof ideas}%
\label{sec:ProofSketch}

In this section, we sketch the main proof ideas, to prepare for the
fully rigorous, but somewhat technical proofs in \Cref{sec:Proofs}.
We remark that many ideas are inspired by the techniques in \cite{PinkusUniversalApproximation};
we modify these ideas to apply to the complex domain.



\subsection{The case of shallow networks}%
\label{sub:ShallowProofSketch}


\paragraph{Proving sufficiency for smooth $\sigma$:}

Let us assume that $\sigma$ is smooth but \emph{not} polyharmonic.
Thanks to \Cref{eq:WirtingerLaplaceRepresentation}, this implies
$\partial^m \overbar{\del}^\ell \sigma \not\equiv 0$ for all $m,\ell \in \mathbb{N}_0$.
A direct calculation using the properties of the Wirtinger calculus shows that
\begin{equation}
  \partial_w^m \overbar{\del}_w^\ell \big|_{w = 0}
  \bigl[ \sigma(w z + \theta) \bigr]
  = z^m \, \overbar{z}^\ell \cdot (\partial^m \overbar{\del}^\ell \sigma) (\theta) .
  \label{eq:IntroductionMonomialExtraction}
\end{equation}
By choosing $\theta = \theta_{m,\ell}$ such that $(\partial^m \overbar{\del}^\ell \sigma) (\theta) \neq 0$,
one can thus ``extract'' the monomial $z^m \, \overbar{z}^\ell$ from certain
Wirtinger derivatives of $\sigma$.

Note that $\Psi_w : z \mapsto \sigma(w z + \theta)$ can be computed by a single neuron.
Furthermore, since the set $\mathcal{NN}_{\sigma}^1$ is a vector space and closed under translations
and dilations, one can compute difference quotients of $w \mapsto \Psi_w (z)$ using shallow networks.
Based on this observation, one can show that the derivative on the left-hand side of
\Cref{eq:IntroductionMonomialExtraction} can be approximated by shallow networks;
see the proofs of \Cref{lem:MonomialExtraction} and \Cref{prop:DerivativesInTheSpace}
for the details.

By the complex version of the \emph{Stone-Weierstraß theorem}, any continuous function
can be uniformly approximated%
\footnote{Note that this is decidedly false if one only considers polynomials in $z$,
since these are always holomorphic, which is preserved under locally uniform convergence.}
by polynomials $p(z,\overbar{z})$.
This proves universality for input dimension $d = 1$.
Generalizing this to higher input dimension is mainly technical;
see \Cref{lem:FromOneDimensionToHigherDimensions}.


\paragraph{Generalizing to non-smooth $\sigma$:}

The idea is to use convolutions to approximate $\sigma \in \mathcal{M}$ by smooth functions.
More precisely, using that $\sigma \in \mathcal{M}$, one can show for each $\varphi \in C_c^\infty(\mathbb{C})$
that the convolution $\varphi \ast \sigma$ can be approximated arbitrarily well
(locally uniformly) by sums of translations of $\sigma$, and thus by shallow
neural networks that use $\sigma$ as the activation function;
see (the proof of) \Cref{lem:ConvolutionApproximation} for the details.

As a consequence, it suffices to show that for a suitable choice of $\varphi$,
one can approximate every continuous function $f$ arbitrarily well
using shallow networks that use $\varphi \ast \sigma$ as the activation function.
Actually, we show something formally weaker, namely that every continuous function $f$
can be approximated arbitrarily well by networks where each neuron has an
activation function $\varphi \ast \sigma$, where $\varphi$ can be chosen independently
for each neuron.
By the same argument as above, this suffices to prove the actual claim.

To prove the universality of networks with activation function $\varphi \ast \sigma$
varying for each neuron, we show that since $\sigma$ is not almost polyharmonic,
there is for each $m \in \mathbb{N}$ a function $\varphi_m \in C_c^\infty (\mathbb{C})$ satisfying
$\Delta^m (\varphi_m \ast \sigma) \not\equiv 0$,
and thus also $\Delta^k (\varphi_m \ast \sigma) \not\equiv 0$ for $k \leq m$.
The proof of this is based on noting that $\varphi_\varepsilon \ast \sigma \to \sigma$ in $L_{\mathrm{loc}}^1$,
for a suitable choice of $\varphi_\varepsilon \in C_c^\infty (\mathbb{C})$, and on noting that
the property of being (almost) polyharmonic of order $m$ is preserved under this type
of convergence.
This last property is essentially a consequence of \emph{Weyl's lemma} \cite{StroockWeylLemma};
see \Cref{lem:WeaklyPolyharmonicIsPolyharmonic} for the details.
As in \Cref{eq:IntroductionMonomialExtraction}, it follows from
$\Delta^k (\varphi_m \ast \sigma) \not\equiv 0$ for $k \leq m$
that shallow networks using the activation function $\varphi_m \ast \sigma$
can approximate the monomials $z^k \overbar{z}^\ell$ with $0 \leq k,\ell \leq m$ arbitrarily well.
Thus, taking together all the different activation functions $\varphi_m \ast \sigma$ for $m \in \mathbb{N}$,
one recovers all possible monomials and can complete the proof as before.

We remark that this proof device of considering several different activation functions
at once is responsible for many of the technical complications in the proof.



\paragraph{Proving necessity:}

The main observation here is that the operations involved in constructing
a neural network from the activation function $\sigma$ preserve the polyharmonicity.

Precisely, let us assume that $\sigma \in C^\infty(\mathbb{C}; \mathbb{C})$ is polyharmonic,
meaning $\Delta^m \sigma \equiv 0$ for some $m \in \mathbb{N}$;
the generalization to ``almost polyharmonic'' functions is then mainly technical%
\footnote{Note, however, that there is still something to do here.
For instance, for the case of \emph{deep} networks, a similar statement is false,
as \Cref{exa:PathologicalUniversalSigma} shows.}.
Furthermore, it is enough to consider the case of input dimension $d = 1$.
Indeed, if ${f_0 : \mathbb{C} \to \mathbb{C}}$ is continuous and cannot be approximated
by networks in $\mathcal{NN}_\sigma^1$, it is easy to see that
${f : \mathbb{C}^d \to \mathbb{C}, (z_1,\dots,z_d) \mapsto f(z_1)}$ cannot be approximated
by networks in $\mathcal{NN}_{\sigma}^d$.

Since the affine-linear maps $z \mapsto b_j + w_j z$ are holomorphic,
they satisfy $\overbar{\del} (b_j + w_j \, z) = 0$.
Thanks to the chain rule for the Wirtinger derivatives and by \Cref{eq:WirtingerLaplaceRepresentation},
this implies
\begin{align*}
  \Delta^m \big[ \sigma(b_j + w_j \, z) \big]
  & = 4^m \, \partial^m \overbar{\del}^m \bigl[\sigma(b_j + w_j \, z)\bigr] \\
  & = 4^m \, |w_j|^{2m} \cdot \bigl(\partial^m \overbar{\del}^m \sigma\bigr) (b_j + w_j z) \\
  & = |w_j|^{2m} \cdot (\Delta^m \sigma) (b_j + w_j z)
    = 0.
\end{align*}
By linearity, this implies $\Delta^m \Phi \equiv 0$ for all $\Phi \in \mathcal{NN}_{\sigma}^1$.
But similar to the space of holomorphic functions, the space of polyharmonic
functions of a fixed order is a proper subspace of the set of continuous functions
and is closed with respect to locally uniform convergence.
This is essentially a consequence of Weyl's lemma \cite{StroockWeylLemma};
see \Cref{lem:WeaklyPolyharmonicIsPolyharmonic} for the details.

Overall, this shows that $\mathcal{NN}_\sigma^1$ does not have the universal approximation
property if $\sigma$ is (almost) polyharmonic.


\subsection{The case of deep networks}%
\label{sub:DeepProofSketch}

\paragraph{Sufficiency for smooth $\sigma$:}

By assumption, $\sigma$ is neither holomorphic nor antiholomorphic
(i.e., $\overline{\sigma}$ is not holomorphic).
Therefore, $\partial \sigma \not\equiv 0$ and $\overbar{\del} \sigma \not\equiv 0$.
As in \Cref{eq:IntroductionMonomialExtraction}, this implies that shallow networks with
activation function $\sigma$ can approximate the monomials $z$ and $\overbar{z}$,
and hence also the function $z \mapsto \Re z$ arbitrarily well.

Furthermore, since $\sigma$ is not of the form $\sigma(z) = p(z, \overbar{z})$,
one can show for each $m \in \mathbb{N}_0$ that either $\partial^m \sigma \not\equiv 0$
or $\overbar{\del}^m \sigma \not\equiv 0$.
Again, this implies as in \Cref{eq:IntroductionMonomialExtraction} that shallow networks
with activation function $\sigma$ can either approximate the monomial $z^m$ or the monomial
$\overbar{z}^m$ arbitrarily well.
Note that for real inputs $z \in \mathbb{R}$, it does not matter which of the two cases occurs.

Since we consider deep networks with at least two layers, it follows by composition
that suitable networks $\Phi \in \mathcal{NN}_{\sigma,L}^1$ can approximate arbitrarily well
the function $z \mapsto q(\Re z)$, where $q \in \mathbb{C} [X]$ is an arbitrary polynomial.
It is then mainly technical to show that this implies that suitable networks
$\Phi \in \mathcal{NN}_{\sigma,L}^1$ can approximate \emph{every} continuous function $f : \mathbb{C} \to \mathbb{C}$;
see Step~4 in the proof of \Cref{thm:DeepNetworksSufficientCriterion}.
This establishes universality in the case of input dimension $d = 1$.
The generalization to higher input dimensions is again mainly technical;
see \Cref{lem:FromOneDimensionToHigherDimensions}.




\paragraph{Generalizing to non-smooth $\sigma$:}

Since this is similar to the case of shallow networks, we omit the details in this proof sketch.


\paragraph{Proving necessity:}

As for the case of shallow networks, it is enough to consider the case of
input dimension $d = 1$.
If $\sigma$ is holomorphic, it is straightforward to see that every function
$\Phi \in \mathcal{NN}_{\sigma,L}^1$ is holomorphic as well, and thus satisfies $\overbar{\del} \Phi \equiv 0$
and hence $\Delta \Phi \equiv 0$; see \Cref{eq:WirtingerLaplaceRepresentation}.
Likewise, if $\sigma$ is antiholomorphic (meaning that $\overline{\sigma}$ is holomorphic),
then each $\Phi \in \mathcal{NN}_{\sigma,L}^1$ is holomorphic or antiholomorphic,
depending on whether $L$ is even or odd.
Again, this implies $\Delta \Phi \equiv 0$.
Finally, if $\sigma(z) = p(z,\overbar{z})$ is a polynomial of $z$ and $\overbar{z}$,
one can show that each $\Phi \in \mathcal{NN}_{\sigma,L}^1$ satisfies $\Phi(z) = q_\Phi (z,\overbar{z})$
for a two-variable polynomial $q_\Phi \in \mathbb{C}[X,Y]$ of degree $\deg q_\Phi \leq K = K(p,L)$.
Based on this, one can show $\Delta^m \Phi \equiv 0$, for a suitable $m = m(p,L)$.
Thus, in any case, $\mathcal{NN}_{\sigma,L}^1$ only consists of polyharmonic functions of a fixed degree.
This implies as for shallow networks that the network class $\mathcal{NN}_{\sigma,L}^1$ is not universal.






\section{Proofs}%
\label{sec:Proofs}

In this section we formally prove
\Cref{thm:ShallowUniversalApproximation,thm:DeepUniversalApproximationIntroduction},
following the ideas outlined in the preceding section.
In \Cref{sub:SufficiencyShallow,sub:NecessityShallow}, we consider the case of shallow networks
and separately prove the sufficiency and necessity in \Cref{thm:ShallowUniversalApproximation}.
\Cref{sub:SufficiencyDeep,sub:NecessityDeep} follow the same pattern, but for deep networks.


\subsection{Sufficiency for shallow networks}%
\label{sub:SufficiencyShallow}

In the following, instead of directly working with sets of neural networks,
we will consider the slightly more general setting of (complex) subspaces
$V \subset \{ f : \mathbb{C} \to \mathbb{C} \}$ that are \emph{closed under translations and dilations}.
By this we mean that if $\varphi \in V$, then also $\varphi_{a,b} \in V$ for arbitrary
$a,b \in \mathbb{C}$, where
\begin{equation}
  \varphi_{a,b} : \quad
  \mathbb{C} \to \mathbb{C}, \quad
  z \mapsto \varphi(a \, z + b) .
  \label{eq:TranslationDilation}
\end{equation}
The following proposition gives a sufficient condition for such a space $V$
to be dense in the set of all continuous functions.
Here, we only consider subspaces of the set of smooth functions;
the more general case $V \subset \mathcal{M}$ will be considered later.

\begin{proposition}\label{prop:GeneralDensityResultWithSmoothness}
  Let $V \subset C^\infty (\mathbb{C}; \mathbb{C})$ be a (complex) vector space that is
  closed under translations and dilations.
  Furthermore, assume that for arbitrary $m,\ell \in \mathbb{N}_0$ there is $\varphi_{m,\ell} \in V$
  with $\partial^m \overbar{\del}^\ell \varphi_{m,\ell} \not \equiv 0$.
  Then $C(\mathbb{C}; \mathbb{C}) \subset \overline{V}$.
\end{proposition}

The proof of \Cref{prop:GeneralDensityResultWithSmoothness} (given after the following lemma)
is heavily inspired by the arguments in \cite[Step~3 in Section~6]{PinkusUniversalApproximation}.
The main insight of that argument---adapted to the complex setting---%
is contained in the following lemma.
It essentially shows that $\overline{V}$ contains sufficiently many monomials.

\begin{lemma}\label{lem:MonomialExtraction}
  Let $V \subset C^\infty(\mathbb{C}; \mathbb{C})$ be a (complex) vector space that is
  closed under translations and dilations.
  Given arbitrary $\varphi \in V$, $\theta \in \mathbb{C}$, and $m,\ell \in \mathbb{N}_0$, the map
  \[
    \mathbb{C} \to \mathbb{C}, \quad
    z \mapsto z^m \bar{z}^\ell \cdot (\partial^m \overbar{\del}^\ell \varphi) (\theta)
  \]
  belongs to $\overline{V}$.
\end{lemma}

\begin{proof}
  \textbf{Step 1:} We show for $\varphi \in C^\infty(\mathbb{C}; \mathbb{C})$, $m,\ell \in \mathbb{N}_0$
  and $z, \theta \in \mathbb{C}$ that
  \begin{equation}
    \partial_w^m \, \overbar{\del}_w^\ell \big|_{w=0} \big[ \varphi (w z + \theta) \big]
    = z^m \overbar{z}^\ell \cdot (\partial^m \overbar{\del}^\ell \varphi) (\theta) .
    \label{eq:MonomialReproduction}
  \end{equation}
  To see this, note that $w \mapsto w \, z + \theta$ is holomorphic, so that
  $\partial_w \bigl[\, \overline{w z + \theta} \,\bigr] = \overline{\overbar{\del}_w [w z + \theta]} = 0$
  and $\partial_w (w \, z + \theta) = z$, as well as
  \(
    \overbar{\del}_w \big[ \, \overline{w z + \theta} \, \big]
    = \overline{\partial_w [w z + \theta]}
    = \overbar{z} ;
  \)
  see \Cref{eq:WirtingerConjugation}.
  Therefore, the chain rule for the Wirtinger derivatives (see \Cref{eq:ChainRule}) shows that
  \[
    \partial_w \big[ \varphi(w z + \theta) \big]
    = (\partial \varphi) (w z + \theta) \cdot \partial_w [w z + \theta]
      + (\overbar{\del} \varphi) (w z + \theta)
        \cdot \partial_w \bigl[\, \overline{w z + \theta} \,\bigr]
    = z \cdot (\partial \varphi) (w z + \theta) .
  \]
  Based on this, a straightforward induction shows that
  $\partial_w^{m} [\varphi(w z + \theta)] = z^m \cdot (\partial^m \varphi)(w z + \theta)$;
  indeed, for the induction step one uses that
  \[
    \partial_w^{m+1} \bigl[\varphi(w z + \theta)\bigr]
    = \partial_w \big[ z^m \cdot (\partial^m \varphi) (w z + \theta) \big]
    = z^m \cdot \partial_w [(\partial^m \varphi) (w z + \theta)]
    = z^{m} \cdot z \cdot (\partial^{m+1} \varphi) (w z + \theta) .
  \]
  Using exactly the same arguments, one sees that
  \(
    \overbar{\del}_w^\ell \big[ \varphi (w z + \theta) \big]
    = \overbar{z}^\ell \cdot (\overbar{\del}^\ell \varphi) (w z + \theta) .
  \)
  In combination, this shows
  \[
    \partial_w^m \, \overbar{\del}_w^\ell \big[ \varphi (w z + \theta) \big]
    = \partial_w^m \big[ \overbar{z}^\ell \cdot (\overbar{\del}^\ell \varphi) (w z + \theta) \big]
    = \overbar{z}^\ell \, z^m \cdot (\partial^m \, \overbar{\del}^\ell \varphi) (w z + \theta) .
  \]
  Evaluating this at $w = 0$, we obtain \Cref{eq:MonomialReproduction}.

  \medskip{}

  \noindent
  \textbf{Step 2:} \emph{(Completing the proof):}
  Let $\varphi \in V \subset C^\infty (\mathbb{C}; \mathbb{C})$ and $\theta \in \mathbb{C}$ be arbitrary.
  Since $V$ is closed under dilations and translations, and since derivatives can be approximated
  by difference quotients, it follows for arbitrary $k,n \in \mathbb{N}_0$ that
  $\psi_{k,n} \in \overline{V}$, where
  \[
    \psi_{k,n} : \quad
    \mathbb{C} \to \mathbb{C}, \quad
    z \mapsto \frac{\partial^k \partial^n}{\partial a^k \partial b^n} \Big|_{a = b = 0} \,\,
              \varphi \big( (a + i b) z + \theta \big) .
  \]
  A fully rigorous proof showing that $\psi_{k,n} \in \overline{V}$
  is given in \Cref{prop:DerivativesInTheSpace}.

  By definition of the Wirtinger derivatives and since all partial derivatives
  commute for smooth functions, we see that if we write $w = a + i b$, then
  the operator $\partial_w^m \overbar{\del}_w^\ell$ is a finite linear combination (with complex coefficients)
  of the operators $\frac{\partial^k \, \partial^n}{\partial a^k \, \partial b^n}$
  for $k,n \in \mathbb{N}_0$.
  Therefore, we see
  \[
    \Bigl(z \mapsto \partial_w^m \overbar{\del}_w^\ell \big|_{w=0} \big[ \varphi(w z + \theta) \big] \Bigr)
    \in \operatorname{span}_{\mathbb{C}} \bigl\{ \psi_{k,n} \colon k,n \in \mathbb{N}_0 \bigr\}
    \subset \overline{V} .
  \]
  In combination with \Cref{eq:MonomialReproduction}, this yields the claim of the lemma.
\end{proof}

Based on the lemma above, we can easily prove \Cref{prop:GeneralDensityResultWithSmoothness}.

\begin{proof}[Proof of \Cref{prop:GeneralDensityResultWithSmoothness}]
  By assumption, we can find for arbitrary $m,\ell \in \mathbb{N}_0$
  a point $\theta_{m,\ell} \in \mathbb{C}$ and a function $\varphi_{m,\ell} \in V$ such that
  $\rho_{m,\ell} := (\partial^m \overbar{\del}^\ell \varphi_{m,\ell})(\theta_{m,\ell}) \neq 0$.
  Thanks to \Cref{lem:MonomialExtraction}, we thus see
  $\big( z \mapsto \rho_{m,\ell} \cdot z^m \overbar{z}^\ell \big) \in \overline{V}$.
  This implies
  \(
    \overline{V}
    \supset \operatorname{span}_{\mathbb{C}}
            \bigl\{
              (z \mapsto z^m \overline{z}^\ell)
              \colon
              m,\ell \in \mathbb{N}_0
            \bigr\} ,
  \)
  where the right-hand side is an algebra of continuous functions that separates the points of
  $\mathbb{C}$, contains the constant functions, and is closed under conjugation.
  Thus, the complex version of the Stone-Weierstraß theorem
  (see for instance \cite[Theorem~4.51]{FollandRA}) implies that
  $C(\mathbb{C}; \mathbb{C}) \subset \overline{\overline{V}} = \overline{V}$, where we recall that the closure
  is taken with respect to the topology of \emph{locally} uniform convergence.
\end{proof}

The next lemma will be used to generalize \Cref{prop:GeneralDensityResultWithSmoothness}
from subspaces $V \subset C^\infty$ to subspaces $V \subset \mathcal{M}$.
The proof of the lemma is closely based on that of
\cite[Step~4 in Section~6]{PinkusUniversalApproximation}.

\begin{lemma}\label{lem:ConvolutionApproximation}
  With the space $\mathcal{M}$ as in \Cref{sub:IntroductionResults}, let $\sigma \in \mathcal{M}$ be arbitrary.
  Then, for any $\varphi \in C_c^\infty (\mathbb{C}; \mathbb{C})$, we have
  \[
    \varphi \ast \sigma
    \in \overline{\strut \operatorname{span}_{\mathbb{C}} \, \{ T_z \, \sigma \colon z \in \mathbb{C} \}} .
  \]
  Here, $T_z \sigma : \mathbb{C} \to \mathbb{C}, w \mapsto \sigma(w - z)$ denotes the translation of $\sigma$
  by $z \in \mathbb{C}$, and the convolution $\varphi \ast \sigma : \mathbb{C} \to \mathbb{C}$ is given by
  $\varphi \ast \sigma (z) = \int_{\mathbb{C}} \varphi (w) \, \sigma(z - w) \, d w$,
  where integration is with respect to the Lebesgue measure on $\mathbb{C} \cong \mathbb{R}^2$.
\end{lemma}

\begin{proof}
  Define $V := \strut \operatorname{span}_{\mathbb{C}} \, \{ T_z \, \sigma \colon z \in \mathbb{C} \}$.
  Let $K \subset \mathbb{C}$ be compact and $\varepsilon > 0$.
  Identifying $\mathbb{C} \cong \mathbb{R}^2$, choose $A > 0$ so large that $\mathop{\operatorname{supp}} \varphi \subset (-A,A)^2$
  and $K \subset (-A,A)^2$.
  We will construct $g \in V$ satisfying $\| g - \varphi \ast \sigma \|_{L^\infty([-A,A]^2)} \leq 2 \varepsilon$.
  The construction of $g$ will be divided into three steps.

  \medskip{}

  \noindent
  \textbf{Step 1:} \emph{(Constructing a suitable covering of the set of discontinuities of $\sigma$):}
  Choose
  \begin{equation}
    0 < \delta
    \leq \varepsilon / \bigl(1 + 10 \, \| \sigma \|_{L^\infty([-2 A, 2 A]^2)} \, \| \varphi \|_{L^\infty}\bigr)
    .
    \label{eq:ConvolutionApproximationDeltaChoice}
  \end{equation}
  Since $\sigma \in \mathcal{M}$, we have $\lambda(\overline{D}) = 0$,
  with ${D := \{ z \in \mathbb{C} \colon \sigma \text{ not continuous at } z \}}$
  and $\lambda$ denoting the Lebesgue measure.
  It is well-known%
  \footnote{One way to see this is to note by outer regularity that there is an open
  set $U \supset \overline{D}$ satisfying $\lambda(U) < \delta/2$.
  Furthermore, the open set $U$ is a countable union $U = \bigcup_{i=1}^\infty Q_i '$
  of cubes $Q_i '$ with disjoint interiors (see e.g.~\cite[Lemma~2.43]{FollandRA}),
  which ensures that $\sum_{i=1}^\infty \lambda(Q_i ') = \lambda(U) < \delta/2$.
  For each $i$, one can then find an \emph{open} cube $Q_i \supset Q_i '$
  with $\lambda(Q_i) < \lambda(Q_i ') + 2^{-(i+1)} \delta$,
  so that $\sum_{i=1}^\infty \lambda(Q_i) < \delta$
  and $\overline{D} \subset U \subset \bigcup_{i=1}^\infty Q_i$.}
  that this implies $\overline{D} \subset \bigcup_{i=1}^\infty Q_i$
  for suitable open cubes $Q_i \subset \mathbb{R}^2$ with $\sum_{i=1}^\infty \lambda(Q_i) \leq \delta$.
  By compactness, $\overline{D} \cap [-2 A, 2 A]^2 \subset \bigcup_{i=1}^N Q_i =: W$
  for a suitable $N \in \mathbb{N}$.

  Since $\sigma$ is (uniformly) continuous on the compact set
  ${\Omega := [-2 A, 2 A]^2 \setminus W}$, we can find $m \in \mathbb{N}$ such that
  $m > 8 A \sqrt{N / \delta}$ and such that
  \begin{equation}
    \big| \sigma(s) - \sigma(t) \big| \leq \frac{\varepsilon}{1 + \| \varphi \|_{L^1}}
    \quad \text{for all} \quad
    s,t \in \Omega \text{ with } \| s - t \|_\infty \leq \frac{2 A}{m} .
    \label{eq:ConvolutionApproximationUniformContinuity}
  \end{equation}

  \medskip{}

  \noindent
  \textbf{Step 2:} \emph{(Constructing $g$):}
  For $k, \ell \in \FirstN{m}$, set
  ${y_{k,\ell} := - (A, A)^T + \frac{2 A}{m} (k-1, \ell-1)^T \! \in \mathbb{R}^2 \cong \mathbb{C}}$
  and $\Delta_{k,\ell} := y_{k,\ell} + \frac{2 A}{m} [0,1)^2 \subset \mathbb{R}^2 \cong \mathbb{C}$,
  as well as $\theta_{k,\ell} := \int_{\Delta_{k,\ell}} \varphi(y) \, d y \in \mathbb{C}$.
  Note that $[-A,A)^2 = \biguplus_{k,\ell \in \FirstN{m}} \Delta_{k,\ell}$
  and also that $g \in V$ for
  \[
    g : \quad
    \mathbb{C} \to \mathbb{C}, \quad
    z \mapsto \sum_{k,\ell \in \FirstN{m}}
                \theta_{k,\ell} \, \sigma(z - y_{k,\ell}) .
  \]

  We want to prove $|(\varphi \ast \sigma)(z) - g(z)| \leq 2 \varepsilon$ for all $z \in [-A,A]^2$.
  To this end, first note because of
  $\mathop{\operatorname{supp}} \varphi \subset (-A,A)^2 \subset \biguplus_{k,\ell \in \FirstN{m}} \Delta_{k,\ell}$ that
  \(
    (\varphi \ast \sigma)(z)
    = \sum_{k,\ell \in \FirstN{m}}
        \int_{\Delta_{k,\ell}}
          \varphi(y) \sigma(z - y)
        \, d y ,
  \)
  and hence
  \begin{equation}
    \big| (\varphi \ast \sigma) (z) - g(z) \big|
    \leq \sum_{k,\ell \in \FirstN{m}}
           \int_{\Delta_{k,\ell}}
             |\varphi(y)| \cdot \big| \sigma(z - y) - \sigma(z - y_{k,\ell}) \big|
           \, d y .
    \label{eq:ConvolutionApproximationBasicEstimate}
  \end{equation}

  \medskip{}

  \noindent
  \textbf{Step 3:} \emph{(Completing the proof):}
  Fix $z \in [-A,A]^2$.
  In order to further estimate the right-hand side of \Cref{eq:ConvolutionApproximationBasicEstimate},
  define the ``good index set'' as
  $I_g := \{ (k,\ell) \in \FirstN{m}^2 \colon (z - \Delta_{k,\ell}) \cap W = \emptyset\}$
  and the ``bad index set'' as $I_b:= \FirstN{m}^2 \setminus I_g$.

  For $(k,\ell) \in I_g$, we have $z - \Delta_{k,\ell} \subset [-2A, 2A]^2 \setminus W = \Omega$.
  Thus, we see for each $y \in \Delta_{k,\ell}$ that ${z - y, z - y_{k,\ell} \in \Omega}$
  with $\| (z - y) - (z - y_{k,\ell}) \|_\infty = \| y_{k,\ell} - y \|_\infty \leq \frac{2 A}{m}$.
  In view of \Cref{eq:ConvolutionApproximationUniformContinuity}, this implies
  $|\sigma(z - y) - \sigma(z - y_{k,\ell})| \leq \varepsilon / (1 + \| \varphi \|_{L^1})$.
  Overall, we thus see
  \begin{equation}
    \begin{split}
      & \sum_{(k,\ell) \in I_g}
          \int_{\Delta_{k,\ell}}
            |\varphi(y)| \cdot |\sigma(z - y) - \sigma(z - y_{k,\ell})|
          \, d y \\
      & \leq \frac{\varepsilon}{1 + \| \varphi \|_{L^1}}
             \cdot \sum_{(k,\ell) \in I_g}
                     \int_{\Delta_{k,\ell}}
                       |\varphi(y)|
                     \, d y
        \leq \varepsilon \cdot \frac{\| \varphi \|_{L^1}}{1 + \| \varphi \|_{L^1}}
        \leq \varepsilon .
    \end{split}
    \label{eq:ConvolutionApproximationGoodPart}
  \end{equation}

  On the other hand, for $(k,\ell) \in I_b$ we have $\Delta_{k,\ell} \cap (z - W) \neq \emptyset$.
  Recall that $W = \bigcup_{j=1}^N Q_j$ for certain open cubes $Q_j$,
  say $Q_j = \gamma_j + (-r_j, r_j)^2$,
  where $\sum_{j=1}^N (2 r_j)^2 = \sum_{j=1}^N \lambda(Q_j) \leq \delta$.
  Since $\Delta_{k,\ell}$ is a cube with side-length $2A / m$ satisfying
  $\Delta_{k,\ell} \cap (z - W) \neq \emptyset$, we see
  \[
    \Delta_{k,\ell}
    \subset z - W + \frac{2 A}{m} \, \bigl[-1, 1\bigr]^2
    \subset \bigcup_{j=1}^N
             \bigg(
               z - \gamma_j + \Bigl( \frac{2 A}{m} + r_j \Bigr) [-1,1]^2
             \bigg) ,
  \]
  where the right-hand side is \emph{independent} of the choice of $(k,\ell) \in I_b$.
  Combining this with the elementary estimate $(a + b)^2 \leq 2 \, (a^2 + b^2)$, we thus see
  \begin{align*}
    \sum_{(k,\ell) \in I_b} \!\!\!
      \lambda(\Delta_{k,\ell})
    & = \lambda \bigg(
                  \biguplus_{(k,\ell) \in I_b} \!\!
                    \Delta_{k,\ell}
                \bigg)
      \leq \sum_{j=1}^N \!
             \Big[
               4 \cdot \Big( \frac{2 A}{m} \,+\, r_j \Big)^2
             \Big] \\
    & \leq 8 \sum_{j=1}^N \!
               \Big(
                 \frac{4 A^2}{m^2} \,+\, r_j^2
               \Big)
      \leq \Big( \frac{8 A}{m} \Big)^2 \, N + 2 \delta
      \leq 3 \delta .
  \end{align*}
  Here, the last step used that we chose $m > 8A \sqrt{N / \delta}$ in Step~1.
  The preceding bound allows us to estimate the sum over the ``bad'' indices
  in \Cref{eq:ConvolutionApproximationBasicEstimate} as follows:
  \begin{equation}
    \begin{split}
      \sum_{(k,\ell) \in I_b}
        \int_{\Delta_{k,\ell}}
          |\varphi(y)| \cdot \big| \sigma(z \!-\! y) - \sigma(z \!-\! y_{k,\ell}) \big|
        \, d y
      & \leq 2 \,
             \| \sigma \|_{L^\infty([-2A, 2A]^2)} \,
             \| \varphi \|_{L^\infty}
             \sum_{(k,\ell) \in I_b} \!\!
               \lambda(\Delta_{k,\ell}) \\
      & \leq 6 \delta \,
             \| \sigma \|_{L^\infty([-2A, 2A]^2)} \,
             \| \varphi \|_{L^\infty}
        \leq \varepsilon ,
    \end{split}
    \label{eq:ConvolutionApproximationBadPart}
  \end{equation}
  by our choice of $\delta$ in \Cref{eq:ConvolutionApproximationDeltaChoice}.
  Overall, combining
  \Cref{eq:ConvolutionApproximationBasicEstimate,eq:ConvolutionApproximationGoodPart,eq:ConvolutionApproximationBadPart}
  we see ${|(\varphi \ast \sigma)(z) - g(z)| \leq 2 \varepsilon}$ for all $z \in [-A,A]^2 \supset K$.
  Since $g \in V$, this easily yields the claim $\varphi \ast \sigma \in \overline{V}$.
\end{proof}

Using the preceding lemma, we can now generalize \Cref{prop:GeneralDensityResultWithSmoothness}
to the setting of spaces that may contain non-smooth functions.

\begin{theorem}\label{thm:GeneralDensityResult}
  For $m \in \mathbb{N}_0$, define
  \[
    \mathcal{H}_m
    := \big\{
         \sigma : \mathbb{C} \to \mathbb{C}
         \quad \colon \quad
         \exists \, \gamma \in C^\infty (\mathbb{C}; \mathbb{C}) :
           \sigma = \gamma \text{ almost everywhere and } \Delta^m \gamma \equiv 0
       \big\} .
  \]

  Let $V \subset \mathcal{M}$ be a (complex) vector space that is closed under dilations and translations.
  If ${V \nsubseteq \bigcup_{m=0}^\infty \mathcal{H}_m}$, then $C(\mathbb{C}; \mathbb{C}) \subset \overline{V}$.
\end{theorem}

\begin{proof}
  Define
  \(
    W := \operatorname{span}_{\mathbb{C}}
         \big\{
           \varphi \ast \sigma
           \colon
           \varphi \in C_c^\infty (\mathbb{C}; \mathbb{C}) \text{ and } \sigma \in V
         \big\} .
  \)
  Since each $\sigma \in V \subset \mathcal{M}$ is locally bounded, standard properties of the
  convolution show $W \subset C^\infty (\mathbb{C}; \mathbb{C})$.
  The idea of the proof is to show that \Cref{prop:GeneralDensityResultWithSmoothness}
  is applicable to $W$---so that $C(\mathbb{C}; \mathbb{C}) \subset \overline{W}$---and then
  use \Cref{lem:ConvolutionApproximation} to conclude $\overline{W} \subset \overline{V}$.

  \medskip{}

  \noindent
  \textbf{Step 1:} \emph{(Showing that $W$ is closed under dilations and translations):}
  Clearly, it is enough to show for $a,b \in \mathbb{C}$, $\varphi \in C_c^\infty (\mathbb{C}; \mathbb{C})$,
  and $\sigma \in V$ that $\big( z \mapsto (\varphi \ast \sigma) (a \, z + b) \big) \in W$.

  Let us first consider the case $a \neq 0$.
  Note that if we identify $\mathbb{C} \cong \mathbb{R}^2$, then the function $z \mapsto a \, z$
  corresponds to the map
  \(
    \mathbb{R}^2 \to \mathbb{R}^2,
    (x,y) \mapsto \left(
                    \begin{smallmatrix}
                      \Re a & - \Im a \\
                      \Im a & \Re a
                    \end{smallmatrix}
                  \right)
                  \left(\begin{smallmatrix} x \\ y \end{smallmatrix}\right)
    ,
    \vphantom{\sum_j}
  \)
  as follows from the identity
  \(
    a \cdot (x + i \, y)
    = (x \cdot \Re a - y \cdot \Im a)
      + i ( x \cdot \Im a + y \cdot \Re a ) .
    \strut
  \)
  Since
  \({
    \det
    \left(
      \begin{smallmatrix}
        \Re a & - \Im a \\
        \Im a & \Re a
      \end{smallmatrix}
    \right)
    = |a|^2 ,
  }\)
  this justifies the application of the change-of-variables formula in the following calculation,
  in which we use $\sigma_{a,b}$ as defined in \Cref{eq:TranslationDilation}
  and $\varphi_a (z) := \varphi (a z)$:
  \begin{equation}
    \begin{split}
      (\varphi \ast \sigma) (a \, z + b)
      & = \int_{\mathbb{C}}
            \varphi(w) \,
            \sigma (a \, z + b - w)
          \, d w
        = \int_{\mathbb{C}}
            \varphi_a (a^{-1} w) \,
            \sigma_{a,b} (z - a^{-1} w)
          \, d w \\
      & = |a|^2 \, \int_{\mathbb{C}}
                     \varphi_a (v) \cdot \sigma_{a,b} (z - v)
                   \, d v
        = |a|^2 \cdot (\varphi_a \ast \sigma_{a,b}) (z) .
    \end{split}
    \label{eq:ConvolutionTransformation}
  \end{equation}
  Since $\varphi_a \in C_c^\infty(\mathbb{C}; \mathbb{C})$ and $\sigma_{a,b} \in V$,
  this shows $\big( z \mapsto (\varphi \ast \sigma)(a \, z + b) \big) \in W$, as claimed.

  Finally, let us consider the case $a = 0$.
  Note that $z \mapsto (\varphi \ast \sigma)(0 \cdot z + b) = (\varphi \ast \sigma)(b)$
  is a constant function.
  Furthermore, since by assumption $V \nsubseteq \bigcup_{m=0}^\infty \mathcal{H}_m$,
  we see in particular that $V \neq \{ 0 \}$.
  Hence, there are $\sigma_0 \in V$ and $\theta_0 \in \mathbb{C}$ such that $\sigma_0 (\theta_0) \neq 0$.
  Since $V$ is a vector space and closed under dilations and translations, this implies
  $\bigl(z \mapsto \sigma_0 (0 \cdot z + \theta_0)\bigr) \in V$, so that $V$ contains
  the constant function ${\mathds{1}}_{\mathbb{C}} : \mathbb{C} \to \mathbb{C}, z \mapsto 1$.
  Now, choose $\varphi_0 \in C_c^\infty (\mathbb{C}; \mathbb{C})$ with $\int_{\mathbb{C}} \varphi_0(z) \, d z = 1$
  and note ${\mathds{1}}_{\mathbb{C}} = \varphi_0 \ast {\mathds{1}}_{\mathbb{C}} \in W$,
  so that also $W$ contains the constant functions.
  This easily yields the claim in case of $a = 0$.

  \medskip{}

  \noindent
  \textbf{Step 2:} \emph{(Showing that \Cref{prop:GeneralDensityResultWithSmoothness} applies to $W$):}
  Assume towards a contradiction that this is not true; in view of Step~1 this means that there
  exist $m,\ell \in \mathbb{N}_0$ such that $\partial^m \overbar{\del}^\ell \psi \equiv 0$ for all $\psi \in W$.
  Let $k := \max \{ m, \ell \}$ and note thanks to \Cref{eq:WirtingerLaplaceRepresentation} that
  \begin{equation}
    \Delta^k \psi
    = 4^k \cdot \partial^k \overbar{\del}^k \psi
    = 4^k \cdot \partial^{k-m} \overbar{\del}^{k - \ell} \bigl[\, \partial^m \overbar{\del}^\ell \psi \,\bigr]
    \equiv 0
    \qquad \forall \, \psi \in W .
    \label{eq:GeneralDensityContradictionProperty}
  \end{equation}
  We will show that this implies $V \subset \mathcal{H}_k$, which will provide the desired contradiction.

  Define $\eta : \mathbb{C} \to \mathbb{R}$ via $\eta(z) := C \cdot \exp(1 / (|z|^2 - 1))$ if $|z| < 1$
  and $\eta(z) := 0$ otherwise, where $C > 0$ is chosen such that $\int_{\mathbb{C}} \eta(z) \, d z = 1$.
  Then it is shown in \cite[Section~C.5]{EvansPDE} that $\eta \in C_c^\infty (\mathbb{C}; \mathbb{R})$.
  For $\varepsilon > 0$ define $\eta_\varepsilon : \mathbb{C} \to \mathbb{R}, z \mapsto \varepsilon^{-2} \cdot \eta(z/\varepsilon)$.
  Let $\sigma \in V \subset \mathcal{M}$ be arbitrary and set $\sigma_\varepsilon := \eta_\varepsilon \ast \sigma \in W$.
  By \Cref{eq:GeneralDensityContradictionProperty}, we thus have $\Delta^k \sigma_\varepsilon \equiv 0$.

  Note that $\sigma$ is locally bounded and hence $\sigma \in L_{\mathrm{loc}}^1 (\mathbb{C} ; \mathbb{C})$,
  so that \cite[Theorem~7 in Appendix~C]{EvansPDE} shows $\sigma_\varepsilon \to \sigma$
  as $\varepsilon \downarrow 0$, with convergence in $L^{1}_{\mathrm{loc}}(\mathbb{C}; \mathbb{C})$.
  Using partial integration (which is justified since $\sigma_\varepsilon \in C^\infty(\mathbb{C}; \mathbb{C})$),
  we thus see for arbitrary $\varphi \in C_c^\infty(\mathbb{C}; \mathbb{R})$ that
  \[
    \int_{\mathbb{C}}
      \sigma(z) \, \Delta^k \varphi(z)
    \, d z
    = \lim_{\varepsilon \downarrow 0}
      \int_{\mathbb{C}}
        \sigma_\varepsilon (z) \, \Delta^k \varphi(z)
      \, d z
    = \lim_{\varepsilon \downarrow 0}
      \int_{\mathbb{C}}
        \Delta^k \sigma_\varepsilon (z) \, \varphi(z)
      \, d z
    = 0 .
  \]
  This means that $\Delta^k \sigma = 0$ in the sense of distributions.
  It is a folklore fact that this implies ${\sigma = g}$ almost everywhere for a smooth function
  $g \in C^\infty(\mathbb{C}; \mathbb{C})$ with $\Delta^k g \equiv 0$; see \Cref{lem:WeaklyPolyharmonicIsPolyharmonic}
  for a formal proof.
  Hence, $\sigma \in \mathcal{H}_k$.
  Since $\sigma \in V$ was arbitrary, this shows $V \subset \mathcal{H}_k$,
  contradicting the assumptions of the theorem.

  We have thus shown that \Cref{prop:GeneralDensityResultWithSmoothness} applies to $W$,
  meaning $C(\mathbb{C}; \mathbb{C}) \subset \overline{W}$.

  \medskip{}

  \noindent
  \textbf{Step 3:} \emph{(Completing the proof):}
  For $\varphi \in C_c^\infty(\mathbb{C}; \mathbb{C}) \vphantom{\sum_j}$ and $\sigma \in V \subset \mathcal{M}$,
  \Cref{lem:ConvolutionApproximation} shows that
  \(
    \varphi \ast \sigma
    \in \overline{
          \operatorname{span}_{\mathbb{C}}
          \{
            T_z \, \sigma
            \colon
            z \in \mathbb{C}
          \}
        }
    \subset \overline{V} ,
  \)
  since $V$ is a vector space and closed under translations.
  Because $\overline{V}$ is a vector space, this implies $W \subset \overline{V}$ and thus
  $C(\mathbb{C}; \mathbb{C}) \subset \overline{W} \subset \overline{\overline{V}} = \overline{V}$.
\end{proof}

In order to deduce the ``sufficient part'' of the universal approximation theorem
from \Cref{thm:GeneralDensityResult}, the following lemma will be helpful.

\begin{lemma}\label{lem:FromOneDimensionToHigherDimensions}
  For $f : \mathbb{C} \to \mathbb{C}$, $b \in \mathbb{C}$, and $a \in \mathbb{C}^d$, define
  \begin{equation}
    f^{(a,b)} : \quad
    \mathbb{C}^d \to \mathbb{C}, \quad
    z \mapsto f(b + a^T z) .
    \label{eq:DimensionIncreasingDilation}
  \end{equation}
  Define $\varrho_\mathbb{C} : \mathbb{C} \to \mathbb{C}, z \mapsto \max \{ 0, \Re z \}$
  and let $\mathcal{F} \subset \{ f : \mathbb{C} \to \mathbb{C} \}$ with $\varrho_\mathbb{C} \in \overline{\mathcal{F}}$.

  If $\mathcal{G} \subset \{ g : \mathbb{C}^d \to \mathbb{C} \}$ is a (complex) vector space
  that satisfies $\strut f^{(a,b)} \in \mathcal{G}$ for all $f \in \mathcal{F}$, $b \in \mathbb{C}$ and $a \in \mathbb{C}^d$,
  then $C(\mathbb{C}^d; \mathbb{C}) \subset \overline{\mathcal{G}}$.
\end{lemma}

\begin{proof}
  It is enough to show $C(\mathbb{C}^d; \mathbb{R}) \subset \overline{\mathcal{G}}$;
  the case of complex-valued functions can be handled by noting
  that $\Phi + i \Psi \in \mathcal{G}$ if $\Phi, \Psi \in \mathcal{G}$.
  Thus, let $\psi \in C(\mathbb{C}^d; \mathbb{R})$, $R > 0$ and $\varepsilon > 0$.
  We want to construct $g \in \mathcal{G}$ satisfying
  $\| \psi - g \|_{L^\infty(\overline{B_R}(0))} \leq \varepsilon$.

  Define $\underline{\psi} : \mathbb{R}^{2 d} \cong \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}, (x,y) \mapsto \psi(x + i y)$
  and $\varrho : \mathbb{R} \to \mathbb{R}, x \mapsto \max \{ 0, x \}$.
  Furthermore, for $z = x + i y$ with $x,y \in \mathbb{R}^d$,
  let us write $\underline{z} := (x, y)^T \in \mathbb{R}^{2 d}$,
  noting that $| \underline{z} | = |z|$.
  Since $\varrho$ is continuous but does not coincide almost everywhere with a polynomial,
  the classical universal approximation theorem (see \cite{PinkusUniversalApproximation})
  yields $M \in \mathbb{N}$ and $\beta_1,\dots,\beta_M \in \mathbb{R}^{2 d}$
  as well as $\alpha_1,\dots,\alpha_M, \gamma_1,\dots,\gamma_M \in \mathbb{R}$
  such that $\big\| \underline{\psi} - h \big\|_{L^\infty(\overline{B_R}(0))} \leq \frac{\varepsilon}{2}$,
  where $h : \mathbb{R}^{2 d} \to \mathbb{R}$ is defined by
  $h(v) = \sum_{j=1}^M \alpha_j \, \varrho(\gamma_j + \beta_j^T v)$.

  Let us write $\mathbb{R}^{2 d} \ni \beta_j = \bigl(\beta_j^{(1)}, \beta_j^{(2)}\bigr) \in \mathbb{R}^d \times \mathbb{R}^d$
  and define $w_j := \beta_j^{(1)} - i \, \beta_j^{(2)} \in \mathbb{C}^d$ and
  $b_j := \gamma_j \in \mathbb{R} \subset \mathbb{C}$ for ${j \in \{ 1, \dots, M \}}$.
  A straightforward calculation shows
  \begin{equation}
    \Re \bigl(b_j + w_j^T z\bigr)
    = \gamma_j + \beta_j^T \underline{z}
    \qquad \text{and hence} \qquad
    \varrho_{\mathbb{C}} \bigl(b_j + w_j^T z\bigr)
    = \varrho \bigl(\gamma_j + \beta_j^T \underline{z}\bigr)
    \label{eq:RealLinearformAsComplex}
  \end{equation}
  for all $j \in \FirstN{M}$ and $z \in \mathbb{C}^d$.

  \smallskip{}

  Set $A := 1 + \sum_{j=1}^M |\alpha_j|$ and choose $C > 0$ with $\big| b_j + w_j^T z \big| \leq C$
  for all $z \in \overline{B_R}(0)$ and $j \in \FirstN{M}$.
  Since ${\varrho_{\mathbb{C}} \in \overline{\mathcal{F}}}$, there is $\phi \in \mathcal{F}$ satisfying
  $\| \varrho_{\mathbb{C}} - \phi \|_{L^\infty(\overline{B_C}(0))} \leq \frac{\varepsilon}{4 A}$.
  With notation as in \Cref{eq:DimensionIncreasingDilation}, define
  \[
    g := \sum_{j=1}^M
           \alpha_j \, \phi^{(w_j,b_j)}
    .
  \]
  Since $\mathcal{G}$ is a vector space with $\phi^{(w,b)} \in \mathcal{G}$
  for all $b \in \mathbb{C}$ and $w \in \mathbb{C}^d$, we see $g \in \mathcal{G}$.
  Finally, recall that ${b_j + w_j^T z \in \overline{B_C}(0) \subset \mathbb{C}}$
  for all $z \in \overline{B_R}(0) \subset \mathbb{C}^d$.
  Thus, we see by definition of $h$ and in view of \Cref{eq:RealLinearformAsComplex} that
  \begin{align*}
    |\psi(z) - g(z)|
    & \leq \big| \underline{\psi}(\underline{z}) - h(\underline{z}) \big|
         + \big| h(\underline{z}) - g(z) \big| \\
    & \leq \frac{\varepsilon}{2}
           + \sum_{j=1}^M
               |\alpha_j|
               \cdot \big|
                       \varrho_{\mathbb{C}}\bigl(b_j + w_j^T z\bigr)
                       - \phi\bigl(b_j + w_j^T z\bigr)
                     \big|
      \leq \frac{\varepsilon}{2}
           + \frac{\varepsilon}{4 A} \sum_{j=1}^M |\alpha_j|
      \leq \varepsilon
  \end{align*}
  for all $z \in \overline{B_R}(0)$, as desired.
\end{proof}

We close this subsection by deducing the ``sufficient part'' of
\Cref{thm:ShallowUniversalApproximation} from \Cref{thm:GeneralDensityResult}
and \Cref{lem:FromOneDimensionToHigherDimensions}.

\begin{theorem}\label{thm:ShallowUniversalApproximationSufficient}
  Let $\sigma \in \mathcal{M}$ and suppose that there \emph{does not} exist a (complex)
  polyharmonic function $h \in C^\infty(\mathbb{C}; \mathbb{C})$ satisfying $\sigma = h$ almost everywhere.
  Then for each input dimension $d \in \mathbb{N}$, the set $\mathcal{NN}_\sigma^d$ of shallow
  complex-valued neural networks with activation function $\sigma$ and $d$-dimensional input
  has the universal approximation property,
  meaning $C(\mathbb{C}^d; \mathbb{C}) \subset \overline{\mathcal{NN}_\sigma^d}$.
\end{theorem}

\begin{proof}
  For $a,b \in \mathbb{C}$, let $\sigma_{a,b}$ be as defined in \Cref{eq:TranslationDilation}.
  Define $V := \operatorname{span}_{\mathbb{C}} \{ \sigma_{a,b} \colon a,b \in \mathbb{C}  \}$,
  noting that $V \subset \mathcal{M}$ and that $\sigma = \sigma_{1,0} \in V$,
  so that $V \nsubseteq \bigcup_{m=0}^\infty \mathcal{H}_m$ by our assumption on $\sigma$.
  Moreover, using the identity $(\sigma_{a,b})_{\alpha,\beta} = \sigma_{a \alpha, b + a \beta}$
  it follows that $V$ is invariant under dilations and translations.
  Therefore, we can apply \Cref{thm:GeneralDensityResult} to conclude
  that $C(\mathbb{C};\mathbb{C}) \subset \overline{V}$.

  Define $\mathcal{F} := V$ and note that $\mathcal{G} := \mathcal{NN}_\sigma^d \subset \{ g : \mathbb{C}^d \to \mathbb{C} \}$
  is a vector space.
  Furthermore, note for $\alpha,\beta,b \in \mathbb{C}$ and $a \in \mathbb{C}^d$ with notation as in
  \Cref{lem:FromOneDimensionToHigherDimensions} for arbitrary $z \in \mathbb{C}^d$ that
  \[
    (\sigma_{\alpha,\beta})^{(a,b)} (z)
    = \sigma_{\alpha,\beta} (b + a^T z)
    = \sigma\bigl(\beta + \alpha (b + a^T z)\bigr)
    = \sigma \bigl(\beta + \alpha b + (\alpha a)^T z\bigr) ,
  \]
  where the function on the right-hand side is an element of $\mathcal{G}$.
  This easily implies $f^{(a,b)} \in \mathcal{G}$ for arbitrary $f \in \mathcal{F} = V$.
  Therefore, \Cref{lem:FromOneDimensionToHigherDimensions} shows
  $C(\mathbb{C}^d;\mathbb{C}) \subset \overline{\mathcal{G}} = \overline{\mathcal{NN}_\sigma^d}$, as claimed.
\end{proof}


\subsection{Necessity for shallow networks}%
\label{sub:NecessityShallow}

In this section, we prove the ``necessary part'' of \Cref{thm:ShallowUniversalApproximation}.
Precisely, we will prove the following:

\begin{theorem}\label{thm:ShallowUniversalApproximationNecessary}
  Let $\sigma : \mathbb{C} \to \mathbb{C}$ and suppose that $\sigma = g$ almost everywhere for a
  (complex-valued) polyharmonic function $g \in C^\infty(\mathbb{C}; \mathbb{C})$.
  Then for any $d \in \mathbb{N}$ and with $\mathcal{NN}_\sigma^d$ as in
  \Cref{sub:IntroductionResults}, we have $C(\mathbb{C}^d; \mathbb{C}) \nsubseteq \overline{\mathcal{NN}_\sigma^d} \strut$.
  In fact, there exist $f \in C_c (\mathbb{C}^d; \mathbb{R})$ and $\varepsilon > 0$ such that
  $\| f - \Phi \|_{L^1(B_1(0))} \geq \varepsilon$ for all $\Phi \in \mathcal{NN}_\sigma^d$.
\end{theorem}

The main ingredient for the proof is the following lemma
which essentially shows that a space consisting of polyharmonic functions
\emph{of a fixed order} cannot have the universal approximation property,
even if one relaxes the topology of locally uniform convergence to the topology
of local $L^1$ convergence.

\begin{lemma}\label{lem:PolyharmonicityObstructsUniversality}
  Let $d \in \mathbb{N}$ and $\mathcal{F} \subset \{ F : \mathbb{C}^d \to \mathbb{C} \colon F \text{ measurable} \}$,
  and assume that there exists $m \in \mathbb{N}_0$ with the following property:
  For each $F \in \mathcal{F}$ and each $w \in \mathbb{C}^{d-1}$,
  there exists $g = g_{w,F} \in C^{\infty}(\mathbb{C};\mathbb{C})$ with $\Delta^m g \equiv 0$
  and such that $F(z,w) = g(z)$ for almost all $z \in \mathbb{C}$.

  Then there exist $f \in C_c(\mathbb{C}^d; \mathbb{R})$ and $\varepsilon > 0$ such that
  $\| f - F \|_{L^1(B_1(0))} \geq \varepsilon$ for all $F \in \mathcal{F}$.
  In particular this implies $C(\mathbb{C}^d; \mathbb{C}) \nsubseteq \overline{\mathcal{F}}$.
\end{lemma}

\begin{rem*}
  In case of $d = 1$, the assumption is to be understood as stating that for each $F \in \mathcal{F}$
  there is $g \in C^\infty(\mathbb{C};\mathbb{C})$ with $\Delta^m g \equiv 0$ and $F = g$ almost everywhere.
\end{rem*}

\begin{proof}
  We only provide the proof for the case $d \geq 2$ and leave the modification for the (easier)
  case $d = 1$ to the reader.
  For brevity, given $g : \mathbb{C}^d \to \mathbb{C}$, define
  $g^{[w]} : \mathbb{C} \to \mathbb{C}, z \mapsto g(z,w)$ for $w \in \mathbb{C}^{d-1}$.

  Let $U := B_{1/2}(0) \subset \mathbb{C}$ and $V := B_{1/2}(0) \subset \mathbb{C}^{d-1}$,
  noting that $U \times V \subset B_1(0) \subset \mathbb{C}^d$.
  Choose $\gamma \in C_c(\mathbb{C}^d; \mathbb{R})$ with $\gamma \equiv 1$ on $\overline{B_1}(0) \subset \mathbb{C}^d$
  and define
  \[
    f : \quad
    \mathbb{C}^d \to \mathbb{R}, \quad
    z = (z_1,\dots,z_d) \mapsto \gamma(z) \cdot \max \bigl\{ 0, \Re z_1 \bigr\} .
  \]
  Assume towards a contradiction that the claim of the lemma is false;
  this implies existence of a sequence $(F_n)_{n \in \mathbb{N}} \subset \mathcal{F}$ such that if we set
  \[
    H_n : \quad
    V \to [0,\infty], \quad
    w \mapsto \int_{U}
                \big| f(z,w) - F_n(z,w) \big|
              \, d z ,
  \]
  then
  \[
    \| H_n \|_{L^1(V)}
    =    \int_{U \times V}
           \big| f(z,w) - F_n(z,w) \big|
         \, d (z,w)
    \leq \| f - F_n \|_{L^1(B_1(0))}
    \xrightarrow[n\to\infty]{} 0.
  \]
  It is well-known (see for instance \cite[Corollary~2.32]{FollandRA}) that this implies existence
  of a subsequence $(H_{n_k})_{k \in \mathbb{N}}$ satisfying $H_{n_k} (w) \to 0$ as $k \to \infty$,
  for almost all $w \in V$.
  Since $V$ has positive measure, we can choose $w_0 \in V$ satisfying
  $\big\| f^{[w_0]} - F_{n_k}^{[w_0]} \big\|_{L^1(U)} = H_{n_k} (w_0) \to 0$ as $k \to \infty$.
  Furthermore, by the assumptions of the lemma there is for each $k \in \mathbb{N}$ some
  $g_k \in C^\infty(\mathbb{C};\mathbb{C})$ satisfying $\Delta^m g_k \equiv 0$ and $F_{n_k}^{[w_0]} = g_k$
  almost everywhere.

  For arbitrary $\varphi \in C_c^\infty (U; \mathbb{R})$, this implies
  \begin{align*}
    \int_{U}
      f^{[w_0]} (z) \cdot \Delta^m \varphi (z)
    \, d z
    & = \lim_{k \to \infty}
        \int_{U}
          F_{n_k}^{[w_0]} (z) \, \Delta^m \varphi(z)
        \, d z
      = \lim_{k \to \infty}
        \int_{U}
          g_k (z) \, \Delta^m \varphi(z)
        \, d z \\
    & = \lim_{k \to \infty}
        \int_{U}
          \varphi(z) \, \Delta^m g_k (z)
        \, d z
      = 0 ,
  \end{align*}
  meaning that $f^{[w_0]} \in L_{\mathrm{loc}}^1(U; \mathbb{R})$ is weakly polyharmonic of order $m$.
  As shown in \Cref{lem:WeaklyPolyharmonicIsPolyharmonic}, this yields existence of
  $h \in C^\infty(U;\mathbb{R})$ with $f^{[w_0]} = h$ almost everywhere on $U$.
  But for $z \in U$ we have $(z, w_0) \in B_1(0)$ and hence
  ${f^{[w_0]}(z) = f(z, w_0) = \gamma(z,w_0) \cdot \max \{ 0, \Re z \} = \max \{ 0, \Re z \}}$.
  On the one hand, this shows that $h$ and $f^{[w_0]}$ are both continuous on $U$,
  so that $h = f^{[w_0]}$ everywhere on $U$, not just almost anywhere.
  On the other hand, we thus get for all $z \in U$ that $h(z) = f^{[w_0]}(z) = \max \{ 0, \Re z \}$,
  where the right-hand side is not a smooth function of $z \in U = B_{1/2}(0) \subset \mathbb{C}$.
  This contradicts the smoothness of $h$.

  Finally, if we had $C(\mathbb{C}^d; \mathbb{C}) \subset \overline{\mathcal{F}}$, there would be a sequence
  $(F_n)_{n \in \mathbb{N}} \subset \mathcal{F}$ satisfying $F_n \to f$ uniformly on $\overline{B_1}(0)$,
  and hence $\| f - F_n \|_{L^1(B_1(0))} \to 0$ as well, in contradiction to what we just showed.
\end{proof}

We close this subsection by using the above lemma to prove
\Cref{thm:ShallowUniversalApproximationNecessary}.

\begin{proof}[Proof of \Cref{thm:ShallowUniversalApproximationNecessary}]
  Since $g$ is polyharmonic, there is $m \in \mathbb{N}$ with $\Delta^m g \equiv 0$.
  The remainder of the proof is divided into three steps.

  \medskip{}

  \noindent
  \textbf{Step 1:} \emph{(With $g_{a,b}$ as in \Cref{eq:TranslationDilation},
  we have $\Delta^m g_{a,b} \equiv 0$ for all $a,b \in \mathbb{C}$):}
  To see this, note that $z \mapsto b + a \, z$ is holomorphic, so that elementary
  properties of the Wirtinger derivatives (see \Cref{sec:WirtingerCalculus}) show
  $\overline{\overbar{\del} \, \overline{(b + a \, z)}} = \partial (b + a z) = a$
  and $\partial \overline{(b + a z)} = \overline{\overbar{\del} (b + a \, z)} = 0$.
  Thus, the chain rule for Wirtinger derivatives (see \Cref{eq:ChainRule})
  shows for $h \in C^\infty(\mathbb{C};\mathbb{C})$ that
  \[
    \partial \bigl[h(b + a \, z)\bigr]
    = (\partial h) (b + a \, z) \cdot \partial(b + a \, z)
      + (\overbar{\del} h)(b + a \, z) \cdot \partial \overline{(b + a \, z)}
    = a \cdot (\partial h) (b + a \, z)
  \]
  and
  \[
    \overbar{\del} \big[ h(b + a \, z) \big]
    = (\partial h)(b + a \, z) \cdot \overbar{\del} (b + a \, z)
      + (\overbar{\del} h) (b + a \, z) \cdot \overbar{\del} \overline{b + a \, z}
    = \overline{a} \cdot (\overbar{\del} h)(b + \, a z) .
  \]
  Based on these identities and using \Cref{eq:WirtingerLaplaceRepresentation},
  an induction shows that
  \[
    \Delta^m g_{a, b} (z)
    = 4^m \cdot \partial^m \overbar{\del}^m \big[ g (b + a \, z) \big]
    = 4^m \cdot a^m \overline{a}^m \cdot (\partial^m \overbar{\del}^m g) (b + a \, z)
    = |a|^{2m} \cdot (\Delta^m g) (b + a \, z)
    = 0
  \]
  for all $z \in \mathbb{C}$, as claimed.

  \medskip{}

  \noindent
  \textbf{Step 2:} \emph{(There are $\varepsilon > 0$ and $f \in C_c(\mathbb{C}^d; \mathbb{R})$
  with $\| f - \Psi \|_{L^1(B_1(0))} \geq \varepsilon$ for all $\Psi \in \mathcal{NN}_g^d$):}
  Note for $b \in \mathbb{C}$, $w \in \mathbb{C}^{d-1}$ and $a \in \mathbb{C}^d$ that there exists
  $d = d(a,b,w) \in \mathbb{C}$ satisfying $b + a^T (z,w) = d + a_1 \, z$ for all $z \in \mathbb{C}$.
  Therefore, Step~1 shows that
  \[
    \Delta^m \bigl(z \mapsto g(b + a^T (z,w))\bigr)
    = \Delta^m g_{a_1, d} \equiv 0
    .
  \]
  By linearity, by definition of $\mathcal{NN}_{g}^d$, and because of $\Delta^m (1) \equiv 0$
  (since $m \in \mathbb{N}$), we thus see that $\Delta^m \bigl(z \mapsto \Psi (z,w) \bigr) \equiv 0$
  for all $\Psi \in \mathcal{NN}_g^d$ and $w \in \mathbb{C}^{d-1}$.
  Thus, setting $\mathcal{F} := \mathcal{NN}_g^d$, \Cref{lem:PolyharmonicityObstructsUniversality} yields
  $f \in C_c(\mathbb{C}^d;\mathbb{R})$ and $\varepsilon > 0$
  satisfying $\| f - F \|_{L_1(B_1(0))} \geq \varepsilon$ for all $F \in \mathcal{F}$.
  This is precisely what was claimed in this step.

  \medskip{}

  \noindent
  \textbf{Step 3:} \emph{(For each $\Phi \in \mathcal{NN}_\sigma^d$, there is $\Psi \in \mathcal{NN}_g^d$
  with $\Phi = \Psi$ almost everywhere):}
  Let $N := \{ z \in \mathbb{C} \colon \sigma(z) \neq g(z) \}$.
  By assumption, $N \subset \mathbb{C}$ is a (Lebesgue) null-set.
  Each $\Phi \in \mathcal{NN}_\sigma^d$ is of the form
  ${\Phi(z) = c + \sum_{j=1}^k \theta_j \, \sigma(b_j + w_j^T z)}$
  for certain $k \in \mathbb{N}$, ${\theta_1,b_1,\dots,\theta_k,b_k,c \in \mathbb{C}}$
  and $w_1,\dots,w_k \in \mathbb{C}^d$.

  Let $J_0 := \bigl\{ j \in \FirstN{k} \colon w_j = 0 \bigr\}$
  and ${J_1 := \FirstN{k} \setminus J_0}$.
  For each $j \in J_1$, \Cref{lem:HyperplaneNullSet} shows that
  $M_j := \{ z \in \mathbb{C}^d \colon b_j + w_j^T z \in N \}$ is a null-set,
  and hence so is $M := \bigcup_{j \in J_1} M_j$.
  For each $j \in J_0$, we have $\theta_j \, \sigma (b_j + w_j^T z) \equiv \theta_j \, \sigma(b_j)$
  and hence $c + \sum_{j \in J_0} \theta_j \, \sigma(b_j + w_j^T z) \equiv c'$
  for a suitable $c' \in \mathbb{C}$.
  On the other hand, for $j \in J_1$ and $z \in \mathbb{C}^d \setminus M$, we have
  $\sigma(b_j + w_j^T z) = g(b_j + w_j^T z)$, which shows that if we define $\Psi : \mathbb{C}^d \to \mathbb{C}$
  by $\Psi (z) := c' + \sum_{j \in J_1} \theta_j \, g(b_j + w_j^T z)$
  then $\Psi \in \mathcal{NN}_g^d$ and $\Phi(z) = \Psi(z)$
  for all $z \in \mathbb{C}^d \setminus M$ and hence almost everywhere.

  \medskip{}

  Finally, let $f \in C_c(\mathbb{C}^d;\mathbb{R})$ as provided by Step~2.
  For each $\Phi \in \mathcal{NN}_\sigma^d$, Step~3 yields ${\Psi \in \mathcal{NN}_g^d}$
  with $\Phi = \Psi$ almost everywhere, so that
  ${\| f - \Phi \|_{L^1(B_1(0))} = \| f - \Psi \|_{L^1(B_1(0))} \geq \varepsilon \!>\! 0}$.
  Exactly as in the proof of \Cref{lem:PolyharmonicityObstructsUniversality},
  this also implies $C(\mathbb{C}^d; \mathbb{C}) \nsubseteq \overline{\mathcal{NN}_\sigma^d}$.
\end{proof}

Finally, we remark that \Cref{thm:ShallowUniversalApproximation} is an immediate consequence
of combining \Cref{thm:ShallowUniversalApproximationSufficient,thm:ShallowUniversalApproximationNecessary}.


\subsection{Sufficiency for deep networks}%
\label{sub:SufficiencyDeep}

In this section, we consider the case of deep complex-valued networks;
that is, complex-valued networks with more than one hidden layer.
Somewhat surprisingly, these deep networks enjoy the universal approximation property
for a strictly larger class of activation functions than for the case of shallow networks.
Before we state and prove this result rigorously, let us first provide a
precise definition of such deep complex-valued networks.

\begin{definition}\label{def:DeepComplexNetworks}
  Let $d,L \in \mathbb{N}$.
  We define the set $\mathcal{W}_L^d$ of all \emph{complex network weights}
  with $d$-dimensional input and $L$ hidden layers as
  \[
    \mathcal{W}_L^d
    := \bigg\{
         \big(
           (A_0, b_0),
           \dots,
           (A_L, b_L)
         \big)
         \quad \colon \quad
         \begin{array}{l}
           N_0,\dots,N_{L+1} \in \mathbb{N},
           \quad
           N_0 = d,
           \quad
           N_{L+1} = 1, \\[0.1cm]
           \text{and }
           A_j \in \mathbb{C}^{N_{j+1} \times N_j}, \quad
           b_j \in \mathbb{C}^{N_{j+1}}
         \end{array}
       \bigg\} .
  \]
  Given network weights $\Theta = \big( (A_0,b_0),\dots,(A_L,b_L) \big) \in \mathcal{W}_L^d$
  and any function $\sigma : \mathbb{C} \to \mathbb{C}$, we define the associated \emph{network function}
  $\mathcal{N}_\sigma \Theta : \mathbb{C}^d \to \mathbb{C}$ via $\mathcal{N}_\sigma \Theta (z) = z^{(L)}$, where
  \[
    z^{(-1)} := z,
    \quad
    z^{(j)} := \sigma\bigl(b_j + A_j \, z^{(j-1)}\bigr) \quad \text{for } j \in \{ 0,\dots,L-1 \},
    \quad \text{and} \quad
    z^{(L)} := b_L + A_L \, z^{(L-1)} .
  \]
  Here, the activation function $\sigma$ is applied componentwise, meaning
  $\sigma(z) = \big( \sigma(z_1),\dots,\sigma(z_N) \big)$ for $z = (z_1,\dots,z_N) \in \mathbb{C}^N$.

  Finally, we define the set of all network functions with activation function $\sigma$,
  $L$ hidden layers, and $d$-dimensional input as
  \[
    \mathcal{NN}_{\sigma,L}^d
    := \big\{
         \mathcal{N}_\sigma \Theta
         \,\, \colon \,\,
         \Theta \in \mathcal{W}_L^d
       \big\} .
  \]
\end{definition}

\begin{rem*}
  It is not hard to see that $\mathcal{NN}_{\sigma,1}^d = \mathcal{NN}_\sigma^d$,
  with the set $\mathcal{NN}_\sigma^d$ of shallow complex-valued networks
  as defined in \Cref{sub:IntroductionResults}.
\end{rem*}

Our analysis of the universal approximation property for such deep networks will crucially
depend on the following closure properties of the network classes $\mathcal{NN}_{\sigma,L}^d$.
The (mainly technical) proof is deferred to \Cref{sub:NetworkClosurePropertiesProof}.

\begin{lemma}\label{lem:NetworkClosureProperties}
  Let $\sigma : \mathbb{C} \to \mathbb{C}$ and $d, L, T \in \mathbb{N}$.
  Then the following hold:
  \begin{enumerate}[label=\alph*)]
    \item \label{enu:NetworksVectorSpace}
          If $\Phi, \Psi \in \mathcal{NN}_{\sigma,L}^d$ and $\alpha, \beta \in \mathbb{C}$,
          then $\alpha \Phi + \beta \Psi \in \mathcal{NN}_{\sigma,L}^d$ as well.

    \item \label{enu:NetworksLowDimToHighDim}
          If $\Phi \in \mathcal{NN}_{\sigma,L}^1$ and $a \in \mathbb{C}^d$, $b \in \mathbb{C}$, then
          $\Xi : \mathbb{C}^d \to \mathbb{C}, z \mapsto \Phi(b + a^T z)$ satisfies
          $\Xi \in \mathcal{NN}_{\sigma,L}^d$.

    \item \label{enu:NetworksHighDimToLowDim}
          If $\Phi \in \mathcal{NN}_{\sigma,L}^d$ and $a,b \in \mathbb{C}^d$, then
          $\Xi : \mathbb{C} \to \mathbb{C}, z \mapsto \Phi(b + z a)$ satisfies $\Xi \in \mathcal{NN}_{\sigma,L}^1$.

    \item \label{enu:NetworksComposition}
          If $\Phi \in \mathcal{NN}_{\sigma,L}^d$ and $\Psi \in \mathcal{NN}_{\sigma,T}^1$,
          then $\Psi \circ \Phi \in \mathcal{NN}_{\sigma, L+T}^d$.
  \end{enumerate}
\end{lemma}

With these properties, we can now prove the ``sufficient part''
of \Cref{thm:DeepUniversalApproximationIntroduction}.
Precisely, we prove the following:

\begin{theorem}\label{thm:DeepNetworksSufficientCriterion}
  Let $\sigma \in \mathcal{M}$ and assume that \emph{none} of the following properties hold:
  \begin{enumerate}[label=\alph*)]
    \item we have $\sigma (z) = p(z, \overline{z})$ for almost all $z \in \mathbb{C}$,
          where $p \in \mathbb{C}[X,Y]$ is a complex polynomial of two variables,

    \item we have $\sigma = g$ almost everywhere or $\sigma = \overline{g}$ almost everywhere,
          where $g : \mathbb{C} \to \mathbb{C}$ is an entire function.
  \end{enumerate}
  Then we have $C(\mathbb{C}^d; \mathbb{C}) \subset \overline{\mathcal{NN}_{\sigma,L}^d}$ for arbitrary $d \in \mathbb{N}$
  and $L \in \mathbb{N}_{\geq 2}$.
\end{theorem}

\begin{proof}
  \textbf{Step 1:} \emph{(There are $\varphi_1, \varphi_2 \in C_c^\infty (\mathbb{C};\mathbb{R})$ satisfying
  $\partial (\varphi_1 \ast \sigma) \not \equiv 0$ and ${\overbar{\del} (\varphi_2 \ast \sigma) \not \equiv 0}$):}
  Assume towards a contradiction that this is false.
  Then there is a differential operator ${\delta \in \{ \partial, \overbar{\del} \}}$
  such that $\delta (\varphi \ast \sigma) \equiv 0$ for all $\varphi \in C_c^\infty(\mathbb{C};\mathbb{R})$.

  Define $\eta : \mathbb{C} \to \mathbb{R}$ via $\eta(z) := C \cdot \exp(1 / (|z|^2 - 1))$ if $|z| < 1$
  and $\eta(z) := 0$ otherwise, where $C > 0$ is chosen such that $\int_{\mathbb{C}} \eta(z) \, d z = 1$.
  Then it is shown in \cite[Section~C.5]{EvansPDE} that $\eta \in C_c^\infty (\mathbb{C}; \mathbb{R})$.
  For $\varepsilon > 0$ define $\eta_\varepsilon : \mathbb{C} \to \mathbb{R}, z \mapsto \varepsilon^{-2} \cdot \eta(z/\varepsilon)$
  and $\sigma_\varepsilon := \eta_\varepsilon \ast \sigma$.
  By assumption, we have $\delta \, \sigma_\varepsilon \equiv 0$.
  Thanks to \Cref{eq:WirtingerLaplaceRepresentation}, this implies in particular that
  $\Delta \sigma_\varepsilon \equiv 0$.

  Note that $\sigma$ is locally bounded and hence $\sigma \in L_{\mathrm{loc}}^1 (\mathbb{C} ; \mathbb{C})$,
  so that \cite[Theorem~7 in Appendix~C]{EvansPDE} shows $\sigma_\varepsilon \to \sigma$
  as $\varepsilon \downarrow 0$, with convergence in $L^{1}_{\mathrm{loc}}(\mathbb{C}; \mathbb{C})$.
  Using partial integration (which is justified since $\sigma_\varepsilon \in C^\infty(\mathbb{C}; \mathbb{C})$),
  we thus see for arbitrary $\varphi \in C_c^\infty(\mathbb{C}; \mathbb{R})$ that
  \begin{equation}
    \int_{\mathbb{C}}
      \sigma (z) \, \Delta \varphi(z)
    \, d z
    = \lim_{\varepsilon \downarrow 0}
      \int_{\mathbb{C}}
        \sigma_\varepsilon (z) \, \Delta \varphi(z)
      \, d z
    = \lim_{\varepsilon \downarrow 0}
      \int_{\mathbb{C}}
        \varphi(z) \, \Delta \sigma_\varepsilon (z)
      \, d z
    = 0 \, ;
    \label{eq:DeepNetworksWeakHarmonicity}
  \end{equation}
  that is, $\sigma$ is weakly harmonic.
  Thanks to \Cref{lem:WeaklyPolyharmonicIsPolyharmonic}, this implies $\sigma = g$ almost everywhere
  for a suitable function $g \in C^\infty (\mathbb{C}; \mathbb{C})$.
  Recalling that $\delta \in \{ \partial, \overbar{\del} \}$ and $\delta \, \sigma_\varepsilon \equiv 0$,
  we see for arbitrary $\varphi \in C_c^\infty (\mathbb{C}; \mathbb{R})$ via partial integration that
  \begin{equation}
    \begin{split}
      \int_{\mathbb{C}}
        \varphi(z) \delta g (z)
      \, d z
      & = - \int_{\mathbb{C}}
              g (z) \, \delta \, \varphi (z)
            \, d z
        = - \int_{\mathbb{C}}
              \sigma (z) \, \delta \, \varphi (z)
            \, d z \\
      & = - \lim_{\varepsilon \downarrow 0}
            \int_{\mathbb{C}}
              \sigma_\varepsilon (z) \, \delta \varphi (z)
            \, d z
        = \lim_{\varepsilon \downarrow 0}
          \int_{\mathbb{C}}
            \varphi(z) \, \delta \, \sigma_\varepsilon (z)
          \, d z
        = 0 .
    \end{split}
    \label{eq:DeepNetworksWeakDifferentialOperator}
  \end{equation}
  By the fundamental lemma of the calculus of variations (see for instance \cite[Lemma~4.22]{AltFA}),
  this implies $\delta \, g = 0$ almost everywhere, and then everywhere since $\delta \, g$
  is continuous.
  In case of $\delta = \overbar{\del}$ this implies that $g$ is holomorphic;
  see \Cref{sec:WirtingerCalculus}.
  Since $\sigma = g$ almost everywhere, $\sigma$ then coincides almost everywhere with a
  holomorphic function, in contradiction to our assumptions.
  If otherwise $\delta = \partial$, then $\overbar{\del} \overline{g} = \overline{\partial g} \equiv 0$,
  so that $h = \overline{g}$ is holomorphic and $\sigma = g = \overline{h}$ almost everywhere,
  again in contradiction to our assumptions.

  \medskip{}

  \noindent
  \textbf{Step 2:} \emph{(For each $m \in \mathbb{N}_0$, there is $\psi_m \in C_c^\infty(\mathbb{C}; \mathbb{R})$
  with $\partial^m (\psi_m \ast \sigma) \not\equiv 0$ or ${\overbar{\del}^m (\psi_m \ast \sigma) \not \equiv 0}$):}
  Assume towards a contradiction that this is false, meaning there is $m \in \mathbb{N}_0$ such that
  for each $\psi \in C_c^\infty(\mathbb{C}; \mathbb{R})$ we have $\partial^m (\psi \ast \sigma) \equiv 0$
  \emph{and} $\overbar{\del}^m (\psi \ast \sigma) \equiv 0$.
  Let $\eta, \eta_\varepsilon$, and $\sigma_\varepsilon$ as defined in Step~1 and note
  $\partial^m \sigma_\varepsilon \equiv 0 \equiv \overbar{\del}^m \sigma_\varepsilon$.
  Thanks to \Cref{eq:WirtingerLaplaceRepresentation} this implies
  $\Delta^m \sigma_\varepsilon = 4^m \partial^m \overbar{\del}^m \sigma_\varepsilon \equiv 0$.

  As in \Cref{eq:DeepNetworksWeakHarmonicity}, we thus see
  $\int_{\mathbb{C}} \sigma(z) \Delta^m \varphi (z) \, d z = 0$ for all $\varphi \in C_c^\infty(\mathbb{C};\mathbb{R})$,
  meaning that $\sigma$ is weakly polyharmonic of order $m$.
  Thanks to \Cref{lem:WeaklyPolyharmonicIsPolyharmonic}, this implies that there exists
  $g \in C^\infty(\mathbb{C}; \mathbb{R})$ satisfying $\sigma = g$ almost everywhere.
  Since $\partial^m \sigma_\varepsilon \equiv 0 \equiv \overbar{\del}^m \sigma_\varepsilon$ for all $\varepsilon > 0$,
  we see using similar arguments as in \Cref{eq:DeepNetworksWeakDifferentialOperator}
  that $\partial^m g \equiv 0 \equiv \overbar{\del}^m g$.
  The condition $\overbar{\del}^m g \equiv 0$ means that $g$ is \emph{polyanalytic of order $m$};
  see \cite[Equation~(1.3)]{BalkPolyanalyticFunctions}.
  As shown in \cite[Bottom of Page 10]{BalkPolyanalyticFunctions}, this implies that we can write
  $g(z) = \sum_{k=0}^{m-1} \overline{z}^k \, a_k (z)$ for all $z \in \mathbb{C}$,
  with holomorphic functions $a_k : \mathbb{C} \to \mathbb{C}$.

  \smallskip{}

  Denoting by $a_k^{(m)}$ the \emph{complex} derivative of $a_k$ of order $m$,
  we claim that $a_k^{(m)} \equiv 0$ for all ${k \in \{ 0,\dots,m-1 \}}$.
  Assume towards a contradiction that this is not so, and let ${K \in \{ 0,\dots,m-1 \}}$
  be maximal with $a_K^{(m)} \not\equiv 0$.
  Since $\overbar{\del} f \equiv 0$ and $\partial f = f'$ for each holomorphic function $f$
  (with $f'$ denoting the complex derivative of $f$), we have
  $\overbar{\del} a_k(z) \equiv 0$ and $\partial \bar{z}^k = \overline{\overbar{\del} z^k} \equiv 0$
  as well as $\partial^m a_k (z) = a_k^{(m)} (z)$ and $\overbar{\del}^K \bar{z}^k = \overline{\partial^K z^k} = 0$
  for $k < K$, while $\overbar{\del}^K \bar{z}^K = \overline{\partial^K z^K} = K!$.
  Combining this with the product rule for Wirtinger derivatives (see \Cref{sec:WirtingerCalculus}
  and in particular \Cref{eq:SpecialProductRule}) and recalling the maximality of $K$,
  we see because of $\partial^m g \equiv 0$ that
  \[
    0
    = \overbar{\del}^K \partial^m g(z)
    = \sum_{k=0}^{m-1}
        \big[
          (\overbar{\del}^K \bar{z}^k) \cdot a_k^{(m)}(z)
        \big]
    = \sum_{k=0}^{K}
        \big[
          (\overbar{\del}^K \bar{z}^k) \cdot a_k^{(m)}(z)
        \big]
    = K! \cdot a_K^{(m)} (z) ,
  \]
  in contradiction to $a_K^{(m)} \not\equiv 0$.

  Overall, we see that each $a_k$ is holomorphic with $a_k^{(m)} \equiv 0$.
  Thus, $a_k (z) = \sum_{j=0}^{m-1} a_{k,j} \, z^j$ is a polynomial of degree at most $m - 1$,
  and hence $g(z) = \sum_{k,j=0}^{m-1} a_{k,j} \bar{z}^k z^j$
  for suitable coefficients $a_{k,j} \in \mathbb{C}$.
  Since $\sigma = g$ almost everywhere, this means that $\sigma$ coincides almost everywhere
  with a polynomial in $z$ and $\bar{z}$, contradicting our assumptions.

  \medskip{}

  \noindent
  \textbf{Step 3:} With $\sigma_{a,b}$ as in \Cref{eq:TranslationDilation}, let us define
  \[
    W := \operatorname{span}_{\mathbb{C}}
         \big\{
           \varphi \ast \sigma_{a,b}
           \,\, \colon \,\,
           a,b \in \mathbb{C} \text{ and } \varphi \in C_c^\infty(\mathbb{C}; \mathbb{R})
         \big\}
      \subset C^\infty (\mathbb{C}; \mathbb{C}).
  \]
  Furthermore, define $\zeta_m : \mathbb{C} \to \mathbb{C}, z \mapsto z^m$ for $m \in \mathbb{N}_0$
  and $R : \mathbb{C} \to \mathbb{C}, z \mapsto \Re z$, as well as $\mathrm{id}_{\mathbb{C}} : \mathbb{C} \to \mathbb{C}, z \mapsto z$.
  In this step we show that $W$ is closed under dilations and translations and,
  denoting the closure of $W$ with respect to locally uniform convergence by $\overline{W}$, that
  \begin{equation}
    \mathrm{id}_{\mathbb{C}}, R \in \overline{W}
    \qquad \text{and} \qquad
    \forall \, m \in \mathbb{N}_0 : \quad
      \zeta_m \in \overline{W} \text{ or } \overline{\zeta_m} \in \overline{W} .
    \label{eq:DeepNetworksWRichness}
  \end{equation}

  To see this, first note that our assumptions on $\sigma$ imply $\sigma \not\equiv 0$;
  choosing $b \in \mathbb{C}$ with $\sigma(b) \neq 0$, we thus see $\sigma_{0,b} \equiv \sigma(b) \neq 0$
  and hence (with $\eta$ as in Step~1) $W \ni \eta \ast \sigma_{0,b} \equiv \sigma(b) \neq 0$ as well.
  In other words, $W$ contains the constant functions.
  To see that $W$ is closed under translations and dilations, let $\varphi \in C_c^\infty(\mathbb{C};\mathbb{R})$
  and $a,b, \alpha,\beta \in \mathbb{C}$ be arbitrary.
  In case of $\alpha = 0$, the function $z \mapsto (\varphi \ast \sigma_{a,b})(\beta + \alpha z)$
  is a constant function and thus belongs to $W$, as we just saw.
  Otherwise if $\alpha \neq 0$, then the calculation in \Cref{eq:ConvolutionTransformation}
  shows for $\varphi_\alpha (z) := \varphi (\alpha z)$ that
  \(
    (\varphi \ast \sigma_{a,b}) (\alpha z + \beta)
    = |\alpha|^2 \cdot
      \bigl(
        \varphi_\alpha \ast (\sigma_{a,b})_{\alpha,\beta}
      \bigr) (z) .
  \)
  Since $\varphi_\alpha \in C_c^\infty (\mathbb{C}; \mathbb{R})$ and
  $(\sigma_{a,b})_{\alpha,\beta} = \sigma_{a \alpha, b + a \beta}$,
  this implies $\big( z \mapsto  (\varphi \ast \sigma_{a,b}) (\alpha z + \beta)\big) \in W$,
  which easily shows that $W$ is closed under dilations and translations.

  To prove \Cref{eq:DeepNetworksWRichness}, first recall from Step~1 that
  $\partial (\varphi_1 \ast \sigma)(\theta_1) \neq 0 \neq \overbar{\del} (\varphi_2 \ast \sigma) (\theta_2)$
  for certain $\theta_1, \theta_2 \in \mathbb{C}$.
  Since $\varphi_1 \ast \sigma, \varphi_2 \ast \sigma \in W$, an easy application of
  \Cref{lem:MonomialExtraction} shows that $\mathrm{id}_{\mathbb{C}}, \overline{\mathrm{id}_{\mathbb{C}}} \in \overline{W}$
  and hence $R = \frac{1}{2} (\mathrm{id}_{\mathbb{C}} + \overline{\mathrm{id}_{\mathbb{C}}}) \in \overline{W}$.
  Similarly, with $\psi_m$ as in Step~2, we can choose for each $m \in \mathbb{N}_0$ some $\lambda_m \in \mathbb{C}$
  such that $[\partial^m (\psi_m \ast \sigma)](\lambda_m) \neq 0$
  or $\bigl[\overbar{\del}^m (\psi_m \ast \sigma)\bigr](\lambda_m) \neq 0$.
  In the first case, \Cref{lem:MonomialExtraction} shows $\zeta_m \in \overline{W}$,
  while in the second case $\overline{\zeta_m} \in \overline{W}$.

  \medskip{}

  \noindent
  \textbf{Step 4:} \emph{(Showing that $\varrho_{\mathbb{C}} \in \overline{\mathcal{NN}_{\sigma,2}^1}$
  with $\varrho_\mathbb{C}$ as in \Cref{lem:FromOneDimensionToHigherDimensions}):}
  Let $\varepsilon,r > 0$; we want to construct $\Gamma \in \mathcal{NN}_{\sigma,2}^1$ satisfying
  $\| \varrho_{\mathbb{C}} - \Gamma \|_{L^\infty (\overline{B_r}(0))} \leq \varepsilon$.

  First of all, note that \Cref{lem:ConvolutionApproximation} shows for arbitrary
  $\varphi \in C_c^\infty(\mathbb{C}; \mathbb{R})$ and $a,b \in \mathbb{C}$ because of $\sigma_{a,b} \in \mathcal{M}$ that
  \(
    \varphi \ast \sigma_{a,b}
    \subset \overline{
              \operatorname{span}_{\mathbb{C}}
              \{
                T_z \sigma_{a,b}
                \colon
                z \in \mathbb{C}
              \}
            }
    \subset \overline{\mathcal{NN}_{\sigma,1}^1} .
  \)
  By definition of $W$, this easily implies $\overline{W} \subset \overline{\mathcal{NN}_{\sigma,1}^1}$.
  Next, since $\varrho : \mathbb{R} \to \mathbb{R}, x \mapsto \max \{ 0, x \}$ is continuous,
  the classical Stone-Weierstraß theorem
  (see \cite[Theorem~7.26]{RudinPrinciplesOfMathematicalAnalysis}) shows that there is a polynomial
  ${p(x) = \sum_{n=0}^N a_n \, x^n}$ (with $N \in \mathbb{N}$ and $a_0,\dots,a_N \in \mathbb{R}$) satisfying
  $|\varrho(x) - p(x)| \leq \frac{\varepsilon}{3}$ for all $x \in [-r, r]$.

  For each $m \in \mathbb{N}_0$ let us choose $\theta_m \in \{ \zeta_m, \overline{\zeta_m} \}$
  with $\theta_m \in \overline{W} \subset \overline{\mathcal{NN}_{\sigma,1}^1}$; this is possible
  by \Cref{eq:DeepNetworksWRichness}.
  Since $\mathcal{NN}_{\sigma,1}^1$ is a vector space, we thus see
  $f := \sum_{n=0}^N a_n \theta_n \in \overline{\mathcal{NN}_{\sigma,1}^1}$;
  hence, there exists $\Phi \in \mathcal{NN}_{\sigma,1}^1$ satisfying
  $\| \Phi - f \|_{L^\infty(\overline{B_{r+1}}(0))} \leq \frac{\varepsilon}{3}$.
  Since $f$ is continuous, it is uniformly continuous on $\overline{B_{r+1}}(0)$;
  we can thus choose $\delta \in (0,1)$ such that $|f(z) - f(w)| \leq \frac{\varepsilon}{3}$
  for all $z,w \in \overline{B_{r+1}}(0)$ with $|z - w| \leq \delta$.
  Note furthermore that $\zeta_m (z) = \overline{\zeta_m (z)} = z^m$ for $z \in \mathbb{R}$,
  and hence $f(z) = p(z)$ for all $z \in \mathbb{R}$.

  Finally, since $R \in \overline{W} \subset \overline{\mathcal{NN}_{\sigma,1}^1}$
  by \Cref{eq:DeepNetworksWRichness}, we can choose $\Psi \in \mathcal{NN}_{\sigma,1}^1$ satisfying
  $|R(z) - \Psi(z)| \leq \delta \leq 1$ for all $z \in \overline{B_r}(0)$.
  Because of $|R(z)| = |\Re z| \leq |z| \leq r$, this implies $\Psi(z) \in \overline{B_{r+1}}(0)$
  for $z \in \overline{B_r}(0)$.
  Summarizing all the obtained estimates, we finally see for $z \in \overline{B_r}(0)$ that
  \[
    \bigl|\varrho_{\mathbb{C}}(z) - (\Phi \circ \Psi)(z)\bigr|
    \leq \bigl|\varrho(R (z)) - f(R(z))\bigr|
         + \big| f(R(z)) - f(\Psi(z)) \big|
         + \big| f(\Psi(z)) - \Phi(\Psi(z)) \big|
    \leq \varepsilon .
  \]
  Since $\Gamma := \Phi \circ \Psi \in \mathcal{NN}_{\sigma,2}^1$
  by \Cref{lem:NetworkClosureProperties} \ref{enu:NetworksComposition},
  this implies $\varrho_{\mathbb{C}} \in \overline{\mathcal{NN}_{\sigma,2}^1}$, as claimed.

  \medskip{}

  \noindent
  \textbf{Step 5:} \emph{(Completing the proof):}
  Let $L \in \mathbb{N}_{\geq 2}$ and $d \in \mathbb{N}$.
  With $f^{(a,b)}$ as defined in \Cref{lem:FromOneDimensionToHigherDimensions},
  \Cref{lem:NetworkClosureProperties} shows that
  $\mathcal{G} := \mathcal{NN}_{\sigma,L}^d \subset \{ g : \mathbb{C}^d \to \mathbb{C} \}$
  is a (complex) vector space that satisfies $f^{(a,b)} \in \mathcal{NN}_{\sigma,L}^d$ for all
  $f \in \mathcal{F} := \mathcal{NN}_{\sigma,L}^1$, $b \in \mathbb{C}$ and $a \in \mathbb{C}^d$.
  Therefore, \Cref{lem:FromOneDimensionToHigherDimensions} shows that it is enough to prove
  $\varrho_{\mathbb{C}} \in \overline{\mathcal{NN}_{\sigma,L}^1}$.
  In case of $L = 2$, this was shown in Step~4; thus, let us assume $L > 2$.

  Since \Cref{eq:DeepNetworksWRichness} shows
  $\mathrm{id}_{\mathbb{C}} \in \overline{W} \subset \overline{\mathcal{NN}_{\sigma,1}^1}$,
  there is a sequence ${(\Phi_n)_{n \in \mathbb{N}} \subset \mathcal{NN}_{\sigma,1}^1}$
  satisfying $\Phi_n \to \mathrm{id}_{\mathbb{C}}$ locally uniformly on $\mathbb{C}$.
  Furthermore, by Step~4 we can choose a sequence $(\Psi_n)_{n \in \mathbb{N}} \subset \mathcal{NN}_{\sigma,2}^1$
  satisfying $\Psi_n \to \varrho_{\mathbb{C}}$ locally uniformly.
  Since the limit functions are continuous, this easily implies
  \(
    \Phi_n \circ \cdots \circ \Phi_n \circ \Psi_n
    \to \mathrm{id}_{\mathbb{C}} \circ \cdots \circ \mathrm{id}_{\mathbb{C}} \circ \varrho_{\mathbb{C}}
    = \varrho_{\mathbb{C}}
  \)
  with locally uniform convergence, where $\Phi_n$ appears $L-2$ times in the composition.
  A formal argument for the claimed convergence is given in
  \cite[Lemma~A.7]{GribonvalNNApproximationSpaces}.
  Since $\Phi_n \circ \cdots \circ \Phi_n \circ \Psi_n \in \mathcal{NN}_{\sigma,L}^1$ by
  \Cref{lem:NetworkClosureProperties} \ref{enu:NetworksComposition}, we are done.
\end{proof}



\subsection{Necessity for deep networks}%
\label{sub:NecessityDeep}

The following result contains the ``necessary'' part
of \Cref{thm:DeepUniversalApproximationIntroduction};
precisely, it shows that those activation functions $\sigma$
that are excluded in the sufficient criterion of \Cref{thm:DeepNetworksSufficientCriterion}
indeed do \emph{not} yield universal network classes,
at least if one assumes a priori that $\sigma$ is continuous.
As we will see in \Cref{exa:PathologicalUniversalSigma} below,
this continuity assumption can not simply be dropped,
and is thus not just a proof artifact.

\begin{theorem}\label{thm:DeepNetworksNecessaryCriterion}
  Let $\sigma : \mathbb{C} \to \mathbb{C}$ be continuous and $d,L \in \mathbb{N}$.
  Assume that (at least) one of the following properties is satisfied:
  \begin{enumerate}[label=\alph*)]
    \item we have $\sigma (z) = p(z, \overline{z})$ for almost all $z \in \mathbb{C}$,
          where $p \in \mathbb{C}[X,Y]$ is a complex polynomial of two variables,

    \item we have $\sigma = g$ almost everywhere or $\sigma = \overline{g}$ almost everywhere,
          where $g : \mathbb{C} \to \mathbb{C}$ is an entire function.
  \end{enumerate}
  Then there exist $f \in C_c(\mathbb{C}^d;\mathbb{R})$ and $\varepsilon > 0$ with $\| f - \Phi \|_{L^1(B_1(0))} \geq \varepsilon$
  for all $\Phi \in \mathcal{NN}_{\sigma,L}^d$.
  In particular, $C(\mathbb{C}^d; \mathbb{C}) \nsubseteq \overline{\mathcal{NN}_{\sigma,L}^d}$.
\end{theorem}

\begin{proof}
  Since $\sigma$ is continuous, the identities $\sigma(z) = p(z, \bar{z})$ or $\sigma(z) = g(z)$
  or $\sigma(z) = \overline{g(z)}$ hold everywhere, not only almost everywhere.
  In particular, $\sigma \in C^\infty(\mathbb{C}; \mathbb{C})$, which easily implies
  $\mathcal{NN}_{\sigma,L}^1 \subset C^\infty (\mathbb{C}; \mathbb{C})$ as well.
  We will show below that there is some $m = m(\sigma,L) \in \mathbb{N}$ such that
  \begin{equation}
    \forall \, \Psi \in \mathcal{NN}_{\sigma,L}^1 : \quad \Delta^m \Psi \equiv 0.
    \label{eq:DeepNetworksNecessityPolyharmonicity}
  \end{equation}
  Once this is shown, \Cref{lem:NetworkClosureProperties} \ref{enu:NetworksHighDimToLowDim}
  shows for every $\Phi \in \mathcal{NN}_{\sigma,L}^d$ and arbitrary $w \in \mathbb{C}^{d-1}$ that
  if we set $e_1 = (1,0,\dots,0) \in \mathbb{C}^d$ and
  $\Psi : \mathbb{C} \to \mathbb{C}, z \mapsto \Phi(z,w) = \Phi \big( (0,w) + z \, e_1 \big)$,
  then $\Psi \in \mathcal{NN}_{\sigma,L}^1$ and hence $\Psi \in C^\infty(\mathbb{C};\mathbb{C})$
  and $\Delta^m \Psi \equiv 0$.
  Then, a straightforward application of \Cref{lem:PolyharmonicityObstructsUniversality}
  yields the claim of the theorem.

  The (somewhat technical) proof of \Cref{eq:DeepNetworksNecessityPolyharmonicity} is deferred
  to the appendix.
  The intuition is that if $\sigma$ is holomorphic or antiholomorphic,
  then each $\Psi \in \mathcal{NN}_{\sigma,L}^1$ will be holomorphic or antiholomorphic,
  so that $\Delta \Psi \equiv 0$.
  Likewise, if $\sigma(z) = p(z, \overline{z})$ is a polynomial, then each
  $\Psi \in \mathcal{NN}_{\sigma,L}^1$ will be a polynomial in $z,\bar{z}$ of fixed degree $N = N(p,L)$,
  and hence $\Delta^{N+1} \Psi \equiv 0$.
  A more formal argument is given in \Cref{sub:AppendixDeepNetworksNecessityPolyharmonicity}.
\end{proof}

The following example presents an activation function $\sigma \in \mathcal{M}$
that coincides almost everywhere with a polynomial, but for which
$\mathcal{NN}_{\sigma,L}^d$ is nevertheless universal for any $L \geq 2$.

\begin{example}\label{exa:PathologicalUniversalSigma}
  Let $\varrho_{\mathbb{C}} : \mathbb{C} \to \mathbb{C}, z \mapsto \max \{ 0, \Re z \}$
  as in \Cref{lem:FromOneDimensionToHigherDimensions}.
  Define
  \[
    \sigma : \quad
    \mathbb{C} \to \mathbb{C}, \quad
    z \mapsto \begin{cases}
                \Re z,            & \text{if } z \notin \mathbb{R} , \\
                \varrho_{\mathbb{C}}(z), & \text{if } z \in \mathbb{R} .
              \end{cases}
  \]
  Clearly, $\sigma$ is locally bounded.
  Moreover, we have $N := \{ z \in \mathbb{C} \colon \sigma \text{ not continuous at } z \} \subset \mathbb{R}$,
  so that the closure $\overline{N} \subset \mathbb{R}$ is a null-set when considered as a subset of $\mathbb{C}$;
  therefore, $\sigma \in \mathcal{M}$.
  Next, note that $\sigma(z) = \Re z = z + \bar{z}$ for almost all $z \in \mathbb{C}$
  (namely, for all $z \in \mathbb{C} \setminus \mathbb{R}$),
  so that $\sigma$ satisfies the first condition of \Cref{thm:DeepNetworksNecessaryCriterion}.

  Nevertheless, it is straightforward to verify that
  $\sigma \circ \cdots \circ \sigma = \varrho_{\mathbb{C}}$,
  whenever $\sigma$ appears at least twice in the composition.
  In view of \Cref{lem:NetworkClosureProperties} \ref{enu:NetworksComposition},
  we thus see $\varrho_{\mathbb{C}} \in \mathcal{NN}_{\sigma,L}^1$ whenever $L \in \mathbb{N}_{\geq 2}$.
  Via a straightforward application of \Cref{lem:FromOneDimensionToHigherDimensions},
  this implies $C(\mathbb{C}^d; \mathbb{C}) \subset \overline{\mathcal{NN}_{\sigma,L}^d}$
  for all $d \in \mathbb{N}$ and $L \in \mathbb{N}_{\geq 2}$.

  This example shows that in the necessary condition for the universality of deeper networks
  (\Cref{thm:DeepNetworksNecessaryCriterion}), one cannot simply relax the continuity assumption
  by instead assuming that $\sigma \in \mathcal{M}$.
\end{example}


