This augments these ideas.

I was thinking about a network topology in which a geodesic would be defined by a local property of routing directions. By geodesic I mean here a property of a path thru the network between two points. A geodesic path between two nodes is no longer than any other path. It occurred to me that counting the intersections of the lines shown here and described here as nodes fills the bill. I wrote that program under the hypothesis that certain routing instruction sequences (steering directions = SD) would only reach points already reached by shorter routes. Had this been false there would be areas in the picture not bounded by pentagons. Of course there are such areas but those seem to be only due to truncating the infinite recursion. There is a mathematical theory of automatic groups which covers these ideas but I have not understood that theory yet.

A path thru the network may be expressed by somehow identifying the starting node, an initial link (1 of 4) and then steering directions—a sequence of decisions to be taken at each subsequent node along the path. At each node there are three possible decisions we denote here as L, R and o. They denote turning left, right or proceeding directly onward. A string of letters, each from this set, constitute the body of the steering directions. It can be seen that a geodesic path always excludes certain subsequences such as “LL” or “RR” steering directions with such substrings can always be shortened by local transformations.

I think there is a converse theorem to the effect that operating on a sequence by such shortening transformations can transform any sequence to a geodesic between the same end nodes.

Efficacy of Network

But is this a good topology? One measure is how many nodes you can get to in n steps, for various n. One can get to cosh(bn) nodes for some constant b. I don’t know b but it is favorable. This means more crudely that you can connect an exponential number of nodes within a fixed radius with this scheme. Moreover it is a homogeneous network except at the boundary. There are torus like closures which make the boundary disappear but then I don’t know whether the geodesic properties remain.

This network is 2D but there are higher dimensional versions as well.

Network topologies should also allow routing around failures and congestion. This network does this but such routing complicates geodesic calculations.

Alas I think I can argue that there is a node thru which 1/2 of random connections go. This is probably a killer. You can go for higher genus hyperbolic spaces but then you are into homotopy theory to shorten the paths. Too, tiling multiply connected spaces is an unknown art.

Other issues

Is a source route from ‘origin’ the only name that a node needs? I think so but this is scary!

There are other space tilings but in only hyperbolic spaces do the reachable nodes grow exponentially with distance. Torus connections amount to tiling a flat space which is simple in some ways but connectivity is eventually inferior.


Unify names: “ source route”, “steering directions”, “”

Proofs of, or program corroboration of said theorems are needed.

Detailed rules for path shortening are needed.

Local algorithms for shortening are needed.


Thinking out loud about navigating in {5, 4}

Looking at the yield of the PostScript program suggests the idea of a water shed. Starting from the center node we wonder for which destinations we should begin by going north. For the first ambiguous destination, X, we can start north with path instructions “RoR”. Alternatively we can start west with the instructions “LoL” which also gets to X. On the geodesic (mathematical sense, not my sense) from the origin to X we go thru a regular series of borderline cases with paths such as “RoRLRoR”. You can get to the same place starting west with “LoLRLoL”. (Fortunately I can zoom my PostScript display program!) I think any geodesic to one of the destinations in this direction go thru the intervening ones. Automatic group theory might make this clear. This note gives hope.

Another sort of notation is to imagine a sequence of base 4 digits. One digit is consumed per link traversal. This can express a path that goes to a node and immediately returns over the same link. I will use codes {l, r, f, b} coded numerically as {1, 3, 2, 0}. This may arise during transformation of links and may otherwise be useful. I think the shortening rules amount to saying that if you find yourself immediately returning over a link, don’t go there in the first place. Any b in the path is removed by one of the rules:
lbl -> f; lbr -> b; lbf -> r; lbb -> l
rbl -> b; rbr -> f; rbf -> l; rbb -> r
fbl -> r; fbr -> l; fbf -> b; fbb -> f
bbl -> l; bbr -> r; bbf -> f; bbb -> b

This may be more concisely expressed in the numerical form (n, 0, m) -> (n+m) thus motivating the particular coding. The only other shortening rule is to say that when you find a path portion that traverses three sides of a pentagon, use the two other sides instead.
(m, 1, 1, n) -> (m−1, 3, n−1) and by reflection (m, 3, 3, n) -> (m+1, 1, n+1)

All arithmetic is modulo 4, of course. For canonicalization you may also want to say that when you go between the far vertices of two adjacent pentagons, pass to the right.
(m, 3, 2, 3, n) -> (m+1, 1, 2, 1, n+1)

With these rules the address of a node is the path from the origin, shortened as much as possible and canonicalized. The path may start with b but b may not appear elsewhere. I am close to being able to determine the coefficient of exponent in the exponential growth of the number of accessible nodes.

b and r generate the group. Geometrically r is a rotation of 72 degrees about the center of some pentagon and b is a rotation of 180 degrees about the midpoint of some edge of that pentagon. The group ‘presentation’ is thus:
b, r; b2, r5