1
vote
2answers
236 views

Infinite play with tape, or covering the integers with prime arithmetic progressions

It is possible that a more technical version of this question has been asked and answered in the literature. If so, then a reference is much appreciated. I will phrase it in terms of colored tapes ...
6
votes
1answer
160 views

Is (Z,+,0,1,P2,P3) decidable?

Is Presburger arithmetic, augmented with two unary predicates P2, P3, for powers of 2 and powers of 3 respectively, decidable? I know that adding just one of P2, P3 to Presburger keeps it decidable, ...
2
votes
1answer
220 views

Elementary proof of bounds on factor polynomials

The question Getting a bound on the coefficients of the factor polynomial got very nice answers on Gelfond's theorem. But for work on proof theory of arithmetic I want a proof in arithmetic. The ...
10
votes
1answer
249 views

Reducibility of polynomials maps

Motivated by this question. Let $f \in \mathbb{Q}[x]$ or$f \in \mathbb{Z}[x]$ . Consider the sequence $f(x),f(f(x)), \ldots f^n(x)$. If some $f^k(x)$ is reducible, the rest iterates will be ...
6
votes
4answers
1k views

Interactions of number theoretic conjectures and other fields of mathematics

There are many interesting open conjectures in number theory. My question is not about partial results or possible ways to prove them. It is about their interactions with the other fields of ...
14
votes
2answers
1k views

Hilbert's 10th problem and nilpotent groups

I am asking this question on behalf of a colleague of mine who does not have an MO account. Nevertheless I am also interested in the answer. The question concerns relationships between Hilbert's ...
12
votes
1answer
665 views

Reverse mathematics of Hilbert's Theorem 90

What is known, and what is published, on the reverse mathematics of the nest of results called Hilbert's Theorem 90?
23
votes
1answer
675 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 ...
12
votes
5answers
821 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". I regard the ...
11
votes
1answer
415 views

First order decidability of rings vs Diophantine decidability

Are there known (preferably ``concrete'') examples of a ring $R$ (commutative, with 1) such that: $\bullet$ the first order theory of $R$ is undecidable, but $\bullet$ the positive existential (= ...
1
vote
1answer
794 views

Are there non-commutative models of arithmetic which have a prime number structure?

Peano Arithmetic (PA) models have a prime number structure and commutativity of addition and multiplication. Presburger arithmetic (PrA) models of arithmetic have addition without multiplication and ...
8
votes
2answers
389 views

Proof theory and primitive roots

I have had this question on my mind for two decades. We know, after Heath-Brown, that one out (say) of 3, 5, 7 is a primitive root mod p for infinitely many primes p. We just don't know which one. (We ...
0
votes
2answers
604 views

Gödel, Escher, Bach: b is a power of 10. [closed]

I’d like to verify if my formula correctly expresses that a number is a power of $ 10 $, using the $ \sf{TNT} $ language provided by Hofstadter in his famous book Gödel, Escher, Bach: An Eternal ...
15
votes
1answer
362 views

What sets of primes can we pick out with first-order statements?

For each prime $p$, we have the algebraically closed field $\bar{\mathbb F}_p$ with the Frobenius automorphism. Given any first-order statement with no free variables using the symbols $0,1, +, ...
10
votes
1answer
254 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 ...
9
votes
0answers
268 views

What is the simplest known arithmetic definition of exponentiation?

For $n$ a natural number, let $E_n$ denote the set of bounded arithmetic formulas consisting of n alternating blocks of bounded quantifiers starting with an existential quantifier, followed by a ...
6
votes
1answer
410 views

(Finite) Models of two subtheories of Peano Arithmetic

Consider first-order theory (with identity) of Peano Artithmetic built in the language $\{S,+,\times,0\}$ and with the following set of axioms: \begin{align} \neg Sx&=0\tag{1}\\\ ...
4
votes
0answers
342 views

How arithmetical is algebraic exponentiation?

Suppose $K$ is an exponential real closed field, i.e. there is an isomorphism, say exp, between the additive group of $K$ and the multiplicative group of its positive elements. Assume further that $Z$ ...
6
votes
4answers
684 views

Does there exist a non-trivial Ultrafinitist set theory?

Does there exist a set theory T-which has not yet been proved to be inconsistent-and in which one can prove the existence of (1) the empty set (2) sets that are singletons and (3) sets which have ...
9
votes
1answer
362 views

Beyond Presburger Arithmetic

Do there exist known examples of predicates $P$ (possibly functional) such that 1) $P$ admits a first-order definition in the language ${\Bbb N}(+,\times,0,1)$; 2) $P$ admits no definition that does ...
7
votes
2answers
428 views

Computing the measure of the projection on the torus of a semialgebraic set

Let $V \subseteq \mathbb{R}^n$ be a set cut out by a system of finitely many polynomial equations and inequalities with integer coefficients. Let $W$ be the set of all points in the box $[0,1]^n$ that ...
1
vote
1answer
325 views

Absoluteness of Countability

Let M be a countable transitive model for ZFC, P is a partial order in M. Notions like "partial orders" and "dense" are absolute. Consider the following set $S$={$D\in M: D$ is dense in $P$} = {$D: D$ ...
11
votes
1answer
368 views

Is ramification of number fields first order?

Fix a prime number $p$. Is there a first order sentence $\phi_p$ in the language of fields such that $\phi_p$ holds in a number field $K$ if and only if the prime $p$ is unramified in the field ...
1
vote
1answer
149 views

Is the closure of a semialgebraic set mod 1 also semialgebraic?

Let $p:\mathbb{R}^n\to[0,1)^n$ be the map defined by $p(x_1,\ldots,x_n)=(\{x_1\},\ldots,\{x_n\})$, where $\{\cdot\}$ is the fractional part operator. Experimentation suggests that if $S \subseteq ...
3
votes
1answer
212 views

Defining $\mathbb{Z}$ in $\prod_p \mathbb{F}_p(t)/\mathcal{U}$

Is it possible to show that there is a simple formula, preferably existential, that characterizes a nonstandard model of the ring of integers among the elements of $\prod_p ...
2
votes
1answer
336 views

Defining $\mathbb{Z}^*$ in $\prod_p \mathbb{F}_p/\mathcal{U}$ (or pseudo-finite fields)

Is it possible to show that there is a simple formula, preferably existential, that characterizes a nonstandard model of the ring of integers among the elements of $\prod_p \mathbb{F}_p/\mathcal{U}$? ...
26
votes
1answer
1k views

Do the algebraic integers form a free abelian group?

It is a well-known fact, proved in every introductory textbook on algebraic number theory, that if $K$ is an algebraic number field, i.e. a finite extension of $\mathbb{Q}$, then its ring ...
6
votes
0answers
415 views

Are advanced number-theoretic techniques related to undecidability?

Is there any evidence for or against the idea that some of the important statements of number theory that have only been proved using infinite sets, are in fact undecidable in Peano arithmetic? Most ...
16
votes
4answers
4k views

Can the Riemann hypothesis be undecidable?

The question is contained in the title; I mean the standard axioms ZFC. The wiki link: Riemann hypothesis. There are finite algorithms allowing one to decide if there are non-trivial zeroes of the ...
7
votes
3answers
1k views

Unprovable sentence about integers

Is there any natural* statement S about the natural integers such that if PA contains no contradictions then neither PA+S nor PA+not S contains a contradiction? If unknown, where can I read about the ...
6
votes
5answers
2k views

A meta-mathematical question related to Hilbert tenth problem

I am reading Bjorn Poonen's very nice survey on Hilbert's Tenth problem (http://www-math.mit.edu/~poonen/papers/uniform.pdf), and while I believe I understand the mathematics well, I have widespread ...
10
votes
2answers
1k views

Formalizing Euclid's proof of the infinitude of primes

Euclid's proof of the infinitude of primes requires me to take an arbitrary finite set of primes and multiply them together. If I want to formalize this proof in Peano Arithmetic, I need to know that ...
7
votes
1answer
411 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 ...
1
vote
2answers
387 views

Is anyone aware of a good exposition of the Gauss-Kramer model of Integers?

In the Princeton Companion of Mathematics, the Analytic Number Theory section, the author mentions what he calls Gauss-Kramer model, which is simply modeling the integers on a countable sequence of ...
25
votes
0answers
1k views

Peano Arithmetic and the Field of Rationals

In 1949 Julia Robinson showed the undecidability of the first order theory of the field of rationals by demonstrating that the set of natural numbers $\Bbb{N}$ is first order definable in $(\Bbb{Q}, ...
40
votes
14answers
4k views

What is the high-concept explanation on why real numbers are useful in number theory?

The utopian situation in mathematics would be that the statement and the proof of every result would live "in the same world", at the same level of mathematical complexity (in a broad sense), unless ...
22
votes
1answer
787 views

Concerning the rarity of provably transcendental real numbers

Does there exist any rubric where provably transcendental real numbers emerge, in a meaningful way, as rare among all the transcendental numbers? Here are some of the things I'm worried about: 1) To ...
12
votes
2answers
1k views

Induction, the infinitude of the primes, and workaday number theory

There are various open problems in the subject of logical number theory concerning the possibility of proving this or that well-known standard results over this or that weak theory of arithmetic, ...
5
votes
4answers
498 views

Logical equivalences for FTA

I hope this isn't a stupid question... It's well known that (in the presence of various other axioms), Euclid's Postulate 5 ('parallel axiom') is equivalent to the Pythagorean Theorem. That is, ...
15
votes
1answer
460 views

Real algebraic sets bounded away from integer points

A subset $S$ of $\mathbb{R}^n$ is "bounded away from integer points" if for some positive $\epsilon$ every point in $S$ lies at a distance of at least $\epsilon$ from $\mathbb{Z}^n$. For example the ...
19
votes
1answer
1k views

Nontrivial circular arguments?

There is a famous circular argument for the Prime Number Theorem (PNT). It turns out that there exists an infinite sequence of elementary-to-prove Chebyshev-type estimates that taken together imply ...
5
votes
1answer
333 views

Theory of addition and a predicate that recognizes powers of 2

What is the complexity of the theory of addition (Presburger arithmetic) augmented by a unary predicate that recognizes powers of 2?
13
votes
4answers
1k views

Fermat's Last Theorem and Computability Theory

This question stems from the paper "Computably categorical fields via Fermat's Last Theorem," by Russell Miller and Hans Schoutens (available online at http://qcpages.qc.cuny.edu/~rmiller/Fermat.pdf). ...
10
votes
0answers
615 views

Does Fermat hold in non-standard models?

Let $n \geq 3$ be a natural number and $PA$ denote Peano arithmetic. Do we have $PA \models \forall x,y,z \geq 1 : x^n + y^n \neq z^n$? In other words, does Fermat's Last Theorem hold also in ...
21
votes
4answers
5k views

Did Pogorzelski claim to have a proof of Goldbach's Conjecture?

In 1977, Henry Pogorzelski published what some believed was a claimed proof of Goldbach's Conjecture in Crelle's Journal (292, 1977, 1-12). His argument has not been accepted as a proof of Goldbach's ...
11
votes
2answers
716 views

Which recursively-defined predicates can be expressed in Presburger Arithmetic?

In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...
7
votes
3answers
1k views

Gödel's Incompleteness Theorem and the complexity of arithmetic

In How complicated can structures be? Jouko Väänänen says: The guiding result of mathematical logic is the Incompleteness Theorem of Gödel, which says that the logical structure of number theory ...
43
votes
5answers
4k views

Does anyone know a polynomial whose lack of roots can't be proved?

In Ebbinghaus-Flum-Thomas's Introduction to Mathematical Logic, the following assertion is made: If ZFC is consistent, then one can obtain a polynomial $P(x_1, ..., x_n)$ which has no roots in the ...
31
votes
5answers
3k views

Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?

1) Can the Riemann Hypothesis (RH) be expressed as a $\Pi_1$ sentence? More formally, 2) Is there a $\Pi_1$ sentence which is provably equivalent to RH in PA? (This is mentioned in P. ...
24
votes
3answers
2k views

Composite pairs of the form n!-1 and n!+1

It's well known that the numbers of the form $n!\pm1$ are not always prime. Indeed, Wilson's Theorem guarantees that $(p-2)!-1$ and $(p-1)!+1$ are composite for every prime number $p > 5$. Is ...