Q Map total fiber disjoint
Binius.BinaryBasefold.qMap_total_fiber_disjoint
Plain-language statement
The images of qMap_total_fiber over distinct quotient points y₁ ≠ y₂ are disjoint
Exact Lean statement
theorem qMap_total_fiber_disjoint
(i : Fin ℓ) (steps : ℕ) (h_i_add_steps : i + steps ≤ ℓ)
{y₁ y₂ : sDomain 𝔽q β h_ℓ_add_R_rate ⟨i.val + steps, by omega⟩}
(hy_ne : y₁ ≠ y₂) :
Disjoint
((qMap_total_fiber 𝔽q β (i := ⟨i, by omega⟩) (steps := steps)
(h_i_add_steps := fin_ℓ_steps_lt_ℓ_add_R i steps h_i_add_steps) y₁ '' Set.univ).toFinset)
((qMap_total_fiber 𝔽q β (i := ⟨i, by omega⟩) (steps := steps)
(h_i_add_steps := fin_ℓ_steps_lt_ℓ_add_R i steps h_i_add_steps) y₂ '' Set.univ).toFinset)Formal artifact
Lean source
theorem qMap_total_fiber_disjoint (i : Fin ℓ) (steps : ℕ) (h_i_add_steps : i + steps ≤ ℓ) {y₁ y₂ : sDomain 𝔽q β h_ℓ_add_R_rate ⟨i.val + steps, by omega⟩} (hy_ne : y₁ ≠ y₂) : Disjoint ((qMap_total_fiber 𝔽q β (i := ⟨i, by omega⟩) (steps := steps) (h_i_add_steps := fin_ℓ_steps_lt_ℓ_add_R i steps h_i_add_steps) y₁ '' Set.univ).toFinset) ((qMap_total_fiber 𝔽q β (i := ⟨i, by omega⟩) (steps := steps) (h_i_add_steps := fin_ℓ_steps_lt_ℓ_add_R i steps h_i_add_steps) y₂ '' Set.univ).toFinset) := by -- Proof by contradiction. Assume the intersection is non-empty. rw [Finset.disjoint_iff_inter_eq_empty] by_contra h_nonempty -- Let `x` be an element in the intersection of the two fiber sets. obtain ⟨x, h_x_mem_inter⟩ := Finset.nonempty_of_ne_empty h_nonempty have hx₁ := Finset.mem_of_mem_inter_left h_x_mem_inter have hx₂ := Finset.mem_of_mem_inter_right h_x_mem_inter -- A helper lemma : applying the forward map to a point in a generated fiber returns -- the original quotient point. have iteratedQuotientMap_of_qMap_total_fiber_eq_self (y : sDomain 𝔽q β h_ℓ_add_R_rate ⟨i.val + steps, by omega⟩) (k : Fin (2 ^ steps)) : iteratedQuotientMap 𝔽q β h_ℓ_add_R_rate (i := ⟨i, by omega⟩) (k := steps) (h_bound := by omega) (qMap_total_fiber 𝔽q β (i := ⟨i, by omega⟩) (steps := steps) (h_i_add_steps := by apply Nat.lt_add_of_pos_right_of_le; omega) (y := y) k) = y := by have h := generates_quotient_point_if_is_fiber_of_y (h_i_add_steps := h_i_add_steps) (x:= ((qMap_total_fiber 𝔽q β (i := ⟨i, by omega⟩) (steps := steps) (h_i_add_steps := by apply Nat.lt_add_of_pos_right_of_le; omega) (y := y) k) : sDomain 𝔽q β h_ℓ_add_R_rate (i := ⟨i, by omega⟩)) ) (y := y) (hx_is_fiber := by use k) exact h.symm have h_exists_k₁ : ∃ k, x = qMap_total_fiber 𝔽q β (i := ⟨i, by omega⟩) (steps := steps) (h_i_add_steps := by apply Nat.lt_add_of_pos_right_of_le; omega) y₁ k := by -- convert (x ∈ Finset of the image of the fiber) to statement -- about membership in the Set. rw [Set.mem_toFinset] at hx₁ rw [Set.mem_image] at hx₁ -- Set.mem_image gives us t an index that maps to x -- ⊢ `∃ (k : Fin (2 ^ steps)), k ∈ Set.univ ∧ qMap_total_fiber ... y₁ k = x`. rcases hx₁ with ⟨k, _, h_eq⟩ use k; exact h_eq.symm have h_exists_k₂ : ∃ k, x = qMap_total_fiber 𝔽q β (i := ⟨i, by omega⟩) (steps := steps) (h_i_add_steps := by apply Nat.lt_add_of_pos_right_of_le; omega) y₂ k := by rw [Set.mem_toFinset] at hx₂ rw [Set.mem_image] at hx₂ -- Set.mem_image gives us t an index that maps to x rcases hx₂ with ⟨k, _, h_eq⟩ use k; exact h_eq.symm have h_y₁_eq_quotient_x : y₁ = iteratedQuotientMap 𝔽q β h_ℓ_add_R_rate i steps h_i_add_steps x := by apply generates_quotient_point_if_is_fiber_of_y (hx_is_fiber := by exact h_exists_k₁) have h_y₂_eq_quotient_x : y₂ = iteratedQuotientMap 𝔽q β h_ℓ_add_R_rate i steps h_i_add_steps x := by apply generates_quotient_point_if_is_fiber_of_y (hx_is_fiber := by exact h_exists_k₂) let kQuotientIndex := pointToIterateQuotientIndex (i := ⟨i, by omega⟩) (steps := steps) (h_i_add_steps := by omega) (x := x) -- Since `x` is in the fiber of `y₁`, applying the forward map to `x` yields `y₁`. have h_map_x_eq_y₁ : iteratedQuotientMap 𝔽q β h_ℓ_add_R_rate (i := ⟨i, by omega⟩) (k := steps) (h_bound := by omega) x = y₁ := by have h := iteratedQuotientMap_of_qMap_total_fiber_eq_self (y := y₁) (k := kQuotientIndex) have hx₁ : x = qMap_total_fiber 𝔽q β (i := ⟨i, by omega⟩) (steps := steps) (h_i_add_steps := by apply Nat.lt_add_of_pos_right_of_le; omega) y₁ kQuotientIndex := by have h_res := is_fiber_iff_generates_quotient_point 𝔽q β i steps (by omega) (x := x) (y := y₁).mp (h_y₁_eq_quotient_x) exact h_res.symm rw [hx₁] exact iteratedQuotientMap_of_qMap_total_fiber_eq_self y₁ kQuotientIndex -- Similarly, since `x` is in the fiber of `y₂`, applying the forward map yields `y₂`. have h_map_x_eq_y₂ : iteratedQuotientMap 𝔽q β h_ℓ_add_R_rate (i := ⟨i, by omega⟩) (k := steps) (h_bound := by omega) x = y₂ := by -- have h := iteratedQuotientMap_of_qMap_total_fiber_eq_self (y := y₂) (k := kQuotientIndex) have hx₂ : x = qMap_total_fiber 𝔽q β (i := ⟨i, by omega⟩) (steps := steps) (h_i_add_steps := by apply Nat.lt_add_of_pos_right_of_le; omega) y₂ kQuotientIndex := by have h_res := is_fiber_iff_generates_quotient_point 𝔽q β i steps (by omega) (x := x) (y := y₂).mp (h_y₂_eq_quotient_x) exact h_res.symm rw [hx₂] exact iteratedQuotientMap_of_qMap_total_fiber_eq_self y₂ kQuotientIndex exact hy_ne (h_map_x_eq_y₁.symm.trans h_map_x_eq_y₂)- Project
- ArkLib
- License
- Apache-2.0
- Commit
- fad5cbf80877
- Source
- ArkLib/ProofSystem/Binius/BinaryBasefold/Prelude.lean:533-618
Reuse this declaration
Bring the exact result into your workflow
The import identifies the source module. Your project still needs the pinned package dependency shown on this page.
What this badge means
This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.
Continue in this project
Related declarations
Affine gaps lifted to interleaved codes
affine_gaps_lifted_to_interleaved_codes
Project documentation
This lemma proves the final algebraic step in the DG25 Theorem 3.1 proof. It shows that if R > e + 1, then e * (R / (R - 1)) < e + 1. The intuition is that the fraction R / (R - 1) is always greater than 1, but as R gets larger, it gets closer to 1. The hypothesis R > e + 1 provides a strong enough bound to ensure the product e * (fraction) do...
Source project: ArkLib
Person-level attribution pending.
Gadget Decompose coeff
ArkLib.Lattices.Ajtai.gadgetDecompose_coeff
Plain-language statement
The k-th coefficient (k < deg φ) of a gadget-decomposition block is exactly the corresponding digit of the corresponding input coefficient.
Source project: ArkLib
Person-level attribution pending.
Gadget Decompose lawful
ArkLib.Lattices.Ajtai.gadgetDecompose_lawful
Plain-language statement
The base-b gadget decomposition is a lawful gadget decomposition.
Source project: ArkLib
Person-level attribution pending.