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
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:57 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Aug 8, 2013 at 9:23 | history | edited | Stefan Kohl♦ | CC BY-SA 3.0 |
Added list of questions left open by SJR's answer.
|
| Aug 6, 2013 at 19:15 | vote | accept | Stefan Kohl♦ | ||
| Aug 2, 2013 at 18:39 | answer | added | Sidney Raffer | timeline score: 29 | |
| Jul 30, 2013 at 12:38 | answer | added | joro | timeline score: 3 | |
| Jul 30, 2013 at 0:08 | comment | added | Will Sawin | I'm just saying the same method probably won't work. | |
| Jul 29, 2013 at 23:38 | answer | added | Igor Rivin | timeline score: 2 | |
| Jul 29, 2013 at 23:22 | comment | added | Stefan Kohl♦ | @WillSawin: There could still be an easy proof that injectivity is algorithmically undecidable -- who knows ... . | |
| Jul 29, 2013 at 22:44 | comment | added | Will Sawin | It seems hard to do injectivity in a similar way, because it seems hard to prove injectivity! Any reduction would produce lots and lots of examples of injective polynomials $\mathbb Z^n \to \mathbb Z$, which I don't think we have many of currently. | |
| Jul 29, 2013 at 22:36 | history | edited | Ricardo Andrade |
changed tags
|
|
| Jul 29, 2013 at 20:28 | comment | added | Henry Cohn | Oops, I gave a correct argument given a polynomial that takes on every value except 0, but an incorrect polynomial with that property. Replacing it with $(1+y_1^2+\dots+y_4^2)(1+2y_5)$ works (unless I'm messing up again), but SJR's solution is nicer. | |
| Jul 29, 2013 at 19:54 | comment | added | Stefan Kohl♦ | @SJR: Very nice argument! -- Can injectivity possibly be dealt with in a similar way? | |
| Jul 29, 2013 at 19:51 | comment | added | Joel David Hamkins | @SJR, why not post your comment as an answer? | |
| Jul 29, 2013 at 19:51 | comment | added | Stefan Kohl♦ | @SamHopkins: maybe -- though not necessarily ... . | |
| Jul 29, 2013 at 19:48 | comment | added | Stefan Kohl♦ | @HenryCohn: sorry, but I don't understand your argument: as I see, the polynomial $(2+2(y_1^2 + \dots + y_4^2))(1+2y_5)$ you give takes only even values. Also, I think the polynomial $p(x_1, \dots, x_n)^2 + z^2$ takes only nonnegative values. | |
| Jul 29, 2013 at 18:31 | comment | added | Sidney Raffer | There is no algorithm to test if $f:\mathbb{Z}^n\to \mathbb{Z}$ is surjective, by reduction to Hilbert's Tenth Problem: An arbitrary polynomial $g(x_1,\ldots,x_n)$ has an integral zero if and only if $h:=x_{n+1}(1+2g(x_1,\ldots,x_n)^2)$ is surjective. (For the right-to-left implication, note that $g$ must vanish where $h$ takes the value 2.) | |
| Jul 29, 2013 at 18:31 | comment | added | Henry Cohn | Over $\mathbb{Z}$, surjectivity is certainly undecidable (but injectivity seems harder, as does working over $\mathbb{Q}$). Consider any polynomial that takes on every value except $0$. For example, $(2+2(y_1^2+\dots+y_4^2))(1+2y_5)$ (probably not the simplest construction). Then multiplying this polynomial by $p(x_1,\dots,x_n)^2 + z^2$ gives a polynomial that takes on every integer value iff $p(x_1,\dots,x_n)=0$ has a solution. | |
| Jul 29, 2013 at 18:14 | comment | added | Joel David Hamkins | Great question. To establish undecidability, perhaps we might hope somehow to reduce the diophantine solution problem over $\mathbb{Z}$ to the injectivity problem for $\mathbb{Z}$... | |
| Jul 29, 2013 at 18:14 | comment | added | Sam Hopkins | Since Hilbert's tenth problem over $\mathbb{Q}$ is an open problem (see e.g. www-math.mit.edu/~poonen/slides/h10.pdf), you would have to think this is also open. | |
| Jul 29, 2013 at 17:33 | history | asked | Stefan Kohl♦ | CC BY-SA 3.0 |