PERMUTATIONS IN ABELIAN GROUPS AND THE SEQUENCE n!(mod p)

VSEVOLOD F. LEV

Abstract. We show that for any finite abelian group G there is a permutation (g_{1}, …, g_{|G|}) of the elements of G such that the number of distinct sums of the form g_{1} +⋯+g_{n} (1 ≤ n ≤ |G|) is O(\sqrt{|G|}), and another permutation for which the number of these sums is Ω(|G|). These estimates are best possible.

1. Introduction: background and summary of results

How many distinct residue classes modulo a given prime p are represented among the numbers 1!, 2!, …, (p−1)! ? This is [G94, Problem F11]. We prefer to re-state the question additively, fixing a primitive root g modulo p and passing to indices with respect to g; one asks then how many distinct elements of the cyclic group C_{p−1} are there among the members of the (p − 1)-term sequence

ind 1, ind 1 + ind 2, …, ind 1 + ind 2 + ⋯ + ind(p − 1).

This is a sequence of the form

a_{1}, a_{1} + a_{2}, …, a_{1} + a_{2} + ⋯ + a_{p−1}  (1)

where (a_{1}, …, a_{p−1}) is a permutation of C_{p−1}. To deal with constructions of this kind, for a finite subset A of an abelian group denote by Π_{A} the set of all |A|! permutations of A, and with each permutation π = (a_{1}, …, a_{|A|}) ∈ Π_{A} associate the set

S(π) := {a_{1} + ⋯ + a_{j}: 1 ≤ j ≤ |A|}

of all group elements, representable as a “partial sum” of π. Now for a finite abelian group G put

σ^{+}(G) := max{|S(π)|: π ∈ Π_{G}}

and

σ^{−}(G) := min{|S(π)|: π ∈ Π_{G}},

the largest and the smallest possible number of partial sums for a permutation π ∈ Π_{G}.

Example 1. The permutation set Π_{{0}} of the trivial group {0} consists of one single permutation π = (0), hence σ^{−}({0}) = σ^{+}({0}) = |S(π)| = 1. If g is the non-zero element of the cyclic group C_{2} then Π_{C_{2}} = {π_{1}, π_{2}}, where π_{1} = (0, g) and π_{2} = (g, 0); as S(π_{1}) = {0, g} and S(π_{2}) = {g} we have σ^{−}(C_{2}) = 1 and σ^{+}(C_{2}) = 2. If now g is a non-zero element of the cyclic group C_{3} then the permutations of C_{3} are

π_{1} = (0, g, 2g), π_{2} = (2g, 0, g), π_{3} = (g, 2g, 0),
π_{4} = (0, 2g, g), π_{5} = (g, 0, 2g), π_{6} = (2g, g, 0);

since |S(π_{i})| = 2 for any i ∈ [1, 6], we have σ^{−}(C_{3}) = σ^{+}(C_{3}) = 2.

Back to the general case, we notice that |S(π)| ≤ |G| for all π ∈ Π_{G} whence σ^{+}(G) ≤ |G|. On the other hand, if π = (g_{1}, …, g_{|G|}) ∈ Π_{G} then any element of G, other than g_{1} and 0, is representable as a difference of two distinct elements of S(π). It follows that |S(π)|(|S(π)| − 1) ≥ |G| − 2 which yields |S(π)| ≥ \sqrt{|G|}, provided that |G| ≥ 3. Along with Example 1 this shows that σ^{−}(G) ≥ \sqrt{|G|} holds unless |G| = 2. This last observation originates from [GLS] (where it is presented for the special case G = C_{p−1}); the resulting \sqrt{p} lower bound is all we know about the number of classes modulo p that the sequence 1!, 2!, …, (p − 1)! hits.

To summarize, we have

\sqrt{|G|} ≤ σ^{−}(G) ≤ σ^{+}(G) ≤ |G|  (2)

for all finite abelian groups G with |G| ≠ 2, and the main goal of this paper is to prove that on the other hand, σ^{−}(G) ≪ \sqrt{|G|} and σ^{+}(G) ≫ |G| hold.

Theorem 1. For any finite abelian group G we have σ^{+}(G) > |G|/2.

Theorem 2. For any finite abelian group G we have σ^{−}(G) < 8\sqrt{2|G|}.

The proofs of these two theorems, as well as that of Theorem 3 below, are presented in the next section; the proof of Theorem 1 is fairly straightforward and included mainly for the sake of completeness, the proof of Theorem 2 is more involving.

Notice that the conclusion one can draw concerning the sequence n!(mod p) is of negative sort: by Theorem 2, in order to improve the \sqrt{p} bound one has to exploit the special properties of this particular sequence.

How sharp Theorem 1 is? Suppose that G is a finite abelian group such that the sum of all elements of G is zero, and consider a permutation π = (a_{1}, …, a_{|G|}) ∈ Π_{G}. Let i ∈ [1, |G|] be so chosen that a_{i} = 0. If i = 1 then a_{1} = a_{1} +⋯+a_{|G|}, and if i ≥ 2 then a_{1} + ⋯ + a_{i−1} = a_{1} + ⋯ + a_{i}. In both cases we have |S(π)| ≤ |G| − 1 and we derive that the last inequality in (2) can be strengthened to

σ^{+}(G) ≤ \begin{cases}|G| − 1 & if the sum of all elements of G is zero, \\ |G| & if the sum of all elements of G is distinct from zero. \end{cases} (3)

It is quite possible that in fact, equality is attained in (3). We were able to prove this for the following particular groups.

Example 2. Let p be a prime and let r ≥ 1 be an integer with p^{r} > 2. Identifying the elementary abelian group C_{p}^{r} with the additive group of the finite field GF(p^{r}), fix a primitive element θ ∈ GF(p^{r}) and consider the permutation π = (0, 1, θ, θ^{2}, …, θ^{m−2}) ∈ Π_{C_{p}^{r}}, where m = p^{r}. As the sums 1 + θ + ⋯ + θ^{i} = (θ^{i+1} −1)/(θ−1) for i = 0, …, m−2 are pairwise distinct, we have |S(π)| = m−1 and therefore σ^{+}(C_{p}^{r}) = m − 1 in view of (3).

Example 3. Consider a cyclic group C_{m} the order of which is a power of two: m = 2^{k} (k ≥ 1). Fix a generating element g ∈ C_{m}. Then for all i = 0, …, m − 1 the sums 0 + g + ⋯ + ig = (i(i + 1)/2)g are easily seen to be pairwise distinct, hence the “identity permutation” π = (0, g, 2g, …, (m − 1)g) satisfies |S(π)| = m and therefore σ^{+}(C_{m}) = m.

Example 4. Consider the cyclic group C_{2p} where p is a prime such that two is a primitive root modulo p. Define the permutation (a_{0}, …, a_{p−2}) ∈ Π_{[1,p−1]} by a_{i} ≡ 2^{i} (mod p) (i = 0, …, p − 2) and, identifying C_{2p} with the quotient group ℤ/2pℤ, let

π = (0, a_{0}, a_{1}, a_{2}, …, a_{p−3}, −a_{p−2}, p, a_{p−2}, −a_{p−3}, …, −a_{2}, −a_{1}, −a_{0}) ∈ Π_{C_{2p}}.

A routine verification shows that then |S(π)| = 2p and therefore σ^{+}(C_{2p}) = 2p.

Theorems 1 and 2 do not address the following natural question: how large |S(π)| is for a “typical” permutation π ∈ Π_{G}? It is easily seen that if a_{1}, …, a_{|G|} ∈ G are chosen randomly and independently, then the expected number of the group elements missing among a_{1}, …, a_{|G|} is (e^{−1} + o(1))|G|. (See [CVZ, Theorem 2] for a somewhat more general result.) One can speculate that this is also about the number of group elements missing in (1); accordingly, if π ∈ Π_{G} is a randomly selected permutation, then E|S(π)| = (1 − e^{−1} + o(1))|G| as |G| → ∞. We believe that this heuristic yields the correct asymptotic value of E|S(π)|; this agrees with the numerical evidence suggesting (as indicated in [G94]) that the answer to the question at the beginning of this section is (1 − e^{−1} + o(1))p. What we were able to prove in this direction is

Theorem 3. If G is a finite abelian group and π ∈ Π_{G} is chosen randomly (so that every particular permutation is chosen with probability 1/|G|!), then

E|S(π)| > (c + o(1))|G|; c = 1/(1 + e) ≈ 0.2689

as |G| → ∞.

2. Proofs

Proof of Theorem 1. We set n = ⌊|G|/2⌋ + 1 and show that there exist pairwise distinct a_{1}, …, a_{n} ∈ G with the property that all sums s_{i} := a_{1}+⋯+a_{i} (i ∈ [1, n]) are pairwise distinct, too. If the sequence (a_{1}, …, a_{n}) is then completed in an arbitrary way to a permutation π ∈ Π_{G} then evidently |S(π)| ≥ n, implying the result.

We construct a_{1}, …, a_{n} one by one, starting with a_{1} = 0. Suppose that a_{1}, …, a_{j} with some j ∈ [1, n − 1] have been found. There are j values of a ∈ G satisfying

a_{1} + ⋯ + a_{j} + a = s_{i}  (4)

for some i ∈ [1, j], zero being one of them. Consequently, there are |G| − j ≥ j non-zero values of a for which none of (4) hold true. At least one of these values is distinct from all a_{1}, …, a_{j} and we set a_{j+1} equal to this value. □

We now turn to the estimates of σ^{−}(G). The following proposition is used to prove Theorem 2 and can also serve to illustrate our basic technique. In its proof and throughout the rest of the paper, we denote by B[U, V] the complete bipartite graph with partite sets U and V. The set of edges of a graph Γ will be denoted by E(Γ).

Proposition 1. Let G be the elementary abelian 2-group of rank r ≥ 1. Then

σ^{−}(G) ≤ 2^{⌈r/2⌉} + 2^{⌊r/2⌋} − 1.

Proof. The case r ≤ 2 is easy to verify. (For r = 1, see Example 1; for r = 2 notice that σ^{−}(G) ≤ σ^{+}(G) ≤ |G| − 1 = 3 by (3), as the elements of G add up to zero.) Assuming that r ≥ 3, fix two subgroups K, L ≤ G such that |K| = 2^{⌈r/2⌉}, |L| = 2^{⌊r/2⌋}, and G = K ⊕ L, and write Γ = B[K, L]. With each edge (k, l) ∈ E(Γ) we associate the sum k + l, so that all the elements of G are associated in a unique way with the edges of Γ. Since all vertices of Γ have even degree, Γ possesses an Eulerian circuit C. Let π := (a_{1}, …, a_{|G|}) ∈ Π_{G} be the permutation of G in which every a_{i} is the element associated with the ith edge of C, assuming the first edge to be incident to zero (either in K or in L). It is easily seen then that for any i ∈ [1, |G|], the sum a_{1} + ⋯ + a_{i} equals to the element of K ∪ L, incident to both the ith and (i + 1)th edges. Therefore

σ^{−}(G) ≤ |S(π)| = |K ∪ L| = |K| + |L| − 1,

as requested. □

To extend the approach used in the proof of Proposition 1 onto groups other than C_{2}^{r} we introduce the notion of a Sidon graph. We say that the graph Γ is a Sidon graph over the abelian group G if the vertex set of Γ is a subset of G, and for any pair of edges (u, v), (u′, v′) ∈ E(Γ) (more precisely, for any quadruple of vertices (u, v, u′, v′) such that u is adjacent with v and u′ is adjacent with v′) we have v − u = v′ − u′ if and only if u = u′ and v = v′.

Remark. Clearly, if Γ is a Sidon graph over G then for any edge (v, v′) ∈ E(Γ) the order of v′ − v in G is at least three. In particular, the graph constructed in the proof of Proposition 1 is not Sidon.

Given a graph Γ on a subset of an abelian group we let

D(Γ) := {v′ − v: (v′, v) ∈ E(Γ)}.

Clearly, Γ is Sidon if and only if |D(Γ)| = 2|E(Γ)|.

Lemma 1. Suppose that Γ = (V, E) is a Sidon graph over a finite abelian group G. Then there is a permutation π ∈ Π_{D(Γ)} such that |S(π)| ≤ |V |.

Proof. Consider the digraph \overline{Γ} obtained from Γ by replacing every its edge by the two corresponding directed edges. The out-degree of every vertex v ∈ V in \overline{Γ} equals its in-degree, hence \overline{Γ} possesses an Eulerian circuit C = (v_{0}, v_{1}, …, v_{s−1}, v_{s} = v_{0}) where s = 2|E| = |D(Γ)|. Observing that the differences v_{i} − v_{i−1} (1 ≤ i ≤ s) list all elements of D(Γ) so that every a ∈ D(Γ) is listed exactly once, let a_{i} := v_{i} − v_{i−1}. As a_{1} + ⋯ + a_{i} = v_{i} − v_{0} (i = 1, …, s), the permutation π := (a_{1}, …, a_{s}) ∈ Π_{D(Γ)} satisfies S(π) = V − v_{0}, hence |S(π)| ≤ |V |, as wanted. □

Proposition 2. Let K and L be subgroups of a finite abelian group G such that G = K ⊕ L. Then σ^{−}(G) < 2(|K| + |L|).

Proof. Let G_{0} := {g ∈ G: 2g = 0} be the subgroup of all those elements of G of order one or two and write K_{0} := K ∩ G_{0} and L_{0} := L ∩ G_{0}; thus G_{0} = K_{0} ⊕ L_{0}. Evidently, we can find subsets K_{1} ⊆ K and L_{1} ⊆ L such that K = K_{1} ∪ K_{0} ∪ (−K_{1}), L = L_{1} ∪ L_{0} ∪ (−L_{1}), and the two unions are disjoint. Consider the (incomplete bipartite) graph Γ on the vertex set K ∪ L_{1} ∪ L_{0} in which every vertex of K is adjacent with every vertex of L_{1} and in addition, every vertex of K_{1} is adjacent with every vertex of L_{0}. It is easily verified that D(Γ) = G \ G_{0} whence

|D(Γ)| = |K||L| − |K_{0}||L_{0}| = 2|K||L_{1}| + 2|K_{1}||L_{0}| = 2|E(Γ)|

and therefore Γ is a Sidon graph over G. The group G_{0} is an elementary abelian two-group; denote its rank by r. By Lemma 1 there exists π_{1} ∈ Π_{G\G_{0}} with |S(π_{1})| ≤ |K| + |L_{1}| + |L_{0}|, and by Proposition 1 there exists π_{2} ∈ Π_{G_{0}} with

|S(π_{2})| ≤ 2^{⌈r/2⌉} + 2^{⌊r/2⌋} − 1 < |K_{0}| + |L_{0}|.

Concatenating π_{1} and π_{2} we obtain π ∈ Π_{G} such that

|S(π)| < (|K| + |L_{1}| + |L_{0}|) + (|K_{0}| + |L_{0}|) ≤ 2(|K| + |L|).
□

Remark. The proof of Proposition 2 can be easily modified to show that if K is an arbitrary subgroup of G, then σ^{−}(G) < 2(|K| + |G|/|K|).

Corollary 1. If G is homocyclic of even rank, then σ^{−}(G) < 4\sqrt{|G|}.

Lemma 2. Let G be a non-trivial finite abelian group. Then there exist subgroups K, L, M ≤ G such that K is cyclic, G = K ⊕ L ⊕ M, and

|K| ≥ \frac{|M|}{|L|} ≥ 1.  (5)

Moreover, if G is not homocyclic of even rank then (5) can be replaced with

|K| ≥ 2 \frac{|M|}{|L|} ≥ 2.  (6)

Proof. Suppose that G = H_{1}⊕⋯⊕H_{r}, where r is the rank of G and H_{1}, …, H_{r} ≤ G are non-zero cyclic subgroups of orders m_{1}, …, m_{r}, respectively, such that m_{i}|m_{i+1} for i = 1, …, r − 1. We assume that r ≥ 3 for otherwise the assertion is immediate. Let

f := \frac{m_{r}m_{r−2}m_{r−4} …}{m_{r−1}m_{r−3}m_{r−5} …}

and notice that f is an integer and moreover, f ≥ 2 unless r is even and m_{1} = ⋯ = m_{r}. Consequently, from m_{r} = f · (m_{r−1}m_{r−3} …)/(m_{r−2}m_{r−4} …) it follows that one can choose K = H_{r}, L = H_{r−2} ⊕ H_{r−4} ⊕ ⋯, and M = H_{r−1} ⊕ H_{r−3} ⊕ · · ·. □

We are now ready to prove our main result.

Proof of Theorem 2. If G is homocyclic of even rank the assertion follows from Corollary 1. Assuming that G is not homocyclic of even rank, we find K, L, M ≤ G as in Lemma 2. If |K| = 2 then |M| = |L| by (6) and applying Proposition 2 we get

σ^{−}(G) < 2(|K||L| + |M|) = 2(|K| + 1)|L| = 3\sqrt{2|G|};

accordingly, for the rest of the proof we assume that |K| ≥ 3.

Set

s := ⌊\sqrt{\frac{|K||L|}{2|M|}}⌋ and t := ⌈\frac{|K|}{2s}⌉ − 1

so that s ≥ 1 (as it follows from (6)), s ≤ ⌊\sqrt{|K|/2}⌋ < |K|/2, and therefore t ≥ 1.

Let n := ⌊(|K| − 1)/2⌋ (so that n ≥ st), fix an element k generating K, and if |K| is even denote by g the unique element of K of order two. Define

U := {0, k, …, (t − 1)k} + L, V := {tk, 2tk, …, stk} + M,
W := {(st + 1)k, (st + 2)k, …, nk} + L

and consider the graphs Γ_{1} := B[U, V] and Γ_{2} := B[W, M]. (If n = st then Γ_{2} is empty.) It is easily verified that

D(Γ_{1}) = {−stk, …, −2k, −k, k, 2k, …, stk} + L + M

and

D(Γ_{2}) = {−nk, −(n − 1)k, …, −(st + 1)k, (st + 1)k, …, (n − 1)k, nk} + L + M

whence |D(Γ_{i})| = 2|E(Γ_{i})| (i = 1, 2) and therefore both Γ_{1} and Γ_{2} are Sidon graphs. Moreover, D(Γ_{1}) and D(Γ_{2}) are disjoint, and the complement of their union in G is the set L + M if |K| is odd and (L + M) ∪ (g + L + M) if |K| is even.

By Lemma 1, we can find π_{1} ∈ Π_{D(Γ_{1})} and π_{2} ∈ Π_{D(Γ_{2})} such that

|S(π_{1})| ≤ t|L| + s|M|, |S(π_{2})| ≤ (n − st)|L| + |M|.

By Proposition 2, we can find π_{3} ∈ Π_{L+M} such that |S(π_{3})| < 2(|L| + |M|). If |K| is even then adding g to all elements of π_{3} we obtain π_{4} ∈ Π_{g+M+L} such that S(π_{4}) ⊆ S(π_{3}) ∪ (g + S(π_{3})) and consequently, |S(π_{4})| ≤ 2|S(π_{3})| < 4(|L| + |M|). Concatenating π_{1}, π_{2}, π_{3}, and for |K| even π_{4}, we obtain π ∈ Π_{G} satisfying

|S(π)| < t|L| + s|M| + (n − st)|L| + |M| + 6(|L| + |M|).  (7)

Now taking into account that

t|L| ≤ \frac{|K||L|}{2s} < \frac{|K||L|}{\sqrt{|K||L|/2|M|}} = \sqrt{2|G|},
s|M| ≤ \sqrt{|G|/2},
st > \frac{|K|}{2} − s ≥ n + \frac{1}{2} − s,

and

|G| = |K||L||M| ≥ 2|M|^{2},

we obtain from (7)

|S(π)| < \sqrt{2|G|} + \sqrt{|G|/2} + (s − 1)|L| + |M| + 6(|L| + |M|)

≤ \frac{3}{2} \sqrt{2|G|} + (s + 12)|M|

≤ 2\sqrt{2|G|} + 12\sqrt{|G|/2}

= 8\sqrt{2|G|}.

This completes the proof. □

Proof of Theorem 3. Write m := |G| and fix an integer k = αm ∈ [1, m]. With any permutation π = (a_{1}, …, a_{m}) ∈ Π_{G} satisfying |S(π)| ≤ k we associate (in an arbitrary, but unique way) a k-element subset S_{π} ⊆ G such that S(π) ⊆ S_{π}. As a_{1} ∈ S_{π} and a_{i} ∈ S_{π} − (a_{1} + ⋯ + a_{i−1}) for i = 2, …, m − k, with any given k-element subset S ⊆ G we have associated at most k^{m−k}k! permutations. It follows that the total number of permutations π ∈ Π_{G} satisfying |S(π)| ≤ k is at most

\binom{m}{k}k^{m−k}k! = \frac{k^{m−k}m!}{(m − k)!},

hence

Pr (|S(π)| ≤ k) ≤ k^{m−k}/(m − k)!

< \frac{1}{\sqrt{2π(m − k)}} (\frac{ke}{m − k} )^{m−k} = \frac{1}{\sqrt{2π(1 − α)m}} (\frac{αe}{1 − α})^{(1−α)m}.

Now choose k := ⌊m/(1 + e)⌋. Then α < 1/(1 + e) whence Pr (|S(π)| ≤ k) = o(1) and from the Markov inequality we derive that

E|S(π)| ≥ (k + 1) Pr (|S(π)| ≥ k + 1)

= (k + 1)(1 − Pr (|S(π)| ≤ k)) > \frac{m}{1 + e} (1 + o(1)),

as claimed. □

Acknowledgement

We would like to thank Michael Muzychuk who has brought to our attention the issue of Eulerian circuits, and Igor Shparlinski from whom we have learned about the problem studied in this paper.

References

[GLS] M. Z. Garaev, F. Luca, and I. E. Shparlinski, Character sums and songruences with n!, submitted.

[CVZ] C. Cobeli, M Vájáitu, and A. Zaharescu, The sequence n!(mod p), preprint.

[G94] R. K. Guy, Unsolved problems in numbere theory, Springer-Verlag, New York, 1994.

Department of Mathematics, University of Haifa at Oranim, Tivon 36006, Israel.

  E-mail address: seva@math.haifa.ac.il