Maximal Subset Sums in a Group of Order a Power of 2

John Greene and Clayton Higgins Department of Mathematics and Statistics University of Minnesota Duluth Duluth, MN 55812 USA

                       jgreene@d.umn.edu
                      higgi503@d.umn.edu

Abstract If G is an abelian group of order 2^{n}, and S = {g_{1}, g_{2}, …, g_{n}} is a subset of G, we call S a perfect cover for G if every element of G is the subset sum of elements in S. We prove that perfect covers always exist and count how many perfect covers there are for selected groups. In particular, we count the number of perfect covers for the groups ℤ_{2^{m}} ⊕ ℤ_{2^{n}} and (ℤ_{2})^{m} ⊕ ℤ_{2^{n}}.

1 Introduction

Given an additive abelian group G, there is extensive literature related to sequences

S = {g_{1}, g_{2}, …, g_{k}}

of nonzero elements of G. Erdős, Ginzburg and Ziv [6] asked when such sequences either contain, or do not contain subsequences summing to 0. The smallest k so that every sequence of length k must have a subsequence summing to 0 is called the Davenport constant for G, investigated in various papers [5, 7, 14, 15]. The Davenport constant has applications to non-unique factorization [11] and to the density of Carmichael numbers [2].

The inverse problem deals with long sequences with no zero-sum subsequences. See, for example, Olson [14] or Gao et al. [8]. Yet another related problem asks how many representations an element g ∈ G might have as a subsequence sum, as investigated by Gao and Geroldinger [10], and more recently by Lev [12]. See Gao and Geroldinger [9] for a survey of zero-sum problems.

Here, we are interested in a different question. We say that a sequence S covers an element g ∈ G if g is a subsequence sum of elements of S. Every sequence S covers 0 because we allow the empty subsequence. We say a sequence S covers G if S covers every element of G. Rather than ask how large S must to be, we look at the other extreme, how small S can be and still cover G. We mention the simplest case, where G is cyclic of order m, say G = ℤ_{m}. Then S = {1, 2, 4, …, 2^{k−1}} with k = ⌈log_{2}(m)⌉ is best possible. For general G, we do not know how small k = |S| can be. However, if G = ℤ_{m_{1}} ⊕ ℤ_{m_{2}} ⊕ ⋯ ⊕ ℤ_{m_{j}} then k = ⌈log_{2}(m_{1})⌉ + ⌈log_{2}(m_{2})⌉ + ⋯ + ⌈log_{2}(m_{j})⌉ suffices.

In the case where |G| = 2^{n}, we can say more. If every element of G is covered by exactly m subsequences (up to order), we call S a perfect m-cover for G. Most of our attention is focused on the case where m = 1, requiring each element of G to be covered by a unique subsequence of S. In this case, we drop the m and call S a perfect cover. Since a perfect cover cannot contain repeated elements, and we do not wish to consider the order of the terms in the sequence, in this case, we take S to be a set, and consider the subset sums. A perfect cover is a perfect restricted n-basis for a group of size 2^{n}, as defined by Bajnok, Berson and Just [4]. For perfect m-covers, we introduce the notation of a colored multiset. A colored multiset is a multiset, where each instance of an element g in the set is considered distinct (a different color) from the other instances in the set. For example, if S = {1, 1, 5, 6, 6} = {1_{1}, 1_{2}, 5, 6_{1}, 6_{2}} in Z_{8}, then 4 is covered five times by S,

4 = 6_{1} + 6_{2}
= 6_{1} + 5 + 1_{1}
= 6_{1} + 5 + 1_{2}
= 6_{2} + 5 + 1_{1}
= 6_{2} + 5 + 1_{2}.

Colored multisets arise naturally in the theory of integer partitions, when numbers can be repeated, but are considered to have different kinds or colors. See, for example, Andrews [3] or Agarwal [1]. As in the theory of partitions, this scheme allows for a natural generating function interpretation in ℤ_{2^{n}}: If S contains m_{1} 1’s, m_{2} 2’s, and so on, then the generating function for the number of times k is counted is p(q), a polynomial of degree at most 2^{n} − 1, equal to the remainder when ∏_{i=1}^{2^{n}−1}(1 + q^{i})^{m_{i}} is divided by 1 − q^{2^{n}}. That is, p(q) is the unique polynomial of degree less than 2^{n} satisfying

∏_{i=1}^{2^{n}−1}(1 + q^{i})^{m_{i}} = (1 − q^{2^{n}})f(q) + p(q)

for some polynomial f(q). In our example above,

(1 + q)^{2}(1 + q^{5})(1 + q^{6})^{2} = (1 − q^{8})f(q) + p(q),

with p(q) = 5q^{7} + 5q^{6} + 5q^{5} + 5q^{4} + 3q^{3} + 3q^{2} + 3q + 3. Since the coefficients in p(q) for the example above are not all the same, we see that {1_{1}, 1_{2}, 5, 6_{1}, 6_{2}} is not a perfect m-cover for ℤ_{8}.

Perfect covers always exist.

Theorem 1. If G is an abelian group of size 2^{n}, then G has a perfect cover. In fact, if x ≠ 0, then there is a perfect cover containing x.

Proof. An explicit perfect cover for G is given by Bajnok, Berson, and Just [4, Section 4]. We give an alternative proof here, more conducive to counting perfect covers.

We induct on n, with the case of n = 1 being trivial. Assuming the result for groups of order less than 2^{n}, suppose |G| = 2^{n} and x ≠ 0 is in G. Let H be the subgroup generated by x. If |H| = 2^{m}, then H has a perfect cover {x, 2x, …, 2^{m−1}x}. By inductive hypothesis, G/H has a perfect cover {g_{1} + H, g_{2} + H, …, g_{n−m} + H}. We claim that S = {g_{1}, g_{2}, …, g_{n−m}, x, 2x, …, 2^{m−1}x} is a perfect cover for G. To that end, let g ∈ G. Since g + H ∈ G/H,

g + H = g_{i_{1}} + H + g_{i_{2}} + H, …, g_{i_{r}} + H = (g_{i_{1}} + g_{i_{2}} + ⋯ + g_{i_{r}}) + H

for some elements g_{i_{l}}. This means that g = g_{i_{1}} + g_{i_{2}} + ⋯ + g_{i_{r}} + h for some h ∈ H, and h is a sum of terms involving x. Since everything in G is a sum of elements of S and |S| = n, S is a perfect cover.

Our main focus is on the number of perfect covers for an abelian group of order 2^{n}. We do not have a complete answer to this question, but we have exact counts for a number of infinite families of groups. Let C(G) denote the number of perfect covers for a group G. Our main counting theorems are listed below.

Theorem 2. If G = ℤ_{2^{n}}, then G has 2^{n(n−1)/2} perfect covers. That is, C(ℤ_{2^{n}}) = 2^{n(n−1)/2}.

The sequence defined by a_{n} = 2^{n(n−1)/2} is sequence \underline{A006125} in the On-Line Encyclopedia of Integer Sequences (OEIS) [13].

We have two 2-parameter infinite families of groups where we can enumerate the number of perfect covers in terms of recurrence relations. These recurrences imply that there are explicit polynomials facilitating the count of the number of perfect covers.

Theorem 3. If a_{m,n} = C(ℤ_{2^{m}} ⊕ ℤ_{2^{n}}), then for m ≥ n ≥ 1, we have

a_{m,n} = 2^{m+n−1}(a_{m−1,n} + 2a_{m,n−1}) − 3 · 2^{2m+2n−4}a_{m−1,n−1}.  (1)

For each fixed n ≥ 0, there is a polynomial p(x) of degree n for which

C(Z_{2^{m}} ⊕ Z_{2^{n}}) = 2^{(m−1)n}2^{m(m−1)/2}p(m) for all m ≥ n.  (2)

We note that a_{m,0} = C(ℤ_{2^{m}}) = 2^{m(m−1)/2}. Also, a_{m,n} = a_{n,m}. However, the recurrence above is not symmetric in m, n and only applies when m ≥ n. Our other family involves groups of arbitrary rank, but with only one large cyclic component.

Theorem 4. Let b_{m,n} be the number of perfect covers for (ℤ_{2})^{m} ⊕ ℤ_{2^{n}}. Then

b_{m,0} = C((ℤ_{2})^{m}) = \frac{(2^{m} − 1)(2^{m} − 2^{1}) ⋯ (2^{m} − 2^{m−1})}{m!}.  (3)

If we define B_{m,k} by

B_{m,k} = \frac{2^{m}(2^{m} − 1)(2^{m} − 2^{1}) ⋯ (2^{m} − 2^{k−1})}{(k + 1)!},

then b_{m,n} satisfies a recurrence

b_{m,n} = 2^{m+n−1}b_{m,n−1} + ∑_{k=1}^{m} B_{m,k}2^{k(m−k)}2^{(k+1)(n−1)}b_{m−k,n−1}  (4)

for all m, n > 0. Moreover, for each m there is a polynomial q(x) of degree m for which

C((ℤ_{2})^{m} ⊕ ℤ_{2^{n}}) = 2^{m(n−1)}2^{n(n−1)/2}q(n) for all m, n ≥ 0.  (5)

The sequence b_{m,0} defined in formula 3 also counts the number of bases for an ndimensional space over ℤ_{2}, given in \underline{A053601}.

Theorem 2 and Theorem 3 are proved in Section 3; Theorem 4 is proved in Section 4. The proofs of these theorems require more detailed knowledge of perfect covers, which is presented in Section 2. Various special cases of the counting theorems are presented in Section 5, along with exact counts for abelian groups of order 2^{n} for all n ≤ 7.

2 Properties of perfect covers

We begin with two basic properties of perfect m-covers.

Lemma 5. If S = {g_{1}, …, g_{n}} is a perfect m-cover for G, then for any g ∈ G, S′ = {g, g_{1}, …, g_{n}} is a perfect (2m)-cover.

Proof. Given any element x in G, covered by m distinct sublists of S, x is covered by those same sublists of S′. Moreover, x − g is covered by m distinct sublists of S, and appending g to each of these gives another m lists covering x. All covers of x arise in one of these two ways.

Lemma 6. If G = H ⊕ K where |H| = 2^{m} and |K| = 2^{n}, and if S = {(h_{1}, k_{1}), …, (h_{j}, k_{j})} is a perfect l-cover for G, then S_{1} = {h_{1}, …, h_{j}} is a perfect (2^{n}l)-cover of H and S_{2} = {k_{1}, …, k_{j}} is a perfect (2^{m}l)-cover for K.

Proof. For every element (h, k) ∈ G, there are exactly l sublists of S covering (h, k). Thus, for each k, there are l such sublists. For every sublist of S covering (h, k), the corresponding sublists of S_{1} covers h. Thus, there are l|K| = 2^{n}l such sublists of S_{1} covering h. Since this number is independent of h, S_{1} is a perfect 2^{n}l-cover. The proof for S_{2} is similar.

Given an abelian group G, we define a function F on subsets A of G via

F (A) = ∑_{x∈A} x.

Note that if A and B are disjoint, then F (A ∪ B) = F (A) + F (B).

Lemma 7. Let G be an abelian group with |G| = 2^{n} and with perfect cover S = {z_{1}, …, z_{n}}. If z is an element of S and S_{1} = S − {z}, then each of the following hold.

(a) The subsets of S_{1} cover exactly half of G, with nothing covered more than once.

(b) Suppose that g is an element of G covered by S_{1} and j is a positive integer. Then S_{1} covers g + 2jz, but not g + (2j − 1)z.

Proof. If F (A) = F (B) for some subsets A, B of S_{1}, then since A and B are subsets of a perfect cover, A = B. A counting argument shows that S_{1} covers half of the elements of G.

For statement (b), we first consider the case where j = 1. If g is covered by S_{1} then g = F (A) for some subset A of S_{1}. Suppose g +z is covered by S_{1}, say g +z = F (B) for some subset B of S_{1}. Then g + z is covered by two subsets of S, B and A ∪ {z}, a contradiction. Next, suppose that g + 2z is not covered by S_{1}. Since g + 2z is covered by S, there must be a subset C of S, which is not a subset of S_{1} for which F (C) = g + 2z. In this case, z ∈ C so C = D ∪ {z} for some subset D of S_{1}. Now

g + 2z = F (C) = F (D ∪ {z}) = F (D) + z,

so F (D) = g + z, meaning g + z is covered by S_{1}, a contradiction.

Inducting on j, suppose that S_{1} covers g + 2jz but not g + (2j − 1)z for some j. Let g′ = g + 2jz. According to the above, g′ + z is not covered, but g′ + 2z is. That is, S_{1} does not cover g + (2j + 1)z but it does cover g + (2j + 2)z.

A similar result holds for perfect m-covers.

Lemma 8. Suppose |G| = 2^{n} and let S = {x_{1}, …, x_{j+n}} be a perfect 2^{j} cover. Let S_{1} = {x_{1}, …, x_{j+n−1}}. If a is covered m times by S_{1}, then a + x_{j+n} is covered 2^{j} − m times by S_{1}.

Proof. Let a + x_{j+n} be covered k times by S_{1}. Now a + x_{j+n} is covered 2^{j} times by S. Exactly k of these come from subsets of S_{1}. This means the remaining 2^{j} − k of them must be covered by subsets of S which are not subsets of S_{1}. These are all of the form A ∪ {x_{j+n}} where A is a subset of S_{1}. But these A all cover (a + x_{j+n}) − x_{j+n} = a, so there are exactly m of these. This means 2^{j} − k = m, or k = 2^{j} − m, as desired.

Corollary 9. If b is covered m times by S_{1}, then for all k, b + 2kx_{j+n} is covered m times, and b + (2k + 1)x_{j+n} is covered 2^{j} − m times by S_{1}.

Proof. This is induction on k, but the basic idea is that by Lemma 8, b + x_{j+n} is covered 2^{j} − m times, and applying Lemma 8 with b + x_{j+m} instead of b, then b + 2x_{j+m} is covered 2^{j} − (2^{j} − m) = m times, b + 3x_{j+n} is covered 2^{j} − m times, and so on.

There is a useful equivalence relation on the elements of G defined as follows. We write a ∼ b if b is an odd multiple of a. We note that this is obviously an equivalence relation. Moreover, this relation interacts well with perfect covers. We have the following theorem.

Theorem 10. Given a group G of order 2^{n}, the following are equivalent for a, b ∈ G.

(1) a ∼ b.

(2) For any perfect cover S = {a, s_{2}, …, s_{n}}, T = {b, s_{2}, …, s_{n}} is also a perfect cover.

(3) The set {a, b} is never a subset of a perfect cover.

Proof. Suppose S = {a, s_{2}, …, s_{n}} is a perfect cover. Let T = {b, s_{2}, …, s_{n}} and S′ = {s_{2}, …, s_{n}}. If x is covered by S′, then so is x + 2ra for all r. So suppose F (A) = y for some subset A of S. If A is a subset of S′ then A is a subset of T as well, so T covers y. Next, suppose that a ∈ A and let A′ = A − {a}. Then F (A) = F (A′) + a, or F (A′) = y − a. Now A′ ⊆ S′, meaning that y−a is covered by S′. As a consequence, so is y−a+2ra for all integers r. If b = (2j + 1)a then selecting r = −j we have that S′ represents y − a − 2ja = y − b. Letting F (B) = y − b for B ⊆ S′, we have F ({b} ∪ B) = y. That is, T covers y. Since y was an arbitrary element of G, T covers G, making it a perfect cover. Thus, (1) implies (2).

Next, (2) implies (3), for if {a, b, s_{3}, …, s_{k}} is a perfect cover, then replacing a by b gives that {b, b, s_{3}, …, s_{k}} is also be a perfect cover. However, this set represents b in two different ways, a contradiction.

Finally, suppose that b is not equivalent to a. We show that there is a perfect cover containing both a and b, and this is the contrapositive of (3) implying (1), completing the proof. To that end, let H be the subgroup generated by a. Since b is not an odd multiple of a, either b is an even multiple of a or b is not in H. In the first case, we can form a perfect cover for H containing both a and b, leading to a perfect cover for G containing both a and b. In the second case, we can let bH be one of the cosets of H and by Lemma 1, there is a perfect cover for G/H containing bH, leading to a perfect cover for G containing b.

By using Corollary 9 we also have the following extension of part (2) of the theorem above.

Lemma 11. Suppose G is an abelian group of order 2^{n}, with perfect 2^{k}-cover and S = {a, s_{2}, …, s_{n+k}}. If a ∼ b then T = {b, s_{2}, …, s_{n+k}} is also a perfect 2^{k}-cover of G.

Proof. Let y ∈ G. Then y is covered 2^{k} times by S. We prove that y is also covered 2^{k} times by T. To that end, let y be covered m times by S′ = {s_{2}, …, s_{n+k}}. Then y − a is covered 2^{k} − m times by S′. Now b = (2j + 1)a for some j so by Corollary 9, y − b = y − a − 2ja is covered 2^{k} − m times by S′, as desired.

Appending any element to a perfect m-cover produces another perfect cover, as mentioned in Theorem 5. A partial converse might be that every perfect m-cover contains a perfect (m/2)-cover as a sublist. Unfortunately, in general, this is not true. For example, the set {(0, 1), (1, 0), (1, 1), (1, 2), (1, 3), (2, 1)} is a perfect 4-cover for ℤ_{4} ⊕ ℤ_{4}, but none of the six subsets of order 5 is a 2-cover, and no subset is a perfect cover. However, in the case of G = ℤ_{2^{n}}, we can say more.

Theorem 12. A colored multiset S = {g_{1}, g_{2}, …, g_{k}} is a perfect m-cover for G = ℤ_{2^{n}} if and only if S contains elements of each order 2, 2^{2}, … 2^{n}.

Proof. If a ∼ b then a and b have the same order in G. For G = ℤ_{2^{n}}, the equivalence class of a consists of all elements with the same order as a. Given an m-cover S = {g_{1}, g_{2}, …, g_{k}} for G, if m > 1 then some of the g_{i} might be 0. Let z count the number of 0’s in S. For the other elements of S, we systematically apply Theorem 11 to find a simpler cover. For each g_{i} ≠ 0, replace it in S by the smallest positive integer of the same order. The result is a new m-cover containing only 0’s and powers of 2. Such a cover contains z zeros, l_{0} 1’s, l_{1} 2’s, …, l_{n−1} elements 2^{n−1}. Now {1, 2, 2^{2}, …, 2^{n−1}} is a perfect cover for G. As a consequence, by Theorem 5, appending 0’s or powers of 2 to this set produces perfect 2^{j}-covers, with j being the number of elements added to the colored multiset.

For the other direction, the generating function for the number of covers for the elements of G is g(q) with

2^{z} ∏_{i=0}^{n−1}(1 + q^{2^{i}})^{l_{i}} = f(q)(1 − q^{2^{n}}) + g(q).  (6)

To be a perfect m-cover, we need

g(q) = m(1 + q + q^{2} + ⋯ + q^{2^{n}−1}) = m ∏_{i=0}^{n−1}(1 + q^{2^{i}}).

Since 1 − q^{2^{n}} = (1 − q) ∏_{i=0}^{n−1}(1 + q^{2^{i}}), we see that 1 + q^{2^{i}} divides the right hand side of (6). Since 1 + q^{2^{i}} is irreducible over ℤ for each i, this polynomial must divide the left hand side as well, showing that l_{i} > 0, as desired.

Corollary 13. Every perfect m-cover for ℤ_{2^{n}} contains a perfect cover.

Proof. Slightly more is true: if S = {g_{1}, g_{2}, …, g_{k}} is a perfect m-cover, with m > 1, then there is an element g_{i} that can be deleted from S to produce a perfect (m/2)-cover. To show this, if S contains 0, then this can be deleted producing the perfect (m/2)-cover. If S does not contain 0, then S contains k > n elements of order larger than 1. But there are only n orders for nonzero elements of G. Thus, there must be two elements, g_{i}, g_{j} of the same order. Deleting g_{j} produces a colored list of size k − 1, containing all orders. Thus, this list is a perfect (m/2)-cover. The conclusion of the corollary follows.

Corollary 14. If S = {(h_{1}, k_{1}), …, (h_{n}, k_{n})} is a perfect m-cover for H ⊕ ℤ_{2^{n}}, where H has order a power of 2, then S contains elements k_{i} of each order 2^{j} with 1 ≤ j ≤ n.

Proof. This is an immediate consequence of Theorem 12 and Theorem 6.

We introduce an operator, T on subsets of G, defined as follows. If A = {x_{1}, …, x_{k}} is a subset of G, then

T (A) = {a_{1}x_{1} + ⋯ + a_{m}x_{m} | for each i, a_{i} = 0 or a_{i} is odd}.

By virtue of the equivalence in Theorem 10, T reacts well with perfect covers. We have the following basic properties of T .

Theorem 15. Let S = {s_{1}, s_{2}, …, s_{n}} be a perfect cover for a group G of order 2^{n}.

(a) If A and B are disjoint subsets of S, then T (A) ∩ T (B) = {0}.

(b) In particular, if A ⊆ S and s_{i} ∉ A then s_{i} ∉ T (A).

(c) For any subset A = {x_{1}, …, x_{k}} of G, the set T (A) is a union of equivalence classes of elements of G, along with 0.

Proof. For part (a), without loss of generality, let A = {s_{1}, …, s_{k}} and B = {s_{k+1}, …, s_{l}}. Suppose g ∈ T (A)∩T (B) and g ≠ 0. Then g = a_{1}s_{1}+⋯+a_{k}s_{k} and g = a_{k+1}s_{k+1}+⋯+a_{l}s_{l} for some a_{i} which are either 0 or odd. Since g ≠ 0, at least one a_{i} with 1 ≤ i ≤ k is nonzero and at least one a_{j} with k + 1 ≤ j ≤ l is nonzero. For each i ≤ l, let

b_{i} = \begin{cases}1, & if a_{i} = 0, \\ a_{i}, & if a_{i} ≠ 0. \end{cases}

Then by systematic application of Theorem 10, we see that S′ = {b_{1}s_{1}, …, b_{l}s_{l}, s_{l+1}, …, s_{n}} is a perfect cover for g. In this perfect cover, g has two distinct representations as subset sums, a contradiction.

Part (b) is a special case of part (a), since we may let B = {s_{i}}. For part (c), suppose g ∈ T (A), say g = a_{1}x_{1}+⋯+a_{k}x_{k}, with each a_{i} either 0 or odd. Then bg = ba_{1}x_{1}+⋯+ba_{k}x_{k} for any integer b, and if b is odd, then ba_{i} is either 0 or odd for each i, so bg ∈ T (A) as well. Thus, T contains the equivalence class of g as a subset, and the result follows.

Another general property of T is the following.

Lemma 16. If G is an abelian group of order 2^{n} and x_{1}, x_{2}, …, x_{m} are any nonzero elements of G satisfying x_{i} ∉ T ({x_{1}, …, x_{i−1}}) for each i with 2 ≤ i ≤ m, then all subset sums of {x_{1}, x_{2}, …, x_{m}} are distinct. In particular, if m = n then {x_{1}, x_{2}, …, x_{m}} is a perfect cover for G.

Proof. Let A and B be subsets of {x_{1}, x_{2}, …, x_{m}} and suppose F (A) = F (B). Letting C = A∩B, it is clear that A−C and B−C also have the same subset sums. If A ≠ B then there is a largest index j with x_{j} ∈ (A−C)∪(B−C). However, this implies x_{j} = ϵ_{1}x_{1}+⋯+ϵ_{j−1}x_{j−1} where each ϵ_{i} is 0 or ±1. In particular, x_{j} ∈ T ({x_{1}, …, x_{j−1}}), a contradiction.

3 Counting theorems for groups of rank 1 or 2.

In this section, we provide proofs for Theorem 2 and Theorem 3. We begin with the first of these.

Proof of Theorem 2. Two group elements in ℤ_{2^{m}} are equivalent if and only if they have the same order. Since elements of a perfect cover must come from different equivalence classes, and there are only m equivalence classes for ℤ_{2^{m}}, the number of perfect covers is the product of the sizes of the equivalence classes. There are 2^{m−j−1} elements in the equivalence class of 2^{j}, so

C(ℤ_{2^{m}}) = 2^{m−1}2^{m−2} ⋯ 2^{1} · 2^{0} = 2^{m(m−1)/2},

as desired.

The group ℤ_{2^{m}} ⊕ ℤ_{2^{n}} contains three elements of order 2. We leverage this fact to count perfect covers. We begin with two general lemmas, followed by a lemma specific to ℤ_{2^{m}} ⊕ℤ_{2^{n}}, before giving the proof of Theorem 3.

Lemma 17. Let G be an abelian group of order 2^{n}, with H a subgroup of order 2^{m}. Then G has exactly 2^{m(n−m)}C(G/H)C(H) perfect covers that contain a perfect cover for H as a subset.

Proof. Let {h_{1}, …, h_{m}} be a perfect cover for H and let {g_{1} + H, g_{2} + H, …, g_{n−m} + H} be a perfect cover for G/H. Then as in the proof of Theorem 1,

S = {g_{1}, g_{2}, …, g_{n−m}, h_{1}, h_{2}, …, h_{m}}

is a perfect cover for G. Now each g_{i} is an arbitrary element of a particular coset of H, so g_{i} can be selected in |H| = 2^{m} ways, giving us 2^{m(n−m)}C(G/H)C(H) ways to select S. Each selection is distinct, due to either the g’s differing or the h’s differing.

We must show that perfect covers for G which contain a perfect cover for H must arise in this way. To that end, let

S = {g_{1}, g_{2}, …, g_{n−m}, h_{1}, h_{2}, …, h_{m}}

be a perfect cover for G containing a perfect cover of H as a subset. Given any g ∈ G, we may write g = F (A ∪ B) where A is a subset of {g_{1}, g_{2}, …, g_{n−m}} and B is a subset of {h_{1}, h_{2}, …, h_{m}}. Thus, g + H will be the sum of the cosets for the elements in A. That is, g + H is the sum of elements from some subset of {g_{1} + H, g_{2} + H, …, g_{n−m} + H}. By a counting argument, this forces {g_{1} + H, g_{2} + H, …, g_{n−m} + H} to be a perfect cover for G/H.

Lemma 18. If A is a subset of a perfect cover S for a group G, and A contains no elements of order 2, then T (A) either contains no elements of order 2, or contains at least two distinct elements of order 2.

Proof. If h has order 2 in G and h ∈ T (A), then h = a_{1}x_{1}+⋯+a_{k}x_{k} for some x_{1}, …, x_{k} ∈ A and all a_{i} odd. If x_{1} has order 2^{l}, then 2^{l−1}x_{1} has order 2, as does h + 2^{l−1}x_{1}. By hypothesis, x_{1} does not have order 2 so 2^{l−1} is even, consequently,

h + 2^{l−1}x_{1} = (a_{1} + 2^{l−1})x_{1} + a_{2}x_{2} + ⋯ + a_{k}x_{k} ∈ T (A).

Since h and h + 2^{l−1}x_{1} are distinct elements of order 2, the result follows.

Lemma 19. Every perfect cover for ℤ_{2^{m}} ⊕ ℤ_{2^{n}} contains an element of order 2.

Proof. By way of contradiction, suppose that S is a perfect cover for G = ℤ_{2^{m}} ⊕ ℤ_{2^{n}} which does not contain an element of order 2. Since S covers the elements of G of order 2, there must be some subset A ⊆ S of smallest size, for which T (A) contains an element, h, of order 2. If A = {x_{1}, …, x_{k}}, then h = a_{1}x_{1} + ⋯ + a_{k}x_{k}, where all a_{i} are odd. As in the previous lemma, let x_{1} have order 2^{j}. Then h + 2^{j−1}x_{1} ∈ T (A) as well. Suppose that 2^{j−1}x_{1} ∈ T (A), say 2^{j−1}x_{1} = b_{1}x_{1} + ⋯ + b_{k}x_{k}, where each b_{i} is either 0 or odd. If b_{1} is 0, then 2^{j−1}x_{1}, an element of order 2, would belong to T (A − {x_{1}}). Since A − {x_{1}} a proper subset of A, we have a contradiction. If b_{1} is odd, then (2^{j−1} − b_{1})x_{1} ∈ T (A − {x_{1}}), which contradicts Theorem 15. Thus, 2^{j−1}x_{1} ∉ T (A). Note that this shows A ≠ S. If |x| is the order of x in G, then a similar argument shows that \frac{1}{2}|x_{i}|x_{i} ∉ T (A) for any i. Since G has exactly three elements of order 2, it follows that the third element is \frac{1}{2}|x_{1}|x_{1} = \frac{1}{2}|x_{i}|x_{i} for each i.

Next, let B = S −A. Since \frac{1}{2}|x_{1}|x_{1} is covered by S we have \frac{1}{2}|x_{1}|x_{1} = c_{1}x_{1} +⋯+c_{k}x_{k} +u where each c_{i} is 0 or odd and u ∈ T (B). If any c_{i} is odd, then \frac{1}{2}|x_{1}|x_{1} = \frac{1}{2}|x_{i}|x_{i} = c_{1}x_{1} + ⋯ + c_{k}x_{k} + u implies x_{i} ∈ T (S − {x_{i}}), violating Theorem 15. Consequently, each c_{i} is 0, showing \frac{1}{2}|x_{1}|x_{1} ∈ T (B). However, by Lemma 18, this forces T (B) to contain at least two elements of order 2. Finally, since both T (A) and T (B) contain at least two elements of order 2, one of these elements is common to T (A) ∩ T (B), contradicting Theorem 15. This concludes the proof the lemma.

Proof of Theorem 3. We begin with the recurrence relation (1). If h is an element of order 2 in G, a group of order 2^{k}, then by Lemma 17, G has 2^{k−1}C(G/⟨h⟩) perfect covers containing h. Let h_{1} = (2^{m−1}, 0), h_{2} = (0, 2^{n−1}) and h_{3} = (2^{m−1}, 2^{n−1}) be the three elements of order 2 in G = ℤ_{2^{m}} ⊕ ℤ_{2^{n}}. Every perfect cover contains at least one of h_{1}, h_{2}, h_{3}. If a perfect cover contains two of the elements of order 2, then the elements of order 2 will form a perfect cover for H, the unique non-cyclic subgroup of order 4 in G. By inclusion-exclusion and Lemma 17, we have

\begin{matrix}C(G) = 2^{m+n−1}(C(G/⟨h_{1}⟩) + C(G/⟨h_{2}⟩) + C(G/⟨h_{3}⟩)) \\ −2^{2m+2n−4}C(G/H)C(H). \end{matrix}

Now

G/⟨h_{1}⟩ ≈ ℤ_{2^{m−1}} ⊕ ℤ_{2^{n}}, G/⟨h_{2}⟩ ≈ G/⟨h_{3}⟩ ≈ ℤ_{2^{m}} ⊕ ℤ_{2^{n−1}},

and G/H ≈ ℤ_{2^{m−1}} ⊕ ℤ_{2^{n−1}}. Noting that C(H) = 3, the recurrence in Theorem 3 follows.

The m-component of the powers of 2 in recurrence (1) may be scaled away by setting a_{m,n} = 2^{(m−1)n}2^{m(m−1)/2}c_{m,n}. The resulting recurrence is

c_{m,n} = c_{m−1,n} + 2^{n+1}c_{m,n−1} − 3 · 2^{n−1}c_{m−1,n−1},

with initial condition c_{m,0} = 1. An induction argument shows that c_{m,n} − c_{m−1,n} is a polynomial in m of degree n − 1. From this, it follows that c_{m,n} is a polynomial in m of degree n. Denoting this polynomial p(x), it is straightforward to show that the leading term in p(x) is \frac{2^{n(n−1)/2}}{n!} x^{n}.

4 Proof of Theorem 4

Next, we turn our attention to Theorem 4, beginning with the group (ℤ_{2})^{m}.

Proof of Formula 3. The group (ℤ_{2})^{m} is an m-dimensional vector space over ℤ_{2}. As a consequence, any k independent elements in G span a k-dimensional subspace of size 2^{k}. A set S is a basis for G as a vector space if and only if S is a perfect cover. The number of ordered bases is clearly (2^{m} − 1)(2^{m} − 2) ⋯ (2^{m} − 2^{m−1}) as we select a nonzero element, then something not in its span, and so on. Since perfect covers are sets, we divide the count for ordered bases by m!.

For the recurrence in Theorem 4, we use the following notation. If G = H ⊕ ℤ_{2^{n}} is an abelian group with |H| = 2^{m}, let

S = {s_{1}, s_{2}, …, s_{m+n}} = {(x_{1}, y_{1}), …, (x_{m+n}, y_{m+n})}

be a perfect cover for G, where x_{i} ∈ H and y_{j} ∈ ℤ_{2^{n}} for each i, j. Note that the colored multiset {y_{1}, …, y_{m+n}} must be a perfect 2^{m}-cover for ℤ_{2^{n}}. As such, the y’s must contain elements of all orders larger than 1. We base our count on how many elements of order 2^{n} there are. These correspond to odd values of y. We begin with two general lemmas for G, and then focus on the case where H = (ℤ_{2})^{m}.

Lemma 20. A perfect cover S for G can have k odd y-values for any k with 1 ≤ k ≤ m + 1.

Proof. Since the colored multiset {y_{1}, …, y_{m+n}} is a perfect 2^{m} cover for ℤ_{2^{n}}, at least one, and no more than m + 1 of the y-values can be odd. Moreover, if 1 ≤ k ≤ m + 1 and {x_{1}, …, x_{m}} is a perfect cover for H, then the set

S = {(x_{1}, 0), …, (x_{m+1−k}, 0), (x_{m+2−k}, 1), …, (x_{m}, 1),
(0, 1), (0, 2), …, (0, 2^{n−1})}

is a perfect cover for H ⊕ℤ_{2^{n}} containing k odd y-values. This last claim follows because given any (h, l) ∈ G, one may select a subset of {x_{1}, …, x_{m}} summing to h. The corresponding subset of S will sum to an element (h, r) for some r ∈ ℤ_{2^{n}}, and one can add to (h, r) a subset sum of {(0, 1), (0, 2), …, (0, 2^{n−1})} summing to (0, l − r) to get (h, l). Since S covers G and has m + n elements, it must be a perfect cover.

Lemma 21. Let G = H ⊕ ℤ_{2^{n}} be an abelian group, with |H| = 2^{m}. There are

2^{m}2^{n−1}C(H ⊕ ℤ_{2^{n−1}})

perfect covers S in which y_{1} is odd but all y_{i} with i > 1 are even.

Proof. Every element of the form (h, 2k) ∈ H ⊕ ℤ_{2^{n}} must be covered by the elements in S − {(x_{1}, y_{1})}. Consequently, S − {(x_{1}, y_{1})} is a perfect cover for H ⊕ 2ℤ_{2^{n}} ≈ H ⊕ ℤ_{2^{n−1}}. Similarly, for every perfect cover for H ⊕ ℤ_{2^{n−1}}, one may double each y-component and add a term (u, v) with v odd to produce a perfect cover for H ⊕ℤ_{2^{n}}. Since there are 2^{m}2^{n−1} ways to select u and v, this means that H ⊕ ℤ_{2^{n}} has 2^{m}2^{n−1}C(H ⊕ ℤ_{2^{n−1}}) perfect covers with one odd y-value.

Corollary 22. The group (ℤ_{2})^{m} ⊕ ℤ_{2^{n}} has 2^{m}2^{n−1}a_{m,n−1} perfect covers S in which y_{1} is odd but y_{i} is even for every i > 1.

We now investigate the case where a cover of (ℤ_{2})^{m} ⊕ ℤ_{2^{n}} has a prescribed number of odd y-terms.

Lemma 23. Suppose that (ℤ_{2})^{m} ⊕ ℤ_{2^{n}} has a perfect cover S for which y_{1}, …, y_{k+1} are odd and the remaining y_{i} are even. As subspaces of the vector space (ℤ_{2})^{m} over ℤ_{2}, let

U = Span{x_{1} + x_{2}, x_{1} + x_{3}, …, x_{1} + x_{k+1}}

and

V = Span{x_{k+2}, …, x_{m+n}}.

Then dim U = k, dim V = m − k and U ∩ V = {0}. In particular, (ℤ_{2})^{m} = U ⊕ V.

Proof. The vector space U has an alternate description, that U is the set of all combinations of {x_{1}, …, x_{k+1}} which contain an even number of terms. Let h ∈ (ℤ_{2})^{m}. Since S is a perfect cover for (ℤ_{2})^{m} ⊕ ℤ_{2^{n}}, there is a subset A of S which covers (h, 0). This cover must contain an even number of elements s_{i} with i ≤ k + 1. As a consequence, h = h_{1} + h_{2} where h_{1} ∈ U and h_{2} ∈ V. This shows (ℤ_{2})^{m} = U + V.

Next, suppose h ≠ 0 and h ∈ U ∩ V. Then there are elements (h, 2u) and (h, 2v) in (ℤ_{2})^{m} ⊕ ℤ_{2^{n}} so that (h, 2u) is covered by some subset of {s_{1}, …, s_{k+1}} and (h, 2v) is covered by some subset of {s_{k+2}, …, s_{m+n}}. Since h ≠ 0, there must be a positive even number of s_{i} with i ≤ k + 1 in the sum giving (h, 2u). Let l be the largest index less than or equal to k + 1 so that

(h, 2u) = (x_{i_{1}}, y_{i_{1}}) + ⋯ + (x_{l}, y_{l}).

There is an odd number α so that αy_{l} + (2u − y_{l}) = 2v in ℤ_{2^{n}}. Consequently, if S′ = (S − {s_{l}}) ∪ {αs_{1}}, then S′ is a perfect cover for (ℤ_{2})^{m} ⊕ ℤ_{2^{n}}, by Theorem 10. However, since αx_{i} = x_{i} in (ℤ_{2})^{m}, the corresponding subset sums in S′ cover (h, 2v) twice, once from the first k + 1 values and once from the remaining values. That is, S′ cannot be a perfect cover, a contradiction. Thus, U ∩ V = {0}, showing (ℤ_{2})^{m} = U ⊕ V.

Finally, since (ℤ_{2})^{m} is the direct sum of U and V, showing dim U = k will also establish that dim V = m − k. To that end, suppose

ϵ_{1}(x_{1} + x_{2}) + ⋯ + ϵ_{k+1}(x_{1} + x_{k+1}) = 0

where each ϵ_{i} is 0 or 1. This sum corresponds to adding the x_{i} in some subset, A, of {x_{1}, x_{2}, …, x_{k+1}} where A has even size. Now x_{1} ∈ A if an odd number of the ϵ_{i} are 1 and x_{1} ∉ A if an even number of the ϵ_{i} are 1. If A is nonempty, of size 2j, then without loss of generality, A = {x_{1}, …, x_{2j}}. Now ∑_{i=1}^{2j−1}(x_{i}, y_{i}) = (u, v) where u = x_{2j} and v is odd. We now form an new cover, S′ by replacing (x_{2j}, y_{2j}) by (x_{2j}, 2^{n} − y_{2j}), which we can do by part 2 of Theorem 10, as multiplying x_{2j} by any odd number does not change x_{2j}. In this new cover, ∑_{i=1,x_{i}∈A}^{2j}(x_{i}, y_{i}) = (0, 0), providing two different covering sets for (0, 0), a contradiction.

Lemma 24. Under the same conditions as in Lemma 23,

{s_{k+2}, …, s_{m+n}}

is a perfect cover for V ⊕ 2ℤ_{2^{n}} ≈ (ℤ_{2})^{m−k} ⊕ ℤ_{2^{n−1}}.

Proof. The subset sums of {s_{k+2}, …, s_{m+n}} are all distinct, since this set is a subset of a perfect cover. Moreover, every subset sum belongs to V ⊕ 2ℤ_{2^{n}} by the previous Lemma. Since |V ⊕ 2ℤ_{2^{n}}| = 2^{m+n−k−1} and |{s_{k+2}, …, s_{m+n}}| = m + n − k − 1, the result follows.

With these preliminaries, we proceed to the proof.

Proof of the recurrence in Theorem 4. We count the number of perfect covers by cases based on how many odd y_{i} there are in the cover. If there is a single odd y-value, then by Lemma 22, there are 2^{m}2^{n−1}a_{m,n−1} such covers. For the case where there are k + 1 odd y-values, the previous lemma shows that every such perfect cover corresponds to a perfect cover for V ⊕ 2ℤ_{2^{n}}. Suppose now that V is a subspace of (ℤ_{2})^{m} of dimension m − k. We extend a perfect cover for V⊕2ℤ_{2^{n}} to perfect covers for (ℤ_{2})^{m}⊕2ℤ_{2^{n}} by denoting the cover for V⊕2ℤ_{2^{n}} to be {(x_{k+2}, y_{k+2}), …, (x_{m+n}, y_{m+n})}, and selecting k + 1 additional elements (x_{i}, y_{i}). The y_{i} may be arbitrary odd elements of ℤ_{2^{n}}, so each can be selected in 2^{n−1} ways. The set {x_{1} + x_{2}, …, x_{1} + x_{k+1}} must generate a k-dimensional vector space that intersects trivially with V. We select the x’s as follows. First select independent vectors u_{1}, …, u_{k} ∈ (ℤ_{2})^{m}, not in V. The first can be selected in 2^{m} − 2^{m−k} ways, the next in 2^{m} − 2^{m−k+1}, and so on, with u_{k} selected in 2^{m} − 2^{m−1} ways. Now let x_{1} be arbitrary, and let x_{i+1} = u_{i} − x_{1}. Thus, as an ordered list, one may select s_{1}, …, s_{k+1} in

2^{m}(2^{m} − 2^{m−k}) ⋯ (2^{m} − 2^{m−1})2^{(k+1)(n−1)}

ways. To convert from a list to a set, we divide this by (k + 1)!. Consequently, for every subspace V of dimension m − k we can construct

\frac{2^{m}(2^{m} − 2^{m−k}) ⋯ (2^{m} − 2^{m−1})}{(k + 1)!}2^{(k+1)(n−1)}a_{m−k,n−1}  (7)

perfect covers. Finally, we must count how many distinct subspaces V of dimension m − k there are. This is well known [17, Proposition 1.3.18] to be

\frac{(2^{m} − 1)(2^{m} − 2^{1}) ⋯ (2^{m} − 2^{m−k−1})}{(2^{m−k} − 1)(2^{m−k} − 2^{1}) ⋯ (2^{m−k} − 2^{m−k−1})}.  (8)

The product of the expressions in (7) and (8) is

B_{m,k}2^{k(m−k)}2^{(k+1)(n−1)}a_{m−k,n−1},

and the proof follows.

Proof of formula (5) in Theorem 4. Again, we may scale away some powers of 2 in the recurrence. Letting b_{m,n} = 2^{m(n−1)}2^{n(n−1)/2}d_{m,n}, the resulting recurrence is

d_{m,n} = d_{m,n−1} + ∑_{k=1}^{m} B_{m,k}2^{(k−1)(m−k)}d_{m−k,n−1}.

For a fixed m, this recurrence implies the existence of a polynomial q(x) of degree m for which d_{m,n} = q(n). The leading term for q(x) is \frac{(2^{m}−1)(2^{m}−2^{1})···(2^{m}−2^{m−1})}{m!}x^{m}.

5 Comments

The number of perfect covers for ℤ_{2^{m}} gives OEIS sequence \underline{A006125} and the number of perfect covers for ℤ_{2} × ℤ_{2^{m}} is related to \underline{A123903}. These OEIS sequences have an aspect in common: the first is the number of tournaments on n labeled nodes, and the second is the number of tournaments where one player beats every other player. We have not investigated this possible link to perfect covers, though we suspect it to be a coincidence.

We do not have general formulas for p(x) and q(x) in Theorem 3 and Theorem 4. The cases where their degrees are small are straightforward.

Corollary 25. For groups of rank 2, we have the counts

C(ℤ_{2^{n}} ⊕ ℤ_{2}) = 2^{n−1}2^{n(n−1)/2}(n + 2),  (9)
C(ℤ_{2^{n}} ⊕ ℤ_{4}) = 2^{2n−2}2^{n(n−1)/2}(n^{2} + 11n + 4),  (10)
C(ℤ_{2^{n}} ⊕ ℤ_{8}) = 2^{3n−3}2^{n(n−1)/2} \frac{4n^{3} + 108n^{2} + 512n − 384}{3}.  (11)

The first formula holds for all n ≥ 0, and is a scaled, translated version of a sequence in OEIS. Specifically, if a_{n} = 2^{n−1}2^{n(n−1)/2}(n + 2) then 2a_{n−2} gives sequence \underline{A123903}. The second formula in Corollary 25 is valid for n ≥ 1 and the third is valid for n ≥ 2.

Corollary 26. For groups covered by Theorem 4, we have special cases

C(ℤ_{2} ⊕ ℤ_{2} ⊕ ℤ_{2^{n}}) = 2^{2n−2}2^{n(n−1)/2}(3n^{2} + 13n + 12),  (12)

C(ℤ_{2} ⊕ ℤ_{2} ⊕ ℤ_{2} ⊕ ℤ_{2^{n}})  (13)
= 2^{3n−3}2^{n(n−1)/2}(28n^{3} + 196n^{2} + 392n + 224),

C((ℤ_{2})^{4} ⊕ ℤ_{2^{n}}) = 2^{4n−4}2^{n(n−1)/2} ×  (14)
(840n^{4} + 8400n^{3} + 27160n^{2} + 22488n + 13440),

each holding for all n ≥ 0.

We are currently far short of a count for the number of perfect covers for the general abelian group of order 2^{n}. We do not have a count for the general rank 3 case, C(ℤ_{2^{m}} ⊕ ℤ_{2^{k}} ⊕ ℤ_{2^{n−m−k}}), though we conjecture a recurrence for this case.

Conjecture 27. If a_{m,n,k} = C(ℤ_{2^{m}} ⊕ ℤ_{2^{n}} ⊕ ℤ_{2^{k}}), then when m ≥ n ≥ k we have

a_{m,n,k} = 2^{m+n+k−1}(a_{m−1,n,k} + 2a_{m,n−1,k} + 4a_{m,n,k−1})  (15)
− 3 · 4^{m+n+k−2}(a_{m−1,n−1,k} + 2a_{m−1,n,k−1} + 4a_{m,n−1,k−1})
+ 28 · 8^{m+n+k−3}a_{m−1,n−1,k−1}.

The initial conditions for this recurrence are that a_{m,n,0} = C(ℤ_{2^{m}} ⊕ ℤ_{2^{n}}), as given in Theorem 3, and that a_{m,n,k} is symmetric in m, n, k. This recurrence agrees with the count in Formula (12), where n = k = 1. The recurrence in conjecture 27 also agrees with the number of perfect covers calculated for ℤ_{4} ⊕ ℤ_{4} ⊕ ℤ_{2}, ℤ_{8} ⊕ ℤ_{4} ⊕ ℤ_{2}, ℤ_{4} ⊕ ℤ_{4} ⊕ ℤ_{4} and ℤ_{16} ⊕ ℤ_{4} ⊕ ℤ_{2}.

Conjecture 27 would follow from the rank 3 case of the following conjecture.

Conjecture 28. If G is an abelian group of order 2^{n}, then every perfect cover for G contains an element of order 2.

We have calculated the number of perfect covers for every group of order 2^{n} with n ≤ 7, as listed in the following tables.

Group ℤ_{2} ℤ_{4} ℤ_{2} ⊕ ℤ_{2} ℤ_{8} ℤ_{4} ⊕ ℤ_{2} (ℤ_{2})^{3}
Covers 1 2  3  8  16  28

Table 1: Cover counts for groups of size 8 or less.

Group ℤ_{16} ℤ_{8} ⊕ ℤ_{2} ℤ_{4} ⊕ ℤ_{4} ℤ_{4} ⊕ ℤ_{2} ⊕ ℤ_{2} (ℤ_{2})^{4}
Covers 64 160 240 400 840

Table 2: Cover counts for groups of order 16.

Group  ℤ_{32}  ℤ_{16} ⊕ ℤ_{2} ℤ_{8} ⊕ ℤ_{4} ℤ_{8} ⊕ (ℤ_{2})^{2}
Covers  1,024  3,072  5,888  9,984
Group ℤ_{4} ⊕ ℤ_{4} ⊕ ℤ_{2} ℤ_{4} ⊕ (ℤ_{2})^{3} (ℤ_{2})^{5}
Covers 16,128 32,256 83,328

Table 3: Cover counts for groups of order 32.

Group  ℤ_{64}  ℤ_{32} ⊕ ℤ_{2}  ℤ_{16} ⊕ ℤ_{4} ℤ_{16} ⊕ (ℤ_{2})^{2}
Covers  32,768  114,688  262,144  458,752
Group  ℤ_{8} ⊕ ℤ_{8}  ℤ_{8} ⊕ ℤ_{4} ⊕ ℤ_{2} ℤ_{8} ⊕ (ℤ_{2})^{3}  (ℤ_{4})^{3}
Covers  132,096  970,752  2,007,040 1,863,680
Group (ℤ_{4})^{2} ⊕ (ℤ_{2})^{2} ℤ_{4} ⊕ (ℤ_{2})^{4}  (ℤ_{2})^{6}
Covers 3,477,504  8,630,272 27,998,208

Table 4: Cover counts for groups of order 64.

Group  ℤ_{128}  ℤ_{64} ⊕ ℤ_{2}  ℤ_{32} ⊕ ℤ_{4}  ℤ_{32} ⊕ (ℤ_{2})^{2}
Covers 2,097,152  8,388,608  22,020,096  39,845,888
Group  ℤ_{16} ⊕ ℤ_{8}  ℤ_{16} ⊕ ℤ_{4} ⊕ ℤ_{2}  ℤ_{16} ⊕ (ℤ_{2})^{3} ℤ_{8} ⊕ ℤ_{8} ⊕ ℤ_{2}
Covers 39,845,888  101,711,872  220,200,960  153,354,240
Group ℤ_{8} ⊕ ℤ_{4} ⊕ ℤ_{4} ℤ_{8} ⊕ ℤ_{4} ⊕ (ℤ_{2})^{2} ℤ_{8} ⊕ (ℤ_{2})^{4}  (ℤ_{4})^{3} ⊕ ℤ_{2}
Covers 266,600,448  510,656,512  1,337,720,832 1,024,327,680
Group (ℤ_{4})^{2} ⊕ (ℤ_{2})^{3}  ℤ_{4} ⊕ (ℤ_{2})^{5}  (ℤ_{2})^{7}
Covers 2,513,960,960 7,850,164,224 32,509,919,232

Table 5: Cover counts for groups of order 128.

Theorem 1 provides a recursive scheme for finding a perfect cover for a group G of order 2^{n}. One selects any nonzero element x of G and builds a cover from perfect covers for ⟨x⟩ and for H = G/⟨x⟩. Given that a perfect cover for H might not be obvious, one iterates the procedure. We have not attempted to build an algorithm from this approach.

Theorem 15 and Lemma 16 suggest an alternate scheme for constructing perfect covers:

(1) Select an element x_{1} ≠ 0 from G, let S_{1} = {x_{1}}, and set j = 1.

(2) If j = n, stop, S_{n} is a perfect cover for G. Otherwise, given a set S_{j}, select x_{j+1} ∉ T (S_{j}).

(3) Let S_{j+1} = {x_{1}, x_{2}, …, x_{j}, x_{j+1}} and go to step (2).

This approach seems to produce a perfect cover most of the time. It is guaranteed to produce a perfect cover if step (2) can execute n − 1 times, giving j = n. However, this approach can fail, as shown by the set

S_{7} = {(0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 0), (1, 2, 3, 1), (1, 1, 2, 3), (1, 3, 1, 2)},

a subset of G = (ℤ_{4})^{4}. Here, T (S_{7}) = G but n = 8 so the subset sums only cover half of G. Thus, T (S_{j}) can fill the group G before j = n. We think that a group must have rank 4 before this approach can fail. It would be interesting to find a modification of this approach that is guaranteed to produce perfect covers.

We have extensive numerical evidence for Conjecture 27, and Conjecture 28. In particular, Conjecture 27 holds for every relevant group of order up to 128. Moreover, consistent with Conjecture 28, all perfect covers for groups of order up to 128 contain elements of order 2. It would be nice to see proofs for these conjectures.

References

[1] A. Agarwal, Rogers-Ramanujan identities for n-color partitions, J. Number Theory 28 (1988), 299–305.

[2] W. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. 140 (1994), 703–722.

[3] G. Andrews, A survey of multipartitions: Congruences and identities, Amer. J. Math. 5 (1982), 251–330.

[4] B. Bajnok, C. Berson, and H. A. Just, On perfect bases in finite abelian groups, Involve 15 (2022), 525–536.

[5] R. C. Baker and W. M. Schmidt, Diophantine problems in variables restricted to the values 0 and 1, J. Number Theory 12 (1980), 460–486.

[6] P. Erdős, A. Ginzburg, and A. Ziv, A theorem in additive number theory, Bull. Res. Council Israel 10 (1961), 41–43.

[7] W. Gao, On Davenport’s constant of finite abelian groups with rank three, Discrete Math. 222 (2000), 111–124.

[8] W. Gao, M. Huang, W. Hui, Y. Li, C. Liu, and J. Peng, Sums of sets of abelian group elements, J. Number Theory 208 (2020), 208–229.

[9] W. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: A survey, Expo. Math. 24 (2006), 337–369.

[10] W. Gao and A. Geroldinger, On the number of subsequences with given sum of sequences over finite abelian p-groups. Rocky Mountain J. Math. 37 (2007), 1541–1550.

[11] A. Geroldinger, Sets of lengths, Amer. Math. Monthly 123 (2016), 960–988.

[12] V. F. Lev, A nonlinear bound for the number of subsequence sums, European J. Combin. 118 (2024), 103907.

[13] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2025. Published electronically at https://oeis.org.

[14] J. Olson, An addition theorem mod p, J. Combin. Theory 5 (1968), 45–52.

[15] J. Olson, A combinatorial problem on finite Abelian groups, I, J. Number Theory 1 (1969), 8–10.

[16] J. Olson, A combinatorial problem on finite Abelian groups, II, J. Number Theory 1 (1969), 195–199.

[17] R. Stanley, Enumerative Combinatorics, Volume 1, Wadsworth & Brooks/Cole, 1986.

2020 Mathematics Subject Classification: Primary 11P70; Secondary 11B13, 05A99. Keywords: subset sum, finite abelian group.

(Concerned with sequences \underline{A006125}, \underline{A053601}, and \underline{A123903}.)

Received December 23 2024; revised versions received December 31 2024; February 11 2025; December 5 2025; December 8 2025. Published in Journal of Integer Sequences, December 10 2025.

Return to Journal of Integer Sequences home page.