factorization on number fields

asked 2017-12-12 10:28:25 -0500 This post is a wiki. Anyone with karma >750 is welcome to improve it.

I am trying to factor a division polynomial on a number field and I get the following error. "PariError: inconsistent concatenation t_COL (16 elts) , t_VEC (8 elts)" Could you please tell me how I can rectify it?

Thank you very much in advance!

Here is the code I am trying to compile:

K.<rho> = NumberField(x^16 - 7x^12 + 48x^8 - 7x^4 + 1) Kx.<x> = K[] P = 2x^24 - 220779/1250x^22 + 10143441/15625x^21 - 142856857143/25000000x^20 + 131732868267/19531250x^19 + 31020130846593/5000000000x^18 + 13930920190065879/1562500000000x^17 - 421500204770774287041/5000000000000000x^16 - 31485474287738310861/976562500000000x^15 + 2518173788725346513398533/6250000000000000000x^14 - 582641643196535738602059/3125000000000000000x^13 - 73639749524289565897523550321/125000000000000000000000x^12 + 20820019744955833474743619767/48828125000000000000000x^11 + 300689661910158431801904075908157/625000000000000000000000000x^10 - 4454385478020717587635582204420833/7812500000000000000000000000x^9 + 16361877508124295728413974125123451/400000000000000000000000000000x^8 + 1573027301404166809168217933184311901/9765625000000000000000000000000x^7 - 11987294796540068181333112421577867214431/125000000000000000000000000000000000x^6 + 113700674422931989849194398791831231927941/1562500000000000000000000000000000000x^5 - 168139864900386988616344904823569275391618007/2500000000000000000000000000000000000000x^4 + 2632186130949079940307397635576696383706753/78125000000000000000000000000000000000x^3 - 116064304293562967834364362386796558774110963539/12500000000000000000000000000000000000000000x^2 + 206061630034967578571315740889755584982886782011/156250000000000000000000000000000000000000000x - 30099620598750107945851944211328293200688722593391/500000000000000000000000000000000000000000000000

print P.parent()==Kx

print P.roots()

edit retag close merge delete

To display inline code, like f, use backticks.

To display blocks of code or error messages, separate them by a blank line from the rest of the text, and do one of the following (all give the same result):

• indent all code lines with 4 spaces
• select code lines and click the "code" button (the icon with '101 010')
• select code lines and hit ctrl-K

For instance, typing

If we define f by

def f(x, y):
return (x, y)

then f(2, 3) returns (2, 3) but f(2) gives:

TypeError: f() takes exactly 2 arguments (1 given)

produces:

If we define f by

def f(x, y):
return (x, y)

then f(2, 3) returns (2, 3) but f(2) gives:

TypeError: f() takes exactly 2 arguments (1 given)

Please edit your question to do that.

Tip: don't tick the "community wiki" checkbox when posting questions.

The "community wiki" tag is for questions that are not about Sage, but about Ask Sage itself.

Also, with the "community wiki" checkbox ticked, upvotes to your post don't earn you karma.

You need karma to be able to post links, to upvote questions and answers by others, etc.

Sort by » oldest newest most voted

The final message of the question is to find the roots. (Not to avoid an error, i had to wait some time, no result and no error were shown.)

Sometimes is better to break somehow / anyhow the polynomials, if possible, so that the algorithms used certainly use the simpler pieces. (We always suppose this is the case, but...)

The following code uses as input a polynomial Q, note that the posted P is related to Q via:

# P = 2 * Q( 100*x ) / 10^48

The following code then finds the roots in the given field without waiting. The trick was to use the intermediate field obtained from the posted polynomial by substituting x^4 to a new variable.

The code is:

R.<x> = QQ[]
Q = ( x^24
- 883116*x^22
+ 324590112*x^21
- 285713714286*x^20
+ 33723614276352*x^19
+ 3102013084659300*x^18
+ 445789446082108128*x^17
- 421500204770774287041*x^16
- 16120562835322015160832*x^15
+ 20145390309802772107188264*x^14
- 932226629114457181763294400*x^13
- 294558998097158263590094201284*x^12
+ 21319700218834773478137466641408*x^11
+ 2405517295281267454415232607265256*x^10
- 285080670593325925608677261082933312*x^9
+ 2045234688515536966051746765640431375*x^8
+ 805389978318933406294127581790367693312*x^7
- 47949179186160272725332449686311468857724*x^6
+ 3638421581533823675174220761338599421694112*x^5
- 336279729800773977232689809647138550783236014*x^4
+ 16845991238074111617967344867690856855723219200*x^3
- 464257217174251871337457449547186235096443854156*x^2
+ 6593972161118962514282103708472178719452377024352*x
- 30099620598750107945851944211328293200688722593391 )

# P = 2 * Q( 100*x ) / 10^48

L.<u> = NumberField( x^4  - 7*x^3  + 48*x^2 - 7*x   + 1)
K.<t> = NumberField( x^16 - 7*x^12 + 48*x^8 - 7*x^4 + 1)
emb   = [ emb for emb in L.embeddings(K) if emb(u) == t^4 ]

RL.<X> = L[]
RK.<Y> = K[]

print "Q has the following roots in L:"
for root in Q.roots( ring=L, multiplicities=False ):
print root

print "\nQ has the following factors in L[X]:"
for f, mul in RL(Q).factor():
print
print f

fcoeffs = f.coefficients( sparse=False )
g = sum( [ emb( fcoeffs[k] ) * Y^k for k in range(len(fcoeffs)) ] )
print "image of f is g, the following polynomial:"
print g
print "roots of g in K:"
for root in g.roots( ring=K, multiplicities=False ):
print root

The results are not shown here.

But in order to see why it works, here is the intermediate step:

sage: for f, mul in RL(Q).factor():
....:     print f
....:
X - 15/4*u^3 - 123/4
X - 3/4*u^3 - 351/4
X + 3/4*u^3 + 615/4
X + 15/4*u^3 + 4707/4
X^2 + (-24*u^3 + 168*u^2 - 1128*u + 150)*X + 2448*u^3 - 17136*u^2 + 115056*u - 7479
X^2 + (-u^3 - 275)*X + 102*u^3 + 35871
X^2 + (u^3 + 47)*X - 102*u^3 + 3027
X^2 + (24*u^3 - 168*u^2 + 1128*u - 18)*X - 2448*u^3 + 17136*u^2 - 115056*u + 9657
X^4 - 948*X^3 + 25974*X^2 + 10203948*X - 81103599
X^4 + (-84*u^3 + 576*u^2 - 4032*u + 216)*X^3 + (3024*u^3 - 20736*u^2 + 145152*u - 15930)*X^2 + (474012*u^3 - 3250368*u^2 + 22752576*u + 3635496)*X + 9330552*u^3 - 63980928*u^2 + 447866496*u - 210398391
X^4 + (84*u^3 - 576*u^2 + 4032*u - 384)*X^3 + (-3024*u^3 + 20736*u^2 - 145152*u + 5670)*X^2 + (-474012*u^3 + 3250368*u^2 - 22752576*u + 7021296)*X - 9330552*u^3 + 63980928*u^2 - 447866496*u - 143751591

Now pari has a much simpler job to find the roots. The above factors over L are moved to polynomials over K, their roots are calculated immediately...

more