periodic_int_shift_eq_of_le
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
- periodic_count_eq_of_shift_balance_of_lower_boundFor a finite-period count balance C(v)+R(v)=t+R(v+h), a pointwise lower bound C(v)>=t forces C to be identically t.
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.
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.
uses
monotone_nat_of_le_succ,Nat.cast_add,Nat.cast_one,add_mul,one_mul,add_associntro 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)
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).
uses
Nat.cast_one,one_mulhave hu := hmono (show 1 ≤ n by omega) simp only [Nat.cast_one, one_mul] at hu
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.
uses
mul_commhave hp : R (v + (n : ℤ) * h) = R v := by simpa [mul_comm] using hperiod.int_mul h v
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.
uses
le_antisymmrw [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
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.
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)