(1.23), p. 521 — in case 1, d_{k−1} drops by a factor < ¾ and the other d_i are unchanged, so D drops by a factor < ¾; case 2 changes no d_i
ProvedLLLFactor.Reduction.potD_case1_ltalgorithmlattice-basis-reductionlllp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-function
Let be linearly independent, let be the Gram determinants (1.24) and .
- If a step of case 1 of the algorithm (1.15) leads from to , then
- If a step of case 2 leads from to , then for .
This is the potential argument of (1.23): "the number only changes if some is changed, which only occurs in case 1. In case 1, the number is reduced by a factor … whereas the other are unchanged … hence is reduced by a factor ."
Preamble
import Mathlib import Definitions.Def_LLLFactor_Reduction_Algorithm
Formal statement
namespace LLLFactor.Reduction
theorem potD_case1_lt {n : ℕ} (b b' : Fin n → LLLFactor.RedBasis.Vec n) (k k' : ℕ)
(hb : LinearIndependent ℝ b) :
(Case1 (b, k) (b', k') →
gram b' (k - 1) < (3 / 4 : ℝ) * gram b (k - 1) ∧
(∀ i : ℕ, i ≤ n → i ≠ k - 1 → gram b' i = gram b i) ∧
potD b' < (3 / 4 : ℝ) * potD b) ∧
(Case2 (b, k) (b', k') → ∀ i : ℕ, i ≤ n → gram b' i = gram b i) := by sorry
end LLLFactor.Reduction
Source
Lenstra, Lenstra, Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), p. 521, (1.23)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.