Reals sets consisting of intervals and isolated points

[ares]

Finite unions of open/closed/semi-closed subsets of the real line, for example

    sage: RealSet(0,2) + RealSet.unbounded_above_closed(10)
    (0, 2) + [10, +Infinity)

This ticket also encountered a number of bugs in the comparison of infinity with various field elements like

sage: RLF(0) < oo
False

These are now also fixed and extensive doctests were added.

[kcrisman]

Patch?

[ares]

Replying to kcrisman:

Patch?

uploaded

[vbraun]

Initial patch

[vbraun]

I'm taking over this ticket since I need this for piecewise functions. I'm not sure what happened with the originally proposed patch, but what was attached here is not the actual code.

[kcrisman]

Is + what we're looking for here? Maybe something like u or U? Just worried about the difference between this "sum" and the Minkowski sum (which is, in fact, already in Sage).

In fact, maybe these should inherit from something related to that... probably not, but just raising the possibility.

How do I get more exotic sets like the union of 1/n for positive integer n? ;-)

[novoselt]

It think it is better to stick to the category of finite unions of intervals and points, then with functions defined on such sets and their periodic extensions (like 1 on [0, 1], 0 on (1,2), then extend periodically in one or both directions to get square wave).

Things with infinite unions lead to accumulation points and cannot really be handled in a uniform way, I suspect.

[kcrisman]

Yes, I was being silly :)

[ares]

Patch for realsets.py

[ares]

I just attached the original patch. I did not notice before that the initial patch was not correctly uploaded, I am very sorry for that.

[vbraun]

Updated patch

[vbraun]

I've added the authors to my patch and incorporated any methods that made sense to me. Ares, since your patch would take a bit of work to make use of the Sage class hierarchy and since docstrings are not quite according to Sage specs I propose that we base the implementation on what I have currently posted. The imho only thing left is to decide what to do with the toGf method. Which is some third-party code, I suppose. Maybe you can explain what it is for? If you think it should go into Sage we could turn it into a underscore method.

[ares]

Replying to vbraun:

I've added the authors to my patch and incorporated any methods that made sense to me. Ares, since your patch would take a bit of work to make use of the Sage class hierarchy and since docstrings are not quite according to Sage specs I propose that we base the implementation on what I have currently posted. The imho only thing left is to decide what to do with the toGf method. Which is some third-party code, I suppose. Maybe you can explain what it is for? If you think it should go into Sage we could turn it into a underscore method.

We will move the toGf method into another paquet, since we use it to support our MOLTO project demo (D6.2.pdf) and it is not directly related to realsets.

[rws]

Looks and tests fine. I've fixed some typos and added the module to the reference manual.

---

New commits:

​308d16b	Implement RealSet - finite unions of open/closed/semi-closed subsets of the real line.
​a861752	Further improvements to RealSet
​15ef91c	Trac #13125: reviewer's patch: fix typos, add module to set refman

[vbraun]

Fails on OSX:

sage -t --long src/sage/sets/real_set.py
**********************************************************************
File "src/sage/sets/real_set.py", line 1156, in sage.sets.real_set.RealSet.intersection
Failed example:
    s1.intersection(s2)
Expected:
    (1, 2)
Got:
    (-oo, -10] + (1, 2)
**********************************************************************
File "src/sage/sets/real_set.py", line 1158, in sage.sets.real_set.RealSet.intersection
Failed example:
    s1 & s2    # syntactic sugar
Expected:
    (1, 2)
Got:
    (-oo, -10] + (1, 2)
**********************************************************************
1 item had failures:
   2 of  11 in sage.sets.real_set.RealSet.intersection
    [191 tests, 2 failures, 0.14 s]

[vbraun]

In fact, only fails on OSX 10.9.2 but works on 10.6... weird.

[saludes]

It fails in OSX 10.7.5 too. The error seems to be in the comparation involving one sage.rings.real_lazy.LazyWrapper instance:

sage: s1 = RealSet(0,2) + RealSet.unbounded_above_closed(10);  s1
(0, 2) + [10, +oo)
sage: s2 = RealSet(1,3) + RealSet.unbounded_below_closed(-10);  s2
(-oo, -10] + (1, 3)
sage: s1.intersection(s2)
(-oo, -10] + (1, 2)

Not right. Look at the intersection of the first intervals:

sage: i1 = s1._intervals[0]; i1
(0, 2)
sage: i2 = s2._intervals[0]; i2
(-oo, -10]
sage: i1.intersection(i2)
(-oo, -10]

Wrong. Compare the bounds:

sage: (i1._lower, i2._lower)
(0, -Infinity)
sage: cmp(i1._lower, i2._lower)
-1
sage: i1._lower < i2._lower
True

It doesn't fail for floats or integers:

sage: 0.0 < i2._lower
False
sage: type(i1._lower), type(i2._lower)
(sage.rings.real_lazy.LazyWrapper, sage.rings.infinity.MinusInfinity)

[rws]

Confirm different (correct) behaviour on Linux:

...
sage: s1.intersection(s2)
(1, 2)
...
sage: i1.intersection(i2)
(0, 0)
...
sage: cmp(i1._lower, i2._lower)
1
sage: i1._lower < i2._lower
False

[saludes]

More specifically, it seems to fail only when comparing to zero (OSX 10.7.5):

sage: filter(lambda x: RLF(x) < -oo, range(-10,10))
[0]
sage: filter(lambda x: RLF(float(x)/3) < -oo, range(-10,10))
[0]

and +oo is not affected:

sage: filter(lambda x: RLF(x) >= oo, range(-10,10))
[]

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​d7e2c53

Merge branch 'develop' into ticket/13125

[saludes]

Replying to rws: What to do now? Since the problem seems to be related with RLF, should we open a new ticket and redirect this to the new one?

[vbraun]

My guess is that the problem is comparisons with infinity, I noticed some wonky behavior when I wrote the patch. Its tricky to debug since it apparently depends on the position of objects in memory (the fall-back comparison order).

[rws]

Replying to saludes:

Replying to rws: What to do now? Since the problem seems to be related with RLF, should we open a new ticket and redirect this to the new one?

If it happens on OSX only then it cannot be in this patch, so I'll set to positive. Now it depends on if people on OSX can reproduce the problem without this patch or not; by the above reasoning it should be possible. If so, please open a ticket. If not you should wait until this one is in Sage.

[rws]

Um, I just see that the problem code doesn't even need this patch, so I'll go ahead and open that ticket myself.

[rws]

Anything missing for this ticket being accepted?

[vbraun]

Sorry, I wanted to have a look at the changes but haven't had the time yet.

[vbraun]

I've added some tests for comparison with infinity; these need to be fixed before the ticket is usable. One of the gems on my machine is

sage: RLF(0) < oo
False

---

New commits:

​142aa88

add tests for comparison of infinity with other ring elements

[vbraun]

See also #15004

[vbraun]

There was some work in #14045 to fix comparison with float('inf') but didn't go any further.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​e4303ea	fix element constructor of the infinity ring
​fa497ee	handle conversion of RIF into InfinityRing

[tscrim]

I don't like this change:

+        elif isinstance(x, sage.rings.real_mpfi.RealIntervalFieldElement):
+            if x.upper().is_infinity() or x.lower().is_infinity():
                 return self.gen()

since RIF(0, oo) gets turned into infinity (where is very likely to not be):

sage: UnsignedInfinityRing(RIF(2, oo))
Infinity

I think we should follow the usual paradigm for RIF:

sage: RIF(2, 4) == 4
False
sage: RIF(2, 4) <= 4
True
sage: RIF(2, 4) < 4
False
sage: RIF(2) == 2
True

So I would say this is wrong:

sage: RIF(2, oo) == oo
True

and I would raise an error anytime we're converting something which is not directly equal to a (signed) infinity. For example:

sage: UnsignedInfinityRing(RIF(2, oo))
Infinity

should raise an error, but this would be okay:

sage: UnsignedInfinityRing(RIF(oo, oo))
Infinity

[vbraun]

The question is not whether or not you like a pony, but if and how RIF should coerce into the infinity ring. The way Sage works is that everything that should be comparable with infinity can be coerced into the infinity ring, so if you ever compare with infinity the comparison is done there. If you don't have a coercion (e.g. RIF before this ticket) then you will get undesirable answers from the fallback comparison (=memory location).

So if = yes, the only question is how. Semi-infinite intervals can either coerce into infinity, or "less than infinity", or zero (the only elements of the infinity ring). Its pretty clear that anything not infinite is undesirable.

[git]

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

​563a877

also handle conversion of symbolic infinity

[vbraun]

I forgot that SR can also represent infinity and conversion to the infinity ring should work. For SR there is no coercion to the infinity ring since SR wants to handle its own infinities (in fact: the infinity ring coerces into SR).

Arguably that should be changed and SR also coerce into the infinity ring instead of the other way round. But then SR wouldn't be able to react to things like oo * x. Downside of the current way is

sage: bool(SR(-1000) > oo), bool(SR(-1000) < oo)
(False, False)

i.e. SR doesn't know how to decide this rather simple inequality. In any case, thats for another ticket.

[rws]

Merge conflicts.

[git]

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

​cef5700

Merge branch 'develop' into t/13125/ticket/13125

[vbraun]

Fixed

[git]

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

​f96c67e

strip out grant acknowledgement

[vbraun]

I've removed the grant acknowledgement and will put it whereever we agree on in ​https://groups.google.com/d/msg/sage-devel/_NtS2b8W3uo/BsBz6IcLn4cJ

[pbruin]

I'm mostly happy with the fixes related to infinity, although we are nowhere close to fixing all the bugs in #11506. Of the examples listed there, the following one is changed by this ticket:

sage: InfinityRing(CC(oo))
A positive finite number

This used to return +Infinity, which is not perfect either, but is at least consistent with InfinityRing(UnsignedInfinity(oo)). (I'd argue that both of these should probably be undefined, since complex and unsigned infinity are in no way more positive than negative.)

Could you fix the above example to return +Infinity again?

I leave it to someone else to review the new code for real sets. It would have been better if the infinity-related stuff had been done on a separate ticket.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

[vbraun]

Agree that it should be a separate ticket. It just wasn't clear to me in the beginning that things were this messed up. I've split off the fixing-infinity part into #11506

[tscrim]

I let this slip off, sorry Volker. I think there should be no coercion because there is no way to deal with these (semi)infinite intervals. However if we are forced to make this a coercion, then it should be less than infinity since my (very anecdotal) evidence says that most computations won't escape to oo, but instead just don't have a good upper bound.

That being said, I think this should not be positively reviewed as it stands.

Do you think Nils would be a good person to ask about this, someone else, or go directly to sage-devel?

[vbraun]

I've moved all infinity-related commits to #11506, let's move the discussion there.

No coercion means: comparison by memory location.

[tscrim]

Okay, but the branch currently doesn't merge cleanly

[pbruin]

Just to be clear (since Volker set this to positive review after moving the infinity-related stuff to #11506): it wasn't my intention to give a positive review except for that example. I haven't looked at the real sets code at all.

[git]

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

​7b72a42

Merge branch 'develop' into t/13125/real_sets

[pbruin]

OK, I didn't notice that the real sets code had already been reviewed.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:

​e620d38	rm global is_HyperellipticCurve
​1932b64	rm global is_{Expect,Gap,Singular}Element
​3841cc7	rm global is_Finite_Field, is_Finite_FieldElement
​ae72be9	rm global is_Graphics
​f0ac47d	rm global is_ProjectiveSpace
​bd2b01a	rm global is_QuadraticForm
​fa34d62	rm global is_Scheme
​8ad8402	rm global is_Morphism
​b948874	global is_*: delete deprecation warning
​c818746	fix merge conflict with #14329