geodetic_c_condition_iff_product_condition_three
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
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
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.
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).
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
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.
uses
Nat.le_succ,congrArg,Fin.val,Finset.mem_Iic.mpr,le_rfl,Finset.mul_le_prod,Nat.mul_le_mulrefine ⟨?_, ?_⟩ · 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
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.
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, 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).
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]
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.
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- 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
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=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