Lecture Notes in Mathematics 0061 :srotidE .A Dold, Heidelberg E Takens, Groningen regnirpS Berlin Heidelberg New York Barcelona Budapest gnoI-I Kong London Milan Paris oykoT watsydatW zciweikraN laimonyloP sgnippaM r e g n~ i r p S Author Wtadyslaw Narkiewicz Institute of Mathematics Wroctaw University Plac Grunwaldzki 2/4 PL-50-384-Wroclaw, Poland E-mail: narkiew @ math.uni.wroc.pl Mathematics Subject Classification (1991): ,80C11 llR09, llT06, ,50E21 13B25, 13F20, 14E05 ISBN 3-540-59435-3 Springer-Verlag Berlin Heidelberg New York CIP-Data applied for This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. (cid:14)9 Springer-Verlag Berlin Heidelberg 1995 Printed in Germany Typesetting: Camera-ready output by the author SPIN: 10130271 46/3142-543210 - Printed on acid-free paper Preface 1. Our aim is to give a survey of results dealing with certain algebraic and arithmetic questions concerning polynomial mappings in one or several variables. The first part will be devoted to algebraic properties of the ring lnt(R) of poly- nomials which map a given ring R into itself. In the case R -- Z the first result goes back to G.P61ya who in 1915 determined the structure of Int(Z) and later considered the case when R is the ring of integers in an algebraic number field. The rings Int(R) have many remarkable algebraic properties and are a source of examples and counter-examples in commutative algebra. E.g. the ring Int(Z) is not Noetherian and not a Bezout ring but it is a Priifer domain and a Skolem ring. We shall present classical results in this topic due to G.P61ya, A.Ostrowski and T.Skolem as well as modern development. 2, In the second part we shall deal with fully invariant sets for polynomial mappings )I( in one or several variables, i.e. sets X satisfying (I)(X) = X. In the case of complex polynomials this notion is closely related to Julia sets and the modern theory of fractals, however we shall concentrate on much more modest questions and consider polynomial maps in fields which are rather far from being algebraically closed. Our starting point will be the observation that if f is a polynomial with rational coefficients and X is a subset of the rationals satisfying f(X) = X, then either X is finite or f is linear. It turns out that the same assertion holds for certain other fields in place of the rationals and also for a certain class of polynomial mappings in several variables. We shall survey the development of these question and finally we shall deal with cyclic points of a polynomial mapping, i.e. with fixpoints of its iterates. Here we shall give the classical result of I.N.Baker~concerning cyclic points of complex polynomials and then consider that question in rings of integers in an algebrai~c number field. There are several open problems concerning questions touched upon in these lectures and we present twenty one of them. 3. This text is based on a course given by the author at the Karl-Franzens University in Graz in 1991. I am very grateful to professor Franz Halter-Koch for organizing my stay in Graz as well for several very fruitful discussions. My thanks go also to colleagues and friends who had a look at the manuscript and in particular to the anonymous referee who pointed out some inaccuracies. The work on these lecture notes has been supported by the KBN grant 2 1037 91 01. The typesetting has been done by the author using ,4.M$-TEX. Notations We shall denote the rational number field by Q, the field of reals by R, the complex number field by C and the field of p~adic numbers by Qp. The ring of rational integers will be denoted by Z, the set of nonnegative rational integers by N, the ring of integers of pQ by Zp, the finite field of q elements by Fq and the ring of integers in an algebraic number field K by ZK. By a b ew shall denote the divisibility ill various rings and in case of the ring of rational integers ew shall write q 1 a in the case when q is the maximal power of a prime which divides a. The same notation will be used for divisibility of ideals in Dedekind domains. The symbol will mark the end of a proof. CONTENTS PREFACE .............................................................. V NOTATIONS ........................................................... VI PART A: RINGS OF INTEGRAL-VALUED POLYNOMIALS ...... l .I POLYNOMIAL FUNCTIONS ........................................... I .fI THE RING Int(R) ................................................. 12 III. FIXED DIVISORS .................................................. 26 IV. REGULAR BASIS .................................................. 31 V. P6LYA FIELDS ..................................................... 35 VI. INTEGRAL-VALUED DERIVATIVES .................................. 41 Int(R) VII. ALGEBRAIC PROPERTIES OF .............................. 48 VIII. D-RINGS ........................................................ 61 PART B: FULLY INVARIANT SETS FOR POLYNOMIAL MAPPINGS ......................................................... 67 IX. THE PROPERTIES (P) AND (SP) ................................. 67 X. HEIGHTS AND TRANSCENDENTAL EXTENSIONS ..................... 77 XI. PAIRS OF POLYNOMIAL MAPPINGS ................................ 93 XII. POLYNOMIAL CYCLES ............................................ 97 LIST OF OPEN PROBLEMS ............................................ 110 REFERENCES ........................................................ 112 INDEX ............................................................... 124 PART A Rings of integral-valued polynomials I. Polynomial functions 1. Let R be an arbitrary commutative ring with unit. Every element f of RX, the ring of all polynomials in one variable with coefficients in R, defines a map T! : R > R. The set of all maps T! obtained in this way forms a ring, the ring of polynomial functions on R, which we shall denote by P(R). Let IR denote the set of all polynomials f E RX satisfying f(r) = 0 for all r E R, and let F(R) denote the set of all maps R > R. The following lemma collects a few easy facts concerning P(R) and IR: LEMMA 1.1. (i) The set IR is an ideal in RX and we have P(R) -~ RX/IR, (ii) If R is a domain then the equality In = {0} holds if and only if R is infinite, (iii) If R = Fq then IR is generated by the polynomial Xq - X and P(R) _~ RX/(X q - X)RX. PROOF: The assertion (i) is evident. If R is infinite then clearly only the zero polynomial vanishes identically on R. If R is a finite domain then it is a field, say R = Fq, and the polynomial X q - X vanishes identically. This proves (ii). The last assertion follows from the remark that if a polynomial vanishes at all elements of the field Fq then it must be divisible by l'I Ix-a) = xq- z qFEa 2. The ring P(R) can be described in terms of certain ideals of R: THEOREM 1.2. (J.WIESENBAUER 82) If R is a commutative ring with unit element and for j = 0,1 .... we define Ij to be the set of alia E R such that there exist Co,C1,..., cj-1 in R With j-1 ax j W Z cixi : 0 for all x E R o=..i then the Ij's form an ascending chain of ideals in R and if for j - 0, 1,... we fix a set Aj of representatives of R/b containing ,O then every f e P(R) can be uniquely written in the form N f(x) = E aj x j j=O with a suitable N, aj E Aj and aN (cid:127) 0 in case f r .O PROOF: Clearly the Ij's form an ascending chain of ideals. Assume that our assertion fails for some non-zero f E P(R). Consider all possible polynomial representations: ~T : f(x) = ~ djx j (x e R, dj E R, dm #0) O=j and denote by i(R) the maximal index j with dj ~ Aj. Choose now a represen- tation R0 with i = i(Ro) minimal and write (1.1) f(x) = E djxJ + ajxJ' j=O j=l+i with di ~ Ai and aj E Aj for j = 1 + i, 2 + i ..... m. If ai E Ai satisfies ai - di EIi then with suitable ,0b bl,..., bi-1 E R we have i-1 (a,-d,)x~+~b~zZ=O for all z e R, j=O hence in (1.1) we may replace the term dix i by i--1 aix i + Ebjz5, j=o contradicting the choice of .0~T 3. If p is a rational prime then every fimction Z/pZ ~ Z/pZ can be represented by a polynomial. The next theorem describes commutative rings with unit having this property. THEOREM 1.3. (L.RI~DEI, T.SZELE 47, part I) Let R be a commutative ring with a unit element. Every function f : R ~ R can be represented by a polynomial from RX, i.e. F(R) = P(R) holds if and only if R is a finite field. PROOF: The sufficiency of the stated condition follows immediately from the interpolation formula of Lagrange, so we concentrate on its necessity. If R is infinite and its cardinality equals a, then tile cardinality of RX also equals a but the cardinality of all maps R } R equals a ~ > a, hence not every such map can be represented by a polynomial. Let thus R = {al = 0,a2,..., an} be a finite unitary commutative ring of n elements. If it is not a field, then it has a zero-divisor c, since every finite domain is necessarily a field. Put n g(X) = H(X - aO, i=1 and observe that for all a E R one has g(a) = .O This shows that if a map R ~ R can be represented by a polynomial F, then F can be chosen to have its degree < n - ,1 since F and F mod g represent the same function on R. The number of all maps R } R and the number of all polynomials of degree <_ n - 1 both equal n n and hence it is sufficient to find a non-zero polynomial of degree _~ n - 1 vanishing on R. The polynomial n S(x) = c 1-(x - aa i=2 can serve as an example since it evidently vanishes at non-zero arguments and moreover we have f(O) = (-1)"-lca2a3...an, but as c is a zero-divisor there is an element ai # 0 with cai = 0 and thus f(0) = 0. (This argument can be modified to cover also rings which do not have a unit element. Cf. L.RI~DEI, T.SZELE 47, part I, p.301). 4. Consider the following example: Let R = Z/4Z be the ring of residue classes mod 4 and put f(x)= { 0 if x:0,1 1 ifx = 2,3. The function f cannot be represented by a polynomial over R, since otherwise we would have 1 =f(3)=f(1)=0 (mod2). However the polynomial attains integral values at integers and it induces on R the function f. This situation is a special case of the following construction: Let R and S1 C $2 be commutative rings and let F : S1 .... > R be a surjective homomorphism. If a polynomial f E S2X satisfies