Precious Metal Sequences and Sierpiński-Type Graphs

Andreas M. Hinz^{1} Department of Mathematics Ludwig-Maximilians-Universität München Theresienstraße 39 80333 Munich Germany

                         hinz@math.lmu.de

Paul K. Stockmeyer Department of Computer Science The College of William & Mary P.O. Box 8795 Williamsburg, VA 23187-8795 USA

                       pkstockmeyer@cox.net

Abstract

Sierpiński graphs S_{p}^{n} and Sierpiński triangle graphs Ŝ_{p}^{n} form two-parametric families of connected simple graphs which are related, for p = 3, to the Tower of Hanoi with n discs and for n → ∞ to the Sierpiński triangle fractal. The vertices of minimal degree play a special role as extreme vertices in S_{p}^{n} and primitive vertices in Ŝ_{p}^{n}. The key concept of this note is that of an m-key vertex whose distance to one of the extreme or primitive vertices, respectively, is m times the distance to another one. The number of such vertices and the distances occurring lead to integer sequences with respect to parameter n like, e.g., the Fibonacci sequence (golden) for p = 3 and the Pell sequence (silver) for p = 4. The elements of most of these sequences form self-generating sets. We discuss the cases m = 1, 2, 3, 4 in detail.

1Corresponding author.

1 Introduction

The vertices of Sierpiński graph S_{p}^{n} with base p ∈ ℕ, p ≥ 2, and exponent n ∈ ℕ_{0} are ntuples of the set P := [p]_{0} := {0, …, p − 1} and written as s = s_{n} … s_{1} with s_{d} ∈ P for d ∈ [n] := {1, …, n}. The edge set is given by

E(S_{p}^{n}) = \{\{\underline{s}ij^{d−1}, \underline{s}ji^{d−1}\} | \{i, j\} ∈ \binom{P}{2}, d ∈ [n], \underline{s} = s_{n} … s_{d+1} ∈ P^{n−d}\} .  (1)

Note that S_{p}^{0} = ({ϵ}, ∅) ≅ K_{1} with the empty word ϵ, S_{p}^{1} ≅ K_{p} and that S_{2}^{n} is a path on 2^{n} vertices. Sierpiński graphs were introduced in the 1990s as mathematical models for the famous Tower of Hanoi (p = 3) and the Chinese Rings (p = 2); see [?, Chapter 4]. In the past two decades they developed a life on their own as can be seen in a recent survey [?]. Apart from many graph parameters determined, metric properties have been investigated, and the graphs S_{3}^{n} were used to approximate the fractal structure of the Sierpiński triangle (see [?]).

If we concatenate s_{n+1} = k ∈ P to the left of all vertices of S_{p}^{n} we get what we may call the graph kS_{p}^{n} ≅ S_{p}^{n} as a subgraph of S_{p}^{1+n}. These p copies of S_{p}^{n} are mutually linked in S_{p}^{1+n} by the so-called critical edges \{ij^{n}, ji^{n}\}, \{i, j\} ∈ \binom{P}{2}, according to (1). This shows that Sierpiński graphs S_{p}^{n} are connected and therefore endowed with the canonical distance function δ where δ(s, t) is the length of a shortest s, t-path in S_{p}^{n}. The importance of the critical edges lies in the fact that for p ≥ 3 a shortest i\overline{s}, j\overline{t}-path may either run through critical edge {ij^{n}, ji^{n}} (direct path) or via two critical edges, namely {ik^{n}, ki^{n}} and {kj^{n}, jk^{n}} for some (but only one) k ∈ P \ {i, j} (indirect path). The decision whether the direct or an indirect path is shortest (or both are) and for which k, is not easy and has been analyzed and solved with an algorithm by Hinz and Holz auf der Heide [?]. The decisive ingredient is the distance δ(s, j^{n}) of an arbitrary vertex s ∈ P^{n} to a so-called extreme vertex j^{n} in S_{p}^{n}. It is given (see [?, Theorem 4.5]) by the formula

∀ s ∈ P^{n} ∀ j ∈ P : δ(s, j^{n}) = ∑_{d=1}^{n}(s_{d} ≠ j) · 2^{d−1},  (2)

where we make use of the Iverson bracket (or Iverson convention) which assigns a numerical (binary) value (A) to a statement A; it is defined by (A) = 1, if A is true, and (A) = 0, if A is false. Obviously, δ(s, j^{n}) ≤ 2^{n} − 1 and putting s = i^{n} for some i ∈ P \ {j} we have diam(S_{p}^{n}) = δ(i^{n}, j^{n}) = 2^{n} − 1. Another immediate consequence of (2) is the following invariant:

∀ s ∈ P^{n} : ∑_{j=0}^{p−1} δ(s, j^{n}) = (p − 1) · (2^{n} − 1).  (3)

Sierpiński graphs S_{3}^{n} are isomorphic to Hanoi graphs H_{3}^{n}; see [?, pp. 177ff]. For these, the number of 2-key vertices with δ(s, 2^{n}) = 2 · δ(s, 0^{n}) has been found to be Fibonacci number F_{n−1} in [?, Theorem 3.1]. Here, for n ≥ 3, the 2-key distances δ(s, 0^{n}) have the form 2β + 2^{n−2} + 1 with β running through the set of (n − 3)-bit numbers without consecutive 0s; see [?, Lemma 3.2]. The fact that all 2-key distances are odd follows also from the observation from (2) that exactly one of the distances δ(s, j^{n}) is even, namely for j = s_{1} in S_{3}^{n} and for j = s_{n} ◁⋯ ◁s_{1} in H_{3}^{n}, where the operation given by i ◁k = i+(3−2i−k)(i ≠ k) for i, k ∈ {0, 1, 2} has to be evaluated from the right; see [?, (2.8)].

In the present note we want to extend these results in three ways. We will consider Sierpiński graphs of any base p ≥ 2 (Section 2), thereby looking at m-key vertices, i.e., those s ∈ P^{n} for which δ(s, (p − 1)^{n}) = m · δ(s, 0^{n}) and their respective m-key distances for m = 1 (Section 2.1), m = 2 (Section 2.2), m = 3 (Section 2.3), and m = 4 (Section 2.4). Finally, we will consider the corresponding questions for Sierpiński triangle graphs Ŝ_{p}^{n} (Section 3). These are graphs which have often been mistaken for Sierpiński graphs and even been called so (see [?] for a discussion), but whose metric properties are somewhat more difficult to access (see [?]). Our focus will be on integer sequences emerging from these considerations. Some of the sequences come from the so-called self-generating sets, like, e.g., the Mersenne sequence M_{n} = 2^{n} − 1 (\underline{A000225}, referring to the On-Line Encyclopedia of Integer Sequences (OEIS)) with α = 1 and F = {k ↦ 2k + 1} in the following lemma.

Lemma 1. Let α ∈ ℕ and F be a finite set of functions from ℕ to ℕ with

∀ f ∈ F ∀ x ∈ ℕ : f(x) > x.  (4)

We say that Γ ⊂ ℕ fulfills property SG(α, F), iff {α} ∪ ⋃{f(Γ) | f ∈ F} ⊂ Γ. Then the following are equivalent:

1. ℕ ⊃ C = {α} ∪ ⋃{f(C) | f ∈ F},

2. C = {c_{k} ∘ ⋯ ∘ c_{1}(α) | c_{ℓ} ∈ F, ℓ ∈ [k], k ∈ ℕ_{0}},

3. C = ⋂{Γ ⊂ ℕ | Γ fulfills SG(α, F)},

4. C is the smallest subset of ℕ (w.r.t. “⊂”) that fulfills SG(α, F). Such a C is called a self-generating set, α is its seed and F is its generating function set. Points 2 to 4 guarantee that C is defined uniquely by 1.

Proof. 1. ⇒ 2. Let ℕ ⊃ C = {α} ∪ ⋃{f(C) | f ∈ F} and define C′ := ⋃{C_{k} | k ∈ ℕ_{0}} with C_{k} := {c_{k} ∘ ⋯ ∘ c_{1}(α) | c_{ℓ} ∈ F, ℓ ∈ [k]}. We prove C_{k} ⊂ C by induction on k. C_{0} = {α} ⊂ C. If x = c_{k+1} ∘ c_{k} ∘ ⋯ ∘ c_{1}(α) ∈ C_{k+1}, then x = f(x′) with f = c_{k+1} ∈ F, x′ = c_{k} ∘⋯∘c_{1}(α) ∈ C_{k} ⊂ C, the latter by induction assumption. Therefore, x ∈ f(C) ⊂ C.

For C ⊂ C′, we apply the Algorithm to x ∈ C. The condition in the while loop can be checked because F is finite and x′ must be smaller than x by virtue of (4). The algorithm terminates because x is getting strictly smaller in each iteration of the while loop. The output of c = c_{k} … c_{1} then provides the representation of x as an element of C′, i.e., x = c_{k} ∘ ⋯ ∘ c_{1}(α).

2. ⇒ 3. Let C = {c_{k} ∘ ⋯ ∘ c_{1}(α) | c_{ℓ} ∈ F, ℓ ∈ [k], k ∈ ℕ_{0}} and C′ = ⋂{Γ ⊂ ℕ | Γ fulfills SG(α, F)}. For every Γ ⊂ ℕ which fulfills SG(α, F) we can prove C_{k} ⊂ Γ by induction as before. So C_{k} ⊂ C′ and consequently C ⊂ C′. Obviously, C fulfills SG(α, F), so that C′ ⊂ C.

Algorithm Procedure C ⊂ C′ Parameter x: element of C Parameter c: string of elements of F

input x

c ← ϵ (empty word)

while ∃ f ∈ F ∃ x′ ∈ C : x = f(x′)

x ← x′, c ← cf end while output c

3. ⇒ 4. C = ⋂{Γ ⊂ ℕ | Γ fulfills SG(α, F)} fulfills SG(α, F). If Γ ⊂ ℕ fulfills SG(α, F), then C ⊂ Γ.

4. ⇒ 1. Let C be the smallest subset of ℕ that fulfills SG(α, F) and assume that x ∈ C \ ({α} ∪ ⋃{f(C) | f ∈ F}). Let C′ := C \ {x}. Then α ∈ C′ and if f ∈ F and x′ ∈ C′, then f(x′) ≠ x, i.e., f(x′) ∈ C′. So C′ fulfills SG(α, F), but is smaller than C, a contradiction.

2 Sierpiński graphs

For p ∈ ℕ, p ≥ 2, and n ∈ ℕ_{0} we define Sierpiński graph S_{p}^{n} with V (S_{p}^{n}) = P^{n} and edge set as in (1). Let m ∈ ℕ. An m-key vertex in S_{p}^{n} is an s ∈ P^{n} with δ(s, (p − 1)^{n}) = m · δ(s, 0^{n}). If s is an m-key vertex, the value δ(s, 0^{n}) is called an m-key distance. If there is no doubt about the m we just write “key vertex (distance)”. The set of m-key vertices in S_{p}^{n} is denoted by _{m}Ψ_{p,n}, occasionally without the indices m or p. A special case is n = 0, where the only vertex ϵ is a key vertex for every m, i.e., _{m}Ψ_{p,0} = {ϵ}, and 0 is the only key distance. For n ∈ ℕ, key distances are always positive.

In the discussion of the case p = 2, Mersenne numbers M_{n} = 2^{n} − 1 play a central role. The following is probably well-known:

Lemma 2. Every odd k > 1 divides some M_{κ} with ⌈ln(k + 1)/ ln(2)⌉ ≤ κ < k. In particular, every odd number is a proper divisor of some Mersenne number.

Proof. It suffices to prove the first statement because Mersenne number M_{κ} is a proper divisor of M_{2κ} = (2^{κ} + 1)M_{κ} for κ ∈ ℕ.

The set of residues modulo k of powers of 2 has size at most k − 1 because k > 1 is odd and therefore the remainder 0 is impossible. So by the pigeonhole principle there must be 0 ≤ i < j ≤ k − 1 such that \frac{2^{j}}{k} − \frac{2^{i}}{k} ∈ ℕ, whence k | 2^{i}(2^{j−i} − 1). Again because k is odd we get k | 2^{κ} − 1 with 1 ≤ κ := j − i ≤ k − 1.

As we have seen before, S_{2}^{n}, n ∈ ℕ, is a path graph on 2^{n} vertices which can be labeled by binary strings s ∈ {0, 1}^{n}, leading from 0^{n} to 1^{n} in natural order of their values as binary numbers. An m-key vertex s must therefore satisfy (m+1)δ = M_{n}, where the m-key distance δ is δ(s, 0^{n}) = (s)_{2} and must be odd. We get

1 ≤ δ = \frac{M_{n}}{m + 1} ≤ \frac{M_{n}}{2} , n ≥ 2.

So we find m-key vertices if and only if m + 1 > 1 is a divisor of M_{n} and δ is a proper divisor of M_{n}. From Lemma 2 we see that there are m-key vertices iff m is even and that every odd δ is a key distance. We call δ = 1 trivial, which leads to an (M_{n} − 1)-key distance with trivial key vertex 0^{n−1}1. Note that

M_{n} is prime if and only if no non-trivial key vertex exists in S_{2}^{n}.

So for odd m and n ∈ ℕ we have _{m}Ψ_{2,n} = ∅. For m = 2 we get _{2}Ψ_{2,n} = {(01)^{n/2}}, if n is even and_{2}Ψ_{2,n} = ∅, if n is odd. This reflects the famous formula M_{n} mod 3 = n mod 2 (cf. [?, p. 100]). For n = 2ν, ν ∈ ℕ, the (positive) 2-key distances form the sequence \underline{A002450} of odd Lichtenberg numbers ℓ_{2ν−1} = \frac{1}{3}(2^{2ν} − 1) = δ ((01)^{ν}, 0^{2ν}). (For the Lichtenberg sequence (\underline{A000975}), see [?] and [?]). For m = 4 we note that 5 | M_{n} ⇔ 4 | n, as can be seen by looking at the residues modulo 5 of powers of 2, so that there are 4-key vertices if and only if n = 4ν, ν ∈ ℕ_{0}, namely _{4}Ψ_{2,4ν} = {(0011)^{ν}}. The sequence of 4-key distances is \underline{A182512}(ν) = \frac{1}{5}(2^{4ν} − 1) = 0, 3, 51, 819, 13107, ….

2.1 The case m = 1

As a warm-up for general p we ask whether for some key vertices s ∈ P^{n}, n ∈ ℕ, the distances to two extreme vertices, 0^{n} and (p − 1)^{n} say, are equal. From (3) we see that this cannot happen for p = 2. For p ≥ 3 we have from (2):

δ(s, (p − 1)^{n}) = δ(s, 0^{n}) ⇔ ∑_{d=1}^{n}(s_{d} ≠ p − 1) · 2^{d−1} = ∑_{d=1}^{n}(s_{d} ≠ 0) · 2^{d−1}
⇔ ∀ d ∈ [n] : s_{d} ≠ p − 1 ⇔ s_{d} ≠ 0
⇔ ∀ d ∈ [n] : s_{d} ∈ [p − 2]
⇔ s ∈ [p − 2]^{n}.

Theorem 3. For p ∈ ℕ, p ≥ 2, and n ∈ ℕ_{0} we have _{1}Ψ_{p,n} = [p − 2]^{n}.

So there are (p − 2)^{n} key vertices and the corresponding key distance δ(s, 0^{n}) is always 2^{n} − 1. In particular, for p = 3 there is only one key vertex at distance 2^{n} − 1 from both 0^{n} and 2^{n}, namely extreme vertex 1^{n}.

2.2 The case m = 2

The Fibonacci sequence turns up in |_{2}Ψ_{3,n}| = F_{n−1}, which is also the number of 2-key distances occurring for S_{p}^{n}; see Proposition 6 below. (This is formally compatible for n = 0, if we put F_{−1} = 1.) In order to generalize this result we define F_{q,n} for q, n ∈ ℕ_{0} by

F_{q,0} = 0,  (5)
F_{q,1} = 1,  (6)
F_{q,n+2} = q · F_{q,n+1} + F_{q,n}.  (7)

(F_{q} is the Lucas sequence of the first kind U(P, Q) for the parameters P = q and Q = −1; see [?, formula (10)]. The numbers F_{q,n} are sometimes called q-Fibonacci numbers, as, e.g., in [?].) Again, for formal reasons, we put F_{q,−1} = 1, compatible with (5), (6), and (7) for n = −1. Special cases are

F_{0,n} = n mod 2,
F_{1,n} = F_{n},
F_{2,n} = P_{n},

where F_{n} are the Fibonacci numbers (\underline{A000045}) and P_{n} are the Pell numbers (\underline{A000129}), respectively. Let Q_{±} := \frac{1}{2} (q ± \sqrt{4 + q^{2}}); then

F_{q,n} = \frac{1}{\sqrt{4 + q^{2}}} ((F_{q,1} − Q_{−}F_{q,0})Q_{+}^{n} − (F_{q,1} − Q_{+}F_{q,0})Q_{−}^{n})  (8)
= \frac{Q_{+}^{n} − Q_{−}^{n}}{Q_{+} − Q_{−}}

is the solution of (7), the latter if (5) and (6) are fulfilled. For q ∈ ℕ the ratios F_{q,n+1}/F_{q,n} tend to Q_{+} as n → ∞. These irrational numbers have recently been called metallic means; see, e.g., [?, p. 2]. Since this expression is used inconsistently in literature, we prefer to refer to them as precious metal means as, e.g., the golden (q = 1, Q_{+} = \frac{1}{2} (1 + \sqrt{5})), silver (q = 2, Q_{+} = 1 + \sqrt{2}) and bronze (q = 3, Q_{+} = \frac{1}{2} (3 + \sqrt{13})) ratio. They have the constant infinite continued fraction representation [q; \overline{q}].

Our first main result now reads

Theorem 4. For p ∈ ℕ, p ≥ 2, and n ∈ ℕ_{0} we have |_{2}Ψ_{p,n}| = F_{p−2,n−1}.

Proof. Let \overline{s} = s_{n} … s_{1} ∈ P^{n} and s = s_{n+1}\overline{s} ∈ Ψ_{n+1}. Then s_{n+1} = 0, because (p − 1)^{n+1} is the closest extreme vertex to vertex (p − 1)\overline{s} in S_{p}^{n+1} and if s_{n+1} ∈ [p − 2], then

δ(s, (p − 1)^{n+1}) = δ(\overline{s}, (p − 1)^{n}) + 2^{n} < 2^{n+1}

and

δ(s, 0^{n+1}) = δ(\overline{s}, 0^{n}) + 2^{n} ≥ 2^{n}.

Let Φ_{n} := {s ∈ P^{n} | 2^{n} + δ(s, (p − 1)^{n}) = 2 · δ(s, 0^{n})}, i.e., Ψ_{n+1} = 0Φ_{n}. We show that |Φ_{n}| fulfills the recurrence (5), (6), (7) for q = p − 2. If s ∈ Φ_{0}, then 1 = 0, whence |Φ_{0}| = 0, i.e., (5) holds. So let n ∈ ℕ. Then

s ∈ Φ_{n} ⇔ 2^{n} + ∑_{d=1}^{n}(s_{d} ≠ p − 1) · 2^{d−1} = 2 · ∑_{d=1}^{n}(s_{d} ≠ 0) · 2^{d−1}

⇔ 2^{n} + ∑_{d=1}^{n−1}(s_{d+1} ≠ p − 1) · 2^{d} + (s_{1} ≠ p − 1) = (s_{n} ≠ 0) · 2^{n} + ∑_{d=1}^{n−1}(s_{d} ≠ 0) · 2^{d}
⇔ s_{1} = p − 1, ∀ d ∈ [n − 1] : s_{d} = 0 ⇔ s_{d+1} = p − 1, s_{n} ≠ 0.  (9)

For n = 1 we have s ∈ Φ_{1} iff s = p − 1, so |Φ_{1}| = 1, i.e., (6) is satisfied. Together with (9) (cf. also the standard drawings of S_{p}^{n}, e.g., in [?, Chapter 4]) we can deduce

∀ n ∈ ℕ_{0} : Φ_{n+2} = [p − 2]Φ_{n+1} ˙∪ (p − 1)0Φ_{n}.

Therefore |Φ_{n}| also satisfies (7) for q = p − 2.

Remark 5. 1. 2-key vertices s lie at \frac{2}{3} = (0.\overline{10} )_{2} on the only optimal path from (p − 1)^{n} to 0^{n} which passes s.

2. For p = 2 it follows immediately from (9) that Ψ_{n} = ∅, if n is odd, and that otherwise s = (01)^{n/2} is the only element of Ψ_{n}, as we have seen before.

Sierpiński graph S_{2}^{n} and R^{n}, the state graph of the Chinese Rings (see [?, Chapter 2]), being isomorphic, we see that if the number of rings is odd, there is no state at \frac{2}{3} distance between the extreme states 0^{n} and 10^{n−1}, while for an even positive number of rings there is exactly one, which is the state 1^{n}.

The approach taken in [?] was slightly different. We looked at the binary representation of the key distance δ(s, 0^{n+1}) and observed [?, Lemma 3.2(2)] that the last bit is 1 and that the representation does not contain a square 00 [?, Lemma 3.2(3)] (this would, e.g., contradict the distance formula (2), because there would be a 0 at the same place in the binary representations of δ(s, 0^{n+1}) and δ(s, (p − 1)^{n+1}); for p = 2 there are no squares 11 either because there are only two types of bits). Conversely, every binary number with these properties represents some δ(s, 0^{n+1}). To achieve this, one can construct a bijection between P^{n} and the set of those binary matrices b = (b_{j,d−1})_{j∈P,d∈[n]} ∈ {0, 1}^{p×n} which satisfies

∀ d ∈ [n] : ∑_{i=0}^{p−1} b_{i,d−1} = p − 1;  (10)

in fact, b_{j,d−1} = (s_{d} ≠ j) for s ∈ P^{n}. This can be based on the fact that the set of those binary matrices which satisfy (10) has size p^{n} (as can easily be seen by induction on n).

Note that this bijection shows that p − 1 rows of the matrix suffice to recover s, because the missing row can be reconstructed by virtue of (10). Moreover, from this representation one can immediately deduce [?, Corollary 4.7].

Let us add our observations that s_{n+1} = 0 for key vertices s = s_{n+1}\overline{s} in S_{p}^{n+1} [?, Lemma 3.2(1)] and that therefore the first and last bits of δ(\overline{s}, 0^{n}) are 1. The quest for key distances in S_{p}^{n+1} can then be reduced, for p ≥ 3, to the problem of finding, for n ≥ 2, the value of |B_{n−2}| for the sets B_{ℓ} defined as the sets of bit strings of length ℓ ∈ ℕ_{0} which do not contain the substring 00. A counting like this can be found in [?, Section 1.2]. Quite obviously, B_{0} just contains the empty word, and B_{1} = {0, 1}. As before, we get

B_{ℓ+2} = {1t | t ∈ B_{ℓ+1}} ˙∪ {01t | t ∈ B_{ℓ}},

whence |B_{ℓ}| = F_{ℓ+2}.

The elements of the union of the B_{ℓ}, ℓ ∈ ℕ, considered as decimal numbers, form the sequence a given by

a_{0} = 0, ∀ n ∈ ℕ, n ≥ 2 ∀k ∈ [F_{n}]_{0} : a_{F_{n+1}−1+k} = a_{F_{n−1}−1+k} + 2^{n−2};

this is, apart from the offset, the sequence \underline{A003754} of the OEIS, i.e., a_{n} = \underline{A003754}(n + 1) for n ∈ ℕ_{0}.

The distances occurring in C_{n} := {δ(s, 0^{n}) | s ∈ Φ_{n}} are none for n = 0, (1)_{2} for n = 1, and (1β1)_{2} with β running through B_{n−2} for n ≥ 2 or, in other words, C_{n} = 2^{n−1} +(C_{n−1} ∪C_{n−2}). Hence these distances are all different so that |C_{n}| = F_{n}. We arrive at

Proposition 6. The number of 2-key distances in S_{p}^{n}, p ≥ 3, is F_{n−1}.

The sequence c obtained from ⋃_{n∈ℕ_{0}} C_{n}, ordered by size, is given by c_{n} = 2a_{n−1} + 1 for

n ∈ ℕ, i.e.,

c_{0} = 0, ∀ n ∈ ℕ ∀k ∈ [F_{n}]_{0} : c_{F_{n+1}+k} = c_{F_{n−1}+k} + 2^{n−1}.

It is \underline{A247648} = 2 · \underline{A003754} + 1 and starts (0,)1, 3, 5, 7, 11, 13, 15, 21, 23, 27, …; see [?, p. 77]. The sequence forms the self-generating set obtained from α = 1 and F = {k ↦ 2k + 1, k ↦ 4k + 1} in Lemma 1. In particular, the sequence c includes the odd Lichtenberg numbers, i.e., the positive 2-key distances for p = 2, which are generated by k ↦ 4k + 1 with seed 1.

The sets Φ_{n} contain, for p ∈ ℕ, p ≥ 3, and n ∈ ℕ, the vertices s ∈ [p − 2]^{n−1}(p − 1) with maximal distance δ(s, 0^{n}) = 2^{n} − 1. Similarly, the vertices s = ((p − 1)0)^{(n−1)/2} (p − 1), if n is odd, and s ∈ ((p − 1)0)^{(n−2)/2} [p − 2](p − 1), if n is even, have minimal distance δ(s, 0^{n}) = J_{n+1} (Jacobsthal numbers (\underline{A001045}); cf. [?]). For p = 3 it is possible to prove that all elements of Φ_{n} are those which lie on the straight line joining maximal distance with minimal distance vertices in the standard triangular drawing of S_{3}^{n}. If the side length of the triangle is chosen to be 1, this magic line is the same for all n [?, Theorem 3.3] and leads to a fractal if intersected with the Sierpiński triangle (of side length 1), see [?, Section 4]. When drawn as tetrahedra with side length 1, the graphs S_{4}^{n} contain an analogue magic triangle accommodating all 2-key vertices and leading to another fascinating fractal structure, the Pell fractal (cf. [?, Section 5]).

2.3 The case m = 3

A 3-key vertex s of S_{p}^{n} must satisfy

∑_{d=1}^{n}(s_{d} ≠ p − 1) · 2^{d−1} = 3 ∑_{d=1}^{n}(s_{d} ≠ 0) · 2^{d−1}.  (11)

If s_{n} ≠ 0, then RHS ≥ 3 · 2^{n−1} > M_{n} ≥ LHS; therefore s_{n} = 0 and (11) can be replaced by

2^{n−1} + ∑_{d=1}^{n−1}(s_{d} ≠ p − 1) · 2^{d−1} = 3 ∑_{d=1}^{n−1}(s_{d} ≠ 0) · 2^{d−1}.  (12)

For n = 1 this leads to a contradiction, whence _{3}Ψ_{p,1} = ∅. So let n ≥ 2 and assume that s_{n−1} = 0. Then RHS ≤ 3 · M_{n−2} < 3 · 2^{n−2} = 2^{n−1} + 2^{n−2} ≤ LHS, a contradiction. Similarly, if s_{n−1} = p−1, then LHS ≤ 2^{n−1}+M_{n−1} < 3·2^{n−2} ≤ RHS, another contradiction. Therefore, s_{n−1} ∈ [p − 2] and (12) reduces to

∑_{d=1}^{n−2}(s_{d} ≠ p − 1) · 2^{d−1} = 3 ∑_{d=1}^{n−2}(s_{d} ≠ 0) · 2^{d−1}.  (13)

For n = 2 we are done with _{3}Ψ_{p,2} = 0[p − 2]. For n ≥ 3 we notice that (13) is the same as (11), but with n replaced by n − 2. It follows that

3Ψ_{p,n} = 0[p − 2]_{3}Ψ_{p,n−2}

with δ(s, (p − 1)^{n}) = M_{n} for s ∈ _{3}Ψ_{p,n}. We can summarize the case m = 3 in the following theorem.

Theorem 7. The set of 3-key vertices in S_{p}^{n} is empty for odd n and otherwise _{3}Ψ_{p,n} = (0[p − 2])^{n/2} with |_{3}Ψ_{p,n}| = (p − 2)^{n/2}. The sequence of positive 3-key distances is \frac{1}{3}M_{2k} = ℓ_{2k−1} = 1, 5, 21, 85, … for k ∈ ℕ; these are the odd Lichtenberg numbers, \underline{A002450}. It is the self-generating sequence for seed 1 and generating function set {k ↦ 4k + 1}.

2.4 The case m = 4

For this case we need some preparation. For q ∈ ℕ_{0} let the sequences (F F_{q,n})_{n∈ℕ_{0}} be defined by

F F_{q,0} = F F_{q,1} = F F_{q,2} = 0,  (14)
F F_{q,3} = 1,  (15)
F F_{q,n+4} = q (F F_{q,n+3} + F F_{q,n+1}) + F F_{q,n}.  (16)

As before and consistent with (14), (15) and (16), we put F F_{q,−1} = 1. For q = 0, the sequence is F F_{0,n} = (n mod 4 = 3). If q = 1, we write F F_{n} for F F_{1,n}; then the sequence F F_{3+n} is \underline{A006498}. The sequence of differences \overline{F F} is, apart from the shift of the offset, \underline{A070550}. For the sequence of partial sums ΣF F, cf. the somewhat obscure entry \underline{A097083} of the OEIS. The sequences F F_{2,n} and F F_{3,n} are, but for the offsets, \underline{A089928} and \underline{A089931}, respectively. The relation between the sequences F F_{q,n} and F_{q,n} is the following.

Proposition 8. For all q, k ∈ ℕ_{0}: F F_{q,2k} = F_{q,k−1}F_{q,k}, F F_{q,2k+1} = F_{q,k}^{2}.

Proof. Induction on k, where the cases k = 0 and k = 1 are obvious. For k ∈ ℕ we get:

F F_{q,2(k+1)} = F F_{q,2(k−1)+4} = q · F F_{q,2(k−1)+3} + q · F F_{q,2(k−1)+1} + F F_{q,2(k−1)}
= q · F_{q,k}^{2} + q · F_{q,k−1}^{2} + F_{q,k−2}F_{q,k−1}
= q · F_{q,k}^{2} + F_{q,k−1}(q · F_{q,k−1} + F_{q,k−2})
= q · F_{q,k}^{2} + F_{q,k−1}F_{q,k} = F_{q,k}F_{q,k+1}

and

F F_{q,2(k+1)+1} = F F_{q,2k−1+4} = q · F F_{q,2k+2} + q · F F_{q,2k} + F F_{q,2k−1}
= q · F F_{q,2(k+1)} + q · F F_{q,2k} + F F_{q,2(k−1)+1}
= q · F_{q,k}F_{q,k+1} + q · F_{q,k−1}F_{q,k} + F_{q,k−1}^{2}
= q · F_{q,k}F_{q,k+1} + F_{q,k−1}F_{q,k+1} = F_{q,k+1}^{2}.

In particular, for all k ∈ ℕ_{0} we have

\begin{matrix}F F_{1,2k} = F_{k} · F_{k−1}, \\ F F_{1,2k+1} = F_{k}^{2} \end{matrix}  and  \begin{matrix}F F_{2,2k} = P_{k} · P_{k−1}, \\ F F_{2,2k+1} = P_{k}^{2}. \end{matrix}

We will now set out to prove

Theorem 9. For p ∈ ℕ, p ≥ 2, and n ∈ ℕ_{0} we have |_{4}Ψ_{p,n}| = F F_{p−2,n−1}.

Proof. For n = 0, we have _{4}Ψ_{p,0} = {ϵ}, whence |_{4}Ψ_{p,0}| = 1 = F F_{p−2,−1} by our convention. In S_{p}^{1} ≅ K_{p} there is no distance four times a different one, so _{4}Ψ_{p,1} = ∅ and |_{4}Ψ_{p,1}| = 0 = F F_{p−2,0}. For n ≥ 2 we have that s ∈ P^{n} lies in _{4}Ψ_{p,n} iff

(s_{1} ≠ p − 1) + (s_{2} ≠ p − 1) · 2 + ∑_{d=3}^{n}(s_{d} ≠ p − 1) · 2^{d−1}

= ∑_{d=3}^{n}(s_{d−2} ≠ 0) · 2^{d−1} + (s_{n−1} ≠ 0) · 2^{n} + (s_{n} ≠ 0) · 2^{n+1}.

This, in turn, is only possible if

s_{1} = p − 1 = s_{2}, ∀ d ∈ [n − 2] : s_{d} = 0 ⇔ s_{d+2} = p − 1, s_{n−1} = 0 = s_{n}.

For n = 2 and n = 3 this cannot be fulfilled, so _{4}Ψ_{p,2} = ∅ = _{4}Ψ_{p,3} and consequently |_{4}Ψ_{p,2}| = 0 = F F_{p−2,1} and |_{4}Ψ_{p,3}| = 0 = F F_{p−2,2}. For n ≥ 4 this amounts to s = 00\overline{s}(p − 1)(p − 1) with \overline{s} = s_{n−2} … s_{3} ∈ P^{n−4} fulfilling

s_{3} ≠ p − 1 ≠ s_{4}, ∀ d ∈ [n − 4] \ [2] : s_{d} = 0 ⇔ s_{d+2} = p − 1, s_{n−3} ≠ 0 ≠ s_{n−2}.  (17)

Let \overline{S}_{1} = \overline{S}_{2} = \overline{S}_{3} = ∅ and for n ≥ 4 denote the set of \overline{s} fulfilling (17) by \overline{S}_{n}. Then \overline{S}_{4} = \{ϵ\}, \overline{S}_{5} = [p−2], \overline{S}_{6} = [p−2]^{2}, and \overline{S}_{7} = [p−2]^{3} ˙∪ (p−1)[p−2]0. For n ≥ 8 we have the following three cases for an \overline{s} = s_{n−2}s_{n−3} … s_{3} ∈ \overline{S}_{n}, depending on the number of initial p − 1 (there cannot be three in a row because of (17)):

1. 0 ≠ s_{n−2} ≠ p − 1,

2. s_{n−2} = p − 1 ≠ s_{n−3} ≠ 0,

3. s_{n−2} = p − 1 = s_{n−3}.

In case 1, \overline{s} will run through [p − 2]\overline{S}_{n−1}, because s_{n−3} ≠ 0 ≠ s_{n−4}. In case 2, s_{n−4} has to be 0, and all elements of (p − 1)[p − 2]0\overline{S}_{n−3} are admissible because s_{n−5} ≠ 0 ≠ s_{n−6}. Finally, in case 3, s_{n−4} = 0 = s_{n−5}, and all elements of (p − 1)(p − 1)00\overline{S}_{n−4} are admissible because s_{n−6} ≠ 0 ≠ s_{n−7}. So we obtain that for n ≥ 8 (in fact, for n ≥ 5):

\overline{S}_{n} = [p − 2]\overline{S}_{n−1} ∪ (p − 1)[p − 2]0\overline{S}_{n−3} ∪ (p − 1)(p − 1)00\overline{S}_{n−4},  (18)

with the unions disjoint. We can conclude that (for n ∈ ℕ)

|\overline{S}_{1}| = |\overline{S}_{2}| = |\overline{S}_{3}| = 0,  (19)
|\overline{S}_{4}| = 1,  (20)
|\overline{S}_{n+4}| = (p − 2) (|\overline{S}_{n+3}| + |\overline{S}_{n+1}|) + |\overline{S}_{n}|.  (21)

Comparison of (19), (20), (21) with (14), (15), (16) yields |\overline{S}_{n}| = F F_{p−2,n−1} and since |_{4}Ψ_{p,n}| = |\overline{S}_{n}|, the theorem is proved.

If we ask for DD_{n} := {δ(s, 0^{n}) | s ∈ _{4}Ψ_{p,n}}, we see that DD_{0} = {0}, DD_{1} = DD_{2} = DD_{3} = ∅, and for n ≥ 4 we have

DD_{n} = 3 + \{∑_{d=3}^{n−2}(s_{d} ≠ 0) · 2^{d−1} | \overline{s} = s_{n−2} … s_{3} ∈ \overline{S}_{n}\} .  (22)

All elements of \overline{S}_{n} have the form σ = σ_{k} … σ_{1}, where σ_{ℓ} ∈ [p − 2] ˙∪ (p − 1)[p − 2]0 ˙∪ \{(p − 1)(p − 1)00} and k ∈ ℕ_{0} is such that σ has overall length n. It follows that the binary representation of a distance in DD_{n} has the form 00β_{k} … β_{1}11 with β_{ℓ} = 1 if σ_{ℓ} ∈ [p − 2], β_{ℓ} = 110 if σ_{ℓ} ∈ (p−1)[p−2]0, and β_{ℓ} = 1100 if σ_{ℓ} = (p−1)(p−1)00, respectively. Therefore,