Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/AMS/Regular/BBBold.js
| 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.