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 conferences proceedings or journals . The articles below may differ from more objective lists like my DBLP entry.

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

• 2023
  • Antonin Callard, Ville Salo. Distortion in the automorphism group of a full-shift. ETDS, (preview), 1--61, October 2023. [DOI] [arXiv]
    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] [arXiv]
    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_0^1$-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] [HAL]
    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] [HAL]
    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.