P -orderings of finite subsets of Dedekind domains

DOI 10.1007/s10801-008-0157-9

P -orderings of finite subsets of Dedekind domains

Keith Johnson

Received: 6 May 2008 / Accepted: 8 October 2008 / Published online: 3 November 2008

© Springer Science+Business Media, LLC 2008

Abstract IfRis a Dedekind domain,P a prime ideal ofRandS⊆Ra finite subset then aP-ordering of S, as introduced by M. Bhargava in (J. Reine Angew. Math.

490:101–127,1997), is an ordering{a_i}^m_i=1 of the elements ofS with the property that, for each 1< i≤m, the choice ofa_iminimizes theP-adic valuation of

j <i(s− aj)over elementss∈S. IfS,Sare two finite subsets ofRof the same cardinality then a bijectionφ:S→Sis aP-ordering equivalence if it preservesP-orderings.

In this paper we give upper and lower bounds for the number of distinctP-orderings a finite set can have in terms of its cardinality and give an upper bound on the number ofP-ordering equivalence classes of a given cardinality.

Keywords P-ordering·P-sequence·Dedekind domain

1 Introduction

LetR be a Dedekind domain, P a prime ideal ofR,Kthe quotient field ofR and q the cardinality ofR/P. Also, forx∈R, letγ (x)denote the largest integerkfor whichx∈P^k. IfSis a subset ofRthen aP-ordering ofS, as introduced in [1], is a sequence{a_i|i=1,2, . . .}of elements ofSwith the property that, for eachi >1, the choice ofa_i minimizesγ (

j <i(s−a_j))over alls∈S. Such orderings play a central role in the study of polynomials which are integer valued on subsets ofR([1], [2]).

ForSa finite set we will make the convention that aP-ordering ofSstops when all elements ofShave been enumerated (since beyond that pointγ (

(s−aj))= ∞for anys∈Sand the ordering is arbitrary). IfS,Sare two finite subsets ofRof the same cardinality,m, then a bijectionφ:S→Sis aP-ordering equivalence if{a_i}^m_i=1is a P ordering ofSif and only if{φ (a_i)}^m_i=1is aP-ordering ofS.

K. Johnson (

Department of Mathematics, Dalhousie University, Halifax, Nova Scotia, B3H 4R2, Canada e-mail:johnson@mathstat.dal.ca

Since the first element in aP-ordering can be picked arbitrarily it is clear that a set can have many differentP-orderings and it is natural to ask how many distinct P-orderings a given finite set can have and how they can be enumerated. Similarly one can ask how many nonP-ordering equivalent sets there are of a given cardinality, and how they can be enumerated. In this paper we give upper and lower bounds in terms of the cardinality ofSfor the number ofP-orderingsScan have and give an upper bound for the number nonP-ordering equivalent sets that can exist of a given cardinality.

In more detail the results can be described as follows:

Proposition 1.1 IfS⊆R, is a set of cardinality mthen S has at least 2^m−1 P- orderings, and for eachmthere are sets realizing this bound.

Proposition 1.2 Ifq= |P|then the maximum number ofP-orderings which a subset ofRof cardinalitymcan have is bounded by the functionα(m)given byα(m)=m! form≤q and form > q

α(m)=max{ q

i=1

i^mi q

i=1

α(m_i)}

where the maximum is taken over all sequences m₁≥m₂≥ · · · ≥m_q ≥0 with m_i=mexcept the trivial sequencem₁=m,m_i=0 fori >1.

The most familiarP-ordering is the usual increasing order on the set{1, . . . , m} in the caseR=Z. An analog of this set and ordering for a general Dedekind domain and primePwas defined in ( [8], p.104).P-orderings of these sets have the following properties:

Proposition 1.3 If {r₀, . . . r_q−1} is a set of representatives for R/P, π a repre- sentative of P \P² and, for n∈Z^≥0 whose representation in base q is

n_iqⁱ, a_n=

r_niπⁱ then

(a) The set{a1. . . , a_m}hasβ(m)distinctP-orderings, where

β(m)=

n<m

(

i≥0

(n_i+1))

(b) Ifq=2 thenα(m)=β(m), i.e. the sets in part (a) have the maximal number ofP-orderings among sets of cardinalitym.

(c) For each q >2 there are sets of cardinality m with more than β(m) P- orderings for infinitely manym.

LetN (m)denote the number ofP-ordering equivalence classes of sets of cardi- nalitym.

Proposition 1.4 The numbersN (m)satisfy the inequality N (m)≤

D(k₁−1, . . . , kt−1)N (k1) . . . N (k_t)

where the sum is over all nontrivial partitions ofmas a sum of no more thanqstrictly positive integers andD(k₁, . . . , k_t)denotes the generalized Delannoy number [7].

The proofs of these results are inductive and involve relating theP-orderings of Sto those of certain of its subsets. This requires some algebraic and combinatorial results about combining orderings of subsets which we assemble in Section 2. The proofs of Propositions1.1, 1.2and 1.3are then given in Sections 3. That section also contains remarks and computational results about the rate of growth ofαandβ. Section 4 contains the proof of Proposition1.4.

The inequality in Proposition1.4is in most cases not an equality. In Section 4 we make some comments as to possible improvements and give some computational results for the caseR=ZandP=2 and 3.

It should be remarked that while the results in this paper hold for a general Dedekind domain the case of the integers illustrates almost all of the ideas com- pletely. The only significant difference is that in the case of the integersqis a prime while in the general case it will be a power of a prime.

2 Shuffles and Alignments

We begin by establishing some elementary results about orderings, shuffles and align- ments of finite collections of finite sets. In this paper it will be convenient for us to treat an ordered set as a finite sequence rather than as a set with a binary relation. We will use the notation< n >to denote the set of integers from 1 ton(and take<0>

to be the empty set).

Definition 2.1 An ordering of a setSof cardinalitynis a bijective mapψ:< n >→ S.

When only one ordering of a set is being considered we will sometimes revert to the familiar notation{a_i, i=1, . . . , n}witha_i=φ (i)for an ordering. With this definition orderings pass to subsets as follows:

Definition 2.2 If S is an ordered set with orderingψ,S⊆S, andi:S→S the inclusion map then the restriction of the orderingψtoS is the unique orderingψ ofS for whichψ⁻¹◦i◦ψ is increasing.ψ is given byψ(j )=s ifj = |{k≤ ψ⁻¹(s)|ψ (k)∈S}|.

We will be concerned with the number of different ways in which a collection of ordered sets can be combined to form a larger ordered set. For this the following definition is useful.

Definition 2.3 Letk1, . . . , k_qbe nonnegative integers andn=

k_j. A(k1, . . . , k_q)- shuffle is an ordered set ofq strictly increasing mapsφ_j :< k_i>→< n >with dis- joint images.

In the special caseq =2 this is usually called a riffle shuffle and describes the familiar action of shuffling a deck of cards. There is a substantial literature on the algebra and combinatorics of this case [6]. In general a shuffle is sometimes also defined to be a permutationσ∈S_n with the property that its restriction to each of the subsets{i|j−1

=1k < i≤j

=1k }is increasing. The correspondence between that definition and the one above is that if σ is such a permutation then φ_j(i)= σ (i+j−1

=1k ).

Proposition 2.4 (a) IfS is a finite ordered set with orderingψwhich is the disjoint union of subsetsS=q

j=1Sj with|Sj| =kj and inclusion maps ij :Sj→S then eachS_j is, by restriction, an ordered set with orderingψ_j and there exists a unique (k₁, . . . , k_q)-shuffle(φ₁, . . . , φ_q)such thatψ◦φ_j=i_j◦ψ_j forj=1, . . . , q.

(b) If {(S_j, ψ_j), j =1, . . . , q} is an ordered set of q finite ordered sets with

|S_j| =k_j,S=q

j=1S_j and (φ_j, j =1, . . . , q)is a(k₁, . . . , k_q)-shuffle then there is a unique orderψforSsuch thatψ◦φ_j=i_j◦ψ_j forj =1, . . . , q.

Proof (a) Ifi_j:S_j →S is the inclusion map then the mapφ_j :< k_j >→< n >is the strictly increasing mapψ⁻¹◦i_j◦ψ_j in Definition2.2. These maps have disjoint images because theS_j’s are disjoint and the union of their images is< n >because

∪S_j=S.

(b) The equationψ◦φj=ij◦ψj determinesψ uniquely because every integer in< n >is in the image of φj for a unique index valuej. The resulting mapψ is injective because eachψj andij is, and theij’s have disjoint images. It is onto becauseψj has imageSj andSis the union of the images of theij’s.

Terminology 2.5 IfS,{S_j},{φ_j}are related as in the previous lemma then we will refer toS as the ordered set obtained from{S_j}by the action of the shuffle{φ_j}, or as the shuffle of the{S_j}if{φ_j}is clear from the context.

There is a similar definition and result for collections of sets which are not disjoint:

Definition 2.6 Letk₁, . . . , k_qbe nonnegative integers and letm≤

k_j. A(k₁, . . . , k_q;m)-alignment is an ordered set ofqstrictly increasing mapsφ_j:< k_i >→< m >

the union of whose images is< m >.

The name comes from applications in biology [9] of the caseq =2. The vari- ation here is that the images of the φj’s need not be disjoint. We will sometimes refer to such an object simply as a(k1, . . . , kq)-alignment since the integermcan be recovered as the cardinality of the union of the images of theφj’s.

Proposition 2.7 (a) IfS is a finite ordered set with orderingψ andS is the union of subsetsS= ∪^q_j=1S_j with|S_j| =k_j,|S| =mand inclusion mapsi_j:S_j→Sthen each S_j is, by restriction, an ordered set with ordering ψ_j and there is a unique (k₁, . . . , k_q;m)-alignment(φ₁, . . . , φ_q)such thatψ◦φ_j=i_j◦ψ_j forj=1, . . . , q.

(b) If{(S_j, ψ_j)|j=1, . . . , q}is a collection ofq finite ordered subsets of a setS with|S_j| =k_j,S= ∪S_j and if(φ₁, . . . , φ_q)is a(k₁, . . . , k_q;m)-alignment such that

for anys∈S_j∩S_j φ_j◦ψ_j⁻¹(s)=φ_j◦ψ_j⁻¹(s)for anyj, jthen there is a unique orderψforSsuch thatψ◦φj=ij◦ψj forj=1, . . . , q.

Proof (a) As in the previous proof we take φ_j =ψ⁻¹◦i_j ◦ψ_j which is strictly increasing. Since theψ_j’s are bijective and the union of the images of thei_j’s isS, the union of the images of theφj’s is< m >, hence these form an alignment.

(b) The equationψ◦φ_j=i_j◦ψ_j determinesψon the image ofφ_j. An integer that is in the intersection of the images of two of theφ_j’s is one whose inverse image under each of theφj’s is mapped to the same element inS by each of theψj’s and so lies in the intersection of two or more of theSj’s. That this equation determines the same value for each of the possible choices ofφ_j thus follows from the equation φ_j◦ψ_j⁻¹=φ_j◦ψ_j⁻¹holding on the intersection of theS_j’s.ψis surjective because the ψj’s are bijective and the union of the images of the ij’s is S. It is injective

because each of theψ_j’s is.

We will refer to the alignment determined in 2.7(a) as the union alignment of the Sr’s.

A shuffle is, of course, a special case of an alignment but there is a further connec- tion between the two ideas:

Proposition 2.8 If {φ1, . . . , φ_q} is a (k1, . . . , k_q)-shuffle with

k_j =n and if π:< n >→< m > is a nondecreasing surjective map with the property that, for any , π⁻¹( ) meets the image of any one of the φ_j’s in at most one point then {π◦φ1, . . . , π◦φq}is a(k1, . . . , kq;m)-alignment.

Proof Sinceπis nondecreasing eachπ◦φ_j is also nondecreasing. Since anyπ⁻¹( ) meets the image ofφjin at most one point,π◦φj is injective and so strictly increas- ing. The union of the images of theφ¯_j’s is the image underπ of the union of the images of theφ_j’s, i.e.π(< n >)=< m >sinceπis surjective.

Definition 2.9 If π is as in the previous proposition then the alignment {π ◦ φ1, . . . , π◦φ_q}will be called the projection of the shuffle{φ1, . . . , φ_q}alongπ.

Proposition 2.10 If { ¯φ1, . . . ,φ¯q} is a (k1, . . . , kq;m)-alignment and π :< n >→

< m >is a nondecreasing surjective map such that

k_j=nand for every 1≤ ≤m it is the case that|π⁻¹( )| = |{j| ∈Image(φj)}|then the number of(k₁, . . . , k_q)- shuffles whose projection alongπis{ ¯φ₁, . . . ,φ¯_q}is

m

=1

|π⁻¹( )|!

Proof Given{ ¯φ1, . . . ,φ¯q}andπ, choosing{φ1, . . . , φq}such thatφ¯j =π◦φj in- volves, for each 1≤ ≤m, choosing values fromπ⁻¹( )for thoseφ_j’s for which

∈Image(φ¯_j). There are |π⁻¹( )| possible values and, by hypothesis, there are

|π⁻¹( )| suchφ_j with ∈Image(φ¯_j), hence|π⁻¹( )|! ways of assigning the val- ues to theφ_j’s so that the images of theφ_j’s are disjoint. That the resulting mapsφ_j are increasing follows from the fact that theφ¯_j’s are and thatπis nondecreasing.

We note also that counting shuffles or alignments yields a familiar sequence of constants:

Proposition 2.11 (a) The number of(k1, . . . , kq)-shuffles is the multinomial coeffi- cientC(k1, . . . , kq)=(

kj)!/(k1!. . . kq!).

(b) The sum overmof the number of(k1, . . . , kq;m)-alignments for allm≤ kj

is the generalized Delannoy number [7]D(k1, . . . , kq).

Proof (a) If{φ₁, . . . , φ_q}is a(k₁, . . . , k_q)-shuffle with

n_j =nthen n=φ_j(k_j) for exactly one index valuej and{φ₁, . . . , φ_j|<kj−1>, . . . , φ_q} is a (k₁, . . . , k_j − 1, . . . , kq)-shuffle. Thus the number of(k₁, . . . , k_q)-shuffles,C_k1,...,kq satisfies the re- currence

C(k₁, . . . , k_q)=

q

j=1

C(k₁, . . . , k_j−1, . . . , kq)

which is a familiar recurrence formula for the multinomial coefficients. As with the multinomial coefficientsC also has the properties thatC(k1, . . . , k_i−1,0, ki+1, . . . , k_q)=C(k1, . . . , k_i−1, k_i+1, . . . , k_q)and thatC(k)=1. The result thus follows by induction.

(b) If{φ1, . . . , φ_q}is a(k1, . . . , k_q;m)-alignment with

n_j=mthenm=φ_j(k_j) for some nonempty collection of index values. Let_j=1 ifj is in this collection and 0 otherwise. It follows that{φ₁|<k1−1>, . . . , φ_q|<kq−q>}is a(k₁−₁, . . . , k_q−_q)- alignment and so that the number of(k₁, . . . , k_q)-alignments,D(k₁, . . . , k_q), satisfies the recurrence

D(k1, . . . , kq)=

(1,...,q)∈({0,1}^q)^∗

D(k1−1, . . . , kq−q)

where({0,1}^q)^∗ denotes the set of all binary strings(₁, . . . , _q)except(0, . . . ,0).

This is the recurrence determining the generalized Delannoy numbers. Both D and the Delannoy numbers have the properties D(k1, . . . , ki−1,0, ki+1, . . . , kq)= D(k1, . . . , ki−1, ki+1, . . . , kq) and D(k)=1. Hence the result follows by induc-

tion.

Remark The argument in the proof of part (b) of the previous proposition also gives the recurrence formula

D₍k1, . . . , k_q;m)=

(1,...,q)∈({0,1}^q)^∗

D(k1−1, . . . , k_q−_q;m−1)

ifD(k₁, . . . , k_q;m)denotes the number of (k₁, . . . , k_q;m)alignments. This allows theD(k₁, . . . , k_q;m)to be computed recursively also. In particular forq=2 it shows

that

D(k1, k2;m)=

k₂

k₁+k₂−m

m

k₂

and so gives the well known formula ( [5], p.81) forD(k₁, k₂):

D(k₁, k₂)=

m

k2

k1+k2−m

m

k2

3 CountingP-orderings

As in the introduction we define aP-ordering of a finite subsetSofRas follows:

Definition 3.1 AP-ordering ofS is an ordering{a_i, i=1,2, . . .|S|}ofS with the property that for eachi >1 the elementa_i minimizes γ (

j <i(s−a_j))among all elementssofS.

Recall from [1] that there is associated to a setS⊆Ra sequence of nonnegative integers called theP-sequence ofS.

Definition 3.2 If{ai}^m_i=1is aP-ordering of a setS⊆Rthen theP-sequence ofSis the sequence of integersD= {di}^m_i=1withd1=0 anddi=γ (

j <i(ai−aj)).

(In [2] theP-sequence of a setSis the sequence of ideals(

j <i(a_i−a_j))however in this paper there is one prime ideal P which is fixed throughout so that this is equivalent to working with theP-adic valuations of these ideals.) It is shown in [1]

that theP-sequence ofS depends only onS and not on the particularP-ordering used to compute it. We will find the following additional facts aboutP-sequences useful:

Lemma 3.3 (a) TheP-sequence ofS characterizesP-orderings of S in the sense that if{ai}^m_i=1is an ordering ofSsuch thatγ (

j <i(ai−aj))=difor all 1≤i≤m then{a_i}^m_i=1is aP-ordering ofS.

(b)P-sequences are always nondecreasing.

(c) Ifπ∈P \P²,k∈Z⁺,r∈R,D= {d_i}^m_i=1is theP-sequence ofS andS= {r+π^kS|s∈S}then the bijectionφ (s)=r+π^ksbetweenSandSis aP-ordering equivalence ofSandSand theP-sequence ofSisD= {di+i·k}^m_i=1.

Proof (a) Suppose that{a_i}^m_i=1is an ordering ofSfor whichγ (

(a_i−a_j))=d_ifor alli. If{a_i}^m_i=1were not aP-ordering, then there would existk >1 anda∈Rsuch thatγ (

j <i(ai−aj))is minimal fori < kand γ (

j <k

(a−aj)) < γ (

j <k

(ak−aj))=dk.

This contradicts the fact thatd_kis the same for allP-orderings.

(b) The minimality ofγ (

j <k(a_k−a_j))implies dk=γ (

j <k

(ak−aj))≤γ (

j <k

(ak+1−aj))≤γ (

j <k+1

(ak+1−aj))=dk+1

(c) Suppose{ai}^m_i=1is an ordering ofS. The corresponding ordering ofSis{r+ π^ka_i}^m_i=1= {a_i}^m_i=1and

γ (

j <i

(a_i−a_j))=γ (

j <1

(π^k(a_i−a_j))

=γ (π^ik

j <i

(ai−aj))

=ik+γ (

j <i

(a_i−a_j)).

Such an ordering is aP-ordering if and only ifγ (

j <i(a_i−a_j))is minimal, which in turn happens if and only if γ (

j <i(a_i −a_j)) is minimal since the term ik is constant for alli-fold products inS. This formula also establishes the value of the

P-sequence ofS.

There is a connection between theP-sequence of a setSand that of certain of its subsets which will play a central role in what follows. The subsets of interest are:

Definition 3.4 IfS is a finite subset ofR andr+P is a coset of R/P let Sr = S∩(r+P ). IfDis theP-sequence ofSdenote theP-sequence ofS_r byD_r.

The following result relatesP-orderings and theP-sequence ofS to those of the S_r’s. The first part of this result is Lemma 3.4 in [3] (see also [4]). We include a proof here for completeness.

Lemma 3.5 (a) AP-ordering ofSgives, by restriction, aP-ordering ofS_r for each r. TheP-sequence ofSis equal to the sorted concatenation of theP-sequencesD_r of the S_r’s for all of the distinct residue classes ofR/P where the sorting is into nondecreasing order.

(b) TheP-sequence of each of the setsSr is strictly increasing.

Proof (a) Let {a_i}^m_i=1 be a P-ordering of S and suppose a_k ∈S_r. If a_j ∈S_r for r≡r(P )thenγ (a_k−a_j)=0, and so

d_k=γ (

j <k

(a_k−a_j))

=γ (

j <k aj∈Sr

(ak−aj)).

Furthermore ifs∈S_rthen

γ (

j <k a_j∈Sr

(s−a_j))=γ (

j <k

(s−a_j))≥γ (

j <k

(a_k−a_j))

=γ (

j <k aj∈Sr

(ak−aj)),

and soa_kminimizesγ (

j <k

aj∈Sr(s−a_j))fors∈S_r. Hence{a_i}^m_i=1∩S_ris aP-ordering ofS_r and{d_k|a_k∈S_r}is theP-sequence ofS_r.

SinceDis nondecreasing by Lemma3.3(b), the result follows.

(b) In the proof of Lemma3.3(b) the last inequality is strict for the setsSr.

In order to count the number ofP-orderings a set can have we examine how we can reconstruct aP-ordering ofSfrom that of the setsS_r in the previous lemma and for this the ideas of shuffle and alignment are relevant. Lemma3.5(a) implies that a P-ordering ofS is obtained fromP-orderings of the setsS_r by applying a shuffle, and Lemma3.3identifies which shuffles ofP-orderings of theSr’s yieldP-orderings ofS.

Lemma 3.6 Suppose that{Di, i=1, . . . , q}is a set of finite sets of distinct nonnega- tive integers each with the increasing order, one for eachr∈R/P. Let the cardinality ofD_i bek_i and letDandD¯ denote the disjoint union and the union respectively of theD_i’s, each with the nondecreasing order. Also let the cardinalities ofDandD¯ be n(=

ki)andmrespectively. In this case the inclusions¯iiof theDi’s intoD¯ deter- mine a(k₁, . . . , k_q)-alignment and the canonical projectionπ¯ :D→ ¯Ddetermines a mapπ:< n >→< m >. A(k₁, . . . , k_q)-shuffle determines a shuffle of theD_i’s into Dif and only if it projects alongπto the alignment determined by theD_i’s.

Proof The alignment is given by Proposition2.7(a). Denote it by(φ¯₁, . . . ,φ¯_q). It is determined by the condition that¯i_iψ_i= ¯ψφ¯_i. Letψ_i,ψ andψ¯ be the orders onD_i, DandD. The map¯ π is given byψ¯⁻¹π ψ. A shuffle¯ (φ1, . . . , φq)projects alongπ to(φ¯₁, . . . ,φ¯_q)if and only ifπ φ_i= ¯φ_i for alli. It determines a shuffle of theD_i’s intoDif and only ifψ φ_i =i_iψ_i for alli. Sinceπ ψ¯ = ¯ψ π,π i¯ _i = ¯i_i andψ_i,ψ,ψ¯

are bijections these are equivalent.

D_i

ii

i¯i

k_i

ψ_i

φi

φ¯i

D

¯ π

< n >

ψ

π

D¯ < m >

ψ¯

Proposition 3.7 The following are equivalent:

(a) A shuffle of a collection ofP-orderings of theSr’s results in aP-ordering of S.

(b) The shuffle of the associatedD_r’s results in a sequence in nondecreasing order.

(c) The shuffle projects along π to the alignment associated to the D_r’s as in Lemma3.6.

Proof By Lemma3.3P-orderings ofS are characterized by theP-sequence ofS.

Thus a shuffle yields aP-ordering ofSif and only if the shuffle of theDr’s yields theP-sequence ofS. This is described by Lemma3.5.

This Proposition gives us a method for inductively counting the number ofP- orderings of a given set.

Corollary 3.8 Let i be the number of integers occurring in exactlyi of theDr’s.

There areq

i=1(i!)ⁱ distinct shuffles which shuffle theDr’s into the sequenceDand so which shuffleP-orderings of theS_r’s into aP-ordering ofS.

Proof From Lemma3.5(a) the shuffles involved are those that shuffle theD_r’s into a sequence in nondecreasing order. Since theD_r’s are each strictly increasing the only choices in shuffling them into non decreasing order occur when the same integer occurs in more than one of theDr’s. If it occurs iniof them then there arei!choices

as to how to order them.

Corollary 3.9 IfS_r hasN_r distinctP-orderings for each residue classr, thenShas q

i=1

(i!)ⁱ

r∈R/P

N_r

distinctP-orderings.

We may now prove Proposition1.1by induction:

Proof Suppose that forn < msets of cardinalitynhave at least 2ⁿ⁻¹ P-orderings and thatS is of cardinalitym. By Lemma3.3(c)S isP-ordering equivalent to a set containing representatives from at least two distinct residue classes moduloP and so, replacingS by this equivalent set if necessary, we may assume that S has this property. IfS has representatives fromk distinct residue classes moduloP thenk of theP-sequencesD_r of Lemma3.7have the number 0 in common and so in the previous corollary k≥1. Thus if |Sj| =kj so that

kj=mthen the number of P-orderings ofSis at least

k! k

j=1

2^kj−1=k!2^m−k≥2^m−1.

To verify that this bound is sharp chose any strictly increasing sequence of nonneg- ative integers{ej, j =1, . . . , m}and consider the set{π^ej}. This isP-equivalent to the set{π^ej−e1}for which|S₁| =1,|S₀| =m−1 and|S_r| =0 for all other residue classesr. Thus the number ofP-orderings ofSis twice that ofS0by Corollary3.9.

SinceS0is the same type of set asSwith one fewer element, it follows by induction

thatShas 2^m−1P-orderings.

Remark An entirely different proof of Proposition1.1can be given by showing that P-orderings of a finite set may be constructed in the reverse order by showing thata_j maximizes

γ (

s∈S\{a,a_j+1,...,am}

(a−s))

over alla∈S\{a_j+1, . . . , a_m}and then showing that at every stage there are at least two elements that maximize this quantity.

Similarly we can establish Proposition 1.2:

Proof of Proposition1.2 First note that ifm≤qthen any set ofmelements in which no two are congruent moduloP will have all possible orderings asP-orderings. Thus we may assumem > q. Suppose thatS^mis a set of cardinalitymwith the maximal number ofP-orderings among sets of this size. If, as before, the intersections ofS^m with the cosets ofR/P are denoted S_r^m then the number ofP-orderings of S^m is given by

q

i=1

(i!)ⁱ

r∈R/P

Nr,

whereN_r, i are as in Corollary 3.9. We may assume, by translating and removing common factors ofP, that at least two of the setsS_r^mare nonempty. If we sort the setsS_r^mby size into decreasing order and letmi denote the size of the i-th set then the productq

i=1(i!)ⁱ is largest for fixedm_i if each i is as large as possible. Since

can be at mostm_i−m_i+1, takingm_q+1=0. In this case q

i=1

(i!)ⁱ≤ q

i=1

( i

j=1

j )^mi−mi+1 = q

j=1

(j

q

i=j(mi−mi+1)

)= q

j=1

j^mj

and so the number ofP-orderings is less than or equal to q

j=1

j^mj q

i=1

α(m_i)≤α(m).

We next turn to the proof of Proposition 1.3

Proof of Proposition1.3(a) Ifm≤q then all of thea_i are distinct moduloP and so all of the m! possible orderings are P-orderings. Since for m≤q β(m)=m! the result holds in these cases. Now assumem > q. As in the introduction leta_n= r_niπⁱ if the representation ofn in baseq is

n_iqⁱ and letS^m= {a1, . . . , a_m}.

Also, letm= ·q+twith 0≤t < q. The setsS_r^mhave +δelements forδ=0 or 1 withδ=1 ifr=r_kwithk < t, andδ=0 otherwise. The bijectionS ^+δ→S_r^mgiven bya→r+π agives a 1−1 correspondence betweenP-orderings of the two sets and also shows that theP-sequences of theS_r^m’s are all equal in the first entries, and those for whichδ=1 have final entry equal also. Corollary3.9therefore implies that the number ofP-orderings ofS^mis equal to

(q!) ·t! ·(# ofP-orderings ofS ⁺¹)^t·(# ofP-orderings ofS )^q−t. Therefore to show that the number ofP-orderings ofS^misβ(m)it suffices to show thatβ(m)satisfies the recurrence

β(m)=(q!) t!β( +1)^tβ( )^q−t. Recall that

β(m)=

1≤n<m

(

i≥0

(ni+1)).

Lemma 3.10 If 0< a < qthen

β(aq^k)=(a!)^qk(q!)^kaqk−1.

Proof An integeriin the range from 0 to a−1 will occur as thek+1-st digit of the numbers in the range from 1 toaq^k−1 exactlyq^k times. Similarly for 0≤j≤k an integer in the range from 1 toq−1 will occur as thej-th digit of numbers in the range from 0 toaq^k−1 exactlyaq^k−1times and 0 will occuraq^k−1−1 times. Thus

β(aq^k)=(a!)^qk((q!)^aqk−1)^k.

Corollary 3.11 β(aq^k)=β(aq^k−1)^q·(q!)^aqk−1.

Lemma 3.12 If 0< a < qandaq^k< m≤(a+1)q^kthen β(m)=(a+1)^m−aqk·β(aq^k)·β(m−aq^k).

Proof For allnin the rangeaq^k≤n < mthek+1-st digit isa and the remaining digits coincide with those ofn−aq^k. Thus

β(m)=

n<m

(

i≥0

(ni+1))

=

n<aq^k

(

i≥0

(ni+1))

aq^k≤n<m

(

i≥0

(ni+1))

=β(aq^k)

aq^k≤n<m

(

i≥0

(n_i+1))

=β(aq^k)(a+1)^m−aqkβ(m−aq^k).

We now verify the recurrence formula forβ by induction onmand supposem= q+twithaq^k< m≤(a+1)q^k. Note that in this caseaq^k−1< ≤(a+1)q^k−1.

We then have, using the lemma twice and simplifying the result:

(q!) t!β( +1)^tβ( )^q−t

=(q!)t!(a ^+1−aqk−1β(aq^k−1)β( +1−aq^k−1))^t

×(a ^−aqk−1β(aq^k−1)β( −aq^k−1))^q−t

=(q!)t!a^{t ( +1)+(q−t ) −qaqk−1}β(aq^k−1)^qβ( +1−aq^k−1)^tβ( −aq^k−1)^q−t

=q! t!a^m−aqkβ(aq^k−1)^qβ( +1−aq^k−1)^tβ( −aq^k−1)^q−t. Using Corollary 3.11this becomes

q!^−aqk−1t!a^m−aqkβ(aq^k)β( +1−aq^k−1)^tβ( −aq^k−1)^q−t which, by the induction hypothesis is

a^m−aqkβ(aq^k)β(m−aq^k)=β(m).

Proof of Proposition1.3(b) Ifm≤q thenα(m)andβ(m)are both equal tom!. To prove part (b) form > q it suffices to show that whenq=2 ifm=m₁+m₂with m₁≥m₂ thenβ(m)≥2^m2β(m₁)β(m₂). Since for q=2 the recurrence above for

β(m)specializes toβ(2m)=2^mβ(m)²andβ(2m+1)=2^mβ(m)β(m+1)we may prove this by induction onm. There are 4 cases according to the parities ofm₁and m2. Suppose for example thatm,m1andm2are all even, saym1=2m,m2=2m. Then

2^m2β(m₁)β(m₂)=2^m2+m+mβ(m)²β(m)²

=2^m+m(2^mβ(m)β(m))²

≤2^m+m(β(m+m))²

=β(2(m+m))

=β(m).

Similar calculations establish the other three cases.

Proof of Proposition1.3(c) To prove part (c) supposeq >2, let{ri|i=1, . . . , q−1} be anyq−1 distinct residue classes inR/Pand letT = {ri, π+ri|i=1, . . . , q−1}. Since this has 2 representatives from each of the residue classesr_i+P the number of distinct P-orderings of this set is(q−1)!²2^q−1. On the other hand|T| =2(q−1)= q+(q−2)andβ(2(q−1))=q!(q−2)!2^q−2according to the recurrence forβ. The ratio of these is 2−2/q >1.

Define a sequence of setsTⁿrecursively byT⁰=T,Tⁿ⁺¹= {π x+r|x∈Tⁿ, r∈ R/P}. The setTⁿhas 2qⁿ(q−1)elements and, using the recursive formula for the number ofP-orderings,

(q!)^(qn(q−1)((q−1)!)^2qn2^qn(q−1) P-orderings. On the other hand

β(qⁿ2(q−1))=β(qⁿ⁺¹+qⁿ(q−2))

=2^qn(q−2)β(qⁿ⁺¹)β(qⁿ(q−2))

=2^qn(q−2)(q!)^(n+1)qn((q−2)!)^qn(q!)^{n(q−2)qn−1}.

The quotient of the number ofP-orderings ofTⁿbyβ(|Tⁿ|)is(2−2/q)^qnwhich is

greater than 1, and increases asndoes.

Lemmas 3.10and 3.12allow an explicit formula forβ(m)to be given in terms of the coefficients in the baseqexpansion ofmand so give the upper boundβ(m)≤

!^{mlog(m)/qlog(q)}. For q=2 this gives a nonrecursive upper bound for α. Forq >2 we have no such explicit formula forα(m). Some indication of the relation between α(m)andβ(m)forq >2 is given by the behaviour of log(α(m)/β(m)). Graphs of this function are given in Figure1forq=3 andq=5.

Proposition 3.7 gives a recursive method for enumerating the P-orderings of a given set S. If all elements of S lie in the same residue class modulo P then Lemma3.3(c) can be applied to find a P-ordering equivalent set with representa- tives in at least two residue classes. The subsetsS_r and theirP-sequences,D_r, can