Method error when multiplying an AcbPolyRingElem by some small rational

[rburing]

Setup:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.10.0 (2023-12-25)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> using Nemo

Welcome to Nemo version 0.41.2

Nemo comes with absolutely no warranty whatsoever

julia> CC = AcbField(4096)
Complex Field with 4096 bits of precision and error bounds

julia> R, x = polynomial_ring(CC, "x")
(Univariate Polynomial Ring in x over Complex Field with 4096 bits of precision and error bounds, x)

Problem:

julia> 1//46056306910739171242500*x
ERROR: MethodError: no method matching normalise(::AcbPolyRingElem, ::Int64)

Closest candidates are:
  normalise(::FqRelPowerSeriesRingElem, ::Int64)
   @ Nemo ~/.julia/packages/Nemo/Ik9Iu/src/flint/fq_default_rel_series.jl:39
  normalise(::FpAbsPowerSeriesRingElem, ::Int64)
   @ Nemo ~/.julia/packages/Nemo/Ik9Iu/src/flint/fmpz_mod_abs_series.jl:49
  normalise(::FpRelPowerSeriesRingElem, ::Int64)
   @ Nemo ~/.julia/packages/Nemo/Ik9Iu/src/flint/fmpz_mod_rel_series.jl:46
  ...

Stacktrace:
 [1] *(a::Rational{Int128}, b::AcbPolyRingElem)
   @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/67yib/src/Poly.jl:760
 [2] top-level scope
   @ REPL[4]:1

[fingolfin]

Thank you for reporting this issue!

As a quick workaround in case you need it: this works when using "our" rational numbers:

julia> QQ(1//46056306910739171242500)*x
[2.17125528961338664420046908293397582469959395066467866192707950609321061598520590517247847194909449397459051338727699925323460062834454062199481042129325112994260092977602139044491188062821289848385353725430008896646287709851460806814755877806588214575269035932923475842316159511284106785022636414796553592157072198400621147153676685317334347815399002067692369366494734482556867893748818284962860214824751426181039654891341653349951497177073854628716409957583099557982208348166600539582686684900665107445406533648904391748268408479470194091615941962889444479483192683847903485885756086110764204579979628902383746666750186782714685340338629172861427766257458943046883445787236231260922158126591458105293095885842571707132783393896384697907386825831576640629563287726750770915831397741011623869501974898521831292835107749847580908803783729910449912616773647523816255475325598356765990844196702532915952801790585818801794510959702081117303314089598746793547966175956904549348504444335269073886843418033911083434043562076904199903432701048150785617367845776930512465562295673538809572038218462459555830713421188434004223520999861880800003711179904380283767284331622829066729084192594910502920141989829818483965393366527264916088835045542e-23 +/- 3.95e-1256]*x

Apparently the polynomial ring interface has a required normalise method which is not implemented for AcbPolyRingElem -- and many others. Perhaps there should be a do-nothing default method for it?

Also we should add a "polynomial ring interface conformance test suite". Then the "ring interface conformance test suite" should automatically run that for any PolyRingElem / PolyRing subtypes. (And then do the same for MPolyRingElem, and other ring types which have their own special documented APIs).

Finally, we can of course also define specialized ad-hoc multiplication methods for e.g. Rational and AcbPolyRingElem and others in case we can implement them more efficiently, but that's an optimization, and otherwise just hides the core issues.

[fingolfin]

Looking into this reveals so many bads thing 😭

OK first of, I think we should add this generic method to AbstractAlgebra (and similar ones for NC polynomials, series, etc.?)

function Nemo.normalise(a::PolyRingElem, n::Int)
   while n > 0 && iszero(coeff(a,n))
      n -= 1
   end
   return n + 1
end

Perhaps also add an is_zero_coeff(a,n) method to allow optimizing this a bit in various situations (similar to have we have is_zero_entry, is_zero_row, is_zero_column

Anyway, the Julia code above is a modified version of this method from AA which only applies to the "generic polynomial" implementation -- note that differing return value there which is wrong:

function normalise(a::Poly, n::Int)
   while n > 0 && iszero(a.coeffs[n])
      n -= 1
   end
   return n   # <- this is WRONG
end

The documentation says normalise returns the length of the polynomial after normalisation, which is the degree PLUS ONE, which is 2 in your example. As a result, without that fix, computing 1//2 * x return zero.

So: any code that has been using normalise probably is subtly broken:either it gives wrong results, or it is adapt to the wrong implementations of normalise. We need to figure out which it is and either adapt the documentation, or the implementations (probably both to some degree). Urgh

There are almost identical methods in AA for NCPoly, SparsePoly, LaurentSeriesElem and more which have the same issue. On the other hand, all methods in Nemo I looked at have the "correct" return value (I didn't look at all, though).

So the next thing to do is to audit all (?) code calling normalise to see what it expects. 😭

[thofma]

It is not clear what the semantics for polynomials with inexact coefficients is and if your generic normalise function would work at all. There maybe coefficients which contain zero. What is the degree or length of the polynomial f = [0 +/- 0.5] * x + 1 and what should the normalise function return?

[fingolfin]

OK fine then the generic normalise can refuse to work for inexact ones.

And the generic code calling normalise then maybe also in some cases should check that.

We still should fix it so that documentation and code match.

For the issue here, we can also solve it by modifying this code:

###############################################################################
#
#   Ad hoc binary operators
#
###############################################################################

for T in [Integer, ZZRingElem, QQFieldElem, Float64, BigFloat, ArbFieldElem, AcbFieldElem, ZZPolyRingElem, QQPolyRingElem]

... to also include Rational in the list of types T (and adding tests, of course). And then probably the same for a bunch of other similar such adhoc lists.