# Non-zero sum Heffter arrays and their applications

Simone Costa  DICATAM - Sez. Matematica, Università degli Studi di Brescia,
Via Branze 43, I-25123 Brescia, Italy<EMAIL_ADDRESS>,  Stefano Della
Fiore  DII, Università degli Studi di Brescia, Via Branze 38, I-25123 Brescia,
Italy<EMAIL_ADDRESS>and  Anita Pasotti  DICATAM - Sez. Matematica,
Università degli Studi di Brescia, Via Branze 43, I-25123 Brescia, Italy
<EMAIL_ADDRESS>
###### Abstract.

In this paper we introduce a new class of partially filled arrays that, as
Heffter arrays, are related to difference families, graph decompositions and
biembeddings. A _non-zero sum Heffter array_ $\mathrm{N}\mathrm{H}(m,n;h,k)$
is an $m\times n$ p. f. array with entries in $\mathbb{Z}_{2nk+1}$ such that:
each row contains $h$ filled cells and each column contains $k$ filled cells;
for every $x\in\mathbb{Z}_{2nk+1}\setminus\\{0\\}$, either $x$ or $-x$ appears
in the array; the sum of the elements in every row and column is different
from $0$ (in $\mathbb{Z}_{2nk+1}$). Here first we explain the connections with
relative difference families and with path decompositions of the complete
multipartite graph. Then we present a complete solution for the existence
problem and a constructive complete solution for the square case and for the
rectangular case with no empty cells when the additional, very restrictive,
property of “globally simple” is required. Finally, we show how these arrays
can be used to construct biembeddings of complete graphs.

###### Key words and phrases:

Heffter array, orthogonal cyclic path decomposition, complete multipartite
graph, embedding

###### 2010 Mathematics Subject Classification:

05B20; 05C10; 05C38

##  1\. Introduction

An $m\times n$ partially filled (p.f., for short) array on a set $\Omega$ is
an $m\times n$ matrix whose elements belong to $\Omega$ and where some cells
can be empty. In 2015 Archdeacon [3] introduced a class of p.f. arrays which
has been extensively studied: the _Heffter arrays_.

######  Definition 1.1.

A _Heffter array_ $\mathrm{H}(m,n;h,k)$ is an $m\times n$ p. f. array with
entries in $\mathbb{Z}_{2nk+1}$ such that:

  * (a)

each row contains $h$ filled cells and each column contains $k$ filled cells;

  * (b)

for every $x\in\mathbb{Z}_{2nk+1}\setminus\\{0\\}$, either $x$ or $-x$ appears
in the array;

  * (c)

the elements in every row and column sum to $0$ (in $\mathbb{Z}_{2nk+1}$).

Trivial necessary conditions for the existence of a $\mathrm{H}(m,n;h,k)$ are
$mh=nk$, $3\leq h\leq n$ and $3\leq k\leq m$. If $m=n$ then $h=k$ and a square
$\mathrm{H}(n,n;k,k)$ will be simply denoted by $\mathrm{H}(n;k)$. The
following result has been proved in [5, 14, 24].

######  Theorem 1.2.

A $\mathrm{H}(n;k)$ exists for every $n\geq k\geq 3$.

In [21] this concept has been generalized as follows.

######  Definition 1.3.

Let $v=\frac{2nk}{\lambda}+t$ be a positive integer, where $t$ divides
$\frac{2nk}{\lambda}$, and let $J$ be the subgroup of $\mathbb{Z}_{v}$ of
order $t$. A $\lambda$-_fold Heffter array $A$ over $\mathbb{Z}_{v}$ relative
to $J$_, denoted by ${}^{\lambda}\mathrm{H}_{t}(m,n;h,k)$, is an $m\times n$
p.f. array with elements in $\mathbb{Z}_{v}$ such that:

  * ($\rm{a_{1}})$

each row contains $h$ filled cells and each column contains $k$ filled cells;

  * ($\rm{b_{1}})$

the multiset $\\{\pm x\mid x\in A\\}$ contains each element of
$\mathbb{Z}_{v}\setminus J$ exactly $\lambda$ times;

  * ($\rm{c_{1}})$

the elements in every row and column sum to $0$ (in $\mathbb{Z}_{v}$).

It is easy to see that if $\lambda=t=1$ we find again the arrays of Definition
1.1.

Classical Heffter arrays and the above generalization have been introduced
also in view of their vast variety of applications and connections with other
much studied problems and concepts. In particular there are some recent papers
in which Heffter arrays are investigated to obtain new face $2$-colorable
embeddings (briefly biembeddings) see [3, 15, 19, 20, 21, 23]. On the other
hand several authors focused their attention on the existence problem, see [4,
5, 12, 14, 17, 24, 29, 30, 31].

Here we introduce a new class of p.f. arrays, which is related to the one of
Heffter arrays.

######  Definition 1.4.

Let $v=\frac{2nk}{\lambda}+t$ be a positive integer, where $t$ divides
$\frac{2nk}{\lambda}$, and let $J$ be the subgroup of $\mathbb{Z}_{v}$ of
order $t$. A _non-zero sum_ $\lambda$-_fold Heffter array $A$ over
$\mathbb{Z}_{v}$ relative to $J$_, denoted by
${}^{\lambda}\mathrm{N}\mathrm{H}_{t}(m,n;h,k)$, is an $m\times n$ p.f. array
with elements in $\mathbb{Z}_{v}$ such that:

  * ($\rm{a_{2}})$

each row contains $h$ filled cells and each column contains $k$ filled cells;

  * ($\rm{b_{2}})$

the multiset $\\{\pm x\mid x\in A\\}$ contains each element of
$\mathbb{Z}_{v}\setminus J$ exactly $\lambda$ times;

  * ($\rm{c_{2}})$

the sum of the elements in every row and column is different from $0$ (in
$\mathbb{Z}_{v}$).

Here we focus our attention on the case $\lambda=1$, namely when the entries
of the array are pairwise distinct. If the array is square then $h=k\geq 1$,
while if $m\neq n$ then at least one of $h$ and $k$ has to be greater than
$1$. As done for Heffter arrays, a square non-zero sum Heffter array will be
simply denoted by $\mathrm{N}\mathrm{H}(n;k)$.

This definition is motivated by Alspach’s partial sums conjecture that deals
with sets whose sum is different from $0$. In particular the truth of this
conjecture would show that any $\mathrm{N}\mathrm{H}_{t}(m,n;h,k)$ provides
two orthogonal path decompositions of $K_{\frac{2nk+t}{t}\times t}$.

The relations between non-zero sum Heffter arrays, Alspach’s conjecture and
orthogonal path decompositions will be explained in detail in Section 2. Then
we will analyze the existence problem for $\mathrm{N}\mathrm{H}_{t}(m,n;h,k)$.
In particular, in Section 3, we will show a construction that completely
solves the square case when $t=1$ (but, assuming the existence of a
$\mathrm{H}_{t}(n;k)$, it works also for $t>1$) and, in Section 4, using a
probabilistic approach, we will provide a complete solution to the general
case. Moreover, in Section 5, we will construct $k$-diagonal square non-zero
sum Heffter arrays and rectangular ones with no empty cells that satisfy the
very restrictive property of being “globally simple”. Finally, in the last
section, we will show how these arrays can be used to construct $2$-colorable
embeddings of complete graphs and we will prove some existence theorems about
biembeddings.

##  2\. Relations with orthogonal path decompositions

In this section we explain the relation between non-zero sum Heffter arrays,
difference families and orthogonal decompositions. To do this we have to
introduce some concepts and notation.

Given a finite subset $T$ of an abelian group $G$ and an ordering
$\omega=(t_{1},t_{2},\ldots,t_{k})$ of the elements in $T$, let
$s_{i}=\sum_{j=1}^{i}t_{j}$, for any $i=1,\ldots,k$, be the $i$-th partial sum
of $T$. The ordering $\omega$ is said to be _simple_ if $s_{b}\neq s_{c}$ for
all $1\leq b<c\leq k$ or, equivalently, if there is no proper subsequence of
$\omega$ that sums to $0$. If $\omega$ is a simple ordering then also
$\omega^{-1}=(t_{k},t_{k-1},\ldots,t_{1})$ is simple. We point out that there
are several problems and conjectures about distinct partial sums. For
instance, several years ago Alspach made the following conjecture, whose
validity would shorten some cases of known proofs about the existence of cycle
decompositions.

######  Conjecture 2.1.

Let $A\subseteq\mathbb{Z}_{v}\setminus\\{0\\}$ such that $\sum_{a\in A}a\neq
0$. Then there exists an ordering of the elements of $A$ such that the partial
sums are all distinct and non-zero.

Conjecture 2.1 has been proved for subsets $A$ of size $k$ of $\mathbb{Z}_{v}$
whenever

  * (1)

$k\leq 9$ or $k=10$ and $v$ is a prime (see [3, 26]);

  * (2)

$k\in\\{v-1,v-2\\}$ or $k=v-3$ and $v$ is a prime (see [3, 7, 26]);

  * (3)

$v\leq 25$ (see [6]);

  * (4)

the prime power factors of $v$ are greater than a suitable constant $N$ and
$k\leq 11$ (see [22]).

Other problems related to the previous one have been proposed in [2, 6, 18,
32].

Given an $m\times n$ p.f. array $A$, the rows and the columns of $A$ are
denoted by ${R}_{1},\ldots,{R}_{m}$ and by ${C}_{1},\ldots,{C}_{n}$,
respectively. We denote by $\mathcal{E}(A)$ the list of the elements of the
filled cells of $A$ and by $\mathcal{E}({R}_{i})$, $\mathcal{E}({C}_{j})$, the
elements of the $i$-th row, of the $j$-th column, respectively, of $A$. Also,
by $\omega_{{R}_{i}}$ and $\omega_{{C}_{j}}$ we denote, respectively, an
ordering of $\mathcal{E}({R}_{i})$ and of $\mathcal{E}({C}_{j})$. If for any
$i=1,\ldots,m$ and for any $j=1,\ldots,n$, the orderings $\omega_{{R}_{i}}$
and $\omega_{{C}_{j}}$ are simple, we define by
$\omega_{r}=\omega_{{R}_{1}}\circ\ldots\circ\omega_{{R}_{m}}$ the simple
ordering for the rows and by
$\omega_{c}=\omega_{{C}_{1}}\circ\ldots\circ\omega_{{C}_{n}}$ the simple
ordering for the columns. Also, by _natural ordering_ of a row (column) of $A$
one means the ordering from left to right (from top to bottom). A p.f. array
$A$ on an abelian group $G$ is said to be

  * •

_simple_ if there exists a simple ordering for each row and each column of
$A$;

  * •

_globally simple_ if the natural ordering of each row and each column of $A$
is simple.

######  Remark 2.2.

We note that, if Conjecture 2.1 would be true, then any
$\mathrm{N}\mathrm{H}_{t}(m,n;h,k)$ would be simple. Moreover, if $h,k\leq 3$,
then every non-zero sum Heffter array is globally simple.

Given a graph $\Gamma$, we denote by $V(\Gamma)$ and $E(\Gamma)$ the vertex-
set and the edge-set of $\Gamma$, respectively, and by ${}^{\lambda}\Gamma$
the multigraph obtained from $\Gamma$ by repeating each edge $\lambda$ times.
Also by $K_{v}$, $K_{q\times r}$, $C^{\prime}_{k}$, $P_{k}$ we represent the
complete graph on $v$ vertices, the complete multipartite graph with $q$ parts
each of size $r$, the cycle of length $k$ and the path of length $k$ on $k+1$
distinct vertices, respectively. Given a subgraph $\Gamma$ of a graph $K$, a
$\Gamma$-decomposition of $K$ is a set of graphs (said blocks), all isomorphic
to $\Gamma$, whose edge-sets partition the edge-set of $K$, see for instance
[8]. Given an additive group $G$, a $\Gamma$-decomposition $\mathcal{D}$ of a
graph $K$ is $G$-regular if, up to isomorphisms, $V(K)=G$ and for any
$B\in{\mathcal{D}}$ also the graph $B+g$ is a block of ${\mathcal{D}}$ for any
$g\in G$. Here we will work with cyclic $P_{k}$-decompositions, namely
decompositions into paths regular under the cyclic group. It is well known
that difference families are a very useful tool for constructing regular
decompositions. We recall the definition, see [1, 9].

######  Definition 2.3.

Let $\Gamma$ be a graph with vertices in an additive group $G$. The multiset
$\Delta\Gamma=\\{\pm(x-y)\mid\\{x,y\\}\in E(\Gamma)\\}$ is called the _list of
differences_ from $\Gamma$.

More generally, given a set $\mathcal{W}$ of graphs with vertices in $G$, by
$\Delta\mathcal{W}$ one means the union (counting multiplicities) of all
multisets $\Delta\Gamma$, where $\Gamma\in\mathcal{W}$.

######  Definition 2.4.

Let $J$ be a subgroup of an additive group $G$ and let $\Gamma$ be a graph. A
collection $\mathcal{F}$ of graphs isomorphic to $\Gamma$ and with vertices in
$G$ is said to be a $(G,J,\Gamma,\lambda)$-_difference family_ (briefly, DF)
_over $G$ relative to_ $J$ if each element of $G\setminus J$ appears exactly
$\lambda$ times in the list of differences of $\mathcal{F}$ while no element
of $J$ appears there.

If $\lambda=t=1$ one speaks of a $(G,\Gamma,1)$-DF. Moreover, if $t$ is a
divisor of $v$, a
$(\mathbb{Z}_{v},\frac{v}{t}\mathbb{Z}_{v},\Gamma,\lambda)$-DF, where
$\frac{v}{t}\mathbb{Z}_{v}$ denotes the subgroup of $\mathbb{Z}_{v}$ of order
$t$, is simply denoted by $(v,t,\Gamma,\lambda)$-DF. The connection between
relative difference families and decompositions of a complete multipartite
multigraph is given by the following result.

######  Proposition 2.5.

[10, Proposition 2.6] If $\mathcal{F}=\\{B_{1},\ldots,B_{\ell}\\}$ is a
$(G,J,\Gamma,\lambda)$-DF, then $\mathcal{B}=\\{B_{i}+g\mid
i=1,\ldots,\ell;g\in G\\}$ is a $G$-regular $\Gamma$-decomposition of
${}^{\lambda}K_{q\times r}$, where $q=|G:J|$ and $r=|J|$. Hence, if
$\mathcal{F}$ is a $(G,\Gamma,1)$-DF there exists a $G$-regular
$\Gamma$-decomposition of $K_{|G|}$.

It is well know, see for instance [19], that if there exists a simple
$\mathrm{H}_{t}(m,n;h,k)$, then there exist a $(2mh+t,t,C^{\prime}_{h},$
$1)$-DF and a $(2nk+t,t,C^{\prime}_{k},1)$-DF. In a similar way one can prove
the following.

######  Proposition 2.6.

If there exists a simple $\mathrm{N}\mathrm{H}_{t}(m,n;h,k)$, then there exist
a $(2mh+t,t,P_{h},1)$-DF and a $(2nk+t,t,P_{k},1)$-DF.

######  Remark 2.7.

Let $\mathcal{F}_{h}$ and $\mathcal{F}_{k}$ be the relative DFs constructed in
the previous proposition. Note that for any $P_{h}\in\mathcal{F}_{h}$ and any
$P_{k}\in\mathcal{F}_{k}$, we have $|\Delta P_{h}\cap\Delta
P_{k}|\in\\{0,2\\}.$

We recall the following definition, see for instance [13].

######  Definition 2.8.

Two graph decompositions $\mathcal{D}$ and $\mathcal{D}^{\prime}$ of a simple
graph $K$ are said _orthogonal_ if and only if for any $B$ of $\mathcal{D}$
and any $B^{\prime}$ of $\mathcal{D}^{\prime}$, $B$ intersects $B^{\prime}$ in
at most one edge.

Heffter arrays are also used for getting orthogonal cycle decompositions, see
for instance [11]. Analogously from non-zero sum Heffter arrays one can
construct orthogonal path decompositions as shown by the following result.

######  Proposition 2.9.

Let $A$ be a $\mathrm{N}\mathrm{H}_{t}(m,n;h,k)$ simple with respect to the
orderings $\omega_{r}$ and $\omega_{c}$. Then:

  * (1)

there exists a cyclic $h$-path decomposition $\mathcal{D}_{\omega_{r}}$ of
$K_{\frac{2mh+t}{t}\times t}$;

  * (2)

there exists a cyclic $k$-path decomposition $\mathcal{D}_{\omega_{c}}$ of
$K_{\frac{2nk+t}{t}\times t}$;

  * (3)

the decompositions $\mathcal{D}_{\omega_{r}}$ and $\mathcal{D}_{\omega_{c}}$
are orthogonal.

###### Proof.

(1) and (2) follow from Propositions 2.5 and 2.6. Then (3) follows from Remark
2.7. ∎

We point out that the notion of simple array can be extended also to
${}^{\lambda}\mathrm{N}\mathrm{H}_{t}(m,n;h,k)$ with $\lambda>1$, similar to
what was done in [21] for Heffter arrays. Then reasoning as above one can get
two path decompositions of the $\lambda$-fold multipartite complete graph, but
in this case the decompositions are not orthogonal.

######  Example 2.10.

Consider the $\mathrm{N}\mathrm{H}(3,4;4,3)$, say $A$, below.

$\begin{array}[]{|r|r|r|r|}\hline\cr 1&10&-11&2\\\ \hline\cr 8&6&-3&5\\\
\hline\cr-7&12&9&4\\\ \hline\cr\end{array}$

Firstly we find simple orderings for the rows and the columns of $A$. Note
that, for instance, the natural orderings from left to right of the first row
and of the third row are not simple. While every ordering of the columns is
simple since $k=3$.

Set, for instance:

$\displaystyle\omega_{1}$ $\displaystyle=(1,2,10,-11),$ $\displaystyle\nu_{1}$
$\displaystyle=(1,8,-7),$ $\displaystyle\omega_{2}$
$\displaystyle=(8,6,-3,5),$ $\displaystyle\nu_{2}$ $\displaystyle=(10,6,12),$
$\displaystyle\omega_{3}$ $\displaystyle=(4,-7,12,9),$ $\displaystyle\nu_{3}$
$\displaystyle=(-11,-3,9),$ $\displaystyle\nu_{4}$ $\displaystyle=(2,5,4).$

Starting from these orderings we obtain the following paths:

$\displaystyle P_{\omega_{1}}$ $\displaystyle=[0,1,3,13,2],$ $\displaystyle
P_{\nu_{1}}$ $\displaystyle=[0,1,9,2],$ $\displaystyle P_{\omega_{2}}$
$\displaystyle=[0,8,14,11,16],$ $\displaystyle P_{\nu_{2}}$
$\displaystyle=[0,10,16,3],$ $\displaystyle P_{\omega_{3}}$
$\displaystyle=[0,4,22,9,18],$ $\displaystyle P_{\nu_{3}}$
$\displaystyle=[0,14,11,20],$ $\displaystyle P_{\nu_{4}}$
$\displaystyle=[0,2,7,11].$

Set $\mathcal{F}_{\omega}=\\{P_{\omega_{i}}\mid i=1,\ldots,3\\}$ and
$\mathcal{F}_{\nu}=\\{P_{\nu_{i}}\mid i=1,\ldots,4\\}$; by the construction of
the paths it immediately follows that
$\Delta\mathcal{F}_{\omega}=\Delta\mathcal{F}_{\nu}=\mathbb{Z}_{25}\setminus\\{0\\}$.
Hence $\mathcal{F}_{\omega}$ is a $(25,P_{4},1)$-DF and $\mathcal{F}_{\nu}$ is
a $(25,P_{3},1)$-DF. Set ${\mathcal{D}}_{\omega}=\\{P_{\omega_{i}}+g\mid
i=1,\ldots,3,g\in\mathbb{Z}_{25}\\}$ and
${\mathcal{D}}_{\nu}=\\{P_{\nu_{i}}+g\mid
i=1,\ldots,4,g\in\mathbb{Z}_{25}\\}$. Then $\mathcal{D}_{\omega}$ is a cyclic
$P_{4}$-decomposition of $K_{25}$, $\mathcal{D}_{\nu}$ is a cyclic
$P_{3}$-decomposition of $K_{25}$. Moreover, $\mathcal{D}_{\omega}$ and
$\mathcal{D}_{\nu}$ are orthogonal.

##  3\. A constructive complete solution for the square case

In this section we present a complete solution for the existence of a
$\mathrm{N}\mathrm{H}(n;k)$ for any $n\geq k\geq 1$.

######  Remark 3.1.

The existence of a globally simple $\mathrm{N}\mathrm{H}(n;1)$, say
$A=(a_{i,j})$, for every $n\geq 1$ is trivial. In fact it is sufficient to set
$a_{i,i}=i$ for every $i=1,\ldots,n$, while all other cells are empty.

######  Proposition 3.2.

For every $n\geq 2$, there exists a globally simple
$\mathrm{N}\mathrm{H}(n;2)$.

###### Proof.

Let $A=(a_{i,j})$ be an $n\times n$ matrix with $n\geq 2$. Set $a_{i,i}=i$ and
$a_{i,i+1}=n+i$ for every $i=1,\ldots,n$, where the subscript are considered
modulo $n$. It is immediate to see that $A$ is a $\mathrm{N}\mathrm{H}(n;2)$.
∎

We recall that given a square matrix $A$ of order $n$ a _transversal_ of $A$
is a set of $n$ filled cells such that no two belong to the same row and no
two belong to the same column.

######  Lemma 3.3.

A square p.f. array with $k\geq 1$ filled cells in each row and in each column
admits a transversal.

###### Proof.

Let $A$ be an $n\times n$ array as in the statement. Associate to $A$ a
bipartite graph, say $\Gamma$, on $2n$ vertices, in which the vertices of one
part represent the $n$ rows and the vertices of the other part represent the
$n$ columns of $A$ and there is an edge connecting two vertices if and only if
the cell of the corresponding row and column is not an empty cell. Note that a
transversal of $A$ is nothing but a perfect matching of $\Gamma$ which, by
construction, is $k$-regular and it is well-known that a regular and bipartite
graph admits a perfect matching. ∎

######  Theorem 3.4.

If there exists a $\mathrm{H}_{t}(n;k)$ then there also exists a
$\mathrm{N}\mathrm{H}_{t}(n;k)$.

###### Proof.

Let $A$ be a $\mathrm{H}_{t}(n;k)$. By Lemma 3.3, there exists a transversal
$T$ of $A$ containing $n$ filled cells. Let $H$ be the matrix obtained from
$A$ by changing the signs of the elements of $T$ and leaving all other cells
unchanged. Note that to prove that $H$ is a $\mathrm{N}\mathrm{H}_{t}(n;k)$ we
have only to check condition ($\rm{c_{2}})$ of Definition 1.4. Now we remark
that if $t$ is odd, $\mathbb{Z}_{2nk+t}$ does not contain an involution, while
if $t$ is even the involution of $\mathbb{Z}_{2nk+t}$ belongs to the subgroup
of order $t$ of $\mathbb{Z}_{2nk+t}$. Hence, in any case, $A$ does not contain
the involution. Also, we recall that $A$ is a $\mathrm{H}_{t}(n;k)$ hence each
row and each column of $A$ sums to zero. It follows that changing the sign of
exactly one element in each row and in each column of $A$ all the sums are now
different from zero. The result follows. ∎

######  Corollary 3.5.

For every $n\geq k\geq 1$ there exists a $\mathrm{N}\mathrm{H}(n;k)$.

###### Proof.

If $k=1$ or $k=2$ the result follows from Remark 3.1 and Proposition 3.2,
respectively. For $k\geq 3$, the result follows from Theorems 1.2 and 3.4. ∎

In the next section we will present a generalization of the previous
corollary, whose proof is not constructive.

######  Example 3.6.

Here we have the $\mathrm{H}(7;5)$ constructed in [5]. Note that the cells
with bold elements form a transversal of the array.

$\begin{array}[]{|r|r|r|r|r|r|r|}\hline\cr\bf{-10}&&16&-1&-2&-3&\\\
\hline\cr&\bf{-4}&&-6&-7&-5&22\\\ \hline\cr-30&29&\bf{-9}&-8&&&18\\\
\hline\cr-11&&-12&\bf{28}&-31&26&\\\ \hline\cr&-14&-15&-13&&\bf{17}&25\\\
\hline\cr 27&-34&20&&\bf{19}&&-32\\\ \hline\cr 24&23&&&21&-35&\bf{-33}\\\
\hline\cr\end{array}$

Applying the proof of Theorem 3.4 we get the $\mathrm{N}\mathrm{H}(7;5)$
below.

$\begin{array}[]{|r|r|r|r|r|r|r|}\hline\cr 10&&16&-1&-2&-3&\\\
\hline\cr&4&&-6&-7&-5&22\\\ \hline\cr-30&29&9&-8&&&18\\\
\hline\cr-11&&-12&-28&-31&26&\\\ \hline\cr&-14&-15&-13&&-17&25\\\ \hline\cr
27&-34&20&&-19&&-32\\\ \hline\cr 24&23&&&21&-35&33\\\ \hline\cr\end{array}$

##  4\. A complete solution for the rectangular case

In this section we prove the existence of a
$\mathrm{N}\mathrm{H}_{t}(m,n;h,k)$ whenever the trivially necessary
conditions $m\geq k\geq 1$, $n\geq h\geq 1$, $nk=mh$ and $t|2nk$ are
satisfied.

######  Lemma 4.1.

Let $m\geq k\geq 1$ and $n\geq h\geq 1$ be such that $nk=mh$. Then there
exists an $m\times n$ p.f. array $A$ that has exactly $h$ filled cells in each
row and exactly $k$ filled cells in each column.

###### Proof.

Let $m,n,h,k$ be as in the statement. Let $S$ be the subgroup of
$\mathbb{Z}_{m}\times\mathbb{Z}_{n}$ generated by $(1,1)$. It is not hard to
see that the order of $S$ is equal to $\text{lcm}(m,n)$. Now consider the
$m\times n$ empty array, say $A$, whose rows represent the elements of
$\mathbb{Z}_{m}$ while the columns represent the elements of $\mathbb{Z}_{n}$.
One can check that filling exactly the cells of $A$ correspoding to the
elements of the subgroup $S$, we get a p.f. array with exactly
$\frac{\text{lcm}(m,n)}{m}$ filled cells in each row and
$\frac{\text{lcm}(m,n)}{n}$ filled cells in each column. Now note that
$\text{lcm}(m,n)$ divides $nk=mh$ and set $r=\frac{nk}{\text{lcm}(m,n)}$.
Consider $r$ distinct cosets of $S$ in $\mathbb{Z}_{m}\times\mathbb{Z}_{n}$.
Filling exactly the cells of $A$ corresponding to the elements of these cosets
we obtain the required array. ∎

######  Theorem 4.2.

For every $m\geq k\geq 1$, $n\geq h\geq 1$ and $t$ such that $nk=mh$ and
$t|2nk$ there exists a $\mathrm{N}\mathrm{H}_{t}(m,n;h,k)$.

###### Proof.

If $m=1$, which implies $k=1$ and $n=h$, take an arbitrary subset $S$ of
$\mathbb{Z}_{2n+t}\setminus\frac{2n+t}{t}\mathbb{Z}_{2n+t}$ of size $n$ which
does not contain pairs of the form $\\{x,-x\\}$ for some
$x\in\mathbb{Z}_{2n+t}$. Note that such a set $S$ exists since
$\mathbb{Z}_{2n+t}\setminus\frac{2n+t}{t}\mathbb{Z}_{2n+t}$ does not contain
the involution (if it exists). Let $A$ be a $1\times n$ array filled with the
elements of $S$. If the row of $A$ does not sum to zero, $A$ is a
$\mathrm{N}\mathrm{H}_{t}(1,n;n,1)$, otherwise, it is sufficient to change the
sign of an element in $A$ and the new array is a
$\mathrm{N}\mathrm{H}_{t}(1,n;n,1)$. Clearly if $n=1$ one can reason in the
same way.

So in the following we can assume $m,n\geq 2$. Let $S$ be a subset of
$\mathbb{Z}_{2nk+t}\setminus\frac{2nk+t}{t}\mathbb{Z}_{2nk+t}$ of size $nk$
and such that, for every
$x\in\mathbb{Z}_{2nk+t}\setminus\frac{2nk+t}{t}\mathbb{Z}_{2nk+t}$, exactly
one of $x$ or $-x$ appears in $S$. As before, such a set $S$ exists since
$\mathbb{Z}_{2nk+t}\setminus\frac{2nk+t}{t}\mathbb{Z}_{2nk+t}$ does not
contain the involution (if it exists). We also consider an $m\times n$ p.f.
array $A$ having exactly $h$ filled cells in each row and exactly $k$ filled
cells in each column whose existence follows by Lemma 4.1. Now, we prove that
we can write the elements of $S$ in the filled cells of $A$ so that the sum
over each row and column is non-zero. For this purpose, we fill $A$, uniformly
at random, with the elements of $S$. Then we evaluate the expected value
$\mathbb{E}(X)$ of the random variable $X$ given by the number of rows that
sum to zero.

Due to the linearity of $\mathbb{E}(X)$ we have that:

$\mathbb{E}(X)=\sum_{i=1}^{m}\mathbb{P}\left(\sum_{x\in{R}_{i}}x=0\right).$

For symmetry,
$\mathbb{P}(\sum_{x\in{R}_{i}}x=0)=\mathbb{P}(\sum_{x\in{R}_{1}}x=0)$ for
every $i=1,\ldots,m$, and hence

$\mathbb{E}(X)=m\cdot\mathbb{P}\left(\sum_{x\in{R}_{1}}x=0\right).$

Now we want to give an upper-bound for the term
$\mathbb{P}(\sum_{x\in{R}_{1}}x=0)$. We note that, if $h\in\\{1,2\\}$, this
probability is zero since neither $0$ nor pairs of the form $\\{x,-x\\}$ are
contained in $S$. Therefore, we can suppose $h\geq 3$. Let us assume we have
already chosen the first $h-1$ elements, $x_{1},\dots,x_{h-1}$, of ${R}_{1}$.
Then there exists at most one $\bar{x}\in S\setminus\\{x_{1},\dots,x_{h-1}\\}$
that makes the sum zero. This means that

$\mathbb{P}\left(\sum_{x\in{R}_{1}}x=0\right)\leq\frac{1}{mh-(h-1)}$

and hence

$\mathbb{E}(X)\leq\frac{m}{mh-(h-1)}.$

Note that, since $m\geq 2$ and $h\geq 3$, we obtain:

(4.1) $\displaystyle 2m+(h-1)\leq 2m+m(h-2)$ $\displaystyle=$ $\displaystyle
mh.$

We also emphasize that in (4.1) the equality holds only if $(m,h)=(2,3)$ which
implies $(n,k)=(3,2)$ or $(n,k)=(6,1)$ since $mh=nk$ and $n\geq h=3$. This
implies that $\frac{m}{mh-(h-1)}\leq 1/2$, namely $\mathbb{E}(X)\leq 1/2$.
Similarly, also the expected value $\mathbb{E}(Y)$ of the random variable $Y$
given by the number of columns that sum to zero cannot exceed $1/2$. By the
previous remark on the equality in (4.1), it immediately follows that if one
of $\mathbb{E}(X)$ or $\mathbb{E}(Y)$ is equal to $1/2$, then the other one is
zero, which implies that $\mathbb{E}(X)+\mathbb{E}(Y)<1$. Therefore we can
fill $A$ with the elements of $S$ so that the sum over each row and column is
non-zero. ∎

From Remark 2.2, Proposition 2.9 and Theorem 4.2 we have the existence of a
pair of orthogonal path decompositions whenever Conjecture 2.1 is satisfied.
In particular, from the results of [3] and [26], it follows that:

######  Proposition 4.3.

Let $m\geq k\geq 1$, $n\geq h\geq 1$ and $t$ be such that $nk=mh$ and $t|2nk$.
Then, assuming that either $k,h\leq 9$ or $k,h\leq 10$ and $2nk+t$ is a prime,
there exist a cyclic $h$-path decomposition $\mathcal{D}_{\omega_{r}}$ of
$K_{\frac{2mh+t}{t}\times t}$ and a cyclic $k$-path decomposition
$\mathcal{D}_{\omega_{c}}$ of $K_{\frac{2nk+t}{t}\times t}$. Also,
$\mathcal{D}_{\omega_{r}}$ and $\mathcal{D}_{\omega_{c}}$ are a pair of
orthogonal decompositions.

##  5\. A constructive complete solution for globally simple
$\mathrm{N}\mathrm{H}(n;k)$ and $\mathrm{N}\mathrm{H}(m,n;n,m)$

In this section we construct a globally simple square non-zero sum Heffter
array $\mathrm{N}\mathrm{H}(n;k)$ for every $n\geq k\geq 1$ and a globally
simple non-zero sum Heffter array $\mathrm{N}\mathrm{H}(m,n;n,m)$ for every
$m,n\geq 1$.

Given an $n\times n$ p.f. array $A$, for any $1\leq i\leq n$, the $i$-th
diagonal of $A$ is defined as follows:

$D_{i}=\\{(i,1),(i+1,2),\ldots,(i-1,n)\\}.$

All the arithmetic on the row and column indices is performed modulo $n$,
where the set of reduced residues is $\\{1,2,\ldots,n\\}$. The $k+1$ diagonals
$D_{i},D_{i+1},\ldots,D_{i+k}$ are said to be _consecutive diagonals_.

######  Definition 5.1.

A square p.f. array $A$ of size $n\geq k\geq 1$ is said to be _cyclically
$k$-diagonal_ if the nonempty cells of $A$ are exactly those of $k$
consecutive diagonals.

######  Theorem 5.2.

For any $n\geq k\geq 1$ there exists a cyclically $k$-diagonal globally simple
$\mathrm{N}\mathrm{H}(n;k)$.

###### Proof.

Let $n\geq k\geq 1$ and let $A=(a_{i,j})$ be the $n\times n$ array defined as
follows. If $j\geq i$, set $j=i+r$, hence $a_{i,j}=a_{i,i+r}$. If $j<i$
instead of $a_{i,j}$ we can consider $a_{i,j+n}$ since, as usual, the
subscripts are considered modulo $n$. Then $j+n=i+r$ for some $r$ and hence,
also in this case, $a_{i,j}$ can be written in the form $a_{i,i+r}$. Now, for
any $0\leq r\leq k-1$ we set $a_{i,i+r}=\varepsilon[r+1+(i-1)k]$ where
$\varepsilon$ is equal to $1$ if $r$ is even, while $\varepsilon$ is equal to
$-1$ for $r$ odd. All the other cells of $A$ are left empty. One can check
that the filled cells of $A$ are exactly those of the diagonals
$D_{1},D_{2},\ldots,D_{k}$, so $A$ is a cyclically $k$-diagonal array. Now we
want to prove that $A$ is a globally simple $\mathrm{N}\mathrm{H}(n;k)$. It is
easy to see that conditions ($\rm{a_{2}})$ and ($\rm{b_{2}})$ of Definition
1.4 are satisfied.

We list the partial sums for each row starting from the element $a_{i,i}$, for
$1\leq i\leq n$. If $k$ is even we have

$\displaystyle\mathcal{S}(R_{i})$ $\displaystyle=$
$\displaystyle\Big{(}(i-1)k+1,-1,(i-1)k+2,-2,\ldots,(i-1)k+\frac{k}{2},-\frac{k}{2}\Big{)},$

while for $k$ odd it results

$\displaystyle\mathcal{S}(R_{i})$ $\displaystyle=$
$\displaystyle\Big{(}(i-1)k+1,-1,(i-1)k+2,-2,\ldots,\frac{k-1}{2},(i-1)k+\frac{k+1}{2}\Big{)}.$

So it is immediate that the sum of the elements of each row is different from
zero.

Now we list the partial sums for each column. We start from the first $k-1$
columns, and we have four cases according to the parity of $i$ and $k$. In
each of these cases we list the sums starting from the element
$a_{n-k+1+i,i}$.

Case 1. $k$ even, $i$ odd with $1\leq i\leq k-1$.

$\displaystyle\mathcal{S}(C_{i})$ $\displaystyle=$
$\displaystyle\Big{(}-k(n-k+1+i),k-1,-(k-1)-k(n-k+1+i),2(k-1),$
$\displaystyle-2(k-1)-k(n-k+1+i),3(k-1),\ldots,$
$\displaystyle\frac{k-i-1}{2}(k-1),-\frac{k-i-1}{2}(k-1)-k(n-k+1+i),$
$\displaystyle-\frac{k-i-1}{2}(k-1)-k(n-k+1+i)+i,-\frac{k-i+1}{2}(k-1)-k(n-k+1+i),$
$\displaystyle-\frac{k-i+1}{2}(k-1)-k(n-k+1+i)+i,\ldots,-\frac{k-2}{2}(k-1)-k(n-k+1+i),$
$\displaystyle-\frac{k-2}{2}(k-1)-k(n-k+1+i)+i\Big{)}.$

Case 2. $k$ even, $i$ even with $1\leq i\leq k-1$.

$\displaystyle\mathcal{S}(C_{i})$ $\displaystyle=$
$\displaystyle\Big{(}-k(n-k+1+i),k-1,-(k-1)-k(n-k+1+i),2(k-1),$
$\displaystyle-2(k-1)-k(n-k+1+i),3(k-1),\ldots,-\frac{k-i-2}{2}(k-1)-k(n-k+1+i),$
$\displaystyle\frac{k-i}{2}(k-1),\frac{k-i}{2}(k-1)-i,\frac{k-i+2}{2}(k-1),\frac{k-i-2}{2}(k-1)-i,$
$\displaystyle\frac{k-i+4}{2}(k-1),\ldots,\frac{k-2i+2}{2}(k-1)-i,\frac{k}{2}(k-1)\Big{)}.$

Case 3. $k$ odd, $i$ odd with $1\leq i\leq k-1$.

$\displaystyle\mathcal{S}(C_{i})$ $\displaystyle=$
$\displaystyle\Big{(}k(n-k+1+i),-(k-1),(k-1)+k(n-k+1+i),-2(k-1),$
$\displaystyle
2(k-1)+k(n-k+1+i),-3(k-1),\ldots,-\frac{k-i}{2}(k-1),-\frac{k-i}{2}(k-1)+i,$
$\displaystyle-\frac{k-i+2}{2}(k-1),-\frac{k-i-2}{2}(k-1)+i,-\frac{k-i+4}{2}(k-1),-\frac{k-i-4}{2}(k-1)+i,$
$\displaystyle-\frac{k-i+6}{2}(k-1),\ldots,-\frac{k-2i+1}{2}(k-1)+i\Big{)}.$

Case 4. $k$ odd, $i$ even with $1\leq i\leq k-1$.

$\displaystyle\mathcal{S}(C_{i})$ $\displaystyle=$
$\displaystyle\Big{(}k(n-k+1+i),-(k-1),(k-1)+k(n-k+1+i),-2(k-1),$
$\displaystyle 2(k-1)+k(n-k+1+i),-3(k-1),\ldots,-\frac{k-i-1}{2}(k-1),$
$\displaystyle\frac{k-i-1}{2}(k-1)+k(n-k+1+i),\frac{k-i-1}{2}(k-1)+k(n-k+1+i)-i,$
$\displaystyle\frac{k-i+1}{2}(k-1)+k(n-k+1+i),\frac{k-i-3}{2}(k-1)+k(n-k+1+i)-i,$
$\displaystyle\frac{k-i+3}{2}(k-1)+k(n-k+1+i),\ldots,\frac{k-2i+1}{2}(k-1)+k(n-k+1+i)-i,$
$\displaystyle\frac{k-1}{2}(k-1)+k(n-k+1+i)\Big{)}.$

Now we list the sums of the columns $C_{j}$ for $k\leq j\leq n$. Write $j$ as
$k-1+i$ for $1\leq i\leq n-k+1$. We have two cases according to the parity of
$k$.

If $k$ is even we have

$\displaystyle\mathcal{S}(C_{k-1+i})$ $\displaystyle=$
$\displaystyle\Big{(}-ik,k-1,-(k-1)-ik,2(k-1),-2(k-1)-ik,3(k-1),\ldots,$
$\displaystyle-\frac{k-2}{2}(k-1)-ik,\frac{k}{2}(k-1)\Big{)},$

while for $k$ odd it results

$\displaystyle\mathcal{S}(C_{k-1+i})$ $\displaystyle=$
$\displaystyle\Big{(}ik,-(k-1),(k-1)+ik,-2(k-1),2(k-1)+ik,-3(k-1),\ldots,$
$\displaystyle-\frac{k-1}{2}(k-1),\frac{k-1}{2}(k-1)+ik\Big{)}.$

Note that also the sum of the elements of each column is different from zero.
Hence $A$ is a $\mathrm{N}\mathrm{H}(n;k)$. It can be easily verified that the
partial sums for each row and each of the last $n-k+1$ columns are pairwise
distinct modulo $2nk+1$. Instead proving that the partial sums for each of the
first $k-1$ columns are pairwise distinct is slightly tedious. For this
reason, the partial sums distinctness was verified with Mathematica. So, we
defer the reader to the following link for the source code.

http://stefano-dellafiore.me/additional_material_NH.zip.

∎

To help the reader to follow the proof of the previous theorem we present two
examples with different parity of $k$.

######  Example 5.3.

Applying the proof of Theorem 5.2 we get the $\mathrm{N}\mathrm{H}(11;8)$ and
the $\mathrm{N}\mathrm{H}(11;9)$ below.

$\begin{array}[]{|r|r|r|r|r|r|r|r|r|r|r|}\hline\cr 1&-2&3&-4&5&-6&7&-8&&&\\\
\hline\cr&9&-10&11&-12&13&-14&15&-16&&\\\
\hline\cr&&17&-18&19&-20&21&-22&23&-24&\\\
\hline\cr&&&25&-26&27&-28&29&-30&31&-32\\\
\hline\cr-40&&&&33&-34&35&-36&37&-38&39\\\ \hline\cr
47&-48&&&&41&-42&43&-44&45&-46\\\ \hline\cr-54&55&-56&&&&49&-50&51&-52&53\\\
\hline\cr 61&-62&63&-64&&&&57&-58&59&-60\\\
\hline\cr-68&69&-70&71&-72&&&&65&-66&67\\\ \hline\cr
75&-76&77&-78&79&-80&&&&73&-74\\\ \hline\cr-82&83&-84&85&-86&87&-88&&&&81\\\
\hline\cr\end{array}$

$\begin{array}[]{|r|r|r|r|r|r|r|r|r|r|r|}\hline\cr 1&-2&3&-4&5&-6&7&-8&9&&\\\
\hline\cr&10&-11&12&-13&14&-15&16&-17&18&\\\
\hline\cr&&19&-20&21&-22&23&-24&25&-26&27\\\ \hline\cr
36&&&28&-29&30&-31&32&-33&34&-35\\\
\hline\cr-44&45&&&37&-38&39&-40&41&-42&43\\\ \hline\cr
52&-53&54&&&46&-47&48&-49&50&-51\\\
\hline\cr-60&61&-62&63&&&55&-56&57&-58&59\\\ \hline\cr
68&-69&70&-71&72&&&64&-65&66&-67\\\
\hline\cr-76&77&-78&79&-80&81&&&73&-74&75\\\ \hline\cr
84&-85&86&-87&88&-89&90&&&82&-83\\\
\hline\cr-92&93&-94&95&-96&97&-98&99&&&91\\\ \hline\cr\end{array}$

######  Proposition 5.4.

For any $n\geq k\geq 1$, there exist a pair of orthogonal cyclic
$P_{k}$-decompositions of $K_{2nk+1}$.

###### Proof.

The result follows by Proposition 2.9 and Theorem 5.2. ∎

######  Theorem 5.5.

For any $m,n\geq 1$ there exists a globally simple
$\mathrm{N}\mathrm{H}(m,n;n,m)$.

###### Proof.

Let $m,n\geq 1$ and let $A=(a_{i,j})$ be the $m\times n$ array defined as
follows. For any $1\leq i\leq m$ and $1\leq j\leq n$ set
$a_{i,j}=\varepsilon[j+(i-1)n]$ where $\varepsilon$ is equal to $1$ if $i+j$
is even, while it holds $-1$ for $i+j$ odd. We want to prove that $A$ is a
globally simple $\mathrm{N}\mathrm{H}(m,n;n,m)$. It is easy to see that
conditions ($\rm{a_{2}})$ and ($\rm{b_{2}})$ of Definition 1.4 are satisfied.
Also, one can check that the partial sums of the rows, written starting from
the element $a_{i,1}$, are exactly the same as the array constructed in the
proof of Theorem 5.2. So we already know, that the sum of the elements of each
row is not zero and that the partial sums are pairwise distinct.

Now we list the partial sums of the columns starting from $a_{1,j}$, for
$1\leq j\leq n$. If $m$ is even we have

$\displaystyle\mathcal{S}(C_{j})$ $\displaystyle=$
$\displaystyle\pm\left(j,-n,n+j,-2n,2n+j,-3n,3n+j,\ldots,\frac{m-2}{2}n+j,-\frac{m}{2}n\right),$

while for $m$ odd it results

$\displaystyle\mathcal{S}(C_{j})$ $\displaystyle=$
$\displaystyle\pm\left(j,-n,n+j,-2n,2n+j,-3n,3n+j,\ldots,-\frac{m-1}{2}n+j,\frac{m-1}{2}n+j\right),$

where the sign is $+$ if $j$ is odd, $-$ if $j$ is even. Note that also the
sum of the elements of each column is different from zero. Hence $A$ is a
$\mathrm{N}\mathrm{H}(m,n;n,m)$. Finally, by a direct check, it is not hard to
see that the partial sums of each column are pairwise distinct in
$\mathbb{Z}_{2mn+1}$, hence $A$ is a globally simple
$\mathrm{N}\mathrm{H}(m,n;n,m)$. ∎

######  Example 5.6.

Applying the proof of Theorem 5.5 we get the $\mathrm{N}\mathrm{H}(8,5;5,8)$
and the $\mathrm{N}\mathrm{H}(9,4;4,9)$ below.

$\begin{array}[]{|r|r|r|r|r|}\hline\cr 1&-2&3&-4&5\\\
\hline\cr-6&7&-8&9&-10\\\ \hline\cr 11&-12&13&-14&15\\\
\hline\cr-16&17&-18&19&-20\\\ \hline\cr 21&-22&23&-24&25\\\
\hline\cr-26&27&-28&29&-30\\\ \hline\cr 31&-32&33&-34&35\\\
\hline\cr-36&37&-38&39&-40\\\ \hline\cr\end{array}\hskip
56.9055pt\begin{array}[]{|r|r|r|r|}\hline\cr 1&-2&3&-4\\\
\hline\cr-5&6&-7&8\\\ \hline\cr 9&-10&11&-12\\\ \hline\cr-13&14&-15&16\\\
\hline\cr 17&-18&19&-20\\\ \hline\cr-21&22&-23&24\\\ \hline\cr
25&-26&27&-28\\\ \hline\cr-29&30&-31&32\\\ \hline\cr 33&-34&35&-36\\\
\hline\cr\end{array}$

######  Proposition 5.7.

For any $m,n\geq 1$, there exist a cyclic $P_{m}$-decomposition
$\mathcal{D}_{\omega_{r}}$ of $K_{2mn+1}$ and a cyclic $P_{n}$-decomposition
$\mathcal{D}_{\omega_{c}}$ of $K_{2mn+1}$. Also, $\mathcal{D}_{\omega_{r}}$
and $\mathcal{D}_{\omega_{c}}$ are a pair of orthogonal decompositions.

###### Proof.

The result follows by Proposition 2.9 and Theorem 5.5. ∎

##  6\. Relation with embeddings

As already remarked in the Introduction, Archdeacon [3] introduced Heffter
arrays also because of their applications and, in particular, since they are
useful for finding biembeddings of cycle decompositions. In this section,
generalizing some of Archdeacon’s results we show how starting from a non-zero
sum Heffter array it is possible to obtain suitable biembeddings.

We recall the following definition, see [27].

######  Definition 6.1.

An _embedding_ of a graph $\Gamma$ in a surface $\Sigma$ is a continuous
injective mapping $\psi:\Gamma\to\Sigma$, where $\Gamma$ is viewed with the
usual topology as $1$-dimensional simplicial complex.

The connected components of $\Sigma\setminus\psi(\Gamma)$ are called
$\psi$-_faces_. If each $\psi$-face is homeomorphic to an open disc, then the
embedding $\psi$ is said to be _cellular_.

######  Definition 6.2.

A _biembedding_ of two circuit decompositions $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ of a simple graph $\Gamma$ is a face $2$-colorable
embedding of $\Gamma$ in which one color class is comprised of the circuits in
$\mathcal{D}$ and the other class contains the circuits in
$\mathcal{D}^{\prime}$.

Following the notation given in [3], for every edge $e$ of a graph $\Gamma$,
let $e^{+}$ and $e^{-}$ denote its two possible directions and let $\tau$ be
the involution swapping $e^{+}$ and $e^{-}$ for every $e$. Let $D(\Gamma)$ be
the set of all directed edges that correspond to edges of $\Gamma$ and, for
any $v\in V(\Gamma)$, call $D_{v}$ the set of edges directed out of $v$. A
_local rotation_ $\rho_{v}$ is a cyclic permutation of $D_{v}$. If we select a
local rotation for each vertex of $\Gamma$, then all together they form a
rotation of $D(\Gamma)$. We recall the following result, see [3, 25, 28].

######  Theorem 6.3.

A rotation $\rho$ on $\Gamma$ is equivalent to a cellular embedding of
$\Gamma$ in an orientable surface. The face boundaries of the embedding
corresponding to $\rho$ are the orbits of $\rho\circ\tau$.

Now our goal is to provide a construction of a biembedding starting from a
non-zero sum Heffter array. In order to characterize the faces of this
embedding, we introduce some notations.

Given a cyclic path decomposition $\mathcal{D}$ of $K_{v}$ we want to define
an associated circuit decomposition $\mathcal{C}(\mathcal{D})$. As usual, we
identify the vertex-set of $K_{v}$ with $\mathbb{Z}_{v}$. Let us consider
$P=(x_{0},x_{1},\dots,x_{k})\in\mathcal{D}$, and let $\lambda_{P}$ be the
minimum positive integer such that $\lambda_{P}(x_{k}-x_{0})=0$ in
$\mathbb{Z}_{v}$. Then we set

$C_{P}:=\bigcup_{i=0}^{\lambda_{P}-1}P+i(x_{k}-x_{0}).$

Note that, because of the definition, $C_{P}$ is a circuit and we say that the
path $P$ generates $C_{P}$. Now we consider the set of all circuits of type
$C_{P}$ without repeating them. More formally, we define

$\mathcal{C}(\mathcal{D}):=\\{C_{P}:\ P\in\mathcal{D}\\}.$

Since $\mathcal{C}(\mathcal{D})$ is a set, chosen from a set $\mathcal{T}$ of
generating paths for those circuits, we have that

$\mathcal{C}(\mathcal{D})=\\{C_{P}:\ P\in\mathcal{T}\\}.$

Moreover, since $\bigcup_{P\in\mathcal{D}}P=\bigcup_{P\in\mathcal{T}}C_{P}$,
we have that $\mathcal{C}(\mathcal{D})$ is a decomposition of $K_{v}$ into
circuits.

Then, adapting the proof of Theorem 3.4 of [20], we show that the Archdeacon
embedding (see [3]) is well-defined also in this case. For this purpose we
recall the following definition. Given a non-zero sum Heffter array
$A=\mathrm{N}\mathrm{H}(m,n;h,k)$, the orderings $\omega_{r}$ and $\omega_{c}$
are said to be _compatible_ if $\omega_{c}\circ\omega_{r}$ is a cycle of
length $|\mathcal{E}(A)|$.

######  Theorem 6.4.

Let $A$ be a non-zero sum Heffter array $\mathrm{N}\mathrm{H}(m,n;h,k)$ that
is simple with respect to the compatible orderings $\omega_{r}$ and
$\omega_{c}$. Then there exists a cellular biembedding of the circuit
decompositions $\mathcal{C}(\mathcal{D}_{\omega_{r}^{-1}})$ and
$\mathcal{C}(\mathcal{D}_{\omega_{c}})$ of $K_{2nk+1}$ into an orientable
surface.

###### Proof.

Since the orderings $\omega_{r}$ and $\omega_{c}$ are compatible, we have that
$\omega_{c}\circ\omega_{r}$ is a cycle of length $|\mathcal{E}(A)|$. Let us
consider the permutation $\bar{\rho}_{0}$ on
$\pm\mathcal{E}(A)=\mathbb{Z}_{2nk+1}\setminus\\{0\\}$ defined by:

$\bar{\rho}_{0}(a)=\begin{cases}-\omega_{r}(a)\mbox{ if
}a\in\mathcal{E}(A);\\\ \omega_{c}(-a)\mbox{ if }a\in-\mathcal{E}(A).\\\
\end{cases}$

Note that, if $a\in\mathcal{E}(A)$, then
$\bar{\rho}_{0}^{2}(a)=\omega_{c}\circ\omega_{r}(a)$ and hence
$\bar{\rho}_{0}^{2}$ acts cyclically on $\mathcal{E}(A)$. Also
$\bar{\rho}_{0}$ exchanges $\mathcal{E}(A)$ with $-\mathcal{E}(A)$. Thus it
acts cyclically on $\pm\mathcal{E}(A)$.

Identified the vertex-set of $K_{2nk+1}$ with $\mathbb{Z}_{2nk+1}$, we define
the map $\rho$ on the set of its oriented edges so that:

$\rho((x,x+a))=(x,x+\bar{\rho}_{0}(a)).$

Since $\bar{\rho}_{0}$ acts cyclically on
$\pm\mathcal{E}(A)=\mathbb{Z}_{2nk+1}\setminus\\{0\\}$, the map $\rho$ is a
rotation of $K_{2nk+1}$. Hence, by Theorem 6.3, there exists a cellular
embedding $\sigma$ of $K_{2nk+1}$ in an orientable surface (i.e. the
Archdeacon embedding) so that the face boundaries correspond to the orbits of
$\rho\circ\tau$ where $\tau((x,x+a))=(x+a,x)$.

Let us consider the oriented edge $(x,x+a)$ with $a\in\mathcal{E}(A)$, and let
${C}$ be the column containing $a$. Moreover, let us denote by $\lambda_{c}$
the minimum positive integer such that
$\sum_{i=0}^{\lambda_{c}|\mathcal{E}({C})|-1}\omega_{c}^{i}(a)=0$ in
$\mathbb{Z}_{2nk+1}$. Since $a\in\mathcal{E}(A)$, $-a\in-\mathcal{E}(A)$ and
we have that:

$\rho\circ\tau((x,x+a))=\rho((x+a,(x+a)-a))=(x+a,x+a+\omega_{c}(a)).$

Thus $(x,x+a)$ belongs to the boundary of the face $F_{1}$ delimited by the
oriented edges:

$(x,x+a),(x+a,x+a+\omega_{c}(a)),(x+a+\omega_{c}(a),x+a+\omega_{c}(a)+\omega_{c}^{2}(a)),\dots$
$\dots,\left(x+\sum_{i=0}^{\lambda_{c}|\mathcal{E}({C})|-2}\omega_{c}^{i}(a),x\right).$

We note that the circuit associated to the face $F_{1}$ is:

$\left(x,x+a,x+a+\omega_{c}(a),\ldots,x+\sum_{i=0}^{\lambda_{c}|\mathcal{E}({C})|-2}\omega_{c}^{i}(a)\right).$

Let us now consider the oriented edge $(x,x+a)$ with $a\not\in\mathcal{E}(A)$.
Hence $-a\in\mathcal{E}(A)$, and we name by ${R}$ the row containing the
element $-a$. Moreover, let us denote by $\lambda_{r}$ the minimum positive
integer such that
$\sum_{i=0}^{\lambda_{r}|\mathcal{E}({R})|-1}\omega_{c}^{i}(-a)=0$ in
$\mathbb{Z}_{2nk+1}$. Since $-a\in\mathcal{E}(A)$ we have that:

$\rho\circ\tau((x,x+a))=\rho((x+a,(x+a)-a))=(x+a,x+a-\omega_{r}(-a)).$

Thus $(x,x+a)$ belongs to the boundary of the face $F_{2}$ delimited by the
oriented edges:

$(x,x+a),(x-(-a),x-(-a)-\omega_{r}(-a)),$
$(x-(-a)-\omega_{r}(-a),x-(-a)-\omega_{r}(-a)-\omega_{r}^{2}(-a)),\dots,\left(x-\sum_{i=0}^{\lambda_{r}|\mathcal{E}({R})|-2}\omega_{r}^{i}(-a),x\right).$

Since $A$ is a non-zero sum Heffter array and $\omega_{r}$ acts cyclically on
$\mathcal{E}({R})$, for any $j\in[1,\lambda_{r}|\mathcal{E}({R})|]$ we have
that:

$-\sum_{i=0}^{j-1}\omega_{r}^{i}(-a)=\sum_{i=j}^{\lambda_{r}|\mathcal{E}({R})|-1}\omega_{r}^{i}(-a)=\sum_{i=1}^{\lambda_{r}|\mathcal{E}({R})|-j}\omega_{r}^{\lambda_{r}|\mathcal{E}({R})|-i}(-a)=\sum_{i=1}^{\lambda_{r}|\mathcal{E}({R})|-j}\omega_{r}^{-i}(-a).$

It follows that the circuit associated to the face $F_{2}$ can be written also
as:

$\left(x,x+\sum_{i=1}^{\lambda_{r}|\mathcal{E}({R})|-1}\omega_{r}^{-i}(-a),x+\sum_{i=1}^{\lambda_{r}|\mathcal{E}({R})|-2}\omega_{r}^{-i}(-a),\dots,x+\omega_{r}^{-1}(-a)\right).$

Therefore any nonoriented edge $\\{x,x+a\\}$ belongs to the boundaries of
exactly two faces: one of type $F_{1}$ and one of type $F_{2}$. Hence the
embedding is 2-colorable.

Moreover, it is easy to see that those face boundaries are the circuits of the
decompositions $\mathcal{C}(\mathcal{D}_{\omega_{r}^{-1}})$ and
$\mathcal{C}(\mathcal{D}_{\omega_{c}})$. ∎

######  Remark 6.5.

Note that the proof of Theorem 6.4 can be adapted to the case of a
${}^{\lambda}\mathrm{N}\mathrm{H}_{t}(m,n;h,k)$ that is simple with respect to
the compatible orderings $\omega_{r}$ and $\omega_{c}$. Here we obtain a
cellular biembedding of the circuit decompositions
$\mathcal{C}(\mathcal{D}_{\omega_{r}^{-1}})$ and
$\mathcal{C}(\mathcal{D}_{\omega_{c}})$ of
${}^{\lambda}K_{\frac{2nk}{\lambda}+t}$ into an orientable surface. However,
since the notations would get much more complicated and since our existence
results of Theorems 5.2 and 5.5 cover the case $t=\lambda=1$ we have written
the proof only in that case.

We note that the existence results on compatible orderings of [16] do not
depend on the sum of the elements in each row and each column of the array.
Hence, from Proposition $4.8$, Theorem $4.12$ and Theorem $4.15$ of [16], it
follows that, given a cyclically $k$-diagonal non-zero sum
$\mathrm{N}\mathrm{H}(n;k)$, there exists a pair of compatible orderings in
the following cases:

  * (1)

if $nk$ is odd and $gcd(n,k-1)=1$;

  * (2)

if $nk$ is odd and $3<k<200$;

  * (3)

if $nk$ is odd and $n\geq(k-2)(k-1)$.

Furthermore, due to Theorem 5.2, for all such values of $n$ and $k$, there
exists a biembedding of $K_{2nk+1}$ into an orientable surface whose face
lengths are multiples of $k$. It follows that:

######  Theorem 6.6.

Let $n\geq k$ be odd integers such that one of the following holds:

  * (1)

$gcd(n,k-1)=1$;

  * (2)

$3<k<200$;

  * (3)

$n\geq(k-2)(k-1)$.

Then there exists a biembedding of $K_{2nk+1}$ into an orientable surface
$\Sigma$ whose face lengths are multiples of $k$.

Moreover, from Theorem $3.3$ of [16], it follows that given a
$\mathrm{N}\mathrm{H}(m,n;n,m)$, there exists a pair of compatible orderings
whenever $m$ and $n$ are not both odd. As a consequence of Theorem 5.5, we
have that:

######  Theorem 6.7.

Let $m$ and $n$ be integers and assume that $m$ and $n$ are not both odd. Then
there exists a biembedding of $K_{2mn+1}$ into an orientable surface $\Sigma$
whose face lengths are multiples of $m$ or multiples of $n$.

######  Remark 6.8.

Let us assume that we are under the hypothesis of Theorem 6.6 and that $2nk+1$
is a prime. Then each face is a circuit of length $k(2nk+1)$ and hence we have
$2n$ faces. It follows that the genus of the surface $\Sigma$ is:

$g=\frac{2-(2nk+1)+(2nk+1)nk-2n}{2}.$

Similarly, if we are under the hypothesis of Theorem 6.7 and $2mn+1$ is a
prime, then we have $m+n$ faces. It follows that the genus of the surface
$\Sigma$ is:

$g=\frac{2-(2mn+1)+(2mn+1)mn-(m+n)}{2}.$

## Acknowledgements

The first and the third authors were partially supported by INdAM–GNSAGA.

## References

  * [1] R.J.R. Abel M. Buratti, Difference families, in: Handbook of Combinatorial Designs. Edited by C. J. Colbourn and J. H. Dinitz. Second edition. Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, 2007.
  * [2] B. Alspach G. Liversidge, On strongly sequenceable abelian groups, Art Discrete Appl. Math. 3 (2020), #P1.02.
  * [3] D.S. Archdeacon, Heffter arrays and biembedding graphs on surfaces, Electron. J. Combin. 22 (2015) #P1.74.
  * [4] D.S. Archdeacon, T. Boothby J.H. Dinitz, Tight Heffter arrays exist for all possible values, J. Combin. Des. 25 (2017), 5–35.
  * [5] D.S. Archdeacon, J.H. Dinitz, D.M. Donovan E.S. Yazıcı, Square integer Heffter arrays with empty cells, Des. Codes Cryptogr. 77 (2015), 409–426.
  * [6] D.S. Archdeacon, J.H. Dinitz, A. Mattern D.R. Stinson, On partial sums in cyclic groups, J. Combin. Math. Combin. Comput. 98 (2016), 327–342.
  * [7] J.P. Bode H. Harborth, Directed paths of diagonals within polytopes, Discrete Math. 299 (2005), 3–10.
  * [8] D. Bryant S. El-Zanati, Graph decompositions, in: Handbook of Combinatorial Designs. Edited by C. J. Colbourn and J. H. Dinitz. Second edition. Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, 2007.
  * [9] M. Buratti, Recursive constructions for difference matrices and relative difference families, J. Combin. Des. 6 (1998), 165–182.
  * [10] M. Buratti A. Pasotti, Graph decompositions with the use of difference matrices, Bull. Inst. Combin. Appl. 47 (2006), 23–32.
  * [11] A.C. Burgess, N.J. Cavenagh, D.A. Pike, _Mutually orthogonal cycle systems_ , preprint.
  * [12] K. Burrage, N.J. Cavenagh, D. Donovan E.Ş. Yazıcı, Globally simple Heffter arrays $H(n;k)$ when $k\equiv 0,3\pmod{4}$, Discrete Math. 343 (2020), 111787.
  * [13] Y. Caro R. Yuster, Orthogonal decomposition and packing of complete graphs, J. Combin. Theory Ser. A 88 (1999), 93–111.
  * [14] N.J. Cavenagh, J. Dinitz, D. Donovan E.S. Yazıcı, The existence of square non-integer Heffter arrays, Ars Math. Contemp. 17 (2019), 369–395.
  * [15] N.J. Cavenagh, D. Donovan E.Ş. Yazıcı, Biembeddings of cycle systems using integer Heffter arrays, J. Combin. Des. 28 (2020), 900–922.
  * [16] S. Costa, M. Dalai A. Pasotti, A tour problem on a toroidal board, Austral. J. Combin. 76 (2020), 183–207.
  * [17] S. Costa, F. Morini, A. Pasotti M.A. Pellegrini, A generalization of Heffter arrays, J. Combin. Des. 28 (2020), 171–206.
  * [18] S. Costa, F. Morini, A. Pasotti M.A. Pellegrini, A problem on partial sums in abelian groups, Discrete Math. 341 (2018), 705–712.
  * [19] S. Costa, F. Morini, A. Pasotti M.A. Pellegrini, Globally simple Heffter arrays and orthogonal cyclic cycle decompositions, Austral. J. Combin. 72 (2018), 549–593.
  * [20] S. Costa, A. Pasotti M.A. Pellegrini, Relative Heffter arrays and biembeddings, Ars Math. Contemp. 18 (2020), 241–271.
  * [21] S. Costa A. Pasotti, On $\lambda$-fold relative Heffter arrays and biembedding multigraphs on surfaces, Europ. J. Combin. 97 (2021), 103370.
  * [22] S. Costa M.A. Pellegrini, Some new results about a conjecture by Brian Alspach, Archiv der Mathematik 115 (2020), 479–488.
  * [23] J.H. Dinitz A.R.W. Mattern, Biembedding Steiner triple systems and $n$-cycle systems on orientable surfaces, Austral. J. Combin. 67 (2017), 327–344.
  * [24] J.H. Dinitz I.M. Wanless, The existence of square integer Heffter arrays, Ars Math. Contemp. 13 (2017), 81–93.
  * [25] J.L. Gross T.W. Tucker, Topological Graph Theory, John Wiley, New York, 1987.
  * [26] J. Hicks, M.A. Ollis J.R. Schmitt, Distinct partial sums in cyclic groups: polynomial method and constructive approaches, J. Combin. Des. 27 (2019), 369–385.
  * [27] B. Mohar, Combinatorial local planarity and the width of graph embeddings, Canad. J. Math. 44 (1992), 1272–1288.
  * [28] B. Mohar C. Thomassen, Graphs on surfaces, Johns Hopkins University Press, Baltimore, 2001.
  * [29] F. Morini M.A. Pellegrini, On the existence of integer relative Heffter arrays, Discrete Math. 343 (2020), 112088.
  * [30] F. Morini M.A. Pellegrini, _Magic rectangles, signed magic arrays and integer $\lambda$-fold relative Heffter arrays_, Austral. J. Combin. 80 (2021), 249–280.
  * [31] F. Morini M.A. Pellegrini, _Rectangular Heffter arrays: a reduction theorem_ , preprint available at https://arxiv.org/abs/2107.08857v2.
  * [32] M.A. Ollis, Sequences in dihedral groups with distinct partial products, Austral. J. Combin. 78 (2020), 35–60.


# Fine-structure transitions of the carbon isoelectronic sequence C, N+ and
O2+ induced by collisions with atomic hydrogen

Pei-Gen Yan,1 James F. Babb,1
1Center for Astrophysics | Harvard & Smithsonian, MS 14, 60 Garden St., Cambridge, MA 02138 E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Fine-structure transitions can be involved in various processes including
photon absorption, charge transfer and inelastic collision between ions,
electrons and neutral atoms. We present fine-structure excitation and
relaxation cross sections for the collisions of the first few members of the
carbon isoelectronic sequence (C, N+ and O2+) with atomic hydrogen calculated
using quantum-mechanical methods. For C, the scattering theory and
computational approach is verified by comparison with previous calculations.
The rate coefficients for the collisional processes are obtained. For N+ and
O2+, the transitions correspond to the lines [O iii] 52 µm, [O iii] 88 µm, [N
ii] 122 µm, and [N ii] 205 µm, observed in the far-infrared in the local
Universe and more recently in high-redshift galaxies using radio
interferometry. The influence of different potentials on the cross sections
and rate coefficients are demonstrated.

###### keywords:

ISM – molecular processes – scattering processes

††pubyear: 2022††pagerange: Fine-structure transitions of the carbon
isoelectronic sequence C, N+ and O2+ induced by collisions with atomic
hydrogen–References

##  1 Introduction

In many astrophysical environments, fine-structure levels of atoms and ions
are populated by collisions with electrons, hydrogen atoms, and hydrogen
molecules, as well as by photons. Excitation of an atom by such collisions
might be followed by spontaneous emission leading to a loss of kinetic energy
or “cooling.” The competition between relaxation of the fine-structure levels
by collisions and spontaneous emission affects the diagnostic potential of the
observed lines. Cross sections and rate coefficients for collisional
relaxation can be calculated and used in sophisticated modeling codes to
interpret astronomical observations.

In the far-infrared, the lines [O i] 63 µm, [O i] 146 µm, and [C ii] 158 µm
are commonly observed and utilized as probes of physical conditions;
accordingly the collisions of O and C+ with electrons, hydrogen atoms, and
hydrogen molecules are well-studied. Recently, the rest-frame far-infrared
lines [O iii] 52 µm, [O iii] 88 µm, [N ii] 122 µm, and [N ii] 205 µm, became
of interest111For completeness, we note that [N iii] 57 µm is of interest, but
we do not treat it in this paper. in observations of high-redshift galaxies
($z>6$) using ALMA, see, for example, Inoue et al. (2014), Sugahara et al.
(2021), and Ramos Padilla et al. (2022). While the O2+ and N+ lines above
generally trace Hii regions and thus are expected to be most affected by
electron collisions—for which collision strengths are available, see Tayal
(2011); Tayal & Zatsarinny (2017)—complete interpretations of these nascent
high-$z$ observations are still in their infancy and as far as we know, no
data on the collisional cross sections and rate coefficients for fine-
structure excitation or de-excitation of N+ or O2+ in collisions with H are
available should they be needed for modeling or simulation. In the present
paper, we treat the collisions

$\textrm{A}(^{3}P_{j})+\textrm{H}(^{2}S_{1/2})\rightarrow\textrm{A}(^{3}P_{j^{\prime}})+\textrm{H}(^{2}S_{1/2})\,,$
(1)

where A can be C, N+ and O2+ and $(j,j^{\prime})$ can be $(1,2)$, $(0,1)$, or
$(0,2)$. For ground state carbon atoms, quantum-mechanical calculations of
cross sections for process (1) were previously reported by Launay & Roueff
(1977) and Abrahamsson et al. (2007). Although the atomic structure of the
ions is in some ways similar to neutral carbon we find that in collisions with
hydrogen atoms the resulting cross sections and rate coefficients have
quantitative differences.

##  2 Theoretical Models

We use a close-coupling scattering formulation (Mies, 1973; Launay & Roueff,
1977) with the wave function $\Phi^{JM}$ expanded in the space-fixed basis
$|j_{a}j_{b}j_{ab}lJM\rangle$ as

$\Phi^{JM}=\sum_{j_{ab},l}F_{j_{ab}l}^{JM}(R)|j_{a}j_{b}j_{ab}lJM\rangle\,,$
(2)

where the two colliding systems are labeled $a$ and $b$, $F_{j_{ab}l}^{JM}(R)$
is the reduced radial wave function, $R$ is the internuclear distance,
$j_{ab}=j_{a}+j_{b}$ is the total electric angular momentum, and $J=j_{ab}+l$
is the total angular momentum. With the total wave function (Eq. 2), the
Schrödinger equation that describes the internal motions of the C, N+ or O2+
ion and H system can be reduced to a set of coupled differential equations,
expressed in atomic units (a.u.) as

$\bigg{[}\frac{d}{dR^{2}}-\frac{l(l+1)}{R^{2}}+k_{j_{a}}^{2}\bigg{]}F_{j_{ab}l}^{J}(R)=2\mu\sum_{j^{\prime}_{a}j^{\prime}_{ab}l^{\prime}}U^{J}_{j_{a}j_{ab}l;j^{\prime}_{a}j^{\prime}_{ab}l^{\prime}}F_{j_{ab}l}^{J}(R)\,,$
(3)

with the wave number $k_{j_{a}}$ defined by
$k^{2}_{j_{a}}=2\mu(E-\varepsilon_{j_{a}})$, where $\mu$ is the reduced mass
of systems $a$ and $b$, $E$ is the total collision energy, and
$\varepsilon_{j_{a}}$ is the fine-structure state splitting energy of the C,
N+, or O2+ atom. We adopt the values of $\varepsilon_{j_{a}}$ from NIST
(Kramida et al., 2022): For the C atom

$\varepsilon_{0}=0,\qquad\varepsilon_{1}=16.417\;\mathrm{cm}^{-1},\qquad\varepsilon_{2}=43.413\;\mathrm{cm}^{-1}\,,$
(4)

for the N+ ion,

$\varepsilon_{0}=0,\qquad\varepsilon_{1}=48.7\;\mathrm{cm}^{-1},\qquad\varepsilon_{2}=130.8\;\mathrm{cm}^{-1}\,.$
(5)

and for the O2+ ion,

$\varepsilon_{0}=0,\qquad\varepsilon_{1}=113.178\;\mathrm{cm}^{-1},\qquad\varepsilon_{2}=306.174\;\mathrm{cm}^{-1}\,.$
(6)

$U$ is the coupling matrix given by the summation of the $V_{\mathrm{el}}$ and
$V_{\mathrm{so}}$ matrices in the basis $|j_{a}j_{b}j_{ab}lJM\rangle$. The
$V_{\mathrm{so}}$ matrix is diagonal and the nonzero elements are the fine-
structure splittings that are given above in (4), (5), or (6). For the
elements of the potential energy $V_{\mathrm{el}}$ matrix, we adopt the
expression described in Launay & Roueff (1977); Flower et al. (2000); Krems et
al. (2006). Then the cross sections for fine-structure transitions are
calculated by

$\sigma_{j_{a}\rightarrow j^{\prime}_{a}}(E)=\sum_{J}\sigma_{j_{a}\rightarrow
j^{\prime}_{a}}^{J}(E)\,,$ (7) $\sigma_{j_{a}\rightarrow
j^{\prime}_{a}}^{J}(E)=\frac{\pi}{k_{j_{a}}^{2}}\frac{2J+1}{(2j_{a}+1)(2j_{b}+1)}\sum_{j_{ab}lj^{\prime}_{ab}l^{\prime}}|T^{J}_{j^{\prime}_{a}j^{\prime}_{ab}l^{\prime};j_{a}j_{ab}l}|^{2}\,,$
(8)

where $\sigma_{j_{a}\rightarrow j^{\prime}_{a}}^{J}$ are the partial cross
sections and the $T$ matrix is defined by $T^{J}=-2iK^{J}(I-iK^{J})^{-1}$,
where $K^{J}$ is the open channel reaction matrix defined in Johnson (1973).
The maximum value for the partial waves $J$ is set as 1000 and for the maximum
collision energy used (9.05 eV), the partial cross section converged for CH at
about 300, for NH+ at about 500, and for OH2+ at about 990.

##  3 Interatomic Potentials

For the CH system, the four electronic states involved in the fine-structure
transitions of C(3P) in collisions with H(2S) are the b${}^{4}\Pi$,
B${}^{2}\Sigma^{-}$, a${}^{4}\Sigma^{-}$, and X${}^{2}\Pi$ states. The present
calculations, using the MRCI-DKH (Douglas-Kroll-Hess) method with the aug-cc-
pV5Z-dk basis within Molpro 2010.1 (Werner et al., 2010), are shown in Fig. 1.

Figure 1: Potential energies (in Hartrees) for the CH system as functions of
the internuclear distance $R$ (in $a_{0}$) labeled from the top down at the
equilibrium distance of the lowest state: b${}^{4}\Pi$ (blue dashed line),
B${}^{2}\Sigma^{-}$ (green dotted line), a${}^{4}\Sigma^{-}$ (orange solid
line) and X${}^{2}\Pi$ (red dashdot line).

The calculated potential energies were smoothly joined to the long-range
potential function $-C_{6}/R^{6}$ at $R=9\,a_{0}$, where we used the value
$C_{6}=20.3$ a.u. (Yau & Dalgarno, 1976).

For the NH+ system, the four electronic states involved in the fine-structure
transitions of N+(3P) in collision with H(2S) are the 2${}^{4}\Sigma^{-}$,
1${}^{4}\Pi$, 1${}^{2}\Sigma^{-}$, and X${}^{2}\Pi$ states. The present
calculations, using the MRCI-DKH (Douglas-Kroll-Hess) method with the aug-cc-
pV5Z-dk basis within Molpro 2010.1 (Werner et al., 2010), are shown in Fig. 2,

Figure 2: Potential energies for the NH+ system as functions of the
internuclear distance $R$. The 1${}^{4}\Sigma^{-}$ state correlating to
N(4S)–H+(1S) is labeled with the gray dotted line. The other states correlate
to N+(3P)–H(2S) and are labeled from the top down at the equilibrium distance
of the lowest state: 1${}^{4}\Pi$ (blue dashed line), 2${}^{4}\Sigma^{-}$
(orange solid line), 1${}^{2}\Sigma^{-}$ (green dotted line) and X${}^{2}\Pi$
(red dashdot line).

along with the 1${}^{4}\Sigma^{-}$ state correlating to N(4S) + H+(1S). The
potentials were joined at $R=17\,a_{0}$ to the long-range charge-induced
dipole interaction $-\alpha_{\mathrm{H}}/2R^{4}$ between N+(3P) and H(2S),
where $\alpha_{\mathrm{H}}=4.5$ a.u. is the polarizability of the hydrogen
atom.

For the OH2+ system, the four electronic states that are involved in the fine-
structure transitions of O2+(3P) in collision with H(2S) are the 3${}^{2}\Pi$,
2${}^{2}\Sigma^{-}$, 2${}^{4}\Pi$, and 3${}^{4}\Sigma^{-}$ states. We adopted
the recent MRCI+Q calculations using the aug-cc-pV5Z basis that were presented
by De Melo et al. (2021) and which we show in Fig. 3.

Figure 3: Potential energies for the OH2+ system as functions of the
internuclear distance $R$, labeled from the top down at the equilibrium
distance of the lowest state: 3${}^{2}\Pi$ (red dashdot line),
2${}^{2}\Sigma^{-}$ (green dotted line), 2${}^{4}\Pi$ (blue dashed line), and
3${}^{4}\Sigma^{-}$ (orange solid line) from De Melo et al. (2021).

The long-range charge-induced dipole interaction potential
$-\alpha_{\mathrm{H}}/R^{4}$ between O2+(3P) ion and the H(2S) atom was
smoothly connected to the potentials at $R=20\,a_{0}$.

##  4 Scattering calculations

Using the theoretical quantum description of a collision between two open-
shell atoms in arbitrary angular momentum states derived by Krems et al.
(2006), the scattering calculations were performed using a Python code that we
wrote based partially on the Molcol Fortran 77 code (Flower et al., 2019)
utilizing Johnson’s multichannel logarithmic derivative algorithm (Johnson,
1973). In order to prove the reliability of the present approach, the Python
code was tested by calculating cross sections for the C+-H, the Si+-H, and the
O-H systems (Yan & Babb, 2022b); in all these cases, the corresponding rate
coefficients were found to be in very good agreement with those of preceding
calculations from the literature when we used the potential energy data of the
original sources. In the following, we will also show that our calculations of
the cross sections and rate coefficients for the C-H system are in good accord
with those of others.

Having established the reliability of our theory and code, the cross sections
were computed for collisional energies up to about 8.6 eV. The scattering
equations were integrated from $R=1\,a_{0}$ to $R=30\,a_{0}$. The
corresponding excitation and relaxation rate coefficients were computed for
temperatures up to 10,000 K by averaging over a Maxwellian energy
distribution,

$k_{j_{a}\rightarrow j^{\prime}_{a}}(T)=\bigg{(}\frac{8}{\pi\mu
k_{B}^{3}T^{3}}\bigg{)}^{1/2}\int_{0}^{\infty}\sigma_{j_{a}\rightarrow
j^{\prime}_{a}}(E_{k})e^{-E_{k}/k_{B}T}E_{k}dE_{k}\,,$ (9)

where $T$ is the temperature, $k_{B}$ is Boltzmann’s constant, $\sigma$ is the
cross section, and $E_{k}$ is the kinetic energy.

##  5 Results

With the CH potentials as described above, the calculated excitation and
relaxation cross sections 222Note that the cross sections correspond strictly
to the process (1) and we calculate these to energies $\sim 10^{5}$ K to have
a suitable integrand for the rate coefficient of Eq. (9). In a gas of
temperature $~{}\sim 10,000$ K or higher cross sections corresponding to other
channels such as $\textrm{C}(^{1}D)$ and $\textrm{C}(^{1}S)$ might be opened.
are shown in Fig. 4.

Figure 4: Excitation and relaxation cross sections for fine-structure
transitions of C in collision with H. The three transitions $(j\rightarrow
j^{\prime})$ are labeled with different colors.

The corresponding rate coefficients as functions of temperature are given in
Fig. 5

Figure 5: Excitation and relaxation rate coefficients for fine-structure
transitions of C in collision with H. The three transitions $(j\rightarrow
j^{\prime})$ are labeled with different colors.

and Table 1.

Table 1: Rate coefficients (in units of 10-9 cm3s-1) for the fine-structure excitation and relaxation of C(${}^{3}P_{j}$) by H. $T$(K) | $j=0\rightarrow j^{\prime}=1$ | $j=0\rightarrow j^{\prime}=2$ | $j=1\rightarrow j^{\prime}=2$
---|---|---|---
100 | 0.360 | 0.234 | 0.319
200 | 0.425 | 0.401 | 0.465
500 | 0.540 | 0.656 | 0.693
700 | 0.596 | 0.762 | 0.794
1000 | 0.665 | 0.888 | 0.917
2000 | 0.844 | 1.185 | 1.215
5000 | 1.195 | 1.707 | 1.755
7000 | 1.368 | 1.948 | 2.010
10000 | 1.579 | 2.242 | 2.320
$T$(K) | $j=1\rightarrow j^{\prime}=0$ | $j=2\rightarrow j^{\prime}=0$ | $j=2\rightarrow j^{\prime}=1$
10 | 0.199 | 0.086 | 0.252
20 | 0.182 | 0.080 | 0.251
50 | 0.157 | 0.077 | 0.256
70 | 0.153 | 0.081 | 0.265
100 | 0.152 | 0.088 | 0.283
200 | 0.159 | 0.110 | 0.339
500 | 0.189 | 0.149 | 0.450
700 | 0.205 | 0.167 | 0.504
1000 | 0.227 | 0.189 | 0.572
2000 | 0.284 | 0.245 | 0.743
5000 | 0.400 | 0.346 | 1.061
7000 | 0.458 | 0.393 | 1.213
10000 | 0.527 | 0.451 | 1.397

From Fig. 5, we see that at low temperatures (or relatively small kinetic
energies), the excitation rate coefficient of the $0\rightarrow 1$ transition
is larger than those of the $1\rightarrow 2$ and $0\rightarrow 2$ transitions.
The energy differences of the $0\rightarrow 1$ transition are the smallest
leading to this being the strongest transition. With increasing temperature
(kinetic energy), we find that the rate coefficients for the $0\rightarrow 1$
transition drop to being the smallest, such behavior is explained by the
“forbidden” selection rules demonstrated by Monteiro & Flower (1987). This
“forbidden” selection rule may explain the lower relaxation rate coefficients
of $2\rightarrow 0$ and $1\rightarrow 0$ transitions compared to that of the
$2\rightarrow 1$ transition. In order to further prove the reliability of the
present approach, we also made comparisons of the present calculations with
those of Launay & Roueff (1977) and of Abrahamsson et al. (2007), as shown in
Fig. 6.

Figure 6: Comparison of temperature dependent excitation rate coefficients of
the present calculations (solid lines)with those of Abrahamsson et al. (2007)
(large dots) and with those of Launay & Roueff (1977) (dashed lines).

It can be seen that the present calculations are in good agreement with the
other works, especially for the $0\rightarrow 1$ transitions. The
discrepancies for the rate coefficients of the $1\rightarrow 2$ and
$0\rightarrow 2$ transitions could be caused by the different potentials we
used. Comparing Figs. 4 and 5, it is apparent that the relaxation cross
sections decrease as a function of energy, while the relaxation rate
coefficients increase as a function of temperature, a consequence of the
energy dependence in the integrand of Eq. (9). For example, the log-log plot
of Fig. 4 shows that the relaxation cross sections decrease slowly for energy
$E_{k}>1000\,^{0}\textrm{K}$ and thus the relaxation rate coefficients shown
in Fig. 5 increase for $T>100\,\textrm{K}$.

With the NH+ potentials as described above, the calculated excitation and
relaxation cross sections are shown in Fig. 7.

Figure 7: Excitation and relaxation cross sections for fine-structure
transitions of N+ in collision with H. The three transitions $(j\rightarrow
j^{\prime})$ are labeled with different colors.

The corresponding rate coefficients for the fine structure transitions of N+
in collision with H as a function of temperature are given in Fig. 8

Figure 8: Excitation and relaxation rate coefficients for fine-structure
transitions of $\textrm{N}^{+}$ in collision with H. The three transitions
$(j\rightarrow j^{\prime})$ are labeled with different colors.

and Table 2.

Table 2: Rate coefficients (in units of 10-9 cm3s-1) for the fine-structure excitation and relaxation of N+(${}^{3}P_{j}$) by H. $T$(K) | $j=0\rightarrow j^{\prime}=1$ | $j=0\rightarrow j^{\prime}=2$ | $j=1\rightarrow j^{\prime}=2$
---|---|---|---
100 | 0.466 | 0.153 | 0.298
200 | 0.613 | 0.475 | 0.626
500 | 0.742 | 1.072 | 1.116
700 | 0.793 | 1.306 | 1.305
1000 | 0.856 | 1.558 | 1.514
2000 | 0.998 | 2.093 | 1.973
5000 | 1.228 | 3.002 | 2.764
7000 | 1.353 | 3.408 | 3.126
10000 | 1.524 | 3.878 | 3.556
$T$(K) | $j=1\rightarrow j^{\prime}=0$ | $j=2\rightarrow j^{\prime}=0$ | $j=2\rightarrow j^{\prime}=1$
10 | 0.353 | 0.169 | 0.458
20 | 0.333 | 0.156 | 0.461
50 | 0.330 | 0.171 | 0.513
70 | 0.324 | 0.184 | 0.544
100 | 0.314 | 0.201 | 0.583
200 | 0.290 | 0.244 | 0.678
500 | 0.285 | 0.313 | 0.848
700 | 0.292 | 0.342 | 0.927
1000 | 0.306 | 0.376 | 1.022
2000 | 0.345 | 0.460 | 1.256
5000 | 0.415 | 0.624 | 1.698
7000 | 0.455 | 0.700 | 1.907
10000 | 0.511 | 0.790 | 2.158

Compared to the CH system, the cross sections and rate coefficients of the
$1\rightarrow 2$ and $0\rightarrow 2$ transitions for the NH+ system are
larger because of the stronger long-range attractions and deeper potential
wells as shown in Fig. 2. Furthermore, we find that for NH+ the $1\rightarrow
2$ transition rate coefficient is the largest compared to CH where the
$0\rightarrow 2$ transition is the largest. This phenomenon might be caused by
the different shapes of the potentials for the two systems: The
1${}^{4}\Sigma^{-}$ state of the CH system has a much deeper well than the
2${}^{4}\Sigma^{-}$ state of the NH+ system. Similarly to the CH system, the
excitation rate coefficients of the $0\rightarrow 1$ transition are also the
smallest among the three transitions because of the “forbidden” selection
rule. $\textrm{N}^{+}$ can be removed by the exothermic charge transfer
process (Butler & Dalgarno, 1979)

$\textrm{N}^{+}(^{3}P)+\textrm{H}(^{2}S)\rightarrow\textrm{N}(^{4}S^{\mathrm{o}})+\textrm{H}^{+}+0.9467~{}\textrm{eV}.$
(10)

The rate coefficients were calculated by Lin et al. (2005) and they decrease
from a value of about $10^{-13}\,\textrm{cm}^{3}/\textrm{s}$ at
$10,000\,\textrm{K}$ and appear to be considerably slower than the relaxation
process which is no less than $10^{-10}\,\textrm{cm}^{3}/\textrm{s}$ even at
$10\,\textrm{K}$.

With the OH2+ potentials as described above, the calculated cross sections for
fine structure transition of O2+ in collision with H are shown in Fig. 9.

Figure 9: Excitation and relaxation cross sections for fine-structure
transitions of O2+ in collision with H. The three transitions $(j\rightarrow
j^{\prime})$ are labeled with different colors.

The corresponding rate coefficients are given in Fig. 10

Figure 10: Excitation and relaxation rate coefficients for fine-structure
transitions of O2+ in collision with H. The three transitions $(j\rightarrow
j^{\prime})$ are labeled with different colors.

and Table 3.

Table 3: Rate coefficients (in units of 10-9 cm3s-1) for the fine-structure excitation and relaxation of O2+(${}^{3}P_{j}$) by H. $T$(K) | $j=0\rightarrow j^{\prime}=1$ | $j=0\rightarrow j^{\prime}=2$ | $j=1\rightarrow j^{\prime}=2$
---|---|---|---
100 | 0.510 | 0.348 | 0.147
200 | 0.979 | 0.305 | 0.583
500 | 1.152 | 1.050 | 1.284
700 | 1.149 | 1.296 | 1.474
1000 | 1.162 | 1.493 | 1.626
2000 | 1.296 | 1.690 | 1.814
5000 | 1.643 | 1.776 | 1.982
7000 | 1.800 | 1.809 | 2.051
10000 | 1.987 | 1.856 | 2.138
$T$(K) | $j=1\rightarrow j^{\prime}=0$ | $j=2\rightarrow j^{\prime}=0$ | $j=2\rightarrow j^{\prime}=1$
10 | 0.796 | 0.525 | 1.318
20 | 0.859 | 0.552 | 1.386
50 | 0.902 | 0.570 | 1.427
70 | 0.896 | 0.571 | 1.431
100 | 0.866 | 0.569 | 1.430
200 | 0.737 | 0.552 | 1.408
500 | 0.532 | 0.507 | 1.344
700 | 0.483 | 0.486 | 1.316
1000 | 0.456 | 0.464 | 1.288
2000 | 0.469 | 0.421 | 1.249
5000 | 0.566 | 0.387 | 1.255
7000 | 0.614 | 0.384 | 1.279
10000 | 0.673 | 0.387 | 1.318

From Figs. 9 and 10, we see that at the lowest temperatures both the cross
sections and rate coefficients of the OH2+ system are larger than those of the
CH and NH+ systems. This is caused by the stronger long-range interaction
$-\alpha_{\mathrm{H}}/R^{4}$ of the OH2+ system compared to the other two
systems. The four wells of the OH2+ potentials, see Fig. 3, lead to the mild
increase of the $0\rightarrow 1$ transition for temperatures larger than 4000
K. $\textrm{O}^{2+}$ can be removed by the charge transfer process (Butler et
al., 1979)

$\textrm{O}^{2+}(^{3}P)+\textrm{H}(^{2}S)\rightarrow\textrm{O}^{+}(^{4}P)+\textrm{H}^{+}+6.701~{}\textrm{eV}.$
(11)

The rate coefficient is about $10^{-9}\,\textrm{cm}^{3}/\textrm{s}$ over the
temperature range $200<T<10,000\,\textrm{K}$ (Honvault et al., 1995), which is
comparable to our calculated fine-structure relaxation rate coefficients shown
in Table 3. This might be an important consideration for modeling
applications.

The critical density $n_{c}$, an important parameter to indicate whether
collisions affect the presence of fine structure lines, is defined as

$n_{c}(j;T;x)=\frac{\sum_{j^{\prime}}A(j\rightarrow
j^{\prime})}{\sum_{j^{\prime}}k_{j\rightarrow j^{\prime}}(T;x)}\,,$ (12)

where $A(j\rightarrow j^{\prime})$ is the transition probability (Mendoza,
1983) and $k_{j\rightarrow j^{\prime}}(T;x)$ is the relaxation rate
coefficient for collisions with species $x$, which maybe be hydrogen (H) or
electrons (e). Our calculated critical densities for N+ and O2+, respectively,
and H are shown in Figs. 11

Figure 11: Critical densities for the relaxation of N+ in collision with
hydrogen (solid lines) and electrons (dashed lines). For electrons, data from
Tayal (2011) were used.

and 12.

Figure 12: Critical densities for the relaxation of O2+ in collision with
hydrogen (solid lines) and electrons (dashed lines). For electrons, data from
Tayal & Zatsarinny (2017) were used.

We also plot the critical densities for electrons (e), which were determined
using the effective collision strengths from Tayal (2011) for N+ and from
Tayal & Zatsarinny (2017) for O2+. The graphical data in Figs. 11 and 12 might
be useful for considerations of the relative importance of hydrogen and
electron densities at specific temperatures. For example, we can see that the
critical densities induced by electrons are 10 to 102 times smaller than those
induced by hydrogen atoms due to the strong electron-ion interactions.

##  6 Conclusion

We introduced a methodology that yields consistent sets of rate coefficients
for a number of cases. Based partially on the Molcol Fortran code (Flower et
al., 2019), we developed a new Python code utilizing Johnson’s multichannel
logarithmic derivative algorithm (Johnson, 1973). We presented for the first
time a comparison of the excitation and relaxation cross sections and rate
coefficients for fine-structure transitions in collision of C, N+, or O2+ and
atomic hydrogen. The calculations are based on accurate CH (present work), NH+
(present work), and OH2+ (De Melo et al., 2021) potentials. The present
research may be useful in applications of far-infrared lines to astrophysical
diagnostics.

## Data Availability

The data points corresponding to the rate coefficients plotted in Figs. 8 and
10 are given in LAMDA format (Schöier et al., 2005) at Figshare (Yan & Babb,
2022a).

## Acknowledgements

This work was supported by NASA APRA grant 80NSSC19K0698.

## References

  * Abrahamsson et al. (2007) Abrahamsson E., Krems R. V., Dalgarno A., 2007, ApJ, 654, 1171
  * Butler & Dalgarno (1979) Butler S. E., Dalgarno A., 1979, ApJ, 234, 765
  * Butler et al. (1979) Butler S. E., Bender C. F., Dalgarno A., 1979, ApJ, 230, L59
  * De Melo et al. (2021) De Melo G. F., Franzreb K., Ornellas F. R., 2021, PCCP, 23, 13672
  * Flower et al. (2000) Flower D., Bourhis G., Launay J.-M., 2000, Comput. Phys. Commun., 131, 187
  * Flower et al. (2019) Flower D., Bourhis G., Launay J.-M., 2019, Molcol: A program for solving atomic and molecular collision problems, doi:10.17632/NRHFXT7G69.1, https://data.mendeley.com/datasets/nrhfxt7g69/1
  * Honvault et al. (1995) Honvault P., Gargaud M., Bacchus-Montabonel M. C., McCarroll R., 1995, A&A, 302, 931
  * Inoue et al. (2014) Inoue A. K., Shimizu I., Tamura Y., Matsuo H., Okamoto T., Yoshida N., 2014, ApJ, 780, L18
  * Johnson (1973) Johnson B., 1973, J. Comp. Phys., 13, 445
  * Kramida et al. (2022) Kramida A., Yu. Ralchenko Reader J., and NIST ASD Team 2022, NIST Atomic Spectra Database (ver. 5.10), [Online]. Available: https://physics.nist.gov/asd [2022, October 25]. National Institute of Standards and Technology, Gaithersburg, MD.
  * Krems et al. (2006) Krems R. V., Jamieson M. J., Dalgarno A., 2006, ApJ, 647, 1531
  * Launay & Roueff (1977) Launay J. M., Roueff E., 1977, A&A, 56, 289
  * Lin et al. (2005) Lin C. Y., Stancil P. C., Gu J. P., Buenker R. J., Kimura M., 2005, Phys. Rev. A, 71, 062708
  * Mendoza (1983) Mendoza C., 1983, IAU Symp., 103, 143
  * Mies (1973) Mies F. H., 1973, Phys. Rev. A, 7, 942
  * Monteiro & Flower (1987) Monteiro T. S., Flower D. R., 1987, MNRAS, 228, 101
  * Ramos Padilla et al. (2022) Ramos Padilla A. F., Wang L., van der Tak F. F. S., Trager S., 2022 (arXiv:2205.11955)
  * Schöier et al. (2005) Schöier F. L., van der Tak F. F. S., van Dishoeck E. F., Black J. H., 2005, A&A, 432, 369
  * Sugahara et al. (2021) Sugahara Y., et al., 2021, ApJ, 923, 5
  * Tayal (2011) Tayal S. S., 2011, ApJS, 195, 12
  * Tayal & Zatsarinny (2017) Tayal S. S., Zatsarinny O., 2017, ApJ, 850, 147
  * Werner et al. (2010) Werner H.-J., Knowles P. J., Knizia G., Manby F. R., Schütz M., et al., 2010, Molpro, version 2010.1, a package of ab initio programs
  * Yan & Babb (2022a) Yan P.-G., Babb J. F., 2022a, Figshare, doi:10.6084/m9.figshare.21256365
  * Yan & Babb (2022b) Yan P.-G., Babb J. F., 2022b, RNAAS, 6, 145
  * Yau & Dalgarno (1976) Yau A. W., Dalgarno A., 1976, ApJ, 206, 652