Skip to content

IrreduciblePolynomialQ

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

IrreduciblePolynomialQ[poly]

gives True if poly is an irreducible polynomial over the rationals.

Notes Option Extension -\> alpha | {alpha\_i} tests irreducibility over the field extension generated by the algebraic numbers alpha\_i. Option Extension -\> Automatic extends Q by every algebraic-number coefficient in poly; Extension -\> All tests absolute irreducibility over the complex numbers. Option GaussianIntegers -\> True tests irreducibility over the Gaussian rationals.

Examples (19)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (5)

In[1]:= IrreduciblePolynomialQ[{x^2 - 1, x^2 - 2}]
Out[1]= {False, True}

In[2]:= IrreduciblePolynomialQ[{x^2 + 1, x^3 - 8}]
Out[2]= {True, False}

In[3]:= IrreduciblePolynomialQ[{x^4 - 4 y^2, x^4 - 2 y^2}]
Out[3]= {False, True}

In[4]:= IrreduciblePolynomialQ[x^2 + 2 I x - 1]
Out[4]= False

In[5]:= IrreduciblePolynomialQ[x^2 + 2 Sqrt[2] x + 2]
Out[5]= True

Options (8)

In[6]:= IrreduciblePolynomialQ[x^2 + 1, GaussianIntegers -> True]
Out[6]= False

In[7]:= IrreduciblePolynomialQ[x^2 + 2 Sqrt[2] x + 2, Extension -> Automatic]
Out[7]= False

In[8]:= IrreduciblePolynomialQ[{x^3 - 2, x^3 - 3}, Extension -> 2^(1/3)]
Out[8]= {False, True}

In[9]:= IrreduciblePolynomialQ[x^2 + 2, Extension -> {I, Sqrt[2]}]
Out[9]= False

In[10]:= IrreduciblePolynomialQ[{x^3 - 3, x^2 + 2 x y - 7}, Extension -> All]
Out[10]= {False, True}

In[11]:= IrreduciblePolynomialQ[{x^2 - 2 y^4, x^4 - 3 y^2}, Extension -> Sqrt[3]]
Out[11]= {True, False}

In[12]:= IrreduciblePolynomialQ[x^2 + y^2, GaussianIntegers -> True]
Out[12]= False

In[13]:= IrreduciblePolynomialQ[x^7 + 12 x y - 11, Extension -> All]
Out[13]= True

Applications (6)

In[14]:= IrreduciblePolynomialQ[x^2 + 1]
Out[14]= True

In[15]:= IrreduciblePolynomialQ[x^4 + 1]
Out[15]= True

In[16]:= IrreduciblePolynomialQ[x^4 + 1, Extension -> All]
Out[16]= False

In[17]:= IrreduciblePolynomialQ[x^2 + 1, GaussianIntegers -> True]
Out[17]= False

In[18]:= IrreduciblePolynomialQ[x^4 - 10 x^2 + 1]
Out[18]= True

In[19]:= IrreduciblePolynomialQ[x^4 - 10 x^2 + 1, Extension -> Sqrt[2]]
Out[19]= False

Options & behaviour

Multivariate inputs paired with an algebraic extension (Extension -> α, Extension -> All, or GaussianIntegers -> True) take a separate path: because the underlying Factor[poly, Extension -> α] only applies the extension to single-variable polynomials, a multivariate poly that reaches the no-extension fallback would otherwise look irreducible. To close that gap, IrreduciblePolynomialQ runs a Hilbert-irreducibility specialisation probe: pick the variable of maximum degree as the surviving univariate indeterminate, substitute every other variable with each c in {2, 3, 5}, factor the resulting univariate over the extension, and flip the verdict to False only when every valid specialisation produces >= 2 non-constant factors. Hilbert's theorem says an irreducible multivariate p stays irreducible under almost every integer specialisation, so unanimous "reducible" probes are strong evidence; the probe never downgrades a False from the cheap factor path (e.g. x*y).

Known limitations: - The specialisation probe is necessary but not sufficient: a reducible multivariate polynomial whose factors degenerate at every probed c can slip through and report True. This is rare in practice and only affects polynomials with a small set of "bad" specialisations. - Modulus -> p is not yet supported and is silently ignored.

Diagnostics: - IrreduciblePolynomialQ[] emits IrreduciblePolynomialQ::argx and stays unevaluated. - A trailing non-Rule past position 1 (e.g. IrreduciblePolynomialQ[1, 2, 3], or an unknown option name like IrreduciblePolynomialQ[x, Foo -> Bar]) emits IrreduciblePolynomialQ::nonopt and stays unevaluated.

Algorithm

irrpolyq.c -- IrreduciblePolynomialQ[poly, opts].

Always returns True or False on a structurally valid call. Wrong arg count emits IrreduciblePolynomialQ::argx and returns NULL. Malformed options emit IrreduciblePolynomialQ::nonopt and return NULL.

Algorithm:

  1. Resolve the factoring field from (GaussianIntegers, Extension)
     and a Complex-coefficient sniff of poly.  Precedence:
       Extension -> All           : absolute irreducibility (see below).
       Extension -> α | {α_i}     : Q(α) / compositum.
       Extension -> Automatic     : extension_autodetect on poly.
       GaussianIntegers -> True   : Q(i).
       complex coef in poly       : Q(i).
       otherwise                  : Q.

  2. Reject non-polynomial inputs (Sin[x], free symbol-only, ...).
     Pure constants (no polynomial variable) -> False (not irreducible).

  3. Factor poly using the resolved field, then count non-constant
     factors with multiplicity:
       0     -> False (constant)
       1     -> True
       >= 2  -> False

  Extension -> All:
    Univariate degree-1 polynomials are absolutely irreducible; everything
    else of degree >= 2 univariate splits into linear factors over C, so
    False.  For multivariate inputs, we approximate absolute irreducibility
    by factoring over Q(i) (catches conjugate-pair factorisations like
    x^2 + y^2 = (x+iy)(x-iy)).  This is incomplete -- it does not detect
    reducibility over Q(sqrt(d)) for d > 0 -- but covers the headline
    Wolfram examples and never produces a false "irreducible" for the
    Q(i) cases that motivate the option in practice.

  IrreduciblePolynomialQ is registered with ATTR_LISTABLE so List inputs
  thread element-wise via the evaluator before this builtin runs; the
  code here only ever sees a scalar first argument.

Implementation notes

Algorithm. builtin_irreduciblepolynomialq always returns True/False on a structurally valid call. It parses the GaussianIntegers and Extension options, resolves the factoring field by precedence (Extension -> All = absolute irreducibility; explicit α/{α_i} = Q(α)/compositum; Automatic = extension_autodetect; GaussianIntegers -> True or a complex coefficient = Q(i); else Q), then Factors the polynomial over that field and counts non-constant factors with multiplicity (irr_dispatch): 0 → False (constant), 1 → True, >= 2 → False. Extension -> All treats degree-1 univariate as absolutely irreducible and approximates the multivariate case by factoring over Q(i). For multivariate inputs that name an extension, a Hilbert-style specialisation probe (irr_multivariate_specialize_probe) can flip a True verdict to False (covering cases the cheap univariate-only extension path misses).

Data structures. Delegates to the polynomial factoring subsystem (facpoly/qafactor); options are read off Rule heads in the argument list. Wrong arity emits IrreduciblePolynomialQ::argx; malformed options emit ::nonopt (both return NULL). Registered Listable, so list inputs thread before this handler runs.

Complexity / limits. Dominated by the underlying Factor. The Extension -> All multivariate approximation is incomplete — it detects Q(i)-conjugate splits like x^2+y^2 but not reducibility over a general real quadratic field.

  • Listable, Protected. The evaluator threads any List first argument element-wise; the builtin itself sees only scalar polynomial inputs.
  • Always returns True or False on a structurally valid call. Constant numeric inputs (0, 1, 5, 2/3), non-polynomial expressions (Sin[x], Pi, Sqrt[x]), and the empty polynomial return False; constants are not irreducible polynomials.
  • Algorithm: factor poly over the resolved field, then count non-constant factors with multiplicity. The polynomial is irreducible iff exactly one non-constant factor (mult 1) appears in the factorisation. Numeric units (Integer, Rational, Complex leaves) and any sub-expression whose leaves are all free of the polynomial variables are treated as constants.
  • Extension dispatch:
  • Extension -> None (default): Factor[poly] over Q. Atomic algebraic constants in poly (Sqrt[int], Power[int, p/q]) are frozen to fresh placeholder symbols before factoring so Mathilda's multivariate Factor doesn't silently re-apply Extension -> Automatic -- matching Mathematica's "treat algebraic-number coefficients like independent variables" semantics.
  • Extension -> alpha: dispatches to the public Factor[poly, Extension -> alpha].
  • Extension -> {alpha_1, ...}: list-of-generators tower, same routing.
  • Extension -> Automatic: Factor[poly, Extension -> Automatic] -- Mathilda's own auto-detect.
  • Extension -> All (absolute irreducibility):
    • Univariate degree 1 -> True; degree >= 2 -> False (splits over C).
    • Multivariate -- best-effort -- factors over Q(i) to catch conjugate-pair factorisations like x^2 + y^2 = (x + i y)(x - i y).
  • Gaussian mode (GaussianIntegers -> True, or auto-on for Complex-bearing input) calls qa_factor_with_extension directly on a Complex[a, b] -> a + b I lifted form of poly so the qa-factoring path sees the imaginary unit as a free symbol rather than an opaque Complex literal. The lifted form is intentionally un-evaluated to avoid Mathilda's Times[b, I] -> Complex[0, b] canonicalisation undoing the lift.

Attributes: Listable, Protected.

References

See also: Complex, List, Pi, Rational, Rule

Notes & additional examples

Notes

IrreduciblePolynomialQ[poly] tests irreducibility over the rationals. Extension -> alpha (or a list) tests over the field extension generated by the given algebraic numbers; Extension -> Automatic adjoins every algebraic coefficient of poly; Extension -> All tests absolute irreducibility over the complex numbers; and GaussianIntegers -> True tests over the Gaussian rationals.