Opened 4 years ago

Last modified 21 months ago

#26042 needs_work enhancement

Real transcendental extension fields

Reported by: slelievre Owned by:
Priority: major Milestone: sage-wishlist
Component: algebra Keywords: transcendental, field extension
Cc: dimpase, mmarco, vdelecroix, saraedum, slelievre Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues: many tests/examples missing
Branch: u/wphooper/real_transcendental_extension_fields (Commits, GitHub, GitLab) Commit: 4a82da8237254203b4d36ac3498356cde2214edf
Dependencies: Stopgaps:

Status badges

Description (last modified by slelievre)

An often requested feature is to be able to work in say QQ[pi], QQ[e], QQ[e, pi], or similar extensions.

I think Sage should support real transcendental extension fields. It does not as far as I can tell. For example it should support arithmetic and comparisons in Q(e) with e the usual constant e [...]

The problem is that you cannot know if a certain expression involving pi, e and cos(3/4) is zero or not [...]. That means that, for instance, you don't know if you can take its inverse.

I would be happy if there was a way to work with the transcendental extension QQ[pi] where I can assert that an expression is zero.

An implementation is attached to Pat Hooper's 2018-08-08 post on sage-devel.

Change History (27)

comment:1 Changed 4 years ago by slelievre

  • Cc dimpase mmarco vdelecroix added

Not sure what component to set this to: algebra? basic arithmetic? symbolics? or maybe something else?

comment:2 Changed 4 years ago by slelievre

  • Description modified (diff)

comment:3 follow-up: Changed 4 years ago by wphooper

Thanks Samuel for posting this. Two comments:

1) You can't rigorously decide equality in Q(e,pi) because you don't know if Q(e)(pi) is a transcendental extension of Q(e). If this extension is not transcendental, it would mean that in my implementation checking when calling x<y for x,y in Q(e,pi) could enter an infinite loop (in the case where x=y but are represented differently as rational functions in e and pi), but when a result is returned to x<y, then that answer would be rigorous. So, there might still be some point in supporting Q(e,pi)...

2) Defining Q(r) where r is a random number in (say) [0, 1] would be important to me. I'm not sure how many chains of transcendental extensions are known, but I think Sage should support chains involving random numbers at least, e.g., Q(e, r_1, r_2, ...)

comment:4 in reply to: ↑ 3 Changed 4 years ago by vdelecroix

Replying to wphooper:

2) Defining Q(r) where r is a random number in (say) [0, 1] would be important to me.

+1. And even K(r) where K is a (real embedded) number field.

comment:5 Changed 4 years ago by wphooper

  • Branch set to u/wphooper/real_transcendental_extension_fields

comment:6 Changed 4 years ago by vdelecroix

  • Commit set to f62b687b5bce1364903faf85ccba9590c393a9f2

Hi Pat,

You should not be creating NestedIntervalRealSet but use RealLazyField. The latter is far from being perfect, but it is exactly inteded for this purpose.

sage: RLF.pi()
3.141592653589794?
sage: my_pi = RLF.pi()
sage: my_pi.numerical_approx(digits=50)
3.1415926535897932384626433832795028841971693993751
sage: RealIntervalField(100)(my_pi)
3.14159265358979323846264338328?

New commits:

f62b687First commit

comment:7 Changed 4 years ago by wphooper

Hi Vincent,

Thank you. Sure, I'll try to switch to RealLazyField?. I hadn't realized that you could get intervals from RLF.

The other thing I use is FunctionField?. One issue I was having was that it seems not to cancel constants in the numerator and denominator:

sage: K.<x>=FunctionField(QQ)
sage: y = (2*x)/(2*(x+1)); y
2*x/(2*x + 2)
sage: y^2
4*x^2/(4*x^2 + 8*x + 4)

These constants build up when performing the kind of repeated operations I was doing and slow things down a lot. I deal with this by calling ".factor().expand()" on FunctionField? elements at every step, but this also seems slow and I'm not sure if it will work in all fields...

comment:8 Changed 4 years ago by vdelecroix

This will not solve your simplification problem but I wonder why these two are different

sage: QQ['t'].fraction_field()
Fraction Field of Univariate Polynomial Ring in t over Rational Field
sage: FunctionField(QQ, 't')
Rational function field in t over Rational Field

It seems that the second is just a wrapper over the first one

sage: K = FunctionField(QQ, 't')
sage: t = K.gen()
sage: parent(t._x) is QQ['t'].fraction_field()
True
sage: 

Concerning simplification in fraction field, this is a non-trivial matter and you may want to have a look at

If you really want to work with a transcendental extension of QQ then better work with ZZ['x'].fraction_field() that apparently works better with simplification.

comment:9 Changed 4 years ago by git

  • Commit changed from f62b687b5bce1364903faf85ccba9590c393a9f2 to debf39c820b66c64428d1d8df3e71fbbae6d4f36

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

debf39cRewrite using RealLazyField.

comment:10 Changed 4 years ago by wphooper

I switched to RealLazyField. I also created a class (and parent) which represents a lazily computed random number in [0,1] (and created a random_real convenience function).

I did not address the simplifications problem. I'd like to work in the general case at first. Once people are happy with the general case, I think it will be worth doing some optimization when the base is QQ and perhaps also for number fields.

comment:11 Changed 4 years ago by vdelecroix

Hi Pat,

Some random thoughts

  1. It does not make much sense to generate the bits by packets of 53. I know that 53 is the standard mantissa for double floating point, but in the present situation it would be more natural to use 64 bits. (idem in _mpfr_ or _richcmp_)
  1. I don't think that the following is necessary in _coerce_map_from_
    +        if S == self:
    +            return True
    
  1. Why not make the LazyRandomElement an actual element of the real lazy field RLF? It would be better than having the ad-hoc LazyRandomNumberSet_class.

comment:12 Changed 4 years ago by git

  • Commit changed from debf39c820b66c64428d1d8df3e71fbbae6d4f36 to bb2ce193ea22d6bffc18bbab2f7f9d6c619ae63e

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

a7347e8Add support for LazyRandomNumber and RLF.random() to get a random number in [0,1].
bb2ce19Remove random number classes, make use of random numbers added to RLF.

comment:13 Changed 4 years ago by git

  • Commit changed from bb2ce193ea22d6bffc18bbab2f7f9d6c619ae63e to fe54abb47eface212ab114b9f69df5a9610bdb9b

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

fe54abbRemoval of unnecessary lines in _coerce_map_from_

comment:14 follow-ups: Changed 4 years ago by wphooper

Hi Vincent,

  1. I originally wanted to do this, but I ran into trouble with categories. I made changes in this direction, but I'm still having the issue. Namely RLF.random()._test_category() gives an error. It would be great if you could fix or tell me how to fix it.
  1. In LazyRandomNumber I decided to store representations of RealIntervalFields with precision 64*2^k for k=0,1,2,.... Previously, I was doing 53*k. The new use of exponential growth here means that the memory requirements to get a random number of large precision drop from quadratic to linear (and presumably some algorithm times drop as well).
  1. Fixed in second commit above.
  1. I noticed a bug in RealLazyField:
    sage: float(sin(RLF.pi()))
    AttributeError: type object 'float' has no attribute 'pi'
    

The same error appears with RDF replacing float.

I'm thinking we solve issue 3 above, then maybe it makes sense to make RealTranscendentalExtensionField support underlying functions fields such as ZZ['x'].fraction_field(). I wanted to see that people are happy with this scheme before I put more work in.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 4 years ago by vdelecroix

Replying to wphooper:

  1. I noticed a bug in RealLazyField:
    sage: float(sin(RLF.pi()))
    AttributeError: type object 'float' has no attribute 'pi'
    

The same error appears with RDF replacing float.

It is indeed a bug. A new ticket should be open to fix the issue. Note that curiously the following does work

sage: (sin(RLF.pi())).eval(RDF)
1.2246467991473515e-16

comment:16 in reply to: ↑ 15 Changed 4 years ago by wphooper

Replying to vdelecroix:

It is indeed a bug. A new ticket should be open to fix the issue. Note that curiously the following does work

sage: (sin(RLF.pi())).eval(RDF)
1.2246467991473515e-16

I opened a ticket: https://trac.sagemath.org/ticket/26839

comment:17 in reply to: ↑ 14 Changed 4 years ago by vdelecroix

Replying to wphooper:

  1. I originally wanted to do this, but I ran into trouble with categories. I made changes in this direction, but I'm still having the issue. Namely RLF.random()._test_category() gives an error. It would be great if you could fix or tell me how to fix it.

This fails for a very bad reason. One quick fix is to change the declaration

- class LazyRandomNumber(LazyFieldElement):
+ cdef class LazyRandomNumber(LazyFieldElement):

(and you probably want to copy the declaration in real_lazy.pxd)

The reason why it fails is because any element of a parent should also inherit some methods that are defined by the category mechanism (the stuff in sage/categories/). For that machinery to work some extra inheritance construction is done on the fly. But this operates differently on Python classes (without cdef) and Cython classes (with cdef). For clearer explanation, you might want to have a look at Simon King's tutorial.

An alternative way to solve the problem is to call explicitely the inheritance machinery on your Python class... but the quick fix above is probably nicer.

comment:18 Changed 3 years ago by git

  • Commit changed from fe54abb47eface212ab114b9f69df5a9610bdb9b to de1f92d197316edfba1611026da94f6d9b0adce0

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

43fabbaFirst commit
961c60bRewrite using RealLazyField.
580303aAdd support for LazyRandomNumber and RLF.random() to get a random number in [0,1].
26faf3dRemove random number classes, make use of random numbers added to RLF.
58c57f9Removal of unnecessary lines in _coerce_map_from_
de1f92dConvert the LazyRandomNumber class to cython

comment:19 Changed 3 years ago by wphooper

  • Cc saraedum slelievre added

Rebased on 8.9.rc0.

Cythonized LazyRandomNumber so that now RLF.random()._test_category() passes.

comment:20 follow-up: Changed 3 years ago by slelievre

  • Component changed from PLEASE CHANGE to algebra

Setting component to algebra for lack of a better idea.

comment:21 in reply to: ↑ 20 ; follow-up: Changed 3 years ago by dimpase

Replying to slelievre:

Setting component to algebra for lack of a better idea.

Tarski rotating in his grave...

comment:22 Changed 3 years ago by git

  • Commit changed from de1f92d197316edfba1611026da94f6d9b0adce0 to 0e93f2fdb2827c131f26593e1572b9f5467f8e89

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

0e93f2fAdjust to location change of FunctionFieldElement.

comment:23 in reply to: ↑ 21 Changed 3 years ago by slelievre

Replying to dimpase:

Replying to slelievre:

Setting component to algebra for lack of a better idea.

Tarski rotating in his grave...

The "number fields" component might be the closest fit...

comment:24 Changed 3 years ago by git

  • Commit changed from 0e93f2fdb2827c131f26593e1572b9f5467f8e89 to 4a82da8237254203b4d36ac3498356cde2214edf

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

4a82da8Make python3 compatible; Add "long time" doctest comments.

comment:25 Changed 3 years ago by wphooper

  • Status changed from new to needs_review

The issues mentioned in the discussion above all seem resolved now. All tests are passing for me in both python2 and python3 now. Also the cancellation issue mentioned in comment 7 seems to have been resolved by changes in FunctionField.

Changed to "needs review".

(I'm grateful to Samuel Lelièvre for help getting through some issues I was having with cython and compiling sage.)

comment:26 Changed 21 months ago by gh-mjungmath

This is a nice feature!

Unfortunately, most functions miss a test and/or example block.

See here for details.

comment:27 Changed 21 months ago by dimpase

  • Status changed from needs_review to needs_work
  • Work issues set to many tests/examples missing

Indeed, tests/examples should be present for all the public functions. Setting to needs work due to this.

Note: See TracTickets for help on using tickets.