%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
%\usepackage{lipsum}
\usepackage{xifthen}
%\usepackage{enumerate}

\newtheorem{thm}{Theorem}
\newtheorem{theorem}[thm]{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{obs}[thm]{Observation}

\theoremstyle{definition}
\newtheorem{dfn*}[thm]{Definition}

% Definitions:
\newcommand{\ZZ}{\mathbb Z}
\newcommand{\NN}{\mathbb N}
\newcommand{\QQ}{\mathbb Q}
\newcommand{\RR}{\mathbb R}
\newcommand{\CC}{\mathbb C}
\newcommand{\Mod}[1]{\ (\mathrm{mod}\ #1)}
\newcommand{\floor}[1]{\lfloor {#1} \rfloor}
\newcommand{\note}[1]{{\color{magenta} [{#1}]}}
\newcommand{\NNpos}{\NN^+}
% incomplete gamma function
\newcommand{\icg}[1][]{
    % \icg[s,z] = Gamma(s,z), Gamma(s,0) = Gamma(s)
    \ifthenelse{\isempty{#1}{}}
        {\Gamma(s,z)}%
        {\Gamma(#1)}%
}
% cycle restricted permutation
\newcommand{\crp}[2]{d^{#1}(#2)} 
% generalized cyclic arrangement count
\newcommand{\gs}[2]{a(#1,#2)}


%% define your title in the usual way
\title{Derangements and the $p$-Adic Incomplete Gamma Function}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[A.~O'Desky and D.~H.~Richman]{Andrew O'Desky\addressmark{1}%\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}
\and 
David Harry Richman\thanks{\href{mailto:hrichman@uw.edu}{hrichman@uw.edu}}\addressmark{2}
}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Princeton University, Princeton NJ, USA \\ 
\addressmark{2}Department of Mathematics, University of Washington, Seattle WA, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{The derangement-counting sequence satisfies strong $p$-adic regularity properties. 
We prove that these $p$-adic properties generalize to various other derangement-like sequences.
To fit these observations into a unified framework, we show the existence of a $p$-adic analogue of the incomplete gamma function.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{derangement, incomplete gamma function, $p$-adic numbers}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{derangements.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
A {\em derangement} on a finite set is a permutation with no fixed points.
The number of derangements on $n$ elements is
\begin{align}
d(n) &= \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)!,
%&= n! - n \cdot (n-1)! + \binom{n}{2} \cdot (n-2)! + \cdots 
%+ (-1)^k \binom{n}{k} (n-k)! 
%+ \cdots + (-1)^n 
\end{align}
which follows from inclusion-exclusion.
The first few values of the derangement-count\-ing sequence $d(n)$ are given in 
Table~\ref{table:derangements}.
\begin{table}[h]
\[
\begin{array}{c|cccccccccc}
  $n$  &  0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
   $d(n)$  & 1 & 0 & 1 & 2 & 9 & 44 & 265 & 1854 & 14833 & 133496
\end{array}
\]
\caption{Number of derangements.}
\label{table:derangements}
\end{table}

Can we use the values of $d(n)$ on nonnegative integers $n \in \NN$ to extrapolate a function $d(x)$ on some larger domain of inputs?
For example, what value can be reasonably assigned to $d(1/3)$ or to $d(-1)$?

One route to answering this question is via the following observation.
\begin{obs}
\label{obs:derangement-cong}
The function $f(n) = (-1)^n d(n)$ is {\em congruence preserving}
in the sense that
\begin{equation}
\label{eq:cong-preserving}
a \equiv b \Mod m 
\qquad\text{ implies } \qquad
f(a) \equiv f(b) \Mod m 
\end{equation}
for any nonnegative integers $a,b,m$.
\end{obs}
This observation was noted by Wright \cite[Theorem 1]{wright} and Barsky \cite[Proposition 5]{barsky1981analyse}.
In the language of $p$-adic analysis, Observaton~\ref{obs:derangement-cong}
%is equivalent to the statement that
implies that $(-1)^n d(n)$ is $p$-adically continuous for every prime $p$.
(Moreover, it is Lipschitz continuous with Lipschitz constant $1$.)
Since $\NN$ is dense in $\ZZ_p$, it follows that
there is a unique continuous extension $f(x) = (-1)^x d(x)$ defined on $\ZZ_p$,
interpolating values of $f$ on $\NN$.
This $p$-adic extension can be used to define $d(-1) \in \ZZ_p$ for any $p$, 
and $(-1)^{1/3}d(1/3)  \in \ZZ_p$ for any $p\neq 3$.

We now describe another ``classical'' example
of looking at a combinatorial sequence under a $p$-adic lens.
An {\em arrangement} on a finite set $[n]$ is a choice of subset $A \subset [n]$ and a choice of permutation on $A$.
The number of arrangements on $[n]$ is
\begin{equation}
a(n) = \sum_{k=0}^n \binom{n}{k} k! .
\end{equation}
\begin{table}[h]
\centering
\begin{tabular}{c|cccccccccc}
  $n$  &  0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
   $a(n)$  & 1 & 2 & 5 & 16 & 65 & 326 & 1957 & 13700 & 109601 & 986410
\end{tabular}
\caption{Number of arrangements.}
\label{table:arrangements}
\end{table}
\begin{obs}
\label{obs:arrangement-cong}
The function $a(n)$ is {congruence preserving}
in the sense of \eqref{eq:cong-preserving}.
\end{obs}
This observation was noted by Hall \cite[Corollary 2]{hall-1971},
who also made note of the floor function identity $a(n) = \floor{e \, n!}$ 
when $n\geq 1$.
In \cite{hall-1971} Hall investigates general properties of the set of all congruence preserving functions $\NN \to \ZZ$, and calls such functions {\em pseudo-polynomials};
it contains the polynomials $\ZZ[x]$ as a strict subset.


In this article, which is an extended abstract for \cite{odesky-richman}, we describe several new extensions of this phenomenon,
where a combinatorially-defined sequence satisfies strong $p$-adic regularity.
These extensions are described in Sections~\ref{sec:cyclic-derangements} and \ref{sec:cycle-restricted-perm}.
In Section~\ref{sec:p-inc-gamma}, we describe how to construct a continuous, two-variable $p$-adic function 
which is a natural analogue to the incomplete gamma function.

%Miska \cite{miska}


\subsection{$r$-cyclic derangements and arrangements}
\label{sec:cyclic-derangements}
Let $C_r$ denote the cyclic group of order $r$.
The wreath product $C_r \wr S_n$
can be realized as the subgroup of $GL_n(\CC)$ generated by the permutation matrices and the diagonal matrices of (multiplicative) order $r$;
it is a finite group of order $r^n n!$.

The action of the symmetric group $S_n$ on 
the finite set $[n]$
generalizes to a natural action of $C_r \wr S_n$
on the set $[r] \times [n]$.
In the matrix representation described above, the set $[r] \times [n]$ can be identified with the orbit of the unit coordinate vectors in $\CC^n$.
We say an element of $C_r \wr S_n$
is an {\em $r$-cyclic derangement} 
if its action on $[r] \times [n]$ has no fixed points.
For example,
the $2$-cyclic derangements for $n=2$ %is $d(2,2) = 5$, 
correspond to the matrices
$$
\begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix},
\qquad
\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix},
\qquad
\begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix},
\qquad
\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix},
\qquad
\begin{pmatrix} 0 & -1 \\ -1 & 0 \end{pmatrix}.
$$
The study of such generalized derangements was initiated by 
Faliharimalala--Zeng \cite[Equation (2.7)]{faliharimalala-zeng}
and
Assaf \cite[Theorem 2.1]{assaf}, 
who gave the following expression for the number of $r$-cyclic derangements:
\begin{equation}
\label{eq:cyc-derangements}
d(n,r) = \sum_{k=0}^n (-1)^k \binom{n}{k} r^{n-k} (n-k)! .
%= (-1)^n \sum_{k=0}^n (-1)^k \binom{n}{k} r^k k!
\end{equation}
(For an interesting $q$-analogue extension of \eqref{eq:cyc-derangements}, see 
\cite[Equation (2.5)]{faliharimalala-zeng-2011}.)

We similarly define an {\em $r$-cyclic arrangement} on $[r]\times[n]$ as a choice of subset $A \subset [n]$ and an element of $C_r \wr S_{|A|}$.
The number of $r$-cyclic arrangements on $[r]\times [n]$ is
\begin{equation}
\label{eq:cyc-arrangements}
a(n,r) 
%= \sum_{k=0}^n \binom{n}{k} r^{n-k} (n-k)!.
= \sum_{k=0}^n \binom{n}{k} r^k k!.
\end{equation}
The $p$-adic regularity of derangements and arrangements extend to $d(n,r)$ and $a(n,r)$, 
for each choice of $r$.
\begin{thm}\label{thm:cyclic-derangements}
Let $p$ be a prime.
\begin{enumerate}
\item
For any positive integer $r$,
the function $n\mapsto (-1)^n d(n,r)$ is $p$-adically continuous.

\item 
For any positive integer $r$,
the function $n \mapsto a(n,r)$
is $p$-adically continuous.
\end{enumerate}
\end{thm}
For convenience,
the two cases of Theorem~\ref{thm:cyclic-derangements}
%the expressions \eqref{eq:cyc-derangements} and \eqref{eq:cyc-arrangements} 
may be combined into a single one:
when $r$ is replaced with a negative integer $-r$ in
the expression \eqref{eq:cyc-arrangements}, we obtain
\begin{equation*}
a(n,-r) := \sum_{k=0}^n \binom{n}{k} (-r)^k k!
= (-1)^n d(n,r).
\end{equation*}
We also note that 
the upper limit 
in the sum \eqref{eq:cyc-arrangements} 
may be extended to infinity without changing the value
$a(n,r) = \sum_{k=0}^\infty \binom{n}{k} r^k k! $, 
since the terms with $k > n$ all vanish.
We will return to the expression $a(n,r)$ in Section~\ref{sec:p-inc-gamma}.

\subsection{Cycle restricted permutations}
\label{sec:cycle-restricted-perm}

A derangement is a permutation whose cycle type 
%is restricted to have 
has no length-$1$ cycles.
More generally, we may be interested in the class of permutations whose cycle type is restricted to having lengths in a given set.
For any set of positive integers $L$, let
\begin{equation}
\label{eq:crp-def}
\crp{L}{n} = \# (\text{permutations in $S_n$ with cycle lengths in } L).
\end{equation}
We call such permutations counted by $\crp{L}{n}$ the {\em cycle restricted permutations} of $L$.
Thus the usual derangement numbers satisfy $d(n) = \crp{L}{n}$ for $L = \{2,3,4,\ldots\}$,
and counting all permutations we have $n! = \crp{L}{n}$ for $L = \NNpos$.
\begin{theorem}
\label{thm:intro-p-derangement}
Let $L$ be a set of positive integers,
and let $\crp{L}{n}$ be defined by \eqref{eq:crp-def}.
%    the number of permutations in $S_n$ 
%    whose cycle lengths are in $L$. 
    Let $p$ denote a prime.
    For $p \geq 3$:
\begin{enumerate}
\item 
%For a prime $p\geq 3$,
%If $1 \in L$, then 
$\crp{L}{n}$ is $p$-adically continuous 
    if and only if $1\in L$ and  $p \not\in L$.
\item 
%If $1 \not\in L$, then 
%For a prime $p\geq 3$,
$ (-1)^n \crp{L}{n}$ is $p$-adically continuous if and only if 
$1 \not\in L$ and $p  \in L$.
\\

In the case $p=2$: $(-1)^n$ is $2$-adically continuous, and 
\item 
$\crp{L}{n}$ is $2$-adically continuous 
%(equivalently, $(-1)^n \crp{L}{n}$ is $2$-adically continuous)
if and only if $1\in L$ and $2 \not\in L$, or $1 \not\in L$ and $2\in L$.
\end{enumerate}
\end{theorem}

For example, let $\{3^i\} := \{1, 3, 9, 27, \ldots \}$ denote the set of powers of $3$;
the initial values of $\crp{\{3^i\}}{n}$  are shown in Table~\ref{table:3i-restricted}.
The function $n\mapsto \crp{\{3^i\}}{n}$ can be $p$-adically interpolated by a continuous function on $\ZZ_p$ if and only if $p\neq 3$. 
\begin{table}[h]
\centering
\begin{tabular}{c|cccccccccc}
  $n$  &  0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
   $\crp{\{3^i\}}{n}$  & 1 & 1 & 1 & 3 & 9 & 21 & 81 & 351& 1233 & 46089
\end{tabular}
\caption{Number of $\{3^i\}$-cycle restricted permutations.}
\label{table:3i-restricted}
\end{table}

An essential step to proving Theorem~\ref{thm:intro-p-derangement} 
is the following formal power series identity. 
\begin{proposition}\label{prop:EGFcrp} % {{{
    Let $\crp{L}{n}$ be defined by \eqref{eq:crp-def}. 
%    the number of permutations in $S_n$
%    whose cycle lengths are in $L$.
%$$\crp{L}{n} = \#\{\sigma \in S_n  \;:\; 
%        \text{every cycle length of $\sigma$ is in } L \}.$$
    Then the exponential generating function 
    %$F(X) = \sum_{n\geq 0} \crp{L}{n} \frac{X^n}{n!} $ 
    of $\crp{L}{n}$ factors as %is given by  
    \begin{equation*}
        \label{eqn:EGFcpn}
        \sum_{n\geq 0} \crp{L}{n} \frac{X^n}{n!} 
        = \prod_{{r \in L}} 
    \exp\left( \frac{X^r}{r} \right).
    \end{equation*}
\end{proposition} % }}}
The proof is a convenient 
application of combinatorial species 
(see \cite[\S1]{nelson1990} 
for a quick introduction 
or \cite{bll} for a comprehensive treatment). 
To connect Proposition~\ref{prop:EGFcrp} to Theorem~\ref{thm:intro-p-derangement},
we apply Mahler's criterion for $p$-adic continuity as described in Section~\ref{sec:p-continuity}.


\subsection{A $p$-adic incomplete gamma function}
\label{sec:p-inc-gamma}

Just as the values of the gamma function at positive integers 
count permutations, 
%we will see that 
the values of the incomplete gamma function 
%at 
%$(n,r) \in\NNpos \times \ZZ $
essentially count $r$-cyclic arrangements and derangements  
on $[r]\times [n]$ (see Section \ref{sec:cyclic-derangements}).
The $p$-adic regularity of Theorem \ref{thm:cyclic-derangements} can be strengthened to $p$-adic continuity in both variables of $\gs{n}{r}$ jointly,
and this leads to a construction for a $p$-adic incomplete gamma function.

Recall that the (upper) incomplete gamma function $\Gamma(s,z)$ %on $\CC \times \CC$
is defined for $s,z\in \RR$, $z > 0$, by the integral 
\begin{equation}
\label{eq:inc-gamma-integral}
\Gamma(s,z) = \int_z^\infty t^s \exp(-t) \frac{dt}{t} .
\end{equation}
%(The integral converges when $ \mathrm{Re}(s) > 1$, and is 
(The function $\Gamma(s,z)$ may be extended to  $s,z \in \CC$ by analytic continuation.)
In analogy with 
the classical formula $\Gamma(n+1) = n!$ 
we may verify that
    \begin{equation}
    \label{eqn:gamma-arrangement}
    \icg[n+1, 1/r] 
    =
        \gs{n}{r}r^{-n}e^{-1/r} 
    \end{equation}
for $(n,r) \in\NN \times \ZZ \setminus\{0\}$, 
where $\gs{n}{r}$ is given by \eqref{eq:cyc-arrangements}. 
Recall that $\gs{n}{r}$ counts $r$-cyclic arrangements 
if $r > 0$,
resp. $(-r)$-cyclic derangements if $r < 0$.

Equation \eqref{eqn:gamma-arrangement} shows that the $p$-adic continuity of the incomplete gamma function essentially reduces to 
the $p$-adic continuity of $a(n,r)$.
% in the argument $n$, with $r$ fixed,
Theorem \ref{thm:cyclic-derangements} may be strengthened to observe that $a(n,r)$ is jointly continuous in both arguments $p$-adically.
As a technicality to deal with the transcendental factor $e^{-1/r}$ in \eqref{eqn:gamma-arrangement}, 
we need to choose a field homomorphism $\tau_p \colon \QQ(e) \to \QQ_p$.
For this choice we let $\tau_p(1/e) = \sum_{k\geq 0} p^k / k!$.

\begin{theorem}\label{thm:incomplete-gamma} % {{{
There exists a unique continuous function 
    $\Gamma_{p}\colon\ZZ_p \times (1+p\ZZ_p)\to \ZZ_p$
    satisfying 
$$
\Gamma_{p}(n,1/r) = 
    \tau_p\icg[n,1/r]
$$ 
for any positive integers $n$ and $r$ satisfying $r \equiv 1 \Mod p$. 
Explicitly, for any $s \in \ZZ_p$ and $z \in 1 + p\ZZ_p$ we have
\begin{equation} % {{{
%	\Gamma_p(s+1,1/r) = \exp_p(p/r) r^{-s} \sum_{k=0}^\infty  \binom{s}{k} r^{k}  k! 
    \Gamma_p(s,z) = \exp_p(pz) z^{s-1} \sum_{k=0}^\infty \binom{s-1}{k} z^{-k}  k!,
\end{equation} % }}}
where $\exp_p(x) = \sum_{k\geq 0} x^k/k!$ is the $p$-adic exponential function on $\ZZ_p$.  
\end{theorem} % }}}
We hope that the $p$-adic incomplete gamma function constructed in Theorem~\ref{thm:incomplete-gamma} may have
interesting applications in number theory.
See Section~\ref{sec:gamma} for related discussion.

\section{$p$-adic continuity}
\label{sec:p-continuity}
In this section we briefly recall 
some results from 
$p$-adic analysis.
% for the reader's convenience. 
For more background 
we refer to \cite{robert-2000,schikhof}. 
%Let $p$ denote a prime number. 
%Let $K$ be a subfield of $\CC_p$. 
For an introduction to $p$-adic numbers, see \cite{koblitz}.

Given a function $f \colon \NN \to \QQ$, 
the basic question of $p$-adic interpolation is whether $f$ 
extends to a continuous function 
%(Lipschitz function, 
%locally analytic function, 
%analytic function, etc.) 
$\widetilde{f} \colon \ZZ_p \to \QQ_p$. 
%In other words, whether there exists 
%a function $f_p$ fitting into a commutative diagram:  
%\begin{equation}
%\begin{tikzcd}
%    \NN \arrow[d,"\subset"] \arrow[r,"f"]&\CC_p \arrow[d,"="] \\
%    \ZZ_p \arrow[r,"f_p"] & \CC_p
%\end{tikzcd}
%\end{equation}
%where $f_p$ is continuous in the $p$-adic topology.
%If a continuous extension exists 
%then it is unique. 
%since $\NN \subset \ZZ_p$ 
%is dense in the $p$-adic topology.
This question is generally approached 
using 
Mahler expansions and finite differences. 

\subsection{Mahler expansion}

For a nonnegative integer $k$, let $\binom{x}{k} \in \QQ[x]$
denote the polynomial 
\begin{equation*}
\binom{x}{k} = \frac{x(x-1)\cdots(x-k+1)}{k!}.
\end{equation*}
The polynomials $\{ \binom{x}{k} : k = 0,1,2,\ldots\}$ form a basis of $\QQ[x]$
as a $\QQ$-vector space.

\begin{dfn*}
A {\em Mahler series} is an expression of the form
$\sum_{k\geq 0}c_k \binom{x}{k} $
where $c_k \in \QQ$.
A function $f$ admits a {\em Mahler expansion}
if there are constants $c_k$ such that 
\begin{equation*}
f(x) = \sum_{k\geq 0} c_k \binom{x}{k}
= c_0 + c_1 \binom{x}{1} + c_2 \binom{x}{2} + \cdots 
\end{equation*}
for all $x$ in the domain of $f$.
The constants $c_k$ are the {\em Mahler coefficients} of $f$.
\end{dfn*}
It is helpful to think of Mahler expansions as a ``discrete analogue'' to Taylor expansions in calculus.
A function on the domain $\ZZ$ or $\ZZ_p$ may fail to admit a Mahler expansion, but a function %$f: \NN \to \QQ$ 
on $\NN$ always has a Mahler expansion.
Finding a Mahler expansion for a function $f: \NN \to \QQ$ means 
to solve for $c_k$ in the system of equations
\begin{equation}
\label{eq:mahler-to-f}
f(n) = \sum_{k=0}^n \binom{n}{k} c_k
\qquad \text{for }n = 0,1,2,\ldots .
\end{equation}
%which are linear in $c_k$.
The constant coefficient is simply $c_0 = f(0)$,
and the other coefficients can be found using finite differences.
The {\em finite difference operator} $\Delta$ is defined by
\begin{equation*}
\Delta f(x) = f(x+1) - f(x).
\end{equation*}
Applied to the polynomial $\binom{x}{k}$, we have the familiar combinatorial identity
%\begin{equation*}
$
\Delta \binom{x}{k} = \binom{x+1}{k} - \binom{x}{k}
= \binom{x}{k-1}.
$
%\end{equation*}
Taking iterated finite differences, we have $\Delta^i \binom{n}{k} = \binom{n}{k-i}$ if $i \leq k$ and $0$ otherwise.
%so that
%$$
%\Delta_i
%$$
Assuming that $f(x) = \sum_{k \geq 0} c_k \binom{x}{k}$,
we have
$$
\Delta^i f(x) = \sum_{k \geq i} c_k \binom{x}{k-i}
= c_i + c_{i+1} \binom{x}{1} + c_{i+2}\binom{x}{2} + \cdots
$$
hence
\begin{equation}
\label{eq:f-to-mahler}
c_n = \Delta^n f(0) = \sum_{k}(-1)^k\binom{n}{k} f(n-k)
\qquad\text{for } n=0, 1, 2, \ldots 
\end{equation}
yields a solution to \eqref{eq:mahler-to-f}.
To summarize,
we have shown that an arbitrary  function $f: \NN \to \QQ$ has Mahler coefficients given by \eqref{eq:f-to-mahler}

The question of which $f: \NN\to \QQ$ admit a continuous extension to $\ZZ_p \to \QQ_p$ was conveniently answered by Mahler,
using Mahler coefficients.
Let $|\cdot|_p: \ZZ_p \to \RR$ denote the $p$-adic absolute value.
\begin{theorem}[Mahler {\cite[Lemma 1, Theorem 1]{mahler}}]
Suppose $f : \NN \to \QQ$ is a function with Mahler coefficients $c_k$.
Then $f$ extends to a continuous function $\widetilde{f}: \ZZ_p \to \QQ_p$ if and only if $|c_k|_p \to 0$ as $k \to \infty$.
\end{theorem}

For example, the function $f(n) = 3^n$ has Mahler coefficients
$$
c_n = \sum_{k=0}^n (-1)^k \binom{n}{k} 3^{n-k} = (3 - 1)^n = 2^n .
$$
%so we have the Mahler expansion
%$
%3^x = (1+2)^x = 1 + 2 \binom{x}{1} + 2^2 \binom{x}{2} + \cdots. 
%$
By Mahler's theorem, $3^x$ extends continuously to $x \in \ZZ_p$ if and only if $|2^n|_p \to 0$ as $n \to \infty$, 
which occurs if and only if $p=2$.
A similar argument shows that $(-1)^x$ extends continuously to $x \in \ZZ_p$ if and only if $p=2$.

\subsection{Exponential generating functions}

The relation between a function's values $f(n) =: a_n$ and its Mahler coefficients $c_n$ 
has a convenient expression using exponential generating functions (EGFs).
The exponential generating function of a sequence $(a_n)$ is the formal power series
$$
\sum_{n=0}^\infty a_n \frac{X^n}{n!} \in \QQ[[X]].
$$
\begin{proposition}
Consider two sequences $(a_n)$ and $(c_n)$ of rational numbers,
with associated EGFs
$$
A(X) = \sum_{n\geq 0} a_n \frac{X^n}{n!},
\qquad
C(X) = \sum_{n\geq 0} c_n \frac{X^n}{n!}.
$$
Then the following are equivalent:
\begin{enumerate}
\item 
$(c_n)$ are the Mahler coefficients of the function $f(n) = a_n$;

\item 
$a_n = \sum_{k=0}^n \binom{n}{k} c_k$;

\item 
$c_n = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} a_k$;

\item 
$A(X) = \exp({X}) C(X)$, where $\exp(X) = \sum_{n\geq 0} \frac{X^n}{n!}$.
\end{enumerate}
\end{proposition}


\subsection{Analyzing cycle restricted permutations}

To deduce Theorem~\ref{thm:intro-p-derangement} from Proposition~\ref{prop:EGFcrp},
we need to combine the following statements.
Recall that for a set $L$ of cycle lengths,
the counts of cycle restricted permutations  $\crp{L}{n}$
satisfy the generating function identity
\begin{equation*}
\sum_{n\geq 0} \crp{L}{n} \frac{X^n}{n!}
= \prod_{r \in L} \exp \left(\frac{X^r}{r}\right).
\end{equation*}
Thus we focus our attention on individual factors
$\exp\left(\frac{X^r}{r}\right)$ for $r \in \NNpos$,
or for slightly more generality their integer powers
$\exp\left(\frac{m X^r}{r}\right)$ for $m \in \ZZ$.
\begin{proposition}
Let $r$ be a positive integer and $m\in \ZZ$.
Consider the formal power series
$$
\sum_{n \geq 0} c_n \frac{X^n}{n!} := 
\exp\left(\frac{m X^r}{r}\right).
$$
\begin{enumerate}
\item 
If $r = 1$ or $p$, then $|c_n|_p \to 0$ as $n\to \infty $ 
if and only if $p $ divides $ m$.

\item 
If $r \neq 1$ or $p$, then $|c_n|_p \to 0$ as $n\to \infty $.
\end{enumerate}
\end{proposition}
We then address the case of an infinite product of factors of this type.
\begin{proposition}
Let $m_1,m_2,\ldots \in \ZZ$, 
and consider the 
%{\em zeta function associated to $m = (m_1,m_2,\ldots)$} is the 
formal power series  in $\QQ_p[[X]]$ defined by the infinite product
\begin{equation}
\sum_{n \geq 0} c_n \frac{X^n}{n!} := 
\prod_{r=1}^\infty \exp\left( \frac{m_rX^r}{r}\right). 
\end{equation}
Then % $\zeta_m$ is in $V$
the EGF coefficients $c_n$ satisfy 
$|c_n|_p \to 0$ as $n\to \infty$
if and only if 
$m_1 \equiv m_p \Mod p$. 
\end{proposition}
We leave the details of the proof  in \cite{odesky-richman} for the interested reader.

\section{Parallel story: factorials and the gamma function}
\label{sec:gamma}
The factorial $n!$ counts the number of permutations on a finite set of $n$ elements.
The first few values are shown in Table~\ref{table:factorials}.
\begin{table}[h]
\centering
\begin{tabular}{c|cccccccccc}
  $n$  &  0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
   $n!$  & 1 & 1 & 2 & 6 & 24 & 120 & 720 & 5040 & 40320 & 362880
\end{tabular}
\caption{Number of permutations.}
\label{table:factorials}
\end{table}

The question of whether the values $n!$ can be interpolated over $\RR$ (or $\CC$) is classical, going back to Euler and Gauss.
The gamma function $\Gamma(s)$ is 
%a complex number which interpolates the factorial function,
defined for positive real $s$ by the integral
\begin{equation}\label{eqn:gamma-integral}
\Gamma(s) = \int_0^\infty t^s\exp(-t) \frac{dt}{t} ,
\end{equation}
and satisfies 
$
\Gamma(n+1) = n! .
$
(Compare to \eqref{eq:inc-gamma-integral} earlier.)
The function $\Gamma(s)$ can be extended by analytic continuation to a meromorphic function on $s \in \CC$.

The question of whether $n!$ can be interpolated $p$-adically is more recent.
It is straightforward to compute the Mahler coefficients of 
the factorial function
\begin{equation}
n! = 1 + 1\binom{n}{2} + 2\binom{n}{3} + 9\binom{n}{4} + 44\binom{n}{5} + \cdots ;
\end{equation}
these coefficients in fact coincide with the derangement numbers $d(n)$ (cf. Table~\ref{table:derangements}).
The $p$-adic absolute value $|d(n)|_p$ does not decay as $n\to\infty$ for any prime $p$,
so the function $n\mapsto n!$ is not $p$-adically continuous
by Mahler's theorem.

Morita \cite{morita-1975} discovered that it is possible to $p$-adically interpolate a ``factorial-like'' function, after making the following tweaks:
\begin{equation}
\label{eq:morita}
\Gamma_{p}^{Mor}(n+1) = (-1)^{n+1} \prod_{\substack{1\leq k \leq n \\ p \not\;\mid \;  k}} k.
\end{equation}
Namely, an alternating sign is introduced, and integer multiples of $p$ are left out of the product.
The formula \eqref{eq:morita} defines a $p$-adic continuous function $\Gamma_p^{Mor} \colon \ZZ_p \to \ZZ_p$.
Morita's $p$-adic analogue of the gamma function was found to satisfy various nice arithmetic formulas, see, \textit{e.g.}, Gross--Koblitz
\cite{gross-koblitz-1979}.

Since the gamma function in the classical (Archimedean) case 
is reached by taking a limit in one argument of the incomplete gamma function,
namely
$\Gamma(s) = \lim_{z \to 0} \Gamma(s,z)$,
it is natural to expect a nice relation
between Morita's $p$-adic gamma function 
(or perhaps another $p$-adic gamma function analogue)
and the $p$-adic incomplete gamma function constructed in Section~\ref{sec:p-inc-gamma}.
Such a relation is currently beyond  our understanding.
We hope to explore this in future work.

\acknowledgements{We thank Sami Assaf, Daniel Barsky, A. Suki Dasher, Jeffrey Lagarias, and Julian Rosen for helpful comments, corrections, and inspiration for this work.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}
