Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

YukonModule.ArkLib.Data.CodingTheory.PolishchukSpielman.Degrees.part0

Definition
Yukon_242be9c48cf0d0c464d1328d

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

better-codes

Source module ArkLib.Data.CodingTheory.PolishchukSpielman.Degrees.

Definition code
/-
Copyright (c) 2024-2026 ArkLib Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Alexander Hicks, Aleph
-/

import Definitions.Def_Yukon_01ccec4dda453f6e2e78a73a

import Mathlib.Analysis.Normed.Field.Lemmas
import Mathlib.LinearAlgebra.Lagrange
import Mathlib.RingTheory.Polynomial.UniqueFactorization


import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Algebra.Polynomial.BigOperators
import Mathlib.RingTheory.Polynomial.Resultant.Basic
import Mathlib.Algebra.Polynomial.Roots
import Aesop
import Mathlib.Algebra.Polynomial.Bivariate
import Mathlib.Data.Nat.Log
import Mathlib.Algebra.Order.Star.Basic
import Mathlib.Algebra.Order.Ring.Nat
import Mathlib.Tactic.Cases
import Mathlib.Order.Lattice.Nat
import Mathlib.Data.List.GetD
import Mathlib.Algebra.GroupWithZero.Nat
import Init
import Mathlib.RingTheory.Polynomial.Basic
import Mathlib.Algebra.Tropical.Basic
import Mathlib.Algebra.Ring.TransferInstance
import Mathlib.Algebra.Polynomial.Inductions
set_option backward.isDefEq.respectTransparency.types false
/-!
# Degree bounds for Polishchuk-Spielman

This file contains auxiliary lemmas regarding degree bounds, evaluation, and
variable swapping for bivariate polynomials, used in the Polishchuk-Spielman
lemma [BCIKS20].

## Main results

- `ps_bx_lt_nx`, `ps_by_lt_ny`: Bounds on the degrees parameters.
- `ps_card_eval_x_eq_zero_le_degree_x`, `ps_card_eval_y_eq_zero_le_nat_degree_y`:
  Bounds on the number of roots of a bivariate polynomial on lines.
- `ps_eval_y_eq_eval_x_swap`: Relates evaluation in Y to evaluation in X of the swapped polynomial.
- `ps_exists_x_preserve_nat_degree_y`, `ps_exists_y_preserve_degree_x`:
  Existence of evaluation points preserving the degree.

## References

* [Ben-Sasson, E., Carmon, D., Ishai, Y., Kopparty, S., and Saraf, S., *Proximity Gaps
    for Reed-Solomon Codes*][BCIKS20]

-/

open Polynomial.Bivariate Polynomial Finset
open scoped BigOperators

lemma ps_bx_lt_nx {b_x b_y : ℕ} {n_x n_y : ℕ+}
    (h_le_1 : 1 > (b_x : ℚ) / (n_x : ℚ) + (b_y : ℚ) / (n_y : ℚ)) : b_x < (n_x : ℕ) := by
  contrapose! h_le_1;
  exact le_add_of_le_of_nonneg
    (by rw [le_div_iff₀ (Nat.cast_pos.mpr n_x.pos )]; norm_cast; linarith) (by positivity)

lemma ps_by_lt_ny {b_x b_y : ℕ} {n_x n_y : ℕ+}
    (h_le_1 : 1 > (b_x : ℚ) / (n_x : ℚ) + (b_y : ℚ) / (n_y : ℚ)) : b_y < (n_y : ℕ) := by
  exact_mod_cast
    (by nlinarith [show (0 : ℚ) ≤ b_x / (n_x : ℚ) by positivity,
    show (0 : ℚ) ≤ b_y / (n_y : ℚ) by positivity,
      mul_div_cancel₀ (b_x : ℚ) (show (n_x : ℚ) ≠ 0 by positivity),
      mul_div_cancel₀ (b_y : ℚ) (show (n_y : ℚ) ≠ 0 by positivity),
      show (n_x : ℚ) > 0 by positivity, show (n_y : ℚ) > 0 by positivity] : (b_y : ℚ) < n_y)

lemma ps_card_eval_x_eq_zero_le_degree_x {F : Type} [Field F] [DecidableEq F]
    (A : F[X][Y]) (hA : A ≠ 0) (P : Finset F) :
    (P.filter (fun x ↦ evalX x A = 0)).card ≤ degreeX A := by
  by_contra! h_contra;
  obtain ⟨j₀, hj₀⟩ : ∃ j₀, (A.coeff j₀).natDegree = degreeX A ∧ A.coeff j₀ ≠ 0 := by
    have h_exists_j₀ : ∃ j₀ ∈ A.support, ∀ n ∈ A.support,
        (A.coeff n).natDegree ≤ (A.coeff j₀).natDegree := by
      exact exists_max_image _ _ (nonempty_of_ne_empty (by aesop))
    obtain ⟨j₀, hj₀₁, hj₀₂⟩ := h_exists_j₀
    exact ⟨j₀, le_antisymm (le_sup (f := fun n ↦ (A.coeff n).natDegree) hj₀₁)
      (Finset.sup_le fun n hn ↦ hj₀₂ n hn), by aesop⟩
  -- Let $P_A$ be the set of $x \in P$ such that $A(x, Y) = 0$.
  set PA := P.filter (fun x ↦ evalX x A = 0) with hPA_def;
  have h_coeff_zero : ∀ x ∈ PA, (A.coeff j₀).eval x = 0 := by
    intro x hx
    replace hx := congr_arg (fun f ↦ f.coeff j₀) (mem_filter.mp hx |>.2)
    aesop
  exact absurd (Finset.card_le_card
    (show PA ⊆ ((A.coeff j₀).roots.toFinset) from fun x hx ↦ by aesop))
    (by exact not_le.mpr <| lt_of_le_of_lt (Multiset.toFinset_card_le _) <|
      Nat.lt_of_le_of_lt (card_roots' _) <| by aesop)

lemma ps_card_eval_y_eq_zero_le_nat_degree_y {F : Type} [Field F] [DecidableEq F]
    (A : F[X][Y]) (hA : A ≠ 0) (P : Finset F) :
    (P.filter (fun y ↦ evalY y A = 0)).card ≤ natDegreeY A := by
  set A_poly : Polynomial (Polynomial F) := A
  have hA_poly : A_poly ≠ 0 := by assumption
  have h_roots : ((P.filter <| fun y ↦ A_poly.eval (C y) = 0).image (fun y ↦ C y)).card ≤
      A_poly.natDegree := by
    have h_roots : (P.filter (fun y ↦ A_poly.eval (C y) = 0)).image (fun y ↦ C y) ⊆
        A_poly.roots.toFinset := by intro; aesop
    exact le_trans (card_le_card h_roots)
      (le_trans (Multiset.toFinset_card_le _) (card_roots' _)) |> le_trans <| by aesop
  generalize_proofs at *
  rw [Finset.card_image_of_injective _ fun x y hxy ↦ by simpa using hxy] at h_roots
  aesop

lemma ps_coeff_mul_monomial_ite {R : Type} [Semiring R]
    (A : R[X]) (j i : ℕ) (r : R) :
    (A * Polynomial.monomial j r).coeff i =
      if j ≤ i then A.coeff (i - j) * r else 0 := by
  classical
  simp [← C_mul_X_pow_eq_monomial, ← mul_assoc, coeff_mul_X_pow', coeff_mul_C]

lemma ps_coeff_mul_sum_monomial {R : Type} [CommRing R]
    (A : R[X]) (m n : ℕ) (hm : A.natDegree ≤ m)
    (c : Fin n → R) (i : ℕ) :
    (A * (∑ j : Fin n, Polynomial.monomial (j : ℕ) (c j))).coeff i =
      ∑ j : Fin n,
        if (j : ℕ) ≤ i ∧ i ≤ (j : ℕ) + m
        then A.coeff (i - (j : ℕ)) * c j else 0 := by
  classical
  have hdeg : ∀ N : ℕ, m < N → A.coeff N = 0 := (natDegree_le_iff_coeff_eq_zero).1 hm
  simp [Finset.mul_sum, finsetSum_coeff, ps_coeff_mul_monomial_ite]
  grind only [cases Or]

private lemma ps_swap_coeff {F : Type} [CommRing F] (g : F[X][Y]) (i j : ℕ) :
    Bivariate.coeff (swap g) i j = Bivariate.coeff g j i := by
  have h_swap_coeff : ∀ (g : F[X][Y]) (i j : ℕ),
      Bivariate.coeff (swap g) i j = Bivariate.coeff g j i := by
    unfold Bivariate.coeff
    -- By definition of swap, we have that swap g = ∑ i, ∑ j, g.coeff j * X^i * Y^j.
    have h_swap_def : ∀ g : F[X][Y], swap g = ∑ i ∈ g.support,
        ∑ j ∈ (g.coeff i).support, monomial j (monomial i ((g.coeff i).coeff j)) := by
      intro g
      simp [swap, eval_finsetSum, aeval_def, eval₂_eq_sum, sum_def,
        ← C_mul_X_pow_eq_monomial, Finset.sum_mul _ _ _ ]
      ac_rfl
    simp only [h_swap_def, finsetSum_coeff, coeff_monomial, sum_ite_eq', mem_support_iff, ne_eq]
    intro g i j
    rw [Finset.sum_eq_single i] <;> simp_all only [swap_apply, mem_support_iff, ne_eq]
    · split_ifs <;> simp_all
    · intro b hb hb'; split_ifs <;> simp_all [coeff_monomial]
    · push Not; intro h; simp [h]
  exact h_swap_coeff g i j

private lemma ps_degree_x_swap_le {F : Type} [CommRing F] (f : F[X][Y]) :
    degreeX (swap f) ≤ natDegreeY f := by
  by_contra h_contra
  obtain ⟨n, hn⟩ : ∃ n ∈ (swap f).support,
      (swap f).coeff n ≠ 0 ∧ (swap f).coeff n ≠ 0 ∧ ((swap f).coeff n).natDegree > f.natDegree := by
    unfold degreeX at h_contra; aesop;
  obtain ⟨m, hm⟩ : ∃ m > f.natDegree, ((swap f).coeff n).coeff m ≠ 0 := by
    exact ⟨((swap f).coeff n).natDegree, hn.2.2.2, by aesop⟩
  have h_coeff_swap : ((swap f).coeff n).coeff m = (f.coeff m).coeff n := by
    convert ps_swap_coeff f m n using 1 <;> rfl
  exact hm.2 (h_coeff_swap.symm ▸ by rw [coeff_eq_zero_of_natDegree_lt hm.1]; aesop)

private lemma ps_degree_x_swap_ge {F : Type} [CommRing F] (f : F[X][Y]) (hf : f ≠ 0) :
    natDegreeY f ≤ degreeX (swap f) := by
  obtain ⟨N, hN⟩ : ∃ N, N = f.natDegree ∧ f.coeff N ≠ 0 := by
    simp_all only [ne_eq, ↓existsAndEq, coeff_natDegree, leadingCoeff_eq_zero,
      not_false_eq_true, and_self]
  obtain ⟨n, hn⟩ : ∃ n, n = (f.coeff N).natDegree ∧ (f.coeff N).coeff n ≠ 0 := by
    contrapose! hN; aesop;
  have h_swap_coeff_nonzero : ((swap f).coeff n).coeff N ≠ 0 := by
    convert hn.2 using 1;
    convert ps_swap_coeff f N n using 1 <;> rfl
  have h_swap_coeff_nonzero_natDegree : (swap f).coeff n ≠ 0 :=
    (ne_of_apply_ne Polynomial.coeff fun a ↦ h_swap_coeff_nonzero (congrFun a.symm N)).symm
  have h_swap_coeff_nonzero_natDegree_le : Nat.max (((swap f).coeff n).natDegree)
      (Nat.max (((swap f).coeff n).natDegree) N) ≤ degreeX (swap f) := by
    refine le_trans ?_ (Finset.le_sup <| show n ∈ ((swap f).support) from ?_) <;>
      simp_all only [ne_eq, ext_iff, coeff_zero, not_forall, coeff_natDegree, swap_apply,
        le_sup_left, sup_of_le_right, sup_le_iff, le_refl, true_and]
    · exact le_natDegree_of_ne_zero h_swap_coeff_nonzero |> le_trans (by aesop)
    · aesop
  have h_swap_coeff_nonzero_natDegree_le_natDegreeY : N ≤ Nat.max (((swap f).coeff n).natDegree)
      (Nat.max (((swap f).coeff n).natDegree) N) := le_max_of_le_right (le_max_right _ _)
  have h_final : f.natDegree ≤ degreeX (swap f) := by
    bv_omega
  exact h_final

lemma ps_degree_x_swap {F : Type} [CommRing F] (f : F[X][Y]) :
    degreeX (swap f) = natDegreeY f := by
  by_cases hf : f = 0
  · subst hf; simp [degreeX, natDegreeY]
  · exact le_antisymm (ps_degree_x_swap_le f) (ps_degree_x_swap_ge f hf)

lemma ps_descend_eval_x {F : Type} [Field F]
    {A B G A1 B1 : F[X][Y]} (hA : A = G * A1) (hB : B = G * B1)
    (x : F) (hx : evalX x G ≠ 0) (q : F[X]) (h : evalX x B = q * evalX x A) :
    evalX x B1 = q * evalX x A1 := by
  simp_all only [evalX_eq_map, ne_eq, Polynomial.map_mul]
  exact mul_left_cancel₀ hx <| by linear_combination h;

lemma ps_descend_eval_y {F : Type} [Field F]
    {A B G A1 B1 : F[X][Y]} (hA : A = G * A1) (hB : B = G * B1)
    (y : F) (hy : evalY y G ≠ 0) (q : F[X]) (h : evalY y B = q * evalY y A) :
    evalY y B1 = q * evalY y A1 := by
  unfold evalY at *
  simp_all only [ne_eq, eval_mul]
  exact mul_left_cancel₀ hy <| by linear_combination h

lemma ps_eval_x_eq_map {F : Type} [CommSemiring F]
    (x : F) (f : F[X][Y]) :
    evalX x f = f.map (evalRingHom x) := by
  classical
  ext n; simp [evalX, toFinsupp_apply]

lemma ps_eval_y_eq_eval_x_swap {F : Type} [CommRing F]
    (y : F) (f : F[X][Y]) :
    evalY y f = evalX y (swap f) := by
  letI : Algebra F[X] F[X] := Polynomial.algebra (R := F) (A := F)
  convert aveal_eq_map_swap y f using 1
  · unfold evalY; simp [Polynomial.aeval_def]
  · -- By definition of `evalX`, we have `evalX y (swap f) = (swap f).map (evalRingHom y)`.
    rw [ps_eval_x_eq_map]
    rfl

lemma ps_exists_x_preserve_nat_degree_y {F : Type} [Field F]
    (B : F[X][Y]) (hB : B ≠ 0) (P_x : Finset F)
    (hcard : P_x.card > degreeX B) :
    ∃ x ∈ P_x, (evalX x B).natDegree = natDegreeY B := by
  obtain ⟨x, hx⟩ : ∃ x ∈ P_x, (B.coeff (natDegreeY B)).eval x ≠ 0 := by
    have h_p_ne_zero : natDegree (B.coeff (natDegreeY B)) < P_x.card := by
      exact lt_of_le_of_lt
        (Finset.le_sup (f := fun n ↦ (B.coeff n).natDegree)
          (natDegree_mem_support_of_nonzero hB))
        hcard
    by_contra h_contra; push Not at h_contra
    have h_poly_zero : leadingCoeffY B = 0 :=
      eq_zero_of_degree_lt_of_eval_finset_eq_zero P_x
        (degree_le_natDegree.trans_lt (by exact_mod_cast h_p_ne_zero))
        h_contra
    exact absurd h_poly_zero (leadingCoeffY_ne_zero _ |>.2 hB)
  refine ⟨x, hx.1, le_antisymm ?_ ?_⟩
  · rw [evalX]
    simp only [natDegree_le_iff_degree_le, degree_le_iff_coeff_zero, Nat.cast_lt,
      coeff_ofFinsupp, Finsupp.mapRange_apply]
    intro m hm
    rw [toFinsupp_apply, coeff_eq_zero_of_natDegree_lt hm]
    simp
  · refine le_natDegree_of_ne_zero ?_
    convert hx.2 using 1
    all_goals rfl

lemma ps_exists_y_preserve_degree_x {F : Type} [Field F]
    (B : F[X][Y]) (hB : B ≠ 0) (P_y : Finset F) (hcard : P_y.card > natDegreeY B) :
    ∃ y ∈ P_y, (evalY y B).natDegree = degreeX B := by
  revert B hB P_y hcard;
  intro B hB P_y hcard
  set d := degreeX B with hd
  set g := B.sum (fun j p ↦ Polynomial.monomial j (p.coeff d)) with hg
  have hg_ne_zero : g ≠ 0 := by
    obtain ⟨j0, hj0⟩ : ∃ j0 ∈ B.support, (B.coeff j0).natDegree = d := by
      have h_sup : ∃ j0 ∈ B.support, ∀ j ∈ B.support,
          (B.coeff j).natDegree ≤ (B.coeff j0).natDegree := by
        apply_rules [Finset.exists_max_image]; aesop
      generalize_proofs at *; (
      exact ⟨h_sup.choose, h_sup.choose_spec.1, le_antisymm
        (Finset.le_sup (f := fun j ↦ (B.coeff j).natDegree) h_sup.choose_spec.1)
        (Finset.sup_le fun j hj ↦ h_sup.choose_spec.2 j hj)⟩)
    have h_nonzero_term : (B.coeff j0).coeff d ≠ 0 := by
      rw [← hj0.2, coeff_natDegree]; aesop
    have h_g_nonzero : g.coeff j0 = (B.coeff j0).coeff d := by
      simp only [coeff_sum, coeff_monomial, hg, hd]
      rw [sum_def]
      aesop
    exact fun h ↦ h_nonzero_term (by rw [← h_g_nonzero, h, coeff_zero])
  have hg_natDegree : natDegree g ≤ natDegreeY B := by
    refine le_trans (natDegree_sum_le _ _) (Finset.sup_le ?_)
    intro j hj
    exact (natDegree_monomial_le _).trans (le_natDegree_of_mem_supp _ hj)
  have hg_eval_nonzero : ∃ y ∈ P_y, g.eval y ≠ 0 := by
    by_contra! hcard_contra
    exact hg_ne_zero (eq_zero_of_degree_lt_of_eval_finset_eq_zero P_y
      (degree_le_natDegree.trans_lt (by exact_mod_cast lt_of_le_of_lt hg_natDegree hcard))
      hcard_contra)
  obtain ⟨y, hy⟩ := hg_eval_nonzero
  use y, hy.left
  have h_deg_y : (evalY y B).natDegree ≤ d := by
    have h_deg_y : ∀ j ∈ B.support, natDegree (B.coeff j) ≤ d :=
      fun j hj ↦ Finset.le_sup (f := fun n ↦ (B.coeff n).natDegree) hj
    rw [evalY, eval_eq_sum, sum_def]
    exact le_trans
      (natDegree_sum_le _ _) (Finset.sup_le fun i hi ↦ le_trans (natDegree_mul_le ..) (by aesop))
  have h_deg_y_eq : (evalY y B).coeff d = g.eval y := by
    simp only [sum_def, eval_finsetSum, eval_monomial, g]
    unfold evalY
    simp only [eval_eq_sum, sum_def, finsetSum_coeff]
    refine Finset.sum_congr rfl fun i hi ↦ ?_
    induction i <;> simp_all [coeff_mul, coeff_C, pow_succ'] ; ring_nf
    rw [sum_eq_single (degreeX B, 0)] <;> simp only [mem_antidiagonal, ne_eq,
      Nat.sum_antidiagonal_eq_sum_range_succ_mk, Nat.succ_eq_add_one, sum_ite_eq', mem_range,
      Order.lt_add_one_iff, zero_le, ↓reduceIte, tsub_zero, mul_eq_zero, Prod.forall, Prod.mk.injEq,
      not_and]
    all_goals ring_nf
    · simp [coeff_zero_eq_eval_zero, eval_pow, eval_C]
    · intro a b hab h; rcases b with (_ | b) <;> simp_all [coeff_eq_zero_of_natDegree_lt]
    · aesop
  exact le_antisymm h_deg_y (le_natDegree_of_ne_zero (by aesop))

lemma ps_filter_nonzero_card_y {F : Type} [Field F] [DecidableEq F]
    (A : F[X][Y]) (hA : A ≠ 0) (P_y : Finset F) (bound : ℕ)
    (h_bound_ge : bound ≥ natDegreeY A)
    (h_card_gt : P_y.card > bound) :
    (P_y.filter (fun y ↦ evalY y A ≠ 0)).card > bound - natDegreeY A := by
  have := ps_card_eval_y_eq_zero_le_nat_degree_y A hA P_y;
  simp_all only [ne_eq, ge_iff_le, gt_iff_lt, Finset.filter_not, Finset.card_sdiff]
  rw [Finset.inter_eq_left.mpr (Finset.filter_subset _ _)] ; omega

lemma ps_filter_nonzero_card_x {F : Type} [Field F] [DecidableEq F]
    (A : F[X][Y]) (hA : A ≠ 0) (P_x : Finset F) (bound : ℕ)
    (h_bound_ge : bound ≥ degreeX A)
    (h_card_gt : P_x.card > bound) :
    (P_x.filter (fun x ↦ evalX x A ≠ 0)).card > bound - degreeX A := by
  have h_card_splits : P_x.card =
      (P_x.filter (fun x ↦ evalX x A = 0)).card + (P_x.filter (fun x ↦ evalX x A ≠ 0)).card := by
    rw [Finset.card_filter_add_card_filter_not]
  linarith [ps_card_eval_x_eq_zero_le_degree_x A hA P_x,
    Nat.sub_add_cancel (show degreeX A ≤ bound from h_bound_ge)]

lemma ps_degX_bound {F : Type} [Field F]
    {A B P : F[X][Y]} (hA : A ≠ 0) (hP : P ≠ 0) (hBA : B = P * A)
    (b_x b_y a_x a_y : ℕ) (n_y : ℕ+) (h_by_ge_ay : b_y ≥ a_y)
    (h_f_degY : a_y ≥ natDegreeY A) (h_g_degY : b_y ≥ natDegreeY B)
    (P_y : Finset F) (h_card_Py : n_y ≤ P_y.card) (quot_x : F → F[X])
    (h_quot_x : ∀ y ∈ P_y, (quot_x y).natDegree ≤ b_x - a_x ∧ evalY y B = (quot_x y) * (evalY y A))
    (h_by_lt_ny : b_y < n_y) :
    degreeX P ≤ b_x - a_x := by
  classical
  by_contra h_contra
  obtain ⟨y, hy⟩ : ∃ y ∈ P_y, (evalY y P).natDegree = degreeX P ∧ evalY y A ≠ 0 := by
    have h_card_filter : (P_y.filter (fun y ↦ evalY y A ≠ 0)).card > natDegreeY P := by
      have h_filter_card : (P_y.filter (fun y ↦ evalY y A ≠ 0)).card > b_y - natDegreeY A := by
        apply_rules [ps_filter_nonzero_card_y]
        all_goals linarith
      grind +qlia
    have := ps_exists_y_preserve_degree_x P hP (P_y.filter (fun y ↦ evalY y A ≠ 0)) ?_ <;> aesop
  -- Since $B = P * A$, we have $evalY y B = evalY y P * evalY y A$.
  have h_eval_Y_B : evalY y B = evalY y P * evalY y A := by unfold evalY; aesop
  have := h_quot_x y hy.1
  simp_all
  linarith

lemma ps_degY_bound {F : Type} [Field F]
    {A B P : F[X][Y]} (hA : A ≠ 0) (hP : P ≠ 0) (hBA : B = P * A)
    (b_x b_y a_x a_y : ℕ) (n_x : ℕ+) (h_bx_ge_ax : b_x ≥ a_x)
    (h_f_degX : a_x ≥ degreeX A) (h_g_degY : b_y ≥ natDegreeY B)
    (P_x : Finset F) (h_card_Px : n_x ≤ P_x.card) (quot_y : F → F[X])
    (h_quot_y : ∀ x ∈ P_x, (quot_y x).natDegree ≤ b_y - a_y ∧ evalX x B = (quot_y x) * (evalX x A))
    (h_bx_lt_nx : b_x < (n_x : ℕ)) (hdegX_P_le : degreeX P ≤ b_x - a_x) :
    natDegreeY P ≤ b_y - a_y := by
  classical
  obtain ⟨x, hx⟩ : ∃ x ∈ P_x, (evalX x A) ≠ 0 ∧ (evalX x P).natDegree = natDegreeY P := by
    have h_filter : (P_x.filter (fun x ↦ (evalX x A) ≠ 0)).card > (degreeX P) := by
      have := ps_filter_nonzero_card_x A hA P_x b_x (by linarith) (by linarith); simp_all; omega
    obtain ⟨x, hx⟩ : ∃ x ∈ P_x.filter (fun x ↦ (evalX x A) ≠ 0),
        (evalX x P).natDegree = (natDegreeY P) := by apply_rules [ps_exists_x_preserve_nat_degree_y]
    aesop
  -- Since $evalX x B = quot_y x * evalX x A$, we have $evalX x P = quot_y x$.
  have h_evalX_P : evalX x P = quot_y x := by
    have h_evalX_P : evalX x B = evalX x P * evalX x A := by rw [hBA, evalX_mul]
    exact mul_left_cancel₀ hx.2.1 <| by
      linear_combination h_evalX_P.symm.trans (h_quot_y x hx.1 |>.2)
  exact hx.2.2 ▸ h_evalX_P ▸ h_quot_y x hx.1 |>.1

lemma ps_degree_bounds_of_mul {F : Type} [Field F]
    (a_x a_y b_x b_y : ℕ) (n_x n_y : ℕ+)
    (h_bx_ge_ax : b_x ≥ a_x) (h_by_ge_ay : b_y ≥ a_y)
    {A B P : F[X][Y]} (hA : A ≠ 0) (hBA : B = P * A)
    (h_f_degX : a_x ≥ degreeX A) (h_f_degY : a_y ≥ natDegreeY A)
    (h_g_degY : b_y ≥ natDegreeY B) (P_x P_y : Finset F) [Nonempty P_x] [Nonempty P_y]
    (quot_x : F → F[X]) (quot_y : F → F[X])
    (h_card_Px : n_x ≤ P_x.card) (h_card_Py : n_y ≤ P_y.card)
    (h_quot_x : ∀ y ∈ P_y, (quot_x y).natDegree ≤ b_x - a_x ∧ evalY y B = (quot_x y) * (evalY y A))
    (h_quot_y : ∀ x ∈ P_x, (quot_y x).natDegree ≤ b_y - a_y ∧ evalX x B = (quot_y x) * (evalX x A))
    (h_le_1 : 1 > (b_x : ℚ) / (n_x : ℚ) + (b_y : ℚ) / (n_y : ℚ)) :
    degreeX P ≤ b_x - a_x ∧ natDegreeY P ≤ b_y - a_y := by
  classical
  letI : DecidableEq F := Classical.decEq F
  by_cases hB0 : B = 0
  · have hP0 : P = 0 := by
      rcases mul_eq_zero.mp (hBA ▸ hB0 : P * A = 0) with h | h
      · exact h
      · exact absurd h hA
    subst hP0
    constructor <;> simp [degreeX, natDegreeY]
  · have hP : P ≠ 0 := fun h ↦ hB0 (by simp [hBA, h])
    have hdegX := ps_degX_bound hA hP hBA b_x b_y a_x a_y n_y h_by_ge_ay
      h_f_degY h_g_degY P_y h_card_Py quot_x h_quot_x (ps_by_lt_ny h_le_1)
    exact ⟨hdegX, ps_degY_bound hA hP hBA b_x b_y a_x a_y n_x h_bx_ge_ax
      h_f_degX h_g_degY P_x h_card_Px quot_y h_quot_y (ps_bx_lt_nx h_le_1) hdegX⟩

lemma ps_gcd_decompose {F : Type} [Field F]
    {A B : F[X][Y]} (hA : A ≠ 0) (hB : B ≠ 0) :
    ∃ G A1 B1 : F[X][Y],
      A = G * A1 ∧ B = G * B1 ∧ IsRelPrime A1 B1 ∧ A1 ≠ 0 ∧ B1 ≠ 0 := by
  have h_ufd : GCDMonoid (F[X][Y]) := UniqueFactorizationMonoid.toGCDMonoid F[X][Y]
  obtain ⟨G, hG⟩ : ∃ G : F[X][Y], G ∣ A ∧ G ∣ B ∧ ∀ C : F[X][Y], C ∣ A → C ∣ B → C ∣ G :=
    ⟨GCDMonoid.gcd A B, GCDMonoid.gcd_dvd_left A B,
      GCDMonoid.gcd_dvd_right A B, fun C h₁ h₂ ↦ GCDMonoid.dvd_gcd h₁ h₂⟩
  obtain ⟨A1, hA1⟩ := hG.left
  obtain ⟨B1, hB1⟩ := hG.right.left
  refine ⟨G, A1, B1, hA1, hB1, ?_, ?_, ?_⟩ <;>
    simp_all only [ne_eq, mul_eq_zero, not_or, false_or, dvd_mul_right, true_and, IsRelPrime]
  · intro d hd1 hd2
    specialize hG (G * d)
    simp_all only [ne_eq, not_false_eq_true, mul_dvd_mul_iff_left, forall_const]
    exact isUnit_of_dvd_one (by
    obtain ⟨k, hk⟩ := hG
    exact ⟨k, mul_left_cancel₀ hA.1 <| by linear_combination hk⟩)
  all_goals push Not

lemma ps_is_rel_prime_swap {F : Type} [CommRing F] {A B : F[X][Y]}
    (h : IsRelPrime A B) : IsRelPrime (swap A) (swap B) := by
  classical
  let f : F[X][Y] ≃+* F[X][Y] := swap.toRingEquiv
  refine fun d hdA hdB ↦ ?_
  have hunit : IsUnit (f.symm d) :=
    h ((map_dvd_iff f).1 (by rw [RingEquiv.apply_symm_apply]; exact hdA))
      ((map_dvd_iff f).1 (by rw [RingEquiv.apply_symm_apply]; exact hdB))
  have : IsUnit (f (f.symm d)) := f.toRingHom.isUnit_map hunit
  simpa [f] using this

lemma ps_nat_degree_y_swap {F : Type} [CommRing F]
    (f : F[X][Y]) : natDegreeY (swap f) = degreeX f := by
  have h := ps_degree_x_swap (swap f)
  have hs : swap (swap f) = f := swap.left_inv f
  rw [hs] at h
  exact h.symm


Source
https://github.com/Verified-zkEVM/ArkLib/blob/e65197892890b8fd9b0dc05b8980273cf1d595cc/ArkLib/Data/CodingTheory/PolishchukSpielman/Degrees.lean yukon-proof-operation:1f589a4e08d6c64a7b1004b1dff4cfb0962d204a2e593b1dd690eb881f5efe7a [yukon-proof-receipt:eyJlbnZpcm9ubWVudCI6eyJtYXRobGliUmV2IjoiMGRmNDQ0YTM2MGVhYTYwYWI4YzExZGNhNTFhODZhZjY5Mjk1NTQ3NCIsInRvb2xjaGFpbiI6ImxlYW5wcm92ZXIvbGVhbjQ6djQuMzMuMSJ9LCJoYXNoIjoiNmQ0ZjllMDkyM2YxYmNlNTEwNzA0OTg2ZTk3ODk3MWE3ZGI0YzI0MWU0ZGIwMjNmNmM1MGY3YzAwYjJiNDMyNCIsImtpbmQiOiJkZWZpbml0aW9uIiwibWFya2VyIjoieXVrb24tcHJvb2Ytb3BlcmF0aW9uOjFmNTg5YTRlMDhkNmM2NGE3YjEwMDRiMWRmZjRjZmIwOTYyZDIwNGEyZTU5M2IxZGQ2OTBlYjg4MWY1ZWZlN2EiLCJ0YWciOiJiZXR0ZXItY29kZXMiLCJ0YXJnZXQiOiJZdWtvbl8yNDJiZTljNDhjZjBkMGM0NjRkMTMyOGQiLCJ2IjoyfQ]

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