AFTD Auto-Formalizing Theoretical Domains

geodetic_c_condition_iff_product_condition_two

theoremverifiedformalization

Let d ≥ 1 and let c : Fin d → ℕ be a monotone nondecreasing sequence with c(0) = 1. Then c satisfies the geodesic product condition for K = 2 if and only if c satisfies the arithmetic geodetic condition for K = 2 (that is, c(i) = 1 for all i < d - 1 and c(d - 1) ≤ 2).

Statement

theorem geodetic_c_condition_iff_product_condition_two (d : ℕ) (hd : 1 ≤ d)
    (c : Fin d → ℕ) (hc0 : c ⟨0, hd⟩ = 1) (hmono : Monotone c) :
    satisfies_geodetic_product_condition d c 2 ↔ satisfies_geodetic_c_condition d c 2
Formalizes
arXiv:2611.05762, Sec. 4.2
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • satisfies_geodetic_product_conditionA sequence c : Fin d → ℕ satisfies the geodesic product condition for bound K if for every index i : Fin d, the product of c(j) over all j…
  • satisfies_geodetic_c_conditionA sequence c : Fin d → ℕ satisfies the arithmetic geodetic condition for bound K if c(i) = 1 for all i with i.val + 1 < d, and c(i) ≤ K…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

Read back from the Lean

Let $d$ be a natural number such that $1 \le d$, and let $c : \text{Fin } d \to \mathbb{N}$ be a monotone function such that $c(0) = 1$. Then, the condition that $\prod_{j \le i} c(j) \le 2$ for all $i \in \text{Fin } d$ is equivalent to the condition that $c(i) = 1$ for all $i \in \text{Fin } d$ with $i + 1 < d$, and $c(i) \le 2$ for all $i \in \text{Fin } d$ with $i + 1 = d$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem proves that for a monotone nondecreasing sequence c on {0, ..., d - 1} starting at c(0) = 1, all prefix products ∏_{j ≤ i} c(j) are at most 2 if and only if c(i) = 1 for all i < d - 1 and c(d - 1) ≤ 2. In the forward direction, if any entry before the final index were at least 2, its successor would also be at least 2 by monotonicity, making their product at least 4, which exceeds the bound 2. In the reverse direction, all entries before the final index are 1, so every prefix product collapses to its single last factor c(i), which is at most 2.

  1. Every element satisfies c(j) ≥ 1, and the forward implication reduces to checking c(i) = 1 for i < d - 1 and c(i) ≤ 2 for i = d - 1

    We split the equivalence into both directions. In the forward direction, we assume the prefix product condition holds for K = 2. Since c is monotone nondecreasing and c(0) = 1, we have 1 = c(0) ≤ c(j) for all indices j. We then split the target geodetic condition into its two obligations: c(i) = 1 whenever i + 1 < d, and c(i) ≤ 2 whenever i + 1 = d.

    lines 5–11

    uses Nat.zero_le

      constructor
      · intro hprod
        have hc_ge_one : ∀ j : Fin d, 1 ≤ c j := fun j => by
          have hj : (⟨0, hd⟩ : Fin d) ≤ j := Nat.zero_le _
          have h := hmono hj
          rwa [hc0] at h
        refine ⟨?_, ?_⟩
  2. For any index i such that i + 1 < d, we have c(i) = 1

    Suppose for contradiction that c(i) ≠ 1. Since c(i) ≥ 1, this forces c(i) ≥ 2. Because i + 1 < d, the next index next_i = i + 1 exists in Fin d, and monotonicity gives c(next_i) ≥ c(i) ≥ 2. The indices i and next_i are distinct elements of the prefix set {j | j ≤ next_i}. Since every factor is at least 1, the total product over this prefix set is bounded below by the product of these two distinct factors: c(i) * c(next_i) ≤ ∏_{j ≤ next_i} c(j). But c(i) * c(next_i) ≥ 2 * 2 = 4, whereas the product condition requires this product to be at most 2, giving 4 ≤ 2, a contradiction.

    lines 12–35

    uses Nat.le_succ, congrArg, Finset.mem_Iic.mpr, le_rfl, Finset.mul_le_prod, Nat.mul_le_mul

        · intro i hi
          by_contra hne
          have h2 : 2 ≤ c i := by
            have : 1 ≤ c i := hc_ge_one i
            omega
          let next_i : Fin d := ⟨i.val + 1, hi⟩
          have hi_le : i ≤ next_i := Nat.le_succ i.val
          have hnext_ge : 2 ≤ c next_i := h2.trans (hmono hi_le)
          have h_ne : i ≠ next_i := by
            intro h
            have hval : i.val = next_i.val := congrArg Fin.val h
            dsimp [next_i] at hval
            omega
          have hi_mem : i ∈ Finset.Iic next_i := Finset.mem_Iic.mpr hi_le
          have hnext_mem : next_i ∈ Finset.Iic next_i := Finset.mem_Iic.mpr le_rfl
          have hmul : c i * c next_i ≤ ∏ j ∈ Finset.Iic next_i, c j :=
            Finset.mul_le_prod (fun j _ => hc_ge_one j) hi_mem hnext_mem h_ne
          have hprod_le : ∏ j ∈ Finset.Iic next_i, c j ≤ 2 := hprod next_i
          have : 4 ≤ 2 := by
            calc 4 = 2 * 2 := by rfl
            _ ≤ c i * c next_i := Nat.mul_le_mul h2 hnext_ge
            _ ≤ ∏ j ∈ Finset.Iic next_i, c j := hmul
            _ ≤ 2 := hprod_le
          omega
  3. For any index i such that i + 1 = d, we have c(i) ≤ 2

    Since i is in the prefix set {j | j ≤ i} and all terms are at least 1, the single term c(i) is bounded above by the full prefix product ∏_{j ≤ i} c(j). By the product condition, this product is at most 2, so c(i) ≤ 2.

    lines 36–40

    uses Finset.mem_Iic.mpr, le_rfl, Finset.single_le_prod'

        · intro i _
          have hi_mem : i ∈ Finset.Iic i := Finset.mem_Iic.mpr le_rfl
          have hle : c i ≤ ∏ j ∈ Finset.Iic i, c j :=
            Finset.single_le_prod' (fun j _ => hc_ge_one j) hi_mem
          exact hle.trans (hprod i)
  4. In the reverse direction, for any index i, the prefix product ∏_{j ≤ i} c(j) simplifies to c(i)

    Assume the arithmetic geodetic condition for K = 2, and fix an index i. For any b ≤ i with b ≠ i, we have b < i and hence b + 1 < d. The first part of the geodetic condition then gives c(b) = 1. Because every factor in the prefix product except possibly c(i) is 1, the product collapses to c(i).

    lines 41–54

    uses Finset.mem_Iic.mpr, le_rfl, Finset.mem_Iic.mp, lt_of_le_of_ne, Finset.prod_eq_single_of_mem

      · intro hc i
        have hi_mem : i ∈ Finset.Iic i := Finset.mem_Iic.mpr le_rfl
        have h_single : ∀ b ∈ Finset.Iic i, b ≠ i → c b = 1 := by
          intro b hb hne
          have hle : b ≤ i := Finset.mem_Iic.mp hb
          have hlt : b < i := lt_of_le_of_ne hle hne
          have hbd : b.val + 1 < d := by
            have : i.val < d := i.isLt
            have : b.val < i.val := hlt
            omega
          exact hc.1 b hbd
        have hprod : ∏ j ∈ Finset.Iic i, c j = c i :=
          Finset.prod_eq_single_of_mem i hi_mem h_single
        rw [hprod]
  5. For any index i, c(i) ≤ 2, completing the reverse direction

    Since i < d, we have i + 1 ≤ d. We case-split on whether i + 1 = d or i + 1 < d. If i + 1 = d, the second part of the geodetic condition directly yields c(i) ≤ 2. If i + 1 < d, the first part gives c(i) = 1 ≤ 2. Thus in both cases, the product ∏_{j ≤ i} c(j) = c(i) is at most 2.

    lines 55–59

    uses eq_or_lt_of_le

        have : i.val + 1 ≤ d := i.isLt
        rcases eq_or_lt_of_le this with h_eq | h_lt
        · exact hc.2 i h_eq
        · have := hc.1 i h_lt
          omega
Nat.zero_le
0 is less than or equal to any natural number
Nat.le_succ
Any natural number n is less than or equal to its successor n + 1
congrArg
Applying a function to equal arguments yields equal results: if a₁ = a₂, then f(a₁) = f(a₂)
Finset.mem_Iic.mpr
If x ≤ a, then x belongs to the interval of elements at most a (Finset.Iic a)
Finset.mem_Iic.mp
If x belongs to the interval Finset.Iic a, then x ≤ a
le_rfl
The inequality relation ≤ is reflexive: a ≤ a
Finset.mul_le_prod
In an ordered monoid with factors ≥ 1, the product of two distinct elements in a finite set is bounded above by the total product over that set
Nat.mul_le_mul
If n₁ ≤ n₂ and m₁ ≤ m₂, then n₁ * m₁ ≤ n₂ * m₂ for natural numbers
Finset.single_le_prod'
In an ordered monoid where all factors are ≥ 1, each individual element in a finite set is bounded above by the total product over the set
lt_of_le_of_ne
If a ≤ b and a ≠ b, then a < b
Finset.prod_eq_single_of_mem
If every element in a finite set except possibly a chosen element has value 1, the product over the set equals the value of that element
eq_or_lt_of_le
If a ≤ b, then either a = b or 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

/-- For nondecreasing c starting with 1, the product condition for K=2 is equivalent to c_i = 1 for i < d-1 and c_{d-1} ≤ 2. -/theorem geodetic_c_condition_iff_product_condition_two (d : ℕ) (hd : 1 ≤ d)    (c : Fin d → ℕ) (hc0 : c ⟨0, hd⟩ = 1) (hmono : Monotone c) :    satisfies_geodetic_product_condition d c 2 ↔ satisfies_geodetic_c_condition d c 2 := by  constructor  · intro hprod    have hc_ge_one : ∀ j : Fin d, 1 ≤ c j := fun j => by      have hj : (⟨0, hd⟩ : Fin d) ≤ j := Nat.zero_le _      have h := hmono hj      rwa [hc0] at h    refine ⟨?_, ?_⟩    · intro i hi      by_contra hne      have h2 : 2 ≤ c i := by        have : 1 ≤ c i := hc_ge_one i        omega      let next_i : Fin d := ⟨i.val + 1, hi⟩      have hi_le : i ≤ next_i := Nat.le_succ i.val      have hnext_ge : 2 ≤ c next_i := h2.trans (hmono hi_le)      have h_ne : i ≠ next_i := by        intro h        have hval : i.val = next_i.val := congrArg Fin.val h        dsimp [next_i] at hval        omega      have hi_mem : i ∈ Finset.Iic next_i := Finset.mem_Iic.mpr hi_le      have hnext_mem : next_i ∈ Finset.Iic next_i := Finset.mem_Iic.mpr le_rfl      have hmul : c i * c next_i ≤ ∏ j ∈ Finset.Iic next_i, c j :=        Finset.mul_le_prod (fun j _ => hc_ge_one j) hi_mem hnext_mem h_ne      have hprod_le : ∏ j ∈ Finset.Iic next_i, c j ≤ 2 := hprod next_i      have : 4 ≤ 2 := by        calc 4 = 2 * 2 := by rfl        _ ≤ c i * c next_i := Nat.mul_le_mul h2 hnext_ge        _ ≤ ∏ j ∈ Finset.Iic next_i, c j := hmul        _ ≤ 2 := hprod_le      omega    · intro i _      have hi_mem : i ∈ Finset.Iic i := Finset.mem_Iic.mpr le_rfl      have hle : c i ≤ ∏ j ∈ Finset.Iic i, c j :=        Finset.single_le_prod' (fun j _ => hc_ge_one j) hi_mem      exact hle.trans (hprod i)  · intro hc i    have hi_mem : i ∈ Finset.Iic i := Finset.mem_Iic.mpr le_rfl    have h_single : ∀ b ∈ Finset.Iic i, b ≠ i → c b = 1 := by      intro b hb hne      have hle : b ≤ i := Finset.mem_Iic.mp hb      have hlt : b < i := lt_of_le_of_ne hle hne      have hbd : b.val + 1 < d := by        have : i.val < d := i.isLt        have : b.val < i.val := hlt        omega      exact hc.1 b hbd    have hprod : ∏ j ∈ Finset.Iic i, c j = c i :=      Finset.prod_eq_single_of_mem i hi_mem h_single    rw [hprod]    have : i.val + 1 ≤ d := i.isLt    rcases eq_or_lt_of_le this with h_eq | h_lt    · exact hc.2 i h_eq    · have := hc.1 i h_lt      omega
See it in the graphDiscuss this resultChallenge it