\documentclass[12pt]{article} \usepackage{e-jc} \specs{P37}{18(2)}{2012} \usepackage{amsthm,amsmath,amssymb} \usepackage{latexsym} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{ar$\chi$iv:#1}}} \numberwithin{equation}{section} \newtheorem{theorem}{Theorem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem*{remark}{Remark} \newtheorem{remarknu}[theorem]{Remark} \newtheorem*{note}{Note} \newtheorem{example}{Example} \def\fl#1{\left\lfloor#1\right\rfloor} \def\cl#1{\left\lceil#1\right\rceil} \def\coef#1{\left\langle#1\right\rangle} \def\Cat{\operatorname{Cat}} \def\Hom{\operatorname{Hom}} \def\Mono{\operatorname{Mono}} \def\Epi{\operatorname{Epi}} \def\tS{{\tilde S}} \def\FF{F} \def\GG{G} \def\al{\alpha} \def\be{\beta} \def\de{\delta} \def\si{\sigma} \def\ta{\tau} \def\rh{\rho} \def\ga{\gamma} \def\om{\omega} \def\Ga{\Gamma} \def\la{\lambda} \def\De{\Delta} \newcommand{\sq}{\mathrm{sq}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\N}{\mathbb{N}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\stab}{\mathrm{Stab}} \renewcommand{\labelenumi}{(\roman{enumi})} %\newcommand{\qed}{\hfill \mbox{$\Box$}\vspace{\baselineskip}} \title{A method for determining the\\ mod-$2^k$ behaviour of recursive sequences,\\ with applications to subgroup counting} \author{M. Kauers\thanks{Research supported by the Austrian Science Foundation FWF, grant Y464-N18.}\\ \small Research Institute for Symbolic Computation\\[-0.8ex] \small Johannes Kepler Universit\"at, Altenbergerstra\ss e 69\\[-0.8ex] \small A-4040 Linz, Austria\\ \small WWW: {\tt http://www.kauers.de/}\\ \and C. Krattenthaler\thanks{Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network ``Analytic Combinatorics and Probabilistic Number Theory".}\\ \small Fakult\"at f\"ur Mathematik, Universit\"at Wien\\[-0.8ex] \small Nordbergstra\ss e~15, A-1090 Vienna, Austria\\ \small WWW: {\tt http://www.mat.univie.ac.at/\lower0.5ex\hbox{\~{}}kratt}\\ \and T. W. M\"uller\thanks{Research supported by Lise Meitner Grant M1201-N13 of the Austrian Science Foundation FWF.}\\ \small School of Mathematical Sciences, Queen Mary\\[-0.8ex] \small \& Westfield College, University of London,\\[-0.8ex] \small Mile End Road, London E1 4NS, United Kingdom.%\newline %WWW: \tt http://www.maths.qmw.ac.uk/\~{}twm/. } \date{\dateline{May 3, 2011}{Jun 9, 2012}{Jun 20, 2012}\\ \small 2010 Mathematics Subject Classifications: Primary 20E06; Secondary 05A15 05E99 11A07 20E07 33F10 68W30} %\keywords{Polynomial recurrences, symbolic summation, %subgroup numbers, free subgroup numbers, %Catalan numbers, Fu\ss--Catalan numbers} \begin{document} \maketitle \centerline{\it Dedicated to Doron Zeilberger} \bigskip \begin{abstract} We present a method to obtain congruences modulo powers of $2$ for sequences given by recurrences of finite depth with polynomial coefficients. We apply this method to Catalan numbers, Fu\ss--Catalan numbers, and to subgroup counting functions associated with Hecke groups and their lifts. This leads to numerous new results, including many extensions of known results to higher powers of $2$. \phantom{spacer} \end{abstract} \section{Introduction} Ever since the work of Sylow \cite{SyloAA}, Frobenius \cite{Frob1,Frob2}, and P.~Hall \cite{PHall2}, the study of congruences for subgroup numbers and related numerical quantities of groups has played an important role in group theory. Divisibility properties of subgroup numbers of (finitely generated) infinite groups may to some extent be viewed as some kind of analogue to these classical results for finite groups. To the best of our knowledge, the first significant result in this direction was obtained by Stothers \cite{Stothers}: {\it the number of index-$n$-subgroups in the inhomogeneous modular group $PSL_2(\mathbb Z)$ is odd if, and only if, $n$ is of the form $2^k-3$ or $2^{k+1}-6,$ for some positive integer $k\ge2$.} A different proof of this result was given by Godsil, Imrich, and Razen \cite{GIR}. The systematic study of divisibility properties of subgroup counting functions for infinite groups begins with \cite{MuHecke}. There, the parity of subgroup numbers and the number of free subgroups of given finite index are determined for arbitrary Hecke groups $\mathfrak H(q)=C_2*C_q$ with $q\ge3$. Subsequently, the results of \cite{MuHecke} were generalised to larger classes of groups and arbitrary prime modulus in \cite{CaMuAA,KrMuAC,ModSub2,ModSub,MuPu2}. A first attempt at obtaining congruences modulo higher prime powers was made in \cite{MuPu}, where the behaviour of subgroup numbers in $PSL_2(\mathbb Z)\cong \mathfrak H(3)$ is investigated modulo $8$ and a congruence modulo $16$ is derived for the number of free subgroups of given index in $PSL_2(\mathbb Z)$. A common feature of all the above listed sequences of subgroup numbers is that they obey recurrences of finite depth with polynomial coefficients. The purpose of this paper is to present a new method for determining congruences modulo arbitrarily large powers of $2$ for sequences described by such recurrences. Our method is inspired by the observation that many of the aforementioned results say in essence that the generating function for the subgroup numbers under consideration, when reduced modulo a $2$-power, can be expressed as a polynomial in the basic series \begin{equation} \label{eq:Phidef} \Phi(z)=\sum _{n\ge0} ^{}z^{2^n} \end{equation} with coefficients that are Laurent polynomials in $z$. What our method affords is an algorithmic procedure to find such polynomial expressions, provided they exist. By applying our method to Catalan numbers, to (certain) Fu\ss--Catalan numbers, and to various subgroup counting problems in Hecke groups and their lifts, we obtain far-reaching generalisations and extensions of the previously mentioned results. In order to give a concrete illustration, the recent result \cite[Theorems~6.1--6.6]{LiYeAA} of Liu and Yeh determining the behaviour of Catalan numbers $\Cat_n$ modulo $64$ can be compactly written in the form \begin{multline} \label{eq:Cat64} \sum _{n=0} ^{\infty}\Cat_nz^n= 32 z^5+16 z^4+6 z^2+13 z+1 +\left(32 z^4+32 z^3+20 z^2+44 z+40\right) \Phi(z)\\ +\left(16 z^3+56 z^2+30 z+52+\frac{12}{z}\right) \Phi^2(z) +\left(32 z^3+60 z+60+\frac{28}{z}\right) \Phi^3(z)\\ +\left(32 z^3+16 z^2+48 z+18+\frac{35}{z}\right) \Phi^4(z) +\left(32 z^2+44\right) \Phi^5(z)\\ +\left(48 z+8+\frac{50}{z}\right) \Phi^6(z)+\left(32 z+32+\frac{4}{z}\right) \Phi^7(z) \quad \quad \text { modulo }64, \end{multline} as may be seen by a straightforward (but rather tedious) computation. Our method can not only {\it find\/} this result, but it produces as well corresponding formulae modulo {\it any} given power of $2$ in a completely automatic fashion, see Theorems~\ref{thm:Cat} and \ref{thm:Cat4096} in Section~\ref{sec:Cat}. In a sense, which is made precise in Section~\ref{sec:method}, our method is very much in the spirit of Doron Zeilberger's philosophy that {\it mathematicians should train computers to automatically produce theorems}. Indeed, Theorems~\ref{thm:Cat}, \ref{thm:freie-m}, \ref{thm:Unterg}, \ref{thm:2mf}, \ref{thm:H5} imply that our algorithm is able to produce a theorem on the behaviour modulo {\it any} given $2$-power of the subgroup counting functions featuring in these theorems, and, if fed with a concrete $2$-power, our implementation will diligently output the corresponding result (provided the input does not cause the available computer resources to be exceeded \dots). Moreover, when discussing subgroup numbers of lifts of $PSL_2(\mathbb Z)$, (such as the homogeneous modular group $SL_2(\mathbb Z)$), a crucial role is also played by an application of the holonomic functions approach to finding recurrences for multi-variate hypergeometric sums, pioneered by Wilf and Zeilberger \cite{WiZeAC,ZeilAN}, and further developed in \cite{ChyzAA,ChSaAA,KoutAA}. The rest of this introduction is devoted to a more detailed description of the contents of this paper. In Section~\ref{sec:Phi} we discuss our main character, the formal power series $\Phi(z)$ defined in \eqref{eq:Phidef}. While $\Phi(z)$ is transcendental over $\mathbb Q[z]$ (or, equivalently, over $\Z[z]$), it is easy to see that it is algebraic modulo powers of $2$. The focus in that section is on polynomial identities for $\Phi(z)$ modulo a given $2$-power which are of {\it minimal degree}. Then, in Section~\ref{sec:method}, we describe our method of expressing the generating function of a recursive sequence, when reduced modulo a given $2$-power, as a polynomial in $\Phi(z)$ with coefficients that are Laurent polynomials in $z$. The method relies in an essential way on the polynomial identities from Section~\ref{sec:Phi}. The problem how to extract the explicit value of a concrete coefficient in a polynomial expression in $\Phi(z)$ (such as \eqref{eq:Cat64}) modulo a given $2$-power is discussed in Section~\ref{sec:extr}, where we present an efficient algorithm performing this task. This algorithm is of theoretical value (minimal length relations between powers of $\Phi(z)$ such as the ones in Proposition~\ref{prop:minpol} are established by applying this algorithm to the powers of $\Phi(z)$; see also Appendix~\ref{appA}) as well as of practical significance, as is demonstrated by the derivations of Theorems~\ref{thm:1} and \ref{thm:Ga3}. As a first illustration of our method, we apply it to Catalan numbers, thereby significantly improving numerous earlier results in the literature; see Section~\ref{sec:Cat}. This is contrasted in Section~\ref{sec:nonex} with an example (concerning particular Fu\ss--Catalan numbers) where our method is bound to fail. The reason is spelled out in Theorem~\ref{thm:C2C7}, which, at the same time, also gives a new description for the parity pattern of the numbers of free subgroups of given index in the Hecke group $\mathfrak H(7)$. The subsequent sections contain several applications of our method to the problem of determining congruences modulo a given $2$-power for numbers of subgroups of Hecke groups $\mathfrak{H}(q)$ and their lifts \begin{equation} \label{eq:Heckelift} \Gamma_m(q) = C_{2m} \underset{C_m}{\ast} C_{qm} = \big\langle x,y\,\big\vert\, x^{2m} = y^{qm} = 1,\, x^2 = y^q\big\rangle, \quad m\ge1. \end{equation} Ubiquitous in these applications is --- explicitly or implicitly --- the intimate relation between subgroup numbers of a group $\Ga$ and numbers of permutation representations of $\Ga$, in the form of identities between the corresponding generating functions. This is directly visible in the folklore result \eqref{eq:Dey} (which is not only used in Sections~\ref{sec:SL2Z}, \ref{sec:Ga3}, and \ref{sec:H5}, but also lies behind the crucial differential equation \eqref{eq:S1diff} in Section~\ref{sec:PSL2Z}; cf.\ its derivation in \cite{GIR}), and also indirectly in Lemma~\ref{Lem:Gamma_m(q)FreeRec} via the $A$-invariants $A_\mu(\mathfrak H(q))$, see \cite[Sec.~2.2]{MuHecke}. In the cases relevant here, the numbers of permutation representations of $\Ga$ satisfy linear recurrences with polynomial coefficients --- to make these explicit may require the algorithmic machinery around the ``holonomic paradigm" (cf.\ \cite{ChyzAA,ChSaAA,KoutAA,MallAA,SaZiAA,WiZeAC,ZeilAN}), see Sections~\ref{sec:SL2Z} and \ref{sec:Ga3} for corresponding examples. Via the aforementioned generating function relation, such a recurrence can be translated into a Riccati-type differential equation for the generating function of the subgroup numbers that we are interested in. It is here, where our method comes in: it is tailor-made for being applied to formal power series $F(z)$ satisfying this type of differential equation, and it affords an algorithmic procedure to find a polynomial in $\Phi(z)$ which agrees, after reduction of the coefficients of $F(z)$ modulo a given power of $2$, with the power series $F(z)$. We start in Section~\ref{sec:free} with free subgroup numbers of lifts $\Ga_m(q)$, for primes $q\ge3$, where we prepare the ground for application of our method. More specifically, in Proposition~\ref{Prop:flambdaq2Part} we present a lower bound for the $2$-adic valuation of the number of free subgroups of index $n$ in $\Ga_m(q)$, where $q$ is a Fermat prime. In particular, this result implies that the sequence of free subgroup numbers under consideration is essentially zero modulo a given $2$-power in the case when $m$ is even. In Section~\ref{sec:free2}, we show that our method provides an algorithm for determining these numbers of free subgroups of $\Ga_m(3)$ modulo any given $2$-power in the case when $m$ is odd. The corresponding results (see Theorems~\ref{thm:freie-m} and \ref{thm:freie-m64}) go far beyond the previous result \cite[Theorem~1]{MuPu} on the behaviour of the number of free subgroups of $PSL_2(\mathbb Z)$ modulo~$16$. Our method provides as well an algorithm for determining the number of {\it all\/} subgroups of index $n$ in $PSL_2(\mathbb Z)$ modulo powers of $2$, as we demonstrate in Section~\ref{sec:PSL2Z}. Not only are we able to provide a new proof of Stothers' result \cite{Stothers} (which was stated in the second paragraph above), but our method leads as well to refinements modulo arbitrary powers of $2$ of Stothers' result and of the mod-$8$ results in \cite[Theorem~2]{MuPu} mentioned earlier; see Theorems~\ref{thm:Unterg} and \ref{thm:Untergr64}. For the homogeneous modular group $SL_2(\mathbb Z)$ (being isomorphic to the lift $\Ga_2(3)$) and for the lift $\Ga_3(3)$, however, our method from Section~\ref{sec:method} fails already for the modulus $8=2^3$. We overcome this obstacle by instead tuning our computations with the target of obtaining results modulo~$16=2^4$. Indeed, this leads to the determination of the number of subgroups of index~$n$ in $SL_2(\mathbb Z)$ and in $\Ga_3(3)$ modulo~8 (see Theorems~\ref{thm:Sl2Z8} and \ref{thm:Ga38}), but direct application of our method does not produce corresponding results modulo~16. Only by an {\it enhancement\/} of the method, which we outline in Appendix~\ref{appD}, we are able to produce descriptions of the subgroup numbers of $SL_2(\mathbb Z)$ modulo~16, see Theorem~\ref{thm:Sl2Z16}. For the subgroup numbers of $\Ga_3(3)$ even this enhancement fails, and this shows that the generating function for these subgroup numbers, when coefficients are reduced modulo~16, {\it cannot\/} be represented as a polynomial in $\Phi(z)$ with coefficients that are Laurent polynomials in $z$. Still, the results in Theorems~\ref{thm:Sl2Z8}, \ref{thm:Sl2Z16}, and \ref{thm:Ga38} go significantly beyond the earlier parity results \cite[Eq.~(6.3) with $\vert H\vert=1$]{KrMuAC} for these groups. This is explained in Sections~\ref{sec:SL2Z} and \ref{sec:Ga3}, with Section~\ref{sec:lift} preparing the ground by providing formulae for the number of permutation representations of $SL_2(\mathbb Z)$ as well as other lifts of $PSL_2(\mathbb Z)$. A further example where our method works for any $2$-power is the subject of Section~\ref{sec:Hecke}: there we apply the method to a functional equation (see \eqref{eq:2meq}) extending the functional equation for Catalan numbers (producing {\it Fu\ss--Catalan numbers}), and show that it works for any given $2$-power; see Theorem~\ref{thm:2mf}. In fact, we apply a variation of the method here, in that the basic series $\Phi(z)$ gets replaced by a slightly different series, which we denote by $\Phi_h(z)$ (see \eqref{eq:Phim}). If Theorem~\ref{thm:2mf} is combined with results from \cite{MuHecke}, then it turns out that our method provides as well an algorithm for determining the number of free subgroups of index $n$ in a Hecke group $\mathfrak H(q)$ and its lifts, where $q$ is a Fermat prime, modulo any given $2$-power; see Corollary~\ref{thm:freeHecke}. The same assertion holds as well for the problem of determining the number of subgroups of index $n$ in the Hecke group $\mathfrak H(5)$, again modulo any given $2$-power (see Theorems~\ref{thm:H5} and \ref{cor:H5} in Section~\ref{sec:H5}). We conjecture that the same is true for Hecke groups $\mathfrak H(q)$, with $q$ a Fermat prime (see Conjecture~\ref{conj:Hq}). The results of Sections~\ref{sec:Hecke} and \ref{sec:H5} discussed above largely generalise the parity results \cite[Cor.~A', respectively Theorem~B]{MuHecke} for subgroup numbers of Hecke groups, although our results are not independent, in the sense that we base our analyses on prior results from \cite{MuHecke}. \medskip Concluding the introduction, we remark that there is no principal obstacle to generalising our method to other basic series and moduli. For example, one may think of analysing the behaviour of recursive sequences modulo powers of any prime $p$ in terms of the obvious generalisation of $\Phi(z)$, i.e., the series $\sum _{n\ge0} ^{}z^{p^n}$. It is in fact not difficult to see that our results from Sections~\ref{sec:Cat} and \ref{sec:Hecke} for Fu\ss--Catalan numbers characterised by the functional equation \eqref{eq:2meq} for their generating function have rather straightforward analogues for Fu\ss--Catalan numbers whose generating function satisfies the functional equation \begin{equation} \label{eq:pmeq} zf^{p^h}(z)-f(z)+1=0. \end{equation} However we are not aware of any applications of this (or of variants) to congruence properties of subgroup numbers modulo powers of primes $p$ different from $2$. In fact, the known results (cf.\ \cite{MuPu2} or \cite[Theorem~3]{MuPu}) strongly point to the fact that the phenomena that appear modulo primes different from $2$ cannot be captured by series of the type $\sum _{n\ge0} ^{}z^{p^n}$. So, currently, we do not know of interesting applications in this direction, but we hope to be able to return to this circle of ideas in future publications. \begin{note} This paper is accompanied by several {\sl Mathematica} files and a {\sl Mathematica} notebook so that an interested reader is able to redo (most of) the computations that are presented in this article. Files and notebook are available at the article's website\break {\tt http://www.mat.univie.ac.at/\lower0.5ex\hbox{\~{}}kratt/artikel/modlifts.html}. \end{note} \section{The $2$-power series $\Phi(z)$} \label{sec:Phi} Here we consider the formal power series $\Phi(z)$ defined in \eqref{eq:Phidef}. This series is the principal character in the method for determining congruences of recursive sequences modulo $2$-powers, which we describe in Section~\ref{sec:method}. It is well known that this series is transcendental over $\mathbb Z[z]$ (this follows for instance from the density argument used in the proof of Lemma~\ref{lem:minpol} below). However, if the coefficients of $\Phi(z)$ are considered modulo a $2$-power $2^\ga$, then $\Phi(z)$ obeys a polynomial relation with coefficients that are polynomials in $z$. The focus of this section is on what may be said concerning such polynomial relations, and, in particular, about those of minimal length. \medskip Here and in the sequel, given power series (or Laurent series) $f(z)$ and $g(z)$, we write $$f(z)=g(z)~\text {modulo}~2^\ga$$ to mean that the coefficients of $z^i$ in $f(z)$ and $g(z)$ agree modulo~$2^\ga$ for all $i$. We say that a polynomial $A(z,t)$ in $z$ and $t$ is {\it minimal for the modulus $2^\ga$}, if it is monic (as a polynomial in $t$), has integral coefficients, satisfies $A(z,\Phi(z))=0$~modulo~$2^\ga$, and there is no monic polynomial $B(z,t)$ with integral coefficients of $t$-degree less than that of $A(z,t)$ with $B(z,\Phi(z))=0$~modulo~$2^\ga$. (Minimal polynomials are not unique; see Remark~\ref{rem:min}.) Furthermore, we let $v_2(\al)$ denote the $2$-adic valuation of the integer $\al$, that is, the maximal exponent $e$ such that $2^e$ divides $\al$. The lemma below provides a lower bound for the degree of a polynomial that is minimal for the modulus $2^\ga$. \begin{lemma} \label{lem:minpol} If $A(z,t)$ is minimal for the modulus $2^\ga$, then the degree $d$ of $A(z,t)$ in $t$ satisfies $v_2(d!)\ge\ga$. In particular, the series $\Phi(z)$ is transcendental over $\mathbb Z[z]$. \end{lemma} \begin{proof} We introduce the following {\it density function} with respect to a given modulus $2^\ga$ for a power series $f(z)$ in $z$: \begin{equation} \label{eq:density} D(f,2^\ga;n):=\big\vert\{e:2^{n-1}\le e<2^n\text { and } \coef{z^e}f(z)\not\equiv 0~\text {modulo}~2^\ga\}\big\vert, \quad \quad n=1,2,\dots, \end{equation} where $\coef{z^{e}}f(z)$ denotes the coefficient of $z^{e}$ in $f(z)$. Setting \begin{equation} \label{eq:Em} E_m(z):=\sum _{n_1>\dots>n_m\ge0} ^{}z^{2^{n_1}+2^{n_2}+\dots+2^{n_m}}, \end{equation} simple counting yields that \begin{equation} \label{eq:DEm} D(E_m,2^\ga;n)= \binom {n-1}{m-1}\sim \frac {1} {(m-1)!}n^{m-1}, \quad \quad \text {as }n\to\infty. \end{equation} (The modulus $2^\ga$ does not play a role here.) Furthermore, by considering the binary representations of possible exponents $e$ such that the coefficient of $z^e$ in $\Phi^m(z)$ does not vanish, we have \begin{equation} \label{eq:DPhi} D(\Phi^m,2^\ga;n)=\mathcal O\left(n^{m-1}\right), \quad \quad \text {as }n\to\infty. \end{equation} Indeed, by direct expansion, we see that \begin{equation} \label{eq:PhiE} \Phi^m(z)=m!\,E_m(z)+R_m(z), \end{equation} where all monomials $z^e$ which appear with non-vanishing coefficient in $R_m(z)$ have a binary expansion with at most $m-1$ digits $1$. Consequently, again by elementary counting, we have $$D(R_m,2^\ga;n)\le \binom {n-1}{m-2}+\binom {n-1}{m-3}+\dots+\binom {n-1}0,$$ and hence $D(R_m,2^\ga;n)=\mathcal O(n^{m-2})$ as $n\to\infty$. Let us, by way of contradiction, suppose that the degree $d$ of $A(z,t)$ satisfies $v_2(d!)<\ga$. Considering \eqref{eq:PhiE} with $m=d$, we see that $E_d(z)$ appears in $\Phi^d(z)$ with a non-zero coefficient modulo $2^\ga$. Furthermore, the other terms in $\Phi^d(z)$ (denoted by $R_d(z)$ in \eqref{eq:PhiE}) have a density function modulo $2^\ga$ which is asymptotically strictly smaller than the density function of $E_d(z)$. Consequently, if we remember \eqref{eq:DEm}, we have $$ D(\Phi^d,2^\ga;n)\sim \frac {d!} {(d-1)!}n^{d-1}=dn^{d-1}, \quad \quad \text {as }n\to\infty. $$ Moreover, by \eqref{eq:DPhi}, all powers $\Phi^m(z)$ with $m\dots>n_m\ge0} ^{}z^{2^{n_1}+2^{n_2}+\dots+2^{n_m}} $$ (with $m$ occurrences of $1$ in $H_{1,1,\dots,1}(z)$). Note that the above series is identical with the series which we earlier denoted by $E_m(z)$. Straightforward calculations yield that \begin{align} \label{eq:Phi2} \Phi^2(z)&=\Phi(z)+2H_{1,1}(z)-z,\\ \label{eq:Phi3} \Phi^3(z)&=-2\sum _{n\ge0} ^{}z^{3\cdot 2^n}+ 3(1-z)\Phi(z)+6H_{1,1}(z)+6H_{1,1,1}(z)-3z,\\ \notag \Phi^4(z)&=-12\sum _{n\ge0} ^{}z^{3\cdot 2^n} -8\sum _{n_1>n_2\ge0} ^{}z^{3\cdot 2^{n_1}+2^{n_2}} -8\sum _{n_1>n_2\ge0} ^{}z^{2^{n_1}+3\cdot 2^{n_2}} +(13-18z)\Phi(z)\\ \label{eq:Phi4} &\kern2cm +(30-12z)H_{1,1}(z)+36H_{1,1,1}(z)+24H_{1,1,1,1}(z)+5z^2-13z. \end{align} In particular, relation~\eqref{eq:Phi2}, together with Lemma~\ref{lem:minpol}, immediately implies the claims about minimal polynomials for the moduli $2$ and $4$. Moreover, a simple computation using \eqref{eq:Phi2}--\eqref{eq:Phi4} shows that \begin{equation} \label{eq:rel4} \Phi^4(z)+6\Phi^3(z)+(2z+3)\Phi^2(z)+(2z+6)\Phi(z)+2z+5z^2=0 \quad \text {modulo }8. \end{equation} Together with Lemma~\ref{lem:minpol}, this establishes the claims about minimal polynomials for the moduli $8$, $16$, $32$, and $64$. In order to prove the claim for the modulus $128$, one uses the expressions for $\Phi^i(z)$, $i=2,3,\dots,8$, given above and in Appendix~\ref{appA}. \end{proof} \begin{remarknu}\label{rem:min} Minimal polynomials are highly non-unique: for example, the polynomial $$ (t^2+t+z)^2+2(t^2+t+z) $$ is obviously also a minimal polynomial for the modulus $4$. \end{remarknu} Based on the observations in Proposition~\ref{prop:minpol} and Lemma~\ref{lem:minpol}, we propose the following conjecture. \begin{conjecture} \label{conj:1} The degree of a minimal polynomial for the modulus $2^\ga$, $\ga\ge1$, is the least $d$ such that $v_2(d!)\ge\ga$. \end{conjecture} \begin{remarknu} \label{rem:1} (1) Given the binary expansion of $d$, say $$d=d_0+d_1\cdot 2+d_2\cdot 4+\cdots+d_r\cdot 2^r, \quad 0\le \ga_i\le1,$$ by the well-known formula of Legendre \cite[p.~10]{LegeAA}, we have \begin{align}\notag v_2(d!)&=\sum _{\ell=1} ^{\infty}\fl{\frac {d} {2^\ell}}= \sum _{\ell=1} ^{\infty}\fl{\sum _{i=0} ^{r}d_i 2^{i-\ell}}= \sum _{\ell=1} ^{\infty}\sum _{i=\ell} ^{r}d_i 2^{i-\ell}\\ \label{eq:Leg} &= \sum _{i=1} ^{r}\sum _{\ell=1} ^{i}d_i 2^{i-\ell}= \sum _{i=1} ^{r}d_i\left(2^{i}-1\right)= d-s(d), \end{align} where $s(d)$ denotes the sum of digits of $d$ in its binary expansion. Consequently, an equivalent way of phrasing Conjecture~\ref{conj:1} is to say that the degree of a minimal polynomial for the modulus $2^\ga$ is the least $d$ with $d-s(d)\ge\ga$. \medskip (2) We claim that, in order to establish Conjecture~\ref{conj:1}, it suffices to prove the conjecture for $\ga=2^{\de}-1$, $\de=1,2,\dots$. If we take into account Lemma~\ref{lem:minpol} plus the above remark, this means that it is sufficient to prove that, for each $\de\ge1$, there is a polynomial $A_\de(z,t)$ of degree $2^{\de}$ such that \begin{equation} \label{eq:min2ga} A_\de(z,\Phi(z))=0\quad \text {modulo }2^{2^\de-1}. \end{equation} For, arguing by induction, let us suppose that we have already constructed $A_1(z,t),\break A_2(z,t), \dots,A_m(z,t)$ satisfying \eqref{eq:min2ga}. Let $$\al=\al_1\cdot 2+\al_2\cdot 4+\cdots+\al_m\cdot 2^m, \quad 0\le \al_i\le1,$$ be the binary expansion of the even positive integer $\al$. In this situation, we have \begin{equation} \label{eq:betaind} \prod _{\de=1} ^{m}A_{\de}^{\al_\de}(z,\Phi(z))=0\quad \text {modulo } \prod _{\de=1} ^{m}2^{\al_\de(2^\de-1)}= \prod _{\de=0} ^{m}2^{\al_\de(2^\de-1)}= 2^{\al-s(\al)}. \end{equation} On the other hand, the degree of the left-hand side of \eqref{eq:betaind} as a polynomial in $\Phi(z)$ is $\sum _{\de=1} ^{m}\al_\de 2^\de=\al$. Let us put these observations together. In view of \eqref{eq:Leg}, Lemma~\ref{lem:minpol} says that the degree of a minimal polynomial for the modulus $2^\ga$ cannot be smaller than the least integer, $d^{(\ga)}$ say, for which $d^{(\ga)}-s(d^{(\ga)})\ge\ga$. (We remark that $d^{(\ga)}$ must be automatically even.) If we take into account that the quantity $\al-s(\al)$, as a function in $\al$, is weakly monotone increasing in $\al$, then \eqref{eq:betaind} tells us that, as long as $d^{(\ga)}\le 2+4+\dots+2^m=2^{m+1}-2$, we have found a monic polynomial of degree $d^{(\ga)}$, $B_\ga(z,t)$ say, for which $B_\ga(z,\Phi(z))=0$ modulo~$2^\ga$, namely the left-hand side of \eqref{eq:betaind} with $\al$ replaced by $d^{(\ga)}$, to wit $$ B_\ga(z,t)=\prod _{\de=1} ^{m}A_{\de}^{d^{(\ga)}_\de}(z,t), $$ where $d^{(\ga)}=d^{(\ga)}_1\cdot 2+d^{(\ga)}_2\cdot 4+\cdots+d^{(\ga)}_m\cdot 2^m$ is the binary expansion of $d^{(\ga)}$. Hence, it must necessarily be a minimal polynomial for the modulus $2^\ga$. Since $(2^{m+1}-2)-s(2^{m+1}-2)=2^{m+1}-2-m$, we have thus found minimal polynomials for all moduli $2^\ga$ with $\ga\le 2^{m+1}-m-2$. Now we should note that the quantity $\al-s(\al)$ makes a jump from $2^{m+1}-m-2$ to $2^{m+1}-1$ when we move from $\al=2^{m+1}-2$ to $\al=2^{m+1}$ (the reader should recall that it suffices to consider even $\al$). If we take $A_m^2(z,t)$, which has degree $2\cdot 2^m=2^{m+1}$, then, by \eqref{eq:min2ga}, we also have a minimal polynomial for the modulus $\left(2^{2^m-1}\right)^2=2^{2^{m+1}-2}$ and, in view of the preceding remark, as well for all moduli $2^\ga$ with $\ga$ between $2^{m+1}-m-1$ and $2^{m+1}-2$. So, indeed, the first modulus for which we do not have a minimal polynomial is the modulus $2^{2^{m+1}-1}$. This is the role which $A_{m+1}(z,t)$ (see \eqref{eq:min2ga} with $m+1$ in place of $\de$) would have to play. \smallskip The arguments above show at the same time that, supposing that we have already constructed $A_1(z,t),A_2(z,t),\dots,A_m(z,t)$, the polynomial $A^2_m(z,t)$ is a very close ``approximation" to the polynomial $A_{m+1}(z,t)$ that we are actually looking for next, which is only ``off" by a factor of $2$. In practice, one can recursively compute polynomials $A_\de(z,t)$ satisfying \eqref{eq:min2ga} by following the procedure outlined in the next-to-last paragraph before Lemma~\ref{lem:aiodd} in the next section. It is these computations (part of which are reported in Proposition~\ref{prop:minpol}) which have led us to believe in the truth of Conjecture~\ref{conj:1}. \end{remarknu} \section{Coefficient extraction from powers of $\Phi(z)$} \label{sec:extr} In the next section we are going to describe a method for expressing formal power series satisfying certain differential equations, after the coefficients of the series have been reduced modulo $2^k$, as polynomials in the $2$-power series $\Phi(z)$ (which has been discussed in the previous section; for the definition see \eqref{eq:Phidef}), the coefficients being Laurent polynomials in $z$. Such a method would be without value if we could not, at the same time, provide a procedure for extracting coefficients from powers of $\Phi(z)$. The description of such a procedure is the topic of this section. Clearly, a brute force expansion of a power $\Phi^K(z)$, where $K$ is a given positive integer, yields \begin{equation} \label{eq:Phipot} \Phi^K(z)=\sum _{r=1} ^{K} \underset{a_1+\dots+a_r=K}{\sum _{a_1,\dots,a_r\ge1} ^{}}\frac {K!} {a_1!\,a_2!\cdots a_r!}H_{a_1,a_2,\dots,a_r}(z), \end{equation} where $$ H_{a_1,a_2,\dots,a_r}(z):=\sum_{n_1>n_2>\dots>n_r\ge0} z^{a_12^{n_1}+a_22^{n_2}+\dots+a_r2^{n_r}}. $$ The expansion \eqref{eq:Phipot} is not (yet) suited for our purpose, since, when $a_1,a_2,\dots,a_r$ vary over all possible choices such that their sum is $K$, the series $H_{a_1,a_2,\dots,a_r}(z)$ are {\it not\/} linearly independent over the ring $\Z[z,z^{-1}]$ of Laurent polynomials in $z$ over the integers\footnote{The same is true for an arbitrary ring in place of the ring $\Z$ of integers.}, and, second, coefficient extraction from a series $H_{a_1,a_2,\dots,a_r}(z)$ can be a hairy task if some of the $a_i$'s are even. However, we shall show (see Corollary~\ref{lem:Hind}) that, if we restrict to {\it odd\/} $a_i$'s, then the corresponding series $H_{a_1,a_2,\dots,a_r}(z)$, together with the (trivial) series $1$, {\it are} linearly independent over $\Z[z,z^{-1}]$, and there is an efficient algorithm to express all other series $H_{b_1,b_2,\dots,b_s}(z)$, where we do {\it not\/} make any restriction on the $b_i$'s, as a linear combination over $\Z[z,z^{-1}]$ of $1$ and the former series (see Lemma~\ref{lem:Hbi}). Since coefficient extraction from a series $H_{a_1,a_2,\dots,a_r}(z)$ with all $a_i$'s odd is straightforward (see Remark~\ref{rem:eff}), this solves the problem of coefficient extraction from powers of $\Phi(z)$. As a side result, the procedure which we described in the previous paragraph, and which will be substantiated below, provides all the means for determining minimal polynomials in the sense of Section~\ref{sec:Phi}: as explained in Item~(2) of Remark~\ref{rem:1} at the end of that section, it suffices to find a minimal polynomial for the modulus $2^{2^\de-1}$, $\de=1,2,\dots$. For doing this, we would take a minimal polynomial $A_{\de-1}(z,t)$ for the modulus $2^{2^{\de-1}-1}$, expand the square $A^2_{\de-1}(z,t)$, and replace each coefficient $c_{\al,\be}$ of a monomial $z^\alpha t^\beta$ in $A^2_{\de-1}(z,t)$ by $c_{\al,\be}+2^{2^{\de}-2}x_{\al,\be}$, where $x_{\al,\be}$ is a variable, thereby obtaining a modified polynomial, $B_{\de-1}(z,t)$ say. Now we would substitute $\Phi(z)$ for $t$, so that we obtain $B_{\de-1}(z,\Phi(z))$. Here, we express powers of $\Phi(z)$ in terms of the series $H_{a_1,a_2,\dots,a_r}(z)$ with all $a_i$'s being odd, and collect terms. By reading the coefficients of $z^\ga H_{a_1,a_2,\dots,a_r}(z)$ in this expansion of $B_{\de-1}(z,\Phi(z))$ and equating them to zero modulo $2^{2^\de-1}$, we produce a system of linear equations modulo $2^{2^\de-1}$ in the unknowns $x_{\al,\be}$. By the definition of $A_{\de-1}(z,t)$, after division by $2^{2^\de-2}$, this system reduces to a system modulo $2$, that is, to a linear system of equations over the field with two elements. A priori, this system need not have a solution, but experience seems to indicate that it always does; see Conjecture~\ref{conj:1}. \medskip We start with an auxiliary result pertaining to the uniqueness of representations of integers as sums of powers of $2$ with multiplicities, tailor-made for application to the series $H_{a_1,a_2,\dots,a_r}(z)$. \begin{lemma} \label{lem:aiodd} Let $d,r,s$ be positive integers with $r\ge s,$ $c$ an integer with $\vert c\vert\le d,$ and let $a_1,a_2,\dots,a_r$ respectively $b_1,b_2,\dots,b_s$ be two sequences of odd integers, with $1\le a_i\le d$ for $1\le i\le r,$ and $1\le b_i\le d$ for $1\le i\le s$. If \begin{equation} \label{eq:a2b2} a_12^{2rd}+a_22^{2(r-1)d}+\dots+a_r2^{2d}= b_12^{n_1}+b_22^{n_2}+\dots+b_s2^{n_s}+c \end{equation} for integers $n_1,n_2,\dots,n_s$ with $n_1>n_2>\dots>n_s\ge0,$ then $r=s,$ $c=0,$ $a_i=b_i,$ and $n_i=2d(r+1-i)$ for $i=1,2,\dots,r$. \end{lemma} \begin{proof} We use induction on $r$. First, let $r=1$. Then $s=1$ as well, and \eqref{eq:a2b2} becomes \begin{equation} \label{eq:a2b2A} a_12^{2d}=b_12^{n_1}+c. \end{equation} If $n_1>2d$, then the above equation, together with the assumption that $a_1$ is odd, implies $$ 2^{2d}\equiv c\quad \text {modulo }2^{2d+1}. $$ However, by assumption, we have $\vert c\vert\le d<2^{2d}$, which is absurd. If $dn_2>\dots>n_r\ge0$, then necessarily $n_r=v_2(M)$, $n_{r-1}=v_2(M-a_r2^{n_r})$, etc. The term $z^M$ appears in $H_{a_1,a_2,\dots,a_{r}}(z)$ if, and only if, the above process terminates after {\it exactly} $r$ steps. This means, that, with $n_r,n_{r-1},\dots,n_1$ constructed as above, we have $$ M-\left(a_s2^{n_s}+\dots+a_{r-1}2^{n_{r-1}}+a_r2^{n_r}\right)>0 $$ for $s>1$, and $$ M-\left(a_12^{n_1}+\dots+a_{r-1}2^{n_{r-1}}+a_r2^{n_r}\right)=0. $$ It should be noted that, given $a_1,a_2,\dots,a_r$, this procedure of coefficient extraction needs at most $O(\log M)$ operations, that is, its computational complexity is linear. \end{remarknu} Our next goal is to show that a series $H_{b_1,b_2,\dots,b_s}(z)$ can be expressed as a linear combination over $\Z[z,z^{-1}]$ of the series $1$ and the series $H_{a_1,a_2,\dots,a_r}(z)$, where all $a_i$'s are odd. In doing this, we are forced to consider the more general series $$ H_{b_1,b_2,\dots,b_s}^{\be_1,\be_2,\dots,\be_s}(z):= \sum _{n_1+\be_1>n_2+\be_2>\dots>n_s+\be_s\ge0} ^{} z^{b_12^{n_1}+b_22^{n_2}+\dots+b_s2^{n_s}}, $$ where, as before, $b_1,b_2,\dots,b_s$ are positive integers, and $\be_1,\be_2,\dots,\be_s$ are integers. \begin{lemma} \label{lem:Hbi} For positive integers $b_1,b_2,\dots,b_s$ and integers $\be_1,\be_2,\dots,\be_s,$ the series\break $H_{b_1,b_2,\dots,b_s}^{\be_1,\be_2,\dots,\be_s}(z)$ can be expressed as a linear combination over $\Z[z^{1/2^e}]$ {\em(}for a suitable integer $e${\em)} of the series $1$ and series of the form $H_{a_1,a_2,\dots,a_r}(z),$ where all $a_i$'s are odd. Moreover, in the above expansion of the series $H_{b_1,b_2,\dots,b_s}(z)= H_{b_1,b_2,\dots,b_s}^{0,0,\dots,0}(z)$ we have $e=0$; that is, in that case all coefficients are in $\Z[z]$. \end{lemma} \begin{proof} We describe an algorithmic procedure for expressing $H_{b_1,b_2,\dots,b_s}^{\be_1,\be_2,\dots,\be_s}(z)$ in terms of series $H_{a_1,a_2,\dots,a_r}^{\ga_1,\ga_2,\dots,\ga_r}(z)$, where either $r\dots> n_{s-1}+\be_{s-1}-\be_s+e_s> n_s+e_s\ge -\be_s+e_s} ^{} z^{b_12^{n_1}+b_22^{n_2}+\dots+b_{s-1}2^{n_{s-1}}+b'_s2^{n_s+e_s}}. \end{multline*} In the above sum on the right-hand side, let $n'_s=n_s+e_s$ be a new summation index. Then, for $e_s\le\be_s$, one sees that \begin{multline} \label{eq:Rek1} H_{b_1,b_2,\dots,b_s}^{\be_1,\be_2,\dots,\be_s}(z)= H_{b_1,b_2,\dots,b_{s-1},b'_s} ^{\be_1-\be_s+e_s,\be_2-\be_s+e_s,\dots, \be_{s-1}-\be_s+e_s,0}(z)\\[2mm] +\sum _{k=1} ^{\be_s-e_s}z^{b'_s2^{-k}} H_{b_1,b_2,\dots,b_{s-1}} ^{\be_1-\be_s+e_s+k-1,\be_2-\be_s+e_s+k-1,\dots, \be_{s-1}-\be_s+e_s+k-1}(z). \end{multline} On the other hand, for $e_s\ge\be_s$, one has \begin{multline} \label{eq:Rek2} H_{b_1,b_2,\dots,b_s}^{\be_1,\be_2,\dots,\be_s}(z)= H_{b_1,b_2,\dots,b_{s-1},b'_s} ^{\be_1-\be_s+e_s,\be_2-\be_s+e_s,\dots, \be_{s-1}-\be_s+e_s,0}(z)\\[2mm] -\sum _{k=0} ^{e_s-\be_s-1}z^{b'_s2^{k}} H_{b_1,b_2,\dots,b_{s-1}} ^{\be_1-\be_s+e_s-k-1,\be_2-\be_s+e_s-k-1,\dots, \be_{s-1}-\be_s+e_s-k-1}(z). \end{multline} Now consider $$ H_{b_1,\dots,b_h,b_{h+1},\dots,b_s} ^{\be_1,\dots,\be_h,0,\dots,0}(z), $$ where $1\le hn_{h+1}>\dots>n_s\ge0} {\sum _{n_1+\be_1-\be_h+e_h>\dots> n_{h-1}+\be_{h-1}-\be_h+e_h> n_h+e_h} ^{}} z^{b_12^{n_1}+\dots+b_{h-1}2^{n_{h-1}}+b'_h2^{n_h+e_h}+ b_{h+1}2^{n_{h+1}}+\dots+b_s2^{n_s}}. \end{multline*} In the above sum on the right-hand side, let $n'_h=n_h+e_h$ be a new summation index. Then, for $e_h\le\be_h$, one sees that \begin{multline} \label{eq:Rek3} H_{b_1,\dots,b_h,b_{h+1},\dots,b_s} ^{\be_1,\dots,\be_h,0,\dots,0}(z)= H_{b_1,\dots,b_{h-1},b'_h,b_{h+1},\dots,b_s} ^{\be_1-\be_h+e_h,\dots, \be_{h-1}-\be_h+e_h,0,0,\dots,0}(z)\\[2mm] +\sum _{k=0} ^{\be_h-e_h-1} H_{b_1,\dots,b_{h-1},b'_h+b_{h+1}2^k,b_{h+2},\dots,b_s} ^{\be_1-\be_h+e_h+k,\dots, \be_{h-1}-\be_h+e_h+k,k,0,\dots,0}(z). \end{multline} On the other hand, for $e_h\ge\be_h$, one has \begin{multline} \label{eq:Rek4} H_{b_1,\dots,b_h,b_{h+1},\dots,b_s} ^{\be_1,\dots,\be_h,0,\dots,0}(z)= H_{b_1,\dots,b_{h-1},b'_h,b_{h+1},\dots,b_s} ^{\be_1-\be_h+e_h,\dots, \be_{h-1}-\be_h+e_h,0,0,\dots,0}(z)\\[2mm] -\sum _{k=1} ^{e_h-\be_h} H_{b_1,\dots,b_{h-1},b'_h2^k+b_{h+1},b_{h+2},\dots,b_s} ^{\be_1-\be_h+e_h-k,\dots, \be_{h-1}-\be_h+e_h-k,0,0,\dots,0}(z). \end{multline} It is clear that, if we recursively apply \eqref{eq:Rek1}--\eqref{eq:Rek4} to a given series $H_{b_1,b_2,\dots,b_s}^{\be_1,\be_2,\dots,\be_s}(z)$, and use $H_\emptyset^\emptyset(z)=1$ as an initial condition, we will eventually arrive at a linear combination of $1$ and series $H_{a_1,a_2,\dots,a_r}^{0,0,\dots,0}(z)= H_{a_1,a_2,\dots,a_r}(z)$ with all $a_i$'s being odd, where the coefficients are polynomials in $z^{1/2^e}$ for a suitable $e$. (Potential fractional exponents come from the relation \eqref{eq:Rek1}.) This proves the first assertion of the lemma. Now let us consider the case where all the $\be_i$'s are zero. Suppose that we have an expansion as described in the first part of the lemma for $H_{b_1,b_2,\dots,b_s}(z)$, \begin{equation} \label{eq:be=0} H_{b_1,b_2,\dots,b_s}(z)= {\sum _{\mathbf a} ^{}} c(\mathbf a) z^{e(\mathbf a)} H_{\mathbf a}(z), \end{equation} where the sum is taken over all finite tuples $\mathbf a=(a_1,a_2,\dots)$ with all $a_i$'s being odd, and where only finitely many coefficients $c(\mathbf a)$ are non-zero. We also allow the tuple $\mathbf a$ to be the empty tuple $()$ and make the convention that $H_{()}(z)=1$, so that the series $1$ is as well included in the linear combination on the right-hand side of \eqref{eq:be=0}. Let us now consider exponents $e(\mathbf a)$ that are not integral. Let $\epsilon$ be a real number strictly between $0$ and $1$, and concentrate on exponents $e(\mathbf a)$ with fractional part $\epsilon$; in symbols $\{e(\mathbf a)\}=\epsilon$. Then we isolate these exponents $e(\mathbf a)$ in the relation \eqref{eq:be=0}, and since there are no fractional exponents on the left-hand side, we obtain $$ 0= {{\sum _{\{e(\mathbf a)\}=\epsilon} ^{}}} c(\mathbf a) z^{e(\mathbf a)} H_{\mathbf a}(z). $$ After dividing both sides through by $z^\epsilon$, an application of Corollary~\ref{lem:Hind} shows that $c(\mathbf a)=0$ for all $\mathbf a$ with $\{e(\mathbf a)\}=\epsilon$. Thus, all exponents $e(\mathbf a)$ actually occurring in \eqref{eq:be=0} with non-zero coefficients $c(\mathbf a)$ are in fact integral. This completes the proof of the lemma. \end{proof} Computer computations suggest that, if we restrict our attention to the series\break $H_{b_1,b_2,\dots,b_s}(z)$, which are the ones that we are actually interested in, there is a strengthening of Lemma~\ref{lem:Hbi} (see also Appendix~\ref{appA}). \begin{conjecture} \label{conj:H} For any positive integers $b_1,b_2,\dots,b_s,$ the series $H_{b_1,b_2,\dots,b_s}(z)$ can be expressed as a linear combination over $\Z[z,z^{-1}]$ of the series $1$ and series of the form $H_{a_1,a_2,\dots,a_r}(z),$ where all $a_i$'s are odd, $r\le s,$ and $a_1+a_2+\dots+a_r\le b_1+b_2+\dots+b_s$. \end{conjecture} To conclude this section, let us provide an illustration of the above discussion. We set ourselves the task of determining the coefficient of $z^{1099511640192}$ in $\Phi^5(z)$. In order to accomplish this task, we first express $\Phi^5(z)$ in terms of series $H_{a_1,\dots,a_r}(z)$ with all $a_i$'s being odd. This is done by means of the expansion \eqref{eq:Phipot} and the algorithm described in the proof of Lemma~\ref{lem:Hbi}. The resulting expansion is displayed in Appendix~\ref{appA}. Now we have to answer the question, in which of the series $H_{a_1,\dots,a_r}(z)$ that appear in this expansion of $\Phi^5(z)$ do we find the monomial $z^{1099511640192}$. Using the algorithm described in Remark~\ref{rem:eff}, we see that {\allowdisplaybreaks \begin{align*} 1099511640192&=5\cdot 2^7+1099511639552,\\ &=3\cdot 2^{13} +2^{12} +2^7+1099511611392,\\ &=2^{40} +3\cdot 2^{12} +2^7,\\ &=2^9 +2^8 +3\cdot 2^7+1099511639040,\\ &=3\cdot 2^{12} +2^7+1099511627776,\\ &=2^8 +3\cdot 2^7+1099511639552,\\ &=2^{40} +2^{13} +2^{12} +2^7,\\ &=1+3\cdot 2^0+1099511640188,\\ &=3\cdot 2^7+1099511639808,\\ &=1+2^2+2^1+2^0+1099511640184,\\ &=2^{13} +2^{12} +2^7+1099511627776,\\ &=1+2^1+2^0+1099511640188,\\ &=2^{12} +2^7+1099511635968,\\ &=2+2^1+1099511640188,\\ &=1+2^0+1099511640190,\\ &=2^7+1099511640064. \end{align*}}% Here, the third line shows that $z^{1099511640192}$ appears in $H_{1,3,1}(z)$, and the seventh line shows that it appears in $H_{1,1,1,1}(z)$ (thereby making it impossible to appear in $H_{1,1,1,1,1}(z)$), while the remaining lines show that it does not appear in any other term in the expansion of $\Phi^5(z)$ displayed in Appendix~\ref{appA}. Hence, by taking into account the coefficients with which the series $H_{1,3,1}(z)$ and $H_{1,1,1,1}(z)$ appear in this expansion, the coefficient of $z^{1099511640192}$ in $\Phi^5(z)$ is seen to equal $-40+240=200$. \section{The method} \label{sec:method} We consider a (formal) differential equation \begin{equation} \label{eq:diffeq} \mathcal P(z;F(z),F'(z),F''(z),\dots,F^{(s)}(z))=0, \end{equation} where $\mathcal P$ is a polynomial with integer coefficients, which has a power series solution $F(z)$ with integer coefficients. In this situation, we propose the following algorithmic approach to determining the series $F(z)$ modulo a $2$-power $2^{3\cdot 2^\al}$, for some positive integer $\al$. We make the Ansatz \begin{equation} \label{eq:Ansatz} F(z)=\sum _{i=0} ^{2^{\al+2}-1}a_i(z)\Phi^i(z)\quad \text {modulo }2^{3\cdot 2^\al}, \end{equation} with $\Phi(z)$ as given in \eqref{eq:Phidef}, and where the $a_i(z)$'s are (at this point) undetermined Laurent polynomials in $z$. Now we substitute \eqref{eq:Ansatz} into \eqref{eq:diffeq}, and we shall gradually determine approximations $a_{i,\be}(z)$ to $a_i(z)$ such that \eqref{eq:diffeq} holds modulo $2^\be$, for $\be=1,2,\dots,3\cdot 2^\al$. To start the procedure, we consider the differential equation \eqref{eq:diffeq} modulo $2$, with \begin{equation} \label{eq:Ansatz1} F(z)=\sum _{i=0} ^{2^{\al+2}-1}a_{i,1}(z)\Phi^i(z)\quad \text {modulo }2. \end{equation} Using the elementary fact that $\Phi'(z)=1$ modulo $2$, we see that the left-hand side of \eqref{eq:diffeq} is a polynomial in $\Phi(z)$ with coefficients that are Laurent polynomials in $z$. We reduce powers $\Phi^k(z)$ with $k\ge2^{\al+2}$ using the relation (which is implied by the minimal polynomial for the modulus~$8$ given in Proposition~\ref{prop:minpol})\,\footnote{Actually, if we would like to obtain an optimal result, we should use the relation implied by a minimal polynomial for the modulus $2^{3\cdot 2^\al}$ in the sense of Section~\ref{sec:Phi}. But since we have no general formula available for such a minimal polynomial (cf.\ Item (2) of Remark~\ref{rem:1} in that section), and since we wish to prove results for arbitrary moduli, choosing instead powers of a minimal polynomial for the modulus $8$ is the best compromise. In principle, it may happen that there exists a polynomial in $\Phi(z)$ with coefficients that are Laurent polynomials in $z$, which is identical with $F(z)$ after reduction of its coefficients modulo $2^{3\cdot 2^\al}$, but the Ansatz \eqref{eq:Ansatz} combined with the reduction \eqref{eq:PhiRel} fails because it is too restrictive. %However, %it turns out that --- at least in all the cases that we treat --- this %obstruction does not occur. We are not aware of a concrete example where this obstruction occurs. The subgroup numbers of $SL_2(\Z)$ %??and of $\Ga_3(3)$ (which we treat modulo~$8$ in Section~\ref{sec:SL2Z} %??and \ref{sec:Ga3} by the method described here, and modulo~$16$ by an enhancement of the method outlined in Appendix~\ref{appD}) are a potential candidate when considered modulo $2^{3\cdot 2^\al}$ for $\al\ge1$. On the other hand, once we are successful using this (potentially problematic) Ansatz, then the result can easily be converted into an optimal one by further reducing the polynomial thus obtained, using the relation implied by a minimal polynomial for the modulus $2^{3\cdot 2^\al}$.} \begin{equation} \label{eq:PhiRel} \big(\Phi^4(z)+6\Phi^3(z)+(2z+3)\Phi^2(z)+(2z+6)\Phi(z)+2z+5z^2\big) ^{2^\al}=0\quad \text {modulo }2^{3\cdot 2^\al}. \end{equation} Since, at this point, we are only interested in finding a solution to \eqref{eq:diffeq} modulo~$2$, the above relation simplifies to \begin{equation} \label{eq:PhiRel2} \Phi^{2^{\al+2}}(z)+\Phi^{2^{\al+1}}(z)+z^{2^{\al+1}}=0\quad \text{modulo }2. \end{equation} Now we compare coefficients of powers $\Phi^k(z)$, $k=0,1,\dots,2^{\al+2}-1$ (see Remark~\ref{rem:comp}). This yields a system of $2^{\al+2}$ (differential) equations (modulo~$2$) for the unknown Laurent polynomials $a_{i,1}(z)$, $i=0,1,\dots,2^{\al+2}-1$, which may or may not have a solution. Provided we have already found Laurent polynomials $a_{i,\be}(z)$, $i=0,1,\dots,2^{\al+2}-1$, for some $\be$ with $1\le \be\le 3\cdot 2^{\al}-1$, such that \begin{equation} \label{eq:Ansatz2} \sum _{i=0} ^{2^{\al+2}-1}a_{i,\be}(z)\Phi^i(z) \end{equation} solves \eqref{eq:diffeq} modulo~$2^\be$, we put \begin{equation} \label{eq:Ansatz2a} a_{i,\be+1}(z):=a_{i,\be}(z)+2^{\be}b_{i,\be+1}(z),\quad i=0,1,\dots,2^{\al+2}-1, \end{equation} where the $b_{i,\be+1}(z)$'s are (at this point) undetermined Laurent polynomials in $z$. Next we substitute \begin{equation} \label{eq:Ansatz2b} \sum _{i=0} ^{2^{\al+2}-1}a_{i,\be+1}(z)\Phi^i(z) \end{equation} instead of $F(z)$ in \eqref{eq:diffeq}. Using the fact that $\Phi'(z)=\sum _{n=0} ^{\be}2^nz^{2^n-1}$ modulo~$2^{\be+1}$, we expand the left-hand side as a polynomial in $\Phi(z)$ (with coefficients being Laurent polynomials in $z$), we apply again the reduction using relation \eqref{eq:PhiRel}, we compare coefficients of powers $\Phi^k(z)$, $k=0,1,\dots,2^{\al+2}-1$ (again, see Remark~\ref{rem:comp}), and, as a result, we obtain a system of $2^{\al+2}$ (differential) equations (modulo~$2^{\be+1}$) for the unknown Laurent polynomials $b_{i,\be+1}(z)$, $i=0,1,\dots,2^{\al+2}-1$, which may or may not have a solution. If we manage to push this procedure through until $\be=3\cdot 2^\al-1$, then, setting $a_i(z)=a_{i,3\cdot 2^\al}(z)$, $i=0,1,\dots,2^{\al+2}-1$, the right-hand side of \eqref{eq:Ansatz} is a solution to \eqref{eq:diffeq} modulo~$2^{3\cdot 2^\al}$, as required. \begin{remarknu} \label{rem:comp} As the reader will have noticed, each comparison of coefficients of powers of $\Phi(z)$ is based on the ``hope" that, if a polynomial in $\Phi(z)$ is zero modulo a $2$-power $2^\be$ (as a formal Laurent series), then already all coefficients of powers of $\Phi(z)$ in this polynomial vanish modulo $2^\be$. However, this implication is false in general (see Lemma~\ref{lem:Null16} below for the case of modulus $2^4=16$). It may thus happen that the method described in this section fails to find a solution modulo $2^\be$ to a given differential equation in the form of a polynomial in $\Phi(z)$ with coefficients that are Laurent polynomials in $z$ over the integers, while such a solution does in fact exist. As a matter of fact, this situation occurs in the analysis modulo~$16$ of the subgroup numbers of $SL_2(\Z)$, see %??Remarks~\ref{rem:2}, \ref{rem:Ga3}, and Theorem~\ref{thm:Sl2Z16}. In Appendix~\ref{appD}, we outline an enhancement of the method, which (at least in principle; Appendix~\ref{appD} treats only the case of the modulus~$16$ explicitly) allows us to decide whether or not a solution modulo a given power in terms of a polynomial in $\Phi(z)$ with coefficients that are Laurent polynomials in $z$ over the integers exists, and, if so, to explicitly find such a solution. \end{remarknu} It is not difficult to see that performing the iterative step \eqref{eq:Ansatz2a} amounts to solving a system of linear differential equations in the unknown functions $b_{i,\be+1}(z)$ modulo~$2$, where all of them are Laurent polynomials in $z$, and where only first derivatives of the $b_{i,\be+1}(z)$'s occur. Solving such a system is equivalent to solving an ordinary system of linear equations, as is shown by the lemma below. Given a Laurent polynomial $p(z)$ over the integers, we write $p^{(o)}(z)$ for the odd part $\frac {1} {2}(p(z)-p(-z))$ and $p^{(e)}(z)$ for the even part $\frac {1} {2}(p(z)+p(-z))$ of $p(z)$, respectively. \begin{lemma} \label{lem:2x2diff} Let $c_{i,j}(z)$ and $d_{i,j}(z),$ $1\le i,j\le N,$ and $r_i(z),$ $1\le i\le N,$ be given Laurent polynomials in $z$ with integer coefficients. Then the system of differential equations \begin{equation} \label{eq:2x2diff} \sum _{j=1} ^{N}c_{i,j}(z)f_j(z)+ \sum _{j=1} ^{N}d_{i,j}(z)f'_j(z)=r_i(z)\quad \text {\em modulo }2, \quad \quad 1\le i\le N, \end{equation} has solutions $f_j(z),$ $1\le j\le N,$ that are Laurent polynomials in $z$ over the integers if, and only if, the system of\/ {\em linear} equations \begin{align} \notag \sum _{j=1} ^{N}c^{(e)}_{i,j}(z)f^{(1)}_j(z)+ \sum _{j=1} ^{N}c^{(o)}_{i,j}(z)f^{(2)}_j(z)+ \sum _{j=1} ^{N}z^{-1}d^{(1)}_{i,j}(z)f^{(2)}_j(z)&=r^{(e)}_i(z)\quad \text {\em modulo }2, \\[2mm] \notag \sum _{j=1} ^{N}c^{(o)}_{i,j}(z)f^{(1)}_j(z)+ \sum _{j=1} ^{N}c^{(e)}_{i,j}(z)f^{(2)}_j(z)+ \sum _{j=1} ^{N}z^{-1}d^{(o)}_{i,j}(z)f^{(2)}_j(z)&=r^{(o)}_i(z)\quad \text {\em modulo }2,\\ &\kern3cm 1\le i\le N, \label{eq:4x4} \end{align} has a solution in Laurent polynomials $f_j^{(1)}(z),f_j^{(2)}(z)$ in $z$ over the integers for $1\le j\le N$. \end{lemma} \begin{proof}We write $f_j(z)=f_j^{(e)}(z)+f_j^{(o)}(z)$, and observe that $$ f_j'(z)=z^{-1}f_j^{(o)}(z)\quad \text {modulo }2. $$ If this is used in \eqref{eq:2x2diff}, and if we separate the even and odd parts on both sides of the equations, then \eqref{eq:4x4} with $f_j^{(1)}(z)=f_j^{(e)}(z)$ and $f_j^{(2)}(z)=f_j^{(o)}(z)$, $j=1,2,\dots,N$, results after little manipulation. Conversely, suppose that $g_j^{(1)}(z),g_j^{(2)}(z)$, $j=1,2,\dots,N$, is a solution to the system \eqref{eq:4x4}, that is, \begin{align} \notag \sum _{j=1} ^{N}c^{(e)}_{i,j}(z)g^{(1)}_j(z)+ \sum _{j=1} ^{N}c^{(o)}_{i,j}(z)g^{(2)}_j(z)+ \sum _{j=1} ^{N}z^{-1}d^{(1)}_{i,j}(z)g^{(2)}_j(z)&=r^{(e)}_i(z)\quad \text { modulo }2, \\[2mm] \notag \sum _{j=1} ^{N}c^{(o)}_{i,j}(z)g^{(1)}_j(z)+ \sum _{j=1} ^{N}c^{(e)}_{i,j}(z)g^{(2)}_j(z)+ \sum _{j=1} ^{N}z^{-1}d^{(o)}_{i,j}(z)g^{(2)}_j(z)&=r^{(o)}_i(z)\quad \text { modulo }2,\\ &\kern3cm 1\le i\le N. %\label{eq:4x4g} \end{align} At this point, the $g_j^{(1)}(z)$'s need not be even Laurent polynomials, and the $g_j^{(2)}(z)$'s need not be odd Laurent polynomials. We have to prove that there exists a solution $f_j^{(1)}(z),f_j^{(2)}(z)$, $j=1,2,\dots,N$, such that all $f_j^{(1)}(z)$'s are even Laurent polynomials and all $f_j^{(2)}(z)$'s are odd Laurent polynomials. By separating even and odd parts of the $g_k^{(1)}(z)$'s and the $g_j^{(2)}(z)$'s, we obtain the equations %{\allowdisplaybreaks \begin{align} \notag \sum _{j=1} ^{N}c^{(e)}_{i,j}(z)(g^{(1)}_j)^{(e)}(z)+ \sum _{j=1} ^{N}c^{(o)}_{i,j}(z)(g^{(2)}_j)^{(o)}(z)+ \sum _{j=1} ^{N}z^{-1}d^{(1)}_{i,j}(z)(g^{(2)}_j)^{(o)}(z)&=r^{(e)}_i(z)\\ \label{eq:4x4g1} &\text { modulo }2, \\[2mm] \notag \sum _{j=1} ^{N}c^{(e)}_{i,j}(z)(g^{(1)}_j)^{(o)}(z)+ \sum _{j=1} ^{N}c^{(o)}_{i,j}(z)(g^{(2)}_j)^{(e)}(z)+ \sum _{j=1} ^{N}z^{-1}d^{(1)}_{i,j}(z)(g^{(2)}_j)^{(e)}(z)&=0\\ \notag &\text { modulo }2, \\[2mm] \notag \sum _{j=1} ^{N}c^{(o)}_{i,j}(z)(g^{(1)}_j)^{(e)}(z)+ \sum _{j=1} ^{N}c^{(e)}_{i,j}(z)(g^{(2)}_j)^{(o)}(z)+ \sum _{j=1} ^{N}z^{-1}d^{(o)}_{i,j}(z)(g^{(2)}_j)^{(o)}(z)&=r^{(o)}_i(z)\\ \label{eq:4x4g2} &\text { modulo }2,\\ \notag \sum _{j=1} ^{N}c^{(o)}_{i,j}(z)(g^{(1)}_j)^{(o)}(z)+ \sum _{j=1} ^{N}c^{(e)}_{i,j}(z)(g^{(2)}_j)^{(e)}(z)+ \sum _{j=1} ^{N}z^{-1}d^{(o)}_{i,j}(z)(g^{(2)}_j)^{(e)}(z)&=0\\ \notag &\text { modulo }2,\\ \notag &\kern0cm 1\le i\le N. %\label{eq:4x4g} \end{align}%}% Combining \eqref{eq:4x4g1} and \eqref{eq:4x4g2}, we see that $(g_j^{(1)})^{(e)}(z),(g_j^{(2)})^{(o)}(z)$, $j=1,2,\dots,N$, is a solution to \eqref{eq:4x4}, and now the $(g_j^{(1)})^{(e)}(z)$'s are indeed even polynomials while the $(g_j^{(2)})^{(o)}(z)$'s are indeed odd polynomials. Addition of both sides of \eqref{eq:4x4g1} and \eqref{eq:4x4g2} then yields that $$ f_j(z):=(g_j^{(1)})^{(e)}(z)+(g_j^{(2)})^{(o)}(z),\quad 1\le j\le N, $$ is a solution to \eqref{eq:2x2diff} in Laurent polynomials in $z$ over the integers. \end{proof} In general, it is difficult to characterise when the system \eqref{eq:4x4} has a solution. What one has to do is to solve the system over the {\it field\/} of rational functions in $z$ over $\Z/2\Z$, and then to see whether possibly occurring denominators cancel out or, in the case of a parametric solution, whether denominators can be {\it made} to cancel by a suitable choice of the parameters. One simple case, where a characterisation is possible, is given in Lemma~\ref{lem:diff710}, which is crucial for the proof that the generating function for the number of subgroups of index $n$ of $PSL_2(\mathbb Z)$, when these are reduced modulo a given power of $2$, can always be expressed as a polynomial in $\Phi(z)$ with coefficients that are Laurent polynomials in $z$. \medskip We remark that the idea of the method that we have described in this section has certainly further potential. For example, the fact that the series $\Phi(z)$ remains invariant under the substitution $z\to z^2$ (or, more generally, under the substitution $z\to z^{2^h}$, where $h$ is some positive integer) --- up to a simple additive correction --- can be exploited in order to extend the range of applicability of our method to equations where we not only allow differentiation but also this kind of substitution. This is actually already used in a very hidden way in Section~\ref{sec:H5} (cf.\ \cite[Theorem~12]{MuHecke}, setting in relation subgroup numbers of the Hecke group $\mathfrak H(q)$ with subgroup numbers of $C_q*C_q$ modulo~$2$; in terms of generating functions, the meaning of this theorem is that the generating function for the former numbers can be expressed in terms of the generating function for the latter numbers by a relation which involves a substitution $z\to z^2$). Furthermore, as we already mentioned in the introduction, there is no obstacle to modifying the method presented here to work for recursive sequences which are reduced modulo powers of $p$, in connection with the series $\sum _{n\ge0} ^{}z^{p^n}$, although at present we are not able to offer any interesting applications in this direction. \section{A sample application: Catalan numbers} \label{sec:Cat} The {\it Catalan numbers}, defined by $\Cat_n=\frac {1} {n+1}\binom {2n}n$, $n=0,1,\dots$, are ubiquitous in enumerative combinatorics. (Stanley provides a list of 66~sequences of sets enumerated by Catalan numbers in \cite[Ex.~6.19]{StanBI}, with many more in the addendum \cite{Stadd}.) Recently, there have been several papers on the congruence properties of Catalan numbers modulo powers of $2$, see \cite{EuLYAA,LiYeAA,PoSaAA,XiXuAA}. In particular, in \cite{LiYeAA} the Catalan numbers are determined modulo $64$. As we already mentioned in the introduction, the corresponding result (cf.\ \cite[Theorems~6.1--6.6]{LiYeAA}) can be compactly written in the form \eqref{eq:Cat64}. Clearly, once we know the right-hand side of \eqref{eq:Cat64}, the validity of the congruence \eqref{eq:Cat64} can be routinely verified by substituting the right-hand side into the well-known functional equation (cf.\ \cite[(2.3.8)]{Wilf}) \begin{equation} \label{eq:CatEF} zC^2(z)-C(z)+1=0, \end{equation} where $C(z)=\sum _{n=0} ^{\infty}\Cat_nz^n$ denotes the generating function for the Catalan numbers, and reducing powers of $\Phi(z)$ whose exponent exceeds $7$ by means of the relation \eqref{eq:PhiRel} with $\al=1$. We shall now demonstrate that the method from Section~\ref{sec:method} allows one not only to {\it find\/} the congruence \eqref{eq:Cat64} algorithmically, but also to find analogous congruences modulo {\it arbitrary} powers of $2$.\footnote{\label{F:Lucas}% In principle, one could use the generalisations of Lucas' theorem due to Davis and Webb \cite{DaWeAA}, and to Granville \cite{GranAA}, respectively, to analyse the classical expression $\frac {1} {n+1}\binom {2n}n$ for the Catalan numbers modulo a given $2$-power, or, more generally, the right-hand side of \eqref{eq:FCat}. But this approach would be rather cumbersome in comparison with our method, and it is doubtful that one would be able to derive results which are of the same level of generality as Theorems~\ref{thm:Cat}, \ref{thm:Cat4096}, or \ref{thm:2mf}.} \begin{theorem} \label{thm:Cat} Let $\Phi(z)=\sum _{n\ge0} ^{}z^{2^n}$, and let $\al$ be some positive integer. Then the generating function $C(z)$ for Catalan numbers, reduced modulo $2^{3\cdot 2^\al}$, can be expressed as a polynomial in $\Phi(z)$ of degree at most $2^{\al+2}-1$ with coefficients that are Laurent polynomials in $z$ over the integers. \end{theorem} \begin{proof} We apply the method from Section~\ref{sec:method}. We start by substituting the Ansatz \eqref{eq:Ansatz1} in \eqref{eq:CatEF} and reducing the result modulo $2$. In this way, we obtain \begin{equation} \label{eq:quadr} z \sum _{i=0} ^{2^{\al+2}-1}a_{i,1}^2(z)\Phi^{2i}(z) +\sum _{i=0} ^{2^{\al+2}-1}a_{i,1}(z)\Phi^i(z)+1=0\quad \text {modulo }2. \end{equation} We may reduce $\Phi^{2i}(z)$ further using the relation \eqref{eq:PhiRel2}. This leads to \begin{multline} \label{eq:GlCat} z\sum _{i=0} ^{2^{\al+1}-1}\left(a_{i,1}^2(z) +z^{2^{\al+1}}a_{i+2^{\al+1},1}^2(z)\right)\Phi^{2i}(z) + z\sum _{i=0} ^{2^{\al}-1} z^{2^{\al+1}}a_{i+3\cdot2^{\al},1}^2(z)\Phi^{2i}(z)\\[2mm] + z\sum _{i=0} ^{2^{\al}-1}\left(a_{i+2^{\al+1},1}^2(z) +a_{i+3\cdot2^{\al},1}^2(z)\right)\Phi^{2i+2^{\al+1}}(z) +\sum _{i=0} ^{2^{\al+2}-1}a_{i,1}(z)\Phi^i(z) +1=0\quad \text {modulo }2. \end{multline} Now we compare coefficients of $\Phi^i(z)$, for $i=0,1,\dots,2^{\al+2}-1$. For $i$ odd, we see immediately that this implies that $a_{i,1}(z)=0$ modulo~$2$. Proceeding inductively, we now suppose that $a_{2^\be u,1}(z)=0$ modulo~$2$ for odd $u$ and some positive integer $\be$, $\be<\al$. Reading off coefficients of $\Phi^{2^{\be+1}i}$, where $i$ is odd, we then obtain \begin{multline*} za_{2^{\be}i,1}^2(z) +z^{2^{\al+1}+1}a_{2^{\be}i+2^{\al+1},1}^2(z) +z^{2^{\al+1}+1}a_{2^{\be}i+3\cdot2^\al,1}^2(z) \\[2mm] +za_{2^{\be}i+2^\al,1}^2(z) +za_{2^{\be}i+2^{\al+1},1}^2(z) +a_{2^{\be+1}i,1}(z) =0\quad \text {modulo }2. \end{multline*} However, due to our inductive assumption, all squared terms on the left-hand side of this congruence vanish, and we conclude that $a_{2^{\be+1}i,1}(z)=0$ modulo~$2$. So far, we have found that all coefficient Laurent polynomials $a_{i,1}(z)$ vanish modulo~$2$ except possibly $a_{0,1}(z)$ and $a_{2^{\al+1},1}(z)$. The corresponding congruences that we obtain from extracting coefficients of $\Phi^0(z)$ and $\Phi^{2^{\al+1}}(z)$, respectively, in \eqref{eq:GlCat}, are \begin{align} \label{eq:GlCat-a0} za_{0,1}^2(z) +z^{2^{\al+1}+1}a_{2^{\al+1},1}^2(z)+a_{0,1}(z)+1=0\quad &\text {modulo }2, \\[2mm] \label{eq:GlCat-aviel} za_{2^{\al+1},1}^2(z)+a_{2^{\al+1},1}(z)=0\quad &\text {modulo }2. \end{align} The only solutions to \eqref{eq:GlCat-aviel} are $ a_{2^{\al+1},1}(z)=0 $ modulo~$2$, respectively $ a_{2^{\al+1},1}(z)=z^{-1} $ modulo~$2$. The first option is impossible, since it would imply that, modulo~$2$, the series $C(z)$ reduces to a polynomial; a contradiction to the well-known fact (easily derivable from Legendre's formula \cite[p.~10]{LegeAA} for the $p$-adic valuation of factorials; cf.\ \eqref{eq:Leg}) that the Catalan number $\Cat_n$ is odd if, and only if, $n=2^k-1$ for some $k$. Thus, \begin{equation*} %\label{eq:Cataviel} a_{2^{\al+1},1}(z)=z^{-1}\quad \text {modulo }2. \end{equation*} Use of this result in \eqref{eq:GlCat-a0} yields the congruence \begin{equation} \label{eq:Cata0} za_{0,1}^2(z)+a_{0,1}(z) +z^{2^{\al+1}-1}+1=0\quad \text {modulo }2 \end{equation} for $a_{0,1}(z)$. We let $$ a_{0,1}(z)=\widetilde a_{0,1}(z)+\sum _{k=0} ^{\al}z^{2^k-1} $$ and substitute this in \eqref{eq:Cata0}. Thereby, we get $$ z\widetilde a_{0,1}^2(z)+\sum _{k=0} ^{\al}z^{2^{k+1}-1} +\widetilde a_{0,1}(z)+\sum _{k=0} ^{\al}z^{2^k-1} +z^{2^{\al+1}-1}+1=0\quad \text {modulo }2, $$ or, after simplification, $$ z\widetilde a_{0,1}^2(z)+\widetilde a_{0,1}(z)=0\quad \text {modulo }2. $$ Again, either $\widetilde a_{0,1}(z)=0$ modulo~$2$, or $\widetilde a_{0,1}(z)=z^{-1}$ modulo~$2$. Here, the second option is impossible, since it would imply that $C(z)$ contains a negative $z$-power, which is absurd. In summary, we have found that \begin{align*} a_{0,1}(z)&=\sum _{k=0} ^{\al}z^{2^k-1}\quad \text {modulo }2,\\[2mm] a_{2^{\al+1},1}(z)&=z^{-1}\quad \text {modulo }2, \end{align*} with all other $a_{i,1}(z)$ vanishing, forms the unique solution modulo $2$ in Laurent polynomials $a_{i,1}(z)$ to the system of congruences resulting from \eqref{eq:GlCat}. \medskip After we have completed the ``base step," we now proceed with the iterative steps described in Section~\ref{sec:method}. We consider the Ansatz \eqref{eq:Ansatz2}--\eqref{eq:Ansatz2b}, where the coefficients $a_{i,\be}(z)$ are supposed to provide a solution $C_{\be}(z)=\sum _{i=0} ^{2^{\al+2}-1}a_{i,\be}(z)\Phi^i(z)$ to \eqref{eq:CatEF} modulo~$2^\be$. This Ansatz, substituted in \eqref{eq:CatEF}, produces the congruence \begin{equation*} zC_{\be}^2(z)-C_{\be}(z) +2^\be\sum _{i=0} ^{2^{\al+2}-1}b_{i,\be+1}(z)\Phi^i(z) +1=0 \quad \text {modulo }2^{\be+1}. \end{equation*} By our assumption on $C_{\be}(z)$, we may divide by $2^\be$. Comparison of powers of $\Phi(z)$ then yields a system of congruences of the form $$ b_{i,\be+1}(z)+\text {Pol}_i(z)=0\quad \text {modulo }2,\quad \quad i=0,1,\dots,2^{\al+2}-1, $$ where $\text {Pol}_i(z)$, $i=0,1,\dots,2^{\al+2}-1$, are certain Laurent polynomials with integer coefficients. This system being trivially uniquely solvable, we have proved that, for an arbitrary positive integer $\al$, the algorithm of Section~\ref{sec:method} will produce a solution $C_{{3\cdot 2^\al}}(z)$ to \eqref{eq:CatEF} modulo $2^{3\cdot 2^\al}$ which is a polynomial in $\Phi(z)$ with coefficients that are Laurent polynomials in $z$. \end{proof} For example, our computer program needs only about 30 seconds to come up with the corresponding congruence modulo $2^{3\cdot 2^2}=4096$. { \allowdisplaybreaks \begin{theorem} \label{thm:Cat4096} Let $\Phi(z)=\sum _{n\ge0} ^{}z^{2^n}$. Then we have \begin{multline} \label{eq:Cat4096} \sum _{n=0} ^{\infty}\Cat_nz^n= 2048 {z^{14}} + 3072 {z^{13}} + 2048 {z^{12}} + 3584 {z^{11}} + 640 {z^{10}} + 2240 {z^9} + 32 {z^8} \\[2mm] + 832 {z^7} + 2412 {z^6} + 1042 {z^5} + 2702 {z^4} + 53 {z^3} + 2 {z^2} + z + 1 \\[2mm] \kern-3cm + \left( 2048 {z^{12}} + 3840 {z^{10}} + 2112 {z^8} + 2112 {z^7} + 552 {z^6} \right. \\[2mm] \left.+ 3128 {z^5} + 2512 {z^4} + 4000 {z^3} + 3904 {z^2} \right) \Phi(z) \\[2mm] + \left( 2048 {z^{13}} + 3072 {z^{11}} + 1536 {z^{10}} + 1152 {z^9} + 1024 {z^8} + 4000 {z^7} + 3440 {z^6} \right. \\[2mm] \left.+ 3788 {z^5} + 3096 {z^4} + 3416 {z^3} + 2368 {z^2} + 288 z \right) {{\Phi^2(z)}}\\[2mm] + \left( 2048 {z^{11}} + 2048 {z^{10}} + 2304 {z^9} + 512 {z^8} + 2752 {z^7} + 3072 {z^6} + 728 {z^5} \right. \\[2mm] \left.+ 3528 {z^4} + 1032 {z^3} + 3168 {z^2} + 3456 z + 3904 \right) {{\Phi^3(z)}}\\[2mm] + \left( 2048 {z^{12}} + 3072 {z^{11}} + 1024 {z^{10}} + 2048 {z^9} + 1152 {z^8} + 1728 {z^7} + 2272 {z^6} + 2464 {z^5} \right. \\[2mm] \left.+ 3452 {z^4} + 3154 {z^3} + 2136 {z^2} + 3896 z + 1600 + {\frac {48} z} \right) {{\Phi^4(z)}}\\[2mm] \kern-1.5cm + \left( 2048 {z^{10}} + 2048 {z^9} + 1792 {z^8} + 1792 {z^7} + 1088 {z^6} + 1536 {z^5} \right. \\[2mm] \left.+ 1704 {z^4} + 3648 {z^3} + 3288 {z^2} + 200 z + 3728 +{\frac {2272} z} \right) {{\Phi^5(z)}}\\[2mm] + \left( 2048 {z^{11}} 1024 {z^9} + 1536 {z^8} + 3200 {z^7} + 2816 {z^6} + 1312 {z^5} + 3824 {z^4} \right. \\[2mm] \left.+ 140 {z^3} + 592 {z^2} + 3692 z + 488 + {\frac {2760} z} \right) {{\Phi^6(z)}} \\[2mm] + \left( 2048 {z^9} + 2304 {z^7} + 2304 {z^6} + 3520 {z^5} + 960 {z^4} + 2456 {z^3} \right. \\[2mm] \left.+ 2128 {z^2} + 2936 z + 1784 + {\frac {4024} z} \right) {{\Phi^7(z)}}\\[2mm] + \left( 2048 {z^{10}} + 1024 {z^9} + 2048 {z^8} + 512 {z^7} + 3968 {z^6} + 1088 {z^5} + 1888 {z^4} \right. \\[2mm] \left.+ 832 {z^3} + 1444 {z^2} + 2646 z + 3258 + {\frac {339} z} \right) {{\Phi^8(z)}}\\[2mm] \kern-3cm + \left( 2048 {z^8} + 3328 {z^6} + 1536 {z^5} + 3008 {z^4} \right. \\[2mm] \left. + 320 {z^3} + 2168 {z^2} + 1144 z + 3992 + {\frac {3152} z} \right) {{\Phi^9(z)}}\\[2mm] \kern-3cm + \left( 2048 {z^9} + 3072 {z^7} + 512 {z^6} + 1408 {z^5} + 2560 {z^4} \right. \\[2mm] \left. + 3424 {z^3} + 3408 {z^2} + 1316 z + 3608 + {\frac {2380} z} \right) {{\Phi^{10}(z)}}\\[2mm] \kern-2cm + \left( 2048 {z^7} + 2048 {z^6} + 2816 {z^5} + 3072 {z^4} + 1856 {z^3} \right. \\[2mm] \left. + 2688 {z^2} + 1288 z + 3880 + {\frac {3904} z} \right) {{\Phi^{11}(z)}}\\[2mm] \kern-3cm + \left( 2048 {z^8} + 1024 {z^7} + 3072 {z^6} + 2048 {z^5} + 1408 {z^4} \right. \\[2mm] \left. + 2624 {z^3} + 1440 {z^2} + 224 z + 948 + {\frac {358} z} \right) {{\Phi^{12}(z)}}\\[2mm] + \left( 2048 {z^6} + 2048 {z^5} + 3328 {z^4} + 2816 {z^3} + 1984 {z^2} + 384 z + 2488 + {\frac {2384} z} \right) {{\Phi^{13}(z)}}\\[2mm] + \left( 2048 {z^7} + 1024 {z^5} + 512 {z^4} + 2432 {z^3} + 1792 {z^2} + 3040 z + 336 + {\frac {260} z} \right) {{\Phi^{14}(z)}}\\[2mm] + \left( 2048 {z^5} + 768 {z^3} + 256 {z^2} + 64 z + 2752 + {\frac {2696} z} \right) {{\Phi^{15}(z)}}\\[2mm] \text{\em modulo }4096. \end{multline} \end{theorem} } The reader is reminded that coefficient extraction from an expression such as the one on the right-hand side of \eqref{eq:Cat4096} is straightforward, via the algorithm described in Section~\ref{sec:extr} (see \eqref{eq:Phipot} and the proof of Lemma~\ref{lem:Hbi}). \section{A non-example} \label{sec:nonex} Consider the equation \begin{equation} \label{eq:EqH7} z\FF^6(z)-\FF(z)+1=0, \end{equation} which has a unique formal power series solution $\FF(z)$. We note that the coefficients in the series are special instances of numbers that are now commonly known as {\it Fu\ss--Catalan numbers}, which have numerous combinatorial interpretations; cf.\ \cite[pp.~59--60]{ArmDAA}. It was shown in \cite[Eq.~(36)]{MuHecke} that the coefficient of $z^\la$ in the series $\FF(z)$ has the same parity as the number of free subgroups of index $14\la$ in the Hecke group $\mathfrak H(7)=C_2*C_7$. If we try our method from Section~\ref{sec:method}, then already at the mod-$2$ level we fail: let $\FF(z)=a_1(z)\Phi(z)+a_0(z)$~modulo~$2$, for some Laurent polynomials $a_0(z)$ and $a_1(z)$. Upon substitution in \eqref{eq:EqH7} and simplification using (cf.\ Proposition~\ref{prop:minpol}) $$ \Phi^2(z)+\Phi(z)+1=0 \text{ modulo }2, $$ we obtain \begin{multline*} z a_0^6(z) + z a_0^4(z) a_1^2(z) +a_0(z)+z a_1^6(z)+1\\[2mm] +\Phi(z) \left( z a_0^4(z) a_1^2(z) + z a_0^2(z) a_1^4(z) +a_1(z)\right)=0 \quad \text{modulo }2. \end{multline*} or, equivalently, \begin{align} \label{eq:a0a1} z a_0^6(z) + z a_0^4(z) a_1^2(z) +z a_1^6(z) +a_0(z) +1&=0 \quad \text {modulo }2\\[2mm] \label{eq:a0a12} z a_0^4(z) a_1^2(z) + z a_0^2(z) a_1^4(z) +a_1(z)&=0 \quad \text {modulo }2. \end{align} However, this congruence has no solution in Laurent polynomials $a_0(z)$ and $a_1(z)$. For, the Laurent polynomials $a_0^6(z)$, $a_0^4(z)a_1^2(z)$, $a_1^6(z)$, all of them being squares, contain only even powers of $z$ when the coefficients are reduced modulo~$2$. Consequently, the term $a_0(z)+1$ on the left-hand side of \eqref{eq:a0a1} can only contain even powers (modulo~$2$). In particular, $a_0(z)$ must contain the term $1$. If we now suppose that $a_0(z)$ and/or $a_1(z)$ contain negative powers of $z$, then we obtain a contradiction regardless whether the orders (the minimal $e$ such that $z^e$ appears in a Laurent polynomial) of $a_0(z)$ and $a_1(z)$ are the same or not. This implies that both $a_0(z)$ and $a_1(z)$ are actually polynomials in~$z$, with $a_0(z)$ being of the form $a_0(z)=1+\widetilde a_0(z)$, where $\widetilde a_0(z)$ is a polynomial without constant term. %Hence, the left-hand side of %\eqref{eq:a0a1} equals %\begin{equation} \label{eq:a0a1A} %z+z\widetilde a_0^6(z) + z % a_1^2(z) + z\widetilde a_0^4(z) % a_1^2(z) %+z a_1^6(z) % +\widetilde a_0(z). %\end{equation} If we now multiply both sides of \eqref{eq:a0a1} by $a_1^2(z)$ and both sides of \eqref{eq:a0a12} by $a_0^2(z)$, and subsequently add the two congruences, then we obtain $$ z a_1^8(z) +a_0(z)a_1^2(z) +a_0^2(z)a_1(z) +a_1^2(z)=0 \quad \text {modulo }2. $$ Dividing by $a_1(z)$ and replacing $a_0(z)$ by $1+\widetilde a_0(z)$, we obtain the equivalent congruence $$ z a_1^7(z) +\widetilde a_0(z)a_1(z) +\widetilde a_0^2(z)+1=0 \quad \text {modulo }2. $$ This congruence has no solution since $\widetilde a_0(z)$ has no constant term modulo $2$. \medskip In the next theorem, we reveal the deeper reason why our method must fail for $\FF(z)$. Namely, it shows that exponents $e$ of terms $z^e$ which survive in $\FF(z)$ after reduction of its coefficients modulo $2$ may have an arbitrary number of blocks of consecutive $1$'s. In contrast, a polynomial in $\Phi(z)$ of degree $d$ with coefficients that are Laurent polynomials in $z$ can only have terms $z^e$, %after reduction of the coefficients of the %series modulo $2$, where $e$ contains at most $d$ blocks of consecutive $1$'s, apart from a right-most block of bounded length.\footnote{The length of this right-most block is in fact bounded by the maximal modulus of an exponent of $z$ occurring in a Laurent polynomial coefficient.} \begin{theorem} \label{thm:C2C7} Let $\FF(z)$ be the unique formal power series solution to the functional equation \eqref{eq:EqH7}. Then the coefficient of $z^n$ in $\FF(z)$ is odd if, and only if, the sequence of binary digits of $n$ is built by concatenating (in any order) blocks of $0011$ and\/ $01$. In particular, the number of free subgroups of index $n$ in $\mathfrak H(7)=C_2*C_7$ is odd if, and only if, the above condition holds. \end{theorem} \begin{proof} By replacing $\FF(z)$ by $1+\GG(z)$ in \eqref{eq:EqH7}, we obtain $$ z\left(1+\GG(z)\right)^6-\GG(z)=0, $$ or, equivalently, $$ z=\frac {\GG(z)} {(1+\GG(z))^6}, $$ so that $\GG(z)$ is the compositional inverse of the series $z/(1+z)^6$. By the Lagrange inversion formula (cf.\ \cite[Theorem~5.4.2 with $k=1$]{StanBI}), we obtain for $n\ge1$ that \begin{align*} \coef{z^n}\FF(z) &=\coef{z^n}\GG(z)=\frac {1} {n}\coef{z^{-1}}\frac {(1+z)^{6n}} {z^n}\\[2mm] &=\frac {1} {n}\coef{z^{n-1}}{(1+z)^{6n}} =\frac {1} {n}\binom {6n}{n-1} =\frac {1} {6n+1}\binom {6n+1}{n}. \end{align*} By the well-known theorem of Legendre \cite[p.~10]{LegeAA} (cf.\ \eqref{eq:Leg}), we see that the coefficient of $z^n$ in $\FF(z)$ is odd if, and only if, \begin{equation} \label{eq:s65} s(6n+1)-s(5n+1)-s(n)=0, \end{equation} where, as in Section~\ref{sec:Phi}, $s(m)$ denotes the binary digit sum of $m$. Another way to phrase \eqref{eq:s65} is to say that, whenever we find a $1$ in the binary expansion of $n$, then there must also be a $1$ in the binary expansion of $6n+1$ at the same digit place. We are now ready to establish the claim of the theorem. In view of the above considerations, it suffices to show that the condition on $n$ in the statement of the theorem is equivalent to \eqref{eq:s65}. \medskip Let $n$ be a positive integer with the property that its binary expansion is formed by concatenating blocks of the form $0011$ and $01$. We prove that \eqref{eq:s65} holds in this case by induction on $n$. It is routine to check that our assertion holds true for $n=1,2,\dots,15$. Now, let $n=4n_1+1$, with some positive integer $n_1$. In other words, the right-most digits in the binary expansion of $n$ are $01$ and the binary expansion of $n_1$ is formed by concatenating blocks of the form $0011$ and $01$. In that case, we have \begin{align} \notag s(6n+1)-s(5n+1)&-s(n)\\[2mm] \notag &=s\left(4(6n_1+1)+2+1\right)-s\left(4(5n_1+1)+2\right)-s(4n_1+1)\\[2mm] &=s(6n_1+1)+2-s(5n_1+1)-1-s(n_1)-1=0, \label{eq:4n+1} \end{align} by the induction hypothesis applied to $n_1$. On the other hand, if $n=16n_1+3$ for some positive integer $n_1$, that is, if the right-most digits in the binary expansion of $n$ are $0011$ and the binary expansion of $n_1$ is formed by concatenating blocks of the form $0011$ and $01$, then \begin{align} \notag s(6n+1)-s(5n+1)&-s(n)\\[2mm] \notag &=s\left(16(6n_1+1)+2+1\right)-s\left(16(5n_1+1)\right)-s(16n_1+2+1)\\[2mm] &=s(6n_1+1)+2-s(5n_1+1)-s(n_1)-2=0, \label{eq:6n+1} \end{align} establishing again the truth of \eqref{eq:s65}. \medskip In order to prove the converse, let us suppose that $n$ satisfies \eqref{eq:s65}. We start by showing that the binary expansion of $n$ cannot contain any of the substrings $111$, $000$, $1011$. We call an occurrence of any of these substrings a ``violation." Assuming that the right-most violation is a substring of the form $111$, we have \begin{align*} n&=\hphantom{11}\dots \mathbf1110 \dots,\\[1mm] 2n&=\hphantom{0}\dots 1110 \dots0,\\[1mm] 4n&={}\dots 1110 \dots00,\\[1mm] 6n+1&=\hphantom{1}\dots 1\mathbf01\hphantom{0} \dots1, \end{align*} since to the right of the substring $111$ in $n$ there are only blocks of the form $0011$ and $01$ according to our assumption, which implies that there cannot be any carries ``destroying" the substring $101$ in $6n+1$. However, this means that at the place where we find the bold-face $1$ in (the binary expansion of) $n$ we find a $0$ in (the binary expansion of) $6n+1$, a contradiction to \eqref{eq:s65}. Now we assume that the right-most violation is a substring of the form $000$. In that case, we have \begin{align*} n&=\hphantom{11}\dots \mathbf1000 \dots,\\[1mm] 2n&=\hphantom{0}\dots 1000 \dots0,\\[1mm] 4n&={}\dots 1000 \dots00,\\[1mm] 6n+1&=\hphantom{1}\dots 1\mathbf0\hphantom{00} \dots1, \end{align*} a contradiction to \eqref{eq:s65} for the same reason. Finally we assume that the right-most violation is a substring of the form $1011$. Then we have \begin{align*} n&=\hphantom{11}\dots \mathbf10110 \dots,\\[1mm] 2n&=\hphantom{0}\dots 10110 \dots0,\\[1mm] 4n&={}\dots 10110 \dots00,\\[1mm] 6n+1&=\hphantom{1}\dots 0\mathbf001\hphantom{0} \dots1, \end{align*} since to the right of the substring $1011$ in $n$ there are only blocks of the form $0011$ and $01$ according to our assumption, which implies that there cannot be any carries ``destroying" the substring $0001$ in $6n+1$. However, this means that at the place where we find the bold-face $1$ in $n$ we find a $0$ in $6n+1$, again a contradiction to \eqref{eq:s65}. Now let us suppose that $n=2^\al n_1+n_0$, where $n_0$ is an $\al$-digit (binary) number formed by concatenating blocks of the form $0011$ and $01$. By applying the computations \eqref{eq:4n+1} and \eqref{eq:6n+1} (possibly several times), one sees that $n$ satisfies \eqref{eq:s65} if, and only if, $n_1$ does. We claim that $n_1$ cannot be even. For, if it were, say $n_1=2^\be n_2$, then $n_1$ has a $1$ at the digit place $\be$ while $6n_1+1$ has not, a contradiction to \eqref{eq:s65}. But then the already established fact that $n$, and hence $n_1$, cannot contain any of the substrings $111$, $000$, $1011$ implies that the right-most digits in the binary expansion of $n_1$ form either a block $01$ or a block $0011$. This provides an inductive argument that the binary expansion of $n$ is formed by concatenating blocks of the form $0011$ and $01$, and thus completes the proof of the theorem. \end{proof} \section{Free subgroups in lifts of Hecke groups} \label{sec:free} For integers $m,q$ with $m\geq1$, $q\geq3$, and $q$ prime, we consider the group $\Gamma_m(q)$ as defined in \eqref{eq:Heckelift}. Denote by $f_\lambda^{(q)}(m)$ the number of free subgroups of index $2qm\lambda$ in $\Gamma_m(q)$. The purpose of this section is to estimate the $2$-adic valuation of $f_\lambda^{(q)}(m)$ in the case when $q$ is a Fermat prime. This estimate is based on a recurrence relation for these numbers, which, in turn, results from a specialisation of a differential equation in \cite[Sec.~2]{MuHecke}. Moreover, this differential equation for the generating function of free subgroup numbers in $\Ga_m(q)$ will become of crucial importance in Sections~\ref{sec:free2} and \ref{sec:Hecke}. In order to present the aforementioned differential equation, we first need to compute several important invariants of $\Ga_m(q)$. Using notation and definitions from \cite[Sec.~2]{MuHecke}, we have $m_{\Gamma_m(q)} = 2qm$, $\chi(\Gamma_m(q)) = -\frac{q-2}{2qm}$, and thus, \[ \mu(\Gamma_m(q)) = 1 - m_{\Gamma_m(q)} \chi(\Gamma_m(q)) =q-1 = \mu(\mathfrak{H}(q)). \] Moreover, for the family of zeta-invariants $\{\zeta_\kappa(\Gamma_m(q)):\kappa\mid 2qm\}$ of $\Gamma_m(q)$, we find that \begin{equation} \label{Eq:ZetaGamma_m(q)} \zeta_\kappa(\Gamma_m(q)) = \begin{cases} 1,& \kappa=m,\\[1mm] -1,& \kappa=2qm,\\[1mm] 0,& \mbox{otherwise.} \end{cases} \end{equation} Our first result in this section compares the $A$-invariants of $\Gamma_m(q)$, as defined in \cite[Eq.~(14)]{MuHecke}, to those of the underlying Hecke group $\mathfrak{H}(q)$, and provides an estimate for their $2$-adic valuation. \begin{lemma} \label{Lem:ACompare} \begin{enumerate} \item For an integer $m\ge1$ and a prime $q\ge3$, we have \[ A_\mu(\Gamma_m(q)) = m^{q-1} A_\mu(\mathfrak{H}(q)),\quad 0\leq\mu\leq q-1. \] \item We have \[ v_2(A_\mu(\mathfrak{H}(q)) \geq \mu,\quad 0\leq \mu\leq q-1. \] \end{enumerate} \end{lemma} \begin{proof} (i) In view of (\ref{Eq:ZetaGamma_m(q)}), we have, for $0\leq \mu\leq q-1$, that {\allowdisplaybreaks \begin{align*} A_\mu(\Gamma_m(q)) &= \frac{1}{\mu!} \sum_{j=0}^\mu (-1)^{\mu-j} \binom{\mu}{j} 2qm(j+1) \left(\vphantom{\sum_{g_{g_g}}}\right.\underset{(k,2qm)=m}{\prod_{1\leq k\leq 2qm}} (2qmj+k)\left.\vphantom{\sum_{g_{g_g}}}\right) \big(2qm(j+1)\big)^{-1}\\[1mm] &= \frac{1}{\mu!} \sum_{j=0}^\mu (-1)^{\mu-j} \binom{\mu}{j} \underset{(k,2qm)=m}{\prod_{1\leq k\leq 2qm}} (2qmj+k)\\[1mm] &= \frac{1}{\mu!} \sum_{j=0}^\mu (-1)^{\mu-j} \binom{\mu}{j} \underset{(k',2q)=1}{\prod_{1\leq k'\leq 2q}} \big[m(2qj+k')\big]\\[1mm] &= m^{\varphi(2q)} \frac{1}{\mu!} \sum_{j=0}^\mu (-1)^{\mu-j} \binom{\mu}{j} \underset{(k',2q)=1}{\prod_{1\leq k'\leq 2q}} (2qj+k')\\[1mm] &= m^{q-1} A_\mu(\mathfrak{H}(q)), \end{align*}}% as claimed. (ii) This follows from \cite[Lemma~1]{MuHecke}. \end{proof} Our next result is a recurrence relation for the subgroup numbers $f_{\lambda}^{(q)}(m)$. \begin{lemma} \label{Lem:Gamma_m(q)FreeRec} For $m, q$ as in Lemma~{\em\ref{Lem:ACompare}} and $\lambda\geq1,$ we have \begin{multline} \label{Eq:fqmRec} f_{\lambda+1}^{(q)}(m) = \sum_{\mu=1}^{q-1} \sum_{\nu=1}^\mu \underset{\mu_1+\cdots+\mu_\nu=\mu} {\sum_{\mu_1,\ldots,\mu_\nu>0}} \underset{\lambda_1+\cdots+\lambda_\nu=\lambda-\mu} {\sum_{\lambda_1,\ldots,\lambda_\nu\geq0}} \binom{\mu}{\mu_1,\ldots,\mu_\nu} \big(\nu!\, (2q)^\nu\big)^{-1} m^{q-\nu-1} A_\mu(\mathfrak{H}(q))\\[2mm] \times \prod_{j=1}^\nu\Big[(\mu_j-1)! \binom{\lambda_j+\mu_j-1}{\mu_j-1}\Big] \prod_{j=1}^\nu f^{(q)}_{\lambda_j+\mu_j}(m), \end{multline} with initial value $f_1^{(q)}(m) = m^{q-1} A_0(\mathfrak{H}(q))$. \end{lemma} \begin{proof} Setting $\mathfrak{G} = \Gamma_m(q)$ in \cite[Eq.~(18)]{MuHecke}, and using Part~(i) of Lemma~\ref{Lem:ACompare} to compute $A_\mu(\Gamma_m(q))$ in terms of $A_\mu(\mathfrak{H}(q))$, leads to the differential equation \begin{multline} \label{Eq:FmqDiffEq} \kern-2pt G_{m}(q;z) = m^{q-1} A_0(\mathfrak{H}(q))\\[2mm] + \sum_{\mu=1}^{q-1} \sum_{\nu=1}^\mu \underset{\mu_1+\cdots+\mu_\nu=\mu}{\sum_{\mu_1,\ldots,\mu_\nu>0}} \binom{\mu}{\mu_1,\ldots,\mu_\nu}\big(\nu!\, (2q)^\nu\big)^{-1} m^{q-\nu-1} A_\mu(\mathfrak{H}(q)) z^\mu \prod_{j=1}^\nu \big(G_{m}(q;z)\big)^{(\mu_j-1)} \end{multline} for the generating function $G_{m}(q;z):= \sum_{\lambda\geq0} f_{\lambda+1}^{(q)}(m) z^\lambda$. Comparing the coefficient of $z^\lambda$ in (\ref{Eq:FmqDiffEq}) for $\lambda\geq1$ yields (\ref{Eq:fqmRec}); while, for $\lambda=0$, we obtain the required initial value $f_1^{(q)}(m)$. \end{proof} Given these preparations, we can now show the following estimate for the $2$-adic valuation of $f_\lambda^{(q)}(m)$ in the case when $q$ is a Fermat prime. \begin{proposition} \label{Prop:flambdaq2Part} {\em (i)} Let $m\geq1$ be an integer, and let $q\geq3$ be a Fermat prime. Then we have \begin{equation} \label{Eq:flambdaq2Part} v_2(f_\lambda^{(q)}(m)) \geq v_2(m)(\lambda+q-2),\quad \lambda\geq1. \end{equation} In particular, if $m$ is even, then $f_\lambda^{(q)}(m)$ is zero modulo any given $2$-power for all sufficiently large values of $\lambda$. {\em (ii)} For $q=3,$ equality occurs in Inequality~{\em (\ref{Eq:flambdaq2Part})} if, and only if, $\lambda+1$ is a $2$-power. \end{proposition} \begin{proof} (i) Since (\ref{Eq:flambdaq2Part}) is trivially true for $m$ odd, we may suppose that $v_2(m)>0$. We use induction on $\lambda$. For $\lambda=1$, we have \[ v_2(f_1^{(q)}(m)) = v_2(m^{q-1} A_0(\mathfrak{H}(q))) \geq (q-1) v_2(m) = (\lambda+q-2)v_2(m), \] as desired. Now suppose that our claim (\ref{Eq:flambdaq2Part}) holds for all $f_\gamma^{(q)}(m)$ such that $\gamma < L$, with some integer $L\geq2$, and consider an arbitrary summand \[ S = S(\mu, \nu, \mu_1,\ldots,\mu_\nu, \lambda_1,\ldots,\lambda_\nu) \] in the recurrence relation (\ref{Eq:fqmRec}) with $\lambda=L-1$. We find that \begin{align*} v_2(S) &\geq v_2\binom{\mu}{\mu_1,\ldots,\mu_\nu} - v_2(\nu!) - \nu + (q-\nu-1)v_2(m) \\[1mm] &\hspace{7cm}+ v_2(A_\mu(\mathfrak{H}(q))) + \sum_{j=1}^\nu v_2(f^{(q)}_{\lambda_j+\mu_j}(m))\\[2mm] &\geq v_2\binom{\mu}{\mu_1,\ldots,\mu_\nu} - v_2(\nu!) - \nu + (q-\nu-1) v_2(m) + \mu\\[1mm] &\hspace{7cm}+ \sum_{j=1}^\nu (\lambda_j+\mu_j+q-2) v_2(m)\\[2mm] &\ge v_2\binom{\mu}{\mu_1,\ldots,\mu_\nu} - v_2(\nu!) - \nu + (q-\nu-1) v_2(m) + \mu\\[1mm] &\hspace{7cm}+ (L-1)v_2(m) + (q-2)\nu v_2(m)\\[2mm] &\geq (L+q-2) v_2(m) + (q-3)\nu v_2(m) + v_2\binom{\mu}{\mu_1,\ldots,\mu_\nu} + \mu - \nu - v_2(\nu!), \end{align*} where we have used Part~(ii) of Lemma~\ref{Lem:ACompare} plus the induction hypothesis in the second step. Since $\nu\leq\mu$, the desired inequality for the $2$-adic valuation of $f_L^{(q)}(m)$ will follow, if we can show that \begin{equation} \label{Eq:NecEst} v_2(\nu!) \leq (q-3)\nu v_2(m) + v_2\binom{\mu}{\mu_1,\ldots,\mu_\nu}. \end{equation} Since $q$ is a Fermat prime, we have $q-1=2^\alpha$ for some $\alpha\geq1$. Thus, if $\nu