/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 8 (2015) 417-423
The multisubset sum problem for finite abelian groups
Amela Muratovic-Ribic
University of Sarajevo, Department of Mathematics, Zmaja od Bosne 33-35, 71000 Sarajevo, Bosnia and Herzegovina
Qiang Wang *
School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6, Canada
Received 28 October 2013, accepted 29 August 2014, published online 11 June 2015
Abstract
We use a similar techique as in [2] to derive a formula for the number of multisubsets of a finite abelian group G with any given size and any given multiplicity such that the sum is equal to a given element g G G. This also gives the number of partitions of g into a given number of parts over a finite abelian group.
Keywords: Composition, partition, subset sum, polynomials, finite fields, character, finite abelian groups.
Math. Subj. Class.: 11B30, 05A15, 20K01, 11T06
1 Introduction
Let G be a finite abelian group of size n and D be a subset of G. The well known subset sum problem in combinatorics is to decide whether there exists a subset S of D which sums to a given element in G. This problem is an important problem in complexity theory and cryptography and it is NP-complete (see for example [3]). For any g G G and i a positive integer, we let the number of subsets S of D of size i which sum up to g be denoted by
N(D, i, g) = #{S C D : #S = i, £ s = g}.
ses
* Research is partially supported by NSERC of Canada.
E-mail addresses: amela@pmf.unsa.ba (Amela Muratovic-Ribic), wang@math.carleton.ca (Qiang Wang) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
418
Ars Math. Contemp. 8(2015)381-408
When D has more structure, Li and Wan made some important progress in counting these subset sums by a sieve technique [3, 4]. Recently Kosters [2] gives a shorter proof of the formula obtained by Li and Wan earlier, using character theory.
N (G,i,g) = n £	£ M(s/d)#G[d],
i	\ i/s I
s|gcd(exp(G),i)	V 1 7 d|gcd(e(g),s)
where exp(G) is the exponent of G, e(g) = max{d : d | exp(G),g G dG}, ^ is the Mobius function, and G[d] = {h G G : dh = 0} is the d-torsion of G.
More generally, we consider a multisubset M of D. The number of times an element belongs to M is the multiplicity of that member. We define the multiplicity of a multisubset M is the largest multiplicity among all the members in M. We denote
M(D, i, j, g) = #{multisubset M of D : multiplicity(M) < j, #M = i, £ s = g}.
seM
It is an interesting question by its own to count M(D, i, j, g), the number of multisubsets of D of cardinality i which sum to g where every element is repeated at most j times. If j = 1, then M(D, i, j, g) = N(D, i, g). If j > i, this problem is also equivalent to counting partitions of g with at most i parts over D, which is M(D, i, i, g). In this case we use a simpler notation M(D, i, g) because the second i does not give any restriction.
Another motivation to study the enumeration of multisubset sums is due to a recent study of polynomials of prescribed ranges over a finite field. Indeed, through the study of enumeration of multisubset sums over finite fields [5], we were able to disprove a conjecture of polynomials of prescribed ranges ove a finite field proposed in [1]. Let Fq be a finite field of q elements and F* be the cyclic multiplicative group. When D is Fq (the additive group) or F*, counting the multisubset sum problem is the same as counting partitions over finite fields, which has been studied earlier in [6].
In this note, we use the similar method as in [2] to obtain M(D, i, j, g) when D = G. However, we work in a power series ring instead of a polynomial ring.
Theorem 1. Let G be a finite abelian group of size n and let g G G, i, j G Z with i > 0 and j > 1. For any s | n, we define
c (n,j)= £ (-1)f/s V - 1)( "T"
fc>0,o<t< n gcd(s,j + D ,	V	J V
Then we have
M(G, i, j, g) = 1 £ C(n, i, j, s) £ M(s/d)#G[d].
s|gcd(exp(G),i)	d|gcd(s,e(g))
where exp(G) is the exponent of G, e(g) = max{d : d | exp(G),g G dG}, ^ is the Mobius function, and G[d] = {h G G : dh = 0} is the d-torsion of G.
As a corollary, we obtain the main theorem in [2] when j = 1.
A. Muratovic-Ribic, Q. Wang: The multisubset sum problem for.
419
Corollary 1. (Theorem 1.1 in [2]) Let G be a finite abelian group of size n and let g G G and i G Z. Then we have
N(G,i,g) = n £ (-i)^	£ p(s/d)#G[d].
^^	\ i/S I
s|gcd(exp(G),i)	V 1 7 d|Scd(s,e(g))
where exp(G) is the exponent of G, e(g) = max{d : d | exp(G),g G dG}, p is the Mobius function, and G[d] = {h G G : dh = 0} is the d-torsion of G.
Moreover, when j > i, the formula gives the number of partitions of g with at most i parts over a finite abelian group. To avoid confusion the multiset consisting of ai,...,o„ is denoted by {{a1?..., an}}, with possibly repeated elements, and by {a1;..., an} the usual sets. We define a partition of the element g G G with exactly i parts in D as a multiset {{a1; a2,..., a,i}} such that all ak's are nonzero elements in D and
ai + a2 + ... + ai = g.
Then the number of these partitions is denoted by PD (i, g), i.e.,
Pd(i,g) = |{{ai, a2,. .., ai}} C D : ai + a2 + ... + ai = g, ai,. .., ai = 0 j .
It turns out M(D, i, g) = ^k=o PD(k, g) is the number of partitions of g G G with at most i parts in D.
Corollary 2. Let G be a finite abelian group of size n and let g G G. Then the number of partitions of g over G with at most i parts is
n E (n/s+//s -1) E p(s/d)#G[d]. n z—' V i/s / ^—'
s|gcd(exp(G),i) V	1	7 d|gcd(s,e(g))
where exp(G) is the exponent of G, e(g) = max{d : d | exp(G),g G dG}, p is the Mobius function, and G[d] = {h G G : dh = 0} is the d-torsion of G.
Proof. The number is M (G, i, j, g) when j > i > 0. If j > i, then the linear Diophantine equation sk +1 • lcm(s, j + 1) = i reduces to sk = i and t = 0. The rest of proof follows immediately.	□
In Section 2, we prove our main theorem and derive Corollary 1 as a consequence. In Section 3, we extend our study to a subset of a finite abelian group and make a few remarks on how to obtain the number of partitions over any subset of a finite abelian group.
2 Proof of Theorem 1
To make this paper self-contained, we recall the following lemmas (see Lemmas 2.1-2.4 in [2]). Let G be a finite abelian group of size n. Let C be the field of complex numbers and G = Hom(G, C*) be the group of characters of G. Let x G G and x be the conjugate character which satisfies x(g) = x(g) = x(-g) for all g G G. We note that a character x can be naturally extended to a C-algebra morphism x : C[G] ^ C on the group ring C[G].
Lemma 1. Let a = £ G agg G C[G]. Then we have ag = n Exea xt(g)x(a).
420
Ars Math. Contemp. 8(2015)381-408
Lemma 2. Let m be a positive integer and g G G. Then
x(g) = ¿9emG#G[mi
xeo,xm=1
where SgemG is 1 if g G mG and it is zero otherwise.
Lemma 3. Let x G G be a character and m be its order. Then we have
n (1 - x(a)Y) = (1 - Ym)n/m.
aeo
Lemma 4. Let g G G. The number e(g) is equal to lcm{d : d | exp(G), g G dG}. For d | exp(G) we have g G dG if and only if d | e(g).
Let us present the proof of Theorem 1. We use the multiplicative notation for the group.
Proof. Fix j > 1. Working in the power series ring C[G][[X]] over the group ring, the generating function of ^geG M(G, i, j, g)g is
i _ ffj+iyj+1
]T (G, i, j, g)gX4 = n(1+aX+• • ^ Xj) = fl 1_gX G C[G][[X]].
i=0 geo	aeo	aeo
Using Lemma 1, we write
£ M(G,i,j,g)Xi = 1 £ x(g) n jj.
i=0	xeo	aeo	AV '
Separating the first sum on the right hand side, we obtain
£ M<G,i„„,* = n £ £ x(g) n jj.
i=0	s|exp(o) xeo,ord(x)=s aeo	y
For each fixed x of the order s, we know that xj+1 has the order gcd(sSj+1). Therefore by Lemma 3, we simplify the above as follows:
n gcd(s,j + 1)
^	1 ___^	/1 _ Xlcm(s ,j+1)\ s
£ M (G,i ^g)* = - £	£	X(g)^- - X s )n/s-. (2.1)
l=0	s | exp(o) xeo,ord(x)=s
Note that
J2 ^ = J2 J2 x(g^
xe-<o,xs = 1	dls xeo,ord(x) = d
By Lemma 2 and the Mobius inversion formula, we obtain
X^g^X^ M(s/d)	M(s/d)^gedo#G[d].
xeo,ord(x) = s	dls	xeo,xd = 1	dls
A. Muratovic-Ribic, Q. Wang: The multisubset sum problem for.
421
Because d | s | exp(G), by Lemma 4, g G dG if and only if d | e(g). Hence
E X(g)= E M(s/d)^sedG#G[d] = E M(s/d)#G[dj.
XeO,ord(x)=s	d|s	d|gcd(s,e(g))
Plugging this into Equation (2.1), we get
n gcd(s,j + 1)
œ	1	i\_ Xlcm(s,j + in s
EM(G,i,j,g)Xi = n E E M(s/d)#G[dP— Xs n/s-.
i=0	s | exp(G) dlgcd(s,e(g))	(	)
By applying the binomial theorem to the right hand side and comparing coefficients of X1 in both sides, we single out M (G, i, j, g) and obtain
M (G, i, j, g) = — E E M(s/d)#G[d]G (n,i,j,s). -
s|exp(G) d|gcd(s,e(g))
After bringing C(n, i, j, s) out of the inner sum we complete the proof.	□
Finally we remark that we can derive Corollary 1 using N (G, i, g) = M (G, i, 1, g). When j = 1, let us consider sk +t • lcm(s, j + 1) = sk + t • lcm(s, 2) = i. If s is even, we obtain sk + st = i and thus k +t = i/s. Note that we have the following power series expansions
1 _e r-/s+k - v
(1 - x)n/s	V k J
v ' k=0 v 7
2n/s	, . *
(1 - x)2n/s =E (-!)'(2-/s)
t = 0 V /
and
n/s / / (1 - x)«/s = EE ((-1)^
j = 0
Now we compare the coefficients of the term xi/s in both sides of
1	)2n/
(1 - xs)2n/s = (1 - xs)n
(1 - xs)n/s
after expanding these power series. Hence we obtain
C(„„ 1,.)=	(-1).("/S +k- 1)(2"/s) = (-i)./.(«/;).
k>0,0<t<2n/s
Moreover, C(n, i, 1, s) = (-1)i+i/s(n/ss) because i is even.
Similarly, if s is odd, we obtain sk + 2st = i and thus k + 2t = i/s. Moreover, i + i/s is even. Using
(1 - x2s)n/s--= (1 + xs)n/s,
V	y (1 - Xs)n/s V	y '
x~ .
422
Ars Math. Contemp. 8(2015)381-408
we obtain
Y^ f-iW n/s + k - ^ fn/^ = r-iv+i/s^n/s
C (n'i' 1'a)= (-1)V k ){t) W
k>0,0<t<n/s
3 A few remarks
In this section we study M(D, i, j, g) where j > i and D is a subset of G. We recall that in this case we use the notation M(D, i, g) because j does not really put any restriction. First of all, we note that
œ	1	œ
EE M (G \{0},i,g)gX4 = ft ^^ = (1 - X ) EE M (G,i,g)gX
i=0 g£G	ct£G,CT=0	i=0 g£G
By Corollary 2, we obtain
M (G \{0},i,g)
1
n
f e (n/s+;/•-1) e m(s/d)#g[d]
\s|gcd(exp(G),i)	d|gcd(s,e(g))
e (n/s - o e .(s/d)*«^.
s|gcd(exp(G),i-1) V	V	"	7 d|gcd(s,e(g))	/
We note M(G \ {0}, i, g) = PG(i, g). Therefore we obtain an explicit formula for the number of partitions of g into i parts over G. More generally, let D = G \ S, where S = {u1, u2,..., «|S|} = 0. Denote by Ms(G, i, g) the number of multisubsets of G of sizes i that contain at least one element from S. Then the number of multisubsets of D = G \ S with i parts which sum up to g is equal to
M(G \ S, i, g) = M(G, i, g) - Ms(G, i, g).
Note that M(G, 0,0) = 1 and M(G, 0, s) =0 for any s G G \ {0}. The principle of inclusion-exclusion immediately implies that Ms(G, i, g) is given in the following formula. We note that the formula is quite useful when the size of S is small in order to compute M(G \ S, i, g).
Proposition 1. For all i = 1, 2,... and g G G we have
Ms (G, i, g) = E M (G, i - 1,g - u) - ...
«es
+(-1)t-1 E M (G, i - t, g - (ui + U2 + ... + ut)) + ...
{«1,U2,...,«t }CS
+ (-1)i-2 E M (G, 1, g - (ui + U2 + ... + Ui-i))+
{ui,«2,...,»i-i}CS
(-1)i-i E M (G, 1, g - (ui + U2 + ... + Ui)).
{«1 ,«2,...,«i }CS
A. Muratovic-Ribic, Q. Wang: The multisubset sum problem for.
423
Proof. Fix an element g G G. Denote by A the family of all the multisubsets of G with i parts which sum up to g and each multisubset also contains the element u. The principle of the inclusion-exclusion implies that
|Uu£s Au | = £ |Au|- £ | Aui nAu21 + ...	(3.1)
uES	|ui,u2|CS
It is obvious to see |AUl n Au21 = M (G, i - 2, g - (ui + u2)) etc. by definition and the result follows directly.	□
Acknowledgements
We thank anonymous referees for their helpful suggestions. References
[1]	A. Gacs, T. Heger, Z. L. Nagy, D. Palvolgyi, Permutations, hyperplanes and polynomials over finite fields, Finite Field Appl. 16 (2010), 301-314.
[2]	M. Kosters, The subset problem for finite abelian groups, J. Combin. Theory Ser. A 120 (2013), 527-530.
[3]	J. Li and D. Wan, On the subset sum problem over finite fields, Finite Field Appl. 14 (2008), 911-929.
[4]	J. Li and D. Wan, Counting subset sums of finite abelian groups, J. Combin. Theory Ser. A 119 (2012), no. 1, 170-182.
[5]	A. Muratovic-Ribic and Q. Wang, On a conjecture of polynomials with prescribed range, Finite Field Appl. 18 (2012), no. 4, 728-737.
[6]	A. Muratovic-Ribic and Q. Wang, Partitions and compositions over finite fields, Electron. J. Combin. 20 (2013), no. 1, P34, 1-14.