AFTD Auto-Formalizing Theoretical Domains

bh_upper_density_ge_of_subsequence

theoremverified

If a set A has normalized counting function at least c along a strictly increasing sequence of checkpoints, and the normalized counting function is bounded from above, then its normalized upper density is at least c.

Statement

theorem bh_upper_density_ge_of_subsequence (h : ℕ) (A : Set ℕ) (x : ℕ → ℕ)
    (hx : ∀ k, x k < x (k + 1)) (c : ℝ)
    (h_bd : Filter.IsBoundedUnder (· ≤ ·) Filter.atTop (fun n : ℕ => ((bh_counting A n : ℝ)) / ((n : ℝ) ^ ((1 : ℝ) / (h : ℝ)))))
    (hc : ∀ k, c ≤ ((bh_counting A (x k) : ℝ)) / ((x k : ℝ) ^ ((1 : ℝ) / (h : ℝ)))) :
    c ≤ bh_upper_density h A
Source
step towards op_939_optimal_upper_density_strictly_greater
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • bh_countingFor a set of natural numbers A and a positive integer n, A(n) is the cardinality of A ∩ {1, ..., n}.
  • bh_upper_densityFor a set of natural numbers A and order h, the normalized upper density is the limit superior along atTop of |A ∩ {1, ..., n}| / n^(1/h)…

The proof, explained

To show that the normalized upper density is at least c, the argument shows that the normalized counting function is frequently at least c as n → ∞. Since the sequence of checkpoints x is strictly increasing, it tends to infinity, which guarantees that for any threshold a there exists a checkpoint x(K) ≥ a where the ratio is at least c. Because the normalized counting function is bounded from above, holding frequently at least c implies that its limit superior—the normalized upper density—is at least c.

  1. The checkpoint sequence x is strictly increasing.

    By assumption hx, x(k) < x(k + 1) for all k. By strictMono_nat_of_lt_succ, this pointwise successor inequality implies that x is strictly monotone on ℕ.

    line 7

    uses strictMono_nat_of_lt_succ

      have hmono : StrictMono x := strictMono_nat_of_lt_succ hx
  2. The normalized counting function is frequently at least c along Filter.atTop.

    By Filter.frequently_atTop, holding frequently along atTop means that for any arbitrary bound a, there is some b ≥ a where the normalized counting ratio is at least c. Because x is strictly increasing, it tends to infinity, so x is eventually at least a by Filter.Tendsto.eventually_ge_atTop. Extracting a cutoff index K via Filter.eventually_atTop.mp, we have a ≤ x(K) (using le_rfl at K). Choosing b = x(K), the assumption hc ensures that the normalized counting function at x(K) is at least c.

    lines 8–12

    uses Filter.frequently_atTop, Filter.eventually_atTop.mp, Filter.Tendsto.eventually_ge_atTop, le_rfl

      have hfreq : ∃ᶠ n in Filter.atTop, c ≤ ((bh_counting A n : ℝ)) / ((n : ℝ) ^ ((1 : ℝ) / (h : ℝ))) := by
        rw [Filter.frequently_atTop]
        intro a
        obtain ⟨K, hK⟩ := Filter.eventually_atTop.mp (Filter.Tendsto.eventually_ge_atTop hmono.tendsto_atTop a)
        exact ⟨x K, hK K le_rfl, hc K⟩
  3. The normalized upper density of A is at least c.

    The normalized upper density bh_upper_density h A is defined as the limit superior of the normalized counting function along Filter.atTop. Since this function is frequently at least c and is bounded from above along Filter.atTop by assumption h_bd, Filter.le_limsup_of_frequently_le yields c ≤ bh_upper_density h A.

    line 13

    uses Filter.le_limsup_of_frequently_le

      exact Filter.le_limsup_of_frequently_le hfreq h_bd
strictMono_nat_of_lt_succ
A sequence on ℕ is strictly monotone if each term is strictly less than its successor.
Filter.frequently_atTop
A property holds frequently along the atTop filter on a directed order if and only if for every threshold a, there exists some b ≥ a satisfying the property.
Filter.eventually_atTop.mp
If a property holds eventually along atTop on ℕ, then there exists a cutoff index K such that the property holds for all b ≥ K.
Filter.Tendsto.eventually_ge_atTop
If a function tends to atTop along a filter, then for any threshold c, its values are eventually at least c along that filter.
le_rfl
The preorder relation ≤ is reflexive: a ≤ a for every a.
Filter.le_limsup_of_frequently_le
If a function is frequently at least a along a filter and is bounded from above under ≤, then a is at most the limit superior of the function along that filter.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- If a set A has normalized counting function at least c along a strictly increasing sequence of checkpoints, and the normalized counting function is bounded under le, then its normalized upper density is at least c. -/theorem bh_upper_density_ge_of_subsequence (h : ℕ) (A : Set ℕ) (x : ℕ → ℕ)    (hx : ∀ k, x k < x (k + 1)) (c : ℝ)    (h_bd : Filter.IsBoundedUnder (· ≤ ·) Filter.atTop (fun n : ℕ => ((bh_counting A n : ℝ)) / ((n : ℝ) ^ ((1 : ℝ) / (h : ℝ)))))    (hc : ∀ k, c ≤ ((bh_counting A (x k) : ℝ)) / ((x k : ℝ) ^ ((1 : ℝ) / (h : ℝ)))) :    c ≤ bh_upper_density h A := by  have hmono : StrictMono x := strictMono_nat_of_lt_succ hx  have hfreq : ∃ᶠ n in Filter.atTop, c ≤ ((bh_counting A n : ℝ)) / ((n : ℝ) ^ ((1 : ℝ) / (h : ℝ))) := by    rw [Filter.frequently_atTop]    intro a    obtain ⟨K, hK⟩ := Filter.eventually_atTop.mp (Filter.Tendsto.eventually_ge_atTop hmono.tendsto_atTop a)    exact ⟨x K, hK K le_rfl, hc K⟩  exact Filter.le_limsup_of_frequently_le hfreq h_bd
See it in the graphDiscuss this resultChallenge it