On Additive Combinatorics of Permutations of ℤn
L. Sunil Chandran, Deepak Rajendraprasad, Nitin Singh
Abstract
Let ℤn denote the ring of integers
modulo n. A permutation of
ℤn is a sequence of
n distinct elements of ℤn.
Addition and subtraction of two permutations is defined
element-wise. In this paper we consider two extremal problems on
permutations of ℤn, 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))/2k≤s(n)≤n!·
2-(n-1)/2((n-1)/2)!
and
2(n-1)/2·(n-1 / 2)!≤t(n)≤
2k·(n-1)!/φ(n), where k is
the number of distinct prime divisors of n and
φ is the Euler's totient function.
Full Text: PDF PostScript