ProximityPrize.SubmissionUpper.ComplementTruncationPencil.truncationQuotient
DefinitionYukon_fce1ab10c536c75cdaab6eafbetter-codes-history
The quotient whose negative is the desired two-monomial word on roots of the locator.
Original contribution: dtumad, verified Better Codes submission 3cf4cb0e-7415-4347-9264-f1e9f9d8da9b. Source Lean 4.32.2, exact commit 20fb04406d24efa1ee911ff5c8694cbb5b206036. Statements, definitions and proof bodies preserved; imports and exported names adapted for Prove2Me.
Definition code
/-
Copyright (c) 2026 Proximity Prize Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
-/
import Mathlib
/-!
# Complement truncation and a monomial pencil
Let `L * R = X^N - 1`, and split the complementary factor as
`R = X^s * H + r * X^(s - 1) + E`.
If `gamma * r = -1`, multiplying the resulting quotient candidate by `X^s`
gives an expression involving only the locator `L` and the short residual
tail `E`. At every root of `L`, the negative quotient evaluates as the
two-monomial pencil
`x^(A - 1) + gamma * x^(N - s)`.
This is the exact algebraic bridge behind the complement-truncation syndrome
experiment. It deliberately does not assert that the residual high band can
be cancelled: at the current benchmark agreement it still has `8709`
coefficients.
-/
namespace ProximityPrize.SubmissionUpper.ComplementTruncationPencil
open Polynomial
variable {F : Type} [Field F]
/-- The quotient whose negative is the desired two-monomial word on roots of
the locator. -/
noncomputable def truncationQuotient (N A s : ℕ) (gamma : F)
(L H : Polynomial F) : Polynomial F :=
Polynomial.C gamma * L * H - Polynomial.C gamma * Polynomial.X ^ (N - s) -
Polynomial.X ^ (A - 1)
end ComplementTruncationPencil
end SubmissionUpper
end ProximityPrize
Source