k22_code_shortening_density
For natural numbers 4 ≤ n ≤ N, any K_{2,2}-code on Fin N can be restricted to Fin n with density at least that of the original code.
Statement
theorem k22_code_shortening_density (n N : ℕ) (hn : 4 ≤ n) (hle : n ≤ N)
(C : Set (SimpleGraph (Fin N))) (hC : is_kst_code 2 2 N C) :
∃ D : Set (SimpleGraph (Fin n)),
is_kst_code 2 2 n D ∧
(C.ncard : ℝ) / (2 ^ (N.choose 2) : ℝ) ≤ (D.ncard : ℝ) / (2 ^ (n.choose 2) : ℝ)- Source
- step towards k22_code_exists_dense_family
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
The proof, explained
The theorem is proved by induction on N ≥ n. The key step reduces a K_{2,2}-code on Fin (m+1) to a K_{2,2}-code on Fin m without decreasing density by pigeonholing: each graph's neighborhood of the (m+1)-th vertex is one of 2^m possible sets, so some neighborhood occurs in at least a 1/2^m fraction of the code. Restricting this subcode to Fin m is injective and preserves the K_{2,2}-code property, while its size relative to 2^(m.choose 2) matches or exceeds the original density because (m+1).choose 2 = m.choose 2 + m.
An edge exists in the symmetric difference G Δ G' if and only if it belongs to G but not G', or to G' but not G.
Unfolding the definition of symmDiff as (G \ G') ⊔ (G' \ G) and rewriting using the lemmas for adjacency in unions and set differences of graphs.
uses
symmDiff_def,SimpleGraph.sup_adj,SimpleGraph.sdiff_adjprivate lemma k22_code_shortening_density_symmDiff_adj {V : Type*} (G G' : SimpleGraph V) (u v : V) : (symmDiff G G').Adj u v ↔ (G.Adj u v ∧ ¬ G'.Adj u v) ∨ (G'.Adj u v ∧ ¬ G.Adj u v) := by rw [symmDiff_def, SimpleGraph.sup_adj, SimpleGraph.sdiff_adj, SimpleGraph.sdiff_adj]
Restricting the symmetric difference of two graphs on Fin (M+1) via Fin.castSucc is the symmetric difference of their restrictions to Fin M. automation
By extensionality on pairs of vertices, this reduces to adjacency, which simplifies directly via the definitions of comap, union, and difference of graphs.
uses
SimpleGraph.comap_adj,symmDiff_def,SimpleGraph.sup_adj,SimpleGraph.sdiff_adjprivate lemma k22_code_shortening_density_comap_symmDiff {M : ℕ} (G G' : SimpleGraph (Fin (M+1))) : (symmDiff G G').comap Fin.castSucc = symmDiff (G.comap Fin.castSucc) (G'.comap Fin.castSucc) := by ext a b simp only [SimpleGraph.comap_adj, symmDiff_def, SimpleGraph.sup_adj, SimpleGraph.sdiff_adj]
Restricting a complete bipartite graph between embedded sets in Fin (M+1) to Fin M recovers the complete bipartite graph between the original sets in Fin M.
By extensionality, an edge exists between a and b in the pullback if and only if castSucc a and castSucc b form an edge in the complete bipartite graph between castSucc '' s and castSucc '' t. Since castSucc is injective, this is equivalent to a and b being distinct vertices with one in s and the other in t.
uses
SimpleGraph.comap_adj,SimpleGraph.between_adj,SimpleGraph.top_adj,Set.mem_image,Fin.castSucc_inj,Or.inl,Or.inrprivate lemma k22_code_shortening_density_comap_between {M : ℕ} (s t : Set (Fin M)) : (SimpleGraph.between (Fin.castSucc '' s) (Fin.castSucc '' t) ⊤).comap Fin.castSucc = SimpleGraph.between s t ⊤ := by ext a b simp only [SimpleGraph.comap_adj, SimpleGraph.between_adj, SimpleGraph.top_adj, Set.mem_image, Fin.castSucc_inj] constructor · rintro ⟨hne, ⟨⟨x, hx, rfl⟩, ⟨y, hy, rfl⟩⟩ | ⟨⟨x, hx, rfl⟩, ⟨y, hy, rfl⟩⟩⟩ · exact ⟨fun h => hne (by rw [h]), Or.inl ⟨hx, hy⟩⟩ · exact ⟨fun h => hne (by rw [h]), Or.inr ⟨hx, hy⟩⟩ · rintro ⟨hne, h | h⟩ · obtain ⟨h1, h2⟩ := h exact ⟨fun h' => hne (Fin.castSucc_inj.mp h'), Or.inl ⟨⟨a, h1, rfl⟩, ⟨b, h2, rfl⟩⟩⟩ · obtain ⟨h1, h2⟩ := h exact ⟨fun h' => hne (Fin.castSucc_inj.mp h'), Or.inr ⟨⟨a, h1, rfl⟩, ⟨b, h2, rfl⟩⟩⟩
Two graphs on Fin (M+1) are equal if their restrictions to Fin M agree and their adjacencies to Fin.last M agree.
By extensionality on vertices u and v, each vertex is either castSucc of an element of Fin M or Fin.last M. If both are castSucc images, equality follows from the restrictions agreeing; if one is castSucc and the other is Fin.last M, it follows from the hypothesis on the last vertex; if both are Fin.last M, looplessness ensures neither graph contains a self-loop.
uses
Fin.eq_castSucc_or_eq_last,SimpleGraph.comap_adj,SimpleGraph.adj_commprivate lemma k22_code_shortening_density_eq_of_res_eq {M : ℕ} (G G' : SimpleGraph (Fin (M+1))) (hres : G.comap Fin.castSucc = G'.comap Fin.castSucc) (hlast : ∀ i : Fin M, G.Adj (Fin.castSucc i) (Fin.last M) ↔ G'.Adj (Fin.castSucc i) (Fin.last M)) : G = G' := by ext u v rcases Fin.eq_castSucc_or_eq_last u with ⟨a, rfl⟩ | rfl <;> rcases Fin.eq_castSucc_or_eq_last v with ⟨b, rfl⟩ | rfl · rw [← SimpleGraph.comap_adj, ← SimpleGraph.comap_adj, hres] · exact hlast a · simpa only [SimpleGraph.adj_comm] using hlast b · exact ⟨fun h => absurd h (G.loopless.irrefl _), fun h => absurd h (G'.loopless.irrefl _)⟩
The vertex Fin.last M is not in the image of any subset of Fin M under Fin.castSucc.
Every element castSucc x is strictly less than Fin.last M, so it cannot equal Fin.last M.
uses
Fin.castSucc_lt_lastprivate lemma k22_code_shortening_density_last_notin {M : ℕ} (A : Finset (Fin M)) : (Fin.last M) ∉ (Fin.castSucc '' (↑A : Set (Fin M))) := by rintro ⟨x, _, hx⟩ exact absurd hx (Fin.castSucc_lt_last x).ne
If two graphs agree on edges to the last vertex and their restrictions have symmetric difference K_{A,B}, their full symmetric difference on Fin (M+1) is K_{castSucc '' A, castSucc '' B}.
The restrictions of both sides to Fin M agree by the commutation lemmas. Furthermore, neither side contains an edge incident to Fin.last M: the symmetric difference does not because both graphs have identical neighborhoods of Fin.last M, and the complete bipartite graph does not because Fin.last M is not in castSucc '' A or castSucc '' B. Hence the two graphs are equal everywhere.
uses
k22_code_shortening_density_comap_symmDiff,k22_code_shortening_density_comap_between,k22_code_shortening_density_symmDiff_adj,SimpleGraph.between_adj,k22_code_shortening_density_last_notin,k22_code_shortening_density_eq_of_res_eqprivate lemma k22_code_shortening_density_transfer {M : ℕ} (G G' : SimpleGraph (Fin (M+1))) (hnbh : ∀ i : Fin M, G.Adj (Fin.castSucc i) (Fin.last M) ↔ G'.Adj (Fin.castSucc i) (Fin.last M)) (A B : Finset (Fin M)) (hAB : symmDiff (G.comap Fin.castSucc) (G'.comap Fin.castSucc) = SimpleGraph.between (↑A : Set (Fin M)) (↑B : Set (Fin M)) ⊤) : symmDiff G G' = SimpleGraph.between (Fin.castSucc '' (↑A : Set (Fin M))) (Fin.castSucc '' (↑B : Set (Fin M))) ⊤ := by have hres_eq : (symmDiff G G').comap Fin.castSucc = (SimpleGraph.between (Fin.castSucc '' (↑A : Set (Fin M))) (Fin.castSucc '' (↑B : Set (Fin M))) ⊤).comap Fin.castSucc := by rw [k22_code_shortening_density_comap_symmDiff, k22_code_shortening_density_comap_between] exact hAB have hiso1 : ∀ i : Fin M, ¬ (symmDiff G G').Adj (Fin.castSucc i) (Fin.last M) := by intro i rw [k22_code_shortening_density_symmDiff_adj] rintro (⟨h1, h2⟩ | ⟨h1, h2⟩) · exact h2 ((hnbh i).mp h1) · exact h2 ((hnbh i).mpr h1) have hiso2 : ∀ i : Fin M, ¬ (SimpleGraph.between (Fin.castSucc '' (↑A : Set (Fin M))) (Fin.castSucc '' (↑B : Set (Fin M))) ⊤).Adj (Fin.castSucc i) (Fin.last M) := by intro i h rw [SimpleGraph.between_adj] at h rcases h with ⟨_, h | h⟩ · exact k22_code_shortening_density_last_notin B h.2 · exact k22_code_shortening_density_last_notin A h.2 exact k22_code_shortening_density_eq_of_res_eq _ _ hres_eq (fun i => ⟨fun h => absurd h (hiso1 i), fun h => absurd h (hiso2 i)⟩)
For any map f : α → β on a finite set T, there exists an element s0 in β whose fiber has size at least |T| / |β|.
If T is empty, any element works. If T is nonempty, choose s0 maximizing the fiber size. The sum of all fiber sizes over the image of f equals |T|, and each fiber has size at most that of s0, so |T| is at most |image f| * |fiber s0|, which is bounded by |β| * |fiber s0|.
uses
Classical.arbitrary,Finset.exists_mem_eq_sup',Finset.card_eq_sum_card_fiberwise,Finset.mem_image,Finset.le_sup',Finset.sum_le_sum,Finset.sum_const,smul_eq_mul,Nat.mul_le_mul_right,Finset.card_le_univ,Nat.mul_commprivate lemma k22_code_shortening_density_max_fiber {α β : Type*} [Fintype β] [DecidableEq β] [Nonempty β] (f : α → β) (T : Finset α) : ∃ s : β, T.card ≤ (T.filter (fun a => f a = s)).card * Fintype.card β := by classical rcases T.eq_empty_or_nonempty with hT | hT · exact ⟨Classical.arbitrary β, by simp [hT]⟩ · have hRan : (T.image f).Nonempty := hT.image f obtain ⟨s0, hs0mem, hs0eq⟩ := Finset.exists_mem_eq_sup' hRan (fun s => (T.filter (fun a => f a = s)).card) have hsum : T.card = ∑ s ∈ T.image f, (T.filter (fun a => f a = s)).card := by rw [Finset.card_eq_sum_card_fiberwise (f := f) (t := T.image f)] intro a ha exact Finset.mem_image.mpr ⟨a, ha, rfl⟩ have hle1 : ∑ s ∈ T.image f, (T.filter (fun a => f a = s)).card ≤ (T.image f).card * (T.filter (fun a => f a = s0)).card := by have hb : ∀ s ∈ T.image f, (T.filter (fun a => f a = s)).card ≤ (T.filter (fun a => f a = s0)).card := by intro s hs rw [← hs0eq] exact Finset.le_sup' (fun s => (T.filter (fun a => f a = s)).card) hs calc ∑ s ∈ T.image f, (T.filter (fun a => f a = s)).card ≤ ∑ s ∈ T.image f, (T.filter (fun a => f a = s0)).card := Finset.sum_le_sum hb _ = (T.image f).card * (T.filter (fun a => f a = s0)).card := by rw [Finset.sum_const, smul_eq_mul] refine ⟨s0, ?_⟩ calc T.card = ∑ s ∈ T.image f, (T.filter (fun a => f a = s)).card := hsum _ ≤ (T.image f).card * (T.filter (fun a => f a = s0)).card := hle1 _ ≤ Fintype.card β * (T.filter (fun a => f a = s0)).card := Nat.mul_le_mul_right _ (Finset.card_le_univ _) _ = (T.filter (fun a => f a = s0)).card * Fintype.card β := Nat.mul_comm _ _
There is a subset S ⊆ C of graphs that agree on their neighborhood of Fin.last m, with |C| ≤ |S| * 2^m, and the restriction map to Fin m is injective on S.
Assigning each graph G in C its neighborhood of Fin.last m defines a function to subsets of Fin m, of which there are 2^m. By the fiber lemma, some fiber S has size at least |C| / 2^m. All graphs in S have identical edges to Fin.last m, so any two graphs in S with the same restriction to Fin m must be identical.
uses
k22_code_shortening_density_max_fiber,Fintype.card_set,Fintype.card_fin,congrArg,k22_code_shortening_density_eq_of_res_eqprivate lemma k22_code_shortening_density_step (m : ℕ) (C : Set (SimpleGraph (Fin (m+1)))) (hC : is_kst_code 2 2 (m+1) C) : ∃ D : Set (SimpleGraph (Fin m)), is_kst_code 2 2 m D ∧ (C.ncard : ℝ) / 2 ^ ((m+1).choose 2) ≤ (D.ncard : ℝ) / 2 ^ (m.choose 2) := by classical set f : SimpleGraph (Fin (m+1)) → Set (Fin m) := fun G => {i | G.Adj (Fin.castSucc i) (Fin.last m)} with hf set T : Finset (SimpleGraph (Fin (m+1))) := Finset.univ.filter (fun G => G ∈ C) with hT obtain ⟨s0, hs0⟩ := k22_code_shortening_density_max_fiber f T rw [Fintype.card_set, Fintype.card_fin] at hs0 set S : Set (SimpleGraph (Fin (m+1))) := C ∩ {G | f G = s0} with hS have hTC : (↑T : Set (SimpleGraph (Fin (m+1)))) = C := by ext G; simp [hT] have hSC : S = ↑(T.filter (fun a => f a = s0)) := by ext G; simp [hS, hT, Set.mem_inter_iff] have hlast_eq : ∀ G1 ∈ S, ∀ G2 ∈ S, ∀ i : Fin m, G1.Adj (Fin.castSucc i) (Fin.last m) ↔ G2.Adj (Fin.castSucc i) (Fin.last m) := by intro G1 hG1 G2 hG2 i have h1 : f G1 = s0 := hG1.2 have h2 : f G2 = s0 := hG2.2 have h3 := congrArg (fun s : Set (Fin m) => i ∈ s) (h1.trans h2.symm) simpa [hf] using h3 have hinj : Set.InjOn (fun G : SimpleGraph (Fin (m+1)) => G.comap Fin.castSucc) S := by intro G1 hG1 G2 hG2 heq exact k22_code_shortening_density_eq_of_res_eq G1 G2 heq (hlast_eq G1 hG1 G2 hG2) refine ⟨(fun G => G.comap Fin.castSucc) '' S, ?_, ?_⟩
The restricted set of graphs D = {G|_{Fin m} : G ∈ S} is a K_{2,2}-code on Fin m.
Suppose distinct graphs in D had symmetric difference equal to a complete bipartite graph K_{A, B} with |A| = |B| = 2. Then their preimages H1, H2 in S would have symmetric difference equal to K_{castSucc '' A, castSucc '' B} on Fin (m+1) by the transfer lemma. Since H1, H2 ∈ C, this contradicts the assumption that C is a K_{2,2}-code on Fin (m+1).
uses
Finset.coe_image,k22_code_shortening_density_transfer,Finset.disjoint_left,Finset.mem_image,Fin.castSucc_inj,Finset.card_image_of_injective,Fin.castSucc_injective· rintro G1 G2 ⟨H1, hH1, rfl⟩ ⟨H2, hH2, rfl⟩ hGne A B hdisj hA hB hdiff have hHne : H1 ≠ H2 := by rintro rfl; exact hGne rfl have hstep : symmDiff H1 H2 = SimpleGraph.between (↑(A.image Fin.castSucc) : Set (Fin (m+1))) (↑(B.image Fin.castSucc) : Set (Fin (m+1))) ⊤ := by simp only [Finset.coe_image] exact k22_code_shortening_density_transfer H1 H2 (hlast_eq H1 hH1 H2 hH2) A B hdiff have hdisj' : Disjoint (A.image Fin.castSucc) (B.image Fin.castSucc) := by rw [Finset.disjoint_left] intro x hx hx' simp only [Finset.mem_image] at hx hx' obtain ⟨a, ha, rfl⟩ := hx obtain ⟨b, hb, hb2⟩ := hx' exact Finset.disjoint_left.mp hdisj ha (Fin.castSucc_inj.mp hb2 ▸ hb) have hA' : (A.image Fin.castSucc).card = 2 := by rw [Finset.card_image_of_injective _ (Fin.castSucc_injective m), hA] have hB' : (B.image Fin.castSucc).card = 2 := by rw [Finset.card_image_of_injective _ (Fin.castSucc_injective m), hB] exact hC hH1.1 hH2.1 hHne _ _ hdisj' hA' hB' hstep
The code D satisfies the density inequality |C| / 2^((m+1).choose 2) ≤ |D| / 2^(m.choose 2).
Since restriction is injective on S, |D| = |S|. Using |C| ≤ |S| * 2^m and the identity (m+1).choose 2 = m.choose 2 + m, dividing both sides by 2^((m+1).choose 2) = 2^m * 2^(m.choose 2) shows that the density of D is at least that of C.
uses
Set.ncard_coe_finset,Set.InjOn.ncard_image,div_le_iff₀,div_le_div_of_nonneg_right,Nat.choose_succ_succ,Nat.choose_one_right,pow_add· have hCcard : (C.ncard : ℝ) = (T.card : ℝ) := by rw [← hTC, Set.ncard_coe_finset] have hScard : (S.ncard : ℝ) = ((T.filter (fun a => f a = s0)).card : ℝ) := by rw [hSC, Set.ncard_coe_finset] have hDcard : ((fun G : SimpleGraph (Fin (m+1)) => G.comap Fin.castSucc) '' S).ncard = S.ncard := Set.InjOn.ncard_image hinj have hs0R : (T.card : ℝ) ≤ ((T.filter (fun a => f a = s0)).card : ℝ) * 2 ^ m := by exact_mod_cast hs0 have hkey : (C.ncard : ℝ) ≤ (S.ncard : ℝ) * 2 ^ m := by rw [hCcard, hScard] exact hs0R rw [show (((fun G : SimpleGraph (Fin (m+1)) => G.comap Fin.castSucc) '' S).ncard : ℝ) = (S.ncard : ℝ) by rw [hDcard]] have hp2 : (0:ℝ) < 2 ^ (m.choose 2) := by positivity have h1 : (C.ncard : ℝ) / 2 ^ m ≤ (S.ncard : ℝ) := by rw [div_le_iff₀ (by positivity : (0:ℝ) < 2 ^ m)] linarith have h2 : (C.ncard : ℝ) / 2 ^ m / 2 ^ m.choose 2 ≤ (S.ncard : ℝ) / 2 ^ m.choose 2 := div_le_div_of_nonneg_right h1 hp2.le have hchoose : (m+1).choose 2 = m.choose 2 + m := by have h := Nat.choose_succ_succ m 1 simp [Nat.choose_one_right] at h omega calc (C.ncard : ℝ) / 2 ^ ((m+1).choose 2) = (C.ncard : ℝ) / 2 ^ m / 2 ^ m.choose 2 := by rw [hchoose, pow_add]; ring _ ≤ (S.ncard : ℝ) / 2 ^ m.choose 2 := h2
In the base case N = n, the original code C trivially satisfies the density inequality with itself.
We set up induction on N ≥ n using Nat.le_induction; when N = n, taking D = C satisfies the code property and reflexivity of ≤ gives equal density.
uses
Nat.le_induction,le_refl/-- Shortening preserves code density: any K_{2,2}-code on Fin N can be restricted to Fin n without decreasing density. -/ theorem k22_code_shortening_density (n N : ℕ) (hn : 4 ≤ n) (hle : n ≤ N) (C : Set (SimpleGraph (Fin N))) (hC : is_kst_code 2 2 N C) : ∃ D : Set (SimpleGraph (Fin n)), is_kst_code 2 2 n D ∧ (C.ncard : ℝ) / (2 ^ (N.choose 2) : ℝ) ≤ (D.ncard : ℝ) / (2 ^ (n.choose 2) : ℝ) := by classical revert C refine Nat.le_induction (m := n) ?_ ?_ N hle · intro C hC exact ⟨C, hC, le_refl _⟩
The density-shortening theorem holds for all N ≥ n by induction.
In the induction step from k to k+1, we shorten the code on Fin (k+1) to Fin k without decreasing density using the one-step shortening lemma, and then apply the induction hypothesis to shorten from Fin k to Fin n. By transitivity of ≤, the density never decreases.
uses
k22_code_shortening_density_step· intro k hk ih C hC obtain ⟨D', hD', hle'⟩ := k22_code_shortening_density_step k C hC obtain ⟨D, hD, hle2⟩ := ih D' hD' exact ⟨D, hD, hle'.trans hle2⟩
symmDiff_def- The symmetric difference of a and b is defined as (a \ b) ⊔ (b \ a).
SimpleGraph.sup_adj- An edge exists in G ⊔ H if and only if it exists in G or in H.
SimpleGraph.sdiff_adj- An edge exists in G \ H if and only if it exists in G and does not exist in H.
SimpleGraph.comap_adj- An edge exists between u and v in the pullback graph G.comap f if and only if f u is adjacent to f v in G.
SimpleGraph.between_adj- An edge exists in between s t G if and only if it is an edge in G with one endpoint in s and the other in t.
SimpleGraph.top_adj- In the complete graph ⊤, vertices v and w are adjacent if and only if v ≠ w.
Set.mem_image- y is in the image f '' s if and only if there exists x in s with f x = y.
Fin.castSucc_inj- Fin.castSucc is injective: castSucc a = castSucc b if and only if a = b.
Or.inl- Introduces the left disjunct of an 'or' proposition.
Or.inr- Introduces the right disjunct of an 'or' proposition.
Fin.eq_castSucc_or_eq_last- Every element i of Fin (n+1) is either castSucc j for some j in Fin n, or the last element Fin.last n.
SimpleGraph.adj_comm- Graph adjacency is symmetric: G.Adj u v if and only if G.Adj v u.
Fin.castSucc_lt_last- castSucc a is strictly less than Fin.last n for any a in Fin n.
k22_code_shortening_density_comap_symmDiff- Restricting the symmetric difference of two graphs on Fin (M+1) to Fin M equals the symmetric difference of their restrictions.
k22_code_shortening_density_comap_between- Restricting the complete bipartite graph between embedded sets in Fin (M+1) to Fin M yields the complete bipartite graph between the original sets in Fin M.
k22_code_shortening_density_symmDiff_adj- Characterization of edges in the symmetric difference of two graphs as belonging to one but not the other.
k22_code_shortening_density_last_notin- The vertex Fin.last M does not belong to the image of any subset of Fin M under castSucc.
k22_code_shortening_density_eq_of_res_eq- Two graphs on Fin (M+1) are equal if their restrictions to Fin M agree and they have the same edges to Fin.last M.
Classical.arbitrary- Produces an arbitrary element of a nonempty type.
Finset.exists_mem_eq_sup'- A function on a nonempty finite set attains its maximum value at some element.
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set equals the sum of the cardinalities of its fibers over a target set.
Finset.mem_image- b is in Finset.image f s if and only if there is a in s such that f a = b.
Finset.le_sup'- The value of a function at an element in a set is at most the supremum over that set.
Finset.sum_le_sum- A sum of pointwise smaller terms is less than or equal to the sum of the larger terms.
Finset.sum_const- The sum of a constant value over a finite set is that constant multiplied by the cardinality of the set.
smul_eq_mul- Scalar multiplication of a natural number with a natural number equals ordinary multiplication.
Nat.mul_le_mul_right- Multiplying both sides of an inequality by a natural number on the right preserves the inequality.
Finset.card_le_univ- The cardinality of a finset in a finite type is at most the cardinality of the type.
Nat.mul_comm- Multiplication of natural numbers is commutative.
k22_code_shortening_density_max_fiber- For any function from a finite set T to a finite type β, there is some fiber whose size times |β| is at least |T|.
Fintype.card_set- The cardinality of the powerset of a finite type α is 2 ^ |α|.
Fintype.card_fin- The cardinality of Fin n is n.
congrArg- Applying a function to equal arguments produces equal results.
Finset.coe_image- Coercing the image of a finset to a set equals the set image of the coerced finset.
k22_code_shortening_density_transfer- If two graphs on Fin (M+1) agree on neighborhoods of the last vertex and their restrictions have symmetric difference K_{A,B}, then their full symmetric difference is K_{A,B}.
Finset.disjoint_left- Two finsets are disjoint if and only if no element of the first belongs to the second.
Finset.card_image_of_injective- An injective map on a finset preserves its cardinality.
Fin.castSucc_injective- Fin.castSucc is an injective function.
Set.ncard_coe_finset- The set cardinality (ncard) of a coerced finset equals the finset cardinality (card).
Set.InjOn.ncard_image- The cardinality of the image under an injective map on a set equals the cardinality of the set.
div_le_iff₀- For c > 0, b / c ≤ a if and only if b ≤ a * c.
div_le_div_of_nonneg_right- Dividing both sides of an inequality a ≤ b by a non-negative number preserves the inequality.
Nat.choose_succ_succ- Pascal's identity: (n+1).choose (k+1) = n.choose k + n.choose (k+1).
Nat.choose_one_right- n.choose 1 = n for any natural number n.
pow_add- Exponentiation distributes over addition: a ^ (m + n) = a ^ m * a ^ n.
Nat.le_induction- Induction on natural numbers starting from a base value m: if P m holds and P k implies P (k+1) for all k ≥ m, then P N holds for all N ≥ m.
le_refl- Any element is less than or equal to itself in a preorder.
k22_code_shortening_density_step- Given a K_{2,2}-code on Fin (m+1), there exists a K_{2,2}-code on Fin m whose density is at least that of the original code.
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.
private lemma k22_code_shortening_density_symmDiff_adj {V : Type*} (G G' : SimpleGraph V) (u v : V) : (symmDiff G G').Adj u v ↔ (G.Adj u v ∧ ¬ G'.Adj u v) ∨ (G'.Adj u v ∧ ¬ G.Adj u v) := by rw [symmDiff_def, SimpleGraph.sup_adj, SimpleGraph.sdiff_adj, SimpleGraph.sdiff_adj]private lemma k22_code_shortening_density_comap_symmDiff {M : ℕ} (G G' : SimpleGraph (Fin (M+1))) : (symmDiff G G').comap Fin.castSucc = symmDiff (G.comap Fin.castSucc) (G'.comap Fin.castSucc) := by ext a b simp only [SimpleGraph.comap_adj, symmDiff_def, SimpleGraph.sup_adj, SimpleGraph.sdiff_adj]private lemma k22_code_shortening_density_comap_between {M : ℕ} (s t : Set (Fin M)) : (SimpleGraph.between (Fin.castSucc '' s) (Fin.castSucc '' t) ⊤).comap Fin.castSucc = SimpleGraph.between s t ⊤ := by ext a b simp only [SimpleGraph.comap_adj, SimpleGraph.between_adj, SimpleGraph.top_adj, Set.mem_image, Fin.castSucc_inj] constructor · rintro ⟨hne, ⟨⟨x, hx, rfl⟩, ⟨y, hy, rfl⟩⟩ | ⟨⟨x, hx, rfl⟩, ⟨y, hy, rfl⟩⟩⟩ · exact ⟨fun h => hne (by rw [h]), Or.inl ⟨hx, hy⟩⟩ · exact ⟨fun h => hne (by rw [h]), Or.inr ⟨hx, hy⟩⟩ · rintro ⟨hne, h | h⟩ · obtain ⟨h1, h2⟩ := h exact ⟨fun h' => hne (Fin.castSucc_inj.mp h'), Or.inl ⟨⟨a, h1, rfl⟩, ⟨b, h2, rfl⟩⟩⟩ · obtain ⟨h1, h2⟩ := h exact ⟨fun h' => hne (Fin.castSucc_inj.mp h'), Or.inr ⟨⟨a, h1, rfl⟩, ⟨b, h2, rfl⟩⟩⟩private lemma k22_code_shortening_density_eq_of_res_eq {M : ℕ} (G G' : SimpleGraph (Fin (M+1))) (hres : G.comap Fin.castSucc = G'.comap Fin.castSucc) (hlast : ∀ i : Fin M, G.Adj (Fin.castSucc i) (Fin.last M) ↔ G'.Adj (Fin.castSucc i) (Fin.last M)) : G = G' := by ext u v rcases Fin.eq_castSucc_or_eq_last u with ⟨a, rfl⟩ | rfl <;> rcases Fin.eq_castSucc_or_eq_last v with ⟨b, rfl⟩ | rfl · rw [← SimpleGraph.comap_adj, ← SimpleGraph.comap_adj, hres] · exact hlast a · simpa only [SimpleGraph.adj_comm] using hlast b · exact ⟨fun h => absurd h (G.loopless.irrefl _), fun h => absurd h (G'.loopless.irrefl _)⟩private lemma k22_code_shortening_density_last_notin {M : ℕ} (A : Finset (Fin M)) : (Fin.last M) ∉ (Fin.castSucc '' (↑A : Set (Fin M))) := by rintro ⟨x, _, hx⟩ exact absurd hx (Fin.castSucc_lt_last x).neprivate lemma k22_code_shortening_density_transfer {M : ℕ} (G G' : SimpleGraph (Fin (M+1))) (hnbh : ∀ i : Fin M, G.Adj (Fin.castSucc i) (Fin.last M) ↔ G'.Adj (Fin.castSucc i) (Fin.last M)) (A B : Finset (Fin M)) (hAB : symmDiff (G.comap Fin.castSucc) (G'.comap Fin.castSucc) = SimpleGraph.between (↑A : Set (Fin M)) (↑B : Set (Fin M)) ⊤) : symmDiff G G' = SimpleGraph.between (Fin.castSucc '' (↑A : Set (Fin M))) (Fin.castSucc '' (↑B : Set (Fin M))) ⊤ := by have hres_eq : (symmDiff G G').comap Fin.castSucc = (SimpleGraph.between (Fin.castSucc '' (↑A : Set (Fin M))) (Fin.castSucc '' (↑B : Set (Fin M))) ⊤).comap Fin.castSucc := by rw [k22_code_shortening_density_comap_symmDiff, k22_code_shortening_density_comap_between] exact hAB have hiso1 : ∀ i : Fin M, ¬ (symmDiff G G').Adj (Fin.castSucc i) (Fin.last M) := by intro i rw [k22_code_shortening_density_symmDiff_adj] rintro (⟨h1, h2⟩ | ⟨h1, h2⟩) · exact h2 ((hnbh i).mp h1) · exact h2 ((hnbh i).mpr h1) have hiso2 : ∀ i : Fin M, ¬ (SimpleGraph.between (Fin.castSucc '' (↑A : Set (Fin M))) (Fin.castSucc '' (↑B : Set (Fin M))) ⊤).Adj (Fin.castSucc i) (Fin.last M) := by intro i h rw [SimpleGraph.between_adj] at h rcases h with ⟨_, h | h⟩ · exact k22_code_shortening_density_last_notin B h.2 · exact k22_code_shortening_density_last_notin A h.2 exact k22_code_shortening_density_eq_of_res_eq _ _ hres_eq (fun i => ⟨fun h => absurd h (hiso1 i), fun h => absurd h (hiso2 i)⟩)private lemma k22_code_shortening_density_max_fiber {α β : Type*} [Fintype β] [DecidableEq β] [Nonempty β] (f : α → β) (T : Finset α) : ∃ s : β, T.card ≤ (T.filter (fun a => f a = s)).card * Fintype.card β := by classical rcases T.eq_empty_or_nonempty with hT | hT · exact ⟨Classical.arbitrary β, by simp [hT]⟩ · have hRan : (T.image f).Nonempty := hT.image f obtain ⟨s0, hs0mem, hs0eq⟩ := Finset.exists_mem_eq_sup' hRan (fun s => (T.filter (fun a => f a = s)).card) have hsum : T.card = ∑ s ∈ T.image f, (T.filter (fun a => f a = s)).card := by rw [Finset.card_eq_sum_card_fiberwise (f := f) (t := T.image f)] intro a ha exact Finset.mem_image.mpr ⟨a, ha, rfl⟩ have hle1 : ∑ s ∈ T.image f, (T.filter (fun a => f a = s)).card ≤ (T.image f).card * (T.filter (fun a => f a = s0)).card := by have hb : ∀ s ∈ T.image f, (T.filter (fun a => f a = s)).card ≤ (T.filter (fun a => f a = s0)).card := by intro s hs rw [← hs0eq] exact Finset.le_sup' (fun s => (T.filter (fun a => f a = s)).card) hs calc ∑ s ∈ T.image f, (T.filter (fun a => f a = s)).card ≤ ∑ s ∈ T.image f, (T.filter (fun a => f a = s0)).card := Finset.sum_le_sum hb _ = (T.image f).card * (T.filter (fun a => f a = s0)).card := by rw [Finset.sum_const, smul_eq_mul] refine ⟨s0, ?_⟩ calc T.card = ∑ s ∈ T.image f, (T.filter (fun a => f a = s)).card := hsum _ ≤ (T.image f).card * (T.filter (fun a => f a = s0)).card := hle1 _ ≤ Fintype.card β * (T.filter (fun a => f a = s0)).card := Nat.mul_le_mul_right _ (Finset.card_le_univ _) _ = (T.filter (fun a => f a = s0)).card * Fintype.card β := Nat.mul_comm _ _private lemma k22_code_shortening_density_step (m : ℕ) (C : Set (SimpleGraph (Fin (m+1)))) (hC : is_kst_code 2 2 (m+1) C) : ∃ D : Set (SimpleGraph (Fin m)), is_kst_code 2 2 m D ∧ (C.ncard : ℝ) / 2 ^ ((m+1).choose 2) ≤ (D.ncard : ℝ) / 2 ^ (m.choose 2) := by classical set f : SimpleGraph (Fin (m+1)) → Set (Fin m) := fun G => {i | G.Adj (Fin.castSucc i) (Fin.last m)} with hf set T : Finset (SimpleGraph (Fin (m+1))) := Finset.univ.filter (fun G => G ∈ C) with hT obtain ⟨s0, hs0⟩ := k22_code_shortening_density_max_fiber f T rw [Fintype.card_set, Fintype.card_fin] at hs0 set S : Set (SimpleGraph (Fin (m+1))) := C ∩ {G | f G = s0} with hS have hTC : (↑T : Set (SimpleGraph (Fin (m+1)))) = C := by ext G; simp [hT] have hSC : S = ↑(T.filter (fun a => f a = s0)) := by ext G; simp [hS, hT, Set.mem_inter_iff] have hlast_eq : ∀ G1 ∈ S, ∀ G2 ∈ S, ∀ i : Fin m, G1.Adj (Fin.castSucc i) (Fin.last m) ↔ G2.Adj (Fin.castSucc i) (Fin.last m) := by intro G1 hG1 G2 hG2 i have h1 : f G1 = s0 := hG1.2 have h2 : f G2 = s0 := hG2.2 have h3 := congrArg (fun s : Set (Fin m) => i ∈ s) (h1.trans h2.symm) simpa [hf] using h3 have hinj : Set.InjOn (fun G : SimpleGraph (Fin (m+1)) => G.comap Fin.castSucc) S := by intro G1 hG1 G2 hG2 heq exact k22_code_shortening_density_eq_of_res_eq G1 G2 heq (hlast_eq G1 hG1 G2 hG2) refine ⟨(fun G => G.comap Fin.castSucc) '' S, ?_, ?_⟩ · rintro G1 G2 ⟨H1, hH1, rfl⟩ ⟨H2, hH2, rfl⟩ hGne A B hdisj hA hB hdiff have hHne : H1 ≠ H2 := by rintro rfl; exact hGne rfl have hstep : symmDiff H1 H2 = SimpleGraph.between (↑(A.image Fin.castSucc) : Set (Fin (m+1))) (↑(B.image Fin.castSucc) : Set (Fin (m+1))) ⊤ := by simp only [Finset.coe_image] exact k22_code_shortening_density_transfer H1 H2 (hlast_eq H1 hH1 H2 hH2) A B hdiff have hdisj' : Disjoint (A.image Fin.castSucc) (B.image Fin.castSucc) := by rw [Finset.disjoint_left] intro x hx hx' simp only [Finset.mem_image] at hx hx' obtain ⟨a, ha, rfl⟩ := hx obtain ⟨b, hb, hb2⟩ := hx' exact Finset.disjoint_left.mp hdisj ha (Fin.castSucc_inj.mp hb2 ▸ hb) have hA' : (A.image Fin.castSucc).card = 2 := by rw [Finset.card_image_of_injective _ (Fin.castSucc_injective m), hA] have hB' : (B.image Fin.castSucc).card = 2 := by rw [Finset.card_image_of_injective _ (Fin.castSucc_injective m), hB] exact hC hH1.1 hH2.1 hHne _ _ hdisj' hA' hB' hstep · have hCcard : (C.ncard : ℝ) = (T.card : ℝ) := by rw [← hTC, Set.ncard_coe_finset] have hScard : (S.ncard : ℝ) = ((T.filter (fun a => f a = s0)).card : ℝ) := by rw [hSC, Set.ncard_coe_finset] have hDcard : ((fun G : SimpleGraph (Fin (m+1)) => G.comap Fin.castSucc) '' S).ncard = S.ncard := Set.InjOn.ncard_image hinj have hs0R : (T.card : ℝ) ≤ ((T.filter (fun a => f a = s0)).card : ℝ) * 2 ^ m := by exact_mod_cast hs0 have hkey : (C.ncard : ℝ) ≤ (S.ncard : ℝ) * 2 ^ m := by rw [hCcard, hScard] exact hs0R rw [show (((fun G : SimpleGraph (Fin (m+1)) => G.comap Fin.castSucc) '' S).ncard : ℝ) = (S.ncard : ℝ) by rw [hDcard]] have hp2 : (0:ℝ) < 2 ^ (m.choose 2) := by positivity have h1 : (C.ncard : ℝ) / 2 ^ m ≤ (S.ncard : ℝ) := by rw [div_le_iff₀ (by positivity : (0:ℝ) < 2 ^ m)] linarith have h2 : (C.ncard : ℝ) / 2 ^ m / 2 ^ m.choose 2 ≤ (S.ncard : ℝ) / 2 ^ m.choose 2 := div_le_div_of_nonneg_right h1 hp2.le have hchoose : (m+1).choose 2 = m.choose 2 + m := by have h := Nat.choose_succ_succ m 1 simp [Nat.choose_one_right] at h omega calc (C.ncard : ℝ) / 2 ^ ((m+1).choose 2) = (C.ncard : ℝ) / 2 ^ m / 2 ^ m.choose 2 := by rw [hchoose, pow_add]; ring _ ≤ (S.ncard : ℝ) / 2 ^ m.choose 2 := h2/-- Shortening preserves code density: any K_{2,2}-code on Fin N can be restricted to Fin n without decreasing density. -/theorem k22_code_shortening_density (n N : ℕ) (hn : 4 ≤ n) (hle : n ≤ N) (C : Set (SimpleGraph (Fin N))) (hC : is_kst_code 2 2 N C) : ∃ D : Set (SimpleGraph (Fin n)), is_kst_code 2 2 n D ∧ (C.ncard : ℝ) / (2 ^ (N.choose 2) : ℝ) ≤ (D.ncard : ℝ) / (2 ^ (n.choose 2) : ℝ) := by classical revert C refine Nat.le_induction (m := n) ?_ ?_ N hle · intro C hC exact ⟨C, hC, le_refl _⟩ · intro k hk ih C hC obtain ⟨D', hD', hle'⟩ := k22_code_shortening_density_step k C hC obtain ⟨D, hD, hle2⟩ := ih D' hD' exact ⟨D, hD, hle'.trans hle2⟩