5. There exists monic f ∈ Z [ X ] with f ( α ) = 0 , where we know m g = f α for some g ∈ Q [ X ] by the remark after the definition of m . There α exists nonzero a ∈ Z such that am ∈ Z [ X ] and is simple. Then f = α − 1 − 1 ( am )( a g ) , whence a g ∈ Z [ X ] by part 2 of Problem 3.2. But f is α monic. So a = 1 and therefore m ∈ Z [ X ] . α 6 3.4 (6 points) For all 1 ≤ i ≤ m , let f ( X , . . . , X ) = a X + . . . + a X ∈ Z [ X , . . . , X ] i 1 n i, 1 1 i,n n 1 n where n > m and | a | ≤ A for all i, j for some fixed A > 0 . Prove that there i,j exist x , . . . , x ∈ Z , satisfying 1 n f ( x , . . . , x ) = . . . = f ( x , . . . , x ) = 0 1 1 n m 1 n m/ ( n − m ) such that | x | ≤ b ( nA ) c for all j and x 6 = 0 for some j . We use the j j notation b s c to denote the greatest integer not greater than s . Hint: Use the Pigeonhole Principle. That is, if there are N pigeonholes and M pigeons, where M > N , then at least one pigeonhole must get > 1 pigeon. ∑ ∑ n n Solution. Let a = max(0 , a ) and b = min(0 , a ) . For all integer i i,j i i,j j =1 j =1 n r ≥ 0 , there are ( r + 1) n -tuples ( x , . . . , x ) in the n -dimensional “box” 1 n n { 0 , . . . , r } . The m -tuple ( f , . . . , f ) is a function on this box, with values in 1 m the m -dimensional box m ∏ B = { b r, . . . , a r } i i i =1 ∏ (Above, is a shorthand notation for × . . . × , and the terms of the product are again sets.) m/ ( n − m ) n m Set r = b ( nA ) c . Since n > m , we have ( r + 1) > (( r + 1) nA ) > m ( rnA + 1) , whence m ∏ m m

B = ( ra − rb + 1) ≤ ( rnA + 1) < ( r + 1)

i i i =1 By the Pigeonhole Principle, two of our n -tuples are mapped to the same m - tuple by ( f , . . . , m ) . Their difference ( x , . . . , x ) is nonzero, meaning x 6 = 0 1 1 n i for some i , and is mapped to (0 , . . . , 0) , so that | x | ≤ r for all i . i Note: Thanks to Kevin Li for pointing out that when all f ’s are zero, we m/ ( n − m ) cannot both satisfy | x | ≤ b ( nA ) c for all j and x 6 = 0 for some j . This j j problem may be fixed by either making A take on only integer values or making at least one f nonzero. i 4 Main Results (56 points) The problems in this section are very hard, so do not be discouraged if you get stuck on some—or all!—of them. In what follows, let I = [ − 1 / 2 , +1 / 2] . 7 4.1 (4 points) Let 0 < < 1 / 2 . Show that if, for all α which are algebraic integers in I of degree d ≥ 3 , ∣ ∣ ∣ ∣ p 1 ∣ ∣ α − < ∣ ∣ 1+ + d/ 2 q q has only finitely many solutions for the rational p/q in lowest terms, then, for all α which are algebraic integers (not necessarily in I ) of degree d ≥ 1 , it also has only finitely many solutions for the rational p/q in lowest terms. Solution. Let us first show that the existence of only finitely many solutions for p/q is equivalent to the existence of a constant c ( α, ) such that ∣ ∣ ∣ ∣ p c ( α, ) ∣ ∣ α − ≥ ∣ ∣ 1+ d/ 2+ q q p for all 6 = α . This fact, which we will call Lemma 4.1, will be used both here q and in the solution to 4.5. First we assume that there are finitely many solutions to ∣ ∣ ∣ ∣ p 1+ δ + d/ 2 ∣ ∣ α − < 1 /q ∣ ∣ q then clearly their exists a lower bound C such that ∣ ∣ ∣ ∣ p C ∣ ∣ α − ≥ ∣ ∣ 1+ δ + d/ 2 q q where C is min( c ) and each c > 0 is chosen such that i i ∣ ∣ ∣ ∣ p c i i ∣ ∣ α − ≥ ∣ ∣ 1+ δ + d/ 2 q i q i . Finitely many c implies positive minimum, so C is positive. i Conversely, if we start with the existence of C ( α, δ ) for all 0 < δ < such that ∣ ∣ ∣ ∣ p C ( α, δ ) ∣ ∣ α − ≥ ∣ ∣ 1+ δ + d/ 2 q q p for all 6 = α . Then when q ∣ ∣ ∣ ∣ p 1 ∣ ∣ α − < ∣ ∣ 1+ + d/ 2 q q δ − we have 0 < C ( α, δ ) < q , which for δ < can only be true for finitely many p . This proves our lemma. q 8 So equivalently, we have to produce a constant c ( α, ) depending only on α and , such that ∣ ∣ ∣ ∣ p c ( α, ) ∣ ∣ α − ≥ ∣ ∣ 1+ d/ 2+ q q p p for all 6 = α . If α / ∈ R , we know that | α − | ≥ Im( α ) > 0 and for large enough q q q we get a contradiction. Thus q is bounded, and for fixed q , the number of choices for p are finite (by the inequality) and so we have finitely many solutions a in total. Thus we are reduced to α ∈ R . If d = 1 , we have that α = where b p a, b are integers. For 6 = α , we see that q ∣ ∣ ∣ ∣ p 1 1 ∣ ∣ α − ≥ ≥ ∣ ∣ 3 / 2+ q qb bq 1 ′ ′ and pick c ( α, ) = . For d = 2 , we have α ∈ R , α 6 = α such that P ( x ) = b p p 1 2 ′ x + ax + b = ( x − α )( x − α ) and a, b ∈ Z . For ∈ Q , we have | P ( ) | ≥ . If 2 q q q | α − p/q | < 1 , we have ∣ ∣ ∣ ∣ p P ( p/q ) 1 ∣ ∣ α − = > ∣ ∣ ′ ′ 2 q | α − p/q | (1 + | α − α | ) q ( ) 1 and picking c ( α, ) = min 1 , gives us the desired result. Finally ′ 1 + | α − α | 1 when α ∈ R and | α | > , pick integer n such that n + α ∈ I and observe 2 { } p p 1 that the finiteness of the set : | ( α + n ) − | < is equivalent to 1+ d/ 2+ q q q { } ′ ′ p p − n p 1 the finiteness of the set := : | α − | < . 1+ d/ 2+ q q q q 4.2 (8 points) md + Let d, m, n ∈ Z such that d ≥ 3 and 1 < < 2 , and let n +1 md λ = 1 − 2 n + 2 Let α be an algebraic integer in I of degree d . Show that there exist P ( X ) , Q ( X ) ∈ Z [ X ] such that: