All proofs
Project-declaredLean 4.31.0 · mathlib@fabf563a7c95

Rel Dist floor bound iff complement bound

Code.relDist_floor_bound_iff_complement_bound

Project documentation

The equivalence between the two lowerbound of upperBound in Nat and NNReal context. In which, upperBound is viewed as the size of an agreement set S (e.g. between two words, or between a word to a code, ...). Specifically, n - ⌊δ * n⌋ ≤ (upperBound : ℕ) ↔ (1 - δ) * n ≤ (upperBound : ℝ≥0). This lemma is useful for jumping back-and-forth between...

Exact Lean statement

lemma relDist_floor_bound_iff_complement_bound (n upperBound : ℕ) (δ : ℝ≥0) :
    n - Nat.floor (δ * (n)) ≤ upperBound ↔
    (1 - δ) * (n : ℝ≥0) ≤ (upperBound : ℝ≥0)

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
lemma relDist_floor_bound_iff_complement_bound (n upperBound : ) (δ : 0) :    n - Nat.floor* (n))  upperBound     (1 - δ) * (n : 0)  (upperBound : 0) := by  let k := upperBound  set r : 0 := δ * n  set m :  := Nat.floor r  have h_m_le_r_NNReal : (m : NNReal)  r := Nat.floor_le (a := r) (ha := zero_le)  have h_m_le_r_ENNReal : (m : ENNReal)  (r : ENNReal) := by    change ( (m : NNReal) : ENNReal)  (r : ENNReal)    rw [ENNReal.coe_le_coe]    exact h_m_le_r_NNReal  have hr : ↑m  r := Nat.floor_le (mul_nonneg δ.coe_nonneg n.cast_nonneg)  have hr' : r < ↑m + 1 := Nat.lt_floor_add_one r  have h_sub : ↑(n - m) = max (↑n - ↑m) 0 := by    by_cases h : m  n    · simp only [zero_le, sup_of_le_left]    · simp only [zero_le, sup_of_le_left]  conv_rhs => -- convert rhs to ENNReal    rw [ENNReal.coe_le_coe, ENNReal.coe_mul, ENNReal.coe_sub,      ENNReal.coe_one, ENNReal.coe_natCast]    rw [ENNReal.sub_mul (h := fun h1 h2 => by exact ENNReal.natCast_ne_top n)]    simp only [one_mul, ENNReal.coe_natCast]  conv_lhs => -- convert lhs to ENNReal    rw [Nat.cast_le:= ENNReal) (m := n - m) (n := k)]    simp only [ENNReal.natCast_sub]  by_cases h_r_le_n : r  n  · have h_m_le_n : m  n := by exact Nat.floor_le_of_le h_r_le_n    constructor    · intro hNat_le      calc        _  (n : ENNReal) - (m : ENNReal) := by          rw [ENNReal.sub_le_sub_iff_left (b := ↑δ * ↑n) (c := (m : ENNReal))            (h := Nat.cast_le.mpr h_m_le_n) (h' := ENNReal.natCast_ne_top n)]          exact h_m_le_r_ENNReal        _  _ := by exact hNat_le    · intro hNNReal_le      -- APPROACH: Exploting the gap between any two consecutive Nat      let sub_eq := ENNReal.natCast_sub (m := n) (n := m)      rw [sub_eq]      rw [Nat.cast_le]      rw [Nat.lt_add_one_iff]      -- Convert to ℝ      rw [ Nat.cast_lt:= )]      rw [Nat.cast_sub h_m_le_n, Nat.cast_add, Nat.cast_one]      -- The goal is now `(n : ℝ) - (m : ℝ) < (k : ℝ) + 1`      have h_hyp_ : (n : ) - (r : )  (k : ) := by        exact_mod_cast hNNReal_le      have h_floor_lt_ : (r : ) < (m : ) + 1 := by        exact_mod_cast hr'      -- `linarith` proves `n - m < k + 1` from: `n - r ≤ k` AND `r < m + 1`      -- by showing `n - m < n - r + 1 ≤ k + 1`      linarith  · have h_n_lt_r : n < r := by exact lt_of_not_ge h_r_le_n    have h_m_ge_n : m  n :=      NNReal.floor_ge_Nat_of_gt (r := r) (n := n) (h := lt_of_not_ge h_r_le_n)    have h_n_sub_m_eq_0 : n - m = 0 := Nat.sub_eq_zero_of_le h_m_ge_n    have h_n_sub_r_eq_0 : (n : ENNReal) - r = 0 := by      change ((n : NNReal) : ENNReal) - r = 0      rw [ENNReal.coe_sub] -- ↑((n : ℝ≥0) - r) = 0      have h_n_sub_r_eq_0_NNReal : (n : NNReal) - r = 0 := by        apply NNReal.sub_eq_zero_of_le        exact le_of_lt h_n_lt_r      rw [h_n_sub_r_eq_0_NNReal]      exact rfl    conv_lhs => -- convert ↑n - ↑m into 0      rw [ENNReal.natCast_sub]      rw [h_n_sub_m_eq_0, Nat.cast_zero]    conv_rhs => -- convert ↑n - ↑r into 0      change (n : ENNReal) - r  k      rw [h_n_sub_r_eq_0]
Project
ArkLib
License
Apache-2.0
Commit
fad5cbf80877
Source
ArkLib/Data/CodingTheory/Basic/RelativeDistance.lean:413-482

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

Project-declaredLean 4.31.0

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...

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

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.

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

Gadget Decompose lawful

ArkLib.Lattices.Ajtai.gadgetDecompose_lawful

Plain-language statement

The base-b gadget decomposition is a lawful gadget decomposition.

cryptographyproof systemscoding theory

Source project: ArkLib

Person-level attribution pending.

View proof record