On the Minimum Number of Completely 3-Scrambling Permutations

On the Minimum Number of Completely 3-Scrambling Permutations

Jun Tarui

Department of Information and Communication Engineering, University of Electro-Communications Chofu, Tokyo 182-8585 Japan [email protected]

A familyP = {π1, . . . , πq}of permutations of[n] = {1, . . . , n}iscompletely k-scrambling[Spencer, 1972;

F¨uredi, 1996] if for any distinctkpointsx1, . . . , xk∈[n], permutationsπi’s inPproduce allk!possible orders on πi(x1), . . . , πi(xk). LetN^∗(n, k)be the minimum size of such a family. This paper focuses on the casek= 3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to F¨uredi for comparison.

2

log₂elog₂n≤N^∗(n,3)≤2 log₂n+ (1 +o(1)) log₂log₂n.

We also prove the existence oflimn→∞N^∗(n,3)/log₂n=c3. Determining the valuec3and proving the existence oflimn→∞N^∗(n, k)/log₂n=ckfork≥4remain open.

1 Introduction and Summary

Following Spencer [Sp72] and F¨uredi [F¨u96], call a familyP = {π1, . . . , πq}of permutations of[n]

completelyk-scramblingif for any distinctx1, x2, . . . , xk ∈[n], there exists a permutationπi ∈ Psuch that πi(x1) < πi(x2) < · · · < πi(xk); or equivalently, πi’s applied to x1, x2, . . . , xk produce all k!

orders. This paper focuses on the casek= 3. Following F¨uredi [F¨u96], say that a familyPis3-mixingif for any distinctx, y, z∈[n], there is a permutationπi ∈ Pthat placesxbetweenyandz, i.e., there is a permutationπisuch that eitherπi(y)< πi(x)< πi(z)orπi(z)< πi(x)< πi(y).

LetN^∗(n, k)be the minimumqsuch that completelyk-scramblingqpermutations exist for[n]. The best known bounds forN^∗(n, k)can be expressed as follows. For arbitrary fixedk≥3, asn→ ∞,

1

log₂e(k−1)! +o(1)

log₂n≤N^∗(n, k)≤ k

log₂(k!/(k!−1))log₂n. (1) The coefficient of the upper bound in (1) isΘ(k·k!); thus the gap between the coefficients of the lower and upper bounds in (1) isΘ(k²). The upper bound in (1) was shown by Spencer [Sp72] by a probabilistic argument, where one considers the probability that some order among somex1, . . . , xkis never produced byqindependent random permutations. The lower bound in (1) was first proved by F¨uredi [F¨u96] for k = 3, and was proved fork ≥3by Radhakrishnan [Ra03]; entropy arguments are used in both work;

1365–8050 c2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

the factorlog₂ein the lower bound comes from the fact thatR1

0 H(x)dx= (log₂e)/2, whereH(x)is the binary entropy function.

As for the casek= 3, F¨uredi [F¨u96] has shown that 2

log₂elog₂n≤N^∗(n,3)≤ 10

log₂7

log₂n+O(1), (2)

where the coefficients oflog₂nare1.38. . .and3.56. . .in (2). The lower bound in (2) is in fact a lower bound for the case where we only require a family to be 3-mixing. No better lower bound for completely 3-scrambling families is known. If a familyP ={π1, . . . , π_q}is 3-mixing, by adding toP theqreverse permutations ofπ_i’s mappingx7→n+1−πi(x), we can obtain completely 3-scrambling2qpermutations.

Ishigami [Is95] has given an efficient recursive construction of 3-mixing families starting with a 3-mixing family of five permutations of{1, . . . ,7}. F¨uredi [F¨u96] gave the upper bound in (2) by making these observations and doubling the size of Ishigami’s 3-mixing family.

In this paper, we first give an improved upper bound forN^∗(n,3)by a simple construction. Letf(q) be the maximumnsuch that completely3-scramblingqpermutations exist for[n].

Theorem 1

f(q)≥

bq/2c bq/4c

.

The following upper bound onN^∗(n,3)readily follows.

Corollary 1

N^∗(n,3)≤2 log₂n+ (1 +o(1)) log₂log₂n.

It seems natural to conjecture that for every fixedk≥3, asn→ ∞,N^∗(n, k) = (ck+o(1)) log₂nfor someck. We show the existence of limit for the casek= 3:

Theorem 2

q→∞lim

log₂f(q)

q =C exists.

The following immediately follows.

Corollary 2

n→∞lim

N^∗(n,3)

log₂n = 1/C=c3 exists.

2 Proofs

We can identify in a natural way a total orderφon[n]and the permutation of[n]induced byφ; thus we speak interchangeably in terms of permutations and total orders. In fact for an arbitrary finite setU with nelements, we can assume for our purposes thatU is identified with[n]in an arbitrary fixed way, and speak about permutations ofUin terms of total orders onU.

Proof of Theorem 1.Putr=bq/2cand letF ={A1, A2, . . . , Am}be a family of subsets of{1, . . . , r}

such thatAi6⊆Ajfor alli6=j; i.e.,Fis an antichain.

For each pointx∈ {1, . . . , r}, define two ordersφxandψxonF. In both ordersφxandψx, the sets Aicontaining the pointxare smaller than all the setsAk not containingx. Among the sets containingx and among the sets not containingx: in the orderφx,Ai < Ajprecisely wheni < j; in the orderψx, this is reversed, andAi< Ajprecisely wheni > j.

We claim that for arbitrary distincti, j, k∈[m], there exists an orderθ∈ {φ₁, ψ₁, φ₂, ψ₂, . . . , φ_r, ψ_r} such thatA_i < A_j < A_k in the orderθ. To see the claim fix a pointx∈ (A_i−A_k)6=∅, i.e.,x∈ A_i andx6∈Ak. Depending on whetherx∈Ajorx6∈Aj, we specify an orderθthat produces the ordering Ai< Aj < Ak.

Casex∈A_j: Letθ=φ_xifi < jand letθ=ψ_xifi > j.

Casex6∈Aj: Letθ=φxifj < kand letθ=ψxifj > k.

Clearly under the orderθ,A_i < A_j < A_k. Hence the2rorders thus defined on[m]are completely 3-scrambling. We obtain the theorem by taking F to be the family of all subsets of {1, . . . , r} with cardinalitybr/2c=bq/4c.2

Proof of Theorem 2. Our proof of Theorem 2 will be basically similar to F¨uredi’s proof [F¨u96] of the existence oflim_q→∞(log₂g(q))/q, whereg(q)is the maximum nsuch that 3-mixingq permutations exist for[n]. To make a recursive construction go through for scrambling permutations, we introduce and use red-blue colored doubly reversing permutations: Call a familyP ={π1, . . . , πq}of permutations of [n]2-reversingif there is a coloringχ:{π1, . . . , πq} → {red,blue}such that for every distincti, j∈[n], there are redπκ, redπλ, blueπµ, and blueπνsatisfying

πκ(i)< πκ(j), πλ(i)> πλ(j); πµ(i)< πµ(j), πν(i)> πν(j).

For a permutationπof [n], letreverse(π)be the permutation of[n]mappingx7→ n+ 1−π(x). Let P be a family of permutations of[n]with|P| ≥ 3. We can easily transformP to a 2-reversing family by adding at most two permutations as follows. Arbitrarily fix two distinct permutationsσ, τ ∈ Psuch thatτ 6= reverse(σ); suchσandτexist since|P| ≥3; addreverse(σ)andreverse(τ)toP; colorσand reverse(σ)red; colorτandreverse(τ)blue; color the remaining permutations arbitrarily.

Letf^∗(q)be the maximumnsuch that completely 3-scramblingand2-reversingqpermutations exist for[n]. By definition and from the discussion above we have

f^∗(q)≤f(q)≤f^∗(q+ 2). (3)

Claim 1

f^∗(q+r)≥f^∗(q)f^∗(r).

For the moment we assume that Claim 1 holds and go on to derive Theorem 2.

The sequence(1/q) log₂f^∗(q)is bounded above. ¿From this and Claim 1 it follows by classical calcu- lus (Fekete’s theorem) that

q→∞lim 1

qlog₂f^∗(q) = lim sup

q→∞

1

qlog₂f^∗(q).

From (3) it now follows that

q→∞lim 1

qlog₂f(q) = lim

q→∞

1

qlog₂f^∗(q).

Thus we are left to prove Claim 1.

LetS = {σ1, . . . , σq} andT = {τ1, . . . , τr} be completely 3-scrambling and 2-reversing families of permutations of[l]and[m]respectively. Assume that both families are validly red-blue colored. Let U ={(i, j) : 1≤i≤l,1≤j≤m}; think ofUas a matrix withlrows andmcolumns. We will show that we can defineq+rorders onU that are completely 3-scrambling and 2-reversing. Note that from this Claim 1 follows.

Letx= (i, j)andy= (i⁰, j⁰)be distinct elements ofU. Fork= 1, . . . , q, define the orderσ˜kusingσk

in a row-major form as follows: ifi6=i⁰, orderxandyaccording to the order ofσ_k(i)andσ_k(i⁰). When i=i⁰: ifσ_k is red,(i, j)<(i, j⁰)⇐⇒ j < j⁰; ifσ_k is blue,(i, j)<(i, j⁰)⇐⇒j > j⁰. Similarly for k= 1, . . . , r, define the orderτ˜_konU in a column-major form: whenj6=j⁰,x < y⇐⇒τ_k(j)< τ_k(j⁰);

whenj = j⁰: ifτ_k is red,(i, j)<(i⁰, j)⇐⇒ i < i⁰; ifτ_k is blue,(i, j)<(i⁰, j)⇐⇒ i > i⁰. As for colors, letσ˜_kand˜τ_kinherit the colors ofσ_kandτ_k.

Claim 2 The familyF={˜σ1, . . . ,σ˜q,τ˜1, . . . ,τ˜r}is completely 3-scrambling and 2-reversing.

To see Claim 2, letx1= (i1, j1), x2= (i2, j2), x3= (i3, j3)be distinct elements ofU. Ifi1, i2, i3are all distinct,σk’s produce all six orderings ofi1, i2, i3, and henceσ˜k’s produce all six orderings ofx1, x2, x3. Similar arguments withτk’s andτ˜k’s apply for the case whenj1, j2, j3are all distinct.

The remaining case is when |{i1, i2, i3}| = |{j1, j2, j3}| = 2. We write, e.g., 231 to express the orderingx2< x3< x1. Assume that

x1= (i, j), x2= (i, j⁰), x3= (i⁰, j), i6=i⁰, j6=j⁰.

We will see that all six orderings ofx₁, x₂, x₃ are produced by checking that (1) all the four orders in whichx₃is smallest or largest, i.e., 312, 321, 123, 213 are produced and that (2) all the four orders in whichx2is smallest or largest are produced.

A redσ˜_κand a blue˜σ_µsatisfyingσ_κ(i)< σ_κ(i⁰)andσ_µ(i)< σ_µ(i⁰)produce 123 and 213 respectively.

Similarly, a redσ˜_λ and a blueσ˜_ν satisfyingσ_λ(i) > σ_λ(i⁰)andσ_ν(i) > σ_ν(i⁰)produce 312 and 321 respectively. Thus all the four orders in whichx₃is smallest or largest are produced. Similarly, two red

˜

τ’s and two blueτ˜’s orderingjandj⁰in both directions produce the four orders in whichx₂is smallest or largest.

Finally, ifx = (i, j)andy = (i⁰, j⁰)are distinct points inU, either (i) i 6= i⁰ or (ii)j 6= j⁰. The 2-reversing condition is satisfied by˜σ_k’s in case (i) and byτ˜_k’s in case (ii).2

Acknowledgements

The author thanks the anonymous referees for helpful comments.

References

[F¨u96] Z. F¨uredi. Scrambling Permutations and Entropy of Hypergraphs,Random Structures and Al- gorithms, vol. 8, no. 2, pp. 97–104, 1996.

[Is95] Y. Ishigami. Containment Problems in High-Dimensional Spaces,Graphs and Combinatorics, vol. 11, pp. 327–335, 1995.

[Ra03] J. Radhakrishnan. A Note on Scrambling Permutations, Random Structures and Algorithms, vol. 22 , no. 4, pp. 435–439, 2003.

[Sp72] J. Spencer. Minimal Scrambling Sets of Simple Orders,Acta Mathematica Hungarica, vol. 22, pp. 349–353, 1972.