Recursive call in FractionFieldElement._evaluate_polynomial

[saraedum]

Currently, the following fails:

sage: R.<x> = GF(2)[]
sage: S.<y> = R.fraction_field()[]
sage: (y+1)(R.one())
RuntimeError: maximum recursion depth exceeded while calling a Python object

CC: @mezzarobba @roed314 @xcaruso @sagetrac-swewers

Component: basic arithmetic

Author: Julian Rüth

Branch: b773600

Reviewer: Marc Mezzarobba

Issue created by migration from https://trac.sagemath.org/ticket/25440

[saraedum]

comment:1

What happens here:

• R.one() is coerced into the coefficient ring of y+1, i.e., R.fraction_field()
• The _evaluate_polynomial for fraction field elements is called with self==R.fraction_field()(R.one()) and pol==y+1.

inverse = ~self
if inverse.denominator().is_one():
   num = inverse.numerator()
   return pol.reverse()(num)/num**pol.degree()

• This sets num==R.one() and we're back to square one.

[saraedum]

Branch: u/saraedum/25440

[saraedum]

Commit: 26bf0c2

[saraedum]

comment:3

I had run into a precision problem in the same spot several times before and had never bothered for long enough to track it down. I hope the reviewer doesn't mind that I also fix this while I am at it.

---

New commits:

26bf0c2

Remove recursive call when evaluating polynomials in fractions

[saraedum]

comment:4

I have not run full doctests yet. Let's see what the patchbots think.

[saraedum]

Author: Julian Rüth

[mezzarobba]

comment:5

The first part looks good to me. (Cc:ing the original author of the code just in case.)

Regarding the precision issue, while your fix doesn't hurt as far as I can see, I don't believe foo.is_one() should ever return True when foo is not exactly one... so IMO the real bug is in elements for which that happens.

[fchapoton]

comment:6

mistake here:

+            sage: (y+1)(R.one())
+            sage: 0

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b773600

Fix typo in doctest

[sagetrac-git]

Changed commit from 26bf0c2 to b773600

[saraedum]

comment:8

Replying to @mezzarobba:

The first part looks good to me. (Cc:ing the original author of the code just in case.)

Regarding the precision issue, while your fix doesn't hurt as far as I can see, I don't believe foo.is_one() should ever return True when foo is not exactly one... so IMO the real bug is in elements for which that happens.

I think that's a dilemma of inexact objects and p-adics in particular. Currently, x == 1 and x.is_one() are satisfied by inexact one elements. That comes with its drawbacks, as can be seen in this example. But changing this is probably going to break things in even more places. Also, it's unclear what the alternative would be. Should R(1) != 1? Or should not R(1).is_one() hold? Or just R(1)*p/p != 1? Or should R(1) == 1 raise an exception?

I think there is no good answer here with the operators available in Sage/Python. Whatever you choose, some algorithms are going to break because the assumptions made by the implementation are not met.

[mezzarobba]

comment:9

Replying to @saraedum:

I think that's a dilemma of inexact objects and p-adics in particular.Currently, x == 1 and x.is_one() are satisfied by inexact one elements. That comes with its drawbacks, as can be seen in this example. But changing this is probably going to break things in even more places.

I'm not so sure: intervals have exactly the same issue, but they only declare equal elements that are, and they work reasonably well with the rest of Sage... Really, for me, the way equality of p-adics (and series) appear to work is closer to a bug than an implementation choice.

Also, it's unclear what the alternative would be. Should R(1) != 1?

Ideally yes, but that's a lost battle.

Or should not R(1).is_one() hold?

Probably. Though, if I understand right, (some?) p-adic rings have a maximum precision, and there is an argument for declaring elements equal when they agree to the precision of the parent, or perhaps even to that of the more precise of the two elements.

[saraedum]

comment:10

Replying to @mezzarobba:

Replying to @saraedum:

I think that's a dilemma of inexact objects and p-adics in particular.Currently, x == 1 and x.is_one() are satisfied by inexact one elements. That comes with its drawbacks, as can be seen in this example. But changing this is probably going to break things in even more places.

I'm not so sure: intervals have exactly the same issue, but they only declare equal elements that are, and they work reasonably well with the rest of Sage... Really, for me, the way equality of p-adics (and series) appear to work is closer to a bug than an implementation choice.

It's a valid alternative. Two elements are equal if they are indistinguishable. We have thought about this and it certainly has its merits. But you also have to keep this in mind when implementing generic algorithms. No matter what you do, some assumptions that exact implementations make are going to be violated, e.g., a + b - b == a is not true in RIF.

I am not saying that we should not change the notion of equality in p-adics. I have discussed this with several people in the past and even had a ticket about this at some point. However, it's not clear what's the right notion of equality. The one we have is unfortunate but I am not convinced anymore that there is a better one.

Anyway, while things are the way they are, I'd like to fix this precision issue in Sage. If you are opposed to this, I don't mind at all to take this out of this changeset and propose it on a different ticket and continue the discussion there :)

[mezzarobba]

comment:11

Replying to @saraedum:

But you also have to keep this in mind when implementing generic algorithms. No matter what you do, some assumptions that exact implementations make are going to be violated, e.g., a + b - b == a is not true in RIF.

Yes, of course. And I wholeheartedly agree that Sage is missing finer grained comparison operators. But I thought the (weak) consensus to deal with the situation—not only in the context of intervals, but also, e.g., for method that do their best to answer undecidable questions—was to stick as much as possible to the convention that positive boolean answers must be correct, while negative ones may mean “I don't know”. In any case, that's the convention I try to apply when writing or reviewing generic code where the issue might arise.

Anyway, while things are the way they are, I'd like to fix this precision issue in Sage. If you are opposed to this, I don't mind at all to take this out of this changeset and propose it on a different ticket and continue the discussion there :)

No, I don't really care about that particular change, and I'm happy to keep it in if it can help. I just don't think it will be a sustainable model in the long run.

[mezzarobba]

Reviewer: Marc Mezzarobba

[vbraun]

Changed branch from u/saraedum/25440 to b773600

[mezzarobba]

comment:13

Replying to @mezzarobba:

Regarding the precision issue, while your fix doesn't hurt as far as I can see, I don't believe foo.is_one() should ever return True when foo is not exactly one... so IMO the real bug is in elements for which that happens.

And, at #25318, I'm proposing to remove the doctest you added, because it breaks with the changes in that ticket, and I see no way of making things work both with p-adics and with parents that use what I consider the correct semantics for is_one().

[mezzarobba]

Changed commit from b773600 to none