AFTD Auto-Formalizing Theoretical Domains

op_258_hypercube_bipartite_decomposition

theoremverified

For any l ≥ 1, the edge set of the complete graph on 2^l vertices can be partitioned into l bipartite layers (indexed by the first differing bit under a hypercube bijection) such that layer j has at most 2^{2l - 2 - j} edges.

Statement

theorem op_258_hypercube_bipartite_decomposition (l : ℕ) (hl : 1 ≤ l) :
    ∃ (layer : (SimpleGraph.completeGraph (Fin (2^l))).edgeSet → Fin l)
      (f : Fin l → Fin (2^l) → Fin 2),
      (∀ (u v : Fin (2^l)) (hne : u ≠ v),
        f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) u ≠
        f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) v) ∧
      (∀ j : Fin l,
        ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin (2^l))).edgeSet).filter
          (fun e => layer e = j)).card ≤ 2 ^ (2 * l - 2 - (j : ℕ)))
Source
step towards op_258_sum_ne_top_of_forces_three
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • bitThe real embedding of a Boolean value, sending false to 0 and true to 1.
Used by 1
  • op_258_sum_ne_top_of_forces_threeIf a positive antitone profile a forces a monochromatic triangle K_3 on sufficiently large complete graphs, then the infinite sum of a_i…

The proof, explained

The theorem partitions the edge set of the complete graph on 2^l vertices into l bipartite layers indexed by j ∈ {0, …, l - 1}, where each edge {u, v} is assigned to layer j = l - 1 - p with p = ⌊log₂(u ^^^ v)⌋ being the index of the highest differing bit between u and v. Layer j is bipartite because coloring each vertex by its p-th bit gives distinct colors to the endpoints of every edge in that layer. The size of layer j is bounded by mapping each edge injectively to a key triple consisting of the common quotient of its endpoints by 2^(p + 1) (which is in [0, 2^(l - 1 - p))) and the two remainders modulo 2^p (each in [0, 2^p)), sorted so the endpoint with p-th bit 0 comes first; the size of this product set is 2^(l - 1 - p) · 2^p · 2^p = 2^(2l - 2 - j).

  1. If u ≠ v, then u ^^^ v ≠ 0.

    By contradiction: if u ^^^ v = 0, then every bit of u ^^^ v is false. Because the i-th bit of u ^^^ v is the boolean XOR of the i-th bits of u and v, matching bits must be equal for every index i. By extensionality on bits, u = v, contradicting u ≠ v.

    lines 1–10

    uses Nat.eq_of_testBit_eq, congrArg, Nat.testBit_xor, Nat.zero_testBit

    lemma op_258_hypercube_bipartite_decomposition_xor_ne {u v : ℕ} (h : u ≠ v) : u ^^^ v ≠ 0 := by
      intro h0
      apply h
      apply Nat.eq_of_testBit_eq
      intro i
      have := congrArg (fun n => n.testBit i) h0
      simp only [Nat.testBit_xor, Nat.zero_testBit] at this
      revert this
      cases u.testBit i <;> cases v.testBit i <;> simp
    
  2. The prefixes of u and v strictly above their highest differing bit are identical: u / 2^(p + 1) = v / 2^(p + 1) where p = ⌊log₂(u ^^^ v)⌋.

    It suffices to show that bit i of u / 2^(p + 1) matches bit i of v / 2^(p + 1) for every i. Bit i of the quotient corresponds to bit i + p + 1 of the original numbers. Since u ^^^ v < 2^(p + 1) ≤ 2^(i + p + 1), bit i + p + 1 of u ^^^ v is false, so bits i + p + 1 of u and v must agree.

    lines 11–22

    uses Nat.eq_of_testBit_eq, Nat.testBit_div_two_pow, lt_of_lt_of_le, Nat.lt_log2_self, Nat.pow_le_pow_right, Nat.testBit_eq_false_of_lt, Nat.testBit_xor

    lemma op_258_hypercube_bipartite_decomposition_hi {u v : ℕ} (h : u ≠ v) :
        u / 2 ^ ((u ^^^ v).log2 + 1) = v / 2 ^ ((u ^^^ v).log2 + 1) := by
      apply Nat.eq_of_testBit_eq
      intro i
      rw [Nat.testBit_div_two_pow, Nat.testBit_div_two_pow]
      have hlt : u ^^^ v < 2 ^ (i + ((u ^^^ v).log2 + 1)) :=
        lt_of_lt_of_le Nat.lt_log2_self (Nat.pow_le_pow_right (by norm_num) (by omega))
      have := Nat.testBit_eq_false_of_lt hlt
      rw [Nat.testBit_xor] at this
      revert this
      cases u.testBit (i + ((u ^^^ v).log2 + 1)) <;> cases v.testBit (i + ((u ^^^ v).log2 + 1)) <;> simp
    
  3. The p-th bits of u and v differ, where p = ⌊log₂(u ^^^ v)⌋.

    Since u ≠ v, u ^^^ v is nonzero, so its most significant bit at index p is true. Thus the boolean XOR of the p-th bits of u and v is true, meaning they cannot be equal.

    lines 23–29

    uses Nat.testBit_log2, op_258_hypercube_bipartite_decomposition_xor_ne, Nat.testBit_xor

    lemma op_258_hypercube_bipartite_decomposition_bit {u v : ℕ} (h : u ≠ v) :
        u.testBit (u ^^^ v).log2 ≠ v.testBit (u ^^^ v).log2 := by
      have := Nat.testBit_log2 (op_258_hypercube_bipartite_decomposition_xor_ne h)
      rw [Nat.testBit_xor] at this
      revert this
      cases u.testBit (u ^^^ v).log2 <;> cases v.testBit (u ^^^ v).log2 <;> simp
    
  4. Any natural number x is uniquely determined by its high quotient x / 2^(p + 1), its p-th bit, and its remainder x % 2^p.

    To prove x = y, test whether bit i of x equals bit i of y for all i. Trichotomy on i compared to p breaks this into three cases: if i < p, the bits are determined by the remainders modulo 2^p; if i = p, they are given by the assumed equality of the p-th bits; if i > p, they are determined by the quotients upon division by 2^(p + 1).

    lines 30–42

    uses Nat.eq_of_testBit_eq, lt_trichotomy, congrArg, Nat.testBit_mod_two_pow, Nat.testBit_div_two_pow, Nat.sub_add_cancel

    lemma op_258_hypercube_bipartite_decomposition_recon {p x y : ℕ}
        (hd : x / 2 ^ (p + 1) = y / 2 ^ (p + 1)) (hb : x.testBit p = y.testBit p)
        (hm : x % 2 ^ p = y % 2 ^ p) : x = y := by
      apply Nat.eq_of_testBit_eq
      intro i
      rcases lt_trichotomy i p with hi | hi | hi
      · have := congrArg (fun n => n.testBit i) hm
        simpa [Nat.testBit_mod_two_pow, hi] using this
      · subst hi; exact hb
      · have := congrArg (fun n => n.testBit (i - (p + 1))) hd
        simp only [Nat.testBit_div_two_pow] at this
        rwa [Nat.sub_add_cancel (by omega)] at this
    
  5. The key encoding on unordered pairs of endpoints is symmetric: key p u v = key p v u.

    The definition sorts the two lower remainders according to whether the p-th bit is clear or set. Unfolding the definition and splitting into cases on the boolean values of the p-th bits confirms that swapping u and v produces the identical triple.

    lines 43–53

    def op_258_hypercube_bipartite_decomposition_key (p u v : ℕ) : ℕ × ℕ × ℕ :=
      if u.testBit p = v.testBit p then (0, 0, 0)
      else if u.testBit p then (v / 2 ^ (p + 1), v % 2 ^ p, u % 2 ^ p)
      else (u / 2 ^ (p + 1), u % 2 ^ p, v % 2 ^ p)
    
    lemma op_258_hypercube_bipartite_decomposition_key_symm (p u v : ℕ) :
        op_258_hypercube_bipartite_decomposition_key p u v =
          op_258_hypercube_bipartite_decomposition_key p v u := by
      unfold op_258_hypercube_bipartite_decomposition_key
      cases u.testBit p <;> cases v.testBit p <;> simp
    
  6. The key encoding injectively reconstructs the pair of endpoints.

    Given that two pairs (a₁, b₁) and (a₂, b₂) have bit p clear on a_i, bit p set on b_i, equal high quotients, and identical key triples, we apply the reconstruction lemma separately to deduce a₁ = a₂ from their matching quotient, clear p-th bit, and remainder, and b₁ = b₂ from their quotient, set p-th bit, and remainder.

    lines 54–66

    uses Prod.mk.injEq, op_258_hypercube_bipartite_decomposition_recon

    lemma op_258_hypercube_bipartite_decomposition_key_inj {p a1 b1 a2 b2 : ℕ}
        (hab1 : a1 / 2 ^ (p + 1) = b1 / 2 ^ (p + 1)) (hab2 : a2 / 2 ^ (p + 1) = b2 / 2 ^ (p + 1))
        (ha1 : a1.testBit p = false) (hb1 : b1.testBit p = true)
        (ha2 : a2.testBit p = false) (hb2 : b2.testBit p = true)
        (h : (a1 / 2 ^ (p + 1), a1 % 2 ^ p, b1 % 2 ^ p) = (a2 / 2 ^ (p + 1), a2 % 2 ^ p, b2 % 2 ^ p)) :
        a1 = a2 ∧ b1 = b2 := by
      simp only [Prod.mk.injEq] at h
      obtain ⟨h1, h2, h3⟩ := h
      exact ⟨op_258_hypercube_bipartite_decomposition_recon h1 (by rw [ha1, ha2]) h2,
        op_258_hypercube_bipartite_decomposition_recon (by rw [← hab1, h1, hab2]) (by rw [hb1, hb2]) h3⟩
    
    /-- On an edge whose highest differing bit is `p`, the key lists the high part, then the low
    part of the endpoint with bit `p` clear, then that of the other. -/
  7. When the p-th bits of u and v differ, the key function reduces to its conditional branch on bit p.

    Because the p-th bits are not equal, the initial equality guard evaluates to false, leaving only the branch that sorts the endpoints according to which one has bit p set.

    lines 67–74

    uses if_neg

    lemma op_258_hypercube_bipartite_decomposition_key_eq {p u v : ℕ}
        (hd : u.testBit p ≠ v.testBit p) :
        op_258_hypercube_bipartite_decomposition_key p u v =
          if u.testBit p then (v / 2 ^ (p + 1), v % 2 ^ p, u % 2 ^ p)
          else (u / 2 ^ (p + 1), u % 2 ^ p, v % 2 ^ p) := by
      unfold op_258_hypercube_bipartite_decomposition_key
      rw [if_neg hd]
    
  8. For any distinct vertices u and v of Fin (2^l), the highest differing bit p satisfies p < l, their quotients above p match, and their p-th bits differ.

    Symmetry of bitwise XOR implies that ⌊log₂(u ^^^ v)⌋ is invariant under swapping u and v. Since u, v < 2^l, their XOR is strictly less than 2^l, so p = ⌊log₂(u ^^^ v)⌋ < l. The quotient match and differing p-th bit then follow directly from the previous lemmas.

    lines 75–98

    uses SimpleGraph.completeGraph_eq_top, Nat.xor_comm, Nat.log2_lt, op_258_hypercube_bipartite_decomposition_xor_ne, Nat.xor_lt_two_pow, op_258_hypercube_bipartite_decomposition_hi, op_258_hypercube_bipartite_decomposition_bit

    /-- Bipartite layering of the complete graph on 2^l vertices with layer bounds 2^{2l - 2 - j}. -/
    theorem op_258_hypercube_bipartite_decomposition (l : ℕ) (hl : 1 ≤ l) :
        ∃ (layer : (SimpleGraph.completeGraph (Fin (2^l))).edgeSet → Fin l)
          (f : Fin l → Fin (2^l) → Fin 2),
          (∀ (u v : Fin (2^l)) (hne : u ≠ v),
            f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) u ≠
            f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) v) ∧
          (∀ j : Fin l,
            ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin (2^l))).edgeSet).filter
              (fun e => layer e = j)).card ≤ 2 ^ (2 * l - 2 - (j : ℕ))) := by
      classical
      -- the level of an edge: its highest differing bit
      have hsym : ∀ a b : Fin (2 ^ l), (a.val ^^^ b.val).log2 = (b.val ^^^ a.val).log2 := by
        intro a b; rw [Nat.xor_comm]
      -- facts about an edge `s(u, v)`
      have hfacts : ∀ u v : Fin (2 ^ l), u.val ≠ v.val →
          (u.val ^^^ v.val).log2 < l ∧
          u.val / 2 ^ ((u.val ^^^ v.val).log2 + 1) = v.val / 2 ^ ((u.val ^^^ v.val).log2 + 1) ∧
          u.val.testBit (u.val ^^^ v.val).log2 ≠ v.val.testBit (u.val ^^^ v.val).log2 := by
        intro u v h
        exact ⟨(Nat.log2_lt (op_258_hypercube_bipartite_decomposition_xor_ne h)).mpr
            (Nat.xor_lt_two_pow u.isLt v.isLt),
          op_258_hypercube_bipartite_decomposition_hi h,
          op_258_hypercube_bipartite_decomposition_bit h⟩
  9. Define the edge layering function and vertex coloring candidates for each layer.

    Each edge e = s(u, v) is assigned to layer j = l - 1 - p ∈ Fin l, where p = ⌊log₂(u ^^^ v)⌋ is the highest differing bit, lifted to unordered pairs via Sym2.lift. The coloring f for layer j maps a vertex w to 1 if bit l - 1 - j is set and 0 otherwise.

    lines 99–101

    uses Sym2.lift

      refine ⟨fun e => ⟨l - 1 - Sym2.lift ⟨fun a b : Fin (2 ^ l) => (a.val ^^^ b.val).log2, hsym⟩ e.1,
          by omega⟩,
        fun j w => if w.val.testBit (l - 1 - j.val) then 1 else 0, ?_, ?_⟩
  10. The vertex coloring f properly 2-colors the edges of each layer, showing that each layer is bipartite.

    For an edge s(u, v) in layer j = l - 1 - p, evaluating the coloring checks bit l - 1 - j = p. By definition of p, the p-th bit of u and the p-th bit of v are distinct, so f j u ≠ f j v.

    lines 102–109

    uses Fin.ext, Sym2.lift_mk

      · intro u v hne
        have hne' : u.val ≠ v.val := fun h => hne (Fin.ext h)
        obtain ⟨hlt, -, hb⟩ := hfacts u v hne'
        have e : l - 1 - (l - 1 - (u.val ^^^ v.val).log2) = (u.val ^^^ v.val).log2 := by omega
        simp only [Sym2.lift_mk, Fin.val_mk, e]
        revert hb
        cases u.val.testBit (u.val ^^^ v.val).log2 <;>
          cases v.val.testBit (u.val ^^^ v.val).log2 <;> decide
  11. Any edge belonging to layer j has highest differing bit p = l - 1 - j and connects distinct vertices.

    Setting p = l - 1 - j, an edge whose layer index is j has l - 1 - ⌊log₂(u ^^^ v)⌋ = j, which rearranges to ⌊log₂(u ^^^ v)⌋ = p. Moreover, edges of the complete graph connect strictly distinct vertices.

    lines 110–123

    uses SimpleGraph.completeGraph_eq_top, Fin.ext

      · intro j
        have hj : j.val < l := j.isLt
        set p := l - 1 - j.val with hp
        -- an edge of layer `j` has highest differing bit `p`
        have hlevel : ∀ (u v : Fin (2 ^ l)), u.val ≠ v.val →
            l - 1 - (u.val ^^^ v.val).log2 = j.val → (u.val ^^^ v.val).log2 = p := by
          intro u v h h'
          have := (hfacts u v h).1
          omega
        have hne_of : ∀ (u v : Fin (2 ^ l)),
            s(u, v) ∈ (SimpleGraph.completeGraph (Fin (2 ^ l))).edgeSet → u.val ≠ v.val := by
          intro u v h huv
          apply (show u ≠ v by simpa [SimpleGraph.completeGraph_eq_top] using h)
          exact Fin.ext huv
  12. The number of edges in layer j is at most the cardinality of range(2^(l - 1 - p)) × range(2^p) × range(2^p).

    By Finset.card_le_card_of_injOn, the size of layer j is bounded by the cardinality of this product of ranges, provided the key encoding maps layer j edges into the product and is injective on them.

    lines 124–130

    uses Sym2.lift, Finset.card_le_card_of_injOn, op_258_hypercube_bipartite_decomposition_key_symm

        calc ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin (2^l))).edgeSet).filter
              (fun e => (⟨l - 1 - Sym2.lift ⟨fun a b : Fin (2 ^ l) => (a.val ^^^ b.val).log2, hsym⟩ e.1,
                by omega⟩ : Fin l) = j)).card
            ≤ (Finset.range (2 ^ (l - 1 - p)) ×ˢ Finset.range (2 ^ p) ×ˢ Finset.range (2 ^ p)).card := by
              refine Finset.card_le_card_of_injOn (fun e => Sym2.lift
                ⟨fun a b : Fin (2 ^ l) => op_258_hypercube_bipartite_decomposition_key p a.val b.val,
                  fun a b => op_258_hypercube_bipartite_decomposition_key_symm p _ _⟩ e.1) ?_ ?_
  13. The key of any edge in layer j belongs to range(2^(l - 1 - p)) × range(2^p) × range(2^p).

    For any vertex w < 2^l, the quotient w / 2^(p + 1) is strictly less than 2^(l - 1 - p) because 2^(l - 1 - p) * 2^(p + 1) = 2^l. Both lower remainders modulo 2^p are strictly bounded by 2^p by definition of remainder.

    lines 131–152

    uses Sym2.lift_mk, op_258_hypercube_bipartite_decomposition_key_eq, pow_add, Nat.div_lt_iff_lt_mul, Nat.mod_lt

              · intro e he
                have he' := congrArg Fin.val (Finset.mem_filter.mp (Finset.mem_coe.mp he)).2
                obtain ⟨e, hee⟩ := e
                induction e using Sym2.ind with
                | h u v =>
                  have huv := hne_of u v hee
                  simp only [Sym2.lift_mk] at he'
                  have hX := hlevel u v huv he'
                  obtain ⟨-, hhi, hb⟩ := hfacts u v huv
                  rw [hX] at hhi hb
                  simp only [Sym2.lift_mk, Finset.coe_product, Finset.coe_range, Set.mem_prod,
                    Set.mem_Iio, Finset.mem_coe, Finset.mem_product, Finset.mem_range]
                  rw [op_258_hypercube_bipartite_decomposition_key_eq hb]
                  have hpow : 2 ^ (l - 1 - p) * 2 ^ (p + 1) = 2 ^ l := by
                    rw [← pow_add]; congr 1; omega
                  have hdiv : ∀ w : Fin (2 ^ l), w.val / 2 ^ (p + 1) < 2 ^ (l - 1 - p) := by
                    intro w
                    rw [Nat.div_lt_iff_lt_mul (by positivity), hpow]
                    exact w.isLt
                  split_ifs
                  · exact ⟨hdiv v, Nat.mod_lt _ (by positivity), Nat.mod_lt _ (by positivity)⟩
                  · exact ⟨hdiv u, Nat.mod_lt _ (by positivity), Nat.mod_lt _ (by positivity)⟩
  14. The key encoding is injective on the edges of layer j.

    Given two edges e₁ and e₂ in layer j that produce the same key, both have highest differing bit p. By case analysis on which endpoint of each edge has bit p clear and which has it set, the reconstruction lemma applies to identify the endpoints, up to edge symmetry (Sym2.eq_swap), showing e₁ = e₂.

    lines 153–190

    uses Sym2.lift_mk, op_258_hypercube_bipartite_decomposition_key_eq, Subtype.ext, op_258_hypercube_bipartite_decomposition_key_inj, Fin.ext, Sym2.eq_swap

              · intro e1 he1 e2 he2 heq
                have he1' := congrArg Fin.val (Finset.mem_filter.mp (Finset.mem_coe.mp he1)).2
                have he2' := congrArg Fin.val (Finset.mem_filter.mp (Finset.mem_coe.mp he2)).2
                obtain ⟨e1, hee1⟩ := e1
                obtain ⟨e2, hee2⟩ := e2
                induction e1 using Sym2.ind with
                | h u1 v1 =>
                induction e2 using Sym2.ind with
                | h u2 v2 =>
                  have huv1 := hne_of u1 v1 hee1
                  have huv2 := hne_of u2 v2 hee2
                  simp only [Sym2.lift_mk] at he1' he2' heq
                  have hX1 := hlevel u1 v1 huv1 he1'
                  have hX2 := hlevel u2 v2 huv2 he2'
                  obtain ⟨-, hhi1, hb1⟩ := hfacts u1 v1 huv1
                  obtain ⟨-, hhi2, hb2⟩ := hfacts u2 v2 huv2
                  rw [hX1] at hhi1 hb1
                  rw [hX2] at hhi2 hb2
                  rw [op_258_hypercube_bipartite_decomposition_key_eq hb1,
                    op_258_hypercube_bipartite_decomposition_key_eq hb2] at heq
                  apply Subtype.ext
                  show s(u1, v1) = s(u2, v2)
                  cases hu1 : u1.val.testBit p <;> cases hv1 : v1.val.testBit p <;>
                    cases hu2 : u2.val.testBit p <;> cases hv2 : v2.val.testBit p <;>
                    simp only [hu1, hv1, hu2, hv2, ne_eq, eq_self_iff_true, not_true_eq_false, not_false_eq_true, Bool.false_eq_true, Bool.true_eq_false,
                      if_true, if_false] at hb1 hb2 heq ⊢
                  · obtain ⟨h1, h2⟩ := op_258_hypercube_bipartite_decomposition_key_inj
                      hhi1 hhi2 hu1 hv1 hu2 hv2 heq
                    rw [Fin.ext h1, Fin.ext h2]
                  · obtain ⟨h1, h2⟩ := op_258_hypercube_bipartite_decomposition_key_inj
                      hhi1 hhi2.symm hu1 hv1 hv2 hu2 heq
                    rw [Fin.ext h1, Fin.ext h2, Sym2.eq_swap]
                  · obtain ⟨h1, h2⟩ := op_258_hypercube_bipartite_decomposition_key_inj
                      hhi1.symm hhi2 hv1 hu1 hu2 hv2 heq
                    rw [← Fin.ext h1, ← Fin.ext h2, Sym2.eq_swap]
                  · obtain ⟨h1, h2⟩ := op_258_hypercube_bipartite_decomposition_key_inj
                      hhi1.symm hhi2.symm hv1 hu1 hv2 hu2 heq
                    rw [Fin.ext h1, Fin.ext h2]
  15. The product set cardinality equals 2^(2l - 2 - j).

    The cardinality of range(2^(l - 1 - p)) × range(2^p) × range(2^p) is the product 2^(l - 1 - p) * 2^p * 2^p = 2^(l - 1 + p). Substituting p = l - 1 - j yields exponent (l - 1) + (l - 1 - j) = 2l - 2 - j.

    lines 191–194

    uses Finset.card_product, Finset.card_range, pow_add

          _ = 2 ^ (2 * l - 2 - (j : ℕ)) := by
              simp only [Finset.card_product, Finset.card_range, ← pow_add]
              congr 1
              omega
Nat.eq_of_testBit_eq
Two natural numbers are equal if all their corresponding bits are equal.
congrArg
Applying a function to both sides of an equality yields an equality.
Nat.testBit_xor
The i-th bit of x XOR y is the boolean XOR of the i-th bit of x and the i-th bit of y.
Nat.zero_testBit
Every bit of 0 is false.
Nat.testBit_div_two_pow
The i-th bit of x / 2^n is the (i + n)-th bit of x.
lt_of_lt_of_le
Strict inequality is transitive with non-strict inequality: if a < b and b ≤ c, then a < c.
Nat.lt_log2_self
Every natural number n is strictly less than 2^(⌊log₂ n⌋ + 1).
Nat.pow_le_pow_right
For base n > 0, exponentiation preserves non-strict inequality: if i ≤ j, then n^i ≤ n^j.
Nat.testBit_eq_false_of_lt
If n < 2^i, then the i-th bit of n is false.
Nat.testBit_log2
For any nonzero natural number n, the bit at index ⌊log₂ n⌋ is true (the most significant bit is 1).
op_258_hypercube_bipartite_decomposition_xor_ne
If u ≠ v, then their bitwise XOR u ^^^ v is nonzero.
lt_trichotomy
Any two elements in a linear order satisfy a < b, a = b, or b < a.
Nat.testBit_mod_two_pow
The i-th bit of x % 2^j equals the i-th bit of x when i < j, and is false otherwise.
Nat.sub_add_cancel
If m ≤ n, then (n - m) + m = n.
Prod.mk.injEq
Two ordered pairs are equal if and only if their respective components are equal.
op_258_hypercube_bipartite_decomposition_recon
A natural number is uniquely determined by its quotient by 2^(p + 1), its p-th bit, and its remainder modulo 2^p.
if_neg
If a proposition c is false, then (if c then t else e) evaluates to e.
Nat.xor_comm
Bitwise XOR is commutative.
Nat.log2_lt
For nonzero n, ⌊log₂ n⌋ < k if and only if n < 2^k.
Nat.xor_lt_two_pow
If x < 2^n and y < 2^n, then x ^^^ y < 2^n.
op_258_hypercube_bipartite_decomposition_hi
Two distinct natural numbers u and v have identical quotients when divided by 2^(⌊log₂(u ^^^ v)⌋ + 1).
op_258_hypercube_bipartite_decomposition_bit
Two distinct natural numbers u and v have differing bits at index ⌊log₂(u ^^^ v)⌋.
Sym2.lift
Lifts a symmetric binary operation to a well-defined function on unordered pairs.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural values are equal.
Sym2.lift_mk
Evaluating a lifted symmetric function on an unordered pair s(a, b) yields the function applied to (a, b).
SimpleGraph.completeGraph_eq_top
The complete graph is the top element of SimpleGraph, containing all distinct pairs of vertices as edges.
Finset.card_le_card_of_injOn
If a function maps a finite set s into a finite set t and is injective on s, then |s| ≤ |t|.
op_258_hypercube_bipartite_decomposition_key_symm
The key encoding function on triples (p, u, v) is symmetric in u and v.
op_258_hypercube_bipartite_decomposition_key_eq
When the p-th bits of u and v differ, the key function evaluates directly to the common high quotient and the lower remainders ordered by the p-th bit.
pow_add
Exponents add under multiplication of powers: a^(m + n) = a^m * a^n.
Nat.div_lt_iff_lt_mul
For positive k, x / k < y is equivalent to x < y * k.
Nat.mod_lt
For positive y, x % y < y.
Subtype.ext
Two terms of a subtype are equal if their underlying values are equal.
op_258_hypercube_bipartite_decomposition_key_inj
The key encoding uniquely determines a pair of endpoints with differing p-th bits and equal high quotients.
Sym2.eq_swap
Unordered pairs are symmetric: s(a, b) = s(b, a).
Finset.card_product
The cardinality of the Cartesian product of two finite sets is the product of their cardinalities.
Finset.card_range
The cardinality of Finset.range n is n.

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

lemma op_258_hypercube_bipartite_decomposition_xor_ne {u v : ℕ} (h : u ≠ v) : u ^^^ v ≠ 0 := by  intro h0  apply h  apply Nat.eq_of_testBit_eq  intro i  have := congrArg (fun n => n.testBit i) h0  simp only [Nat.testBit_xor, Nat.zero_testBit] at this  revert this  cases u.testBit i <;> cases v.testBit i <;> simplemma op_258_hypercube_bipartite_decomposition_hi {u v : ℕ} (h : u ≠ v) :    u / 2 ^ ((u ^^^ v).log2 + 1) = v / 2 ^ ((u ^^^ v).log2 + 1) := by  apply Nat.eq_of_testBit_eq  intro i  rw [Nat.testBit_div_two_pow, Nat.testBit_div_two_pow]  have hlt : u ^^^ v < 2 ^ (i + ((u ^^^ v).log2 + 1)) :=    lt_of_lt_of_le Nat.lt_log2_self (Nat.pow_le_pow_right (by norm_num) (by omega))  have := Nat.testBit_eq_false_of_lt hlt  rw [Nat.testBit_xor] at this  revert this  cases u.testBit (i + ((u ^^^ v).log2 + 1)) <;> cases v.testBit (i + ((u ^^^ v).log2 + 1)) <;> simplemma op_258_hypercube_bipartite_decomposition_bit {u v : ℕ} (h : u ≠ v) :    u.testBit (u ^^^ v).log2 ≠ v.testBit (u ^^^ v).log2 := by  have := Nat.testBit_log2 (op_258_hypercube_bipartite_decomposition_xor_ne h)  rw [Nat.testBit_xor] at this  revert this  cases u.testBit (u ^^^ v).log2 <;> cases v.testBit (u ^^^ v).log2 <;> simplemma op_258_hypercube_bipartite_decomposition_recon {p x y : ℕ}    (hd : x / 2 ^ (p + 1) = y / 2 ^ (p + 1)) (hb : x.testBit p = y.testBit p)    (hm : x % 2 ^ p = y % 2 ^ p) : x = y := by  apply Nat.eq_of_testBit_eq  intro i  rcases lt_trichotomy i p with hi | hi | hi  · have := congrArg (fun n => n.testBit i) hm    simpa [Nat.testBit_mod_two_pow, hi] using this  · subst hi; exact hb  · have := congrArg (fun n => n.testBit (i - (p + 1))) hd    simp only [Nat.testBit_div_two_pow] at this    rwa [Nat.sub_add_cancel (by omega)] at thisdef op_258_hypercube_bipartite_decomposition_key (p u v : ℕ) : ℕ × ℕ × ℕ :=  if u.testBit p = v.testBit p then (0, 0, 0)  else if u.testBit p then (v / 2 ^ (p + 1), v % 2 ^ p, u % 2 ^ p)  else (u / 2 ^ (p + 1), u % 2 ^ p, v % 2 ^ p)lemma op_258_hypercube_bipartite_decomposition_key_symm (p u v : ℕ) :    op_258_hypercube_bipartite_decomposition_key p u v =      op_258_hypercube_bipartite_decomposition_key p v u := by  unfold op_258_hypercube_bipartite_decomposition_key  cases u.testBit p <;> cases v.testBit p <;> simplemma op_258_hypercube_bipartite_decomposition_key_inj {p a1 b1 a2 b2 : ℕ}    (hab1 : a1 / 2 ^ (p + 1) = b1 / 2 ^ (p + 1)) (hab2 : a2 / 2 ^ (p + 1) = b2 / 2 ^ (p + 1))    (ha1 : a1.testBit p = false) (hb1 : b1.testBit p = true)    (ha2 : a2.testBit p = false) (hb2 : b2.testBit p = true)    (h : (a1 / 2 ^ (p + 1), a1 % 2 ^ p, b1 % 2 ^ p) = (a2 / 2 ^ (p + 1), a2 % 2 ^ p, b2 % 2 ^ p)) :    a1 = a2 ∧ b1 = b2 := by  simp only [Prod.mk.injEq] at h  obtain ⟨h1, h2, h3⟩ := h  exact ⟨op_258_hypercube_bipartite_decomposition_recon h1 (by rw [ha1, ha2]) h2,    op_258_hypercube_bipartite_decomposition_recon (by rw [← hab1, h1, hab2]) (by rw [hb1, hb2]) h3⟩/-- On an edge whose highest differing bit is `p`, the key lists the high part, then the lowpart of the endpoint with bit `p` clear, then that of the other. -/lemma op_258_hypercube_bipartite_decomposition_key_eq {p u v : ℕ}    (hd : u.testBit p ≠ v.testBit p) :    op_258_hypercube_bipartite_decomposition_key p u v =      if u.testBit p then (v / 2 ^ (p + 1), v % 2 ^ p, u % 2 ^ p)      else (u / 2 ^ (p + 1), u % 2 ^ p, v % 2 ^ p) := by  unfold op_258_hypercube_bipartite_decomposition_key  rw [if_neg hd]/-- Bipartite layering of the complete graph on 2^l vertices with layer bounds 2^{2l - 2 - j}. -/theorem op_258_hypercube_bipartite_decomposition (l : ℕ) (hl : 1 ≤ l) :    ∃ (layer : (SimpleGraph.completeGraph (Fin (2^l))).edgeSet → Fin l)      (f : Fin l → Fin (2^l) → Fin 2),      (∀ (u v : Fin (2^l)) (hne : u ≠ v),        f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) u ≠        f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) v) ∧      (∀ j : Fin l,        ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin (2^l))).edgeSet).filter          (fun e => layer e = j)).card ≤ 2 ^ (2 * l - 2 - (j : ℕ))) := by  classical  -- the level of an edge: its highest differing bit  have hsym : ∀ a b : Fin (2 ^ l), (a.val ^^^ b.val).log2 = (b.val ^^^ a.val).log2 := by    intro a b; rw [Nat.xor_comm]  -- facts about an edge `s(u, v)`  have hfacts : ∀ u v : Fin (2 ^ l), u.val ≠ v.val →      (u.val ^^^ v.val).log2 < l ∧      u.val / 2 ^ ((u.val ^^^ v.val).log2 + 1) = v.val / 2 ^ ((u.val ^^^ v.val).log2 + 1) ∧      u.val.testBit (u.val ^^^ v.val).log2 ≠ v.val.testBit (u.val ^^^ v.val).log2 := by    intro u v h    exact ⟨(Nat.log2_lt (op_258_hypercube_bipartite_decomposition_xor_ne h)).mpr        (Nat.xor_lt_two_pow u.isLt v.isLt),      op_258_hypercube_bipartite_decomposition_hi h,      op_258_hypercube_bipartite_decomposition_bit h⟩  refine ⟨fun e => ⟨l - 1 - Sym2.lift ⟨fun a b : Fin (2 ^ l) => (a.val ^^^ b.val).log2, hsym⟩ e.1,      by omega⟩,    fun j w => if w.val.testBit (l - 1 - j.val) then 1 else 0, ?_, ?_⟩  · intro u v hne    have hne' : u.val ≠ v.val := fun h => hne (Fin.ext h)    obtain ⟨hlt, -, hb⟩ := hfacts u v hne'    have e : l - 1 - (l - 1 - (u.val ^^^ v.val).log2) = (u.val ^^^ v.val).log2 := by omega    simp only [Sym2.lift_mk, Fin.val_mk, e]    revert hb    cases u.val.testBit (u.val ^^^ v.val).log2 <;>      cases v.val.testBit (u.val ^^^ v.val).log2 <;> decide  · intro j    have hj : j.val < l := j.isLt    set p := l - 1 - j.val with hp    -- an edge of layer `j` has highest differing bit `p`    have hlevel : ∀ (u v : Fin (2 ^ l)), u.val ≠ v.val →        l - 1 - (u.val ^^^ v.val).log2 = j.val → (u.val ^^^ v.val).log2 = p := by      intro u v h h'      have := (hfacts u v h).1      omega    have hne_of : ∀ (u v : Fin (2 ^ l)),        s(u, v) ∈ (SimpleGraph.completeGraph (Fin (2 ^ l))).edgeSet → u.val ≠ v.val := by      intro u v h huv      apply (show u ≠ v by simpa [SimpleGraph.completeGraph_eq_top] using h)      exact Fin.ext huv    calc ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin (2^l))).edgeSet).filter          (fun e => (⟨l - 1 - Sym2.lift ⟨fun a b : Fin (2 ^ l) => (a.val ^^^ b.val).log2, hsym⟩ e.1,            by omega⟩ : Fin l) = j)).card        ≤ (Finset.range (2 ^ (l - 1 - p)) ×ˢ Finset.range (2 ^ p) ×ˢ Finset.range (2 ^ p)).card := by          refine Finset.card_le_card_of_injOn (fun e => Sym2.lift            ⟨fun a b : Fin (2 ^ l) => op_258_hypercube_bipartite_decomposition_key p a.val b.val,              fun a b => op_258_hypercube_bipartite_decomposition_key_symm p _ _⟩ e.1) ?_ ?_          · intro e he            have he' := congrArg Fin.val (Finset.mem_filter.mp (Finset.mem_coe.mp he)).2            obtain ⟨e, hee⟩ := e            induction e using Sym2.ind with            | h u v =>              have huv := hne_of u v hee              simp only [Sym2.lift_mk] at he'              have hX := hlevel u v huv he'              obtain ⟨-, hhi, hb⟩ := hfacts u v huv              rw [hX] at hhi hb              simp only [Sym2.lift_mk, Finset.coe_product, Finset.coe_range, Set.mem_prod,                Set.mem_Iio, Finset.mem_coe, Finset.mem_product, Finset.mem_range]              rw [op_258_hypercube_bipartite_decomposition_key_eq hb]              have hpow : 2 ^ (l - 1 - p) * 2 ^ (p + 1) = 2 ^ l := by                rw [← pow_add]; congr 1; omega              have hdiv : ∀ w : Fin (2 ^ l), w.val / 2 ^ (p + 1) < 2 ^ (l - 1 - p) := by                intro w                rw [Nat.div_lt_iff_lt_mul (by positivity), hpow]                exact w.isLt              split_ifs              · exact ⟨hdiv v, Nat.mod_lt _ (by positivity), Nat.mod_lt _ (by positivity)⟩              · exact ⟨hdiv u, Nat.mod_lt _ (by positivity), Nat.mod_lt _ (by positivity)⟩          · intro e1 he1 e2 he2 heq            have he1' := congrArg Fin.val (Finset.mem_filter.mp (Finset.mem_coe.mp he1)).2            have he2' := congrArg Fin.val (Finset.mem_filter.mp (Finset.mem_coe.mp he2)).2            obtain ⟨e1, hee1⟩ := e1            obtain ⟨e2, hee2⟩ := e2            induction e1 using Sym2.ind with            | h u1 v1 =>            induction e2 using Sym2.ind with            | h u2 v2 =>              have huv1 := hne_of u1 v1 hee1              have huv2 := hne_of u2 v2 hee2              simp only [Sym2.lift_mk] at he1' he2' heq              have hX1 := hlevel u1 v1 huv1 he1'              have hX2 := hlevel u2 v2 huv2 he2'              obtain ⟨-, hhi1, hb1⟩ := hfacts u1 v1 huv1              obtain ⟨-, hhi2, hb2⟩ := hfacts u2 v2 huv2              rw [hX1] at hhi1 hb1              rw [hX2] at hhi2 hb2              rw [op_258_hypercube_bipartite_decomposition_key_eq hb1,                op_258_hypercube_bipartite_decomposition_key_eq hb2] at heq              apply Subtype.ext              show s(u1, v1) = s(u2, v2)              cases hu1 : u1.val.testBit p <;> cases hv1 : v1.val.testBit p <;>                cases hu2 : u2.val.testBit p <;> cases hv2 : v2.val.testBit p <;>                simp only [hu1, hv1, hu2, hv2, ne_eq, eq_self_iff_true, not_true_eq_false, not_false_eq_true, Bool.false_eq_true, Bool.true_eq_false,                  if_true, if_false] at hb1 hb2 heq ⊢              · obtain ⟨h1, h2⟩ := op_258_hypercube_bipartite_decomposition_key_inj                  hhi1 hhi2 hu1 hv1 hu2 hv2 heq                rw [Fin.ext h1, Fin.ext h2]              · obtain ⟨h1, h2⟩ := op_258_hypercube_bipartite_decomposition_key_inj                  hhi1 hhi2.symm hu1 hv1 hv2 hu2 heq                rw [Fin.ext h1, Fin.ext h2, Sym2.eq_swap]              · obtain ⟨h1, h2⟩ := op_258_hypercube_bipartite_decomposition_key_inj                  hhi1.symm hhi2 hv1 hu1 hu2 hv2 heq                rw [← Fin.ext h1, ← Fin.ext h2, Sym2.eq_swap]              · obtain ⟨h1, h2⟩ := op_258_hypercube_bipartite_decomposition_key_inj                  hhi1.symm hhi2.symm hv1 hu1 hv2 hu2 heq                rw [Fin.ext h1, Fin.ext h2]      _ = 2 ^ (2 * l - 2 - (j : ℕ)) := by          simp only [Finset.card_product, Finset.card_range, ← pow_add]          congr 1          omega
See it in the graphDiscuss this resultChallenge it