Timeline for Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 31, 2013 at 5:23 | comment | added | joro | @StefanKohl The algorithm couldn't solve any of your challenges (it was fast since the constant coefficient was zero). You are right it can't disprove surjectivity (I suppose this was clearly stated in the answer). It fails if it can't compute the auxiliary polynomials f_2 .. f_n (they don't exist if f_1 is not surjective and maybe don't exist for certain surjective f_1). Btw, the algorithm needs to solve a nonlinear system which is hard. | |
| Jul 30, 2013 at 15:57 | comment | added | Stefan Kohl♦ | As for test examples, what does your implementation tell about surjectivity / non-surjectivity of $f(x_1,x_2,x_3) = x_1^2+x_2^2+x_3^2$, of $f(x_1,x_2,x_3) = x_1 x_2 x_3$, of $f(x_1,x_2,x_3) = x_1 x_2+x_1 x_3+x_2 x_3$ or of $f(x_1,x_2,x_3,x_4) = x_1^2+x_2^3+x_3^4+x_4^5$? -- And by the way, which computer algebra system do you use? | |
| Jul 30, 2013 at 15:32 | comment | added | Stefan Kohl♦ | Thank you for the explanations! -- Though I find it somewhat difficult to assess the scope of applicability of your sketch of a method. By the way, how can it be detected whether the method fails for a particular polynomial, if at all? -- And is it right that the method cannot be used to disprove surjectivity of any polynomial? | |
| Jul 30, 2013 at 14:08 | comment | added | joro | @StefanKohl In short if you have invertible polynomial map Q^n -> Q^n, all polynomials $f_i$ are surjective. You fix $f$ and the answer tries to find $f_2 \ldots f_n$ and the inverse map. There may be more than one solution. | |
| Jul 30, 2013 at 13:52 | comment | added | joro | @StefanKohl edited the question trying to answer your questions. In short, all $f_i$ are polynomials with range Q. Let me know if you have other questions. | |
| Jul 30, 2013 at 13:51 | history | edited | joro | CC BY-SA 3.0 |
Tried to answe Stefan's questions.
|
| Jul 30, 2013 at 13:12 | comment | added | Stefan Kohl♦ | Thanks. -- But sorry -- there seem to be a few things I don't understand. For the beginning: firstly, the range of the mapping $f$ is $\mathbb{Q}$ rather than $\mathbb{Q}^n$. Secondly, what exactly are the mappings $f_i$ from $\mathbb{Q}^n$ to itself for? Thirdly, which of the coefficients of $f_i$ do you call $c_i$? Fourthly, is $c3x^3 = 3cx^3$ or rather $c3x^3 = c_3x^3$, etc.? | |
| Jul 30, 2013 at 12:38 | history | answered | joro | CC BY-SA 3.0 |