A method for determining the mod-\(2^k\) behaviour of recursive sequences, with applications to subgroup counting
type: Item
instance of: scholarly article
title: A method for determining the mod-\(2^k\) behaviour of recursive sequences, with applications to subgroup counting
zbMATH Open document ID: 1260.05008
author: M. Kauers
author: C. Krattenthaler
author: T. W. Müller
published in: The Electronic Journal of Combinatorics
publication date: 2012-10-23T00:00:00Z
full work available at URL: https://arxiv.org/abs/1107.2015
full work available at URL: v18i2p37
reviewed by: Jan-Christoph Schlage-Puchta
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 20E07
Mathematics Subject Classification ID: 11A07
Mathematics Subject Classification ID: 11B37
zbMATH DE Number: 6098117
zbMATH Keywords: generating functions
zbMATH Keywords: formal power series
zbMATH Keywords: congruences
zbMATH Keywords: subgroup growth
MaRDI profile type: Publication
arXiv ID: 1107.2015
Recommended article: Asymptotic behaviour of the poles of a special generating function for acyclic digraphs
Recommended article: Note sur une identite dans la théorie des congruences supérieures.
Recommended article: Single variable Bell polynomials
Recommended article: Sulle somme delle potenze simili dei numeri interi, e sui numeri di Bernoulli et di Stirling.
Recommended article: The fine numbers refined
Recommended article: Q4383341
Recommended article: On equal roots of equations.
Recommended article: Bemerkungen über das Integral \(\int _0^{\infty } z^s e^{-e^z} dz\).
Recommended article: Note on a number theoretical function.
Recommended article: Generalized Bell numbers and zeros of successive derivatives of an entire function
review text: For a finitely generated group \(\Gamma\), denote by \(s_n(\Gamma)\) the number of subgroups of index \(n\) in \(\Gamma\). \textit{W. W. Stothers}, [Proc. R. Soc. Edinb., Sect. A 78, 105--112 (1977; Zbl 0384.20037)] showed that \(s_n(\mathrm{PSL}_2(\mathbb{Z}))\) is odd if and only if \(n\) is of the form \(2^k-3\) or \(2^k-6\). While Stothers proof was mainly combinatorial, \textit{C. Godsil}, \textit{W. Imrich}, and \textit{R. Razen}, [Monatsh. Math. 87, 273--280 (1979; Zbl 0407.20037)] proved the same result by constructing a differential equation for the generating function of \(s_n(\mathrm{PSL}_2(\mathbb{Z}))\). This approach was later generalised to quite general free products by the last named author [Forum Math. 15, No. 5, 759--810 (2003; Zbl 1042.20012)] and to moduli being higher powers of 2 by the last author and the reviewer [New York J. Math. 11, 205--224 (2005; Zbl 1111.20042)]. In all these cases numbers which are close to integers of the form \(2^{k_1}+\dots+2^{k_\ell}\) played a special rôle. In a completely different context, \textit{S.-C. Liu} and \textit{J. C.-C. Yeh}, [J. Integer Seq. 13, No. 5, Article ID 10.5.4, (2010; Zbl 1230.05013)] determined the behaviour of the Catalan numbers modulo 64. Again, numbers close to integers of the form \(2^{k_1}+\dots+2^{k_\ell}\) were special. In the present work the authors give a structural explanation for these at first sight unexpected phenomena.NEWLINENEWLINEThe central object of this paper is the function \(\Phi(z)=\sum_{n\geq 1} z^{2^n}\). While \(\Phi(z)\) is transcendental over \(\mathbb{C}\), it is algebraic over \(\mathbb{Z}/2^\alpha\mathbb{Z}\) for any \(\alpha\). In this article a method is described, which can solve the following problem. Given a polynomial \(P\) in \(k+2\) variables with integral coefficients, such that the differential equation \(P(z, f, f', \ldots, f^{(k)})=0\) has a unique solution as a formal power series, and an integer \(\alpha>0\), find a solution of this differential …
description: scientific article; zbMATH DE number 6098117