Presumptive Eiruv and the Percolation Transition – Part 1 by Dr. Robert Savit

(2012/5772)

Kol Torah is privileged to reprint a groundbreaking article written by Dr. Robert Savit, an Orthodox physics professor at the University of Michigan with whom Rabbi Jachter worked closely to create the Ann Arbor community Eiruv.  We invite our readers to share their thoughts about this groundbreaking essay which has potential to significantly impact the Eiruvin of our community.

Kol Torah expresses its gratitude to Koninklijke Brille NV publications for permitting us to reprint this important essay, which originally appeared in the journal “Images” volume 5.1 (2011) ISSN 1871-7993, pp.37-43(7). 

Abstract

In this paper I show that, under certain circumstances, it is reasonable to assume the existence of a physical boundary that will constitute a kosher, physical Eiruv around a Jewish community (presumptive Eiruv) without having to explicitly construct, or even identify the Eiruv route.  The basis for this contention lies in an important physical phenomenon called the “percolation transition.”  The central idea is associated with the problem of finding a long connected path that traverses a given area if the elements of the path (short elements that are co-joined to make up the long connected path) occur randomly with some fixed probability.  If the probability of finding these short elements is very small then there will almost never be a long traversing path.  But if the probability of finding the short elements is somewhat higher (but still not extremely large), studies of the percolation transition show that one will almost always be able to find a long traversing path.  The short elements here are the walls, fences, embankments, wires, etc. that can constitute portions of the Eiruv, and the traversing path is the Eiruv itself.  This paper presents the central idea of the percolation transition, exhibits its application to Eiruv, and briefly discusses some of the practical and Halachic issues presumptive Eiruv raises.

I.  Introduction

Establishing a community Eiruv involves three elements:

1. Physical construction of the Eiruv boundary.

2. Acquisition of rights to the enclosed region from the civil authorities.

3. Placement of a symbolic piece of communal property (“Eiruv Chatzeirot”) someplace inside the Eiruv boundary, for example, a box of matzah.

By far the most difficult, expensive and time consuming element is the physical construction of the Eiruv boundary.  Many different elements can be used as part of the Eiruv boundary including existing walls, fences, embankments, and power and cable lines, so long as those elements satisfy a set of Halachic requirements.  The practical process of constructing the boundary consists of seeking routes that use pre-existing elements as much as possible, and filling in the gaps with purpose constructed structures such as Lechis (posts), poles or wires.   As anyone who has tried to establish an Eiruv in an urban area knows, there are many different potential routes for the Eiruv boundary, and the best one, i.e., the one that requires the least modification or construction, may not be the shortest one.  This multiply-connected feature of potential Eiruv elements is both a blessing and a curse.  On the one hand it provides many plausible routes for the Eiruv, some of which may require only minimal (or no) emendation.  On the other hand, exploring the many possible options may require many hundreds of man-hours.  It turns out, however, that under certain circumstances, there may be good reason to assume the existence of a physical, kosher Eiruv, even in the absence of its actual construction or even specific identification.  I call this situation “presumptive Eiruv.”  It is based on a physical and mathematical phenomenon known as the percolation transition.

The percolation problem in physics is the problem of finding a long connected path that traverses a given area if the elements of the path (short elements that are co-joined to make up the long connected path) occur randomly with some fixed probability.  The question of a percolating path arises, for example, in the context of water seeping through a rock:  Suppose we pour water on top of a rock, and suppose that the rock contains fissures or short porous channels, randomly distributed.  The water will flow from the top to the bottom of the rock if there is at least one connected path of the porous channels that connects the top to the bottom of the rock.  We call this a “percolating path”.  If the probability of finding short porous channels is very small, then there will almost never be a long traversing (percolating) path.  On the other hand, if the probability of finding short porous channels in any small region of the rock is near one, then, clearly, there will almost always be a percolating path.  Remarkably, though, it turns out that we do not need a very high probability of finding short porous channels in order to ensure that there will be a percolating path:  If the probability of finding short segments is higher than a certain intermediate value (but still not very close to one) then there will be a dramatic increase in the likelihood of finding a percolating path and one will almost always be able to find such a percolating path.  The dramatic change in the probability of finding a percolating path as the probability of finding short segments increases is called the “percolation transition”. 

In the next section I will describe the idea of percolation and the percolation transition in more detail.  I will not be extremely technical, but will present enough of the general idea to allow the reader to understand the application to Eiruv.  In section III I will apply the results of section II to the problem of establishing an Eiruv.  The general idea is to consider the density of elements in a city that can be used as elements of a kosher Eiruv, and ask when we can expect, with high probability, a “percolating path” consisting of a closed circuit surrounding a Jewish neighborhood.  The model I will discuss in section III will be a highly simplified and idealized version of the situation one is likely to face when actually establishing an Eiruv.  In section IV I will briefly touch on some of the ways in which the simple model of section III would need to be modified in the face of the actual physical constraints imposed by a particular Eiruv including constraints that Halacha imposes on the model of section III.  I will also briefly comment on some of the considerations that are likely to arise in a Halachic analysis of the idea of presumptive Eiruv, and which may consequently affect the rabbinic attitude toward the a priori assumption of the existence of a physical Eiruv.  The paper ends with section V, a brief conclusion.

II.  The Percolation Transition

Kol Torah Pic 1.jpg

The classic percolation problem is the following[1].  Suppose we have a large square grid as shown in Figs. 1a and 1b.  The grid extends over a square of size L by L.  Each line segment joining two points of the grid I will call a “bond”.  Suppose that L is large enough so that the grid contains many bonds.  (I.e., if the length of a bond is b, we suppose that L is much, much greater than b.)  Suppose that each bond can be colored red (editor’s note: Due to ink constraints, the red bonds are printed here as black) with a probability, p. (p is, of course, between zero and one.)  The result of this random coloring process will be that a fraction, p, of the bonds will be red. We ask, as a function of p, what is the probability that we will find at least one completely connected red line that runs from the top of the grid to the bottom of the grid (a percolating path).  Now, if p is very small there will be very few red bonds and so the probability that there is an unbroken red path from the top to the bottom of the grid will be very small.  On the other hand, if p is close to one, then almost all the bonds will be red and there will generally be very many unbroken red paths from the top to the bottom of the grid.  One might suppose that the probability of finding an unbroken red path from the top to the bottom of the grid would be a smooth, gently increasing function of p.  But, in fact, the probability of finding a percolating path as a function of p is not gentle at all.  In Fig. 1a we show an example of a grid constructed with p=0.4, while in Fig. 1b, we have an example with p=0.6.  Notice that there is no percolating path in Fig. 1a, but there are several in Fig. 1b.  The probability of finding a percolating path as a function of p is shown (notionally) by the green line in Fig. 2.  (The other lines in this figure will be explained below.)  We see that the probability of finding a percolating path is very small until p reaches a “critical value”, p*, at which value the probability of finding a percolating path quickly increases to near one.  For the geometry of our problem (a square grid) the value of p* happens to be exactly 0.5.[2]  This abrupt increase in the probability of finding a percolating path as a function of p is called the “percolation transition”.

The graph (purple line) shown in Fig. 2 can be understood qualitatively in the following way:  If L is large, any path that connects the top of the grid to the bottom of the grid will incorporate many bonds, and if p is small then the probability of any one particular path being a percolating path will be very small (of the order of pn, where n is the number of bonds in that particular path).  However, if L is large, then the number of possible percolating paths will also be extremely large.  So, even though, for any p less than one, the probability of a given path being a percolating path is very small, there are so many possible paths, that the probability of at least one of the paths being percolating can be close to one.  This happens when p is greater than a certain finite value (p*).[3]  Notice that the abrupt transition in the probability of finding a percolating path when p=p* is dependent on the existence of many paths running from the top to the bottom of the grid—that is, on the multiply-connected nature of the grid.

Before applying this insight to the problem of Eiruv, a couple of comments are in order:

1.  The qualitative behavior of Fig. 2, in which there is a percolation transition at a fractional value of p (p*) applies to many different systems, including different kinds of grids (not just square grids), different geometries and different ways of randomly “coloring” the elements of the grids.  It also applies to grids that are not regular, and which, themselves, may be random—for example, to grids composed of bonds that connect points that are randomly distributed in a plane.  The ubiquitousness of the percolation transition is an important feature in arguing for its applicability to the problem of Eiruv.

2.  The graph in Fig. 2 shows an abrupt increase in the probability for a percolating path at p*.  But even for p greater than p* (but less than one), the probability of a percolating path, while close to one, is not exactly one.  However, as L, the size of the grid, increases the rise in Fig. 2 at p* becomes more abrupt, and the probability for a percolating path for any p greater p* approaches one.  This behavior is indicated in Fig. 2 by the different colored, solid lines.  The sequence of line colors moving from blue to green to purple are associated with the probability of finding a percolating cluster, as a function of p, on increasingly larger grids (purple is largest, blue is the smallest).  In the limit that the grid is infinitely large (i.e. L becomes infinite), the curve in Fig. 2 becomes discontinuous, as indicated by the dashed vertical line, so that the probability of finding a percolating path is zero for p less than p* and is exactly one for p greater than p*.  This increasing abruptness of the percolation transition as the size of the system increases is a general feature of most percolation problems (See also footnote 3.)

In the coming weeks, we will continue Professor Savit’s article and discuss how the percolation transition can be used to create a theoretical Eiruv without building anything extra, as well as the Halachic challenges surrounding this concept.

[1] This is actually the classic bond percolation problem, since we are asking about the percolation of bonds that join the sites of a lattice.

[2] This value of p* is special to the square lattice.  As we shall discuss below, the precise value of p* depends on some of the details of the system.

[3]For the somewhat mathematically inclined, this argument can be made semi-quantitative as follows: If p<1 and if L>>b, then the probability of any one particular path being a percolating path will be very small, of the order of pn, where n is the number of bonds in that particular path.  However, the number of bonds in a given path scales with the size of the grid like L, so that, in terms of the grid size, L, the probability of any one path being percolating can be written as e-aL, where a is a positive number that depends on , and decreases as p increases.  On the other hand, if L is much larger than b, then the number of possible percolating paths is exponentially large—i.e. the number of possible paths grows with L like ~ecL, where c is some positive constant that depends on the geometry of the grid.  Roughly speaking, then, the probability of finding at least one percolating path is a function of the probability of any one path being percolating, times the number of such paths, that is, like e(c-a)L.  If a>c this will be approach zero as L gets large, but if c>a, this will get large as L gets large.  The value of p* is roughly determined by the condition c=a.  (Remember that a depends on p, and c depends on the nature of the grid).  The cognoscenti will recognize this as a typical energy-entropy argument in statistical mechanics.

Presumptive Eiruv and the Percolation Transition – Part 2 by Dr. Robert Savit

Which Parts of Israel Warrant Tearing Keri’ah Today by Rabbi Chaim Jachter