On Additive Combinatorics of Permutations of \mathbb{Z}_n

Abstract

Let ${\mathbb{Z}}_n$ denote the ring of integers modulo $n$. In this paper we consider two extremal problems on permutations of ${\mathbb{Z}}_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 the sum of any two distinct permutations in the collection is not 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 $s(n)\ge (n\varphi (n))/2^k$ where $k$ is the number of distinct prime divisors of $n$. When $n$ is an odd prime we prove $s(n)\le \frac{e^2}{\pi }n((n-1)/e{)}^{\frac{n-1}{2}}$. For the second problem, we prove $2^{(n-1)/2}.(\frac{n-1}{2})!\le t(n)\le 2^k.(n-1)!/\varphi (n)$ when $n$ is odd.

9 pages

References in corpus (1)

• Maximum size of reverse-free sets of permutations