In [13]:
def polgen(n):
n0=n//2
L=[[1]]+[[1]]+[[-1,1] for k in [1..n0-1]]
CP=cartesian_product(L)
plist=[sum(k[t]*x^(n-t) for t in [0..n0]) for k in CP]
return plist
def CBound(f):
cf=[k[0] for k in f.coefficients()]
cf.reverse()
cf0=abs(cf[0])
cf1=[(abs(k)+2)/cf0 for k in cf]
return ceil(max(cf1)+1)
@parallel(ncpus=128)
def LWood(f):
df0=ZZ(f.degree(x))//2
f0=f-sum(x^k for k in [0..df0-1])
p0=taylor(sqrt(f0),x,infinity,0)
p0den=p0.denominator()
P1=expand(f0-(p0-1/p0den)^2)
P2=expand(f0-(p0+1/p0den)^2)
b=max(CBound(P1),CBound(P2))
CP=cartesian_product([[-1,1] for k in [1..df0]])
SOL=[]
for k in CP:
F=pari(f+sum(k[t]*x^t for t in [0..df0-1]))
SOL=SOL+[(F,F.hyperellratpoints([b,1]),b)]
return SOL
In [19]:
%%time
BMAX=0
for X,Y in list(LWood(polgen(12))):
for k in Y:
BMAX=max(BMAX,k[2])
if len(k[1])>0:
if max([abs(r[0]) for r in k[1]])>2:
print(k)
print("max bound=",BMAX)
(x^12 + x^11 - x^10 - x^9 - x^8 + x^7 - x^6 - x^5 + x^4 - x^3 + x^2 + x + 1, [[-3, 553], [-3, -553], [-1, 1], [-1, -1], [0, 1], [0, -1], [1, 1], [1, -1]], 2538) (x^12 + x^11 - x^10 + x^9 + x^8 - x^7 + x^6 - x^5 - x^4 + x^3 + x^2 + x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [3, 821], [3, -821]], 1596) (x^12 + x^11 + x^10 - x^9 - x^8 - x^7 + x^6 + x^5 - x^4 + x^3 - x^2 - x + 1, [[-3, 655], [-3, -655], [-1, 1], [-1, -1], [0, 1], [0, -1], [1, 1], [1, -1]], 1859) max bound= 5374 CPU times: user 167 ms, sys: 175 ms, total: 341 ms Wall time: 1.04 s
In [20]:
%%time
BMAX=0
for X,Y in list(LWood(polgen(14))):
for k in Y:
BMAX=max(BMAX,k[2])
if len(k[1])>0:
if max([abs(r[0]) for r in k[1]])>2:
print(k)
print("max bound=",BMAX)
(x^14 + x^13 - x^12 - x^11 - x^10 + x^9 + x^8 + x^7 - x^6 + x^5 - x^4 + x^3 + x^2 + x + 1, [[-3, 1661], [-3, -1661], [0, 1], [0, -1]], 4438) (x^14 + x^13 - x^12 + x^11 - x^10 - x^9 - x^8 + x^7 - x^6 - x^5 + x^4 - x^3 - x^2 + x + 1, [[0, 1], [0, -1], [3, 2437], [3, -2437]], 11848) (x^14 + x^13 - x^12 + x^11 + x^10 - x^9 - x^8 + x^7 + x^6 + x^5 - x^4 + x^3 - x^2 + x + 1, [[-3, 1597], [-3, -1597], [0, 1], [0, -1]], 5470) (x^14 + x^13 + x^12 - x^11 - x^10 + x^9 + x^8 + x^7 - x^6 + x^5 + x^4 - x^3 + x^2 - x + 1, [[-3, 1955], [-3, -1955], [0, 1], [0, -1]], 3806) (x^14 + x^13 + x^12 + x^11 + x^10 - x^9 - x^8 + x^7 + x^6 - x^5 - x^4 + x^3 + x^2 - x + 1, [[-3, 1901], [-3, -1901], [0, 1], [0, -1]], 4036) (x^14 + x^13 + x^12 + x^11 - x^10 + x^9 - x^8 + x^7 + x^6 + x^5 - x^4 - x^3 - x^2 + x + 1, [[-3, 1859], [-3, -1859], [0, 1], [0, -1]], 5104) max bound= 19712 CPU times: user 365 ms, sys: 406 ms, total: 771 ms Wall time: 1.3 s
In [21]:
%%time
BMAX=0
for X,Y in list(LWood(polgen(16))):
for k in Y:
BMAX=max(BMAX,k[2])
if len(k[1])>0:
if max([abs(r[0]) for r in k[1]])>2:
print(k)
print("max bound=",BMAX)
(x^16 + x^15 - x^14 - x^13 - x^12 - x^11 - x^10 - x^9 - x^8 + x^7 - x^6 - x^5 - x^4 - x^3 + x^2 - x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [3, 7087], [3, -7087]], 88049) (x^16 + x^15 - x^14 - x^13 - x^12 - x^11 - x^10 - x^9 - x^8 - x^7 - x^6 + x^5 - x^4 - x^3 + x^2 - x + 1, [[-3, 5011], [-3, -5011], [-1, 1], [-1, -1], [0, 1], [0, -1]], 88049) (x^16 + x^15 - x^14 - x^13 - x^12 + x^11 + x^10 - x^9 + x^8 - x^7 + x^6 + x^5 - x^4 - x^3 - x^2 + x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [1, 1], [1, -1], [3, 7121], [3, -7121]], 57161) (x^16 + x^15 - x^14 - x^13 + x^12 - x^11 - x^10 - x^9 + x^8 + x^7 + x^6 - x^5 - x^4 - x^3 + x^2 + x + 1, [[-3, 5117], [-3, -5117], [0, 1], [0, -1], [1, 1], [1, -1]], 87565) (x^16 + x^15 - x^14 - x^13 + x^12 + x^11 + x^10 + x^9 - x^8 - x^7 - x^6 - x^5 - x^4 - x^3 + x^2 + x + 1, [[-3, 5089], [-3, -5089], [-1, 1], [-1, -1], [0, 1], [0, -1], [1, 1], [1, -1]], 62545) (x^16 + x^15 - x^14 + x^13 + x^12 - x^11 + x^10 + x^9 - x^8 + x^7 - x^6 + x^5 + x^4 + x^3 + x^2 + x + 1, [[0, 1], [0, -1], [1, 3], [1, -3], [5, 422409], [5, -422409]], 80689) (x^16 + x^15 + x^14 + x^13 + x^12 - x^11 - x^10 + x^9 - x^8 - x^7 + x^6 + x^5 - x^4 + x^3 + x^2 - x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [3, 8005], [3, -8005]], 66103) (x^16 + x^15 + x^14 + x^13 + x^12 - x^11 + x^10 + x^9 + x^8 + x^7 - x^6 - x^5 + x^4 + x^3 + x^2 - x + 1, [[-3, 5713], [-3, -5713], [0, 1], [0, -1], [1, 3], [1, -3]], 71573) (x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 - x^9 + x^8 + x^7 - x^6 + x^5 - x^4 + x^3 + x^2 - x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [1, 3], [1, -3], [3, 8033], [3, -8033]], 64540) max bound= 671205 CPU times: user 1.59 s, sys: 1.06 s, total: 2.65 s Wall time: 2.67 s
In [22]:
%%time
BMAX=0
for X,Y in list(LWood(polgen(18))):
for k in Y:
BMAX=max(BMAX,k[2])
if len(k[1])>0:
if max([abs(r[0]) for r in k[1]])>2:
print(k)
print("max bound=",BMAX)
(x^18 + x^17 - x^16 - x^15 - x^14 - x^13 - x^12 - x^11 + x^10 - x^9 - x^8 + x^7 + x^6 + x^5 + x^4 - x^3 + x^2 - x + 1, [[0, 1], [0, -1], [3, 21263], [3, -21263]], 176452) (x^18 + x^17 - x^16 - x^15 - x^14 + x^13 - x^12 - x^11 - x^10 - x^9 + x^8 + x^7 - x^6 - x^5 - x^4 + x^3 - x^2 + x + 1, [[-3, 14927], [-3, -14927], [0, 1], [0, -1]], 261441) (x^18 + x^17 - x^16 - x^15 + x^14 - x^13 + x^12 - x^11 - x^10 - x^9 + x^8 - x^7 - x^6 + x^5 - x^4 + x^3 - x^2 - x + 1, [[-3, 15383], [-3, -15383], [0, 1], [0, -1]], 295124) (x^18 + x^17 - x^16 - x^15 + x^14 + x^13 - x^12 + x^11 + x^10 + x^9 + x^8 + x^7 - x^6 + x^5 - x^4 + x^3 - x^2 - x + 1, [[-3, 15235], [-3, -15235], [0, 1], [0, -1]], 156977) (x^18 + x^17 - x^16 + x^15 - x^14 - x^13 + x^12 - x^11 - x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 - x^3 + x^2 - x + 1, [[-3, 14083], [-3, -14083], [0, 1], [0, -1]], 686789) (x^18 + x^17 + x^16 + x^15 - x^14 - x^13 + x^12 + x^11 + x^10 - x^9 + x^8 + x^7 - x^6 + x^5 - x^4 - x^3 + x^2 - x + 1, [[-3, 16859], [-3, -16859], [0, 1], [0, -1]], 171324) (x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 - x^11 - x^10 + x^9 + x^8 - x^7 - x^6 - x^5 - x^4 + x^3 + x^2 - x + 1, [[-3, 17053], [-3, -17053], [0, 1], [0, -1]], 127366) max bound= 3341457 CPU times: user 7.28 s, sys: 3 s, total: 10.3 s Wall time: 10.5 s
In [23]:
%%time
BMAX=0
for X,Y in list(LWood(polgen(20))):
for k in Y:
BMAX=max(BMAX,k[2])
if len(k[1])>0:
if max([abs(r[0]) for r in k[1]])>2:
print(k)
print("max bound=",BMAX)
(x^20 + x^19 - x^18 - x^17 - x^16 + x^15 + x^14 + x^13 - x^12 - x^11 - x^10 + x^9 + x^8 - x^7 + x^6 - x^5 - x^4 + x^3 - x^2 + x + 1, [[-3, 44851], [-3, -44851], [0, 1], [0, -1], [1, 1], [1, -1]], 1127602) (x^20 + x^19 - x^18 - x^17 + x^16 - x^15 + x^14 - x^13 + x^12 - x^11 - x^10 + x^9 + x^8 - x^7 - x^6 + x^5 + x^4 - x^3 + x^2 - x + 1, [[-3, 46159], [-3, -46159], [-1, 3], [-1, -3], [0, 1], [0, -1], [1, 1], [1, -1]], 1627745) (x^20 + x^19 - x^18 + x^17 + x^16 + x^15 - x^14 - x^13 + x^12 - x^11 - x^10 + x^9 - x^8 - x^7 - x^6 - x^5 + x^4 + x^3 + x^2 - x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [1, 1], [1, -1], [3, 66649], [3, -66649]], 2940305) (x^20 + x^19 + x^18 - x^17 + x^16 - x^15 + x^14 - x^13 + x^12 - x^11 - x^10 - x^9 + x^8 - x^7 - x^6 + x^5 - x^4 + x^3 + x^2 - x + 1, [[-3, 53903], [-3, -53903], [-1, 3], [-1, -3], [0, 1], [0, -1], [1, 1], [1, -1]], 691407) (x^20 + x^19 + x^18 + x^17 + x^16 - x^15 + x^14 - x^13 + x^12 + x^11 + x^10 - x^9 - x^8 + x^7 - x^6 + x^5 + x^4 - x^3 + x^2 + x + 1, [[-3, 51449], [-3, -51449], [0, 1], [0, -1], [1, 3], [1, -3]], 653785) (x^20 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 - x^13 + x^12 + x^11 + x^10 + x^9 - x^8 - x^7 - x^6 + x^5 - x^4 + x^3 - x^2 + x + 1, [[-3, 51169], [-3, -51169], [0, 1], [0, -1], [1, 3], [1, -3]], 553449) max bound= 36063346 CPU times: user 30.7 s, sys: 7.82 s, total: 38.5 s Wall time: 39.7 s
In [24]:
%%time
BMAX=0
for X,Y in list(LWood(polgen(22))):
for k in Y:
BMAX=max(BMAX,k[2])
if len(k[1])>0:
if max([abs(r[0]) for r in k[1]])>2:
print(k)
print("max bound=",BMAX)
(x^22 + x^21 - x^20 - x^19 - x^18 + x^17 + x^16 - x^15 + x^14 - x^13 + x^12 + x^11 + x^10 - x^9 - x^8 + x^7 + x^6 + x^5 + x^4 - x^3 - x^2 + x + 1, [[-3, 134699], [-3, -134699], [0, 1], [0, -1]], 922892) (x^22 + x^21 - x^20 - x^19 + x^18 - x^17 - x^16 + x^15 - x^14 - x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 - x^6 + x^5 + x^4 + x^3 - x^2 - x + 1, [[-3, 138031], [-3, -138031], [0, 1], [0, -1]], 1126588) (x^22 + x^21 - x^20 - x^19 + x^18 - x^17 - x^16 + x^15 - x^14 + x^13 - x^12 - x^11 + x^10 - x^9 - x^8 - x^7 + x^6 - x^5 + x^4 + x^3 - x^2 - x + 1, [[-3, 138017], [-3, -138017], [0, 1], [0, -1]], 2423151) (x^22 + x^21 - x^20 - x^19 + x^18 + x^17 + x^16 - x^15 + x^14 - x^13 + x^12 + x^11 + x^10 + x^9 - x^8 - x^7 + x^6 - x^5 + x^4 + x^3 - x^2 - x + 1, [[-3, 137545], [-3, -137545], [0, 1], [0, -1]], 2550780) (x^22 + x^21 - x^20 - x^19 + x^18 + x^17 + x^16 - x^15 + x^14 + x^13 - x^12 - x^11 + x^10 - x^9 + x^8 + x^7 - x^6 + x^5 + x^4 + x^3 - x^2 - x + 1, [[-3, 137531], [-3, -137531], [0, 1], [0, -1]], 1297195) (x^22 + x^21 - x^20 + x^19 - x^18 + x^17 + x^16 + x^15 + x^14 + x^13 - x^12 - x^11 + x^10 + x^9 - x^8 - x^7 - x^6 + x^5 - x^4 - x^3 + x^2 + x + 1, [[-3, 125645], [-3, -125645], [0, 1], [0, -1]], 107488624) (x^22 + x^21 - x^20 + x^19 + x^18 - x^17 + x^16 + x^15 + x^14 + x^13 - x^12 - x^11 - x^10 - x^9 + x^8 + x^7 - x^6 + x^5 - x^4 + x^3 + x^2 + x + 1, [[0, 1], [0, -1], [3, 199595], [3, -199595]], 1594883) (x^22 + x^21 - x^20 + x^19 + x^18 + x^17 + x^16 + x^15 - x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 - x^7 - x^6 + x^5 + x^4 + x^3 + x^2 + x + 1, [[0, 1], [0, -1], [3, 200221], [3, -200221]], 16820705) (x^22 + x^21 + x^20 - x^19 - x^18 - x^17 - x^16 - x^15 - x^14 - x^13 - x^12 + x^11 + x^10 + x^9 + x^8 - x^7 - x^6 + x^5 - x^4 + x^3 - x^2 + x + 1, [[0, 1], [0, -1], [3, 208771], [3, -208771]], 1267905) (x^22 + x^21 + x^20 + x^19 - x^18 + x^17 - x^16 + x^15 + x^14 + x^13 + x^12 - x^11 + x^10 - x^9 - x^8 + x^7 - x^6 - x^5 + x^4 - x^3 - x^2 + x + 1, [[-3, 150583], [-3, -150583], [0, 1], [0, -1]], 1865260) (x^22 + x^21 + x^20 + x^19 + x^18 + x^17 - x^16 + x^15 - x^14 - x^13 + x^12 - x^11 - x^10 - x^9 - x^8 - x^7 + x^6 + x^5 + x^4 + x^3 - x^2 + x + 1, [[-3, 153113], [-3, -153113], [0, 1], [0, -1]], 1439153) max bound= 204015976 CPU times: user 2min 11s, sys: 28 s, total: 2min 39s Wall time: 2min 42s
In [25]:
%%time
BMAX=0
for X,Y in list(LWood(polgen(24))):
for k in Y:
BMAX=max(BMAX,k[2])
if len(k[1])>0:
if max([abs(r[0]) for r in k[1]])>2:
print(k)
print("max bound=",BMAX)
(x^24 + x^23 - x^22 - x^21 - x^20 - x^19 - x^18 - x^17 - x^16 - x^15 + x^14 + x^13 - x^12 - x^11 - x^10 - x^9 - x^8 + x^7 - x^6 - x^5 + x^4 + x^3 + x^2 - x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [3, 574033], [3, -574033]], 16149580) (x^24 + x^23 - x^22 - x^21 + x^20 + x^19 - x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 - x^11 + x^10 + x^9 - x^8 - x^7 + x^6 - x^5 - x^4 - x^3 - x^2 + x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [3, 582397], [3, -582397]], 10836044) (x^24 + x^23 - x^22 - x^21 + x^20 + x^19 + x^18 - x^17 - x^16 + x^15 + x^14 + x^13 - x^12 - x^11 - x^10 - x^9 - x^8 + x^7 - x^6 - x^5 + x^4 + x^3 + x^2 - x + 1, [[-3, 412495], [-3, -412495], [-1, 1], [-1, -1], [0, 1], [0, -1], [1, 1], [1, -1]], 9650332) (x^24 + x^23 - x^22 + x^21 - x^20 - x^19 + x^18 - x^17 - x^16 + x^15 - x^14 - x^13 - x^12 + x^11 - x^10 - x^9 - x^8 - x^7 - x^6 - x^5 - x^4 + x^3 - x^2 + x + 1, [[0, 1], [0, -1], [3, 592643], [3, -592643]], 570439925) (x^24 + x^23 - x^22 + x^21 - x^20 - x^19 + x^18 + x^17 + x^16 - x^15 - x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 - x^7 + x^6 + x^5 + x^4 - x^3 - x^2 + x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [1, 3], [1, -3], [3, 592913], [3, -592913]], 632634490) (x^24 + x^23 - x^22 + x^21 + x^20 + x^19 - x^18 - x^17 - x^16 - x^15 - x^14 - x^13 + x^12 - x^11 - x^10 - x^9 + x^8 - x^7 + x^6 + x^5 + x^4 - x^3 + x^2 + x + 1, [[-3, 385331], [-3, -385331], [0, 1], [0, -1], [1, 1], [1, -1]], 358036888) (x^24 + x^23 - x^22 + x^21 + x^20 + x^19 + x^18 - x^17 + x^16 - x^15 + x^14 - x^13 + x^12 + x^11 - x^10 - x^9 - x^8 - x^7 + x^6 - x^5 - x^4 - x^3 + x^2 - x + 1, [[-1, 3], [-1, -3], [0, 1], [0, -1], [1, 1], [1, -1], [3, 600493], [3, -600493]], 26556076) (x^24 + x^23 - x^22 + x^21 + x^20 + x^19 + x^18 + x^17 - x^16 - x^15 - x^14 - x^13 - x^12 + x^11 + x^10 - x^9 - x^8 - x^7 + x^6 + x^5 + x^4 - x^3 - x^2 - x + 1, [[-3, 385999], [-3, -385999], [-1, 1], [-1, -1], [0, 1], [0, -1], [1, 1], [1, -1]], 271289855) (x^24 + x^23 + x^22 - x^21 - x^20 + x^19 - x^18 + x^17 + x^16 + x^15 - x^14 + x^13 - x^12 - x^11 + x^10 - x^9 - x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1, [[-3, 474325], [-3, -474325], [0, 1], [0, -1], [1, 1], [1, -1]], 43270907) (x^24 + x^23 + x^22 - x^21 + x^20 - x^19 - x^18 - x^17 + x^16 - x^15 + x^14 + x^13 - x^12 + x^11 + x^10 + x^9 + x^8 + x^7 - x^6 - x^5 - x^4 - x^3 - x^2 - x + 1, [[-3, 484333], [-3, -484333], [0, 1], [0, -1], [1, 1], [1, -1]], 17644785) (x^24 + x^23 + x^22 - x^21 + x^20 - x^19 + x^18 - x^17 - x^16 + x^15 + x^14 - x^13 - x^12 - x^11 - x^10 - x^9 - x^8 + x^7 + x^6 + x^5 - x^4 + x^3 - x^2 + x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [1, 1], [1, -1], [3, 632495], [3, -632495]], 34362973) (x^24 + x^23 + x^22 + x^21 - x^20 - x^19 - x^18 + x^17 - x^16 - x^15 - x^14 - x^13 + x^12 - x^11 + x^10 - x^9 + x^8 + x^7 + x^6 + x^5 - x^4 + x^3 - x^2 - x + 1, [[-3, 454241], [-3, -454241], [-1, 1], [-1, -1], [0, 1], [0, -1], [1, 1], [1, -1]], 11038851) (x^24 + x^23 + x^22 + x^21 - x^20 - x^19 + x^18 - x^17 + x^16 + x^15 + x^14 - x^13 - x^12 - x^11 - x^10 - x^9 + x^8 - x^7 - x^6 - x^5 + x^4 - x^3 + x^2 + x + 1, [[-3, 455449], [-3, -455449], [-1, 3], [-1, -3], [0, 1], [0, -1], [1, 1], [1, -1]], 13239592) (x^24 + x^23 + x^22 + x^21 - x^20 + x^19 - x^18 + x^17 - x^16 - x^15 - x^14 - x^13 + x^12 + x^11 + x^10 + x^9 - x^8 - x^7 - x^6 - x^5 + x^4 - x^3 + x^2 - x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [1, 1], [1, -1], [3, 644801], [3, -644801]], 23075752) (x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 - x^17 - x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 - x^9 - x^8 + x^7 + x^6 + x^5 - x^4 - x^3 - x^2 - x + 1, [[-1, 1], [-1, -1], [0, 1], [0, -1], [1, 3], [1, -3], [3, 650615], [3, -650615]], 9279969) (x^24 + x^23 + x^22 + x^21 + x^20 + x^19 + x^18 + x^17 + x^16 + x^15 - x^14 + x^13 + x^12 + x^11 + x^10 + x^9 - x^8 + x^7 + x^6 + x^5 + x^4 - x^3 + x^2 - x + 1, [[-3, 460231], [-3, -460231], [-1, 1], [-1, -1], [0, 1], [0, -1]], 8470210) max bound= 4792168585 CPU times: user 10min 23s, sys: 2min 37s, total: 13min 1s Wall time: 28min 28s
In [ ]: