Functional Equations Connected With The Collatz Problem

Results in Mathematics Vol. 25 (1994) 0378-6218/94/020001 -12$1.50+0.20/0 (c) 1994 Birkhauser Verlag, Basel FUNCTIONAL EQUATIONS CONNECTED WITH THE COLLATZ PROBLEM Lothar Berg and Gunter Meinardus Abstract. In this paper, some aspects of the famous 3n + 1 problem, due to L. Collatz, are stu- died. Introducing generat ing functions for the iterated mappings, we derive certain linear recursion formulae and investigate their properties. For the still unproved conjecture of L. Collatz we state two equivalent analytic versions , concerning the rational character of some generat ing funct ions, and the set of solutions of a linear functional equation, respectively. Math. Subject Classification: llB37,39B32 Keywords: 3n +1 problem, Collatz Conjecture, generating functions 1 Preliminaries The mapping T : N -t N, defined, for n E N, by { In T(n) = 2 3n + 1 for n == 0 mod 2 for n == 1 mod 2 was introduced by L. Collatz and named after him , for the history d. J. C. Lagarias [7]. Since, for odd n , the expression 3n +1 is always even, we will consider a modified mapping t , which is under all aspects equivalent to the Collatz mapping T . Most investigations are a bit easier to work out on t than on T, however. In addition, we continue t to the set of integers Z, i.e. the mapping t : Z -t Z is defined, for nEZ, by or by { In t(n) = ~(3n + 1) for n == 0 mod 2 for n == 1 mod 2 (1) 1 t(n) = 4{4n + 1 - (-It(2n + I)} The iterates of this mapping are defined recursively by to(n) = n, tm(n) = t(tm_1(n)) for m :::: 1. Already as a student about 1930, L. Collatz [3] has stated the Conjecture 1. For every number n E N there exists a number m( n) with the property (2) (3) (4) 2 Berg and Meinardus This conjecture, usually called the 3n + 1 Conjecture, has now been verified up to n = 5.6 x 1013 , d. G. Leavens and M. Vermeulen [8] , but a general proof of it is still open . However, there exists a series of papers dealing with the Collatz problem and its generalizations, where the problem is attacked by combinatorical, number theoretical, and also by stochastical methods in connection with Diophantine equations and ergodic theory, d . e.g, R. Terras [11], R. E. Crandall [4] and K. R. Matthews [9]. In the following we use analytical methods by considering generating functions and functional equations. The basic ideas and equivalent versions of the main results with T instead of t are already contained in the preprint G. Meinardus [10] . The mapping t possesses the only fixed points 0 and -1 in Z. Furthermore, th ere exist the three cycles 1,2,1, -5, -7, -10, -5, -17, -25, -37, -55, -82, -41, -61, -91, -136, -68, -34, -17 of period 2,3 and 11, respectively. A generalization of Conjecture 1 is that the iterates (3) of the positive integers always enter into the first cycle, and of the negative integers into -1 or into one of the last two cycles, d. C. Bohm and G. Sontacchi [2]. 2 Elementary properties The mapping t is a linear function of the discrete variable nEZ, depending on the residue class of n modulo 2. Hence, the iterates tm with m ~ 1 have the analogous property on the residue class of n modulo 2m • In order to find an explicit representation for tm , we introduce the functions xm(n) with values 0 and 1 by (5) They have the property xAn + 2m ) = xj(n) for j < m. Then, according to R. Terras [10] and J. C. Lagarias [7], we have the Lemma 1. The iterates tm possess the representation 1 tm(n) = 2m (amvn + bmv) for n == v mod 2 m and 0 5 v < n with the coefficients m-l amv = 3:ro(v)+ ···+:rm-dv), bmv = L x;(v)2; · 3:ri+d v)+···+:rm - 1(v) ;=0 and the initial values amO = 1, bmo = 0 . The first coefficients in (7) are amv =3" for exactly (':) values u, A simple consequence of (6) is (6) (7) Berg and Meinardus 3 (9) (8) Lemma 2. The iterates tm possess the property tm(2mk + v) = amvk+ tm(v) Furth ermore, they satisfy the difference equation tm(n - 2m ) + tm(n +2m ) = 2tm(n) Equation (6) gives for m = 2, in particular, 1 ~n for n == 0 mod 4 H3n + 1) for n == 1 mod 4 t2(n) - - H3n +2) for n == 2 mod 4 H9n +5) for n == 3 mod 4 Lemma 3. The Collatz mapping t has only one proper cycle with the period 2, namely the cycle 1,2,1. Proof. We have to discuss the equation t2 (n) = n, i.e. the four equations n = 4n, 3n + 1 = 4n, 3n +2 = 4n and 9n +5 = 4n , which have the solutions 0,1,2 and -1 , respectively. Since 0 and -1 are fixed points, we have proved the lemma • For more informations about cycles d. R. Terras [11] and L. E. Garner [6] . By means of the discrete Fourier transform, we can easily generalize (2) to Lemma 4. The iterates tm have the unique representation 1 2m_l tm(n) =~ L (aml'n +PmI') (::,n 4 1'=0 2'"_1 2'"_1 amI' = L amv(~I'V , PmI' = L bmv(~I'V v=o v=o (10) (11) For the proof it is only necessary to replace the coefficients in (10) by (11), and to use the orthogonality relations 2 m_l { 2m r - d 2mL (::,(n- v) = tor n = v mo 1'=0 0 else . In what follows we need an estimate for the iterates. Lemma 5. For all natural numbers m, n we have tm(n) ::; a)m (n + 1) - 1 (12) Proof. From (1) we easily obtain 3 tm+I(n) + 1 ::; 2(tm(n) + 1) and according to the initial ~alue to(n) = n, this inequality implies (12) • 4 Berg and Meinardus 3 Generating functions It is useful to introduce the two generating functions for the modified Collatz mapping t 00 fm(z) = L tm(n)zn , (13) n=O 00 gn(w) = L tm(n)wm (14) m=O with integers m, n and complex variables z, w. In view of Lemma 5, the first series converges for Izl < 1, and the second one for Iwl < 2/3. Theorem 2. The functions fm(z) are rational functions of the form (15) with the numerator 2m+'_1 Pm(z) = L em"z" (16) ,,=1 and the coefficients for v = 1, 2, ... ,2m , for v = 2m + 1, ... ,2m +! - 1 (17) Proof. For Izi < 1 we consider the product 2m 2m +1 L tm(n)Zn + L (tm(n) - 2tm(n - 2m)) zn+ n=1 n=2m +l f: (tm(n) - 2tm(n - 2m) + tm(n - 2m+!)) zn , n=2m +'+1 where we have used that tm(O) = O. According to (9) we have Hence, the last series vanishes, and also the term of the second series with n = 2m +!, so that we have proved (16) with (17) • Analogously, we can prove, cf. a theorem of W. B. Ford [5]: Corollary 1. For Izi > 1 the function (15) has the expansion 00 fm(z) = - L tm( _n)z-n n=1 Berg and Meinardus 5 The leading coefficient of (16) is equal to -tm(- I ) = 1, so that Pm(z) has the exact degree 2m +! - 1. Special examples are fo(z) = (1~Z)2 f (z ) - 2z±z2±z31 - (1_z2)2 By substitution of (6) into (13) we obtain the decomposition (18) By substitution of (10) into (13) we find the complete decomposition into partial fractions 1 2 m_1 (om" 13m" - om,,) fm(z) = 4m ~ (1 - C::'z)2 + 1 - C::'z About the functions g" we state the Conjecture 2. The functions 00 g,,(w) = L tm(n)wm m=O from (14) are rational functions of the form ( ) _ q,,(w) g" w - 1-w2 where q"(w) are polynomials with integer coefficients. Special examples are go(w) = 0, (19) gl(W) g2(W) g3(W) g4(W) gs(w) = 1±2w 1-w2 = ~1-w2 , 3 +5w +8w2+4w3 + 2~~t,~5 = 4 + 2w±w21-w2 , = 5 +8w +4w3 + 2w3±w'1-w2 Theorem 3. Conjecture 1 and 2 are equivalent. Proof. If tk(n) = 1 for a fixed n E N, then k-1 wk +2wk±1 g,,(w) = L tm(n)wm + 1 _ w2 m=O 6 Berg and Meinardus i.e. gm is of the form (19). Conversely, if gm possesses the representation (19) with a polynomial qn(w) of degree k + 1, then we can write it in the form and the coefficients in (14) have the cycle do ,db do. Since both coefficients d, = tm(k + i) are positive, one of the numbers do , dt must be equal to 1 according to Lemma 3 • We also introduce the generating function 00 F(z, w) = L tm(n)znwm , m ,n=O (20) which is a holomorphic function of 2 variables in the polydisk Hz, w)llzl < 1, Iwl < D, and can also be represented as 00 F( z , w) = L fm(z)wm , m=O 00 F( z,w) = Lgn(W)zn n=O 4 Functional equations In what follows, we use the notation and the Heeke operator H3 , defined for a function u( z) by (21) (22) (23) cr. G. E. Andrews [1] . Theorem 4. The generating functions (13),(14) and (20) satisfy the linear functional equations g2n(W) = 2n +wgn(w) , g2n-t(W) =2n - 1+wg3n-t(W) , (24) (25) (26) Berg and Meinardus Proof. From (13) we obtain 00 00 fm+l(z) = E tm(t(n)) zn = fm(z2) +E tm(3k - I)Z2k-l n=O k=l On the other side, we have 00 = E tm (3k _1)z6k-3 , k=l so that both equations imply (24). From tm(2n) = tm-1(n) and therefore 00 92n(W) = 2n + E tm_1(n)wm m=l it follows (25), and from tm(2n -1) = tm_1(3n -1) and therefore 00 92n-l(W) = 2n -1 +E t";'_1(3n - l)wm m=l 7 (27) it follows (26), where in both cases we have used to(n) = n. Finally, multiplying (24) by wm and summing over m, we obtain (27) in view of fo(z) = z/(1 - Z)2 • Obviously, the homogeneous equation corresponding to (27) cannot have a nontrivial solution, which is holomorphic with respect to w in the neighbourhood of w = 0, and for a fixed z "# O. Hence, we get the Corollary 2. The equation (27) determines the function F(z,w) from (20) uniquely. A simple consequence of (24) is the formula with m:::: 1. Now, we consider the functional equation (28) (29) 8 Berg and Meinardus which is the homogeneous equation corresponding to (27) in the case w = 1. This equation is equivalent to the system of equations h(z)+h(-z) =2h(Z2) , which we find, if we replace z by -z in (29), cf. (28). We consider the series 00 h(z) = E hnzn , n=O which shall be convergent for Izi < l. Lemma 6. The function (32) is a solution of (30), if and only if for all n E N The function (32) is a solution of (31), if and only if for all n E N The function (32) is a solution of (29), if and only if fo r all n E N (30) (31) (32) (33) (34) (35) Proof. The first statement is obvious, the second can be proved analogously as (24), and the third follows from the equivalence of (35) and the system (33), (34) • If we introduce the function 00 '"' 2 n f3(z)=L.. z , n=O (36) which satisfies the functional equation f3( z) = z + f3( Z2) and has the unit circle as natural boundary, then the general solution of (30) is 00 h(z) = ho +E h2n+lf3 (Z2n+l) n=O The solutions of (34) are hSn+3 = h12n+5 = h1Sn+S , and generally (37) Berg and Meinardus 9 for 0 < m < k with k 2': 1, n 2': 0 and n =F 3p + 1. This can easely be checked, since every positive odd number can uniquely be written in the form 2k(2n + 1) - 1, and for n = 3p + 1 we have the identity 2k(6p +3) = 3 · 2k(2p +1). Hence, the solutions of (31) have the form h(z) = ho +hI(z + z2) + h3(Z3 + ZS +z8) +h4z4+h6z6+h7(z7+Zll + zI7 +Z26) 38 +h9(z9+zI4) + hlOzIO+ h12zI2 +hI3(zI3 + z20) + hIS(zIS + z23 + z3S + zS3 +Z80) +...( ) Finally, it can easily be checked that Z ho+hI--1- z is a solution of (29) for arbitrary constants ho and hI . Conjecture 3. Besides of (39), there exist no further solutions of which are holomorphic for Izi < 1. Theorem 5. Conjecture 1 and Conjecture 3 are also equivalent. (39) Proof. If Conjecture 1 is true, then we find hn = hI for all n E N, and we have the property (35). Now, we assume the existence of a number v E N with for all mEN. Let M be the set of all these numbers u. We consider the function 00 h(z) = L z" = L hnzn "eM n=I with h _ { 1 for n EM, n - 0 else . Obviously, these coefficients have the property (35), so that h(z) is a solution of (29) holo- morphic for Izi < 1. But in view of 1 ¢ M, h(z) has not the form (39) • 5 The polynomials Pm(z) Replacing (15) into (28), we find (40) This equation implies that 10 is an odd polynomial, d. (17) . Theorem 6. The polynomials Pm (z) have the property Pm (Zmk) = Pm-l (Z~k) +3Wmk Pm-l (Wmk) Zmk where ( 27rik ) (( k ) 27ri) Zmk =exp ~ ,Wmk =exp Pmk + 2m-1 """'3" for m ~ 1,0::; k < m, and P = Pmk is a solution of the congruence 2m - 1P + k == 0 mod 3 . Proof. Replacing (15) into (24), we obtain after simple changes Berg and Meinardus (41) (42) (43) with W v = )..vZ2/ 3 . For Z -+ Zmk we have W v -+ Wmk and )..V/Z l / 3 -+ Wmk/Zmk ' Moreover, we find easily lim 1 - Z2 m = { 3 in case?f (43) 1 - w~m-l 0 else , so that the theorem is proved • The condition (43) means that W~::-l = 1. The solutions J1. = J1.mk of (43) are Pmk = 0 for k == 0 mod 3 , Pmk = 1 for k == 1 mod 3 and m == 0 mod 2, or k == 2 mod 3 and m == 1 mod 2 Pmk = 2 for k == 1 mod 3 and m == 1 mod 2, or k == 2 mod 3 and m == 0 mod 2 For k = 0 we have ZmO = WmO = 1, so that (41) turns into According to Po(1) = 1, we obtain the solution (44) for m ~ 0, which also can be checked by means of (7) and (18). For k = 2m - 1 we have Zmk = -1 and Pmk = 2, hence Wmk = 1, so that (41) turns into and in view of (44) into the result (45) Berg and Meinardus 11 for m 2: 1, which also follows from (40) and (44). For k = 2m - 2 and m 2: 2 we have Zmk = i and J-Lmk = 1, hence Wmk = -1, so that (41) turns into Pm(i) = (1 +3i)Pm_l (-1) and in view of (45) into (46) for m 2: 2. Of course, Pm(-i) is the corresponding conjugate value. Generally, for k =2m- lq with q odd and m 2: t , the value Zmk is a root of 1 of order 2l , and both z;'k and Wmk are roots of 1 of order 2l - 1• Hence, we obtain by induction the Corollary 3. For every tEN and q odd there exists a complex number rql not depending on m with for m 2: t . Remarks. Let us mention that the functions (13) have also the representation 1 m-4 1 m-l r,,(z) fm(z) = (1 _ z)2 + 4(1 - z) + 4" ?; (1 + z2")2 (47) (48) where r.,(z) is a polynomial of degree 2"+1 -1 with integer coefficients, i.e. that the functions (49) have the form (50) In view of (39), the last term of (49) is a solution of (29), hence, (49) is also a solution of (24) with dminstead of 1m, and (50) can be proved by induction beginning with z-1 do(z) = 4(1 + Z)2 In the decompositions f ( ) = P2m(Z) + Plm(Z)m z (1 _ z2m)2 1 _ Z2m d (z) = r2m(z) rlm(z) m (1 + Z2 m )2 + 1 + z2m where the numerators are polynomials of degree 2m -1, we find according to (18), (49) and am+t ,,, - 2a m" = -(-I)"m("lam" with xm(v) defined by (5) that 2m_l 1 2m_l P2m(z) = L am"z", r2m(z) = -2 L (-ltm (" l am"zv ,,=0 ,,=0 (51 ) 12 Berg and Meinardus Another relation is ( ) _ P2.m+I(z) - 2P2m(z)(1 + Z2m ) r2m z - 2(1 _ Z2m) since, in view of (47) and Pm(Zlq) = P2m(Zlq), the numerator vanishes for z2 m = 1. This relation implies P2.m+v(z) =P2m(z)(1 +3z2m) +rom(z)(1 _ Z2m ) , where rOm(z) =P2m(z) + 2r2m(Z) are lacunary polynomials. Some examples are roo(z) = rOl(z) = 0 r02(z) = 6z , r03(z) = 6z2 , r04(z) = 6(9z9 +9z7 + ZS +Z4 +3z) Acknowledgement. The authors thank the referee for his helpful suggestions, in particu- lar for refering to the paper [81 . References [1] G. E. ANDREWS, The Theory of Partitions. Addison -Wesley Publ. Co. Reading, Mass ., 1976. [2] C. BClHME and G. SONTACCHI, On the existence of cycles of given length in integer sequences like Xn+l = xn/2 if X n even, and Xn+l =3xn +1 otherwise. Atti Accad . Naz. Lincei Rend . Cl. Sci. Fis . Mat. Natur.64 (1978) 260-264. [3] L. COLLATZ, About the motivation of the (3n + I)-problem (Chinese). J . Qufu Norm. Univ., Nat . Sci. 3 (1986) 9-11. [4] R. E. CRANDALL, On the «3x +1 « problem. Math. Compo 32 (1978) 1281-1292. (5) W. B. FORD,Studies on Divergent Series and Summability and The Asymptotic Develop- ments of Functions Defined by Maclaurin Series . Clesea Publ. Comp o New York, N. Y., 1960, p. 205-211. [6] L. E. GARNER, On the Collatz 3n + 1 algorithm. Proc. Amer . Math. Soc. 82 (1981) 19-22. [7] J. C. LAGARIAS, The 3x + 1 problem and its generalizations. Amer. Math. Monthley 92 (1985), 3-23. [8] G. LEAVENS and M. VERMEULEN, 3x + 1 search programs. Compo Math. Appl. 24 (1992) 79-99. [9] K. R. MATTHEWS, Some Borel measure associated with the generalized Collatz mapping. ColI. Math. 63 (1992) 191-202. [10] G. MEINARDUS, Uber das Syracuse-Problem. Preprint Nr. 67, Mannheim 1987. [11] R. TERRAS, A stopping time problem on the positive integers. Acta Arith. 30 (1976) 211-252. Lothar Berg Fachbereich Mathematik Universitat Rostock D-18051 Rostock Gunter Meinardus Fakultat fiir Mathematik und Informatik Universitat Mannheim D-68131 Mannheim Eingegangen am 1. Juni 1993 /ColorImageDict > /JPEG2000ColorACSImageDict > /JPEG2000ColorImageDict > /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 150 /GrayImageMinResolutionPolicy /Warning /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 150 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict > /GrayImageDict > /JPEG2000GrayACSImageDict > /JPEG2000GrayImageDict > /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /Warning /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 600 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict > /AllowPSXObjects false /CheckCompliance [ /PDFA1B:2005 ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile (sRGB IEC61966-2.1) /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description > >> setdistillerparams > setpagedevice