# Expressivity of Neural Networks via Chaotic Itineraries
beyond Sharkovsky’s Theorem

Clayton Sanford Vaggos Chatziafratis Columbia University,
<EMAIL_ADDRESS>University, vaggos@{northwestern,
cs.stanford, ucsc}.edu. Part of this work was done while the author was
supported by Northwestern University.

Given a target function $f$, how large must a neural network be in order to
approximate $f$? Recent works examine this basic question on neural network
expressivity from the lens of dynamical systems and provide novel “depth-vs-
width” tradeoffs for a large family of functions $f$. They suggest that such
tradeoffs are governed by the existence of periodic points or _cycles_ in $f$.
Our work, by further deploying dynamical systems concepts, illuminates a more
subtle connection between periodicity and expressivity: we prove that periodic
points alone lead to suboptimal depth-width tradeoffs and we improve upon them
by demonstrating that certain “chaotic itineraries” give stronger exponential
tradeoffs, even in regimes where previous analyses only imply polynomial gaps.
Contrary to prior works, our bounds are nearly-optimal, tighten as the period
increases, and handle strong notions of inapproximability (e.g., constant
$L_{1}$ error). More broadly, we identify a phase transition to the chaotic
regime that exactly coincides with an abrupt shift in other notions of
function complexity, including VC-dimension and topological entropy.

##  1 Introduction

Whether a neural network (NN) succeeds or fails at a given task crucially
depends on whether or not its architecture (depth, width, types of activation
units etc.) is suitable for the task at hand. For example, a “size-inflation”
phenomenon has occurred in recent years, in which NNs tend to be deeper and/or
larger. Recall that in 2012, AlexNet had 8 layers. In 2015, ResNet won the
ImageNet competition with 152 layers (Krizhevsky et al., 2012; He et al.,
2016), This trend still continues to date, with modern models using billions
of parameters (Brown et al., 2020). The empirical success of deep neural
networks motivates researchers to ask: What are the theoretical benefits of
depth, and what are the depth-vs-width tradeoffs?

This question gives rise to the study of neural network expressivity, which
characterizes the class of functions that are representable (or approximately
representable) by a NN of certain depth, width, and activation. For instance,
Eldan and Shamir (2016) propose a family of “radial” functions in
$\mathbb{R}^{d}$ that are easily expressible with 3-layered feedforward neural
nets of small width, but require any approximating 2-layer network to have
exponentially (in $d$) many neurons. In other words, they formally show that
depth—even if increased by 1—can be exponentially more valuable than width.

Not surprisingly, understanding the expressivity of NNs was an early question
asked in 1969, when Minsky and Papert showed that the Perceptron can only
learn linearly separable data and fails on simple XOR functions (Minsky and
Papert, 1969). The natural question of which functions can multiple such
Perceptrons (i.e., multilayer feedforward NN) express was addressed later by
Cybenko (1989); Hornik et al. (1989) proving the so-called universal
approximation theorem. This states, roughly, that just one hidden layer of
standard activation units (e.g., sigmoids, ReLUs etc.) suffices to approximate
any continuous function arbitrarily well. Taken at face value, any continuous
function is a 2-layer (i.e., 1-hidden-layer) network in disguise, and hence,
there is no reason to consider deeper networks. However, the width required
can grow arbitrarily, and many works in the following decades quantify those
depth-vs-width tradeoffs.

Towards this direction, one typically identifies a function together with a
“measure of complexity” to demonstrate benefits of depth. For example, the
seminal work by Telgarsky (2015, 2016) relies on the number of oscillations of
a simple triangular wave function. Other relevant notions of complexity to the
expressivity of NNs include the VC dimension (Warren, 1968; Anthony and
Bartlett, 1999; Schmitt, 2000), the number of linear regions (Montufar et al.,
2014; Arora et al., 2016) or activation patterns (Hanin and Rolnick, 2019),
the dimension of algebraic varieties (Kileel et al., 2019), the Fourier
spectrum (Barron, 1993; Eldan and Shamir, 2016; Daniely, 2017; Lee et al.,
2017; Bresler and Nagaraj, 2020), fractals (Malach and Shalev-Shwartz, 2019),
topological entropy (Bu et al., 2020), Lipschitzness (Safran et al., 2019; Hsu
et al., 2021), global curvature and trajectory length (Poole et al., 2016;
Raghu et al., 2017) just to name a few.

This work builds upon recent papers (Chatziafratis et al., 2019, 2020), which
study expressivity from the lens of discrete-time dynamical systems and extend
Telgarsky’s results beyond triangle (tent) maps. At a high-level, their idea
is the following: if the initial layers of a NN output a real-valued function
$f$, then concatenating the same layers $k$ times one after the other outputs
$f^{k}\vcentcolon=f\circ f\circ\ldots\circ f$, i.e., the composition of $f$
with itself $k$ times. By associating each discrete timestep $k$ to the output
of the corresponding layer in the network, one can study expressivity via the
underlying properties of $f$’s trajectories. Indeed, if $f$ contains higher-
order fixed points, called periodic points, then deeper NNs can efficiently
approximate $f^{k}$, but shallower nets would require exponential width,
governed by $f$’s periodicity.

Inspired by these novel connections to discrete dynamical systems, we pose the
following natural question:

Apart from periodicity, are there other properties of $f$’s trajectories
governing the expressivity tradeoffs?

We indeed prove that $f$’s periodicity alone is not the end of the story, and
we improve on the known depth-width tradeoffs from several perspectives. We
exhibit functions of the same period with very different behaviors (see Sec.
2) that can be distinguished by the concept of “chaotic itineraries.” We
analyze these here in order to achieve nearly-optimal tradeoffs for NNs. Our
work highlights why previous works that examine periodicity alone only obtain
loose bounds. More specifically:

  * •

We accurately quantify the oscillatory behavior of a large family of functions
$f$. This leads to sharper and nearly-optimal lower bounds for the width of
NNs that approximate $f^{k}$.

  * •

Our lower bounds cover a stronger notion of approximation error, i.e.,
constant separations between NNs, instead of bounds that become small
depending heavily on $f$ and its periodicity.

  * •

At a conceptual level, we introduce and study certain chaotic itineraries,
which supersede Sharkovsky’s theorem (see Sec. 1.2).

  * •

We elucidate connections between periodicity and other function complexity
measures like the VC-dimension and the topological entropy (Alsedà et al.,
2000). We show that all of these measures undergo a phase transition that
exactly coincides with the emergence of the chaotic regime based on periods.

To the best of our knowledge, we are the first to incorporate the notion of
chaotic itineraries from discrete dynamical systems into the study of NN
expressivity. Other related works that have previously used ideas from chaotic
dynamical systems (e.g., Li-Yorke chaos) to show the convergence (or not) of
standard optimization methods, e.g., gradient descent, multiplicative weights
update algorithm, include Lee et al. (2019); Palaiopanos et al. (2017). Before
stating and interpreting our results, we provide some basic definitions.

###  1.1 Function Approximation and NNs

This paper employs three notions of approximation to compare functions
$f,g:[0,1]\to[0,1]$.

  * •

$L_{1}(f,g)=\left\|f-g\right\|_{1}=\int_{0}^{1}\left|f(x)-g(x)\right|dx.$

  * •

$L_{\infty}(f,g)=\left\|f-g\right\|_{\infty}=\sup_{x\in[0,1]}\left|f(x)-g(x)\right|.$

  * •

Classification error $\mathcal{R}_{S,t}$: For $t\in[0,1]$, let
$[[x]]_{t}=\mathbbm{1}\left\\{x\geq t\right\\}$. Let
$S=\\{x_{1},\dots,x_{n}\\}\subseteq[0,1]$. Then,
$\mathcal{R}_{S,t}(f,g)=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\left\\{[[f(x_{i})]]_{t}\neq[[g(x_{i})]]_{t}\right\\}.$

For what follows, let $\mathcal{N}(u,\ell)$ be the family of feedforward NNs
of depth $\ell$ and width at most $u$ per layer with ReLU activation
functions.111Recall ReLU$(x)=\max(x,0)$. All our results also hold for the
more general family of semialgebraic activations (Telgarsky, 2016).

###  1.2 Discrete Dynamical Systems

To construct families of functions that yield depth-separation results, we
rely on a standard notion of unimodal functions from dynamical systems
(Metropolis et al., 1973).

######  Definition 1.

Let $f:[0,1]\to[0,1]$ be a continuous and piece-wise differentiable function.
We say $f$ is a _unimodal mapping_ if:

  1. 1.

$f(0)=f(1)=0$, and $f(x)>0$ for all $x\in(0,1)$.

  2. 2.

There exists a unique maximizer $x^{\prime}\in(0,1)$ of $f$, i.e., $f$ is
strictly increasing on the interval $[0,x^{\prime})$ and strictly decreasing
on $(x^{\prime},1]$.

Our constructions rely on unimodal functions that are concave and also
symmetric (i.e., $f(x)=f(1-x)$ for all $x\in[0,1]$). We note that the
resulting function family is fairly general, already capturing the triangle
waves of Telgarsky (2015, 2016) and the logistic map used in previous depth-
separation results (Schmitt, 2000). Moreover, the study of one-dimensional
discrete dynamical systems by applied mathematicians explicitly identifies
unimodal mappings as important objects of study (Metropolis et al., 1973;
Alsedà et al., 2000).

Recall that a fixed point $x^{*}$ of $f$ is a point where $f(x^{*})=x^{*}$. A
more general notion of higher-order fixed points is that of periodicity.

######  Definition 2.

For some $p\in\mathbb{N}$, we say that $x_{1},\dots,x_{p}\in[0,1]$ is a _$p$
-cycle_ if $f(x_{j})=x_{j+1}$ for all $j\in[p-1]$ and $f(x_{p})=x_{1}$. We say
that $f$ has _periodicity_ $p$ if such a cycle exists and that $x_{1}$ is a
_point of period $p$_ if $x_{1}$ belongs to a $p$-cycle. Equivalently, $x_{1}$
is a point of period $p$ if $f^{p}(x_{1})=x_{1}$ and $f^{k}(x_{1})\neq
x_{1}$222Throughout the paper, $f^{k}$ means composition of $f$ with itself
$k$ times. for all $k\in[p-1]$.333As is common, $[m]=\\{1,2,\dots,m\\}$.

Does the existence of some $p$-cycle in $f$ have any implications about the
existence of other cycles? These relations between the periods of $f$ are of
fundamental importance to the study of dynamical systems. In particular, Li
and Yorke (1975) proved in 1975 that “period 3 implies chaos” in their
celebrated work, which also introduced the term “chaos” to mathematics and
later spurred the development of chaos theory. Interestingly, an even more
general result was already obtained a decade earlier in Eastern Europe, by
Sharkovsky (1964, 1965):

######  Theorem 1 (Sharkovsky’s Theorem).

Let $f:[0,1]\to[0,1]$ be continuous. If $f$ contains period $p$ and
$p\triangleright p^{\prime}$, then $f$ also contains period $p^{\prime}$,
where the symbol “ $\triangleright$” is defined based on the following
(decreasing) ordering:

$3\triangleright 5\triangleright 7\triangleright\ldots\triangleright 2\cdot
3\triangleright 2\cdot 5\triangleright 2\cdot 7\triangleright\ldots$
$\ldots\triangleright 2^{2}\cdot 3\triangleright 2^{2}\cdot 5\triangleright
2^{2}\cdot 7\triangleright\ldots\triangleright 2^{3}\triangleright
2^{2}\triangleright 2\triangleright 1.$

This ordering, called Sharkovsky’s ordering, is a total ordering on the
natural numbers, where $l\triangleright r$ whenever $l$ is to the left of $r$.
The maximum number in this ordering is 3; if $f$ contains period 3, then it
also has all other periods, which is also known as _Li-Yorke chaos_.
Chatziafratis et al. (2019, 2020) apply this theorem to obtain depth-width
tradeoffs based on periods and obtain their most powerful results when $p=3$.
We go beyond Sharkovsky’s theorem and prove that tradeoffs are determined by
the “itineraries” of periods.444These are called “patterns” in Alsedà et al.
(2000).

######  Definition 3 (Itineraries).

For a $p$-cycle $x_{1},\dots,x_{p}$, suppose that $x_{a_{1}}<\dots<x_{a_{p}}$
for $a_{j}\in[p]$. The _itinerary_ of the cycle is the cyclic permutation of
$x_{a_{1}},\dots,x_{a_{p}}$ induced by $f$, which we represent by the string
$\mathbf{a}=a_{1}\dots a_{p}$. Because cyclic permutations are invariant to
rotation, we assume (wlog) that $a_{1}=1$.

######  Definition 4 (Chaotic Itineraries).

A $p$-cycle is a _chaotic itinerary_ or an _increasing cycle_ if its itinerary
is $12\dots p$. That is, $x_{1}<\dots<x_{p}$.

Examining chaotic itineraries circumvents the limitations of prior works based
on periods and yields sharper exponential depth-width tradeoffs. Unlike other
function complexity properties, the existence of a chaotic itinerary is easily
verifiable (see App. B.3). To grasp clean examples of itineraries, see App.
B.1.

###  1.3 Our Main Contributions

Our principal goal is to use knowledge about $f$’s itineraries to more
accurately quantify the “oscillations” of $f^{k}$ as a measure of complexity
and draw connections to other complexity measures. Section 3 produces sharper
and more robust NN approximability tradeoffs than prior works by leveraging
chaotic itineraries and unimodality. Section 4 shows how a phase transition in
VC-dimension and topological entropy of $f$ occurs exactly when the growth
rate of oscillations shifts from polynomial to exponential.

While previous works count oscillations too, they either construct too narrow
a range of functions555e.g., Telgarsky (2015, 2016) only analyzes triangles.,
obtain loose depth-width tradeoffs666e.g., Chatziafratis et al. (2019, 2020)
have a suboptimal dependence on $p$ under stringent Lipschitz assumptions., or
have unsatisfactory approximation error. 777e.g., Chatziafratis et al. (2019,
2020); Bu et al. (2020) do not obtain constant error rates. In Section 3, we
improve along these three directions by taking advantage of the unimodality
and itineraries of $f$. The unimodality of $f$ allows us to quantify both the
number of piecewise monotone pieces of $f^{k}$ (i.e., oscillations) and the
corresponding height between the highest and lowest values of $f^{k}$’s
oscillations. This improvement on the height enables stronger notions of
function approximation (e.g., constant error rates with no dependence on $f$
or its period $p$). Chaotic itineraries allow an improved analysis of the
number of oscillations in $f^{k}$ and grant sharper exponential lower bounds
on the width of any shallow net $g$ approximating $f^{k}$.

We say that our results are nearly-optimal because we exhibit a broad family
of functions $f$ that are inapproximable by shallow networks of width
$O(\rho^{k})$ for $\rho$ arbitrarily close to 2. Because no unimodal function
$f$ can induce more than $2^{k}$ oscillations in $f^{k}$, we cannot aspire to
tighter exponent bases in this setting.888Our results also transfer to non-
unimodal functions via the observation that for bimodal $g$, there is some
unimodal $f$ such that the number of oscillations of $g$ is at most twice
those of $f$. On the other hand, none of the bounds from previous works
(except the narrow bounds of Telgarsky) produce width bounds of more than
$\Omega(\phi^{k})$, where $\phi\approx 1.618$ is the Golden Ratio. To
demonstrate our sharper tradeoffs, we state a special case of our results for
the $L_{\infty}$ error.

######  Theorem 2.

For $p\geq 3$ and $k\in\mathbb{N}$, consider any symmetric, concave unimodal
mapping $f$ with an increasing $p$-cycle and any $g\in\mathcal{N}(u,\ell)$
with width

$u\leq\frac{1}{8}\left(\max\left(2-\frac{4}{2^{p}},\phi\right)\right)^{k/\ell}$

Then, $L_{\infty}(f^{k},g)=\Omega(1)$, independent of $f,p,k$.

######  Remark 1.

When $g$ is shallow with depth $\ell=O(k^{1-\epsilon})$ (e.g.,
$\ell=k^{0.99}$), then its width must be exponentially large in order to well-
approximate $f^{k}$. This exponential separation is sharper than prior works
(Chatziafratis et al., 2019, 2020), and quickly becomes even sharper (tending
to 2) with larger values of $p$. This is counterintuitive as Sharkovsky’s
ordering implies that period 3 is the most chaotic and prior works recover a
suboptimal rate of at most $\phi\approx 1.618$ (see Table 1).

######  Remark 2.

Our approximation error is constant independent of all other parameters
$f,k,p$. Previous results (Chatziafratis et al., 2019, 2020; Bu et al., 2020)
obtain a gap that depends on $f,p$ and may be arbitrarily small. Moreover, we
have required nothing of the Lipschitz constant of $f$, unlike the strict
assumptions on the Lipschitz constant $L$ of $f$ by Chatziafratis et al.
(2020) (e.g., they require $L=\phi$ for period $p=3$). Indeed, Propositions 2
and 3 in the Appendix C.6 (see also Fig. 12, Fig. 13), and Figure 1 illustrate
how their lower bounds break down for large $L$ and how their $L_{\infty}$
bounds can shrink, becoming arbitrarily weak for certain 3-periodic $f$.

Figure 1: To illustrate the limitations of prior work (Chatziafratis et al.,
2019, 2020; Bu et al., 2020), we visualize a unimodal mapping $f$ on the left
and $f^{10}$ on the right where $f$ has a 3-cycle without $f^{10}$ having
large oscillations. As guaranteed by the previous results, the total number of
oscillations of $f^{k}$ is $\Omega(\phi^{k})$; however, each is of magnitude
at most $\epsilon$ for this construction and $f^{k}$ can be
$\epsilon$-approximated by a two-layer constant-width neural network, by
Proposition 3. Here, $\epsilon=0.1$, but it may be arbitrarily small. Hence,
to obtain non-trivial constant-accuracy lower bounds on the size of neural
network needed to approximate $f^{k}$, it is insufficient to require only that
$f$ has a 3-cycle.

We also present analogous results for the classification error and the $L_{1}$
errors. Please see the full statements in Theorems 4 and 5. Furthermore,
Theorems 6 and 7 offer an improvement on the results of Chatziafratis et al.
(2020) by giving constant-accuracy $L_{\infty}$ lower bounds without needing a
chaotic itinerary.

In addition, Section 4 relates our chaotic itineraries to standard notions of
function complexity like the VC dimension and the topological entropy (for
precise definitions, see Sec. 4). The types of periodic itineraries of $f$
give rise to two regimes: the doubling regime and the chaotic regime. In the
former, we have a polynomial number of oscillations, while the latter is
characterized by an exponential number of oscillations. Here we show the
following correspondence:

######  Theorem 3 (Informal).

The transition between these two regimes exactly coincides with a sharp
transition in the VC-dimension of the iterated mappings $f^{k}$ for fixed $f$
(from bounded to infinite) and in the topological entropy (from zero to
positive).

##### Our Techniques

To quantify the oscillations of $f^{k}$, we use its chaotic itineraries to
decompose the $[0,1]$ interval into several subintervals
$\\{I_{j}\\}_{j=1}^{j=p-1}$. We count the number of times $f^{k}$ “visits”
each $I_{j}$, by identifying a suitable matrix $A$ whose spectral radius is a
lower bound on the growth rate of oscillations. The associated characteristic
polynomial of $A$ is $\lambda^{p}-2\lambda^{p-1}+1$ and has larger spectral
radius that that of prior works for all periods. Moreover, the corresponding
oscillations of at least one of the subintervals $I_{j}$ do not shrink in
size, giving a bound on the total number of oscillations of a sufficient size.
This provides a lower bound on the height between the peak and the bottom of
these oscillations that later provides constant approximation errors for small
shallow NNs.

More broadly, our work builds on the efforts to characterize large families of
functions that give depth separations and addresses questions raised by Eldan
and Shamir (2016); Telgarsky (2016); Poole et al. (2016); Malach and Shalev-
Shwartz (2019) about the properties of hard-to-represent functions. Similar to
periods, the concept of chaotic itineraries can serve as a certificate of
complexity, which is also easy to verify for unimodal $f$ (see Proposition 1
in Appendix).

##  2 Warm-up Examples

This section presents illustrative examples and instantiates our results for
some simple cases. These highlight the limitations of exclusively considering
periodicity of cycles alone—and not itineraries—when developing accurate
oscillation/crossing bounds (see also Def. 5, 6) and sharp expressivity
tradeoffs.

Consider the three unimodal mappings in Figure 2, $f_{\mathbf{a}}$ with
itineraries $\mathbf{a}\in\\{1324,1234,123\\}$. Observe that $f_{1234}$ has
the cycle $(\frac{1}{5},\frac{2}{5},\frac{3}{5},\frac{4}{5})$, $f_{1324}$ has
$(\frac{1}{5},\frac{3}{5},\frac{2}{5},\frac{4}{5})$, and $f_{123}$ has
$(\frac{1}{4},\frac{1}{2},\frac{3}{4})$. Despite their similarities, they give
rise to significantly different behaviours in $f_{\mathbf{a}}^{k}$.

What do prior works based on NN approximation with respect to periods and
Sharkovsky’s theorem alone tell us? Chatziafratis et al. (2019, 2020) show
that the 3-cycle of $f_{123}$ ensures that $f^{k}$ has $\Omega(\phi^{k})$
oscillations, where $\phi\approx 1.618$ is the golden ratio. However, their
theorems do not imply anything for $f_{1324}$ and $f_{1234}$, since 4 is a
power of 2, and they require odd periods.

Figure 2: Plots of unimodal mappings with different itineraries $f_{1234}$,
$f_{1324}$, and $f_{123}$. Despite their similarities, $f_{1234}$ leads to the
most oscillations and sharpest depth-width tradeoffs (see Fig. 3).

As it turns out, $f_{1234}$ leads to exponential oscillations and $f_{1324}$
leads only to polynomial oscillations:

  * •

A mapping with a 1324-itinerary is guaranteed no other cycles except the
2-cycle and a fixed point (Metropolis et al., 1973). Sharkovsky’s theorem and
Chatziafratis et al. (2019) predict this outcome, since 4 is the third-right-
most element of the Sharkovsky ordering, and its existence alone promises
nothing more. The ordering of itineraries introduced by (Metropolis et al.,
1973) (see Table 3 in Appendix) indicates that the particular 1324-itinerary
only implies the periods 2 and 1, and confirms this intuition. We classify
this itinerary as part of the _doubling regime_ and prove in Theorem 8 that
any $f^{k}$ with a maximal 1324-itinerary (that is, there is no 8-cycle)
cannot exhibit sharp depth-width tradeoffs: for any $\epsilon>0$, there exists
a 2-layer ReLU neural network $g$ of width $O(\frac{k^{3}}{\epsilon})$ such
that $L_{\infty}(f_{1324}^{k},g)\leq\epsilon.$

  * •

Going beyond Sharkovsky’s theorem, a mapping with a 1234-itinerary—even though
it is of period 4—it is guaranteed to contain a 3-cycle as well (see Table 3
in Appendix). Hence, “itinerary-1234 implies period-3, implies chaos,” and
$f_{1234}^{k}$ has at least $\Omega(\phi^{k})$ oscillations and is hard to
approximate by small shallow NNs. Moreover, Theorem 4 and Table 1 show that
$f_{1234}^{k}$ actually has $\Omega(\rho^{k})$ oscillations for $\rho\approx
1.839>\phi$. A corollary is that any NN $g$ of depth $\sqrt{k}$ and width
$O(1.839^{\sqrt{k}})$ has $L_{\infty}(f_{1234}^{k},g)=\Omega(1)$, which is a
stronger separation (constant error) than the ones given by Chatziafratis et
al. (2019, 2020).

Figure 3: The chaotic itinerary $f_{1234}$ has more oscillations than
$f_{123}$ even though $3\triangleright 4$ by Sharkovsky’s Theorem. Itineraries
$f_{1234}$ and $f_{1324}$ (both of period 4) differ dramatically in
oscillation count, showing why periodicity alone fails to capture the optimal
tradeoffs.

The reverse is not true: Sharkovsky’s Theorem guarantees that period-3 implies
period-4, but the only 4-cycle guaranteed by the theorem is actually the non-
chaotic 1324-itinerary, already shown to lead to minimal function complexity.

Furthermore, as $p$ increases, the existence of a chaotic itinerary $12\dots
p$ on $f$ ensures that $f^{k}$ has $\Omega(\rho^{k})$ oscillations for
$\rho\to 2$.999Similarly to Telgarsky (2016), the optimal achievable rate is
$\rho\leq 2$ if we start with a unimodal $f$ (e.g., tent map). If one used
multimodal functions as a building block (e.g., starting with
$f^{\prime}=f^{2}$ or $f^{\prime}=f^{3}$), we could achieve larger rates
(e.g., 4 or 8 respectively). Figure 3 demonstrates these differences in
oscillations (by counting the number of monotone pieces of functions
$f^{k}_{\mathbf{a}}$ with a maximal itinerary-$\mathbf{a}$). As indicated
theoretically, the number of oscillations of $f_{1324}$ is polynomially-
bounded, while the others grow exponentially fast, with $f_{1234}$ being
closer to $2^{k}$. Please see Appendix A for more such examples.

Generally, prior constructions where the oscillation count of $f^{k}$ increase
at a rate faster than $\phi^{k}$ were too narrow (including only the triangle
map). Because $f_{1234}$ breaks the barrier, we abstract away the details and
point to chaotic itineraries as the main source of complexity, leading to
sharper depth-width tradeoffs.

While periodicity tells a compelling story about why $f_{123}^{k}$ is
difficult to approximate, it fails to explain why $f_{1234}^{k}$ is even more
complex. The exponential-vs-polynomial gap in the function complexity of
$f_{1234}$ and $f_{1324}$ depends solely on the order of the elements of the
cycle and distinguishes functions that NNs can easily approximate from those
they cannot.

The remainder of the paper addresses the question introduced here—when does
the itinerary tell us much more than the length of the period—in a general
context that explores a “hierarchy” of such chaotic itineraries, strengthens a
host of NN inapproximability bounds (Sec. 3), and reveals tight connections
with other complexity notions, like the VC-dimension and topological entropy
(Sec. 4).

##  3 Depth-Width Tradeoffs via Chaotic Itineraries

We give our main hardness results on the inapproximability of functions
generated by repeated compositions of $f$ to itself when $f$ has certain
cyclic behavior. Section 3.2 applies insights about chaotic itineraries to
prove constant $L_{\infty}$ and $L_{1}$ lower bounds on the accuracy of
approximating $f^{k}$ when $f$ has an increasing cycle. Section 3.3
strengthens previous bounds on the number of oscillations when $f$ has an odd
cycle, which is not necessarily increasing. Appendix 5 presents Table 2 that
illustrates the key differences between results.

###  3.1 Notation

To measure the function complexity of $f^{k}$, we count the number of times
$f^{k}$ oscillates. We employ two notions of oscillation counts. The first is
relatively weak and counts every interval on which $f$ is either increasing or
decreasing, regardless of its size.

######  Definition 5.

Let $f:[0,1]\to[0,1]$. $M(f)$ represents the _number of monotone pieces_ of
$f$. That is, it is the minimum $m$ such that there exists
$x_{0}=0<x_{1}<\dots<x_{m-1}<x_{m}=1$ where $f$ is monotone on
$[x_{j-1},x_{j}]$ for all $j\in[m]$.

The second instead counts the number of times a fixed interval of size $b-a$
is crossed:

######  Definition 6.

Let $f:[0,1]\to[0,1]$ and $[a,b]\in[0,1]$. $C_{a,b}(f)$ represents the _number
of crossings_ of $f$ on the interval $[a,b]$. That is, it is the maximum $c$
such that there exist

$0\leq x_{1}<x^{\prime}_{1}\leq x_{2}<x^{\prime}_{2}\leq\dots\leq
x_{c}<x_{c}^{\prime}\leq 1$

where for all $j\in[c]$, $f([x_{j},x^{\prime}_{j}])\subset[a,b]$ and either
$f(x_{j})=a$ and $f(x^{\prime}_{j})=b$ or vice versa.

##### Characteristic Polynomials

The base of the exponent of our width bounds is shown to equal the largest
root of one of two polynomials:

$\displaystyle P_{\mathrm{inc},p}(\lambda)$
$\displaystyle=\lambda^{p}-2\lambda^{p-1}+1,$ $\displaystyle
P_{\mathrm{odd},p}(\lambda)$ $\displaystyle=\lambda^{p}-2\lambda^{p-2}-1.$

Let $\rho_{\mathrm{inc},p}$ and $\rho_{\mathrm{odd},p}$ be the largest roots
of $P_{\mathrm{inc},p}$ and $P_{\mathrm{odd},p}$ respectively. Table 1
illustrates that as $p$ grows, $\rho_{\mathrm{inc},p}$ increases to 2, while
$\rho_{\mathrm{odd},p}$ drops to $\sqrt{2}$. Note that
$\rho_{\mathrm{odd},p}\in(\sqrt{2},\sqrt{2+2/2^{p/2}})$ (Alsedà et al., 2000).
We bound the growth rate of $\rho_{\mathrm{inc},p}$ with the following:

######  Fact 1.

$\rho_{\mathrm{inc},p}\in[\max(2-\frac{4}{2^{p}},\phi),2)$, where
$\phi=\frac{1+\sqrt{5}}{2}$ is the Golden Ratio.

We prove Fact 1 in Appendix C.2.

Table 1:  Approximate values of $\rho_{\mathrm{inc},p}$, the lower bound on
$\rho_{\mathrm{inc},p}$ in Fact 1, and $\rho_{\mathrm{odd},p}$ (for odd $p$).
$p$ | $\rho_{\mathrm{inc},p}$ | Fact 1 | $\rho_{\mathrm{odd},p}$
---|---|---|---
$3$ | $1.618$ | $1.618$ | $1.618$
$4$ | $1.839$ | $1.75$ | n/a
$5$ | $1.928$ | $1.875$ | $1.513$
$6$ | $1.966$ | $1.938$ | n/a
$7$ | $1.984$ | $1.969$ | $1.466$
$8$ | $1.992$ | $1.984$ | n/a
$9$ | $1.996$ | $1.992$ | $1.441$
$10$ | $1.999$ | $1.996$ | n/a

###  3.2 Inapproximability of Iterated Functions with Increasing Cycles

Our inapproximability results that govern the size of neural network $g$
necessary to adequately approximate $f^{k}$ when $f$ has an increasing cycle
(like Theorem 2) rely on a key lemma that bounds the number of constant-size
oscillations of $f^{k}$.

######  Lemma 1 (Oscillation Bound for Increasing Cycles).

Suppose $f$ is a symmetric, concave unimodal mapping with an increasing
$p$-cycle for some $p\geq 3$. Then, there exists $[a,b]\subset[0,1]$ with
$b-a\geq\frac{1}{18}$ such that
$C_{a,b}(f^{k})\geq\tfrac{1}{2}\rho_{\mathrm{inc},p}^{k}$ for all
$k\in\mathbb{N}$.

We prove Lemma 1 in Appendix C.1. For an increasing $p$-cycle
$x_{1},\dots,x_{p}$, we lower-bound $M(f^{k})$ (the total number of monotone
pieces, regardless of size) by relating the number of times $f^{k}$ crosses
each interval $[x_{j},x_{j+1}]$ to the number of crossings of $f^{k-1}$. Doing
so entails analyzing the largest eigenvalues of a transition matrix, which
gives rise to the polynomial $P_{\mathrm{inc},p}$. We prove that the intervals
crossed must be sufficiently large due to the symmetry, concavity, and
unimodality of $f$.

######  Remark 3.

If one does not wish to assume that $f$ is unimodal, symmetric, or concave,
then the proof can be modified to show that $C_{a,b}(f^{k})=\Omega(\rho^{k})$
for the same $\rho$, but for $a$ and $b$ dependent on $f$. These results are
similar in flavor to those of Chatziafratis et al. (2019, 2020); Bu et al.
(2020), and they suffer from the same drawback: potentially vacuous
approximation bounds when $a$ and $b$ are close. Appendix C.6 shows natural
functions that are either not symmetric or not concave, whose oscillations
shrink in size arbitrarily.

####  3.2.1 $L_{\infty}$ Approximation and Classification

Our first result is a restatement of Theorem 2 that quantifies
inapproximability in terms of both $L_{\infty}$ and classification error,
which are comparable to the respective results of Bu et al. (2020) and
Chatziafratis et al. (2019).

######  Theorem 4.

Suppose $f$ is a symmetric concave unimodal mapping with an increasing
$p$-cycle for some $p\geq 3$. Then, any $k\in\mathbb{N}$ and
$g\in\mathcal{N}(u,\ell)$ with
$u\leq\frac{1}{8}\rho_{\mathrm{inc},p}^{k/\ell}$ have
$\|f^{k}-g\|_{\infty}=\Omega(1)$.

Moreover, there exists $S$ with
$\left|S\right|=\frac{1}{2}\lfloor\rho_{\mathrm{inc},p}^{k/\ell}\rfloor$ and
$t\in(0,1)$ such that $\mathcal{R}_{S,t}(f^{k},g)\geq\frac{1}{4}.$

The proof follows from our main Lemma 1 above and Theorem 10/Corollary 2 in
the Appendix (two previous inapproximability bounds based on oscillations).

Despite relying on unimodality assumptions and the existence of increasing
cycles, Theorem 4 obtains much stronger bounds than its previous counterparts:

  * •

The assumption that $f$ has an increasing cycle causes a much larger exponent
base for the width bound. Chatziafratis et al. (2019, 2020) only prove that
the existence of 3-cycle mandates a width of $\Omega(\phi^{k/\ell})$. We
exactly match that bound for $p=3$, and improve upon it when $p>3$. As
illustrated by Table 1, increasing $p$ pushes the base $\rho_{\mathrm{inc},p}$
rapidly to 2, which is the maximum exponent base for the increase of
oscillations of any unimodal map. (And the maximal topological entropy of a
unimodal map.) This also approximately matches the bases from Bu et al.
(2020), which scale with the topological entropy of $f$.

  * •

As illustrated in Appendix C.6, the inaccuracy of neural networks with respect
to the $L_{\infty}$ approximation in Chatziafratis et al. (2019, 2020); Bu et
al. (2020) may be arbitrarily small for certain choices of $f$. Our
unimodality assumptions ensure that the oscillations of $f^{k}$ are large and
hence, that the inaccuracy of $g$ is constant.

####  3.2.2 $L_{1}$ Approximation

We also strengthen the bound on $L_{1}$-inapproximability given by
Chatziafratis et al. (2020) by again introducing a stronger exponent and
applying unimodality to yield a constant-accuracy bound.

######  Theorem 5.

Consider any $L$-Lipschitz $f:[0,1]\to[0,1]$ with an increasing $p$-cycle for
some $p\geq 3$. If $L=\rho_{\mathrm{inc},p}$, then for any $k\in\mathbb{N}$,
any $g\in\mathcal{N}(u,\ell)$ with
$u\leq\frac{1}{16}\rho_{\mathrm{inc},p}^{k/\ell}$ has
$\|f^{k}-g\|_{1}=\Omega(1).$

The proof follows again using our main Lemma 1 and using Theorem 11 in the
Appendix.

We make Theorem 5 more explicit by showing that many tent maps meet the
Lipschitzness condition. Let $f_{\text{tent},r}=2r\min(x,1-x)$ be the tent
map, parameterized by $r\in(0,1)$ Our result improves upon Chatziafratis et
al. (2020), by obtaining constant approximation error and using the larger
$\rho_{\mathrm{inc},p}$ rather than $\rho_{\mathrm{odd},p}$.

######  Corollary 1.

For any $p\geq 3$ and $k\in\mathbb{N}$, any $g\in\mathcal{N}(u,\ell)$ with
$u\leq\frac{1}{16}\rho_{\mathrm{inc},p}^{k/\ell}$ has
$\|f_{\text{tent},\rho_{\mathrm{inc},p}}^{k}-g\|_{1}=\Omega(1).$

We prove Corollary 1 in Appendix C.4. The only non-trivial part of the proof
involves proving the existence of an increasing $p$-cycle that causes $f^{k}$
to have $\Omega(\rho_{\mathrm{inc},p}^{k})$ oscillations.

###  3.3 Improved Bounds for Odd Periods

While Theorems 4 and 5 give stricter bounds on the width of neural networks
needed to approximate iterated functions $f^{k}$ than Chatziafratis et al.
(2019, 2020), they also require extra assumptions about the cycles—namely,
that the cycles are increasing. However, more powerful inapproximability
results with constant error are still possible even without additional
assumptions. Specifically, we leverage unimodality to improve the desired
inaccuracy to a constant without compromising width.

As before, the results hinge on a key technical lemma that bounds the number
of interval crossings.

######  Lemma 2.

For some odd $p\geq 3$, suppose $f$ is a symmetric concave unimodal mapping
with an odd $p$-cycle. Then, there exists $[a,b]\subset[0,1]$ with $b-a\geq
0.07$ such that $C_{a,b}(f^{k})=\rho_{\mathrm{odd},p}^{k-p}$ for any
$k\in\mathbb{N}$.

We prove Lemma 2 in Appendix C.5. The challenging part is to find a lower
bound on the length of the intervals crossed.

Like before, we provide lower-bounds on approximation up to a constant degree.

######  Theorem 6.

For some odd $p\geq 3$, suppose $f$ is a symmetric, concave unimodal mapping
with any $p$-cycle. Then, any $k\in\mathbb{N}$ and any
$g\in\mathcal{N}(u,\ell)$ with
$u\leq\frac{1}{8}\rho_{\mathrm{odd},p}^{(k-p)/\ell}$ have
$\|f^{k}-g\|_{\infty}=\Omega(1).$

Moreover, there exists $S$ with
$\left|S\right|=\frac{1}{2}\lfloor\rho_{\mathrm{odd},p}^{k}\rfloor$ and
$t\in(0,1)$ such that $\mathcal{R}_{S,t}(f^{k},g)\geq\frac{1}{4}.$

The proof is immediate from Lemma 2, Theorem 10, and Corollary 2 in the
Appendix.

We also get the analogous result but for the $L_{1}$ error:

######  Theorem 7.

Consider any $L$-Lipschitz $f:[0,1]\to[0,1]$ with a $p$-cycle for some odd
$p\geq 3$. If $L=\rho_{\mathrm{odd},p}$, then, any $k\in\mathbb{N}$ and
$g\in\mathcal{N}(u,\ell)$ with
$u\leq\frac{1}{16}\rho_{\mathrm{odd},p}^{(k-p)/\ell}$ have
$\|f^{k}-g\|_{1}=\Omega(1).$

The proof is immediate from Lemma 1 and Theorem 11 in the Appendix.

##  4 Periods, Phase Transitions and Function Complexity

We formalize the correspondence between different notions of function
complexity in dynamical systems and learning theory: neural network
approximation, oscillation count, cycle itinerary, topological entropy, and
VC-dimension. We make Theorem 3 rigorous by presenting two regimes into which
unimodal mappings can be classified—the _doubling regime_ and the _chaotic
regime_ —and show that all of these measurements of complexity hinge on which
regime a function belongs to.101010These two regimes correspond to different
settings of the parameters $r$ in the bifurcation diagram of Figure 8 in the
Appendix. The doubling regime is the left-hand-side, where the stable periods
routinely split in two before the first chaos is encountered. The chaotic
regime is to the right-hand-side, which is characterized by chaos punctuated
by intermittent stability.

Some components of the claims regarding the topological entropy are the
immediate consequences of other results; however, we include them to give a
complete picture of the gap between the two regimes. To the best of our
knowledge, we believe the bound on monotone pieces of $f^{k}$ in the doubling
regime and both VC-dimension bounds below to be novel.

We define VC-dimension and introduce topological entropy in Appendix D, along
with the proofs of both theorems. For VC-dimension, we consider the hypothesis
class $\mathcal{H}_{f,t}:=\\{[[f^{k}]]_{t}:k\in\mathbb{N}\\}$, which
corresponds to the class of iterated fixed maps.

######  Theorem 8.

[Doubling Regime] Suppose $f$ is a symmetric unimodal mapping whose maximal
cycle is a primary cycle of length $p=2^{q}$. That is, there exists a
$p$-cycle but no $2p$-cycles (and thus, no cycles with lengths non-powers-of-
two). Then, the following are true:

  1. 1.

For any $k\in\mathbb{N}$, $M(f^{k})=O((4k)^{q+1})$.

  2. 2.

For any $k\in\mathbb{N}$, there exists $g\in\mathcal{N}(u,2)$ with
$u=O((4k)^{q+1}/\epsilon)$ such that
$\left\|g-f^{k}\right\|_{\infty}\leq\epsilon$. Moreover, if
$f=f_{\text{tent},r}$, then there exists $g\in\mathcal{N}(u,2)$ with
$u=O((4k)^{q+1})$ and $g=f^{k}$.

  3. 3.

$h_{\mathrm{top}}(f)=0$.

  4. 4.

For any $t\in(0,1)$, $\text{VC}(\mathcal{H}_{f,t})\leq 18p^{2}$.

######  Theorem 9.

[Chaotic Regime] Suppose $f$ is a unimodal mapping that has a $p$-cycle where
$p$ is not a power-of-two. Then, the following are true:

  1. 1.

There exists some $\rho\in(1,2]$ such that for any $k\in\mathbb{N}$,
$M(f^{k})=\Omega(\rho^{k})$.

  2. 2.

For any $k\in\mathbb{N}$ and any $g\in\mathcal{N}(u,\ell)$ with $\ell\leq k$
and $u\leq\frac{1}{8}\rho^{k/\ell}$, there exist samples $S$ with
$\left|S\right|=\frac{1}{2}\left\lfloor\rho^{k}\right\rfloor$ such that
$\mathcal{R}_{S,1/2}(f^{k},g)\geq\frac{1}{4}$.

  3. 3.

$h_{\mathrm{top}}(f)\geq\rho>0$.

  4. 4.

There exists a $t\in(0,1)$ such that $\text{VC}(\mathcal{H}_{f,t})=\infty$.

######  Remark 4.

As discussed in Appendix B, any non-primary cycle implies the existence of a
cycle whose length is not a power of two. Thus, these results also apply if
there exists any non-primary power-of-two cycle, such as the 1234-itinerary
4-cycle.

##  5 Comparison with Prior Works

Given the large number of results presented in this paper and the many axes of
comparison one can draw between these results and their predecessors in
Telgarsky (2016); Chatziafratis et al. (2019, 2020), we provide Table 2 to
illuminate these comparisons. It reinforces our key contributions, namely that
(1) the presence of increasing cycles makes a function more difficult to
approximate than a 3-cycle alone; (2) requiring that $f$ satisfy unimodality
constraints gives lower-bounds to constant accuracy that cannot be made
vacuous by adversarial choices of $f$; and (3) the key distinction between
“hard” and “easy” functions is the existence of non-primary power-of-two
cycles.

| Condition | Approx. | Unimodal? | Concave? | Symmetric? |  $L\leq\rho$? | Acc. | Exp. | Hard? |  Source
---|---|---|---|---|---|---|---|---|---|---
1 | Maximal PO2 | $L_{\infty}$ | Yes | No | Yes | No | $\Omega(1)$ | Any | No |  Thm 8
2 | $h_{\mathrm{top}}(f)\geq\rho$ | $L_{\infty}$ | No | No | No | No | $\epsilon(f)$ | $\rho$ | Yes |  BZL Thm 16
3 | Non-primary | Cls. | No | No | No | No | $\frac{1}{4}$ | $(1,\phi]$ | Yes |  CNPW Thm 1.6, Remark 4
4 | Non-primary | $L_{\infty}$ | No | No | No | No | $\epsilon(f)$ | $(1,\phi]$ | Yes |  CNPW Thm 1.6, Remark 4, BZL Thm 16
5 | Non-PO2 | Cls. | No | No | No | No | $\frac{1}{4}$ | $(1,\phi]$ | Yes |  CNPW Thm 1.6
6 | Non-PO2 | $L_{\infty}$ | No | No | No | No | $\epsilon(f)$ | $(1,\phi]$ | Yes |  CNPW Thm 1.6, BZL Thm 16
7 | Odd cycle | Cls. | No | No | No | No | $\frac{1}{4}$ | $(\sqrt{2},\phi]$ | Yes |  CNP Thm 1.1
8 | Odd cycle | $L_{\infty}$ | No | No | No | No | $\epsilon(f)$ | $(\sqrt{2},\phi]$ | Yes |  CNP Thm 1.1, BZL Thm 16
9 | Odd cycle | $L_{\infty}$ | Yes | Yes | Yes | No | $\Omega(1)$ | $(\sqrt{1},\phi]$ | Yes |  Thm 6
10 | Odd cycle | $L_{1}$ | No | No | No | Yes | $\epsilon(f)$ | $(\sqrt{2},\phi]$ | Yes |  CNP Thm 1.2
11 | $f_{\text{tent},\rho_{p}/2}$ | $L_{1}$ | Implied | Implied | Implied | Implied | $\Omega(1)$ | $(\sqrt{2},\phi]$ | Yes |  CNP Lemma 3.6
12 | Odd cycle | $L_{1}$ | Yes | Yes | Yes | Yes | $\Omega(1)$ | $(\sqrt{2},\phi]$ | Yes |  Thm 7
13 | Inc. Cycle | Cls. | No | No | No | No | $\frac{1}{4}$ | $[\phi,2)$ | Yes |  Thm 4, Remark 3
14 | Inc. Cycle | $L_{\infty}$ | No | No | No | No | $\epsilon(f)$ | $[\phi,2)$ | Yes |  Thm 4, Remark 3
15 | Inc. Cycle | $L_{\infty}$ | Yes | Yes | No | No | $\Omega(1)$ | $[\phi,2)$ | No |  Prop 2
16 | Inc. Cycle | $L_{\infty}$ | Yes | No | Yes | No | $\Omega(1)$ | $[\phi,2)$ | No |  Prop 3
17 | Inc. Cycle | $L_{\infty}$ | Yes | Yes | Yes | No | $\Omega(1)$ | $[\phi,2)$ | Yes |  Thm 4
18 | Inc. Cycle | $L_{1}$ | No | No | No | Yes | $\epsilon(f)$ | $[\phi,2)$ | Yes |  Thm 5, CNP Thm 1.2
19 | Inc. Cycle | $L_{1}$ | Yes | Yes | Yes | Yes | $\Omega(1)$ | $[\phi,2)$ | Yes |  Thm 5
20 | $f_{\text{tent},\rho_{p}/2}$ | $L_{1}$ | Implied | Implied | Implied | Implied | $\Omega(1)$ | $[\phi,2)$ | Yes |  Cor 1
21 | $f_{\text{tent},1}$ | $L_{1}$ | Implied | Implied | Implied | Implied | $\Omega(1)$ | 2 | Yes |  Telgarsky

Table 2: Compares the conditions and limitations of the theoretical results
presented in this paper and its predecessors. New results are bolded.

We provide context for each column to clarify what its cells mean and how to
compare their values.

  * •

“Condition” specifies what must be true of the complexity of $f$ in order for
the relevant bounds to occur. All but the latter two conditions describe a
very broad array of functions, while the last two focus only on a restricted
subset of tent mappings.

    * –

“Maximal PO2” means that the maximal cycle of $f$ is a primary111111See
Appendix B.2. $p$-cycle where $p$ is a power of two. This means that $f$ lies
in the doubling regime described in Theorem 8.

    * –

“$h_{\mathrm{top}}(f)\geq\rho$” considers any $f$ with a lower-bound on its
topological entropy for some $\rho>1$. Notably, all conditions other than
“Maximal PO2” satisfy this for some $\rho$.

    * –

“Non-primary” means that any non-primary cycle exists in $f$. That is, if $f$
is known to have a non-primary power-of-two cycle, then the results apply.

    * –

“Non-PO2” refers to any $f$ that has a $p$-cycle where $p$ is not a power of
two.

    * –

“Odd cycle” includes any $f$ that has a $p$-cycle where $p$ is odd.

    * –

“Inc. cycle” means that $f$ has an increasing $p$-cycle for some $p$, i.e. a
cycle with itinerary $12\dots p$.

    * –

$f_{\text{tent},\rho_{p}/2}$ refers to families of tent maps scaled by
$\rho_{p}$ solving the polynomials from Chatziafratis et al. (2020) Lemma 3.6
(for odd periods) and Corollary 1 (for increasing cycles).

    * –

The last row refers exclusively to the tent map of height 1 and slope 2.

  * •

“Approx.” refers to how difference between neural network $g$ and iterated map
$f^{k}$ is measured. The options are $L_{1}$, $L_{\infty}$, and classification
error. It’s easier to show that $g$ can $L_{1}$-approximate $f^{k}$ than it is
to show that $g$ can $L_{\infty}$-approximate $f$; conversely, it’s most
impressive to show lower bound results with respect to the $L_{1}$ error than
it is for the $L_{\infty}$ error.

Chatziafratis et al. (2019, 2020) consider classification error, Bu et al.
(2020) focus on $L_{\infty}$ approximation, and Chatziafratis et al. (2020)
also consider $L_{1}$ approximation. We routinely translate classification
errors to $L_{\infty}$ errors using Corollary 2, which draws on Theorem 16 of
Bu et al. (2020).

  * •

“Unimodal?,” “Concave?,” and “Symmetric?,” have “Yes” if and only if $f$ must
meet the respective property for the proof to hold. They have “Implied” if the
value of “Condition” already ensures that the property is satisfied and the
requirement need not be enforced.

  * •

“$L\leq\rho$?” is “Yes” if the results only hold if $f$ is chosen with a
Lipschitz constant less than the rate of growth of its oscillations. This is a
very restrictive condition met by very few functions (including no logistic
maps with cycles).

  * •

“Acc.” specifies the desired accuracy of the hardness result. “$\Omega(1)$”
means that there exists some constant $\epsilon$ such that for any choice of
$f$ in the category, any neural network $g$ will be unable to approximate $f$
up to accuracy $\epsilon$. “$\epsilon(f)$” means that the degree of
approximation may depend on the chosen function $f$ (and the period $p$) that
belongs to the category; these bounds may be vacuous by an adversarial choice
of $f$. As a result, hardness results with “$\Omega(1)$” are more impressive.

  * •

“Exp.” refers to the base of the exponent of the lower-bound on the width
necessary to approximate $f^{k}$ using a shallow network $g$. Larger values
indicate stronger bounds.

  * •

“Hard?” is “Yes” if for every $f$ satisfying the conditions to the left, $f$
cannot be approximated up to the specified accuracy by any neural network $g$.
It is “No” if there exists some $f$ satisfying the conditions that can be
approximated to a stronger degree of accuracy.

  * •

“Source” denotes where to find the result. Some of the less interesting
results are not given their own theorems and rather are immediate implications
of several theorems across this body of literature. For the sake of space, we
use “CNPW” to refer to (Chatziafratis et al., 2019); “CNP” for (Chatziafratis
et al., 2019); “BZL” for (Bu et al., 2020); and “Telgarsky” for (Telgarsky,
2016).

##  6 Conclusion

In this work, we build new connections between deep learning theory and
dynamical systems by applying results from discrete-time dynamical systems to
obtain novel depth-width tradeoffs for the expressivity of neural networks.
While prior works relied on Sharkovsky’s theorem and periodicity to provide
families of functions that are hard-to-approximate with shallow neural
networks, we go beyond periodicity. Studying the chaotic itineraries of
unimodal mappings, we reveal subtle connections between expressivity and
different types of periods, and we use them to shed new light on the benefits
of depth in the form of enhanced width lower bounds and stronger approximation
errors. More broadly, we believe that it is an exciting direction for future
research to exploit similar tools and concepts from the literature of
dynamical systems in order to improve our understanding of neural networks,
e.g., their dynamics, optimization and robustness properties.

## Acknowledgements

C.S. is supported by the National Science Foundation Graduate Research
Fellowship Program (NSF GRFP); grants NSF CCF-1563155 and NSF CCF 1814873; a
grant from the Simons Collaboration on Algorithms and Geometry; and a Google
Faculty Research Award to Daniel Hsu. V.C. was supported by Northwestern
University. The authors are grateful to Daniel Hsu for helpful comments and
feedback on an early draft of this work.

## References

  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  _Advances in neural information processing systems_ , 25:1097–1105, 2012.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Brown et al. (2020) Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _NeurIPS_ , 2020.
  * Eldan and Shamir (2016) Ronen Eldan and Ohad Shamir.  The power of depth for feedforward neural networks.  In _Conference on learning theory_ , pages 907–940, 2016.
  * Minsky and Papert (1969) Marvin Minsky and Seymour A Papert.  _Perceptrons: An introduction to computational geometry_.  MIT press, 1969.
  * Cybenko (1989) George Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of control, signals and systems_ , 2(4):303–314, 1989.
  * Hornik et al. (1989) Kurt Hornik, Maxwell Stinchcombe, and Halbert White.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5):359–366, 1989.
  * Telgarsky (2015) Matus Telgarsky.  Representation benefits of deep feedforward networks.  _arXiv preprint arXiv:1509.08101_ , 2015.
  * Telgarsky (2016) Matus Telgarsky.  benefits of depth in neural networks.  In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, _29th Annual Conference on Learning Theory_ , volume 49 of _Proceedings of Machine Learning Research_ , pages 1517–1539, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR.
  * Warren (1968) Hugh E Warren.  Lower bounds for approximation by nonlinear manifolds.  _Transactions of the American Mathematical Society_ , 133(1):167–178, 1968.
  * Anthony and Bartlett (1999) Martin Anthony and Peter L Bartlett.  _Neural network learning: Theoretical foundations_ , volume 9.  cambridge university press Cambridge, 1999.
  * Schmitt (2000) Michael Schmitt.  Lower bounds on the complexity of approximating continuous functions by sigmoidal neural networks.  In _Advances in neural information processing systems_ , pages 328–334, 2000.
  * Montufar et al. (2014) Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio.  On the number of linear regions of deep neural networks.  In _Advances in neural information processing systems_ , pages 2924–2932, 2014.
  * Arora et al. (2016) Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee.  Understanding deep neural networks with rectified linear units.  _arXiv preprint arXiv:1611.01491_ , 2016.
  * Hanin and Rolnick (2019) Boris Hanin and David Rolnick.  Deep relu networks have surprisingly few activation patterns.  In _Advances in Neural Information Processing Systems_ , pages 359–368, 2019.
  * Kileel et al. (2019) Joe Kileel, Matthew Trager, and Joan Bruna.  On the expressive power of deep polynomial neural networks.  In _Advances in Neural Information Processing Systems_ , pages 10310–10319, 2019.
  * Barron (1993) Andrew R Barron.  Universal approximation bounds for superpositions of a sigmoidal function.  _IEEE Transactions on Information theory_ , 39(3):930–945, 1993.
  * Daniely (2017) Amit Daniely.  Depth separation for neural networks.  In _Conference on Learning Theory_ , pages 690–696. PMLR, 2017.
  * Lee et al. (2017) Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski, and Sanjeev Arora.  On the ability of neural nets to express distributions.  In _Conference on Learning Theory_ , pages 1271–1296. PMLR, 2017\.
  * Bresler and Nagaraj (2020) Guy Bresler and Dheeraj Nagaraj.  Sharp representation theorems for relu networks with precise dependence on depth.  _arXiv preprint arXiv:2006.04048_ , 2020.
  * Malach and Shalev-Shwartz (2019) Eran Malach and Shai Shalev-Shwartz.  Is deeper better only when shallow is good?  _arXiv preprint arXiv:1903.03488_ , 2019.
  * Bu et al. (2020) Kaifeng Bu, Yaobo Zhang, and Qingxian Luo.  Depth-width trade-offs for neural networks via topological entropy, 2020\.
  * Safran et al. (2019) Itay Safran, Ronen Eldan, and Ohad Shamir.  Depth separations in neural networks: what is actually being separated?  In _Conference on Learning Theory_ , pages 2664–2666. PMLR, 2019\.
  * Hsu et al. (2021) Daniel Hsu, Clayton Sanford, Rocco A Servedio, and Emmanouil-Vasileios Vlatakis-Gkaragkounis.  On the approximation power of two-layer networks of random relus.  _Conference on Learning Theory_ , 2021.
  * Poole et al. (2016) Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli.  Exponential expressivity in deep neural networks through transient chaos.  In _Advances in neural information processing systems_ , pages 3360–3368, 2016.
  * Raghu et al. (2017) Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl Dickstein.  On the expressive power of deep neural networks.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pages 2847–2854. JMLR. org, 2017.
  * Chatziafratis et al. (2019) Vaggos Chatziafratis, Sai Ganesh Nagarajan, Ioannis Panageas, and Xiao Wang.  Depth-width trade-offs for relu networks via sharkovsky’s theorem.  _arXiv preprint arXiv:1912.04378_ , 2019.
  * Chatziafratis et al. (2020) Vaggos Chatziafratis, Sai Ganesh Nagarajan, and Ioannis Panageas.  Better depth-width trade-offs for neural networks through the lens of dynamical systems.  In _International Conference on Machine Learning_ , pages 1469–1478. PMLR, 2020.
  * Alsedà et al. (2000) Lluís Alsedà, Jaume Llibre, and Michal Misiurewicz.  _Combinatorial Dynamics and Entropy in Dimension One_.  WORLD SCIENTIFIC, 2nd edition, 2000.  doi: 10.1142/4205.
  * Lee et al. (2019) Jason D Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I Jordan, and Benjamin Recht.  First-order methods almost always avoid strict saddle points.  _Mathematical programming_ , 176(1):311–337, 2019\.
  * Palaiopanos et al. (2017) Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras.  Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos.  _arXiv preprint arXiv:1703.01138_ , 2017.
  * Metropolis et al. (1973) N Metropolis, M.L Stein, and P.R Stein.  On finite limit sets for transformations on the unit interval.  _Journal of Combinatorial Theory, Series A_ , 15(1):25 – 44, 1973.  ISSN 0097-3165.  doi: https://doi.org/10.1016/0097-3165(73)90033-2.
  * Li and Yorke (1975) Tien-Yien Li and James A Yorke.  Period three implies chaos.  _The American Mathematical Monthly_ , 82(10):985–992, 1975.
  * Sharkovsky (1964) OM Sharkovsky.  Coexistence of the cycles of a continuous mapping of the line into itself.  _Ukrainskij matematicheskij zhurnal_ , 16(01):61–71, 1964.
  * Sharkovsky (1965) OM Sharkovsky.  On cycles and structure of continuous mapping.  _Ukrainskij matematicheskij zhurnal_ , 17(03):104–111, 1965.
  * Misiurewicz and Szlenk (1980) Michal Misiurewicz and Wieslaw Szlenk.  Entropy of piecewise monotone mappings.  _Studia Mathematica_ , 67:45–63, 1980.
  * Young (1981) Lai-Sang Young.  On the prevalence of horseshoes.  _Transactions of the American Mathematical Society_ , 263:75–88, 1981.  ISSN 0002-9947.
  * Vapnik and Chervonenkis (2013) Vladimir Naumovich Vapnik and Alexey Ya. Chervonenkis.  On the uniform convergence of the frequencies of occurrence of events to their probabilities.  In _Empirical Inference_ , 2013.
  * Rosser (1941) Barkley Rosser.  Explicit bounds for some functions of prime numbers.  _American Journal of Mathematics_ , 63(1):211–232, 1941.  ISSN 00029327, 10806377.

##  Appendix A Supplement for Section 2

Figures 4 and 6 demonstrate two emblematic cases where the differences in
function complexity of $f_{123}$, $f_{1234}$, and $f_{1324}$ are most evident.
Both figures provide a function for each $f_{\mathbf{a}}$ that has a maximal
itinerary of $\mathbf{a}$. (That is, there is no “higher-ranked” itinerary
from Table 3 present in $f_{\mathbf{a}}$; all other cycles are induced by the
existence of a cycle with itinerary $\mathbf{a}$.)

Figures 4 and 5 provide a simple case where the elements of the cycles are
evenly spaced ($\frac{1}{4},\frac{1}{2},\frac{3}{4}$ for $f_{123}$;
$\frac{1}{5},\frac{2}{5},\frac{3}{5},\frac{4}{5}$ for $f_{1234},f_{1324}$).
Despite the fact that $f_{1234}$ and $f_{1324}$ have the same maximum value,
they exhibit substantially different fractal-like patterns, which produce
exponentially more oscillations for $f_{1234}$.

Figure 6 and 7 instead considers logistic maps of the form
$f_{\text{log},r}(x)=4rx(1-x)$ for the values of $r$ where itinerary
$\mathbf{a}$ is _super-stable_ , or when nearby iterates converge to the cycle
exponentially fast. These functions are concave, symmetric, and unimodal.
Here, complexity strictly increases with the maximum value of
$f_{\text{log},r}$. Indeed, $f_{1234},f_{123}$ and $f_{1324}$ ordered by
height is the order by which they exhibit most to least chaotic behavior.

Figure 4: A comparison of the function complexity (as measured by the number
of monotone pieces) of $f^{k}$ for unimodal mappings $f$ having cycles with
different itineraries. The left shows $f$, $f^{2}$, $f^{5}$, and $f^{10}$ for
a function with a 1234 4-cycle. The center has a 1324 4-cycle. The bottom has
a 123 3-cycle. Figure 5 shows how the number of monotone pieces of $f^{k}$
increases with $k$ for each mapping. Figure 5: Visualizes the number of
monotone pieces of $f^{k}$ which increases with $k$ for each mapping along
with $2^{k}$ (the maximum number of monotone pieces of any unimodal $f$). Note
that the 1234 itinerary produces a more “complex” function with more monotone
pieces than 123, despite the Sharkovsky analysis from Chatziafratis et al.
(2019) arguing that 3-cycles are the most powerful when determining iteration
counts. Moreover, the number of monotone pieces of the 1234 and 123
itineraries increases exponentially, while that of the 1324 itineraries does
not. (Identical to Figure 3.)

Figure 6: Demonstrates the same ideas as Figure 4, except instead of using
asymmetric and non-concave piecewise functions, we use the scaled logistic
map, $f_{\text{log},r}$. Using Table 1 of Metropolis et al. (1973), we set the
parameter $r$ to $3.96$, $3.50$, and $3.83$ respectively to ensure that a
super-stable 1234, 1324, and 123 cycle exists. Figure 7: Like Figure 5,
vizualizes the differences in number of monotone pieces for the logistic
mappings described in Figure 6.

##  Appendix B More Examples for Itineraries

###  B.1 Examples of Itineraries

Let the tent map and logistic map be defined by
$f_{\text{tent},r}(x)=2r\max(x,1-x)$ and $f_{\text{log},r}(x)=4rx(1-x)$
respectively, for parameter $r\in(0,1)$.

######  Example 1.

For all $r\in(\frac{1}{2},1]$, there is a two-cycle $C$ of itinerary 12 (which
is the only itinerary for a 2-cycle) in $f_{\text{tent},r}$ with

$C=\left(\frac{2r}{1+4r^{2}},\frac{4r^{2}}{1+4r^{2}}\right).$

######  Example 2.

When $r=\frac{1+\sqrt{5}}{4}$, there is a two-cycle $C$ of $f_{\text{log},r}$
with

$C=\left(\frac{1}{2},\frac{1+\sqrt{5}}{4}\right).$

######  Example 3.

When $r\in[\frac{1+\sqrt{5}}{4},1]$, $f_{\text{tent},r}$ has a three-cycle $C$
of itinerary 123 with

$C=\left(\frac{2r}{1+8r^{3}},\frac{4r^{2}}{1+8r^{3}},\frac{8r^{3}}{1+8r^{3}}\right).$

Note that this and Example 1 are consistent with Sharkovsky’s Theorem;
whenever there exists a three-cycle, there also exists a two-cycle.

######  Example 4.

When $r\in[\frac{1}{2},1]$, there also exists a four-cycle $C$ of itinerary
$1324$ for $f_{\text{tent},r}$ with

$C=\left(\frac{8r^{3}-4r^{2}+2r}{16r^{2}+1},\frac{16r^{4}-8r^{3}+4r^{2}}{16r^{2}+1},\frac{16r^{4}-8r^{3}+2r}{16r^{2}+1},\frac{16r^{4}-4r^{2}+2r}{16r^{2}+1}\right).$

Again, this reaffirms Sharkovsky’s Theorem, since this cycle always exists
when the above three-cycle exists.

######  Example 5.

However, when $r\in(0.9196\dots,1]$, there also exists a four-cycle $C$ of
itinerary $1234$ for $f_{\text{tent},r}$ with

$C=\left(\frac{2r}{16r^{2}+1},\frac{4r^{2}}{16r^{2}+1},\frac{8r^{3}}{16r^{2}+1},\frac{16r^{4}}{16r^{2}+1}\right).$

This demonstrates a relationship beyond Sharkovsky’s theorem: whenever a
$1234$ four-cycle exists, a $123$ three-cycle also exists. This will be
integral to the bounds we show.

######  Example 6.

The triangle map from Telgarsky (2016), $f_{\text{tent},1}$ has an increasing
$p$-cycle $C_{p}$ for every $p\in\mathbb{N}$ with

$C_{p}=\left(\frac{2}{1+2^{p}},\frac{2^{2}}{1+2^{p}},\dots,\frac{2^{p}}{1+2^{p}}\right).$

Thus Theorem 10 and Fact 1 retrieve the fact used by Telgarsky that
$M(f_{\text{tent},1})=\Omega(2^{k})$.

###  B.2 Orderings of Itineraries

As has been mentioned before, the existence of some cycles can be shown to
imply the existence of other cycles. Sharkovsky’s Theorem famously does this
by showing that if $p\triangleright p^{\prime}$, then the existence of a
$p$-cycle implies the existence of a $p^{\prime}$-cycle. Proposition 1 can be
used to imply that the existence of a chaotic $p$-cycle implies the existence
of a chaotic $(p-1)$-cycle. These pose a broader question: Is there a complete
ordering on all cycle itineraries that can appear in unimodal mappings? And
does this ordering coincide with the amount of “chaos” induced by a cycle?

Researchers of discrete dynamical systems have thoroughly investigated these
questions; we refer interested readers to Metropolis et al. (1973); Alsedà et
al. (2000) for a more comprehensive survey. We introduce the basics of this
theory as it relates to our results.

Metropolis et al. (1973) present a partial ordering over cyclic itineraries
present in unimodal mappings, which serves as a measurement of the complexity
of the function. That is, two itineraries $\mathbf{a}$ and
$\mathbf{a}^{\prime}$ may be related analogously to Sharkovsky’s Theorem with
$\mathbf{a}\triangleright\mathbf{a}^{\prime}$, if $f$ having itinerary
$\mathbf{a}$ implies that $f$ has itinerary $\mathbf{a}^{\prime}$. This
ordering for all cycles of length at most 6 is illustrated in Table 3. For
instance, if a unimodal map has a cycle with itinerary 12435, then it also has
a cycle with itinerary 135246.

Table 3: For any unimodal function $f$, let $f_{r}(x):=rf(x)$ for $r>0$. As
$r$ increases, any such family obtains new cycles in the same order, and those
cycles are super-stable in the same order. This translates Table 1 of
Metropolis et al. (1973) to our notation and shows at what values of $r$,
$f_{\text{log},r}$ has various super-stable cycles of length at most 6.
Cycle length $p$ | Itinerary | Regime |  $r$ s.t. super-stable for $f_{\text{log},r}$ | Cycle Type
---|---|---|---|---
2 | 12 | Doubling | $0.8090$ | Primary
4 | 1324 | Doubling | $0.8671$ | Primary
6 | 143526 | Chaotic | $0.9069$ | Primary
5 | 13425 | Chaotic | $0.9347$ | Stefan, Primary
3 | 123 | Chaotic | $0.9580$ | Stefan, Increasing, Primary
6 | 135246 | Chaotic | $0.9611$ |
5 | 12435 | Chaotic | $0.9764$ |
6 | 124536 | Chaotic | $0.9844$ |
4 | 1234 | Chaotic | $0.9901$ | Increasing
6 | 123546 | Chaotic | $0.9944$ |
5 | 12345 | Chaotic | $0.9976$ | Increasing
6 | 123456 | Chaotic | $0.9994$ | Increasing

We make several observations about the table and make connections to the
itineraries discussed elsewhere in the paper.

  * •

The table does not contradict Sharkovsky’s Theorem. Note that $3\triangleright
5\triangleright 6\triangleright 4\triangleright 2$, and order in which the
first itinerary occurs of a period is the same as the Sharkovsky ordering:

$12\triangleleft 1324\triangleleft 143526\triangleleft 13425\triangleleft
123.$

  * •

The last cycle to occur for a given period is its increasing cycle and it
occurs as $p$ increases (not with the Sharkovsky ordering of $p$):

$12\triangleleft 123\triangleleft 1234\triangleleft 12345\triangleleft
123456.$

  * •

The first cycle to appear for every odd period is its Stefan cycle (123,
13425). This is proved by Alsedà et al. (2000) and justifies why Theorem 6
relies on the existence of a Stefan cycle whenever there is an odd period.

  * •

There exist cycles of power-of-two length (e.g. 1234) that induce non-power-
of-two cycles (e.g. 123).

Following the last bullet point, we distinguish between the $2^{q}$-cycles
that only induce cycles of length $2^{i}$ for $i<q$ and those that induce non-
power-of-two cycles. To do so, we say that the itinerary of a $p$-cycle is
primary if it induces no other $p$-cycle with a different itinerary.

We say that an itinerary $\mathbf{a}^{\prime}=a_{1}^{\prime}\dots
a_{2p}^{\prime}$ of a $2p$-cycle is a 2-extension of itinerary
$\mathbf{a}=a_{1}\dots a_{p}$ of a $p$-cycle if

$a_{i}=\left\lceil\frac{a_{i}^{\prime}}{2}\right\rceil=\left\lceil\frac{a_{i+p}^{\prime}}{2}\right\rceil$

for all $i$. For instance, $12$ is a 2-extension of $1$, $1324$ is of $12$,
$15472638$ is of $1324$, and $135246$ is of $123$.

Theorem 2.11.1 of Alsedà et al. (2000) characterizes which itineraries are
primary. It critically shows that a power-of-two cycle is primary if and only
if it is composed of iterated 2-extensions of the trivial fixed-point
itinerary 1. As a result, 1324 is a primary itinerary and 1234 is not. This
sheds further light on the warmup example given in Section 2 and expanded upon
in Appendix A, where $f_{1324}^{k}$ has a polynomial number of oscillations,
while $f_{1234}^{k}$ has an exponential number.

According to Theorem 2.12.4 of Alsedà et al. (2000), the existence a non-
primary itinerary of any period implies the existence of some cycle with
period not a power of two. Hence, $f$ can only be in the doubling regime
(where all periods are powers of two) if all of those power-of-two periods are
primary. The existence of any non-primary power-of-two period (such as 1234 or
13726548) implies that the $f$ is in the chaotic regime.

This ordering can also be visualized using the bifurcation diagrams in Figure
8. The diagram plots the convergent behavior of $f^{k}_{r}(x)$ for large $k$,
where $r$ is some parameter and reflects the complexity of the unimodal
function $f_{r}$. (When $r=0$, $f_{r}=0$; when $r=1$, $x_{\max}=1$, and
$C_{0,1}(f^{k})=2^{k}$.) As $r$ increases, the number of oscillations of
$f_{r}^{k}$ increases and with it, new cycles are introduced. Each new cycle
has a stable region over parameters $r$ where $f_{r}^{k}(x)$ converges to the
cycle, and the bifurcation diagram visualizes when each of these stable
regions occurs. While the three functions families $f_{r}$ have different
underlying unimodal functions, they produce qualitatively identical
bifurcation diagrams that feature the same ordering of itineraries.

Figure 8: Bifurcation diagrams—which display the qualitative behavior of a
family of functions $f_{r}$ as the parameter $r\in[0,1]$ changes—showing the
convergence behavior for iterates $f_{r}^{k}(x)$ for large $k$. For fixed $r$
on the horizontal axis, the points plotted correspond to $f^{k}(x_{0})$ for
very large $k$. Regions of $r$ where a vertical slice contains $p$ discrete
points indicates the existence of a stable $p$-cycle, since $f^{k}(x_{0})$
converges exclusively to those points. Regions where the slice has a dispersed
mass of points exhibit chaos. As $r$ increases, cycles of different
itineraries appear and experience stability in the same order indicated by
Table 3. In the first plot, $f_{r}$ is the logistic map
$f_{r}(x)=f_{\text{log},r}(x)=4rx(1-x)$. The second $f_{r}$ is the“flat tent
map,” $f_{r}(x)=\min\\{\frac{5rx}{2},r,\frac{5rx}{2}(1-x)\\}$, and the third
is the sine map, $f_{r}(x)=r\sin(\pi x)$. The three are qualitatively
identical and exhibit self-similarity.

Our discussions of the doubling and chaotic regimes in Section 4 are inspired
by these bifurcation diagrams. Parameter values $r$ are naturally partitioned
into two categories: those on the left side of the diagram where the plot is
characterized by a branching of cycles (the doubling regime) and those on the
right side where there are extended regions of chaos, interrupted by small
stable regions (the chaotic regime).

###  B.3 Identifying Increasing Cycles in Unimodal Maps

It is straightforward to determine whether a symmetric and unimodal $f$ has an
increasing $p$-cycle. Algorithmically, one can do so by verifying that
$f(\frac{1}{2})>\frac{1}{2}$ and counting how many consecutive values of
$k\geq 2$ satisfy $f^{k}(x_{0})<\frac{1}{2}$.

######  Proposition 1.

Consider some $p\geq 2$ and a symmetric unimodal mapping $f$. $f$ has an
increasing $p$-cycle if

$f^{2}\left(\frac{1}{2}\right)<\dots<f^{p}\left(\frac{1}{2}\right)\leq\frac{1}{2}<f\left(\frac{1}{2}\right),$

then $f$ has an increasing $p$-cycle.

###### Proof.

Refer to Figure 9 for a visualization of the variables and inequalities
defined.

Let $x^{\prime}=f(\frac{1}{2})$. By the unimodality of $f$ and the fact that
$x^{\prime}>\frac{1}{2}$, there exists some $x^{\prime\prime}>\frac{1}{2}$
such that

$f(x^{\prime\prime})<f^{2}(x^{\prime\prime})<\dots<f^{p-1}(x^{\prime\prime})=\frac{1}{2}.$

Because $f$ is monotonically increasing on $[0,\frac{1}{2}]$, the following
string of inequalities hold.

$f(x^{\prime})\leq f(x^{\prime\prime})<f^{2}(x^{\prime})\leq
f^{2}(x^{\prime\prime})<\dots<f^{p-1}(x^{\prime})\leq
f^{p-1}(x^{\prime\prime})=\frac{1}{2}$ (1)

It then must hold that $x^{\prime}\geq x^{\prime\prime}$.

Let $g(x)=f^{p}(x)-x$ and note that $g$ is continuous. Because $\frac{1}{2}$
maximizes $f$, it must be the case that $f^{p}(x^{\prime})\leq x^{\prime}$ and
$g(x^{\prime})\leq 0$. Because $f^{p}(x^{\prime\prime})=x^{\prime}$ and
$x^{\prime\prime}\leq x^{\prime}$, $g(x^{\prime\prime})\geq 0$. Hence, there
exists $x^{*}\in[x^{\prime\prime},x^{\prime}]$ such that $g(x^{*})=0$ and
$f^{p}(x^{*})=x^{*}$.

Since $x^{*}\in[x^{\prime\prime},x^{\prime}]$, it must also be the case that
$f^{j}(x^{*})\in[f^{j}(x^{\prime}),f^{j}(x^{\prime\prime})]$ for $j\in[p-1]$.
By Equation (1), it follows that

$f(x^{*})<f^{2}(x^{*})<\dots<f^{p-1}(x^{*})<f^{p}(x^{*})=x^{*}.$

Hence, there exists an increasing $p$-cycle. ∎

$1/2\
$$x^{\prime\prime}$$f(x^{\prime\prime})$$f^{2}(x^{\prime\prime})$$f^{p-2}(x^{\prime\prime})$$x^{\prime}$$f(x^{\prime})$$f^{2}(x^{\prime})$$f^{p-1}(x^{\prime})$$x^{*}$$f\left(x^{*}\right)$$f^{2}\left(x^{*}\right)$$f^{p-2}\left(x^{*}\right)$$f^{p-1}\left(x^{*}\right)$$x$$f(x)$
Figure 9: Visualizes the proof of Proposition 1.

##  Appendix C Additional Proofs for Section 3

###  C.1 Proof of Lemma 1

We restate and prove the lemma. This is the main technical lemma that we use
to get the sharper depth-width tradeoffs and the improved notion of constant
approximation.

See 1

###### Proof.

We first lower-bound the total number of oscillations that will appear an
increasing $p$-cycle is present. Later, we show that the size of the
oscillations is large as well.

Because we have an increasing cycle of itinerary $12\dots p$, we assume (wlog)
that the cycle is $(x_{1},\dots,x_{p})$ with $x_{1}<x_{2}<\dots<x_{p}$. Define
intervals $I_{j}\vcentcolon=[x_{j},x_{j+1}]$ for $j\in\\{1,\dots,p-1\\}$.
Because $f$ is continuous, we conclude that $I_{j+1}\subset f(I_{j})$ for all
$j<p$ and $I_{j}\subset f(I_{p-1})$ for all $j$. Figure 10 visualizes these
relationships.

$x$$f(x)$$x_{p-1}$$x_{p}$$x_{1}$$x_{2}$$x_{3}$$x_{p-2}$$I_{1}$$I_{2}$$I_{p-2}$$I_{p-1}$$I_{1}$$\dotsc$$I_{2}$$I_{3}$$I_{p-2}$$I_{p-1}$
Figure 10: Visualizes the intervals $I_{1},\dots,I_{p-1}$ defined in the proof
of Lemma 1 and which intervals $f$ maps to one another when $f$ has an
increasing $p$-cycle.

Using the methods of Chatziafratis et al. (2019), we define
$y^{(k)}\in\mathbb{N}^{p-1}$ such that $y^{(k)}_{j}$ is a lower bound on the
number of times $f^{k}$ passes through interval $I_{j}$, or

$C_{x_{j},x_{j+1}}(f^{k})\geq y^{(k)}_{j}.$

We can then encode the interval relationships above with
$y^{(k+1)}=A_{p}y^{(k)}$ where $y^{({0})}$ is a vector of all ones and and
$A_{p}\in\\{0,1\\}^{(p-1)\times(p-1)}$ with
$(A_{p})_{i,j}=\mathbbm{1}\left\\{j=p-1\text{ or }i=j+1\right\\}$. We get the
following adjacency matrix for the intervals, capturing the mapping
relationships (under $f$) between them:

$A_{p}=\begin{bmatrix}0&0&0&\cdots&0&1\\\ 1&0&0&\cdots&0&1\\\
0&1&0&\cdots&0&1\\\ 0&0&1&\cdots&0&1\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&0&\cdots&1&1\end{bmatrix}.$

We find the characteristic polynomial of $A_{p}$ and lower-bound $y^{(k+1)}$
with the spectral radius of $A_{p}$. We show by induction on $p\geq 3$ that

$\det(A_{p}-\lambda
I)=(-1)^{p-1}\left(\lambda^{p-1}-\sum_{i=0}^{p-2}\lambda^{i}\right).$

For the base case $p=3$, we have:

$\displaystyle\det(A_{3}-\lambda I)$
$\displaystyle=\begin{vmatrix}-\lambda&1\\\
1&1-\lambda\end{vmatrix}=\lambda^{2}-\lambda-1,$

which satisfies the desired form.

Now, we show the inductive step by expanding the determinant of $A_{p}-\lambda
I$.

$\displaystyle\det(A_{p}-\lambda I)$
$\displaystyle=\begin{vmatrix}-\lambda&0&0&\cdots&0&1\\\
1&-\lambda&0&\cdots&0&1\\\ 0&1&-\lambda&\cdots&0&1\\\ 0&0&1&\cdots&0&1\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&0&\cdots&-\lambda&1\\\
0&0&0&\cdots&1&1-\lambda\end{vmatrix}=-\lambda\begin{vmatrix}-\lambda&0&\cdots&0&1\\\
1&-\lambda&\cdots&0&1\\\ 0&1&\cdots&0&1\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&\cdots&-\lambda&1\\\
0&0&\cdots&1&1-\lambda\end{vmatrix}-\begin{vmatrix}0&0&\cdots&0&1\\\
1&-\lambda&\cdots&0&1\\\ 0&1&\cdots&0&1\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&\cdots&-\lambda&1\\\
0&0&\cdots&1&1-\lambda\end{vmatrix}.$

The left determinant exactly equals $\det(A_{p-1}-\lambda I)$, which we can
expand using the inductive hypothesis. The second equals $(-1)^{p-2}$, because
$p-2$ row swaps (which are elementary row operations) can be used to move the
first row to the bottom and make the matrix upper-triangular with diagonals of
one. We conclude the inductive step below.

$\displaystyle\det(A_{p}-\lambda I)$
$\displaystyle=-\lambda\det(A_{p-1}-\lambda I)-(-1)^{p-2}$
$\displaystyle=-\lambda(-1)^{p-2}\left(\lambda^{p-2}-\sum_{i=0}^{p-3}\lambda^{i}\right)+(-1)^{p-1}=(-1)^{p-1}\left(\lambda^{p-1}-\sum_{i=0}^{p-2}\lambda^{i}\right).$

We find the eigenvalues of $A_{p}$ by finding the roots of the polynomial

$P(x)=\lambda^{p-1}-\sum_{i=0}^{p-2}\lambda^{i}=0.$

Observe that there must be a root greater than $1$ because $P(1)=2-p<0$ and
$P(2)=1>0$. Equivalently, if $\lambda\neq 1$,

$P(x)=\lambda^{p-1}-\frac{1-\lambda^{p-1}}{1-\lambda}=\frac{\lambda^{p}-2\lambda^{p-1}+1}{\lambda-1}=0.$

Hence, finding the largest root of $P$ is equivalent to finding the largest
root of $\lambda^{p}-2\lambda^{p-1}+1$, which is $\rho_{\mathrm{inc},p}$ by
definition.

This implies that the spectral radius of $A_{p}$,
sp$(A_{p})=\rho_{\mathrm{inc},p}>1$, and hence, we also have sp$(A_{p}^{k})=$
sp$(A_{p})^{k}=\rho_{\mathrm{inc},p}^{k}$. Since all the elements in $A_{p}$
and in $A_{p}^{k}$ are non-negative, then the infinity norm of $A_{p}^{k}$ is
by definition the maximum among its row sums. Since the last column of $A_{p}$
is the all 1’s vector, the largest row sum in $A_{p}^{k}$ appears at its last
row:

$||A_{p}^{k}||_{\infty}=\sum_{j=1}^{p-1}(A_{p}^{k})_{p-1,j}$

We can now use the fact that the infinity norm of a matrix is larger than its
spectral norm:

$||A_{p}^{k}||_{\infty}\geq\rho_{\mathrm{inc},p}^{k}$

We conclude that there exists at least one interval $I_{j^{*}}$ (e.g., the
interval $I_{p-1}$) which is crossed at least $\rho_{\mathrm{inc},p}^{k}$
times by $f^{k}$, so
$C_{x_{j^{*}},x_{j^{*}+1}}(f^{k})\geq\rho_{\mathrm{inc},p}^{k}$.

Thus, for some $a^{\prime},b^{\prime}$ we get
$C_{a^{\prime},b^{\prime}}(f^{k})\geq\rho_{\mathrm{inc},p}^{k}$. But can we
find $a^{\prime},b^{\prime}$ with large difference $b^{\prime}-a^{\prime}$?

Now, we show that the intervals traversed are sufficiently large, in order to
lower-bound $C_{a,b}(f^{k})$ with $b-a\geq\frac{1}{18}$. By Lemma 3, there
exists some $j$ with $x_{j+1}-x_{j}\geq\frac{1}{18}$. It suffices to show that
$f^{k}$ traverses the interval $I_{j}$ sufficiently many times.

From earlier in the proof, there exists some $j^{*}$ such that $f$ crosses
$I_{j^{*}}$ at least $N\vcentcolon=\rho_{\mathrm{inc},p}^{k}$ times. We
conclude by showing that every other interval is traversed at least half as
often as this most popular interval, which suggests that
$C_{x_{j},x_{j+1}}(f)\geq\frac{N}{2}$.

For $A\in\mathbb{R}^{(p-1)\times(p-1)}$ as defined earlier in the section and
for $y^{(k)}\vcentcolon=A^{k}\vec{1}$, we argue inductively that the elements
of $y^{(k)}$ are non-decreasing and that $y^{(k)}_{p-1}\leq 2y^{(k)}_{1}$. For
the base case, this is trivially true for $k=0$.

Suppose it holds for $k$. By construction, we have
$y^{(k+1)}_{1}=y^{(k)}_{p-1}$ and $y^{(k+1)}_{j}=y^{(k)}_{j-1}+y^{(k)}_{p-1}$
for all $j>1$. By the inductive hypotheses,

$y^{(k+1)}_{1}\leq y^{(k+1)}_{2}\leq\dots\leq y^{(k+1)}_{p-1}\leq
2y^{(k+1)}_{1}.$

Therefore, $f^{k}$ crosses interval $I_{j}$ at least $\frac{N}{2}$ times, and
$I_{j}$ has width at least $\frac{1}{18}$. The claim immediately follows. ∎

######  Lemma 3.

For some $p\geq 3$, consider a symmetric concave unimodal function $f$ with an
increasing $p$-cycle of $x_{1}<\dots<x_{p}$. Then, there exists $j\in[p-1]$
such that $x_{j+1}-x_{j}\geq\frac{1}{18}$.

###### Proof.

By the continuity of $f$, note that $[x_{1},x_{p}]\subset
f^{3}([x_{p-3},x_{p-2}])$. There then exists some $y_{1}\in[x_{p-3},x_{p-2}]$
such that $f^{3}(y_{1})=y_{1}$,
$y_{2}\vcentcolon=f(y_{1})\in[x_{p-2},x_{p-1}]$, and
$y_{3}\vcentcolon=f(y_{2})\in[x_{p-1},x_{p}]$. Thus, if $f$ has a maximal
$p$-cycle, then $f$ also has a 3-cycle corresponding to
$x_{p-3}<y_{1}<y_{2}<y_{3}<x_{p}$.

We now show that $y_{3}-y_{1}$ must be sufficiently large by concavity. For
$f$ to be concave, the following inequality must hold:

$\displaystyle\frac{f(y_{1})-f(0)}{y_{1}-0}\geq\frac{f(y_{2})-f(y_{1})}{y_{2}-y_{1}}>0>\frac{f(y_{3})-f(y_{2})}{y_{3}-y_{2}}\geq\frac{f(1)-f(y_{3})}{1-y_{3}},$

or equivalently,

$\frac{y_{2}}{y_{1}}\geq\frac{y_{3}-y_{2}}{y_{2}-y_{1}}>0>-\frac{y_{3}-x_{1}}{y_{3}-y_{2}}\geq-\frac{y_{1}}{1-y_{3}}.$

In addition, note that $y_{1}<\frac{1}{2}$ and $y_{3}>\frac{1}{2}$. If the
former were false, then $f(y_{2})\leq f(y_{1})$ (by unimodality), which
contradicts $y_{3}>y_{2}$. If the latter were false, then $f(y_{3})>f(y_{2})$,
which contradicts $y_{1}<y_{3}$.

We consider two cases and show that either way, the interval must have width
at least $\frac{1}{6}$.

  * •

If $y_{2}-y_{1}\leq\frac{2}{5}(y_{3}-y_{1})$, then
$\frac{y_{3}-y_{2}}{y_{2}-y_{1}}\geq\frac{3}{2},$ which mandates that
$y_{1}\leq\frac{2y_{2}}{3}$ to ensure concavity. Thus,

$y_{3}-y_{1}\geq y_{3}-\frac{2y_{2}}{3}\geq\frac{y_{3}}{3}\geq\frac{1}{6}.$

  * •

If $y_{2}-y_{1}\geq\frac{2}{5}(y_{3}-y_{1})$, then
$\frac{y_{3}-y_{1}}{y_{3}-y_{2}}\geq\frac{5}{3},$ and thus
$y_{1}\geq\frac{5}{3}(1-y_{3})$ and $y_{3}\geq 1-\frac{3y_{1}}{5}$. Then,

$y_{3}-y_{1}\geq 1-\frac{3y_{1}}{5}-y_{1}=1-\frac{8y_{1}}{5}\geq\frac{1}{5}.$

Thus, we must have

$\max\\{x_{p-2}-x_{p-3},x_{p-2}-x_{p-1},x_{p}-x_{p-1}\\}\geq\frac{1}{18}.\qed$

###  C.2 Proof of Fact 1

See 1

###### Proof.

Let $P_{\mathrm{inc},p}(\lambda)=\lambda^{p}-2\lambda^{p-1}+1$.

First, observe that $\rho_{\mathrm{inc},p}<2$, because
$P_{\mathrm{inc},p}(\lambda)>0$ whenever $\lambda\geq 2$. We lower-bound
$\rho_{\mathrm{inc},p}$ by finding some $\lambda$ for each $p$ such that
$P_{\mathrm{inc},p}(\lambda)\leq 0$ or equivalently
$\lambda^{p-1}(2-\lambda)\geq 1$ for all $p\geq 3$, which bounds
$\rho_{\mathrm{inc},p}$ by the Intermediate Value Theorem.

Consider $\lambda=2-\frac{4}{2^{p}}$. Then,

$\displaystyle\lambda^{p-1}(2-\lambda)$
$\displaystyle=\left(2-\frac{4}{2^{p}}\right)^{p-1}\cdot\frac{4}{2^{p}}=2\left(1-\frac{2}{2^{p}}\right)^{p-1}$
$\displaystyle\geq
2\left(1-\frac{2(p-1)}{2^{p}}\right)=2-2\cdot\frac{p-1}{2^{p-1}}$
$\displaystyle\geq 2-2\cdot\frac{1}{2}=1.\qed$

###  C.3 Previous Results about Hardness of Approximating Oscillatory
Functions

We rely on prior results from Chatziafratis et al. (2019, 2020) to show that
an iterated function $f^{k}$ is inapproximable by neural networks. These
results hold if $f^{k}$ has sufficiently many crossings of some interval. We
apply these results later with improved bounds on both the number and the size
of crossings.

Chatziafratis et al. (2019) show that the classification error of $f^{k}$ can
be bounded if there are enough oscillations.

######  Theorem 10 ((Chatziafratis et al., 2019), Section 4).

Consider any continuous $f:[0,1]\to[0,1]$ and any $g\in\mathcal{N}(u,\ell)$.
Suppose there exists $a<b$ such that $C_{a,b}(f)=\Omega(\rho^{t})$ and suppose
$u\leq\frac{1}{8}\rho^{k/\ell}$. Then, for $t=\frac{a+b}{2}$, there exists $S$
with $\left|S\right|=\frac{1}{2}\left\lfloor\rho^{k}\right\rfloor$ samples
such that

$\mathcal{R}_{S,t}(f^{k},g)\geq\frac{1}{2}-\frac{(2u)^{\ell}}{n}.$

We adapt that claim to lower-bound the $L_{\infty}$ approximation of $f^{k}$
by $g$.

######  Corollary 2.

Consider any continuous $f:[0,1]\to[0,1]$ and any $g\in\mathcal{N}(u,\ell)$.
Suppose there exists $a<b$ such that $C_{a,b}(f)=\Omega(\rho^{t})$ and suppose
$u\leq\frac{1}{8}\rho^{k/\ell}$. Then,

$\left\|f^{k}-g\right\|_{\infty}\geq\frac{b-a}{2}.$

###### Proof.

By Theorem 10, there exists some $x\in[0,1]$ such that (wlog) $f^{k}(x)\leq a$
and $g(x)\geq\frac{a+b}{2}$. The conclusion for the $L_{\infty}$ error is
immediate by definition. ∎

Chatziafratis et al. (2020) give a lower-bound on the ability of a neural
network $g$ to $L_{1}$-approximate $f^{k}$, provided a correspondence between
the Lipschitz constant of $f$ and the rate of oscillations $\rho$.

######  Theorem 11 (Chatziafratis et al. (2020) Theorem 3.2).

Consider any $L$-Lipschitz $f:[0,1]\to[0,1]$ and any
$g\in\mathcal{N}(u,\ell)$. Suppose there exists $a<b$ such that
$C_{a,b}(f)=\Omega(\rho^{t})$. If $L\leq\rho$ and
$u\leq\frac{1}{16}\rho^{k/\ell}$, then

$\left\|f^{k}-g\right\|_{1}=\Omega((b-a)^{2}).$

The Lipschitzness assumption is extremely strict, especially because they show
in their Lemma 3.1 that $L\geq\rho$ whenever $f$ has a period of odd length.

###  C.4 Proof of Corollary 1

See 1

###### Proof.

This theorem follows from Theorem 5 and Lemma 1. Because
$f_{\text{tent},\rho_{p}/2}$ is $\rho_{p}$-Lipschitz, it remains only to prove
that there exists an increasing $p$-cycle. We show that

$\frac{1}{2},f\left(\frac{1}{2}\right),\dots,f^{p-1}\left(\frac{1}{2}\right)$

is such a cycle.

By definition of the tent map,
$f(\frac{1}{2})=\frac{\rho_{\mathrm{inc},p}}{2}$ and
$f^{2}(\frac{1}{2})=\rho_{\mathrm{inc},p}(1-\frac{\rho_{\mathrm{inc},p}}{2})$.
If we assume for now that $f^{j}(\frac{1}{2})\leq\frac{1}{2}$ for all
$j\in\\{2,\dots,p-1\\}$, then

$f^{p}\left(\frac{1}{2}\right)=\rho_{\mathrm{inc},p}^{p-1}\left(1-\frac{\rho_{\mathrm{inc},p}}{2}\right)=-\frac{1}{2}\left(\rho_{\mathrm{inc},p}^{p}-2\rho_{\mathrm{inc},p}^{p-1}+1\right)+\frac{1}{2}=0+\frac{1}{2}.$

Because $f^{p}(\frac{1}{2})=\frac{1}{2}$ and we assumed that
$f^{j+1}(\frac{1}{2})=\rho_{\mathrm{inc},p}f^{j}(\frac{1}{2})$ for $j\geq 2$
and $\rho>1$, it must be the case that $f^{j}(\frac{1}{2})\leq\frac{1}{2}$ for
all $j\in\\{2,\dots,p-1\\}$.

Lemma 1 thus implies that $f^{k}$ has $\Omega(\rho_{\mathrm{inc},p}^{k})$
crossings, which enables us to complete the proof by invoking Theorem 5, since
the Lipschitzness condition is met. ∎

###  C.5 Proof of Lemma 2

See 2

###### Proof.

By Theorems 2.94 and 3.11.1 of Alsedà et al. (2000), there exists a $p$-cycle
of the form

$x_{p}<x_{p-2}<\dots<x_{3}<x_{1}<x_{2}<x_{4}<\dots<x_{p-1},$

which is known as a Stefan cycle. The analysis of Section 3.2 of Chatziafratis
et al. (2020) shows that
$C_{[x_{1},x_{2}]}(f^{k})\geq\rho_{\mathrm{odd},p}^{k}$. Their exploitation of
the relationships between intervals is visualized in Figure 11. By the
continuity of $f$, applying $f$ an additional $p-1$ times gives
$C_{[x_{p},x_{1}]}(f^{k+p-1})\geq\rho_{\mathrm{odd},p}^{k}$. Because
$[x_{p-2},x_{1}]\subset[x_{p},x_{1}]$, applying $f$ one more time gives
$C_{[x_{2},x_{p-1}]}(f^{k+p})\geq\rho_{\mathrm{odd},p}^{k}$.

$x$$f(x)$$x_{p-1}$$x_{p}$$x_{p-2}$$x_{3}$$x_{p-3}$$I_{1}$$I_{2}$$I_{(p-1)/2}$$I_{1}$$\dotsc$$I_{2}$$I_{p-2}$$I_{p-1}$$x_{p-4}$$x_{1}$$x_{2}$$x_{4}$$x_{p-5}$$I_{(p+1)/2}$$I_{(p+3)/2}$$I_{p-3}$$I_{p-1}$$\dotsc$$I_{(p-3)/2}$$I_{(p-1)/2}$$I_{(p+1)/2}$$I_{(p+3)/2}$
Figure 11: Gives an example of a Stefan $p$-cycle (which is relied upon in
Lemma 2 and demonstrates the interval relationships). Analogous to Figure 10.

Hence, by redefining $k$, we have

$\max\\{C_{[x_{1},x_{2}]}(f^{k}),C_{[x_{2},x_{p-1}]}(f^{k}),C_{[x_{p},x_{1}]}(f^{k})\\}\geq\rho_{\mathrm{odd},p}^{k-p}.$

Since $[x_{p},x_{p-1}]$ is the disjoint union of $[x_{1},x_{2}]$,
$[x_{2},x_{p-1}]$, and $[x_{p},x_{1}]$, there exists
$[a,b]\subset[x_{p},x_{p-1}]$ with $b-a\geq\frac{1}{3}(x_{p-1}-x_{p})$ such
that $C_{[a,b]}(f^{k})\geq\\\ rhoodd{p}^{k-p}$.

The problem reduces to placing a lower bound on $x_{p-1}-x_{p}$. To do so, we
derive contradictions on the concavity and symmetry of $f$. Let
$r=f(\frac{1}{2})\in(x_{p},1)$ be the the largest outcome of $f$, and let

$a=\sup_{x,x^{\prime}\in[1-r,r]}\left|\frac{f(x)-f(x^{\prime})}{x-x^{\prime}}\right|$

be the maximum absolute slope of $f$ on $[1-r,r]$. $a$ must be finite by the
concavity and continuity of $f$, and if $f$ is differentiable,
$a=f^{\prime}(1-r)=-f^{\prime}(r)$. Thus, $f$ is $a$-Lipschitz on that
interval.

Because $f([x_{p},x_{p-1}])\subseteq[x_{p},r]\subset[1-r,r]$, it follows that
$\left|f^{2}(x)-f^{2}(x^{\prime})\right|\leq a^{2}\left|x-x^{\prime}\right|$.
Thus, $x_{2}-x_{p}\leq a^{2}(x_{p-2}-x_{p})$ and $x_{2}-x_{p}\leq
x_{4}-x_{p}\leq a^{2}(x_{2}-x_{p-2})$. Averaging the two together, we have
$x_{2}-x_{p}\leq\frac{a^{2}}{2}(x_{2}-x_{p})$, which means $a\geq\sqrt{2}$.

To satisfy concavity, the following must be true:

$\frac{f(1-r)-f(0)}{1-r-0}=\frac{f(r)}{1-r}\geq a\geq\sqrt{2}.$

We rearrange the inequality and apply properties of monotonicity to lower-
bound $r$ away from $\frac{1}{2}$:

$r\geq 1-\frac{f(r)}{\sqrt{2}}\geq
1-\frac{f(x_{p-1})}{\sqrt{2}}=1-\frac{x_{p}}{\sqrt{2}}>1-\frac{1}{2\sqrt{2}}.$

It also must be the case for any $x\in[\frac{1}{2},1]$, that:

$\left|\frac{f(x)-f\left(\frac{1}{2}\right)}{x-\frac{1}{2}}\right|\leq 2.$

Otherwise, the concavity of $f$ would force $f(\frac{1}{2})>1$.

We finally assemble the pieces to lower-bound the gap between $x_{p-1}$ and
$x_{p}$:

$\displaystyle x_{p-1}-x_{p}$ $\displaystyle\geq
x_{p-1}-\frac{1}{2}\geq-\frac{1}{2}\left(f(x_{p-1})-f\left(\frac{1}{2}\right)\right)=\frac{r}{2}-\frac{x_{p}}{2}$
$\displaystyle>\frac{1}{2}-\frac{1}{4\sqrt{2}}-\frac{1}{4}=\frac{1}{4}-\frac{1}{4\sqrt{2}}>0.07.\qed$

###  C.6 Necessity of Symmetry and Concavity Assumptions in Theorems 4 and 5

We demonstrate the weakness of the bounds promised by Chatziafratis et al.
(2019, 2020); Bu et al. (2020) and argue that our assumptions of symmetry and
concavity are necessary in order to avoid such non-vacuous bounds. To do so,
we exhibit two families of functions in Propositions 2 and 3 which contain
functions with increasing $p$-cycles for every $p$ that produce large numbers
of oscillations, yet are trivial to approximate because their oscillations can
be made arbitrarily small. The functions considered in both cases are unimodal
and lack symmetry and concavity respectively.

These expose a fundamental shortcoming of other approaches to the hardness of
neural network approximation in the aforementioned works because they all rely
on showing that for every mapping $f$ meeting some condition (e.g. odd period,
positive topological entropy), there exists some $[a,b]\in[0,1]$ where
$C_{a,b}$ is exponentially large, and hence no poly-size shallow neural
network $g$ can obtain $L_{\infty}(f^{k},g)\leq P(b-a)$ for some polynomial
$P$. However, because $[a,b]$ depends on $f$, their difference can potentially
be arbitrarily small. The propositions show that this concern is significant
and that $[a,b]$ indeed becomes arbitrarily narrow for simple 3-periodic
functions. While Chatziafratis et al. (2019) avoid addressing this issue head-
on by focusing on classification error over $L_{\infty}$ error, their
classification lower-bounds rely on misclassification of points whose actual
distance can be shrinking (see for example Figure 12).

The implications of these propositions contrast with the more robust hardness
results we present in Theorems 4, 5, 6, and 7, which leverage unimodality,
symmetry, and concavity to ensure that the accuracy of approximation can be no
better than some constant (independent on $f,p$) when the neural network $g$
is too small. We show here that those assumptions are necessary by exhibiting
functions that satisfy all but one, and become easy to
$L_{\infty}$-approximate with small depth-2 ReLU networks.

######  Proposition 2.

For $p\geq 3$ and for sufficiently small $\epsilon>0$, there exists a concave
unimodal mapping $f$ with a chaotic $p$-cycle such that for any $k$, there
exists $g\in\mathcal{N}(3,2)$ with

$L_{\infty}(f^{k},g)\leq\epsilon.$

###### Proof.

For all $j\in[p]$, let $x_{j}=1-\frac{p-j+1}{p}\epsilon$. Define $f$ to be a
piecewise-linear function with $p+1$ pieces chosen with boundaries that
satisfy

$f(0)=0,f(x_{1})=x_{2},f(x_{2})=x_{3},\dots,f(x_{p-1})=x_{p},f(x_{p})=x_{1},f(1)=0.$

We visualize $f$ for $p=3$ in Figure 12. $f$ is unimodal because it increases
on $[0,x_{p-1}]$ and decreases on $[x_{p-1},1]$. It is concave because
$f^{\prime}(x)$ does not increase as $x$ grows, since

$f^{\prime}(x)=\begin{cases}\frac{1-\frac{p-1}{p}\epsilon}{1-\epsilon}>1&x\in[0,x_{1})\\\
1&x\in(x_{1},x_{p-1})\\\ -p+1&x\in(x_{p-1},x_{p})\\\
-\frac{1-\epsilon}{\epsilon}&x\in(x_{p},1],\end{cases}$

as long as $\frac{1-\epsilon}{\epsilon}>p-1$.

Figure 12: Plots the asymmetric function with a $p$-cycle referenced in
Proposition 2 for $p=3$ and $\epsilon=0.1$. While $f$ oscillates frequently,
$f$ can be trivially $0.1$-approximated by three ReLUs. As $\epsilon\to 0$,
the $L_{\infty}$ approximation hardness guarantees implied by Chatziafratis et
al. (2019) become vacuous because the oscillations, even though they are
exponentially many, they shrink in size.

We show inductively that for all $k$, there exists $a_{k}<b_{k}$ such that
$f^{k}(a_{k})=f^{k}(b_{k})=1-\epsilon$,
$f^{k}([a_{k},b_{k}])\in[1-\epsilon,1]$, and $f^{k}$ has exactly one linear
piece for each of the intervals $[0,a_{k}]$ and $[b_{k},1]$.

These are true for the base case $k=1$ for $a_{1}\in(0,x_{1})$ and
$b_{1}=x_{p}$.

If the claim holds for $k$, then there is some $a_{k+1}\in(0,a_{k})$ and
$b_{k+1}\in(b_{k},1)$ such that $f(a_{k+1})=f(b_{k+1})=a_{k}$. Then,
$f^{k+1}(a_{k+1})=f^{k+1}(b_{k+1})=1-\epsilon$ and
$f^{k+1}([0,a_{k+1}])=f^{k+1}([b_{k+1},1])=[0,1-\epsilon]$. For all
$x\in[0,a_{k+1}]$, $f^{j}(x)\leq 1-\epsilon$ for all $j\leq k+1$. Hence,
$f^{k+1}$ is linear on $[0,a_{k+1}]$ (and also $[b_{k+1},1]$. Because
$f([x_{1},x_{p}])=[x_{1},x_{p}]$,
$f^{k+1}([a_{k+1},b_{k+1}])\subseteq[x_{1},x_{p}]\subseteq[1-\epsilon,1]$. The
claim then holds for $k+1$.

Thus, the piecewise linear mapping $g$ with boundaries $g(0)=0$,
$g(a_{k})=1-\epsilon$, $g(b_{k})=1-\epsilon$, and $g(1)=0$ is an
$\epsilon$-approximation of $f$. Because $g$ has three pieces and contains the
origin, it can be exactly represented by a linear combination of four ReLUs,
and hence as a depth-2 neural network of width 3. ∎

######  Proposition 3.

For $p\geq 3$ and for sufficiently small $\epsilon>0$, there exists a
symmetric unimodal mapping $f$ with a chaotic $p$-cycle such that for any $k$,
there exists $g\in\mathcal{N}(3,2)$ with

$L_{\infty}(f^{k},g)\leq\epsilon.$

###### Proof.

Let $x_{j}=\frac{1}{2}-\frac{p-1-j}{2(p-1)}\epsilon$ for all $j\in[p-1]$ and
$x_{p}=\frac{1}{2}+\frac{\epsilon}{2}$. Let $f$ be a piecewise-linear function
with boundaries

$\displaystyle f(0)=0,\
f\left(\frac{1}{2}-\frac{\epsilon}{2}\right)=\frac{1}{2}-\frac{p-2}{p-1}\cdot\frac{\epsilon}{2},\
f\left(\frac{1}{2}-\frac{\epsilon}{2(p-1)}\right)=\frac{1}{2},\
f\left(\frac{1}{2}\right)=\frac{1}{2}+\frac{\epsilon}{2},$ $\displaystyle
f\left(\frac{1}{2}+\frac{\epsilon}{2(p-1)}\right)=\frac{1}{2},\
f\left(\frac{1}{2}+\frac{\epsilon}{2}\right)=\frac{1}{2}-\frac{p-2}{p-1}\cdot\frac{\epsilon}{2},\
f(1)=0.$

We visualize $f$ for $p=3$ in Figure 13. Note that $f$ is symmetric and
unimodal and has an increasing $p$-cycle $x_{1}<\dots<x_{p}$. It is not
concave because $f^{\prime}(x)=1$ for $x\in[x_{1},x_{p-2}]$ and
$f^{\prime}(x)=2(p-1)$ for $x\in[x_{p-2},x_{p-1}]$.

Figure 13: Another example of a function with a 3-cycle that can be
$\epsilon$-approximated for arbitrarily small $\epsilon$. (Here,
$\epsilon=0.1$.) This function corresponds to the one in Proposition 3 and the
Chatziafratis et al. (2019) bounds are again vacuous for small $\epsilon$.
Unlike Figure 12, this function is symmetric, but not concave.

Using a very similar argument to argument from the proof of Proposition 2, for
all $k$, there exists $a_{k}<b_{k}$ such that $f^{k}$ is linear on $[0,a_{k}]$
and $[b_{k},1]$ and
$f^{k}([a_{k},b_{k}])\in[\frac{1}{2}-\epsilon,\frac{1}{2}+\epsilon]$. As
before, there exists a piecewise linear function with three pieces (which can
be thought of as a depth-2 neural network of width 3) that
$\epsilon$-approximates $f$. ∎

##  Appendix D Additional Proofs for Section 4

###  D.1 Preliminaries

Before reintroducing and proving the theorems about the doubling and chaotic
regime, we introduce topological entropy and define VC-dimension.

####  D.1.1 Topological Entropy

Topological entropy is a well-known measure of function complexity in
dynamical systems that measures the “bumpiness” of a mapping. Like we do with
chaotic itineraries, Bu et al. (2020) draw analogies between the neural
network approximability of $f^{k}$ and the topological entropy of $f$. We do
not give a rigorous definition of topological entropy, but we include a well
known result connecting topological entropy to the number of monotone pieces
(not constant-sized crossings), which is stated as Lemma 3 of the
aforementioned work.

######  Lemma 4.

[Misiurewicz and Szlenk (1980); Young (1981)] If $f:[0,1]\to[0,1]$ is
continuous and piece-wise monotone, then the topological entropy of $f$
satisfies the following:

$h_{\mathrm{top}}(f)=\lim_{k\to\infty}\frac{1}{k}\log M(f^{k}).$

####  D.1.2 VC-Dimension

We capture the complexity of the mappings produced by repeated application of
$f$, by measuring the capability of a family of iterates to fit arbitrarily-
labeled samples with the VC-dimension. For some threshold parameter
$t\in(0,1)$, we first define a hypothesis class that we use to cast this
family of iterated functions as Boolean-valued.

######  Definition 7.

For some unimodal $f:[0,1]\to[0,1]$ and threshold $t\in(0,1)$, let

$\mathcal{H}_{f,t}:=\\{[[f^{k}]]_{t}:k\in\mathbb{N}\\}$

be the Boolean-valued hypothesis class of classifiers of composed functions.

The following is the standard definition of the VC-dimension:

######  Definition 8 (Vapnik and Chervonenkis (2013)).

For some hypothesis class $\mathcal{H}$ containing functions
$[0,1]\to\\{0,1\\}$, we say that $\mathcal{H}$ _shatters_ samples
$x_{1},\dots,x_{d}\in[0,1]$ if for every labeling of the samples
$\sigma_{1},\dots,\sigma_{d}\in\\{0,1\\}$, there exists some $h\in\mathcal{H}$
such that $h(x_{i})=\sigma_{i}$ for all $i\in[d]$. The _VC-dimension_ of
$\mathcal{H}$, $\text{VC}(\mathcal{H})$ is the maximum $d$ such that there
exists $x_{1},\dots,x_{d}\in[0,1]$ that $\mathcal{H}$ shatters.

$\text{VC}(\mathcal{H}_{f,t})$ will be a useful measurement of complexity of
the mapping $f$, which as we show is tighly connected with the notion of
periodicity and oscillations. Notably, this is a measurement of the complexity
of iterated maps and is not a typical formulation of VC-dimension for neural
networks, since those typically would consider a fixed depth and a fixed
width, but variable values for the weights, rather than fixed $f$ and variable
$k$.

###  D.2 Proof for Theorem 8 and 9

See 8

###### Proof.

Claim 1 follows from a somewhat involved argument in Appendix D.3 that uses an
inductive argument to compare the behavior of a mapping with a maximal
$p$-cycle to one with a maximal $\frac{p}{2}$-cycle. By categorizing intervals
of $[0,1]$ based on how $f^{k}$ behaves on that interval, we analyze how
$f^{k+1}$ in turn behaves, which leads to a bound on the monotone pieces
$M(f^{k})$.

Claim 2 is a simple consequence of Claim 1, by using the fact that a ReLU
network can piecewise approximate each monotone piece of $f^{k}$. This
argument appears in Appendix D.4.

Claim 3 follows easily from Claim 1 and Lemma 4. We note that this derivation
about the topological entropy and the periodicity of $f$ is a known fact in
the dynamical systems community.

Claim 4 relies on another recursive argument that frames VC-dimension in terms
of the possible trajectories of $f^{k}(x)$ for fixed $x$ and changing $k$. We
characterize these trajectories by making use of Regular Expressions and by
bounding the corresponding VC dimension in Appendix D.5. ∎

See 9

###### Proof.

Claims 1 and 2 are immediate implications Theorems 1.5 and 1.6 of
Chatziafratis et al. (2019). Claim 3 follows by applying Lemma 4 to Claim 1
(again this derivation about the topological entropy is basic in the
literature on dynamical systems).

The most interesting part of the theorem is the last claim. We prove Claim 4
in Appendix D.6 by showing that the VC-dimension of the class is at least $d$
for all $d\in\mathbb{N}$. The argument relies on the existence of an infinite
number of cycles of other lengths, as guaranteed by Sharkovsky’s Theorem. ∎

###  D.3 Proof of Theorem 8, Claim 1

We restate Claim 1 of the theorem as the following proposition and prove it.

######  Proposition 4 (Claim 1 of Theorem 8).

Suppose $f$ is a symmetric unimodal mapping whose maximal cycle is of length
$p=2^{q}$. Then, for any $k\in\mathbb{N}$, $M(f^{k})=O((4k)^{q+1})$.

In order to bound the number of times $f$ oscillates based on its power-of-two
periods, we categorize $f$ by its cyclic behavior and the bound the number of
local maxima and minima $f$ has based on its characterization.

######  Definition 9 (Category).

For $q\geq 0$ and $z\in\\{0,1\\}$, let $\mathcal{F}_{q,z}$ contain the set of
all symmetric unimodal functions $f$ such that (1) $f$ has a $2^{q}$-cycle,
(2) $f$ does not have a $2^{q+1}$-cycle, and (3)
$[[f^{2^{q}}(\frac{1}{2})]]_{1/2}=z$.

We abuse notation to let
$M(\mathcal{F}_{q,z}^{k})=\max_{f\in\mathcal{F}_{q,z}}M(f^{k})$. Thus, for $f$
given in the theorem statement with a $2^{q}$-cycle, but not a
$2^{q+1}$-cycle, our final bound is obtained by

$M(f^{m})\leq\max\\{M(\mathcal{F}_{q,0}^{m}),M(\mathcal{F}_{q,1}^{m})\\}.$

We let $M(f,a,b)$ represent the number of monotone pieces of $f$ on the sub-
interval $[a,b]\subset[0,1]$.

We build a large-scale inductive argument by first bounding base cases
$M(\mathcal{F}_{0,0}^{k})$ and $M(\mathcal{F}_{0,1}^{k})$. Then, we relate
$M(\mathcal{F}_{q,z}^{k})$ to $M(\mathcal{F}_{q-1,1-z}^{k})$ to get the
desired outcome.

Before beginning the proof, we state a slight refinement of the part of the
theorem, which takes into account the newly-introduced categories, from which
the claim follows.

######  Proposition 5.

For any $k\in\mathbb{N}$, $q\geq 0$, and $z\in\\{0,1\\}$,

$M(\mathcal{F}_{q,z}^{k})\leq\begin{cases}2(3q)^{k}&\text{$q$ is even, $z=0$,
or $q$ is odd, $z=1$}\\\ 2(3q)^{k+1}&\text{$q$ is even, $z=1$, or $q$ is odd,
$z=0$}.\end{cases}$

Thus, proving Proposition 5 is sufficient to prove Proposition 4. The
remainder of the section proves Proposition 5.

####  D.3.1 Special Case Proof for $q=1$

We show that $M(\mathcal{F}_{0,0}^{k})=2$ and $M(\mathcal{F}_{0,1}^{k})=2k$.

For $f_{r}$ as defined above, we characterize the number of oscillations that
are added by increasing $r$ past $\frac{1}{2}$, where super-stability of a
fixed point exists. Figure 14 illustrates those results.

Figure 14: The base case results of Proposition 5 demonstrate the number of
oscillations of $f^{k}$ increases when $f$ moves from $\mathcal{F}_{0,0}$ to
$\mathcal{F}_{0,1}$. The plots show $f$ and $f^{5}$ for
$f\in\mathcal{F}_{0,0}$ ($f=f_{\text{log},0.45}$) on the left and
$f\in\mathcal{F}_{0,1}$ ($f=f_{\text{log},0.775}$) on the right.

To analyze the oscillation patterns of $f^{k}$, we define several “building
blocks,” which represent disjoint pieces of $f^{k}$. That is, the interval
$[0,1]$ can be partitioned into several sub-intervals, each of which has
$f^{k}$ follow certain simple behavior that we categorize. We argue that any
iterate can be decomposed into those pieces and then show how applying $f$ to
$f^{k}$ modifies the pieces in order to analyze $f^{k+1}$. Here are the
function pieces that we analyze, which map interval $[a,b]\subseteq[0,1]$ to
$[0,1]$:

######  Definition 10.

For any $f:[0,1]\rightarrow[0,1]$ and for any $[a,b]\subseteq[0,1]$, $f$ is
referred to on interval $[a,b]$ as:

  * •

a increasing crossing piece $\mathsf{Ic}$ if $f$ is strictly increasing on
$[a,b]$ and has $f(a)=0$, $f(b)>\frac{1}{2}$, and $f^{\prime}(b)>0$;

  * •

a decreasing crossing piece $\mathsf{Dc}$ if $f$ is strictly decreasing on
$[a,b]$ and has $f(a)>\frac{1}{2}$, $f(b)=0$, and $f(a)<0$;

  * •

a up peak $\mathsf{Up}$ if there exists some $c\in(a,b)$ that maximizes $f$ on
$[a,b]$, $f$ is strictly increasing on $[a,c)$, $f$ is strictly decreasing on
$(c,b]$, and $f(x)>\frac{1}{2}$ for all $x\in[a,b]$;

  * •

a up valley $\mathsf{Uv}$ if there exists some $c\in(a,b)$ that minimizes $f$
on $[a,b]$, $f$ is strictly decreasing on $[a,c)$, $f$ is strictly increasing
on $(c,b]$, and $f(x)>\frac{1}{2}$ for all $x\in[a,b]$; and

  * •

a down peak $\mathsf{Dp}$ if there exists some $c\in(a,b)$ that maximizes $f$
on $[a,b]$, $f$ is strictly increasing on $[a,c)$, $f$ is strictly decreasing
on $(c,b]$, and $f(x)\leq\frac{1}{2}$ for all $x\in[a,b]$.

If there exists a sequence of intervals $J_{1},\dots,J_{m}$ such that $f$ is
piece $\eta_{i}$ on $J_{i}$, then we represented $f$ with the string
$\eta_{1}\dots\eta_{m}$.

Figure 15: For $f\in\mathcal{F}_{0,1}$ ($f=f_{\text{log},0.775}$), visualizes
the decomposition of $f$, $f^{2}$, and $f^{3}$ into
$\mathsf{Ic}\mathsf{Up}\mathsf{Dc}$,
$\mathsf{Ic}\mathsf{Up}\mathsf{Uv}\mathsf{Up}\mathsf{Dc}$, and
$\mathsf{Ic}(\mathsf{Up}\mathsf{Uv})^{2}\mathsf{Up}\mathsf{Dc}$ respectively.

We specify an invariant for each part of the theorem, such that proving the
invariant is sufficient to prove the proposition:

  1. 1.

If $f\in\mathcal{F}_{0,0}$, then $f^{k}$ is a down peak on $[0,1]$ for all
$k$, and $f^{k}$ has two monotone pieces.

  2. 2.

If $f\in\mathcal{F}_{0,1}$, $f$ is represented by
$\mathsf{Ic}(\mathsf{Up}\mathsf{Uv})^{k-1}\mathsf{Up}\mathsf{Dc}$. That is,
$[0,1]$ can be partitioned into $2k+1$ subsequent intervals $J_{1},\dots
J_{2k+1}$ such that $f^{k}$ is an increasing crossing piece on $J_{1}$, a
decreasing crossing piece on $J_{2k+1}$ (if $k\neq 0$), an up peak on $J_{2j}$
for $j\in\\{1,\dots,k\\}$, and a up valley on $J_{2j+1}$ for
$j\in\\{1,\dots,k-1\\}$. Hence, $f^{k}$ has $k$ distinct maxima and $2k$
monotone pieces. Figure 15 illustrates this invariant.

Base Case:

  1. 1.

For $f\in\mathcal{F}_{0,0}$, $f^{1}=f$ is trivially a down peak on $[0,1]$ by
the definition of $\mathcal{F}_{0,0}$, since $\frac{1}{2}$ maximizes $f$.

  2. 2.

For $f\in\mathcal{F}_{0,1}$, $f$ can be represented by
$\mathsf{Ic}\mathsf{Up}\mathsf{Dc}$. That is, $[0,1]$ can be decomposed into
intervals $I_{1}$, $I_{2}$, and $I_{3}$, on which $f_{r}$ is an increasing
crossing piece, an up peak, and a decreasing crossing piece respectively.

Inductive Step:

We examine what happens to each function piece when $f$ is applied to it. We
can use the following analysis, along with the inductive hypothesis to show
that $f^{k+1}$ can be decomposed as we expect it to be.

  1. 1.

Examining the down peak proves first invariant for the case when
$f\in\mathcal{F}_{0,0}$. Because $f$ strictly increases on $[0,\frac{1}{2}]$
and because $f([0,1])\subseteq[0,\frac{1}{2}]$ if $f^{k}$ is a down peak,
$f\circ f^{k}$ also supports a down peak on $[0,1]$.

Because we inductively assume that $f^{k}$ is a low peak on $[0,1]$, it then
follows that $f^{k+1}$ is also a down peak on $[0,1]$.

  2. 2.

We first prove a claim, which implies that $f$ has no down peaks for
$f\in\mathcal{F}_{0,1}$. Let $x_{\max}=f(\frac{1}{2})$,

######  Claim 1.

If $f\in\mathcal{F}_{0,1}$, then
$f((\frac{1}{2},x_{\max}])\subseteq(\frac{1}{2},x_{\max}]$.

###### Proof.

Because $\frac{1}{2}$ maximizes $f$, $f(x)\leq x_{\max}$ for all
$x\in[\frac{1}{2},x_{\max}]$. Since $f$ monotonically decreases, on
$[\frac{1}{2},x_{\max}]$, the claim can only be false if
$f(x_{\max})<\frac{1}{2}$. We show by contradiction that this is impossible.

Because $f$ is continuous and monotonically increases on $[0,\frac{1}{2}]$ and
ranges from $0$ to $x_{\max}\geq\frac{1}{2}$, there exists some
$x^{\prime}\leq\frac{1}{2}$ such that $f(x^{\prime})=\frac{1}{2}$ and
$f^{2}(x^{\prime})=x_{\max}$.

Let $g(x)=f^{2}(x)-x$. By assumption,
$g(\frac{1}{2})=f(x_{\max})-\frac{1}{2}<0$. By definition of $x^{\prime}$,
$g(x^{\prime})=\frac{1}{2}-x^{\prime}\geq 0$. Because $g$ is continuous, the
Intermediate Value Theorem implies the existence of
$x^{\prime\prime}\in[x^{\prime},\frac{1}{2})$ such that
$g(x^{\prime\prime})=0$ and $f^{2}(x^{\prime\prime})=x^{\prime\prime}$. Since
$f$ has no two-cycles, it must be the cause that
$f(x^{\prime\prime})=x^{\prime\prime}$ and $x^{\prime\prime}=\frac{1}{2}$.
However, this contradicts our finding that $x^{\prime\prime}<\frac{1}{2}$,
which means that $f(x_{\max})\geq\frac{1}{2}$ and the claim holds. ∎

Now, we proceed with analyzing each of the function pieces on some interval
$[a,b]\subseteq[0,1]$ when $f\in\mathcal{F}_{0,1}$. The transformations are
visualized in Figure 15.

     * •

Increasing crossing piece: If $f^{k}$ has an $\mathsf{Ic}$ on $[a,b]$, then
$f^{k+1}$ can be represented by $\mathsf{Ic}\mathsf{Up}$ on $[a,b]$.

There exist $c$ and $d$ such that $a<d<c<\frac{1}{2}<b$,
$f^{k}(c)=\frac{1}{2}$, and $f^{k}(d)=c$. Then, $[a,\frac{1}{2}(c+d)]$
supports an increasing crossing piece on $f\circ f^{k}$—because
$f(f^{k}(a))=0$, $f(f^{k}(\frac{1}{2}(c+d)))>\frac{1}{2}$, and $f\circ f^{k}$
is strictly increasing on that interval since $f$ is increasing before
reaching $\frac{1}{2}$. $[0.5(c+d),b]$ supports a high peak—because $c$ is a
local maxima on $f\circ f^{k}$, and $f\circ f^{k}$ is strictly increasing
before $c$ and strictly decreasing after $c$.

     * •

Decreasing crossing piece: For the same arguments, $f^{k+1}$ can represented
by $\mathsf{Up}\mathsf{Dc}$ on $[a,b]$ if $f^{k}$ is represented by
$\mathsf{Dc}$ on $[a,b]$.

     * •

Up peak: Because $f$ strictly decreases for $x>\frac{1}{2}$ and because
$f^{k}([a,b])\subseteq(\frac{1}{2},x_{\max}]$ if $\mathsf{Up}$ represents
$f^{k}$ on $[a,b]$, $c$ becomes a local minimum for $f\circ f^{k}$, and
$f^{k+1}$ is a high valley $\mathsf{Uv}$ on $[a,b]$.

     * •

Up valley: Because $f$ strictly decreases for $x>\frac{1}{2}$ and because
$f^{k}([a,b])\subseteq(\frac{1}{2},x_{\max}]$ if $\mathsf{Uv}$ represents
$f^{k}$ on $[a,b]$, $c$ becomes a local maximum for $f\circ f^{k}$, and
$f^{k+1}$ is a high peak $\mathsf{Up}$ on $[a,b]$.

Now, consider the inductive hypothesis. Because $f^{k}$ can be represented by
$\mathsf{Ic}(\mathsf{Up}\mathsf{Uv})^{k-1}\mathsf{Up}\mathsf{Dc}$, applying
the above transformations to each piece implies that $f^{k+1}$ can be
represented by
$\mathsf{Ic}(\mathsf{Up}\mathsf{Uv})^{k}\mathsf{Up}\mathsf{Dc}$. Hence, the
inductive argument goes through.

####  D.3.2 General Case Proof

The argument proceeds inductively. We show that if we have some
$f\in\mathcal{F}_{q,k}$, then we can find some other function
$h\in\mathcal{F}_{q-1,1-k}$ and characterize the behavior of $f$ in terms of
the behavior of $h$.

Since we assume that $q\geq 1$, there will always exist some
$x^{*}>\frac{1}{2}$ that is a fixed point of $f$.121212Sharkovsky’s Theorem
yields this by showing that the existence of a $2^{q}$-cycle implies the
existence of any $2^{j}$-cycle, for all $j\in\\{0,\dots,q-1\\}$.
$x^{*}>\frac{1}{2}$ by our assumption that a 2-cycle $x_{1}<x_{2}$ exists. It
must be true that $x_{2}>\frac{1}{2}$; otherwise, $f(x_{2})>x_{2}>x_{1}$,
which breaks the cycle. Because $f(\frac{1}{2})>\frac{1}{2}$ and
$f(x_{2})<x_{2}$, there exists $x^{*}\in(\frac{1}{2},x_{2})$ such that
$f(x^{*})=x^{*}$ by the Intermediate Value Theorem. By symmetry,
$f(1-x^{*})=x^{*}$. Let $\phi:[0,1]\to[1-x^{*},x^{*}]$ be a decreasing
isomorphism with $\phi(x)=x^{*}-x(2x^{*}-1)$, and let

$h=\phi^{-1}\circ f^{2}\circ\phi.$

$h$ is a useful construct, because its behavior resembles simpler versions of
$f$, with fewer cycles and oscillations. We use properties of $h$ to relate
pieces of $f^{k}$ to those of $h^{k/2}$. We illustrate this recursive and
fractal-like behavior in Figure 16.

Note that $h^{k}=\phi^{-1}\circ f^{2k}\circ\phi$.

Figure 16: Visualizes the analogy between mappings in $\mathcal{F}_{q,z}$ and
$\mathcal{F}_{q-1,1-z}$. The left plots the first 4 iterates of
$f=f_{\text{log},0.9}\in\mathcal{F}_{4,1}$ (has a maximal 4-cycle with
$f^{4}(\frac{1}{2})>\frac{1}{2}$), while the right plots those of
$f=f_{\text{log},0.85}\in\mathcal{F}_{2,0}$ (has a maximal 2-cycle with
$f^{2}(\frac{1}{2})<\frac{1}{2}$. The purple highlighted regions on the left
behave qualitatively similar to $f_{\text{log},0.85}$, while the green regions
are similar to $f_{\text{log},0.85}^{2}$.

######  Lemma 5.

$h$ is a symmetric unimodal mapping with $h\in\mathcal{F}_{q-1,1-z}$.

###### Proof.

We verify the conditions for $f$ to be unimodal mapping.

  1. 1.

$h$ is continuous and piece-wise differentiable on $[0,1]$ because $f^{2}$ is,
and $h$ is merely a linear transformation of $f^{2}$.

  2. 2.

$h(0)=h(1)=0$. $h((0,1))$ is strictly positive because
$f((1-x^{*},x^{*}))=(x^{*},x_{\max})$,
$f^{2}((1-x^{*},x^{*}))=(f(x_{\max}),x^{*})$, and $f(x_{\max})<f(x^{*})=x^{*}$
by $f$ being decreasing on $[\frac{1}{2},1]$.

  3. 3.

$h$ is uniquely maximized by $\frac{1}{2}$ because $\frac{1}{2}$ minimizes
$f^{2}$ on the interval $[1-x^{*},x^{*}]$. $f$ maps both
$[1-x^{*},\frac{1}{2}]$ and $[\frac{1}{2},x^{*}]$ onto $[x^{*},x_{\max}]$ and
is increasing and decreasing on the respective intervals. Because $f$ maps
$[x^{*},x_{\max}]$ onto $[f(x_{\max}),x^{*}]$ and $f(x_{\max})<x^{*}$ and is
decreasing on $[x^{*},x_{\max}]$, $f^{2}$ is increasing on
$[1-x^{*},\frac{1}{2}]$ and decreasing on $[\frac{1}{2},x^{*}]$.

Thus, $h$ is maximized by $\frac{1}{2}$, increases before $\frac{1}{2}$, and
decreases after $\frac{1}{2}$.

  4. 4.

We must also show that $h$ is well-defined, which entails proving that
$h(x)\leq 1$ for all $x\in[0,1]$. Suppose that were not the case. Then,
$h(\frac{1}{2})>1$, and there exists some $x^{\prime}\leq\frac{1}{2}$ with
$h(x^{\prime})=1$. There also exists some $x^{**}\in[1-x^{\prime},1]$ with
$h(x^{**})=x^{**}$ by the Intermediate Value Theorem.

Let $g(x)=h^{3}(x)-x$ and note that $g$ is continuous on $[0,x^{\prime}]$.
Observe that $g(1-x^{**})=2x^{**}-1>0$ and $g(x^{\prime})=-x^{\prime}<0$.
Thus, there exists $x^{\prime\prime}\in[1-x^{**},x^{\prime}]$ with
$g(x^{\prime\prime})=0$. Because $h$ is increasing on $[0,x^{\prime}]$ and
$x^{\prime}>1-x^{**}$, it must be the case that
$h(x^{\prime})>x^{**}>x^{\prime}$. Thus, $x^{**}$ is not a fixed point and
must be on a 3-cycle in $h$.

However, if $x^{**}$ is on a 3-cycle in $h$, then $\phi(x^{**})$ must be part
of a 6-cycle in $f$. This contradicts the assumption that $f$ cannot have a
$2^{q+1}$-cycle, because Sharkovsky’s Theorem states that a 6-cycle implies a
$2^{q+1}$-cycle.

We show that $h$ is symmetric.

$\displaystyle h(x)$
$\displaystyle=\phi^{-1}(f^{2}(\phi(x)))=\phi^{-1}(f^{2}(1-\phi(x)))=\phi^{-1}(f^{2}(1-x^{*}+x(2x^{*}-1)))$
$\displaystyle=\phi^{-1}(f^{2}(x^{*}-(1-x)(2x^{*}-1)))=\phi^{-1}(f^{2}(\phi(1-x)))=h(1-x).$

If $f^{2^{q}}(\frac{1}{2})\geq\frac{1}{2}$, then
$h^{2^{q-1}}(\frac{1}{2})\leq\frac{1}{2}$, and if
$f^{2^{q}}(\frac{1}{2})\leq\frac{1}{2}$, then
$h^{2^{q-1}}(\frac{1}{2})\geq\frac{1}{2}$. Thus,
$[[h^{2^{q-1}}(\frac{1}{2})]]_{1/2}=[[f^{2^{q}}(\frac{1}{2})]]_{1/2}$. By
Lemma 6, $h$ has a $2^{q-1}$-cycle and does not have a $2^{q}$-cycle. Thus,
$h\in\mathcal{F}_{q-1,1-z}$. ∎

######  Lemma 6.

For $p\in\mathbb{Z}_{+}$, $h$ has a $p$-cycle if and only if $f$ has a
$2p$-cycle.

###### Proof.

Suppose $x_{1},\dots,x_{p}$ is a $p$-cycle for $h$. Then,
$\phi(x_{1}),\dots,\phi(x_{p})$ is a $p$-cycle for $f^{2}$. If
$x_{1},\dots,x_{p}$ are distinct, then so must be
$\phi(x_{1}),\dots,\phi(x_{p})$, since $\phi$ is an isomorphism. Thus,

$\phi(x_{1}),f(\phi(x_{1})),\dots,\phi(x_{p}),f(\phi(x_{p}))$

is a $2p$-cycle for $f$.

Conversely, if $x_{1},\dots,x_{2p}$ is a $2p$-cycle for $f$, then
$x_{1},x_{3},\dots,x_{2p-1}$ is a $p$-cycle for $f^{2}$ and

$\phi^{-1}(x_{1}),\dots,\phi^{-1}(x_{2p})$

is a $p$-cycle for $h$. ∎

We proceed with a proof similar in structure to the one in the last section,
where we divide each $f^{k}$ into intervals and monitor the evolution of each
as $k$ increases. We define the classes of the pieces of some 1-dimensional
map $f^{k}$ on interval $[a,b]$ below. We visualize these classes in Figure
17.

  * •

$f^{k}$ is an approach $\mathsf{A}$ on $[a,b]$ if $f$ is strictly increasing,
$f^{k}(a)=0$, and $f^{k}(b)=1-x^{*}$.

  * •

Similarly, $f^{k}$ is a departure $\mathsf{D}$ on $[a,b]$ if $f^{k}$ is
strictly decreasing, $f^{k}(a)=1-x^{*}$, and $f^{k}(b)=0$.

  * •

$f^{k}$ is an $i$-Left Valley $\mathsf{Lv}_{i}$ on $[a,b]$ if
$f^{k}:[a,b]\rightarrow[f(x_{\max}),x^{*}]$ and if there exists some strictly
increasing and bijective $\sigma:[a,b]\rightarrow[1-x^{*},x^{*}]$ such that
$f^{k}=\phi\circ h^{i}\circ\phi^{-1}\circ\sigma$ on $[a,b]$. Note that
$f^{k}(a)=f^{k}(b)=x^{*}$—unless $i=0$, in which case $f^{k}(a)=1-x^{*}$ and
$f_{r}^{k}(b)=x^{*}$.

  * •

$f^{k}$ is analogously a $i$-Right Valley $\mathsf{Rv}_{i}$ if the same
condition holds, except that $\sigma$ is strictly decreasing.

  * •

$f^{k}$ is an $i$-Left Peak $\mathsf{Lp}_{i}$ on $[a,b]$ if $f^{k-1}$ is
$\mathsf{Lv}_{i-1}$ on $[a,b]$. It follows that
$f^{k}:[a,b]\rightarrow[x^{*},x_{\max}]$, that there exists some $c\in[a,b]$
such that $f^{k}(c)=x_{\max}$ (because $\frac{1}{2}\in[f(x_{\max}),x^{*}]$),
and that $f^{k}(a)=f^{k}(b)=x^{*}$.

  * •

$f^{k}$ is an $i$-Right Peak $\mathsf{Rp}_{i}$ on $[a,b]$ if $f^{k-1}$ is
$\mathsf{Rv}_{i-1}$ on $[a,b]$. The same claims hold as $\mathsf{Lp}_{i}$.

Figure 17: Similar to Figure 15, visualizes the classifications of
$f,f^{2},f^{3},f^{4}$ for $f=f_{\text{log},0.9}\in\mathcal{F}_{4,1}$, and
demonstrates that the decompositions are
$\mathsf{A}\mathsf{Lv}_{0}\mathsf{Lp}_{0}\mathsf{Rv}_{0}\mathsf{D}$,
$\mathsf{A}\mathsf{Lv}_{0}\mathsf{Lp}_{1}\mathsf{Lv}_{1}\mathsf{Rp}_{1}\mathsf{Rv}_{0}\mathsf{D}$,
$\mathsf{A}\mathsf{Lv}_{0}\mathsf{Lp}_{1}\mathsf{Lv}_{1}\mathsf{Lp}_{2}\mathsf{Rv}_{1}\mathsf{Rp}_{1}\mathsf{Rv}_{0}\mathsf{D}$,
and
$\mathsf{A}\mathsf{Lv}_{0}\mathsf{Lp}_{1}\mathsf{Lv}_{1}\mathsf{Lp}_{2}\mathsf{Lv}_{2}\mathsf{Rp}_{2}\mathsf{Rv}_{1}\mathsf{Rp}_{1}\mathsf{Rv}_{0}\mathsf{D}$
respectively.

Now, the proof of the number of oscillations proceeds in two steps. (1) We
analyze how each of the above pieces evolves with each application of $f$. (2)
We show how many maxima and minima each translates to.

######  Lemma 7.

When $f\in\mathcal{F}_{q,z}$ for $q\geq 1$ and for all $k\in\mathbb{Z}_{+}$,
$f^{k}$ can be decomposed into $2k+3$ pieces $\eta_{1},\dots,\eta_{2k+3}$ such
that

$\text{$\eta_{i}$ is }\begin{cases}\text{$\mathsf{A}$ if $i=1$}\\\
\text{$\mathsf{Lv}_{j}$ if $i=2j+2$ for $j\in\\{0,1,\dots,\left\lfloor
k/2\right\rfloor\\}$}\\\ \text{$\mathsf{Lp}_{j}$ if $i=2j+1$ for
$j\in\\{1,\dots,\left\lfloor(k+1)/2\right\rfloor\\}$}\\\
\text{$\mathsf{Rv}_{j}$ if $i=2k-2j+2$ for
$j\in\\{0,1,\dots,\left\lfloor(k-1)/2\right\rfloor\\}$}\\\
\text{$\mathsf{Rp}_{j}$ if $i=2k-2j+3$ for $j\in\\{1,\dots,\left\lfloor
k/2\right\rfloor\\}$}\\\ \text{$\mathsf{D}$ if $i=2k+3$}\\\ \end{cases}$

That is, if $k$ is even, then $f$ can be represented by

$\mathsf{A}\mathsf{Lv}_{0}\mathsf{Lp}_{1}\mathsf{Lv}_{1}\dots\mathsf{Lv}_{k/2-1}\mathsf{Lp}_{k/2}\mathsf{Lv}_{k/2}\mathsf{Rp}_{k/2}\mathsf{Rv}_{k/2-1}\dots\mathsf{Rv}_{1}\mathsf{Rp}_{2}\mathsf{Rv}_{0}\mathsf{D}.$

If $k$ is odd, then $f$ is represented by

$\mathsf{A}\mathsf{Lv}_{0}\mathsf{Lp}_{1}\mathsf{Lv}_{1}\dots\mathsf{Lp}_{(k-1)/2}\mathsf{Lv}_{(k-1)/2}\mathsf{Lp}_{(k+1)/2}\mathsf{Rv}_{(k-1)/2}\mathsf{Rp}_{(k-1)/2}\dots\mathsf{Rv}_{1}\mathsf{Rp}_{2}\mathsf{Rv}_{0}\mathsf{D}.$

###### Proof.

This lemma is proved inductively. $f$ can be decomposed into the pieces
$\mathsf{A}\mathsf{Lv}_{0}\mathsf{Lp}_{1}\mathsf{Rv}_{0}\mathsf{D}$.

  * •

By unimodality and symmetry, $f$ is strictly increasing on $[0,\frac{1}{2})$
and strictly decreasing on $(\frac{1}{2},1]$. There exists some $x_{1}$ such
that $[0,x_{1}]$ is strictly increasing and $f(x_{1})=1-x^{*}$ (because
$1-x^{*}<x^{*}<x_{\max}$). Thus, $f$ is $\mathsf{A}$ on $[0,x_{1}]$.
Similarly, $[1-x_{1},1]$ is strictly decreasing and $f(1-x_{1})=1-x^{*}$,
which implies that $f$ is $\mathsf{D}$ on $[1-x_{1},1]$.

  * •

Note that $x_{1}<1-x^{*}<x^{*}<1-x_{1}$, and $f$ is increasing on
$[x_{1},1-x^{*}]$ and decreasing on $[x^{*},1-x_{1}]$.

Because $[x_{1},1-x^{*}]$ is monotone, there exists continuous and increasing
$\sigma:[x_{1},1-x^{*}]\rightarrow[1-x^{*},x^{*}]$ such that $f(x)=\sigma(x)$.
Since $h^{0}$ is the identity map, it trivially also holds that
$f(x)=\phi(h^{0}(\phi^{-1}(\sigma(x))))$. Because $f(x_{1})=1-x^{*}$ and
$f(x^{*})=x^{*}$, it follows that $f$ is $\mathsf{Lv}_{0}$ on
$[x_{1},1-x^{*}]$.

By a similar argument, $f$ is $\mathsf{Rv}_{0}$ on $[x^{*},1-x_{1}]$, with the
only difference being that $\sigma$ needs to be strictly decreasing for it to
hold.

  * •

$[1-x^{*},x^{*}]$ is $\mathsf{Lp}_{1}$ because $[1-x^{*},x^{*}]$ is
$\mathsf{Lv}_{0}$ on the identity map $f^{0}$. This trivially holds using the
identity $\sigma$ map.

Now, we prove the inductive step, which can be summed up by the following
line:

$\mathsf{A}\rightarrow\mathsf{A}\mathsf{Lv}_{0};\mathsf{D}\rightarrow\mathsf{Rv}_{0}\mathsf{D};\mathsf{Lv}_{j}\rightarrow\mathsf{Lp}_{j+1};\mathsf{Lp}_{j}\rightarrow\mathsf{Lv}_{j};\mathsf{Rv}_{j}\rightarrow\mathsf{Rp}_{j+1};\mathsf{Rp}_{j}\rightarrow\mathsf{Rv}_{j}.$

We show each part of the relationship as follows:

  * •

If $f^{k}$ is $\mathsf{A}$ on $[0,b]$, then there exists some $c\in(0,b)$ such
that $f^{k+1}(c)=1-x^{*}$ because $f^{k}$ is an isomorphism between $[0,b]$
and $[0,x^{*}]$.

It follows that $f^{k+1}$ is $\mathsf{A}$ on $[0,c]$ because $f^{k+1}$ is
strictly increasing on the interval from $0$ to $1-x^{*}$.

$[c,b]$ is $\mathsf{Lv}_{0}$ because there must exist some increasing $\sigma$
such that $f^{k+1}(x)=\sigma(x)$ on that interval. Thus, it follows that
$f^{k+1}=\phi\circ h^{0}\circ\phi^{-1}\circ\sigma$ on $[0,b]$.

  * •

The same argument holds for $\mathsf{D}$. If $f^{k}$ is $\mathsf{D}$ on
$[a,1]$, then there exists $c\in(a,1)$ such that $[a,c]$ is $\mathsf{Rv}_{0}$
and $[c,1]$ is $\mathsf{D}$.

  * •

If $f^{k}$ is $\mathsf{Lv}_{j}$ on $[a,b]$, then $f^{k+1}$ is
$\mathsf{Lp}_{j+1}$ on the same interval by the definition of
$\mathsf{Lp}_{j+1}$.

  * •

Similarly, if $f^{k}$ is $\mathsf{Rv}_{j}$ on $[a,b]$, then $f^{k+1}$ is
$\mathsf{Rp}_{j+1}$ on the same interval by the definition of
$\mathsf{Rp}_{j+1}$.

  * •

If $f^{k}$ is $\mathsf{Lp}_{j}$ on $[a,b]$, then $f^{k-1}$ is
$\mathsf{Lv}_{j-1}$ and hence $f^{k-1}$ maps to $[f(x_{\max}),x^{*}]$ on the
interval. Therefore, there exists $\sigma$ such that $f^{k-1}=\phi\circ
h^{j-1}\circ\phi^{-1}\circ\sigma$ on the interval. We use the properties of
$h$ to show that $f^{k+1}$ is $\mathsf{Lv}_{j}$ on $[a,b]$. Note that
$f^{2}=\phi\circ h\circ\phi^{-1}$ on $[f(x_{\max}),x^{*}]$.

$\displaystyle f^{k+1}$ $\displaystyle=f^{2}\circ f^{k-1}=\phi\circ
h\circ\phi^{-1}\circ\phi\circ h^{j-1}\circ\phi^{-1}\circ\sigma=\phi\circ
h^{j}\circ\phi^{-1}\circ\sigma$

Thus, $f^{k+1}$ satisfies the condition to be $\mathsf{Lv}_{j}$.

  * •

By a identical argument, if $f^{k}$ is $\mathsf{Rp}_{j}$ on $[a,b]$, then
$f^{k+1}$ is $\mathsf{Rv}_{j}$.

The remainder of this argument follows by applying the above transition rules
for each piece to the inductive hypothesis about the ordering of pieces in
$f^{k}$ to obtain the ordering for $f^{k+1}$. ∎

Now, we determine how many local maxima and minima are contained in each type
of piece. Let $\mathrm{maxima}(f)$ and $\mathrm{minima}(f)$ represent the
number of local maxima and minima respectively on mapping $f$ on interval
$[0,1]$. We bound the total number of monotone pieces with these bounds by
using $M(f)=2\mathrm{maxima}(f)$. We similarly abuse notation to bound the
number of maxima and minima in a category with
$\mathrm{maxima}(\mathcal{F}_{q,z}^{k})$ and
$\mathrm{minima}(\mathcal{F}_{q,z}^{k})$, and in the interval $[a,b]$ with
$\mathrm{maxima}(f,a,b)$ and $\mathrm{minima}(f,a,b)$.

By the base case in the previous section
$\mathrm{maxima}(\mathcal{F}_{0,0}^{k})=1$,
$\mathrm{minima}(\mathcal{F}_{0,0}^{k})=2$,
$\mathrm{maxima}(\mathcal{F}_{0,1}^{k})=k,$ and
$\mathrm{minima}(\mathcal{F}_{0,1}^{k})=k+1$. We obtain recurrences to
represent $\mathrm{maxima}(\mathcal{F}_{q,z}^{k})$ and
$\mathrm{minima}(\mathcal{F}_{q,z}^{k})$.

For each part, we rely on the following facts: If $\sigma$ is a strictly
increasing bijection, then
$\mathrm{maxima}(f\circ\sigma,a,b)=\mathrm{maxima}(f,a,b)$. If $\sigma$ is
strictly decreasing, then
$\mathrm{minima}(f\circ\sigma,a,b)=\mathrm{maxima}(f,a,b)$. (The reverse are
true for minima of $f$.)

We analyze each type of piece individually, considering what happens when $f$
has some kind of piece on interval $[a,b]$.

  * •

Because $\mathsf{A}$ and $\mathsf{D}$ segments are strictly increasing or
decreasing, $\mathrm{maxima}(f,a,b)=0$ when $f$ has either piece on $[a,b]$.
$\mathrm{minima}(f,a,b)=1$ because segments that support $\mathsf{A}$ contain
$0$ and segments with $\mathsf{D}$ have $1$, each of which $f$ maps to 0.

  * •

Because each $\mathsf{Lv}_{i}$ segment of $f^{k}$ on $[a,b]$ can be
represented as $\phi\circ h^{i}\circ\phi^{-1}\circ\sigma$, and because $\phi$
is strictly decreasing,
$\mathrm{maxima}(f_{r}^{k},a,b)=\mathrm{minima}(h^{i})$ and
$\mathrm{minima}(f_{r}^{k},a,b)=\mathrm{maxima}(h^{i})$. By Lemma 5,
$h\in\mathcal{F}_{q-1,1-z}$,
$\mathrm{maxima}(f_{r}^{k},a,b)\leq\mathrm{minima}(\mathcal{F}_{q-1,1-z}^{i})$
and
$\mathrm{minima}(f_{r}^{k},a,b)\leq\mathrm{maxima}(\mathcal{F}_{q-1,1-z}^{i})$.

The same analysis holds for each $\mathsf{Rv}_{i}$ segment.

  * •

Consider an $\mathsf{Lp}_{i}$ segment of $f^{k}$ on $[a,b]$, which has output
spanning the interval $[x^{*},x_{\max}]$. Because $x^{*}>\frac{1}{2}$, $f$ is
strictly decreasing on the domain $[x^{*},x_{\max}]$. Thus, $f^{k+1}$ must
satisfy $\mathrm{maxima}(f_{r}^{k+1},a,b)=\mathrm{minima}(f_{r}^{k},a,b)$ and
$\mathrm{minima}(f_{r}^{k+1},a,b)=\mathrm{maxima}(f_{r}^{k},a,b)$.

Note by the definition of $\mathsf{Lp}_{i}$ that $[a,b]$ must also support an
$\mathsf{Lv}_{i-1}$ segment on $f^{k-1}$ and an $\mathsf{Lv}_{i}$ segment on
$f^{k+1}$. From the previous bullet, the $\mathsf{Lv}_{i}$ segment must have
at most $\mathrm{minima}(\mathcal{F}_{q-1,1-z}^{i})$ maxima and
$\mathrm{maxima}(\mathcal{F}_{q-1,1-z}^{i})$ minima. Because there must be a
one-to-one correspondence between minima of $f^{k+1}$ and maxima of $f^{k}$ on
the interval and vice versa, the $\mathsf{Lp}_{i}$ segment has
$\mathrm{maxima}(f_{r}^{k},a,b)\leq\mathrm{maxima}(\mathcal{F}_{q-1,1-z}^{i})$
and
$\mathrm{minima}(f_{r}^{k},a,b)\leq\mathrm{minima}(\mathcal{F}_{q-1,1-z}^{i})$.

The same analysis hold for each $\mathsf{Rp}_{i}$ segment.

Therefore, we can construct a recurrence relationship for the number of maxima
and minima for $f_{r}^{k}$ based on the sequences found in Lemma 7.

$\displaystyle\mathrm{maxima}(\mathcal{F}_{q,z}^{k})$
$\displaystyle\leq\underbrace{\sum_{i=0}^{\left\lfloor
k/2\right\rfloor}\mathrm{minima}(\mathcal{F}_{q-1,1-z}^{k})}_{\mathsf{Lv}_{i}}+\underbrace{\sum_{i=0}^{\left\lfloor(k-1)/2\right\rfloor}\mathrm{minima}(\mathcal{F}_{q-1,1-z}^{k})}_{\mathsf{Rv}_{i}}$
$\displaystyle\quad+\underbrace{\sum_{i=1}^{\left\lfloor(k+1)/2\right\rfloor}\mathrm{maxima}(\mathcal{F}_{q-1,1-z}^{k})}_{\mathsf{Lp}_{i}}+\underbrace{\sum_{i=1}^{\left\lfloor
k/2\right\rfloor}\mathrm{maxima}(\mathcal{F}_{q-1,1-z}^{k})}_{\mathsf{Rp}_{i}}$
$\displaystyle\mathrm{minima}(\mathcal{F}_{q,z}^{k})$
$\displaystyle=\underbrace{2}_{\mathsf{A}\&\mathsf{D}}+\underbrace{\sum_{i=0}^{\left\lfloor
k/2\right\rfloor}\mathrm{maxima}(\mathcal{F}_{q-1,1-z}^{k})}_{\mathsf{Lv}_{i}}+\underbrace{\sum_{i=0}^{\left\lfloor(k-1)/2\right\rfloor}\mathrm{maxima}(\mathcal{F}_{q-1,1-z}^{k})}_{\mathsf{Rv}_{i}}$
$\displaystyle\quad+\underbrace{\sum_{i=1}^{\left\lfloor(k+1)/2\right\rfloor}\mathrm{minima}(\mathcal{F}_{q-1,1-z}^{k})}_{\mathsf{Lp}_{i}}+\underbrace{\sum_{i=1}^{\left\lfloor
k/2\right\rfloor}\mathrm{minima}(\mathcal{F}_{q-1,1-z}^{k})}_{\mathsf{Rp}_{i}}$

We bound $\mathrm{maxima}(\mathcal{F}_{q,z}^{k})$ and
$\mathrm{minima}(\mathcal{F}_{q,z}^{k})$ by induction to prove Proposition 5.
We use the following inductive assumption over all $k$, $q$, and $z$, which
suffices to prove the claim:

$\mathrm{maxima}(\mathcal{F}_{q,z}^{k}),\mathrm{minima}(\mathcal{F}_{q,z}^{k})\leq\begin{cases}(4q)^{k}&\text{$q$
is even, $z=0$, or $q$ is odd, $z=1$}\\\ (4q)^{k+1}&\text{$q$ is even, $z=1$,
or $q$ is odd, $z=0$}.\end{cases}$

By the previous section, the claim holds for $q=0$ and all $k$ and $z$, which
gives the base case.

Moving forward, we assume that the claim holds for all values of $q^{\prime}$
with $q^{\prime}\leq q$ and any $k$ and $z$. We prove that it holds for $q+1$
with any choices of $k$ and $z$.

We show that the bound holds for $\mathrm{minima}(\mathcal{F}_{q+1,z}^{k})$
when $q+1$ is even and $z=1$, or $q+1$ is odd and $z=0$. The other cases are
nearly identical. Since the bounds are trivial for $k=1$, we prove them below
for $k\geq 2$.

$\displaystyle\mathrm{minima}(\mathcal{F}_{q+1,z}^{k})$ $\displaystyle\leq
2+\sum_{i=0}^{\left\lfloor
k/2\right\rfloor}(4i)^{q+1}+\sum_{i=0}^{\left\lfloor(k-1)/2\right\rfloor}(4i)^{q+1}+\sum_{i=0}^{\left\lfloor(k+1)/2\right\rfloor}(4i)^{q+1}+\sum_{i=0}^{\left\lfloor
k/2\right\rfloor}(4i)^{q+1}$ $\displaystyle\leq
4\cdot\frac{k}{2}\cdot(2k)^{q+1}+(2(k+1))^{q+1}\leq(2k)^{q+2}+(3k)^{q+1}\leq(4k)^{q+2}.$

###  D.4 Proof of Theorem 8, Claim 2

We restate the claim:

######  Proposition 6 (Claim 2 of Theorem 8).

Suppose $f$ is a symmetric unimodal mapping whose maximal cycle is of length
$p=2^{q}$. For any $k\in\mathbb{N}$, there exists $g\in\mathcal{N}(u,2)$ with