Permutations in Abelian groups and the sequence \(n!\pmod p\). (Q2488833)

Let \(G\) be a finite Abelian group, \(|G|=n\), and for each permutation \(\pi=(a_1,\dots,a_n)\) of the elements of \(G\) put \(S(\pi)=\{a_1+\cdots+a_j:1\leq j\leq n\}\). The sequence in the title is a particular case when \(G\) is a \(p\)-element cyclic group and the permutation is the natural ordering. Put \[ \sigma^+(G)=\max\{|S(\pi)|\},\quad\sigma^-(G)=\min\{|S(\pi)|\} \] taken over all the \(n!\) permutations. By easy counting arguments we get \[ \sqrt n\leq\sigma^-(G)\leq\sigma^+(G)\leq n. \] In the paper it is shown that these estimates always give the correct order of magnitude; more exactly, for any group we have \(\sigma^+(G)>n/2\) and \(\sigma^-(G)<8\sqrt{2n}\). The first is a relatively easy greedy algorithm, the second, however, is an involved construction using the structure of the group. It is also proved that the expectation of \(|S(\pi)|\) for a random permutation is at least \(n/e\), and it is conjectured that this is asymptotically the correct value.