Chandran, L. Sunil and Rajendraprasad, Deepak and Singh, Nitin - On additive combinatorics of permutations of ℤ<sub>n</sub>

dmtcs:2074 - Discrete Mathematics & Theoretical Computer Science, June 1, 2014, Vol. 16 no. 2
On additive combinatorics of permutations of ℤ<sub>n</sub>

Authors: Chandran, L. Sunil and Rajendraprasad, Deepak and Singh, Nitin

Let ℤ<sub>n</sub> denote the ring of integers modulo n. A permutation of ℤ<sub>n</sub> is a sequence of n distinct elements of ℤ<sub>n</sub>. Addition and subtraction of two permutations is defined element-wise. In this paper we consider two extremal problems on permutations of ℤ<sub>n</sub>, namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that no sum of two distinct permutations in the collection is a permutation. Let the sizes be denoted by s(n) and t(n) respectively. The case when n is even is trivial in both the cases, with s(n)=1 and t(n)=n!. For n odd, we prove (nφ(n))/2<sup>k</sup>≤s(n)≤n!· 2<sup>-(n-1)/2</sup>((n-1)/2)! and 2<sup>(n-1)/2</sup>·(n-1 / 2)!≤t(n)≤ 2<sup>k</sup>·(n-1)!/φ(n), where k is the number of distinct prime divisors of n and φ is the Euler's totient function.

Source : oai:HAL:hal-01185614v1
Volume: Vol. 16 no. 2
Section: PRIMA 2013
Published on: June 1, 2014
Submitted on: December 2, 2013
Keywords: reverse free families,orthomorphisms,sums of permutations,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]