Prove that $f(x) = -1-3x \pmod{2^e}$ cycles with period $2^e$

Question

This question is inspired by the Collatz-like "Binary Complement Sequences," as discussed here and here and here on seq-fan.

For a given exponent $e$, let $f$ be defined as $f(x) = -1-3x \pmod{2^e}$. Now calculate $f(0)$, $f^2(0) = f(f(0))$, $f^3(0)$, $f^4(0)$...

For example, when $e=3$, the sequence is $$0, 7, 2, 1, 4, 3, 6, 5, 0$$ (because e.g. $f^2(0)=f(7)=-1-21\pmod{8}=2$).

Prove that this sequence is always a cyclic permutation of the integers from 0 to $2^e$. That is, prove that $f^n(0) = 0$ iff $n \equiv 0 \pmod{2^e}$.

(I don't know that this is always true, but it seems to be true, and so I bet it's easy to prove for someone who knows math. :) If it's true, my next question will be whether it's possible to efficiently compute discrete logarithms in this group — like, "given $e=64$, find me the $x$ such that $f^x(0) = 42$." I know this is a well-studied hard problem for functions of the form $f(x)=px\pmod{2^e}$, but I'm not sure what effect our extra "minus 1" might have.)

Answer 1

(Credit for this answer really goes to Junekey Jeon, who had the key insight, but asked me to write it up.)

The trick is to see that iterating $f(x)=-1-3x\pmod{2^e}$ gives us exactly a linear congruential generator! Using the terminology from that Wikipedia page, we have a modulus of $m=2^e$, a multiplier of $a=2^e-3$, an increment of $c=2^e-1$, and a seed of $X_0=0$.

By the Hull–Dobell Theorem, an LCG with $c\neq 0$ will have period $m$ if and only if all three of these conditions hold:

• $m$ and $c$ are relatively prime (yes: $c$ is odd),
• $a\equiv 1$ mod $p$ whenever $p$ is a prime factor of $m$ (yes: the only such $p$ is 2, and $a\equiv 1$ mod 2),
• $a\equiv 1$ mod 4 whenever 4 divides $m$ (yes: $2^e-3\equiv 1$ mod 4 whenever $2^e\equiv 0$ mod 4).

So, all three conditions hold, and so this LCG does have period $m=2^e$.

Answer 2

It is true by the definition of the modulo operation,
every sequence $ a \bmod b $ is cyclic with period $ b $, because for $ a \in [\,0, b ]\, $, $ a \bmod b = a $ .
For $ a \notin [\,0, b )\, $, $ a \bmod b \equiv a + kb \bmod b $, where $ k $ is any integer.

So, from that, $ a \equiv a + b \equiv a + 2b \equiv \cdots $

$ f(x) = -1-3x $ is a linear function, which means the sequence created by inputting integers into this function creates a linear sequence.
Therefore, applying a scaling factor $ s $, we can make it equal to $ f(x) = x + C $

In this case, $ s = - \frac{1}{3} $, which gives $ sf(x) = x + \frac{1}{3} $

From there we have a direct relation between $ f(x) $ and $ a $, becasue $ (sa \bmod b) = s(a \bmod b) $.

In other words, every linear sequence is cyclic with the period being at most whatever number you write on the right of the modulo function.