is_squarefree for integer polynomials

[fagu]

The polynomial $7x^2+2$ is irreducible in $\mathbb Z[x]$, but Nemo (version 0.35.1) claims that it is not squarefree:

Zx, x = ZZ["x"]
f = 7*x^2+2
is_squarefree(f) # returns false
factor(f) # 1 * (7*x^2 + 2)

I'm new to Nemo and might be misunderstanding the specification of is_squarefree, so apologies if this is out of scope. But at least this test suggests to me that it's intended to work for integer polynomials:
https://github.com/lgoettgens/Hecke.jl/blob/c7ab8cd067cbddc815002a1dcde0da3e1a21a64c/test/Misc/Poly.jl#L111-L117

The reason for this behavior is that f is divided by its leading coefficient with divexact. That seems to round $(7x^2+2)/7$ to $x^2$, which is not squarefree.

Nemo.jl/src/HeckeMiscPoly.jl

Line 526 in 45d8783

g = divexact(f, leading_coefficient(f))

The check flag of divexact is ignored when dividing by scalars:

Nemo.jl/src/flint/fmpz_poly.jl

Lines 409 to 423 in 45d8783

	function divexact(x::ZZPolyRingElem, y::ZZRingElem; check::Bool=true)
	iszero(y) && throw(DivideError())
	z = parent(x)()
	ccall((:fmpz_poly_scalar_divexact_fmpz, libflint), Nothing,
	(Ref{ZZPolyRingElem}, Ref{ZZPolyRingElem}, Ref{ZZRingElem}), z, x, y)
	return z
	end
	function divexact(x::ZZPolyRingElem, y::Int; check::Bool=true)
	y == 0 && throw(DivideError())
	z = parent(x)()
	ccall((:fmpz_poly_scalar_divexact_si, libflint), Nothing,
	(Ref{ZZPolyRingElem}, Ref{ZZPolyRingElem}, Int), z, x, y)
	return z
	end

(Flint assumes that the division is exact, but doesn't check it.)

[thofma]

Thanks for the report. I think the is_squarefree function was written with polynomials over fields in mind. I have opened #1511 to fix it.

[fagu]

Thanks for the fix.

It segfaults for the zero polynomial, but I would say that's a bug in FLINT. (Reported at flintlib/flint#1414.)

[thofma]

Hm, I am inclined to add the assumption, that the input must be non-zero. (Magma is also doing this.)

What do you think?

[fagu]

For factor_squarefree, I think throwing an exception would be good, just like when you call factor(ZZ(0)) or factor(Zx(0)).

For is_squarefree, I guess throwing an exception is also the safest option, and consistent with is_squarefree(ZZ(0)). My personal opinion is that false would be the correct answer (as 0 is divisible by x^2), but for polynomials over fields, is_squarefree currently returns true, and FLINT also says true...

[thofma]

I agree with you, that 0 should never be squarefree, and that returning true is rather odd.

It is actually hard to find a definition for squarefree elements in arbitrary rings. Interpolating the definition for integers and polynomials over fields, I would come up with: An element is not squarefree, if it is divisible by the square of a non-unit. This generalizes https://de.wikipedia.org/wiki/Quadratfreie_Zahl#Allgemeine_Definition, although Wikipedia imposes the condition that the element is non-zero (but they do not provide a source).

[fagu]

Not really relevant here, but just for the record: I agree with your definition of squarefree elements in the case of unique factorization domains. But for Dedekind domains, I think the usual definition would be that an element (or more generally an ideal) is squarefree if it is not divisible by the square of any prime ideal.