ideal.interreduced_basis hangs forever

This completes in a fraction of a second:

sage: R.<a,b,c,d>=PolynomialRing(QQ,order="lex")
sage: ideal(a^16,a-b^16,b-c^16,c-d^15).interreduced_basis()
[d^61440, c - d^15, b - d^240, a - d^3840]

I stopped the following after more than an hour, which leads me to believe that Sage is stuck in an infinite loop:

sage: R.<a,b,c,d>=PolynomialRing(QQ,order="lex")
sage: ideal(a^16,a-b^16,b-c^16,c-d^16).interreduced_basis()

The only difference between the two is that the power of d in the input binomial involving c as the initial term is increased from 15 to 16. This difference has no mathematical significance and should have no impact on the computation time.

I suspect that the reason is that by default Sage uses Singular to implement interreduced_basis, and Singular has limitations on the size of exponents. See http://www.singular.uni-kl.de/Manual/latest/sing_343.htm#SEC384 which in particular says

the maximal allowed exponent of a ring variable depends on the ordering of the ring and is at least 32767.

In this case increasing the exponent from 15 to 16 makes the output have an exponent of 16⁴=2¹⁶=65536, while leaving it at 15 puts it just a bit below that, allowing to contain it within a 16 bit integer.

Component: commutative algebra

Keywords: groebner

Issue created by migration from https://trac.sagemath.org/ticket/6473

sagemath / sage

ideal.interreduced_basis hangs forever #6473