All proofs
Project-declaredLean 4.31.0 · mathlib@fabf563a7c95

Johnson condition weak implies strong

JohnsonBound.johnson_condition_weak_implies_strong

Plain-language statement

The weak Johnson condition implies the strong one on the ball intersection.

Exact Lean statement

lemma johnson_condition_weak_implies_strong [Field F]
    {B : Finset (Fin n → F)} {v : Fin n → F} {e : ℕ}
    (h_J_cond_weak : JohnsonConditionWeak B e)
    (h_B2_not_one : 1 < (B ∩ ({ x | Δ₀(x, v) ≤ e } : Finset _)).card)
    (h_F_nontriv : 2 ≤ card F) :
    JohnsonConditionStrong (B ∩ ({ x | Δ₀(x, v) ≤ e } : Finset _)) v

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
lemma johnson_condition_weak_implies_strong [Field F]    {B : Finset (Fin n  F)} {v : Fin n  F} {e : }    (h_J_cond_weak : JohnsonConditionWeak B e)    (h_B2_not_one : 1 < (B ∩ ({ x | Δ₀(x, v)  e } : Finset _)).card)    (h_F_nontriv : 2  card F) :    JohnsonConditionStrong (B ∩ ({ x | Δ₀(x, v)  e } : Finset _)) v := by  have h_n_pos : 0 < n := by    by_contra hn    push Not at hn    have : n = 0 := by omega    subst this    have B_singleton : B.card  1 :=      card_le_one.2 (fun _ _ _ _ => funext (Fin.elim0 ·))    have : (B ∩ ({ x | Δ₀(x, v)  e } : Finset _)).card  1 :=      le_trans (card_le_card inter_subset_left) B_singleton    omega  unfold JohnsonConditionStrong  intro e_1 d q frac  by_cases h_dsqrt_pos : (0 : )  1 - frac * d / ↑n  · have h_B2_nonempty : (0 : ) < ((B ∩ ({ x | Δ₀(x, v)  e } : Finset _)).card : ) :=      by norm_cast; omega    have h_frac_pos : frac > 0 := by      unfold frac      have : 1 < card F := by        simpa [Fintype.one_lt_card_iff] using ((0 : F), (1 : F), by simp :  a b : F, a  b)      field_simp      unfold q      simp only [Nat.cast_pos, Fintype.zero_lt_card, div_pos_iff_of_pos_left, sub_pos,        Nat.one_lt_cast]      exact h_F_nontriv    have j_fun_bound : (↑e / ↑n : ) < (1 / ↑frac * (1 - √(1 - ↑frac * ↑d / ↑n))) := by      unfold JohnsonConditionWeak J at h_J_cond_weak      simp_all only [Rat.cast_natCast, Rat.cast_div, Rat.cast_sub, Rat.cast_one, one_div, inv_div,        ne_eq, sub_nonneg, Nat.cast_pos, Finset.card_pos, gt_iff_lt]      let d_weak := sInf { d |  u  B,  v  B, ¬u = v  Δ₀(u, v) = d }      have d_subset : ↑d_weak  (d : ) := by          unfold d          unfold JohnsonBound.d          unfold d_weak          have min_dist := min_dist_le_d h_B2_not_one          have subset_inf_ineq :              sInf { d |  u  B,  v  B, u  v  Δ₀(u, v) = d }               sInf { d |               u  (B ∩ ({ x | Δ₀(x, v)  e } : Finset _)),               v_1  (B ∩ ({ x | Δ₀(x, v)  e } : Finset _)),              u  v_1  Δ₀(u, v_1) = d } := by              have subset : { d |                           u  (B ∩ ({ x | Δ₀(x, v)  e } : Finset _)),                           v_1  (B ∩ ({ x | Δ₀(x, v)  e } : Finset _)),                          u  v_1  Δ₀(u, v_1) = d }                           { d |  u  B,  v  B, u  v  Δ₀(u, v) = d } := by                intro d u, hu_in, v_1, hv_in, hne, heq                exact                  u, by                    simp only [mem_inter, mem_filter, mem_univ, true_and] at hu_in; exact hu_in.1,                  v_1, by                    simp only [mem_inter, mem_filter, mem_univ, true_and] at hv_in; exact hv_in.1,                  hne, heq              gcongr              obtain u, hu, v_1, hv_1, hne := one_lt_card.mp h_B2_not_one              use Δ₀(u, v_1)              exact u, hu, v_1, hv_1, hne, rfl          calc ↑d_weak              = ↑(sInf { d |  u  B,  v  B, ¬u = v  Δ₀(u, v) = d }) := by rfl            _  ↑(sInf { d |               u  (B ∩ ({ x | Δ₀(x, v)  e } : Finset _)),               v_1  (B ∩ ({ x | Δ₀(x, v)  e } : Finset _)),              u  v_1  Δ₀(u, v_1) = d }) := by exact_mod_cast subset_inf_ineq            _  JohnsonBound.d (B ∩ ({ x | Δ₀(x, v)  e } : Finset _)) :=              by exact_mod_cast min_dist      have bound : (↑frac)⁻¹ * (1 - √(1 - ↑frac * ↑d_weak / ↑n))           (↑frac)⁻¹ * (1 - √(1 - ↑frac * ↑d / ↑n)) := by        have ineq1 : (↑d_weak / ↑n)  (d / ↑n) := by          rw [ mul_le_mul_iff_of_pos_left (Nat.cast_pos.mpr h_n_pos)]          field_simp          exact d_subset        have ineq2 : frac * (d_weak / n)  frac * (d / n) :=          mod_cast (mul_le_mul_iff_of_pos_left h_frac_pos).mpr ineq1        have ineq3' : (1 : ) - frac * d / n  (1 : ) - frac * d_weak / n := by          norm_cast; grind        have ineq4 : √(1 - ↑frac * ↑d / ↑n)  √(1 - ↑frac * ↑d_weak / ↑n) :=          sqrt_le_sqrt ineq3'        have ineq5 :            (1 - √(1 - ↑frac * ↑d_weak / ↑n))  (1 - √(1 - ↑frac * ↑d / ↑n)) := by linarith        simp_all      have h_J_cond_weak' : ↑e / ↑n < 1 / (↑frac) * (1 - √(1 - frac * (d_weak / ↑n))) := by        unfold frac        unfold q        unfold d_weak        push_cast        rw [one_div_div]        exact h_J_cond_weak      field_simp      field_simp at h_J_cond_weak'      field_simp at bound      nlinarith [mul_le_mul_of_nonneg_left bound (Nat.cast_nonneg n)]    have err_n : (↑e_1 / ↑n : )  (↑e / ↑n : ) := by      apply div_le_div_of_nonneg_right _ (Nat.cast_nonneg n)      exact_mod_cast e_ball_le_radius v e        (by simpa using show 0 < (B ∩ ({ x | Δ₀(x, v)  e } : Finset _)).card by omega)    have j_fun_bound_e1 : (↑e_1 / ↑n : ) < (1 / ↑frac * (1 - √(1 - ↑frac * ↑d / ↑n))) :=      lt_of_le_of_lt err_n j_fun_bound    have rearrange_jboundw_e1 : √(1 - ↑frac * ↑d / ↑n) < 1 - frac * e_1 / ↑n := by      have : frac * e_1 / ↑n < 1 - √(1 - frac * d / ↑n) := by        calc ↑frac * ↑e_1 / ↑n            = ↑frac * (↑e_1 / ↑n) := by ring          _ < ↑frac * (1 / ↑frac * (1 - √(1 - ↑frac * ↑d / ↑n))) := by            simp_all only [Rat.cast_div, Rat.cast_natCast, Rat.cast_sub, Rat.cast_one, sub_nonneg,              Nat.cast_pos, Finset.card_pos, gt_iff_lt, zero_lt_card, div_pos_iff_of_pos_left,              sub_pos, Nat.one_lt_cast, one_div, inv_div, mul_lt_mul_iff_right₀, frac, q, d, e_1]          _ = 1 - √(1 - ↑frac * ↑d / ↑n) := by            grind only [= division_by_conjugate, = sqrt_one]      grind only    have h_esqrtpos : (0 : )  1 - frac * e_1 / ↑n := by      have : (0 : )  √(1 - ↑frac * ↑d / ↑n) := by        simp_all only [Rat.cast_div, Rat.cast_natCast, Rat.cast_sub, Rat.cast_one, sub_nonneg,          Nat.cast_pos, Finset.card_pos, gt_iff_lt, zero_lt_card, div_pos_iff_of_pos_left,          sub_pos, Nat.one_lt_cast, one_div, inv_div, sqrt_nonneg, frac, q, d, e_1]      grind only    suffices recast_main_goal : (1 - frac * d / ↑n : ) < (1 - frac * e_1 / ↑n) ^ 2 by      exact_mod_cast recast_main_goal    suffices roots : √(1 - frac * d / ↑n) < 1 - frac * e_1 / ↑n by      rw [ sqrt_lt h_dsqrt_pos h_esqrtpos]      exact_mod_cast roots    exact rearrange_jboundw_e1  · have strict_neg : 1 - ↑frac * ↑d / ↑n < (0 : ) := by      have : ¬(0 : )  1 - frac * d / ↑n := by exact_mod_cast h_dsqrt_pos      rw [Rat.not_le] at this      exact this    calc 1 - ↑frac * ↑d / ↑n < (0 : ) := strict_neg      _  (1 - ↑frac * ↑e_1 / ↑n) ^ 2 := by exact_mod_cast sq_nonneg (1 - frac * ↑e_1 / ↑n)
Project
ArkLib
License
Apache-2.0
Commit
fad5cbf80877
Source
ArkLib/Data/CodingTheory/JohnsonBound/Basic.lean:101-231

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