A368824 a(n) is the smallest degree of (0,1)-polynomial with exactly n real distinct roots.

1, 2, 7, 10, 19, 28

Offset

1,2

Comments

(0,1) (or Newman) polynomials have coefficients from {0,1}.

Links

Table of n, a(n) for n=1..6.

P. Borwein, T. Erdélyi, and G. Kós, Littlewood-type problems on [0,1], Proc. London Math. Soc. 79 (1999), 22-46.

MathOverflow, Number of real roots of 0,1 polynomial.

A. Odlyzko and B. Poonen, Zeros of polynomials with 0,1 coefficients, L’Enseignement Mathématique 39 (1993), 317-348.

Formula

a(n) ~ C*n^2 (see Odlyzko and Poonen) with numerical estimate 0.7 < C < 0.9.

Mathematica

(* Suitable only for 1 <= n <= 4;
for larger n, special Julia and Python packages are needed *)
Table[Exponent[Monitor[Catch[Do[
   poly = FromDigits[IntegerDigits[k, 2], x];
   res = Length@{ToRules@Reduce[poly == 0, x, Reals]};
   If[res == n, Throw@{res, Expand@poly}]
   , {k, 2000}]], k][[2]], x], {n, 1, 4}]

Prog

(Python)
from itertools import count
from sympy.abc import x
from sympy import sturm, oo, sign, nan, LT
def A368824(n):
    for m in count(2):
        l = len(s:=bin(m)[2:])
        q = sturm(sum(int(s[i])*x**(l-i-1) for i in range(l)))
        a = [1 if (k:=LT(p).subs(x, -oo))==nan else sign(k) for p in q[:-1]]+[sign(q[-1])]
        b = [1 if (k:=LT(p).subs(x, oo))==nan else sign(k) for p in q[:-1]]+[sign(q[-1])]
        if n==sum(1 for i in range(len(a)-1) if a[i]!=a[i+1])-sum(1 for i in range(len(b)-1) if b[i]!=b[i+1]):
            return l-1 # Chai Wah Wu, Feb 15 2024

Crossrefs

Cf. A368774, A362344.

Sequence in context: A152211 A309805 A125852 * A336903 A155171 A049830

Adjacent sequences: A368821 A368822 A368823 * A368825 A368826 A368827

Keyword

nonn,hard,more

Author

Denis Ivanov, Jan 07 2024

Status

approved