help links subscribe changes refresh edit

	NoncommutativePolynomials
NonCommutativeLaurentPolynomials ←	↑	→ XDistributedPolynomial

SandboxFactoringNoncommutativePolynomials

Edit detail for SandboxFactoringNoncommutativePolynomials revision 5 of 14

	1 2 3 4 5 6 7 8 9 10 11 12 13 14
Editor: Bill Page Time: 2018/07/07 01:52:27 GMT+0
Note: factors

added:
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:

changed:
-fl:=map((x:G):G+->eval(x,s1.1),l1)
-fr:=map((x:G):G+->eval(x,s1.1),r1)
-fl*fr 
fl1:=map((x:G):G+->eval(x,s1.1),l1)
fr1:=map((x:G):G+->eval(x,s1.1),r1)
fl1*fr1 

changed:
-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 num-
-ber 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 2:
\begin{axiom}
p_2 : XDP := x*y
l2 := reduce(+,leftSubwords(p_2))
r2 := reduce(+,rightSubwords(p_2))
e2 := factorizationEquations(p_2)
concat(vars l2, rest vars r2)
s2:=solve(e1,concat(vars l2, rest vars r2))
fl2:=map((x:G):G+->eval(x,s2.1),l2)
fr2:=map((x:G):G+->eval(x,s2.1),r2)
fl2*fr2 
\end{axiom}

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

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

concat(vars l2, rest vars r2)

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

(15)

Type: List(Symbol)

fricas

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

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

(16)

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

fricas

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

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

(17)

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

fricas

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

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

(18)

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

fricas

fl2*fr2

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

(19)

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