# Tagged Questions

238 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 ...
162 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, ...
222 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 ...
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 ...
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 ...
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 ...
669 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?
681 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 ...
833 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 ...
424 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 (= ...
801 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 ...
393 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 ...
653 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 ...
365 views

213 views

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 ...
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 ...
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, ...
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, ...
463 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 ...
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 ...
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?
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). ...
619 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 ...
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 ...
722 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 ...
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 ...
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 ...
### 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. ...
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 ...