NON-REGULARITY OF bα+ logk nc

Abstract. This paper presents a new proof that if kα is irrational then the sequence {bα+logk nc}n≥1 is not k-regular. Unlike previous proofs, the meth-ods used do not rely on automata or language theoretic concepts. The paper also proves the stronger statement that if kα is irrational then the generating function in k non-commuting variables associated with {bα + logk nc}n≥1 is not algebraic. Fix an integer k ≥ 2. A sequence {a(n)}n≥0 is k-regular if the Z-module gen-erated by the subsequences {a(ken + i)}n≥0 for e ≥ 0 and 0 ≤ i < ke is finitely generated. Regular sequences were introduced by Allouche and Shallit [1] and have several nice characterizations, including the following characterization as rational power series in non-commuting variables x0, x1,..., xk−1. If n = nl · · ·n1n0 is the standard base-k representation of n, then let τ(n) = xn0xn1 · · ·xnl. The sequence {a(n)}n≥0 is k-regular if and only if the power series n≥0 a(n)τ(n) is rational. In this sense, regular sequences are analogous to constant-recursive sequences (se-quences that satisfy linear recurrence equations with constant coefficients), the set of which coincides with the set of sequences whose generating functions in a single variable are rational. The sequence {blog2(n+ 1)c}n≥0 is an example of a 2-regular sequence, and the associated power series in non-commuting variables x0 and x1 is f(x0, x1) = n≥0 blog2(n+ 1)cτ(n) = x1 + x0x1 + 2x1x1 + 2x0x0x1 + 2x1x0x1 + 2x0x1x1 + 3x1x1x1 + · · ·. The rational expression for this series is somewhat large; however its commutative projection is quite manageable: x1 1 − x0 − x1 + x20 + x0x1 (1 − x1) (1 − x0 − x1)2 Allouche and Shallit [2, open problem 16.10] asked whether the sequence {b 12 + log2(n+ 1)c}n≥0 is 2-regular. Bell [3] and later Moshe [5, Theorem 4] gave proofs that this sequence is not 2-regular. Moreover, they proved the following. Theorem. Let k ≥ 2 be an integer and α be a real number. The sequence {bα + logk(n+ 1)c}n≥0 is k-regular if and only if kα is rational. In this paper we prove the following theorem, which is a slightly weaker statement than the previous theorem but still establishes that if kα is irrational then {bα + logk(n + 1)c}n≥0 is not k-regular. Let |τ(n) | be the length of the word τ(n), i.e., |τ(0) | = 0 and |τ(n) | = blogk nc+ 1 for n ≥ 1