Timeline for Probability a polynomial has a root which is a root of unity
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Jun 18, 2014 at 9:21 | vote | accept | Simd | ||
| May 30, 2014 at 5:27 | comment | added | ofer zeitouni | @fedja yes it was a typo on my side. And thanks for the argument. | |
| May 30, 2014 at 1:50 | comment | added | fedja | @ofer zeitouni Every $d$ consecutive powers of the root are linearly independent over $\mathbb Q$ and for (vector-valued) independent symmetric random variables, we have $P(X+Y=0)\le\sqrt{P(X+X'=0)P(Y+Y'=0)}$, etc. ($Z'$ is an independent copy of $Z$, and I assume that the difference between the formula in you comment and that in mine is just a typo on your side). | |
| May 29, 2014 at 7:18 | comment | added | ofer zeitouni | @Fedja, where does the $(1+c/n)^{-d/2}$ estimate come from? Does it hold for $d=d(n)$? | |
| S May 28, 2014 at 19:59 | history | suggested | F. C. |
added one tag
|
|
| May 28, 2014 at 19:58 | review | Suggested edits | |||
| S May 28, 2014 at 19:59 | |||||
| May 28, 2014 at 18:41 | answer | added | user21349 | timeline score: 16 | |
| May 28, 2014 at 18:33 | comment | added | user21349 | The question of whether $-1$ is a root of $P$ can be related to the question of whether $1$ is a root of the polynomial $P^*$ whose odd-$i$ coefficients have had their signs flipped. For large $n$, the probability that these two polynomials are distinct gets exponentially close to 1. For large $n$, the probability that both 1 and $-1$ are roots is small, so the probability that $\pm 1$ is a root is double the probability that 1 is a root. So taking into account fedja's comment, we just need to estimate the probability that 1 is a root. | |
| May 28, 2014 at 16:13 | comment | added | Simd | @MarcoGolla An asymptotic estimate would be great. Thank you. | |
| May 28, 2014 at 14:36 | comment | added | Marco Golla | Are you interested in an asymptotic estimate? In lower/upper bounds? Exact values? | |
| May 28, 2014 at 14:28 | answer | added | user44143 | timeline score: 13 | |
| May 28, 2014 at 13:52 | comment | added | fedja | I do not have time for the full computation now, but let me still note that the probability that $1$ is a root is already of order $n^{-1/2}$ and that the number of cyclotomic polynomials of degree $d$ is at most $e^{Clog d\log\log d}$, so the probability that we have a root of some cyclotomic polynomial of degree $d$ is at most $e^{Clog d\log\log d}(1+c\frac nd)^{-d/2}$), which shows that we do not really need to bother much about anything except $\pm 1$ for large $n$. | |
| May 28, 2014 at 8:32 | comment | added | Marco Golla | A somewhat related question: mathoverflow.net/questions/166068/… | |
| May 28, 2014 at 8:07 | history | asked | Simd | CC BY-SA 3.0 |