musings about roots of expressions

[Chris Smith]

Given two expressions, `p` and `q`

p = x*y + x + y*z

q = p + z

it is easy to show that `q = (x + z)*(y + 1)`. But I'm wanting to avoid factoring but would like to know whether a solution for `x` from `p = 0` or `q = 0` is a factor or not. For `q`, the root `x = -z` represent a simple factor whereas the root of x = `-yz/(y + 1)` is different.

I'm lacking the vocabulary to differentiate `-z` from `-yz/(y + 1)`. Is it that the latter has a denominator while the former does not? (And since the original expression had no denominator then the `-z` represents a "whole" factor while the other root does not?)

As an alternative to factoring, it seems like collection and identification of similar subexpressions should allow a multivariate expression to be written in terms of un-factored factors, e.g. `collect(q, x) -> x*(y + 1) + y*z + z` and then use `factor_terms` on the non-x portion of the expression to find a matching factor of `y + 1` so the expression can be separated into two factors, one with `y` and one with `x` and `z`.  This works for less trivial expressions and can be done recursively something like this:

def sep(e):
  free = e.free_symbols
  if not free:return e
  x = next(ordered(free))
  c = collect(e.expand(),x)
  if not c.is_Add:return c
  i,d = c.as_independent(x)
  d = d.func(*[factor_terms(di) for di in d.args])
  i = factor_terms(i)
  ia, a = i.as_independent(Add, as_Add=False)
  if a==1:
      return e
  _a = sep(a)
  D = Dummy()
  return factor_terms(ia*D + d.xreplace({a:D})).subs(D, _a)

 eq
v**3*y*z**10 + 4*v**3*y*z**6 + 2*v**3*y*z**5 + 4*v**3*y*z**2 + 4*v**3*y*z + v**3*y + v**3*z**10 + 4*v**3*z**6 + 2*v**3*z**5 + 4*v**3*z**2 + 4*v**3*z + v**3 + 3*v**2*x*y*z**10 + 12*v**2*x*y*z**6 + 6*v**2*x*y*z**5 + 12*v**2*x*y*z**2 + 12*v**2*x*y*z + 3*v**2*x*y + 3*v**2*x*z**10 + 12*v**2*x*z**6 + 6*v**2*x*z**5 + 12*v**2*x*z**2 + 12*v**2*x*z + 3*v**2*x + 3*v*x**2*y*z**10 + 12*v*x**2*y*z**6 + 6*v*x**2*y*z**5 + 12*v*x**2*y*z**2 + 12*v*x**2*y*z + 3*v*x**2*y + 3*v*x**2*z**10 + 12*v*x**2*z**6 + 6*v*x**2*z**5 + 12*v*x**2*z**2 + 12*v*x**2*z + 3*v*x**2 + x**3*y*z**10 + 4*x**3*y*z**6 + 2*x**3*y*z**5 + 4*x**3*y*z**2 + 4*x**3*y*z + x**3*y + x**3*z**10 + 4*x**3*z**6 + 2*x**3*z**5 + 4*x**3*z**2 + 4*x**3*z + x**3
 sep(eq)
(y + 1)*(v**3 + 3*v**2*x + 3*v*x**2 + x**3)*(z**10 + 4*z**6 + 2*z**5 + 4*z**2 + 4*z + 1)
 eq == _.expand()
True

(It always seems like `factor` is faster than this but factor can be slow, too. And I don't really need the separated factors "factored" as much as I just need them separated.

So maybe that sort of function will answer the question...

Any thoughts would be appreciated as to what might be the best way to know when you have a solution that is a whole factors (not a rational factor -- or whatever it should be called.)

/c

[Chris Smith]

Note to self: distinguish between roots and factors. All polynomials have roots but not all roots correspond to factors, e.g.

roots of *unfactorable* `x**2 + 5*x + 1` are `[-5/2 - sqrt(21)/2, -5/2 + sqrt(21)/2]` -- notice that we left the integer domain and needed to express solutions in terms of radicals. Roots of `x**2+5*x+6` are integers `[-3, -2]` suggesting that the factors are `x + 3` and `x + 2`. All quadratics can be written as `a*(x - r1)*(x - r2)` but that does not mean that those are factors (lower order expressions which divide the original evenly).

see also https://byjus.com/maths/factoring-polynomials/

[Oscar Benjamin]

On Fri, 11 Mar 2022 at 23:13, Chris Smith <smi...@gmail.com> wrote:
>
> Given two expressions, `p` and `q`
>
> p = x*y + x + y*z
> q = p + z
>
> it is easy to show that `q = (x + z)*(y + 1)`. But I'm wanting to avoid factoring but would like to know whether a solution for `x` from `p = 0` or `q = 0` is a factor or not. For `q`, the root `x = -z` represent a simple factor whereas the root of x = `-yz/(y + 1)` is different.
>
> I'm lacking the vocabulary to differentiate `-z` from `-yz/(y + 1)`. Is it that the latter has a denominator while the former does not? (And since the original expression had no denominator then the `-z` represents a "whole" factor while the other root does not?)

The vocabulary I would use is to say that x + z is a polynomial factor
within the polynomial ring Z[x,y,z] (or Q[x,y,z]) whereas x-yz/(y+1)
is a polynomial factor in the polynomial ring Q(y, z)[x] which is the
ring of polynomials in x whose coefficients are rational functions of
y and z.

> As an alternative to factoring,

Why do you need an alternative to factoring?

It is possible to check if one polynomial is a factor of another
without computing a full factorisation. You can just polynomial
division:

In [18]: p = x*y + x + y*z

In [19]: q = p + z

In [20]: sx = solve(q, x)[0]

In [21]: sx
Out[21]: -z

In [22]: div(q, x - sx)
Out[22]: (y + 1, 0)

In [24]: rem(q, x - sx)
Out[24]: 0

Note the remainder 0.

--
Oscar

[Chris Smith]

> why do you need an alternative to factoring

I want to separate variables in an expression. It is not important the factors be factored since each factor will be solved for some variable (and, if polynomial, Poly will prefer the unfactored form). So I want the quickest method of finding those unfactored-but-separated-factors of an expression. My tests have shown that if an expression *can* be factored then the separation routine I am using (below) is, on average, about the same as factoring. When the expression cannot be separated the routine is about 3X faster. Times vary a lot, though, ranging from 2X to 20X faster.

def ift(e):
    """return a separation of variables without resorting to use
    of `factor`.
    Examples
    ========
    >>> from sympy.solvers.solvers import ift
    >>> from sympy.abc import a,b,c,d,e,f,g,x,y,z
    >>> ift(a*b*e + b**2*c*d*f/(-c*d + c*g) + b**2*c*f*g/(c*d - c*g))
    b*(a*e - b*f)
    >>> ift((z*(x + y)**2*(2*y + 4)**3).expand())
    8*z*(x**2 + 2*x*y + y**2)*(y**3 + 6*y**2 + 12*y + 8)
    """
    try:from sympy.simplify import bottom_up

    except:from sympy.core.traversal import bottom_up
    from sympy.simplify.simplify import signsimp
    def do(e):
        free = e.free_symbols
        if not free or not e.args:
            return e
        e = collect(e, free.pop())
        if e.is_Mul:
            return e.func(*[do(i) for i in e.args])
        if not e.is_Add:
            return e
        i, d = e.as_independent(Add)
        if not d:
            return e
        return factor_terms(i) + d
    n, d = [factor_terms(bottom_up(i, do)) for i in e.as_numer_denom()]
    return factor_terms(signsimp(n/d))

[Chris Smith]

Cancellation of terms will cause that routine trouble.