four_cycle_graph_code_density_tendsto_one_along_powers_of_two
As the natural number r tends to infinity, the sequence ((2 : ℝ) ^ r) * kst_code_max_density 2 2 (2 ^ r) tends to 1.
Statement
theorem four_cycle_graph_code_density_tendsto_one_along_powers_of_two : Filter.Tendsto (fun r : ℕ => ((2 : ℝ) ^ r) * kst_code_max_density 2 2 (2 ^ r)) Filter.atTop (nhds 1)
- Formalizes
- arXiv:2610.35136, Proposition 4.3; arXiv:2301.13305, Proposition 1.5
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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}.
- k22_code_max_density_leFor every natural number n with 4 ≤ n, the maximum density of a K_{2,2}-code on Fin n, kst_code_max_density 2 2 n, is at most 1 / ((n : ℝ)…
- tendsto_pow_two_div_sub_two_atTopAs the natural number r tends to infinity, 2^r / (2^r - 2) tends to 1.
- 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.
Read back from the Lean
The theorem asserts that as $r \to \infty$ (along $\mathbb{N}$), the quantity $$2^r \cdot \operatorname{kst\_code\_max\_density}(2, 2, 2^r)$$ converges to $1$ in $\mathbb{R}$ (with respect to the standard topology). Here, for any $s, t, n \in \mathbb{N}$, $\operatorname{kst\_code\_max\_density}(s, t, n)$ is defined as the supremum over all subsets $C \subseteq \operatorname{SimpleGraph}(\operatorname{Fin} n)$ satisfying $\operatorname{is\_kst\_code}(s, t, n, C)$ of the normalized cardinality (density) $$\frac{|C|}{2^{\binom{n}{2}}}.$$ A set $C$ of simple graphs on vertex set $\operatorname{Fin} n$ satisfies $\operatorname{is\_kst\_code}(s, t, n, C)$ if for every pair of distinct graphs $G, G' \in C$ and every pair of disjoint subsets $A, B \subseteq \operatorname{Fin} n$ with $|A| = s$ and $|B| = t$, the symmetric difference of $G$ and $G'$ is not equal to the complete bipartite graph with parts $A$ and $B$ (i.e., the graph on $\operatorname{Fin} n$ whose only edges are the $s \times t$ edges between $A$ and $B$). For $s = t = 2$, this means the symmetric difference of any two distinct graphs in $C$ cannot be a 4-cycle.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof applies the squeeze theorem to bound 2^r * kst_code_max_density 2 2 (2^r) between 1 and 2^r / (2^r - 2) for all r ≥ 2. Both bounding sequences tend to 1 as r → ∞: the lower bound is constant, while the upper bound converges to 1 by a prior limit lemma. Multiplying the known lower and upper density bounds for K_{2,2}-codes by 2^r yields the required inequalities.
It suffices to show that 2^r * kst_code_max_density 2 2 (2^r) is eventually squeezed between 1 and 2^r / (2^r - 2).
The constant sequence 1 converges to 1 (tendsto_const_nhds), and the sequence 2^r / (2^r - 2) converges to 1 as r → ∞ (tendsto_pow_two_div_sub_two_atTop). By the squeeze theorem (tendsto_of_tendsto_of_tendsto_of_le_of_le'), the target sequence also converges to 1 once it is bounded between these two sequences for all sufficiently large r.
uses
tendsto_const_nhds,tendsto_pow_two_div_sub_two_atTop,tendsto_of_tendsto_of_tendsto_of_le_of_le'have h_const : Filter.Tendsto (fun _ : ℕ => (1 : ℝ)) Filter.atTop (nhds 1) := tendsto_const_nhds have h_top := tendsto_pow_two_div_sub_two_atTop apply tendsto_of_tendsto_of_tendsto_of_le_of_le' h_const h_top
For all sufficiently large r, 1 ≤ 2^r * kst_code_max_density 2 2 (2^r).
Restricting to r ≥ 2 (Filter.eventually_ge_atTop), the lower bound 1 / 2^r ≤ kst_code_max_density 2 2 (2^r) holds by k22_code_max_density_two_pow_ge. Multiplying both sides by the positive quantity 2^r (mul_le_mul_of_nonneg_left, le_of_lt) gives 2^r * (1 / 2^r) ≤ 2^r * kst_code_max_density 2 2 (2^r). Since 2^r ≠ 0 (ne_of_gt), the left-hand side simplifies to 1 (mul_one_div_cancel).
uses
Filter.eventually_ge_atTop,k22_code_max_density_two_pow_ge,mul_le_mul_of_nonneg_left,le_of_lt,mul_one_div_cancel,ne_of_gt· filter_upwards [Filter.eventually_ge_atTop 2] with r hr have h_ge := k22_code_max_density_two_pow_ge r hr have h_pos : 0 < (2 : ℝ) ^ r := by positivity have h_mul := mul_le_mul_of_nonneg_left h_ge (le_of_lt h_pos) rw [mul_one_div_cancel (ne_of_gt h_pos)] at h_mul exact h_mul
For all sufficiently large r, 2^r * kst_code_max_density 2 2 (2^r) ≤ 2^r / (2^r - 2).
Again restricting to r ≥ 2 (Filter.eventually_ge_atTop), we have 4 = 2^2 ≤ 2^r by monotonicity of powers (Nat.pow_le_pow_right). Applying the upper bound k22_code_max_density_le with block length 2^r ≥ 4 yields kst_code_max_density 2 2 (2^r) ≤ 1 / (2^r - 2). Multiplying both sides by 2^r ≥ 0 (mul_le_mul_of_nonneg_left) and rewriting 2^r * (1 / (2^r - 2)) as 2^r / (2^r - 2) via ring arithmetic completes the upper bound.
uses
Filter.eventually_ge_atTop,Nat.pow_le_pow_right,k22_code_max_density_le,mul_le_mul_of_nonneg_left· filter_upwards [Filter.eventually_ge_atTop 2] with r hr have hr4 : 4 ≤ 2 ^ r := by calc 4 = 2 ^ 2 := by rfl _ ≤ 2 ^ r := Nat.pow_le_pow_right (by decide) hr have h_le := k22_code_max_density_le (2 ^ r) hr4 have h_pos : 0 ≤ (2 : ℝ) ^ r := by positivity have h_mul := mul_le_mul_of_nonneg_left h_le h_pos have h_eq : (2 : ℝ) ^ r * (1 / (((2 ^ r : ℕ) : ℝ) - 2)) = (2 : ℝ) ^ r / ((2 : ℝ) ^ r - 2) := by push_cast ring rwa [h_eq] at h_mul
tendsto_const_nhds- A constant sequence converges to that constant value along any filter.
tendsto_pow_two_div_sub_two_atTop- The sequence 2^r / (2^r - 2) converges to 1 as r tends to infinity.
tendsto_of_tendsto_of_tendsto_of_le_of_le'- The squeeze theorem: if g(x) ≤ f(x) ≤ h(x) eventually and both g and h tend to a, then f tends to a.
Filter.eventually_ge_atTop- For any threshold a, the inequality a ≤ x holds eventually along the atTop filter.
k22_code_max_density_two_pow_ge- For r ≥ 2, the maximum density of a K_{2,2}-code of block length 2^r is at least 1 / 2^r.
mul_le_mul_of_nonneg_left- Multiplying an inequality b ≤ c on the left by a non-negative element a ≥ 0 yields a * b ≤ a * c.
le_of_lt- A strict inequality a < b implies a ≤ b.
mul_one_div_cancel- For any non-zero element a, a * (1 / a) = 1.
ne_of_gt- If a > b, then a ≠ b.
Nat.pow_le_pow_right- For base n > 0, exponentiation is monotonic in the exponent: if i ≤ j then n^i ≤ n^j.
k22_code_max_density_le- For n ≥ 4, the maximum density of a K_{2,2}-code of block length n is at most 1 / (n - 2).
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.
/-- The sequence 2^r * kst_code_max_density 2 2 (2^r) converges to 1 as r tends to infinity. -/theorem four_cycle_graph_code_density_tendsto_one_along_powers_of_two : Filter.Tendsto (fun r : ℕ => ((2 : ℝ) ^ r) * kst_code_max_density 2 2 (2 ^ r)) Filter.atTop (nhds 1) := by have h_const : Filter.Tendsto (fun _ : ℕ => (1 : ℝ)) Filter.atTop (nhds 1) := tendsto_const_nhds have h_top := tendsto_pow_two_div_sub_two_atTop apply tendsto_of_tendsto_of_tendsto_of_le_of_le' h_const h_top · filter_upwards [Filter.eventually_ge_atTop 2] with r hr have h_ge := k22_code_max_density_two_pow_ge r hr have h_pos : 0 < (2 : ℝ) ^ r := by positivity have h_mul := mul_le_mul_of_nonneg_left h_ge (le_of_lt h_pos) rw [mul_one_div_cancel (ne_of_gt h_pos)] at h_mul exact h_mul · filter_upwards [Filter.eventually_ge_atTop 2] with r hr have hr4 : 4 ≤ 2 ^ r := by calc 4 = 2 ^ 2 := by rfl _ ≤ 2 ^ r := Nat.pow_le_pow_right (by decide) hr have h_le := k22_code_max_density_le (2 ^ r) hr4 have h_pos : 0 ≤ (2 : ℝ) ^ r := by positivity have h_mul := mul_le_mul_of_nonneg_left h_le h_pos have h_eq : (2 : ℝ) ^ r * (1 / (((2 ^ r : ℕ) : ℝ) - 2)) = (2 : ℝ) ^ r / ((2 : ℝ) ^ r - 2) := by push_cast ring rwa [h_eq] at h_mul