op_258_hypercube_bipartite_decomposition
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).
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.
uses
Nat.eq_of_testBit_eq,congrArg,Nat.testBit_xor,Nat.zero_testBitlemma 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
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.
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_xorlemma 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
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.
uses
Nat.testBit_log2,op_258_hypercube_bipartite_decomposition_xor_ne,Nat.testBit_xorlemma 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
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).
uses
Nat.eq_of_testBit_eq,lt_trichotomy,congrArg,Nat.testBit_mod_two_pow,Nat.testBit_div_two_pow,Nat.sub_add_cancellemma 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
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.
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
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.
uses
Prod.mk.injEq,op_258_hypercube_bipartite_decomposition_reconlemma 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. -/
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.
uses
if_neglemma 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]
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.
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⟩
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.
uses
Sym2.liftrefine ⟨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, ?_, ?_⟩
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.
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
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.
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
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.
uses
Sym2.lift,Finset.card_le_card_of_injOn,op_258_hypercube_bipartite_decomposition_key_symmcalc ((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) ?_ ?_
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.
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)⟩
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₂.
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]
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.
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.
- The Lean proof indexes layers by j = l - 1 - p rather than the differing bit position p directly, so layer j corresponds to edges whose highest differing bit is p = l - 1 - j.
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.
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