import Erdos1135.Tao.Density.FiniteLogCountUnion import Erdos1135.Tao.Section3.ForwardWindowMultiplicity /-! # Uniform Odd Syracuse Bad-Set Cover The bounded Section 3 trace supplies a no-hit estimate on each active seed-forward window. This leaf proves that the inclusively rounded windows cover the required ambient prefix and combines their estimates using the multiplicity-two mass bound. -/ namespace Erdos1135 namespace Tao open scoped BigOperators noncomputable section theorem logCount_odd_syracuseBad_eq_zero_of_le {B X : ℕ} (hXB : X ≤ B) : logCount {N : ℕ | Odd N ∧ ¬ syracuseHitsAtMost N B} X = 0 := by classical unfold logCount refine Finset.sum_eq_zero fun i hi => ?_ have hiB : i + 1 ≤ B := by have hiX : i + 1 ≤ X := Nat.succ_le_of_lt (Finset.mem_range.mp hi) exact hiX.trans hXB have hhit : syracuseHitsAtMost (i + 1) B := ⟨0, by simpa only [Function.iterate_zero, id_eq] using hiB⟩ have hnot : i + 1 ∉ {N : ℕ | Odd N ∧ ¬ syracuseHitsAtMost N B} := fun hbad => hbad.2 hhit simp only [hnot, if_false] theorem oddLogWindowSet_union_eq_of_join {lo₁ hi₁ lo₂ hi₂ : ℕ} (hlo : lo₁ ≤ lo₂) (hhi : hi₁ ≤ hi₂) (hjoin : lo₂ ≤ hi₁ + 1) : oddLogWindowSet lo₁ hi₁ ∪ oddLogWindowSet lo₂ hi₂ = oddLogWindowSet lo₁ hi₂ := by ext n constructor · rintro (hn | hn) · rw [oddLogWindowSet_mem] at hn ⊢ exact ⟨hn.1, hn.2.1.trans hhi, hn.2.2⟩ · rw [oddLogWindowSet_mem] at hn ⊢ exact ⟨hlo.trans hn.1, hn.2⟩ · intro hn rw [oddLogWindowSet_mem] at hn by_cases hnhi : n ≤ hi₁ · exact Or.inl (oddLogWindowSet_mem.mpr ⟨hn.1, hnhi, hn.2.2⟩) · exact Or.inr (oddLogWindowSet_mem.mpr ⟨hjoin.trans (by omega), hn.2⟩) private theorem forwardWindowSet_biUnion_range_succ {y : ℝ} (hy : 1 ≤ y) (L : ℕ) : (⋃ m ∈ Finset.range (L + 1), taoSection3ForwardWindowSet y m) = oddLogWindowSet (taoNyLo (taoSection3ForwardScale y 0)) (Nat.floor (taoSection3ForwardScale y (L + 1))) := by induction L with | zero => simp [taoSection3ForwardWindowSet, taoSection3ForwardWindow_hi_eq_floor_next (zero_le_one.trans hy)] | succ L ih => have hunion : (⋃ m ∈ Finset.range (L + 1 + 1), taoSection3ForwardWindowSet y m) = (⋃ m ∈ Finset.range (L + 1), taoSection3ForwardWindowSet y m) ∪ taoSection3ForwardWindowSet y (L + 1) := by ext n constructor · intro hn rcases Set.mem_iUnion.mp hn with ⟨m, hmUnion⟩ rcases Set.mem_iUnion.mp hmUnion with ⟨hmRange, hnWindow⟩ by_cases hm : m < L + 1 · exact Or.inl (Set.mem_iUnion.mpr ⟨m, Set.mem_iUnion.mpr ⟨Finset.mem_range.mpr hm, hnWindow⟩⟩) · have hmEq : m = L + 1 := by have := Finset.mem_range.mp hmRange omega exact Or.inr (hmEq ▸ hnWindow) · rintro (hn | hn) · rcases Set.mem_iUnion.mp hn with ⟨m, hmUnion⟩ rcases Set.mem_iUnion.mp hmUnion with ⟨hmRange, hnWindow⟩ exact Set.mem_iUnion.mpr ⟨m, Set.mem_iUnion.mpr ⟨Finset.mem_range.mpr (lt_trans (Finset.mem_range.mp hmRange) (by omega)), hnWindow⟩⟩ · exact Set.mem_iUnion.mpr ⟨L + 1, Set.mem_iUnion.mpr ⟨Finset.mem_range.mpr (by omega), hn⟩⟩ have hlo : taoNyLo (taoSection3ForwardScale y 0) ≤ taoNyLo (taoSection3ForwardScale y (L + 1)) := by unfold taoNyLo exact Nat.ceil_mono (taoSection3ForwardScale_monotone hy (Nat.zero_le _)) have hhi : Nat.floor (taoSection3ForwardScale y (L + 1)) ≤ Nat.floor (taoSection3ForwardScale y (L + 1 + 1)) := Nat.floor_mono (taoSection3ForwardScale_monotone hy (by omega)) have hjoin : taoNyLo (taoSection3ForwardScale y (L + 1)) ≤ Nat.floor (taoSection3ForwardScale y (L + 1)) + 1 := by unfold taoNyLo exact Nat.ceil_le_floor_add_one _ rw [hunion, ih] simpa [taoSection3ForwardWindowSet, taoSection3ForwardWindow_hi_eq_floor_next (zero_le_one.trans hy), Nat.add_assoc] using (oddLogWindowSet_union_eq_of_join hlo hhi hjoin) /-- The `j + 2` active seed-forward windows form the exact inclusive odd window from the rounded seed up to the ambient natural endpoint. -/ theorem taoSection3AmbientActiveWindowSet_biUnion_eq {X : ℕ} (hX : 1 ≤ X) (j : ℕ) : (⋃ m ∈ Finset.range (j + 2), taoSection3ForwardWindowSet (taoSection3AmbientBoundary (X : ℝ) (j + 2)) m) = oddLogWindowSet (taoNyLo (taoSection3AmbientBoundary (X : ℝ) (j + 2))) X := by have hy : 1 ≤ taoSection3AmbientBoundary (X : ℝ) (j + 2) := taoSection3AmbientBoundary_one_le (by exact_mod_cast hX) (j + 2) have hchain := forwardWindowSet_biUnion_range_succ hy (j + 1) rw [taoSection3AmbientForwardScale_top (Nat.cast_nonneg X) j] at hchain simpa [taoSection3ForwardScale, Nat.add_assoc] using hchain theorem logCount_syracuseNoHitAtMost_inter_ambientForwardWindow_le {B X j m : ℕ} {eps : ℝ} (hX : 1 ≤ X) (hm : m < j + 2) (hmass : 0 < logFinsetMass (taoSection3ForwardWindow (taoSection3AmbientBoundary (X : ℝ) (j + 2)) m)) (hprob : syracuseNoHitWindowProb B (taoNyLo (taoSection3ForwardScale (taoSection3AmbientBoundary (X : ℝ) (j + 2)) m)) (taoNyHi (taoSection3ForwardScale (taoSection3AmbientBoundary (X : ℝ) (j + 2)) m) taoAlpha) hmass ≤ eps) : logCount (syracuseNoHitAtMost B ∩ taoSection3ForwardWindowSet (taoSection3AmbientBoundary (X : ℝ) (j + 2)) m) X ≤ eps * logCount (taoSection3ForwardWindowSet (taoSection3AmbientBoundary (X : ℝ) (j + 2)) m) X := by let y := taoSection3AmbientBoundary (X : ℝ) (j + 2) have hy : 1 ≤ y := by dsimp only [y] exact taoSection3AmbientBoundary_one_le (by exact_mod_cast hX) (j + 2) have hhiX : taoNyHi (taoSection3ForwardScale y m) taoAlpha ≤ X := by have htop := taoSection3ForwardWindow_hi_le_top hy hm dsimp only [y] at htop rw [taoSection3AmbientForwardScale_top (Nat.cast_nonneg X) j] at htop simpa using htop have hlocal := logCount_noHitWindow_le_of_prob_le hmass hprob change logCount (syracuseNoHitAtMost B ∩ taoSection3ForwardWindowSet y m) X ≤ eps * logCount (taoSection3ForwardWindowSet y m) X unfold taoSection3ForwardWindowSet rw [logCount_eq_of_subset_Iic_of_le (Set.Subset.trans Set.inter_subset_right (oddLogWindowSet_subset_Iic (taoNyLo (taoSection3ForwardScale y m)) (taoNyHi (taoSection3ForwardScale y m) taoAlpha))) hhiX, logCount_eq_of_subset_Iic_of_le (oddLogWindowSet_subset_Iic (taoNyLo (taoSection3ForwardScale y m)) (taoNyHi (taoSection3ForwardScale y m) taoAlpha)) hhiX] simpa only [y] using hlocal /-- Checked Section 3 output: for every sufficiently large target `B`, the odd Syracuse non-hitting set has a polynomially small logarithmic mass in every finite prefix, including prefixes below `B`. -/ theorem exists_taoSection3UniformOddBadMass_checked : ∃ D c : ℝ, ∃ Bstar : ℕ, 0 ≤ D ∧ 0 < c ∧ 2 ≤ Bstar ∧ ∀ {B : ℕ}, Bstar ≤ B → ∀ X : ℕ, logCount {N : ℕ | Odd N ∧ ¬ syracuseHitsAtMost N B} X ≤ D * (Real.log (B : ℝ)) ^ (-c) * logCount {N : ℕ | Odd N} X := by rcases exists_taoSection3AmbientGeometricBudget_checked with ⟨Ctrace, c, Bstar, hCtrace, hc, hBstar, hbudget⟩ refine ⟨2 * Ctrace, c, Bstar, by positivity, hc, hBstar, ?_⟩ intro B hBBstar X have hBtwo : 2 ≤ B := hBstar.trans hBBstar have hlogB : 0 ≤ Real.log (B : ℝ) := Real.log_nonneg (by exact_mod_cast (show 1 ≤ B by omega)) by_cases hXB : X ≤ B · rw [logCount_odd_syracuseBad_eq_zero_of_le hXB] exact mul_nonneg (mul_nonneg (mul_nonneg (by positivity) hCtrace) (Real.rpow_nonneg hlogB _)) (logCount_nonneg {N : ℕ | Odd N} X) · have hBX : B < X := Nat.lt_of_not_ge hXB have hXone : 1 < X := by omega rcases hbudget hBBstar (X := (X : ℝ)) (by exact_mod_cast hBX) with ⟨j, hseed, _hterminal, hpartial⟩ let y := taoSection3AmbientBoundary (X : ℝ) (j + 2) have hy : 1 < y := by dsimp only [y, taoSection3AmbientBoundary] exact Real.one_lt_rpow (by exact_mod_cast hXone) (pow_pos taoSection3AmbientRatio_pos (j + 2)) have hyB : y ≤ (B : ℝ) := (taoSection3ForwardScale_seed_le hy.le 1).trans hseed have hloB : taoNyLo y ≤ B := by unfold taoNyLo exact Nat.ceil_le.mpr hyB let eta : ℝ := Ctrace * (Real.log (B : ℝ)) ^ (-c) have heta : 0 ≤ eta := by dsimp only [eta] exact mul_nonneg hCtrace (Real.rpow_nonneg hlogB _) let I := Finset.range (j + 2) let W : ℕ → Set ℕ := fun m => taoSection3ForwardWindowSet y m let E : ℕ → Set ℕ := fun m => syracuseNoHitAtMost B ∩ W m have hcover : ∀ N : ℕ, N ≤ X → N ∈ {N : ℕ | Odd N ∧ ¬ syracuseHitsAtMost N B} → ∃ m ∈ I, N ∈ E m := by intro N hNX hbad have hloN : taoNyLo y ≤ N := by by_contra hloN have hNB : N ≤ B := by have : N < taoNyLo y := Nat.lt_of_not_ge hloN omega exact hbad.2 ⟨0, by simpa only [Function.iterate_zero, id_eq] using hNB⟩ have hchain := taoSection3AmbientActiveWindowSet_biUnion_eq (X := X) hXone.le j have hnWindow : N ∈ oddLogWindowSet (taoNyLo y) X := oddLogWindowSet_mem.mpr ⟨hloN, hNX, Nat.odd_iff.mp hbad.1⟩ have hnUnion : N ∈ ⋃ m ∈ I, W m := by dsimp only [I, W] rw [hchain] simpa only [y] using hnWindow rcases Set.mem_iUnion.mp hnUnion with ⟨m, hmUnion⟩ rcases Set.mem_iUnion.mp hmUnion with ⟨hmI, hmWindow⟩ refine ⟨m, hmI, ?_⟩ exact ⟨by simpa only [syracuseNoHitAtMost] using hbad.2, hmWindow⟩ have hlocal : ∀ m ∈ I, logCount (E m) X ≤ eta * logCount (W m) X := by intro m hmI have hm : m < j + 2 := Finset.mem_range.mp hmI have hmle : m ≤ j + 1 := by omega rcases hpartial m hmle with ⟨hmass, hprob⟩ exact logCount_syracuseNoHitAtMost_inter_ambientForwardWindow_le (B := B) (X := X) (j := j) (m := m) (eps := eta) hXone.le hm hmass hprob have hmass := sum_logFinsetMass_taoSection3AmbientActiveWindow_nat_le_two_logCount_odd hXone j calc logCount {N : ℕ | Odd N ∧ ¬ syracuseHitsAtMost N B} X ≤ ∑ m ∈ I, logCount (E m) X := logCount_le_finset_sum_of_prefix_cover I E _ X hcover _ ≤ ∑ m ∈ I, eta * logCount (W m) X := by exact Finset.sum_le_sum fun m hmI => hlocal m hmI _ = eta * ∑ m ∈ I, logCount (W m) X := by rw [Finset.mul_sum] _ = eta * ∑ m ∈ Finset.range (j + 2), logFinsetMass (taoSection3ForwardWindow y m) := by congr 1 dsimp only [I, W] apply Finset.sum_congr rfl intro m hm exact logCount_taoSection3AmbientActiveWindowSet_eq_mass hXone.le j (Finset.mem_range.mp hm) _ ≤ eta * (2 * logCount {N : ℕ | Odd N} X) := mul_le_mul_of_nonneg_left hmass heta _ = (2 * Ctrace) * (Real.log (B : ℝ)) ^ (-c) * logCount {N : ℕ | Odd N} X := by dsimp only [eta] ring end end Tao end Erdos1135