Carry Groups

Carry Groups Tyler Cook1 ,

Blair Madore2 ,

Erica Miller3 , Tim Pollio4 , Anneliese Spaeth67

Zachariah Riel5 ,

Edited by Zachariah Riel March 1, 2007

1

SUNY Potsdam SUNY Potsdam 3 St. Edwards University 4 Princeton University 5 Kent State University 6 Xavier University 7 We thank Dr. Joel Foisy, SUNY Potsdam, Clarkson University, NSF, and NSA for their support through the Clarkson-Potsdam REU program. 2

Introduction Consider the subset of Z Z2 Z4 Z8 consisting of those elements where all but …nitely many coordinates are zero. We will de…ne an additive operation on this set. Instead of adding these elements in the usual coordinate-wise fashion, we will introduce the notion of "carrying" from the …nite cyclic groups into Z. In the following example, we will add coordinate-wise, but we will carry 1, twice, into the Z coordinate. Here, we carry a 1 into the Z coordinate whenever the sum of the elements of a coordinate exceeds its modulus. Let a +c b denote the least nonnegative residue of a + b, modulo c; let a c b denote the least nonnegative residue of ab, modulo c. For x 2 R, let the ‡oor of x be denoted by bxc. In this example, we "add" (5; 1; 2; 3; 0; 0; :::) and (1; 1; 1; 7; 6; 0; 0; :::) as follows.

= =

( ( ( (

Z 5; 1; 5 + 1 + 2; 8;

Z2 1; 1; 1 +2 1; 0;

Z4 2; 1; 2 +4 1; 3;

Z8 3; 7; 3 +8 7; 2;

Z16 0; 6; 0 +16 6; 6;

0; 0; 0; 0;

::: ::: ::: ::: :::

) ) ) )

The subset of elements, where all but …nitely many coordinates are zero, of Z Z2 Z4 Z8 forms an Abelian group under this additive operation, which will be denoted by . We denote this group by 1 1 1 1 Z Z2 Z4 Z8 ; more precisely, we may denote it by Z Z2 Z4 Z8 , since each time we exceed the modulus of a coordinate when adding two elements, 1 is carried into the Z coordinate. We say this, a3 a4 a1 a2 (or because we also consider in…nitely (and …nitely) generated groups of the form Z Zb1 Zb2 Zb3 an a1 a2 Zbn ). Groups of this type, we will call carry groups. Z Zb1 Zb2 Dr. Jonathan L. King …rst de…ned the carry group Z Z2 Z4 Z8 and claimed that it could be used to solve a problem in ergodic theory concerning the roots of a measure preserving transformation1 . This problem was solved by Dr. Blair Madore2 , though a complete understanding of the structure of this group and its …nitely generated subgroups was not needed for the solution. During the 2001 and 2006 PotsdamClarkson NSF-REU summer programs, Madore and his students have further investigated the structure of carry groups. We will now de…ne carry groups more formally. All of our groups are written additively and all …nite cyclic groups Zn are represented by f0; 1; :::; n 1g. Let (nk ) be a (…nite or in…nite) sequence of positive integers greater than 1. Also, let H be an Abelian group and let (hk ) be a (…nite or in…nite) sequence of elements of H. We de…ne a group with an operation on the Cartesian product H Zn1 Zn2 Zn3 Znm . The operation is de…ned by (a; a1 ; a2 ; a3 ; :::; am ) (b; b1 ; b2 ; b3 ; :::; bm ) = a+b+

m X i=1

hi

ai + bi ; a1 +n1 b1 ; a2 +n2 b2 ; a3 +n3 b3 ; :::; am +nm bm ni

Simply, this is coordinate-wise addition, where hi is carried into the H coordinate if ai +bi we denote this group by H

h1

Zn1

h2

Zn2

h3

Zn3

hm

!

. ni . Conveniently,

Znm

1 J. L. King, The generic transformation has roots of all orders. Dedicated to the memory of Anzelm Iwanik. Colloq. Math. 84/85 part 2, pp 521-547, 2000. 2 B. F. Madore, Rank-one group actions with simple mixing Z subactions, Ph.D. Thesis, University of Toronto, 2000.

1

so that we know we’re using the operation . This also helps so that we can see which elements of H are carried for each coordinate. Note that these groups are …nitely generated. We can similarly de…ne in…nitely generated carry groups. In particular, these groups are de…ned on the subset of H Zn1 Zn2 Zn3 , where all but …nitely many coordinates of the elements are zero. The operation , in this case, is de…ned by (a; a1 ; a2 ; a3 ; :::) (b; b1 ; b2 ; b3 ; :::) = a+b+

1 X

! ai + bi ; a1 +n1 b1 ; a2 +n2 b2 ; a3 +n3 b3 ; ::: . ni

hi

i=1

We’re guaranteed that

P1

i=1 hi

j

ai +bi ni

k

is an element of H, since all but …nitely many coordinates of the h1

h2

h3

elements are zero. We similarly denote this group by H Zn1 Zn2 Zn3 . One can check that these are all Abelian groups; it is tedious, but straightforward. In this paper, for most of our carry groups, we will have H = Z. 2

4

( ( (

Z 2; 1; 9;

Example. Consider (2; 1; 2); (1; 3; 4) 2 Z Z4 Z5 . We compute (2; 1; 2) (1; 3; 4) as follows.

=

2

4

Z4 1; 3; 0;

Z5 2 4 1

) ) )

Example. In the carry group Z Z4 Z5 , consider the element a = (4; 2; 1). We calculate inverse of a, to be a = ( 4 1 1; 4 2; 5 1) = ( 6; 2; 4) ,

a, the

since (4; 2; 1) ( 6; 2; 4) = ( 6; 2; 4) (4; 2; 1) = (0; 0; 0) . a1

In general, given any element (m; m1 ; m2 ; :::; mn ) of the carry group H Zb1 given by (m; m1 ; m2 ; :::; mn ) = (m0 ; m01 ; m02 ; :::; m0n ) , where m0 =

m

X

0

ai and m0i =

bi

1 i n mi 6=0

Now, for (m; m1 ; m2 ; :::; mn ) 2 H

a1

Zb1

a2

an

if if

mi

mi = 0, mi 6= 0,

a2

an

Zbn , the inverse is

for i = 1; :::; n.

Zbn , let the element

(m; m1 ; m2 ; :::; mn ) (m; m1 ; m2 ; :::; mn ) | {z \k" tim es

(m; m1 ; m2 ; :::; mn ) }

be denoted by k (m; m1 ; m2 ; :::; mn ). What does the element k (m; m1 ; m2 ; :::; mn ) look like explicitly? The answer to that question may not be immediately clear. However, a straightforward induction argument will a1 a2 an verify that, given k 2 N and (m; m1 ; m2 ; :::; mn ) 2 H Zb1 Zbn , 0 1 k n X1 X i bj mj + mj k (m; m1 ; m2 ; :::; mn ) = @km + aj ; k b1 m1 ; k b2 m2 ; :::; k bn mn A . ( 1) bj i=0 j=1

Furthermore, let’s …nd an explicit formula for k (m; m1 ; m2 ; :::; mn ). Since we’re working with an Abelian group, we have that k (m; m1 ; m2 ; :::; mn ) = k ( (m; m1 ; m2 ; :::; mn )). For all j = 1; 2; :::; n, let m0j =

0 bj

mj 2

if if

mj = 0, mj 6= 0.

We have that k (m; m1 ; m2 ; :::; mn ) = k ( (m; m1 ; m2 ; :::; mn )) 0

B = kB @ m 0

B = B @ km 0

B B = B km @ 0

B = B @ km 0

X

1 i n mi 6=0

k

C ai ; m01 ; m02 ; :::; m0n C A

X

ai +

X

ai +

X

ai +

i

bj

k X1

X

aj

i

m0j + m0j ;k bj

bj

k X1

X

aj

i

bj

B = B @ km +

X

aj

B = B @ km +

k X1

X

aj

i

i=0 1 j n mj 6=0

i

i=0 1 j n mj 6=0

bj

bj

mj + bj bj

b1

m01 ; k

m0j + m0j ; k bj

(bj

b1

mj ) + bj bj

i=0 1 j n mj 6=0

1 i n mi 6=0 k X1

0

aj

i=0 1 j n m0j 6=0

1 i n mi 6=0

k

k n X1 X i=0 j=1

1 i n mi 6=0

k

1

mj

1 ; k

mj + ( mj ) ; k bj

b1

b2

m02 ; :::; k

m1 ; k

mj

b1

m1 ; k

b2

; k

m1 ; k

b2

b1

bn

1

C m0n C A

m2 ; :::; k

m1 ; k

b2

bn

b2

bn

C C mn C A

m2 ; :::; k

m2 ; :::; k

m2 ; :::; k

1

bn

1

bn

1

1

C mn C A

C mn C A

C mn C A

( 2)

Using ( 1 ) and ( 2 ), we come upon the following proposition. Proposition. Given any nonzero integer d and any (m; m1 ; m2 ; :::; mn ) 2 H d (m; m1 ; m2 ; :::; mn ) 0 $ jdj 1 n X X i sgn (d) = @dm + aj i=0 j=1

bj

% mj + mj sgn (d) ;d bj

b1

m1 ; d

b2

a1

Zb1

a2

m2 ; :::; d

an

bn

Zbn , 1

mn A .

( )

By now, the reader should be a bit more familiar with what we call carry groups and the operation . Now, our aim is to present some theory regarding the structure of these carry groups. For the most part, our classi…cation of these groups is complete. For …nitely generated carry groups, we can surely use the Fundamental Theorem of Finitely Generated Abelian Groups and the Smith Normal Form to …nd their structure. However, our theory provides alternative and interesting methods that yield their structure. We have come upon an understanding of …nitely and in…nitely generated carry groups, which will be discussed in the following sections.

3

Chapter 1

Structure Theory for Finitely Generated Uniform Carry Groups During the summer of 2001, Dr. Blair Madore’s1 NSF-REU group formulated a structure theory for …nitely generated carry groups of the form a

Z Zb1

a

Zb2

a

a

Zbn .

For the sake of simplicity, let’s refer to them as uniform carry groups. We will now state and prove their main results.2 The following fact is trivial. However, it will be used often throughout this paper. It would be best to keep it in mind. Lemma 1.1. If a; b; n 2 Z, 0

a < n, and 0 n

b < n, then

a+b + (a +n b) = a + b. n

(1)

a+b = 1. Also, a +n b = a + b n. Therefore Proof. If a + b n, then 1 a+b n < 2, meaning that n a+b a+b = 0. Hence, n n + (a +n b) = n 1 + (a + b n) = a + b. If a + b < n, then a+b n < 1 so that n a+b n n + (a +n b) = (a +n b) = a + b.

Proposition 1.2. Z Zn = Z.

Proof. De…ne ' : Z Zn ! Z by ' (a; b) = na + b. Let (a1 ; b1 ) ; (a2 ; b2 ) 2 Z Zn . Therefore, ' ((a1 ; b1 ) (a2 ; b2 ))

b1 + b 2 b1 + b 2 ; b1 +n b2 = n a1 + a2 + + (b1 +n b2 ) n n b1 + b 2 (1) = n (a1 + a2 ) + n + (b1 +n b2 ) = n (a1 + a2 ) + (b1 + b2 ) n = ' (a1 ; b1 ) + ' (a2 ; b2 ) . = ' a1 + a2 +

1 SUNY

Potsdam Madore, H. McDonough, C. Miller, D. Van Nort, A. Rogalski, and J. Wood, “Structure Theory for Carry Groups”, Pi Mu Epsilon Journal, Vol. 12 (Fall 2004) 1, 17-25. 2 B.

4

Now, if m 2 Z, then there exist unique integers q and r such that m = nq + r and 0 r < n. Therefore ' (q; r) 7! m so that ' is surjective. Now, if ' (a1 ; b1 ) = ' (a2 ; b2 ) = m, then na1 + b1 = na2 + b2 = m. We know that 0 b1 ; b2 < n. The division algorithm tells us that m has a unique representation of the form nq + r, where 0 r < n. To avoid a contradiction, we must have (a1 ; b1 ) = (a2 ; b2 ). Alternatively, show that j(0; 1)j = 1 and Z Zn = h(0; 1)i.

Proposition 1.3. Z Zm Zn = Z

Proof. De…ne : Z Z Zm Zn . So,

Zm

((a1 ; b1 ; c1 ) (a2 ; b2 ; c2 ))

m

Zn ! Z = = = =

Zn . m

Zn by

(a; b; c) = (ma + b; c). Let (a1 ; b1 ; c1 ) ; (a2 ; b2 ; c2 ) 2

b1 + b2 c1 + c2 + ; b1 +m b2 ; c1 +n c2 m n b 1 + b2 c1 + c2 m a1 + a2 + + + (b1 +m b2 ) ; c1 +n c2 m n c1 + c2 m a1 + a2 + + (b1 + b2 ) ; c1 +n c2 n (ma1 + b1 ; c1 ) (ma2 + b2 ; c2 ) = (a1 ; b1 ; c1 ) (a2 ; b2 ; c2 ) . a1 + a2 +

As in Proposition 1.2, surjectivity and injectivity both follow from the division algorithm.

Proposition 1.4. Z

m

Zn = Z

Zgcd(m;n) .

Proof. As m and n are positive integers, we can surely …nd r; s 2 Z such that m d and 0 < r < n. Now de…ne : Z Zn ! Z Zd by (x; y) = Note that

nx+my d

nx + my ; rx +d sy . d

2 Z since d j m and d j n. Let (a1 ; b1 ) ; (a2 ; b2 ) 2 Z

((a1 ; b1 ) (a2 ; b2 ))

= = = = = = =

a1 + a2 + m n a1 + a2 + m

mr+ns = gcd (m; n) =

(2) m

Zn . We have that

b1 + b 2 ; b1 +n b2 n b1 +b2 n

d

+ m (b1 +n b2 )

b1 + b 2 ; r a1 + a2 + m n

+d s (b1 +n b2 )

n (a1 + a2 ) + m (b1 + b2 ) b1 + b 2 ; r a1 + a2 + m +d s (b1 +n b2 ) d n n (a1 + a2 ) + m (b1 + b2 ) b1 + b2 ; ra1 +d ra2 +d rm +d sb1 +d sb2 d n n (a1 + a2 ) + m (b1 + b2 ) ; ra1 +d ra2 +d sb1 +d sb2 d na1 + mb1 na2 + mb2 + ; (ra1 +d sb1 ) +d (ra2 +d sb2 ) d d na1 + mb1 na2 + mb2 ; ra1 +d sb1 ; ra2 +d sb2 = (a1 ; b1 ) (a2 ; b2 ) . d d

5

!

Importantly, notice that m n ; d d Since

= (0; 1) and

(s

m; n

is a homomorphism, we know that for (a; b) 2 Z a (s

Thus, is surjective. Now, if Hence,

m; n

(a1 ; b1 ) = n (a1 d r (a1

r) b

m (b1 d a2 ) +d s (b1

a2 ) +

Zd ,

m n ; d d

(a2 ; b2 ), then

r) = (1; 0) .

= (a; b) :

na1 +mb1 ; ra1 d

+d sb1 =

na2 +mb2 ; ra2 d

+d sb2 .

b2 )

= 0 and

(3)

b2 )

= 0.

(4)

n m We know that gcd m a2 ) and nd j (b1 b2 ). It follows that d ; d = 1. Hence, (3) implies that d j (a1 m n k d = ja1 a2 j and k d = jb1 b2 j for some nonnegative integer k. Without loss of generality, suppose n a1 a2 = k m b2 . Thus, r (a1 a2 ) + s (b1 b2 ) = k r dm + s nd = k dd = k. By d and k d = b1 (4), we know that k 0 (mod d). Since 0 b1 ; b2 < n, we know that jb1 b2 j < n. If k 6= 0, then jb1 b2 j = k nd n as d j k; this is a contradiction. Therefore, k = 0 =) b1 = b2 =) a1 = a2 . Hence, is injective. The proof is complete.

Corollary 1.5. Z Zm Zn = Z

Zgcd(m;n) .

m

Lemma 1.6. If K is an abelian group and ' : Z Za1 ! K is an isomorphism such that ' (m; 0) = M , then m m m m M M M Z Za1 Za2 Zan = K Za2 Zan .

m

m

m

m

Proof. Let G = Z Za1 Za2 Zan and let H = K be denoted by . Let : G ! H be de…ned by

M

Za2

M

M

Zan . Let the operation of K

(x; x1 ; x2 ; :::; xn ) = (' (x; x1 ) ; x2 ; :::; xn ) . If (x; x1 ; x2 ; :::; xn ) = g1 and (y; y1 ; y2 ; :::; yn ) = g2 are elements of G, then (g1 g2 )

=

=

=

= = It is very clear that

! n X xi + yi ; x1 +a1 y1 ; x2 +a2 y2 ; :::; xn +an yn x+y+m ai i=1 ! ! n X xi + yi ' x+y+m ; x1 +a1 y1 ; x2 +a2 y2 ; :::; xn +an yn ai i=1 ! ! n X xi + yi ' (x; x1 ) ' (y; y1 ) ' m ; 0 ; x2 +a2 y2 ; :::; xn +an yn ai i=2 ! ! n X xi + yi ' (x; x1 ) ' (y; y1 ) M; x2 +a2 y2 ; :::; xn +an yn ai i=2

(' (x; x1 ) ; x2 ; :::; xn ) (' (y; y1 ) ; y2 ; :::; yn ) = is a bijection since ' is a bijection.

6

(g1 )

(g2 ) .

Lemma 1.7. (Z

Zd )

Proof. Let G = (Z the mapping

(q;0)

Zd )

(q;0)

Zb2

(q;0)

Zb2

(q;0)

(q;0)

q

Zbn = Zd

(q;0)

Z Zb2

q

q

Zbn and let G0 = Zd

Zbn . q

Z Zb2

q

q

Zbn . Consider

0

: G ! G , which is de…ned by ((x; x1 ) ; x2 ; :::; xn ) = (x1 ; (x; x2 ; :::; xn )) .

It is easily shown that

is a homomorphism; also, from the de…nition of , bijectivity quickly follows.

Now, for example, consider the carry group Z Z22 Z6 Z4 . We know that Z Z22 = Z. Moreover, there is an isomorphism ' : Z Therefore, Lemma 1.6 tells us that Z Z22 Z6 Z4 = Z Now, it follows from Proposition 1.4 that Z 22

22

Z6 = Z

Z6

22

Z6

22

Z4 .

Zgcd(22;6) = Z

22 6 gcd(22;6) ; 0

: Z Z6 ! Z Z2 such that (22; 0) 7! again, we have that Z

22

22

'

Z22 ! Z such that (1; 0) 7! 22.

Z2 and there is an isomorphism

= (lcm (22; 6) ; 0) = (66; 0). Applying Lemma 1.6

Z4 = (Z

Z2 )

(66;0)

Z4 .

It follows from Lemma 1.7 and Proposition 1.4 that (Z

Z2 )

= Z2 = Z2 = Z2

Z

(66;0) 66

Z4

Z4

Z Zgcd(66;4) Z Z2 .

Actually, we can follow the same procedure with any carry group and …nd its structure. We will now generalize this procedure. Consider the carry group G = Z Za1 Za2 Zan . Note that Z Za1 = Z by an isomorphism that maps (1; 0) to a1 . Therefore, Lemma 1.6 tells us that G=Z

a1

Za2

a1

a1

Zan :

a1

Proposition 1.4 tells us that Z Za2 = Z Zgcd(a1 ;a2 ) by an isomorphism that maps (a1 ; 0) to (lcm (a1 ; a2 ) ; 0). Lemma 1.6 tells us that G= Z

Zgcd(a1 ;a2 )

(lcm(a1 ;a2 );0)

Za3

(lcm(a1 ;a2 );0)

(lcm(a1 ;a2 );0)

Zan .

We now apply Lemma 1.7 to get that G = Zgcd(a1 ;a2 )

Z

lcm(a1 ;a2 )

Za3

lcm(a1 ;a2 )

lcm(a1 ;a2 )

Zan

:

Using the Principle of Mathematical Induction, we come upon the following theorem. Theorem 1.8. If a1 ; a2 ; :::; an are positive integers greater than 1, then Z Za1

Za2

Zan = Z

n M i=2

7

Zgcd(lcm(a1 ;:::;ai

1 );ai )

!

.

According to the theorem above, …nding the structure of any uniform carry group comes down to a few simple calculations. Using the theorem and the same example from above, we can quickly …nd that Z Z22 Z6 Z4 Z Zgcd(22;6) Zgcd(lcm(22;6);4) = = Z Z2 Z2 : In the following sections, we will discuss some more structure theory that applies to all carry groups (and not just uniform carry groups).

8

Chapter 2

General Structure Theory for Finitely Generated Carry Groups During the 2006 Potsdam-Clarkson NSF-REU, with Dr. Madore, we1 further investigated carry groups and continued the work of the 2001 REU program. There, we completely classi…ed the structure of …nitely generated carry groups. Our classi…cation for in…nitely generated carry groups is, for the most part, complete. We will now state and prove our main results. Lemma 2.1. Z

a1

Zb1

a2

a1

an

a2

Zbn = Z

a01

Zb1

a0n

a02

an

Proof. Let G = Z Zb1 Zbn and let H = Z for all i = 1; :::; n. Therefore, for each i = 1; :::; n,

Zbn if ai

a01

Zb1

a02

a0i (mod bi ) for all i = 1; :::; n. a0n

Zbn . Suppose that ai

a0i (mod bi )

a0i = ai + mi bi for some mi 2 Z. Now, let ' : G ! H be de…ned by ' (x; x1 ; :::; xn ) =

x

n X

mi xi ; x1 ; :::; xn

i=1

!

.

If (c; c1 ; :::; cn ) and (d; d1 ; :::; dn ) are elements of G, then ' ((c; c1 ; :::; cn ) (d; d1 ; :::; dn )) ! n X ci + di ; c1 +b1 d1 ; :::; cn +bn dn = ' c+d+ ai bi i=1 =

=

=

c+d+

c+d+

c+d+

n X

i=1 n X

i=1 n X i=1

=

c

n X i=1

ai (a0i a0i

ci + di bi

mi (ci +bi di ) ; c1 +b1 d1 ; :::; cn +bn dn

ci + di mi b i ) bi ci + di bi !

mi ci ; c1 ; :::; cn

mi (ci +bi di ) ; c1 +b1 d1 ; :::; cn +bn dn

mi (ci + di ) ; c1 +b1 d1 ; :::; cn +bn dn d

n X

!

mi di ; d1 ; :::; dn

i=1

!

!

!

= ' (c; c1 ; :::; cn ) ' (d; d1 ; :::; dn ) .

Now, surjectivity and injectivity follow quickly from the de…nition of '. 1 Tyler

Cook - SUNY Potsdam, Erica Miller - St. Edwards University, Tim Pollio - Princeton University, Zachariah Riel Kent State University, Annaliese Spaeth - Xavier University

9

Lemma 2.2. If gcd (b1 ; c) = 1, then Z

Proof. Let G = Z

a1

Zb1

a2

an

a1

Zb1

a2

an

Zbn and let H = Z

Zbn = Z

ca1

Zb1

ca1

a2

Zb1

an

a2

an

Zbn .

Zbn . Let ' : H ! G be de…ned by

' (x; x1 ; x2 ; :::; xn ) = c (0; x1 ; 0; :::; 0) (x; 0; x2 ; :::; xn ) . If (d; d1 ; d2 ; :::; dn ) and (e; e1 ; e2 ; :::; en ) are elements of H, then ' ((d; d1 ; d2 ; :::; dn ) (e; e1 ; e2 ; :::; en )) ! n X di + ei d1 + e1 = ' d + e + ca1 + ai ; d1 +b1 e1 ; d2 +b2 e2 ; :::; dn +bn en b1 bi i=2 n

= c (0; d1 +b1 e1 ; 0; :::; 0)

d + e + ca1

= c (0; d1 ; 0; :::; 0) (0; e1 ; 0; :::; 0)

X di + ei d1 + e1 + ai ; 0; d2 +b2 e2 ; :::; dn +bn en b1 bi i=2

a1

d1 + e1 ; 0; 0; :::; 0 b1

n

d + e + ca1

X d1 + e1 di + ei + ai ; 0; d2 +b2 e2 ; :::; dn +bn en b1 bi i=2

= c (0; d1 ; 0; :::; 0) c (0; e1 ; 0; :::; 0)

d+e+

n X i=2

ai

!

di + ei ; 0; d2 +b2 e2 ; :::; dn +bn en bi

!

!

= c (0; d1 ; 0; :::; 0) c (0; e1 ; 0; :::; 0) (d; 0; d2 ; :::; dn ) (e; 0; e2 ; :::; en ) = (c (0; d1 ; 0; :::; 0) (d; 0; d2 ; :::; dn )) (c (0; e1 ; 0; :::; 0) (e; 0; e2 ; :::; en )) = ' (d; d1 ; d2 ; :::; dn ) ' (e; e1 ; e2 ; :::; en ) . Since gcd (b1 ; c) = 1, we can …nd integers r and s such that b1 r + cs = 1. Clearly, c b1 s = 1. Let q be the least nonnegative residue of s, modulo b1 . Now, let (p; p1 ; p2 ; :::; pn ) 2 G. It follows from ( ) that 0 1 jcj 1 X (i sgn (c) q) + q sgn (c) b1 c (0; q; 0; :::; 0) = @ a1 ; 1; 0; :::; 0A b1 i=0 and so

0

'@

jcj 1

X i=0

a1

(i sgn (c)

1 q) + q sgn (c) b1 ; q; 0; :::; 0A = (0; 1; 0; :::; 0) . b1

Therefore, since ' is a homomorphism, we have that 0 1 jcj 1 X (i sgn (c) q) + q sgn (c) ' b1 a1 p1 @ ; q; 0; :::; 0A (p; 0; p2 ; :::; pn ) 7 ! (p; p1 ; p2 ; :::; pn ) . b1 i=0

Thus, ' is surjective. Suppose that (d; d1 ; d2 ; :::; dn ) ; (e; e1 ; e2 ; :::; en ) 2 H such that ' (d; d1 ; d2 ; :::; dn ) = ' (e; e1 ; e2 ; :::; en ). Thus, (d; 0; d2 ; :::; dn ) c (0; d1 ; 0; :::; 0) = (e; 0; e2 ; :::; en ) c (0; e1 ; 0; :::; 0) . Surely, di = ei for i = 2; :::; n. The previous equation gives us 0 jcj 1 X (i sgn (c) b1 d1 ) + d1 sgn (c) @d + a1 ;c b1 i=0 0 jcj 1 X (i sgn (c) b1 e1 ) + e1 sgn (c) @ a1 = e+ ;c b1 i=0

b1

b1

1

d1 ; d2 ; :::; dn A 1

e1 ; e2 ; :::; en A .

Since cd1 ce1 (mod b1 ) and gcd (b1 ; c) = 1, we have that d1 e1 (mod b1 ). Consequently, d1 = e1 . This forces d = e. Thus, ' is injective and the proof is complete. 10

The following lemma gives a few minor facts about carry groups. At this point, the reader should be familiar enough with carry groups to see (or at least have a strong suspicion) that they are true. We could probably get away with assuming these facts without stating them. For the sake of clarity, we will state them. However, we will leave it to the reader to prove the lemma, as it is a straightforward exercise. Note that the second fact is a generalization of Lemma 1.6; its proof is similar to that of 1.6. The third fact is practically identical with Lemma 1.7. Lemma 2.3. (a) If

2 Sn , then Z

a1

Zb1

an

a2

Zbn = Z

a

(1)

Zb

a

a

(2)

(1)

(n)

Zb

(n)

.

(b) Let H and K be Abelian groups. If H = K via ' : H ! K, then for any h1 ; :::; hn 2 H, H (c) (Z

Zd )

(a2 ;0)

Zb2

h1

(a3 ;0)

Zb1

h2

(an ;0)

hn

'(h1 )

Zbn = K

Zbn = Zd

Z a1

a2

Zb1

Zb2

a2

'(h2 )

a3

an

an

'(hn )

Zbn .

Zbn . ca1

a2

an

Lemma 2.2 tells us that if gcd (b1 ; c) = 1, then Z Zb1 Zbn = Z Zb1 Zbn . Actually, we can generalize this lemma a bit. Now, Lemma 2.3(a) tells us that the structure of a carry group does not change if we rearrange the …nite cyclic groups along with their respective carries. Therefore, we can apply 2.3(a) and 2.2 over and over again. Without loss of generality, if gcd (bi ; ci ) = 1 for all i = 1; :::; n, then a1 a2 an c1 a1 c2 a2 cn an Z Zb1 Zbn = Z Zb1 Zbn . From now on, whenever we refer to Lemma 2.2, we will refer to it in this general sense. Lemma 2.4. Given a; b 2 N, there exists c 2 N such that gcd(b; c) = 1 and ac

gcd(a; b)(mod b).

Proof. So, let a; b 2 N. Let b = p1 1 p2 2 pl l be a prime factorization for b. It is clear that, for all i = 1; :::; l, there exist ci ; i 2 Z such that a ci pi i (mod pi i ), where ci pi i < pi i and gcd(ci ; pi ) = 1. Also, for all i = 1; :::; l, there exist ki ; i 2 Z such that gcd(a; b) ki pi i (mod pi i ), where ki pi i < pi i and gcd(ki ; pi ) = 1. We claim that, for all i = 1; :::; l, i = i . First, suppose that j > j for some j. We know that we can write gcd(a; b) = ra + sb for some r; s 2 Z. Therefore, kj pj j

gcd(a; b)

ra + sb

ra

rcj pj j (mod pj j ).

Hence, kj

rcj pj

j

j

(mod pj j ).

j

j Now, this implies that kj = rcj pj + qj pj j for some qj 2 Z. Hence, pj j kj . Since pj > 1, this is a contradiction of the fact that gcd(kj ; pj ) = 1. Thus, i i for all i. Now, suppose that j < j for some j. So, since gcd(a; b) j a, we can write a = w gcd(a; b) for some w 2 Z. Now, we have that j (mod pj j ). Since cj pj j a w gcd(a; b) wkj pj j (mod pj j ). Therefore, we have that cj wkj pj j j < j , we have that pj j cj , which contradicts the fact that gcd(cj ; pj ) = 1. Therefore, we have that i i for all i. Since we also have that i i for all i, we conclude that i = i for all i.

Now, we can …nd a c such that c ki ci 1 (mod pi i ) for all i = 1; :::; l, which is guaranteed by the Chinese Remainder Theorem. Also, for all i = 1; :::; l, we have that ac

aki ci

1

ci pi i ki ci

1

pi i ki = pi i ki

Also, by the Chinese Remainder Theorem, we have that ac

11

gcd(a; b)(mod pi i ). gcd(a; b)(mod b).

a1

a2

an

Lemma 2.4 is quite useful for our cause. Consider the carry group Z Zb1 Zbn . For each i = 1; :::; n, it follows from Lemma 2.4 that there exists ci 2 N such that gcd(bi ; ci ) = 1 and ai ci gcd(ai ; bi )(mod bi ). It follows from Lemma 2.2 and Lemma 2.1 that Z = Z = Z

a1

a2

Zb1

c1 a1

Zb1

an

Zbn

c2 a2

gcd(a1 ;b1 )

cn an

Zb1

Zbn

gcd(a2 ;b2 )

gcd(an ;bn )

Zbn . a2

a1

an

Zbn , then ai j bi Thus, without loss of generality, we can assume that if given any carry group Z Zb1 for all i = 1; :::; n. The following lemma uses this general assumption. As you will see later, the following a1 an a2 lemma is a necessary tool for …nding the structure of Z Zb1 Zbn . Lemma 2.5. If ai j Z

Proof. Let G = Z In G, let

i,

a1 b1

a1 b1

bi j

i,

and gcd ( i ;

a2 b2

Z

1

1

Z

1

1

an bn

a2 b2

an bn

Z

Z y y1

yn

i)

n

n

n

n

= 1 for all i = 1; :::; n, then

=Z

a1

b1

Z

1

a2

Z

a1 b1

and let H = Z

an

1

Z

a1 b1 1

bn

Z

n

Z

1

Z

a2 b2

n

.

an bn

Z

an bn n

Z

n

.

= (1; 0; 0; :::; 0) = (0; 1; 0; :::; 0) .. . = (0; 0; 0; :::; 1) .

In H, let x = x11 = x12 =

xn1 xn2

(1; 0; 0; :::; 0) (0; 1; 0; :::; 0) (0; 0; 1; 0; :::; 0) .. . = (0; 0; 0; :::; 1; 0) = (0; 0; 0; :::; 1) .

Let ' : H ! G be de…ned by n

' (q; q11 ; q12 ; :::; qn1 ; qn2 ) = qy i=1

( i qi1 yi

i qi2 yi )

,

where is the operator corresponding to the operation . Let (c; c11 ; c12 ; :::; cn1 ; cn2 ) ; (d; d11 ; d12 ; :::; dn1 ; dn2 ) 2 H. Then, ' ((c; c11 ; c12 ; :::; cn1 ; cn2 ) (d; d11 ; d12 ; :::; dn1 ; dn2 )) n X ci2 + di2 ci1 + di1 ; c11 + + = ' c+d+ ai bi =

c+d+

i=1 n X

ai bi

i=1

i

ci1 + di1 i

i

+

ci2 + di2 i

12

!

1

d11 ; c12 +

1

d12 ; :::; cn1 +

n

dn1 ; cn2 +

n

dn2

n

y i=1

i

(ci1 +

i

di1 ) yi

i

ci2 +

i

di2 yi

.

!

Note that, in the previous line, n

(ci1 +

i

i=1

i

di1 ) yi

n

= i=1

ci2 +

i

i=1

(ci1 +

di1 ) yi

i

ci2 +

i

i=1 n X

=

i ci1 yi

i di1 yi

ai bi

i ci1 yi

i di1 yi

ai bi

i ci1

n

i di1

i ci2 yi

y

i

+

i

i ci2

ai bi

+ i i

n i ci2 yi

y

i di2 yi

ci2 + di2

ai bi

i=1

!

ci2 + di2

i di2 yi

i=1

ci1 + di1

i

i=1

+

di2 yi

i i

ci1 + di1

ai bi

i

i=1

n

=

di2 yi

n i

n

=

i

y

i

n

y i=1

( i ci1 yi

i di1 yi

i ci2 yi

i di2 yi )

.

Therefore, ' ((c; c11 ; c12 ; :::; cn1 ; cn2 ) (d; d11 ; d12 ; :::; dn1 ; dn2 )) ! n X ci1 + di1 ci2 + di2 = c+d+ ai bi + y i

i=1

n i

i=1

i

(ci1 +

i

di1 ) yi

i

ci2 +

i

di2 yi

n

=

(c + d) y i=1

( i ci1 yi

i di1 yi

i ci2 yi

i di2 yi )

n

=

cy i=1

n

( i ci1 yi

i ci2 yi )

dy i=1

( i di1 yi

i di2 yi )

= ' (c; c11 ; c12 ; :::; cn1 ; cn2 ) ' (d; d11 ; d12 ; :::; dn1 ; dn2 ) . So, ' is a homomorphism. For each i = 1; :::; n, we can …nd ri ; si 2 Z such that i ri + i si = 1, as gcd ( i ; i ) = 1. For each i = 1; :::; n, let Ri be the least nonnegative residue of ri , modulo i . Also, for each i, let Si be the least nonnegative residue of si , modulo i . For each i = 1; :::; n, there are integers mi ; ni such that ri = Ri + mi i and si = Si + ni i . Therefore, for each i = 1; :::; n, i ri

+

i si

=

i

(Ri + mi

i)

+

(Si + ni

i

i)

i Ri

+

i Si

1(mod

i i ).

Therefore, for each i = 1; :::; n, '

Si xi1 Ri xi2 7 ! and so

i Si yi

i Si

ai bi

+

i Ri yi

i Si

= yi ai bi

+

i Ri

y

i i

i Ri

'

x Si xi1 Ri xi2 7 ! yi .

i i

Let (p; p1 ; :::; pn ) 2 G. Therefore, n

pi

px

ai bi

i Si

i=1

+

i Ri

x Si xi1 Ri xi2

i i

'

7 ! (p; p1 ; :::; pn ) .

So, ' is surjective. Now, suppose that (c; c11 ; c12 ; :::; cn1 ; cn2 ) ; (d; d11 ; d12 ; :::; dn1 ; dn2 ) 2 H such that ' (c; c11 ; c12 ; :::; cn1 ; cn2 ) = ' (d; d11 ; d12 ; :::; dn1 ; dn2 ). Then, n

n

cy i=1

( i ci1 yi

i ci2 yi )

= dy i=1

( i di1 yi

i di2 yi )

.

Hence, c+

=

d+

n X

i=1 n X i=1

ai bi

i ci1 +

i ci2

i i

ai bi

i di1

+

i di2

i i

13

!

n

y

!

i=1

i ci1 +

i

i ci2

i

yi

n

y i=1

i di1 +

i

i

i di2

yi .

i di2

y

Therefore, for each i = 1; :::; n, i ci1 + i ci2

=)

i (ci1

i di1 + i di2

di1 ) +

i (ci2

(mod di2 ) = ki

i i) i i

for some ki 2 Z. Since i j ki i i and i j i (ci1 di1 ) for i = 1; :::; n, it is forced that i j i (ci2 di2 ) for i = 1; :::; n. Therefore, for all i = 1; :::; n, i j (ci2 di2 ) since gcd ( i ; i ) = 1. If ci2 6= di2 for some i, then 0 < jci2 di2 j < i and i - (ci2 di2 ), which is a contradiction. We must have that ci2 = bi2 for i = 1; :::; n. Similarly, i j (ci1 di1 ) for i = 1; :::; n. Since jci1 di1 j < i , we must have that ci1 = di1 for all i in order to avoid a contradiction. This forces c = d. Therefore, H = G. Now, let b1

a1

a2

bn

an

Z n Z n . Since bi j i for i = 1; :::; n, we have that gcd ( i ; bi ) = 1 for K=Z Z 1 Z 1 i = 1; :::; n. Similarly, ai j i for all i implies that gcd (ai ; i ) = 1 for all i. It follows from Lemma 2.2 that H = K. Therefore, G = K. Given a carry group, what are the necessary and su¢ cient conditions for it to be isomorphic to Z? The following theorem tells us precisely when a carry group is isomorphic to Z. Theorem 2.6. Let G = Z

a1

Zb1

a2

an

Zbn . The following are equivalent:

(a) The integers b1 ; :::; bn are pairwise relatively prime and gcd (ai ; bi ) = 1 for all i = 1; :::; n. (b) G = Z.

a1

a2

an

Proof. [(b) =) (a)] Let G = Z Zb1 Zbn . Assume that G = Z. We wish to show that the integers b1 ; :::; bn are pairwise relatively prime and gcd (ai ; bi ) = 1 for all i = 1; :::; n. Suppose that it isn’t true. Then, there exist 1 i1 < i2 n such that gcd (bi1 ; bi2 ) > 1 or there exists 1 j n such that gcd (ai ; bi ) > 1. (i) Suppose that there exists 1

j

aj

n such that gcd (aj ; bj ) > 1. We know that Z

aj

Zbj < G. By aj

Proposition 1.4, Z Zbj = Z Zgcd(aj ;bj ) . Therefore, there is a corresponding element of Z Zbj (in G) that has order gcd (aj ; bj ). Thus, G has an element of …nite order. This contradicts the fact that G = Z and Z has no elements of …nite order. Therefore, we must have that gcd (ai ; bi ) = 1 for all i = 1; :::; n. (ii) Suppose that there exist 1 Z

ai1

Zbi1

ai2

i1 < i2

n such that gcd (bi1 ; bi2 ) = d > 1. We know that

Zbi2 < G. Consider the element q 2 Z q=

ai1

b i1 ai (0; 1; 0) d 2

Zbi1

ai2

Zbi2 given by

b i2 ai (0; 0; 1) . d 1

I claim that q 6= (0; 0; 0). Otherwise, if the third coordinate of q is zero, then we would have to conclude b that di2 ai1 is a multiple of bi2 ; this means that d j ai1 . So, gcd (ai1 ; bi1 ) d > 1 since d j bi1 . This violates the fact that gcd (ai ; bi ) = 1 for all i = 1; :::; n. Hence, q 6= (0; 0; 0). We now get that b i 1 b i2 q

= = =

b i1 b i 2 bi1 ai2 (0; 1; 0) d b i1 b i 2 ai2 (ai1 ; 0; 0) d b i1 b i 2 ai1 ai2 (1; 0; 0) d

bi 1 bi 2 bi2 ai1 (0; 0; 1) d b i1 b i 2 ai1 (ai2 ; 0; 0) d b i 1 b i2 ai1 ai2 (1; 0; 0) = (0; 0; 0) . d

We have found that q is an element of …nite order. We obtain the contradiction that G has elements of …nite order. We must have that b1 ; :::; bn are all pairwise relatively prime. 14

[(a) =) (b)] Suppose that we’re given positive integers b1 ; :::; bn and integers a1 ; :::; an such that a1 a2 an b1 ; :::; bn are pairwise relatively prime and gcd (ai ; bi ) = 1 for all i = 1; :::; n. Let G = Z Zb1 Zbn . Using Lemma 2.2, Theorem 1.8, and the hypothesis that b1 ; :::; bn are pairwise relatively prime, we …nd that G

Z Zb1 Zbn Z Zgcd(b1 ;b2 ) Zgcd(lcm(b1 ;b2 );b3 ) Z Zgcd(b1 ;b2 ) Zgcd(b1 b2 ;b3 ) Z Z1 Z1 Z1 = Z.

= = = =

Zgcd(lcm(b1 ;b2 ;:::;bn Zgcd(b1 b2

bn

1 );bn )

1 ;bn )

We have a method for …nding the structure of any …nitely generated carry group, which we will now present. Suppose that we’re given the carry group a1

G=Z

Zb1

a2

an

Zbn .

According to the lemmas (2.4, 2.2, and 2.1), without loss of generality, we can assume that ai j bi for all i. We can now rewrite this as G=Z

p1111 p1212

1m1

p1m

1

p2121 p2222

Z

p1111 p1212

2m2

p2m

2

im

p1111

p1212

Zp

Zp

n1 n2 n1 pn2

where pi1i1 pi2i2 pimi i is the prime factorization of bi . For each 1 Now, by Lemma 2.5, G=Z

nmn pnm n

pn1n1 pn2n2

1m p1m 1 1

11 11

nmn pnm n

p1313

Zp

i

n,

Zp

nmn nmn

12 12

ij

ij

nmn pnm n

for all 1

.

, j

mi . (#1 )

This may look a bit ambiguous. To be clear, the group written in (#1 ) consists of m1 + + mn = N carry “components,” whereas the original group G consisted of n carry “components.” We say that a direct sum of …nite cyclic groups with any group of this form is “reduced.” We will now show that the group in (#1 ) can be transformed from an N -component group to an (N 1)-component reduced group. Choose any prime p 2 fpij : 1 i n and 1 j mi g . Let = min f For each 1

i

n and each 1

ij

j

: p = pij for some 1

i

n and 1

j

mi g .

mi , let ij

1 p

=

if if

pij = p; pij 6= p.

Applying Lemma 2.2, we get that G=Z Note that p j

ij

ij pij

11 11 p11

for all 1

Zp

12 12 p12

11 11

i

13 13 p13

Zp

nmn nmn pnmn

n and all 1

j

mi . In light of Lemma 2.3(a), we can assume that

p = p11 and = 11 . Further, by Proposition 1.4, there is an isomorphism (p ; 0) = p 11 ; 0 . Using Lemma 2.3(b), we have that G = (Z

Zp )

(

12 12 p12 ;0

)

Zp

(

.

Zp

nmn nmn

12 12

13 13 p13 ;0

)

(

:Z

nmn nmn pnmn ;0

)

p

Zp

Zp

nmn nmn

12 12

15

!Z

11

.

Zp , where

ij

Notice that, for each 1 i n, follows from Lemma 2.3(c) that G

= (Z

Zp )

= Zp

Z

(

ij pij

12 ( 11 12 p12 p

)

ij

;0 =

;0)

ij pij

(

Zp

p(

)

11

13 ( 11 13 p13 p

)

; 0 for all 1

;0)

(

j

mi (why?). So now, it

nmn ( 11 nmn pnmn p

)

;0)

12 12

12 ( 11 12 p12 p

)

13 ( 11 13 p13 p

Zp

nmn ( 11 nmn pnmn p

)

)

Zp

nmn nmn

12 12

!

Zp

nmn nmn

.

(#2 )

So, we have transformed the N -component group to an (N 1)-component reduced group as desired. Of course, this iterated process can be used to express G as a direct sum of Z with …nite cyclic groups. So, this method yields the structure of any …nitely generated carry group. However, this can be improved. Fix any 1 i n and 1 j mi . Recall that ij = p whenever pij 6= p. Therefore, if pij 6= p, then ij ( ) 11 = pijij p 11 . In (#2 ), if pij 6= p, then the ij th carry “component” has the form ij pij p pijij p

11

Z

pijij

We know that gcd p the ij

th

11

; pijij

.

= 1, since pij 6= p. Thus, we can apply Lemma 2.2 to rewrite (#2 ), where

carry “component” becomes

pijij

Z

pijij

.

This is the ij th carry “component” that we started with in (#1 ). Recall that when we chose the prime p = p11 , we transformed the carry “component” p1111

Zp

11 11

into a direct summand. In general, the argument above shows that the transformation of a carry “component” into a direct summand does not a¤ect the carry components whose bases are powers of a prime di¤erent from p. Therefore, this problem amounts to reducing groups of the form H=Z

p

1

Zp

p

2

p

1

n

Zp

n

,

where p is a prime, i i for i = 1; :::; n, and (without loss of generality) present our main structure theorem for …nitely generated carry groups. Theorem 2.7. Suppose that p is a prime. If Z

p

1

Zp

p

2

p

1

i

i

n

Zp

n

1

for i = 1; :::; n and ! n M ZpMi , =Z

n.

2

1

2

We now

n,

then

i=1

where M1 =

1

and Mi = min

i;

i

+

i 1

i 1

for i > 1.

Proof. Suppose that p is a prime. Let 1 ; :::; n and 1 ; :::; n be integers such that i i i+1 for each i = 1; :::; n. Let M1 = 1 and Mi = min i , and i i; i + i 1 each i > 1. We claim that, for each 1 k n, ! k M k k k p k+1 + k p k+2 + k p n+ k H= ZpMi Z Zp k+1 Zp n . i=1

16

0,

i

i 1

> 0, for

H

Z

=

p

= (Z

(p

1

Zp

Zp 1 )

= Zp

Z

1

2 ;0)

1

(p p

2+ 1

2+ 1

Zp

!Z

1

3 ;0)

(p

Zp 1 ;0

1

p

By Lemma 1.4, there is an isomorphism 1 : Z Lemma 2.3(b) and Lemma 2.3(c) tell us that

Zp n ;0)

(p

2

)

Zp

1

(p

1 ;0

Zp

n

)

n+ 1

(p

1 ;0

)

2 3+ 1

p

Zp

3+ 1

such that (p 1 ; 0) maps to p 1 ; 0 .

1

1

n+ 1

p

Zp

n

1

Zp

2

n

.

Our claim is true for k = 1. Suppose that, for some 1 l < n, our claim is true for k = l. Thus, ! l M p l+1 + l l p l+2 + l l p n+ l l H= ZpMi Z Zp l+1 Zp n . i=1

l+1 + l

p

l

Applying Lemma 1.4, there is an isomorphism 2 : Z Zp l+1 + l l l+1 ; 0 maps to p ; 0 . It follows from Lemma 2.3 that p H

=

l M

ZpMi

i=1

=

l M

ZpMi

i=1

=

l+1 M

ZpMi

i=1

!

Z

!

p

Z

!

Z

p

l+1 + l

l

Zp

l+2

l

p

n+ l

l+1 + l+1 ;0

l+2

l+1 + l+1

Zp (p

l+1 + l+1

l+3

p

Zp

)

l+2

! Z

n

ZpMl+1 such that

l

l+1

(p

ZpMl+1

l+2 + l

p

l+1

n

l+1 + l+1 ;0

p

n

)

Zp

n

!

l+1 + l+1

Zp

n

.

Therefore, our claim is true for k = l + 1 whenever it is true for k = l. By induction, it follows that ! n M H=Z ZpMi . i=1

6

10

Example. Let G = Z Z9 Z14 Thus, Lemma 2.2 tells us that

5

Z7 . Notice that gcd (2; 9) = 1, gcd (3; 14) = 1, and gcd (3; 7) = 1.

G

6

= Z Z9 = Z = Z

Also, note that 12

3 (mod 9), 30

62 12

10

Z9

Z9

5

Z14 Z7

10 3 30

Z14

Z14

2 (mod 14), and 15 3

2

15

53

Z7

Z7 .

1 (mod 7). Therefore, by Lemma 2.1, 1

G = Z Z9 Z14 Z7 . Now, note that gcd (7; 2) = 1. Therefore, Lemma 2.5 tells us that 3

2

1

1

G = Z Z9 Z2 Z7 Z7 .

17

Continuing on, using Theorem 2.7, we get that G

3

2

= Z Z9 Z2 = Z3 = Z3

70

2

Z Z2 Z2

Z71 70

Z

70

Z71

70

Z71

Z71 70

Z71

70

Z71

= Z3 Z2 (Z Z70 Z7minf1;0+1 = Z3 Z2 (Z Z1 Z7 ) = Z Z3 Z2 Z7 .

0g

)

At this point, our classi…cation of …nitely generated carry groups is complete. Now, we will explore in…nitely generated Carry groups.

18

Chapter 3

In…nitely Generated Carry Groups We will now consider groups of the form G=Z

a1

Zb1

a2

Zb2

a3

a4

Zb3

.

Note that the proofs of the lemmas in Chapter 2 did not depend on the fact that the groups were …nitely generated (perhaps except for Lemma 2.3(a)). Therefore, without loss of generality, we assume that ai j bi and bi is a prime power for all i 2 N. We will now give some de…nitions.

De…nitions Suppose that we are given G = Z

a1

Zb1

a2

Zb2

a3

1. Portions of the expression of G of the form

Zb3 ai

a4

, where ai j bi and bi is a prime power for all i.

Zbi are referred to as components.

2. We will de…ne bi =ai to be the depth of the component. 3. The collection of all components of G whose bi are powers of a …xed prime, p, is called the p-system of G. We denote a p-system of G as Gp and we denote its associated subgroup of G as Z Gp . 4. We de…ne the depth of a p-system to be the supremum of the depths of its components. 5. A p-system is said to be bounded if it has …nite depth. 6. A bounded p-system is said to be simple if it has some component to the depth of the system.

ai

Zbi where ai = 1 and bi is equal

7. The in…nitely generated carry group G is said to have rational form if there exist H sequence n1 ; n2 ; ::: of natural numbers such that ! 1 M G=H Zni .

Q and a

i=1

8. An element x 2 G where x = (m; m1 ; m2 ; :::) is said to be an integer if mi = 0 for all i. We may refer to x as m is this case. 9. For the in…nitely generated carry group G, we de…ne by G

G

: G ! Q, the projection homomorphism,

(x; x1 ; x2 ; :::) = x +

1 X i=1

19

xi

ai . bi

10. De…ne Gt = fx 2 G : x has …nite orderg. Gt is called the torsion subgroup of G. Furthermore, we say that G is torsion-free if Gt = f0G g. Note that the mapping given in de…nition 9, G , is actually a homomorphism; it is an easy exercise to show that G is a homomorphism. We leave this to the reader. Lemma 3.1. For any x 2 G, there exists n 2 N such that nx is an integer. Proof. Let x = (x0 ; x1 ; x2 ; :::) 2 G. Remember that xi = 0 for all except …nitely many i. Now, let Y n= bi . xi 6=0

We know that bi j n whenever xi 6= 0. Hence, bi j nxi whenever xi 6= 0; in this case, the ith coordinate of nx is 0. Therefore, nx is zero in every coordinate except possibly the …rst one. Therefore, nx is an integer by de…nition. Lemma 3.2. For the in…nitely generated carry group G, ker

G

= Gt .

Proof. Let x = (c; c1 ; c2 ; :::) 2 G. By the previous lemma, there exists n 2 N such that nx is an integer; say, nx = (b; 0; 0; :::). First of all, suppose that x 2 Gt ; then mx = 0G for some m 2 N. Therefore, m (nx) = mnx = n (mx) = 0G and nx 2 Gt . Since nx is an integer, we must have that nx = 0G ; otherwise, mnx = m (b; 0; 0; :::) = (mb; 0; 0; :::) 6= 0G since mb would be nonzero. Therefore, G (nx) = G (0G ) = 0. Hence, n G (x) = 0 so that G (x) = 0 and x 2 ker G . Thus, Gt ker G . Conversely, let x 2 ker G . Still, nx is an integer; also, nx 2 ker G , since G (nx) = n G (x) = 0. We know that nx = 0G , because G (nx) = G (b; 0; 0; :::) = b. Since nx = 0G , we conclude that x 2 Gt . Thus, ker G Gt . Hence, ker G = Gt . Corollary 3.3. For the in…nitely generated carry group G, G=Gt =

G

(G).

L1 Notice that if G has rational form H ( i=1 Zni ), then Corollary 3.3 implies that case, it follows that G (G) is a direct summand of G.

G

(G) = H. In this

Lemma 3.4. If Gp is a p-system of G, then there are no in…nite chains of additive pth roots in G. a1

a2

a3

a4

. Let x 2 G and suppose that x has Proof. Let Gp be a p-system of G = Z Zb1 Zb2 Zb3 an in…nite chain of additive pth roots. Then, for every n 2 N, there exists xn 2 G such that pn xn = x. Thus, for every n 2 N, G (xn ) = G (x) =pn 2 Q. Therefore, for some m 2 N, G (xm ) = ab , where gcd (a; p) = 1 and p j b. It is true that there is at least one component of the p-system, where the corresponding coordinate of xm is nonzero. Suppose otherwise. That is, suppose xm is zero in all the 0 coordinates corresponding to components of the p-system. Then G (xm ) = ab0 where p - b0 . Hence, 0 0 0 0 ab = a b. Since p - b , p - a, and p is a prime, we have that p - ab . This is a contradiction since p j a0 b. Thus, there is at least one component of the p-system, where the corresponding coordinate of xm is p

nonzero. Assume, without loss of generality, that this component is Zp and that the corresponding coordinate of xm is 6= 0. We know that p xm+ = xm . No matter what is in the Zp -coordinate of xm+ , we have that the Zp -coordinate of p xm+ = xm is 0. This is a contradiction. Therefore, x 2 G does not have an in…nite chain of pth roots. 20

Lemma 3.5. If some p-system of G is not bounded, then G does not have rational form.

Proof. Suppose that Gp is an unbounded system of G. Also, suppose that G has rational form with the associated H we know that i

p

1

p

2

p

Q. So, Z Gp has the form Z Zp 1 Zp 2 i can take arbitrarily large values. We claim that

3

. Since Gp is not bounded,

n : n 2 Z; m 2 N H Q. pm n o n o n n It is obvious that G (Z Gp ) : n 2 Z; m 2 N . Let y 2 : n 2 Z; m 2 N ; then y = m m p p for some n1 2 Z, m 2 N. Let = min fi 2 N : i i > m1 g. Therefore, G

(Z Gp ) =

n1

m1

y=p

m1

= n1 p

p

G

n1 pm1

(0; 0; :::; 1; 0; 0; :::) ,

n o (Z Gp ) and pnm : n 2 Z; m 2 N G (Z Gp ). o n n The claim is proved. Therefore, an isomorphic copy of pm : n 2 Z; m 2 N exists as a subgroup of o n G. This is impossible, because the set pnm : n 2 Z; m 2 N has in…nite chains of additive pth roots, whereas G does not. This is a contradiction. Therefore, G cannot have rational form. where the 1 is in the Z -coordinate. Thus, y 2

Theorem 3.6. Let G = Z

a1

Zb1

a2

Zb2

a3

Zb3

G

a4

. The following are equivalent:

(a) The integers b1 ; b2 ; ::: are pairwise relatively prime and gcd (ai ; bi ) = 1 for all i 2 N.

(b) G is torsion-free.

(c) G is isomorphic to a subgroup of Q.

Proof. [(a) (b)] Let x = (x0 ; x1 ; x2 ; :::) 2 Gt . There exists n0 2 N such that xi = 0 for all i > n0 . Qn=) 0 Let n1 = i=1 bi . By the proof of Lemma 3.1, n1 x is an integer. So, we must have that n1 x = 0G . Otherwise, n1 x has in…nite order. Hence, G (n1 x) = n1 G (x) = 0. This means that (x) = 0 n0 X xi ai x0 + = 0. bi i=1 G

=)

Pn0 xi ai We know that i=1 bi must be an integer, since x0 is an integer. The common denominator for this sum of rational numbers is n1 . Therefore, 0 1 n1 j

Fix 1

k

n0 . We know that bk j

Furthermore, whenever 1

i

n0 X B Bxi ai @ i=1

n0 X i=1

0

B Bxi ai @

Y

1 j n0 j6=i

Y

1 j n0 j6=i

C bj C A.

C bj C A.

n0 and i 6= k, we have that Y bk j xi ai bj . 1 j n0 j6=i

21

1

So, bk divides the ith summand for all i 6= k and bk divides the whole sum. To avoid a contradiction, bk must divide the k th summand; that is, Y bk j xk ak bj . 1 j n0 j6=k

Since all the bi are pairwise relatively prime, we know that bk and

Q

1 j n 0 bj j6=k

are relatively prime.

Hence, bk j xk ak . Since gcd (bk ; ak ) = 1, we have that bk j xk . Since 0 xk < bk , we must have that xk = 0. We chose k arbitrarily. Hence, for all 1 i n0 , we have that xi = 0. In light of the equation G (x) = 0, it is forced that x0 = 0. Hence, x = 0G . We conclude that G is torsion-free. [(b) =) (c)] Suppose that G is torsion-free. Since Gt = ker G and Gt = f0G g, we have that ker G = f0G g. This implies that G is an injective homomorphism. Therefore, G = G (G) Q. [(c) =) (a)] The exact same argument from the …rst half of the proof of Theorem 2.6 su¢ ces. As in the previous section, if we reduce components whose bases are powers of a prime p, then the carries of other components are not a¤ected whenever their bases are powers of a di¤erent prime. Therefore, the problem of reducing an in…nitely generated carry group comes down to reducing its p-systems. The following theorem tells us how bounded p-systems are reduced.

Lemma 3.7. Suppose that Gp is a bounded p-system, where Z Gp = Z Z Gp =

Z

p

1 M

1

Zp

1

p

1

Zp

p 1

2

Zp

p

3

2

. Then,

Zp i .

i=2

Proof. Suppose that G is an in…nitely generated carry group, where Gp is a bounded p-system of G. So, Z Gp is of the form Z

p

1

Zp

p

2

1

Zp

p

3

. Since the depth of Gp is …nite, this depth must be

2

achieved by one of the components. Without loss of generality, assume that this component is L1 p 1 Let H = Z Zp 1 i=2 Zp i . In H, let y y1 y2

Let ' : Z Gp ! H be de…ned by

"

' (x; x1 ; x2 ; :::) = xy

p

1

Zp 1 .

= ((1; 0) ; 0; :::; 0) = ((0; 1) ; 0; :::; 0) = ((0; 0) ; 1; :::; 0) .. .

x1

1 X i=2

xi p

1

1+

i

i

!

y1

#

1 M

xi yi .

i=2

It is straightforward (but quite tedious) to show that ' is a homomorphism. Surjectivity and injectivity follow quickly from the de…nition of '.

Lemma 3.8. If all of the p-systems of G are bounded and if all but …nitely many of the systems of G are simple, then G has rational form.

22

Proof. Apply Lemma 3.7 to all of the p-systems of G. Notice that the repeated application of Lemma c1 c2 c3 3.7 reduces G to a direct sum of …nite cyclic groups and a group of the form H0 = Z Zd1 Zd2 , where the di are pairwise relatively prime and ci = 1 for all but …nitely many i. For the (…nitely many) components that satisfy ci 6= 1, we can repeatedly apply Proposition 1.4 and transform them into direct summands. After transforming all such components into direct summands, G is reduced to , where the d0i are a direct sum of …nite cyclic groups and a group of the form H1 = Z Zd01 Zd02 pairwise relatively prime. Therefore, H1 satis…es Theorem 2.6(a) or Theorem 3.6(a). Hence, in any case, H1 = H for some H Q. Thus, G has rational form.

Lemma 3.9. If G has in…nitely many non-simple systems, then G does not have rational form.

Proof. Suppose that G has in…nitely many non-simple systems and that G has rational form. Then, essentially, G (G) is a direct summand of G. Therefore, there is a subgroup G1 G such that G1 = G (G). Let x 2 G1 be the element that corresponds to 1 2 G (G). Let n be a number so that nx is an integer. Let p be a prime such that p relatively prime to nx and Gp is a non-simple system of G; note that such a p exists by hypothesis. Assume that Gp is bounded; otherwise, we have our result by Lemma 3.5. Let pd be the depth of Gp . Since the depth is …nite, it is a maximum and must be achieved by some component of Gp . Therefore, p d 2 G (G). Then, certainly, x and nx both have pd-th roots. Say, pd y = nx. Let z z1 z2

= = =

(1; 0; 0; :::; 0) (0; 1; 0; :::; 0) (0; 0; 1; :::; 0) .. .

be the generators for G. Then, y must be a linear combination of z; z1 ; z2 ; :::. Assume that zi has ai a 1 in the coordinate corresponding to the Zbi component. Given ci , we know that either pd ci zi a is not an integer or pd ci zi = pd ci bii z. We claim that p j pd ci abii if pd ci zi = pd ci abii z. Assume that pd pd ci zi = pd ci abii z and p - pd ci abii . Then, pd j abii . Since pd is the depth of Gp , we have that abii and, therefore, pd = abii . Since Gp is not simple, we have that p j ai . Therefore, pd+1 j bi . Therefore, p j ci ; otherwise, pd+1 - pd ci =) bi - pd ci and so pd ci zi cannot be an integer. Since p j ci , we have that pd ci abii = pd ci p d = ci and p j pd ci abii ; this contradicts our assumption that p - pd ci abii . Thus, if pd ci zi = pd ci abii z, then p j pd ci abii . Since y is a linear combination of elements of the form cz and ci zi , we know that pd y is a linear combination of elements of the form pd cz and pd ci zi . These elements must be multiples of p; otherwise, they wouldn’t be integers and, thus, pd y = nx wouldn’t be an integer. Since the elements of the linear combination are multiples of p, we must have that pd y = nx is a multiple of p. This is a contradiction of the fact that p was chosen to be relatively prime to nx. Therefore, we must have that G does not have rational form. We know that every countably generated carry group satis…es the hypothesis of at least one of Lemma 3.5, Lemma 3.8, or Lemma 3.9. Therefore, we have a complete characterization of which groups have a rational form. Therefore, in sum, we conclude with the following theorem. Theorem 3.10. For any carry group G, G has rational form if and only if every system of G is bounded and all but …nitely many systems of G are simple.

23

Bibliography [1] J. L. KING, The generic transformation has roots of all orders. Dedicated to the memory of Anzelm Iwanik. Colloq. Math. 84/85 part 2, pp 521-547, 2000. [2] B. F. MADORE, Rank-one group actions with simple mixing Z subactions, Ph.D. Thesis, University of Toronto, 2000. [3] T. W. HUNGERFORD, "Algebra," Springer-Verlag, New York, 1975. [4] L. FUCHS, "In…nite Abelian Groups," Academic Press, New York, 1970-73. [5] N. JACOBSON, "Basic Algebra I - Second Edition," W.H. Freeman and Company, New York, 1985. [6] D.S. DUMMIT and R.S. FOOTE, "Abstract Algebra, 2nd Edition," J.W. Wiley and Sons, New York, 1999. [7] B. MADORE, H. McDONOUGH, C. MILLER, D. VAN NORT, A. ROGALSKI, and J. WOOD, Structure Theory for Carry Groups, Pi Mu Epsilon Journal, Vol. 12 (Fall 2004) 1, 17-25. [8] T. COOK, B. MADORE, E. MILLER, T. POLLIO, Z. RIEL, and A. SPAETH, Carry Groups, in preparation.

24