{'fraction_non_alphanumeric': 0.040662396763863136, 'fraction_numerical': 0.011377043654137872, 'mean_word_length': 4.867243510506799, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exact Solution of a Jamming Transition: Closed Equations for a Bootstrap Percolation Problem

Jamming, or dynamical arrest, is a transition at which many particles stop moving in a collective manner. In nature it is brought about by, for example, increasing the packing density, changing the interactions between particles, or otherwise restricting the local motion of the elements of the system. The onset of collectivity occurs because, when one particle is blocked, it may lead to the blocking of a neighbor. That particle may then block one of its neighbors, these effects propagating across some typical domain of size named the dynamical correlation length. When this length diverges, the system becomes immobile. Even where it is finite but large the dynamics is dramatically slowed. Such phenomena lead to glasses, gels, and other very long-lived nonequilibrium solids. The bootstrap percolation models are the simplest examples describing these spatio-temporal correlations. We have been able to solve one such model in two dimensions exactly, exhibiting the precise evolution of the jamming correlations on approach to arrest. We believe that the nature of these correlations and the method we devise to solve the problem are quite general. Both should be of considerable help in further developing this field.

There exists within nature a whole class of systems that exhibit a geometrical 'percolation' transition at which they become spanned by a single infinite cluster extending across the whole system [1][2][3]. Such transitions may be observed, for example, by randomly occupying lattice sites at some prescribed density. Spatio-temporal particle correlations implied by simple dynamical models may also be studied using percolation ideas. Indeed, since its introduction [4,5], the potential of the bootstrap percolation problem [6,7] to analyze the dynamics of a system of highly coupled and locally interacting units has been recognized. Latterly the range of applications has continued to grow [8][9][10][11][12].
This problem is of particular interest because of a growing focus on, and appreciation of, the unifying role of dynamical arrest [13][14][15][16][17], or 'jamming' [18] in the formation of complex condensed states of matter. Despite many advances, there is as yet no complete and fundamental conceptual framework to describe the phenomena. In comparable situations it has been an important lesson of critical phenomena [19,20] that an exact solution, even of a two dimensional model system, can be of great assistance in broader efforts to understand the issues. Thus, an exact closed solution of one bootstrap problem (with all of the implications of strong packinginduced coupling and divergent correlated domains) would represent, even without direct access to transport coefficients, a solution of a non-trivial (and non-mean field) 'jamming' or arrest scenario. We will present such a solution in this paper. That such a treatment is possible must be considered surprising, for there have been no prior indications of such simplification.
The connection of the bootstrap percolation problem to jamming phenomena is clear. Thus, particles, processors, or members of a competing population are considered to become 'inactive' (or blocked) depending on the state of their immediate environment. The relationship of the bootstrap process to dynamics is as follows. Beginning with a lattice occupied according to the steady state (usually random) distribution of particles of the underlying dynamical model, units not blocked (i.e. movable) are iteratively removed. Those remaining are blocked irrespective of the arrangements of the movable ones in the configuration. Onset of extended mutual blocking (in which one unit is prevented from 'moving' by its neighbors and also contributes to the blocking † of some of those neighbors) manifests itself by a sharp change in the occupancy of the lattice after the bootstrap process. Percolation occurs when, after the iterative procedure finishes, the blocked clusters extend across the whole system. Even on approach to such a transition, singleparticle movement requires a long sequential and contingent string of changes in surrounding units. In the underlying dynamics this long string implies a growing correlation length-and accompanying time-scale, both determined by mutual blocking effects. This ('dynamical') length scale is named the bootstrap length. Apart from those errors introduced by removal (rather than movement, and subsequent averaging) of particles, this is the characteristic blocking or 'jamming' length over which motions can occur only by rare and co-operative motions. Beyond it, motion is diffusive.

Methods
Bootstrap percolation transitions are believed to fall into two broad 'universality' classes [21], depending on the dimensionality d and on the local rule 'c' † , and we might expect this to be reflected in the classes of jamming. The first type is a continuous transition in which the blocked domain size diverges as a power law in system size and density. The second type, when d ≤ c < 2d − 1, displays discontinuous transitions with different essential singularities.
Specifically, the case c = d † [5,22,23] is believed to be more relevant to particle jamming, and † In 'conventional' bootstrap percolation, particles are removed if they are surrounded by c or fewer particles. In 'modified' bootstrap percolation, an additional condition requires the neighboring vacant sites to be secondneighbor to each other.
there the bootstrap length ξ diverges as ξ = exp o(d−1) (A/(1 − ρ)) [24] (here exp o(d−1) is the exponential function iterated d − 1 times). For the two-dimensional square lattice (c = 2) † , theoretical calculations based on a set of bounds [25] have resulted in an elegant outcome; essentially exact asymptotic results, lim ρ→1 ξ→∞ 2(1 − ρ) log ξ = A, where A = π 2 /9 and π 2 /3 for conventional and modified bootstrap † respectively. It transpires that at high packing, this length is also the typical distance between increasingly rare voids (later named connected holes) in the configuration [26], providing a key connection between the spatio-temporal correlations, and the packing of particle configurations that determine them.
A striking aspect of this arena of research is that all attempts [27,28] (including some of the most extensive calculations to have been applied in statistical mechanics) to obtain agreement between simulations and known exact asymptotic results have so far failed. Indeed, the bootstrap problem has generated topical interest [29] because of the notorious (apparent) lack of agreement between simulation [27,28] and theoretical [24,25,[30][31][32] developments.
In our study we introduce holes or 'dynamically available volume' [22,33], these being empty sites on the lattice into which at least one neighboring particle can move. A hole is termed 'connected' or disconnected respectively if the lattice can (or cannot) be vacated by sequentially removing particles using it as an origin in the bootstrap process. In the underlying dynamics, connected holes typically initiate a sequence of moves that will mobilize every particle in the system. They are therefore the mediators of transport in the system, and the order parameter of arrest. For a system to bootstrap (and therefore not be jammed) it must contain at least one connected hole. We identify ν as being the connected hole density (average frequency of such occurrences in the lattice). In the high density regime, the bootstrap length may therefore be calculated from ξ = 1/ν 1/d [26], the particles within this distance being movable only via the restricted motions made available by a single connected hole.
Disconnected holes in the modified bootstrap problem (for d = 2, c = 2-modified † ) are found to be enclosed by a single continuous rectangular boundary or 'cage' of particles, none of which can be moved by any particle rearrangements inside the boundary. They cannot be formed for edge lengths much larger than l c (the cut-off size, l c ∼ 1/(1 − ρ)) for then there is typically an intervening vacancy. We can therefore sample particle removal paths around holes directly in simulations [26]. If particle domains much larger than l c can be removed, the hole may be identified as connected, rendering the simulation very efficient. Thus, the (•) points in the ( Fig.   1) are hole densities one would obtain for systems sizes up to L = 220, 000. They constitute the largest simulations to have been carried out on a two-dimensional bootstrap problem.
The bootstrap problem is an example of strong (packing-induced) coupling, so theoretical developments, including simple extensions of previous approaches [25] involving asymptotic bounds, invariably fail. Instead we define new intermediate states that imply bootstrap-type (ie spatio-temporal) correlations. Transitions between them may then be composed into sequences or particle 'removal paths' whose steps are de-correlated, and transition coefficients (c from state to state are then easily calculated from the random ensemble. These intermediate states are rectangular regions (of size k by k +s, see Fig. 2). They are, irrespective of their orientation in space, completely empty, or empty save for one, two (adjacent) or three edges occupied entirely by particles. The probabilities that such rectangles are visited during the emptying process are P (i) k,k+s (ρ), i = 1, 4 (the states P (2) k+s,k (ρ) and P (4) k+1,k (ρ) are also defined, these bearing the same meaning as P (2) k,k+s (ρ) and P (4) k,k+1 (ρ), but for the orientation of the occupied lines with respect to the direction of the elongation). In defining the transitions between them, only certain directions (illustrated by arrows in Fig. 2) of the removal paths are permitted ‡ . For example, if the path leads to a state '1' (probability P (1) k,k+s (ρ)) the next attempt to grow the vacated rectangle will be via either of the two 'long' directions, this requiring removal of particles along one or other of those directions. These directions are chosen randomly, with equal probability. ‡ These movements tend to restore the symmetric empty square, except for the state represented by P (2) k,k+s (ρ).  [26]), the last point being equivalent to a system of size 220,000, the current limit of computer simulation. The solid line represents the result of our new exact theory. These are compared with the asymptotic result exp(−π 2 /3(1−ρ)) (dashed line) [25]. We recall that results for the total connected hole density ν coincide with 1/ξ 2 at high density [26], where ξ is the bootstrap percolation correlation length. Inset: ∂ν/∂ρ (Red) and ∂ 2 ν/∂ρ 2 (Blue) against density in the same range. ∂ν/∂ρ increases sharply from −1.73 to approximately zero with an inflexion signalled by the peak in ∂ 2 ν/∂ρ 2 at ρ = 0.85. The next intermediate state will be a k + 1 by k + s rectangle, either in state '1' or in state '2', since these represent the only outcome of that transition. The transition ('jump') rates for these two choices are (1 − ρ k+s ) and ρ k+s , and they define c (1,1) k+1,k+s (ρ) and c (2,1) k+1,k+s (ρ) respectively.
We reiterate these choices. In essence a highly correlated bootstrap process becomes uncorrelated within the subset of intermediate states, leading to an exact method to identify connected holes by random sampling of a constrained set of states. For connected holes we remain within P [1] k,k+s P [2] k,k+s P [2] k+s,k P [3] k,k+s P [4] k,k+s Figure 2: Intermediate states. Intermediate local configurations surrounding a candidate hole required in evaluation of the sum over 'particle removal paths' that are used to empty the lattice (k = 4 and s = 3 in the example). The white circles are sites that have been emptied in previous steps, and the red disks are temporarily blocked particles along the perimeter edges. For each configuration, the arrows indicate allowed transitions (to be selected at random) involving the growth of one boundary line by one step. This process restores that local configuration to another intermediate state (P These features constitute the key elements of the methodological advances described in this paper, and similar treatments may be attempted for other such problems in future [26].
The exact equations representing the process may be written in closed form, Here s ≥ 0 and the equations are solved numerically subject to the initial conditions, P (i) 1,k = (1− ρ)δ 1i δ 1k . These equations converge numerically for k ≫ l c and 0 < s/k < 1. The connected hole density, the probability to bootstrap a square of indefinite size, is then given by the expression, Because of the cut-off in cage size, these equations converge very rapidly and there are no practical limitations on the density range that can be studied by computer, as already discussed in [26]. Based on exact asymptotic analysis, the quantity −2(1 − ρ) log ξ + π 2 /3 = f (ρ) would be predicted to be positive and vanishing in the asymptotic limit (ρ → 1). Now we have numerically calculated the solution for the modified model up to the largest sizes allowed by the precision of the computer, and indeed this quantity does decrease monotonically when ρ approaches 1. However, at ρ ∼ 0.9965, f (ρ) is still of order unity, rather too large to be neglected. Suffice it to say that the true exact bootstrap length for this density is ξ ∼ 10 150 .
Thus in reality, for large but finite systems one sees ξ = exp[−f (ρ)/2(1 − ρ)] exp[π 2 /6(1 − ρ)], f (ρ) being a decreasing but 'always' finite function of (1 − ρ). Equations (1) may also be solved asymptotically. We illustrate in Fig. 3 the density of cages (dimension k by k + s) at particle density ρ = 0.95 and the probability for vacated square-like regions P k,k (ρ). There we see that cages become rare somewhat beyond the critical size l c § . The reduction of cages, capable of § The threshold value lc in (Fig. 3) can be understood as that size at which, with equal probability, the droplet preventing bootstrapping, leads to the dominance of P (1) k,k (ρ) and P (1) k,k+1 (ρ) beyond the critical core size. Particle density ρ = 0.95. Illustrative calculation in the 'metastable' or droplet state. The red surface represents the probability (in log 10 scale) that a rectangular cage surrounding a vacant site is first found at size k by k + s. The probability density of cages is plotted against k (core size) and s (asymmetry-degree), and decreases monotonically in k. High degrees of asymmetry are very rare. The probability of finding an empty square of size k is also plotted for a comparison. The intersection with the corresponding cage size distribution is at l c = 25, indicating that cages become statistically irrelevant (i.e. extremely rare) already at sizes much smaller than ξ ∼ 10 5 .
can either grow or find a cage in the next step.

Results
The results for connected hole density, the full curve in Fig. 1, or equivalently the bootstrap length, settle a longstanding mystery, the theory now being in precise agreement with simulation where the latter is applicable. They permit us to explore the nature of the problem all the way from lower density to the asymptotic form, as solutions to a single closed set of equations. It is now clear that there has never been any inconsistency between the simulations and asymptotic results. They were both correct, but direct comparison is not appropriate for any range of density appropriate to computer simulation. The numerical results (and associated asymptotic analysis) from these same equations are sufficient to show that the previously reported exponential asymptotic form [25] occurs for such high density (and large length-scales) that systems of physical interest will never reach this regime. As noted in the previous parapraph, even at system sizes of ξ ∼ 10 150 there remains a singular model-dependent pre-factor to the leading exponential. Formulae purporting to describe the behavior for finite systems (or systems at finite density) in terms of a simple exponential are effective fits, and possess no fundamental significance.
The real paradoxes lie in the Physics. As we now show, this Physics turns out to be much richer than had been supposed until now. In discussing these issues we have in mind primarily the clarification of the model system, though the results may relate to recent experimental observations, and could help to clarify these issues also. We give only pointers to the new directions.
Recall that the connected hole density in a region characterizes the ease of long-ranged movement of particles in that region, these being the empty spaces on the lattice that permit sustained motion. Given this, the insets to (Fig. 1) are striking. There we show both the first (ν = ∂ν/∂ρ = −∂ν/∂v ) and second derivatives (ν = ∂ 2 ν/∂ρ 2 = ∂ 2 ν/∂v 2 ) of the connected hole density with respect to particle (or vacancy, v) density. The former is the long-wavelength limit of the response of dynamical processes in the system to small changes in particle density. We observe a 'transition' in the response of the dynamics to small changes in particle density. For densities lower than ρ = 0.85 (the 'unstable' regime ¶ ) a small local decrease of density leads to many new connected holes, and thereby opens up many new transport pathways. For particle densities higher than this (the 'metastable' regime) the response of dynamical properties to a density fluctuation is vanishingly small.
Albeit in this quite new context of near-arrested systems, these ideas make contact with early prescient remarks [30] in which it was suggested that bootstrap models might offer an explanation for the decay of the metastable state and (by extension) the 'spinodal' transition to unstable state decay. Indeed, the two regimes of connected hole density reflect the relaxation of particle configurations by two characteristic means. At low density, configurations are intrinsically unstable to small spatial variations of density, these leading to new dynamical pathways reminiscent of 'spinodal waves' that enable efficient relaxation of quite dense particle configurations. Beyond the peak at ρ = 0.85 the state develops metastability, this being reflected also in the characteristic exponentially small connected hole density there, and the decay of such configurations becomes much more difficult. In (Fig. 4) we illustrate these ideas in a more visual manner. Thus, the left picture (Fig. 4) represents a configuration at density ρ = 0.79. There we see the development of 'spinodal-like' patterns of empty space as particles are removed from the unstable state. The right picture (Fig. 4), at ρ = 0.915 exhibits the classical appearance of decay of the metastable state, including growing empty droplets, with smaller sub-critical droplets failing to grow any further. These analogies will prove deeply helpful in future formulations of quantitative laws for dynamical arrest also [34]. ¶ The low density near-arrest regime has a hole density that is well fitted to power laws (ρc − ρ) µ with ρc and µ suitably defined in the range of interest, whilst the high density regime is well-fitted to the exponential law exp  The peak of the second derivative in (Fig. 1) defines a transition between two near-jammed regimes, the first 'unstable' regime where spatial density heterogeneities produce large heterogeneities also in the dynamics, the second 'metastable' regime where the response is much weaker. This observation may well be related to recent ideas derived from simulations [35,36] and experiments [37][38][39] where dynamically heterogeneous processes have been viewed as intrinsic to the arrest process. The 'size' of these domains in our bootstrap calculation (1/ √ ν) in the 'unstable' regime reaches a maximum value of l d = 8 at ρ = 0.85. Thereafter the dynamically heterogeneous processes change their nature to 'droplets' of movement and the system continues to slow further, as the number of connected holes decreases. Thus, the dynamical (here bootstrap) correlation length continues to diverge, but no longer has the same quality of 'dynamical heterogeneity'.
That there exists two such regimes, with a clearly defined transition between them has not been previously clarified in the scientific literature. There is inferential evidence from simulations and experiment that dynamical heterogeneities near 'arrest' [36] might change as the system further progresses towards complete arrest. However, the broader implication of this discussion is that dynamical heterogeneities, and the 'metastable' state, could be formulated into a theoretical approach via these response functions in available volume. It is encouraging to note that, with the advent of new microscopy tools [37,38], there has emerged the possibility to directly measure these new more appropriate order parameters and response functions using direct optical imaging.
We do not here deal with the issue in detail, but note that, associated with the two regimes of the response function, the transport coefficients governing these two regimes should be quite different. This observation might also point to a resolution of another long-standing controversy about the nature of the dynamical laws (power law or 'exponential') near arrest ¶ .

Discussion
In summary, a new approach to treating strong jamming correlations using random paths between appropriately selected states means that the two-dimensional bootstrap model can now be solved exactly. This advance allows us to explore phenomena far beyond the reach of simulations using modern computers, and provides us with the first complete picture of the onset of arrest . The conclusions of the study are intriguing and resolve long-standing apparent conflicts between theoretical and simulation treatment of these problems.
True arrest occurs only as a limit of a 'metastable state' when the system is dense-packed on the lattice. Thus, even the smallest amounts of available volume means that motion is It is possible to show that more complicated jamming scenarios may also be exactly solved in two dimensions providing the defining constraints on particle movement remain short-ranged on the lattice. still possible, albeit at enormously long time-scales. The finite size dependence of this regime is barely appreciable, but nevertheless persists up to the fully packed limit and means that neither simulations, nor nature, can ever access length scales where simple asymptotic results in terms of density are valid * * . However, the results written in terms of connected hole density, or dynamically available volume, are simple. This has deep implications for the way in which experiments (indeed the whole study of dynamical arrest) might be framed in future [22,33].
Finally, and important to the general arena of dynamical arrest, we have shown how the conceptual infrastructure of order parameters, dynamically available volumes, spatio-temporal correlation lengths, and equations to represent them, may be framed into a closed theory, from which rational approximations emerge. However, it is our belief that these new principles governing treatment of the bootstrap are close to those required to frame a comparable dynamical theory, from which one would obtain the transport coefficients in systems that are dynamically slowed.
Understanding and ultimately calculating these transport coefficients in dynamically slowed systems from a fundamental theoretical basis, and comparing them to results from carefully designed experiments, constitutes one of the outstanding challenges of those interested in the field of dynamical arrest.