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.