AFTD Auto-Formalizing Theoretical Domains

periodic_int_shift_eq_of_le

theoremverified

A natural-valued function on the integers with a positive finite period that never decreases under a fixed integer shift is invariant under that shift.

Statement

theorem periodic_int_shift_eq_of_le
    (n : ℕ) (hn : 0 < n) (h : ℤ) (R : ℤ → ℕ)
    (hperiod : Function.Periodic R (n : ℤ))
    (hle : ∀ v, R v ≤ R (v + h)) :
    ∀ v, R (v + h) = R v
Source
Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635 Section 3. These class-model, pruning and colour-rigidity lemmas do not establish the unresolved graph covering value. No research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

To show that a periodic function R : ℤ → ℕ of positive period n that never decreases under an integer shift h is invariant under that shift, we consider the sequence j ↦ R(v + j * h) for j ∈ ℕ. Because R is nondecreasing under each shift by h, this sequence is monotone, which implies R(v + h) ≤ R(v + n * h) since 1 ≤ n. The n-periodicity of R ensures that shifting by n * h leaves the function unchanged, giving R(v + n * h) = R v and therefore R(v + h) ≤ R v; antisymmetry then forces R(v + h) = R v.

  1. For any fixed integer v, the sequence j ↦ R(v + j * h) is monotone nondecreasing on ℕ.

    Fix an arbitrary integer v. By monotone_nat_of_le_succ, a sequence on ℕ is monotone if every term is at most its successor, R(v + j * h) ≤ R(v + (j + 1) * h). Expanding (j + 1) * h = j * h + h and regrouping terms with add_assoc, this is precisely the assumption hle evaluated at v + j * h.

    lines 8–13

    uses monotone_nat_of_le_succ, Nat.cast_add, Nat.cast_one, add_mul, one_mul, add_assoc

      intro v
      have hmono : Monotone (fun j : ℕ => R (v + (j : ℤ) * h)) := by
        apply monotone_nat_of_le_succ
        intro j
        simpa only [Nat.cast_add, Nat.cast_one, add_mul, one_mul, add_assoc] using
          hle (v + (j : ℤ) * h)
  2. R(v + h) ≤ R(v + n * h).

    Since n > 0, we have 1 ≤ n by linear integer arithmetic. Applying the monotonicity of j ↦ R(v + j * h) to 1 ≤ n and simplifying 1 * h to h yields R(v + h) ≤ R(v + n * h).

    lines 14–15

    uses Nat.cast_one, one_mul

      have hu := hmono (show 1 ≤ n by omega)
      simp only [Nat.cast_one, one_mul] at hu
  3. Shifting by n * h leaves R invariant: R(v + n * h) = R v.

    Since R has period n, shifting by any integer multiple of n preserves R. Commuting the product n * h to h * n shows that this shift is a multiple of the period, so R(v + n * h) = R v.

    lines 16–17

    uses mul_comm

      have hp : R (v + (n : ℤ) * h) = R v := by
        simpa [mul_comm] using hperiod.int_mul h v
  4. R(v + h) ≤ R v, which together with R v ≤ R(v + h) implies R(v + h) = R v.

    Substituting R(v + n * h) = R v into R(v + h) ≤ R(v + n * h) yields R(v + h) ≤ R v. Since the hypothesis hle also provides R v ≤ R(v + h), antisymmetry of ≤ on ℕ (le_antisymm) concludes that R(v + h) = R v.

    lines 18–19

    uses le_antisymm

      rw [hp] at hu
      exact le_antisymm hu (hle v)
monotone_nat_of_le_succ
A sequence in a preorder is monotone if each term is less than or equal to its successor.
Nat.cast_add
Casting a sum of natural numbers to another additive structure with one equals the sum of the cast terms.
Nat.cast_one
Casting the natural number 1 to another structure with one yields 1.
add_mul
Multiplication distributes over addition on the right: (a + b) * c = a * c + b * c.
one_mul
Multiplying by 1 on the left is the identity: 1 * a = a.
add_assoc
Addition is associative: (a + b) + c = a + (b + c).
mul_comm
Multiplication in a commutative magma is commutative: a * b = b * a.
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.

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

open Finsettheorem periodic_int_shift_eq_of_le    (n : ℕ) (hn : 0 < n) (h : ℤ) (R : ℤ → ℕ)    (hperiod : Function.Periodic R (n : ℤ))    (hle : ∀ v, R v ≤ R (v + h)) :    ∀ v, R (v + h) = R v := by  intro v  have hmono : Monotone (fun j : ℕ => R (v + (j : ℤ) * h)) := by    apply monotone_nat_of_le_succ    intro j    simpa only [Nat.cast_add, Nat.cast_one, add_mul, one_mul, add_assoc] using      hle (v + (j : ℤ) * h)  have hu := hmono (show 1 ≤ n by omega)  simp only [Nat.cast_one, one_mul] at hu  have hp : R (v + (n : ℤ) * h) = R v := by    simpa [mul_comm] using hperiod.int_mul h v  rw [hp] at hu  exact le_antisymm hu (hle v)
See it in the graphDiscuss this resultChallenge it