Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185614
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 5:13:45 PM
Last modification on : Saturday, August 11, 2018 - 11:22:01 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:09:57 AM

File

dmtcs-16-2-3.pdf
Publisher files allowed on an open archive

Identifiers

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 (2), pp.35--40. ⟨10.46298/dmtcs.2074⟩. ⟨hal-01185614⟩

Share

Metrics

Record views

70

Files downloads

852