I don’t expect anyone to understand that title as it stands, but here is an explanation of where I am.
So, as I explained some time ago, I am working with tricots, that are collatz-ish operators. Here the one I am interested in sends 2k on k and 2k+1 on k+1. It takes values among rationals with an odd denominator.
For example, the orbit generated from 7/5 would go like this:
What I call the trajectory here is simply a way to code if each step corresponds to odd or even, here I’d say the trajectory of 7/5 under this tricot is: 10100110011001… or 10[1001] (odd, even, then an infinite repetiton of odd-even-even-odd). Here the length of that trajectory’s period is 4, as “1001” is of length 4.
The specific tricot I defined previously only produces ultimately periodic orbits, and thus the length of the period of a number’s trajectory is always well-defined.
What I noticed is that a,b and q such that (a,q) are coprime and (b,q) are coprime, then a/q and b/q are going to have periods of same lengths. I have checked for about a hundred values of q and it seems to always work, although I don’t have the beginning of an idea for how to prove it.
Interesting question, here are a few hints that could help…
When you consider a cycle of length l starting from a rational x=\frac{a}{q}, you get an equation of the form 2^l a = a + q \, \beta(v)
where \beta(v) is an integer depending only on the parity vector v that describes your tricot in terms of 0s and 1s. So the length l is such that 2^l - 1 is divisible by q. You cannot have a cycle of any arbitrary length. In practice, we may expect that the length l of a cycle is most likely the smallest such l. This is the case in your example where q=5 and l=4.
Another constraint is that your tricots always decrease as long as the numerator is above q, and the latter cannot grow above q when it is smaller than q. So the number of cycles for a given denominator q is limited and the sum of their lengths is upper bounded by q-1 (when q is prime, otherwise the bound is even smaller).
I already have that result. Basically any a/q (where a and q are coprime) goes eventually to a’/q such that 0<a’<q, and from that point the trajectory becomes periodic.
All periods eventually happen. That’s just a matter of solving a rather simple equation. The bigger q gets, the longer, on average, periods will be, but that’s only an average tendency.
For a given q (>=3), the longest possible period is of length q-1. In that case, q is prime (but the reciprocal isn’t true).
Yes, and that’s not difficult to prove for a given denominator that there are only a few possible cycles. Actually I can quite easily prove that the sum of all the lengths of cycles for a given q is equal to q-1 so that’s easy to categorize them.
So I just put your question into ChatGPT and it came out with this reason, after paraphrasing:
T(a/q)={a/2q if numerator is even, and (a+q)/2q if numerator is odd}.
Start with a/q in lowest terms. Whether a is odd or even determines which branch applies. In either branch, the denominator doubles and then is renormalized back to q, so what really matters is how a evolves mod q.
In both the even and odd cases, a becomes (2^(-1) *a) mod q. Or just (a/2)modq.
If gcd(a,q)=1, then a is in the unit group (Z/qZ)×. The sequence of numerators is then a,2^(−1)a,(2^(−1))^2*a,…. This cycles with period equal to the multiplicative order of 2^(-1)(modq).
That period depends only on q, not on a (as long as gcd(a,q)=1. And because ord(2^(-1),q)=ord(2,q) (same order), this is really just the order of 2 modulo q.
I hope this helps even though I didn’t do any of the work.
Ok, I think I get what you say (although that doesn’t correspond to the meaning of “congruent” I am used to).
That said, I don’t get how it follows that the period should be the same for different numerators that are not in the same cycle. Is there a secret unquoted theorem here or something obvious I am missing?
I fully agree with @HungryMonkey7 (and ChatGPT, for once ).
When restricting to rationals a/q with 1 <= a <= q-1, the tricot is a permutation. There are 2 cases:
If 2 is a primitive root mod q, then there is a unique cycle with gcd(a,q)=1 of length phi(q) where phi(q) is the Euler totient function (number of numerators a coprime to q). This case occurs for q=3, 5, 9, 11, 13, 19, 25, … and phi(q)=q-1 whenever q is prime.
Otherwise, all cycles with gcd(a,q)=1 are of the same length which is the order of 2 in (Z/qZ)^x. This occurs for q=7, 15, 17, 21, 23,… with respective number of cycles 2, 2, 2, 2, 2, … and lengths 3, 4, 8, 6, 11, … The number of cycles can be larger than 2, e.g., for q=31, there are 6 cycles of lengths 5.
I don’t get how you come up with your second point though. Is it something you quote from the article? (and that I missed).
Just for clarity, I saw by myself that there can be many cycles, the only point I don’t know how to prove is that “all cycles with gcd(a,q)=1 are of the same length which is the order of 2 in (Z/qZ)^x”.
Consider the case q=31 and start from the cycle where all numerators are powers of 16 mod q (16 is the inverse of 2 since 2*16 = 32 = 1 mod q): 1 → 16 → 8 → 4 → 2 → 1.
Next, let us choose a numerator that is not in the previous cycle, like a=3. Multiplying each term by 3 (mod q) gives another cycle of length 5 : 3 → 17 → 24 → 12 → 6 → 3.
By repeating this process, we obtain six cycles of length 5. This is not a formal proof, but you get the idea, which is based on group theory. The whole point is that the action of the tricot modulo q is basically a division by 2.
Observe that the number of odd terms is not preserved from one cycle to another.
This method cannot be applied to Collatz due to the factor 3 whenever an odd term is encountered. But it can be applied to another variant where odd n \rightarrow \frac{3n+1}{2} and even n \rightarrow \frac{3n}{2}. This is an equivalent formulation for the “tricot” 2n \rightarrow 3n and 2n+1 \rightarrow 3n+2, already discussed in the topic Finding a specific irrational number.
Obviously, all positive integers have divergent trajectories. But, the situation is less clear on (negative) rationals with an odd denominator. Starting from -\frac13 or -\frac23 leads to the fixed points 0 and -1, respectively. The previous method implies that the length of a rational cycle with denominator q \geq 5 and coprime to 3 is given by the order of \frac32 in \mathbb{Z}_q^{\rm x}. However, the existence of such a cycle is not guaranteed. For q=5, we have the cycle -\frac25 \rightarrow -\frac35 \rightarrow -\frac25 of period 2, but there seems to be no cycle for q=7 and q=11. There is also a cycle for the denominator 13 with period 4, starting from -\frac{4}{13}.
One may ask whether there are infinitely many cycles and what periods are possible (or not)?
To keep things homogeneous I consider the general case: 2k → Nk ; 2k+1 → Nk+1, with N an odd positive integer. (the case I described in the beginning of this thread is N=1, what you are describing can be assimilated to N=3)
If you are looking for the trajectory [a_0, a_1, …, a_(n-1)], you just have to solve a relatively simple equation: (…((x - a_0)⸱(N/2)+a_0-a_1)⸱(N/2)…) = x
Also it seems like there is some kind of correspondance:
x/3 under 2k → k ; 2k+1 → k+1 corresponds to x/5 under 2k → 3k ; 2k+1 → 3k+1 and, more generally, x/(N+2) under 2k → Nk ; 2k+1 → Nk+1, in that they all only permit [10], [01], [0] and [1] non-chaotic trajectories.
The same can be said for x/5 which corresponds with x/(N²+2²)
x/7 which corresponds with x/(N^3-2^3)
x/9 which corresponds with x/(N^3+2^3)
I’m not sure such a correspondance can be consistenty found.
You mean that rationals of the form x/3 under the first transformation (N=1) have the same dynamics as rationals of the form x/5 under the second one (N=3)?
More precisely, rationals of the form x/3 under the first transformation (N=1) have the same dynamics as some rationals of the form x/5 under the second one (N=3):
N=1: 1/3 → 2/3 → 1/3… ( [10] for 1/3, [01] for 2/3)
N=3: 2/5 → 3/5 → 2/5… ( [01] for 2/5, [10] for 3/5)
Ok, I get it now. Solving the equations for any given period yields a “correspondance” taking the form of a generic cycle where each term can be expressed as a rational function of N and they all have the same denominator.
For period 2, we always have the cycle \frac{2}{N+2} \rightarrow \frac{N}{N+2} \rightarrow \frac{2}{N+2} .
For period 4 and parity vector [0011], we get a generic cycle starting from \frac{4}{N^2+4}.
For period 4 and parity vector [0001], we get a generic cycle starting from \frac{8}{(N+2)(N^2+4)}.
Yet, there seems to be no conjugacy between these functions, so their dynamics differ.
).