Ideal membership in multivariate polynomials
Lax619925.IdealMembership · concepts/Lax619925/IdealMembership.lean · lax-619925
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The ideal-membership statement on which the paper's unified ideal-chain argument rests. It says that ideal membership in is decidable in the propositional sense: for every finite set of generators , there exists a -valued function such that exactly when lies in the ideal generates — the same shape as the other statements. It is proven in the proofs package by a classical argument: excluded middle supplies the characteristic function of the ideal. The constructive Gröbner-basis decision procedure (Buchberger's algorithm) — the Gröbner-basis fact mathlib does not yet provide, its file implementing division only — is the algorithmic content of the paper's decidability claims and is out of scope for this submission. The paper's unified ideal-chain argument (the chain of ideals stabilising by Hilbert's basis theorem) reduces the equality problem for the Hadamard, shuffle, and infiltration automata to this statement.
Concept map
In the paper
- page 37 of this submission's paper
Lean source view on GitHub
| 1 | import Mathlib.Data.Real.Basic |
| 2 | import Mathlib.Data.Fin.Basic |
| 3 | import Mathlib.Data.Fintype.Basic |
| 4 | import Mathlib.Data.Finset.Basic |
| 5 | import Mathlib.Algebra.MvPolynomial.Basic |
| 6 | import Mathlib.RingTheory.Ideal.Basic |
| 7 | |
| 8 | /-! |
| 9 | --- |
| 10 | title: Ideal membership in multivariate polynomials |
| 11 | type: theorem |
| 12 | --- |
| 13 | The ideal-membership statement on which the paper's unified ideal-chain |
| 14 | argument rests. It says that ideal membership in `MvPolynomial (Fin k) ℚ` |
| 15 | is decidable in the propositional sense: for every finite set of generators |
| 16 | `gens`, there exists a `Bool`-valued function `dec` such that `dec p = true` |
| 17 | exactly when `p` lies in the ideal `gens` generates — the same shape as the |
| 18 | other `*EqualityDecidable` statements. It is proven in the proofs package by |
| 19 | a classical argument: excluded middle supplies the characteristic function of |
| 20 | the ideal. The constructive Gröbner-basis decision procedure (Buchberger's |
| 21 | algorithm) — the Gröbner-basis fact mathlib does not yet provide, its |
| 22 | `MvPolynomial.Groebner` file implementing division only — is the algorithmic |
| 23 | content of the paper's decidability claims and is out of scope for this |
| 24 | submission. The paper's unified ideal-chain argument (the chain `I_n` of |
| 25 | ideals stabilising by Hilbert's basis theorem) reduces the equality problem |
| 26 | for the Hadamard, shuffle, and infiltration automata to this statement. |
| 27 | -/ |
| 28 | |
| 29 | namespace Lax619925.IdealMembership |
| 30 | |
| 31 | /-- Ideal membership in the multivariate polynomial ring over `ℚ` is decidable: |
| 32 | given a finite set of generators, there is a decision procedure `dec` such |
| 33 | that `dec p = true` iff `p` lies in the ideal the generators span. Proven |
| 34 | in the proofs package by a classical argument (excluded middle supplies the |
| 35 | characteristic function); the constructive Gröbner-basis procedure is out |
| 36 | of scope. -/ |
| 37 | axiom IdealMembershipDecidable (k : ℕ) (gens : Finset (MvPolynomial (Fin k) ℚ)) : |
| 38 | ∃ dec : MvPolynomial (Fin k) ℚ → Bool, ∀ p, dec p = true ↔ p ∈ Ideal.span ↑gens |
| 39 | |
| 40 | end Lax619925.IdealMembership |
| 41 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments