# The congruence properties of Romik’s sequence of Taylor coefficients of
Jacobi’s theta function $\theta_{3}$

C. Krattenthaler† Fakultät für Mathematik, Universität Wien, Oskar-
Morgenstern-Platz 1, A-1090 Vienna, Austria. WWW:
http://www.mat.univie.ac.at/~kratt.  and  T. W. Müller  Fakultät für
Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, A-1090 Vienna,
Austria.

###### Abstract.

In [Ramanujan J. 52 (2020), 275–290], Romik considered the Taylor expansion of
Jacobi’s theta function $\theta_{3}(q)$ at $q=e^{-\pi}$ and encoded it in an
integer sequence $(d(n))_{n\geq 0}$ for which he provided a recursive
procedure to compute the terms of the sequence. He observed intriguing
behaviour of $d(n)$ modulo primes and prime powers. Here we prove (1) that
$d(n)$ eventually vanishes modulo any prime power $p^{e}$ with $p\equiv 3$
(mod 4), (2) that $d(n)$ is eventually periodic modulo any prime power $p^{e}$
with $p\equiv 1$ (mod 4), and (3) that $d(n)$ is purely periodic modulo any
2-power $2^{e}$. Our results also provide more detailed information on period
length, respectively from when on the sequence vanishes or becomes periodic.
The corresponding bounds may not be optimal though, as computer data suggest.
Our approach shows that the above congruence properties hold at a much finer,
polynomial level.

###### Key words and phrases:

Modular forms of half integer weight, Jacobi theta function, Taylor
coefficients, congruences

###### 2020 Mathematics Subject Classification:

Primary 11F37; Secondary 11B83 14K25

†Research partially supported by the Austrian Science Foundation FWF, grant
S50-N15, in the framework of the Special Research Program “Algorithmic and
Enumerative Combinatorics”

##  1\. Introduction

The focus of this article is on Jacobi’s theta function $\theta_{3}$ defined
by (cf. [13, top of p. 464 with $z=0$])

$\theta_{3}(\tau)=\sum_{n=-\infty}^{\infty}q^{n^{2}},\quad\text{with
$q=e^{i\pi\tau}$}.$

In [9], Romik considered the Taylor expansion of $\theta_{3}(\tau)$ at
$\tau=i$ in the form (cf. [9, display below Eq. (8)])

$\theta_{3}\left(i\frac{1+z}{1-z}\right)=\theta_{3}(i)(1-z)^{1/2}\sum_{n=0}^{\infty}\frac{d(n)}{(2n)!}\Phi^{n}z^{2n},$
(1.1)

where $\Phi=\Gamma^{8}(1/4)/(128\pi^{4})$ and, as is well-known (cf. [3, p.
325, Entry 1(i)]), $\theta_{3}(i)=\pi^{1/4}/\Gamma(3/4)$. He showed that the
sequence $\big{(}d(n)\big{)}_{n\geq 0}$ is an integer sequence, and he
provided a highly non-trivial recursive procedure for computing the
coefficients $d(n)$ (see Section 2). The first few values turn out to be

$1,1,-1,51,849,-26199,1341999,82018251,18703396449,\\\
-993278479599,-78795859032801,38711746282537251,-923351332174412751,\dots{}$

The signs of these numbers seem very irregular. (In fact, Problem 5 in Section
8 of [9] asks for figuring out the pattern of signs. So far, there has been no
progress on that question.) However, computer experiments led Romik [9, Conj.
13] to conjecture that $\big{(}d(n)\big{)}_{n\geq 0}$ is (eventually) periodic
when taken modulo a prime $p$ with $p\equiv 1$ (mod 4), and that the sequence
eventually vanishes when taken modulo a prime $p$ with $p\equiv 3$ (mod 4).
More computer experiments suggest (cf. also [12, Conjecture 18(3)]) that
analogous assertions hold modulo any prime power (including powers of 2). To
be more precise, such experiments suggest that:

  1. (1)

$d(n)$ eventually vanishes modulo any prime power $p^{e}$ with $p\equiv 3$
(mod 4);

  2. (2)

$d(n)$ is eventually periodic modulo any prime power $p^{e}$ with $p\equiv 1$
(mod 4);

  3. (3)

$d(n)$ is purely periodic modulo any 2-power $2^{e}$.

Item (1) was proved for primes (i.e., for $e=1$) by Scherer [10]. He also
obtained partial results on Items (2) and (3) by proving that
$d(n)\equiv(-1)^{n+1}$ (mod 5) for $n\geq 1$, and that $d(n)$ is odd for all
$n$. Guerzhoy, Mertens and Rolen [4] claim to have proved Item (2) in full, as
a special case of a more general result for a whole family of modular forms of
half integer weight.111The authors of the present article admit that they are
not able to comprehend what the result(s) in [4] say about Romik’s sequence
$\big{(}d(n)\big{)}_{n\geq 0}$. The first problem is that $\tilde{\Omega}$ in
Theorem 1.3 of [4] is nowhere defined. One may guess that
$\tilde{\Omega}^{2}=\omega$, with the $\omega$ in the proof of Theorem 1.3 on
pages 148/149 of [4]. We assume this guess in the following. In the Remark on
top of page 150 of [4], Romik’s sequence is addressed explicitly. There,
$\omega$ is computed as $\Gamma^{2}(1/4)/(8\pi)^{1/2}$. In Theorem 1.3, the
coefficients $\partial^{n}f(\tau_{0})$ are considered. If, in the case of
$f(\tau)=\Theta(\tau)=\theta_{3}(2\tau)$, we make the comparison of
coefficients in (1-1) and (1-3) of [4], then we obtain the relation
$(2\pi)^{n}\partial^{n}\Theta(i/2)=\Theta(i/2)\Phi^{n}D(n),$ where we write
$D(n)$ for the Taylor coefficients in Romik’s series, that is, $D(2n)=d(n)$
and$D(2n+1)=0$. In order to apply Theorem 1.3 to Romik’s sequence, we must
choose $k=1$ there. In particular, we should divide the above relation by
$\tilde{\Omega}^{4n+1}$:
$\frac{(2\pi)^{n}\partial^{n}\Theta(i/2)}{\tilde{\Omega}^{4n+1}}=\frac{\Theta(i/2)\Phi^{n}D(n)}{\tilde{\Omega}^{4n+1}}.$
Now we use the assumption that $\tilde{\Omega}=\omega^{1/2}$ and the relation
$\omega^{2}=2^{1/2}\pi\Phi$ from the Remark on top of page 150 of [4]. We
substitute and get, after some cancellation,
$\frac{(2\pi)^{n}\partial^{n}\Theta(i/2)}{\tilde{\Omega}^{4n+1}}=\frac{D(n)}{2^{n/2-1/4}\pi^{n+1/2}}.$
Here is the first problem: $\pi$ does not drop out. This could be easily
fixed: just change the normalisation by that power of $\pi$. However, that
would create another, equally serious problem. Then the (re)normalised
sequence equals Romik’s sequence (with 0s for odd indexed coefficients) up to
some power of $2^{1/2}$. Then Theorem 1.3, say with $A=0$, predicts a period
length of the (re)normalised sequence, taken modulo $p$, of $2(p-1)$. (The
factor 2 comes from the period length of $2^{1/2}$ modulo $p$.) Translated to
Romik’s original sequence $\big{(}d(n)\big{)}_{n\geq 0}$ (i.e., without 0s),
this implies a period length of $p-1$. However, this is definitely wrong. For
example, for $p=13$, Romik’s sequence, taken modulo 13, begins
$1,1,12,12,4,9,9,3,10,10,12,1,1,9,4,4,10,3,3,\\\
1,12,12,4,9,9,3,10,10,12,1,1,9,4,4,10,3,3,1,12,12,4,\dots{}$ The period length
is visibly 18 ($=(p-1)^{2}/8$); see Conjecture 43(1) in Section 13. Despite
correspondence with the authors of [4], these concerns were not dispelled. In
[12], Wakhare revisited Item (2) for primes (i.e., for $e=1$). He showed that
$d(n)$ is (eventually) periodic modulo any prime number $p$ with $p\equiv 1$
(mod 4) by proving the refinement (see [12, Theorem 2]222 Wakhare did not
simplify $-2^{(p-1)/2}$ modulo $p$ on the right-hand side of the displayed
congruence in [12, Theorem 1] to $(-1)^{(p-5)/4}$.)

$d\left(n+\tfrac{p-1}{2}\right)\equiv(-1)^{(p-5)/4}(3\cdot 7\cdot
11\cdots(2p-3))^{2}d(n)\pmod{p},\\\ \text{for }p\equiv 1~{}(\text{mod
}4)\text{ and }n\geq\tfrac{p+1}{2}.$ (1.2)

Since on the right-hand side of this congruence we have a square,
$\frac{p-1}{2}$-fold iteration of this congruence in combination with Fermat’s
Little Theorem shows that $d(n)$ is (eventually) periodic modulo $p$ with (not
necessarily minimal) period length $\frac{(p-1)^{2}}{4}$.333Wakhare concludes
a period length of only $\frac{(p-1)^{2}}{2}$. The reason is probably the
missed simplification pointed out in Footnote 2.

What all these authors did not notice is that periodicity was already
(implicitly) known. Namely, Rodriguez Villegas and Zagier showed in [8, §§ 6,
7] that Taylor coefficients of entire modular forms at complex multiplication
points444$\tau=i$ is such a “complex multiplication point” for $\theta_{3}$ —
suitably normalised — can be computed via a certain recursive (polynomial)
scheme, and they indicated that this scheme can also be adapted to cover half-
integral weights. Moreover, O’Sullivan and Risager proved in [7, Theorem 6.1]
(in a special case, but the argument is completely general) that integral
number sequences that are produced by such a scheme are automatically periodic
modulo any prime power. On the other hand, this argument only leads to very
crude, super-exponential bounds on the period length, it cannot tell from when
on periodicity occurs, and it also cannot predict whether such a sequence
vanishes eventually modulo a prime power (thus producing a trivial period).

The purpose of the present article is to provide full proofs of all the above
items that do include explicit statements about period lengths, respectively
from when on periodicity or vanishing modulo a prime power holds. The theorem
below collects our corresponding findings (see Theorems 21, 39, and 31).

######  Theorem 1.

(1) Let $p$ be a prime number with $p\equiv 3$ (mod 4), and let $e$ be a
positive integer. Then $d(n)\equiv 0$ (mod $p^{e}$) for
$n\geq\left\lceil\frac{ep^{2}}{2}\right\rceil$.

(2) Let $p$ be a prime number with $p\equiv 1$ (mod 4), and let $e$ be a
positive integer. Then the sequence $\big{(}d(n)\big{)}_{n\geq e+1}$ is purely
periodic modulo $p^{e}$ with (not necessarily minimal) period length
$\frac{1}{4}p^{e-1}(p-1)^{2}$.

(3) Let $e$ be a positive integer. The sequence $(d(n))_{n\geq 0},$ when taken
modulo any fixed $2$-power $2^{e}$ with $e\geq 3,$ is purely periodic with
(not necessarily minimal) period length $2^{e-1}$. Modulo $4,$ the sequence is
purely periodic with period length $4,$ the first few values of the sequence
(modulo $4$) being given by

$1,1,3,3,1,\dots.$

Our proof of Item (2) in fact generalises the congruence (1.2) to prime
powers; see (12.3).

The proofs of the congruence properties of $d(n)$ listed in Theorem 1 that we
provide here are elementary throughout. They do however reveal that these
congruences hold at a much finer, polynomial level; see Remarks 8, 10, 14, 16,
Theorems 28–30, and 38.

More specifically, our proofs require a careful $p$-adic analysis of the
earlier mentioned recursive procedure of computation of the numbers $d(n)$.
This procedure involves two further sequences, namely
$\big{(}u(n)\big{)}_{n\geq 0}$ and $\big{(}v(n)\big{)}_{n\geq 0}$, and a lower
triangular matrix $\big{(}r(n,k)\big{)}_{n,k\geq 0}$. We refer the reader to
Section 2 for the corresponding definitions. In order to accomplish the proofs
of the congruence assertions in Theorem 1, we must first analyse $u(n)$,
$v(n)$, and $r(n,k)$ modulo the three families of prime powers that feature in
the theorem, before we can make conclusions about $d(n)$.

Accordingly, our article is organised as follows. In the next section, we
review Romik’s recursive procedure to compute the Taylor coefficients $d(n)$.
This section contains in fact a notable novelty that is crucial for our
proofs. Briefly, Romik defines a sequence $\big{(}v(n)\big{)}_{n\geq 0}$ and
shows that it equals the product of the matrix $\big{(}r(n,k)\big{)}_{n,k\geq
0}$ — which in its definition involves the sequence $\big{(}u(n)\big{)}_{n\geq
0}$ — and the sequence $\big{(}d(n)\big{)}_{n\geq 0}$ (seen as column vector).
At this point, one would like to invert this relation to have direct access to
the numbers $d(n)$. This would require the computation of the inverse of the
matrix $\big{(}r(n,k)\big{)}_{n,k\geq 0}$. In all previous papers, this point
is somehow by-passed. However, as it turns out, Lagrange inversion permits one
to give a compact formula for the entries of this inverse matrix, again in
terms of the sequence $\big{(}u(n)\big{)}_{n\geq 0}$; see (2.11). More
specifically, we extend the matrix $\big{(}r(n,k)\big{)}_{n,k\geq 0}$ to the
larger matrix $\mathbf{R}=\big{(}R(n,k)\big{)}_{n,k\geq 0}$ in which the
former matrix is embedded as the submatrix indexed by even labelled rows and
columns; that is, $r(n,k)=R(2n,2k)$ for all $n$ and $k$. Our inversion result
then applies to this larger matrix which, in view of the Lagrange inversion
formula, is the one that should be looked at.

In Section 3, we recall the standard results from elementary number theory
concerning the divisibility of factorials and binomial coefficients by prime
powers that we use ubiquitously in our article.

Subsequently, we embark on the $p$-adic analysis of our sequences. Section 4
is devoted to the proof that $u(n)$ vanishes modulo any fixed odd prime prime
power $p^{e}$ for large enough $n$. It contains two main results: Theorem 7
treats the “generic case”, while Theorem 9 contains the (significant)
improvement for the case where $p\equiv 1$ (mod 4). The corresponding results
for $v(n)$ modulo odd prime powers are presented in Section 5. Again there are
two main results: Theorem 13 treats the “generic case”, while Theorem 15
contains the (significant) improvement for the case where $p\equiv 1$ (mod 4).
The final preparations for our first main result on $d(n)$ is done in Section
6, where we prove a $p$-divisibility result for the matrix entries $r(n,k)$
for primes $p$ with $p\equiv 3$ (mod 4); see Theorem 19 and Corollary 20.
Theorem 21 in Section 7 is then our first main result for the sequence
$\big{(}d(n)\big{)}_{n\geq 0}$. It says that $d(n)$ is divisible by prime
powers $p^{e}$ with $p\equiv 3$ (mod 4) for
$n\geq\left\lceil{ep^{2}}/{2}\right\rceil$, thus establishing Part (1) of
Theorem 1.

The next sections are devoted to the analysis of our sequences and our matrix
$\mathbf{R}$ modulo powers of 2. The subject of Section 8 is to show that the
sequence $(v(n))_{n\geq 0}$ is purely periodic modulo any fixed power of $2$,
together with a precise statement on the period length. As a matter of fact,
Theorems 28 and 29 contain a polynomial refinement of that assertion. In
Section 9 we establish a periodicity result for the entries of the inverse of
the matrix $\mathbf{R}$ modulo powers of $2$; see Theorem 30. These findings
are then put together to obtain our second main result for the sequence
$\big{(}d(n)\big{)}_{n\geq 0}$. Namely, $\big{(}d(n)\big{)}_{n\geq 0}$ is
purely periodic modulo $2^{e}$ with (not necessarily minimal) period length
$2^{e-1}$ for $e\geq 3$, while modulo 4 it starts with $1,1,3,3$ and then
repeats itself; see Theorem 31 in Section 10. These results establish Part (3)
of Theorem 1.

The purpose of Sections 11 and 12 is to prove periodicity of
$\big{(}d(n)\big{)}_{n\geq 0}$ modulo prime powers $p^{e}$ with $p\equiv 1$
(mod $4$), accompanied by a precise statement on the period length. The
preparatory work in the former section concerns the analysis of the entries of
the inverse of the matrix $\mathbf{R}$ modulo these prime powers; see Theorem
38. Again, this theorem actually contains a polynomial refinement. This is
then used to prove our third main result on $d(n)$, namely that
$\big{(}d(n)\big{)}_{n\geq e+1}$ is purely periodic modulo $p^{e}$ with
$p\equiv 1$ (mod 4) with (not necessarily minimal) period length
$\frac{1}{4}p^{e-1}(p-1)^{2}$, thus establishing Part (2) of Theorem 1; see
Theorem 39 in Section 12.

The final section, Section 13, addresses the question of whether our results
can be improved concerning period length, respectively point of vanishing. As
is reported in that section, (computer) data suggest that our results are not
far from being optimal, but that it may be possible to improve them by —
roughly — a factor of 2. (Our result on $d(n)$ modulo powers of 2 in Theorem
1(3) seems to be optimal, though.) A proof of such strengthenings would
however require considerable effort involving highly technical considerations.

##  2\. Romik’s recursive procedure for the computation of $d(n)$

In order to prove integrality of the coefficients $d(n)$ in (1.1), Romik sets
up a recursive scheme to compute these numbers from which it is immediate that
it produces integers. This scheme involves two further sequences,
$\big{(}u(n)\big{)}_{n\geq 0}$ and $\big{(}v(n)\big{)}_{n\geq 0}$, and a lower
triangular matrix $\big{(}r(n,k)\big{)}_{n,k\geq 0}$, which we are going to
define next.

Let $(u(n))_{n\geq 0}$ be the sequence defined by an exponential generating
function $U(t)$ via (cf. [9, Eq. (9) and Lemma 5]555The reader should be
warned that our definitions of the series $U(t)$ and the later defined series
$V(t)$ slightly deviate from Romik’s definitions; one gets Romik’s series from
ours by dividing our $U(t)$ by $t$, and by then replacing $t$ by $t^{1/2}$.
Our convention is crucial for the application of Lagrange inversion in
Proposition 2. )

$U(t):=\sum_{n\geq
0}\frac{u(n)}{(2n+1)!}t^{2n+1}=t\frac{{}_{2}F_{1}\\!\left[\begin{matrix}\frac{3}{4},\frac{3}{4}\\\
\frac{3}{2}\end{matrix};{\displaystyle
4t^{2}}\right]}{{}_{2}F_{1}\\!\left[\begin{matrix}\frac{1}{4},\frac{1}{4}\\\
\frac{1}{2}\end{matrix};{\displaystyle 4t^{2}}\right]}.$ (2.1)

Here, ${}_{2}F_{1}[\dots]$ is the usual Gauß hypergeometric series. The reader
is referred to any standard book on special functions for the definition, such
as e.g. [2, Eq. (2.1.2)]. It is not difficult to see (cf. [9, Eq. (17)]) that
an equivalent definition of $u(n)$ is by the recurrence

$u(n)=\prod_{j=1}^{n}(4j-1)^{2}-\sum_{m=0}^{n-1}\binom{2n+1}{2m+1}\Bigg{(}\prod_{j=1}^{n-m}(4j-3)^{2}\Bigg{)}u(m),\quad\text{with
}u(0)=1.$ (2.2)

The first few values turn out to be

$1,6,256,28560,6071040,2098483200,1071889920000,758870167910400,\\\
711206089850880000,852336059876720640000,1271438437097485762560000,\dots{}$

For convenience, we shall later frequently use the short notations

$\Pi_{1}(N):=\prod_{j=1}^{N}(4j-1)^{2}\quad\text{and}\quad\Pi_{3}(N):=\prod_{j=1}^{N}(4j-3)^{2}.$
(2.3)

Then, using these, the above recurrence can be rewritten as

$u(n)=\Pi_{1}(n)-\sum_{m=0}^{n-1}\binom{2n+1}{2m+1}\Pi_{3}(n-m)u(m),\quad\text{with
}u(0)=1.$ (2.4)

The sequence $(v(n))_{n\geq 0}$ is also defined via an exponential generating
function, namely by (cf. [9, Eq. (10) and Lemma 6])

$\sum_{n\geq
0}\frac{v(n)}{2^{n}(2n)!}t^{2n}={}_{2}F_{1}\\!\left[\begin{matrix}\frac{1}{4},\frac{1}{4}\\\
\frac{1}{2}\end{matrix};{\displaystyle 4t^{2}}\right]^{1/2}=\left(\sum_{j\geq
0}\frac{\prod_{\ell=1}^{j}(4\ell-3)^{2}}{(2j)!}t^{2j}\right)^{1/2}.$ (2.5)

Again, it is not difficult to see (cf. [9, Eq. (20)]) that an equivalent
definition of $v(n)$ is by the recurrence

$v(n)=2^{n-1}\Pi_{3}(n)-\frac{1}{2}\sum_{m=1}^{n-1}\binom{2n}{2m}v(m)v(n-m),\quad\text{with
}v(0)=1.$ (2.6)

The first few values turn out to be

$1,1,47,7395,2453425,1399055625,1221037941375,1513229875486875,\\\
2526879997358510625,5469272714829657020625,14892997153152592003359375,\dots{}$

The lower triangular matrix $\big{(}r(n,k)\big{)}_{n,k\geq 0}$ is defined via
the generating function $U(t)$ for the $u(n)$’s in (2.1), namely by

$r(n,k):=2^{n-k}\frac{(2n)!}{(2k)!}\left\langle t^{2n}\right\rangle
U^{2k}(t).$ (2.7)

The matrix is indeed lower triangular since $r(n,k)=0$ for $n<k$, due to the
fact that $U(t)$ has zero constant term. For the convenience of the reader, we
display the table of numbers $r(n,k)$ with $0\leq n,k\leq 6$:

$\begin{matrix}1&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0\\\ 0&48&1&0&0&0&0\\\
0&7584&240&1&0&0&0\\\ 0&2515968&97664&672&1&0&0\\\
0&1432498176&63221760&560448&1440&1&0\\\
0&1247557386240&60299053056&628024320&2141568&2640&1\end{matrix}$

Romik showed that the Taylor coefficients $d(n)$ in (1.1) are related to the
numbers $v(n)$ via the triangular system of equations

$v(n)=\sum_{k=0}^{n}r(n,k)d(k),\quad\text{for all }n\geq 0.$ (2.8)

This may be “turned around” to obtain a recursion for the $d(n)$’s (cf. [9,
Theorem 7]),

$d(n)=v(n)-\sum_{k=0}^{n-1}r(n,k)d(k),\quad\text{and }d(0)=1.$ (2.9)

Without any doubt, Equation (2.9) does provide a recursive way to compute the
coefficients $d(n)$. Indeed, Scherer [10] and Wakhare [12] used it for the
proof of their results. However, in our opinion the suitability of (2.9) for
the proof of congruence relations satisfied by the $d(n)$’s using inductive
arguments is limited. It is more conceptual to invert the relation (2.8) and
express the $d(n)$’s entirely in terms of the $v(n)$’s and the inverse of the
matrix $\big{(}r(n,k)\big{)}_{n,k\geq 0}$.

In order to carry out this programme, we need an explicit formula for the
entries of this inverse matrix. It turns out that this can best be achieved if
one defines the (larger) infinite matrix $\mathbf{R}=(R(n,k))_{n,k\geq 0}$ by

$R(n,k)=2^{(n-k)/2}\frac{n!}{k!}\left\langle t^{n}\right\rangle U^{k}(t).$
(2.10)

Since $U(t)$ is a power series in which even powers of $t$ do not occur, the
matrix $\mathbf{R}$ has a “checkerboard pattern”; more precisely, $R(n,k)\neq
0$ if, and only if, $n$ and $k$ have the same parity. The entries $R(n,k)$ are
in fact all integers. This follows from this checkerboard pattern of
$\mathbf{R}$ (implying that $2^{(n-k)/2}$ on the right-hand side of (2.10) is
always an integer) and from the exponential formula of combinatorics as Romik
explains in [9, Proof of Theorem 7] in a special case (namely in the case
where both $n$ and $k$ are even; the general case can be treated in the same
manner). The matrix $\big{(}r(n,k)\big{)}_{n,k\geq 0}$ is a submatrix of
$\mathbf{R}$ since $R(2n,2k)=r(n,k)$ for all $n$ and $k$ (compare with (2.7)).

######  Proposition 2.

The inverse $\mathbf{R}^{-1}$ of $\mathbf{R}$ is given by
$(R^{-1}(n,k))_{n,k\geq 0}$ with

$R^{-1}(n,k)=2^{(n-k)/2}\frac{(n-1)!}{(k-1)!}\left\langle t^{-k}\right\rangle
U^{-n}(t).$ (2.11)

Here, the case $k=0$ has to be interpreted as $R^{-1}(0,0)=1$ and
$R^{-1}(n,0)=0$ for $n\geq 1$. Moreover, $\mathbf{R}^{-1}$ has integer entries
and $R^{-1}(n,k)\neq 0$ only if $n$ and $k$ have the same parity.

###### Proof.

That $\mathbf{R}^{-1}$ has integer entries is obvious since it is the inverse
of a triangular matrix with integer entries (cf. [9, Theorem 7]) and $1$’s on
the main diagonal.

The first assertion is a consequence of Lagrange inversion (cf. [11, Theorem
5.4.2]): if $F(t)$ is a formal power series with $F(0)=0$ and
$F^{\prime}(0)\neq 0$, and $F^{(-1)}(t)$ is its compositional inverse, then

$\left\langle
t^{n}\right\rangle\big{(}F^{(-1)}(t)\big{)}^{k}=\frac{k}{n}\left\langle
t^{-k}\right\rangle F^{-n}(t).$

In order to apply this theorem to our situation, it must be observed that
under the above conditions the matrix $\big{(}\left\langle t^{n}\right\rangle
F^{k}(t)\big{)}_{n,k\geq 0}$ is inverse to $\big{(}\left\langle
t^{n}\right\rangle\big{(}F^{(-1)}(t)\big{)}^{k}\big{)}_{n,k\geq 0}$. If one
applies this observation with $F(t)=U(t)$, then the assertion of the
proposition follows upon little manipulation.

With the formula (2.11) established, the parity condition follows again from
the fact that $U(t)$ is a power series in which only odd powers of $t$ occur.
∎

Using the entries of the matrix $\mathbf{R}$, the system of equations (2.8)
can be rewritten as

$v(n)=\sum_{k=0}^{n}R(2n,2k)d(k),\quad\text{for all }n\geq 0.$

If we invert this relation using the inverse matrix $\mathbf{R}^{-1}$, then we
obtain

$d(n)=\sum_{k=0}^{n}R^{-1}(2n,2k)v(k).$ (2.12)

We are going to use this formula in the proofs in Sections 10 and 12.

##  3\. Classical criteria for divisibility of factorials and binomial
coefficients by prime powers

Here and in the sequel, for a prime number $p$, let $v_{p}(\alpha)$ denote the
$p$-adic valuation of the integer (or rational number) $\alpha$, defined as
the maximal exponent $e$ such that $\alpha/p^{e}$ is an integer (respectively
a rational number with numerator and denominator coprime to $p$).

There are essentially two formulae for the $p$-adic valuation of a factorial.
The one that we need in this article is Legendre’s formula.

######  Lemma 3 (Legendre’s formula [6, p. 12]).

Let $N$ be a positive integer and $p$ a prime number. Then

$v_{p}(N!)=\frac{N-s_{p}(N)}{p-1},$

where $s_{p}(N)$ denotes the sum of digits in the $p$-adic representation of
$N$.

Similarly, there are essentially two formulae for the $p$-adic valuation of a
binomial coefficient, one in terms of the number of carries when adding the
involved numbers, the other in terms of digit sums; we shall need the former
one.

######  Lemma 4 (Kummer’s theorem [5, pp. 115–116]).

Let $N$ and $K$ be positive integers and $p$ a prime number. Then
$v_{p}\left(\binom{N}{K}\right)$ equals the number of carries when $K$ and
$N-K$ are added in terms of their $p$-adic representations.

The following relation forms the link between the previous two lemmas, and it
provides, at the same time, the previously mentioned alternative in computing
the $p$-adic valuation of a binomial coefficient.

######  Lemma 5.

Let $A$ and $B$ be positive integers and $p$ a prime number. Then

$\frac{1}{p-1}\Big{(}s_{p}(A)+s_{p}(B)-s_{p}(A+B)\Big{)}\\\ =\\#(\text{\em
carries when adding $A$ and $B$ in their $p$-adic representations}).$

##  4\. The sequence $(u(n))_{n\geq 0}$ modulo odd prime powers

In this section, we analyse the numbers $u(n)$ modulo odd prime powers
$p^{e}$. The first result is Theorem 7 which states that $u(n)$ vanishes
modulo $p^{e}$ for $n\geq\left\lfloor ep^{2}/2\right\rfloor$, for all odd
primes and all positive integers $e$. In case the prime $p$ should be
congruent to $1$ modulo 4, however, this result can be significantly
strengthened; see Theorem 9. The proof of that theorem requires two auxiliary
results which we state and prove separately; cf. Lemmas 11 and 12.

We begin by providing lower bounds on the $p$-adic valuations of the products
$\Pi_{1}(N)$ and $\Pi_{3}(N)$ defined in (2.3) that will be ubiquitously used
in this and the next section.

######  Lemma 6.

For all odd primes $p$ and non-negative integers $N,$ we have

$v_{p}\big{(}\Pi_{1}(N)\big{)}\geq
2\left\lfloor\tfrac{N}{p}\right\rfloor\quad\text{and}\quad
v_{p}\big{(}\Pi_{3}(N)\big{)}\geq 2\left\lfloor\tfrac{N}{p}\right\rfloor.$
(4.1)

If $p\equiv 1$ (mod $4$), then we even have

$v_{p}\big{(}\Pi_{3}(N)\big{)}\geq
2\left\lfloor\tfrac{N+\frac{3}{4}(p-1)}{p}\right\rfloor.$ (4.2)

The following theorem proves Conjecture 18(1) in [12] for $u(n)$.

######  Theorem 7.

Let $(u(n))_{n\geq 0}$ be defined by the recurrence (2.2). Then, given an odd
prime $p$ and a positive integer $e,$ the number $u(n)$ is divisible by
$p^{e}$ for $n\geq\left\lfloor\frac{ep^{2}}{2}\right\rfloor$.

Moreover, for odd positive integers $g,$ the number $u(\frac{gp-1}{2})$ is
divisible by $p$ for$p\equiv 3$ (mod $4$).

###### Proof.

We prove the theorem by a double induction on $e$ and $n$, the outer induction
being on $e$. Clearly, the theorem is trivial for $e=0$, which serves as the
start of the induction.

Let $n\geq\left\lfloor\frac{ep^{2}}{2}\right\rfloor$. By (4.1), for the first
term on the right-hand side of (2.2)/(2.4) we have

$v_{p}\big{(}\Pi_{1}(n)\big{)}\geq 2\left\lfloor\tfrac{n}{p}\right\rfloor\geq
2\left\lfloor\tfrac{ep^{2}}{2p}\right\rfloor=2\left\lfloor\tfrac{ep}{2}\right\rfloor\geq
e.$

Next we consider the summand on the right-hand side of (2.2)/(2.4) for
$\left\lfloor\frac{(f-1)p^{2}}{2}\right\rfloor\leq
m<\left\lfloor\frac{fp^{2}}{2}\right\rfloor$ with $1\leq f<e$. By (4.1) and by
the induction hypothesis applied to $u(m)$, we have

$v_{p}\left(\big{(}\Pi_{3}(n-m)\big{)}u(m)\right)\geq
2\left\lfloor\tfrac{n-m}{p}\right\rfloor+f-1.$

Our conditions imply
$n-m\geq\left\lfloor\frac{ep^{2}}{2}\right\rfloor-\left\lfloor\frac{fp^{2}}{2}\right\rfloor+1\geq{\frac{(e-f)p^{2}}{2}}$.
Therefore, we obtain

$v_{p}\left(\big{(}\Pi_{3}(n-m)\big{)}u(m)\right)\geq
2\left\lfloor\tfrac{(e-f)p^{2}}{2p}\right\rfloor+f-1\geq e-f+1+f-1=e.$

Consequently, the summand is divisible by $p^{e}$ for
$m<\left\lfloor\frac{(e-1)p^{2}}{2}\right\rfloor$.

For $\left\lfloor\frac{(e-1)p^{2}}{2}\right\rfloor\leq
m\leq\min\left\\{n-p,\left\lfloor\frac{ep^{2}}{2}\right\rfloor-1\right\\}$, we
have

$v_{p}\left(\big{(}\Pi_{3}(n-m)\big{)}u(m)\right)\geq
2\left\lfloor\tfrac{n-m}{p}\right\rfloor+e-1\geq 1+e-1=e.$

Hence, also these summands are divisible by $p^{e}$.

The only range for $m$ which remains to be considered is

$\min\left\\{n-p,\left\lfloor\tfrac{ep^{2}}{2}\right\rfloor-1\right\\}<m<n.$

We distinguish two cases. If

$\min\left\\{n-p,\left\lfloor\tfrac{ep^{2}}{2}\right\rfloor-1\right\\}=\left\lfloor\tfrac{ep^{2}}{2}\right\rfloor-1,$

then, by the induction hypothesis (for $n$), the number $u(m)$ is divisible by
$p^{e}$, and thus also the corresponding summand. On the other hand, if

$\min\left\\{n-p,\left\lfloor\tfrac{ep^{2}}{2}\right\rfloor-1\right\\}=n-p,$

then we need only consider $m$’s in the range
$n-p<m<\left\lfloor\tfrac{ep^{2}}{2}\right\rfloor$, since for the $m$’s with
$m\geq\left\lfloor\tfrac{ep^{2}}{2}\right\rfloor$ the number $u(m)$ is
divisible by $p^{e}$. Here we use the symmetry of binomial coefficients,

$\binom{2n+1}{2m+1}=\binom{2n+1}{2(n-m)}=\frac{(2n+1)(2n)\cdots(2m+2)}{(2(n-m))!}.$

Since $2n+1\geq ep^{2}$ and $2m+2\leq ep^{2}$, the numerator of the above
fraction contains a factor $p^{2}$, while the denominator may be divisible by
$p$ but not by $p^{2}$, since $2(n-m)<2p$. Together with the fact that $u(m)$
is divisible by $p^{e-1}$ by the induction hypothesis, this shows that here
too the corresponding summand is divisible by $p^{e}$.

Finally, we address the second assertion of the theorem. For
$n=\frac{gp-1}{2}$, we have $\binom{2n+1}{2m+1}=\binom{gp}{2m+1}$, which is
divisible by $p$ if $\frac{(g-2)p+1}{2}\leq m<\frac{gp-1}{2}$. For $0\leq
m<\frac{(g-2)p+1}{2}$, we have $p\leq n-m\leq\frac{gp-1}{2}$, and hence, by
(4.1), the product $\prod_{i=1}^{n-m}(4j-3)$ is divisible by $p$. Furthermore,
the product $\prod_{i=1}^{(p-1)/2}(4j-1)=3\cdot 7\cdots(2p-3)$ contains $p$ as
a factor if $p\equiv 3$ (mod $4$). Together, this establishes that $p$ divides
$u(\frac{gp-1}{2})$.

The proof of the theorem is now complete. ∎

######  Remark 8.

An examination of the above arguments reveals that the products $\Pi_{1}(n)$
and $\Pi_{3}(n)$ in the definition (2.4) could have been replaced with any
functions $f(n)$ and $g(n)$ that satisfy the $p$-divisibility properties in
(4.1).

######  Theorem 9.

Let $(u(n))_{n\geq 0}$ be defined by the recurrence (2.2). Then, given a
prime$p\equiv 1$ (mod $4$) and a positive integer $e,$ the number $u(n)$ is
divisible by $p^{e}$ for $n\geq\left\lceil\frac{ep}{2}\right\rceil$. Moreover,
the number $u\big{(}\frac{p-1}{2}\big{)}$ is a quadratic residue modulo $p$
and relatively prime to $p$.

###### Proof.

We begin with the second assertion. Setting $n=\frac{p-1}{2}$ in (2.2)/(2.4),
we obtain

$u\left(\tfrac{p-1}{2}\right)=\Pi_{1}\left(\tfrac{p-1}{2}\right)-\sum_{m=0}^{(p-3)/2}\binom{p}{2m+1}\Pi_{3}\left(\tfrac{p-1}{2}\right)u(m).$

Due to the range of the sum on the right-hand side, the binomial coefficient
is always divisible by $p$. Therefore, we have

$u\left(\tfrac{p-1}{2}\right)\equiv\Pi_{1}\left(\tfrac{p-1}{2}\right)\pmod{p}.$
(4.3)

The assertion now follows by observing that
$\Pi_{1}\left(\tfrac{p-1}{2}\right)$ is a square not divisible by $p$.

For the proof of the first assertion, we proceed again by a double induction
on $e$ and $n$, the outer induction being on $e$. The theorem is trivial for
$e=0$, which serves as the start of the induction.

We divide the proof into subtasks. At many places, the argument depends on the
parity of $e$ and/or on the distance of $n$ from its lower bound
$\left\lceil\frac{ep}{2}\right\rceil$.

Task 1: The first term on the left-hand side of (2.4) vanishes modulo $p^{e}$
for even $e$. By (4.1), we have

$v_{p}\big{(}\Pi_{1}(n)\big{)}\geq 2\left\lfloor\tfrac{n}{p}\right\rfloor\geq
2\left\lfloor\tfrac{\left\lceil\frac{ep}{2}\right\rceil}{p}\right\rfloor\geq
2\left\lfloor\tfrac{e}{2}\right\rfloor=e,$

as desired, since $e$ is even.

Task 2: The assertion holds for
$n\geq\left\lceil\frac{(e+1)p}{2}\right\rceil$. Under this assumption we have

$v_{p}\big{(}\Pi_{1}(n)\big{)}\geq 2\left\lfloor\tfrac{n}{p}\right\rfloor\geq
2\left\lfloor\tfrac{\left\lceil\frac{(e+1)p}{2}\right\rceil}{p}\right\rfloor\geq
2\left\lfloor\tfrac{e+1}{2}\right\rfloor\geq e,$

which shows that the first term on the right-hand side of (2.4) vanishes
modulo $p^{e}$.

Next we consider the summand on the right-hand side of (2.4). For
$m\geq\left\lceil\frac{ep}{2}\right\rceil$, the term $u(m)$ is divisible by
$p^{e}$ by the inductive hypothesis (with respect to $n$), hence the
corresponding summand vanishes modulo $p^{e}$. Now let
$\left\lceil\frac{(f-1)p}{2}\right\rceil\leq
m<\left\lceil\frac{fp}{2}\right\rceil$ with $1\leq f\leq e$. Our conditions
imply that

$n-m\geq\left\lceil\frac{(e+1)p}{2}\right\rceil-\left\lceil\frac{fp}{2}\right\rceil+1\geq\left\lceil\frac{(e+1-f)p}{2}\right\rceil.$

Therefore, by using (4.2) we obtain

$v_{p}\left(\big{(}\Pi_{3}(n-m)\big{)}u(m)\right)\geq
2\left\lfloor\tfrac{\left\lceil\frac{(e+1-f)p}{2}\right\rceil+\frac{3}{4}(p-1)}{p}\right\rfloor+f-1\geq(e-f+1)+f-1=e,$

which shows that also in this case the corresponding summand vanishes modulo
$p^{e}$.

From now on we assume that $n<\left\lceil\frac{(e+1)p}{2}\right\rceil$ or,
more precisely, integrating the overall assumption, that
$\left\lceil\frac{ep}{2}\right\rceil\leq
n<\left\lceil\frac{(e+1)p}{2}\right\rceil$.

Task 3: $p$-adic analysis of the summand in (2.4) for
$\left\lceil\frac{ep}{2}\right\rceil\leq
n<\left\lceil\frac{(e+1)p}{2}\right\rceil$. As before, by the induction
hypothesis of the induction on $n$, the term $u(m)$ in the sum in (2.4) is
divisible by $p^{e}$ for $m\geq\left\lceil\frac{ep}{2}\right\rceil$, and thus
is the corresponding summand.

Next we consider the summand on the right-hand side of (2.4) for
$\left\lceil\frac{(f-1)p}{2}\right\rceil\leq
m<\left\lceil\frac{fp}{2}\right\rceil$ with $1\leq f\leq e$. Our conditions
imply
$n-m\geq\left\lceil\frac{ep}{2}\right\rceil-\left\lceil\frac{fp}{2}\right\rceil+1\geq\left\lceil\frac{(e-f)p}{2}\right\rceil$.
Therefore, by using (4.2) we obtain

$v_{p}\left(\big{(}\Pi_{3}(n-m)\big{)}u(m)\right)\geq
2\left\lfloor\tfrac{\left\lceil\frac{(e-f)p}{2}\right\rceil+\frac{3}{4}(p-1)}{p}\right\rfloor+f-1\geq(e-f)+f-1=e-1.$

Our goal is to show that the summand is divisible by $p^{e}$. We claim that
this is indeed the case as long as $e$ is even, or $e$ is odd and
$m\neq\frac{fp-1}{2}$ for odd $f$. We must therefore prove that the binomial
coefficient in (2.4) is divisible by $p$ in these cases.

To see this, we consider the $p$-adic representations of $2m+1$ and $2n-2m$.
Since $m\neq\frac{fp-1}{2}$, (this condition is essential for the first line
below), these are

$\displaystyle(2m+1)_{p}$ $\displaystyle={}$ $\displaystyle(f-1)_{p}\ *$
$\displaystyle\big{(}2n-2m\big{)}_{p}$ $\displaystyle={}$
$\displaystyle(e-f)_{p}\ *$ (4.4)

Here, $(\alpha)_{p}$ denotes the $p$-adic representation of the integer
$\alpha$, and the stars on the right-hand sides indicate the right-most digits
of $(2m+1)_{p}$ and $(2n-2m)_{p}$ whose precise values are irrelevant. The sum
of $2m+1$ and $2n-2m$ is $2n+1$ whose $p$-adic representation has the form
$(e)_{p}\ *$. Hence, when adding the two numbers on the right-hand sides of
(4.4), at least one carry must occur — namely one from the $p^{0}$-digit to
the $p^{1}$-digit. By Kummer’s theorem in Lemma 4, the consequence is that the
binomial coefficient $\binom{2n+1}{2m+1}$ is divisible by $p$. Therefore the
corresponding summand is divisible by $p^{e}$.

In order to summarise our findings so far:

  1. (1)

By Task 2 the assertion of the theorem holds for
$n\geq\left\lceil\frac{(e+1)p}{2}\right\rceil$.

  2. (2)

For even $e$ and $\left\lceil\frac{ep}{2}\right\rceil\leq
n<\left\lceil\frac{(e+1)p}{2}\right\rceil$ we have shown that all summands of
the sum on the right-hand side of (2.4) are divisible by $p^{e}$. Since in
Task 1 we have proved that also the first term on the right-hand side of (2.4)
is divisible by $p^{e}$, this establishes the assertion of the theorem for
even $e$.

  3. (3)

For odd $e$ and $\left\lceil\frac{ep}{2}\right\rceil\leq
n<\left\lceil\frac{(e+1)p}{2}\right\rceil$ we have shown that all summands of
the sum on the right-hand side of (2.4) vanish modulo $p^{e}$ except for those
where $m$ is of the form $\frac{p-1}{2}+ip$ for some non-negative integer $i$.

Hence, it remains to discuss the case where $e$ is odd and
$\left\lceil\frac{ep}{2}\right\rceil\leq
n<\left\lceil\frac{(e+1)p}{2}\right\rceil$.

Task 4: $e$ is odd and $\left\lceil\frac{ep}{2}\right\rceil\leq
n<\left\lceil\frac{(e+1)p}{2}\right\rceil$. By Item (3) above, the relation
(2.4) reduces modulo $p^{e}$ to

$u(n)\equiv\Pi_{1}(n)-\sum_{i=0}^{(e-1)/2}\binom{2n+1}{(2i+1)p}\Pi_{3}\big{(}n-\tfrac{p-1}{2}-ip\big{)}u\big{(}\tfrac{p-1}{2}+ip\big{)}\pmod{p^{e}}.$
(4.5)

By the induction hypothesis, we know that

$v_{p}\left(u\left(\tfrac{p-1}{2}+ip\right)\right)\geq 2i.$ (4.6)

Furthermore, by (4.1) we have

$v_{p}\left(\Pi_{3}\big{(}n-\tfrac{p-1}{2}-ip\big{)}\right)\geq
2\left\lfloor\tfrac{1}{p}\left(n-\tfrac{p-1}{2}-ip\right)\right\rfloor\geq
2\left\lfloor\tfrac{1}{p}\left(\tfrac{(e-2i-1)p}{2}\right)\right\rfloor\geq
e-2i-1,$ (4.7)

since $e$ is odd. In particular, the inequalities (4.6) and (4.7) together
imply that

$v_{p}\left(\Pi_{3}\big{(}n-\tfrac{p-1}{2}-ip\big{)}u\big{(}\tfrac{p-1}{2}+ip\big{)}\right)\geq
e-1.$

Consequently, we may consider the binomial coefficient in (4.5) modulo $p$.
Now we use the elementary congruence

$\binom{ap+r}{bp}\equiv\binom{ap}{bp}\pmod{p}$

for positive integers $a,b,r$ with $1\leq r<p$. Since the assumptions of the
case in which we are imply that $ep+2\leq 2n+1\leq(e+1)p-1$, we infer that

$\binom{2n+1}{(2i+1)p}\equiv\binom{ep}{(2i+1)p}\pmod{p}.$

Thus, we see that the congruence (4.5) is equivalent with

$u(n)\equiv\Pi_{1}(n)-\sum_{i=0}^{(e-1)/2}\binom{ep}{(2i+1)p}\Pi_{3}\big{(}n-\tfrac{p-1}{2}-ip\big{)}u\big{(}\tfrac{p-1}{2}+ip\big{)}\pmod{p^{e}}.$
(4.8)

On the other hand, the inequality (4.7) also implies that we may consider the
term $u\big{(}\tfrac{p-1}{2}+ip\big{)}$ in (4.8) modulo $p^{2i+1}$. This
allows us to use Lemma 12 with $e$ replaced by $2i+1$. The corresponding
substitution in (4.8) gives

$u(n)\equiv\Pi_{1}(n)-\sum_{i=0}^{(e-1)/2}\binom{ep}{(2i+1)p}\Pi_{3}\big{(}n-\tfrac{p-1}{2}-ip\big{)}\\\
\cdot\sum_{k\geq 0}\sum_{i=\alpha_{0}>\alpha_{1}>\dots>\alpha_{k}\geq
0}(-1)^{k}\Pi_{1}\left(\tfrac{p-1}{2}+\alpha_{k}p\right)\\\
\cdot\prod_{j=0}^{k-1}\binom{(2\alpha_{j}+1)p}{(2\alpha_{j+1}+1)p}\Pi_{3}\big{(}(\alpha_{j}-\alpha_{j+1})p\big{)}\pmod{p^{e}}.$
(4.9)

We have

$\Pi_{3}\big{(}n-\tfrac{p-1}{2}-ip\big{)}=\Pi_{3}\big{(}\tfrac{ep-2i-1}{2}\big{)}\prod_{j=\frac{(e-2i-1)p}{2}+1}^{n-\frac{p-1}{2}-ip}(4j-3)^{2}.$
(4.10)

Moreover, by (4.1), and remembering that $i=\alpha_{0}$, we get

$v_{p}\left(\Pi_{3}\big{(}\tfrac{(e-2i-1)p}{2}\big{)}\Pi_{1}\left(\tfrac{p-1}{2}+\alpha_{k}p\right)\prod_{j=0}^{k-1}\Pi_{3}\big{(}(\alpha_{j}-\alpha_{j+1})p\big{)}\right)\\\
\geq(e-2i-1)+2\alpha_{k}+\sum_{j=0}^{k-1}2(\alpha_{j}-\alpha_{j+1})=e-1.$

This allows us to consider the product on the right-hand side of (4.10) modulo
$p$, once that equation is substituted in (4.9). The result then is

$u(n)\equiv\Pi_{1}(n)-\bigg{(}\prod_{j=1}^{n-\frac{ep-1}{2}}(4j-3)^{2}\bigg{)}\sum_{i=0}^{(e-1)/2}\binom{ep}{(2i+1)p}\Pi_{3}\big{(}\tfrac{(e-2i-1)p}{2}\big{)}\\\
\cdot\sum_{k\geq 0}\sum_{i=\alpha_{0}>\alpha_{1}>\dots>\alpha_{k}\geq
0}(-1)^{k}\Pi_{1}\left(\tfrac{p-1}{2}+\alpha_{k}p\right)\\\
\cdot\prod_{j=0}^{k-1}\binom{(2\alpha_{j}+1)p}{(2\alpha_{j+1}+1)p}\Pi_{3}\big{(}(\alpha_{j}-\alpha_{j+1})p\big{)}\pmod{p^{e}}.$
(4.11)

Here we see that, in the sum, for $k\geq 1$ the term for

$i=\tfrac{e-1}{2}=\alpha_{0}>\alpha_{1}>\dots>\alpha_{k}\geq 0$

cancels with the term for

$\tfrac{e-1}{2}>\alpha^{\prime}_{0}>\alpha^{\prime}_{1}>\dots>\alpha^{\prime}_{k-1}\geq
0,$

where $\alpha^{\prime}_{j}=\alpha_{j+1}$ for $j=0,1,\dots,k-1$. After this
cancellation, the only remaining term in the sum is the one for $k=0$ and
$\alpha_{0}=\frac{e-1}{2}$. In this regard, we have

$\displaystyle\Bigg{(}\prod_{j=1}^{n-\frac{ep-1}{2}}(4j-3)^{2}\Bigg{)}\Pi_{1}\left(\tfrac{p-1}{2}+\alpha_{0}p\right)$
$\displaystyle\equiv\Bigg{(}\prod_{j=1}^{n-\frac{ep-1}{2}}(4j+2p+4\alpha_{0}p-3)^{2}\Bigg{)}\Pi_{1}\left(\tfrac{p-1}{2}+\alpha_{0}p\right)$
$\displaystyle\equiv\Pi_{1}(n)\pmod{p^{e}}$

since, again using (4.1),

$v_{p}\left(\Pi_{1}\left(\tfrac{p-1}{2}+\alpha_{0}p\right)\right)=v_{p}\left(\Pi_{1}\left(\tfrac{p-1}{2}+\tfrac{e-1}{2}p\right)\right)\geq
e-1.$

Consequently, this term cancels with the first term on the right-hand side of
(4.11).

This concludes the induction step, and hence the proof of the theorem is now
complete. ∎

######  Remark 10.

An examination of the above arguments (including the proofs of Lemmas 11 and
12 which are used in the above proof) reveals that the products $\Pi_{1}(n)$
and $\Pi_{3}(n)$ in the definition (2.4) could have been replaced with any
functions $f(n)$ and $g(n)$ that satisfy the $p$-divisibility properties in
(4.1) and (4.2), and where $f(n)$ is a quadratic residue modulo $p$ not
divisible by $p$.

######  Lemma 11.

We assume that, given a prime $p\equiv 1$ (mod $4$) and an odd positive
integer $e,$ the number $u(n)$ is divisible by $p^{h}$ for
$n\geq\left\lceil\frac{hp}{2}\right\rceil$ and $h<e$. Then

$u\left(\tfrac{ep-1}{2}\right)\equiv\Pi_{1}\left(\tfrac{ep-1}{2}\right)-\sum_{i=1}^{(e-1)/2}\binom{ep}{2ip}\Pi_{3}(ip)\,u\\!\left(\tfrac{ep-1}{2}-ip\right)\pmod{p^{e}}.$
(4.12)

###### Proof.

We put $n=\frac{ep-1}{2}$ in (2.4) and consider the summand indexed by $m$ on
the right-hand side for $\left\lceil\frac{(f-1)p}{2}\right\rceil\leq
m<\left\lceil\frac{fp}{2}\right\rceil$ with $1\leq f\leq e$. By our assumption
on the divisibility of $u(m)$ by powers of $p$ and by (4.2), we have

$v_{p}\left(\big{(}\Pi_{3}\big{(}\tfrac{ep-1}{2}-m\big{)}\big{)}u(m)\right)\geq
2\left\lfloor\tfrac{\frac{ep-1}{2}-m+\frac{3}{4}(p-1)}{p}\right\rfloor+f-1.$

Our conditions imply
$\frac{ep-1}{2}-m\geq{\frac{ep-1}{2}}-\left\lceil\frac{fp}{2}\right\rceil+1\geq\left\lceil\frac{(e-f)p}{2}\right\rceil$.
Therefore, we obtain

$v_{p}\left(\big{(}\Pi_{3}\big{(}\tfrac{ep-1}{2}-m\big{)}\big{)}u(m)\right)\geq
2\left\lfloor\tfrac{\left\lceil\frac{(e-f)p}{2}\right\rceil+\frac{3}{4}(p-1)}{p}\right\rfloor+f-1\geq(e-f)+f-1=e-1.$

In order to show that the summand is indeed divisible by $p^{e}$ for $m$ not
of the form $\frac{ep-1}{2}-ip=\frac{p-1}{2}+\frac{e-2i-1}{2}p$ for some $i$,
we must therefore prove that the binomial coefficient in (2.4) is divisible by
$p$ in this case. To see this, we consider the $p$-adic representations of
$2m+1$ and $ep-1-2m$. Since $m$ is not of the form $\frac{p-1}{2}+sp$ (this
condition is essential for the first line below), these are

$\displaystyle(2m+1)_{p}$ $\displaystyle={}$ $\displaystyle(f-1)_{p}\ *$
$\displaystyle\big{(}ep-1-2m\big{)}_{p}$ $\displaystyle={}$
$\displaystyle(e-f)_{p}\ *$ (4.13)

As before, $(\alpha)_{p}$ denotes the $p$-adic representation of the integer
$\alpha$, and the stars on the right-hand sides indicate the right-most digits
of $(2m+1)_{p}$ and $(ep-1-2m)_{p}$ whose precise values are irrelevant. The
sum of $2m+1$ and $ep-1-2m$ is $ep$ whose $p$-adic representation has the form
$(e)_{p}\ *$. Hence, when adding the two numbers on the right-hand sides of
(4.13), at least one carry must occur — namely one from the $p^{0}$-digit to
the $p^{1}$-digit. By Kummer’s theorem in Lemma 4, the consequence is that the
binomial coefficient $\binom{ep}{2m+1}$ is divisible by $p$. Therefore the
corresponding summand is divisible by $p^{e}$.

This proves that, under our assumptions, the only summands which “survive” on
the right-hand side of (2.4) modulo $p^{e}$ are those for which $m$ is of the
form $\frac{p-1}{2}+sp$ for some $s$. This leads directly to (4.12). ∎

By iteration of the recurrence in (4.12), we obtain the following non-
recursive congruence.

######  Lemma 12.

Under the assumptions of Lemma 11, we have

$u\left(\tfrac{ep-1}{2}\right)\equiv\sum_{k\geq
0}\sum_{\frac{e-1}{2}=\alpha_{0}>\alpha_{1}>\dots>\alpha_{k}\geq
0}(-1)^{k}\Pi_{1}\left(\tfrac{p-1}{2}+\alpha_{k}p\right)\\\
\cdot\prod_{j=0}^{k-1}\binom{(2\alpha_{j}+1)p}{(2\alpha_{j+1}+1)p}\Pi_{3}\big{(}(\alpha_{j}-\alpha_{j+1})p\big{)}\pmod{p^{e}}.$
(4.14)

###### Proof.

We show the claim by an induction on $e$. For the start of the induction, we
observe that for $e=1$ the sum on the right-hand side of (4.14) reduces to a
single term for $k=0$ and $\alpha_{0}=0$, which turns out to equal
$u(\frac{p-1}{2})$, in agreement with the claim.

For the induction step, we observe that, by (4.1), we have
$v_{p}\big{(}\Pi_{3}(ip)\big{)}\geq 2i$. Hence we may consider the term
$u\left(\tfrac{ep-1}{2}-ip\right)$ in (4.12) modulo $p^{e-2i}$. This allows us
to substitute the right-hand side of (4.14) for $e$ replaced by $e-2i$ in
(4.12). If, at the same time, we replace $\alpha_{j}$ by $\alpha_{j+1}$ for
all $j$, then this leads us to

$\displaystyle u\left(\tfrac{ep-1}{2}\right)$
$\displaystyle\equiv\Pi_{1}\left(\tfrac{ep-1}{2}\right)$ $\displaystyle\kern
14.22636pt-\sum_{i=1}^{(e-1)/2}\binom{ep}{(e-2i)p}\Pi_{3}(ip)\sum_{k\geq
0}\sum_{\frac{e-1}{2}-i=\alpha_{1}>\alpha_{2}>\dots>\alpha_{k+1}\geq
0}(-1)^{k}\Pi_{1}\left(\tfrac{p-1}{2}+\alpha_{k+1}p\right)$
$\displaystyle\kern
142.26378pt\cdot\prod_{j=1}^{k}\binom{(2\alpha_{j}+1)p}{(2\alpha_{j+1}+1)p}\Pi_{3}\big{(}(\alpha_{j}-\alpha_{j+1})p\big{)}\pmod{p^{e}}.$

Setting $\alpha_{0}=\frac{e-1}{2}$, we realise that the right-hand side can be
put together in the form of the expression on the right-hand side of (4.14)
with $k$ replaced by $k+1$. This concludes the induction step and, hence, the
induction argument. ∎

##  5\. The sequence $(v(n))_{n\geq 0}$ modulo odd prime powers

Here, we analyse the numbers $v(n)$ modulo odd prime powers $p^{e}$. The first
result is Theorem 13 which says that also $v(n)$ vanishes modulo $p^{e}$ for
$n\geq\left\lceil ep^{2}/2\right\rceil$, for all odd primes and all positive
integers $e$. Again, should the prime $p$ be congruent to $1$ modulo 4, this
result can be significantly improved; see Theorem 15.

The following theorem proves Conjecture 18(1) in [12] for $v(n)$.

######  Theorem 13.

Let $(v(n))_{n\geq 0}$ be defined by the recurrence (2.6). Then, given an odd
prime $p$ and a positive integer $e,$ the number $v(n)$ is divisible by
$p^{e}$ for $n\geq\left\lceil\frac{ep^{2}}{2}\right\rceil$.

###### Proof.

In analogy with the proof of Theorem 7, we proceed by a double induction on
$e$ and $n$, the outer induction being on $e$. Clearly, the theorem is trivial
for $e=0$, which serves as the start of the induction.

Now let $n\geq\left\lceil\frac{ep^{2}}{2}\right\rceil$. By (4.1), the first
term on the right-hand side of (2.6) is divisible by $p^{e}$. We consider the
summand on the right-hand side of (2.6) for
$\left\lceil\frac{fp^{2}}{2}\right\rceil\leq
m<\left\lceil\frac{(f+1)p^{2}}{2}\right\rceil$ with $0\leq f<e$. By the
induction hypothesis applied to $v(m)$, we have $v_{p}(v(m))=f$. On the other
hand, if we apply the induction hypothesis to $v(n-m)$, then we obtain
$v_{p}(v(n-m))=e-f-1$ or $v_{p}(v(n-m))=e-f$, depending on whether or not
$n-m<\left\lceil\frac{(e-f)p^{2}}{2}\right\rceil$. In the latter case, we
infer that $v_{p}\big{(}v(m)v(n-m)\big{)}=f+(e-f)=e$, and hence the
corresponding summand in (2.6) is divisible by $p^{e}$.

On the other hand, in the former case, the conclusion is that
$v_{p}\big{(}v(m)v(n-m)\big{)}=e-1$. In order to show that the corresponding
summand is divisible by $p^{e}$, we must therefore prove that the binomial
coefficient in (2.6) is divisible by $p$ in this case. To see this, we
consider the $p$-adic representations of $2m$ and $2(n-m)$. These are

$\displaystyle(2m)_{p}$ $\displaystyle={}$ $\displaystyle(f)_{p}\ *\ *$
$\displaystyle\big{(}2(n-m)\big{)}_{p}$ $\displaystyle={}$
$\displaystyle(e-f-1)_{p}\ *\ *$ (5.1)

Here, $(\alpha)_{p}$ denotes the $p$-adic representation of the integer
$\alpha$, and the two stars on the right-hand sides indicate the right-most
two digits of $(2m)_{p}$ and $(2(n-m))_{p}$ whose precise values are
irrelevant. The sum of $2m$ and $2(n-m)$ is $2n$ whose $p$-adic representation
has the form $(e)_{p}\ *\ *$. Hence, when adding the two numbers on the right-
hand sides of (5.1), at least one carry must occur — namely one from the
$p$-digit to the $p^{2}$-digit. By Kummer’s theorem in Lemma 4, the
consequence is that the binomial coefficient $\binom{2n}{2m}$ is divisible by
$p$. Therefore, again, the corresponding summand is divisible by $p^{e}$.

Finally, if $\left\lceil\frac{ep^{2}}{2}\right\rceil\leq m<n$, by the
induction hypothesis (for $n$), the number $v(m)$ is divisible by $p^{e}$,
which of course implies divisibility of the corresponding summand by $p^{e}$.

This concludes the induction step, and, thus, the proof of the theorem. ∎

######  Remark 14.

An examination of the above arguments reveals that the product $\Pi_{3}(n)$ in
the definition (2.6) could have been replaced with any function $f(n)$ that
satisfies the $p$-divisibility property in (4.1).

######  Theorem 15.

Let $(v(n))_{n\geq 0}$ be defined by the recurrence (2.6). Then, given a
prime$p\equiv 1$ (mod $4$) and a positive integer $e,$ the number $v(n)$ is
divisible by $p^{e}$ for $n\geq\left\lceil\frac{ep}{2}\right\rceil$.

###### Proof.

In analogy with the proof of Theorem 7, we proceed by a double induction on
$e$ and $n$, the outer induction being on $e$. Clearly, the theorem is trivial
for $e=0$, which serves as the start of the induction.

Now let $n\geq\left\lceil\frac{ep}{2}\right\rceil$. Hence, by (4.2) for
$n\geq\left\lceil ep/2\right\rceil$ we have

$v_{p}\big{(}\Pi_{3}(n)\big{)}\geq
2\left\lfloor\frac{\left\lceil\frac{ep}{2}\right\rceil+\frac{3}{4}(p-1)}{p}\right\rfloor\geq
2\left\lfloor{\frac{e}{2}+\frac{3}{4}-\frac{3}{4p}}\right\rfloor\geq e.$

Thus, the first term on the right-hand side of (2.6) is divisible by $p^{e}$.

We consider the summand on the right-hand side of (2.6) for
$\left\lceil\frac{fp}{2}\right\rceil\leq
m<\left\lceil\frac{(f+1)p}{2}\right\rceil$ with $0\leq f<e$. By the induction
hypothesis applied to $v(m)$, we have $v_{p}(v(m))=f$. On the other hand, if
we apply the induction hypothesis to $v(n-m)$, then we obtain
$v_{p}(v(n-m))=e-f-1$ or $v_{p}(v(n-m))=e-f$, depending on whether or not
$n-m<\left\lceil\frac{(e-f)p}{2}\right\rceil$. In the latter case, we infer
that $v_{p}\big{(}v(m)v(n-m)\big{)}=f+(e-f)=e$, and hence the corresponding
summand in (2.6) is divisible by $p^{e}$.

On the other hand, in the former case, the conclusion is that
$v_{p}\big{(}v(m)v(n-m)\big{)}=e-1$. In order to show that the corresponding
summand is divisible by $p^{e}$, we must therefore prove that the binomial
coefficient in (2.6) is divisible by $p$ in this case. To see this, we
consider the $p$-adic representations of $2m$ and $2(n-m)$. These are

$\displaystyle(2m)_{p}$ $\displaystyle={}$ $\displaystyle(f)_{p}\ *$
$\displaystyle\big{(}2(n-m)\big{)}_{p}$ $\displaystyle={}$
$\displaystyle(e-f-1)_{p}\ *$ (5.2)

Here as before, $(\alpha)_{p}$ denotes the $p$-adic representation of the
integer $\alpha$, and the stars on the right-hand sides indicate the right-
most digits of $(2m)_{p}$ and $(2(n-m))_{p}$ whose precise values are
irrelevant. The sum of $2m$ and $2(n-m)$ is $2n$ whose $p$-adic representation
has the form $(e)_{p}\ *$. Hence, when adding the two numbers on the right-
hand sides of (5.2), at least one carry must occur — namely one from the
$p^{0}$-digit to the $p^{1}$-digit. By Kummer’s theorem in Lemma 4, the
consequence is that the binomial coefficient $\binom{2n}{2m}$ is divisible by
$p$. Therefore, again, the corresponding summand is divisible by $p^{e}$.

Finally, if $\left\lceil\frac{ep^{2}}{2}\right\rceil\leq m<n$, by the
induction hypothesis (for $n$), the number $v(m)$ is divisible by $p^{e}$,
which of course implies divisibility of the corresponding summand by $p^{e}$.

This concludes the induction step, and, thus, the proof of the theorem. ∎

######  Remark 16.

An examination of the above arguments reveals that the product $\Pi_{3}(n)$ in
the definition (2.6) could have been replaced with any function $f(n)$ that
satisfies the $p$-divisibility property in (4.2).

##  6\. The matrix $\mathbf{R}$ modulo prime powers $p^{e}$ with $p\equiv
3~{}(\text{mod }4)$

The goal of this section is to derive a divisibility result for the matrix
entries $R(n,k)$ by prime powers $p^{e}$ with $p\equiv 3$ (mod 4) that would
allow us to carry through an inductive proof of Theorem 1(1) via the use of
the recurrence (2.9). This will be eventually achieved in Corollary 20, which
is based on Theorem 19, the main result in this section. It requires an
auxiliary result that is stated and proved separately in Lemma 18.

Our starting point here is the same as the one in [10] and [12]: a
straightforward expansion of the expression on the right-hand side of (2.7)
that defines $r(n,k)$ in the form

$2^{-(n-k)}r(n,k)={\sum}{}^{\displaystyle\prime}\frac{(2n)!}{\prod_{i=1}^{2n}i!^{c_{i}}c_{i}!}\prod_{i=1}^{2n}u\big{(}\tfrac{i-1}{2}\big{)}^{c_{i}},$
(6.1)

where the sum $\sum\\!{}^{\prime}$ is over all tuples
$(c_{1},c_{2},\dots,c_{2n})$ of non-negative integers $c_{i}$, where
$c_{2j}=0$ for all $j$, and

$\displaystyle c_{1}+c_{3}+\dots+c_{2n-1}$ $\displaystyle=2k,$ $\displaystyle
c_{1}+3c_{3}+\dots+(2n-1)c_{2n-1}$ $\displaystyle=2n.$

In the sequel, inspired by [10], we write $\mathcal{P}_{N,K}$ for the set of
all tuples $(c_{1},c_{2},\dots,c_{N})$ of non-negative integers with

$\displaystyle c_{1}+c_{2}+\dots+c_{N}$ $\displaystyle=K,$ (6.2)
$\displaystyle c_{1}+2c_{2}+\dots+Nc_{N}$ $\displaystyle=N.$ (6.3)

Furthermore, we write $\mathcal{P}^{o}_{N,K}$ for the set of tuples
$(c_{1},c_{2},\dots,c_{N})$ of non-negative integers $c_{i}$ for which
$c_{2j}=0$ for all $j$, and which satisfy

$\displaystyle c_{1}+c_{3}+\dots+c_{2n-1}$ $\displaystyle=K,$ (6.4)
$\displaystyle c_{1}+3c_{3}+\dots+(2n-1)c_{2n-1}$ $\displaystyle=N,$ (6.5)

with $n=\left\lceil N/2\right\rceil$. It should be noted that, if $N$ and $K$
do not have the same parity, then the set $\mathcal{P}^{o}_{N,K}$ is empty.
Clearly, $\mathcal{P}^{o}_{N,K}$ is a subset of $\mathcal{P}_{N,K}$. The sum
in (6.1) is over all tuples $(c_{i})$ in $\mathcal{P}^{o}_{2n,2k}$.

We recall that the ratio of factorials in (6.1) is an integer.

######  Lemma 17 ([1, Theorem 13.2]).

Let $N$ and $K$ be positive integers such that $N\geq K$. For all tuples
$(c_{i})_{1\leq i\leq N}$ in $\mathcal{P}_{N,K},$ the quantity

$\frac{N!}{\prod_{i=1}^{N}i!^{c_{i}}c_{i}!}$

is an integer, and it equals the number of partitions of the set
$\\{1,2,\dots,N\\}$ into $c_{i}$ blocks of size $i,$ for $i=1,2,\dots,N$.

The auxiliary result below is the key to the proof of the main theorem of this
section, Theorem 19.

######  Lemma 18.

Let $N,K,e,f$ be non-negative integers with $N\geq K,$ and let $p$ be a prime
number with $p\equiv 3$ (mod $4$). If $N\geq{{ep}}$ and $K<{fp},$ then we have

$\sum_{i=1}^{N}c_{i}(s_{p}(i)-1)+p\sum_{i=1}^{N}c_{i}v_{p}\left(u(\tfrac{i-1}{2})\right)\geq
e-f+1$ (6.6)

for all tuples $(c_{i})_{1\leq i\leq N}$ in $\mathcal{P}^{o}_{N,K}$.

###### Proof.

We denote the left-hand side in (6.6) by $E(N,K)$. We prove the assertion by
induction on $N$. For the start of the induction, we observe that the lemma is
trivially true for $N<p$. For, in that case we have $0\leq K\leq N<p$, hence,
with $e=0$ and $f=1$, the assertion says that the left-hand side in (6.6) is
bounded below by $e-f+1=0$, which is obviously the case.

We now proceed to the induction step.

(I) We assume first that all $i$’s with $c_{i}\neq 0$ are of the form $gp+1$
for a non-negative integer $g$. Let these $i$’s be $g_{j}p+1$, $1\leq j\leq
r$, with multiplicity $a_{j}>0$. In this notation, the relations (6.4) and
(6.5) become

$\displaystyle a_{1}+a_{2}+\dots+a_{r}$ $\displaystyle=K,$ $\displaystyle
a_{1}(g_{1}p+1)+a_{2}(g_{2}p+1)+\dots+a_{r}(g_{r}p+1)$ $\displaystyle=N.$

We have

$E(N,K)\geq\sum_{i=1}^{N}c_{i}(s_{p}(i)-1)\geq\sum_{j=1}^{r}a_{j}(g_{j}+1-1)=\sum_{j=1}^{r}a_{j}g_{j}=\frac{1}{p}(N-K).$

If we now remember that $N\geq ep$ and $K<fp$, then the conclusion is
$E(N,K)>e-f$, as desired.

(II) Next we assume that there exists an $I$ with $c_{I}\geq 1$, and such that
$I$ is not of the form $gp+1$ for a non-negative integer $g$. We choose $h$
such that $I=I_{0}+hp$, with $0\leq I_{0}<p$. Furthermore, we let

$I=I_{0}+I_{1}p+I_{2}p^{2}+\dots+I_{s}p^{s},$

with $0\leq I_{j}<p$ for all $j$, be the $p$-adic representation of $I$.
Clearly, we have

$h=I_{1}+I_{2}p+\dots+I_{s}p^{s-1}.$

By the definition of $s_{p}(I)$ and Theorem 7, we then have

$\displaystyle(s_{p}(I)-1)+pv_{p}\left(u(\tfrac{I-1}{2})\right)$
$\displaystyle\geq(I_{0}+I_{1}+I_{2}+\dots+I_{s}-1)+p(I_{2}+I_{3}p+\dots+I_{s}p^{s-2})$
$\displaystyle\geq I_{0}+h+I_{2}+\dots+I_{s}-1.$ (6.7)

We now discuss several cases separately.

Case 1. Two of the digits $I_{0},I_{2},I_{3},\dots,I_{s}$ are positive. Then,
from (6.7), we infer

$(s_{p}(I)-1)+pv_{p}\left(u(\tfrac{I-1}{2})\right)\geq h+1.$ (6.8)

Therefore, we have

$\displaystyle E(N,K)$
$\displaystyle=\sum_{i=1}^{N}c_{i}(s_{p}(i)-1)+p\sum_{i=1}^{N}c_{i}v_{p}\left(u(\tfrac{i-1}{2})\right)$
$\displaystyle\geq\sum_{i=1}^{N}c^{\prime}_{i}(s_{p}(i)-1)+p\sum_{i=1}^{N}c^{\prime}_{i}v_{p}\left(u(\tfrac{i-1}{2})\right)+h+1$
$\displaystyle\geq E(N-I,K-1)+h+1,$ (6.9)

where, by definition, $c_{i}^{\prime}=c_{i}$ for $i\neq I$, and
$c_{I}^{\prime}=c_{I}-1$. We have

$N-I\geq ep-(hp+I_{0})\geq(e-h-1)p.$

Therefore, by the induction hypothesis for $N-I$ (with $K$ replaced by $K-1$),
we find that

$E(N-I,K-1)\geq(e-h-1)-f+1.$

If this is substituted in (6.9), we obtain the desired estimate $E(N,K)\geq
e-f+1$.

Case 2. $I_{0}=0$ and one of the digits $I_{2},I_{3},\dots,I_{s}$ is positive.
Then, from (6.7) and Theorem 7, we infer

$(s_{p}(I)-1)+pv_{p}\left(u(\tfrac{I-1}{2})\right)\geq h+p\geq h+1.$

The remaining arguments are the same as in Case 1.

Case 3. $I_{0}\geq 2$. Then, from (6.7), we infer that also here the
inequality in (6.8) holds. The remaining arguments are the same as in Case 1.

Case 4. $I_{0}=1$ and $I_{2}=I_{3}=\dots=I_{s}=0$. This case is void since we
assumed that $I$ is not of the form $ap+1$.

Case 5. $I_{0}=I_{2}=I_{3}=\dots=I_{s}=0$. Here we have $I=gp$ with $1\leq
g<p$. By Theorem 7 (see in particular the second assertion), we get

$(s_{p}(I)-1)+pv_{p}\left(u(\tfrac{I-1}{2})\right)\geq(g-1)+p\geq g+1.$

Again, the remaining arguments are the same as in Case 1.

Parts (I) and (II) do indeed cover all possibilities: for, we may find $I$
with $c_{I}\geq 1$, not of the form $ap+1$ for a non-negative integer $a$.
This case is covered by Part (II). If not, all $i$’s with $c_{i}\neq 0$ are of
the form $ap+1$. This case is covered by Part (I). This concludes the proof of
the lemma. ∎

The main result in this section is the following divisibility result.

######  Theorem 19.

Let $N,K,e,f$ be non-negative integers with $N\geq K,$ and let $p$ be a prime
number with $p\equiv 3$ (mod $4$). If $N\geq ep^{2}$ and $K<fp^{2},$ then

$\sum_{(c_{i})\in\mathcal{P}^{o}_{N,K}}\frac{N!}{\prod_{i=1}^{N}i!^{c_{i}}c_{i}!}\prod_{i=1}^{N}u\big{(}\tfrac{i-1}{2}\big{)}^{c_{i}}$
(6.10)

is divisible by $p^{e-f+1}$.

Before we proceed to the proof, we state the immediate corollary that
followsfrom (6.1) and is relevant for the proof of the main result in the next
section. It is obtained as the special case where $N=2n$ and $K=2k$.

######  Corollary 20.

Let $n,k,e,f$ be non-negative integers with $n\geq k,$ and let $p$ be a prime
number with $p\equiv 3$ (mod $4$). If
$n\geq\left\lceil\frac{ep^{2}}{2}\right\rceil$ and
$k<\left\lceil\frac{fp^{2}}{2}\right\rceil,$ then $r(n,k)$ is divisible by
$p^{e-f+1}$.

###### Proof of Theorem 19.

We claim that each individual summand in (6.10) is divisible by $p^{e-f+1}$.
In order to see this, we apply Legendre’s formula in Lemma 3 to this summand,
and obtain

$\displaystyle(p-1)$ $\displaystyle
v_{p}\Bigg{(}\frac{N!}{\prod_{i=1}^{N}i!^{c_{i}}c_{i}!}\prod_{i=1}^{N}u\big{(}\tfrac{i-1}{2}\big{)}^{c_{i}}\Bigg{)}$
$\displaystyle=N-s_{p}(N)-\sum_{i=1}^{N}c_{i}(i-s_{p}(i))-\sum_{i=1}^{N}(c_{i}-s_{p}(c_{i}))+(p-1)\sum_{i=1}^{N}c_{i}v_{p}\left(u\big{(}\tfrac{i-1}{2}\big{)}\right)$
$\displaystyle=\sum_{i=1}^{N}c_{i}s_{p}(i)-\sum_{i=1}^{N}(c_{i}-s_{p}(c_{i}))-s_{p}\Bigg{(}\sum_{i=1}^{N}ic_{i}\Bigg{)}+(p-1)\sum_{i=1}^{N}c_{i}v_{p}\left(u\big{(}\tfrac{i-1}{2}\big{)}\right).$
(6.11)

We denote the last line in (6.11) by $F(N,K)$. In order to prove the theorem,
we must show that

$F(N,K)\geq(p-1)(e-f+1).$ (6.12)

We are going to prove this by induction on $N$. For the start of the
induction, we observe that the claim is trivially true for $N<p$. For, in that
case, we have $0\leq K\leq N<p$, hence, with $e=0$ and $f=1$, the assertion
says that $F(N,K)$ is bounded below by $(p-1)(e-f+1)=0$, which is the case
because of Lemma 17.

We now proceed to the induction step.

(I) We assume first that all $c_{i}$’s are divisible by $p$. We write
$c_{i}=pc_{i}^{\prime}$ and substitute this in the definition of $F(N,K)$:

$\displaystyle F(N,K)$
$\displaystyle=\sum_{i=1}^{N}pc_{i}^{\prime}s_{p}(i)-\sum_{i=1}^{N}(pc_{i}^{\prime}-s_{p}(pc_{i}^{\prime}))$
$\displaystyle\kern 56.9055pt-
s_{p}\Bigg{(}\sum_{i=1}^{N}pic_{i}^{\prime}\Bigg{)}+(p-1)\sum_{i=1}^{N}pc_{i}^{\prime}v_{p}\left(u\big{(}\tfrac{i-1}{2}\big{)}\right)$
$\displaystyle=(p-1)\sum_{i=1}^{N}c_{i}^{\prime}(s_{p}(i)-1)+(p-1)p\sum_{i=1}^{N}c_{i}^{\prime}v_{p}\left(u\big{(}\tfrac{i-1}{2}\big{)}\right)$
$\displaystyle\kern
56.9055pt+\sum_{i=1}^{N}c_{i}^{\prime}s_{p}(i)-\sum_{i=1}^{N}(c_{i}^{\prime}-s_{p}(c_{i}^{\prime}))-s_{p}\Bigg{(}\sum_{i=1}^{N}ic_{i}^{\prime}\Bigg{)}.$

The tuple $(c_{1}^{\prime},c_{2}^{\prime},\dots,c_{N}^{\prime})$ is an element
of $P^{o}_{N/p,K/p}$. In particular, the above sums can be truncated to run
over $i=1,2,\dots,N/p$. Lemma 18 with $N$ replaced by $N/p$, $K$ replaced by
$K/p$, $c_{i}$ replaced by $c_{i}^{\prime}$, then says that the expression in
the next-to-last line is at least $(p-1)(e-f+1)$. Lemma 17 implies that the
expression in the last line is non-negative. This proves our claim in the
current case.

(II) Next we assume that there exists an $I$ with $c_{I}\geq 1$, and such that
$I$ is not divisible by $p$. Then, writing $c_{i}^{\prime}=c_{i}$ for $i\neq
I$, and $c_{I}^{\prime}=c_{I}-1$, we have

$\displaystyle F(N,K)$
$\displaystyle=\sum_{i=1}^{N}c_{i}^{\prime}s_{p}(i)+s_{p}(I)-\sum_{i=1}^{N}(c_{i}^{\prime}-s_{p}(c_{i}^{\prime}))$
$\displaystyle\kern 56.9055pt-
s_{p}\Bigg{(}\sum_{i=1}^{N}ic_{i}^{\prime}+I\Bigg{)}+(p-1)\left(\sum_{i=1}^{N}c_{i}^{\prime}v_{p}\left(u\big{(}\tfrac{i-1}{2}\big{)}\right)+v_{p}\left(u\big{(}\tfrac{I-1}{2}\big{)}\right)\right)$
$\displaystyle\kern-34.14322pt\geq
F(N-I,K-1)+s_{p}(I)+s_{p}\Bigg{(}\sum_{i=1}^{N}ic_{i}^{\prime}\Bigg{)}-s_{p}\Bigg{(}\sum_{i=1}^{N}ic_{i}^{\prime}+I\Bigg{)}+(p-1)v_{p}\left(u\big{(}\tfrac{I-1}{2}\big{)}\right).$
(6.13)

By Lemma 5, we observe that

$s_{p}(I)+s_{p}\Bigg{(}\sum_{i=1}^{N}ic_{i}^{\prime}\Bigg{)}-s_{p}\Bigg{(}\sum_{i=1}^{N}ic_{i}^{\prime}+I\Bigg{)}=(p-1)C,$

where $C$ is the number of carries when adding $I$ and
$\sum_{i=1}^{N}ic_{i}^{\prime}=N-I$ in their $p$-adic representations. Now we
consider the $p$-adic representations of $N$ and $I$. Choose $g$ such that
$gp^{2}\leq I<(g+1)p^{2}$. Then, schematically, the $p$-adic representations
of $N$ and $I$ are

$\displaystyle(N)_{p}$ $\displaystyle={}$ $\displaystyle(e)_{p}\ *\ *$
$\displaystyle(I)_{p}$ $\displaystyle={}$ $\displaystyle(g)_{p}\ *\ *$ (6.14)

Again, $(\alpha)_{p}$ denotes the $p$-adic representation of the integer
$\alpha$, and the two stars on the right-hand sides indicate the right-most
two digits of $(N)_{p}$ and $(I)_{p}$ whose precise values are irrelevant.
(Here, we implicitly assume that $e$ is chosen maximally in the statement of
the theorem, which we can do without loss of generality.)

We have

$N-I\geq ep^{2}-(gp^{2}+p^{2}-1)\geq(e-g-1)p^{2}.$

Therefore, there are two possibilities: the $p$-adic representation of $N-I$
is $(N-I)=(e-g)_{p}\ *\ *$, or it is $(N-I)_{p}=(e-g-1)_{p}\ *\ *$. Comparing
with (6.14), we see that, in the latter case, we have $C\geq 1$.

We now apply the induction hypothesis for $N-I$ (with $K$ replaced by $K-1$).
If $(N-I)=(e-g)_{p}\ *\ *$, we find that

$F(N-I,K-1)+(p-1)C\geq(p-1)\big{(}(e-g)-f+1\big{)},$

while, if $(N-I)=(e-g-1)_{p}\ *\ *$, we find that

$\displaystyle F(N-I,K-1)+(p-1)C$
$\displaystyle\geq(p-1)\big{(}(e-g-1)-f+1\big{)}+(p-1)C$
$\displaystyle\geq(p-1)(e-g-f+1).$

We substitute this in (6.13) and also use that
$v_{p}\left(u\big{(}\tfrac{I-1}{2}\big{)}\right)\geq g$, by Theorem 7, since
$I\geq gp^{2}$. The result is

$F(N,K)\geq(p-1)(e-f-g+1)+(p-1)g=(p-1)(e-f+1),$

as desired.

This completes the proof of the theorem. ∎

##  7\. The sequence $(d(n))_{n\geq 0}$ modulo prime powers $p^{e}$ with
$p\equiv 3~{}(\text{mod }4)$

We are now in a position to prove our first main result. The following theorem
proves Conjecture 18(3) in [12], in the stronger form given in Theorem 1(1).

######  Theorem 21.

Given a prime $p$ with $p\equiv 3$ (mod $4$) and a positive integer $e,$ the
number $d(n)$ is divisible by $p^{e}$ for
$n\geq\left\lceil\frac{ep^{2}}{2}\right\rceil$.

###### Proof.

We prove the assertion by induction on $n$. Let
$n\geq\left\lceil\frac{ep^{2}}{2}\right\rceil$. We use the recurrence (2.9).
By Theorem 13, we know that $v(n)$ is divisible by $p^{e}$. On the other hand,
consider some $k$ with $\left\lceil\frac{(f-1)p^{2}}{2}\right\rceil\leq
k<\left\lceil\frac{fp^{2}}{2}\right\rceil$. By the induction hypothesis and
Corollary 20, we have

$v_{p}\big{(}r(n,k)d(k)\big{)}\geq(e-f+1)+(f-1)=e.$

In other words, each term on the right-hand side of (2.9) is divisible by
$p^{e}$, hence so is $d(n)$, as desired. ∎

##  8\. The sequence $(v(n))_{n\geq 0}$ modulo powers of $2$

The purpose of this section is to show periodicity of the sequence
$\big{(}v(n)\big{)}_{n\geq 0}$ modulo powers of 2, together with a precise
statement on the period length. The corresponding analysis is much more
involved than the preceding ones modulo odd prime powers. Our starting point
is an expansion that is very similar in spirit to the one in Section 6, namely
(8.18). As a matter of fact, the main results of this section concern a
polynomial refinement of $v(n)$ in which the product
$\Pi_{3}(j)=\prod_{\ell=1}^{j}(4\ell-3)^{2}$ gets replaced by a variable
$x(j)$, $j=0,1,\dots$, with the only restriction that $x(0)=1$ and that both
$x(1)$ and $x(2)$ are odd.

The main results in Theorems 28 and 29 need substantial preparations. These
are the contents of Lemma 22, Corollaries 23 and 24, and Lemmas 25–27, which
provide formulae and bounds for the 2-adic valuation of the ratios of
factorials that appear in the expansion (8.18).

######  Lemma 22.

For all positive integers $n$ and $c_{2}$ with $n\geq 2c_{2},$ we have

$v_{2}\left(\frac{(2n)!}{2!^{n-2c_{2}}(n-2c_{2})!\,4!^{c_{2}}c_{2}!}\right)=\\#(\text{\em
carries when adding $(n-2c_{2})_{2}$ and $(2c_{2})_{2}$}),$ (8.1)

where, as before, $(\alpha)_{2}$ denotes the $2$-adic representation of the
integer $\alpha$.

###### Proof.

By Legendre’s formula in Lemma 3, we obtain

$\displaystyle v_{2}$
$\displaystyle\left(\frac{(2n)!}{2!^{n-2c_{2}}(n-2c_{2})!\,4!^{c_{2}}c_{2}!}\right)$
$\displaystyle\kern
42.67912pt=2n-s_{2}(2n)-(n-2c_{2})-\big{(}n-2c_{2}-s_{2}(n-2c_{2})\big{)}-3c_{2}-(c_{2}-s_{2}(c_{2}))$
$\displaystyle\kern 42.67912pt=-s_{2}(n)+s_{2}(n-2c_{2})+s_{2}(2c_{2}).$

By Lemma 5, this is indeed the number of carries when adding $n-2c_{2}$ and
$2c_{2}$ in their $2$-adic representations. ∎

######  Corollary 23.

For all positive integers $n,$ we have

$v_{2}\left(\frac{(2n)!}{2!^{n-2}(n-2)!\,4!}\right)=\begin{cases}v_{2}(n)-1,&\text{if
$n$ is even,}\\\\[2.84526pt] v_{2}(n-1)-1,&\text{if $n$ is odd}.\end{cases}$

###### Proof.

We appeal to Lemma 22 with $c_{2}=1$. If $n$ is even, say
$n=2^{v_{2}(n)}n_{0}$ for an odd integer $n_{0}$ and $v_{2}(n)\geq 1$, then
the number of carries in (8.1) is $v_{2}(n)-1$. On the other hand, if $n$ is
odd, say $n=2^{v_{2}(n-1)}n_{0}+1$ for an odd integer $n_{0}$, then this
number of carries is $v_{2}(n-1)-1$. ∎

######  Corollary 24.

For all positive integers $n$, we have

$v_{2}\left(\frac{(2n)!}{2!^{n-4}(n-4)!\,4!^{2}2!}\right)=\begin{cases}v_{2}(n)-2,&\text{if
$n\equiv 0$ {\em(mod $4$)},}\\\\[2.84526pt] v_{2}(n-1)-2,&\text{if $n\equiv 1$
{\em(mod $4$)},}\\\\[2.84526pt] v_{2}(n-2)-2,&\text{if $n\equiv 2$ {\em(mod
$4$)},}\\\\[2.84526pt] v_{2}(n-3)-2,&\text{if $n\equiv 3$ {\em(mod
$4$)}.}\end{cases}$

###### Proof.

Again, we appeal to Lemma 22, here with $c_{2}=2$. If $n\equiv 0$ (mod $4$),
say $n=2^{v_{2}(n)}n_{0}$ for an odd integer $n_{0}$ and $v_{2}(n)\geq 2$,
then the number of carries in (8.1) is $v_{2}(n)-2$. The other cases are
treated similarly. We leave the details to the reader. ∎

######  Lemma 25.

For all positive integers $n$ and $c_{2}$ with $n\geq 2c_{2}\geq 6,$ we have

$c_{2}+v_{2}\left(\frac{(2n)!}{2!^{n-2c_{2}}(n-2c_{2})!\,4!^{c_{2}}c_{2}!}\right)\geq
1+\max\limits_{n-2c_{2}<i\leq n}v_{2}(i).$ (8.2)

###### Proof.

Choose $\alpha$ and $\beta$ such that $n=n_{0}2^{\alpha}+n_{1}$, with $n_{0}$
odd and $n_{1}<2^{\beta+2}$, and $2^{\beta}\leq c_{2}<2^{\beta+1}$. These
conditions imply that the $2$-adic representations can be schematically
indicated as

$\displaystyle\hphantom{\dots\,}\underset{\downarrow}{\scriptstyle\alpha}\kern
24.0pt\underset{\downarrow}{\scriptstyle\beta+2}\kern-5.0pt$
$\displaystyle(n)_{2}$ $\displaystyle={}$ $\displaystyle\dots\,10\,\dots\,0$
$\displaystyle*\,\dots$ $\displaystyle(2c_{2})_{2}$ $\displaystyle=$
$\displaystyle\kern 3.0pt1\,\dots$ (8.3)

with the meaning that the $1$ shown in the $2$-adic representation of $n$ is
the $\alpha$-th digit counted from right (the counting starting with $0$), and
that the left-most (non-zero) digit of the $2$-adic representation of $2c_{2}$
is the $(\beta+1)$-st digit, that is, $2c_{2}<2^{\beta+2}$.

First, we assume that $\beta\geq 2$. The case of $\beta=1$, which implies that
$2c_{2}=6$, will be disposed of at the end of this proof.

We distinguish two cases, depending on the relative sizes of $n_{1}$ and
$2c_{2}$.

Case 1: $n_{1}<2c_{2}$. Here, by inspection of (8.3), we see that

$\max\limits_{n-2c_{2}<i\leq n}v_{2}(i)=\alpha.$ (8.4)

On the other hand, by Lemma 22, the term $v_{2}(\,.\,)$ on the left-hand side
of (8.2) equals the number of carries when adding $n-2c_{2}$ and $2c_{2}$ in
their $2$-adic representations. Equivalently, this is the number of carries
when performing the subtraction of $(2c_{2})_{2}$ from $(n)_{2}$. Here,
inspection of (8.3) yields that this is at least $\alpha-(\beta+2)+1$. Thus,
together with (8.4) and the elementary inequality

$2^{\beta}\geq\beta+2\quad\text{for }\beta\geq 2,$ (8.5)

we get

$c_{2}+v_{2}\left(\frac{(2n)!}{2!^{n-2c_{2}}(n-2c_{2})!\,4!^{c_{2}}c_{2}!}\right)\geq
c_{2}+\alpha-\beta-1\geq 2^{\beta}+\alpha-\beta-1\\\
\geq\beta+2+\alpha-\beta-1=\alpha+1\geq 1+\max\limits_{n-2c_{2}<i\leq
n}v_{2}(i).$

Case 2: $n_{1}\geq 2c_{2}$. Now, by inspection of (8.3), we see that

$\max\limits_{n-2c_{2}<i\leq n}v_{2}(i)\leq\beta+1.$

Hence, using again (8.5), we get

$c_{2}+v_{2}\left(\frac{(2n)!}{2!^{n-2c_{2}}(n-2c_{2})!\,4!^{c_{2}}c_{2}!}\right)\geq
c_{2}\geq 2^{\beta}\geq\beta+2\geq 1+\max\limits_{n-2c_{2}<i\leq n}v_{2}(i).$

Finally we address the case where $\beta=1$, and thus $2c_{2}=6$. In this
case, the schematic representation (8.3) becomes

$\displaystyle\underset{\downarrow}{\scriptstyle\alpha}\kern
29.0pt\underset{\downarrow}{\scriptstyle 3}\kern 1.0pt$ $\displaystyle(n)_{2}$
$\displaystyle={}$ $\displaystyle\dots\,10\,\dots\,0$ $\displaystyle*\\!**$
$\displaystyle(6)_{2}$ $\displaystyle=$ $\displaystyle\kern 3.0pt110$

Here also, we must distinguish two cases depending on whether or not $n_{1}$
is greater than 6.

If $n_{1}<6$, then (8.4) holds. By Lemma 22, we then get

$c_{2}+v_{2}\left(\frac{(2n)!}{2!^{n-2c_{2}}(n-2c_{2})!\,4!^{c_{2}}c_{2}!}\right)\geq
3+(\alpha-2)=\alpha+1\geq 1+\max\limits_{n-2c_{2}<i\leq n}v_{2}(i).$

On the other hand, if $n_{1}\geq 6$ then

$\max\limits_{n-2c_{2}<i\leq n}v_{2}(i)\leq 2,$

and we obtain

$c_{2}+v_{2}\left(\frac{(2n)!}{2!^{n-2c_{2}}(n-2c_{2})!\,4!^{c_{2}}c_{2}!}\right)\geq
3\geq 1+\max\limits_{n-2c_{2}<i\leq n}v_{2}(i).$

This completes the proof of the lemma. ∎

######  Lemma 26.

For all positive integers $n$ and $c_{2}$ with $n\geq 2c_{2}+3,$ we have

$c_{2}+2+v_{2}\left(\frac{(2n)!}{2!^{n-2c_{2}-3}(n-2c_{2}-3)!\,4!^{c_{2}}c_{2}!\,6!}\right)\geq
1+\max\limits_{n-2c_{2}-3<i\leq n}v_{2}(i).$ (8.6)

###### Proof.

By Legendre’s formula in Lemma 3, we obtain

$\displaystyle v_{2}$
$\displaystyle\left(\frac{(2n)!}{2!^{n-2c_{2}-3}(n-2c_{2}-3)!\,4!^{c_{2}}c_{2}!\,6!}\right)$
$\displaystyle\kern
42.67912pt=2n-s_{2}(2n)-(n-2c_{2}-3)-\big{(}n-2c_{2}-3-s_{2}(n-2c_{2}-3)\big{)}$
$\displaystyle\kern 85.35826pt-3c_{2}-(c_{2}-s_{2}(c_{2}))-4$
$\displaystyle\kern
42.67912pt=-s_{2}(n)+s_{2}(n-2c_{2}-3)+s_{2}(2c_{2})+s_{2}(3)$
$\displaystyle\kern 42.67912pt\geq-s_{2}(n)+s_{2}(n-2c_{2}-3)+s_{2}(2c_{2}+3)$
$\displaystyle\kern 42.67912pt=\\#(\text{carries when adding
$(n-2c_{2}-3)_{2}$ and $(2c_{2}+3)_{2}$}).$

From here on we follow the setup and the arguments in the proof of Lemma 25,
with $2c_{2}+3$ in place of $2c_{2}$; see, in particular, the schematic
representation in (8.3) with that replacement. There is one notable
difference, though: here the lower bound on $c_{2}$ is zero (as opposed to $3$
in the proof of Lemma 25). This entails $2c_{2}+3\geq 3$, and hence the lower
bound on the parameter $\beta$ is $\beta\geq 0$. Thus, instead of (8.5), we
can only use $2^{\beta}\geq\beta+1$ here, a bound that is by $1$ weaker. This
is balanced by the additional summand $+2$ on the left-hand side of (8.6) when
compared to the left-hand side of (8.2). ∎

######  Lemma 27.

For all positive integers $n$ and tuples $(c_{1},c_{2},\dots,c_{n})$ in

$\mathcal{P}_{n,k}\backslash\\{(n,0,\dots,0),(n-2,1,0,\dots,0),(n-4,2,0,\dots,0)\\},$

we have

$n-k+v_{2}\left(\frac{(2n)!}{2!^{c_{1}}c_{1}!\,4!^{c_{2}}c_{2}!\cdots(2n)!^{c_{n}}c_{n}!}\right)\geq
1+\max\limits_{c_{1}<i\leq n}v_{2}(i).$ (8.7)

###### Proof.

By Legendre’s formula in Lemma 3, the $2$-adic valuation on the left-hand side
of (8.7) equals

$\displaystyle
v_{2}\left(\frac{(2n)!}{2!^{c_{1}}c_{1}!\,4!^{c_{2}}c_{2}!\cdots(2n)!^{c_{n}}c_{n}!}\right)$
$\displaystyle=2n-s_{2}(2n)-\sum_{i=1}^{n}\big{(}c_{i}(2i-s_{2}(2i))+c_{i}-s_{2}(c_{i})\big{)}$
$\displaystyle=\sum_{i=1}^{n}c_{i}s_{2}(i)-\sum_{i=1}^{n}\big{(}c_{i}-s_{2}(c_{i})\big{)}-s_{2}(n).$

Define the quantity $G(n,k)$ by

$G(n,k):=n-k+\sum_{i=1}^{n}c_{i}s_{2}(i)-\sum_{i=1}^{n}\big{(}c_{i}-s_{2}(c_{i})\big{)}-s_{2}(n).$

We must show that $G(n,k)$ is at least as large as the right-hand side of
(8.7). We achieve this by demonstrating that, among all elements
$(c_{1},c_{2},\dots,c_{n})\in\mathcal{P}_{n,k}$ with fixed $c_{1}$, the ones
with $c_{i}=0$ for $i\geq 4$ and $c_{3}=0$ or $c_{3}=1$, depending on the
parity of $n-c_{1}$, attain the smallest values of $G(n,k)$, and then
appealing to Lemmas 25 and 26.

First consider a tuple $(c_{1},c_{2},\dots,c_{n})$ in which $c_{2j}>0$ for
some $j\geq 2$. We claim that the value of $G(n,k)$ decreases if instead we
consider the tuple $(c_{1},c_{2}+jc_{2j},\dots,0,\dots,c_{n})$, with $0$
appearing in position $2j$. This new tuple is an element of
$\mathcal{P}_{n,k+(j-1)c_{2j}}$. In order to prove the claim, we compare the
contributions of the tuples to $G(n,k)$, ignoring the terms that are the same
for both tuples. In particular, we may ignore appearances of $n$ (such as in
$s_{2}(n)$) since $n$ is the same for both tuples (as opposed to $k$, which
becomes $k+(j-1)c_{2j}$ for the modified tuple). The — in this sense —
relevant contribution of $(c_{1},c_{2},\dots,c_{n})$ to $G(n,k)$ is

$c_{2}s_{2}(2)+c_{2j}s_{2}(2j)-(c_{2}-s_{2}(c_{2}))-(c_{2j}-s_{2}(c_{2j}))\\\\[2.84526pt]
=c_{2j}\big{(}s_{2}(j)-1\big{)}+s_{2}(c_{2})+s_{2}(c_{2j}).$ (8.8)

On the other hand, the (relevant) contribution of
$(c_{1},c_{2}+jc_{2j},\dots,0,\dots,c_{n})$ to$G(n,k+(j-1)c_{2j})$ is

$-(j-1)c_{2j}+(c_{2}+jc_{2j})s_{2}(2)-(c_{2}+jc_{2j}-s_{2}(c_{2}+jc_{2j}))=-(j-1)c_{2j}+s_{2}(c_{2}+jc_{2j}).$
(8.9)

The difference of (8.8) and (8.9) is

$\displaystyle c_{2j}\big{(}s_{2}(j)+j-2\big{)}+s_{2}(c_{2})+s_{2}(c_{2j})$
$\displaystyle-s_{2}(c_{2}+jc_{2j})$ $\displaystyle\geq
c_{2j}s_{2}(j)+(j-2)c_{2j}+s_{2}(c_{2j})-s_{2}(c_{2j}j)$
$\displaystyle\geq(j-2)c_{2j}+s_{2}(c_{2j})\geq s_{2}(c_{2j}),$

which is positive, thus proving our claim.

Now consider a tuple $(c_{1},c_{2},\dots,c_{n})$ in which $c_{2j+1}>0$ for
some $j\geq 2$. Again,we claim that the value of $G(n,k)$ (weakly) decreases
if instead we consider the
tuple$(c_{1},c_{2}+(j-1)c_{2j+1},c_{3}+c_{2j+1},\dots,0,\dots,c_{n})$, with
$0$ appearing in position $2j+1$. This new tuple is an element of
$\mathcal{P}_{n,k+(j-1)c_{2j+1}}$. In order to prove the claim, we compare the
contributions of the tuples to $G(n,k)$, ignoring the terms that are the same
for both tuples. The (relevant) contribution of $(c_{1},c_{2},\dots,c_{n})$ to
$G(n,k)$ is

$c_{2}s_{2}(2)+c_{3}s_{2}(3)+c_{2j+1}s_{2}(2j+1)-(c_{2}-s_{2}(c_{2}))-(c_{3}-s_{2}(c_{3}))-(c_{2j+1}-s_{2}(c_{2j+1}))\\\\[2.84526pt]
=c_{3}+c_{2j+1}s_{2}(j)+s_{2}(c_{2})+s_{2}(c_{3})+s_{2}(c_{2j+1}).\kern
56.9055pt$ (8.10)

On the other hand, the (relevant) contribution of
$(c_{1},c_{2}+(j-1)c_{2j+1},c_{3}+c_{2j+1},\dots,0,\break\dots,c_{n})$ to
$G(n,k+(j-1)c_{2j+1})$ is

$-(j-1)c_{2j+1}+(c_{2}+(j-1)c_{2j+1})s_{2}(2)+(c_{3}+c_{2j+1})s_{2}(3)\\\\[2.84526pt]
-(c_{2}+(j-1)c_{2j+1}-s_{2}(c_{2}+(j-1)c_{2j+1}))-(c_{3}+c_{2j+1}-s_{2}(c_{3}+c_{2j+1}))\\\\[2.84526pt]
=c_{3}-(j-2)c_{2j+1}+s_{2}(c_{2}+(j-1)c_{2j+1})+s_{2}(c_{3}+c_{2j+1}).$ (8.11)

The difference of (8.10) and (8.11) is

$\displaystyle c_{2j+1}\big{(}s_{2}(j)+j-2\big{)}$
$\displaystyle+s_{2}(c_{2})+s_{2}(c_{3})+s_{2}(c_{2j+1})$ $\displaystyle\kern
56.9055pt-s_{2}(c_{2}+(j-1)c_{2j+1})-s_{2}(c_{3}+c_{2j+1})$ $\displaystyle\geq
c_{2j+1}\big{(}s_{2}(j)+j-2\big{)}+s_{2}(c_{2})-s_{2}(c_{2}+(j-1)c_{2j+1})$
$\displaystyle\geq
c_{2j+1}\big{(}s_{2}(j)-1\big{)}+(j-1)c_{2j+1}-s_{2}((j-1)c_{2j+1})$
$\displaystyle\geq c_{2j+1}\big{(}s_{2}(j)-1\big{)},$

which is non-negative, as claimed.

So far, the above arguments show that we may restrict our attention to tuples
$(c_{1},c_{2},\dots,c_{n})$ in $\mathcal{P}_{n,k}$ with $c_{i}=0$ for $i\geq
4$. Finally, we argue that “$3$’s can be traded for $2$’s”, that is, we may
decrease $c_{3}$ at the cost of increasing $c_{2}$. There are two cases to be
considered. First let $c_{3}$ be even, $c_{3}=2c_{3}^{\prime}$ say, with
$c_{3}^{\prime}\geq 1$. We claim that the value of $G(n,k)$ decreases if
instead of $(c_{1},c_{2},c_{3},\dots,c_{n})$ we consider the tuple
$(c_{1},c_{2}+3c_{3}^{\prime},0,\dots,c_{n})$, This new tuple is an element of
$\mathcal{P}_{n,k+c_{3}^{\prime}}$. In order to prove the claim, we compare
the contributions of the tuples to $G(n,k)$, ignoring the terms that are the
same for both tuples. The (relevant) contribution of
$(c_{1},c_{2},c_{3},\dots,c_{n})$ to $G(n,k)$ is

$c_{2}s_{2}(2)+c_{3}s_{2}(3)-(c_{2}-s_{2}(c_{2}))-(c_{3}-s_{2}(c_{3}))=c_{3}+s_{2}(c_{2})+s_{2}(c_{3}^{\prime}).$
(8.12)

On the other hand, the (relevant) contribution of
$(c_{1},c_{2}+3c_{3}^{\prime},0,\dots,c_{n})$ to $G(n,k+c_{3}^{\prime})$ is

$-c_{3}^{\prime}+(c_{2}+3c_{3}^{\prime})s_{2}(2)-(c_{2}+3c_{3}^{\prime}-s_{2}(c_{2}+3c_{3}^{\prime}))=-c_{3}^{\prime}+s_{2}(c_{2}+3c_{3}^{\prime}).$
(8.13)

The difference of (8.12) and (8.13) is

$\displaystyle
3c_{3}^{\prime}+s_{2}(c_{2})+s_{2}(c_{3}^{\prime})-s_{2}(c_{2}+3c_{3}^{\prime})$
$\displaystyle\geq
3c_{3}^{\prime}+s_{2}(c_{2}+c_{3}^{\prime})-s_{2}(c_{2}+3c_{3}^{\prime})$
$\displaystyle\geq 3c_{3}^{\prime}-s_{2}(2c_{3}^{\prime})\geq c_{3}^{\prime},$
(8.14)

which is positive, proving our claim.

Finally, let $c_{3}$ be odd, $c_{3}=2c_{3}^{\prime}+1$ say, with
$c_{3}^{\prime}\geq 1$. We claim that the value of $G(n,k)$ decreases if
instead of $(c_{1},c_{2},c_{3},\dots,c_{n})$ we consider the tuple
$(c_{1},c_{2}+3c_{3}^{\prime},1,\dots,c_{n})$, This new tuple is an element of
$\mathcal{P}_{n,k+c_{3}^{\prime}}$. In order to prove the claim, we compare
the contributions of the tuples to $G(n,k)$, ignoring the terms that are the
same for both tuples. The (relevant) contribution of
$(c_{1},c_{2},c_{3},\dots,c_{n})$ to $G(n,k)$ is

$c_{2}s_{2}(2)+c_{3}s_{2}(3)-(c_{2}-s_{2}(c_{2}))-(c_{3}-s_{2}(c_{3}))=c_{3}+s_{2}(c_{2})+s_{2}(c_{3}^{\prime})+1.$
(8.15)

On the other hand, the (relevant) contribution of
$(c_{1},c_{2}+3c_{3}^{\prime},1,\dots,c_{n})$ to $G(n,k+c_{3}^{\prime})$ is

$-c_{3}^{\prime}+(c_{2}+3c_{3}^{\prime})s_{2}(2)+s_{2}(3)-(c_{2}+3c_{3}^{\prime}-s_{2}(c_{2}+3c_{3}^{\prime}))\\\\[2.84526pt]
=-c_{3}^{\prime}+s_{2}(c_{2}+3c_{3}^{\prime})+2.$ (8.16)

The difference of (8.15) and (8.16) is the same as (8.14), of which we already
know that it is positive.

We are now in the position to finish the proof of the lemma. Our tuple
$(c_{1},c_{2},\dots,c_{n})$ may be one where $c_{i}=0$ for $i\geq 3$. Then
$c_{1}=n-2c_{2}$, $n-k=(c_{1}+2c_{2})-(c_{1}+c_{2})=c_{2}$, and $c_{2}\geq 3$
by assumption. The assertion of the lemma then follows from Lemma 25. On the
other hand, our tuple $(c_{1},c_{2},\dots,c_{n})$ may be one where $c_{3}=1$
and $c_{i}=0$ for $i\geq 4$. Then $c_{1}=n-2c_{2}-3$, and
$n-k=(c_{1}+2c_{2}+3)-(c_{1}+c_{2}+1)=c_{2}+2$. The assertion of the lemma
then follows from Lemma 26. If we are not in one of these two cases, then we
apply the above described reductions repeatedly until we arrive at a tuple
which belongs to one of these two cases. Since the value of $G(n,k)$ never
increases while the value of $c_{1}$ remains invariant when doing these
reductions, Lemmas 25 and 26 again establish the assertion of the lemma.

The proof is now complete. ∎

We are now in the position to embark on the proof of periodicity of $v(n)$ as
defined in (2.5) modulo powers of 2. The next theorem treats the “generic”
case where $e\geq 3$, whereas Theorem 29 handles the remaining cases where
$e=1$ or $e=2$. Both theorems provide in fact polynomial refinements.

######  Theorem 28.

Let $x(j),$ $j=0,1,2,\dots,$ be a sequence of integers with $x(0)=1,$ $x(1)$
and $x(2)$ odd. Then the coefficients $v_{\mathbf{x}}(n)$ in the expansion

$\sum_{n\geq
0}\frac{v_{\mathbf{x}}(n)}{2^{n}\,(2n)!}t^{n}=\Bigg{(}1+\sum_{j\geq
1}\frac{x(j)}{(2j)!}t^{2j}\Bigg{)}^{1/2}$ (8.17)

are integers. Moreover, for all integers $e\geq 3,$ the sequence
$(v_{\mathbf{x}}(n))_{n\geq 0}$ is purely periodic modulo $2^{e}$ with (not
necessarily minimal) period length $2^{e-1}$.

######  Remark.

Computer experiments suggest that, in fact, the period length of $2^{e-1}$ is
minimal.

###### Proof of Theorem 28.

We compute the defining expansion for the coefficients $v_{\mathbf{x}}(n)$:

$\displaystyle\sum_{n\geq 0}\frac{v_{\mathbf{x}}(n)}{2^{n}(2n)!}t^{n}$
$\displaystyle=\Bigg{(}1+\sum_{j\geq 1}\frac{x(j)}{(2j)!}t^{j}\Bigg{)}^{1/2}$
$\displaystyle=\sum_{k\geq 0}\binom{1/2}{k}\Bigg{(}\sum_{j\geq
1}\frac{x(j)}{(2j)!}t^{j}\Bigg{)}^{k}$ $\displaystyle=1+\sum_{k\geq
1}(-1)^{k-1}\frac{\prod_{j=1}^{k-1}(2j-1)}{2^{k}\,k!}{\sum_{c_{1}+c_{2}+\dots=k}}\frac{k!}{c_{1}!\,c_{2}!\cdots}\prod_{i\geq
1}\frac{x^{c_{i}}(i)}{(2i)!^{c_{i}}}t^{ic_{i}}.$

By comparing coefficients of $t^{n}$, we obtain

$v_{\mathbf{x}}(n)=\sum_{k\geq
1}\sum_{(c_{i})\in\mathcal{P}_{n,k}}(-1)^{k-1}\Bigg{(}\prod_{j=1}^{k-1}(2j-1)\Bigg{)}2^{n-k}\frac{(2n)!}{2!^{c_{1}}c_{1}!\,4!^{c_{2}}c_{2}!\cdots(2n)!^{c_{n}}c_{n}!}\prod_{i=1}^{n}{x^{c_{i}}(i)},$
(8.18)

where $\mathcal{P}_{n,k}$ is defined around (6.2)–(6.3). For convenience, we
denote the summand in the above double sum by $S(n,k,(c_{i}))$, that is, we
set

$S(n,k,(c_{i})):=(-1)^{k-1}\Bigg{(}\prod_{j=1}^{k-1}(2j-1)\Bigg{)}2^{n-k}\frac{(2n)!}{2!^{c_{1}}c_{1}!\,4!^{c_{2}}c_{2}!\cdots(2n)!^{c_{n}}c_{n}!}\prod_{i=1}^{n}{x^{c_{i}}(i)}$
(8.19)

for some positive integer $k$ and $(c_{i})\in\mathcal{P}_{n,k}$. The fraction
in the expression in (8.18) (and in (8.19)) is an integer since, by Lemma 17,
it is the number of all partitions of $\\{1,2,\dots,2n\\}$ into $c_{i}$ blocks
of size $2i$, $i=1,2,\dots,n$. If this property is used in (8.18), then this
establishes the integrality assertion of the theorem.

Now, let $n<2^{e-1}$. We want to prove that

$v_{\mathbf{x}}(n+a2^{e-1})\equiv v_{\mathbf{x}}(n)\pmod{2^{e}},$ (8.20)

for all positive integers $a$. Using our short notation for the summand in
(8.18), we have

$v_{\mathbf{x}}\big{(}n+a2^{e-1}\big{)}=\sum_{k\geq
1}\sum_{(\tilde{c}_{i})\in\mathcal{P}_{n+a2^{e-1},k}}S(n+a2^{e-1},k,(\tilde{c}_{i})).$
(8.21)

We are going to prove the finer congruences

$\displaystyle S(n+a2^{e-1},k,(\tilde{c}_{i}))$ $\displaystyle\equiv
0\pmod{2^{e}},\quad\text{if }\tilde{c}_{1}<a2^{e-1},$
$\displaystyle\kern-28.45274pt\text{$(\tilde{c}_{i})$ not in cases
\eqref{eq:exc1}--\eqref{eq:exc3}},$ (8.22) $\displaystyle
S(n+a2^{e-1},n+a2^{e-1},(n+a2^{e-1},0,\dots,0))$ $\displaystyle\equiv
S(n,n,(n,0,\dots,0))\pmod{2^{e}},$ (8.23) $\displaystyle
S(n+a2^{e-1},k+a2^{e-1},(\tilde{c}_{i}))$ $\displaystyle\equiv
S(n,k,(c_{1},\tilde{c}_{2},\dots,\tilde{c}_{n}))\pmod{2^{e}}$
$\displaystyle\kern-139.41832pt\text{with $\tilde{c}_{1}=c_{1}+a2^{e-1}$, and
$(\tilde{c}_{i})$ not in cases \eqref{eq:exc1}--\eqref{eq:exc3}},$ (8.24)
$\displaystyle
S(n+a2^{e-1},n+a2^{e-1}-1,(n+a2^{e-1}-2,1,0,\dots,0))\kern-28.45274pt$
$\displaystyle+S(n+a2^{e-1},n+a2^{e-1}-2,(n+a2^{e-1}-4,2,0,\dots,0))\kern-85.35826pt$
$\displaystyle\kern-142.26378pt\equiv S(n,n-1,(n-2,1,0,\dots,0))$
$\displaystyle\kern-85.35826pt+S(n,n-2,(n-4,2,0,\dots,0))\pmod{2^{e}}.$ (8.25)

In the last congruence, undefined terms (terms $S(n,k,(\tilde{c}_{i}))$ with
negative $\tilde{c}_{1}$) have to be understood as being zero.

We claim that (8.22)–(8.25) together imply (8.20), and thus the theorem. In
order to prove this, we consider the summand $S(n+a2^{e-1},k,(\tilde{c}_{i}))$
on the right-hand side of (8.21), when taken modulo $2^{e}$, for the various
choices of $k$ and tuples $(\tilde{c}_{i})$. If $\tilde{c}_{1}<a2^{e-1}$,
then, by (8.22), the corresponding summand vanishes modulo $2^{e}$. On the
other hand, if $\tilde{c}_{1}\geq a2^{e-1}$, then, since $k\geq\tilde{c}_{1}$,
we must also have $k\geq a2^{e-1}$. Consequently, we may apply (8.23) and
(8.24) to conclude that

$S(n+a2^{e-1},k,(\tilde{c}_{i}))\equiv
S(n,k-a2^{e-1},(c_{1},\tilde{c}_{2},\dots,\tilde{c}_{n}))\pmod{2^{e}},$ (8.26)

except if we are in cases (8.28) or (8.29). However, for those cases the
congruence (8.25) applies. It shows that, even though the congruence (8.26)
may not hold for an individual summand in case (8.28) or (8.29), if they are
combined then the corresponding reduction in (8.26) is allowed. Altogether, we
arrive at

$\displaystyle v_{\mathbf{x}}\big{(}n+a2^{e-1}\big{)}$
$\displaystyle=\sum_{k\geq
1}\sum_{(\tilde{c}_{i})\in\mathcal{P}_{n+a2^{e-1},k}}S(n+a2^{e-1},k,(\tilde{c}_{i}))$
$\displaystyle\equiv\sum_{k\geq
a2^{e-1}+1}\sum_{(c_{i})\in\mathcal{P}_{n,k-a2^{e-1}}}S(n+a2^{e-1},k-a2^{e-1},(c_{i}))\pmod{2^{e}}$
$\displaystyle\equiv v_{\mathbf{x}}(n)\pmod{2^{e}},$

thus confirming the claim.

Now we provide the proofs of the crucial congruences (8.22)–(8.25).

Proof of (8.22). If we use Lemma 27 with $n$ replaced by $n+a2^{e-1}$ and
$c_{i}=\tilde{c}_{i}$ for all $i$, then we see that
$S(n+ap^{e-1},k,(\tilde{c}_{i}))$ is divisible by

$2^{1+\max\limits_{\tilde{c}_{1}<i\leq n+a2^{e-1}}v_{2}(i)},$

with three exceptions, namely

$\displaystyle(\tilde{c}_{1},\tilde{c}_{2},\dots,\tilde{c}_{n})$
$\displaystyle=(n+a2^{e-1},0,\dots,0),$ (8.27)
$\displaystyle(\tilde{c}_{1},\tilde{c}_{2},\dots,\tilde{c}_{n})$
$\displaystyle=(n+a2^{e-1}-2,1,0,\dots,0),$ (8.28)
$\displaystyle(\tilde{c}_{1},\tilde{c}_{2},\dots,\tilde{c}_{n})$
$\displaystyle=(n+a2^{e-1}-4,2,0,\dots,0).$ (8.29)

In particular, if $\tilde{c}_{1}<a2^{e-1}$, and if (8.27)–(8.29) do not apply,
then in the range$\tilde{c}_{1}<i\leq n+a2^{e-1}$ we will find that
$i=a2^{e-1}$, and, consequently, $S(n+a2^{e-1},k,(\tilde{c}_{i}))$ is
divisible by $2^{e}$, as desired.

Proof of (8.23). By definition, we have

$\displaystyle S(n+a2^{e-1},n+a$ $\displaystyle
2^{e-1},(n+a2^{e-1},0,\dots,0))$
$\displaystyle=(-1)^{n+a2^{e-1}-1}\bigg{(}\prod_{j=1}^{n+a2^{e-1}-1}(2j-1)\bigg{)}(2n+a2^{e}-1)!!\,x^{n+a2^{e-1}}(1)$
$\displaystyle=(-1)^{n-1}(2n+a2^{e}-3)!!\,(2n+a2^{e}-1)!!\,x^{n+a2^{e-1}}(1)$

and

$S(n,n,(n,0,\dots,0))=(-1)^{n-1}(2n-3)!!\,(2n-1)!!\,x^{n}(1).$

By assumption, the number $x(1)$ is odd. Hence, Euler’s theorem and the fact
that $\varphi(2^{e})=2^{e-1}$ imply that

$x^{2^{e-1}}(1)\equiv 1\pmod{2^{e}}.$

Furthermore, we have

$\displaystyle(2n+a2^{e}-1)!!$
$\displaystyle=(2n-1)!!\prod_{j=0}^{a-1}(2n+j2^{e}+1)(2n+j2^{e}+3)\cdots(2n+(j+1)2^{e}-1)$
$\displaystyle\equiv(2n-1)!!\pmod{2^{e}},$ (8.30)

since, for each $j$, the factors inside the product in the first line form a
complete set of representatives of the multiplicative group
$({\mathbb{Z}}/2^{e}{\mathbb{Z}})^{\times}$. An analogous relation holds for
$(2n+a2^{e}-3)!!$ and $(2n-3)!!$. Altogether, this establishes the congruence
(8.23).

Proof of (8.24). Replace $n$ by $n+a2^{e-1}$, and $c_{1}$ by $c_{1}+a2^{e-1}$
in (8.19). Since $(c_{1}+a2^{e-1},c_{2},\dots)\in P_{n+a2^{e-1},k}$, the
$c_{i}$’s must vanish for $i>n$. Furthermore, we have $k\geq c_{1}+a2^{e-1}$,
which allows us to write $k=k^{\prime}+a2^{2-1}$ for some non-negative integer
$k^{\prime}$. Hence, under these substitutions and simplifications, and
writing $k$ instead of $k^{\prime}$ in abuse of notation, we obtain

$S(n+a2^{e-1},k+a2^{e-1},(\tilde{c}_{i}))=(-1)^{k+a2^{e-1}-1}\Bigg{(}\prod_{j=1}^{k+a2^{e-1}-1}(2j-1)\Bigg{)}\\\\[2.84526pt]
\times
2^{n-k}\frac{(2n+a2^{e})!}{2!^{c_{1}+a2^{e-1}}(c_{1}+a2^{e-1})!\,4!^{c_{2}}c_{2}!\cdots
n!^{c_{n}}c_{n}!}x^{a2^{e-1}}(1)\prod_{i=1}^{n}{x^{c_{i}}(i)},$ (8.31)

with $(c_{i})\in\mathcal{P}_{n,k}$. We are interested in the residue class of
this expression modulo $2^{e}$. As in (8.30), elementary number theory tells
us that

$\prod_{j=1}^{k+a2^{e-1}-1}(2j-1)\equiv\prod_{j=1}^{k-1}(2j-1)\quad(\text{mod
}2^{e}).$

Furthermore, we know that $x(1)$ is odd by assumption. Therefore the
expression (8.31) simplifies to

$S(n+a2^{e-1},k+a2^{e-1},(\tilde{c}_{i}))\equiv(-1)^{k-1}\Bigg{(}\prod_{j=1}^{k-1}(2j-1)\Bigg{)}\\\\[2.84526pt]
\times
2^{n-k}\frac{(2n+a2^{e})!\,c_{1}!}{(2n)!\,2^{a2^{e-1}}(c_{1}+a2^{e-1})!}\frac{(2n)!}{2!^{c_{1}}c_{1}!\,4!^{c_{2}}c_{2}!\cdots
n!^{c_{n}}c_{n}!}\prod_{i=1}^{n}{x^{c_{i}}(i)}\quad(\text{mod }2^{e}).$ (8.32)

We have

$\frac{(2n+a2^{e})!\,c_{1}!}{(2n)!\,2^{a2^{e-1}}(c_{1}+a2^{e-1})!}=\frac{(n+a2^{e-1})!\,(2n+a2^{e}-1)!!\,c_{1}!}{n!\,(2n-1)!!\,(c_{1}+a2^{e-1})!}.$

Since, again by elementary number theory,

$\frac{(2n+a2^{e}-1)!!}{(2n-1)!!}\equiv 1\quad(\text{mod }2^{e}),$

we may conclude that

$\displaystyle\frac{(2n+a2^{e})!\,c_{1}!}{(2n)!\,2^{a2^{e-1}}(c_{1}+a2^{e-1})!}$
$\displaystyle\equiv\frac{(n+a2^{e-1})!\,c_{1}!}{n!\,(c_{1}+a2^{e-1})!}\quad(\text{mod
}2^{e})$
$\displaystyle\equiv\prod_{i=c_{1}+1}^{n}\frac{i+a2^{e-1}}{i}\quad(\text{mod
}2^{e})$ $\displaystyle\equiv\prod_{i=c_{1}+1}^{n}\frac{(i\cdot
2^{-v_{2}(i)})+a2^{e-v_{2}(i)-1}}{i\cdot 2^{-v_{2}(i)}}\quad(\text{mod
}2^{e}).$

If this is substituted back in (8.32), then we see that

$S(n+a2^{e-1},k+a2^{e-1},(\tilde{c}_{i}))\\\\[2.84526pt]
\equiv(-1)^{k-1}\Bigg{(}\prod_{j=1}^{k-1}(2j-1)\Bigg{)}\Bigg{(}\prod_{i=c_{1}+1}^{n}\frac{(i\cdot
2^{-v_{2}(i)})+a2^{e-v_{2}(i)-1}}{i\cdot 2^{-v_{2}(i)}}\Bigg{)}\\\\[2.84526pt]
\cdot 2^{n-k}\frac{(2n)!}{2!^{c_{1}}c_{1}!\,4!^{c_{2}}c_{2}!\cdots
n!^{c_{n}}c_{n}!}\prod_{i=1}^{n}{x^{c_{i}}(i)}\quad(\text{mod }2^{e}).$ (8.33)

The reader should note that we wrote the first product over $i$ in this
particular form in order to make certain that the expressions $i\cdot
2^{-v_{2}(i)}$ in the denominator are odd numbers.

At this point, we would like to simplify the terms $(i\cdot
2^{-v_{2}(i)})+a2^{e-v_{2}(i)-1}$ to$i\cdot 2^{-v_{2}(i)}$. For, assuming the
validity of this simplification, the first product over $i$ on the right-hand
side of (8.33) would simplify to 1, and the remaining terms exactly equal
$S\big{(}n,k,(c_{i})\big{)}$.

We claim that this simplification is indeed allowed. For, by Lemma 27, we know
that the second line in (8.33) is an integer which is divisible by

$2^{1+\max\limits_{c_{1}<i\leq n}v_{2}(i)}.$

Hence, instead of computing modulo $2^{e}$, we may reduce the first line of
(8.33) modulo

$2^{e-1-\max\limits_{c_{1}<i\leq n}v_{2}(i)}.$

(It should be observed that the exponent is non-negative since we assumed
fromthe beginning that $n<2^{e-1}$.) This is exactly what we need to perform
the desiredsimplification, and the first product over $i$ drops out. What
remains is exactly$S(n,k,(c_{1},\tilde{c}_{2},\dots,\tilde{c}_{n}))$.

Proof of (8.25). Here, instead of Lemma 27, we can only use the slightly
weaker Corollaries 23 and 24.

We discuss first the “generic case”, namely when $n\geq 4$, where all terms in
(8.25) are defined. Let us begin with the term

$S(n+a2^{e-1},n+a2^{e-1}-1,(n+a2^{e-1}-2,1,0,\dots,0)).$

The corresponding expression on the right-hand side of (8.33) contains the
product

$\prod_{i=(n-2)+1}^{n}\frac{(i\cdot 2^{-v_{2}(i)})+a2^{e-v_{2}(i)-1}}{i\cdot
2^{-v_{2}(i)}}\\\\[2.84526pt] =\frac{\big{(}((n-1)\cdot
2^{-v_{2}(n-1)})+a2^{e-v_{2}(n-1)-1}\big{)}\big{(}(n\cdot
2^{-v_{2}(n)})+a2^{e-v_{2}(n)-1}\big{)}}{(n-1)\cdot 2^{-v_{2}(n-1)}\,n\cdot
2^{-v_{2}(n)}}.$ (8.34)

If $n\equiv 0$ (mod $4$), then Corollary 23 says that the last line in (8.33)
(which in particular contains the prefactor $2^{n-k}$) is (exactly) divisible
by $2\cdot 2^{v_{2}(n)-1}=2^{v_{2}(n)}$, and hence we may consider the
numerator in (8.34) modulo $2^{e-v_{2}(n)}$. Since

$((n-1)\cdot 2^{-v_{2}(n-1)})+a2^{e-v_{2}(n-1)-1}\equiv((n-1)\cdot
2^{-v_{2}(n-1)})\pmod{2^{e-1}}$

(with $v_{2}(n-1)=0$), the product (8.34) reduces to

$\displaystyle\prod_{i=n-1}^{n}\frac{(i\cdot
2^{-v_{2}(i)})+a2^{e-v_{2}(i)-1}}{i\cdot 2^{-v_{2}(i)}}$
$\displaystyle\equiv\frac{(n\cdot 2^{-v_{2}(n)})+a2^{e-v_{2}(n)-1}}{n\cdot
2^{-v_{2}(n)}}\pmod{2^{e}}$ $\displaystyle\equiv
1+\frac{a2^{e-v_{2}(n)-1}}{n\cdot 2^{-v_{2}(n)}}\pmod{2^{e}}.$

When substituted back in (8.33), this shows that

$S(n+a2^{e-1},n+a2^{e-1}-1,(n+a2^{e-1}-2,1,0,\dots,0))\\\\[2.84526pt] \equiv
S(n,n-1,(n-2,1,0,\dots,0))+u_{1}\frac{a2^{e-v_{2}(n)-1}}{n\cdot
2^{-v_{2}(n)}}\pmod{2^{e}},$

where $u_{1}$ is an odd integer. Here it is important that $x(1)$ and $x(2)$
are odd, which they are by assumption.

An analogous discussion for the other term on the left-hand side of (8.25),
using Corollary 24, leads to

$S(n+a2^{e-1},n+a2^{e-1}-2,(n+a2^{e-1}-4,2,0,\dots,0))\\\\[2.84526pt] \equiv
S(n,n-2,(n-4,2,0,\dots,0))+u_{2}\frac{a2^{e-v_{2}(n)-1}}{n\cdot
2^{-v_{2}(n)}}\pmod{2^{e}},$

where $u_{2}$ is an odd integer. Together, the last two congruences establish
(8.25).

The discussions for the other congruence classes of $n$ modulo $4$ are just
minor variations of the above arguments and are therefore omitted here.

Finally, we address the remaining cases of “small” $n$, namely $0\leq n<4$,
when one or both terms on the right-hand side of (8.25) contain negative
parameter values, in which case they are declared to be zero by definition. We
exemplify what has to be done in these cases by going through the case where
$n=1$. All other cases may be handled in a similar manner.

Corollary 23 with $n$ replaced by $1+a2^{e-1}$, together with the assumption
that all $x(i)$’s are odd, implies that

$S(n+a2^{e-1},n+a2^{e-1}-1,(n+a2^{e-1}-2,1,0,\dots,0))\equiv\begin{cases}2^{e-1}~{}(\text{mod
}2^{e}),&\text{if $a$ is odd},\\\\[2.84526pt] 0~{}(\text{mod }2^{e}),&\text{if
$a$ is even}.\end{cases}$

Likewise, Corollary 24 with $n$ replaced by $1+a2^{e-1}$, together with the
assumption that all $x(i)$’s are odd, implies that

$S(n+a2^{e-1},n+a2^{e-1}-2,(n+a2^{e-1}-4,2,0,\dots,0))\equiv\begin{cases}2^{e-1}~{}(\text{mod
}2^{e}),&\text{if $a$ is odd},\\\\[2.84526pt] 0~{}(\text{mod }2^{e}),&\text{if
$a$ is even}.\end{cases}$

Together, this establishes (8.25) in the considered case.

This finishes the proof of the theorem. ∎

Our next result generalises [10, Theorem 1(i)].

######  Theorem 29.

Let $x(j),$ $j=0,1,2,\dots,$ be integers with $x(0)=1$ and $x(1)$ odd. Then
the sequence $(v_{\mathbf{x}}(n))_{n\geq 0},$ with the coefficients
$v_{\mathbf{x}}(n)$ being defined in (8.17), when taken modulo $2,$ is the
all-$1$-sequence. Modulo $4,$ the sequence is purely periodic with period
length $4,$ the first few values of the sequence (modulo $4$) being given by

$1,\,x(1),\,3,\,x(1)+2,\,1,\,\dots.$ (8.35)

###### Proof.

It suffices to treat the case of modulus $4$ since, because of the assumption
that $x(1)$ is odd, it implies the assertion for the modulus $2$.

We prove the claim in the statement of the theorem by induction on $n$.

We use the recurrence (2.6) for the induction step. We may assume that $n\geq
4$. We rewrite the recurrence (2.6) modulo $4$ in the form

$0\equiv-\sum_{m=0}^{\left\lceil
n/2\right\rceil-1}\binom{2n}{2m}v(m)v(n-m)-\frac{1}{2}\chi(n\text{
even})\binom{2n}{n}v^{2}(n/2)\quad(\text{mod }4),$

where $\chi(\mathcal{A})=1$ if $\mathcal{A}$ is true and $\chi(\mathcal{A})=0$
otherwise. Since the central binomial coefficient is divisible by $2$ for
$n\geq 1$, we see that, for the induction, we may simply substitute the
claimed mod-4 values of $v(m)$ for $m=0,1,\dots,n$ in

$\frac{1}{2}\sum_{m=0}^{n}\binom{2n}{2m}v(m)v(n-m),$ (8.36)

and check that the resulting expression is divisible by $4$.

We substitute the values from (8.35) in the expression (8.36), to get

$\frac{1}{2}\sum_{m\equiv 0~{}(\text{mod
}4)}\binom{2n}{2m}+\frac{x(1)}{2}\sum_{m\equiv 1~{}(\text{mod
}4)}\binom{2n}{2m}\\\\[2.84526pt] +\frac{3}{2}\sum_{m\equiv 2~{}(\text{mod
}4)}\binom{2n}{2m}+\frac{x(1)+2}{2}\sum_{m\equiv 3~{}(\text{mod
}4)}\binom{2n}{2m}.$ (8.37)

Next we recall the well-known (and easily derived) fact that

$\sum_{m\equiv r~{}\text{(mod
8)}}\binom{N}{m}=\frac{1}{8}\sum_{j=0}^{7}\omega^{-rj}(1+\omega^{j})^{N},$

where $\omega=\frac{1+\mathbf{i}}{\sqrt{2}}$ is a primitive eighth root of
unity (with $\mathbf{i}=\sqrt{-1}$). Using this in (8.37), we obtain

$\frac{1}{16}\sum_{j=0}^{7}(1+\omega^{j})^{2n}+\frac{x(1)}{16}\sum_{j=0}^{7}(-\mathbf{i})^{j}(1+\omega^{j})^{2n}\\\\[2.84526pt]
+\frac{3}{16}\sum_{j=0}^{7}(-1)^{j}(1+\omega^{j})^{2n}+\frac{x(1)+2}{16}\sum_{j=0}^{7}\mathbf{i}^{j}(1+\omega^{j})^{2n}.$

Now we multiply this expression by $z^{n}$ and sum the result over all $n\geq
0$. After evaluating all the appearing geometric series and simplifying, we
obtain

$\frac{(x(1)+3)\left(1-7z+21z^{2}-35z^{3}+34z^{4}-42z^{5}-28z^{6}-8z^{7}\right)}{1-8z+28z^{2}-56z^{3}+68z^{4}-112z^{5}-112z^{6}-64z^{7}}.$
(8.38)

Here, we should first observe that the factor $x(1)+3$ is even, since $x(1)$
is odd by assumption. Furthermore, the denominator has the form $1+2f(z)$,
where $f(z)$ is a polynomial with integer coefficients, and the coefficients
of $z^{4}$, $z^{5}$, $z^{6}$, and $z^{7}$ in the numerator are all even. It is
not difficult to see that, together, this implies that in the series expansion
of (8.38) the coefficients of $z^{n}$ is divisible by $4$ for $n\geq 4$. ∎

##  9\. The inverse of the matrix $\mathbf{R}$ modulo powers of $2$

In this section, we prove periodicity of the matrix entries $R^{-1}(k+2n,k)$
(given by Proposition 2) modulo powers of 2, when considered as a sequence
indexed by $k$. Moreover, this result comes again with a precise statement on
period lengths. Our starting point is again an expansion in the spirit of
(6.1), namely (9.2). Also here, the main result of this section concerns a
polynomial refinement. More precisely, in this refinement, the number $u(j)$
gets replaced by a variable $y(j)$, $j=0,1,\dots$, with the only restriction
that $y(0)=1$.

######  Theorem 30.

Let $y(j),$ $j=0,1,2,\dots,$ be integers with $y(0)=1$. Furthermore, define
coefficients $R^{-1}_{y}(n,k)$ by

$R^{-1}_{y}(n,k)=2^{(n-k)/2}\frac{(n-1)!}{(k-1)!}\left\langle
t^{-k}\right\rangle U^{-n}_{y}(t),$ (9.1)

where

$U_{y}(t):=\sum_{j\geq 0}\frac{y(j)}{(2j+1)!}t^{2j+1}.$

Here again, the case $k=0$ has to be interpreted as $R^{-1}_{y}(0,0)=1$ and
$R^{-1}_{y}(n,0)=0$ for $n\geq 1$. Then, for fixed $n$ and any $2$-power
$2^{e},$ the sequence $\big{(}R^{-1}_{y}(k+2n,k)\big{)}_{k\geq 0}$ is purely
periodic modulo $2^{e}$ with (not necessarily minimal) period length $2^{e}$.

###### Proof.

By the definition (9.1), we have

$\displaystyle R^{-1}_{y}(2n+{}k$
$\displaystyle,k)=2^{n}\frac{(2n+k-1)!}{(k-1)!}\left\langle
t^{2n}\right\rangle\big{(}U_{y}(t)/t\big{)}^{-2n-k}$
$\displaystyle=2^{n}\frac{(2n+k-1)!}{(k-1)!}\left\langle
t^{2n}\right\rangle\sum_{m\geq
0}\binom{-2n-k}{m}\big{(}U_{y}(t)/t-1\big{)}^{m}$
$\displaystyle=2^{n}\frac{(2n+k-1)!}{(k-1)!}\left\langle
t^{2n}\right\rangle\sum_{m\geq
0}(-1)^{m}\binom{2n+k+m-1}{m}\Bigg{(}\sum_{j\geq
1}\frac{y(j)}{(2j+1)!}t^{2j}\Bigg{)}^{m}$
$\displaystyle=2^{n}\frac{(2n+k-1)!}{(k-1)!}\sum_{m\geq
0}(-1)^{m}\binom{2n+k+m-1}{m}$ $\displaystyle\kern
56.9055pt\cdot\underset{c_{1}=0}{\sum_{(c_{i})\in\mathcal{P}^{o}_{2n+m,m}}}\frac{m!}{3!^{c_{3}}c_{3}!\,5!^{c_{5}}c_{5}!\cdots(2n+1)!^{c_{2n+1}}c_{2n+1}!}\prod_{i=1}^{2n+1}{y^{c_{i}}\big{(}\tfrac{i-1}{2}\big{)}}$
$\displaystyle=\sum_{m\geq
0}\underset{c_{1}=0}{\sum_{(c_{i})\in\mathcal{P}^{o}_{2n+m,m}}}(-1)^{m}2^{n}\binom{2n+m+k-1}{2n+m}$
$\displaystyle\kern
85.35826pt\cdot\frac{(2n+m)!}{3!^{c_{3}}c_{3}!\,5!^{c_{5}}c_{5}!\cdots(2n+1)!^{c_{2n+1}}c_{2n+1}!}\prod_{i=1}^{2n+1}{y^{c_{i}}\big{(}\tfrac{i-1}{2}\big{)}}.$
(9.2)

Here, we observe that $\mathcal{P}^{o}_{2n+m,m}$ is empty for $m>n$. Indeed,
for $(c_{i})\in\mathcal{P}^{o}_{2n+m,m}$ with $c_{1}=0$, we have

$3m=3\sum_{i=1}^{2n+1}c_{i}\leq\sum_{i=1}^{2n+1}ic_{i}=2n+m,$ (9.3)

and hence $m\leq n$. Consequently, we may restrict the sum over $m$ in (9.2)
to $m=0,1,\dots,n$.

We want to consider $R^{-1}_{y}(2n+k,k)$ for fixed $n$ as a function in $k$.
Inspection of the last expression in (9.2) reveals that, since the sum over
$m$ is finite, $R^{-1}_{y}(2n+k,k)$ is a polynomial in $k$ with rational
coefficients. Hence, it is certainly periodic modulo $2^{e}$ (and, more
generally, modulo any modulus $M$). In order to find a bound on the period
length, we must perform a $2$-adic analysis of the expression in (9.2).

We may rewrite (9.2) as follows:

$\displaystyle R^{-1}_{y}(2n+k,k)$ $\displaystyle=\sum_{m\geq
0}\underset{c_{1}=0}{\sum_{(c_{i})\in\mathcal{P}^{o}_{2n+m,m}}}(-1)^{m}2^{n}\frac{(2n+m+k-1)(2n+m+k-2)\cdots
k}{(2n)!}$ $\displaystyle\kern
85.35826pt\cdot\frac{(2n)!}{2!^{c_{3}}c_{3}!\,4!^{c_{5}}c_{5}!\cdots(2n)!^{c_{2n+1}}c_{2n+1}!}\prod_{i=1}^{2n+1}\left(\frac{y\big{(}\tfrac{i-1}{2}\big{)}}{i}\right)^{c_{i}}$
$\displaystyle=\sum_{m\geq
0}\underset{c_{1}=0}{\sum_{(c_{i})\in\mathcal{P}^{o}_{2n+m,m}}}(-1)^{m}\frac{(2n+m+k-1)(2n+m+k-2)\cdots
k}{n!\,(2n-1)!!}$ $\displaystyle\kern
71.13188pt\cdot\frac{(2n)!}{2!^{c_{3}}c_{3}!\,4!^{c_{5}}c_{5}!\cdots(2n)!^{c_{2n+1}}c_{2n+1}!}\prod_{i=1}^{2n+1}\left(\frac{y\big{(}\tfrac{i-1}{2}\big{)}}{i}\right)^{c_{i}}.$
(9.4)

We want to consider (9.4) modulo $2^{e}$, and our goal is to show that, modulo
$2^{e}$, this expression is periodic with period length $2^{e}$ as a
(polynomial) function in $k$.

Now, the first term in the last line of (9.4) is an integer due to the fact
that

$\sum_{i=1}^{2n+1}(2i)c_{i}=\sum_{i=1}^{2n+1}(2i+1)c_{i}-\sum_{i=1}^{2n+1}c_{i}=(2n+m)-m=2n,$

which allows the application of Lemma 17 with $(c_{i})$ replaced by

$(0,c_{3},0,c_{5},0,\dots,0,c_{2n+1}).$

The product over $i$ in the last line of (9.4) is a rational number with an
odd denominator, since $c_{i}=0$ for all even $i$. Thus, the last line of
(9.4) represents a rational number with an odd denominator, which has a non-
negative $2$-adic valuation. Likewise, the term $(2n-1)!!$ in the denominator
of the expression in the first line of (9.4) is an odd number, and
consequently also does not influence the 2-adic analysis of this expression.

We substitute $k+2^{e}$ in place of $k$ in the remaining terms in the first
line of (9.4) (ignoring the sign $(-1)^{m}$), and compute

$\displaystyle\frac{(2n+m+k+2^{e}-1)(2n+m+k+2^{e}-2)\cdots(k+2^{e})}{n!}$
$\displaystyle\kern
14.22636pt=\binom{2n+m+k+2^{e}-1}{n}{(n+m+k+2^{e}-1)(n+m+k+2^{e}-2)\cdots(k+2^{e})}$
$\displaystyle\kern
14.22636pt\equiv\binom{2n+m+k+2^{e}-1}{n}{(n+m+k-1)(n+m+k-2)\cdots
k}\pmod{2^{e}}$ $\displaystyle\kern
14.22636pt=(2n+m+k+2^{e}-1)(2n+m+k+2^{e}-2)\cdots(n+m+k+2^{e})$
$\displaystyle\kern
56.9055pt\times{(n+m+k-1)(n+m+k-2)\cdots(n+k)}\binom{n+k-1}{n}\pmod{2^{e}}$
$\displaystyle\kern 14.22636pt\equiv\frac{(2n+m+k-1)(2n+m+k-2)\cdots
k}{n!}\pmod{2^{e}}.$

If we use this congruence in (9.4), then the periodicity of this expression in
$k$ with period length $2^{e}$ becomes apparent.

This finishes the proof of the theorem. ∎

##  10\. The sequence $(d(n))_{n\geq 0}$ modulo powers of $2$

Now we are in the position to prove our second main result, namely Part 3 of
Theorem 1.

######  Theorem 31.

The sequence $(d(n))_{n\geq 0},$ when taken modulo any fixed $2$-power $2^{e}$
with $e\geq 3,$ is purely periodic with (not necessarily minimal) period
length $2^{e-1}$. Modulo $4,$ the sequence is purely periodic with period
length $4,$ the first few values of the sequence (modulo $4$) being given by

$1,1,3,3,1,\dots.$

###### Proof.

Suppose first that $e\geq 3$. By (9.2) with $y(i)=u(i)$ for all $i$, we
have$R^{-1}(2n,2k)\equiv 0$ (mod $2^{e}$) for $n\geq k+e$, due to the factor
$2^{n-k}$ that arises under the corresponding substitution. Thus, the relation
(2.12) becomes

$\displaystyle d(n)$
$\displaystyle\equiv\sum_{k=\max\\{0,n-e+1\\}}^{n}R^{-1}(2n,2k)v(k)\quad(\text{mod
}2^{e})$
$\displaystyle\equiv\sum_{k=0}^{\min\\{n,e-1\\}}R^{-1}(2n,2n-2k)v(n-k)\quad(\text{mod
}2^{e}).$ (10.1)

By Theorem 28 with $x(j)=\prod_{\ell=1}^{j}(4\ell-3)^{2}$ for all $j$, the
sequence $(v(n))_{n\geq 0}$ is (purely) periodic modulo $2^{e}$ with period
length $2^{e-1}$, and, by Theorem 30 with $y(j)=u(j)$ for all $j$, $k$ and $n$
interchanged, and subsequently $n$ replaced by $2n-2k$, the sequence
$\big{(}R^{-1}(2n,2n-2k))_{n\geq 0}$ is (purely) periodic modulo $2^{e}$ with
period length $2^{e-1}$. There is a little detail that needs to be addressed
here: what is the meaning of $R^{-1}(2n,2n-2k)$ if $n<k$? So far we have not
given a meaning to this in that case. However, the expression for
$R^{-1}(2n+k,k)$ provided by (9.2) makes it easy to define the appropriate
extension. Namely, as we said earlier, this expression is a polynomial in $k$
and therefore it gives a meaning to $R^{-1}(2n+k,k)$ for all — positive or
negative — integers $k$. Moreover, as long as $-2n\leq k<0$, the term
$R^{-1}(2n+k,k)$ vanishes because of the appearance of the binomial
coefficient $\binom{2n+m+k-1}{2n+m}$ in (9.2). Furthermore, the periodicity
argument still applies to the extended sequence. Altogether, this allows us to
relax the upper bound on the summation index $k$ in (10.1) to

$d(n)=\sum_{k=0}^{e-1}R^{-1}(2n,2n-2k)v(n-k)\quad(\text{mod }2^{e}).$

The above arguments show in particular that each summand on the right-hand
side is (purely) periodic modulo $2^{e}$ with (not necessarily minimal) period
length $2^{e-1}$. Since these are finitely many summands, the same must hold
for $d(n)$.

The assertion of the theorem concerning the behaviour of the sequence modulo
$4$ is a direct consequence of Theorem 29 with $x(1)=1$ and Theorem 30 with
$y(j)=u(j)$ for all $j$. ∎

##  11\. The inverse of the matrix $\mathbf{R}$ modulo prime powers $p^{e}$
with $p\equiv 1~{}(\text{mod }4)$

This section prepares for the proof of our third main result, given in the
subsequent section. The goal is to establish periodicity of $R^{-1}(2n,2k)$
modulo powers of a prime $p$ with $p\equiv 1$ (mod 4), when considered as a
sequence in $n$. This will eventually be achieved in Theorem 38. Similar to
Section 9, we actually prove a polynomial refinement in which the number
$u(j)$ that appears in the definition of the matrix entries $R^{-1}(2n,2k)$
(cf. (2.11)) is replaced by an integer $y(j)$, $j=0,1,\dots$, with the
restriction that $y(j)$ is divisible by $p^{e}$ for $j\geq\left\lceil
ep/2\right\rceil$. The corresponding analysis is the most demanding one in
this article. Already the final periodicity result in (11.21) (with
“supporting” powers $p^{\left\lfloor 2k/p\right\rfloor}$ on both sides)
indicates that matters are much more delicate here. While our starting point
is again the expansion (9.2) (with the appropriate substitutions; see
(11.22)), the analysis of the summand modulo powers of $p$ is much more
intricate here. The corresponding auxiliary results are the subject of Lemmas
32–37.

We start with a lower bound for the $p$-adic valuation of the summand in
(11.22) in the “generic” case.

######  Lemma 32.

Let $p$ be a prime with $p\equiv 1$ (mod $4$) and let
$\big{(}y(n)\big{)}_{n\geq 0}$ be an integer sequence with the property that
$v_{p}\big{(}y(n)\big{)}\geq e$ for
$n\geq\left\lceil\frac{ep}{2}\right\rceil$. For all positive integers $n$ and
$k,$ and non-negative integers $m$ and $c_{i},$ $1\leq i\leq 2n-2k,$ with
$\sum_{i=1}^{2n-2k}ic_{i}=2n-2k+m,$ $\sum_{i=1}^{2n-2k}c_{i}=m,$ and $c_{i}=0$
for all even $i,$ we have

$v_{p}\left(\frac{(2n+m-1)!}{(2k-1)!\prod_{i=1}^{2n-2k}i!^{c_{i}}\,c_{i}!}\prod_{i=1}^{2n-2k}{y^{c_{i}}\big{(}\tfrac{i-1}{2}\big{)}}\right)\\\\[2.84526pt]
\geq\\#\left(\text{\em carries when adding $\left(2n+m-1-pc_{p}\right)_{p}$
and $(pc_{p})_{p}$}\right)\kern 56.9055pt\\\\[2.84526pt] +\\#\left(\text{\em
carries when adding $\left(2n-2k+m-pc_{p}\right)_{p}$ and
$(2k-1)_{p}$}\right)\\\\[2.84526pt]
+\tfrac{1}{2(p-1)}(2n-2k+m-pc_{p})-\tfrac{1}{p-1}s_{p}(2n-2k+m-pc_{p}).$
(11.1)

######  Remark 33.

For non-negative integers $N$, we have

$\tfrac{1}{2(p-1)}N-\tfrac{1}{p-1}s_{p}(N)\geq-\tfrac{1}{2}.$

Thus, although the last line in (11.1) can be negative, the sum of the two
numbers of carries on the right-hand side of (11.1) is still a lower bound for
the $p$-adic valuation on the left-hand side since the latter is an integer.

###### Proof of Lemma 32.

By Legendre’s formula in Lemma 3, the $p$-adic valuation on the left-hand side
of (11.1) equals

$v_{p}\left(\frac{(2n+m-1)!}{(2k-1)!\prod_{i=1}^{2n-2k}i!^{c_{i}}\,c_{i}!}\prod_{i=1}^{2n-2k}{y^{c_{i}}\big{(}\tfrac{i-1}{2}\big{)}}\right)\\\\[2.84526pt]
=\frac{1}{p-1}\left(\vphantom{\sum_{p}^{i}}2n-2k+m-s_{p}(2n+m-1)+s_{p}(2k-1)\right.\kern
85.35826pt\\\\[2.84526pt]
\left.-\sum_{i=1}^{2n-2k}\Big{(}c_{i}i-c_{i}s_{p}(i)+c_{i}-s_{p}(c_{i})\Big{)}\right)+\sum_{i=1}^{2n-2k}c_{i}v_{p}\Big{(}y\big{(}\tfrac{i-1}{2}\big{)}\Big{)}.$
(11.2)

We consider the terms involving $c_{i}$ on the right-hand side of (11.2)
separately. Concerning these, we claim that the following lower bound holds
for all odd $i\geq 3$ with $i\neq p$:

$\frac{1}{p-1}\big{(}-(i+1)c_{i}+c_{i}s_{p}(i)+s_{p}(c_{i})\big{)}+c_{i}v_{p}\Big{(}y\big{(}\tfrac{i-1}{2}\big{)}\Big{)}\geq-\frac{ic_{i}}{2(p-1)}.$
(11.3)

Multiplying both sides by $2(p-1)$ and using our divisibility assumption for
$y\big{(}\frac{i-1}{2}\big{)}$, we see that the above claim will follow from
the estimate

$-(i+2)c_{i}+2c_{i}s_{p}(i)+2s_{p}(c_{i})+2(p-1)c_{i}\left\lfloor\tfrac{i-1}{p}\right\rfloor\geq
0.$

This inequality can now indeed easily be verified for $3\leq i<p$, for
$p<i<2p$, for $i=2p+1$, and finally for $2p+3\leq i$ making use of the simple
inequality $\left\lfloor\tfrac{i-1}{p}\right\rfloor\geq\tfrac{i-p}{p}$. This
proves our claim in (11.3).

We use (11.3) in (11.2) for $i\neq p$, keeping the terms for $i=p$ unchanged.
Thereby, we obtain

$\displaystyle v_{p}$
$\displaystyle\left(\frac{(2n+m-1)!}{(2k-1)!\prod_{i=1}^{2n-2k}i!^{c_{i}}\,c_{i}!}\prod_{i=1}^{2n-2k}{y^{c_{i}}\big{(}\tfrac{i-1}{2}\big{)}}\right)$
$\displaystyle\geq\frac{1}{p-1}\left(\vphantom{\underset{f}{\sum_{p}^{i}}}2n-2k+m-pc_{p}+s_{p}(c_{p})-s_{p}(2n+m-1)+s_{p}(2k-1)-\frac{1}{2}\underset{i\neq
p}{\sum_{i=1}^{2n-2k}}ic_{i}\right)$
$\displaystyle=\frac{1}{2(p-1)}(2n-2k+m-pc_{p})+\frac{1}{p-1}\big{(}s_{p}(pc_{p})-s_{p}(2n+m-1)+s_{p}(2k-1)\big{)}$
$\displaystyle=\frac{1}{2(p-1)}(2n-2k+m-pc_{p})-\frac{1}{p-1}s_{p}(2n-2k+m-pc_{p})$
$\displaystyle\kern
56.9055pt+\frac{1}{p-1}\big{(}s_{p}(pc_{p})+s_{p}(2n+m-1-pc_{p})-s_{p}(2n+m-1)\big{)}$
$\displaystyle\kern
56.9055pt+\frac{1}{p-1}\big{(}s_{p}(2k-1)+s_{p}(2n-2k+m-pc_{p})-s_{p}(2n+m-1-pc_{p})\big{)}.$
(11.4)

By Lemma 5, the next-to-last line in (11.4) equals the first number of carries
that appears on the right-hand side of (11.1), while the last line in (11.4)
equals the second number of carries on the right-hand side of (11.1). Thus, we
have established (11.1). ∎

In a special case, the bound from the previous lemma can be slightly improved.

######  Lemma 34.

To the assumptions of Lemma 32 we add the conditions that $c_{i}=0$ for $i\geq
2p$ and that $c_{i}<p$ for $1\leq i<p$ and for $p<i<2p$. Then we have

$v_{p}\left(\frac{(2n+m-1)!}{(2k-1)!\prod_{i=1}^{2n-2k}i!^{c_{i}}\,c_{i}!}\prod_{i=1}^{2n-2k}{y^{c_{i}}\big{(}\tfrac{i-1}{2}\big{)}}\right)\\\\[2.84526pt]
\geq\\#\left(\text{\em carries when adding $\left(2n+m-1-pc_{p}\right)_{p}$
and $(pc_{p})_{p}$}\right)\kern 56.9055pt\\\ +\\#\left(\text{\em carries when
adding $\left(2n-2k+m-pc_{p}\right)_{p}$ and $(2k-1)_{p}$}\right)\\\
+\tfrac{1}{p-1}(2n-2k+m-pc_{p})-\tfrac{1}{p-1}s_{p}(2n-2k+m-pc_{p}).$ (11.5)

######  Remark 35.

The only difference between (11.5) and (11.1) is a “missing” factor of 2 in
the denominator of the first term in the last line of (11.5). Now, by
Legendre’s formula in Lemma 3, this last line equals the $p$-adic valuation of
$(2n-2k+m-pc_{p})!$ and is therefore non-negative (as opposed to the last line
in (11.1); cf. Remark 33).

###### Proof of Lemma 34.

We use again the identity (11.2). At this point, we observe that the
additional conditions on the $c_{i}$’s imply that the contribution of $c_{i}$
with $1\leq i<2p$ and $i\neq p$ in (11.2) is non-negative. Indeed, this
contribution is

$-\frac{1}{p-1}\big{(}c_{i}i-c_{i}s_{p}(i)+c_{i}-s_{p}(c_{i})\big{)}+c_{i}v_{p}\Big{(}y\big{(}\tfrac{i-1}{2}\big{)}\Big{)}\\\\[2.84526pt]
=-\frac{1}{p-1}\big{(}ic_{i}-c_{i}s_{p}(i)\big{)}+c_{i}v_{p}\Big{(}y\big{(}\tfrac{i-1}{2}\big{)}\Big{)}.$
(11.6)

since $c_{i}<p$. If $i<p$, then we have $s_{p}(i)=i$ and hence the value in
(11.6) is non-negative. If, on the other hand, $p<i<2p$, then we have
$s_{p}(i)=i-p+1$ and $v_{p}\Big{(}y\big{(}\tfrac{i-1}{2}\big{)}\Big{)}\geq 1$,
and therefore the value in (11.6) is again non-negative.

For the remaining terms in (11.2), we compute

$\frac{1}{p-1}\big{(}2n-2k+m-s_{p}(2n+m-1)+s_{p}(2k-1)-pc_{p}+s_{p}(c_{p})\big{)}\\\\[2.84526pt]
=\frac{1}{p-1}(2n-2k+m-pc_{p})-\frac{1}{p-1}s_{p}(2n-2k+m-pc_{p})\\\
+\frac{1}{p-1}\big{(}s_{p}(2n+m-1-pc_{p})+s_{p}(pc_{p})-s_{p}(2n+m-1)\big{)}\\\
+\frac{1}{p-1}\big{(}s_{p}(2n-2k+m-pc_{p})+s_{p}(2k-1)-s_{p}(2n+m-1-pc_{p})\big{)}.$
(11.7)

By Lemma 5, the last line is the number of carries that appears in the next-
to-last line in (11.5). For the same reason, the next-to-last line in (11.7)
is the number of carries that appears in the third line from below in (11.5).
This completes the proof. ∎

The next lemma collects together several auxiliary inequalities that concern
the right-hand side of (11.1). They will be used in subsequent arguments.

######  Lemma 36.

Let $p$ be a prime with $p\equiv 1$ (mod $4$) and $N$ and $\ell$ non-negative
integers with $p^{\ell}\leq N<p^{\ell+1}$. Then

$\displaystyle\left\lfloor\tfrac{N}{p}\right\rfloor$ $\displaystyle\geq\ell,$
$\displaystyle\quad\text{for }\ell\geq 0,$ (11.8)
$\displaystyle\tfrac{1}{2(p-1)}N-\tfrac{1}{p-1}s_{p}(N)$
$\displaystyle>\tfrac{N}{2p}-\tfrac{3}{2},$ $\displaystyle\quad\text{for
}\ell\geq 0,$ (11.9) $\displaystyle\tfrac{1}{2(p-1)}N-\tfrac{1}{p-1}s_{p}(N)$
$\displaystyle\geq\ell+\tfrac{3}{8},$ $\displaystyle\quad\text{for }\ell\geq
2,$ (11.10) $\displaystyle\tfrac{1}{2(p-1)}N-\tfrac{1}{p-1}s_{p}(N)$
$\displaystyle\geq\ell,$ $\displaystyle\quad\text{for }\ell\geq 1\text{ and
}N\geq p^{\ell}(p-1),$ (11.11)
$\displaystyle\tfrac{1}{2(p-1)}N-\tfrac{1}{p-1}s_{p}(N)$ $\displaystyle>0,$
$\displaystyle\quad\text{for }2p\leq N<p^{2}.$ (11.12)

###### Proof.

The first inequality is obvious.

For the proof of (11.9), we write $N=n_{0}+n_{1}p+n_{2}p^{2}$ with $0\leq
n_{0},n_{1}<p$ and $n_{2}\geq 0$, and then estimate the difference of the
left-hand side and ${N}/(2p)$,

$\displaystyle\tfrac{1}{2(p-1)}N-\tfrac{1}{p-1}s_{p}(N)-\tfrac{N}{2p}$
$\displaystyle=\tfrac{N}{2p(p-1)}-\tfrac{1}{p-1}s_{p}(N)$
$\displaystyle=\tfrac{1}{2p(p-1)}\left(n_{0}+n_{1}p+n_{2}p^{2}-2pn_{0}-2pn_{1}-2ps_{p}(n_{2})\right)$
$\displaystyle\geq\tfrac{1}{2p(p-1)}\left(-n_{0}(2p-1)-n_{1}p+n_{2}(p^{2}-2p)\right)$
$\displaystyle\geq-\tfrac{2p-1}{2p}-\tfrac{1}{2}>-\tfrac{3}{2},$

as desired.

In order to show (11.10), let $N=n_{0}+n_{1}p+\dots+n_{\ell}p^{\ell}$ with
$0\leq n_{i}<p$ for all $i$ and $n_{\ell}>0$. Then we have

$\displaystyle\tfrac{1}{2(p-1)}N-\tfrac{1}{p-1}s_{p}(N)$
$\displaystyle=\tfrac{1}{2(p-1)}\big{(}n_{0}+n_{1}p+\dots+n_{\ell}p^{\ell}\big{)}-\tfrac{1}{p-1}(n_{0}+n_{1}+\dots+n_{\ell})$
$\displaystyle=\tfrac{1}{2(p-1)}\big{(}-n_{0}+n_{1}(p-2)+\dots+n_{\ell}(p^{\ell}-2)\big{)}$
$\displaystyle\geq\tfrac{1}{2(p-1)}\big{(}-(p-1)+(p^{\ell}-2)\big{)}$ (11.13)
$\displaystyle=\tfrac{1}{2(p-1)}(p^{\ell}-2)-\tfrac{1}{2}.$ (11.14)

Now, it is a simple exercise to show that

$p^{\ell}\geq 2(p-1)\ell+p^{2}-4p+4,\quad\text{for }\ell\geq 2\text{ and
}p\geq 5.$

We use this in (11.14) to get

$\tfrac{1}{2(p-1)}N-\tfrac{1}{p-1}s_{p}(N)\geq\ell+\tfrac{1}{2(p-1)}(p^{2}-4p+2)-\tfrac{1}{2}=\ell+\tfrac{1}{2}(p-4)-\tfrac{1}{2(p-1)}\geq\ell+\tfrac{3}{8},$

since $p\geq 5$.

For the proof of the strengthening in (11.11), we observe that, instead of the
last line in (11.14), we may improve that lower bound to

$\tfrac{1}{2(p-1)}N-\tfrac{1}{p-1}s_{p}(N)\geq\tfrac{1}{2(p-1)}\big{(}-(p-1)+(p-1)(p^{\ell}-2)\big{)}=\tfrac{1}{2}(p^{\ell}-3).$

The fact that this is at least $\ell$ for $\ell\geq 1$ and $p\geq 5$ is
straightforward to verify.

Finally we turn to the proof of (11.12). We write $N=n_{0}+n_{1}p$ with $0\leq
n_{0}<p$ and $2\leq n_{1}<p$, and compute

$\displaystyle\tfrac{1}{2(p-1)}N-\tfrac{1}{p-1}s_{p}(N)$
$\displaystyle=\tfrac{1}{2(p-1)}(n_{0}+n_{1}p)-\tfrac{1}{p-1}(n_{0}+n_{1})$
$\displaystyle=\tfrac{1}{2(p-1)}\big{(}-n_{0}+n_{1}(p-2)\big{)}$
$\displaystyle\geq\tfrac{1}{2(p-1)}\big{(}-(p-1)+2(p-2)\big{)}$
$\displaystyle=\tfrac{1}{2(p-1)}\big{(}p-3\big{)}>0,$

since $p\geq 5$.

This completes the proof of the lemma. ∎

The purpose of the lemma below is to “convert” the lower bound from Lemmas 32
and 34 into a form that is needed in the proof of the upcoming Theorem 38.

######  Lemma 37.

Let $p$ be a prime with $p\equiv 1$ (mod $4$) and let
$\big{(}y(n)\big{)}_{n\geq 0}$ be an integer sequence with the property that
$v_{p}\big{(}y(n)\big{)}\geq e$ for
$n\geq\left\lceil\frac{ep}{2}\right\rceil$. For all positive integers $n$ and
$k,$ and non-negative integers $m$ and $c_{i},$ $1\leq i\leq 2n-2k,$ with
$\sum_{i=1}^{2n-2k}ic_{i}=2n-2k+m,$ $\sum_{i=1}^{2n-2k}c_{i}=m,$ and $c_{i}=0$
for all even $i,$ we have

$\left\lfloor\tfrac{2k}{p}\right\rfloor+v_{p}\left(\frac{(2n+m-1)!}{(2k-1)!\prod_{i=1}^{2n-2k}i!^{c_{i}}\,c_{i}!}\prod_{i=1}^{2n-2k}{y^{c_{i}}\big{(}\tfrac{i-1}{2}\big{)}}\right)\\\
\geq 1+\max_{c_{p}<i\leq\left\lfloor(2n+m-1)/p\right\rfloor}v_{p}(i).$ (11.15)

By convention, if $c_{p}=\left\lfloor(2n+m-1)/p\right\rfloor$ the right-hand
side is interpreted as zero (so that the inequality is trivially true).

###### Proof.

We proceed in a similar manner as in the proof of Lemma 25.

Choose $\alpha$, $\beta$, and $\gamma$ such that
$2n+m-1=n_{0}p^{\alpha}+n_{1}$, with $n_{0}$ not divisible by $p$ and
$n_{1}<p^{\beta+1}$, $p^{\beta}\leq 2n+m-1-pc_{p}<p^{\beta+1}$, and
$p^{\gamma}\leq 2k-1<p^{\gamma+1}$. These conditions imply that the $p$-adic
representations can be schematically indicated as

$\displaystyle\underset{\downarrow}{\scriptstyle\alpha}\kern 24.0pt$
$\displaystyle\underset{\downarrow}{\scriptstyle\beta}\kern-8.0pt$
$\displaystyle\underset{\downarrow}{\scriptstyle\gamma}\kern 17.0pt$
$\displaystyle\left(2n+m-1\right)_{p}$ $\displaystyle={}\dots\,$
$\displaystyle?\,0\,\dots\,0$ $\displaystyle*\dots$ $\displaystyle\,\dots.\,$
$\displaystyle\dagger$ $\displaystyle\left(2n+m-1-pc_{p}\right)_{p}$
$\displaystyle=$ $\displaystyle{\kern 3.0pt}?\,\dots$
$\displaystyle\,\dots.\,$ $\displaystyle\dagger$
$\displaystyle\left(2k-1\right)_{p}$ $\displaystyle=$ $\displaystyle\kern
0.0pt?\,\dots$ $\displaystyle*$ (11.16)

with the meaning that the shown $?$ in the first line is the $\alpha$-th digit
counted from right (the counting starting with $0$), that the left-most (non-
zero) digit of the $p$-adic representation of $2n+m-1-pc_{p}$ is the
$\beta$-th digit, and that the left-most (non-zero) digit of the $p$-adic
representation of $2k-1$ is the $\gamma$-th digit. The symbol $*$ indicates an
arbitrary digit (between $0$ and $p-1$) — not necessarily the same in the
first and in the third line, the symbol $?$ indicates an arbitrary non-zero
digit (between $1$ and $p-1$) — not necessarily the same in lines 1–3, while
$\dagger$ indicates a digit which is the same in the first and in the second
line. The reader is advised to consult (11.16) constantly while going through
the subsequent arguments.

We first dispose of the simple case in which $\beta=0$ (and hence $\gamma=0$):
in that case, by considering the schematic representation in (11.16), it
becomes apparent that $c_{p}=\left\lfloor(2n+m-1)/p\right\rfloor$. According
to the convention that we have made in the statement of the lemma, there is
nothing to prove. Hence, from now on, we assume that $\beta\geq 1$.

Now we distinguish two main cases, depending on the relative sizes of $n_{1}$
and$2n+m-1-pc_{p}$.

Case 1: $n_{1}<2n+m-1-pc_{p}$. Here, by inspection of (11.16), we see that

$\max\limits_{c_{p}<i\leq\left\lfloor{(2n+m-1)}/{p}\right\rfloor}v_{p}(i)=\alpha-1,$
(11.17)

since we obtain the $p$-adic representation of
$\left\lfloor(2n+m-1)/p\right\rfloor$ by simply deleting the right-most digit
(indicated by $\dagger$ in (11.16)) in the $p$-adic representation of
$2n+m-1$, and since $pc_{p}$ is the difference of the first two lines in
(11.16).

On the other hand, by Lemma 32, the left-hand side of (11.15) is bounded below
by

$\left\lfloor\tfrac{2k}{p}\right\rfloor+\\#\left(\text{carries when adding
$\left(2n+m-1-pc_{p}\right)_{p}$ and $(pc_{p})_{p}$}\right)\\\\[2.84526pt]
+\\#\left(\text{carries when adding $\left(2n-2k+m-pc_{p}\right)_{p}$ and
$(2k-1)_{p}$}\right)\\\\[2.84526pt]
+\tfrac{1}{2(p-1)}(2n-2k+m-pc_{p})-\tfrac{1}{p-1}s_{p}(2n-2k+m-pc_{p}).$
(11.18)

Clearly, the number of carries when adding two numbers $A$ and $B$ in their
$p$-adic representations equals the number of carries when performing the
subtraction of, say, $A$ from $A+B$. In view of this observation, inspection
of (11.16) yields that the number of carries in the first line of (11.18) is
at least $\alpha-\beta$. Hence, comparison of (11.15) with (11.17) shows that
what remains to demonstrate is that

$\left\lfloor\tfrac{2k}{p}\right\rfloor+\\#\left(\text{carries when adding
$\left(2n-2k+m-pc_{p}\right)_{p}$ and $(2k-1)_{p}$}\right)\\\\[2.84526pt]
+\tfrac{1}{2(p-1)}(2n-2k+m-pc_{p})-\tfrac{1}{p-1}s_{p}(2n-2k+m-pc_{p})\geq\beta.$
(11.19)

In order to accomplish this, we need to discuss several subcases.

If $\beta>\gamma+1$ and $\gamma\geq 0$, then $2n-2k+m-pc_{p}\geq p^{\beta}$ or
$p^{\beta-1}\leq 2n-2k+m-pc_{p}<p^{\beta}$. In the former case we may use
(11.10) to conclude that the left-hand side of (11.19) is at least
$\beta+\frac{3}{8}$, while in the latter case the number of carries in (11.19)
must be at least 1 and $2n-2k+m-pc_{p}$ must be at least $(p-1)p^{\beta-1}$;
consequently (11.11) leads to the conclusion that the left-hand side of
(11.19) is at least $1+(\beta-1)=\beta$, both confirming the inequality in
(11.19).

The case where $\beta=1$ and $\gamma=0$ needs a special treatment, to which we
will come at the end of this discussion of subcases.

If $\beta=\gamma\geq 1$, then we use (11.8) to see that $\left\lfloor
2k/p\right\rfloor$ is at least $\gamma=\beta$, again confirming (11.19). We
point out that for this conclusion we implicitly used the observation of
Remark 33.

If $\beta=\gamma+1$ and $\gamma\geq 1$, then either $2n-2k+m-pc_{p}\geq
p^{\beta}$ or the number of carries in (11.19) is at least 1. In the former
case, we may use (11.10) to see that the last line on the left-hand side of
(11.19) is at least $\beta$, as desired. In the latter case, the inequality
(11.8) specialised to $N=2k>p^{\gamma}$ implies that the left-hand side of
(11.19) is at least $1+\gamma=\beta$, again confirming (11.19). Here also,
this conclusion requires implicitly the observation of Remark 33.

Finally we discuss the remaining case where $\beta=1$ and $\gamma=0$. Here, we
have either $2p\leq 2n-2k+m-pc_{p}<p^{2}$, or $p\leq 2n-2k+m-pc_{p}<2p$, or
$1\leq 2n-2k+m-pc_{p}<p$. In the first case, the inequality (11.12) implies
that the third line on the left-hand side of (11.19) is strictly positive.
Since this is a lower bound for the left-hand side of (11.15), an integer, it
is an effective lower bound of $1=\beta$, as desired. For the second and third
cases, we observe that, since by assumption

$2n-2k+m-pc_{p}=\underset{i\neq p}{\sum_{i=1}^{2n-2k}}ic_{i},$

we must have $c_{i}=0$ for $i\geq 2p$, $c_{i}\leq 1$ for $p<i<2p$, and
$c_{i}<p$ for $3\leq i<p$. Thus, the conditions of Lemma 34 are satisfied. We
may therefore bound the left-hand side of (11.15) by

$\\#\left(\text{carries when adding $\left(2n+m-1-pc_{p}\right)_{p}$ and
$(pc_{p})_{p}$}\right)\\\\[2.84526pt] +\\#\left(\text{carries when adding
$\left(2n-2k+m-pc_{p}\right)_{p}$ and $(2k-1)_{p}$}\right)\\\\[2.84526pt]
+\tfrac{1}{p-1}(2n-2k+m-pc_{p})-\tfrac{1}{p-1}s_{p}(2n-2k+m-pc_{p}).$ (11.20)

We have already found that the number of carries in the first line is at least
$\alpha-\beta=\alpha-1$. On the other hand, under the assumption on
$2n-2k+m-pc_{p}$ in the second case, the expression in the third line equals
1. Together with (11.17), this confirms again (11.15). In the third case,
there must be at least one carry when adding $2n-2k+m-pc_{p}$ and $2k-1$ in
their $p$-adic representations, meaning that the second line in (11.20) equals
1. This again confirms (11.15).

Case 2: $n_{1}\geq 2n+m-1-pc_{p}$. Now, by inspection of (11.16), we see that

$\max\limits_{c_{p}<i\leq\left\lfloor{(2n+m-1)}/{p}\right\rfloor}v_{p}(i)\leq\beta-1.$

A moment’s thought will convince the reader that we are in exactly the same
situation as in Case 1: we must either prove (11.19) or, in the case where
$\beta=1$ and $\gamma=0$, show that the sum of the second and third lines in
(11.20) is at least 1. Hence, the remaining steps are the same as the
corresponding ones in Case 1, completing the proof. ∎

We are now in the position to prove the announced “twisted” periodicity of the
matrix entries $R^{-1}_{y}(2n,2k)$ as given by (9.1) modulo prime powers
$p^{e}$, when considered as a sequence in $n$.

######  Theorem 38.

Let $p$ be a prime with $p\equiv 1$ (mod $4$) and let
$\big{(}y(n)\big{)}_{n\geq 0}$ be an integer sequence with the property that
$v_{p}\big{(}y(n)\big{)}\geq e$ for
$n\geq\left\lceil\frac{ep}{2}\right\rceil$. For all positive integers $n,$
$k,$ and $e,$ we have

$p^{\left\lfloor
2k/p\right\rfloor}R^{-1}_{y}\left(2n+p^{e-1}(p-1),2k\right)\\\
\equiv{y^{p^{e-1}}\big{(}\tfrac{p-1}{2}\big{)}}\cdot(-1)^{(p-5)/4}p^{\left\lfloor
2k/p\right\rfloor}R^{-1}_{y}\left(2n,2k\right)\pmod{p^{e}},\quad\text{for
}n\geq e+1.$ (11.21)