The 3x+1 Problem: Status and Recent Work Part 1

if it's odd you want to multiply by three and add one in either case take the resulting number and then iterate so for example if you start with three that's odd goes to ten by the mapping that's even cut it in half and so on and so forth and you see that this four to one pattern will just get a rate forever so the question is to each of the positive integers eventually iterate to one that's the problem I've explained it to each of my children when they were seven or eight years old they weren't going for about a day and moved on I got every one and I'll say something about the history of this problem as well all right so first there's two or three different notations which are used in the literature the old one is C of X this is just as I described it on the last slide but we can compress the dynamics a little bit if you start with X is an odd number you get this but if X is odd you can see three X plus one will be even so if you know your next step will be dividing by two so why don't we just divide by two right away and that will compress the dynamics so you can see this is the old iteration I had and in the compressed dynamics it just makes our life a little a little tinier so any positive integer must iterate under this map T to one of the following so now instead of having four two one four two one forever now it will just oscillate between two and one that's called the trivial cycle and we expect that's the conjecture that everything will eventually enter trivial cycle but there could be a non-trivial cycle and I'll have something to say about that or you could have some orbit which marches off to infinity then we'll march off on monotonically you can show that any starting none any starting on number has to get an even eventually and so it will come down but but it could kind of do do this kind of thing and and keep growing in the limit I should say so most of the papers that are written on this topic use the t form the compressed dynamics that I just mentioned some paper a few papers still use that older notation and then a very few papers use the most quote-unquote optimally compressed notation he will take it an odd number sorry if your number is even you don't just divide by 2 you divide by as many twos as possible to get it down to an odd and so people just look at the dynamics on the odd integers under this mouth but counting exactly how many tubes will divide into it is not a neat process and so it makes it harder to do analysis on okay well as you might have guessed some people have looked of numerical investigations I have some various records to report in 2000 and using 14.4 cpu years just a little over ten to the seventeen so all numbers up to there were check yes they do iterate to one eventually in 2003 there's a dutch mathematician who who set up a distributed computer project and so you know people will come in and check a certain range and he's gotten it a bit higher about twice as high and then the same person we work of this he's gone quite a bit higher still this took eighty one point one cpu years but if you're going to infinity this still isn't very so we still have a long ways to go actually when it was first up there I was very impressed cuz I thought that we were going to say if n is bigger than some number like excuse I work sometime we don't know what explicitly then the conjecture is true I don't know it's such a result I'm not about now I understand larges yes the matter what larges all get behind the people that's right and just by curiosity when you start with the numbers like that how big the steps well so I mean let me show you an example so even so there's three expressions which are used in measuring what happens with the story number so don't read all this let me just describe it in many terms so stopping time means you start with the number N and the stopping time is the number of iterations you need to get below where you started the minimum number of steps so if you started with an even number the stopping time is one okay because you will go down the total stopping time of n is the number of steps it takes to get to one the minimum number of steps and of course if it never reaches 1 if the conjecture is false then the total stopping time will be infinity for that starting point and then the height is the maximum you hit before you come down and even with a modest number like 27 it takes 96 iterations before you jump below 27 111 iterates to get to 1 and you can get as high as nine thousand two hundred thirty-two so this is part of what makes this a problem so difficult is there's not really nice constraints about what can happen on the innards they can really kind of seem to get out of control until they maybe start collapsing down to what they expect them to you just remember Steven Weber you've divided 3x plus 1 by 2 yes yes and that's the one 96% of the slides we'll worry about ok so just keep that that napping of mine saw the stopping time and again there's a lot of nomenclature on here what is the take-home message on the slide this gaming is basically saying almost all integers have a finite stopping time almost all integers will get below where they started now that's not all it's almost all in a density sense so this is I would say probably about the strongest result there is on the 3x plus 1 problem one thing that drives people like me bananas is that as opposed to most other well-known conjectures that have pretty solid partial results at least I feel the 3x plus 1 problem as almost no good partial results and this I would say is probably one of the strongest if not the strongest partial results um if there was some kind of randomness going on and this is it's a little Gilles article into the problem because this is a completely deterministic problem that people have used stochastic approaches to look at it and to see some kind of order if there was some kind of if you've iterated for a while and you've gotten so mixed up you don't know which way you're going you have a 50/50 chance of going up for download at each step if you reach that point that with this kind of quote/unquote randomness it takes approximately 9 to 10 steps to get below where you started and this matches these this matches decently well with what is experimentally serve so you know you would expect all right on average it takes this many steps to get below where you started if we could prove that all numbers have a finite stopping time then by induction you would be done because if you get finite number of steps below and you just keep going down and you're done everything has to get to one but this is only assuming a certain kind of randomness is built in the total stop you obviously do have your is table that's right there are a huge to guard but mostly they end up to me because it looks pretty random like that's right I've got in here again Dornan I have to say but it's not approved okay so I said this yesterday I did it okay all right but not formal proof this total stopping time let me remind you that's the number of steps starting it in Sigma infinity event is the number of steps you need to get down to one the minimum number of steps and people have looked at what this called gamma and the stopping time ratio we're going to divide that by the natural log of N and they can get some kind of bounds on this kind of thing log of 2 and log of 3 come up with some frequency for people who are trying to do analysis on this problem not surprisingly because we are more or less multiplying by 3 and dividing by 2 our n is the ratio of the number of auditor s versus all all the iterates we've gotten up to a point so we've got something there's a lower bound and there's an upper bound for this for the stopping time ratio so something times log of n kind of makes sense for the total stopping time but again we just have these kind of rough rough heuristics going on here more specifically this is what I was saying a moment ago suppose you had roughly a 50 the chance of going up or down if you picks up large some large number and then watch what happens then that that ratio I talked about theoretically is exactly this value it's been shown with stochastic models that the lip soup of these guys is bounded by this quantity and the closest that come to it with this particular starting number because people have done a lot of experiments with this particular starting number that's about the closest we can get to 41 so and this is pushing kind of this randomness as far as smart I have seen people like Jeff lick areas and happily he didn't work on this somebody called this a global statistic suppose I started the value of a 1 and it takes me P iterates to get down to 1 so let's label these numbers a1 a2 up to AP and we'll create this expression here notice it's a quadratic polynomial of the A's on top and on the bottom and the authors were able to prove that this ratio no matter what you start with has to lie between these two fractions which are relatively close and these bounds the lower and upper bounds are sharp because if you start with either of these particular starting numbers for a given K as K or n tend to infinity you approach the lower bound for the bound but you know this is a pretty tight gap here so it's suggesting there is some order going on here there is some order in the total stopping time maybe there's even better cooling for global statistics out there let me talk about the origin of this problem a little bit so it's traditionally credited to Lothar Colin's he was at on board and colas apparently was interested in graphs graph theory problems and he was looking at various graphs and directed perhaps and looking at cycles within that and he had he had a particular graph and everything seemed to land in one cycle and so he wanted to come up with something simpler he was he looked at this particular function which is similar spirit to our T function a little more complicated in each of these expressions depending on which modular class you're in where it's out to be an integer and he saw that this seemed to be complicated so he said what is a simpler problem I can build the simplest problem I can build that still captures the complex dynamics that he's seen here and that's when he got to this so-called 3x plus 1 function so collapse never published anything on it because as he said he obtained no results and I would say join the club there's lots of people who worked on this in a fun more results but there are other names for this problem sometimes called posses algorithm Syracuse problem because this problem made the rounds in different schools ok but it's got all kinds of different names weights it's a little bit a little bit funny sir Brian Thwaites is a British mathematician and he was a teacher in the 50s and he claimed it was a hot summer day and the students were bored and he had to kind of keep them motivated so he thought about this exact problem the three X plus one problem and he gave it to his students just to work they had fun before the class was over so he claims to have originated it and he could say the exact hour of a particular day so he claims to be the author of it nobody really thinks of Thwaites now everybody credits it to Co Lots but it didn't stop the weights from sometime in the early nineties writing a paper called my conjecture also got an algorithm I know that's funny well maybe hostage doesn't have any problems just the number three Possible's yeah yeah yeah product theory I I think it's the aeronautic theory yeah yeah so I mean this problem I'm gonna run becoming a popular guy stayed right came to know not originated not originated but perhaps or died so somebody would hear it and there's this honey there's a sec talks about it yeah so Stan poem was the same he didn't claim preventive but he popularized it so there's a funny quote about the popularization for about a hunt everybody at Yale worked on it with no results similar phenomenon to happen at Chicago the joke was made this problem Spartacus I'm having a reason and to some extent is true um if you keeping in line with Colossus motivation there's the so-called culottes graph and this is a sketch do to codons and you can see he's writing in German here to I am two signs for one karate for four and on a half and four and even and he's got his little kind of tree here or for graph which is generating a clear portion of of that can be written like this but of course you know this trees going on forever and so you need a and any other Indian package right right so he yeah he's here he you see the cycle he's using the see map that I talked about on the first slide and he's generating it backwards and he was interested in our magic 27 that I talked about and you see he got so much he's got dots in here and so on eventually comes down all right predecessor says so one significant piece of analysis that a German mathematician in Guto veil she were gone he looked at footer the so-called predecessor sets so again let me try to say this without worrying about all the notation come with a number a what are all the numbers above it which will eventually hit a that is if you make the graph like I get on the last slide what is all the order all the branches and leaves about that point so that's the predecessors of a and then this Z sub a of X is the predecessors of a which are below a value X and at some point some people started looking at Z sub 1 of X that is what are the numbers which iterate to one but are below X and the question is could we get this greater than or equal to X to the C for some positive variable see in 79 it was show there exists a positive C so that this holds for X sufficiently large and then in 90 it was sharpened that I can get an exact value of C point two five and then higher and higher and higher and this is the best that I know up-to-date so we're trying to get these again it's like saying how much of the tree do I know will be coming to one and so to see is one thing important as well eventually I guess so yeah I mean for him can see equal yeah I was going see was one for sufficiently large yes that would prove it so you have a possible disaster yeah but it's but plenty for is kind of far away from one we think it's close to one but it's still to me this in a certain sense is no better than the density result I mentioned earlier okay some people have tried looking at the problem by reducing the problem to different residue classes so if I can prove the conjecture if I start with numbers in certain residue classes would that be sufficient to prove it for all starting numbers so obviously if I prove it for all odd numbers I will be done if you do it for four K plus 1 numbers going through into what mod floor you'd be done for k plus three this guy and for any J you can prove this guy since I can make this J's largest they want I can get the density to be as small as I like but still all of these have positive densities so a question which which hung around for some time was is there some set of zero density which would be sufficient if you can prove 3x plus one on that set it proves it everywhere so he was a zero of density type result but it involves a different function more complicated function so this function R of n says if 11 divides n then just return n over 11 if 15 divides in and none of the above and not this case then do this to it and you have this finite number of branches that come out so it's a much more complicated function but the claim was the 3x plus 1 conjecture is true if and only if the orbits of this function if you start at any power of two iterates to the number of two and since this set has zero density then this is zeroed in this is like a zero density result if I can prove that the are orbits of any power of two eventually gets to I would be done and this set is zero density the problem though is that this is a much more complicated function to evaluate even if you start with two to the three equal to eight it takes 50 iterates to get down to two so whether this is really helpful is not really quite clear um what's helpful with this approach though for now is it gets rid of that plus one part 3x plus 1 the plus one you know it's just a pain in the ass to deal with all right you try iterating it and if you didn't have the plus one you're just multiplying by threes and dividing by twos and you've got some you've got some structure you can deal with but that plus one just just creates a lot of headache this at least you've got lit up the plus one part but all these notas create problem with analysis so alright let's move on let's talk about cycles remember I said earlier that we have two options we either approach the trivial cycle one two we approach a non-trivial cycle or we approach infinity so let's talk about cycles so suppose I have a cycle of points that is I started one number in the cycle and after fun at number of iterations I come back to where I start if I divide it in the even number of terms the even terms and the odd terms in the cycle here's a cute little exercise if you you want to feel like you're making progress on this problem this is not hard to prove okay that takes a little bit of that through some the even terms in this cycle that's equal to the sum of the odd terms plus the number of terms and there are other results if you have a cycle then you must have some integers and be able to express a number like this the only circuit is the trivial circuit the circuit of one circuit means you just go up and you just come down and you're done and you've entered a cycle a two circuit means you go up and down and up and down and then you can get back to where you started with so it's it's been shown this is the only one circuit there are no two circuits but you know there's lots of other stuff to worry of other stuff with cycles so this is this is this is all I would say another very interesting helpful result related to the conjecture so if you have a cycle at the smallest term was M small down and the largest term was capital amla then you can found the total number of terms in the cycle divided by the number of on terms by these two quantities here so this tells you if you have a large cycle if you are if the terms were very big in your cycle this tells you that this ratio is approximately log of three bays - this is an irrational number and so people have used die Fenton approximation to see what can I say about this ratio and it forces the number of terms in the cycle to have different forms this was a result of 93 this was a stronger result in 97 and these forms which were generated were based on the lower bounds for if I know if I have a cycle I show this numerical computations from before so the numerical computations help generate the size of these numbers if we have even higher lower balanced - give me the bigger numbers coming up here so amongst other things this tells me if I had a non-trivial cycle the length has to be at least two hundred and seventy two million long so if some of you are trying to scribble to find an example on the back of an envelope you need a pretty big job all right the problem has had a lot of the lure that's not to say Paul there is said that the MAGIX is not yet ready for such things and he's quoted this up good people have asked him about it asked him about it after such clothes and he would say things like oh it's hopeless absolutely hopeless and he refers to such problems as diseases brennick yeah yeah well I know of people who have really consumed a lot of time on this problem without really getting too far so I saw there are prices Hey so especially if there are students in the audience you are aware like the playmat Institute has some prize problems things like for the Riemann hypothesis P versus NP existence of solutions to have your Stokes equations but you may not know that there is prize money for the three x plus one problem all there is offered $500 himself and remember sir Brian Thwaites he offered a thousand British pounds now the first two have passed away and I'm guessing the third one has by now so there might not even be any I think once Adam said a long time ago he would honor all their dishes but I don't even know he's still not stuck and so don't don't hold your breath I think all right there's a so called week 3 X plus 1 problem so you start with you build a multiplicative semi-group that's generated by these fractions here and of course you see the 3 and the 2 and as that 3x plus 1 smell to it so you you take these numbers you've built a multiplicative semi-group the we X week 3x plus one problem says that the set s contains every positive integer and it's been proven that the 3x plus 1 conjecture applies the leaked 3x plus 1 conjecture I hope the graphic helps you see what I think of this and relative strengths of these two different problems and the weak 3x plus one problem was proven in 2006 all right well at least at least it's not false because I would imply this as false and nobody leaves this is false and so what what do you do when you can't prove something well but some people including myself have tried to extend the problem to larger spaces so instead of just working on the positive integers what if we just look at all the integers keep the same map but now you're just allowing it to work on all the integers and you have three new cycles you have this very simple one you have this with three terms and this one with a few more terms and it's conjectured that there are no other cycles no other cycles on all the integers besides these three and the one with one two that's it and I'll just point out that going to the negative integers working them is equivalent to looking at the so-called 3x minus 1 problem and I'll talk about that kind of thing in a moment or two extending beyond the integers a few people have looked at the ring of to attak integers and so you've got the same kind of map as before and it's shown that from a dynamical perspective this map is conjugate to a shift map via this conjugacy and i don't want you two to get stuck on that too much but there's been some interesting work to do with looking at this conjugacy and now if you look at rational numbers whose in reduced form Houston on who have odd denominators it ends up the 3x plus 1 problem is equivalent to these other kinds of things so some stuff with this tool attic analysis have been studied but as far as I understand it's kind of come to a standstill for several years now and not more progress is being done but this is a reformulation in a different sense how about extending into the whole real line this is from a paper that I wrote in the mid-90s so my idea was we know that when X is heave and I divide by 2 when it's odd I want this expression so I'm going to interpolate this this branched function with cosine and sine and so on the integers I get exactly what I want but I've got a function that works off the integers as well for any real number so this map has certain interesting properties the reason I wanted to do this is because there's a lot of its well developed area studying real dynamics and I thought I can use the tools of real dynamics to help me get some information about the interests of this mapping so any cycle on the positive integers you can choose locally attractive if you have a cycle close by real numbers have to get sucked into it there appears to be only only two attracting cycles there's the trivial cycle and then there's this other funny two cycle which is off the integers for people who know dynamics this map is what we call negative schwartzie and derivative which is important it means that we only need to be looking at the critical points of this function to understand the long-term dynamics and indeed I just could show that the 3x plus 1 conjecture is equivalent to showing that the critical points of this function of all iterate 2 1 2 unfortunately there are an infinite number of critical points so is this any easier than studying the original problem I did some more analysis and I maybe in the intro

Channel: Experimental mathematics

Views: 40,394

Rating: 4.826087 out of 5

Keywords: Rutgers, Colloquium

Id: t1I9uHF9X5Y

Length: 29min 59sec (1799 seconds)

Published: Mon Apr 15 2013