On additive combinatorics of permutations of [Z.sub.n].

MSC2010: 11A05, 11A07, 11A41, 05E99, 05D05.

1 Introduction

For n [member of] Z, let [Z.sub.n] denote the ring {0, ..., n - 1} with + and. as addition and multiplication modulo n respectively. Let S([Z.sub.n]) denote the set of all permutations of the set [Z.sub.n]. We are interested in obtaining bounds on the maximum size of a subset P of S([Z.sub.n]) in the case when two distinct permutations in P sum up to a permutation, and in the case when no two distinct permutations in P sum up to a permutation. As far as we know the problems considered above are new, though a similar looking problem for difference of permutations is well studied, in the form of mutually orthogonal orthomorphisms of finite groups. For the sake of completeness, we discuss the connection between difference of permutations problem with the orthomorphisms problem in Section 4. The families of permutations we consider have similarities to reverse free and reverse full families of permutations as considered by Furedi et al. (2010) and Cibulka (2013).

2 Preliminaries

We recall some basic notions from elementary number theory that will be used in the paper. An element s G [Z.sub.n] is said to be invertible if there exists t G [Z.sub.n] such that st = 1 (recall that multiplication in [Z.sub.n] is modulo n). The set of all invertible elements of [Z.sub.n] is called the unit group of [Z.sub.n] and is denoted by [Z.sup.x.sub.n]. It is easily seen that [Z.sup.x.sub.n] is a group under multiplication. We know that k [member of] [Z.sub.n] is invertible if and only if gcd(k, n) = 1. The cardinality of the set {k [member of] Z: 1 [greater than or equal to] k [greater than or equal to] n - 1, gcd(k, n) = 1} is denoted by [phi](n), also known as Euler's totientfunction in literature. The following results are well known.

Lemma 2.1 Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [p.sub.1], ..., [p.sub.k] are distinct prime divisors of n. Then, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Lemma 2.2 (Chinese Remainder Theorem) Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [p.sub.1], ..., [p.sub.k] are distinct prime divisors of n. Then, we have the following isomorphism

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

From the above lemma we see that s = ([s.sub.1], ..., [s.sub.k]) is invertible in [Z.sub.n] if and only if [s.sub.i] is invertible in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all i = 1, ..., k.

Notation 2.3 We will denote permutations of [Z.sub.n] as n-tuples ([[sigma].sub.1], ..., [[sigma].sub.n]) where [[sigma].sub.i] [member of] [Z.sub.n], and all [[sigma].sub.i] are distinct. This is not to be confused with the cycle representation of a permutation, which is customary in algebra. Since we do not use cycle representation of permutations in this paper, we hope there is no confusion. Let [sigma] = ([[sigma].sub.1], ..., [[sigma].sub.n]) and [tau] = ([[tau].sub.1], ..., [[tau].sub.n]), be n- tuples over [Z.sub.n]. Then a [+ or -] t denotes the tuple ([[sigma].sub.1] [+ or -] [[tau].sub.1], ..., [[sigma].sub.n] [+ or -] [[tau].sub.n]). For c [member of] [Z.sub.n], c.[sigma] will denote the tuple (c[[sigma].sub.1], ..., c[[sigma].sub.n]), and c + [sigma] will denote the tuple (c + [[sigma].sub.1], ..., c + [[sigma].sub.n]).

Lemma 2.4 Let n be even and ([a.sub.1], ..., [a.sub.n]) and ([b.sub.1], ..., [b.sub.n]) be two permutations of [Z.sub.n]. Then a + b is not a permutation of [Z.sub.n].

Proof: Let c = a + b = ([c.sub.1], ..., [a.sub.n]). For contradiction, assume that c is a permutation. Treating a, b, c as n-tuples over Z we have, [c.sub.i] [equivalent to] [a.sub.i] + [b.sub.i] (mod n). Summing up over all i, we have,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which is a contradiction as (n - 1)/2 is not an integer when n is even. This proves the lemma.

Lemma 2.5 Let a = ([a.sub.0], ..., [a.sub.n-1]) and b = ([b.sub.0], ..., [b.sub.n-1]) be distinct permutations of the set {0, ..., n-1} such that the component-wise sums [c.sub.i] = [a.sub.i] + [b.sub.i] are all distinct. Then there exist 0 [greater than or equal to] j, k [greater than or equal to] n - 1 such that [c.sub.j] = [c.sub.k] + 1.

Proof: Without loss of generality assume [c.sub.i] = [a.sub.i] + [b.sub.i] satisfy the ordering [c.sub.0] < [c.sub.1] < ... < [c.sub.n-1]. Now suppose the claim is not true. Then we have, [c.sub.i] - [c.sub.i-1] [less than or equal to] 2 for 1 [greater than or equal to] i [greater than or equal to] n - 1. Summing up we get 2n - 2 [greater than or equal to] [[summation].sup.n-1.sub.i=1] ([c.sub.i] - [c.sub.i-1]) = [c.sub.n-1] - [c.sub.0] [greater than or equal to] 2n - 2. Thus [c.sub.i] - [c.sub.i-1] = 2 for all 1 [greater than or equal to] i [greater than or equal to] n - 1, which implies ci = 2i for all 0 [greater than or equal to] i [greater than or equal to] n - 1. Now [a.sub.0] + [b.sub.0] = [c.sub.0] = 0 implies [a.sub.0] = [b.sub.0] = 0. Now [c.sub.1] = [a.sub.1] + [b.sub.1] = 2, therefore we must have [a.sub.1] = [b.sub.1] = 1. Continuing this way, we conclude that [a.sub.i] = [b.sub.i] = i for all 0 [greater than or equal to] i [greater than or equal to] n - 1, contradicting the fact that the permutations were distinct.

3 Results and Proofs

In this section, we consider the maximum sizes of collections of permutations of [Z.sub.n] under two different constraints, namely,

(i) Sum of any two distinct permutations in the collection is again a permutation (not necessarily in the collection). We will say that such a collection satisfies property (P1).

(ii) No sum of two distinct permutations in the collection is a permutation. We will say that such a collection satisfies property (P2).

Let s(n) and t(n) denote the maximum sizes of the collections of permutations of [Z.sub.n] satisfying (P1) and (P2) respectively. We prove the following:

Theorem 3.1 Let n > 3 be an odd integer and s(n), t(n) be as defined. Then, we have

(a) n[phi](n)/[2.sup.k] [greater than or equal to] s(n) [greater than or equal to] n! x [2.sup.-(n-1)/2]/((n - 1)/2)!,

(b) ((n - 1)/2)! x [2.sup.(n-1)/2] [greater than or equal to] t(n) [greater than or equal to] [2.sup.k](n - 1)!/[phi](n),

where k denotes the number of distinct prime divisors of n.

The sizes of collections of permutations of [Z.sub.n] satisfying (P1) and (P2) satisfy a similar inequality as the sizes of the families of reverse free and reverse full permutations considered by Furedi et al. (2010) and Cibulka (2013).

Lemma 3.2 For an integer n [less than or equal to] 1, let s(n),t(n) be as defined. Then, we have s(n) x t(n) [greater than or equal to] n\.

Proof: Let S = {[[sigma].sub.1], ..., [[sigma].sub.s]} and T = {[[tau].sub.1], ..., [[tau].sub.t]} be collections of permutations satisfying (P1) and (P2) respectively. We show that [[sigma].sub.i] [upsilon] [T.sub.j] are distinct for all 1 [greater than or equal to] i [greater than or equal to] s and 1 [greater than or equal to] j [greater than or equal to] t, which would imply st [greater than or equal to] n!. For sake of contradiction, without loss of generality assume [[sigma].sub.1] [upsilon] [[tau].sub.1] = [[sigma].sub.2] [upsilon] [[tau].sub.2]. Now consider the collections of permutations S' = {[[sigma].sup.-1.sub.1] [upsilon] [[sigma].sub.i]: 1 [greater than or equal to] i [greater than or equal to] s} and T' = {[[tau].sub.j] [upsilon] [[tau].sup.-1.sub.1]: 1 [greater than or equal to] j [greater than or equal to] t}. It can be seen that S' and T' also satisfy (P1) and (P2) respectively. We note that id g S' n T', where id denotes the identity permutation. Since [[sigma].sup.-1.sub.1] [upsilon] [[sigma].sub.2] [member of] S', id + [[sigma].sup.-1.sub.1] [upsilon] [[sigma].sub.2] is a permutation. Composing with the permutation [[sigma].sup.-1.sub.2] [upsilon] [[sigma].sub.1], we conclude that id + [[sigma].sup.-1.sub.2] [upsilon] [[sigma].sub.1] is a permutation. However [[sigma].sup.-1.sub.2] [upsilon] [[sigma].sub.1] = [[tau].sub.2] [upsilon] [[tau].sup.-1.sub.1] by assumption, and thus id + [[tau].sub.2] [upsilon] [[tau].sup.-1.sub.1] is a permutation. But this is a contradiction as both id and [[tau].sub.2] [upsilon] [[tau].sup.-1.sub.1] are in the collection T', which satisfies (P2). The lemma now follows.

From Lemma 2.4, we note that s(n) = 1 when n is even. Now we present a construction for the lower bound on s(n) when n is odd.

Lemma 3.3 Let n be an odd number [less than or equal to] 3. Then s(n) [less than or equal to] (n[phi](n))/[2.sup.k] where [phi](n) is the Euler's totient function and k is the number of distinct prime divisors of n.

Proof: Our construction is based on the following observations.

(a) For a permutation [tau] of [Z.sub.n], k.[tau] is a permutation of [Z.sub.n] if and only if k is invertible in [Z.sub.n].

(b) For a permutation [tau] of [Z.sub.n], k + [tau] is a permutation for all k [member of] [Z.sub.n].

(c) Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [p.sub.i]'s are distinct prime divisors of n. Then there exists a subset S of invertible elements of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that for any x, y [member of] S, x + y is invertible in [Z.sub.n]. To describe the set S, we use the isomorphism in Lemma 2.2. Let S = {s G [Z.sub.n]: s = ([s.sub.1], ..., [s.sub.k]) where [s.sub.i] [equivalent to] [c.sub.i] mod pi for some 1 [greater than or equal to] [c.sub.i] [greater than or equal to] ([p.sub.i] - 1)/2}. Note that in the description of S, each [s.sub.i] has [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] choices, and hence the set S has the desired cardinality. Further each element of S is invertible in [Z.sub.n]. Now for s, t [member of] S, we have s + 1 = ([s.sub.1] + [t.sub.1], ..., [s.sub.k] + [t.sub.k]) where s = ([s.sub.1], ..., [s.sub.k]) and t = ([t.sub.1], ..., [t.sub.k]). By definition of S, observe that [s.sub.i] + [t.sub.i] [??] 0 (mod pi) for all 1 [greater than or equal to] i [greater than or equal to] k. Thus s + 1 is invertible in [Z.sub.n].

Now consider the set P = {s.(x + 0, x + 1, ..., x + n - 1): s [member of] S, x [member of] [Z.sub.n]}. By observations (a), (b) and (c), we see that P consists of permutations of [Z.sub.n]. Let a, t be two distinct permutations in P with a = s.(x + 0, ..., x + n - 1) and [tau] = t.(y + 0, ..., y + n - 1). Then [sigma] + [tau] = (sx + ty) + (s + 1).(0, 1, ..., n - 1). Since s + t is invertible, by observations (a) and (b), we conclude that a + t is a permutation. Thus P satisfies (P1). Finally we observe that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This proves the lemma.

Remark 3.4 We note that when n is a prime number, the bound in Lemma 3.3 reduces to n(n - 1)/2.

From Lemma 2.4, we see that t(n) = 1 when n is an even integer. We note that when n is even, we have equality in Lemma 3.2. Now we consider the lower bound for t(n) when n is an odd integer.

Lemma 3.5 Let n be an odd number. Then, we have t(n) [less than or equal to] [2.sup.(n-1)/2] x (n-1/2)!, where k is the number of distinct prime divisors of n.

Proof: We say the pair of permutations ([a.sub.0], ..., [a.sub.n-1]) and ([b.sub.0], ..., [b.sub.n-1]) of the set {0, ..., n - 1} are admissible if the sums [a.sub.i] + [b.sub.i], 0 [greater than or equal to] i [greater than or equal to] n - 1, are not all distinct (the addition being in Z). We construct a collection P of mutually admissible permutations of {0, ..., n - 1}. Note that P when viewed as a set of permutations of [Z.sub.n], satisfies (P2). Let m = (n - 1)/2. For 0 [greater than or equal to] i [greater than or equal to] m - 1, let [B.sub.i] = (2i, 2i + 1) and [[bar.B].sub.i] = (2i + 1, 2i). Let c = [c.sub.0][c.sub.1] ... [cm.sub.-1] be a binary string of length m, and a be a permutation of {0, ..., m - 1}. Define [P.sub.[sigma],c] = ([x.sub.0], [x.sub.1], ..., [x.sub.n-2], [x.sub.n-1]) where,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

for 0 [greater than or equal to] i [greater than or equal to] m - 1 and [x.sub.n-1] = n - 1. It is easily observed that [P.sub.[sigma],c] is a permutation of the set {0, ..., n - 1} and [P.sub.[sigma],c] [not equal to] [P.sub.[sigma]',c'] for ([sigma], c) [not equal to] ([sigma]', c'). Let P denote the collection of permutations {[P.sub.[sigma],c]}. We now show that any two permutations in the collection P are admissible. Let [P.sub.[sigma],c] and [P.sub.[sigma]',c'] be two distinct permutations in P. We consider two cases:

Case: c [not equal to] c'. Let i be such that [sigma] [not equal to] [sigma]'. Without loss of generality assume [c.sub.i] = 0, [c'.sub.i] = 1. Let [P.sub.[sigma],c] = ([x.sub.0], ..., [x.sub.n-1]) and [P.sub.[sigma',c'] = ([x'.sub.0], ..., [x'.sub.n-1]). Then we have, ([x.sub.2i], [x.sub.2i+1]) = [B.sub.[sigma](i)] = (a, a + 1) and ([x'.sub.2i], [x'.sub.2i+1]) = [[bar.B].sub.[sigma]'(i)] = (b + 1, b) for some a, b. Thus [x.sub.2i] + [x'.sub.2i] = [x.sub.2i+1] + [x'.sub.2i+1] = a + b + 1, and hence the permutations are admissible.

Case: c = c'. In this case we must have [sigma] [not equal to] [sigma]'. In the block [B.sub.i] = (2i, 2i + 1), let us call 2i as the little end and 2i + 1 as the big end. Then c = c' implies that in the component-wise addition of [P.sub.[sigma],c] and [P.sub.[sigma]',c'] the little ends are summed with little ends, and big ends are summed with big ends. Let L be the set of sums of little ends, i.e, L = {2[sigma](i) + 2[sigma]'(i): 0 [greater than or equal to] i [greater than or equal to] m - 1} and B be the sums of big ends, i.e., B = {2[sigma](i) + 2[sigma]'(i) + 2:0 [greater than or equal to] i [greater than or equal to] m - 1}. Clearly the permutations Pac and Pa\c> are admissible if [sigma](j) + [sigma]'(j) = [sigma](k) + [sigma]'(k) for some 0 [greater than or equal to] j, k [greater than or equal to] m - 1. Assume that it is not the case. Then we show that L [intersection] B is non-empty which will prove that [P.sub.[sigma],c] and [P.sub.[sigma]',c'] are admissible. By Lemma 2.5, there exist 0 [greater than or equal to] j, k [greater than or equal to] m - 1 such that [sigma](j) + [sigma]'(j) = [sigma](k) + [sigma]'(k) + 1, or 2[sigma](j) + 2[sigma]'(j) = 2[sigma](k) + 2[sigma]'(k) + 2. We see that the left side of the identity is in L and the right side is in B. Thus L [intersection] B is non-empty.

Hence the collection of permutations [P.sub.[sigma],c], when viewed as permutations of [Z.sub.n] satisfy (P2). Finally we note that the number of permutations is [2.sup.m] x m! = [2.sup.(n-1)/2] x (n-1/2)!. This completes the proof.

We can now complete the proof of Theorem 3.1.

Proof of Theorem 3.1: From Lemmata 3.2, 3.3 and 3.5, we have s(n) [greater than or equal to] [2.sup.-(n-1)/2] x n!/((n - 1!)/2)!, and t(n) [greater than or equal to] [2.sup.k](n - 1)!/[phi](n). The result then follows from the lower bounds for s(n) and t(n). ?

Remark 3.6 We note that for a prime number n, the upper bound for t(n) is roughly [(n/e).sup.n] [square root of n] whereas the lower bound is roughly [(n/e).sup.n/2] [square root of n]. Thus there is a quadratic gap between the upper and lower bounds. We also mention that one way to obtain permutations summing up to a non permutation is to consider a family of permutations with mutual reverses. Two permutations [sigma], [tau] of {0, ..., n - 1} are said to have a mutual reverse if there exist i [not equal to] j such that [sigma](i) = [tau](j) and [sigma](j) = [tau](i). A family of permutations, every two of which have a mutual reverse is called reverse full, Furedi et al. (2010). Note that a reverse full family of permutations satisfies (P2). From a result of Cibulka (2013) on size of reverse-free families of permutations, the maximum size of a reverse full family of permutations on n symbols is at most [n.sup.n/2+0(log n)], though we are unaware of any non-trivial lower bound for the same. Our construction achieves ~[(n/e).sup.n/2] [square root of n], but under a much more flexible constraint.

4 Differences of Permutations being Permutation

In this section, we wish to obtain upper and lower bounds on the maximum size of set P [subset or equal to] S([Z.sub.n]) such that for any two distinct permutations [sigma], [tau] [member of] P, [sigma] - [tau] is also a permutation of [Z.sub.n]. We say that P C S([Z.sub.n]) satisfies property (P3) if for any two [sigma], [tau] [member of] P, [sigma] [not equal to] [tau], [sigma] - [tau] is a permutation of [Z.sub.n]. Let f (n) = max{[absolute value of P]: P [subset or equal to] S ([Z.sub.n]) satisfies (P3)}.

The above problem is only superficially different from the well studied problem of finding mutually orthogonal orthomorphisms of finite groups (See Evans (2002)). For a finite group G, abijection [theta]: G [right arrow] G is called an orthomorphism of G if the map x [right arrow] [theta](x) - x is a bijection. Two orthomorphisms [theta], [phi] are called orthogonal if [theta] - [phi] is a bijection. It is not hard to see that a set of k permutations of [Z.sub.n] satisfying (P3) gives a set of k - 1 mutually orthogonal orthomorphisms of [Z.sub.n] and vice versa.

4.1 Latin Squares

Orthogonal orthomorphisms have been used in construction of mutually orthogonal Latin squares (MOLS). Although the construction appears in any standard text on combinatorics (cf. Lint and Wilson (2001)), we describe it in our setting. We will say a map L: [Z.sub.n] x [Z.sub.n] [right arrow] [Z.sub.n] to be an n x n Latin square, if (i) L(i, j) [not equal to] L(i', j) for i [not equal to] i' and (ii) L(i, j) [not equal to] L(i, j') for j [not equal to] j'. One can think of L as n x n square array with entries from {0, ..., n - 1 } where each row and column contains distinct entries. Two n x n Latin squares L, L' are called orthogonal if L(i, j) = x and L'(i, j) = y has a unique solution for all (x, y) [member of] [Z.sub.n] x [Z.sub.n]. The following is easy to verify:

Lemma 4.1 Let [[sigma].sub.1], ..., [[sigma].sub.k] be a collection of permutations of [Z.sub.n] satisfying (P3). Then, there are k mutually orthogonal Latin squares [L.sub.1], ..., [L.sub.k] where the Latin square [L.sub.r] is defined by [L.sub.r](i, j) = i + [[sigma].sub.r](j).

If we write the permutations of P as rows of a matrix, we get a [absolute value of P] x n matrix over [Z.sub.n] with the property that the difference of any two distinct rows is a permutation of [Z.sub.n]. Such matrices have been used in connection with constructions of Latin squares and orthogonal arrays (cf. (Lint and Wilson, 2001, Chapter 22)). Well known bounds for mutually orthogonal orthomorphisms yield the following lemma.

Lemma 4.2 For n [less than or equal to] 2, we have

(a) f (n) [greater than or equal to] n - 1,

(b) f (n) = 1, when n is an even number;

(c) f (n) = n - 1, when n is a prime number.

Question 4.3 What are the values of f (n) for odd composite numbers n? From the results of Evans (2002) it follows that for odd numbers n > 3 and n not divisible by 9, we have f(n) [less than or equal to] 3.

Acknowledgements

The authors would like to thank the anonymous referees for their useful comments. The Lemma 3.2 in particular is due to a referee, which has greatly simplified the paper and also enhanced the symmetry of the results. The earlier version of the paper contained separate upper bound proofs for s(n) and t(n), however using Lemma 3.2, those are implied by respective lower bounds on s(n) and t(n). The second author is supported by VATAT Post-doctoral Fellowship, Council of Higher Education, Israel. The third author thanks National Mathematics Initiative, India for support.

References

J. Cibulka. Maximum size of reverse-free sets of permutations. SIAM J. Discrete Math., 27(1):232-239, 2013.

A. B. Evans. On orthogonal orthomorphisms of cyclic and non-abelian groups. Discrete Mathematics, 243:229-233, 2002.

Z. Furedi, I. Kantor, A. Monti, and B. Sinaimeri. On reverse-free codes and permutations. SIAM J. Discrete Math., 24(3):964-978, 2010.

J. H. V. Lint and R. M. Wilson. A Course in Combinatorics. Cambridge University Press, 2001.

L. Sunil Chandran (1) * Deepak Rajendraprasad (2) Nitin Singh (3)

(1) Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India

(2) Department of Computer Science, University of Haifa, Haifa, Israel

(3) Department of Mathematics, Indian Institute of Science, Bangalore, India

received 2ndDec. 2013, revised 27thMar. 2014, accepted 27thApr 2014.

* Email: sunil@csa.iisc.ernet.in
Author: Printer friendly Cite/link Email Feedback Chandran, L. Sunil; Rajendraprasad, Deepak; Singh, Nitin Discrete Mathematics and Theoretical Computer Science Report Jun 1, 2014 3975 Uniquely monopolar-partitionable block graphs. A matroid associated with a phylogenetic tree. Combinatorics Mathematical research Permutations