simplify(..., canonical=true) gives noncanonical answer

[fagu]

According to the documentation, the function simplify(..., canonical=true) should produce a canonical defining polynomial of a given number field. However, it is not idempotent:

using Oscar

function polredabs(f::QQPolyRingElem)::QQPolyRingElem
	K, _ = number_field(f, :w, cached=false)
	L, _ = simplify(K, canonical=true)
	return defining_polynomial(L)
end

R, x = polynomial_ring(QQ, :x)
f = x^8 + 4*x^7 - 56*x^6 - 168*x^5 + 758*x^4 + 2412*x^3 - 1656*x^2 - 9508*x - 6828
g = polredabs(f)
h = polredabs(g)

println(f)
println(g)
println(h)

outputs

x^8 + 4*x^7 - 56*x^6 - 168*x^5 + 758*x^4 + 2412*x^3 - 1656*x^2 - 9508*x - 6828
x^8 - 4*x^7 - 30*x^6 + 164*x^5 - 2*x^4 - 1056*x^3 + 1432*x^2 + 372*x - 1076
x^8 - 4*x^7 - 30*x^6 + 44*x^5 + 298*x^4 + 108*x^3 - 614*x^2 - 680*x - 199

The last polynomial is correct according to pari/gp:

? polredabs(x^8 + 4*x^7 - 56*x^6 - 168*x^5 + 758*x^4 + 2412*x^3 - 1656*x^2 - 9508*x - 6828)
%1 = x^8 - 4*x^7 - 30*x^6 + 44*x^5 + 298*x^4 + 108*x^3 - 614*x^2 - 680*x - 199

Actually, the code has a comment that might be related:

Hecke.jl/src/NumField/NfAbs/Simplify.jl

Lines 451 to 468 in 07b4ccf

	#try to find the T2 shortest element
	#the precision management here needs a revision once we figure out
	#how....
	#examples that require this are Gunters:
	#=
	die drei Polynome
	[ 10834375376002294480896, x^18 - x^16 - 6*x^14 - 4*x^12 - 4*x^10 + 2*x^8 +
	6*x^6 - 4*x^4 + 3*x^2 - 1 ],
	[ 10834375376002294480896, x^18 - 3*x^16 + 4*x^14 - 6*x^12 - 2*x^10 + 4*x^8 +
	4*x^6 + 6*x^4 + x^2 - 1 ],
	[ 10834375376002294480896, x^18 + x^16 - x^14 - 8*x^12 - 3*x^8 + 27*x^6 -
	25*x^4 + 8*x^2 - 1 ],
	werden alle als 'canonical' ausgegeben, obwohl sie isomorphe
	K"orper definieren ??
	=#

If these precision problems are hard to fix, maybe there should be a warning in the documentation?

(Sorry if this issue is already known...)

[fagu]

The polynomials g and h are totally real with the same T2-norm $(-4)^2-2\cdot(-30)=76$.

I don't know if there's any point in implementing this special case, but: For totally real fields the T2-norm is always an integer, so I suppose one doesn't need to work with floating point numbers in this case.

In general, the T2-norm is at least always an algebraic integer.

(How does Pari do it?)

[fagu]

Kind of inefficient, but one could use interval arithmetic for comparisons and test whether two elements $\alpha,\beta\in\mathcal O_K$ have the same T2-norm by testing whether $p_\alpha(X) = p_\beta(X)$, where
$$p_\alpha(X) = \prod_{A_1,\dots,A_s,B}\left(X-2\cdot\sum_{i=1}^{s} \alpha^{(a_i)}\cdot\alpha^{(a_i')}-\sum_{u=1}^{n-2s} \left(\alpha^{(b_u)}\right)^2\right) \in \mathbb Z[X].$$
Here, $s$ is the number of pairs of complex embeddings and the product is over all ways to partition $[n]=A_1\sqcup\dots\sqcup A_s\sqcup B$ into sets $A_i = { a_i,a_i' }$ of size $2$ and a set $B={b_1,\dots,b_{n-2s}}$ modulo permutation of $A_1,\dots,A_s$.

(The polynomial $p_\alpha(X)$ has degree $\frac{n!}{2^s\cdot s!\cdot(n-2s)!}$.)

[fieker]

On Mon, Dec 04, 2023 at 06:01:14AM -0800, Fabian Gundlach wrote: Kind of inefficient, but one could use interval arithmetic for comparisons and test whether two elements $\alpha,\beta\in\mathcal O_K$ have the same T2-norm by testing whether $p_\alpha(X) = p_\beta(X)$, where $$p_\alpha(X) = \prod_{A_1,\dots,A_s,B}\left(X-2\cdot\sum_{i=1}^{s} \alpha^{(a_i)}\cdot\alpha^{(a_i')}-\sum_{u=1}^{n-2s} \left(\alpha^{(b_u)}\right)^2\right) \in \mathbb Z[X].$$ Here, $s$ is the number of pairs of complex embeddings and the product is over all ways to partition $[n]=A_1\sqcup\dots\sqcup A_s\sqcup B$ into sets $A_i = \{ a_i,a_i' \}$ of size $2$ and a set $B=\{b_1,\dots,b_{n-2s}\}$ modulo permutation of $A_1,\dots,A_s$. (The polynomial $p_\alpha(X)$ has degree $\frac{n!}{2^s\cdot s!\cdot(n-2s)!}$.)

The issue is understood and mostly unrelated. Problem: find the shortest primtive elements and sort the minpolys. Think of Q(zeta_n)(sqrt(alpha)) as a difficult case. I can make it totally real, but this is the hard case. Think alpha >> 0, then all "short" elements are in Q(zeta_n), hence not primitive. You'll have to enumerate a huge number of elements before you hit a primitive one. Therefor pari and we cheat. Since we know that (in the product basis) sqrt(alpha) has to be involved somehow, we start the enumeration at the 1st element that involves sqrt(alpha). Unfortunately, in this example, we start with the 2nd element while the first would have been the canonical one. In general if alpha and beta have the same length, this is difficult to verify. I do not have a good strategy and bound for that - and neither has pari... There is a possibility that the bound indeed is terrible. (Here of course T_2(x) = trace(x^2) is in Z and exact, hence this problem we don't have)

…

-- Reply to this email directly or view it on GitHub: #1308 (comment) You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

[fagu]

Thanks for the explanation and the quick fix!