All Questions
Tagged with nt.number-theory computability-theory
19 questions with no upvoted or accepted answers
28
votes
0
answers
907
views
On certain representations of algebraic numbers in terms of trigonometric functions
Let's say that a real number has a simple trigonometric representation, if it can be represented as a product of zero or more rational powers of positive integers and zero or more (positive or ...
- 6,819
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
17
votes
0
answers
808
views
Decidability of $x^3+y^3+z^3 = c$
I wondering if it is known whether the following problem is algorithmically decidable or undecidable by Turing machines: given an integer c, determine if there are integers $(x,y,z)$ such that $x^3+y^...
- 171
17
votes
0
answers
969
views
Groups generated by 3 involutions
Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$\tau_{r_1(m_1),r_2(m_2)}$ be the ...
- 19.6k
9
votes
0
answers
346
views
Is Videla's solution of Hilbert's tenth problem for rational functions over field of characteristic 2 wrong?
The paper in question.
Quick introduction to the problem: suppose that $F$ is a finite field of characteristic 2
(for purposes of this post $F = \mathbb{F}_2$ will suffice) and let $F[t]$ and $F(t)$ ...
- 543
7
votes
0
answers
257
views
Computability assertions for Riemann zeta zeros
While looking for information about the Riemann zeta function, I kept running into the claim that there is an algorithm to decide whether or not a zero of the function is off the half-line. Is this ...
- 18.7k
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
7
votes
0
answers
98
views
Deciding when certain elements of $L[[x]]$, coming from recursions, are algebraic over $L(x)$
Let $L$ be a finite field of characteristic $2$. Suppose that for some $k > 0$ we are given elements $A(0),\, A(1), \dots, \, A(k-1)$ and $c(0),\, c(1), \dots,\, c(k-1)$ of $L[t]$. Define $A(n)$ ...
- 5,422
5
votes
0
answers
187
views
Is there an effective way to compute the square root of an algebraic number?
For an algebraic number $\alpha$, let $f_\alpha$ denote its minimal polynomial. We can symbolically represent an algebraic number $\alpha$ by the tuple
$$
(f_\alpha, x, y, r) \in \mathbb{Q}[x] \times ...
- 1,087
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
4
votes
0
answers
249
views
Coefficients in Hilbert's tenth problem over number rings: do they matter?
Here are two ways to define Hilbert's tenth problem over a ring $R$:
Given a polynomial $p \in \mathbb Z[x_1,\ldots,x_n]$, can one decide whether it has a solution in $R^n$?
Given a polynomial $p \in ...
- 934
3
votes
0
answers
186
views
Decidable equality for computable functions $\mathbb{N}\to\mathbb{N}$
Suppose we have two computable functions $f, g:\mathbb{N}\to\mathbb{N}$. When is $f=g$ algorithmically decidable?
For example it is decidable if $f$ and $g$ are polynomials of a priori known degree.
- 31
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
3
votes
0
answers
240
views
Complexity of representations of sets using elementary functions
Fermat conjectured that $2^{2^n}+1$ is prime for every $n \in \mathbb{N}.$ Before even knowing about Euler's counterexample (that $2^{32}+1 = 641 \cdot 6700417$), you could possibly say that Fermat ...
- 745
3
votes
0
answers
454
views
What is the relation between the length of period of simple continued fraction expansion of quadratic algebraic numbers $\sqrt{A}$ and the integer $A$
What is the relation between the length of period of simple continued fraction expansion of quadratic algebraic numbers and the integer
As we know,$\sqrt{2} = [1;2,2,2,2,…]$; while $\sqrt{14}= [3;1,2,...
- 3,094
2
votes
0
answers
200
views
Integers $n$ such that $n^d + (n+1)^d$ is never prime
Let us call an integer $n>0$ pure if for all integers $d>0$ we have that $n^d + (n+1)^d$ is not prime. Is the set of pure integers non-empty? Is it computable?
- 48.9k
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
0
votes
0
answers
234
views
whether the quotient of continued fraction of algebraic irrational number is bounded or not is similar or equivalent to Collatz conjecture?
I vaguely recall that whether the quotient of continued fraction of algebraic irrational number is bounded or not is similar or equivalent to Collatz conjecture, could any one give the reference? or ...
- 3,094
0
votes
1
answer
126
views
Integer quadratic representation subject to discriminant minimization algorithm
Let $f(x)=ax^2+bx+c$ and $f(x)=n$. Is there an algorithm to choose $a,b,c$ such that the discriminant is minimized? Where $a,b,c,n,x$ are all integers.
More concretely, is there an algorithm to find $...
