Search

Parikh-collinear morphisms have the property that all the Parikh vectors of the images of letters are collinear, i.e., the associated adjacency matrix has rank 1. In the conference DLT–WORDS 2023 we showed that fixed points of Parikh-collinear morphisms are automatic. We also showed that the abelian complexity function of a binary fixed point of such a morphism is automatic under some assumptions. In this note, we fully generalize the latter result. Namely, we show that the abelian complexity function of a fixed point of an arbitrary, possibly erasing, Parikh-collinear morphism is automatic. Furthermore, a deterministic finite automaton with output generating this abelian complexity function is provided by an effective procedure. To that end, we discuss the constant of recognizability of a morphism and the related cutting set. [ABSTRACT FROM AUTHOR]

Following Inoue et al., we define a word to be a repetition if it is a (fractional) power of exponent at least 2. A word has a repetition factorization if it is the product of repetitions. We study repetition factorizations in several (generalized) automatic sequences, including the infinite Fibonacci word, the Thue-Morse word, paperfolding words, and the Rudin-Shapiro sequence. [ABSTRACT FROM AUTHOR]

Let t (n) denote the number of 1-bits in the base-2 representation of n , taken modulo 2. We show how to prove the classic conjecture of Leo Moser, on the rarefied sum ∑ 0 ≤ i < n (− 1) t (3 i) , using tools from automata theory and logic. The same technique can be used to prove results about analogous sums. [ABSTRACT FROM AUTHOR]

We explore the evaluation of infinite products involving the automatic sequence (d n : n ∈ N 0) known as the period-doubling sequence, inspired by the work of Allouche, Riasat, and Shallit on the evaluation of infinite products involving the Thue–Morse or Golay–Shapiro sequences. Our methods allow for the application of integral operators that result in new product expansions for expressions involving the dilogarithm function, resulting in new formulas involving Catalan's constant G, such as the formula ∏ n = 1 ∞ n + 2 n n + 1 4 n + 3 4 n + 5 4 n + 4 d n = e 2 G π 2 introduced in this article. More generally, the evaluation of infinite products of the form ∏ n = 1 ∞ e (n) d n for an elementary function e(n) is the main purpose of our article. Past work on infinite products involving automatic sequences has mainly concerned products of the form ∏ n = 1 ∞ R (n) a (n) for an automatic sequence a(n) and a rational function R(n), in contrast to our results as in above displayed product evaluation. Our methods also allow us to obtain new evaluations involving ζ (3) π 2 for infinite products involving the period-doubling sequence. [ABSTRACT FROM AUTHOR]

Motivated by near-identical graphs of two increasing continuous functions—one related to Zaremba's conjecture and the other due to Salem—we provide an explicit connection between fractals and regular sequences by showing that the graphs of ghost distributions, the distribution functions of measures associated to regular sequences, are sections of self-affine sets. Additionally, we provide a sufficient condition for such measures to be purely singular continuous. As a corollary, and analogous to Salem's strictly increasing singular continuous function, we show that the ghost distributions of the Zaremba sequences are singular continuous. [ABSTRACT FROM AUTHOR]

The Kronecker algebra K is the path algebra induced by the quiver with two parallel arrows, one source and one sink (i.e., a quiver with two vertices and two arrows going in the same direction). Modules over K are said to be Kronecker modules. The classification of these modules can be obtained by solving a well-known tame matrix problem. Such a classification deals with solving systems of differential equations of the form A x = B x ′ , where A and B are m × n , F -matrices with F an algebraically closed field. On the other hand, researching the Yang–Baxter equation (YBE) is a topic of great interest in several science fields. It has allowed advances in physics, knot theory, quantum computing, cryptography, quantum groups, non-associative algebras, Hopf algebras, etc. It is worth noting that giving a complete classification of the YBE solutions is still an open problem. This paper proves that some indecomposable modules over K called pre-injective Kronecker modules give rise to some algebraic structures called skew braces which allow the solutions of the YBE. Since preprojective Kronecker modules categorize some integer sequences via some appropriated snake graphs, we prove that such modules are automatic and that they induce the automatic sequences of continued fractions. [ABSTRACT FROM AUTHOR]

The ring $\mathbb Z_{d}$ of d -adic integers has a natural interpretation as the boundary of a rooted d -ary tree $T_{d}$. Endomorphisms of this tree (that is, solenoidal maps) are in one-to-one correspondence with 1-Lipschitz mappings from $\mathbb Z_{d}$ to itself. In the case when $d=p$ is prime, Anashin ['Automata finiteness criterion in terms of van der Put series of automata functions', p-Adic Numbers Ultrametric Anal. Appl. 4 (2) (2012), 151–160] showed that $f\in \mathrm {Lip}^{1}(\mathbb Z_{p})$ is defined by a finite Mealy automaton if and only if the reduced coefficients of its van der Put series constitute a p -automatic sequence over a finite subset of $\mathbb Z_{p}\cap \mathbb Q$. We generalize this result to arbitrary integers $d\geq 2$ and describe the explicit connection between the Moore automaton producing such a sequence and the Mealy automaton inducing the corresponding endomorphism of a rooted tree. We also produce two algorithms converting one automaton to the other and vice versa. As a demonstration, we apply our algorithms to the Thue–Morse sequence and to one of the generators of the lamplighter group acting on the binary rooted tree. [ABSTRACT FROM AUTHOR]

We study the properties of the ternary infinite word p = 012102101021012101021012⋯, that is, the fixed point of the map h : 0 → 01, 1 → 21, 2 → 0. We determine its factor complexity, critical exponent, and prove that it is 2-balanced. We compute its abelian complexity and determine the lengths of its bispecial factors. Finally, we give a characterization of p in terms of avoided factors. [ABSTRACT FROM AUTHOR]

We discuss the use of negative bases in automatic sequences. Recently the theorem-prover Walnut has been extended to allow the use of base (—k) to express variables, thus permitting quantification over ℤ instead of ℕ. This enables us to prove results about two-sided (bi-infinite) automatic sequences. We first explain the theory behind negative bases in Walnut. Next, we use this new version of Walnut to give a very simple proof of a strengthened version of a theorem of Shevelev. We use our ideas to resolve two open problems of Shevelev from 2017. We also reprove a 2000 result of Shut involving bi-infinite binary words. [ABSTRACT FROM AUTHOR]

We pursue an exploration into the interdisciplinarity given by amalgamations of the study of mathematical artwork and the study of automatic sequences. [ABSTRACT FROM AUTHOR]

We study the properties of the uncountable set of Stewart words. These are Toeplitz words specified by infinite sequences of Toeplitz patterns of the form αβγ , where α , β , γ is any permutation of the symbols 0,1,?. We determine the critical exponent of the Stewart words, prove that they avoid the pattern x x y y x x , find all factors that are palindromes, and determine their subword complexity. An interesting aspect of our work is that we use automata-theoretic methods and a decision procedure for automata to carry out the proofs. [ABSTRACT FROM AUTHOR]

Given a right-infinite word x over a finite alphabet A, the rank of x is the size of the smallest set S of words over A such that x can be realized as an infinite concatenation of words in S. We show that the property of having rank two is decidable for the class of k-automatic words for each integer k ≥ 2. [ABSTRACT FROM AUTHOR]

The Kronecker algebra K is the path algebra induced by the quiver with two parallel arrows, one source and one sink (i.e., a quiver with two vertices and two arrows going in the same direction). Modules over K are said to be Kronecker modules. The classification of these modules can be obtained by solving a well-known tame matrix problem. Such a classification deals with solving systems of differential equations of the form Ax=Bx′, where A and B are m×n, F-matrices with F an algebraically closed field. On the other hand, researching the Yang–Baxter equation (YBE) is a topic of great interest in several science fields. It has allowed advances in physics, knot theory, quantum computing, cryptography, quantum groups, non-associative algebras, Hopf algebras, etc. It is worth noting that giving a complete classification of the YBE solutions is still an open problem. This paper proves that some indecomposable modules over K called pre-injective Kronecker modules give rise to some algebraic structures called skew braces which allow the solutions of the YBE. Since preprojective Kronecker modules categorize some integer sequences via some appropriated snake graphs, we prove that such modules are automatic and that they induce the automatic sequences of continued fractions.

We prove a number of conjectures recently stated by P. Barry, related to the paperfolding sequence and the Rueppel sequence. Furthermore, we study the regularity of sequences involved in the paper, and prove that for all q ≥ 2 , the sequence consisting of the positive integers whose odd part is of the form 4 k + 1 is not q -regular. Finally we establish the 2-regularity of two sequences of Hankel determinants. [ABSTRACT FROM AUTHOR]

Let (a (n) : n ∈ N 0) denote an automatic sequence. Previous research on infinite products involving automatic sequences has mainly dealt with identities for products as in ∏ n R (n) a (n) for rational functions R (n). This inspires the development of techniques for evaluating ∏ n f (n) a (n) more generally, for functions f (n) that are not rational functions. This leads us to apply Euler's product expansion for the Γ-function together with recursive properties of a (n) to obtain identities as in ∏ n f (n , z) a (n) = Γ (z + 1) , and this is motivated by how the equivalent series identity ∑ n a (n) ln ⁡ f (n , z) = ln ⁡ Γ (z + 1) could be applied in relation to the remarkable results due to Gosper on the integration of ln ⁡ Γ (z + 1). We succeed in applying this approach, using Gosper's integration identities, to obtain new infinite products that we evaluate in terms of the Glaisher–Kinkelin constant A and that involve the Thue–Morse sequence, the period-doubling sequence, and the regular paperfolding sequence. A byproduct of our method gives us a way of generalizing a Dirichlet series identity due to Allouche and Sondow, and we also explore applications related to a product evaluation due to Gosper involving A. [ABSTRACT FROM AUTHOR]

The main subject of this paper are binary pattern sequences, that is, sequences of the form (− 1) # (n , A) where A is a set of strings of 0s and 1s, and # (n , A) denotes the total number of times patterns from A appear in the binary expansion of n. A sequence is said to be noncorrelated if the corresponding spectral measure is equal to the Lebesgue measure. We show that it is possible to algorithmically verify if a given binary pattern sequence is noncorrelated. As an application, we compute that there are exactly 2272 noncorrelated binary pattern sequences of length ≤4. If we restrict our attention to patterns that do not end with 0, we put forward a sufficient condition for a pattern sequence to be noncorrelated. We conjecture that this condition is also necessary, and verify this conjecture for lengths ≤5. [ABSTRACT FROM AUTHOR]

We extend the notion of k -automatic sequences to Ostrowski-automatic sequences, and develop a procedure to computationally decide certain combinatorial and enumeration questions about such sequences that can be expressed as predicates in first-order logic. Our primary contribution is the design and implementation of an adder recognizing addition in a generalized Ostrowski numeration system. We also provide applications of our work to several topics in combinatorics on words, including repetitions and pattern avoidance. We partially resolve a previous conjecture about balanced words by Rampersad et al., and make the first progress on an open problem on rich words by Vesti. We also prove some known results about Lucas words using only machine computation. [ABSTRACT FROM AUTHOR]

We present a short proof of Cobham's theorem without using Kronecker's approximation theorem, making it suitable for generalization beyond automatic sequences. [ABSTRACT FROM AUTHOR]

Continued fraction expansions of automatic numbers have been extensively studied during the last few decades. The research interests are, on one hand, in the degree or automaticity of the partial quotients following the seminal paper of Baum and Sweet in 1976, and on the other hand, in calculating the Hankel determinants and irrationality exponents, as one can find in the works of Allouche–Peyrière–Wen–Wen, Bugeaud, and the first author. This paper is motivated by the converse problem: to study Stieltjes continued fractions whose coefficients form an automatic sequence. We consider two such continued fractions defined by the Thue–Morse and period-doubling sequences, respectively, and prove that they are congruent to algebraic series in ℤ [ [ x ] ] modulo 4. Consequently, the sequences of the coefficients of the power series expansions of the two continued fractions modulo 4 are 2 -automatic. [ABSTRACT FROM AUTHOR]

In this article, we prove that all completely multiplicative automatic sequences (a n) n ∈ N defined on C , vanishing or not, can be written in the form a n = b n χ n , where (b n) n ∈ N is an almost constant sequence, and (χ n) n ∈ N is a Dirichlet character. [ABSTRACT FROM AUTHOR]

A formal inverse of a given automatic sequence (the sequence of coefficients of the composition inverse of its associated formal power series) is also automatic. The comparison of properties of the original sequence and its formal inverse is an interesting problem. Such an analysis has been done before for the Thue-Morse sequence. In this paper, we describe arithmetic properties of formal inverses of the generalized Thue-Morse sequences and formal inverses of two modifications of the Rudin-Shapiro sequence. In each case, we give the recurrence relations and the automaton, then we analyze the lengths of factors consisting of identical letters as well as the frequencies of letters. We also compare the obtained results with the original sequences. [ABSTRACT FROM AUTHOR]

In a recent paper, one of us posed three open problems concerning squarefree arithmetic progressions in infinite words. In this paper we solve these problems and prove some additional results. For instance, among other things, we show that there exists a squarefree word w over a ternary alphabet such that for every p ≥ 3 , the subsequence of w indexed by the multiples of p contains a square. [ABSTRACT FROM AUTHOR]

Hankel determinants and automatic sequences are two classical subjects widely studied in Mathematics and Theoretical Computer Science. However, these two topics were considered totally independently, until in 1998, when Allouche, Peyrière, Wen and Wen proved that all the Hankel determinants of the Thue-Morse sequence are nonzero. This property allowed Bugeaud to prove that the irrationality exponents of the Thue-Morse-Mahler numbers are exactly 2. Since then, the Hankel determinants of several other automatic sequences, in particular, the paperfolding sequence, the Stern sequence, the period-doubling sequence, are studied by Coons, Vrbik, Guo, Wu, Wen, Bugeaud, Fu, Han, Fokkink, Kraaikamp, and Shallit. On the other hand, it is known that the Hankel determinants of a rational power series are ultimately zero, and the Hankel determinants of a quadratic power series over finite fields are ultimately periodic. It is therefore natural to ask if we can obtain similar results about the Hankel determinants of algebraic series. In the present paper, we provide a partial answer to this question by establishing the automaticity of the reduced Hankel determinants modulo 2 of a family of automatic sequences. As an application of our result, we give upper bounds for the irrationality exponent of a family of automatic numbers. [ABSTRACT FROM AUTHOR]

Studying and comparing arithmetic properties of a given automatic sequence and the sequence of coefficients of the composition inverse of the associated formal power series (the formal inverse of that sequence) is an interesting problem. This problem was studied before for the Thue–Morse sequence. In this paper, we study arithmetic properties of the formal inverses of two sequences closely related to the well-known Baum–Sweet sequence. We give the recurrence relations for their formal inverses and we determine whether the sequences of indices at which these formal inverses take value 0 and 1 are regular. We also show an unexpected connection between one of the obtained sequences and the formal inverse of the Thue–Morse sequence. [ABSTRACT FROM AUTHOR]

In this paper, we study the abelian complexity ρ n a b (t (k)) of generalized Thue-Morse sequences t (k) for every integer k ≥ 2. We obtain the exact value of ρ n a b (t (k)) for every integer n ≥ k. Consequently, ρ n a b (t (k)) is ultimately periodic with period k. Moreover, we show that the abelian complexities of a class of infinite sequences are automatic sequences. [ABSTRACT FROM AUTHOR]

In a recent paper, Jason P. Bell and Jeffrey Shallit introduced the notion of Lie complexity and proved that the Lie complexity function of an automatic sequence is automatic. In this note, we give more facts concerning Lie complexity and define the extended Lie complexity and the prefix Lie complexity. Further, we prove that some proprieties of Lie complexity also hold for the extended Lie complexity. Particularly, we prove that the extended Lie complexity function and the first-order difference sequence of the prefix Lie complexity function of an automatic sequence are both automatic. This article is dedicated to Jean-Paul Allouche on the occasion of his 70th birthday. [ABSTRACT FROM AUTHOR]

We study correlation estimates of automatic sequences (that is, sequences computable by finite automata) with polynomial phases. As a consequence, we provide a new class of good weights for classical and polynomial ergodic theorems. We show that automatic sequences are good weights in L2 for polynomial averages and totally ergodic systems. For totally balanced automatic sequences (i.e., sequences converging to zero in mean along arithmetic progressions) the pointwise weighted ergodic theorem in L1 holds. Moreover, invertible automatic sequences are good weights for the pointwise polynomial ergodic theorem in Lr, r > 1. [ABSTRACT FROM AUTHOR]

In this paper, we study the abelian complexity of the Rudin–Shapiro sequence and a related sequence. We show that these two sequences share the same complexity function ρ ( n ) , which satisfies certain recurrence relations. As a consequence, the abelian complexity function is 2-regular. Further, we prove that the box dimension of the graph of the asymptotic function λ ( x ) is 3/2, where λ ( x ) = lim k → ∞ ⁡ ρ ( 4 k x ) / 4 k x and ρ ( x ) = ρ ( ⌊ x ⌋ ) for every x > 0 . [ABSTRACT FROM AUTHOR]

The irrationality exponent of an irrational p-adic number $$\xi $$ , which measures the approximation rate of $$\xi $$ by rational numbers, is in general very difficult to compute explicitly. In this work, we shall show that the irrationality exponents of large classes of automatic p-adic numbers and Mahler p-adic numbers (which are transcendental) are exactly equal to 2. Our classes contain the Thue-Morse-Mahler p-adic numbers, the regular paperfolding p-adic numbers, the Stern p-adic numbers, among others. [ABSTRACT FROM AUTHOR]

Allouche and Shallit introduced the notion of a regular power series as a generalisation of automatic sequences. Becker showed that all regular power series satisfy Mahler equations and conjectured equivalent conditions for the converse to be true. We prove a stronger form of Becker's conjecture for a subclass of Mahler power series. [ABSTRACT FROM AUTHOR]

We present family of automatic sequences that define algebraic continued fractions in characteristic 2. This family is constructed from ultimately period words and contains the period-doubling sequence. [ABSTRACT FROM AUTHOR]