login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

Edit detail for SandboxFactoringNoncommutativePolynomials revision 8 of 14

1 2 3 4 5 6 7 8 9 10 11 12 13 14
Editor: Bill Page
Time: 2018/07/07 14:17:24 GMT+0
Note: mapPoly

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


removed:
-)set output tex off
-)set output algebra on

added:
)set output tex off
)set output algebra on

added:
)set output tex on
)set output algebra off

added:
test(mapPoly p_4 = fl4*fr4)

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

fricas
--)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
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
p_1 : XDP := x*(1-y*x);
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Integer)
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

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 G744 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

\label{eq2}x -{x \  y \  x}(2)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Integer)
fricas
l1 := reduce(+,leftSubwords(p_1))

\label{eq3}{a_{1}}+{{a_{2}}\  x}+{{a_{3}}\  x \  y}(3)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
r1 := reduce(+,rightSubwords(p_1))

\label{eq4}{b_{1}}+{{b_{2}}\  x}+{{b_{3}}\  y \  x}(4)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
e1 := factorizationEquations(p_1)

\label{eq5}\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] 
(5)
Type: List(Fraction(Polynomial(Integer)))
fricas
vars(p)==concat map(variables,coefficients(p))
Type: Void
fricas
concat(vars l1, rest vars r1)
fricas
Compiling function vars with type XDistributedPolynomial(
      OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer))) -> 
      List(Symbol)

\label{eq6}\left[{a_{3}}, \:{a_{2}}, \:{a_{1}}, \:{b_{2}}, \:{b_{1}}\right](6)
Type: List(Symbol)
fricas
s1:=solve(e1,concat(vars l1, rest vars r1))

\label{eq7}\left[{\left[{{a_{3}}= 0}, \:{{a_{2}}= -{1 \over{b_{3}}}}, \:{{a_{1}}= 0}, \:{{b_{2}}= 0}, \:{{b_{1}}= -{b_{3}}}\right]}\right](7)
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fl1:=map((x:G):G+->eval(x,s1.1),l1)

\label{eq8}-{{1 \over{b_{3}}}\  x}(8)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fr1:=map((x:G):G+->eval(x,s1.1),r1)

\label{eq9}-{b_{3}}+{{b_{3}}\  y \  x}(9)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fl1*fr1

\label{eq10}x -{x \  y \  x}(10)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))

Example 2:

fricas
p_2 : XDP := x*y

\label{eq11}x \  y(11)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Integer)
fricas
l2 := reduce(+,leftSubwords(p_2))

\label{eq12}{a_{1}}+{{a_{2}}\  x}(12)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
r2 := reduce(+,rightSubwords(p_2))

\label{eq13}{b_{1}}+{{b_{2}}\  y}(13)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
e2 := factorizationEquations(p_2)

\label{eq14}\left[{{a_{1}}\ {b_{1}}}, \:{{a_{1}}\ {b_{2}}}, \:{{a_{2}}\ {b_{1}}}, \:{{{a_{2}}\ {b_{2}}}- 1}\right](14)
Type: List(Fraction(Polynomial(Integer)))
fricas
s2:=solve(e2,concat(vars l2, rest vars r2))

\label{eq15}\left[{\left[{{a_{2}}={1 \over{b_{2}}}}, \:{{a_{1}}= 0}, \:{{b_{1}}= 0}\right]}\right](15)
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fl2:=map((x:G):G+->eval(x,s2.1),l2)

\label{eq16}{1 \over{b_{2}}}\  x(16)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fr2:=map((x:G):G+->eval(x,s2.1),r2)

\label{eq17}{b_{2}}\  y(17)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fl2*fr2

\label{eq18}x \  y(18)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))

Example 3:

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

\label{eq19}-{{y}^{2}}-{y \  x}+{x \  y}+{{x}^{2}}(19)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Integer)
fricas
l3 := reduce(+,leftSubwords(p_3))

\label{eq20}{a_{1}}+{{a_{3}}\  y}+{{a_{2}}\  x}(20)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
r3 := reduce(+,rightSubwords(p_3))

\label{eq21}{b_{1}}+{{b_{3}}\  y}+{{b_{2}}\  x}(21)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
e3 := factorizationEquations(p_3)

\label{eq22}\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] (22)
Type: List(Fraction(Polynomial(Integer)))
fricas
s3:=solve(e3,concat(vars l3, rest vars r3))

\label{eq23}\left[{\left[{{a_{2}}={1 \over{b_{2}}}}, \:{{a_{3}}= -{1 \over{b_{2}}}}, \:{{a_{1}}= 0}, \:{{b_{3}}={b_{2}}}, \:{{b_{1}}= 0}\right]}\right](23)
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fl3:=map((x:G):G+->eval(x,s3.1),l3)

\label{eq24}-{{1 \over{b_{2}}}\  y}+{{1 \over{b_{2}}}\  x}(24)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fr3:=map((x:G):G+->eval(x,s3.1),r3)

\label{eq25}{{b_{2}}\  y}+{{b_{2}}\  x}(25)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fl3*fr3

\label{eq26}-{{y}^{2}}-{y \  x}+{x \  y}+{{x}^{2}}(26)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))

Example 4:

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 - in this case b[3].

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

\label{eq27}{{x}^{2}}-{{{y}^{2}}\  x}+{x \ {{z}^{2}}}-{{{y}^{2}}\ {{z}^{2}}}(27)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Integer)
fricas
l4 := reduce(+,leftSubwords(p_4))

\label{eq28}{a_{1}}+{{a_{2}}\  y}+{{a_{5}}\  x}+{{a_{3}}\ {{y}^{2}}}+{{a_{6}}\  x \  z}+{{a_{4}}\ {{y}^{2}}\  z}(28)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
r4 := reduce(+,rightSubwords(p_4))

\label{eq29}{b_{1}}+{{b_{2}}\  z}+{{b_{5}}\  x}+{{b_{3}}\ {{z}^{2}}}+{{b_{6}}\  y \  x}+{{b_{4}}\  y \ {{z}^{2}}}(29)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
e4 := factorizationEquations(p_4)

\label{eq30}\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] 
(30)
Type: List(Fraction(Polynomial(Integer)))
fricas
)set output tex off
 
fricas
)set output algebra on
--s4:=solve(e4,concat(vars l4, rest vars r4)) s4:=solve(e4,concat(vars l4, [b[1],b[2],b[4],b[5],b[6]]))
(49) [ 1 1 [a = 0, a = 0, a = - --, a = --, a = 0, a = 0, b = 0, b = 0, 4 6 3 b 5 b 2 1 1 2 3 3 b = 0, b = b , b = 0] 4 5 3 6 ]
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{eq31}{{1 \over{b_{3}}}\  x}-{{1 \over{b_{3}}}\ {{y}^{2}}}(31)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fr4:=map((x:G):G+->eval(x,s4.1),r4)

\label{eq32}{{b_{3}}\  x}+{{b_{3}}\ {{z}^{2}}}(32)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fl4*fr4

\label{eq33}{{x}^{2}}-{{{y}^{2}}\  x}+{x \ {{z}^{2}}}-{{{y}^{2}}\ {{z}^{2}}}(33)
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{eq34} \mbox{\rm true} (34)
Type: Boolean