
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
August 26th, 2014, 03:22 AM  #1 
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  Collatz, a pigeonhole approach
I've been exploring the Collatz conjecture for a long while. I've put up a post here: Prime Numbers: Collatz  a pigeonhole estimation approach.. It's an approach that is somewhat statistical, looking at patterns generated by a a function that identifies Collatz chains. It has some problems, which I've tried to indicate. Grateful to anyone who can spare the time to look at it (and apologies in advance for being a bit waffly, not using LateX etc and thus setting off CRG’s bullshit detector). It would help me to work out whether it's worth continuing to try and sort out the problems in the method. 
August 26th, 2014, 06:23 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
Of course when you have a heuristic/statistical approach and you're asking for it to be tightened up, a blog post is perfect. I wouldn't 'ding' you for failing to use TeX unless you were actually claiming a proof (in which case I'd expect you to have done the tightening already ). I don't understand what you're getting at or why this should show that (even) most numbers go to 1, but I did code your function (PARI/GP) which I'll leave here in case it's useful to someone else: Code: f(p)={ my(n=log(p)\log(2)+1,q=2^np,t); t=sum(i=0,#binary(q),if(bittest(q,i),q=2^i;3^hammingweight(q)*2^i,0)); (2^nt)/3^hammingweight(2^np) }; 
August 26th, 2014, 06:42 AM  #3  
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26 
Thanks. Quote:
The last step (which is the weakest as it stands) is to suggest that if we can use it to show that there are always sufficient integer solutions to hit every odd integer in any region, then this would at least be strong statistical evidence of the truth of the conjecture. And that because we can't have more than one solution for the same integer, we can maybe apply a kind of pigeonhole principle to say that if there are sufficient integer solutions to 'fill' each integer, then the conjecture is true. Last edited by Hedge; August 26th, 2014 at 06:45 AM.  
August 26th, 2014, 07:43 AM  #4 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  But even without that restriction, there are only 465 (by my count) odds up to a million which product positive integers. That's very very very far from enough to get a pigeonhole proof. Worse, the fraction of numbers which produce positive integers seems to decrease as the range becomes larger: just 1153 up to 10 million, about 1/4 the density.

August 26th, 2014, 08:04 AM  #5 
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26 
You'd expect the fraction of solutions to decrease, because you are getting more higher level Collatz chains. Level 1 chains work for 1 in 2 powers of 2. Level 2 chains work for 1 in 6. Level 3 for 1 in 18 and so on. (r is a level n number if its Collatz chain reaches 1 in n tripling steps and also if the binary expression of q has n '1's in it.) This means this approach is incredibly computationally unwieldy, since you quickly get to extremely large powers of 2. But what I was looking at is the pattern of how many integer solutions are produced in a particular region by numbers of particular levels, and whether we could show that you will only ever need test a finite number of levels to find sufficient integer solutions to fill a particular region. So maybe think of the pigeonhole aspect of it working in terms of how many levels of number you need to test before a region must be full (and if we can double this each time we double the region we are considering). (I think that might be slightly clearer than some of the waffle about estimates later in the blog post). Last edited by Hedge; August 26th, 2014 at 08:17 AM. 
August 26th, 2014, 08:32 AM  #6 
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26 
Just to give one example of how the estimation process works: For level 2 numbers, we can laboriously test odd numbers up to a million (or 2^20 for simplicity) which will give us results for r up to about 109,000. Alternatively we can use Pascal's triangle to work out that up to 2^20 there are 1+2+3....+15+16 = 136 odd numbers that produce level 2 results. We'd expect 1 in 6 of these (approximately) to be integers, so estimate 136/6 = 22.666. In fact there are 24, starting 3, 13, 53, 113, 213, 227 etc. So while the estimate is slightly inaccurate, it is pretty good, and the higher we go the more accurate it should get. One point where I am a bit stuck is whether we can put a bottom limit on how big the inaccuracy can be, since we will sometimes have an underestimate. Last edited by Hedge; August 26th, 2014 at 08:42 AM. 
August 26th, 2014, 09:05 AM  #7  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Quote:
But in that case you still don't have nearly enough power to prove what you need. The sum of the levels of all the acceptable odds (i.e., f(n) is a positive integer) up to a million is only 21882 which is much less than 500,000. Up to 10 million it gets worse at only 63488. So even if there were no duplicates through any of these (surely false) and you could predict levels precisely (unlikely) you'd still be far out.  
August 26th, 2014, 10:48 AM  #8  
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  Quote:
Quote:
In other words; (((17*3+1)*3+4)*3+32) = 512 can be expressed as (17*27) + 9 + (3*4) + 32 And ((((17*3+1)*3+4)*3+32)*3+512) can be expressed as (17*81) + 27 + (9*4) + (3*32) + 512 = 2048 But the latter (and subsequent duplications) is excluded by the function because 512 = 2048/4. So the only chain identified will the first one above. Quote:
I do see problems, of course, but I'm not sure you're attacking the right part of it, yet. The question isn't 'can we prove every integer is output by the function if we continue it forever'? (For which the method would obviously be hopeless because of the problems with density you note). The question might be 'given that we know that all the integers are output up to 8, then up to 16, then up to 32 and so on, can we go on to show that the number of integer solutions will double each time we double the region we are looking at?' Or, you could look at density a different way  any level 1 integer solution for f(n) = r gives a solution r < n/3. For a level 2 solution it is r < n/9, for a level 3 solution it is r < n/27, for a level 4 solution it is r < n/81. We can fully count the number of values of n that give us level 1, 2, 3 etc solutions (whether integer or not). So the density we need to look at isn't 'numbers less than 10^6' but (roughly speaking) 'level 1 numbers less than 10^6/3 plus level 2 numbers less than 10^6/9 + level 3 numbers less than 10^6/27 + level 4 numbers less than 10^6/81...' Then what I'm trying to do is modify this so for integer solutions beneath 16 we look at 'level 1 numbers less than (3*16)/3 plus level 2 numbers less than (9*16)/9 + level 3 numbers less than (27*16)/27 + level 4 numbers less than (81*16)/81...' Which would (in theory) give us a decent estimate of density below 16 (whereas the 10^6 example above applies to different regions for different level numbers).  
August 26th, 2014, 11:27 AM  #9 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  I have no idea how this gets us closer to answering that. 
August 26th, 2014, 11:38 AM  #10 
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  

Tags 
approach, collatz, pigeonhole 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pigeonhole question  hiddenphi1  Applied Math  1  July 14th, 2014 11:56 AM 
Pigeonhole principle... please help!  merlin2222  Algebra  2  June 27th, 2011 02:27 PM 
Pigeonhole Principle.  deadlyned  Number Theory  1  March 12th, 2011 01:34 PM 
pigeonhole problem  mathdigger  Applied Math  0  October 9th, 2010 12:55 AM 
Pigeonhole Problem  wulfgarpro  Algebra  17  March 22nd, 2010 04:13 PM 