help links subscribe changes refresh edit

	NoncommutativePolynomials
NonCommutativeLaurentPolynomials ←	↑	→ XDistributedPolynomial

SandboxFactoringNoncommutativePolynomials

Edit detail for SandboxFactoringNoncommutativePolynomials revision 9 of 14

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

added:

Definitions

removed:
-

changed:
-
-mapPoly(p:XDP):YDP ==
-  if reductum p = 0 then
-    return leadingCoefficient(p)*leadingSupport(p)
-  else
-    return mapPoly(reductum p)+leadingCoefficient(p)*leadingSupport(p)
-
-p_1 : XDP := x*(1-y*x);
-
\end{axiom}


\begin{axiom}

added:
Helper functions

Lift XDP over integers to YDP over rational functions
\begin{axiom}
mapPoly(p:XDP):YDP ==
  if reductum p = 0 then
    return leadingCoefficient(p)*leadingSupport(p)
  else
    return mapPoly(reductum p)+leadingCoefficient(p)*leadingSupport(p)

vars(p)==concat map(variables,coefficients(p))
\end{axiom}

Example 0:

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

removed:
-vars(p)==concat map(variables,coefficients(p))

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

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

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

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 G740 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}}= -{1 \over{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}-{{1 \over{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}}={1 \over{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}{1 \over{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}}={1 \over{b_{2}}}}, \:{{a_{3}}= -{1 \over{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}-{{1 \over{b_{2}}}\ y}+{{1 \over{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)))

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

)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]]))

   (48)
   [
                              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{eq30}{{1 \over{b_{3}}}\ x}-{{1 \over{b_{3}}}\ {{y}^{2}}}$

(30)

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

fricas

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

$\label{eq31}{{b_{3}}\ x}+{{b_{3}}\ {{z}^{2}}}$

(31)

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

fricas

fl4*fr4

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

(32)

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{eq33} \mbox{\rm true}$

(33)

Type: Boolean