SUMS AND DIFFERENCES ALONG HAMILTONIAN CYCLES

VSEVOLOD F. LEV

Dedicated to Jarik Nesetril on the occasion of his 60th birthday

Abstract. Given a finite abelian group G, consider the complete graph on the set of all elements of G. Find a Hamiltonian cycle in this graph and for each pair of consecutive vertices along the cycle compute their sum. What are the smallest and the largest possible number of distinct sums that can emerge in this way? What is the expected number of distinct sums if the cycle is chosen randomly? How do the answers change if an orientation is given to the cycle and differences (instead of sums) are computed? We give complete solutions to some of these problems and establish reasonably sharp estimates for the rest.

1. Introduction

For a finite abelian group G, by C(G) we denote the set of all Hamiltonian cycles in the complete digraph on the vertex set G; thus, C(G) is empty if G is trivial and |C(G)| = (|G| − 1)! otherwise. Given a cycle C ∈ C(G), label each edge (g_{1}, g_{2}) ∈ C with the sum g_{1} + g_{2} and consider the set S(C) ⊆ G of all labels along C. Now let

σ_{max}(G) := max{|S(C)|: C ∈ C(G)},
σ_{min}(G) := min{|S(C)|: C ∈ C(G)},

and assuming that C ∈ C(G) is chosen randomly,

σ_{rnd}(G) := E (|S(C)|).

Similarly, labeling each (directed) edge (g_{1}, g_{2}) ∈ C with the difference g_{2}−g_{1}, consider the set D(C) ⊆ G of all labels along C, and let

δ_{max}(G) := max{|D(C)|: C ∈ C(G)},
δ_{min}(G) := min{|D(C)|: C ∈ C(G)},

Key words and phrases. Addition Cayley graph; rainbow-sum; rainbow-difference; directed terrace; sequenceable group; harmonious group.

and (choosing C ∈ C(G) at random),

δ_{rnd}(G) := E (|D(C)|).

In this paper we find the exact values or establish tight bounds for these six quantities, for all finite abelian groups G.

We assume that min ∅ = max ∅ = 0 in the definitions above; thus, if G is trivial, then σ_{max}(G) = σ_{min}(G) = δ_{max}(G) = δ_{min}(G) = 0, while σ_{rnd}(G) and δ_{rnd}(G) are undefined. Also, if |G| = 2, then σ_{max}(G) = σ_{min}(G) = δ_{max}(G) = δ_{min}(G) = σ_{rnd}(G) = δ_{rnd}(G) = 1.

Occasionally, we will consider Hamiltonian cycles on subsets of finite abelian groups, as well as Hamiltonian paths on finite abelian groups or their subsets. The definitions of S(C) and D(C) are carried without any modification onto the case where C is a Hamiltonian cycle or path on a finite subset of an additively written group.

In connection with the quantities σ_{max}(G) and δ_{max}(G) we will be interested in Hamiltonian cycles and paths such that all sums (differences) of two consecutive elements along the cycle or path are pairwise distinct; that is, |S(C)| = |A| (respectively, |D(C)| = |A|) for a cycle and |S(C)| = |A| − 1 (respectively, |D(C)| = |A| − 1) for a path on the set A. We call such cycles and paths rainbow-sum (respectively, rainbow-difference) and use abbreviations like “RS-cycle” or “RD-path”. Under various names such cycles and paths have been studied by a number of authors; for details and references see the next section and also comments at the end of Sections 4 and 7.

Both cycles and paths on the set A will be written as C = (a_{1}, …, a_{|A|}), where the components of C list the elements of A; clearly, each Hamiltonian path on A has a unique representation of this sort, and each cycle has |A| representations.

We close this section with the list of notation, used below in this paper and not introduced yet:

⟨g⟩ − the subgroup, generated by the group element g;
Σ(G) − the sum of the elements of the finite abelian group G;
rk(G) − the rank of the finite abelian group G;
ℤ/mℤ − the group of residues modulo the positive integer m;
Cay_{G}^{+}(S) − the addition Cayley graph, induced on the finite abelian group G

by its subset S (see the next section for the definition).

SUMS AND DIFFERENCES ALONG HAMILTONIAN CYCLES 3

2. Summary of results

We now briefly discuss our principal results; proofs (mostly of combinatorial nature), comments, and more results are postponed until Sections 3–8.

The smallest possible number of differences along a Hamiltonian cycle can be determined precisely.

Theorem 1. For any finite abelian group G we have δ_{min}(G) = rk(G).

The situation with the largest possible number of differences is subtler and for some groups there is still room for improvement.

Recall, that an involution of a group is an element of order 2. It is well-known and easy to verify that for a finite abelian group G the following conditions are equivalent:

(i) G has exactly one involution; (ii) G has exactly one invariant factor of even order; (iii) the sum of all elements of G is distinct from 0.

Theorem 2. Let G be a finite non-trivial abelian group. If G has exactly one involution, then δ_{max}(G) = |G|−1. If G has no involutions or at least two involutions, then δ_{max}(G) ≤ |G| − 2; indeed, equality holds with the possible exception of those groups G, whose Sylow 2-subgroup is non-cyclic of order 8.

The proof of Theorem 2 uses results of Gordon [1] and Headley [2] asserting that (i) if G is a one-involution group, then G possesses an RD-path; (ii) if G is not a one-involution group and the Sylow 2-subgroup of G is not of order 8, then the set of non-zero elements of G possesses an RD-cycle. (These results are based on earlier work of Friedlander, Gordon, and Miller [3]). The question of whether the requirement that G is not one-involution, without any extra assumptions, ensures the existence of an RD-cycle on the set of non-zero elements of G, to our knowledge is open. Answering it in the affirmative would show that in the estimate of Theorem 2, equality is actually attained for all finite non-trivial abelian groups G.

In connection with Theorem 2, Ollis [4] has recently shown that δ_{max}(G) = |G| − 2 holds true also if the Sylow 2-subgroup of G is isomorphic to (ℤ/2ℤ)⊕(ℤ/4ℤ), whereas if the Sylow 2-subgroup of G is isomorphic to (ℤ/2ℤ)^{3}, then δ_{max}(G) ≥ |G| − 4.

Theorem 3. For any finite non-trivial abelian group G we have

δ_{rnd}(G) = (1 − e^{−1})|G| + O(1),

with an absolute implicit constant.

4 VSEVOLOD F. LEV

Observe that the expression (1 − e^{−1})|G| + O(1) is not at all surprising in this context, giving the expected number of pairwise distinct elements of G, appearing in the sequence of |G| randomly and independently chosen elements.

For a subset S of a finite abelian group G, consider the graph with the vertex set G and the edge set {(g′, g′′) ∈ G × G: g′ + g′′ ∈ S}. We denote this graph by Cay_{G}^{+}(S) and call it the addition Cayley graph, induced on G by S. Addition Cayley graphs received very little attention in the literature; we mention the papers [13], where the clique number of the random addition Cayley graph is studied, and [5], where hamiltonicity of addition Cayley graphs is investigated in the special case that S does not contain elements of the form 2g with g ∈ G. The latter paper is particularly relevant in our context: in a somewhat unexpected way, it turns out that the quantity σ_{min}(G) is tightly related to hamiltonicity of the graphs Cay_{G}^{+}(S). Specifically, if C ∈ C(G), then C is a Hamiltonian cycle in Cay_{G}^{+}(S(C)); conversely, if S ⊆ G and C is a Hamiltonian cycle in Cay_{G}^{+}(S), then S(C) ⊆ S. (We identify graphs with the digraphs, obtained by replacing each undirected edge with the pair of corresponding directed edges. Thus, for instance, if |G| = 2 and S contains the nonzero element of G, then Cay_{G}^{+}(S) is considered Hamiltonian.) It follows that σ_{min}(G) is the minimum size of a subset S ⊆ G such that Cay_{G}^{+}(S) is Hamiltonian. We remark that hamiltonicity of “conventional” Cayley graphs was intensively studied and in particular, it is well-known that any connected Cayley graph on a finite abelian group with at least three elements is Hamiltonian; see [6]. However, apart from the results of [5], nothing seems to be known on hamiltonicity of addition Cayley graphs. We establish some properties of the graphs Cay_{G}^{+}(S) in Section 6 and as a corollary determine the value of σ_{min}(G) precisely if G is of even order, and obtain reasonable estimates if G is of odd order.

Theorem 4. Let G be a finite non-trivial abelian group. If |G| is even and G is of type (m_{1}, …, m_{rk(G)}), then

σ_{min}(G) = \begin{cases}rk(G) & if m_{1} = 2, \\ rk(G) + 1 & if m_{1} > 2. \end{cases}

If |G| is odd, then

rk(G) + 1 ≤ σ_{min}(G) ≤ 2 rk(G) + 1.

Theorem 4 shows that σ_{min}(G) = 2 if G is cyclic of even order |G| ≥ 4, and σ_{min}(G) ∈ {2, 3} if G is cyclic of odd order. Indeed, we were able to find σ_{min}(G) for cyclic groups G of odd order, too.

Theorem 5. If G is cyclic of order |G| ≥ 3, then

σ_{min}(G) = \begin{cases}2 & if |G| is even, \\ 3 & if |G| is odd. \end{cases}

Computations seem to suggest that if rk(G) = 2 and |G| ≠ 9 is odd, then σ_{min}(G) = 3. One can speculate that, indeed, σ_{min}(G) = rk(G)+1 for all non-cyclic finite abelian groups G of odd order, with a “small” number of exceptions.

Our next theorem establishes the largest possible number of sums along a Hamiltonian cycle.

Theorem 6. For any finite non-trivial abelian group G we have

σ_{max}(G) = \begin{cases}|G| & if G is neither a one-involution group, \\ & nor an elementary abelian 2-group; \\ |G| − 1 & if G is a one-involution group; \\ |G| − 2 & if G is an elementary abelian \\ & 2-group and |G| > 2. \end{cases}

The proof of Theorem 6 is based on (i) a theorem due to Beals, Gallian, Headley, and Jungreis (see [7]) claiming that if G is a finite abelian group which is neither a one-involution group, nor an elementary 2-group, then G possesses an RS-cycle; (ii) an original construction of an RS-path on every finite abelian one-involution group G.

It is worth mentioning that Theorem 6 bears relation with Latin transversals in Cayley tables, as we now explain; cf. [14]. Let G be a finite abelian group. Does the Cayley table of G have a Latin transversal? In other words, do there exist two permutations (g′_{1}, …, g′_{|G|}) and (g′′_{1}, …, g′′_{|G|}) of the elements of G such that (g′_{1} + g′′_{1}, …, g′_{|G|} +g′′_{|G|}) is also a permutation? It is easily seen that if the answer is positive, then the elements of G add up to 0, whence G is not one-involution; on the other hand, it was shown in [8] (see also [9] where this was independently rediscovered) that this condition is also sufficient. Notice the connection with Snevily’s conjecture [10], which is that any square sub-table of the Cayley table of a finite abelian group of odd order possesses a Latin transversal. Clearly, G has an RS-cycle if and only if its Cayley table has a Latin transversal of some special sort; namely, one with g′′_{1} = g′_{2}, g′′_{2} = g′_{3} , …, g′′_{n} = g′_{1}.

Theorem 7. For any finite non-trivial abelian group G we have

σ_{rnd}(G) = (1 − e^{−1})|G| + O(1),

with an absolute implicit constant.

We recommend the reader to compare Theorems 3 and 7.

3. The minimum number of differences: δ_{min}(G)

Proof of Theorem 1. The case where G is trivial is immediate and we assume for the rest of the proof that |G| ≥ 2.

Let n := |G| and suppose that C = (g_{1}, …, g_{n}) ∈ C(G) is a Hamiltonian cycle on G, written in such a way that g_{1} = 0. In view of g_{i+1} − g_{i} ∈ D(C) (i = 1, …, n − 1), every element of G can be represented as a sum of elements of D(C); thus D(C) generates G and consequently |D(C)| ≥ rk(G). It follows that δ_{min}(G) ≥ rk(G).

To show that δ_{min}(G) ≤ rk(G) we use induction on rk(G). If rk(G) = 1 then G is cyclic and, identifying it with the group ℤ/nℤ, we consider the Hamiltonian cycle C := (0, 1, 2, …, n − 1); clearly, D(C) = {1}, which settles the case rk(G) = 1. To complete the proof we show that for any Hamiltonian cycle C = (h_{1}, …, h_{n}) on the n-element abelian group H and any integer m ≥ 2, there is a Hamiltonian cycle C′ on the group H ⊕ (ℤ/mℤ) with |D(C′)| ≤ |D(C)| + 1. Indeed, it is immediately verified that one can choose

C′ := (h_{1}, h_{2}, …, h_{n},

h_{n} + 1, h_{1} + 1, …, h_{n−1} + 1, h_{n−1} + 2, h_{n} + 2, …, h_{n−2} + 2,

⋮
h_{2} + (m − 1), h_{3} + (m − 1), …, h_{1} + (m − 1)).
□

4. The maximum number of differences: δ_{max}(G)

Proof of Theorem 2. Recall, that by Σ(G) we denote the sum of all elements of G. Let C = (g_{1}, …, g_{|G|}) ∈ C(G). Since 0 ∉ D(C), we have |D(C)| ≤ |G| − 1. Moreover, if all non-zero elements of G are represented in D(C), then exactly one of them, say g, is represented twice and therefore

0 = (g_{2} − g_{1}) + ⋯ + (g_{|G|} − g_{|G|−1}) + (g_{1} − g_{|G|}) = Σ(G) + g;

consequently, in this case Σ(G) = −g ≠ 0, meaning that G is one-involution. The upper bound

δ_{max}(G) ≤ \begin{cases}|G| − 1 & if G is a one-involution group; \\ |G| − 2 & if G is not a one-involution group \end{cases}

follows.

Next, notice that if G is not isomorphic to the direct sum of a group of odd order and a non-cyclic group of order 8, then either G is one-involution, or the Sylow 2subgroup of G is not of order 8. If G is one-involution then, as shown in [1], the group G possesses an RD-path; closing this path (by joining its first and last elements), we get a Hamiltonian cycle C ∈ C(G) with |D(C)| ≥ |G| − 1. If G is not one-involution then G does not have an RD-path: otherwise, arguing as above we would obtain δ_{max}(G) ≥ |G| − 1 which, as we saw, is wrong. It is shown in [2], however, that if G is not one-involution and the Sylow 2-subgroup of G is not of order 8, then the set of non-zero elements of G possesses an RD-cycle. Choosing arbitrarily two adjacent elements of this cycle and inserting 0 between them, we obtain a Hamiltonian cycle C ∈ C(G) with |D(C)| ≥ |G| − 2. □

For a survey of results, related to the existence of RD-cycles and RD-paths in finite abelian groups, see [11] or [12]. We notice that the standard terminology used in [1, 2, 3, 11, 12, 14] and a number of other papers is distinct from that we use here. Specifically, RD-paths are called directed terraces, and those groups possessing an RD-path are called sequenceable; furthermore, RD-cycles on the set of non-zero group elements are called directed R-terraces, and those groups for which such an RD-cycle exists are called R-sequenceable.

5. The expected number of differences: δ_{rnd}(G)

Proof of Theorem 3. Let n := |G|; clearly, n ≥ 3 can be assumed without loss of generality. Representing D(C) as a sum of indicator random variables, corresponding to the non-zero elements of G, write

δ_{rnd}(G) = ∑_{g∈G\\{0\}} Pr \{g ∈ D(C)\} = \frac{1}{(n − 1)!} ∑_{g∈G\\{0\}} |\{C ∈ C(G): g ∈ D(C)\}|. (1)

Assuming that g ∈ G \ {0} is fixed, for each A ⊆ G let C_{A}(G) denote the set of all those cycles C ∈ C(G) such that every element a ∈ A is followed along C by the element a + g. Observe, that if A contains a coset of the subgroup ⟨g⟩, generated by g, then C_{A}(G) is empty, unless A = ⟨g⟩ = G (in which case C_{A}(G) consists of one single cycle, induced by g on G).

Claim 1. If A does not contain a coset of ⟨g⟩, then |C_{A}(G)| = (n − |A| − 1)!.

Proof. For each c ∈ G \ A find the non-negative integer k (depending on c) so that c − (k + 1)g ∉ A and c − kg, …, c − g ∈ A. Consider all chains of the form (c − kg, …, c−g, c), for all c ∈ G\A. These chains partition G, and for C ∈ C(G) we have C ∈ C_{A}(G) if and only if C is composed of these chains, following each other in some order. The claim follows now since the number of chains is |G \ A| = n − |A|. □

Using Claim 1 and the inclusion-exclusion principle, we get

|{C ∈ C(G): g ∈ D(C)}| = | ⋃_{∅≠A⊆G}C_{A}(G)|

= ∑_{∅≠A⊆G}(−1)^{|A|+1}|C_{A}(G)|

= ∑_{j=1}^{n−1}(−1)^{j+1}(n − j − 1)! N_{j} + (−1)^{n+1}τ,  (2)

where N_{j} is the number of those A ⊆ G with |A| = j such that A contains no coset of ⟨g⟩, and τ is equal to 1 if ⟨g⟩ = G and equal to 0 otherwise.

We now claim that if d is the order of g in G (so that d | n and d ≥ 2), then

N_{j} = ∑_{0≤i≤j/d}(−1)^{i}\binom{n/d}{i}\binom{n − id}{j − id}  (3)

holds for each j ∈ [1, n − 1]. Indeed, represent G as a union of n/d cosets of ⟨g⟩. There are \binom{n/d}{i} ways to choose i cosets, and for any choice of i ≤ j/d cosets there are \binom{n−id}{j−id} ways to choose j − id elements from the remaining cosets; our claim follows now by the inclusion-exclusion principle.

Substituting (2) and (3) into (1), and for d | n letting K_{d} be the number of elements g ∈ G of order d, we get

δ_{rnd}(G) = \frac{1}{(n − 1)!} ∑_{d|n, d≥2} K_{d}

× ( ∑_{j=1}^{n−1}(−1)^{j+1}(n − j − 1)! ∑_{0≤i≤j/d}(−1)^{i}\binom{n/d}{i}\binom{n − id}{j − id}) + O(1)

= \frac{1}{(n − 1)!} ∑_{d|n, d≥2} K_{d}

× ( ∑_{0≤i≤(n−1)/d}(−1)^{i}\binom{n/d}{i}(n − id)! ∑_{j=max\{1,id\}}^{n−1} \frac{(−1)^{j+1}}{(j − id)!(n − j)}) + O(1)

= M + R + O(1),

where M is the part of the expression, obtained for i = 0, and R is the remaining part (corresponding to positive values of i). The former is not difficult to compute:

M = n ∑_{d|n, d≥2} K_{d} ∑_{j=1}^{n−1} \frac{(−1)^{j+1}}{j! (n − j)}

= n ∑_{d|n, d≥2} K_{d} ∑_{j=1}^{n−1} \frac{(−1)^{j+1}}{j!} (\frac{1}{n} + O(\frac{j^{2}}{n^{2}} ))

= ∑_{d|n, d≥2} K_{d}(1 − e^{−1} + O(\frac{1}{n}))

= (1 − e^{−1})n + O(1).

To complete the proof it remains to estimate the remainder term R. Clearly, we have

|R| ≤ \frac{1}{(n − 1)!} ∑_{d|n, d≥2} K_{d} ∑_{1≤i<n/d} \binom{n/d}{i}(n − id)! ∑_{j=id}^{n−1} \frac{1}{(j − id)! (n − j)}.

Consider the internal sum. If id ≤ j ≤ min{id + 2, n − 1} then

\frac{1}{(j − id)! (n − j)} ≤ \frac{1}{n − j} ≤ \frac{3}{n − id},

while for id + 3 ≤ j + 1 ≤ n − 1 we have

\frac{(j − id)! (n − j)}{(j + 1 − id)! (n − j − 1)} = \frac{n − j}{(j + 1 − id)(n − j − 1)} ≤ \frac{1}{3} \frac{n − j}{n − j − 1} ≤ \frac{2}{3},

10 VSEVOLOD F. LEV

and hence

∑_{j=id}^{n−1} \frac{1}{(j − id)! (n − j)} = O(\frac{1}{n − id}).

Thus

|R| ≤ \frac{1}{(n − 1)!} ∑_{d|n, d≥2} K_{d} ∑_{1≤i<n/d} \binom{n/d}{i}(n − id − 1)!

and to estimate the sum over i we observe that the summand corresponding to i = 1 is \frac{n}{d}(n − d − 1)!, while for 2 ≤ i + 1 < n/d we have

\frac{\binom{n/d}{i+1}(n − (i + 1)d − 1)!}{\binom{n/d}{i}(n − id − 1)!} = \frac{n/d − i}{i + 1} · \frac{1}{(n − (i + 1)d) ⋯ (n − id − 1)}

≤ \frac{1}{(i + 1)d} · \frac{n − id}{n − id − 1} ≤ \frac{2}{(i + 1)d} ≤ \frac{1}{2}.

It follows that

∑_{1≤i<n/d} \binom{n/d}{i}(n − id − 1)! ≤ \frac{2n}{d} (n − d − 1)! ≤ n(n − 3)!

and therefore

|R| ≤ \frac{n(n − 3)!}{(n − 1)!} ∑_{d|n, d≥2} K_{d} = O(1),

completing the proof. □

6. The minimum number of sums: σ_{min}(G)

In this section we establish some general results on hamiltonicity of addition Cayley graphs and as a corollary, derive Theorems 4 and 5. It is worth reminding that we identify undirected graphs with the corresponding digraphs so that, for instance, the complete graph on two vertices is considered Hamiltonian.

The trivial necessary condition for hamiltonicity is connectedness.

Proposition 1. Let S be a subset of the finite abelian group G. In order for Cay_{G}^{+}(S) to be connected it is necessary and sufficient that S is not contained in a coset of a proper subgroup of G, except, perhaps, for the non-zero coset of a subgroup of index 2.

Proof. The cases where G is trivial and where S is empty are easy to check. Assuming that G is non-trivial and S is non-empty, let H be the smallest subgroup such that S is contained in a coset of H; in other words H is the subgroup, generated by the set of

SUMS AND DIFFERENCES ALONG HAMILTONIAN CYCLES 11

all differences s′ − s′′ (with s′, s′′ ∈ S). Observe, that the component of 0 in Cay_{G}^{+}(S) consists of all those elements of G, representable as s_{1} − s_{2} + s_{3} − ⋯ + (−1)^{k+1}s_{k} with k ≥ 0 and s_{1}, …, s_{k} ∈ S; that is, this component is the set H ∪ (S + H). Thus Cay_{G}^{+}(S) is connected if and only if either H = G, or H is a subgroup of index 2 and S ⊆ G \ H. □

We remark that for the special case where S does not contain group elements of the form 2g (g ∈ G), the assertion of Proposition 1 is equivalent to [5, Proposition 2.3].

In contrast with the “conventional” case, connectedness is not sufficient for hamiltonicity of an addition Cayley graph. Say, if S = {s_{1}, s_{2}} ⊆ ℤ/nℤ, where n ≥ 3 is an integer and s_{1} − s_{2} generates ℤ/nℤ, then the corresponding graph is connected, but not Hamiltonian. This follows from the fact that there are elements g ∈ G with either 2g = s_{1}, or 2g = s_{2}, and these elements have just one neighbor in the graph. Moreover, it can be shown that if n ≡ 3 (mod 4), G = ℤ/nℤ, and S = {0, 1, 3} ⊆ G, then Cay_{G}^{+}(S) is 2-connected, but not Hamiltonian.

Corollary 1. Let S be a subset of the finite abelian group G such that Cay_{G}^{+}(S) is Hamiltonian. Then |S| ≥ rk(G) and moreover, if G is of type (m_{1}, …, m_{rk(G)}) with m_{1} > 2, then indeed |S| ≥ rk(G) + 1.

Proof. Since Cay_{G}^{+}(S) is Hamiltonian, it is connected, hence S is not contained in a proper subgroup of G by Proposition 1. It follows that S generates G and therefore |S| ≥ rk(G).

Assume now that |S| = rk(G). Fix arbitrarily an element s ∈ S and let H denote the subgroup of G, generated by S −s. Since 0 ∈ S −s, we have rk(H) ≤ |S −s|−1 = rk(G)−1, whence H is a proper subgroup. By Proposition 1 and in view of S ⊆ s+H, the index of H in G is 2, so that H contains the subgroup 2G := {2g: g ∈ G}. If m_{1} > 2, then we have rk(2G) = rk(G), and by the above

|S| ≥ rk(H) + 1 ≥ rk(2G) + 1 = rk(G) + 1,

a contradiction. □

For groups of even order the estimate of Corollary 1 is sharp.

Lemma 1. Let G be a finite abelian group of type (m_{1}, …, m_{rk(G)}). If |G| is even, then there is a subset S ⊆ G with

|S| = \begin{cases}rk(G) & if m_{1} = 2, \\ rk(G) + 1 & if m_{1} > 2 \end{cases}

such that Cay_{G}^{+}(S) is Hamiltonian.

Proof. Let H < G be an index 2 subgroup with rk(H) = rk(G) − 1 if m_{1} = 2, and rk(H) = rk(G) if m_{1} > 2. Fix an element s ∈ G \ H. By Theorem 1, there is a Hamiltonian cycle C = (h_{1}, …, h_{|H|}) ∈ C(H) such that |D(C)| = rk(H). Now C′ := (h_{1}, s−h_{1}, h_{2}, s−h_{2}, , …, h_{|H|}, s−h_{|H|}) is a Hamiltonian cycle on G satisfying |S(C′)| = |D(C)| + 1 and the assertion follows. □

Lemma 2. Let S be a finite non-trivial abelian group of odd order. Then there is a subset S ⊆ G of size |S| ≤ 2 rk(G) + 1 such that Cay_{G}^{+}(S) is Hamiltonian.

Proof. We write r := rk(G) and use induction on r. If r = 1 then G is cyclic and, identifying it with the group ℤ/(2n + 1)ℤ with a positive integer n, we consider the Hamiltonian cycle

C := (0, 1, 2n, 2, 2n − 1 , …, n, n + 1) ∈ C(G).

One verifies immediately that |S(C)| = 3, proving the lemma for r = 1.

Assuming now that r ≥ 2, write G = H ⊕ F where H and F are subgroups of G such that rk(H) = r − 1 and F is cyclic. Write |H| = m and |F | = 2n + 1 (so that m ≥ 3 and n ≥ 1 are integers) and find, using the induction hypothesis, a Hamiltonian cycle C_{H} = (h_{1}, …, h_{m}) ∈ C(H) such that |S(C_{H})| ≤ 2r−1. Identifying F with the group ℤ/(2n + 1)ℤ, consider the following n + 1 paths in the complete graph on the vertex set G:

(h_{1}, …, h_{m}),
(h_{1} + 1, h_{2} + 2n, …, h_{m} + 1, h_{1} + 2n, h_{2} + 1, …, h_{m} + 2n),
⋮
(h_{1} + n, h_{2} + (n + 1), …, h_{m} + n,
h_{1} + (n + 1), h_{2} + n, …, h_{m} + (n + 1)).

Straightforward verification shows that the (cyclic) concatenation of these paths yields a Hamiltonian cycle C ∈ C(G) with S(C) = S(C_{H}) ∪ {h_{m} + h_{1} + 1, h_{m} + h_{1} + (n + 1)}. Thus |S(C)| = |S(C_{H})| + 2 ≤ 2r + 1 and the assertion follows. □

Theorem 4 is immediate from Corollary 1, Lemmas 1 and 2, and the remark, preceding the statement of Theorem 4 in Section 2. To prove Theorem 5 we classify those subsets S of the finite abelian group G with |S| ≤ 2 such that Cay_{G}^{+}(S) is Hamiltonian.

SUMS AND DIFFERENCES ALONG HAMILTONIAN CYCLES 13

Lemma 3. Let G be a finite abelian group with |G| ≥ 3.

(i) If |S| = 1 then Cay_{G}^{+}(S) is not Hamiltonian; (ii) If |S| = 2 then Cay_{G}^{+}(S) is Hamiltonian if and only if the difference of the

two elements of S generates an index 2 subgroup of G, and this subgroup is disjoint with S.

Proof. The first assertion is immediate; to prove the second assertion assume that |S| = 2 and write n := |G| and S := {s_{1}, s_{2}}. If n is odd, then there is an element g ∈ G with 2g = s_{1}; the vertex of Cay_{G}^{+}(S), corresponding to g, has then just one neighbor, whence Cay_{G}^{+}(S) is not Hamiltonian. Suppose that n is even. In this case for Cay_{G}^{+}(S) to be Hamiltonian it is necessary and sufficient that in the n-element sequence

(0, s_{1}, s_{2} − s_{1}, s_{1} − (s_{2} − s_{1}), 2(s_{2} − s_{1}), …, s_{1} − (n/2 − 1)(s_{2} − s_{1}))

all elements are pairwise distinct and the last element is equal to s_{2}. The latter condition means that the difference s_{2} − s_{1} has order n/2 in G, and the former condition reduces then to G = {0, s_{1}} ⊕ H, where H is the subgroup, generated by s_{2} − s_{1}. Equivalently, H is a subgroup of index 2, to which neither s_{1} nor s_{2} belong. □

Corollary 2. For any finite abelian group G with |G| ≥ 3 we have σ_{min}(G) ≥ 2. Equality is attained in the last estimate if and only if G has a cyclic subgroup of index 2; that is, either G is cyclic of even order, or G is of type (2, m) with an even m ≥ 2.

To complete our investigation of the quantity σ_{min}(G) we observe that for |G| even the assertion of Theorem 5 follows from Corollary 2, or alternatively from the combination of Corollary 1 and Lemma 1; for |G| odd it follows by combining Corollary 2 and Lemma 2.

7. The maximum number of sums: σ_{max}(G)

Proof of Theorem 6. If C = (g_{1}, …, g_{|G|}) is an RS-cycle over the finite non-trivial abelian group G, then the sum of the elements of G is Σ(G) = (g_{1} + g_{2}) + ⋯ + (g_{|G|} + g_{1}) = 2Σ(G), whence Σ(G) = 0. Thus, if G is one-involution, then σ_{max}(G) ≤ |G|−1. Moreover, if G is an elementary abelian 2-group with |G| > 2, then by Theorem 2 we have σ_{max}(G) = δ_{max}(G) ≤ |G| − 2 and indeed, equality holds provided that |G| ≠ 8. Furthermore, if G is elementary abelian of order |G| = 8, then a cycle C ∈ C(G) with |S(C)| = 6 is easy to construct; say, if g_{1}, g_{2}, g_{3} are independent elements of G, then one can set

C := (0, g_{1}, g_{2}, g_{3}, g_{1} + g_{2}, g_{1} + g_{2} + g_{3}, g_{1} + g_{3}, g_{2} + g_{3}).

This establishes the upper bound for σ_{max}(G) and shows that equality is attained if G is an elementary abelian 2-group with |G| > 2.

If G is neither a one-involution group, nor an elementary abelian 2-group, then by [7, Theorem 6.6] the group G possesses an RS-cycle, which proves the assertion in this case.

Finally, suppose that G is one-involution, and hence the direct sum of a (possibly, trivial) group of odd order and a cyclic group of even order. Identifying the latter group with the corresponding group of residues, we can then write G = H ⊕ (ℤ/nℤ), where H is a group of odd order k := |H|, and n = 2m is a positive even integer. If k = 1 we let h_{1} = 0 (the zero element of the group H), if k ≥ 3 we fix an RS-cycle (h_{1}, …, h_{k}) ∈ C(H); the existence of such an RS-cycle follows from the above-mentioned [7, Theorem 6.6]. Consider the Hamiltonian paths P′ and P′′ on ℤ/nℤ, defined by

P′ := (0, m, 1, m + 1, 2, m + 2 , …, m − 1, 2m − 1),
P′′ := (m, 0, m + 1, 1, m + 2, 2 , …, 2m − 1, m − 1).

We have S(P′) = S(P′′) = (ℤ/nℤ) \ {m − 1}, so that P′ and P′′ are RS-paths. For i = 1, …, n let p′_{i} and p′′_{i} denote the ith elements of P′ and P′′, respectively. Observing that p′_{n} + p′′_{1} = p′′_{n} + p′_{1} = m − 1, one verifies easily that

P := (h_{1} + p′_{1}, h_{1} + p′_{2}, …, h_{1} + p′_{n},
h_{2} + p′′_{1}, h_{2} + p′′_{2}, …, h_{2} + p′′_{n},
⋮
h_{k} + p′_{1}, h_{k} + p′_{2}, …, h_{k} + p′_{n})

is a Hamiltonian path on G with S(P) = G \ {h_{1} + h_{k} + (m − 1)}, hence an RS-path on G. Closing it (by joining its last and first elements) we obtain a Hamiltonian cycle C ∈ C(G) with |S(C)| ≥ |S(P)| = |G| − 1, as wanted. □

We note that RS-cycles were first introduced in [7], where they are called harmonious sequences and those groups possessing an RS-cycle are called harmonious groups.

SUMS AND DIFFERENCES ALONG HAMILTONIAN CYCLES 15

8. The expected number of sums: σ_{rnd}(G)

Proof of Theorem 7. Consider the two subgroups of the group G defined by G_{0} := {g ∈ G: 2g = 0} and 2G := {2g: g ∈ G}. Let n := |G| and n_{0} := |G_{0}|, so that |2G| = n/n_{0} in view of the isomorphism G/G_{0} ≅ 2G. Without loss of generality we assume that n ≥ 3.

Given a Hamiltonian cycle C ∈ C(G), represent S(C) as a sum of indicator random variables, corresponding to the elements of G, and write

σ_{rnd}(G) = ∑_{g∈G} Pr \{g ∈ S(C)\} = \frac{1}{(n − 1)!} ∑_{g∈G} |\{C ∈ C(G): g ∈ S(C)\}|.  (4)

Assuming that g ∈ G is fixed, for each A ⊆ G let C_{A}(G) denote the set of all those cycles C ∈ C(G) such that every a ∈ A is followed along C by g − a. Observe, that if g = a′ + a′′ with some a′, a′′ ∈ A, then a′ is to be followed by a′′ and vice versa along any cycle C ∈ C_{A}(G); consequently, C_{A}(G) is empty in this case. On the other hand, if g has no representations as g = a′ + a′′ with a′, a′′ ∈ A, then it is easy to see that |C_{A}(G)| = (n − |A| − 1)! (compare with Claim 1 in the proof of Theorem 3). Using the inclusion-exclusion principle we get

|{C ∈ C(G): g ∈ S(C)}| = | ⋃_{∅≠A⊆G}C_{A}(G)|

= ∑_{∅≠A⊆G}(−1)^{|A|+1}|C_{A}(G)|

= ∑_{j=1}^{n−1}(−1)^{j+1}(n − j − 1)! N_{j},  (5)

where N_{j} is the number of those A ⊆ G with |A| = j such that g cannot be represented as a sum of two elements of A.

If g ∉ 2G then G is a disjoint union of pairs of the form (c, g −c) with c ∈ G, and in order for A to have the property that a′ + a′′ ≠ g for all a′, a′′ ∈ A, it is necessary and sufficient that A contains at most one element out of each pair. Thus, N_{j} = \binom{n/2}{j} 2^{j} if j ≤ n/2, and N_{j} = 0 if j > n/2 in this case. On the other hand, if g ∈ 2G then there are n_{0} representations g = 2c with c ∈ G; removing such elements c from G, we can split the remaining n − n_{0} elements into (n − n_{0})/2 pairs as above, and now in order for A to have the property in question it is necessary and sufficient that A contains at most one element out of each of these pairs (and no non-paired elements). Therefore, in this case N_{j} = \binom{(n−n_{0})/2}{j} 2^{j} if j ≤ (n − n_{0})/2, and N_{j} = 0 if j > (n − n_{0})/2. Using these observations, from (4) and (5) we obtain

σ_{rnd}(G) = \frac{1}{(n − 1)!} (1 − \frac{1}{n_{0}} ) n ∑_{1≤j≤n/2}(−1)^{j+1}(n − j − 1)! \binom{n/2}{j}2^{j}

+ \frac{1}{(n − 1)!} \frac{n}{n_{0}} ∑_{1≤j≤(n−n_{0})/2}(−1)^{j+1}(n − j − 1)! \binom{(n − n_{0})/2}{j}2^{j}, (6)

where the first summand is to be dropped if n is odd.

Let now m denote one of the numbers n/2 and (n − n_{0})/2 and suppose that m is an integer. Notice that for any j ∈ [1, m] we have

\frac{1}{(n − 1)!} (n − j − 1)! = \frac{1}{(n − j) ⋯ (n − 1)} > n^{−j}

while, on the other hand,

\frac{1}{(n − 1)!} (n − j − 1)! = n^{−j}(1 − \frac{1}{n})^{−1} ⋯ (1 − \frac{j}{n})^{−1}

< n^{−j}e^{2(\frac{1}{n} +···+ \frac{j}{n})} ≤ n^{−j}e^{2j^{2}/n} < n^{−j}(1 + O(j^{2}/n)).

It follows that

\frac{1}{(n − 1)!} ∑_{j=1}^{m}(−1)^{j+1}(n − j − 1)!\binom{m}{j}2^{j}

= − ∑_{j=1}^{m} \binom{m}{j}( − \frac{2}{n})^{j} + O(\frac{1}{n} ∑_{j=1}^{m} \binom{m}{j}j^{2}(\frac{2}{n})^{j})

= 1 − (1 − \frac{2}{n})^{m} + O(\frac{1}{n} ∑_{j=1}^{m} \frac{j^{2}}{j!} (\frac{2m}{n})^{j})

= 1 − e^{m ln(1−2/n)} + O(\frac{1}{n} ∑_{j=1}^{m} \frac{j^{2}}{j!} )

= 1 − e^{−2m/n+O(m/n^{2})} + O(1/n)

= 1 − e^{−2m/n}(1 + O(m/n^{2})) + O(1/n)

= 1 − e^{−2m/n} + O(1/n).

Now if n is odd then n_{0} = 1 and (6) along with the last computation give

σ_{rnd}(G) = n(1 − e^{−(n−1)/n} + O(1/n)) = (1 − e^{−1}) n + O(1), as wanted. Similarly, if n is even then

σ_{rnd}(G) = (1 − \frac{1}{n_{0}} )n(1 − e^{−1} + O(1/n)) + \frac{n}{n_{0}} (1 − e^{−(n−n_{0})/n} + O(1/n))

= (1 − e^{−1}) n + \frac{n}{n_{0}} (e^{−1} − e^{−(n−n_{0})/n}) + O(1)

= (1 − e^{−1}) n + \frac{1 − e^{n_{0}/n}}{n_{0}/n} e^{−1} + O(1)

= (1 − e^{−1}) n + O(1),

completing the proof. □

References

[1] B. Gordon, Sequences in groups with distinct partial products, Pacific J. Math. 11 (1961), 1309–1313.

[2] P. Headley, R-sequenceability and R*-sequenceability of Abelian 2-groups, Discrete Math. 131 (1–3) (1994), 345–350.

[3] R.J. Friedlander, B. Gordon, and M.D. Miller, On a group sequencing problem of Ringel, Congr. Numer. 21 (1978), 307–321.

[4] M.A. Ollis, Private communication.

[5] B. Cheyne, V. Gupta, and C. Wheeler, Hamilton Cycles in Addition Graphs, Rose-Hulman Undergraduate Math. Journal 1 (4) (2003) (electronic).

[6] D. Marušič, Hamiltonian circuits in Cayley graphs, Discrete Math. 46 (1) (1983), 49–54.

[7] R. Beals, J.A. Gallian, P. Headley, and D. Jungreis, Harmonious groups, J. Comb. Theory, Series A 56 (1991), 223–238.

[8] L.J. Paige, A note on finite Abelian groups, Bull. Amer. Math. Soc. 53 (1947), 590–593.

[9] J. Surányi, A certain way of presenting finite abelian groups [Hungarian], Mat. Lapok 23 (1972), 257–259 (1974).

[10] H.S. Snevily, Unsolved Problems: The Cayley Addition Table of ℤ_{n}, Amer. Math. Monthly 106 (6) (1999), 584–585.

[11] A.D. Keedwell, Complete mappings and sequencings of finite groups, in CRC Handbook of Combinatorial Designs (C.J Colbourn and J.H Dinitz eds.), CRC Press 1996, 246–253.

[12] M.A. Ollis, On terraces for abelian groups, Discrete Mathematics 305 (2005), 250–263.

[13] B. Green, Counting sets with small sumset, and the clique number of random Cayley graphs, Combinatorica 25 (3) (2005), 307–326.

[14] L.J. Paige, Complete mappings of finite groups, Pacific J. Math. 1 (1951), 111–116.

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

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