isunit is wrong for polynomials over a non-integral domain

[wbhart]

Polynomials can be units in more cases than currently being tested, over a non-integral domain.

[wbhart]

We have the following theorems:

Thm: If R is of finite characteristic (and commutative) then f in R[x] is a unit iff f = u + r(x)*x for u a unit in R and all coefficients of r(x) are nilpotent in R.

Thm: a in Z/nZ is nilpotent iff rad(a) = rad(n).

[fingolfin]

These days have a somewhat better is_unit method in src/HeckeMoreStuff.jl:376 for rings over Z/nZ:

function is_unit(f::T) where {T<:Union{ZZModPolyRingElem,zzModPolyRingElem}}
  if !is_unit(constant_coefficient(f))
    return false
  end
  for i = 1:degree(f)
    if !is_nilpotent(coeff(f, i))
      return false
    end
  end
  return true
end

Perhaps we could define a similar but more generic method in AA:

function is_unit(f::T) where {T<:PolyRingElem}
  is_unit(constant_coefficient(f)) || return false
  is_domain_type(base_ring_type(T)) && return true
  for i = 1:degree(f)
    if !is_nilpotent(coeff(f, i))
      return false
    end
  end
  return true
end

Of course then we also need a more general is_nilpotent in AA. For starters:

function is_nilpotent(a::T) where {T <: RingElem}
  is_domain_type(parent_type(T)) && return is_zero(a)
  error("not implemented")
end

and then we can also copy the is_nilpotent(a::ResElem{T}) where {T<:IntegerUnion} method from Nemo...

This won't cover all cases but at least it covers some, and for others we get an error instead of nonsense output.

[fingolfin]

In fact we don't need a check for the characteristic either. See e.g. https://kconrad.math.uconn.edu/blurbs/ringtheory/polynomial-properties.pdf

For is_nilpotent, we can implement generically for ...

• anything where is_domain_type holds
• univariate polynomial rings by delegating to the coefficient ring (a polynomial in $R[x]$ is nilpotent iff its coefficients are nilpotent in $R$
• this extends to multivariate rings (by considering $R[x,y]$ as $R[x][y]$), see Theorem 3.1 in the linked PDF
• ... and thus to UniversalPolyRing
• ResElem{<:IntegerUnion}
• we already handle MatrixElem in AA (though possibly with room for improvement?), so we have matrix rings covered

Dunno about Laurent and series rings (mainly because I am too lazy to think about them, but my guess would be that at least for the Laurent rings it against reduces to considering the coefficients -- it shouldn't be too hard to either adapt the proofs or else follow them to construct a counter example)

[JohnAAbbott]

The article by Conrad excludes polynomials over the zero ring: presumably all such polynomials are both nilpotent and invertible.

[thofma]

Yes, all elements in the zero-ring are nilpotent and invertible. (I think both Theorem 2.1 and 2.2 are valid for zero rings; the is_unit method proposed by Max above also works independent of whether the coefficient ring is the zero ring.)

[JohnAAbbott]

Is there a general way of indexing/iterating over the terms of a "generalized polynomial": univariate, multivariate, polynomials, laurent polynomials, power-series, puiseux-series? For the function coeff: I note that indexing over univariate polynomials uses indexes starting from 0 with no upper limit, whereas indexes into a multivariate polynomial start from 1 and must not exceed length(f). For a univariate puiseux-series one can use S.scale and precision(S) to find an upper limit... Help/guidance would be appreciated!

[thofma]

No, there is no uniform interface. I would also avoid inexact rings for the moment.

[JohnAAbbott]

I wanted to implement is_unit and is_nilpotent for puiseux-series, but now realise that the definition is not entirely clear. Is the power series z + O(z^2) nilpotent? If the ring is "capped" then it clearly is; if the ring is "relative" then no finite power will give zero. Should the result depend on whether the ring is "capped"?

[thofma]

Yes it is not entirely clear, which is why I suggest that we should not implement it. It is not clear what the semantics of equality is or should be. At the moment one gets a "no such method exists". Which is fine, since it is not a wrong result. On the other hand, for polynomials the functions are currently wrong.

[JohnAAbbott]

If the base_ring is the zero ring then everything is both nilpotent and invertible. We can in some cases decide if a *-series is invertible or not; in other cases we do not have enough information. So should the code attempt to decide if possible, and otherwise give a not enough info error? Similarly, in some cases it is clear that a *-series is not nilpotent, but we can never decide that it is nilpotent...

[fingolfin]

@JohnAAbbott I would suggest to ignore the series case completely for now; just let it throw a "not implemented" error for now. Instead focus on the cases we can handle. Once those are in, we have covered the most pressing need, and then can take our time to figure out the other times one at a time.

[JohnAAbbott]

I have a first implementation (and test suite). Where should it go? Right now I have a single file containing both is_nilpotent and is_unit for several cases -- I find it quite handy to have all the implementations close together (not least because they are all structurally similar, though not similar enough that they could be easily fused into fewer separate functions). The disadvantage is that the functions refer to disparate types. I unintentionally ignored the reference to the implementation in src/HeckeMoreStuff.jl, so re-implemented is_nilpotent for ResElem{IntegerUnion}. Now there are two implementations where sometimes one is faster, and sometimes the other is faster... sigh!

[thofma]

They should go (in AbstractAlgebra) in src/Poly.jl and src/MPoly.jl respectively. And similar for the tests.

[JohnAAbbott]

I also have implementations for Laurent polys. It seems that src/LaurentPoly.jl contains very little, while there are further functions/operations in src/algorithm/LaurentPoly.jl; in contrast src/LaurentMPoly.jl contains several functions, and there is no file src/algorithm/LaurentMPoly.jl. This is a slightly incoherent design structure. Currently I'm adding the new functions to src/algorithm/LaurentPoly.jl and to src/LaurentMPoly.jl...