blob: 6d8f91a9e08c519f6006998ad6336aec45964f74 [file]
/-
Copyright (c) 2025 Amazon.com, Inc. or its affiliates. All Rights Reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/
module
prelude
import Init.LawfulBEqTactics
public import Init.Data.Int.DivMod.Basic
public meta import Init.Grind.Tactics
import Init.ByCases
import Init.Data.Int.DivMod.Lemmas
import Init.Omega
public section
/-!
# Typeclasses for types that can be embedded into an interval of `Int`.
The typeclass `ToInt α lo? hi?` carries the data of a function `ToInt.toInt : α → Int`
which is injective, lands between the (optional) lower and upper bounds `lo?` and `hi?`.
The function `ToInt.wrap` is the identity if either bound is `none`,
and otherwise wraps the integers into the interval `[lo, hi)`.
The typeclass `ToInt.Add α lo? hi?` then asserts that `toInt (x + y) = wrap lo? hi? (toInt x + toInt y)`.
There are many variants for other operations.
These typeclasses are used solely in the `grind` tactic to lift linear inequalities into `Int`.
-/
namespace Lean.Grind
/-- An interval in the integers (either finite, half-infinite, or infinite). -/
inductive IntInterval : Type where
| /-- The finite interval `[lo, hi)`. -/
co (lo hi : Int)
| /-- The half-infinite interval `[lo, ∞)`. -/
ci (lo : Int)
| /-- The half-infinite interval `(-∞, hi)`. -/
io (hi : Int)
| /-- The infinite interval `(-∞, ∞)`. -/
ii
deriving BEq, ReflBEq, LawfulBEq, DecidableEq, Inhabited
namespace IntInterval
/-- The interval `[0, 2^n)`. -/
@[expose] abbrev uint (n : Nat) := IntInterval.co 0 (2 ^ n)
/-- The interval `[-2^(n-1), 2^(n-1))`. -/
@[expose] abbrev sint (n : Nat) := IntInterval.co (-(2 ^ (n - 1))) (2 ^ (n - 1))
/-- The lower bound of the interval, if finite. -/
@[expose] def lo? (i : IntInterval) : Option Int :=
match i with
| co lo _ => some lo
| ci lo => some lo
| io _ => none
| ii => none
/-- The upper bound of the interval, if finite. -/
@[expose] def hi? (i : IntInterval) : Option Int :=
match i with
| co _ hi => some hi
| ci _ => none
| io hi => some hi
| ii => none
@[simp, expose] def nonEmpty (i : IntInterval) : Bool :=
match i with
| co lo hi => lo < hi
| ci _ => true
| io _ => true
| ii => true
@[simp, expose] def isFinite (i : IntInterval) : Bool :=
match i with
| co _ _ => true
| ci _
| io _
| ii => false
def mem (i : IntInterval) (x : Int) : Prop :=
match i with
| co lo hi => lo ≤ x ∧ x < hi
| ci lo => lo ≤ x
| io hi => x < hi
| ii => True
instance : Membership Int IntInterval where
mem := mem
@[simp] theorem mem_co (lo hi : Int) (x : Int) : x ∈ IntInterval.co lo hi ↔ lo ≤ x ∧ x < hi := by rfl
@[simp] theorem mem_ci (lo : Int) (x : Int) : x ∈ IntInterval.ci lo ↔ lo ≤ x := by rfl
@[simp] theorem mem_io (hi : Int) (x : Int) : x ∈ IntInterval.io hi ↔ x < hi := by rfl
@[simp] theorem mem_ii (x : Int) : x ∈ IntInterval.ii ↔ True := by rfl
theorem nonEmpty_of_mem {x : Int} {i : IntInterval} (h : x ∈ i) : i.nonEmpty := by
cases i <;> simp_all <;> omega
@[simp, expose]
def wrap (i : IntInterval) (x : Int) : Int :=
match i with
| co lo hi => (x - lo) % (hi - lo) + lo
| ci lo => max x lo
| io hi => min x (hi - 1)
| ii => x
theorem wrap_wrap (i : IntInterval) (x : Int) :
wrap i (wrap i x) = wrap i x := by
cases i <;> simp [wrap] <;> omega
theorem wrap_mem (i : IntInterval) (h : i.nonEmpty) (x : Int) :
i.wrap x ∈ i := by
match i with
| co lo hi =>
simp [wrap]
simp at h
constructor
· apply Int.le_add_of_nonneg_left
apply Int.emod_nonneg
omega
· have := Int.emod_lt (x - lo) (b := hi - lo) (by omega)
omega
| ci lo =>
simp [wrap]
omega
| io hi =>
simp [wrap]
omega
| ii =>
simp [wrap]
theorem wrap_eq_self_iff (i : IntInterval) (h : i.nonEmpty) (x : Int) :
i.wrap x = x ↔ x ∈ i := by
match i with
| co lo hi =>
simp [wrap]
simp at h
constructor
· have := Int.emod_lt (x - lo) (b := hi - lo) (by omega)
have := Int.emod_nonneg (x - lo) (b := hi - lo) (by omega)
omega
· intro w
rw [Int.emod_eq_of_lt] <;> omega
| ci lo =>
simp [wrap]
omega
| io hi =>
simp [wrap]
omega
| ii =>
simp [wrap]
theorem wrap_add {i : IntInterval} (h : i.isFinite) (x y : Int) :
i.wrap (x + y) = i.wrap (i.wrap x + i.wrap y) := by
match i with
| co lo hi =>
simp [wrap]
rw [Int.emod_eq_emod_iff_emod_sub_eq_zero, Int.emod_def (x - lo), Int.emod_def (y - lo)]
have : (x + y - lo - (x - lo - (hi - lo) * ((x - lo) / (hi - lo)) + lo + (y - lo - (hi - lo) * ((y - lo) / (hi - lo)) + lo) - lo)) =
(hi - lo) * ((x - lo) / (hi - lo) + (y - lo) / (hi - lo)) := by
simp only [Int.mul_add]
omega
rw [this]
exact Int.mul_emod_right ..
theorem wrap_mul {i : IntInterval} (h : i.isFinite) (x y : Int) :
i.wrap (x * y) = i.wrap (i.wrap x * i.wrap y) := by
match i with
| co lo hi =>
dsimp [wrap]
rw [Int.add_left_inj, Int.emod_eq_emod_iff_emod_sub_eq_zero, Int.emod_def (x - lo), Int.emod_def (y - lo)]
have : x - lo - (hi - lo) * ((x - lo) / (hi - lo)) + lo = x - (hi - lo) * ((x - lo) / (hi - lo)) := by omega
rw [this]; clear this
have : y - lo - (hi - lo) * ((y - lo) / (hi - lo)) + lo = y - (hi - lo) * ((y - lo) / (hi - lo)) := by omega
rw [this]; clear this
have : x * y - lo - ((x - (hi - lo) * ((x - lo) / (hi - lo))) * (y - (hi - lo) * ((y - lo) / (hi - lo))) - lo) =
x * y - (x - (hi - lo) * ((x - lo) / (hi - lo))) * (y - (hi - lo) * ((y - lo) / (hi - lo))) := by omega
rw [this]; clear this
have : (x - (hi - lo) * ((x - lo) / (hi - lo))) * (y - (hi - lo) * ((y - lo) / (hi - lo))) =
x * y - (hi - lo) * (x * ((y - lo) / (hi - lo)) + (x - lo) / (hi - lo) * (y - (hi - lo) * ((y - lo) / (hi - lo)))) := by
conv => lhs; rw [Int.sub_mul, Int.mul_sub, Int.mul_left_comm, Int.sub_sub, Int.mul_assoc, ← Int.mul_add]
rw [this]; clear this
rw [Int.sub_sub_self]
apply Int.mul_emod_right
theorem wrap_eq_bmod {i : Int} (h : 0 ≤ i) :
(IntInterval.co (-i) i).wrap x = x.bmod ((2 * i).toNat) := by
dsimp only [wrap]
match i, h with
| (i : Nat), _ =>
have : (2 * (i : Int)).toNat = 2 * i := by omega
rw [this]
simp [Int.bmod_eq_emod, ← Int.two_mul]
have : (2 * (i : Int) + 1) / 2 = i := by omega
rw [this]
by_cases h : i = 0
· simp [h]
split
· rw [← Int.sub_eq_add_neg, Int.sub_eq_iff_eq_add, Nat.two_mul, Int.natCast_add,
← Int.sub_sub, Int.sub_add_cancel]
rw [Int.emod_eq_iff (by omega)]
refine ⟨?_, ?_, ?_⟩
· omega
· have := Int.emod_lt x (b := 2 * (i : Int)) (by omega)
omega
· rw [Int.emod_def]
have : x - 2 * ↑i * (x / (2 * ↑i)) - ↑i - (x + ↑i) = (2 * (i : Int)) * (- (x / (2 * i)) - 1) := by
simp only [Int.mul_sub, Int.mul_neg]
omega
rw [this]
exact Int.dvd_mul_right ..
· rw [← Int.sub_eq_add_neg, Int.sub_eq_iff_eq_add, Int.natCast_zero, Int.sub_zero]
rw [Int.emod_eq_iff (by omega)]
refine ⟨?_, ?_, ?_⟩
· have := Int.emod_nonneg x (b := 2 * (i : Int)) (by omega)
omega
· omega
· rw [Int.emod_def]
have : x - 2 * ↑i * (x / (2 * ↑i)) + ↑i - (x + ↑i) = (2 * (i : Int)) * (- (x / (2 * i))) := by
simp only [Int.mul_neg]
omega
rw [this]
exact Int.dvd_mul_right ..
theorem wrap_eq_wrap_iff :
(IntInterval.co lo hi).wrap x = (IntInterval.co lo hi).wrap y ↔ (x - y) % (hi - lo) = 0 := by
simp only [wrap]
rw [Int.add_left_inj]
rw [Int.emod_eq_emod_iff_emod_sub_eq_zero]
have : x - lo - (y - lo) = x - y := by omega
rw [this]
end IntInterval
/--
`ToInt α I` asserts that `α` can be embedded faithfully into an interval `I` in the integers.
-/
class ToInt (α : Type u) (range : outParam IntInterval) where
/-- The embedding function. -/
toInt : α → Int
/-- The embedding function is injective. -/
toInt_inj : ∀ x y, toInt x = toInt y → x = y
/-- The embedding function lands in the interval. -/
toInt_mem : ∀ x, toInt x ∈ range
/--
The embedding into the integers takes `0` to `0`.
-/
class ToInt.Zero (α : Type u) [Zero α] (I : outParam IntInterval) [ToInt α I] where
/-- The embedding takes `0` to `0`. -/
toInt_zero : toInt (0 : α) = 0
/--
The embedding into the integers takes numerals in the range interval to themselves.
-/
class ToInt.OfNat (α : Type u) [∀ n, OfNat α n] (I : outParam IntInterval) [ToInt α I] where
/-- The embedding takes `OfNat` to `OfNat`. -/
toInt_ofNat : ∀ n : Nat, toInt (OfNat.ofNat n : α) = I.wrap n
/--
The embedding into the integers takes addition to addition, wrapped into the range interval.
-/
class ToInt.Add (α : Type u) [Add α] (I : outParam IntInterval) [ToInt α I] where
/-- The embedding takes addition to addition, wrapped into the range interval. -/
toInt_add : ∀ x y : α, toInt (x + y) = I.wrap (toInt x + toInt y)
/--
The embedding into the integers takes negation to negation, wrapped into the range interval.
-/
class ToInt.Neg (α : Type u) [Neg α] (I : outParam IntInterval) [ToInt α I] where
/-- The embedding takes negation to negation, wrapped into the range interval. -/
toInt_neg : ∀ x : α, toInt (-x) = I.wrap (-toInt x)
/--
The embedding into the integers takes subtraction to subtraction, wrapped into the range interval.
-/
class ToInt.Sub (α : Type u) [Sub α] (I : outParam IntInterval) [ToInt α I] where
/-- The embedding takes subtraction to subtraction, wrapped into the range interval. -/
toInt_sub : ∀ x y : α, toInt (x - y) = I.wrap (toInt x - toInt y)
/--
The embedding into the integers takes multiplication to multiplication, wrapped into the range interval.
-/
class ToInt.Mul (α : Type u) [Mul α] (I : outParam IntInterval) [ToInt α I] where
/-- The embedding takes multiplication to multiplication, wrapped into the range interval. -/
toInt_mul : ∀ x y : α, toInt (x * y) = I.wrap (toInt x * toInt y)
/--
The embedding into the integers takes exponentiation to exponentiation, wrapped into the range interval.
-/
class ToInt.Pow (α : Type u) [HPow α Nat α] (I : outParam IntInterval) [ToInt α I] where
/-- The embedding takes exponentiation to exponentiation, wrapped into the range interval. -/
toInt_pow : ∀ x : α, ∀ n : Nat, toInt (x ^ n) = I.wrap (toInt x ^ n)
/--
The embedding into the integers takes modulo to modulo (without needing to wrap into the range interval).
-/
class ToInt.Mod (α : Type u) [Mod α] (I : outParam IntInterval) [ToInt α I] where
/--
The embedding takes modulo to modulo (without needing to wrap into the range interval).
One might expect a `wrap` on the right hand side,
but in practice this stronger statement is usually true.
-/
toInt_mod : ∀ x y : α, toInt (x % y) = toInt x % toInt y
/--
The embedding into the integers takes division to division, wrapped into the range interval.
-/
class ToInt.Div (α : Type u) [Div α] (I : outParam IntInterval) [ToInt α I] where
/--
The embedding takes division to division (without needing to wrap into the range interval).
One might expect a `wrap` on the right hand side,
but in practice this stronger statement is usually true.
-/
toInt_div : ∀ x y : α, toInt (x / y) = toInt x / toInt y
/--
The embedding into the integers is monotone.
-/
class ToInt.LE (α : Type u) [LE α] (I : outParam IntInterval) [ToInt α I] where
/-- The embedding is monotone with respect to `≤`. -/
le_iff : ∀ x y : α, x ≤ y ↔ toInt x ≤ toInt y
/--
The embedding into the integers is strictly monotone.
-/
class ToInt.LT (α : Type u) [LT α] (I : outParam IntInterval) [ToInt α I] where
/-- The embedding is strictly monotone with respect to `<`. -/
lt_iff : ∀ x y : α, x < y ↔ toInt x < toInt y
open IntInterval
namespace ToInt
/-! ## Helper theorems -/
theorem Zero.wrap_zero (I : IntInterval) [_root_.Zero α] [ToInt α I] [ToInt.Zero α I] :
I.wrap 0 = 0 := by
have := toInt_mem (0 : α)
rw [I.wrap_eq_self_iff (I.nonEmpty_of_mem this)]
rwa [ToInt.Zero.toInt_zero] at this
@[simp]
theorem wrap_toInt (I : IntInterval) [ToInt α I] (x : α) :
I.wrap (toInt x) = toInt x := by
rw [I.wrap_eq_self_iff (I.nonEmpty_of_mem (toInt_mem x))]
exact ToInt.toInt_mem x
/-- Construct a `ToInt.Sub` instance from a `ToInt.Add` and `ToInt.Neg` instance and
a `sub_eq_add_neg` assumption. -/
def Sub.of_sub_eq_add_neg {α : Type u} [_root_.Add α] [_root_.Neg α] [_root_.Sub α]
(sub_eq_add_neg : ∀ x y : α, x - y = x + -y)
{I : IntInterval} (h : I.isFinite) [ToInt α I] [Add α I] [Neg α I] : ToInt.Sub α I where
toInt_sub x y := by
rw [sub_eq_add_neg, ToInt.Add.toInt_add, ToInt.Neg.toInt_neg, Int.sub_eq_add_neg]
conv => rhs; rw [wrap_add h, ToInt.wrap_toInt]
end ToInt
/-
Remark: `↑a` is notation for `ToInt.toInt a`.
We want to hide `Lean.Grind.ToInt.toInt` applications in the counterexamples produced by
the `cutsat` procedure in `grind`.
-/
@[app_unexpander ToInt.toInt]
meta def toIntUnexpander : PrettyPrinter.Unexpander := fun stx => do
match stx with
| `($_ $a:term) => `(↑$a)
| _ => throw ()
end Lean.Grind