AFTD Auto-Formalizing Theoretical Domains

dimension_lifting_recurrence_bound

theoremverifiedformalization

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.

  1. 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).

    lines 1–8

    uses Nat.choose_succ_succ

    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_id
  2. 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.

    lines 10–20

    uses List.map_cons, List.sum_cons, Nat.cast_add, List.mem_cons_self, List.mem_cons_of_mem

    lemma 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
  3. 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.

    lines 22–34

    uses add_zero, Nat.choose_zero_right, Nat.cast_one, mul_one

    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)) := 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
  4. 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).

    lines 35–46

    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 hp
  5. Each 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.

    lines 47–87

    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_nonneg

              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
  6. 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.

    lines 88–113

    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_add

              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]
  7. 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.

    lines 114–133

    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
  8. 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.

    lines 134–136

    uses Nat.add_sub_of_le

      intro 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.

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

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
See it in the graphDiscuss this resultChallenge it