Skip to main content
AlexKontorovich/PrimeNumberTheoremAnd
Source indexedlemma · leanprover/lean4:v4.32.0

Erdos392.Factorization.lower_score_3_case2b

PrimeNumberTheoremAnd.IEANTN.Erdos392 · PrimeNumberTheoremAnd/IEANTN/Erdos392.lean:798 to 819

Source documentation

Case 2b of lower_score_3: If L ≤ n and the product of deficit primes is > n, we can find a submultiset to add that reduces the score.

Exact Lean statement

lemma Factorization.lower_score_3_case2b {n : ℕ} (f : Factorization n) (L : ℕ)
    (h_surplus : ∀ p, f.balance p ≤ 0)
    (hf : ∃ p ∈ (n + 1).primesBelow, p ≤ L ∧ f.balance p < 0)
    (h_prod : n < (deficitMultiset f L).prod)
    (hL_le_n : L ≤ n) :
    ∃ f' : Factorization n,
      f'.total_imbalance < f.total_imbalance ∧ f'.score L ≤ f.score L

Complete declaration

Lean source

Canonical source
Full Lean sourceLean 4
lemma Factorization.lower_score_3_case2b {n : } (f : Factorization n) (L : )    (h_surplus :  p, f.balance p  0)    (hf :  p  (n + 1).primesBelow, p  L  f.balance p < 0)    (h_prod : n < (deficitMultiset f L).prod)    (hL_le_n : L  n) :     f' : Factorization n,      f'.total_imbalance < f.total_imbalance  f'.score L  f.score L := by  obtain p₀, hp₀_mem, hp₀_le, hp₀_bal := hf  have hp₀ := prime_of_mem_primesBelow hp₀_mem  obtain M, hM_sub, hM_lb, hM_ub := exists_submultiset_prod_between (deficitMultiset f L)    (hp₀.pos.trans_le hp₀_le) ((hp₀.pos.trans_le hp₀_le).trans_le hL_le_n)      (fun p hp  (mem_deficitMultiset f L p hp).2) h_prod  refine addFactor f M.prod hM_ub (pos_of_ne_zero fun h  by grind), ?_, ?_  · have h_imb := addFactor_submultiset_total_imbalance f L h_surplus M hM_sub      M.prod hM_ub (pos_of_ne_zero fun h  by grind) rfl    refine h_imb ▸ sub_lt ?_ <| card_pos.mpr (by grind)    exact pos_of_ne_zero fun h       hp₀_bal.ne <| by        have := sum_eq_zero_iff.mp h _ hp₀_mem        grind  · exact score_le_of_add_submultiset f L M hM_sub M.prod hM_ub (by grind) rfl hM_lb      (card_pos.mpr (by grind)) <| hp₀.two_le.trans hp₀_le