roots crashes for polynomials over q-adic fields (wild ramification, precision loss)

[alexey-orlov-math]

1. Wild ramification: nonzero constant causes crash

Over $Q_{2^2}$, X^3 + 3*X works correctly:

roots(change_base_ring(qadic_field(2, 2; precision=3)[1], X^3 + 3*X))
3-element Vector{QadicFieldElem}:
 0
 (2^1 + O(2^2))*a + 2^0 + 2^1 + O(2^2)
 (2^1 + O(2^2))*a + 2^0 + O(2^2)

Yet adding a nonzero constant (even with high precision) crashes:

roots(change_base_ring(qadic_field(2, 2; precision=10)[1], X^3 + 3*X - 2))
ERROR: BoundsError: attempt to access 0-element Vector{FqPolyRingElem} at index [1]
Stacktrace:
 [1] ...
 [3] Hecke.HenselCtxdr{QadicFieldElem}(...)
   @ Hecke ~/math/software/Hecke.jl/src/LocalField/Poly.jl:886
 [4] Hensel_factorization(...)
 [5] roots(...)
   @ Hecke ~/math/software/Hecke.jl/src/LocalField/automorphisms.jl:13
 [6] _roots(...)
 [7] roots(...)
   @ Hecke ~/math/software/Hecke.jl/src/LocalField/automorphisms.jl:31

This happens at any precision. The same occurs over $Q_{3^2}$: the reduction mod 3 of X^3 + 3*X - c is X^3 - c, which for c = 1 or c = 2 has a triple root in $F_9$ (wild ramification). X^3 + 3*X finds roots correctly, while X^3 + 3*X - 1 and X^3 + 3*X - 2 crash with the same stack trace.

2. Wild ramification combined with insufficient precision

roots(change_base_ring(qadic_field(3, 2; precision=2)[1], X^4 + 2*X - 3))
ERROR: AssertionError: !(iszero(f))
Stacktrace:
 [1] _content(...)
   @ Hecke ~/math/software/Hecke.jl/src/LocalField/Poly.jl:128
 [2] fun_factor(...)
 [3] Hensel_factorization(...)
 [4] roots(...)
   @ Hecke ~/math/software/Hecke.jl/src/LocalField/automorphisms.jl:13
 [5] _roots(...)
 [6] roots(...)
   @ Hecke ~/math/software/Hecke.jl/src/LocalField/automorphisms.jl:31

Increasing the precision makes it crash in the same way as (1).

3. Tame ramification and precision loss

roots(change_base_ring(qadic_field(3, 2; precision=10)[1], X^3 + 3*X - 36))
1-element Vector{QadicFieldElem}:
 3^1 + O(3^7)

Since $v_3(36) = 2$, losing 3 digits of precision is arguably understandable. Yet Sage gives [(3 + O(3^3), 1)] at precision 2 and [(3 + O(3^11), 1)] at precision 10. If we try to lower precision in Hecke:

roots(change_base_ring(qadic_field(3, 2; precision=2)[1], X^3 + 3*X - 36))
ERROR: AssertionError: degree(h) > 0
Stacktrace:
 [1] roots(...)
   @ Hecke ~/math/software/Hecke.jl/src/LocalField/automorphisms.jl:24

For reference, Sage computes the Newton polygon slopes as [-1, -1/2, -1/2] with factorization

((3^-1 + O(3^9))*X^2 + (1 + O(3^10))*X + 1 + 3 + O(3^10)) * ((3 + O(3^11))*X + 2*3^2 + 2*3^3 + 2*3^4 + 2*3^5 + 2*3^6 + 2*3^7 + 2*3^8 + 2*3^9 + 2*3^10 + 2*3^11 + O(3^12))

with a quadratic factor (slope -1/2, roots in a ramified extension) and a linear factor for x = 3. The factorization suggests that the precision loss might be related to a difference between absolute and relative precision tracking, and/or possibly to the lack of dynamic precision increase

In the wild ramification case, when there are solutions (so no early exit from checking newton polygon) it seems to be too easy to get a crash. In the tame case, it is prone to precision loss and crashes when precision is too low, whereas Sage manages to find roots with the same or less input precision.