-- Mathlib/.lake/packages/lean4/src/lean/Init/Data/Nat/Linear.lean
theorem Poly.of_denote_eq_cancelAux (ctx : Context) (fuel : Nat) (m₁ m₂ r₁ r₂ : Poly)
    (h : denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂)) : denote_eq ctx (r₁.reverse ++ m₁, r₂.reverse ++ m₂)

Proof state:
case pos
ctx : Context
fuel : Nat
ih✝ :
  ∀ (m₁ m₂ r₁ r₂ : Poly),
    denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) → denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)
r₁ r₂ m₁✝ m₂✝ : Poly
k₁ : Nat
v₁ : Var
m₁ : List (Nat × Var)
k₂ : Nat
m₂ : List (Nat × Var)
hltv hgtv : ¬blt v₁ v₁ = true
hltk : ¬k₁.blt k₂ = true
hgtk : k₂.blt k₁ = true
h : denote_eq ctx (cancelAux fuel m₁ m₂ ((k₁ - k₂, v₁) :: r₁) r₂)
ih : denote ctx r₁ + (denote ctx m₁ + (k₁ - k₂) * Var.denote ctx v₁) = denote ctx r₂ + denote ctx m₂
⊢ denote ctx r₁ + (denote ctx m₁ + k₁ * Var.denote ctx v₁) = denote ctx r₂ + (denote ctx m₂ + k₂ * Var.denote ctx v₁)

Tactic:
have haux : k₂ * Var.denote ctx v₁ ≤ k₁ * Var.denote ctx v₁ := Nat.mul_le_mul_right _ (Nat.le_of_lt (Nat.blt_eq.mp hgtk))

Result:
case pos
ctx : Context
fuel : Nat
ih✝ :
  ∀ (m₁ m₂ r₁ r₂ : Poly),
    denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) → denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)
r₁ r₂ m₁✝ m₂✝ : Poly
k₁ : Nat
v₁ : Var
m₁ : List (Nat × Var)
k₂ : Nat
m₂ : List (Nat × Var)
hltv hgtv : ¬blt v₁ v₁ = true
hltk : ¬k₁.blt k₂ = true
hgtk : k₂.blt k₁ = true
h : denote_eq ctx (cancelAux fuel m₁ m₂ ((k₁ - k₂, v₁) :: r₁) r₂)
ih : denote ctx r₁ + (denote ctx m₁ + (k₁ - k₂) * Var.denote ctx v₁) = denote ctx r₂ + denote ctx m₂
haux : k₂ * Var.denote ctx v₁ ≤ k₁ * Var.denote ctx v₁
⊢ denote ctx r₁ + (denote ctx m₁ + k₁ * Var.denote ctx v₁) = denote ctx r₂ + (denote ctx m₂ + k₂ * Var.denote ctx v₁)

Proof state:
case pos
ctx : Context
fuel : Nat
ih✝ :
  ∀ (m₁ m₂ r₁ r₂ : Poly),
    denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) → denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)
r₁ r₂ m₁✝ m₂✝ : Poly
k₁ : Nat
v₁ : Var
m₁ : List (Nat × Var)
k₂ : Nat
m₂ : List (Nat × Var)
hltv hgtv : ¬blt v₁ v₁ = true
hltk : k₁.blt k₂ = true
h : denote_eq ctx (cancelAux fuel m₁ m₂ r₁ ((k₂ - k₁, v₁) :: r₂))
ih : denote ctx r₁ + denote ctx m₁ = denote ctx r₂ + denote ctx m₂ + k₂ * Var.denote ctx v₁ - k₁ * Var.denote ctx v₁
haux : k₁ * Var.denote ctx v₁ ≤ k₂ * Var.denote ctx v₁
⊢ denote ctx r₁ + (denote ctx m₁ + k₁ * Var.denote ctx v₁) = denote ctx r₂ + (denote ctx m₂ + k₂ * Var.denote ctx v₁)

Tactic:
have ih := Nat.eq_add_of_sub_eq (Nat.le_trans haux (Nat.le_add_left ..)) ih.symm

Result:
case pos
ctx : Context
fuel : Nat
ih✝¹ :
  ∀ (m₁ m₂ r₁ r₂ : Poly),
    denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) → denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)
r₁ r₂ m₁✝ m₂✝ : Poly
k₁ : Nat
v₁ : Var
m₁ : List (Nat × Var)
k₂ : Nat
m₂ : List (Nat × Var)
hltv hgtv : ¬blt v₁ v₁ = true
hltk : k₁.blt k₂ = true
h : denote_eq ctx (cancelAux fuel m₁ m₂ r₁ ((k₂ - k₁, v₁) :: r₂))
ih✝ : denote ctx r₁ + denote ctx m₁ = denote ctx r₂ + denote ctx m₂ + k₂ * Var.denote ctx v₁ - k₁ * Var.denote ctx v₁
haux : k₁ * Var.denote ctx v₁ ≤ k₂ * Var.denote ctx v₁
ih : denote ctx r₂ + denote ctx m₂ + k₂ * Var.denote ctx v₁ = denote ctx r₁ + denote ctx m₁ + k₁ * Var.denote ctx v₁
⊢ denote ctx r₁ + (denote ctx m₁ + k₁ * Var.denote ctx v₁) = denote ctx r₂ + (denote ctx m₂ + k₂ * Var.denote ctx v₁)

Proof state:
case succ.h_2
ctx : Context
fuel : Nat
ih :
  ∀ (m₁ m₂ r₁ r₂ : Poly),
    denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) → denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)
m₂ r₁ r₂ m₁✝ m₂✝ : Poly
x✝ : m₂ = [] → False
h : denote_eq ctx (List.reverse r₁, List.reverse r₂ ++ m₂)
⊢ denote_eq ctx (List.reverse r₁, List.reverse r₂ ++ m₂)

Tactic:
assumption

Result:
no goals

Proof state:
case pos
ctx : Context
fuel : Nat
ih✝ :
  ∀ (m₁ m₂ r₁ r₂ : Poly),
    denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) → denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)
r₁ r₂ m₁✝ m₂✝ : Poly
k₁ : Nat
v₁ : Var
m₁ : List (Nat × Var)
k₂ : Nat
m₂ : List (Nat × Var)
hltv hgtv : ¬blt v₁ v₁ = true
hltk : k₁.blt k₂ = true
h : denote_eq ctx (cancelAux fuel m₁ m₂ r₁ ((k₂ - k₁, v₁) :: r₂))
ih : denote ctx r₁ + denote ctx m₁ = denote ctx r₂ + (denote ctx m₂ + (k₂ - k₁) * Var.denote ctx v₁)
⊢ denote ctx r₁ + (denote ctx m₁ + k₁ * Var.denote ctx v₁) = denote ctx r₂ + (denote ctx m₂ + k₂ * Var.denote ctx v₁)

Tactic:
have haux : k₁ * Var.denote ctx v₁ ≤ k₂ * Var.denote ctx v₁ := Nat.mul_le_mul_right _ (Nat.le_of_lt (Nat.blt_eq.mp hltk))

Result:
case pos
ctx : Context
fuel : Nat
ih✝ :
  ∀ (m₁ m₂ r₁ r₂ : Poly),
    denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) → denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)
r₁ r₂ m₁✝ m₂✝ : Poly
k₁ : Nat
v₁ : Var
m₁ : List (Nat × Var)
k₂ : Nat
m₂ : List (Nat × Var)
hltv hgtv : ¬blt v₁ v₁ = true
hltk : k₁.blt k₂ = true
h : denote_eq ctx (cancelAux fuel m₁ m₂ r₁ ((k₂ - k₁, v₁) :: r₂))
ih : denote ctx r₁ + denote ctx m₁ = denote ctx r₂ + (denote ctx m₂ + (k₂ - k₁) * Var.denote ctx v₁)
haux : k₁ * Var.denote ctx v₁ ≤ k₂ * Var.denote ctx v₁
⊢ denote ctx r₁ + (denote ctx m₁ + k₁ * Var.denote ctx v₁) = denote ctx r₂ + (denote ctx m₂ + k₂ * Var.denote ctx v₁)

Proof state:
case succ
ctx : Context
fuel : Nat
ih :
  ∀ (m₁ m₂ r₁ r₂ : Poly),
    denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) → denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)
m₁ m₂ r₁ r₂ : Poly
h :
  denote_eq ctx
    (match m₁, m₂ with
    | m₁, [] => (List.reverse r₁ ++ m₁, List.reverse r₂)
    | [], m₂ => (List.reverse r₁, List.reverse r₂ ++ m₂)
    | (k₁, v₁) :: m₁, (k₂, v₂) :: m₂ =>
      bif blt v₁ v₂ then cancelAux fuel m₁ ((k₂, v₂) :: m₂) ((k₁, v₁) :: r₁) r₂
      else
        bif blt v₂ v₁ then cancelAux fuel ((k₁, v₁) :: m₁) m₂ r₁ ((k₂, v₂) :: r₂)
        else
          bif k₁.blt k₂ then cancelAux fuel m₁ m₂ r₁ ((k₂ - k₁, v₁) :: r₂)
          else bif k₂.blt k₁ then cancelAux fuel m₁ m₂ ((k₁ - k₂, v₁) :: r₁) r₂ else cancelAux fuel m₁ m₂ r₁ r₂)
⊢ denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)

Tactic:
split at h <;> (try simp; assumption)

Result:
case succ.h_3
ctx : Context
fuel : Nat
ih :
  ∀ (m₁ m₂ r₁ r₂ : Poly),
    denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) → denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)
r₁ r₂ m₁✝¹ m₂✝¹ : Poly
k₁✝ : Nat
v₁✝ : Var
m₁✝ : List (Nat × Var)
k₂✝ : Nat
v₂✝ : Var
m₂✝ : List (Nat × Var)
h :
  denote_eq ctx
    (bif blt v₁✝ v₂✝ then cancelAux fuel m₁✝ ((k₂✝, v₂✝) :: m₂✝) ((k₁✝, v₁✝) :: r₁) r₂
    else
      bif blt v₂✝ v₁✝ then cancelAux fuel ((k₁✝, v₁✝) :: m₁✝) m₂✝ r₁ ((k₂✝, v₂✝) :: r₂)
      else
        bif k₁✝.blt k₂✝ then cancelAux fuel m₁✝ m₂✝ r₁ ((k₂✝ - k₁✝, v₁✝) :: r₂)
        else bif k₂✝.blt k₁✝ then cancelAux fuel m₁✝ m₂✝ ((k₁✝ - k₂✝, v₁✝) :: r₁) r₂ else cancelAux fuel m₁✝ m₂✝ r₁ r₂)
⊢ denote_eq ctx (List.reverse r₁ ++ (k₁✝, v₁✝) :: m₁✝, List.reverse r₂ ++ (k₂✝, v₂✝) :: m₂✝)

Proof state:
case succ.h_2
ctx : Context
fuel : Nat
ih :
  ∀ (m₁ m₂ r₁ r₂ : Poly),
    denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) → denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)
m₂ r₁ r₂ m₁✝ m₂✝ : Poly
x✝ : m₂ = [] → False
h : denote_eq ctx (List.reverse r₁, List.reverse r₂ ++ m₂)
⊢ denote_eq ctx (List.reverse r₁ ++ [], List.reverse r₂ ++ m₂)

Tactic:
simp

Result:
case succ.h_2
ctx : Context
fuel : Nat
ih :
  ∀ (m₁ m₂ r₁ r₂ : Poly),
    denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) → denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)
m₂ r₁ r₂ m₁✝ m₂✝ : Poly
x✝ : m₂ = [] → False
h : denote_eq ctx (List.reverse r₁, List.reverse r₂ ++ m₂)
⊢ denote_eq ctx (List.reverse r₁, List.reverse r₂ ++ m₂)