import Normalization import Bridges import Reserved namespace KKFiniteCoreProof open KKFiniteCoreDraft lemma next_survivor (S : Finset Nat) (s : Nat) (hS : PrimeFamily S) (hs : Survivor S s) : ∃ d, Consecutive S s d := by classical have hex : ∃ d, 0 < d ∧ Survivor S (s+d) := by obtain ⟨d, hd, h⟩ := survivor_in_each_period_window S s hS exact ⟨d, (Finset.mem_Icc.mp hd).1, h⟩ refine ⟨Nat.find hex, (Nat.find_spec hex).1, hs, (Nat.find_spec hex).2, ?_⟩ intro i hi hid hn exact Nat.find_min hex hid ⟨hi, hn⟩ lemma consecutive_mod (S : Finset Nat) (s d : Nat) : Consecutive S s d ↔ Consecutive S (s % period S) d := by have h (i : Nat) : Survivor S (s+i) ↔ Survivor S (s % period S+i) := survivor_congr S ((Nat.mod_modEq s (period S)).symm.add (Nat.ModEq.refl i)) unfold Consecutive rw [← survivor_congr S (Nat.mod_modEq s (period S)), h d] simp_rw [h] theorem cyclic_gap_set_nonempty : Target_cyclic_gap_set_nonempty := by classical intro S hS obtain ⟨d, hd⟩ := next_survivor S (period S-1) hS (canonical_survivor S hS) refine ⟨d, Finset.mem_filter.mpr ⟨Finset.mem_Icc.mpr ⟨hd.1, consecutive_distance_bounded S _ _ hS hd⟩, ?_⟩⟩ exact ⟨period S-1, Finset.mem_range.mpr (by have := period_pos S hS; omega), hd⟩ theorem G2_attained_and_bounds : Target_G2_attained_and_bounds := by classical intro S hS have hm : G2 S ∈ cyclicGapDistances S := by have h := Finset.sup_mem_of_nonempty (f := id) (cyclic_gap_set_nonempty S hS) simpa [G2] using h exact ⟨(Finset.mem_Icc.mp (Finset.mem_filter.mp hm).1).1, (Finset.mem_Icc.mp (Finset.mem_filter.mp hm).1).2, (Finset.mem_filter.mp hm).2⟩ theorem all_consecutive_distances_le_G2 : Target_all_consecutive_distances_le_G2 := by classical intro S s d hS hd apply Finset.le_sup (f := id) exact Finset.mem_filter.mpr ⟨Finset.mem_Icc.mpr ⟨hd.1, consecutive_distance_bounded S s d hS hd⟩, ⟨s % period S, Finset.mem_range.mpr (Nat.mod_lt _ (period_pos S hS)), (consecutive_mod S s d).mp hd⟩⟩ theorem excluded_block_bound : Target_excluded_block_bound := by classical intro S s m hS hblock let t := s + period S have shifted : ExcludedBlock S t m := by intro i hi hn apply hblock i hi apply (survivor_periodic S (s+i) hS).mp simpa [t, Nat.add_assoc, Nat.add_comm, Nat.add_left_comm] using hn let A := (Finset.range (t+1)).filter (Survivor S) have hA : A.Nonempty := by refine ⟨period S-1, Finset.mem_filter.mpr ⟨Finset.mem_range.mpr ?_, canonical_survivor S hS⟩⟩ dsimp [t] omega let l := A.max' hA have hlmem : l ∈ A := Finset.max'_mem A hA have hlt : l ≤ t := by have := Finset.mem_range.mp (Finset.mem_filter.mp hlmem).1 omega have hls : Survivor S l := (Finset.mem_filter.mp hlmem).2 obtain ⟨d, hd⟩ := next_survivor S l hS hls have hright : t < l+d := by by_contra hn have hmem : l+d ∈ A := Finset.mem_filter.mpr ⟨Finset.mem_range.mpr (by omega), hd.2.2.1⟩ have hle : l+d ≤ l := Finset.le_max' A (l+d) hmem have := hd.1 omega have hdist : m+1 ≤ d := by by_contra hn have hi : l+d-t ∈ Finset.Icc 1 m := Finset.mem_Icc.mpr (by omega) have hs := shifted (l+d-t) hi have he : t+(l+d-t) = l+d := by omega rw [he] at hs exact hs hd.2.2.1 exact hdist.trans (all_consecutive_distances_le_G2 S l d hS hd) theorem exists_block_iff_gap_bound : Target_exists_block_iff_gap_bound := by intro S m hS constructor · rintro ⟨s, _, hs⟩ exact excluded_block_bound S s m hS hs · intro hm obtain ⟨_, _, s, hs, hc⟩ := G2_attained_and_bounds S hS refine ⟨s, Finset.mem_range.mp hs, ?_⟩ intro i hi obtain ⟨hi1, him⟩ := Finset.mem_Icc.mp hi exact hc.2.2.2 i hi1 (by omega) theorem cover_iff_gap_bound : Target_cover_iff_gap_bound := by intro S m hS exact (exists_cover_iff_exists_block S m hS).trans (exists_block_iff_gap_bound S m hS) theorem completion_implies_gap_bound : Target_completion_implies_gap_bound := by intro S R a m hS hd hc obtain ⟨b, _, _, hb⟩ := reserved_completion S R a m hd hc exact (cover_iff_gap_bound (S ∪ R) m hS).mp ⟨b, hb⟩ #print axioms cyclic_gap_set_nonempty #print axioms G2_attained_and_bounds #print axioms all_consecutive_distances_le_G2 #print axioms excluded_block_bound #print axioms exists_block_iff_gap_bound #print axioms cover_iff_gap_bound #print axioms completion_implies_gap_bound end KKFiniteCoreProof