Edit detail for SandboxFactoringNoncommutativePolynomials revision 14 of 14

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

--)read nc_ini03

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

OVL ==> OrderedVariableList(ALPHABET)

OFM ==> FreeMonoid(OVL)

F ==> Integer

G ==> Fraction(Polynomial(Integer))

XDP ==> XDPOLY(OVL, F)

YDP ==> XDPOLY(OVL, G)

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

y := 'y::OFM;

z := 'z::OFM;

OF ==> OutputForm

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.

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.

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.

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.

Helper functions

Lift XDP over integers to YDP over rational functions and back

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.

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.

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

Example 0:

p0 := factorizationEquations(x::XDP)

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

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

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

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

Compiling function G742 with type Integer -> Boolean

(1)

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:

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

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

(2)

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

(3)

e1 := factorizationEquations(p_1)

(4)

concat(vars l1, rest vars r1)

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

(5)

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

(6)

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

(7)

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

(8)

fl1*fr1

(9)

Example 2:

p_2 : XDP := x*y

(10)

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

(11)

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

(12)

e2 := factorizationEquations(p_2)

(13)

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

(14)

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

(15)

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

(16)

fl2*fr2

(17)

Example 3:

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

(18)

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

(19)

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

(20)

e3 := factorizationEquations(p_3)

(21)

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

(22)

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

(23)

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

(24)

fl3*fr3

(25)

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.

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

Example 4:

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

(26)

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

(27)

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

(28)

e4 := factorizationEquations(p_4)

(29)

groebnerFactorize e4

(30)

e4a := last %

(31)

param(e4a)

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

(32)

)set output tex off
 

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

)set output tex on
 

)set output algebra off

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

(33)

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

(34)

fl4*fr4

(35)

test(mapPoly p_4 = fl4*fr4)

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

(36)

Example 5:

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

(37)

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

(38)

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

(39)

e5 := factorizationEquations(p_5)

(40)

)set output tex off
 

)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

s5

   (63)
   [
                                              1         1
     [a  = 0, a  = 0, a   = 0, a   = 0, a  = --, a   = --, a  = 0, a   = 0,
       6       7       12       13       5   b    11   b    4       10
                                              3         3
      a  = 0, a  = 0, a  = 0, a  = 0, a  = 0, b   = 0, b   = 0, b  = 0,
       3       9       2       8       1       12       13       6
      b   = 0, b  = 0, b   = 0, b  = 0, b  = 0, b  = b , b  = 0, b  = 0,
       11       5       10       4       9       8    3   7       2
      b  = 0]
       1
     ]

)set output tex on
 

)set output algebra off

fl5:=map((x:G):G+->eval(x,s5.1),l5)

(41)

fr5:=map((x:G):G+->eval(x,s5.1),r5)

(42)

fl5*fr5

(43)

test(mapPoly p_5 = fl5*fr5)

(44)

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.

p_6 : XDP := 2 - x^2

(45)

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

(46)

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

(47)

e6 := factorizationEquations(p_6)

(48)

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

s6

(49)

Test for irreducibility.

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

(50)

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"

(51)