Modular Schur numbers

Modular Schur numbers Jonathan Chappelon∗ Institut de Math´ematiques et de Mod´elisation de Montpellier Universit´e Montpellier 2, France [email protected] Mar´ıa Pastora Revuelta Marchena Mar´ıa Isabel Sanz Dom´ınguez Departamento de Matem´atica Aplicada I Escuela T´ecnica Superior de Ingenier´ıa de Edificaci´on Universidad de Sevilla, Spain {pastora,isanz}@us.es Submitted: May 21, 2012; Accepted: Jun 18, 2013; Published: Jun 30, 2013 Mathematics Subject Classifications: 05C55, 05D10, 11A07, 05A17, 11P81, 11P83 Abstract For any positive integers land m, a set of integers is said to be (weakly) l-sum- free modulo mif it contains no (pairwise distinct) elements x1, x2, . . . , xl, y satisfying the congruence x1+. . . +xl≡ymod m. It is proved that, for any positive integers kand l, there exists a largest integer nfor which the set of the first npositive integers {1,2, . . . , n}admits a partition into k(weakly) l-sum-free sets modulo m. This number is called the generalized (weak) Schur number modulo m, associated with kand l. In this paper, for all positive integers kand l, the exact value of these modular Schur numbers are determined for m= 1, 2 and 3. Keywords: modular Schur numbers; Schur numbers; weak Schur numbers; sumfree sets; weakly sum-free sets 1 Introduction In [8], Guy proposed two unsolved problems in elementary number theory. The first one is the Schur’s problem of partitioning integers into sum-free classes (Problem E12). Schur proved in [13] that if the set of the first k!epositive integers is partitioned into kparts any way, then x+y=zcan be solved in integers within one part. Let S(k) be the largest ∗Part of this work was carried out during a short postdoctoral research visit at the Instituto de Matem´aticas de la Universidad de Sevilla Antonio de Castro Brzezicki (IMUS). the electronic journal of combinatorics 20(2) (2013), #P61 1 integer nsuch that there exists a partition of the first npositive integers {1,2, . . . , n}into kparts with no solution to the equation x+y=z, in any part. The exact value of S(k) is known only for k∈ {1,2,3,4}and the Problem E12 is to determine it for k⩾5. The second unsolved problem proposed by Guy is a modular version of this Schur’s problem (Problem E13). It was posed by Abbott and Wang in [2]. Let T(k) be the largest integer nsuch that there exists a partition of {1,2, . . . , n}into k parts, with no solution to the congruence x+y≡z(mod n+ 1), in any part. Abbott and Wang determined that T(k) = S(k) for k∈ {1,2,3,4}, and they conjectured that the equality is true for all positive integers k. The main purpose of this paper is to study and explicitly determine modular generalizations of Schur numbers. 1.1 Modular generalized Schur numbers Let kbe a positive integer and let Sbe a set of integers. A k-partition of Sis a set P={S1, . . . , Sk}of subsets of Ssuch that any element of Sis contained in exactly one element of P. Let lbe a positive integer. A set of integers is said to be l-sum-free if it contains no elements x1, . . . , xl, y satisfying x1+. . . +xl=y. For every positive integer k, the generalized Schur number S(k, l) is the largest integer nfor which the set of the first npositive integers {1,2, . . . , n}admits a k-partition into l-sum-free sets. For l= 2, the numbers S(k, 2) = S(k) are known as Schur numbers. They have been introduced by Schur himself in 1916 [13], in order to study a modular version of the Fermat’s Last Theorem. He proved that those numbers are always finite, for every positive integer k. The first few Schur numbers are given in Table 1. k1 2 3 4 5 6 7 S(k, 2) 1 4 13 44 160 ⩽· · · ⩽305 ⩾536 ⩾1680 Table 1: The first few Schur numbers S(k, 2). The exact value of S(4,2) was obtained by Baumert [1]. The lower and upper bounds of S(5,2) are due to Exoo [6] and Sanz [12], respectively. Finally, the lower bounds of S(6,2) and S(7,2) were obtained by Fredricksen and Sweet [7] by considering symmetric sum-free partitions. the electronic journal of combinatorics 20(2) (2013), #P61 2 Many generalizations of Schur numbers have appeared since their introduction. In this paper, the generalized Schur numbers that we consider are similarly defined in [3, 10]. These numbers are always finite (see [11, 10] for instance). Let mbe a positive integer. A set of integers is said to be l-sum-free modulo mif it contains no elements x1, . . . , xl, y satisfying x1+. . . +xl≡y(mod m). For every positive integer k, the generalized Schur number modulo m, denoted by Sm(k, l), is the largest integer nfor which the set of the first npositive integers {1,2, . . . , n}admits ak-partition into l-sum-free sets modulo m. Obviously, for every modulus m, the inequality Sm(k, l)⩽S(k, l) (1) holds because a l-sum-free set modulo mof integers is also l-sum-free. Moreover, since m+. . . +m≡mmod m, a l-sum-free set of integers modulo mdoes not contain the integer m. Therefore, we have Sm(k, l)⩽m−1.(2) For l= 2, Abbott and Wang investigated in [2] the numbers T(k) = max {n∈N|Sn+1(k, 2) = n}, where kis a positive integer. They obtained that T(k) = S(k, 2) for k∈ {1,2,3,4}and they conjectured that the equality is true for all positive integers k. In this paper, we explicitly determine the modular generalized Schur numbers Sm(k, l) for small values of m: for all moduli m∈ {1,2,3}. For m= 1, the result is clear. Indeed, S1(k, l)=0, for all k⩾1 and l⩾1, since every positive integer xverifies x+. . . +x≡xmod 1 and thus, there does not exist non-empty l-sum-free set modulo 1. For m= 2 and m= 3, the exact values of Sm(k, l) are given by the following theorems. Theorem 1.1. Let kand lbe two positive integers. Then, S2(k, l) = 0for lodd, 1for leven. Theorem 1.2. Let kand lbe two positive integers. Then, S3(k, l) =    0for k⩾1and l≡1 mod 3, 1for k= 1 and l≡0,2 mod 3, 2for k⩾2and l≡0,2 mod 3. A simple proof of these theorems will be provided in Section 2. the electronic journal of combinatorics 20(2) (2013), #P61 3 1.2 Modular generalized weak Schur numbers A set of integers is said to be weakly l-sum-free if it contains no pairwise distinct elements x1, . . . , xl, y satisfying x1+. . . +xl=y. For every positive integer k, the generalized weak Schur number WS(k, l) is the largest integer nfor which the set of the first npositive integers {1,2, . . . , n}admits a k-partition into weakly l-sum-free sets. For l= 2, the numbers WS(k, 2) are called weak Schur numbers. The first few weak Schur numbers are given in Table 2. k1 2 3 4 5 6 WS(k, 2) 2 8 23 66 ⩾196 ⩾575 Table 2: The first few weak Schur numbers WS(k, 2). The exact value of WS(4,2) was obtained by Blanchard, Harary and Reis [4]. The lower bounds of WS(5,2) and WS(6,2) are due to Eliahou, Mar´ın, Revuelta and Sanz [5]. More generally, the generalized weak Schur numbers are always finite (see [14, 9, 10] for instance). Moreover, the generalized weak Schur numbers appear as a good upper bound for the generalized Schur numbers, since a weakly l-sum-free set of integers is also l-sum-free. Therefore, we have S(k, l)⩽WS(k, l),(3) for all positive integers kand l. A trivial lower bound for the weak Schur numbers is kl ⩽WS(k, l),(4) because each of the kweakly sum-free sets can contain ldistinct integers without solution of the equation x1+. . . +xl=y. Better lower bounds for WS(k, l) can be found in [12]. A set of integers is said to be weakly l-sum-free modulo mif it contains no pairwise distinct elements x1, . . . , xl, y satisfying x1+. . . +xl≡y(mod m). For every positive integer k, the generalized weak Schur number modulo m, denoted by WSm(k, l), is the largest integer nfor which the set of the first npositive integers {1,2, . . . , n}admits a k-partition into weakly l-sum-free sets modulo m. For every modulus m, the inequality WSm(k, l)⩽WS(k, l) (5) holds because a weakly l-sum-free set modulo mof integers is also weakly l-sum-free. Abbott and Wang conjectured that T(k) is equal to S(k, 2), for all positive integer k. Here, in the weak case, it appears that considering similar numbers than T(k) is without the electronic journal of combinatorics 20(2) (2013), #P61 4 great interest. Indeed, as we can see in Table 3 for m∈ {1,...,15}, the values of modular generalized weak Schur numbers, for k= 2 and l= 2, seem to be very difficult to predict. For m⩾16, we have WSm(2,2) = WS(2,2) because WSm(2,2) ⩽WS(2,2) = 8 and because, for two distinct integers x, y ∈ {1,...,8}, we always have x+y⩽15 < m. m1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 WSm(2,2) 4 5 4 5 6 6 7 6 7 7 7 8 8 8 8 Table 3: The modular generalized weak Schur numbers WSm(2,2) In this paper, we explicitly determine the modular generalized weak Schur numbers WSm(k, l) for small values of m: for all moduli m∈ {1,2,3}. For m= 1, we obtain that WS1(k, l) = kl, for all k⩾1 and l⩾1, since a weakly l-sum-free set modulo 1 has cardinality of at most lbecause every l+ 1 distinct positive integers x1, . . . , xl, y verify x1+. . . +xl≡ymod 1. For m= 2 and m= 3 the following theorems will be proved in Section 4 and Section 5 respectively. Theorem 1.3. Let kand lbe two positive integers. Then, WS2(k, l) =                l+ 1 for k= 1 and l≡0,1 mod 4, lfor k= 1 and l≡2,3 mod 4, 2(k−1)l+ 1 for k⩾2and leven, k(l+ 1) for k⩾2and l≡1 mod 4, k⩾2even and l≡3 mod 4, k(l+ 1) −1for k⩾3odd and l≡3 mod 4. Theorem 1.4. Let kand lbe two positive integers. Then, WS3(k, l) =                                3kfor k⩾1and l= 1, lfor k= 1 and l⩾2, 2l+ 2 for k= 2 and l⩾2, l ≡0,1,5 mod 9, 2l+ 1 for k= 2 and l= 3, l⩾5, l ≡2,3,4,6,7,8 mod 9, 2lfor k= 2 and l∈ {2,4}, 3(k−2)l+ 2 for k⩾3and l≡0,2 mod 3, k(l+ 1) for k= 3, k ⩾5and l⩾2, l ≡1 mod 3, k= 4 and l⩾2, l ≡1,7 mod 9, 4l+ 3 for k= 4 and l≡4 mod 9. 1.3 Contents This paper is organized as follows. A simple proof of Theorems 1.1 and 1.2 is given in Section 2, which completely determines the exact value of the generalized Schur numbers the electronic journal of combinatorics 20(2) (2013), #P61 5 modulo 2 and 3. In Section 3, several basic results on the projection of partitions of integers in Z/mZ, which will be useful in our proofs in the sequel, are introduced. The generalized weak Schur numbers modulo 2 are obtained by proving Theorem 1.3 in Section 4 and the case m= 3 is settled in Section 5 by proving Theorem 1.4. Remark that Theorems 1.3 and 1.4 are the most difficult results to prove in this paper, much more difficult than Theorems 1.1 and 1.2 whose proofs, in Section 2, are direct. Finally, in Section 6, we discuss open problems. 2Sm(k, l)for the moduli m= 2 and m= 3 We begin this section by proving Theorem 1.1, that is, S2(k, l) = 0 for k⩾1 and lodd, 1 for k⩾1 and leven. Proof of Theorem 1.1. Let kand lbe two positive integers. As already remarked in Section 1, the inequality S2(k, l)⩽1 holds. Moreover, since Pl i=1 1 = l, it follows that the integer 1 belongs to a sum-free set of integers modulo 2 if and only if lis even. We end with the proof of Theorem 1.2, that is, S3(k, l) =    0 for k⩾1 and l≡1 mod 3, 1 for k= 1 and l≡0,2 mod 3, 2 for k⩾2 and l≡0,2 mod 3. Proof of Theorem 1.2. Let kand lbe two positive integers. Since Pl i=1 1 = l, it follows that the integer 1 belongs to a l-sum-free set of integers modulo 3 if and only if l≡0 or 2 mod 3. Thus, we have S3(k, l) = 0 when l≡1 mod 3. Since Pl i=1 1 = l≡2 mod 3 for l≡2 mod 3 and Pl−1 i=1 1+2 = l+1 ≡1 mod 3 for l≡0 mod 3, it follows that the integers 1 and 2 cannot belong together to a l-sum-free set of integers modulo 3 when l≡0 or 2 mod 3. Therefore S3(1, l) = 1 for k= 1 when l≡0 or 2 mod 3. Finally, if k⩾2 and l≡0 or 2 mod 3, then S3(k, l)⩽2 as remarked in Section 1 and S3(k, l)⩾2 because the sets {1}and {2}are both l-sum-free modulo 3. This leads to the formula S3(k, l) = 2 in this case. 3 Projective partitions in Z/mZ Throughout this paper, projections of partitions into Z/mZwill be considered. Let πm:Z−→ Z/mZ denote the canonical projection map. Let Sbe a set of integers and let P={S1, . . . , Sk} be a k-partition of S. Denote by πm(P) the projection of the partition Pof S, that is the partition πm(P) = {πm(S1), . . . , πm(Sk)}of the multiset πm(S) of Z/mZ. the electronic journal of combinatorics 20(2) (2013), #P61 6 For example, if we consider the partition P={{1,2,4,8},{3,5,6,7}} of the set S={1,...,8}, then we obtain that π2(P) = {{1,0,0,0},{1,1,0,1}} is a partition of the multiset π2(S) = {0,0,0,0,1,1,1,1}of Z/2Z. As for sets of integers, a multiset of Z/mZis said to be (weakly) l-sum-free if it contains no (pairwise distinct) elements x1, . . . , xl, y satisfying x1+. . . +xm=yin Z/mZ. Proposition 3.1. A set Sof integers is (weakly) l-sum-free modulo mif and only if its projection πm(S)is a (weakly) l-sum-free multiset of Z/mZ. Remark that the partition P, of the previous example, is a partition of Sinto weakly 2-sum-free sets but it is not a partition of Sinto weakly 2-sum-free sets modulo 2 since π2(P) is not a partition of π2(S) into weakly 2-sum-free multisets in Z/2Z. Indeed, in each element of π2(P), we have three distinct elements satisfying either 0 + 0 = 0 or 1 + 1 = 0 in Z/2Z. For every multiset Mof Z/mZ, denote by mM:Z/mZ−→ N the multiplicity function associated with M, that is the function which assigns to each element x∈Z/mZits multiplicity in M. Let |M|denote the cardinality of the multiset M, that is the number of elements constituting M, counted with multiplicity, that is |M|=X x∈Z/mZ mM(x)∈N. Obviously, by πn, each k-partition of a set of npositive integers can be associated uniquely with a k-partition of a multiset of nterms in Z/mZ, counted with multiplicity. Conversely, this process is not bijective in general. Indeed, distinct partitions of the same set of integers can be projected on the same partition in Z/mZ. Proposition 3.2. Let mand nbe two positive integers and let S={1,2, . . . , n}. The exact number of k-partitions P={S1, . . . , Sk}of Sthat have the same projective kpartition πm(P) = {πm(S1), . . . , πm(Sk)}is equal to m−1 Y v=0 k Y u=1 Pk w=umπm(Sw)(v) mπm(Su)(v)= m−1 Y v=0 Pk w=1 mπm(Sw)(v) mπm(S1)(v),mπm(S2)(v),...,mπm(Sk)(v), where a b1,b2,...,bkis the multinomial coefficient a! b1!b2!···bk!. the electronic journal of combinatorics 20(2) (2013), #P61 7 Proof. Consider the euclidean division of nby m, that is n=qm +r. Let εbe the function defined by ε:Z/mZ−→ {0,1}where ε(v) = 1 for v∈ {1, . . . , r}and ε(v)=0 for v∈ {0, r + 1, . . . , m −1}. Thus there is exactly q+ε(v) integers in {1, . . . , n}whose residue class modulo mis v∈Z/mZ. We proceed by induction on u. Suppose that we have already chosen the integers in the first u−1 sets of the k-partition P. For the set Su, we have to choose, for every v∈Z/mZ,mπm(Su)(v) integers among the remaining q+ε(v)−Pu−1 w=1 mπm(Sw)(v) integers whose residue class modulo mis v. This corresponds to the binomial coefficient q+ε(v)−Pu−1 w=1 mπm(Sw)(v) mπm(Su)(v)=Pk w=umπm(Sw)(v) mπm(Su)(v). This completes the proof. For example, the number of 2-partitions Pof {1,...,8}whose projection in Z/2Zis the partition π2(P) = {{1,0,0,0},{1,1,1,0}} is equal to 16, since (4 3·4 1)·(4−3 1·4−1 3) = 4·4 = 16. These 16 partitions are given below. {{1,2,4,6},{3,5,7,8}},{{1,2,4,8},{3,5,7,6}},{{1,2,6,8},{3,5,7,4}}, {{1,4,6,8},{3,5,7,2}},{{3,2,4,6},{1,5,7,8}},{{3,2,4,8},{1,5,7,6}}, {{3,2,6,8},{1,5,7,4}},{{3,4,6,8},{1,5,7,2}},{{5,2,4,6},{1,3,7,8}}, {{5,2,4,8},{1,3,7,6}},{{5,2,6,8},{1,3,7,4}},{{5,4,6,8},{1,3,7,2}}, {{7,2,4,6},{1,3,5,8}},{{7,2,4,8},{1,3,5,6}},{{7,2,6,8},{1,3,5,4}}, {{7,4,6,8},{1,3,5,2}}. 4WSm(k, l)for the modulus m= 2 The goal of this section is to prove Theorem 1.3, that is, WS2(k, l) =                l+ 1 for k= 1 and l≡0,1 mod 4, lfor k= 1 and l≡2,3 mod 4, 2(k−1)l+ 1 for k⩾2 and leven, k(l+ 1) for k⩾2 and l≡1 mod 4, k⩾2 even and l≡3 mod 4, k(l+ 1) −1 for k⩾3 odd and l≡3 mod 4. The proof of Theorem 1.3 is based on the following two lemmas. Lemma 4.1. For any weakly l-sum-free multiset Mof Z/2Z, with |M|⩾1, we have 1. mM(0) ⩽l. 2. mM(1) ⩽lif lis odd. 3. |M|⩽l+ 1 if |M∩Z/2Z|= 2. the electronic journal of combinatorics 20(2) (2013), #P61 8 Proof. 1. Since Pl i=1 0 = 0, the multiset Mcannot contain more than lterms 0 ∈Z/2Z. 2. Suppose that lis odd, that is π2(l) = 1. Since Pl i=1 1 = π2(l) = 1, the multiset M cannot contain more than lelements 1 ∈Z/2Z. 3. Suppose that M={0,1, x1, . . . , xl}is a weakly l-sum-free multiset of Z/2Zwith cardinality |M|=l+ 2. Since the sum of the lelements Pl i=1 xiis equal to either 0 or 1, which are both contained in M\ {x1, . . . , xl}, we obtain a contradiction. Remark. For leven, a multiset only constituted by elements 1 ∈Z/2Z, with any cardinality |M|⩾1, is always weakly l-sum free in Z/2Zsince Pl i=1 1 = π2(l) = 0. Lemma 4.2. Let M={x1, . . . , xl+1}be a multiset of Z/2Zwith cardinality |M|=l+ 1. Then, Mis weakly l-sum-free if and only if Pl+1 i=1 xi= 1. Proof. First, by definition, the multiset Mis weakly l-sum-free if and only if, for every 1⩽j⩽l+ 1, the inequality Pl+1 i=1,i6=jxi6=xjholds. Moreover, since l+1 X i=1 i6=j xi6=xjfor all 1 ⩽j⩽l+ 1 ⇐⇒ l+1 X i=1 xi6= 2xj= 0 for all 1 ⩽j⩽l+ 1 ⇐⇒ l+1 X i=1 xi= 1, the result follows. We are now ready to prove Theorem 1.3, the main result of this section. 4.1 For k= 1 Let k= 1 and let lbe a positive integer. We will prove that WS2(1, l) = l+ 1 for l≡0,1 mod 4, lfor l≡2,3 mod 4. Claim 4.3. WS2(1, l)∈ {l, l + 1}for all positive integers l. Proof. Since a multiset of lelements in Z/2Zis always weakly l-sum-free, the inequality WS2(1, l)⩾lholds. Moreover, from Lemma 4.1, we know that a weakly l-sum-free multiset Msuch that |M∩Z/2Z|= 2 has cardinality of at most l+ 1. Therefore WS2(1, l)⩽l+ 1. Claim 4.4. Let S={1,2, . . . , l + 1}. Then, the multiset π2(S)is weakly l-sum-free if and only if l≡0or 1 mod 4. the electronic journal of combinatorics 20(2) (2013), #P61 9 MmM(0) mM(1) mM(2) |M| S1(l+ 1)/3 2(l+ 1)/3 0 l+ 1 S2(l+ 1)/3 0 2(l+ 1)/3l+ 1 π3(S) 2(l+ 2)/3 2(l+ 2)/3 2(l+ 2)/3 2l+ 2 This proves that WS3(2, l)⩾2l+ 2 for all l≡5 mod 9. Case 1.2: if mπ3(S)(0) + 1 = mπ3(S)(1) = mπ3(S)(2) ≡1 mod 3. Then, 2l+ 2 = mπ3(S)(0) + mπ3(S)(1) + mπ3(S)(2) ≡2 mod 9 and thus l≡0 mod 9. We can verify with Lemma 5.2 that the following 2-partition of π3(S) is weakly l-sum-free in this case. MmM(0) mM(1) mM(2) |M| S1l/3 2l/3 + 1 0 l+ 1 S2l/3 0 2l/3+1 l+ 1 π3(S) 2l/3 2l/3 + 1 2l/3 + 1 2l+ 2 This proves that WS3(2, l)⩾2l+ 2 for all l≡0 mod 9. Case 2: if only one of the multisets S1and S2contains elements 0 ∈Z/3Z. Without loss of generality, we can suppose that this is S1. Then, we have S1∩Z/3Z= {0, a}and S2∩Z/3Z={a, 2a}with a∈ {1,2} ⊂ Z/3Z. By Lemma 5.2, we know that the multisets S1and S2are weakly l-sum-free if and only if Px∈S1x= 2.2a=aand Px∈S2x= 2.0 = 0. It follows that mS1(a)≡1 mod 3 and mS2(a)≡mS2(2a) mod 3. This implies that mπ3(S)(a) = mS1(a) + mS2(a)≡1 + mS2(2a) = 1 + mπ3(S)(2a) (mod 3). Since mπ3(S)(1) = mπ3(S)(2) or mπ3(S)(1) = mπ3(S)(2) + 1 by definition of the set S, we deduce that a= 1 and mπ3(S)(1) = mπ3(S)(2) + 1. Moreover, by definition of the set S again, we have mπ3(S)(0) = mπ3(S)(2) = mπ3(S)(1) −1. Then 2l+ 2 = mπ3(S)(0) + mπ3(S)(1) + mπ3(S)(2) = 3mπ3(S)(0) + 1 ≡1 mod 3 and thus l≡1 mod 3. It follows that 2 ≡l+ 1 = mS2(1) + mS2(2) ≡2.mS2(2) = 2.mπ3(S)(2) mod 3. Therefore mπ3(S)(0) = mπ3(S)(2) = mπ3(S)(1) −1≡1 (mod 3). Then 2l+ 2 = mπ3(S)(0) + mπ3(S)(1) + mπ3(S)(2) ≡4 mod 9 and thus l≡1 mod 9. We can verify with Lemma 5.2 that the following 2-partition of π3(S) is weakly l-sum-free in this case. MmM(0) mM(1) mM(2) |M| S1(2l+ 1)/3 (l+ 2)/3 0 l+ 1 S20 (l+ 2)/3 (2l+ 1)/3l+ 1 π3(S) (2l+ 1)/3 (2l+ 4)/3 (2l+ 1)/3 2l+ 2 the electronic journal of combinatorics 20(2) (2013), #P61 16 This proves that WS3(2, l)⩾2l+ 2 for all l⩾2, l≡1 mod 9. This completes the proof that WS3(2, l)⩾2l+ 2 if and only if l≡0,1,5 mod 9. Claim 5.8. WS3(2, l)⩾2l+ 1 for l⩾9. Proof. Let S={1,2,...,2l+ 1}. We will prove that there exists a partition of π3(S) into 2 weakly l-sum-free multisets. Consider the euclidean division of l⩾9by3:l= 3q+r where q⩾3 and r∈ {0,1,2}. Then, l+ 1 = 3q+r+ 1 and 2l+ 1 = 6q+ 2r+ 1 and π3(S) is a multiset of Z/3Zwhose multiplicity function verifies that mπ3(S)(1) ⩾2q+ 1,mπ3(S)(2) ⩾2qand mπ3(S)(0) ⩾2q. First, we prove that there exists a submultiset S1with |S1|=l+ 1 which is weakly l-sum- free. The multiset S1is defined below by its multiplicity function, distinguishing different cases depending on the residue class of qmodulo 3. π3(q)mS1(0) mS1(1) mS1(2) 0q+r2q+ 1 0 1q+r+ 2 2q−1 0 2q+r+ 1 2q0 Case 1: for q≡0 mod 3. The multiset S1is well defined because mS1(0) = q+r⩽2q⩽mπ3(S)(0) and mS1(1) = mπ3(S)(1). Moreover, it is weakly l-sum-free by Lemma 5.2 since X x∈S1 x= (q+r).0 + (2q+ 1).1 = π3(2q+ 1) = 1 = 2.2. Case 2: for q≡1 mod 3. Remark that q⩾4 in this case. The multiset S1is well defined because mS1(0) = q+r+ 2 ⩽2q⩽mπ3(S)(0) and mS1(1) = 2q−1⩽2q+ 1 ⩽mπ3(S)(1). Moreover, it is weakly l-sum-free by Lemma 5.2 since X x∈S1 x= (q+r+ 2).0 + (2q−1).1 = π3(2q−1) = 1 = 2.2. Case 3: for q≡2 mod 3. The multiset S1is well defined because mS1(0) = q+r+1 ⩽2q⩽mπ3(S)(0) and mS1(1) = 2q⩽2q+ 1mπ3(S)(1). Moreover, it is weakly l-sum-free by Lemma 5.2 since X x∈S1 x= (q+r+ 1).0 + (2q).1 = π3(2q)=1=2.2. Finally, if S2is the multiset, with cardinality l, constituted by all the other elements of π3(S)\S1, then S2is clearly weakly l-sum-free and we have obtained a weakly l-sum-free 2-partition of π3(S). the electronic journal of combinatorics 20(2) (2013), #P61 17 Thus, by Claim 5.6, Claim 5.7 and Claim 5.8, we have already proved that WS3(2, l) = 2l+ 2 for l≡0,1,5 mod 9, 2l+ 1 for l⩾9, l ≡2,3,4,6,7,8 mod 9. It remains to settle the cases l∈ {2,3,4,6,7,8}. Claim 5.9. WS3(2,2) ⩽4. Proof. Let S={1,2,3,4,5}. Then π3({1,2,3,4,5}) = {0,1,1,2,2}. In any 2-partition of π3(S) there is one multiset with cardinality of at least 3. Since the submultisets {0,1,1}, {0,1,2},{0,2,2},{1,1,2}and {2,2,1}are not weakly 2-sum-free in Z/3Z, it follows that there is no weakly 2-sum-free 2-partition of π3(S). Therefore WS3(2,2) ⩽4. So, from Claim 5.6 and Claim 5.9, we obtain that WS3(2,2) = 4. Claim 5.10. WS3(2,4) ⩽8. Proof. Let S={1,2,3,4,5,6,7,8,9}. Then π3(S) = {0,0,0,1,1,1,2,2,2}. In any 2- partition of π3(S) there is one multiset with cardinality of at least 5. Since a weakly 4-sum-free multiset with cardinality of 5 contains exactly 2 different terms of Z/3Zby Lemma 5.1 and since the submultisets {0,0,1,1,1},{0,0,0,1,1},{1,1,1,2,2},{1,1,2,2,2},{0,0,2,2,2},{0,0,0,2,2} are not weakly 4-sum-free in Z/3Zby Lemma 5.2, it follows that there is no weakly 4-sum-free 2-partition of π3(S). Therefore WS3(2,4) ⩽8. Thus, from Claim 5.6 and Claim 5.10, we obtain that WS3(2,4) = 8. Claim 5.11. WS3(2, l)⩾2l+ 1 for l∈ {3,6,7,8}. Proof. Let S={1,2,...,2l+ 1}. We can verify by using Lemma 5.2 that the following partition P={S1, S2}of π3(S) is weakly l-sum-free. l= 3 : MmM(0) mM(1) mM(2) |M| S10 2 2 4 S22 1 0 3 π3(S) 2 3 2 7 l= 6 : MmM(0) mM(1) mM(2) |M| S13 4 0 7 S21 1 4 6 π3(S) 4 5 4 13 l= 7 : MmM(0) mM(1) mM(2) |M| S14 4 0 8 S21 1 5 7 π3(S) 5 5 5 15 the electronic journal of combinatorics 20(2) (2013), #P61 18 l= 8 : MmM(0) mM(1) mM(2) |M| S15 4 0 9 S20 2 6 8 π3(S) 5 6 6 17 Finally, by Claim 5.7 and Claim 5.11, we deduce that WS3(2, l) = 2l+1 for l∈ {3,6,7,8}. This concludes the proof of Theorem 1.4 in this case. 5.3 For k⩾3and l≡0,2 mod 3 Let k⩾3 and lbe two positive integers, with l≡0 or 2 mod 3. We will prove that WS3(k, l) = 3(k−2)l+ 2. Claim 5.12. WS3(k, l)⩽3(k−2)l+ 2 for k⩾3and l≡0,2 mod 3. Proof. Let S={1,2,...,3(k−2)l+ 3}. Suppose that there exists a partition P= {S1, . . . , Sk}of π3(S) into kweakly l-sum-free multisets in Z/3Z. First, we prove that |Si|⩽l+ 1, for all 1 ⩽i⩽k. From the definition of π3(S), we know that mπ3(S)(x) = (k−2)l+ 1, for all x∈Z/3Z. Since mSi(0) ⩽l, for all 1⩽i⩽k, by Lemma 5.1 and Pk i=1 mSi(0) = mπ3(S)(0) = (k−2)l+ 1, it follows from the pigeonhole principle that there are at least k−1 multisets Sicontaining at least one element 0 ∈Z/3Z. Moreover, by Lemma 5.1 again, a weakly l-sum-free multiset Sifor which mπ3(Si)(0) ⩾1 has cardinality of at most l+1. Therefore, if the number of multisets Sifor which mSi(0) ⩾1 is k, we have |Si|⩽l+ 1, for all 1 ⩽i⩽k. In the other case, if the number of multisets Sifor which mSi(0) ⩾1 is exactly k−1, we can also prove that the kth multiset has cardinality of at most l+ 1. Indeed, if we suppose that mSi(0) ⩾1, for all 1 ⩽i⩽k−1, and mSk(0) = 0 with |Sk|⩾l+ 2, then Sk∩Z/3Z={a}with a∈ {1,2} ⊂ Z/3Zby Lemma 5.1. Thus, since l+2 = mπ3(Sk)(a)⩽mπ3(S)(a)=(k−2)l+1, it follows that k⩾4. Then, 2((k−2)l+ 1) −(k−1)(l+ 1) = 2kl −4l+ 2 −kl +l−k+ 1 =kl −3l−k+ 3 = (k−3)l−(k−3) = (k−3)(l−1) >0. Therefore 2((k−2)l+1) >(k−1)(l+1). Moreover, since Sk∩Z/3Z={a}, the 2((k−2)l+1) elements 0 and 2aof π3(S) must be in S1∪S2∪· · ·∪Sk−1. But we know that |Si|⩽l+1, for all 1 ⩽i⩽k−1, in contradiction with 2((k−2)l+ 1) >(k−1)(l+ 1). We have proved that, in every cases, we have |Si|⩽l+ 1, for all 1 ⩽i⩽k. We deduce that 3((k−2)l+ 1) = |π3(S)|⩽k(l+ 1). the electronic journal of combinatorics 20(2) (2013), #P61 19 Finally, since 3((k−2)l+ 1) −k(l+ 1) = 3kl −6l+ 3 −kl −k = 2kl −6l−k+ 3 =k(2l−1) −3(2l−1) = (k−3)(2l−1), we obtain that 3((k−2)l+1) > k(l+1) for k⩾4, in contradiction with |π3(S)|⩽k(l+1). For k= 3, we have |S1|=|S2|=|S3|=l+ 1. Since mπ3(S)(0) = l+ 1 > l, it follows from Lemma 5.1 that the number of multisets Sicontaining elements 0 ∈Z/3Zis at least of two. It is exactly two because if each multiset Sicontains elements 0 ∈Z/3Z, then there is a weakly l-sum-free multiset Siwhich contains all the elements of Z/3Zand with |Si|=l+1, in contradiction with Lemma 5.1. So we deduce that the partition Pis either of the form S1∩Z/3Z=S2∩Z/3Z={0, a}and S3∩Z/3Z={2a}, or of the form S1∩Z/3Z={0, a}, S2∩Z/3Z={0,2a}and S3∩Z/3Z={a, 2a}, where a∈ {1,2} ⊂ Z/3Zand |S1|=|S2|=|S3|=l+ 1. For the first form, we know from Lemma 5.2 that S1and S2are weakly l-sum-free if and only if Px∈S1x=Px∈S2x=a, that is, if and only if mS1(a)≡mS2(a)≡1 mod 3. It follows that l+ 1 = mπ3(S)(a) = mS1(a) + mS2(a)≡2 (mod 3), and thus l≡1 mod 3, in contradiction with the hypothesis that l≡0 or 2 mod 3. For the second form, we know from Lemma 5.2 that S1and S2are weakly l-sum-free if and only if Px∈S1x=aand Px∈S2x= 2a, that is, if and only if mS1(a)≡mS2(a)≡1 mod 3. Moreover, we have mS2(2a) = l+ 1 −mS3(2a) = mS3(a). It follows that l+ 1 = mπ3(S)(a) = mS1(a) + mS3(a) = mS1(a) + mS2(2a)≡2 (mod 3), and thus l≡1 mod 3, in contradiction with the hypothesis that l≡0 or 2 mod 3. This concludes the proof. Claim 5.13. WS3(k, l)⩾3(k−2)l+ 2 for k⩾3and l≡0,2 mod 3. Proof. Let S={1,2,...,3(k−2)l+ 2}. We consider the following partition P= {S1, . . . , Sk}of π3(S) and we prove that it is weakly l-sum-free. MmM(0) mM(1) mM(2) |M| S10 (k−2)l+ 1 0 (k−2)l+ 1 S20 0 (k−2)l+ 1 (k−2)l+ 1 S3, . . . , Skl0 0 l π3(S) (k−2)l(k−2)l+ 1 (k−2)l+ 1 3(k−2)l+ 2 the electronic journal of combinatorics 20(2) (2013), #P61 20 First, Pis a partition of π3(S) since the multiplicity functions verify that Pk i=1 mSi(x) = mπ3(S)(x) for all x∈Z/3Z. The multisets S1and S2are weakly l-sum-free because, as already remarked above, a multiset which is only constituted by elements 1 or 2 ∈Z/3Z is always weakly l-sum-free when l≡0,2 mod 3. For S3, . . . , Sk, multisets containing only lelements are always weakly l-sum-free in Z/3Z. This completes the proof. 5.4 For k⩾3and l≡1 mod 3 Let k⩾3 and l⩾2 be two positive integers, with l≡1 mod 3. We will prove that WS3(k, l) =    k(l+ 1) for k= 3, k ⩾5 and l⩾2, l ≡1 mod 3, k= 4 and l⩾2, l ≡1,7 mod 9, 4l+ 3 for k= 4 and l≡4 mod 9. Claim 5.14. WS3(k, l)⩽k(l+ 1) for k⩾1and l⩾2, l ≡1 mod 3. Proof. Directly follows from Lemma 5.1. Claim 5.15. Let l≡1 mod 3. Let Mbe a multiset of Z/3Zsuch that |M∩Z/3Z|= 2 and |M|=l+ 1. Then, Mis weakly l-sum-free if and only if mM(x)≡1 mod 3 for all x∈M∩Z/3Z. Proof. Suppose that M∩Z/3Z={a, b}with a6=b. First, since l≡1 mod 3, it follows that mM(a) + mM(b) = l+ 1 ≡2 (mod 3). Thus either mM(a)≡mM(b)≡1 mod 3 or mM(a)≡0 mod 3 and mM(b)≡2 mod 3. Suppose that mM(a)≡0 mod 3 and mM(b)≡2 mod 3. We know, by Lemma 5.2, that X x∈M x=mM(a).a +mM(b).b = 2.2(a+b) = a+b. This leads to the equality 2b= 0.a + 2.b =mM(a).a +mM(b).b =a+b, in contradiction with a6=b. This completes the proof. Claim 5.16. WS3(k, l)⩾WS3(k−3, l) + 3(l+ 1) for k⩾4and l≡1 mod 3. Proof. Let S={1,2,...,WS3(k−3, l)}. Let P={S1, . . . , Sk−3}be a partition of π3(S) into weakly l-sum-free multisets of Z/3Z. Consider the multisets Sk−2,Sk−1and Skof Z/3Zdefined below by their multiplicity function. MmM(0) mM(1) mM(2) |M| Sk−2l1 0 l+ 1 Sk−10l1l+ 1 Sk1 0 l l + 1 Sk−2∪Sk−1∪Skl+ 1 l+ 1 l+ 1 3(l+ 1) the electronic journal of combinatorics 20(2) (2013), #P61 21 Then P0={S1, . . . , Sk}is a partition of the multiset π3(S0) = π3({1,2,...,WS3(k−3, l)+ 3(l+1)}) since Pk i=1 mSi(x) = mπ3(S)(x)+(l+1) = mπ3(S0)(x) for all x∈Z/3Z. Moreover, since l≡1 mod 3, it follows that the multisets Sk−2,Sk−1and Skare weakly l-sum-free in Z/3Zby Lemma 5.2 and Claim 5.15. Therefore WS3(k, l)⩾WS3(k−3, l) + 3(l+ 1) for all k⩾4 and l≡1 mod 3. Claim 5.17. WS3(3, l)⩾3(l+ 1) for l≡1 mod 3. Proof. Let S={1,2,...,3(l+ 1)}. The following 3-partition P={S1, S2, S3}of π3(S) is weakly l-sum-free, as already seen in the proof of Claim 5.16. MmM(0) mM(1) mM(2) |M| S1l1 0 l+ 1 S20l1l+ 1 S31 0 l l + 1 π3(S)l+ 1 l+ 1 l+ 1 3(l+ 1) This completes the proof. Let kbe a positive integer and let S={1,2, . . . , k(l+ 1)}. In the sequel of this section, suppose that there exists a partition P={S1, . . . , Sk}of π3(S) into kweakly l-sum-free multisets of Z/3Z. By Lemma 5.1, |Si|=l+ 1 and |Si∩Z/3Z|= 2 for all 1 ⩽i⩽k. For every x∈Z/3Z, denote by nxthe number of multisets Siin Psuch that x∈Si∩Z/3Z. For Si∩Z/3Z={a, b}, the multiset Siis weakly l-sum-free if and only if mSi(a)≡mSi(b)≡1 (mod 3) by Lemma 5.2 and Claim 5.15. It follows that nx∈ {1, . . . , k}and nx≡mπ3(S)(x) (mod 3), for all x∈Z/3Z. We distinguish different cases depending on the value of kand the residue class of lmodulo 9. Claim 5.18. WS3(5, l)⩾5(l+ 1) for l≡4 mod 9. Proof. Consider the euclidean division of lby 9, that is l= 9r+ 4. Then, 5(l+ 1) = 5(9r+ 5) = 45r+ 25 = 3(15r+ 8) + 1 and n0≡mπ3(S)(0) = 15r+ 8 ≡2 (mod 3), n1≡mπ3(S)(1) = 15r+ 9 ≡0 (mod 3), n2≡mπ3(S)(2) = 15r+ 8 ≡2 (mod 3). We deduce that n0, n2∈ {2,5}and n1= 3. Moreover, we have n0+n1+n2= 10. For n0= 5, n1= 3 and n2= 2, we can verify by using Lemma 5.2 and Claim 5.15 that the following partition of π3(S) is weakly l-sum-free. the electronic journal of combinatorics 20(2) (2013), #P61 22 MmM(0) mM(1) mM(2) |M| S19r+ 4 1 0 l+ 1 S23r+ 1 6r+ 4 0 l+ 1 S31 9r+ 4 0 l+ 1 S43r+ 1 0 6r+ 4 l+ 1 S51 0 9r+ 4 l+ 1 π3(S) 15r+ 8 15r+ 9 15r+ 8 5(l+ 1) This completes the proof. Claim 5.19. WS3(5, l)⩾5(l+ 1) for l≡7 mod 9. Proof. Consider the euclidean division of lby 9, that is l= 9r+ 7. Then, 5(l+ 1) = 5(9r+ 8) = 45r+ 40 = 3(15r+ 13) + 1 and n0≡mπ3(S)(0) = 15r+ 13 ≡1 (mod 3), n1≡mπ3(S)(1) = 15r+ 14 ≡2 (mod 3), n2≡mπ3(S)(2) = 15r+ 13 ≡1 (mod 3). We deduce that n0, n2∈ {1,4}and n1∈ {2,5}. Moreover, we have n0+n1+n2= 10. For n0=n2= 4 and n1= 2, we can verify by using Lemma 5.2 and Claim 5.15 that the following partition of π3(S) is weakly l-sum-free. MmM(0) mM(1) mM(2) |M| S13r+ 1 6r+ 7 0 l+ 1 S20 9r+ 7 1 l+ 1 S39r+ 7 0 1 l+ 1 S43r+ 4 0 6r+ 4 l+ 1 S51 0 9r+ 7 l+ 1 π3(S) 15r+ 13 15r+ 14 15r+ 13 5(l+ 1) This completes the proof. Claim 5.20. WS3(4, l)⩾4(l+ 1) for l≡1 mod 9. Proof. Consider the euclidean division of lby 9, that is l= 9r+ 1. Then, 4(l+ 1) = 4(9r+ 2) = 36r+ 8 = 3(12r+ 2) + 2 and n0≡mπ3(S)(0) = 12r+ 2 ≡2 (mod 3), n1≡mπ3(S)(1) = 12r+ 3 ≡0 (mod 3), n2≡mπ3(S)(2) = 12r+ 3 ≡0 (mod 3). the electronic journal of combinatorics 20(2) (2013), #P61 23 We deduce that n0= 2 and n1=n2= 3. Moreover, we have n0+n1+n2= 8. We can verify by using Lemma 5.2 and Claim 5.15 that the following partition of π3(S) is weakly l-sum-free. MmM(0) mM(1) mM(2) |M| S16r+ 1 3r+ 1 0 l+ 1 S26r+ 1 0 3r+ 1 l+ 1 S30 6r+ 1 3r+ 1 l+ 1 S40 3r+ 1 6r+ 1 l+ 1 π3(S) 12r+ 2 12r+ 3 12r+ 3 4(l+ 1) This completes the proof. Claim 5.21. WS3(4, l)=4l+ 3 for l≡4 mod 9. Proof. Consider the euclidean division of lby 9, that is l= 9r+ 4. Then, 4(l+ 1) = 4(9r+ 5) = 36r+ 20 = 3(12r+ 6) + 2 and n0≡mπ3(S)(0) = 12r+ 6 ≡0 (mod 3), n1≡mπ3(S)(1) = 12r+ 7 ≡1 (mod 3), n2≡mπ3(S)(2) = 12r+ 7 ≡1 (mod 3). We deduce that n0= 3 and n1, n2∈ {1,4}. Moreover, n1, n26= 1 since mπ3(S)(1) = mπ3(S)(2) = 12r+ 7 > l + 1. Thus n0= 3 and n1=n2= 4 in contradiction with n0+n1+n2= 8. This proves that WS3(4, l)⩽4l+ 3 for l≡4 (mod 9). Finally, from Claim 5.16 and Claim 5.4, we deduce that WS3(4, l)⩾WS3(1, l)+3(l+1) = 4l+ 3. This completes the proof. Claim 5.22. WS3(7, l)⩾7(l+ 1) for l≡4 mod 9. Proof. Consider the euclidean division of lby 9, that is l= 9r+ 4. Then, 7(l+ 1) = 7(9r+ 5) = 63r+ 35 = 3(21r+ 11) + 2 and n0≡mπ3(S)(0) = 21r+ 11 ≡2 (mod 3), n1≡mπ3(S)(1) = 21r+ 12 ≡0 (mod 3), n2≡mπ3(S)(2) = 21r+ 12 ≡0 (mod 3). We deduce that n0∈ {2,5}and n1, n2∈ {3,6}. Moreover, we have n0+n1+n2= 14. Since mπ3(S)(0) = 21r+ 11 >18r+ 8 = 2l, it follows that n0= 5. For n0= 5, n1= 6 and n2= 3, we can verify by using Lemma 5.2 and Claim 5.15 that the following partition of π3(S) is weakly l-sum-free. the electronic journal of combinatorics 20(2) (2013), #P61 24 MmM(0) mM(1) mM(2) |M| S19r+ 4 1 0 l+ 1 S29r+ 4 1 0 l+ 1 S33r+ 1 6r+ 4 0 l+ 1 S41 9r+ 4 0 l+ 1 S51 0 9r+ 4 l+ 1 S60 6r+ 1 3r+ 4 l+ 1 S70 1 9r+ 4 l+ 1 π3(S) 21r+ 11 21r+ 12 21r+ 12 7(l+ 1) This completes the proof. Claim 5.23. WS3(4, l)⩾4(l+ 1) for l≡7 mod 9. Proof. Consider the euclidean division of lby 9, that is l= 9r+ 7. Then, 4(l+ 1) = 4(9r+ 8) = 36r+ 32 = 3(12r+ 10) + 2 and n0≡mπ3(S)(0) = 12r+ 10 ≡1 (mod 3), n1≡mπ3(S)(1) = 12r+ 11 ≡2 (mod 3), n2≡mπ3(S)(2) = 12r+ 11 ≡2 (mod 3). We deduce that n0∈ {1,4}and n1=n2= 2. Since mπ3(S)(0) = 12r+ 10 >9r+ 7 = l, it follows that n0= 4. For n0= 4 and n1=n2= 2, we can verify by using Lemma 5.2 and Claim 5.15 that the following partition of π3(S) is weakly l-sum-free. MmM(0) mM(1) mM(2) |M| S13r+ 4 6r+ 4 0 l+ 1 S23r+ 1 6r+ 7 0 l+ 1 S33r+ 4 0 6r+ 4 l+ 1 S43r+ 1 0 6r+ 7 l+ 1 π3(S) 12r+ 10 12r+ 11 12r+ 11 4(l+ 1) This completes the proof. Finally, we obtain that WS3(k, l) = k(l+ 1) for all k⩾3 and l⩾2, with l≡1 mod 3, except for k= 4 and l≡4 mod 9, by combining Claim 5.14, Claim 5.16, Claim 5.17, Claim 5.18, Claim 5.19, Claim 5.20, Claim 5.22 and Claim 5.23. This concludes the proof of Theorem 1.4. the electronic journal of combinatorics 20(2) (2013), #P61 25