help links subscribe changes refresh edit

	NoncommutativePolynomials
NonCommutativeLaurentPolynomials ←	↑	→ XDistributedPolynomial

SandboxFactoringNoncommutativePolynomials

Edit detail for SandboxFactoringNoncommutativePolynomials revision 14 of 14

	1 2 3 4 5 6 7 8 9 10 11 12 13 14
Editor: Bill Page Time: 2018/07/09 21:46:12 GMT+0
Note: test for irreducibility

changed:
-We need the solution of the factorization equations to associate a unique value with each variable. If the result includes any implicit solutions, i.e. equations whose righthand side is not just a symbol then 'solve' was not able to find a full solution. In this case the expression is irreducible over the base domain.
We need the solution of the factorization equations to associate a unique value with each variable. If the result includes any implicit solutions, i.e. equations whose lefthand side is not just a symbol then 'solve' was not able to find a full solution. In this case the expression is irreducible over the base domain.

Konrad Schrempf wrote:

  Date: Wed, Jul 4, 2018 at 5:45 AM
  Subject: Factorization in XDPOLY ...

Since I never tried the ansatz (of Daniel Smertnig) and I needed something to warm up again (for programming in FriCAS) I did it now ...

Factorization of non-commutative polynomials

in the free associative algebra XDPOLY using an ansatz

Idea: Daniel Smertnig, January 26, 2017

Test: Konrad Schrempf, Mit 2018-07-04 10:33

Definitions

fricas

(1) -> --)read nc_ini03

ALPHABET := ['x, 'y, 'z];

Type: List(OrderedVariableList([x,y,z]))

fricas

OVL ==> OrderedVariableList(ALPHABET)

Type: Void

fricas

OFM ==> FreeMonoid(OVL)

Type: Void

fricas

F ==> Integer

Type: Void

fricas

G ==> Fraction(Polynomial(Integer))

Type: Void

fricas

XDP ==> XDPOLY(OVL, F)

Type: Void

fricas

YDP ==> XDPOLY(OVL, G)

Type: Void

fricas

--NCP ==> NCPOLY(OVL, F)
x := 'x::OFM;

Type: FreeMonoid(OrderedVariableList([x,y,z]))

fricas

y := 'y::OFM;

Type: FreeMonoid(OrderedVariableList([x,y,z]))

fricas

z := 'z::OFM;

Type: FreeMonoid(OrderedVariableList([x,y,z]))

fricas

OF ==> OutputForm

Type: Void

fricas

leftSubwords(p:XDP) : List(YDP) ==
  lst_wrd : List(OFM) := []
  for mon in support(p) repeat
    wrd := 1$OFM
    for fct in factors(mon) repeat
      for i in 1 .. fct.exp repeat
        pos := position(wrd, lst_wrd)::NNI
        if zero?(pos) then
          lst_wrd := cons(wrd, lst_wrd)
        wrd := wrd*(fct.gen)::OFM
  lst_pol : List(YDP) := []
  cnt_pol := #lst_wrd
  for wrd in lst_wrd repeat
    sym_tmp := (a[cnt_pol])::Symbol
    lst_pol := cons(sym_tmp*wrd::YDP, lst_pol)
    cnt_pol := (cnt_pol-1)::NNI
  lst_pol

   Function declaration leftSubwords : XDistributedPolynomial(
      OrderedVariableList([x,y,z]),Integer) -> List(
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(
      Polynomial(Integer)))) has been added to workspace.

Type: Void

fricas

rightSubwords(p:XDP) : List(YDP) ==
  lst_wrd : List(OFM) := []
  for mon in support(p) repeat
    wrd := 1$OFM
    for fct in reverse(factors(mon)) repeat
      for i in 1 .. fct.exp repeat
        pos := position(wrd, lst_wrd)::NNI
        if zero?(pos) then
          lst_wrd := cons(wrd, lst_wrd)
        wrd := (fct.gen)::OFM*wrd
  lst_pol : List(YDP) := []
  cnt_pol := #lst_wrd
  for wrd in lst_wrd repeat
    sym_tmp := (b[cnt_pol])::Symbol
    lst_pol := cons(sym_tmp*wrd::YDP, lst_pol)
    cnt_pol := (cnt_pol-1)::NNI
  lst_pol

   Function declaration rightSubwords : XDistributedPolynomial(
      OrderedVariableList([x,y,z]),Integer) -> List(
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(
      Polynomial(Integer)))) has been added to workspace.

Type: Void

fricas

factorizationPolynomial(p:XDP) : YDP ==
  lsw := leftSubwords(p)
  rsw := rightSubwords(p)
  fp := 0$YDP
  for lw in lsw repeat
    for rw in rsw repeat
      fp := fp + lw*rw
  fp

   Function declaration factorizationPolynomial : 
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Integer) -> 
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(
      Polynomial(Integer))) has been added to workspace.

Type: Void

fricas

factorizationEquations(p:XDP) : List(G) ==
  lst_eqn : List(G) := []
  fp := factorizationPolynomial(p)
  for mon in support(fp) repeat
    c_1 := coefficient(p, mon)
    c_2 := coefficient(fp, mon)
    lst_eqn := cons(c_2-c_1::G, lst_eqn)
  for mon in support(p) repeat
    if zero?(coefficient(fp, mon)) then
      lst_eqn := []
      break
  lst_eqn

   Function declaration factorizationEquations : XDistributedPolynomial
      (OrderedVariableList([x,y,z]),Integer) -> List(Fraction(
      Polynomial(Integer))) has been added to workspace.

Type: Void

Helper functions

Lift XDP over integers to YDP over rational functions and back

fricas

mapPoly(p:XDP):YDP ==
  if reductum p = 0 then
    return leadingCoefficient(p)*leadingSupport(p)
  else
    return mapPoly(reductum p)+leadingCoefficient(p)*leadingSupport(p)

   Function declaration mapPoly : XDistributedPolynomial(
      OrderedVariableList([x,y,z]),Integer) -> XDistributedPolynomial(
      OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer))) has 
      been added to workspace.

Type: Void

fricas

mapPoly2XDP(p:YDP):XDP ==
  if reductum p = 0 then
    return retract(leadingCoefficient(p))*leadingSupport(p)
  else
    return mapPoly2XDP(reductum p)+retract(leadingCoefficient(p))*leadingSupport(p)

   Function declaration mapPoly2XDP : XDistributedPolynomial(
      OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer))) -> 
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Integer) has 
      been added to workspace.

Type: Void

fricas

vars(p)==concat map(variables,coefficients(p))

Type: Void

Example 0:

fricas

p0 := factorizationEquations(x::XDP)

fricas

Compiling function leftSubwords with type XDistributedPolynomial(
      OrderedVariableList([x,y,z]),Integer) -> List(
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(
      Polynomial(Integer))))

fricas

Compiling function rightSubwords with type XDistributedPolynomial(
      OrderedVariableList([x,y,z]),Integer) -> List(
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(
      Polynomial(Integer))))

fricas

Compiling function factorizationPolynomial with type 
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Integer) -> 
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(
      Polynomial(Integer)))

fricas

Compiling function factorizationEquations with type 
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Integer) -> 
      List(Fraction(Polynomial(Integer)))

fricas

Compiling function G69 with type Integer -> Boolean

$\label{eq1}\left[ \right]$

(1)

Type: List(Fraction(Polynomial(Integer)))

fricas

solve(p0)

   >> Error detected within library code:
   No identity element for reduce of empty list using operation
   setUnion

shows that x is irreducible ;-).

Well for non-trivial polynomials solve does not work. One could try Groebner- Shirshov bases, etc.

In principle it should work with general base rings, for example the integers. But I do not know the capabilities of solve. Anyway, I hope that it could be useful within XDPOLY (at least for small polynomials, because the number of non-linear equations is increasing exponentially).

The file in the attachment is meant to put on github for discussions.

https://github.com/billpage/ncpoly

Example 1:

fricas

p_1 : XDP := x*(1-y*x);

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Integer)

fricas

l1 := reduce(+,leftSubwords(p_1))

$\label{eq2}{a_{1}}+{{a_{2}}\ x}+{{a_{3}}\ x \ y}$

(2)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

r1 := reduce(+,rightSubwords(p_1))

$\label{eq3}{b_{1}}+{{b_{2}}\ x}+{{b_{3}}\ y \ x}$

(3)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

e1 := factorizationEquations(p_1)

$\label{eq4}\begin{array}{@{}l} \displaystyle \left[{{a_{1}}\ {b_{1}}}, \:{{{a_{1}}\ {b_{2}}}+{{a_{2}}\ {b_{1}}}- 1}, \:{{a_{1}}\ {b_{3}}}, \:{{a_{3}}\ {b_{1}}}, \:{{a_{2}}\ {b_{2}}}, \: \right. \ \ \displaystyle \left.{{{a_{2}}\ {b_{3}}}+{{a_{3}}\ {b_{2}}}+ 1}, \:{{a_{3}}\ {b_{3}}}\right]$

(4)

Type: List(Fraction(Polynomial(Integer)))

fricas

concat(vars l1, rest vars r1)

fricas

Compiling function vars with type XDistributedPolynomial(
      OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer))) -> 
      List(Symbol)

$\label{eq5}\left[{a_{3}}, \:{a_{2}}, \:{a_{1}}, \:{b_{2}}, \:{b_{1}}\right]$

(5)

Type: List(Symbol)

fricas

s1:=solve(e1,concat(vars l1, rest vars r1))

$\label{eq6}\left[{\left[{{a_{3}}= 0}, \:{{a_{2}}= -{\frac{1}{b_{3}}}}, \:{{a_{1}}= 0}, \:{{b_{2}}= 0}, \:{{b_{1}}= -{b_{3}}}\right]}\right]$

(6)

Type: List(List(Equation(Fraction(Polynomial(Integer)))))

fricas

fl1:=map((x:G):G+->eval(x,s1.1),l1)

$\label{eq7}-{{\frac{1}{b_{3}}}\ x}$

(7)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

fr1:=map((x:G):G+->eval(x,s1.1),r1)

$\label{eq8}-{b_{3}}+{{b_{3}}\ y \ x}$

(8)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

fl1*fr1

$\label{eq9}x -{x \ y \ x}$

(9)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

Example 2:

fricas

p_2 : XDP := x*y

$\label{eq10}x \ y$

(10)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Integer)

fricas

l2 := reduce(+,leftSubwords(p_2))

$\label{eq11}{a_{1}}+{{a_{2}}\ x}$

(11)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

r2 := reduce(+,rightSubwords(p_2))

$\label{eq12}{b_{1}}+{{b_{2}}\ y}$

(12)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

e2 := factorizationEquations(p_2)

$\label{eq13}\left[{{a_{1}}\ {b_{1}}}, \:{{a_{1}}\ {b_{2}}}, \:{{a_{2}}\ {b_{1}}}, \:{{{a_{2}}\ {b_{2}}}- 1}\right]$

(13)

Type: List(Fraction(Polynomial(Integer)))

fricas

s2:=solve(e2,concat(vars l2, rest vars r2))

$\label{eq14}\left[{\left[{{a_{2}}={\frac{1}{b_{2}}}}, \:{{a_{1}}= 0}, \:{{b_{1}}= 0}\right]}\right]$

(14)

Type: List(List(Equation(Fraction(Polynomial(Integer)))))

fricas

fl2:=map((x:G):G+->eval(x,s2.1),l2)

$\label{eq15}{\frac{1}{b_{2}}}\ x$

(15)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

fr2:=map((x:G):G+->eval(x,s2.1),r2)

$\label{eq16}{b_{2}}\ y$

(16)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

fl2*fr2

$\label{eq17}x \ y$

(17)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

Example 3:

fricas

p_3 : XDP := (x-y)*(x+y)

$\label{eq18}-{{y}^{2}}-{y \ x}+{x \ y}+{{x}^{2}}$

(18)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Integer)

fricas

l3 := reduce(+,leftSubwords(p_3))

$\label{eq19}{a_{1}}+{{a_{3}}\ y}+{{a_{2}}\ x}$

(19)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

r3 := reduce(+,rightSubwords(p_3))

$\label{eq20}{b_{1}}+{{b_{3}}\ y}+{{b_{2}}\ x}$

(20)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

e3 := factorizationEquations(p_3)

$\label{eq21}\begin{array}{@{}l} \displaystyle \left[{{a_{1}}\ {b_{1}}}, \:{{{a_{1}}\ {b_{3}}}+{{a_{3}}\ {b_{1}}}}, \:{{{a_{1}}\ {b_{2}}}+{{a_{2}}\ {b_{1}}}}, \:{{{a_{3}}\ {b_{3}}}+ 1}, \:{{{a_{3}}\ {b_{2}}}+ 1}, \: \right. \ \ \displaystyle \left.{{{a_{2}}\ {b_{3}}}- 1}, \:{{{a_{2}}\ {b_{2}}}- 1}\right]$

(21)

Type: List(Fraction(Polynomial(Integer)))

fricas

s3:=solve(e3,concat(vars l3, rest vars r3))

$\label{eq22}\left[{\left[{{a_{2}}={\frac{1}{b_{2}}}}, \:{{a_{3}}= -{\frac{1}{b_{2}}}}, \:{{a_{1}}= 0}, \:{{b_{3}}={b_{2}}}, \:{{b_{1}}= 0}\right]}\right]$

(22)

Type: List(List(Equation(Fraction(Polynomial(Integer)))))

fricas

fl3:=map((x:G):G+->eval(x,s3.1),l3)

$\label{eq23}-{{\frac{1}{b_{2}}}\ y}+{{\frac{1}{b_{2}}}\ x}$

(23)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

fr3:=map((x:G):G+->eval(x,s3.1),r3)

$\label{eq24}{{b_{2}}\ y}+{{b_{2}}\ x}$

(24)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

fl3*fr3

$\label{eq25}-{{y}^{2}}-{y \ x}+{x \ y}+{{x}^{2}}$

(25)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

In order to obtain a solution we must choose (to omit) one variable that is necessarily not 0 since it is going to appear in the denominator of a coefficient in the result.

Although this solution might be a bit "heavy" [groebnerFactorize]? expresses the solution as a union of ideals. In each ideal those variables that are necessarily zero will appear as bases containing only one variable. The remaining variables are "significant" and we can choose any of these as parameters.

fricas

param(e) == first variables first remove((x:G):Boolean+->#variables(x)<2, e)

Type: Void

Example 4:

fricas

p_4 : XDP := (x-y^2)*(x+z^2)

$\label{eq26}{{x}^{2}}-{{{y}^{2}}\ x}+{x \ {{z}^{2}}}-{{{y}^{2}}\ {{z}^{2}}}$

(26)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Integer)

fricas

l4 := reduce(+,leftSubwords(p_4))

$\label{eq27}{a_{1}}+{{a_{2}}\ y}+{{a_{5}}\ x}+{{a_{3}}\ {{y}^{2}}}+{{a_{6}}\ x \ z}+{{a_{4}}\ {{y}^{2}}\ z}$

(27)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

r4 := reduce(+,rightSubwords(p_4))

$\label{eq28}{b_{1}}+{{b_{2}}\ z}+{{b_{5}}\ x}+{{b_{3}}\ {{z}^{2}}}+{{b_{6}}\ y \ x}+{{b_{4}}\ y \ {{z}^{2}}}$

(28)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

e4 := factorizationEquations(p_4)

$\label{eq29}\begin{array}{@{}l} \displaystyle \left[{{a_{1}}\ {b_{1}}}, \:{{a_{1}}\ {b_{2}}}, \:{{a_{2}}\ {b_{1}}}, \:{{{a_{1}}\ {b_{5}}}+{{a_{5}}\ {b_{1}}}}, \:{{a_{1}}\ {b_{3}}}, \:{{a_{2}}\ {b_{2}}}, \:{{a_{3}}\ {b_{1}}}, \: \right. \ \ \displaystyle \left.{{{a_{1}}\ {b_{6}}}+{{a_{2}}\ {b_{5}}}}, \:{{{a_{5}}\ {b_{2}}}+{{a_{6}}\ {b_{1}}}}, \:{{{a_{5}}\ {b_{5}}}- 1}, \:{{{a_{1}}\ {b_{4}}}+{{a_{2}}\ {b_{3}}}}, \: \right. \ \ \displaystyle \left.{{{a_{3}}\ {b_{2}}}+{{a_{4}}\ {b_{1}}}}, \:{{{a_{2}}\ {b_{6}}}+{{a_{3}}\ {b_{5}}}+ 1}, \:{{{a_{5}}\ {b_{3}}}+{{a_{6}}\ {b_{2}}}- 1}, \:{{a_{6}}\ {b_{5}}}, \: \right. \ \ \displaystyle \left.{{a_{5}}\ {b_{6}}}, \:{{{a_{2}}\ {b_{4}}}+{{a_{3}}\ {b_{3}}}+{{a_{4}}\ {b_{2}}}+ 1}, \:{{a_{4}}\ {b_{5}}}, \:{{a_{3}}\ {b_{6}}}, \:{{a_{6}}\ {b_{3}}}, \:{{a_{6}}\ {b_{6}}}, \: \right. \ \ \displaystyle \left.{{a_{5}}\ {b_{4}}}, \:{{a_{4}}\ {b_{3}}}, \:{{a_{4}}\ {b_{6}}}, \:{{a_{3}}\ {b_{4}}}, \:{{a_{6}}\ {b_{4}}}, \:{{a_{4}}\ {b_{4}}}\right]$

(29)

Type: List(Fraction(Polynomial(Integer)))

fricas

groebnerFactorize e4

$\label{eq30}\left[{\left[ 1 \right]}, \:{\left[{b_{6}}, \:{{b_{5}}-{b_{3}}}, \:{b_{4}}, \:{{{a_{3}}\ {b_{3}}}+ 1}, \:{b_{2}}, \:{b_{1}}, \:{a_{6}}, \:{{a_{5}}+{a_{3}}}, \:{a_{4}}, \:{a_{2}}, \:{a_{1}}\right]}\right]$

(30)

Type: List(List(Polynomial(Integer)))

fricas

e4a := last %

$\label{eq31}\left[{b_{6}}, \:{{b_{5}}-{b_{3}}}, \:{b_{4}}, \:{{{a_{3}}\ {b_{3}}}+ 1}, \:{b_{2}}, \:{b_{1}}, \:{a_{6}}, \:{{a_{5}}+{a_{3}}}, \:{a_{4}}, \:{a_{2}}, \:{a_{1}}\right]$

(31)

Type: List(Polynomial(Integer))

fricas

param(e4a)

fricas

Compiling function param with type List(Polynomial(Integer)) -> 
      Symbol

$\label{eq32}b_{5}$

(32)

Type: Symbol

fricas

)set output tex off

fricas

)set output algebra on

--s4:=solve(e4,concat(vars l4, rest vars r4))
s4:=solve(e4a,remove(param(e4a), concat(vars l4,vars r4)) )

   (53)
   [
                              1        1
     [a  = 0, a  = 0, a  = - --, a  = --, a  = 0, a  = 0, b  = 0, b  = 0,
       4       6       3     b    5   b    2       1       4       6
                              5        5
      b  = b , b  = 0, b  = 0]
       3    5   2       1
     ]

Type: List(List(Equation(Fraction(Polynomial(Integer)))))

fricas

)set output tex on

fricas

)set output algebra off

fl4:=map((x:G):G+->eval(x,s4.1),l4)

$\label{eq33}{{\frac{1}{b_{5}}}\ x}-{{\frac{1}{b_{5}}}\ {{y}^{2}}}$

(33)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

fr4:=map((x:G):G+->eval(x,s4.1),r4)

$\label{eq34}{{b_{5}}\ x}+{{b_{5}}\ {{z}^{2}}}$

(34)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

fl4*fr4

$\label{eq35}{{x}^{2}}-{{{y}^{2}}\ x}+{x \ {{z}^{2}}}-{{{y}^{2}}\ {{z}^{2}}}$

(35)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

test(mapPoly p_4 = fl4*fr4)

fricas

Compiling function mapPoly with type XDistributedPolynomial(
      OrderedVariableList([x,y,z]),Integer) -> XDistributedPolynomial(
      OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

$\label{eq36} \mbox{\rm true}$

(36)

Type: Boolean

Example 5:

fricas

p_5 : XDP := (x*y*z+y*x*z)*(z*x*y+z*y*x)

$\label{eq37}{y \ x \ {{z}^{2}}\ y \ x}+{y \ x \ {{z}^{2}}\ x \ y}+{x \ y \ {{z}^{2}}\ y \ x}+{x \ y \ {{z}^{2}}\ x \ y}$

(37)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Integer)

fricas

l5 := reduce(+,leftSubwords(p_5))

$\label{eq38}\begin{array}{@{}l} \displaystyle {a_{1}}+{{a_{8}}\ y}+{{a_{2}}\ x}+{{a_{9}}\ y \ x}+{{a_{3}}\ x \ y}+{{a_{10}}\ y \ x \ z}+{{a_{4}}\ x \ y \ z}+ \ \ \displaystyle {{a_{11}}\ y \ x \ {{z}^{2}}}+{{a_{5}}\ x \ y \ {{z}^{2}}}+{{a_{13}}\ y \ x \ {{z}^{2}}\ y}+{{a_{12}}\ y \ x \ {{z}^{2}}\ x}+ \ \ \displaystyle {{a_{7}}\ x \ y \ {{z}^{2}}\ y}+{{a_{6}}\ x \ y \ {{z}^{2}}\ x}$

(38)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

r5 := reduce(+,rightSubwords(p_5))

$\label{eq39}\begin{array}{@{}l} \displaystyle {b_{1}}+{{b_{2}}\ y}+{{b_{7}}\ x}+{{b_{8}}\ y \ x}+{{b_{3}}\ x \ y}+{{b_{9}}\ z \ y \ x}+{{b_{4}}\ z \ x \ y}+ \ \ \displaystyle {{b_{10}}\ {{z}^{2}}\ y \ x}+{{b_{5}}\ {{z}^{2}}\ x \ y}+{{b_{11}}\ y \ {{z}^{2}}\ y \ x}+{{b_{6}}\ y \ {{z}^{2}}\ x \ y}+ \ \ \displaystyle {{b_{13}}\ x \ {{z}^{2}}\ y \ x}+{{b_{12}}\ x \ {{z}^{2}}\ x \ y}$

(39)

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

e5 := factorizationEquations(p_5)

$\label{eq40}\begin{array}{@{}l} \displaystyle \left[{{a_{1}}\ {b_{1}}}, \:{{{a_{1}}\ {b_{2}}}+{{a_{8}}\ {b_{1}}}}, \:{{{a_{1}}\ {b_{7}}}+{{a_{2}}\ {b_{1}}}}, \:{{a_{8}}\ {b_{2}}}, \: \right. \ \ \displaystyle \left.{{{a_{1}}\ {b_{8}}}+{{a_{8}}\ {b_{7}}}+{{a_{9}}\ {b_{1}}}}, \:{{{a_{1}}\ {b_{3}}}+{{a_{2}}\ {b_{2}}}+{{a_{3}}\ {b_{1}}}}, \:{{a_{2}}\ {b_{7}}}, \:{{a_{1}}\ {b_{9}}}, \: \right. \ \ \displaystyle \left.{{a_{1}}\ {b_{4}}}, \:{{a_{8}}\ {b_{8}}}, \:{{a_{10}}\ {b_{1}}}, \:{{{a_{8}}\ {b_{3}}}+{{a_{9}}\ {b_{2}}}}, \:{{a_{9}}\ {b_{7}}}, \:{{a_{4}}\ {b_{1}}}, \:{{a_{3}}\ {b_{2}}}, \: \right. \ \ \displaystyle \left.{{{a_{2}}\ {b_{8}}}+{{a_{3}}\ {b_{7}}}}, \:{{a_{2}}\ {b_{3}}}, \:{{a_{1}}\ {b_{10}}}, \:{{a_{1}}\ {b_{5}}}, \:{{a_{8}}\ {b_{9}}}, \:{{a_{8}}\ {b_{4}}}, \:{{a_{11}}\ {b_{1}}}, \: \right. \ \ \displaystyle \left.{{a_{10}}\ {b_{2}}}, \:{{a_{10}}\ {b_{7}}}, \:{{a_{9}}\ {b_{8}}}, \:{{a_{9}}\ {b_{3}}}, \:{{a_{2}}\ {b_{9}}}, \:{{a_{2}}\ {b_{4}}}, \:{{a_{5}}\ {b_{1}}}, \:{{a_{4}}\ {b_{2}}}, \:{{a_{4}}\ {b_{7}}}, \: \right. \ \ \displaystyle \left.{{a_{3}}\ {b_{8}}}, \:{{a_{3}}\ {b_{3}}}, \:{{{a_{1}}\ {b_{11}}}+{{a_{8}}\ {b_{10}}}}, \:{{{a_{1}}\ {b_{6}}}+{{a_{8}}\ {b_{5}}}}, \:{{{a_{11}}\ {b_{2}}}+{{a_{13}}\ {b_{1}}}}, \right. \ \ \displaystyle \left.\:{{{a_{11}}\ {b_{7}}}+{{a_{12}}\ {b_{1}}}}, \:{{{a_{9}}\ {b_{9}}}+{{a_{10}}\ {b_{8}}}}, \:{{{a_{9}}\ {b_{4}}}+{{a_{10}}\ {b_{3}}}}, \: \right. \ \ \displaystyle \left.{{{a_{1}}\ {b_{13}}}+{{a_{2}}\ {b_{10}}}}, \:{{{a_{1}}\ {b_{12}}}+{{a_{2}}\ {b_{5}}}}, \:{{{a_{5}}\ {b_{2}}}+{{a_{7}}\ {b_{1}}}}, \:{{{a_{5}}\ {b_{7}}}+{{a_{6}}\ {b_{1}}}}, \right. \ \ \displaystyle \left.\:{{{a_{3}}\ {b_{9}}}+{{a_{4}}\ {b_{8}}}}, \:{{{a_{3}}\ {b_{4}}}+{{a_{4}}\ {b_{3}}}}, \:{{a_{8}}\ {b_{11}}}, \:{{a_{8}}\ {b_{6}}}, \:{{a_{13}}\ {b_{2}}}, \: \right. \ \ \displaystyle \left.{{{a_{8}}\ {b_{13}}}+{{a_{9}}\ {b_{10}}}+{{a_{10}}\ {b_{9}}}+{{a_{11}}\ {b_{8}}}+{{a_{13}}\ {b_{7}}}- 1}, \: \right. \ \ \displaystyle \left.{{{a_{8}}\ {b_{12}}}+{{a_{9}}\ {b_{5}}}+{{a_{10}}\ {b_{4}}}+{{a_{11}}\ {b_{3}}}+{{a_{12}}\ {b_{2}}}- 1}, \:{{a_{12}}\ {b_{7}}}, \:{{a_{7}}\ {b_{2}}}, \right. \ \ \displaystyle \left.\:{{{a_{2}}\ {b_{11}}}+{{a_{3}}\ {b_{10}}}+{{a_{4}}\ {b_{9}}}+{{a_{5}}\ {b_{8}}}+{{a_{7}}\ {b_{7}}}- 1}, \: \right. \ \ \displaystyle \left.{{{a_{2}}\ {b_{6}}}+{{a_{3}}\ {b_{5}}}+{{a_{4}}\ {b_{4}}}+{{a_{5}}\ {b_{3}}}+{{a_{6}}\ {b_{2}}}- 1}, \:{{a_{6}}\ {b_{7}}}, \:{{a_{2}}\ {b_{13}}}, \: \right. \ \ \displaystyle \left.{{a_{2}}\ {b_{12}}}, \:{{{a_{10}}\ {b_{10}}}+{{a_{11}}\ {b_{9}}}}, \:{{{a_{10}}\ {b_{5}}}+{{a_{11}}\ {b_{4}}}}, \:{{a_{1 3}}\ {b_{8}}}, \:{{a_{13}}\ {b_{3}}}, \: \right. \ \ \displaystyle \left.{{a_{12}}\ {b_{8}}}, \:{{a_{12}}\ {b_{3}}}, \:{{a_{9}}\ {b_{11}}}, \:{{a_{9}}\ {b_{6}}}, \:{{a_{9}}\ {b_{13}}}, \:{{a_{9}}\ {b_{12}}}, \:{{{a_{4}}\ {b_{10}}}+{{a_{5}}\ {b_{9}}}}, \: \right. \ \ \displaystyle \left.{{{a_{4}}\ {b_{5}}}+{{a_{5}}\ {b_{4}}}}, \:{{a_{7}}\ {b_{8}}}, \:{{a_{7}}\ {b_{3}}}, \:{{a_{6}}\ {b_{8}}}, \:{{a_{6}}\ {b_{3}}}, \:{{a_{3}}\ {b_{11}}}, \:{{a_{3}}\ {b_{6}}}, \: \right. \ \ \displaystyle \left.{{a_{3}}\ {b_{13}}}, \:{{a_{3}}\ {b_{12}}}, \:{{a_{11}}\ {b_{10}}}, \:{{a_{11}}\ {b_{5}}}, \:{{a_{13}}\ {b_{9}}}, \:{{a_{1 3}}\ {b_{4}}}, \:{{a_{12}}\ {b_{9}}}, \: \right. \ \ \displaystyle \left.{{a_{12}}\ {b_{4}}}, \:{{a_{10}}\ {b_{11}}}, \:{{a_{10}}\ {b_{6}}}, \:{{a_{10}}\ {b_{13}}}, \:{{a_{10}}\ {b_{12}}}, \:{{a_{5}}\ {b_{10}}}, \:{{a_{5}}\ {b_{5}}}, \: \right. \ \ \displaystyle \left.{{a_{7}}\ {b_{9}}}, \:{{a_{7}}\ {b_{4}}}, \:{{a_{6}}\ {b_{9}}}, \:{{a_{6}}\ {b_{4}}}, \:{{a_{4}}\ {b_{11}}}, \:{{a_{4}}\ {b_{6}}}, \:{{a_{4}}\ {b_{13}}}, \:{{a_{4}}\ {b_{12}}}, \: \right. \ \ \displaystyle \left.{{{a_{11}}\ {b_{11}}}+{{a_{13}}\ {b_{10}}}}, \:{{{a_{11}}\ {b_{6}}}+{{a_{13}}\ {b_{5}}}}, \:{{{a_{11}}\ {b_{13}}}+{{a_{12}}\ {b_{10}}}}, \: \right. \ \ \displaystyle \left.{{{a_{11}}\ {b_{12}}}+{{a_{12}}\ {b_{5}}}}, \:{{{a_{5}}\ {b_{11}}}+{{a_{7}}\ {b_{10}}}}, \:{{{a_{5}}\ {b_{6}}}+{{a_{7}}\ {b_{5}}}}, \: \right. \ \ \displaystyle \left.{{{a_{5}}\ {b_{13}}}+{{a_{6}}\ {b_{10}}}}, \:{{{a_{5}}\ {b_{12}}}+{{a_{6}}\ {b_{5}}}}, \:{{a_{13}}\ {b_{11}}}, \:{{a_{13}}\ {b_{6}}}, \:{{a_{13}}\ {b_{13}}}, \: \right. \ \ \displaystyle \left.{{a_{13}}\ {b_{12}}}, \:{{a_{12}}\ {b_{11}}}, \:{{a_{12}}\ {b_{6}}}, \:{{a_{12}}\ {b_{13}}}, \:{{a_{12}}\ {b_{12}}}, \:{{a_{7}}\ {b_{11}}}, \:{{a_{7}}\ {b_{6}}}, \: \right. \ \ \displaystyle \left.{{a_{7}}\ {b_{13}}}, \:{{a_{7}}\ {b_{12}}}, \:{{a_{6}}\ {b_{11}}}, \:{{a_{6}}\ {b_{6}}}, \:{{a_{6}}\ {b_{13}}}, \:{{a_{6}}\ {b_{12}}}\right]$

(40)

Type: List(Fraction(Polynomial(Integer)))

fricas

)set output tex off

fricas

)set output algebra on

-- look for a solution
for i in 1..#coefficients r5 repeat
  s5 := solve(e5,concat(vars l5, remove(b[i],vars r5)))
  #s5.1>0 => break

   >> Error detected within library code:
   index out of range

Example 6:

We need the solution of the factorization equations to associate a unique value with each variable. If the result includes any implicit solutions, i.e. equations whose lefthand side is not just a symbol then solve was not able to find a full solution. In this case the expression is irreducible over the base domain.

fricas

p_6 : XDP := 2 - x^2

              2
   (62)  2 - x

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Integer)

fricas

l6 := reduce(+,leftSubwords(p_6))

   (63)  a  + a x
          1    2

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

r6 := reduce(+,rightSubwords(p_6))

   (64)  b  + b x
          1    2

Type: XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))

fricas

e6 := factorizationEquations(p_6)

   (65)  [a b  - 2, a b  + a b , a b  + 1]
           1 1       1 2    2 1   2 2

Type: List(Fraction(Polynomial(Integer)))

fricas

-- look for a solution
for i in 1..#coefficients r6 repeat
  s6 := solve(e6,concat(vars l6, remove(b[i],vars r6)))
  #s6.1>0 => break

Type: Void

fricas

s6

                  2 b
                     2        2      2     2
   (67)  [[a  = - ----, a  = --, 2 b   - b   = 0]]
            2        2   1   b      2     1
                   b          1
                    1

Type: List(List(Equation(Fraction(Polynomial(Integer)))))

Test for irreducibility.

fricas

map(x+->retractIfCan(lhs x)@Union(Symbol,"failed") case Symbol, s6.1)

   (68)  [true, true, false]

Type: List(Boolean)

fricas

if reduce(_and, %) then
    fl6:=map((x:G):G+->eval(x,s6.1),l6)
    fr6:=map((x:G):G+->eval(x,s6.1),r6)
    fl6*fr6
    test(mapPoly p_6 = fl6*fr6)
  else
    "irreducible"::"irreducible"

   (69)  "irreducible"

Type: irreducible