bh_upper_density_ge_of_subsequence
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.
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 ℕ.
uses
strictMono_nat_of_lt_succhave hmono : StrictMono x := strictMono_nat_of_lt_succ hxThe 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.
uses
Filter.frequently_atTop,Filter.eventually_atTop.mp,Filter.Tendsto.eventually_ge_atTop,le_rflhave 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⟩
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.
uses
Filter.le_limsup_of_frequently_leexact 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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