figure 5. the virtual bird can hold on to the baton or pass it to any neighbor.

figure 6. the flight net and path integrals in R4.

other can be brought together by other flocks. The design of a protocol involves the geometric analysis of the flight net (Figure 6), which is the unfolding of all neighboring relations in four-dimensional spacetime. This is a tree-like geometric object in R4 with local convexity properties, which encodes the exponentially large number of influences among birds. The position of each bird can be expressed by a path integral in that space. Examining these integrals (actually sums) and the geometry that produces them allows us to answer the question above4.

While flocks cease to fragment reasonably rapidly (thus
ensuring quick physical convergence), it might take very long
for them to stop merging. How long? A tower-of-twos of height
logarithmic in the number of birds. Surprisingly, this result
is tight! To prove that, we regard the set of birds as forming a
computer and we ask a “busy-beaver” type of question: What is
the smallest nonzero angle between any two stationary veloci-
ties? The term “stationary” refers to the fact that each flock is
a coupled oscillator with constant stationary velocity (the low-
est mode of its spectrum). These velocity vectors form angles
between them. How small can they get short of 0? (Zero angles
correspond to flocks flying in parallel.) To answer this question
requires looking at the flocks of birds as a circuit whose gates,
enacting flock merges, produce a redistribution of the energy
among the modes called a spectral shift. It is remarkable that
the busy-beaver function of this exotic computing device can
be pinned down almost exactly: the logarithmic height of the
tower-of-twos is known up to a factor of 4.

5. DiffusiVe infLuence s Ystems

We set f (x) = (P(x) ⊗ Id) x ∈ (Rd)n, where P(x) is a stochastic matrix whose positive entries correspond to the edges of G (x) and are rationals assumed larger than some arbitrarily small r > 0. We grant the agents a measure of self-confidence by adding a self-loop to each node of G(x). Agent i computes the i-th row of P(x) by means of its own algebraic decision tree; that is, on the basis of the signs of a finite number of dn-variate polynomials evaluated at the coordinates of x. This high level of generality allows G (x) to be specified by any first-order sentence over the reals.f Note how the descriptive complexity resides in the communication algorithm G, which can be arbitrarily expressive: the action f is confined to diffusion (with different weights for each agent if so desired).

By taking tensor powers (no details needed here), we can linearize the system and reduce the dimension to d = 1, so f (x) = P(x)x, where P(x) = Pc, for any x ∈ c, and c is an atom (open n-cell) of an arrangement of hyperplanes in Rn, called the switching partition SP (Figure 7). We assume self-confidence but not mutual confidence, that is, positive diagonal entries but not necessarily bidirectionality.

In spite of having no positive Lyapunov exponents, diffusive systems can be chaotic and even Turing-complete. Perturbations wipe out their computational power, however, by making them attracted to periodic orbits. Such systems, in other words, are clocks in disguise.g This dichotomy requires a subtle bifurcation analysis, which we sketch in the next section.

Theorem 1: 6 Given any initial state, the orbit of a diffusive influence system is attracted exponentially fast to a limit cycle almost surely under an arbitrarily small perturbation. The period and preperiod are bounded by a polynomial in the reciprocal of the failure probability. In the bidirectional case, the system is attracted to a fixed point in time nO(n)|log e|, where n is the number of agents and e is the distance to the fixed point.

The number of limit cycles is infinite, but if we measure distinctness the right way (i.e., by factoring out foliations), there are actually only a finite number of them.h The critical region of parameter space is where chaos, strange attractors, and Turing completeness reside. It is still very mysterious.i This does not mean that it is difficult to identify at least some of the critical points. Here is a simple f This is the language of geometry and algebra over the reals with statements specified by any number of quantifiers and polynomial (in)equalities. It was shown to be decidable by Tarski and amenable to quantifier elimination and algebraic cell decomposition by Collins7. g To perturb the system means randomly perturbing the switching partition and making exceptions for infinitesimal and indefinitely disappearing edges. The conditions are easy to enforce and, in one form or another, required. Note that we do not perturb the matrices or the initial states. h A limit cycle is an attracting periodic orbit, for example, {− 1, 1} where x(t) = (− 1)t + 2−t x(t− 1) and x(0) ∈ R. i I only know that the critical region has measure zero and looks like a Cantor set.