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

[rharron]

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.)

CC: @sagetrac-misjafasteinmetz

Component: number fields

Keywords: Relative number field, roots

Author: Kiran Kedlaya

Branch: 4c52f08

Reviewer: Peter Bruin

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

[pjbruin]

comment:1

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.

[pjbruin]

comment:2

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.

[kedlaya]

comment:3

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.

[kedlaya]

comment:4

Replying to @pjbruin:

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.

[kedlaya]

Branch: u/kedlaya/weird_bug_in_roots_of_a_polynomial_in_relative_number_field_extension

[sagetrac-git]

Commit: db39004

[sagetrac-git]

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

db39004

Fix print statements in docstrings for Py3

[sagetrac-git]

Changed commit from db39004 to fa9c485

[sagetrac-git]

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

fa9c485

Added doctest from Kevin Buzzard via sage-nt

[kedlaya]

comment:8

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.

[kedlaya]

Author: Kiran Kedlaya

[pjbruin]

comment:9

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).

[pjbruin]

Reviewer: Peter Bruin

[sagetrac-git]

Changed commit from fa9c485 to 4c52f08

[sagetrac-git]

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

4c52f08

Modify `_cmp_` for relative number fields, fix doctests

[kedlaya]

comment:11

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

[pjbruin]

comment:12

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

[vbraun]

Changed branch from u/kedlaya/weird_bug_in_roots_of_a_polynomial_in_relative_number_field_extension to 4c52f08

[dimpase]

Changed commit from 4c52f08 to none