ON FACTORIZATION IN BLOCK MONOIDS FORMED BY $\{\bar{1},\bar{a}\}$ IN $\mathbb{Z}_{n}$

Size: px

Start display at page:

Download "ON FACTORIZATION IN BLOCK MONOIDS FORMED BY $\{\bar{1},\bar{a}\}$ IN $\mathbb{Z}_{n}$"

磐贡
1 years ago
Views:

1 Proceedigs of the Ediburgh Mathematical Society (2003) 46, c DOI:0.07/S Prited i the Uited Kigdom ON FACTORIZATION IN BLOCK MONOIDS FORMED BY {, ā} IN Z SCOTT T. CHAPMAN AND WILLIAM W. SMITH 2 Triity Uiversity, Deartmet of Mathematics, 75 Stadium Drive, Sa Atoio, TX , USA (schama@triity.edu) 2 The Uiversity of North Carolia at Chael Hill, Deartmet of Mathematics, Chael Hill, NC , USA (wwsmith@ .uc.edu) (Received 8 March 2002) Abstract We cosider the factorizatio roerties of block mooids o Z determied by subsets of the form S a = {, ā}. We deote such a block mooid by B a(). I 2, we rovide a method based o the divisio algorithm for determiig the irreducible elemets of B a(). Sectio 3 offers a method to determie the elasticity of B a() based solely o the cross umber. Sectio 4 alies the results of 3 to ivestigate the comlete set of elasticities of Krull mooids with divisor class grou Z. Keywords: block mooid; elasticity of factorizatio; Krull mooid 2000 Mathematics subject classificatio: Primary 20M4; 20D60; 3F05. Itroductio This aer deals with factorizatio roerties of certai block mooids, ad we start with some otatio ad termiology. Let G be a abelia grou writte additively, G 0 = G {0}, ad let { } F(G) = v g Z + {0} g G 0 g vg be the multilicative free abelia mooid with basis G 0. Give F F(G), we write F = g G 0 g vg(f ). The block mooid over G is defied by { } B(G) = B F(G) v g (B)g =0. g G 0 Note that the emty block acts as the idetity i B(G). I geeral, give S G 0,weset B(G, S) ={B B(G) v g (B) =0forg G 0 \ S}. 257

2 258 S. T. Chama ad W. W. Smith A summary of some basic facts about block mooids ca be foud i [6]. The articular block mooids i which we have a iterest ca be described as follows. Let ad a be itegers with >2, <a<ad set ā = a + Z i Z/Z = Z.IfS a = {, ā}, the B(Z,S a )={ u ā v where u, v 0 ad u + av = t with t>0}. For ease of otatio, let B a () =B(Z,S a ). I a recet aer, the first author ad Aderso [2] exlored the ossible elasticities of a Krull domai D with divisor class grou Z.IfS is the subset of Z \{0} which cotais the height-oe rime ideals of D, the it is well kow that the factorizatio roerties of D relatig to legths of factorizatios are idetical to those of B(Z,S) (see [3] for a exlaatio). Our iterest i the mooids B a () stems from their use i [2]. I articular, the mooids B a () are itrisic i arguig the followig: while there is a Krull domai with divisor class grou Z 3 with elasticity 3 5 ad aother with elasticity 3 7, there is o Krull domai with divisor class grou Z 3 with elasticity strictly betwee 3 5 ad 3 7. Metio of the mooids B a () i the literature is ot isolated to [2]. I [5], Geroldiger gives a elegat characterizatio of the irreducible blocks i B a () usig cotiued fractios. I 2 we start by offerig a alterate characterizatio of these irreducible blocks based o the divisio algorithm. We the aly this characterizatio i 3ad4to study cocets related to the legths of factorizatios of elemets i B a () ito irreducible elemets. I 3 we show that the elasticity of B a () ism a (), where m a () is the miimum value obtaied by the Zaks Skula fuctio (see [4]) o B a (). I 4we comute this elasticity for various values of a ad cosider the comlete set of elasticities of the B a () for a fixed value of with 2 a. We the secialize these results to the case where is a rime iteger. We fiish, i 4, with a argumet which geeralizes the observatio metioed earlier i [2] for Krull domais with divisor class grou Z 3. I articular, for a odd rime 3, we show that there is o B a () with elasticity strictly betwee 2. Irreducibles i B a () 2 ( +) ad 4 ( +3). Geroldiger [5] rovides a descritio of the irreducibles i B a (). Here we give a alterate descritio of the irreducibles. Followig the otatio of [5] for 2, <a, ad u 0, let B u = { u ā x where x 0 ad u + ax = t with t>0}. ad the set B(u) = u ā v, where v = mi{x u ā x B u }. It is easily see (as i [5]) that if B is irreducible i B a (), the B = B(u) for some u (the coverse is ot true). Proositio 8 of [5] determies for each u the value of v i B(u). Proositio 0 of [5] the rovides a remarkable ecessary ad sufficiet coditio for B(u) to be irreducible. The values of u for which B(u) is irreducible are determied by a algorithm ivolvig the covergets of the cotiued fractio of the multilicative iverse of a modulo.

3 Factorizatio i block mooids o Z 259 We rovide a alterate descritio of the irreducibles by classifyig the irreducibles as oe of the followig two tyes. Tye : u ā v with 0 u<a. Tye 2: u ā v with a u. Settig d = gcd (a, ), we itroduce the followig otatio. For k a/d write (by the Divisio Algorithm) k = aq k + r k with 0 r k <a. This rocess yields a sequece of remaiders r,r 2,...,r w ad a sequece of blocks where w = a/d. r ā q,..., rw ā qw, ( ) Theorem 2.. With the otatio give above, the irreducible blocks of B a () ca be described as follows. (a) Tye blocks: rkā q k, where r k <r i for each i<k. (b) Tye 2 blocks: u ā v, where u + av = ad v is a iteger with 0 v /a. Proof. First we rove (a). Note that for B(u) ay block of the form u ā v with 0 u<a, we have u + av = k. IfB(u) is irreducible it must be the case that k a/d. Sice 0 u<awe have u = r k ad v = q k. Hece, all irreducible blocks of tye lie i the sequece ( ). For a block rkāq k take from ( ), we show that if there is a i<kwith r i r k, the it is reducible. We have i = aq i + r i, k = aq k + r k. Sice i q i = ad q k = a we kow that q k q i. Assumig r k r i yields k, a (k i) = a(q k q i )+(r k r i ) ad, i fact, rkāq k = ri ā qi r k iā q k i. Now suose for rkāq k that r k <r i for each i<k.if rkāq k is reducible, the we write rkāq k = u ā v B, where u ā v is irreducible. So, k = r k + aq k, w = u + av ad (by assumtio) w<k. Hece w<k. Sice u r k <a, by the uiqueess imlied by the Divisio Algorithm, we have that u = r w ad v = q w with w<kad

4 260 S. T. Chama ad W. W. Smith r w r k, cotradictig the assumtio. Hece, the block is irreducible, which cocludes the roof of (a). We ow rove (b). If u ā v is of the give form, the it is clearly irreducible. Now suose u + av = t with t 2 ad a u. Write = aq + r with 0 r<a ( r ā q is a tye irreducible by defiitio). The t = u + av > = r + aq. Thus (t ) =(u r) +a(v q). But t ad r<a u<. It follows that u r>0 ad v q 0 ad that r ā q u r ā v q = u ā v.thust 2 yields that u ā v is reducible ad the imlicatio is established, comletig the roof. We ote the divisio = aq + r,0 r <a, always roduces the first tye irreducible. Also, 0 ā /d is tye ad ā 0 is tye 2. We illustrate this descritio of irreducibles with the followig simle examle. Examle 2.2. The tye irreducibles i B 8 (9) are give by the divisios ()9 = 8(2) + 3, (3)9 = 8(7) +, (8)9 = 8(9) + 0. That is, 3 8 2, 8 7, are the tye irreducible blocks. The tye 2 irreducible blocks are simly ad 8. We use this simle descritio of the irreducibles i the followig sectios, where it will be see that the tye irreducibles lay a critical role i the study of the elasticity of the block mooid B a (). 3. O the elasticity of B a () For B a (), the elasticity is defied as ρ(b a ()) = su{m/ B B = C C m with each B i ad C j irreducible i B a ()}. Geeral backgroud for this cocet ca be foud i []. I [4], the Zaks Skula fuctio is itroduced as a tool for studyig the elasticity. We iterret the otatio ad results of that work i the settig of B a () as follows. For the block B = u ā v, the Zaks Skula costat (or cross umber) for B is give by k(b) =(u + dv)/. Welet ad M a () = max{k(b) B is a irreducible block i B a ()} m a () = mi{k(b) B is a irreducible block i B a ()}. With this otatio, we state the followig as a lemma (see [4, Corollary.]).

5 Lemma 3.. For 2 ad <a, Factorizatio i block mooids o Z 26 max{m a (),m a () } ρ(b a ()) M a() m a (). Obviously, the case a reresets the trivial case where m a () = M a () = ρ(b a ()) =. I this sectio, we establish a efficiet algorithm usig the characterizatio of irreducibles from 2 to calculate the elasticity. I later sectios, we will aalyse for a give the set of elasticities {ρ(b a ()) 2 a }. I articular, i this sectio we will show that M a () = ad that m a () is determied by the tye irreducibles. We first ote for the irreducibles γ = { } ad γ 2 = {ā /d } that k(γ )=k(γ 2 )=. Hece, m a () M a (). It is also easy to see that if B = u ā v is a tye 2 irreducible (i.e. u a ad = u + av), the k(b) = u + dv u + av sice d a. To show k(b) for B is a tye irreducible is slightly more ivolved. Theorem 3.2. For each irreducible block B of B a (), we have that k(b). Thus M a () =ad ρ(b a ()) = m a (). Proof. By the above remark we merely eed to rove the result for the tye irreducibles i B a (). We use the otatio of 2 ad write the irreducible B = rkā q k, where k = aq k + r k ad 0 r k <a.ifr k = 0, the B = 0 ā /d ad k(b) =. Hece, we assume that r k 0.B irreducible imlies for the divisios = aq + r, 2 = aq 2 + r 2,. (k ) = aq k + r k that r k <r i for i =, 2,...,k ad d r j for j k. Notice that the remaiders r,...,r k are distict. To see this, suose that r i = r j with j i < a/d. The i = aq i + r i ad j = aq j + r j imlies that (i j) = a(q i q j ). It follows that a/d divides (i j) ad hece i = j. Sice a dk is the largest ositive iteger less tha a that is itself less tha k distict itegers divisible by d (also less tha a), it follows that r k a dk. Sice k q k = < k a a, if we assume that r k + dq k <a dk +(dk/a), the a( a) <dk( a), a cotradictio. Hece k(b) =(r k + dq k )/ <. Havig established M a () =, we ow tur our attetio to m a (). We show that it is determied by the tye irreducibles with the followig lemma. =,

6 262 S. T. Chama ad W. W. Smith Lemma 3.3. Let B = r ā q be the tye irreducible determied by the divisio = aq + r with 0 r <a. The k(b) k(b i ) for ay tye 2 irreducible B i. Proof. Theorem 2. (b) imlies that tye 2 irreducibles exist if ad oly if a /2. I this case, they are the irreducibles of the form B t = ta ā t where t< /a. Thus k(b t )=( ta + dt)/ ad k(b) =(r + dq )/. The result is established if r + dq ta + dt for t< /a. Sice = aq + r, this iequality reduces to dq aq ta + dt ad hece t(a d) q (a d). Agai, sice we exclude the case a, a d>0 ad q = /a yields the desired iequality. We summarize the results of this sectio i the followig theorem. Let B a() deote the set of all irreducible blocks of tye i B a (). Theorem 3.4. Let a<ad d = gcd (a, ). () If a, the m a () =. (2) If a, the { u + dv m a () = mi } u ā v Ba() <. (3) ρ(b a ()) = m a (). We ote that m a () is ot ecessarily obtaied by r ā q. As a examle, easy calculatios reveal that m (9) is obtaied by r3 ā q3. 4. The set of elasticities For a give iteger, weset P () ={ρ(b a ()) 2 a }. I this sectio, we make some geeral observatios about the set P (). Due to the results of 3, we use a simler otatio ad describe Hece, P () ={(/m) m Mi()}. Mi() ={m a () 2 a<}. Examle 4.. I Examle 2.2, it was show that m (9) = 7 9. Additioal calculatios yield Mi(9) = {2, 3, 4, 5, 7, 0}. Lemma 4.2. The followig statemets are equivalet. () P (). (2) Mi(). (3) is ot rime.

7 Factorizatio i block mooids o Z 263 Proof. This has ofte bee observed earlier, sice ot rime meas there is a divisor a of with 2 a. Theorem 4.3. Let >2 be a ositive iteger. (a) For all we have that 2 Mi(). I fact, 2 = ρ(b a()), where a =. (b) If >3 is a odd iteger, the 3 Mi(). I fact, 3 = ρ(b a()) for a = 2 ( ). (c) If is odd ad a = 2 ( +), the ρ(b a()) = /( 2 ( + )). That is, 2 ( +) Mi(). (d) ρ(b 2 ())=if is eve ad ρ(b 2 ()) = /( 2 ( + )) if is odd. Proof. (a) I this case, = a() + roduces the oly tye irreducible B besides ā ad k(b) =2/. (b) As i the revious case, the fact that = a(2) + imlies that there is oly oe irreducible tye block to cosider with the desired value. (c) For k a wehavek = a(2k )+(a k). Hece, the remaiders a,a 2,..., decrease ad each divisio gives a irreducible B k = a k ā 2k. We ote that gcd (a, ) = ad hece (a k)+(2k ) k(b k )= which is miimal whe k =, where k(b )= a = 2 ( +). = a + k, (d) The statemet for eve is trivial sice 2. For odd, we have the isomorhism of Z give by multilicatio by 2 carries the set S a oto S 2, where a = 2 ( + ). Hece art (c) gives the result. We tur our attetio to describig the set P () for a rime iteger. We discuss this i terms of the set of itegers Mi(), keeig i mid that x Mi() if ad oly if (/x) P (). To motivate these results, we iclude the results of calculatios of Mi() for rimes i the rage 4 59:

8 264 S. T. Chama ad W. W. Smith Mi() 4 {2, 3, 4, 5, 6, 7, 8, 9, 0,, 4, 5, 2} 43 {2, 3, 4, 5, 6, 7, 8, 9, 0,, 3, 5, 22} 47 {2, 3, 4, 5, 6, 7, 8, 9, 0,, 2, 4, 6, 7, 24} 53 {2, 3, 4, 5, 6, 7, 8, 9, 0,, 3, 4, 8, 9, 27} 59 {2, 3, 4, 5, 6, 7, 8, 9, 0,, 2, 3, 4, 5, 7, 20, 2, 30} We ote several roerties of each Mi() already established uder the coditio that is rime i Lemma 4.2 ad Theorem 4.3. The smallest umber i each set is 2, obtaied at a =. For 5, 3 i Mi() is obtaied at a = 2 ( ) ad 2 ( + ) is obtaied at a = 2 ad a = 2 ( + ). A review of the values give i the above table idicates that Mi() begis with a strig of cosecutive itegers ad aears to always have 2 ( + ) as the maximum value with a ga below it. We establish this atter for the geeral case. We require several results from elemetary umber theory whose roofs are left to the reader. Lemma 4.4. Suose 2 ad a is a iteger with <a<. (a) a 2. a (b) If 3 ad 3 a 2 ( ), the 2 a 3 2. a (c) If = aq + r ad 0 r<a, the q + r 2 ( +). Usig our earlier otatio, a immediate corollary of Lemma 4.4 is that 2 ( +) is ideed the maximum elemet of Mi(). Moreover, Mi() {2, 3,..., 2 ( +)} for all rime 3. The ext result establishes that for ay iteger s 2, the values 2, 3,...,s are i Mi() for sufficietly large. Theorem 4.5. {2,...,s} Mi() for all rimes >s 2 s. Proof. Let t = s. We will show that m a () =s for a = t. We use the divisios from 2 to cosider the tye irreducibles. For k < ( t)/t, we have kt<aad k = a(k)+kt. That is, i the otatio of 2, q k = k ad r k = kt. Clearly, r <r 2 < ad the oly tye irreducible formed for k<( t)/t is from the divisio = a() + t ad q + r = t +. The other tye irreducibles will be determied by divisios k = aq k + r k for 0 r k <a with k ( t)/t. However, k = ak + kt ad k ( t)/t imlies kt t = a. Write kt = au + v with 0 v<a, which gives k = a(k + u) +v. Hece q k = k + u ad r k = v. Notig that u, we have q k + r k = k + u + v k + t + t t.

9 Factorizatio i block mooids o Z 265 However, >t+ t 2 yields (/t) >t+. Hece q k + r k >t+. This establishes that ρ(b a ()) is determied by B = r ā q (the block with miimal k(b) value) ad hece m a () =t +. It would seem that the revious result may ot be the best ossible. For examle, it states that {2,...,0} Mi() for all rimes >90. Calculatios idicate that this is actually the case for all rimes 4. I fact, further calculatios show that {2,...,7} Mi(97). We ow tur our attetio to the large values i Mi(). Before doig so, we record the followig result i the sirit of our earlier calculatios. Lemma 4.6. Let >3. (a) If 3, the m 3 () =, Mi() ad ρ(b 3 ())=. (b) If 3, the m 3 () = 3 ( +4), 3 ( +4) Mi() ad ρ(b 3 ()) = 3 ( +4). Proof. The case 3 has already bee established i Theorem 3.4 (). The argumet for 3 cosiders the two cases (mod 3) ad 2 (mod 3). We have used the otatio 3 ( +4) to uify the result, but ote that 3 ( +4) = 3 + whe (mod 3) ad 3 ( +4) = whe 2 (mod 3). Case. (mod 3). I this case =3q + rovides the oly tye irreducible ad q += 3 +. Case 2. 2 (mod 3). Here there are two tye irreducibles give by =3q +2 ad 2 = 3(2q + ) +. The secod yields a quotiet lus remaider value of 2q +2, which is greater tha q + 2 (as >3). Thus the miimum value that gives ρ(b 3 )is q +2= The revious lemma yields that the value 3 ( +4) will be i Mi() for all rimes 5. We will ow show that for all rimes 3, this value is the secod largest value of Mi(). Hece, for 3 there will always be a ga (icreasig i legth as icreases) betwee the two largest values of Mi(), amely 3 ( +4) ad 2 ( + ). This ga was observed for small values of i [2]. Theorem 4.7. Let be a odd rime ad let a be a iteger with 3 a ad a 2 ( +). The m a() 3 ( +4)ad hece ρ(b a ()) 3 ( +4). Proof. We slit the roof ito two cases.

10 266 S. T. Chama ad W. W. Smith Case. Suose that 3 a 2 ( ). If = aq + r with 0 r<a, we will the argue that q + r 3 ( + 4), which imlies that ρ(b a ()) 3 ( +4). Now, q = /a ad r = a /a. Hece q + r = + /a ( a). By Lemma 4.4 (b), sice a<0, ( a) 2 ( ) 2 ( a) = 2 a 3 a 3 (2 ). Therefore, q + r (2 ) = 3 ( + 4). Case 2. Suose that a> 2 (+). For c< 2 ( ) set a = 2 (+)+c = 2 ( +2c + ). We fix c ad cosider all rimes. It is sufficiet to get the result if we kow there exists t so that t = aq t + r t with 0 r t <aad q t + r t 3 ( +4) (i.e. we eed ot be cocered with irreducibility as a irreducible factor will have eve smaller q + r ). Let b =2c + (a odd iteger greater tha or equal to 3) ad b<. First ote that = a()+( a) =a() + 2 ( b) ad q + r = 2 ( b +2) 3 ( +4) wheever 3b + 2. For other rimes >3b +2> 3b, choose k so that b(2k +)=b +2bk < b +2b(k +). ( ) We have the followig idetity (k +) =( 2 ( + b))(2k +)+( 2 ( b(2k + ))). The coditio ( ) gives 0 2 ( b(2k +)) <a= 2 (+b) ad that k + a. Hece, this is the result of the divisio algorithm whe (k+) is divided by a.nowq k+ +r k+ = 2 (2(2k +)+ b(2k + )). We claim that 2 (2(2k +)+ b(2k + )) 3 ( +4) (i.e. 6(2k+)+3 3b(2k+) 2+8 ad hece 3b(2k+) 6(2k+)+8 is eeded). By ( ), b+2b(k+), so we eed oly show b+2b(k+) 3b(2k+) 6(2k+)+8 or b +2bk +2b 6bk +3b 2k + 2 or 0 4bk 2k + 2 or 6k 2bk +. But this is true if b 3, which it is (recall for b = ad c = 0 that a = 2 ( + ), which has elasticity /( 2 ( + ))). We summarize what we have for Z regardig elasticity i terms of the set Mi() (where is rime). The lower ed of the set has cosecutive umbers 2, 3,... (Theorem 4.5). At the other extreme, the largest value is 2 ( + ). The ext ossible value less tha 2 ( +) is 3 ( +4). These are equal for = 3 ad 5 ad differ by oe for = 7 ad. However, for 3 there is a ga betwee these two values ad sice 2 ( +) 3 ( +4)= 6 ( 5), this ga betwee values gets large as icreases i size. We ed this sectio with a alicatio of the above i a slightly more geeral settig. I [2], the followig set of elasticities is cosidered (where is a odd rime): Υ () ={ρ(b(z,s)) S Z \{0}}.

11 I that work, they observed that Factorizatio i block mooids o Z 267 Υ () { 2, 3,...,/( 2 ( + )), }. They also oted there were gas i the sets Υ () for = 3, 7, 9 ad 23. With the simle observatio that ρ(b(z,s T )) max{ρ(b(z,s)),ρ(b(z,t))} ad the fact that ρ(b a ()) = 2 ( +) for a =2 or a = 2 ( + ), we easily use the aalysis of this sectio to coclude that the oly ossible set S that could have ρ(b(z,s)) betwee /( 2 ( + )) ad / 4 ( +3) would be S = {, 2, 2 ( +)}. However, i [2, Lemma 2 (c)] it is show that ρ(z, {, 2, 2 ( +)}) is ot betwee these values. Hece, we have the followig theorem. Theorem 4.8. Let 3 be a rime. There is o subset S Z \{0} with 2 ( +) <ρ(b(z,s)) < 4 ( +3). ( ) Hece, for such a rime, there is o Krull domai D with divisor class grou Z whose elasticity ρ(d) satisfies the iequality ( ). Ackowledgemets. suggestios. The authors thak the referee for may helful commets ad Refereces. D. F. Aderso, Elasticity of factorizatios i itegral domais: a survey, Lecture Notes i Pure ad Alied Mathematics, vol. 89,. 29 (Marcel Dekker, New York, 997). 2. D. F. Aderso ad S. T. Chama, O the elasticities of Krull domais with fiite cyclic divisor class grou, Commu. Alg. 28 (2000), S. T. Chama ad A. Geroldiger, Krull mooids, their sets of legths ad associated combiatorial roblems, Factorizatio i itegral domais, Lecture Notes i Pure ad Alied Mathematics, vol. 89, (Marcel Dekker, New York, 997). 4. S. T. Chama ad W. W. Smith, A aalysis usig the Zaks Skula costat of elemet factorizatios i Dedekid domais, J. Alg. 59 (993), A. Geroldiger, O o-uique factorizatios ito irreducible elemets, II, Colloq. Math. Soc. Jaos Bolyai 5 (987), A. Geroldiger ad F. Halter-Koch, No-uique factorizatios i block semigrous ad arithmetical alicatios, Math. Slovaca 42 (992),

Séminaire Lotharingien de Combinatoire 67 (2012), Article B67c A SYMMETRICAL q-eulerian IDENTITY GUO-NIU HAN, ZHICONG LIN, AND JIANG ZENG Abstract. We

Séminaire Lotharingien de Combinatoire 67 (2012), Article B67c A SYMMETRICAL q-eulerian IDENTITY GUO-NIU HAN, ZHICONG LIN, AND JIANG ZENG Abstract. We Sémiaire Lotharigie de Combiatoire 67 (2012), rticle B67c SYMMETRICL -EULERIN IDENTITY GUO-NIU HN, ZHICONG LIN, ND JING ZENG bstract. We fid a -aalog of the followig symmetrical idetity ivolvig biomial