The 2025 Winter Meeting of the Association for Symbolic Logic was held January 8-11, 2025, in conjunction with the annual Joint Mathematics Meeting. The program committee consisted of Artem Chernikov (chair), Natasha Dobrinen, and Joe Miller.

The ASL program included seven plenary speakers, a tutorial, a special session and a contributed paper session. The ASL Special Session Combinatorial Set Theory was organized by James Cummings and Spencer Unger. The two-part ASL Tutorial Tropical geometry, logarithmic limits and o-minimality was given by Sergei Starchenko. The plenary addresses at the meeting are listed below.

Maria-Florina Balcan (Carnegie Mellon), Machine learning theory: new challenges and connections.

Anton Bernshteyn (UCLA) Some recent progress in descriptive combinatorics.

Alexi Block Gorman (Université Gustave-Eiffel) Characterizing k-automatic expansions of Presburger arithmetic.

Theodore A. Slaman (Berkeley), Extending Borel’s conjecture from measure to dimension.

Daniel Turetsky (Victoria University, Wellington) True stages for computability and effective descriptive set theory.

Jinhe Ye (Oxford), Lang-Weil estimate in finite difference fields.

Andy Zucker (Waterloo), Topological dynamics and continuous logic.

Abstracts of the invited talks and the contributed talks by members of the Association for Symbolic Logic follow.

For the Program Committee

Artem Chernikov

Abstract of invited tutorial

▸SERGEI STARCHENKO, Tropical geometry, logarithmic limits and o-minimality.

Department of Mathematics, University of Notre Dame, Notre Dame, IN.

E-mail: sstarche@nd.edu.

Let $V\subseteq (\mathbb {C}^*)^n$ be an algebraic variety. For $t\in \mathbb {R}_{>0}$ , let $\mathcal {A}_t(V)\subseteq \mathbb {R}^n$ be the image of V under the logarithmic map $\operatorname {Log}_t\colon (\mathbb {C}^*)^n \to \mathbb {R}^n$ defined by

$$\begin{align*}\operatorname{Log}_t(z_1,\dotsc,z_n)= (\log_t(|z_1|,\dotsc,\log_t(z_n)). \end{align*}$$

Very often the set $\mathcal {A}_t(V)$ is called the tropical amoeba of V.

The limit set $\mathcal {A}_0(V)=\lim _{t\to \infty }$ was first studied extensively by Bergman [2] and Bieri and Groves [3]. It has been shown that these limit sets are rational polyhedra.

By a result of Einsiedler, Kapranov and Lind [5], these limit sets are also closely related to tropical varieties.

Later, many properties of logarithmic sets were extended to semi-algebraic sets by Alessandrini [1] and, independently, by Starchenko, Aschenbrenner and Lippel.

The main goal of this tutorial is to demonstrate that main properties of limit logarithmic sets follow from results of van den Dries and Lewenberg on tame pairs of o-minimal structures. [4].

We also consider logarithmic limits of semi-algebraic families and, in particular, answer a question of Alessandrini on semi-linearity of these limits.

[1] Alessandrini, Daniele, Logarithmic limit sets of real semi-algebraic sets, Advances in Geometry , vol. 13 (2013), no. 1, pp. 155–190.

[2] Bergman, George M., The logarithmic limit-set of an algebraic variety, Transactions of the American Mathematical Society , vol. 157 (1971), pp. 459–469.

[3] Bieri, Robert and Groves, John R.J., A rigidity property for the set of all characters induced by valuations, Transactions of the American Mathematical Society , vol. 294 (1986), no. 2, pp. 425–434.

[4] van den Dries, Lou and Lewenberg, Adam H, T-convexity and tame extensions, The Journal of Symbolic Logic , vol. 60 (1995), no. 1, pp. 74–102.

[5] Einsiedler, Manfred; Kapranov, Mikhai; and Lind, Douglas, Non-Archimedean amoebas and tropical varieties, Journal für die Reine und Angewandte Mathematik , vol. 601 (2006), pp. 139–157.

Abstracts of invited plenary lectures

▸MARIA-FLORINA BALCAN, Machine learning theory: new challenges and connections

School of Computer Science, Carnegie Mellon University, Pittsburgh, PA.

E-mail: ninamf@cs.cmu.edu.

In recent years, machine learning has been applied to increasingly complex settings rendering classic learning theoretic approaches insufficient for reasoning about their performance. In this talk I will discuss new frontiers of learning theory and its interplay with other fields for analyzing learning of more complex objects (algorithms rather than simple classifiers) and learning in challenging environments with strategic agents.

At the interface between machine learning and algorithm design, I will survey recent work on learning algorithms for solving problems that are hard in classic frameworks. The classic theory of computing framework considers hand-designed algorithms and focuses on worst-case guarantees. Since such hand-designed algorithms have weak worst-case guarantees for many problems, in practice machine learning components are often incorporated in algorithm design. In this talk, I will describe recent work in our group that provides theoretical foundations for such learning augmented algorithms. I will describe both specific case studies (from data science to operations research to computational biology) and general principles applicable broadly to a variety of combinatorial algorithmic problems. I will then show how we can loop back and use these tools to learn machine learning algorithms themselves!

I will also survey work that employs learning theory lenses to relax assumptions traditionally made in game theory, including learning utilities of agents from data and leveraging contextual feature information widely used in machine learning but often ignored in game theory.

▸ANTON BERNSHTEYN, Some recent progress in descriptive combinatorics.

Department of Mathematics, University of California, Los Angeles, CA, USA.

E-mail: bernshteyn@math.ucla.edu.

A common theme throughout mathematics is the search for “constructive” solutions as opposed to mere existence results. For problems on $\mathbb {R}$ and other well-behaved spaces, this idea is conveniently captured by the concept of a Borel construction. For example, one can seek Borel solutions to such combinatorial problems as graph coloring, perfect matching, etc. The area studying these questions is called descriptive combinatorics. Unfortunately, many classical facts in graph theory—for example, Brooks’ theorem—turn out to be inherently “non-constructive” in this sense. That being said, recent years have seen the emergence of geometric tools that make it possible to solve many combinatorial problems “constructively.” In this talk I will describe these tools, outline the general techniques for using them, and give a number of applications. Some of the results in this talk come from separate joint works with Abhishek Dhawan, Felix Weilacher, and Jing Yu.

▸ALEXI BLOCK GORMAN, JASON BELL, AND CHRIS SCHULZ, Characterizing k-automatic expansions of Presburger arithmetic

Laboratoire d’Informatique Gaspard Monge, Université Gustave Eiffel, France.

E-mail: blockgorman.1@osu.edu.

Department of Pure Mathematics, University of Waterloo, Canada.

Department of Pure Mathematics, University of Waterloo, Canada.

There are compelling and long-established connections between automata theory and model theory, particularly regarding expansions of Presburger arithmetic by sets whose base-k representations are recognized by an automaton. We call such sets “k-automatic,” and in this talk we will discuss recent results and ongoing work toward a complete characterization of all expansions of Presburger arithmetic in which all definable sets are k-automatic. We will characterize such expansions both in terms of model-theoretic properties, and via notions of density coming from arithmetic geometry. This talk is based on joint work with Jason Bell and Chris Schulz.

▸THEODORE A. SLAMAN, Extending Borel’s conjecture from measure to dimension

Department of Mathematics, University of California Berkeley, 719 Evans Hall #3840, Berkeley, CA 94720-3840 USA.

E-mail: slaman@math.berkeley.edu.

Borel (1919) defined a set of real numbers A to have strong measure zero if for every sequence of positive numbers $(\epsilon _i: i \in \omega )$ there is an open cover of A, $(U_i: i \in \omega )$ , such that for each i, the diameter of $U_i$ is less than $\epsilon _i.$ Besicovitch (1956) showed that A has strong measure zero if and only if A has strong dimension zero, which means that for every gauge function f, A is null for its associated measure $H^f$ . We say that a subset of A of $R^n$ has strong dimension f if and only if $H^f(A)>0$ and for every gauge function g of higher order $H^g(A)=0.$ Here, g has higher order than f when $\lim _{t \to 0^+} g(t)/f(t)=0.$

Borel conjectured that a set of strong measure zero must be countable. This conjecture naturally extends to the assertion that a set has strong dimension f if and only if it is $\sigma $ -finite for $H^f\kern-1.2pt $ . Sierpinski (1928) used the continuum hypothesis to give a counterexample to Borel’s conjecture and Besicovitch (1963) did the same for its generalization. Laver (1976) showed that Borel’s conjecture is relatively consistent with ZFC, the conventional axioms of set theory including the axiom of choice. We will discuss the proof that its generalization to strong dimension is also relatively consistent with ZFC.

▸DANIEL TURETSKY, True stages for computability and effective descriptive set theory

School of Mathematics and Statistics, Victoria University of Wellington, Wellington, New Zealand.

E-mail: dan.turetsky@vuw.ac.nz.

Priority arguments are hard. The true stages machinery was conceived as a technique for organizing complex priority constructions in computability theory, much like Ash’s metatheorem. With a little modification, however, it can prove remarkably useful in descriptive set theory. Using this machinery, we can obtain nice proofs of results of Wadge, Hausdorff and Kuratowski, and Louveau, sometimes strengthening the result in the process. I will give the ideas behind the machinery and some examples of how it applies to both computability theory and descriptive set theory.

▸JINHE YE, Lang-Weil estimate in finite difference fields

Mathematical Institute, University of Oxford, Oxford, UK.

E-mail: jinhe.ye@maths.ox.ac.uk.

A difference field is a field equipped with a given automorphism and a difference variety is the natural analogue of an algebraic varieties in this setting. Complex numbers with complex conjugation or finite fields with the Frobenius automorphism are natural examples of difference fields.

For finite fields and varieties over them, the celebrated Lang-Weil estimate gives a universal estimate of number of rational points of varieties over finite fields in terms of several notions of the complexities of the given variety. In this talk, we will discuss an analogue to Lang-Weil estimate for difference varieties in finite difference fields. The proof uses pseudofinite difference fields, where the automorphism is the nonstandard Frobenius. This is joint work with Martin Hils, Ehud Hrushovski and Tingxiang Zou.

▸ANDY ZUCKER, Topological dynamics and continuous logic

Department of Pure Mathematics, University of Waterloo, Waterloo, Canada.

E-mail: a3zucker@uwaterloo.ca.

Motivated by the recent construction of the author of a notion of ultracoproduct of flows of topological groups [2] and by recent work of Ben Yaacov and Goldbring which offers a formalization of unitary representations of locally compact groups in the language of continuous logic [1], we present some of the key ideas needed for such a formalization for flows of topological groups. A crucial addition is the need to add several sorts onto the algebra of continuous functions of the flow which serve as “external declarations” of moduli of G-continuity, obtaining a richer structure that we call a graded G-flow. Working with graded G-flows, the theory of ultracoproducts and weak containment dramatically simplifies, while also shedding light on why things are so much more difficult in the “ungraded” setting.

[1] I. Ben Yaacov and I. Goldbring, Unitary representations of locally compact groups as metric structures, Notre Dame Journal of Formal Logic , vol. 64 (2023), no. 2, pp. 159–172.

[2] A. Zucker, Ultracoproducts and weak containment for flows of topological groups, arXiv:2401.08000.

Abstracts of contributed talks

▸ANG LI, Countable ordered groups and Weihrauch reducibility

Department of Mathematics, University of Wisconsin–Madison, 480 Lincoln Drive, USA.

E-mail: ali233@wisc.edu.

This paper continues to study the connection between reverse mathematics and Weihrauch reducibility. In particular, we study the problems formed from Maltsev’s theorem [1] on the order types of countable ordered groups. Solomon [2] showed that the theorem is equivalent to $\mathsf {\Pi _1^1}$ - $\mathsf {CA_0}$ , the strongest of the big five subsystems of second order arithmetic. We show that the strength of the theorem comes from having a dense linear order without endpoints in its order type. Then, we show that for the related Weihrauch problem to be strong enough to be equivalent to $\mathsf {\widehat {WF}}$ (the analog problem of $\mathsf {\Pi _1^1}$ - $\mathsf {CA_0}$ ), an order-preserving function is necessary in the output. Without the order-preserving function, the problems are very much to the side compared to analog problems of the big five.

[1] Anatoly Mal’tsev, On ordered groups, Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya , vol. 13 (1949), no. 6, pp. 473–482.

[2] Reed Solomon, $\mathsf {\Pi _1^1}$ - $\mathsf {CA_0}$ and Order Types of Countable Ordered Groups, The Journal of Symbolic Logic , vol. 66 (2001), no. 1, pp. 192–206.

▸ERMEK NURKHAIDAROV AND EREZ SHOCHAT, The automorphism groups of countable short recursively saturated models of Peano Arithmetic

Department of Mathematics, Pennsylvania State University, Mont Alto, 1 Campus dr., PA 17237, USA.

E-mail: esn1@psu.edu.

Department of Mathematics, St. Francis College, 179 Livingston Street, Brooklyn, NY 11201, USA.

E-mail: eshochat@sfc.edu.

Let M be a countable recursively saturated model of $\mathrm {PA}$ . For $a\in M$ , let $M(a)$ be the largest elementary cut containing a. It is known that such submodel is a countable short recursively saturated model of $\mathrm {PA}$ . In this talk we discuss the properties of countable short recursively saturated models of $\mathrm {PA}$ and their automorphism groups.

We use results from and [1] and [4], to show that the set of initial segments of $M(a)$ which are fixed setwise by all automorphisms of the model, depends on the types realized in the last gap of the model. We then expand on results from [4] to show that there are additional countable recursively saturated models of $\mathrm {PA}$ whose automorphism groups are not isomorphic as topological groups.

Finally, by modifying the results from [2] and [3], we discuss instances where two different countable short arithmetically saturated models of $\mathrm {PA}$ have non-isomorphic automorphism groups, as topological groups. In particular, we show that if $(\omega ,\mathrm {Rep}(\mathrm {Th}(M(a)))) \models \mathrm {RT}^3_2$ then $\mathrm {SSy}(M(a))$ is coded in $\mathrm {Aut}(M(a))$ .

[1] R. Kossak, H. Kotlarski, and J.H. Schmerl, On maximal subgroups of the automorphism group of a countable recursively saturated model of PA, Annals of Pure and Applied Logic , vol. 65 (1993), pp. 125–148.

[2] R. Kossak and J.H. Schmerl, The automorphism group of an arithmetically saturated model of Peano Arithmetic, Journal of the London Mathematical Society , vol. 52 (1995), pp. 235-244.

[3] E. Nurkhaidarov, Automorphism groups of arithmetically saturated models, The Journal of Symbolic Logic , vol. 71 (2006), pp. 203–216.

[4] E. Shochat, A Galois correspondence for countable short recursively saturated models of PA, Mathematical Logic Quarterly , vol. 56 (2010), no. 3, pp. 228–238.

▸DIEGO A. ROJAS, Almost-everywhere convergence theorems in harmonic analysis and algorithmic randomness

Department of Mathematics and Statistics, Sam Houston State University, 1900 Avenue I, Huntsville, TX 77340, United States.

E-mail: dar117@shsu.edu.

Since the turn of the millennium, there has been an ongoing program to use almost-everywhere theorems in analysis and ergodic theory to study algorithmic randomness [2]. In harmonic analysis, Franklin, McNicholl, and Rute [1] characterized Schnorr randomness in terms of an effective version of Carleson’s Theorem. To this end, we analyze Martin-Löf randomness and Schnorr randomness in terms of convergence of Fourier series and convergence of radial limits of Poisson integrals, respectively. This is joint work with Johanna N.Y. Franklin and Lucas E. Rodriguez.

[1] Johanna N.Y. Franklin, Timothy H. McNicholl, and Jason Rute, Algorithmic randomness and Fourier analysis, Theory of Computing Systems , vol. 63 (2019), pp. 567–586.

[2] Kenshi Miyabe, André Nies, and Jing Zhang, Using almost-everywhere convergence theorems from analysis to study randomness, Bulletin of Symbolic Logic , vol. 22 (2016), no. 3, pp. 305–331.