All Questions
10 questions
5
votes
1
answer
310
views
Parity of number of solutions to Diophantine equations
By $MRDP$ resolution of Hilbert's tenth, we infer, counting number of solutions to Diophantine equations is undecidable.
Is parity of number of solutions to Diophantine equations undecidable?
- 13.9k
6
votes
1
answer
641
views
How constructive is Matiyasevich's theorem?
A famous corollary of Matiyasevich's theorem is that there exists a Diophantine equation such that it is undecidable (under some recursively axiomatizable theory $T$, such as ZFC) whether that ...
- 1,311
21
votes
1
answer
1k
views
Is "almost-solvability" of Diophantine equations decidable?
Say that a Diophantine equation is almost-satisfiable iff for each $n\in\mathbb{N}$ it has a solution mod $n$. Trivially genuine satisfiability over $\mathbb{N}$ implies almost-satisfiability, but the ...
- 21.2k
7
votes
0
answers
274
views
Is decidability reducible to unique decidability (perhaps in multilinear polynomial situations)?
Given a Diophantine equation it is not decidable if it has integer solution.
I. Is there a Diophantine set $\mathcal D_{unique}$ satisfying the properties
every member in $\mathcal D_{unique}$ is a ...
- 13.9k
16
votes
3
answers
1k
views
Is Multilinear Hilbert's tenth problem version undecidable?
A multilinear polynomial $f\in\mathbb Z[x_1,\dots,x_t]$ has terms only of form $$b\prod_{i=1}^tx_i^{a_i}$$ where $a_i\in\{0,1\}$ and $b\in\mathbb Z$.
Is there no general purpose algorithm for ...
- 13.9k
56
votes
7
answers
7k
views
What is the smallest unsolved Diophantine equation?
If $P=\sum_{\bf i} a_{\bf i}x^{\bf i}\in {\mathbb Z}[x_1,\dots,x_d]$, let $|P|=\sum_{\bf i}|a_{\bf i}|x^{\bf i}$ and $h(P)=|P|(2,\dots,2)$, so that there is only a finite number of $P$ with $h(P)\leq ...
- 937
4
votes
0
answers
225
views
Short Diophantine definition of the sum-of-divisors function (using less than 100 variables)?
Is there a short Diophantine definition of the sum-of-divisors function? Is there a polynomial $p$ such that
$$c = \sum_{d|n}d \ \leftrightarrow \ \exists x_1, \ldots x_{100}\ p(c,n,x_1, \ldots x_{...
user44143
12
votes
1
answer
334
views
Sets of integers represented by degree zero rational functions
Suppose $f(x_1,x_2,\dots)=\frac{P}{Q}$, where $P,Q$ are polynomials in several variables with integer coefficients that have the same degree. Let's denote by $S(f)$ the set of integers $n$ for which $...
- 85.6k
58
votes
3
answers
4k
views
What is the geometry of an undecidable diophantine equation?
As an arithmetic algebraic geometer of the highest moral fiber, I am trained to look at Diophantine equations in terms of the geometry of the corresponding scheme. For instance, if the Diophantine ...
- 148k
10
votes
2
answers
822
views
Is there a two-variable prime-representing polynomial (in the sense of Jones-Sato-Wada-Wiens)?
In the math.se question Proof of no prime-representing polynomial in 2 variables, Alon Amit asks if Ribenboim's claim that a prime-representing polynomial (a Diophantine polynomial in which the ...
- 9,114