AFTD Auto-Formalizing Theoretical Domains

k22_code_shortening_density

theoremverified

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.

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

    lines 1–4

    uses symmDiff_def, SimpleGraph.sup_adj, SimpleGraph.sdiff_adj

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

    lines 5–10

    uses SimpleGraph.comap_adj, symmDiff_def, SimpleGraph.sup_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]
    
  3. 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.

    lines 11–26

    uses SimpleGraph.comap_adj, SimpleGraph.between_adj, SimpleGraph.top_adj, Set.mem_image, Fin.castSucc_inj, Or.inl, Or.inr

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

    lines 27–38

    uses Fin.eq_castSucc_or_eq_last, SimpleGraph.comap_adj, SimpleGraph.adj_comm

    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 _)⟩
    
  5. 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.

    lines 39–43

    uses Fin.castSucc_lt_last

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

    lines 44–73

    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_eq

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

    lines 74–104

    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_comm

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

    lines 105–130

    uses k22_code_shortening_density_max_fiber, Fintype.card_set, Fintype.card_fin, congrArg, k22_code_shortening_density_eq_of_res_eq

    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, ?_, ?_⟩
  9. 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).

    lines 131–150

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

    lines 151–179

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

    lines 180–190

    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 _⟩
  12. 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.

    lines 191–194

    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

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