Skip to content

[Merged by Bors] - feat: port Data.MvPolynomial.Funext#3225

Closed
Parcly-Taxel wants to merge 12 commits intomasterfrom
port/Data.MvPolynomial.Funext
Closed

[Merged by Bors] - feat: port Data.MvPolynomial.Funext#3225
Parcly-Taxel wants to merge 12 commits intomasterfrom
port/Data.MvPolynomial.Funext

Conversation

@Parcly-Taxel
Copy link
Copy Markdown
Collaborator


Open in Gitpod

Mathbin -> Mathlib
fix certain import statements
move "by" to end of line
add import to Mathlib.lean
@Parcly-Taxel Parcly-Taxel added help-wanted The author needs attention to resolve issues WIP Work in progress mathlib-port This is a port of a theory file from mathlib. labels Apr 2, 2023
@Parcly-Taxel Parcly-Taxel added awaiting-review and removed help-wanted The author needs attention to resolve issues WIP Work in progress labels Apr 2, 2023

variable {R : Type _} [CommRing R] [IsDomain R] [Infinite R]

set_option maxHeartbeats 1000000 in
Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If this line is absent, there are timeouts. Should I leave it this way?

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

At minimum, needs to have a -- Porting note

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm trying to look at this now, but waiting on oleans / cache get! problems.

Two possibilities that I'd be okay with:

  1. Leave it in, with a porting note
  2. Split out two separate lemmas funext_fin_zero and funext_fin_succ.

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Okay, the answer here is that this proof should never have been in mathlib3 in the first place. There is a lemma that should have been factored out:

theorem eval_eval_finSuccEquiv (f : MvPolynomial (Fin (n + 1)) R) :
    (eval x) (Polynomial.eval q (finSuccEquiv R n f)) = eval (Fin.cons (eval x q) x) f := sorry

private theorem funext_fin {n : ℕ} {p : MvPolynomial (Fin n) R}
    (h : ∀ x : Fin n → R, eval x p = 0) : p = 0 := by
  induction' n with n ih
  · apply (MvPolynomial.isEmptyRingEquiv R (Fin 0)).injective
    rw [RingEquiv.map_zero]
    convert h finZeroElim
  · apply (finSuccEquiv R n).injective
    simp only [AlgEquiv.map_zero]
    refine Polynomial.funext fun q => ?_
    rw [Polynomial.eval_zero]
    apply ih fun x => ?_
    calc _ = _ := eval_eval_finSuccEquiv p
         _ = 0 := h _

eval_eval_finSuccEquiv needs to be proved, and moved to Mathlib.Data.MvPolynomial.Equiv, after eval_eq_eval_mv_eval'.

In @jcommelin's defence, when he wrote this proof in leanprover-community/mathlib3#4196 the API in Mathlib.Data.MvPolynomial.Equiv wasn't as developed.

@Parcly-Taxel, do you want to tackle this? (Up to you of course.)

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@Parcly-Taxel, I went down the rabbit hole and proved the theorem. There are some TODOs about things that need to be moved, still.

Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@semorrison Should we make a mathlib3 PR that moves the theorems to their proper files and rewrites funext_fin accordingly?

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think that would be a great idea, if you're up for it

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I've done this now.

@kim-em kim-em added WIP Work in progress merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) and removed awaiting-review labels Apr 3, 2023
@kim-em kim-em removed the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Apr 4, 2023
@Parcly-Taxel Parcly-Taxel added awaiting-review and removed WIP Work in progress labels Apr 19, 2023
@kim-em
Copy link
Copy Markdown
Contributor

kim-em commented Apr 20, 2023

As I've now written most of this, can someone else please review and merge?

Copy link
Copy Markdown
Member

@jcommelin jcommelin left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks 🎉

bors merge

@kim-em kim-em added ready-to-merge This PR has been sent to bors. and removed awaiting-review labels Apr 20, 2023
bors bot pushed a commit that referenced this pull request Apr 20, 2023
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
Co-authored-by: Johan Commelin <johan@commelin.net>
@bors
Copy link
Copy Markdown

bors bot commented Apr 20, 2023

Pull request successfully merged into master.

Build succeeded:

@bors bors bot changed the title feat: port Data.MvPolynomial.Funext [Merged by Bors] - feat: port Data.MvPolynomial.Funext Apr 20, 2023
@bors bors bot closed this Apr 20, 2023
@bors bors bot deleted the port/Data.MvPolynomial.Funext branch April 20, 2023 15:22
kbuzzard pushed a commit that referenced this pull request Apr 22, 2023
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
Co-authored-by: Johan Commelin <johan@commelin.net>
bors bot pushed a commit to leanprover-community/mathlib3 that referenced this pull request Apr 28, 2023
This proof was timing out in leanprover-community/mathlib4#3225, so I completely rewrote it using smaller lemmas. This is the backport.



Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
kim-em added a commit that referenced this pull request May 10, 2023
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
Co-authored-by: Johan Commelin <johan@commelin.net>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

mathlib-port This is a port of a theory file from mathlib. ready-to-merge This PR has been sent to bors.

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants