On April 18, 2024 at 14:00 EEST, Mihai Prunescu (University of Bucharest and IMAR) will give a talk in the Logic Seminar.
Title: On representability by arithmetic terms
Abstract:
Consider number-theoretic functions like \(\tau\), which represents the number of divisors of a natural number, \(\sigma\), which yields the sum of its divisors, or Euler’s totient function \(\varphi\), which computes, for any \(n\), the number of residues modulo \(n\), which are relatively prime to \(n\). There are methods to compute these functions for a given argument \(n\) from the prime number decomposition of \(n\), but it is difficult to imagine arithmetic closed terms in \(n\) alone, computing them. Yet, those functions are Kalmár-elementary and by the results of Mazzanti and Marchenkov, such terms do exist. As well, closed arithmetic terms represent the \(n\)th prime and various other number-theoretical functions. I will show how such terms can be effectively constructed. Work in progress.
The talk will take place physically at FMI (Academiei 14), Hall 214 “Google”.