Decompose a rational function over its denominator's factors, not only its roots (#919)

[Rafael-SOWNet]

Closes #919.

A partial fraction decomposition split N/D at a rational root of D, which was all the decomposition there was. A denominator that factors over ℚ with no rational root anywhere in it was left whole and its integral came back unevaluated — even where every factor was one the integrator already reads.

"1/(x^4 + 3x^2 + 2)".Integrate("x")

was  integral(1 / (x ^ 4 + 3 * x ^ 2 + 2), x)
is   arctan(x) - sqrt(2) * arctan(sqrt(2) * x / 2) / 2 + C

x^4 + 3x^2 + 2 is (x^2 + 1)(x^2 + 2), and the rule for a linear numerator over a quadratic answers both halves. Nothing was missing but the split. #918 supplied the factorisation over ℚ that makes it available, so this is the second consumer of the polynomial layer after the equation solver.

What it does

The same shape as the step at a root: one irreducible factor with its multiplicity against the product of the rest, U*A + V*B = 1 from the extended Euclidean algorithm in ℚ[x], and N/(A*B) = N*V/A + N*U/B with each numerator reduced modulo its own denominator. Both sides are strictly smaller problems of the same kind, so the integrator recurses and reaches the full decomposition whichever factor is peeled first.

The extended Euclid did not exist — there was one over 𝔽ₚ inside the factoriser and IntegerPolynomial.Gcd over ℤ without the cofactors — so RationalPolynomial is new: dense, lowest power first, coefficients in lowest terms as they are written.

No condition is attached, and that is a statement rather than an omission. A and B being coprime, A*B vanishes exactly where one of them does, so the two sides are undefined at the same points. A decomposition loses a singularity when it cancels a shared factor; this cancels nothing. The identity is checked — overA*B + overB*A against the numerator, over ℚ — rather than trusted, so what survives a failure is a refusal and never a wrong antiderivative.

The guard, which is the part with a measurement behind it

The decomposition is produced only where every factor is a shape an integration rule reads: linear at any multiplicity, quadratic at the first, nothing else. That costs no answer — a piece with no rule leaves the whole integral unevaluated either way — and it is what keeps declining cheap.

Deciding it by trying instead was measured and is much worse. (1 - x^4)/(1 + x^4 + x^8), whose factorisation holds the irreducible quartic x^4 - x^2 + 1, took 18s to return the same unevaluated integral it returns in 203ms, because every half of every split is a fresh problem the whole integrator then searches. intbench caught this before the guard existed: four problems crossed the 3s budget and one previously-answered problem went with them.

What is still declined

x^2/(x^4 + 1) — irreducible over ℚ, and only factors once real coefficients are allowed — and 1/(x^4 + 2x^2 + 1), the power of a single irreducible. The ladder that would decompose the second is deliberately not built: every term it produces is over (x^2 + c)^k, which nothing reads, so it would end in the same unevaluated integral it started from.

One test changed rather than added to

ADenominatorWithNoRationalRootIsStillDeclined pinned 1/(x^4 + 4) as out of reach on the grounds that it has no rational root. It is reducible over ℚ — (x^2 - 2x + 2)(x^2 + 2x + 2) — and is now answered, so the boundary that test records has moved to what does not factor over ℚ at all. BREAKING-CHANGES.md carries the entry.

Measured

On this branch against a stock build of master, same machine.

unit suite	6960 passed, 0 failed
F# wrapper	130/130
casbench	116/119, 0 wrong, 0 error, 0 timeout — equal to master
propcheck	1340 checks, 0 failures
rootcheck	596/596 clean
simpsweep	10463/10463 agree
crashcheck	1652 cases, 0 crashed, 0 unexpected throws
intbench families=0	46/191 → 47/191 solved, 0 wrong, 6 timeout either side
intbench families=1	30/228 both, and identical to master problem by problem

Every antiderivative in the new tests is checked by differentiating it back and comparing to the integrand numerically, never against a written form.

🤖 Generated with Claude Code