Proof of Lemma 2.15, p. 17 — if t·I⁻¹ is coprime to J, u ∈ M and t·u ∈ IJM, then u ∈ JM
ProvedLPRRingLWE.Clear.mem_of_mul_memdedekind-domainfractional-idealp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ring-lwe
Let be a number field with ring of integers , let be ideals with , let be such that is coprime to , and let be a fractional ideal of . Then for every ,
This is the injectivity half of Lemma 2.15: the kernel of on is contained in (the reverse inclusion is immediate from ).
Formalization Note The paper's convention that and are nonzero is not needed for this implication and is not assumed; dropping it makes the statement stronger. is kept because appears in the coprimality hypothesis.
Preamble
import Mathlib import Definitions.Def_LPRRingLWE_Clear_Setting
Formal statement
namespace LPRRingLWE.Clear
open NumberField
open scoped nonZeroDivisors
/-- Proof of Lemma 2.15, p. 17 (kernel step): if `t · I⁻¹` is coprime to `J`, `u ∈ M` and
`t · u ∈ IJM`, then `u ∈ JM`. -/
theorem mem_of_mul_mem {K : Type*} [Field K] [NumberField K]
(I J : Ideal (𝓞 K)) (hI : I ≠ ⊥) (t : 𝓞 K) (ht : t ∈ I) (hcop : ClearedCoprime t I J)
(M : FractionalIdeal (𝓞 K)⁰ K) :
∀ u ∈ M, algebraMap (𝓞 K) K t * u ∈ (I : FractionalIdeal (𝓞 K)⁰ K) * J * M →
u ∈ (J : FractionalIdeal (𝓞 K)⁰ K) * M := by sorry
end LPRRingLWE.Clear
Source
Lyubashevsky, Peikert & Regev, On ideal lattices and learning with errors over rings, J. ACM 60(6) (2013), p. 17, proof of Lemma 2.15, second paragraph ("Second, if θ_t(u) = 0 … u ∈ JM")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.