Opened 6 years ago

Closed 5 years ago

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

Reported by: Owned by: robharron major sage-7.3 number fields Relative number field, roots misjafasteinmetz Kiran Kedlaya Peter Bruin N/A 4c52f08

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

### 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: ↓ 4 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

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:

 ​db39004 `Fix 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:

 ​fa9c485 `Added 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

• 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:

 ​4c52f08 `Modify _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.