AFTD Auto-Formalizing Theoretical Domains

kst_code_density_odd_odd

theoremverifiedformalization

Let s and t be odd natural numbers, and let n be a natural number such that s + t ≤ n. Then the maximum density of a K_{s,t}-code in simple graphs on vertex set [n], kst_code_max_density s t n, is equal to 1/2.

Statement

theorem kst_code_density_odd_odd (s t n : ℕ) (hs : Odd s) (ht : Odd t) (hn : s + t ≤ n) :
    kst_code_max_density s t n = 1 / 2
Formalizes
arXiv:2610.35136, Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences, Proposition 3.2
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • is_kst_codeA family C of simple graphs on vertex set [n] is a K_{s,t}-code if for every two distinct graphs G, G' in C and every pair of disjoint…
  • 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}.
  • kst_code_card_leLet s, t, n be natural numbers with 1 ≤ s, 1 ≤ t, and s + t ≤ n. Every K_{s,t}-code C of simple graphs on vertex set [n] has cardinality…
  • is_kst_code_even_edge_graphsLet s and t be odd natural numbers, and let n be a natural number. The set of simple graphs on vertex set [n] with an even number of edges…
  • ncard_even_edge_graphsFor every natural number n ≥ 2, the cardinality of the set of simple graphs on vertex set [n] having an even number of edges is 2^{n…

Read back from the Lean

For all natural numbers $s$, $t$, and $n$, if $s$ is odd, $t$ is odd, and $s + t \le n$, then the maximum density of a $K_{s,t}$-code on vertex set $\mathrm{Fin}\ n$ (kst_code_max_density s t n) is equal to $1/2$.

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 shows that the maximum density of a K_{s,t}-code on n vertices is 1/2 when s and t are odd and n ≥ s + t, by establishing matching upper and lower bounds. For the upper bound, every K_{s,t}-code has cardinality at most 2^(binom(n,2) - 1), which is at most half of the 2^binom(n,2) possible graphs on n vertices. For the lower bound, the family of all graphs on n vertices with an even number of edges is shown to be a valid K_{s,t}-code (since K_{s,t} has an odd number of edges s * t) with cardinality exactly 2^(binom(n,2) - 1), achieving density 1/2.

  1. 1 ≤ s, 1 ≤ t, and 2 ≤ n

    Because s and t are odd natural numbers, each is of the form 2k + 1, so s ≥ 1 and t ≥ 1. Together with the hypothesis s + t ≤ n, this guarantees n ≥ 1 + 1 = 2.

    lines 4–7

      classical
      have hs1 : 1 ≤ s := by obtain ⟨k, rfl⟩ := hs; omega
      have ht1 : 1 ≤ t := by obtain ⟨k, rfl⟩ := ht; omega
      have hn2 : 2 ≤ n := by omega
  2. For every family of graphs C on vertex set Fin n, its conditional density contribution is at most 1/2

    We split into cases depending on whether C is a K_{s,t}-code. If it is not, the supremum is over an empty index set, which evaluates to 0 ≤ 1/2 by ciSup_neg and Real.sSup_empty. If C is a K_{s,t}-code, the supremum evaluates to |C| / 2^(n.choose 2) by ciSup_pos. Since n ≥ 2, n.choose 2 ≥ 1 by Nat.choose_pos, so 2^(n.choose 2) = 2^(n.choose 2 - 1) * 2 by pow_succ. The cardinality bound kst_code_card_le gives |C| ≤ 2^(n.choose 2 - 1), and clearing the positive denominator with div_le_iff₀ shows that the density is at most 1/2.

    lines 8–25

    uses ciSup_pos, kst_code_card_le, Nat.choose_pos, pow_succ, div_le_iff₀, ciSup_neg, Real.sSup_empty

      have h_le : ∀ C : Set (SimpleGraph (Fin n)),
          (⨆ (_hC : is_kst_code s t n C), (Set.ncard C : ℝ) / (2 ^ (n.choose 2) : ℝ)) ≤ 1 / 2 := by
        intro C
        by_cases h : is_kst_code s t n C
        · rw [ciSup_pos h]
          have hcard_C := kst_code_card_le s t n hs1 ht1 hn C h
          have hk : 1 ≤ n.choose 2 := Nat.choose_pos hn2
          have hk' : n.choose 2 = (n.choose 2 - 1) + 1 := by omega
          have hpow : (2 ^ (n.choose 2) : ℝ) = (2 ^ (n.choose 2 - 1) : ℝ) * 2 := by
            conv_lhs => rw [hk']
            rw [pow_succ]
          have hpos : (0 : ℝ) < (2 ^ (n.choose 2) : ℝ) := by positivity
          rw [div_le_iff₀ hpos, hpow]
          have hcast : (Set.ncard C : ℝ) ≤ (2 ^ (n.choose 2 - 1) : ℝ) := by
            exact_mod_cast hcard_C
          linarith
        · rw [ciSup_neg h, Real.sSup_empty]
          norm_num
  3. The maximum density kst_code_max_density s t n is at most 1/2

    By antisymmetry (le_antisymm), it suffices to prove the two inequalities between the maximum density and 1/2. For the upper bound, we unfold the definition of kst_code_max_density as a supremum over all graph families C. Since every family has density contribution at most 1/2 and the collection of graph families is nonempty, the supremum is at most 1/2 by ciSup_le.

    lines 26–29

    uses le_antisymm, ciSup_le

      apply le_antisymm
      · dsimp [kst_code_max_density]
        have : Nonempty (Set (SimpleGraph (Fin n))) := ⟨∅⟩
        exact ciSup_le h_le
  4. The family C_even of graphs with an even number of edges is a K_{s,t}-code with density exactly 1/2

    Let C_even be the set of simple graphs on Fin n whose edge sets have even cardinality. Because s and t are both odd, is_kst_code_even_edge_graphs shows that C_even is a K_{s,t}-code. By ncard_even_edge_graphs, |C_even| = 2^(n.choose 2 - 1). Factoring the total number of graphs as 2^(n.choose 2) = 2^(n.choose 2 - 1) * 2 and cancelling the non-zero factor 2^(n.choose 2 - 1) using one_mul, mul_comm, and mul_div_mul_right shows that the density |C_even| / 2^(n.choose 2) equals 1/2. By ciSup_pos, the conditional supremum for C_even is therefore exactly 1/2, allowing us to rewrite 1/2 as this term.

    lines 30–48

    uses is_kst_code_even_edge_graphs, ncard_even_edge_graphs, Nat.choose_pos, pow_succ, Nat.cast_pow, Nat.cast_ofNat, one_mul, mul_comm, mul_div_mul_right, ciSup_pos

      · dsimp [kst_code_max_density]
        set C_even : Set (SimpleGraph (Fin n)) := {G | Even G.edgeFinset.card}
        have hC_even : is_kst_code s t n C_even := is_kst_code_even_edge_graphs s t n hs ht
        have hcard : C_even.ncard = 2 ^ (n.choose 2 - 1) := ncard_even_edge_graphs n hn2
        have hdens : (C_even.ncard : ℝ) / (2 ^ (n.choose 2) : ℝ) = 1 / 2 := by
          rw [hcard]
          have hk : 1 ≤ n.choose 2 := Nat.choose_pos hn2
          have hk' : n.choose 2 = (n.choose 2 - 1) + 1 := by omega
          have hpow : (2 ^ (n.choose 2) : ℝ) = (2 ^ (n.choose 2 - 1) : ℝ) * 2 := by
            conv_lhs => rw [hk']
            rw [pow_succ]
          rw [Nat.cast_pow, Nat.cast_ofNat, hpow]
          have hne : ((2 : ℝ) ^ (n.choose 2 - 1)) ≠ 0 := by positivity
          nth_rw 1 [← one_mul ((2 : ℝ) ^ (n.choose 2 - 1))]
          rw [mul_comm ((2 : ℝ) ^ (n.choose 2 - 1)) 2]
          exact mul_div_mul_right 1 2 hne
        have hinner : (⨆ (_hC : is_kst_code s t n C_even), (C_even.ncard : ℝ) / (2 ^ (n.choose 2) : ℝ)) = 1 / 2 := by
          rw [ciSup_pos hC_even, hdens]
        rw [← hinner]
  5. 1/2 ≤ kst_code_max_density s t n

    The set of density contributions across all graph families C is bounded above by 1/2 by the earlier upper bound. By le_ciSup, the overall supremum is at least the value achieved at C_even, which is 1/2, completing the proof.

    lines 49–55

    uses le_ciSup

        have hbdd : BddAbove (Set.range fun C : Set (SimpleGraph (Fin n)) =>
            ⨆ (_hC : is_kst_code s t n C), (C.ncard : ℝ) / (2 ^ (n.choose 2) : ℝ)) := by
          use 1 / 2
          rintro y ⟨C, rfl⟩
          dsimp only
          exact h_le C
        exact le_ciSup hbdd C_even
ciSup_pos
when a proposition p holds, the indexed supremum ⨆ (h : p), f h simplifies to f p
kst_code_card_le
if 1 ≤ s, 1 ≤ t, s + t ≤ n, and C is a K_{s,t}-code on Fin n, then |C| ≤ 2^(n.choose 2 - 1)
Nat.choose_pos
the binomial coefficient n.choose k is strictly positive whenever k ≤ n
pow_succ
a^(n + 1) = a^n * a in any monoid
div_le_iff₀
for c > 0 in a linearly ordered group with zero, b / c ≤ a if and only if b ≤ a * c
ciSup_neg
when a proposition p is false, the indexed supremum ⨆ (h : p), f h equals sSup ∅
Real.sSup_empty
the supremum of the empty set in ℝ is 0
le_antisymm
if a ≤ b and b ≤ a in a partial order, then a = b
ciSup_le
if ι is nonempty and f x ≤ c for all x, then the supremum iSup f is at most c
is_kst_code_even_edge_graphs
for odd natural numbers s and t, the set of graphs on Fin n with an even number of edges is a K_{s,t}-code
ncard_even_edge_graphs
for n ≥ 2, the number of graphs on Fin n with an even number of edges is 2^(n.choose 2 - 1)
Nat.cast_pow
the coercion of a natural power into a semiring equals the power of the coerced base: ↑(m ^ n) = ↑m ^ n
Nat.cast_ofNat
the coercion of a numeral literal into a type with NatCast matches the numeral literal
one_mul
1 * a = a
mul_comm
multiplication is commutative: a * b = b * a
mul_div_mul_right
in a group with zero, (a * c) / (b * c) = a / b whenever c ≠ 0
le_ciSup
if the range of f is bounded above, then f c ≤ iSup f for any point c

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 maximum density of a K_{s,t}-code on Fin n is exactly 1/2 when s and t are odd and n ≥ s + t. -/theorem kst_code_density_odd_odd (s t n : ℕ) (hs : Odd s) (ht : Odd t) (hn : s + t ≤ n) :    kst_code_max_density s t n = 1 / 2 := by  classical  have hs1 : 1 ≤ s := by obtain ⟨k, rfl⟩ := hs; omega  have ht1 : 1 ≤ t := by obtain ⟨k, rfl⟩ := ht; omega  have hn2 : 2 ≤ n := by omega  have h_le : ∀ C : Set (SimpleGraph (Fin n)),      (⨆ (_hC : is_kst_code s t n C), (Set.ncard C : ℝ) / (2 ^ (n.choose 2) : ℝ)) ≤ 1 / 2 := by    intro C    by_cases h : is_kst_code s t n C    · rw [ciSup_pos h]      have hcard_C := kst_code_card_le s t n hs1 ht1 hn C h      have hk : 1 ≤ n.choose 2 := Nat.choose_pos hn2      have hk' : n.choose 2 = (n.choose 2 - 1) + 1 := by omega      have hpow : (2 ^ (n.choose 2) : ℝ) = (2 ^ (n.choose 2 - 1) : ℝ) * 2 := by        conv_lhs => rw [hk']        rw [pow_succ]      have hpos : (0 : ℝ) < (2 ^ (n.choose 2) : ℝ) := by positivity      rw [div_le_iff₀ hpos, hpow]      have hcast : (Set.ncard C : ℝ) ≤ (2 ^ (n.choose 2 - 1) : ℝ) := by        exact_mod_cast hcard_C      linarith    · rw [ciSup_neg h, Real.sSup_empty]      norm_num  apply le_antisymm  · dsimp [kst_code_max_density]    have : Nonempty (Set (SimpleGraph (Fin n))) := ⟨∅⟩    exact ciSup_le h_le  · dsimp [kst_code_max_density]    set C_even : Set (SimpleGraph (Fin n)) := {G | Even G.edgeFinset.card}    have hC_even : is_kst_code s t n C_even := is_kst_code_even_edge_graphs s t n hs ht    have hcard : C_even.ncard = 2 ^ (n.choose 2 - 1) := ncard_even_edge_graphs n hn2    have hdens : (C_even.ncard : ℝ) / (2 ^ (n.choose 2) : ℝ) = 1 / 2 := by      rw [hcard]      have hk : 1 ≤ n.choose 2 := Nat.choose_pos hn2      have hk' : n.choose 2 = (n.choose 2 - 1) + 1 := by omega      have hpow : (2 ^ (n.choose 2) : ℝ) = (2 ^ (n.choose 2 - 1) : ℝ) * 2 := by        conv_lhs => rw [hk']        rw [pow_succ]      rw [Nat.cast_pow, Nat.cast_ofNat, hpow]      have hne : ((2 : ℝ) ^ (n.choose 2 - 1)) ≠ 0 := by positivity      nth_rw 1 [← one_mul ((2 : ℝ) ^ (n.choose 2 - 1))]      rw [mul_comm ((2 : ℝ) ^ (n.choose 2 - 1)) 2]      exact mul_div_mul_right 1 2 hne    have hinner : (⨆ (_hC : is_kst_code s t n C_even), (C_even.ncard : ℝ) / (2 ^ (n.choose 2) : ℝ)) = 1 / 2 := by      rw [ciSup_pos hC_even, hdens]    rw [← hinner]    have hbdd : BddAbove (Set.range fun C : Set (SimpleGraph (Fin n)) =>        ⨆ (_hC : is_kst_code s t n C), (C.ncard : ℝ) / (2 ^ (n.choose 2) : ℝ)) := by      use 1 / 2      rintro y ⟨C, rfl⟩      dsimp only      exact h_le C    exact le_ciSup hbdd C_even
See it in the graphDiscuss this resultChallenge it