text:
# Self-organized patterns and traffic flow in colonies of organisms: from bacteria and social insects to vertebrates11footnote 1A longer version of this article will be published elsewhere

## 1 Introduction

In general, pattern is a general term for any recognizable regularity in the observed data. By “spatial” pattern we mean some kind of regularity in the arrangment of the constituents in space . Similarly, when we monitor a time-dependent quantity over a period of time, any possible regularity in the temporal variation may be referred to as a ”temporal” pattern . Moreover, in phenomena where both spatial and temporal regularities occur simultaneously, a decoupling of the analysis of spatial and temporal patterns may not be possible and one has to deal with a spatio-temporal pattern .

Exotic patterns observed in living systems have attracted attention of physicists for a long time . During the development of an organism, i.e., during the process of morphogenesis, cells are known to form specific patterns in tissues that form parts of specific organs or organ systems . However, in this paper we shall consider almost exclusively patterns exhibited by aggregates of organisms in their colonies ; schools of fish and flocks of migrating birds are, perhaps, the most familiar patterns of this type . The cellular patterns in tissues, after an initial transient period, remain practically unchanged for the remaining life period of the organism. In contrast, patterns exhibited by aggregates of organisms are transient; some of these aggregate are short-lived whereas others may persist for days.

Such aggregation is observed in colonies of organisms as simple as single-cell bacteria as well as in colonies of complex multi-cellular vertebrates. All types of locomotion, i.e., aerial, aquatic and terrestrial, of individual organisms can give rise to such aggregation. The population of organisms in the aggregate may vary from tens to millions. These aggregates come in a wide range of shapes and sizes.

The reasons for the formation of such aggregates are now quite well understood. Individual organisms benefit (e.g., escaping predators) from aggregation despite some detrimental effects (e.g., getting infected by contagious disease). However, several fundamental questions regarding the structure and dynamics of these aggregates remain to be answered. For example, (a) what decides the shape of an aggregate and how do these form, (b) how does an aggregate maintain a shape over a period of time, (c) what triggers the changes of shapes of the aggregates, (d) how does fission and fusion of existing aggregates take place , etc.

Encouraged by the success of the conceptual framework of non-equilibrium statistical mechanics in the study of pattern formation in non-living systems , efforts have been made over the last decade to understand pattern formation in living systems by applying the same conceptual tools. It turns out that the aggregates of organisms exhibit richer patterns than those observed in non-living systems; this may be due to the fact that the constituent elements (i.e., the individual organisms) are living objects with many internal degrees of freedom. What makes these living organisms so different from their non-living counterparts is that each living object is an autonomous system that is capable of taking decision which is normally in its own self-interest. Thus, the evolution of the patterns involves a subtle interplay of the dynamical response of the individual organisms to their local surroundings and the global dynamics at the level of the colonies.

On the basis of the formation process, these aggregates can be broadly divided into two classes: (i) aggregates that ”self-organize”, and (ii) aggregates that form in response to external cues such as light or food. There are situations where an external cue nucleates an aggregate, but the aggregate soon grows in size dwarfing the original stimulus . For example, a small school of fish may nucleate around some floating object, but soon the school may grow to such a huge size that the original attractant becomes irrelevant.

In the transient patterns exhibited by aggregates of organisms, one can identify two different characteristic time scales of dynamics: the shorter time scale is associated with the reflex and response of individual organisms to their immediate surroundings whereas the whole pattern changes on the longer time scale. In those patterns where terretrial locomotion drives each individual organisms and the pattern consists of long linear stretches, the spatio-temporal organization appears very similar to those in vehicular traffic. Perhaps, the most familiar examples are traffic of ants and termites on trails. In this article we shall also analyse such traffic flows from the perspective of statistical physics .

A common feature of most of the patterns considered in this paper is that each organism can be represented by a (self-propelled) particle and the system, as a whole, may be regarded as a collection of interacting (self-propelled) particles driven far from equilibrium . The steady states of such systems are of current interest in non-equilibrium statistical mechanics . The transition from one such steady state to another, with the variation of parameters, is analogous to phase transitions exhibited by thermodynamic systems in equilibrium. The non-equilibrium phase transitions from one dynamical phase to another remain among the most challenging and least understood frontiers of statistical physics.

## 2 Theoretical approaches for modeling

The fundamental question to be addressed by any theory of patterns in colonies of organisms is the following: how do the individual decisions and local interactions of the individuals influence the global structure (shape, size, etc.), collective dynamics and function of the colony of the organisms? What is the interplay of deterministic and stochastic dynamics?

### 2.1 Different types of theoretical approaches

First of all, the theoretical approaches can be broadly divided into two categories: (I) “Eulerian” and (II) “Lagrangian”. In the Eulerian models individual organisms do not appear explicitly and, instead, one considers only the population densities (i.e., number of individual organisms per unit area or per unit volume). But, the Lagrangian models describe the dynamics of the individual organisms explicitly. Just as “microscopic” models of matter are formulated in terms of molecular constituents, the Lagrangian models of pattern are also developed in terms of the constituent organisms. Therefore, the Lagrangian models are often referred to as “microscopic” models.

In the recent years, it has been emphasized by several groups (see, for example, ref. ) that although the patterns of the colonies are manifest only at the level of the population, the patterns are emergent collective properties that are determined by the responses of the individuals to their local environments and the local interactions among the individual organisms. Therefore, in order to gain a deep understanding of the pattern formation process, it is essential to investigate the linkages between these two levels of biological organization.

Usually, but not necessarily, space and time are treated as continua in the Eulerian models and partial differential equations (PDEs) or integro-differential equations are written down for the time-dependent local collective densities of the organisms . The Lagrangian models have been formulated following both continuum and discrete approaches. In the continuum formulation of the Lagrangian models, differential equations describe the individual trajectories of the organisms .

For developing Lagrangian model, one must first specify the state of each individual organism. The informations which may be needed for the complete specification of the state include, for example, the location (position in space whose dimensionality may be one, two or three), genotype and phenotype, ontogenetic status (age, size and maturity), physiological status (hunger), behavioral status (motivation), etc. . In addition, the environmental informations must also be provided; these may include physical and chemical features of the environment, resources in the environment, etc. The dynamical laws governing the time-evolution of the system must predict the state of the system at a time $`t+\mathrm{\Delta }t`$, given the corresponding state at time $`t`$. The change of state should reflect the response of the system in terms of movement of the individual organisms, their mortality, reproduction (and consequent population growth).

A natural framework for the mathematical formulation of such models is the Newton’s equations for individual organisms; each organism is modelled as a “particle” subjected to some “effective forces” arising out of its interaction with the other organisms in the colony . These forces not only cause their movements but also their alignments. In addition, the organisms may also experience viscous drag and some random forces (“noise”) that may be caused by the surrounding fluid medium. Even in the absence of any direct physical interaction between the organisms (other than the “hard-core” repulsion) there may be some other “effective interactions” which are often referred to as “social” interactions. Some of these interactions capture the effects of communications via chemical signalling; these include, for example, communications among amoeba forming a multicellular slug or those between ants on a trail. This type of models are sometimes formulated in terms of an effective energy landscape. Each organism executes moves in its own energy landscape which, in turn, varies with time because of the movement of the other organisms . In contrast to the forces arising from physical interactions, the social forces do not necessarily obey Newton’s third law! In this paper we shall present an explicit example for such social interactions in the context of the pedestrian dynamics.

Most of the recent Lagrangian models, however, have been formulated on discretized space and the temporal evolution of the system in discrete time steps are prescribed as dynamical update rules using the language of cellular automata (CA)  or lattice gas (LG) . Since each of the individual organisms may be regarded as an agent, the CA and LG models are someties also referred to as agent-based models .

One advantage of the continuum models is that all the tools for analytical treatment of differential- and integro-differential equations are readily available . However, a continuum formulation is usually sensible only for large and dense aggregates but hard to justify for loosely packed aggregates. Moreover, even if a continuum description can be justified, what is even harder to justify is the analytical form of the inter-organism interactions, which are required for writing down the equations of motion for the individual organisms in the Lagrangian approach. Furthermore, the differential equations often turn out to be too complicated to be solved analytically. Numerical solution of these equations require discretization of both space and time. Therefore, the alternative discrete formulations, based on CA and LG, may be used from the beginning .

In fact, there are some further advantages in modeling biological systems with CA and LG. Biologically, it is quite realistic to think in terms of the way each individual organism responds to its local environment and the series of actions they perform. The lack of detailed knowledge of these behavioral responses is compensated by the rules of CA. Usually, it is much easier to devise a reasonable set of logic-based rules, instead of cooking up some effective force for dynamical equations, to capture the behaviour of living organisms. Moreover, because of the high speed of simulations of CA and LG, a wide range of possibilities can be explored which would be impossible with more traditional methods based on differential equations. Furthermore, it may be possible to derive continuum Eulerian models by appropriately coarse-graining agent-based Lagrangian models under some justifiable approximations.

The most satisfactory and convenient analytical approach may be to use a hybrid of the Lagragian-Eulerian methods. One can start with a agent-based microscopic model following the Lagrangian approach and, then, derive corresponding macroscopic Eulerian models from these equations under reasonable approximations. It may be possible to solve the approximate Eulerian equations using the analytical tools for solving PDEs.

### 2.2 Types of ordering in the aggregate

The aggregates formed by the organisms can exhibit different types of ordered structures depending on the individual and/or collective features as well as external environmental conditions.

Some aggregates are compact Euclidean objects while others exhibit fractal structure. Among the compact patterns, several different types of ordering have been observed. For example, the positions and orientations of the individual organisms may correspond to those of non-spherical molecules in a crystal. However, most often, the positions of the organisms do not form a regular lattice but they are all oriented more or less in the same direction; some of this type of structures of the aggregates are analogues of nematic liquid crystals . In some other aggregates like, for example, swarms of mosquitoes, there is no spatial or orientational ordering inside the aggregate although the aggregate persists.

It has been realized for quite some time that, in reality, swarms have a finite size. Therefore, attempts should be made to obtain localized patterns  or propagating bands , rather than propagating surfaces, to capture migrating finite colonies.

## 3 Patterns of aggregates of cells and uni-cellular organisms

Various species of uni-cellular organisms, e.g., bacteria, amoeba, etc., form aggregates with wide varieties of patterns. Moreover, some types of cells, which normally form parts of multi-cellular organisms, are also capable of forming interesting patterns when these are isolated from the organism and grown in cultures.

### 3.1 Patterns of bacterial colonies in biofilms

The microbial biofilms pose not only intellectual challenge to physicists interested in the patterns of bacterial colonies but also of practical interest in microbiology. For example, the dental plaques, the bacterial films formed inside water pipes, etc. are examples of microbial biofilms. The growth of such structures have been invesigated using CA approaches .

Normally, in the laboratory, bacterial colonies are grown on substrates with a high nutrient level and intermediate agar concentration. Patterns of the aggregates formed in colonies grown in such comfortable conditions are compact. However, harsh conditions for bacterial colonies can be created, for example, by using low level of nutrients; aggregates of bacteria formed in such environments can be very complex and interesting from the point of view of pattern formation . Hydrodynamics is also likely to play some role in the growth of the bacterial colonies in wet conditions .

The colonies of Proteus mirabilis form circular swarms that have a terrace-like structure. Modeling such swarms have been attempted so far following, to our knowledge, only Euclidean approach . Very recently, Indekeu and Giuraniuc  have developed a CA model of “nutrient-limited aggregation” and growth of bacterial towers. The three-dimensional system is modeled as a simple cubic lattice where each site can be either empty or occupied by a bacterium or nutrient or water. Chemotaxis, rather than diffusion, drives the growth process.

There are speculations as to the potential applications of the new understanding of the mechanisms of pattern formation in bacterial colonies to synthesize systems, which are too complicated to produce by conventional methods, through self-organization .

### 3.2 Patterns of aggregates of amoeba; slime molds

The slime mold Dictyostelium discoideum can exist in two different forms, namely, either as a population of individual amoeba or as a multi-cellular organism consisting of thousands of cells . These amoeba feed on other bacteria and can exist as a well dispersed colony of uncorrelated individual organisms when the supply of nutrients is abundant. However, when nutrients become scarce, the amoeba begin a collective restructuring of the colony through communication via chemical signalling. The colony exhibits a sequence of different spatial patterns; the final three-dimensional structure is a fruit body that looks similar to a small mushroom with very large number of spores. The spores get spread out over a large area by wind. When these land in areas with sufficiently high supply of nutrients, they give rise to a new well dispersed population of amoeba.

From the perspective of transient patterns, the intermediate stages of aggregation of the amoeba are most interesting. The initial patterns consist of concentric rings which gradually transform to rotating spirals. At a later stage, the slow movements of the cells towards the centers of such patterns transform the patterns themselves into a system of thin dense streaks.

The aggregation of the amoeba Dictyostelium discoideum was modelled long ago (for example, by Keller and Segel ) using an Eulerian approach (see also ref. for the recent literature on theoretical models). Kessler and Levin  have developed a discrete CA-type model to study these spatial patterns. Each cell was represented by a two-state automaton (a “bion”) which is capable of measuring the concentration and concentration gradients of cAMP as well as sense the presence of nearby bions.

In the Kessler-Levin model , initially, a random fraction of the sites (typically $`5`$-$`20`$ percent) of a square lattice are occupied by the bions. In addition, cAMP concentration $`c`$ was assumed to obey a discretized diffusion equation on the lattice. Each bion remains in the state $`0`$ until it detects a local concentration above a predetermined threshold. As soon as the local cAMP concentration exceeds the threshold, the bion makes a transition to the state $`1`$ and emits an amout $`\mathrm{\Delta }c`$ of cAMP over the next $`\tau `$ time steps. Then the bion remains in a quiescent state $`2`$ for the next $`t_R`$ time steps before reverting back to the state $`0`$; in the quiescent state the bion remains immune to further excitation.

The rule for the movement of the individual cells in the Kessler-Levine model  is as follows: for a cell located, at a given time step $`t`$, at the lattice site $`i,j`$, the discretized gradients in the concentrations $`c`$ of cAMP are computed using

$$(c)_x=(c_{i+1,j}^{(t)}c_{i1,j}^{(t)})/2$$

$$(c)_y=(c_{i,j+1}^{(t)}c_{i,j1}^{(t)})/2$$

If the cell is in the excited state $`1`$ and if at least one of the two gradients exceeds the predetermined threshold, the cell attempts to move to the next neighbouring lattice site with the higher concentration of cAMP in that direction. If gradients in both the directions exceed the threshold, the cell attempts to move in the direction determined by the diagonal in between those two directions of increasing cAMP concentration. However, the attempt of hopping is successful only if the target site is not occupied by any other cell. Each cell can move only once in each excitation cycle. Carrying out computer simulations of this model, Kessler and Levin  observed the spiral spatial patterns characteristic of the aggregation during the formation of the multicellular slug. A more detailed CA model, which is intended to account for the patterns at different stages of evolution, has been developed more recently by Savill and Hogeweg .

### 3.3 Patterns in colonies of myxobacteria

Myxobacteria form large clusters and move like a pack of wolves. Each individual myxobacterium preys on several other microorganisms. In contrast to communication system based on the diffusible morphogens in Dictyostelium discoideum, the myxobacteria use an altogether different mechanism of communication where cells communicate with each other by direct physical contact. Periodic waves of movements, called ripples, have been observed in these colonies. However, in spite of superficial similarities, there are crucial differences in the properties of these ripples and similar patterns observed in cellular slime mold Dictyostelium discoideum. In particular, the colliding wave fronts in case of Dictyostelium discoideum annihilate each other whereas the waves in the colonies of myxobacteria can pass through each other. This phenomenon has been reproduced by a model , formulated in the spirit of Lagragian approach, where the trajectories of the individual myxobacteria are described by a set of Langevin-like equations.

### 3.4 Pattern of aggregates of fibroblasts

Fibroblasts are a special type of cells found in connective tissues. In the laboratory these cells can be extracted from their natural locations and their in-vitro aggregation can be studied using cultures on a petri dish. The two-dimensional colonies of such cells have been found to form patches where each patch consists of a single layer of hundreds of fibroblasts with a single axis of orientation. The competing contiguous patches eventually merge into a large array with one single axis of orientation.

A CA model for this pattern formation by fibroblasts was developed by Edelstein-Keshet and Ermentrout . Each of the lattice sites could be either empty or occupied by a cell. Each cell is assigned an orientation and a state of binding. The orientation of a cell can be denoted by an arrow; the direction of the arrow determines the direction of the movement of the cell in the next time step. The state of binding (i.e., whether or not the cell is bound to an aggregate) determines whether or not it is allowed to move. However, both the orientation and the state of binding are dynamic variables that can change with time.

On a discrete lattice, however, the arrow can point in only a finite set of discrete directions. For example, implementing the model on a square lattice, Edelshtein-Keshet and Ermentrout  allowed the arrow to be pointed towards any of eight neighbouring sites surrounding it (i.e., the four nearest-neighbour as well as the four next nearest-neibour sites). Consequently, each cell could change its orientation by an angle that would be an integral multiple of $`45^{}`$. For the sake of simplicity, only two discrete states of binding are assumed; the cell is either bound to an aggregate or unbound (i.e., not part of any aggregate). Therefore, the total number of possible states of each cell is twelve while that of each lattice site is thirteen.

Starting from a homogeneous state with random orientations, the state of the system is updated at each discrete time step according to the following rules:
(i) an unbound cell reorients by one angular unit (e.g., $`45^0`$ on a square lattice) with probability $`p_0`$,
(ii) an unbound cell may reverse its motion with probability $`p_R`$,
(iii) if an unbound cell comes in contact with another cell or group of cells, the probabilty of binding and aligning is $`p_A`$ if the angle of contact is small enough; otherwise the approaching cell reverses its direction and moves away,
(iv) bound cells do not move; the probability that a bound cell detaches from a group is $`p_D`$.

By carrying out computer simulations, Edelstein-Keshet and Ermentrout  demonstrated that this simple model captures the essential qualitative features of the aggregation process observed in the in-vitro experiments.

## 4 Patterns in social insect colonies

From now onwards, in this paper we shall study patterns of the aggregates formed by multi-cellular organisms. We begin with the simpler (and smaller) organisms and, then, consider those of organisms with larger sizes and more complex physiology.

Termites, ants, bees and wasps are the most common social insects, although the extent of social behavior, as compared to solitary life, varies from one sub-species to another . The ability of the social insect colonies to function without a leader has attracted the attention of experts from different disciplines . Insights gained from the modeling of the colonies of such insects are finding important applications in computer science (useful optimization and control algorithms) , communication engineering , artificial “swarm intelligence”  and micro-robotics  as well as in management .

### 4.1 Ant-trail formation

Ants communicate with each other by dropping a chemical (generically called pheromone) on the substrate as they move forward . Although we cannot smell it, the trail pheromone sticks to the substrate long enough for the other following sniffing ants to pick up its smell and follow the trail. This process is called chemotaxis .

Rauch et al. developed a continuum model, following a hybrid of the Lagrangian and the Eulerian approaches in terms of an effective energy landscape. They wrote one set of stochastic differential equations for the positions of the ants and another set of PDEs for the local densities of pheromone.

Suppose a set of “particles”, each of which represents an ant, move in a potential field $`U[\sigma (x)]`$, where the potential at any arbitrary location $`x`$ is determined by the local density $`\sigma (x)`$ of the pheromone field. Consequently, each “particle” experiences an “inertial”force $`\stackrel{}{F}(x)=U(x)`$. Each “particle” is also assumed to be subjected to a “frictional force” where “friction” merely parametrizes the tendency of an ant to continue in a given direction: a smaller “friction” implies that the ant’s velocity persists for a longer time in a given direction. The equation of motion for the “particles” (stochastic differential equation) are assumed to have the form

$$\ddot{x}=\gamma \dot{x}U[\sigma (x)]+\eta (t)$$
(1)
where $`\eta (t)`$ is a Gaussian white noise with the statistical properties

$$\eta (t)=0$$
(2)
and

$$\eta (t)\eta (t^{})=\frac{1}{\beta }\delta (tt^{})$$
(3)
The strength $`1/\beta `$ of the noise determines the degree of determinacy with which the particle would follow the gradient of the local potential; the larger the value of $`\beta `$ the stronger is the tendency of the particle to follow the potential gradient.

Thus, the movement of an ant may be described as the noisy motion of a particle in an “energy landscape”. However, this energy landscape is not static but evolves in response to the motion of the particle as each particle drops pheromone at its own location at a rate $`g`$ per unit time. Assuming that pheromone can diffuse in space with a diffusion constant $`D`$ and evaporate at a rate $`\kappa `$, the equation governing the pheromone field is given by

$$\frac{\sigma (x)}{t}=D\sigma (x)+g\rho (x)\kappa \sigma (x)$$
(4)
where $`\rho (x)`$ is the local density of the particles at $`x`$. Finally, Rauch et al. assumed that the function $`U[\sigma (x)]`$ has the form

$$U[\sigma (x)]=\mathrm{ln}\left(1+\frac{\sigma }{1+\delta \sigma }\right)$$
(5)
where $`1/\delta `$ is called the capacity.

Watmough and Edelstein-Keshet  introduced a CA model to study the formation of ant-trail networks by foraging ants. In this model, each ant is described by its discrete position and velocity on a discrete. The rules for updating the positions and velocities of the ants as well as the pheromone contration on the trail are as follows:
(i) The ants move at a fixed speed; if the ant is a forager and not following a trail, its movements are random.
(ii) Each ant deposits a trail pheromone at a constant rate as it moves.
(iii) The trail pheromone also evaporates at a constant rate.
(iv) The probability $`p_{\mathrm{}}(c)`$ per unit time that an ant will keep following a trail (and not loose the trail) is a function of the local pheromone concentration; the function $`p_{\mathrm{}}(c)`$ is to be specified separately.
(v) When an ant, following a trail, reaches a point of bifurcation it chooses one of the two branches where the rule for choosing the branch is prescribed in the beginning.

Carrying out computer simulations of this CA model, Watmough and Edelstein-Keshet  observed trail patterns that look very similar to real ant-trail networks. The formation of human trails have some similarities with that of ant-trails; some recent models that elucidate the mechanisms of the emergence of human trails will be discussed later in this article.

### 4.2 Phase transition between disordered and ordered foraging

Beekman et al.  pointed out close similarities between phase transitions in non-living systems and that of foraging behaviour on the ant-trail.

A foraging ant that discovers a food source lays down a pheromone trail as it crawls back to its nest. But, the trail would completely disappear unless it is reinforced by other ants before the original pheromone, a volatile chemical, evaporates away. From the study of their model, Beekman et al.  found that the two important relevant parameters are (a) the total number of ants within the colony, and (b) the individual rate at which the ants discover food sources. They showed that (i) when the independent discoveries of food sources are infrequent, a first order (discontinuous) phase transition from a disordered foraging behaviour (i.e., foraging without a pheromone trail) to ordered foraging (i.e., trail-based foraging) takes place as the size of the colony increses; (ii) this transition exhibits hysteresis (i.e., history-dependence): when the rate of individual discoveries of food sources decreases the system chooses one of the two alternative modes of behaviour- either no trail or a well used trail- depending on the initial conditions. In other words, when the independent discoveries of food sources become infrequent, the colonies find it difficult to start a trail but can still sustain an existing trail.

### 4.3 Traffic on ant-trails

In  we have developed particle-hopping models, formulated in terms of a stochastic cellular automaton (CA) (or, lattice gas), which may be interpreted as models of uni-directional and bi-directional traffic flow in an ant-trail. These models are not intended to address the question of the emergence of the ant-trail , but focus on the traffic of ants on a trail which has already been formed. The model generalizes the totally asymmetric simple exclusion process (TASEP)  with parallel dynamics by taking into account the effect of the pheromone.

In our model of uni-directional ant-traffic the ants move according to a rule which is essentially an extension of the TASEP dynamics. In addition, a second field is introduced which models the presence or absence of pheromones (see Fig. 1). The hopping probability of the ants is now modified by the presence of pheromones. It is larger if a pheromone is present at the destination site. Furthermore, the dynamics of the pheromones has to be specified. They are created by ants and free pheromones evaporate with probability $`f`$ per unit time. Assuming periodic boundary conditions, the state of the system is updated at each time step in two stages (see Fig. 1). In stage I ants are allowed to move while in stage II the pheromones are allowed to evaporate. In each stage the stochastic dynamical rules are applied in parallel to all ants and pheromones, respectively.

Stage I: Motion of ants
An ant in a site cannot move if the site immediately in front of it is also occupied by another ant. However, when this site is not occupied by any other ant, the probability of its forward movement to the ant-free site is $`Q`$ or $`q`$, depending on whether or not the target site contains pheromone. Thus, $`q`$ (or $`Q`$) would be the average speed of a free ant in the absence (or presence) of pheromone. To be consistent with real ant-trails, we assume $`q<Q`$, as presence of pheromone increases the average speed.

Stage II: Evaporation of pheromones
Trail pheromone is volatile. So, pheromone secreted by an ant will gradually decay unless reinforced by the following ants. In order to capture this process, we assume that each site occupied by an ant at the end of stage I also contains pheromone. On the other hand, pheromone in any ‘ant-free’ site is allowed to evaporate; this evaporation is also assumed to be a random process that takes place at an average rate of $`f`$ per unit time.

The total amount of pheromone on the trail can fluctuate although the total number $`N`$ of the ants is constant because of the periodic boundary conditions. In the two special cases $`f=0`$ and $`f=1`$ the stationary state of the model becomes identical to that of the TASEP with hopping probability $`Q`$ and $`q`$, respectively.

One interesting phenomenon observed in the simulations is coarsening. At intermediate time usually several non-compact clusters are formed (Fig. 2(a)). However, the velocity of a cluster depends on the distance to the next cluster ahead. Obviously, the probability that the pheromone created by the last ant of the previous cluster survives decreases with increasing distance. Therefore clusters with a small headway move faster than those with a large headway. This induces a coarsening process such that after long times only one non-compact cluster survives (Fig. 2(b)). A similar behaviour has been observed also in the bus-route model .

In vehicular traffic, usually, the inter-vehicle interactions tend to hinder each other’s motion so that the average speed of the vehicles decreases monotonically with increasing density. In contrast, in our model of uni-directional ant-traffic the average speed of the ants varies non-monotonically with their density over a wide range of small values of $`f`$ because of the coupling of their dynamics with that of the pheromone. This uncommon variation of the average speed gives rise to the unusual dependence of the flux on the density of the ants in our uni-directional ant-traffic model. Furthermore, the flux is no longer particle-hole symmetric.

It is possible to extend the model of uni-directional ant-traffic to a minimal model of bi-directional ant-traffic . In the models of bi-directional ant-traffic the trail consists of two lanes of sites. These two lanes need not be physically separate rigid lanes in real space. In the initial configuration, a randomly selected subset of the ants move in the clockwise direction in one lane while the others move counterclockwise in the other lane. The numbers of ants moving in the clockwise direction and counterclockwise in their respective lanes are fixed, i.e. ants are allowed neither to take U-turn<sup>2</sup><sup>2</sup>2U-turns of so-called followers on pre-existing trails are very rare . nor to change lane.

The rules governing the dropping and evaporation of pheromone in the model of bi-directional ant-traffic are identical to those in the model of uni-directional traffic. The common pheromone trail is created and reinforced by both the outbound and nestbound ants. The probabilities of forward movement of the ants in the model of bi-directional ant-traffic are also natural extensions of the similar situations in the uni-directional traffic. When an ant (in either of the two lanes) does not face any other ant approaching it from the opposite direction the likelihood of its forward movement onto the ant-free site immediately in front of it is $`Q`$ or $`q`$, respectively, depending on whether or not it finds pheromone ahead. Finally, if an ant finds another oncoming ant just in front of it, as shown in Fig. 3, it moves forward onto the next site with probability $`K`$.

Since ants do not segregate in perfectly well defined lanes, head-on encounters of oppositely moving individuals occur quite often although the frequency of such encounters and the lane discipline varies from one species of ants to another. In reality, two ants approaching each other feel the hindrance, turn by a small angle to avoid head-on collision  and, eventually, pass each other. At first sight, it may appear that the ants in our model follow perfect lane discipline and, hence, unrealistic. However, that is not true. The violation of lane discipline and head-on encounters of oppositely moving ants is captured, effectively, in an indirect manner by assuming $`K<Q`$. But, a left-moving (right-moving) ant cannot overtake another left-moving (right-moving) ant immediately in front of it in the same lane. It is worth mentioning that even in the limit $`K=Q`$ the traffic dynamics on the two lanes would remain coupled because the pheromone dropped by the outbound ants also influence the nestbound ants and vice versa.

Fig. 4 shows fundamental diagrams for the two relevant cases $`q<K<Q`$ and $`K<q<Q`$ and different values of the evaporation probability $`f`$ for equal densities on both lanes. In both cases the unusual behaviour related to a non-monotonic variation of the average speed with density as in the uni-directional model can be observed .

An additional feature of the fundamental diagram in the bi-directional ant-traffic model is the occurrence of a plateau region. This plateau formation is more pronounced in the case $`K<q<Q`$ than for $`q<K<Q`$ since they appear for all values of $`f`$. Similar plateaus have been observed earlier  in models related to vehicular traffic where randomly placed bottlenecks slow down the traffic in certain locations along the route.

The experimental data available at present  are not accurate enough to test the predictions mentioned above. More accurate measurements, using novel methodologies are in progress .

## 5 Patterns in the colonies of vertebrates

Migrating fish schools and bird flocks have one common feature that both of these correspond to a non-vanishing average linear drift velocity. In theoretical models a bird or a fish can be represented by a polar self-propelled particle. The nature of the dynamical phases and phase transitions of both polar and apolar self-propelled particles have been investigated extensively in the literature over the last decade .

Ramaswamy and collaborators  have studied the hydrodynamic fluctuations of liquid-crystal-like ordered dynamical phases of self-propelled apolar particles. Carrying out linear stability analysis, they have not only predicted certain long-wavelength instabilities but also indicated the possibility of novel propagating modes which, in principle, may be observed in experiments with real or artificial self-propelled particles.

The structure and function of schools of fish have attracted attention for the last few dacades . But, serious efforts have been only over the last few years  in the understanding the mechanism of their formation through self-organization in terms of quantitative models. For example, Niwa  has developed a model of fish schooling following the Lagrangian approach. However, the equations describing the movements of the individual fishes are written in terms of continuous space and time; in fact, these equations are very similar to Langevin equations for Brownian particles subjected to not only intertial forces but also viscous drag and random noise.

Stöcker  has developed a CA model for tuna school formation. However, for the sake of simplicity, we outline here the main idead behind the first CA model of fish schooling, developed by Huth and Wissel . Each fish is characterized by its position and velocity vectors. Suppose, $`r_{ij}`$ denotes the magnitude of the separation between the fish labelled by the integer indices $`i`$ and $`j`$. In order to decide the position and velocity of the fish $`i`$, one needs to draw three imaginary speheres of radii $`r_1`$, $`r_2`$ and $`r_3`$ ($`r_1<r_2<r_3`$) around it. If the fish $`j`$ is located within the smallest sphere, then it would have a repulsive effect on the fish $`i`$ such that the fish $`i`$ will have a tendency to swim away in a direction perpendicular to the direction of the velocity of the fish $`j`$. On the other hand, if the fish $`j`$ is located anywhere within the distance $`r_1<r_{ij}<r_2`$, the fish $`i`$ will tend to move parallel to the velocity of the fish $`j`$. In case $`r_2<r_{ij}<r_3`$, the fish $`i`$ will be attracted towards the fish $`j`$. Finally, if the fish $`j`$ is located outside the largest sphere of radius $`r_3`$, i.e., $`r_{ij}>r_3`$, it will have no influence on the movement of the fish $`i`$. Huth and Wissel  also introduced rules for combining the influences of more than one fish within the spheres of influence.

## 6 Human traffic on trails

Various kinds of pattern formation can also be observed in human societies, especially in pedestrian dynamics . As we will see, the human “intelligence” plays only a minor role. Instead, the observed effects can be understood as simply collective phenomena in systems of interacting particles. In fact, some effects (like lane formation) also appear in true physical systems . Before we present a CA model that reproduces the essentials of pedestrian dynamics we list some of the observed collective phenomena.

### 6.1 Collective phenomena and pattern formation

One of the reasons why the investigation of pedestrian dynamics is attractive for physicists is that many interesting collective effects and self-organization phenomena can be observed .

Jamming: At large densities various kinds of jamming phenomena occur, typically at bottlenecks like doors or narrowing corridors. This kind of clogging effect does not depend strongly on the microscopic dynamics of the particles. Other types of jamming occur in the case of counterflow where two groups of pedestrians mutually block each other. This happens typically at high densities and when it is not possible to turn around and move back, e.g. when the flow of people is large.

Lane formation: In counterflow with groups of people moving in opposite directions, a kind of spontaneous symmetry breaking occurs (see Fig. 5). The motion of the pedestrians can self-organize into dynamically varying lanes where people move in just one direction . Thus, strong interactions with oncoming pedestrians are reduced and a higher walking speed is possible.

Oscillations: In counterflow at bottlenecks, e.g. doors, oscillatory changes of the direction of motion are observed. Once a pedestrian is able to pass the bottleneck it becomes easier for others to follow her/him in the same direction until somebody is able to pass (e.g. through a fluctuation) the bottleneck in the opposite direction (see Fig. 6).

Patterns at intersections: At intersections various collective patterns of motion can be formed. A typical example are short-lived roundabouts which make the motion more efficient. Even if these are connected with small detours the formation of these patterns can be favourable since they allow for a “smoother” motion.

Panics: In panic situations, many counter-intuitive phenomena can occur. In the faster-is-slower effect  a higher desired velocity leads to a slower movement of a large crowd. Typical is also herding behaviour where people just blindly follow others. Such effects are extremely important for evacuations in emergency situations.

### 6.2 Modelling Pedestrian Dynamics

Several different types of models have been suggested in order to reproduce and understand the phenomena described in the previous subsection. In addition, practical applications, e.g. in the planning of public buildings like football stadiums, are of considerable importance. The latter requires models that can simulate even large crowds efficiently but, at the same time, are realistic enough to capture the essential aspects of the dynamics, e.g. the observed collective effects. Therefore it is not surprising that only a few models are able to achieve this.

A continuum approach that has been very successful in modelling pedestrian dynamics, is the so-called social force model (see e.g.  and references therein). Pedestrians are treated as particles subject to long-ranged forces induced by the social behaviour of the individuals. The typical structure of the force between the pedestrian is described by

$$𝐟_{ij}=𝐟_{ij}^{(soc)}+𝐟_{ij}^{(phys)}.$$
(6)
Here $`𝐟_{ij}^{(phys)}`$ is a physical force and describes friction and compression when pedestrians make contact. $`𝐟_{ij}^{(soc)}`$ is a repulsive social force modelling the tendency to keep a certain distance to other individuals. Typically it is long-ranged and has the form

$$𝐟_{ij}^{(soc)}=A_ig_{ij}(\lambda _i,\phi _{ij})\mathrm{exp}\left(r_{ij}/\xi _i\right)𝐧_{ij}$$
(7)
where $`r_{ij}`$ is (a suitably defined) distance between the pedestrians and $`𝐧_{ij}`$ a normalized vector pointing from individual $`j`$ to $`i`$. Apart from the interaction strength $`A_i`$ and the range $`\xi _i`$ of the force it has also a direction dependence that enters through the function $`g_{ij}`$ which depends on a parameter $`\lambda _i`$ controlling the anisotropy of interactions and the angle $`\phi _{ij}`$ between the directions of motion.

This idea leads then to equations of motion similar to Newtonian mechanics. There are, however, important differences since, e.g., in general the third law (“action = reaction”) is not fulfilled by social forces.

So-called active-walker models  have been used to describe the formation of human or animal trails etc. Here the walker leaves a trace by modifying the underground on his path. This modification is similar to chemotaxis since it can be regarded as a stimulus for other pedestrians. Vegetation is destroyed by the walker and so it becomes more attractive for others to follow the same path.

Most cellular automata (CA) models for pedestrian dynamics proposed so far are rather simple  and can be considered as generalizations of the Biham-Middleton-Levine model for city traffic . However, these models are not able to reproduce all the collective effects observed empirically.

In the following we present the so-called floor field CA model developed in . It is a CA with stochastic dynamics and in many respects can be regarded as a two-dimensional version of the ant trail model of Sec. 4.3. The basic idea is to model interactions between pedestrians as a kind of virtual chemotaxis. Like an ant on a ant trail any moving pedestrian creates a virtual trace that influences the motion of other pedestrians by enhancing the probability of motion in the same direction. In this way long-ranged spatial interactions are translated into local interactions, but with “memory”. This reduces the number of interaction terms considerably (from $`O(N^2)`$ to $`O(N)`$ for crowds of $`N`$ people) and allows for a much more efficient implementation on a computer.

The idea of a virtual trace can be generalized to a so-called floor field. This floor field includes the virtual trace created by the pedestrians as well as a static component which does not change with time. The latter allows to model e.g. preferred areas, walls and other obstacles. The pedestrians then react to both types of floor fields. The ‘particles’ in the model have very little “intelligence” and the formation of complex structures and collective effects is solely achieved through self-organization. No detailed assumptions about the human behaviour are necessary.

As already emphasized, it is similar to a 2-dimensional variant of the ant trail model. We have a hard-core exclusion so that each cell can be occupied at most by one pedestrian. In contrast to pheromone field in the ant trail model, the floor fields are virtual and, therefore, not restricted by hard-core exclusion. Here we do not give a complete definition of the model here which can be found in .

These basic principles are already sufficient to reproduce the effects described in Sec. 6.1, such as lane formation in a corridor, herding and oscillations at a bottleneck . In addition, the model can also be used very efficiently for the simulation of emergency situations .

## 7 Conclusion

Aesthetically beautiful patterns are formed by aggregates of living organisms. Such patterns are formed by organisms as simple as uni-cellular bacteria, by social insects like ants and termites as well as by more complex vertebrates like birds and fish. All the patterns of our interest are transient in nature. Interesting transient patterns emerge also in human societies. During time intervals that are short compared to the lifetime of a pattern formed by the terrestrial locomotion of organisms, the collective movements on linear segments often appear similar to vehicular traffic. In this article we have presented a critical review of the theoretical works, particularly those published over the last decade, focussing almost exclusively on the agent-based models formulated in the spirit of the classical Lagrangian approach. These include the Langevin-like stochastic differential equations, where dynamics is formulated in continuous space-time to describe the trajectories of the individual organisms. Another class of agent-based discrete models are developed using the language of cellular-automata where the dynamics is formulated in terms of update rules. Direct comparison with controlled experiments have been possible mostly in case of micro-organisms and small insects. The challenge is to unveil the mystery of these transient tapestry and traffic of life.

Acknowledgements

DC thanks Dietrich Stauffer for hospitality in Köln during a visit, supported by a joint Indo-German research project funded by DFG, when some of the works reported here were initiated. We also thank Alexander John for useful discussions.


format: text

text:
# What We Know and What we Don’t Know About the Universe 1footnote 11footnote 1Keynote address at the International Workshop on Astronomy and Relativistic Astrophysics, October 12-16 2003, Olinda, Brazil.

## I Introduction

It is true that the words “cosmology” and “revolution” have appeared together in many reviews and lectures in recent years. Even though to a cynic it may seem that cosmologists produce a lot of hot air, I claim that there is indeed reason for this excitement. Until the mid-sixties, cosmology was regarded with much suspicion by many scientists, who thought it closer to metaphysics than to physics. The reason for the skepticism was an appalling lack of observational data, or at least consistent observational data. For example, since the time of Hubble, the universe’s age has varied from 2 billion years (mcu below the known Earth’s age even in 1929) to over 20 billion. Its geometry has been bent and closed like the surface of a sphere, flat as a tabletop, or bent and open like the surface of a saddle. (Of course, generalized to 3 spatial dimensions.) Its material composition has also been a mystery: which chemical elements are made in stars and which during the first moments after the “bang”? What of other, exotic kinds of matter? And what about the cosmological constant? Is it there or not? And if it is, what is it? hetherington  Questions related to the shape, age, and material composition of the cosmos have been at the forefront of cosmology since Einstein’s pioneering use of his theory of relativity to the study of the universe as a whole.

Controversy is a good thing for science only when there are ways of resolving it. This is why these are exciting times for cosmology. We have convincing answers to many of the questions above, and are close to answering some more. Of course, this does not mean that cosmology is approaching its end. Quite the contrary, as with any mature area of science, new technologies and observational tools will continue to provide both answers and new questions and surprises.

## II Space

In astronomy and cosmology the yardstick is the light-year (ly), the distance covered by light in 1 year, equal to $`9.46\times 10^{12}`$ km. That’s $`63,200`$ times the Earth-Sun distance, also known as astronomical unit (A.U.). Pluto is at about $`40`$ A.U. from the Sun. Oort’s cloud, the nursery of long-period comets at the outskirts of the solar system, is at roughly $`100,000`$ A.U., about $`1.58`$ ly from the Sun. The nearest star, Proxima Centauri, is at $`4.29`$ ly from the Sun. So, when people say that interstellar space is mostly empty you better believe it. At least of “visible” stuff. It turns out, paraphrasing the fox in Saint Exupéry’s The Little Prince, “what is essential \[to the universe\] is invisible to the eye.” Invisible but very real, as will be seen below.

Once we start thinking about other stars, it is inevitable to ask if there are other planets as well. The thought that our solar system is unique in some way brings nightmares to most (but not all) post-copernican scientists. Although the curiosity about extrasolar planets existed for as long as modern astronomy (and before gleiser-pa ), the hunt started in earnest in the mid-1990s when minute variations of stellar light frequency could be detected due to improved observational technologies and computer data analysis software. At the time of writing (January 2004), 104 planetary systems with 119 planets have been detected \[See www.obspm.fr/planets\]. The curious lack of multiple planetary systems is most probably due to the limitations of the observational methods; one should not consider this as any indication of our uniqueness. NASA (Terrestrial Planet Finder Mission) and the European Space Agency (Darwin Mission) are formulating competing (possibly future collaborations) missions with a projected capability of not only imaging Earth-size planets in the infrared but also of studying the chemical composition of their atmospheres. The goal is to explore the possibility that these planets may harbor life. We may know the answer within a decade or two. Or sooner, if programs like SETI are successful, or if we receive a visitor or message. Improbable but not impossible.

Jumping farther out, the Milky Way – our home galaxy – is a spiral containing about $`300`$ billion stars and diameter of $`100,000`$ ly or $`30`$ kpc, where kpc stands for $`10^3`$ parsecs. ($`1`$ pc equals $`3.3`$ ly.) Strong evidence indicates that a giant black hole with a mass of about $`3`$ million suns is at the dead center of the Milky Way, at Sagittarius A. Possibly most other galaxies also host giant black holes at their centers, given the huge outpour of radiation many produce at varying wavelengths. If you think $`3`$ million solar masses is large think again; observations indicate that the huge galaxy M87 in the Virgo Cluster host a black hole with $`3`$ billion solar masses.

Which brings me to clusters of galaxies and to the large-scale structure of the universe. The Andromeda galaxy, our nearest neighbor, is at about $`2.5`$ Mly (million light-years) from the Milky Way. As we consider distances of millions of light-years, galaxies become the units by which we visualize the cosmos. When the Hubble Space Telescope or other large terrestrial telescopes image deep space, the light they collect as point or small sources is coming from huge galaxies millions and even billions of light-years away. What we see as stars when we look at the night sky, large-scale astronomers see as galaxies, each with millions or billions of stars. And what they see is that galaxies may coexist in groups or clusters due to their mutual gravitational attraction, like islands in an archipelago. Furthermore, galaxies and cluster of galaxies are not randomly distributed across space; they tend to collect in curved sheet-like surfaces, reminiscent of the shapes we see in bubble baths. Only at distances of $`100`$ million Mpc or more these “bubbly” structures seem to disappear, with the universe becoming smoother.

One of the successes of modern cosmology was to shed partial light on the origin of such complex large-scale structures. The answer involves of course gravity as the conductor, and three players: ordinary, or baryonic, matter, the stuff made of protons as we are; a different kind of matter known as dark matter bartusiak , which we know exists from its gravitational pull on ordinary matter (there are some dissenters, though); and small energy inhomogeneities, the seeds that cause matter (first dark and then baryonic) to start condensing. You may think of these energy inhomogeneities as lumps in an otherwise smooth cookie dough, regions where the local density of energy (recall that matter and energy are treated equally in relativity) varies from the average. So, we need three players. Computer simulations using them at the right proportions (more about that later) reproduce quite well astronomical observations. But what is this dark matter stuff, and what was the mechanism that generated the seeds that triggered structure and galaxy formation? We will leave dark matter for later. It is believed that the inhomogeneities were originated during the earliest moments of cosmic existence, in a process called inflationguth . During inflation, the universe expanded extremely fast. Even small fluctuations in its quite smooth energy were amplified enormously. Those are the culprits for large-scale structure, some $`100,000`$ years after inflation ended. Although there is no compelling model for inflation based on what we know of particles physics, the core idea and its predictions seem to be in excellent agreement with observations. If nothing else, the final answer will contain some of its elements.

What of the shape of the whole cosmos? When Einstein wrote his paper on cosmology, he assumed the universe was static and with the closed geometry of a 3-sphere. At the time, there was no compelling reason to suppose otherwise, and spheres, since the time of the Pythagoreans, have had an alluring effect on the minds of philosophers and scientists alike gleiser-du . A spherical universe is closed yet has no boundary, and all its points are equivalent. (Imagine the surface of a perfect ball.) The question remained open until the advent of inflation in the early-1980s. For when one talks of an expanding universe, one is referring to an expanding geometry, as if the surface of a ball were inflating like a party balloon. (But no one is blowing on it from the outside!) All points rush away from each other, and distances increase at tremendous rates. Imagine then the balloon inflating, and focus your attention on a patch on its surface. As it inflates, the patch becomes flatter. An enormous amount of inflation leads to a practically flat patch. This patch, according to inflationary cosmology, is where we live. Thus, inflation predicts a flat cosmos. This prediction has been spectacularly confirmed by observations of the cosmic microwave background (CMB), the fossil radiation from the time cosmic structure started to form turner .

But our cosmos may be flat only locally. We can’t say much about other folds of the cosmos, far removed from us. In fact, we will never be able to know about those remote cosmic regions, as no signal can be sent or arrive from there in able time: light is only so fast, and our cosmic patch has been around for about $`13`$ billion years. We cannot see beyond the flat island of $`13`$ ly radius we call our universe. Some models of inflation even predict that the universe is really a “multiverse,” a bubbling soup of cosmoids forever bursting in and out of existence linde . We will have to wait a bit on this one.

## III Time

The big bang model is our current best description of cosmic history. It states that the universe had a very hot and dense infancy, and that it has been expanding ever since. There is now excellent concordance between different methods that estimate the age of the universe. Here are a few: Measurements of the Hubble constant all the way to galaxies at $`500`$ Mpc give $`H_0=72`$ km/sec/Mpc in a universe with $`1/3`$ matter and $`2/3`$ dark energy (more about this soon). This results in an age of $`t_0=13\times 10^9`$ years with an uncertainty of $`1.5\times 10^9`$ year freedman ; measurements of the CMB, independent of $`H_0`$, give $`t_0=13.7\pm 0.2\times 10^9`$ yearswmap ; knox ; Finally, the ages of the oldest stars in globular clusters are estimated to be about $`12.5\times 10^9`$ years krauss . A consistent age is $`t_0=13.5\pm 1.0\times 10^9`$ years.

Within the big bang framework, the evolving cosmic history is a history of increasing complexification: at the earliest times, matter was broken down to its smallest components. To understand cosmic history is equivalent to recreate how the structures that make up the material universe emerged. Complexification happened in stages, controlled mostly by the cosmic temperature. At a given temperature, only certain particles or their bound states (atomic nuclei, atoms, perhaps solitons) are in thermal equilibrium with the ambient radiation. One may picture this as a love triangle, where photons and possibly other light particles such as neutrinos (the radiation) interact with matter particles which are trying to bind. If these interactions proceed fast enough, the particles (or their bound states) are in equilibrium; otherwise, they are left behind as fossils of this era. Since different interactions have different associated energy (temperature) scales, the cosmic history evolves in stages, depending when a certain interaction goes out of equilibrium, from the most to the least energetic. Thus, the early cosmic history went through at least three stages: a particle era, a nuclear era, and an atomic era. The boundary between the particle and nuclear eras is at about $`10^5`$ sec, when quarks and gluons combined to make the baryons, particles that interact by the strong nuclear force such as protons, neutrons, and mesons gleiser-cp . Since protons have lifetimes of at least $`10^{31}`$ years, we can say that they are fossils from this era. Once protons and neutrons were around, they could start to bind into the lightest nuclei, H2, H3, He4, He3, and Li7. This happened when the universe was about 1 minute old. One of the great triumphs of the big bang model is predicting successfully the abundances of these nuclei. In particular, He4 account for about $`23`$% of the baryonic matter in the cosmos, and hydrogen to about $`75`$%.

The next step in the cosmic history is the formation of hydrogen atoms, at about $`380,000`$ years. This is when protons bind with electrons and photons are free to roam across space, responding here and there to variations in the average energy density by having cold and hot spots. Measuring the properties of these photons, known as the CMB, is equivalent to taking a snapshot of the universe at that early time smoot ; mather . From then on, the universe became transparent to radiation. This means that it is impossible to try to study the cosmos before this time by direct measurements of electromagnetic radiation of any wavelength; to probe the early universe we need to hunt for fossils. Dozens of terrestrial missions and the satellites COBE and WMAP (and soon PLANCK) have produced high precision measurements of the CMB, re-energizing modern cosmology and confirming yet again the predictions of the big bang model. Measurements of the CMB allowed us to confirm the flatness of space spergel . (Recent claims to the contrary luminet , remain a possibility, albeit a very improbable one.) They have also allowed us to learn when the first stars were born (roughly at $`200`$ million years).

Understanding the nature of time remains one of the great challenges of physics. A classical theory of gravity (and thus the big bang model) predicts the existence of an “initial singularity,” the instant in time when the energy density reaches an infinite value and space collapses to a point. At the heart of the problem is a proper formulation of a quantum theory of gravity, explaining its behavior at very small distances and high energies. Although there are models describing the origin of the universe (at least our local patch) by a quantum tunneling event hawking ; linde2 , the transition from a quantum to a classical universe one described by the big bang model remains obscure. We need guidance from particle physics to pick the proper theory to work with. String theory greene  and/or loop gravity smolin  have made much progress, but we still don’t have a compelling connection between their realm and that of 4-dimensional spacetime particle physics.

## IV Matter

It must be clear to the reader that within modern cosmology, treating space, time, and matter as three separate topics is highly artificial. The three are deeply intertwined. A point in case is the questions of the “end of time” gleiser-pa . Up to 1998, the standard big bang model had a very simple prediction: if we know the total energy density of the universe ($`\rho _{\mathrm{tot}}`$), we can tell what will happen to it. The cosmic fate is controlled by the critical density, $`\rho _{\mathrm{crit}}=3H_0^2/8\pi G10^{29}`$ g/cm3, where $`G`$ is Newton’s gravitational constant. It is convenient to define the ratio $`\mathrm{\Omega }_i\rho _i/\rho _{\mathrm{crit}}`$ for a given contribution to $`\rho _{\mathrm{tot}}`$. Of course, $`\rho _{\mathrm{tot}}=_i\rho _i`$, and $`\mathrm{\Omega }_{\mathrm{tot}}=\rho _{\mathrm{tot}}/\rho _{\mathrm{crit}}`$. If $`\mathrm{\Omega }_{\mathrm{tot}}>1`$, the universe will recollapse in the distant future. Otherwise, it will continue its expansion indefinitely. The discovery in 1998 that the universe is presently accelerating blurred the clarity of this prediction livio . The culprit of this acceleration is called dark energy, a ghostly contribution to the total energy density (and pressure, which makes ’dark energy’ a somewhat imprecise name) spread out homogeneously or nearly so across the universe. Its net effect is to push the cosmic geometry apart, somewhat like an anti-gravitational force. Measurements of distant supernovae and of the CMB give $`\mathrm{\Omega }_{\mathrm{DE}}0.73\pm 0.04`$. So, not only there is an unknown energy component in the universe, but it is also the dominant one: CMB and other measurements place $`\mathrm{\Omega }_{\mathrm{tot}}=1.02\pm 0.02`$, meaning that everything else must amount to no more than $`27`$% or so of cosmic stuff. Most probably this implies that the universe is marginally flat and hence will expand forever. But what if the universe were supercritical ($`\mathrm{\Omega }_{\mathrm{tot}}>1`$? Without dark energy (pre 1998), we would say it would recollapse in a finite time. But with dark energy things are more subtle krauss2 ; gleiser-pa .

Dark energy is extremely difficult to pinpoint; its effects on the CMB are mostly relegated to very large fluctuations. The two main contenders are the infamous cosmological constant, created by Einstein to balance out his collapsing static spherical model, and a hypothetical scalar field called quintessence caldwell . The main difference between a cosmological constant and a scalar field is in their pressures and clustering properties. Scalar fields may have pressures of smaller absolute magnitude and respond to variations in the gravitational field: i.e., quintessence may cluster, even if very subtly. The problem is that the models for quintessence are somewhat contrived, at least from a particle physics viewpoint. If quintessence exists, it will almost certainly not be a fundamental field, but a phenomenological order parameter or condensate of some sort. The cosmological constant is not in much better shape. Quantum physics predicts that all fields have a sort of fundamental inescapable jitter. Since all that moves carry energy, this quantum jitter has an associated energy, called zero-point energy weinberg ; padmanabhan . This energy is most certainly related to the cosmological constant. Quintessence has nothing to say about this. The problem is, if one would naively compute the zero-point energy in the universe, the result would be a cosmological constant some $`120`$ orders of magnitude too large. In other words, we don’t understand the cosmological constant. Until we have a better grasp of it, dark energy will remain mysterious.

What then is the cosmic recipe, circa January 2004? Taking $`\mathrm{\Omega }_{\mathrm{tot}}=1`$, the total normal (baryonic) matter and dark matter components add up to $`27`$%, or $`\mathrm{\Omega }_\mathrm{M}+\mathrm{\Omega }_{\mathrm{DM}}=0.27`$. Nucleosynthesis constrains $`\mathrm{\Omega }_\mathrm{M}0.04`$, leaving $`\mathrm{\Omega }_{\mathrm{DM}}0.23`$. That measurements of the distribution of dark matter in galaxies and clusters of galaxies, as well as CMB measurements, concur very nearly with this estimate speaks to the robustness of modern observational and theoretical cosmology. It turns out that the stuff we and stars are made of is by far the universes’s subdominant energy component. Even this familiar component is only partially accessible; some of ordinary matter is also “dark” in the sense that it does not produce visible radiation. (But it produces other kinds of radiation, such as infrared, as we have seen in the hunt for extrasolar planets.) However, the bets are still off for what is the dark matter component. Unless we are missing something very basic about gravity at large distances, dark matter is not of the ordinary kind. It may not be of a single kind either: maybe several exotic particles and more complex objects contribute to $`\mathrm{\Omega }_{\mathrm{DM}}`$. A tremendous amount of effort is being dedicated to disclose some of its nature, be it by direct detection (cryogenic detectors that would “count” the dark matter particles as they impact its collecting area or resonate in special cavities) or by production in the laboratory (if dark matter is related to supersymmetry, it may possibly be produced in particle accelerators very soon kane .) Whatever dark matter is, the stakes are high: we are talking of an unknown kind of matter, over six times more abundant in the universe than ordinary matter. Both dark energy and dark matter promise new physics ahead.

## V CONCLUSIONS

I hope this brief overview has given the reader at least a general flavor of the excitement permeating present cosmological and astrophysical research. We have learned a tremendous amount about the physical universe, its material composition, its shape, and its age. Yet, science teaches us that there will always be more to learn. In fact, the old aphorism, “the more we know the more we don’t know” seems to apply very well here. As new tools and ideas open new vistas to the physical universe, we stand in awe of nature’s creativity and of our ability to understand so much of it. To those that cynically comment on the state of “mystery” in cosmology, “too much dark stuff around,” I say that this is precisely how science progresses: by teaching us to accept ignorance as the main precondition for learning. Only then we stand a chance of rationally answering some of the many questions we have, and the many more that will surely come. What we have learned so far speaks for itself.

###### Acknowledgements.

I’d like to express my gratitude to the organizers of IWARA 2003, and in particular to Helio Coelho, Sandra Prado, and Cesar Vasconcellos for their invitation and wonderful hospitality. My research is sponsored in part by a NSF grant PHY-0099543.


text:
# Untitled Document

On the length of the continued fraction for values of quotients of power sums

P. Corvaja U. Zannier

Abstract. Generalizing a result of Pourchet, we show that, if $`\alpha ,\beta `$ are power sums over $`𝐐`$ satisfying suitable necessary assumptions, the length of the continued fraction for $`\alpha (n)/\beta (n)`$ tends to infinity as $`n\mathrm{}`$. This will be derived from a uniform Thue-type inequality for the rational approximations to the rational numbers $`\alpha (n)/\beta (n)`$, $`n𝐍`$.

Introduction. The features of the continued fraction of a positive real number are usually extraordinarily difficult to predict. However, if the numbers in question run through certain parametrized families, some regularity occasionally appears. For instance, we may recall remarkable results by Schinzel \[S1\], \[S2\], on the lengths of the periods of the continued fractions for $`\sqrt{f(n)}`$, where $`f`$ is a polynomial with rational coefficients and $`n`$ varies through $`𝐍`$.

In a similar direction, but much more simply, one can deal with the continued fractions of the rational numbers $`r(n)`$, $`n𝐍`$, where now $`r𝐐(X)`$ is a rational function; for example, we may now look at the length of the fraction: in \[S2, Lemma 2\], Schinzel proves that this length is bounded as a function of $`n`$ (see also \[M\] for a more precise result). Substantially, the reason for this is that $`r(X)`$ has a finite expansion as a simple continued fraction with partial quotients in $`𝐐[X]`$.<sup>(1)</sup> Observe however that such continued fraction specialized at $`X=n`$ may not coincide with the continued fraction for $`r(n)`$.

More generally, one may inquire about the length of the continued fraction for the rational values of other arithmetical functions. In general, due to the lack of an Euclid’s algorithm, we have not a suitable “functional continued fraction”; this fact makes the situation different from the case of $`𝐐(X)`$ and generally speaking considerably more difficult.

For certain exponential functions, we have a result by Y. Pourchet, answering an appealing question of Mendès-France (see \[M2, p. 214\]); it states that, for coprime integers $`a,b>1`$, the length of the continued fraction for $`(a/b)^n`$ tends to infinity as $`n\mathrm{}`$, in marked contrast to the rational function case.

This theorem may be derived from the (deep) lower bound $`|(a/b)^n(p/q)|_ϵq^2\mathrm{exp}(ϵn)`$ (any positive $`ϵ`$), where $`p,q`$ are integers with $`0<q<b^n`$ (which follows e.g. from Ridout generalization of Roth’s Theorem \[R\]). The estimate is in fact amply sufficient, since it implies that all the partial quotients of the continued fraction in question are $`_ϵ\mathrm{exp}(ϵn)`$, and the statement about the length follows at once. (See also \[Z, Ex. II.6\].)

In this direction, one may consider more general power sums in place of $`a^n,b^n`$. Namely, in analogy to \[CZ1\] (where the notation is slightly different) we consider the ring (actually a domain) $``$ made up of the functions on $`𝐍`$ of the form

$$\alpha (n)=c_1a_1^n+\mathrm{}+c_ra_r^n,$$
$`(1)`$
where the coefficients $`c_i`$ are rational numbers, the $`a_i`$ are positive integers and the number $`r`$ of summands is unrestricted. (We shall often normalize (1) so that the $`c_i`$ are nonzero and the $`a_i`$ are distinct; in this case the $`a_i`$ are called the “roots” of $`\alpha `$.)

We then consider the ratio $`\alpha /\beta `$ of nonzero elements of $``$ and ask about the length of the continued fraction for the values $`\alpha (n)/\beta (n)`$ (provided $`\beta (n)0`$, which is the case for all large $`n`$). It turns out (Corollary 2 below) that the length of the relevant continued fraction does not tend to infinity if and only if $`\alpha /\beta `$ admits an expansion as a (finite) continued fraction over $``$. Note that $``$ is not euclidean, so in practice this condition “rarely” holds.

This result plainly generalizes Pourchet’s, but now the Ridout Theorem seems no longer sufficient for a proof. In fact, we shall need the full force of the Schmidt Subspace Theorem, similarly to \[CZ1\], where (among others) the related question of the integrality of the values $`\alpha (n)/\beta (n)`$ was investigated.

Similarly to the above sketched argument for Pourchet’s Theorem, the conclusions about the continued fraction will be derived from a “Thue-type” inequality for the rational approximations to the values in question, which is the content of the Theorem below. Its proof follows \[CZ1\] in the main lines, except for a few technical points; however the present new simple applications of those principles are perhaps not entirely free of interest.

Preliminary to the statements, we introduce a little more notation.

We let $`_𝐐`$ be the domain of the functions of type (1), but allowing the $`a_i`$ to be positive rationals. If $`\alpha _𝐐`$ is written in the form (1), with nonzero $`c_i`$ and distinct $`a_i`$, we set $`\mathrm{}(\alpha )=\mathrm{max}(a_1,\mathrm{},a_r)`$, agreeing that $`\mathrm{}(0)=0`$.

It is immediate to check that $`\mathrm{}(\alpha \beta )=\mathrm{}(\alpha )\mathrm{}(\beta )`$, $`\mathrm{}(\alpha +\beta )\mathrm{max}(\mathrm{}(\alpha ),\mathrm{}(\beta ))`$ and that $`\mathrm{}(\alpha )^n|\alpha (n)|\mathrm{}(\alpha )^n`$ for $`n𝐍`$ tending to infinity (so in particular, $`\alpha (n)`$ cannot vanish infinitely often if $`\alpha 0`$).

Theorem. Let $`\alpha ,\beta `$ be nonzero and assume that for all $`\zeta `$, $`\mathrm{}(\alpha \zeta \beta )\mathrm{}(\beta )`$. Then there exist $`k=k(\alpha ,\beta )>0`$ and $`Q=Q(\alpha ,\beta )>1`$ with the following properties. Fix $`ϵ>0`$; then, for all but finitely many $`n𝐍`$ and for integers $`p,q`$, $`0<q<Q^n`$, we have

$$\left|\frac{\alpha (n)}{\beta (n)}\frac{p}{q}\right|\frac{1}{q^k}\mathrm{exp}(ϵn).$$

We tacitly mean that the alluded finite set of exceptional integers includes those $`n𝐍`$ with $`\beta (n)=0`$; this finite set may depend on $`ϵ`$.

Remarks. (i) The assumption about $`\alpha ,\beta `$ expresses the lack of an “Euclid division” in $``$ for $`\alpha :\beta `$ and cannot be omitted. In fact, suppose that $`\mathrm{}(\alpha \zeta \beta )<\mathrm{}(\beta )`$ for some $`\zeta `$. Then, the values $`\zeta (n)`$ have bounded denominator and verify $`|(\alpha (n)/\beta (n))\zeta (n)|\mathrm{exp}(ϵ_0n)`$ for large $`n`$ and some positive $`ϵ_0`$ independent of $`n`$, against the conclusion of the Theorem (with $`p/q=p_n/q_n=\zeta (n)`$).

Note that the assumption is automatic if $`\mathrm{}(\alpha )\mathrm{}(\beta )`$ and $`\mathrm{}(\beta )`$ does not divide $`\mathrm{}(\alpha )`$.

(ii) By the short argument after Lemma 1 below, given $`\alpha ,\beta `$, one can test effectively whether a $`\zeta `$ such that $`\mathrm{}(\alpha \zeta \beta )<\mathrm{}(\beta )`$ actually exist. Also, the proof will show that a suitable $`Q`$ and “exponent” $`k`$ may be computed. On the contrary, the finitely many exceptional $`n`$’s cannot be computed with the present method of proof.

(iii) Naturally, the lower bound is not significant for $`q`$ larger than $`\mathrm{}(\beta )^{n/(k1)}`$. So, some upper bound $`Q^n`$ for $`q`$ is not really restrictive. (Also, since the dependence of $`k`$ on $`\alpha ,\beta `$ is unspecified, and since $`\mathrm{}(\beta )^{1/(k1)}1`$ as $`k\mathrm{}`$, it is immaterial here to specify a suitable $`Q`$ in terms of $`k`$.)

Note also that a lower bound $`Q^n`$ for the denominator of $`\alpha (n)/\beta (n)`$ follows, sharpening \[CZ1, Thm. 1\]; in this direction, see \[BCZ\], \[CZ3, Remark 1\] and \[Z, Thm. IV.3\] for stronger conclusions in certain special cases.

(iv) Like for the proofs in \[CZ1\], the method yields analogous results for functions of the form (1), but where $`a_i`$ are any algebraic numbers subject to the sole (but crucial) restriction that there exists a unique maximum among the absolute values $`|a_i|`$. Using the (somewhat complicated) method of \[CZ2\], one may relax this condition, assuming only that not all the $`|a_i|`$ are equal. For the sake of simplicity, we do not give the proofs of these results, which do not involve new ideas compared to \[CZ1\], \[CZ2\] and the present paper, but only complication of detail.

(v) The Theorem can be seen as a Thue-type inequality with moving targets (similarly to \[C\] or \[V\]). It seems an interesting, but difficult, problem, to obtain (under suitable necessary assumptions) the “Roth’s exponent” $`k=2`$, or even some exponent independent of $`\alpha ,\beta `$. (As recalled above, this holds in the special cases of Pourchet’s Theorem.)

Corollary 1. Let $`\alpha ,\beta `$ be as in the Theorem. Then the length of the continued fraction for $`\alpha (n)/\beta (n)`$ tends to infinity as $`n\mathrm{}`$.

This corollary is in fact a lemma for the following result, which gives a more precise description.

Corollary 2. Let $`\alpha ,\beta `$ be nonzero. Then the length of the continued fraction for $`\alpha (n)/\beta (n)`$ is bounded for infinitely many $`n𝐍`$ if and only if there exist power sums $`\zeta _0,\mathrm{},\zeta _k`$ such that we have the identical continued fraction expansion

$$\frac{\alpha (n)}{\beta (n)}=[\zeta _0(n),\zeta _1(n),\mathrm{},\zeta _k(n)].$$

If this is the case, the mentioned length is uniformly bounded for all $`n𝐍`$.

It will be pointed out how the condition on $`\alpha /\beta `$ may be checked effectively.

The special case $`\alpha (n)=a^n1`$, $`\beta (n)=b^n1`$ appears as \[Z, Ex. IV.12\]. For completeness we give here this application.

Corollary 3. Let $`a,b`$ be multiplicatively independent positive integers. Then the length of the continued fraction for $`(a^n1)/(b^n1)`$ tends to infinity with $`n`$.

Proofs. We start with the following very simple:

Lemma 1. Let $`\alpha ,\beta `$ be nonzero and let $`t`$ be any positive number. Then there exists $`\eta _𝐐`$ such that $`\mathrm{}(\alpha \eta \beta )<t`$. Such an $`\eta `$ may be computed in terms of $`\alpha ,\beta ,t`$.

Proof. Write $`\beta (n)=cb^n(1\delta (n))`$, where $`c𝐐^{}`$, $`b=\mathrm{}(\beta )`$ and where $`\delta _𝐐`$ satisfies $`u:=\mathrm{}(\delta )<1`$. In particular, we have $`|\delta (n)|u^n`$, so for a fixed integer $`R`$ we have an approximation, for $`n\mathrm{}`$,

$$\frac{\alpha (n)}{\beta (n)}=\frac{\alpha (n)}{cb^n}\left(\underset{r=0}{\overset{R}{}}\delta (n)^r\right)+O\left(\left(\frac{\mathrm{}(\alpha )u^{R+1}}{b}\right)^n\right).$$

Choose $`R`$ so that $`u^R<t/u\mathrm{}(\alpha )`$ and define $`\eta `$ by the first term on the right. Then $`\eta _𝐐`$ and $`|\alpha (n)\eta (n)\beta (n)|(\mathrm{}(\alpha )u^{R+1})^n`$. Therefore $`\mathrm{}(\alpha \eta \beta )\mathrm{}(\alpha )u^{R+1}<t`$, concluding the proof.

We note at once that this argument may be used to check the assumption for the Theorem. In fact, suppose $`\mathrm{}(\alpha \zeta \beta )<\mathrm{}(\beta )`$ for a $`\zeta `$. Then, if $`\eta `$ is as in the lemma, with $`t=\mathrm{}(\beta )`$, it follows that $`\mathrm{}(\eta \zeta )<1`$. Since $`\eta `$ may be constructed and since the “roots” of $`\zeta `$ are positive integers by assumption, this inequality determines $`\zeta `$ uniquely; namely, if a suitable $`\zeta `$ exists, it is just the “subsum” of $`\eta `$ made up with the integer roots.

To go on, for the reader’s convenience, we recall a version of Schmidt’s Subspace Theorem suitable for us; it is due to H.P. Schlickewei (see \[Schm2, Thm.1E, p.178\]).

Subspace Theorem. Let $`S`$ be a finite set of places of $`𝐐`$, including the infinite one and normalized in the usual way (i.e. $`|p|_v=p^1`$ if $`v|p`$). For $`vS`$ let $`L_{0v},\mathrm{},L_{hv}`$ be $`h+1`$ linearly independent linear forms in $`h+1`$ variables with rational coefficients and let $`\delta >0`$. Then the solutions $`𝐱:=(x_0,\mathrm{},x_h)𝐙^{h+1}`$ to the inequality

$$\underset{vS}{}\underset{i=0}{\overset{h}{}}|L_{iv}(𝐱)|_v𝐱^\delta $$

where $`𝐱:=\mathrm{max}\{|x_i|\}`$, are all contained in finitely many proper subspaces of $`𝐐^{h+1}`$.

For our last lemma we could invoke results by Evertse \[E\]; for completeness we give a short proof of the special case we need.

Lemma 2. Let $`\zeta _𝐐`$ and let $`D`$ be the minimal positive integer such that $`D^n\zeta (n)`$. Then, for every $`ϵ>0`$ there are only finitely many $`n𝐍`$ such that the denominator of $`\zeta (n)`$ is smaller than $`D^n\mathrm{exp}(ϵn)`$.

Proof. We may write $`D^n\zeta (n)=_{i=0}^hu_ie_i^n`$, where $`u_i𝐐^{}`$ and $`e_i`$ are distinct positive integers with $`(e_0,\mathrm{},e_h,D)=1`$. Let $`S`$ be the set of places of $`𝐐`$ made up of the infinite one and of those dividing $`De_0\mathrm{}e_h`$.

Define the linear form $`L(𝐗):=_{i=0}^hu_iX_i`$.

For each $`vS`$ we define linear forms $`L_{iv}`$, $`i=0,\mathrm{},h`$, as follows. If $`v`$ does not divide $`D`$ (including $`v=\mathrm{}`$), then we put simply $`L_{iv}=X_i`$ for $`i=0,\mathrm{},h`$. If $`v|D`$, then there exists $`j=j_v`$ such that $`|e_j|_v=1`$; then we set $`L_{jv}=L`$ and $`L_{iv}=X_i`$ for $`ij`$. The forms $`L_{iv}`$, $`i=0,\mathrm{},h`$, are plainly linearly independent for each fixed $`vS`$.

Suppose now that the conclusion does not hold, so for some positive $`ϵ`$ and for all $`n`$ in an infinite set $`\mathrm{\Sigma }𝐍`$ the denominator of $`\zeta (n)`$ is $`D^n\mathrm{exp}(ϵn)`$. For $`n\mathrm{\Sigma }`$, put $`𝐱=𝐱(n)=(e_0^n,\mathrm{},e_h^n)`$.

Then, for $`n\mathrm{\Sigma }`$, the numerator of $`D^n\zeta (n)`$ has a g.c.d. with $`D^n`$ which is $`\mathrm{exp}(ϵn)`$. In turn this gives

$$\underset{v|D}{}|L(𝐱(n))|_v\mathrm{exp}(ϵn),n\mathrm{\Sigma }.$$

Also, for $`n\mathrm{\Sigma }`$, we have

$$\underset{vS}{}\underset{i=0}{\overset{h}{}}|L_{iv}(𝐱)|_v=\left(\underset{v|D}{}|L(𝐱)|_v\right)\underset{vS}{}\underset{i=0}{\overset{h}{}}|e_i^n|_v=\underset{v|D}{}|L(𝐱)|_v,$$

where the first equality holds because $`|e_{j_v}|_v=1`$ for $`v|D`$ and the second because the (inner) double product is $`1`$ by the product formula. Hence

$$\underset{vS}{}\underset{i=0}{\overset{h}{}}|L_{iv}(𝐱)|_v\mathrm{exp}(ϵn),n\mathrm{\Sigma }.$$

Since however $`𝐱(n)`$ is bounded exponentially in $`n`$, we may apply the Subspace Theorem (with a suitable positive $`\delta `$) and conclude that all the $`𝐱(n)`$, $`n\mathrm{\Sigma }`$, lie in a finite union of proper subspaces. But $`e_0,\mathrm{},e_h`$ are distinct positive integers, whence each subspace corresponds to at most finitely many $`n`$, a contradiction which concludes the proof.

Proof of Theorem. Let $`\eta `$ be as in Lemma 1, with $`t=1/9`$. Write

$$\eta (n)=g_1(\frac{e_1}{d})^n+\mathrm{}+g_h(\frac{e_h}{d})^n,$$

where $`g_i𝐐^{}`$ and where $`e_i,d`$ are positive integers with $`e_1>e_2>\mathrm{}>e_h`$.

We define $`k:=h+3`$, $`Q=\mathrm{exp}(1/k)`$, and we assume that for some fixed $`ϵ>0`$ (which we may take $`<1/6`$, say) there exist infinitely many triples $`(n,p,q)`$ of integers with $`0<qQ^n`$, $`n\mathrm{}`$ and

$$\left|\frac{\alpha (n)}{\beta (n)}\frac{p}{q}\right|\frac{1}{q^k}\mathrm{exp}(ϵn).$$
$`(2)`$
We shall eventually obtain a contradiction, which will prove what we want.

We proceed to define the data for an application of the Subspace Theorem. We let $`S`$ be the finite set of places of $`𝐐`$ consisting of the infinite one and of all the places dividing $`de_1\mathrm{}e_h`$.

We define linear forms in $`X_0,\mathrm{},X_h`$ as follows. For $`v\mathrm{}`$ or for $`i0`$ we set simply $`L_{iv}=X_i`$. We define the remaining form $`L_0\mathrm{}`$ by

$$L_0\mathrm{}(𝐗)=X_0g_1X_1\mathrm{}g_hX_h.$$

Plainly, for each $`v`$ the forms $`L_{iv}`$ are independent. For a triple $`(n,p,q)`$ as above we set

$$𝐱=𝐱(n,p,q)=(pd^n,qe_1^n,\mathrm{},qe_h^n)𝐙^{h+1}$$

and we proceed to estimate the double product $`_{vS}_{i=0}^h|L_{iv}(𝐱)|_v`$.

For $`i0`$ we have $`_{vS}|L_{iv}(𝐱)|_v=_{vS}|qe_i^n|_vq`$. In fact, we have $`_{vS}|e_i^n|_v=1`$ by the product formula, since the $`e_i`$ are $`S`$-units; also, $`_{vS}|q|_v|q|`$, since $`q`$ is an integer.

Further, we have $`_{vS}|L_{0v}(𝐱)|_v=\frac{|L_0\mathrm{}(𝐱)|}{|x_0|}_{vS}|x_0|_v`$. As before, we see that the inner product is bounded by $`|p|`$, since $`d^n`$ is an $`S`$-unit.

Also, $`|L_0\mathrm{}(𝐱)|=qd^n|\eta (n)(p/q)|`$. Then, using (2) and $`|(\alpha (n)/\beta (n))\eta (n)|(t/\mathrm{}(\beta ))^nt^n`$, we obtain

$$|L_0\mathrm{}(𝐱)|qd^nt^n+qd^n(q^k\mathrm{exp}(ϵn)).$$

Since $`q^kQ^{kn}=\mathrm{exp}(n)`$ and since $`t=1/9<\mathrm{exp}(1ϵ)`$, the first term on the right does not exceed the second one, whence

$$|L_0\mathrm{}(𝐱)|qd^n(q^k\mathrm{exp}(ϵn)).$$

Combining this with the previous bound we get

$$\underset{vS}{}|L_{0v}(𝐱)|_vqd^n(q^k\mathrm{exp}(ϵn))|x_0|^1|p|=q^{(k1)}\mathrm{exp}(ϵn).$$

Finally, for the double product this yields (since $`k>h+1`$)

$$\underset{vS}{}\underset{i=0}{\overset{h}{}}|L_{iv}(𝐱)|_vq^{(kh1)}\mathrm{exp}(ϵn)\mathrm{exp}(ϵn).$$

Now, (2) entails $`|p|q\mathrm{}(\alpha )^n(Q\mathrm{}(\alpha ))^n`$, whence $`𝐱C^n`$ for some $`C`$ independent of $`n`$. Hence the double product is bounded by $`𝐱^\delta `$ for some fixed positive $`\delta `$ and large enough $`n`$.

The Subspace Theorem then implies that all the vectors $`𝐱`$ in question are contained in a certain finite union of proper subspaces of $`𝐐^{h+1}`$.

In particular, there exists a fixed subspace, say of equation $`z_0X_0z_1X_1\mathrm{}z_hX_h=0`$, containing an infinity of the vectors in question. We cannot have $`z_0=0`$, since this would entail $`_{i=1}^hz_ie_i^n=0`$ for an infinity of $`n`$; in turn, the fact that the $`e_i`$ are distinct would imply $`z_i=0`$ for all $`i`$, a contradiction. Therefore we may assume that $`z_0=1`$, and we find that, for the $`n`$’s corresponding to the vectors in question,

$$\frac{p}{q}=\underset{i=1}{\overset{h}{}}z_i(\frac{e_i}{d})^n=\zeta (n),$$
$`(3)`$
say, where $`\zeta _𝐐`$. We now show that actually $`\zeta `$ lies in $``$. Assume the contrary; then the minimal positive integer $`D`$ so that $`D^n\zeta (n)`$ is $`2`$. But then equation (3) together with Lemma 2 implies that $`q2^n\mathrm{exp}(ϵn)`$. Since this would hold for infinitely many $`n`$, we would find $`Q2\mathrm{exp}(ϵ)`$, whence $`\mathrm{exp}((1/k)+ϵ)2`$, a contradiction. (Recall that $`k3,ϵ<1/6`$.)

Therefore $`\zeta `$ lies in $``$; using (3) to substitute in (2) for $`p/q`$ we find that, for an infinity of $`n`$,

$$\left|\frac{\alpha (n)}{\beta (n)}\zeta (n)\right|\mathrm{exp}(ϵn).$$

In particular, $`\mathrm{}((\alpha /\beta )\zeta )<1`$, whence $`\mathrm{}(\alpha \zeta \beta )<\mathrm{}(\beta )`$, contrary to the assumptions, concluding the proof.

Proof of Corollary 1. For notation and basic facts about continued fractions we refer to \[Schm1, Ch. I\] and let $`p_r(n)/q_r(n)`$, $`r=0,1,\mathrm{}`$, be the (finite) sequence of convergents of the continued fraction for $`\alpha (n)/\beta (n)`$, where we may assume that $`\alpha (n)`$ and $`\beta (n)`$ are positive.

As is well-known, $`p_r(n),q_r(n)`$ are positive integers, $`q_0(n)=1`$, and we have

$$\left|\frac{\alpha (n)}{\beta (n)}\frac{p_r(n)}{q_r(n)}\right|\frac{1}{q_{r+1}(n)q_r(n)}.$$
$`(4)`$
Suppose the conclusion false, so for some fixed $`R𝐍`$ there is an infinite set $`\mathrm{\Sigma }𝐍`$ such that for $`n\mathrm{\Sigma }`$ the continued fraction for $`\alpha (n)/\beta (n)`$ has finite length $`R+11`$. By this we mean that $`p_R(n)/q_R(n)=\alpha (n)/\beta (n)`$.

Since $`\alpha ,\beta `$ satisfy the assumptions for the Theorem, there exist $`Q>1`$, $`k2`$ as in that statement.

Define now the sequence $`c_0,c_1,\mathrm{}`$ by $`c_0=0`$ and $`c_{r+1}=(k1)c_r+1`$ and choose a positive number $`ϵ<c_R^1\mathrm{log}Q`$, so $`\mathrm{exp}(c_Rϵ)<Q`$; we proceed to show by induction on $`r=0,\mathrm{},R`$, that, for large $`n\mathrm{\Sigma }`$,

$$q_r(n)\mathrm{exp}(c_rϵn).$$
$`(5)`$
We have $`q_0(n)=1`$, so (5) is true for $`r=0`$; we shall now show that (if $`rR1`$), for large $`n`$, (5) implies the same inequality with $`r+1`$ in place of $`r`$.

Observe first that, by construction, $`\mathrm{exp}(c_rϵ)\mathrm{exp}(c_Rϵ)<Q`$, whence $`q_r(n)\mathrm{exp}(c_rϵn)<Q^n`$ for large enough $`n\mathrm{\Sigma }`$. We may then apply the Theorem with $`p=p_r(n)`$, $`q=q_r(n)`$ and deduce that for large $`n\mathrm{\Sigma }`$ we have

$$\left|\frac{\alpha (n)}{\beta (n)}\frac{p_r(n)}{q_r(n)}\right|q_r(n)^k\mathrm{exp}(ϵn).$$

Hence, combining with (4),

$$q_{r+1}(n)q_r(n)^{k1}\mathrm{exp}(ϵn)\mathrm{exp}(((k1)c_r+1)ϵn)=\mathrm{exp}(c_{r+1}ϵn)$$

by the inductive assumption and the definition of $`c_{r+1}`$. This induction proves (5) for $`rR`$.

Finally, by (5) with $`r=R`$, we have $`q_R(n)\mathrm{exp}(c_Rϵn)`$ for large $`n\mathrm{\Sigma }`$, whence $`q_R(n)<Q^n`$, since $`\mathrm{exp}(c_Rϵ)<Q`$ by construction. But then the Theorem holds for $`p=p_R(n)`$, $`q=q_R(n)`$, leading in particular to $`0=|(\alpha (n)/\beta (n))(p_R(n)/q_R(n))|>0`$, a contradiction which concludes the argument.

Proof of Corollary 2. For convenience let us denote by $`\psi (x)`$ the length of the continued fraction for the rational number $`x`$.

We start with the hardest half of the proof; namely, assuming that $`\psi (\alpha (n)/\beta (n))`$ is bounded for $`n`$ in an infinite sequence $`\mathrm{\Sigma }𝐍`$, we prove that $`\alpha /\beta `$ has a finite continued fraction over $``$.

Let us argue by induction on $`\mathrm{}(\alpha )+\mathrm{}(\beta )`$, the result being trivial when this number is $`2`$.

Since $`|\psi (x)\psi (1/x)|1`$, we may plainly assume $`\mathrm{}(\alpha )\mathrm{}(\beta )`$. By our present assumption, the hypothesis of Corollary 1 cannot hold for $`\alpha ,\beta `$, so there exists $`\zeta `$ such that, putting $`\eta =\alpha \zeta \beta `$, we have $`\mathrm{}(\eta )<\mathrm{}(\beta )`$. For large $`n`$, we have $`\beta (n)0`$ and

$$\frac{\eta (n)}{\beta (n)}=\frac{\alpha (n)}{\beta (n)}\zeta (n).$$

Since $`\zeta `$, the rational numbers $`\zeta (n)`$, $`n𝐍`$, have a finite common denominator $`D>0`$. We now appeal to \[S1, Thm. 1\], which bounds $`\psi ((p/q)r)`$ in terms of $`\psi (p/q)`$, where $`r`$ is a rational number with fixed denominator. Applying this with $`p/q=\alpha (n)/\beta (n)`$, $`r=\zeta (n)`$ and noting that $`\psi (\alpha (n)/\beta (n))`$ is bounded by assumption for $`n\mathrm{\Sigma }`$, we immediately obtain that the numbers $`\psi (\eta (n)/\beta (n))`$ are also bounded for $`n\mathrm{\Sigma }`$. Since $`\mathrm{}(\eta )+\mathrm{}(\beta )<\mathrm{}(\alpha )+\mathrm{}(\beta )`$, the inductive assumption implies the existence of a finite continued fraction expansion over $``$ for $`\eta /\beta `$. In turn, this yields the same for $`\alpha /\beta `$, proving the conclusion.

The “converse” part of Corollary 2 is again immediate from \[S1, Thm. 1\].

Like for Corollary 1, the condition that $`\alpha /\beta `$ admits a finite continued fraction over $``$ may be checked effectively. To verify this, observe first that, if $`\alpha /\beta `$ admits a continued fraction over $``$ as in the statement, then it also admits an expansion such that $`\mathrm{}(\zeta _i)1`$ for all $`i1`$; this claim follows at once from the continued fraction identity

$$[A,c,B]=[A+c^1,c(cB+1)],$$

which allows to absorb all possible “constant” partial quotients $`c`$.

With this proviso (but not otherwise) the continued fraction over $``$ is unique (if it exists); its existence may be checked e.g. by iterating the effective criterion for checking the assumption of the Theorem (or of Corollary 1), as in the comments after Lemma 1.

Proof of Corollary 3. We could invoke Corollary 2, but it is perhaps simpler to argue directly, by induction on $`a+b`$ (the assertion being empty for $`a+b=2`$). On exchanging $`a,b`$ we may assume that $`a>b>1`$.

Now, we may assume that $`a`$ is divisible by $`b`$; in fact, if this does not hold, we plainly have $`\mathrm{}(a^n1\zeta (b^n1))a>b`$ for any $`\zeta `$; in turn, we may then apply (a fortiori) Corollary 1 to $`\alpha (n)=a^n1`$, $`\beta (n)=b^n1`$, yielding the present assertion.

Write then $`a=bc`$, where $`c`$ is a positive integer $`<a`$. Note that $`b,c`$ are multiplicatively independent (since $`a,b`$ are such) whence the continued fraction for $`(c^n1)/(b^n1)`$ has length tending to infinity, by the inductive assumption. But then the identity

$$\frac{a^n1}{b^n1}=c^n+\frac{c^n1}{b^n1}$$

immediately implies the sought conclusion.

Final remarks. (a) It seems a very difficult problem to quantify the corollaries, namely to prove an explicit lower bound for the length of the relevant continued fractions. Even in the special case of Pourchet’s Theorem, this seems to be related with an explicit version of Ridout’s (or Roth’s) Theorem, which presently appears inaccessible.

(b) The methods of proof probably lead to results similar to the Theorem, where $`\alpha (n)/\beta (n)`$ is replaced by some algebraic function of a power sum, like e.g. the $`d`$-th root $`\alpha (n)^{1/d}`$. The pattern should combine the arguments from, say, \[CZ1, Cor. 1\] (or \[CZ4, Thm. 2\]) with the above ones.

In case $`d=2`$ it is perhaps possible to obtain corollaries similar to the present one, but in the direction of Schinzel’s mentioned papers; namely, under suitable assumptions on the power-sum $`\alpha _𝐐`$, the length of the period of the continued fraction for $`\sqrt{\alpha (n)}`$ tends to infinity with $`n`$.

References.

\[BCZ\] \- Y. Bugeaud, P. Corvaja, U. Zannier, An upper bound for the G.C.D. of $`a^n1`$ and $`b^n1`$, Math. Z. 243 (2003), 79-84.

\[C\] \- P. Corvaja, Une application nouvelle de la méthode de Thue, Annales de l’Institut Fourier 45, (1995), 1177-1203.

\[CZ1\] \- P. Corvaja, U. Zannier, Diophantine equations with power sums and Universal Hilbert Sets, Indag. Mathem., N.S., 9 (3) (1998), 317-332.

\[CZ2\] \- P. Corvaja, U. Zannier, Finiteness of integral values for the ratio of two linear recurrences, Invent. Math. 149 (2002), 431-451.

\[CZ3\] \- P. Corvaja, U. Zannier, On the greatest prime factor of $`(ab+1)(ac+1)`$, Proc. Amer. Math. Soc., 131 (2003), 1705-1709.

\[CZ4\] \- P. Corvaja, U. Zannier, Some New Applications of the Subspace Theorem, Compositio Math. 131 (2002), 319-340.

\[E\] \- Y.-H. Evertse, On sums of $`S`$-units and linear recurrences, Compositio Math., 53 (1984), 225-244.

\[M\] \- M. Mendès-France, Quelques problèmes relatifs à la théorie des fractions continues limitées, Sém. Delange-Pisot-Poitou, 13e année (1971/72), Théorie des nombres, 1, Exp. No. 2, Secrétariat Mathématique, Paris, 1973.

\[M2\] \- M. Mendès-France, Sur les fractions continues limitées, Acta Arith. 23 (1973), 207-215.

\[R\] \- D. Ridout, The $`p`$-adic generalization of the Thue-Siegel-Roth theorem, Mathematika, 5 (1958), 40-48.

\[S1\] \- A. Schinzel, On some problems of the arithmetical theory of continued fractions, Acta Arith. 6 (1961), 393-413.

\[S2\] \- A. Schinzel, On some problems of the arithmetical theory of continued fractions II, Acta Arith. 7 (1962), 287-298.

\[Schm1\] \- W.M. Schmidt, Diophantine Approximation, Springer LNM 785, 1980.

\[Schm2\] \- W.M. Schmidt, Diophantine Approximations and Diophantine Equations, Springer Verlag LN 1467, 1991.

\[V\] \- P. Vojta, Roth’s theorem with moving targets, Internat. Math. Res. Notices, 3 (1996) 109-114.

\[Z\] \- U. Zannier, Some applications of Diophantine Approximation to Diophantine Equations, to appear in the series “Dottorato di Ricerca in Matematica”, ETS, Pisa.

Pietro Corvaja

Dipartimento di Matematica, Università di Udine

via delle Scienze 206, 33100 Udine (Italy)

corvaja@dimi.uniud.it

Umberto Zannier

Istituto Univ. di Architettura, D.C.A.

S. Croce 191, 30135 Venezia (Italy)

zannier@brezza.iuav.unive.it