All Questions
Tagged with computability-theory nt.number-theory
48 questions
5
votes
1
answer
469
views
Is the set of generalized Fermat triples computable?
Is $\;\big\{(a,b,c)\in\mathbb{N}^3: \big(\exists m,n,\ell \in (\mathbb{N}\setminus\{0,1,2\})\big): a^m + b^n= c^\ell\big\}\;$ computable?
- 48.9k
1
vote
1
answer
150
views
Resource request (probability theory, computability theory, algebra)
I'm a first year graduate student trying to explore specific topics I might be interested in researching. Currently, I enjoy algebra, probability theory, and the computability theory side of logic, ...
- 121
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
16
votes
2
answers
1k
views
Is it decidable whether two real algebraic irrationals generate the same extension of the rationals?
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
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 $...
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
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
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
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
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
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
13
votes
2
answers
1k
views
What is known in general about the liquid transfer problem?
In several puzzle books, I have seen the following kind of a problem: there are several containers that can hold up to certain amounts of liquid (these liquids are assumed to be infinitely divisible). ...
- 2,075
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
0
votes
1
answer
81
views
Normal $0,1$-sequence with infinitely many frequent finite substrings
Let $\mathbb{N}$ denote the set of non-negative integers. We can identify every bitstream, i.e. a function $s:\mathbb{N}\to \{0,1\}$, with some $A\in{\cal P}(\mathbb{N})$: take $A = s^{-1}(\{1\})$.
...
- 48.9k
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
2
votes
1
answer
152
views
Computationally random bitstreams and normalcy
Let $\mathbb{N}$ denote the set of non-negative integers. We can identify every bitstream, i.e. a function $s:\mathbb{N}\to \{0,1\}$, with some $A\in{\cal P}(\mathbb{N})$: take $A = s^{-1}(\{1\})$.
...
- 48.9k
35
votes
2
answers
7k
views
Is there a known Turing machine which halts if and only if the Collatz conjecture has a counterexample?
Some of the simplest and most interesting unproved conjectures in mathematics are Goldbach's conjecture, the Riemann hypothesis, and the Collatz conjecture.
Goldbach's conjecture asserts that every ...
- 1,173
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
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
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
-1
votes
1
answer
70
views
Computability of a relation connected to the discrete logarithm [closed]
Informally speaking, I was wondering whether the relation
$a^k \equiv b \text{ (mod } n)$ for some $k,n$
is computable. More formally: Let $\mathbb{N}$ denote the set of the positive integers and ...
- 48.9k
3
votes
1
answer
209
views
How does the minimal size of a rational solution to a system of polynomial equations depend on parameters?
The undecidability of Hilbert's tenth problem implies the following (there is a stronger statement here, Theorem 9):
For any computable function $f$, there is a family of integer polynomials (where ...
- 934
2
votes
2
answers
169
views
Decidability of matrix problem in ${\mathbb Z}/p{\mathbb Z}$
Let $p$ be a prime number, $n$ be a positive integer, and let ${\mathbb Z}_p^{n\times n}$ denote the set of $n\times n$-matrices over ${\mathbb Z}/p{\mathbb Z}$.
Suppose we are given an integer $m>...
- 48.9k
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
8
votes
2
answers
752
views
Paul Cohen on genesis of method of forcing and mathematical similarities
We have on record Paul Cohen's comments on being inspired by issues of formalizing algorithms in number theory (this needs to be verified as per comment) as well as related remarks on computability. ...
- 16.6k
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
1
vote
1
answer
631
views
Computability of prime difference function
Consider the following function $f: \omega\to \{0,1\}$:
Set $f(n) = 1$ if for all $k\in \omega$ there are prime numbers $p,q > k$ such that $n = p-q$, and
set $f(n) = 0$ otherwise.
(Trivially, ...
- 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
16
votes
1
answer
555
views
Computer software for periods
Kontsevich and Zagier define a period as an integral of a rational function (over $\mathbb{Q}$) defined on a $\mathbb{Q}$-semialgebraic set. They conjecture that if two periods are equal, then the ...
- 109k
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
15
votes
1
answer
1k
views
Is there a known primitive recursive upper bound on the nth "Zhang prime"
(This question is pure curiosity. Feel free to close it if you feel it is not appropriate for mathoverflow.)
In 2013 Zhang showed that there are infinitely many pairs of primes which are less that ...
- 6,287
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
1
vote
2
answers
490
views
Rationale behind an requirement on Turing machines
Hopcroft and Ullman's definition of a Turing machine seems to be standard. This definition defines a Turing machine to be a 7-tupel $T = \langle Q,\Gamma,b,\Sigma,\delta,q_0,F \rangle$ obeying some ...
- 9,720
-1
votes
1
answer
419
views
What is the probability that a randomly chosen number from set of c.e.number is period(number)?
What is the probability that a randomly chosen number from the set of c.e.numbers is period(number)?
What is the probability that a randomly chosen number from the set of computable numbers is ...
- 3,094
3
votes
1
answer
360
views
What is the relation between KC and height of rational number?
Roughly speaking,Kolmogorov Complexity of a bits string or a description is the minimal length of programs outputing a bits string,and height of rational number is logarithm of the largest numerator ...
- 3,094
4
votes
1
answer
429
views
N^2 and two counter machines
I asked this question on cstheory a few months ago, but I didn't receive an answer, so I'm posting it here to see if there are original ideas from the "math world" to solve it. The original question ...
- 1,602
33
votes
3
answers
6k
views
Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?
Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...
- 19.6k
1
vote
1
answer
324
views
Problem to a solution
Consider an NP hard problem $\frak P$ which takes an input of length n
$\frak P$ can be solved partially by a factor $ p_i = p(n,i)\in$ [0,1)... by a polynomial time algorithm $\mathcal A(i)$ ...
- 11
24
votes
1
answer
1k
views
Are sums of sequences decidable?
Suppose that $f,g$ are rational functions with integer coefficients such that $\sum_{n=0}^{\infty}f(n)$ and $\sum_{n=0}^{\infty}g(n)$ both converge. Is it decidable whether
$\sum_{n=0}^{\infty}f(n)=\...
49
votes
5
answers
5k
views
Are the two meanings of "undecidable" related?
I am usually confused by questions of the type "could such and such a problem be undecidable", because as far as I know there are two distinct possible meanings of "undecidable". ...
- 18.7k
46
votes
3
answers
3k
views
Does an existence of large cardinals have implications in number theory or combinatorics?
Does an existence of large cardinals have implications in more down-to-earth fields like number theory, finite combinatorics, graph theory, Ramsey theory or computability theory? Are there any ...
- 1,699
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
0
votes
1
answer
158
views
any given c.e.set has number M whose power bounds the corresponding elements of S?
For S ,any given c.e.set,does there exist a M (integer) and a partially computable function outputing every element of S the c.e.set ,such that $\forall x\in S,\exists n x=f(n)$ and $x=f(n)\leq ...
- 3,094
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
1
vote
1
answer
580
views
Relation between partially computable function and complex function
Given a partially computable function, is there an analytic complex function which is equal to it at every point of it's domain? Or under what condition does a partially computable function correspond ...
- 3,094
3
votes
2
answers
912
views
Why is every finite set Diophantine? [closed]
I understand that every finite set is recursively enumerable, as I see that one could just encode each element of some finite set on a Turing Machines tape, and then have the machine check each member ...
