Update 1: I've now used the multiprocessing library for the parallelization of the computation, and accordingly updated the Python code.
Update 2: We have $\nu(7)\le 45$ and $\nu(8)\le 52$, as the polynomials \begin{equation} x^{45} + x^{44} + x^{42} + x^{37} + x^{35} + x^{33} + x^{31} + x^{30} + x^{28} + x^{26} + x^{24} + x^{23} + x^{22} + x^{20} + x^{18} + x^{16} + x^{15} + x^{13} + x^{11} + x^{9} + x^{4} + x^{2} + x \end{equation} and \begin{equation} x^{52} + x^{51} + x^{49} + x^{46} + x^{40} + x^{38} + x^{37} + x^{36} + x^{35} + x^{33} + x^{31} + x^{29} + x^{27} + x^{26} + x^{24} + x^{22} + x^{20} + x^{18} + x^{17} + x^{16} + x^{15} + x^{13} + x^{7} + x^{4} + x^{2} + x \end{equation} have $7$ and $8$ real roots, respectively.
The Python script, if it is named mo.py
, is best called in a Linux console via makes use of parallelization. The line nohup python3 mo.py nr cpus start= &
, where nr17
is a lower bound for the number of real roots we want,tells that cpus
is the number of kernels we want to use,$17$ cores will be used and start
shouldof course can be $i$ for $0\le i\le cpus-1$.
For instance, in order to compute $\nu(6)$ without parallelization, just call python3 mo.py 6 1 0
adjusted.
The script identifies the binary expansion $p=\sum a_i2^i$ with the polynomial $\sum a_ix^i$. Note that we need not look at polynomials which are divisible by $x^2$. Another reduction, by about the factor $2$, uses that the number of nonzero roots of a polynomial equals the number of its reciprocal.
In case that someone wants to look for a pattern, here is a list of all $0$-$1$-polynomials of degree $28$ with $6$ distinct real roots. To save space, we give the list as the sequencenumbers $p$ (see above) of numbers: 437545878, 437594646, 437594838, 437619606, 437643798, 440494998, 440875158, 443812758, 443836950, 443837334, 443910678, 443911062, 443916438, 443923062, 443923350, 444033942, 450177558, 462908310. (In SageMath, if K
is a polynomial ring, and p
is one of these numbers, K(p.bits())
yields the corresponding polynomial.)
from sys import argvcypari2
from multiprocessing import cypari2Pool
pari = cypari2.Pari()
nr, cpus, start = [int(z) for z in17 argv[1:]]################
def int2polcheck(pi):
ifbest, p&3bestp, ==bestf = 0:, 0, ''
for p in range(2**n return+ None
i, 2**(n+1), cpus):
i = 0
l = []
c = p
for j, recb =in 0enumerate(bin(p)[-1:1:-1]):
while c != 0:
if c&1b !=== 0'1':
l.append(f'x^{ij}')
recs = (rec << 1) + '+'.join(c & 1l)
im +== 1pari(s).polsturm()
cif >>=m 1> best:
if p&1 == 0:
best, bestp, bestf rec= <<=m, 1p, s
return pari('+'.join(l)) if p <= recbest, elsebestp, Nonebestf
n = -1
file = open(f'mo_461631_nr={nr}_cpus={cpus}_start={start}.log', 'w')
while True:
n += 1
print(f'degree = {n}')
with file.writePool(f'degree = {n}\n'cpus)
as file.flush()P:
for p in range(2**n +res start,= 2**P.map(n+1)check, range(cpus):)
best, fbestp = int2pol0, 2**(pn+1)
for m, ifp, fs !=in Noneres:
if m = f.polsturm()
> best or (m == best ifand mp >=< nrbestp):
print(mbest, pbestp, f)
bestf = file.write(str((m, p, f)) + '\n')s
file.closeprint()
break
else:
f'deg = {n}, m = {best}, p continue
= {bestp}, bestf = break{bestf}')