No common terms between polynomials: an efficient check?

Question

The "common term" would be in standard form, but the two input multivariate polynomials needn't be, e.g $x(1+y)+y$ and $y(x+a+b)$ have one common term, $xy$.

A brute force solution would be to expand both polynomials to standard form, then check for common terms. e.g. $x+xy+y$, $xy+ay+ab$.

Is there a better way?

EDIT if it makes it easier, we can loosen "same term" to allow different coefficients, so that e.g. $2xy$ and $3xy$ count as the "same term". (there must be a more mathy way to say that)... so, perhaps it becomes like a single component in Fourier analysis?

Maybe, a specific term could be identified by differentiating its factors by their power number of times to eliminate it (e.g. $x^2y^3$, differentiate by $x$ twice and by $y$ three times). Though, seems inefficient, and unclear how to extend that to checking all terms apart from brute force.

---

BTW "no common terms" is the opposite of "all terms in common" (in a sense), i.e checking for identical polynomials. This does have an efficient algorithm, using the Schwartz-Zippel lemma (see Is there an efficient algorithm for expression equivalence?).

Answer 1

Here is an approach that might occasionally be a bit better in practice, but is still exponential-time in the worst case, so it is not a satisfying answer to your question. Suppose we want to determine whether the polynomials $f(x,y,\dots),g(x,y,\dots)$ have a common term. First write

$$\begin{align*} f(x,y,\dots) &= f_0(y,\dots) + x f_1(y,\dots)\\ g(x,y,\dots) &= g_0(y,\dots) + x g_1(y,\dots). \end{align*}$$

Then recursively check whether $f_0,g_0$ have a common term; and check whether $f_1,g_1$ have a common term.

To express $f$ in that format, note that

$$f_0(y,\dots) = f(0,y,\dots)$$

so it suffices to plug in $x=0$ into the expression for $f$ to get an expression for $f_0$. Try to simplify that expression as much as possible using standard rules for simplifying polynomials. Then, you can write

$$f_1(y,\dots) = (f(x,y,\dots) - f_0(y,\dots))/x.$$

Simplify that expression as much as possible.

If no simplification is done, the running time is exponential in $n$, the number of variables. We obtain a recurrence of the form $T(n) = 2 T(n-1) + O(1)$, so the worst-case running time is exponential. The room for hope is that if simplification is done at each stage, it's possible that for some inputs this might be faster than that. In general it will still be exponential-time in the worst case, though, so I don't know whether this will actually be any better in practice.