## Abstract

The idealized mathematical problem of four bugs in cyclic pursuit starting from a 2-by-1 rectangle is considered, and asymptotic formulas are derived to describe the motion. In contrast to the famous case of four bugs on a square, here the trajectories quickly freeze to essentially one dimension. After the first rotation about the centre point, the scale of the configuration has shrunk by a factor of 10^{427907250}, and this number is then exponentiated four more times with each successive cycle. Relations to Knuth’s double-arrow notation and level-index arithmetic are discussed.

## 1. Introduction

In 1957, Martin Gardner made famous the problem of ‘four bugs on a square’, each one chasing the next at speed 1 (Gardner 1957). By symmetry, the bugs remain always on a square, spiralling into a mutual collision at time 1 if the initial side length was 1. With this in mind, for the first problem of Oxford’s Numerical Analysis Problem Solving Squad in October 2008, L.N.T. assigned the students what looked like a straightforward variation to be worked out numerically on the computer:

J.L., in his first week as a graduate student at Oxford, proved more careful than the professor. The orbits he found were far from straightforward, and at first the rest of the squad thought he might have been misled by numerical error. But he was right, and in this article we shall describe the remarkable paths that the four bugs follow, involving events on space and time scales decreasing to zero at an almost incomprehensible rate governed by a stack of exponentials. It is perhaps no surprise that the bugs circle infinitely often around their midpoint before eventually colliding, but who would have guessed that by the time the first circuit has been completed, the scale of the configuration has shrunk by a factor of 10*Four particles start at t=0 at the vertices of a 2×1 rectangle. Each one chases the particle to its left with speed 1. When does a collision occur?*

^{427907250}? This number is approximately . The second circuit brings four more exponentiations and a shrinkage factor approximately

We elucidate the details of the motion by an asymptotic analysis that connects one configuration of a ‘rectangle dance’ to a similar configuration reappearing later on a smaller scale. The discussion at the end mentions connections to the literature of pursuit problems together with some remarks about very large numbers, level-index arithmetic, and symmetries and sensitive dependences in dynamical systems.

## 2. The rectangle dance

We label the bugs 1, 2, 3 and 4. By symmetry, 1 and 3 will follow the same trajectories at angles differing by *π*, and likewise 2 and 4. So the bugs remain always on a parallelogram, which we take to be centred at the origin. Let us reveal the ending of our drama here at the outset: all four bugs are destined to collide after 1.5 time units. With this end in view, let us redefine the initial time as *t*=*τ*_{0}=−1.5 and track events as *t*→0.

Figure 1*a* shows the motion up to *t*=*σ*_{1}≈−0.328190029216. There are no surprises here. Each bug follows the next, and at the end we see a nice parallelogram. This termination time has been chosen because at this moment, the parallelogram has become a rhombus, with all sides of equal length.

Figure 1*b* continues the story to *t*=*τ*_{1}≈−0.148243863926. We now see that bugs 2 and 3 are getting quite close. If each were chasing the other, there would soon be a collision. However, 3 is chasing 4, not 2. It moves along, oblivious to bug 2, which is continually following but cannot catch up. The termination time in the figure has been chosen since at about this time, the parallelogram has become a rectangle again, with an aspect ratio of about 0.08748.

What happens after this point is that the motion becomes nearly one dimensional. Bug 3 heads for 4 with 2 entrained behind it at a distance of approximately 0.01136323; likewise bug 1 heads for 2 with 4 entrained behind. The two pairs are approaching each other. Figure 2 shows the configuration at the arbitrarily chosen time *t*=−0.03.

Figure 2 may seem to suggest that 1 and 3 will collide. Neither is chasing the other, however, and they do not collide. In fact, at *t*=*σ*_{2}≈−0.011365703053, a rhombus appears for a second time as 3 and 1 pass each other at a distance of approximately 1.193963×10^{−6}. We call this movement ‘dos–a–dos’ (though here, unlike in a square dance, the two particles continue moving ahead after passing each other back-to-back).

At *t*=*τ*_{2}≈−0.00568, a rectangle appears again with bugs 3, 4 at one end and 1, 2 at the other. We call this ‘swing your partner’ (though here, it is just a half-swing as the partner doing the swinging only has eyes for another dancer across the room). The aspect ratio has now shrunk to a very low value. It is approximately 2×10^{−9}.

From here on, the motion is almost exactly confined to one dimension. An infinite sequence of interactions unfolds, rectangle alternating with rhombus. Figure 3 summarizes the situation through the first four rectangle rhombus rectangle cycles.

The first few steps that we have described are readily computed numerically by standard ordinary differential equation (ODE) methods. After this point, the geometries are so extreme that the problem is a perfect one for asymptotics, though challenging. We may summarize our conclusions, based on the asymptotic analysis detailed in the next two sections, as follows. Let *ε*<1 be the width-to-length ratio of a rectangle and *δ*<1 the width-to-length ratio of a rhombus. The motion of the four bugs is controlled by the sequence and for *j*≥2 with our initial condition *ε*_{0}=0.5, *ε*_{j} and *δ*_{j} are extremely close to zero. Section 3 derives the following formulae governing the transitions *δ*_{j}→*ε*_{j} and *ε*_{j}→*δ*_{j+1} in the limits *ε*,*δ*→0. From rhombus to rectangle, there is a halving of the time and space scales,
2.1
and a squaring of the aspect ratio,
2.2

From rectangle to rhombus is where the big contraction occurs. Now the time and space scales shrink in proportion to the aspect ratio of the rectangle:
2.3
while the aspect ratio is *exponentiated*:
2.4

By combining equations (2.2) and (2.4) we can eliminate *δ*_{j+1} and derive an expression relating the aspect ratio of one rectangle to the aspect ratio of the next:
2.5
In all the formulae (2.1)–(2.5), the symbol ∼ has its usual precise mathematical meaning: the ratio of the quantities on the left and right converges to 1 in the limit (*ε*,*δ*→0). It is tempting to try to combine equations (2.2) and (2.4) in the other order to eliminate *ε*_{j} and get an asymptotic formula relating *δ*_{j+1} to *δ*_{j}. However, the presence of the exponential in equation (2.4) implies that *ε*_{j} must be known to more than leading-order accuracy for this to be possible. In fact, our analysis will refine equation (2.2) by deriving further terms in the asymptotic expansion for *ε*_{j}:
2.6
The integral in this expression has the value
2.7
and by combining equation (2.4) with equation (2.6) one can derive the desired relationship:
2.8
with
2.9

## 3. Differential equations and rescaled time

We begin the analysis by formulating a system of ODEs describing the motion of the four bugs. At any time, the bugs lie at the vertices of a parallelogram. Denoting their positions in the *ξ*–*η* plane purely for notational convenience by complex variables *z*_{1}, *z*_{2}, *z*_{3}=−*z*_{1}, and *z*_{4}=−*z*_{2} with *z*=*ξ*+*iη*, we have the equations
3.1
We set
3.2
so that ℓ_{1}≥0 and ℓ_{2}≥0 are the lengths of the sides of the parallelogram, while *ϕ* and *θ* are the angle of orientation and the internal angle, as sketched in figure 4.

Substituting equation (3.1) into equation (3.2) gives, after some manipulation, an equivalent system of ODEs in the variables ℓ_{1},ℓ_{2},*ϕ*,*θ*:
3.3
and
3.4
We note that the orientation *ϕ* plays no role in the evolution of the other variables. Thus, following the schematic approach of figure 3, we shall not consider *ϕ* further.

One conclusion comes immediately from equation (3.3). Since *d*ℓ_{1}/*dt*+*d*ℓ_{2}/*dt*=−2, the perimeter 2(ℓ_{1}+ℓ_{2}) of the parallelogram reduces at the constant rate 4. With initial side lengths 2 and 1 at *t*=−3/2, the figure shrinks to a collision at *t*=0, as stated in §1.

We now take one further step, taking advantage of scale invariance, to reduce the problem from three dependent variables to two. Let the configuration variables be rescaled as
and let time be rescaled logarithmically,
Our problem now is to track the evolution of *s* and *x* as . Equations (3.3) and (3.4) become
3.5
Each of *s* and *x* oscillates between (almost) ±1 as , getting ever closer to these limits with each cycle. When *x*=0, the bugs lie at the corners of a rectangle with aspect ratio
3.6

When *s*=0, the configuration is a rhombus with aspect ratio
3.7

## 4. Asymptotic analysis

The next six pages summarize, rather tersely, our asymptotic analysis. After that we return to a discussion of other aspects of the problem.

Asymptotically, the motion proceeds as a repetition of three stages. In stage 1 an almost flat parallelogram with interior angle close to 0 flips to an almost flat parallelogram with interior angle close to *π* (passing through a rectangle on the way). In stage 2 the ends approach each other so that the parallelogram shortens. In stage 3 the ends get so close that the parallelogram changes from being long and thin to short and fat (passing through a rhombus on the way). These stages are illustrated in figure 5.

### (a) Rectangle to rhombus

We begin with the long thin rectangle *x*(0)=0, *s*(0)=−1+*p*, *p*≪1. We wish to find the value of *x* when *s*=0.

*Stage 1*: During this stage the rectangle flattens (so that *x* changes from 0 to being close to −1, corresponding to the interior angle *θ* expanding from *π*/2 to close to *π*), while remaining long and thin (that is, *s* will stay close to −1, corresponding to *l*_{1}≪*l*_{2}).

Writing *s*=−1+*pu*, gives
4.1
Expanding *x*=*x*_{0}+*px*_{1}+⋯ , *u*=*u*_{0}+*pu*_{1}+⋯ , we find at leading order
so that *u*_{0}(1−*x*_{0})= const. =1 by the initial condition. Then,
4.2
with solution
As ,
4.3
To capture fully the asymptotic behaviour (2.4) we need the next term in the expansion also. After some manipulation, it can be shown that
so that as ,
4.4
This expansion ceases to be asymptotic when *e*^{−4τ}=*O*(*p*), i.e. . At this point, *x* has become close to 1, but *s* is still close to −1.

*Stage 2*: During this stage, the parallelogram shortens while remaining thin. During the whole of stage 2, the four bugs are almost collinear, so that *x* and *s* are both close to −1. As the parallelogram shortens, its interior angle gets closer and closer to *π*, as bug 4 tucks in behind bug 1 and bug 2 tucks in behind bug 3 (figure 2).

Most of stage 2 occurs on a long time scale, but in order to obtain the initial conditions for the evolution, we need to consider first a short timescale that will enable us to match with the solution in stage 1.

We rescale by setting *s*=−1+*pu*, *x*=−1+*py*, . Then,
Here, *u* is slowly increasing while *y* is rapidly decreasing. Expanding *y*∼*y*_{0}+*py*_{1}+⋯ , *u*∼*u*_{0}+*pu*_{1}+⋯ gives, at leading order,
4.5
Matching with equation (4.3) gives *C*=2*e*. At next order
Thus,
4.6
Matching with equation (4.4) gives

Let us now switch to the long time scale . By this time *y* is exponentially small, so that *y*≪*u* and, to all orders in *p*,
so that
4.7
Matching with equations (4.5) and (4.6) gives
Then,
so that
Here, it is crucial to have *u* correct to *O*(*p*) to get the leading-order behaviour of *y*. Matching with equation (4.5) gives
Hence,
4.8
This expansion is valid until , at which point *u*_{0}=*O*(1/*p*).

*Stage 3*: During this stage, the parallelogram finally shortens enough that instead of being long and thin (corresponding to *s*≈−1, *l*_{1}≪*l*_{2}) it becomes short and fat (corresponding to *s*≈1, *l*_{2}≪*l*_{1}). During this stage, it passes through the rhombus (corresponding to *s*=0, *l*_{1}=*l*_{2}).

Set . By this time,
Now set *x*=−1+*κy* with *κ*=2 *e*^{−4/p}/*p*^{2}. Then,
Hence, expanding *s*∼*s*_{0}+*κs*_{1}+⋯ , *y*∼*y*_{0}+*κy*_{1}+⋯ , at leading order
Matching with equations (4.7) and (4.8) gives *a*=1/2, *μ*=2. We finally reach the rhombus when *s*_{0}=0, which occurs for , at which point *y*_{0}=4 *e*^{2}. Thus, if *x*=−1+*k* when *s*=0, then
4.9

### (b) Rhombus to rectangle

The rhombus lies in the middle of stage 3, as the parallelogram switches from being long and thin to short and fat. We can see from figure 5 that after stage 3 we return to stage 1, but with *l*_{1} and *l*_{2} swapped. It is convenient to swap the labels of *l*_{1} and *l*_{2} now (while the configuration is a rhombus so that the labelling makes no difference) so that when we emerge from stage 3 to stage 1 the notation will correspond to that of §3. This switch of labels corresponds to replacing *θ* by *π*−*θ*, so we must replace *x* with −*x*. Thus, we continue in stage 3 with the rhombus *x*(0)=1−*k*, *s*(0)=0, *k*≪1, where we have reset time to zero. We wish to find the value of *s* when *x*=0. Setting *x*=1−*ky* as in stage 3 above gives
and
Expanding *s*∼*s*_{0}+*ks*_{1}+⋯, *y*∼*y*_{0}+*ky*_{1}+⋯, gives, at leading order,
4.10
The expansion breaks down as , when , . To capture the asymptotics fully we need the next-order correction terms. At the next order, we find
and
Hence
and

As , 4.11 and 4.12 where 4.13

*Stage 1*: We have now emerged from stage 3 and returned to stage 1. Thus, we rescale *s*=−1+*ku*, . A similar expansion holds to that in §3. This time, instead of initial conditions, we have the matching condition
Expanding *x*=*x*_{0}+*kx*_{1}+⋯, *u*=*u*_{0}+*ku*_{1}+⋯, we find
4.14
and
4.15
for some constant *d*. As
From equations (4.10) and (4.11), as ,
Matching gives
At the next order, we find
4.16
and
4.17
As ,
4.18
4.19
Matching equation (4.19) with equation (4.12) gives
i.e. *c*_{1}=*e*^{−2}−*e*^{−1}. We find that when *x*=0,
Thus, if we set *s*=−1+*p* when *x*=0, then
4.20
Equations (4.9) and (4.20) now allow us to iterate from . Note that in such an iteration, the *O*(*k*^{2}) terms in equation (4.20) are needed to get the correct leading-order behaviour in equation (4.9).

To translate from *k* and *p* to *δ* and *ε* we recall that for the rectangle, when *l*_{2}≪*l*_{1},
while for the rhombus with *θ*≪1, , so that
Thus,
4.21
Using equation (4.21) in equations (4.20) and (4.9) leads to equations (2.4) and (2.6). Finally, we determine the time taken for the transitions from rectangle to rhombus and vice versa. For the rectangle to rhombus transition, the majority of the time is spent in stages 2 and 3, and the transition time from *x*=0 to *s*=0 is . Translating back to unstretched time, this gives *σ*_{j+1}∼*p*_{j}*τ*_{j}/2∼*ϵ*_{j}*τ*_{j}, which is equation (2.3). For the rhombus to rectangle transition, the majority of the time is spent in stage 3, and the transition time from *s*=0 to *x*=0 is . Translating back to unstretched time, this gives *τ*_{j}∼*σ*_{j}/2, which is equation (2.1).

## 5. Discussion

For the history of pursuit problems, a very readable reference is Nahin’s recent book *Chases and Escapes* (Nahin 2007). Such problems apparently originated with the French mathematician, astronomer and marine scientist Pierre Bouguer, who published a paper in 1735 on the problem of a pirate ship chasing a merchant vessel. Thus, the fundamental paradox underlying the present paper is nearly three centuries old: if A chases B with both moving at the same speed, then, in general, A will be swung around by B but will never catch it.

Problems of *cyclic* pursuit, with each particle chasing the next, seem to have originated with three bugs (or dogs) on a regular triangle in a Cambridge University tripos exam of 1871, and in published form in a paper 6 years later by Edouard Lucas. The generalization to a regular *n*-gon became familiar in the 1950s through publications by, among others, H. Steinhaus, L. A. Graham, J. C. Clapham and M. Gardner as mentioned before. Deviations from regular polygons appeared with Frank Morley as published in a textbook of Harry Bateman in 1918. A key paper on this problem was published by Klamkin & Newman (1971). These authors found that like our parallelograms, irregular triangles quickly degenerate to nearly one dimension and undergo an infinite sequence of interactions on smaller and smaller scales until finally all three particles collide together simultaneously. (Having understood figure 5, the reader will find it easy to work out the analogous moves for triangles.) The parallelogram and triangle problems are of similar complexity: in each case, the shape at each time is determined by two parameters, and a single parameter is enough to describe the cyclically recurring extreme shapes (rhombus and rectangle; thin and fat isosceles triangles). The key contribution of the present paper when compared with Klamkin and Newman is an explicit description of the orbits with asymptotic analysis to make them quantitative.

Numerical simulations began years ago; we note in particular a paper by Behroozi & Gagnon (1975). A more recent paper of interest is by Richardson (2001). But the four-bug problem beautifully illustrates that not everything can be done by numerical simulation.

The extraordinarily large numbers we have encountered defy one’s intuition. For example, consider the formula 5.1 Of course, this equation is not mathematically valid; a correct formula would be Yet, if 428000000 represents a number known only to three digits of accuracy, then the two sides of formula (5.1) are the same after all. Further down the stack, the choice of exponents makes even less difference, so for example, the mathematically erroneous equation 5.2 in which the two sides differ by a quantity that is unimaginably large, is again quite valid if you only know three digits of the top exponent.

Another mathematically invalid equation that is nevertheless almost incomprehensibly close to correct for these giant numbers is
5.3
(Strictly speaking the exponent on the right should be 10 raised to a power that matches in the first 428000000 digits after the decimal point.) In general, if *B* is a very large number represented by a stack of exponentials as in equation (5.2), then to very good approximation
5.4
the latter equation reflecting the fact that although the numbers appearing in the lower reaches of a stack of exponentials do not make much difference, the height of the stack always matters. It is interesting to note the similarity of equation (5.4) with the equations
5.5
which serve as shorthand for two of the discoveries of Georg Cantor (1845–1918) that shocked his contemporaries but soon became a standard and indispensable part of mathematics. Cantor proved that some sets that one might expect to differ in size have in fact the same cardinality as defined by one-to-one correspondence: thus ‘’ reflects the fact that, for example, the numbers of points on a line and in a plane are equal. Other infinite sets, however, are truly different in cardinality, and in particular, the set of subsets of an infinite set *S* is always larger than *S* itself: ‘’. Comparing equations (5.4) and (5.5), we see that the kinds of numbers arising in the analysis of the four-bug problem are so large that, to good approximation, they have some of the same properties as infinity.

There is a literature on stacks of exponentials going back at least to Hardy and Littlewood, and one of the contributions is a double-arrow notation due to Knuth (1976). An example makes the definition clear:
5.6
(It is a safe bet that the reader has never seen the ‘’ symbol used to connect two quantities that differ more vastly than these.) Thus, the scale of the four-bug configuration shrinks by factors of about
5.7
after rotations. Knuth’s numbers are integers, but a related development for real numbers arises in computer science. The standard method for computing with real numbers is floating point arithmetic, in which a fraction and an exponent are each represented by binary numbers, leading to a system of numbers mimicking scientific notation with about 16 digits of relative accuracy and magnitudes roughly from 10^{−308} to 10^{308} (Overton 2001). Since the 1980s, a different representation known as *level-index arithmetic* has been advocated by Clenshaw and Olver and others (Clenshaw & Olver 1984). Here, every number is represented by a stack such as
where the *level* is the number of exponentiations in the stack and the *index* is the top exponent, which lies in [0,1). Thus, in standard level index notation, the four-bug scale after 3,4,5,… rotations shrinks by factors
This system has some appealing properties, but a hardware implementation would hardly get far for the four-bug problem: Clenshaw and Olver recommend that the maximum level be set at 7.

Level index arithmetic also comes with a notion of *generalized precision* for measuring the agreement of two quantities (Clenshaw & Olver 1984). Approximately speaking, *x* and *x*′ agree with generalized precision *α* if their two indices differ by *α* or less. With this terminology, one could make precise statements, for example, about the meaning of the numbers in figure 3 or the symbol ‘≈’ in equation (5.6).

It is also interesting to reflect on the four-bug problem from the point of view of sensitivity of solutions of differential equations to perturbations in the initial data. This paper has highlighted the phenomenon that Martin Gardner’s square is an unstable configuration, at least from one point of view: if you perturb the symmetry ever so slightly, the resulting four-particle configurations change utterly in shape. (The same may or may not go for regular *n*-gons for larger *n*.) Indeed, the four-bug problem as we have posed it with a rectangular initial condition itself possesses a fragile symmetry: any perturbation along the way would quickly eliminate the rectangles and rhombuses.

Thus, the four-bug problem brings to mind the sensitive dependences that are the heart of the subject of chaos, with well-known connections to many scientific problems including the weather and perhaps the climate of planet Earth. One cannot simply say that this system is chaotic: in the original *t*,{*z*_{j}} variables, the trajectories only last for a finite time and the distorted configurations are only distorted in a relative, not absolute sense. One the other hand, after the change to variables we get a system that very likely is chaotic. Matters of stability versus chaos are among the fundamental questions one would ask in a scientific application related to the four-bug problem, such as the analysis of a collection of animals or robots like those recently investigated by Marshall *et al.* (2004, 2006). For particles connected gravitationally rather than by our constant-speed pursuit law, such questions have attracted interest for a long time (Diacu & Holmes 1996).

## Acknowledgements

We have benefited from discussions with the other 2008 Problem Squad members Almut Eisenträger, Jen Pestana and Hao Wang. L.N.T. would also like to thank Mr and Mrs E. McLoughlin of Meols, Wirral, UK, for inviting him to a square dance shortly before this project began. This publication is based on work supported in part by Award no. KUK-C1-013-04, made by King Abdullah University of Science and Technology (KAUST).

- Received October 1, 2010.
- Accepted October 14, 2010.

- This journal is © 2010 The Royal Society