is closely related to the regrowth rate $b$, but not very sensitive to the
tumour size at relapse $N$, depending on it only logarithmically. That
equation (4.3) should be a decent predictor of the actually observed relapse
time is not especially surprising from a mathematical perspective, but bears
mentioning as the clinicians on the study found this to be practically useful.

Although the clinicians who participated in the study found the multiple
exponential model’s measurement of the regrowth rate $b$ very useful, the
applied mathematicians and biophysicists were more interested in the inferred
fraction of resistant cells, $f_{R}$. Since one of the motivations for this
combination was to minimise the likelihood of cross-resistance, the inferred
fraction of resistant cells is an indicator of the proportion of cells that
are cross-resistant at the start of therapy, and measurement of $f_{R}$ can
provide a stringent test of the working hypothesis that cross-resistance
arises from purely evolutionary means. That is, it is acquired by novel
genetic mutations and requires several distinct genetic mutations (to the
different pathways relevant to the distinct mechanisms of action of each
drug).

Figure 4.4:  A plot of the inferred fractions of resistant cells for each
patient. Only those datasets for which $f_{R}$ was well-defined were plotted.
Fits which failed our test for over-interpretation are represented by red
points, fits that passed are represented with black points. Note the
logarithmic scale: the range of observed values spans several orders of
magnitude.

The inferred fraction of resistant cells $f_{R}$ varies substantially between
patients (see figure 4.4), but in all cases was many orders of magnitude
higher than theoretically expected. The lowest value observed was $3.4\times
10^{-7}$ (patient 25, see figure 4.4, and 4.3), while the highest values were
$1$ (i.e. all cells seemed to be resistant, patients 12, 25 and 26), although
we should point out that for many of these particularly high values, the
multiple exponential model fails our test for over-interpretation. The highest
value of $f_{R}$ for which the multiple exponential model was considered
meaningful was $7.9\times 10^{-2}$ (patient 11, see figure 4.2), which is
still many orders of magnitude higher than was theoretically expected. Median
values of $f_{R}$ and $b$ were $2.98\times 10^{-3}$ and $1.44\times
10^{-2}\;\mathrm{day}^{-1}$ respectively. If we restrict this analysis to the
datasets for which the multiple exponential model did not fail our test for
over-interpretation of noise, we instead find $3.99\times 10^{-4}$ and
$2.46\times 10^{-3}\;\mathrm{day}^{-1}$.

Other research on multi-drug resistance also estimates $f_{R}$ to be much
higher than what one would expect on the basis of the above working
hypothesis, in the range $5\times 10^{-5}$ to $3\times 10^{-4}$, consistent
with our inferences from the best-fit model parameters above [123]. However,
it is important to note that this study analysed resistance to two drugs only,
erlotinib and crizotinib, two protein kinase inhibitors which have very
different mechanisms of action to any in the combination studied here. In
fact, these drugs target specific signalling proteins, whereas the combination
chemotherapy analysed here is much less selective.

As $f_{R}$ was clearly not unmeasurably small, and the disease recurred in a
resistant form in the majority of cases, it must be the case that at least one
of the postulates underlying the working hypothesis behind the therapy is
wrong. Either there _is_ in fact a mutation which can confer resistance to all
four drugs simultaneously, the relevant single-drug resistance mutations are
not selectively neutral prior to therapy, or cells can become resistant
without having acquired genetic mutations, or some combination of the above.
We shall explore each of this possibilities in turn.

####  4.3.2 Molecular mechanisms of single-drug resistance

Before considering possible mechanisms of multi-drug resistance that can arise
from a single mutation, let’s review some of what is known about mechanisms of
single-drug resistance, as it is a simpler case which can inform and constrain
our discussion of the possible mechanisms of cross-resistance. As cisplatin
resistance is very common when used in isolation [113], and cisplatin is the
best studied of the drugs in the combination, we will focus primarily on the
mechanisms of action and transport into and out of the cell.

Cisplatin’s primary mechanism of action as an anticancer agent is by damaging
DNA. This triggers a DNA damage response in the cell’s signalling pathways,
inducing apoptosis (programmed cell death) [113]. Before any damage can be
done by cisplatin’s reaction with the DNA itself, it must be present in the
nucleus of the cell [114]. It is also only activated by a reaction with the
cytoplasm [114]. It therefore has to have been transported into the cell
sufficiently quickly (and out sufficiently slowly) that it has an appreciable
concentration inside the cell [115]. Examples of uptake and efflux pathways
are via copper transporter 1 (CTR1) and MRP2, one of the ATP-binding cassette
(“ABC”) transporters [113, 115]. Resistance to cisplatin can therefore consist
of a reduced response to DNA damage, decreased activation of the cisplatin
complex by aquation, and lower concentrations of cisplatin inside the cell by
modified uptake and efflux [113, 115].

Changes in efflux mediated by the ABC transporters like MRP2 have been studied
for some time, due to the potential importance of these transporters as
markers for responsiveness to therapy and as potential targets of new drugs
[124]. At one time, they were even thought to be almost exclusively
responsible for the emergence of multi-drug resistance [125]. However,
although inhibitors of ABC transporters do reduce chemoresistance to a degree,
they do not have a very strong affect with regards to restoring cells’
sensitivity to cisplatin. As a result, it is suspected that other factors must
be involved in the development of cisplatin resistance. Either other efflux
pumps insensitive to the inhibitors tested, or changes in uptake and action in
the cell [126].

Evidence for CTR1’s role in cisplatin uptake seems more straightforward, and
includes:

  * •

Mice in which the transmembrane pump CTR1 has been knocked out are much more
resistant to the cytotoxic effects of cisplatin [127].

  * •

Cells with higher than normal copper concentrations (copper shares an uptake
pathway with cisplatin, CTR1) are more resistant to cisplatin [128].

  * •

Cells with lowered copper concentrations are more sensitive to cisplatin
[129].

All of which seems to indicate that CTR1 transports cisplatin into the cell,
and less cisplatin is transported when CTR1 is absent or busy.

Finally, changes in signal transduction pathways could provide a way for
cancer cells to continue to survive and divide even in the presence of high
concentrations of cisplatin. Out of a preponderance of partially understood
mechanisms, the ability of cells to divide in the presence of DNA damage by
inhibiting apoptosis [113] and the ability of all cells to break down and
recycle individual damaged components, autophagy, bear particular mention
[130]. A mutation in one of the protein kinases that triggers apoptosis
(programmed cell death) could plausibly result in a line of cancer cells which
doggedly divide even with cisplatin-damaged DNA, although we should note that
this mechanism of resistance is specific to cisplatin’s mode of action.
Autophagy, on the other hand, is a non-specific response to stress that is
latent even in normal cells, and though its relevance to cisplatin resistance
is not well understood, there are results which indicate that there is an
inverse relationship between cisplatin resistance and the inhibition of
autophagy [113, 130].

To summarise, proposed mechanisms that may contribute to cisplatin resistance
include increased efflux and cisplatin removal from the cell, decreased uptake
of cisplatin into the cell, and weakened cellular response to DNA damage and
toxicity.

####  4.3.3 Possible mechanisms of cross-resistance

As this is the first time that this specific combination has been tested
clinically, and consequently the first time that cross-resistance to the four
agents involved has been observed, the mechanism behind this resistance is
basically unknown and as a result we can at present only speculate as to its
true nature. On the basis of the stochastic theory of Antal, Bozič and others,
the cross-resistance is extremely unlikely to be due to cells’ acquiring
multiple independent mutations by virtue of the heterogeneity of the drugs’
mechanisms of action [105, 121]. however, the anomalously high fractions of
resistant cells $f_{R}$ can be explained in principle by there being many
different mutations which can provide resistance to individual drugs, with
$n_{i}$ on the order of $10^{4}$. Given present uncertainties about the
mechanism of action of several of these drugs, this possibility cannot be
conclusively ruled out at this time.

Besides invoking such high values of $n_{i}$, the alternatives to the working
hypotheses underlying this prediction can be tentatively sorted into two
groups: mechanisms which involve cross-resistance being _acquired_ by one (or
very few) novel mutation, and mechanisms in which a sub-population of cells in
which a latent _intrinsic_ resistance is activated without requiring new
genetic alterations as such. The heterogeneity in structure, transport
pathways, and mechanisms of action between the drugs in the combination makes
it unlikely that a mutation affecting one transport protein, or indeed any one
of the specific mechanisms or cellular responses to each drug will result in
resistance to others in the combination. A mutation that allows cells to avoid
apoptosis triggered by cisplatin’s damage of cellular DNA seems unlikely to
have any relevance to the formation of microtubules blocked by docetaxel, for
example. This presents a difficult puzzle to attempts to explain the observed
frequencies of cross-resistance in terms of either acquired single mutations
or intrinsic cellular responses. We will first discuss possible mechanisms of
_acquired_ cross-resistance (caused by mutations), and then discuss different
mechanisms of _intrinsic_ cross-resistance (not caused by mutations as such).

######  4.3.3.0.1 Acquired resistance

One possibility for cross-resistance to be acquired by a single mutation is if
there were a protein kinase that interacted with every drug’s uptake and
efflux pumps, perhaps downregulating the uptake pumps and upregulating the
efflux pumps, acting as part of a signal transduction pathway that is
activated during a relatively non-specific cellular response to toxicity and
stress. When this protein kinase was activated by another above it in the
pathway, the effect of its simultaneously closing many intake transporters and
opening many efflux transporters would be a kind of emergency evacuation of
cytotoxins from the cell, as though an alarm had been sounded. A mutation
which caused this kinase to take on its active conformation all the time would
lead to broad changes in membrane transport, which would be consistent with
cross-resistance. This hypothetical “alarm kinase”, if it exists at all, may
be some undiscovered molecule yet to be characterised, or may simply be a
hitherto obscure function of a protein that has already been partially
characterised in the literature. In either case, there are some simple
criteria that this protein kinase would have to meet:

  * •

It should be sensitive to cytotoxic stress on the cell (possibly associated
with inflammation, autophagy or the heat shock response)

  * •

It should interact with many different pump and transporter proteins or should
be “upstream” of them in many distinct signalling pathways

  * •

The mutated protein should lose the specificity to stress but interact with
transport proteins similarly

The existence of such an alarm kinase could provide one mechanism for cells to
acquire broad cross-resistance with a single mutation. This single mutation
would plausibly be neutral in the absence of combination chemotherapy, as
there would be no selective advantage associated with excluding high
concentrations of cytotoxins in this case. We should emphasise, nonetheless,
that this is speculative. A single neutral mutation could arise through chance
as in the branching process theory developed by Antal et al. detailed above in
section 4.2.2, or else could arise as a genetic hitch-hiker [121].

While we are not aware of any one protein kinase that definitely satisfies all
of the above criteria, after surveying the literature the best educated guess
as to the identity of this alarm kinase that we were not able to conclusively
rule out was JNK1 (also known as MAPK8). JNK1 is a signalling protein which is
associated with stress and inflammation, interacts with several distinct
signalling pathways, and there are results suggesting that activation of JNK1
is associated with drug resistance and conversely that inhibition of JNK1 is
associated with reversal of resistance [131, 132]. Furthermore, JNK inhibition
also results in P-glycoprotein (or MDR1), an important efflux pump, being
downregulated, which sensitizes some lines of cancer cells to cisplatin, one
of the drugs in the combination [133]. However, these results should be
interpreted cautiously, as there is at least one contrary experimental result
in the literature, and it may be the case that the specific cancers and cell
lines studied are not representative of the specific type of cancer in our own
study [134]. We are also not aware of any results regarding common mutated
forms of JNK1, in particular whether or not mutants are permanently in the
“active” conformation: continual failure to identify any single mutant protein
kinase associated with cross-resistance would strongly suggest that the alarm
kinase hypothesis was false.

While there are other conceivable ways that multi-drug responses can arise
without such an alarm kinase, it does provide a simple explanation for the
non-specific (in that several very different drugs are involved) but unified
(in that they are all cytotoxic and resisted by the cell _somehow_) response
observed in this study.

Alternatively, it may be the case that several distinct mutations are indeed
required, but for some unknown reason are not neutral before the therapy is
applied. This would throw out the framework in section 4.2.2 and fractions of
resistant cells may be much higher, perhaps approaching fixation (that is,
$f_{R}\approx 1$). While it seems unlikely to us at first glance that
alterations in the specific mechanisms of uptake, efflux and the targets of
four specific drugs should also have some adaptive selective advantage in the
absence of these drugs, enough is unknown about them that this cannot be
conclusively ruled out — for example, modified efflux pump activity could be a
side-effect of an advantageous mutation controlling proliferation via some
complex gene-gene or protein-protein interactions. Furthermore, this
explanation does not need hypothetical uncharacterised functions of protein
kinases to be invoked.

Either hypothesis - that resistance is acquired through the mutation of a
single alarm kinase, or several independent drivers - would be conclusively
falsified by demonstrating that cross-resistance could be induced in a line of
cancer (or indeed normal) cells without any additional mutations. This would
indicate that cross-resistance was an intrinsic response, rather than
acquired.

######  4.3.3.0.2 Intrinsic resistance

It may also be the case that resistance to several drugs at once can be
induced in otherwise genetically normal cells, or simply that the drugs fail
to have an effect for reasons unrelated to genetic alterations. This class of
possible mechanisms attempt to explain the anomalously high resistant
fractions in terms of intrinsic resistance. Cells resist the effect of the
drug combination without inheriting the ability to do so as such, due to
differences in regulation of normal genes or in their microenvironment.

Perhaps the simplest way in which this kind of apparent “resistance” can come
about is by poor vascularization. If there is very poor penetration of the
tumour by capillaries, drugs present in the bloodstream will find it difficult
to reach high concentrations in the tumour cells by diffusion from the
bloodstream alone. Poor vascularization, and the associated depletion of
oxygen around these areas of the tumour, is known to be a factor in multi-drug
resistance, but may be mediated by more complex cellular responses (e.g.
involving ABC transporters) rather than the simple fact that less agent will
be present [125].

Another way that cells could develop resistance to the combination of drugs is
if there were a latent response to exclude cytotoxins from the cell by
altering membrane transport, and this latent response was activated by signals
from other cells. This generic response to cytotoxicity could possibly be
triggered by the activation of an “alarm kinase”, but the possibility of this
being controlled by a less centralised pathway cannot be ruled out. This class
of mechanisms could work in concert with acquired resistance. The effective
number of resistant cells can be amplified substantially, and one resistant
cell could “shield” a number of other sensitive cells from the effects of the
therapy by activating a latent intrinsic response.

It would be desirable to make some quantitative predictions as to how many
sensitive cells could be shielded by one resistant cell by such a mechanism.
The observed $f_{R}$ of around $10^{-4}$ would then be determined by the
product of the underlying tiny core population of truly resistant cells
$f_{R}^{\star}$ and this shielding ratio, $S$. The tiny resistant core
$f_{R}^{\star}$ could take on some small value consistent with T. Antal and I.
Bozič’s theory based on branching processes, say $f_{R}^{\star}$ in the range
$10^{-14}-10^{-8}$, and since

$f_{R}=f_{R}^{\star}S\;,$ (4.10)

then values of $S$, the number of sensitive cells shielded by one cell in the
resistant core population, would then have to be at least $10^{4}$ or larger
to account for clinical observations. To understand whether or not this is an
achievable value of $S$, we will have to look at more explicit models of
signalling mechanisms.

First, consider the case that this latent resistance is activated by the
diffusion of a small molecule such as a cytokine. The molecule is produced by
the core resistant population, diffuses through the surrounding sensitive
cells, triggering their latent intrinsic resistance program, and gradually
breaks down over time (see figure 4.5 for an illustration). If this molecule
is only produced by core resistant cells, is not transported actively, having
a diffusion coefficient $D_{c}$, and has a degradation rate $\lambda$, then
its steady-state concentration in the tumour $\rho_{c}$ obeys the simple
differential equation

$D_{c}\Delta\rho_{c}-\lambda_{c}\rho_{c}=0$ (4.11)

outside the core population of cells from which it is released. While one can
explicitly solve this equation analytically in a few cases (such as one
dimension, spherical symmetry, _et cetera_), we won’t reproduce exact
solutions here. Instead, we will be satisfied to observe that solutions of
equation (4.11) have a characteristic length scale $L_{c}$

$L_{c}=\sqrt{\frac{D_{c}}{\lambda_{c}}}$ (4.12)

which can be interpreted as the effective distance that the signalling
molecule can travel before breaking down. A single resistant cell can then
shield sensitive cells in a volume on the order of $L_{c}^{3}$, and so if a
typical cell has size $d_{\mathrm{cell}}=10\;\mu\mathrm{m}$, the shielding
ratio $S$ will be

$S=\left(\frac{L_{c}}{d_{\mathrm{cell}}}\right)^{3}\;.$ (4.13)

Many cytokines have diffusion coefficients on the order of
$10^{-6}\;\mathrm{cm}^{2}\mathrm{s}^{-1}$, and degradation rates on the order
of $10^{-3}\;\mathrm{s}^{-1}$, which correspond to $L_{c}\approx
300\;\mu\mathrm{m}$ [135, 136]. Via equation (4.13), given a cell size of
around $10\;\mu\mathrm{m}$, this corresponds to a shielding ratio of $S\approx
3\times 10^{4}$, the correct order of magnitude for this to be a viable
explanation. While far more research would have to be done to exclude other
explanations, this simple argument shows that shielding of sensitive cells by
resistant cells is not ruled out by what is currently known about the dynamics
of cell signalling.

The hypothesis that cytokine signalling could result in cross-resistance,
which is at first glance compatible with current experimental knowledge, could
be ruled out by demonstrating the presence of cross-resistance in the absence
of signalling by cytokines or other small molecules, perhaps with a knock-out
or inhibition experiment (on mice) [137].

Figure 4.5: A diagram showing one possible mechanism by which the apparent
number of resistant cells can be much larger than the true number of
underlying resistant mutants. Resistant mutants “shield” sensitive cells by
producing a small signalling molecule (represented by blue haze), which
triggers sensitive cells to alter their transmembrane pump activity in
response and slow their uptake of the cytotoxin diffusing across the tumour
from top right (represented by yellow haze). The small molecule in question
may be a cytokine, and the response related to inflammatory response in normal
tissue: CA19-9 is also known to be elevated by inflammation. Resistant mutant
cell in blue, sensitive cells with modified uptake/efflux tagged with blue
stars.

Larger shielding ratios can be achieved with other signalling mechanisms.
Rather than being mediated by a small signalling molecule, cells are able to
transmit signals by coming into biochemical contact with cells they are
adjacent to. Conformational changes inreceptors on the membranes of two
adjacent cells can trigger signalling cascades when they come into adhesive
contact [4] (see figure 4.6). A given signal can then propagate through a
population of connected cells in a wavelike manner, with characteristic
speeds, in which newly activated cells on the wavefront triggering a new front
of cells in front of them. Wavelike phenomena in tissues are well-attested,
and the activation patterns associated with them are readily monitored by
tracking second messengers such as calcium [138, 139].

Shielding models based on wavelike propagation differ from models based on
diffusion of a small molecule in the crucial regard that the distance the
signal can travel is not limited by the degradation of a small molecule. It
follows that the number of cells that can be shielded could be much larger.
Naively, one might suspect that arbitarily large volumes of tumour cells could
be reached by the signal, but this is probably not the case. The propagation
of calcium waves depends on a reliable response of the cells to activation,
and occasional random failure of some of these cells due to variability in
response (among other imaginable factors) will attenuate the signal.

Although the mechanism underlying the attenuation was not studied in detail,
an experiment to measure the distance that calcium-dependent waves could
travel before becoming attenuated to the point of undetectability put the
attenuation distance at about $1\;\mathrm{mm}$. We should note, however, that
this was in a very different type of tissue than ductal pancreatic cancer, and
may also be affected by geometry [140]. This places an experimental estimate
on the upper limit of shielding range by this mechanism.

An attenuation distance of approximately $1\;\mathrm{mm}$ and a typical cell
size of $10\;\mathrm{\hbox{\textmu}m}$ imply a shielding ratio

$S\approx\left(\frac{1\;\mathrm{mm}}{10\;\mathrm{\hbox{\textmu}m}}\right)^{3}=10^{6}$
(4.14)

via equation (4.13). This is indeed much higher than in the small-molecule
proposal.

In order to actually test this possibility, at least one candidate molecule
and an interesting novel prediction are in order. The current experimental
literature on calcium-dependent signalling in cancer seems to point to IP3R as
another important second messenger in these pathways, but plays such diverse
roles even in normal tissues that its presence wouldn’t be specific to this
proposed mechanism [141]. An alternative candidate, which transmitted signals
from cell to cell via gap junctions, is Connexin-42. If it is the case that
wavelike signalling is behind cross-resistance, then the fact that regions
which can be reached by these waves must be spatially contiguous could be used
to exclude this hypothesis. If only one spatially connected region of a tumour
was found to have established multi-drug resistance, this would be consistent
with the wavelike hypothesis; whereas if many distinct regions were found to
have independently established cross-resistance or it was otherwise diffused
throughout he tumour in a way not obviously related to space, this would
effectively rule out wavelike signalling as responsible.

The fact that the resistant subpopulation regrows exponentially seems to
suggest that well-mixed, and therefore spatially diffuse growth of the
resistant subpopulation is occurring. However, it is not possible on the basis
of our clinical data alone to rule out the possibility that this is due to the
resistant population being well-perfused and growing exponentially albeit in a
spatially limited region. An experiment which could detect cross-resistant
regions and comment on their topology, perhaps via advances in medical imaging
or analysis of tumour biopsies, could provide a stringent test of this
hypothesis.

Figure 4.6: A diagram showing one possible mechanism by which a small number
of resistant mutants can trigger a cascade of resistance in otherwise
sensitive cells. A travelling wave of cell-to-cell signalling through
transmembrane proteins and tight junctions triggers a change in transmembrane
pump activity and slows the uptake of cytotoxin in cells. Candidate molecules
that may be associated with this travelling wave are Connexin-42 and JNK1.
Mutant cells in blue, sensitive cells with modified uptake/efflux tagged with
blue stars, and the travelling wave of resistance to cytotoxin represented by
successive wavefronts, dashed black line.

###  4.4 Concluding remarks

Despite positive remarks about our mathematical model’s usefulness from
practising clinicians who organised and carried out the experimental work of
the study, the inferred fraction of resistant subclones $f_{R}$ was several
orders of magnitude higher than what was expected on the basis of a
mathematically rigorous theory that assumed as little as possible about
unknown biology. This inconsistency between the experimental result and the
theoretical prediction indicates that at least one of the postulates of the
underlying theory is wrong, a very surprising result which presents a major
interpretative challenge.

The relevant postulates of the mathematical theory are that:

  1. 1.

Resistance to chemotherapy is acquired by the accumulation of novel genetic
mutations,

  2. 2.

Several distinct mutations are required, as the mechanisms of action of the
drugs do not overlap,

  3. 3.

The relevant mutations are selectively neutral prior to the application of the
therapy.

Different alternative mechanisms can be speculated about as explanations in
each case, but much additional research would need to be done to exclude even
a few of the abundance of possible explanations. Of particular interest is the
possibility of poorly-characterised interactions between known protein kinases
bringing about resistance to several agents simultaneously, whether this is by
one of these mutating or a yet-to-be-discovered response to toxicity latent
even in normal cells.

Each of our proposed mechanisms to explain the anomalously high $f_{R}$ can be
clarified and made more concrete with educated guesses as to the identity of
candidate molecules which may be involved. However, as many of our candidate
molecules are known to have many different interactions, many of which are
still poorly characterised, experimental evidence that one of them is
correlated with cross-resistance does not in itself constitute evidence for
our purported mechanism. More stringent tests that could specifically exclude
each proposal, and ideally novel predictions of more rigorous quantitative
formulations thereof, are necessary to clarify which if any are responsible
for the unexpectedly high rates of cross-resistance observed. We have tried to
put forward at least one way to experimentally falsify each proposal.

In conclusion, this analysis has highlighted very serious holes in the current
understanding of multi-drug resistance in pancreatic cancer, in particular
regarding the specificity of cellular responses to cytotoxins, and the
possibility of overlapping mechanisms. While it may be the case that one yet-
to-be-identified mutated protein can bring about resistance to drugs with
widely different pharmacological properties and cellular transport mechanisms,
there are a large number of other possible mechanisms by which intrinsic
resistance could emerge which cannot be ruled out on the basis of current
experimental knowledge, and would need to be ruled out by future research in
order to shed light on the true mechanism of cross-resistance observed here.

##  Chapter 5 Conclusion

The main object of this thesis was to explore the relationships between cell
motility, tumour growth, and evolution in advanced cancers. Although motility
and invasion is known to be of critical importance for growth and clinical
outcomes, there is a lack of research which is both precise, clinically
applicable, and simple enough to be intelligible and transparent to ordinary
humans. We intended to develop and apply a series of minimalistic models with
a view to establishing how changes in migration could affect the speed at
which cancers evolve, and furthermore we attempted to constrain and test these
models’ results empirically.

There are a number of more specific questions that we set out to address. What
mechanical and kinetic properties determine the speed of cell migration, and
the frequency with which motile cells are released by a tumour? What effect do
the resulting changes in cell migration have on the growth curve of cancers?
How do differences in growth rates and fitness determine the pace of
evolution? And finally, how rapidly do cancers grow and evolve in reality?

To address how the mechanical properties of cancer cells affected how easily
they could migrate through tissues, we performed simulations of how motile
cells responded to applied forces while embedded in cellular monolayers. These
simulations treated cells as isotropic elastic spheres, modelled the
transition between different cell types as a stochastic process, and measured
how quickly the cells moved when subjected to a constant traction force. The
two cell types were treated as static, non-invasive epithelial cells and
motile invasive mesenchymal type cells, with the invasive cells assigned a
different elastic stiffness. The effect of adjusting the elastic stiffness was
that more elastic and easily deformed cells could move faster through tissue,
and stiffer cells moved slower through tissue: elastic stiffness therefore
affects cells’ drag coefficients, at least in cellular monolayers.

We also found that making invasive cells arbitrarily stiff did not result in
an arbitrarily high resistance to motion. We interpreted this as representing
the fact that even an ideally stiff sphere surrounded in a deformable medium
would have its resistance to motion limited by the surrounding medium,
similarly to the case of a very hard metal sphere falling through a viscous
liquid.

These mechanistic simulations were very computationally intensive, so were not
suitable for simulations of larger tumours. To examine the effect of changes
in cell migration speed, changes in rates of type switching, and changes in
cell division rate on the growth curves of large tumours, we developed a
lattice model in which cells could transition between a non-motile type that
stayed at one lattice site and divided with an adjustable stochastic rate, and
a motile type which hopped between sites with a constant speed and randomly
changed direction with some rate $\alpha$.

These simulations naturally showed how spheroidal tumours could emerge from a
simple set of rules, and that migration enabled limited periods of exponential
growth. They also demonstrated that the rate of this exponential growth was
not only affected by the rate at which cells switched to motile types, which
was expected, but also by the rate at which they switched back to non-motile
types, and furthermore by the migration speed. These latter two dependencies
were unexpected and rather complex, but could be interpreted in terms of their
effect on the proportion of motile cells present at any one time and the delay
between a cell’s escape and its founding of a new tumour.

Another lattice model was developed which abstracted cell migration entirely,
treating migration events as instantaneous and extremely distant from the
originating tumour. The new secondary lesions which were founded as a result
of these events could therefore be thought of as developing independently of
the originating primary. These simulations also included the appearance of new
mutations, and treated cell division as a stochastic process. These
simulations established that ensembles of tumours do indeed grow exponentially
if the individual lesions’ growth do not interfere with each other, and that
the rate of this exponential growth can be related to the proportion of cells
which migrate and found new lesions.

The roughness of the surfaces of the spheroids in this lattice model was also
important, resulting in a more complex dependence between migration and growth
rates and a slower speed at which new advantageous mutants can grow across the
surface than previously estimated by other authors.

To understand how this last lattice model could support exponential growth and
how the pace of evolution could be estimated, we developed a coarse-grained
analytical theory which treated individual lesions as continuous “blobs” with
pre-determined growth curves, and migration and mutation as stochastic events
which occurred with some specified rates. The rationale for this was that
invasion and new mutations occur much more rarely than cell division. Both
numerical realisations of the stochastic process, and a mean-field
approximation could be studied: they corroborated the idea that exponential
growth could occur as long as individual lesions were isolated from each
other, and showed how the accumulation of advantageous mutations could be
related to the underlying growth curves of lesions of different genetic
backgrounds. Some questions remain about the accuracy of the approximation
scheme we used, and we were not able to answer them definitively.

Finally, we attempted to model how tumour size developed over time in
pancreatic cancer patients during a new form chemotherapy designed to have
very few possible mutations that could cause resistance. We found that in many
cases a sum of two simple exponential functions provided a very good fit, but
the inferred number of resistant cells was many orders of magnitude higher
than predicted by other authors on the study. This revealed serious
deficiencies in the current understanding of pancreatic cancer, as the
prediction was made on the basis of a mathematical model which did not make
any controversial assumptions with respect to the underlying biology, and we
were forced to consider alternative hypotheses for the mechanisms by which
resistance to chemotherapy emerges.

Although they weren’t related in a strongly systematic way, we went to some
effort to ensure that the conclusions of one model could inform the inputs of
the following model. For example, the mechanistic simulation predicts cell
motility speed, which is an important input to the run-and-tumble lattice
model. This lattice model predicts growth curves of tumours, which were an
important input to the analytical ensemble model, and the ensemble model made
predictions for the proportion of advantageous mutants, which was one possible
interpretation of the fraction of resistant cells observed in the clinical
study. In this way, future work in a related area may be able to chain
together improvements on our minimal models to estimate the effect of changing
individual cell properties like elasticity on how rapidly new mutant strains
emerge. We should emphasise that this is at this point rather speculative, and
the number of possible factors affecting the macroscopic outcomes is probably
much larger than the ones we have chosen to study in this thesis.

The usefulness of our approach, of making models that are “as simple as
possible but no simpler”, and of trying to connect our calculations to
experimental observables, is not only that the resulting mathematical models
are open to experimental refutations, as is a prerequisite for all science,
but also that the whole of our theoretical work can be understood and in
principle reproduced by a single person. This is in contrast to many trends in
current scientific work, which rely on models and analyses so complex that
their reproduction requires cooperation between many different specialists on
a wide scale.

Of course, the experimental study to which we contributed necessarily required
a large collaboration, as the actual practical business of conducting it was
intrinsically difficult. This does not mean, however, that theory should
follow suit. I believe that we have demonstrated how theory which balances
minimalism and empirical relevance still has the potential to give a unified
picture of scientific knowledge where this is possible, and more importantly
to reveal unexpected holes where this is not. If the point of science is to
advance human understanding, then science cannot depend on black boxes.

## References

  * [1] Steven I Hajdu.  A note from history: landmarks in history of cancer, part 1.  Cancer, 117(5):1097–1102, 2011.
  * [2] Douglas Hanahan and Robert A Weinberg.  The hallmarks of cancer.  Cell, Vol. 100, 57-70, January 7, 2000, 2000.
  * [3] Douglas Hanahan and Robert A Weinberg.  Hallmarks of cancer: the next generation.  cell, 144(5):646–674, 2011.
  * [4] B. Alberts, D. Bray, J. Lewis, M. Raff, K. Roberts, and P. Walter.  Molecular biology of the cell, 5th ed.  2008\.
  * [5] G. B. Pierce.  Relationship between differentiation and carcinogenesis.  Journal of Toxicology and Environmental Health, Part A Current Issues, 2(6), 1335-1342, 1977.
  * [6] Cancer Research UK.  Released under a Creative Commons share-alike license with attribution, _https://creativecommons.org/licenses/by-sa/4.0/deed.en_.
  * [7] Sean J Morrison and Judith Kimble.  Asymmetric and symmetric stem-cell divisions in development and cancer.  nature, 441(7097):1068, 2006.
  * [8] B. D. Simons and H. Clevers.  Strategies for homeostatic stem cell self-renewal in adult tissues.  Cell, 145(6), 851-862, 2011.
  * [9] A. Wilson, E. Laurenti, G. Oser, R. C. van der Wath, W. Blanco-Bose, M. Jaworski, …, and A. Trumpp.  Hematopoietic stem cells reversibly switch from dormancy to self-renewal during homeostasis and repair.  Cell, 135(6), 1118-1129, 2008.
  * [10] Julia Frede, Philip Greulich, Tibor Nagy, Benjamin D Simons, and Philip H Jones.  A single dividing cell population with imbalanced fate drives oesophageal tumour growth.  2016\.
  * [11] Maria P Alcolea, Philip Greulich, Agnieszka Wabik, Julia Frede, Benjamin D Simons, and Philip H Jones.  Differentiation imbalance in single oesophageal progenitor cells causes clonal immortalization and field change.  Nature cell biology, 16(6):615, 2014.
  * [12] Peter C Nowell.  The clonal evolution of tumor cell populations.  Science, 194(4260):23–28, 1976.
  * [13] Ben Vogelstein et al.  Cancer genes and the pathways they control.  Nature Medicine 10, 789-799, 2004.
  * [14] B Vogelstein, N Papadopoulos, VE Velculescu, S Zhou, LA Diaz, and KW Kinzler.  Cancer genome landscapes.  Science 339 (6127): 1546-58, 2013.
  * [15] R. Durrett, J. Foo, K. Leder, Mayberry J., and F. Michor.  Evolutionary dynamics of tumor progression with random fitness values.  Theoretical Population Biology, 78:54–66, 2010.
  * [16] M.A. Nowak et al.  The linear process of somatic evolution.  Proc. Natl Acad. Sci. USA, 100, 14966–14969, 2003.
  * [17] Eric R Fearon, Bert Vogelstein, et al.  A genetic model for colorectal tumorigenesis.  Cell, 61(5):759–767, 1990.
  * [18] Ivana Bozic, Antal, Hisashi Ohtsuki, Hannah Carter, Dewey Kim, Sining Chen, Rachel Karchin, Kenneth W Kinzler, Bert Vogelstein, and Martin A Nowak.  Accumulation of driver and passenger mutations during tumor progression.  Proceedings of the National Academy of Sciences, 107(43):18545–18550, 2010.
  * [19] Luis A. Diaz Jr, Richard T. Williams, Jian Wu, Isaac Kinde, J. Randolph Hecht, Jordan Berlin, Benjamin Allen, Ivana Bozic, Johannes G. Reiter, Martin A. Nowak, Kenneth W. Kinzler, Kelly S. Oliner, and Bert Vogelstein.  The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers.  Nature, 486(7404):537–540, June 2012.
  * [20] Gerard Manning, David B Whyte, Ricardo Martinez, Tony Hunter, and Sucha Sudarsanam.  The protein kinase complement of the human genome.  Science, 298(5600):1912–1934, 2002.
  * [21] Piya Lahiry, Ali Torkamani, Nicholas J Schork, and Robert A Hegele.  Kinase mutations in human disease: interpreting genotype-phenotype relationships.  Nature reviews. Genetics, 11(1):60, 2010.
  * [22] Erich A Nigg.  Cyclin-dependent protein kinases: key regulators of the eukaryotic cell cycle.  Bioessays, 17(6):471–480, 1995.
  * [23] Ramsey A Foty, Gabor Forgacs, Cathie M Pfleger, and Malcolm S Steinberg.  Liquid properties of embryonic tissues: measurement of interfacial tensions.  Physical review letters, 72(14):2298, 1994.
  * [24] Gabor Forgacs and Malcolm S Steinberg.  Viscoelastic properties of living embryonic tissues: a quantitative study.  Biophysical Journal Volume 74 2227–2234, May 1998.
  * [25] Malcolm S Steinberg.  Differential adhesion in morphogenesis: a modern view.  Current Opinion in Genetics & Development, 17(4) 281–286, August 2007.
  * [26] Robert H Insall and Laura M Machesky.  Actin dynamics at the leading edge: from simple machinery to complex networks.  Developmental cell, 17(3):310–322, 2009.
  * [27] Damijan Miklavčič, Tomaž Jarm, Rihard Karba, and Gregor Serša.  Mathematical modelling of tumor growth in mice following electrotherapy and bleomycin treatment.  Mathematics and computers in simulation, 39(5):597–602, 1995.
  * [28] Andrew Stein, Daniel DeWoskin, Michael Higley, Kyle Lemoi, Ben Owens, Aminur Rahman, Horacio Rotstein, David Rumschitzki, Sumanth Swaminathan, Matthew Tanzy, et al.  Dynamic models of metastatic tumor growth.  In Final Report of the 27th Annual Workshop on Mathematical Problems in Industry, New Jersey Institute of Technology, 2011.
  * [29] Sébastien Benzekry, Clare Lamont, Afshin Beheshti, Amanda Tracz, John M. L. Ebos, Lynn Hlatky, and Philip Hahnfeldt.  Classical mathematical models for description and prediction of experimental tumor growth.  PLoS Comput Biol, 10(8):e1003800, 08 2014.
  * [30] I.A. Rodriguez-Brenes, N.L. Komarova, and D. Wodarz.  Tumor growth dynamics: insights into evolutionary processes.  Trends in Ecology & Evolution, 28:597–604, 2013.
  * [31] Peter L Bonate.  Modeling tumor growth in oncology.  In Pharmacokinetics in Drug Development, pages 1–19. Springer, 2011\.
  * [32] R.A. Weinberg.  The Biology of Cancer.  Garland Science, 2007.
  * [33] Shinichi Yachida, Sian Jones, Ivana Bozic, Antal, Rebecca Leary, Baojin Fu, Mihoko Kamiyama, Ralph H Hruban, James R Eshleman, Martin A Nowak, et al.  Distant metastasis occurs late during the genetic evolution of pancreatic cancer.  Nature, 467(7319):1114–1117, 2010.
  * [34] S. Ling and et al.  Extremely high genetic diversity in a single tumor points to prevalence of non-darwinian cell evolution.  Proceedings of the National Academy of Sciences, 112:E6496–E6505, 2015.
  * [35] A Sottoriva and et al.  A big bang model of human colorectal tumor growth.  Nature Genetics, 47:209–216, 2015.
  * [36] James D Murray.  Mathematical Biology. II Spatial Models and Biomedical Applications.  Springer-Verlag New York Incorporated, 2001.
  * [37] Ernst Mayr.  Systematics and the origin of species, from the viewpoint of a zoologist.  Harvard University Press, 1942.
  * [38] Erik A. Martens, Rumen Kostadinov, Carlo C. Maley, and Oskar Hallatschek.  Spatial structure increases the waiting time for cancer.  New journal of physics 13(11), 115014, 2011.
  * [39] O. Hallatschek, P. Hersen, S. Ramanathan, and D.R Nelson.  Genetic drift at expanding frontiers promotes gene segregation.  Proceedings of the National Academy of Sciences, 104(50):19926–30, 2007.
  * [40] Bartlomiej Waclaw, Ivana Bozic, Meredith E. Pittman, Ralph H. Hruban, Bert Vogelstein, and Martin A. Nowak.  A spatial model predicts that dispersal and cell turnover limit intratumour heterogeneity.  Nature, 525(7568):261–264, September 2015.
  * [41] Antal, PL Krapivsky, and MA Nowak.  Spatial evolution of tumors with successive driver mutations.  Physical Review E, 92, 2015.
  * [42] Philip Greulich, Bartłomiej Waclaw, and Rosalind J Allen.  Mutational pathway determines whether drug gradients accelerate evolution of drug-resistant cells.  Physical Review Letters, 109(8):088101, 2012.
  * [43] Stephen Jay Gould and Niles Eldredge.  Punctuated equilibria: an alternative to phyletic gradualism.  1972\.
  * [44] Anne C Chiang and Joan Massagué.  Molecular basis of metastasis.  New England Journal of Medicine, 359(26):2814–2823, 2008.
  * [45] Melanie C Smitt, Kent W Nowels, Mark J Zdeblick, Stefanie Jeffrey, Robert W Carlson, Frank E Stockdale, and Don R Gfinet.  The importance of the lumpectomy surgical margin status in long term results of breast conservation.  Cancer, 76:259–267, 1995.
  * [46] Francesco Porpiglia, Cristian Fiori, Carlo Terrone, Enrico Bollito, Dario Fontana, and Roberto Mario Scarpa.  Assessment of surgical margins in renal cell carcinoma after nephron sparing: a comparative study: laparoscopy vs open surgery.  The Journal of urology, 173(4):1098–1101, 2005.
  * [47] Jessica H Maxwell, Lester DR Thompson, Margaret S Brandwein-Gensler, Bernhard G Weiss, Martin Canis, Bibianna Purgina, Arpan V Prabhu, Chi Lai, Yongli Shuai, William R Carroll, et al.  Early oral tongue squamous cell carcinoma: sampling of margins from tumor bed and worse local control.  JAMA Otolaryngology–Head & Neck Surgery, 141(12):1104–1110, 2015\.
  * [48] LA Liotta, K Tryggvason, S Garbisa, Ian Hart, CM Foltz, and S Shafie.  Metastatic potential correlates with enzymatic degradation of basement membrane collagen.  Nature, 284(5751):67–68, 1980.
  * [49] Miriam Schenk, Berk Aykut, Christian Teske, Nathalia A Giese, Juergen Weitz, and Thilo Welsch.  Salinomycin inhibits growth of pancreatic cancer and cancer cell migration by disruption of actin stress fiber integrity.  Cancer letters, 358(2):161–169, 2015.
  * [50] Sir James Lighthill.  Mathematical biofluiddynamics.  SIAM, 1975.
  * [51] G Moreno-Bueno, F Portillo, and A Cano.  Transcriptional regulation of cell polarity in emt and cancer.  Oncogene 27, 6958-6969, 2008.
  * [52] J. Yang, X. Du, G. Wang, Y. Sun, K. Chen, X. Zhu, …, and W. Zhang.  Mesenchymal to epithelial transition in sarcomas.  European Journal of Cancer, 50(3), 593-601, 2014.
  * [53] Piyush B. Gupta et al.  Stochastic state transitions give rise to phenotypic equilibrium in populations of cancer cells.  Cell 146(4), 633-644, 2011.
  * [54] G John Ferguson, Laura Milne, Suhasini Kulkarni, Takehiko Sasaki, Simon Walker, Simon Andrews, Tom Crabbe, Peter Finan, Gareth Jones, Shaun Jackson, et al.  Pi (3) k [gamma] has an important context-dependent role in neutrophil chemokinesis.  Nature cell biology, 9(1):86, 2007.
  * [55] Qiuhui Li, Kiera Rycaj, Xin Chen, and Dean G Tang.  Cancer stem cells and cell size: A causal link?  In Seminars in cancer biology, volume 35, pages 191–199. Elsevier, 2015.
  * [56] Anh N Hoang, Caroline N Jones, Laurie Dimisko, Bashar Hamza, Joseph Martel, Nikola Kojic, and Daniel Irimia.  Measuring neutrophil speed and directionality during chemotaxis, directly from a droplet of whole blood.  Technology, 1(01):49–57, 2013.
  * [57] M Lekka, P Laidler, D Gil, J Lekki, Z Stachura, and AZ Hrynkiewicz.  Elasticity of normal and cancerous human bladder cells studied by scanning force microscopy.  European Biophysics Journal, 28(4):312–316, 1999.
  * [58] Dirk Drasdo.  Buckling instabilities of one-layered growing tissues.  Physical review letters, 84(18):4244, 2000.
  * [59] Gernot Schaller and Michael Meyer-Hermann.  Multicellular tumor spheroid in an off-lattice voronoi-delaunay cell model.  Physical Review E, 71(5):051910, 2005.
  * [60] Ramsey A Foty and Malcolm S Steinberg.  The differential adhesion hypothesis: a direct evaluation.  Developmental biology, 278(1):255–263, 2005.
  * [61] Ramsey A Foty and Malcolm S Steinberg.  Cadherin-mediated cell-cell adhesion and tissue segregation in relation to malignancy.  International Journal of Developmental Biology, 48(5-6):397–409, 2004.
  * [62] Gareth Wyn Jones and S Jonathan Chapman.  Modeling growth in biological materials.  Siam review, 54(1):52–118, 2012.
  * [63] Jörg Galle, Markus Loeffler, and Dirk Drasdo.  Modeling the effect of deregulated proliferation and apoptosis on the growth dynamics of epithelial cell populations in vitro.  Biophysical journal, 88(1):62–75, 2005.
  * [64] Dirk Drasdo and Stefan Höhme.  A single-cell-based model of tumor growth in vitro: monolayers and spheroids.  Physical biology, 2(3):133, 2005.
  * [65] Lev D Landau and EM Lifshitz.  Theory of elasticity, vol. 7.  Course of Theoretical Physics, 3:109, 1986.
  * [66] Remigiusz Kowalczyk.  Preventing blow-up in a chemotaxis model.  Journal of Mathematical Analysis and Applications, 305(2):566–588, 2005.
  * [67] Tomasz Koziara and Nenad Bicanic.  Bounding box collision detection.  In 13th acme conference: university of sheffield, 2005.
  * [68] Hawa-Racine Thiam, Pablo Vargas, Nicolas Carpi, Carolina Lage Crespo, Matthew Raab, Emmanuel Terriac, Megan C King, Jordan Jacobelli, Arthur S Alberts, Theresia Stradal, et al.  Perinuclear arp2/3-driven actin polymerization enables nuclear deformation to facilitate cell migration through complex environments.  Nature communications, 7, 2016.
  * [69] Matthew P Neilson, John A Mackenzie, Steven D Webb, and Robert H Insall.  Modeling cell movement and chemotaxis using pseudopod-based feedback.  SIAM Journal on Scientific Computing, 33(3):1035–1057, 2011.
  * [70] Marco Scianna and Luigi Preziosi.  Modeling the influence of nucleus elasticity on cell invasion in fiber networks and microchannels.  Journal of theoretical biology, 317:394–406, 2013.
  * [71] Murray Eden.  A two-dimensional growth process.  Dynamics of fractal surfaces, 4:223–239, 1961.
  * [72] Luca Angelani.  Run-and-tumble particles, telegrapher’s equation and absorption problems with partially reflecting boundaries.  Journal of Physics A: Mathematical and Theoretical, 48(49):495003, 2015.
  * [73] J Tailleur and ME Cates.  Statistical mechanics of interacting run-and-tumble bacteria.  Physical review letters, 100(21):218103, 2008.
  * [74] Ron Breukelaar and Th Bäck.  Using a genetic algorithm to evolve behavior in multi dimensional cellular automata: emergence of behavior.  In Proceedings of the 7th annual conference on Genetic and evolutionary computation, pages 107–114. ACM, 2005.
  * [75] Kurt Mehlhorn and Peter Sanders.  Algorithms and data structures.  2007\.
  * [76] Sidney Goldstein.  On diffusion by discontinuous movements, and on the telegraph equation.  The Quarterly Journal of Mechanics and Applied Mathematics, 4(2):129–156, 1951.
  * [77] M Suzuoki and et al.  Impact of caveolin-1 expression on prognosis of pancreatic ductal adenocarcinoma.  British Journal of Cancer, 87:1140–1144, 2002.
  * [78] H Enderling, L Hlatky, and P Hahnfeldt.  Migration rules: tumours are conglomerates of self-metastases.  British journal of cancer, 100(12):1917–1925, 2009.
  * [79] L Hanin, J Rose, and M Zaider.  A stochastic model for the sizes of detectable metastases.  Journal of Theoretical Biology, 243(3):407–417, 2006.
  * [80] O G McDonald, H Wu, W Timp, and A Doi.  Genome-scale epigenetic reprogramming during epithelial-to-mesenchymal transition.  Nature Structural & Molecular Biology, 18:867–874, 2011.
  * [81] Fabien Montel, Morgan Delarue, Jens Elgeti, Laurent Malaquin, Markus Basan, Thomas Risler, Bernard Cabane, Danijela Vignjevic, Jacques Prost, Giovanni Cappello, et al.  Stress clamp experiments on multicellular tumor spheroids.  Physical review letters, 107(18):188102, 2011.
  * [82] K Iwata, K Kawasaki, and N Shigesada.  A dynamical model for the growth and size distribution of multiple metastatic tumors.  Journal of theoretical biology, 203(2):177–186, 2000.
  * [83] F Michor, M A Nowak, and Y Iwasa.  Stochastic dynamics of metastasis formation.  Journal of Theoretical Biology, 240:521–530, 2006.
  * [84] Barbara Lee Keyfitz and N Keyfitz.  The mckendrick partial differential equation and its uses in epidemiology and population study.  Mathematical and Computer Modelling, 26(6):1–9, 1997.
  * [85] Benoît Perthame.  Transport equations in biology.  Springer, 2006.
  * [86] E Baratchart and et al.  Computational modelling of metastasis development in renal cell carcinoma.  PLoS Computational Biology, 11:e1004626, 2015.
  * [87] Motoo Kimura.  The number of heterozygous nucleotide sites maintained in a finite population due to steady flux of mutations.  Genetics, 61(4):893, 1969.
  * [88] J Folkman.  What is the evidence that tumors are angiogenesis dependent?  Journal of the National Cancer Institute, 82:4–7, 1990.
  * [89] G N Naumov, J Folkman, and O Straume.  Tumor dormancy due to failure of angiogenesis: role of the microenvironment.  Clinical & Experimental Metastasis, 26:51–60, 2008.
  * [90] Maxim O Lavrentovich and David R Nelson.  Survival probabilities at spherical frontiers.  Theoretical population biology, 102:26–39, 2015.
  * [91] C. Tomasetti, L. Marchionni, M. A. Nowak, G. Parmigiani, and B. Vogelstein.  Only three driver gene mutations are required for the development of lung and colorectal cancers.  Proceedings of the National Academy of Sciences, 112:118–123, 2015\.
  * [92] C.J. Thalhauser, J.S. Lowengrub, D. Stupack, and N.L. Komarova.  Selection in spatial stochastic models of cancer: Migration as a key modulator of fitness.  Biol. Direct, 5:21, 2010.
  * [93] O. Hallatschek and D.S. Fisher.  Acceleration of evolutionary spread by long-range dispersal.  Proceedings of the National Academy of Sciences, 111:E4911–19, 2014\.
  * [94] P. Vaupel, F. Kallinowski, and P. Okunieff.  Blood flow, oxygen, and nutrient supply, and metabolic microenvironment of human tumors: A review.  Cancer Research, 49:6449–65, 1989.
  * [95] S.K. Parks, Y. Cormerais, I. Marchiq, and J. Pouyssegur.  Hypoxia optimises tumour growth by controlling nutrient import and acidic metabolite export.  Molecular Aspects of Medicine, 47-48:3–14, 2016.
  * [96] M. et al. Fokkelman.  Cellular adhesome screen identifies critical modulators of focal adhesion dynamics, cellular traction forces and cell migration behaviour.  Scientific Reports, 6:31707, 2016.
  * [97] M. Gerlinger and et al.  Intratumor heterogeneity and branch evolution revealed by multiregion sequencing.  New England Journal of Medicine, 366:883–892, 2012.
  * [98] B. Werner and et al.  The cancer stem cell fraction in hierarchically organized tumors can be estimated using mathematical modeling and patient-specific treatment trajectories.  Cancer Research, 76:1705, 2016.
  * [99] B.J. Bauer, R. Sieberg, and A. Traulsen.  Cancer initiation with epistatic interactions between driver and passenger mutations.  Journal of Theoretical Biology, 358:52–60, 2014.
  * [100] Chris D Greenman and Tom Chou.  Kinetic theory of age-structured stochastic birth-death processes.  Physical Review E, 93(1):012112, 2016.
  * [101] Giles Bond-Smith, Neal Banga, Toby M Hammond, and Charles J Imber.  Pancreatic adenocarcinoma.  Bmj, 344(e2476), 2012.
  * [102] Thierry Conroy, Françoise Desseigne, Marc Ychou, Olivier Bouché, Rosine Guimbaud, Yves Bécouarn, Antoine Adenis, Jean-Luc Raoul, Sophie Gourgou-Bourgade, Christelle de la Fouchardière, et al.  Folfirinox versus gemcitabine for metastatic pancreatic cancer.  New England Journal of Medicine, 364(19):1817–1825, 2011.
  * [103] Daniel D Von Hoff, Ramesh K Ramanathan, Mitesh J Borad, Daniel A Laheru, Lon S Smith, Tina E Wood, Ronald L Korn, Neil Desai, Vuong Trieu, Jose L Iglesias, et al.  Gemcitabine plus nab-paclitaxel is an active regimen in patients with advanced pancreatic cancer: a phase i/ii trial.  Journal of Clinical Oncology, 29(34):4548–4554, 2011.
  * [104] Mark Sausen, Jillian Phallen, Vilmos Adleff, Siân Jones, Rebecca J Leary, Michael T Barrett, Valsamo Anagnostou, Sonya Parpart-Li, Derek Murphy, Qing Kay Li, et al.  Clinical implications of genomic alterations in the tumour and circulation of pancreatic cancer patients.  Nature communications, 6:7686, 2015.
  * [105] Ivana Bozic, Johannes G Reiter, Benjamin Allen, Tibor Antal, Krishnendu Chatterjee, Preya Shah, Yo Sup Moon, Amin Yaqubie, Nicole Kelly, Dung T Le, et al.  Evolutionary dynamics of cancer in response to targeted combination therapy.  Elife, 2:e00747, 2013.
  * [106] Daniel B Longley, D Paul Harkin, and Patrick G Johnston.  5-fluorouracil: mechanisms of action and clinical strategies.  Nature Reviews Cancer, 3(5):330–338, 2003.
  * [107] E Mini, SFAU Nobili, BFAU Caciagli, I Landini, and T Mazzei.  Cellular pharmacology of gemcitabine.  Annals of Oncology, 17(suppl_5):v7–v12, 2006.
  * [108] CM Galmarini, JR Mackey, and C Dumontet.  Nucleoside analogues: mechanisms of drug resistance and reversal strategies.  Leukemia, 15(6):875, 2001.
  * [109] Jing Zhang, Frank Visser, Karen M King, Stephen A Baldwin, James D Young, and Carol E Cass.  The role of nucleoside transporters in cancer chemotherapy with nucleoside drugs.  Cancer and Metastasis Reviews, 26(1):85–110, 2007.
  * [110] Anne-Marie C Yvon, Patricia Wadsworth, and Mary Ann Jordan.  Taxol suppresses dynamics of individual microtubules in living human tumor cells.  Molecular biology of the cell, 10(4):947–959, 1999.
  * [111] SD Baker, Jaap Verweij, GA Cusatis, RH Schaik, Steven Marsh, SJ Orwick, RM Franke, S Hu, EG Schuetz, V Lamba, et al.  Pharmacogenetic pathway analysis of docetaxel elimination.  CliniCal pharmaCology & TherapeuTiCs, 85(2):155–163, 2009.
  * [112] Donald Mastropaolo, Arthur Camerman, Yuogang Luo, Gary D Brayer, and Norman Camerman.  Crystal and molecular structure of paclitaxel (taxol).  Proceedings of the National Academy of Sciences, 92(15):6920–6924, 1995.
  * [113] L Galluzzi, L Senovilla, I Vitale, J Michels, I Martins, O Kepp, M Castedo, and G Kroemer.  Molecular mechanisms of cisplatin resistance.  Oncogene, 31(15):1869–1883, 2012.
  * [114] Mahmoud El-Khateeb, Trevor G Appleton, Lawrence R Gahan, Bruce G Charles, Susan J Berners-Price, and Ann-Maree Bolton.  Reactions of cisplatin hydrolytes with methionine, cysteine, and plasma ultrafiltrate studied by a combination of hplc and nmr techniques.  Journal of inorganic biochemistry, 77(1):13–21, 1999.
  * [115] Fabio Arnesano, Maurizio Losacco, and Giovanni Natile.  An updated view of cisplatin transport.  European journal of inorganic chemistry, 2013(15):2701–2711, 2013\.
  * [116] XG Ni, XF Bai, YL Mao, YF Shao, JX Wu, Y Shan, CF Wang, J Wang, YT Tian, Q Liu, et al.  The clinical value of serum cea, ca19-9, and ca242 in the diagnosis and prognosis of pancreatic cancer.  European Journal of Surgical Oncology (EJSO), 31(2):164–169, 2005\.
  * [117] Tomoko Ogawa, Hajime Yokoi, and Yoshifumi Kawarada.  A case of inflammatory pseudotumor of the liver causing elevated serum ca19-9 levels.  The American journal of gastroenterology, 93(12):2551–2555, 1998\.
  * [118] KS Goonetilleke and AK Siriwardena.  Systematic review of carbohydrate antigen (ca 19-9) as a biochemical marker in the diagnosis of pancreatic cancer.  European Journal of Surgical Oncology (EJSO), 33(3):266–270, 2007\.
  * [119] Erwin Kreyszig.  Advanced engineering mathematics.  John Wiley & Sons, 2010.
  * [120] Isaac Jacob Schoenberg.  Spline functions and the problem of graduation.  Proceedings of the National Academy of Sciences, 52(4):947–950, 1964.
  * [121] Tibor Antal and PL Krapivsky.  Exact solution of a two-type branching process: models of tumor progression.  Journal of Statistical Mechanics: Theory and Experiment, 2011(08):P08018, 2011.
  * [122] Salvador E Luria and Max Delbrück.  Mutations of bacteria from virus sensitivity to virus resistance.  Genetics, 28(6):491, 1943.
  * [123] C Bhang Hyo-eun, David A Ruddy, Viveksagar Krishnamurthy Radhakrishna, Justina X Caushi, Rui Zhao, Matthew M Hims, Angad P Singh, Iris Kao, Daniel Rakiec, Pamela Shaw, et al.  Studying clonal dynamics in response to cancer therapy using high-complexity barcoding.  Nature medicine, 21(5):440–448, 2015.
  * [124] M Yamasaki, T Makino, T Masuzawa, Y Kurokawa, H Miyata, S Takiguchi, K Nakajima, Y Fujiwara, N Matsuura, M Mori, et al.  Role of multidrug resistance protein 2 (mrp2) in chemoresistance and clinical outcome in oesophageal squamous cell carcinoma.  British journal of cancer, 104(4):707, 2011.
  * [125] Jean-Pierre Gillet and Michael M Gottesman.  Mechanisms of multidrug resistance in cancer.  Multi-drug resistance in cancer, pages 47–76, 2010.
  * [126] Jing Jin, Feng-Peng Wang, Huailing Wei, and Gengtao Liu.  Reversal of multidrug resistance of cancer through inhibition of p-glycoprotein by 5-bromotetrandrine.  Cancer chemotherapy and pharmacology, 55(2):179–188, 2005.
  * [127] Seiko Ishida, Jaekwon Lee, Dennis J Thiele, and Ira Herskowitz.  Uptake of the anticancer drug cisplatin mediated by the copper transporter ctr1 in yeast and mammals.  Proceedings of the National Academy of Sciences, 99(22):14298–14302, 2002.
  * [128] Swati S More, Omar Akil, Alexandra G Ianculescu, Ethan G Geier, Lawrence R Lustig, and Kathleen M Giacomini.  Role of the copper transporter, ctr1, in platinum-induced ototoxicity.  Journal of Neuroscience, 30(28):9500–9509, 2010.
  * [129] Seiko Ishida, Frank McCormick, Karen Smith-McCune, and Douglas Hanahan.  Enhancing tumor-specific uptake of the anticancer drug cisplatin with a copper chelator.  Cancer cell, 17(6):574–583, 2010.
  * [130] Lingjie Bao, Melba C Jaramillo, Zhenbo Zhang, Yunxi Zheng, Ming Yao, Donna D Zhang, and Xiaofang Yi.  Induction of autophagy contributes to cisplatin resistance in human ovarian cancer cells.  Molecular medicine reports, 11(1):91–98, 2015.
  * [131] Jun Hayakawa, Chantal Depatie, Masahide Ohmichi, and Dan Mercola.  The activation of c-jun nh2-terminal kinase (jnk) by dna-damaging agents serves to promote drug resistance via activating transcription factor 2 (atf2)-dependent enhanced dna repair.  Journal of Biological Chemistry, 278(23):20582–20592, 2003.
  * [132] Mohammad Fallahi-Sichani, Nathan J Moerke, Mario Niepel, Tinghu Zhang, Nathanael S Gray, and Peter K Sorger.  Systematic analysis of braf v 600e melanomas reveals a role for jnk/c-jun pathway in adaptive resistance to drug-induced apoptosis.  Molecular systems biology, 11(3):797, 2015.
  * [133] XY Liu, SP Liu, J Jiang, X Zhang, and T Zhang.  Inhibition of the jnk signaling pathway increases sensitivity of hepatocellular carcinoma cells to cisplatin by downregulating expression of p-glycoprotein.  Eur Rev Med Pharmacol Sci, 20(6):1098–1108, 2016.
  * [134] ED Lagadinou, PG Ziros, OA Tsopra, K Dimas, D Kokkinou, E Thanopoulou, M Karakantza, P Pantazis, A Spyridonidis, and NC Zoumbos.  c-jun n-terminal kinase activation failure is a new mechanism of anthracycline resistance in acute myeloid leukemia.  Leukemia, 22(10):1899, 2008.
  * [135] Xiaoping Ao and Julie A Stenken.  Microdialysis sampling of cytokines.  Methods, 38(4):331–341, 2006.
  * [136] Raymond Cheong, Adriel Bergmann, Shannon L Werner, Joshua Regal, Alexander Hoffmann, and Andre Levchenko.  Transient i$\kappa$b kinase activity mediates temporal nf-$\kappa$b dynamics in response to a wide range of tumor necrosis factor-$\alpha$ doses.  Journal of Biological Chemistry, 281(5):2945–2950, 2006.
  * [137] Valerie Sloane Jones, Ren-Yu Huang, Li-Pai Chen, Zhe-Sheng Chen, Liwu Fu, and Ruo-Pan Huang.  Cytokines in cancer drug resistance: cues to new therapeutic strategies.  Biochimica et Biophysica Acta (BBA)-Reviews on Cancer, 1865(2):255–265, 2016.
  * [138] John C Gilkey, Lionel F Jaffe, Ellis B Ridgway, and George T Reynolds.  A free calcium wave traverses the activating egg of the medaka, oryzias latipes.  The Journal of Cell Biology, 76(2):448–466, 1978.
  * [139] Raz Kupferman, Partha P Mitra, PC Hohenberg, and SS Wang.  Analytical calculation of intracellular calcium wave characteristics.  Biophysical journal, 72(6):2430–2444, 1997.
  * [140] Torben R Uhrenholt, Timothy L Domeier, and Steven S Segal.  Propagation of calcium waves along endothelium of hamster feed arteries.  American Journal of Physiology-Heart and Circulatory Physiology, 292(3):H1634–H1640, 2007.
  * [141] Yutaka Yoshida and Shoichi Imai.  Structure and function of inositol 1, 4, 5-trisphosphate receptor.  The Japanese Journal of Pharmacology, 74(2):125–137, 1997.


# The Repetition Threshold for Rote Sequences

Nicolas Ollinger
Université d’Orléans
LIFO - bât. 3IA
6 rue Léonard de Vinci
BP 6759
45067 Orléans Cedex 2
France
<EMAIL_ADDRESS>
Jeffrey Shallit111Supported in part by a grant from NSERC, 2018–04118.
School of Computer Science
University of Waterloo
200 University Ave. W.
Waterloo, ON N2L 3G1
Canada
<EMAIL_ADDRESS>
###### Abstract

We consider Rote words, which are infinite binary words with factor complexity
$2n$. We prove that the repetition threshold for this class is $5/2$. Our
technique is purely computational, using the Walnut theorem prover and a new
technique for generating automata from morphisms due to the first author and
his co-authors.

##  1 Introduction

We consider infinite sequences (words) $\bf x$ over a finite alphabet. A
classical metric for such sequences is their factor complexity (aka subword
complexity, aka complexity) $\rho_{\bf x}(n)$, which counts the number of
distinct factors (i.e., contiguous blocks) occurring in $\bf x$.

Rote sequences, introduced by Rote [18], form a particularly interesting
class; they are the words of factor complexity $2n$ for $n\geq 1$. Since such
a sequence has exactly two factors of length $1$, Rote sequences must be
defined over a binary alphabet, which we take to be $\Sigma_{2}=\\{0,1\\}$.
Some examples of Rote sequences studied in the literature include the Rote-
Fibonacci sequence [8] and complementation-symmetric Rote sequences [9].

Another metric of interest involves the degree of repetition in a word. We say
a finite word $z=z[0..n-1]$ has a period $p\leq n$ if $z[i]=z[i+p]$ for $0\leq
i<n-p$. For example, the French word entente has periods $3$, $6$, $7$. The
exponent $\exp(z)$ of a finite word $z$ is its length divided by its shortest
period. Thus, entente has exponent $7/3$. The critical exponent
$\operatorname{ce}({\bf x})$ of an infinite word $\bf x$ is the supremum, over
all finite factors $z$, of $\exp(z)$. Such a critical exponent can be
attained, or not attained. Given a set $S$ of infinite words, its repetition
threshold is the infimum, over all ${\bf x}\in S$, of $\operatorname{ce}({\bf
x})$.

Repetition thresholds have been determined for many large classes of words.
For example, in Dejean’s conjecture [7], the set $S$ is taken to be
$\Sigma_{k}^{*}$, where $\Sigma_{k}=\\{0,1,\ldots,k-1\\}$. Dejean’s conjecture
was finally proven by Currie and Rampersad [6] and [16], independently. Other
interesting classes that have been studied include Sturmian words [3],
balanced words [15], and many others.

In this note we determine the repetition threshold for Rote sequences. Along
the way we construct a certain infinite binary word $\bf q$ and examine some
of its properties.

##  2 Lower bound

Let us extend the notion of Rote word to finite words: we say a finite word
$z$ of length $n$ is Rote if $\rho_{z}(i)\leq 2i$ for $1\leq i\leq n$.

######  Proposition 1.

Every Rote word of length $>38$ (and hence every infinite Rote word) has a
finite factor of exponent $\geq 5/2$.

###### Proof.

We perform breadth-first or depth-first search over the tree of all finite
Rote words of critical exponent $<5/2$. This tree is finite and the longest
words are of length $38$. They are

$00110011010011001001101001100100110010,00110011010011001001101001100100110011,$

and the six words formed by reversal and complementation of these two. ∎

##  3 The words $\bf p$ and $\bf q$

It now remains to see that the bound of $5/2$ is optimal; that is, there
exists an infinite binary word of critical exponent $5/2$ and factor
complexity $2n$.

We describe this word as follows: let $h$ be the morphism defined by
$h(0)=01$, $h(1)=21$, $h(2)=0$. This morphism and its infinite fixed point

${\bf p}=012102101021012101021\cdots$

were studied, for example, in [5]. Next, define another morphism as follows:
$g(0)=011$, $g(1)=0$, and $g(2)=01$. The word we are interested in is ${\bf
q}:=g({\bf p})$. Our main result is therefore the following:

######  Theorem 2.

The infinite word ${\bf q}$ is a Rote word with the optimal critical exponent
$5/2$.

The presence of the factor $1001\,1001\,10$ shows that $\operatorname{ce}({\bf
q})\geq 5/2$. Thus, it remains to prove the following two claims:

  * (1)

$\bf q$ contains no factors of exponent $>5/2$: it is $(5/2)^{+}$-power-free;

  * (2)

$\bf q$ has factor complexity $2n$.

To prove both these claims, we use the the theorem prover Walnut, [12, 20], a
free software package that can rigorously prove or disprove many assertions
about certain kinds of sequences. It is discussed in the next section.

The word $\bf q$ was very recently studied by Dvořáková, Ochem, and Opočenská
[10]; they also proved, as we have, that $\bf q$ is $(5/2)^{+}$-power-free,
using a detailed analysis of return words. The reader may enjoy comparing
their proof with ours. We thank Pascal Ochem for informing us about their
work.

##  4 Proving theorems with Walnut

Both claims (1) and (2) above are, in principle, decidable because we know
that $\bf p$ is an automatic word in the Pisot-$4$ numeration system described
in [5]. In particular, there is a $72$-state automaton computing ${\bf p}[n]$
in the following sense: the input is $n$ expressed in the $P4$ numeration
system, and the output associated with the last state reached is ${\bf p}[n]$.
Therefore, by a classic result of Bruyère et al. [2], we know that there is an
algorithm to translate a first-order logical formula $\varphi$, using addition
and indexing into ${\bf p}$, into an automaton accepting the representation of
the natural number values making $\varphi$ true. If there are no free
variables, this gives us a way to rigorously prove or disprove claims merely
by computing the corresponding automata.

Walnut, a free software system originally created by Hamoon Mousavi, [12], and
discussed in more detail in [20], implements this algorithm. As an example,
let us find a DFAO (deterministic finite automaton with output) computing $\bf
q$. We can get it from the DFAO for $\bf p$ because, as proved in [5], the
count of each letter appearing in prefixes of $\bf p$ is also computable by an
automaton, in a synchronized sense [19]: there are automata $A_{i}$, for
$i\in\\{0,1,2\\}$ that on input $n$ and $y$ in parallel, both expressed in the
$P4$ system, and accepts if and only if $y=|{\bf p}[0..n-1]|_{i}$, the number
of occurrences of $i$ in the prefix of length $i$. Here the automaton $A_{0}$
has $43$ states, $A_{1}$ has $34$ states, and $A_{2}$ has $48$ states.

Thus we can compute ${\bf q}[n]$ with an automaton by determining the position
of $\bf p$ that gives rise to the symbol, using these synchronized automata.
This gives an automaton of $72$ states for $\bf q$ in the $P4$ system, which
can be computed with the following Walnut code.

    def imlen "?msd_pisot4 Ex,y,z $paut0(n,x) &
       $paut1(n,y) & $paut2(n,z) & w=3*x+y+2*z":
    #159 states
    def se "?msd_pisot4 ~En $imlen(n,w)":
    #72 states
    combine Q se:

As an application, let us compute the abelian complexity of $\bf q$. (Recall
that the abelian complexity of a sequence is the number of distinct blocks of
length $n$, up to rearrangement of symbols.) Since $\bf q$ is defined over a
binary alphabet, this amounts to determining how many different possibilities
there are for the number of $0$’s in a length-$n$ factor of $\bf q$. And this,
in turn,

Next, we count the number of $0$’s in a prefix of $\bf q$ of length $n$, and
an arbitrary factor of length $n$ as follows:

    def pref0 "?msd_pisot4 (n=0&p=0) |
       (Ew,x $imlen(p-1,w) & $imlen(p,x) & n>w & n<=x)"::
    # 182 states
    def count0 "?msd_pisot4 Ew,x $pref0(i,w) & $pref0(i+n,x) & z+w=x":
    #20474 states

Next, we determine an automaton that accepts $n$ and $x$ in parallel, if $x$
is the number of $0$’s in some factor of $\bf q$ of length $n$:

    def range0 "?msd_pisot4 Ei $count0(i,n,x)":
    # 728 states

We are now ready to prove the following result.

######  Theorem 3.

The abelian complexity function of $\bf q$ takes the values $\\{1,2,3,4\\}$
and these are the only possibilities. Furthermore, there is a DFAO of $341$
states computing it.

###### Proof.

First let us show the abelian complexity never takes the value $5$:

    eval val5 "?msd_pisot4 ~Ex,y,n $range0(n,x) & $range0(n,y) & y=x+4":

and Walnut returns TRUE.

Next, let us determine the automaton computing the abelian complexity function
of $\bf q$:

    def val1 "?msd_pisot4 Ax,y ($range0(n,x) & $range0(n,y)) => x=y"::
    def val2 "?msd_pisot4 Ax,y ($range0(n,x) & $range0(n,y) & x>=y) =>
       (x=y|x=y+1)"::
    def val3 "?msd_pisot4 Ax,y ($range0(n,x) & $range0(n,y) & x>=y) =>
       (x=y|x=y+1|x=y+2)"::
    def val4 "?msd_pisot4 Ax,y ($range0(n,x) & $range0(n,y) & x>=y) =>
       (x=y|x=y+1|x=y+2|x=y+3)"::
    def abel2 "?msd_pisot4 $val2(n) & ~$val1(n)"::
    # 336 states
    def abel3 "?msd_pisot4 $val3(n) & ~$val2(n)"::
    # 340 states
    def abel4 "?msd_pisot4 $val4(n) & ~$val3(n)"::
    # 333 states
    combine BEL val1=1 abel2=2 abel3=3 abel4=4::
    # 341 states

The automaton BEL is the desired one computing the abelian complexity function
of $\bf q$, and it has $341$ states, too large to display here. ∎

##  5 The main result

Once we have an automaton that computes ${\bf q}$, we can computationally
prove conditions (1) and (2) as follows, at least in principle. Let’s start
with condition (1). It suffices to give a first-order logical statement
asserting the nonexistence of factors of exponent $>5/2$. We can do this as
follows:

$\neg\exists i,n\ n\geq 1\wedge\forall t,u\ (t\geq i\wedge t\leq i+3n/2\wedge
u=t+n)\implies{\bf q}[u]={\bf q}[v].$

This statement, suitably translated into Walnut, looks like

    eval check52plus "?msd_pisot4 ~Ei,n n>=1 &
       At,u (t>=i & 2*t<=2*i+3*n & u=t+n) => Q[t]=Q[u]":

To handle condition (2), there are multiple possible approaches. One is the
following: we compute a linear representation for the number of novel factors
of length $n$ appearing in ${\bf q}$; these are factors ${\bf q}[i..i+n-1]$
that never appeared previously. Then the number of novel factors is the factor
complexity at $n$. To do this, we use the following Walnut code:

    def factoreq "?msd_pisot4 Au,v (u>=i & u<i+n & u+j=v+i) => Q[u]=Q[v]":
    def novel n "?msd_pisot4 n>=1 & Aj (j<n) => ~$factoreq(i,j,n)":
    def twon n "?msd_pisot4 i<2*n":

This would give us a linear representation for the factor complexity function
$\rho_{n}({\bf q})$, with the exception that it computes $0$ at $n=0$, and a
linear representation for $2n$. We can then check whether these two linear
representations compute the same function using the ideas in [20, p. 58].

However, our attempts to prove (1) and (2) using our $P4$ automaton failed
because of the large number of states involved. To get around this problem, we
use the same approach, but with a different numeration system that is more
“tuned” to the specific word $\bf q$.

Recently the first author and co-authors developed a new technique for
creating addable numeration systems based on morphisms [4]. Using this we can
complete the computational proof of our main theorem, Theorem 2.

###### Proof.

The Dumont-Thomas numeration system associated with the morphism

${h(a)=ab,h(b)=cb,h(c)=a}$

is given by the addressing automaton $\mathcal{N}_{h}$ in Fig. 1(a). The
language recognized by this DFA, ordered in radix order, is the abstract
numeration system DTh. We obtain a DFAO recognizing ${\bf q}$ by adding the
output $x$ for each state $x$ of $\mathcal{N}_{h}$. By the Cayley-Hamilton
theorem, all sequences $(|h^{n}(u)|)_{n\geq 0}$ obey the recurrence relation
given by the characteristic polynomial $P(X)=X^{3}-2X^{2}+X-1$ of the
incidence matrix

$M=\begin{pmatrix}1&1&0\\\ 0&1&1\\\ 1&0&0\end{pmatrix}$

of the morphism $h$. It turns out $P$ is the irreducible monic polynomial of
the Pisot number

$\theta=\frac{2+\sqrt[3]{\frac{25+3\sqrt{69}}{2}}+\sqrt[3]{\frac{25-3\sqrt{69}}{2}}}{3}\approx
1.7548776662466916.$

Without too much surprise, the number $\theta$ is the same Pisot number used
to define the greedy numeration system $P4$. To compute the addition relation
for DTh, we construct the sequence automaton $\mathcal{A}_{h}$ given in Fig.
1(b) by associating the sequence of lengths of the associated prefixes with
each symbol on a transition of the addressing automaton as follows:

  * •

it is the null sequence $(0)$ for the symbol $0$

  * •

for the symbol $1$ it is the sequence $(a_{n})=(|h^{n}(a)|)_{n\geq 0}$
starting from state $a$ as $h(a)=ab$ and the sequence
$(c_{n})=(|h^{n}(c)|)_{n\geq 0}$ starting from state $b$ as $h(b)=cb$.

Given the recurrence relation ${u_{n+3}=2u_{n+2}-u_{n+1}+u_{n}}$, it is
sufficient to compute the first $3$ values of each sequence. We do so using
the incidence matrix and the initial length 1 for each letter $a,b,c$.

$\begin{array}[]{cccc | cccc}n&0&1&2&3&4&5&\cdots\\\ \hline\cr a_{n}&1&2&4&7&12&21&\cdots\\\ b_{n}&1&2&3&5&9&16&\cdots\\\ c_{n}&1&1&2&4&7&12&\cdots\\\ \end{array}$

We recognize the sequence A005251 from the OEIS [13] for both $(a_{n})$ and
$(c_{n})$.

$a$$b$$c$01100 (a) Addressing automaton $\mathcal{N}_{h}$

$a$$b$$c$0:$(0)$1:$(a_{n})$1:$(c_{n})$0:$(0)$0:$(0)$ (b) Sequence automaton
$\mathcal{A}_{h}$

Figure 1: Addressing and sequence automata for ${h(a)=ab,h(b)=cb,h(c)=a}$

Combining techniques from Frougny and Solomyak [11] to techniques from Bruyère
and Hansel [1], one can construct a DFA recognizing the addition relation
$\\{(x,y,z)\,:\,x+y=z\\}$. That is, the system DTh is addable, to use the
terminology from [14]. For more details and a practical tool to compute this
addition automaton, refer to [4].

To construct a numeration system for ${\bf q}=g({\bf p})$, we first consider
the length of images of $|g(a)|=|011|=3$, $|g(b)|=|0|=1$, and $|g(c)|=|01|=2$
and use them as initial values to construct new sequences for an _inflated_
version ${\bf p}^{\prime}$ of ${\bf p}$—its image by $g^{\prime}(a)=a12$,
$g^{\prime}(b)=b$, $g^{\prime}(c)=c3$. By construction ${\bf
q}=g^{\prime\prime}({\bf p}^{\prime})$ where
$g^{\prime\prime}(a)=g^{\prime\prime}(b)=g^{\prime\prime}(c)=0$ and
$g^{\prime\prime}(1)=g^{\prime\prime}(2)=g^{\prime\prime}(3)=1$.

$\displaystyle{\bf p}$
$\displaystyle=abcbacbabacbabcbabacbabcbacbabcbabacbabcbacbabacbabcbacbabcbabacbabcba\cdots$
$\displaystyle{\bf p}^{\prime}$
$\displaystyle=a12bc3ba12c3ba12ba12c3ba12bc3ba12ba12c3ba12bc3ba12c3ba12bc3ba12ba12\cdots$

$\begin{array}[]{cccc | cccc}n&0&1&2&3&4&5&\cdots\\\ \hline\cr a^{\prime}_{n}&3&4&7&13&23&40&\cdots\\\ b^{\prime}_{n}&1&3&6&10&17&30&\cdots\\\ c^{\prime}_{n}&2&3&4&7&13&23&\cdots\\\ \end{array}$

We recognize the sequence A137495 from OEIS for both $(a^{\prime}_{n})$ and
$(c^{\prime}_{n})$. Replacing the sequences $(a_{n})$ and $(c_{n})$ by
$(a^{\prime}_{n})$ and $(c^{\prime}_{n})$ inside $\mathcal{A}_{h}$ provides a
new sequence automaton for the positions with letters $a$, $b$ and $c$ in
${\bf p}^{\prime}$. To obtain a numeration system for ${\bf p}^{\prime}$, it
is sufficient to provide new transitions to reach letters $1$, $2$ and $3$,
which are all at bounded distance of a support letter (given by $g^{\prime}$).
To do so, we first replace the letter $1$ by the letter $3$ to preserve radix
order, and we allow the last letter of a number representation to add an
increment of $1$ or $2$ to its position and add a new state to represent the
final symbol $1$ in ${\bf q}$. We then modify each transition pointing to $a$
or $c$ and replicate it via a transition to the new state. Doing so, we obtain
the addressing automaton $\mathcal{N}_{\bf q}$ depicted in Fig. 2(a) that
defines the new numeration system for ${\bf q}$. A DFAO for ${\bf q}$ is
obtained by adding $g^{\prime\prime}(x)$ as output to each state $x$.
Considering the new recurrence relation given by $XP(X)=X^{4}-2X^{3}+X^{2}-X$,
we associate ultimately null sequences $\alpha_{i}=(i,0,0,0,\ldots)$ with the
increment transitions. This way, we obtain the sequence automaton
$\mathcal{A}_{\bf q}$ depicted in Fig. 2(b), from which we compute the
addition relation DFA for $\\{(x,y,z)\,:\,x+y=z\\}$ using the same technique
as before—it is still possible as the recurrence relation is ultimately Pisot.

$a$$b$$c$$1$031,230101,2 (a) Addressing automaton $\mathcal{N}_{\bf q}$

$a$$b$$c$$1$0:$(0)$3:$(a^{\prime}_{n})$1:$\alpha_{1}$,2:$\alpha_{2}$3:$(c^{\prime}_{n})$0:$(0)$1:$\alpha_{1}$0:$(0)$1:$\alpha_{1}$,2:$\alpha_{2}$
(b) Sequence automaton $\mathcal{A}_{\bf q}$

Figure 2: Addressing and sequence automata for ${\bf q}$

This gives a family of relatively small automata: the DFA for the numeration
system and the DFAO for ${\bf q}$ both have 4 states, and the addition
relation DFA has 143 states. With this new representation, manipulating ${\bf
q}$ with Walnut is very fast and we conclude the desired results, as follows:

    eval check52plus "?msd_mor ~Ei,n n>=1 & At,u (t>=i & 2*t<=2*i+3*n & u=t+n)
       => Mor[t]=Mor[u]":
    def factoreq "?msd_mor Au,v (u>=i & u<i+n & u+j=v+i) => Mor[u]=Mor[v]":
    # 125 states
    def novel n "?msd_mor n>=1 & Aj (j<n) => ~$factoreq(i,j,n)":
    # 120 states
    def twon n "?msd_mor n>=1 & i<2*n":
    # 70 states

and we now check, using a Maple program, that the linear representations
computed by novel and twon are identical. Here Mor is the automaton computing
Q in the new numeration system. ∎

The attentive reader might notice that the addressing automaton
$\mathcal{N}_{\bf q}$ is prefix-closed, as all states are finite. Indeed, it
is related (by exchanging $3$ and $2$ in the label from $b$ to $b$) to the
Dumont-Thomas numeration system associated with the morphism $t(a)=a11b$,
$t(1)=\varepsilon$, $t(b)=c1b$, $t(c)=a11$.

##  6 Additional remarks

######  Remark 4.

We observe that $\bf q$ is uniformly recurrent. Indeed, two factors of length
$n\geq 1$ are separated by at most $7n$ positions.

    def nextgap "?msd_mor Ej i<j & $factoreq(i,j,n) & i+g=j &
       At (i<t & t<j) => ~$factoreq(i,t,n)":
    # 275 states
    def maxgap "?msd_mor Ei $nextgap(g,i,n) &
       Ah (h>g) => ~Ei $nextgap(h,i,n)"::
    # 38 states
    eval uc "?msd_mor Ag,n (n>=1 & $maxgap(g,n)) => g<=7*n"::

And Walnut returns TRUE for this last assertion.

######  Remark 5.

As it turns out, the factor $1001\,1001\,10$ mentioned previously is the only
factor of exponent $5/2$ in $\bf q$. We can prove this with the following
Walnut commands:

    def per "?msd_mor p>=1 & p<=n & $factoreq(i,i+p,n-p)":
    # 719 states
    def exp52 "?msd_mor Ep $per(i,n,p) & 2*n=5*p":
    # 7 states
    eval testlength "?msd_mor Ai,n (n>=1 & $exp52(i,n)) =>
       (n=10 & $factoreq(i,11,10))":

This raises the question of what the asymptotic critical exponent of $\bf q$
is: this is the supremum over all $e$ such that there are infinitely many
distinct factors of exponent $\leq e$. It seems that this asymptotic critical
exponent is the same as that for $\bf p$, but we did not try to prove this,
although it seems likely it can be done using Walnut.

######  Remark 6.

The sequence $\bf q$ contains no palindromes of length $>15$. Indeed, it even
contains no reversible factor of length $>15$, where “reversible” means a
factor whose reverse is also in $\bf q$. This can be proven most simply by
checking all $32$ factors of length $16$.

######  Remark 7.

The set of all finite binary Rote words of critical exponent $\leq 5/2$ seems
to have a certain “rigidity” of structure, reminiscent of the famous Restivo-
Salemi theorem for overlap-free words [17]. For example, it seems like the
number of such words of length $n$ is $\leq 16n$ for all $n\geq 58$. However,
we leave this for another day.

## References

  * [1] V. Bruyère and G. Hansel.  Bertrand numeration systems and recognizability.  Theoret. Comput. Sci. 181 (1997), 17–43.
  * [2] V. Bruyère, G. Hansel, C. Michaux, and R. Villemaire.  Logic and $p$-recognizable sets of integers.  Bull. Belgian Math. Soc. 1 (1994), 191–238.  Corrigendum, Bull. Belgian Math. Soc. 1 (1994), 577.
  * [3] A. Carpi and A. de Luca.  Special factors, periodicity, and an application to Sturmian words.  Acta Informatica 36 (2000), 983–1006.
  * [4] O. Carton, J.-M. Couvreur, M. Delacourt, and N. Ollinger.  Addition in Dumont-Thomas numeration systems in theory and practice.  Arxiv preprint arXiv:2406.09868 [cs.FL]. Available at http://www.arxiv.org/abs/2406.09868, 2024.
  * [5] J. Currie, P. Ochem, N. Rampersad, and J. Shallit.  Properties of a ternary infinite word.  RAIRO Inform. Théor. App. 57 (2023), 1–17.
  * [6] J. Currie and N. Rampersad.  A proof of Dejean’s conjecture.  Math. Comp. 80 (2011), 1063–1070.
  * [7] F. Dejean.  Sur un théorème de Thue.  J. Combin. Theory. Ser. A 13 (1972), 90–99.
  * [8] C. F. Du, H. Mousavi, E. Rowland, L. Schaeffer, and J. Shallit.  Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability.  Theoret. Comput. Sci. 657 (2017), 146–162.
  * [9] L. Dvořáková, K. Medková, and E. Pelantová.  Complementary symmetric Rote sequences: the critical exponent and the recurrence function.  Discrete Math. & Theoret. Comput. Sci. 22(1) (2020), DMTCS–22–1–20.  `https://dmtcs.episciences.org/6519/`
  * [10] L. Dvořáková, P. Ochem, and D. Opočenská.  Critical exponent of binary words with few distinct palindromes.  Elect. J. Combinatorics 31(2) (2024), #P2.29.
  * [11] C. Frougny and B. Solomyak.  On representation of integers in linear numeration systems.  In M. Pollicott and K. Schmidt, editors, Ergodic Theory of $\mathbb{Z}^{d}$ Actions, Vol. 228 of London Mathematical Society Lecture Note Series, pp. 345–368. Cambridge University Press, 1996.
  * [12] H. Mousavi.  Automatic theorem proving in Walnut.  Arxiv preprint arXiv:1603.06017 [cs.FL], available at http://arxiv.org/abs/1603.06017, 2016.
  * [13] N. J. A. Sloane et al.  The on-line encyclopedia of integer sequences, 2024.  Electronic resource, available at https://oeis.org.
  * [14] J. Peltomaki and V. Salo.  Automatic winning shifts.  Inform. Comput. 285 (2022), 104883.
  * [15] N. Rampersad, Jeffrey Shallit, and Élise Vandomme.  Critical exponents of infinite balanced words.  Theoret. Comput. Sci. 777 (2019), 454–463.
  * [16] M. Rao.  Last cases of Dejean’s conjecture.  Theoret. Comput. Sci. 412 (2011), 3010–3018.
  * [17] A. Restivo and S. Salemi.  Overlap free words on two symbols.  In M. Nivat and D. Perrin, editors, Automata on Infinite Words, Vol. 192 of Lecture Notes in Computer Science, pp. 198–206. Springer-Verlag, 1985.
  * [18] G. Rote.  Sequences with subword complexity $2n$.  J. Number Theory 46 (1994), 196–213.
  * [19] J. Shallit.  Synchronized sequences.  In T. Lecroq and S. Puzynina, editors, WORDS 2021, Vol. 12847 of Lecture Notes in Computer Science, pp. 1–19. Springer-Verlag, 2021\.
  * [20] J. Shallit.  The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words with Walnut, Vol. 482 of London Math. Society Lecture Note Series.  Cambridge University Press, 2023.