cycle_power_dyadic_tight_class_parent
Equality in the dyadic class weight bound forces all rooted-tree parent implications at every smaller dyadic scale, uniformly in the arc length.
Statement
theorem cycle_power_dyadic_tight_class_parent (m j : ℕ) (hj : 1 ≤ j) (hjm : j < m) (b : ℕ → Bool) (htight : cycle_power_dyadic_class_weight m b = (range (2 ^ m)).sum (fun a => (b a).toNat)) : ∀ a < 2 ^ j, (a < 2 ^ (j - 1) → b (a + 2 ^ m - 2 ^ j) = true → b a = true) ∧ (2 ^ (j - 1) ≤ a → b a = true → b (a + 2 ^ m - 2 ^ j) = true)
- Source
- Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635 Section 3. These class-model, pruning and colour-rigidity lemmas do not establish the unresolved graph covering value. No research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- cycle_power_dyadic_b_lift_lowMiddle-quarter pruning preserves every smaller-scale left position.
- cycle_power_dyadic_b_lift_highMiddle-quarter pruning maps every smaller-scale right endpoint to its original larger-scale position.
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- cycle_power_dyadic_tight_class_pruneDeleting a tight dyadic class's middle two quarters and compressing the remaining outer quarters preserves equality between its dyadic…
- cycle_power_dyadic_tight_class_middle_parentEquality in the uniform dyadic class weight bound forces each selected middle-quarter position to have its matched outer-quarter parent…
- cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
- Used by 16
- cycle_power_dyadic_tight_class_inner_imp_oneFor m ≥ 2 and a tight dyadic class b : ℕ → Bool at exponent m (class weight equal to class size) with b 1 = b (2^m - 2) and b (2i) = b…
- cycle_power_dyadic_rank_count_balanceAt every nontrivial dyadic tree rank, exact long-edge coverage is a two-term occupancy balance L_j(v)+R_j(v+D-2^j)=1, uniformly in the…
- cycle_power_dyadic_boundary_pairing_of_terminal_eight_lower_boundFor any dyadic radius at least eight, a periodic tight Boolean class model with exact dyadic-edge coverage and all ordinary coverage has…
- cycle_power_dyadic_fold_modelThe fold of a tight dyadic class model. If x is a tight, exactly dyadically covered, fully covered integer Boolean class model at exponent…
- cycle_power_dyadic_crossed_no_island_models_eqPairing conjecture for coupled no-island models. Let m ≥ 1 and let y, z : ℤ → ℕ → Bool be two integer Boolean class models at exponent m,…
- cycle_power_dyadic_neighbour_weight_boundA tight rooted dyadic class satisfies a uniform weighted bound for the ordinary distances one below the dyadic long distances, with a…
- cycle_power_dyadic_no_island_power_cornerConditional uniform dyadic corner law: in tight two-interval class profiles with exact dyadic edges and one ordinary-neighbour family, a…
- cycle_power_dyadic_sixteen_block_geometryEvery tight dyadic rooted model of radius2^(k+4), with all-rank exactness, full ordinary coverage and monotone outer eighths, satisfies…
- cycle_power_eight_corrected_count_upper_windowIn every zero-phase defective half model of exponent three, the corrected lower count at v is at least its value at v+4.
- cycle_power_eight_corrected_count_lower_windowIn every zero-phase defective half model of exponent three, the corrected lower count at v is at most its value at v+4.
- cycle_power_dyadic_endpoint_overlap_of_no_islandConjectured local uniform geometry: if all tight dyadic classes are unions of an initial and terminal interval, with arbitrary unequal…
- cycle_power_dyadic_outer_quarter_monotone_of_eight_block_extensionAssuming the local eight-block extension predicate at every positive block size, every tight exact fully ordinarily covered dyadic model…
- cycle_power_dyadic_outer_eighth_active_root_separationIn a tight model of radius2^(k+4) with monotone outer eighths and exact rank k ownership, two active seven-eighth roots are separated by…
- cycle_power_fifteen_model_no_islandThe no-island class shape at exponent m = 4 (bandwidth 15), in the exact form the conditional theorem…
- cycle_power_fifteen_model_alternating_endpointAt exponent 4 (bandwidth 15) every tight, exactly dyadically covered, fully covered integer Boolean class model with five active classes…
- cycle_power_eight_block_gap_owner_transfer_atTranslation of the accepted gap-owner transfer to any integer root, with full ordinary coverage supplying the required edge.
The proof, explained
The theorem is proved by strong induction on the cycle dimension m = k + 2. For the maximal scale j = k + 1, the parent implications follow directly from the middle-parent tightness lemma cycle_power_dyadic_tight_class_middle_parent. For any strictly smaller scale j ≤ k, pruning produces a tight configuration at dimension k + 1, allowing the induction hypothesis to be applied and translated back to the original configuration via index preservation lemmas.
Set up strong induction on m and rewrite m = k + 2 using m ≥ 2.
We proceed by strong induction on m, generalizing over the scale j and configuration b. Since 1 ≤ j < m, we must have m ≥ 2, so we can write m = k + 2 for k = m - 2. The recurrence pow_succ gives 2^(k+1) = 2 * 2^k and 2^(k+2) = 2 * 2^(k+1).
uses
Nat.strong_induction_on,pow_succinduction m using Nat.strong_induction_on generalizing j b with | h m ih => have hm : 2 ≤ m := by omega obtain ⟨k, hk⟩ : ∃ k, m = k + 2 := ⟨m - 2, by omega⟩ subst m have hH : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega have hD : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega
When j = k + 1, reduce the claim for any a < 2^(k+1) to two parent implications on the middle intervals.
We branch on whether j = k + 1. In this top-scale case, cycle_power_dyadic_tight_class_middle_parent establishes forward and backward implications between the middle halves. For any a < 2^(k+1), the shifted index a + 2^(k+2) - 2^(k+1) simplifies to a + 2^(k+1) and the scale exponent j - 1 simplifies to k. Splitting the goal conjunction leaves one implication for a < 2^k and one for 2^k ≤ a.
uses
cycle_power_dyadic_tight_class_middle_parentby_cases hjtop : j = k + 1 · subst j have hp := cycle_power_dyadic_tight_class_middle_parent k b htight intro a ha have hindex : a + 2 ^ (k + 2) - 2 ^ (k + 1) = a + 2 ^ (k + 1) := by omega have hpred : k + 1 - 1 = k := by omega rw [hindex, hpred] constructor
When j = k + 1 and a < 2^k, b(a + 2^(k+1)) = true implies b(a) = true.
Assuming a < 2^k and b(a + 2^(k+1)) = true, the shifted index satisfies 2^(k+1) ≤ a + 2^(k+1) < 3 * 2^k. The backward implication of the middle parent lemma applies to this index, yielding b((a + 2^(k+1)) - 2^(k+1)) = true, which simplifies to b(a) = true by Nat.add_sub_cancel_right.
uses
Nat.add_sub_cancel_right· intro haq hx have hh := hp.2 (a + 2 ^ (k + 1)) (by omega) (by omega) hx simpa only [Nat.add_sub_cancel_right] using hh
When j = k + 1 and 2^k ≤ a < 2^(k+1), b(a) = true implies b(a + 2^(k+1)) = true.
Assuming 2^k ≤ a < 2^(k+1) and b(a) = true, the forward implication of the middle parent lemma directly yields b(a + 2^(k+1)) = true.
· intro haq hx exact hp.1 a haq ha hx
When j ≤ k, the induction hypothesis applies to the pruned lift configuration at dimension k + 1.
When j ≠ k + 1, we have j ≤ k since j < k + 2. Lemma cycle_power_dyadic_tight_class_prune shows that pruning the configuration produces a tight configuration at dimension k + 1. Since k + 1 < k + 2 and j < k + 1, we may apply the induction hypothesis ih to this pruned lift configuration at scale j.
uses
cycle_power_dyadic_tight_class_prune· have hjk : j ≤ k := by omega have hs := cycle_power_dyadic_tight_class_prune k b htight have hi := ih (k + 1) (by omega) j hj (by omega) (cycle_power_dyadic_b_lift k b) hs
The parent implications for the pruned lift transfer to b, completing the case j ≤ k.
Evaluating the induction hypothesis at any a < 2^j gives the parent implications for the lifted configuration. Because j ≤ k and a < 2^j, cycle_power_dyadic_b_lift_low rewrites the base index to b(a), and cycle_power_dyadic_b_lift_high rewrites the shifted index to b(a + 2^(k+2) - 2^j), concluding the proof.
uses
cycle_power_dyadic_b_lift_low,cycle_power_dyadic_b_lift_highintro a ha have hh := hi a ha simpa only [cycle_power_dyadic_b_lift_low k j a hjk ha, cycle_power_dyadic_b_lift_high k j a hjk ha] using hh
Nat.strong_induction_on- Strong induction principle on ℕ: to prove P(n) for all n, it suffices to prove P(n) assuming P(m) holds for all m < n.
pow_succ- In any monoid, a^(n + 1) = a^n * a.
cycle_power_dyadic_tight_class_middle_parent- For a tight configuration at dimension k + 2, truth of b(a) for 2^k ≤ a < 2^(k+1) implies truth of b(a + 2^(k+1)), and truth of b(a) for 2^(k+1) ≤ a < 3 * 2^k implies truth of b(a - 2^(k+1)).
Nat.add_sub_cancel_right- For natural numbers, (n + m) - m = n.
cycle_power_dyadic_tight_class_prune- If a configuration b is tight at dimension k + 2, then its pruned lift configuration is tight at dimension k + 1.
cycle_power_dyadic_b_lift_low- For a scale j ≤ k and an index a < 2^j, the pruned lift configuration agrees with b at a.
cycle_power_dyadic_b_lift_high- For a scale j ≤ k and an index a < 2^j, the pruned lift configuration at the shifted index a + 2^(k+1) - 2^j agrees with b at a + 2^(k+2) - 2^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.
open Finsettheorem cycle_power_dyadic_tight_class_parent (m j : ℕ) (hj : 1 ≤ j) (hjm : j < m) (b : ℕ → Bool) (htight : cycle_power_dyadic_class_weight m b = (range (2 ^ m)).sum (fun a => (b a).toNat)) : ∀ a < 2 ^ j, (a < 2 ^ (j - 1) → b (a + 2 ^ m - 2 ^ j) = true → b a = true) ∧ (2 ^ (j - 1) ≤ a → b a = true → b (a + 2 ^ m - 2 ^ j) = true) := by induction m using Nat.strong_induction_on generalizing j b with | h m ih => have hm : 2 ≤ m := by omega obtain ⟨k, hk⟩ : ∃ k, m = k + 2 := ⟨m - 2, by omega⟩ subst m have hH : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega have hD : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega by_cases hjtop : j = k + 1 · subst j have hp := cycle_power_dyadic_tight_class_middle_parent k b htight intro a ha have hindex : a + 2 ^ (k + 2) - 2 ^ (k + 1) = a + 2 ^ (k + 1) := by omega have hpred : k + 1 - 1 = k := by omega rw [hindex, hpred] constructor · intro haq hx have hh := hp.2 (a + 2 ^ (k + 1)) (by omega) (by omega) hx simpa only [Nat.add_sub_cancel_right] using hh · intro haq hx exact hp.1 a haq ha hx · have hjk : j ≤ k := by omega have hs := cycle_power_dyadic_tight_class_prune k b htight have hi := ih (k + 1) (by omega) j hj (by omega) (cycle_power_dyadic_b_lift k b) hs intro a ha have hh := hi a ha simpa only [cycle_power_dyadic_b_lift_low k j a hjk ha, cycle_power_dyadic_b_lift_high k j a hjk ha] using hh