We present several new techniques for evolving code
through sequences of mutations.
Among these are
(1) a method of local scoring
assigning a score to each expression in a program,
allowing us to more precisely identify buggy code,
(2) -expressions
which act as an intermediate step to
evolving -conditionals, and
(3) cyclic evolution
in which we evolve programs through phases of expansion and reduction.
To demonstrate their merits,
we provide a basic proof-of-concept implementation
which we show evolves correct code for several functions
manipulating integers and lists,
including some that are intractable
by means of existing Genetic Programming techniques.

§ INTRODUCTION

From Darwinian evolution, a process of local optimization,
emerged highly complex organisms.
An organism is, in a sense, a program encoded by DNA
determining physical actions based on observed data.
It is therefore natural to ask
whether it would also be possible to evolve through natural selection
computer code that solves a given problem.
This is the task at the heart of Genetic Programming.

This paper is aimed at describing a hill-climbing algorithm for
evolving a programs,
taking an approach that is quite different
from established Genetic Programming methods.
As a starting point,
let us consider an extremely simple hill-climbing algorithm
for evolving programs for a programming language $\mathscr L$.
For that algorithm,
we will need

* an initial program $P_0 \in \mathscr L$,[
For example, this could be a randomly generated program
or a program that we are trying to debug.

* a scoring function $S : \mathscr L \to [0, 1]$
assessing how well a program is performing at solving a given task
with $1$ meaning perfect,[
$S$ will typically work by
running the program on a pre-defined list of inputs and
then comparing the actual outputs to the desired outputs,
assigning a score based on how many of these cases are correct.
] and

* for each program $P \in \mathscr L$,
a probability distribution $M(P)$ on $\mathscr L$
of mutations of $P$.

The (non-deterministic) algorithm produces
a sequence of programs $P_0, P_1, \ldots \in \mathscr L$
where $P_0$ is the initial program and for $k \geq 1$

\[
P_k \defeq
\begin{cases}
& \text{if $S(P_k') > S(P_{k - 1})$;} \\
P_{k - 1},
& \text{otherwise.}
\end{cases}
\]

where $P_k'$ is randomly sampled from $M(P_{k - 1})$.
The algorithm terminates with solution $P_k$ when $S(P_k) = 1$,
which may or may not happen eventually.

A good choice of the distribution $M(P)$ should minimize
the expected score loss
L(P) \defeq S(P) - \mathbb E[S(M(P))].
In particular, likely mutations should ideally
only affect the program behavior slightly.
However, small changes in code often have major effect on the behavior of the program,
so typically $L > 0$.

The objective of this paper is to describe
ways to improve and refine this primitive idea to make it feasible:

* In <ref>,
we shall see how assign a score to each expression in a program
as opposed to the entire program at once.
In this way,
we get a more precise understanding of which parts of a program are buggy.
Later, these local scores are leveraged to choose mutations so that
the expressions that are the most buggy are
the most likely to be mutated.

* In <ref>,
we introduce $\ysuppose$-expressions.
These are expressions that are waiting to be promoted into $\yif$-conditionals.
This two-stage process gives an efficient and precise way
to evolve conditions for $\yif$-conditionals.

* In <ref>,
we discuss greedy criteria
for when a mutation should be regarded successful.
Specifically, we will mutate one expression at a time,
and the mutation is regarded successful
if the score of the new expression is
strictly greater than the score of the old expression.

* In <ref>,
we describe an evolutionary process which consists of cycles.
Each cycle is divided into four stages:
stretching, mutation, rewinding, and compression.
This design allows us to probe new program structures
while avoiding endless program expansion.

* In <ref>,
we present a basic proof-of-concept implementation of these ideas and
show that it is able to generate correct code for several small problems.
On one well-known problem, the even-parity problem,
we also compare our implementation to some found in the literature
and find that our methods outperforms the best of the considered implementations
by more than an order of magnitude.

* In <ref>,
we discuss future theoretical and practical directions,
including integration with Deep Learning techniques.

§.§ Functional Programming as a setting for Genetic Programming

This paper is focused on functional programs,
although some of its techniques are applicable to other paradigms as well.
The lack of side effects lends itself to Genetic Programming
as it means that changing a part of the code has
a more predictable effect on the program behavior:
we need not worry about how a state change could affect
the behavior of expressions elsewhere in the program.

§ LOCAL SCORING

When evolving programs,
we need to be able to quantify how well a program is performing.
As we discussed in the introduction,
one could do that by assigning the program a score
based on how well it adheres to its test cases.
However, with such an approach to scoring,
if a test case fails,
we gain little insight into what parts of the code could be the root cause of the failure.
If we were able to trace back such failure to specific parts of the code,
we could focus on mutating those parts.

In this section, we explain a simple method for assigning each expression a score.
We assume that every type is an Algebraic Data Type
so that values can be viewed as trees;
each node corresponds to a value constructor
and its children correspond to its arguments.
Then, the idea is to augment each node in the value tree with a trace,
which is a list of expressions that could affect the value at that node.
To state this method precisely,
we formally describe a small programming language
implementing this idea.

§.§ A programming language with traced values

As the setting for this paper,
we consider a simplistic, functional programming language
whose values are traced.
We first describe its syntax:

\begin{align*}
\Coloneqq\ & g_1 \mid g_2 \mid \cdots
\text{function}
\\
\Coloneqq\ & \xtrue \mid \xfalse \mid d_1 \mid d_2 \mid \cdots
\text{value constructor}
\\
\Coloneqq\ & y_1 \mid y_2 \mid \cdots
\text{variable}
\\
\Coloneqq\ & 1 \mid 2 \mid \cdots
\text{expression tag}
\\
\Coloneqq\ &
x \mid
c(e, \ldots, e) \mid
f(e, \ldots, e)
\\
\mid\ &
\xcase e \xof
c(x, \ldots, x) \to e;
\cdots;
c(x, \ldots, x) \to e
\xend
\\
\mid\ &
\xif e \xthen
\xelse
\xend
\\
\mid\ &
\xsuppose e \xthen
\xend
\\
\Coloneqq\ &
\text{tagged expression}
\\
\Coloneqq\ &
f(x, \ldots, x) = e
\text{function definition}
\\
\Coloneqq\ &
D \mid D; P
\text{program}
\end{align*}

We moreover stipulate that

* in a program $P$,
each function $g_i$ may be declared at most once,

* in a program $P$,
each participating expression has a unique tag,
that is,
among all the bodies of functions and all their subexpressions,
each tag $i$ appears at most once,

* cases in a $\ycase$-expression should be disjoint,
that is,
the constructors appearing on the left-hand side of the arms
should be pairwise distinct,

* a variable can be bound at most once in each case of a $\ycase$-expression,
that is,
the left-hand side of the arm takes the form $c(x_1, \ldots, x_n)$
where $x_1, \ldots, x_n$ are pairwise distinct variables, and

* variables bound by a case of a $\ycase$-expression cannot
overshadow variables that are already bound.

We now describe the typing rules.
We use a simple nominal type system with types

\[
\tau \Coloneqq \xbool \mid \tau_1 \mid \tau_2 \mid \cdots.
\]

A typing context $\Gamma$ is a collection of judgments of the forms

* a variable typing:
$x : \tau$,

* a function signature:
$f : (\tau, \ldots, \tau) \to \tau$, or

* a type definition:
$\tau \Coloneqq c(\tau, \ldots, \tau) \mid \cdots \mid c(\tau, \ldots, \tau)$.

The typing rules are

\[
\inferrule[TrueType]
{\Gamma \vdash \xtrue^{(t)} : \xbool}
\qquad
\inferrule[FalseType]
{\Gamma \vdash \xfalse^{(t)} : \xbool}
\quad
\inferrule[VarType]
{x : a \in \Gamma}
{\Gamma \vdash x^{(t)} : a}
\]

\[
\inferrule[FunctionType]
\Gamma \vdash e_1 : a_1, \ldots, e_n : a_n
\\
f : (a_1, \ldots, a_n) \to b \in \Gamma
{\Gamma \vdash f(e_1, \ldots, e_n)^{(t)} : b}
\]

\[
\inferrule[ConstructorType]
\Gamma \vdash e_1 : a_1, \ldots, e_n : a_n
\\
a \Coloneqq \cdots \mid c(a_1, \ldots, a_n) \mid \cdots \in \Gamma
{\Gamma \vdash c(e_1, \ldots, e_n)^{(t)} : a}
\]

\[
\inferrule[CaseType]
a \Coloneqq
c_1(a_{1, 1}, \ldots, a_{1, n_1})
\mid
\cdots
\mid
c_m(a_{m, 1}, \ldots, a_{m, n_m})
\in \Gamma
\\
\Gamma \vdash
d : a
\\
\Gamma, \forall j. x_{1, j} : a_{1, j} \vdash e_1 : b
\\
\cdots
\\
\Gamma, \forall j. x_{m, j} : a_{m, j} \vdash e_m : b
\Gamma
\vdash
\xcase d \xof
c_1(x_{1, 1}, \ldots, x_{1, n_1}) \to e_1;
\cdots;
c_m(x_{m, 1}, \ldots, x_{m, n_m}) \to e_n
\xend^{(t)}
: b
\]

\[
\inferrule[IfType]
{\Gamma \vdash e_1 : a, e_2 : a, c : \xbool}
\Gamma \vdash
\xif c \xthen
\xelse
\xend^{(t)}
: a
\qquad
\inferrule[SupposeType]
{\Gamma \vdash e : a, c : \xbool}
\Gamma \vdash
\xsuppose c \xthen
\xend^{(t)}
: a
\]

We shall often write just $P$ when we mean
a well-typed program $(P, \Gamma)$,
letting the typing context $\Gamma$ containing all the
type definitions and
function signatures
be implicit.

At last, we explain the semantics of our programming language.
The values of the programming language are

\[
v \Coloneqq c^{[\pm t, \ldots, \pm t]}(v, \ldots, v)
\]

where $\pm \Coloneqq + \mid -$.
Conceptually, each value constructor is tagged with a trace,
a list of expressions that could affect the value.
Its trace need not contain the traces of the arguments $(v, \ldots, v)$
whose traces in turn consist of expressions
that could affect the arguments but not the parent value constructor.
A sign $\pm$ should be thought of as measuring the influence of an expression:
$+$ means that if the value is bad then the expression should be punished, and
$-$ means that if the value is bad then the expression should be rewarded.
The relevance of $-$ will be revealed in <ref>.

An evaluation context $\sigma$ is a collection of bindings of the form

\[
B \Coloneqq x = v \mid f(x, \ldots, x) = e
\]

such that each variable $x$ and each function $f$
appears at most once in the left-hand sides.
For a program $P$,
one extracts an evaluation context $\sigma(P)$ by collecting all its function definitions.

We use the notation $\sigma \vdash e \downarrow v$ to denote that
an expression $e$
evaluates to a value $v$
in the evaluation context $\sigma$.
Furthermore, we make use of the notation

\[
\(c^{[t_{k + 1}, \ldots, t_n]}(v_1, \ldots, v_k)\)^{[t_0, \ldots, t_k,]}
\defeq
c^{[t_0, t_1, \ldots, t_n]}(v_1, \ldots, v_k)
\]

where $t_i$ are signed tags.
We shall sometimes elide the $+$ in $+ t$ for notational convenience.
The rules for evaluation are as follows.

\[
\inferrule[Var]
{\sigma, x = v \vdash x^{(t)} \downarrow v^{[t,]}}
\qquad
\inferrule[Cons]
{\sigma \vdash e_1 \downarrow v_1, \ldots, e_n \downarrow v_n}
{\sigma \vdash c(e_1, \ldots, e_n)^{(t)} \downarrow c^{[t]}(v_1, \ldots, v_n)}
\]

\[
\inferrule[Call]
\sigma \vdash e_1 \downarrow v_1, \ldots, e_n \downarrow v_n
\\
x_1 = v_1, \ldots, x_n = v_n \vdash e \downarrow v
{\sigma, f(x_1, \ldots, x_n) = e \vdash f(e_1, \ldots, e_n)^{(t)} \downarrow v^{[t,]}}
\]

\[
\inferrule[Case]
\sigma \vdash d \downarrow c^{[t_1, \ldots, t_k]}(v_1, \ldots, v_n)
\\
\sigma, x_1 = v_1, \ldots, x_n = v_n \vdash e \downarrow v
\sigma \vdash
\xcase d \xof
\cdots;
c(x_1, \ldots, x_n) \to e;
\cdots
\xend^{(t_0)}
\downarrow v^{[t_0, t_1, \ldots, t_k,]}
\]

\[
\inferrule[IfTrue]
\sigma \vdash
c \downarrow \xtrue^{[t_1, \ldots, t_n]},
e_1 \downarrow v
\sigma \vdash
\xif c \xthen
\xelse
\xend^{(t_0)}
\downarrow v^{[t_0, t_1, \ldots, t_n,]}
\]

\[
\inferrule[IfFalse]
\sigma \vdash
c \downarrow \xfalse^{[t_1, \ldots, t_n]},
e_2 \downarrow v
\sigma \vdash
\xif c \xthen
\xelse
\xend^{(t_0)}
\downarrow v^{[t_0, t_1, \ldots, t_n,]}
\]

We postpone stating the semantics of $\ysuppose$-expressions to <ref>.

Note that whenever an expression is evaluated,
the value it produces is tagged with a unique identifier for that expression.
The rules are defined in such a way that
each value ends up carrying traces of expressions that could affect the value.

To illustrate, let us elaborate a bit on the Case rule.
The rule says that what a $\ycase$-expression
evaluates to may be affected by

* the $\ycase$-expression $t_0$ itself since, trivially,
replacing the entire $\ycase$-expression could change its value,

* those expressions $t_1, \ldots, t_n$ that
could affect the entirety, even the value constructor,
of the value attained by $d$ that we are casing on, and

* those expressions that could affect the value attained by
the body $e$ of the chosen arm.

The rules IfTrue and IfFalse are quite similar.[
The reason that we include $\yif$-conditionals
in spite of having $\ycase$-expressions
is that they simplify our discussion of $\ysuppose$-expressions
in <ref>.

§.§ Extracting local scores

We shall need to consider values with other kinds of tags.

\[
v^u \Coloneqq c^{u}(v^u, \ldots, v^u).
\]

Of particular use are
untagged values $v^{()}$,
traced values $v = v^{[\pm t, \ldots, \pm t]}$ (recall the definitions from <ref>), and
score-tagged values $v^{[0, 1]}$.

Fix a base typing context $\Gamma_{\f{types}}$
containing just the type definitions we shall use.
To assign scores to expressions in a program $(P, \Gamma)$
with $\Gamma_{\f{types}} \subseteq \Gamma$,
we will need a test criterion
consisting of the data

* a name and signature $f : (a_1, \ldots, a_n) \to b$ for the function we are testing,
where $a_1, \ldots, a_n, b$ are types defined in $\Gamma_{\f{types}}$,

* untagged input values $(v_{1, k} : a_1, \ldots, v_{n, k} : a_n)$ for $k = 1, \ldots, N$, and

* for each $k = 1, \ldots, N$, an assessment function

\[
s_{(v_{1, k}, \ldots, v_{n, k})} :
\{w \in v^{()} \mid w : b\}
\to
\{w \in v^{[0, 1]} \mid w : b\}
\]

which takes a $b$-typed value
and sets the tag at each node to a score
(but does not change the underlying value)
such that all the tags in
s_{(v_{1, k}, \ldots, v_{n, k})}(w)
are $1$
if and only if $w$ is the desired result of $f(v_{1, k}, \ldots, v_{n, k})$.[
scores above $0.5$ ought to represent closer to right than to wrong and
scores below $0.5$ closer to wrong than to right.
(This will later become important for $\ysuppose$-expressions.)

We call the function specified in (1) the primary function.

For example,
suppose $P$ consisted of
just one function definition $\text{swap}(x, y) = \cdots$ and
$\Gamma$ consisted of
the type definition
$\xBoolTwo \Coloneqq \xPair(\xbool, \xbool)$ and
the function signature
$\text{swap} : \xBoolTwo \to \xBoolTwo$.
If we were to assess how well $\text{swap}$ swaps the booleans in the pair
like $(x, y) \mapsto (y, x)$,
the test criterion could consist of

the name and signature
\text{swap} : \xBoolTwo \to \xBoolTwo,

the inputs
$\xPair^{()}(\xtrue^{()}, \xtrue^{()})$,
$\xPair^{()}(\xfalse^{()}, \xtrue^{()})$,

$\xPair^{()}(\xtrue^{()}, \xfalse^{()})$,
$\xPair^{()}(\xfalse^{()}, \xfalse^{()})$, and

the assessment functions

\[
s_{\xPair(a_1^{()}, a_2^{()})} :
\xPair^{()}(b_1^{()}, b_2^{()})
\mapsto
\xPair^{(\delta(b_1, a_2) + \delta(b_2, a_1))/2}
(b_1^{\delta(b_1, a_2)}, b_2^{\delta(b_2, a_1)})
\]

where $\delta(x, y)$ is $1$ if $x = y$ and $0$ otherwise.

The assessment functions are defined in such a way
that the resulting tag to the $\xPair$ constructor measures
how close the value is to the desired value $\xPair(a_2^{()}, a_1^{()})$,
and the resulting tag to the boolean in each coordinate measures
how close the respective coordinate is to the desired value.
Notice how the assessment functions give perfect scores
when the behavior is as desired:

\[
s_{\xPair(a_1^{()}, a_2^{()})}(\xPair^{()}(a_2^{()}, a_1^{()}))
\xPair^{1}(a_2^{1}, a_1^{1}).
\]

Let us return to the general setup $(1)$-$(3)$
and explain how to compute a score for each expression in the program $P$.
We will assume that $f$ always terminates.[
This restriction can be dealt with
by imposing limits to the number of execution steps allowed
or by restricting what kinds of recursion are allowed.
The minutiae are dealt with in our proof-of-concept implementation;
see <ref>.
The process for obtaining expression-level scores is as follows.

* For each $k = 1, \ldots, N$,
evaluate the function call
f(\f{tr}(v_{1, k}), \ldots, \f{tr}(v_{n, k}))
and call its (traced) value $w_k$.
Here, $\f{tr}(v)$ is the traced value obtained from the untagged value $v$ by
setting each tag to the empty trace $[]$.

* For each $k = 1, \ldots, N$,
w_k' \defeq s_{(v_{1, k}, \ldots, v_{n, k})}(\f{untag}(w_k))
where $\f{untag}(w_k)$ is the untagged value obtained from the traced value $w_k$ by
replacing each tag with $()$.

* For each node in $w_k$, extract
the positively charged tags $+ t_1, \ldots, + t_p$ from its trace,
the negatively charged tags $- u_1, \ldots, - u_q$ from its trace, and
the tag $s \in [0, 1]$ of the corresponding node in $w_k'$;
then collect all the tuples
$(t_i, s)$ for $i = 1, \ldots, p$ and
$(u_i, 1 - s)$ for $i = 1, \ldots, q$
into a list $\ell$.

* An expression in $P$ with the tag $t$ is assigned the score,

\[
S_P(t) \defeq
\frac
{\sum_{(t, s) \in \ell} s}
{\sum_{(t, s) \in \ell} 1}
\]

averaging over all the scores in $\ell$ associated to the tag $t$.

Note how
a positively charged tag $+t$ in some trace in $w_k$ contribute to the average defining $S_P(t)$
with the score produced by
s_{(v_{1, k}, \ldots, v_{n, k})}
corresponding to the trace
whereas a negatively charged tag $- t$ contribute
with the inversion of that score.
The net effect is that
an expression with tag $t$ that appears in a trace positively charged
(resp. negatively charged)
is incentivized to maximize (resp. minimize) the score corresponding to that trace
if we are to maximize the score $S_P(t)$.

For the rest of the paper,
we shall fix a test criterion (with respect to the fixed $\Gamma_{\f{types}}$).
Moreover, from now on,
we will only consider programs $P$
that contain
the type definitions $\Gamma_{\f{types}}$ and
a function definition for the primary function (1).
In particular, for each such program $P$,
we get a scoring function $S_P$.
If $e$ is an expression in $P$ with expression tag $t$,
we write $S_P(e) \defeq S_P(t)$.
Also, when the context resolves ambiguity,
we shall omit the subscript $P$,
writing $S$ instead of $S_P$.

§ -EXPRESSIONS

Let us informally consider the problem of evolving code for
the minimum function
\f{min} : \Z \times \Z \to \Z.
We may assess a candidate implementation
based on some example arguments $A \subseteq \Z \times \Z$
ranging over small numbers.
Start with the initial program

\[
\tag{$P_0$}
\f{min}(n, m) = 0.
\]

This is not faring particularly well:
there are a few $(n, m) \in A$ with $0 = n \leq m$ or $0 = m \leq n$
but they make up an increasingly small fraction as $|A|$ grows.
If we try to mutate $P_0$ by replacing the body of $\f{min}(n, m)$
by various randomly chosen expressions and testing it on $A$,
it is not hard to find the improved program

\[
\tag{$P_1$}
\f{min}(n, m) = n,
\]

which performs a lot better:
it is correct whenever $n \leq m$
which is roughly $\frac12$ of the time.
However, at this point, we stagnate.
The next program we want is

\[
\tag{$P_2$}
\f{min}(n, m) = \xif n \leq m \xthen n \xelse m \xend,
\]

but this is quite a leap from $P_1$ and
would therefore take a long time
to discover through picking out random expressions.
More complex examples are even less tractable.
How do we overcome this problem of evolving $\yif$-conditionals?

$\ysuppose$-expressions allow us to separate
the problem of evolving the condition
from the problem of evolving the $\yelse$-branch.
In the above informal example,
small intermediate steps between $P_1$ and $P_2$ could be

\begin{align*}
&\f{min}(n, m) = n
\\
\becomes\ &
\f{min}(n, m) = \xsuppose \xtrue \xthen n \xend
\\
\becomes\ &
\f{min}(n, m) = \xsuppose n \leq m \xthen n \xend
\\
\becomes\ &
\f{min}(n, m) = \xif n \leq m \xthen n \xelse n \xend,
\\
\becomes\ &
\f{min}(n, m) = \xif n \leq m \xthen n \xelse m \xend,
\end{align*}

Conceptually, $\ysuppose$-expressions encourage the condition,
initially constant $\xtrue$,
to evolve to be $\xtrue$ whenever the body is correct and $\xfalse$ otherwise.
When the condition for the $\ysuppose$-expression is good enough,
we will promote the $\ysuppose$-expression into an $\yif$-conditional:

\[
\xsuppose c \xthen e \xend
\quad
\becomes
\quad
\xif c \xthen e \xelse e \xend.
\]

This evolutionary strategy is established in <ref>.

With this discussion in mind,
let us now state the semantics of $\ysuppose$-expressions.
We use the notation established in <ref>.
Define ${-}{-}t \defeq +t$.
The rules are then as follows.

\[
\inferrule[SupposeTrue]
\sigma \vdash
c \downarrow \xtrue^{[t_1, \ldots, t_n]},
e \downarrow v
\sigma \vdash
\xsuppose c \xthen
\xend^{(t_0)}
\downarrow v^{[t_0, t_1, \ldots, t_n,]}
\]

\[
\inferrule[SupposeFalse]
\sigma \vdash
c \downarrow \xfalse^{[t_1, \ldots, t_n]},
e \downarrow v
\sigma \vdash
\xsuppose c \xthen
\xend^{(t_0)}
\downarrow v^{[t_0, -t_1, \ldots, -t_n,]}
\]

Thus, if we disregard traces,
$\ysuppose$-expressions just evaluate their bodies.
However, if we follow the Local Scoring model set out in <ref>,
we see that if $c$ evaluates to $\mathbf{True}$,
the better $e$ performs,
the higher score is assigned to $c$,
whereas if $c$ evaluates to $\xfalse$,
the better $e$ performs,
the lower score is assigned to $c$.

We will need the following lemma in <ref>.

Let $P$ be a program.
Suppose $P$ contains an expression
\xsuppose \xtrue^{(t)} \xthen
\xend^{(u)}.
Then $S(t) = S(u)$.

Recall the algorithm specified in <ref>.
Note that the steps (a)-(c) are the same
no matter whether we are computing $S(t)$ or $S(u)$.
From the rule SupposeTrue,
we see that during step (a),
$+u$ (resp. $-u$) will always appear coupled with $+t$ (resp. $-t$) in traces.
It follows that
$\ell$ has exactly $m$ pairs $(t, s)$
if and only if it has exactly $m$ pairs $(u, s)$.

\[
\frac
{\sum_{(t, s) \in \ell} s}
{\sum_{(t, s) \in \ell} 1}
\frac
{\sum_{(u, s) \in \ell} s}
{\sum_{(u, s) \in \ell} 1}
\]

completing the proof.

§ SOME MUTATION PRINCIPLES

We discuss here some simple principles for how to mutate programs
by leveraging Local Scoring.
These will be used in combination with
the methods presented in <ref>.

§.§ Mutually exclusive mutation

Changing a single expression has a high chance of breaking the program,
but changing multiple expressions has an even higher chance of doing so.
It therefore makes sense to change just one expression
in each mutation step.

A simple scheme to mutate a program $P$ is to first pick a random expression.
The probability for picking a given expression $e$
should be proportional to $1 - S(e)$,
so that
we are more likely to mutate what is broken and
we never mutate what works perfectly.[
In particular, under this scheme, dead code is never mutated.
This expression is then replaced by a new, randomly generated expression of the same type
(with expression tags disjoint from the expression tags used in $P$),
giving a new program $P'$, the mutant of $P$.

§.§ Greedy Principle of Mutation

Suppose we use a hill-climbing algorithm
which has as state a program $P$
that it repeatedly tries to mutate
until it finds a good mutant, a successor,
which then replaces $P$,
repeating this process until the program solves some task perfectly.
How do we determine if a given mutant $P'$ should replace $P$ as its successor?

If we go purely by some kind of global score based on the behavior of the program,
as in <ref>,
we fail to evolve the conditions for $\ysuppose$-expressions
changing which has no exterior effect on the program behavior.
We therefore propose another criterion.
Recall that we mutate a program $P$ to a program $P'$
by replacing some expression $e$ with a new expression $e'$.
The Greedy Principle of Mutation stipulates
that $P'$ should be the successor to $P$ if and only if $S_{P'}(e') > S_P(e)$.
The principle is greedy since
the mutation can (and usually does) change the scores of
expressions that are not $e$ and
yet we only focus on how the score of $e$ changes.

Notice how the condition is
$S_{P'}(e') > S_P(e)$ as opposed to $S_{P'}(e') \geq S_P(e)$.
This is a deliberate choice.
It means that we prefer doing no mutation to mutating:
we only accept mutations that strictly improve the expression they change.
We shall refer to this property as mutation conservativity.

§ CYCLIC EVOLUTION

We have described $\ysuppose$-expressions
but we have yet to explain
how $\xsuppose$ should be introduced during evolution and
when these should be promoted into $\yif$-conditionals.
When mutating a program $P$,
we would like to sometimes replace an expression

\[
e \quad \becomes \quad \xsuppose \xtrue \xthen e \xend
\]

after which mutations can begin to improve $\xtrue$ to a more meaningful condition.
If we were to just follow the simplistic scheme set out in <ref>,
such replacement might happen
but the resulting program will never succeed the existing program
because the score of the replaced expression is the same as
the score of the original expression $e$.
One could circumvent this issue
by making an exception to mutation conservativity,
making this specific type of mutation always succeed.
This, however, is not a very good solution to the problem at hand:
the program would then grow unbounded
as we add more and more redundant $\ysuppose$-expressions.

What we propose instead is to divide the evolution into
phases of growth,
phases of mutation, and
phases of reduction;
similar to how a person
who is trying to gain muscle
might divide their eating into phases of bulking and phases of cutting.
Specifically, instead of proceeding one mutation at a time,
the basic unit of the algorithm will be a cycle
consisting of four phases:

* Stretching in which a program is
replaced by an equivalent, more redundant program
by introducing
redundant $\ysuppose$-expressions,
redundant $\yif$-conditionals,
redundant $\ycase$-expressions, and
redundant new functions.

* Mutation in which a number small changes are made to the program,
replacing the program
whenever a mutation satisfying the Greedy Principle of Mutation is found.

* Rewinding in which we try to undo the stretches done in (a).

* Compression in which we try to
rewrite the program to an equivalent, smaller form.

The algorithm we propose evolves programs by
repeatedly applying cycles until a program
performing perfectly (in accord with the test criterion) is found.

We describe basic ways to implement each phase.
We emphasize that each can be extended and refined in many ways,
some of which will be discussed in <ref>.

§.§ Stretching

The stretching phase makes the program more redundant,
setting the scene for the mutation phase
to turn that redundancy into useful structure.
The stretching phase consists of $N_\f{stretch}$ stretches
for some fixed constant $N_\f{stretch} > 0$.
Each stretch picks out a random expression in the program
with the probability of choosing an expression $e$
being proportional to $1 - S(e)$.
The stretched program $P'$ is constructed from $P$
by picking randomly among the following possibilities:

* replacing
$e \becomes \xsuppose \xtrue \xthen e \xend,$

* if $e = \xsuppose c \xthen e' \xend$ and $S(c) > S(e')$,
replacing $e \becomes \xif c \xthen e' \xelse e' \xend$,

* picking a variable $x : \tau$ bound in the context of $e$
and replacing

\begin{align*}
\becomes\
&\xcase x \xof
\\&
c_1(x_1, \ldots, x_{n_1})
\to
e[x/c_1(x_1, \ldots, x_{n_1})];
\\&
\cdots;
\\&
c_k(x_1, \ldots, x_{n_k})
\to
e[x/c_k(x_1, \ldots, x_{n_k})]
\\
\end{align*}

(a) $x_1, \ldots$ are variables that do not participate in $e$,
(b) $c_1, \ldots, c_k$ are the value constructors for $\tau$:

\[
\tau \Coloneqq
c_1(\cdots \text{($n_1$ arguments)})
\mid
\cdots
\mid
c_k(\cdots \text{($n_k$ arguments)}),
\]

and (c) $e[x/e']$ denotes $e$ with all occurrences of $x$ replaced by $e'$, or

* for
x_1 : a_1, \ldots, x_n : a_n
the variables bound in the context of $e : b$,
adding a new function

\begin{align*}
&f :
(b, a_1, \ldots, a_n)
\to
\\
&f(y, x_1, \ldots, x_n) = y
\end{align*}

and replacing
e \becomes f(e, x_1, \ldots, x_n).

In each case, the replacing expression
should be tagged with some tags disjoint from those used in $P$,
but we elide this for notational simplicity.

Let us elaborate on the condition
S(c) > S(e')
in stretch (2).
The justification for this condition comes from <ref>
which precludes stretch (2) from happening when $c = \xtrue$.
In this way,
when a stretch (1) introduces a $\ysuppose$-expression,
the condition must first improve
(which can happen in the mutation phase)
before a stretch (2) can promote it into an $\yif$-conditional.
As such, we don't end up immediately creating a lot of redundant $\yif$-conditionals.

§.§ Mutation

The mutation phase consists of $N_\f{mutate}$ mutations, successful or not,
where $N_\f{mutate} > 0$ is some fixed constant.
A mutation changes the program in the way described <ref>.
A mutation is considered successful if it satisfies
the Greedy Principle of Mutation (see <ref>)
in which case the mutant program replaces the program and the search continues.

§.§ Rewinding

The purpose of stretching was to create new program structures
that the mutation phase could make use of.
However, not all stretches create useful program structures.
If we return to our informal example of <ref> with evolving the $\min$ function,
we could have the stretch

\begin{align*}
&\min(n, m) = \xif n \leq m \xthen n \xelse n \xend
\\
\becomes\ &
\min(n, m) = \xif n \leq m \xthen n \xelse (\xsuppose \xtrue \xthen n \xend) \xend
\end{align*}

But that wouldn't be of much use
because in the $\yelse$-branch $n$ is never the right expression.
So, unless the second $n$ is mutated,
the condition for the $\ysuppose$-expression will just converge to $\xfalse$.
We must be able to deal effectively with such useless stretches
to stop the program that is being evolved from accumulating redundancy.

After the mutation phase has completed,
we propose to clean up the stretches
by rewinding them.
Specifically, for each stretching operation $s$,
we define a corresponding rewinding operation $\overline s$,
which is a transformation of programs that undoes
(is left-inverse to)
Then, if stretches
s_1, \ldots, s_{N_\f{stretch}}
were made in the stretching phase in that order,
the rewinding phase applies rewinding operations
\overline s_{N_\f{stretch}}, \ldots, \overline s_1
in that order
(notice the reversal of order).

For a stretch $s$ out of the $N_\f{stretch}$ stretches done in the stretching phase,
we will now describe its corresponding rewinding operation $\overline s$.
$\overline s$ depends on which type (1)-(4) of stretch $s$ is:

$(\overline 1)$
If $s$ is a stretch of type (1),
$\overline s$ is the following program transformation.
Let $e_1, \ldots, e_n$ be the $\ysuppose$-expressions
that originated from $s$.
$c_1, \ldots, c_n$ be their respective condition expressions and
$e_1', \ldots, e_n'$ their respective bodies.
For $i = 0, \ldots, n$,
replace $e_i \becomes e_i'$ if $S(c_i) \leq S(e_i)$.

$(\overline 2)$
If $s$ is a stretch of type (2),
$\overline s$ is the following program transformation.
Let $e_1, \ldots, e_n$ be the $\yif$-conditionals
that originated from $s$.
$c_1, \ldots, c_n$ be their respective condition expressions and
$e_1', \ldots, e_n'$ their respective $\xtrue$-branches.
For $i = 0, \ldots, n$,
replace $e_i \becomes \xsuppose c_i \xthen e_i' \xend$
if the latter expression attains a score in the program with this replacement made
at least the score $S(e_i)$.

$(\overline 3)$
If $s$ is a stretch of type (3),
$\overline s$ is the following program transformation.
Let $x$ be the variable chosen in $s$.
Let $e_1, \ldots, e_n$ be the expressions $\xcase x \xof \cdots$
that originated from $s$.
c_1(x_1, \ldots, x_{n_1}),
\ldots,
c_k(x_1, \ldots, x_{n_k})
be the cases that appear in each of those $\ycase$-expressions.
For $i = 1, \ldots, n$,
do the following.

* Look for a $1 \leq j \leq k$ such that
(i) $n_j > 0$,
(ii) the expression
e_{i, j}' \defeq
e_{i, j}[c_j(x_1, \ldots, x_{n_j})/x],
where $e_{i, j}$ is the body of the $\ycase$-expression $e_i$ to the case $c_j$,
does not reference the variables $x_1, \ldots, x_{n_j}$, and
(iii) after replacing $e_i$ with $e_{i, j}'$,
the new $e_{i, j}'$ attains a score at least the score $S(e_i)$.
If such a $j$ exists,
replace $e_i \becomes e_{i, j}'$ in the program.

* If not, look instead for a $1 \leq j \leq k$ such that
(i) $n_j = 0$ and
(ii) after replacing $e_i$ with $e_{i, j}$,
the new $e_{i, j}$ attains a score at least the score $S(e_i)$.
If such a $j$ exists,
replace $e_i \becomes e_{i, j}$ in the program.

* If such a $j$ could not be found either, do nothing.

$(\overline 4)$
If $s$ is a stretch of type (4),
$\overline s$ is the following program transformation.
Let $e_1, \ldots, e_n$ be the call-expressions
that originated from $s$.
Let $f$ be the name of the function they are calling.
Suppose its definition in the program is
f(x_1, \ldots, x_k) = e.
If $e$ contains a subexpression $f(\cdots)$, do nothing.
Otherwise, do the following.
For each $i = 1, \ldots, n$,
replace $e_i = f(a_1, \ldots, a_k) \becomes e[x_1/a_1]\cdots[x_k/a_k]$.
If after this transformation the expression $f(\cdots)$ appears nowhere in the program,
furthermore remove the function definition
f(x_1, \ldots, x_k) = e
from the program.

As before, we elide tags in notation,
implicitly tagging expressions with unique tags.
And again, $e[a/b]$ denotes the expression $e$ with all occurrences of $a$ replaced by $b$.

Note that in each of these rewinding operations,
we talk of possibly multiple expressions $e_1, \ldots, e_n$.
This is because an expression created by one stretch may be duplicated by another
(stretches of type (2) or (3)).
It is therefore necessary to track
what expressions originate in what stretches.
This can be done by tagging each expression by some extra bookkeeping data
of which we shall not deal with the details.

The condition $S(c_i) \leq S(e_i)$ in $(\overline 1)$
is again justified by <ref>.
In particular, the condition is only fulfilled
if the condition $c_i$ is at least as bad as the initial condition $\xtrue$.
In effect, we throw away a $\xsuppose$
if its condition didn't manage to improve at all during the mutation phase.

§.§ Compression

The final phase is compression,
replacing the program by an equivalent, shorter form.
There are indeed many ways to approach this problem of removing excess;
we present one which we found works reasonably well in practice.

As input for the algorithm,
we need to run the program on the examples in the test criterion
that we fixed in <ref>
(see step (a))
and collect for each expression $e$ an input–output table:
the set with an element $(\sigma, \f{untag}(v))$
for each evaluation $\sigma \vdash e \downarrow v$ done.

We say that an expression $e$ is linear if either
$e = x^{(t)}$ for $x$ a variable or
$e = c(e_1, \ldots, e_n)^{(t)}$ for
$c$ a value constructor and
$e_1, \ldots, e_n$ linear expressions.

Recall that we defined a program to consist of
a list of function declarations $f(x_1, \ldots, x_n) = e$.
The compression algorithm first applies the following procedure to each of the bodies $e$.

* If $e = c(e_1, \ldots, e_n)^{(t)}$ for $c$ a value constructor,
apply the procedure recursively to $e_1, \ldots, e_n$.

* If $e = \xsuppose c \xthen b \xend^{(t)}$,
apply the procedure recursively to $c$ and $b$;
and if after doing so
$e$ became
$e' = \xsuppose c' \xthen b' \xend^{(t)}$
where $c'$ admits no variable $x^{(u)}$ as a subexpression,
further replace $e' \becomes b'$.

* If neither of the above cases apply, try to find
a linear expression $\ell$ with the behavior specified by the input–output table of $e$.
(The algorithm for finding $\ell$ is postponed to <ref>.)
If such $\ell$ exists,
pick one and
replace $e \becomes \ell$
(in which we tag $\ell$ with expression tags disjoint from those used in $P$),
and we're done.
If not,
continue to the next steps.

* If $e = \xif c \xthen a \xelse b \xend^{(t)}$,
apply the procedure recursively to $c$, $a$, and $b$.
Suppose that after doing so
$e$ became
$e' = \xif c' \xthen a' \xelse b' \xend^{(t)}$.
If $c' = \xtrue^{(u)}$ for some $u$,
further replace $e' \becomes a'$.
Or, if $c' = \xfalse^{(u)}$ for some $u$,
further replace $e' \becomes b'$.

* If $e = f(e_1, \ldots, e_n)^{(t)}$ for $f$ a function,
apply the procedure recursively to $e_1, \ldots, e_n$.

After this, the algorithm removes from the program function definitions
g(\cdots) = \cdots
for functions $g$ that are not reachable from the primary function $f$ in the call graph.
The resulting program is the result of the compression phase.

Note that, in each step
the $w_k$ used in
the definition of $S$ in <ref>
remain unchanged if we disregard traces.
This is the sense in which the original program is equivalent to the compressed program,
that is,
they are equivalent on known input.

§.§.§ An algorithm for finding linear expressions

We are presented with the problem of
listing the linear expressions $\ell$ satisfying a given specification.
Let us be more precise.
We are given
a type $\tau$,
a typing context $\Gamma$ containing a definition of $\tau$, and
an input–output table $T = \{(\sigma_1, v_1), \ldots, (\sigma_n, v_n)\}$
such that for each $i = 1, \ldots, n$,
(i) $\sigma_i$ is an evaluation context and $v_i$ an untagged value of type $\tau$ and
(ii) all variables found in $\sigma_i$ are found in $\Gamma$ and vice versa.
The task is then to compute the (untagged) linear expressions $\ell$
that evaluate[
according to semantics like those given in <ref>
but ignoring traces
]to $v_i$ in context $\sigma_i$ for every $i = 1, \ldots, n$.

If $n = 0$ (that is, the input–output table is empty),
the problem is equivalent to finding all linear expressions of type $\tau$.
This possibly infinite list can easily be computed by a breadth-first search
applied to the recursive definition of linear expressions
given near the beginning of <ref>.

Now, suppose $n > 0$.
For convenience,
we shall rename the variables in $\Gamma$
so that they are called $x_1, \ldots, x_n$.
Recall the notation for tagged values established in <ref>.
An $\ell$-value is a tagged value $\in v^{\mathscr P(\{\circ, 1, \ldots, n\})}$
where $\mathscr P$ denotes the power set operator.
Moreover, given an $\ell$-value $w = c^A(w_1, \ldots, w_k)$,

\[
\ell(w)
\defeq
\{x_i^{()} \mid i \in \N \cap A\}
\cup
\begin{cases}
\{c^{()}(w_1', \ldots, w_k') \mid w_i' \in \ell(w_i)\},
& \text{if $\circ \in A$;} \\
\emptyset,
& \text{otherwise.}
\end{cases}
\]

$\ell(w)$ is a finite set.

Proceed by induction over $w$:
assume that the lemma is true for every proper subvalue of $w$.
Note that $A$ is finite.
Since each $\ell(w_i)$ is finite by the induction hypothesis,
the induction step follows from the formula defining $\ell(w)$.

To an input–output pair $(\sigma, v)$
v = c^{()}(v_1, \ldots, v_k),
we associate an $\ell$-value

\[
w(\sigma, v)
\defeq
c^{\{\circ\} \cup \{i \mid (x_i = v) \in \sigma\}}
(w(\sigma, v_1), \ldots, w(\sigma, v_k)).
\]

$\ell(w(\sigma, v))$ is the set of linear expressions
that evaluates to $v$ in the evaluation context $\sigma$.

Proceed by induction on $v$:
assume that the lemma is true for every proper subvalue of $v$.
The linear expressions evaluating to $v$ in the context $\sigma$ are
the variables $x_i$ such that $(x_i = v) \in \sigma$ and
expressions $c(e_1, \ldots, e_k)$
where each $e_i$ is a linear expression evaluating to $v_i$ in the context $\sigma$.
The induction step follows from unfolding definitions.

Given $\ell$-values
$w_1 = c_1^A(w_{1, 1}, \ldots, w_{1, p})$ and
$w_2 = c_2^B(w_{2, 1}, \ldots, w_{2, q})$,

\[
w_1 * w_2
\defeq
\begin{cases}
c_1^{A \cap B}(w_{1, 1} * w_{2, 1}, \ldots, w_{1, p} * w_{2, p}),
& \text{if $c_1 = c_2$;} \\
c_1^{A \cap B \setminus \{\circ\}}(w_{1, 1}, \ldots, w_{1, p}),
& \text{otherwise.}
\end{cases}
\]

$\ell(w_1 * w_2) = \ell(w_1) \cap \ell(w_2)$.

Proceed by induction on $w_1$:
assume that the lemma is true
when $w_1$ is replaced by any $w_{1, i}$.

Case: $c_1 = c_2$
Using the induction hypothesis,

\begin{align*}
\ell(w_1 * w_2)
\ell(c_1^{A \cap B}(w_{1, 1} * w_{2, 1}, \ldots, w_{1, p} * w_{2, p}))
\\
\{x_i^{()} \mid i \in \N \cap A \cap B\}
\\
&\quad \cup
\begin{cases}
\{c_1^{()}(w_1', \ldots, w_n') \mid w_i' \in \ell(w_{1, i} * w_{2, i})\},
& \text{if $\circ \in A \cap B$;} \\
\emptyset,
& \text{otherwise.}
\end{cases}
\\
\{x_i^{()} \mid i \in \N \cap A \cap B\}
\\
\begin{cases}
\{c_1^{()}(w_1', \ldots, w_n') \mid w_i' \in \ell(w_{1, i}) \cap \ell(w_{2, i})\},
& \text{if $\circ \in A \cap B$;} \\
\emptyset,
& \text{otherwise.}
\end{cases}
\\
\(
\{x_i^{()} \mid i \in \N \cap \mask{B}{A}\}
\cup
\begin{cases}
\{c_1^{()}(w_1', \ldots, w_n') \mid w_i' \in \ell(w_{1, i})\},
& \text{if $\circ \in A$;} \\
\emptyset,
& \text{otherwise.}
\end{cases}
\)
\\
\(
\{x_i^{()} \mid i \in \N \cap B\}
\cup
\begin{cases}
\{c_1^{()}(w_1', \ldots, w_n') \mid w_i' \in \ell(w_{2, i})\},
& \text{if $\circ \in B$;} \\
\emptyset,
& \text{otherwise.}
\end{cases}
\)
\\
&= \ell(w_1) \cap \ell(w_2).
\end{align*}

Case: $c_1 \neq c_2$
Unfolding definitions,

\begin{align*}
\ell(w_1 * w_2)
\ell(c_1^{A \cap B \setminus \{\circ\}}(w_{1, 1}, \ldots, w_{1, p}))
\\
\{x_i^{()} \mid i \in \N \cap A \cap B\}
\cup
\emptyset
\\
\(
\{x_i^{()} \mid i \in \N \cap \mask{B}{A}\}
\cup
\begin{cases}
\{c_1^{()}(w_1', \ldots, w_n') \mid w_i' \in \ell(w_{1, i})\},
& \text{if $\circ \in A$;} \\
\emptyset,
& \text{otherwise.}
\end{cases}
\)
\\
\(
\{x_i^{()} \mid i \in \N \cap B\}
\cup
\begin{cases}
\{c_2^{()}(w_1', \ldots, w_n') \mid w_i' \in \ell(w_{2, i})\},
& \text{if $\circ \in B$;} \\
\emptyset,
& \text{otherwise.}
\end{cases}
\)
\\
\ell(w_1) \cap \ell(w_2).
\end{align*}

We can now describe the algorithm for finding linear expressions.
Combining the lemmata above,
we find that the set

\[
\ell(w(\sigma_1, v_1) * \cdots * w(\sigma_n, v_n))
\]

contains exactly the linear expressions coforming to the input–output table $T$.
Since the definitions of $\ell$, $w$, and $*$ deal with
finite data in finite numbers of steps,
we can compute this set in its entirety by unfolding definitions,
thus giving an algorithm.

§ A PROOF-OF-CONCEPT IMPLEMENTATION

We provide a proof-of-concept implementation
which can be found at <https://gitlab.com/maxvi/ssgp>.
Excluding comments and blank lines,
it consists of a little less than 2700 lines of Haskell code.
Great care was taken to document the API and every piece of code,
amounting to over 1300 lines of comments.
Various QuickCheck tests are also included.
We emphasize that the implementation is a minimum viable product;
for instance, it is completely unoptimized
(see <ref>).

The implementation deviates from a naïve implementation of the theoretical ideas described above
in a number of ways,
many of which we shall cover in this section.
It produces code written in
what is, sparring $\ysuppose$-expressions, a subset of Haskell.

§.§ Results

We have chosen a few examples, tabulated below,
which highlight some strengths and weaknesses of our implementation.

Avail. funcs.
Avg. iter.

$[\Z] \to \Z$
$+ : (\Z, \Z) \to \Z$
$5/5 = 100\%$

$(\Z, \Z) \to \Z$
$\leq : (\Z, \Z) \to \xbool$
$5/5 = 100\%$

$[\Z] \to \Z$
$\leq : (\Z, \Z) \to \xbool$
$5/5 = 100\%$

$(\Z, [\Z]) \to [\Z]$
$\leq : (\Z, \Z) \to \xbool$
$5/5 = 100\%$

$() \to [\Z]$

$5/5 = 100\%$

$[\Z] \to [\Z]$
$\leq : (\Z, \Z) \to \xbool$
$0/5 = \ \ \ 0\%$

$[\Z] \to [\Z]$

$0/5 = \ \ \ 0\%$

Some benchmarks of our proof-of-concept implementation.

insert :: Int -> [Int] -> [Int]
insert x0 (Cons[Int] x1 (Cons[Int] x2 x3)) =
if f0 x0 x1 (Cons[Int] x2 x3) then
Cons[Int] x1 (insert x0 (Cons[Int] x2 x3))
Cons[Int] x0 (Cons[Int] x1 (Cons[Int] x2 x3))
insert x0 Nil[Int] = Cons[Int] x0 Nil[Int]
insert x0 (Cons[Int] x1 Nil[Int]) =
if f0 x0 x1 Nil[Int] then
Cons[Int] x1 (Cons[Int] x0 Nil[Int])
Cons[Int] x0 (Cons[Int] x1 Nil[Int])

f0 :: Int -> Int -> [Int] -> Bool
f0 x0 x1 x2 = leq x1 x0

Example of code produced by our proof-of-concept implementation.

Each example was run five times.
Each run was set to have a maximum of 10 cycles (see <ref>),
after which we would declare the evolution to not converge.
The constants used were
$N_\f{stretch} = 3$ and
$N_\f{mutate} = 300$.
The last column records the average number of
iterations (stretches, mutations, rewindings, compressions) that occured
before evolution converged to correct code.
At each iteration,
a new program is proposed and
this program is then run on a pre-fixed set of examples
through which local scores are assigned.

Every type is an Algebraic Data Type.
Integers are encoded by their binary representation.
Lists are defined recursively in a left-biased way as
[\Z] \Coloneqq \mathbf{Cons}(\Z, [\Z]) \mid \mathbf{Nil}.
There is no standard library;
each example can only use the functions specified in the third column,
nothing else.
If one were to add more useful functions there,
one would get better convergence rates.

Let us elaborate on the behavior of some of the tabulated functions.
$\min'$ picks out the smallest number from a list,
defaulting to $0$ if the list is empty.
$\f{insert}$ inserts a number into a list of numbers before the first entry
that is greater than or equal to the number.
$\f{helloworld}$ lists the ASCII codes for the string Hello World.
The rest are self-explanatory.

§.§ Comparison with other works

Koza [5] established the even-parity problem
as a benchmark for Genetic Programming.
The goal is to evolve code for the function $[\xbool] \to \xbool$
which returns
$\xtrue$ if the list has even number of $\xtrue$s and
$\xfalse$ otherwise.
Briggs and O'Neill [2] use this problem
to compare a number of approaches found in literature.
We reproduce their benchmarks below,
adding a benchmark of our own proof-of-concept implementation.

GP with Local Scoring
This paper

Exhaustive enumeration
[2]

[9]

GP with combinators
[2]

GP with iteration
[4]

Generic GP
[8]

[1]

GP with ADFs
[5]

Comparison of the smallest number of program assessments needed
for $99\%$ convergence rate on the even-parity problem
across various approaches.
Smaller numbers are better.
(No claims as to exhaustiveness of listed approaches are made.)

The last column records estimates for the smallest number of program assessments
needed during evolution
for an algorithm to find a correct solution with 99% probability.
A program assessment scores a program
by running it on a number of examples.

We ran our proof-of-concept implementation 100 times on the even-parity problem.
Every run eventually converged on correct code,
with the average number of programs tested before convergence being 335.3.
The best run needed to test just 79 programs and the worst 677 programs.
Generalizing from our data,
we find that if we stop evolution after 674 programs,
we arrive at a correct solution with $99\%$ probability.
The only built-in function made available from the onset was the binary operation,
\f{not} : \xbool \to \xbool.

§.§ Local scores and deep recursion

For scores $S(e)$,
we use instead a weighted average in which
each summand is weighted by the reciprocal of the call-stack depth.
In effect, deep recursive calls have less influence on scores.

§.§ Continuous scoring

The Hello World example uses a continuous scoring function,
meaning that it takes into account
how close the string that $\f{helloworld}()$ produces
is to the desired string Hello World,
instead of just rewarding $1$ when correct and $0$ when incorrect
(in which case evolving the correct code would be virtually impossible).
Local scoring means that if $\f{helloworld}()$ returned the string Hello Gorld,
we trace the problematic character, G, back to the expression that produced it
and then change that expression little by little,
inching in on the correct character, W.

§.§ Timeouts and restrictions to recursion

A fundamental issue is that the problem of bounding the running time of
an arbitrary program in a Turing-complete language
is undecidable
as was famously shown by Turing in 1936 [7].
To overcome this issue,
we imposed restrictions on what is allowed during execution:

* We impose a limit on
how many function calls can be made in one program execution.
If exceeded,
the local score of
every expression that was evaluated during the execution
gets punished.

* We impose restrictions on what forms of recursions are allowed.
Specifically, we shall only allow a call $f(v_1, \ldots, v_n)$
if there is an $i$
such that for all calls $f(w_1, \ldots, w_n)$ on the call-stack,
$|v_i| < |w_i|$.
Here, $|v|$ denotes the size of a value $v$,
that is, its number of nodes.
If this condition is violated,
the local score of every expression on the expression stack
(the expression-level analogue of the call-stack)
gets punished.

The restriction (2) alone ensures termination,
as the following lemma shows.

There is no infinite sequence $a_1, a_2, \ldots \in \N^n$
with the property that each $a_i$ has a coordinate $a_{i, j} \in \N$
such that $a_{i, j} < a_{i', j}$ for any $i' < i$.

Assume for contradiction that such sequence $a_*$ exists.
The sequence may be partitioned into $n$ subsequences,
p_{1, *}, \ldots, p_{n, *}
such that for each $i = 1, \ldots, n$,
p_{i, k, i} < p_{i, k', i}
for any $k' < k$.
Since $a_*$ is infinite,
one of these subsequences, say $p_{j, *}$, is infinite.
But then
p_{j, 1, j} > p_{j, 2, j} > \cdots
is an infinite descending sequence in $\N$,
which is not possible.

§.§ Controlled Recursion

When a recursive function is broken,
it is usually catastrophically broken.
This is because errors propagate (and multiply) upwards through recursion.
This affects negatively the quality of the local scores
which we want to reflect closeness to a solution.
For example, if we were to define natural numbers inductively using successors,
\N \Coloneqq 0 \mid S(\N),
then the recursive definition

\begin{align*}
0 \oplus m &\defeq m
\\
S(n) \oplus m &\defeq n \oplus m
\end{align*}

is only one $S$ away from being the correct definition of addition
($S(n) \oplus m = S(n \oplus m)$),
yet in terms of actual behavior it is quite far away:
$n \oplus m = m$.
To deal with this issue,
we employ a technique we shall call Controlled Recursion,
in which we answer recursive calls using training data.
For example, if we were trying to evolve $\oplus$ to be addition,
we would,
when producing the values $w_1, \ldots, w_N$ in <ref>,
evaluate the recursive call $n \oplus m$
in the body of the second equation above as $n + m$
instead of using the actual code for $\oplus$.
That means that the output only differs by $1$ from the desired output,
and the score is accordingly better
(that is, if we use a continuous scoring function as in <ref>)
than if we were to answer recursive calls using the actual code.
To discourage degenerate self-referential definitions like
S(n) \oplus m \defeq S(n) \oplus m,
we only answer recursive calls like this that are smaller
than the calls on the call-stack,
a la the restriction (2) we imposed in <ref>.

§.§ Stretches

Since the examples did not appear to need it,
we disabled the stretch (4) described in <ref>.
Moreover, for stretch (1),
we only introduce $\ysuppose$-expressions
at the top of bodies of equations.[
It would probably be better to allow them to be introduced wherever
but have a mechanism pushing them up the expression tree (generalization)
before they are promoted into $\yif$-conditionals
so as to not have to reinvent the same conditions for various subexpressions.

§.§ Limitations

A significant issue is the performance suboptimality of our proof-of-concept implementation.
With optimized code execution,
we could perhaps try many times more mutations in the same amount of time,
thereby searching much deeper for new mutations.
We discuss this further in <ref>.

Another striking issue is that of overfitting.
For example, overfitting obstructs discovery of correct code for the function
\f{reverse} : [\Z] \to [\Z]
reversing the items of a list.
Instead of attacking the problem algorithmically,
it generates more and more cases:
one for the empty list $[]$,
one for $[x_1]$,
one for $[x_1, x_2]$,
and so on.
While it obviously does get closer to a correct solution in terms of behavior,
it does not approach a correct solution in terms of code.
The issue is that lists are defined recursively in a left-biased way,
making operations on the beginning of the list far easier to discover
than operations on the end.

A human is able to immediately tell that such code is bad style;
perhaps if one taught the same intuition to a neural network,
that could be used to stir away from overfitting.
See <ref> for more discussion.

Overfitting was not an issue
in any of the converging examples from <ref>.

§ EXTENSIONS AND FUTURE WORK

§.§ Crossover and parallelism

In contrast to a lot of the literature (see <ref>),
we use what is a kind of hill-climbing algorithm:
at every point in the algorithm,
we have exactly one program.
It is typical to instead evolve a population of programs,
mutating them and using a procedure called crossover
to combine two programs producing one or more offspring programs.
We remark that
this could be added on top of our hill-climbing method,
making for highly parallelized Genetic Programming:
one could do $C$ cycles of hill-climbing (see <ref>) for each program in the population
\{P_{(1)}, \ldots, P_{(n)}\}
in parallel,
yielding a new population
\{P_{(1)}', \ldots, P_{(n)}'\}
which is then extracted for crossover
combining programs at random
and natural selection killing of all but $n$ of the resulting programs.
This procedure is repeated until a solution is found.
With this, many hill-climbing processes run in parallel but
still share discoveries once in a while,
avoiding too much duplicated effort.

§.§ Optimizations

By far the most significant component performance-wise is
that which executes programs.
As we were more focused on the theoretical background,
no serious attempt at optimizing this was made
in our proof-of-concept implementation written in Haskell.
Let us discuss some techniques and ideas
that could be used in a performant implementation.

* Use a more performant language such as Rust or C.

* Currently, we represent code as an Abstract Syntax Tree
which is quite inefficient for a number of reasons.
For instance, execution requires dereferencing a lot of pointers
resulting in many cache misses.
A more efficient, flat representation of code,
such as a stack machine,
could be used instead.

* Expressions that attain high scores could be compiled,
making for extremely performant execution of those parts of the program
that are unlikely to change.
Compilation is typically a heavy process and
it is therefore unlikely that it is
worth it to recompile the entire program on every mutation,
but perhaps a good balance could be struck.

* Since we are running the same (or similar) code again and again,
it would make sense to make heavy use of memoization,
trading CPU cycles for increased memory usage.

* A significant amount of time is spent on testing out bad mutations,
typically scoring extremely poorly.
One could use heuristics for quickly discarding
large swaths of bad mutations with only few false positives.
Local Scoring is particularly apt for this.
For example, if one was to test a mutation $e \becomes e'$ of an expression $e$,
one could first compute the score of $e'$
with respect to a small, randomly chosen subset of $w_1, \ldots, w_N$
(see <ref>)
chosen so that for each $w_i$ in this subset
the expression $e'$ appears somewhere in one of its traces,
and then preemptively discard the mutation if this approximate score is
significantly smaller than $S(e)$.[
Or perhaps, instead of $S(e)$, it would be better to
use the corresponding approximate score computed for $e$.
This would necessitate storing not just the local scores
but also all summands of the averages,
so that averages of subsets can be computed at a later point.

* While our proof-of-concept implementation does ensure
that the exact same program isn't tried multiple times,
one could employ more advanced ways of ensuring
that equivalent mutations aren't attempted multiple times.
One would need to specify algorithms that are able to tell
if a mutation on a program $P$ corresponds
to a mutation on a program $P'$ equivalent to $P$ by a number of stretches
(see <ref>).
Perhaps a hash function could be devised for this purpose.

§.§ Integration with Deep Learning methods

We are choosing new code to try out essentially at random
instead of doing so intelligently and
drawing from an intuitive understanding of
what changes are needed in what situations.
Recently, there has been major breakthroughs on
the subject of using Deep Learning methods to generate code
(e.g., [3] and [6]).
An interesting direction would be to hybridize the approaches,
combinining the overview of Local Scoring with the intuition of Deep Learning.
Let us speculate a bit on what that could look like.

* One could incorporate into the scores an assessment of the plausibility of code,
as determined by a Deep Learning model,
rewarding code that looks like human-written code.
This could help guide the search in directions
of known patterns,
combating issues like overfitting and getting stuck in local minima.

* What kind of mutation or stretch to do could be chosen using a neural network
that is trained (on a fixed training set of code)
to predict what is most likely to cause improvements.
Deep Learning-based code generation could be used to
propose candidates for the replacing expressions
that we use when mutating
instead of generating these at random.

* Additionally, since we use mutation conservativity (see <ref>),
there will typically be long periods of attempting mutations
before a successful mutation is found.
One could collect data from these failed mutations.
An idea is to then use Deep Learning to
analyze these attempted mutations and their resulting local scores
in order to get a sense of which mutations do well,
which could then be leveraged to pick out qualified guesses for new mutations
making use of problem-specific knowledge.
Perhaps, one could even train a Deep Learning model during evolution on this data
to predict what mutations are likely successful.

[1]
Alexandros Agapitos and Simon M Lucas.
Learning recursive functions with object oriented genetic
In European Conference on Genetic Programming, pages 166–177.
Springer, 2006.

[2]
Forrest Briggs and Melissa O’Neill.
Functional genetic programming with combinators.
In Proceedings of the Third Asian-Pacific workshop on Genetic
Programming, ASPGP, pages 110–127, 2006.

[3]
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira
Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg
Brockman, et al.
Evaluating large language models trained on code.
arXiv preprint arXiv:2107.03374, 2021.

[4]
Evan Kirshenbaum.
Iteration over vectors in genetic programming.
HP Laboratories Technical Report HPL-2001-327, 2001.

[5]
John R Koza.
Genetic programming II, volume 17.
MIT press Cambridge, 1994.

[6]
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser,
Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago,
et al.
Competition-level code generation with alphacode.
arXiv preprint arXiv:2203.07814, 2022.

[7]
Alan Mathison Turing.
On computable numbers, with an application to the
J. of Math, 58(345-363):5, 1936.

[8]
Man Leung Wong and Kwong Sak Leung.
Evolving recursive functions for the even-parity problem using
genetic programming.
In Advances in genetic programming, pages 221–240. MIT press,

[9]
Gwoing Tina Yu.
An analysis of the impact of functional programming techniques
on genetic programming.
University of London, University College London (United Kingdom),


# Formation of singularities in solutions to nonlinear hyperbolic systems with
general sources

Johannes Bärlin

###### Abstract

We consider nonlinear hyperbolic systems with a general source and prove that
for appropriately chosen smooth initial data the lifespan of the associated
$C^{1}$-solution $u$ cannot be infinite. We employ ideas of F. John [Joh74]
and L. Hörmander [Hör87] to show that the derivative $u_{x}$ of $u$ becomes
unbounded in finite time.

##  1 Introduction

In this paper we consider quasi-linear hyperbolic systems of the form

(1.1) $\displaystyle u_{t}+a(u)u_{x}=g(u)$

on $(0,\infty)\times\mathbb{R}$ where $a:\Omega\mapsto\mathbb{R}^{N\times N}$
and $g:\Omega\mapsto\mathbb{R}^{N}$ are smooth functions with
$N\in\mathbb{N}$, $\Omega\subset\mathbb{R}^{N}$ open and $0\in\Omega$,
satisfying the following three assumptions:

  * A1

$a(0)$ has only real, simple eigenvalues;

  * A2

There is $p\in\\{1,\ldots,N\\}$ such that the $p$-th eigenvalue of $a$ is
genuinely nonlinear at $0$;

  * A3

$g(0)=0$.

By adapting ideas of John and Hörmander [Joh74, Hör87] we will show:

######  Theorem 1.1.

If A1, A2, A3 hold then there exist smooth compactly supported functions
$u^{0}:\mathbb{R}\mapsto\Omega$ such that while remaining bounded, the unique
$C^{1}$-solution $u$ of (1.1) with data $u(0,\cdot)=u^{0}$ exists only for
finite time.

The question whether solutions to hyperbolic systems develop singularities
over time is classical. For $g\equiv 0$, it has been answered affirmatively
for general small and compactly supported data under the assumption of genuine
non-linearity by P. Lax in [Lax64] for $N=1,2,$ and for general
$N\in\mathbb{N}$ by F. John in [Joh74], with a notable generalization by T.-P.
Liu in [Liu79].

If however $g\not\equiv 0$, the situation can be dichotomous in the sense that

  * (i)

for small data a smooth solution to (1.1) exists for all time while

  * (ii)

for some large initial data the smooth solution of (1.1) must develop a
singularity.

While property (i) is known to hold for quite general classes notably of
relaxation systems [Zen99, MZ02, Yon04, KY04, BHN07, BZ11] (cf. also, e.g.,
[Rug04, LL09, Fre22]), blow-up results (ii) have been shown in particular
cases by ad hoc constructions, see e.g. [LL09, HW19, HRW22, Bä22].

The finding of the present paper shows that, independently of the nature of
the source $g$, it is the genuine non-linearity of the differential operator
$\partial_{t}+a(\cdot)\partial_{x}$ that by itself entails the breakdown of
certain smooth solutions. The result applies to all systems considered in
[Zen99, MZ02, Yon04, KY04, BHN07, BZ11] if the space dimension is equal to one
and the assumptions A1-A3 are satisfied. It is sharp in the sense that there
exist significant relaxation systems with linear principal part
$\partial_{t}+a\partial_{x}$ $-$ and nonlinear equilibrium system $-$ whose
solutions remain smooth for all times, see e.g. [LL09], Sec. 4.

##  2 Preliminaries

We start with some notation. Let $T>0,m,n\in\mathbb{N}$ and $k\in\\{1,2\\}$.
The space $C^{\infty}_{c}(\mathbb{R};\mathbb{R}^{m})$ contains all infinitely
many times continuously differentiable functions
$f:\mathbb{R}\rightarrow\mathbb{R}^{m}$ with compact support
$\textnormal{supp}\,f\subset\mathbb{R}$. We denote by
$C([0,T]\times\mathbb{R};\mathbb{R}^{m})$ the space of continuous functions
$f:[0,T]\times\mathbb{R}\mapsto\mathbb{R}^{m}$. A function
$f:[0,T]\times\mathbb{R}\rightarrow\mathbb{R}^{m}$ is an element of the space
$C^{k}([0,T]\times\mathbb{R};\mathbb{R}^{m})$ if for all
$\alpha\in\mathbb{N}^{2}_{0},|\alpha|\leq k,$ the partial derivative
$\partial^{\alpha}f$ exists on $(0,T)\times\mathbb{R}$ and is equal to a
function $f_{\alpha}\in C([0,T]\times\mathbb{R};\mathbb{R}^{m})$ there. Here
$\partial^{\alpha}$ is the usual multi-index notation for
$\partial_{t}^{\alpha_{1}}\partial_{x}^{\alpha_{2}}$. We write $f\in
C^{k}_{c}([0,T]\times\mathbb{R};\mathbb{R}^{m})$ if the support of $f$ is
compact. Similar definitions are used for
$C([0,T)\times\mathbb{R};\mathbb{R}^{m})$ and
$C^{k}([0,T)\times\mathbb{R};\mathbb{R}^{m})$. We will drop the reference to
$\mathbb{R}^{m}$ in the following since it should be clear from the context
where a considered function takes its values. Finally if
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ is a differentiable function then
$Df$ denotes its Jacobi-matrix. If $n=1$ we will also write $f^{\prime}$.

Fix a $p\in\\{1,\ldots,N\\}$ satisfying assumption A2. By A1 there are
$\delta>0$ and smooth functions

$\displaystyle\lambda_{i}:$ $\displaystyle
B_{2\delta}(0)\subset\mathbb{R}^{N}\rightarrow\mathbb{R},$ $\displaystyle
r_{i}:$ $\displaystyle
B_{2\delta}(0)\subset\mathbb{R}^{N}\rightarrow\mathbb{R}^{N\times 1},$
$\displaystyle l_{i}:$ $\displaystyle
B_{2\delta}(0)\subset\mathbb{R}^{N}\rightarrow\mathbb{R}^{1\times N},$

for all $i\in\\{1,\ldots,N\\}$ which satisfy for all $u\in B_{2\delta}(0)$ and
all $i,j$

$\displaystyle
l_{i}(u)a(u)=\lambda_{i}(u)l_{i}(u),\;a(u)r_{i}(u)=\lambda_{i}(u)r_{i}(u),\;\textnormal{and}\;\lambda_{i}(u)<\lambda_{j}(u)\;\textnormal{if}\;i<j.$

We normalize the above eigenvectors of $a$ such that for all $i,j$

$\displaystyle|l_{i}|=1\;\textnormal{and}\;l_{i}r_{j}=\delta_{ij},$

and such that by Assumption A2 it holds

(2.1) $\displaystyle\langle D\lambda_{p}(0),r_{p}(0)\rangle<0.$

Set

(2.2) $\displaystyle c_{\lambda}:=\min_{i\neq p}\inf_{u\in
B_{\delta}(0)}|\lambda_{i}(u)-\lambda_{p}(u)|>0.$

Fix $T>0$ and a solution

(2.3) $\displaystyle u\in C^{2}([0,T]\times\mathbb{R})$

of (1.1) with

(2.4) $\displaystyle|u(t,x)|\leq\delta.$

By differentiation of (1.1) the derivative of $u$

$\displaystyle w(t,x):=u_{x}(t,x)$

satisfies the equation

(2.5) $\displaystyle w_{t}+a(u)w_{x}=Dg(u)w+\gamma(u,w)$

where $\gamma$ is a quadratic form in $w$. Decompose $w$ with respect to
$\\{r_{j}(u)\\}_{j}$ to obtain

$\displaystyle w(t,x)=\sum_{j}w_{j}(t,x)r_{j}(u(t,x)).$

The component functions $w_{i}$ satisfy certain partial differential equations
along the $i$-th characteristic curves. The latter are determined by the
ordinary differential equations

(2.6)
$\displaystyle\frac{d}{dt}X_{i}(t;x)=\lambda_{i}(u(t,X_{i}(t;x))),\;X_{i}(0;x)=x,$

which may be solved under the above hypothesis on $[0,T]$ for all
$x\in\mathbb{R}$. The $i$-th characteristic curve $C_{i}(x)$ starting at
$(0,x)$ is given by the trace of

$\displaystyle t\mapsto(t,X_{i}(t;x)).$

For given $i$ and $(t,x)\in[0,T]\times\mathbb{R}$ let $z_{i}=z_{i}(t,x)$ be
the unique element of $\mathbb{R}$ such that the $i$-th characteristic curve
starting at $(0,z_{i})$ runs through $(t,x)$, i.e.

$\displaystyle(t,x)\in C_{i}(z_{i}).$

If $f:[0,T]\times\mathbb{R}\rightarrow\mathbb{R}$ is a differentiable function
then let $L_{i}f$ denote the derivative of $f$ with respect to $t$ along the
$i$-th characteristic:

$\displaystyle L_{i}f(t,x)=f_{t}(t,x)+\lambda_{i}(u(t,x))f_{x}(t,x).$

From (2.5) one obtains a system of partial differential equations:

(2.7) $\displaystyle
L_{i}w_{i}=\sum_{j,k}\gamma_{ijk}(u)w_{j}w_{k}+\sum_{k}G_{ik}(u)w_{k}$

where $\gamma_{ijk}$ are given in [Joh74] and below; they satisfy for all
$i,j$

(2.8) $\displaystyle\gamma_{ijj}(u)=-\delta_{ij}\langle
D\lambda_{i}(u),r_{i}(u)\rangle.$

The functions $G_{ik}$ will be discussed below, too. There are constants
$\overline{\gamma},\overline{G}>0$ such that

$\displaystyle\max_{i}\sup_{u\in B_{\delta}(0)}\sum_{j,k}|\gamma_{ijk}(u)|$
$\displaystyle\leq\overline{\gamma}$ $\displaystyle\max_{i}\sup_{u\in
B_{\delta}(0)}\sum_{k}|G_{ik}(u)|$ $\displaystyle\leq\overline{G}.$

Following [Hör87] we calculate the differential of
$w_{i}(dx-\lambda_{i}(u)dt)$ and obtain by (2.7)

(2.9) $\displaystyle
d(w_{i}(dx-\lambda_{i}(u)dt)=\left(\sum_{jk}\Gamma_{ijk}(u)w_{j}w_{k}+\sum_{k}G_{ik}(u)w_{k}\right)dt\wedge
dx$

where the $\Gamma_{ijk}$ are like in [Hör87], in particular for all $i,j$

(2.10) $\displaystyle\Gamma_{ijj}(u)=0.$

We find a constant $\overline{\Gamma}>0$ such that

$\displaystyle\sup_{i}\sup_{u\in
B_{\delta}(0)}\sum_{j,k}|\Gamma_{ijk}(u)|\leq\overline{\Gamma}.$

The reader may find expressions and relations for the coefficient functions
$c_{ijk},\gamma_{ijk},\Gamma_{ijk}$ and $G_{ik}$ at the end of this section.
We end our considerations on a solution (2.3), (2.4) by the following
statement which is a straightforward extension of Lemma 1.2.2 in [Hör87] to
systems with sources.

######  Lemma 2.1.

Let $T>0$ und let $i\in\\{1,\ldots N\\}$. Suppose $u\in
C^{2}([0,T]\times\mathbb{R})$ solves (1.1) with $|u(t,x)|\leq\delta$. Let
$\tau$ be a $C^{1}$-arc in $[0,T]\times\mathbb{R}$ intersecting the $i$-th
characteristic curves transversally, and let $A_{i}(\tau)$ be the open region
bounded by $\tau$, the orbits of $L_{i}$ through the end points of $\tau$ and
an interval $\tau_{i0}$ where $\\{t=0\\}$. Then

(2.11) $\displaystyle\int\limits_{\tau}|w_{i}(dx$
$\displaystyle-\lambda_{i}(u)dt)|$
$\displaystyle\leq\int\limits_{\tau_{i0}}|w_{i}|dx+\int\limits_{A_{i}(\tau)}|\sum_{j,k}\Gamma_{ijk}(u)w_{j}w_{k}+\sum_{k}G_{ik}(u)w_{k})|dxdt.$

###### Proof.

The proof is essentially the same as in [Hör87] using (2.9) and Stokes’
formula. Let us just comment on the case when $w_{i}$ does not have constant
sign on $\tau$. Then one considers the (relatively) open set

$\displaystyle\tilde{\tau}:=\tau\cap\\{w_{i}\neq 0\\}.$

Use a compact exhaustion
$\\{\tau_{j}\\}_{j\in\mathbb{N}},\tau_{j}\subset\textnormal{int}\,\tau_{j+1},\cup_{j}\tau_{j}=\tilde{\tau},$
of $\tilde{\tau}$ and note that each $\tau_{j}$ consists of finitely many
singletons and pathwise connected components. Then apply the considerations
holding when $w_{i}$ has constant sign on $\tau$ to each of these components.
∎

Assumption A3 $g(0)=0$ implies a propagation of support result for solutions
to (1.1) which we report in the next lemma.

######  Lemma 2.2.

Let $T>0$. Suppose $u\in C^{1}([0,T]\times\mathbb{R})$ is a solution of (1.1)
with

$\displaystyle\textnormal{supp}\,u(0,\cdot)\subset[a,b]$

for some $a<b$. Then for all $t\in[0,T]$ it holds

$\displaystyle\textnormal{supp}\,u(t,\cdot)\subset[a+\lambda_{1}(0)t,b+\lambda_{N}(0)t].$

###### Proof.

Consider all characteristics emanating, at $t=0$, from
$\mathbb{R}\backslash(a,b)$. ∎

We close this section with an existence result for (1.1) with smooth compactly
supported data. For a function $f:\mathbb{R}\rightarrow\mathbb{R}^{N}$ set

$\displaystyle||f||_{\infty}:=\sup\limits_{x\in\mathbb{R}}|f(x)|.$

######  Lemma 2.3.

Let $c>0$ and $\tilde{\delta}<\delta$, and consider a compactly supported
$C^{2}$-function $u^{0}:\mathbb{R}\rightarrow B_{\tilde{\delta}}(0)$ with
$||u^{0}_{x}||_{\infty}\leq c$. Then there are a time
$T=T(\tilde{\delta},c)\in(0,\infty)$ and a unique solution $u\in
C^{2}([0,T]\times\mathbb{R})$ of (1.1) with initial data $u(0,\cdot)=u^{0}$.
For all $\alpha\in\mathbb{N}^{2}_{0},|\alpha|\leq 2$, the derivatives
$\partial^{\alpha}u$ of $u$ are bounded and for all
$(t,x)\in[0,T]\times\mathbb{R}$ it holds $|u(t,x)|<\delta$.

###### Proof.

Adapt the proof of Theorem 1.2.5. in [Hör87] using assumption A3. The source
term $g$ does not cause any problems since it is a lower order term. Also note
[Lax73] and [Rau12] on how to deal with strictly hyperbolic systems in one
space dimension. ∎

We finally give some relations and expressions concerning certain coefficient
functions appearing in the above analysis. From [Joh74] we have

$\displaystyle
c_{ijk}(u)=\left(\frac{d}{ds}(l_{i}(u)a(u+sr_{k}(u))r_{j}(u)\right)_{s=0}$

and

$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\gamma_{ijk}=\gamma_{ikj},\;\gamma_{iii}=-c_{iii},$
$\displaystyle 2\gamma_{iik}$ $\displaystyle=-c_{iik}-c_{iki}+\sum_{j,j\neq
i}\frac{\lambda_{i}-\lambda_{k}}{\lambda_{j}-\lambda_{i}}c_{ijk}\langle
l_{j},l_{i}\rangle\;\textnormal{if}\;k\neq i,$ $\displaystyle 2\gamma_{ijk}$
$\displaystyle=-\frac{\lambda_{j}-\lambda_{k}}{\lambda_{j}-\lambda_{i}}c_{ijk}-\frac{\lambda_{k}-\lambda_{j}}{\lambda_{k}-\lambda_{i}}c_{ikj}\;\textnormal{if}\;j\neq
i,k\neq i.$

The coefficients $\Gamma_{ijk}$ are determined by the requirement [Hör87]

$\displaystyle\sum_{j,k}\gamma_{ijk}(u)w_{j}w_{k}+\sum_{k}w_{i}w_{k}\langle
D\lambda_{i}(u),r_{k}(u)\rangle=\sum_{j,k}\Gamma_{ijk}(u)w_{j}w_{k}$

for all $w\in\mathbb{R}^{N}$. An explicit expression for $G_{ik}$ may be
obtained from the requirement that for all $w\in\mathbb{R}^{N}$ it holds

$\displaystyle\sum_{k}G_{ik}(u)w_{k}=\sum_{k}l_{i}Dg(u)r_{k}w_{k}+\sum_{j,k,j\neq
i}\frac{1}{\lambda_{j}-\lambda_{i}}c_{ijk}(l_{k}g(u))(\langle
l_{j},l_{i}\rangle w_{i}-w_{j}).$

##  3 Initial data and smallness properties

We begin with the construction of the special initial data that will lead to
the formation of a singularity. Let $U:I\rightarrow B_{\delta}(0)$ be an
integral curve of $r_{p}$ through $0$ defined on an open interval
$I\subset\mathbb{R}$ with $0\in I$:

$\displaystyle U^{\prime}(\xi)=r_{p}(U(\xi))\;(\xi\in I),\;U(0)=0.$

Let $\alpha\in C^{\infty}_{c}(\mathbb{R})$ with $\alpha(\mathbb{R})\subset
I,\textnormal{supp}\,\alpha\subset(-1/2,1/2)$ and
$\max\limits_{x}|\alpha^{\prime}|=\max\limits_{x}\alpha^{\prime}>0$. For
$\varepsilon\in(0,1]$ define

$\displaystyle u^{0\varepsilon}(x)=U(\varepsilon\alpha(x))\;(x\in\mathbb{R}).$

Then $u^{0\varepsilon}\in C^{\infty}_{c}(\mathbb{R})$.

######  Remark 3.1.

For $g\equiv 0$, these data give rise to a breaking wave. The idea of using
the same data for the system with non-vanishing source is that the associated
blow-up of the quantity $w_{p}$ persists if the source term is small.

The purpose of this section consists in showing the following

######  Lemma 3.2.

For any fixed $\overline{T}\in(0,\infty)$ there exist constants
$c_{J},c_{M},c_{S},c_{V}>0$ and $\nu>0$ such that if for
$\varepsilon,\kappa\in(0,\nu]$ and

$\displaystyle 0<T\leq\overline{T}\varepsilon^{-1}$

a function $u\in C^{2}([0,T]\times\mathbb{R})$ solves the Cauchy problem

(3.1) $\displaystyle\left\\{\begin{aligned} u_{t}+a(u)u_{x}&=\varepsilon\kappa
g(u),\\\ u(0,x)&=u^{0\varepsilon}(x).\end{aligned}\right.$

then for all $t\in[0,T]$ the quantities

$\displaystyle J(t)$
$\displaystyle:=\sup\limits_{s\in[0,t]}\int_{a_{p}(s)}^{b_{p}(s)}|w_{p}(s,x)|dx,$
$\displaystyle M(t)$
$\displaystyle:=\sup\limits_{(s,x)\in[0,t]\times\mathbb{R}}|u(s,x)|,$
$\displaystyle S(t)$
$\displaystyle:=\sup\limits_{s\in[0,t]}b_{p}(s)-a_{p}(s),$
$\displaystyle\tilde{V}(t)$ $\displaystyle:=\max\limits_{i\neq
p}\sup\limits_{(s,x)\in[0,t]\times\mathbb{R}}|w_{i}(s,x)|,$ $\displaystyle
W^{out}_{p}(t)$
$\displaystyle:=\sup\limits_{\begin{subarray}{c}(s,x)\in[0,t]\times\mathbb{R},\\\
(s,x)\not\in R_{p}(t)\end{subarray}}|w_{p}(s,x)|,$ $\displaystyle V(t)$
$\displaystyle:=W^{out}_{p}(t)+\tilde{V}(t),$

satisfy

(3.2) $\displaystyle J(t)$ $\displaystyle<c_{J}\varepsilon$ (3.3)
$\displaystyle M(t)$ $\displaystyle<c_{M}\varepsilon<\delta$ (3.4)
$\displaystyle S(t)$ $\displaystyle<c_{S}$ (3.5) $\displaystyle V(t)$
$\displaystyle<c_{V}\varepsilon^{2}.$

Here we have set

$\displaystyle b_{p}(t)$ $\displaystyle:=X_{p}(t;1/2)$ $\displaystyle
a_{p}(t)$ $\displaystyle:=X_{p}(t;-1/2)$ $\displaystyle R_{p}(t)$
$\displaystyle:=\\{(s,x)\in[0,t]\times\mathbb{R}|\;x\in[a_{p}(s),b_{p}(s)]\\}.$

######  Remark 3.3.

Since we expect the solution $u$ to be of the same size as $u^{0\varepsilon}$
we find that $J$ and $M$ should be comparable to $u^{0\varepsilon}$, too,
hence of order $\varepsilon$. The quantities $\tilde{V}$ and $W^{out}_{p}$ are
initially equal to zero, and thinking of the idea of perturbing the simple
wave, we hope that the interaction between $w_{i},i\neq p,$ and $w_{p}$ is
weak, and that $w_{p}$ along the $p$-th characteristics outside $R_{p}$
remains small compared to $w_{p}$ inside $R_{p}$ by the propagation properties
of the hyperbolic differential operator in (3.1).

###### Proof.

Let $\overline{T}>0$. For

$\displaystyle\overline{c}$
$\displaystyle:=\max\left\\{1,\max\limits_{i}\sup\limits_{u\in
B_{\delta}(0)}\sum_{j,k}|c_{ijk}(u)|\right\\}$ $\displaystyle\overline{r}$
$\displaystyle:=\sup\limits_{u\in B_{\delta}(0)}\sum\limits_{k}|r_{k}(u)|$

set

$\displaystyle c_{J}$ $\displaystyle:=2\max_{x}\alpha^{\prime}(x)$
$\displaystyle c_{V}$
$\displaystyle:=2\overline{G}c_{\lambda}^{-1}c_{J}(1+\overline{G}\,\overline{T})$
$\displaystyle c_{S}$ $\displaystyle:=2\overline{c}(1+c_{J}\overline{T})$
$\displaystyle c_{M}$
$\displaystyle:=2\overline{r}(c_{J}+c_{V}(1+\overline{T}(\lambda_{N}(0)-\lambda_{1}(0))).$

Take $\nu$ so small that

(3.6) $\displaystyle c_{M}\nu<\delta$

holds. Let $\varepsilon,\kappa\in(0,\nu]$ with $\nu$ to be determined further
later on, and let $T\in(0,\overline{T}\varepsilon^{-1}]$. Suppose we are given
a solution $u\in C^{2}([0,T]\times\mathbb{R})$ of the Cauchy problem 3.1. By
Lemma 2.2 we find that $u\in C^{2}_{c}([0,T]\times\mathbb{R})$. At $t=0$ it
holds

(3.7)
$\displaystyle|u(0,x)|=|u^{0\varepsilon}(x)|=|\int\limits^{x}_{-\infty}\varepsilon\alpha^{\prime}(y)r_{p}(U(\varepsilon\alpha(y))dy|\leq\varepsilon\overline{r}c_{J}\leq\frac{c_{M}}{2}\varepsilon<c_{M}\varepsilon$

Because $u\in C^{2}_{c}$ the function $M$ is continuous on $[0,T]$ and we find
a $t_{1}\in(0,T]$ such that (3.3) holds for all $t\in[0,t_{1}]$ since the
stronger inequality (3.7) holds at $t=0$. Hence on $[0,t_{1}]$ the functions
$J,S,V,\tilde{V},W^{out}_{p}$ are well-defined, continuous and increasing. We
will show that the set

$\displaystyle E_{1}:=\\{t\in[0,T]|\;\eqref{cJ}-\eqref{cV}\;\textnormal{hold
on}\;[0,t]\\}$

is non-empty, open and closed, hence equal to $[0,T]$. We have by

$\displaystyle
u_{x}(0,x)=\varepsilon\alpha^{\prime}(x)r_{p}(u(0,x))=w_{p}(0,x)r_{p}(u(0,x))$

that initially the waves $w_{j}$ satisfy

(3.8) $\displaystyle w_{i}(0,x)$
$\displaystyle=0\;\;\;\;\;\;\;\;\textnormal{if}\;i\neq p,$ (3.9)
$\displaystyle w_{p}(0,x)$ $\displaystyle=\varepsilon\alpha^{\prime}(x).$

By (3.8), (3.9) and the compact support of $\alpha$ in $(-1/2,1/2)$ we find
$0\in E_{1}$ since

$\displaystyle J(0)$
$\displaystyle\leq\varepsilon\max_{x}\alpha^{\prime}=\varepsilon\frac{c_{J}}{2}$
$\displaystyle S(0)$ $\displaystyle=1\leq\frac{c_{S}}{2}$ $\displaystyle V(0)$
$\displaystyle=0\leq\frac{c_{V}}{2}.$

By continuity and monotonicity of $J,M,S$ and $V$ the set $E_{1}$ is open in
$[0,T]$. It remains to show that $E_{1}$ is closed which is by monotonicity
equivalent to:

$\displaystyle\textnormal{If
for}\;T^{\prime}\in(0,T]\;\textnormal{\eqref{cJ}-\eqref{cV} hold
on}\;[0,T^{\prime})\;\textnormal{then \eqref{cJ}-\eqref{cV} hold
at}\;t=T^{\prime}.$

Suppose for $T^{\prime}\in(0,T]$ we have $[0,T^{\prime})\subset E_{1}$ and let
$t\in[0,T^{\prime})$. Note that $M(T^{\prime})<\delta$ by (3.3). For
$s\in[0,t]$ it holds (compare [Joh74] p. 394)

$\displaystyle\frac{d}{ds}(b_{p}(s)-a_{p}(s))$
$\displaystyle=\int\limits^{b_{p}(s)}_{a_{p}(s)}\sum_{k}c_{ppk}(u(s,x))w_{k}(s,x)dx$
$\displaystyle\leq\overline{c}(\tilde{V}(s)S(s)+J(s)).$

Integrating the last relation over $[0,t]$ we find by
$t\leq\overline{T}\varepsilon^{-1}$ and $[0,t]\subset E_{1}$ that

$\displaystyle S(t)$ $\displaystyle\leq
S(0)+\overline{c}(\tilde{V}(t)S(t)t+J(t)t)$
$\displaystyle\leq\overline{c}(1+c_{J}\overline{T})+\overline{c}\overline{T}c_{V}\varepsilon
S(t).$

If $\nu$ satisfies

(3.10) $\displaystyle 1-\overline{c}\overline{T}c_{V}\nu\geq\frac{2}{3}$

then

$\displaystyle S(t)\leq\frac{3}{2}\overline{c}(1+c_{J}\overline{T})<c_{S}$

which shows $S(T^{\prime})<c_{S}$.

To estimate $J(t)$ we use Lemma 2.1 with
$\tau=\\{s\\}\times[a_{p}(s),b_{p}(s)]$ for $s\in[0,t]$ to obtain

$\displaystyle\int\limits_{a_{p}(s)}^{b_{p}(s)}|w_{p}(s,x)|dx\leq
J(0)+\int\limits_{A_{p}(\tau)}|\sum_{j,k}\Gamma_{pjk}(u)w_{j}w_{k}+\varepsilon\kappa\sum_{k}G_{ik}(u)w_{k}|dxdt.$

By (2.10) we see that the terms involving $\Gamma_{pjk}(u)w_{j}w_{k}$ are
essentially linear and we get

$\displaystyle J(t)$ $\displaystyle\leq
J(0)+\overline{\Gamma}[\tilde{V}(t)^{2}S(t)t+\tilde{V}(t)J(t)t]+\varepsilon\kappa\overline{G}[\tilde{V}(t)S(t)t+J(t)t]$
$\displaystyle\leq\varepsilon\frac{c_{J}}{2}+\varepsilon^{3}\overline{\Gamma}c_{V}^{2}c_{S}\overline{T}+\varepsilon^{2}\kappa\overline{G}c_{V}c_{s}\overline{T}+J(t)[\varepsilon\overline{\Gamma}c_{V}\overline{T}+\kappa\overline{G}\,\overline{T}].$

If $\nu$ satisfies

(3.11)
$\displaystyle\nu^{2}(\overline{\Gamma}c_{V}^{2}c_{S}\overline{T}+\overline{G}c_{V}c_{s}\overline{T})$
$\displaystyle\leq\frac{1}{8}c_{J},$ (3.12) $\displaystyle
1-\nu(\overline{\Gamma}c_{V}\overline{T}+\overline{G}\,\overline{T})$
$\displaystyle\geq\frac{5}{6}$

then

$\displaystyle J(t)\leq\frac{3}{4}c_{J}\varepsilon<c_{J}\varepsilon$

implying $J(T^{\prime})<c_{J}\varepsilon$.

We estimate $u(s,x)$ for all $(s,x)\in[0,t]\times\mathbb{R}$ using Lemma 2.2
by

$\displaystyle|u(s,x)|$
$\displaystyle=|\int\limits_{-\infty}^{x}u_{x}(s,y)dy|$
$\displaystyle\leq\int\limits_{-1/2+\lambda_{1}(0)s}^{1/2+\lambda_{N}(0)s}|u_{x}(s,x)|dy$
$\displaystyle\leq\overline{r}(J(t)+V(t)(1+t(\lambda_{N}(0)-\lambda_{1}(0)))$
$\displaystyle\leq\varepsilon\overline{r}(c_{J}+c_{V}(1+\overline{T}(\lambda_{N}(0)-\lambda_{1}(0)))$
$\displaystyle=\varepsilon\frac{c_{M}}{2}$

yielding $M(T^{\prime})\leq\varepsilon\frac{c_{M}}{2}<\varepsilon
c_{M}<\delta$.

The estimates for $V(t)$ are the longest ones. We begin with an estimate of
$W^{out}_{p}(t)$: Let $(s,x)\in[0,t]\times\mathbb{R}$ with $(s,x)\not\in
R_{p}(t)$. Then for $z_{p}=z_{p}(s,x)$ and all $\sigma\in[0,t]$ we find

(3.13) $\displaystyle(\sigma,X_{p}(\sigma,z_{p}))\not\in R_{p}(t)$

because the $p$-th characteristic curves $C_{p}(y)$ may not cross for
different choices of $y\in\mathbb{R}$ since they are defined through solutions
of (2.6) with $i=p$. Furthermore, by (3.9) it holds

(3.14) $\displaystyle w_{p}(0,z_{p})=0.$

Integrating $L_{p}w_{p}$ along $C_{p}(z_{p})$ and using (2.7), (3.13) and
(3.14) yields

$\displaystyle|w_{p}(s,x)|$
$\displaystyle=|\int\limits_{0}^{s}\sum_{j,k}\gamma_{pjk}(u)w_{j}w_{k}+\varepsilon\kappa\sum_{k}G_{ik}(u)w_{k}d\sigma|$
$\displaystyle\leq
t\overline{\gamma}(V(t)+\varepsilon\kappa\overline{G})V(t),$

and therefore by $[0,t]\subset E_{1}$

(3.15) $\displaystyle
W^{out}_{p}(t)\leq\overline{T}(\overline{\gamma}c_{V}\varepsilon+\overline{G}\kappa)V(t).$

We turn to the estimate for $\tilde{V}(t)$. Let $i\neq p$ and
$(s,x)\in[0,t]\times\mathbb{R}$. For $z_{i}=z_{i}(s,x)$ define

$\displaystyle\omega_{i}(s,x):=\\{\sigma\in[0,t]|\;(\sigma,X_{i}(\sigma;z_{i}))\in
R_{p}(t)\\}.$

Then $\omega_{i}(s,x)$ is a (possibly empty) closed interval in $[0,t]$ and
the trace of

$\displaystyle\omega_{i}(s,x)\ni\sigma\mapsto(\sigma,X_{i}(\sigma;z_{i}))$

defines a smooth arc $\tau_{i}(s,x)$ in $[0,t]\times\mathbb{R}$ intersecting
the $p$-th characteristic curves transversally by the separation of
eigenvalues of $a$ (2.2). We have $w_{i}(0,z_{i})=0$ by (3.8) and integrating
the equation (2.7) for $L_{i}w_{i}$ along $C_{i}(z_{i})$ gives

$\displaystyle|w_{i}(s,x)|=|\int\limits_{0}^{s}\sum_{j,k}\gamma_{ijk}(u)w_{j}w_{k}+\varepsilon\kappa\sum_{k}G_{ik}(u)w_{k}d\sigma|.$

Using the important relations (2.8) for the coefficients $\gamma_{ijk}$ yields

(3.16)
$\displaystyle|w_{i}(s,x)|\leq(\overline{\gamma}V(t)+\varepsilon\kappa\overline{G})\left[tV(t)+\int_{0}^{t}|w_{p}(\sigma,X_{i}(\sigma;z_{i}))|d\sigma.\right]$

We need to estimate the integral of $|w_{p}|$ along $C_{i}(z_{i})$. To this
end we make use of Lemma 2.1 and (2.2):

(3.17) $\displaystyle\int_{0}^{t}|w_{p}(\sigma,X_{i}$
$\displaystyle(\sigma;z))|d\sigma$ $\displaystyle\leq$ $\displaystyle
W^{out}_{p}(t)t+\int\limits_{w_{i}(s,x)}|w_{p}|\frac{\lambda_{i}(u)-\lambda_{p}(u)}{\lambda_{i}(u)-\lambda_{p}(u)}d\sigma$
$\displaystyle\leq$ $\displaystyle
V(t)t+c_{\lambda}^{-1}\int\limits_{\tau_{i}(s,x)}|w_{p}(dx-\lambda_{p}(u)dt)|$
$\displaystyle\leq$ $\displaystyle V(t)t+c_{\lambda}^{-1}J(0)$
$\displaystyle+c_{\lambda}^{-1}\int\limits_{A_{p}(\tau_{i})}|\sum_{j,k}\Gamma_{pjk}(u)w_{j}w_{k}+\varepsilon\kappa\sum_{k}G_{ik}(u)w_{k}|dxdt$
$\displaystyle\leq$ $\displaystyle
V(t)t+c_{\lambda}^{-1}[c_{J}\varepsilon+t(\overline{\Gamma}V(t)+\varepsilon\kappa\overline{G})(V(t)S(t)+J(t))]$

where the relations (2.10) for $\Gamma_{pjk}$ were used in the last step.
Combining the estimates (3.15)-(3.17) we find a function
$Q=Q(\varepsilon,\kappa)$ given by

$\displaystyle Q(\varepsilon,\kappa)=$ $\displaystyle
3\overline{T}(\overline{\gamma}c_{V}\varepsilon+\overline{G}\kappa)+\overline{\gamma}\varepsilon
c_{\lambda}^{-1}[c_{J}+\overline{T}(\overline{\Gamma}c_{V}\varepsilon+\overline{G}\kappa)(c_{V}c_{S}\varepsilon+c_{J})]$
$\displaystyle+\overline{G}\kappa
c_{\lambda}^{-1}\overline{T}\varepsilon(\overline{\Gamma}(c_{V}c_{S}\varepsilon+c_{J})+\overline{G}c_{S}\kappa),$

and a constant $\overline{Q}:=Q(1,1)$ such that for all
$\varepsilon,\kappa\in(0,\nu]$ we have
$Q(\varepsilon,\kappa)\leq\overline{Q}\nu$ and

$\displaystyle V(t)$ $\displaystyle\leq
Q(\varepsilon,\kappa)V(t)+\kappa\overline{G}c_{\lambda}^{-1}c_{J}(1+\kappa\overline{G}\,\overline{T})\varepsilon^{2}$
$\displaystyle\leq\overline{Q}\nu V(t)+\frac{c_{V}}{2}\varepsilon^{2}.$

If $\nu$ satisfies

(3.18) $\displaystyle 1-\nu\overline{Q}\leq\frac{3}{4}$

then

$\displaystyle V(t)\leq\frac{2}{3}c_{V}\varepsilon^{2}<c_{V}\varepsilon^{2}.$

Hence $T^{\prime}\in E_{1}$ follows if $\nu$ satisfies the conditions (3.6),
(3.10), (3.11), (3.12) and (3.18). ∎

As a first application of Lemma 3.2 we prove that any $C^{1}$-solution of
(3.1) on $[0,T]$ must be a $C^{2}$-solution of (3.1) on $[0,T]$ if $T$ is
smaller than a certain $\varepsilon$-depended bound.

######  Lemma 3.4.

Let $\overline{T}\in(0,\infty)$ and choose $\nu=\nu(\overline{T})$ such that
the conclusions of Lemma 3.2 hold. Let $\varepsilon,\kappa\in[0,\nu]$. If
$0<T\leq\overline{T}\varepsilon^{-1}$ and $u\in C^{1}([0,T]\times\mathbb{R})$
solves (3.1) then $u\in C^{2}([0,T]\times\mathbb{R})$.

###### Proof.

Let $\varepsilon,\kappa\in[0,\nu]$, $T\in(0,\overline{T}\varepsilon^{-1}]$ and
suppose $u\in C^{1}([0,T]\times\mathbb{R})$ solves (3.1). By Lemma 2.2 we have
$u\in C^{1}_{c}([0,T]\times\mathbb{R})$ and there is a constant $c_{u_{x}}>0$
such that for all $(t,x)\in[0,T]\times\mathbb{R}$

$\displaystyle|u_{x}(t,x)|\leq c_{u_{x}}.$

We argue by continuous induction. Set

$\displaystyle E_{3}:=\\{T^{\prime}\in[0,T]|\;u\in
C^{2}([0,T^{\prime}]\times\mathbb{R})\\}.$

We need to show that $E_{3}$ is non-empty, relatively open and closed. By
Lemma 2.3 there is a $C^{2}$-solution on $[0,T^{\prime}]$ of (3.1) for some
$T^{\prime}>0$ since $u^{0\varepsilon}\in C^{2}_{c}(\mathbb{R})$ and
$||u^{0\varepsilon}||_{\infty}<\varepsilon c_{M}<\delta$ where $c_{M}$ is
chosen like in Lemma 3.2. By Lemma 2.2 this solution has to be equal to $u$ on
$[0,T^{\prime}]$, i.e. $T^{\prime}\in E_{3}$.

Choose $\tilde{\nu}>\nu$ with $\tilde{\nu}c_{M}<\delta$. Let $\Delta t=\Delta
t(\tilde{\nu}c_{M},c_{u_{x}})>0$ be a time of existence for a $C^{2}$-solution
of

(3.19) $\displaystyle u_{t}+a(u)u_{x}=\varepsilon\kappa g(u)$

with initial data satisfying appropriate bounds as given by Lemma 2.3. Let
$T^{\prime}\in E_{3}$. Because $u(T^{\prime},\cdot)\in
C^{2}_{c}(\mathbb{R}),||u(T^{\prime},\cdot)||_{\infty}<\varepsilon c_{M}$ and
$||u_{x}(T^{\prime},\cdot)||_{\infty}\leq c_{u_{x}}$ there is a solution
$\tilde{u}\in C^{2}([T^{\prime},T^{\prime}+\Delta t]\times\mathbb{R})$ of
(3.19) with $\tilde{u}(T^{\prime},x)=u(T^{\prime},x)$ for $x\in\mathbb{R}$.
Uniqueness again yields $u\equiv\tilde{u}$ on $[T^{\prime},T^{\prime}+\Delta
t]\cap[T^{\prime},T]$. We conclude that $E_{3}$ is open in $[0,T]$.

Let $T^{\prime}\in[0,T]$. We show that if $[0,T^{\prime})\subset E_{3}$ than
$T^{\prime}\in E_{3}$. This implies the closedness of $E_{3}$. Because
$E_{3}\not=\emptyset$ the case $T^{\prime}=0$ follows immediately. Therefore
suppose $T^{\prime}>0$ and $[0,T^{\prime})\subset E_{3}$. Then $u\in
C^{2}([0,T^{\prime})\times\mathbb{R})$. Set
$\tilde{t}:=T^{\prime}-\frac{\min\\{T^{\prime},\Delta t\\}}{2}$. By
$T^{\prime}\leq T\leq\overline{T}\varepsilon^{-1}$, Lemma 3.2 and continuity
of $u$ on $[0,T]$ we find for all $(t,x)\in[0,T^{\prime}]\times\mathbb{R}$
that

$\displaystyle|u(t,x)|\leq\nu c_{M}<\tilde{\nu}c_{M}<\delta.$

Because $|u_{x}(\tilde{t},x)|\leq c_{u_{x}}$, too, there is a $C^{2}$-solution
of (3.19) on $[\tilde{t},\tilde{t}+\Delta t]$ with initial data
$u(\tilde{t},\cdot)$. By $\tilde{t}<T^{\prime}<\tilde{t}+\Delta t$ we find
$u\in C^{2}$ on $[0,T^{\prime}]$, i.e. $T^{\prime}\in E_{3}$. ∎

##  4 The gradient blow-up

Set

$\displaystyle\overline{T}:=\frac{4}{\gamma_{ppp}(0)\max\alpha^{\prime}}.$

We are now ready to prove the key finding of this paper:

######  Proposition 4.1.

There exist $\nu\in(0,1]$ such that if for $\varepsilon,\kappa\in(0,\nu]$ and
$T>0$ a function $u\in C^{2}([0,T]\times\mathbb{R})$ solves (3.1) with
$u(0,x)=u^{0\varepsilon}(x)$ then $T$ must satisfy

(4.1) $\displaystyle
T<T_{\varepsilon}:=\frac{3}{4}\overline{T}\varepsilon^{-1}.$

###### Proof.

Let $z\in\mathbb{R}$ such that
$\alpha^{\prime}(z)=\max\limits_{x}\alpha^{\prime}$ and let
$\varepsilon,\kappa\in(0,\nu]$ for $\nu=\nu(\overline{T})$ like in Lemma 3.2.
Suppose $u\in C^{2}([0,T_{\varepsilon}]\times\mathbb{R})$ solves (3.1). Then
the statement of Lemma 3.2 applies to $u$ since
$T_{\varepsilon}\leq\overline{T}\varepsilon^{-1}$. For
$t\in[0,T_{\varepsilon}]$ define

$\displaystyle W(t):=w_{p}(t,X_{p}(t;z)).$

Then $W(0)=\varepsilon\alpha^{\prime}(z)$ and $W$ satisfies (2.7):

$\displaystyle
W^{\prime}=\sum_{j,k}\gamma_{pjk}(u)w_{j}w_{k}+\varepsilon\kappa\sum_{k}G_{ik}(u)w_{k}.$

Set

$\displaystyle c_{W}:=2\frac{c_{V}}{\alpha^{\prime}(z)}.$

Let $\nu$ be so small such that for all $\varepsilon\in(0,\nu]$ and for all
$(t,x)\in[0,T_{\varepsilon}]\times\mathbb{R}$

(4.2) $\displaystyle\gamma_{ppp}(u(t,x))>\frac{1}{2}\gamma_{ppp}(0)$

which is possible by $|u(t,x)|<c_{M}\varepsilon$ (see (3.3)). We find

$\displaystyle
W^{\prime}>\frac{1}{2}\gamma_{ppp}(0)W^{2}-\overline{\gamma}(V^{2}+V|W|)-\varepsilon\kappa\overline{G}(V+|W|).$

We claim that for $\nu$ small enough the relations

(4.3) $\displaystyle W(t)$ $\displaystyle>\frac{W(0)}{2}>0$ (4.4)
$\displaystyle V(t)$ $\displaystyle<\varepsilon c_{W}W(t)$

hold for all $t\in[0,T_{\varepsilon}]$. Like in the proof of Lemma 3.2 we
proceed by continuous induction. Set

$\displaystyle
E_{2}:=\\{t\in[0,T_{\varepsilon}]|\;\textnormal{\eqref{lowerboundW} and
\eqref{upperboundV} hold on}\;[0,t]\\}.$

Again $E_{2}$ will be non-empty, open and closed in $[0,T_{\varepsilon}]$.
Since

$\displaystyle W(0)$
$\displaystyle=\varepsilon\alpha^{\prime}(z)>\frac{W(0)}{2}>0,$ $\displaystyle
V(0)$ $\displaystyle=0<\varepsilon\frac{c_{W}}{2}W(0)<\varepsilon c_{W}W(0)$

we find by continuity of $W$ and $V$ a $t_{2}>0$ with $[0,t_{2}]\subset
E_{2}$.

Let $t\in E_{2}\backslash\\{0\\}$. We show that if $\varepsilon$ and $\kappa$
are small enough then for all $s\in[0,t]$ the stronger inequalities

(4.5) $\displaystyle W(s)$ $\displaystyle\geq W(0)$ (4.6) $\displaystyle V(s)$
$\displaystyle\leq\varepsilon\frac{c_{W}}{2}W(s)$

hold. By continuity this implies that $E_{2}$ is open in
$[0,T_{\varepsilon}]$, and by the procedure in the proof of Lemma 3.2 it also
implies its closedness in $[0,T_{\varepsilon}]$. For $s\in[0,t]$ (4.4) gives

$\displaystyle
W^{\prime}(s)>\left(\frac{1}{2}\gamma_{ppp}(0)-\overline{\gamma}c_{W}\varepsilon(1+c_{W}\varepsilon)\right)W(s)^{2}-\varepsilon\kappa\overline{G}(1+c_{W}\varepsilon)W(s).$

If we choose $\nu$ so small that

(4.7) $\displaystyle\frac{1}{2}\gamma_{ppp}(0)-2\overline{\gamma}c_{W}\nu$
$\displaystyle>\frac{3}{8}\gamma_{ppp}(0),$ (4.8) $\displaystyle\nu c_{W}+1$
$\displaystyle<2$

then

(4.9) $\displaystyle
W^{\prime}(s)>\frac{3}{8}\gamma_{ppp}(0)W(s)^{2}-2\varepsilon\kappa\overline{G}W(s).$

If $\nu$ satisfies

(4.10)
$\displaystyle\frac{3}{16}\gamma_{ppp}(0)\alpha^{\prime}(z)-2\nu\overline{G}>\frac{1}{8}\gamma_{ppp}(0)\alpha^{\prime}(z)$

then we obtain by (4.3)

$\displaystyle W^{\prime}(s)$
$\displaystyle>(\frac{3}{16}\gamma_{ppp}(0)\alpha^{\prime}(z)-2\kappa\overline{G})\varepsilon
W(s)$ $\displaystyle>\frac{1}{8}\gamma_{ppp}(0)\alpha^{\prime}(z)\varepsilon
W(s)$ $\displaystyle>0.$

Hence $W$ increases on $[0,t]$ and $W(s)\geq W(0)$ holds for all $s\in[0,t]$.
Furthermore, by (3.5) we find for all $s\in[0,t]$

$\displaystyle
V(s)<c_{V}\varepsilon^{2}=\frac{c_{V}}{\alpha^{\prime}(z)}\varepsilon
W(0)\leq\frac{c_{V}}{\alpha^{\prime}(z)}\varepsilon
W(s)=\frac{c_{W}}{2}\varepsilon W(s)$

which concludes the proof of the inequalities (4.5) and (4.6) if $\nu$
satisfies the conditions (4.7), (4.8) and (4.10).

Finally let $y$ be the solution of

(4.11) $\displaystyle
y^{\prime}=\frac{3}{8}\gamma_{ppp}(0)y^{2}-2\varepsilon\kappa\overline{G}y,\;y(0)=W(0).$

Then by Gronwall’s Lemma and (4.9) we have

$\displaystyle y(s)\leq W(s)$

as long as $y$ and $W$ exist. Solving (4.11) explicitly and using (4.10) we
see that the lifespan of $y$ is given by

$\displaystyle T_{max}(\varepsilon,\kappa)$
$\displaystyle=-\frac{1}{2\varepsilon\kappa\overline{G}}\ln\left(\frac{-2\kappa\overline{G}}{\frac{3}{8}\gamma_{ppp}(0)\alpha^{\prime}(z)}+1\right)$
$\displaystyle\leq\varepsilon^{-1}\left(\frac{8}{3}\frac{1}{\gamma_{ppp}(0)\alpha^{\prime}(z)}+c\kappa\right)$

where the constant $c>0$ may be chosen uniformly for all
$\kappa,\varepsilon\in(0,\nu]$. If $\nu$ is so small that

(4.12)
$\displaystyle\frac{8}{3}\frac{1}{\gamma_{ppp}(0)\alpha^{\prime}(z)}+c\nu<\frac{3}{\gamma_{ppp}(0)\alpha^{\prime}(z)}=\frac{3}{4}\overline{T}$

then $T_{max}(\varepsilon,\kappa)<T_{\varepsilon}$ and $W$ cannot be continued
as a differentiable function on $[0,T_{\varepsilon}]$. ∎

The obvious scaling

$\displaystyle(t,x)\mapsto((\varepsilon\kappa)^{-1}t,(\varepsilon\kappa)^{-1}x)$

yields

######  Corollary 4.2.

There exist $\nu$ such that for all $\varepsilon,\kappa\in(0,\nu]$ the maximal
time of existence $T^{\ast}>0$ for the unique solution $u\in
C^{1}([0,T^{\ast})\times\mathbb{R})$ of the Cauchy problem

(4.13) $\displaystyle\left\\{\begin{aligned} u_{t}+a(u)u_{x}&=g(u),\\\
u(0,x)&=u^{0\varepsilon}((\varepsilon\kappa)^{-1}x)\end{aligned}\right.$

is finite. The solution $u$ satisfies

(4.14) $\displaystyle|u(t,x)|<\delta\;\text{for
all}\;(t,x)\in[0,T^{\ast})\times\mathbb{R}$

and $T^{\ast}$ is bounded by

$\displaystyle T^{\ast}<\overline{T}\kappa.$

###### Proof.

Choose $\nu\in(0,1]$ so small that the statements of Lemma 3.2 and Proposition
4.1 hold. By Lemma 2.3 and $||u^{0\varepsilon}||_{\infty}<\varepsilon
c_{M}<\delta$ the set

$\displaystyle E_{4}:=\\{T\in[0,\overline{T}\kappa)|\;\exists\,u\in
C^{1}([0,T]\times\mathbb{R}):\;u\;\textnormal{solves}\;\eqref{CP2}\\}$

is non-empty, in particular there is $T^{\prime}>0$ such that
$[0,T^{\prime}]\subset E_{4}$. Let $T\in E_{4}\backslash\\{0\\}$. Then $u\in
C^{1}([0,T]\times\mathbb{R})$ and $0<T\leq\overline{T}\kappa$. We find $u\in
C^{2}([0,T]\times\mathbb{R})$ by Lemma 3.4 and $|u(t,x)|<\varepsilon
c_{M}<\delta$ for all $(t,x)\in[0,T]\times\mathbb{R}$ by Lemma 3.2. Applying
Lemma 2.3 there is a $\Delta t>0$ such that $u$ can be extend as a
$C^{2}$-solution of (4.13) onto $[0,T+\Delta t]$. We deduce that $E_{4}$ is
open and of the form $E_{4}=[0,T^{\ast})$ for some
$T^{\ast}\in(0,\overline{T}\kappa]$. In summary: The unique $C^{1}$-solution
$u$ on $[0,T^{\ast})$ of (4.13) is in fact a $C^{2}$-solution on
$[0,T^{\ast})$ and satisfies $|u(t,x)|<\delta$ for all
$(t,x)\in[0,T^{\ast})\times\mathbb{R}$. Finally, Proposition 4.1 yields
$T^{\ast}\leq\frac{3}{4}\overline{T}\kappa<\overline{T}\kappa$. ∎

Theorem 1.1 is an immediate consequence.

######  Remark 4.3.

Note that these data are in general not small in $C^{1}$: The first derivative
of the data in Corollary 4.2 has its supremum bounded from below by

$\displaystyle\kappa^{-1}\max_{x}\alpha^{\prime}\min_{|u|\leq\delta}|r_{p}(u)|>0.$

Acknowledgements: We want to thank H. Freistühler for proposing this problem
and making helpful suggestions on how to approach it. During the research for
this paper the author has been supported by Deutsche Forschungsgemeinschaft
under Grant No. FR822/10-1.

## References

  * [BHN07] S. Bianchini, B. Hanouzet, and R. Natalini.  Asymptotic behavior of smooth solutions for partially dissipative hyperbolic systems with a convex entropy.  Comm. Pure Appl. Math., 60(11):1559–1622, 2007.
  * [BZ11] K. Beauchard and E. Zuazua.  Large time asymptotics for partially dissipative hyperbolic systems.  Arch. Ration. Mech. Anal., 199(1):177–227, 2011.
  * [Bä22] J. Bärlin.  Blow-up of solutions to relaxed compressible Navier-Stokes equations in divergence form.  arXiv:2202.05634, 2022.
  * [Fre22] H. Freistühler.  Time-asymptotic stability of first-order symmetric hyperbolic systems of balance laws in dissipative compressible fluid dynamics.  published electronically in Quart. Appl. Math., 2022.
  * [Hör87] L. Hörmander.  The lifespan of classical solutions of nonlinear hyperbolic equations.  In Pseudodifferential operators (Oberwolfach, 1986), volume 1256 of Lecture Notes in Math., pages 214–280. Springer, Berlin, 1987.
  * [HRW22] Y. Hu, R. Racke, and N. Wang.  Formation of singularities for one-dimensional relaxed compressible Navier-Stokes equations.  Konstanzer Schriften in Mathematik KOPS, 2022.
  * [HW19] Y. Hu and N. Wang.  Global existence versus blow-up results for one dimensional compressible Navier-Stokes equations with Maxwell’s law.  Math. Nachr., 292(4):826–840, 2019.
  * [Joh74] F. John.  Formation of singularities in one-dimensional nonlinear wave propagation.  Comm. Pure Appl. Math., 27:377–405, 1974.
  * [KY04] S. Kawashima and W.-A. Yong.  Dissipative structure and entropy for hyperbolic systems of balance laws.  Arch. Ration. Mech. Anal., 174(3):345–364, 2004.
  * [Lax64] P. D. Lax.  Development of singularities of solutions of nonlinear hyperbolic partial differential equations.  J. Mathematical Phys., 5:611–613, 1964.
  * [Lax73] P. D. Lax.  Hyperbolic systems of conservation laws and the mathematical theory of shock waves.  Conference Board of the Mathematical Sciences Regional Conference Series in Applied Mathematics, No. 11. Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1973.
  * [Liu79] T.-P. Liu.  Development of singularities in the nonlinear waves for quasilinear hyperbolic partial differential equations.  J. Differential Equations, 33(1):92–111, 1979.
  * [LL09] T. Li and H. Liu.  Critical thresholds in hyperbolic relaxation systems.  J. Differential Equations, 247(1):33–48, 2009.
  * [MZ02] C. Mascia and K. Zumbrun.  Pointwise Green’s function bounds and stability of relaxation shocks.  Indiana Univ. Math. J., 51(4):773–904, 2002.
  * [Rau12] J. Rauch.  Hyperbolic partial differential equations and geometric optics, volume 133 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2012.
  * [Rug04] T. Ruggeri.  Entropy principle and relativistic extended thermodynamics: global existence of smooth solutions and stability of equilibrium state.  Nuovo Cimento Soc. Ital. Fis. B, 119(7-9):809–821, 2004.
  * [Yon04] W.-A. Yong.  Entropy and global existence for hyperbolic balance laws.  Arch. Ration. Mech. Anal., 172(2):247–266, 2004.
  * [Zen99] Y. Zeng.  Gas dynamics in thermal nonequilibrium and general hyperbolic systems with relaxation.  Arch. Ration. Mech. Anal., 150(3):225–279, 1999.