Alternating state complexity of the set of primes and squarefree integers

2023/07/21 by Schlage-Puchta, Jan-Christoph
#11N36 #68Q45 #FOS: Mathematics #Logic (math.LO) #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2307.11745

Abstract

We show that the set of prime numbers has exponential alternating complexity, proving a conjecture by Fijalkow. We further show that the set of squarefree integers has essentially maximal possible alternating complexity.

Related

• Lower bounds for the state complexity of probabilistic languages and the language of prime numbers
• Lower Bounds for Alternating Online State Complexity
• Sharpening "Primes is in P" for a large family of numbers
• Obstructions to uniformity, and arithmetic patterns in the primes
• Squarefree smooth numbers and Euclidean prime generators