Phase transition creates the geometry of the continuum from discrete space

Models of discrete space and space-time that exhibit continuum-like behavior at large lengths could have profound implications for physics. They may help tame the infinities arising from quantizing gravity, and remove the need for the machinery of the real numbers; a construct with no direct observational support. However, despite many attempts to build discrete space, researchers have failed to produce even the simplest geometries. Here we investigate graphs as the most elementary discrete models of two-dimensional space. We show that if space is discrete, it must be disordered, by proving that all planar lattice graphs exhibit a taxicab metric similar to square grids. We then give an explicit recipe for growing disordered discrete space by sampling a Boltzmann distribution of graphs at low temperature. Finally, we propose three conditions which any discrete model of Euclid's plane must meet: have a Hausdorff dimension of 2, support unique straight lines, and obey Pythagoras' theorem. Our model satisfies all three, resulting in a discrete model in which continuum-like behavior emerges at large lengths.

Figure 1

The geometry of the square grid graph. Two nodes $A$ and $B$ on the square grid graph are separated by 19 edges. There are many possible shortest paths (geodesics) of length 19 edges between the nodes, of which two are shown in black. The resemblance to the possible routes followed by yellow cabs in New York city inspired the term “taxicab metric” for the measure of distance on this graph [16].

Figure 2

Geodesic confinement is not found in planar lattice graphs but is in planar disordered graphs. (a) In a doubly-periodic triangulation (a modified snub square tiling), two nodes marked as circles are 22 edges apart. We call the set of all geodesics between them (shown in black) the geodesic bundle, containing a number of nodes proportional to the square of the geodesic length. (b) In a random triangulation, the geodesic bundle between two nodes 22 edges apart is confined to a narrow region. We call this phenomenon geodesic confinement. (c) A nonplanar doubly periodic graph (all nodes shown as circles) has neither a taxicab nor Euclidean metric.

Figure 3

Steinitz moves on a portion of a triangulation. The push move (left to right) consists of choosing a node $A$ and two opposite neighbors $P$ and $Q$ (or nearly opposite, if the degree of $A$ is odd). Node $A$ is divided into nodes $A^{\prime }$ and $B$. The pop move (right to left) consists of choosing a node $A^{\prime }$, and then one of its neighbors $B$, which are then merged to a single node $A$. In contrast to Ref. [20], which keeps track of triangular faces, we avoid tetrahedra and bottlenecks smaller than four edges, so faces can be assigned unambiguously, if desired. To ensure no tetrahedra are formed during a pop move, we make an additional check before the merger of $A^{\prime }$ and $B$: we require that no neighbor of $A^{\prime }$ that is not $P, Q$, or $B$ is connected to a neighbor of $B$ that is not $P, Q$, or $A^{\prime }$.

Figure 4

Growing graphs at high and low temperatures; the third column shows the main result of this article: a discrete model of Euclidean space. A small octahedral triangulation, with $N=6$ can be grown and equilibrated into larger graphs with $N=2^8, 2^{10}$, and $2^{12}$ nodes at (a) high temperature, (b) $T=0.5$ in the curvature model, or (c) low temperature in the walker model. The illustrative embedding into space shown here is irrelevant to our results; we are only interested in the graph.

Figure 5

Stereograms of graphs with 6144 nodes. Top two images: high temperature graph. Middle two images: curvature model at $T=0.5$. Bottom two images: walker model at low temperature. The nodes are coloured according to degree, as shown in the legend at the top of the figure. To view as stereograms, the figure should be held approximately 30 cm away, while looking through the page until the two images fuse.

Figure 6

Statistical tests for Euclidean behavior of our graphs. Top row: The mean node eccentricity $H$ and standard deviation for example points, divided by $N^{1/2}$, where $N$ is the number of nodes. (a) The curvature model with $T=0.5$ (black), $2^0, 2^2, 2^4, 2^6$ (gray), and ${10}^5$ (dashed). (b) The walker model, with $T=2^{-3}$ (black), $2^2, 2^3, 2^4$,..., $2^8$ (gray), and ${10}^5$ (dashed). Middle row: (c) The number of nodes $N_{\mathrm{geo}}$ in geodesic bundles of different lengths $\lambda$ on a low-temperature walker model graph with $N=2^{15}$ nodes. (d) Fitted values for $\gamma$, where $N_{\mathrm{geo}}\propto N^{\gamma }$ for graphs of different $N$. Bottom row: $R$ is the ratio of the perpendicular length to the edge side of an equilateral triangle drawn on a low-temperature walker model with $N=2^{15}$ nodes. $R_{\mathrm{sph}}$ is the exact equivalent on a smooth sphere [Eq. (5)]. (e) $R$ plotted against $R_{\mathrm{sph}}-\sqrt{3}$ (we show a random sample of 250 from the full set of 6078 points). The line is a linear regression and we extract the intercept as a graph-theoretic estimate of $\sqrt{3}$. (f) Estimates of $\sqrt{3}$ by this method for graphs of different size $N$. The dashed gray horizontal line is the exact value.

Figure 7

Equilateral triangles on the plane and on a graph. (a) An equilateral triangle drawn on the Euclidean plane with straightedge and compass, where $M$ is halfway between $A$ and $B$, and $MC/AM=\sqrt{3}$. (b) The same construction using geodesics on a low-temperature “walker model” graph (which approximates a smooth sphere) with $N=2^{16}$ nodes and triangle side length of 32.

Figure 8

All doubly periodic planar graphs have a taxicab metric on long length scales. (a)–(d) A grid of unit cells forms a doubly periodic planar graph; nodes within the unit cells not shown. For some node type $p$, if $p_0{p}_1$ is a shortest path between nodes separated by $\mathbf{v}=(m,n)$ unit cells, then $p_0{p}_1...p_k$ is the shortest path between nodes separated by $k\mathbf{v}$ unit cells. (e),(f) For $m$ and $n$ relatively prime, the geodesic ${\mathcal{G}}_{pp}\left(k\mathbf{v}\right)$ is the concatenation of $k-1$ copies of both ${\mathcal{G}}_{qq}\left(\mathbf{u}\right)$ and ${\mathcal{G}}_{qq}\left({\mathbf{u}}^{\prime }\right)$, with tails at either end. See the text for details.