My Math Forum Collatz, a pigeonhole approach

 Number Theory Number Theory Math Forum

 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 "k-level" 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 ~sqrt-sized, 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:
 Originally Posted by CRGreathouse But it looks like the error in your approximation is about ~sqrt-sized, 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.
Don't worry, I never take it as being mean when you have the patience to help, and having to explain it more clearly only helps me learn and work stuff out.

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:
 Originally Posted by CRGreathouse I supposed it worked like a Poisson/binomial process (independent numbers).
Well, this is getting to one big area where I do see problems, since the thing I instinctively don't trust about this route is the statistical element.

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.
Attached Images
 Level 2.jpg (94.3 KB, 6 views)

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:
 Originally Posted by Hedge 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.
I assume that you can't prove this. Perhaps you can convince me by computing terms high enough to show that the error drops off faster than would be expected by such a model.

August 29th, 2014, 06:10 AM   #27
Senior Member

Joined: Mar 2012

Posts: 572
Thanks: 26

Quote:
 Originally Posted by CRGreathouse I assume that you can't prove this. Perhaps you can convince me by computing terms high enough to show that the error drops off faster than would be expected by such a model.
I hate to ask, but could you do me a favour, because it would indeed be a useful/interesting test and you already have the basic code (which I can't use)? Could you calculate how many integers the function outputs (with the restriction q< 2^n/4 in place)* up to 10 or 100 million or so? Or is that a pain?

*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:
 Originally Posted by CRGreathouse 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.)
That's a tad unfair (although I know I've no right to expect even the patience you do give me). The only things I've disputed are basics like whether f(3) should have been excluded and an assumption you made, that the function must generate duplicates (and in those cases it was my failure to express myself clearly enough in the first place that led to it).

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 Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top