Checking some Asymptotic Properties of Real and Complex Roots of Random Algebraic Polynomials

Henryk Zawadzki

The Karol Adamiecki University of Economics in Katowice, Poland

Random Algebraic Polynomials and the Kac Formula

Definition

An algebraic polynomial of degree n

(Subscript[p, n])(z)=(∑_(j=0)^n)(Subscript[a, j])(z^j)

is called random algebraic polynomial (RAP) if its coefficients (Subscript[a, 0]),(Subscript[a, 1]),...,(Subscript[a, n])  are random variables.

Kac Formula

When the coefficients of RAP are random variables, the number (Subscript[ν, n]) of all real roots of (1) is also a random variable. 
M. Kac [2,3] derived a formula for the expected value of (Subscript[ν, n]), assuming that (Subscript[a, j]) ( j = 0, ..., n) are independent, identically distributed standard normal variables.

Mark (Marek) Kac (1914-1984)

The Kac formula is of the form

E((Subscript[v, n]))=(∫_(-∞)^∞)(Subscript[g, n])(t)dt

with so called intensity functions

(Subscript[g, n])(t)=(1/π)(Sqrt[(1/((((t^2)-1))^2))-(((((n+1))^2)(t^(2n)))/((((t^(2n+2))-1))^2))])

It is easy to show how the shape of the graphs of intensity functions (3) changes when n is increasing.

g[n_]:=(1/π) (Sqrt[(1/((((t^2)-1))^2))-(((((n+1))^2)*(t^(2 n)))/((((t^(2 n+2))-1))^2))])

plot1=Show[Table[Plot[g[n],{t,-2,2}, PlotRange->All,AxesOrigin->{0,0},AxesLabel->{"t","(Subscript[g, n])(t)"}],{n,2,50}]]

The (pointwise) convergence of functional sequence ((Subscript[g, n])) to some limiting function is clearly visible.
One can easily prove that for t ≠ ± 1 the limiting function is given by the formula

g(t) = (1/(π|(t^2)-1|))

plot2=Plot[1/(π*Abs[1-t^2]),{t,-2,2}, PlotStyle->{RGBColor[1,0,0],Thickness[0.008]},PlotRange->{0,6},AxesLabel->{"t","g(t)"}]

Show[plot1,plot2,AxesLabel->{"t","(Subscript[g, n])(t),g(t)"}]

Manipulate[Plot[g[n],{t,-2,2},PlotRange->All,AxesOrigin->{0,0}],{n,2,50,1}]

The bimodality of distributions of (Subscript[v, n])  ( n ≥2 ) reflects the tendency of real roots to concentrate in the vicinity of numbers ± 1.

Approximations of the Kac Formula

Kac also shoved that

E((Subscript[v, n]))∼(2/π)ln n

where the symbol "∼" denotes the equivalence of sequences.

The formula (4) was sharpened by several researchers

E((Subscript[v, n]))∼(2/π)ln n +(2/(π n))+C

with C ≈ 0.6257358072... (Edelman, Kostlan [1]).

Calculating with  NIntegrate the values of  E((Subscript[v, n])) directly from Kac formula (2) and the values of sequence

(Subscript[c, n])=(2/π)ln n +(2/(π n))+C

we can show that for increasing n these values become indistinguishable.

EV[n_]:=NIntegrate[g[n],{t,-∞,∞}]

c[n_]:=(2/π) Log[n]+(2/(π n))+0.6257358072

list1=Table[EV[n],{n,50}];list2=Table[c[n],{n,50}];

ListPlot[{list1,list2},AxesOrigin->{0,0},PlotMarkers->{Automatic,Tiny},AxesLabel->{"n","E((Subscript[v, n])), (Subscript[c, n])"}]

Next two plots show that

(Subscript[c, n])-E((Subscript[v, n]))->0

and

((E((Subscript[v, n])))/(Subscript[c, n]))->1

list3=Table[list2[[n]]-list1[[n]],{n,50}];

ListPlot[list3,AxesOrigin->{0,0},PlotMarkers->{Automatic,Tiny},AxesLabel->{"n","(Subscript[c, n])-E((Subscript[v, n]))"},PlotRange->{0,0.27}, PlotStyle->{RGBColor[0,1,0]}]

list4=Table[list1[[n]]/list2[[n]],{n,50}];

ListPlot[list4,PlotMarkers->{Automatic,Tiny},AxesLabel->{"n","E((Subscript[v, n]))/(Subscript[c, n])"},PlotRange->{0.7,1.1}, PlotStyle->{RGBColor[1,0,0]}]

"Checking" the Kac Formula

Let us generate k  RAPs of degree  2, 3, ..., n  with i.i.d. standart normal distributed coefficients and using CountRoots function calculate (from the sample) the average number  (Subscript[(OverBar[E]), n]) of real roots. 
Let us take for example

n:=50;k:=100;SeedRandom[1950];

For[i=2,i≤n,i++,For[j=1,j≤k,j++,For[m=0,m≤i,m++,{a[i_,j_,m_]:=RandomReal[NormalDistribution[0,1]],poly[i_,j_]:=(∑_(m=0)^i)a[i,j,m]*(x^m),c[i_,j_]:=CountRoots[poly[i,j],x]};EVS[i_]:=Mean[Table[c[i,j],{j,1,k}]]//N]]]

list5=Table[EVS[i],{i,2,50}];

ListPlot[{list2,list5},AxesLabel->{"n","(Subscript[c, n]),(OverBar[(Subscript[E, n])])"},AxesOrigin->{0,0}]

CountRoots and Countroots Functions

Function   CountRoots[poly,x] gives the number of real roots of poly.

Function  Countroots[poly,{α,β}]  gives the number of roots of  poly  with main argument ranging in the interval [α, β ).

Countroots[poly_,{α_,β_}]:=Part[BinCounts[Arg[x]/.NSolve[poly==0,x],{{α,β}}],1]

Let us take for example

poly:=x^10-10 x+1

CountRoots[poly,x]

Countroots[poly,{0,π/2}]

Graphics[{Red,PointSize[Medium],Point[{Re[x],Im[x]}/.NSolve[poly==0,x]]},Axes->True,AxesLabel->{"Re(z)","Im(z)"}]

Plot[poly,{x,-2,2}]

NSolve[poly==0,x]

How are the Roots of RAPs distributed (located) on the Complex Plane?

Clear[poly]

For[i=1,i≤k,i++,For[j=0,j≤n,j++,a[i_,j_]:=RandomReal[NormalDistribution[0,1]]]]

poly[i_]:=(∑_(j=0)^n)a[i,j]*(x^j)

plot[i_]:=Graphics[{Red,PointSize[0.003],Point[{Re[x],Im[x]}/.NSolve[poly[i]==0,x]]}]

GraphicsGrid[Partition[Table[plot[i],{i,1,100}],10],Frame->All]

Clustering

For n big enough, the roots of RAPs cluster near the unit circle |z| = 1.

Show[Table[plot[i],{i,1,k}],Axes->True,PlotRange->{{-2.5,2.5},{-2.5,2.5}},AxesLabel->{"Re(z)","Im(z)"}]

r[j_]:=Show[Table[plot[i],{i,1,j}],Axes->True,PlotRange->{{-2.5,2.5},{-2.5,2.5}},AxesLabel->{"Re(z)","Im(z)"}];

Manipulate[r[j],{j,1,k,1}]

Uniform Distribution in Argument

The roots of RAPs are (asymptotically) uniformly distributed in argument in the sence of convergence

((E{(Subscript[v, n])[S(α,β)]})/n)->((β-α)/(2π))

where (Subscript[v, n])[S(α,β)] denotes the number of roots lying in the sector

S(α,β)={z∈C: α ≤Arg<β}

of the complex plane that does not intersect the real axis ([4]). 

Let us take again k = 100, n = 50 and put  α = (π/4) , β = ((3π)/4).

α:=(π/4);β:=((3 π)/4);

Clear[poly]

For[i=2,i≤n,i++,For[j=1,j≤k,j++,For[m=0,m≤i,m++,{a[i_,j_,m_]:=RandomReal[NormalDistribution[0,1]],poly[i_,j_]:=(∑_(m=0)^i)a[i,j,m]*(x^m),c[i_,j_]:=Countroots[poly[i,j],{α,β}]};EVS[i_]:=Mean[Table[c[i,j],{j,1,k}]]//N]]]

list6=Table[EVS[i]/i,{i,2,50}];

plot3=ListPlot[list6 ];

plot4=Plot[(β-α)/(2*π),{x,0,n},PlotStyle->{RGBColor[1,0,0]}];

Show[plot3,plot4,AxesLabel->{"n","E{(Subscript[ν, n])[S(α,β)]}/n"}, PlotRange->{0.00,0.3},AxesOrigin->{0,0}]

References

1. A. Edelman, E. Kostlan, How many zeros of a random polynomial are real, Bull. (New Series) Amer. Math. Soc. 32, Number 1, January 1995, 1-37.
2. M. Kac, On the average number of real roots of a random algebraic equation, Bull. Amer. Math. Soc. 49, (1943), 314-320.
3. M. Kac, On the average number of real roots of a random algebraic equation (II), Proc. London Math. Soc.(3), 50, (1949), 390-408.
4. L.A. Shepp, R.J. Vanderbei, The complex zeros of random polynomials, Trans. Amer. Math. Soc. 347, Number 11, November 1995.