Opened 5 years ago

Closed 4 years ago

#17830 closed enhancement (fixed)

Comparison of number field elements dependent of real embedding

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.10
Component: number fields Keywords: sd66
Cc: tmonteil, jj, sstarosta, gagern, mkoeppe Merged in:
Authors: Vincent Delecroix, Štěpán Starosta Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: d63b7ac (Commits) Commit: d63b7ac784f22fa8245694f31c19f3d3d7616e88
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

Comparison of embedded number field elements should be identical to the comparison of the embedding. In other words, we should have:

sage: x = polygen(ZZ)
sage: K.<cbrt2> = NumberField(x^3 - 2, embedding=AA.polynomial_root(x^3-2, RIF(0,3)))
sage: 6064/4813 < cbrt2 < 90325/71691
True

This has been done in #13213 for quadratic number fields. This ticket aims to implement this for all number fields by storing into the parent a list of interval approximations of the generator.

This concerns only real embeddings.

To go further, one should consider:

  • having a fast evaluation of integer polynomial with real intervals (mpfi elements) input
  • make better interaction with QQbar (see also #18103 and #18104)

Change History (26)

comment:1 Changed 5 years ago by vdelecroix

  • Branch set to u/vdelecroix/17830
  • Commit set to 5f7f57b445adebb118d1d80acb4e930911265494

Working implementation (i.e. all tests pass in sage.rings.number_fields). Needs some speedup and bullet proofs!


New commits:

1fd916ftrac #17830: ordering for real embedded number fields
316dd8etrac #17830: floor/ceil
5f7f57btrac #17830: cleaner import in number_field.py

comment:2 Changed 5 years ago by vdelecroix

  • Description modified (diff)
  • Summary changed from Comparison of number field elements dependent of embedding to Comparison of number field elements dependent of real embedding

comment:3 Changed 5 years ago by sstarosta

  • Cc sstarosta added

comment:4 Changed 5 years ago by vdelecroix

  • Keywords sd66 added

comment:5 Changed 5 years ago by sstarosta

  • Branch changed from u/vdelecroix/17830 to u/sstarosta/17830
  • Commit changed from 5f7f57b445adebb118d1d80acb4e930911265494 to 82f6d09a1f62887d0e5b72b81a8def80edb0d414

I have done some testing and committed a few tweaks done on Sage days 66 + doc improvement.

comment:6 Changed 5 years ago by vdelecroix

I am not sure it is because of your commit, but

sage -t continued_fraction.py  # 1 doctest failed
sage -t polynomial/polynomial_rational_flint.pyx  # 1 doctest failed

comment:7 Changed 5 years ago by vdelecroix

  • Authors changed from Vincent Delecroix to Vincent Delecroix, Štěpán Starosta
  • Branch changed from u/sstarosta/17830 to u/vdelecroix/17830
  • Commit changed from 82f6d09a1f62887d0e5b72b81a8def80edb0d414 to 96ac61e74d5dc073fe6d11570ed0be0934c50c77
  • Status changed from new to needs_review

The two failing doctests come from the introduction of the method _real_mpfi_. I just propose to get rid of it in this ticket. The main reason is that there are a lot of duplication between:

  • AA and QQbar
  • RLF and CLF
  • what is implemented in this ticket for number fields

I propose to clean it up in ticket #18103 and add the _real_mpfi_ feature there.

Vincent


New commits:

d0f6f7bTrac 17830: simpler initialization + TODO
96ac61eTrac 17830: revert the introduction of _real_mpfi_

comment:8 Changed 5 years ago by vdelecroix

  • Cc gagern added
  • Description modified (diff)

comment:9 Changed 5 years ago by git

  • Commit changed from 96ac61e74d5dc073fe6d11570ed0be0934c50c77 to b7ba83a447e1f5cc819b2cb6fa1adfe50fabf826

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

90b4acctrac #17830: ordering for real embedded number fields
ee5a198trac #17830: floor/ceil
ec50d4dtrac #17830: cleaner import in number_field.py
f07dc08trac #17830: doc improvements and small tweaks
b7ba83aTrac 17830: simpler initialization + TODO

comment:10 Changed 5 years ago by vdelecroix

rebase on sage-6.7.beta3

comment:11 Changed 5 years ago by mkoeppe

  • Cc mkoeppe added

comment:12 Changed 5 years ago by git

  • Commit changed from b7ba83a447e1f5cc819b2cb6fa1adfe50fabf826 to a8c294b7188157fb1c168d1eff89ad0c2b200469

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

95f3adatrac #17830: ordering for real embedded number fields
7d0d0c0trac #17830: floor/ceil
2d49517trac #17830: cleaner import in number_field.py
e1efbd6trac #17830: doc improvements and small tweaks
875f756Trac 17830: simpler initialization + TODO
a8c294bTrac #17830: rich_to_bool is no longer a method

comment:13 Changed 5 years ago by vdelecroix

rebased on 6.8.beta6

comment:14 Changed 5 years ago by git

  • Commit changed from a8c294b7188157fb1c168d1eff89ad0c2b200469 to eb50b94345e732b879ab5faf5c8016252a17d60c

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

575b264Trac #18159: add a ._test_cardinality in Sets category
cc87bd5Trac #18159: remove a duplicated test
32c403dTrac #18159: fix cardinality/is_finite in sets/set.py
937ebf4Trac #18159: fix some tests related to TestSuite
eb50b94Trac #18159: fix two parents

comment:15 Changed 5 years ago by git

  • Commit changed from eb50b94345e732b879ab5faf5c8016252a17d60c to a8c294b7188157fb1c168d1eff89ad0c2b200469

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

95f3adatrac #17830: ordering for real embedded number fields
7d0d0c0trac #17830: floor/ceil
2d49517trac #17830: cleaner import in number_field.py
e1efbd6trac #17830: doc improvements and small tweaks
875f756Trac 17830: simpler initialization + TODO
a8c294bTrac #17830: rich_to_bool is no longer a method

comment:16 Changed 5 years ago by vdelecroix

Sorry... I pushed to the wrong ticket. Back to normal.

comment:17 follow-up: Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work
+Decreased doctests rings/number_field/number_field_base.pyx from 11 / 11 = 100% to 12 / 13 = 92%

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

Replying to chapoton:

+Decreased doctests rings/number_field/number_field_base.pyx from 11 / 11 = 100% to 12 / 13 = 92%

Then what? There is no way to test _init_embedding_approx that initialize private attributes. For sure we can duplicate doctests from _get_embedding_approx or even write

TESTS::

    sage: 1 + 1 # indirect doctest
    2

if it makes you happier. But I am not happy with that. If you have any constructive suggestion I would be happy to hear it.

General note: asking for review (= waiting from other people comments) is different from merging into Sage. Patchbot green light concerns the latter.

comment:19 Changed 4 years ago by git

  • Commit changed from a8c294b7188157fb1c168d1eff89ad0c2b200469 to 9313849ee0acdcb799f3f5f40fc0caa342baddc0

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

5b7e757trac #17830: ordering for real embedded number fields
bd7eef0trac #17830: floor/ceil
94b22b6trac #17830: cleaner import in number_field.py
138957atrac #17830: doc improvements and small tweaks
9313849Trac 17830: simpler initialization + TODO

comment:20 Changed 4 years ago by vdelecroix

  • Milestone changed from sage-6.6 to sage-6.10
  • Status changed from needs_work to needs_review

New commits:

5b7e757trac #17830: ordering for real embedded number fields
bd7eef0trac #17830: floor/ceil
94b22b6trac #17830: cleaner import in number_field.py
138957atrac #17830: doc improvements and small tweaks
9313849Trac 17830: simpler initialization + TODO

comment:21 Changed 4 years ago by git

  • Commit changed from 9313849ee0acdcb799f3f5f40fc0caa342baddc0 to c7a50e734790af1f011a5c236542e3b67b2f8aea

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

c7a50e7Trac #17830: add a useless doctest

comment:22 Changed 4 years ago by vbraun

  • Status changed from needs_review to needs_work

Lgtm but merge conflict...

comment:23 Changed 4 years ago by git

  • Commit changed from c7a50e734790af1f011a5c236542e3b67b2f8aea to d63b7ac784f22fa8245694f31c19f3d3d7616e88

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

ff13d1ftrac #17830: ordering for real embedded number fields
c52229dtrac #17830: floor/ceil
8543255trac #17830: cleaner import in number_field.py
c098dc7trac #17830: doc improvements and small tweaks
8bb1031Trac #17830: simpler initialization + TODO
d63b7acTrac #17830: add a useless doctest

comment:24 Changed 4 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Thanks for having a look! Rebased on 7.0.beta1.

Vincent

comment:25 Changed 4 years ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

comment:26 Changed 4 years ago by vbraun

  • Branch changed from u/vdelecroix/17830 to d63b7ac784f22fa8245694f31c19f3d3d7616e88
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.