Mathematical Assoc. of America American Mathematical Monthly 121:1 July 11, 2018 12:03 p.m. Proof-of-Kimberling-Conjecture˙1˙.

tex page 1

A Novel Proof for Kimberling’s Conjecture

on Doubly Fractal Sequences
Matin Amini and Majid Jahangiri

Abstract. A sequence is a fractal sequence if it contains itself as a proper subsequence. (The

arXiv:1612.09481v1 [math.NT] 30 Dec 2016

self-containment property resembles that of visual fractals) A doubly fractal sequence of inte-
gers is defined by operations called upper trimming and lower trimming. C. Kimberling proved
that signature sequences are doubly fractal and conjectured the converse. This article gives a
procedure for constructing doubly fractal sequences and proves Kimberling’s conjecture.

1. INTRODUCTION Geometric fractals are characterized by visual self-similarity.

That is, zooming on a visual fractal shows that the original structure is repeated inside
itself infinitely many times. Clark Kimberling noticed that a sequence of integers can
also contain infinitely many copies of itelf in two different ways [4], and he studied
properties of such sequences [1, 2, 3, 5, 6]. Briefly, operations called upper trimming
and lower trimming, applied to suitable sequences S , leave behind the sequence S
itself. An integer sequence of this sort is called a doubly fractal sequence. Signature
sequences as defined in Section 2, are known to be doubly fractal. In this article we
introduce a procedure for constructing doubly fractal sequences, and then we apply the
procedure to prove Kimberling’s conjecture that the signature sequences are the only
doubly fractal sequences.
The structure of this article is as follows: definitions and required preliminaries are
given in Section 2. The constructive procedure is given in Section 3, and the relation-
ship between the doubly fractal sequences and the signature sequences is discussed in
Section 4.

2. DEFINITIONS AND PRELIMINARIES Suppose S = (s1 , s2 , s3 , . . .) is a fi-

nite or infinite sequence of numbers in the set N of positive integers. The k th term of
a sequence S is denoted by S(k) or sk .
Definition 1. Suppose every positive integer occurs in S . The upper trimmed (sub)sequence
of S , denoted by ∧S , is the sequence that remains after every first occurrence of every
positive integer is removed from S .
Definition 2. Suppose every positive integer occurs in S . The lower trimmed (sub)sequence
of S , denoted by ∨S , is the sequence that remains after 1 is subtracted from every term
of S and then all 0s are removed.
Definition 3. A sequence S is a doubly fractal sequence if s1 = 1 and ∧S = ∨S = S .
Definition 4. A sequence (1, 2, . . . , n, m, . . .) in N where m 6= n is an initial segment
of type 1. A sequence (1, 1, . . . , 1, m, . . .) in N, where m > 1, is an initial segment of
type 2.
Now suppose every positive integer occurs at least once in S . The index of the k th
occurrence of n is denoted by Ik (n).
Lemma 5. Suppose S is a doubly fractal sequence. Then S has an initial segment of
type 1 or 2, and, a fortiori, that segment is one of these two forms: (1, 2, 3, . . . n, 1)
or (1, 1, . . . , 1, 2).
| {z }
n

January 2014] A NOVEL PROOF FOR KIMBERLING’S CONJECTURE 1

Mathematical Assoc. of America American Mathematical Monthly 121:1 July 11, 2018 12:03 p.m. Proof-of-Kimberling-Conjecture˙1˙.tex page 2

Proof. First s1 = 1 by Definition 3. We continue with two cases. Case 1: s2 6= 1.

If s2 > 2, then ∨S (1) = s2 − 1 > 1 6= 1, so that necessarily s2 = 2. Let n be the
greatest integer k for which sk = k . If sn+1 ≥ n + 1, then ∧S (n) ≥ n + 1 6= n =
sn , contrary to ∧S = S . Therefore, sn+1 = 1 as desired.
Case 2: s2 = 1. Suppose sk = 1 for k = 1, 2, . . . , n and sn+1 6= n. If sn+1 > 2, then
∨S (1) = sn+1 − 1 > 1 = s1 , contrary to ∨S = S . Therefore sn+1 = 2.
The sequence below is an example of a doubly fractal sequence which the second term
is not 2.

S = (1, 1, 1, 2, 1, 2, 1, 2, 3, 1, 2, 3, 1, 2, . . .).

Definition 6. Let θ be a real number and let Mθ = {i + jθ : i, j ∈ N}, a multiset

depending on θ . We arrange the numbers in Mθ in nondecreasing order(with duplicates
if and only if θ is rational) so that the ordered set can be represented as
∞
Mθ = (sh + ah θ)h=1 .

The sequence Sθ = (s1 , s2 , s3 , . . .) is the signature (sequence) of θ . For example,

S√13 = (1, 2, 3, 4, 1, 5, 2, 6, 3, 7, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11, 4, 8 . . .),

and the signature of 1/7 is

S1/7 = (1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 2, 1 . . .).

The next proposition is proved in [1].

Proposition 7. The signature of a positive number θ is a doubly fractal sequence.
Theorem 8. Distinct numbers have distinct signatures.
Proof. Prove this by contradiction. Without loose of generality, assume that α < β .
Denote the decimal representation of these numbers as α = a.a1 a2 a3 . . . am . . . and
β = b.b1 b2 b3 . . . bm . . ., in which ak = bk , for all k ≤ m and am+1 6= bm+1 . Now
for every e, f, g, h ∈ N we have e + f α < g + hα if and only if e + f β < g + hβ .
Equivalently g − e + (h − f )α > 0 if and only if g − e + (h − f )β > 0. So we can
write (−bb1 b2 b3 . . . bm bm+1 ) + β10m+1 ≥ 0 but we have (−bb1 b2 b3 . . . bm bm+1 ) +
α10m+1 < 0, a contradiction.

3. THE CONSTRUCTION PROCEDURE In this section we explain a procedure

which constructs doubly fractal sequences. The initial segment of a doubly fractal se-
quence S is either (1, 2, 3, . . . , n, 1) or (1, 1, . . . , 1, 2), by Lemma 5. We assume the
| {z }
n
former case, and the latter is translated to the former. Start with S = (1, 2, 3, . . . , n),
we extend this sequence in a way that in each step the result is always a doubly fractal
(finite) sequence. The terms of this initial segment is referred by the main terms. A
subsequence starts from a 1 term until the next n term is called a block. In each step,
the least positive integer which has not appeared until then in S is denoted by ℓS .
Extend S by rewriting the main terms after the initial block, term by term and in
each step insert ℓS after each main term except n, i.e., we have

S = (1, 2, 3, . . . , n, 1, n + 1, 2, n + 2, 3, n + 3, . . . , n − 1, 2n − 1, n).

2
c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 121
Mathematical Assoc. of America American Mathematical Monthly 121:1 July 11, 2018 12:03 p.m. Proof-of-Kimberling-Conjecture˙1˙.tex page 3

We start with A = (1, 2, 3, 4) and we have A = (1, 2, 3, 4, 1, 5, 2, 6, 3, 7, 4). The

next ℓS is 2n. Until now the sequence S is extended two blocks. To construct bth
block, b ≥ 3, we proceed as follows. Constitute the sequence t from the terms be-
tween n − 1 and n exclusive in the (b − 1)th block of S and add 1 to all of them,
and the sequence t′ from the terms between last n + 1 and its previous n term, ex-
clusive (e.g., in sequence A we have t = (8) and t′ = (1)). In other words, for each
k > 2, t = (S(Ik (n − 1) + 1) + 1, . . . , S(Ik (n) − 1) + 1) and t′ = (S(Ik−1 (n) +
1), . . . , S(Ik−1 (n + 1) − 1)).
Proposition 9. The ℓS and 1 appear once in t and t′ , respectively, and all of other
terms of t and t′ are the same.
Proof. For the sequence t′ , from Properties (II) and (III), for any k > 1, terms be-
tween S(Ik (n)) and S(Ik (n + 1)) should turn to terms between S(Ik (n − 1)) and
S(Ik (n)) by lower-trimming, and should turn to terms between S(Ik−1 (n)) and
S(Ik−1 (n + 1)) by upper-trimming. So the terms between S(I2 (n)) and S(I2 (n +
1)) are upper-trimmed to the terms between S(I1 (n)) and S(I1 (n + 1)), which is
only the 1 term. In the case of the sequence t, only one ℓS is inserted between each
main term, especially n − 1 and n, by the construction. So there’s one 1 term in
the subsequence T ′ = (S(Ik−1 (n)), . . . , S(Ik−1 (n + 1))) and one ℓS term in the
subsequence T = (S(Ik (n − 1)), . . . , S(Ik (n))). The lower-trimming of S turn the
terms of T ′ to that terms of S in which the terms of T will turn to them when S
is upper-trimmed. Therefore all elements of T and T ′ other than ℓS and 1 are the
same.
We denote by Indxt (ℓS ) and Indxt′ (1) the position of ℓS and 1 in the sequences
t and t′ , respectively. We constitute a new sequence P from t and t′ by merging them
as follows. Write all terms of t′ into the P except 1. If Indxt (ℓS ) = Indxt′ (1) then
insert one of the subsequences (1, ℓS ) or (ℓS , 1) in the position Indxt (ℓS ) into the
P sequence. For example, in the case of A = (1, 2, 3, 4, 1, 5, 2, 6, 3, 7, 4), the next
ℓS will be 8 and P would be (1, 8) or (8, 1). On the other hand, if Indxt (ℓS ) 6=
Indxt′ (1) then insert the ℓS and 1 simultaneously into the P in the positions
Indxt (ℓS ) and Indxt′ (1), respectively. For example, if t = (a1 , ℓS , a2 , a3 , a4 )
and t′ = (a1 , a2 , a3 , 1, a4 ) then P = (a1 , ℓS , a2 , a3 , 1, a4 ). Set d = IndxP (1) −
IndxP (ℓS ). In P , delete the term 1 and all the terms after 1 (P may become a null
sequence). To extend the sequence S , append P to the end of S . After that we want
to rewrite the terms of last block, term by term such that if the appended term is a
main term m, then insert the new ℓS into the position IndxS (ℓS ) = IndxS (m) − d
if and only if IB (1) ≤ IndxS (ℓS ) ≤ IB (n). In The case of our example sequence A,
P = () and d = −1, so it is extended as
A = (1, 2, 3, 4
1, 5, 2, 6, 3, 7, 4
1, 8, 5, 2, 9, 6, 3, 10, 7, 4).
For the next extension, t = (11, 8) and t′ = (1, 8). Let P = (11, 1, 8) and so d = 1.
Deleting 1 and the terms after 1 from P and extending the sequence A results that

A = (1, 2, 3, 4,
1, 5, 2, 6, 3, 7, 4,
1, 8, 5, 2, 9, 6, 3, 10, 7, 4, 11,

January 2014] A NOVEL PROOF FOR KIMBERLING’S CONJECTURE 3

Mathematical Assoc. of America American Mathematical Monthly 121:1 July 11, 2018 12:03 p.m. Proof-of-Kimberling-Conjecture˙1˙.tex page 4

1, 8, 5, 12, 2, 9, 6, 13, 3, 10, 7, 14, 4).

At this point t = (11, 8, 15) and t′ = (11, 1, 8), so Indxt (ℓS ) 6= Indxt′ (1). There-
fore P = (11, 1, 8, 15) and then d = −2. Deleting 1 and the terms after 1 from P and
appending it to the end of A demonstrates

A = (1, 2, 3, 4,
1, 5, 2, 6, 3, 7, 4,
1, 8, 5, 2, 9, 6, 3, 10, 7, 4, 11,
1, 8, 5, 12, 2, 9, 6, 13, 3, 10, 7, 14, 4, 11,
1, 8, 15, 5, 12, 2, 9, 16, 6, 13, 3, 10, 17, 7, 14, 4).

Note that since d = −2, ℓS ’s are inserted two positions after each main term except
for n term.
Now assume that we start with the latter possibility of initial segment, i.e., S =
(1, 1, . . . , 1, 2). In this case first we construct the doubly fractal sequence started by
| {z }
n
S ′ = (1, 2, . . . , n) and then extend S by computing kth term of S , k > n + 1, by the
formula

S(k) = #{s′i | s′i = s′k , 1 ≤ i ≤ k}.

For example, beginning from A′ = (1, 1, 1, 1, 2) then the extended sequence will be

A′ = (1, 1, 1, 1,
2, 1, 2, 1, 2, 1, 2,
3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1,
4, 2, 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4, 1,
5, 3, 1, 4, 2, 5, 3, 1, 4, 2, 5, 3, 1, 4, 2, 5).

4. THE MAIN RESULT In this section we discuss the correspondence of the family
of doubly fractal sequences and the the family of signature sequences. In [4] C. Kim-
berling conjectured that these two families should be the same. Here we try to give a
proof to this conjecture.
Lemma 10. The n + 2 first terms of a doubly fractal sequence can be the initial
segment of infinitely many signature sequences.
Proof. For any real number n − 1 ≤ θ ≤ n, we have the relations

1 + θ < 2 + θ < . . . < n + θ ≤ 1 + 2θ ≤ n + 1 + θ

in the construction of its signature sequence. So the initial segment of the signature
sequence of each n − 1 ≤ θ ≤ n will be (1, 2, 3, . . . , n, 1, n + 1). In the case of
1
n+1
≤ θ ≤ n1 , the inequalities are in the form:

1 + θ < 1 + 2θ < . . . < 1 + nθ ≤ 2 + θ ≤ 1 + (n + 1)θ.

4
c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 121
Mathematical Assoc. of America American Mathematical Monthly 121:1 July 11, 2018 12:03 p.m. Proof-of-Kimberling-Conjecture˙1˙.tex page 5

Theorem 11. Every doubly fractal sequence S can be made by the construction pro-
cedure explained in §3. Also every sequence made by that procedure is doubly fractal.
Proof. The conclusion will be obtained by induction. Let S be an arbitrary doubly
fractal sequence. By Lemma 5, the initial block of every doubly fractal sequence is
either (1, 2, 3, ..., n, 1) or (1, 1, 1, . . . , 1, 2). This coincides with the initial assump-
tion in our construction. Now suppose that until the k th occurrence of the integer n,
the sequence S coincides with the sequence obtained by k th extension steps of the
procedure of §3. Define by Pk (n) = (S(Ik (n)), . . . , S(Ik+1 (n) − 1)) the k -th part
of S . Since S is assumed to be doubly fractal, then Property (II) implies that:

∧Pk+1 (n) = Pk (n). (4.1)

So the first term of the (k + 1)st part is n and all other of the main terms must appear
in (k + 1)st part. Since the k th part contains a term n + 1, so by Property (II), the
(k + 1)st part should contain n + 1. Let π denote the terms appeared between n and
n + 1 in the (k + 1)st part of S . From the construction rule of t′ in §3, one 1 appears
between n and n + 1 in the k th part of S , so 1 should also appear in π . Property
(III) implies that all the terms of π must be lower-trimmed to terms between (k + 1)st
term n − 1 and (k + 1)st term n (which was the t sequence formed in the procedure
§3). There is one LS in t in kth part, so LS + 1 should appear in π . So the merging
sequence of t and t′ as described in the procedure §3 will exactly be the same as the
π sequence and the distance of 1 and LS + 1 in π is equal to the d defined in §3. The
rule of allocating the new ℓS ’s in the construction procedure assures that the distance
of them from the main terms satisfy the Properties (II) and (III).
Theorem 12 (Main Theorem). Each sequence S = (s1 , s2 , s3 , . . .) constructed by
the procedure explained in §3 is a signature one. In other words, every doubly fractal
sequence is a signature sequence.
Proof. If there exists a positive real number θ such that Sθ = S , we are done. On
the contrary, suppose there is not any real number θ such that its signature sequence
coincides with S . Suppose {1, 2, . . . , n} are the main terms of S . By Lemma 10, first
n + 2 terms of S is the initial segment of infinitely many signature sequences. Let Sm ,
m ≥ n + 2, be the longest initial segment of S which is the initial segment of some
signature sequence S ′ . So sm+1 6= s′m+1 . By Proposition 7, S ′ is also doubly fractal,
therefore one could assign 1 or ℓS in the construction step of sm+1 , by Theorem 11.
Without lose of generality assume that sm+1 = 1. The case sm+1 = ℓS is similar.
According to the doubly fractality of S ′ , the term after ℓS in S ′ must be 1. So Sm+2′
=
(s1 , . . . , sm , ℓS , 1) is the initial segment of S . Since Sm+2 is the initial segment of
′ ′

the signature sequence S ′ , they satisfy the inequalities

s′1 + a′1 θ ≤ s′2 + a′2 θ ≤ . . . ≤ s′m + a′m θ ≤ ℓS + θ ≤ 1 + a′m+2 θ (4.2)

in which for 1 ≤ i ≤ m + 1, a′i is the number of iterations of s′i in Si′ . By the as-
sumption, since Sm+1 is not the initial segment of any signature sequence, one of the
inequalities

s1 + a1 θ ≤ s2 + a2 θ ≤ . . . ≤ sm + am θ ≤ 1 + am+1 θ (4.3)

must be unsatisfied. Since a1 = a′1 , a2 = a′2 , . . . , am = a′m , am+1 = a′m+2 , unsatis-

fiability of (4.3) contradicts the satisfiability of (4.2).

January 2014] A NOVEL PROOF FOR KIMBERLING’S CONJECTURE 5

Mathematical Assoc. of America American Mathematical Monthly 121:1 July 11, 2018 12:03 p.m. Proof-of-Kimberling-Conjecture˙1˙.tex page 6

REFERENCES

1. Clark Kimberling, Fractal Sequences and Interspersions Ars Combin. 44 (1997), 157–168.
2. Clark Kimberling, Interspersions and Dispersions Proc. Amer. Math. Soc. 117.2 (1993), 313–321.
3. Clark Kimberling, Numeration Systems and Fractal Sequences Acta Arith. 73 (1995), 103–117.
4. Clark Kimberling and John E. Brown, Partial Complements and Transposable Dispersions J. Integer Seq.
7 (2004).
5. Clark Kimberling and A. S. Fraenkel, Generalized Wythoff arrays, shuffles and interspersions Discrete
Mathematics 126 (1994), 137–149.
6. Clark Kimberling and H. S. Shultz, Card sorting by dispersions and fractal sequences Ars Combin. 53
(1999), 209–218.
7. Franklin T. Adams-Watters, https://oeis.org/A002260/a002260.txt.

MATIN AMINI ([email protected])

National Organization for Development of Exceptional Talents (NODET), Tehran, Iran
[email protected]

MAJID JAHANGIRI ([email protected])

School of Mathematics, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran
[email protected]

6
c THE MATHEMATICAL ASSOCIATION OF AMERICA [Monthly 121