More Like this

1. Counting mod n in pseudofinite fields

   https://doi.org/10.1007/s11856-021-2279-x  

   Johnson, Will (January 2021, Israel Journal of Mathematics)

   We show that in an ultraproduct of finite fields, the mod-n nonstandard size of definable sets varies definably in families. Moreover, if K is any pseudofinite field, then one can assign "nonstandard sizes mod n" to definable sets in K. As n varies, these nonstandard sizes assemble into a definable strong Euler characteristic on K, taking values in the profinite completion hat(Z) of the integers. The strong Euler characteristic is not canonical, but depends on the choice of a nonstandard Frobenius. When Abs(K) is finite, the Euler characteristic has some funny properties for two choices of the nonstandard Frobenius. Additionally, we show that the theory of finite fields remains decidable when first-order logic is expanded with parity quantifiers. However, the proof depends on a computational algebraic geometry statement whose proof is deferred to a later paper. 

   more » « less
2. The local sum conjecture in two dimensions

   https://doi.org/10.1142/S1793042120500888  

   Fraser, Robert; Wright, James (September 2020, International Journal of Number Theory)

   The local sum conjecture is a variant of some of Igusa’s questions on exponential sums put forward by Denef and Sperber. In a remarkable paper by Cluckers, Mustata and Nguyen, this conjecture has been established in all dimensions, using sophisticated, powerful techniques from a research area blending algebraic geometry with ideas from logic. The purpose of this paper is to give an elementary proof of this conjecture in two dimensions which follows Varčenko’s treatment of Euclidean oscillatory integrals based on Newton polyhedra for good coordinate choices. Another elementary proof is given by Veys from an algebraic geometric perspective. 

   more » « less
3. Beyond NP: Quantifying over Answer Sets

   https://doi.org/10.1017/S1471068419000140  

   AMENDOLA, GIOVANNI; RICCA, FRANCESCO; TRUSZCZYNSKI, MIROSLAW (September 2019, Theory and Practice of Logic Programming)

   Abstract Answer Set Programming (ASP) is a logic programming paradigm featuring a purely declarative language with comparatively high modeling capabilities. Indeed, ASP can model problems in NP in a compact and elegant way. However, modeling problems beyond NP with ASP is known to be complicated, on the one hand, and limited to problems in $$\[\Sigma _2^P\]$$ on the other. Inspired by the way Quantified Boolean Formulas extend SAT formulas to model problems beyond NP, we propose an extension of ASP that introduces quantifiers over stable models of programs. We name the new language ASP with Quantifiers (ASP(Q)). In the paper we identify computational properties of ASP(Q); we highlight its modeling capabilities by reporting natural encodings of several complex problems with applications in artificial intelligence and number theory; and we compare ASP(Q) with related languages. Arguably, ASP(Q) allows one to model problems in the Polynomial Hierarchy in a direct way, providing an elegant expansion of ASP beyond the class NP. 

   more » « less
4. A Logic for Expressing Log-Precision Transformers

   Merrill, William; Sabharwal, Ashish (December 2023, NeurIPS 2023)

   One way to interpret the reasoning power of transformer-based language models is to describe the types of logical rules they can resolve over some input text. Recently, Chiang et al. (2023) showed that finite-precision transformers can be equivalently expressed in a generalization of first-order logic. However, finite-precision transformers are a weak transformer variant because, as we show, a single head can only attend to a constant number of tokens and, in particular, cannot represent uniform attention. Since attending broadly is a core capability for transformers, we ask whether a minimally more expressive model that can attend universally can also be characterized in logic. To this end, we analyze transformers whose forward pass is computed in logn precision on contexts of length n. We prove that any log-precision transformer can be equivalently expressed as a first-order logic sentence that, in addition to standard universal and existential quantifiers, may also contain majority-vote quantifiers. This is the tightest known upper bound and first logical characterization of log-precision transformers. 

   more » « less
5. WHICH CLASSES OF STRUCTURES ARE BOTH PSEUDO-ELEMENTARY AND DEFINABLE BY AN INFINITARY SENTENCE?

   https://doi.org/10.1017/bsl.2023.1  

   BONEY, WILL; CSIMA, BARBARA F.; DAY, NANCY A.; HARRISON-TRAINOR, MATTHEW (March 2023, The Bulletin of Symbolic Logic)

   Abstract When classes of structures are not first-order definable, we might still try to find a nice description. There are two common ways for doing this. One is to expand the language, leading to notions of pseudo-elementary classes, and the other is to allow infinite conjuncts and disjuncts. In this paper we examine the intersection. Namely, we address the question: Which classes of structures are both pseudo-elementary and $${\mathcal {L}}_{\omega _1, \omega }$$ -elementary? We find that these are exactly the classes that can be defined by an infinitary formula that has no infinitary disjunctions. 

   more » « less