A method for determining the mod-\(2^k\) behaviour of recursive sequences, with applications to subgroup counting (Q456187)

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. The 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 equation, which modulo \(2^\alpha\) coincides with a polynomial in \(z, z^{-1}\), and \(\Phi\). Such a solution need not exist, and in certain degenerate cases the method presented here might miss a solution, however, in many cases the method allows one to prove that for any \(\alpha\) such a solution exists, and to explicitly compute such a solution for rather large values of \(\alpha\). As applications the authors show that for each \(\alpha>0\) the generating function of the Catalan numbers coincides modulo \(2^{3\cdot 2^\alpha}\) with a polynomial in \(z, z^{-1}\) and \(\Phi\), which has at most degree \(2^{\alpha+2}-1\) in \(\Phi\). The same holds true for the number of subgroups in \(\mathrm{PSL}_2(\mathbb{Z})\) and the number of free subgroups in cyclic extensions of \(\mathrm{PSL}_2(\mathbb{Z})\) of the form \(\Gamma_q=\langle x,y|x^{2q}=y^{3q}=1\rangle\). Moreover, \(s_n(\mathrm{SL}_2(\mathbb{Z}))\) is computed modulo 16, and \(s_n(\Gamma_3)\) modulo 8. Finally the authors consider variations of their method obtained by replacing \(\Phi\) by certain generalised power series, and apply this generalisation to certain Fuß-Catalan numbers and to \(s_n(C_2\ast C_5)\).