Halting problem in number theory

[José Manuel Rodríguez Caballero]

Dear FOM members,
  Yuri Matiyasevich [1] reduced Riemann's hypothesis to the statement that
a certain program (written in the Python programming language) never halts.
I would like to share another halting problem originated in number theory
[3]. Also, this problem belongs to the so-called theory of the distribution
of divisors [4]. I would like to ask if there is a string s of well-matched
parentheses, so that it cannot be determined if the function
arithmetic_halting(s) halts. In the Python programming language, this
function is defined as follows.

from sympy import divisors

def parentheses(n):
    P = set(divisors(n))
    R = sorted(P.symmetric_difference({2*d for d in P}))
    return ''.join('(' if x%2==1 else ')' for x in R)

def arithmetic_halting(s):
    n = 1
    while True:
        if parentheses(n) == s:
            return n
        n += 1

The function parentheses(n) takes a positive integer n and returns a word
consisting of parentheses. This word is obtained as follows. Take the
symmetric difference between the set of divisors of n and this set where
each element is multiplied by 2. Write the result in increasing order. For
any odd number in the list, type an opening parenthesis, for any even
number, type a closing parenthesis. The fact that this word is well-matched
was proved in [2].

For example, take n = 12. The divisors of 12 are 1, 2, 4, 6, 12. Twice
these divisors: 2, 4, 8, 12, 24. The symmetric difference is 1, 6, 8, 12.
Hence, the parentheses are ( ( ) ).

The function arithmetic_halting(s) takes a word consisting of well-matched
parentheses s and return the smallest positive integer n satisfying
parentheses(n)
= s, if this number exists, otherwise it does not halt.

My approach would be to try to prove that the function arithmetic_halting(s),
when s is restricted to well is rich enough to encode any computation. If
this is the case, it cannot be total. I am not aware of similar problems in
the literature.

Kind regards,
Jose M.


[1] Matiyasevich, Yu. "The Riemann hypothesis in computer science."
*Theoretical
Computer Science* 807 (2020): 257-265. URL =
https://www.sciencedirect.com/science/article/abs/pii/S0304397519304633

[2] Caballero, José Manuel Rodríguez. "Symmetric Dyck Paths and Hooley’s
Delta-Function." *International Conference on Combinatorics on Words*.
Springer, Cham, 2017. URL =
https://link.springer.com/chapter/10.1007/978-3-319-66396-8_23

[3] Caballero, José Manuel Rodríguez. "Jordan's Expansion of the Reciprocal
of Theta Functions and 2-densely Divisible Numbers." *Integers* 20 (2020):
A2. URL = http://math.colgate.edu/~integers/u2/u2.pdf

[4] Hall, Richard Roxby, and Gérald Tenenbaum. *Divisors*. Cambridge
University Press, 1988.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20211206/eb6619ce/attachment.html>