OAI/NumberTheory/Ostmann/ZeroDensity/DensityDefectSelection.lean

GitHub source file

4 declarations, 0 contain sorry, 0 declared as axioms

Small collision defect forces balanced supports and accurate tests

  1. theorem OAI.Ostmann.reciprocal_gap_forces_thirds line 12
  2. theorem OAI.Ostmann.small_defect_balances_supports line 34
  3. theorem OAI.Ostmann.small_defect_controls_test_errors line 46
  4. theorem OAI.Ostmann.weighted_cost_exception_bound line 62

    Source documentation

    Weighted Markov bound, used with cost p * collisionDefect.

    theorem weighted_cost_exception_bound (P : Finset ℕ) (w cost : ℕ → ℝ) (δ : ℝ)
    (hw : ∀ p ∈ P, 0 ≤ w p) (hcost : ∀ p ∈ P, 0 ≤ cost p) :
    δ * (∑ p ∈ P.filter (fun p => δ < cost p), w p) ≤ ∑ p ∈ P, w p * cost p := by
…