A long enough chain never locks

A crowd of clocks that falls into step found Kuramoto’s threshold for a population in which every oscillator feels every other equally: below a coupling of twice the spread of the natural frequencies nothing happens, above it a cluster forms, and the threshold does not depend on how many oscillators there are. It ended on the other extreme, a population in which each oscillator feels only its neighbours, and stated without measuring it that a long chain never fully synchronises. This essay measures it, and finds that the threshold for complete locking of a chain can be read off the natural frequencies by a single running sum, that it grows like the square root of the chain’s length, and that its distribution across random chains is one of the classical laws of statistics.

The chain is the simplest network that is not complete. Oscillator $i$ has natural frequency $\omega_i$ and phase $\theta_i$, and it is pulled only by oscillators $i - 1$ and $i + 1$:

$$\frac{d\theta_i}{dt} = \omega_i + K\big[\sin(\theta_{i+1} - \theta_i) + \sin(\theta_{i-1} - \theta_i)\big],$$

with the two end oscillators having only one neighbour each. Locking means that every oscillator runs at the same average frequency, so the whole chain turns together like a single clock with a fixed pattern of phase differences along it.

The link that has to carry the most #

Suppose the chain has locked, with every oscillator running at the common frequency $\bar\omega$, which must be the average of the natural frequencies because the coupling terms cancel in pairs when all the equations are added. Now add up only the equations of the first $k$ oscillators. Every coupling term between two of those oscillators cancels with its partner, and only the term across the link between oscillator $k$ and oscillator $k + 1$ survives:

$$K\sin(\theta_{k+1} - \theta_k) = -\sum_{i \le k} (\omega_i - \bar\omega) = -S_k.$$

So the link after oscillator $k$ must carry the whole imbalance $S_k$ of natural frequencies on one side of it: the first $k$ oscillators, if they are faster than average in total, must be held back by exactly that much, and the only thing that can hold them back is the one link joining them to the rest. A sine is at most one, so the link can carry at most $K$. A locked state therefore exists exactly when every running total $S_k$ lies between $-K$ and $K$, and the locking coupling is the largest of them in absolute value:

$$K_L = \max_k |S_k|.$$

This criterion was found by Bard Ermentrout and Nancy Kopell in 1984, and Steven Strogatz and Renato Mirollo used it in 1988 to study chains with random frequencies. It turns a question about a nonlinear system of differential equations into a question about a list of numbers.

For the chain of forty in the hero figure the running sums wander up and down and reach their largest size, $4.482$, at link 27. That is the chain’s locking coupling. At $4$ per cent above it, the simulation runs every oscillator at one frequency to within $2 \times 10^{-5}$, the error of the integration. At $4$ per cent below it, the chain breaks in two, and the break is at link 27: the first 27 oscillators run together at one frequency, the last 13 at another, $0.065$ apart. The weakest link fails first, and it is weakest not because its own oscillators are unusual but because it carries the accumulated imbalance of everything on one side.

The shape of a locked chain #

The same equation that gives the threshold gives the locked state itself. Above $K_L$, the phase difference across link $k$ is fixed by $\sin(\theta_{k+1} - \theta_k) = -S_k/K$, so the phases along a locked chain are a picture of its running sums: where the sum climbs, the phases fall behind link by link, and where it falls, they pull ahead. Every link sits at an angle whose sine is its share of the load, and as $K$ decreases towards $K_L$ the most heavily loaded link turns towards a right angle, the largest pull a sine can deliver.

Each link’s equation has two solutions, an angle and its supplement, so a chain of $N - 1$ links has $2^{N-1}$ locked states in all whenever $K$ exceeds $K_L$. Only one of them is stable: the one in which every link takes the angle nearer nought, so that every cosine is positive. The stability calculation linearises the equations about the locked state and finds a weighted version of the graph Laplacian, with link $k$ weighted by $K\cos(\theta_{k+1} - \theta_k)$, and a Laplacian with positive weights pushes every disturbance back towards the locked state. At $K = K_L$ the weakest link’s cosine reaches nought, its two solutions merge, and the stable locked state disappears in a saddle-node bifurcation — the same event that how a lock comes apart followed at the edge of an Arnold tongue, here happening at one particular link of a long chain.

That is why the chain breaks exactly at the link with the largest running sum: it is the first link whose cosine reaches nought, and once it slips the two sides of it become independent chains, each with its own average frequency and its own running sums measured from that average.

Checked one chain at a time #

The criterion is a theorem, and the next figure checks it the way it would be used: from the natural frequencies alone, predict the locking coupling, then simulate just above and just below.

Every one of the sixteen chains behaves as predicted. Three per cent above its own $K_L$, the spread of average frequencies is at most a few hundred-thousandths, and for most chains far less — down to $10^{-13}$, which is the arithmetic, not the dynamics. Three per cent below, the spread is between five hundredths and a third. The prediction used nothing but the frequencies and a running sum. That is worth emphasising because the alternative — finding the threshold by simulating at many couplings and watching for locking — is slow and unreliable near the threshold, where the oscillators take a long time to settle and look nearly locked for a long time before they slip.

The square root of the length #

For a chain whose natural frequencies are drawn independently from a distribution with spread $\sigma$, the running sums $S_k$ are a random walk. It is a walk with a constraint: since the frequencies are measured from their own average, the walk must return to nought at the end, $S_N = 0$. A random walk forced to return to its start is called a bridge, and its largest excursion grows like the square root of its length, by the same law that makes the spread of a sum of coin flips grow like the square root of their number and that makes a walk that comes home wander a distance of order $\sqrt n$ before it does. So the locking coupling of a long chain grows like $\sqrt N$.

Averaged over thousands of random chains, the locking coupling divided by $\sqrt N$ is $0.681$ at ten oscillators, $0.808$ at a hundred, $0.850$ at a thousand and $0.860$ at ten thousand, approaching the limit $\sqrt{\pi/2}\,\ln 2 = 0.8687$ from below. So a chain of ten thousand oscillators with frequencies of spread one needs a coupling of about 86 to lock, while a population of the same oscillators all coupled to each other needs only $1.596$, Kuramoto’s $2/(\pi g(0))$, whatever its size.

The consequence is the sentence the earlier essay stated: no fixed coupling locks a long enough chain. For any $K$, a chain of more than about $(K/0.87)^2$ oscillators will typically have some link whose running imbalance exceeds it, and that link will slip. This is the oscillator version of what two chaotic orbits made to agree found for rings of chaotic maps: with only local coupling, the strength needed to make a whole line agree grows with the line’s length, because disagreement accumulates along it faster than a single link can absorb it.

A ring carries a current #

Joining the two ends of the chain into a ring changes the arithmetic in one respect, and the change is instructive. On a ring, the first $k$ oscillators are joined to the rest by two links, one at each end, so the imbalance $S_k$ can be shared between them. There is a free constant: every link can carry its running sum minus the same amount $c$, a circulating flow round the ring that adds to every link equally and cancels in every sum of equations. The ring locks when some choice of $c$ brings every $S_k - c$ inside $\pm K$, and the best choice puts $c$ midway between the largest and smallest running sums. So a ring’s locking coupling is half the range of its running sums rather than the largest of them in size — for a random walk bridge, a smaller number, but one that still grows like $\sqrt N$, with a law found by Kuiper in 1960 for the circular version of the Kolmogorov–Smirnov test.

The circulating constant has a second meaning that matters when the oscillators are identical. Then every running sum is nought, and the ring can lock with any circulation small enough for $K$ to carry: the phases can wind round the ring, each link turned by the same angle, and come back to where they started after a whole number of turns. A chain cannot wind, because its ends are free. A ring can, and the next essay on this subject follows a ring of identical clocks into those winding states.

Kolmogorov’s law #

The limit $\sqrt{\pi/2}\,\ln 2$ is not an arbitrary constant. It is the mean of a distribution that statistics has used since 1933.

As the chain grows, its running sums, rescaled by $\sigma\sqrt N$, converge to a Brownian bridge — the same passage from a jagged walk to a continuous random curve that the walk that becomes a curve watched happen to an unconstrained walk, with the extra condition that the curve end where it began. The convergence is slow at the top end of the distribution, because the largest excursion of a finite walk is a little smaller than that of its limit, which is why the averages in the previous figure approach $0.8687$ from below; the average settles and the wobble does not found the same slow approach in sums of random terms. The bridge is the continuous limit of a random walk tied down at both ends, and the locking coupling converges in law to the largest excursion of that bridge. Andrey Kolmogorov found the distribution of that excursion in 1933: the probability that it stays below $x$ is

$$1 - 2\sum_{k \ge 1} (-1)^{k-1} e^{-2k^2x^2},$$

and its mean is $\sqrt{\pi/2}\,\ln 2$. Four thousand chains of a thousand oscillators each give a histogram that follows Kolmogorov’s density closely, the largest gap between the two distribution functions being $0.039$.

Kolmogorov’s distribution is best known as the law of the Kolmogorov–Smirnov statistic: to test whether a sample of $N$ numbers came from a given distribution, compare the sample’s cumulative proportions with the distribution’s, take the largest difference, and multiply by $\sqrt N$. Under the hypothesis that the sample fits, that difference is the largest excursion of a tied-down random walk, for the same reason the chain’s running sums are: both are cumulative sums of independent deviations that must add to nought at the end. A chain of oscillators deciding whether it can lock is computing a goodness-of-fit statistic of its own natural frequencies.

Breaking into plateaus #

Below the locking coupling the chain does not simply stop being synchronised. It breaks into groups of neighbours that share a frequency, and the last figure follows the breaking as the coupling falls.

Just above the locking coupling the chain of 120 is one cluster. At nine tenths of it, two; at three quarters, still two; at six tenths and a half, three; at four tenths, four; at three tenths and a fifth, seven and eight; at a tenth, thirty-eight. The chain breaks first at its weakest link, where the running sum is largest, and then each piece breaks at its own weakest link, by the same criterion applied to the piece’s own frequencies measured from the piece’s own average. The plateaus are the frequency staircase that Ermentrout and Kopell called frequency plateaus, and they are seen in real chains of coupled oscillators: in the segmented oscillators that drive the swimming of a lamprey, and in the electrical rhythms along the mammalian small intestine, whose pacemaker cells form a chain with natural frequencies falling from one end to the other and are observed to lock in plateaus.

What the simulations cannot show #

The locking criterion is exact and proved; the figures confirm it and use it. What they cannot settle is behaviour that the criterion does not describe. Below the locking coupling the clusters drift past each other, and their average frequencies are determined by the full nonlinear dynamics, not by any running sum; the figure measures them by simulation, and the count of clusters at a given coupling depends on the threshold used to decide when two neighbours share a frequency. Near the boundary between two plateaus the oscillators slip intermittently, and averaged over a finite run their frequencies can look intermediate.

The figures also use the bell curve for the natural frequencies. The square-root law needs only that the frequencies have a finite spread; for frequencies with heavy tails, like the Lorentzian of the earlier essay, the running sums are no longer a Brownian bridge, their largest excursion grows faster than $\sqrt N$, and Kolmogorov’s law does not apply. The figure of the all-to-all threshold, for its part, assumed the bell curve too, and its value of $1.596$ belongs to it.

Still open: from chains to grids #

The chain is solved because a line has a single route between any two points, so every link’s load is fixed by the frequencies. In two dimensions — a grid of oscillators each coupled to four neighbours — there are many routes, the load on each link depends on the phases as well as the frequencies, and no criterion like $\max |S_k|$ is known. Strogatz and Mirollo showed in 1988 that complete locking of a lattice in any dimension also needs a coupling that grows with its size. Whether a cluster spanning a positive fraction of a large lattice can form at a fixed coupling depends on the dimension, and numerical studies since have placed the dimensions at which such partial synchronisation first becomes possible — for frequencies, and separately for phases — at values that are supported by simulation and not proved.

A different question is what happens when the oscillators are identical. Then the running sums are all nought, a chain locks at any coupling, and the interesting structure moves elsewhere — to rings, where the phases can wind round the ring as they lock. How a lock comes apart found a saddle-node bifurcation at the edge of every locked state; a ring of identical oscillators has many locked states at once, and which one a random start chooses is the question the next measurement takes up.

Imbalance carried by one link #

A chain of oscillators can lock only if every link can carry the accumulated difference of natural rhythms on one side of it, and the largest of those accumulated differences is a random walk’s largest excursion. That one observation gives the threshold exactly for every chain, gives its growth like $\sqrt N$ for random ones, identifies its distribution with Kolmogorov’s, and predicts where a chain breaks when it fails to lock. The contrast with the crowd in which everyone feels everyone is complete. There the threshold was set by how many oscillators sit near the centre of the frequency distribution, independent of size; here it is set by the worst cumulative imbalance along a line, and it grows without bound. Coupling to everyone averages disagreement away; coupling to neighbours passes it along, link by link, until some link cannot hold it.