help links subscribe changes refresh edit

	NoncommutativePolynomials
NonCommutativeLaurentPolynomials ←	↑	→ XDistributedPolynomial

SandboxFactoringNoncommutativePolynomials

Edit detail for SandboxFactoringNoncommutativePolynomials revision 1 of 14

	1 2 3 4 5 6 7 8 9 10 11 12 13 14
Editor: Bill Page Time: 2018/07/04 15:16:25 GMT+0
Note: ansatz of Daniel Smertnig as implemented by Konrad Schrempf

changed:
-
Konrad Schrempf <math@versibilitas.at> 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

\begin{axiom}

--)read nc_ini03
ALPHABET := ['x, 'y, 'z];
OVL ==> OrderedVariableList(ALPHABET)
OFM ==> FreeMonoid(OVL)
F ==> Fraction(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

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

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

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

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

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)
  lst_eqn
\end{axiom}

\begin{axiom}
p0 := factorizationEquations(x::XDP)
solve(p0)
\end{axiom}

shows that x is irreducible ;-).

\begin{axiom}
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]])
\end{axiom}

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

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

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)
  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 G739 with type Integer -> Boolean

$\label{eq1}\left[{{a_{1}}\ {b_{1}}}\right]$

(1)

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

fricas

solve(p0)

$\label{eq2}\left[{\left[{{a_{1}}= 0}\right]}, \:{\left[{{b_{1}}= 0}\right]}\right]$

(2)

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

shows that x is irreducible ;-).

fricas

p1 := x::XDP * y::XDP

$\label{eq3}x \ y$

(3)

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

fricas

l1 := leftSubwords(p1)

$\label{eq4}\left[{a_{1}}, \:{{a_{2}}\ x}\right]$

(4)

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

fricas

r1 := rightSubwords(p1)

$\label{eq5}\left[{b_{1}}, \:{{b_{2}}\ y}\right]$

(5)

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

fricas

pe1 := factorizationPolynomial(p1)

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

(6)

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

fricas

fe1 := factorizationEquations(p1)

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

(7)

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

fricas

ve1 := members set concat map(variables,fe1)

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

(8)

Type: List(Symbol)

fricas

s1 := solve(concat [fe1,[ve1.2-1]])

$\label{eq9}\left[{\left[{{b_{1}}= 0}, \:{{a_{1}}= 0}, \:{{b_{2}}= 1}, \:{{a_{2}}= 1}\right]}\right]$

(9)

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

fricas

p1 := (x::XDP+1)^2

$\label{eq10}1 +{2 \ x}+{{x}^{2}}$

(10)

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

fricas

pe1 := factorizationPolynomial(p1)

$\label{eq11}{{a_{1}}\ {b_{1}}}+{{\left({{a_{1}}\ {b_{2}}}+{{a_{2}}\ {b_{1}}}\right)}\ x}+{{a_{2}}\ {b_{2}}\ {{x}^{2}}}$

(11)

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

fricas

fe1 := factorizationEquations(p1)

$\label{eq12}\left[{{{a_{1}}\ {b_{1}}}- 1}, \:{{{a_{1}}\ {b_{2}}}+{{a_{2}}\ {b_{1}}}- 2}, \:{{{a_{2}}\ {b_{2}}}- 1}\right]$

(12)

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

fricas

ve1 := members set concat map(variables,fe1)

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

(13)

Type: List(Symbol)

fricas

solve(concat [fe1,[ve1.1-1]])

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

(14)

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

fricas

solve(factorizationEquations((x::XDP+y::XDP)^2))

   >> Error detected within library code:
   system does not have a finite number of solutions

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