Skip to main content
simplified program code
Source Link
Peter Mueller
  • 22.5k
  • 1
  • 75
  • 107

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.

instanceeach sufficiently small integers$n$
the maximum number of distinct real roots of degree$\nu(6)$$n$ polynomials with coefficients$0$ and$1$(which is [OEIS A362344][1]) together with a lexicographically smallest example
For instance, we see within a few minutes that$\nu(6)=28$.
gppari
parigp

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 0adjusted.

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}')

Update: 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.

instance
$\nu(6)$
gp
pari

The script, if it is named mo.py, is best called in a Linux console via nohup python3 mo.py nr cpus start &, where nr is a lower bound for the number of real roots we want, cpus is the number of kernels we want to use, and start should 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.

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 sequence (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 argv
import cypari2
pari = cypari2.Pari()

nr, cpus, start = [int(z) for z in argv[1:]]

def int2pol(p):
    if p&3 == 0:
        return None
    i = 0
    l = []
    c = p
    rec = 0
    while c != 0:
        if c&1 != 0:
            l.append(f'x^{i}')
        rec = (rec << 1) + (c & 1)
        i += 1
        c >>= 1
    if p&1 == 0:
        rec <<= 1
    return pari('+'.join(l)) if p <= rec else None

n = -1
file = open(f'mo_461631_nr={nr}_cpus={cpus}_start={start}.log', 'w')
while True:
    n += 1
    print(f'degree = {n}')
    file.write(f'degree = {n}\n')
    file.flush()
    for p in range(2**n + start, 2**(n+1), cpus):
        f = int2pol(p)
        if f != None:
            m = f.polsturm()
            if m >= nr:
                print(m, p, f)
                file.write(str((m, p, f)) + '\n')
                file.close()
                break
    else:
        continue
    break

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.

each sufficiently small integers$n$
the maximum number of distinct real roots of degree$n$ polynomials with coefficients$0$ and$1$(which is [OEIS A362344][1]) together with a lexicographically smallest example
For instance, we see within a few minutes that$\nu(6)=28$.
pari
gp

The Python script makes use of parallelization. The line cpus = 17 tells that $17$ cores will be used and of course can be adjusted.

The script identifies the binary expansion $p=\sum a_i2^i$ with the polynomial $\sum a_ix^i$.

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 numbers $p$ (see above): 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.)

import cypari2
from multiprocessing import Pool
pari = cypari2.Pari()

cpus = 17 ################

def check(i):
    best, bestp, bestf = 0, 0, ''
    for p in range(2**n + i, 2**(n+1), cpus):
        l = []
        for j, b in enumerate(bin(p)[-1:1:-1]):
            if b == '1':
                l.append(f'x^{j}')
        s = '+'.join(l)
        m = pari(s).polsturm()
        if m > best:
            best, bestp, bestf = m, p, s
    return best, bestp, bestf

n = 1
while True:
    n += 1
    with Pool(cpus) as P:
        res = P.map(check, range(cpus))
    best, bestp = 0, 2**(n+1)
    for m, p, s in res:
        if m > best or (m == best and p < bestp):
            best, bestp, bestf = m, p, s
    print(f'deg = {n}, m = {best}, p = {bestp}, bestf = {bestf}')
added 742 characters in body
Source Link
Peter Mueller
  • 22.5k
  • 1
  • 75
  • 107

Below is the Python code which for instance computesUpdate: We have $\nu(6)$.$\nu(7)\le 45$ and (Initially$\nu(8)\le 52$, I had written a SageMath script using Sturm's Theoremas 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, howeverrespectively.

These polynomials are the lexicographically smallest ones of the form polsturm function from gp/pari$xh(x)$, where $h$ is somewhat fasterequal to its reciprocal.)


Below is the Python code which for instance computes$\nu(6)$.(Initially, I had written a SageMath script using Sturm's Theorem, however the `polsturm` function from gp/pari is somewhat faster.)

Below is the Python code which for instance computes $\nu(6)$. (Initially, I had written a SageMath script using Sturm's Theorem, however the polsturm function from gp/pari is somewhat faster.)

Update: 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.

These polynomials are the lexicographically smallest ones of the form $xh(x)$, where $h$ is equal to its reciprocal.


Below is the Python code which for instance computes$\nu(6)$.(Initially, I had written a SageMath script using Sturm's Theorem, however the `polsturm` function from gp/pari is somewhat faster.)
Source Link
Peter Mueller
  • 22.5k
  • 1
  • 75
  • 107

Below is the Python code which for instance computes $\nu(6)$. (Initially, I had written a SageMath script using Sturm's Theorem, however the polsturm function from gp/pari is somewhat faster.)

The script, if it is named mo.py, is best called in a Linux console via nohup python3 mo.py nr cpus start &, where nr is a lower bound for the number of real roots we want, cpus is the number of kernels we want to use, and start should 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.

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 sequence (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.)

And here is the Python code (which requires the library cypari2):

from sys import argv
import cypari2
pari = cypari2.Pari()

nr, cpus, start = [int(z) for z in argv[1:]]

def int2pol(p):
    if p&3 == 0:
        return None
    i = 0
    l = []
    c = p
    rec = 0
    while c != 0:
        if c&1 != 0:
            l.append(f'x^{i}')
        rec = (rec << 1) + (c & 1)
        i += 1
        c >>= 1
    if p&1 == 0:
        rec <<= 1
    return pari('+'.join(l)) if p <= rec else None

n = -1
file = open(f'mo_461631_nr={nr}_cpus={cpus}_start={start}.log', 'w')
while True:
    n += 1
    print(f'degree = {n}')
    file.write(f'degree = {n}\n')
    file.flush()
    for p in range(2**n + start, 2**(n+1), cpus):
        f = int2pol(p)
        if f != None:
            m = f.polsturm()
            if m >= nr:
                print(m, p, f)
                file.write(str((m, p, f)) + '\n')
                file.close()
                break
    else:
        continue
    break