Department of

March 2021 April 2021May 2021Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr SaSuMo Tu We Th Fr Sa 1 2 3 4 5 6 1 2 3 1 7 8 9 10 11 12 13 4 5 6 7 8 9 10 2 3 4 5 6 7 8 14 15 16 17 18 19 20 11 12 13 14 15 16 17 9 10 11 12 13 14 15 21 22 23 24 25 26 27 18 19 20 21 22 23 241617 18 19 20 21 22 28 29 30 31 25 26 27 28 29 30 23 24 25 26 27 28 29 30 31

Tuesday, April 27, 2021

**Abstract:** Since 1929, when Presburger formalized his eponymous arithmetic $(\mathbb{Z}, <, +)$—integers with order and addition, but not multiplication—various extensions of this theory have been studied. Presburger arithmetic (PA) is decidable, as are some of its extensions, such as that by base-2 exponentiation. In joint work with Philipp Hieronymi, we extend PA by the sine function. Let sine-Presburger arithmetic ($\sin$-PA) be the theory of $(\mathbb{R}, <, +, \mathbb{Z}, \sin)$ with quantification only over integers. We show that the $\sin$-PA fragment with 4 alternating quantifier blocks is undecidable by encoding the halting problem. On the other hand, we present a decision procedure for the existential fragment of $\sin$-PA, under assumption of Schanuel’s Conjecture from transcendental number theory.