AFTD Auto-Formalizing Theoretical Domains

op_258_forces_of_forces_smul_blowup

theoremverified

For γ ≥ 1 and k ≥ 1: if a forces a monochromatic K_{γk}, then the profile γ·a forces a monochromatic K_k.

Statement

theorem op_258_forces_of_forces_smul_blowup (a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a)
    (hsum : 1 < ∑' i : ℕ+, ENNReal.ofReal (a i)) (γ k : ℕ) (hγ : 1 ≤ γ)
    (h : op_258_forces a (γ * k)) : op_258_forces (fun i => (γ : ℝ) * a i) k
Source
step towards op_258_forces_step
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • op_258_bounded_extensionFor a positive antitone profile a with Σ a i > 1 there is n₀ such that for every n ≥ n₀, every partially defined a-bounded colouring of…
  • op_258_forcesThe decay profile a forces a monochromatic K_k if for all sufficiently large n, every a-bounded colouring of the edges of K_n has a…
  • op_258_boundedA colouring c of the edges of the complete graph K_n is a-bounded if for every colour i the number of edges of colour i is at most a i *…
  • op_258_forces_mono_cliqueIf a forces a monochromatic K_k, then a forces a monochromatic K_j for every j ≤ k.
  • op_258_choose_two_mul_sq_leFor any γ ≥ 1 and m : ℕ, γ² * C(m, 2) ≤ C(γ * m, 2).
  • op_258_pigeonhole_blocksLet s be a finite set and f : α → Fin γ. If γ * k ≤ |s| and γ ≥ 1, then there exists b ∈ Fin γ with |{x ∈ s | f x = b}| ≥ k.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • op_258_has_mono_cliqueThe colouring c of the edges of K_n has a monochromatic K_k: there are a k-element vertex set s and a colour i such that every edge inside…
  • FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via ZMod.

Lean source view module on GitHub

def op_258_forces_of_forces_smul_blowup_b (γ n : ℕ) : Fin (γ * n) → Fin γ :=
  fun x => (finProdFinEquiv (m := γ) (n := n)).symm x |>.1
def op_258_forces_of_forces_smul_blowup_q (γ n : ℕ) : Fin (γ * n) → Fin n :=
  fun x => (finProdFinEquiv (m := γ) (n := n)).symm x |>.2
def op_258_forces_of_forces_smul_blowup_emb (γ n : ℕ) (r : Fin γ) : Fin n → Fin (γ * n) :=
  fun u => finProdFinEquiv (r, u)
lemma op_258_forces_of_forces_smul_blowup_b_emb (γ n : ℕ) (r : Fin γ) (u : Fin n) :
    op_258_forces_of_forces_smul_blowup_b γ n (op_258_forces_of_forces_smul_blowup_emb γ n r u) = r := by
  simp [op_258_forces_of_forces_smul_blowup_b, op_258_forces_of_forces_smul_blowup_emb]
lemma op_258_forces_of_forces_smul_blowup_q_emb (γ n : ℕ) (r : Fin γ) (u : Fin n) :
    op_258_forces_of_forces_smul_blowup_q γ n (op_258_forces_of_forces_smul_blowup_emb γ n r u) = u := by
  simp [op_258_forces_of_forces_smul_blowup_q, op_258_forces_of_forces_smul_blowup_emb]
lemma op_258_forces_of_forces_smul_blowup_emb_bq (γ n : ℕ) (x : Fin (γ * n)) :
    op_258_forces_of_forces_smul_blowup_emb γ n (op_258_forces_of_forces_smul_blowup_b γ n x) (op_258_forces_of_forces_smul_blowup_q γ n x) = x := by
  simp only [op_258_forces_of_forces_smul_blowup_b, op_258_forces_of_forces_smul_blowup_q, op_258_forces_of_forces_smul_blowup_emb]
  exact Equiv.apply_symm_apply _ _
lemma op_258_forces_of_forces_smul_blowup_eq_of_bq (γ n : ℕ) {x y : Fin (γ * n)}
    (hb : op_258_forces_of_forces_smul_blowup_b γ n x = op_258_forces_of_forces_smul_blowup_b γ n y)
    (hq : op_258_forces_of_forces_smul_blowup_q γ n x = op_258_forces_of_forces_smul_blowup_q γ n y) : x = y := by
  rw [← op_258_forces_of_forces_smul_blowup_emb_bq γ n x, ← op_258_forces_of_forces_smul_blowup_emb_bq γ n y, hb, hq]
lemma op_258_forces_of_forces_smul_blowup_mem_edgeSet_iff (V : Type*) (z : Sym2 V) :
    z ∈ (SimpleGraph.completeGraph V).edgeSet ↔ ¬ z.IsDiag := by
  rw [SimpleGraph.completeGraph_eq_top, SimpleGraph.edgeSet_top]; simp
lemma op_258_forces_of_forces_smul_blowup_emb_injective (γ n : ℕ) (r : Fin γ) :
    Function.Injective (op_258_forces_of_forces_smul_blowup_emb γ n r) := by
  intro u v h
  have := congrArg (fun x => (finProdFinEquiv (m := γ) (n := n)).symm x) h
  simpa [op_258_forces_of_forces_smul_blowup_emb] using this
lemma op_258_forces_of_forces_smul_blowup_mk_mem (n : ℕ) {x y : Fin n} (h : x ≠ y) :
    Sym2.mk x y ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet := by
  rw [op_258_forces_of_forces_smul_blowup_mem_edgeSet_iff, Sym2.mk_isDiag_iff]; exact h
noncomputable def op_258_forces_of_forces_smul_blowup_g (γ n : ℕ)
    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) (x y : Fin (γ * n)) : ℕ+ :=
  if h : op_258_forces_of_forces_smul_blowup_b γ n x = op_258_forces_of_forces_smul_blowup_b γ n y ∧
      op_258_forces_of_forces_smul_blowup_q γ n x ≠ op_258_forces_of_forces_smul_blowup_q γ n y then
    c ⟨Sym2.mk (op_258_forces_of_forces_smul_blowup_q γ n x) (op_258_forces_of_forces_smul_blowup_q γ n y),
        op_258_forces_of_forces_smul_blowup_mk_mem n h.2⟩
  else 1
lemma op_258_forces_of_forces_smul_blowup_g_symm (γ n : ℕ)
    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) :
    ∀ x y, op_258_forces_of_forces_smul_blowup_g γ n c x y = op_258_forces_of_forces_smul_blowup_g γ n c y x := by
  intro x y
  unfold op_258_forces_of_forces_smul_blowup_g
  by_cases h : op_258_forces_of_forces_smul_blowup_b γ n x = op_258_forces_of_forces_smul_blowup_b γ n y ∧
      op_258_forces_of_forces_smul_blowup_q γ n x ≠ op_258_forces_of_forces_smul_blowup_q γ n y
  · have h' : op_258_forces_of_forces_smul_blowup_b γ n y = op_258_forces_of_forces_smul_blowup_b γ n x ∧
        op_258_forces_of_forces_smul_blowup_q γ n y ≠ op_258_forces_of_forces_smul_blowup_q γ n x :=
      ⟨h.1.symm, fun e => h.2 e.symm⟩
    rw [dif_pos h, dif_pos h']
    congr 1
    apply Subtype.ext
    exact Sym2.eq_iff.2 (Or.inr ⟨rfl, rfl⟩)
  · have h' : ¬ (op_258_forces_of_forces_smul_blowup_b γ n y = op_258_forces_of_forces_smul_blowup_b γ n x ∧
        op_258_forces_of_forces_smul_blowup_q γ n y ≠ op_258_forces_of_forces_smul_blowup_q γ n x) :=
      fun e => h ⟨e.1.symm, fun e2 => e.2 e2.symm⟩
    rw [dif_neg h, dif_neg h']
noncomputable def op_258_forces_of_forces_smul_blowup_lift (γ n : ℕ)
    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) : Sym2 (Fin (γ * n)) → ℕ+ :=
  Sym2.lift ⟨op_258_forces_of_forces_smul_blowup_g γ n c, op_258_forces_of_forces_smul_blowup_g_symm γ n c⟩
lemma op_258_forces_of_forces_smul_blowup_lift_mk (γ n : ℕ)
    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) (x y : Fin (γ * n)) :
    op_258_forces_of_forces_smul_blowup_lift γ n c (Sym2.mk x y) = op_258_forces_of_forces_smul_blowup_g γ n c x y :=
  Sym2.lift_mk _ x y
lemma op_258_forces_of_forces_smul_blowup_lift_map (γ n : ℕ)
    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) (r : Fin γ) (z : Sym2 (Fin n))
    (hz : z ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet) :
    op_258_forces_of_forces_smul_blowup_lift γ n c (Sym2.map (op_258_forces_of_forces_smul_blowup_emb γ n r) z) = c ⟨z, hz⟩ := by
  induction z using Sym2.inductionOn with
  | hf u v =>
    have huv : u ≠ v := by
      have h := hz; rw [op_258_forces_of_forces_smul_blowup_mem_edgeSet_iff, Sym2.mk_isDiag_iff] at h; exact h
    rw [Sym2.map_mk, op_258_forces_of_forces_smul_blowup_lift_mk]
    unfold op_258_forces_of_forces_smul_blowup_g
    rw [dif_pos ⟨by rw [op_258_forces_of_forces_smul_blowup_b_emb, op_258_forces_of_forces_smul_blowup_b_emb],
                   by rw [op_258_forces_of_forces_smul_blowup_q_emb, op_258_forces_of_forces_smul_blowup_q_emb]; exact huv⟩]
    congr 1
    apply Subtype.ext
    simp only [op_258_forces_of_forces_smul_blowup_q_emb]
noncomputable def op_258_forces_of_forces_smul_blowup_c0 (γ n : ℕ)
    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+)
    (e : (SimpleGraph.completeGraph (Fin (γ * n))).edgeSet) : ℕ+ :=
  op_258_forces_of_forces_smul_blowup_lift γ n c e.1
noncomputable def op_258_forces_of_forces_smul_blowup_push (γ n : ℕ)
    (p : Fin γ × (SimpleGraph.completeGraph (Fin n)).edgeSet) :
    (SimpleGraph.completeGraph (Fin (γ * n))).edgeSet :=
  ⟨Sym2.map (op_258_forces_of_forces_smul_blowup_emb γ n p.1) p.2.1, by
    have hz : ¬ p.2.1.IsDiag := by
      have := p.2.2; rwa [op_258_forces_of_forces_smul_blowup_mem_edgeSet_iff] at this
    rw [op_258_forces_of_forces_smul_blowup_mem_edgeSet_iff, Sym2.isDiag_map (op_258_forces_of_forces_smul_blowup_emb_injective γ n p.1)]
    exact hz⟩
lemma op_258_forces_of_forces_smul_blowup_c0_push (γ n : ℕ)
    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+)
    (p : Fin γ × (SimpleGraph.completeGraph (Fin n)).edgeSet) :
    op_258_forces_of_forces_smul_blowup_c0 γ n c (op_258_forces_of_forces_smul_blowup_push γ n p) = c p.2 := by
  obtain ⟨r, ⟨z, hz⟩⟩ := p
  exact op_258_forces_of_forces_smul_blowup_lift_map γ n c r z hz
lemma op_258_forces_of_forces_smul_blowup_c0_mk (γ n : ℕ)
    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) {x y : Fin (γ * n)} (hxy : x ≠ y) :
    op_258_forces_of_forces_smul_blowup_c0 γ n c ⟨Sym2.mk x y, op_258_forces_of_forces_smul_blowup_mk_mem (γ * n) hxy⟩
      = op_258_forces_of_forces_smul_blowup_g γ n c x y := by
  simp only [op_258_forces_of_forces_smul_blowup_c0, op_258_forces_of_forces_smul_blowup_lift_mk]
lemma op_258_forces_of_forces_smul_blowup_c0_internal (γ n : ℕ)
    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+) {x y : Fin (γ * n)}
    (hb : op_258_forces_of_forces_smul_blowup_b γ n x = op_258_forces_of_forces_smul_blowup_b γ n y)
    (hq : op_258_forces_of_forces_smul_blowup_q γ n x ≠ op_258_forces_of_forces_smul_blowup_q γ n y) (hxy : x ≠ y) :
    op_258_forces_of_forces_smul_blowup_c0 γ n c ⟨Sym2.mk x y, op_258_forces_of_forces_smul_blowup_mk_mem (γ * n) hxy⟩
      = c ⟨Sym2.mk (op_258_forces_of_forces_smul_blowup_q γ n x) (op_258_forces_of_forces_smul_blowup_q γ n y),
            op_258_forces_of_forces_smul_blowup_mk_mem n hq⟩ := by
  rw [op_258_forces_of_forces_smul_blowup_c0_mk γ n c hxy]
  unfold op_258_forces_of_forces_smul_blowup_g
  rw [dif_pos ⟨hb, hq⟩]
lemma op_258_forces_of_forces_smul_blowup_card_bound (γ n : ℕ) (a : ℕ+ → ℝ) (hγ : 1 ≤ γ)
    (hpos : ∀ i, 0 < a i) (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+)
    (hc : op_258_bounded (fun i => (γ : ℝ) * a i) n c) (i : ℕ+) :
    ((((Finset.univ : Finset (Fin γ × (SimpleGraph.completeGraph (Fin n)).edgeSet)).image
        (op_258_forces_of_forces_smul_blowup_push γ n)).filter
          (fun e => op_258_forces_of_forces_smul_blowup_c0 γ n c e = i)).card : ℝ)
      ≤ a i * (((γ * n).choose 2) : ℝ) := by
  classical
  set F : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet :=
    (Finset.univ.filter (fun e => c e = i)) with hFdef
  set T : Finset (Fin γ × (SimpleGraph.completeGraph (Fin n)).edgeSet) :=
    (Finset.univ.filter (fun p => c p.2 = i)) with hTdef
  set A : Finset (SimpleGraph.completeGraph (Fin (γ * n))).edgeSet :=
    ((Finset.univ : Finset (Fin γ × (SimpleGraph.completeGraph (Fin n)).edgeSet)).image
        (op_258_forces_of_forces_smul_blowup_push γ n)).filter
          (fun e => op_258_forces_of_forces_smul_blowup_c0 γ n c e = i) with hAdef
  have hT : T = (Finset.univ : Finset (Fin γ)).product F := by
    ext p; simp [hTdef, hFdef]
  have hTcard : T.card = γ * F.card := by
    rw [hT]; simp
  have hsub : A ⊆ T.image (op_258_forces_of_forces_smul_blowup_push γ n) := by
    intro e he
    rw [hAdef] at he
    simp only [Finset.mem_filter, Finset.mem_image] at he
    obtain ⟨p, -, hp⟩ := he.1
    refine Finset.mem_image.mpr ⟨p, ?_, hp⟩
    rw [hTdef]
    simp only [Finset.mem_filter, Finset.mem_univ, true_and]
    rw [← op_258_forces_of_forces_smul_blowup_c0_push γ n c p, hp]
    exact he.2
  have hcardle : A.card ≤ T.card := by
    calc A.card ≤ (T.image (op_258_forces_of_forces_smul_blowup_push γ n)).card := Finset.card_le_card hsub
      _ ≤ T.card := Finset.card_image_le
  have hfib : (F.card : ℝ) ≤ (γ : ℝ) * a i * (n.choose 2 : ℝ) := by
    have hci := hc i
    rw [← hFdef] at hci
    simpa using hci
  have h1 : (A.card : ℝ) ≤ (T.card : ℝ) := by exact_mod_cast hcardle
  have h2 : (T.card : ℝ) = (γ : ℝ) * (F.card : ℝ) := by
    rw [hTcard]; push_cast; ring
  have hchoose := op_258_choose_two_mul_sq_le γ n hγ
  have hcast : ((γ ^ 2 * n.choose 2 : ℕ) : ℝ) = (γ : ℝ) ^ 2 * (n.choose 2 : ℝ) := by
    push_cast; ring
  calc (A.card : ℝ)
      ≤ (T.card : ℝ) := h1
    _ = (γ : ℝ) * (F.card : ℝ) := h2
    _ ≤ (γ : ℝ) * ((γ : ℝ) * a i * (n.choose 2 : ℝ)) := by gcongr
    _ = a i * ((γ : ℝ) ^ 2 * (n.choose 2 : ℝ)) := by ring
    _ = a i * ((γ ^ 2 * n.choose 2 : ℕ) : ℝ) := by rw [hcast]
    _ ≤ a i * (((γ * n).choose 2) : ℝ) :=
        mul_le_mul_of_nonneg_left hchoose (hpos i).le

/-- Forcing scales up: if a forces K_{γk} then γ·a forces K_k (one half of Proposition 1.2). -/
theorem op_258_forces_of_forces_smul_blowup (a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a)
    (hsum : 1 < ∑' i : ℕ+, ENNReal.ofReal (a i)) (γ k : ℕ) (hγ : 1 ≤ γ)
    (h : op_258_forces a (γ * k)) : op_258_forces (fun i => (γ : ℝ) * a i) k := by
  classical
  obtain ⟨n₀, hn₀⟩ := h
  obtain ⟨n₁, hn₁⟩ := op_258_bounded_extension a hpos hanti hsum
  refine ⟨max n₁ n₀, ?_⟩
  intro n hn c hc
  by_contra hno
  have hge : n ≤ γ * n := by
    calc n = 1 * n := (Nat.one_mul n).symm
      _ ≤ γ * n := Nat.mul_le_mul_right n hγ
  have hnN₁ : n₁ ≤ γ * n := le_trans (le_trans (le_max_left n₁ n₀) hn) hge
  have hnN₀ : n₀ ≤ γ * n := le_trans (le_trans (le_max_right n₁ n₀) hn) hge
  obtain ⟨c', hc'bound, hc'agree⟩ :=
    hn₁ (γ * n) hnN₁
      ((Finset.univ : Finset (Fin γ × (SimpleGraph.completeGraph (Fin n)).edgeSet)).image
        (op_258_forces_of_forces_smul_blowup_push γ n))
      (op_258_forces_of_forces_smul_blowup_c0 γ n c)
      (fun i => op_258_forces_of_forces_smul_blowup_card_bound γ n a hγ hpos c hc i)
  obtain ⟨S, i, hScard, hSmono⟩ := hn₀ (γ * n) hnN₀ c' hc'bound
  obtain ⟨r, hr⟩ := op_258_pigeonhole_blocks S γ k hγ (op_258_forces_of_forces_smul_blowup_b γ n) (by rw [hScard])
  obtain ⟨t, ht_sub, ht_card⟩ := Finset.exists_subset_card_eq hr
  refine hno ⟨t.image (op_258_forces_of_forces_smul_blowup_q γ n), i, ?_, ?_⟩
  · rw [Finset.card_image_of_injOn, ht_card]
    intro x hx y hy hq
    have hbx : op_258_forces_of_forces_smul_blowup_b γ n x = r := (Finset.mem_filter.mp (ht_sub hx)).2
    have hby : op_258_forces_of_forces_smul_blowup_b γ n y = r := (Finset.mem_filter.mp (ht_sub hy)).2
    exact op_258_forces_of_forces_smul_blowup_eq_of_bq γ n (hbx.trans hby.symm) hq
  · intro u v hu hv huv
    simp only [Finset.mem_image] at hu hv
    obtain ⟨x, hx, rfl⟩ := hu
    obtain ⟨y, hy, rfl⟩ := hv
    have hxS : x ∈ S := (Finset.mem_filter.mp (ht_sub hx)).1
    have hyS : y ∈ S := (Finset.mem_filter.mp (ht_sub hy)).1
    have hbx : op_258_forces_of_forces_smul_blowup_b γ n x = r := (Finset.mem_filter.mp (ht_sub hx)).2
    have hby : op_258_forces_of_forces_smul_blowup_b γ n y = r := (Finset.mem_filter.mp (ht_sub hy)).2
    have hxy : x ≠ y := by intro e; exact huv (by rw [e])
    have hmono' : c' ⟨Sym2.mk x y, op_258_forces_of_forces_smul_blowup_mk_mem (γ * n) hxy⟩ = i :=
      hSmono hxS hyS hxy
    have hmem : (⟨Sym2.mk x y, op_258_forces_of_forces_smul_blowup_mk_mem (γ * n) hxy⟩ :
          (SimpleGraph.completeGraph (Fin (γ * n))).edgeSet) ∈
        ((Finset.univ : Finset (Fin γ × (SimpleGraph.completeGraph (Fin n)).edgeSet)).image
          (op_258_forces_of_forces_smul_blowup_push γ n)) := by
      apply Finset.mem_image.mpr
      refine ⟨(r, ⟨Sym2.mk (op_258_forces_of_forces_smul_blowup_q γ n x) (op_258_forces_of_forces_smul_blowup_q γ n y),
        op_258_forces_of_forces_smul_blowup_mk_mem n huv⟩), Finset.mem_univ _, ?_⟩
      apply Subtype.ext
      show Sym2.map (op_258_forces_of_forces_smul_blowup_emb γ n r)
          (Sym2.mk (op_258_forces_of_forces_smul_blowup_q γ n x) (op_258_forces_of_forces_smul_blowup_q γ n y)) = Sym2.mk x y
      rw [Sym2.map_mk,
        show op_258_forces_of_forces_smul_blowup_emb γ n r (op_258_forces_of_forces_smul_blowup_q γ n x) = x from by
          rw [← hbx]; exact op_258_forces_of_forces_smul_blowup_emb_bq γ n x,
        show op_258_forces_of_forces_smul_blowup_emb γ n r (op_258_forces_of_forces_smul_blowup_q γ n y) = y from by
          rw [← hby]; exact op_258_forces_of_forces_smul_blowup_emb_bq γ n y]
    have hagree := hc'agree _ hmem
    have hc0 := op_258_forces_of_forces_smul_blowup_c0_internal γ n c (hbx.trans hby.symm) huv hxy
    have hfin : c ⟨Sym2.mk (op_258_forces_of_forces_smul_blowup_q γ n x) (op_258_forces_of_forces_smul_blowup_q γ n y),
        op_258_forces_of_forces_smul_blowup_mk_mem n huv⟩ = i := by
      rw [← hc0, ← hagree]
      exact hmono'
    convert hfin
See it in the graphDiscuss this resultChallenge it