Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

YukonModule.CompPoly.Univariate.Raw.Ops.part0

Definition
Yukon_2b2cffaf7915639b497d3e9d

by yukon · Sep 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

better-codes

Source module CompPoly.Univariate.Raw.Ops.

Definition code
/-
Copyright (c) 2025 CompPoly. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Quang Dao, Gregor Mitscha-Baude, Derek Sorensen, Desmond Coles,
  Natalie Klaus, Dimitris Mitsios
-/
module

import all Definitions.Def_Yukon_8b420bde4918adb5e45d1b8c

public import Definitions.Def_Yukon_8b420bde4918adb5e45d1b8c



public import Mathlib.Data.Nat.Log
public import Mathlib.Algebra.Order.Star.Basic
public import Mathlib.Algebra.Order.Ring.Nat
public import Mathlib.Tactic.Cases
public import Mathlib.Order.Lattice.Nat
public import Mathlib.Data.List.GetD
public import Mathlib.Algebra.GroupWithZero.Nat
public import Init
public import Mathlib.RingTheory.Polynomial.Basic
public import Mathlib.Algebra.Tropical.Basic
meta import Definitions.Def_Yukon_8b420bde4918adb5e45d1b8c
set_option backward.isDefEq.respectTransparency.types false
/-!
# Raw Univariate Polynomial Operations

Operations and evaluation lemmas for raw computable univariate polynomials.
-/

public section

namespace CompPoly

namespace CPolynomial.Raw

variable {R : Type*}
variable {Q : Type*}

section Operations

section Semiring

variable {S : Type*}

/-- Evaluates a `CPolynomial.Raw` at `x : S` using a ring homomorphism `f : R →+* S`.

  Computes `f(a₀) + f(a₁) * x + f(a₂) * x² + ...` where `aᵢ` are the coefficients.  -/
def eval₂ [Semiring R] [Semiring S] (f : R →+* S) (x : S) (p : CPolynomial.Raw R) : S :=
  p.zipIdx.foldl (fun acc ⟨a, i⟩ => acc + f a * x ^ i) 0

/-- Evaluates a `CPolynomial.Raw` at `x : S` using Horner's method.

  Computes `f(aₙ) + x * (f(aₙ₋₁) + x * (... + x * f(a₀)))` via a right fold. -/
@[inline, specialize]
def eval₂Horner [Semiring R] [Semiring S] (f : R →+* S) (x : S) (p : CPolynomial.Raw R) : S :=
  p.foldr (fun a acc => acc * x + f a) 0

/-- Evaluates a `CPolynomial.Raw` at a given value -/
@[inline, specialize]
def eval [Semiring R] (x : R) (p : CPolynomial.Raw R) : R :=
  p.eval₂ (RingHom.id R) x

/-- Raw addition: pointwise sum of coefficient arrays (padded to equal length).

  The result may have trailing zeros and should be trimmed for canonical form. -/
@[inline, specialize]
def addRaw [Zero R] [Add R] (p q : CPolynomial.Raw R) : CPolynomial.Raw R :=
  let ⟨p', q'⟩ := Array.matchSize p q 0
  .mk (Array.zipWith (· + ·) p' q' )

/-- Addition of two `CPolynomial.Raw`s, with result trimmed. -/
@[inline, specialize]
def add [Zero R] [Add R] [BEq R] (p q : CPolynomial.Raw R) : CPolynomial.Raw R :=
  addRaw p q |> trim

section SMulDefs

/-- Scalar multiplication: multiplies each coefficient by `r`. -/
@[inline, specialize]
def smul [Mul R] (r : R) (p : CPolynomial.Raw R) : CPolynomial.Raw R :=
  .mk (Array.map (fun a => r * a) p)

/-- Right scalar multiplication: multiplies each coefficient by `r` on the right.

  Corresponds to `p.toPoly * Polynomial.C r`, in contrast to `smul` which corresponds
  to `Polynomial.C r * p.toPoly`. The distinction matters in non-commutative semirings. -/
@[inline, specialize]
def smulRight [Mul R] (r : R) (p : CPolynomial.Raw R) : CPolynomial.Raw R :=
  .mk (Array.map (fun a => a * r) p)

/-- Raw scalar multiplication by a natural number (may have trailing zeros). -/
@[inline, specialize]
def nsmulRaw [Semiring R] (n : ℕ) (p : CPolynomial.Raw R) : CPolynomial.Raw R :=
  .mk (Array.map (fun a => n * a) p)

/-- Scalar multiplication of `CPolynomial.Raw` by a natural number, with result trimmed. -/
@[inline, specialize]
def nsmul [Semiring R] [BEq R] (n : ℕ) (p : CPolynomial.Raw R) : CPolynomial.Raw R :=
  nsmulRaw n p |> trim

end SMulDefs

section MulPowXDefs

/-- Multiplication by `X^i`: shifts coefficients right by `i` positions (prepends `i` zeros). -/
@[inline, specialize]
def mulPowX [Zero R] (i : Nat) (p : CPolynomial.Raw R) : CPolynomial.Raw R :=
  .mk (Array.replicate i 0 ++ p)

/-- Multiplication of a `CPolynomial.Raw` by `X`, reduces to `mulPowX 1`. -/
@[inline, specialize]
def mulX [Zero R] (p : CPolynomial.Raw R) : CPolynomial.Raw R := p.mulPowX 1

end MulPowXDefs

/-- Multiplication accumulator using the naive `O(n²)` algorithm: `Σᵢ (aᵢ * q) * X^i`.

  The partial sums are combined with the untrimmed `addRaw`, so the result may carry
  trailing zeros and should be trimmed for canonical form. Deferring the trim to the
  end (see `mul`) avoids an `O(size)` scan after every partial sum. -/
@[inline, specialize]
def mulRaw [Semiring R] (p q : CPolynomial.Raw R) : CPolynomial.Raw R :=
  p.zipIdx.foldl (fun acc ⟨a, i⟩ => acc.addRaw <| (smul a q).mulPowX i) (mk #[])

/-- Multiplication using the naive `O(n²)` algorithm: `Σᵢ (aᵢ * q) * X^i`.

  Trims only once, at the end of the convolution fold, rather than after every
  partial sum (`mulRaw` does the untrimmed accumulation). -/
@[inline, specialize]
def mul [Semiring R] [BEq R] (p q : CPolynomial.Raw R) : CPolynomial.Raw R :=
  (mulRaw p q).trim

/-- Exponentiation of a `CPolynomial.Raw` by a natural number `n` via repeated multiplication.
This is the specification; `powBySq` is the efficient O(log n) implementation. -/
@[inline, specialize]
def pow [Semiring R] [BEq R] (p : CPolynomial.Raw R) (n : Nat) : CPolynomial.Raw R :=
  (mul p)^[n] (C 1)

/-- Repeated-squaring core that accumulates with the untrimmed `mulRaw`, deferring
the canonicalization trim to the outer `powBySq` wrapper. The output may carry
trailing zeros and is not in canonical form.

For $ n > 0 $, computes $ p ^ n $ by recursing on $ n / 2 $:
* If $ n $ is even: $ (p ^ {n/2})^2 $
* If $ n $ is odd:  $ p \cdot (p ^ {n/2})^2 $
-/
@[inline, specialize]
def powBySqUntrimmed [Semiring R] (p : CPolynomial.Raw R) : Nat → CPolynomial.Raw R
  | 0 => C 1
  | n + 1 =>
    let half := powBySqUntrimmed p ((n + 1) / 2)
    let sq := mulRaw half half
    if (n + 1) % 2 = 0 then sq else mulRaw p sq
  decreasing_by omega

/-- Exponentiation via repeated squaring: $ O(\log n) $ multiplications
instead of $ O(n) $. Delegates to `powBySqUntrimmed` and trims only once
at the end, rather than after every squaring step.
-/
@[inline, specialize]
def powBySq [Semiring R] [BEq R] (p : CPolynomial.Raw R) (n : Nat) : CPolynomial.Raw R :=
  (powBySqUntrimmed p n).trim

instance  _root_.CompPoly.CPolynomial.Raw.instZero : Zero (CPolynomial.Raw R) := ⟨#[]⟩
instance  _root_.CompPoly.CPolynomial.Raw.instOne [One R] : One (CPolynomial.Raw R) := ⟨C 1⟩
instance  _root_.CompPoly.CPolynomial.Raw.instAddOfZeroOfBEq [Zero R] [Add R] [BEq R] : Add (CPolynomial.Raw R) := ⟨add⟩
instance  _root_.CompPoly.CPolynomial.Raw.instSMulOfMul [Mul R] : SMul R (CPolynomial.Raw R) := ⟨smul⟩
instance  _root_.CompPoly.CPolynomial.Raw.instSMulNatOfSemiringOfBEq [Semiring R] [BEq R] : SMul ℕ (CPolynomial.Raw R) := ⟨nsmul⟩
instance  _root_.CompPoly.CPolynomial.Raw.instMulOfSemiringOfBEq [Semiring R] [BEq R] : Mul (CPolynomial.Raw R) := ⟨mul⟩
instance  _root_.CompPoly.CPolynomial.Raw.instPowNatOfSemiringOfBEq [Semiring R] [BEq R] : Pow (CPolynomial.Raw R) Nat := ⟨pow⟩
instance  _root_.CompPoly.CPolynomial.Raw.instNatCast [NatCast R] : NatCast (CPolynomial.Raw R) := ⟨fun n => C (n : R)⟩

/-- Keep only the stored coefficients with index `< k`. -/
@[inline, specialize]
def truncate [Zero R] (k : Nat) (p : CPolynomial.Raw R) : CPolynomial.Raw R :=
  p.extract 0 k

/-- Return exactly the first `k` coefficients, padding missing coefficients with zero. -/
@[inline, specialize]
def takeLow [Zero R] (k : Nat) (p : CPolynomial.Raw R) : CPolynomial.Raw R :=
  Array.ofFn fun i : Fin k ↦ p.coeff i

/-- Reverse the first `n` coefficients, padding missing coefficients with zero. -/
@[inline, specialize]
def reverse [Zero R] (n : Nat) (p : CPolynomial.Raw R) : CPolynomial.Raw R :=
  Array.ofFn fun i : Fin n ↦ p.coeff (n - 1 - i.val)

/-- Low product computed by the coefficient convolution formula. -/
@[inline, specialize]
def mulLowConvolution [Semiring R] (k : Nat) (p q : CPolynomial.Raw R) : CPolynomial.Raw R :=
  Array.ofFn fun i : Fin k ↦
    (Finset.range (i.val + 1)).sum fun j ↦ p.coeff j * q.coeff (i.val - j)

/-- Backend for computing the low `k` coefficients of a raw product. -/
structure MulLowContext (R : Type*) [Semiring R] [BEq R] [LawfulBEq R] where
  /-- Return the low `k` coefficients of `p * q`. -/
  mulLow : Nat → CPolynomial.Raw R → CPolynomial.Raw R → CPolynomial.Raw R
  /-- The backend does not return coefficients at degree `>= k`. -/
  size_le : ∀ k p q, (mulLow k p q).size ≤ k
  /-- Low coefficients agree with ordinary raw multiplication. -/
  coeff_of_lt : ∀ k p q i, i < k → (mulLow k p q).coeff i = (p * q).coeff i

/-- Upper bound on degree: `size - 1` if non-empty, `⊥` if empty. -/
def degreeBound (p : CPolynomial.Raw R) : WithBot Nat :=
  match p.size with
  | 0 => ⊥
  | .succ n => n

/-- Convert `degreeBound` to a natural number by sending `⊥` to `0`. -/
def natDegreeBound (p : CPolynomial.Raw R) : Nat :=
  (degreeBound p).getD 0

/-- Check if a `CPolynomial.Raw` is monic, i.e. its leading coefficient is 1. -/
def monic [Zero R] [One R] [BEq R] (p : CPolynomial.Raw R) : Bool := p.leadingCoeff == 1

/-- Pseudo-division by `X`: removes the constant term and shifts remaining coefficients left. -/
def divX (p : CPolynomial.Raw R) : CPolynomial.Raw R := p.extract 1 p.size

end Semiring

section Ring

/-- Negation of a `CPolynomial.Raw`. -/
@[inline, specialize]
def neg [Neg R] (p : CPolynomial.Raw R) : CPolynomial.Raw R := p.map (fun a => -a)

/-- Subtraction of two `CPolynomial.Raw`s. -/
@[inline, specialize]
def sub [Zero R] [Add R] [Neg R] [BEq R]
    (p q : CPolynomial.Raw R) : CPolynomial.Raw R :=
  p.add q.neg

instance  _root_.CompPoly.CPolynomial.Raw.instNeg [Neg R] : Neg (CPolynomial.Raw R) := ⟨neg⟩
instance  _root_.CompPoly.CPolynomial.Raw.instSubOfZeroOfAddOfNegOfBEq [Zero R] [Add R] [Neg R] [BEq R] : Sub (CPolynomial.Raw R) := ⟨sub⟩
instance  _root_.CompPoly.CPolynomial.Raw.instIntCast [IntCast R] : IntCast (CPolynomial.Raw R) := ⟨fun n => C (n : R)⟩

end Ring

end Operations

end CPolynomial.Raw

end CompPoly


Source
https://github.com/zksecurity/CompPoly/blob/641694629e4557520a1539b272ec338c9f3044c7/CompPoly/Univariate/Raw/Ops.lean yukon-proof-operation:fcfbc108bddf79ddbf8ed0977c5354990232ede081fdd04dc3538612b898f478 [yukon-proof-receipt:eyJ2IjoxLCJtYXJrZXIiOiJ5dWtvbi1wcm9vZi1vcGVyYXRpb246ZmNmYmMxMDhiZGRmNzlkZGJmOGVkMDk3N2M1MzU0OTkwMjMyZWRlMDgxZmRkMDRkYzM1Mzg2MTJiODk4ZjQ3OCIsImhhc2giOiI4ZGYwYmY0MWRhZDY1M2UyM2YzZDY1OTU1ZTg3M2Q3NDQ4MTBkNmU5MGY0MWQ1MDk0ODYzYjVlMWRhMWYxOWI5Iiwia2luZCI6ImRlZmluaXRpb24iLCJ0YXJnZXQiOiJZdWtvbl8yYjJjZmZhZjc5MTU2MzliNDk3ZDNlOWQiLCJlbnZpcm9ubWVudCI6eyJtYXRobGliUmV2IjoiMGRmNDQ0YTM2MGVhYTYwYWI4YzExZGNhNTFhODZhZjY5Mjk1NTQ3NCIsInRvb2xjaGFpbiI6ImxlYW5wcm92ZXIvbGVhbjQ6djQuMzMuMSJ9LCJ0YWciOiJiZXR0ZXItY29kZXMifQ]

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me