Opened 6 years ago

Closed 5 years ago

Last modified 5 years ago

#18942 closed defect (fixed)

Weird bug in roots of a polynomial in relative number field extension

Reported by: robharron Owned by:
Priority: major Milestone: sage-7.3
Component: number fields Keywords: Relative number field, roots
Cc: misjafasteinmetz Merged in:
Authors: Kiran Kedlaya Reviewers: Peter Bruin
Report Upstream: N/A Work issues:
Branch: 4c52f08 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description

I have no idea what is going on.

sage: F.<omega> = NumberField(x^2+x+1)
sage: xx = polygen(F)
sage: ABs = []
sage: ps = [p for p, _ in F(7).factor()]
sage: for mu in ps:
    K = F.extension(xx^3 - mu, 'alpha')
    print K.defining_polynomial().roots(K)
sage: for mu in ps:
    K = F.extension(xx^3 - mu, 'alpha')
    print K.defining_polynomial().roots(K)

[(alpha, 1), ((-omega - 1)*alpha, 1), (omega*alpha, 1)]
[(alpha, 1), (omega*alpha, 1), ((-omega - 1)*alpha, 1)]
[]
[(alpha, 1), (omega*alpha, 1), ((-omega - 1)*alpha, 1)]

So, that's weird. But it gets worse! First do this

sage: fbar = xx^3 - ps[0]
sage: Kbar = F.extension(fbar, 'alpha')
sage: fbar.roots(Kbar)
[]

Okay, but then do fbar.roots?? to see the source code, then press 'q' to exit that, then

sage: fbar.roots(Kbar)
[(alpha, 1), ((-omega - 1)*alpha, 1), (omega*alpha, 1)]

Huh?

(I'm doing this is sage 6.7 on the cloud.)

Change History (15)

comment:1 Changed 5 years ago by pbruin

It seems this is caused by the PolynomialRing constructor not distinguishing between relative number fields with different defining polynomials, but with the same absolute polynomials and the same variable names:

sage: F.<omega> = NumberField(x^2 + x + 1)
sage: y = polygen(F)
sage: K = F.extension(y^3 + 3*omega + 2, 'alpha')
sage: L = F.extension(y^3 - 3*omega - 1, 'alpha')
sage: K is L
False
sage: K.absolute_polynomial() == L.absolute_polynomial()
True
sage: K['x'] is L['x']
True

I found this ticket via this sage-nt discussion and suspect the above problem is the cause of both bugs.

comment:2 follow-up: Changed 5 years ago by pbruin

In fact, in the above example we have

sage: K == L
True

which causes a cache lookup in PolynomialRing to return K['x'] when given L as input.

We should probably make number fields satisfy K == L if and only if K is L, i.e. make them inherit from WithEqualityById. Doing this in the most naive way unfortunately leads to a number of doctest failures.

comment:3 Changed 5 years ago by kedlaya

I like this theory, but it seems like it would be more consistent with this output:

[(alpha, 1), ((-omega - 1)*alpha, 1), (omega*alpha, 1)]
[]
[(alpha, 1), ((-omega - 1)*alpha, 1), (omega*alpha, 1)]
[]

where the polynomial ring gets created once and then never changes. Fortunately (?), this actually is the output that I get trying this on two different machines running 7.1, starting from an empty session, and on SMC, currently running 6.10. This behavior appears to be reproducible.

However, I tried a development build I have on SMC (version 7.2beta6), again from an empty session:

[(alpha, 1), ((-omega - 1)*alpha, 1), (omega*alpha, 1)]
[(alpha, 1), (omega*alpha, 1), ((-omega - 1)*alpha, 1)]
[(alpha, 1), ((-omega - 1)*alpha, 1), (omega*alpha, 1)]
[]

This also appears to be reproducible.

comment:4 in reply to: ↑ 2 Changed 5 years ago by kedlaya

Replying to pbruin:

In fact, in the above example we have

sage: K == L
True

which causes a cache lookup in PolynomialRing to return K['x'] when given L as input.

We should probably make number fields satisfy K == L if and only if K is L, i.e. make them inherit from WithEqualityById. Doing this in the most naive way unfortunately leads to a number of doctest failures.

In this example, we also have:

sage: hash(K) == hash(L)
True

which is presumably why PolynomialRing is fooled. Digging into src/sage/rings/number_field/number_field.py:

   def __hash__(self):
        r"""
        Compute the hash value of this number field.

        TESTS:

        Since there is a custom implementation of :meth:`__cmp`, we need a
        custom ``__hash__``. The number fields ``K`` and ``L`` in the following
        example used to have different hashes prior to :trac:`11670`::

            sage: R.<x> = QQ[]
            sage: R.<y> = QQ[]
            sage: K.<a> = NumberField(x^2+1)
            sage: L.<a> = NumberField(y^2+1)
            sage: K == L
            True
            sage: hash(K) == hash(L)
            True

        """
        return hash((self.variable_name(), self.base_field(), tuple(self.__polynomial)))

It appears that self.__polynomial is the absolute defining polynomial, not the relative one. I'm guessing this was done on purpose to fix some other problem, judging from this byline:

- Julian Rueth (2014-04-03): absolute number fields are unique parents

It might be worth trying to replace self.__polynomial with something like self.relative_polynomial() to see how much doctest breakage results.

comment:5 Changed 5 years ago by kedlaya

  • Branch set to u/kedlaya/weird_bug_in_roots_of_a_polynomial_in_relative_number_field_extension

comment:6 Changed 5 years ago by git

  • Commit set to db390043e683d183e04303080e67a94357a5618d

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

db39004Fix print statements in docstrings for Py3

comment:7 Changed 5 years ago by git

  • Commit changed from db390043e683d183e04303080e67a94357a5618d to fa9c48539be9e27a676463710da32122943d95d8

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

fa9c485Added doctest from Kevin Buzzard via sage-nt

comment:8 Changed 5 years ago by kedlaya

  • Authors set to Kiran Kedlaya
  • Milestone changed from sage-6.8 to sage-7.2
  • Status changed from new to needs_review

In fact, changing the hash of a number field to refer to the relative defining polynomial doesn't seem to break anything that I could find. These commits implement that change and add several doctests based on the above discussion and the linked sage-nt thread.

comment:9 Changed 5 years ago by pbruin

  • Reviewers set to Peter Bruin
  • Status changed from needs_review to needs_work

Several comments:

  • Changing __hash__ is not enough; you also have to update __cmp__ to be compatible with it. Python (and Sage) objects are supposed to satisfy the implication x == y ==> hash(x) == hash(y). Otherwise things like the cache lookup in comment:2 will give undesired results if there is a hash collision.
  • In particular, the output of K == L in the first doctest should be False.
  • There is no reason to introduce a new attribute __relative_polynomial. Since relative_polynomial() simply returns an existing attribute, you can just do
    return hash((self.variable_name(), self.base_field(), tuple(self.relative_polynomial())))
    
  • An indented block should always be indented by 4 spaces relative to the previous line; in some of the doctests there are only 3 spaces.
  • It is not very useful to have a doctest whose output consists of dozens of lines True; it is cleaner to replace print(elt.is_integral) by assert(elt.is_integral).

comment:10 Changed 5 years ago by git

  • Commit changed from fa9c48539be9e27a676463710da32122943d95d8 to 4c52f08b74a2883ce23ba82a5ef8bda4b37e5f04

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

4c52f08Modify _cmp_ for relative number fields, fix doctests

comment:11 Changed 5 years ago by kedlaya

  • Status changed from needs_work to needs_review

See if this covers everything. I added a relevant doctest for __cmp__.

comment:12 Changed 5 years ago by pbruin

  • Status changed from needs_review to positive_review

Looks good to me and all tests pass according to the patchbot.

comment:13 Changed 5 years ago by misjafasteinmetz

  • Cc misjafasteinmetz added

comment:14 Changed 5 years ago by vbraun

  • Branch changed from u/kedlaya/weird_bug_in_roots_of_a_polynomial_in_relative_number_field_extension to 4c52f08b74a2883ce23ba82a5ef8bda4b37e5f04
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:15 Changed 5 years ago by dimpase

  • Commit 4c52f08b74a2883ce23ba82a5ef8bda4b37e5f04 deleted
  • Milestone changed from sage-7.2 to sage-7.3
Note: See TracTickets for help on using tickets.