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
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 6, 2013 at 22:31 | comment | added | Stefan Kohl♦ | Indeed whether the surjectivity problem is strictly harder than HTP for $\mathbb{Q}$ is interesting as well, and as long as one doesn't know the answer to HTP for $\mathbb{Q}$ or if the answer is positive, it is indeed a separate question. -- So definitely, I would find it interesting to get this answered. | |
| Aug 6, 2013 at 21:38 | comment | added | Sidney Raffer | @Stefan; Actually there is a third question that I wish I could answer. My argument shows that an oracle for determining surjectivity of rational maps could be used to test for rational zeros of polynomials. But is the converse true? Or is the surjectivity problem strictly harder than HTP for the rationals? | |
| Aug 6, 2013 at 19:28 | comment | added | Stefan Kohl♦ | Finally, only two problems remain: the first is the question whether there is a polynomial which maps $\mathbb{Q}^n$ to $\mathbb{Q}$ injectively, and the second is Hilbert's Tenth Problem over $\mathbb{Q}$. There is little hope for solving the latter here, but of course it would be nice to find an answer to the former question (which seems to be of unclear difficulty). In any case I think the answer is nice enough to accept at this point. | |
| Aug 6, 2013 at 19:15 | vote | accept | Stefan Kohl♦ | ||
| Aug 6, 2013 at 18:11 | history | edited | Sidney Raffer | CC BY-SA 3.0 |
added 67 characters in body
|
| Aug 6, 2013 at 18:07 | comment | added | Sidney Raffer | @Stefan: I've added an argument for the surjectivity problem over Q. | |
| Aug 6, 2013 at 18:02 | history | edited | Sidney Raffer | CC BY-SA 3.0 |
added 2103 characters in body
|
| Aug 3, 2013 at 21:10 | comment | added | Stefan Kohl♦ | What is now still missing is an answer to the question whether surjectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ is algorithmically decidable -- respectively, an argument telling that this is also equivalent to Hilbert's Tenth Problem over $\mathbb{Q}$ or the like. | |
| Aug 3, 2013 at 21:07 | comment | added | Stefan Kohl♦ | But is there an injective polynomial from $\mathbb{Q}^n$ to $\mathbb{Q}$? -- This seems quite plausible, but Jonas Meyer's comment I referred to in the question suggests that it is at least in no way obvious. | |
| Aug 2, 2013 at 22:31 | comment | added | Sidney Raffer | Actually, the injectivity argument works perfectly well over the rationals, provided that there is at least one injective polynomial that maps QxQ into Q. The upshot is that injectivity is decidable if and only if Hilbert's Tenth Problem for field of rational numbers is effectively solvable. | |
| Aug 2, 2013 at 22:18 | comment | added | Stefan Kohl♦ | Very nice. Thanks! -- Is there any chance to adapt this argumentation to answer the 'main' part of the question, i.e. the one on polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$? | |
| Aug 2, 2013 at 18:56 | history | edited | Sidney Raffer | CC BY-SA 3.0 |
added 5 characters in body
|
| Aug 2, 2013 at 18:39 | history | answered | Sidney Raffer | CC BY-SA 3.0 |