Ok, I think I have an elementary proof of no circuits using the fact that for all iterate x in a positive integer cycle with k odd terms we have x < 3^k (see this thread), for which we do not have an elementary proof (yet).
Notations:
- k: number of odd terms
- l: number of even terms
- n = k+l
We know that to get a positive integer cycle, you need both:
- Bound 1. 2^n > 3^k
- Bound 2. k > l
Both bounds have elementary proofs.
Now consider, the circuit 0^l 1^k, using the result I mentioned at the top, we know that the first/last iterate of the circuit in this rotation is exactly 3^k - 1 (and not just congruent to 3^k - 1 modulo 3^k).
Now, because of rotation 1^k 0^l you know that this is asking 3^k - 1 to end with l bits 0 in base 2. Now, look at the first k such that 3^k-1 ends with l bits 0 in base 2:
| l | First k such that 3^k - 1 ends with l bits 0 in base 2 |
|---|---|
| 1 | 1 |
| 2 | None |
| 3 | 2 |
| 4 | 4 |
| 5 | 8 |
| 6 | 16 |
| 7 | 32 |
| 8 | 64 |
^ you can reproduce the above using your favorite programming language, here’s my Python code.
This is no coincidence, excluding l \in \{1,2\}, we get k = 2^{l-2}, and I believe it can be proved without too much effort using what is known about the multiplicative group of \mathbb{Z}/2^l\mathbb{Z} because we are basically asking for the multiplicative order of 3 in multiplicative group \mathbb{Z}/2^l\mathbb{Z}, i.e. smallest k > 0 such that 3^k = 1 \text{ mod } 2^l. I’m waiting on my number theorist friend to give me the proof, but meanwhile, ChatGPT’s proof of this 2^{l-2} lemma seems correct/promising.
The nice thing is that it requires k to be way too big, i.e. way too many odd numbers in the circuit!!
Indeed, you need to satisfy Bound 1, i.e. 2^n > 3^k, which becomes at least:
2^{2^{l-2} + l} > 3^{2^{l-2}}
And, according to Wolfram Alpha, this is possible only for l \in \{1,2,3,4,5\} which for us becomes l \in \{1,3,4,5\}. (ChatGPT reasoning on this does not seem bad).
This only gives a finite number of (k,l) couples to check given our two bounds (see above).
QED