show/hide this revision's text 3 fixed grammar

Here's an idea (not a solution), which I thought I would post before heading out for coffee inspiration.

Let $f(x)=\sum_{i=1}^n p_i(x)$ be the expression we are attempting to simplify. One possible approach is to ask which $p_i$ can be the last polynomial of the simplification. To answer this, we can first use the $O(nlog(n))$ algorithm to compute the factorization of $f$. Say $f(x)=(ax+b)(cx+d)$. Then, the only possible choices for the last polynomial are the $p_i$'s that are divisible by $(ax+b)$ or $(cx+d)$. If we are lucky, there might only be one such choice, say $p_k$. We can then replace $f$ by $f-p_k$ and recurse. This approach will certainly work in the case that there is a unique ordering of simplification.

show/hide this revision's text 2 edited body

Here's an idea (not a solution), which I thought I would post before heading out for coffee inspiration.

Let $f(x)=\sum_{i=1}^n p_i(x)$ be the expression we are attempting to simplify. One possible approach is to ask which $p_i$ can be the last polynomial of the simplification. To answer this, we can first use the $O(nlog(n))$ algorithm to compute the factorization of $f$. Say $f(x)=(ax+b)(cx+d)$. Then, the only possible choices for the last polynomial are the $p_i$'s that are divisible by $(ax+b)$ or $(cx+b)$. (cx+d)$. If we lucky, there might only be one such choice, say $p_k$. We can then replace $f$ by $f-p_k$ and recurse. This approach will certainly work in the case that there is a unique ordering of simplification.

show/hide this revision's text 1

Here's an idea (not a solution), which I thought I would post before heading out for coffee inspiration.

Let $f(x)=\sum_{i=1}^n p_i(x)$ be the expression we are attempting to simplify. One possible approach is to ask which $p_i$ can be the last polynomial of the simplification. To answer this, we can first use the $O(nlog(n))$ algorithm to compute the factorization of $f$. Say $f(x)=(ax+b)(cx+d)$. Then, the only possible choices for the last polynomial are the $p_i$'s that are divisible by $(ax+b)$ or $(cx+b)$. If we lucky, there might only be one such choice, say $p_k$. We can then replace $f$ by $f-p_k$ and recurse. This approach will certainly work in the case that there is a unique ordering of simplification.