Ask Your Question
0

Performance of discriminant calculations over power series rings

asked 2023-11-03 13:01:33 +0100

Marco Castronovo gravatar image

updated 2023-11-03 19:28:12 +0100

Let $P=\mathbb{Q}[t_1,\ldots ,t_n]$ be the ring of polynomials of variables $t_1,\ldots ,t_n$ with rational coefficients, and let $S=P[[q]]$ be the ring of power series of variable $q$ with coefficients in $P$. Given a polynomial $p\in S[x]$ of variable $x$ with coefficients in $S$, denote $\Delta(p)=\operatorname{resultant}(p(x),p'(x))\in S$ the discriminant of $p$, which is the resultant of $p(x)$ and its $x$-derivative $p'(x)$. What is the performance of SageMath in computing $\Delta(p)$ modulo $q^A$ for a given $A\in\mathbb{N}$?

I'm interested in a theoretical answer describing the complexity class of the algorithms used by SageMath, as well as in an empirical answer estimating how much time it would take to do this calculation in the case below, where $n=4$, $A=2$, and $p(x)$ is as shown. It doesn't seem to terminate in any reasonable time on a laptop.

P.<t2,t3,t4,t5> = PolynomialRing(QQ)
S.<q> = PowerSeriesRing(R, default_prec=2)
p = x^6 + ((-1/6*t2^3 - t2^2*t3 - 1/2*t2*t3^2 - 2*t2*t4 - t3*t4 - 2*t5)*q)*x^5 + ((28*t2*t3 - 32*t4*t5)*q + (1/6*t2^5*t3 - 1/6*t2^4*t3^2 + 1/2*t2^3*t3^3 + 1/3*t2^4*t4 + 5/3*t2^3*t3*t4 + 2*t2^2*t3^2*t4 + 3/2*t2^2*t4^2 + 2*t2*t3*t4^2 + 1/3*t2^3*t5 - 6*t2^2*t3*t5 + t2*t3^2*t5 + 9*t2*t4*t5^2 + 3*t2*t4*t5 + 2*t3*t4*t5)*q^2)*x^4 + ((-2/3*t2^4*t3 - 104/3*t2^3*t3^2 - 8*t2^2*t3^3 + 16/3*t2^3*t4*t5 + 40*t2^2*t3*t4*t5 + 16*t2*t3^2*t4*t5 + 18*t2^3*t4 - 44*t2^2*t3*t4 + 8*t2*t3^2*t4 + 96*t2*t4^2*t5 + 32*t3*t4^2*t5 + 48*t2*t4^2 + 24*t3*t4^2 + 33*t2^2*t5 - 152*t2*t3*t5 + 33*t3^2*t5 + 224*t4*t5^2 + 80*t4*t5)*q^2 + (-1/12*t2^7*t3^2 + 1/6*t2^6*t3^3 - 1/3*t2^5*t3^4 + 1/12*t2^6*t3*t4 + 7/6*t2^5*t3^2*t4 + 1/12*t2^4*t3^3*t4 + 1/12*t2^5*t4^2 + 8/3*t2^4*t3*t4^2 + 23/12*t2^3*t3^2*t4^2 - 7/6*t2^5*t3*t5 + 4/3*t2^4*t3^2*t5 - 11/2*t2^3*t3^3*t5 + 3/2*t2^4*t4*t5^2 + 15/2*t2^2*t3^2*t4*t5^2 + 2*t2^3*t4^3 + 7/2*t2^2*t3*t4^3 + 1/6*t2^4*t4*t5 + 17/3*t2^3*t3*t4*t5 - 19/2*t2^2*t3^2*t4*t5 + 15*t2*t3*t4^2*t5^2 + 2*t2*t4^4 + 6*t2^2*t4^2*t5 - 5*t2*t3*t4^2*t5 - 1/6*t2^3*t5^2 + 3*t2^2*t3*t5^2 - 1/2*t2*t3^2*t5^2 + 12*t4^3*t5^2 + 4*t4^3*t5 + 6*t2*t4*t5^2 - t3*t4*t5^2 + 2*t5^3)*q^3)*x^3 + ((-9*t2^4 + 16*t2^3*t3 + 178*t2^2*t3^2 + 16*t2*t3^3 - 9*t3^4 - 32*t2^2*t4*t5 - 448*t2*t3*t4*t5 - 32*t3^2*t4*t5 + 256*t4^2*t5^2 + 128*t2^2*t4 - 256*t2*t3*t4 + 128*t3^2*t4 + 512*t4^2*t5 + 256*t4^2)*q^2 + (-26/9*t2^6*t3^2 + 16/3*t2^5*t3^3 - 2/3*t2^4*t3^4 - 4/3*t2^5*t3*t4*t5 - 20/3*t2^4*t3^2*t4*t5 - 4*t2^3*t3^3*t4*t5 - 10*t2^5*t3*t4 + 24*t2^4*t3^2*t4 - 22/3*t2^3*t3^3*t4 + 8*t2^4*t4^2*t5 - 16/3*t2^3*t3*t4^2*t5 + 24*t2^2*t3^2*t4^2*t5 - 8*t2^4*t4^2 + 18*t2^3*t3*t4^2 - 16*t2^2*t3^2*t4^2 - 311/3*t2^4*t3*t5 + 57*t2^3*t3^2*t5 - 145*t2^2*t3^3*t5 + 16*t2^2*t4^3*t5 + 64*t2*t3*t4^3*t5 + 344/3*t2^3*t4*t5^2 - 148*t2^2*t3*t4*t5^2 + 192*t2*t3^2*t4*t5^2 + 144*t2*t4^2*t5^3 + 8*t2^2*t4^3 - 118/3*t2^3*t4*t5 + 23*t2^2*t3*t4*t5 - 50*t2*t3^2*t4*t5 + 64*t4^4*t5 + 48*t2*t4^2*t5^2 + 80*t3*t4^2*t5^2 + 32*t4^4 - 36*t2*t4^2*t5 + 24*t3*t4^2*t5 - 66*t2^2*t5^2 + 194*t2*t3*t5^2 - 66*t3^2*t5^2 - 208*t4*t5^3 - 96*t4*t5^2)*q^3 + (-5/72*t2^8*t3^4 - 11/36*t2^7*t3^3*t4 - 19/36*t2^6*t3^2*t4^2 - 7/6*t2^6*t3^3*t5 + t2^5*t3^2*t4*t5^2 - 13/12*t2^5*t3*t4^3 - 4*t2^5*t3^2*t4*t5 + 7/2*t2^4*t3*t4^2*t5^2 - 5/6*t2^4*t4^4 - 17/3*t2^4*t3*t4^2*t5 - 19/6*t2^4*t3^2*t5^2 + t2^3*t4^3*t5^2 + 3*t2^3*t3*t4*t5^3 - 14/3*t2^3*t4^3*t5 - 7/3*t2^3*t3*t4*t5^2 - 6*t2^2*t4^2*t5^3 - 19/2*t2^2*t4^2*t5^2 + 4*t2^2*t3*t5^3 - 9*t2*t4*t5^4 - 7*t2*t4*t5^3 - t5^4)*q^4)*x^2 + ((55/3*t2^6*t3 - 28*t2^5*t3^2 - 198*t2^4*t3^3 - 196/3*t2^3*t3^4 + 25*t2^2*t3^5 - 56/3*t2^5*t4*t5 + 224/3*t2^4*t3*t4*t5 + 520*t2^3*t3^2*t4*t5 + 192*t2^2*t3^3*t4*t5 - 32*t2*t3^4*t4*t5 - 272/3*t2^3*t4^2*t5^2 - 384*t2^2*t3*t4^2*t5^2 - 176*t2*t3^2*t4^2*t5^2 + 26/3*t2^5*t4 - 52/3*t2^4*t3*t4 + 120*t2^3*t3^2*t4 - 68*t2^2*t3^3*t4 + 10*t2*t3^4*t4 - 16/3*t2^3*t4^2*t5 + 144*t2^2*t3*t4^2*t5 + 368*t2*t3^2*t4^2*t5 - 16*t3^3*t4^2*t5 - 256*t2*t4^3*t5^2 - 256*t3*t4^3*t5^2 - 272/3*t2^3*t4^2 + 376*t2^2*t3*t4^2 + 224*t2*t3^2*t4^2 - 8*t3^3*t4^2 + 18*t2^4*t5 - 288*t2^3*t3*t5 - 484*t2^2*t3^2*t5 - 288*t2*t3^3*t5 + 18*t3^4*t5 - 384*t2*t4^3*t5 - 128*t3*t4^3*t5 + 416*t2^2*t4*t5^2 + 704*t2*t3*t4*t5^2 + 416*t3^2*t4*t5^2 - 128*t2*t4^3 + 128*t3*t4^3 + 32*t2^2*t4*t5 + 448*t2*t3*t4*t5 + 32*t3^2*t4*t5)*q^3 + (17/18*t2^8*t3^3 + 4/9*t2^7*t3^4 + 1/3*t2^6*t3^5 - 2/3*t2^7*t3^2*t4*t5 - 8/3*t2^6*t3^3*t4*t5 - 2*t2^5*t3^4*t4*t5 + 40/9*t2^7*t3^2*t4 + 44/9*t2^6*t3^3*t4 + 22/3*t2^5*t3^4*t4 - 4*t2^6*t3*t4^2*t5 - 40/3*t2^5*t3^2*t4^2*t5 - 12*t2^4*t3^3*t4^2*t5 + 25/3*t2^6*t3*t4^2 + 40/3*t2^5*t3^2*t4^2 + 58/3*t2^4*t3^3*t4^2 + 100/3*t2^6*t3^2*t5 - 39*t2^5*t3^3*t5 + 166/3*t2^4*t3^4*t5 - 16/3*t2^5*t4^3*t5 - 24*t2^4*t3*t4^3*t5 - 24*t2^3*t3^2*t4^3*t5 - 184/3*t2^5*t3*t4*t5^2 + 128/3*t2^4*t3^2*t4*t5^2 - 156*t2^3*t3^3*t4*t5^2 + 24*t2^4*t4^2*t5^3 + 120*t2^2*t3^2*t4^2*t5^3 + 11/3*t2^5*t4^3 + 16/3*t2^4*t3*t4^3 + 10*t2^3*t3^2*t4^3 + 359/6*t2^5*t3*t4*t5 - 349/3*t2^4*t3^2*t4*t5 + 251/6*t2^3*t3^3*t4*t5 - 80/3*t2^3*t4^4*t5 - 16*t2^2*t3*t4^4*t5 - 130/3*t2^4*t4^2*t5^2 + 448/3*t2^3*t3*t4^2*t5^2 - 220*t2^2*t3^2*t4^2*t5^2 + 240*t2*t3*t4^3*t5^3 - 40/3*t2^3*t4^4 - 4*t2^2*t3*t4^4 + 61/2*t2^4*t4^2*t5 - 38/3*t2^3*t3*t4^2*t5 - 239/2*t2^2*t3^2*t4^2*t5 + 13*t2^4*t3*t5^2 - 556/3*t2^3*t3^2*t5^2 + 163*t2^2*t3^3*t5^2 - 32*t2^2*t4^3*t5^2 - 8*t2*t3*t4^3*t5^2 + 17*t2^3*t4*t5^3 + 192*t2^2*t3*t4*t5^3 - 223*t2*t3^2*t4*t5^3 + 192*t4^4*t5^3 - 32*t2^2*t4^3*t5 - 124*t2*t3*t4^3*t5 + 67*t2^3*t4*t5^2 + 14*t2^2*t3*t4*t5^2 + 229*t2*t3^2*t4*t5^2 + 192*t4^4*t5^2 - 240*t2*t4^2*t5^3 - 400*t3*t4^2*t5^3 + 48*t4^4*t5 - 104*t2*t4^2*t5^2 - 144*t3*t4^2*t5^2 + 33*t2^2*t5^3 + 20*t2*t3*t5^3 + 33*t3^2*t5^3 - 224*t4*t5^4 - 80*t4*t5^3)*q^4)*x + (-76/9*t2^8*t3^2 - 10*t2^7*t3^3 + 4*t2^6*t3^4 - 22*t2^5*t3^5 - 64/3*t2^4*t3^6 + 52/3*t2^7*t3*t4*t5 + 112/3*t2^6*t3^2*t4*t5 + 20/3*t2^5*t3^3*t4*t5 + 64*t2^4*t3^4*t4*t5 + 56*t2^3*t3^5*t4*t5 - 8*t2^6*t4^2*t5^2 - 64/3*t2^5*t3*t4^2*t5^2 - 80/3*t2^4*t3^2*t4^2*t5^2 - 64*t2^3*t3^3*t4^2*t5^2 - 40*t2^2*t3^4*t4^2*t5^2 - 25/2*t2^7*t3*t4 - 130/3*t2^6*t3^2*t4 - 235/3*t2^5*t3^3*t4 - 58*t2^4*t3^4*t4 - 103/6*t2^3*t3^5*t4 + 32/3*t2^6*t4^2*t5 + 400/3*t2^5*t3*t4^2*t5 + 272*t2^4*t3^2*t4^2*t5 + 256*t2^3*t3^3*t4^2*t5 + 80*t2^2*t3^4*t4^2*t5 - 256/3*t2^4*t4^3*t5^2 - 736/3*t2^3*t3*t4^3*t5^2 - 256*t2^2*t3^2*t4^3*t5^2 - 80*t2*t3^3*t4^3*t5^2 - 9/2*t2^6*t4^2 + 28/3*t2^5*t3*t4^2 - 337/3*t2^4*t3^2*t4^2 + 36*t2^3*t3^3*t4^2 + 79/2*t2^2*t3^4*t4^2 - 7*t2^6*t3*t5 - 554/3*t2^4*t3^3*t5 - 240*t2^3*t3^4*t5 - 51*t2^2*t3^5*t5 + 16*t2^4*t4^3*t5 + 976/3*t2^3*t3*t4^3*t5 + 160*t2^2*t3^2*t4^3*t5 + 5/3*t2^5*t4*t5^2 + 88*t2^4*t3*t4*t5^2 + 482*t2^3*t3^2*t4*t5^2 + 520*t2^2*t3^3*t4*t5^2 + 71*t2*t3^4*t4*t5^2 - 256*t2^2*t4^4*t5^2 - 256*t2*t3*t4^4*t5^2 - 64*t3^2*t4^4*t5^2 - 128*t2^3*t4^2*t5^3 - 352*t2^2*t3*t4^2*t5^3 - 256*t2*t3^2*t4^2*t5^3 + 88/3*t2^4*t4^3 + 92/3*t2^3*t3*t4^3 + 112*t2^2*t3^2*t4^3 + 36*t2*t3^3*t4^3 - 43/3*t2^5*t4*t5 + 68*t2^4*t3*t4*t5 - 362*t2^3*t3^2*t4*t5 - 196*t2^2*t3^3*t4*t5 - 61*t2*t3^4*t4*t5 - 128*t2^2*t4^4*t5 - 192*t2*t3*t4^4*t5 - 64*t3^2*t4^4*t5 + 944*t2^2*t3*t4^2*t5^2 + 544*t2*t3^2*t4^2*t5^2 + 112*t3^3*t4^2*t5^2 - 512*t2*t4^3*t5^3 - 256*t3*t4^3*t5^3 - 16*t2^2*t4^4 - 32*t2*t3*t4^4 - 16*t3^2*t4^4 + 80*t2^3*t4^2*t5 + 296*t2^2*t3*t4^2*t5 + 256*t2*t3^2*t4^2*t5 + 40*t3^3*t4^2*t5 - 9*t2^4*t5^2 - 240*t2^3*t3*t5^2 - 718*t2^2*t3^2*t5^2 - 240*t2*t3^3*t5^2 - 9*t3^4*t5^2 - 640*t2*t4^3*t5^2 - 384*t3*t4^3*t5^2 + 384*t2^2*t4*t5^3 + 1280*t2*t3*t4*t5^3 + 384*t3^2*t4*t5^3 - 256*t4^2*t5^4 - 128*t2*t4^3*t5 - 128*t3*t4^3*t5 + 96*t2^2*t4*t5^2 + 320*t2*t3*t4*t5^2 + 96*t3^2*t4*t5^2 - 512*t4^2*t5^3 - 256*t4^2*t5^2)*q^4 + (157/12*t2^7*t3^4*t5 - 32*t2^6*t3^3*t4*t5^2 + 16*t2^5*t3^2*t4^2*t5^3 + 185/3*t2^6*t3^3*t4*t5 - 128*t2^5*t3^2*t4^2*t5^2 + 56*t2^4*t3*t4^3*t5^3 + 129/2*t2^5*t3^2*t4^2*t5 + 53*t2^5*t3^3*t5^2 - 96*t2^4*t3*t4^3*t5^2 - 98*t2^4*t3^2*t4*t5^3 + 16*t2^3*t4^4*t5^3 + 48*t2^3*t3*t4^2*t5^4 + 27/2*t2^4*t3*t4^3*t5 + 50*t2^4*t3^2*t4*t5^2 - 32*t2^3*t4^4*t5^2 + 47*t2^3*t3*t4^2*t5^3 - 96*t2^2*t4^3*t5^4 - 14*t2^3*t4^4*t5 + 50*t2^3*t3*t4^2*t5^2 + 71*t2^3*t3^2*t5^3 - 60*t2^2*t4^3*t5^3 + 54*t2^2*t3*t4*t5^4 - 144*t2*t4^2*t5^5 - 36*t2^2*t4^3*t5^2 + 213*t2^2*t3*t4*t5^3 - 144*t2*t4^2*t5^4 + 12*t2*t4^2*t5^3 - 90*t2*t3*t5^4 + 240*t4*t5^5 + 96*t4*t5^4)*q^5
Delta = p.resultant(p.differentiate())
edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
0

answered 2023-11-03 21:27:07 +0100

Max Alekseyev gravatar image

First off, the code appears to be incomplete as neither R nor x is defined. Per textual description, the set-up should be

P.<t2,t3,t4,t5> = PolynomialRing(QQ)
S.<q> = PowerSeriesRing(P, default_prec=2)
R.<x> = PolynomialRing(S)

Next, the discriminant can be computed directly as p.discriminant().

Finally, there seems to be a misunderstanding of what default precision is. Per documentation:

default_prec – the default precision used if an exact object must be changed to an approximate object in order to do an arithmetic operation. [...] The default precision is specified at construction, but does not bound the precision of created elements.

In your code, the coefficients of p are specified as exact and thus have infinite precision. Hence, the discriminant is not computed modulo q^2 but exactly, In order to perform computation modulo q^2, the precision of the coefficients has to be changed to 2 first:

p.map_coefficients(lambda t: t.add_bigoh(2)).discriminant()

which instantly returns O(q^10).

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2023-11-03 13:01:33 +0100

Seen: 157 times

Last updated: Nov 03 '23