Timeline for How to tell if two random polynomials are identical
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 4, 2016 at 17:28 | comment | added | Bill Dubuque | @Gerry This theorem explains why radix representation remains unique after said extension to allow negative digits. It boils down to a simple root bound: an integer root of $\,f(x)\in\Bbb Z[x]\,$ divides the nonzero coefficient of least degree (a slight generalization of the obvious fact that roots divide the constant coefficient). | |
| Sep 24, 2010 at 23:03 | comment | added | Gerry Myerson | @Tony, good. Now, what if all you're told is that $c\ge-100$ for all coefficients $c$? Or, what if all you're told is that at most 17 of the coefficients are negative? | |
| Sep 24, 2010 at 14:24 | history | edited | Tony Huynh | CC BY-SA 2.5 |
added 382 characters in body; added 12 characters in body; deleted 14 characters in body
|
| Sep 24, 2010 at 10:52 | comment | added | Tony Huynh | @Gerry: If we allow for negative coefficients but are told that $|c| \leq b$ for all coefficients $c$, then we can always do it with one evaluation. Let $n$ be a power of 10 such that $n \geq 2b+1$. Then I think $P$ and $Q$ are equal if and only if $P(n)=Q(n)$. For example, if I am told that all coefficients of $P$ lie in [−4,4] then we can recover $P$ by computing $P(10)$. To recover $p_0$ say, simply note that $p_0 \equiv P(10)$ (mod 10), and this works regardless of the sign of $P(10)$. Once I know $p_0$ (mod 10), I know it exactly. Once I know $p_0$, I can work (mod 100) to get $p_1$. | |
| Sep 24, 2010 at 0:35 | comment | added | Gerry Myerson | The original problem allowed for negative coefficients. Is there a variation on this trick that will still work in that case? | |
| Sep 23, 2010 at 18:14 | comment | added | Nate Eldredge | That's a cute fact! | |
| Sep 23, 2010 at 15:39 | comment | added | Tony Huynh | Sure, instead of taking P(1)+1, we can let n be a power of 10 that is bigger than P(1). Then if we compute P(n), we can 'just read off' the coefficients of P. | |
| Sep 23, 2010 at 14:57 | comment | added | JBL | Consider the case when P(1) is a power of 10 to make it particularly transparent. | |
| Sep 23, 2010 at 14:43 | comment | added | Tony Huynh | Note that $P(1)$ is just the sum of the coefficients of $P$. If the coefficients are all non-negative, then in particular they are all at most $P(1)$. So, if we express $P(P(1)+1)$ in base $P(1)+1$ we completely recover the coefficients of $P$. | |
| Sep 23, 2010 at 14:29 | comment | added | Steve Huntsman | Why does this work? | |
| Sep 23, 2010 at 14:25 | history | edited | Tony Huynh | CC BY-SA 2.5 |
added 8 characters in body
|
| Sep 23, 2010 at 14:00 | history | answered | Tony Huynh | CC BY-SA 2.5 |