geodetic_c_condition_iff_product_condition_two
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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.
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.
uses
Nat.zero_leconstructor · 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 ⟨?_, ?_⟩
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.
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
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.
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)
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).
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]
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.
uses
eq_or_lt_of_lehave : 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
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.
/-- 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