Timeline for A factorization game
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2019 at 20:04 | comment | added | Seva | @fedja: This is more or less the observation made also by Fedor Petrov as a comment to my previous post. Unfortunately, it does not answer the question: I'd like to see even one, but specific polynomial. My hope is that the proof for this one polynomial can be extended to yield a general necessary condition that the head / middle part of a fully reducible polynomial must satisfy. Very loosely speaking, I'd like to have a kind of the Descartes rule of signs for the finite fields settings. | |
| May 8, 2019 at 18:46 | comment | added | fedja | One "hidden reason" is symmetry: you have only about $4^p$ ways to choose your roots because the permutations do not matter and I have about $p^{p/10}$ ways to choose my top coefficients, so I wouldn't even bother to think if $p$ is large, just roll a $p$-sided die. | |
| May 7, 2019 at 15:35 | comment | added | Gerhard Paseman | Try this for a simulation. Let you and A take turns. Given p, A starts on turn 1 and names coefficient for p-1. You name root 1. On turn j A names coefficient for (power of) p-j, and then you name root j. How far can you go before you lose (no way that your product of linear factors will match the named polynomial of A)? My guess is you can simulate a few turns for small p and extrapolate to large p. Gerhard "But Don't Game The Results" Paseman, 2019.05.07. | |
| May 7, 2019 at 13:34 | history | edited | Seva | CC BY-SA 4.0 |
added 1217 characters in body
|
| May 7, 2019 at 9:33 | comment | added | Seva | @joro: Exactly - my question is about these possible hidden reasons! | |
| May 7, 2019 at 9:30 | comment | added | joro | OK, I didn't examine it carefully. In general greatly underdetermined system will have solution over F_p, unless there is some hidden reason. | |
| May 7, 2019 at 9:26 | comment | added | Seva | @joro: The system is actually greatly underdetermined, as the number of variables $2\deg B$ is much larger than the number of equations $\deg B-0.9p$ - or have you meant anything else? | |
| May 7, 2019 at 8:59 | comment | added | joro | Working symbolically write $B=\prod_i X_i x + Y_i$. After equating coefficients you have $2 \deg(B)$ unknowns and $\deg(B) - 0.9p$ equations. If the system is overdetermined likely it won't have solutions. | |
| May 6, 2019 at 15:14 | history | asked | Seva | CC BY-SA 4.0 |