k22_code_max_density_ge_inv_pow_two
For any natural numbers n and r such that n ≤ 2^r and 2 ≤ r, the maximum density of a K_{2,2}-code on Fin n is at least 1 / 2^r.
Statement
theorem k22_code_max_density_ge_inv_pow_two (n r : ℕ) (hn : n ≤ 2 ^ r) (hr : 2 ≤ r) :
1 / ((2 : ℝ) ^ r) ≤ kst_code_max_density 2 2 n- Source
- step towards four_cycle_graph_code_asymptotic_density_eventually_ge
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- kst_code_max_density_antitoneFor all natural numbers s, t, n with 1 ≤ s and 1 ≤ t, the maximum density of a K_{s,t}-code is non-increasing in n: kst_code_max_density s…
- k22_code_max_density_two_pow_geFor every natural number r ≥ 2, the maximum density of a K_{2,2}-code on Fin (2^r) is at least 1 / 2^r.
- kst_code_max_densityThe maximum density of a K_{s,t}-code in simple graphs on vertex set [n] is the supremum over all K_{s,t}-codes C of |C| / 2^{n choose 2}.
The proof, explained
The theorem is proved by combining a known lower bound on the maximum density of a $K_{2,2}$-code on $2^r$ vertices with the fact that the maximum density is non-increasing as the number of vertices grows. First, a helper lemma establishes by induction that the maximum density of a $K_{s,t}$-code on $m$ vertices is at most that on $n$ vertices whenever $n ≤ m$. Specializing this monotonicity to $s = 2$, $t = 2$, and $n ≤ 2^r$ shows that the density on $2^r$ vertices is bounded above by that on $n$ vertices; transitivity then propagates the known bound $1 / 2^r ≤ \mathrm{kst\_code\_max\_density}(2, 2, 2^r)$ to the desired bound on $n$ vertices.
For any parameters $s, t ≥ 1$ and natural numbers $n ≤ m$, the maximum density of a $K_{s,t}$-code on $m$ vertices is bounded above by the maximum density on $n$ vertices: $\mathrm{kst\_code\_max\_density}(s, t, m) ≤ \mathrm{kst\_code\_max\_density}(s, t, n)$.
We prove this monotonicity property by induction on the inequality relation $h : n ≤ m$. In the base case where $m = n$, the inequality holds reflexively by `le_rfl`. In the inductive step from $m$ to $m + 1$, the single-step monotonicity lemma `kst_code_max_density_antitone` gives $\mathrm{kst\_code\_max\_density}(s, t, m + 1) ≤ \mathrm{kst\_code\_max\_density}(s, t, m)$, which combines with the inductive hypothesis via transitivity (`le_trans`) to complete the step.
uses
le_rfl,le_trans,kst_code_max_density_antitoneinduction h with | refl => exact le_rfl | step h ih => exact le_trans (kst_code_max_density_antitone s t _ hs ht) ih
The maximum density of a $K_{2,2}$-code on $2^r$ vertices is at most the maximum density on $n$ vertices: $\mathrm{kst\_code\_max\_density}(2, 2, 2^r) ≤ \mathrm{kst\_code\_max\_density}(2, 2, n)$.
Applying the helper lemma `k22_code_max_density_ge_inv_pow_two_antitone_le` with $s = 2$ and $t = 2$ to the hypothesis $n ≤ 2^r$ (`hn`) yields this intermediate inequality (`hmono`). The required side conditions $1 ≤ 2$ are verified by basic numeric evaluation (`norm_num`).
uses
k22_code_max_density_ge_inv_pow_two_antitone_lehave hmono : kst_code_max_density 2 2 (2 ^ r) ≤ kst_code_max_density 2 2 n := k22_code_max_density_ge_inv_pow_two_antitone_le 2 2 (by norm_num) (by norm_num) hn
Combining the lower bound on $2^r$ vertices with monotonicity yields $1 / 2^r ≤ \mathrm{kst\_code\_max\_density}(2, 2, n)$.
By `k22_code_max_density_two_pow_ge`, the maximum density on $2^r$ vertices is at least $1 / 2^r$, since $2 ≤ r$. Applying transitivity of inequality (`le_trans`) to this lower bound and the monotonicity bound `hmono` completes the proof.
uses
le_trans,k22_code_max_density_two_pow_geexact le_trans (k22_code_max_density_two_pow_ge r hr) hmono
le_rfl- Every element in a preorder is less than or equal to itself ($a ≤ a$).
le_trans- Inequality in a preorder is transitive: if $a ≤ b$ and $b ≤ c$, then $a ≤ c$.
kst_code_max_density_antitone- For parameters $s, t ≥ 1$, the maximum density of a $K_{s,t}$-code on $n + 1$ vertices is at most the maximum density on $n$ vertices.
k22_code_max_density_ge_inv_pow_two_antitone_le- For parameters $s, t ≥ 1$, if $n ≤ m$, then the maximum density of a $K_{s,t}$-code on $m$ vertices is at most the maximum density on $n$ vertices.
k22_code_max_density_two_pow_ge- For any natural number $r ≥ 2$, the maximum density of a $K_{2,2}$-code on $2^r$ vertices is at least $1 / 2^r$.
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.
private lemma k22_code_max_density_ge_inv_pow_two_antitone_le (s t : ℕ) (hs : 1 ≤ s) (ht : 1 ≤ t) {n m : ℕ} (h : n ≤ m) : kst_code_max_density s t m ≤ kst_code_max_density s t n := by induction h with | refl => exact le_rfl | step h ih => exact le_trans (kst_code_max_density_antitone s t _ hs ht) ih/-- For any natural numbers n and r such that n ≤ 2^r and 2 ≤ r, the maximum density of a K_{2,2}-code on Fin n is at least 1 / 2^r. -/theorem k22_code_max_density_ge_inv_pow_two (n r : ℕ) (hn : n ≤ 2 ^ r) (hr : 2 ≤ r) : 1 / ((2 : ℝ) ^ r) ≤ kst_code_max_density 2 2 n := by have hmono : kst_code_max_density 2 2 (2 ^ r) ≤ kst_code_max_density 2 2 n := k22_code_max_density_ge_inv_pow_two_antitone_le 2 2 (by norm_num) (by norm_num) hn exact le_trans (k22_code_max_density_two_pow_ge r hr) hmono