kst_code_density_odd_odd
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 ≤ 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.
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
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.
uses
ciSup_pos,kst_code_card_le,Nat.choose_pos,pow_succ,div_le_iff₀,ciSup_neg,Real.sSup_emptyhave 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
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.
uses
le_antisymm,ciSup_leapply le_antisymm · dsimp [kst_code_max_density] have : Nonempty (Set (SimpleGraph (Fin n))) := ⟨∅⟩ exact ciSup_le h_le
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.
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]
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.
uses
le_ciSuphave 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
- In Lean, the maximum density is formalized as a supremum over all graph families C of an inner supremum indexed by proofs that C is a K_{s,t}-code; when C is not a code, the inner supremum is over the empty set, which evaluates to 0 in ℝ.
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 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