All Questions
8 questions
6
votes
1
answer
669
views
Hilbert's tenth problem for equations with finitely many solutions
Is there a known example of a set $S$ of Diophantine equations such that
$S$ is computable;
it is a theorem that every equation in $S$ has (at most) finitely many solutions;
the function that maps an ...
- 82.7k
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 ...
- 20.5k
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
3
votes
0
answers
116
views
Variation in decidability of diophantine equations with field extension
Let $O_k$ be the ring of integers in a subfield $k$ of $\overline{\mathbb{Q}}$. Let's call an equation $p(x_1, \dots, x_n) = 0$ where $p$ is a polynomial in $n$-variables $x_1, \dots, x_n$ with ...
- 31
1
vote
0
answers
216
views
How to solve special Diophantine equation systems (which one can solve by hand) with the computer?
I have a quadratic Diophantine equation system which is possibly not homogeneous and has some mixed and some linear terms.
But I know that there are only finitely many solutions over the integers.
One ...
- 1,755
5
votes
0
answers
356
views
minimum size of undecidable quadratic diophantine problems
According to Matiyasevich, the existence of integer solutions of systems of polynomial equations with integer coefficients is undecidable. By introducing additional variables substituting factors of ...
- 3,873
18
votes
0
answers
1k
views
Is the set of integers of the form $a/(b+c)+b/(a+c)+c/(a+b)$ computable?
The starting point of this question is the observation that the smallest positive integers $a,b,c$ satisfying
$$\frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} = 4$$
are absurdly high, namely $$(...
- 48.9k
12
votes
2
answers
1k
views
Why can Diophantine equations represent exponential growth?
The wikipedia page on Matiyasevich's theorem challenges:
Unfortunately there seems to be as yet no short intuitive explanation as to why Diophantine equations can represent exponential growth only ...
- 595