text:
\begin{document}
\begin{center}

 {\large \bf Ramanujan-type Congruences for Overpartitions Modulo $5$}

\end{center}

\begin{center}
{  William Y.C. Chen}$^{a,b}$, {Lisa H. Sun}$^{a,*}$, {Rong-Hua Wang}$^{a}$  and
  {Li Zhang}$^{a}$ \vskip 2mm

   $^{a}$Center for Combinatorics, LPMC-TJKLC\\
   Nankai University, Tianjin 300071, P. R. China\\[6pt]
   $^{b}$Center for Applied Mathematics\\
Tianjin University,  Tianjin 300072, P. R. China\\[12pt]

    chen@nankai.edu.cn, $^{*}$sunhui@nankai.edu.cn, \\
    wangwang@mail.nankai.edu.cn, zhangli427@mail.nankai.edu.cn
\end{center}

\vskip 6mm \noindent {\bf Abstract.}  Let $\overline{p}(n)$ denote the number of overpartitions of $n$. Hirschhorn and Sellers showed that $\overline{p}(4n+3)\equiv 0 \pmod{8}$ for   $n\geq 0$. They also conjectured that $\overline{p}(40n+35)\equiv 0 \pmod{40}$ for $n\geq 0$.  Chen and Xia proved this conjecture by using the $(p,k)$-parametrization of theta functions given by Alaca, Alaca and Williams. In this paper, we show that
$\overline{p}(5n)\equiv (-1)^{n}\overline{p}(4\cdot 5n) \pmod{5}$ for $n \geq 0$ and  $\overline{p}(n)\equiv (-1)^{n}\overline{p}(4n)\pmod{8}$ for $n \geq 0$ by using the relation of the generating function of $\overline{p}(5n)$ modulo $5$ found by Treneer and the $2$-adic expansion of the generating function of $\overline{p}(n)$ due to Mahlburg. As a consequence, we deduce that $\overline{p}(4^k(40n+35))\equiv 0 \pmod{40}$ for $n,k\geq 0$.
Furthermore, applying the Hecke operator on $\phi(q)^3$ and the fact that $\phi(q)^3$ is a Hecke eigenform, we obtain an infinite family of congrences $\overline{p}(4^k \cdot5\ell^2n)\equiv 0 \pmod{5}$, where $k\ge 0$ and $\ell$ is a prime such that $\ell\equiv3 \pmod{5}$ and $\left(\frac{-n}{\ell}\right)=-1$.
Moreover, we show that $\overline{p}(5^{2}n)\equiv \overline{p}(5^{4}n) \pmod{5}$ for $n \ge 0$. So we are led to the congruences $\overline{p}\big(4^k5^{2i+3}(5n\pm1)\big)\equiv 0 \pmod{5}$ for $n, k, i\ge 0$.
In this way, we obtain various Ramanujan-type congruences for $\overline{p}(n)$ modulo $5$ such as $\overline{p}(45(3n+1))\equiv 0 \pmod{5}$ and $\overline{p}(125(5n\pm 1))\equiv 0 \pmod{5}$ for $n\geq 0$.

\noindent {\bf Keywords}: overpartition, Ramanujan-type congruence, modular form, Hecke operator, Hecke eigenform

\noindent {\bf MSC(2010)}: 05A17, 11P83

\section{Introduction}

 The objective of this paper is to use  half-integral weight modular forms to derive three infinite families of congruences for overpartitions modulo $5$.

 Recall that a partition of a nonnegative integer $n$ is a nonincreasing sequence of positive integers whose sum is $n$. An overpartition of $n$ is a partition of $n$ where the first occurrence of each distinct part may be overlined. We denote the number of overpartitions of $n$ by $\overline{p}(n)$. We set $\overline{p}(0)=1$ and $\overline{p}(n)=0$ if $n<0$. For example, there are eight  overpartitions of $3$
\[3,\ \bar{3},\ 2+1,\ \bar{2}+1,\ 2+\bar{1},\ \bar{2}+\bar{1},\ 1+1+1,\ \bar{1}+1+1.\]

Overpartitions arise in combinatorics \cite{Corteel-Lovejoy-2003}, $q$-series \cite{Corteel-Hitczenko-2004}, symmetric functions \cite{Berndt-2006}, representation theory \cite{Kang-Kwon-2004},
mathematical physics \cite{1-Fortin-Jacob-Mathieu-2005,Fortin-Jacob-Mathieu-2005} and number theory \cite{Lovejoy-2004,Lovejoy-Mallet-2011}.
They are also called standard MacMahon diagrams, joint partitions,  jagged partitions or dotted partitions.

 Corteel and Lovejoy \cite{Corteel-Lovejoy-2003} showed that the generating function of $\overline{p}(n)$ is given by
\[
\sum_{n\geq0}\overline{p}(n)q^n= \frac{(-q;q)_\infty}{(q;q)_\infty}.
\]
Recall that the generating function of $\overline{p}(n)$ can be expressed as
\begin{equation*}
\sum_{n\geq0}\overline{p}(n)q^n=\frac{1}{\phi(-q)},
\end{equation*}
where $\phi(q)$ is Ramanujan's  theta function as defined by
\begin{equation}\label{sum}
\phi(q)=\sum_{n=-\infty}^{\infty}q^{n^2},
\end{equation}
see Berndt \cite{Berndt-2006}.

On the other  hand,  the generating function of $\overline{p}(n)$ has the following $2$-adic expansion
\begin{align}\label{L-2-1}
\sum_{n\geq0}\overline{p}(n)q^n=1+\sum_{k=1}^{\infty}2^k\sum_{n=1}^{\infty}(-1)^{n+k}c_k(n)q^n,
\end{align}
 where $c_k(n)$ denotes the number of representations of $n$
 as a sum of $k$ squares of positive integers. The above
 $2$-adic expansion \eqref{L-2-1}  is useful
 to derive congruences for $\overline{p}(n)$ modulo powers of $2$, see, for example \cite{Kim-2008-1,Kim-2009,Mahlburg-2004}.

By employing  dissection
formulas, Fortin, Jacob and Mathieu \cite{Fortin-Jacob-Mathieu-2005}, Hirschhorn and Sellers \cite{1-Hirschhorn-Sellers-2005} independently derived various Ramanujan-type congruences for $\overline{p}(n)$, such as
\begin{equation}\label{4n+3}
\overline{p}(4n+3)\equiv 0 \pmod{8}.
\end{equation}
Hirschhorn and Sellers \cite{1-Hirschhorn-Sellers-2005} proposed the following conjectures
\begin{align}
&\overline{p}(27n+18)\equiv 0 \pmod{12},  \label{1-r-1}\\[5pt]
&\overline{p}(40n+35)\equiv 0 \pmod{40}.   \label{1-r-2}
\end{align}
They also conjectured that if $\ell$ is prime and $r$ is a quadratic nonresidue modulo $\ell$ then
\begin{align}\label{1-r-3}
\overline{p}(\ell n+r)\equiv\left\{
 \begin{array}{ll}
   0 \pmod{8} &\mbox{if $\ell\equiv\pm1 \pmod{8}$,}\\[5pt]
   0 \pmod{4} &\mbox{if $\ell\equiv\pm3 \pmod{8}$.}
     \end{array}
   \right.
\end{align}

By using the $3$-dissection formula for $\phi(-q)$, Hirschhorn and Sellers \cite{2-Hirschhorn-Sellers-2005} proved \eqref{1-r-1} and obtained  a family of congruences
\begin{align*}
\overline{p}(9^\alpha(27n+18))\equiv 0 \pmod{12},
\end{align*}
where $n,\alpha \geq 0$.

Employing the $2$-dissection formulas of theta functions due to Ramanujan, Hirschhorn and Sellers \cite{1-Hirschhorn-Sellers-2005}, Chen and Xia \cite{Chen-Xia-2013} obtained a generating function of $\overline{p}(40n+35)$ modulo $5$. Using the $(p,k)$-parametrization of theta functions given by Alaca, Alaca and Williams \cite{AAW-2006}, they showed that
\begin{align}\label{40n+35-mod5}
\overline{p}(40n+35)\equiv 0 \pmod{5}.
\end{align}
This proves Hirschhorn and Sellers' conjecture \eqref{1-r-2} by combining congruence \eqref{4n+3}.
Applying the $2$-adic expansion \eqref{L-2-1}, Kim \cite{Kim-2009} proved  \eqref{1-r-3} and obtained  congruence properties  of $\overline{p}(n)$ modulo 8.

For powers of $2$, Mahlburg \cite{Mahlburg-2004} showed that $\overline{p}(n)\equiv0 \pmod{64}$ holds for a set of integers of arithmetic density $1$. Kim \cite{Kim-2008-1} showed that $\overline{p}(n)\equiv0 \pmod{128}$ holds for a set of integers of arithmetic density $1$. For the modulus $3$,
 by using the fact that $\phi(q)^5$ is a Hecke eigenform in the half-integral weight modular form space $M_{\frac{5}{2}}(\tilde{\Gamma}_0(4))$, Lovejoy and Osburn \cite{LOQ11} proved that
\[
\overline{p}(3\ell^3 n)\equiv0 \pmod{3},
\]
where $\ell\equiv2 \pmod{3}$ is an odd prime and $\ell \nmid n$.
Moreover, by utilizing  half-integral weight modular forms, Treneer \cite{Treneer-2006} showed that for a prime $\ell$ such that $\ell\equiv-1 \pmod{5}$,
\begin{align*}
\overline{p}(5 \ell^3 n)\equiv0 \pmod{5},
\end{align*}
for all $n$ coprime to $\ell$.

In this paper, we   establish the following two congruence relations for overpartitions modulo $5$ and modulo $8$ by using a relation of the generating function of $\overline{p}(5n)$ modulo $5$  and applying the $2$-adic expansion \eqref{L-2-1}.

\begin{thm}\label{rel-mod5}
For   $n\geq0$, we have
\begin{align}\label{recmod5}
&\overline{p}(5n)\equiv (-1)^{n}\overline{p}(4\cdot 5n) \pmod{5}.
\end{align}
\end{thm}

\begin{thm}\label{rel-mod8}
For $n\geq0$, we have
\begin{align}\label{formula-mod8}
\overline{p}(n)\equiv (-1)^{n}\overline{p}(4n)\pmod{8}.
\end{align}
\end{thm}

Combining the above two congruence relations with congruences \eqref{4n+3} and \eqref{40n+35-mod5}, we arrive at a family of congruences modulo 40.

\begin{coro}\label{gen-HS}
For  $n,k\geq0$, we have
\begin{align}\label{m1}
\overline{p}(4^k(40n+35))\equiv 0 \pmod{40}.
\end{align}
\end{coro}

 Based on the Hecke operator on $\phi(q)^3$ and the fact that $\phi(q)^3$ is a Hecke eigenform in   $M_{\frac{3}{2}}(\tilde{\Gamma}_0(4))$, we obtain
  a family of congruences for  overpartitions modulo $5$.

\begin{thm}\label{thm-2}  Let $\left(\frac{\cdot}{\ell}\right)$ denote the Legendre symbol.
Assume that  $k$ is a nonnegative integer and $\ell$ is a prime with $\ell\equiv3 \pmod{5}$. Then we have
\begin{align*}
\overline{p}(4^k \cdot5\ell^2n)\equiv 0 \pmod{5},
\end{align*}
where $n$ is a nonnegative integer such that $\left(\frac{-n}{\ell}\right)=-1$.
\end{thm}

 Using the properties of  the Hecke operator $T_{\frac{3}{2},16}(\ell^2)$ and the Hecke eigenform $\phi(q)^3$, we are led to another congruence relation for overpartitions modulo $5$.

\begin{thm}\label{relation-mod5}
For  $n\geq0$, we have
\begin{align}\label{T-5-1}
&\overline{p}(5^{2}n)\equiv \overline{p}(5^{4}n) \pmod{5}.
\end{align}
\end{thm}

Combining \eqref{recmod5} and \eqref{T-5-1}, we find the
 following family of congruences modulo 5.

\begin{coro}\label{coro-2}
For $n,k,i\geq0$, we have
\begin{align}\label{infi-con-3}
\overline{p}\big(4^k5^{2i+3}(5n\pm1)\big)\equiv 0 \pmod{5}.
\end{align}
\end{coro}

\section{Preliminaries}

To make this paper self-contained, we recall some definitions and notation on half-integral weight modular forms. For more details, see \cite{Chen-Du-Hou-Sun-2012,Treneer-2006,Koblitz-1993,
Ono-2004,Shimura-1973}.

Let $k$ be an odd positive integer and $N$ be a positive integer with
$4|N$. We use $M_{\frac{k}{2}}(\tilde{\Gamma}_0(N))$ to denote
the space of holomorphic modular forms on $\Gamma_0(N)$ of weight $\frac{k}{2}$.

\begin{defi}
Let
\[
f(z)=\sum_{n\geq0}a(n)q^n
\]
be a modular form in $M_\frac{k}{2}(\tilde{\Gamma}_0(N))$.
For any odd prime $\ell\nmid N$, the action of
the Hecke operator $T_{\frac{k}{2},N}(\ell^2)$  on $f(z)\in M_{\frac{k}{2}}(\tilde{\Gamma}_0(N))$ is given by
\begin{align} \label{hec-1}
f(z)\mid T_{\frac{k}{2},N}(\ell^2)=\sum_{n\ge 0}\left(a(\ell^2n)+\Big(\frac{(-1)^{\frac{k-1}{2}n}}{\ell}\Big)
\ell^{\frac{k-3}{2}}a(n)+
\ell^{k-2}a\Big(\frac{n}{\ell^2}\Big)\right)q^n,
\end{align}
where $a(\frac{n}{\ell^2})=0$ if $n$ is not divisible by $\ell^2$.
\end{defi}

The following proposition says that the Hecke operator  $T_{\frac{k}{2},N}(\ell^2)$ maps
the modular form space $M_{\frac{k}{2}}(\tilde{\Gamma}_0(N))$ into itself.

\begin{pro}
Let $\ell$ be an odd prime and $f(z)\in M_{\frac{k}{2}}(\tilde{\Gamma}_0(N))$, then
\[
f(z)\mid T_{\frac{k}{2},N}(\ell^2) \in M_{\frac{k}{2}}(\tilde{\Gamma}_0(N)).
\]
\end{pro}

A Hecke eigenform associated with the Hecke operator $T_{\frac{k}{2},N}(\ell^2)$ is defined as follows.
\begin{defi}
A half-integral weight modular form $f(z)\in M_{\frac{k}{2}}(\tilde{\Gamma}_0(4N))$ is called a Hecke eigenform for the Hecke operator $T_{\frac{k}{2},N}(\ell^2)$, if for every prime $\ell \nmid 4N$ there exists a complex number $\lambda(\ell)$ for which
\[
f(z)\mid T_{\frac{k}{2},N}(\ell^2)=\lambda(\ell) f(z).
\]
\end{defi}

For the space of half-integral weight modular forms on $\Gamma_0(4)$, we have the following dimension formula.

\begin{pro}
We have
\[
\dim M_{\frac{k}{2}}(\tilde{\Gamma}_0(4))=1+\Big\lfloor \frac{k}{4} \Big\rfloor.
\]
\end{pro}

By the above  dimension formula, we see that $\dim M_{\frac{3}{2}}(\tilde{\Gamma}_0(4))=1$. From the fact that $\phi(q)^3 \in M_{\frac{3}{2}}(\tilde{\Gamma}_0(4))$, it is easy to deduce that
\begin{align}\label{eigenform-1}
\phi(q)^3\mid T_{\frac{3}{2},4}(\ell^2)=(\ell+1)\phi(q)^3,
\end{align}
 see, for example \cite[P. 18]{Treneer-2006}.

\section{Proofs of Theorem \ref{rel-mod5} and Theorem \ref{rel-mod8}}

In this section, we give proofs of Theorem \ref{rel-mod5} and Theorem \ref{rel-mod8} by using a relation of the generating function of $\overline{p}(5n)$ modulo $5$ and the $2$-adic expansion \eqref{L-2-1} of $\overline{p}(n)$.

{\noindent \emph{Proof of Theorem \ref{rel-mod5}}}. Recall  the
following $2$-dissection formula for $\phi(q)$,
\begin{align}\label{P-L-3-2}
\phi(q)=\phi(q^4)+2q\psi(q^8),
\end{align}
where
\begin{equation*}
\psi(q)=\sum_{n=0}^{\infty}q^{\frac{n^2+n}{2}},
\end{equation*}
see, for example, Hirschhorn and Sellers \cite{1-Hirschhorn-Sellers-2005}.
Replacing $q$ by $-q$,  \eqref{P-L-3-2} becomes
\begin{align}
\phi(-q)=\phi(q^4)-2q\psi(q^8).\label{dis-q}
\end{align}
We now consider the generating function of $\overline{p}(5n)$ modulo 5.
The following relation is due to Treneer \cite[p. 18]{Treneer-2006},
\begin{equation}\label{L-1-1}
\sum_{n\geq0}\overline{p}(5 n)q^n \equiv \phi(-q)^3\pmod{5}.
\end{equation}
Plugging \eqref{dis-q} into \eqref{L-1-1} yields that
\begin{align}\label{P-L-3-3}
\sum_{n\geq0}\overline{p}(5 n)q^n
\equiv\phi(q^4)^3-q\phi(q^4)^2\psi(q^8)+2q^2\phi(q^4)\psi(q^8)^2-3q^3\psi(q^8)^3 \pmod{5}.
\end{align}
Extracting the terms of $q^{4n+i}$ for $i=0,1,2,3$  on both sides of \eqref{P-L-3-3} and   setting $q^4$ to $q$,  we obtain
\begin{align}
&\sum_{n\geq0}\overline{p}(20n)q^n\equiv\phi(q)^3 \pmod{5},\label{P-L-3-4-1}\\
&\sum_{n\geq0}\overline{p}(20n+5)q^n\equiv-\phi(q)^2\psi(q^2) \pmod{5},\label{P-L-3-4-2}\\
&\sum_{n\geq0}\overline{p}(20n+10)q^n\equiv2\phi(q)\psi(q^2)^2 \pmod{5},\label{P-L-3-4-3}\\
&\sum_{n\geq0}\overline{p}(20n+15)q^n\equiv-3\psi(q^2)^3 \pmod{5}.\label{P-L-3-4-4}
\end{align}
Substituting the $2$-dissection formula \eqref{P-L-3-2}
 into \eqref{P-L-3-4-1}, we find that
\begin{align}\label{eq-p20}
\sum_{n\geq0}\overline{p}(20 n)q^n \equiv\phi(q^4)^3+q\phi(q^4)^2\psi(q^8)+2q^2\phi(q^4)\psi(q^8)^2+3q^3\psi(q^8)^3 \pmod{5}.
\end{align}
Extracting the terms of $q^{4n+i}$ for $i=0,1,2,3$  on both sides of \eqref{eq-p20} and setting $q^4$ to $q$,  we obtain
\begin{align}
&\sum_{n\geq0}\overline{p}(4\cdot20n)\equiv\phi(q)^3 \pmod{5},\label{P-L-3-7-1}\\[5pt]
&\sum_{n\geq0}\overline{p}(4\cdot(20n+5))\equiv\phi(q)^2\psi(q^2) \pmod{5},\label{P-L-3-7-2}\\[5pt]
&\sum_{n\geq0}\overline{p}(4\cdot(20n+10))\equiv2\phi(q)\psi(q^2)^2 \pmod{5},\label{P-L-3-7-3}\\[5pt]
&\sum_{n\geq0}\overline{p}(4\cdot(20n+15))\equiv3\psi(q^2)^3 \pmod{5}.\label{P-L-3-7-4}
\end{align}
Comparing the equations \eqref{P-L-3-4-1}--\eqref{P-L-3-4-4} with \eqref{P-L-3-7-1}--\eqref{P-L-3-7-4}, we deduce that
\begin{align*}
&\overline{p}(5\cdot(4n))\equiv\overline{p}(4\cdot 5\cdot4n) \pmod{5},\\[5pt]
&\overline{p}(5\cdot(4n+1))\equiv-\overline{p}(4\cdot 5\cdot(4n+1)) \pmod{5},\\[5pt]
&\overline{p}(5\cdot(4n+2))\equiv\overline{p}(4\cdot 5\cdot(4n+2)) \pmod{5},\\[5pt]
&\overline{p}(5\cdot(4n+3))\equiv-\overline{p}(4\cdot 5\cdot(4n+3)) \pmod{5}.
\end{align*}
So we conclude that
\begin{align*}
\overline{p}(5n)\equiv(-1)^n\overline{p}(4\cdot 5n) \pmod{5}.
\end{align*}
 This completes the proof. \qed

We note that extracting the terms of odd powers of $q$ on both sides of \eqref{P-L-3-4-4} leads to the congruence
 $\overline{p}(40n+35)\equiv 0 \pmod{5}$ due to Chen and Xia \cite{Chen-Xia-2013}.

Next, we prove Theorem \ref{rel-mod8} by using the $2$-adic expansion \eqref{L-2-1}. Recall that $c_k(n)$ in \eqref{L-2-1} denotes the
number of representations of $n$ as a sum of $k$ squares of positive
integers. In particular, $c_1(n)=1$ if $n$ is a square; otherwise, $c_1(n)=0$.

{\noindent \emph{Proof of Theorem \ref{rel-mod8}}}.
 It follows from \eqref{L-2-1} that
\begin{align}\label{P-T-4-1-1}
\overline{p}(n) &\equiv(-1)^n\left(-2c_1(n)+4c_2(n)\right) \pmod{8},
\end{align}
where $n\geq 1$.
Replacing $n$ by $4n$ in \eqref{P-T-4-1-1}, we get
\begin{equation}\label{eq-p4n}
\overline{p}(4n)\equiv-2c_1(4n)+4c_2(4n) \pmod{8}.
\end{equation}
Since $c_1(n)=c_1(4n)$ and $c_2(n)=c_2(4n)$,  \eqref{eq-p4n}
can be rewritten as
\begin{align}\label{P-T-4-1-2}
\overline{p}(4n)\equiv-2c_1(n)+4c_2(n) \pmod{8}.
\end{align}
Substituting \eqref{P-T-4-1-2} into \eqref{P-T-4-1-1}, we arrive at
\begin{align*}
\overline{p}(n)\equiv (-1)^{n}\overline{p}(4n)\pmod{8},
\end{align*}
as claimed. \qed

It is easy to see that Corollary \ref{gen-HS} can be obtained by
iteratively applying Theorem  \ref{rel-mod5} and Theorem \ref{rel-mod8} to  the congruences   $\overline{p}(40n + 35) \equiv 0 \pmod{5}$  and $\overline{p}(40n + 35) \equiv 0 \pmod{8}$ that can be deduced from congruence \eqref{4n+3} by replacing $n$ with $10n+8$.

\section{Proof of Theorem \ref{thm-2}}

In this section, we  prove Theorem \ref{thm-2} by using the Hecke operator on $\phi(q)^3$  along with the fact that $\phi(q)^3$ is a Hecke eigenform in   $M_{\frac{3}{2}}(\tilde{\Gamma}_0(4))$.

 In view of Theorem \ref{rel-mod5}, to prove Theorem \ref{thm-2}, it suffices to consider the special case $k=0$ that takes the following form.

\begin{thm}
Let $\ell$ be a prime with $\ell\equiv3 \pmod{5}$. Then
\begin{align}\label{l-mod5}
\overline{p}(5\ell^2n)\equiv 0  \pmod{5}
\end{align}
holds for any nonnegative integer $n$ with $\left(\frac{-n}{\ell}\right)=-1$.
\end{thm}
\pf Recall that $\phi(-q)^3$ is a modular form in $ M_{\frac{3}{2}}(\tilde{\Gamma}_0(16))$. Suppose that
\begin{align}\label{eq-exphi}
\phi(-q)^3=\sum_{n\geq0}a(n)q^n
\end{align}
is the Fourier expansion of $\phi(-q)^3$.

Applying the Hecke operator $T_{\frac{3}{2},16}(\ell^2)$ to $\phi(-q)^3$
and using  \eqref{hec-1}, we find that
\begin{equation}\label{heck-1}
\phi(-q)^3\mid T_{\frac{3}{2},16}(\ell^2)=\sum_{n=0}^\infty \left(a(\ell^2n)+\Big(\frac{-n}{\ell}\Big)a(n)+\ell a\Big(\frac{n}{\ell^2}\Big)\right) q^n,
\end{equation}
where $\ell$ is an odd prime.
Replacing $q$ by $-q$ in \eqref{eigenform-1},
we see that $\phi(-q)^3$ is a Hecke eigenform in the space $M_{\frac{3}{2}}(\tilde{\Gamma}_0(16))$,  and hence
\begin{align}\label{L-1-2}
\phi(-q)^3\mid T_{\frac{3}{2},16}(\ell^2)=(\ell+1)\phi(-q)^3.
\end{align}
Comparing the coefficients of $q^n$ in \eqref{heck-1} and \eqref{L-1-2}, we deduce that
\begin{align}\label{P-T-5-2}
a(\ell^2n)+\Big(\frac{-n}{\ell}\Big)a(n)+\ell a\Big(\frac{n}{\ell^2}\Big)=(\ell+1)a(n).
\end{align}
Revoking  the  congruence \eqref{L-1-1}, that is,
\begin{equation}\label{eq-phiq3}
\phi(-q)^3\equiv\sum_{n\geq0}\overline{p}(5 n)q^n \pmod{5},
\end{equation}
and comparing \eqref{eq-exphi} with \eqref{eq-phiq3}, we get
\begin{align}\label{P-T-5-3}
a(n)\equiv\overline{p}(5n) \pmod{5}.
\end{align}
Plugging \eqref{P-T-5-3} into \eqref{P-T-5-2}, we deduce that
\begin{align}\label{overpc}
\overline{p}(5\ell^2n)+\left(\frac{-n}{\ell}\right)\overline{p}(5n)+\ell
\overline{p}\left(\frac{5n}{\ell^2}\right)\equiv(\ell+1)\overline{p}(5n) \pmod{5}.
\end{align}
Since $\ell\equiv3 \pmod{5}$ and $(\frac{-n}{\ell})=-1$, we see that $\ell \nmid 5$ and $\ell \nmid n$, so that $\ell^2 \nmid 5n$ and $\overline{p}\left(\frac{5n}{\ell^2}\right)=0$.
Moreover, we have $\left(\frac{-n}{\ell}\right)\equiv(\ell+1)\equiv -1 \pmod{5}$.
Hence congruence \eqref{overpc} becomes
\begin{align*}
\overline{p}(5\ell^2n)\equiv 0 \pmod{5}.
\end{align*}
This completes the proof. \qed

 We now give some special cases of Theorem \ref{thm-2}. Setting $\ell=3$ and $k=0,1$ in Theorem \ref{thm-2}, respectively, we obtain the following
 congruences for $n\geq0$,
\begin{align*}
&\overline{p}\big(45(3n+1)\big)\equiv 0  \pmod{5},\\[5pt]
&\overline{p}\big(180(3n+1)\big)\equiv 0  \pmod{5}.
\end{align*}
Setting $\ell=13$, $k=0$ in Theorem \ref{thm-2}, we obtain the following congruences for $n\geq0$,
\begin{align*}
&\overline{p}\big(845 (13n+2)\big)\equiv0 \pmod{5},\\[5pt]
&\overline{p}\big(845 (13n+5)\big)\equiv0 \pmod{5},\\[5pt]
&\overline{p}\big(845 (13n+6)\big)\equiv0 \pmod{5},\\[5pt]
&\overline{p}\big(845 (13n+7)\big)\equiv0 \pmod{5},\\[5pt]
&\overline{p}\big(845 (13n+8)\big)\equiv0 \pmod{5},\\[5pt]
&\overline{p}\big(845 (13n+11)\big)\equiv0 \pmod{5}.
\end{align*}

\section{Proof of Theorem \ref{relation-mod5}}

In this section, we complete the proof of Theorem \ref{relation-mod5} by using  the Hecke operator $T_{\frac{3}{2},16}(\ell^2)$ and the Hecke eigenform $\phi(-q)^3$.

{\noindent \emph{Proof of Theorem \ref{relation-mod5}.}}
Setting $\ell=5$ in the congruence relation \eqref{overpc}, we find that
\begin{align}\label{P-T-5-4}
\overline{p}(5n)\equiv \overline{p}(5^3n)+\left(\frac{n}{5}\right)\overline{p}(5n) \pmod{5}.
\end{align}
By the definition of the Legendre symbol, we see that if $n\equiv0 \pmod{5}$, then $\left(\frac{n}{5}\right)=0$.
Hence, by replacing $n$ with $5n$ in   congruence \eqref{P-T-5-4}, we obtain that
\begin{align}
\overline{p}(5^2 n)\equiv\overline{p}(5^4 n) \pmod{5}, \label{P-T-5-6-1}
\end{align}
as claimed. \qed

Furthermore, we note that if $n\equiv\pm1 \pmod{5}$, then
$\left(\frac{n}{5}\right)=1$. Hence by setting $n$ to $5n\pm1$ in \eqref{P-T-5-4}, we deduce that
\begin{align}\label{P-T-5-6-2}
\overline{p}(5^3(5n\pm1))\equiv 0 \pmod{5}.
\end{align}
By iteratively applying the congruence $\overline{p}(5n)\equiv (-1)^{n}\overline{p}(4\cdot 5n) \pmod{5}$ given in Theorem \ref{rel-mod5} and congruence \eqref{P-T-5-6-1} to   \eqref{P-T-5-6-2}, we obtain that
\begin{equation}\label{eq-p45}
\overline{p}(4^k 5^{2i+3}(5n\pm1))\equiv 0 \pmod{5},
\end{equation}
where $n, k,i \ge 0$. This proves
Corollary \ref{coro-2}.

For $n\geq0$, setting $i=0$ and $k=0,1$ in \eqref{eq-p45},  we obtain the following
 special cases
\begin{align*}
&\overline{p}\big(125(5n\pm 1)\big) \equiv 0 \pmod{5},\\[5pt]
&\overline{p}\big(500(5n\pm 1)\big) \equiv0 \pmod{5}.
\end{align*}

By replacing $n$ by $5n\pm2$ in \eqref{P-T-5-4} and iteratively using the congruence relation \eqref{P-T-5-6-1}, we obtain the following   relation.

\begin{coro}
For $n,i\geq0$, we have
\begin{align*}
\overline{p}\big(5(5n\pm2)\big)\equiv 3\,\overline{p}\big(5^{2i+3}(5n\pm2)\big) \pmod{5}.
\end{align*}
\end{coro}

\vspace{.3cm}

{\noindent \bf Acknowledgments.} This work was supported by the 973 Project, the PCSIRT Project
of the Ministry of Education and the National Science Foundation of China.

config: arxiv


text:
\begin{document}

\title{$M$-Polynomial Revisited: Bethe Cacti and an Extension of Gutman's Approach}

\author{Emeric Deutsch$^{a}$\thanks{Email: \texttt{EmericDeutsch@msn.com}}
\and Sandi Klav\v zar$^{b,c,d}$\thanks{Email: \texttt{sandi.klavzar@fmf.uni-lj.si}}
}

\maketitle

\begin{center}
$^a$ Polytechnic Institute of New York University, United States\\
\medskip

$^d$ Faculty of Mathematics and Physics, University of Ljubljana, Slovenia
\medskip

$^b$ Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia\\
\medskip

$^c$ Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
\end{center}

\begin{abstract}
The $M$-polynomial of a graph $G$ is defined as $\sum_{i\le j} m_{i,j}(G)x^iy^j$, where $m_{i,j}(G)$, $i,j\ge 1$, is the number of edges $uv$ of $G$ such that $\{d_v(G), d_u(G)\} = \{i,j\}$. Knowing the $M$-polynomial, formulas for bond incident degree indices (an important subclass of degree-based topological indices) can be obtained by means of specific operators defined on differentiable functions in two variables. This is illustrated on three infinite families of Bethe cacti. Gutman's approach for the computation of the coefficients of the $M$-polynomial is also recalled and an extension of it is given. This extension is used to determine the $M$-polynomial of a two-parameter infinite family of lattice graphs.
\end{abstract}

\noindent
{\bf Keywords:} M-polynomial; Bethe cacti; degree-based topological index; bond incident degree index; graph polynomial.  \\

\noindent
{\bf AMS Subj.\ Class.\ (2010)}: 05C07, 05C31, 92E10.

\baselineskip16pt

\section{Introduction}
\label{sec:intro}

A large part of chemical graph theory investigates topological indices (in other words, graph invariants) which are aimed to be chemically relevant. Among these topological indices, degree-based ones, such as different variants of the Randi\'c index and the Zagreb index, play a central role. For a general and uniform discussion on the degree-based topological indices see the survey~\cite{gutman-2013a}. For selected recent investigations of  (variants of) the Randi\'c index see~\cite{chen-2017, das-2017, ma-2018, milivojevic-2017} and for (variants of) the Zagreb index we refer to~\cite{an-2018, vukicevic-2017, wang-2018}. We also refer to~\cite{gutman-2013b}, where these indices are correlated with physico-chemical parameters of octane isomers. For a selection of recent papers that compute degree-based topological indices see~\cite{ali-2018, kang-2018, kwun-2017, liu-2017, munir-2016a, munir-2016b, munir-2017, rezaei-2017}; we especially emphasize the approach to degree-based topological indices of hexagonal nanotubes in~\cite{vetrik-2017+}.

In order to simplify the computation of the bond incident degree indices, which form an utmost important subclass of degree-based topological indices  (to be defined in Section~\ref{sec:prelim}), and to stop the production of papers that, for a given family of graphs computes a given topological index from skratch, the $M$-polynomial was introduced in~\cite{deutsch-2015}. (For a related approach using the degree sequence polynomial for generalized Zagreb indices, see~\cite{doslic-2017}.) In~\cite{deutsch-2015} it was proved that the computation of several degree-based topological indices becomes a routine task, provided that the corresponding $M$-polynomial is known. More precisely, the problem more or less reduces to the one of determining the number $m_{i,j}$ of the edges of a graph whose endpoints are of degrees $i$ and $j$. Hence a particular purpose of this  paper is to point out to future authors that
\begin{itemize}
\item[(i)] the expressions for the $m_{i,j}$s should be derived (or explained) and that
\item[(ii)] not much space should be taken up by the computation of the topological indices; they follow easily either by elementary algebra from the $m_{i,j}$s or by elementary calculus from the $M$-polynomial.
\end{itemize}
Numerous very recent papers that compute degree-based topological indices do not satisfy these natural requirements. Therefore, in this paper we further explain the approach and demonstrate its power on three families of Bethe cacti from~\cite{bala-1990}. These families have been selected in particular because the determination of the $M$-polynomial (equivalently of the corresponding $m_{i,j}$s) is not that straightforward as it is in several earlier cases.

The rest of the paper is organized as follows. In the next section we formally introduce the $M$-polynomial and recall how it can be applied to bond incident degree topological indices. In Section~\ref{sec:Bethe} we introduce three families of Bethe cacti, give their recursive definitions, and based on them determine the $M$-polynomial in all of the cases. In Section~\ref{sec:Bethe-indices} we combine the results from the previous two sections to give closed formulas for several degree-based topological indices of the considered Bethe cacti. In the concluding section we recall Gutman's approach for the computation of the coefficients of the $M$-polynomial.  We extend this approach by adjoining Euler's formula to the original six equalities. We use this extended approach to determine the $M$-polynomial of a two-parameter infinite family of lattice graphs, consisting of $5$-, $6$-, and $8$-gonal faces.

We do not give basic definitions of graph theory here; the reader can consult the book~\cite{west-2001}.

\section{Preliminaries}
\label{sec:prelim}

Let $G = (V(G), E(G))$ be a graph and let $m_{i,j}(G)$, $i,j\ge 1$, be the number of edges $uv$ of $G$ such that $\{d_v(G), d_u(G)\} = \{i,j\}$, where $d_v(G)$ (or $d_v$ for short) is the degree of the vertex $v$ in $G$. (It seems that the variables $m_{i,j}$ were introduced for the first time in~\cite{gutman-2002}.) For instance, if $G$ is $k$-regular, then $m_{k,k} = |E(G)|$, while $m_{i,j}(G) = 0$ as soon as $i\ne k$ or $j\ne k$. The {\em $M$-polynomial} of $G$ is the two variable polynomial defined as
$$\sum_{i\le j} m_{i,j}(G)x^iy^j\,.$$
The role of this polynomial for degree-based indices is similar to the role of the Hosoya polynomial~\cite{hosoya-1988} (see also~\cite{deutsch-2013, eliasi-2013, lin-2013, tratnik-2017}) for distance-based invariants.

A {\em degree-based topological index} $I$ of a graph $G$ is an arbitrary graph invariant that is defined as a function of the degrees of the vertices of $G$. In many important cases, $I$ is of the form
\begin{equation}
\label{eq:degree-index}
I(G) = \sum_{e=uv\in E}f(d_u, d_v)\,,
\end{equation}
where $f=f(x,y)$ is a function to be suitable for chemical applications~\cite{gutman-2013a, hollas-2005}. The degree-based topological indices $I$ that are of the form~\eqref{eq:degree-index} were named {\em bond incident degree indices} in~\cite{vukicevic-2011}; we follow this terminology here. We will also abbreviate bond incident degree index to {\em BID index}. For instance, the generalized Randi\'c index $R_\alpha(G)$, $\alpha\ne 0$, is a BID index because it is obtained by selecting $f(x,y) = (xy)^\alpha$~\cite{bollobas-1998}; see Table~\ref{table1} for additional important BID indices. As examples of degree-based topological indices that are not BID indices consider the higher order Randi\'c indices. In this case the summation is taken over all paths in a graph of a given length instead over all edges as it is done in~\eqref{eq:degree-index}.

From our point of view it is utmost important to note that~\eqref{eq:degree-index} can be rewritten as
\begin{equation}
\label{eq:degree-index-2}
I(G) = \sum_{i\le j}m_{i,j}(G) f(i, j)\,.
\end{equation}

Consider the following operators defined on differentiable functions in two variables:
$$
\begin{array}{cccccc}
D_x(f(x,y)) & = & x \frac{\partial f(x,y)}{\partial x}, \qquad D_y(f(x,y)) & = & y \frac{\partial f(x,y)}{\partial y}, \\ \\
S_x(f(x,y)) & = & \int_{0}^x \frac{f(t,y)}{t} dt, \qquad S_y(f(x,y)) & = & \int_{0}^y \frac{f(x,t)}{t} dt, \\ \\
J(f(x,y)) & = & f(x,x), \qquad Q_\alpha(f(x,y)) & = & x^\alpha f(x,y), \alpha\ne 0.
\end{array}
$$
Now we can recall the following key result from~\cite{deutsch-2015}.

\begin{theorem} {\rm \cite[Theorems 2.1,2.2]{deutsch-2015}}
\label{thm:main}
Let $G$ be a graph.
\begin{enumerate}
\item[(i)] If $\displaystyle{I(G) = \sum_{e=uv\in E}f(d_u, d_v)}$, where $f(x,y)$ is a polynomial in $x$ and $y$, then
$$I(G) = f(D_x,D_y)(M(G;x,y))\big|_{x=y=1}\,.$$
\item[(ii)] If $\displaystyle{I(G) = \sum_{e=uv\in E}f(d_u, d_v)}$, where $f(x,y) = \sum_{i,j\in \mathbb{Z}}\alpha_{ij}x^iy^j$, then $I(G)$ can be obtained from $M(G;x,y)$ using the operators $D_x$, $D_y$, $S_x$, and $S_y$.
\item[(iii)] If $\displaystyle{I(G) = \sum_{e=uv\in E}f(d_u, d_v)}$, where $f(x,y) = \frac{ x^r y^s}{(x+y+\alpha)^k}$, where $r,s\ge 0$, $,t\ge 1$, and $\alpha\in {\mathbb{Z}}$, then
$$I(G) = S_x^k\,Q_\alpha\,J\,D_x^r\,D_y^s (M(G;x,y))\big|_{x=1}\,.$$
\end{enumerate}
\end{theorem}

Table~\ref{table1} contains applications of Theorem~\ref{thm:main} for some of the main BID indices.

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|}\hline
$\phantom{\Big|}$BID index$\phantom{\Big|}$ & $f(x,y)$ & derivation from $M(G;x,y)$ \\
\hline\hline
$\phantom{\Big|}$first Zagreb$\phantom{\Big|}$ &
$x+y$ & $(D_x + D_y)(M(G;x,y))\big|_{x=y=1}$ \\
\hline
$\phantom{\Big|}$second Zagreb$\phantom{\Big|}$ &
$xy$ & $(D_xD_y)(M(G;x,y))\big|_{x=y=1}$ \\
\hline
$\phantom{\Big|}$second modified Zagreb$\phantom{\Big|}$ &
$\frac{1}{xy}$ & $(S_xS_y)(M(G;x,y))\big|_{x=y=1}$ \\
\hline
$\phantom{\Big|}$general Randi\'c ($\alpha\in {\mathbb{N}}$)$\phantom{\Big|}$ &
$(xy)^\alpha$ & $(D_x^\alpha D_y^\alpha)(M(G;x,y))\big|_{x=y=1}$ \\
\hline
$\phantom{\Big|}$general Randi\'c ($\alpha\in {\mathbb{N}}$)$\phantom{\Big|}$ &
$\frac{1}{(xy)^\alpha}$ & $(S_x^\alpha S_y^\alpha)(M(G;x,y))\big|_{x=y=1}$ \\
\hline
$\phantom{\Big|}$symmetric division index$\phantom{\Big|}$ &
$\frac{x^2 + y^2}{xy}$ & $(D_xS_y + D_yS_x)(M(G;x,y))\big|_{x=y=1}$ \\
\hline
$\phantom{\Big|}$harmonic$\phantom{\Big|}$ &
$\frac{2}{x+y}$ & $2\,S_x\,J\,(M(G;x,y))\big|_{x=1}$ \\
\hline
$\phantom{\Big|}$inverse sum$\phantom{\Big|}$ &
$\frac{xy}{x+y}$ & $S_x\,J\,D_x\,D_y\,(M(G;x,y))\big|_{x=1}$ \\
\hline
$\phantom{\Big|}$augmented Zagreb$\phantom{\Big|^{X^X}}$ & $\left(\frac{xy}{x+y-2}\right)^3$ $\phantom{\Big|}$ & $S_x^3\,Q_{-2}\,J\,D_x^3\,D_y^3\,(M(G;x,y))\big|_{x=1}$ \\
\hline
\end{tabular}
\end{center}
\caption{How to compute important BID indices from the $M$-polynomial}
\label{table1}
\end{table}

\section{Families of Bethe cacti}
\label{sec:Bethe}

Balasubramanian~\cite{bala-1990} considered families $C_n$, $D_n$, and $E_n$ ($n\ge 1$) of cactus graphs. Since the recursive structure of the families $C_n$ and $E_n$ can be described using the family $D_n$, we first consider the family $D_n$.

\subsection{Bethe cacti $D_n$}

The recursive definition of the family of the Bethe cacti $D_n$, $n\ge 1$, is shown in Fig.~\ref{fig:D_n-recursive}. Here the black vertex of $D_n$ denotes the attaching vertex, where $D_n$ is attached to $D_{n+1}$ (three times). The smallest Bethe cactus $D_1$ is shown in the recursive description (Fig.~\ref{fig:D_n-recursive}), while the next two Bethe cacti $D_2$ and $D_3$ are drawn in Fig.~\ref{fig:D_2-and-D_3}. The general construction should then be clear.

\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.6,style=thick,x=1cm,y=1cm]
\def\vr{3pt}

\coordinate(a1) at (0,0);
\coordinate(b1) at (1,1);
\coordinate(c1) at (0,2);
\coordinate(d1) at (-1,1);

\coordinate(a2) at (7,0);
\coordinate(b2) at (8,1);
\coordinate(c2) at (7,2);
\coordinate(d2) at (6,1);

\draw (a1) -- (b1) -- (c1) -- (d1) -- (a1);
\draw (a2) -- (b2) -- (c2) -- (d2) -- (a2);

\draw (4.6,1) ellipse (1.4cm and 1cm);
\draw (7,3.4) ellipse (1cm and 1.4cm);
\draw (9.4,1) ellipse (1.4cm and 1cm);

\foreach \i in {1,2}
{
\draw(a\i)[fill=white] circle(\vr);
\draw(b\i)[fill=white] circle(\vr);
\draw(c\i)[fill=white] circle(\vr);
\draw(d\i)[fill=white] circle(\vr);
}
\draw(a1)[fill=black] circle(\vr);
\draw(a2)[fill=black] circle(\vr);

\draw (7,-1) node {$D_n, n\ge 2$};
\draw (0,-1) node {$D_1$};
\draw (4.5,1) node {$D_{n-1}$};
\draw (9.5,1) node {$D_{n-1}$};
\draw (7,3.5) node {$D_{n-1}$};

\end{tikzpicture}
\end{center}
\caption{Recursive definition of the Bethe cacti $D_n$}
\label{fig:D_n-recursive}
\end{figure}

\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.9,style=thick,x=1cm,y=1cm]
\def\vr{3pt}

\coordinate(x1) at (1,1.5);
\coordinate(x2) at (1.5,1);
\coordinate(x3) at (2,1.5);
\coordinate(x4) at (1.5,2);
\coordinate(x5) at (2,2.5);
\coordinate(x6) at (2.5,2);
\coordinate(x7) at (3,2.5);
\coordinate(x8) at (2.5,3);
\coordinate(x9) at (3,1.5);
\coordinate(x10) at (3.5,1);
\coordinate(x11) at (4,1.5);
\coordinate(x12) at (3.5,2);
\coordinate(x13) at (2.5,1);

\coordinate(a1) at (5,1.5);
\coordinate(a2) at (5.5,1);
\coordinate(a3) at (6,1.5);
\coordinate(a4) at (5.5,2);
\coordinate(a5) at (6.5,0.5);
\coordinate(a6) at (7,0);
\coordinate(a7) at (7.5,0.5);
\coordinate(a8) at (7,1);
\coordinate(a9) at (6.5,2.5);
\coordinate(a10) at (7,2);
\coordinate(a11) at (7.5,2.5);
\coordinate(a12) at (7,3);
\coordinate(a13) at (7.5,3.5);
\coordinate(a14) at (8,3);
\coordinate(a15) at (8.5,3.5);
\coordinate(a16) at (8,4);
\coordinate(a17) at (8.5,5);
\coordinate(a18) at (9,4.5);
\coordinate(a19) at (9.5,5);
\coordinate(a20) at (9,5.5);
\coordinate(a21) at (9.5,3.5);
\coordinate(a22) at (10,3);
\coordinate(a23) at (10.5,3.5);
\coordinate(a24) at (10,4);
\coordinate(a25) at (10.5,2.5);
\coordinate(a26) at (11,2);
\coordinate(a27) at (11.5,2.5);
\coordinate(a28) at (11,3);
\coordinate(a29) at (10.5,0.5);
\coordinate(a30) at (11,0);
\coordinate(a31) at (11.5,0.5);
\coordinate(a32) at (11,1);
\coordinate(a33) at (12,1.5);
\coordinate(a34) at (12.5,1);
\coordinate(a35) at (13,1.5);
\coordinate(a36) at (12.5,2);
\coordinate(x) at (8,1.5);
\coordinate(y) at (9,0.5);
\coordinate(z) at (10,1.5);
\coordinate(w) at (9,2.5);

\draw (x1) -- (x2) -- (x3) -- (x4) -- (x1);
\draw (x5) -- (x6) -- (x7) -- (x8) -- (x5);
\draw (x9) -- (x10) -- (x11) -- (x12) -- (x9);
\draw (x3) -- (x6) -- (x9) -- (x13) -- (x3);

\draw (a1) -- (a2) -- (a3) -- (a4) -- (a1);
\draw (a5) -- (a6) -- (a7) -- (a8) -- (a5);
\draw (a9) -- (a10) -- (a11) -- (a12) -- (a9);
\draw (a13) -- (a14) -- (a15) -- (a16) -- (a13);
\draw (a17) -- (a18) -- (a19) -- (a20) -- (a17);
\draw (a21) -- (a22) -- (a23) -- (a24) -- (a21);
\draw (a25) -- (a26) -- (a27) -- (a28) -- (a25);
\draw (a29) -- (a30) -- (a31) -- (a32) -- (a29);
\draw (a33) -- (a34) -- (a35) -- (a36) -- (a33);

\draw (x) -- (a8) -- (a3) -- (a10) -- (x);
\draw (w) -- (a15) -- (a18) -- (a21) -- (w);
\draw (z) -- (a26) -- (a33) -- (a32) -- (z);
\draw (x) -- (y) -- (z) -- (w) -- (x);

\foreach \i in {1,2,...,13}
{
\draw(x\i)[fill=white] circle(\vr);
}
\draw(x13)[fill=black] circle(\vr);
\foreach \i in {1,2,...,36}
{
\draw(a\i)[fill=white] circle(\vr);
}
\draw(x)[fill=white] circle(\vr);
\draw(y)[fill=black] circle(\vr);
\draw(z)[fill=white] circle(\vr);
\draw(w)[fill=white] circle(\vr);
\end{tikzpicture}
\end{center}
\caption{The Bethe cacti $D_2$ and $D_3$}
\label{fig:D_2-and-D_3}
\end{figure}

\begin{theorem}
\label{thm:M-poly-of-Dn}
$M(D_1; x,y) = 4x^2y^2$ and if $n\ge 2$, then
$$M(D_n; x,y) = 2\cdot 3^{n-1}x^2y^2 + 2(3^{n-1}+1)x^2y^4 + 2(3^{n-1} - 2)x^4y^4\,.$$
\end{theorem}

\proof
Clearly, $M(D_1; x,y) = 4x^2y^2$. Assume in the rest that $n\ge 2$ and for the initial condition in the following three recurrences consider $D_2$ from Fig.~\ref{fig:D_2-and-D_3}. We first infer that
$$m_{2,2}(D_{2}) = 6,\quad m_{2,2}(D_{n}) = 3 m_{2,2}(D_{n-1}), n\ge3\,,$$
which solves as $m_{2,2}(D_{n}) = 2\cdot 3^{n-1}$.

Note further that two $24$-edges of $D_{n-1}$ become $44$-edges in $D_n$. Consequently,
$$m_{2,4}(D_{2}) = 8,\quad m_{2,4}(D_{n}) = 3 m_{2,4}(D_{n-1}) - 6 +2, n\ge3\,,$$
which solves into $m_{2,4}(D_{n}) = 2\cdot 3^{n-1} + 2$ and
$$m_{4,4}(D_{2}) = 2,\quad m_{4,4}(D_{n}) = 3 m_{4,4}(D_{n-1}) + 6 +2, n\ge3\,,$$
which in turn solves into $m_{4,4}(D_{n}) = 2\cdot 3^{n-1} - 4$. Putting together the three solutions of the recurrences, the result follows.
\qed

\subsection{Bethe cacti $C_n$}

The recursive definition of the family of the Bethe cacti $C_n$, $n\ge 1$, is shown in Fig.~\ref{fig:C_n-recursive}. The vertex at which each of the four copies of $D_{n-1}$ is attached to the central $4$-cycle, respectively, is the black vertex of $D_{n-1}$ as shown in Fig.~\ref{fig:D_2-and-D_3}. The smallest Bethe cactus $C_1$ is thus the $4$-cycle graph, while the Bethe cacti $C_2$ and $C_3$ are drawn in Fig.~\ref{fig:C_2-and-C_3}. The general construction should then be clear.

\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.6,style=thick,x=1cm,y=1cm]
\def\vr{3pt}

\coordinate(a1) at (0,0);
\coordinate(b1) at (1,1);
\coordinate(c1) at (0,2);
\coordinate(d1) at (-1,1);

\coordinate(a2) at (7,0);
\coordinate(b2) at (8,1);
\coordinate(c2) at (7,2);
\coordinate(d2) at (6,1);

\draw (a1) -- (b1) -- (c1) -- (d1) -- (a1);
\draw (a2) -- (b2) -- (c2) -- (d2) -- (a2);

\draw (4.6,1) ellipse (1.4cm and 1cm);
\draw (7,3.4) ellipse (1cm and 1.4cm);
\draw (9.4,1) ellipse (1.4cm and 1cm);
\draw (7,-1.4) ellipse (1cm and 1.4cm);

\foreach \i in {1,2}
{
\draw(a\i)[fill=white] circle(\vr);
\draw(b\i)[fill=white] circle(\vr);
\draw(c\i)[fill=white] circle(\vr);
\draw(d\i)[fill=white] circle(\vr);
}

\draw (11,-1) node {$C_n, n\ge 2$};
\draw (0,-1) node {$C_1$};
\draw (4.5,1) node {$D_{n-1}$};
\draw (9.5,1) node {$D_{n-1}$};
\draw (7,3.5) node {$D_{n-1}$};
\draw (7,-1.5) node {$D_{n-1}$};

\end{tikzpicture}
\end{center}
\caption{Recursive definition of the Bethe cacti $C_n$}
\label{fig:C_n-recursive}
\end{figure}

\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.9,style=thick,x=1cm,y=1cm]
\def\vr{3pt}

\coordinate(x1) at (1,1.5);
\coordinate(x2) at (1.5,1);
\coordinate(x3) at (2,1.5);
\coordinate(x4) at (1.5,2);
\coordinate(x5) at (2,2.5);
\coordinate(x6) at (2.5,2);
\coordinate(x7) at (3,2.5);
\coordinate(x8) at (2.5,3);
\coordinate(x9) at (3,1.5);
\coordinate(x10) at (3.5,1);
\coordinate(x11) at (4,1.5);
\coordinate(x12) at (3.5,2);
\coordinate(x13) at (2.5,1);
\coordinate(x14) at (3,0.5);
\coordinate(x15) at (2.5,0);
\coordinate(x16) at (2,0.5);

\coordinate(a1) at (5,1.5);
\coordinate(a2) at (5.5,1);
\coordinate(a3) at (6,1.5);
\coordinate(a4) at (5.5,2);
\coordinate(a5) at (6.5,0.5);
\coordinate(a6) at (7,0);
\coordinate(a7) at (7.5,0.5);
\coordinate(a8) at (7,1);
\coordinate(a9) at (6.5,2.5);
\coordinate(a10) at (7,2);
\coordinate(a11) at (7.5,2.5);
\coordinate(a12) at (7,3);
\coordinate(a13) at (7.5,3.5);
\coordinate(a14) at (8,3);
\coordinate(a15) at (8.5,3.5);
\coordinate(a16) at (8,4);
\coordinate(a17) at (8.5,5);
\coordinate(a18) at (9,4.5);
\coordinate(a19) at (9.5,5);
\coordinate(a20) at (9,5.5);
\coordinate(a21) at (9.5,3.5);
\coordinate(a22) at (10,3);
\coordinate(a23) at (10.5,3.5);
\coordinate(a24) at (10,4);
\coordinate(a25) at (10.5,2.5);
\coordinate(a26) at (11,2);
\coordinate(a27) at (11.5,2.5);
\coordinate(a28) at (11,3);
\coordinate(a29) at (10.5,0.5);
\coordinate(a30) at (11,0);
\coordinate(a31) at (11.5,0.5);
\coordinate(a32) at (11,1);
\coordinate(a33) at (12,1.5);
\coordinate(a34) at (12.5,1);
\coordinate(a35) at (13,1.5);
\coordinate(a36) at (12.5,2);
\coordinate(a37) at (7.5,-0.5);
\coordinate(a38) at (8,0);
\coordinate(a39) at (8.5,-0.5);
\coordinate(a40) at (8,-1);
\coordinate(a41) at (9.5,-0.5);
\coordinate(a42) at (10,0);
\coordinate(a43) at (10.5,-0.5);
\coordinate(a44) at (10,-1);
\coordinate(a45) at (8.5,-2);
\coordinate(a46) at (9,-1.5);
\coordinate(a47) at (9.5,-2);
\coordinate(a48) at (9,-2.5);
\coordinate(x) at (8,1.5);
\coordinate(y) at (9,0.5);
\coordinate(z) at (10,1.5);
\coordinate(w) at (9,2.5);

\draw (x1) -- (x2) -- (x3) -- (x4) -- (x1);
\draw (x5) -- (x6) -- (x7) -- (x8) -- (x5);
\draw (x9) -- (x10) -- (x11) -- (x12) -- (x9);
\draw (x3) -- (x6) -- (x9) -- (x13) -- (x3);
\draw (x13) -- (x14) -- (x15) -- (x16) -- (x13);

\draw (a1) -- (a2) -- (a3) -- (a4) -- (a1);
\draw (a5) -- (a6) -- (a7) -- (a8) -- (a5);
\draw (a9) -- (a10) -- (a11) -- (a12) -- (a9);
\draw (a13) -- (a14) -- (a15) -- (a16) -- (a13);
\draw (a17) -- (a18) -- (a19) -- (a20) -- (a17);
\draw (a21) -- (a22) -- (a23) -- (a24) -- (a21);
\draw (a25) -- (a26) -- (a27) -- (a28) -- (a25);
\draw (a29) -- (a30) -- (a31) -- (a32) -- (a29);
\draw (a33) -- (a34) -- (a35) -- (a36) -- (a33);
\draw (a37) -- (a38) -- (a39) -- (a40) -- (a37);
\draw (a41) -- (a42) -- (a43) -- (a44) -- (a41);
\draw (a45) -- (a46) -- (a47) -- (a48) -- (a45);
\draw (y) -- (a41) -- (a46) -- (a39) -- (y);

\draw (x) -- (a8) -- (a3) -- (a10) -- (x);
\draw (w) -- (a15) -- (a18) -- (a21) -- (w);
\draw (z) -- (a26) -- (a33) -- (a32) -- (z);
\draw (x) -- (y) -- (z) -- (w) -- (x);

\foreach \i in {1,2,...,16}
{
\draw(x\i)[fill=white] circle(\vr);
}
\draw(x13)[fill=white] circle(\vr);
\foreach \i in {1,2,...,48}
{
\draw(a\i)[fill=white] circle(\vr);
}
\draw(x)[fill=white] circle(\vr);
\draw(y)[fill=white] circle(\vr);
\draw(z)[fill=white] circle(\vr);
\draw(w)[fill=white] circle(\vr);
\end{tikzpicture}
\end{center}
\caption{The Bethe cacti $C_2$ and $C_3$}
\label{fig:C_2-and-C_3}
\end{figure}

\begin{theorem}
\label{thm:M-poly-of-Cn}
$M(C_1; x,y) = 4x^2y^2$ and if $n\ge 2$, then
$$M(C_n; x,y) = 8\cdot 3^{n-2}x^2y^2 + 8\cdot 3^{n-2}x^2y^4 + 4(2\cdot 3^{n-2} - 1)x^4y^4\,.$$
\end{theorem}

\proof
Clearly, $M(C_1; x,y) = 4x^2y^2$. Assume in the rest that $n\ge 2$. Recalling from the proof of Theorem~\ref{thm:M-poly-of-Dn} that $m_{2,2}(D_{n}) = 2\cdot 3^{n-1}$, we have
$$m_{2,2}(C_{n}) = 4 m_{2,2}(D_{n-1}) = 4\cdot 2\cdot 3^{n-2} = 8\cdot 3^{n-2}\,.$$
Recalling further that $m_{2,4}(D_{n}) = 2\cdot 3^{n-1} + 2$ and $m_{4,4}(D_{n}) = 2\cdot 3^{n-1} - 4$, and observing that two $24$-edges of $D_{n-1}$ become $44$-edges in $C_n$, we get
$$m_{2,4}(C_{n}) = 4 m_{2,4}(D_{n-1}) - 8 = 4(2\cdot 3^{n-2} + 2) - 8 = 8\cdot 3^{n-2}$$
and
$$m_{4,4}(C_{n}) = 4 m_{4,4}(D_{n-1}) + 8 + 4 = 4(2\cdot 3^{n-2} -4) + 12 = 8\cdot 3^{n-2}-4\,.$$
Hence the result.
\qed

\subsection{Bethe cacti $E_n$}

The recursive definition of the family of the Bethe cacti $E_n$, $n\ge 1$, is shown in Fig.~\ref{fig:E_n-recursive}. Again, the vertex at which each of the three copies of $D_{n-1}$ is attached to the central path on three vertices, respectively, is the black vertex of $D_{n-1}$ as shown in Fig.~\ref{fig:D_2-and-D_3}. Thus the smallest Bethe cactus $E_1$ is the path on three vertices, the next two Bethe cacti $E_2$ and $E_3$ are drawn in Fig.~\ref{fig:E_2-and-E_3}. The general construction should then be clear.

\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.6,style=thick,x=1cm,y=1cm]
\def\vr{3pt}

\coordinate(a1) at (-1,1);
\coordinate(b1) at (1,1);
\coordinate(c1) at (0,2);

\coordinate(a2) at (6,1);
\coordinate(b2) at (8,1);
\coordinate(c2) at (7,2);

\draw (a1) -- (c1) -- (b1);
\draw (a2) -- (c2) -- (b2);

\draw (4.6,1) ellipse (1.4cm and 1cm);
\draw (7,3.4) ellipse (1cm and 1.4cm);
\draw (9.4,1) ellipse (1.4cm and 1cm);

\foreach \i in {1,2}
{
\draw(a\i)[fill=white] circle(\vr);
\draw(b\i)[fill=white] circle(\vr);
\draw(c\i)[fill=white] circle(\vr);
}

\draw (7,-1) node {$E_n, n\ge 2$};
\draw (0,-1) node {$E_1$};
\draw (4.5,1) node {$D_{n-1}$};
\draw (9.5,1) node {$D_{n-1}$};
\draw (7,3.5) node {$D_{n-1}$};

\end{tikzpicture}
\end{center}
\caption{Recursive definition of the Bethe cacti $E_n$}
\label{fig:E_n-recursive}
\end{figure}

\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.9,style=thick,x=1cm,y=1cm]
\def\vr{3pt}

\coordinate(x1) at (1,1.5);
\coordinate(x2) at (1.5,1);
\coordinate(x3) at (2,1.5);
\coordinate(x4) at (1.5,2);
\coordinate(x5) at (2,2.5);
\coordinate(x6) at (2.5,2);
\coordinate(x7) at (3,2.5);
\coordinate(x8) at (2.5,3);
\coordinate(x9) at (3,1.5);
\coordinate(x10) at (3.5,1);
\coordinate(x11) at (4,1.5);
\coordinate(x12) at (3.5,2);

\coordinate(a1) at (5,1.5);
\coordinate(a2) at (5.5,1);
\coordinate(a3) at (6,1.5);
\coordinate(a4) at (5.5,2);
\coordinate(a5) at (6.5,0.5);
\coordinate(a6) at (7,0);
\coordinate(a7) at (7.5,0.5);
\coordinate(a8) at (7,1);
\coordinate(a9) at (6.5,2.5);
\coordinate(a10) at (7,2);
\coordinate(a11) at (7.5,2.5);
\coordinate(a12) at (7,3);
\coordinate(a13) at (7.5,3.5);
\coordinate(a14) at (8,3);
\coordinate(a15) at (8.5,3.5);
\coordinate(a16) at (8,4);
\coordinate(a17) at (8.5,5);
\coordinate(a18) at (9,4.5);
\coordinate(a19) at (9.5,5);
\coordinate(a20) at (9,5.5);
\coordinate(a21) at (9.5,3.5);
\coordinate(a22) at (10,3);
\coordinate(a23) at (10.5,3.5);
\coordinate(a24) at (10,4);
\coordinate(a25) at (10.5,2.5);
\coordinate(a26) at (11,2);
\coordinate(a27) at (11.5,2.5);
\coordinate(a28) at (11,3);
\coordinate(a29) at (10.5,0.5);
\coordinate(a30) at (11,0);
\coordinate(a31) at (11.5,0.5);
\coordinate(a32) at (11,1);
\coordinate(a33) at (12,1.5);
\coordinate(a34) at (12.5,1);
\coordinate(a35) at (13,1.5);
\coordinate(a36) at (12.5,2);
\coordinate(x) at (8,1.5);

\coordinate(z) at (10,1.5);
\coordinate(w) at (9,2.5);

\draw (x1) -- (x2) -- (x3) -- (x4) -- (x1);
\draw (x5) -- (x6) -- (x7) -- (x8) -- (x5);
\draw (x9) -- (x10) -- (x11) -- (x12) -- (x9);
\draw (x3) -- (x6) -- (x9);

\draw (a1) -- (a2) -- (a3) -- (a4) -- (a1);
\draw (a5) -- (a6) -- (a7) -- (a8) -- (a5);
\draw (a9) -- (a10) -- (a11) -- (a12) -- (a9);
\draw (a13) -- (a14) -- (a15) -- (a16) -- (a13);
\draw (a17) -- (a18) -- (a19) -- (a20) -- (a17);
\draw (a21) -- (a22) -- (a23) -- (a24) -- (a21);
\draw (a25) -- (a26) -- (a27) -- (a28) -- (a25);
\draw (a29) -- (a30) -- (a31) -- (a32) -- (a29);
\draw (a33) -- (a34) -- (a35) -- (a36) -- (a33);

\draw (x) -- (a8) -- (a3) -- (a10) -- (x);
\draw (w) -- (a15) -- (a18) -- (a21) -- (w);
\draw (z) -- (a26) -- (a33) -- (a32) -- (z);
\draw (z) -- (w) -- (x);

\foreach \i in {1,2,...,12}
{
\draw(x\i)[fill=white] circle(\vr);
}

\foreach \i in {1,2,...,36}
{
\draw(a\i)[fill=white] circle(\vr);
}
\draw(x)[fill=white] circle(\vr);

\draw(z)[fill=white] circle(\vr);
\draw(w)[fill=white] circle(\vr);
\end{tikzpicture}
\end{center}
\caption{The Bethe cacti $E_2$ and $E_3$}
\label{fig:E_2-and-E_3}
\end{figure}

\begin{theorem}
\label{thm:M-poly-of-En}
$M(E_1; x,y) = 2xy^2$, $M(E_2; x,y) = 6x^2y^2 + 4x^2y^3 + 2x^2y^4 + 2x^3y^4$, and if $n\ge 3$, then
$$M(E_n; x,y) = 2\cdot 3^{n-1}x^2y^2 + 2\cdot 3^{n-1}x^2y^4 + 6x^3y^4 + (2\cdot 3^{n-1} - 10)x^4y^4\,.$$
\end{theorem}

\proof
Clearly, $M(E_1; x,y) = 2xy^2$ and $M(E_2; x,y) = 6x^2y^2 + 4x^2y^3 + 2x^2y^4 + 2x^3y^4$. Assume in the rest that $n\ge 3$. Note that two $24$-edges of the middle $D_{n-1}$ become $44$-edges in $E_n$, and that two $24$-edges of an extreme $D_{n-1}$ become $34$-edges in $E_n$. Hence, recalling again from the proof of Theorem~\ref{thm:M-poly-of-Dn} that $m_{2,2}(D_{n}) = 2\cdot 3^{n-1}$, $m_{2,4}(D_{n}) = 2\cdot 3^{n-1} + 2$, and $m_{4,4}(D_{n}) = 2\cdot 3^{n-1} - 4$, we get:
\begin{eqnarray*}
m_{2,2}(E_{n}) & = & 3 m_{2,2}(D_{n-1}) = 3\cdot 2\cdot 3^{n-2} = 2\cdot 3^{n-1}\,,\\
m_{2,3}(E_{n}) & = & 3 m_{2,3}(D_{n-1}) = 0\,,\\
m_{2,4}(E_{n}) & = & 3 m_{2,4}(D_{n-1}) - 6 = 3\cdot 2\cdot 3^{n-2} + 6 - 6 = 2\cdot 3^{n-1}\,,\\
m_{3,3}(E_{n}) & = & 3 m_{3,3}(D_{n-1}) = 0\,,\\
m_{3,4}(E_{n}) & = & 3 m_{3,4}(D_{n-1}) + 4 + 2 = 6\,,\\
m_{4,4}(E_{n}) & = & 3 m_{4,4}(D_{n-1}) + 2 = 3\cdot 2\cdot 3^{n-2} -12 + 2 = 2\cdot 3^{n-1} - 10\,.
\end{eqnarray*}
Putting all this together, the result follows.
\qed

\section{Topological indices of Bethe cacti}
\label{sec:Bethe-indices}

Combining Theorem~\ref{thm:M-poly-of-Dn} with the expressions from Table~\ref{table1}, routine computations yield the expressions for the selected listed topological indices of $D_n$, $C_n$, and $E_n$, $n\ge 2$. Let us demonstrate this by computing the symmetric division index of $D_n$, $n\ge 2$. From Table~\ref{table1} we know that this reduces to compute $(D_xS_y + D_yS_x)(M(G;x,y))\big|_{x=y=1}$. Now,
\begin{eqnarray*}
S_x(M(D_n;x,y)) & = & \int_0^x \frac{2\cdot 3^{n-1}t^2y^2 + 2(3^{n-1}+1)t^2y^4 + 2(3^{n-1} - 2)t^4y^4}{t} \\
& = & \frac{3^{n - 1}x^2y^2(x^2y^2 + 2(y^2 + 1))}{2} - x^4y^4 + x^2y^4\,,
\end{eqnarray*}
and hence
\begin{eqnarray}
\label{eq:first}
D_yS_x(M(D_n;x,y)) & = & y\cdot (2\cdot 3^{n - 1}x^2y(x^2y^2 + 2y^2 + 1) - 4x^2y^3(x^2 - 1))\,.
\end{eqnarray}
Similarly we compute that
\begin{eqnarray}
\label{eq:second}
D_xS_y(M(D_n;x,y)) & = & x\cdot (3^{n - 1}xy^2(2x^2y^2 + y^2 + 2) - xy^4(4x^2 - 1))\,.
\end{eqnarray}
Summing~\eqref{eq:first} and~\eqref{eq:second} we get
\begin{eqnarray*}
(D_xS_y + D_yS_x)(M(G;x,y)) & = & 3^{n - 1}x^2y^2(4x^2y^2 + 5y^2 + 4) - x^2y^4·(8x^2 - 5)
\end{eqnarray*}
from where we conclude that
\begin{eqnarray*}
(D_xS_y + D_yS_x)(M(G;x,y))\big|_{x=y=1} & = & 13\cdot 3^{n - 1} - 3\,.
\end{eqnarray*}
All the other entries from Table~\ref{table2} are computed along the same lines.

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|}\hline
$\phantom{\Big|}$topological index $I$ & $I(D_n)$ & $I(C_n)$ & $I(E_n)$ \\
\hline\hline
first Zagreb &
$\phantom{\displaystyle{\frac{1}{1}}} 4\cdot3^{n + 1} - 20$ &
$16\cdot 3^n - 32$ &
$4\cdot 3^{n + 1} - 38$ \\
\hline
second Zagreb &
$\phantom{\displaystyle{\frac{1}{1}}} 56\cdot3^{n - 1} - 48$ &
$224\cdot 3^{n - 2} - 64$ &
$56\cdot 3^{n - 1} - 88$ \\
\hline
second modified Zagreb &
$\phantom{\displaystyle{\frac{1}{1}}} \frac{7}{8}\cdot 3^{n - 1}$ &
$\frac{7}{2}\cdot 3^{n - 2} - \frac{1}{4}$ &
$\frac{7}{8}\cdot 3^{n - 1} - \frac{1}{8}$ \\
\hline
symmetric division index &
$\phantom{\displaystyle{\frac{1}{1}}} 13\cdot3^{n - 1} - 3$ &
$52\cdot 3^{n - 2} - 8$ &
$13\cdot 3^{n - 1} - \frac{15}{2}$ \\
\hline
harmonic &
$\phantom{\displaystyle{\frac{1}{1}}} \frac{13}{2}\cdot 3^{n - 2} - \frac{1}{3}$ &
$26\cdot 3^{n - 3} - 1$ &
$\frac{13}{2}\cdot 3^{n - 2} - \frac{11}{14}$ \\
\hline
inverse sum &
$\phantom{\displaystyle{\frac{1}{1}}} 26\cdot 3^{n - 2} - \frac{16}{3}$ &
$104\cdot 3^{n - 3} - 8$ &
$26\cdot 3^{n - 2} - \frac{68}{7}$ \\
\hline
\end{tabular}
\end{center}
\caption{Selected topological indices of Bethe cacti}
\label{table2}
\end{table}

\section{(An extension of) Gutman's approach}
\label{sec:conclude}

As already pointed out in~\cite{deutsch-2015}, an approach to determine the coefficients $m_{i,j}$ of an $M$-polynomial has been proposed by Gutman~\cite{gutman-2002} by considering corresponding linear equations. Let us briefly recall the approach here, in particular to correct a statement from~\cite[p.~99]{deutsch-2015} (see below).

Let $G$ be a chemical graph (a graph of maximum degree at most $4$) with $n$ vertices and $m$ edges, and let $n_i$, $1\le i\le 4$, be the number of vertices of degree $i$. Clearly, $m_{1,1} = 0$ as soon as the graph has at least three vertices and is connected, while for the the other $m_{i,j}$s we have:
\begin{eqnarray}
n_1 + n_2 + n_3 + n_4 & = & n \label{eq-3} \\
m_{1,2} + m_{1,3} + m_{1,4} & = & n_1 \label{eq-4} \\
m_{1,2} + 2m_{2,2} + m_{2,3} + m_{2,4} & = & 2n_2 \label{eq-5} \\
m_{1,3} + m_{2,3} + 2m_{3,3} + m_{3,4} & = & 3n_3 \label{eq-6} \\
m_{1,4} + m_{2,4} +m_{3,4} + 2m_{4,4} & = & 4n_4  \label{eq-7}\\
n_1 + 2n_2 + 3n_3 + 4n_4 & = & 2m\,. \label{eq-8}
\end{eqnarray}
Equations~\eqref{eq-3}-\eqref{eq-7} are linearly independent, while~\eqref{eq-8} is a consequence of~\eqref{eq-3}-\eqref{eq-7}. (In~\cite{deutsch-2015} it is said that all these equations are linearly independent.) Gutman's approach is to determine first some of the $m_{i,j}$s and then the remaining ones can be obtained from the above relations.

We extend Gutman's approach by adjoining to Equations~\eqref{eq-3}-\eqref{eq-8} Euler's formula (cf.~\cite[p.~201]{west-2001})
\begin{equation}
\label{eq:Euler}
\sum m_{i,j} - \sum n_i = f - 2\,,
\end{equation}
usable whenever dealing with a plane graph whose number of faces $f$ can be determined.

In the rest we are going to use this extended Gutman approach to determine the $M$-polynomial of the networks $G(p,q)$, $p,q\ge 1$. In Fig.~\ref{fig:G(3,4)} the network $G(3,4)$ is drawn, from which the general definition should be clear. In particular, $G(1,1)$ consists of an $8$-gon with two $6$-gons attached at the top and two $6$-gons attached at the bottom.

\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.7,style=thick,x=1cm,y=1cm]
\def\vr{3pt}

\draw (1,0) -- (0,0.5) -- (0,1.5) -- (1,2) -- (0.5,3) -- (1,4) -- (0,4.5) -- (0,5.5) -- (1,6) -- (0.5,7) -- (1,8) -- (0,8.5) -- (0,9.5) -- (1,10) -- (0.5,11) -- (1,12) -- (0,12.5) -- (0,13.5) -- (1,14);

\draw (5,0) -- (4,0.5) -- (4,1.5) -- (5,2) -- (4.5,3) -- (5,4) -- (4,4.5) -- (4,5.5) -- (5,6) -- (4.5,7) -- (5,8) -- (4,8.5) -- (4,9.5) -- (5,10) -- (4.5,11) -- (5,12) -- (4,12.5) -- (4,13.5) -- (5,14);

\draw (9,0) -- (8,0.5) -- (8,1.5) -- (9,2) -- (8.5,3) -- (9,4) -- (8,4.5) -- (8,5.5) -- (9,6) -- (8.5,7) -- (9,8) -- (8,8.5) -- (8,9.5) -- (9,10) -- (8.5,11) -- (9,12) -- (8,12.5) -- (8,13.5) -- (9,14);

\draw (13,0) -- (12,0.5) -- (12,1.5) -- (13,2) -- (12.5,3) -- (13,4) -- (12,4.5) -- (12,5.5) -- (13,6) -- (12.5,7) -- (13,8) -- (12,8.5) -- (12,9.5) -- (13,10) -- (12.5,11) -- (13,12) -- (12,12.5) -- (12,13.5) -- (13,14);

\draw (1,0) -- (2,0.5) -- (2,1.5) -- (3,2) -- (3.5,3) -- (3,4) -- (2,4.5) -- (2,5.5) -- (3,6) -- (3.5,7) -- (3,8) -- (2,8.5) -- (2,9.5) -- (3,10) -- (3.5,11) -- (3,12) -- (2,12.5) -- (2,13.5) -- (1,14);

\draw (5,0) -- (6,0.5) -- (6,1.5) -- (7,2) -- (7.5,3) -- (7,4) -- (6,4.5) -- (6,5.5) -- (7,6) -- (7.5,7) -- (7,8) -- (6,8.5) -- (6,9.5) -- (7,10) -- (7.5,11) -- (7,12) -- (6,12.5) -- (6,13.5) -- (5,14);

\draw (9,0) -- (10,0.5) -- (10,1.5) -- (11,2) -- (11.5,3) -- (11,4) -- (10,4.5) -- (10,5.5) -- (11,6) -- (11.5,7) -- (11,8) -- (10,8.5) -- (10,9.5) -- (11,10) -- (11.5,11) -- (11,12) -- (10,12.5) -- (10,13.5) -- (9,14);

\draw (13,0) -- (14,0.5) -- (14,1.5) -- (15,2) -- (15.5,3) -- (15,4) -- (14,4.5) -- (14,5.5) -- (15,6) -- (15.5,7) -- (15,8) -- (14,8.5) -- (14,9.5) -- (15,10) -- (15.5,11) -- (15,12) -- (14,12.5) -- (14,13.5) -- (13,14);

\draw (0,0.5) -- (1,0) -- (2,0.5) -- (3,0) -- (4,0.5) -- (5,0) -- (6,0.5) -- (7,0) -- (8,0.5) -- (9,0) -- (10,0.5) -- (11,0) -- (12,0.5) -- (13,0) -- (14,0.5) -- (15,0) -- (16,0.5);

\draw (0,4.5) -- (1,4) -- (2,4.5) -- (3,4) -- (4,4.5) -- (5,4) -- (6,4.5) -- (7,4) -- (8,4.5) -- (9,4) -- (10,4.5) -- (11,4) -- (12,4.5) -- (13,4) -- (14,4.5) -- (15,4) -- (16,4.5);

\draw (0,8.5) -- (1,8) -- (2,8.5) -- (3,8) -- (4,8.5) -- (5,8) -- (6,8.5) -- (7,8) -- (8,8.5) -- (9,8) -- (10,8.5) -- (11,8) -- (12,8.5) -- (13,8) -- (14,8.5) -- (15,8) -- (16,8.5);

\draw (0,12.5) -- (1,12) -- (2,12.5) -- (3,12) -- (4,12.5) -- (5,12) -- (6,12.5) -- (7,12) -- (8,12.5) -- (9,12) -- (10,12.5) -- (11,12) -- (12,12.5) -- (13,12) -- (14,12.5) -- (15,12) -- (16,12.5);

\draw (0,1.5) -- (1,2) -- (2,1.5) -- (3,2) -- (4,1.5) -- (5,2) -- (6,1.5) -- (7,2) -- (8,1.5) -- (9,2) -- (10,1.5) -- (11,2) -- (12,1.5) -- (13,2) -- (14,1.5) -- (15,2) -- (16,1.5);

\draw (0,5.5) -- (1,6) -- (2,5.5) -- (3,6) -- (4,5.5) -- (5,6) -- (6,5.5) -- (7,6) -- (8,5.5) -- (9,6) -- (10,5.5) -- (11,6) -- (12,5.5) -- (13,6) -- (14,5.5) -- (15,6) -- (16,5.5);

\draw (0,9.5) -- (1,10) -- (2,9.5) -- (3,10) -- (4,9.5) -- (5,10) -- (6,9.5) -- (7,10) -- (8,9.5) -- (9,10) -- (10,9.5) -- (11,10) -- (12,9.5) -- (13,10) -- (14,9.5) -- (15,10) -- (16,9.5);

\draw (0,13.5) -- (1,14) -- (2,13.5) -- (3,14) -- (4,13.5) -- (5,14) -- (6,13.5) -- (7,14) -- (8,13.5) -- (9,14) -- (10,13.5) -- (11,14) -- (12,13.5) -- (13,14) -- (14,13.5) -- (15,14) -- (16,13.5);

\draw (3.5,3) -- (4.5,3); \draw (7.5,3) -- (8.5,3); \draw (11.5,3) -- (12.5,3);
\draw (3.5,7) -- (4.5,7); \draw (7.5,7) -- (8.5,7); \draw (11.5,7) -- (12.5,7);
\draw (3.5,11) -- (4.5,11); \draw (7.5,11) -- (8.5,11); \draw (11.5,11) -- (12.5,11);

\draw (16,0.5) -- (16,1.5);
\draw (16,4.5) -- (16,5.5);
\draw (16,8.5) -- (16,9.5);
\draw (16,12.5) -- (16,13.5);

\draw (2,11) node {$1$};
\draw (2,7) node {$2$};
\draw (2,3) node {$p=3$};
\draw (6,11) node {$2$};
\draw (10,11) node {$3$};
\draw (14,11) node {$q=4$};

\end{tikzpicture}
\end{center}
\caption{The lattice $G(3,4)$}
\label{fig:G(3,4)}
\end{figure}

Clearly, vertices of $G(p,q)$ are of degrees $2$ and $3$, hence we need to determine $m_{2,2} = m_{2,2}(G(p,q))$,
$m_{2,3} = m_{2,3}(G(p,q))$, and
$m_{3,3} = m_{3,3}(G(p,q))$.

Note first that
\begin{equation}
\label{eq:m22}
m_{2,2} = 2(p + 1) + 4 = 2p + 6\,,
\end{equation}
where $2(p + 1)$ correspond the side edges with both end-points of degree $2$, and $4$ corresponds to the corner edges (with both end-points of degree $2$). Furthermore,  $n_2 = 4q + 4(p + 1) + 2p = 6p + 4q + 4$, where $4q$ comes from the top and bottom vertices of degree $2$, the term $4(p + 1)$ comes from the sides, and the term $2p$ from the almost sides. Equation~\eqref{eq-5} in our case reduces to $2m_{2,2} + m_{2,3} = 2n_2$, from which we get
\begin{equation}
\label{eq:m23}
m_{2,3} = 8p + 8q - 4\,.
\end{equation}
Equation~\eqref{eq-6} reduces to $m_{2,3} + 2m_{3,3} = 3n_3$ and therefore,
\begin{equation}
\label{eq:n3-m33}
3n_3 - 2m_{3,3} = 8p + 8q - 4\,.
\end{equation}
Since the number of $8$-gons of $G(p,q)$ is $pq$, the number of its $6$-gons is $2q(p+1)$, and the number of its $5$-gons is $2p(q-1)$, Equation~\eqref{eq:Euler} reduces to

\begin{equation}
\label{eq:Euler-2}
m_{3,3} - n_3 = 5pq - 6p - 2q + 1\,.
\end{equation}
Solving~\eqref{eq:n3-m33} and~\eqref{eq:Euler-2} yields $n_3 = 10pq - 4p + 4q - 2$ and
\begin{equation}
\label{eq:m33}
m_{3,3} = 15pq - 10p + 2q - 1\,.
\end{equation}
From Equations~\eqref{eq:m22}, \eqref{eq:m23}, and \eqref{eq:m33} we conclude that
$$M(G(p,q); x,y) = (2p + 6)x^2y^2 + (8p + 8q - 4)x^2y^3 + (15pq - 10p + 2q - 1)x^3y^3\,.$$

\section*{Acknowledgments}

Sandi Klav\v zar acknowledges the financial support from the Slovenian Research Agency (research core funding No.\ P1-0297).


TITLE: Distributions dual to functions of polynomial growth.
QUESTION [0 upvotes]: The space of distributions on $\mathbb{R}^n$ is essentially found by requiring that it should be possible to apply the distribution to any bump function. Similarly, compactly supported distributions can be applied to any smooth function.
Is there some space of distributions which can be applied to all functions of polynomial growth?
I'm fairly sure this condition should have been given a name by now but I'm struggling to find a reference.

REPLY [0 votes]: Since I was unable to find any name for this type of distribution I have given it a name myself and proved that it works well. Here are the relevant notions:


TITLE: Neumann boundary conditions for Laplace equation with Raviart-Thomas elements
QUESTION [2 upvotes]: I am working on creating a finite element model for the Darcy equation using Raviart-Thomas elements and the mixed hybrid formulation.
The problem in mixed form is this:
$\mathbb{K}\nabla p = \vec{q}$
$\nabla\cdot\vec{q} = 0$
Where $\mathbb{K}$ is the diagonal matrix $\begin{bmatrix} k_0 & 0 \\ 0 & k_1\end{bmatrix}$
Now the weak formulation with Lagrange multipliers is:
$\begin{align}
\int_\Omega \mathbb{K}^{-1} \bar{\vec{q}}\cdot\vec{q} d \Omega + \int_\Omega p \nabla\bar{\vec{q}} d \Omega- \sum_E \iint_E \lambda\cdot(\bar{\vec{q}}\cdot\vec{n}_E) dE & = \int_\Gamma \bar{\vec{q}}\cdot\vec{n}p d \Gamma \\
    \int_\Omega \bar{p}\nabla\cdot\vec{q} &= 0 \\
\sum_E \iint_E \bar{\lambda}\cdot(\vec{q}\cdot\vec{n}_E) dE &= 0
\end{align}$
Where a bar over the variable indicates it is a test function for that variable.
Now I understand where the Dirchelet boundary conditions can be included, but for my case I would like to be able to also include Neumann boundary conditions. I found  an article which does what I want to be included, but the mathematic are unfortunately too complicated for me (I'm an undergrad student Biomedical Engineering).
I am hoping that someone here can help me with this problem.

REPLY [0 votes]: Neumann boundary conditions for the mixed formulation are imposed as "essential" boundaries. What that means is, you enforce it by directly setting $\vec{q}$ on the boundary. Remember that $RT_0$ gives you a single velocity degree of freedom on every edge. Since you have a Neumann condition, you want to directly restrict the velocity unknowns on the Neumann edges to the value of the boundary condition.
One way of accomplishing this is by first building the entire linear system of equation as if you have Dirichlet (pressure) boundaries. Locate in the linear system the rows that correspond to the Neumann boundaries. You can then force those unknowns to the value you need it to be by setting the row to zero and placing 1 on the diagonal. On the corresponding right hand side, place the actual flux value you want to set it to.
For example, let's say your linear system looks like this:
$$
\left(\begin{array}{cccc}
a_{00} &a_{01} & a_{02} &a_{03}\\
a_{10} &a_{11} & a_{12} &a_{13}\\
a_{20} &a_{21} & a_{22} &a_{23}\\
a_{30} &a_{31} & a_{32} &a_{33}
\end{array}\right)
\left(\begin{array}{c}
q_0\\
q_1\\
q_2\\
p_0
\end{array}\right)=
\left(\begin{array}{c}
0\\
0\\
0\\
0
\end{array}\right)
$$
Let's assume that $q_0, q_1, q_2$ are the velocity unknowns corresponding to edges of a triangle. Say you want to set the boundary on $q_0 = 10$. The linear system would then become:
$$
\left(\begin{array}{cccc}
1 & 0 & 0 & 0\\
a_{10} &a_{11} & a_{12} &a_{13}\\
a_{20} &a_{21} & a_{22} &a_{23}\\
a_{30} &a_{31} & a_{32} &a_{33}
\end{array}\right)
\left(\begin{array}{c}
q_0\\
q_1\\
q_2\\
p_0
\end{array}\right)=
\left(\begin{array}{c}
10\\
0\\
0\\
0
\end{array}\right)
$$


TITLE: How can I find the max number of times the Euclidean Algorithm must be executed for a given starting remainder?
QUESTION [2 upvotes]: If each step of the Euclidean Algorithm reduces the remainder by at least 50%, how can I calculate the max number of steps it will take to find the greatest common denominator? If the initial remainder of two numbers is 1000, would log2(m) give me this value? If r ≤ m/2 for each step of the Euclidean Algorithm, could I just find m assuming that r = 1000 in the max case and substitute m in the previous logarithm to find the max number of steps?

REPLY [3 votes]: A brute force run shows that the maximum number of iterations is indicated by the ordinality of the first Fibonacci number greater than the larger number of the pair subjected to Euclid's Algorithm. For example, for the numbers $(1000,x)$, the next Fibonacci number is $1597$ and it is the $15^{th}$ or $16^{th}$ Fibonacci number depending on where you begin the series, so the maximum number of iterations is $15$ or $16$ assuming $x$ is smaller than $1000$.
(Note: If the larger number is entered second, the iteration count is one higher.) Here is a sample run in which the "count" and GCD numbers are displayed only when the current iteration count for a pair is greater than the previous "largest count". It took $\approx 3.2$ hours of CPU time using interpretive BASIC. I'm sure it would take less time with math-specific languages.
 enter limit? 100000
 iterations( 1 )    GCD( 2 , 1 ) = 1
 iterations( 2 )    GCD( 3 , 2 ) = 1
 iterations( 3 )    GCD( 5 , 3 ) = 1
 iterations( 4 )    GCD( 8 , 5 ) = 1
 iterations( 5 )    GCD( 13 , 8 ) = 1
 iterations( 6 )    GCD( 21 , 13 ) = 1
 iterations( 7 )    GCD( 34 , 21 ) = 1
 iterations( 8 )    GCD( 55 , 34 ) = 1
 iterations( 9 )    GCD( 89 , 55 ) = 1
 iterations( 10 )   GCD( 144 , 89 ) = 1
 iterations( 11 )   GCD( 233 , 144 ) = 1
 iterations( 12 )   GCD( 377 , 233 ) = 1
 iterations( 13 )   GCD( 610 , 377 ) = 1
 iterations( 14 )   GCD( 987 , 610 ) = 1
 iterations( 15 )   GCD( 1597 , 987 ) = 1
 iterations( 16 )   GCD( 2584 , 1597 ) = 1
 iterations( 17 )   GCD( 4181 , 2584 ) = 1
 iterations( 18 )   GCD( 6765 , 4181 ) = 1
 iterations( 19 )   GCD( 10946 , 6765 ) = 1
 iterations( 20 )   GCD( 17711 , 10946 ) = 1
 iterations( 21 )   GCD( 28657 , 17711 ) = 1
 iterations( 22 )   GCD( 46368 , 28657 ) = 1
 iterations( 23 )   GCD( 75025 , 46368 ) = 1

BASIC is considered unsophisticated these days but it is free and easier to learn that PYTHON and others. Here is the program that ran the test above.
  100 print "enter limit";
  110 input l1
  120 c9 = 0
  130 for i1 = 1 to l1
  140    for i2 = 1 to i1-1
  150 c1 = 0
  160 x1 = i1
  170 x2 = i2
  180 r1 = x1 mod x2
  190 c1 = c1+1
  200 if r1 > 0
  210    x1 = x2
  220    x2 = r1
  230 goto 180
  240 endif
  250 if c1 > c9
  260    c9 = c1
  270    print "iterations( " c1 ")  ",;
  280    print "GCD( " i1 ", " i2 ") = " x2
  290 endif
  300   next i2
  310 next i1


TITLE: Cardinality of the set of maximal ideals in a Boolean ring/algebra
QUESTION [1 upvotes]: If B is a Boolean ring is of uncountable cardinality c, does B have 2^c distinct maximal ideals ?
Can you please give me a reference where this question is answered (hopefully) positively ? Thanks

REPLY [3 votes]: This particular question is easy to answer.  Many related questions about the relationships between various cardinals associated with Boolean algebra (or Boolean rings), such as: cardinality, number of ultrafilters, density, cellularity, distributivity etc, can be found in

Monk, J. Donald: Cardinal invariants on Boolean algebras.
Progress in Mathematics, 142. Birkhäuser Verlag, Basel, 1996. 3-7643-5402-X.  MR1393943


TITLE: Finding the volume when a region is rotated about the $y$-axis?
QUESTION [0 upvotes]: My basic question is:
When we think of the area under the graph and extending it in the 3 dimensions, we actually get a cylinder with height = $f(x)$, thickness = $dx$ and inner radius = $x$. Then the volume should be $\int \pi (2x+dx) \ dx\  f(x) $. Right?
Then why is it:
$\int \pi\ x f(x) dx$ ??

REPLY [1 votes]: You just need to think carefully about what is going on with the method of shells. I suggest reading here (scroll down about halfway where they start talking about shells).
Another great resource that explains what you need is video #29 in this series. (The entire set of videos is excellent, with great visuals as well as step-by-step explanations.)
Most generally (and as the links above will explain), the method of shells produces an integral of the form $$\int_a^b \pi\cdot(\text{shell radius})\cdot(\text{shell height})\,dx,$$ i.e., $\int_a^b \pi\,x f(x)\,dx$ as you mentioned.


TITLE: Derive closed form solution of linear regression in the overparametrized case
QUESTION [0 upvotes]: Consider the linear regression model in the case where number of training samples $n$ < number of parameters $d$ (overparametrized linear regression). The model is
$$y_i = <\beta,\mathbf{x}_i> +\epsilon_i, \quad \beta\in\mathbb{R}^d,\ \epsilon_i\in\mathbb{R},\ i=1,\dots,n$$
where $\epsilon$ is zero-mean noise. Let $\mathbf{X}\in\mathbb{R}^{n\times d}$ be the data matrix:
\begin{align}
    \mathbf{X} &= \begin{bmatrix}
           \mathbf{x}_1\\
           \mathbf{x}_2\\
           \vdots \\
           \mathbf{x}_n
         \end{bmatrix}
  \end{align}
Now, since $n<d$, $\mathbf{X}^T\mathbf{X}\in\mathbb{R}^{d\times d}$ is not invertible, since
$$\text{rank}(\mathbf{X})=\text{rank}(\mathbf{X}^T) \leq \min \{n,d\}=n\implies \text{rank}(\mathbf{X}^T\mathbf{X})\leq n<d$$
There are clearly infinitely many $\beta$ such that
$$\mathbf{y}=\mathbf{X}\beta$$
I'm told that the minimum norm solution is
$$\beta^*=\mathbf{X}^{\dagger}y$$
where, in this specific case $n < d$, $\mathbf{X}^{\dagger}=\mathbf{X}^T(\mathbf{X} \mathbf{X}^T)^{-1}$. Can you help me prove this in a constructive manner? I tried to premultiply by $\mathbf{X}^T\in\mathbb{R}^{d\times n}$ (which is legit since $\mathbf{y}\in\mathbb{R}^n$), but I get
$$\mathbf{X}^T\mathbf{y}=\mathbf{X}^T\mathbf{X}\beta$$
and now I'm stuck because, as noted above, $=\mathbf{X}^T\mathbf{X}$ is not invertible.
EDIT: the solution
$$\beta^*=\mathbf{X}^{\dagger}y$$
is valid iif $\mathbf{X}\mathbf{X}^T$ is invertible. However, since
$\mathbf{X}\mathbf{X}^T\in\mathbb{R}^{n\times n}$, $\text{rank}(\mathbf{X}^T\mathbf{X})\leq n $ and $\mathbf{X}$ is a random matrix, meaning that its rows are random vectors sampled from an (unknown) probability distribution, for most nondegenerate probability distributions $\mathbf{X}\mathbf{X}^T$ will be full rank.
EDIT2: a question was mentioned in the comments, which isn't related to my question. I explicitly asked for a constructive proof of the fact that, when $n<d$, the minimum norm solution is
$$\beta^*=\mathbf{X}^T(\mathbf{X} \mathbf{X}^T)^{-1}y$$
instead of the usual one, when $\mathbf{X}$ is full column rank
$$\beta^*=(\mathbf{X}^T \mathbf{X})^{-1}\mathbf{X}^Ty$$
Thus, answers that don't constructively derive this expression, are not answers to this question.

REPLY [1 votes]: (Note to whoever was thinking about answering my question: I'm not going to accept my own answer anytime soon, so if you were going to write an answer of yours, don't feel discouraged!)
Proof #1
By Lagrange multipliers: we're looking for
$$\min_{\beta}{\frac{1}{2}||\beta||^2} \quad s.t. \mathbf{X}\beta=\mathbf{y}$$
Convert to unconstrained optimization by introducing a Lagrange multiplier $\lambda$:
$$\min_{\beta,\lambda}\frac{1}{2}||\beta||^2+\lambda^T(\mathbf{X}\beta-\mathbf{y})=\min_{\beta,\lambda}\mathcal{L}(\beta,\lambda)$$
Set gradients to 0:
$$ \begin{equation*}
\begin{alignedat}{3}
 \nabla_{\beta}{\mathcal{L}} & = \beta +\mathbf{X}^T\lambda=0  \\
  \nabla_{\lambda}{\mathcal{L}} & = \mathbf{X}\beta-\mathbf{y}=0
\end{alignedat}
\end{equation*}$$
Thus $-\mathbf{X}\mathbf{X}^T\lambda=\mathbf{y}$. But since $\mathbf{X}\mathbf{X}^T$ is invertible, we get
$$\lambda=-(\mathbf{X}\mathbf{X}^T)^{-1}\mathbf{y}\implies\beta=-\mathbf{X}^T\lambda=\mathbf{X}^T(\mathbf{X}\mathbf{X}^T)^{-1}\mathbf{y}\ \square.$$
The nice thing about this proof is that you don't have to commit the expression of the pseudo-inverse to memory.
Proof #2
Not as satisfying. Assume $\beta^*=\mathbf{X}^T(\mathbf{X}\mathbf{X}^T)^{-1}\mathbf{y}$: we want to prove that

it's a solution of $\mathbf{X}\beta=\mathbf{y}$
it's the min norm solution

1) is trivial: $\mathbf{X}\beta^*=\mathbf{X}\mathbf{X}^T(\mathbf{X}\mathbf{X}^T)^{-1}\mathbf{y}=\mathbf{y}$. To prove 2), it's sufficient to prove that, given any other solution $\beta$ to $\mathbf{X}\beta=\mathbf{y}$, then $(\beta-\beta^*)=\mathbf{u}$ is orthogonal to $\beta^*$. The assertion then follows immediately:
$$||\beta||^2=\beta^T\beta=(\mathbf{u}+\beta^*)^T(\mathbf{u}+\beta^*)=||\mathbf{u}||^2+2\mathbf{u}^T\beta^*+||\beta^*||^2=||\mathbf{u}||^2+||\beta^*||^2\geq||\beta^*||^2$$
To prove that $(\beta^*)^T\mathbf{u}=0$, we write
$$(\mathbf{X}^T(\mathbf{X}\mathbf{X}^T)^{-1}\mathbf{y})^T\mathbf{u}=\mathbf{y}^T(\mathbf{X}\mathbf{X}^T)^{-1}\mathbf{X}\mathbf{u}=\mathbf{y}^T(\mathbf{X}\mathbf{X}^T)^{-1}\mathbf{X}(\beta-\beta^*)=\mathbf{y}^T(\mathbf{X}\mathbf{X}^T)^{-1}(\mathbf{y}-\mathbf{y})=0$$
where we used the fact that $\mathbf{X}\mathbf{X}^T$ is symmetric and so is its inverse.


TITLE: Factorial Proof - ${n \choose r-1}+{n \choose r}={n+1 \choose r}$
QUESTION [4 upvotes]: ${n \choose r-1}+{n \choose r}={n+1 \choose r}.$
So what I tried to do was expand the first and second term.
$\frac{n!}{(r-1)!(n+1-r)!}+\frac{n!}{(r)!(n-r)!}.$
Then what I did was try to get common denominators.
$\frac{n!}{(r-1)!(n+1-r)(n-r)!}+\frac{n!}{(r)(r-1)!(n-r)!}.$
Then I attempted to combine and get the common denominator.
$\frac{(n!)(r)+(n!)(n+1-r)}{(r-1)!(n+1-r)(n-r)!(r)}.$
From here I simplified a bit more but didn't get a nice answer.
Some insight would be helpful.

REPLY [3 votes]: \begin{eqnarray*}\binom{n}{r-1}+\binom{n}{r}&=&\frac{n!}{(n-(r-1))!(r-1)!}+\frac{n!}{(n-r)!r!}\\&=&\frac{n!r}{(n-r+1)!r!}+\frac{n!(n-r+1)}{(n-r+1)!r!}\\&=&\frac{n!r+n!n-n!r+n!}{(n-r+1)!r!}\\&=&\frac{n!n+n!}{(n+1-r)!r!}\\&=&\frac{(n+1)n!}{(n+1-r)!r!}\\&=&\frac{(n+1)!}{((n+1)-r)!r!}\\&=&\binom{n+1}{r}
\end{eqnarray*}

REPLY [0 votes]: You start well:
$$
\binom{n}{r-1}+\binom{n}{r}=
\frac{n!}{(r-1)!\,(n-r+1)!}+\frac{n!}{r!\,(n-r)!}
$$
Now it's best to collect all common terms. Not so different from what you did, but with less complications. Note you can collect

$n!$ in the numerator
$(r-1)!$ in the denominator, using $r!=r\,(r-1)!$
$(n-r)!$ in the denominator, using $(n-r+1)!=(n-r+1)\,(n-r)!$

Thus you can go on with
$$
=\frac{n!}{(r-1)!\,(n-r)!}\left(\frac{1}{n-r+1}+\frac{1}{r}\right)
$$
The part in parentheses can be rewritten as $\dfrac{n+1}{r(n-r+1)}$
so you have
$$
=\frac{(n+1)\,n!}{r\,(r-1)!\,(n-r+1)\,(n-r)!}=\frac{(n+1)!}{r!\,(n+1-r)!}=\binom{n+1}{r}
$$


TITLE: Quadrature methods for high-dimensional Gaussian integration
QUESTION [1 upvotes]: Suppose that $f$ is the density of a high(-$d$)-dimensional Gaussian measure with mean $\mu$ and non-singular covariance matrix $\Sigma$.  Let $g:\mathbb{R}^d\rightarrow \mathbb{R}$ be a continuous function for which the integral $\int f(x)g(x)dx<\infty$.
Are there known "efficient" quadrature rules specifically for computing the integral $\int f(x)g(x)dx$ under these assumptions?

REPLY [2 votes]: You may want to use a stochastic algorithm. Entry points to the literature (which is large) could be

A stochastic
algorithm for high-dimensional integrals over unbounded regions with
Gaussian weight (1999)

Higher-Dimensional
Integration with Gaussian Weight for Applications in Probabilistic
Design (2004)

Sparse Quadrature for High-Dimensional Integration with Gaussian Measure (2018)

Cubature formulae for the gaussian weight: Some old and new rules (2020)


TITLE: Solving this problem without Taylor series ( I made an extra assumption)
QUESTION [3 upvotes]: I want to show that the derivative of a (one-time differentiable) function $f(x)$ is given by $$f'(a)= \lim \limits_{h \to 0} \dfrac {1}{h} \displaystyle \int_{-1}^{1} \dfrac{3u}{2} f(a+uh) \ du$$
I used the Taylor's expansion about the point $x=a$ and the conventional $h$ as $uh$ [i.e. $f(x+h)= f(x) + h f'(x) + \cdots$] and got the answer. However, I made an additional assumption that the function $f(x)$ possesses a convergent series about $uh$ and this includes the assumption that the function is differentiable more than once.
Tried applying the Leibniz rule, but could not get to the RHS. How can I prove the result without using the Taylor series?

REPLY [0 votes]: Let $u=t^{1/3}/h$ so that $$du=\frac{1}{3h}t^{-2/3}\,dt$$ and thus the desired limit is $$\lim_{h\to 0}\frac{1}{2h^3}\int_{-h^3}^{h^3}\frac{f(a+t^{1/3})}{t^{1/3}}\,dt$$ Next use $v=h^3$ to get $$\lim_{v\to 0}\frac{1}{2v}\int_{-v}^{v}\frac{f(a+t^{1/3})-f(a)}{t^{1/3}}\,dt+\frac{f(a) }{2v} \int_{-v} ^{v} t^{-1/3}\,dt$$ Note that the second integral is $0$ and the first integral can be split into integrals over $[-v, 0]$ and $[0,v]$. Thus the limit is split into limit of two terms one of which is $$\lim_{v\to 0}\frac{1}{2v}\int_0^v\frac{f(a+t^{1/3})-f(a)}{t^{1/3}}\,dt$$ and by fundamental theorem of calculus this equals $$\frac{1}{2}\lim_{t\to 0}\frac{f(a+t^{1/3})-f(a)}{t^{1/3}}=\frac{f'(a)}{2}$$ Similarly the other limit also equals $f'(a) /2$ and the desired limit is $f'(a)$.

The above uses the assumption that $f$ is Riemann integrable in some neighborhood of $a$ and derivative $f'(a) $ exists.


TITLE: Is the passive reference configuration different from the conventional direction of current?
QUESTION [0 upvotes]: Is the passive reference configuration different from the conventional direction of current?
According to the passive reference configuration, current enters the positive polarity of voltage, while according to conversational current, electric current is said to move from the positive terminal to the negative. So do they differ in terms of current direction, or have I got something wrong? I was just expecting them to agree with each other.

REPLY [0 votes]: I think you're just asking for some clarification on terminology. Imagine a circuit which consists of only a resistor (passive component) connected across a battery (an active component). The end of the resistor connected to the battery's positive terminal will be it's positive end.
In the conventional current model, current flows out of the battery's positive end into the resistor's positive end. The term "passive reference configuration" is just a way of stating this, or letting you know the conventional current model is being used.


text:
\subsection{Campana's orbifold category}
Before proceeding to the proof, let us first make some recall.

A \textsl{smooth orbifold pair} is a pair \((X,\Delta)\), where \(X\) is a smooth projective variety and where \(\Delta\) is a \(\Q\)-divisor on \(X\) with only normal crossings and with coefficients between \(0\) and \(1\).
In analogy with ramification divisors, it is very natural to write
\[
  \Delta
  =
  \sum_{i\in I}
  (1-\myfrac{1}{m_{i}}) \Delta_{i},
\]
with \textsl{multiplicities} \(m_{i}=a_i/b_i\) in \(\Q_{\geq1}\cup\Set{+\infty}\).
If \(b_{i}=0\), by convention \(a_{i}=1\).
The multiplicity \(1\) corresponds to empty boundary divisors.
The multiplicity \(+\infty\) corresponds to reduced boundary divisors.
We denote \(\abs{\Delta}\bydef\sum_{i\in I}\Delta_i\) (it could be slightly larger than the support of \(\Delta\) because of possible multiplicities \(1\)).

Such pairs \((X,\Delta)\) are studied using their \textsl{orbifold cotangent bundles} (\cite{CP15}).
Following the presentation used notably in \cite{C15},  it is natural to define these bundles on certain Galois coverings, the ramification of which is partially supported on \(\Delta\).
A Galois covering \(\pi\colon Y\to X\) from a smooth projective (connected) variety $Y$ will be termed \textsl{adapted} for the pair \((X,\Delta)\) if
\begin{itemize}
  \item
    for any component \(\Delta_{i}\) of \(\abs{\Delta}\), \(\pi^{\ast}\Delta_{i}=p_{i}D_{i}\), where \(p_{i}\) is an integer multiple of \(a_{i}\) and \(D_{i}\) is a simple normal crossing divisor;
  \item
    the support of \(\pi^{\ast}\Delta+\mathrm{Ram}(\pi)\) has only normal crossings, and the support of the branch locus of \(\pi\) has only normal crossings.
\end{itemize}
There always exists such an adapted covering (\cite[Prop. 4.1.12]{Laz}).

Let \(\pi\colon Y\to X\) be a \(\Delta\)-adapted covering. For any point \(y\in Y\), there exists an open neighbourhood \(U\ni y\) invariant under the isotropy group of \(y\) in \(\Aut(\pi)\), equipped with centered coordinates \(w_{i}\) such that \(\pi(U)\) has coordinates \(z_{i}\) centered in \(\pi(y)\) and
\[
  \pi(w_{1},\dotsc,w_{n})
  =
  (z_{1}^{p_{1}},
  \dotsc,
  z_{n}^{p_{n}}),
\]
where \(p_{i}\) is an integer multiple of the coefficient \(a_{i}\) of \((z_{i}=0)\).
Here by convention, if \(z_{i}\) is not involved in the local definition of \(\Delta\) then \(a_{i}=b_{i}=1\).

If all multiplicities are infinite (\(\Delta=\abs{\Delta}\)), for any \(\Delta\)-adapted covering \(\pi\colon Y\to X\), we denote
\[
  \Omega(\pi,\Delta)
  \bydef
  \pi^{\ast}\Omega_{X}(\log \Delta).
\]
For arbitrary multiplicities, the \textsl{orbifold cotangent bundle} is defined to be the vector bundle \(\Omega(\pi,\Delta)\) fitting in the following short exact sequence:
\begin{equation}
  \label{eq:orbi_cotangent}
  0
  \to
  \Omega(\pi,\Delta)
  \hookrightarrow
  \Omega(\pi,\abs{\Delta})
  \stackrel{\mathrm{res}}{\longrightarrow}
  \bigoplus_{i\in I\colon m_{i}<\infty}
  \O_{\myfrac{\pi^{\ast}\Delta_{i}}{m_{i}}}
  \to
  0.
\end{equation}
Here the quotient is the composition of the pullback of the residue map
\[
  \pi^{\ast}\mathrm{res}
  \colon
  \pi^{\ast}\Omega_{X}(\log \abs{\Delta})
  \to
  \bigoplus_{i\in I\colon m_{i}<\infty}
  \O_{\pi^{\ast}\Delta_{i}}
\]
with the quotients
\(
\O_{\pi^{\ast}\Delta_{i}}
\twoheadrightarrow
\O_{\myfrac{\pi^{\ast}\Delta_{i}}{m_{i}}}
\)
(\cite[\textit{loc. cit.}]{C15}).

Alternatively, the sheaf of orbifold differential forms adapted to \(\pi\colon Y\to(X,\Delta)\) is the subsheaf
\(
\Omega(\pi,\Delta)
\subseteq
\Omega(\pi,\abs{\Delta})
\)
locally generated (in coordinates as above) by the elements
\[
  w_{i}^{\myfrac{p_{i}}{m_{i}}}
  \pi^{\ast}(\diff z_{i}/z_{i})
  =
  w_{i}^{-p_{i}(1-\myfrac{1}{m_{i}})}
  \pi^{\ast}(\diff z_{i}).
\]
Note that if the multiplicities \(m_i\)'s are integers and if the cover \(\pi\) is \textsl{strictly adapted} (i.e. \(p_i=m_i\)), then \(\Omega(\pi,\Delta)\) identifies with \(\Omega_Y\) via the differential map of \(\pi\).

\subsection{Orbifold positivity}
The direct image of the sheaf of \(\Aut(\pi)\)-invariant sections of \(S^N\Omega(\pi,\Delta)\)
\[
  S^{[N]}\Omega(X,\Delta)
  \bydef
  \pi_{\ast}((S^N\Omega(\pi,\Delta)))^{\Aut(\pi)}
  \subseteq
  S^N\Omega_{X}(\log\abs{\Delta}),
\]
is a subsheaf of logarithmic symmetric differentials which does not depend on the choice of \(\pi\).
Note that in almost all situations \(S^{[N]}\Omega(X,\Delta)\neq S^N\Omega(X,\Delta)\).
The sheaves \(S^{[N]}\Omega(X,\Delta)\) are independently defined and cannot be seen as symmetric powers.
One has merely a morphism \(S^pS^{[N]}\Omega(X,\Delta)\to S^{[pN]}\Omega(X,\Delta)\) given by multiplication.
However, the philosophy in the framework of Campana's orbifolds is to study orbifold pairs through adapted covers, and we will.

We would like to relate positivity properties of the orbifold cotangent bundle with some positivity properties of \(\Omega(\pi,\Delta)\), for some adapted cover \(\pi\).
The definition for bigness is quite clear.
\begin{defi}
  We say that \((X,\Delta)\) has a \textsl{big cotangent bundle} if \(\Omega(\pi,\Delta)\) is big for some (hence for all) adapted cover \(\pi\).
  Equivalently, the orbifold cotangent bundle of the pair \((X,\Delta)\) is \textsl{big} if for some/any ample integral divisor \(A\subseteq X\), there exists an integer \(N\) such that
  \(H^0(X,S^{[N]}\Omega(X,\Delta)\otimes A^\vee) \neq \{0\}\).
\end{defi}

To define ampleness, we will use augmented base loci, or rather their natural projections.
In the spirit of~\cite{MU}, in which augmented base loci of vector bundles are studied, we define the orbifold augmented base locus of the cotangent bundle to the pair \((X,\Delta)\), as follows.
Recall that the base locus of a vector bundle \(E\) is defined in~\cite{MU} as
\[
  \Bs(E)
  \bydef
  \left\{x \in X\middle/H^0(X,E) \to E_x \text{ is not surjective}\right\}.
\]
\begin{defi}
  The \textsl{orbifold augmented base locus} of \(\Omega(X,\Delta)\) is
  \[
    \BB_+(\Omega(X,\Delta))
    \bydef
    \bigcap_{p/q\in \Q}\bigcap_{N>0}
    \Bs(S^{[Nq]}\Omega(X,\Delta)\otimes (A^\vee)^{\otimes Np}),
  \]
  for an integral ample divisor \(A\to X\).
\end{defi}

Before proceeding to the definition, observe first the following.
For an adapted cover \(\pi\colon Y\to (X,\Delta)\), we use the notation \(Y'\bydef\P(\Omega(\pi,\Delta))\to Y\).
\begin{prop}
  \label{prop:pi_inv}
  Over $X\setminus \abs{\Delta}$,
  the image of the augmented base locus $\BB_+(\O_{Y'}(1))$ by the natural projection \(Y'\twoheadrightarrow Y\twoheadrightarrow X\) does not depend on \(\pi\). Indeed, it actually coincides with the orbifold augmented base locus \(\BB_+(\Omega(X,\Delta))\vert_{X\setminus\abs\Delta}\).
\end{prop}
\begin{proof}
  \begin{enumerate}
    \item
      We claim that for any adapted cover \(\pi\), in order to compute the augmented base locus of \(\Omega(\pi,\Delta)\), it is sufficient to consider \(\Aut(\pi)\)-invariant sections.

      Notice first that because of the relative ampleness of $\O_{Y'}(1)$, one can assume that the ample line bundle in the definition of $\BB_+(\O_{Y'}(1))$ is the pull-back of an ample line bundle on $X$, and in particular is  invariant under  \(\Aut(\pi)\).
      Then observe that $\BB_+(\O_{Y'}(1))$ is \(\Aut(\pi)\)-invariant.
      Indeed, for any global section \(\sigma\) and for any element of the Galois group \(\alpha\), the Galois transform \(\sigma^\alpha\) is also a global section.
      We deduce that for each orbit of \(\Aut(\pi)\), either all points are in the augmented base locus, or none.

      Let $\BB^G_+(\O_{Y'}(1))$ denote the base locus obtained by considering only \(\Aut(\pi)\)-invariant sections.
      If $v \in \BB_+(\O_{Y'}(1))$, then obviously $v\in\BB^G_+(\O_{Y'}(1))$.
      Conversely, consider $v \not \in \BB_+(\O_{Y'}(1))$. By the preceding considerations, the (finite) orbit of $v$ stays outside $\BB_+(\O_{Y'}(1))$.
      By Noetherianity, $\BB_+(\O_{Y'}(1))$ can be realized as a single base locus.
      One can then find a divisor in the associated linear system that avoids all the points in the orbit of \(v\).
      In other words, one can find a global section \(\sigma\) which does not vanish at any point of the orbit of $v$. Moreover, this section can be made invariant after multiplication by its Galois conjugates. To conclude, $\BB_+(\O_{Y'}(1)) = \BB^G_+(\O_{Y'}(1))$.
    \item
      Now remark that there is a natural morphism $\pi^*S^{[N]}\Omega(X,\Delta) \to S^N (\Omega(\pi,\Delta))$ which is an injection of sheaves and an isomorphism outside
      $\abs{\Delta}$. Combining with the preceding equality of base loci, one obtains that $\BB_+(\O_{Y'}(1))$ has a projection on $X\setminus \abs{\Delta}$ which depends only on the sheaves $S^{[N]}\Omega(X,\Delta)$. Namely (reasoning as in~\cite{MU}), it is the restriction of \(\BB_+(\Omega(X,\Delta))\).
      \qedhere
  \end{enumerate}
\end{proof}

There are many interesting situations where one cannot expect global ampleness of \(\Omega(\pi,\Delta)\) but where bigness is not sufficient for applications (see below). Therefore, we shall introduce an intermediate positivity property.

\begin{defi}
  We say that \((X,\Delta)\) has an \textsl{ample cotangent bundle modulo boundary} if its orbifold augmented base locus is contained in the boundary.
\end{defi}

  Equivalently, \((X,\Delta)\) has an ample cotangent bundle modulo boundary, if for some (hence for all) adapted cover \(\pi\), the orbifold cotangent bundle \(\Omega(\pi,\Delta)\) is ample modulo the \(\Aut(\pi\))-invariant closed subset living over the boundary. This definition will be used in practice.

\begin{rema}
  As a consequence of Proposition~\ref{prop:pi_inv}, the ``ampleness modulo boundary'' of \(\Omega(\pi,\Delta)\) does not depend on \(\pi\).
  Ampleness of orbifold cotangent bundles has been recently studied in the PhD thesis of Tanuj Gomez where it is shown by a different method that for strictly adapted covers ramifying exactly on \(\abs\Delta\), the (global) ampleness of \(\Omega(\pi,\Delta)\) does not depend on the cover.
  It would be interesting to check to which extent ampleness of \(\Omega(\pi,\Delta)\) is equivalent to the triviality of \(H^q(X,S^{[N]}\Omega(X,\Delta)\otimes A^{\otimes p})\), for some \(A\) ample, any \(p,q>0\), and \(N\) large enough.
\end{rema}

\begin{rema}
  In general, one cannot expect that there exists a strictly adapted covering ramifying exactly over the boundary divisor. But if \(\pi\colon Y\to(X,\Delta)\) is a strictly adapted cover ramifying exactly over \(\Delta\), a convenient way to prove that the orbifold cotangent bundle \(\Omega(X,\Delta)\) is ample modulo boundary is to prove that the orbifold cotangent bundle \(\Omega(\pi,\Delta)\simeq\Omega_Y\) is ample modulo its ramification locus and it is actually equivalent.
\end{rema}

\subsection{Obstructions to orbifold positivity}
Positivity of cotangent bundles of projective manifolds or log-cotangent bundles of pairs has been investigated by many authors (see \textit{e.g.} \cite{Deb05,Xie18,BDa18,Den20,CR20,Etesse,Nog86,BDe18}). In the orbifold setting, much less seems to be known. Nevertheless, results of \cite{Sommese} can be interpreted as the study of ampleness of orbifold cotangent bundles associated to orbifolds $(\P^2, \Delta)$ corresponding to arrangements of lines in $\P^2$. In particular, \cite[Theo.~4.1]{Sommese} characterizes exactly which arrangements have ample orbifold cotangent bundles. An interesting consequence of this result is that when the orbifold $(\P^2, \Delta)$ is smooth (i.e. when the lines are in general position), the orbifold cotangent bundle is \emph{never} ample.
This is due to the following fact. Let $C$ be any irreducible component of $\pi^{-1}(\abs{\Delta})$ then ${\Omega_Y}_{|C} \cong \Omega_C \oplus N_C^*$ (\cite[p.~217]{Sommese}), and $\deg N_C^*=-C^2 \leq 0$.
In other words, each component of the boundary carries a negative quotient.

This can be generalized as follows.
\begin{lemm}
  Let \((\P^n,\Delta)\) be a smooth orbifold pair with integer (or infinite) coefficients. Then, for any strictly adapted covering \(\pi\) the cotangent bundle \(\Omega(\pi,\Delta)\) has negative quotients supported on each boundary component with finite multiplicity, and trivial quotients supported on each boundary component with infinite multiplicity.
\end{lemm}
\begin{proof}
  Let \(\Delta=(1-1/m_1)\Delta_1+\Delta'\), where the multiplicity of \(\Delta_1\) in \(\Delta'\) is zero.

  If \(m_1=\infty\), the residue exact sequence
  \(
  \Omega(\pi,\abs{\Delta'})
  \hookrightarrow
  \Omega(\pi,\abs{\Delta})
  \twoheadrightarrow
  \O_{\pi^\ast\Delta_1}
  \)
  restricts to
  \[
    \Omega(\pi,\Delta')
    \hookrightarrow
    \Omega(\pi,\Delta)
    \twoheadrightarrow
    \O_{\pi^\ast\Delta_1}.
  \]
  We get the sought trivial quotient on \(\abs{\pi^\ast\Delta_1}\)

  If \(m_1<\infty\), let \(D_1\bydef\myfrac{\pi^{\ast}\Delta_{1}}{m_{1}}\). Note that this is a reduced divisor. By~\eqref{eq:orbi_cotangent}, one has:
  \[
    \Omega(\pi,\Delta)
    \hookrightarrow
    \Omega(\pi,\abs{\Delta})
    \twoheadrightarrow
    \O_{D_1}
    \oplus
    \bigoplus_{i\in I\colon m_{i}<\infty}
    \O_{\myfrac{\pi^{\ast}\Delta_{i}'}{m_{i}}},
  \]
  and
  \[
    \Omega(\pi,\Delta')
    \hookrightarrow
    \Omega(\pi,\abs{\Delta})
    \twoheadrightarrow
    \O_{m_1D_1}
    \oplus
    \bigoplus_{i\in I\colon m_{i}<\infty}
    \O_{\myfrac{\pi^{\ast}\Delta_{i}'}{m_{i}}}.
  \]
  One infers
  \[
    \Omega(\pi,\Delta')
    \hookrightarrow
    \Omega(\pi,\Delta)
    \twoheadrightarrow
    \O_{m_1D_1}
    \diagup
    \O_{D_1}.
  \]
  Let \(\mathcal{I}\) denote the ideal sheaf of \(D_1\) in \(Y\).
  The quotient above is isomorphic to \(\mathcal{I}\diagup\mathcal{I}^{m_1}\). Composing with the quotient \(\mathcal{I}/\mathcal{I}^{m_1}\twoheadrightarrow \mathcal{I}/\mathcal{I}^2\simeq \mathcal N_{D_1}^*\), we deduce that \(\Omega(\pi,\Delta)\) has a negative quotient supported on \(\abs{D_1}\) (and namely the conormal bundle of \(D_1\)).
\end{proof}

Therefore, starting with smooth orbifold pairs associated to hyperplane arrangements in projective spaces, the best one can hope for is ampleness modulo the boundary.