bitword_is_aperiodic_of_prime
For prime n, every n-bit word other than 0^n and 1^n is aperiodic.
Statement
theorem bitword_is_aperiodic_of_prime (n x : ℕ) (hn : n.Prime) (hx : x < 2 ^ n) (h0 : x ≠ 0)
(h1 : x ≠ 2 ^ n - 1) : bitword_is_aperiodic n x- Source
- for brgc_necklace_order_consecutive_aperiodic_adjacent: it gives the prime case of arXiv:2610.24758 Conjecture 1
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- bitword_is_aperiodicThe n-bit word x is aperiodic (primitive): no rotation by 0 < r < n fixes it, i.e. its necklace has n distinct rotations.
- bitword_rotateCyclic rotation of an n-bit word x (a number below 2^n) by one position: the word is shifted up and its top bit moves to the bottom.
- Used by 5
- bitword_rotate_iterate_cutCyclically rotating an n-bit nonconstant word left by a positions exchanges its prefix of length a and its suffix of length b, where a+b=n.
- brgc_necklace_first_rank_exists_of_nonconstantEvery nonconstant binary word of length at least two has a first-occurrence Gray rank in its rotation class.
- brgc_necklace_first_rank_rotation_maxRotating a first-occurrence representative right once gives a representative of maximum inverse Gray rank in its rotation class; the…
- alpha_lexical_odd_completion_iff_rotation_max_of_primeThe proposed encoding bridge between positive lexical sequences and nonconstant odd-parity maximum-rank necklace representatives at odd…
- brgc_necklace_first_rank_min_rotationsEvery rotation of a first-occurrence representative has inverse Gray rank at least its first-occurrence rank.
The proof, explained
To show that any n-bit word x ∉ {0, 2^n - 1} is aperiodic when n is prime, we assume for contradiction that some non-trivial shift r ∈ (0, n) leaves x invariant. Because n is prime, r is coprime to n and therefore has a multiplicative inverse m modulo n, allowing us to write m * r = q * n + 1. Since rotating by r bits fixes x, iterating this shift m times also fixes x. On the other hand, m * r rotations correspond algebraically to multiplication by 2^(q * n + 1) ≡ 2 (mod 2^n - 1), which is equivalent to a single 1-bit rotation. This forces x to be a fixed point of a single rotation, which can only be 0 or 2^n - 1, contradicting the assumption on x.
Set K = 2^(n - 1) and express 2^n as 2 * K.
Unfolding `bitword_rotate`, the highest bit position is K = 2^(n - 1), which is positive. Since 1 ≤ n, writing n = (n - 1) + 1 via `Nat.sub_add_cancel` allows rewriting 2^n as 2 * K using `pow_succ'` and commutativity.
uses
Nat.sub_add_cancel,pow_succ',mul_commdsimp [bitword_rotate] at h set K := 2 ^ (n - 1) have hK : 0 < K := by positivity have hM : 2 ^ n = 2 * K := by have : n = n - 1 + 1 := (Nat.sub_add_cancel hn).symm nth_rw 1 [this] rw [pow_succ', mul_comm]
If x < K, then bitword_rotate n x = x forces x = 0.
When x < K, the top bit quotient x / K is 0 by `Nat.div_eq_of_lt`. In addition, 2 * x < 2 * K = 2^n, so (2 * x) % 2^n = 2 * x by `Nat.mod_eq_of_lt`. The rotation equation becomes 2 * x = x, from which linear arithmetic (`omega`) deduces x = 0.
uses
lt_or_ge,Nat.div_eq_of_lt,Nat.mod_eq_of_ltrcases lt_or_ge x K with hlt | hge · have hdiv : x / K = 0 := Nat.div_eq_of_lt hlt have h2x : 2 * x < 2 ^ n := by omega have hmod : 2 * x % 2 ^ n = 2 * x := Nat.mod_eq_of_lt h2x omega
If x ≥ K, then bitword_rotate n x = x forces x = 2^n - 1.
When x ≥ K, since x < 2^n = 2 * K, the top bit quotient x / K equals 1 by `Nat.div_eq_of_lt_le`. Similarly, 2^n ≤ 2 * x < 2 * 2^n, so (2 * x) / 2^n = 1 and the remainder (2 * x) % 2^n equals 2 * x - 2^n by `Nat.div_add_mod`. The rotation equation simplifies to (2 * x - 2^n) + 1 = x, which `omega` solves to give x = 2^n - 1.
uses
Nat.div_eq_of_lt_le,add_one_mul,one_mul,Nat.div_add_mod· have hdiv : x / K = 1 := by apply Nat.div_eq_of_lt_le · omega · rw [add_one_mul, one_mul]; omega have h2x_ge : 1 * 2 ^ n ≤ 2 * x := by omega have h2x_lt : 2 * x < (1 + 1) * 2 ^ n := by omega have hd : 2 * x / 2 ^ n = 1 := Nat.div_eq_of_lt_le h2x_ge h2x_lt have hmod : 2 * x % 2 ^ n = 2 * x - 2 ^ n := by have hdm := Nat.div_add_mod (2 * x) (2 ^ n) rw [hd] at hdm omega omega
For n ≥ 2, K = 2^(n - 1) satisfies 2 ≤ K and 2^n = 2 * K.
Unfolding `bitword_rotate`, since n ≥ 2 we have 1 ≤ n - 1, which implies 2 = 2^1 ≤ 2^(n - 1) = K by monotonicity of powers (`Nat.pow_le_pow_right`). The identity 2^n = 2 * K follows by `Nat.sub_add_cancel` as before.
uses
Nat.pow_le_pow_right,Nat.sub_add_cancel,pow_succ',mul_commdsimp [bitword_rotate] set K := 2 ^ (n - 1) have hK_ge : 2 ≤ K := by have : 1 ≤ n - 1 := by omega calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ (n - 1) := Nat.pow_le_pow_right (by norm_num) this have hM : 2 ^ n = 2 * K := by have : n = n - 1 + 1 := (Nat.sub_add_cancel (by omega : 1 ≤ n)).symm nth_rw 1 [this] rw [pow_succ', mul_comm]
If x < K, rotating x equals (2 * x) % (2^n - 1) and stays strictly between 0 and 2^n - 1.
When x < K, x / K = 0. Because x < K = 2^(n - 1), we have 2 * x < 2^n - 1, so both (2 * x) % 2^n and (2 * x) % (2^n - 1) reduce to 2 * x by `Nat.mod_eq_of_lt`. Thus rotation gives 2 * x, which matches (2 * x) % (2^n - 1), and the bounds follow from 0 < x.
uses
lt_or_ge,Nat.div_eq_of_lt,Nat.mod_eq_of_ltrcases lt_or_ge x K with hlt | hge · have hdiv : x / K = 0 := Nat.div_eq_of_lt hlt have h2x : 2 * x < 2 ^ n := by omega have hmod1 : 2 * x % 2 ^ n = 2 * x := Nat.mod_eq_of_lt h2x have h2x' : 2 * x < 2 ^ n - 1 := by omega have hmod2 : (2 * x) % (2 ^ n - 1) = 2 * x := Nat.mod_eq_of_lt h2x' omega
If x ≥ K, rotating x also equals (2 * x) % (2^n - 1) and stays strictly between 0 and 2^n - 1.
When x ≥ K, x / K = 1. Applying `Nat.div_eq_of_lt_le` and `Nat.div_add_mod`, the division of 2 * x by 2^n gives remainder 2 * x - 2^n, and the division by 2^n - 1 gives remainder 2 * x - 2^n + 1. Adding the top bit 1 to the first remainder matches the second remainder, confirming the formula.
uses
Nat.div_eq_of_lt_le,add_one_mul,one_mul,Nat.div_add_mod· have hdiv : x / K = 1 := by apply Nat.div_eq_of_lt_le · omega · rw [add_one_mul, one_mul]; omega have hd1 : 2 * x / 2 ^ n = 1 := by apply Nat.div_eq_of_lt_le · omega · rw [add_one_mul, one_mul]; omega have hmod1 : 2 * x % 2 ^ n = 2 * x - 2 ^ n := by have := Nat.div_add_mod (2 * x) (2 ^ n) rw [hd1] at this omega have hd2 : (2 * x) / (2 ^ n - 1) = 1 := by apply Nat.div_eq_of_lt_le · omega · rw [add_one_mul, one_mul]; omega have hmod2 : (2 * x) % (2 ^ n - 1) = 2 * x - 2 ^ n + 1 := by have := Nat.div_add_mod (2 * x) (2 ^ n - 1) rw [hd2] at this omega omega
The 0th iterate of rotation is the identity, matching (2^0 * x) % (2^n - 1).
For m = 0, the 0th iterate is the identity function (`Function.iterate_zero`), 2^0 = 1, and x % (2^n - 1) = x by `Nat.mod_eq_of_lt` since x < 2^n - 1.
uses
Function.iterate_zero,id_eq,pow_zero,one_mul,Nat.mod_eq_of_ltinduction m with | zero => simp only [Function.iterate_zero, id_eq, pow_zero, one_mul] rw [Nat.mod_eq_of_lt hx1] exact ⟨rfl, hx0, hx1⟩
The (m + 1)-st iterate of rotation equals (2^(m + 1) * x) % (2^n - 1).
By the induction hypothesis, the m-th iterate y equals (2^m * x) % (2^n - 1) and lies in the desired range. Applying Lemma 2 (`bitword_is_aperiodic_of_prime_rotate_eq_mod`) to y gives rotation as (2 * y) % (2^n - 1). Rewriting with `Nat.mul_mod_mod`, associativity, and exponent arithmetic yields (2^(m + 1) * x) % (2^n - 1).
uses
Function.iterate_succ',Function.comp_apply,bitword_is_aperiodic_of_prime_rotate_eq_mod,Nat.mul_mod_mod,mul_assoc,pow_succ,mul_comm| succ m ih => rw [Function.iterate_succ', Function.comp_apply] obtain ⟨ih_eq, ih_pos, ih_lt⟩ := ih have hstep := bitword_is_aperiodic_of_prime_rotate_eq_mod n ((bitword_rotate n)^[m] x) hn ih_pos ih_lt refine ⟨?_, hstep.2.1, hstep.2.2⟩ rw [hstep.1, ih_eq] rw [Nat.mul_mod_mod, ← mul_assoc, pow_succ, mul_comm 2 (2 ^ m)]For n ≥ 2, (2^n)^q ≡ 1 (mod 2^n - 1).
Because n ≥ 2, 2^n ≥ 4, so 2^n - 1 > 1. Writing 2^n = (2^n - 1) + 1, `Nat.add_mod_left` gives 2^n % (2^n - 1) = 1. Distributing powers across modulo (`Nat.pow_mod`), ((2^n)^q) % (2^n - 1) = 1^q % (2^n - 1) = 1.
uses
Nat.pow_le_pow_right,Nat.add_mod_left,Nat.mod_eq_of_lt,Nat.pow_mod,one_powhave hM : 1 < 2 ^ n - 1 := by have : 4 ≤ 2 ^ n := by calc 4 = 2 ^ 2 := by norm_num _ ≤ 2 ^ n := Nat.pow_le_pow_right (by norm_num) hn omega have h_mod : (2 ^ n) % (2 ^ n - 1) = 1 := by have : 2 ^ n = (2 ^ n - 1) + 1 := by omega nth_rw 1 [this] rw [Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] have h_pow_mod : ((2 ^ n) ^ q) % (2 ^ n - 1) = 1 := by rw [Nat.pow_mod, h_mod, one_pow, Nat.mod_eq_of_lt hM]
(2^(q * n + 1) * x) % (2^n - 1) = (2 * x) % (2^n - 1).
Factoring 2^(q * n + 1) as ((2^n)^q) * 2 via `pow_add`, `pow_one`, and `pow_mul`, modular multiplication (`Nat.mul_mod`) substitutes ((2^n)^q) % (2^n - 1) = 1, leaving (2 * x) % (2^n - 1).
uses
pow_add,pow_one,mul_comm,pow_mul,mul_assoc,Nat.mul_mod,one_mul,Nat.mod_modhave h2k : 2 ^ (q * n + 1) = ((2 ^ n) ^ q) * 2 := by rw [pow_add, pow_one, mul_comm q n, pow_mul, mul_comm] rw [h2k, mul_assoc, Nat.mul_mod, h_pow_mod, one_mul, Nat.mod_mod]
If f^r(x) = x, then f^(m * r)(x) = x for all m.
By induction on m: the base case m = 0 reduces to the identity. In the induction step, f^((m + 1) * r)(x) = f^r(f^(m * r)(x)) by `Function.iterate_add`, which equals f^r(x) = x by the induction hypothesis and the premise.
uses
add_one_mul,Function.iterate_add,Function.comp_applyinduction m with | zero => simp | succ m ih => rw [add_one_mul, Function.iterate_add, Function.comp_apply, h, ih]
Under the contradiction hypothesis that r rotations fix x, r is coprime to n and has an inverse m modulo n.
Assume for contradiction that 0 < r < n and the r-th iterate of rotation fixes x. Since n is prime and r < n, n does not divide r (`Nat.not_dvd_of_pos_of_lt`), so r and n are coprime. By `Nat.exists_mul_mod_eq_one_of_coprime`, there exists m < n such that (r * m) % n = 1.
uses
Nat.not_dvd_of_pos_of_lt,Nat.exists_mul_mod_eq_one_of_coprimeintro r hr0 hrn hfix have hn2 : 2 ≤ n := hn.two_le have hx_pos : 0 < x := by omega have hx_lt : x < 2 ^ n - 1 := by omega have hcop : r.Coprime n := by have hdvd : ¬ n ∣ r := Nat.not_dvd_of_pos_of_lt hr0 hrn exact (hn.coprime_iff_not_dvd.mpr hdvd).symm obtain ⟨m, hm_lt, hm_mod⟩ := Nat.exists_mul_mod_eq_one_of_coprime hcop hn2
Write m * r = q * n + 1, where q = (r * m) / n.
By Euclidean division (`Nat.div_add_mod`), r * m = n * (r * m / n) + (r * m) % n. Since (r * m) % n = 1, commutativity of multiplication gives m * r = q * n + 1 for q = (r * m) / n.
uses
Nat.div_add_mod,mul_commhave h_div_mod : m * r = (r * m / n) * n + 1 := by have hdiv := (Nat.div_add_mod (r * m) n).symm rw [hm_mod, mul_comm n] at hdiv rw [mul_comm m r] exact hdiv set q := r * m / n
The (m * r)-th iterate of rotation fixes x and equals a single rotation of x.
Because the r-th iterate fixes x, Lemma 5 (`bitword_is_aperiodic_of_prime_iterate_mul_apply`) shows the (m * r)-th iterate also fixes x. Since m * r = q * n + 1, Lemma 3 (`bitword_is_aperiodic_of_prime_iterate_eq_mod`) and Lemma 4 (`bitword_is_aperiodic_of_prime_pow_mul_add_one_mul_mod`) reduce this iterate to (2 * x) % (2^n - 1), which by Lemma 2 (`bitword_is_aperiodic_of_prime_rotate_eq_mod`) is exactly bitword_rotate n x. Thus bitword_rotate n x = x.
uses
bitword_is_aperiodic_of_prime_iterate_mul_apply,bitword_is_aperiodic_of_prime_iterate_eq_mod,bitword_is_aperiodic_of_prime_pow_mul_add_one_mul_mod,bitword_is_aperiodic_of_prime_rotate_eq_modhave hfix_k : (bitword_rotate n)^[m * r] x = x := bitword_is_aperiodic_of_prime_iterate_mul_apply (bitword_rotate n) x r hfix m have h_mod_k := (bitword_is_aperiodic_of_prime_iterate_eq_mod n hn2 x hx_pos hx_lt (m * r)).1 rw [h_div_mod] at h_mod_k hfix_k rw [bitword_is_aperiodic_of_prime_pow_mul_add_one_mul_mod n q x hn2] at h_mod_k have h_rot1 := (bitword_is_aperiodic_of_prime_rotate_eq_mod n x hn2 hx_pos hx_lt).1 rw [← h_rot1] at h_mod_k rw [h_mod_k] at hfix_k
Conclude that x = 0 or x = 2^n - 1, contradicting the hypotheses.
Since a single rotation fixes x, Lemma 1 (`bitword_is_aperiodic_of_prime_rotate_eq_self`) implies x = 0 or x = 2^n - 1. Each alternative contradicts the assumptions x ≠ 0 and x ≠ 2^n - 1, completing the proof.
uses
bitword_is_aperiodic_of_prime_rotate_eq_selfhave h_or := bitword_is_aperiodic_of_prime_rotate_eq_self (by omega) hx hfix_k rcases h_or with hx0 | hx1' · exact h0 hx0 · exact h1 hx1'
Nat.sub_add_cancel- For natural numbers with m ≤ n, subtracting m and then adding m yields n: (n - m) + m = n.
pow_succ'- In a monoid, a^(n + 1) = a * a^n.
mul_comm- Multiplication is commutative: a * b = b * a.
lt_or_ge- In a linearly ordered type, either a < b or b ≤ a.
Nat.div_eq_of_lt- For natural numbers, if a < b, then the integer quotient a / b is 0.
Nat.mod_eq_of_lt- For natural numbers, if a < b, then a % b = a.
Nat.div_eq_of_lt_le- If k * n ≤ m < (k + 1) * n, then the integer division m / n equals k.
add_one_mul- Right distributivity of addition with one: (a + 1) * b = a * b + b.
one_mul- 1 is the left multiplicative identity: 1 * a = a.
Nat.div_add_mod- Euclidean division identity for natural numbers: n * (m / n) + m % n = m.
Nat.pow_le_pow_right- For n > 0 and i ≤ j, powers are monotonic: n^i ≤ n^j.
Function.iterate_zero- The 0th iterate of any function is the identity: f^[0] = id.
id_eq- The identity function satisfies id(a) = a.
pow_zero- Any element raised to power 0 equals 1: a^0 = 1.
Function.iterate_succ'- The (n + 1)-st iterate of a function satisfies f^[n + 1] = f ∘ f^[n].
Function.comp_apply- Function composition applied to an argument: (f ∘ g)(x) = f(g(x)).
bitword_is_aperiodic_of_prime_rotate_eq_mod- For 2 ≤ n and 0 < x < 2^n - 1, rotating x equals (2 * x) % (2^n - 1), and the result remains strictly between 0 and 2^n - 1.
Nat.mul_mod_mod- Multiplication distributes inside a remainder: m * (n % l) % l = (m * n) % l.
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
pow_succ- In a monoid, a^(n + 1) = a^n * a.
Nat.add_mod_left- For natural numbers, (x + z) % x = z % x.
Nat.pow_mod- Powers distribute over modular reduction: a^b % n = (a % n)^b % n.
one_pow- 1 raised to any power is 1: 1^n = 1.
pow_add- Multiplication of powers with the same base: a^(m + n) = a^m * a^n.
pow_one- Any element raised to the first power is itself: a^1 = a.
pow_mul- Power of a power rule: a^(m * n) = (a^m)^n.
Nat.mul_mod- Multiplication distributes over modular reduction: (a * b) % n = ((a % n) * (b % n)) % n.
Nat.mod_mod- Taking remainder modulo n twice is idempotent: (a % n) % n = a % n.
Function.iterate_add- Function iteration adds over iteration counts: f^[m + n] = f^[m] ∘ f^[n].
Nat.not_dvd_of_pos_of_lt- If 0 < n < m, then m does not divide n.
Nat.exists_mul_mod_eq_one_of_coprime- If n is coprime to k and 1 < k, then n has a multiplicative inverse modulo k: there is m < k with (n * m) % k = 1.
bitword_is_aperiodic_of_prime_iterate_mul_apply- If x is a fixed point of f^r, then x is also a fixed point of f^(m * r) for every m.
bitword_is_aperiodic_of_prime_iterate_eq_mod- For 2 ≤ n and 0 < x < 2^n - 1, the m-th rotation iterate equals (2^m * x) % (2^n - 1) and remains strictly between 0 and 2^n - 1.
bitword_is_aperiodic_of_prime_pow_mul_add_one_mul_mod- For 2 ≤ n, (2^(q * n + 1) * x) % (2^n - 1) = (2 * x) % (2^n - 1).
bitword_is_aperiodic_of_prime_rotate_eq_self- If 1 ≤ n, x < 2^n, and rotating x by one bit yields x, then x = 0 or x = 2^n - 1.
- The formalization encodes n-bit words as natural numbers in the interval [0, 2^n), defining rotation purely arithmetically as (2 * x) % 2^n + x / 2^(n - 1).
- Several case-analysis steps use the `omega` decision procedure to resolve integer linear arithmetic bounds and divisibility conditions automatically.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma bitword_is_aperiodic_of_prime_rotate_eq_self {n x : ℕ} (hn : 1 ≤ n) (hx : x < 2 ^ n) (h : bitword_rotate n x = x) : x = 0 ∨ x = 2 ^ n - 1 := by dsimp [bitword_rotate] at h set K := 2 ^ (n - 1) have hK : 0 < K := by positivity have hM : 2 ^ n = 2 * K := by have : n = n - 1 + 1 := (Nat.sub_add_cancel hn).symm nth_rw 1 [this] rw [pow_succ', mul_comm] rcases lt_or_ge x K with hlt | hge · have hdiv : x / K = 0 := Nat.div_eq_of_lt hlt have h2x : 2 * x < 2 ^ n := by omega have hmod : 2 * x % 2 ^ n = 2 * x := Nat.mod_eq_of_lt h2x omega · have hdiv : x / K = 1 := by apply Nat.div_eq_of_lt_le · omega · rw [add_one_mul, one_mul]; omega have h2x_ge : 1 * 2 ^ n ≤ 2 * x := by omega have h2x_lt : 2 * x < (1 + 1) * 2 ^ n := by omega have hd : 2 * x / 2 ^ n = 1 := Nat.div_eq_of_lt_le h2x_ge h2x_lt have hmod : 2 * x % 2 ^ n = 2 * x - 2 ^ n := by have hdm := Nat.div_add_mod (2 * x) (2 ^ n) rw [hd] at hdm omega omegalemma bitword_is_aperiodic_of_prime_rotate_eq_mod (n x : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) : bitword_rotate n x = (2 * x) % (2 ^ n - 1) ∧ 0 < bitword_rotate n x ∧ bitword_rotate n x < 2 ^ n - 1 := by dsimp [bitword_rotate] set K := 2 ^ (n - 1) have hK_ge : 2 ≤ K := by have : 1 ≤ n - 1 := by omega calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ (n - 1) := Nat.pow_le_pow_right (by norm_num) this have hM : 2 ^ n = 2 * K := by have : n = n - 1 + 1 := (Nat.sub_add_cancel (by omega : 1 ≤ n)).symm nth_rw 1 [this] rw [pow_succ', mul_comm] rcases lt_or_ge x K with hlt | hge · have hdiv : x / K = 0 := Nat.div_eq_of_lt hlt have h2x : 2 * x < 2 ^ n := by omega have hmod1 : 2 * x % 2 ^ n = 2 * x := Nat.mod_eq_of_lt h2x have h2x' : 2 * x < 2 ^ n - 1 := by omega have hmod2 : (2 * x) % (2 ^ n - 1) = 2 * x := Nat.mod_eq_of_lt h2x' omega · have hdiv : x / K = 1 := by apply Nat.div_eq_of_lt_le · omega · rw [add_one_mul, one_mul]; omega have hd1 : 2 * x / 2 ^ n = 1 := by apply Nat.div_eq_of_lt_le · omega · rw [add_one_mul, one_mul]; omega have hmod1 : 2 * x % 2 ^ n = 2 * x - 2 ^ n := by have := Nat.div_add_mod (2 * x) (2 ^ n) rw [hd1] at this omega have hd2 : (2 * x) / (2 ^ n - 1) = 1 := by apply Nat.div_eq_of_lt_le · omega · rw [add_one_mul, one_mul]; omega have hmod2 : (2 * x) % (2 ^ n - 1) = 2 * x - 2 ^ n + 1 := by have := Nat.div_add_mod (2 * x) (2 ^ n - 1) rw [hd2] at this omega omegalemma bitword_is_aperiodic_of_prime_iterate_eq_mod (n : ℕ) (hn : 2 ≤ n) (x : ℕ) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) (m : ℕ) : (bitword_rotate n)^[m] x = (2 ^ m * x) % (2 ^ n - 1) ∧ 0 < (bitword_rotate n)^[m] x ∧ (bitword_rotate n)^[m] x < 2 ^ n - 1 := by induction m with | zero => simp only [Function.iterate_zero, id_eq, pow_zero, one_mul] rw [Nat.mod_eq_of_lt hx1] exact ⟨rfl, hx0, hx1⟩ | succ m ih => rw [Function.iterate_succ', Function.comp_apply] obtain ⟨ih_eq, ih_pos, ih_lt⟩ := ih have hstep := bitword_is_aperiodic_of_prime_rotate_eq_mod n ((bitword_rotate n)^[m] x) hn ih_pos ih_lt refine ⟨?_, hstep.2.1, hstep.2.2⟩ rw [hstep.1, ih_eq] rw [Nat.mul_mod_mod, ← mul_assoc, pow_succ, mul_comm 2 (2 ^ m)]lemma bitword_is_aperiodic_of_prime_pow_mul_add_one_mul_mod (n q x : ℕ) (hn : 2 ≤ n) : (2 ^ (q * n + 1) * x) % (2 ^ n - 1) = (2 * x) % (2 ^ n - 1) := by have hM : 1 < 2 ^ n - 1 := by have : 4 ≤ 2 ^ n := by calc 4 = 2 ^ 2 := by norm_num _ ≤ 2 ^ n := Nat.pow_le_pow_right (by norm_num) hn omega have h_mod : (2 ^ n) % (2 ^ n - 1) = 1 := by have : 2 ^ n = (2 ^ n - 1) + 1 := by omega nth_rw 1 [this] rw [Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] have h_pow_mod : ((2 ^ n) ^ q) % (2 ^ n - 1) = 1 := by rw [Nat.pow_mod, h_mod, one_pow, Nat.mod_eq_of_lt hM] have h2k : 2 ^ (q * n + 1) = ((2 ^ n) ^ q) * 2 := by rw [pow_add, pow_one, mul_comm q n, pow_mul, mul_comm] rw [h2k, mul_assoc, Nat.mul_mod, h_pow_mod, one_mul, Nat.mod_mod]lemma bitword_is_aperiodic_of_prime_iterate_mul_apply {α : Type*} (f : α → α) (x : α) (r : ℕ) (h : f^[r] x = x) (m : ℕ) : f^[m * r] x = x := by induction m with | zero => simp | succ m ih => rw [add_one_mul, Function.iterate_add, Function.comp_apply, h, ih]theorem bitword_is_aperiodic_of_prime (n x : ℕ) (hn : n.Prime) (hx : x < 2 ^ n) (h0 : x ≠ 0) (h1 : x ≠ 2 ^ n - 1) : bitword_is_aperiodic n x := by intro r hr0 hrn hfix have hn2 : 2 ≤ n := hn.two_le have hx_pos : 0 < x := by omega have hx_lt : x < 2 ^ n - 1 := by omega have hcop : r.Coprime n := by have hdvd : ¬ n ∣ r := Nat.not_dvd_of_pos_of_lt hr0 hrn exact (hn.coprime_iff_not_dvd.mpr hdvd).symm obtain ⟨m, hm_lt, hm_mod⟩ := Nat.exists_mul_mod_eq_one_of_coprime hcop hn2 have h_div_mod : m * r = (r * m / n) * n + 1 := by have hdiv := (Nat.div_add_mod (r * m) n).symm rw [hm_mod, mul_comm n] at hdiv rw [mul_comm m r] exact hdiv set q := r * m / n have hfix_k : (bitword_rotate n)^[m * r] x = x := bitword_is_aperiodic_of_prime_iterate_mul_apply (bitword_rotate n) x r hfix m have h_mod_k := (bitword_is_aperiodic_of_prime_iterate_eq_mod n hn2 x hx_pos hx_lt (m * r)).1 rw [h_div_mod] at h_mod_k hfix_k rw [bitword_is_aperiodic_of_prime_pow_mul_add_one_mul_mod n q x hn2] at h_mod_k have h_rot1 := (bitword_is_aperiodic_of_prime_rotate_eq_mod n x hn2 hx_pos hx_lt).1 rw [← h_rot1] at h_mod_k rw [h_mod_k] at hfix_k have h_or := bitword_is_aperiodic_of_prime_rotate_eq_self (by omega) hx hfix_k rcases h_or with hx0 | hx1' · exact h0 hx0 · exact h1 hx1'