INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A03

PERMUTATIONS OF THE NATURAL NUMBERS WITH PRESCRIBED DIFFERENCE MULTISETS

Peter Hegarty

Chalmers University of Technology, 41296 Göteborg, Sweden

                          hegarty@math.chalmers.se

Urban Larsson

Chalmers University of Technology, 41296 Göteborg, Sweden

                        md0larur@student.chalmers.se

Received: 5/27/05, Revised: 1/16/06, Accepted: 2/4/06, Published: 2/13/06

Abstract

We study permutations π of the natural numbers for which the numbers π(n) are chosen greedily under the restriction that the differences π(n)−n belong to a given (multi)subset M of Z for all n ∈ S, a given subset of N. Various combinatorial properties of such permutations (for quite general M and S) are exhibited and others conjectured. Our results generalise to a large extent known facts in the case M = Z, S = N, where the permutation π arises in the study of the game of Wythoff Nim.

1. Introduction

Consider the permutation π = π_{g} of the natural numbers defined inductively as follows:

(i) π(1) = 1,

(ii) for each n > 1, π(n) := t, where t is the least natural number not already appearing among π(1), ..., π(n − 1) and such that t − n ≠ π(i) − i, for any 1 ≤ i < n.

Informally, we say that π chooses numbers greedily under the restriction that differences π(n) − n may not be repeated. The permutation π exhibits a rich variety of beautiful properties, which may be said to be well-known. It is an involution of N and its asymptotics are given by

lim_{n∈A} \frac{π(n)}{n} = ϕ = \frac{1 + \sqrt{5}}{2},

the golden ratio, where A = {n : π(n) ≥ n}. In the literature it is usually studied in one of several different contexts, for example in the game of Wythoff Nim, in connection with Beatty sequences and with so-called Stolarsky interspersion arrays. This material is reviewed below.

Our idea for this paper was to study permutations π = π_{g}^{M,S} of N, defined by a greedy choice procedure, under the restriction that the differences π(n)−n belong to some assigned, but otherwise arbitrary, (multi)subset M of Z, whenever n ∈ S, some assigned subset of N. Hence the above discussion relates to the case S = N and M = Z. We were motivated by the observation that some of the attractive properties of πZ,N_{g} can be naturally generalised, and the purpose of the paper (and perhaps others to follow) is to carry out this generalisation as far as possible.

An outline of our results will be presented in the next section. First we wish to recall in some more detail, for the sake of the uninitiated reader, the properties of πZ,N_{g} referred to above. An exposition of this material, including a detailed list of references, can be found in, for example, [9]. To ease notation, and to emphasise the connection with the game of Wythoff Nim, we henceforth denote our permutation as π_{W}.

Wythoff Nim (a.k.a. Corner the Queen) The positions of this 2-person impartial game, first studied by Wythoff [12], consist of pairs (k, l) of non-negative integers. From any given such position, the allowed moves are

Type I: (k, l) → (k′, l) for any 0 ≤ k′ < k.

Type II: (k, l) → (k, l′) for any 0 ≤ l′ < l.

Type III: (k, l) → (k − s, l − s) for any 0 ≤ s ≤ min{k, l}.

It is not dificult to see that the P-positions for this game, that is those starting positions from which the previous player has a winning strategy, are precisely the pairs (n−1, π_{W} (n)− 1), for all n ∈ N.

Beatty Sequences Let r, s be any positive irrational numbers such that

\frac{1}{r} + \frac{1}{s} = 1.  (1)

Beatty discovered [1] that the sets X = {⌊nr⌋ : n ∈ N}, Y = {⌊ns⌋ : n ∈ N} form a partition of N. Now choose r = ϕ, s = ϕ + 1 = ϕ^{2}. One readily checks that (1) is satisfied. It is well-known that π_{W} is completely described by

π_{W} (1) = 1, π_{W} = π_{W}^{−1}, π_{W} (⌈nr⌉) = ⌈ns⌉, ∀ n ≥ 1.  (2)

The point is that this gives a much more precise description of π_{W} than just knowing its asymptotic behaviour.

Stolarsky interspersion arrays An array A = (a_{ij})_{i,j>0} of natural numbers is called an interspersion array if the following properties are satisfied:

(i) each natural number appears exactly once in the array, (ii) each row of the array is an infinite increasing sequence, (iii) each column is an increasing sequence (the number of rows may or may not be finite), (iv) for any i, j, p, q > 0 with i ≠ j, if a_{i,p} < a_{j,q} < a_{i,p+1}, then a_{i,p+1} < a_{j,q+1} < a_{i,p+2}.

A Stolarsky interspersion satisfies the following additional property:

(v) every row of the array is a Fibonacci sequence, i.e.: for any i ≥ 1 and j ≥ 3, we have that

a_{i,j} = a_{i,j−1} + a_{i,j−2}.  (3)

(Note that such an interspersion array must necessarily have infinitely many rows). There are two Stolarsky arrays naturally associated with the permutation π_{W}. The first is called the Wythoff array or the Zeckendorff array. Its first row is the ‘usual’ Fibonacci sequence determined by a_{1,1} = 1, a_{1,2} = 2. The remaining rows are determined inductively as follows:

(i) a_{i,1} is the least natural number not already appearing in the preceeding rows (ii) a_{i,2} is the so-called Zeckendorff right-shift Z of a_{i,1}. That is, a_{i,1} is written in terms of the base for N provided by the first row and then each basis element is replaced by its successor. So, for example, a_{2,1} = 4 = 1 + 3, in terms of the Fibonacci base, so that a_{2,2} = Z(1) + Z(3) = 2 + 5 = 7. (iii) for every j ≥ 3, the relation (3) is satisfied.

It was shown by Kimberling [7] that the pairs (a_{i,2t−1}, a_{i,2t}), for all i, t > 0, in the Wythoff array, constitute the complete set of P-positions for Wythoff Nim.

The second array, known in the literature as the dual Wythoff array, is constructed in a very similar manner to the first. The only difference is in the choice of a_{i,2}, for each i > 1. Since a_{i,1} is the least positive integer not already appearing in the preceeding rows, there is a unique pair (k, j), with k < i, such that a_{i,1} = a_{k,j} + 1. In the dual array, we set a_{i,2} := a_{k,j+1} + 1. Here, of course, the fact that the dual array is an interspersion is already non-trivial, since one needs to prove that, for each i > 1, a_{i,2} has not yet appeared in the preceeding rows. This fact is contained in the following well-known characterisation (see [6], section 5) of the permutation π_{W}:

π_{W} (1) = 1, π_{W} = π_{W}^{−1}, π_{W} (a_{1,2t}) = a_{1,2t+1} ∀ t ≥ 1,
π_{W} (a_{i,2t−1}) = a_{i,2t} ∀ i ≥ 2, t ≥ 1.

We close this introduction by observing that in [2] Fraenkel studied the following nice generalisation of Wythoff Nim. Let m be a natural number. The game of m-Wythoff Nim (our terminology) is played according to the same rules as ordinary Wythoff Nim (the case m = 1) except that we expand the set of allowed moves of Type III as follows: from a position (k, l) one can move to any position (k − s, l − t) such that 0 ≤ s ≤ k, 0 ≤ t ≤ l and |s − t| < m.

Let π_{W_{m}} = π_{g}^{mZ,N} be the permutation of N constructed by the same greedy choice procedure as π_{W}, but with the restriction that π_{W_{m}}(i) − i must be a multiple of m for all i ∈ N. It is easy to see that the P-positions for m-Wythoff Nim are just the pairs (n − 1, π_{W_{m}}(n) − 1), for all n ∈ N. Fraenkel showed that these positions can be written in terms of Beatty sequences. If we choose

r = r_{m} := \frac{2 − m + \sqrt{m^{2} + 4}}{2}, s = s_{m} := r_{m} + m,  (4)

then (2) holds, with π_{W} replaced by π_{W_{m}}. In particular, the asymptotic behaviour of π_{W_{m}} is given by

lim_{n∈A} \frac{π_{W_{m}}(n)}{n} = \frac{s_{m}}{r_{m}} = \frac{m + \sqrt{m^{2} + 4}}{2},

which is the positive root of the equation x^{2} − mx − 1 = 0, where A = {n : π_{W_{m}}(n) ≥ n}. The natural generalisations of the Wythoff and dual Wythoff interspersion arrays are also implicitly contained in Fraenkel’s paper.

Finally, it is worth noting that a good deal of work has been done on various wide-ranging generalisations of Wythoff Nim: see, for example, [4] and [11] for some recent material. One application of our results, to be discussed in the next section, will involve an apparently novel generalisation of the game.

2. Notation, terminology and summary of results

The following standard notations will be adhered to throughout the paper:

Given two sequences (f_{n})_{1}^{∞} and (g_{n})_{1}^{∞} of positive real numbers, we write f_{n} = Θ(g_{n}) if there exist positive constants c_{1} < c_{2} such that c_{1} < f_{n}/g_{n} < c_{2} for all n. We write f_{n} ∼ g_{n} if f_{n}/g_{n} → 1 as n → ∞, f_{n} ≳ g_{n} if lim inf f_{n}/g_{n} ≥ 1 and f_{n} = o(g_{n}) if f_{n}/g_{n} → 0.

We now specify our principal notations and terminology.

For each n ∈ Z, let ζ_{n} ∈ N_{0} ∪ {∞}. The sequence M := (ζ_{n})_{n=−∞}^{∞} is called a multisubset of Z, or simply a multiset. We think of ζ_{n} as the number of occurrences of the integer n in M. If ∑_{n≥0} ζ_{n} = ∞ we say that M is injective. If ∑_{n≤0} ζ_{n} = ∞, we say that M is surjective. A multiset which is both injective and surjective will be called bijective. If ζ_{n} = ζ_{−n} for all integers n, then M is said to be symmetric. The asymptotic density of a multiset M is defined by

d(M) := lim_{n→∞} \frac{1}{2n + 1} ( ∑_{k=−n}^{n} ζ_{k}) ,

whenever this limit exists. Observe that d(M) = ∞ whenever ζ_{n} = ∞ for some n. Hence, this concept is only really interesting if ζ_{n} ∈ N_{0} for all n. Such a multiset is called finitary.

M is said to be a greedy multiset if either M is finitary or the following holds: there is at most one non-negative n and at most one non-positive n for which ζ_{n} = ∞. If n ≥ 0 and ζ_{n} = ∞ then ζ_{n′} = 0 for all n′ > n. If n ≤ 0 and ζ_{n} = ∞, then ζ_{n′} = 0 for all n′ < n.

The positive (resp. negative) part of a multiset M, denoted M_{+} (resp. M_{−}), is the multiset (ζ′_{n}) such that ζ′_{n} = 0 for all n < 0 (resp. n ≥ 0) and ζ′_{n} = ζ_{n} for all n ≥ 0 (resp. n < 0). Finally, let M_{1} = (ζ_{1,n}) and M_{2} = (ζ_{2,n}) be any two multisets. We write M_{1} ≤ M_{2} if ζ_{1,n} ≤ ζ_{2,n} for all n ∈ Z.

Let S be a subset of N and f : N → N be any function. For n ∈ N we denote d(n) = d_{f}(n) := f(n) − n. The difference multiset of f with respect to S, denoted D_{f,S}, is defined by D_{f,S} = (ζ_{n})_{−∞}^{∞} where

ζ_{n} = #{k ∈ S : d(k) = n}.

If S = N we drop the second subscript and write simply D_{f}.

Suppose S = N. If f is an injective function, then D_{f} must be an injective multiset. For otherwise, d_{f}(n) < 0 for all but finitely many n. Thus there exists an integer n_{0} ≥ 1 such that d_{f}(n) < 0 for all n ≥ n_{0}. Let n_{0} ≤ T := max{f(n) : 1 ≤ n < n_{0}}. Then f(n) ≤ T for all 1 ≤ n ≤ T + 1, contradicting injectivity of f. By a similar argument, if f is surjective, then so is D_{f}. Hence if f is a permutation, then D_{f} is bijective. For the remainder of this paper, all multisets are assumed to be bijective.

Let M = (ζ_{n}) and S be given. An injective mapping π_{g} = π_{g}^{M,S} : N → N such that D_{π_{g},S} ≤ M can be constructed by means of a ‘greedy algorithm’: for each n ∈ N, π_{g}(n) is defined inductively to be the least positive integer t not equal to π_{g}(k) for any k < n and, if n ∈ S, satisfying the additional condition that #{k < n : k ∈ S and d_{π_{g}}(k) = t − n} < ζ_{t−n}.

It is easy to see that π_{g} is also surjective (since M is), hence a permutation of N.

We have an associated partition of the natural numbers N = A ⊔ B ⊔ C where

A = A_{M,S} := {n ∈ S : d_{π_{g}}(n) ≥ 0}, B = B_{M,S} := {n ∈ S : d_{π_{g}}(n) < 0},
C = C_{S} := N\S.

We also fix the following notation: for each k ∈ Z, n ≥ 1, set

Ξ_{n,k} = Ξ_{n,k,M,S} := #{j : 1 ≤ j ≤ n, j ∈ S and d_{π_{g}}(j) = k}.

Note that the permutation π_{W_{m}} discussed in Section 1 corresponds to the pair S = N and M = mZ, i.e.: ζ_{n} = 1 if m|n and ζ_{n} = 0 otherwise.

The rest of the paper is organised as follows:

In Section 3 we begin by verifying some very general properties of these ‘greedy difference’ permutations (Proposition 3.1). Some are valid for any M and S, others only for certain S, including the most natural case S = N. In particular, when S = N then π_{g} always satisfies a certain ‘uniqueness property’ not immediately obvious from its definition, and if furthermore M is symmetric, then π_{g} is an involution of N. The main result of this section (Theorem 3.3) shows how the asymptotics of π_{g} can always be computed provided that M and S are ‘sufficiently nice’: more precisely, provided S and both the positive and negative parts of M have an asymptotic density. We also prove a converse result in the case of S = N and symmetric M (Proposition 3.4).

In the next two sections, it is assumed that S = N. In Section 4 we illustrate that, for any symmetric M, there are two natural ways to arrange the pairs {n, π_{g}(n)} in an interspersion array. These generalise the Wythoff array and its dual respectively.

The reader who seeks further motivation for our investigations, before ploughing into the rather technical material in Sections 3 and 4, might profitably read Section 5 first. In this section, we further study the multisets which we denote by M_{m,p}, i.e.: ζ_{n} = p if m|p and ζ_{n} = 0 otherwise. This thus generalises the material in Fraenkel’s paper [2] (the case p = 1). We describe a beautifully simple generalisation of the Wythoff Nim game for which the P-positions are just the pairs (n − 1, π_{g}^{M_{m,p},N}(n) − 1). The idea is to introduce a type of blocking manoeuvre, or so-called Muller twist, into the game. Our game does not seem to be studied in the existing literature either on combinatorial games with Muller twists (see [10], for example), or on Wythoff Nim (see [4], [11]).

This section is closed with a conjecture which suggests a close relationship between the values π_{g}^{M_{m,p},N}(n) and certain Beatty sequences, which partly generalises the known results when p = 1. It is this aspect of the classical framework which seems to be the most difficult to generalise, which is not surprising since it concerns a very precise ‘algebraic’ description of the permutations π_{g}^{M,N}, which is certainly not going to be possible for very general M. Neverthless, in some cases like M = M_{m,p}, there is numerical evidence to suggest a very close relationship with Beatty sequences.

In Section 6, we return to the setting of more general S. We prove a quite technical theorem (Theorem 6.1) about the permutation π_{g}^{Z,2N}, which establishes a very close relationship between it and a certain Beatty sequence. We close the paper with a wide-ranging conjecture which further generalises that in Section 5.

3. General properties and asymptotics

Proposition 3.1 Let M be a bijective multisubset of Z, S a subset of N, π := π_{g}^{M,S}, D := D_{π,S}, A := A_{M,S}, B := B_{M,S}, C := C_{S}.

(i) For any M and S, π satisfies the following properties:

U1: The difference function d is non-decreasing on A and non-increasing on B,

U2: π is strictly increasing on each of A and B ∪ C.

(ii) D is a greedy multiset and, if S is infinite, then D = M if and only if M is greedy.

Now suppose S = N (hence C is the empty set). Then

(iii) π is the unique permutation of N with difference multiset D which satisfies U1 and U2.

(iv) π is an involution, i.e.: π = π^{−1}, if and only if D is symmetric. If M is symmetric and greedy, then π is the unique involution on N with difference multiset M, which satisfies U1 and U2.

Proof: Fix M and S. We begin by establishing the following stronger form of property U1:

U: Let n ≥ 1. Let Δ_{n} := min{k : k ≥ 0 and Ξ_{n−1,k} < ζ_{k}}, δ_{n} := max{k : k ≤ 0 and Ξ_{n−1,k} < ζ_{k}}. Then d(n) ∈ {δ_{n}, Δ_{n}} if n ∈ S.

We can establish U by induction on n. It holds trivially for n = 1, so suppose it holds for 1 ≤ n′ < n. If n ∈ C, there is nothing to prove. If n ∈ A, then U implies that no number ≥ n + Δ_{n} has yet been chosen by π. But since π chooses greedily, it is thus clear that π(n) = n + Δ_{n}, so that U continues to hold in this case.

Suppose n ∈ B. Now U guarantees that π(n) ≤ n + δ_{n}. It suffices to establish a contradiction to the assumption that π(n) < n+δ_{n}. Let k = k_{1} < n be such that π(n)−k_{1} = δ_{n}. If k_{1} ∈ S then U implies that π(k_{1}) > π(n), contradicting the definition of π. So k_{1} ∈ C and π(k_{1}) < k_{1} + δ_{n}. Let k_{2} < k_{1} be such that π(k_{2}) − k_{1} = δ_{n}. Run through the same argument again to obtain the desired contradiction unless k_{2} ∈ C and π(k_{2}) < k_{2} + δ_{n}. But now we may iterate the same argument indefinitely and thereby obtain an infinite decreasing sequence of elements of C, which is ridiculous.

Thus we have established U, from which U1 follows immediately, plus the fact that π is increasing on A. Suppose m, n ∈ B ∪ C, with m < n and π(m) > π(n). Then m ∈ B. Let z = z_{1} := m − [π(m) − π(n)]. If z_{1} ∈ B then, since m ∈ B, U implies that π(z_{1}) > π(n), contradicting the definition of π. So z_{1} ∈ C and hence π(z_{1}) < π(n). We set z_{2} := z_{1} −[π(n)−π(z_{1})] and run through the same argument to obtain a contradiction unless z_{2} ∈ C and π(z_{2}) < π(z_{1}). Iterating indefinitely we obtain, as above, an infinite decreasing sequence of elements of C, which is absurd. Thus we’ve established U2 and hence part (i) of the proposition. Part (ii) follows easily from U and previous arguments.

Turning to (iii), let τ be a permutation of N with D_{τ} = D_{π} which satisfies U1 and U2. Suppose π ≠ τ and let n_{0} be the smallest integer such that π(n_{0}) ≠ τ(n_{0}). First suppose π(n_{0}) < n_{0}. Since τ is surjective, there exists n_{1} > n_{0} such that τ(n_{1}) = π(n_{0}). Thus d_{τ}(n_{1}) < d_{π}(n_{0}). But since D_{τ} = D_{π} and τ satisfies U1, this implies the existence of some n_{2} ∈ (n_{0}, n_{1}) such that d_{τ}(n_{2}) = d_{π}(n_{0}). But then τ(n_{2}) > τ(n_{1}), contradicting the assumption that τ satisfies U2.

Finally, suppose π(n_{0}) > n_{0}. Then U1 forces τ(n_{0}) < n_{0}. But then, by U1 again, we have a contradiction, since a greedy choice algorithm would rather have chosen τ(n_{0}) in position n_{0}.

Finally, it is trivial that if π is an involution, then D is symmetric. The rest of (iv) follows from (ii) and (iii) since, if π satisfies U1 and U2, then so does π^{−1}.

Remark 1 Suppose S = N. For many multisets M, one can strengthen part (iii) of Proposition 3.1 to the following statement:

π is the unique permutation of N with difference multiset D which satisfies U1; in particular, U1 implies U2.

Indeed, it is easily seen from the proof of (iii) that this is true for any multiset M = (ζ_{n}) satisfying: if ζ_{n} ≠ 0 and n < m < 0 then ζ_{m} ≠ 0. A full classification of those M for which this stronger statement of (iii) holds seems a rather messy exercise, however.

Remark 2 We now give an example to illustrate the more significant, if rather simple, fact that parts (iii) and (iv) of Proposition 3.1 do not hold for general S, that is, π_{g} will in general neither be the unique permutation satisfying properties U1 and U2, nor an involution when M is symmetric. We leave aside the issue of determining for which S such a generalisation does hold.

Example: Let M = Z, S = 2N. The first few values of π_{g} are given by

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ π_{g}(n) & 1 & 2 & 3 & 5 & 4 & 8 & 6 & 7 & 9 & 13 & 10 \\ d(n) & 0 & 0 & 0 & 1 & -1 & 2 & -1 & -1 & 0 & 3 & -1 \end{matrix}

from which we immediately see that π_{g} is not an involution. In addition, if σ is the permutation of N which begins

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ σ(n) & 1 & 2 & 3 & 5 & 4 & 8 & 6 & 11 & 7 & 9 & 10 \\ d(n) & 0 & 0 & 0 & 1 & -1 & 2 & -1 & 3 & -2 & -1 & -1 \end{matrix}

and then continues to choose greedily for all n ≥ 12, then σ will also satisfy properties U1 and U2.

Next we turn to asymptotics. Let

L := lim sup_{n∈N} \frac{π(n)}{n} = lim sup_{n∈A} \frac{π(n)}{n},

l := lim inf_{n∈N} \frac{π(n)}{n} = lim inf_{n∈B∪C} \frac{π(n)}{n}.

We seek sufficient conditions for both L and l to be finite limits, over n ∈ A and n ∈ B ∪ C

respectively. First we need a technical lemma. For T = ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ GL_{2}(C) we denote by μ_{T} : C ∪ \{∞\} → C ∪ \{∞\} the Möbius transformation μ_{T} (z) := T z := \frac{az+b}{cz+d}. Recall that T is said to be hyperbolic if the fixed-point equation T z = z has two distinct real solutions.

Lemma 3.2 Let r, s ∈ R_{>0}, δ ∈ (0, 1] and set

a = a(δ, r, s) := (1 + \frac{1}{rs} − \frac{1}{s}) + (1 − \frac{1}{r}) (\frac{1 − δ}{s} ) = 1 − \frac{δ}{s} (1 − \frac{1}{r}) ,

b = b(δ, s) := \frac{1}{s} − \frac{1 − δ}{s} = \frac{δ}{s},

c = c(r, s) := \frac{1}{r} + \frac{1}{rs} − \frac{1}{s},

d = d(s) := 1 + \frac{1}{s}.

Let T = T_{δ,r,s} := ( \begin{matrix}a & b \\ c & d \end{matrix} ). Then for any choice of r, s and δ, the following hold:

(i) det(T) = 1 − \frac{1−δ}{s}. T is hyperbolic with a unique fixed point α = α_{T} in [0, δ] which is neither 0 nor δ. (ii) Let (x_{n})_{n=1}^{∞} be a sequence of positive real numbers such that for any ϵ > 0, x_{n} ∈ (0, δ +ϵ) for all sufficiently large n, and suppose the x_{n} satisfy a recurrence

x_{n+1} = T_{n}x_{n}, n ≥ 1,

where T_{n} = ( \begin{matrix}a_{n} & b_{n} \\ c_{n} & d_{n} \end{matrix} ) ∈ GL_{2}(R) is such that c_{n} = c, d_{n} = d for all n and a_{n} → a, b_{n} → b

as n → ∞. Then x_{n} → α.

Proof: That det(T) = 1 − \frac{1−δ}{s} is easily verified. Next,

(tr T)^{2} − 4(det T) = (\frac{δ − 1}{s})^{2} + \frac{2δ(1 − δ)}{rs^{2}} + (2 + \frac{δ}{rs})^{2} − 4 > 0,

which proves that T is hyperbolic. Finally, it is a tedious but straightforward exercise in high-school algebra to verify that exactly one fixed point lies in [0, δ] and is neither 0 nor δ.

(ii) This is probably a simple exercise for anyone familiar with the (elementary) theory of iteration of Möbius transformations, but we give a proof for the sake of completeness.

For convenience, we let all suffixes n range over N ∪ {∞}, where n = ∞ refers to the matrix T, its entries, fixpoints etc. Denote the other fixpoint of T by β, so β ∈ R\[0, δ]. Without loss of generality, each T_{n} is hyperbolic with fixpoints τ_{1,n}, τ_{2,n} ∈ R ∪ {∞} such

that τ_{1,n} ∈ (0, δ) and τ_{2,n} ∉ [0, δ] for all n and τ_{1,n} → α, τ_{2,n} → β. Let P_{n} := ( \begin{matrix}1 & −τ_{1,n} \\ 0 & 1 \end{matrix} )

or ( \begin{matrix}1 & −τ_{1,n} \\ 1 & −τ_{2,n} \end{matrix} ) according as τ_{2,n} = ∞ or otherwise. Note that, since the c-entry of T_{n} is

fixed, then β = ∞ ⇔ c = 0 ⇔ τ_{2,n} = ∞ for all n.

For all z ∈ C ∪ {∞}, μ_{P_{n}T_{n}P_{n}^{−1}}(z) = κ_{n}z for some κ_{n} ∈ R_{>0}\{1} such that κ_{n} → κ_{∞}. There are two cases, namely κ_{∞} < 1 and κ_{∞} > 1. In either case, we may also assume without loss of generality that each κ_{n} satisfies the same inequality and that there exists ϵ > 0 such that |κ_{n} − 1| > ϵ for all n.

Now x_{n} → α if and only if P_{n}x_{n} → 0. We have

P_{n+1}x_{n+1} = P_{n}x_{n+1} + (P_{n+1}x_{n+1} − P_{n}x_{n+1})  (5)
= P_{n}T_{n}x_{n} + (P_{n+1}x_{n+1} − P_{n}x_{n+1})
= (P_{n}T_{n}P_{n}^{−1})(P_{n}x_{n}) + (P_{n+1}x_{n+1} − P_{n}x_{n+1})
= κ_{n}(P_{n}x_{n}) + (P_{n+1}x_{n+1} − P_{n}x_{n+1}) .

Note that since P_{n} → P_{∞} and the x_{n} are assumed to be bounded, it follows that |P_{n+1}x_{n+1} − P_{n}x_{n+1}| → 0. First suppose κ_{∞} < 1. Applying the triangle inequality to (5) gives

|P_{n+1}x_{n+1}| ≤ (1 − ϵ)|P_{n}x_{n}| + δ_{n},

where δ_{n} → 0, from which it is easily deduced that P_{n}x_{n} → 0, as desired. Finally, suppose κ_{∞} > 1. This time, the triangle inequality gives

|P_{n+1}x_{n+1}| ≥ (1 + ϵ)|P_{n}x_{n}| − δ_{n},

which is easily seen to leave only two possibilities: either P_{n}x_{n} → 0 or P_{n}x_{n} → ∞. But the latter would imply that x_{n} → β, which is impossible, since lim x_{n}, if it exists, must by hypothesis lie in [0, δ]. This completes the proof.

We now come to the main result of this section:

Theorem 3.3 Let M be a finitary multiset and suppose d(M_{+}) and d(M_{−}) both exist in (0, ∞), say equal to r/2 and s/2 respectively. Let S ⊆ N be a set with asymptotic density δ/2 > 0 (considered as a multisubset of Z also). Let α ∈ (0, δ) be a fixpoint of T_{δ,r,s} as in Lemma 3.2. Then the following hold for π := π_{g}^{M,S}:

L = lim_{n∈A} \frac{π(n)}{n}, i.e., the limit exists,
l = lim_{n∈B∪C} \frac{π(n)}{n}, i.e., the limit exists,

L = 1 + \frac{α}{r},  (6)
l = 1 − \frac{δ − α}{s}.  (7)

Proof: The main point is to prove that the limits exist - eqs. (6) and (7) will then follow easily.

We denote M_{+} = (μ_{n})_{0}^{∞}, M_{=}(ν_{n})_{−1}^{−∞} and, for each n ≥ 1, a_{n} := max{A ∩ [1, n]}, b_{n} := max{B ∩ [1, n]}, c_{n} := max{C ∩ [1, n]} and

α_{n} := \frac{|A ∩ [1, n]|}{n}.

The main task will be to show that α_{n} → α as n → ∞. We begin by establishing a couple of claims.

Claim 1: a_{n} ∼ n and b_{n} ∼ n.

First consider a_{n}. We have (a_{n}, n] ⊂ B ∪ C. Property U2 implies that d_{π} is constant on (a_{n}, n], with value d_{0} < 0, say. Then unless a_{n} ∼ n we’ll get the contradiction that ν_{d_{0}} = Θ(d_{0}), as the assumption that S has positive density guarantees that a positive proportion of the interval (a_{n}, n] lies in B.

Next, consider b_{n}. Suppose, on the contrary, that we can find a sequence n_{l} → ∞ such that n_{l} − b_{n_{l}} = Θ(n_{l}). Let us assume that c_{n_{l}} ∼ n_{l} as otherwise the argument becomes much simpler (note that such a situation can only arise a priori if δ = 1). The aim now will be to produce a subsequence (l′) ⊆ (l) and intervals I_{l′} ⊆ [1, n_{l′}] such that

(i) |I_{l′}| = Θ(n_{l′}),

(ii) |I_{l′} ∩ π(A)| ≳ δ|I_{l′}|.

First suppose we have such a sequence of intervals - we can obtain a contradiction from this. Fix l′. Let

π(q) := min{I_{l′} ∩ π(A)},
π(Q) := max{I_{l′} ∩ π(A)}.

Let K_{l′} := [q, Q] ⊆ [1, n_{l′}]. Then U1 implies that |K_{l′} ∩ A| = |I_{l′} ∩ π(A)|. In particular, |K_{l′}| = Θ(n_{l′}). That d(M_{+}) = \frac{r}{2} > 0 implies that (as l′ → ∞)

[π(Q) − Q] − [π(q) − q] ∼ \frac{|I_{l′} ∩ π(A)|}{r} ≳ \frac{δ}{r}|I_{l′}|,

hence

|K_{l′}| = 1 + (Q − q) ≲ |I_{l′}| (1 − \frac{δ}{r}) .

It follows that

\frac{|K_{l′} ∩ A|}{|K_{l′}|} ≳ \frac{δ · |I_{l′}|}{(1 − \frac{δ}{r}) · |I_{l′}|} = δ + |Θ(1)|.

But since |K_{l′}| = Θ(n_{l′}), this contradicts the fact that S has density δ/2.

So it remains to find the intervals I_{l′}. We divide the analysis into two cases:

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A03 12

Case I: [π(c_{n_{l}}) − π(b_{n_{l}})] ∼ (c_{n_{l}} − b_{n_{l}}).

In this case, take I_{l} := (π(b_{n_{l}}), π(c_{n_{l}})], so that (i) is satisfied. By U2, I_{l} ∩ π(B) = ϕ. But

|I_{l} ∩ π(C)| = |(b_{n_{l}}, c_{n_{l}}] ∩ C| ∼ (1 − δ)(c_{n_{l}} − b_{n_{l}}) ∼ (1 − δ)|I_{l}|,

so (ii) is also satisfied. Case II: We can find a sequence (l′) ⊆ (l) such that [π(c_{n_{l′}})−π(b_{n_{l′}})] ≲ (1−Θ(1))(c_{n_{l′}} −b_{n_{l′}}).

Then

c_{n_{l′}} = d(b_{n_{l′}}) + π(c_{n_{l′}}) + Θ(n_{l′}).

Let τ_{l′} be the smallest integer such that Ξ_{b_{n_{l′}} ,d(b_{n_{l′}})−τ_{l′}} < ν_{d(b_{n_{l′}})−τ_{l′}}. Since d(M_{−}) > 0, we can be sure that τ_{l′} = o(n_{l′}). Set

χ_{l′} := d(b_{n_{l′}}) + π(c_{n_{l′}}) + τ_{l′} + 1, I_{l′}^{1} := [χ_{l′}, n_{l′}], I_{l′}^{2} := I_{l′}^{1} − [τ_{l′} + d(b_{n_{l′}})] . Then |I_{l′}^{1}| = |I_{l′}^{2}| = Θ(n_{l′}) and, since χ_{l′} > b_{n_{l′}}, we have I_{l′}^{1} ⊂ A ∪ C. Thus, since d(S) = δ/2, we have that |I_{l′}^{1} ∩ A| ∼ δ|I_{l′}^{1}|. But furthermore, since π chooses greedily, it must be the case that for every x ∈ I_{l′}^{1} ∩ A, x − [τ_{l′} + d(b_{n_{l′}})] ∈ I_{l′}^{2} ∩ π(A). Thus we can finally take I_{l′} = I_{l′}^{2} in this case, and Claim 1 is proven. Claim 2:

π(a_{n}) ∼ n (1 + \frac{α_{n}}{r} ) ,  (8)
π(b_{n}) ∼ n (1 − \frac{δ − α_{n}}{s} ) .  (9)

We have π(a_{n}) = a_{n} + d(a_{n}). We already know that a_{n} ∼ n. But U1 and the assumption that d(M_{+}) = r/2 imply that d(a_{n}) ∼ \frac{α_{n}n}{r}. This proves (8). The proof of (9) is similar.

By U2 we know that

π(a_{n}) − α_{n}n = #{x ∈ B ∪ C : π(x) ≤ π(a_{n})}.

From Claim 2 we know that

π(a_{n}) − α_{n}n ∼ n (1 + \frac{α_{n}}{r} − α_{n}) .  (10)

Set

y = y(n) := max{x ∈ B ∪ C : π(x) ≤ π(a_{n})}.

Now y = π(y) + |d(y)|. Clearly, π(y) ∼ π(a_{n}). From Claim 1 and U1 we also see easily that

|d(y)| ∼ \frac{1}{s}[π(a_{n}) − α_{n}n − (1 − δ)y],

and hence, by (8) and (10), that

\frac{y(n)}{n} ∼ \frac{(1 + \frac{1}{s}) (1 + \frac{α_{n}}{r} ) − \frac{α_{n}}{s}}{1 + \frac{1−δ}{s}} = 1 + Θ(1).  (11)

Relations (10) and (11) imply that

α_{y(n)} ∼ 1 − \frac{(1 + \frac{α_{n}}{r} − α_{n}) (1 + \frac{1−δ}{s})}{(1 + \frac{1}{s}) (1 + \frac{α_{n}}{r} ) − \frac{α_{n}}{s}}.  (12)

Now let N be some very large fixed positive integer. We define a sequence (x_{k,N})_{k=1}^{∞} of rational numbers in (0, 1) and a sequence (z_{k,N})_{k=1}^{∞} of natural numbers tending to infinity by

x_{1,N} := α_{N}, z_{1,N} := y(N),  (13)
x_{k+1,N} := α_{z_{k,N}} , z_{k+1,N} := y(z_{k,N}) ∀ k ≥ 1.

Lemma 3.2 implies that x_{k,N} → α as k → ∞. By (11), this in turn implies that \frac{z_{k+1,N}}{z_{k,N}} → c for some c > 1, independent of N. From the proof of Lemma 3.2 we see that the rate of convergence in both cases is determined by the multisets M_{+}, M_{−} and S, and the choice of starting point N only. ¿From this it is easy to show that α_{n} ∼ α: for sufficiently large n one can compare α_{n} and α_{z_{k,N}} for some N such that n/N ≈ c^{k} and both k and N are also sufficiently large. We omit any further details.

From the knowledge that α_{n} converges to α, the whole of Theorem 3.3 follows easily. Indeed, (8) implies (6) and (9) implies (7), so the proof is complete.

Remark Given M and S satisfying the hypotheses of Theorem 3.3, a permutation τ of N for which D_{τ,S} ≤ M and L, l as in (6) and (7), one may show that

lim sup_{n∈N} \frac{τ(n)}{n} ≥ L, lim inf_{n∈N} \frac{τ(n)}{n} ≤ l.

This is perhaps not surprising, and since the argument we have in mind to prove it is quite technical, while not adding much to the ideas already introduced in this section, we choose not to include it.

For the remainder of this section, and in Sections 4 and 5 to follow, we assume that S = N. In particular, δ = 1 in Theorem 3.3.

In the special case that r = s = 2d, say, then (6) and (7) imply that

L − l = \frac{1}{d}.  (14)

One may check that the fixpoint α is given by

α = \frac{1}{2} [(1 − 2d) + \sqrt{1 + 4d^{2}}]  (15)

and hence that

L = \frac{1}{l}.  (16)

In particular, these relations hold if M is symmetric with asymptotic density d, in which case (16) also follows directly from the fact (Proposition 3.1(iv)) that π is an involution. In fact, in the symmetric case, we have a converse to Theorem 3.3. We omit the proof of the following proposition, which is similar to, though considerably simpler than, that of the theorem.

Proposition 3.4 Suppose M is finitary and symmetric. Suppose L := lim_{n∈A} \frac{π(n)}{n} exists and that L > 1. Then M has asymptotic density d := (L − \frac{1}{L})^{−1}.

4. Interspersion arrays

Let M = (ζ_{n})_{−∞}^{∞} be a symmetric, greedy multiset with ζ_{0} < ∞. We shall describe below two simple, and very similar, algorithms for constructing an interspersion array from π_{g}^{M} = π_{g}^{M,N}. In the case when M = Z these will be shown to coincide with the Wythoff array and its dual (and more generally for the corresponding arrays implicit in Fraenkel’s paper [2] when M = mZ, for any m > 0). When M is finitary, each array will contain infinitely many rows, whereas if ζ_{k} = ∞, then each array will contain exactly k rows.

Using a suggestive notation and terminology, we shall denote the two arrays by W = (w_{i,j}) and W^{∗} = (w_{i,j}^{∗}), and refer to them as the general-difference Wythoff array and generaldifference dual Wythoff array respectively^{1}. We denote by A (resp. A^{∗}) the algorithms for producing W (resp. W^{∗}). We shall now proceed with a formal description of A, including proofs that it produces an array with the desired properties. We then give a short description of A^{∗} and, since it is very similar, we omit details of the equally similar proofs, merely stating the corresponding results.

To describe A, we begin by removing any zeroes from the multiset M. That is, we take M′ = (ζ′_{n})_{−∞}^{∞} to be the multiset given by ζ′_{n} := ζ_{n} if n ≠ 0, and ζ′_{0} := 0. Observe that there is a simple relation between π_{g}^{M} and π_{g}^{M′}, namely

π_{g}^{M}(i) = i for 1 ≤ i ≤ ζ_{0}, π_{g}^{M}(i) = π_{g}^{M′}(i − ζ_{0}) + ζ_{0} for i > ζ_{0}.  (17)

Now set π := π_{g}^{M′}, A := A_{M′}, B := B_{M′}. Let 1 = u_{1} < u_{2} < u_{3} < ⋯ be the elements of A arranged in increasing order. Since M′ is symmetric, we have B = π(A) and U2 implies that i < j ⇔ π(u_{i}) < π(u_{j}). The algorithm A is a recursive procedure for inserting the pairs (u_{i}, π(u_{i})) one-by-one into the array W. At the n:th step it inserts the pair (u_{n}, π(u_{n})) either immediately to the right of an earlier pair, or at the beginning of a new row. We now give the formal rules:

1The reason why we do not simply call the arrays ‘generalised (dual) Wythoff’, which seems natural, is that that terminology has already been used by, for example, Fraenkel and Kimberling [3], in a rather different context.

Step 1: Set w_{1,1} := u_{1}, w_{1,2} := π(u_{1}).

n^{TH} Step for each n > 1: Each of the pairs (u_{i}, π(u_{i})), for 1 ≤ i < n, has already been inserted into the array. Denote by W_{n} the finite array formed by these, and let r_{n} be the number of its’ rows. We must now explain where to insert the pair (u_{n}, π(u_{n})). Define γ = γ(n) to be the smallest amongst the numbers appearing at the right-hand edge of each row of W_{n} (so γ(n) = π(u_{i}) for some n − r_{n} ≤ i < n). Let ξ = ξ(n) be defined by u_{ξ(n)} < γ(n) < u_{ξ(n)+1}. Let

θ = θ_{n} := γ(n) + [π(u_{ξ(n)}) − u_{ξ(n)}] .

We claim that θ_{n} = u_{m} for some m = m(n) ≥ n. For the moment, let us assume this. Then the algorithm A does the following:

(i) If m > n then it assigns w_{r_{n}+1,1} := u_{n}, w_{r_{n}+1,2} := π(u_{n}). (ii) If m = n, then suppose γ(n) appears in the t:th row, say γ(n) = w_{t,2j}. Then we assign w_{t,2j+1} := u_{n}, w_{t,2j+2} := π(u_{n}).

To verify that the algorithm is well-defined, it remains to prove the claim above. First we show that θ ∉ B. For suppose θ = π(u_{j}). Since u_{ξ} < γ we have θ > π(u_{ξ}) and hence j > ξ. By definition of ξ, this implies that u_{j} > γ. But then π(u_{j}) − γ = π(u_{ξ}) − u_{ξ} > π(u_{j}) − u_{j}, which contradicts property U1.

So now we know that θ_{n} = u_{m(n)} for some m(n). It remains to show that m(n) ≥ n. This, and the accompanying fact that A is well-defined, are easily achieved by induction on n. Clearly, the result holds for n = 2, so suppose n > 2 and that A is well-defined at all previous steps. By definition of A, either m(n − 1) = n − 1, in which case γ(n) > γ(n − 1) and hence θ_{n} > θ_{n−1} and m(n) > m(n − 1) as required, or m(n − 1) ≥ n, in which case γ, η and θ are all unchanged at the n:th step and m(n) = m(n − 1) ≥ n, as required.

We now turn to proving the various properties of the array W. The main property of interest is

Theorem 4.1 (i) W is an interspersion array. (ii) If M is finitary, then W will contain infinitely many non-empty rows. Otherwise, if ζ_{k} = ∞ then W will contain exactly k non-empty rows.

Proof: Part (ii) follows easily from part (i): see the remarks at the top of page 317 of [5]. We thus concentrate on proving part (i).

Of the four properties of an interspersion array listed in Section 1, the first is obvious, the second follows from the fact that θ_{n} > γ(n) for any n, and the third is also a simple consequence of the rules followed by A. So it remains to verify the interspersion property. So let i, j, p, q ∈ N with i < j, and suppose that w_{i,p} < w_{j,q} < w_{i,p+1}. We must show that w_{i,p+1} < w_{j,q+1} < w_{i,p+2}. The proof can be divided into four cases, depending on whether each of p and q is odd or even. We present the details in only one case as all the others are similar.

Case I: p, q both odd. Then w_{i,p} = u_{x} and w_{j,q} = u_{y} for some x ≠ y. The assumption is that

u_{x} < u_{y} < π(u_{x}),  (18)

and from this we want to deduce that

π(u_{x}) < π(u_{y}) < u_{z},  (19)

where

u_{z} = π(u_{x}) + π(u_{ξ}) − u_{ξ} and u_{ξ} < π(u_{x}) < u_{ξ+1}.  (20)

The left-hand inequality in (19) follows immediately from the left-hand inequality in (18). For the other side, we observe that the right-hand inequality of (18) implies that y ≤ ξ and hence, by U1, that π(u_{y})−u_{y} ≤ π(u_{ξ})−u_{ξ}. But then, by (20), we have that π(u_{y})−u_{y} ≤ u_{z} −π(u_{x}), which suffices to give the right side of (19).

This completes the proof of Theorem 4.1.

We now briefly describe the construction of the dual array W^{∗}. The algorithm A^{∗} first constructs an array Ω = (ω_{i,j}) which will need to be modified very slightly to produce W^{∗} if ζ_{0} > 0. Namely, A^{∗} begins by setting ω_{1,2j−1} = ω_{1,2j} = j for 1 ≤ j ≤ ζ_{0}. This time we let u_{1} < u_{2} < u_{3} < ⋯ denote, in increasing order, the sequence of elements of A_{M}\{1, ..., ζ_{0}}. A^{∗} now proceeds to insert the pairs (u_{i}, π(u_{i})) into the array Ω according to exactly the same rules as A, with the only difference being that, this time, the function ξ(n) is defined by

u_{ξ(n)−1} < γ(n) < u_{ξ(n)}.

The array W^{∗} may now only differ from Ω in the first row. Namely, we take

w_{i,j}^{∗} := \{ \begin{matrix}ω_{i,j}, & if i > 1, \\ j, & if i = 1, 1 ≤ j ≤ ζ_{0}, \\ ω_{1,j+ζ_{0}}, & if i = 1, j > ζ_{0}. \end{matrix}

We omit the proof of the following result:

Proposition 4.2 W^{∗} is an interspersion array. It has infinitely many rows if M is finitary and exactly k rows if ζ_{k} = ∞.

Remark There is in fact a whole family of interspersion arrays which can be constructed from a given symmetric M, of which W and W^{∗} are the two ‘extremes’, in the following sense. Let the notation be as in the definition of the algorithm A. Fix n and a choice of an integer Δ_{n} ∈ [δ_{ξ(n)}, δ_{ξ(n)+1}]. If we take θ_{n} := γ(n) + Δ_{n} then the same argument as before gives that θ_{n} = u_{m(n)} for some m(n) ≥ n. Hence, provided we don’t vary our choice of Δ_{n} as long as m(n) > n, one can insert the pairs (u_{i}, π(u_{i})) in an array according to the same rules as for A. The proof of Theorem 4.1 can be run through to show that this will be always be an interspersion array (as long as we make the appropriate adjustments regarding ζ_{0}). We omit further details. Clearly, W and W^{∗} correspond respectively to the choices Δ_{n} = δ_{ξ(n)} (resp. Δ_{n} = δ_{ξ(n)+1}) for all n.

We close this section by proving:

Proposition 4.3 If M = Z then W is the Wythoff/Zeckendorff array and W^{∗} is its dual.

Proof: We give the proof for W only; the proof for W^{∗} is similar.

Let π := π_{g}^{M′}, A := A_{M′}. From (2) and (17) it easily follows that

π(u) = ⌈ϕu⌉ for every u ∈ A.  (21)

By [8], Theorems 1 and 4, in order to show that W is the Wythoff array, it thus suffices to prove the following two facts:

(i) for each i > 1, w_{i,1} is the smallest natural number not appearing in the previous rows,

(ii) for every i ≥ 1 and j ≥ 3, w_{i,j} = w_{i,j−1} + w_{i,j−2}. Now (i) is a trivial consequence of the rules for the algorithm A, so we concentrate on (ii). We consider two cases, depending on whether j is odd or even.

Case I: j odd. Then there exist u_{1} ≤ u_{2} ≤ u_{3} ∈ A such that w_{i,j−2} = u_{1}, w_{i,j−1} = π(u_{1}) and w_{i,j} = u_{3} = π(u_{1}) + [π(u_{2}) − u_{2}], where u_{2} = max{A ∩ [1, π(u_{1}))}. Since M = Z, it is clear that u_{2} = π(u_{1}) − 1 (i.e.: no two consecutive integers can lie in B = π(A)). Thus u_{3} = π[π(u_{1}) − 1] + 1 and we need to show that

π[π(u_{1}) − 1] + 1 = u_{1} + π(u_{1}).

But this follows from (21) and [8], Lemma 1.3.

Case II: j even. The proof is similar, just a bit more technical, and makes use of [8], Lemma 1.4. We omit further details.

This completes the proof of Proposition 4.3.

Remark One may equally well show that for any m ≥ 1, if M = mZ, then W = W_{m} coincides with the generalisation of the Wythoff/Zeckendorff array implicit in Fraenkel’s paper [2]. The verification of the recurrence w_{i,j} = mw_{i,j−1} + w_{i,j−2} for i ≥ 1 and j ≥ 3, for which one uses (2) and (4), seems rather messy however, so we do not include it.

5. The multisets M_{m,p}

Let m, p ≥ 1 be any fixed positive integers. We now seek further results for the multiset M_{m,p} = (ζ_{n}^{m,p}) where ζ_{n}^{m,p} := p if m|n and ζ_{n}^{m,p} = 0 otherwise. We denote π_{m,p} := π_{g}^{M_{m,p},N}.

M_{m,p} has density p/m and is finitary and symmetric. Hence, by Proposition 3.1, π_{m,p} is an involution, and by Theorem 3.3 the limits L and l exist and are given by

L^{2} − \frac{m}{p}L − 1 = 0 ⇒ L = \frac{m + \sqrt{m^{2} + 4p^{2}}}{2p} ,  (22)
l = \frac{1}{L} = L − \frac{m}{p}.  (23)

p-Blocking m-Wythoff Nim For want of something better, this is the name we have chosen for a generalisation of the m-Wythoff game of Section 1 for which the P -positions are precisely the pairs (n − 1, π_{m,p}(n) − 1) for n ≥ 1. The rules of the game are just as in the m-Wythoff game, with one exception. Before each move is made, the previous player is allowed to ‘block’ some of the possible moves of Type III. More precisely, if the current configuration is (k, l), then before the next move is made, the previous player is allowed to choose up to p−1 distinct, positive integers c_{1}, ..., c_{p−1} ≤ min{k, l} and declare that the next player may not move to any configuration (k − c_{i}, l − c_{i}).

For m = 1 and any p, it is not hard to see that, by property U1, the P-positions of the game are precisely the configurations (n − 1, π_{1,p}(n) − 1). Combining with the methods of [2], one obtains the same result for all m and p. We omit further details. The interest of the game lies in it being a Muller twist, in the sense of [10], of m-Wythoff Nim.

Beatty sequences There is a simple reason why, for any p > 1, it won’t be possible to express the pairs (n, π_{m,p}(n)) as (⌈nr⌉, ⌈ns⌉) for any real r and s satisfying (1), and depending only on m and p. Let us say that an ordered pair (x, y) of real numbers is in standard form if x ≤ y. Two ordered pairs (n_{1}, π_{m,p}(n_{1})) and (n_{2}, π_{m,p}(n_{2})), in standard form, are said to be consecutive if n_{1} < n_{2} and there is no pair (n_{3}, π_{m,p}(n_{3})) in standard form such that n_{1} < n_{3} < n_{2}.

Now the point is that, for any p > 1, there may exist consecutive pairs (n_{1}, π_{m,p}(n_{1})) and (n_{2}, π_{m,p}(n_{2})) for which n_{2} − n_{1} is any integer in {1, ..., p+1}. On the other hand, for any real α and integer n, the difference ⌈(n+1)α⌉−⌈nα⌉ can attain one of only two possible values.

Nevertheless, there does appear to be a close relationship between all the permutations π_{m,p} and Beatty sequences. Here we content ourselves with conjecturing a weak form of this relationship:

Conjecture 5.1 Fix m, p ≥ 1 and let L and l be given by (22) and (23). Then there exists an integer c = c_{m,p} > 0, depending only on m and p, such that for each n ≥ 1, π_{m,p}(n) differs from one of the numbers ⌊nL⌋ and ⌊nl⌋ by at most c_{m,p}.

One may check that (2) and (4) imply that c_{m,1} = m−1 for all m (more precisely, π(n) = ⌊nl⌋ or ⌊nL⌋ − j for some 0 ≤ j < m in this case). The conjecture is supported by numerical evidence, which even suggests perhaps that the constant c_{m,p} can be made independent of p. For example, for m = 1 and p ≤ 5, we have checked that, for all n ≤ 10, 000, π_{1,p}(n) is one of the four numbers ⌊nL⌋, ⌈nL⌉, ⌊nl⌋, ⌈nl⌉.

A thorough analysis of the connection between the permutations π_{m,p} and Beatty sequences is left for future work.

6. The case S = kN

We now briefly return to the setting of more general subsets S of N. Whenever we can compute the asymptotics of π_{g}, i.e.: the limits L and l, it makes sense to ask if there is a closer relationship between the sequences (π_{g}(n))_{n∈A} and (π_{g}(n))_{n∈B}, and the sequences ⌊nL⌋ and ⌊nl⌋ respectively (which are Beatty sequences unless L and/or l are rational). For the example introduced earlier (M = Z, S = 2N), we shall show below (Theorem 6.1) that this is indeed the case, and state a more general conjecture (Conjecture 6.4) which extends Conjecture 5.1. However, as our method of proof for Theorem 6.1 will be seen to already be very technical, we are unable to shed much light here on the more general hypothesis.

Before stating the theorem, we need some further notation. For any positive integer n we denote

ϵ_{n} := \sqrt{3}n − ⌊\sqrt{3}n⌋.

Set

η := 2 − \sqrt{3},

and observe that, for all n,

ϵ_{n} − ϵ_{n+1} ≡ η (mod 1).  (24)

Let

0 = n_{0} < n_{1} < n_{2} < ⋯

denote the sequence of non-negative integers for which ϵ_{n_{i}} < η. The interval [2n_{i−1}, 2n_{i}) will be called the i:th period.

Theorem 6.1 Let M = Z, S = 2N, π := π_{g}^{M,S}. Define a function f = f_{2} : N → N as follows:

(I) for any n ≥ 1, f(2n − 1) := min{t : t ≠ f(i) for any i ≤ 2n − 2}.

(II) for any n ≥ 1,

f(2n) := n + ⌊\sqrt{3}n⌋, if ϵ_{n} > η and ϵ_{n−1} > η,

f(2n) := n + ⌊\sqrt{3}n⌋, if ϵ_{n} < η and ⌊\sqrt{3}n⌋ ∈ \{f(i) : i < 2n\},

f(2n) := ⌊\sqrt{3}n⌋, if ϵ_{n} < η and ⌊\sqrt{3}n⌋ ∉ \{f(i) : i < 2n\},

f(2n) := n + ⌊\sqrt{3}n⌋, if ϵ_{n−1} < η and f(2n − 2) = ⌊\sqrt{3}(n − 1)⌋,

f(2n) := ⌊\sqrt{3}n⌋ + 2, otherwise, i.e.: iff ϵ_{n−1} < η and ⌊\sqrt{3}(n − 1)⌋ ∈ \{f(i) : i < 2n − 2\}.

Then f ≡ π.

Remark: It is clear that the function f is a well-defined permutation of N. Since, for this pair M, S, we have r = s = 1 and δ = \frac{1}{2}, Theorem 3.3 says that L = \frac{1+\sqrt{3}}{2}, l = L − \frac{1}{2} = \frac{\sqrt{3}}{2}. Thus Theorem 6.1 asserts that, for all n ∈ A, π(n) = ⌊nL⌋, and for all n ∈ B, π(n) = ⌊nl⌋ or ⌊nl⌋ + 2. The behaviour of π(n) for n ∈ C seems to be a bit more erratic, though from U2 we can deduce, for example, that |π(n) − ⌊nl⌋| ≤ 2 for all n ∈ C.

In the proof to follow, the sets A, B and C will refer to π and have their usual meaning. The corresponding sets for f will be denoted A_{f}, B_{f} and C_{f}. We begin with a lemma which follows immediately from the definition of f:

Lemma 6.2 Let 2m_{1} < 2m_{2} be two consecutive numbers in A_{f}. Then either (i) or (ii) holds, where (i)

m_{2} = m_{1} + 1, ϵ_{m_{1}} > η, ϵ_{m_{2}} > η and f(2m_{2}) = f(2m_{1}) + 3.  (25)

(ii)

m_{2} = m_{1} + 2, ϵ_{m_{2}} > η, ϵ_{m_{1}} < η or ϵ_{m_{1}+1} < δ, and f(2m_{2}) − f(2m_{1}) = 5. (26)

Our idea is to prove by induction on k > 0 that f(n) = π(n) for all n in the k-th period. One may verify by hand that the two functions coincide over the first 3 periods say (n_{3} = 11). Now let k > 3 and suppose that f ≡ π over the first k − 1 periods. Note that, by definition,

If n is odd, then f(i) = π(i) ∀ i < n ⇒ f(n) = π(n).  (27)

The main tool in our proof (which does not depend on the induction hypothesis) is the following:

Lemma 6.3 Suppose ϵ_{n} < η. Then there are precisely 2n − ⌊\sqrt{3}n⌋ values of m < n such that f(2m) ≥ ⌊\sqrt{3}n⌋, unless perhaps f(2m) = ⌊\sqrt{3}n⌋ − 1 for some m < n where 2m ∈ A_{f}.

Proof: Let 1 ≤ m < n be even such that f(2m) > ⌊\sqrt{3}n⌋. Then 2m ∈ A_{f} and f(2m) = m + ⌊\sqrt{3}m⌋. Thus

f(2m) > ⌊\sqrt{3}n⌋ ⇔ m > \frac{\sqrt{3}n − ϵ_{n}}{1 + \sqrt{3}} .  (28)

Set

m^{0} := \frac{\sqrt{3}n − ϵ_{n}}{1 + \sqrt{3}} .  (29)

After a little manipulation, we find that

m^{0} = \frac{3n − ⌊\sqrt{3}n⌋}{2} − \frac{\sqrt{3}}{2}ϵ_{n}.

Set m_{0} := ⌊m^{0}⌋. Since ϵ_{n} < η, it is easily checked that m_{0} = m^{0} − ϵ, where

ϵ = \{ \begin{matrix}1 − \frac{\sqrt{3}}{2}ϵ_{n}, & if 3n − ⌊\sqrt{3}n⌋ ∈ 2Z, \\ \frac{1}{2} − \frac{\sqrt{3}}{2}ϵ_{n}, & if 3n − ⌊\sqrt{3}n⌋ ∉ 2Z. \end{matrix}  (30)

Since 2m ∈ A_{f}, we have to count the number of elements of A_{f} in the interval (2m_{0}, 2n). Since ϵ_{n} < η, there are precisely 2n − ⌊\sqrt{3}n⌋ elements of B_{f} in the interval (1, 2n), one for each period. Similarly, there are 2m_{0} − ⌊\sqrt{3}m_{0}⌋ + ϕ elements of B_{f} in the interval [1, 2m_{0}], where ϕ = 0 unless ϵ_{m_{0}} < η and 2m_{0} ∈ B_{f}, in which case ϕ = 1. Hence the total number of elements of A_{f} in (2m_{0}, 2n) is

(n − m_{0} − 1) − [(2n − ⌊\sqrt{3}n⌋) − (2m_{0} − ⌊\sqrt{3}m_{0}⌋ + ϕ)]
= (⌊\sqrt{3}n⌋ − ⌊\sqrt{3}m_{0}⌋) − (n − m_{0}) − 1 + ϕ
= (\sqrt{3} − 1)(n − m^{0}) + (\sqrt{3} − 1)ϵ + (ϵ_{m_{0}} − ϵ_{n}) + (ϕ − 1).

Using (29) and the fact that (1 + \sqrt{3})η = \sqrt{3} − 1, this becomes

2n − ⌊\sqrt{3}n⌋ + Δ,

where

Δ = (\sqrt{3} − 1)ϵ + ϵ_{m_{0}} − \sqrt{3}ϵ_{n} + ϕ − 1.  (31)

We shall now show that Δ = 0 unless ϵ_{m_{0}} < η and f(2m_{0}) = ⌊\sqrt{3}n⌋ − 1, in which case Δ = −1. This will suffice to prove the lemma. The analysis can be divided into two cases, suggested by (30). We present in detail the case ϵ = \frac{1}{2} − \frac{\sqrt{3}}{2}ϵ_{n}, which is the only one in which the possibility that Δ = −1 can arise. The other case is treated similarly but is technically simpler.

The value of ϵ implies that

m_{0} = \frac{3n − ⌊\sqrt{3}n⌋}{2} − \frac{1}{2}.

A little computation shows that

\sqrt{3}m_{0} = (⌊\sqrt{3}n⌋ − m_{0}) + γ,  (32)

where

γ = (\frac{3 + \sqrt{3}}{2}) ϵ_{n} − \frac{\sqrt{3} + 1}{2}.

Since ϵ_{n} < η, one checks readily that γ ∈ (\frac{−\sqrt{3}−1}{2}, −1 + η) ⊂ (−2 + η, −1 + η). Hence there are the following two possibilities: either

ϵ_{m_{0}} > η and ϵ_{m_{0}} = \frac{3 − \sqrt{3}}{2} + (\frac{3 + \sqrt{3}}{2}) ϵ_{n},  (33)

or

ϵ_{m_{0}} < η and ϵ_{m_{0}} = \frac{1 − \sqrt{3}}{2} + (\frac{3 + \sqrt{3}}{2}) ϵ_{n}.  (34)

If (33) holds, then ϕ = 0 also. Substituting everything into (31) in this case, one readily computes that Δ = 0, independent of ϵ_{n}, as required. If (34) holds, then substituting everything into (31) one finds that Δ = −1 + ϕ. If 2m_{0} ∈ B_{f}, then ϕ = 1 and Δ = 0 again, as required. Otherwise, Δ = −1 and 2m_{0} ∈ A_{f}. But then, from (32) and (34), we find that

f(2m_{0}) = m_{0} + ⌊\sqrt{3}m_{0}⌋ = m_{0} + (⌊\sqrt{3}n⌋ − m_{0} − 1) = ⌊\sqrt{3}n⌋ − 1,

and the lemma is proved.

Now let us perform the induction step. To simplify notation, set N := n_{k}. Note that U2, together with Lemmas 6.2 and 6.3, imply that if ⌊\sqrt{3}N⌋ − 1 ∈ f(A_{f}), then f(2N − 1) = ⌊\sqrt{3}N⌋. Let m_{0} = m_{0}(N) = ⌊m^{0}N⌋ be as in (29) ff.

The k:th period is either [2N, 2N + 5] or [2N, 2N + 7] according as to whether ϵ_{N+3} < η or not respectively. Clearly,

ϵ_{N+3} < η ⇔ ϵ_{N} < 4η − 1.  (35)

It is required to show that f(2N + i) = π(2N + i) for i ∈ [0, 5] or i ∈ [0, 7], as appropriate. The first and crucial observation is that Lemma 6.3, together with the induction hypothesis and the definition of f, imply the result for i = 0. By (27) it also suffices to treat the case of even i. We now divide the remainder of the proof into two cases:

Case I: 2N ∈ A_{f}.

Lemma 6.3 and its proof imply that, in Case I, either

(i) 2m_{0} ∈ A_{f}, ϵ_{m_{0}} < η, f(2m_{0}) = ⌊\sqrt{3}N⌋ − 1 and f(2N − 1) = ⌊\sqrt{3}N⌋, or (ii) f(2m_{1}) = ⌊\sqrt{3}N⌋ for some 2m_{1} ∈ A_{f}. In this case, it is clear from (29) that m_{1} = m_{0} +1 and ϵ_{m_{1}} = \frac{3+\sqrt{3}}{2}ϵ_{N}.

i = 2: Since 2N ∈ A_{f}, the definition of f implies that 2(N + 1) ∈ B_{f}, and that f(2N + 2) = ⌊\sqrt{3}N⌋ + 2. We have to show that 2(N + 1) ∈ B. If not, it can only be because the number ⌊\sqrt{3}N⌋ + 2 was already chosen by π, and hence also by f (because of the induction hypothesis), and hence lies in f(A_{f}), by Lemma 6.3. But if (i) holds, then this is impossible by (26), and if (ii) holds, it is impossible by (25).

i = 4: This time, it is required to show that 2(N + 2) ∉ B. If it were, since the numbers ⌊\sqrt{3}N⌋ + j, j = 1, 2, have already been chosen in positions 2N + j, j = 1, 2, the avoidance property of π leaves as the only option that π(2N + 4) = ⌊\sqrt{3}N⌋ + 3. But then this number was not already chosen in position 2N + 3, which is only possible if it already appeared in f(A_{f}), i.e: it cannot but already have appeared somewhere, and hence π will not choose it again.

i = 6: Once again, it needs to be shown that 2(N + 3) ∉ B_{f}. The analysis of the i = 4 case, together with (27), shows that all numbers up to and including ⌊\sqrt{3}N⌋+3 have already appeared in the first 2N + 3 positions. By a similar analysis, either the number ⌊\sqrt{3}N⌋ + 4 has already appeared in f(A_{f}) by then, or it appears in position 2N + 5. That leaves as the only option, if indeed 2(N + 3) ∈ B, that π(2N + 6) = ⌊\sqrt{3}N⌋ + 5. Our analysis shows moreover that this can only happen if the numbers ⌊\sqrt{3}N⌋ + j, j = 1, 2, 3, 4, have appeared in positions 2N + j′, where j′ = 1, 2, 3, 5 respectively. In particular, this means that none of the numbers ⌊\sqrt{3}N⌋ + l, l = 1, 2, 3, 4, 5, appears in f(A_{f}). This contradicts Lemma 6.2.

Case II: 2N ∈ B_{f}.

Lemma 6.3 and U2 imply that ⌊\sqrt{3}N⌋ − 1 does not appear in f(A_{f}). The analysis is very similar to Case I, but for i = 6 becomes considerably more technical. We present just this part of the proof. Note that, by (35), we may henceforth assume that ϵ_{N} > 4γ − 1.

i = 6: It is required to show that 2N +6 ∈ A. If not, one easily sees by going through the analysis for the values of i < 6 that we must, a priori, have π(2N + 6) = ⌊\sqrt{3}N⌋ + j, where j = 4 or 5. If j = 4 then we will derive the contradiction that none of the six consecutive numbers ⌊\sqrt{3}N⌋ + l, l = −1, 0, 1, 2, 3, 4, appears in f(A_{f}).

Thus we may assume that j = 5. Here we can still deduce that exactly one of the seven consecutive numbers ⌊\sqrt{3}N⌋ + l, l = −1, 0, 1, 2, 3, 4, 5, appears in f(A_{f}). By Lemma 6.2, the correct value of l must be 1, 2 or 3. Suppose f(2m) = ⌊\sqrt{3}N⌋ + l. Clearly, m = m_{1} or m = m_{1} + 1, where m_{1} = m_{0} + 1, as above. By (29), we have that

(1 + \sqrt{3})m_{1} = ⌊\sqrt{3}N⌋ + ϵ^{∗},

where

ϵ^{∗} = \{ \begin{matrix}(\sqrt{3} + 1)\frac{\sqrt{3}}{2}ϵ_{N}, & if 3N − ⌊\sqrt{3}N⌋ ∈ 2Z, \\ (\sqrt{3} + 1) (\frac{1}{2} + \frac{\sqrt{3}}{2}ϵ_{N}) , & if 3N − ⌊\sqrt{3}N⌋ ∉ 2Z. \end{matrix}

We examine the two possibilities separately:

First suppose

ϵ^{∗} = (\sqrt{3} + 1) (\frac{1}{2} + \frac{\sqrt{3}}{2}ϵ_{N}) .

Since 4η − 1 < ϵ_{N} < η, we easily compute that ϵ^{∗} ∈ (1 + 2η, 2). Thus ϵ_{m_{1}} > 2η and ⌊(1 + \sqrt{3})m_{1}⌋ = ⌊\sqrt{3}N⌋ + 1, hence ⌊(1 + \sqrt{3})(m_{1} + 1)⌋ = ⌊\sqrt{3}N⌋ + 4. It follows that 2m_{1} ∈ A_{f} and 2(m_{1} + 1) ∈ B_{f}. But this is contradicted by (25), (26) and the fact that ϵ_{m_{1}} > 2η ⇒ ϵ_{m_{1}+1} > η.

Finally, suppose

ϵ^{∗} = (\sqrt{3} + 1) \frac{\sqrt{3}}{2}ϵ_{N}.

Then ϵ^{∗} = ϵ_{m_{1}} and ⌊(1 + \sqrt{3})m_{1}⌋ = ⌊\sqrt{3}N⌋. Thus l = 2 or 3 in this case. But in either case, we have at least three consecutive numbers to the left of ⌊\sqrt{3}N⌋ + l, none of which is appears in f(A_{f}). By (26), this forces either

(i) l = 3, ϵ_{m_{0}} < η, or (ii) l = 2, ϵ_{m_{1}} < η.

But (i) is impossible, since one easily checks that ϵ_{N} ∈ (0, η) ⇒ ϵ_{m_{1}} ∈ (η, 1 − η) ⇒ ϵ_{m_{0}} ∈ (2η, 1). And (ii) is impossible since Lemma 6.2 would then imply that ⌊\sqrt{3}N⌋ + 5 also appeared in f(A_{f}).

Thus we have completed the proof that f = π over the k:th period, and thus the induction step, and hence the proof of Theorem 6.1, is complete.

We finish the paper with a natural extension of Conjecture 5.1:

Conjecture 6.4 Let m, p, k be any three positive integers. Let M := M_{m,p} and take S = S_{k} := kN. Let π = π_{m,p}^{k} := π_{g}^{M,S} and let L, l be as in (6), (7). Then there exists a positive integer c = c_{m,p,k}, depending only on m, p and k, such that, for all n ∈ N, π(n) differs from one of the numbers ⌊nL⌋ and ⌊nl⌋ by at most c_{m,p,k}.

As already remarked, Theorem 6.1 implies that we can take c_{1,1,2} = 2.

Acknowledgement

The authors would like to thank Jonas Knape for his input into some work which is the seed from which this paper grew and the referee for valuable suggestions for improving the presentation of the paper.

References

[1] S. Beatty, Problem 3173, Amer. Math. Monthly 33 (1926) 159; 34 (1927) 159.

[2] A.S. Fraenkel, How to beat your Wythoff games opponent on three fronts, Amer. Math. Monthly 89 (1982), 353-361.

[3] A.S. Fraenkel and C. Kimberling, Generalised Wythoff arrays, shuffles and interspersions, Discrete Math. 126 (1994), 137-149.

[4] A.S. Fraenkel, New games related to old and new sequences, Integers: Electronic J. Comb. Number Theory 4 (2004), Paper G06.

[5] C. Kimberling, Interspersions and dispersions, Proc. Amer. Math. Soc. 117 No.2 (1993), 313-321.

[6] C. Kimberling, The first column of an interspersion, Fibonacci Quart. 32 (1994), 301-314.

[7] C. Kimberling, The Zeckendorff array equals the Wythoff array, Fibonacci Quart. 33 (1995), 3-8.

[8] C. Kimberling, Stolarsky interspersions, Ars Combinatoria 39 (1995), 129-138.

[9] N.J.A. Sloane, My favorite integer sequences. Sequences and their applications, Proceedings of SETA 1998, C. Ding, T. Helleseth and H. Niederreiter (eds.). Springer Verlag, London 1999, pp. 103-110. (An updated version is available online at http://www.research.att.com/∼njas/doc/sg.pdf)

[10] F. Smith and P. Stănică, Comply/constrain games or games with a Muller twist, Integers: Electronic J. Comb. Number Theory 2 (2002), Paper G03.

[11] X. Sun and D. Zeilberger, On Fraenkel’s N-heap Wythoff’s conjectures, Ann. Comb. 8 (2004), 225-238.

[12] W.A. Wythoff, A modificaton of the game of Nim, Nieuw. Archief voor Viskunde (2) 7 (1907), 199-202.