Relations among arithmetical functions, automatic sequences, and sum of digits functions induced by certain Gray codes

Kamiya, Yuichi; Murata, Leo

Journal de théorie des nombres de Bordeaux, Tome 24 (2012) no. 2, pp. 307-337.

Dans l’étude de la somme des chiffres $S_2$ en base deux, la fonction arithmétique $u$ définie par $u\left(0\right)=0$ et $u\left(n\right)={(-1)}^{n-1}$ pour $n\ge 1$ joue un rôle de première importance. Dans cet article, nous commençons par généraliser la relation entre $S_2$ et $u$ en introduisant une permutation sur l’ensemble des suites à valeurs complexes, nulles en 0. Comme application, certaines relations impliquant la fonction somme des chiffres $S_{𝒢}$ associée à un code binaire infini $𝒢$ de type Gray sont mises en vidence. En particulier nous montrons que la différence $n\mapsto S_{𝒢}\left(n\right)-S_{𝒢}(n-1)$ s’obtient par un automate. La formule sommatoire de P. Flajolet et L. Ramshaw pour la somme des chiffres associée au classique code refléchi de Gray est aussi généralisée. La méthode est analytique ; elle utilise la tranformée de Mellin et la formule de Perron pour les séries de Dirichlet.

In the study of the $2$-adic sum of digits function $S_2\left(n\right)$, the arithmetical function $u\left(0\right)=0$ and $u\left(n\right)={(-1)}^{n-1}$ for $n\ge 1$ plays a very important role. In this paper, we firstly generalize the relation between $S_2\left(n\right)$ and $u\left(n\right)$ to a bijective relation between arithmetical functions. And as an application, we investigate some aspects of the sum of digits functions $S_{𝒢}\left(n\right)$ induced by binary infinite Gray codes $𝒢$. We can show that the difference of the sum of digits function, $S_{𝒢}\left(n\right)-S_{𝒢}(n-1)$, is realized by an automaton. And the summation formula of the sum of digits function for reflected binary code, proved by P. Flajolet and L. Ramshaw, is also generalized. Here we use analytic tools such as Mellin transform and Perron’s formula for Dirichlet series.

Classification : 11A25, 11B85
Mots clés : arithmetical function, sum of digits function, Gray code, automatic sequence, Delange’s theorem.

[1] J. P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003. | MR

[2] T. M. Apostol, Introduction to Analytic Number Theory. Springer-Verlag, UTM, 1976. | MR | Zbl

[3] H. Delange, Sur la fonction sommatoire de la fonction “somme des chiffres". L’Enseignement Math. 21 (1975), 31–47. | MR | Zbl

[4] J. M. Dumont and A. Thomas, Systemes de numeration et fonctions fractales relatifs aux substitutions. Theoretical Computer Science 65 (1989), 153–169. | MR | Zbl

[5] P. Flajolet and L. Ramshaw, A note on Gray code and odd-even merge. SIAM J. Comput. 9 (1980), 142–158. | MR | Zbl

[6] P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger, and R. F. Tichy, Mellin transforms and asymptotics: digital sums. Theoretical Computer Science 123 (1994), 291–314. | MR | Zbl

[7] F. Gray, Pulse Code Communications. U.S. Patent 2632058, March 1953.

[8] J. L. Mauclaire and L. Murata, An explicit formula for the average of some $q$-additive functions. Proc. Prospects of Math. Sci., World Sci. Pub. (1988), 141–156. | MR | Zbl

[9] C. E. Killian and C. D. Savage, Antipodal Gray Codes. Discrete Math. 281 (2004), 221–236. | MR