Is the largest root of a random real polynomial more likely real than complex?

https://mathoverflow.net/questions/470951/is-the-largest-root-of-a-random-polynomial-more-likely-to-be-real-than-complex

by jjgreen • 2 years ago

203 119 2 years ago

mathoverflow.net

Sebb767• 2 years ago

For those not well versed in the Stack Exchange network, what's the difference between Math Stack Exchange and Math Overflow?

SassyBird2• 2 years ago

MSE is for noobs, think HS and uni students. MO is for pros, think PhDs, researchers etc.

lupire4• 2 years ago

Adults, who might or not have graduated or attended high school or University, also use MSE.

jjgreen2• 2 years ago

MO is for research-level discussions, questions are often bumped from one to the other (more often from MO to MSE).

admissionsguy• 2 years ago

I believe one was for professionals and the other one for students. Don't remember which one, I guess Overflow is for professionals since we use it for coding.

Sharlin• 2 years ago

Honestly it’s Stack Overflow that’s really the "noob" level programming discussion, with 95% of questions incredibly elementary, whether "professional" or not. cstheory.stackexchange.com is more analogous to mathoverflow.com in that it’s about research-level questions.

I think Math Overflow was the first overflow instance after SO, so it has a sort of a special status and its own domain. *.stackexchange.com came later to meet the growing demand for more instances.

HappyPanacea2• 2 years ago

Math Overflow domain and name are owned by a nonprofit organization, see https://meta.mathoverflow.net/questions/969/who-owns-mathove...

melenaboija• 2 years ago

The MathOverflow corporation is completely independent from Stack Exchange and its mission is to ensure the continued operation of the site in a manner that meets the needs and expectations of the community.

Does it make it more or less hostile than Stack Exchange?

selimthegrim2• 2 years ago

Looking through the links from here one of the answers by Boris Hanin may have resolved a question I had for a while.

meindnoch• 2 years ago

As there's no formula for degree-5 polynomials and above, how do you distinguish between a real root vs. a real number + epsilon*i?

jcla1• 2 years ago

Just because of the impossibility of an exact formula for the roots of a high-degree polynomial that does not rule out the possibility of figuring out, say, the distribution of roots of such polynomials. The question is not about any polynomial in particular (hence Abel's theorem is no barrier).

edit: Think of the following example: take a polynomial a_n x^n + ... + a_0, where the coefficients a_i are i.i.d. Bernoulli random variables. Even though the degree n might be large (> 4) I can say with confidence that such a polynomial has a real root (x = 0) with probability 1/2. Similar though more sophisticated arguments are at work in the linked question.

vouaobrasil• 2 years ago

The estimations are not based on numerics, but rather reasoning. For example, since real-valued polynomials are stable under complex conjugation, each complex root must have a complex conjugate. For polynomials with three distinct roots then, one must be real. This is just an EXAMPLE of the kind of reasoning that can be used to infer whether a root is purely real or complex.

As for formulas: no, there is no GENERAL formula for the quintic polynomial or higher. General formulas only exist for polynomials of degree four or lower.

Of course, there are SPECIFIC formulas for specific KINDS of higher-degree polyomials. But for the general quintic and higher, nothing. That's already been proved classically.

orlp• 2 years ago

As for formulas: no, there is no GENERAL formula for the quintic polynomial or higher.

Note that there is no general formula for quintics (and higher) in radicals.

But it is a bit arbitrary to draw the line there. There is also no 'general formula' using basic arithmetic operations (addition, subtraction, multiplication, division) that gives roots for x^2 = 2.

However it is quite useful to be able to talk about those roots, so we added a dedicated symbol for them (sqrt), and more generally extended the definition of exponentiation to fractional powers.

If it were generally useful to talk about the roots of quintics we also would've added common notation for their roots.

yorwba• 2 years ago

You use Budan's theorem https://en.wikipedia.org/wiki/Budan%27s_theorem to certify that there's exactly one (or exactly zero) real root in the interval (r - ɛ, r + ɛ]. As long as your guess r is within ɛ of a root, this allows distinguishing between real and complex roots even if you don't have the exact value. (There are instances where Budan's theorem cannot give an answer, e.g. most obviously if there's more than one root in the interval.)

red_trumpet2• 2 years ago

I could imagine that one uses the derivative here. If x+iy and x-iy are complex roots, and y is really small, then the derivative at x should be small as well (if y = 0, you have a double zero, so p'(x)=0). So if p'(x) is far away from zero, you have a single real zero. And I guess double zeroes don't really happen with random coefficients.

HappyPanacea2• 2 years ago

If we have polynomial with integer coefficients, we can bound the largest and smallest root by an expression that is maximum of abs. value of coefficients to some power. There should be similar bounds for the smallest imaginary value a root can have. If your polynomial have real numbers for coefficients having a formula doesn't help - we have the same problem of being not able to tell if number is equal zero. For example in the quadratic formula, we can have discriminant equal minus epsilon. If epsilon was zero there is no imaginary root but if it isn't we have an imaginary root.

bmacho• 2 years ago

I think the others answered your question.

In addition, I suggest you to forget this "degree-5 polynomials" thing. They are not different from degree 2 polynomials in any meaningful way, if you talk about computing their roots or reason about their roots.

6gvONxR4sf7o• 2 years ago

There is a formula for arbitrary degree polynomials, it’s just difficult to apply: https://en.m.wikipedia.org/wiki/Thomae%27s_formula Apparently it’s the integrals involved that make it a challenge to use?

You’re probably thinking of the theorem that these can’t always be expressed with just exponents and fractions and other plain algebraic operations.

klyrs2• 2 years ago

There's an incredibly simple result of Sturm that allows one to compute intervals bounding the real roots of polynomials. https://en.wikipedia.org/wiki/Sturm%27s_theorem

That said, if you're working with finite precision, then there's an interesting question somewhere here -- given a polynomial with a certain number of real roots, how precisely do you need to know the coefficients before the answer changes?

LeonardoTolstoy2• 2 years ago

I assume this is one of these things where it is just like ... Oh I don't know this kind of math.

Because in my mind I take a "random" polynomial and only consider the largest two roots. Then I consider doing two reflections: across the bottom/top of the curve, and across the x axis. If those top two roots aren't degenerate the combination of the four curves using the reflections have two curves with a largest real root, and two curves with a largest imaginary root (I think). If it is degenerate then the largest root is real.

So I would then conclude that (1) there are more real largest roots than imaginary and (2) the "advantage" is vanishingly small since there are infinitely more curves with a largest non-degenerate root than degenerate root.

As one can tell I barely know the proper nomenclature. I assume I'm mainly missing some consideration about the uniformity of random coefficients not resulting in a uniform distribution in space? Or possibly my reflections can violate one of the conditions (real coefficients?)? Or I'm just plain wrong.

red_trumpet2• 2 years ago

I don't follow your reflections. Reflecting the graph of a polynomial p(x) along the x-axis means replacing p(x) by p(-x). What do you mean by reflecting "across the bottom/top of the curve"? Reflecting along the y-axis? This would mean p(x) is replaced by -p(x).

r0uv3n• 2 years ago

What do you mean with reflection across the bottom/top of the curve?

With combination you presumably mean taking (polynomial+reflected polynomial)/2?

LeonardoTolstoy2• 2 years ago

Ah there we go. At the very least I was only considering the subspace where the polynomial's derivative has only real roots?

Think of a simple quadratic. The reflection is across the min(f(x)) axis. But for higher order polynomials that doesn't always work so that is certainly an issue. Thanks

keepamovin7• 2 years ago

Wow that is crazy that it is between chance and 1/phi.

In the linked MSE post, it has now been proved that the probability that the largest root is real is at least 6.2%

And! at least 1/10th of 1/phi. Hahaha! :)

I think the link of phi with number theory is natural in the sense that the primes are not random (as is commonly mistaken) but arise recursively from prior primes: they are exactly the 'gaps' not hit by multiples of prior primes, so there's a kind of 'natural growth' pattern that we would expect to reflect some manner of e and phi

It's a very fundamental pattern of magnitude. Truth beauty et all

dr_dshiv2• 2 years ago

Beautiful! Phi always seems to show up when there is crowding.

keepamovin7• 2 years ago

Thanks! Let's collab. We should start a "primes investigation" github repo!!!! :)

RockofStrength3• 2 years ago

You get e from the primes by averaging the set size of only growing gaps (2,3,5)(7,11)(13,17)... or only non-shrinking gaps (2,3,5,7,11)(13,17)(19,23,29)...

Not a property of primes per se, just a property of growth. It works better with a set of randoms.

lupire4• 2 years ago

I thinking that works for primes because primes are approximately randomly distributed.

But primes are more directly "e" if you look at π(N), the count of primes less than N. That is ~n/ ln(n)

https://en.m.wikipedia.org/wiki/Prime-counting_function

keepamovin7• 2 years ago

I think that's also another way you can get e from primes.

Can you explain more what you mean by "set size of only growing gaps" - I like this!

kzrdude2• 2 years ago

This reminds me of another of those random polynomial questions where a good answer showed why the question asker's chosen distribution of coefficients lead to the result they were seeing. Anyone recognize that and have a link? It seems like it's relevant here too.

evertedsphere• 2 years ago

https://math.stackexchange.com/questions/206890/the-egg-biza... ?

kzrdude2• 2 years ago

There's many of these then!

I think I found the one I was thinking of:

https://mathoverflow.net/questions/182412/why-do-roots-of-po...

See answer by Will Jagy

Aardwolf2• 2 years ago

Does random polynomial mean with real or complex coefficients, though?

cool_dude85• 2 years ago

The question posed specifies real coefficients, looks like experimentally tested on random coefficients selected from [-1, 1] from uniform distribution and a sort of scaled normal distribution.

VyseofArcadia• 2 years ago

This stuck out to me, and might be a place where our intuition breaks down. As a human if you tell me, "give me a polynomial with degree n with coefficients drawn uniformly from [-1, 1]," I will likely produce one with a lot of zero coefficients, just because a lot of the polynomials you encounter in the wild have a lot of zero coefficients.

In reality, if you grab a coefficient uniformly from [-1,1], the probability that it is 0 is 0.

Someone2• 2 years ago

Likely (can’t find the test code) tested on coefficients selected from the IEEE doubles in [-1, +1], so from a subset of numbers of the form m/2^n with m and n integers and m between 0 and 2^53 or thereabouts.

For this problem, I don’t see how that would give different results as picking any number in [-1, +1], but that’s not a priori guaranteed. Mathematicians are well-trained as nitpickers.

Smaug123• 2 years ago

The first line of the question says "real".

Aardwolf2• 2 years ago

But that first line is a statement about something related but different (the question is about largest root, this statement is about any root), and the term "random polynomial" without specifying anything is used throughout the rest of the content

outop• 2 years ago

If you allow complex coefficients then the distribution is rotationally symmetric in the complex plane. So a root is no more likely to be in the real line than in any other line through the origin. There would be vanishingly few polynomials with largest root real.

dailykoder• 2 years ago

Sligthly OT, but I always have fun reading these maths posts here: I enjoyed maths in University very much (I did CE) and the joy from my professors always inspired me. I'd love to learn more and dip into solving things with it (maybe with a hang towards numerics?).

But been out of Uni for 2 years now and haven't done much, so probably gotta relearn quite a bit. Does anyone have some good ideas where to start and find fun ideas? Not numerics, but I did quite a few projecteuler problems during my bachelors - maybe there is more like this? Any ideas welcome.

Or should I redo all tasks in my textbooks first? ;-)

belter• 2 years ago

A bit unrelated to your question, but if you love Maths you can't miss The Math Sorcerer: https://www.youtube.com/@TheMathSorcerer

jjgreen2• 2 years ago

I went to University to do maths 6-7 years after leaving school (with decent maths results there) so had forgotten everything. Nothing beats doing all of the exercises that you did before, and actually you find that you've not quite forgotten everything. Good luck!

jsbg• 2 years ago

Mathematics and Its History (https://link.springer.com/book/10.1007/978-1-4419-6053-5) is a really fun book for someone who already knows some university-level math and is just curious.

You may also enjoy Proofs from THE BOOK (https://link.springer.com/book/10.1007/978-3-662-57265-8).

ptero2• 2 years ago

Two questions that immediately jump at me are:

1. What is random? They seem to have run numerical experiments, which suggests they used (something equivalent to) uniform integer coefficients from a bounded set. And that could affect findings a lot!

2. Did they look at odd degrees (which always guarantees a real root), even or both?

Not trying to knock this fun post.

lupire4• 2 years ago

Right. The problem as originally stated is paradoxical. You can't uniformly sample an unbounded set. I assume OP used a random floating point, which are bounded.

But the important part of the question can be asked for any possible distribution over the reals.

Sesse__• 2 years ago

You can't uniformly sample an unbounded set.

You definitely can, as long as you are accepting the use of limits (and without that, sampling uniform over any subsegment over the reals would also be pretty much impossible). “Sample a uniformly chosen real” just is shorthand for “Sample over a real from [-N, +N], then we are interested in the answer then N goes to infinity”. In this case, then just divide all the coefficients by N, which obviously doesn't affect the answer. So uniformly over [-1,+1] is as good as uniformly over R.

This is very common. See e.g. number theory, where you can ask questions like “what is the probability that two randomly chosen natural numbers are coprime”; the set of natural numbers is also unbounded, but it doesn't prevent this question from being well-defined, and the answer is 6/π² (about 0.608).

ptero2• 2 years ago

They are also discrete, coming from a finite set. I remember at the undergrad differential equation class the teacher asked for some arbitrary coefficients so we can classify the result.

She was very surprised that 3 differential equations she got all turned out to be parabolical, which form a set of probability 0 in the full space. But of course the probabilities for equations with small integer coefficients (which is what people wrote) are totally different.

owyn3• 2 years ago

You can't uniformly sample an unbounded set.

I was asked to do this as an interview question at google! It was about log file processing not math (sample an infinite log file), and I thought my answer was ok? But that's why I don't work there so I am really enjoying this whole thread.

ykonstant2• 2 years ago

As stated in the definition, the distribution is that of independent uniform coefficients in (-1,1).

thaumasiotes2• 2 years ago

True, but they give a justification for that distribution, and the justification is incorrect.

The number of real roots of a random polynomial with real coefficients is much smaller than the number of complex roots. Assume that the coefficients are independently and uniformly random in (−1,1) for if not then we can divide each coefficient by the coefficient with the largest absolute[] value to scale each coefficient to (−1,1).

It's true that, if you have a known polynomial, you can normalize the coefficients in this way... assuming that (-1, 1) is a typo for [-1, 1].

But it's definitely not true that you can produce a random polynomial as the input to this idea. That can't be done. The concept of "a random polynomial with real coefficients" is known not to exist; you would have to specify some kind of nonuniform distribution over the reals for the coefficients to be drawn from. Once you have done this, the distribution of coefficients in the normalized equivalents that have coefficients in [-1, 1] will not be uniform.

In other words, the question says "assume that the coefficients [of a random polynomial] are independently and uniformly random in (-1, 1), for if not, we can exhibit equivalent polynomials whose coefficients are dependently and nonuniformly random in [-1, 1]". But this observation makes no sense.

andrewla• 2 years ago

If you're looking to run some numerical experiments with this, there is built-in support in R for this sort of thing:

    plot(polyroot(runif(101,-1,1)))

will give you a visualization of the roots of a polynomial of degree 100.

dahart2• 2 years ago

Assume that the coefficients are independently and uniformly random in (−1,1) for if not then we can divide each coefficient by the coefficient with the largest absolutely value to scale each coefficient to (−1,1).

Not sure about my intuition here, but won’t scaling this way create a non-uniform distribution for all but the largest coeffs, since the scaling is a divide?

klyrs2• 2 years ago

Yeah, but you can't pick a random real number with uniform distribution. Something's gotta give.

axblount2• 2 years ago

The important thing is that multplying a polynomial by a constant doesn't change its roots.

dahart2• 2 years ago

Ah right, of course. The original coefficient space would still be uniform. I guess this means that a bi-unit [-1,1] interval for the random numbers is equivalent to any space of coefficients [-n,n] when it comes to answering the probability question?

charlieyu1• 2 years ago

Now it surprised me as a guy who studied a lot of math. I would think the complex plane is much larger than the real line so the probability would go towards 0.

guyomes• 2 years ago

That would probably be true if all the coefficients were complex numbers. The biais here comes from the fact that all the coefficients are real numbers.

axblount2• 2 years ago

The real line and the complex plane have the same cardinality.

pama7• 2 years ago

I am not sure why the point that reals appear to be more likely would be counterintuitive. If instead of uniform random real coefficients in an interval one picked uniform random roots in a circular disk centered at the origin of the complex plane as the way to construct polynomials, there is a fat chance that one almost never gets a polynomial with real coefficients back, whereas if the random roots were real then the polynomial is guaranteed real. So a priori neither of the possible answers would be surprising and getting reals to be more likely seems a bit more intuitive to me, though not necessary.

eigenket7• 2 years ago

A polynomial of order n has n roots (real and complex). A random polynomial has roughly log(n) of those be real and n - log(n) be nonreal.

For large n, log(n) is tiny compared to n, so it's very surprising that over half the time the largest root is one of the tiny number of real roots

pama7• 2 years ago

Thanks. Finding the right combo to balance the largest root if it were non-real and end up with real coefficients seems harder than balancing a smaller root, ie the polynomial with the larger real root also has an n-1 degree polynomial with real coefficients and smaller maximal root as a factor, whereas for the one with a non-real largest root this n-1 polynomial factor has to have non-real coefficients in a way that exactly balance the largest term to make all coefficients real again and now has less space in the complex plane in order to do so. I am not explaining it well as I am away from a keyboard and I am sure it is very complicated to prove but I am not a priori very surprised either way.

Is the largest root of a random real polynomial more likely real than complex?

Related Stories