login  home  contents  what's new  discussion  bug reports help  links  subscribe  changes  refresh  edit

# Edit detail for SandboxFactoringNoncommutativePolynomials revision 6 of 14

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

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

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
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
 (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
 (2)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Integer)
fricas
l1 := reduce(+,leftSubwords(p_1))
 (3)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
r1 := reduce(+,rightSubwords(p_1))
 (4)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
e1 := factorizationEquations(p_1)
 (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)
 (6)
Type: List(Symbol)
fricas
s1:=solve(e1,concat(vars l1, rest vars r1))
 (7)
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fl1:=map((x:G):G+->eval(x,s1.1),l1)
 (8)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fr1:=map((x:G):G+->eval(x,s1.1),r1)
 (9)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fl1*fr1
 (10)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))

Example 2:

fricas
p_2 : XDP := x*y
 (11)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Integer)
fricas
l2 := reduce(+,leftSubwords(p_2))
 (12)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
r2 := reduce(+,rightSubwords(p_2))
 (13)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
e2 := factorizationEquations(p_2)
 (14)
Type: List(Fraction(Polynomial(Integer)))
fricas
concat(vars l2, rest vars r2)
 (15)
Type: List(Symbol)
fricas
s2:=solve(e2,concat(vars l2, rest vars r2))
 (16)
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fl2:=map((x:G):G+->eval(x,s2.1),l2)
 (17)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fr2:=map((x:G):G+->eval(x,s2.1),r2)
 (18)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fl2*fr2
 (19)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))