help links subscribe changes refresh edit

	NoncommutativePolynomials
NonCommutativeLaurentPolynomials ←	↑	→ XDistributedPolynomial

SandboxFactoringNoncommutativePolynomials

Edit detail for SandboxFactoringNoncommutativePolynomials revision 3 of 14

	1 2 3 4 5 6 7 8 9 10 11 12 13 14
Editor: Bill Page Time: 2018/07/06 15:00:13 GMT+0
Note: solve

changed:
-p1 := x::XDP * y::XDP
-l1 := leftSubwords(p1)
-r1 := rightSubwords(p1)
-pe1 := factorizationPolynomial(p1)
-fe1 := factorizationEquations(p1)
-ve1 := members set concat map(variables,fe1)
-s1 := solve(concat [fe1,[ve1.2-1]])
l1 := reduce(+,leftSubwords(p_1))
r1 := reduce(+,rightSubwords(p_1))
e1 := factorizationEquations(p_1)
vars(p)==concat map(variables,coefficients(p))
concat(vars l1, rest vars r1)
solve(e1,concat(vars l1, rest vars r1))

removed:
-
-\begin{axiom}
-p1 := (x::XDP+1)^2
-pe1 := factorizationPolynomial(p1)
-fe1 := factorizationEquations(p1)
-ve1 := members set concat map(variables,fe1)
-solve(concat [fe1,[ve1.1-1]])
-\end{axiom}
-
-\begin{axiom}
-solve(factorizationEquations((x::XDP+y::XDP)^2))
-\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 ==> Fraction(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]),Fraction(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]),Fraction(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]),Fraction(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]),Fraction(
      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]),Fraction(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]),Fraction(Integer)) -> List(
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(
      Polynomial(Integer))))

fricas

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

fricas

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

fricas

Compiling function factorizationEquations with type 
      XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(
      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 ;-).

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

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{eq5}\left[{a_{3}}, \:{a_{2}}, \:{a_{1}}, \:{b_{2}}, \:{b_{1}}\right]$

(5)

Type: List(Symbol)

fricas

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

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