| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

3. Decidability


    1. Add remark

      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?


        • Add remark

          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?


            • Add remark

              Problem 3.3.

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


                • Add remark

                  Problem 3.4.

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


                    • Add remark

                      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?


                        • Add remark

                          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.