real? sqrt (-sqrt 2)

[Qian Yun]

"real? sqrt (-sqrt 2)" returns "true" by default.

Because interpreter prefers CTRIGMNP over TRIGMNIP
as shown by ")set mes bot on":

Function Selection for real?
Arguments: AN

[1] signature: EXPR(COMPLEX(INT)) -> BOOLEAN
implemented: slot (Boolean)(Expression (Complex (Integer))) from
CTRIGMNP(INT,EXPR(COMPLEX(INT)))
[2] signature: EXPR(INT) -> BOOLEAN
implemented: slot (Boolean)(Expression (Integer)) from
TRIGMNIP(INT,EXPR(INT))


Shall we consider this a bug?

- Qian

[Waldek Hebisch]

On Sun, Nov 19, 2023 at 07:58:50PM +0800, Qian Yun wrote:
> "real? sqrt (-sqrt 2)" returns "true" by default.

You mean should return false? We get this when working
with expressions:

(2) -> real? sqrt (-sqrt 2::EXPR(INT))

(2) false

> Because interpreter prefers CTRIGMNP over TRIGMNIP
> as shown by ")set mes bot on":
>
> Function Selection for real?
> Arguments: AN
>
> [1] signature: EXPR(COMPLEX(INT)) -> BOOLEAN
> implemented: slot (Boolean)(Expression (Complex (Integer))) from
> CTRIGMNP(INT,EXPR(COMPLEX(INT)))
> [2] signature: EXPR(INT) -> BOOLEAN
> implemented: slot (Boolean)(Expression (Integer)) from
> TRIGMNIP(INT,EXPR(INT))
>
>
> Shall we consider this a bug?

I do not think so. IIUC 'real?' in CTRIGMNP is quite different
function than 'real?' in TRIGMNIP. Namely, CTRIGMNP deals
with COMPLEX(EXPR(INT)), which is formal linear combination
'a + %i*b' where 'a' and 'b' are expressions and 'real?'
here tests if 'b' equals 0, which AFAICS is true.

'real?' in TRIGMNIP is making reasonable effort to find out if
"real" transformations of functions will give correct results.
Your expression is affected by trouble, what is meant by
'sqrt'? '-sqrt(2)' have two possible values, positive and negative.
So numerical value depends on choice of branches. One possible
meaning of 'real?' could be "argument is real for all possible choices
of branches". Another could be "argument is real for some choice
of branches". Yet another (and it is more or less what we use)
is that argument is "formally real", that is consists of
applications of "real" functions to "formally real" argument
with exception made for roots: even root of negative constant
is considered not-real. Each meaning have some sense. The first
two are problemantic, because in general branch questions are
undecidable. The third one is decidable and useful in some
contexts. But may be confusing for some users. And your case
is borderline for this definition: if sqrt(2) is considered as function
applied to a constant, than correct answer is "true". If
sqrt(2) is considered to be a positive constant, then
answer is "false". For our purposes it does not matter much.
We just need to be consistent: tests used in various places
should be "uniformly dumb", otherwise there is danger that
something which we consider real will be transformed into
something visibly complex by "too smart" transformation,
leading to possible bugs. And ideally we should not depend
on 'real?' at all: when we really care about expressions having
real values we should use stronger (or at least more reliable)
tests.


--
Waldek Hebisch

[Qian Yun]

On 11/19/23 21:36, Waldek Hebisch wrote:
> On Sun, Nov 19, 2023 at 07:58:50PM +0800, Qian Yun wrote:
>> "real? sqrt (-sqrt 2)" returns "true" by default.
>
> You mean should return false? We get this when working
> with expressions:
>
> (2) -> real? sqrt (-sqrt 2::EXPR(INT))
>
> (2) false
>
>> Because interpreter prefers CTRIGMNP over TRIGMNIP
>> as shown by ")set mes bot on":
>>
>> Function Selection for real?
>> Arguments: AN
>>
>> [1] signature: EXPR(COMPLEX(INT)) -> BOOLEAN
>> implemented: slot (Boolean)(Expression (Complex (Integer))) from
>> CTRIGMNP(INT,EXPR(COMPLEX(INT)))
>> [2] signature: EXPR(INT) -> BOOLEAN
>> implemented: slot (Boolean)(Expression (Integer)) from
>> TRIGMNIP(INT,EXPR(INT))
>>
>>
>> Shall we consider this a bug?
>
> I do not think so. IIUC 'real?' in CTRIGMNP is quite different
> function than 'real?' in TRIGMNIP. Namely, CTRIGMNP deals
> with COMPLEX(EXPR(INT)), which is formal linear combination
> 'a + %i*b' where 'a' and 'b' are expressions and 'real?'
> here tests if 'b' equals 0, which AFAICS is true.

I don't think 'real?' in CTRIGMNP is wrong.

I think the interpreter choose EXPR(COMPLEX(INT)) over EXPR(INT)
for AN is wrong. Isn't AN the same as EXPR(INT) in Rep?
So I think the interpreter auto coercion should prefer EXPR(INT).

> 'real?' in TRIGMNIP is making reasonable effort to find out if
> "real" transformations of functions will give correct results.
> Your expression is affected by trouble, what is meant by
> 'sqrt'? '-sqrt(2)' have two possible values, positive and negative.
> So numerical value depends on choice of branches.

I think for sqrt which is 'nthRoot, should be interpreted as the
positive branch.

While the algebraic number generated by "rootsOf(x^2-2)", which
is 'rootOf, have two possible values.

> One possible
> meaning of 'real?' could be "argument is real for all possible choices
> of branches". Another could be "argument is real for some choice
> of branches". Yet another (and it is more or less what we use)
> is that argument is "formally real", that is consists of
> applications of "real" functions to "formally real" argument
> with exception made for roots: even root of negative constant
> is considered not-real. Each meaning have some sense. The first
> two are problemantic, because in general branch questions are
> undecidable. The third one is decidable and useful in some
> contexts. But may be confusing for some users. And your case
> is borderline for this definition: if sqrt(2) is considered as function
> applied to a constant, than correct answer is "true". If
> sqrt(2) is considered to be a positive constant, then
> answer is "false".

I think we should have "sign", "real?" well defined for AlgebraicNumber.

- Qian

[Waldek Hebisch]

Interpreter has no idea what is Rep of AN. One can argue that
COMPLEX(INT) is more complex than INT, so should be preferable.
OTOH letter C is before letter I and letter T. Consequently,
interpreter sorting puts complex variant first in search list.

From somewhat different point of view, one can ask if the two
functions should share the name. Or if CTRIGMNP and TRIGMNIP
should be exposed. Or maybe more things should be hidden in
ITRIGMNP.

> > 'real?' in TRIGMNIP is making reasonable effort to find out if
> > "real" transformations of functions will give correct results.
> > Your expression is affected by trouble, what is meant by
> > 'sqrt'? '-sqrt(2)' have two possible values, positive and negative.
> > So numerical value depends on choice of branches.
>
> I think for sqrt which is 'nthRoot, should be interpreted as the
> positive branch.
>
> While the algebraic number generated by "rootsOf(x^2-2)", which
> is 'rootOf, have two possible values.

Well, even for AlgebraicNumber you almost immediately get complex
numbers. And no, there is no deep difference between 'nthRoot
and 'rootOf.

> > One possible
> > meaning of 'real?' could be "argument is real for all possible choices
> > of branches". Another could be "argument is real for some choice
> > of branches". Yet another (and it is more or less what we use)
> > is that argument is "formally real", that is consists of
> > applications of "real" functions to "formally real" argument
> > with exception made for roots: even root of negative constant
> > is considered not-real. Each meaning have some sense. The first
> > two are problemantic, because in general branch questions are
> > undecidable. The third one is decidable and useful in some
> > contexts. But may be confusing for some users. And your case
> > is borderline for this definition: if sqrt(2) is considered as function
> > applied to a constant, than correct answer is "true". If
> > sqrt(2) is considered to be a positive constant, then
> > answer is "false".
>
> I think we should have "sign", "real?" well defined for AlgebraicNumber.

Well, if you want then well defined use RealClosure(Fraction(Integer))
for real things and Complex(RealClosure(Fraction(Integer))) in
general case. But this really do not generalize to expressions,
so you are basically throwing away current expression-based
AlgebraicNumber.

--
Waldek Hebisch

[oldk1331]

Then is there a way to specify the algebraic number

which square is 2 and is near +1.41421?

- Qian

[Waldek Hebisch]

On Sun, Nov 19, 2023 at 10:50:17PM +0800, oldk1331 wrote:
> Then is there a way to specify the algebraic number
> which square is 2 and is near +1.41421?

(1) -> rC := RealClosure(Fraction(Integer))

(1) RealClosure(Fraction(Integer))
Type: Type
(2) -> s2 := sqrt(2)$rC

+-+
(2) \|2
Type: RealClosure(Fraction(Integer))
(3) -> approximate(s2, 1/10000)

46341
(3) -----
32768
Type: Fraction(Integer)
(4) -> 2 - (%)^2

4633
(4) - ----------
1073741824
Type: Fraction(Integer)
(5) -> sqrt(-s2)$rC

>> Error detected within library code:
no roots

ATM roots in Complex(rC) remain unimplemented.

--
Waldek Hebisch

[Qian Yun]

Does RealClosure work with Expression? (e.g doing integration)
Currently we can't do so in FriCAS. Is that possible in theory?

- Qian

[Qian Yun]

Answer to myself: some real algebraic number need sqrt(-1) to
represent them (e.g. some root of degree 3 polynomial).
So RealClosure can't handle them I guess.

- Qian

[Waldek Hebisch]

On Mon, Nov 20, 2023 at 06:20:45PM +0800, Qian Yun wrote:
> Answer to myself: some real algebraic number need sqrt(-1) to
> represent them (e.g. some root of degree 3 polynomial).
> So RealClosure can't handle them I guess.

No, this is not a problem. RealClosure can handle real roots of
polynomials without going into complex domain. sqrt(-1) appears
when one wants expression in radicals, but RealClosure represent
roots in more general way.

> - Qian
>
> On 11/20/23 07:45, Qian Yun wrote:
> > Does RealClosure work with Expression? (e.g doing integration)
> > Currently we can't do so in FriCAS.  Is that possible in theory?

Currently you can have Expression(RealClosure(Fraction(Integer))):

(8) -> sqrt(2)$eR

+-+
(8) \|2
Type: Expression(RealClosure(Fraction(Integer)))
(9) -> kernels(sqrt(2)$eR)

(9) []
Type: List(Kernel(Expression(RealClosure(Fraction(Integer)))))
(10) -> sqrt(-1)$eR

+---+
(10) \|- 1
Type: Expression(RealClosure(Fraction(Integer)))
(11) -> kernels(sqrt(-1)$eR)

+---+
(11) [\|- 1 ]
Type: List(Kernel(Expression(RealClosure(Fraction(Integer)))))
(12) -> kernels(sqrt(2 + sqrt(-1)$eR))

+----------+
| +---+
(12) [\|\|- 1 + 2 ]
Type: List(Kernel(Expression(RealClosure(Fraction(Integer)))))

(12) indicate possible confusion, mathematically the same thing may be
expressed in different ways leading to troubles with unrecoginized
zeros.

For integration we need PolynomialFactorizationExplicit and that
is absent for RealClosure. To say the truth, it is not entirely
clear what PolynomialFactorizationExplicit should do for
RealClosure. Interpreting it literally would mean splitting
univariate polynomials into quadratic and linear factors, which
is likely to be quite expensive. After that we would have to
implement multivariate factorization on top of this. I guess
that for multivariate factorization we probably should do
absolute factorization first and then only one variable
splitting.

Note that methods used by RealClosure in principle could
be generalized to elementary constants. But they will
fail in presence of parameters, that is for general
expressions.

Extra remark: it should be possible to get much of effect
of RealClosure by considering pairs of AlgebraicNumber
and floating point approximation. Namely, we can compute
minimal polynomial of algebraic number and moderately
accurate floating point approximation uniquely determines
corresponding exact root. In case when we get reducible
polynomials we could use floating point approximations to
find right factor.

--
Waldek Hebisch

[Dima Pasechnik]

the corresponding exact root will also be uniquely determined by the
signs of k-th order derivatives,
for all k, of the minimal polynomial at the root.
This is called Thom encoding (cf e.g. https://arxiv.org/pdf/1609.02879.pdf).
The advantage is that it still works in a parametrised setting, and that
it does not need any approximations.

Dima
>
> --
> Waldek Hebisch
>
> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/fricas-devel/ZVtVlGr6rtdJqSSX%40fricas.org.

[Qian Yun]

On 11/20/23 20:48, Waldek Hebisch wrote:
>
> Extra remark: it should be possible to get much of effect
> of RealClosure by considering pairs of AlgebraicNumber
> and floating point approximation. Namely, we can compute
> minimal polynomial of algebraic number and moderately
> accurate floating point approximation uniquely determines
> corresponding exact root. In case when we get reducible
> polynomials we could use floating point approximations to
> find right factor.
>

Does this mean the right thing to do is to have two kinds
of algebraic numbers? For first kind, its position is not
fixed (like current status of 'rootOf), for the other kind,
the position is fixed (you described above).

Because some computation doesn't care which root is which
(for example sum of all roots or a polynomial), while other
computation cares.

- Qian

[Waldek Hebisch]

We may have more kinds. Current AlgebraicNumber may run into
trouble if you create depenednt roots. Ralf posted code where
roots have consistent but unkown "order". That is it avoid
troubles due to dependent roots. There is correspondence
with roots in a finite field, and relation of roots in finite
field and roots in complex numbers is hard to compute.
Roots in finite field have rather simple relation to
roots in completition of p-adic numbers, to we can get
several competing variants of algebraic numbers.

--
Waldek Hebisch

[Qian Yun]

If so, I want to confirm that is 'nthRoot already a kind of
algebraic number?

'nthRoot constructs radicals, a subset of algebraic numbers.
And clearly code in different places treats 'nthRoot by
using its real valued branch, different than 'rootOf.

- Qian

[Waldek Hebisch]

On Tue, Nov 21, 2023 at 06:35:57PM +0800, Qian Yun wrote:
>
> If so, I want to confirm that is 'nthRoot already a kind of
> algebraic number?

I am not sure what you want to say here: 'nthRoot is in
AlgebraicNumber which under right conditions models
algebraic numbers and in Expression, where we have
things more general than numbers.

> 'nthRoot constructs radicals, a subset of algebraic numbers.
> And clearly code in different places treats 'nthRoot by
> using its real valued branch, different than 'rootOf.

Well, part of original motivation for domains and packages
was that each domain and package can have its own assumptions.
For example one place may assume that square root has nonnegative
argument and nonnegative value and different place can make
different assumbption. There was hope that modularity
(that is domains and packages) will prevent contradictions.
This does not work as well as originally hoped for.

In integrator we deal with rather general roots and we should
not depend on "reality" of expressions for correctness (this
is the reason for removing calls to 'real'). We can use
"reality" arguments in advisory way, so that result is correct
independent of "reality", but if determination of "reality"
is correct then we get nicer looking result. AFAICS this
applies to basic Rioboo algorithm: result is always a valid
antiderivative, but it removes poles and imaginaries only when
determination of real parts was correct.

--
Waldek Hebisch

[Qian Yun]

On 11/21/23 20:26, Waldek Hebisch wrote:
> On Tue, Nov 21, 2023 at 06:35:57PM +0800, Qian Yun wrote:
>>
>> If so, I want to confirm that is 'nthRoot already a kind of
>> algebraic number?
>
> I am not sure what you want to say here: 'nthRoot is in
> AlgebraicNumber which under right conditions models
> algebraic numbers and in Expression, where we have
> things more general than numbers.
>

OK, to give a specific example, what's the relationship
between sqrt(2) (a 'nthRoot) and %x0 (a 'rootOf):

(1) -> sqrt(2)

+-+
(1) \|2

(2) -> rootsOf(x^2-2)

(2) [%x0, - %x0]

- Qian

[Waldek Hebisch]

Using them together is user error. Argument to rootOf is supposed
to be irreducible polynomial. Once you add 'sqrt(2)' polynomial
'x^2 - 2' factors, so considering both togehter is user error.

Both could be used to represent "the same" element of AlgebraicNumber.
To put it differently, you should be able to replace one by the
other in all places and get correct result. Due to the way
in which AlgebraicNumber works, if you get one as input you
should return the same in the output. OTOH, internally one
can be replaced by the other if computation is more convenient
with different representation. Of course, after computation
is done we need to do backsubstitution, so that kernels
are preserved in the output.

Ralf's code allows you to have both in single computation
and either you have sqrt(2) = rootsOf(x^2-2) or
sqrt(2) = -rootsOf(x^2-2). Which of the two equalites holds
is depends on implementation in a way which for practical
purposes should be considered random.

Note that '>' (order) is not defined for AlgebraicNumber,
so it makes no sense to ask if "sqrt(2) > 0".

To put it differently, Galois theory says that at algebraic
level role of 'sqrt(2)' and '-sqrt(2)' is entirely symmetric.
You (and lot ot other folks) want to break this symmetry.
IMO breaking symmetry for AlgebraicNumber and for Expression
as domains is undesirable. Simply, it requires a lot of effort
and breaking symmetry is dangerous as it may break algorithms
that depend on symmetry. OTOH, locally we may do some things
that break symmetry, but we need to be careful since rest of
algbera will _not_ cooperate and each place when we break
symmetry need some justitication that it will not introduce
contradictions.

--
Waldek Hebisch

[Qian Yun]

Now I understand most of your points.

So what are the possible improvements regarding algebraic number
in the future?

For example, in a "locally breaking symmetry" use case, a "real?"
function to determine if an algebraic number is real, is that useful?
(e.g. (sqrt(3+4*sqrt(-1))+sqrt(3-4*sqrt(-1))))

Also, there's no function to transform a radical ('nthRoot) to
'rootOf currently, right?

- Qian

[Waldek Hebisch]

On Wed, Nov 22, 2023 at 08:29:11AM +0800, Qian Yun wrote:
> Now I understand most of your points.
>
> So what are the possible improvements regarding algebraic number
> in the future?

I do not think about deep changes to AlgebraicNumber or Expression,
at least in reasonably near future. Rather, I think that extra
functionality should go into separate packages.

> For example, in a "locally breaking symmetry" use case, a "real?"
> function to determine if an algebraic number is real, is that useful?
> (e.g. (sqrt(3+4*sqrt(-1))+sqrt(3-4*sqrt(-1))))

Recognizing that the above is real would be useful and does not
look very hard: it is symmetric in 'sqrt(-1)', so invariant
under complex conjugations (that is assuming that branches are
choosen in symmetric way). Assuming principal branch one
could even deduce that it is positive (real part of principal
branch square root is nonnegative).

Certainly I would like to have stronger methods of determining sign.
CAD may help, but is quite heavy. Some folks suggested splitting
(writing) expressions as sums of squares. In 2008 Strzeboński
proposed a simple method for functions build from 'x' and 'exp(x)'
(it generalizes Sturm sequences).

> Also, there's no function to transform a radical ('nthRoot) to
> 'rootOf currently, right?

No specific function, but 'subst' can tranform any expression
given mapping on kernels. And for kernels transformation is
essentially trivial.

--
Waldek Hebisch