# Tagged Questions

**1**

vote

**2**answers

237 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

**1**answer

161 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

**1**answer

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 ...

**10**

votes

**1**answer

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

**4**answers

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

**2**answers

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

**1**answer

668 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

**1**answer

680 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

**5**answers

827 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

**1**answer

418 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

**1**answer

799 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

**2**answers

392 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

**2**answers

640 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

**1**answer

365 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

**1**answer

257 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

**0**answers

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

**1**answer

413 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

**0**answers

345 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

**4**answers

688 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

**1**answer

365 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

**2**answers

429 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

**1**answer

331 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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

417 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

**4**answers

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

**3**answers

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

**5**answers

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

**2**answers

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

**1**answer

412 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

**2**answers

389 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

**0**answers

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

**14**answers

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

**1**answer

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

**2**answers

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

**4**answers

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

**1**answer

462 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

**1**answer

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

**1**answer

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

**4**answers

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

**0**answers

618 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

**4**answers

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

**2**answers

720 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

**3**answers

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

**5**answers

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 ...

**32**

votes

**5**answers

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

**3**answers

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 ...