Printer Friendly

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


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


On the other hand we have


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


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


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


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.


[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

COPYRIGHT 2011 Belgian Mathematical Society
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Schlage-Puchta, Jan-Christoph
Publication:Bulletin of the Belgian Mathematical Society - Simon Stevin
Article Type:Report
Date:May 1, 2011
Previous Article:Path space and free loop space.
Next Article:Subharmonic solutions for some nonautonomous Hamiltonian systems with p(t)-Laplacian.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters