Skip to content

[Merged by Bors] - feat: tactic compute_degree#6221

Closed
adomani wants to merge 57 commits intomasterfrom
adomani_compute_degree
Closed

[Merged by Bors] - feat: tactic compute_degree#6221
adomani wants to merge 57 commits intomasterfrom
adomani_compute_degree

Conversation

@adomani
Copy link
Copy Markdown
Contributor

@adomani adomani commented Jul 28, 2023

This PR ports the whole compute_degree tactic from mathlib3.

The tactic makes progress on goals of the form

  • natDegree f ≤ d,
  • degree f ≤ d,
  • natDegree f = d,
  • degree f = d,
  • coeff f n = r.

The variant compute_degree! applies norm_num and assumption to all left-over goals.

For instance, here is a valid computation of the degree of the 105-th cyclotomic polynomial:

example : natDegree
    (1 + X + X ^ 2 - X ^ 5 - X ^ 6 - 2 * X ^ 7 - X ^ 8 - X ^ 9 + X ^ 12 + X ^ 13 + X ^ 14 +
        X ^ 15 + X ^ 16 + X ^ 17 - X ^ 20 - X ^ 22 - X ^ 24 - X ^ 26 - X ^ 28 + X ^ 31 + X ^ 32 +
        X ^ 33 + X ^ 34 + X ^ 35 + X ^ 36 - X ^ 39 - X ^ 40 - 2 * X ^ 41 - X ^ 42 - X ^ 43 +
        X ^ 46 + X ^ 47 + X ^ 48 : ℤ[X]) = 48 := by
  compute_degree!

(Lean takes approximately 3s on my computer to prove the computation above.)

Affected files:

Mathlib/Lean/Expr/Basic.lean
Mathlib/Tactic/ComputeDegree.lean
test/ComputeDegree.lean

Open in Gitpod

@ghost ghost added the blocked-by-other-PR This PR depends on another PR (this label is automatically managed by a bot) label Jul 28, 2023
@adomani adomani added awaiting-review modifies-tactic-syntax This PR adds a new interactive tactic or modifies the syntax of an existing tactic. t-meta Tactics, attributes or user commands labels Jul 28, 2023
bors bot pushed a commit that referenced this pull request Aug 10, 2023
This PR extracts some lemmas about polynomials that are helpful for the tactic `compute_degree` (#6221).

The signature of a theorem changed:
```lean
theorem coeff_pow_of_natDegree_le (pn : p.natDegree ≤ n) :
    (p ^ m).coeff (n * m) = p.coeff n ^ m  -- <-- the order of the product was `n * m`
    (p ^ m).coeff (m * n) = p.coeff n ^ m  -- <-- and it became `m * n`
```
Modified files:
```
Data/Polynomial/Basic.lean
Data/Polynomial/Degree/Lemmas.lean
Data/Polynomial/Degree/Definitions.lean
Data/Polynomial/Coeff.lean  -- for a "`simp` can prove this" golf
```
@ghost ghost removed the blocked-by-other-PR This PR depends on another PR (this label is automatically managed by a bot) label Aug 10, 2023
@ghost
Copy link
Copy Markdown

ghost commented Aug 10, 2023

This PR/issue depends on:

@ghost ghost added the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Aug 10, 2023
@adomani adomani force-pushed the adomani_compute_degree branch from 811c325 to a66f2ca Compare August 10, 2023 14:35
kim-em pushed a commit that referenced this pull request Aug 14, 2023
This PR extracts some lemmas about polynomials that are helpful for the tactic `compute_degree` (#6221).

The signature of a theorem changed:
```lean
theorem coeff_pow_of_natDegree_le (pn : p.natDegree ≤ n) :
    (p ^ m).coeff (n * m) = p.coeff n ^ m  -- <-- the order of the product was `n * m`
    (p ^ m).coeff (m * n) = p.coeff n ^ m  -- <-- and it became `m * n`
```
Modified files:
```
Data/Polynomial/Basic.lean
Data/Polynomial/Degree/Lemmas.lean
Data/Polynomial/Degree/Definitions.lean
Data/Polynomial/Coeff.lean  -- for a "`simp` can prove this" golf
```
kim-em pushed a commit that referenced this pull request Aug 15, 2023
This PR extracts some lemmas about polynomials that are helpful for the tactic `compute_degree` (#6221).

The signature of a theorem changed:
```lean
theorem coeff_pow_of_natDegree_le (pn : p.natDegree ≤ n) :
    (p ^ m).coeff (n * m) = p.coeff n ^ m  -- <-- the order of the product was `n * m`
    (p ^ m).coeff (m * n) = p.coeff n ^ m  -- <-- and it became `m * n`
```
Modified files:
```
Data/Polynomial/Basic.lean
Data/Polynomial/Degree/Lemmas.lean
Data/Polynomial/Degree/Definitions.lean
Data/Polynomial/Coeff.lean  -- for a "`simp` can prove this" golf
```
Copy link
Copy Markdown
Contributor

@kmill kmill left a comment

Choose a reason for hiding this comment

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

Thanks for writing this tactic. There are some things I'd like to see changed before it is merged, and I've tested all these suggestions locally.

@adomani
Copy link
Copy Markdown
Contributor Author

adomani commented Sep 2, 2023

Kyle, thank you so much for taking the time to review the PR!

I've looked through your suggestions and I find them all great! I hope to have time later today to sit at a computer and implement them.

@kmill
Copy link
Copy Markdown
Contributor

kmill commented Sep 2, 2023

I think this is in a good state now, and the user interface seems well-specified enough (with internals solid enough) that I'm happy to merge it. One thing we might want in the future is to have compute_degree be changed into a collection of norm_num extensions, with compute_degree in particular applying to the goals laid out in the docstring. One might even have compute_degree be a version of norm_num specialized to just degree/natDegree/coeff expressions and inequality goals involving them, letting it automatically compute degrees.

Anyway, the perfect is the enemy of the good, so

bors r+

@github-actions github-actions bot added ready-to-merge This PR has been sent to bors. and removed awaiting-review labels Sep 2, 2023
bors bot pushed a commit that referenced this pull request Sep 2, 2023
This PR ports the whole `compute_degree` tactic from mathlib3.

The tactic makes progress on goals of the form
*  `natDegree f ≤ d`,
*  `degree f ≤ d`,
*  `natDegree f = d`,
*  `degree f = d`,
*  `coeff f n = r`.

The variant `compute_degree!` applies `norm_num` and `assumption` to all left-over goals.

For instance, here is a valid computation of the degree of the 105-th cyclotomic polynomial:
```lean
example : natDegree
    (1 + X + X ^ 2 - X ^ 5 - X ^ 6 - 2 * X ^ 7 - X ^ 8 - X ^ 9 + X ^ 12 + X ^ 13 + X ^ 14 +
        X ^ 15 + X ^ 16 + X ^ 17 - X ^ 20 - X ^ 22 - X ^ 24 - X ^ 26 - X ^ 28 + X ^ 31 + X ^ 32 +
        X ^ 33 + X ^ 34 + X ^ 35 + X ^ 36 - X ^ 39 - X ^ 40 - 2 * X ^ 41 - X ^ 42 - X ^ 43 +
        X ^ 46 + X ^ 47 + X ^ 48 : ℤ[X]) = 48 := by
  compute_degree!
```
(Lean takes approximately 3s on my computer to prove the computation above.)

Affected files:
```
Mathlib/Lean/Expr/Basic.lean
Mathlib/Tactic/ComputeDegree.lean
test/ComputeDegree.lean
```
@bors
Copy link
Copy Markdown

bors bot commented Sep 2, 2023

Pull request successfully merged into master.

Build succeeded!

The publicly hosted instance of bors-ng is deprecated and will go away soon.

If you want to self-host your own instance, instructions are here.
For more help, visit the forum.

If you want to switch to GitHub's built-in merge queue, visit their help page.

@bors bors bot changed the title feat: tactic compute_degree [Merged by Bors] - feat: tactic compute_degree Sep 2, 2023
@bors bors bot closed this Sep 2, 2023
@bors bors bot deleted the adomani_compute_degree branch September 2, 2023 13:20
bors bot pushed a commit that referenced this pull request Sep 6, 2023
This PR is a companion to #6221.  It uses the tactic `compute_degree` to golf two proofs and restore a proof closer to its mathlib3 version.
ebab pushed a commit that referenced this pull request Sep 11, 2023
This PR is a companion to #6221.  It uses the tactic `compute_degree` to golf two proofs and restore a proof closer to its mathlib3 version.
kodyvajjha pushed a commit that referenced this pull request Sep 22, 2023
This PR is a companion to #6221.  It uses the tactic `compute_degree` to golf two proofs and restore a proof closer to its mathlib3 version.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

modifies-tactic-syntax This PR adds a new interactive tactic or modifies the syntax of an existing tactic. ready-to-merge This PR has been sent to bors. t-meta Tactics, attributes or user commands

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants