On additive combinatorics of permutations of ℤn

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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress) (2), pp.35--40
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185614
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 17:13:45
Dernière modification le : jeudi 7 septembre 2017 - 01:03:44
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:09:57

Fichier

dmtcs-16-2-3.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185614, version 1

Collections

Citation

L. Sunil Chandran, Deepak Rajendraprasad, Nitin Singh. On additive combinatorics of permutations of ℤn. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress) (2), pp.35--40. 〈hal-01185614〉

Partager

Métriques

Consultations de la notice

133

Téléchargements de fichiers

191