/- Released under Apache 2.0 license as described in the file LICENSE. -/ import FormalConflictRange.NegCrossTruncNonposGapA2aBottom /-! # The cross-free nonpositive-end gap cell The crossed nonpositive-end gap cell was closed in `NegCrossTruncNonposGapA2a*`. The remaining subcell, where `begin.key ≤ end_.key`, has the same candidate closed form `closedFormNegCrossTruncNonposGap`: `[⊥, end_.key)` when the begin selector can clamp and `[head, end_.key)` otherwise. This module records the structural facts that distinguish it from the crossed cell. * Soundness of both branches is already available from the crossed module: `sound_bottomLong_of_nonpos` fixes `[⊥, max begin.key end.key) = [⊥, end_.key)`, and `sound_headLong_of_nonbottom` fixes `[head, max begin.key end.key) = [head, end_.key)` in the non-clamping branch. Neither proof uses crossing. * The non-clamping branch really is nonempty on the cross-free cell, so the `[head, end_.key)` branch cannot be discarded as vacuous. * Crucially, `[head, end_.key)` is **not** sound outside the non-clamping branch: a compatible database can have a negative begin anchor even when `clampNonposBottom` holds, because a truncated result (`more = true`) may still report the entire complete window. The E2 witness below is kernel-checked. This invalidates the earlier guess that the cross-free cell is always `[⊥, end_.key)`; the `clampNonposBottom` split is essential. -/ namespace FormalConflictRange /-- The cross-free part of the crossed negative-begin truncated nonpositive-end gap cell. -/ def negCrossTruncNonposGapCrossFree (r : RangeRead) (res : Result) : Prop := negCrossTruncNonposGap r res ∧ r.begin.key ≤ r.end_.key /-- The cross-free gap closed form is the same three-branch rule as the crossed one; on cross-free reads `max begin.key end.key = end_.key`. -/ noncomputable def closedFormNegCrossTruncNonposGapCrossFree (r : RangeRead) (res : Result) : ConflictRange := closedFormNegCrossTruncNonposGap r res /-- **Soundness of `[⊥, end_.key)` on the cross-free gap cell.** -/ theorem sound_bottomEnd_crossFree {r : RangeRead} {res : Result} (hbegin : r.begin.offset < 0) (hend : r.end_.offset ≤ 0) (hB_le_E : r.begin.key ≤ r.end_.key) : Sound r res (⟨(([] : Key) : WithTop Key), r.end_.key⟩ : ConflictRange) := by have hs := sound_bottomLong_of_nonpos (r := r) (res := res) (le_of_lt hbegin) hend rwa [max_eq_right hB_le_E] at hs /-- **Soundness of `[head, end_.key)` in the non-clamping branch.** -/ theorem sound_headEnd_crossFree {r : RangeRead} {res : Result} (hrev : r.reverse = false) (hmore : res.more = true) (hne : res.keys ≠ []) (hbegin : r.begin.offset < 0) (hcross : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key) (hclamp : reportedBelowBegin r res ≤ beginSlack r) (hnbot : ¬ clampNonposBottom r res) (hend : r.end_.offset ≤ 0) (hB_le_E : r.begin.key ≤ r.end_.key) : Sound r res (⟨((res.keys.head hne : Key) : WithTop Key), r.end_.key⟩ : ConflictRange) := by have hs := sound_headLong_of_nonbottom hrev hmore hne hbegin hcross hclamp hnbot hend rwa [max_eq_right hB_le_E] at hs /-! ## The E2 witness: `[head, end_.key)` is not sound on the clamping branch Read `begin = ⟨[5], -2⟩`, `end = ⟨[5,0,0], -2⟩`, reporting a single key `[0]` with `more = true`. The database `[[0],[1],[5],[5,0]]` is compatible with a negative begin anchor (it reports the full window), while inserting the empty key makes it incompatible. The two databases agree on `[[0], [5,0,0))`, so `[head, end_.key)` is unsound there. This is exactly why the clamping branch must keep the lower endpoint at `⊥`. -/ /-- The empty key. -/ def xgNil : Key := [] /-- The key `[0]`. -/ def xgZero : Key := [(0 : Fin 256)] /-- The key `[1]`. -/ def xgOne : Key := [(1 : Fin 256)] /-- The key `[5]`, the begin selector key. -/ def xgFive : Key := [(5 : Fin 256)] /-- The key `[5,0]`. -/ def xgFiveZero : Key := [(5 : Fin 256), (0 : Fin 256)] /-- The key `[5,0,0]`, the end selector key. -/ def xgFiveZeroZero : Key := [(5 : Fin 256), (0 : Fin 256), (0 : Fin 256)] /-- The E2 read. -/ def xgRead : RangeRead := { begin := ⟨(xgFive : Key), -2⟩, end_ := ⟨(xgFiveZeroZero : Key), -2⟩, limit := none, reverse := false } /-- The E2 result: one reported key, truncated. -/ def xgRes : Result := { keys := [xgZero], more := true } /-- Bottom-anchored E2 database, reporting the whole window. -/ def xgDB3 : DB := ⟨[xgZero, xgOne, xgFive, xgFiveZero], by decide⟩ /-- The E2 database with the empty key inserted; incompatible. -/ def xgDB4 : DB := ⟨[xgNil, xgZero, xgOne, xgFive, xgFiveZero], by decide⟩ /-- The range `[[0], [5,0,0))`. -/ def xgHeadRange : ConflictRange := ⟨(xgZero : Key), (xgFiveZeroZero : Key)⟩ /-- The range `[⊥, [5,0,0))`. -/ def xgBottomRange : ConflictRange := ⟨(([] : Key) : WithTop Key), (xgFiveZeroZero : Key)⟩ theorem xg_compatible : RangeRead.Compatible xgDB3 xgRead xgRes := by unfold RangeRead.Compatible RangeRead.withinLimit refine ⟨trivial, Or.inl ⟨rfl, ?_, by decide⟩⟩ decide theorem xg_incompatible : ¬ RangeRead.Compatible xgDB4 xgRead xgRes := by unfold RangeRead.Compatible RangeRead.withinLimit rintro ⟨-, h | h⟩ · obtain ⟨-, hpre, -⟩ := h revert hpre decide · obtain ⟨hm, -⟩ := h revert hm decide theorem xg_agree : AgreeOn xgHeadRange xgDB3 xgDB4 := by unfold AgreeOn ConflictRange.keys xgHeadRange decide /-- **`[head, end_.key)` is not sound on the E2 cell.** -/ theorem xg_headRange_not_sound : ¬ Sound xgRead xgRes xgHeadRange := by intro hs have h := (hs xgDB3 xgDB4 xg_agree).mp xg_compatible exact xg_incompatible h /-- The E2 pair lies in the cross-free nonpositive-end gap cell. -/ theorem xg_cell : negCrossTruncNonposGapCrossFree xgRead xgRes := by refine ⟨?_, by decide⟩ unfold negCrossTruncNonposGap refine ⟨rfl, rfl, by decide, by decide, by decide, by decide, by decide, by decide, by decide, by decide, ?_⟩ right decide /-- The begin selector clamps in the E2 cell. -/ theorem xg_clamp : clampNonposBottom xgRead xgRes := by decide /-- `[⊥, end_.key)` is sound on the E2 cell. -/ theorem xg_bottomRange_sound : Sound xgRead xgRes xgBottomRange := by unfold xgBottomRange exact sound_bottomEnd_crossFree (by decide) (by decide) (by decide) /-! ## A non-clamping cross-free witness The same selectors but reporting two keys `[0], [1]` gives `clampNonposBottom = false`, so the non-clamping branch of the cross-free cell is genuinely inhabited. Its database `[[0],[1],[2],[5],[5,0]]` has a nonnegative begin anchor and reports the whole window. -/ /-- The key `[2]`. -/ def xgTwo : Key := [(2 : Fin 256)] /-- The non-clamping result. -/ def xgResTwo : Result := { keys := [xgZero, xgOne], more := true } /-- The non-clamping database. -/ def xgDBNC : DB := ⟨[xgZero, xgOne, xgTwo, xgFive, xgFiveZero], by decide⟩ theorem xg_nonclamp_compatible : RangeRead.Compatible xgDBNC xgRead xgResTwo := by unfold RangeRead.Compatible RangeRead.withinLimit refine ⟨trivial, Or.inl ⟨rfl, ?_, by decide⟩⟩ decide /-- The non-clamping read/result still lies in the cross-free gap cell. -/ theorem xg_nonclamp_cell : negCrossTruncNonposGapCrossFree xgRead xgResTwo := by refine ⟨?_, by decide⟩ unfold negCrossTruncNonposGap refine ⟨rfl, rfl, by decide, by decide, by decide, by decide, by decide, by decide, by decide, by decide, ?_⟩ right decide /-- The begin selector does not clamp for the two-key result. -/ theorem xg_nonclamp : ¬ clampNonposBottom xgRead xgResTwo := by decide /-- `[head, end_.key)` is sound in the non-clamping cross-free branch. -/ theorem xg_nonclamp_headRange_sound : Sound xgRead xgResTwo (⟨(xgZero : Key), (xgFiveZeroZero : Key)⟩ : ConflictRange) := by exact sound_headEnd_crossFree rfl rfl (by decide) (by decide) (by decide) (by decide) xg_nonclamp (by decide) (by decide) end FormalConflictRange namespace FormalConflictRange /-- Extended-natural arithmetic: if `D + 1 ≤ x + g` with `g ≤ D` finite, then `D + 1 - g ≤ x`. -/ theorem enat_sub_cast_le_of_add_cast_le {x : ℕ∞} {g D : ℕ} (h : ((D + 1 : ℕ) : ℕ∞) ≤ x + (g : ℕ∞)) (hg : g ≤ D) : ((D + 1 - g : ℕ) : ℕ∞) ≤ x := by have hD2 : ((D + 1 : ℕ) : ℕ∞) = (g : ℕ∞) + ((D + 1 - g : ℕ) : ℕ∞) := by have h1 : D + 1 = g + (D + 1 - g) := by omega conv_lhs => rw [h1] exact Nat.cast_add .. rw [hD2, add_comm (g : ℕ∞) ((D + 1 - g : ℕ) : ℕ∞)] at h exact (ENat.add_le_add_iff_right (by simp : (g : ℕ∞) ≠ ⊤)).mp h /-- In the cross-free low-capacity gap cell, the key space from the reported last to `begin.key` holds at least `clampNonposD + 1 - g` keys, where `g = intervalCard begin end`. This is the room needed to build the padding database. -/ theorem intervalCard_begin_key_ge_of_crossFree {db : DB} {r : RangeRead} {res : Result} (hcomp : RangeRead.Compatible db r res) (hcell : negCrossTruncNonposGapCrossFree r res) (hne : res.keys ≠ []) : ((clampNonposD r + 1 - (intervalCard r.begin.key r.end_.key).toNat : ℕ) : ℕ∞) ≤ intervalCard (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key) r.begin.key := by obtain ⟨hcell0, hB_le_E⟩ := hcell obtain ⟨hmore, hrev, hbegin, -, hcross, hend, hclamp, hlastB, hlastE, hEne, hcap⟩ := hcell0 have hcap' : intervalCard r.begin.key r.end_.key < ((clampNonposD r + 1 : ℕ) : ℕ∞) := by rcases hcap with hcrosslt | hlt · exact absurd hcrosslt (not_lt.mpr hB_le_E) · exact hlt have hlt_top : intervalCard r.begin.key r.end_.key < (⊤ : ℕ∞) := lt_of_lt_of_le hcap' (by simp) have hne_top : intervalCard r.begin.key r.end_.key ≠ (⊤ : ℕ∞) := ne_of_lt hlt_top have hg : intervalCard r.begin.key r.end_.key = ((intervalCard r.begin.key r.end_.key).toNat : ℕ∞) := (ENat.natCast_toNat hne_top).symm have hg_le : (intervalCard r.begin.key r.end_.key).toNat ≤ clampNonposD r := by have h := hcap' rw [hg] at h have h' : (intervalCard r.begin.key r.end_.key).toNat < clampNonposD r + 1 := by exact_mod_cast h omega have hlastD_eq : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl have hlast_lt_B : ((res.keys.getLast hne : Key) : WithTop Key) < r.begin.key := by rw [← hlastD_eq]; exact hlastB have hka_le_B : ((keyAfter (res.keys.getLast hne) : Key) : WithTop Key) ≤ r.begin.key := keyAfter_le_of_lt hlast_lt_B have hkeyAdd : intervalCard (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key) r.end_.key = intervalCard (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key) r.begin.key + intervalCard r.begin.key r.end_.key := intervalCard_add hka_le_B hB_le_E have htot : ((clampNonposD r + 1 : ℕ) : ℕ∞) ≤ intervalCard (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key) r.begin.key + intervalCard r.begin.key r.end_.key := by have h := intervalCard_keyAfter_getLast_ge (db := db) (r := r) (res := res) hcomp hne hend rw [hkeyAdd] at h exact h rw [hg] at htot exact enat_sub_cast_le_of_add_cast_le htot hg_le end FormalConflictRange namespace FormalConflictRange /-- Padding the reported keys with `f = D + 1 - g` keys in `(last, begin.key)` and the `g` keys of `[begin.key, end_.key)` gives a compatible database: the end selector resolves exactly at index `#reported`, and the begin anchor is nonpositive. Here `g = intervalCard begin end` and `D = clampNonposD`. -/ theorem exists_padDb_crossFree {r : RangeRead} {res : Result} {dbF1 dbF2 : DB} {g : ℕ} (hsort : res.keys.SortedLT) (hrev : r.reverse = false) (hmore : res.more = true) (hne : res.keys ≠ []) (hlim : RangeRead.withinLimit r res.keys) (hbegin : r.begin.offset < 0) (hend : r.end_.offset ≤ 0) (hB_le_E : r.begin.key ≤ r.end_.key) (hEne : r.end_.key < (⊤ : WithTop Key)) (hlastB : ((res.keys.getLastD ([] : Key) : Key) : WithTop Key) < r.begin.key) (hg_le : g ≤ clampNonposD r) (hF1last : ∀ x ∈ dbF1.keys, res.keys.getLast hne < x) (hF1B : ∀ x ∈ dbF1.keys, (x : WithTop Key) < r.begin.key) (hF1len : dbF1.keys.length = clampNonposD r + 1 - g) (hF2B : ∀ x ∈ dbF2.keys, r.begin.key ≤ (x : WithTop Key)) (hF2E : ∀ x ∈ dbF2.keys, (x : WithTop Key) < r.end_.key) (hF2len : dbF2.keys.length = g) (hanc0 : res.keys.length + (clampNonposD r + 1 - g) ≤ beginSlack r + 1) : ∃ dbw : DB, dbw.keys = res.keys ++ dbF1.keys ++ dbF2.keys ∧ RangeRead.Compatible dbw r res ∧ r.end_.anchor dbw = (res.keys.length : ℤ) ∧ r.begin.anchor dbw ≤ 0 := by classical set last : Key := res.keys.getLast hne with hlast have hlastD : res.keys.getLastD ([] : Key) = last := by rw [hlast, List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl have hlast_lt_B : ((last : Key) : WithTop Key) < r.begin.key := by rw [← hlastD]; exact hlastB have hlast_lt_E : ((last : Key) : WithTop Key) < r.end_.key := lt_of_lt_of_le hlast_lt_B hB_le_E have hle_last : ∀ x ∈ res.keys, x ≤ last := fun x hx => (hsort.pairwise.imp le_of_lt).rel_getLast hx have hF1ne : dbF1.keys ≠ [] := by intro h rw [h] at hF1len simp only [List.length_nil] at hF1len omega -- sorted concatenation set F : List Key := dbF1.keys ++ dbF2.keys with hF have hFsorted : F.SortedLT := by rw [hF, List.sortedLT_append] refine ⟨dbF1.sorted, dbF2.sorted, ?_⟩ intro a ha b hb exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le (hF1B a ha) (hF2B b hb)) have hFsorted' : (res.keys ++ F).SortedLT := by rw [List.sortedLT_append] refine ⟨hsort, hFsorted, ?_⟩ intro a ha b hb rw [hF] at hb rcases List.mem_append.mp hb with hb | hb · exact lt_of_le_of_lt (hle_last a ha) (hF1last b hb) · exact lt_of_le_of_lt (hle_last a ha) (WithTop.coe_lt_coe.mp (lt_of_lt_of_le hlast_lt_B (hF2B b hb))) let dbw : DB := ⟨res.keys ++ F, hFsorted'⟩ have hkeyw : dbw.keys = res.keys ++ dbF1.keys ++ dbF2.keys := by change res.keys ++ F = _; rw [hF, List.append_assoc] -- all stored keys lie below the end key have hall_lt_E : ∀ x ∈ dbw.keys, (x : WithTop Key) < r.end_.key := by intro x hx rw [hkeyw] at hx rcases List.mem_append.mp hx with hx | hx · rcases List.mem_append.mp hx with hx | hx · exact lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hle_last x hx)) hlast_lt_E · exact lt_of_lt_of_le (hF1B x hx) hB_le_E · exact hF2E x hx have hlen : dbw.keys.length = res.keys.length + (clampNonposD r + 1) := by rw [hkeyw, List.length_append, List.length_append, hF1len, hF2len] omega have hcntE : dbw.keys.countP (fun x : Key => decide ((x : WithTop Key) < r.end_.key)) = dbw.keys.length := by rw [List.countP_eq_length] intro x hx rw [decide_eq_true_eq] exact hall_lt_E x hx have hDint : ((clampNonposD r : ℕ) : ℤ) = -r.end_.offset := by rw [clampNonposD_eq] exact Int.toNat_of_nonneg (by omega) have hanchorE : r.end_.anchor dbw = (res.keys.length : ℤ) := by cases hE : r.end_.key with | top => exact absurd hE (ne_of_lt hEne) | coe e => have hce : dbw.keys.countP (fun x : Key => decide (x < e)) = dbw.keys.length := by rw [← countP_lt_coe (l := dbw.keys) e, ← hE] exact hcntE rw [anchor_of_coe (s := r.end_) (v := e) hE, hce, hlen] push_cast omega -- the count below the begin key is `t + f` have hcntB : dbw.keys.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = res.keys.length + (clampNonposD r + 1 - g) := by rw [hkeyw, List.countP_append, List.countP_append] have h1 : res.keys.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = res.keys.length := by rw [List.countP_eq_length] intro x hx rw [decide_eq_true_eq] exact lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hle_last x hx)) hlast_lt_B have h2 : dbF1.keys.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = dbF1.keys.length := by rw [List.countP_eq_length] intro x hx rw [decide_eq_true_eq] exact hF1B x hx have h3 : dbF2.keys.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = 0 := by rw [List.countP_eq_zero] intro x hx simp only [decide_eq_true_eq, not_lt] exact hF2B x hx rw [h1, h2, h3, hF1len] omega have hanchorB : r.begin.anchor dbw ≤ 0 := by rw [anchor_eq_count_sub_slack dbw r (le_of_lt hbegin), hcntB] have h := hanc0 push_cast omega -- the end resolution sits at the first filler, above the reported last have hFne : F ≠ [] := by rw [hF] exact List.append_ne_nil_of_left_ne_nil hF1ne _ have hDget? : (res.keys ++ F)[res.keys.length]? = some (F.head hFne) := by rw [List.getElem?_append] rw [ite_eq_right (not_lt.mpr (le_refl _)), Nat.sub_self] rw [List.getElem?_eq_getElem (by rw [hF, List.length_append]; omega), List.head_eq_getElem hFne] have hre : resolve dbw r.end_ = ((F.head hFne : Key) : WithTop Key) := by have hanchorE0 : 0 ≤ r.end_.anchor dbw := by rw [hanchorE]; exact Int.natCast_nonneg _ have hltlen : (r.end_.anchor dbw).toNat < dbw.keys.length := by rw [hanchorE, Int.toNat_natCast, hkeyw, List.length_append, List.length_append, hF1len, hF2len] omega have htoNat : (r.end_.anchor dbw).toNat = res.keys.length := by rw [hanchorE]; simp have hsome : dbw.keys[(r.end_.anchor dbw).toNat]? = some (F.head hFne) := by rw [htoNat] exact hDget? have hget : dbw.keys[(r.end_.anchor dbw).toNat] = F.head hFne := (List.getElem?_eq_some_iff.mp hsome).2 rw [resolve_eq_getElem hanchorE0 hltlen, hget] have hFgt : ∀ x ∈ F, last < x := by intro x hx have hx' : x ∈ dbF1.keys ++ dbF2.keys := hx rcases List.mem_append.mp hx' with hx' | hx' · exact hF1last x hx' · exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le hlast_lt_B (hF2B x hx')) have hlast_lt_Fhead : last < F.head hFne := hFgt _ (List.head_mem hFne) have hFhead_le : ∀ x, x ∈ F → F.head hFne ≤ x := fun x hx => (hFsorted.pairwise.imp le_of_lt).rel_head hx have hFhead_le_F1 : ∀ x ∈ dbF1.keys, F.head hFne ≤ x := fun x hx => hFhead_le x (List.mem_append.mpr (Or.inl hx)) have hFhead_le_F2 : ∀ x ∈ dbF2.keys, F.head hFne ≤ x := fun x hx => hFhead_le x (List.mem_append.mpr (Or.inr hx)) -- begin resolution is at most the reported head have hb_le_head : resolve dbw r.begin ≤ ((res.keys.head hne : Key) : WithTop Key) := by by_cases hneg : r.begin.anchor dbw < 0 · rw [resolve_eq_nil hneg] exact WithTop.coe_le_coe.mpr (nil_le_key _) · have hzero : r.begin.anchor dbw = 0 := by omega have h0 : 0 ≤ r.begin.anchor dbw := by omega have hlt : (r.begin.anchor dbw).toNat < dbw.keys.length := by rw [hzero, hkeyw, List.length_append, List.length_append, hF1len, hF2len] simp omega have htoNat : (r.begin.anchor dbw).toNat = 0 := by rw [hzero]; simp have hget : dbw.keys[(r.begin.anchor dbw).toNat] = res.keys.head hne := by have hsome : dbw.keys[(r.begin.anchor dbw).toNat]? = some (res.keys.head hne) := by rw [htoNat] rw [hkeyw, List.append_assoc] have hpos : 0 < res.keys.length := List.length_pos_iff.mpr hne rw [List.getElem?_append_left hpos, ← List.head?_eq_getElem?] exact List.head?_eq_some_head hne exact (List.getElem?_eq_some_iff.mp hsome).2 rw [resolve_eq_getElem h0 hlt, hget] -- the complete keys are exactly the reported keys have hck : RangeRead.completeKeys dbw r = res.keys := by unfold RangeRead.completeKeys RangeRead.inRange rw [ite_eq_right (by simp [hrev])] rw [hkeyw, List.filter_append, List.filter_append] have hres : res.keys.filter (fun k : Key => decide (resolve dbw r.begin ≤ ((k : Key) : WithTop Key) ∧ ((k : Key) : WithTop Key) < resolve dbw r.end_)) = res.keys := by rw [List.filter_eq_self] intro x hx rw [decide_eq_true_eq] refine ⟨le_trans hb_le_head (WithTop.coe_le_coe.mpr ((hsort.pairwise.imp le_of_lt).rel_head hx)), ?_⟩ rw [hre] exact WithTop.coe_lt_coe.mpr (lt_of_le_of_lt (hle_last x hx) hlast_lt_Fhead) have hF1nil : dbF1.keys.filter (fun k : Key => decide (resolve dbw r.begin ≤ ((k : Key) : WithTop Key) ∧ ((k : Key) : WithTop Key) < resolve dbw r.end_)) = [] := by rw [List.filter_eq_nil_iff] intro x hx rw [decide_eq_true_eq, hre] intro hcon exact not_lt.mpr (WithTop.coe_le_coe.mpr (hFhead_le_F1 x hx)) hcon.2 have hF2nil : dbF2.keys.filter (fun k : Key => decide (resolve dbw r.begin ≤ ((k : Key) : WithTop Key) ∧ ((k : Key) : WithTop Key) < resolve dbw r.end_)) = [] := by rw [List.filter_eq_nil_iff] intro x hx rw [decide_eq_true_eq, hre] intro hcon exact not_lt.mpr (WithTop.coe_le_coe.mpr (hFhead_le_F2 x hx)) hcon.2 rw [hres, hF1nil, hF2nil, List.append_nil, List.append_nil] refine ⟨dbw, hkeyw, ?_, hanchorE, hanchorB⟩ exact ⟨hlim, Or.inl ⟨hmore, by rw [hck], hne⟩⟩ /-- Padding a compatible database with a list `F` of keys strictly above the reported last and strictly below the end key, whose length is `clampNonposD + 1`, and where the end selector anchors exactly at the reported count, makes any single padding key necessary: erasing it drops the end resolution onto the reported last, which the result does not report. -/ theorem erase_incompatible_of_pad {r : RangeRead} {res : Result} {dbw : DB} {F : List Key} {k : Key} (hsort : res.keys.SortedLT) (hrev : r.reverse = false) (hmore : res.more = true) (hne : res.keys ≠ []) (hkeyw : dbw.keys = res.keys ++ F) (hkF : k ∈ F) (hFgt : ∀ x ∈ F, res.keys.getLast hne < x) (hreslt : ∀ x ∈ res.keys, (x : WithTop Key) < r.end_.key) (hFlt : ∀ x ∈ F, (x : WithTop Key) < r.end_.key) (hFlen : F.length = clampNonposD r + 1) (hend : r.end_.offset ≤ 0) (hEne : r.end_.key < (⊤ : WithTop Key)) : ¬ RangeRead.Compatible (dbw.erase k) r res := by classical have hle_last : ∀ x ∈ res.keys, x ≤ res.keys.getLast hne := fun x hx => (hsort.pairwise.imp le_of_lt).rel_getLast hx have hk_not_res : k ∉ res.keys := by intro hx exact absurd (hFgt k hkF) (not_lt.mpr (hle_last k hx)) have herase_keys : (dbw.erase k).keys = res.keys ++ F.erase k := by rw [DB.erase_keys, hkeyw, List.erase_append_right F hk_not_res] have hEraseLt : ∀ x ∈ (dbw.erase k).keys, (x : WithTop Key) < r.end_.key := by intro x hx rw [herase_keys] at hx rcases List.mem_append.mp hx with hx | hx · exact hreslt x hx · exact hFlt x (List.mem_of_mem_erase hx) have hcntErase : cnt (dbw.erase k) r.end_.key = (dbw.erase k).keys.length := cnt_eq_length_of_forall_lt _ hEraseLt have hlenErase : (dbw.erase k).keys.length = res.keys.length + clampNonposD r := by rw [herase_keys, List.length_append, List.length_erase, ite_eq_left hkF, hFlen] omega have hoff : r.end_.offset = -(clampNonposD r : ℤ) := by rw [clampNonposD_eq] have hnonneg : 0 ≤ -r.end_.offset := by omega rw [Int.toNat_of_nonneg hnonneg]; ring obtain ⟨e, he⟩ : ∃ e : Key, r.end_.key = (↑e : WithTop Key) := by cases h : r.end_.key with | top => exact absurd h (ne_of_lt hEne) | coe e => exact ⟨e, rfl⟩ have hanchorErase : r.end_.anchor (dbw.erase k) = (res.keys.length : ℤ) - 1 := by rw [anchor_of_coe (s := r.end_) (v := e) he] have hce : (dbw.erase k).keys.countP (fun x => decide (x < e)) = res.keys.length + clampNonposD r := by rw [← countP_lt_coe (l := (dbw.erase k).keys) e, ← he] exact hcntErase.trans hlenErase rw [hce, hoff]; push_cast; ring have ht_pos : 0 < res.keys.length := List.length_pos_iff.mpr hne have hresolve_end : resolve (dbw.erase k) r.end_ = ((res.keys.getLast hne : Key) : WithTop Key) := by have h0 : 0 ≤ r.end_.anchor (dbw.erase k) := by rw [hanchorErase]; omega have hlt : (r.end_.anchor (dbw.erase k)).toNat < (dbw.erase k).keys.length := by rw [hanchorErase, hlenErase]; omega rw [resolve_eq_getElem h0 hlt] have hidx : (r.end_.anchor (dbw.erase k)).toNat = res.keys.length - 1 := by rw [hanchorErase] have : ((res.keys.length : ℤ) - 1).toNat = res.keys.length - 1 := by omega exact this have hget : (dbw.erase k).keys[(r.end_.anchor (dbw.erase k)).toNat] = res.keys.getLast hne := by simp only [hidx, herase_keys] have hlen : res.keys.length - 1 < res.keys.length := by omega rw [List.getElem_append_left (i := res.keys.length - 1) (h := hlen)] exact (List.getLast_eq_getElem hne).symm rw [hget] intro hcomp' have hfilt := ((compatible_iff_truncated_keys hrev hmore hne).mp hcomp').2 have hlast_not_ck : res.keys.getLast hne ∉ RangeRead.completeKeys (dbw.erase k) r := by rw [RangeRead.mem_completeKeys, hresolve_end] rintro ⟨-, -, hlt⟩ exact lt_irrefl _ hlt have hlast_in_filt : res.keys.getLast hne ∈ (RangeRead.completeKeys (dbw.erase k) r).filter (fun x : Key => decide (x ≤ res.keys.getLast hne)) := by rw [hfilt]; exact List.getLast_mem hne exact hlast_not_ck (List.mem_of_mem_filter hlast_in_filt) /-- A database of `f` keys in `(last, begin.key)`. -/ theorem exists_dbF1_crossFree {r : RangeRead} {res : Result} {f : ℕ} {b : Key} (hne : res.keys ≠ []) (hb : r.begin.key = ((b : Key) : WithTop Key)) (hroom : (f : ℕ∞) ≤ intervalCard (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key) r.begin.key) : ∃ dbF1 : DB, (∀ x ∈ dbF1.keys, res.keys.getLast hne < x) ∧ (∀ x ∈ dbF1.keys, (x : WithTop Key) < r.begin.key) ∧ dbF1.keys.length = f := by obtain ⟨dbF1, hmem, hlen⟩ := exists_db_keysIn (B := (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key)) (E := r.begin.key) (m := f) hroom refine ⟨dbF1, ?_, ?_, hlen⟩ · intro x hx have h := hmem x hx rw [hb] at h rw [mem_keysIn_coe] at h exact lt_of_lt_of_le (keyAfter_self_lt _) h.1 · intro x hx have h := hmem x hx rw [hb] at h rw [mem_keysIn_coe] at h rw [hb]; exact WithTop.coe_lt_coe.mpr h.2 /-- A database of `g` keys in `[begin.key, end_.key)`. -/ theorem exists_dbF2_crossFree {r : RangeRead} {_res : Result} {g : ℕ} {b e : Key} (hb : r.begin.key = ((b : Key) : WithTop Key)) (he : r.end_.key = ((e : Key) : WithTop Key)) (hcap : (g : ℕ∞) ≤ intervalCard r.begin.key r.end_.key) : ∃ dbF2 : DB, (∀ x ∈ dbF2.keys, r.begin.key ≤ (x : WithTop Key)) ∧ (∀ x ∈ dbF2.keys, (x : WithTop Key) < r.end_.key) ∧ dbF2.keys.length = g := by obtain ⟨dbF2, hmem, hlen⟩ := exists_db_keysIn (B := r.begin.key) (E := r.end_.key) (m := g) hcap refine ⟨dbF2, ?_, ?_, hlen⟩ · intro x hx have h := hmem x hx rw [hb, he] at h rw [mem_keysIn_coe] at h rw [hb]; exact WithTop.coe_le_coe.mpr h.1 · intro x hx have h := hmem x hx rw [hb, he] at h rw [mem_keysIn_coe] at h rw [he]; exact WithTop.coe_lt_coe.mpr h.2 /-- A database of `f - 1` keys in `(last, begin.key)` avoiding a chosen key. -/ theorem exists_dbF1_avoid_crossFree {r : RangeRead} {res : Result} {f : ℕ} {k b : Key} (hne : res.keys ≠ []) (hb : r.begin.key = ((b : Key) : WithTop Key)) (hf : 1 ≤ f) (hroom : (f : ℕ∞) ≤ intervalCard (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key) r.begin.key) : ∃ dbB : DB, (∀ x ∈ dbB.keys, res.keys.getLast hne < x) ∧ (∀ x ∈ dbB.keys, (x : WithTop Key) < r.begin.key) ∧ dbB.keys.length = f - 1 ∧ k ∉ dbB.keys := by have hcard : (((f - 1) + 1 : ℕ) : ℕ∞) ≤ intervalCard (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key) r.begin.key := by rwa [Nat.sub_add_cancel hf] obtain ⟨dbB, hmem, hBk, hlen⟩ := exists_db_keysIn_avoid (B := (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key)) (E := r.begin.key) (k := k) (m := f - 1) hcard refine ⟨dbB, ?_, ?_, hlen, hBk⟩ · intro x hx have h := hmem x hx rw [hb] at h rw [mem_keysIn_coe] at h exact lt_of_lt_of_le (keyAfter_self_lt _) h.1 · intro x hx have h := hmem x hx rw [hb] at h rw [mem_keysIn_coe] at h rw [hb]; exact WithTop.coe_lt_coe.mpr h.2 /-- A database of `f` keys in `(last, begin.key)` containing a chosen key `k`. -/ theorem exists_dbF1_mem_crossFree {r : RangeRead} {res : Result} {f : ℕ} {k b : Key} (hne : res.keys ≠ []) (hb : r.begin.key = ((b : Key) : WithTop Key)) (hf : 1 ≤ f) (hroom : (f : ℕ∞) ≤ intervalCard (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key) r.begin.key) (hk : ((res.keys.getLast hne : Key) : WithTop Key) < (k : WithTop Key)) (hkB : (k : WithTop Key) < r.begin.key) : ∃ dbF1 : DB, (∀ x ∈ dbF1.keys, res.keys.getLast hne < x) ∧ (∀ x ∈ dbF1.keys, (x : WithTop Key) < r.begin.key) ∧ dbF1.keys.length = f ∧ k ∈ dbF1.keys := by obtain ⟨dbB, hBgt, hBB, hBlen, hBk⟩ := exists_dbF1_avoid_crossFree (r := r) (res := res) (f := f) (k := k) (b := b) hne hb hf hroom let dbF1 : DB := dbB.insert k hBk have hkey : dbF1.keys = dbB.keys.orderedInsert (· ≤ ·) k := DB.insert_keys dbB k hBk refine ⟨dbF1, ?_, ?_, ?_, ?_⟩ · intro x hx rw [hkey] at hx rcases (List.mem_orderedInsert (· ≤ ·)).mp hx with rfl | hx · exact WithTop.coe_lt_coe.mp hk · exact hBgt x hx · intro x hx rw [hkey] at hx rcases (List.mem_orderedInsert (· ≤ ·)).mp hx with rfl | hx · exact hkB · exact hBB x hx · rw [DB.insert_keys, List.orderedInsert_length, hBlen] omega · exact DB.mem_insert_self dbB k hBk /-- A database of `g - 1` keys in `[begin.key, end_.key)` avoiding a chosen key. -/ theorem exists_dbF2_avoid_crossFree {r : RangeRead} {_res : Result} {g : ℕ} {k b e : Key} (hb : r.begin.key = ((b : Key) : WithTop Key)) (he : r.end_.key = ((e : Key) : WithTop Key)) (hg : 1 ≤ g) (hcap : (g : ℕ∞) ≤ intervalCard r.begin.key r.end_.key) : ∃ dbB : DB, (∀ x ∈ dbB.keys, r.begin.key ≤ (x : WithTop Key)) ∧ (∀ x ∈ dbB.keys, (x : WithTop Key) < r.end_.key) ∧ dbB.keys.length = g - 1 ∧ k ∉ dbB.keys := by have hcard : (((g - 1) + 1 : ℕ) : ℕ∞) ≤ intervalCard r.begin.key r.end_.key := by rwa [Nat.sub_add_cancel hg] obtain ⟨dbB, hmem, hBk, hlen⟩ := exists_db_keysIn_avoid (B := r.begin.key) (E := r.end_.key) (k := k) (m := g - 1) hcard refine ⟨dbB, ?_, ?_, hlen, hBk⟩ · intro x hx have h := hmem x hx rw [hb, he] at h rw [mem_keysIn_coe] at h rw [hb]; exact WithTop.coe_le_coe.mpr h.1 · intro x hx have h := hmem x hx rw [hb, he] at h rw [mem_keysIn_coe] at h rw [he]; exact WithTop.coe_lt_coe.mpr h.2 /-- A database of `g` keys in `[begin.key, end_.key)` containing a chosen key `k`. -/ theorem exists_dbF2_mem_crossFree {r : RangeRead} {res : Result} {g : ℕ} {k b e : Key} (hb : r.begin.key = ((b : Key) : WithTop Key)) (he : r.end_.key = ((e : Key) : WithTop Key)) (hg : 1 ≤ g) (hcap : (g : ℕ∞) ≤ intervalCard r.begin.key r.end_.key) (hkB : r.begin.key ≤ (k : WithTop Key)) (hkE : (k : WithTop Key) < r.end_.key) : ∃ dbF2 : DB, (∀ x ∈ dbF2.keys, r.begin.key ≤ (x : WithTop Key)) ∧ (∀ x ∈ dbF2.keys, (x : WithTop Key) < r.end_.key) ∧ dbF2.keys.length = g ∧ k ∈ dbF2.keys := by obtain ⟨dbB, hBB, hBE, hBlen, hBk⟩ := exists_dbF2_avoid_crossFree (r := r) (_res := res) (g := g) (k := k) (b := b) (e := e) hb he hg hcap let dbF2 : DB := dbB.insert k hBk have hkey : dbF2.keys = dbB.keys.orderedInsert (· ≤ ·) k := DB.insert_keys dbB k hBk refine ⟨dbF2, ?_, ?_, ?_, ?_⟩ · intro x hx rw [hkey] at hx rcases (List.mem_orderedInsert (· ≤ ·)).mp hx with rfl | hx · exact hkB · exact hBB x hx · intro x hx rw [hkey] at hx rcases (List.mem_orderedInsert (· ≤ ·)).mp hx with rfl | hx · exact hkE · exact hBE x hx · rw [DB.insert_keys, List.orderedInsert_length, hBlen] omega · exact DB.mem_insert_self dbB k hBk end FormalConflictRange namespace FormalConflictRange /-- In the cross-free low-capacity gap cell the interval capacity is finite and at most `clampNonposD`. -/ theorem crossFree_g_le {r : RangeRead} {res : Result} (hcell : negCrossTruncNonposGapCrossFree r res) : (intervalCard r.begin.key r.end_.key).toNat ≤ clampNonposD r := by obtain ⟨hcell0, hB_le_E⟩ := hcell obtain ⟨hmore, hrev, hbegin, -, hcross, hend, hclamp, hlastB, hlastE, hEne, hcap⟩ := hcell0 have hcap' : intervalCard r.begin.key r.end_.key < ((clampNonposD r + 1 : ℕ) : ℕ∞) := by rcases hcap with hcrosslt | hlt · exact absurd hcrosslt (not_lt.mpr hB_le_E) · exact hlt have hlt_top : intervalCard r.begin.key r.end_.key < (⊤ : ℕ∞) := lt_of_lt_of_le hcap' (by simp) have hne_top : intervalCard r.begin.key r.end_.key ≠ (⊤ : ℕ∞) := ne_of_lt hlt_top have hg : intervalCard r.begin.key r.end_.key = ((intervalCard r.begin.key r.end_.key).toNat : ℕ∞) := (ENat.natCast_toNat hne_top).symm have h := hcap' rw [hg] at h have h' : (intervalCard r.begin.key r.end_.key).toNat < clampNonposD r + 1 := by exact_mod_cast h omega /-- In the cross-free low-capacity gap cell readability forces the padding inequality `t + (D + 1 - g) ≤ beginSlack + 1`, where `t` is the reported count, `D` the end overshoot and `g` the capacity of `[begin.key, end_.key)`. -/ theorem crossFree_pad_hanc0 {r : RangeRead} {res : Result} (hread : Readable r res) (hcell : negCrossTruncNonposGapCrossFree r res) (hne : res.keys ≠ []) : res.keys.length + (clampNonposD r + 1 - (intervalCard r.begin.key r.end_.key).toNat) ≤ beginSlack r + 1 := by classical have hcellKeep : negCrossTruncNonposGapCrossFree r res := hcell obtain ⟨hcell0, hB_le_E⟩ := hcell obtain ⟨hmore, hrev, hbegin, -, hcrossL, hend, hclamp, hlastB, hlastE, hEne, hcap⟩ := hcell0 obtain ⟨db₀, hcomp₀⟩ := hread have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev have hg_le := crossFree_g_le hcellKeep have hrep : reportedBelowBegin r res = res.keys.length := reportedBelowBegin_eq_length_of_last_lt hne hsort hlastB by_cases hbot : clampNonposBottom r res · -- clamping: `clampNonposBottom` gives `t + f ≤ beginSlack` have h := hbot unfold clampNonposBottom at h rw [hrep] at h -- the subtraction `(D+1) - intervalCard` is the natural `D+1-g` have htop : intervalCard r.begin.key r.end_.key < (⊤ : ℕ∞) := by have hcap' : intervalCard r.begin.key r.end_.key < ((clampNonposD r + 1 : ℕ) : ℕ∞) := by rcases hcap with hcrosslt | hlt · exact absurd hcrosslt (not_lt.mpr hB_le_E) · exact hlt exact lt_of_lt_of_le hcap' (by simp) have hg : intervalCard r.begin.key r.end_.key = ((intervalCard r.begin.key r.end_.key).toNat : ℕ∞) := (ENat.natCast_toNat (ne_of_lt htop)).symm rw [hg] at h -- `((D+1:ℕ):ℕ∞) - (g:ℕ∞) = ((D+1-g:ℕ):ℕ∞)` have hsub : (((clampNonposD r + 1 : ℕ) : ℕ∞) - ((intervalCard r.begin.key r.end_.key).toNat : ℕ∞)) = ((clampNonposD r + 1 - (intervalCard r.begin.key r.end_.key).toNat : ℕ) : ℕ∞) := (ENat.natCast_sub (clampNonposD r + 1) (intervalCard r.begin.key r.end_.key).toNat).symm rw [hsub] at h have hnat : res.keys.length + (clampNonposD r + 1 - (intervalCard r.begin.key r.end_.key).toNat) ≤ beginSlack r := by exact_mod_cast h omega · -- non-clamping: count stored keys above the reported last have hhead : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key := by have hle : leastReported r res = res.keys.head hne := by simp [leastReported, hrev, List.head?_eq_some_head hne] rwa [hle] at hcrossL have hanc : 0 ≤ r.begin.anchor db₀ := by by_contra h exact hbot (clampNonposBottom_of_anchor_neg_trunc hcomp₀ hrev hmore hne hbegin hend hclamp (by omega)) have hhead_mem : res.keys.head hne ∈ res.keys := List.head_mem hne have hlast_mem : res.keys.getLast hne ∈ res.keys := List.getLast_mem hne have hhead_le_last : res.keys.head hne ≤ res.keys.getLast hne := (hsort.pairwise.imp le_of_lt).rel_getLast hhead_mem have hheadB : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key := hhead have hresBegin : resolve db₀ r.begin = ((res.keys.head hne : Key) : WithTop Key) := resolve_begin_eq_head_of_nonbottom hcomp₀ hrev hmore hne hbegin hend hclamp hbot have hgap := gap_count_eq_beginSlack_of_resolve_head (db := db₀) hbegin hhead hanc hresBegin -- `last` is complete and lies below the end resolution have hlast_ck : res.keys.getLast hne ∈ RangeRead.completeKeys db₀ r := (RangeRead.compatible_keys_prefix hcomp₀).subset hlast_mem have hresEnd_gt : ((res.keys.getLast hne : Key) : WithTop Key) < resolve db₀ r.end_ := (RangeRead.mem_completeKeys.mp hlast_ck).2.2 have hfilterComp : (RangeRead.completeKeys db₀ r).filter (fun k : Key => decide (k ≤ res.keys.getLast hne)) = res.keys := ((compatible_iff_truncated_keys hrev hmore hne).mp hcomp₀).2 -- stored keys in `[head, last]` are exactly the reported ones have hfilter := completeKeys_filter_le_of_resolve_begin (db := db₀) hrev hresBegin hresEnd_gt have hHL : db₀.keys.filter (fun k : Key => decide (((res.keys.head hne : Key) : WithTop Key) ≤ (k : WithTop Key) ∧ (k : Key) ≤ res.keys.getLast hne)) = res.keys := by rw [← hfilter, hfilterComp] -- the same filter with `< keyAfter last` have hHKa : (between db₀ ((res.keys.head hne : Key) : WithTop Key) (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key)).length = res.keys.length := by unfold between have hcongr : db₀.keys.filter (fun k : Key => decide (((res.keys.head hne : Key) : WithTop Key) ≤ (k : WithTop Key) ∧ ((k : Key) : WithTop Key) < ((keyAfter (res.keys.getLast hne) : Key) : WithTop Key))) = db₀.keys.filter (fun k : Key => decide (((res.keys.head hne : Key) : WithTop Key) ≤ (k : WithTop Key) ∧ (k : Key) ≤ res.keys.getLast hne)) := by apply List.filter_congr intro k _ rw [decide_eq_decide] by_cases hk : ((res.keys.head hne : Key) : WithTop Key) ≤ (k : WithTop Key) · simp only [hk, true_and] exact WithTop.coe_lt_coe.trans (lt_keyAfter_iff k (res.keys.getLast hne)) · simp only [hk, false_and] rw [hcongr, hHL] -- counts split at `keyAfter last` and at `begin.key` have hcntB : (cnt db₀ r.begin.key) = (cnt db₀ ((res.keys.head hne : Key) : WithTop Key)) + (between db₀ ((res.keys.head hne : Key) : WithTop Key) r.begin.key).length := cnt_eq_add_between db₀ (le_of_lt hheadB) have hgapLen : (between db₀ ((res.keys.head hne : Key) : WithTop Key) r.begin.key).length = beginSlack r + 1 := by rw [← hgap] unfold between rw [List.countP_eq_length_filter] have hcntKa : (cnt db₀ (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key)) = (cnt db₀ ((res.keys.head hne : Key) : WithTop Key)) + res.keys.length := by have := cnt_eq_add_between db₀ (w₁ := ((res.keys.head hne : Key) : WithTop Key)) (w₂ := (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key)) (by exact WithTop.coe_le_coe.mpr (le_trans hhead_le_last (le_of_lt (keyAfter_self_lt _)))) rw [this, hHKa] have hka_le_B : (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key) ≤ r.begin.key := by apply keyAfter_le_of_lt have hlastD : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl rwa [hlastD] at hlastB have hcntB2 : (cnt db₀ r.begin.key) = (cnt db₀ (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key)) + (between db₀ (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key) r.begin.key).length := cnt_eq_add_between db₀ hka_le_B -- the end resolution sits above the reported last have hresEnd_ne : resolve db₀ r.end_ ≠ (([] : Key) : WithTop Key) := by intro h rw [h] at hresEnd_gt exact absurd hresEnd_gt (not_lt.mpr (coe_nil_le_key_withTop ((res.keys.getLast hne : Key) : WithTop Key))) have hbetween_len : (between db₀ (resolve db₀ r.end_) r.end_.key).length = clampNonposD r + 1 := between_resolve_end_length hend hresEnd_ne have hka_le_resEnd : (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key) ≤ resolve db₀ r.end_ := keyAfter_le_of_lt hresEnd_gt -- `[resolve end, end)` sits inside `[keyAfter last, end)` have hsub : (between db₀ (resolve db₀ r.end_) r.end_.key).length ≤ (between db₀ (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key) r.begin.key).length + (between db₀ r.begin.key r.end_.key).length := by -- count approach have hcountEnd : (cnt db₀ r.end_.key) = (cnt db₀ (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key)) + (between db₀ (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key) r.end_.key).length := cnt_eq_add_between db₀ (le_trans hka_le_B hB_le_E) have hcountEnd2 : (cnt db₀ r.end_.key) = (cnt db₀ (resolve db₀ r.end_)) + (between db₀ (resolve db₀ r.end_) r.end_.key).length := cnt_eq_add_between db₀ (resolve_le_key_of_offset_nonpos hend) have hsplit : (between db₀ (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key) r.end_.key).length = (between db₀ (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key) r.begin.key).length + (between db₀ r.begin.key r.end_.key).length := by have h1 := cnt_eq_add_between db₀ hka_le_B have h2 := cnt_eq_add_between db₀ hB_le_E have h3 := cnt_eq_add_between db₀ (le_trans hka_le_B hB_le_E) omega have hmono : (cnt db₀ (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key)) ≤ (cnt db₀ (resolve db₀ r.end_)) := cnt_le_cnt_of_le db₀ hka_le_resEnd rw [hsplit] at hcountEnd omega -- combine the counts have hG : (between db₀ (((keyAfter (res.keys.getLast hne) : Key)) : WithTop Key) r.begin.key).length = beginSlack r + 1 - res.keys.length := by have h1 := hcntB rw [hgapLen] at h1 rw [hcntKa] at hcntB2 omega have hHcard : (between db₀ r.begin.key r.end_.key).length ≤ (intervalCard r.begin.key r.end_.key).toNat := by have h := between_length_le_intervalCard (db := db₀) hB_le_E have htop : intervalCard r.begin.key r.end_.key < (⊤ : ℕ∞) := by have hcap' : intervalCard r.begin.key r.end_.key < ((clampNonposD r + 1 : ℕ) : ℕ∞) := by rcases hcap with hcrosslt | hlt · exact absurd hcrosslt (not_lt.mpr hB_le_E) · exact hlt exact lt_of_lt_of_le hcap' (by simp) have hg : ((intervalCard r.begin.key r.end_.key).toNat : ℕ∞) = intervalCard r.begin.key r.end_.key := ENat.natCast_toNat (ne_of_lt htop) rw [← hg] at h exact_mod_cast h rw [hbetween_len] at hsub omega /-- In the cross-free low-capacity gap cell, a key strictly between the reported last and `end_.key` has an erase witness. -/ theorem exists_witness_last_end_crossFree {r : RangeRead} {res : Result} {k : Key} (hread : Readable r res) (hcell : negCrossTruncNonposGapCrossFree r res) (hne : res.keys ≠ []) (hkgt : ((res.keys.getLast hne : Key) : WithTop Key) < (k : WithTop Key)) (hkE : (k : WithTop Key) < r.end_.key) : ∃ dbw : DB, RangeRead.Compatible dbw r res ∧ k ∈ dbw.keys ∧ ¬ RangeRead.Compatible (dbw.erase k) r res := by classical have hreadKeep : Readable r res := hread have hcellKeep : negCrossTruncNonposGapCrossFree r res := hcell obtain ⟨hcell0, hB_le_E⟩ := hcell obtain ⟨hmore, hrev, hbegin, -, hcrossL, hend, hclamp, hlastB, hlastE, hEne, hcap⟩ := hcell0 obtain ⟨db₀, hcomp₀⟩ := hread have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev have hlim : RangeRead.withinLimit r res.keys := hcomp₀.1 obtain ⟨b, hb⟩ : ∃ b : Key, r.begin.key = ((b : Key) : WithTop Key) := by cases h : r.begin.key with | top => rw [h] at hB_le_E exact absurd (lt_of_le_of_lt hB_le_E hEne) (lt_irrefl _) | coe b => exact ⟨b, rfl⟩ obtain ⟨e, he⟩ : ∃ e : Key, r.end_.key = ((e : Key) : WithTop Key) := by cases h : r.end_.key with | top => exact absurd h (ne_of_lt hEne) | coe e => exact ⟨e, rfl⟩ have hlastD : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl have hlast_lt_B : ((res.keys.getLast hne : Key) : WithTop Key) < r.begin.key := by rw [← hlastD]; exact hlastB have hlast_lt_E : ((res.keys.getLast hne : Key) : WithTop Key) < r.end_.key := by rw [← hlastD]; exact hlastE have hle_last : ∀ x ∈ res.keys, x ≤ res.keys.getLast hne := fun x hx => (hsort.pairwise.imp le_of_lt).rel_getLast hx set g : ℕ := (intervalCard r.begin.key r.end_.key).toNat with hgdef have hg_le : g ≤ clampNonposD r := crossFree_g_le hcellKeep set f : ℕ := clampNonposD r + 1 - g with hfdef have hf : 1 ≤ f := by rw [hfdef]; omega have hroom := intervalCard_begin_key_ge_of_crossFree hcomp₀ hcellKeep hne have hroom' : (f : ℕ∞) ≤ intervalCard (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key) r.begin.key := by rw [hfdef]; exact hroom have hfin : intervalCard r.begin.key r.end_.key < (⊤ : ℕ∞) := by have hcap' : intervalCard r.begin.key r.end_.key < ((clampNonposD r + 1 : ℕ) : ℕ∞) := by rcases hcap with hcrosslt | hlt · exact absurd hcrosslt (not_lt.mpr hB_le_E) · exact hlt exact lt_of_lt_of_le hcap' (by simp) have hcap2 : (g : ℕ∞) ≤ intervalCard r.begin.key r.end_.key := by rw [hgdef, ENat.natCast_toNat (ne_of_lt hfin)] have hanc0 := crossFree_pad_hanc0 hreadKeep hcellKeep hne have hanc0' : res.keys.length + f ≤ beginSlack r + 1 := by rw [hfdef, hgdef]; exact hanc0 -- combine the two padding lists have finish : ∀ (dbF1 dbF2 : DB) (hkIn : k ∈ dbF1.keys ++ dbF2.keys), (∀ x ∈ dbF1.keys, res.keys.getLast hne < x) → (∀ x ∈ dbF1.keys, (x : WithTop Key) < r.begin.key) → dbF1.keys.length = f → (∀ x ∈ dbF2.keys, r.begin.key ≤ (x : WithTop Key)) → (∀ x ∈ dbF2.keys, (x : WithTop Key) < r.end_.key) → dbF2.keys.length = g → ∃ dbw : DB, RangeRead.Compatible dbw r res ∧ k ∈ dbw.keys ∧ ¬ RangeRead.Compatible (dbw.erase k) r res := by intro dbF1 dbF2 hkIn hF1gt hF1B hF1len hF2B hF2E hF2len have hF1len' : dbF1.keys.length = clampNonposD r + 1 - g := by rw [hF1len, hfdef] obtain ⟨dbw, hkeyw, hcompw, hanchorE, hanchorB⟩ := exists_padDb_crossFree hsort hrev hmore hne hlim hbegin hend hB_le_E hEne hlastB hg_le hF1gt hF1B hF1len' hF2B hF2E hF2len hanc0' have hFgt : ∀ x ∈ dbF1.keys ++ dbF2.keys, res.keys.getLast hne < x := by intro x hx rcases List.mem_append.mp hx with hx | hx · exact hF1gt x hx · exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le hlast_lt_B (hF2B x hx)) have hFlt : ∀ x ∈ dbF1.keys ++ dbF2.keys, (x : WithTop Key) < r.end_.key := by intro x hx rcases List.mem_append.mp hx with hx | hx · exact lt_of_lt_of_le (hF1B x hx) hB_le_E · exact hF2E x hx have hreslt : ∀ x ∈ res.keys, (x : WithTop Key) < r.end_.key := fun x hx => lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hle_last x hx)) hlast_lt_E have hFlen : (dbF1.keys ++ dbF2.keys).length = clampNonposD r + 1 := by rw [List.length_append, hF1len, hF2len, hfdef] omega have hkeyw' : dbw.keys = res.keys ++ (dbF1.keys ++ dbF2.keys) := by rw [hkeyw, List.append_assoc] have herase := erase_incompatible_of_pad hsort hrev hmore hne hkeyw' hkIn hFgt hreslt hFlt hFlen hend hEne refine ⟨dbw, hcompw, ?_, herase⟩ rw [hkeyw'] exact List.mem_append.mpr (Or.inr hkIn) by_cases hkB : (k : WithTop Key) < r.begin.key · -- k belongs to the first filler obtain ⟨dbF1, hF1gt, hF1B, hF1len, hkF1⟩ := exists_dbF1_mem_crossFree (r := r) (res := res) (f := f) (k := k) (b := b) hne hb hf hroom' hkgt hkB obtain ⟨dbF2, hF2B, hF2E, hF2len⟩ := exists_dbF2_crossFree (r := r) (_res := res) (g := g) (b := b) (e := e) hb he hcap2 exact finish dbF1 dbF2 (List.mem_append.mpr (Or.inl hkF1)) hF1gt hF1B hF1len hF2B hF2E hF2len · -- k belongs to the second filler have hBk : r.begin.key ≤ (k : WithTop Key) := not_lt.mp hkB have hg1 : 1 ≤ g := by have hge : (1 : ℕ∞) ≤ intervalCard r.begin.key r.end_.key := by rw [intervalCard_eq_encard_keysIn, Set.one_le_encard_iff_nonempty] have hbk : b ≤ k := by rw [hb] at hBk; exact WithTop.coe_le_coe.mp hBk have hke : k < e := by rw [he] at hkE; exact WithTop.coe_lt_coe.mp hkE exact ⟨k, by rw [hb, he]; exact mem_keysIn_coe.mpr ⟨hbk, hke⟩⟩ have hcast : (1 : ℕ∞) ≤ ((intervalCard r.begin.key r.end_.key).toNat : ℕ∞) := by rwa [ENat.natCast_toNat (ne_of_lt hfin)] have hnat : 1 ≤ (intervalCard r.begin.key r.end_.key).toNat := by exact_mod_cast hcast rw [hgdef]; exact hnat obtain ⟨dbF1, hF1gt, hF1B, hF1len⟩ := exists_dbF1_crossFree (r := r) (res := res) (f := f) (b := b) hne hb hroom' obtain ⟨dbF2, hF2B, hF2E, hF2len, hkF2⟩ := exists_dbF2_mem_crossFree (r := r) (res := res) (g := g) (k := k) (b := b) (e := e) hb he hg1 hcap2 hBk hkE exact finish dbF1 dbF2 (List.mem_append.mpr (Or.inr hkF2)) hF1gt hF1B hF1len hF2B hF2E hF2len /-- In the clamping branch of the cross-free low-capacity gap cell, a key strictly below the reported head has an insertion witness. -/ theorem exists_witness_below_head_crossFree {r : RangeRead} {res : Result} {k : Key} (hread : Readable r res) (hcell : negCrossTruncNonposGapCrossFree r res) (hbot : clampNonposBottom r res) (hne : res.keys ≠ []) (hk : ((k : Key) : WithTop Key) < ((res.keys.head hne : Key) : WithTop Key)) : ∃ dbw : DB, RangeRead.Compatible dbw r res ∧ ¬ RangeRead.Compatible (toggle dbw k) r res := by classical have hcellKeep : negCrossTruncNonposGapCrossFree r res := hcell obtain ⟨hcell0, hB_le_E⟩ := hcell obtain ⟨hmore, hrev, hbegin, -, hcrossL, hend, hclamp, hlastB, hlastE, hEne, hcap⟩ := hcell0 obtain ⟨db₀, hcomp₀⟩ := hread have hsort : res.keys.SortedLT := RangeRead.compatible_sortedLT hcomp₀ hrev have hlim : RangeRead.withinLimit r res.keys := hcomp₀.1 obtain ⟨b, hb⟩ : ∃ b : Key, r.begin.key = ((b : Key) : WithTop Key) := by cases h : r.begin.key with | top => rw [h] at hB_le_E exact absurd (lt_of_le_of_lt hB_le_E hEne) (lt_irrefl _) | coe b => exact ⟨b, rfl⟩ obtain ⟨e, he⟩ : ∃ e : Key, r.end_.key = ((e : Key) : WithTop Key) := by cases h : r.end_.key with | top => exact absurd h (ne_of_lt hEne) | coe e => exact ⟨e, rfl⟩ have hlastD : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl have hhead_le_last : res.keys.head hne ≤ res.keys.getLast hne := (hsort.pairwise.imp le_of_lt).rel_getLast (List.head_mem hne) have hle_last : ∀ x ∈ res.keys, x ≤ res.keys.getLast hne := fun x hx => (hsort.pairwise.imp le_of_lt).rel_getLast hx have hlast_lt_B : ((res.keys.getLast hne : Key) : WithTop Key) < r.begin.key := by rw [← hlastD]; exact hlastB have hhead_lt_B : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key := lt_of_le_of_lt (WithTop.coe_le_coe.mpr hhead_le_last) hlast_lt_B have hk_lt_B : ((k : Key) : WithTop Key) < r.begin.key := lt_trans hk hhead_lt_B have hk_not_res : k ∉ res.keys := by intro hx exact absurd hk (not_lt.mpr (WithTop.coe_le_coe.mpr ((hsort.pairwise.imp le_of_lt).rel_head hx))) have hrep : reportedBelowBegin r res = res.keys.length := reportedBelowBegin_eq_length_of_last_lt hne hsort hlastB set g : ℕ := (intervalCard r.begin.key r.end_.key).toNat with hgdef have hg_le : g ≤ clampNonposD r := crossFree_g_le hcellKeep set f : ℕ := clampNonposD r + 1 - g with hfdef have hf : 1 ≤ f := by rw [hfdef]; omega have hroom := intervalCard_begin_key_ge_of_crossFree hcomp₀ hcellKeep hne have hroom' : (f : ℕ∞) ≤ intervalCard (((keyAfter (res.keys.getLast hne)) : Key) : WithTop Key) r.begin.key := by rw [hfdef]; exact hroom have hfin : intervalCard r.begin.key r.end_.key < (⊤ : ℕ∞) := by have hcap' : intervalCard r.begin.key r.end_.key < ((clampNonposD r + 1 : ℕ) : ℕ∞) := by rcases hcap with hcrosslt | hlt · exact absurd hcrosslt (not_lt.mpr hB_le_E) · exact hlt exact lt_of_lt_of_le hcap' (by simp) have hcap2 : (g : ℕ∞) ≤ intervalCard r.begin.key r.end_.key := by rw [hgdef, ENat.natCast_toNat (ne_of_lt hfin)] -- clamping gives `t + f ≤ beginSlack` have hcount : res.keys.length + f ≤ beginSlack r := by have h := hbot unfold clampNonposBottom at h rw [hrep] at h have hsub : (((clampNonposD r + 1 : ℕ) : ℕ∞) - (g : ℕ∞)) = (f : ℕ∞) := by rw [hfdef] exact (ENat.natCast_sub (clampNonposD r + 1) g).symm -- replace the cast capacity by `g` have hgcast : ((intervalCard r.begin.key r.end_.key).toNat : ℕ∞) = intervalCard r.begin.key r.end_.key := ENat.natCast_toNat (ne_of_lt hfin) rw [← hgcast, ← hgdef] at h rw [hsub] at h exact_mod_cast h obtain ⟨dbF1, hF1gt, hF1B, hF1len⟩ := exists_dbF1_crossFree (r := r) (res := res) (f := f) (b := b) hne hb hroom' obtain ⟨dbF2, hF2B, hF2E, hF2len⟩ := exists_dbF2_crossFree (r := r) (_res := res) (g := g) (b := b) (e := e) hb he hcap2 have hF1len' : dbF1.keys.length = clampNonposD r + 1 - g := by rw [hF1len, hfdef] have hanc0 : res.keys.length + (clampNonposD r + 1 - g) ≤ beginSlack r + 1 := by rw [hfdef] at hcount; omega obtain ⟨dbw, hkeyw, hcompw, hanchorE, hanchorB⟩ := exists_padDb_crossFree hsort hrev hmore hne hlim hbegin hend hB_le_E hEne hlastB hg_le hF1gt hF1B hF1len' hF2B hF2E hF2len hanc0 -- the toggled database inserts `k` at the front have hk_lt_all : ∀ x ∈ dbw.keys, k < x := by intro x hx rw [hkeyw] at hx rcases List.mem_append.mp hx with hx | hx · rcases List.mem_append.mp hx with hx | hx · exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le hk (WithTop.coe_le_coe.mpr ((hsort.pairwise.imp le_of_lt).rel_head hx))) · exact lt_trans (lt_of_lt_of_le (WithTop.coe_lt_coe.mp hk) hhead_le_last) (hF1gt x hx) · exact lt_trans (lt_of_lt_of_le (WithTop.coe_lt_coe.mp hk) hhead_le_last) (WithTop.coe_lt_coe.mp (lt_of_lt_of_le hlast_lt_B (hF2B x hx) : ((res.keys.getLast hne : Key) : WithTop Key) < ((x : Key) : WithTop Key))) have hk_not_dbw : k ∉ dbw.keys := fun hx => absurd (hk_lt_all k hx) (lt_irrefl k) refine ⟨dbw, hcompw, ?_⟩ rw [toggle_eq_insert_of_not_mem hk_not_dbw] intro hcomp' have hdbw_ne : dbw.keys ≠ [] := by rw [hkeyw, List.append_assoc]; exact List.append_ne_nil_of_left_ne_nil hne _ have hins_keys : (dbw.insert k hk_not_dbw).keys = k :: dbw.keys := by rw [DB.insert_keys] cases hkw : dbw.keys with | nil => exact absurd hkw hdbw_ne | cons a t => have hka : k ≤ a := le_of_lt (hk_lt_all a (by rw [hkw]; exact List.mem_cons_self ..)) rw [List.orderedInsert_cons_of_le (r := (· ≤ ·)) (a := k) (b := a) t hka] obtain ⟨-, hfilt'⟩ := (compatible_iff_truncated_keys hrev hmore hne).mp hcomp' -- count below begin of the padded database have hrescnt : dbw.keys.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = res.keys.length + f := by rw [hkeyw, List.countP_append, List.countP_append] have h1 : res.keys.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = res.keys.length := by rw [List.countP_eq_length] intro x hx rw [decide_eq_true_eq] exact lt_of_le_of_lt (WithTop.coe_le_coe.mpr (hle_last x hx)) hlast_lt_B have h2 : dbF1.keys.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = dbF1.keys.length := by rw [List.countP_eq_length] intro x hx rw [decide_eq_true_eq] exact hF1B x hx have h3 : dbF2.keys.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = 0 := by rw [List.countP_eq_zero] intro x hx rw [decide_eq_true_eq, not_lt] exact hF2B x hx rw [h1, h2, h3, hF1len]; omega have hcount_ins : (dbw.insert k hk_not_dbw).keys.countP (fun x : Key => decide ((x : WithTop Key) < r.begin.key)) = res.keys.length + f + 1 := by rw [hins_keys, List.countP_cons, decide_eq_true_eq.mpr hk_lt_B, ite_eq_left rfl, hrescnt] have hanchor_ins : r.begin.anchor (dbw.insert k hk_not_dbw) ≤ 0 := by rw [anchor_eq_count_sub_slack _ r (le_of_lt hbegin), hcount_ins] have hcast : (res.keys.length + f : ℤ) ≤ (beginSlack r : ℤ) := by exact_mod_cast hcount push_cast; omega have hk_ck : k ∈ RangeRead.completeKeys (dbw.insert k hk_not_dbw) r := by rw [RangeRead.mem_completeKeys] refine ⟨by rw [hins_keys]; exact List.mem_cons_self .., ?_, ?_⟩ · by_cases hneg : r.begin.anchor (dbw.insert k hk_not_dbw) < 0 · rw [resolve_eq_nil hneg] exact WithTop.coe_le_coe.mpr (nil_le_key k) · have hzero : r.begin.anchor (dbw.insert k hk_not_dbw) = 0 := by omega have h0 : 0 ≤ r.begin.anchor (dbw.insert k hk_not_dbw) := by omega have hlt : (r.begin.anchor (dbw.insert k hk_not_dbw)).toNat < (dbw.insert k hk_not_dbw).keys.length := by rw [hzero, hins_keys, List.length_cons]; simp rw [resolve_eq_getElem h0 hlt] have hget : (dbw.insert k hk_not_dbw).keys[(r.begin.anchor (dbw.insert k hk_not_dbw)).toNat] = k := by simp only [hzero, hins_keys] rfl rw [hget] · have hpre := RangeRead.compatible_keys_prefix hcomp' have hhead_mem : res.keys.head hne ∈ RangeRead.completeKeys (dbw.insert k hk_not_dbw) r := hpre.subset (List.head_mem hne) exact lt_trans hk (RangeRead.mem_completeKeys.mp hhead_mem).2.2 have hk_le_last : k ≤ res.keys.getLast hne := le_trans (le_of_lt (WithTop.coe_lt_coe.mp hk)) hhead_le_last have hk_filt : k ∈ (RangeRead.completeKeys (dbw.insert k hk_not_dbw) r).filter (fun x : Key => decide (x ≤ res.keys.getLast hne)) := by rw [List.mem_filter] exact ⟨hk_ck, by rw [decide_eq_true_eq]; exact hk_le_last⟩ rw [hfilt'] at hk_filt exact hk_not_res hk_filt /-- The default head of a list is its head. -/ theorem list_headD_eq_head {l : List Key} (h : l ≠ []) : l.headD ([] : Key) = l.head h := by revert h cases l with | nil => intro h; exact absurd rfl h | cons a t => intro h; rfl /-- **Minimality of the cross-free nonpositive-end gap closed form.** Both branches of `closedFormNegCrossTruncNonposGapCrossFree` are sound, and every key strictly below `end_.key` is necessary: reported keys by their membership, keys between the reported head and last by convexity, keys above the last by the erasing padding witness, and (in the clamping branch) keys below the head by the front insertion witness. -/ theorem minimal_closedForm_of_negCross_trunc_nonposGap_crossFree {r : RangeRead} {res : Result} (hread : Readable r res) (hcell : negCrossTruncNonposGapCrossFree r res) : Minimal r res (closedFormNegCrossTruncNonposGapCrossFree r res) := by classical have hcellKeep : negCrossTruncNonposGapCrossFree r res := hcell obtain ⟨hcell0, hB_le_E⟩ := hcell obtain ⟨hmore, hrev, hbegin, hne, hcrossL, hend, hclamp, hlastB, hlastE, hEne, hcap⟩ := hcell0 have hhead_lt_B : ((res.keys.head hne : Key) : WithTop Key) < r.begin.key := by have hle : leastReported r res = res.keys.head hne := by simp [leastReported, hrev, List.head?_eq_some_head hne] rwa [hle] at hcrossL by_cases hbot : clampNonposBottom r res · have hclosed : closedFormNegCrossTruncNonposGapCrossFree r res = (⟨(([] : Key) : WithTop Key), r.end_.key⟩ : ConflictRange) := by unfold closedFormNegCrossTruncNonposGapCrossFree closedFormNegCrossTruncNonposGap rw [ite_eq_left hbot, max_eq_right hB_le_E] rw [hclosed] refine minimal_iff_sound_and_necessaryRange.mpr ⟨sound_bottomEnd_crossFree hbegin hend hB_le_E, ?_⟩ intro k _ hkE by_cases hkres : k ∈ res.keys · exact necessary_of_mem_result hread hkres · by_cases hkhead : ((k : Key) : WithTop Key) < ((res.keys.head hne : Key) : WithTop Key) · obtain ⟨dbw, hcompw, hnot⟩ := exists_witness_below_head_crossFree hread hcellKeep hbot hne hkhead exact necessary_of_toggle ⟨dbw, hcompw, hnot⟩ · have hheadk : ((res.keys.head hne : Key) : WithTop Key) ≤ (k : WithTop Key) := not_lt.mp hkhead by_cases hklast : ((k : Key) : WithTop Key) ≤ ((res.keys.getLast hne : Key) : WithTop Key) · exact necessary_of_between_result hread (List.head_mem hne) (List.getLast_mem hne) (WithTop.coe_le_coe.mp hheadk) (WithTop.coe_le_coe.mp hklast) · have hlastk : ((res.keys.getLast hne : Key) : WithTop Key) < (k : WithTop Key) := not_le.mp hklast obtain ⟨dbw, hcompw, hkdbw, hnot⟩ := exists_witness_last_end_crossFree hread hcellKeep hne hlastk hkE exact necessary_of_toggle ⟨dbw, hcompw, by rw [toggle_eq_erase_of_mem hkdbw]; exact hnot⟩ · have hclosed : closedFormNegCrossTruncNonposGapCrossFree r res = (⟨((res.keys.head hne : Key) : WithTop Key), r.end_.key⟩ : ConflictRange) := by have hheadD : res.keys.headD ([] : Key) = res.keys.head hne := list_headD_eq_head hne unfold closedFormNegCrossTruncNonposGapCrossFree closedFormNegCrossTruncNonposGap rw [ite_eq_right hbot, max_eq_right hB_le_E] exact congrArg (fun k : WithTop Key => (⟨k, r.end_.key⟩ : ConflictRange)) (congrArg (fun k : Key => ((k : Key) : WithTop Key)) hheadD) rw [hclosed] refine minimal_iff_sound_and_necessaryRange.mpr ⟨sound_headEnd_crossFree hrev hmore hne hbegin hhead_lt_B hclamp hbot hend hB_le_E, ?_⟩ intro k hklo hkE by_cases hkres : k ∈ res.keys · exact necessary_of_mem_result hread hkres · by_cases hklast : ((k : Key) : WithTop Key) ≤ ((res.keys.getLast hne : Key) : WithTop Key) · exact necessary_of_between_result hread (List.head_mem hne) (List.getLast_mem hne) (WithTop.coe_le_coe.mp hklo) (WithTop.coe_le_coe.mp hklast) · have hlastk : ((res.keys.getLast hne : Key) : WithTop Key) < (k : WithTop Key) := not_le.mp hklast obtain ⟨dbw, hcompw, hkdbw, hnot⟩ := exists_witness_last_end_crossFree hread hcellKeep hne hlastk hkE exact necessary_of_toggle ⟨dbw, hcompw, by rw [toggle_eq_erase_of_mem hkdbw]; exact hnot⟩ end FormalConflictRange