# Why does PolynomialGCD not allow me to compute GCDs of polynomials expressed as functions?

Below is code that

1) Creates a function based on the solution to a recurrence. This function is the one I expect.

2) Prints, in order: the text $n$-kite for $n \in [4, \dots]$, two polynomials associated with the $n$-kite, and then the GCD of the two polynomials.

The polynomials associated with the $n$-kite are always correctly printed, but the GCD of the polynomials expressed as functions is inconsistent with the GCD I obtain by applying PolynomialGCD to the explicit polynomials.

In other words, if $f(x) = x^2 + 3x + 2$ and $g(x) = x^4+3x$, then PolynomialGCD[f, g] $\not =$ GCDPolynomial[x^2 + 3x + 2, x^4 + 3x]. I see this inconsistency take place in my code, and I am not sure how to resolve it.

Clear[a, d, f, n]

f[d_, n_] =
Simplify[a[n] /.
RSolve[{(a[n + 1] - a[n] d + a[n - 1]) == 2 - d,
a[1] == d^3 - 2 d + 1, a[0] == d^2}, a[n], n][[1]]];

For[i=1, i < 50, i++,
Print[Evaluate[i + 3] - kite];
Print[FullSimplify[f[d, i]]];
Print[Together[(-1)*f[d, i - 1] + 1 - d]];
Print["GCD: ", PolynomialGCD[f[d, i], Together[(-1)(f[d, i - 1]) + 1 - d]]]
]
\\ Output below for some kites


Why does GCDPolynomial give $\frac{1}{4}$ when applied to $1 + 3d - 4d^3 +d^5$ and $-1 -d +3d^2- d^4$. The result should really be $d^3 + d^2 - 2d - 1$.

• PolynomialGCD takes the input as it is provided, which in this case contains algebraic functions. To have it work on explicit polynomials, one could use Expand e.g. like this: tt = Table[PolynomialGCD @@ Expand[{f[d, i], -f[d, i - 1] + 1 - d}], {i, 50}]; – Daniel Lichtblau Aug 17 '17 at 16:05

I think PolynomialGCD is struggling with the form of the polynomials as they come out of f[d, n]. At the time of evaluation, there is very little simplification possible on the result of RSolve. Instead, the result should be simplified after a value for n is assigned. See e.g. the following modification (in which I have also converted the For loop into a Table, and removed Print).

ClearAll[a, d, f, n, i, sol]

sol = First@RSolve[{(a[n + 1] - a[n] d + a[n - 1]) == 2 - d,
a[1] == d^3 - 2 d + 1, a[0] == d^2}, a[n], n];
f[i_] := Simplify[a[n] /. sol /. n -> i]

Table[{
i + 3 - kite,
FullSimplify[f[i]],
Together[-f[i - 1] + 1 - d],
PolynomialGCD[f[i], -f[i - 1] + 1 - d]
}, {i, 3}
]

(* Out:
{{4 - kite, 1 - 2 d + d^3, 1 - d - d^2, -1 + d + d^2},
{5 - kite, 2 - 3 d^2 + d^4, d - d^3, -1 + d^2},
{6 - kite, 1 + 3 d - 4 d^3 + d^5, -1 - d + 3 d^2 - d^4, -1 - 2 d + d^2 + d^3}}
*)