Logic Blog 2023-24

Editor: André Nies · 2025

Read Logic Blog 2023-24 by Editor: André Nies (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-12673.txt.

Introduction

Andre Nies edited the joined Logic Blog for 2023 and 2024, published as one file in 2025. Much of the blog treats particular classes of groups and how they relate to logic. Other entries take up ergodic theory and questions in foundations, and a short part near the end turns to AI proving. The file joins the two yearly blogs into a single record, so readers get both years of short research notes in one place.

Catalog record

CREATOREditor: André Nies
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE110 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-12673

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Logic Blog 2023-24 Editor: André Nies Abstract Note: the 2023 and 2024 Logic Blogs have been joined. The Logic Blog is a shared platform for • rapidly announcing results and questions related to logic • putting up results and their proofs for further research • parking results for later use • getting feedback before submission to a journal • fostering collaboration. Each year’s blog is posted on arXiv 2-3 months after the year has ended. Logic Blog 2022 (Link: http://arxiv.org/pdf/2302.11853.pdf ) Logic Blog 2021 (Link: http://arxiv.org/abs/2202.13643 ) Logic Blog 2020 (Link: http://arxiv.org/abs/2101.09508 ) Logic Blog 2019 (Link: http://arxiv.org/abs/2003.03361 ) Logic Blog 2018 (Link: http://arxiv.org/abs/1902.08725 ) Logic Blog 2017 (Link: http://arxiv.org/abs/1804.05331 ) Logic Blog 2016 (Link: http://arxiv.org/abs/1703.01573 ) Logic Blog 2015 (Link: http://arxiv.org/abs/1602.04432 ) Logic Blog 2014 (Link: http://arxiv.org/abs/1504.08163 ) Logic Blog 2013 (Link: http://arxiv.org/abs/1403.5719 ) Logic Blog 2012 (Link: http://arxiv.org/abs/1302.3686 ) Logic Blog 2011 (Link: http://arxiv.org/abs/1403.5721 ) Logic Blog 2010 (Link: http://dx.doi.org/2292/9821 ) How does the Logic Blog work? Writing and editing. The source files are in a shared dropbox. Ask André () in order to gain access. Citing. Postings can be cited. An example of a citation is: H. Towsner, Computability of Ergodic Convergence . In André Nies (editor), Logic Blog, 2012, Part 1, Section 1, available at http://arxiv.org/abs/1302.3686 . The logic blog, once it is on arXiv, produces citations e.g. on Google Scholar. Part I Group theory and its connections to logic 1. Algorithmic questions around the Tits alternative The 2023 NZRMI summer school took place in Nelson, New Zealand. It was organized by Jeroen Schillewaert and Matthew Conder, both based in Auckland. NZMRI means “ New Zealand Mathematical Research Institute ”. There were six three-hour tutorials, by Emmanuel Breuillard (Oxford), Martin Bridson (Oxford), Benson Farb (U. Chicago), Nicolas Monod (EPFL), Anne Thomas (U. Sydney), and Amie Wilkinson (U. Chicago). Here, Andre Nies will discuss some aspects of Breuillard’s lectures. They started out from the Tits alternative. Theorem 1.1 (Tits, 1972) . Let K be a field, and let \Gamma\leq\GL_{d}(K) be finitely generated. Then either \Gamma contains a non-abelian free subgroup, or \Gamma has a solvable subgroup of finite index (i.e., \Gamma is virtually solvable). This result implies that every f.g. torsion linear group is finite, because this is the case for solvable groups as proved easily by induction on the solvability rank. Breuillard in 2008 obtained a strong Tits alternative : given d there is N(d)\in{\mathbb{N}} such that for each field K and each finite subset S of \GL_{d}(K) closed under inversion, either \langle S\rangle is virtually solvable, or S^{N(d)} contains elements a,b generating a free non-abelian subgroup. Breuillard mentioned the following open problem, which essentially asks whether one can decide which side of the Tits alternative holds. Question 1.2 . Given a field K and d\geq 3 , is there an algorithm to decide whether non-commuting matrices A,B\in\GL_{d}(K) generate a free group? The question appears to be open even for K={\mathbb{Q}} . This question can be interpreted literally if K is a computable field. It is a bit harder to make sense of it for K=\mathbb{C} , the main case of interest. In line with computable analysis, the answer will have to be computed from approximations to A,B , such as matrices with entries that are in {\mathbb{Q}}(i) . 1.1. Torsion in \GL_{d}(K) Here is a potentially simpler question: Is there an algorithm to decide whether A\in\GL_{d}(K) is a torsion element? For algebraic number fields, the paper Deciding finiteness of matrix groups by Babai, Beals, Rockmore in ISSAC 93 provides an algorithm that decides the question in polynomial time, and contains another algorithm that does it in Monte Carlo polynomial time with a more practical exponent. Let \chi_{A} denote the characteristic polynomial \chi_{A}(t)=\det(A-tI) . Let \Phi_{k}\in{\mathbb{Z}}[X] be the k -th cyclotomic polynomial. Thus, \Phi_{k} is the minimal polynomial over {\mathbb{Q}} of a primitive k -th root of unity (such as \exp(2\pi i/k) ) and has degree \varphi(k) , where \phi is the Euler totient function. The following is known. Fact 1.3 . A\in\GL_{d}({\mathbb{C}}) is torsion \Leftrightarrow \chi_{A} is a product of cyclotomic polynomials \Phi_{k} , where necessarily \varphi(k)\leq d . Since one can compute \Phi_{k} , and \sqrt{k/2}\leq\varphi(k) for each k\geq 1 , this gives the desired algorithm when the coefficients of A are taken from some computable field K that is a subfield of {\mathbb{C}} (i.e., K is computable and has characteristics 0 ): on input A\in\GL_{d}(K) , 1. compute \chi_{A} . 2. see if it can be written as a product of \Phi_{k} ’s where k\leq 2d^{2} . If so answer yes. Note that this also gives a crude upper bound on the torsion as a function of d , something like 2^{d}\cdot(d^{2d}) . Knowing that, as an algorithm to determine whether A is torsion, we can try the various exponents up to this bound. Note that this is far from efficient. Is there a better bound on the torsion? This 1997 paper by Shmuel Friedland shows that up to conjugation, the group O(d) of orthogonal d\times d matrices over the integers is the maximal finite subgroup of GL_{d}({\mathbb{Q}}) , for large d. Also, its order 2^{d}d! is the maximal order of a finite subgroup, with the exception of d=2,4,6,7,8,9,10 . In the exceptional cases, the maximum has been obtained by Feit, based on Weisfeiler’s tight estimate for the Jordan function, in a preprint called “The orders of finite linear groups”, 1995, which has not appeared. See these 2006 notes by Serre , where the work of Weisfeiler-Feit is called “incomplete”. If it works, then for d=3,5 or d>10 , the maximum order is 2L(d) , where L(d) is the maximum order of an element of the symmetric group S_{d} . (This follows because O(d)\cong C_{2}^{d}\rtimes S(d) .) For the value of L(d) , see this paper by William Miller . It surveys= a proof that \log L(d)\sim\sqrt{d\log d} , where \log is the natural logarithm. Very roughly, this says that L(d) is the square root of the size of S(d) , which is about \exp{(d\log d)} . 2. Khelif,Wilson: On ultraproducts of alternating groups Gabriel Sabbagh asked whether an infinite pseudo-finite group can be finitely generated. For some background see [ 8 , Section 6] . This section is based on notes by Anatole Khelif related to this problem. John Wilson and Nies discussed these by email. The full explication below is due to Wilson. Note that pseudofinite groups are precisely the groups elementarily equivalent to an ultraproduct of finite groups. The main result is: Theorem 2.1 . No infinite finitely generated group is elementarily equivalent to an ultraproduct of a family of finite alternating groups. To prove this, we require two lemmata. For the definition and properties of bi-interpretability we refer the reader to [ 13 , p. 222] . We write P_{n} for the power set of the set \{1,\dots,n\} . Lemma 2.2 . For n\geq 9 , the alternating group A_{n} and the three-sorted structure (A_{n},\{1\dots,n\},P_{n}) , with the group operations on A_{n} , the action of A_{n} on \{1\dots,n\} , the element relation between \{1\dots,n\} and sets in P_{n} and the Boolean algebra operations on P_{n} , are bi-interpretable, in a uniformly way, without parameters. Proof. It suffices to

Read the complete text