Número de raíces reales del polinomio de 0,1

Question

$0,1$ polinomio tiene coeficientes de $\{0,1\}$. Investigo el número de raíces en dichos polinomios.
Estamos hablando de raíces reales, y los múltiplos se cuentan solo una vez.
Se encontró numéricamente que los grados mínimos $\nu(n)$ de tales polinomios con un número dado de raíces $n$ son (12.01):
(En la luz de la respuesta de @Timothy Chow se añadió la columna de $\sqrt{\nu(n)}/n$)

$n$

$\nu(n)$

$\sqrt{\nu(n)}/n$

Ejemplo

1

1

1.0

$x$

2

2

0.707

$x^2+x$

3

7

0.882

$x^7+x^4+x^2+x$

4

10

0.791

$x^{10}+x^9+x^7+x^4+x^2+x$

5

19

0.872

$x^{19}+x^{18}+x^{16}+x^{11}+x^9+x^6+x^5+x^4+x^2+x$

6

28

0.882

$x^{28} + x^{27} + x^{25} + x^{20} + x^{18} + x^{14} + x^{13} + x^{11} + x^{9} + x^{8} + x^{7} + x^{4} + x^{2} + x$

7

$\le$45

0.958

$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$

8

$\le$52

0.944

$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$

¿Y hay algunos resultados teóricos sobre raíces reales de polinomios de $0,1$?

Actualizaciones

1

Los editores de la OEIS decidieron separar estos resultados en una nueva secuencia:
A368824
¡Cualquiera puede editar y actualizarlo!

2

Todos los polinomios con el número máximo de raíces excepto $p_1$ (lo cual es comprensible) y $p_7$ (que creo que se corregirán) tienen raíces $0$ y $-1$ y sus gráficos en $[-1,0]$ se ven así:

Se me ocurrió la idea de que hay alguna ecuación diferencial
$P(x)y''(x) + Q(x)y'(x) + R(x)y(x)=0$
con condiciones de borde $y(0)=y(-1)=0$ que está relacionada con estos polinomios...

Answer 1

¿Existen algunos resultados teóricos sobre las raíces reales de polinomios de 0,1?

Estos polinomios se llaman polinomios de Newman. Una referencia comúnmente citada es Ceros de polinomios con coeficientes de 0,1 de A. Odlyzko y B. Poonen, L’Enseignement Mathématique 39 (1993), 317–348. En el artículo Problemas de tipo Littlewood en [0,1] de P. Borwein, T. Erdélyi, y G. Kós, Proc. London Math. Soc. 79 (1999), 22–46 (DOI), los autores demuestran:

Existe una constante absoluta $c > 0$ tal que cada polinomio $p$ de la forma $$p(x) = \sum_{j=0}^n a_j x^j, \quad |a_j| \le 1, \quad |a_0| = |a_n| = 1, \quad a_j \in \mathbb{C}$$ tiene a lo sumo $c\sqrt{n}$ ceros reales.

Este resultado brinda información sobre la pregunta que hiciste, aunque no la responde completamente. Existe una amplia literatura sobre polinomios de Newman y sus primos cercanos, los polinomios de Littlewood (cuyos coeficientes son $0$ o $\pm1$); ver por ejemplo K. G. Hare y J. Jankauskas, Sobre polinomios de Newman y Littlewood con número prescrito de ceros dentro del disco unidad (arXiv:1910.13994) o T. Erdélyi, Sobre los ceros de polinomios con restricciones de coeficiente tipo Littlewood (Michigan Math. J. 49 (2001), 97–111) y las referencias allí citadas.

Answer 2

Actualización 1: Ahora he utilizado la biblioteca de multiprocesamiento para la paralelización del cálculo, y he actualizado en consecuencia el código de Python.

---

Actualización 2: Tenemos $\nu(7)\le 45$ y $\nu(8)\le 52$, ya que los polinomios $$\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}$$ y $$\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}$$ tienen $7$ y $8$ raíces reales, respectivamente.

Estos polinomios son los más pequeños lexicográficamente de la forma $xh(x)$, donde $h$ es igual a su recíproco.

---

A continuación se muestra el código Python que para cada entero suficientemente pequeño $n$ calcula el número máximo de raíces reales distintas de polinomios de grado $n$ con coeficientes $0$ y $1$ (que es [OEIS A362344][1]) junto con un ejemplo de menor orden lexicográfico. Por ejemplo, vemos en pocos minutos que $\nu(6)=28$. (Inicialmente, había escrito un script de SageMath usando el Teorema de Sturm, sin embargo la función `polsturm` de pari/gp es algo más rápida.)

El script de Python hace uso de la paralelización. La línea cpus = 17 indica que se utilizarán $17$ núcleos y, por supuesto, se puede ajustar.

El script identifica la expansión binaria $p=\sum a_i2^i$ con el polinomio $\sum a_ix^i$.

En caso de que alguien quiera buscar un patrón, aquí hay una lista de todos los polinomios $0$-$1$ de grado $28$ con $6$ raíces reales distintas. Para ahorrar espacio, proporcionamos la lista como los números $p$ (ver arriba): 437545878, 437594646, 437594838, 437619606, 437643798, 440494998, 440875158, 443812758, 443836950, 443837334, 443910678, 443911062, 443916438, 443923062, 443923350, 444033942, 450177558, 462908310. (En SageMath, si K es un anillo de polinomios, y p es uno de estos números, K(p.bits()) da como resultado el polinomio correspondiente).

Y aquí está el código Python (que requiere la biblioteca cypari2):

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