dimension_lifting_recurrence_bound
Let f(p, d) ≥ 0 and g(p) ≥ 0 with g nondecreasing, f(p, k) ≤ p·g(p) for p ≥ 1, and for every p ≥ 1, d > k there are positive integers p_i ≤ p/2 with Σ p_i ≤ p and f(p, d) ≤ f(p, d−1) + Σ f(p_i, d). Then f(p, d) ≤ p·g(p)·C(⌊log₂ p⌋ + d − k, d − k) for all p ≥ 1, d ≥ k.
Statement
theorem dimension_lifting_recurrence_bound (k : ℕ) (f : ℕ → ℕ → ℝ) (g : ℕ → ℝ) (hf : ∀ p d, 0 ≤ f p d) (hg : ∀ p, 0 ≤ g p) (hmono : Monotone g) (hbase : ∀ p, 1 ≤ p → f p k ≤ p * g p) (hrec : ∀ p, 1 ≤ p → ∀ d, k < d → ∃ ps : List ℕ, (∀ x ∈ ps, 1 ≤ x ∧ 2 * x ≤ p) ∧ ps.sum ≤ p ∧ f p d ≤ f p (d - 1) + (ps.map (fun x => f x d)).sum) : ∀ p, 1 ≤ p → ∀ d, k ≤ d → f p d ≤ p * g p * ((Nat.log 2 p + (d - k)).choose (d - k))
- Formalizes
- arXiv:2610.16703 (Piercing boxes and products of trees), Lemma 2.3.
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem is proved by induction on the dimension difference m = d - k. For the inductive step, strong induction on p bounds each term in the partition ps: because every part satisfies x ≤ p/2, the logarithmic term drops by at least 1, allowing the strong induction hypothesis and the monotonicity of g to bound the partition's total sum by p · g(p) · C(⌊log₂ p⌋ - 1 + (m + 1), m + 1). Adding this to the inductive bound on f(p, k + m) and applying Pascal's recurrence identity completes the step for p ≥ 2, while the case p = 1 is immediate because any valid partition must be empty.
For any positive integer L and any m, C(L + m, m) + C(L - 1 + (m + 1), m + 1) = C(L + (m + 1), m + 1).
Since L ≥ 1, linear integer arithmetic gives (L - 1) + (m + 1) = L + m. Substituting this equality into the second term changes it to C(L + m, m + 1). By Pascal's recurrence Nat.choose_succ_succ with n = L + m and k = m, the sum equals C((L + m) + 1, m + 1) = C(L + (m + 1), m + 1).
uses
Nat.choose_succ_succlemma dimension_lifting_recurrence_bound_choose_pascal_step (L m : ℕ) (hL : 1 ≤ L) : (L + m).choose m + (L - 1 + (m + 1)).choose (m + 1) = (L + (m + 1)).choose (m + 1) := by have heq : L - 1 + (m + 1) = L + m := by lia rw [heq] have h_id := (Nat.choose_succ_succ (L + m) m).symm have heq2 : (L + m).succ = L + (m + 1) := by lia rw [heq2] at h_id exact h_id
If each element x of a list ps satisfies f(x) ≤ x · C, then the sum of f over ps is bounded by (Σ ps) · C.
The claim is proved by structural induction on ps. The empty list case is trivial (0 ≤ 0). For a cons list x :: xs, the sum splits into f(x) + Σ_{y ∈ xs} f(y). Applying the hypothesis f(x) ≤ x · C to the head and the induction hypothesis Σ_{y ∈ xs} f(y) ≤ (Σ xs) · C to the tail, linear arithmetic combines the bounds to (x + Σ xs) · C.
uses
List.map_cons,List.sum_cons,Nat.cast_add,List.mem_cons_self,List.mem_cons_of_memlemma dimension_lifting_recurrence_bound_list_sum_bound (ps : List ℕ) (f : ℕ → ℝ) (C : ℝ) (h : ∀ x ∈ ps, f x ≤ (x : ℝ) * C) : (ps.map f).sum ≤ (ps.sum : ℝ) * C := by induction ps with | nil => simp | cons x xs ih => simp only [List.map_cons, List.sum_cons, Nat.cast_add] have hx : f x ≤ (x : ℝ) * C := h x (List.mem_cons_self ..) have hxs : (xs.map f).sum ≤ (xs.sum : ℝ) * C := ih (fun y hy => h y (List.mem_cons_of_mem _ hy)) linarith
The theorem is reparameterized by induction on m = d - k, and the base case m = 0 holds: f(p, k) ≤ p · g(p) · C(⌊log₂ p⌋ + 0, 0) for all p ≥ 1.
We formulate an induction hypothesis H asserting that for all m and all p ≥ 1, f(p, k + m) ≤ p · g(p) · C(⌊log₂ p⌋ + m, m), and proceed by induction on m. In the base case m = 0, the dimension is k + 0 = k and C(⌊log₂ p⌋ + 0, 0) = 1. The target simplifies to f(p, k) ≤ p · g(p), which is directly assumed by the base hypothesis hbase.
uses
add_zero,Nat.choose_zero_right,Nat.cast_one,mul_onetheorem dimension_lifting_recurrence_bound (k : ℕ) (f : ℕ → ℕ → ℝ) (g : ℕ → ℝ) (hf : ∀ p d, 0 ≤ f p d) (hg : ∀ p, 0 ≤ g p) (hmono : Monotone g) (hbase : ∀ p, 1 ≤ p → f p k ≤ p * g p) (hrec : ∀ p, 1 ≤ p → ∀ d, k < d → ∃ ps : List ℕ, (∀ x ∈ ps, 1 ≤ x ∧ 2 * x ≤ p) ∧ ps.sum ≤ p ∧ f p d ≤ f p (d - 1) + (ps.map (fun x => f x d)).sum) : ∀ p, 1 ≤ p → ∀ d, k ≤ d → f p d ≤ p * g p * ((Nat.log 2 p + (d - k)).choose (d - k)) := by have H : ∀ m : ℕ, ∀ p, 1 ≤ p → f p (k + m) ≤ p * g p * ((Nat.log 2 p + m).choose m) := by intro m induction m with | zero => intro p hp simp only [add_zero, Nat.choose_zero_right, Nat.cast_one, mul_one] exact hbase p hp
For the induction step from m to m + 1, strong induction on p ≥ 1 is set up, and for p ≥ 2, the recurrence unpacks a partition ps and bounds the lower-dimension term f(p, k + m).
To prove the statement for m + 1, we use strong induction on p with Nat.strong_induction_on, assuming the bound holds for all positive x < p at dimension k + m + 1. We split cases on p using Nat.lt_or_ge: either p ≥ 2 or p ≤ 1. For p ≥ 2, the recurrence hypothesis hrec at dimension k + (m + 1) > k yields a list ps of positive integers with 2x ≤ p for all x ∈ ps, Σ ps ≤ p, and f(p, k + m + 1) ≤ f(p, k + m) + Σ_{x ∈ ps} f(x, k + m + 1). The outer induction hypothesis on m bounds the first term by f(p, k + m) ≤ p · g(p) · C(⌊log₂ p⌋ + m, m).
uses
Nat.strong_induction_on,Nat.lt_or_ge| succ m ih => intro p induction p using Nat.strong_induction_on with | h p ih_p => intro hp rcases (Nat.lt_or_ge 1 p) with hp_gt | hp_le · -- p ≥ 2 have hp2 : 2 ≤ p := hp_gt obtain ⟨ps, hps_prop, hps_sum, hrec_le⟩ := hrec p hp (k + (m + 1)) (by lia) have h_pred : k + (m + 1) - 1 = k + m := by lia rw [h_pred] at hrec_le have h_ih_p : f p (k + m) ≤ p * g p * ((Nat.log 2 p + m).choose m) := ih p hpEach partition element x ∈ ps satisfies f(x, k + m + 1) ≤ x · C, where C = g(p) · C(⌊log₂ p⌋ - 1 + (m + 1), m + 1).
For each x ∈ ps, the recurrence guarantees 1 ≤ x and 2x ≤ p, so x < p. The inner strong induction hypothesis on p applies to x at dimension k + m + 1, giving f(x, k + m + 1) ≤ x · g(x) · C(⌊log₂ x⌋ + m + 1, m + 1). Since x ≤ p and g is monotone, g(x) ≤ g(p). From 2x ≤ p, monotonicity of the base-2 logarithm gives ⌊log₂(2x)⌋ ≤ ⌊log₂ p⌋. Since ⌊log₂(2x)⌋ = ⌊log₂ x⌋ + 1 by Nat.log_mul_base, we have ⌊log₂ x⌋ + 1 ≤ ⌊log₂ p⌋, which implies ⌊log₂ x⌋ ≤ ⌊log₂ p⌋ - 1. Monotonicity of binomial coefficients then bounds C(⌊log₂ x⌋ + m + 1, m + 1) ≤ C(⌊log₂ p⌋ - 1 + (m + 1), m + 1). Combining these inequalities yields f(x, k + m + 1) ≤ x · C.
uses
Nat.mul_comm,Nat.log_mono_right,Nat.log_mul_base,Nat.choose_le_choose,mul_le_mul_of_nonneg_left,Nat.cast_nonneg,mul_le_mul_of_nonneg_right,mul_nonneglet C : ℝ := g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) have h_elem : ∀ x ∈ ps, f x (k + (m + 1)) ≤ (x : ℝ) * C := by intro x hx have hx_prop := hps_prop x hx have hx1 : 1 ≤ x := hx_prop.1 have hxp : 2 * x ≤ p := hx_prop.2 have hx_lt_p : x < p := by lia have hx_ih := ih_p x hx_lt_p hx1 have hx_le_p : x ≤ p := by lia have hg_le : g x ≤ g p := hmono hx_le_p have hlog_le : Nat.log 2 x + 1 ≤ Nat.log 2 p := by have h1 : Nat.log 2 (x * 2) ≤ Nat.log 2 p := by rw [Nat.mul_comm] exact Nat.log_mono_right hxp have h2 : Nat.log 2 (x * 2) = Nat.log 2 x + 1 := Nat.log_mul_base (by decide) (by lia) rwa [h2] at h1 have hchoose_le : (Nat.log 2 x + (m + 1)).choose (m + 1) ≤ (Nat.log 2 p - 1 + (m + 1)).choose (m + 1) := Nat.choose_le_choose (m + 1) (by lia) refine hx_ih.trans ?_ have h1 : (x : ℝ) * g x ≤ (x : ℝ) * g p := mul_le_mul_of_nonneg_left hg_le (Nat.cast_nonneg x) have hstep1 : (x : ℝ) * g x * ((Nat.log 2 x + (m + 1)).choose (m + 1) : ℝ) ≤ (x : ℝ) * g p * ((Nat.log 2 x + (m + 1)).choose (m + 1) : ℝ) := mul_le_mul_of_nonneg_right h1 (Nat.cast_nonneg _) have hchoose_cast : ((Nat.log 2 x + (m + 1)).choose (m + 1) : ℝ) ≤ ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) := by exact_mod_cast hchoose_le have hstep2 : (x : ℝ) * g p * ((Nat.log 2 x + (m + 1)).choose (m + 1) : ℝ) ≤ (x : ℝ) * g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) := mul_le_mul_of_nonneg_left hchoose_cast (mul_nonneg (Nat.cast_nonneg x) (hg p)) have hstep_comb : (x : ℝ) * g x * ((Nat.log 2 x + (m + 1)).choose (m + 1) : ℝ) ≤ (x : ℝ) * g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) := hstep1.trans hstep2 have heq_C : (x : ℝ) * g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) = (x : ℝ) * C := by dsimp [C] ring rw [heq_C] at hstep_comb exact hstep_comb
Summing over the partition ps and applying Pascal's step completes the induction step for p ≥ 2.
Applying dimension_lifting_recurrence_bound_list_sum_bound to ps and C bounds the partition sum by (Σ ps) · C ≤ p · C = p · g(p) · C(⌊log₂ p⌋ - 1 + (m + 1), m + 1). Adding this to the bound for f(p, k + m) factors out p · g(p), leaving C(⌊log₂ p⌋ + m, m) + C(⌊log₂ p⌋ - 1 + (m + 1), m + 1). Since p ≥ 2, L = ⌊log₂ p⌋ ≥ 1 by Nat.log_pos. Pascal's step lemma dimension_lifting_recurrence_bound_choose_pascal_step evaluates this sum to C(⌊log₂ p⌋ + m + 1, m + 1). Combining this with the recurrence inequality completes the case p ≥ 2.
uses
dimension_lifting_recurrence_bound_list_sum_bound,mul_nonneg,Nat.cast_nonneg,Nat.cast_le,Nat.log_pos,dimension_lifting_recurrence_bound_choose_pascal_step,add_le_addhave h_sum_le := dimension_lifting_recurrence_bound_list_sum_bound ps (fun x => f x (k + (m + 1))) C h_elem have hC_nonneg : 0 ≤ C := mul_nonneg (hg p) (Nat.cast_nonneg _) have h_sum_le_p : (ps.sum : ℝ) * C ≤ (p : ℝ) * C := by have : (ps.sum : ℝ) ≤ (p : ℝ) := Nat.cast_le.mpr hps_sum nlinarith have h_sum_final : (ps.map (fun x => f x (k + (m + 1)))).sum ≤ (p : ℝ) * C := h_sum_le.trans h_sum_le_p have hL_pos : 1 ≤ Nat.log 2 p := Nat.log_pos (by decide) hp2 have h_pascal := dimension_lifting_recurrence_bound_choose_pascal_step (Nat.log 2 p) m hL_pos have h_pascal_R : ((Nat.log 2 p + m).choose m : ℝ) + ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) = ((Nat.log 2 p + (m + 1)).choose (m + 1) : ℝ) := by exact_mod_cast h_pascal have h_sum_bound : (p : ℝ) * C = (p : ℝ) * g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) := by dsimp [C] ring rw [h_sum_bound] at h_sum_final refine hrec_le.trans ?_ calc f p (k + m) + (ps.map (fun x => f x (k + (m + 1)))).sum ≤ (p : ℝ) * g p * ((Nat.log 2 p + m).choose m : ℝ) + (p : ℝ) * g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) := add_le_add h_ih_p h_sum_final _ = (p : ℝ) * g p * (((Nat.log 2 p + m).choose m : ℝ) + ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ)) := by ring _ = (p : ℝ) * g p * ((Nat.log 2 p + (m + 1)).choose (m + 1) : ℝ) := by rw [h_pascal_R]
For p = 1, the partition ps is necessarily empty, and the bound follows directly from the induction hypothesis on m.
When p = 1, any element x ∈ ps must satisfy 1 ≤ x and 2x ≤ 1, which has no integer solution. Thus ps = [], so the partition sum is zero and f(1, k + m + 1) ≤ f(1, k + m). Since ⌊log₂ 1⌋ = 0, C(⌊log₂ 1⌋ + m, m) = C(m, m) = 1, so the outer induction hypothesis gives f(1, k + m) ≤ g(1). Similarly, the target bound at m + 1 evaluates to 1 · g(1) · C(0 + m + 1, m + 1) = g(1). Transitivity closes the case p = 1.
uses
List.mem_cons_self,List.map_nil,List.sum_nil,add_zero,Nat.log_one_right,zero_add,Nat.choose_self,Nat.cast_one,mul_one· -- p = 1 have hp1 : p = 1 := by lia subst hp1 obtain ⟨ps, hps_prop, _, hrec_le⟩ := hrec 1 (by lia) (k + (m + 1)) (by lia) have hps_nil : ps = [] := by cases ps with | nil => rfl | cons x xs => have := (hps_prop x (List.mem_cons_self ..)).2 have := (hps_prop x (List.mem_cons_self ..)).1 lia rw [hps_nil] at hrec_le simp only [List.map_nil, List.sum_nil, add_zero] at hrec_le have h_pred : k + (m + 1) - 1 = k + m := by lia rw [h_pred] at hrec_le have h_ih := ih 1 (by lia) have h_log : Nat.log 2 1 = 0 := Nat.log_one_right 2 rw [h_log] at h_ih ⊢ simp only [zero_add, Nat.choose_self, Nat.cast_one, mul_one] at h_ih ⊢ exact hrec_le.trans h_ih
Specializing H with m = d - k yields the theorem for all p ≥ 1 and d ≥ k.
Given p ≥ 1 and d ≥ k, we instantiate H with m = d - k. Since k ≤ d, Nat.add_sub_of_le gives k + (d - k) = d. Rewriting this sum in H completes the proof.
uses
Nat.add_sub_of_leintro p hp d hd have h := H (d - k) p hp rwa [Nat.add_sub_of_le hd] at h
Nat.choose_succ_succ- Pascal's recurrence for binomial coefficients: Nat.choose (n + 1) (k + 1) = Nat.choose n k + Nat.choose n (k + 1).
List.map_cons- Mapping a function over a cons list applies the function to the head and maps over the tail: List.map f (a :: l) = f a :: List.map f l.
List.sum_cons- The sum of a cons list is the head element plus the sum of the tail: (a :: l).sum = a + l.sum.
Nat.cast_add- The cast from natural numbers to real numbers preserves addition: ↑(m + n) = ↑m + ↑n.
List.mem_cons_self- The head element of a list is a member of that list: a ∈ a :: l.
List.mem_cons_of_mem- If an element belongs to the tail of a list, it belongs to the whole list: a ∈ l → a ∈ y :: l.
add_zero- Adding zero to any element leaves it unchanged: a + 0 = a.
Nat.choose_zero_right- Choosing 0 from any natural number n equals 1: Nat.choose n 0 = 1.
Nat.cast_one- The cast of 1 as a natural number is 1 in the target semiring: ↑1 = 1.
mul_one- Multiplying any element by 1 leaves it unchanged: a * 1 = a.
Nat.strong_induction_on- Principle of strong induction on natural numbers: to prove P(n) for all n, it suffices to prove P(n) assuming P(m) holds for all m < n.
Nat.lt_or_ge- For any two natural numbers n and m, either n < m or n ≥ m.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Nat.log_mono_right- The discrete base-b logarithm is nondecreasing in its argument: if n ≤ m, then Nat.log b n ≤ Nat.log b m.
Nat.log_mul_base- For base b > 1 and n ≠ 0, multiplying n by b increases its discrete logarithm by 1: Nat.log b (n * b) = Nat.log b n + 1.
Nat.choose_le_choose- The binomial coefficient Nat.choose a c is nondecreasing in a: if a ≤ b, then Nat.choose a c ≤ Nat.choose b c.
mul_le_mul_of_nonneg_left- Multiplying an inequality by a nonnegative element on the left preserves the inequality: if b ≤ c and 0 ≤ a, then a * b ≤ a * c.
Nat.cast_nonneg- The cast of any natural number to an ordered semiring is nonnegative: 0 ≤ ↑n.
mul_le_mul_of_nonneg_right- Multiplying an inequality by a nonnegative element on the right preserves the inequality: if b ≤ c and 0 ≤ a, then b * a ≤ c * a.
mul_nonneg- The product of two nonnegative elements is nonnegative: if 0 ≤ a and 0 ≤ b, then 0 ≤ a * b.
dimension_lifting_recurrence_bound_list_sum_bound- If each element x of a list ps satisfies f(x) ≤ x * C, then the sum of f(x) over ps is bounded by (ps.sum) * C.
Nat.cast_le- The cast from natural numbers to real numbers preserves non-strict inequalities: ↑m ≤ ↑n ↔ m ≤ n.
Nat.log_pos- For base b > 1, if b ≤ n, then Nat.log b n is strictly positive (at least 1).
dimension_lifting_recurrence_bound_choose_pascal_step- For L ≥ 1, Nat.choose (L + m) m + Nat.choose (L - 1 + (m + 1)) (m + 1) = Nat.choose (L + (m + 1)) (m + 1).
add_le_add- Adding two inequalities preserves the inequality: if a ≤ b and c ≤ d, then a + c ≤ b + d.
List.map_nil- Mapping a function over the empty list produces the empty list: List.map f [] = [].
List.sum_nil- The sum of the empty list is zero: [].sum = 0.
Nat.log_one_right- The logarithm of 1 in any base is 0: Nat.log b 1 = 0.
zero_add- Zero is the left identity for addition: 0 + a = a.
Nat.choose_self- Choosing n from n equals 1: Nat.choose n n = 1.
Nat.add_sub_of_le- If a ≤ b, then a + (b - a) = b for natural numbers.
- The recurrence in Lean is formalized using list operations (List.map and List.sum) instead of set-indexed summations, requiring a dedicated helper lemma to distribute the linear bound across the list elements.
- Linear integer arithmetic tactics (lia and linarith) discharge arithmetic identities on indices, such as (L - 1) + (m + 1) = L + m and the fact that 2 * x ≤ 1 has no positive integer solutions.
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.
lemma dimension_lifting_recurrence_bound_choose_pascal_step (L m : ℕ) (hL : 1 ≤ L) : (L + m).choose m + (L - 1 + (m + 1)).choose (m + 1) = (L + (m + 1)).choose (m + 1) := by have heq : L - 1 + (m + 1) = L + m := by lia rw [heq] have h_id := (Nat.choose_succ_succ (L + m) m).symm have heq2 : (L + m).succ = L + (m + 1) := by lia rw [heq2] at h_id exact h_idlemma dimension_lifting_recurrence_bound_list_sum_bound (ps : List ℕ) (f : ℕ → ℝ) (C : ℝ) (h : ∀ x ∈ ps, f x ≤ (x : ℝ) * C) : (ps.map f).sum ≤ (ps.sum : ℝ) * C := by induction ps with | nil => simp | cons x xs ih => simp only [List.map_cons, List.sum_cons, Nat.cast_add] have hx : f x ≤ (x : ℝ) * C := h x (List.mem_cons_self ..) have hxs : (xs.map f).sum ≤ (xs.sum : ℝ) * C := ih (fun y hy => h y (List.mem_cons_of_mem _ hy)) linariththeorem dimension_lifting_recurrence_bound (k : ℕ) (f : ℕ → ℕ → ℝ) (g : ℕ → ℝ) (hf : ∀ p d, 0 ≤ f p d) (hg : ∀ p, 0 ≤ g p) (hmono : Monotone g) (hbase : ∀ p, 1 ≤ p → f p k ≤ p * g p) (hrec : ∀ p, 1 ≤ p → ∀ d, k < d → ∃ ps : List ℕ, (∀ x ∈ ps, 1 ≤ x ∧ 2 * x ≤ p) ∧ ps.sum ≤ p ∧ f p d ≤ f p (d - 1) + (ps.map (fun x => f x d)).sum) : ∀ p, 1 ≤ p → ∀ d, k ≤ d → f p d ≤ p * g p * ((Nat.log 2 p + (d - k)).choose (d - k)) := by have H : ∀ m : ℕ, ∀ p, 1 ≤ p → f p (k + m) ≤ p * g p * ((Nat.log 2 p + m).choose m) := by intro m induction m with | zero => intro p hp simp only [add_zero, Nat.choose_zero_right, Nat.cast_one, mul_one] exact hbase p hp | succ m ih => intro p induction p using Nat.strong_induction_on with | h p ih_p => intro hp rcases (Nat.lt_or_ge 1 p) with hp_gt | hp_le · -- p ≥ 2 have hp2 : 2 ≤ p := hp_gt obtain ⟨ps, hps_prop, hps_sum, hrec_le⟩ := hrec p hp (k + (m + 1)) (by lia) have h_pred : k + (m + 1) - 1 = k + m := by lia rw [h_pred] at hrec_le have h_ih_p : f p (k + m) ≤ p * g p * ((Nat.log 2 p + m).choose m) := ih p hp let C : ℝ := g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) have h_elem : ∀ x ∈ ps, f x (k + (m + 1)) ≤ (x : ℝ) * C := by intro x hx have hx_prop := hps_prop x hx have hx1 : 1 ≤ x := hx_prop.1 have hxp : 2 * x ≤ p := hx_prop.2 have hx_lt_p : x < p := by lia have hx_ih := ih_p x hx_lt_p hx1 have hx_le_p : x ≤ p := by lia have hg_le : g x ≤ g p := hmono hx_le_p have hlog_le : Nat.log 2 x + 1 ≤ Nat.log 2 p := by have h1 : Nat.log 2 (x * 2) ≤ Nat.log 2 p := by rw [Nat.mul_comm] exact Nat.log_mono_right hxp have h2 : Nat.log 2 (x * 2) = Nat.log 2 x + 1 := Nat.log_mul_base (by decide) (by lia) rwa [h2] at h1 have hchoose_le : (Nat.log 2 x + (m + 1)).choose (m + 1) ≤ (Nat.log 2 p - 1 + (m + 1)).choose (m + 1) := Nat.choose_le_choose (m + 1) (by lia) refine hx_ih.trans ?_ have h1 : (x : ℝ) * g x ≤ (x : ℝ) * g p := mul_le_mul_of_nonneg_left hg_le (Nat.cast_nonneg x) have hstep1 : (x : ℝ) * g x * ((Nat.log 2 x + (m + 1)).choose (m + 1) : ℝ) ≤ (x : ℝ) * g p * ((Nat.log 2 x + (m + 1)).choose (m + 1) : ℝ) := mul_le_mul_of_nonneg_right h1 (Nat.cast_nonneg _) have hchoose_cast : ((Nat.log 2 x + (m + 1)).choose (m + 1) : ℝ) ≤ ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) := by exact_mod_cast hchoose_le have hstep2 : (x : ℝ) * g p * ((Nat.log 2 x + (m + 1)).choose (m + 1) : ℝ) ≤ (x : ℝ) * g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) := mul_le_mul_of_nonneg_left hchoose_cast (mul_nonneg (Nat.cast_nonneg x) (hg p)) have hstep_comb : (x : ℝ) * g x * ((Nat.log 2 x + (m + 1)).choose (m + 1) : ℝ) ≤ (x : ℝ) * g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) := hstep1.trans hstep2 have heq_C : (x : ℝ) * g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) = (x : ℝ) * C := by dsimp [C] ring rw [heq_C] at hstep_comb exact hstep_comb have h_sum_le := dimension_lifting_recurrence_bound_list_sum_bound ps (fun x => f x (k + (m + 1))) C h_elem have hC_nonneg : 0 ≤ C := mul_nonneg (hg p) (Nat.cast_nonneg _) have h_sum_le_p : (ps.sum : ℝ) * C ≤ (p : ℝ) * C := by have : (ps.sum : ℝ) ≤ (p : ℝ) := Nat.cast_le.mpr hps_sum nlinarith have h_sum_final : (ps.map (fun x => f x (k + (m + 1)))).sum ≤ (p : ℝ) * C := h_sum_le.trans h_sum_le_p have hL_pos : 1 ≤ Nat.log 2 p := Nat.log_pos (by decide) hp2 have h_pascal := dimension_lifting_recurrence_bound_choose_pascal_step (Nat.log 2 p) m hL_pos have h_pascal_R : ((Nat.log 2 p + m).choose m : ℝ) + ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) = ((Nat.log 2 p + (m + 1)).choose (m + 1) : ℝ) := by exact_mod_cast h_pascal have h_sum_bound : (p : ℝ) * C = (p : ℝ) * g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) := by dsimp [C] ring rw [h_sum_bound] at h_sum_final refine hrec_le.trans ?_ calc f p (k + m) + (ps.map (fun x => f x (k + (m + 1)))).sum ≤ (p : ℝ) * g p * ((Nat.log 2 p + m).choose m : ℝ) + (p : ℝ) * g p * ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ) := add_le_add h_ih_p h_sum_final _ = (p : ℝ) * g p * (((Nat.log 2 p + m).choose m : ℝ) + ((Nat.log 2 p - 1 + (m + 1)).choose (m + 1) : ℝ)) := by ring _ = (p : ℝ) * g p * ((Nat.log 2 p + (m + 1)).choose (m + 1) : ℝ) := by rw [h_pascal_R] · -- p = 1 have hp1 : p = 1 := by lia subst hp1 obtain ⟨ps, hps_prop, _, hrec_le⟩ := hrec 1 (by lia) (k + (m + 1)) (by lia) have hps_nil : ps = [] := by cases ps with | nil => rfl | cons x xs => have := (hps_prop x (List.mem_cons_self ..)).2 have := (hps_prop x (List.mem_cons_self ..)).1 lia rw [hps_nil] at hrec_le simp only [List.map_nil, List.sum_nil, add_zero] at hrec_le have h_pred : k + (m + 1) - 1 = k + m := by lia rw [h_pred] at hrec_le have h_ih := ih 1 (by lia) have h_log : Nat.log 2 1 = 0 := Nat.log_one_right 2 rw [h_log] at h_ih ⊢ simp only [zero_add, Nat.choose_self, Nat.cast_one, mul_one] at h_ih ⊢ exact hrec_le.trans h_ih intro p hp d hd have h := H (d - k) p hp rwa [Nat.add_sub_of_le hd] at h