AFTD Auto-Formalizing Theoretical Domains

weakly_consecutive_ends_coprime

theoremverified

In a weakly consecutive sequence, the first and last terms are coprime.

Statement

theorem weakly_consecutive_ends_coprime {k : ℕ} (σ : Equiv.Perm (Fin k))
    (hσ : is_weakly_consecutive σ) (hk : 0 < k) :
    Nat.Coprime ((σ ⟨0, hk⟩ : ℕ) + 1) ((σ ⟨k - 1, by omega⟩ : ℕ) + 1)
Source
step towards weakly_consecutive_one_at_end_of_isPrimePow (Weakly Consecutive Sequences (2024), arXiv:2401.09497, Conjecture 5.2, prime-power case)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • is_weakly_consecutiveA permutation s of {1, ..., k} is weakly consecutive if for all positions i, j and every m, whenever m divides s(i) and m divides i - j, m…
  • weakly_consecutive_first_dvdIn a weakly consecutive sequence of length k, the first term divides k.
  • fin_card_filter_dvdFor m > 0, exactly (k + m - 1)/m of the positions 0, ..., k-1 are multiples of m.
  • perm_card_filter_dvd_succFor any permutation s of {0, ..., k-1} and any m, exactly floor(k/m) positions j have m dividing s(j) + 1 (the values s(j) + 1 run over 1,…
Used by 1

Lean source view module on GitHub

theorem weakly_consecutive_ends_coprime {k : ℕ} (σ : Equiv.Perm (Fin k))    (hσ : is_weakly_consecutive σ) (hk : 0 < k) :    Nat.Coprime ((σ ⟨0, hk⟩ : ℕ) + 1) ((σ ⟨k - 1, by omega⟩ : ℕ) + 1) := by  apply Nat.coprime_of_dvd  intro p hp ha hb  have hp2 := hp.two_le  have hpk : p ∣ k := ha.trans (weakly_consecutive_first_dvd σ hσ hk)  have hk2 : 2 ≤ k := by    rcases Nat.lt_or_ge k 2 with h | h    · exfalso      have : k = 1 := by omega      subst this      have h0 : (σ ⟨0, hk⟩ : ℕ) = 0 := by omega      rw [h0] at ha      exact hp.one_lt.ne' (Nat.dvd_one.1 ha)    · exact h  -- the class of position 0, plus the last position, all hold multiples of p  set last : Fin k := ⟨k - 1, by omega⟩ with hlast  have hsub : insert last (Finset.univ.filter fun j : Fin k => p ∣ (j : ℕ)) ⊆      Finset.univ.filter fun j : Fin k => p ∣ (σ j : ℕ) + 1 := by    intro j    simp only [Finset.mem_insert, Finset.mem_filter, Finset.mem_univ, true_and]    rintro (rfl | hj)    · exact hb    · apply hσ p ⟨0, hk⟩ j ha      simp only [Nat.cast_zero, zero_sub]      exact (dvd_neg).2 (Int.natCast_dvd_natCast.2 hj)  have hnot : last ∉ (Finset.univ.filter fun j : Fin k => p ∣ (j : ℕ)) := by    simp only [Finset.mem_filter, Finset.mem_univ, true_and, hlast]    intro h    have h1 : p ∣ k - (k - 1) := Nat.dvd_sub hpk h    have : k - (k - 1) = 1 := by omega    rw [this] at h1    exact hp.one_lt.ne' (Nat.dvd_one.1 h1)  have hc := Finset.card_le_card hsub  rw [Finset.card_insert_of_notMem hnot, fin_card_filter_dvd p k (by omega),    perm_card_filter_dvd_succ σ p] at hc  have : k / p ≤ (k + p - 1) / p := Nat.div_le_div_right (by omega)  omega
See it in the graphDiscuss this resultChallenge it