AFTD Auto-Formalizing Theoretical Domains

geodetic_c_condition_iff_product_condition_three

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 = 3 if and only if c satisfies the arithmetic geodetic condition for K = 3 (that is, c(i) = 1 for all i < d - 1 and c(d - 1) ≤ 3).

Statement

theorem geodetic_c_condition_iff_product_condition_three (d : ℕ) (hd : 1 ≤ d)
    (c : Fin d → ℕ) (hc0 : c ⟨0, hd⟩ = 1) (hmono : Monotone c) :
    satisfies_geodetic_product_condition d c 3 ↔ satisfies_geodetic_c_condition d c 3
Formalizes
arXiv:2611.05762, Sec. 4.3
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

For any natural number $d \ge 1$ and any function $c : \mathrm{Fin}(d) \to \mathbb{N}$ satisfying $c(0) = 1$ and $c$ is monotone, $c$ satisfies the geodetic product condition with bound 3 if and only if $c$ satisfies the geodetic $c$-condition with bound 3.

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 equivalence is established in two directions. In the forward direction, assuming all prefix products are at most 3, monotonicity forces all terms before the last to equal 1; otherwise, two consecutive terms would each be at least 2, giving a prefix product of at least 2 × 2 = 4, a contradiction. In the backward direction, having all terms equal to 1 except possibly the last means every prefix product collapses to its final factor, which is bounded by 3 by the geodetic condition.

  1. Assume the product condition holds; then every term c(j) is at least 1.

    We split the bi-implication and begin the forward direction by assuming the product condition holds for K = 3. Since the sequence c is nondecreasing and c(0) = 1, for any index j we have 0 ≤ j (via Nat.zero_le), so monotonicity implies 1 = c(0) ≤ c(j).

    lines 5–10

    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
  2. For all indices i < d - 1, c(i) = 1.

    We split the geodetic condition into its two parts and first show c(i) = 1 whenever i < d - 1. Suppose for contradiction that c(i) ≠ 1. Since c(i) ≥ 1, we must have c(i) ≥ 2. Because i < d - 1, the next index i + 1 exists in Fin d, and monotonicity implies c(i + 1) ≥ c(i) ≥ 2. The indices i and i + 1 are distinct elements of the prefix interval {j | j ≤ i + 1}. Because every term is at least 1, the product over the entire prefix is at least the product of these two distinct factors: ∏_{j ≤ i+1} c(j) ≥ c(i) * c(i + 1) ≥ 2 * 2 = 4 (using Finset.mul_le_prod and Nat.mul_le_mul). But the product condition requires this product to be at most 3, yielding 4 ≤ 3, a contradiction.

    lines 11–35

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

        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 ≤ 3 := hprod next_i
          have : 4 ≤ 3 := 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
            _ ≤ 3 := hprod_le
          omega
  3. For the boundary index i = d - 1, c(i) ≤ 3.

    For an index i such that i + 1 = d, the single element c(i) belongs to the prefix product ∏_{j ≤ i} c(j). Because every factor is at least 1, any single factor is bounded by the product over the prefix (via Finset.single_le_prod'). By the product condition, this prefix product is at most 3, so c(i) ≤ 3. This completes the forward direction.

    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, every prefix product ∏_{j ≤ i} c(j) collapses to c(i).

    Assuming the geodetic condition, we fix an index i ∈ Fin d. For any b ≤ i with b ≠ i, we have b < i (via lt_of_le_of_ne), which implies b + 1 < d. The first part of the geodetic condition guarantees c(b) = 1 for all such b. Since every factor in the prefix product except possibly the endpoint c(i) is equal to 1, Finset.prod_eq_single_of_mem simplifies the product ∏_{j ≤ i} c(j) to just 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. Every term c(i) is at most 3, so the product condition holds.

    Having reduced the prefix product to c(i), it suffices to show c(i) ≤ 3. Since i ∈ Fin d, we have i + 1 ≤ d, which splits into either i + 1 = d or i + 1 < d (via eq_or_lt_of_le). If i + 1 = d, then c(i) ≤ 3 directly by the second part of the geodetic condition. If i + 1 < d, then c(i) = 1 ≤ 3 by the first part. In both cases c(i) ≤ 3, proving the product condition.

    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
For every natural number n, 0 ≤ n.
Nat.le_succ
For every natural number n, n ≤ n + 1.
congrArg
Equal arguments applied to the same function yield equal values: if a = b then f a = f b.
Fin.val
The natural number value underlying an index in Fin n.
Finset.mem_Iic.mpr
If a ≤ b, then a belongs to the locally closed interval of elements ≤ b.
Finset.mem_Iic.mp
If a belongs to the locally closed interval of elements ≤ b, then a ≤ b.
le_rfl
The less-than-or-equal relation is reflexive: a ≤ a for every a.
Finset.mul_le_prod
If every element in a finite set has value at least 1, the product of any two distinct elements is at most the product over the entire set.
Nat.mul_le_mul
Multiplication of natural numbers preserves inequalities: if a ≤ b and c ≤ d, then a * c ≤ b * d.
Finset.single_le_prod'
If every element in a finite set has value at least 1, any single element's value is at most the product over the whole set.
lt_of_le_of_ne
In a partial order, if a ≤ b and a ≠ b, then a < b.
Finset.prod_eq_single_of_mem
If every element of a finite set other than a evaluates to 1, the product over the set equals the value at a.
eq_or_lt_of_le
In a linear or partial order, 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=3 is equivalent to c_i = 1 for i < d-1 and c_{d-1} ≤ 3. -/theorem geodetic_c_condition_iff_product_condition_three (d : ℕ) (hd : 1 ≤ d)    (c : Fin d → ℕ) (hc0 : c ⟨0, hd⟩ = 1) (hmono : Monotone c) :    satisfies_geodetic_product_condition d c 3 ↔ satisfies_geodetic_c_condition d c 3 := 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 ≤ 3 := hprod next_i      have : 4 ≤ 3 := 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        _ ≤ 3 := 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