\documentclass[12pt]{article} \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \usepackage{amssymb} \usepackage{amsfonts} \def\ni{\noindent} \begin{document} \begin{center} \vspace*{-40pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6 (2006), \#A03} \vskip 40pt \ni {\bf PERMUTATIONS OF THE NATURAL NUMBERS WITH PRESCRIBED DIFFERENCE MULTISETS} \vskip 20pt \ni {\bf Peter Hegarty} \\ {\smallit Chalmers University of Technology, 41296 G\"{o}teborg, Sweden} \\ {\tt hegarty@math.chalmers.se}\\ \vskip 10pt \ni {\bf Urban Larsson} \\ {\smallit Chalmers University of Technology, 41296 G\"{o}teborg, Sweden} \\ {\tt md0larur@student.chalmers.se} \\ \end{center} \vskip 30pt \centerline{\smallit Received: 5/27/05, Revised: 1/16/06, Accepted: 2/4/06, Published: 2/13/06} \vskip 30pt \centerline{\bf Abstract} \noindent We study permutations $\pi$ of the natural numbers for which the numbers $\pi(n)$ are chosen greedily under the restriction that the differences $\pi(n)-n$ belong to a given (multi)subset $M$ of \ni {\bf Z} for all $n \in S$, a given subset of \ni {\bf 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 = {\hbox{\ni {\bf Z}}}, S = {\hbox{\ni {\bf N}}}$, where the permutation $\pi$ arises in the study of the game of Wythoff Nim. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6 (2006), \#A03\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section*{\normalsize 1. Introduction} Consider the permutation $\pi = \pi_{g}$ of the natural numbers defined inductively as follows: \par (i) $\pi(1) = 1$, \par (ii) for each $n > 1$, $\pi(n):= t$, where $t$ is the least natural number not already appearing among $\pi(1),...,\pi(n-1)$ and such that $t - n \neq \pi(i) - i$, for any $1 \leq i < n$. Informally, we say that $\pi$ chooses numbers greedily under the restriction that differences $\pi(n) - n$ may not be repeated. The permutation $\pi$ exhibits a rich variety of beautiful properties, which may be said to be well-known. It is an involution of \ni {\bf N} and its asymptotics are given by \begin{eqnarray*} \lim_{n \in A} {\pi(n) \over n} = \phi = {1 + \sqrt{5} \over 2}, \end{eqnarray*} the golden ratio, where $A = \{n: \pi(n) \geq 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 $\pi = \pi_{g}^{M,S}$ of \ni {\bf N}, defined by a greedy choice procedure, under the restriction that the differences $\pi(n) - n$ belong to some assigned, but otherwise arbitrary, (multi)subset $M$ of \ni {\bf Z}, whenever $n \in S$, some assigned subset of \ni {\bf N}. Hence the above discussion relates to the case $S = {\hbox{\ni {\bf N}}}$ and $M =$ \ni {\bf Z}. We were motivated by the observation that some of the attractive properties of $\pi_{g}^{{\hbox{\ni {\bf Z,N}}}}$ 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 $\pi_{g}^{{\hbox{\ni {\bf Z,N}}}}$ 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 $\pi_{W}$. \ni {\bf 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 \par {\sc Type I}: $(k,l) \rightarrow (k^{\prime},l)$ for any $0 \leq k^{\prime} < k$. \par {\sc Type II}: $(k,l) \rightarrow (k,l^{\prime})$ for any $0 \leq l^{\prime} < l$. \par {\sc Type III}: $(k,l) \rightarrow (k-s,l-s)$ for any $0 \leq s \leq \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,\pi_{W}(n) - 1)$, for all $n \in {\hbox{\ni {\bf N}}}$. \ni {\bf Beatty Sequences} Let $r,s$ be any positive irrational numbers such that \begin{eqnarray} {1 \over r} + {1 \over s} = 1. \end{eqnarray} Beatty discovered [1] that the sets $X = \{ \lfloor nr \rfloor: n \in {\hbox{\ni {\bf N}}} \}$, $Y = \{ \lfloor ns \rfloor: n \in {\hbox{\ni {\bf N}}} \}$ form a partition of \ni {\bf N}. Now choose $r = \phi, s = \phi + 1 = \phi^{2}$. One readily checks that (1) is satisfied. It is well-known that $\pi_{W}$ is completely described by \begin{eqnarray} \pi_{W}(1) = 1, \;\;\; \pi_{W} = \pi_{W}^{-1}, \;\;\; \pi_{W}( \lceil n r \rceil ) = \lceil n s \rceil, \;\;\; \forall \; n \geq 1. \end{eqnarray} The point is that this gives a much more precise description of $\pi_{W}$ than just knowing its asymptotic behaviour. \ni {\bf Stolarsky interspersion arrays} An array $A = (a_{ij})_{i,j > 0}$ of natural numbers is called an {\em interspersion array} if the following properties are satisfied: \noindent (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 \neq 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 {\em Stolarsky interspersion} satisfies the following additional property: \noindent (v) every row of the array is a Fibonacci sequence, i.e.: for any $i \geq 1$ and $j \geq 3$, we have that \begin{equation} a_{i,j} = a_{i,j-1} + a_{i,j-2}. \end{equation} (Note that such an interspersion array must necessarily have infinitely many rows). There are two Stolarsky arrays naturally associated with the permutation $\pi_{W}$. The first is called the {\em Wythoff array} or the {\em Zeckendorff array}. Its first row is the $\lq$usual' Fibonacci sequence determined by $a_{1,1} = 1$, $a_{1,2} = 2$. The remaining rows are determined inductively as follows: \ni (i) $a_{i,1}$ is the least natural number not already appearing in the preceeding rows \\ (ii) $a_{i,2}$ is the so-called {\em Zeckendorff right-shift} $\cal Z$ of $a_{i,1}$. That is, $a_{i,1}$ is written in terms of the base for \ni {\bf 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} = {\cal Z}(1) + {\cal Z}(3) = 2 + 5 = 7$. \\ (iii) for every $j \geq 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 {\em 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 $\pi_{W}$: \begin{eqnarray*} \pi_{W}(1) = 1, \;\;\; \pi_{W} = \pi_{W}^{-1}, \;\;\; \pi_{W}(a_{1,2t}) = a_{1,2t+1} \;\; \forall \; t \geq 1, \\ \pi_{W}(a_{i,2t-1}) = a_{i,2t} \;\; \forall \; i \geq 2, t \geq 1. \end{eqnarray*} 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 {\em $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 {\sc Type III} as follows: from a position $(k,l)$ one can move to any position $(k-s,l-t)$ such that $0 \leq s \leq k$, $0 \leq t \leq l$ and $|s-t| < m$. \par Let $\pi_{W_{m}} = \pi_{g}^{m{\hbox{\ni {\bf Z,N}}}}$ be the permutation of \ni {\bf N} constructed by the same greedy choice procedure as $\pi_{W}$, but with the restriction that $\pi_{W_{m}}(i) - i$ must be a multiple of $m$ for all $i \in {\hbox{\ni {\bf N}}}$. It is easy to see that the P-positions for $m$-Wythoff Nim are just the pairs $(n-1,\pi_{W_{m}}(n)-1)$, for all $n \in {\hbox{\ni {\bf N}}}$. Fraenkel showed that these positions can be written in terms of Beatty sequences. If we choose \begin{eqnarray} r = r_{m}:= {2-m+\sqrt{m^{2}+4} \over 2}, \;\;\;\; s = s_{m}:= r_{m} + m, \end{eqnarray} then (2) holds, with $\pi_{W}$ replaced by $\pi_{W_{m}}$. In particular, the asymptotic behaviour of $\pi_{W_{m}}$ is given by \begin{eqnarray*} \lim_{n \in A} {\pi_{W_{m}}(n) \over n} = {s_{m} \over r_{m}} = {m + \sqrt{m^{2}+4} \over 2}, \end{eqnarray*} which is the positive root of the equation $x^{2}-mx-1=0$, where $A = \{n: \pi_{W_{m}}(n) \geq 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. \vskip 30pt \section*{\normalsize 2. Notation, terminology and summary of results} The following standard notations will be adhered to throughout the \\ paper: \par Given two sequences $(f_{n})_{1}^{\infty}$ and $(g_{n})_{1}^{\infty}$ of positive real numbers, we write $f_{n} = \Theta (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} \sim g_{n}$ if $f_{n}/g_{n} \rightarrow 1$ as $n \rightarrow \infty$, $f_{n} \gtrsim g_{n}$ if $\liminf f_{n}/g_{n} \geq 1$ and $f_{n} = o(g_{n})$ if $f_{n} / g_{n} \rightarrow 0$. We now specify our principal notations and terminology. For each $n \in {\hbox{\ni {\bf Z}}}$, let $\zeta_{n} \in {\hbox{\ni {\bf N}}}_{0} \cup \{ \infty\}$. The sequence $M:= (\zeta_{n})_{n=-\infty}^{\infty}$ is called a {\em multisubset} of \ni {\bf Z}, or simply a {\em multiset}. We think of $\zeta_{n}$ as the number of occurrences of the integer $n$ in $M$. If $\sum_{n \geq 0} \zeta_{n} = \infty$ we say that $M$ is {\em injective}. If $\sum_{n \leq 0} \zeta_{n} = \infty$, we say that $M$ is {\em surjective}. A multiset which is both injective and surjective will be called {\em bijective}. If $\zeta_{n} = \zeta_{-n}$ for all integers $n$, then $M$ is said to be {\em symmetric}. The {\em asymptotic density} of a multiset $M$ is defined by \begin{eqnarray*} d(M):= \lim_{n \rightarrow \infty} {1 \over 2n+1} \left( \sum_{k=-n}^{n} \zeta_{k} \right), \end{eqnarray*} whenever this limit exists. Observe that $d(M) = \infty$ whenever $\zeta_{n} = \infty$ for some $n$. Hence, this concept is only really interesting if $\zeta_{n} \in {\hbox{\ni {\bf N}}}_{0}$ for all $n$. Such a multiset is called {\em finitary}. $M$ is said to be a {\em 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 $\zeta_{n} = \infty$. If $n \geq 0$ and $\zeta_{n} = \infty$ then $\zeta_{n^{\prime}} = 0$ for all $n^{\prime} > n$. If $n \leq 0$ and $\zeta_{n} = \infty$, then $\zeta_{n^{\prime}} = 0$ for all $n^{\prime} < n$. \par The {\em positive} (resp.~{\em negative}) {\em part} of a multiset $M$, denoted $M_{+}$ (resp. $M_{-}$), is the multiset $(\zeta^{\prime}_{n})$ such that $\zeta^{\prime}_{n} = 0$ for all $n < 0$ (resp. $n \geq 0$) and $\zeta^{\prime}_{n} = \zeta_{n}$ for all $n \geq 0$ (resp. $n < 0$). Finally, let $M_{1} = (\zeta_{1,n})$ and $M_{2} = (\zeta_{2,n})$ be any two multisets. We write $M_{1} \leq M_{2}$ if $\zeta_{1,n} \leq \zeta_{2,n}$ for all $n \in {\hbox{\ni {\bf Z}}}$. Let $S$ be a subset of \ni {\bf N} and $f: {\hbox{\ni {\bf N}}} \rightarrow {\hbox{\ni {\bf N}}}$ be any function. For $n \in {\hbox{\ni {\bf N}}}$ we denote $d(n) = d_{f}(n):= f(n) - n$. The {\em difference multiset} of $f$ {\em with respect to $S$}, denoted $D_{f,S}$, is defined by $D_{f,S} = (\zeta_{n})_{- \infty}^{\infty}$ where \begin{eqnarray*} \zeta_{n} = \# \{ k \in S: d(k) = n \}. \end{eqnarray*} If $S = {\hbox{\ni {\bf N}}}$ we drop the second subscript and write simply $D_{f}$. \par Suppose $S = {\hbox{\ni {\bf 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} \geq 1$ such that $d_{f}(n) < 0$ for all $n \geq n_{0}$. Let $n_{0} \leq T:= \max \{f(n): 1 \leq n < n_{0}\}$. Then $f(n) \leq T$ for all $1 \leq n \leq 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 = (\zeta_{n})$ and $S$ be given. An injective mapping $\pi_{g} = \pi_{g}^{M,S}: {\hbox{\ni {\bf N}}} \rightarrow {\hbox{\ni {\bf N}}}$ such that $D_{\pi_{g},S} \leq M$ can be constructed by means of a $\lq$greedy algorithm': for each $n \in {\hbox{\ni {\bf N}}}$, $\pi_{g}(n)$ is defined inductively to be the least positive integer $t$ not equal to $\pi_{g}(k)$ for any $k < n$ and, if $n \in S$, satisfying the additional condition that $\# \{ k < n: k \in S \; {\hbox{and}} \; d_{\pi_{g}}(k) = t - n \} < \zeta_{t-n}$. It is easy to see that $\pi_{g}$ is also surjective (since $M$ is), hence a permutation of \ni {\bf N}. \par We have an associated partition of the natural numbers \ni {\bf N} $= A \sqcup B \sqcup C$ where \begin{eqnarray*} A = A_{M,S}:= \{n \in S: d_{\pi_{g}}(n) \geq 0 \}, \;\;\;\; B = B_{M,S}:= \{ n \in S: d_{\pi_{g}}(n) < 0 \}, \\ C = C_{S}:= {\hbox{\ni {\bf N}}} \backslash S. \end{eqnarray*} We also fix the following notation: for each $k \in {\hbox{\ni {\bf Z}}}$, $n \geq 1$, set \begin{eqnarray*} \Xi_{n,k} = \Xi_{n,k,M,S}:= \# \{j: 1 \leq j \leq n, j \in S \; {\hbox{and}} \; d_{\pi_{g}}(j) = k \}. \end{eqnarray*} Note that the permutation $\pi_{W_{m}}$ discussed in Section 1 corresponds to the pair $S = {\hbox{\ni {\bf N}}}$ and $M = m{\hbox{\ni {\bf Z}}}$, i.e.: $\zeta_{n} = 1$ if $m | n$ and $\zeta_{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 $\lq$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 = {\hbox{\ni {\bf N}}}$. In particular, when $S = {\hbox{\ni {\bf N}}}$ then $\pi_{g}$ always satisfies a certain $\lq$uniqueness property' not immediately obvious from its definition, and if furthermore $M$ is symmetric, then $\pi_{g}$ is an involution of \ni {\bf N}. The main result of this section (Theorem 3.3) shows how the asymptotics of $\pi_{g}$ can always be computed provided that $M$ and $S$ are $\lq$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 = {\hbox{\ni {\bf N}}}$ and symmetric $M$ (Proposition 3.4). In the next two sections, it is assumed that $S = {\hbox{\ni {\bf N}}}$. In Section 4 we illustrate that, for any symmetric $M$, there are two natural ways to arrange the pairs $\{n,\pi_{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 ${\cal M}_{m,p}$, i.e.: $\zeta_{n} = p$ if $m | p$ and $\zeta_{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,\pi_{g}^{{\cal M}_{m,p},{\hbox{\ni {\bf 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]). \par This section is closed with a conjecture which suggests a close relationship between the values $\pi_{g}^{{\cal M}_{m,p},{\hbox{\ni {\bf 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 $\lq$algebraic' description of the permutations $\pi_{g}^{M,{\hbox{\ni {\bf N}}}}$, which is certainly not going to be possible for very general $M$. Neverthless, in some cases like $M = {\cal 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 $\pi_{g}^{{\hbox{\ni {\bf Z}}},2{\hbox{\ni {\bf N}}}}$, 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. \vskip 30pt \section*{\normalsize 3. General properties and asymptotics} \ni {\bf Proposition 3.1} {Let $M$ be a bijective multisubset of \ni {\bf Z}, $S$ a subset of \ni {\bf N}, $\pi:= \pi_{g}^{M,S}$, $D:= D_{\pi,S}$, $A:= A_{M,S}$, $B:= B_{M,S}$, $C:= C_{S}$. \ni (i) For any $M$ and $S$, $\pi$ satisfies the following properties: ${\cal U}1$: The difference function $d$ is non-decreasing on $A$ and non-increasing on $B$, ${\cal U}2$: $\pi$ is strictly increasing on each of $A$ and $B \cup C$. \ni (ii) $D$ is a greedy multiset and, if $S$ is infinite, then $D = M$ if and only if $M$ is greedy. Now suppose $S = {\hbox{\ni {\bf N}}}$ (hence $C$ is the empty set). Then \ni (iii) $\pi$ is the unique permutation of \ni {\bf N} with difference multiset $D$ which satisfies ${\cal U}1$ and ${\cal U}2$. \ni (iv) $\pi$ is an involution, i.e.: $\pi = \pi^{-1}$, if and only if $D$ is symmetric. If $M$ is symmetric and greedy, then $\pi$ is the unique involution on \ni {\bf N} with difference multiset $M$, which satisfies ${\cal U}1$ and ${\cal U}2$.} \ni {\it Proof}: Fix $M$ and $S$. We begin by establishing the following stronger form of property ${\cal U}1$: ${\cal U}$: Let $n \geq 1$. Let $\Delta_{n}:= \min \{k: k \geq 0 \; {\hbox{and}} \; \Xi_{n-1,k} < \zeta_{k} \}$, $\delta_{n}:= \max \{k: k \leq 0 \; {\hbox{and}} \; \Xi_{n-1,k} < \zeta_{k} \}$. Then $d(n) \in \{\delta_{n},\Delta_{n}\}$ if $n \in S$. We can establish ${\cal U}$ by induction on $n$. It holds trivially for $n = 1$, so suppose it holds for $1 \leq n^{\prime} < n$. If $n \in C$, there is nothing to prove. If $n \in A$, then $\cal U$ implies that no number $\geq n + \Delta_{n}$ has yet been chosen by $\pi$. But since $\pi$ chooses greedily, it is thus clear that $\pi(n) = n + \Delta_{n}$, so that $\cal U$ continues to hold in this case. \par Suppose $n \in B$. Now $\cal U$ guarantees that $\pi(n) \leq n + \delta_{n}$. It suffices to establish a contradiction to the assumption that $\pi(n) < n + \delta_{n}$. Let $k = k_{1} < n$ be such that $\pi(n) - k_{1} = \delta_{n}$. If $k_{1} \in S$ then ${\cal U}$ implies that $\pi(k_{1}) > \pi(n)$, contradicting the definition of $\pi$. So $k_{1} \in C$ and $\pi(k_{1}) < k_{1} + \delta_{n}$. Let $k_{2} < k_{1}$ be such that $\pi(k_{2}) - k_{1} = \delta_{n}$. Run through the same argument again to obtain the desired contradiction unless $k_{2} \in C$ and $\pi(k_{2}) < k_{2} + \delta_{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 ${\cal U}$, from which ${\cal U}1$ follows immediately, plus the fact that $\pi$ is increasing on $A$. Suppose $m,n \in B \cup C$, with $m < n$ and $\pi(m) > \pi(n)$. Then $m \in B$. Let $z = z_{1}:= m - [\pi(m)-\pi(n)]$. If $z_{1} \in B$ then, since $m \in B$, ${\cal U}$ implies that $\pi(z_{1}) > \pi(n)$, contradicting the definition of $\pi$. So $z_{1} \in C$ and hence $\pi(z_{1}) < \pi(n)$. We set $z_{2}:= z_{1} - [\pi(n) - \pi(z_{1})]$ and run through the same argument to obtain a contradiction unless $z_{2} \in C$ and $\pi(z_{2}) < \pi(z_{1})$. Iterating indefinitely we obtain, as above, an infinite decreasing sequence of elements of $C$, which is absurd. Thus we've established ${\cal U}2$ and hence part (i) of the proposition. Part (ii) follows easily from $\cal U$ and previous arguments. Turning to (iii), let $\tau$ be a permutation of \ni {\bf N} with $D_{\tau} = D_{\pi}$ which satisfies ${\cal U}1$ and ${\cal U}2$. Suppose $\pi \neq \tau$ and let $n_{0}$ be the smallest integer such that $\pi(n_{0}) \neq \tau(n_{0})$. First suppose $\pi(n_{0}) < n_{0}$. Since $\tau$ is surjective, there exists $n_{1} > n_{0}$ such that $\tau(n_{1}) = \pi(n_{0})$. Thus $d_{\tau}(n_{1}) < d_{\pi}(n_{0})$. But since $D_{\tau} = D_{\pi}$ and $\tau$ satisfies ${\cal U}1$, this implies the existence of some $n_{2} \in (n_{0},n_{1})$ such that $d_{\tau}(n_{2}) = d_{\pi}(n_{0})$. But then $\tau(n_{2}) > \tau(n_{1})$, contradicting the assumption that $\tau$ satisfies ${\cal U}2$. \par Finally, suppose $\pi(n_{0}) > n_{0}$. Then ${\cal U}1$ forces $\tau(n_{0}) < n_{0}$. But then, by ${\cal U}1$ again, we have a contradiction, since a greedy choice algorithm would rather have chosen $\tau(n_{0})$ in position $n_{0}$. Finally, it is trivial that if $\pi$ is an involution, then $D$ is symmetric. The rest of (iv) follows from (ii) and (iii) since, if $\pi$ satisfies ${\cal U}1$ and ${\cal U}2$, then so does $\pi^{-1}$. \ni {\bf Remark 1} Suppose $S = {\hbox{\ni {\bf N}}}$. For many multisets $M$, one can strengthen part (iii) of Proposition 3.1 to the following statement: \par {\em $\pi$ is the unique permutation of \ni {\bf N} with difference multiset $D$ which satisfies ${\cal U}$1; in particular, ${\cal U}1$ implies ${\cal U}2$}. Indeed, it is easily seen from the proof of (iii) that this is true for any multiset $M = (\zeta_{n})$ satisfying: if $\zeta_{n} \neq 0$ and $n < m < 0$ then $\zeta_{m} \neq 0$. A full classification of those $M$ for which this stronger statement of (iii) holds seems a rather messy exercise, however. \ni {\bf 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, $\pi_{g}$ will in general neither be the unique permutation satisfying properties $\cal U$1 and $\cal U$2, nor an involution when $M$ is symmetric. We leave aside the issue of determining for which $S$ such a generalisation does hold. \ni {\sc Example}: Let $M = {\hbox{\ni {\bf Z}}}$, $S = 2{\hbox{\ni {\bf N}}}$. The first few values of $\pi_{g}$ are given by \begin{tabular} {|c|c|c|c|c|c|c|c|c|c|c|c|} \hline {$n$} & {1} & {2} & {3} & {4} & {5} & {6} & {7} & {8} & {9} & {10} & {11} \\ \hline $\pi_{g}(n)$ & 1 & 2 & 3 & 5 & 4 & 8 & 6 & 7 & 9 & 13 & 10 \\ \hline $d(n)$ & 0 & 0 & 0 & 1 & -1 & 2 & -1 & -1 & 0 & 3 & -1 \\ \hline \end{tabular} \ni from which we immediately see that $\pi_{g}$ is not an involution. In addition, if $\sigma$ is the permutation of \ni {\bf N} which begins \begin{tabular} {|c|c|c|c|c|c|c|c|c|c|c|c|} \hline {$n$} & {1} & {2} & {3} & {4} & {5} & {6} & {7} & {8} & {9} & {10} & {11} \\ \hline $\sigma(n)$ & 1 & 2 & 3 & 5 & 4 & 8 & 6 & 11 & 7 & 9 & 10 \\ \hline $d(n)$ & 0 & 0 & 0 & 1 & -1 & 2 & -1 & 3 & -2 & -1 & -1 \\ \hline \end{tabular} \ni and then continues to choose greedily for all $n \geq 12$, then $\sigma$ will also satisfy properties $\cal U$1 and $\cal U$2. Next we turn to asymptotics. Let \begin{eqnarray*} L:= \limsup_{n \in {\hbox{\ni {\bf N}}}} {\pi(n) \over n} = \limsup_{n \in A} {\pi(n) \over n}, \\ l:= \liminf_{n \in {\hbox{\ni {\bf N}}}} {\pi(n) \over n} = \liminf_{n \in B \cup C} {\pi(n) \over n}. \end{eqnarray*} We seek sufficient conditions for both $L$ and $l$ to be finite limits, over $n \in A$ and $n \in B \cup C$ respectively. First we need a technical lemma. For $T = \left( \begin{array}{cc} a & b \\ c & d \end{array} \right) \in GL_{2}({\hbox{\ni {\bf C}}})$ we denote by $\mu_{T}: {\hbox{\ni {\bf C}}} \cup \{\infty\} \rightarrow {\hbox{\ni {\bf C}}} \cup \{\infty\}$ the M\"{o}bius transformation $\mu_{T}(z):= Tz:= {az + b \over cz+d}$. Recall that $T$ is said to be {\em hyperbolic} if the fixed-point equation $Tz=z$ has two distinct real solutions. \ni {\bf Lemma 3.2} {Let $r,s \in {\hbox{\ni {\bf R}}}_{> 0}$, $\delta \in (0,1]$ and set \begin{eqnarray*} a = a(\delta,r,s):= \left(1 + {1 \over rs} - {1 \over s} \right) + \left(1-{1 \over r} \right)\left( {1-\delta \over s} \right) = 1 - {\delta \over s} \left( 1 - {1 \over r} \right), \end{eqnarray*} \begin{eqnarray*} b = b(\delta,s):= {1 \over s} - {1 - \delta \over s} = {\delta \over s}, \\ c = c(r,s):= {1 \over r} + {1 \over rs} - {1 \over s}, \\ d = d(s):= 1 + {1 \over s}. \end{eqnarray*} Let $T = T_{\delta,r,s}:= \left( \begin{array}{cc} a & b \\ c & d \end{array} \right)$. Then for any choice of $r,s$ and $\delta$, the following hold: \ni (i) det$(T) = 1 - {1 - \delta \over s}$. $T$ is hyperbolic with a unique fixed point $\alpha = \alpha_{T}$ in $[0,\delta]$ which is neither 0 nor $\delta$. \\ (ii) Let $(x_{n})_{n=1}^{\infty}$ be a sequence of positive real numbers such that for any $\epsilon > 0$, $x_{n} \in (0,\delta + \epsilon)$ for all sufficiently large $n$, and suppose the $x_{n}$ satisfy a recurrence \begin{eqnarray*} x_{n+1} = T_{n} x_{n}, \;\;\;\;\;\; n \geq 1, \end{eqnarray*} where $T_{n} = \left( \begin{array}{cc} a_{n} & b_{n} \\ c_{n} & d_{n} \end{array} \right) \in GL_{2}({\hbox{\ni {\bf R}}})$ is such that $c_{n} = c$, $d_{n} = d$ for all $n$ and $a_{n} \rightarrow a$, $b_{n} \rightarrow b$ as $n \rightarrow \infty$. Then $x_{n} \rightarrow \alpha$.} \ni {\it Proof}: That det$(T) = 1 - \frac{1-\delta}{s}$ is easily verified. Next, \begin{eqnarray*} ({\hbox{tr}} \; T)^{2} - 4({\hbox{det}} \; T) = \left( {\delta - 1 \over s} \right)^{2} + {2\delta(1-\delta) \over rs^{2}} + \left( 2 + {\delta \over rs} \right)^{2} - 4 > 0, \end{eqnarray*} 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,\delta]$ and is neither $0$ nor $\delta$. (ii) This is probably a simple exercise for anyone familiar with the (elementary) theory of iteration of M\"{o}bius transformations, but we give a proof for the sake of completeness. For convenience, we let all suffixes $n$ range over ${\hbox{\ni {\bf N}}} \cup \{\infty\}$, where $n = \infty$ refers to the matrix $T$, its entries, fixpoints etc. Denote the other fixpoint of $T$ by $\beta$, so $\beta \in {\hbox{\ni {\bf R}}} \backslash [0,\delta]$. Without loss of generality, each $T_{n}$ is hyperbolic with fixpoints $\tau_{1,n}, \tau_{2,n} \in {\hbox{\ni {\bf R}}} \cup \{\infty\}$ such that $\tau_{1,n} \in (0,\delta)$ and $\tau_{2,n} \not\in [0,\delta]$ for all $n$ and $\tau_{1,n} \rightarrow \alpha$, $\tau_{2,n} \rightarrow \beta$. Let $P_{n}:= \left( \begin{array}{cc} 1 & - \tau_{1,n} \\ 0 & 1 \end{array} \right)$ or $\left( \begin{array}{cc} 1 & - \tau_{1,n} \\ 1 & - \tau_{2,n} \end{array} \right)$ according as $\tau_{2,n} = \infty$ or otherwise. Note that, since the $c$-entry of $T_{n}$ is fixed, then $\beta = \infty \Leftrightarrow c = 0 \Leftrightarrow \tau_{2,n} = \infty$ for all $n$. \par For all $z \in {\hbox{\ni {\bf C}}} \cup \{\infty\}$, $\mu_{P_{n}T_{n}P_{n}^{-1}}(z) = \kappa_{n} z$ for some $\kappa_{n} \in {\hbox{\ni {\bf R}}}_{> 0} \backslash \{1\}$ such that $\kappa_{n} \rightarrow \kappa_{\infty}$. There are two cases, namely $\kappa_{\infty} < 1$ and $\kappa_{\infty} > 1$. In either case, we may also assume without loss of generality that each $\kappa_{n}$ satisfies the same inequality and that there exists $\epsilon > 0$ such that $|\kappa_{n} - 1| > \epsilon$ for all $n$. \par Now $x_{n} \rightarrow \alpha$ if and only if $P_{n} x_{n} \rightarrow 0$. We have \begin{eqnarray} P_{n+1}x_{n+1} = P_{n}x_{n+1} + \left( P_{n+1}x_{n+1} - P_{n} x_{n+1} \right) \\ \nonumber = P_{n} T_{n} x_{n} + \left( P_{n+1}x_{n+1} - P_{n} x_{n+1} \right) \\ \nonumber = (P_{n}T_{n}P_{n}^{-1})(P_{n}x_{n}) + \left( P_{n+1} x_{n+1} - P_{n} x_{n+1} \right) \\ \nonumber = \kappa_{n} (P_{n} x_{n}) + \left( P_{n+1}x_{n+1} - P_{n} x_{n+1} \right). \end{eqnarray} Note that since $P_{n} \rightarrow P_{\infty}$ and the $x_{n}$ are assumed to be bounded, it follows that $| P_{n+1}x_{n+1} - P_{n}x_{n+1} | \rightarrow 0$. First suppose $\kappa_{\infty} < 1$. Applying the triangle inequality to (5) gives \begin{eqnarray*} |P_{n+1}x_{n+1}| \leq (1-\epsilon) |P_{n}x_{n}| + \delta_{n}, \end{eqnarray*} where $\delta_{n} \rightarrow 0$, from which it is easily deduced that $P_{n} x_{n} \rightarrow 0$, as desired. Finally, suppose $\kappa_{\infty} > 1$. This time, the triangle inequality gives \begin{eqnarray*} |P_{n+1}x_{n+1}| \geq (1+\epsilon)|P_{n}x_{n}| - \delta_{n}, \end{eqnarray*} which is easily seen to leave only two possibilities: either $P_{n} x_{n} \rightarrow 0$ or $P_{n} x_{n} \rightarrow \infty$. But the latter would imply that $x_{n} \rightarrow \beta$, which is impossible, since $\lim x_{n}$, if it exists, must by hypothesis lie in $[0,\delta]$. This completes the proof. We now come to the main result of this section: \ni {\bf Theorem 3.3} {Let $M$ be a finitary multiset and suppose $d(M_{+})$ and $d(M_{-})$ both exist in $(0,\infty)$, say equal to $r/2$ and $s/2$ respectively. Let $S \subseteq {\hbox{\ni {\bf N}}}$ be a set with asymptotic density $\delta/2 > 0$ (considered as a multisubset of \ni {\bf Z} also). Let $\alpha \in (0,\delta)$ be a fixpoint of $T_{\delta,r,s}$ as in Lemma 3.2. Then the following hold for $\pi:= \pi_{g}^{M,S}$: \begin{eqnarray*} L = \lim_{n \in A} {\pi(n) \over n}, \;\; {\hbox{i.e., the limit exists}}, \\ l = \lim_{n \in B \cup C} {\pi(n) \over n}, \;\; {\hbox{i.e., the limit exists}}, \end{eqnarray*} \begin{eqnarray} L = 1 + {\alpha \over r}, \\ l = 1 - {\delta-\alpha \over s}. \end{eqnarray}} \ni {\it Proof}: The main point is to prove that the limits exist - eqs. (6) and (7) will then follow easily. \par We denote $M_{+} = (\mu_{n})_{0}^{\infty}$, $M_ = (\nu_{n})_{-1}^{-\infty}$ and, for each $n \geq 1$, $a_{n}:= \max \{A \cap [1,n]\}$, $b_{n}:= \max \{ B \cap [1,n]\}, c_{n}:= \max \{ C \cap [1,n]\}$ and \begin{eqnarray*} \alpha_{n}:= {|A \cap [1,n]| \over n}. \end{eqnarray*} The main task will be to show that $\alpha_{n} \rightarrow \alpha$ as $n \rightarrow \infty$. We begin by establishing a couple of claims. \ni {\em Claim 1}: $a_{n} \sim n$ and $b_{n} \sim n$. First consider $a_{n}$. We have $(a_{n},n] \subset B \cup C$. Property ${\cal U}2$ implies that $d_{\pi}$ is constant on $(a_{n},n]$, with value $d_{0} < 0$, say. Then unless $a_{n} \sim n$ we'll get the contradiction that $\nu_{d_{0}} = \Theta(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} \rightarrow \infty$ such that $n_{l} - b_{n_{l}} = \Theta(n_{l})$. Let us assume that $c_{n_{l}} \sim n_{l}$ as otherwise the argument becomes much simpler (note that such a situation can only arise a priori if $\delta = 1$). The aim now will be to produce a subsequence $(l^{\prime}) \subseteq (l)$ and intervals $I_{l^{\prime}} \subseteq [1,n_{l^{\prime}}]$ such that \par (i) $|I_{l^{\prime}}| = \Theta(n_{l^{\prime}})$, \par (ii) $|I_{l^{\prime}} \cap \pi(A)| \gtrsim \delta |I_{l^{\prime}}|$. First suppose we have such a sequence of intervals - we can obtain a contradiction from this. Fix $l^{\prime}$. Let \begin{eqnarray*} \pi(q):= \min \{I_{l^{\prime}} \cap \pi(A) \}, \\ \pi(Q):= \max \{I_{l^{\prime}} \cap \pi(A) \}. \end{eqnarray*} Let $K_{l^{\prime}}:= [q,Q] \subseteq [1,n_{l^{\prime}}]$. Then ${\cal U}1$ implies that $|K_{l^{\prime}} \cap A| = |I_{l^{\prime}} \cap \pi(A)|$. In particular, $|K_{l^{\prime}}| = \Theta(n_{l^{\prime}})$. That $d(M_{+}) = \frac{r}{2} > 0$ implies that (as $l^{\prime} \rightarrow \infty$) \begin{eqnarray*} [\pi(Q)-Q] - [\pi(q)-q] \sim {|I_{l^{\prime}} \cap \pi(A)| \over r} \gtrsim {\delta \over r} |I_{l^{\prime}}|, \end{eqnarray*} hence \begin{eqnarray*} |K_{l^{\prime}}| = 1 + (Q-q) \lesssim |I_{l^{\prime}}| \left( 1 - {\delta \over r} \right). \end{eqnarray*} It follows that \begin{eqnarray*} {|K_{l^{\prime}} \cap A| \over |K_{l^{\prime}}|} \gtrsim {\delta \cdot |I_{l^{\prime}}| \over \left( 1 - {\delta \over r} \right) \cdot |I_{l^{\prime}}|} = \delta+|\Theta(1)|. \end{eqnarray*} But since $|K_{l^{\prime}}| = \Theta(n_{l^{\prime}})$, this contradicts the fact that $S$ has density $\delta/2$. So it remains to find the intervals $I_{l^{\prime}}$. We divide the analysis into two cases: \ni {\sc Case I}: $[\pi(c_{n_{l}}) - \pi(b_{n_{l}})] \sim (c_{n_{l}} - b_{n_{l}})$. In this case, take $I_{l}:= (\pi(b_{n_{l}}),\pi(c_{n_{l}})]$, so that (i) is satisfied. By ${\cal U}2$, $I_{l} \cap \pi(B) = \phi$. But \begin{eqnarray*} |I_{l} \cap \pi(C)| = |(b_{n_{l}},c_{n_{l}}] \cap C| \sim (1-\delta) (c_{n_{l}} - b_{n_{l}}) \sim (1-\delta) |I_{l}|, \end{eqnarray*} so (ii) is also satisfied. \ni {\sc Case II}: We can find a sequence $(l^{\prime}) \subseteq (l)$ such that $[\pi(c_{n_{l^{\prime}}}) - \pi(b_{n_{l^{\prime}}})] \lesssim (1-\Theta(1))(c_{n_{l^{\prime}}}-b_{n_{l^{\prime}}})$. Then \begin{eqnarray*} c_{n_{l^{\prime}}} = d(b_{n_{l^{\prime}}}) + \pi(c_{n_{l^{\prime}}}) + \Theta(n_{l^{\prime}}). \end{eqnarray*} Let $\tau_{l^{\prime}}$ be the smallest integer such that $\Xi_{b_{n_{l^{\prime}}},d(b_{n_{l^{\prime}}}) - \tau_{l^{\prime}}} < \nu_{d(b_{n_{l^{\prime}}})-\tau_{l^{\prime}}}$. Since $d(M_{-}) > 0$, we can be sure that $\tau_{l^{\prime}} = o(n_{l^{\prime}})$. Set \begin{eqnarray*} \chi_{l^{\prime}}:= d(b_{n_{l^{\prime}}}) + \pi(c_{n_{l^{\prime}}}) + \tau_{l^{\prime}} + 1, \;\;\;\;\;\; I^{1}_{l^{\prime}}:= [\chi_{l^{\prime}},n_{l^{\prime}}], \;\;\;\;\;\; I^{2}_{l^{\prime}}:= I^{1}_{l^{\prime}} - \left[ \tau_{l^{\prime}} + d(b_{n_{l^{\prime}}}) \right]. \end{eqnarray*} Then $|I^{1}_{l^{\prime}}| = |I^{2}_{l^{\prime}}| = \Theta(n_{l^{\prime}})$ and, since $\chi_{l^{\prime}} > b_{n_{l^{\prime}}}$, we have $I^{1}_{l^{\prime}} \subset A \cup C$. Thus, since $d(S) = \delta/2$, we have that $|I^{1}_{l^{\prime}} \cap A| \sim \delta |I^{1}_{l^{\prime}}|$. But furthermore, since $\pi$ chooses greedily, it must be the case that for every $x \in I^{1}_{l^{\prime}} \cap A$, $x - [\tau_{l^{\prime}} + d(b_{n_{l^{\prime}}})] \in I^{2}_{l^{\prime}} \cap \pi(A)$. Thus we can finally take $I_{l^{\prime}} = I^{2}_{l^{\prime}}$ in this case, and {\em Claim 1} is proven. \ni {\em Claim 2}: \begin{eqnarray} \pi(a_{n}) \sim n \left( 1 + {\alpha_{n} \over r} \right), \\ \pi(b_{n}) \sim n \left( 1 - {\delta - \alpha_{n} \over s} \right). \end{eqnarray} We have $\pi(a_{n}) = a_{n} + d(a_{n})$. We already know that $a_{n} \sim n$. But ${\cal U}1$ and the assumption that $d(M_{+}) = r/2$ imply that $d(a_{n}) \sim {\alpha_{n}n \over r}$. This proves (8). The proof of (9) is similar. By ${\cal U}2$ we know that \begin{eqnarray*} \pi(a_{n}) - \alpha_{n}n = \# \{x \in B \cup C: \pi(x) \leq \pi(a_{n}) \}. \end{eqnarray*} From Claim 2 we know that \begin{eqnarray} \pi(a_{n}) - \alpha_{n} n \sim n \left( 1 + {\alpha_{n} \over r} - \alpha_{n} \right). \end{eqnarray} Set \begin{eqnarray*} y = y(n):= \max \{x \in B \cup C: \pi(x) \leq \pi(a_{n}) \}. \end{eqnarray*} Now $y = \pi(y) + |d(y)|$. Clearly, $\pi(y) \sim \pi(a_{n})$. From {\em Claim 1} and ${\cal U}1$ we also see easily that \begin{eqnarray*} |d(y)| \sim {1 \over s} [\pi(a_{n}) - \alpha_{n} n - (1-\delta)y], \end{eqnarray*} and hence, by (8) and (10), that \begin{eqnarray} {y(n) \over n} \sim {\left( 1 + {1 \over s} \right)\left( 1 + {\alpha_{n} \over r} \right) - {\alpha_{n} \over s} \over 1 + {1-\delta \over s}} = 1+\Theta(1). \end{eqnarray} Relations (10) and (11) imply that \begin{equation} \alpha_{y(n)} \sim 1 - {\left(1 + {\alpha_{n} \over r} - \alpha_{n}\right) \left( 1 + {1-\delta \over s}\right) \over \left( 1 + {1 \over s} \right)\left( 1 + {\alpha_{n} \over r} \right) - {\alpha_{n} \over s}}. \end{equation} Now let $N$ be some very large fixed positive integer. We define a sequence $(x_{k,N})_{k=1}^{\infty}$ of rational numbers in $(0,1)$ and a sequence $(z_{k,N})_{k=1}^{\infty}$ of natural numbers tending to infinity by \begin{eqnarray} x_{1,N}:= \alpha_{N}, \;\;\;\; z_{1,N}:= y(N), \\ \nonumber x_{k+1,N}:= \alpha_{z_{k,N}}, \;\;\;\; z_{k+1,N}:= y(z_{k,N}) \;\; \forall \; k \geq 1. \end{eqnarray} Lemma 3.2 implies that $x_{k,N} \rightarrow \alpha$ as $k \rightarrow \infty$. By (11), this in turn implies that ${z_{k+1,N} \over z_{k,N}} \rightarrow 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 $\alpha_{n} \sim \alpha$: for sufficiently large $n$ one can compare $\alpha_{n}$ and $\alpha_{z_{k,N}}$ for some $N$ such that $n/N \approx c^{k}$ and both $k$ and $N$ are also sufficiently large. We omit any further details. From the knowledge that $\alpha_{n}$ converges to $\alpha$, the whole of Theorem 3.3 follows easily. Indeed, (8) implies (6) and (9) implies (7), so the proof is complete. \ni {\bf Remark} Given $M$ and $S$ satisfying the hypotheses of Theorem 3.3, a permutation $\tau$ of \ni {\bf N} for which $D_{\tau,S} \leq M$ and $L,l$ as in (6) and (7), one may show that \begin{eqnarray*} \limsup_{n \in {\hbox{\ni {\bf N}}}} {\tau(n) \over n} \geq L, \;\;\;\;\;\; \liminf_{n \in {\hbox{\ni {\bf N}}}} {\tau(n) \over n} \leq l. \end{eqnarray*} 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 = {\hbox{\ni {\bf N}}}$. In particular, $\delta = 1$ in Theorem 3.3. In the special case that $r = s = 2d$, say, then (6) and (7) imply that \begin{equation} L - l = {1 \over d}. \end{equation} One may check that the fixpoint $\alpha$ is given by \begin{equation} \alpha = {1 \over 2} \left[ (1-2d) + \sqrt{1+4d^{2}} \right] \end{equation} and hence that \begin{equation} L = {1 \over l}. \end{equation} 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 $\pi$ 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. \ni {\bf Proposition 3.4} {Suppose $M$ is finitary and symmetric. Suppose $L:= \lim_{n \in A} {\pi(n) \over n}$ exists and that $L > 1$. Then $M$ has asymptotic density $d:= (L - {1 \over L})^{-1}$.} \vskip 30pt \section*{\normalsize 4. Interspersion arrays} Let $M = (\zeta_{n})_{-\infty}^{\infty}$ be a symmetric, greedy multiset with $\zeta_{0} < \infty$. We shall describe below two simple, and very similar, algorithms for constructing an interspersion array from $\pi_{g}^{M} = \pi_{g}^{M,{\hbox{\ni {\bf N}}}}$. In the case when $M = {\hbox{\ni {\bf 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 = m{\hbox{\ni {\bf Z}}}$, for any $m > 0$). When $M$ is finitary, each array will contain infinitely many rows, whereas if $\zeta_{k} = \infty$, 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 {\em general-difference Wythoff array} and {\em general-difference dual Wythoff array} respectively{\footnote{The reason why we do not simply call the arrays $\lq$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.}}. We denote by $\cal A$ (resp. ${\cal A}^{*}$) the algorithms for producing $W$ (resp. $W^{*}$). We shall now proceed with a formal description of $\cal A$, including proofs that it produces an array with the desired properties. We then give a short description of ${\cal A}^{*}$ and, since it is very similar, we omit details of the equally similar proofs, merely stating the corresponding results. To describe $\cal A$, we begin by removing any zeroes from the multiset $M$. That is, we take $M^{\prime} = (\zeta^{\prime}_{n})_{- \infty}^{\infty}$ to be the multiset given by $\zeta^{\prime}_{n}:= \zeta_{n}$ if $n \neq 0$, and $\zeta^{\prime}_{0}:= 0$. Observe that there is a simple relation between $\pi_{g}^{M}$ and $\pi_{g}^{M^{\prime}}$, namely \begin{eqnarray} \pi_{g}^{M}(i) = i \;\; {\hbox{for $1 \leq i \leq \zeta_{0}$}}, \;\;\;\; \pi_{g}^{M}(i) = \pi_{g}^{M^{\prime}}(i-\zeta_{0}) + \zeta_{0} \;\; {\hbox{for $i > \zeta_{0}$}}. \end{eqnarray} Now set $\pi:= \pi_{g}^{M^{\prime}}$, $A:= A_{M^{\prime}}$, $B:= B_{M^{\prime}}$. Let $1=u_{1} < u_{2} < u_{3} < \cdots$ be the elements of $A$ arranged in increasing order. Since $M^{\prime}$ is symmetric, we have $B = \pi(A)$ and ${\cal U}2$ implies that $i < j \Leftrightarrow \pi(u_{i}) < \pi(u_{j})$. The algorithm $\cal A$ is a recursive procedure for inserting the pairs $(u_{i},\pi(u_{i}))$ one-by-one into the array $W$. At the $n$:th step it inserts the pair $(u_{n},\pi(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: \ni {\sc Step 1}: Set $w_{1,1}:= u_{1}$, $w_{1,2}:= \pi(u_{1})$. \ni {\sc $n^{\mathrm{TH}}$ Step for each $n > 1$}: Each of the pairs $(u_{i},\pi(u_{i}))$, for $1 \leq 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},\pi(u_{n}))$. Define $\gamma = \gamma(n)$ to be the smallest amongst the numbers appearing at the right-hand edge of each row of $W_{n}$ (so $\gamma(n) = \pi(u_{i})$ for some $n - r_{n} \leq i < n$). Let $\xi = \xi(n)$ be defined by $u_{\xi(n)} < \gamma(n) < u_{\xi(n)+1}$. Let \begin{eqnarray*} \theta = \theta_{n}:= \gamma(n) + \left[ \pi(u_{\xi(n)}) - u_{\xi(n)} \right]. \end{eqnarray*} We claim that $\theta_{n} = u_{m}$ for some $m = m(n) \geq n$. For the moment, let us assume this. Then the algorithm $\cal A$ does the following: \ni (i) If $m > n$ then it assigns $w_{r_{n}+1,1}:= u_{n}$, $w_{r_{n}+1,2}:= \pi(u_{n})$. \\ (ii) If $m = n$, then suppose $\gamma(n)$ appears in the $t$:th row, say $\gamma(n) = w_{t,2j}$. Then we assign $w_{t,2j+1}:= u_{n}$, $w_{t,2j+2}:= \pi(u_{n})$. To verify that the algorithm is well-defined, it remains to prove the claim above. First we show that $\theta \not\in B$. For suppose $\theta = \pi(u_{j})$. Since $u_{\xi} < \gamma$ we have $\theta > \pi(u_{\xi})$ and hence $j > \xi$. By definition of $\xi$, this implies that $u_{j} > \gamma$. But then $\pi(u_{j}) - \gamma = \pi(u_{\xi}) - u_{\xi} > \pi(u_{j}) - u_{j}$, which contradicts property ${\cal U}1$. \par So now we know that $\theta_{n} = u_{m(n)}$ for some $m(n)$. It remains to show that $m(n) \geq n$. This, and the accompanying fact that $\cal A$ is well-defined, are easily achieved by induction on $n$. Clearly, the result holds for $n = 2$, so suppose $n > 2$ and that $\cal A$ is well-defined at all previous steps. By definition of $\cal A$, either $m(n-1) = n-1$, in which case $\gamma(n) > \gamma(n-1)$ and hence $\theta_{n} > \theta_{n-1}$ and $m(n) > m(n-1)$ as required, or $m(n-1) \geq n$, in which case $\gamma,\eta$ and $\theta$ are all unchanged at the $n$:th step and $m(n) = m(n-1) \geq n$, as required. We now turn to proving the various properties of the array $W$. The main property of interest is \ni {\bf 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 $\zeta_{k} = \infty$ then $W$ will contain exactly $k$ non-empty rows.} \ni {\it 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). \par Of the four properties of an interspersion array listed in Section 1, the first is obvious, the second follows from the fact that $\theta_{n} > \gamma(n)$ for any $n$, and the third is also a simple consequence of the rules followed by $\cal A$. So it remains to verify the interspersion property. So let $i,j,p,q \in {\hbox{\ni {\bf 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. \ni {\sc Case I}: $p,q$ both odd. Then $w_{i,p} = u_{x}$ and $w_{j,q} = u_{y}$ for some $x \neq y$. The assumption is that \begin{eqnarray} u_{x} < u_{y} < \pi(u_{x}), \end{eqnarray} and from this we want to deduce that \begin{eqnarray} \pi(u_{x}) < \pi(u_{y}) < u_{z}, \end{eqnarray} where \begin{eqnarray} u_{z} = \pi(u_{x}) + \pi(u_{\xi}) - u_{\xi} \;\;\; {\hbox{and}} \;\;\; u_{\xi} < \pi(u_{x}) < u_{\xi+1}. \end{eqnarray} 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 \leq \xi$ and hence, by ${\cal U}1$, that $\pi(u_{y})-u_{y} \leq \pi(u_{\xi}) - u_{\xi}$. But then, by (20), we have that $\pi(u_{y}) - u_{y} \leq u_{z} - \pi(u_{x})$, which suffices to give the right side of (19). \par This completes the proof of Theorem 4.1. We now briefly describe the construction of the dual array $W^{*}$. The algorithm ${\cal A}^{*}$ first constructs an array $\Omega = (\omega_{i,j})$ which will need to be modified very slightly to produce $W^{*}$ if $\zeta_{0} > 0$. Namely, ${\cal A}^{*}$ begins by setting $\omega_{1,2j-1}=\omega_{1,2j}=j$ for $1 \leq j \leq \zeta_{0}$. This time we let $u_{1} < u_{2} < u_{3} < \cdots$ denote, in increasing order, the sequence of elements of $A_{M} \backslash \{1,...,\zeta_{0}\}$. ${\cal A}^{*}$ now proceeds to insert the pairs $(u_{i},\pi(u_{i}))$ into the array $\Omega$ according to exactly the same rules as $\cal A$, with the only difference being that, this time, the function $\xi(n)$ is defined by \begin{eqnarray*} u_{\xi(n)-1} < \gamma(n) < u_{\xi(n)}. \end{eqnarray*} The array $W^{*}$ may now only differ from $\Omega$ in the first row. Namely, we take \begin{eqnarray*} w^{*}_{i,j}:= \left\{ \begin{array}{lr} \omega_{i,j}, & {\hbox{if $i > 1$}}, \\ j, & {\hbox{if $i = 1$, $1 \leq j \leq \zeta_{0}$}}, \\ \omega_{1,j+\zeta_{0}}, & {\hbox{if $i = 1$, $j > \zeta_{0}$}}. \end{array} \right. \end{eqnarray*} We omit the proof of the following result: \ni {\bf Proposition 4.2} {$W^{*}$ is an interspersion array. It has infinitely many rows if $M$ is finitary and exactly $k$ rows if $\zeta_{k} = \infty$.} \ni {\bf 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 $\lq$extremes', in the following sense. Let the notation be as in the definition of the algorithm $\cal A$. Fix $n$ and a choice of an integer $\Delta_{n} \in [\delta_{\xi(n)},\delta_{\xi(n)+1}]$. If we take $\theta_{n}:= \gamma(n) + \Delta_{n}$ then the same argument as before gives that $\theta_{n} = u_{m(n)}$ for some $m(n) \geq n$. Hence, provided we don't vary our choice of $\Delta_{n}$ as long as $m(n) > n$, one can insert the pairs $(u_{i},\pi(u_{i}))$ in an array according to the same rules as for $\cal 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 $\zeta_{0}$). We omit further details. Clearly, $W$ and $W^{*}$ correspond respectively to the choices $\Delta_{n} = \delta_{\xi(n)}$ (resp. $\Delta_{n}=\delta_{\xi(n)+1}$) for all $n$. We close this section by proving: \ni {\bf Proposition 4.3} {If $M = {\hbox{\ni {\bf Z}}}$ then $W$ is the Wythoff/Zeckendorff array and $W^{*}$ is its dual}. \ni {\it Proof}: We give the proof for $W$ only; the proof for $W^{*}$ is similar. \par Let $\pi:= \pi_{g}^{M^{\prime}}$, $A:= A_{M^{\prime}}$. From (2) and (17) it easily follows that \begin{equation} \pi(u) = \lceil \phi u \rceil \;\;\; {\hbox{for every $u \in A$}}. \end{equation} 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: \par (i) for each $i > 1$, $w_{i,1}$ is the smallest natural number not appearing in the previous rows, \par (ii) for every $i \geq 1$ and $j \geq 3$, $w_{i,j} = w_{i,j-1} + w_{i,j-2}$. \\ Now (i) is a trivial consequence of the rules for the algorithm $\cal A$, so we concentrate on (ii). We consider two cases, depending on whether $j$ is odd or even. \ni {\sc Case I}: $j$ odd. Then there exist $u_{1} \leq u_{2} \leq u_{3} \in A$ such that $w_{i,j-2} = u_{1}$, $w_{i,j-1} = \pi(u_{1})$ and $w_{i,j} = u_{3} = \pi(u_{1}) + \left[ \pi(u_{2}) - u_{2}\right]$, where $u_{2} = \max \{A \cap [1,\pi(u_{1})) \}$. Since $M = {\hbox{\ni {\bf Z}}}$, it is clear that $u_{2} = \pi(u_{1})-1$ (i.e.: no two consecutive integers can lie in $B = \pi(A)$). Thus $u_{3} = \pi[\pi(u_{1})-1]+1$ and we need to show that \begin{eqnarray*} \pi[\pi(u_{1})-1] + 1 = u_{1} + \pi(u_{1}). \end{eqnarray*} But this follows from (21) and [8], Lemma 1.3. \ni {\sc 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. \par This completes the proof of Proposition 4.3. \ni {\bf Remark} One may equally well show that for any $m \geq 1$, if $M = m{\hbox{\ni {\bf Z}}}$, 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 \geq 1$ and $j \geq 3$, for which one uses (2) and (4), seems rather messy however, so we do not include it. \vskip 30pt \section*{\normalsize 5. The multisets ${\cal M}_{m,p}$} Let $m,p \geq 1$ be any fixed positive integers. We now seek further results for the multiset ${\cal M}_{m,p} = (\zeta^{m,p}_{n})$ where $\zeta^{m,p}_{n}:= p$ if $m | n$ and $\zeta^{m,p}_{n} = 0$ otherwise. We denote $\pi_{m,p}:= \pi_{g}^{{\cal M}_{m,p},{\hbox{\ni {\bf N}}}}$. ${\cal M}_{m,p}$ has density $p/m$ and is finitary and symmetric. Hence, by Proposition 3.1, $\pi_{m,p}$ is an involution, and by Theorem 3.3 the limits $L$ and $l$ exist and are given by \begin{eqnarray} L^{2} - {m \over p} L - 1 = 0 \; \Rightarrow \; L = {m + \sqrt{m^{2} + 4p^{2}} \over 2p}, \\ l = {1 \over L} = L - {m \over p}. \end{eqnarray} \ni {\bf $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,\pi_{m,p}(n)-1)$ for $n \geq 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 $\lq$block' some of the possible moves of {\sc 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} \leq \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 ${\cal U}1$, the P-positions of the game are precisely the configurations $(n-1,\pi_{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. \ni {\bf Beatty sequences} There is a simple reason why, for any $p > 1$, it won't be possible to express the pairs $(n,\pi_{m,p}(n))$ as $(\lceil n r \rceil, \lceil n s \rceil)$ 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 {\em in standard form} if $x \leq y$. Two ordered pairs $(n_{1},\pi_{m,p}(n_{1}))$ and $(n_{2},\pi_{m,p}(n_{2}))$, in standard form, are said to be {\em consecutive} if $n_{1} < n_{2}$ and there is no pair $(n_{3},\pi_{m,p}(n_{3}))$ in standard form such that $n_{1} < n_{3} < n_{2}$. \par Now the point is that, for any $p > 1$, there may exist consecutive pairs $(n_{1},\pi_{m,p}(n_{1}))$ and $(n_{2},\pi_{m,p}(n_{2}))$ for which $n_{2} - n_{1}$ is any integer in \\ $\{1,...,p+1\}$. On the other hand, for any real $\alpha$ and integer $n$, the difference $\lceil (n+1) \alpha \rceil - \lceil n \alpha \rceil$ can attain one of only two possible values. \par Nevertheless, there does appear to be a close relationship between all the permutations $\pi_{m,p}$ and Beatty sequences. Here we content ourselves with conjecturing a weak form of this relationship: \ni {\bf Conjecture 5.1} { Fix $m,p \geq 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 \geq 1$, $\pi_{m,p}(n)$ differs from one of the numbers $\lfloor nL \rfloor$ and $\lfloor nl \rfloor$ 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, $\pi(n) = \lfloor nl \rfloor$ or $\lfloor nL \rfloor - j$ for some $0 \leq 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 \leq 5$, we have checked that, for all $n \leq 10,000$, $\pi_{1,p}(n)$ is one of the four numbers $\lfloor nL \rfloor$, $\lceil nL \rceil$, $\lfloor nl \rfloor$, $\lceil nl \rceil$. \par A thorough analysis of the connection between the permutations $\pi_{m,p}$ and Beatty sequences is left for future work. \vskip 30pt \section*{\normalsize 6. The case $S = k{\hbox{\ni {\bf N}}}$} We now briefly return to the setting of more general subsets $S$ of \ni {\bf N}. Whenever we can compute the asymptotics of $\pi_{g}$, i.e.: the limits $L$ and $l$, it makes sense to ask if there is a closer relationship between the sequences $(\pi_{g}(n))_{n\in A}$ and $(\pi_{g}(n))_{n\in B}$, and the sequences $\lfloor nL \rfloor$ and $\lfloor nl \rfloor$ respectively (which are Beatty sequences unless $L$ and/or $l$ are rational). For the example introduced earlier $(M={\hbox{\ni {\bf Z}}}, S=2{\hbox{\ni {\bf N}}})$, 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 \begin{eqnarray*} \epsilon_{n}:= \sqrt{3} n - \lfloor \sqrt{3} n \rfloor. \end{eqnarray*} Set \begin{eqnarray*} \eta:= 2 - \sqrt{3}, \end{eqnarray*} and observe that, for all $n$, \begin{equation} \epsilon_{n} - \epsilon_{n+1} \equiv \eta \; ({\hbox{mod $1$}}). \end{equation} Let \begin{eqnarray*} 0 = n_{0} < n_{1} < n_{2} < \cdots \end{eqnarray*} denote the sequence of non-negative integers for which $\epsilon_{n_{i}} < \eta$. The interval $[2n_{i-1},2n_{i})$ will be called the $i$:th {\em period}. \ni {\bf Theorem 6.1} {Let $M={\hbox{\ni {\bf Z}}}$, $S=2{\hbox{\ni {\bf N}}}$, $\pi:= \pi_{g}^{M,S}$. Define a function $f = f_{2}: {\hbox{\ni {\bf N}}} \rightarrow {\hbox{\ni {\bf N}}}$ as follows: (I) for any $n \geq 1$, $f(2n-1):= \min \{ t: t \neq f(i) \; {\hbox{for any $i \leq 2n-2$}} \}$. (II) for any $n \geq 1$, \begin{eqnarray*} f(2n):= n + \lfloor \sqrt{3}n \rfloor, \;\;\; {\hbox{if $\epsilon_{n} > \eta$ and $\epsilon_{n-1} > \eta$}}, \end{eqnarray*} \begin{eqnarray*} f(2n):= n + \lfloor \sqrt{3} n \rfloor, \;\;\; {\hbox{if $\epsilon_{n} < \eta$ and $\lfloor \sqrt{3} n \rfloor \in \{ f(i): i < 2n \}$}}, \end{eqnarray*} \begin{eqnarray*} f(2n):= \lfloor \sqrt{3} n \rfloor, \;\;\; {\hbox{if $\epsilon_{n} < \eta$ and $\lfloor \sqrt{3} n \rfloor \not\in \{ f(i): i < 2n \}$}}, \end{eqnarray*} \begin{eqnarray*} f(2n):= n + \lfloor \sqrt{3} n \rfloor, \;\;\; {\hbox{if $\epsilon_{n-1} < \eta$ and $f(2n-2) = \lfloor \sqrt{3}(n-1) \rfloor$}}, \end{eqnarray*} \begin{eqnarray*} f(2n):= \lfloor \sqrt{3} n \rfloor + 2, \;\;\; {\hbox{otherwise, i.e.: iff $\epsilon_{n-1} < \eta$ and $\lfloor \sqrt{3}(n-1) \rfloor \in \{ f(i): i < 2n-2 \}$}}. \end{eqnarray*} Then $f \equiv \pi$}. \ni {\bf Remark}: It is clear that the function $f$ is a well-defined permutation of \ni {\bf N}. Since, for this pair $M,S$, we have $r=s=1$ and $\delta = \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 \in A$, $\pi(n) = \lfloor nL \rfloor$, and for all $n \in B$, $\pi(n) = \lfloor nl \rfloor$ or $\lfloor nl \rfloor + 2$. The behaviour of $\pi(n)$ for $n \in C$ seems to be a bit more erratic, though from ${\cal U}2$ we can deduce, for example, that $|\pi(n) - \lfloor nl \rfloor| \leq 2$ for all $n \in C$. In the proof to follow, the sets $A,B$ and $C$ will refer to $\pi$ 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$: \ni {\bf Lemma 6.2} { Let $2m_{1} < 2m_{2}$ be two consecutive numbers in $A_{f}$. Then either (i) or (ii) holds, where \\ (i) \begin{equation} m_{2} = m_{1} + 1, \;\; \epsilon_{m_{1}} > \eta, \;\; \epsilon_{m_{2}} > \eta \;\; {\hbox{and}} \;\; f(2m_{2}) = f(2m_{1}) + 3. \end{equation} (ii) \begin{equation} m_{2} = m_{1} + 2, \;\; \epsilon_{m_{2}} > \eta, \;\; \epsilon_{m_{1}} < \eta \; {\hbox{or}} \; \epsilon_{m_{1}+1} < \delta, \;\; {\hbox{and}} \;\; f(2m_{2}) - f(2m_{1}) = 5. \end{equation}} Our idea is to prove by induction on $k > 0$ that $f(n) = \pi(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 \equiv \pi$ over the first $k-1$ periods. Note that, by definition, \begin{equation} {\hbox{If $n$ is odd, then $f(i) = \pi(i) \; \forall \; i < n \Rightarrow f(n) = \pi(n)$}}. \end{equation} The main tool in our proof (which does not depend on the induction hypothesis) is the following: \ni {\bf Lemma 6.3} {Suppose $\epsilon_{n} < \eta$. Then there are precisely $2n - \lfloor \sqrt{3} n \rfloor$ values of $m < n$ such that $f(2m) \geq \lfloor \sqrt{3} n \rfloor$, unless perhaps $f(2m) = \lfloor \sqrt{3} n \rfloor - 1$ for some $m < n$ where $2m \in A_{f}$}. \ni {\it Proof}: Let $1 \leq m < n$ be even such that $f(2m) > \lfloor \sqrt{3} n \rfloor$. Then $2m \in A_{f}$ and $f(2m) = m + \lfloor \sqrt{3} m \rfloor$. Thus \begin{equation} f(2m) > \lfloor \sqrt{3} n \rfloor \Leftrightarrow m > {\sqrt{3} n - \epsilon_{n} \over 1 + \sqrt{3}}. \end{equation} Set \begin{eqnarray} m^{0}:= {\sqrt{3} n - \epsilon_{n} \over 1 + \sqrt{3}}. \end{eqnarray} After a little manipulation, we find that \begin{eqnarray*} m^{0} = {3n - \lfloor \sqrt{3} n \rfloor \over 2} - {\sqrt{3} \over 2} \epsilon_{n}. \end{eqnarray*} Set $m_{0}:= \lfloor m^{0} \rfloor$. Since $\epsilon_{n} < \eta$, it is easily checked that $m_{0} = m^{0} - \epsilon$, where \begin{eqnarray} \epsilon = \left\{ \begin{array}{lr} 1 - \frac{\sqrt{3}}{2} \epsilon_{n}, & {\hbox{if $3n - \lfloor \sqrt{3} n \rfloor \in 2{\hbox{\ni {\bf Z}}}$}}, \\ \frac{1}{2} - \frac{\sqrt{3}}{2} \epsilon_{n}, & {\hbox{if $3n - \lfloor \sqrt{3} n \rfloor \not\in 2{\hbox{\ni {\bf Z}}}$}}. \end{array} \right. \end{eqnarray} Since $2m \in A_{f}$, we have to count the number of elements of $A_{f}$ in the interval $(2m_{0},2n)$. Since $\epsilon_{n} < \eta$, there are precisely $2n - \lfloor \sqrt{3} n \rfloor$ elements of $B_{f}$ in the interval $(1,2n)$, one for each period. Similarly, there are $2m_{0} - \lfloor \sqrt{3} m_{0} \rfloor + \phi$ elements of $B_{f}$ in the interval $[1,2m_{0}]$, where $\phi = 0$ unless $\epsilon_{m_{0}} < \eta$ and $2m_{0} \in B_{f}$, in which case $\phi = 1$. Hence the total number of elements of $A_{f}$ in $(2m_{0},2n)$ is \begin{eqnarray*} (n - m_{0} - 1) - \left[ (2n - \lfloor \sqrt{3} n \rfloor) - (2m_{0} - \lfloor \sqrt{3} m_{0} \rfloor + \phi) \right] \\ = \left( \lfloor \sqrt{3} n \rfloor - \lfloor \sqrt{3} m_{0} \rfloor \right) - (n - m_{0}) - 1 + \phi \\ = (\sqrt{3} - 1)(n - m^{0}) + (\sqrt{3} - 1) \epsilon + (\epsilon_{m_{0}} - \epsilon_{n}) + (\phi - 1). \end{eqnarray*} Using (29) and the fact that $(1+\sqrt{3})\eta = \sqrt{3} - 1$, this becomes \begin{eqnarray*} 2n - \lfloor \sqrt{3} n \rfloor + \Delta, \end{eqnarray*} where \begin{eqnarray} \Delta = (\sqrt{3} - 1)\epsilon + \epsilon_{m_{0}} - \sqrt{3} \epsilon_{n} + \phi - 1. \end{eqnarray} We shall now show that $\Delta = 0$ unless $\epsilon_{m_{0}} < \eta$ and $f(2m_{0}) = \lfloor \sqrt{3} n \rfloor - 1$, in which case $\Delta = -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 $\epsilon = \frac{1}{2} - \frac{\sqrt{3}}{2} \epsilon_{n}$, which is the only one in which the possibility that $\Delta = -1$ can arise. The other case is treated similarly but is technically simpler. The value of $\epsilon$ implies that \begin{eqnarray*} m_{0} = {3n - \lfloor \sqrt{3} n \rfloor \over 2} - {1 \over 2}. \end{eqnarray*} A little computation shows that \begin{eqnarray} \sqrt{3} m_{0} = \left( \lfloor \sqrt{3} n \rfloor - m_{0} \right) + \gamma, \end{eqnarray} where \begin{eqnarray*} \gamma = \left( {3 + \sqrt{3} \over 2} \right) \epsilon_{n} - {\sqrt{3} + 1 \over 2}. \end{eqnarray*} Since $\epsilon_{n} < \eta$, one checks readily that $\gamma \in \left( {-\sqrt{3} - 1 \over 2}, -1 + \eta \right) \subset$ \\ $(-2 + \eta, -1 + \eta)$. Hence there are the following two possibilities: either \begin{equation} \epsilon_{m_{0}} > \eta \;\;\; {\hbox{and}} \;\;\; \epsilon_{m_{0}} = {3 - \sqrt{3} \over 2} + \left( {3 + \sqrt{3} \over 2} \right) \epsilon_{n}, \end{equation} or \begin{equation} \epsilon_{m_{0}} < \eta \;\;\; {\hbox{and}} \;\;\; \epsilon_{m_{0}} = {1 - \sqrt{3} \over 2} + \left( {3 + \sqrt{3} \over 2} \right) \epsilon_{n}. \end{equation} If (33) holds, then $\phi = 0$ also. Substituting everything into (31) in this case, one readily computes that $\Delta = 0$, independent of $\epsilon_{n}$, as required. If (34) holds, then substituting everything into (31) one finds that $\Delta = -1 + \phi$. If $2m_{0} \in B_{f}$, then $\phi = 1$ and $\Delta = 0$ again, as required. Otherwise, $\Delta = -1$ and $2m_{0} \in A_{f}$. But then, from (32) and (34), we find that \begin{eqnarray*} f(2m_{0}) = m_{0} + \lfloor \sqrt{3} m_{0} \rfloor = m_{0} + \left( \lfloor \sqrt{3} n \rfloor - m_{0} - 1 \right) = \lfloor \sqrt{3} n \rfloor - 1, \end{eqnarray*} and the lemma is proved. Now let us perform the induction step. To simplify notation, set $N:= n_{k}$. Note that ${\cal U}2$, together with Lemmas 6.2 and 6.3, imply that if $\lfloor \sqrt{3} N \rfloor - 1 \in f(A_{f})$, then $f(2N-1) = \lfloor \sqrt{3} N \rfloor$. Let $m_{0} = m_{0}(N) = \lfloor m^{0}N \rfloor$ be as in (29) ff. The $k$:th period is either $[2N,2N+5]$ or $[2N,2N+7]$ according as to whether $\epsilon_{N+3} < \eta$ or not respectively. Clearly, \begin{equation} \epsilon_{N+3} < \eta \Leftrightarrow \epsilon_{N} < 4 \eta - 1. \end{equation} It is required to show that $f(2N+ i) = \pi(2N + i)$ for $i \in [0,5]$ or $i \in [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: \newpage \ni {\sc Case I}: $2N \in A_{f}$. Lemma 6.3 and its proof imply that, in {\sc Case I}, either \ni (i) $2m_{0} \in A_{f}$, $\epsilon_{m_{0}} < \eta$, $f(2m_{0}) = \lfloor \sqrt{3} N \rfloor - 1$ and $f(2N-1) = \lfloor \sqrt{3} N \rfloor$, or \\ (ii) $f(2m_{1}) = \lfloor \sqrt{3} N \rfloor$ for some $2m_{1} \in A_{f}$. In this case, it is clear from (29) that $m_{1} = m_{0} + 1$ and $\epsilon_{m_{1}} = \frac{3 + \sqrt{3}}{2} \epsilon_{N}$. $i = 2$: Since $2N \in A_{f}$, the definition of $f$ implies that $2(N+1) \in B_{f}$, and that $f(2N+2) = \lfloor \sqrt{3} N \rfloor + 2$. We have to show that $2(N+1) \in B$. If not, it can only be because the number $\lfloor \sqrt{3} N \rfloor + 2$ was already chosen by $\pi$, 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) \not\in B$. If it were, since the numbers $\lfloor \sqrt{3} N \rfloor + j$, $j= 1,2$, have already been chosen in positions $2N+j$, $j = 1,2$, the avoidance property of $\pi$ leaves as the only option that $\pi(2N+4) = \lfloor \sqrt{3} N \rfloor + 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 $\pi$ will not choose it again. $i = 6$: Once again, it needs to be shown that $2(N+3) \not\in B_{f}$. The analysis of the $i = 4$ case, together with (27), shows that all numbers up to and including $\lfloor \sqrt{3} N \rfloor + 3$ have already appeared in the first $2N+3$ positions. By a similar analysis, either the number $\lfloor \sqrt{3} N \rfloor + 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) \in B$, that $\pi(2N+6) = \lfloor \sqrt{3} N \rfloor + 5$. Our analysis shows moreover that this can only happen if the numbers $\lfloor \sqrt{3} N \rfloor + j$, $j = 1,2,3,4$, have appeared in positions $2N+ j^{\prime}$, where $j^{\prime} = 1,2,3,5$ respectively. In particular, this means that none of the numbers $\lfloor \sqrt{3} N \rfloor + l$, $l = 1,2,3,4,5$, appears in $f(A_{f})$. This contradicts Lemma 6.2. \ni {\sc Case II}: $2N \in B_{f}$. Lemma 6.3 and ${\cal U}2$ imply that $\lfloor \sqrt{3} N \rfloor - 1$ does not appear in $f(A_{f})$. The analysis is very similar to {\sc 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 $\epsilon_{N} > 4\gamma - 1$. $i = 6$: It is required to show that $2N+6 \in A$. If not, one easily sees by going through the analysis for the values of $i < 6$ that we must, a priori, have $\pi(2N+6) = \lfloor \sqrt{3} N \rfloor + j$, where $j = 4$ or $5$. If $j = 4$ then we will derive the contradiction that none of the six consecutive numbers $\lfloor \sqrt{3} N \rfloor + l$, $l = -1,0,1,2,3,4$, appears in $f(A_{f})$. \par Thus we may assume that $j = 5$. Here we can still deduce that exactly one of the seven consecutive numbers $\lfloor \sqrt{3} N \rfloor + 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) = \lfloor \sqrt{3} N \rfloor + l$. Clearly, $m = m_{1}$ or $m = m_{1} + 1$, where $m_{1} = m_{0} + 1$, as above. By (29), we have that \begin{eqnarray*} (1 + \sqrt{3}) m_{1} = \lfloor \sqrt{3} N \rfloor + \epsilon^{*}, \end{eqnarray*} where \begin{eqnarray*} \epsilon^{*} = \left\{ \begin{array}{lr} (\sqrt{3} + 1) \frac{\sqrt{3}}{2} \epsilon_{N}, & {\hbox{if $3N - \lfloor \sqrt{3} N \rfloor \in 2 {\hbox{\ni {\bf Z}}}$}}, \\ (\sqrt{3} + 1)\left(\frac{1}{2} + \frac{\sqrt{3}}{2} \epsilon_{N} \right), & {\hbox{if $3N - \lfloor \sqrt{3} N \rfloor \not\in 2{\hbox{\ni {\bf Z}}}$}}. \end{array} \right. \end{eqnarray*} We examine the two possibilities separately: First suppose \begin{eqnarray*} \epsilon^{*} = \left( \sqrt{3} + 1 \right) \left( {1 \over 2} + {\sqrt{3} \over 2} \epsilon_{N} \right). \end{eqnarray*} Since $4\eta - 1 < \epsilon_{N} < \eta$, we easily compute that $\epsilon^{*} \in (1+2\eta,2)$. Thus $\epsilon_{m_{1}} > 2\eta$ and $\lfloor (1+\sqrt{3})m_{1} \rfloor = \lfloor \sqrt{3} N \rfloor + 1$, hence $\lfloor (1+\sqrt{3})(m_{1} + 1) \rfloor = \lfloor \sqrt{3} N \rfloor + 4$. It follows that $2m_{1} \in A_{f}$ and $2(m_{1} + 1) \in B_{f}$. But this is contradicted by (25), (26) and the fact that $\epsilon_{m_{1}} > 2\eta \Rightarrow \epsilon_{m_{1}+1} > \eta$. Finally, suppose \begin{eqnarray*} \epsilon^{*} = \left( \sqrt{3} + 1 \right) {\sqrt{3} \over 2} \epsilon_{N}. \end{eqnarray*} Then $\epsilon^{*} = \epsilon_{m_{1}}$ and $\lfloor (1+\sqrt{3})m_{1} \rfloor = \lfloor \sqrt{3} N \rfloor$. Thus $l = 2$ or $3$ in this case. But in either case, we have at least three consecutive numbers to the left of $\lfloor \sqrt{3} N \rfloor + l$, none of which is appears in $f(A_{f})$. By (26), this forces either \ni (i) $l = 3$, $\epsilon_{m_{0}} < \eta$, or \\ (ii) $l = 2$, $\epsilon_{m_{1}} < \eta$. But (i) is impossible, since one easily checks that $\epsilon_{N} \in (0,\eta) \Rightarrow \epsilon_{m_{1}} \in (\eta,1-\eta) \Rightarrow \epsilon_{m_{0}} \in (2\eta,1)$. \\ And (ii) is impossible since Lemma 6.2 would then imply that $\lfloor \sqrt{3} N \rfloor + 5$ also appeared in $f(A_{f})$. Thus we have completed the proof that $f = \pi$ 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: \ni {\bf Conjecture 6.4} {Let $m,p,k$ be any three positive integers. Let $M:= {\cal M}_{m,p}$ and take $S = {\cal S}_{k}:= k{\hbox{\ni {\bf N}}}$. Let $\pi = \pi_{m,p}^{k}:= \pi_{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 \in {\hbox{\ni {\bf N}}}$, $\pi(n)$ differs from one of the numbers $\lfloor nL \rfloor$ and $\lfloor nl \rfloor$ by at most $c_{m,p,k}$.} As already remarked, Theorem 6.1 implies that we can take $c_{1,1,2} = 2$. \vskip 30pt \section*{\normalsize 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. \vskip 30pt \section*{\normalsize References} [1] S. {\sc Beatty}, Problem 3173, {\em Amer. Math. Monthly} \ni {\bf 33} (1926) 159; \ni {\bf 34} (1927) 159. \newline [2] A.S. {\sc Fraenkel}, How to beat your Wythoff games opponent on three fronts, {\em Amer. Math. Monthly} \ni {\bf 89} (1982), 353-361. \newline [3] A.S. {\sc Fraenkel and C. Kimberling}, Generalised Wythoff arrays, shuffles and interspersions, {\em Discrete Math.} \ni {\bf 126} (1994), 137-149. \newline [4] A.S. {\sc Fraenkel}, New games related to old and new sequences, \newline {\em Integers: Electronic J. Comb. Number Theory} \ni {\bf 4} (2004), Paper G06. \newline [5] C. {\sc Kimberling}, Interspersions and dispersions, {\em Proc. Amer. Math. Soc.} \ni {\bf 117} No.2 (1993), 313-321. \newline [6] C. {\sc Kimberling}, The first column of an interspersion, {\em Fibonacci Quart.} \ni {\bf 32} (1994), 301-314. \newline [7] C. {\sc Kimberling}, The Zeckendorff array equals the Wythoff array, {\em Fibonacci Quart.} \ni {\bf 33} (1995), 3-8. \newline [8] C. {\sc Kimberling}, Stolarsky interspersions, {\em Ars Combinatoria} \ni {\bf 39} (1995), 129-138. \newline [9] N.J.A. {\sc Sloane}, My favorite integer sequences. {\em 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/$\sim$njas/doc/sg.pdf) \newline [10] F. {\sc Smith and P. St\u{a}nic\u{a}}, Comply/constrain games or games with a Muller twist, {\em Integers: Electronic J. Comb. Number Theory} \ni {\bf 2} (2002), Paper G03. \newline [11] X. {\sc Sun} and D. {\sc Zeilberger}, On Fraenkel's $N$-heap Wythoff's conjectures, {\em Ann. Comb.} \ni {\bf 8} (2004), 225-238. \newline [12] W.A. {\sc Wythoff}, A modificaton of the game of Nim, {\em Nieuw. Archief voor Viskunde (2)} \ni {\bf 7} (1907), 199-202. \end{document}