alarum: Risch integrator fails to divide by zero

[clicl...@freenet.de]

Grrrmbl.

A state-of-the-art implementation of a Risch integrator

)version

Value = "FriCAS 1.3.0 compiled at Thu Sep 1 17:01:37 UTC 2016"

responds to

integrate((1 + x)/((1 + x + x^2)*(a + b*x^3)^(1/3)), x)

with

>> Error detected within library code:
catdef: division by zero

In his "Symbolic Integration Tutorial", Bronstein appears to believe in
the existence of a workable integration algorithm for algebraic
integrands involving a simple radical extension. Didn't he know what he
was talking about?

Martin.

[anti...@math.uni.wroc.pl]

Writing paper he ceratainly knew what is is writing. But writing
code he apparently assumed that he will be lucky. Or to put it
differetly: code he wrote is enough to "demostrate" that algorithm
works. But there remain "uninteresting" programming probles to
resolve. To the point: his code uses random integers. If
substituting those integers into one of denominators gives zero,
then you will see this error. Correct algorithm would retry
with different values. But his code just gives error. Recent
changes to FriCAS lead to change in random choice and for
some integrals (like this one) the problem became very visible.

One can try to hide the problem using more randomness. Or
one can do "uninteresting" programming and properly implement
retry.

BTW: This is FriCAS bug and proper place to report this is
FriCAS mailing list or Sourceforge bugtracke. And this
problem was was already reported (after relase of 1.3.0).

--
Waldek Hebisch

[clicl...@freenet.de]

anti...@math.uni.wroc.pl schrieb:

Oh, I thought I was the first to try this particular variation of a
familar cube-root integrand. But to implement a loop over different
pseudo-random numbers should be easy, and its omission may be a mere
oversight. I will submit this integrand again to the next version.

Another thing has me wondering. Your antiderivatives of rational
functions can be discontinuous because the ATAN part is not always
rewritten to involve polynomial arguments only, as proposed by Rioboo.
For example, FriCAS 1.3.0 computes (expressed in Derive notation)

INT((2560*x^3 - 400*x^2 - 576*x - 84)/(320*x^4 + 80*x^3 - 12*x^2
+ 24*x + 9), x) = 2*LN(320*x^4 + 80*x^3 - 12*x^2 + 24*x + 9)
+ 2*SQRT(11)*ATAN(SQRT(11)*(10*x + 3)/(80*x^2 + 10*x - 9))

This is surprising especially since Bronstein provides pseudocode of
Rioboo's algorithm in his book (Ch. 2.8).

Martin.

[oldk...@gmail.com]

> Oh, I thought I was the first to try this particular variation of a
> familar cube-root integrand. But to implement a loop over different
> pseudo-random numbers should be easy, and its omission may be a mere
> oversight. I will submit this integrand again to the next version.

After fixing this "division by zero" bug, your first integral seems to
loop indefinitely. I think there is no symbolic result for
"integrate((1 + x)/((1 + x + x^2)*(a + b*x^3)^(1/3)), x)".
When a,b are integers, FriCAS can give symbolic results.

> Another thing has me wondering. Your antiderivatives of rational
> functions can be discontinuous because the ATAN part is not always
> rewritten to involve polynomial arguments only, as proposed by Rioboo.

For this example, I have post a small patch to fricas-devel. After
my patch, FriCAS gives continuous result, same as SymPy.
I think this is a small programming mistake made by Manuel Bronstein.

[clicl...@freenet.de]

oldk...@gmail.com schrieb:
>
> [...] I think there is no symbolic result for

> "integrate((1 + x)/((1 + x + x^2)*(a + b*x^3)^(1/3)), x)".
> When a,b are integers, FriCAS can give symbolic results.

Wow - we could all become world-famous if this proves to be the first
parametrized algebraic integrand with this property! Alas, my Derive
oracle says:

goursat5a((x + 1)/(x^2 + x + 1), x, a, 0, 0, b)

[false, false, false, true, true]

which means integrable :(. Might something else perhaps be amiss with
the current "demonstration-only" code of FriCAS?

>
> [...] For this example, I have post a small patch to fricas-devel.

> After my patch, FriCAS gives continuous result, same as SymPy.

Thanks, I myself obtain (up to some piecewise constant):

ATAN(SQRT(11)*(10*x + 3)/(80*x^2 + 10*x - 9)) =
- ATAN(SQRT(11)*(800*x^3 - 40*x^2 + 30*x + 57)/66)
- ATAN(SQRT(11)*(40*x - 7)/55)

Martin.

[oldk...@gmail.com]

> Wow - we could all become world-famous if this proves to be the first
> parametrized algebraic integrand with this property!

Can you be more clear with that? Just to clarify, I test a,b with some
prime numbers, and FriCAS always gives result.

[clicl...@freenet.de]

oldk...@gmail.com schrieb:

>
> > > I think there is no symbolic result for
> > > "integrate((1 + x)/((1 + x + x^2)*(a + b*x^3)^(1/3)), x)".
> > > When a,b are integers, FriCAS can give symbolic results.
>

You appeared to be contemplating the violation of a principle supported
by extensive observation:

Let f(p,x) be an algebraic function in both arguments; if, with respect
to x, f(p,x) possesses an elementary antiderivative for an infinite
number of complex parameter values p, then it possesses a single
symbolic elementary antiderivative F(p,x) that holds for all complex
values of p.

Proof (or disproof) of the principle is left to our top experts in
symbolic integration theory.

Martin.

[oldk...@gmail.com]

> You appeared to be contemplating the violation of a principle supported
> by extensive observation:

Is there a conjecture like this?

Let's say "integrate(f(p,x), x) = F(p,x)", and maybe F is recursive:
F(p,x) = G(F(p-1,x))
I don't think there are algorithms can expand recursive definition.

[anti...@math.uni.wroc.pl]

Look at

http://koutschan.de/conf/ICMS16/davenport.pdf

starting from page 25. It seems that we need to limit
how parameter is choosen, otherwise there is a
couterexample. The claim appeared as a theorem, but
recently couterexample was discovered, so there
remain some work to find correct statement. IIUC
the case when you substitute integers is considerd
to be proved.

--
Waldek Hebisch

[anti...@math.uni.wroc.pl]

oldk...@gmail.com wrote:
>
> After fixing this "division by zero" bug, your first integral seems to
> loop indefinitely. I think there is no symbolic result for
> "integrate((1 + x)/((1 + x + x^2)*(a + b*x^3)^(1/3)), x)".
> When a,b are integers, FriCAS can give symbolic results.

Actually, computation of algebraic integrals in FriCAS may
be quite slow and require a lot of memory -- I can not say
how much but in all slow cases that I looked at there were
indication of forward progress.

--
Waldek Hebisch

[clicl...@freenet.de]

anti...@math.uni.wroc.pl schrieb:

>
> Look at
>
> http://koutschan.de/conf/ICMS16/davenport.pdf
>
> starting from page 25. It seems that we need to limit
> how parameter is choosen, otherwise there is a
> couterexample. The claim appeared as a theorem, but
> recently couterexample was discovered, so there
> remain some work to find correct statement. IIUC
> the case when you substitute integers is considerd
> to be proved.
>

Thanks! I wasn't aware of Davenport's paper, and the "principle" was
distilled from my own and only my own experience :).

Martin.

[clicl...@freenet.de]

anti...@math.uni.wroc.pl schrieb:

>
> Look at
>
> http://koutschan.de/conf/ICMS16/davenport.pdf
>
> starting from page 25. It seems that we need to limit
> how parameter is choosen, otherwise there is a
> couterexample. The claim appeared as a theorem, but
> recently couterexample was discovered, so there
> remain some work to find correct statement. IIUC
> the case when you substitute integers is considerd
> to be proved.
>

I have now looked into this a bit. A better reference is Davenport's
conference paper <http://koutschan.de/conf/ICMS16/Integration.pdf>. His
counterexample:

INT(x/((x^2 - u^2)*SQRT(x^3 - x)), x) = ?

is taken from unpublished work by Masser and Zannier. The integral is
Goursat pseudo-elliptic if and only if u^2 = -1 or u^2 = 3 +- 2*SQRT(2),
the three cases corresponding to the points [u,v]:

[#i, 1 - #i]
[SQRT(2) + 1, 2 + SQRT(2)]
[SQRT(2) - 1, (2 - SQRT(2))*#i]

on the elliptic curve v^2 = u^3 - u. I guess they are just the points
of order four on the curve. Elementary evaluations of the corresponding
Goursat integrals are:

INT(x/((x^2 + 1)*SQRT(x^3 - x)), x) =
1/2*ATANH((x - 1)/SQRT(x^3 - x)) - 1/2*ATAN((x + 1)/SQRT(x^3 - x))

INT(x/((x^2 + 2*SQRT(2) - 3)*SQRT(x^3 - x)), x) =
(2 + SQRT(2))/4*ATANH((SQRT(2) - 1)*(x - 1)/SQRT(x^3 - x))
- (2 + SQRT(2))/4*ATAN((SQRT(2) - 1)*(x + 1)/SQRT(x^3 - x))

INT(x/((x^2 - 2*SQRT(2) - 3)*SQRT(x^3 - x)), x) =
(SQRT(2) - 2)/4*ATANH((1 + SQRT(2))*(x - 1)/SQRT(x^3 - x))
- (SQRT(2) - 2)/4*ATAN((1 + SQRT(2))*(x + 1)/SQRT(x^3 - x))

Thus, the result in Davenport's paper is unnecessarily complicated -
perhaps it can be replaced still?

FriCAS 1.3.0 solves the Goursat integration problems readily. Does the
system allow to compute some (preferably simple) points of order three
on the elliptic curve? According to Davenport, Masser and Zannier claim
those points to determine an infinite number of non-Goursat integrals
that are nonetheless elementary. It would be interesting to see if
FriCAS succeeds in evaluating them and what the antiderivatives look
like.

Martin.

[clicl...@freenet.de]

clicl...@freenet.de schrieb:

I have now also looked into the elliptic-curve aspect of this
counterexample integral.

The three Goursat cases do indeed correspond to the points of order
four. I have also determined the points of order three and discovered
that FriCAS 1.3.0 returns the associated pair of integrals unevaluated.
Something must be very wrong here - with the counterexample, with my
point computations, or with the FriCAS integrator.

Next I have tried the most simple points from those of order six: the
corresponding two integrals are again non-elementary according to FriCAS
1.3.0. Same for order eight.

Be warned, however, that I never before determined torsion points on an
elliptic curve and that I had to work from scratch because Derive lacks
commands and libraries for elliptic-curve computations.

Martin.

[anti...@math.uni.wroc.pl]

My calculations indicate that points of order 3 correspond to
u^2 = 1 +- 2*sqrt(3)/3. FriCAS says that integal is nonelementary,
so something is wrong. Theory behind example is simple, so
I believe it. I am not sure about points, but this is probably
correct. So it remains to check FriCAS :(

--
Waldek Hebisch

[clicl...@freenet.de]

anti...@math.uni.wroc.pl schrieb:

A simple theory should allow to read off simple antiderivatives for the
order-3 integrands.

I suppose you have tried the integral on Axiom as well - the problem
would have to be quite old then.

The points of order 3, 6 and 8 determined by me correspond to the
following three pairs of integrals:

INT(x/((3*x^2 + 2*SQRT(2) - 3)*SQRT(x^3 - x)), x) = ?

INT(x/((3*x^2 - 2*SQRT(2) - 3)*SQRT(x^3 - x)), x) = ?

INT(x/((x^2 + 2*SQRT(2) + 3)*SQRT(x^3 - x)), x) = ?

INT(x/((x^2 - 2*SQRT(2) + 3)*SQRT(x^3 - x)), x) = ?

INT(x/((x^2 + 2*SQRT(10*SQRT(2) + 14) + 4*SQRT(2) + 5)*SQRT(x^3 - x)),
x) = ?

INT(x/((x^2 - 2*SQRT(10*SQRT(2) + 14) + 4*SQRT(2) + 5)*SQRT(x^3 - x)),
x) = ?

So your result for order 3 is confirmed. I derived these x^2 - u^2 from
a recursive definition of the division polynomials and then checked the
points [u,v] by iterating the group operation.

I should mention that my statements about Goursat integrability referred
to Moebius mappings realizing the dihedral group D_2 (isomorphic to the
Klein four-group K_4) only; the special nature of the radicand x^3 - x
may open other possibilities (thus, x <-> 1/x swaps two roots and
preserves the remaining two). Compare Goursat pp. 113-118 for x^3 - 1.

Martin.

[clicl...@freenet.de]

clicl...@freenet.de schrieb:
>
> anti...@math.uni.wroc.pl schrieb:

Actually, Goursat considered the special radicand x^3 - x as well (on
pp. 118-119) and concludes that no special pseudo-elliptic cases arise.
I tend to believe him.

The substitution x <-> 1/x takes the integral into itself, with u
replaced by 1/u. Thus my pair of order-6 integrals is equivalent to the
order-3 one.

Meanwhile I can confirm that the order-3 integrals are elementary. The
antiderivatives take less than 1000 Bytes to write down.

Martin.

[Richard Fateman]

There are a few points that I think are worth mentioning.

1. The Risch/ etc/ methods determine algebraic anti-derivatives.
It is a bit of a stretch sometimes to identify them with functions
with certain properties. It is typically possible to multiply or add
or otherwise muck around with these functions by, for example, use
of delta or step functions. Or adding strange constants.
The results of a subsequent differentiation need not be affected.

2. Either we are dealing with functions of a single variable (e.g. x)
or multiple variables / parameterized or multidimensional integral.

a. If multiple variables, the notion of a singularity becomes much
more complicated, and insisting on a continuous function much more
hazardous. Try to find useful theorems about what amounts to
functions of several complex variables. Not too many that I have found.

b. If a single variable, you are presumably being presented with a
function that is computable and continuous [yeah, well some version of
continuous for some version of integration] within the limits of
integration (yes, I know you might not know the limits. But you really
have a lot of nerve asking for the integral of a function you are not
willing to define adequately between the limits of interest.)
Continuing on this -- a continuous function of the kind being discussed
here can almost always be integrated by numerical methods. That is
given f(x), excellent methods exist to produce a program F(a,b)
which returns the integral of f from a to b (where a and b are
numerical constants).
Arbitrarily high precision methods are available, as are error
bounds. Chance of being fooled very low.

These methods avoid the problems encountered with symbolic methods which
include (i) the uselessness of an implicit proof that there is no
elementary expression for the antiderivative or (ii) there may be one
but we can't tell for sure because there is a bug in our complicated
program or (iii) because the procedure requires a sub-algorithm that is
not computable [zero equivalence] we can't say for sure about (i) or (ii).

3. You might argue (certainly I have) that symbolic results display
more information than (say) a table of numbers for various a,b. Yet
if the result is going to be run through a plotting program, not so
convincing. A partial symbolic result can be obtained by doing a
numerical-partial-fraction decomposition of some expressions --
any denominator that looks like a polynomial in one variable with
coefficients that can be resolved to floating-point numbers can be
factored into a product of linear factors, thereby requiring only
integration of <numerator stuff>/ (x-r)^n.


4. You might argue that you need the results for a high-dimension
multiple integration (calculation of Feynman diagrams was a major
selling point of integration in the Reduce system). Eh, then you
have multiple variables, but given limits, I think.

Now if you want to posit a problem that is to find an antiderivative
that has the fewest singularities, that may be useful. Another challenge
is to find an antiderivative that is, by some data-structure complexity
measure, "the simplest". This seems to be the objective of Rubi.

These problems are interesting in a computer-sciency computer algebra
systems algebraic-geometry context.

I'm not aware of any current clamor from actual or potential users of
computer algebra systems for solution of these problems. Are there
any Feynman diagram people still out there?

I'm not saying that Bronstein's work, or the programmers attempting to
solve the problems in this thread are "wrong", just that the context and
relevance to (say) scientific computation is easy to misconstrue.

Cheers.
RJF

On 1/31/2017 8:39 AM, clicl...@freenet.de wrote:
>
> clicl...@freenet.de schrieb:
>>
>> anti...@math.uni.wroc.pl schrieb:
>>>
>>> My calculations indicate that points of order 3 correspond to
>>> u^2 = 1 +- 2*sqrt(3)/3. FriCAS says that integal is nonelementary,

>>> so something is wrong...

[oldk...@gmail.com]

> Actually, Goursat considered the special radicand x^3 - x as well (on
> pp. 118-119) and concludes that no special pseudo-elliptic cases arise.
> I tend to believe him.

Hello Martin, can you point out which publication of Goursat are you
talking about?

[oldk...@gmail.com]

On Wednesday, February 1, 2017 at 7:26:17 AM UTC+8, Richard Fateman wrote:
> There are a few points that I think are worth mentioning.
>
> 1. The Risch/ etc/ methods determine algebraic anti-derivatives.
> It is a bit of a stretch sometimes to identify them with functions
> with certain properties. It is typically possible to multiply or add
> or otherwise muck around with these functions by, for example, use
> of delta or step functions. Or adding strange constants.
> The results of a subsequent differentiation need not be affected.

For rational functions integration, there exists algorithms that
produce continuous anti-derivatives. It's fairly simple, I see no
reason not to implement it. As for other kinds of integration,
I don't think there's an algorithm that always works, but I think
heuristics can solve some of them.

> b. If a single variable, you are presumably being presented with a
> function that is computable and continuous [yeah, well some version of
> continuous for some version of integration] within the limits of
> integration (yes, I know you might not know the limits. But you really
> have a lot of nerve asking for the integral of a function you are not
> willing to define adequately between the limits of interest.)
> Continuing on this -- a continuous function of the kind being discussed
> here can almost always be integrated by numerical methods. That is
> given f(x), excellent methods exist to produce a program F(a,b)
> which returns the integral of f from a to b (where a and b are
> numerical constants).
> Arbitrarily high precision methods are available, as are error
> bounds. Chance of being fooled very low.

There are problems with numeric methods too, for example
if the integrand includes variables, then numeric integration
must compute over and over again for these variables.
Another one is precision, zero is zero, no matter how many
digits are computed, you can't know if it's really zero or just
a small number.

> 3. You might argue (certainly I have) that symbolic results display
> more information than (say) a table of numbers for various a,b. Yet
> if the result is going to be run through a plotting program, not so
> convincing. A partial symbolic result can be obtained by doing a
> numerical-partial-fraction decomposition of some expressions --
> any denominator that looks like a polynomial in one variable with
> coefficients that can be resolved to floating-point numbers can be
> factored into a product of linear factors, thereby requiring only
> integration of <numerator stuff>/ (x-r)^n.

If the integrand contains variables, then a symbolic result will
better than a plot (you can't draw a 4D function).

> I'm not saying that Bronstein's work, or the programmers attempting to
> solve the problems in this thread are "wrong", just that the context and
> relevance to (say) scientific computation is easy to misconstrue.
>
> Cheers.
> RJF

I think symbolic integration is also full of fun.

Cheers.

[clicl...@freenet.de]

oldk...@gmail.com schrieb:

Edouard Goursat, Note sur quelques intégrales pseudo-elliptiques,
Bulletin de la Société Mathématique de France 15 (1887), 106-120,
on-line at:

<http://www.numdam.org/item?id=BSMF_1887__15__106_1>

Practically forgotten. Straightforward to implement in rule-based
integrators. Covers all pseudo-elliptic integrands that matter in
practice. Can be extended to cube roots.

Martin.

[anti...@math.uni.wroc.pl]

clicl...@freenet.de wrote:
>
> anti...@math.uni.wroc.pl schrieb:

> >
> > clicl...@freenet.de wrote:
> > > I have now also looked into the elliptic-curve aspect of this
> > > counterexample integral.
> > >
> > > The three Goursat cases do indeed correspond to the points of order
> > > four. I have also determined the points of order three and discovered
> > > that FriCAS 1.3.0 returns the associated pair of integrals unevaluated.
> > > Something must be very wrong here - with the counterexample, with my
> > > point computations, or with the FriCAS integrator.
> >
> > My calculations indicate that points of order 3 correspond to
> > u^2 = 1 +- 2*sqrt(3)/3. FriCAS says that integal is nonelementary,
> > so something is wrong. Theory behind example is simple, so
> > I believe it. I am not sure about points, but this is probably
> > correct. So it remains to check FriCAS :(
> >
>
> A simple theory should allow to read off simple antiderivatives for the
> order-3 integrands.

It allows to read of antiderivatives. Concerning simple:
I have less practice in hand calculations than say Gauss
so I am not eager to them by hand, but in principle this
is doable. Currently FriCAS thinks that point are
of infinite order, so probably something is wrong
with FriCAS.

> I suppose you have tried the integral on Axiom as well - the problem
> would have to be quite old then.

It makes no sense: due to known bugs Axiom has no chance
to do them.

> The points of order 3, 6 and 8 determined by me correspond to the
> following three pairs of integrals:
>
> INT(x/((3*x^2 + 2*SQRT(2) - 3)*SQRT(x^3 - x)), x) = ?
>
> INT(x/((3*x^2 - 2*SQRT(2) - 3)*SQRT(x^3 - x)), x) = ?
>
> INT(x/((x^2 + 2*SQRT(2) + 3)*SQRT(x^3 - x)), x) = ?
>
> INT(x/((x^2 - 2*SQRT(2) + 3)*SQRT(x^3 - x)), x) = ?
>
> INT(x/((x^2 + 2*SQRT(10*SQRT(2) + 14) + 4*SQRT(2) + 5)*SQRT(x^3 - x)),
> x) = ?
>
> INT(x/((x^2 - 2*SQRT(10*SQRT(2) + 14) + 4*SQRT(2) + 5)*SQRT(x^3 - x)),
> x) = ?
>
> So your result for order 3 is confirmed. I derived these x^2 - u^2 from
> a recursive definition of the division polynomials and then checked the
> points [u,v] by iterating the group operation.

Points of order 3 are special: here second derivative of defining
function vanishes:

(1) -> f := sqrt(x^3 - x)

+------+
| 3
(1) \|x - x
Type: Expression(Integer)
(2) -> D(f, x, 2)

4 2
3x - 6x - 1
(2) -------------------
+------+
3 | 3
(4x - 4x)\|x - x
Type: Expression(Integer)
(3) -> radicalSolve(numer(%)::Expression(Integer)::Polynomial(Integer))

(3)
+-----------+ +-----------+ +---------+ +---------+
| +-+ | +-+ | +-+ | +-+
\|- 2\|3 + 3 \|- 2\|3 + 3 \|2\|3 + 3 \|2\|3 + 3
[x = --------------,x = - --------------,x = ------------,x = - ------------]
+-+ +-+ +-+ +-+
\|3 \|3 \|3 \|3
Type: List(Equation(Expression(Integer)))

I am not aware of comparable simple method for different orders.

> I should mention that my statements about Goursat integrability referred
> to Moebius mappings realizing the dihedral group D_2 (isomorphic to the
> Klein four-group K_4) only; the special nature of the radicand x^3 - x
> may open other possibilities (thus, x <-> 1/x swaps two roots and
> preserves the remaining two). Compare Goursat pp. 113-118 for x^3 - 1.
>
> Martin.

--
Waldek Hebisch

[anti...@math.uni.wroc.pl]

Hmm, you checked that for order 3 one gets special case, Goursat
says that there are none and you believe Goursat? I do not
understand.

> Meanwhile I can confirm that the order-3 integrals are elementary. The
> antiderivatives take less than 1000 Bytes to write down.
>
> Martin.

--
Waldek Hebisch

[clicl...@freenet.de]

anti...@math.uni.wroc.pl schrieb:

>
> clicl...@freenet.de wrote:
> >
> > anti...@math.uni.wroc.pl schrieb:
> > >
> > > clicl...@freenet.de wrote:
> > > >
> > > > I have now also looked into the elliptic-curve aspect of this
> > > > counterexample integral.
> > > >
> > > > The three Goursat cases do indeed correspond to the points of order
> > > > four. I have also determined the points of order three and discovered
> > > > that FriCAS 1.3.0 returns the associated pair of integrals unevaluated.
> > > > Something must be very wrong here - with the counterexample, with my
> > > > point computations, or with the FriCAS integrator.
> > >
> > > My calculations indicate that points of order 3 correspond to
> > > u^2 = 1 +- 2*sqrt(3)/3. FriCAS says that integal is nonelementary,
> > > so something is wrong. Theory behind example is simple, so
> > > I believe it. I am not sure about points, but this is probably
> > > correct. So it remains to check FriCAS :(
> > >
> >
> > A simple theory should allow to read off simple antiderivatives for
> > the order-3 integrands.
>
> It allows to read of antiderivatives. Concerning simple:
> I have less practice in hand calculations than say Gauss
> so I am not eager to them by hand, but in principle this
> is doable. Currently FriCAS thinks that point are
> of infinite order, so probably something is wrong
> with FriCAS.

There can be no doubt that something is wrong with FriCAS since Gauss
has provided me with a hand-written finite elementary evaluation of one
order-3 integral. And I find his evaluation to hold up.

>
> > I suppose you have tried the integral on Axiom as well - the problem
> > would have to be quite old then.
>
> It makes no sense: due to known bugs Axiom has no chance
> to do them.
>

Long live FriCAS!

Thanks for the details. As noted above, the special denominators x^2 -
u^2 appears as factors of the so-called division polynomials for the
elliptic curve v^2 = u^3 - u:

divpol(3, x, 0, -1, 0)

3*x^4 - 6*x^2 - 1

1/3*(3*x^2 + 2*SQRT(3) - 3)*(3*x^2 - 2*SQRT(3) - 3)

divpol(8, x, 0, -1, 0)

8*(x^6 - 5*x^4 - 5*x^2 + 1)*(x^24 - 68*x^22 - 1694*x^20 + 3276*x^18
- 19601*x^16 + 63352*x^14 - 86436*x^12 + 63352*x^10 - 19601*x^8 +
3276*x^6 - 1694*x^4 - 68*x^2 + 1)*SQRT(x^3 - x)

8*(x^2 + 1)*(x^2 + 2*SQRT(2) - 3)*(x^2 - 2*SQRT(2) - 3)*(x^2 +
2*SQRT(10*SQRT(2) + 14) + 4*SQRT(2) + 5)*(x^2 - 2*SQRT(10*SQRT(2) +
14) + 4*SQRT(2) + 5)*(x^2 + 2*SQRT(41*SQRT(2) + 58) +
4*SQRT(10*SQRT(2) + 14) - 6*2^(3/4) - 8*SQRT(2) - 10*2^(1/4) -
11)*(x^2 + 2*SQRT(41*SQRT(2) + 58) - 4*SQRT(10*SQRT(2) + 14) +
6*2^(3/4) - 8*SQRT(2) + 10*2^(1/4) - 11)*(x^2 - 2*SQRT(41*SQRT(2) +
58) + 4*SQRT(10*SQRT(2) + 14) + 6*2^(3/4) - 8*SQRT(2) + 10*2^(1/4) -
11)*(x^2 - 2*SQRT(41*SQRT(2) + 58) - 4*SQRT(10*SQRT(2) + 14) -
6*2^(3/4) - 8*SQRT(2) - 10*2^(1/4) - 11)*(x^4 + 2*x^2*(5 - 4*SQRT(2))
+ 1)*(x^8 + 4*x^6*(8*SQRT(2) - 11) + 2*x^4*(51 - 32*SQRT(2)) +
4*x^2*(8*SQRT(2) - 11) + 1)*SQRT(x^3 - x)

Ugh. Note that the order-4 factors are repeated for order 8.

Martin.

[clicl...@freenet.de]

anti...@math.uni.wroc.pl schrieb:
>
> clicl...@freenet.de wrote:
> >
> > clicl...@freenet.de schrieb:
> > >

> > > I should mention that my statements about Goursat integrability
> > > referred to Moebius mappings realizing the dihedral group D_2
> > > (isomorphic to the Klein four-group K_4) only; the special nature
> > > of the radicand x^3 - x may open other possibilities (thus, x <->
> > > 1/x swaps two roots and preserves the remaining two). Compare
> > > Goursat pp. 113-118 for x^3 - 1.
> > >
> >
> > Actually, Goursat considered the special radicand x^3 - x as well
> > (on pp. 118-119) and concludes that no special pseudo-elliptic cases
> > arise. I tend to believe him.
>
> Hmm, you checked that for order 3 one gets special case, Goursat
> says that there are none and you believe Goursat? I do not
> understand.
>

Goursat claims ("... ne fournissent pas d'intégrales pseudo-elliptiques
nouvelles") that for the special radicand x^3 - x his method of Moebius
mapping cannot detect pseudo-elliptic integrands beyond those already
found from equation (5) on p. 111 of his paper.

For x^3 - 1, however, the situation is different (pp. 113-118).

Martin.

[anti...@math.uni.wroc.pl]

clicl...@freenet.de wrote:
>
> There can be no doubt that something is wrong with FriCAS since Gauss
> has provided me with a hand-written finite elementary evaluation of one
> order-3 integral. And I find his evaluation to hold up.

<snip>

> > > The points of order 3, 6 and 8 determined by me correspond to the
> > > following three pairs of integrals:
> > >
> > > INT(x/((3*x^2 + 2*SQRT(2) - 3)*SQRT(x^3 - x)), x) = ?
> > >
> > > INT(x/((3*x^2 - 2*SQRT(2) - 3)*SQRT(x^3 - x)), x) = ?
> > >
> > > INT(x/((x^2 + 2*SQRT(2) + 3)*SQRT(x^3 - x)), x) = ?
> > >
> > > INT(x/((x^2 - 2*SQRT(2) + 3)*SQRT(x^3 - x)), x) = ?
> > >
> > > INT(x/((x^2 + 2*SQRT(10*SQRT(2) + 14) + 4*SQRT(2) + 5)*SQRT(x^3 - x)),
> > > x) = ?
> > >
> > > INT(x/((x^2 - 2*SQRT(10*SQRT(2) + 14) + 4*SQRT(2) + 5)*SQRT(x^3 - x)),
> > > x) = ?

FriCAS had a silly bug due to which it treated correctly computed
integral as nonelementary. For finding the bug it did not help
that point that you gave in integral for order 3 and 6 were
wrong (you wrote SQRT(2) while SQRT(3) is correct).

> Thanks for the details. As noted above, the special denominators x^2 -
> u^2 appears as factors of the so-called division polynomials for the
> elliptic curve v^2 = u^3 - u:

Using division polynomials I have found points of order 5,
one corresponds to u^2 = (1 + 2*sqrt(-1))/5. FriCAS have
now computed integrals for orders 3, 5, 6, 8. The results
are rather lengthy, so instead of posting them here I have
put them at:

http://www.math.uni.wroc.pl/~hebisch/fricas/p3

(3 above means order 3, replace 3 by 5, 6, 8 for higher order).

--
Waldek Hebisch

[clicl...@freenet.de]

anti...@math.uni.wroc.pl schrieb:

Oops. I am sorry, the change of SQRT(3) into SQRT(2) was unintentional.
When I copy expressions from Derive, such roots consist of two
characters looking like "V3": one non-ASCII square-root character
immediately followed by the ASCII integer. In the above, I regularized
them manually to SQRT(2), unthinkingly mistaking "3" for "2", probably
doing it once and then using copy-and-paste. (The alternative is to
extract expressions from session files stored on disk; they are regular
but consist of character blocks lacking spaces and exhibiting arbitrary
line-breaks preceded by "~".)

For comparison, here are my direct and factored division polynomials for
orders 5,6,7:

divpol(5, x, 0, -1, 0)

5*x^12 - 62*x^10 - 105*x^8 + 300*x^6 - 125*x^4 + 50*x^2 + 1

(x^2 + 2*SQRT(2*SQRT(5) + 5) - 2*SQRT(5) - 3)*
(x^2 - 2*SQRT(2*SQRT(5) + 5) - 2*SQRT(5) - 3)*
(x^2 + 2*SQRT(5 - 2*SQRT(5)) + 2*SQRT(5) - 3)*
(x^2 - 2*SQRT(5 - 2*SQRT(5)) + 2*SQRT(5) - 3)*(5*x^4 - 2*x^2 + 1)

divpol(6, x, 0, -1, 0)

2*(x^12 - 22*x^10 - 165*x^8 + 92*x^6 - 185*x^4 + 90*x^2 - 3)*(3*x^4 -
6*x^2 - 1)*SQRT(x^3 - x)

2*(x^2 + 2*SQRT(3) + 3)*(x^2 - 2*SQRT(3) + 3)*
(x^2 + 2*SQRT(2)*3^(3/4) - 4*SQRT(3) + 4*12^(1/4) - 7)*
(x^2 - 2*SQRT(2)*3^(3/4) - 4*SQRT(3) - 4*12^(1/4) - 7)*
(x^4 + 2*x^2*(4*SQRT(3) - 7) + 1)*(3*x^4 - 6*x^2 - 1)*SQRT(x^3 - x)

divpol(7, x, 0, -1, 0)

7*x^24 - 308*x^22 - 2954*x^20 + 19852*x^18 - 35231*x^16
+ 82264*x^14 - 111916*x^12 + 42168*x^10 + 15673*x^8
- 14756*x^6 + 1302*x^4 - 196*x^2 - 1

The last one exceeds my factorization capabilities. And here is the
order-3 antiderivative provided by Gauss:

INT(x/((3*x^2 + 2*SQRT(3) - 3)*SQRT(x^3 - x)), x) =
12^(3/8)*SQRT(SQRT(3) + 1)/36*ATANH(SQRT(SQRT(3) + 1)*(SQRT(2)*3^(3/4)
*x^3 + 3*(3 - SQRT(3))*x^2 - SQRT(2)*3^(3/4)*x + 3*SQRT(3) - 5)
/(12^(3/8)*(SQRT(2)*3^(3/4)*x - SQRT(3) + 1)*SQRT(x^3 - x))) +
12^(3/8)*SQRT(SQRT(3) + 1)/36*ATAN(SQRT(SQRT(3) + 1)*(SQRT(2)*3^(3/4)
*x^3 + 3*(SQRT(3) - 3)*x^2 - SQRT(2)*3^(3/4)*x - 3*SQRT(3) + 5)
/(12^(3/8)*(SQRT(2)*3^(3/4)*x + SQRT(3) - 1)*SQRT(x^3 - x)))

Martin.

[anti...@math.uni.wroc.pl]

clicl...@freenet.de wrote:
>
> divpol(7, x, 0, -1, 0)
>
> 7*x^24 - 308*x^22 - 2954*x^20 + 19852*x^18 - 35231*x^16
> + 82264*x^14 - 111916*x^12 + 42168*x^10 + 15673*x^8
> - 14756*x^6 + 1302*x^4 - 196*x^2 - 1
>
> The last one exceeds my factorization capabilities.

This one is irreducible. One possible u = x^2 in terms
of radicals is below:

-1
*
+---+ +-+ +-+ +---+ +-+
((- 13\|- 1 \|3 + 9)\|7 - 35\|- 1 \|3 + 21)
*
+---------------------------------------------------+2
3| +---+ +-+ +-+ +---+ +-+
\|(1524\|- 1 \|3 + 3196)\|7 - 4032\|- 1 \|3 - 8456
+
+---+ +-+
(- 42\|- 1 \|3 + 42)
*
+---------------------------------------------------+
3| +---+ +-+ +-+ +---+ +-+
\|(1524\|- 1 \|3 + 3196)\|7 - 4032\|- 1 \|3 - 8456
+
+-+
- 336\|7 + 924
/
126

--
Waldek Hebisch

[clicl...@freenet.de]

clicl...@freenet.de schrieb:

>
> A state-of-the-art implementation of a Risch integrator
>
> )version
>
> Value = "FriCAS 1.3.0 compiled at Thu Sep 1 17:01:37 UTC 2016"
>
> responds to
>

> integrate((1 + x)/((1 + x + x^2)*(a + b*x^3)^(1/3)), x)
>

> with
>
> >> Error detected within library code:
> catdef: division by zero
>

Meanwhile, the FriCAS version has advanced to 1.3.2, the web interface
is running version 1.3.1, and the division by zero no longer occurs when
the integral is submitted to the web interface. Its computation,
however, exceeds the 5-minute timeout imposed by the interface (Proxy
Error - Reason: Error reading from remote server). Does FriCAS now
manage to return a correct antiderivative eventually?

Martin.

[clicl...@freenet.de]

clicl...@freenet.de schrieb:

Oh my - has FriCAS been chewing on this integral for two weeks already?

Martin.

[Валерий Заподовников]

Okay, why does the case u=i returns nonelementary
result that has weierstrassPInverse(4, 0, x) on latest
HEAD of master?

Also I cannot get these results on latest HEAD of
master I compiled today.
http://www.math.uni.wroc.pl/~hebisch/fricas/p3
not even talking about crazy
http://www.math.uni.wroc.pl/~hebisch/fricas/p5
http://www.math.uni.wroc.pl/~hebisch/fricas/p6
http://www.math.uni.wroc.pl/~hebisch/fricas/p8

This looks like a regression from 1.3.1!

Also, Masser and Zannier published very nice one

integrate(x/(x^2-1/5-2*%i/5)/(x^3-x)^(1/2), x)

It does not work, timeouts after 8 hours and looks
like even crashes because it exists (no warnings) as
if )quit happened.

[nob...@nowhere.invalid]

??????? ???????????? schrieb:

>
> Okay, why does the case u=i returns nonelementary
> result that has weierstrassPInverse(4, 0, x) on latest
> HEAD of master?

Good grief! However:

integrate(x/(x^2+1)/(x^3-x)^(1/2), x)

still works on the web interface running version 1.3.7, the
instantaneous result being:

(log(((4*x^2+8*x+(-4))*(x^3+(-1)*x)^(1/2)+(x^4+8*x^3+2*x^2+(-8)*x+1))
/(x^4+2*x^2+1))
+2*atan(((x^2+(-2)*x+(-1))*(x^3+(-1)*x)^(1/2))/(2*x^3+(-2)*x)))/8

which is reasonably compact. As mentioned earlier in this thread, it
reduces to (in Derive notation):

1/2*ATANH((x - 1)/SQRT(x^3 - x)) - 1/2*ATAN((x + 1)/SQRT(x^3 - x))

>

> Also I cannot get these results on latest HEAD of
> master I compiled today.
> http://www.math.uni.wroc.pl/~hebisch/fricas/p3
> not even talking about crazy
> http://www.math.uni.wroc.pl/~hebisch/fricas/p5
> http://www.math.uni.wroc.pl/~hebisch/fricas/p6
> http://www.math.uni.wroc.pl/~hebisch/fricas/p8
>
> This looks like a regression from 1.3.1!
>
> Also, Masser and Zannier published very nice one
>
> integrate(x/(x^2-1/5-2*%i/5)/(x^3-x)^(1/2), x)
>
> It does not work, timeouts after 8 hours and looks
> like even crashes because it exists (no warnings) as
> if )quit happened.

I fear that the "master" branch you are using must be regarded a work
in progress. One should perhaps better stick with version 1.3.7 until
an official 1.3.8 arrives.

Martin.