WORDS, PERMUTATIONS, AND REPRESENTATIONS OF NUMBERS

HELMUT PRODINGER

Abstract. In this survey paper we consider words, where the letters are interpreted to be numbers or digits. In the first part, natural numbers are weighted with probabilities (from the geometric distribution). Several properties and parameters of sets of such words are analyzed probabilistically; the case of permutations is a limiting case. In the second part, the representation of Gaussian integers to the base −2 + i is considered, as well as redundant representations to the base q, where the digits can be arbitrary integers.

Dedicated to Werner Kuich on the occasion of his sixtieth birthday

1. Introduction

In this survey paper, we consider words w = a_{1}a_{2} … a_{n}, where the letters a_{i} are taken from the set ℤ or a finite subset thereof. In the first part, we assume that the letters are obtained from the geometric distribution, i. e. ℙ{a = k} = pq^{k−1} with p + q = 1. In this way, a probability (weight) is attached to each word w, namely (p/q)^{n}q^{a_{1}+···+a_{n}} (we assume that the letters are independent from each other). Of course, a probability is then also attached to each set L ∩ ℕ^{n}, where L is an arbitrary language. Most of the time, we will consider probability generating functions ∑_{n≥0} ℙ{L ∩ ℕ^{n}}z^{n}. A typical example is the set of all up–down words L = {a_{1}a_{2} … a_{n} | n ≥ 0, a_{1} ≤ a_{2} ≥ a_{3} ≤ … }. The probability of L ∩ ℕ^{n} is then the probability that a random word of length n is an up–down word. The interest in the geometric distribution comes from computer science applications, namely a data structure called skip lists [9], and permutation counting. A permutation σ_{1}σ_{2} … σ_{n} does not enjoy the independence property of letters in a word; a letter σ_{i} can only occur if it was not already used in σ_{1}σ_{2} … σ_{i−1}. This is often cumbersome to model. However, with the present approach, we can (often) consider the limit q → 1. Then, the probability that a letter appears more than once, goes to 0, and each relative ordering of the letters is equiprobable. Hence parameters of permutations which only depend on the “order statistics” will carry over. For example, the parameter “position of the largest element” translates accordingly, but not “value of the largest element.” We report about some recent results in the sequel.

The second part of this survey deals with the alphabet {0, 1, …, q − 1} and similar ones; we think of the letters as digits, and consider the words as representations of numbers. For example, a word a_{n} … a_{1}a_{0} represents the number ∑_{i=0}^{n} a_{i}q^{i} in the q–ary representation. The kth digit of the q–ary representation of n is given by

a_{k} = ⌊\frac{n}{q^{k}} ⌋ − q ⌊\frac{n}{q^{k+1}} ⌋ .

We will deal with more exotic number systems: On the one hand, with the basis −2 + i (with the complex unit i = \sqrt{−1} ), see [4], and on the other hand with redundant representations to the base q, where the digits are allowed to be integers (the alphabet is then ℤ), see [20, 7].

2. Words, geometric probabilities, and permutations

2.1. Monotone words. One of the simplest examples deals with the probability that a word is monotone, i. e. a_{1} < a_{2} < … (or a_{1} ≤ a_{2} ≤ …). This establishes a nice combinatorial interpretation of Euler’s partition identities (see [15]). The identities in question are

∏_{n≥0} (1 + tq^{n}) = ∑_{n≥0} \frac{t^{n}q^{\binom{n}{2}}}{(q; q)_{n}} and ∏_{n≥0} \frac{1}{1 − tq^{n}} = ∑_{n≥0} \frac{t^{n}}{(q; q)_{n}} ,

where (x; q)_{n} := (1 − x)(1 − qx) … (1 − q^{n−1}x). Now the language of monotone words is M_{<} = (ε + 1)(ε + 2) … resp. M_{≤} = 1^{∗} · 2^{∗} …, so that the associated generating functions are given as

M_{<}(z) = ∏_{k≥0} (1 + pq^{k}z) = ∑_{n≥0} \frac{p^{n}z^{n}q^{\binom{n}{2}}}{(q; q)_{n}}

and

M_{≤}(z) = ∏_{k≥0} \frac{1}{1 − pq^{k}z} = ∑_{n≥0} \frac{p^{n}z^{n}}{(q; q)_{n}} .

Therefore the probability that a word of length n is strictly monotone, is p^{n}q^{\binom{n}{2}}/(q; q)_{n} and that it is weakly monotone is p^{n}/(q; q)_{n}. Both quantities tend for q → 1 to 1/n!, which confirms to the fact that just one permutation of n elements is monotone.

2.2. Alternating words. Let us now consider up–down words or down– up words; for permutations, this does not make a difference, but for words it does (see [19] for details). Naturally, one can combine the weak and strict forms for the inequalities. Also, one must distinguish the case of odd resp. even lengths of words. The case of odd lengths is more interesting. Let f^{≤>}(z) be the generating functions where the coefficient of z^{2n+1} is the probability that a word a_{1} … a_{2n+1} satisfies a_{1} ≤ a_{2} > a_{3} ≤ …, etc. The results can all be expressed with the following “q–tangent function”

tan_{q}^{[A,B,C,D]}(z) := ∑_{n≥0} \frac{(−1)^{n}z^{2n+1}}{[2n + 1]_{q}!} q^{An^{2}+Bn}/ ∑_{n≥0} \frac{(−1)^{n}z^{2n}}{[2n]_{q}!} q^{Cn^{2}+Dn};

here we used the notation of q–factorials: [n]_{q}! = (q; q)_{n}/(1 − q)^{n}, which converges for q → 1 to n!.

f^{≥≤}(z) = tan_{q}^{[1,1,1,−1]}(z), f^{<>}(z) = tan_{q}^{[1,1,1,0]}(z),
f^{><}(z) = tan_{q}^{[1,0,1,0]}(z), f^{≤≥}(z) = tan_{q}^{[1,0,1,−1]}(z),
f^{≥<}(z) = f^{≤>}(z) = f^{>≤}(z) = f^{<≥}(z) = tan_{q}^{[0,0,0,0]}(z).

Generating functions for patterns like (≤≤≥)^{∗} lead to Olivier functions, see [1]; q–versions of that are currently worked out together with A. Tsifhumulo.

2.3. The q–path length of a binary search tree. The path length ρ(t) of a binary search tree t is the defined to be the sum over all distances from the root to any node in the tree (measured in terms of nodes, not edges) and satisfies the recursion ρ(t) = ρ(t_{L}) + ρ(t_{R}) + |t_{L}| + |t_{R}| where t_{L} and t_{R} are the left resp. right subtree of the root. (|t| denotes the size of the tree t, i. e. the number of nodes.) Our aim is to rewrite the definition of the path length in terms of permutations. For a permutation π = π_{1} … π_{n} we define ρ(π) by

ρ(π) = |{(j, k) | 1 ≤ j < k ≤ n, π_{j} = min{π_{j},...,π_{k}} or π_{k} = min{π_{j},...,π_{k}}}|.

Then ρ(□) = 0 and, if π = σ1τ, then ρ(π) = ρ(σ) + ρ(τ) + |σ| + |τ|, as pairs with the left coordinate in σ and the right coordinate in τ are definitely not counted. (The correspondence from permutations to trees is as follows: the smallest number forms the root, everything to the left (right) of it (recursively) the left (right) subtree.) This definition gives the path length of the binary search tree associated to the permutation π = π_{1} … π_{n}, provided we interpret π_{i} as the arrival position of key i. But this definition of π can be taken as it is, where π_{1} … π_{n} now denotes a word over the alphabet {1, 2, … }. We compute the expectation of the parameter ρ, for random words of length n, and define for this purpose random variables

L_{jk} = \begin{cases}1 & if π_{j} = min\{π_{j}, …, π_{k}\} \\ 0 & otherwise, \end{cases} , R_{jk} = \begin{cases}1 & if π_{k} = min\{π_{j}, …, π_{k}\} \\ 0 & otherwise, \end{cases} ,

B_{jk} = L_{jk} · R_{jk}, N_{jk} = (1 − L_{jk}) · (1 − R_{jk}). (The letters L, R, B, N are chosen to indicate left, right, both, not.) Then the parameter ρ may be described as

ρ = ∑_{1≤j<k≤n} [L_{jk} + R_{jk} − B_{jk}].

From this one can compute the expected value (q–analogue of the path length in a binary search tree of size n):

E_{n} = (1 − q^{2}) ∑_{1≤i≤n} \frac{n + 1 − i}{1 − q^{i}} − n(1 + q),

which is in the limit q → 1: E_{n} = 2(n + 1)H_{n} − 4n, as is of course well known. (The notations H_{n} = ∑_{1≤k≤n} \frac{1}{k} refer to harmonic numbers, see e. g. [5].) The variance can also be computed, but this is much harder.

A similar but simpler parameter appears in [17], namely the number of inversions (for words):

E_{n} = \frac{n(n − 1)}{2} \frac{q}{1 + q} ,
V_{n} = \frac{n(n − 1)}{6} \frac{q}{(1 + q)^{2}(1 + q + q^{2})}(2(1 − q + q^{2})n − q^{2} + 7q − 1).

The same paper has also a parameter a of Knuth, which is important in the analysis of permutation in situ:

a = |{(i, j) | 1 ≤ i < j ≤ n, x_{i} = min{x_{i}, x_{i+1}, …, x_{j}}}|.

Its expectated value can be computed as follows:

E_{n} = (\frac{p}{q})^{n} ∑_{i_{1},...,i_{n}≥1} q^{i_{1}+···+i_{n}} ∑_{1≤j<k≤n}[[i_{j} = min\{i_{j}, …, i_{k}\}]]

= ∑_{1≤j<k≤n} (\frac{p}{q})^{k+1−j} ∑_{i_{j}=min\{i_{j},...,i_{k}\}} q^{i_{j}+···+i_{k}}

= ∑_{1≤j<k≤n} (\frac{p}{q})^{k+1−j} ∑_{i≥1} q^{i(k+1−j)} \frac{1}{p^{k−j}}

= p ∑_{1≤j<k≤n} (\frac{1}{q})^{k+1−j} ∑_{i≥1} q^{i(k+1−j)}

= p ∑_{1≤j<k≤n} \frac{1}{1 − q^{k+1−j}}

= p ∑_{2≤h≤n}(n + 1 − h)\frac{1}{1 − q^{h}} .

(We used the Iverson convention: [[C]] = 1 if the condition C is true, and [[C]] = 0 otherwise.)

2.4. Lengths of ascending runs. Knuth in [12] has considered the average length L_{k} of the kth ascending run in random permutations of n elements (for simplicity, mostly the instance n → ∞ was discussed). We study the concept of ascending runs in our usual setting (see [18, 13]), i. e., we consider infinite words, with letters 1, 2, ⋯, and they appear with probabilities p, pq, pq^{2}, · · ·. If we decompose a word into ascending runs

a_{1} < ⋯ < a_{r} ≥ b_{1} < ⋯ < b_{s} ≥ c_{1} < ⋯ < c_{t} ≥ ⋯,

then r is the length of the first, s of the second, t of the third run, and so on. We are interested in the averages of these parameters. The generating function

∏_{i≥1}(1 + pq^{i−1}z) = (−pz; q)_{∞}

plays a rôle here, where (a; q)_{∞} = (1 − a)(1 − aq)(1 − aq^{2}) ⋯:

Λ_{m}(z) = ∑_{n≥0}[Probability that a word of length n has (exactly) m ascending runs]z^{n},

then Λ_{0}(z) = 1 and Λ_{1}(z) = (−pz; q)_{∞} − 1 and we have the recurrence

Λ_{m}(z) = ((−pz; q)_{∞})^{m} − ∑_{k=1}^{m} \frac{1}{k!}D^{k}(z^{k}Λ_{m−k}(z))

(D means differentiation w. r. t. z.) In the limiting case q → 1 we can specify these quantities explicitly:

Λ_{m}(z) := e^{mz} − ∑_{k=1}^{m} \frac{1}{k!}D^{k}(z^{k}Λ_{m−k}(z)), Λ_{0}(z) := 1,

and for m ≥ 1 (e. g. via induction)

Λ_{m}(z) = ∑_{j=0}^{m} e^{jz} \frac{z^{m−j−1}(−1)^{m−j}j^{m−j−1}(j(z − 1) + m)}{(m − j)!}.

Knuth has shown that the average length of the mth run is given by

L_{m} = Λ_{m}(1) = m ∑_{j=0}^{m} \frac{(−1)^{m−j}j^{m−j−1}}{(m − j)!} e^{j},

and that L_{m} → 2. In the general case, we are able to prove that L_{m} → 1 + q. To do that we study the double generating function

R(w, z) = ∑_{m≥0} Λ_{m}(z)w^{m} = \frac{1 − w}{1 − w ∏_{n≥0}(1 + pz(1 − w)q^{n})}.

In the limit q → 1 we get R(w, z) = (1 − w)/(1 − we^{z(1−w)}), which is the generating function for Eulerian numbers A(n, k). Note that A(n, k) is the number of permutations of n elements with exactly k runs. (Sometimes, as in [5], the focus is on the number of descents, which is one less than the number of runs.) Hence R(w, z) provides q–Eulerian numbers which differ from those investigated by Carlitz [2].

2.5. Left–to–right maxima. As is easy to guess by the name, this parameter counts how often we meet a number that is larger than all the elements to the left. The results for random permutations are: The harmonic number H_{n} for the expectation and H_{n} − H_{n}^{(2)} for the variance; here, H_{n}^{(2)} = 1 + \frac{1}{4} + ⋯ + \frac{1}{n^{2}} denotes the nth harmonic number of second order.

For recent research on that in the context of random words, see [16, 10, 21]. We will set up a certain “language” L and translate it to enumerating generating functions. We decompose all sequences x_{1}x_{2} … in a canonical way as follows: We combine each left–to–right maximum k with the following (smaller or equal) elements. Such a part is described by A_{k} := k{1, …, k}^{∗}. Such a group may be present or not. This observation gives the desired “language,” where ε denotes the “empty word:”

L := (A_{1} + ε) · (A_{2} + ε) · (A_{3} + ε) ….

Now we want to mark each letter by a “z” and each left–to–right maximum by a “u”. The probability pq^{k−1} for a letter k should of course not being forgotten. The set {1, …, k} maps into z(1 − q^{k}) and its star {1, …, k}^{∗} into 1/(1 − z(1 − q^{k})). So we obtain the generating function F (z, u) as an infinite product:

F (z, u) = ∏_{k≥1} (1 + \frac{zupq^{k−1}}{1 − z(1 − q^{k})}) .

To be explicit, the coefficient of z^{n}u^{k} in F (z, u) is the probability that n random variables have k left–to–right maxima. Let f(z) = \frac{∂F (z,y)}{∂y} |_{y=1}. It is the generating function for the expected values E_{n}. We obtain

f(z) = \frac{pz}{1 − z} ∑_{k≥0} \frac{q^{k}}{1 − z(1 − q^{k})},

which is also, by partial fraction decomposition,

f(z) = p ∑_{k≥0} [\frac{1}{1 − z} − \frac{1}{1 − z(1 − q^{k})}] .

From this the coefficients E_{n} are easy to get:

E_{n} = [z^{n}]f(z) = p ∑_{k≥0} [1 − (1 − q^{k})^{n}] .

The asymptotic evaluation of this is well known: The average number E_{n} of left–to–right maxima in the context of n independently distributed geometric random variables has the asymptotic expansion

E_{n} = p [log_{Q} n + \frac{γ}{L} + \frac{1}{2} − δ (log_{Q} n)] + O(\frac{1}{n})

with a (small) periodic function δ(x). (Here and later we will use the handy abbreviations Q = 1/q and L = log Q.)

Now we turn to the average value and position of the rth left–to–right maximum, for fixed r and n → ∞, something that was studied by Wilf in the instance of permutations [24]. Summarizing our results, we obtain the asymptotic formulæ \frac{r}{p} and \frac{1}{(r−1)!}(\frac{p}{q} log_{Q} n)^{r−1}. The generating function related to the value of interest is

Value(z, u) := \frac{1}{1 − z} ∏_{i=1}^{h−1} \{1 + \frac{pq^{i−1}zu}{1 − (1 − q^{i})z} \} zpq^{h−1},

which originates from the (unique) decomposition of a string as a_{1}w_{1} … a_{r−1}w_{r−1}a_{r}w where a_{1}, …, a_{r} are the left–to–right maxima, the w_{i} are the strings between them, and w can be anything. Note that if a_{k} = l, then this corresponds to a term pq^{l−1}zu. Any letter in w_{k} can come with the probability 1 − q^{k}, and thus w_{k} corresponds to ∑_{j≥0}(1 − q^{k})^{j}z^{j} = 1/(1 − (1 − q^{k})z). A particular value i does not necessarily occur as a left–to–right maximum; that is reflected by the 1 + … in the product. However, when we look for the coefficient of u^{r−1}, we have seen r − 1 left–to–right maxima, and the rth has value h. What comes after that is irrelevant and covered by the factor 1/(1−z). We find it useful to use the abbreviation [[i]] := 1−(1−q^{i})z. The coefficients of z^{n}u^{r−1} in Value(z, u), call them π_{n,h}^{(r)}, are not probabilities, because there exist words of length n

with fewer than r left–to–right maxima, but the quantities π_{n,h}^{(r)}/π_{n}^{(r)} are,

where π_{n}^{(r)} is the probability that a string of length n has r left–to–right maxima. We compute π_{n}^{(r)} from Value(z, u) by summing over all values h;

π_{n}^{(r)} := [z^{n}u^{r−1}]\frac{1}{1 − z} ∑_{h≥1} ∏_{i=1}^{h−1} \{1 + \frac{pq^{i−1}zu}{[[i]]}\} zpq^{h−1} = ∑_{h≥1} π_{n,h}^{(r)}.

Now we turn to the position. Set

σ_{n,j}^{(r)} := [z^{n}u^{r−1}v^{j}]\frac{1}{1 − z} ∑_{h≥1} ∏_{k=1}^{h−1} \{1 + \frac{pq^{k−1}zvu}{1 − (1 − q^{k})zv} \} zvpq^{h−1},

then σ_{n,j}^{(r)}/π_{n}^{(r)} is the probability that a random string of length n has the rth left–to–right maximum in position j. It is the same decomposition as before, however, we are not interested in the value h, so we sum over it. On the other hand, we label the position with the variable v, so we must make sure that every z that does not appear in the factor 1/(1 − z) must be multiplied by a v. Computationally, we find it easier to work with the parameter “position −r”. This leads us to the generating function

Position(z, u, v) := \frac{1}{1 − z} ∑_{h≥1} ∏_{k=1}^{h−1} \{1 + \frac{pq^{k−1}zu}{1 − (1 − q^{k})zv} \} zpq^{h−1}.

There is no space to develop this further; for a full account see [10].

Now we consider the instance of large left–to–right maxima (see [21]). We say that the last left–to–right maximum is the instance r = 1, the previous left–to–right maximum is the instance r = 2, and so on.

The largest element in a random permutation of n elements (which is n) is expected to be in the middle. The second largest is then expected to be in the middle of the first half, and so on. In general, the average position should be about n/2^{r}. The following expression for the average value of the rth left–to–right maximum from the right is obtained as before; just observe that we assume that it is h, and that r − 1 more left–to–right maxima follow to the right, whereas to the left everything is smaller than h:

E_{n}^{(r)} = (−1)^{r}(\frac{p}{q})^{r} ∑_{k=r}^{n} \binom{n}{k}(−1)^{k} ×

× [w^{k}] ∑_{1≤h<i_{1}<···<i_{r−1}} \frac{hwq^{h}}{(1 − wq^{h−1})(1 − wq^{h})} \frac{q^{i_{1}}w … q^{i_{r−1}}w}{(1 − q^{i_{1}}w) … (1 − q^{i_{r−1}}w)}.

A lengthy study leads to

E_{n}^{(r)} = log_{Q} n + σ_{r} + δ_{r}(log_{Q} n) + o(1),

where δ_{r}(x) is a small periodic function of log_{Q} n; the constant σ_{r} is given by

σ_{r} = \frac{γ}{L} + \frac{1}{2} − p^{r−1} ∑_{j≥1} \frac{q^{(j−1)(r−1)}}{(1 − q^{j})^{r}} − p ∑_{j≥1} \frac{q^{j}}{(1 − q^{j})^{2}}

+ p^{r−1} ∑_{j≥1} \frac{q^{j(r−1)}}{(1 − q^{j})^{2}(1 − q^{j+1})^{r−2}} .

Turning to the average position of the rth left–to–right maximum from the right we find

E_{n}^{(r)} = (−1)^{r−1}(\frac{p}{q})^{r} ∑_{k=r+1}^{n} \binom{n}{k}(−1)^{k} ×

× [w^{k}] ∑_{1≤h<i_{1}<···<i_{r−1}} \frac{wq^{h}w(1 − q^{h−1})}{(1 − wq^{h−1})^{2}(1 − wq^{h})} \frac{wq^{i_{1}}}{1 − wq^{i_{1}}} … \frac{wq^{i_{r−1}}}{1 − wq^{i_{r−1}}}

and

E_{n}^{(r)} = (−1)^{r}(\frac{p}{q})^{r−1}ψ_{r}(1) n + ϖ_{r}(log_{Q} n) + o(n),

with some complicated constants and periodic functions. In the limit q → 1 (permutations), this simplifies to

E_{n}^{(r)} = \frac{n}{2^{r}} + o(n).

2.6. Skip lists. We start from the interpretation of a skip list ρ of size n as a word ρ = a_{1} … a_{n}, n ≥ 0, a_{i} ∈ {1, 2, 3, … }. The (horizontal) path length X_{n} is a random variable defined on the set of words of length n. For an individual word, the path length b(ρ) is defined as the sum of all numbers of (weak) right–to–left maxima in the subwords (prefixes) a_{1}, …, a_{i}.

For example, consider 21413. The right–to–left maxima when considering prefixes are 2, 2—1, 4, 4—1, 4—3, given a total of 1+2+1+2+2 = 8.

In order to obtain an expression for the corresponding probability generating function it is convenient to start from the following combinatorial decomposition:

Let m be the maximal element occuring in ρ. Then we can write ρ in a unique way as

ρ = σmτ, where σ ∈ {1, …, m − 1}^{∗}, τ ∈ {1, …, m}^{∗}

(fixing the leftmost occurence of the maximum m). From this decomposition it follows that

b(ρ) = b(σmτ) = b(σ) + b(τ) + |τ| + 1, b(ε) = 0,  (1)

since the contribution of the leftmost maximum is 1 plus the number of the succeding elements. We introduce the bivariate generating functions P^{=m}(z, u), where the coefficient of z^{n}u^{j} is the probability that a skip list ρ with n elements has maximum element m and path length j. The generating functions P^{≤m}(z, u) and P^{<m}(z, u) are defined analogously. Then relation (1) translates into the functional equation

P^{=m}(z, u) = pq^{m−1}zuP^{<m}(z, u)P^{≤m}(zu, u), P^{=0}(z, u) = 1. (2)

Although no simple closed formula for the solution of (2) is available, it allows to extract sufficient information on the moments of the path length. If we set F^{∗}(z) = \frac{∂P^{∗}}{∂u} (z, 1), where ∗ stands for = m, ≤ m or < m, the generating function F (z) = ∑_{n≥0} E(X_{n})z^{n} of the expectations is obtained as

F (z) = lim_{m→∞} F^{≤m}(z).

Performing some algebra one derives

F^{≤m}(z) = \frac{p}{q} \frac{z}{[[m]]^{2}} ∑_{i=1}^{m} \frac{q^{i}}{[[i]]}.

Now we let m tend to infinity and obtain

F (z) = \frac{p}{q} \frac{z}{(1 − z)^{2}} ∑_{i≥1} \frac{q^{i}}{[[i]]}.

The generating function H(z) of the second factorial moments can be obtained in the same way, although the computations are much more involved, see [9]. It is, however, not too complicated to find the coefficients in F (z):

E(X_{n}) = [z^{n}]F (z) = \frac{p}{q} ∑_{i≥1} [−Q^{i} + n + 1 + Q^{i} (1 − q^{i})^{n+1}]

= \frac{p}{q} ∑_{k=2}^{n+1} \binom{n + 1}{k}(−1)^{k} \frac{1}{Q^{k−1} − 1}

= (Q − 1)n( log_{Q} n + \frac{γ − 1}{L} − \frac{1}{2} + \frac{1}{L}δ_{1}(log_{Q} n)) + O(log n)

where γ is Euler’s constant and δ_{1}(x) = ∑_{k≠0} Γ(−1 − \frac{2kπi}{L})e^{2kπix} is a continuous periodic function of period 1 and mean zero.

3. Representations of numbers

3.1. Complex bases. There are representations of numbers that are perhaps not very well known, see e. g. [4]. For easier readability, we describe only a special case. Every Gaussian integer z ∈ ℤ[i] (of the form z = x + iy, with x, y ∈ ℤ) can be uniquely written as

∑_{k=0}^{n} ε_{k}(−2 + i)^{k}, with ε_{k} ∈ {0, 1, 2, 3, 4}.

The minimal polynomial of −2 + i is x^{2} + 4x + 5. As a consequence, 145 = 0, and there is the carry rule 5 = 1310. So if one wants to add 2041 and 4432, one takes 6473, uses the carry rule to get 19523 and the reduction rule to get 5023, and eventually 1310023. Or, one applies the reduction rule earlier, to get 5023 from 6473.

The digits can be computed as follows: Define

s_{k+1} = −4 ⌊\frac{s_{k}}{5} ⌋ − ⌊\frac{s_{k−1}}{5} ⌋ , k ≥ 0, s_{−1} = −5y, s_{0} = x + 2y,

then the kth digit is given by s_{k} mod 5.

Addition of 1 (or any fixed number) can be described by a transducer; digits are read from right to left, and eventually one of the two states marked by • are reached, where the convention is that all digits not read so far are simply copied. The states represent the possible carries.

The paper [4] deals also with the sum–of–digits function (defined in an obvious way), and fundamental regions. Each complex number has a representation in this system, of the form ∑_{k=−∞}^{n} ε_{k}(−2 + i)^{k}, which is in general unique; only “a few” numbers have 2 or even 3 representations. (This is akin to the base 10 representation, where 1 = 0.9999 . . ..)

[figure: 0|1; 1|2; 2|3; 3|4; 4|0; 0|4; 4|0; 0|4; 2|0; 3|1; 4|2; 0|2; 1|3; 2|4; 0|3; 1|4; 0|1; 1|2; 2|3; 3|4; 1|0; 2|1; 3|2; 4|3; 3|0; 4|1; 4|3; 3|2; 2|1; 1|0]

3.2. Redundant representations. The paper [20] is based on the Paul system, which is to the base 2, with digits in {−1, 0, 1}, and no two adjacent nonzero digits. This leads to unique representations, see [6]. However, it was later found out that this system was rediscovered many times. Probably the first appearance is in [22]. Let us write ¯1 = −1 for convenience. It was found out that the k-th digit is given by

a_{k}(n) = 1 ⟺ ⌊\frac{n}{2^{k+2}} + \frac{5}{6}⌋ − ⌊\frac{n}{2^{k+2}} + \frac{4}{6}⌋ = 1

and

a_{k}(n) = ¯1 ⟺ ⌊\frac{n}{2^{k+2}} + \frac{2}{6}⌋ − ⌊\frac{n}{2^{k+2}} + \frac{1}{6}⌋ = 1.

If the expressions on the right hand sides are not 1, they must be 0. Consequently we have the formula

n = ∑_{k≥0} (⌊\frac{n}{2^{k+2}} + \frac{5}{6}⌋ − ⌊\frac{n}{2^{k+2}} + \frac{4}{6}⌋ − ⌊\frac{n}{2^{k+2}} + \frac{2}{6}⌋ + ⌊\frac{n}{2^{k+2}} + \frac{1}{6}⌋) 2^{k}.

The key formula (see [11, 1.2.4, Ex. 38]) to manipulate such floor functions is

⌊x⌋ + ⌊x + \frac{1}{q}⌋ + ⋯ + ⌊x + \frac{q−1}{q}⌋ = ⌊qx⌋,  (3)

where q is an integer ≥ 1 and x a real number. We can now consider the binary representation of λn, for a natural number λ: The kth digit is given by

a_{k}(λn) = ∑_{i=0}^{2λ−1} ⌊\frac{n}{2^{k+1}} + \frac{i}{2λ}⌋ (−1)^{i−1};

this follows from

λn = ∑_{k≥0} 2^{k} (⌊\frac{λn}{2^{k}}⌋ − 2 ⌊\frac{λn}{2^{k+1}} ⌋)

and the formula (3). From this it follows that the representation investigated by Reitwiesner, Paul and others is simply obtained as follows: One computes the ordinary representations of 3n/2 and of n/2 and takes the bitwise difference! For example, 25 = (11001)_{2}, and \frac{3}{2} · 25 = 37.5 = (100101.1)_{2}, \frac{1}{2} ·25 = 12.5 = (1100.1)_{2}, and the bitwise difference is 10¯1001, which is the representation of 25. Clearly, the result is a representation of n in base 2 using digits −1, 0, 1. An obvious generalization is to consider n = (α + 1)n − αn and take the bitwise differences of the two representations. We analyzed only the case that α is either an integer or an integer divided by a power of 2 (a dyadic rational number). Here is one example:

a_{k}(4n) − a_{k}(3n) =

= ⌊\frac{n}{2^{k+1}} + \frac{7}{8}⌋ − ⌊\frac{n}{2^{k+1}} + \frac{5}{6}⌋ − ⌊\frac{n}{2^{k+1}} + \frac{6}{8}⌋ + ⌊\frac{n}{2^{k+1}} + \frac{4}{6}⌋

+ ⌊\frac{n}{2^{k+1}} + \frac{5}{8}⌋ − ⌊\frac{n}{2^{k+1}} + \frac{4}{8}⌋ − ⌊\frac{n}{2^{k+1}} + \frac{3}{6}⌋ + ⌊\frac{n}{2^{k+1}} + \frac{3}{8}⌋

+ ⌊\frac{n}{2^{k+1}} + \frac{2}{6}⌋ − ⌊\frac{n}{2^{k+1}} + \frac{2}{8}⌋ − ⌊\frac{n}{2^{k+1}} + \frac{1}{6}⌋ + ⌊\frac{n}{2^{k+1}} + \frac{1}{8}⌋ .

We discuss now a few syntactical properties. In [6] the rewriting rules

1¯1 ⟶ 01  ¯11 ⟶ 0¯1  011 ⟶ 10¯1  0¯1¯1 ⟶ ¯101

are presented, that can be (repeatedly) applied in any order to transform the standard binary representation of n ∈ ℕ into the “3n/2 − n/2” representation. We say “repeatedly” because of a problem with carries; the following example explains what happens:

01111 ⟶ 10¯111 ⟶ 100¯11 ⟶ 1000¯1.

A more “algorithmic” version is by the following transducer. It reads the binary representation of n from right to left (leading zeros must be added if needed). Of course, the output is also produced from right to left. The basic idea is to transform 01^{k} into 10^{k−1}¯1 for k ≥ 2. However, if the next group (to the left) starts immediately with 1, then we can’t output the leading 1; it is then a carry, belonging to the next group. To make sure that the transduction ends in the starting state (as it should), we can add two leading zeros (see Figure 1).

[figure: 0|0; 0|01; 1|ε; 0|01; 1|ε; 1|0¯1; 0|ε; 1|0; ⟶]

Figure 1. The binary → “3n/2 − n/2” transformer

When dealing with number systems, it is usually very instructive to see how the number 1 can be added. This can normally be done by an automaton. The word is processed from right to left. If no continuation is defined, the rest of the word is left unchanged. Again, possibly leading zeros are needed to lead to one of the accepting states to the right. The output is also recorded from right to left, usually replacing only a suffix of the word (representation of a number), when reaching one of the two states to the right.

[figure: 1|ε; 0|ε; 0|0; 1|¯1; ¯1|0; 0|01; ¯1|0¯1; ⟶]

Figure 2. Adding 1 in the “3n/2 − n/2” representation

Now let us consider a few properties of the system induced by writing n = 5n/4 − n/4: First, we describe the syntactically correct words. If B = 1+¯1+11(¯11)^{∗}(ε+¯1)+¯1¯1(1¯1)^{∗}(ε+1), then the possible representations are given by ε + (B000^{∗})^{∗}B0^{∗}. It is also possible to give a complete set of rewriting rules, but, again, an automaton (transducer) is more instructive: Input are natural numbers, written in ordinary binary notation. The computation ends in the starting state.

[figure: 0|0; 1|0; 1|ε; 0|ε; 0|001; 0|ε; 1|ε; 1|00¯1; 0|1; 1|¯1; ↗]

Figure 3. The binary → “1 = 5/4 − 1/4” transformer

3.3. Minimal representations. Motivated by algorithms on elliptic curves, in [7] representations of an integer n in base q ≥ 2 with arbitrary digits are again studied; set

R_{q}(n) := {ε = (ε_{0}, …, ε_{l}) | l ∈ ℕ, ε_{i} ∈ ℤ, n = ∑_{i=0}^{l} ε_{i}q^{i}}.

We define the cost of a representation ε ∈ R_{q}(n) as

c(ε) = c(ε_{0}, …, ε_{l}) := l + 1 + ∑_{i=0}^{l} |ε_{i}|

and look for representations of n with minimum cost. The modified cost function, which we will call relaxed costs, namely

c′(ε) = c′(ε_{0}, …, ε_{l}) := ∑_{i=0}^{l} |ε_{i}|

is more natural and easier to study.

We note that in general there is no unique minimal representation: Both (−1, 2) ∈ R_{3}(5) and (2, 1) ∈ R_{3}(5) are representations of 5 in base 3 with cost c(−1, 2) = c(2, 1) = 5. We will describe a special minimal representation (“reduced representation”), which is unique. In [7] there is a full set of conversion rules between the two minimal representations relative to the two types of costs. Although they have a language theoretic flavour, they cannot be included here.

In [7] we are able to derive an explicit formula for the digits of the reduced representation in the case of odd and even q, respectively. These formulæ are very useful for the computation of the frequencies of digits and the expected costs of the representations. Let q ≥ 3 be odd and n be a positive integer. Let

ε_{r} := b_{q}^{(r)}(2n) − b_{q}^{(r)}(n), r ≥ 0,

where b_{q}^{(r)}(n) is the r-th digit of the “usual” q-adic expansion of n, i. e.

b_{q}^{(r)}(n) = ⌊\frac{n}{q^{r}} ⌋ − q ⌊\frac{n}{q^{r+1}} ⌋ ,

and l := max{r ≥ 0 | ε_{r} ≠ 0}. Then ε = (ε_{0}, …, ε_{l}) is the relaxed reduced minimal representation. The formula for q ≥ 2 even is more complicated: For r ≥ 0 define

\begin{matrix}ε_{r} := ∑_{i=0}^{q/2−1}( ∑_{j=0}^{q/2−1} & ⌊\frac{n}{q^{r+2}} + \frac{1 + \frac{q}{2} + (q + 1)(iq + j)}{q^{2}(q + 1)}⌋ \\ −(q − 1) & ⌊\frac{n}{q^{r+2}} + \frac{\frac{q}{2} + (q + 1)(iq + q/2)}{q^{2}(q + 1)}⌋ \\ + ∑_{j=q/2+1}^{q−1} & ⌊\frac{n}{q^{r+2}} + \frac{\frac{q}{2} + (q + 1)(iq + j)}{q^{2}(q + 1)}⌋) \\ + ∑_{i=q/2}^{q−1}( ∑_{j=0}^{q/2−2} & ⌊\frac{n}{q^{r+2}} + \frac{1 + \frac{q}{2} + (q + 1)(iq + j)}{q^{2}(q + 1)}⌋ \\ −(q − 1) & ⌊\frac{n}{q^{r+2}} + \frac{1 + \frac{q}{2} + (q + 1)(iq + q/2 − 1)}{q^{2}(q + 1)}⌋ \\ + ∑_{j=q/2}^{q−1} & ⌊\frac{n}{q^{r+2}} + \frac{\frac{q}{2} + (q + 1)(iq + j)}{q^{2}(q + 1)}⌋). \end{matrix}

Let l := max{r ≥ 0 | ε_{r} ≠ 0}. Then ε = (ε_{0}, …, ε_{l}) ∈ R_{q}(n) is the relaxed reduced minimal representation. We make that explicit for q = 2:

ε_{r} = ⌊\frac{n}{2^{r+2}} + \frac{5}{6}⌋ − ⌊\frac{n}{2^{r+2}} + \frac{4}{6}⌋ − ⌊\frac{n}{2^{r+2}} + \frac{2}{6}⌋ + ⌊\frac{n}{2^{r+2}} + \frac{1}{6}⌋ ,

so we see that it is the representation studied by Reitwiesner and others.

It is also possible to formulate a simple algorithm to create the representation of an integer m: Consider a ≡ m mod q, and take a representative in the interval −q/2 ≤ a ≤ q/2. In case, a decision has to be made whether to take a = −q/2 or a = q/2. It is based on the fractional part of m/q^{2}: if {m/q^{2}} < 1/2 then take a = q/2. Continue with m ← (m−a)/q. This rule makes the system balanced.

We are also interested to count how often a given digit i occurs in the relaxed reduced expansion among the numbers 1, …, n; call that #_{i}(n). In the case q odd, the reduced representation is actually the (q, d) representation, with d = −\frac{q−1}{2}, and digits d, d + 1, …, d + q − 1. (For example, 32¯101 with base 4 represents 3 4^{4} + 2 4^{3} − 4^{2} + 1 = 881.) Digit counting in this representation is well known, see [8]. Every digit occurs with the same frequency \frac{1}{q}, and

#_{i}(n) = \frac{1}{q}n log_{q} n + O(n).

Actually, more is known about the error term. It can be made fully explicit and is basically given by n times a periodic function in log_{q} n. From that we get the average value of c′(ε). It is

(\frac{q}{4} − \frac{1}{4q} ) log_{q} n + O(1).

In the instance q even, things are a bit more complicated; digit 0 occurs with frequency \frac{q+2}{q(q+1)}, digits ±1, …, ±\frac{q}{2} − 1 with frequency \frac{1}{q}, digits ±\frac{q}{2} each with frequency \frac{1}{2(q+1)}. So we see that digit 0 appears a bit more often than the other digits, and the digits ±\frac{q}{2} (combined) appear a bit less often than the other digits. This leads to

#_{0}(n) = \frac{q + 2}{q(q + 1)}n log_{q} n + O(n),
#_{i}(n) = \frac{1}{q}n log_{q} n + O(n),  for i = ±1, …, ±\frac{q}{2} − 1,
#_{i}(n) = \frac{1}{2(q + 1)}n log_{q} n + O(n),  for i = ±\frac{q}{2}.

Summing this, (multiplied by |i|), over all possible digits i, we get the average value of ∑ |ε_{i}|:

(\frac{q}{4} − \frac{1}{2(q + 1)}) log_{q} n + O(1).

3.4. Representations in the sense of Morain and Olivos. The representation of n in base 2, with digits −1, 0, 1, where no two adjacent nonzero digits are adjacent, has the lowest number of nonzero digits (roughly speaking, the probability that a random digit is different from zero, is \frac{1}{3}). As we have seen, it can be obtained by repeated applications of replacement rules. Morain and Olivos in [14], see also [23], consider the simpler version, where all occurrences 1^{a} (a ≥ 2, and the block is rendered by zeros) are simultaneously replaced by 10^{a−1}¯1. For example, 11011 is transformed into 10¯110¯1. This Morain/Olivos representation of natural numbers does not take care of carries (but they also consider them, in a second algorithm). However, it is also possible to give explicit formulæ for the digits:

a_{0}(n) = ⌊\frac{n}{4} + \frac{3}{4}⌋ − ⌊\frac{n}{4} + \frac{2}{4}⌋ − ⌊\frac{n}{4} + \frac{1}{4}⌋ + ⌊\frac{n}{4} + \frac{0}{4}⌋ ,

a_{1}(n) = ⌊\frac{n}{8} + \frac{6}{8}⌋ − ⌊\frac{n}{8} + \frac{5}{8}⌋ − ⌊\frac{n}{8} + \frac{2}{8}⌋ + ⌊\frac{n}{8} + \frac{1}{8}⌋ ,

and for k ≥ 2

a_{k}(n) = ⌊\frac{n}{2^{k+2}} + \frac{13}{16}⌋ − ⌊\frac{n}{2^{k+2}} + \frac{10}{16}⌋

+ ⌊\frac{n}{2^{k+2}} + \frac{5}{16}⌋ − 2 ⌊\frac{n}{2^{k+2}} + \frac{4}{16}⌋ + ⌊\frac{n}{2^{k+2}} + \frac{2}{16}⌋ .

A rigorous proof of that is probably unpleasant but doable as in [7].

From this it follows that the number of nonzero digits σ(n) in the Morain/Olivos representation is given by

σ(n) = ⌊\frac{n}{4} + \frac{3}{4}⌋ − ⌊\frac{n}{4} + \frac{2}{4}⌋ + ⌊\frac{n}{4} + \frac{1}{4}⌋ − ⌊\frac{n}{4} + \frac{0}{4}⌋

+ ⌊\frac{n}{8} + \frac{6}{8}⌋ − ⌊\frac{n}{8} + \frac{5}{8}⌋ + ⌊\frac{n}{8} + \frac{2}{8}⌋ − ⌊\frac{n}{8} + \frac{1}{8}⌋

+ ∑_{k≥2} \{ ⌊\frac{n}{2^{k+2}} + \frac{13}{16}⌋ − ⌊\frac{n}{2^{k+2}} + \frac{10}{16}⌋ + ⌊\frac{n}{2^{k+2}} + \frac{5}{16}⌋ − ⌊\frac{n}{2^{k+2}} + \frac{2}{16}⌋ \},

and therefore

∑_{n<N} σ(n) = ⌊\frac{N}{2} ⌋ + ⌊\frac{N + 1}{4}⌋

+ ∑_{n<N} ∑_{k=2}^{l+2} \{ ⌊\frac{n}{2^{k+2}} + \frac{13}{16}⌋ − ⌊\frac{n}{2^{k+2}} + \frac{10}{16}⌋ + ⌊\frac{n}{2^{k+2}} + \frac{5}{16}⌋ − ⌊\frac{n}{2^{k+2}} + \frac{2}{16}⌋ \},

with l = log_{2} N. Now we use Delange’s approach [3] to develop that further (this leads to a more elementary computation than Thuswaldner’s in [23]). Define

g(x) = ∫_{0}^{x} \{ ⌊t + \frac{13}{16}⌋ − ⌊t + \frac{10}{16}⌋ + ⌊t + \frac{5}{16}⌋ − ⌊t + \frac{2}{16}⌋ − \frac{3}{8}\}dt,

then

∑_{n<N} σ(n) = \frac{3N}{4} + O(1) + \frac{3}{8}(⌊l⌋ + 1) + ∑_{k=2}^{⌊l⌋+2} 2^{k+2}g(\frac{N}{2^{k+2}} )

= \frac{3N}{4} + O(1) + \frac{3}{8} log_{2} N + \frac{3}{8}(1 − \{log_{2} N\})

+ N2^{2−{log_{2} N}} ∑_{r≥0} 2^{−r}g(2^{{log_{2} N}−2+r}).

Defining

H(x) = \frac{3}{4} + \frac{3}{8}(1 − \{x\}) + 2^{2−\{x\}} ∑_{r≥0} 2^{−r}g(2^{\{x\}−2+r}),

which is periodic with period 1, we find that the average of σ(n) is given by

\frac{1}{N} ∑_{n<N} σ(n) = \frac{3}{8} log_{2} N + H(log_{2} N) + O(\frac{1}{N} ).

One can compute the Fourier coefficients of H(x), which we omit because of lack of space. The formula should be compared with the ∼ \frac{1}{3} log_{2} N + F (log_{2} N) formula in the Reitwiesner instance. So the more sophisticated algorithm brings the constant down from \frac{3}{8} to \frac{1}{3}.

References

[1] L. Carlitz. Permutations with prescribed pattern. Math. Nachr., 58:31–53, 1973.

[2] L. Carlitz. A combinatorial property of q–Eulerian numbers. American Mathematical Monthly, 82:51–54, 1975.

[3] H. Delange. Sur la fonction sommatoire de la fonction somme des chiffres. Enseignement Mathématique, 21:31–47, 1975.

[4] P. Grabner, P. Kirschenhofer, and H. Prodinger. The sum–of–digits function for complex bases. J. London Math. Soc., 57:20–40, 1998.

[5] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics (Second Edition). Addison Wesley, 1994.

[6] U. Güntzer and M. Paul. Jump interpolation search trees and symmetric binary numbers. Information Processing Letters, 26:193–204, 1987/88.

[7] C. Heuberger and H. Prodinger. On minimal expansions in redundant number systems: Algorithms and quantitative analysis. Computing, 2001.

[8] P. Kirschenhofer and H. Prodinger. Subblock occurrences in positional number systems and Gray code representation. Journal of Information and Optimization Sciences, 5:29–42, 1984.

[9] P. Kirschenhofer and H. Prodinger. The path length of random skip lists. Acta Informatica, 31:775–792, 1994.

[10] A. Knopfmacher and H. Prodinger. Combinatorics of geometrically distributed random variables: Value and position of the rth left-to-right maximum. Discrete Mathematics, 226:255–267, 2001.

[11] D. E. Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms. Addison-Wesley, 1968. Third edition, 1997.

[12] D. E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 1973. Second edition, 1998.

[13] G. Louchard and H. Prodinger. Ascending runs of sequences of geometrically distributed random variables: a probabilistic analysis. submitted, 2001.

[14] F. Morain and J. Olivos. Speeding up the computations on an elliptic curve using addition-subtraction chains. RAIRO Inform. Théor. Appl., 24(6):531–543, 1990.

[15] H. Prodinger. Combinatorial problems of geometrically distributed random variables and applications in computer science. In V. Strehl and R. König, editors, Publications de l’IRMA (Straßbourg) (=Séminaire Lotharingien de Combinatoire), volume 30, pages 87–95, 1993.

[16] H. Prodinger. Combinatorics of geometrically distributed random variables: Leftto-right maxima. Discrete Mathematics, 153:253–270, 1996.

[17] H. Prodinger. Combinatorics of geometrically distributed random variables: Inversions and a parameter of Knuth. Annals of Combinatorics, to appear, 2001.

[18] H. Prodinger. Combinatorics of geometrically distributed random variables: Lengths of ascending runs. LATIN2000, Lecture Notes in Computer Science 1776, pages 473–482, 2000.

[19] H. Prodinger. Combinatorics of geometrically distributed random variables: New q–tangent and q–secant numbers. International Journal of Mathematical Sciences, 24:825–838, 2000.

[20] H. Prodinger. On binary representations of integers with digits −1, 0, 1. Integers, pages A8, 14 pp. (electronic), 2000.

[21] H. Prodinger. Combinatorics of geometrically distributed random variables: Value and position of large left-to-right maxima, submitted, 2000.

[22] G. Reitwiesner. Binary arithmetic. Vol. 1 of Advances in Computers, Academic Press, pages 231–308, 1960.

[23] J. Thuswaldner. Summatory functions of digital sums occurring in Cryptography. Periodica Math. Hungarica, 38:111–130, 1999.

[24] H. Wilf. On the outstanding elements of permutations, 1995,

http://www.cis.upenn.edu/∼wilf.

The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P.O. Wits, 2050 Johannesburg, South Africa.

E-mail address: helmut@gauss.cam.wits.ac.za
WWW–address: http://www.wits.ac.za/helmut/index.htm