Skip to content

FactorSquareFree

Status: Stable

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

Description

FactorSquareFree[poly]

writes poly as a product of pairwise-coprime square-free factors, collecting repeated factors into powers.

Notes Computed via the Yun / Musser square-free decomposition using polynomial GCDs of poly with its derivative; cheaper than full Factor and sufficient when only multiplicities are needed.

Examples (7)

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

Basic examples (4)

In[1]:= FactorSquareFree[x^5 - x^3 - x^2 + 1]
Out[1]= (-1 + x)^2 (1 + 2 x + 2 x^2 + x^3)

In[2]:= FactorSquareFree[x^4 - 9x^3 + 29x^2 - 39x + 18]
Out[2]= (-3 + x)^2 (2 - 3 x + x^2)

In[3]:= FactorSquareFree[x^5 - x^3 y^2 - x^2 y^3 + y^5]
Out[3]= (x - y)^2 (x^3 + 2 x^2 y + 2 x y^2 + y^3)

In[4]:= FactorSquareFree[{(x^2 - 1)(x - 1), (x^4 - 1)(x^2 - 1)}]
Out[4]= {(1 + x) (-1 + x)^2, (1 + x^2) (-1 + x^2)^2}

Applications (3)

In[5]:= FactorSquareFree[x^5 - x^4 - x + 1]
Out[5]= (-1 + x)^2 (1 + x + x^2 + x^3)

In[6]:= FactorSquareFree[(x^2+1)^3 (x-1)^2]
Out[6]= (-1 + x)^2 (1 + x^2)^3

In[7]:= FactorSquareFree[x^8 + 4 x^6 + 6 x^4 + 4 x^2 + 1]
Out[7]= (1 + x^2)^4

Implementation notes

Algorithm. builtin_factorsquarefree (in src/poly/facpoly_squarefree.inc, compiled into facpoly.c) computes the square-free decomposition p = ∏ p_i^i with each p_i square-free and pairwise coprime, using Yun's algorithm. After a Rationalize/Numericalize round-trip for inexact inputs, the dispatcher factor_square_free_dispatcher expands and routes to factor_square_free_poly.

factor_square_free_poly works recursively on the variable list. It first extracts the polynomial content (poly_content) and recurses on it; on the primitive part pp it runs Yun's recurrence: set A = pp, B = gcd(A, A'), C = A/B, D = A'/B − C', then iterate P_i = gcd(C, D) (the degree-i square-free factor), C ← C/P_i, D ← D/P_i − (C/P_i)', accumulating P_i^i. Derivatives are computed by the local poly_deriv and GCDs by poly_gcd_internal; exact divisions by exact_poly_div. An F4 "cheap squarefree" pre-check (sqfree_cheap_check, a univariate-substitution probe) short-circuits the expensive gcd(pp, pp') when pp is provably square-free. A final exact_poly_div recovers any leading/missing scalar factor so the product round-trips to the input.

Data structures. Expr* polynomials manipulated through the generic evaluator (eval_and_free) and the poly helpers (get_degree_poly, poly_gcd_internal, exact_poly_div); factors collected in a growable Expr** buffer with their multiplicities encoded as Power[P_i, i].

Complexity / limits. Dominated by the GCD chain; the cheap pre-check avoids one full multivariate GCD on the common square-free case. Square-free decomposition is a prerequisite stage for full Factor.

  • Listable, Protected.
  • Automatically threads over lists, as well as equations, inequalities and logic functions.
  • Works on both univariate and multivariate polynomials.
  • Multivariate inputs use a cheap squarefree pre-check (F4 Stage 1): after content extraction in the main variable, sqfree_cheap_check substitutes integer values from {1, -1, 2, -2, 3, -3, 4} for the other variables and tests gcd(image, image') over Z[x]. If any image is squarefree at an alpha that preserves the leading-x degree, the pre-check proves pp is squarefree in x and the expensive multivariate gcd(pp, pp') is skipped. Soundness comes from content extraction guaranteeing any repeated factor of pp involves the main variable nontrivially. Measured 6.6× speedup on 4-variable squarefree inputs (6.27 s → 0.95 s); non-squarefree inputs fall through to the original Yun loop with negligible overhead.
  • The cheap pre-check's univariate gcd(image, image') runs through zupoly_gcd (subresultant PRS, GMP mpz_t coefficients). The previous implementation used poly_gcd_internal (Knuth-style primitive PRS at the Expr level) which suffers exponential coefficient growth on the intermediate pseudo-remainders; on a degree-31 univariate image (e.g. Factor[Expand[x^2 (z^13 - x^12)(z^4 + 3 x^9 - y^13)(17 - 5 y - z^14)]]) it ran for >120 s. Routing the same gcd through subresultant PRS keeps coefficient sizes polynomially bounded and runs in sub-millisecond time on the same input, bringing the full Factor call to under 1 s.

Attributes: Listable, Protected.

References

Notes & additional examples

Notes

FactorSquareFree groups a polynomial into pairwise-coprime square-free factors carrying their multiplicities, using the Yun / Musser decomposition (GCDs of the polynomial with its derivative). It does not split factors that are square-free but reducible: 1 + x + x^2 + x^3 is left intact in the first example even though it factors as (1+x)(1+x^2). The last example recognises (1 + x^2)^4 as a perfect fourth power without ever calling full Factor, which is the point — it is cheaper than factorisation when only multiplicities are needed.