Elementary logarithmic lower bound for H(n)
ProvedErdos624.log2_le_Hcombinatoricserdos-problems
For every positive integer n, the base-two integer logarithm of n is at most H(n). This is an elementary counting lower bound: if a map from the subsets of a set Y onto Fin n covers every element, then n cannot exceed the number 2^{|Y|} of subsets of Y. Applied to a set Y of size H(n), this gives the asserted baseline bound. This is a partial result toward Erdős Problem 624; it does not prove the open divergence H(n) − log₂ n → ∞.
Preamble
import Mathlib import Definitions.Def_Erdos624_defs
Formal statement
namespace Erdos624 theorem log2_le_H (n : ℕ) (hn : 0 < n) : Nat.log2 n ≤ H n := by sorry end Erdos624
Source
Erdős Problem 624, https://www.erdosproblems.com/624; cardinality of the image of the powerset map in the formalized definition of H(n).