409 lines
18 KiB
Lean4
409 lines
18 KiB
Lean4
/-
|
||
Released under Apache 2.0 license as described in the file LICENSE.
|
||
-/
|
||
import FormalConflictRange.Empty
|
||
|
||
/-!
|
||
# Realizing prescribed interval counts by a database
|
||
|
||
This file is the database side of the count-to-`FlipWitness` bridge. A finite
|
||
set of endpoints partitions the key space into consecutive half-open intervals.
|
||
If every interval is asked to contain at most as many keys as its cardinality
|
||
allows, the interval-insertion construction of `Basic.lean` realizes all the
|
||
prescribed counts in one database.
|
||
|
||
The main theorem, `exists_db_realizing_counts`, starts at the empty key `⊥` and
|
||
builds the database left to right. The last interval is unbounded above, so no
|
||
finiteness hypothesis is needed for it. This is exactly the shape consumed by a
|
||
characterizing DNF: its endpoints always include `⊥`, and the count at `⊥` is
|
||
zero.
|
||
|
||
The proof is constructive (modulo the classical choice inherent in the existing
|
||
`DB.insertInterval` construction) and uses only the successor chain inside each
|
||
interval, so it does not enumerate databases.
|
||
-/
|
||
|
||
namespace FormalConflictRange
|
||
|
||
namespace DB
|
||
|
||
/-- Append a successor chain above `a` to a database whose keys all lie strictly
|
||
below `a`. This realizes the final unbounded interval `[a, ⊤)`. -/
|
||
def appendAbove (db : DB) (a : Key) (n : ℕ)
|
||
(h : ∀ k ∈ db.keys, k < a) : DB where
|
||
keys := db.keys ++ List.map (chain a) (List.range n)
|
||
sorted := by
|
||
rw [List.sortedLT_append]
|
||
refine ⟨db.sorted, sortedLT_map_chain a n, ?_⟩
|
||
intro x hx y hy
|
||
rw [List.mem_map] at hy
|
||
obtain ⟨i, -, rfl⟩ := hy
|
||
exact lt_of_lt_of_le (h x hx) (chain_le a i)
|
||
|
||
@[simp] theorem appendAbove_keys (db : DB) (a : Key) (n : ℕ)
|
||
(h : ∀ k ∈ db.keys, k < a) :
|
||
(db.appendAbove a n h).keys = db.keys ++ List.map (chain a) (List.range n) := rfl
|
||
|
||
/-- Appending an unbounded chain does not change any count at or below its
|
||
base. -/
|
||
theorem cnt_appendAbove_of_le (db : DB) (a : Key) (n : ℕ)
|
||
(h : ∀ k ∈ db.keys, k < a) {w : WithTop Key} (hw : w ≤ (a : WithTop Key)) :
|
||
cnt (db.appendAbove a n h) w = cnt db w := by
|
||
unfold cnt
|
||
rw [appendAbove_keys, List.countP_append]
|
||
have hzero : (List.map (chain a) (List.range n)).countP
|
||
(fun (k : Key) => decide ((k : WithTop Key) < w)) = 0 := by
|
||
rw [List.countP_eq_zero]
|
||
intro x hx
|
||
rw [List.mem_map] at hx
|
||
obtain ⟨i, -, rfl⟩ := hx
|
||
simpa using not_lt.mpr (le_trans hw (WithTop.coe_le_coe.mpr (chain_le a i)))
|
||
rw [hzero, Nat.add_zero]
|
||
|
||
/-- Appending an unbounded chain leaves every key below `a` untouched. -/
|
||
theorem cnt_appendAbove_self (db : DB) (a : Key) (n : ℕ)
|
||
(h : ∀ k ∈ db.keys, k < a) :
|
||
cnt (db.appendAbove a n h) (a : WithTop Key) = cnt db (a : WithTop Key) :=
|
||
cnt_appendAbove_of_le db a n h le_rfl
|
||
|
||
/-- Appending an unbounded chain of `n` keys makes the total count exactly the
|
||
old length plus `n`. -/
|
||
theorem cnt_top_appendAbove (db : DB) (a : Key) (n : ℕ)
|
||
(h : ∀ k ∈ db.keys, k < a) :
|
||
cnt (db.appendAbove a n h) ⊤ = db.keys.length + n := by
|
||
unfold cnt
|
||
rw [appendAbove_keys, List.countP_append, countP_lt_top, countP_lt_top,
|
||
List.length_map, List.length_range]
|
||
|
||
/-- When all keys are already below the interval's lower endpoint, interval
|
||
insertion keeps them all and appends exactly the successor chain. -/
|
||
theorem insertInterval_keys_eq_of_below (db : DB) {a b : Key} (hab : a ≤ b) (n : ℕ)
|
||
(hn : ∀ i < n, chain a i < b) (hbelow : ∀ k ∈ db.keys, k < a) :
|
||
(db.insertInterval a b hab n hn).keys = db.keys ++ List.map (chain a) (List.range n) := by
|
||
rw [DB.insertInterval_keys]
|
||
have hP : db.keys.filter (fun x => decide (x < a)) = db.keys :=
|
||
List.filter_eq_self.mpr fun x hx => by simpa using hbelow x hx
|
||
have hQ : db.keys.filter (fun x => decide (b ≤ x)) = [] :=
|
||
List.filter_eq_nil_iff.mpr fun x hx hcon => by
|
||
have hxb : b ≤ x := of_decide_eq_true hcon
|
||
exact absurd (hbelow x hx) (not_lt.mpr (le_trans hab hxb))
|
||
rw [hP, hQ, List.append_nil]
|
||
|
||
/-- The length after interval insertion is the old length plus the chain
|
||
length, when all old keys are below the interval. -/
|
||
theorem insertInterval_length_of_below (db : DB) {a b : Key} (hab : a ≤ b) (n : ℕ)
|
||
(hn : ∀ i < n, chain a i < b) (hbelow : ∀ k ∈ db.keys, k < a) :
|
||
(db.insertInterval a b hab n hn).keys.length = db.keys.length + n := by
|
||
rw [insertInterval_keys_eq_of_below db hab n hn hbelow, List.length_append,
|
||
List.length_map, List.length_range]
|
||
|
||
/-- After interval insertion, every key is below the upper endpoint. -/
|
||
theorem insertInterval_keys_lt_of_below (db : DB) {a b : Key} (hab : a ≤ b) (n : ℕ)
|
||
(hn : ∀ i < n, chain a i < b) (hbelow : ∀ k ∈ db.keys, k < a) :
|
||
∀ k ∈ (db.insertInterval a b hab n hn).keys, k < b := by
|
||
intro k hk
|
||
rw [insertInterval_keys_eq_of_below db hab n hn hbelow, List.mem_append] at hk
|
||
rcases hk with hk | hk
|
||
· exact lt_of_lt_of_le (hbelow k hk) hab
|
||
· rw [List.mem_map] at hk
|
||
obtain ⟨i, hi, rfl⟩ := hk
|
||
exact hn i (List.mem_range.mp hi)
|
||
|
||
/-- Interval insertion does not change a count at or below the lower
|
||
endpoint. -/
|
||
theorem cnt_insertInterval_of_le (db : DB) {a b : Key} (hab : a ≤ b) (n : ℕ)
|
||
(hn : ∀ i < n, chain a i < b) {w : Key} (hw : w ≤ a) :
|
||
cnt (db.insertInterval a b hab n hn) (w : WithTop Key) = cnt db (w : WithTop Key) := by
|
||
rw [cnt_coe, cnt_coe]
|
||
exact countP_lt_insertInterval_of_lt hab hw n hn
|
||
|
||
/-- Interval insertion raises the count at the upper endpoint by exactly the
|
||
number of old keys below the lower endpoint plus the chain length. -/
|
||
theorem cnt_insertInterval_self (db : DB) {a b : Key} (hab : a ≤ b) (n : ℕ)
|
||
(hn : ∀ i < n, chain a i < b) (hbelow : ∀ k ∈ db.keys, k < a) :
|
||
cnt (db.insertInterval a b hab n hn) (b : WithTop Key) = db.keys.length + n := by
|
||
rw [cnt_coe]
|
||
rw [countP_lt_insertInterval_self hab hn]
|
||
have hP : db.keys.filter (fun x => decide (x < a)) = db.keys :=
|
||
List.filter_eq_self.mpr fun x hx => by simpa using hbelow x hx
|
||
rw [hP]
|
||
|
||
end DB
|
||
|
||
/-! ## Count specifications for consecutive intervals -/
|
||
|
||
/-- The prescribed counts fit the capacities of the consecutive intervals
|
||
starting at `start`. The endpoints need only be nondecreasing: an empty
|
||
interval is allowed and then its capacity forces the corresponding count to be
|
||
zero. -/
|
||
def CountsFit : Key → List Key → List ℕ → Prop
|
||
| _, [], [] => True
|
||
| start, b :: bs, d :: ds =>
|
||
start ≤ b ∧ (d : ℕ∞) ≤ intervalCard (start : WithTop Key) (b : WithTop Key) ∧
|
||
CountsFit b bs ds
|
||
| _, _, _ => False
|
||
|
||
/-- The counts at a list of endpoints, relative to a base count below the first
|
||
endpoint. -/
|
||
def CountsAt (db : DB) (base : ℕ) : List Key → List ℕ → Prop
|
||
| [], [] => True
|
||
| b :: bs, d :: ds =>
|
||
cnt db (b : WithTop Key) = base + d ∧ CountsAt db (base + d) bs ds
|
||
| _, _ => False
|
||
|
||
/-- The endpoints form a nondecreasing chain starting at `start`. -/
|
||
def BoundsLe : Key → List Key → Prop
|
||
| _, [] => True
|
||
| start, b :: bs => start ≤ b ∧ BoundsLe b bs
|
||
|
||
/-- The interval counts actually realized by a database: each entry is the
|
||
number of keys in the corresponding half-open interval. -/
|
||
def intervalCounts (db : DB) : Key → List Key → List ℕ
|
||
| _, [] => []
|
||
| start, b :: bs =>
|
||
(cnt db (b : WithTop Key) - cnt db (start : WithTop Key)) :: intervalCounts db b bs
|
||
|
||
/-- The last endpoint of the chain, or the starting point for the empty
|
||
chain. -/
|
||
def lastBound (start : Key) : List Key → WithTop Key
|
||
| [] => (start : WithTop Key)
|
||
| b :: bs => lastBound b bs
|
||
|
||
/-- The realized interval counts telescope from the starting count to the count
|
||
at the last endpoint. -/
|
||
theorem intervalCounts_sum (db : DB) (start : Key) (bounds : List Key)
|
||
(hle : BoundsLe start bounds) :
|
||
cnt db (lastBound start bounds) =
|
||
cnt db (start : WithTop Key) + (intervalCounts db start bounds).sum := by
|
||
induction bounds generalizing start with
|
||
| nil => simp [lastBound, intervalCounts]
|
||
| cons b bs ih =>
|
||
rcases hle with ⟨hstartb, hleTail⟩
|
||
have hmono : cnt db (start : WithTop Key) ≤ cnt db (b : WithTop Key) :=
|
||
cnt_le_cnt_of_le db (WithTop.coe_le_coe.mpr hstartb)
|
||
have htail := ih b hleTail
|
||
simp only [intervalCounts, lastBound, List.sum_cons]
|
||
omega
|
||
|
||
/-- The realized interval counts fit their capacities. -/
|
||
theorem intervalCounts_fit (db : DB) (start : Key) (bounds : List Key)
|
||
(hle : BoundsLe start bounds) : CountsFit start bounds (intervalCounts db start bounds) := by
|
||
induction bounds generalizing start with
|
||
| nil => simp [intervalCounts, CountsFit]
|
||
| cons b bs ih =>
|
||
rcases hle with ⟨hstartb, hleTail⟩
|
||
refine ⟨hstartb, ?_, ?_⟩
|
||
· exact cnt_sub_le_intervalCard db (WithTop.coe_le_coe.mpr hstartb)
|
||
· exact ih b hleTail
|
||
|
||
/-- The realized interval counts above `⊥` sum to at most the whole database
|
||
length. -/
|
||
theorem intervalCounts_sum_le_top (db : DB) (bounds : List Key)
|
||
(hle : BoundsLe ([] : Key) bounds) :
|
||
(intervalCounts db ([] : Key) bounds).sum ≤ cnt db ⊤ := by
|
||
have h := intervalCounts_sum db ([] : Key) bounds hle
|
||
have hlast : cnt db (lastBound ([] : Key) bounds) ≤ cnt db ⊤ :=
|
||
cnt_le_cnt_of_le db le_top
|
||
rw [cnt_nil] at h
|
||
omega
|
||
|
||
/-- If the base count is the database's count at `start`, the realized interval
|
||
counts give the database's counts at every later endpoint. -/
|
||
theorem countsAt_intervalCounts (db : DB) (start : Key) (bounds : List Key)
|
||
(hle : BoundsLe start bounds) (base : ℕ) (hbase : base = cnt db (start : WithTop Key)) :
|
||
CountsAt db base bounds (intervalCounts db start bounds) := by
|
||
induction bounds generalizing start base with
|
||
| nil => simp [intervalCounts, CountsAt]
|
||
| cons b bs ih =>
|
||
rcases hle with ⟨hstartb, hleTail⟩
|
||
have hmono : cnt db (start : WithTop Key) ≤ cnt db (b : WithTop Key) :=
|
||
cnt_le_cnt_of_le db (WithTop.coe_le_coe.mpr hstartb)
|
||
refine ⟨?_, ?_⟩
|
||
· rw [hbase]
|
||
omega
|
||
· have hbase' : base + (cnt db (b : WithTop Key) - cnt db (start : WithTop Key)) =
|
||
cnt db (b : WithTop Key) := by
|
||
rw [hbase]
|
||
omega
|
||
rw [hbase']
|
||
exact ih b hleTail (cnt db (b : WithTop Key)) rfl
|
||
|
||
/-- Look up the cumulative count at a key in a list of endpoints. If the key is
|
||
not present, the sum of all counts is returned; the lemmas below only use the
|
||
lookup at present keys. -/
|
||
def countAtWith (base : ℕ) : List Key → List ℕ → Key → ℕ
|
||
| [], _, _ => base
|
||
| _ :: _, [], _ => base
|
||
| b :: bs, d :: ds, k =>
|
||
if k = b then base + d else countAtWith (base + d) bs ds k
|
||
|
||
/-- The cumulative lookup returns the database count at every endpoint in the
|
||
list. -/
|
||
theorem countAtWith_eq_of_CountsAt {db : DB} {base : ℕ} {bounds : List Key}
|
||
{counts : List ℕ} (h : CountsAt db base bounds counts) {k : Key} (hk : k ∈ bounds) :
|
||
countAtWith base bounds counts k = cnt db (k : WithTop Key) := by
|
||
induction bounds generalizing base counts with
|
||
| nil => simp at hk
|
||
| cons b bs ih =>
|
||
cases counts with
|
||
| nil => simp [CountsAt] at h
|
||
| cons d ds =>
|
||
rcases h with ⟨hb, htail⟩
|
||
by_cases hkb : k = b
|
||
· subst k
|
||
simp [countAtWith, hb]
|
||
· have hkbs : k ∈ bs := by
|
||
rcases List.mem_cons.mp hk with rfl | hkbs
|
||
· exact absurd rfl hkb
|
||
· exact hkbs
|
||
simp only [countAtWith]
|
||
rw [ite_eq_right hkb]
|
||
exact ih htail hkbs
|
||
|
||
/-- Evaluate a count environment on any endpoint. The empty key has count
|
||
zero; a genuine endpoint uses the interval lookup; and the top endpoint counts
|
||
the whole database. -/
|
||
def evalCount (bounds : List Key) (counts : List ℕ) (topCount : ℕ) :
|
||
WithTop Key → ℤ
|
||
| some k => if k = ([] : Key) then 0 else (countAtWith 0 bounds counts k : ℤ)
|
||
| none => (counts.sum + topCount : ℤ)
|
||
|
||
/-- The count environment agrees with the empty key. -/
|
||
theorem evalCount_bot {db : DB} {bounds : List Key} {counts : List ℕ}
|
||
{topCount : ℕ} :
|
||
evalCount bounds counts topCount (([] : Key) : WithTop Key) =
|
||
cnt db (([] : Key) : WithTop Key) := by
|
||
simp [evalCount, cnt_nil]
|
||
|
||
/-- The count environment agrees with the top endpoint. -/
|
||
theorem evalCount_top {db : DB} {bounds : List Key} {counts : List ℕ}
|
||
{topCount : ℕ} (htop : cnt db ⊤ = counts.sum + topCount) :
|
||
evalCount bounds counts topCount ⊤ = cnt db ⊤ := by
|
||
simp [evalCount, htop]
|
||
|
||
/-- The count environment agrees with every genuine endpoint in the list. -/
|
||
theorem evalCount_coe_of_mem {db : DB} {bounds : List Key} {counts : List ℕ}
|
||
{topCount : ℕ} (h : CountsAt db 0 bounds counts) {k : Key} (hk : k ∈ bounds)
|
||
(hkbot : k ≠ ([] : Key)) :
|
||
evalCount bounds counts topCount (k : WithTop Key) = cnt db (k : WithTop Key) := by
|
||
have hlook := countAtWith_eq_of_CountsAt h hk
|
||
simp [evalCount, hkbot, hlook]
|
||
|
||
|
||
/-- A count list that is realized at a database's endpoints fits the interval
|
||
capacities. This is the converse of `exists_db_realizing_counts`. -/
|
||
theorem countsFit_of_CountsAt {db : DB} {start : Key} {base : ℕ}
|
||
{bounds : List Key} {counts : List ℕ} (h : CountsAt db base bounds counts)
|
||
(hle : BoundsLe start bounds) (hbase : base = cnt db (start : WithTop Key)) :
|
||
CountsFit start bounds counts := by
|
||
induction bounds generalizing start base counts with
|
||
| nil =>
|
||
cases counts with
|
||
| nil => trivial
|
||
| cons d ds => simp [CountsAt] at h
|
||
| cons b bs ih =>
|
||
cases counts with
|
||
| nil => simp [CountsAt] at h
|
||
| cons d ds =>
|
||
rcases hle with ⟨hstartb, hleTail⟩
|
||
rcases h with ⟨hb, htail⟩
|
||
have hmono : cnt db (start : WithTop Key) ≤ cnt db (b : WithTop Key) :=
|
||
cnt_le_cnt_of_le db (WithTop.coe_le_coe.mpr hstartb)
|
||
refine ⟨hstartb, ?_, ?_⟩
|
||
· have hd : d = cnt db (b : WithTop Key) - cnt db (start : WithTop Key) := by
|
||
rw [hbase] at hb
|
||
omega
|
||
rw [hd]
|
||
exact cnt_sub_le_intervalCard db (WithTop.coe_le_coe.mpr hstartb)
|
||
· have hbase' : base + d = cnt db (b : WithTop Key) := by omega
|
||
rw [hbase'] at htail
|
||
exact ih htail hleTail rfl
|
||
|
||
/-- **Database realization of prescribed consecutive interval counts.** Starting
|
||
from any database whose keys all lie below `start`, one can realize any list of
|
||
counts that fits the capacities of the consecutive intervals, and then add an
|
||
arbitrary number of keys in the final unbounded interval `[last, ⊤)`. The
|
||
counts below `start` are left untouched.
|
||
|
||
This is the constructive bridge from count arithmetic to databases: it uses one
|
||
successor chain per interval, never enumerating keys. -/
|
||
theorem exists_db_extend_with_top (db : DB) (start : Key)
|
||
(hbelow : ∀ k ∈ db.keys, k < start) (bounds : List Key) (counts : List ℕ)
|
||
(topCount : ℕ) (hfits : CountsFit start bounds counts) :
|
||
∃ db' : DB,
|
||
CountsAt db' db.keys.length bounds counts ∧
|
||
cnt db' ⊤ = db.keys.length + counts.sum + topCount ∧
|
||
(∀ w : WithTop Key, w ≤ (start : WithTop Key) → cnt db' w = cnt db w) := by
|
||
induction bounds generalizing db start counts with
|
||
| nil =>
|
||
cases counts with
|
||
| nil =>
|
||
refine ⟨db.appendAbove start topCount hbelow, trivial, ?_, ?_⟩
|
||
· rw [DB.cnt_top_appendAbove]
|
||
simp
|
||
· intro w hw
|
||
exact DB.cnt_appendAbove_of_le db start topCount hbelow hw
|
||
| cons d ds => simp [CountsFit] at hfits
|
||
| cons b bs ih =>
|
||
cases counts with
|
||
| nil => simp [CountsFit] at hfits
|
||
| cons d ds =>
|
||
rcases hfits with ⟨hstartb, hcap, hfitsTail⟩
|
||
have hn : ∀ i < d, chain start i < b := by
|
||
intro i hi
|
||
exact (chain_lt_iff start b i).mpr
|
||
(lt_of_lt_of_le (by exact_mod_cast hi) hcap)
|
||
let db₁ := db.insertInterval start b hstartb d hn
|
||
have hbelow₁ : ∀ k ∈ db₁.keys, k < b :=
|
||
DB.insertInterval_keys_lt_of_below db hstartb d hn hbelow
|
||
obtain ⟨db₂, hcounts₂, htop₂, hlower₂⟩ :=
|
||
ih db₁ b hbelow₁ ds hfitsTail
|
||
refine ⟨db₂, ?_, ?_, ?_⟩
|
||
· constructor
|
||
· have hb₂ : cnt db₂ (b : WithTop Key) = cnt db₁ (b : WithTop Key) :=
|
||
hlower₂ (b : WithTop Key) le_rfl
|
||
rw [hb₂, DB.cnt_insertInterval_self db hstartb d hn hbelow]
|
||
· rw [DB.insertInterval_length_of_below db hstartb d hn hbelow] at hcounts₂
|
||
exact hcounts₂
|
||
· rw [htop₂, DB.insertInterval_length_of_below db hstartb d hn hbelow,
|
||
List.sum_cons]
|
||
omega
|
||
· intro w hw
|
||
have hwb : w ≤ (b : WithTop Key) :=
|
||
le_trans hw (WithTop.coe_le_coe.mpr hstartb)
|
||
rw [hlower₂ w hwb]
|
||
cases w with
|
||
| top => exact (WithTop.not_top_le_coe start hw).elim
|
||
| coe x =>
|
||
exact DB.cnt_insertInterval_of_le db hstartb d hn
|
||
(WithTop.coe_le_coe.mp hw)
|
||
|
||
/-- **Database realization from the empty key.** Any list of consecutive
|
||
counts that fits the capacities is realized by a database, with zero keys below
|
||
`⊥`, the prescribed cumulative counts at the finite endpoints, and an arbitrary
|
||
number of further keys above the last endpoint. -/
|
||
theorem exists_db_realizing_counts (bounds : List Key) (counts : List ℕ)
|
||
(topCount : ℕ) (hfits : CountsFit ([] : Key) bounds counts) :
|
||
∃ db : DB,
|
||
CountsAt db 0 bounds counts ∧ cnt db ⊤ = counts.sum + topCount := by
|
||
let empty : DB := ⟨[], List.sortedLT_nil⟩
|
||
obtain ⟨db, hcounts, htop, -⟩ :=
|
||
exists_db_extend_with_top empty ([] : Key) (by intro k hk; simp [empty] at hk)
|
||
bounds counts topCount hfits
|
||
refine ⟨db, ?_, ?_⟩
|
||
· simpa [empty] using hcounts
|
||
· simpa [empty] using htop
|
||
|
||
/-- **Realizability of a count list is exactly its capacity fit.** -/
|
||
theorem exists_db_counts_iff (bounds : List Key) (counts : List ℕ) (topCount : ℕ)
|
||
(hle : BoundsLe ([] : Key) bounds) :
|
||
(∃ db : DB, CountsAt db 0 bounds counts ∧ cnt db ⊤ = counts.sum + topCount) ↔
|
||
CountsFit ([] : Key) bounds counts := by
|
||
constructor
|
||
· rintro ⟨db, hcounts, -⟩
|
||
exact countsFit_of_CountsAt hcounts hle (by simp [cnt_nil])
|
||
· intro hfit
|
||
exact exists_db_realizing_counts bounds counts topCount hfit
|
||
|
||
end FormalConflictRange
|