Ideal membership in multivariate polynomials

Lax619925.IdealMembership · concepts/Lax619925/IdealMembership.lean · lax-619925

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    The ideal-membership statement on which the paper's unified ideal-chain argument rests. It says that ideal membership in MvPolynomial(Fink)QMvPolynomial (Fin k) ℚ is decidable in the propositional sense: for every finite set of generators gensgens, there exists a BoolBool-valued function decdec such that decp=truedec p = true exactly when pp lies in the ideal gensgens generates — the same shape as the other ∗EqualityDecidable*EqualityDecidable 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 MvPolynomial.GroebnerMvPolynomial.Groebner 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 InI_n of ideals stabilising by Hilbert's basis theorem) reduces the equality problem for the Hadamard, shuffle, and infiltration automata to this statement.

    Concept map
    1 concept
    100%
    Proven claimThis concept
    Evidence

    Each proof establishes this claim relative to its assumptions.

    In the paper

    • page 37 of this submission's paper

    Lean source view on GitHub

    1import Mathlib.Data.Real.Basic
    2import Mathlib.Data.Fin.Basic
    3import Mathlib.Data.Fintype.Basic
    4import Mathlib.Data.Finset.Basic
    5import Mathlib.Algebra.MvPolynomial.Basic
    6import Mathlib.RingTheory.Ideal.Basic
    7
    8/-!
    9---
    10title: Ideal membership in multivariate polynomials
    11type: theorem
    12---
    13The ideal-membership statement on which the paper's unified ideal-chain
    14argument rests. It says that ideal membership in `MvPolynomial (Fin k) ℚ`
    15is 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`
    17exactly when `p` lies in the ideal `gens` generates — the same shape as the
    18other `*EqualityDecidable` statements. It is proven in the proofs package by
    19a classical argument: excluded middle supplies the characteristic function of
    20the ideal. The constructive Gröbner-basis decision procedure (Buchberger's
    21algorithm) — the Gröbner-basis fact mathlib does not yet provide, its
    22`MvPolynomial.Groebner` file implementing division only — is the algorithmic
    23content of the paper's decidability claims and is out of scope for this
    24submission. The paper's unified ideal-chain argument (the chain `I_n` of
    25ideals stabilising by Hilbert's basis theorem) reduces the equality problem
    26for the Hadamard, shuffle, and infiltration automata to this statement.
    27-/
    28
    29namespace 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. -/
    37axiom IdealMembershipDecidable (k : ℕ) (gens : Finset (MvPolynomial (Fin k) ℚ)) :
    38 ∃ dec : MvPolynomial (Fin k) ℚ → Bool, ∀ p, dec p = true ↔ p ∈ Ideal.span ↑gens
    39
    40end Lax619925.IdealMembership
    41
    Show Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…