nested roots

[Ralf Hemmecke]

(458) -> sqrt(s2)

+--------------------------------------------------------+
| +--+
\|1097675101059710976000 %i\|67 + 36223278334970462208000
(458) -----------------------------------------------------------
17
Type: Expression(Complex(Integer))

(459) -> factor gcd(1097675101059710976000,36223278334970462208000)

18 5 3 3 2
(459) 2 3 5 11 10177

Is there some easy way (a fricas function) to obtain from sqrt(s2) an
expression that has moved all common quadratic parts under the square
root outside?

I would like to see something like

+------------------+
| +--+
2579258880 \|165 %i\|67 + 5445
(471) --------------------------------
17
Type: Expression(Complex(Integer))

Thank you
Ralf

[Waldek Hebisch]

Well, this is probably too much:

rootFactor(sqrt(p1))

+-------------+
+--------+ +------+ +-+ +--+ | +--+
(70) 2579258880 \|1 + 2 %i \|2 + %i \|3 \|11 \|\|67 - 33 %i

We have ingredients like

nthRoot(squareFree(1097675101059710976000), 2)$FactoredFunctions(Integer)

(61) [exponent = 2, coef = 2579258880, radicand = [3, 5, 11]]

qroot(1097675101059710976000/1, 2)$pR

(63) [exponent = 2, coef = 2579258880, radicand = 165]

and content and primitivePart:

p1 := 1097675101059710976000*%i*sqrt(67) + _
36223278334970462208000::EXPR(COMPLEX(INT))

content(numer(p1))


(65) 1097675101059710976000

primitivePart(numer(p1))

+--+
(66) \|67 - 33 %i

In a sense closest to what you want is 'froot' from PolynomialRoots
but it does not handle integer content (which AFAICS is delibarate
decision due to potentially prohibitive cost of integer factorization).
It would be easy to add variant of 'froot' which handles also
integer content. OTOH calling anything from PolynomialRoots
is far from easy. For example pR above was defined via this
sequence of assignments:

vV := Kernel(Expression(Complex(Integer)))
eE := IndexedExponents(vV)
sP := SparseMultivariatePolynomial(Complex(Integer), _
Kernel(Expression(Complex(Integer))))
pR := POLYROOT(eE, vV, Complex(Integer), sP, Expression(Complex(Integer)))

Probably better would be do such transformation in 'rootSimp',
but again they can be quite expensive, so debatable is should
be done by default. And of course, 'rootSimp' can do things
which you do not want...

BTW: For roots of rational numbers AlgebraicFunction is doing this
by defualt:

sqrt(1097675101059710976000)
+---+
(67) 2579258880 \|165

But such transformations sometimes are undesirable.

--
Waldek Hebisch

[Ralf Hemmecke]

Dear Waldek,

Thank you for your explanation. It's always hard to find the right
functions if one doesn't know it already.

I am always getting so frustrated when it comes to Expression(...).
I know one can do a lot of things with and within the Expression domain,
but I find it hard and cumbersome to take things apart to achieve what I
want. Actually, I fear that I am not alone with this issue.

Clearly, it is even hard to give a good name to a function that does
exactly what I want. And then this function would have to check that the
expression it gets as input has a certain format.

It's already difficult (or even impossible) to convert my s2 into
AlgebraicNumber.

>> (458) -> sqrt(s2)
>>
>> +--------------------------------------------------------+
>> | +--+
>> \|1097675101059710976000 %i\|67 + 36223278334970462208000
>> (458) -----------------------------------------------------------
>> 17
>> Type: Expression(Complex(Integer))

Maybe I must study Expression even more. But we certainly need more
examples of how to convert from Expression to some more specific
domains. This is what I am currently lacking.

Ralf

[Waldek Hebisch]

On Tue, Jul 04, 2023 at 10:48:10PM +0200, Ralf Hemmecke wrote:

The following probably is doing what you want:

(1) -> p1 := 1097675101059710976000*%i*sqrt(67) + 36223278334970462208000

+--+
(1) 1097675101059710976000 %i\|67 + 36223278334970462208000
Type: Expression(Complex(Integer))
(2) -> r1 := sqrt(p1)

+--------------------------------------------------------+
| +--+
(2) \|1097675101059710976000 %i\|67 + 36223278334970462208000
Type: Expression(Complex(Integer))
(3) -> r1f := rootFactor(r1)

+-------------+
+--------+ +------+ +-+ +--+ | +--+

(3) 2579258880 \|1 + 2 %i \|2 + %i \|3 \|11 \|\|67 - 33 %i
Type: Expression(Complex(Integer))
(4) -> sqrt_rule := rule sqrt(x)*sqrt(y) == sqrt(-%i*%i*x*y)

+-+ +-+ +---+
(4) %D\|x \|y == %D\|x y
Type: RewriteRule(Integer,Complex(Integer),Expression(Complex(Integer)))
(5) -> sqrt_rule(r1f)

+------------------+
| +--+
(5) 2579258880 \|165 %i\|67 + 5445
Type: Expression(Complex(Integer))

So first use rootFactor to expand root into product of integer and
other roots, then combine roots together using rewrite rule.

Note: there is silly looking '-%i*%i' in the right hand of the rule,
I used it to force type to Expression(Complex(Integer)), otherwise
we would get rule applicable to Expression(Integer), but not
applicable to Expression(Complex(Integer)).

--
Waldek Hebisch

[Waldek Hebisch]

On Wed, Jul 05, 2023 at 12:51:55AM +0200, Ralf Hemmecke wrote:
> Dear Waldek,
>
> Thank you for your explanation. It's always hard to find the right functions
> if one doesn't know it already.
>
> I am always getting so frustrated when it comes to Expression(...).
> I know one can do a lot of things with and within the Expression domain, but
> I find it hard and cumbersome to take things apart to achieve what I want.
> Actually, I fear that I am not alone with this issue.
>
> Clearly, it is even hard to give a good name to a function that does exactly
> what I want. And then this function would have to check that the expression
> it gets as input has a certain format.
>
> It's already difficult (or even impossible) to convert my s2 into
> AlgebraicNumber.

Well, the trouble is %i, if you use sqrt(-1), then you will
get Expression(Integer) and things will be easy. But one can
do

(6) -> eI := Expression(Integer)

(6) Expression(Integer)
Type: Type
(7) -> eCI := Expression(Complex(Integer))

(7) Expression(Complex(Integer))
Type: Type
(8) -> iTM := ITRIGMNP(Integer, eI, eCI)

(8)
InnerTrigonometricManipulations(Integer,Expression(Integer),Expression(Comple
x(Integer)))
Type: Type
(9) -> FG2F(r1)$iTM

+------------------------------------------------------------+
| +---+ +--+
(9) \|1097675101059710976000 \|- 1 \|67 + 36223278334970462208000
Type: Expression(Integer)
(10) -> %::AlgebraicNumber

+------------------------------------------------------------+
| +---+ +--+
(10) \|1097675101059710976000 \|- 1 \|67 + 36223278334970462208000
Type: AlgebraicNumber


How one knows the name 'FG2F'? The answer unfortunetly seem to
be "read the source". It is used by integrator: first F2FG
convert form Expression(Integer) to Expression(Complex(Integer)),
then main work is done over complex numbers and then F2FG converts
result back to Expression(Integer)...

How one could write function like 'FG2F'? That is actually resonably
easy: over integral domains expression is just rational function in
kernels. So it is enough to separately transform numerator and
denominator, which is polynomial maniputation. For polynomials
we have PolynomialCategoryLifting which allows relatively simple
definition for complex transformation. You just need to define
map on coefficients and on variables. On coefficient our map
is easy, we map z to real(z) + sqrt(-1)*imag(z). More complex
is map on variables, that is kernels. We need to extract operator
and arguments from the kernel, for operator in
Expression(Complex(Integer)) we need to find its equvalent in
Expression(Integer), this is done by 'operator' function form
Expression(Integer), so we have silly looking code like

new_op := operator(operator(k))$Expression(Complex(Integer))

Once we have new operator you recusively transform arguments and apply
operator to transformed arguments.

If you think a bit that is acutally quite general scheme for building
transformations: if you want transformation to be a homomorphism,
which is natural requirement, then you need to define map on
coefficient and on kernes. If you leave coefficients alone,
there is utility function 'rmap' in ElementaryFunctionStructurePackage
which takes map from kernels to expressions and lifts it to
map on expressions.

What about rewrite rule that I used in another post? This is
build differently then recipe above and in general is dangerous.
I the example it was fine, but such rewirite rule can lead to
depenedent roots which may cause troubles (some years ago I
presented short "0 = 1" proof based on FriCAS handing of
dependent roots).

There is another kind of problems not handled by recipe above:
one can ask if an expression is in some specific subset.
Typical FriCAS pattern here uses 'univariate' reducing
problem to univariate polynomias or ratinal functions having
expressions as coefficients. But there are natural problem
whicj I do not know how to handle by 'univariate' pattern.
One of then is: given expression a and expressions b1,...,bn
check if a is in the field generated by b1,...,bn and in
case of positve anwer write a as rational function of b1,...,bn.
I think that this is solvable using Groebner bases, but probably
does not have signifcantly simpler solution.

> Maybe I must study Expression even more. But we certainly need more examples
> of how to convert from Expression to some more specific domains. This is
> what I am currently lacking.

There are retractions to kernels, coefficients, symbols and polynomials.
You can retract Expression(Integer) to AlgebraicNumber.

'numer', 'denom' and 'univariate' give you way to disassemble
expressions. You can decompose kernel into operator and arguments.
This allows you to build various transformations. There are
predefined functions for "typical" cases.

To get some ideas it may be worthwile to read 'efstruc.spad' and
'manip.spad'.

You can also use pattern matching, but this is a "convenience
feature", FriCAS pattern matching is build on top of operations I
mentioned above.

--
Waldek Hebisch