Imagine a digital universe where points in space are vertices in a graph, and the distance between two points is the length of a shortest path between them. Can the graph be structured whereby macroscopic observers living in the universe perceive isotropic space, as we perceive in our universe?
The distance \(d_G(u, v)\) between vertices in an undirected graph \(G = (V, E)\) is the number of edges in a shortest path between \(u\) and \(v\). The distance \(d_2(u, v)\) between points on the Euclidean plane is the \(2\)-norm of the line segment between \(u\) and \(v\). Non-degenerate \(V \subset \mathbb{N}^2\) cannot satisfy \(d_G = d_2\) because of the incommensurability of the side and the diagonal of a square. Nonetheless, \(d_G\) can be used to approximate \(d_2\); the approximation will be better or worse as a function of \(G\). How well can \(d_G\) approximate \(d_2\), as \(|V|\) grows?
This question is difficult to answer in full generality. Let's consider the special case of a graph whose vertices are the square grid \(\{1, \ldots, n\} \times \{1, \ldots, n\}\). If we add edges between horizontal and vertical neighbors, we get \(d_1\) taxicab distances, based on the \(1\)-norm. If we additionally add edges between diagonal neighbors, then we get \(d_\infty\) chessboard distances, based on the \(\infty\)-norm.
We have the nice property that \(d_1 \leq d_2 \leq d_\infty\), although neither one of
these constructs gives us a very good approximation of \(d_2\). It is easy to see that in
both cases, the divergences from \(d_2\) grow unboundedly with \(n\). In fact,
Fritz
Certain formal properties of Eugrids are worth calling out at this point to avoid confusion. All order-\(n\) Eugrids share the same square grid of vertices depicted above. Edges corresponding to line segments of unit length are present in all Eugrids. Eugrids vary in the presence or absence of edges corresponding to line segments of length \(\sqrt{2}\). Edges corresponding to line segements of other lengths never appear.
It is notationally convenient
Let us consider for the moment only distances from the corner vertex \(\mathbf{1} := (1, 1)\) to other points. This lets us ignore the antidiagonals, which do not affect distances between \(\mathbf{1}\) and other points, simplifying notation, discussion, and visualization.
A very simple way to interpolate between taxicab and chessboard distances is to decide on the presence or absence of each diagonal edge by sampling a random variate from a Bernoulli distribution. We can visualize this interpolation by drawing “circular arcs” of radius \(n\) where the pixel at \(x, y\) is black iff \(d_G(\mathbf{1}, (x, y)) \le r\).
This initially seems promising. If we drill down a bit we find that the best
fit
If we inspect this result carefully however, we notice a problem.
The arc in the figure on the left above looks decently circular away from the axes, but
near the axes themselves there are straight lines, corresponding to a rather high degree
of anisotropy. As the figure on the right above shows, this anisotropy does not diminish
as the measurement scale increases
This informal analysis suffices to demonstrate that Eugrids based on random Bernoulli variates are poor models of the Euclidean plane. It is nonetheles encouraging to see that such a simple procedure can yield reasonably circular arcs, at least away from the axes.
In order to devise better heuristics we must take a look at Eugrid microstructure. Let
\((x_v, y_v)\) be the Cartesian coordinates of vertex \(v\). Assuming \(x_u \leq x_v\) and
\(y_u \leq x_v\),
A simple greedy approach to constructing Eugrids is to visit each potential diagonal at
\(v\) exactly once
\(\mathbf{1}\)-growth is a completely deterministic procedure, but the graph structure that it produces is aperiodic, so Fritz's no-go theorem does not apply; arcs around \(\mathbf{1}\) become increasingly circular as the radius increases.
This demonstrates that the Eugrid representation can give us a very nice model of the Euclidean plane, with minimal anisotropy, at least from a single perspective. The moment we shift our perspective however, things begin to seem rather worse.
Even worse than in the case of Bernoulli random variates, we see severe anisotropy around the axes; back to the drawing board!
How can we make better Eugrids? We can generalize the \(\mathbf{1}\)-growth heuristic and consider losses from more vertices than just \(\mathbf{1}\). What is left is to specify which vertices, and how to weight their relative contributions, since adding a particular diagonal edge may make some distances more Euclidean, and other less so.
For the diagonal at \(v\), we can potentially calculate losses from all vertices \(u\) such that \(x_u \leq x_v\) and \(y_u \leq y_v\). But since this both highly redundant and scales badly with \(n\), we restrict ourselves to vertices along the left and upper edges of the Eugrid, i.e. $$\Gamma_v := \{u \mid x_u \leq x_v \land y_u \leq y_v \land \min(x_u, y_u) = 1\}.$$ We refer to this approach as the \(\Gamma\)-growth heuristic, and the resulting graphs as \(\Gamma\)-Eugrids.
This gives us nice coverage and is computationally tractable, but requires careful normalization to balance relative contributions. In particular, we include two factors.
The first factor weights the contribution of vertex \(u\) by the angle \(\theta^u_v\ :=
\widehat{abc}\), where \(b := v + \mathbf{1}\) and \(a\) and \(c\) are the midpoints
between \(u\) and its two adjacent points in \(\Gamma_v\)
The second factor mitigates against axis-parallel anisotropy by assigning greater importance to vertex \(u\) when the line between \(u\) and \(v\) is closer to axis-parallel, and is defined as
$$\alpha^u_v := \frac{\max{(x_v - x_u, y_v - y_u}) + 1}{\min{(x_v - x_u, y_v - y_u)} + 1}_.$$
Putting it all together, we have
$$L^\Gamma_i(v) := \sum_{u_\in \Gamma_v}{\theta^u_v \cdot \alpha^u_v \cdot L^u_i(v)}.$$
As with the \(\mathbf{1}\)-growth heuristic, the graph produced by \(\Gamma\)-growth is deterministically generated yet aperiodic. It has a rather more complex structure, however, reminiscent of the patterns produced by well-known cellular automata.
This approach gives us fairly circular arcs around \(\mathbf{1}\), with minimal anisotropy.
Furthermore, we obtain reasonable-looking results even when we shift our perspective.
So far we have only considered the determination of the diagonal edges, corresponding to
line segments paralleling \(x=y\). We must also specify how the antidiagonals edges,
paralleling \(x=-y\), are determined. There are various possibilities that one could try,
but perhaps the simplest, and the one chosen here, is to simply flip the diagonals (in
their bit matrix representation) along the first axis. That is to say, an antidiagonal
edge exists between the vertices \((x+1, y)\) and \((x, y+1)\) iff a diagonal
edge exists between the vertices \((n - x, y)\) and \((n - x +1, y+1)\).
is replaced by
.
Now we can at last make lovely circles, like so:
At this point you might be getting a bit uncomfortable with developing and evaluating a discrete model of the Euclidean plane by comparing pictures of vaguely circular blobs. Fortunately, these sorts of models are well-suited to quantitative analysis, which we will turn to in the next section.
Farr and Fink
As defined by
For comparing Eugrids of different orders \(n\) we will consider the distribution of $$H_G(v) := \frac{\epsilon_G(v) - \epsilon_2(v)}{\sqrt{n}}_.$$ In particular, we will wish to demonstrate that \(E[H_G]\) and \(SD[H_G]\) both converge to zero as \(n\) increases. The choice of \(\sqrt{n}\) as the denominator is admittedly debatable and somewhat subjective. The argument is that we are willing to address a certain degree of discrepancy by simply constructing a larger graph, but not impractically so.
Here, and in the subsequent experiments with random Eugrids, \(p\) is selected using Brent's method to minimize the square of the mean of \(H_G\). Nonetheless the standard deviation diverges, and we can see that random Eugrids fail the Hausdorff dimension test.
\(\Gamma\)-Eugrids show a small bias upwards (i.e. graph eccentricity tends to be greater that Euclidean eccentricity), but on the whole do quite well here.
The number of vertices \(N_{geo}\) in the geodesics (shortest paths) between vertices can
be easily seen to grow quadratically as a function of distance for graphs corresponding
to taxicab and chessboard distances; i.e.
$$N_{geo}(u, v) \propto d_G(u, v)^2.$$
Farr and Fink
Random and \(\Gamma\)-Eugrids both attain geodesic confinement.
If ABC is an equilateral triangle with mid-point M halfway between A and B, then \(d_2(M, C) / d_2(A, B) = \sqrt{3} / 2\). We can test this empirically by investigating $$T_G(u, v, w, m) := d_G(m, w) / d_G(u, v) - \sqrt{3} / 2$$ for random equidistant vertices \(u, v, w\) where \(m\) is a vertex midway between \(u\) and \(v\). As with \(H_G\), we would like to see \(E[T_G]\) and \(SD[T_G]\) both converge to zero as \(n\) increases.
Random Eugrids appear to pass the Pythagorean theorem test.
\(\Gamma\)-Eugrids are even better, with the standard deviation dropping down quite rapidly as the graph size increases.
We propose a novel fourth test, specifically for Eugrids. We consider the distribution of \(A_G(u, v, w, m)\) which is calculated using the same formula as \(T_G\) but with a different sampling distribution over vertices. Specifically, we constrain the sampling of \(v\) conditional on \(u\) to satisfy \(x_v = x_u \lor y_v = y_u\). In other words, \(u\) must be reachable from \(v\) by moving in one of the four cardinal directions.
As above, we would like to see \(E[A_G]\) and \(SD[A_G]\) both converge to zero as \(n\) increases.
\(E[A_G]\) for random Eugrids converges to zero, but \(SD[A_G]\) does not.
\(\Gamma\)-Eugrids demonstrate axis anisotropy that decreases as the size of the graph grows.
I was showing my son how to make a glider
in Conway's Game of
Life, and mentioned in passing that gliders could only move in four different
directions
The most readily apparent discrepancy between our observations and the cellular style of
computation is of course isotropy; a secondary discrepancy is the apparent randomness
I would say that I got pretty far, all things considered, but not all the way. In terms
of the empirical results, geodesic confinement is certainly the weakest point; I failed
to make any substantive headway here without abandoning both
unweighted graph distance, and strict determinism. I am also disappointed on the
theoretical side by my failure to make progress towards characterizing the emergence of
approximately Euclidean space from lower-level processes,
as
On the positive side, the approach is quite nice computationally
Why do \(\Gamma\)-Eugrids not attain better geodesic confinement? Recall that the
diagonals are aperiodic; the negative results of
Thus far we have assumed an unweighted graph, where the diagonal edge length equals the length of horizontal and vertical edges. Let's try something else:
This approach works, but can be fairly characterized as a hack. By construction, the only test metric affected by infinitesimally disordered distances is geodesic confinement.
The estimated values of \(\gamma\) are actually less than one, because geodesics are more confined over longer distances. As the mean distance between vertices increases, the estimate approaches one.
Thanks to Dr. Robert Farr for his feedback and for sharing his code with me. Thanks to Dr. Adam Earle for suggesting the illustration of small circular arcs.