August 28th, 2014, 09:15 AM  #21 
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 
Right now, as far as I can tell, you have a heuristic but nothing more for the number of "klevel" solutions up to a given bound. (The bound itself doesn't seem to tell us anything helpful about the size of the solutions themselves, which seems to be a major limitation, but I digress.) The trouble is that the error in your heuristic could easily be enough to hide counterexamples. If the Collatz conjecture were to be false then the most likely way for it to fail would be to have a (large) loop of (large) numbers which don't go to 1, and a priori it's thus possible that there are only finitely many odd numbers which don't go to 1. But it looks like the error in your approximation is about ~sqrtsized, which is way bigger than O(1). So again, what does this get us? I'm not trying to be mean, just trying to see if the approach is viable. 
August 28th, 2014, 10:19 AM  #22  
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  Quote:
I have a couple of thoughts but just so I know, how are you working out the size of the error? That would be useful to know.  
August 28th, 2014, 12:01 PM  #23 
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 supposed it worked like a Poisson/binomial process (independent numbers).

August 28th, 2014, 02:26 PM  #24  
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  Quote:
However, I would argue that it is stronger than a Poisson/binomial process since there is so much dependence and modular structure within the levels, meaning that the estimate is at least based on highly predictable frequencies, rather than independent probabilities. As an example, take q = 3. We may not know which value of 2^n will yield the first integer, but we do know it will be 1 (and only 1) of the first 6. Thereafter it will yield an integer every 6 values of 2^n exactly. And the frequency of integer values output by this (or any particular level 2) value of q will tend towards a limit of 1/6. (and each level 3 value of q will tend to 1/18, each level 4 to 1/54 and so on). In addition, the position of different values of q is interconnected. After the first instance of an integer for q = 3 at 2^n, we know that 2^(n+2) must yield an integer for q = 9, 2^(n+4) must yield an integer for q = 33, and that q = 5, 17 and 65 will (within the first 6 values of q=5) start to yield integers on the alternating powers of 2 so that these 6 values of q settle into a regular pattern where one always falls on each value of 2^n. Then all higher values of q will also be connected to these values, with q = 129 always yielding an integer on the same power of 2^n as q = 3, q = 257 yielding one on the same value as q = 5 and so on. Then there are necessary connections between the position of level n and level n+1 numbers which I won't go on about unless you really want, however again, the main variable is where the first instance falls, but there is only a limited range this can happen in and thereafter we get entirely predictable frequencies and interconnected positioning. So there's loads of structure and this only increases at higher levels as we get different power series within the q numbers. However, I'm still not sure if we can quantify exactly how high the error can get, even given all this structure. Last edited by Hedge; August 28th, 2014 at 02:29 PM.  
August 29th, 2014, 02:37 AM  #25 
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26 
This is a visual version of the stuff about level 2 distribution in the last post. It's very regular (and unlike a Poisson distribution in that respect): every integer solution is 6 away from the next in a straight line up or down (The vertical axis is different values of q, horizontal 2^n). Once you get to level 3 numbers the distribution is like this, but in 3D, with each integer 18 away from the next in a straight line in any direction.

August 29th, 2014, 05:09 AM  #26  
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:
 
August 29th, 2014, 06:10 AM  #27  
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  Quote:
*I know you already did this, but I think it was without the restriction. And I know there's more to the problem than this, but I'd like to use this as an initial yardstick.  
August 29th, 2014, 08:08 AM  #28 
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 
It's problematic to ask me to do the calculations because I don't properly understand you. If you can quote code I've written and say, "yes, this is exactly correct" then I'd be willing to donate some spare cycles to it, but I don't want to spend any until I know that you won't just say, "you computed the wrong thing". (I think that's essentially what you've said about every calculation I've made so far on this thread.) Of course you could just get a copy of PARI/GP at the link in my .sig  it's free. 
August 29th, 2014, 10:35 AM  #29  
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  Quote:
On the poisson distribution, I think the error term is probably better than you assumed, because the separate values aren't independent or random  but I see it's still a problem and beyond that it's a discussion on whether or not there is a path forwards with this, on which the odds are that you are right. Anyhow, I'll have a look at the code, and you're right I should probably try to get the hang of PARI/GP.  
August 29th, 2014, 08:28 PM  #30 
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 
(There's a side problem where my Internet connection has been lost, and I'm forced to post from places other than home. This means I don't have access to PARI/GP or my other specialized software. Hopefully the situation will be repaired next week.)


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 