Helper definitions and theorems for constructing linear arithmetic proofs.

@[reducible, inline]

abbrev Nat.Linear.Var : Type

@[reducible, inline]

abbrev Nat.Linear.Context : Type

def Nat.Linear.fixedVar : Nat

When encoding polynomials. We use fixedVar for encoding numerals. The denotation of fixedVar is always 1.

def Nat.Linear.Var.denote (ctx : Context) (v : Var) : Nat

inductive Nat.Linear.Expr : Type

• num (v : Nat) : Expr
• var (i : Var) : Expr
• add (a b : Expr) : Expr
• mulL (k : Nat) (a : Expr) : Expr
• mulR (a : Expr) (k : Nat) : Expr

instance Nat.Linear.instInhabitedExpr : Inhabited Expr

instance Nat.Linear.instBEqExpr : BEq Expr

def Nat.Linear.Expr.denote (ctx : Context) : Expr → Nat

@[reducible, inline]

abbrev Nat.Linear.Poly : Type

def Nat.Linear.Poly.denote (ctx : Context) (p : Poly) : Nat

def Nat.Linear.Poly.insert (k : Nat) (v : Var) (p : Poly) : Poly

def Nat.Linear.Poly.norm (p : Poly) : Poly

def Nat.Linear.Poly.norm.go (p r : Poly) : Poly

def Nat.Linear.Poly.cancelAux (fuel : Nat) (m₁ m₂ r₁ r₂ : Poly) : Poly × Poly

def Nat.Linear.hugeFuel : Nat

def Nat.Linear.Poly.cancel (p₁ p₂ : Poly) : Poly × Poly

def Nat.Linear.Poly.isNum? (p : Poly) : Option Nat

def Nat.Linear.Poly.isZero (p : Poly) : Bool

def Nat.Linear.Poly.isNonZero (p : Poly) : Bool

def Nat.Linear.Poly.denote_eq (ctx : Context) (mp : Poly × Poly) : Prop

def Nat.Linear.Poly.denote_le (ctx : Context) (mp : Poly × Poly) : Prop

def Nat.Linear.Expr.toPoly (e : Expr) : Poly

def Nat.Linear.Expr.toPoly.go (coeff : Nat) : Expr → Poly → Poly

def Nat.Linear.Expr.toNormPoly (e : Expr) : Poly

def Nat.Linear.Expr.inc (e : Expr) : Expr

structure Nat.Linear.PolyCnstr : Type

• eq : Bool
• lhs : Poly
• rhs : Poly

instance Nat.Linear.instBEqPolyCnstr : BEq PolyCnstr

instance Nat.Linear.instLawfulBEqPolyCnstr : LawfulBEq PolyCnstr

structure Nat.Linear.ExprCnstr : Type

• eq : Bool
• lhs : Expr
• rhs : Expr

def Nat.Linear.PolyCnstr.denote (ctx : Context) (c : PolyCnstr) : Prop

def Nat.Linear.PolyCnstr.norm (c : PolyCnstr) : PolyCnstr

def Nat.Linear.PolyCnstr.isUnsat (c : PolyCnstr) : Bool

def Nat.Linear.PolyCnstr.isValid (c : PolyCnstr) : Bool

def Nat.Linear.ExprCnstr.denote (ctx : Context) (c : ExprCnstr) : Prop

def Nat.Linear.ExprCnstr.toPoly (c : ExprCnstr) : PolyCnstr

def Nat.Linear.ExprCnstr.toNormPoly (c : ExprCnstr) : PolyCnstr

def Nat.Linear.monomialToExpr (k : Nat) (v : Var) : Expr

def Nat.Linear.Poly.toExpr (p : Poly) : Expr

def Nat.Linear.Poly.toExpr.go (e : Expr) (p : Poly) : Expr

def Nat.Linear.PolyCnstr.toExpr (c : PolyCnstr) : ExprCnstr

theorem Nat.Linear.Poly.denote_insert (ctx : Context) (k : Nat) (v : Var) (p : Poly) : denote ctx (insert k v p) = denote ctx p + k * Var.denote ctx v

theorem Nat.Linear.Poly.denote_norm_go (ctx : Context) (p r : Poly) : denote ctx (norm.go p r) = denote ctx p + denote ctx r

theorem Nat.Linear.Poly.denote_sort (ctx : Context) (m : Poly) : denote ctx m.norm = denote ctx m

theorem Nat.Linear.Poly.denote_append (ctx : Context) (p q : Poly) : denote ctx (p ++ q) = denote ctx p + denote ctx q

theorem Nat.Linear.Poly.denote_cons (ctx : Context) (k : Nat) (v : Var) (p : Poly) : denote ctx ((k, v) :: p) = k * Var.denote ctx v + denote ctx p

theorem Nat.Linear.Poly.denote_reverse (ctx : Context) (p : Poly) : denote ctx (List.reverse p) = denote ctx p

theorem Nat.Linear.Poly.denote_eq_cancelAux (ctx : Context) (fuel : Nat) (m₁ m₂ r₁ r₂ : Poly) (h : denote_eq ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)) : denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂)

theorem Nat.Linear.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 (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)

theorem Nat.Linear.Poly.denote_eq_cancel {ctx : Context} {m₁ m₂ : Poly} (h : denote_eq ctx (m₁, m₂)) : denote_eq ctx (m₁.cancel m₂)

theorem Nat.Linear.Poly.of_denote_eq_cancel {ctx : Context} {m₁ m₂ : Poly} (h : denote_eq ctx (m₁.cancel m₂)) : denote_eq ctx (m₁, m₂)

theorem Nat.Linear.Poly.denote_eq_cancel_eq (ctx : Context) (m₁ m₂ : Poly) : denote_eq ctx (m₁.cancel m₂) = denote_eq ctx (m₁, m₂)

theorem Nat.Linear.Poly.denote_le_cancelAux (ctx : Context) (fuel : Nat) (m₁ m₂ r₁ r₂ : Poly) (h : denote_le ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)) : denote_le ctx (cancelAux fuel m₁ m₂ r₁ r₂)

theorem Nat.Linear.Poly.of_denote_le_cancelAux (ctx : Context) (fuel : Nat) (m₁ m₂ r₁ r₂ : Poly) (h : denote_le ctx (cancelAux fuel m₁ m₂ r₁ r₂)) : denote_le ctx (List.reverse r₁ ++ m₁, List.reverse r₂ ++ m₂)

theorem Nat.Linear.Poly.denote_le_cancel {ctx : Context} {m₁ m₂ : Poly} (h : denote_le ctx (m₁, m₂)) : denote_le ctx (m₁.cancel m₂)

theorem Nat.Linear.Poly.of_denote_le_cancel {ctx : Context} {m₁ m₂ : Poly} (h : denote_le ctx (m₁.cancel m₂)) : denote_le ctx (m₁, m₂)

theorem Nat.Linear.Poly.denote_le_cancel_eq (ctx : Context) (m₁ m₂ : Poly) : denote_le ctx (m₁.cancel m₂) = denote_le ctx (m₁, m₂)

theorem Nat.Linear.Expr.denote_toPoly_go {k : Nat} {p : Poly} (ctx : Context) (e : Expr) : Poly.denote ctx (toPoly.go k e p) = k * denote ctx e + Poly.denote ctx p

theorem Nat.Linear.Expr.denote_toPoly (ctx : Context) (e : Expr) : Poly.denote ctx e.toPoly = denote ctx e

theorem Nat.Linear.Expr.eq_of_toNormPoly (ctx : Context) (a b : Expr) (h : a.toNormPoly = b.toNormPoly) : denote ctx a = denote ctx b

theorem Nat.Linear.Expr.of_cancel_eq (ctx : Context) (a b c d : Expr) (h : a.toNormPoly.cancel b.toNormPoly = (c.toPoly, d.toPoly)) : (denote ctx a = denote ctx b) = (denote ctx c = denote ctx d)

theorem Nat.Linear.Expr.of_cancel_le (ctx : Context) (a b c d : Expr) (h : a.toNormPoly.cancel b.toNormPoly = (c.toPoly, d.toPoly)) : (denote ctx a ≤ denote ctx b) = (denote ctx c ≤ denote ctx d)

theorem Nat.Linear.Expr.of_cancel_lt (ctx : Context) (a b c d : Expr) (h : a.inc.toNormPoly.cancel b.toNormPoly = (c.inc.toPoly, d.toPoly)) : (denote ctx a < denote ctx b) = (denote ctx c < denote ctx d)

theorem Nat.Linear.ExprCnstr.toPoly_norm_eq (c : ExprCnstr) : c.toPoly.norm = c.toNormPoly

theorem Nat.Linear.ExprCnstr.denote_toPoly (ctx : Context) (c : ExprCnstr) : PolyCnstr.denote ctx c.toPoly = denote ctx c

theorem Nat.Linear.ExprCnstr.denote_toNormPoly (ctx : Context) (c : ExprCnstr) : PolyCnstr.denote ctx c.toNormPoly = denote ctx c

theorem Nat.Linear.Poly.of_isZero (ctx : Context) {p : Poly} (h : p.isZero = true) : denote ctx p = 0

theorem Nat.Linear.Poly.of_isNonZero (ctx : Context) {p : Poly} (h : p.isNonZero = true) : denote ctx p > 0

theorem Nat.Linear.PolyCnstr.eq_false_of_isUnsat (ctx : Context) {c : PolyCnstr} : c.isUnsat = true → denote ctx c = False

theorem Nat.Linear.PolyCnstr.eq_true_of_isValid (ctx : Context) {c : PolyCnstr} : c.isValid = true → denote ctx c = True

theorem Nat.Linear.ExprCnstr.eq_false_of_isUnsat (ctx : Context) (c : ExprCnstr) (h : c.toNormPoly.isUnsat = true) : denote ctx c = False

theorem Nat.Linear.ExprCnstr.eq_true_of_isValid (ctx : Context) (c : ExprCnstr) (h : c.toNormPoly.isValid = true) : denote ctx c = True

theorem Nat.Linear.ExprCnstr.eq_of_toNormPoly_eq (ctx : Context) (c d : ExprCnstr) (h : (c.toNormPoly == d.toPoly) = true) : denote ctx c = denote ctx d

theorem Nat.Linear.Expr.eq_of_toNormPoly_eq (ctx : Context) (e e' : Expr) (h : (e.toNormPoly == e'.toPoly) = true) : denote ctx e = denote ctx e'

def Nat.elimOffset {α : Sort u} (a b k : Nat) (h₁ : a + k = b + k) (h₂ : a = b → α) : α