login
Maximum number of distinct real roots of degree-n polynomial with coefficients 0,1.
3

%I #50 Sep 03 2024 00:59:29

%S 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

%N Maximum number of distinct real roots of degree-n polynomial with coefficients 0,1.

%H Enrico Bertolazzi, <a href="https://github.com/ebertolazzi/Sturm">Sturm</a>.

%H P. Borwein, T. Erdélyi, and G. Kós, <a href="https://doi.org/10.1112/S0024611599011831">Littlewood-type problems on [0,1]</a>, Proc. London Math. Soc. 79 (1999), 22-46.

%H D. Ivanov et al., <a href="https://mathoverflow.net/questions/461631/number-of-real-roots-of-0-1-polynomial">Number of real roots of 0,1 polynomial</a>, MathOverflow.

%H A. Odlyzko and B. Poonen, <a href="https://doi.org/10.5169/seals-60430">Zeros of polynomials with 0,1 coefficients</a>, L’Enseignement Mathématique 39 (1993), 317-348.

%e 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.

%p f:= proc(n) local i,j,L,p,v,m;

%p m:= 0:

%p for i from 2^n to 2^(n+1)-1 do

%p L:= convert(i,base,2);

%p p:= add(L[j]*x^(j-1),j=1..n+1);

%p v:= sturm(sturmseq(p,x),x,-infinity,infinity);

%p if v > m then m:= v fi;

%p od;

%p m

%p end proc:

%p map(f, [$1..19]); # _Robert Israel_, May 07 2023

%t For[n=1,n<=8,n++,Print[Max[Length@DeleteDuplicates@NSolve[Total[x^#]+x^n==0,x,Reals]&/@Subsets[Range[0,n-1]]]]]

%o (MATLAB)

%o % uses the Sturm toolbox; see links

%o for i=2:13

%o display([i-1 maxroots(i)]);

%o end

%o function max_len=maxroots(n)

%o max_len = 0;

%o combinations = dec2bin(1:2:2^n-1) - '0';

%o for i = 1:2^(n-1)

%o c = combinations(i,:);

%o if sum(c, 2) == 1

%o continue;

%o end

%o len = distinct_real_roots(c);

%o if len > max_len

%o max_len = len;

%o end

%o end

%o end

%o function sign_var=distinct_real_roots(a)

%o S=Sturm();

%o S.build(Poly(a));

%o sign_var=0;

%o last_sign=0;

%o last_sign_parity=0;

%o parity=1;

%o for i=1:length(S.m_sturm)

%o v=S.m_sturm{i}.m_coeffs(end);

%o if v>0

%o if last_sign<0

%o sign_var = sign_var - 1;

%o end

%o if last_sign_parity == -parity

%o sign_var = sign_var + 1;

%o end

%o last_sign = 1;

%o last_sign_parity = parity;

%o elseif v<0

%o if last_sign>0

%o sign_var = sign_var - 1;

%o end

%o if last_sign_parity == parity

%o sign_var = sign_var + 1;

%o end

%o last_sign = -1;

%o last_sign_parity = -parity;

%o end

%o parity = -parity;

%o end

%o end

%o (Python)

%o from itertools import product

%o from sympy.abc import x

%o from sympy import sturm, oo, sign, nan, LT

%o def A362344(n):

%o c = 0

%o for s in product([0,1],repeat=n):

%o q = sturm(x**n+sum(int(s[i])*x**i for i in range(n)))

%o a = [1 if (k:=LT(p).subs(x,-oo))==nan else sign(k) for p in q[:-1]]+[sign(q[-1])]

%o b = [1 if (k:=LT(p).subs(x,oo))==nan else sign(k) for p in q[:-1]]+[sign(q[-1])]

%o 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]))

%o return c # _Chai Wah Wu_, Feb 15 2024

%o (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

%Y Cf. A368774, A368824.

%K nonn,more

%O 1,2

%A _Keyang Li_, May 05 2023

%E a(14) on corrected by _Robert Israel_, May 07 2023

%E a(20)-a(22) from _Michel Marcus_, Feb 15 2024

%E a(23)-a(32) from _Robin Visser_, Aug 30 2024