brgc_necklace_first_rank_mod_four
For length at least two, each first-occurrence rank of a nonconstant necklace is congruent to one or two modulo four.
Statement
theorem brgc_necklace_first_rank_mod_four {n t : ℕ} (hn : 2 ≤ n)
(ht : brgc_necklace_first_rank n t) : t % 4 = 1 ∨ t % 4 = 2- Source
- Supporting arithmetic and canonical-representative lemmas for OP-392, arXiv:2610.24758, Conjecture 1.
- Verified
- 25 Oct 2026
- Axioms
Quot.soundpropext- Built on 3
- brgc_necklace_first_rank_word_oddFor length at least two, the first nonconstant representative in Gray order has final bit one.
- brgc_necklace_first_rankt is the BRGC rank of the first occurrence of a nonconstant binary necklace of length n: t < 2^n, the word g(t) is neither 0^n nor 1^n,…
- brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
The proof, explained
The proof proceeds by contradiction. For any first-occurrence necklace rank t of length n ≥ 2, the binary reflected Gray code word brgc_word t = t ^^^ (t / 2) is known to be odd, meaning (t % 2) ^^^ ((t / 2) % 2) = 1. If t % 4 were neither 1 nor 2, it would have to be 0 or 3. However, when t % 4 = 0, both t and t / 2 are even, yielding 0 ^^^ 0 = 0 ≠ 1; and when t % 4 = 3, both t and t / 2 are odd, yielding 1 ^^^ 1 = 0 ≠ 1. Both cases contradict the oddness of the Gray code word.
The Gray code word of t is odd: brgc_word t % 2 = 1.
Applying brgc_necklace_first_rank_word_odd to the hypotheses that n ≥ 2 and that t is a first-occurrence necklace rank establishes that brgc_word t is odd.
uses
brgc_necklace_first_rank_word_oddhave hodd := brgc_necklace_first_rank_word_odd hn htbrgc_word t % 2 = (t % 2) ^^^ ((t / 2) % 2).
By definition, brgc_word t = t ^^^ (t / 2). Applying Nat.xor_mod_two_pow with n = 1 distributes reduction modulo 2^1 = 2 over the bitwise XOR.
uses
Nat.xor_mod_two_powhave hx : brgc_word t % 2 = (t % 2) ^^^ ((t / 2) % 2) := Nat.xor_mod_two_pow (n := 1)Assuming for contradiction that t % 4 is neither 1 nor 2, t % 4 must be 0 or 3.
We assume the negation of the conclusion for contradiction. Since the remainder of t modulo 4 must be 0, 1, 2, or 3, excluding 1 and 2 leaves only 0 and 3, which omega verifies by modular arithmetic.
by_contra h have hcases : t % 4 = 0 ∨ t % 4 = 3 := by omega
The case t % 4 = 0 leads to a contradiction.
We split into the two cases. In the first case, t % 4 = 0, so both t % 2 = 0 and (t / 2) % 2 = 0. Substituting these into the XOR reduction identity gives 1 = 0 ^^^ 0 = 0, a contradiction.
rcases hcases with hzero | hthree · have ha : t % 2 = 0 := by omega have hb : t / 2 % 2 = 0 := by omega simp [ha, hb, hodd] at hx
The case t % 4 = 3 also leads to a contradiction, concluding the proof.
In the remaining case, t % 4 = 3, so t is odd (t % 2 = 1) and t / 2 is also odd ((t / 2) % 2 = 1, since t = 4k + 3 implies t / 2 = 2k + 1). Substituting these into the XOR reduction identity gives 1 = 1 ^^^ 1 = 0, which is again a contradiction.
· have ha : t % 2 = 1 := by omega have hb : t / 2 % 2 = 1 := by omega simp [ha, hb, hodd] at hx
brgc_necklace_first_rank_word_odd- For n ≥ 2, the Gray code word of a first-occurrence necklace rank of length n is odd, that is, brgc_word t % 2 = 1.
Nat.xor_mod_two_pow- The bitwise XOR modulo 2^n distributes over XOR: (a ^^^ b) % 2^n = (a % 2^n) ^^^ (b % 2^n).
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.
theorem brgc_necklace_first_rank_mod_four {n t : ℕ} (hn : 2 ≤ n) (ht : brgc_necklace_first_rank n t) : t % 4 = 1 ∨ t % 4 = 2 := by have hodd := brgc_necklace_first_rank_word_odd hn ht have hx : brgc_word t % 2 = (t % 2) ^^^ ((t / 2) % 2) := Nat.xor_mod_two_pow (n := 1) by_contra h have hcases : t % 4 = 0 ∨ t % 4 = 3 := by omega rcases hcases with hzero | hthree · have ha : t % 2 = 0 := by omega have hb : t / 2 % 2 = 0 := by omega simp [ha, hb, hodd] at hx · have ha : t % 2 = 1 := by omega have hb : t / 2 % 2 = 1 := by omega simp [ha, hb, hodd] at hx