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
fricas
(1) -> --)read nc_ini03
ALPHABET := ['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;
fricas
y := 'y::OFM;
fricas
z := 'z::OFM;
fricas
OF ==> OutputForm
Type: Void
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
Helper functions
Lift XDP over integers to YDP over rational functions and back
fricas
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.
Type: Void
fricas
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.
Type: Void
fricas
vars(p)==concat map(variables,coefficients(p))
Type: Void
Example 0:
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 G69 with type Integer -> Boolean
\label{eq1}\left[ \right]
(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 : XDP := x*(1-y*x);
fricas
l1 := reduce(+,leftSubwords(p_1))
\label{eq2}{a_{1}}+{{a_{2}}\ x}+{{a_{3}}\ x \ y}
(2) fricas
r1 := reduce(+,rightSubwords(p_1))
\label{eq3}{b_{1}}+{{b_{2}}\ x}+{{b_{3}}\ y \ x}
(3) fricas
e1 := factorizationEquations(p_1)
\label{eq4}\begin{array}{@{}l} \displaystyle \left[{{a_{1}}\ {b_{1}}}, \:{{{a_{1}}\ {b_{2}}}+{{a_{2}}\ {b_{1}}}- 1}, \:{{a_{1}}\ {b_{3}}}, \:{{a_{3}}\ {b_{1}}}, \:{{a_{2}}\ {b_{2}}}, \: \right. \ \ \displaystyle \left.{{{a_{2}}\ {b_{3}}}+{{a_{3}}\ {b_{2}}}+ 1}, \:{{a_{3}}\ {b_{3}}}\right]
(4) Type: List(Fraction(Polynomial(Integer)))
fricas
concat(vars l1, rest vars r1)
fricas
Compiling function vars with type XDistributedPolynomial(
OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer))) ->
List(Symbol)
\label{eq5}\left[{a_{3}}, \:{a_{2}}, \:{a_{1}}, \:{b_{2}}, \:{b_{1}}\right]
(5) Type: List(Symbol)
fricas
s1:=solve(e1,concat(vars l1, rest vars r1))
\label{eq6}\left[{\left[{{a_{3}}= 0}, \:{{a_{2}}= -{\frac{1}{b_{3}}}}, \:{{a_{1}}= 0}, \:{{b_{2}}= 0}, \:{{b_{1}}= -{b_{3}}}\right]}\right]
(6) Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fl1:=map((x:G):G+->eval(x,s1.1),l1)
\label{eq7}-{{\frac{1}{b_{3}}}\ x}
(7) fricas
fr1:=map((x:G):G+->eval(x,s1.1),r1)
\label{eq8}-{b_{3}}+{{b_{3}}\ y \ x}
(8) fricas
fl1*fr1
\label{eq9}x -{x \ y \ x}
(9) Example 2:
fricas
p_2 : XDP := x*y
fricas
l2 := reduce(+,leftSubwords(p_2))
\label{eq11}{a_{1}}+{{a_{2}}\ x}
(11) fricas
r2 := reduce(+,rightSubwords(p_2))
\label{eq12}{b_{1}}+{{b_{2}}\ y}
(12) fricas
e2 := factorizationEquations(p_2)
\label{eq13}\left[{{a_{1}}\ {b_{1}}}, \:{{a_{1}}\ {b_{2}}}, \:{{a_{2}}\ {b_{1}}}, \:{{{a_{2}}\ {b_{2}}}- 1}\right]
(13) Type: List(Fraction(Polynomial(Integer)))
fricas
s2:=solve(e2,concat(vars l2, rest vars r2))
\label{eq14}\left[{\left[{{a_{2}}={\frac{1}{b_{2}}}}, \:{{a_{1}}= 0}, \:{{b_{1}}= 0}\right]}\right]
(14) Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fl2:=map((x:G):G+->eval(x,s2.1),l2)
\label{eq15}{\frac{1}{b_{2}}}\ x
(15) fricas
fr2:=map((x:G):G+->eval(x,s2.1),r2)
\label{eq16}{b_{2}}\ y
(16) fricas
fl2*fr2
Example 3:
fricas
p_3 : XDP := (x-y)*(x+y)
\label{eq18}-{{y}^{2}}-{y \ x}+{x \ y}+{{x}^{2}}
(18) fricas
l3 := reduce(+,leftSubwords(p_3))
\label{eq19}{a_{1}}+{{a_{3}}\ y}+{{a_{2}}\ x}
(19) fricas
r3 := reduce(+,rightSubwords(p_3))
\label{eq20}{b_{1}}+{{b_{3}}\ y}+{{b_{2}}\ x}
(20) fricas
e3 := factorizationEquations(p_3)
\label{eq21}\begin{array}{@{}l} \displaystyle \left[{{a_{1}}\ {b_{1}}}, \:{{{a_{1}}\ {b_{3}}}+{{a_{3}}\ {b_{1}}}}, \:{{{a_{1}}\ {b_{2}}}+{{a_{2}}\ {b_{1}}}}, \:{{{a_{3}}\ {b_{3}}}+ 1}, \:{{{a_{3}}\ {b_{2}}}+ 1}, \: \right. \ \ \displaystyle \left.{{{a_{2}}\ {b_{3}}}- 1}, \:{{{a_{2}}\ {b_{2}}}- 1}\right]
(21) Type: List(Fraction(Polynomial(Integer)))
fricas
s3:=solve(e3,concat(vars l3, rest vars r3))
\label{eq22}\left[{\left[{{a_{2}}={\frac{1}{b_{2}}}}, \:{{a_{3}}= -{\frac{1}{b_{2}}}}, \:{{a_{1}}= 0}, \:{{b_{3}}={b_{2}}}, \:{{b_{1}}= 0}\right]}\right]
(22) Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fl3:=map((x:G):G+->eval(x,s3.1),l3)
\label{eq23}-{{\frac{1}{b_{2}}}\ y}+{{\frac{1}{b_{2}}}\ x}
(23) fricas
fr3:=map((x:G):G+->eval(x,s3.1),r3)
\label{eq24}{{b_{2}}\ y}+{{b_{2}}\ x}
(24) fricas
fl3*fr3
\label{eq25}-{{y}^{2}}-{y \ x}+{x \ y}+{{x}^{2}}
(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.
fricas
param(e) == first variables first remove((x:G):Boolean+->#variables(x)<2, e)
Type: Void
Example 4:
fricas
p_4 : XDP := (x-y^2)*(x+z^2)
\label{eq26}{{x}^{2}}-{{{y}^{2}}\ x}+{x \ {{z}^{2}}}-{{{y}^{2}}\ {{z}^{2}}}
(26) fricas
l4 := reduce(+,leftSubwords(p_4))
\label{eq27}{a_{1}}+{{a_{2}}\ y}+{{a_{5}}\ x}+{{a_{3}}\ {{y}^{2}}}+{{a_{6}}\ x \ z}+{{a_{4}}\ {{y}^{2}}\ z}
(27) fricas
r4 := reduce(+,rightSubwords(p_4))
\label{eq28}{b_{1}}+{{b_{2}}\ z}+{{b_{5}}\ x}+{{b_{3}}\ {{z}^{2}}}+{{b_{6}}\ y \ x}+{{b_{4}}\ y \ {{z}^{2}}}
(28) fricas
e4 := factorizationEquations(p_4)
\label{eq29}\begin{array}{@{}l} \displaystyle \left[{{a_{1}}\ {b_{1}}}, \:{{a_{1}}\ {b_{2}}}, \:{{a_{2}}\ {b_{1}}}, \:{{{a_{1}}\ {b_{5}}}+{{a_{5}}\ {b_{1}}}}, \:{{a_{1}}\ {b_{3}}}, \:{{a_{2}}\ {b_{2}}}, \:{{a_{3}}\ {b_{1}}}, \: \right. \ \ \displaystyle \left.{{{a_{1}}\ {b_{6}}}+{{a_{2}}\ {b_{5}}}}, \:{{{a_{5}}\ {b_{2}}}+{{a_{6}}\ {b_{1}}}}, \:{{{a_{5}}\ {b_{5}}}- 1}, \:{{{a_{1}}\ {b_{4}}}+{{a_{2}}\ {b_{3}}}}, \: \right. \ \ \displaystyle \left.{{{a_{3}}\ {b_{2}}}+{{a_{4}}\ {b_{1}}}}, \:{{{a_{2}}\ {b_{6}}}+{{a_{3}}\ {b_{5}}}+ 1}, \:{{{a_{5}}\ {b_{3}}}+{{a_{6}}\ {b_{2}}}- 1}, \:{{a_{6}}\ {b_{5}}}, \: \right. \ \ \displaystyle \left.{{a_{5}}\ {b_{6}}}, \:{{{a_{2}}\ {b_{4}}}+{{a_{3}}\ {b_{3}}}+{{a_{4}}\ {b_{2}}}+ 1}, \:{{a_{4}}\ {b_{5}}}, \:{{a_{3}}\ {b_{6}}}, \:{{a_{6}}\ {b_{3}}}, \:{{a_{6}}\ {b_{6}}}, \: \right. \ \ \displaystyle \left.{{a_{5}}\ {b_{4}}}, \:{{a_{4}}\ {b_{3}}}, \:{{a_{4}}\ {b_{6}}}, \:{{a_{3}}\ {b_{4}}}, \:{{a_{6}}\ {b_{4}}}, \:{{a_{4}}\ {b_{4}}}\right]
(29) Type: List(Fraction(Polynomial(Integer)))
fricas
groebnerFactorize e4
\label{eq30}\left[{\left[ 1 \right]}, \:{\left[{b_{6}}, \:{{b_{5}}-{b_{3}}}, \:{b_{4}}, \:{{{a_{3}}\ {b_{3}}}+ 1}, \:{b_{2}}, \:{b_{1}}, \:{a_{6}}, \:{{a_{5}}+{a_{3}}}, \:{a_{4}}, \:{a_{2}}, \:{a_{1}}\right]}\right]
(30) Type: List(List(Polynomial(Integer)))
fricas
e4a := last %
\label{eq31}\left[{b_{6}}, \:{{b_{5}}-{b_{3}}}, \:{b_{4}}, \:{{{a_{3}}\ {b_{3}}}+ 1}, \:{b_{2}}, \:{b_{1}}, \:{a_{6}}, \:{{a_{5}}+{a_{3}}}, \:{a_{4}}, \:{a_{2}}, \:{a_{1}}\right]
(31) Type: List(Polynomial(Integer))
fricas
param(e4a)
fricas
Compiling function param with type List(Polynomial(Integer)) ->
Symbol
Type: Symbol
fricas
)set output tex off
fricas
)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
]
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
)set output tex on
fricas
)set output algebra off
fl4:=map((x:G):G+->eval(x,s4.1),l4)
\label{eq33}{{\frac{1}{b_{5}}}\ x}-{{\frac{1}{b_{5}}}\ {{y}^{2}}}
(33) fricas
fr4:=map((x:G):G+->eval(x,s4.1),r4)
\label{eq34}{{b_{5}}\ x}+{{b_{5}}\ {{z}^{2}}}
(34) fricas
fl4*fr4
\label{eq35}{{x}^{2}}-{{{y}^{2}}\ x}+{x \ {{z}^{2}}}-{{{y}^{2}}\ {{z}^{2}}}
(35) fricas
test(mapPoly p_4 = fl4*fr4)
fricas
Compiling function mapPoly with type XDistributedPolynomial(
OrderedVariableList([x,y,z]),Integer) -> XDistributedPolynomial(
OrderedVariableList([x,y,z]),Fraction(Polynomial(Integer)))
\label{eq36} \mbox{\rm true}
(36) Type: Boolean
Example 5:
fricas
p_5 : XDP := (x*y*z+y*x*z)*(z*x*y+z*y*x)
\label{eq37}{y \ x \ {{z}^{2}}\ y \ x}+{y \ x \ {{z}^{2}}\ x \ y}+{x \ y \ {{z}^{2}}\ y \ x}+{x \ y \ {{z}^{2}}\ x \ y}
(37) fricas
l5 := reduce(+,leftSubwords(p_5))
\label{eq38}\begin{array}{@{}l} \displaystyle {a_{1}}+{{a_{8}}\ y}+{{a_{2}}\ x}+{{a_{9}}\ y \ x}+{{a_{3}}\ x \ y}+{{a_{10}}\ y \ x \ z}+{{a_{4}}\ x \ y \ z}+ \ \ \displaystyle {{a_{11}}\ y \ x \ {{z}^{2}}}+{{a_{5}}\ x \ y \ {{z}^{2}}}+{{a_{13}}\ y \ x \ {{z}^{2}}\ y}+{{a_{12}}\ y \ x \ {{z}^{2}}\ x}+ \ \ \displaystyle {{a_{7}}\ x \ y \ {{z}^{2}}\ y}+{{a_{6}}\ x \ y \ {{z}^{2}}\ x}
(38) fricas
r5 := reduce(+,rightSubwords(p_5))
\label{eq39}\begin{array}{@{}l} \displaystyle {b_{1}}+{{b_{2}}\ y}+{{b_{7}}\ x}+{{b_{8}}\ y \ x}+{{b_{3}}\ x \ y}+{{b_{9}}\ z \ y \ x}+{{b_{4}}\ z \ x \ y}+ \ \ \displaystyle {{b_{10}}\ {{z}^{2}}\ y \ x}+{{b_{5}}\ {{z}^{2}}\ x \ y}+{{b_{11}}\ y \ {{z}^{2}}\ y \ x}+{{b_{6}}\ y \ {{z}^{2}}\ x \ y}+ \ \ \displaystyle {{b_{13}}\ x \ {{z}^{2}}\ y \ x}+{{b_{12}}\ x \ {{z}^{2}}\ x \ y}
(39) fricas
e5 := factorizationEquations(p_5)
\label{eq40}\begin{array}{@{}l} \displaystyle \left[{{a_{1}}\ {b_{1}}}, \:{{{a_{1}}\ {b_{2}}}+{{a_{8}}\ {b_{1}}}}, \:{{{a_{1}}\ {b_{7}}}+{{a_{2}}\ {b_{1}}}}, \:{{a_{8}}\ {b_{2}}}, \: \right. \ \ \displaystyle \left.{{{a_{1}}\ {b_{8}}}+{{a_{8}}\ {b_{7}}}+{{a_{9}}\ {b_{1}}}}, \:{{{a_{1}}\ {b_{3}}}+{{a_{2}}\ {b_{2}}}+{{a_{3}}\ {b_{1}}}}, \:{{a_{2}}\ {b_{7}}}, \:{{a_{1}}\ {b_{9}}}, \: \right. \ \ \displaystyle \left.{{a_{1}}\ {b_{4}}}, \:{{a_{8}}\ {b_{8}}}, \:{{a_{10}}\ {b_{1}}}, \:{{{a_{8}}\ {b_{3}}}+{{a_{9}}\ {b_{2}}}}, \:{{a_{9}}\ {b_{7}}}, \:{{a_{4}}\ {b_{1}}}, \:{{a_{3}}\ {b_{2}}}, \: \right. \ \ \displaystyle \left.{{{a_{2}}\ {b_{8}}}+{{a_{3}}\ {b_{7}}}}, \:{{a_{2}}\ {b_{3}}}, \:{{a_{1}}\ {b_{10}}}, \:{{a_{1}}\ {b_{5}}}, \:{{a_{8}}\ {b_{9}}}, \:{{a_{8}}\ {b_{4}}}, \:{{a_{11}}\ {b_{1}}}, \: \right. \ \ \displaystyle \left.{{a_{10}}\ {b_{2}}}, \:{{a_{10}}\ {b_{7}}}, \:{{a_{9}}\ {b_{8}}}, \:{{a_{9}}\ {b_{3}}}, \:{{a_{2}}\ {b_{9}}}, \:{{a_{2}}\ {b_{4}}}, \:{{a_{5}}\ {b_{1}}}, \:{{a_{4}}\ {b_{2}}}, \:{{a_{4}}\ {b_{7}}}, \: \right. \ \ \displaystyle \left.{{a_{3}}\ {b_{8}}}, \:{{a_{3}}\ {b_{3}}}, \:{{{a_{1}}\ {b_{11}}}+{{a_{8}}\ {b_{10}}}}, \:{{{a_{1}}\ {b_{6}}}+{{a_{8}}\ {b_{5}}}}, \:{{{a_{11}}\ {b_{2}}}+{{a_{13}}\ {b_{1}}}}, \right. \ \ \displaystyle \left.\:{{{a_{11}}\ {b_{7}}}+{{a_{12}}\ {b_{1}}}}, \:{{{a_{9}}\ {b_{9}}}+{{a_{10}}\ {b_{8}}}}, \:{{{a_{9}}\ {b_{4}}}+{{a_{10}}\ {b_{3}}}}, \: \right. \ \ \displaystyle \left.{{{a_{1}}\ {b_{13}}}+{{a_{2}}\ {b_{10}}}}, \:{{{a_{1}}\ {b_{12}}}+{{a_{2}}\ {b_{5}}}}, \:{{{a_{5}}\ {b_{2}}}+{{a_{7}}\ {b_{1}}}}, \:{{{a_{5}}\ {b_{7}}}+{{a_{6}}\ {b_{1}}}}, \right. \ \ \displaystyle \left.\:{{{a_{3}}\ {b_{9}}}+{{a_{4}}\ {b_{8}}}}, \:{{{a_{3}}\ {b_{4}}}+{{a_{4}}\ {b_{3}}}}, \:{{a_{8}}\ {b_{11}}}, \:{{a_{8}}\ {b_{6}}}, \:{{a_{13}}\ {b_{2}}}, \: \right. \ \ \displaystyle \left.{{{a_{8}}\ {b_{13}}}+{{a_{9}}\ {b_{10}}}+{{a_{10}}\ {b_{9}}}+{{a_{11}}\ {b_{8}}}+{{a_{13}}\ {b_{7}}}- 1}, \: \right. \ \ \displaystyle \left.{{{a_{8}}\ {b_{12}}}+{{a_{9}}\ {b_{5}}}+{{a_{10}}\ {b_{4}}}+{{a_{11}}\ {b_{3}}}+{{a_{12}}\ {b_{2}}}- 1}, \:{{a_{12}}\ {b_{7}}}, \:{{a_{7}}\ {b_{2}}}, \right. \ \ \displaystyle \left.\:{{{a_{2}}\ {b_{11}}}+{{a_{3}}\ {b_{10}}}+{{a_{4}}\ {b_{9}}}+{{a_{5}}\ {b_{8}}}+{{a_{7}}\ {b_{7}}}- 1}, \: \right. \ \ \displaystyle \left.{{{a_{2}}\ {b_{6}}}+{{a_{3}}\ {b_{5}}}+{{a_{4}}\ {b_{4}}}+{{a_{5}}\ {b_{3}}}+{{a_{6}}\ {b_{2}}}- 1}, \:{{a_{6}}\ {b_{7}}}, \:{{a_{2}}\ {b_{13}}}, \: \right. \ \ \displaystyle \left.{{a_{2}}\ {b_{12}}}, \:{{{a_{10}}\ {b_{10}}}+{{a_{11}}\ {b_{9}}}}, \:{{{a_{10}}\ {b_{5}}}+{{a_{11}}\ {b_{4}}}}, \:{{a_{1 3}}\ {b_{8}}}, \:{{a_{13}}\ {b_{3}}}, \: \right. \ \ \displaystyle \left.{{a_{12}}\ {b_{8}}}, \:{{a_{12}}\ {b_{3}}}, \:{{a_{9}}\ {b_{11}}}, \:{{a_{9}}\ {b_{6}}}, \:{{a_{9}}\ {b_{13}}}, \:{{a_{9}}\ {b_{12}}}, \:{{{a_{4}}\ {b_{10}}}+{{a_{5}}\ {b_{9}}}}, \: \right. \ \ \displaystyle \left.{{{a_{4}}\ {b_{5}}}+{{a_{5}}\ {b_{4}}}}, \:{{a_{7}}\ {b_{8}}}, \:{{a_{7}}\ {b_{3}}}, \:{{a_{6}}\ {b_{8}}}, \:{{a_{6}}\ {b_{3}}}, \:{{a_{3}}\ {b_{11}}}, \:{{a_{3}}\ {b_{6}}}, \: \right. \ \ \displaystyle \left.{{a_{3}}\ {b_{13}}}, \:{{a_{3}}\ {b_{12}}}, \:{{a_{11}}\ {b_{10}}}, \:{{a_{11}}\ {b_{5}}}, \:{{a_{13}}\ {b_{9}}}, \:{{a_{1 3}}\ {b_{4}}}, \:{{a_{12}}\ {b_{9}}}, \: \right. \ \ \displaystyle \left.{{a_{12}}\ {b_{4}}}, \:{{a_{10}}\ {b_{11}}}, \:{{a_{10}}\ {b_{6}}}, \:{{a_{10}}\ {b_{13}}}, \:{{a_{10}}\ {b_{12}}}, \:{{a_{5}}\ {b_{10}}}, \:{{a_{5}}\ {b_{5}}}, \: \right. \ \ \displaystyle \left.{{a_{7}}\ {b_{9}}}, \:{{a_{7}}\ {b_{4}}}, \:{{a_{6}}\ {b_{9}}}, \:{{a_{6}}\ {b_{4}}}, \:{{a_{4}}\ {b_{11}}}, \:{{a_{4}}\ {b_{6}}}, \:{{a_{4}}\ {b_{13}}}, \:{{a_{4}}\ {b_{12}}}, \: \right. \ \ \displaystyle \left.{{{a_{11}}\ {b_{11}}}+{{a_{13}}\ {b_{10}}}}, \:{{{a_{11}}\ {b_{6}}}+{{a_{13}}\ {b_{5}}}}, \:{{{a_{11}}\ {b_{13}}}+{{a_{12}}\ {b_{10}}}}, \: \right. \ \ \displaystyle \left.{{{a_{11}}\ {b_{12}}}+{{a_{12}}\ {b_{5}}}}, \:{{{a_{5}}\ {b_{11}}}+{{a_{7}}\ {b_{10}}}}, \:{{{a_{5}}\ {b_{6}}}+{{a_{7}}\ {b_{5}}}}, \: \right. \ \ \displaystyle \left.{{{a_{5}}\ {b_{13}}}+{{a_{6}}\ {b_{10}}}}, \:{{{a_{5}}\ {b_{12}}}+{{a_{6}}\ {b_{5}}}}, \:{{a_{13}}\ {b_{11}}}, \:{{a_{13}}\ {b_{6}}}, \:{{a_{13}}\ {b_{13}}}, \: \right. \ \ \displaystyle \left.{{a_{13}}\ {b_{12}}}, \:{{a_{12}}\ {b_{11}}}, \:{{a_{12}}\ {b_{6}}}, \:{{a_{12}}\ {b_{13}}}, \:{{a_{12}}\ {b_{12}}}, \:{{a_{7}}\ {b_{11}}}, \:{{a_{7}}\ {b_{6}}}, \: \right. \ \ \displaystyle \left.{{a_{7}}\ {b_{13}}}, \:{{a_{7}}\ {b_{12}}}, \:{{a_{6}}\ {b_{11}}}, \:{{a_{6}}\ {b_{6}}}, \:{{a_{6}}\ {b_{13}}}, \:{{a_{6}}\ {b_{12}}}\right]
(40) Type: List(Fraction(Polynomial(Integer)))
fricas
)set output tex off
fricas
)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
>> Error detected within library code:
index out of range
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.
fricas
p_6 : XDP := 2 - x^2
2
(62) 2 - x
fricas
l6 := reduce(+,leftSubwords(p_6))
(63) a + a x
1 2
fricas
r6 := reduce(+,rightSubwords(p_6))
(64) b + b x
1 2
fricas
e6 := factorizationEquations(p_6)
(65) [a b - 2, a b + a b , a b + 1]
1 1 1 2 2 1 2 2
Type: List(Fraction(Polynomial(Integer)))
fricas
-- 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
Type: Void
fricas
s6
2 b
2 2 2 2
(67) [[a = - ----, a = --, 2 b - b = 0]]
2 2 1 b 2 1
b 1
1
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
Test for irreducibility.
fricas
map(x+->retractIfCan(lhs x)@Union(Symbol,"failed") case Symbol, s6.1)
(68) [true, true, false]
Type: List(Boolean)
fricas
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"
(69) "irreducible"
Type: irreducible