More Like this

1. Generically computable Abelian groups

   https://doi.org/10.1007/978-3-031-34034-5_3  

   Calvert, W.; Cenzer, D.; Harizanov, V. (June 2023, Unconventional Computation and Natural Computation)

   Genova, D.; Kari, J. (Ed.)

   Generically computable sets, as introduced by Jockusch and Schupp, have been of great interest in recent years. This idea of approximate computability was motivated by asymptotic density problems studied by Gromov in combinatorial group theory. More recently, we have defined notions of generically computable structures, and studied in particular equivalence structures and injection structures. A structure is said to be generically computable if there is a c.e. substructure defined on an asymptotically dense set, where the functions are computable and the relations are computably enumerable. It turned out that every equivalence structure has a generically computable copy, whereas there is a non-trivial characterization of the injection structures with generically computable copies. In this paper, we return to group theory, as we explore the generic computability of Abelian groups. We show that any Abelian p-group has a generically computable copy and that such a group has a Σ2-generically computably enumerable copy if and only it has a computable copy. We also give a partial characterization of the Σ1-generically computably enumerable Abelian p-groups. We also give a non-trivial characterization of the generically computable Abelian groups that are not p-groups. 

   more » « less
2. On computable aspects of algebraic and definable closure

   https://doi.org/10.1093/logcom/exaa070  

   Ackerman, Nathanael; Freer, Cameron; Patel, Rehana (December 2020, Journal of Logic and Computation)

   null (Ed.)

   Abstract We investigate the computability of algebraic closure and definable closure with respect to a collection of formulas. We show that for a computable collection of formulas of quantifier rank at most $$n$$, in any given computable structure, both algebraic and definable closure with respect to that collection are $$\varSigma ^0_{n+2}$$ sets. We further show that these bounds are tight. 

   more » « less
3. Computability of topological pressure on compact shift spaces beyond finite type*

   https://doi.org/10.1088/1361-6544/ac7702  

   Burr, Michael; Das, Suddhasattwa; Wolf, Christian; Yang, Yun (June 2022, Nonlinearity)

   We investigate the computability (in the sense of computable analysis) of the topological pressure P_top(ϕ) on compact shift spaces X for continuous potentials ϕ:X→R. This question has recently been studied for subshifts of finite type (SFTs) and their factors (sofic shifts). We develop a framework to address the computability of the topological pressure on general shift spaces and apply this framework to coded shifts. In particular, we prove the computability of the topological pressure for all continuous potentials on S-gap shifts, generalised gap shifts, and particular beta-shifts. We also construct shift spaces which, depending on the potential, exhibit computability and non-computability of the topological pressure. We further prove that the generalised pressure function (X,ϕ) ↦P_top(X,ϕ|_X) is not computable for a large set of shift spaces X and potentials ϕ . In particular, the entropy map X↦h_top(X) is computable at a shift spaceXif and only if X has zero topological entropy. Along the way of developing these computability results, we derive several ergodic-theoretical properties of coded shifts which are of independent interest beyond the realm of computability. 

   more » « less
4. The Galois‐equivariant K‐theory of finite fields

   https://doi.org/10.1112/plms.70012  

   Chan, David; Vogeli, Chase (December 2024, Proceedings of the London Mathematical Society)

   We compute the RO(G)‐graded equivariant algebraic K‐groups of a finite field with an action by its Galois group G. Specifically, we show these K‐groups split as the sum of an explicitly computable term and the well‐studied RO(G)‐graded coefficient groups of the equivariant Eilenberg–MacLane spectrum HZ. Our comparison between the equivariant K‐theory spectrum and HZ further shows they share the same Tate spectra and geometric fixed point spectra. In the case where G has prime order, we provide an explicit presentation of the equivariant K‐groups. 

   more » « less
5. Generically computable linear orderings

   https://doi.org/10.1016/j.apal.2025.103612  

   Calvert, Wesley; Cenzer, Douglas; Gonzalez, David; Harizanov, Valentina (May 2025, Annals of Pure and Applied Logic)

   We study notions of generic and coarse computability in the context of computable structure theory. Our notions are stratified by the Σβ hierarchy. We focus on linear orderings. We show that at the Σ1 level, all linear orderings have both generically and coarsely computable copies. This behavior changes abruptly at higher levels; we show that at the Σα+2 level for any α ∈ ωCK 1 the set of linear orderings with generically or coarsely computable copies is Σ1 1-complete and therefore maximally complicated. This development is new even in the general analysis of generic and coarse computability of countable structures. In the process of proving these results, we introduce new tools for understanding generically and coarsely computable structures. We are able to give a purely structural statement that is equivalent to having a generically computable copy and show that every relational structure with only finitely many relations has coarsely and generically computable copies at the lowest level of the hierarchy. 

   more » « less