Publications

Here is a list of articles that I (co)-wrote, sorted by either publication or submission year. Papers are either preprints , or published in conference proceedings or journals . The articles below may differ from a more objective list like my DBLP entry.

I also write some short math notes on my blog about folklore problems whose answer was probably already well-known, but that I couldn’t find anywhere.

• 2025
  • Antonin Callard. PhD thesis: Soficity of multidimensional subshifts. Université de Caen, France, xvi+164, June 2025.
    pdf:thesis.pdf.
    Abstract:

    In symbolic dynamics, a multidimensional subshift is a formal language $X \subseteq \mathcal{A}^{\Z^d}$ of infinite colorings of the discrete space $\Z^d$ defined in terms of forbidden patterns. As languages of finite words have been classified into several complexity classes (which, classically, include the local regular, context-free, and computably enumerable languages…) depending on the expressiveness of the various devices used for their descriptions (respectively: local automata, finite automata, pushdown automata, Turing machines…), subshifts have been classified into subshifts of finite type (definied by finite families of forbidden patterns), effective subshifts (defined by computably enumerable families of forbidden patterns) and the sofic subshifts: the latter form an intermediary class, and are defined as the morphic images of subshifts of finite type by cellular automata.
    We are interested in the following question: when is a given subshift $X \subseteq \mathcal{A}^{\Z^d}$ actually sofic? In other words, how does one prove or disprove the soficity of a subshift? While this question is entirely solved in the one-dimensional setting (as $\Z$ sofic subshifts are very similar to regular languages of finite words, the Myhill-Nerode theorem characterizes one-dimensional soficity by counting the number of possible “contexts”), describing the frontier between sofic and effective multidimensional subshifts is still an open problem in symbolic dynamics.
    This thesis is divided in two independent parts, with preliminary chapters of introduction and definitions of the relevant notions being considered (from symbolic dynamics, computability theory…). In the first part, we study the extender sets of $\Z^d$ subshifts (which, informally, count the classes of patterns that can be freely exchanged in the configurations of a subshift) using computability theory: in particular, we prove that extender entropies of $\Z^d$ subshifts (i.e. the growth rate of the number of extender sets) can be fully characterized computationally in the arithmetical hierarchy of real numbers, the precise level depending on the complexity and the dynamical properties verified by the considered subshifts. In the second part, we prove a sufficient condition for multidimensional soficity based on a quantification of the “useful information” contained in patterns: more precisely, we introduce a notion of inductive representations (which, informally, describe the information exchanged between adjacent patterns of a given size to check the local validity of a configuration), and prove that admitting computable representations of small complexity is a sufficient condition for soficity. Finally, we describe these results as a variant of communication complexity on infinite colorings, and argue that non-deterministic communication complexity is a fruitful context of the study of multidimensional soficity.

  • Antonin Callard, Léo Paviet Salomon, Pascal Vanier. Computability of extender sets in multidimensional subshifts. STACS 2025, volume 327, 21:1--21:19, February 2025.
    doi:10.4230/LIPIcs.STACS.2025.21; arxiv:2401.07549; hal:04390697.
    Abstract:

    Subshifts are colorings of $\Z^d$ defined by families of forbidden patterns. Given a subshift and a finite pattern, its extender set is the set of admissible completions of this pattern. It has been conjectured that the behavior of extender sets, and in particular their growth called extender entropy ([French, Pavlov. 2018]), could provide a way to separate the classes of sofic and effective subshifts. We prove here that both classes have the same possible extender entropies: exactly the $\Pi_3$ real numbers of $[0,+\infty)$. We also consider computational properties of extender entropies for subshifts with some language or dynamical properties: computable language, minimal and some mixing properties.

• 2024
  • Antonin Callard, Ville Salo. Distortion in the automorphism group of a full-shift. Ergodic Theory and Dynamical Systems, volume 44 - issue 7, 1757--1817, July 2024.
    doi:10.1017/etds.2023.67; arxiv:2208.00685.
    Abstract:

    We show that there is a distortion element in a finitely-generated subgroup $G$ of the automorphism group of the full shift, namely an element of infinite order whose word norm grows polylogarithmically. As a corollary, we obtain a lower bound on the entropy dimension of any subshift containing a copy of $G$, and that a sofic shift's automorphism group contains a distortion element if and only if the sofic shift is uncountable. We obtain also that groups of Turing machines and the higher-dimensional Brin-Thompson groups $mV$ admit distortion elements; in particular, $2V$ (unlike $V$) does not admit a proper action on a $\mathrm{CAT}(0)$ cube complex. The distortion element is essentially the SMART machine.

• 2022
  • Antonin Callard, Benjamin Hellouin de Menibus. The aperiodic Domino problem in higher dimension. STACS 2022, volume 219, 19:1--19:15, March 2022.
    doi:10.4230/LIPIcs.STACS.2022.19; arxiv:2202.07377.
    Abstract:

    The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this paper, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift.
    [Grandjean, Hellouin and Vanier. 2018] proved that this problem is co-recursively enumerable ($\Pi_1^0$-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic ($\Sigma_1^1$-complete), in higher dimension: $d \geq 4$ in the finite type case, $d \geq 3$ for sofic and effective subshifts. The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity.
    This complexity jump is surprising for two reasons: first, it separates 2- and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large.

• 2021
  • Antonin Callard, Pascal Vanier. Surface entropies of $\Z^2$ subshifts of finite type. ICALP 2021, volume 198, 122:1--122:20, July 2021.
    doi:10.4230/LIPIcs.ICALP.2021.122; hal:03133208.
    Abstract:

    Subshifts of finite type (SFTs) are sets of colorings of the plane that avoid a finite family of forbidden patterns. In this article, we are interested in the behavior of the growth of the number of valid patterns in SFTs. While entropy $h$ corresponds to growths that are squared exponential $2^{hn^2}$, surface entropy (introduced in Pace's thesis in 2018) corresponds to the eventual linear term in exponential growths. We give here a characterization of the possible surface entropies of SFTs as the $\Pi_3^0$ real numbers of $[0,+\infty]$.

• 2020
  • Antonin Callard, Mathieu Hoyrup. Descriptive complexity on non-Polish spaces. STACS 2020, volume 154, 8:1--8:16, March 2020.
    doi:10.4230/LIPIcs.STACS.2020.8; hal:02298815.
    Abstract:

    Represented spaces are the topological spaces on which computations can be performed. We investigate the descriptive complexity of sets in represented spaces. First, we prove that the standard representation of a countably-based space preserves the effective descriptive complexity of sets, and we prove that some results from descriptive set theory on Polish spaces extend to arbitrary countably-based spaces. Secondly, we study the larger class of coPolish spaces (in particular the space of polynomials), and we show that their representation does not always preserve the complexity of sets. We relate this mismatch with the sequential aspects of the space.