four_cycle_graph_code_asymptotic_density_eventually_le
For every real number ε > 0, for eventually all natural numbers n in Filter.atTop, (n : ℝ) * kst_code_max_density 2 2 n ≤ 1 + ε.
Statement
theorem four_cycle_graph_code_asymptotic_density_eventually_le (ε : ℝ) (hε : 0 < ε) : ∀ᶠ n : ℕ in Filter.atTop, (n : ℝ) * kst_code_max_density 2 2 n ≤ 1 + ε
- Formalizes
- arXiv:2301.13305, Proposition 1.5; arXiv:2610.35136, Proposition 3.1
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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 : ℝ)…
Read back from the Lean
For every positive real number ε, for all sufficiently large natural numbers n, n times the maximum density of a (2, 2)-graph code on n vertices (namely kst_code_max_density 2 2 n) is at most 1 + ε.
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 theorem establishes that the normalized maximum density n * kst_code_max_density 2 2 n is eventually bounded above by 1 + ε for any ε > 0. The argument relies on the known bound kst_code_max_density 2 2 n ≤ 1 / (n - 2) for n ≥ 4, which reduces the problem to showing n / (n - 2) ≤ 1 + ε. Choosing n ≥ ⌈2 / ε⌉₊ + 4 guarantees that n - 2 ≥ 2 / ε, which rearranges algebraically to n ≤ (1 + ε)(n - 2).
It suffices to show that n * kst_code_max_density 2 2 n ≤ 1 + ε for all n ≥ ⌈2 / ε⌉₊ + 4.
Unfolding the definition of the filter quantifier ∀ᶠ n in Filter.atTop into an existential threshold, we choose the cutoff N = ⌈2 / ε⌉₊ + 4. We then consider an arbitrary n satisfying n ≥ N.
uses
Filter.eventually_atToprw [Filter.eventually_atTop] use ⌈2 / ε⌉₊ + 4 intro n hn
kst_code_max_density 2 2 n ≤ 1 / (n - 2).
Because the ceiling term is non-negative, n ≥ ⌈2 / ε⌉₊ + 4 implies n ≥ 4. Applying the known density bound k22_code_max_density_le for n ≥ 4 yields the inequality.
uses
k22_code_max_density_lehave hn4 : 4 ≤ n := by omega have h_le : kst_code_max_density 2 2 n ≤ 1 / ((n : ℝ) - 2) := k22_code_max_density_le n hn4
It suffices to prove that n * (1 / (n - 2)) ≤ 1 + ε.
Multiplying the upper bound on code density by the non-negative real n gives n * kst_code_max_density 2 2 n ≤ n * (1 / (n - 2)). By transitivity of ≤, bounding the latter quantity by 1 + ε will establish the goal.
uses
mul_le_mul_of_nonneg_left,Nat.cast_nonneghave h_mul : (n : ℝ) * kst_code_max_density 2 2 n ≤ (n : ℝ) * (1 / ((n : ℝ) - 2)) := mul_le_mul_of_nonneg_left h_le (Nat.cast_nonneg n) apply h_mul.trans
n - 2 > 0 and 2 / ε ≤ n - 2.
By definition of the ceiling function, 2 / ε ≤ ⌈2 / ε⌉₊. Casting the assumption n ≥ ⌈2 / ε⌉₊ + 4 to ℝ shows that n ≥ 2 / ε + 4. Since ε > 0, 2 / ε is strictly positive, and linear arithmetic gives both n - 2 > 0 and 2 / ε ≤ n - 2.
uses
Nat.le_ceil,div_poshave h_ceil : 2 / ε ≤ (⌈2 / ε⌉₊ : ℝ) := Nat.le_ceil (2 / ε) have hn_cast : (⌈2 / ε⌉₊ : ℝ) + 4 ≤ (n : ℝ) := by exact_mod_cast hn have h_pos : 0 < (n : ℝ) - 2 := by have : 0 < 2 / ε := div_pos (by norm_num) hε linarith have h1 : 2 / ε ≤ (n : ℝ) - 2 := by linarith
2 ≤ (n - 2) * ε.
Since ε > 0, we can write 2 = (2 / ε) * ε. Multiplying 2 / ε ≤ n - 2 on the right by ε preserves the inequality, yielding 2 ≤ (n - 2) * ε.
uses
div_mul_cancel₀,ne_of_gt,mul_le_mul_of_nonneg_right,le_of_lthave h2 : 2 ≤ ((n : ℝ) - 2) * ε := by calc 2 = (2 / ε) * ε := (div_mul_cancel₀ 2 (ne_of_gt hε)).symm _ ≤ ((n : ℝ) - 2) * ε := mul_le_mul_of_nonneg_right h1 (le_of_lt hε)
n ≤ (1 + ε) * (n - 2).
Splitting n as (n - 2) + 2 and using 2 ≤ (n - 2) * ε gives n ≤ (n - 2) + (n - 2) * ε. Algebraic factoring rewrites the right-hand side as (1 + ε) * (n - 2).
have h3 : (n : ℝ) ≤ (1 + ε) * ((n : ℝ) - 2) := by calc (n : ℝ) = ((n : ℝ) - 2) + 2 := by ring _ ≤ ((n : ℝ) - 2) + ((n : ℝ) - 2) * ε := by linarith _ = (1 + ε) * ((n : ℝ) - 2) := by ring
n * (1 / (n - 2)) ≤ 1 + ε, completing the proof.
Since n - 2 > 0, dividing n ≤ (1 + ε) * (n - 2) by n - 2 yields n / (n - 2) ≤ 1 + ε. Recognizing that n * (1 / (n - 2)) = n / (n - 2), linear arithmetic finishes the verification.
uses
div_le_iff₀,mul_one_divhave h4 : (n : ℝ) / ((n : ℝ) - 2) ≤ 1 + ε := (div_le_iff₀ h_pos).mpr h3 have h5 : (n : ℝ) * (1 / ((n : ℝ) - 2)) = (n : ℝ) / ((n : ℝ) - 2) := mul_one_div (n : ℝ) ((n : ℝ) - 2) linarith
Filter.eventually_atTop- A predicate holds eventually along Filter.atTop if and only if it holds for all values greater than or equal to some threshold.
k22_code_max_density_le- For n ≥ 4, the maximum density of a K_{2,2}-free graph code on n vertices is at most 1 / (n - 2).
mul_le_mul_of_nonneg_left- Multiplying an inequality on the left by a non-negative number preserves the inequality.
Nat.cast_nonneg- The cast of a natural number into an ordered semiring is non-negative.
Nat.le_ceil- A real number is at most the cast of its natural-number ceiling.
div_pos- The quotient of two strictly positive numbers is strictly positive.
div_mul_cancel₀- Multiplying (a / b) by b cancels the division, provided b ≠ 0.
ne_of_gt- If b < a, then a ≠ b.
mul_le_mul_of_nonneg_right- Multiplying an inequality on the right by a non-negative number preserves the inequality.
le_of_lt- A strict inequality implies the corresponding non-strict inequality.
div_le_iff₀- For c > 0, b / c ≤ a is equivalent to b ≤ a * c.
mul_one_div- For any x and y, x * (1 / y) = x / y.
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.
/-- For every ε > 0, eventually n * kst_code_max_density 2 2 n ≤ 1 + ε as n tends to infinity. -/theorem four_cycle_graph_code_asymptotic_density_eventually_le (ε : ℝ) (hε : 0 < ε) : ∀ᶠ n : ℕ in Filter.atTop, (n : ℝ) * kst_code_max_density 2 2 n ≤ 1 + ε := by rw [Filter.eventually_atTop] use ⌈2 / ε⌉₊ + 4 intro n hn have hn4 : 4 ≤ n := by omega have h_le : kst_code_max_density 2 2 n ≤ 1 / ((n : ℝ) - 2) := k22_code_max_density_le n hn4 have h_mul : (n : ℝ) * kst_code_max_density 2 2 n ≤ (n : ℝ) * (1 / ((n : ℝ) - 2)) := mul_le_mul_of_nonneg_left h_le (Nat.cast_nonneg n) apply h_mul.trans have h_ceil : 2 / ε ≤ (⌈2 / ε⌉₊ : ℝ) := Nat.le_ceil (2 / ε) have hn_cast : (⌈2 / ε⌉₊ : ℝ) + 4 ≤ (n : ℝ) := by exact_mod_cast hn have h_pos : 0 < (n : ℝ) - 2 := by have : 0 < 2 / ε := div_pos (by norm_num) hε linarith have h1 : 2 / ε ≤ (n : ℝ) - 2 := by linarith have h2 : 2 ≤ ((n : ℝ) - 2) * ε := by calc 2 = (2 / ε) * ε := (div_mul_cancel₀ 2 (ne_of_gt hε)).symm _ ≤ ((n : ℝ) - 2) * ε := mul_le_mul_of_nonneg_right h1 (le_of_lt hε) have h3 : (n : ℝ) ≤ (1 + ε) * ((n : ℝ) - 2) := by calc (n : ℝ) = ((n : ℝ) - 2) + 2 := by ring _ ≤ ((n : ℝ) - 2) + ((n : ℝ) - 2) * ε := by linarith _ = (1 + ε) * ((n : ℝ) - 2) := by ring have h4 : (n : ℝ) / ((n : ℝ) - 2) ≤ 1 + ε := (div_le_iff₀ h_pos).mpr h3 have h5 : (n : ℝ) * (1 / ((n : ℝ) - 2)) = (n : ℝ) / ((n : ℝ) - 2) := mul_one_div (n : ℝ) ((n : ℝ) - 2) linarith