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