AFTD Auto-Formalizing Theoretical Domains

brgc_necklace_first_rank_mod_four

theoremverified

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.

  1. 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.

    line 3

    uses brgc_necklace_first_rank_word_odd

      have hodd := brgc_necklace_first_rank_word_odd hn ht
  2. brgc_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.

    lines 4–5

    uses Nat.xor_mod_two_pow

      have hx : brgc_word t % 2 = (t % 2) ^^^ ((t / 2) % 2) :=
        Nat.xor_mod_two_pow (n := 1)
  3. 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.

    lines 6–7

      by_contra h
      have hcases : t % 4 = 0 ∨ t % 4 = 3 := by omega
  4. 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.

    lines 8–11

      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
  5. 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.

    lines 12–14

      · 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

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
See it in the graphDiscuss this resultChallenge it