# Regularity of a function related to the 2-adic logarithm.

For a function f: N [right arrow] X mapping the positive integers to some set X, define the q-kernel [K.sub.q](f) as the set of functions {[f.sub.k,l] : k [member of] N, 0 [less than or equal to] l < [q.sup.k]}, where [f.sub.k,l](n) = f([q.sup.k]n + l). The q-kernel is related to the concept of q-automaticity by the following criterion due to Eilenberg [2] (see also [1, Theorem 6.6.2]).

Theorem 1. A function f is q-automatic if and only if [K.sub.q](f) is finite.

The notion of q-regularity generalizes the concept of q-automaticity in the case that X is the set of integers. A function f is called q-regular if [K.sub.q](f) is contained in a finitely generated Z-module.

Motivated by work of Lengyel [3] on the 2-adic logarithm, Allouche and Shallit [1, Problem 16.7.4] asked whether the function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (1)

where [v.sub.2](k) is the 2-adic valuation, is 2-regular or not. Here we give a negative answer to this question. More precisely, we show the following.

Theorem 2. The functions [f.sub.k,0]: n [right arrow] f([2.sup.k]n) are Q-linearly independent.

For the proof we need the following simple statements concerning f.

Proposition 1. 1. We have f{n) = n - O(log n).

2. For n = ([2.sup.l+2] - 3)[2.sup.m] we have f (n) = min (n - m, n - m - l - 2 + 3 x [2.sup.m]). Proof. (1) We trivially have the bound f(n) [less than or equal to] n. On the other hand we have [v.sub.2](k) [less than or equal to] and hence f(n) [greater than or equal to] [min.sub.k[greater than or equal to]n] k - log k/log 2. Since the derivative of the function t - log t/log 2 is 1 - 1/t log 2, which is positive for t [greater than or equal to] 2, for n [greater than or equal to] 2 the minimum is attained for k = n and we conclude f(n) [greater than or equal to] n - log n/log 2, and the first claim is proven.

(2) We want to show that as k runs over all integers [greater than or equal to]n the minimum in (1) is attained at k = n or at k = [2.sup.l+m+2] = n + 3 x [2.sup.m]. From this our claim follows by computing the value of k - [v.sub.2](k) at these two positions. Assume first that k [greater than or equal to] n is not divisible by [2.sup.m+1]. Then we have k - [v.sub.2](k) [greater than or equal to] n - [v.sub.2](k) [greater than or equal to] n - m, which is what we want to have. Next assume that [v.sub.2](k) > m and k < [2.sup.l+m+2]. Then k = ([2.sup.l+2] - 2)[2.sup.m], that is, [v.sub.2](k) = m + 1, and we have k - [v.sub.2](k) = (n + [2.sup.m]) - (m + 1) [greater than or equal to] n - m, which is also consistent with our claim. For k = [2.sup.l+m+2] we have k - [v.sub.2](k) = n - m - l - 2 + 3 x [2.sup.m], and thus it remains to consider the range k > [2.sup.l+m+2]. For [2.sup.l+m+2] < k < [2.sup.l+m+3] we have k - [v.sub.2](k) [greater than or equal to] [2.sup.l+m+2] + 1 - (l + m + 1) > [2.sup.l+m+2] - (l + m + 2), and hence this range cannot contribute to the minimum. Finally, if k [greater than or equal to] [2.sup.l+m+3], then k - [v.sub.2](k) [greater than or equal to] k - log k/log 2 [greater than or equal to] [2.sup.l+m+3] - (l + m + 3) > [2.sup.l+m+2] - (l + m + 2), and this range is also of no importance. Hence, the second claim follows as well.

We now turn to the proof of the theorem. Assume the family of functions [([f.sub.k,0]).sub.k[greater than or equal to]0] was linearly dependent. Then there exist rational numbers [[lambda].sub.0], ..., [[lambda].sub.p], not all 0, such that

[p.summation over (j=0)] [[lambda].sub.j]f([2.sup.j]n) = 0 (2)

holds for all integers n. Evaluating this equation asymptotically for n [right arrow] [infinity] we see that the left hand side is n x ([[summation].sup.p.sub.j=0] [2.sup.j][[lambda].sub.j]) + O(log n). This expression can only vanish identically if

[p.summation over (j=0)][2.sup.j][[lambda].sub.j] = 0. (3)

Let [j.sub.0] be the least integer satisfying [lambda]. Then define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and put n = [2.sup.l] - 3 into (2). We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

On the other hand we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for all j > [j.sub.0], hence, by the second part of the proposition relation (2) becomes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

Finally we put n' = [2.sup.l+1] - 3 into (2). The same computation as the one used for n yields the equation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

Note that the difference between (4) and (5) is that n is replaced by n', and -2 is replaced by -3. If we take the difference of (4) and (5), we therefore obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If we now multiply (3) by (n - n'), and subtract the result from the last equation, all that remains is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. But [j.sub.0] was chosen subject to the condition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence, the initial assumption that not all [[lambda].sub.j] are 0 is wrong, and we conclude that there is no linear relation among the functions [f.sub.k,0].

The reader might wonder why we restricted our attention to the functions [f.sub.k,0]. Essentially the same method of proof can be used to show that the dimension of the linear span <[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]> tends to infinity with k. However, things become notationally more involved, since these functions are no longer linearly independent. In fact, we have [f.sub.k,a] = [f.sub.k,a+1] for every odd a and many more identities like this, that is, these functions are not even different, and to give a lower bound for the dimension we have to choose a suitable subset.

Key words and phrases : automatic sequence, regular sequence, 2-adic logarithm.

References

[1] J.-P. Allouche, J. Shallit, Automatic Sequences, Cambridge University Press, Cambridge, 2003.

[2] Eilenberg, Automata, Languages, and Machines, Academic Press, New York, 1974.

[3] T. Lengyel, Characterizing the 2-adic order of the logarithm. Fibonacci Quart. 32 (1994), 397-401.

Received by the editors January 2010--In revised form in June 2010.

Communicated by A. Weiermann.

2000 Mathematics Subject Classification : 68Q45, 68Q70.

Krijgslaan 281

Gebouw S22

9000 Gent

Belgium

email:jcsp@cage.ugent.be