AFTD Auto-Formalizing Theoretical Domains

four_cycle_graph_code_density_tendsto_one_along_powers_of_two

theoremverifiedformalization

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.

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

    lines 4–6

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

    lines 7–12

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

    lines 13–24

    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

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