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

# Edit detail for SandboxFactoringNoncommutativePolynomials revision 2 of 14

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Editor: Bill Page Time: 2018/07/04 16:39:30 GMT+0 Note: if not ALL monomials are generated ...

added:

for mon in support(p) repeat
if zero?(coefficient(fp, mon)) then
lst_eqn := []
break


  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
 (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
p1 := x::XDP * y::XDP
 (2)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Integer))
fricas
l1 := leftSubwords(p1)
 (3)
Type: List(XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer))))
fricas
r1 := rightSubwords(p1)
 (4)
Type: List(XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer))))
fricas
pe1 := factorizationPolynomial(p1)
 (5)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fe1 := factorizationEquations(p1)
 (6)
Type: List(Fraction(Polynomial(Integer)))
fricas
ve1 := members set concat map(variables,fe1)
 (7)
Type: List(Symbol)
fricas
s1 := solve(concat [fe1,[ve1.2-1]])
 (8)
Type: List(List(Equation(Fraction(Polynomial(Integer)))))

fricas
p1 := (x::XDP+1)^2
 (9)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Integer))
fricas
pe1 := factorizationPolynomial(p1)
 (10)
Type: XDistributedPolynomial?(OrderedVariableList?([x,y,z]),Fraction(Polynomial(Integer)))
fricas
fe1 := factorizationEquations(p1)
 (11)
Type: List(Fraction(Polynomial(Integer)))
fricas
ve1 := members set concat map(variables,fe1)
 (12)
Type: List(Symbol)
fricas
solve(concat [fe1,[ve1.1-1]])
 (13)
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.