# Determination of Hilbert modular forms using squarefree coefficients

Rishabh Agnihotri<EMAIL_ADDRESS>IISc, Bangalore  and
Krishnarjun Krishnamoorthy<EMAIL_ADDRESS>Beijing Institute of
Mathemtical Sciences and Applications (BIMSA), No. 544, Hefangkou Village,
Huaibei Town, Huairou District, Beijing.

###### Abstract.

Let $F$ (over $\mathbb{Q}$) be a totally real number field of narrow class
number $1$. We generalize a result of Kohnen on the determination of half
integral weight modular forms by their Fourier coefficients supported on
squarefree (algebraic) integers. We also give a soft proof that infinitely
many Fourier coefficients supported on squarefree integers are non-vanishing.

###### Key words and phrases:

Half-integral weight Hilbert modular forms, Determination, Central values of
twists, Shimura correspondence

###### 2020 Mathematics Subject Classification:

11F41, 11F37, 11F27

##  1\. Introduction

Modular forms have established themselves as central objects of investigation
in number theory due to the arithmetic nature of their “Fourier coefficients”.
Understanding the various properties of these Fourier coefficients comprises a
significant part of modern day research. While it is clear that the entire
collection of Fourier coefficients uniquely determine a modular form, it is
interesting to ask for a “minimal” set of Fourier coefficients that would
uniquely determine a modular form. Finding sharp answers to this question
takes a particularly interesting turn in the context of half-integral weight
modular forms.

Half-integral weight modular forms are analogues of the classical modular
forms whose weight is a half-integer, prototypical examples being
$\theta$-series of various kinds. There are two important developments in this
theory that are relevant to this paper. The first one is the Shimura
correspondence and the second one is the Waldspurger’s formula. Both these
results provide (in a pleasant complementary fashion) a bridge between the
half-integral realm and the realm of integral weight modular forms where more
tools and techniques are available.

The Shimura correspondence reduces the study of half-integral weight modular
forms to those Fourier coefficients supported on squarefree algebraic
integers. The other coefficients are related to those of the Shimura lift in
an explicit fashion. A deeper relation between the Fourier coefficients
supported at squarefree integers and the Shimura lift is given by the
Waldspurger formula. Therefore philosophically, we expect the squarefree
coefficients to carry all the information required to uniquely determine $f$.
It is then natural to ask for a rigorous formulation of this expectation.
Initial progress in this direction was due to Kohnen [Koh92].

######  Theorem 1 (Kohnen).

Let $f,g$ be two non-zero Hecke eigenforms in $S_{k+\frac{1}{2}}^{+}(4)$ with
Fourier coefficients $a(n)$ and $b(n)$ respectively and suppose that
$a(|D|)=b(|D|)$ for all fundamental discriminants $D$ such that $(-1)^{k}D>0$.
Furthermore suppose that $\lambda_{2}=\mu_{2}$, where $\lambda_{2}$
(respectively $\mu_{2}$) denote the eigenvalues of $f$ (respectively $g$)
under the Hecke operator $T_{k+\frac{1}{2}}^{+}(4)$. Then $f=g$.

Kohnen mentions in [Koh92] that the assumption on the $\lambda_{2},\mu_{2}$
maybe removed; he writes “We expect that the additional condition on
$\lambda_{2}$, in fact, is not necessary, but so far we cannot prove this”.
Modulo some technical subtleties, Kohnen’s key idea is the fact that the
functional equations of the natural Dirichlet series associated to a half-
integral weight form and its Shimura lift have incompatible symmetries, but
for the factors arising from the squarefree coefficients. Thus without the
contribution of the squarefree coefficients, these incompatibilities maybe
utilized to our avail. This observation also underlies the proof of our main
theorem (Theorem 3 below). Kohnen treated a somewhat restricted case (of Hecke
eigenforms in the plus space corresponding to the full level) but the methods
are robust enough to be applied generally.

It is very convenient and quite tempting to restrict attention to newforms
residing in the Kohnen plus space primarily because of the existence of a
newform theory in this space and Kohnen’s result which states that the
newforms in the plus space is isomorphic to the space of integral weight
newforms under the Shimura correspondence. In this light, the problem of
determining half integral weight forms by their squarefree coefficients is
connected to determining integral weight newforms by the central values of the
$L$ functions of their twists by quadratic characters, thanks to the
Waldspurger’s formula111The determination using central values is a much
general result as the Waldspurger formula does not take into account the sign
of the Fourier coefficient of the half-integral weight form.. In this
direction, we have the following result of Luo-Ramakrishnan [LR97].

######  Theorem 2 (Luo-Ramakrishnan).

Let $f,g$ be normalized newforms in $S_{2k}(N),S_{2m}(N^{\prime})$
respectively. Suppose that there is a constant $C$ such that

$L\left(\frac{1}{2},f\otimes\chi_{d}\right)=CL\left(\frac{1}{2},g\otimes\chi_{d}\right)$

for almost all primitive quadratic characters $\chi_{d}$ of conductor $d$
prime to $NN^{\prime}$, then $k=m$, $N=N^{\prime}$ and $f=Cg$.

This result has been generalized in many directions (see [GHS09], [GMP21],
[HT17], [Mun10], [MS15a], [MS15b], [Pi14]). We remark that Theorem 2 allows us
to compare forms of varying weights and levels. This feature is not present in
Theorem 1. Here and henceforth we consider Hilbert modular forms over a
totally real number field $F$ of narrow class number $1$. The purpose of this
paper is to prove two results regarding the determination of half integral
weight Hilbert modular forms by their Fourier coefficients supported on
squarefree integers.

######  Theorem 3.

Suppose that $f$ and $g$ are half-integral weight cuspidal Hecke eigenforms of
varying weights and levels. Denote the normalized Fourier coefficients (see
(2.9)) of $f,g$ as $\lambda_{f}$ and $\lambda_{g}$ respectively. Suppose there
exists $\kappa\neq 0$ such that

(1.1) $\lambda_{f}(\tau)=\kappa\lambda_{g}(\tau)$

for every squarefree $\tau\in\mathcal{O}_{F}$. Then $f=\kappa g$.

Theorem 3 can be seen as an intermediate result between Theorem 1 and Theorem
2 in that, we allow for the flexibility of varying weights and levels, but
still require an equality between the Fourier coefficients themselves and not
just an equality between their sizes. Furthermore we require (1.1) to hold for
every squarefree coefficient, and not “almost all”. It is unclear to us (and
rather unlikely) if the present methods maybe generalized to remove the above
shortcomings.

It is desirable and often quite useful to obtain results which allow us to
“effectively” determine the modular form. This amounts to a finite number of
conditions (as opposed to the requirement that (1.1) hold for every squarefree
integer). In the case of Theorem 2, this problem was resolved by Munshi
[Mun10]. We present below a soft result in this direction in our setting.

######  Theorem 4.

Suppose $f$ is a non-zero Hecke eigenform. Then

$\underset{N(\tau)<T,\ \tau\
\mathrm{sq.free.}}{\limsup_{T\to\infty}}|\lambda_{f}(\tau)|\gg_{f,F}1.$

Theorem 4 is slightly different from the $\Omega$ results obtained in [GK19]
and [Das20] in that we restrict ourselves to squarefree integers. It is an
interesting problem to show that the lower bound above is infact $\infty$;
that is to say that $\limsup\\{|\lambda_{f}(\tau)|\\}=\infty$. This would
provide further credence to the generalization of Ramanujan conjecture as
stated in (2.11) below. A recent result in this direction is available in
[GKS20].

Theorem 4 is essentially a consequence of the Rankin-Selberg theory. The proof
of Theorem 4 can be fine tuned to give an upper bound on the least squarefree
$\tau$ such that $|\lambda_{f}(\tau)|\neq 0$. This would amount to keeping
track of the error term in the Rankin-Selberg estimate (2.14).

The assumption of $F$ having narrow class number $1$ is made partly out of
necessity and partly for convenience. Many parts of the proof can be modified
with the weaker requirement that the discriminant of $F$ be a principal ideal,
along with some other minor assumptions. We may further weaken our assumptions
if we restrict to parallel weight forms. We feel that this setup best
demonstrates the robustness of the new ideas incorporated into the proof of
Theorem 3.

The authors would like to thank Winfriedn Kohnen for his encouragement and
comments.

##  2\. Preliminaries

###  2.1. Notation

We let $F$ be a totally real extension of $\mathbb{Q}$ of degree $r$ and of
narrow class number $1$. The various embeddings of $F$ into $\mathbb{R}$ will
be labeled $\\{\sigma_{i}\\}_{i=1}^{r}$. For any $\sigma_{i}$ and $\xi\in F$,
it will also be convenient to denote $\sigma_{i}(\xi)$ as $\xi_{i}$. Let
$F^{+}$ denote the totally positive elements of $F$ and for any subset $S$ of
$F$, the super script $+$ will be used to denote the totally positive elements
in $S$. That is $S^{+}:=S\cap F^{+}$. For any $\xi\in F$, the membership in
$F^{+}$ will be denoted by $\xi\gg 0$. We shall denote the ring of integers of
$F$ as $\mathcal{O}_{F}$ and it’s units as $U$. The different ideal of $F$
will be denoted by $\mathfrak{d}$ generated by $\delta\in\mathcal{O}_{F}$ and
the discriminant of $F$ over $\mathbb{Q}$ will be denoted as $D_{F}$. Since we
have assumed that $F$ has trivial narrow class group, every fractional ideal
of $F$ has a totally positive generator and the totally positive units are
squares; that is $U^{+}=\\{u^{2}\ |\ u\in U\\}$.

We adopt the following multi-index notation. We shall embedd
$F\hookrightarrow\mathbb{R}^{r}\hookrightarrow\mathbb{C}^{r}$ via its various
embeddings $\\{\sigma_{i}\\}$. We shall also identify
$\mathbb{C}\hookrightarrow\mathbb{C}^{r}$ via the diagonal embedding. Addition
and multiplication in $\mathbb{C}^{r}$ is point-wise. Elements of
$\mathbb{C}^{r}$ will generally be denoted by boldface letters, for example
$\textbf{x},\ \textbf{y},\ \textbf{z}$ etc. For
$\textbf{w}=(w_{1},\ldots,w_{r}),\textbf{z}=(z_{1},\ldots,z_{r})\in\mathbb{C}^{r}$
we let $\textbf{w}\cdot\textbf{z}\in\mathbb{C}$ be the sum
$\sum_{i}w_{i}z_{i}$. For $\textbf{z}=(z_{1},\ldots,z_{r})\in\mathbb{C}^{r}$
and $\textbf{t}=(t_{1},\ldots,t_{r})\in(\mathbb{C})^{r}$, we define
$\textbf{z}^{\textbf{t}}:=z_{1}^{t_{1}}\ldots z_{r}^{t_{r}}$. In the text, we
shall take care that the exponentiation is unambiguous.

Even though we have assumed the narrow class number of $F$ to be equal to $1$,
in some instances it is convenient to consider integral ideals of
$\mathcal{O}_{F}$ rather than the algebraic integers themselves. We shall
freely move between one setting and the other as our requirements may be. We
warn the reader that in many cases, while working with integers in
$\mathcal{O}_{F}$, we implicitly work modulo the unit group. We hope that this
does not lead to any confusion.

Standard references for the results that follow include [Gar90], [Shi78],
[Shi87], [Shi93].

###  2.2. Hilbert modular forms

A weight k is an element of $(\frac{1}{2}\mathbb{Z})^{r}\subset\mathbb{C}^{r}$
of the form

(2.1)
$\textbf{k}=\textbf{m}_{\textbf{k}}+\delta_{\textbf{k}}\left(\frac{1}{2},\ldots,\frac{1}{2}\right),$

where $\textbf{m}_{\textbf{k}}\in(\mathbb{Z})^{r}$ and
$\delta_{\textbf{k}}\in\\{0,1\\}$. The theta series associated to $F$ is
defined as

(2.2) $\theta_{F}(\textbf{z}):=\sum_{v\in\mathcal{O}_{F}}e^{\pi
iv^{2}\cdot\textbf{z}}.$

This is a holomorhpic function on the generalized upper half plane
$\mathcal{H}^{r}$, and is modular with respect to the group

(2.3) $\textbf{D}:=\left\\{\gamma:=\begin{pmatrix}a_{\gamma}&b_{\gamma}\\\
c_{\gamma}&d_{\gamma}\end{pmatrix}\
\Bigg{|}a_{\gamma},d_{\gamma}\in\mathcal{O}_{F},b_{\gamma}\in
2\mathfrak{d}^{-1},c_{\gamma}\in 2\mathfrak{d},\det(\gamma)=1\right\\}.$

For $\gamma\in\textbf{D}$ and $\textbf{z}\in\mathcal{H}^{r}$, define

(2.4)
$h(\gamma,\textbf{z}):=\frac{\theta_{F}\left(\gamma\cdot\textbf{z}\right)}{\theta_{F}(\textbf{z})}.$

Furthermore, for $\gamma\in SL_{2}(F)$ we define
$j\left(\gamma,z\right)=c_{\gamma}z+d_{\gamma}$ and let
$j(\gamma,\textbf{z})=\left(j(\sigma_{i}(\gamma),z_{i})\right)\in\mathbb{C}^{r}$.
A Hilbert modular cusp form of weight k for a congruence subgroup $\Gamma$ is
a holomorphic function $f:\mathcal{H}^{r}\to\mathbb{C}$ such that

  1. (1)

$f(\gamma\textbf{z})=h(\gamma,\textbf{z})^{\delta_{\textbf{k}}}j(\gamma,\textbf{z})^{\textbf{m}_{\textbf{k}}}f(\textbf{z})$
for every $\textbf{z}\in\mathcal{H}^{r}$ and $\gamma\in\Gamma$,

  2. (2)

$f$ vanishes at all the cusps of $\Gamma$.

We understand to allow $\delta_{\textbf{k}}=1$ only when
$\Gamma\subseteq\textbf{D}$. Let $\Lambda$ be the collection of all $d\in F$
such that $\left(\begin{smallmatrix}1&d\\\
&1\end{smallmatrix}\right)\in\Gamma$. Then $f$ has a “Fourier expansion” given
by

$f(\textbf{z})=\sum_{\xi\in\Lambda^{\vee}}a_{f}(\xi)e^{2\pi
i\xi\cdot\textbf{z}}$

where $\Lambda^{\vee}$ denotes the dual of $\Lambda$ given by $\\{\alpha\in F\
|\ \alpha\Lambda\subseteq\mathcal{O}_{F}\\}$. The vanishing of $f$ at the
cusps of $\Gamma$ implies that the Fourier expansion is supported only on
totally positive elements $\xi$. We shall restrict our choices further so that
the Fourier expansion is of the form

(2.5)
$f(\textbf{z})=\sum_{\xi\in\mathcal{O}_{F}^{+}}a_{f}(\xi)e^{(2-\delta_{\textbf{k}})\pi
i\xi\cdot\textbf{z}}.$

This corresponds to conventional choices of congruence subgroups in the
integral and half-integral case.

We may embedd the unit subgroup $U$ inside $SL_{2}(\mathcal{O}_{F})$ as
$u\mapsto\left(\begin{smallmatrix}u&\\\ &u^{-1}\end{smallmatrix}\right)$ and
by abuse of notation, denote the image as $U$. For a congruence subgroup
$\Gamma$, we let $U_{\Gamma}:=U\cap\Gamma$, which is in particular a finite
index subgroup of $U$. In the remainder of this paper, we shall choose
congruence subgroups $\Gamma$ such that $U_{\Gamma}=U$. In particular, we
define

(2.6) $\Gamma_{0}(n):=\left\\{\gamma:=\begin{pmatrix}a_{\gamma}&b_{\gamma}\\\
c_{\gamma}&d_{\gamma}\end{pmatrix}\
\Bigg{|}a_{\gamma},d_{\gamma}\in\mathcal{O}_{F},b_{\gamma}\in
2\mathfrak{d}^{-1},c_{\gamma}\in 2^{-1}n\mathfrak{d},\det(\gamma)=1\right\\}.$

We shall say that $f$ is of level $n$ if it is a modular form for the group
$\Gamma_{0}(n)$; we shall implicitly require that $4|n$.

There is a commuting family of Hecke operators (denoted by $T_{\mathfrak{n}}$)
indexed by the integral ideals $\mathfrak{n}$ of $\mathcal{O}_{F}$, which act
on the space of modular forms that we are interested in. A cusp form $f$ of
weight k will be called a Hecke eigenform if it is an eigenvector for
$T_{\mathfrak{n}^{1+\delta_{k}}}$ for all integral ideals $\mathfrak{n}$. We
shall also suppose that Hecke eigenforms $f$ are normalized so that
$T_{\mathcal{O}_{F}}f=f$ and denote the $\mathfrak{p}$-th eigenvalue as
$\omega_{\mathfrak{p}}$, that is
$T_{\mathfrak{p}^{1+\delta_{k}}}f=\omega_{\mathfrak{p}}f$.

###  2.3. The Dirichlet series associated to $f$

Suppose that $f$ is a modular form of weight k with respect to some congruence
subgroup $\Gamma$. Furthermore suppose that $f$ is a Hecke eigenform for all
the Hecke operators with system of eigenvalues given by
$\\{\omega_{\mathfrak{n}}\\}$. Then for any $u\in U_{\Gamma}$,

(2.7) $a_{f}(\xi u^{2})=u^{\textbf{m}}a_{f}(\xi).$

In particular, we may define the $L$ function associated to $f$ as

(2.8)
$L(s,f):=\sum_{\xi\in\mathcal{O}_{F}^{+}/U_{\Gamma}^{+}}\frac{\lambda_{f}(\xi)}{\xi^{s}}$

where

(2.9) $\lambda_{f}(\xi):=a_{f}(\xi)\xi^{-\frac{\textbf{k}-1}{2}}.$

It is easy to see that this is well-defined. As in the classical case (see
[Gar90, Section 1.7]), it can be shown that Fourier coefficients $a_{f}(\xi)$
satisfy the “Hecke bound”

(2.10)
$a_{f}(\xi)\xi^{-\frac{\textbf{k}-1}{2}}\ll_{\epsilon}N(\xi)^{\frac{1}{2}+\epsilon}$

so that $L(s,f)$ is absolutely convergent for $\Re(s)>\frac{3}{2}$. It seems
reasonable to expect (see [GKS20]) that the Ramanujan conjecture in this case
would be the bound

(2.11)
$a_{f}(\xi)\xi^{-\frac{\textbf{k}-1}{2}}\ll_{\epsilon}N(\xi)^{\epsilon}.$

We remark here that if $U_{\Gamma}=U$, for an integral ideal $\mathfrak{n}$
with a totally positive generator $n$, the definition
$\lambda_{f}(\mathfrak{n}):=\lambda_{f}(n)$ is well-defined. In this fashion,
we may rewrite $L(s,f)$ as a sum indexed by the integral ideals of
$\mathcal{O}_{F}$.

###  2.4. The Shimura lift

For a half integral weight Hilbert modular form of weight k as above, we may
associate an integral weight Hilbert modular form $\mathsf{f}$ of weight
$2\textbf{m}$. More precisely, given a totally positive squarefree element
$\tau$, let $\chi_{\tau}$ denote the Hecke character associated to the
quadratic extension $F(\sqrt{\tau})/F$. Then the Shimura correspondence
asserts that there exists a modular form of weight $2\textbf{m}$ (say
$\mathsf{f}_{\tau}$) whose Fourier coefficients are described formally as

(2.12) $\underset{\xi\neq
0}{\sum_{\xi\in\mathcal{O}_{F}/U_{\Gamma}}}c(\xi,\mathsf{f}_{\tau})M(\xi)=\left(\underset{\xi\neq
0}{\sum_{\xi\in\mathcal{O}_{F}/U_{\Gamma}}}a_{f}(\tau\xi^{2})\xi^{-\textbf{m}}M(\xi)\right)\left(\underset{\xi\neq
0}{\sum_{\xi\in\mathcal{O}_{F}/U_{\Gamma}}}\frac{\chi_{\tau}(\xi)M(\xi)}{N(\xi)}\right)\\\
=a_{f}(\tau)\prod_{\mathfrak{p}}\left(1-\omega_{\mathfrak{p}}M(\mathfrak{p})+\frac{M(\mathfrak{p}^{2})}{N(\mathfrak{p})}\right)^{-1}$

where $M(\xi)=M(\xi\mathcal{O}_{F})$ is a formal symbol on integral ideals
such that $M(\xi_{1}\xi_{2})=M(\xi_{1})M(\xi_{2})$ and the product over
$\mathfrak{p}$ is over all the prime ideals of $\mathcal{O}_{F}$. The second
equality is valid only if $f$ is a Hecke eigenform (in which case $\mathsf{f}$
is also a Hecke eigenform). In this case $\mathsf{f}_{\tau}\not\equiv 0$ if
and only if $a_{f}(\tau)\neq 0$. Moreover, whenever $a_{f}(\tau)\neq 0$, the
modular form $\mathsf{f}_{\tau}a_{f}(\tau)^{-1}$ is independent of the choice
of $\tau$. We shall denote this form as $\mathsf{f}$ and call it the Shimura
lift of $f$. Henceforth, we shall normalize Hecke eigenforms so that their
first Fourier coefficient, that is $\lambda_{\mathsf{f}}(\mathcal{O}_{F})$,
equals unity.

###  2.5. Rankin-Selberg theory

The Rankin-Selberg $L$ function of two half integral weight forms $f,g$
(modular with respect to congruence subgroups $\Gamma_{1},\Gamma_{2}$
respectively) is defined as

(2.13) $L(s,f\times
g)=\sum_{\xi\in\mathcal{O}_{F}^{+}/U_{\Gamma}^{+}}\frac{\lambda_{f}(\xi)\overline{\lambda_{g}(\xi)}}{N(\xi)^{s}}$

where $\Gamma=\Gamma_{1}\cap\Gamma_{2}$. The series is absolutely convergent
for $\Re(s)\gg 1$ and continues to a meromorphic function with a possible pole
at $s=1$ [Shi87]. In particular, if $f=g$, then $L(s,f\times f)$ has a simple
pole at $s=1$ with a positive residue. From a standard Mellin inversion
argument, we can deduce the Rankin-Selberg estimate; as $T\to\infty$, we have

(2.14) $\underset{N(\xi)\leqslant
T}{\sum_{\xi\in\mathcal{O}_{F}^{+}/U_{\Gamma}^{+}}}\left|\lambda_{f}(\xi)\right|^{2}\sim\mathrm{Res}_{s=1}L(s,f\times
f)T.$

##  3\. Functional equation

###  3.1. The Fricke involution

Recall the different ideal $\mathfrak{d}$ of $F$ is generated by $\delta$.
Following [AS08], we introduce the Fricke involution in our setting. Since,

(3.1)
$\theta_{F}\left(\textbf{z}\right)=(-\textbf{iz})^{-\frac{1}{2}}D_{F}^{-\frac{1}{2}}\theta_{F}\left(-\frac{1}{\delta^{2}\textbf{z}}\right),$

we can extend the definition of $h(\gamma,\textbf{z})$ as

(3.2) $h\left(\begin{pmatrix}0&&-\delta^{-1}\\\
\delta&&0\end{pmatrix},\textbf{z}\right):=(-\textbf{iz})^{\frac{1}{2}}D_{F}^{\frac{1}{2}}.$

Suppose $n\in\mathcal{O}_{F}^{+}$. Define the $W(n)$ operator as

(3.3) $W(n):=\left\\{\begin{pmatrix}0&-2\delta^{-1}\\\ 2^{-1}\delta
n&0\end{pmatrix},h(W(n),\textbf{z})\right\\}=\left\\{\begin{pmatrix}0&-2\delta^{-1}\\\
2^{-1}\delta
n&0\end{pmatrix},(-\textbf{iz})^{\frac{1}{2}}\frac{D_{F}^{\frac{1}{2}}N(n)^{\frac{1}{4}}}{2^{\frac{r}{2}}}\right\\}.$

Let $\chi_{n}$ denote the Hecke character associated to the quadratic
extention $F(\sqrt{n})$ over $F$ as above. If $n$ is a perfect square in $F$,
then we shall take $\chi_{n}$ to be trivial.

######  Lemma 1.

If $n$ is a totally positive integer and $f\in S_{\textbf{k}}(\Gamma_{0}(n))$,
then $f|_{W(n)}\in
S_{\textbf{k}}(\Gamma_{0}(n),\chi_{n}^{\delta_{\textbf{k}}})$.

###### Proof.

For ease of notation, let us write $W$ for $W(n)$. It is enough to verify the
transformation property of $f|_{W}$, that is

$\left(f|_{W}\right)|_{\gamma}=\chi_{n}^{\delta_{\textbf{k}}}(a_{\gamma})f|_{W}$

for every $\gamma=\left(\begin{smallmatrix}a_{\gamma}&b_{\gamma}\\\
c_{\gamma}&d_{\gamma}\end{smallmatrix}\right)\in\Gamma_{0}(n)$. For such a
$\gamma$, we have

$W\gamma W^{-1}=\begin{pmatrix}d_{\gamma}&-2^{2}\delta^{-2}n^{-1}c_{\gamma}\\\
-2^{-2}\delta^{2}nb_{\gamma}&a_{\gamma}\end{pmatrix}=:\gamma^{\prime}\in\Gamma_{0}(n).$

Then it follows that

$f|_{W}|_{\gamma}(\textbf{z})=h(\gamma,\textbf{z})^{-\delta_{\textbf{k}}}j(\gamma,\textbf{z})^{-\textbf{m}}h(W,\gamma\textbf{z})^{-\delta_{\textbf{k}}}j(W,\gamma\textbf{z})^{-\textbf{m}}h(\gamma^{\prime},W\textbf{z})^{\delta_{\textbf{k}}}j(\gamma^{\prime},W\textbf{z})^{\textbf{m}}h(W,\textbf{z})^{\delta_{\textbf{k}}}j(W,\textbf{z})^{\textbf{m}}f|_{W}(\textbf{z}).$

Thus, it suffices to show that

$h(\gamma,\textbf{z})^{-\delta_{\textbf{k}}}j(\gamma,\textbf{z})^{-\textbf{m}}h(W,\gamma\textbf{z})^{-\delta_{\textbf{k}}}j(W,\gamma\textbf{z})^{-\textbf{m}}h(\gamma^{\prime},W\textbf{z})^{\delta_{\textbf{k}}}j(\gamma^{\prime},W\textbf{z})^{\textbf{m}}h(W,\textbf{z})^{\delta_{\textbf{k}}}j(W,\textbf{z})^{\textbf{m}}=\chi_{n}^{\delta_{\textbf{k}}}(a_{\gamma})$

Since the $j$ function satisfies the cocycle condition, we have

$j(\gamma^{\prime},W\textbf{z})^{\textbf{m}}j(W,\textbf{z})^{\textbf{m}}=j(\gamma,\textbf{z})^{\textbf{m}}j(W,\gamma\textbf{z})^{\textbf{m}}.$

This completes the proof when $\delta_{\textbf{k}}=0$. If
$\delta_{\textbf{k}}=1$, the verification follows from [AS08, (4.0.1)]. ∎

Following the above strategy, we may show that the $W(n)$ operator commutes
with all the Hecke operators away from $n$ (see [AS08, Lemma 4.1]). In
particular, if $f$ is a Hecke eigenform, then so is $f|_{W(n)}$. Furthermore,
using the strong multiplicity one theorem for $GL(2)$, we can conclude that
the Shimura lifts of $f$ and $f|_{W(n)}$ coincide.

######  Lemma 2.

If we define

$f|_{W^{\prime}(n)}:=\textbf{i}^{\textbf{m}}n^{\frac{\textbf{m}}{2}}f|_{W(n)},$

then, $f|_{W^{\prime}(n)}|_{W^{\prime}(n)}=f$.

###### Proof.

Follows by direct computation. ∎

######  Theorem 5.

Suppose $f$ is a half integral weight cusp form of weight k and level $n$.
Then,

  1. (1)

$L(s,f)$ is absolutely convergent for $\Re(s)>1$,

  2. (2)

continues analytically to the whole complex plane and satisfies the functional
equation

$\Lambda(s,f)=\Lambda(1-s,f|_{W^{\prime}(n)})$

where

$\Lambda(s,f):=D_{F}^{s}N(n)^{\frac{s}{2}}(2\pi)^{-rs}\prod_{j=1}^{r}\Gamma\left(s+\frac{k_{j}-1}{2}\right)L(s,f).$

###### Proof.

Let us denote the abscissa of convergence of $L(s,f)$ as $\mathfrak{a}_{f}$.
From Cauchy-Schwartz inequality and (2.14),

(3.4) $\underset{T\leqslant N(\xi)\leqslant
2T}{\sum_{\xi\in\mathcal{O}_{F}^{+}/U_{\Gamma}^{+}}}\frac{\left|\lambda_{f}(\xi)\right|}{\xi^{\sigma}}\ll_{f}T^{1-\sigma}$

In particular, if $\sigma>1$, then

$\underset{N(\xi)\leqslant
2^{n}}{\sum_{\xi\in\mathcal{O}_{F}^{+}/U_{\Gamma}^{+}}}\frac{\left|\lambda_{f}(\xi)\right|}{\xi^{\sigma}}\ll_{f}\frac{1}{1-2^{1-\sigma}}$

Thus we may choose $\sigma=1+\epsilon$ for any positive $\epsilon$ and hence
conclude that $L(s,f)$ is convergent for $\Re(s)>1$. Thus
$\mathfrak{a}_{f}\leqslant 1$.

We next prove the analytic continuation and functional equation. Set
$T:=(\mathbb{R}^{+})^{r}$ and we may identify the totally positive elements
$F^{+}\hookrightarrow T$ via its embeddings. From the unit theorem,
$U^{+}\hookrightarrow T$ is the image of a degree $r-1$ lattice. We start with
the integral

(3.5)
$I(s):=\int\limits_{T/U_{\Gamma}^{+}}f(\textbf{iy})\textbf{y}^{s+\frac{\textbf{k}-1}{2}}\frac{d\textbf{y}}{\textbf{y}}.$

This is well defined from the arguments in §2.3. Furthermore the exponential
decay of $f$ at the cusps ensures that the integral is convergent (and defines
an analytic function) for $\Re(s)\gg 1$. Because of absolute convergence, for
$\Re(s)$ large enough, we have

$\displaystyle I(s)$
$\displaystyle=\int\limits_{T/U_{\Gamma}^{+}}\sum_{\xi\in\mathcal{O}_{F}^{+}}a_{f}(\xi)e^{-\pi\xi\cdot\textbf{y}}\textbf{y}^{s+\frac{\textbf{k}-1}{2}}\frac{d\textbf{y}}{\textbf{y}}$
$\displaystyle=\int\limits_{T}\sum_{\xi\in\mathcal{O}_{F}^{+}/U_{\Gamma}^{+}}a_{f}(\xi)e^{-\pi\xi\cdot\textbf{y}}\textbf{y}^{s+\frac{\textbf{k}-1}{2}}\frac{d\textbf{y}}{\textbf{y}}$
(3.6)
$\displaystyle=(\pi)^{-rs-\frac{\textbf{k}-1}{2}}\prod_{j=1}^{r}\Gamma\left(s+\frac{k_{j}-1}{2}\right)L(s,f).$

We break the integration into two parts. Suppose
$\textbf{y}=(y_{1},\ldots,y_{r})$. We have

$I(s)=\int\limits_{\prod_{i}y_{i}\geqslant\beta}+\int\limits_{\prod_{i}y_{i}<\beta}=:I_{1}(s)+I_{2}(s).$

where $\beta:=\frac{2^{r}}{D_{F}\sqrt{N(n)}}>0$. The first integral is
convergent for all $s\in\mathbb{C}$. So we focus on the second integral.
Changing the variable $\textbf{w}=(w_{1},\ldots,w_{r})$ such that
$4=\delta_{i}^{2}n_{i}y_{i}w_{i}$, we have

$I_{2}(s)=\int\limits_{\prod_{i}w_{i}\geqslant\beta}\left(\frac{4}{\delta^{2}n\textbf{w}}\right)^{s+\frac{\textbf{k}-1}{2}}f\left(\frac{-4}{\delta^{2}n\textbf{iw}}\right)\frac{d\textbf{w}}{\textbf{w}}.$

We observe that

$f\left(\frac{-4}{\delta^{2}n\textbf{iw}}\right)=\left(\frac{D_{F}^{2}N(n)}{4^{r}}\right)^{\frac{1}{4}}\left(\frac{\delta
n\textbf{iw}}{2}\right)^{\textbf{m}}\textbf{w}^{\frac{1}{2}}f|_{W}(\textbf{iw}).$

Therefore the previous integral becomes

$\displaystyle I_{2}(s)$
$\displaystyle=\left(\frac{D_{F}^{2}N(n)}{4^{r}}\right)^{\frac{1}{4}}\int\limits_{\prod_{i}w_{i}\geqslant\beta}f|_{W}(\textbf{iw})\textbf{w}^{\frac{1}{2}}\left(\frac{\delta
n\textbf{iw}}{2}\right)^{\textbf{m}}\left(\frac{4}{\delta^{2}n\textbf{w}}\right)^{s+\frac{\textbf{k}-1}{2}}\frac{d\textbf{w}}{\textbf{w}}$
$\displaystyle=\textbf{i}^{\textbf{m}}\left(\frac{2}{\delta\sqrt{n}}\right)^{2s-1}n^{\frac{\textbf{m}}{2}}\int\limits_{\prod_{i}w_{i}\geqslant\beta}f|_{W}(\textbf{iw})\textbf{w}^{\frac{\textbf{k}+1}{2}-s}\frac{d\textbf{w}}{\textbf{w}}.$

Observing that $f|_{W}$ is a cusp form, we may conclude that $I_{2}(s)$ is
holomorphic on the whole complex plane. This makes $I(s)$ an analytic function
on the whole complex plane. In order to prove the functional equation, we
rewrite things in terms of the $W^{\prime}$ operator;

$I_{2}(s)=\left(\frac{2}{\delta\sqrt{n}}\right)^{2s-1}\int\limits_{\prod_{i}w_{i}\geqslant\beta}f|_{W^{\prime}}(\textbf{iw})\textbf{w}^{\frac{\textbf{k}+1}{2}-s}\frac{d\textbf{w}}{\textbf{w}}.$

To conclude we have

$I(s)=I_{1}(s)+I_{2}(s)=\int\limits_{\prod_{i}y_{i}\geqslant\beta}f(\textbf{iy})\textbf{y}^{\frac{\textbf{k}-1}{2}-s}\frac{d\textbf{y}}{\textbf{y}}+\left(\frac{2}{\delta\sqrt{n}}\right)^{2s-1}\int\limits_{\prod_{i}y_{i}\geqslant\beta}f|_{W^{\prime}}(\textbf{iy})\textbf{y}^{\frac{\textbf{k}+1}{2}-s}\frac{d\textbf{y}}{\textbf{y}}.$

If we define

(3.7)
$\Lambda(s,f):=2^{\frac{\textbf{k}-1}{2}}\frac{D_{F}^{s}N(n)^{\frac{s}{2}}}{2^{rs}}I(s),$

then

(3.8)
$\Lambda(s,f)=\frac{D_{F}^{s}N(n)^{\frac{s}{2}}}{(2\pi)^{rs}}\prod_{j=1}^{r}\Gamma\left(s+\frac{k_{j}-1}{2}\right)L(s,f)=\Lambda(1-s,f|_{W^{\prime}}).$

This completes the proof. ∎

##  4\. Proof of Theorem 3

Let $f,g$ be given as in the theorem. Denote the levels of $f,g$ as
$4n_{f},4n_{g}$ and weights as
$\textbf{k}=\textbf{m}+\frac{\textbf{1}}{\textbf{2}},\textbf{l}=\textbf{n}+\frac{\textbf{1}}{\textbf{2}}$
respcetively. Our strategy is to first show that there exists a permutation
$\rho$ of $\\{1,\ldots,r\\}$ such that $l_{\rho(i)}=k_{i}$ for every
$i\in\\{1,\ldots,r\\}$, and to show that $N(n_{f})=N(n_{g})$. This will allow
us to prove that $f=g$, in turn implying that $\textbf{k}=\textbf{l}$ and
$n_{f}=n_{g}$.

Without loss of generality, we may suppose that $\kappa=1$ (where $\kappa$ is
as in (1.1)). Let $\mathsf{f}$ be the Shimura lift of $f$. Recall that
$\mathsf{f}$ is a primitive new form of weight $2\textbf{m}$ and level
$n_{\mathsf{f}}$. The Dirichlet series attached to $\mathsf{f}$ is given as in
(2.8) with the weight $2\textbf{m}$ in place of k;

$L(s,\mathsf{f})=\sum_{\xi\in\mathcal{O}_{F}^{+}/U_{\Gamma}^{+}}\frac{a_{\mathsf{f}}(\xi)\xi^{-\textbf{m}+\frac{1}{2}}}{\xi^{s}}.$

Since the Ramanujan conjecture is known for $F$, $L(s,\mathsf{f})$ is
absolutely convergent for $\Re(s)>1$. Proceeding as in the proof of Theorem 5,
we can show that

(4.1)
$\Lambda(s,\mathsf{f})=\frac{D_{F}^{s}N(n_{\mathsf{f}})^{\frac{s}{2}}}{(2\pi)^{rs}}\prod_{j=1}^{r}\Gamma\left(s+m_{j}-\frac{1}{2}\right)L(s,\mathsf{f})=(-1)^{\textbf{m}}\Lambda(1-s,\mathsf{f}|_{W^{\prime}}),$

Observe that, since $\mathsf{f}$ is a Hecke eigenform, $\Lambda(s,\mathsf{f})$
is holomorphic and non-vanishing in the region $\Re(s)>1$ and in the region
$\Re(s)<0$ because of the functional equation. Given an integral ideal
$\mathfrak{n}$, there exists a totally positive element $\eta$ such that
$\mathfrak{n}=\eta\mathcal{O}_{F}$. Let us denote
$\lambda_{\mathsf{f}}(\mathfrak{n}):=a_{\mathsf{f}}(\eta)\eta^{-\textbf{m}+\frac{1}{2}}$.

Suppose that $\rho$ is a totally positive generator for a prime ideal
$\mathfrak{p}$. The connection between $\omega_{\mathfrak{p}}$ and the Fourier
coefficient $\lambda_{\mathsf{f}}(\rho)$ can be deduced from [Shi78, (2.22),
(2.24)] as

$\lambda_{\mathsf{f}}(\rho)N(\rho)^{\frac{1}{2}}=\omega_{\mathfrak{p}}.$

If we choose $M(\xi)$ to be $N(\xi)^{\frac{1}{2}-2s}$ for some complex
parameter $\Re(s)\gg 1$ and observe that $\omega_{\mathfrak{p}}$ is the Hecke
eigenvalue of $\mathsf{f}$ with respect to $T_{\mathfrak{p}}$, (2.12) gives

$\left(\sum_{0\neq\xi\in\mathcal{O}_{F}^{+}/U^{+}}\frac{a_{f}(\tau\xi^{2})\xi^{-\textbf{m}+\frac{1}{2}}}{N(\xi)^{2s}}\right)\left(\sum_{0\neq\xi\in\mathcal{O}_{F}^{+}/U^{+}}\frac{\chi_{\tau}(\xi)}{N(\xi)^{\frac{1}{2}+2s}}\right)=a_{f}(\tau)\prod_{\mathfrak{p}}\left(1-\frac{\lambda_{\mathsf{f}}(\mathfrak{p})}{N(\mathfrak{p})^{2s}}+\frac{1}{N(\mathfrak{p})^{4s}}\right)^{-1}$

which is infact an identity of Dirichlet series in the above region. A
renormalization gives

$\lambda_{f}(\tau)L(2s,\mathsf{f})=L\left(2s+\frac{1}{2},\chi_{\tau}\right)\left(\sum_{0\neq\xi\in\mathcal{O}_{F}^{+}/U^{+}}\frac{\lambda_{f}(\tau\xi^{2})}{N(\xi)^{2s}}\right),$

where $\lambda_{f}(\tau)$ is given as in (2.9). For $\Re(s)>1$,
$L(s,\chi_{\tau})$ is given by an absolutely convergent Euler product and is
non-vanishing in that region. Therefore

(4.2)
$\frac{\lambda_{f}(\tau)}{N(\tau)^{s}}L\left(2s+\frac{1}{2},\chi_{\tau}\right)^{-1}L(2s,\mathsf{f})=\sum_{0\neq\xi\in\mathcal{O}_{F}^{+}/U^{+}}\frac{\lambda_{f}(\tau\xi^{2})}{N(\tau\xi^{2})^{s}}.$

Summing over all the squarefree $\tau$ (modulo $U^{+}$) we get

(4.3) $L\left(s,f\right)=L(2s,\mathsf{f})\left(\underset{\tau\ \mathrm{sq.\
free}}{\sum_{\tau\in\mathcal{O}_{F}^{+}/U^{+}}}\frac{\lambda_{f}(\tau)}{N(\tau)^{s}}L\left(2s+\frac{1}{2},\chi_{\tau}\right)^{-1}\right).$

Proceeding similarly for $g$, (whose Shimura lift we denote by $\mathsf{g}$)
we arrive at

(4.4) $L\left(s,g\right)=L(2s,\mathsf{g})\left(\underset{\tau\ \mathrm{sq.\
free}}{\sum_{\tau\in\mathcal{O}_{F}^{+}/U^{+}}}\frac{\lambda_{g}(\tau)}{N(\tau)^{s}}L\left(2s+\frac{1}{2},\chi_{\tau}\right)^{-1}\right).$

Define

(4.5) $C(s):=\frac{\Lambda(s,f)}{\Lambda(s,g)}.$

where $\Lambda(s,f)$ is given in (3.7). We shall show that $C(s)$ is a
constant. Suppose that $\lambda_{f}(\tau)=\lambda_{g}(\tau)$ for every
squarefree $\tau$. Denote the weight of $g$ as
$\textbf{l}=\textbf{n}+\left(\frac{1}{2},\ldots,\frac{1}{2}\right)$. We shall
first show that there exists a permutation $\rho$ of the indices
$\\{1,2,\ldots,r\\}$ such that $l_{i}=k_{\rho(i)}$ for every $1\leqslant
i\leqslant r$. Our proof is via contradiction. From (4.3) and (4.4), we have

(4.6)
$C(s)=\left(\frac{N(n_{f})}{N(n_{g})}\right)^{\frac{s}{2}}\left(\prod_{i=1}^{r}\frac{\Gamma\left(\frac{2s+m_{i}-\frac{1}{2}}{2}\right)}{\Gamma\left(\frac{2s+n_{i}-\frac{1}{2}}{2}\right)}\right)\frac{L(2s,\mathsf{f})}{L(2s,\mathsf{g})}.$

Applying the Legendre duplication formula to the Gamma factors, we get

(4.7)
$C(s)=\left(\frac{N(n_{f})}{N(n_{g})}\right)^{\frac{s}{2}}\left(\frac{N(n_{\mathsf{g}})}{N(n_{\mathsf{f}})}\right)^{s}2^{\textbf{n}-\textbf{m}}\left(\prod_{i=1}^{r}\frac{\Gamma\left(\frac{2s+n_{i}+\frac{1}{2}}{2}\right)}{\Gamma\left(\frac{2s+m_{i}+\frac{1}{2}}{2}\right)}\right)\frac{\Lambda(2s,\mathsf{f})}{\Lambda(2s,\mathsf{g})}.$

From (3.8) and (4.5), we see that $C(s)=C^{\prime}(1-s)$ where

$C^{\prime}(s):=\frac{\Lambda(s,f|_{W^{\prime}(n_{f})})}{\Lambda(s,g|_{W^{\prime}(n_{g})})}.$

Plugging this in, we get

(4.8)
$\left(\frac{N(n_{f})}{N(n_{g})}\right)^{\frac{s}{2}}\left(\frac{N(n_{\mathsf{g}})}{N(n_{\mathsf{f}})}\right)^{s}\left(\prod_{i=1}^{r}\frac{\Gamma\left(\frac{2s+n_{i}+\frac{1}{2}}{2}\right)}{\Gamma\left(\frac{2s+m_{i}+\frac{1}{2}}{2}\right)}\right)\frac{\Lambda(2s,\mathsf{f})}{\Lambda(2s,\mathsf{g})}=\\\
\left(\frac{N(n_{f})}{N(n_{g})}\right)^{\frac{1-s}{2}}\left(\frac{N(n_{\mathsf{g}})}{N(n_{\mathsf{f}})}\right)^{1-s}\left(\prod_{i=1}^{r}\frac{\Gamma\left(\frac{2-2s+n_{i}+\frac{1}{2}}{2}\right)}{\Gamma\left(\frac{2-2s+m_{i}+\frac{1}{2}}{2}\right)}\right)\frac{\Lambda(2-2s,\mathsf{f})}{\Lambda(2-2s,\mathsf{g})}.$

Here we use the fact that the Shimura lift of $f$ and $f|_{W^{\prime}}$
coincide, similarlly for $g$. Without loss of generality, we may suppose that
for every $1\leqslant i,j\leqslant r$, $m_{i}\neq n_{j}$. Furthermore, we may
suppose that $m_{1}$ is the minimum of $\\{m_{i},n_{j}\\}_{i,j=1}^{r}$.
Substituting $2s=m_{1}+\frac{5}{2}$, we get

(4.9)
$\left(\frac{N(n_{f})}{N(n_{g})}\right)^{\frac{2m_{1}+5}{8}}\left(\frac{N(n_{\mathsf{g}})}{N(n_{\mathsf{f}})}\right)^{\frac{2m_{1}+5}{4}}\left(\prod_{i=1}^{r}\frac{\Gamma\left(\frac{n_{i}+m_{1}+3}{2}\right)}{\Gamma\left(\frac{m_{i}+m_{1}+3}{2}\right)}\right)\frac{\Lambda\left(m_{1}+\frac{5}{2},\mathsf{f}\right)}{\Lambda\left(m_{1}+\frac{5}{2},\mathsf{g}\right)}=\\\
\left(\frac{N(n_{f})}{N(n_{g})}\right)^{\frac{-2m_{1}-1}{8}}\left(\frac{N(n_{\mathsf{g}})}{N(n_{\mathsf{f}})}\right)^{\frac{-2m_{1}-1}{4}}\left(\prod_{i=1}^{r}\frac{\Gamma\left(\frac{n_{i}-m_{1}}{2}\right)}{\Gamma\left(\frac{m_{i}-m_{1}}{2}\right)}\right)\frac{\Lambda\left(-\frac{1}{2}-m_{1},\mathsf{f}\right)}{\Lambda\left(-\frac{1}{2}-m_{1},\mathsf{g}\right)}.$

This leads to a contradiction as the right hand side vanishes but the left
hand side does not. Thus the choice for $m_{1}$ is not possible, whence it
follows that there exists a permutation $\rho$ of the indices
$\\{1,2,\ldots,r\\}$ such that $l_{i}=k_{\rho(i)}$ for every $1\leqslant
i\leqslant r$. Thus

(4.10)
$C(s)=\left(\frac{N(n_{f})}{N(n_{g})}\right)^{\frac{s}{2}}\frac{L(s,f)}{L(s,g)}=\left(\frac{N(n_{f})}{N(n_{g})}\right)^{\frac{s}{2}}\frac{L(2s,\mathsf{f})}{L(2s,\mathsf{g})}.$

As $L(s,\mathsf{f})$ and $L(s,\mathsf{g})$ are given by an absolutely
converging Euler product in the region $\Re(s)>1$, we conclude that $C(s)$ is
holomorphic and non-vanishing in the region $\Re(s)>\frac{1}{2}$. Furthermore,
$C(s)$ continues meromorphically to the whole complex plane. Define

(4.11)
$C_{1}(s):=C(s)\left(\frac{N(n_{g})}{N(n_{f})}\right)^{\frac{s}{2}}\left(\frac{N(n_{\mathsf{f}})}{N(n_{\mathsf{g}})}\right)^{s}.$

From the functional equations of $L(s,\mathsf{f})$ and $L(s,\mathsf{g})$, we
see
$C_{1}(s)=\varepsilon_{\mathsf{f}}\varepsilon_{\mathsf{g}}^{-1}C_{1}\left(\frac{1}{2}-s\right)$,
where $\varepsilon_{\mathsf{f}},\varepsilon_{\mathsf{g}}\in\\{\pm 1\\}$ are
the eigenvalues of $\mathsf{f},\mathsf{g}$ respectively under the respective
Fricke involutions. Rewriting this in terms of $C(s)$, we get

$\displaystyle\left(\frac{N(n_{g})}{N(n_{f})}\right)^{\frac{s}{2}}\left(\frac{N(n_{\mathsf{f}})}{N(n_{\mathsf{g}})}\right)^{s}C(s)$
$\displaystyle=\varepsilon_{\mathsf{f}}\varepsilon_{\mathsf{g}}^{-1}\left(\frac{N(n_{g})}{N(n_{f})}\right)^{\frac{1}{4}-\frac{s}{2}}\left(\frac{N(n_{\mathsf{f}})}{N(n_{\mathsf{g}})}\right)^{\frac{1}{2}-s}C\left(\frac{1}{2}-s\right)$
$\displaystyle=\varepsilon_{\mathsf{f}}\varepsilon_{\mathsf{g}}^{-1}\left(\frac{N(n_{g})}{N(n_{f})}\right)^{\frac{1}{4}-\frac{s}{2}}\left(\frac{N(n_{\mathsf{f}})}{N(n_{\mathsf{g}})}\right)^{\frac{1}{2}-s}C^{\prime}\left(s+\frac{1}{2}\right).$

Applying the recursive relation once again for $C^{\prime}(s)$ and using Lemma
2, we get that

(4.12)
$\left(\frac{N(n_{g})}{N(n_{f})}\right)^{s+\frac{1}{4}}\left(\frac{N(n_{\mathsf{f}})}{N(n_{\mathsf{g}})}\right)^{2s+\frac{1}{2}}C(s)=\left(\frac{N(n_{g})}{N(n_{f})}\right)^{\frac{1}{4}-s}\left(\frac{N(n_{\mathsf{f}})}{N(n_{\mathsf{g}})}\right)^{\frac{1}{2}-2s}C(s+1).$

Rewriting the above equation, we get

(4.13)
$\left(\left(\frac{N(n_{g})}{N(n_{f})}\right)^{\frac{s}{2}}C(s)\right)=\left(\frac{N(n_{g})}{N(n_{f})}\right)^{-\frac{1}{2}-2s}\left(\frac{N(n_{\mathsf{f}})}{N(n_{\mathsf{g}})}\right)^{-4s}\left(\left(\frac{N(n_{g})}{N(n_{f})}\right)^{\frac{s+1}{2}}C(s+1)\right).$

From the Dirichlet series expansion for $L(s,\mathsf{f})$ (and our
normalization), we see that $\lim_{\sigma\to\infty}L(\sigma+it,\mathsf{f})=1$
for any $t\in\mathbb{R}$. Choose $t=0$. From (4.10), choosing
$s=\sigma\in\mathbb{R}$ and letting $\sigma\to\infty$ in (4.13) leads to a
contradiction unless $N(n_{f})=N(n_{g})$ and
$N(n_{\mathsf{f}})=N(n_{\mathsf{g}})$. In particular, (4.12) gives us
$C(s)=C(s+1)$. In particular, it follows that $C(s)$ is an entire function.
Therefore it suffices to show that $C(s)$ is absolutely bounded. From
periodicity, it is sufficient to do this for $\Re(s)\gg 1$ and we shall
suppose so. Fix $t\in\mathbb{R}$. Arguing as above we may choose $\sigma$
large enough so that $|L(\sigma+it,\mathsf{f})|\leqslant 2$ and
$|L(\sigma+it,\mathsf{g})|\geqslant\frac{1}{2}$ implying for large enough
$\sigma$, $|C(\sigma+it)|\leqslant 4$. From periodicity, the above bound holds
for every $\sigma\in\mathbb{R}$. Since $t$ was arbitrary, the above bound
holds uniformly in $\mathbb{C}$. Thus $C(s)$ is a constant as claimed. This
completes the proof.

###  4.1. Restricting to the plus space

Consider forms $f$ of level $4n_{f}$ where $n_{f}$ is odd (coprime to $2$) and
squarefree. The Kohnen-“plus” space is a subspace of cusp forms characterized
by certain conditions on the Fourier coefficients. For modular forms over
$\mathbb{Q}$, Kohnen was able to show certain remarkable properties of this
plus space in connection to the Shimura lift (see [Koh80],[Koh82]). Suppose
that $\xi\in\mathcal{O}_{F}$ is not a square in $F$. A tuple
$(\xi,\eta)\in\mathcal{O}_{F}\times F$ is called a discriminant if

  1. (1)

there exists $\omega_{\xi}\in F(\sqrt{\xi})$ such that
$Tr_{K_{\xi}/F}(\omega_{\xi})^{2}-4N_{K_{\xi}/F}(\omega_{\xi})=\xi$, and

  2. (2)

$\mathcal{O}_{F}\oplus\omega_{\xi}\eta\mathcal{O}_{F}$ is an order in
$K_{\xi}$.

Furthermore we say that $(\xi,\eta)$ is a fundamental discriminant if
$\mathcal{O}_{F}\oplus\omega_{\xi}\eta\mathcal{O}_{F}$ is the ring of integers
of $F(\sqrt{\xi})$. A discriminant $(\xi,\eta)$ corresponds to the Fourier
coefficient $\lambda_{f}(\xi\eta^{2})$ of $f$. In particular we can restrict
ourselves to discriminants of the form $(\xi,1)$ for which $\xi\in F^{+}$. We
may abbreviate the notation for fundamental discriminant $(\xi,1)$ as $\xi$.

Choose and fix a unit $v$ (if it exists) such that $N(v)=-1$. For any weight
$\textbf{m}\in\mathbb{Z}^{r}$, we let $u_{\textbf{m}}$ denote either $1$ or
$v$ depending on whether $(-1)^{\textbf{m}}=\pm 1$ respectively. Now, we may
extend [HI13, Definition 13.2] for our case as follows. In the following, let
us abbreviate $u_{\textbf{m}_{f}}$ as $u_{f}$; similarly for $g$.

######  Definition 1 (Kohnen plus space).

Given a weight $\textbf{k}=\textbf{m}+\frac{\textbf{1}}{\textbf{2}}$, let
$u_{\textbf{m}}$ be as above. The Kohnen plus space is defined as the space of
all half integral weight modular forms of weight k such that
$\lambda_{f}(\tau)=0$ unless $u_{\textbf{m}}\tau\equiv\square\mod 4$.

######  Corollary 1.

Suppose $f$ and $g$ are two newforms of weights
$\textbf{k}_{f}=\textbf{m}_{f}+\frac{\textbf{1}}{\textbf{2}}$ and
$\textbf{k}_{g}=\textbf{m}_{g}+\frac{\textbf{1}}{\textbf{2}}$ respectively, in
the Kohnen plus space (of respective weights and levels). Suppose that
$\lambda_{f}(u_{f}\xi)=\lambda_{g}(u_{g}\xi)$ for every fundamental
discriminant $\xi$. Then $f=g$.

###### Proof.

If $1=u_{f}\neq u_{g}$, then $u_{f}\xi$ and $u_{g}\xi$ cannot both
simultaneously be squares modulo $4$. This leads to a degenrate case. Hence we
may suppose $u_{f}=u_{g}=u$. Suppose $\xi\in u\mathcal{O}_{F}^{+}$ is
squarefree. From Theorem 3, it is enough to verify that

(4.14) $\lambda_{f}(u\xi)=\lambda_{g}(u\xi).$

We may suppose that $\xi\equiv\square\mod 4$; otherwise both sides of (4.14)
vanish. In particular, this means that $\xi$ is coprime to $2$. Then from
[CDyDO05, Theorem 1.7], the relative discriminant of $F(\sqrt{\xi})$ over $F$
equals $\xi$. In this case (4.14) follows from our assumption completing the
proof. ∎

##  5\. Proof of Theorem 4

In order not to clog up notation, in this section,
$\tau\in\mathcal{O}_{F}^{+}/U^{+}$ shall denote a squarefree algebaric
integer. For Hecke eigenforms, choosing $M(\xi)=N(\xi)^{-s}$ in (2.12) and
using Möbius inversion we get

$\lambda_{f}(\tau\xi^{2})=\lambda_{f}(\tau)\sum_{\eta_{1}\eta_{2}=\xi\mod
U}\mu_{F}(\eta_{1})\frac{\chi_{\tau}(\eta_{1})}{N(\eta_{1})}\lambda_{\mathsf{f}}(\eta_{2}),$

where $\mu_{F}$ denotes the analogue of the Möbius function for $F$. For $T\gg
1$ we have

$\underset{N(\tau\xi^{2})\leqslant
T}{\sum_{\tau\xi^{2}\in\mathcal{O}_{F}^{+}/U^{+}}}\left|\lambda_{f}(\tau\xi^{2})\right|^{2}=\underset{N(\tau\xi^{2})\leqslant
T}{\sum_{\tau\xi^{2}\in\mathcal{O}_{F}^{+}/U^{+}}}\left|\lambda_{f}(\tau)\right|^{2}\left|\underset{\eta_{1},\eta_{2}\mod
U}{\sum_{\eta_{1}\eta_{2}=\xi}}\mu_{F}(\eta_{1})\frac{\chi_{\tau}(\eta_{1})}{N(\eta_{1})}\lambda_{\mathsf{f}}(\eta_{2})\right|^{2}.$

Using the Rankin-Selberg estimate (2.14) on the left hand side and the
Ramanujan bound (which is known for $\mathsf{f}$) on the right hand side we
obtain, for some $0<\epsilon<1/2$ and $A\gg 1$,

$\displaystyle T$
$\displaystyle\ll_{f,\epsilon}\underset{N(\tau\xi^{2})\leqslant
T}{\sum_{\tau\xi^{2}\in\mathcal{O}_{F}^{+}/U^{+}}}\left|\lambda_{f}(\tau)\right|^{2}\xi^{\epsilon}=\underset{N(\tau)\leqslant
T}{\sum_{\tau\in\mathcal{O}_{F}^{+}/U^{+}}}\left|\lambda_{f}(\tau)\right|^{2}\sum_{N(\xi)\leqslant\sqrt{\frac{T}{N(\tau)}}}\xi^{\epsilon}$
$\displaystyle\ll T^{\frac{1}{2}+\epsilon}\underset{\log(T)\leqslant
N(\tau)\leqslant
T}{\sum_{\tau\in\mathcal{O}_{F}^{+}/U^{+}}}\frac{\left|\lambda_{f}(\tau)\right|^{2}}{N(\tau)^{\frac{1}{2}+\epsilon}}+\mathcal{O}\left(T^{\frac{1}{2}+\epsilon}\log^{A}(T)\right)$
$\displaystyle\ll_{F}T\sup_{\log(T)\leqslant N(\tau)\leqslant
T}\left\\{|\lambda_{f}(\tau)|^{2}\right\\}+\mathcal{O}\left(T^{\frac{1}{2}+\epsilon}\log^{A}(T)\right).$

Cancelling $T$ from both sides completes the proof.

## References

  * [AS08] Sever Achimescu and Abhishek Saha, _Hilbert modular forms of weight 1/2 and theta functions_ , J. Number Theory 128 (2008), no. 12, 3037–3062. MR 2464853
  * [CDyDO05] Henri Cohen, Francisco Diaz y Diaz, and Michel Olivier, _Counting cyclic quartic extensions of a number field_ , J. Théor. Nombres Bordx. 17 (2005), no. 2, 475–510 (English).
  * [Das20] Soumya Das, _Omega results for Fourier coefficients of half-integral weight and Siegel modular forms_ , Modular forms and related topics in number theory. Proceedings of the international conference on number theory, ICNT 2018, Kozhikode, India, December 10–14, 2018, Singapore: Springer, 2020, pp. 59–72 (English).
  * [Gar90] Paul B. Garrett, _Holomorphic Hilbert modular forms_ , Pacific Grove, CA: Wadsworth &— Brooks/Cole Advanced Books &— Software, 1990 (English).
  * [GHS09] Satadal Ganguly, Jeffrey Hoffstein, and Jyoti Sengupta, _Determining modular forms on ${\rm SL}_{2}(\mathbb{Z})$ by central values of convolution $L$-functions_, Math. Ann. 345 (2009), no. 4, 843–857. MR 2545869
  * [GK19] Sanoli Gun and Winfried Kohnen, _On the Ramanujan-Petersson conjecture for modular forms of half-integral weight_ , Forum Math. 31 (2019), no. 3, 703–711 (English).
  * [GKS20] S. Gun, W. Kohnen, and K. Soundararajan, _Large fourier coefficients of half-integer weight modular forms_ , 2020.
  * [GMP21] Sanoli Gun, V. Kumar Murty, and Biplab Paul, _Distinguishing newforms by their Hecke eigenvalues_ , Res. Number Theory 7 (2021), no. 3, 24 (English), Id/No 49.
  * [HI13] Kaoru Hiraga and Tamotsu Ikeda, _On the Kohnen plus space for Hilbert modular forms of half-integral weight. I_ , Compos. Math. 149 (2013), no. 12, 1963–2010 (English).
  * [HT17] Alia Hamieh and Naomi Tanabe, _Determining Hilbert modular forms by central values of Rankin-Selberg convolutions: the level aspect_ , Trans. Am. Math. Soc. 369 (2017), no. 12, 8781–8797 (English).
  * [Koh80] Winfried Kohnen, _Modular forms of half-integral weight on $\Gamma_{0}(4)$_, Math. Ann. 248 (1980), 249–266 (English).
  * [Koh82] by same author, _Newforms of half-integral weight_ , J. Reine Angew. Math. 333 (1982), 32–72 (English).
  * [Koh92] by same author, _On Hecke eigenforms of half-integral weight_ , Math. Ann. 293 (1992), no. 3, 427–432 (English).
  * [LR97] Wenzhi Luo and Dinakar Ramakrishnan, _Determination of modular forms by twists of critical $L$-values_, Invent. Math. 130 (1997), no. 2, 371–398 (English).
  * [MS15a] Ritabrata Munshi and Jyoti Sengupta, _Determination of $\mathrm{GL}(3)$ Hecke-Maass forms from twisted central values_, J. Number Theory 148 (2015), 272–287 (English).
  * [MS15b] by same author, _On effective determination of Maass forms from central values of Rankin-Selberg $L$-function_, Forum Math. 27 (2015), no. 1, 467–484. MR 3334069
  * [Mun10] Ritabrata Munshi, _On effective determination of modular forms by twists of critical $L$-values_, Math. Ann. 347 (2010), no. 4, 963–978. MR 2658151
  * [Pi14] Qinghua Pi, _On effective determination of cusp forms by $L$-values, level aspect_, J. Number Theory 142 (2014), 305–321. MR 3208405
  * [Shi78] Goro Shimura, _The special values of the zeta functions associated with Hilbert modular forms_ , Duke Math. J. 45 (1978), no. 3, 637–679. MR 507462
  * [Shi87] by same author, _On Hilbert modular forms of half-integral weight_ , Duke Math. J. 55 (1987), 765–838 (English).
  * [Shi93] by same author, _On the Fourier coefficients of Hilbert modular forms of half-integral weight_ , Duke Math. J. 71 (1993), no. 2, 501–557 (English).


11institutetext: School of Computer Science and Engineering, University of
Electronic Science and Technology of China, Chengdu, China
11email<EMAIL_ADDRESS>11email<EMAIL_ADDRESS>
# A Discharging Method: Improved Kernels for Edge Triangle Packing and
Covering

Zimo Sheng  Mingyu Xiao Corresponding author 0000-0002-1012-2373

###### Abstract

Edge Triangle Packing and Edge Triangle Covering are dual problems extensively
studied in the field of parameterized complexity. Given a graph $G$ and an
integer $k$, Edge Triangle Packing seeks to determine whether there exists a
set of at least $k$ edge-disjoint triangles in $G$, while Edge Triangle
Covering aims to find out whether there exists a set of at most $k$ edges that
intersects all triangles in $G$. Previous research has shown that Edge
Triangle Packing has a kernel of $(3+\epsilon)k$ vertices, while Edge Triangle
Covering has a kernel of $6k$ vertices. In this paper, we show that the two
problems allow kernels of $3k$ vertices, improving all previous results. A
significant contribution of our work is the utilization of a novel discharging
method for analyzing kernel size, which exhibits potential for analyzing other
kernel algorithms.

##  1 Introduction

Preprocessing is a fundamental and commonly used step in various algorithms.
However, most preprocessing has no theoretical guarantee on the quality.
Kernelization, originating from the field of parameterized algorithms [1], now
has been found to be an interesting way to analyze the quality of
preprocessing. Consequently, kernelization has received extensive attention in
both theoretical and practical studies.

Given an instance $(I,k)$ of a problem, a kernelization (or a kernel
algorithm) runs in polynomial time and returns an equivalent instance
$(I^{\prime},k^{\prime})$ of the same problem such that $(I,k)$ is a yes-
instance if and only if $(I^{\prime},k^{\prime})$ is a yes-instance, where
$k^{\prime}\leq k$ and $|I^{\prime}|\leq g(k)$ for some computable function
$g$ only of $k$. The new instance $(I^{\prime},k^{\prime})$ is called a
_kernel_ and $g(k)$ is the size of the kernel. If g(·) is a polynomial or
linear function, we classify the problem as having a polynomial or linear
kernel, respectively.

Edge Triangle Packing (ETP), to check the existence of $k$ edge-disjoint
triangles in a given graph $G$ is NP-hard even on planar graphs with maximum
degree 5 [2]. The optimization version of this problem is APX-hard on general
graphs [3]. A general result of [4] leads to a polynomial-time
$(3/2+\epsilon)$ approximation algorithm for any constant $\epsilon>0$. When
the graphs are restricted to planar graphs, the result can be improved. A
polynomial-time approximation scheme for the vertex-disjoint triangle packing
problem on planar graphs was given by [5], which can be extended to ETP on
planar graphs. In terms of parameterized complexity, a $4k$-vertex kernel and
an $O^{*}(2^{\frac{9k}{2}\log k+\frac{9k}{2}})$-time parameterized algorithm
for ETP were developed in [6]. Later, the size of the kernel was improved to
$3.5k$ [7]. The current best-known result is $(3+\epsilon)k$ [8], where
$\epsilon>0$ can be any positive constant. On tournaments, there is also a
kernel of $3.5k$ vertices [9].

Another problem considered in this paper is Edge Triangle Covering (ETC). ETC
is the dual problem of ETP, which is to check whether we can delete at most
$k$ edges from a given graph such that the remaining graph has no triangle.
ETC is also NP-hard even on planar graphs with maximum degree 7 [10]. In terms
of kernelization, a $6k$-vertex kernel for ETC was developed [10]. On planar
graphs, the result was further improved to $\frac{11k}{3}$ [10].

In this paper, we will deeply study the structural properties of Edge Triangle
Packing and Edge Triangle Covering and give some new reduction rules by using
a variant of crown decomposition. After that, we will introduce a new
technology called the discharging method to analyze the size of problem
kernels. Utilizing the new discharging method, we obtain improved kernel sizes
of $3k$ vertices for both ETP and ETC. Notably, our results even surpass the
previously best-known kernel size for ETC on planar graphs [10].

##  2 Preliminaries

Let $G=(V,E)$ denote a simple and undirected graph with $n=|V|$ vertices and
$m=|E|$ edges. A vertex is a _neighbor_ of another vertex if there is an edge
between them. The set of neighbors of a vertex $v$ is denoted by $N(v)$, and
the degree of $v$ is defined as $d(v)=|N(v)|$. For a vertex subset
$V^{\prime}\subseteq V$, we let $N(V^{\prime})=\cup_{v\in
V^{\prime}}N(v)\setminus V^{\prime}$ and $N[V^{\prime}]=N(V^{\prime})\cup
V^{\prime}$. The subgraph induced by a vertex subset $V^{\prime}\subseteq V$
is denoted by $G[V^{\prime}]$ and the subgraph spanned by an edge set
$E^{\prime}\subseteq E$ is denoted by $G[E^{\prime}]$. The vertex set and edge
set of a graph $H$ are denoted by $V(H)$ and $E(H)$, respectively.

A complete graph on $3$ vertices is called a _triangle_. We will use $vuw$ to
denote the triangle formed by vertices $v$, $u$, and $w$. If there is a
triangle $vuw$ in $G$, we say that vertex $v$ _spans_ edge $uw$. An _edge
triangle packing_ in a graph is a set of triangles such that every two
triangles in it have no common edge. The Edge Triangle Packing problem (ETP)
is defined below.

Edge Triangle Packing (ETP) Parameter: $k$ Input: An undirected graph
$G=(V,E)$, and an integer $k$. Question: Does there exist an edge triangle
packing of size at least $k$ in $G$?

An edge _covers_ a triangle if it is contained in the triangle. An _edge
triangle covering_ in a graph is a set of edges $S$ such that there is no
triangle after deleting $S$ from $G$. The Edge Triangle Covering problem (ETC)
is defined below.

Edge Triangle Covering (ETC) Parameter: $k$ Input: An undirected graph
$G=(V,E)$, and an integer $k$. Question: Does there exist an edge triangle
covering of size at most $k$ in $G$?

##  3 Fat-Head Crown Decomposition

One important technique in this paper is based on a variant of the crown
decomposition. Crown decomposition is a powerful technique for the famous
Vertex Cover problem and it has been extended to solve several related
problems [11, 12, 13, 14]. Specifically, we employ a specific variant called
the fat-head crown decomposition to tackle (ETP) [8]. This variant of the
crown decomposition will also be applied in our algorithms for both ETP and
ETC. To provide a comprehensive understanding, let us begin by introducing the
definition of the fat-head crown decomposition.

A _fat-head crown decomposition_ of a graph $G=(V,E)$ is a triple $(C,H,X)$
such that $C$ and $X$ form a partition of $V$ and $H\subseteq E$ is a subset
of edges satisfying the following properties:
1\. $C$ is an independent set.
2\. $H$ is the set of edges spanned by at least one vertex in $C$.
3\. No vertex in $C$ is adjacent to a vertex in $X\setminus V(H)$.
4\. There is an edge-disjoint triangle packing $P$ of size $|P|=|H|$ such that
each triangle in $P$ contains exactly one vertex in $C$ and exactly one edge
in $H$. The packing $P$ is also called the _witness packing_ of the fat-head
crown decomposition.

Figure 1: An illustration for the fat-head crown decomposition

An illustration of the fat-head crown decomposition is shown in Figure 1. To
determine the existence of fat-head crown decompositions in a given graph
structure, we present three lemmas.

###### Lemma 1

_(Lemma 2 in[8])_ Let $G=(V,E)$ be a graph such that each edge and each vertex
is contained in at least one triangle. Given a non-empty independent set
$I\subseteq V$ such that $|I|>|S(I)|$, where $S(I)$ is the set of edges
spanned by at least one vertex in $I$. A fat-head crown decomposition
$(C,H,X)$ of $G$ with $C\subseteq I$ and $H\subseteq S(I)$ together with a
witness packing $P$ of size $|P|=|H|>0$ can be found in polynomial time.

###### Lemma 2

Given a graph $G=(V,E)$, a vertex set $A\subseteq V$, and an edge set
$B\subseteq E$, where $A\cap V(B)=\emptyset$. There is a polynomial-time
algorithm that checks whether there is a fat-head crown decomposition
$(C,H,X)$ such that $\emptyset\neq C\subseteq A$ and $H\subseteq B$ and
outputs one if yes.

###### Proof

We begin by demonstrating that if there exists an edge $uv\in E$ between two
vertices $u$ and $v\in A$, neither $u$ nor $v$ can belong to $C$ in the fat-
head crown decomposition. Suppose, without loss of generality, that $u$ is in
$C$. Since $C$ is an independent set, $v$ cannot be in $C$. Moreover, $v$
cannot be in $X\setminus V(H)$ since no vertex in $C$ is adjacent to a vertex
in $X\setminus V(H)$. Additionally, $v$ cannot be in $V(H)$ since $A\cap
V(B)=\emptyset$. Thus, this scenario is impossible. Therefore, neither $u$ nor
$v$ can be in $C$ for any fat-head crown decomposition $(C,H,X)$ with
$C\subseteq A$ and $H\subseteq B$. Consequently, we can exclude vertices in
$A$ that are adjacent to other vertices in $A$ when computing the
decomposition.

To facilitate the computation, we construct an auxiliary bipartite graph
$G^{\prime}=(A^{\prime},B^{\prime},E^{\prime})$, where each vertex in
$A^{\prime}$ corresponds to a vertex in $A$ that is not adjacent to any other
vertex in $A$, each vertex in $B^{\prime}$ corresponds to an edge in $B$, and
an edge exists between $w\in A^{\prime}$ and $e\in B^{\prime}$ if and only if
$w$ spans $e$ in $G$. Based on the construction of $G^{\prime}$, we deduce
that a fat-head crown decomposition $(C,H,X)$ exists in $G$ if and only if
there exist $C^{\prime}\subseteq A^{\prime}$ and $H^{\prime}\subseteq
B^{\prime}$ in $G^{\prime}$ such that there is a matching of size
$|H^{\prime}|$ in the induced bipartite graph $G^{\prime}[C^{\prime}\cup
H^{\prime}]$.

The existence of the matching can be determined in $O(mn^{1.5})$ time using
the expansion lemma [15]. Thus, the algorithm can verify the existence of a
fat-head crown decomposition and output one if it exists, all within
polynomial time complexity. ∎

###### Lemma 3

If there is a fat-head crown decomposition $(C,H,X)$ in $G$, then $G$ has an
edge-disjoint triangle packing (resp., edge triangle covering) of size $k$ if
and only if the graph $G^{\prime}$ has an edge-disjoint triangle packing
(resp., edge triangle covering) of size $k-|H|$, where $G^{\prime}$ is the
graph obtained from $G$ by deleting vertex set $C$ and deleting edge set $H$.

###### Proof

For a fat-head crown decomposition $(C,H,X)$, there is witness packing $P$ of
size $|P|=|H|$.

We first show that there is an edge-disjoint triangle packing $D$ of size $k$
in $G$ if and only if there is an edge-disjoint triangle packing $D^{\prime}$
of size $k-|H|$ in $G^{\prime}$. We only prove the sufficient condition and
the other direction is obvious since $D^{\prime}\cup P$ is a valid edge-
disjoint triangle packing in $G$. Let $D^{*}\subseteq D$ be the set of
triangles containing either a vertex in $C$ or an edge in $H$. For the former
case, triangle $T$ still contains one edge in $H$ since any triangle
containing a vertex in $C$ must contain one edge in $H$. Thus, each triangle
in $D^{*}$ contains at least one edge in $H$, which means that
$|D^{*}|\leq|H|$. Therefore, $D-D^{*}$ is an edge-disjoint triangle packing of
size at least $k-|H|$ in graph $G^{\prime}$.

Next, we prove that there is an edge triangle covering $M$ of size $k$ in $G$
if and only if there is an edge triangle covering $M^{\prime}$ of size $k-|H|$
in $G^{\prime}$. For the necessary condition. We prove that $M^{\prime}\cup H$
is a valid edge triangle covering in $G$. Consider an arbitrary triangle
$T^{\prime}$ in $G$. If $V(T^{\prime})\cap V(C)=\emptyset$ and
$E(T^{\prime})\cap E(H)=\emptyset$, then $T^{\prime}$ is covered by
$M^{\prime}$ since $M^{\prime}$ is an edge triangle covering for $G^{\prime}$.
If $V(T^{\prime})\cap C\neq\emptyset$, then $T^{\prime}$ is covered by $H$
since vertices in $C$ can only span edges in $H$ by the definition of the fat-
head crown decomposition. If $E(T^{\prime})\cap E(H)\neq\emptyset$, then
$T^{\prime}$ is covered by $H$. For any case, triangle $T^{\prime}$ is covered
by at least one edge in $M^{\prime}\cup H$. For the sufficient condition. Let
$M^{*}=M\cap E(P)$. We know that $|M^{*}|\geq|P|=|H|$ since $P$ is an edge-
disjoint triangle packing of size $|H|$. Thus, $M-M^{*}$ is an edge triangle
covering of size at most $k-|H|$ in $G^{\prime}$. ∎

##  4 The Algorithms

In this section, we present our kernelization algorithms for the Edge Triangle
Packing (ETP) and Edge Triangle Covering (ETC) problems. Our algorithms
involve a set of reduction rules that are applied iteratively until no further
reduction is possible. Each reduction rule is applied under the assumption
that all previous reduction rules have already been applied and cannot be
further applied to the current instance. A reduction rule is _correct_ if the
original instance $(G,k)$ is a yes-instance if and only if the resulting
instance $(G^{\prime},k^{\prime})$ after applying the reduction rule is a yes-
instance.

We have one algorithm for ETP and ETC, respectively. The two algorithms are
similar. We will mainly describe the algorithm for ETP and introduce the
difference for ETC. In total, we have nine reduction rules. The first four
rules are simple rules to handle some special structures, while the remaining
five rules are based on a triangle packing. Especially, the last rule will use
the fat-head crown decomposition. We will show that the algorithms run in
polynomial time.

###  4.1 Simple Rules

###### Reduction Rule 1

For ETP, if $k\leq 0$, then return ‘yes’ to indicate that the instance is a
yes-instance; if $k>0$ and the graph is empty, then return ‘no’ to indicate
that the instance is a no-instance.
For ETC, if $k\geq 0$ and the graph is empty, then return ‘yes’ to indicate
that the instance is a yes-instance; if $k<0$, then return ‘no’ to indicate
that the instance is a no-instance.

###### Reduction Rule 2

If there is a vertex or an edge not appearing in any triangle, then delete it
from the graph.

###### Reduction Rule 3

If there are 4 vertices $u,v,w,x\in V$ inducing a complete graph (i.e., there
are 6 edges $uv,uw,ux,vw,vx,wx\in E$) such that none of the 6 edges is in a
triangle except $uwv,uvx,uwx$, and $vwx$, then
\- For ETP, delete the 6 edges $uv,uw,ux,vw,vx$ and $wx$ and let $k=k-1$;
\- For ETC, delete the 6 edges $uv,uw,ux,vw,vx$ and $wx$ and let $k=k-2$.

The correctness of Reduction Rule 3 is based on the following observation. For
ETP, any edge triangle packing can have at most one triangle containing some
edge from these 6 edges and we can simply take one triangle from this local
structure. For ETC, any edge triangle covering must contain at least two edges
from these 6 edges and after deleting $vu$ and $wx$, none of $uw,ux,vw$, and
$vx$ is contained in a triangle anymore.

###### Reduction Rule 4

If there is a vertex $v\in V$ such that all edges incident to $v$ can be
partitioned into two parts $E_{1}$ and $E_{2}$ such no triangle in $G$
contains an edge in $E_{1}$ and an edge in $E_{2}$, then split $v$ into two
vertices $v^{\prime}$ and $v^{\prime\prime}$ such that all edges in $E_{1}$
are incident on $v^{\prime}$ and all edges in $E_{2}$ are incident on
$v^{\prime\prime}$.

An illustration of Reduction Rule 4 is shown in Figure 2. This reduction rule
will increase the number of vertices in the graph. However, this operation
will simplify the graph structure and our analysis.

Figure 2: An Illustration for Reduction Rule 4

###### Lemma 4

Reduction Rule 4 is correct and can be executed in polynomial time.

###### Proof

First, we consider the correctness. Let $G^{\prime}=(V^{\prime},E^{\prime})$
be the graph after applying Reduction Rule 4 on a vertex $v$. We can establish
a one-to-one mapping between the edges in $E$ and the edges in $E^{\prime}$ by
considering the vertices $v^{\prime}$ and $v^{\prime\prime}\in V^{\prime}$ as
$v\in V$. Three edges in $E$ form a triangle in $G$ if and only if the three
corresponding edges in $E^{\prime}$ form a triangle in $G^{\prime}$ since
there is no triangle in $G$ contains an edge in $E_{1}$ and an edge in
$E_{2}$. Thus, an edge triangle packing of size $k$ (resp., an edge triangle
covering of size $k$) in $G$ is also an edge triangle packing of size $k$
(resp., an edge triangle covering of size $k$) in $G^{\prime}$. This implies
that Reduction Rule 4 is correct for both ETP and ETC.

We give a simple greedy algorithm to find the edge sets $E_{1}$ and $E_{2}$
for a given vertex $v$. Initially, let $E_{1}$ contain an arbitrary edge $e$
incident on $v$. We iteratively perform the following steps until no further
updates occur: if there is a triangle containing an edge in $E_{1}$ and an
edge $e^{\prime}$ incident on $v$ but not in $E_{1}$, then add edge
$e^{\prime}$ to $E_{1}$. It is easy to see that all edges in $E_{1}$ must be
in the same part to satisfy the requirement. If $E_{1}\neq E$, then we can
split $E$ to two parts $E_{1}$ and $E_{2}=E\setminus E_{1}$. Otherwise, the
edges incident on $v$ cannot be split. ∎

###  4.2 Adjustments Based on a Triangle Packing

After applying the first four rules, our algorithms will find a maximal edge-
disjoint triangle packing $S$ by using an arbitrary greedy method. This can be
done easily in polynomial time. The following rules are based on the packing
$S$. From now on, we let $F=V\setminus V(S)$ denote the set of vertices not
appearing in $S$ and $R=E\setminus E(S)$ denote the set of edges not appearing
in $S$. We begin with the following trivial rule.

###### Reduction Rule 5

If $|S|>k$, for ETP, return ‘yes’ to indicate that the instance is a yes-
instance; and for ETC, return ‘no’ to indicate that the instance is a no-
instance.

The following three rules just update the packing $S$ by replacing some
triangles in it and do not change the graph. Illustrations of the three rules
are shown in Figure 3.

Figure 3: Illustrations of Reduction Rules 6-8

###### Reduction Rule 6

If there is a triangle $v_{1}v_{2}v_{3}\in S$ such that there are at least two
edge-disjoint triangles in the spanned graph
$G[R\cup\\{v_{1}v_{2},v_{1}v_{3},v_{2}v_{3}\\}]$, then replace
$v_{1}v_{2}v_{3}$ with these triangles in $S$ to increase the size of $S$ by
at least 1.

###### Reduction Rule 7

If there are two edge-disjoint triangles $v_{1}v_{2}v_{3}$ and
$v_{4}v_{5}v_{6}\in S$ such that there are at least three edge-disjoint
triangles in the spanned graph
$G[R\cup\\{v_{1}v_{2},v_{1}v_{3},v_{2}v_{3},v_{4}v_{5},v_{4}v_{6},v_{5}v_{6}\\}]$,
then replace $v_{1}v_{2}v_{3}$ and $v_{4}v_{5}v_{6}$ with these triangles in
$S$ to increase the size of $S$ by at least 1.

###### Reduction Rule 8

If there are two edge-disjoint triangles $v_{1}v_{2}v_{3}$ and
$v_{4}v_{5}v_{6}\in S$ such that there are two edge-disjoint triangles
$v^{\prime}_{1}v^{\prime}_{2}v^{\prime}_{3}$ and
$v^{\prime}_{4}v^{\prime}_{5}v^{\prime}_{6}$ in the induced graph
$G[F\cup\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\\}]$ such that
$|\\{v^{\prime}_{1},v^{\prime}_{2},v^{\prime}_{3}\\}\cup\\{v^{\prime}_{4},v^{\prime}_{5},v^{\prime}_{6}\\}|>|\\{v_{1},v_{2},v_{3}\\}\cup\\{v_{4},v_{5},v_{6}\\}|$
, then replace triangles $v_{1}v_{2}v_{3}$ and $v_{4}v_{5}v_{6}$ with
triangles $v^{\prime}_{1}v^{\prime}_{2}v^{\prime}_{3}$ and
$v^{\prime}_{4}v^{\prime}_{5}v^{\prime}_{6}$ in $S$ to increase the number of
vertices appearing in $S$ by at least 1.

Note that an application of Reduction Rules 6-8 will not change the structure
of the graph. Thus, the first four reduction rules will not be applied after
executing Reduction Rules 6-8.

###  4.3 A Reduction Based on Fat-head Crown Decomposition

After Reduction Rule 8, we obtain the current triangle packing $S$. An edge in
$E(S)$ is called a _labeled edge_ if it is spanned by at least one vertex in
$F$. We let $L$ denote the set of labeled edges.

We can find a fat-head crown decomposition $(C,H,X)$ with $C\subseteq
V\setminus V(L)$ and $H\subseteq L$ in polynomial time if it exists by Lemma
2. Moreover, we will apply the following reduction rule to reduce the graph,
the correctness of which is based on Lemma 3.

###### Reduction Rule 9

Use the algorithm in Lemma 2 to check whether there is a fat-head crown
decomposition $(C,H,X)$ such that $\emptyset\neq C\subseteq V\setminus V(L)$
and $H\subseteq L$. If yes, then delete vertex set $C$ and edge set $H$, and
let $k=k-|H|$.

An instance is called _reduced_ if none of the nine reduction rules can be
applied to it. The corresponding graph is also called a reduced graph.

###### Lemma 5

For any input instance, the kernelization algorithms run in polynomial time to
output a reduced instance.

###### Proof

Lemma 2 demonstrates that one execution of Reduction Rule 9 can be performed
within polynomial time, while Lemma 4 shows that one execution of Reduction
Rule 4 can also be accomplished in polynomial time. Additionally, each of the
remaining reduction rules can be easily executed within polynomial time. Next,
we only need to show that each reduction rule can be executed for at most
polynomial times to complete our proof. Reduction Rules 1 and 5 can be applied
for at most 1 time. Reduction Rule 2 can be applied for at most $m$ times
since it will delete at least one edge each time. Reduction Rule 4 can be
applied for at most $2m$ times since it will increase one vertex each time and
there are at most $2m$ vertices for the worst case. Reduction Rules 3 and 9
can be applied for at most $k$ times since each of them will decrease $k$ by
at least 1. We consider Reduction Rules 6-8. For a fixed graph $G=(V,E)$,
Reduction Rules 6 and 7 can be continuously executed for at most $k$ times and
Reduction Rule 8 can be continuously executed for at most $3k$ times. Since
Reduction Rule 9 can be applied for at most $k$ times to change the graph, we
know that Reduction Rules 6-8 can be applied for at most $O(k^{2})$ times.
Thus, the algorithms run in polynomial times. ∎

##  5 Analysis Based on Discharging

Next, we use a discharging method to analyze the size of a reduced instance.
Note that there is no significant difference between ETC and ETP in the
analysis. We partition the graph into two parts: one part is the edge-disjoint
triangle packing $S$ after applying all the reductions; the other part is the
set $F$ of vertices not appearing in $S$. Before proceeding with the analysis,
we will establish some properties that will be utilized.

###### Lemma 6

Consider a reduced graph $G=(V,E)$ with triangle packing $S$. For any triangle
$uvw\in S$, at most one of $\\{uv,vw,uw\\}$ is a labeled edge.

###### Proof

Assume to the contrary that there are two edges, say $uv$ and $vw$ are spanned
by vertices in $F$. We show some contradiction.

If edges $uv$ and $vw$ are spanned by two different vertices $x,x^{\prime}\in
F$ respectively, then Reduction Rule 6 could be applied (Case 1 in Figure 4).
Therefore, edges $uv$ and $vw$ are spanned by the same vertex $x\in F$. Since
Reduction Rule 3 is not applied on the four vertices $\\{u,v,w,x\\}$, we know
that at least one edge in $\\{uw,uw,ux,vw,vx,wx\\}$ is contained in a triangle
other than $uwv,uvx,uwx,$ and $vwx$. Due to symmetry, we only need to consider
two edges $vw$ and $xw$.

Assume that edge $vw$ is contained in a triangle $vwy$, where
$y\not\in\\{u,x\\}$. If none of $\\{yv,yw\\}$ appears in $E(S)$, then
Reduction Rule 6 could be applied to replace $uvw$ with two triangles $xvu$
and $yvw$ in $S$. If at least one edge in $\\{yv,yw\\}$ is contained in
$E(S)$, without loss of generality, assume $yw\in E(S)$ and there is a
triangle $ywz\in S$. For this case, Reduction Rule 8 could be applied to
replace $vuw$ and $ywz$ with $xvu$ and $ywz$ (Case 2 in Figure 4).

Assume that edge $xw$ is contained in a triangle $xwy$, where
$y\not\in\\{u,v\\}$. By the maximality of $S$, we know that at least one of
$\\{xy,yw\\}$ must appear in $E(S)$. However, edge $xy$ can not appear in
$E(S)$ since $x\in F$. We know that $wy\in E(S)$ and there is a triangle
$wyz\in S$. For this case, Reduction Rule 8 could be applied to replace $vuw$
and $ywz$ with $xvu$ and $wyz$ (Case 3 in Figure 4).

In any of these cases, we can find a contradiction to the fact that the graph
is reduced. ∎

Figure 4: Three cases in Lemma 6

A triangle $uvw\in S$ is _good_ if it contains a labeled edge and _bad_
otherwise. By Lemma 6, we know that there is exactly one labeled edge in each
good triangle. We let $G^{\prime}$ be the graph obtained by deleting the set
$L$ of labeled edges from $G$. Consider a good triangle $uvw$ with labeled
edge $uv$. If the two edges $vw$ and $wu$ are not in any triangle in
$G^{\prime}$, we call the triangle _excellent_. Otherwise, we call the
triangle _pretty-good_. We let $S_{1}$ denote the set of excellent triangles,
$S_{2}$ denote the set of pretty-good triangles, and $S_{3}$ denotes the set
of bad triangles in $S$. The number of triangles in $S_{1}$, $S_{2}$ and
$S_{3}$ are denoted by $k_{1},k_{2}$, and $k_{3}$, respectively. Let
$V_{1}=V(S_{1})\setminus(V(L)\cup V(S_{2})\cup V(S_{3}))$ and
$V_{2}=V(S_{2})\setminus V(L)$. See Figure 5 for an illustration of these
concepts.

Figure 5: An illustration for triangles and vertices in $G$

###  5.1 The analysis

The discharging method stands as a renowned technique in graph theory, finding
its most notable application in the proof of the famous Four Color Theorem. In
this section, we will use the discharging method to analyze the number of
vertices present in $S_{1}$, $S_{2}$, $S_{3}$, and $F$. The idea of the method
is as follows.

First, we initially assign some integer values to vertices, edges, and
triangles in $S$. The total value assigned is at most $3k$. Subsequently, we
perform steps to update the values, where certain values on vertices, edges,
and triangles are transformed into other vertices, edges, and triangles. In
these steps, we never change the structure of the graph and the total value in
the graph. After performing these transformations, we demonstrate that each
vertex in the graph has a value of at least 1. Consequently, we conclude that
the number of vertices in the graph is at most $3k$.

Initialization: Assign value 3 to each edge in $L$ and each triangle in
$S_{3}$. Edges not in $L$, vertices, and triangles in $S_{1}\cup S_{2}$ are
assigned a value of 0.

By Lemma 6, we know that each of excellent and pretty-good triangles contains
exactly one labeled edge in $L$ and each bad triangle in $S_{3}$ contains no
labeled edge. Thus, the total value in the graph is $3k_{1}+3k_{2}+3k_{3}\leq
3k$.

Step 1: For each labeled edge in $L$, transform a value of 1 to each of its
two endpoints; for each triangle in $S_{3}$, transform a value of 1 to each of
its three vertices.

Figure 6 illustrates the transformation process of Step 1. After Step 1, each
labeled edge has a value of 1, and all triangles have values of 0. Note that
some vertices may have a value of 2 or more, as they may serve as endpoints of
multiple labeled edges and can also be vertices in $V(S_{3})$. However,
vertices in $F\cup V_{1}\cup V_{2}$ still retain a value of 0.

Figure 6: An illustration for Step 1

A _triangle component_ is a connected component in the graph $H=(V(S),E(S))$.
For a vertex $v\in V(S)$, we let $C(v)$ denote the set of vertices in the
triangle component which contain $v$.

Step 2: For each triangle component in $G$, we iteratively transform a value
of 1 from a vertex with a value of at least 2 to a vertex with a value of 0 in
the same triangle component, where vertices in $V_{1}$ have a higher priority
to get the value.

###### Lemma 7

After Step 2, each triangle component has at most one vertex with a value of
0. Moreover,

(i) For any triangle component containing a triangle in $S_{3}$, each vertex
in the triangle component has a value of at least 1;

(ii) For any triangle component containing at least one triangle in $S_{2}$,
if there is a vertex with a value of 0 in the triangle component, then the
vertex must be a vertex in $V_{2}$.

###### Proof

Let $Q$ be a triangle component with $x$ triangles. Since $Q$ is connected, it
contains at most $2x+1$ vertices. Assume that among the $x$ triangles, there
are $x_{1}$ triangles in $S_{1}\cup S_{2}$ and $x_{2}$ triangles in $S_{3}$,
where $x_{1}+x_{2}=x$. By the definition, we know that each triangle in
$S_{1}\cup S_{2}$ contains a distinct labeled edge. According to the
initialization of the assignment, we know that the total value is
$2x_{1}+3x_{2}=2x+x_{2}$. It always holds that $2x+1\leq(2x+x_{2})+1$, and
$2x+1\leq 2x+x_{2}$ when $x_{2}\geq 1$. Thus, $Q$ has at most one vertex with
a value of 0. When $Q$ contains some triangles from $S_{3}$, i.e., $x_{2}\geq
1$, all vertices in $Q$ will get a value of at least 1. The statement (ii)
holds because vertices in $V_{1}$ have a higher priority to receive the value
in Step 2. ∎

After Step 2, only vertices in $F$, some vertices in $V_{1}$, and some
vertices in $V_{2}$ have values of 0. We use the following lemma to transform
some values to vertices in $V_{2}$ with a value of 0.

###### Lemma 8

Consider two triangles $vuw$ and $vxy\in S_{2}$ sharing a common vertex $v$,
where $uv$ and $vx\in L$. If there is an edge $wy\in E$, then $uv$ and $vx$
are spanned by exactly one vertex in $F\cup V_{1}\setminus C(v)$.

Figure 7: An illustration for Lemma 8

###### Proof

Since $vu$ and $vx$ are labeled edges in $L$, we know that each of $vu$ and
$vx$ is spanned by at least one vertex in $F$. Assume to the contrary that
there are two different vertices $q_{1}$ and $q_{2}\in F\cup V_{1}\setminus
C(v)$ that span edges $uv$ and $vx$, respectively. We show some contradiction.
First, none edge in $\\{q_{1}u,q_{1}v,q_{2}v,q_{2}x\\}$ belongs to $E(S)$
since $q_{1}$ and $q_{2}$ are not part of $C(v)$. Thus, Reduction Rule 7 could
be applied to replace triangles $uvw$ and $vxy$ with triangles
$q_{1}uv,q_{2}vx$, and $vwy$, a contradiction to the factor that the graph is
reduced. See Figure 7 for an illustration of the proof. ∎

Step 3: If there are two triangles $vuw$ and $vxy\in S_{2}$ sharing a common
vertex $v$ such that $uv$ and $vx$ are two labeled edges in $L$ and there is
an edge $wy\in E$, we transform a value of 1 from edge $vx$ to the unique
vertex $q_{1}\in F$ spanning $vx$ and transform a value of 1 from edge $uv$ to
the vertex with a value of 0 in $C(v)$ if this vertex exists.

Figure 8: An illustration for Step 3, where the number in parentheses next to
each vertex represents the value of that vertex

See Figure 8 for an illustration of Step 3. We have the following property.

Figure 9: An illustration for Lemma 9

###### Lemma 9

Every vertex in $V_{2}$ has a value of at least 1 after Step 3.

###### Proof

Assume to the contrary there is a vertex $w\in V_{2}$ with a value of 0. We
know that all vertices in $C(w)\setminus\\{w\\}$ have a value of at least 1 by
Lemma 7. Let $wuv\in S_{2}$ be the triangle containing $w$, where $uv$ is the
labeled edge spanning by a vertex $q\in F$. As shown in Figure 9. At least one
of $uw$ and $vw$ is in a triangle in graph $G-L$ by the definition of $S_{2}$.
Without loss of generality, we assume that $uw$ is contained in a triangle
$uwx$, where $x\neq v$. At least one of $ux$ and $wx$ is contained in a
triangle in $S$ otherwise Reduction Rule 6 could be applied.

Case 1: Edge $ux$ is contained in a triangle $uxy\in S$. See Case 1 in Figure
9. The triangle $uxy$ is not in $S_{3}$ otherwise there is a contradiction
that $w$ would have a value of at least 1 by Lemma 7. Thus, triangle $uxy$
must be in $S_{1}\cup S_{2}$ and there is exactly one of $ux$, $uy$, and $xy$
is a labeled edge. Edge $ux$ would not be a labeled edge since triangle $uwx$
is contained in $G-L$. If $xy$ is the labeled edge that is spanned by a vertex
$q^{\prime}\in F$, then Reduction Rule 8 could be applied to replace triangles
$uvw$ and $uxy$ with triangles $uvw$ and $xyq^{\prime}$, a contradiction to
the factor that the graph is reduced. If $uy$ is the labeled edge, then
triangle $uxy\in S_{2}$ since $ux$ is contained in a triangle $uxw\in G-L$.
For this case, the vertex $w$ would have a value of at least 1 by Lemma 7. We
can always find a contradiction.

Case 2: Edge $wx$ is contained in a triangle $wxz\in S$. See Case 2 in Figure
9. If $z\neq q$, then Reduction Rule 8 could be applied to replace triangles
$uvw$ and $wxz$ with triangles $wxz$ and $qvu$, a contradiction to the factor
that the graph is reduced. If $z=q$, then at least two edges in triangle $vuw$
are spanned by vertices in $F$, a contradiction to Lemma 6.

In either case, a contradiction is reached, which implies that the assumption
of a vertex $w\in V_{2}$ having a value of 0 is incorrect. Therefore, every
vertex in $V_{2}$ has a value of at least 1 after Step 3. ∎

After Step 3, all vertices with a value of 0 are in either $F$ or $V_{1}$. We
let $V_{1}^{\prime}$ denote the set of vertices with a value of 0 in $V_{1}$,
$F^{\prime}$ denote the set of vertices with a value of 0 in $F$, and
$L^{\prime}$ denote the set of edges with a value of 1 in $L$ after Step 3. We
give more properties.

###### Lemma 10

Set $F^{\prime}\cup V^{\prime}_{1}$ is an independent set.

###### Proof

We prove that $F\cup V_{1}$ is an independent set, which implies
$F^{\prime}\cup V_{1}^{\prime}$ is an independent set since $F^{\prime}\cup
V_{1}^{\prime}\subseteq F\cup V_{1}$. Assume to the contrary that there is an
edge $uv$ between two vertices in $F\cup V_{1}$. There is at least one
triangle $uvw\in G$ containing $uv$ since Reduction Rule 2 has been applied.
At least one of $uv,vw$, and $uw$ must be in $E(S)$ by the maximality of $S$.

If $uv\in E(S)$, we let $uvx$ be the triangle in $S$ containing $uv$. First,
we know that $u$ and $v\in V_{1}$ since $F\cap V(S)=\emptyset$. By the
definition of $V_{1}$, we get that none of $u$ and $v$ is contained in a
triangle in $S_{3}$ and none of $u$ and $v$ is an endpoint of a labeled edge.
Thus, triangle $uvx$ is not a triangle in $S_{3}$ and it does not contain any
labeled edge and then it is not a triangle in $S_{1}\cup S_{2}$, which implies
triangle $uvx$ is not in $S$, a contradiction.

Otherwise, one of $uw$ and $vw$, say $uw$, is contained in $E(S)$. Let $uwy$
be the triangle in $S$ containing $uw$. We also have that $u\in V_{1}$ since
$F\cap V(S)=\emptyset$. By the definition of $V_{1}$, we know that $u$ is not
a vertex in a triangle in $S_{3}$, and then $uwy$ is not a triangle in
$S_{3}$. Thus, triangle $uwy$ can only be in $S_{1}\cup S_{2}$. Note that none
of $uv$, $vw$ and $uw$ can be a labeled edge since $u$ and $v\in F\cup V_{1}$.
Thus, edge $uw$ is still in a triangle $uvw$ in $G-L$, and then $uwy$ can not
be a triangle in $S_{1}$. However, triangle $uvw$ can not be a triangle in
$S_{2}$ too since $u$ is a vertex in $V_{1}$. We also get a contradiction that
triangle $uvw$ is not in $S$.

Hence, we have shown that no edge exists between any two vertices in
$F^{\prime}\cup V^{\prime}_{1}$, which proves that $F^{\prime}\cup
V^{\prime}_{1}$ forms an independent set. ∎

###### Lemma 11

Vertices in $F^{\prime}$ only span edges in $L^{\prime}$.

###### Proof

Assume to the contrary that there is a vertex $z\in F^{\prime}$ that spans an
edge $e\notin L^{\prime}$. Note that $z\in F$ can only span edges in $L$.
Thus, $e\in L\setminus L^{\prime}$, i.e., the value of $e$ is 0 now. Only Step
3 will create labeled edges with a value of 0. Therefore, edge $e$ appears as
a labeled edge in the graph structure described in Step 3. By Lemma 8, we know
that $z$ is the unique vertex in $F$ spanning $e$ and the value of $z$ is at
least 1 after Step 3, a contradiction to $z\in F^{\prime}$. Thus, vertices
$F^{\prime}$ can only span edges in $L^{\prime}$. ∎

###### Lemma 12

Vertices in $V_{1}^{\prime}$ only span edges in $L^{\prime}$.

Figure 10: Some cases in the proof of Lemma 12

###### Proof

Let $v^{\prime}\in V_{1}^{\prime}$ and $Y$ be the triangle component
containing $v^{\prime}$. First, we show that $N(v^{\prime})\subseteq V(Y)$.

We let $E_{1}$ denote the set of edges with one endpoint being $v^{\prime}$
and the other endpoint being in $N(v^{\prime})\cap V(Y)$ and $E_{2}$ denote
the set of edges with one endpoint being $v^{\prime}$ and the other endpoint
being in $N(v^{\prime})\setminus V(Y)$. Assume that there are edges
$x^{\prime}v^{\prime}\in E_{1}$ and $u^{\prime}v^{\prime}\in E_{2}$ forming a
triangle $x^{\prime}v^{\prime}u^{\prime}$ in $G$ and we show some
contradiction. If $x^{\prime}v^{\prime}\notin E(S)$, then none of
$x^{\prime}v^{\prime}$, $u^{\prime}v^{\prime}$, and $x^{\prime}u^{\prime}$ is
contained in $E(S)$ since $u^{\prime}$ is not in the triangle component
containing $v^{\prime}$. which is a contradiction to the maximality of $S$.
Otherwise $x^{\prime}v^{\prime}\in E(S)$ and we let triangle
$x^{\prime}v^{\prime}y^{\prime}\in S$ be the triangle containing
$x^{\prime}v^{\prime}$. Since the value of $v_{1}$ is 0, by Lemma 7, we know
that $Y$ could not contain any triangle in $S_{2}\cup S_{3}$ and then
$x^{\prime}v^{\prime}y^{\prime}\in S_{1}$. We know that $x^{\prime}y^{\prime}$
is the labeled edge since $v^{\prime}\in V_{1}^{\prime}$. Let $q^{\prime}\in
F$ be the vertex spanning $x^{\prime}y^{\prime}$. We can see that
$q^{\prime}\neq u^{\prime}$ otherwise all the three edges in triangle
$x^{\prime}y^{\prime}v^{\prime}$ are labeled edges spanned by a vertex
$q^{\prime}\in F$, a contradiction to Lemma 6. However, for this case,
Reduction Rule 6 could be applied to replace triangle
$x^{\prime}v^{\prime}y^{\prime}$ with triangles
$q^{\prime}x^{\prime}y^{\prime}$ and $u^{\prime}x^{\prime}v^{\prime}$ in $S$,
a contradiction to the factor that the graph is reduced. Therefore, no
triangle in $G$ contains edges both from $E_{1}$ and $E_{2}$. If both of
$E_{1}$ and $E_{2}$ are not empty, then the condition of Reduction Rule 4
would hold, a contradiction. Since $E_{1}$ can not be empty, we know that
$E_{2}$ is empty. Thus, we have $N(v^{\prime})\subseteq V(Y)$. See Figure
10(a) for an illustration of the proof.

Assuming that $v^{\prime}$ spans an edge $ab$, we can conclude that both $a$
and $b$ are in $V(Y)$ since $N(v^{\prime})$ is a subset of $V(Y)$. Our goal is
to prove that $ab$ belongs to $L$. If $ab\in E(S)\setminus L$, then $ab$ is
contained in a triangle $abd\in S_{1}$ since $Y$ contains only triangles in
$S_{1}$. We have $d\neq v^{\prime}$, otherwise the triangle $abv^{\prime}\in
S_{1}$ would have no labeled edge, a contradiction. The triangle $abd\in
S_{1}$ contains an edge $ab$ which will be in a triangle $abv^{\prime}$ in
$G-L$, which contradicts the definition of $S_{1}$ (See Figure 10(b)). If
$ab\not\in E(S)$, then at least one of $bv^{\prime}$ and $av^{\prime}$, say
$bv^{\prime}$, is contained in $E(S)$ by the maximality of $S$. Let
$bv^{\prime}c\in S_{1}$ be the triangle containing $bv^{\prime}$ where $c\neq
a$ since $ab\not\in E(S)$. The triangle $bcv^{\prime}\in S_{1}$ contains an
edge $bv^{\prime}$ which will be in a triangle $abv^{\prime}$ in $G-L$, which
contradicts the definition of $S_{1}$ (See Figure 10(c)). Thus, it holds that
$ab\in L$. Any vertex $v^{\prime}\in V_{1}^{\prime}$ only span edges $ab\in
L$, where both $a$ and $b$ are in $V(Y)$. Then, edge $ab$ can only be a
labeled edge in a triangle in $S_{1}$. Since all labeled edges in triangles in
$S_{1}$ are in $L^{\prime}$, we know that vertices in $V_{1}^{\prime}$ can
only span edges in $L^{\prime}$. ∎

###### Lemma 13

After Step 3, it holds that $|F^{\prime}\cup V_{1}^{\prime}|\leq|L^{\prime}|$.

###### Proof

By Lemma 10, 11, and 12, we know that $F^{\prime}\cup V_{1}^{\prime}$ is an
independent set and any vertex $v^{\prime}\in F^{\prime}\cup V_{1}^{\prime}$
only span edges in $L^{\prime}$. If $|F^{\prime}\cup
V_{1}^{\prime}|>|L^{\prime}|$, then by Lemma 1 there is a fat-head crown
decomposition $(C,H,X)$ of $G$ with $C\subseteq F^{\prime}\cup V_{1}^{\prime}$
and $H\subseteq L^{\prime}$. Moreover, the fat-head crown decomposition can be
detected by Lemma 2 and will be handled by Reduction Rule 9 since
$F^{\prime}\cup V_{1}^{\prime}\subseteq F\cup V_{1}\subseteq V\setminus V(L)$
and $L^{\prime}\subseteq L$. Thus, we know the lemma holds. ∎

Step 4: We transform value from edges in $L^{\prime}$ to vertices in
$F^{\prime}\cup V_{1}^{\prime}$ such that each vertex in $F^{\prime}\cup
V_{1}^{\prime}$ gets value at least 1 by Lemma 13.

After Step 4, each vertex in $G$ has a value of at least 1. Since the total
value in $G$ is at most $3k$, we can conclude that the graph has at most $3k$
vertices.

###### Theorem 5.1

Edge Triangle Packing and Edge Triangle Covering admit a kernel of at most
$3k$ vertices.

##  6 Conclusion

In this paper, we present simultaneous improvements in the kernel results for
both Edge Triangle Packing and Edge Triangle Covering. Our approach
incorporates two key techniques to achieve these enhancements. The first
technique involves utilizing fat-head crown decomposition, which enables us to
effectively reduce various graph structures. By applying this technique, we
can simplify the problem instances. The second technique we introduce is the
discharging method, which plays a crucial role in analyzing kernel size. This
method is simple and intuitive, and we believe it has the potential to be
applied to the analysis of other kernel algorithms.

Acknowledgments. The work is supported by the National Natural Science
Foundation of China, under the grants 62372095 and 61972070.

## References

  * [1] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Parameterized Algorithms, Springer, 2015.
  * [2] I. Holyer, The NP-completeness of some edge-partition problems, SIAM J. Comput. 10 (4) (1981) 713–717.
  * [3] V. Kann, Maximum bounded h-matching is MAX snp-complete, Inf. Process. Lett. 49 (6) (1994) 309–318.
  * [4] C. A. J. Hurkens, A. Schrijver, On the size of systems of sets every t of which have an sdr, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discret. Math. 2 (1) (1989) 68–72.
  * [5] B. S. Baker, Approximation algorithms for np-complete problems on planar graphs, J. ACM 41 (1) (1994) 153–180.
  * [6] L. Mathieson, E. Prieto-Rodriguez, P. Shaw, Packing edge disjoint triangles: A parameterized view, in: Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings, Vol. 3162 of Lecture Notes in Computer Science, Springer, 2004, pp. 127–137.
  * [7] Y. Yang, Towards optimal kernel for edge-disjoint triangle packing, Inf. Process. Lett. 114 (7) (2014) 344–348.
  * [8] W. Lin, M. Xiao, A (3+$\epsilon$)_k_ -vertex kernel for edge-disjoint triangle packing, Inf. Process. Lett. 142 (2019) 20–26.
  * [9] H. Yuan, Q. Feng, J. Wang, Improved kernels for triangle packing in tournaments, Sci. China Inf. Sci. 66 (5) (2023).
  * [10] D. Brügmann, C. Komusiewicz, H. Moser, On generating triangle-free graphs, Electron. Notes Discret. Math. 32 (2009) 51–58.
  * [11] F. K. H. A. Dehne, M. R. Fellows, F. A. Rosamond, P. Shaw, Greedy localization, iterative compression, modeled crown reductions: New FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover, in: Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings, Vol. 3162 of Lecture Notes in Computer Science, Springer, 2004, pp. 271–280.
  * [12] M. Xiao, S. Kou, Parameterized algorithms and kernels for almost induced matching, Theor. Comput. Sci. 846 (2020) 103–113.
  * [13] M. Xiao, S. Kou, Kernelization and parameterized algorithms for 3-path vertex cover, in: Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings, Vol. 10185 of Lecture Notes in Computer Science, 2017, pp. 654–668.
  * [14] R. Cervený, P. Choudhary, O. Suchý, On kernels for d-path vertex cover, in: 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria, Vol. 241 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 29:1–29:14.
  * [15] H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, D. M. Thilikos, (meta) kernelization, J. ACM 63 (5) (2016) 44:1–44:69.