Yes, most of it was either wrong or too weak (:
I tried going the other way, seeing if it’s possible to prove that no-integer-circuits is actually Baker-hard.
Showing that no integer circuits exist boils down to showing that (2^l - 3^s) = a (3^s - 2^s) has no positive integer solutions in (l,s<l,a), and so far, Baker is needed to show that.
But it seems like only certain putative statements of the form 2^l - 3^s = n (for specific n < s) can be mechanically converted into putative integer circuits. So, either it’s not Baker-hard, or some other method would be needed.
1 Like
The reformulation I got to is no solutions for: (2^n - 3^k)(a+1) = 2^l - 1, with n = k+l, 2^n > 3^k, k \geq l and a+1 < 2^l - 1.
I proved the impossibility (modulo trivial cycle) for a = 0 in Lean, i.e. elementary proof of no small cricuit.
Gotcha. If 3^x-2^x = a(2^k-3^x) has an integer solution, then for some k,x,a, both sides of this equation are integers:
a = \cfrac{3^x-2^x}{2^k-3^x}
which means both sides of these equations are integers:
a+1 = \cfrac{3^x-2^x}{2^k-3^x} + 1
a+1 = \cfrac{3^x-2^x}{2^k-3^x} + \cfrac{2^k-3^x}{2^k-3^x}
a+1 = \cfrac{2^k-2^x}{2^k-3^x}
a+1 = \cfrac{2^x(2^{k-x}-1)}{2^k-3^x}
If the RHS is an integer, then \frac{\text{RHS}}{2^x} is also an integer, so \frac{a+1}{2^x} is also an integer. At a=0, that won’t happen unless x=0, and at a=1, that won’t happen unless x=1 (trivial cycle).
I see, so more generally, the bottom member of an integer circuit (if one existed) would need to be one less than a power of 2. Those are the “rocket numbers” with initial trajectories of up-up-up.
1 Like
I believe that the bottom element would be of the form 2^k a + 2^k - 1 hence “one less than a power of 2” only when you look at the last k bits (with k number of odd terms).
1 Like
Got it, \frac{a+1}{2^x} is an integer if a+1's factors include x twos; it can have other factors.
1 Like
For any integer (n)congruant 3 mod4 if you apply (n+1)÷2 you will get an even number (s) that represents the sequential position of the odd number on an odd numberline.as all/only 3 mod4 increase sequentially by ×1.5 any number that produces s=multiple of 3 will divide by 1.5 and produce an integer, and so is not the base of an increasing structure.any 3 mod4 that converts via the bijection (n+1)÷2=even non multiple of 3 will be the base/lowest odd n in an increasing structure.its not just powers of 2, eg. 10×2^7=1280 consider this the s number and convert to n 1280×2-1=2559
2559×3+1=7678
3839×3+1=11518
5759×3+1=17278
8639×3+1=25918
12959×3+1=38878
19439×3+1=58318
29159×3+1=87478
43739×3+1=131218
(65609×3+1)÷2=98414 and divides by 2 again
If you convert these odd numbers to s you’ll see they start from 10×2^7 keep multiplying by 1.5 until they get to s=odd which represents n=1 mod4. Note that ((2559×3+1)÷2)-2559=1280
Note that the last even integer in these sequences will not be a divisible by 4
16,24,36,54 where 54÷2=27
31+16+24+36+54=161
I’ve been looking for powers of 2 to appear as a constant somewhere, with the idea that everything else cancels out around them. Theyre right under my nose
Take 2559+1÷2=10×(2^7)
2^7=128
(((((((2559×3+1)×3+2)×3+4)×3+8)×3+16)×3+32)×3+64)×3+128)÷(2^7)-1÷3= the highest odd number 2559 hits before the next odd reduces below itself.
ive been looking for where the powers of 2 sit in this system as a constant, this is it. I believe this is relevant to the 2 adic work and binary representations, which is all a little over my head.hope this helps.
Okay at this point im just noticing patterns so please feel free to ask that I delete any posts that aren’t relevant.
Take 31
31×3=(93)
93+1=94
94×3=(282) 282÷2=141
282+2=284.
284×3=(852) 852÷4=213
852+4=856
856×3=(2568) 2568÷8=321
2568+8…….
(141-93)÷16=3
(213-141)÷8=9
(321-213)÷4=27
2,4,8,16,32,64…..
10,20,40,80,160,320….
14,28,56,112,224,448
22,44,88,176,352
Distribution of bases in s
Level 1:2,10,14,22,26…..+8,+4,+8,+4
Level 2:4,20,28,44,52…..+16,+8,+16,+8
leval 3: 8,40,56,88,104…..+32,+16,+32,+16
just dropping this in here as i previously thought predicting a global peak for any n was not possible due to the distribution of the bases of increasing columns. Now I think it may be possible to show a peak for any n<x
Let us consider a much easier problem: Are there sequences starting at a positive integer x and ending at x + 1 with a parity vector of the form 1^s 0^{l-s} (l \geq s \geq 1)? They can be viewed as quasi-periodic circuits or quasi-circuits (the expression “near-circuits” was already used in this thread with a different meaning). The only ones are given below:
- 1 \rightarrow 2,
- 3 \rightarrow 5 \rightarrow 8 \rightarrow 4 .
The proof goes as follows:
Writing that T^l(x) = x + 1 leads to the rational solution
x = \cfrac{2^s}{3^s-2^l}-1.
Since the above denominator is odd, assuming x to be a positive integer implies 3^s-2^l = 1 which only occurs in two cases:
- l=s=1,
- l=3, s=2.
There are various elementary proofs for this fact, one of which goes back to the 14th century! Here is a short proof. Amazingly, this argument was already used to show the nonexistence of high cycles in @mathkook 's paper.
Note that the equation 3^s-2^l = -1 has only one solution with s\geq 1, so there is just one such quasi-circuit of negative integers: -3 \rightarrow -4 \rightarrow -2.
The case of quasi-circuits ending at x-1 instead of x+1 seems as difficult as the case of circuits. So I leave it to the reader! Sometimes, a minor change in the statement of a problem is sufficient to drastically change its difficulty.
2 Likes
Great! That’s awesome. It’s so crazy that it’s easier to show x can’t return to x+1 than to show x can’t return to x.
Here’s another application …
Following the parity vector (110)^a 0^b, no start number x can return to x+5.
Proof.
Under this parity vector, x winds up at \cfrac{3^{2a} x + 5 (3^{2a} - 2^{3a})}{2^{3a+b}}.
Setting that to x+5, we wind up with
x = \cfrac{5(2^{3a+b}-3^{2a}+2^{3a})}{(3^{2a} - 2^{3a+b})} = \cfrac{5 \cdot 2^{3a}}{3^{2a}-2^{3a+b}} - 5
For x to be an integer, we’d need 3^{2a}-2^{3a+b} = \pm 5 (or \pm 1, which @oros covered).
Powers of 2 and 3 only come this close in small exceptional cases, as proven by Herschfeld (1936), including 9 - 4 = 5, 3-8 = -5, and 27-32 = -5. Actually, no a and b pair fits these cases, so the above condition is never satisfied.
(For both cases, 1^a 0^b and (110)^a 0^b, we can also rule out x cycling back to x itself, by adding either 1 or 5 to x (preserving its putative integrality) , cancelling the 2s (also preserving integrality), then using Baker’s heavy artillery to show the result is less than 1.)
Also worth noting that @oros paradoxical paper calls out actual x \rightarrow x+1 sequences as possibly exhibiting self-avoiding behavior (where self = x). Of course, those follow parity vectors other than 1^* 0^*, such as 7, 11, 17, 26, 13, 20, 10, 5, 8.
1 Like
Yet another amazing observation:
Consider a sequence starting at n and ending at n+d with parity vector 1^a 0^b . Assume further that this sequence is paradoxical in the sense that there hold the two conditions
- 3^a < 2^{a+b} (the sequences is expected to decrease on a+b iterations),
- d \geq 0 (the sequence increases or is cyclic).
Then there is an elementary proof for the absence of solution on positive integers whatever the value of d, except for d=0 which is precisely the desired case of a circuit. No luck…
1 Like
I might be a bit late to the party but I believe that I have an elementary (in the sense that it doesn’t use Ellison’ nor Baker’s arguments) proof that no circuits other than the one of the trivial cycle 1-4-2 can exists where a circuit is defined such that the parity vector of the minimal element of the circuit m is 1^x0^{k-x} and for which k is the smallest number such that col^k(m)=m with col(n)=(3n+1)/2 if n odd and n/2 if n even . For this let us first observe that m=2^x-1 and that the maximum element of the circuit is M=3^x-1 since M=col^x(m)=3^x-1, this is a very well known fact and easy to proove by induction or with other ways. In order for us to have a cycle with this parity vector we thus need (3^x-1)/2^{k-x}=2^x-1. Hence v_2(3^x-1)=k-x since 2^x-1 is odd. But it can be shown without much trouble that for all strictly positive integers n, v_2(3^n-1)=1 if n is odd and if v_2(3^n-1)=v_2(n)+2 if n is even. , Using this, since I believe it has already be shown that for this specific circuit case, k=ceil((ln(3)/ln(2)x) we find k-x= ceil((ln(3)-ln(2))/ln(2))(x) . Uing the previous 2-adic valuated equation : since in the case where x=1 we find the trivial cycle and that accordingly to what is before k-x>1 for all x>1 . We necessarily have x even, hence we must have v_2(x)+2=k-x=ceil((ln(3)-ln(2))/ln(2))(x) hence v_2(x)= ceil((ln(3)-ln(2)/ln(2))(x) -2. Now with the observation that for all strictly positive integer n v_2(n)<log_2(n) . With some standard real analysis, we find that the inequation log_2(n)<(((ln(3)-ln(2))/ln(2)n)-2 is true for all n>8 Hence, from what precedes for all x>8 : v_2(x)<(((ln(3)-ln(2))/ln(2)x)-2 And consequently, v_2(x)<ceil((((ln(3)-ln(2))/ln(2)x))-2 . Hence the 2-adic equation is wrong and there can’t be a circuit. for all x>8 . Taking into account the cases of 9>x>0 where we find that the trivial cycle is the only circuit. And we didn’t use any bound on the gap between the powers of 3 and 2. There may be some mistakes in this proof but I don’t think that they can’t be fixed, this proof utilizises mainly the fact that we know that m=2^x-1 but for almost all cycles we have no idea what the minimum’s exact value is. Hence I don’t know if this proof can really help to find some progress in the general cases of cycles.
I don’t think 2^x-1 is necessarily the minimum circuit member. I think it can be k2^x-1 for any odd k.
1 Like
Hum that’s actually a very good point without bounds on the gaps between powers of 2 and 3 there is no reason that m has to be this small. Though if you just go off the hypothesis that the gap between the powers of 2 and 3 have to be atleast 1 you find that for m=(2^x)l-1 since we also have m=(3^x-2^x)/(2^k-3^x) we have m<3^x-2^x which is approximatively 3^x which means that you only have to solve for a finite amount of l where this number should be close to 3^x/2^x The previous equation to solve that now becomes v_2(l(3^x)-1)=k-x . It might be possible again to find a structure in the values of v_2(l(3^x)-1) to have it expressed in terms of x and l this time.
I left a comment on the youtube post, but it seems to have “vanished.”
p=13925519237251
y=386464666251
>>> pow(2,386464666251,13925519237251)
2
>>> pow(3,386464666251,13925519237251)
2
>>> 13925519237251 % 8
3
nothing else before 247555500000001 that i’ve spotted.
Great, add p=13,925,519,237,251 to the list of Kershaw primes at the top of this thread! While the overwhelming majority of rational Collatz circuits (length=l, odds=s) have a lowest member (3^s-2^s)/(2^l-3^s) with coprime numerator and denominator (which implies a non-integral lowest member), very occasionally they are not coprime. Here, the case is l=3,298,323 and s=2,024,573, where factor p is shared by numerator and denominator.
1 Like
And since we like numbers. no more kershaw primes found below 1e15.
However, here are some other numbers
p=93715008807883087
y=58204763305180948
obstruction: ≡ 7 (mod 12)
p=32605142983704221670173899
y=10299951026232923582000541
obstruction: ≡ 3 (mod 8)
1 Like
Back to the topic of this thread …
Even if we don’t have an elementary no-circuit proof (yet?), it’s fun to see how far we can get with elementary means.
Here we give an elementary proof sketch that an integer circuit must have at least 10^{130} odd members.
It’s in the vein of Eliahou (1993), but doesn’t rely on empirical verification of any set of start numbers (such as less than 2^{68}).
Usual disclaimer #1: This proof is probably already known! And yes, it’s a trivial corollary of the fact that no such circuits exist at all, but we only know that through non-elementary means (Baker).
Consider a positive integer circuit of length l with total odd members s.
The smallest member of the circuit is \frac{3^s-2^s}{2^l - 3^s}.
If that’s a positive integer, then so is \frac{3^s-2^s}{2^l-3^s} + \frac{2^l-3^s}{2^l-3^s} = \frac{2^s(2^{l-s} - 1)}{2^l-3^s}. And if that’s a positive integer, so is \frac{2^{l-s}-1}{2^l-3^s}, in which case, 2^{l-s} -1 \geq 2^l-3^s, so 2^{l-s} > 2^l - 3^s, or 3^s > 2^l(1 - 2^{-s}).
For a positive circuit, the smallest member’s denominator must be positive, so 3^s < 2^l. Combining:
2^l(1 - 2^{-s}) < 3^s < 2^l.
skipping lots of algebra including the application of the identity \ln(1-t) \geq -2t …
For a positive integer circuit with length l and s odd members, we have
\mbox{shortfall}(s \log_2 3) < 3 \cdot 2^{-s}.
where \mbox{shortfall}(x) = \lceil x \rceil - x.
now skipping lots of algebra about continued fractions, where for \log_2 3, we can calculate q_0\ q_1\ q_2 ... = 1, 1, 2, 5, 12, 41, 53, 306, 665, 15601, ...
For all s < q_{n+1}, we have
\mbox{shortfall}(s \log_2 3) \geq \frac{1}{q_n + q_{n+1}}.
Combining, for fixed n :
For all s < q_{n+1}, we have \frac{1}{q_n + q_{n+1}} \leq \mbox{shortfall}(s \log_2 3) < 3 \cdot 2^{-s}, so \frac{1}{q_n + q_{n+1}} < 3 \cdot 2^{-s}, so
s < \lceil \log_2 (3(q_n + q_{n+1})) \rceil.
We have a contradiction when s \geq \lceil \log_2 (3(q_n + q_{n+1})) \rceil, for some s < q_{n+1}.
For example, suppose n=5, q_n = 41, q_{n+1} = 53. A contradiction happens for any s < 53 such that s \geq \lceil \log_2(3(41+53)) \rceil = 9. That rules out any circuit with 9 \leq s < 53.
Or take n=10, q_n = 31,867, q_{n+1} = 79,335. Then we rule out circuits with 19 \leq s < 79,335.
Because 19 < 53, we can chain these two results to rule out circuits with 9 \leq s < 79,335. Then we can “extend the chain” with larger n:
| n | \lceil \log_2(3(q_n+q_{n+1})) \rceil | q_{n+1} |
|---|---|---|
| 5 | 9 | 53 |
| 10 | 19 | 79,335 |
| 20 | 36 | 6,586,818,670 |
| 38 | 68 | 27,444,133,206,411,171,953 |
| 81 | 133 | \approx 10^{39} |
| 125 | 203 | \approx 10^{60} |
| 169 | 272 | \approx 10^{80} |
| 207 | 340 | \approx 10^{101} |
| 258 | 437 | \approx 10^{130} |
Since all links of the chain overlap, we conclude that no positive integer circuit exists with 9 \leq s < 10^{130}.
Of course, we have to hand-check 1 \leq x \leq 8, where we’ll find the trivial circuit 1 \rightarrow 2 \rightarrow 1 at s=1, l=2.
A couple days’ worth of CPU should allow us to conclude that s must exceed 10^{10,000} for a positive integer circuit, but I didn’t do it.
The weakness of this method is that it only produces one link at a time, not the entire chain. So far, only Baker’s non-elementary methods confirm that all the links are really going to overlap.
(Usual disclaimer #2: I wrote this out by hand but leaned on AI for sections of the reasoning.)