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, Léo Paviet Salomon, Pascal Vanier. Computability of extender sets in multidimensional subshifts: asymptotic growths, dynamical constraints. 1--43, October 2025.
    arxiv:2401.07549.
    Abstract:

    Subshifts are sets of colorings of $\Z^d$ defined by families of forbidden patterns. In a given subshift, the extender set of a finite pattern is the set of all its admissible completions. Since soficity of $\Z$ subshifts is equivalent to having a finite number of extender sets, it had been conjectured that the number of extender sets could provide a way to separate the classes of sofic and effective subshifts in higher dimensions.
    We investigate some computational characterizations of extender sets in multidimensional subshifts, and in particular their growth, in terms of extender entropies ([French & Pavlov; 2018]) and extender entropy dimensions. We prove here that sofic and effective subshifts have the same possible extender entropies (exactly the $\Pi_3$-computable real numbers of $[0,+\infty)$) and extender entropy dimensions, and investigate the computational complexity of these growth-type quantities under various dynamical and combinatorial constraints.

    Extended version of the original conference paper:

    • Antonin Callard, Léo Paviet Salomon, Pascal Vanier. Computability of extender sets in multidimensional subshifts. STACS 2025, LIPICs volume 327, 21:1--21:19, February 2025.
      doi:10.4230/LIPIcs.STACS.2025.21; arxiv:2401.07549v2; hal:04390697.
  • 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.

• 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, LIPICs 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 & 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, LIPICs 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, LIPICs 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.