My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
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.
Hedge is offline  
 
August 26th, 2014, 06:23 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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^n-p,t);
  t=sum(i=0,#binary(q),if(bittest(q,i),q-=2^i;3^hammingweight(q)*2^i,0));
  (2^n-t)/3^hammingweight(2^n-p)
};
So f(15) = 5, f(49) = -1/81, etc.
CRGreathouse is offline  
August 26th, 2014, 06:42 AM   #3
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Thanks.

Quote:
Originally Posted by CRGreathouse View Post

I don't understand what you're getting at or why this should show that (even) most numbers go to 1...
Briefly, because the function uniquely identifies any integer with a Collatz chain to 1 (given the restriction in point 9 that we only apply it to numbers > 3/4*2^n). Thus we can use it to get a pretty good estimate of how frequently integer solutions must be found in a given region.

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.
Hedge is offline  
August 26th, 2014, 07:43 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by Hedge View Post
Briefly, because the function uniquely identifies any integer with a Collatz chain to 1 (given the restriction in point 9 that we only apply it to numbers > 3/4*2^n).
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.
CRGreathouse is offline  
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.
Hedge is offline  
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.
Hedge is offline  
August 26th, 2014, 09:05 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by Hedge View Post
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.
As I understand it you mean by "level" the number of iterations of $n\mapsto v(3n+1)$ where $v(n)$ is the largest odd dividing n before you get to 1.

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.
CRGreathouse is offline  
August 26th, 2014, 10:48 AM   #8
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Quote:
Originally Posted by CRGreathouse View Post
As I understand it you mean by "level" the number of iterations of $n\mapsto v(3n+1)$ where $v(n)$ is the largest odd dividing n before you get to 1.
Right, or the number of 3n+1 steps.

Quote:
Originally Posted by CRGreathouse View Post
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)....
I'm pretty sure there are no duplicates. The logic is that this function is simply the reverse of a way of expressing a Collatz chain, and the chain from any odd number to 1 is unique.

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:
Originally Posted by CRGreathouse View Post
and you could predict levels precisely (unlikely) you'd still be far out.
I agree this is a problem. But the 1 in 2, 1 in 6, 1 in 18, 1 in 54 method etc is actually pretty accurate, for good reason. For instance it gives us a prediction that we need up to about level 4 or 5 to hit all the integers below 8, up to about level 5 or 6 to hit all the integers below 16. And it gives us a reasonably good estimate of how many level n numbers there are up to any threshold.

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).
Hedge is offline  
August 26th, 2014, 11:27 AM   #9
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by Hedge View Post
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?'
I have no idea how this gets us closer to answering that.
CRGreathouse is offline  
August 26th, 2014, 11:38 AM   #10
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Quote:
Originally Posted by CRGreathouse View Post
I have no idea how this gets us closer to answering that.
OK, I'll have a think about whether there is a simple way I can explain that bit of the train of thought. If not, it may well mean I'm talking rubbish. .
Hedge is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.