STRUCTURE THEOREM FOR (d,g,h)-MAPS 6 0 A.V.KONTOROVICHANDYA.G.SINAI 0 2 Abstract. The (3x+1)-Map, T,acts on the set, Π, of positiveintegers not n divisibleby2or3. ItisdefinedbyT(x)= 3x+1,wherekisthelargestinteger a 2k forwhichT(x)isaninteger. The(3x+1)-Conjectureasksifforeveryx∈Π J there exists an integer, n, such that Tn(x) = 1. The Statistical (3x+1)- 5 Conjectureasksthesamequestion,exceptforasubsetofΠofdensity1. The 2 Structure Theorem proven in [S] shows that infinity is in a sense a repelling point, giving some reasons to expect that the (3x+1)-Conjecture may be ] T true. Inthispaper,wepresenttheanalogoustheoremforsomegeneralizations of the (3x+1)-Map, and expand on the consequences derived in [S]. The N generalizationsweconsideraredeterminedbypositivecoprimeintegers,dand . g,withg>d≥2,andaperiodicfunction,h(x). ThemapT isdefinedbythe h formulaT(x)= gx+h(gx),wherekisagainthelargestintegerforwhichT(x) t dk a is an integer. We prove an analogous Structure Theorem for (d,g,h)-Maps, m and that the probability distribution corresponding to the density converges [ to the Wiener measure with the drift logg− d−d1logd and positive diffusion constant. Thisshowsthatitisnaturaltoexpectthattypicaltrajectoresreturn 1 totheoriginiflogg− d logd<0andescapetoinfinityotherwise. d−1 v 2 2 6 1 1. Introduction 0 1.1. The (3x+1)-Map and (3x+1)-Conjecture. Recall the definition of the 6 0 (3x+1)-Map, (see [L]). Take an integer x > 0, with x odd. Then 3x+1 divides / 2, so we can find a unique k >0 such that y = 3x+1 is again odd. In this way, we h 2k get a mapping T : x y defined on the set Π of strictly positive numbers not t a divisible by 2 or 3. W7−r→ite Π = 6Z++E, where E = 1,5 , is the set of possible m { } congruence classes modulo 6. : Foreveryinteger,x,with0<x<260,acomputerhascheckedthatenoughiter- v i ationsofthe (3x+1)-Mapeventuallysendxto 1 (see [L]). The naturalconjecture X asks if the same statement holds for all x Π: r ∈ a Conjecture 1.1 ((3x+1)-Conjecture). For every x Π, there is an integer n, ∈ such that Tn(x)=1. The Statistical (3x+1)-Conjecture asks the same question, except for a subset of Π of density 1. For every x, we can associate a value, which is the k used in the definition of T. When we apply T repeatedly, we get a set of k values, called the path of x. We shall call the ordered set of positive integers, (k ,...,k ), the “m-path of x,” 1 m denoted by γ (x), if these are the k values that appear in m repeated iterations m of T. Key words and phrases. 3x+1 Problem, 3n+1 Problem, Collatz Conjecture, Structure Theo- rem,(d,g,h)-Maps,BrownianMotion. 1 2 A.V.KONTOROVICHANDYA.G.SINAI E.g. T (17) = 3·17+1 = 13, so k = 2, and γ (17) = (2). T2(17) = T (13) = 22 1 3·13+1 =5, so here k=3, and thus γ (13)=(3), and γ (17)=(2,3). 23 1 2 Assume that we are given an m-path, (k ,...,k ). We can ask the following 1 m question: what is the set of x Π for which γ (x)=(k ,...,k )? m 1 m ∈ The answer is given by the so-called Structure Theorem, proven in [S]. The theorem states that if x Π has γ (x) = (k ,...,k ), then the next value in Π m 1 m ∈ whichwillhavethesamem-pathandcongruenceclassmodulo6isx+6 2k1+...+km. Inother words,there is some firstx Π=6Z++E, callit x , whichha·s γ (x)= 0 m ∈ (k ,...,k ). Writing x = 6 q+ε, with ε E, we get all x with the same ε and 1 m 0 · ∈ m-path from the sequence xp =6 2k1+...+kmp+q +ε. The theorem tells us how to solve uniquely for q given the m(cid:0)-path and ε, an(cid:1)d shows that q < 2k1+...+km, so the representationof x is unique. p E.g. Let k = 2, k = 3, and ε = 5. Then x = 17 = 6 25 0+2 +5, and we 1 2 0 · know that γ (17) = (2,3). Look at x = 6 25 1+2 +5(cid:0)= 209: T(cid:1)(209) = 157, 2 1 · with k = 2, and T2(209) = 59 with k =(cid:0)3, so γ (2(cid:1)09) = (2,3). We can verify 1 2 2 that there are no elements of Π between 18 and 208 that are congruent 5 modulo 6 and have the 2-path (2,3). Moreover,theStructureTheoremtellsusthatiftheimageofx isy =Tm(x )= 0 0 0 6 r+δ, with δ E (since y is also in Π), then we get the next image by adding 0 · ∈ 6 3m. Inotherwords,ify istheimageofx ,theny =Tm(x )=6(3mp+r)+δ. p p p p · The theorem also solves explicitly for r and δ given the m-path and ε, and finds that r <3m. E.g. T2(17)=5=6 32 0+0 +5, and T2(209)=59=6 32 1+0 +5. · · The Structure Theor(cid:0)em also sh(cid:1)ows that infinity is in a sens(cid:0)e a repell(cid:1)ing point. This gives some reasons to expect that the (3x+1)-Conjecture may be true. In this paper, we present the analogous theorem for some generalizations of the (3x+1)-Map, and expand on the consequences derived in [S]. 1.2. The (d,g,h)-Maps and (d,g,h)-Problem. The generalizations we consider are a particular case of maps proposed in [FR]. They are determined by positive coprimeintegers,dandg,withg >d 2,andaperiodicfunction,h(x),satisfying: ≥ (1) h(x+d)=h(x), (2) x+h(x) 0(modd), ≡ (3) 0< h(x) <g for all x not divisible by d. | | The map T is defined by the formula gx+h(gx) T (x)= , dk where k is uniquely chosen so that the result is not divisible by d. Property 2 of h guarantees k 1. The natural domain of this map is the set Π of positive ≥ integers not divisible by d and g. Let E be the set of integers between 1 and dg that divide neither d nor g, so we can write Π = dgZ+ +E. The size of E can easily be calculated: E =(d 1)(g 1). | | − − In the same way as before, we have m-paths, which are the values of k that appear in iterations of T, and we again denote them by γ (x). m The original problem corresponds to g =3, d=2, and h(1)=1. The (3x 1)- − problem corresponds to g = 3, d = 2, and h(1) = 1. The (5x+1)-problem − corresponds to g =5, d=2, and h(1)=1, and so on. STRUCTURE THEOREM FOR (d,g,h)-MAPS 3 The Structure Theoremfor(d,g,h)-Mapswillbe slightly different,inthatgiven an m-path, (k ,...,k ), and congruence class, ε, modulo dg, we do not have a 1 m unique x . Instead, we have (d 1)m values of what was x in the original case, 0 0 − which we will denote by x(i), with i=1,...,(d 1)m. Eachof these can be written 0 − as x(i) = dg q(i)+ε, with q(i) < dk1+...+km. Then we get every x with the given 0 · m-path by adding dg dk1+...+km. In other words, letting · x(i) =dg dk1+...+kmp+q(i) +ε, p (cid:16) (cid:17) we get every x Π with γ (x) = (k ,...,k ) and x ε(moddg) in the set m 1 m ∈ ≡ x(i) . p n op≥0,1≤i≤(d−1)m Here is the precise formulation of the Structure Theorem for (d,g,h)-Maps. Theorem 1.2 (Structure Theorem). Given an m-path, (k ,...,k ), and ε E, 1 m let k = k + ... + k . Then there exist (d 1)m triples, q(i),r(i),δ(i) ,∈i = 1 m − 1,...,(d 1)m, with 0 q(i) <dk, 0 r(i) <gm, and δ(i) E,(cid:0)such that (cid:1) − ≤ ≤ ∈ x Π:x ε(moddg), γ (x)=(k ,...,k ) = dg dkp+q(i) +ε . m 1 m { ∈ ≡ } n (cid:16) (cid:17) op≥0,1≤i≤(d−1)m Moreover, Tm dg dkp+q(i) +ε =dg gmp+r(i) +δ(i). (cid:0) (cid:0) (cid:1) (cid:1) (cid:0) (cid:1) The proof of the theorem is given in the next section. In section 3, we prove that the probability distribution corresponding to the densityconvergestotheWienermeasurewiththedriftlogg d logdandpositive −d−1 diffusion constant. This shows that it is natural to expect that typical trajectories return to the origin if logg d logd < 0 and escape to infinity otherwise. This − d−1 question is discussed in more detail in section 4. 2. Proof of the Structure Theorem The proof goes by induction on m. At each stage, we assume x has the given m-path and modulo class, and write x = dg dkp+q + ε and y = Tm(x) = dg(gms+r)+δ. Thiscanbedoneforanynumb(cid:0)er,since(cid:1)wearesimplywritingout the modulo classes. After some algebra, we come to some equation for the triplets (q,r,δ), and show that it has (d 1)m solutions. − 2.1. Case m=1. Say we are given a 1-path, (k), and let us take an ε E. Write ∈ x=dg t+ε, and assume that x has the 1-path, (k). One can further break t into · the form: t = dkp+q, with 0 q < dk. Let y = T(x), so by our assumption, ≤ dky = gx+h(gx). By periodicity, h(gx) = h(gε), so since ε is fixed, h does not depend on x, and is fixed. Thus we will write just h for h(gx) from now on. Since y Π, we can write y = dg t′ +δ for some δ E, and expand t′ = g s+r, ∈ · ∈ · for 0 r < g. The first step of our analysis is to show that s = p. We write ≤ gx+h=dky, and substitute for x, y, t,and t′: g dg dkp+q +ε +h=dk(dg (g s+r)+δ). · · · (cid:0) (cid:0) (cid:1) (cid:1) We expand this to see: g2dk+1 p+ dg2q+gε+h =g2dk+1 s+ dk+1gr+dkδ . (2.1) · · (cid:0) (cid:1) (cid:0) (cid:1) Next, we apply the following simple Lemma. Lemma 2.1. If a b+c=a b′+c′ with 0 c,c′ <a, then b=b′ and c=c′. · · ≤ 4 A.V.KONTOROVICHANDYA.G.SINAI To apply the lemma (with a = g2dk+1), we need to show that the parts in parentheses on both sides of (2.1) are contained in 0,g2dk+1 1 . We will derive − upperandlowerboundsfortheleftside,andleaves(cid:2)imilarcalculat(cid:3)ionsfortheright side to the reader. Consider the lower bound of the left side. Since q 0, ε 1 and h g+1 ≥ ≥ ≥ − (by Condition 3), we have that dg2 q+gε+h g 1+( g+1)=1, · ≥ · − and thus is positive. Forthe upper boundofthe leftside,we noticethat q dk 1,ε dg 1(since ≤ − ≤ − ε E) and h g 1. So ∈ ≤ − dg2 q+gε+h g2d dk 1 +g(dg 1)+(g 1) · ≤ · − − − = g2dk+(cid:0)1 1. (cid:1) − TheLemmagivesusthatp=s,andfromnowonwewritejustp. Wewant • to characterize q, r and δ, showing that they are independent of p. To continue, we recall that the Lemma implies that the parts in parentheses of (2.1) also concur. So: g2d q+gε+h=dkgd r+dkδ. (2.2) · · The next step is to break δ into δ = δ′g+δ′′, with 0 δ′′ < g. Since δ E, we ≤ ∈ have δ <dg, implying 0 δ′ <d. We now look at (2.2) modulo g to solve for δ′′: ≤ dkδ′′ =h(modg). (2.3) Since g and d are relatively prime, dk has a multiplicative inverse in (Z gZ)∗, \ meaning δ′′ is uniquely determined. Exactly one of the d possible values of δ′ will make δ =δ′g+δ′′ divisible by d, and we throw this value away since δ E. ∈ Thisleavesuswithd 1possiblevaluesforδ,whichwedenotebyδ(1),δ(2),...,δ(d−1). − It suffices to solve (2.2) uniquely for q(i) and r(i) given δ(i). Now we assume we have fixed δ(i), and rearrange (2.2), adding a superscript to q and r to correspond to δ: dkδ(i) gε h g q(i) dkr(i) = − − =v. · − dg Everything on the right hand side is known, so v is now just an integer (and independent of p). We solve for q(i) and r(i) by applying the Chinese Remainder Theorem to the equation g a dkb = 1, then setting q(i) = v a moddk and · − · r(i) =v b(modg). (cid:0) (cid:1) · Having found the triplets q(i),r(i),δ(i) , we are done with the case m=1. • (cid:0) (cid:1) STRUCTURE THEOREM FOR (d,g,h)-MAPS 5 Summarizing the first step of the induction, we pick some ε E, assume x Π ∈ ∈ is ofthe formdg t+ε, andwrite t=dkp+q. Under the same assumptionsfor the · image, y =T (x), we write y =dg t′+δ and t′ =gp+r. We find that δ is unique · modulo g, and there are d 1 values, δ(1),...,δ(d−1), which δ E may take. For − ∈ eachone, we solve for q(i) and r(i). All of the calculations depend only onk and ε. 2.2. Induction on m > 1. For m > 1, the induction goes as follows. To know which x have a given m-path, (k ,...,k ), we first assume we know the answer for 1 m the (m 1)-path, (k ,...,k ). 1 m−1 − Let k =k +k +...+k , and assumeby the induction hypothesis that there 1 2 m−1 are(d 1)m−1valuesforthetriplet(q ,r ,δ )whichsatisfyourequations. m−1 m−1 m−1 − Fix one such triplet, pick any integer, p , and set x=dg dkp +q +ε, m−1 m−1 m−1 and y = dg gm−1p +r +δ . Then we have γ (cid:0)(x) = (k ,...,k(cid:1) ), m−1 m−1 m−1 m 1 m−1 and y =Tm−(cid:0)1(x). Here we writ(cid:1)e pm−1 instead of just p to distinguish from the p we will have in the next paragraph. The triplet (q ,r ,δ ) is still gotten m−1 m−1 m−1 independently of p . m−1 We can alternatively break x into x = dg dk+kmpm+qm +ε for some qm < dk+km and also write z = Tm(x) = T (y) = d(cid:0)g t+δm, with(cid:1)t = gms+rm. The · key idea is to find the d 1 possible values for δ E, and with each we solve for m − ∈ the corresponding q and r , knowing q , r , and δ . We will again see m m m−1 m−1 m−1 that p =s and that (q,r,δ) do not depend on this value. m Since z = T (y), by assumption, we have dkmz = gy +h(gy), (again let h = h(gy)=h(gδ )) which expands to: m−1 dkm+1gm+1s+dkm+1grm+dkmδm =dgm+1pm−1+g2drm−1+gδm−1+h. (2.4) Remembering the two expressions for x, and setting pm = dkmp1+p2 (with 0 ≤ p2 <dkm), we write: x ε dk+kmpm+qm = d−g =dkpm−1+qm−1 = dk+kmp1+dkp2+qm−1. We easily see that 0 dkp2+qm−1 <dk+km, so we again use the Lemma to find: ≤ p = p , (2.5) m 1 q = dkp +q . (2.6) m 2 m−1 Returning to (2.4), we expand: dkm+1gm+1s+ dkm+1grm+dkmδm =dkm+1gm+1p1+ dgm+1p2+g2drm−1+gδm−1+h . (cid:0) (cid:1) (cid:0) (cid:1) Following the same techniques as before, we bound the parts in parentheses on bothsidesbetweenzeroanddkm+1gm+1,andapplythe Lemma. This givesusthat p =p =s, and that m 1 dkm+1grm+dkmδm =dgm+1p2+g2drm−1+gδm−1+h. (2.7) Again looking modulo g and setting δ =δ′g+δ′′, we solve: m δ′′ gδ +h(modg), m−1 ≡ 6 A.V.KONTOROVICHANDYA.G.SINAI which again gives us d choices for δ′, one of which we throw out because δ E. m ∈ Rearranging (2.7), we get: gmp2−dkmrm = dkmδm−dg2rmd−g1−gδm−1−h =v From here, we solve gma dkmb = 1 and set p2 = a v moddkm and rm = − · b v(modgm),soq =dkp +q . Wehave(d 1)valueso(cid:0)f(q ,r ,(cid:1)δ )derived m 2 m−1 m m m fr·om (d 1)m−1 values of (q ,r ,δ ),−so there are a total of (d 1)m m−1 m−1 m−1 − − triplets, consistent with the induction hypothesis. Now everything in the triplet (q ,r ,δ ) is defined, and we are done. m m m 3. Brownian Motion of (d,g,h)-Paths In [FMMT],[LW], it is assumed that the (3x+1)-Map behaves as a geometric Brownian motion, and a stochastic model is built from which other conjectures relating to the problem are derived. Here, we prove that the generalized (d,g,h)- Maps do indeed have this behavior. In order to consider sample (d,g,h)-paths, we must first establish a versionof a probability measure on Z+. The only natural way to do this is through density: Definition 3.1. For A Z+, define ⊂ A [1,n] Π A [1,n] Π dg P (A)= lim | ∩ ∩ | = lim | ∩ ∩ | , (3.1) n→∞ [1,n] Π n→∞ n · E | ∩ | | | provided the limit exists. A nice consequence of the Structure Theorem is that if we want to consider the set of x that follow a certain m-path, they all fall in one of several arithmetic progressions,and so these sets have a density. Partition the interval [0,1] by: 0 = t < t < ... < t = 1. Fix m and let 0 1 r mi = tim . For any x, let xi =Tmi(x). ⌊ ⌋ Theorem 3.2. The properly normalized path lnx converges as m to a i Brownian Path with drift lng d lnd. More precisely, → ∞ − d−1 lnx lnx (m m ) lng d lnd lim Px:ai < i+1− i− i+1− i (cid:16) − d−1 (cid:17) <bi, with i=0,...,r 1 m→∞  d mlnd −  (d−1)2 q   q b0 b1 br−1 e(−12 ir=−01u2i) Za0 Za1 ···Zar−1 (2Pπ)r2 du0du1···dur−1. Proof. By an extension of the Structure Theorem, we know that xi =Tmi(x) can be expressed as xi =dg gmidkmi+1+...+kmp+qi +δi. Then (cid:0) (cid:1) lnx =m lng+(k +...+k )lnd+lnp+O(1), (3.2) i i mi+1 m STRUCTURE THEOREM FOR (d,g,h)-MAPS 7 andsince weareinterestedinquestionsaboutdensity, x is large,sopis large,and i thus O(1) is non-essential. Then we can rearrange(3.2) to: lnx m lng (k +...+k )lnd = lnp i− i − mi+1 m = lnx m lng k +...+k lnd, i+1− i+1 − mi+1+1 m (cid:0) (cid:1) from which we get: d d (m m ) lnd k +...+k lnd=lnx lnx (m m ) lng lnd . i+1− i d 1 − mi+1 mi+1 i+1− i− i+1− i (cid:18) − d 1 (cid:19) − (cid:0) (cid:1) − (3.3) Since the set of x consists of precisely (d 1)i arithmetic progressions, each with i − step dg dk (where k =k +...+k ), we use (3.1) to find that 1 m · 1 dg P γ (x)=(k ,...,k ),x ε(moddg) = (d 1)m. { m 1 m ≡ } dg dk E − · | | This holds for each ε E, so we see that ∈ P γ (x)=(k ,...,k ) = E P γ (x)=(k ,...,k ),x ε(moddg) m 1 m m 1 m { } | |· { ≡ } (d 1)m m (d 1) = − = − . (3.4) dk dkj jY=1 This shows that we can consider the k as independent identically distributed ran- j dom variables, with exponential distribution having the parameter 1. Thus the d expected value, E[k +...+k ] = n P k +...+k =n 1 m 1 m · { } nX≥m = n P (s +1,...,s +1) 1 m · { } nX≥m s1+...+smX=n−m,si≥0 1 = (d 1)m n − dn nX≥m s1+...+smX=n−m,si≥0 n n 1 = (d 1)m − − dn (cid:18) m 1 (cid:19) nX≥m − d = m. d 1 − Similarly, we can calculate that Var[k +...+k ] = d m. So by the Central 1 m (d−1)2 Limit Theorem, lim P k1+...+km− d−d1m (a,b)= b e−u22 du. m→∞  d m ∈  Za √2π (d−1)2 q   8 A.V.KONTOROVICHANDYA.G.SINAI And by (3.3), we have that lnx lnx (m m ) lng d lnd P  i+1− i− i+1− i (cid:16) − d−1 (cid:17) (ai,bi)  m d lnd ∈  · (d−1)2 q   q d (m m ) k +...+k P d−1 i+1− i −(cid:0)d mim+1 mi+1(cid:1) ∈(ai,bi), (d−1)2 q which convergesexactly as claimed. Since the k are independent, the increments, i lnx lnx are as well, andwe havethe statementabout the convergenceofour i+1 i distribu−tions to the Wiener measure. (cid:3) 4. Asymptotic Behavior of Typical Trajectories The previous section proves that the probability distribution corresponding to thedensityconvergestotheWienermeasurewithdriftlogg d logd. Sincedand −d−1 g arerelativelyprime,therearenovaluesofdandg forwhichlogg d logd=0, −d−1 and thus every (d,g,h)-Map has a non-trivial drift. Therefore, the asymptotic behavior of typical trajectories depends entirely on the sign of the drift. When the drift is negative, infinity is a repelling point. In the opposite case, typical trajectories escape to infinity. For the original (3x+1)-Map, the drift is log3 − 2log2<0, and so as a special case, we get the result found in [S]. Inthe literature,the stoppingtime ofanintegerx isdefined asthe firstpositive integer, n, such that Tn(x)<x. If n does not exist, we say that x has an infinite stopping time. In [E] and [T76],[T79], it is independently proven that for the (3x+1)-Map, the density of integers with a finite stopping time is 1. This paper provides another proof of this statement. Acknowledgments: The first author thanks L. Kontorovich and S. Payne for discussionsandcriticism. Thesecondauthorthanksthe NSFforfinancialsupport, grant DMR-9813268. References [E] C.J.Everett,Iterationofthenumbertheoreticfunction f(2n)=n,f(2n+1)=3n+2, Adv.Math.,25 (1977), 42-45. [FMMT] Feix, M.R.; Muriel, A.; Merlini,D.; Tartini, R. The (3x+1)/2 problem: A Statistical Approach, in: Stochastic Processes, Physics and Geometry II, Locarno 1991. World Scientific(1995), 289-300. [FR] Feix, M.R.and Rouet, J.L. The (3x+1)/2 problem and its generalization: a stochas- tic approach, Proceedings of the International Conference on the Collatz Problem and RelatedTopics(2001). [L] Lagarias, J.C., The 3x+1 Problem and Its Generalizations, American Mathematical Monthly,Vol.92,Issue1(Jan.,1985),2-23. STRUCTURE THEOREM FOR (d,g,h)-MAPS 9 [LW] Lagarias, J.C., and Weiss, A. The 3x+1 Problem and: Two stochastic models, Ann. Appl.Prob.2(1992)229-261. [S] Sinai,Ya.G.,Statistical (3x+1)-Problem,(2002), preprint. [T76] R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976), 241-252. [T79] R.Terras,Onthe existenceof a density,ActaArith.35(1979), 101-102. MathematicsDepartmentof Princeton University,Princeton, NJ,08544 USA Current address: Mathematics Department of Columbia University, New York, NY, 10027 USA E-mail address: [email protected] MathematicsDepartmentof Princeton University,Princeton, NJ,08544 USA E-mail address: [email protected]