AFTD Auto-Formalizing Theoretical Domains

four_cycle_graph_code_asymptotic_density_eventually_le

theoremverifiedformalization

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).

  1. 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.

    lines 4–6

    uses Filter.eventually_atTop

      rw [Filter.eventually_atTop]
      use ⌈2 / ε⌉₊ + 4
      intro n hn
  2. 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.

    lines 7–8

    uses k22_code_max_density_le

      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
  3. 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.

    lines 9–11

    uses mul_le_mul_of_nonneg_left, Nat.cast_nonneg

      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
  4. 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.

    lines 12–17

    uses Nat.le_ceil, div_pos

      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
  5. 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) * ε.

    lines 18–21

    uses div_mul_cancel₀, ne_of_gt, mul_le_mul_of_nonneg_right, le_of_lt

      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ε)
  6. 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).

    lines 22–26

      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
  7. 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.

    lines 27–29

    uses div_le_iff₀, mul_one_div

      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
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

/-- 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
See it in the graphDiscuss this resultChallenge it