A362344 Maximum number of distinct real roots of degree-n polynomial with coefficients 0,1.
1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6
Offset: 1
Examples
For n = 7, the maximum number of distinct real roots of a degree-7 polynomial with coefficients 0,1 is 3; e.g., the polynomial x^7 + x^4 + x^2 + x has 3 distinct real roots.
Links
- Enrico Bertolazzi, Sturm.
- P. Borwein, T. Erdélyi, and G. Kós, Littlewood-type problems on [0,1], Proc. London Math. Soc. 79 (1999), 22-46.
- D. Ivanov et al., Number of real roots of 0,1 polynomial, MathOverflow.
- A. Odlyzko and B. Poonen, Zeros of polynomials with 0,1 coefficients, L’Enseignement Mathématique 39 (1993), 317-348.
Programs
-
MATLAB
% uses the Sturm toolbox; see links for i=2:13 display([i-1 maxroots(i)]); end function max_len=maxroots(n) max_len = 0; combinations = dec2bin(1:2:2^n-1) - '0'; for i = 1:2^(n-1) c = combinations(i,:); if sum(c, 2) == 1 continue; end len = distinct_real_roots(c); if len > max_len max_len = len; end end end function sign_var=distinct_real_roots(a) S=Sturm(); S.build(Poly(a)); sign_var=0; last_sign=0; last_sign_parity=0; parity=1; for i=1:length(S.m_sturm) v=S.m_sturm{i}.m_coeffs(end); if v>0 if last_sign<0 sign_var = sign_var - 1; end if last_sign_parity == -parity sign_var = sign_var + 1; end last_sign = 1; last_sign_parity = parity; elseif v<0 if last_sign>0 sign_var = sign_var - 1; end if last_sign_parity == parity sign_var = sign_var + 1; end last_sign = -1; last_sign_parity = -parity; end parity = -parity; end end -
Maple
f:= proc(n) local i,j,L,p,v,m; m:= 0: for i from 2^n to 2^(n+1)-1 do L:= convert(i,base,2); p:= add(L[j]*x^(j-1),j=1..n+1); v:= sturm(sturmseq(p,x),x,-infinity,infinity); if v > m then m:= v fi; od; m end proc: map(f, [$1..19]); # Robert Israel, May 07 2023 -
Mathematica
For[n=1,n<=8,n++,Print[Max[Length@DeleteDuplicates@NSolve[Total[x^#]+x^n==0,x,Reals]&/@Subsets[Range[0,n-1]]]]]
-
PARI
a(n) = my(nb=0, k); for (i=2^n, 2^(n+1)-1, k = #Set(polrootsreal(Pol(binary(i)))); if (k>nb, nb=k)); nb; \\ Michel Marcus, Feb 15 2024
-
Python
from itertools import product from sympy.abc import x from sympy import sturm, oo, sign, nan, LT def A362344(n): c = 0 for s in product([0,1],repeat=n): q = sturm(x**n+sum(int(s[i])*x**i for i in range(n))) 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])] c = max(c,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 c # Chai Wah Wu, Feb 15 2024
Extensions
a(14) on corrected by Robert Israel, May 07 2023
a(20)-a(22) from Michel Marcus, Feb 15 2024
a(23)-a(32) from Robin Visser, Aug 30 2024