8 ms·
Is the largest root of a random real polynomial more likely real than complex?
- Sebb767 2y agoFor those not well versed in the Stack Exchange network, what's the difference between Math Stack Exchange and Math Overflow?
- jjgreen 2y agoMO is for research-level discussions, questions are often bumped from one to the other (more often from MO to MSE).
- admissionsguy 2y agoI 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 2y agoHonestly 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.
- deleted 2y ago[deleted]
- SassyBird 2y agoMSE is for noobs, think HS and uni students. MO is for pros, think PhDs, researchers etc.
- lupire 2y agoAdults, who might or not have graduated or attended high school or University, also use MSE.
- OJFord 2y agoThere are probably some very clever people who are not PhDs nor professional researchers using MO too, GP was just giving examples ('think [...]').
- colechristensen 2y agoThis is not a helpful comment.
- HappyPanacea 2y agoMath Overflow domain and name are owned by a nonprofit organization, see https://meta.mathoverflow.net/questions/969/who-owns-mathoverflow https://meta.mathoverflow.net/questions/969/who-owns-mathove...
- melenaboija 2y 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?
- rvnx 2y agoThey claim "The MathOverflow corporation is completely independent from Stack Exchange" and then when you click Legal notice, you see that all conditions and legal of Stack Exchange applies. In addition: > This letter is to confirm that, per our communications, that MathOverflow ("MathOverflow") agrees that the website, MathOverflow (located at www.mathoverflow.net, www.mathoverflow.com and www.mathoverflow. org (the "MathOverflow Domains"), the assets of which are owned and controlled by MathOverflow, will be upgraded to Stack Exchange, Inc.'s ("Stack Exchange") version 2.0 software model and, in conjunction with this upgrade, MathOverflow accepts Stack Exchange 2.0's Terms of Service (http://stackexchange.com/legal/tems-of-service http://stackexchange.com/legal/tems-of-service, the "Terms" === "completely independent" is perhaps exaggerated claim.
- lupire 2y agoThe corporation is independent, and has the right to unilaterally leave the website at any time. The current website is not independent.
- The_suffocated 2y agoMSE is sometimes perceived as hostile to beginners because it often closes off newbie questions that lack context or are thought to be of low quality. MO is not suffering from this because almost all such questions are migrated to MSE. In this sense, yes, MO is less hostile than MSE because its hostility is outsourced to MSE.
- deleted 2y ago[deleted]
- selimthegrim 2y agoLooking through the links from here one of the answers by Boris Hanin may have resolved a question I had for a while.
- meindnoch 2y agoAs 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 2y agoJust 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 2y agoThe 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.
- chongli 2y ago[flagged]
- vouaobrasil 2y agoHi, I read the post. The numerical approach gives the data. But the proof of the result uses analysis. I was talking about the proof. Thanks.
- LeonardoTolstoy 2y agoI 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_trumpet 2y agoI 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 2y agoWhat do you mean with reflection across the bottom/top of the curve? With combination you presumably mean taking (polynomial+reflected polynomial)/2?
- LeonardoTolstoy 2y agoAh 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
- keepamovin 2y agoWow 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_dshiv 2y agoBeautiful! Phi always seems to show up when there is crowding.
- keepamovin 2y agoThanks! Let's collab. We should start a "primes investigation" github repo!!!! :)
- dr_dshiv 2y agoI love number theory in the context of waves. Here’s an example: https://arxiv.org/pdf/1910.10751 https://arxiv.org/pdf/1910.10751
- keepamovin 2y agoThanks. When you mention waves I'm wondering how we can leverage FFT to make a function of the next prime? But it has to include all primes, I guess? Or is this Reimann, already??
- Analemma_ 2y agoYes, high-level descriptions of the RH are often vague about the connection between the zeta function and the prime numbers, but the short version is that, for every point on on the complex plane, there is an associated real-valued "Riemann harmonic function"; if you sum up the Riemann harmonic functions of the non-trivial zeros of the zeta function, you get the exact prime-counting step function, and this function is much more predictable if the RH is true.
- kzrdude 2y agoThis 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 2y agohttps://math.stackexchange.com/questions/206890/the-egg-bizarre-behavior-of-the-roots-of-a-family-of-polynomials https://math.stackexchange.com/questions/206890/the-egg-biza... ?
- kzrdude 2y agoThere's many of these then! I think I found the one I was thinking of: https://mathoverflow.net/questions/182412/why-do-roots-of-polynomials-tend-to-have-absolute-value-close-to-1 https://mathoverflow.net/questions/182412/why-do-roots-of-po... See answer by Will Jagy
- Aardwolf 2y agoDoes random polynomial mean with real or complex coefficients, though?
- deleted 2y ago[deleted]
- cool_dude85 2y agoThe 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 2y agoThis 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.
- madcaptenor 2y agoAnd how random sparse polynomials behave would also be an interesting question!
- Someone 2y agoLikely (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.
- eternauta3k 2y ago
- dailykoder 2y agoSligthly 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 2y agoA bit unrelated to your question, but if you love Maths you can't miss The Math Sorcerer: https://www.youtube.com/@TheMathSorcerer https://www.youtube.com/@TheMathSorcerer
- jjgreen 2y agoI 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 2y agoMathematics and Its History (https://link.springer.com/book/10.1007/978-1-4419-6053-5 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 https://link.springer.com/book/10.1007/978-3-662-57265-8).
- ptero 2y agoTwo 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.
- lupire 2y agoRight. 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__ 2y 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).
- mturmon 2y agoThis comment opens perhaps a bigger can of worms than intended. The original statement: >> You can't uniformly sample an unbounded set. [of real numbers] is true, provided that by "sample" we mean "sample in a way that obeys Kolmogorov's axioms". (I'm adding the qualifier "of real numbers" to keep this somewhat grounded, so that we don't get distracted with abstract metric spaces, or worse.) In the above comment, by placing a limit on the set ([-N, +N]), you have made the set bounded -- thereby contradicting the premise of the original statement! * Your last paragraph is interesting. Suffice to say, the situation is more complex than your summary would indicate, precisely because of the above issue -- that is, "what does sample mean in this context". It led me to this paper by Lei and Kadane (the latter, the well-known Bayesian theorist) -- https://arxiv.org/pdf/1806.00053 https://arxiv.org/pdf/1806.00053 It is well worth a read, if you're into such things. See especially section 1, and section 7. In essence, the above statement ("You can't sample uniformly") is true, if you interpret "sample" as "following a scheme that obeys Kolmogorov's well-known axioms." However, if you are willing to abandon countable additivity of your measure, and drop down to finitely-additive measures, there are several classes to choose from that support a notion of uniformity. (Again, just thinking about measures on integers, not real numbers. But these are not measures in Kolmogorov's sense.) These measures support a notion of uniformity, but they may not have some properties that you might hope for, such as that the measure of a set A of natural numbers is the same as A + i, where adding "i" shifts the set by "i" units left or right. For some of these measures, the result about co-prime numbers is as you say, and for others, the result is indeterminate. That is, the limit exists, but it can be any number between 0 and $6/\pi/\pi$.
- andrewla 2y agoIf 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.
- dahart 2y 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?
- charlieyu1 2y agoNow 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.
- pama 2y agoI 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.
- eigenket 2y agoA 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
- pama 2y agoThanks. 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.
- eigenket 2y agoI think you're thinking about it in a slightly weird way, if I am understanding you correctly. Picking random roots would be a very different thing. Here were only dealing with polynomials whose complex roots come in conjugate pairs (I.e. if a+ib is a root then so is a-ib) this gives you real coefficients "for free" since (x - (a+ib))(x-(a-ib)) = x^2 -2ax + a^2 + b^2 Theres no coincidental balancing act in choosing the roots to obtain real coefficients. It happens because of the type of polynomials we've chosen.
- angela-misan 2y ago[dead]