
## 3. Decidability

1. #### Problem 3.1.

[Chris Hall, Alexandra Shlapentokh] Given an elliptic curve $E$ given by $y^2 = x^3 + Ax + B$:
1. Is there are algorithm that decides if $E(\mathbb Z) \setminus\{\infty\}$ is empty?
2. Is there an algorithm for enumerating $E(\mathbb Z)$?
3. Can these questions be answered if $E$ is replaced with an arbitrary curve?
• #### Problem 3.2.

1. Is the first order theory of $\mathbb C(t)$ decidable in signature with $1$ and $t$?
2. Does it help if $\frac{\partial}{\partial t_i}$ is added to the signature?
• #### Problem 3.3.

Is the existential theory of $\{\text{complex holomorphic functions over$\mathbb C$}\}$ in signature $0,1,+,\cdot, z$ decidable?
• #### Problem 3.4.

[Arno Fehm] Is $\exists \text{Th}(\mathbb F_p(t))$, in the language of rings without a name for $t$, decidable?
• #### Problem 3.5.

[Thanasis Pheidas] Let $p$ be a fixed prime. Define $$x \mid_p y \Leftrightarrow \exists s\in \mathbb N, y = p^sx$$ Does $(\mathbb Z, +, \mid_p, 0, 1)$ have a decidable existential theory?
• #### Problem 3.6.

[Arno Fehm] Which fragments of $\text{Th}(\mathbb Q)$ are undecidable? Consider the number of quantifiers, not just alternations.

Cite this as: AimPL: Definability and decidability problems in number theory, available at http://aimpl.org/definedecide.