What happens
PolynomialGcd.Gcd returns null — declines — on inputs that are well within every documented limit, because an intermediate of the subresultant remainder sequence exceeds MultivariatePolynomial.MaxTerms (512) even though neither input nor answer comes close.
Minimal reproduction, four variables a, b, c, d:
left = (b + c + 1) * (a + b) * (a + b + c + d) 19 terms
right = (a^2 + b*c + d) * (a + b + c + d) * (a + b + c + d) 29 terms
a + b + c + d divides both — confirmed with DivideExact — and Gcd answers null.
Traced to PseudoRemainder, where divisorLead.Multiply(remainder) returns null three steps in, with a 25-term leading coefficient multiplied by a 159-term remainder. The maximum per-variable degree there is 14, so MaxTerms is the only ceiling that can have fired.
Rate: 7 of 3000 randomly drawn triples in the sweep added by #918 (12 of 6000 in a wider exploratory run). Pinned there as a refusal, in TheTermCeilingIsReachedByAnIntermediate, with the sweep asserting the refusal count stays at or below 7.
Why the class remark does not cover this
The <remarks> on PolynomialGcd explains that the subresultant sequence is what stops the coefficients exploding, citing Knuth's degree-8 example reaching ~10^35. That argument is about coefficient size and it holds. It says nothing about monomial count, which is what fires here: the subresultant divisions bound how big the numbers get, not how many terms a multivariate intermediate has.
Severity
Not a wrong answer. Gcd declines and TryCancel then leaves the quotient alone, so the caller gets an uncancelled fraction rather than a bad one — the right failure mode. 3000 committed plus 6000 exploratory randomised triples produced only refusals, never an incorrect divisor. It is a completeness gap.
What a fix has to weigh
- Raising
MaxTerms is one line and needs a performance measurement, not a guess: PolynomialGcd.TryCancel runs on every quotient the simplifier constructs, and the type is shared with Functions/Algebra/Groebner, where the term counts are much larger and the ceiling is load-bearing.
- A separate, larger ceiling for intermediates than for inputs may be the better shape, since the input bound is what protects the hot path.
- Alternatively a modular (Zippel / Brown) GCD would avoid the intermediate swell entirely rather than budgeting for it, which is the standard answer and a much bigger change.
Found while putting the multivariate GCD under test for #746 item 43; see #918.
What happens
PolynomialGcd.Gcdreturnsnull— declines — on inputs that are well within every documented limit, because an intermediate of the subresultant remainder sequence exceedsMultivariatePolynomial.MaxTerms(512) even though neither input nor answer comes close.Minimal reproduction, four variables
a, b, c, d:a + b + c + ddivides both — confirmed withDivideExact— andGcdanswersnull.Traced to
PseudoRemainder, wheredivisorLead.Multiply(remainder)returnsnullthree steps in, with a 25-term leading coefficient multiplied by a 159-term remainder. The maximum per-variable degree there is 14, soMaxTermsis the only ceiling that can have fired.Rate: 7 of 3000 randomly drawn triples in the sweep added by #918 (12 of 6000 in a wider exploratory run). Pinned there as a refusal, in
TheTermCeilingIsReachedByAnIntermediate, with the sweep asserting the refusal count stays at or below 7.Why the class remark does not cover this
The
<remarks>onPolynomialGcdexplains that the subresultant sequence is what stops the coefficients exploding, citing Knuth's degree-8 example reaching ~10^35. That argument is about coefficient size and it holds. It says nothing about monomial count, which is what fires here: the subresultant divisions bound how big the numbers get, not how many terms a multivariate intermediate has.Severity
Not a wrong answer.
Gcddeclines andTryCancelthen leaves the quotient alone, so the caller gets an uncancelled fraction rather than a bad one — the right failure mode. 3000 committed plus 6000 exploratory randomised triples produced only refusals, never an incorrect divisor. It is a completeness gap.What a fix has to weigh
MaxTermsis one line and needs a performance measurement, not a guess:PolynomialGcd.TryCancelruns on every quotient the simplifier constructs, and the type is shared withFunctions/Algebra/Groebner, where the term counts are much larger and the ceiling is load-bearing.Found while putting the multivariate GCD under test for #746 item 43; see #918.