Failures in polynomials over non-prime residue fields of a tower of number field

remyoudompheng commented 1 year ago

Is there an existing issue for this?

[X] I have searched the existing issues for a bug report that matches the one I want to file, without success.

Did you read the documentation and troubleshoot guide?

[X] I have read the documentation and troubleshoot guide

Environment

- **OS**: Archlinux, Debian
- **Sage Version**: 9.8 and 10.0b5

Steps To Reproduce

Run the following sequence: instantiate a double extension of QQ, and select an ideal such that the residue field has degree > 1.

sage: x = polygen(QQ)
sage: K.<a> = NumberField(x**3-5)
sage: L.<b> = K.extension(x^2+26)
sage: OL = L.ring_of_integers()
sage: IL = OL.ideal(7).factor()[0][0]
sage: kL = OL.residue_field(IL)
sage: kL.degree()
3
sage: R = kL["x"]
sage: poly = R([1,2])
sage: poly.monic()
?
sage: R.random_element(2)
?

Expected Behavior

poly.monic() should divide the polynomial by 2 and random_element select a random polynomial

For example, if the residue field is a prime field (degree 1):

sage: IL = OL.ideal(3).factor()[0][0]
sage: kL = OL.residue_field(IL)
sage: kL.degree()
1
sage: R = kL["x"]
sage: R.random_element(2)
x^2 + x + 2
sage: R([1,2]).monic()
x + 2

If we don't do the extension of K, there is no issue:

sage: IK = OK.ideal(11).factor()[0][0]
sage: kK = OK.residue_field(IK)
sage: kK.degree()
2
sage: R = kL["x"]
sage: R = kK["x"]
sage: R([1,2]).monic()
x + 6
sage: R.random_element(2)
(5*abar + 3)*x^2 + (5*abar + 4)*x + abar + 5

Actual Behavior

An exception is raised:

  File "sage/rings/polynomial/polynomial_element.pyx", line 5732, in sage.rings.polynomial.polynomial_element.Polynomial.monic (build/cythonized/sage/rings/polynomial/polynomial_element.c:47487)
  File "sage/structure/element.pyx", line 1515, in sage.structure.element.Element.__mul__ (build/cythonized/sage/structure/element.c:12383)
  File "sage/structure/coerce.pyx", line 1191, in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:10663)
  File "sage/structure/coerce.pyx", line 1720, in sage.structure.coerce.CoercionModel.get_action (build/cythonized/sage/structure/coerce.c:17595)
  File "sage/structure/coerce.pyx", line 1851, in sage.structure.coerce.CoercionModel.discover_action (build/cythonized/sage/structure/coerce.c:19105)
  File "sage/structure/parent.pyx", line 2550, in sage.structure.parent.Parent.get_action (build/cythonized/sage/structure/parent.c:20835)
  File "sage/structure/parent.pyx", line 2631, in sage.structure.parent.Parent.discover_action (build/cythonized/sage/structure/parent.c:21853)
  File "sage/structure/coerce_actions.pyx", line 217, in sage.structure.coerce_actions.detect_element_action (build/cythonized/sage/structure/coerce_actions.c:5313)
  File "sage/structure/coerce_actions.pyx", line 330, in sage.structure.coerce_actions.ModuleAction.__init__ (build/cythonized/sage/structure/coerce_actions.c:6350)
  File "/usr/lib/python3.10/site-packages/sage/categories/pushout.py", line 4449, in pushout
    return all(Z)
  File "sage/categories/functor.pyx", line 383, in sage.categories.functor.Functor.__call__ (build/cythonized/sage/categories/functor.c:3379)
  File "/usr/lib/python3.10/site-packages/sage/categories/pushout.py", line 506, in _apply_functor
    R = c(R)
  File "sage/categories/functor.pyx", line 383, in sage.categories.functor.Functor.__call__ (build/cythonized/sage/categories/functor.c:3379)
  File "/usr/lib/python3.10/site-packages/sage/categories/pushout.py", line 3295, in _apply_functor
    return R.extension(self.polys, names=self.names, embedding=self.embeddings,
  File "sage/rings/finite_rings/finite_field_base.pyx", line 1534, in sage.rings.finite_rings.finite_field_base.FiniteField.extension (build/cythonized/sage/rings/finite_rings/finite_field_base.c:18139)
  File "sage/structure/factory.pyx", line 367, in sage.structure.factory.UniqueFactory.__call__ (build/cythonized/sage/structure/factory.c:2321)
  File "/usr/lib/python3.10/site-packages/sage/rings/finite_rings/finite_field_constructor.py", line 618, in create_key_and_extra_args
    name = normalize_names(1, name)
  File "sage/structure/category_object.pyx", line 900, in sage.structure.category_object.normalize_names (build/cythonized/sage/structure/category_object.c:8617)
  File "sage/structure/category_object.pyx", line 1016, in sage.structure.category_object.normalize_names (build/cythonized/sage/structure/category_object.c:8491)
IndexError: the number of names must equal the number of generators

Additional Information

This was discovered while working on an unrelated patch (trigggering a failure in ell_curve_isogeny.py in test for isogenies over relative number fields)

remyoudompheng commented 1 year ago

Here is where it fails:

sage: x = polygen(QQ)
sage: K.<a> = NumberField(x**3-5)
sage: L.<b> = K.extension(x^2+26)
sage: OL = L.ring_of_integers()
sage: IL = OL.ideal(7).factor()[0][0]
sage: kL = OL.residue_field(IL)
sage: R = kL["x"]
sage: coercion_model.get_action(R, kL, operator.mul)
Right scalar multiplication by Residue field in bbar of Fractional ideal (7, (3*a^2 + 3*a + 1)*b + 2*a^2 + 2*a + 3) on Univariate Polynomial Ring in x over Residue field in bbar of Fractional ideal (7, (3*a^2 + 3*a + 1)*b + 2*a^2 + 2*a + 3)
sage: coercion_model.get_action(kL, R, operator.mul)
...
IndexError: the number of names must equal the number of generators

tscrim commented 1 year ago

I reproduced the same failure in a different way. I had a typo

sage: x = polygen(QQ)
sage: K.<a> = NumberField(x^3-5)
sage: L.<b> = K.extension(x^2+36)  # Note the slight difference
sage: OL = L.ring_of_integers()
sage: IL = OL.ideal(7).factor()[0][0]
sage: kL = OL.residue_field(IL)
sage: R = kL['x']
sage: R.an_element()^2
<repr(<sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX at 0x7fc972cad9c0>) failed: IndexError: the number of names must equal the number of generators>

Interestingly, multiplying on the right by elements in the base ring works, and the coercions all seem to be in place:

sage: lc = ~poly.leading_coefficient()
sage: poly * lc
x + 4
sage: R(lc) * poly
x + 4
sage: phi = R.coerce_map_from(lc.parent())
sage: phi(lc) * poly
x + 4

From this and the error messages, predicably it fails when trying to find a left action of the base ring:

sage: coercion_model.discover_action(kL, R, operator.mul)
BOOM

even though it discovers the right action just fine. Perhaps something is going wrong with the pushout computation? I would need to trace through things more at this point...

remyoudompheng commented 1 year ago

I believe the fix is to catch IndexError along with ValueError and TypeError in sage.categories.pushout.pushout: it seems already very liberal in which exception types to catch, and the contract is to raise a CoercionException whenever something doesn't make sense.

Another possible cause is that ResidueField have very special construction properties: if k is a ResidueField, usually pushout(k, k.base()) will fail.

tscrim commented 1 year ago

Perhaps, although it seems like it would cover up some mismatch that feels like a real error that could appear elsewhere. Do you have an idea about how to isolate this error? I can do some digging to see, but before I spend time doing that, I wanted to see if you already had or knew where to start.

remyoudompheng commented 1 year ago

Another possibility is to catch the case of multiple variables in the FiniteFieldConstructor and raise a NotImplementedError because multiple extensions of finite fields are not supported (which is true, there is no mathematical obstruction to doing that). It will be properly recast as a CoercionException,

sagemath / sage