# Subgroup sum graphs of finite abelian groups

Peter J. Cameron111School of Mathematics and Statistics, University of St
Andrews, North Haugh St Andrews, Fife, KY16 9SS, U.K., Email: pjc20@st-
andrews.ac.uk, ORCID:0000-0003-3130-9505, R. Raveendra Prathap222Research
Scholar, Department of Mathematics, Manonmaniam Sundaranar University,
Tirunelveli 627012, Tamil Nadu, India, Email<EMAIL_ADDRESS>
and T. Tamizh Chelvam333Department of Mathematics, Manonmaniam Sundaranar
University, Tirunelveli 627012, Tamil Nadu, India, Email<EMAIL_ADDRESS>ORCID:0000-0002-1878-7847

###### Abstract

Let $G$ be a finite abelian group, written additively, and $H$ a subgroup of
$G$. The _subgroup sum graph_ $\Gamma_{G,H}$ is the graph with vertex set $G$,
in which two distinct vertices $x$ and $y$ are joined if $x+y\in
H\setminus\\{0\\}$. These graphs form a fairly large class of Cayley sum
graphs. Among cases which have been considered previously are the _prime sum
graphs_ , in the case where $H=pG$ for some prime number $p$. In this paper we
present their structure and a detailed analysis of their properties. We also
consider the simpler graph $\Gamma^{+}_{G,H}$, which we refer to as the
_extended subgroup sum graph_ , in which $x$ and $y$ are joined if $x+y\in H$:
the subgroup sum is obtained by removing from this graph the partial matching
of edges having the form $\\{x,-x\\}$ when $2x\neq 0$. We study perfectness,
clique number and independence number, connectedness, diameter, spectrum, and
domination number of these graphs and their complements. We interpret our
general results in detail in the prime sum graphs.

##  1 Introduction

Cayley graphs are excellent models for interconnection networks. Hence, there
are many investigations in connection with parallel processing and distributed
computing. The definition of the Cayley graph was introduced by Arthur Cayley
in $1878$ to explain the concept of abstract groups which are described by a
set of generators. Cayley graphs of finite cyclic groups are studied in the
name of circulant graphs [2, 12, 13, 29, 32] and Cayley graphs of finite
groups are considered in [1, 9, 16, 17, 26, 27, 28, 31]. Other graphs from
finite groups are also studied in [5, 7, 15, 33]. Several authors studied
Cayley graphs of finite abelian groups in [8, 14, 30, 34]. The generalized
Cayley graphs of finite rings with respect to subsets are studied in [24, 25].

The square element graph of rings was studied by Biswas, Sen Gupta and Sen [3,
21, 22], while the power graph of semigroups was studied in [4]. The power
graph of groups are studied through the orders of elements in a group in [5,
7, 15, 33]. Raveendra Prathap and Tamizh Chelvam [19, 20] defined and studied
about the square graph and cubic power graph of finite abelian groups. Let $G$
be a finite abelian group with identity element $0.$ The square graph of $G$
denoted $\Gamma_{sq}(G)$ is an undirected simple graph with vertex set $G$ and
two distinct vertices $a$ and $b$ are adjacent in $\Gamma_{sq}(G)$ if $a+b=2t$
for some $t\in G$ and $2t\neq 0.$ Having defined the square graph
$\Gamma_{sq}(G)$ of $G,$ authors studied various properties of the complement
of square graph in [19]. Subsequently another graph called the cubic power
graph $\Gamma_{cpg}(G)$ is introduced and studied in [20]. These graphs can be
generalized, in the context of Cayley graphs of finite abelian groups, in
parallel with the generalizations made in the case of finite rings [24, 25].
For a fixed positive integer $n$, the generalized sum graph $\Gamma_{gsg}(G)$
is the simple undirected graph with vertex set $G$ and two distinct vertices
$x$ and $y$ are adjacent if $x+y\in S=\\{nt\mid nt\neq 0,t\in G\\}.$ One can
see that when $n=2,\Gamma_{gsg}(G)=\Gamma_{sq}(G)$ and when
$n=3,\Gamma_{gsg}(G)=\Gamma_{cpg}(G).$ Further note that when $n=1$ and $S$ is
a generating set for $G,$ $\Gamma_{gsg}(G)$ is the Cayley graph Cay$(G,S)$
[16]. When $n$ is a prime number $p,$ we call the generalized sum graph as the
prime sum graph $\Gamma_{psg}(G).$

In this paper, we extend the process of generalization, by defining the subset
sum graph $\Gamma_{G,H}$, where $G$ is a finite abelian group and $H$ a
subgroup of $G$: the vertices are the elements of $G$, and $x$ and $y$ are
joined if $x+y\in H\setminus\\{0\\}$. A closely related graph, which we call
the extended subset sum graph $\Gamma^{+}_{G,H}$ is defined similarly, but
without the restriction $x+y\neq 0$ for adjacency; it turns out to be easier
to work with.

##  2 Preliminaries

In this section, we recollect certain basic definitions and properties of
graphs which are essential for further reference. Throughout this paper,
$\Gamma=(V,E)$ is a finite simple graph with vertex set $V$ and edge set $E.$
A graph $\Gamma$ is said to be connected if there exists a path between every
pair of distinct vertices in $\Gamma.$ A graph $\Gamma$ is said to be complete
if every pair of distinct vertices are adjacent through an edge and the
complete graph on $n$ vertices is denoted by $K_{n}.$ The degree of a vertex
$v$ is the number of the edges in $\Gamma$ which are incident with $v.$ Note
that degree of each vertex $v$ in $K_{n}$ is $n-1.$ The distance $d(u,v)$
between the vertices $u$ and $v$ in $\Gamma$ is the length of the shortest
path between $u$ and $v.$ If no path exists between $u$ and $v$ in $\Gamma,$
then $d(u,v)=\infty.$ For a vertex $v\in V(\Gamma),$ the eccentricity $e(v)$
of $v$ is the maximum distance from $v$ to any other vertex in $V(\Gamma).$
That is, $e(v)=\max\\{d(v,w):w\in V(\Gamma)\\}.$ The radius of $\Gamma$ is the
minimum eccentricity among the vertices of $\Gamma$ and is denoted by
$rad(\Gamma).$ i.e., $rad(\Gamma)=\min\\{e(v):v\in V(G)\\}.$ The diameter of
$\Gamma$ is the maximum eccentricity among the vertices of $\Gamma$ and is
denoted by $diam(\Gamma).$ i.e., $diam(\Gamma)=\max\\{e(v):v\in V(G)\\}.$ The
girth of $\Gamma$ is the length of a shortest cycle in $\Gamma$ and is denoted
by $\mathop{\mathrm{girth}}(\Gamma).$

A clique of $\Gamma$ is a maximal complete subgraph of $\Gamma$ and the number
of vertices in the largest clique of $\Gamma$ is called the clique number of
$\Gamma$ and is denoted by $\omega(\Gamma)$.

For a vertex $x\in V(G),$ $N(x)$ is the set of all vertices in $G$ which are
adjacent to $x$ and $N[x]=N(x)\cup\\{x\\}.$ An independent set is a set of
vertices in a graph $\Gamma$, in which no two vertices are adjacent. The
cardinality of a maximal independent set is called the independence number and
is denoted by $\beta(\Gamma)$. A (vertex) proper colouring of $\Gamma$ is an
assignment of colours from a set $C$ such that no two adjacent vertices
receive same colour. If $|C|=k,$ we say that the corresponding colouring is a
proper $k$-colouring. A graph is $k$-colourable if it has a proper
$k$-colouring. The chromatic number of a graph $\Gamma$ is the least $k$ such
that $\Gamma$ is $k$-colourable and is denoted by $\chi(\Gamma)$. The clique
cover number $\theta(\Gamma)$ is the smallest number of complete subgraphs
required to cover all the vertices of $\Gamma$. Note that the independence
number and clique cover number of $\Gamma$ are just the clique number and
chromatic number of the complementary graph $\overline{\Gamma}$.

A graph $\Gamma$ is perfect if every induced subgraph of $\Gamma$ has clique
number equal to chromatic number. The Weak Perfect Graph Theorem of Lovász
[18] asserts that the complement of a perfect graph is also perfect; so every
induced subgraph of a perfect graph has independence number equal to clique
cover number. We also make use of the theorem of Dilworth [10] asserting that
the comparability graph (or incomparability graph) of a partial order is
perfect.

The open neighbourhood $N_{\Gamma}(v)$ of the vertex $v$ in $\Gamma$ is the
set of vertices adjacent to $v$, while the closed neighbourhood of $v$ is
$\\{v\\}\cup N_{\Gamma}(v)$. The domination number of a graph is the least
cardinality of a set of vertices for which the union of their closed
neighbourhoods is the whole vertex set

##  3 Definition and basic properties

In this section, we give formal definitions of our graphs, describe their
structure in terms of the structure of $G$ and $H$, examine connectedness,
diameter, girth, and self-centredness, and show that these graphs are perfect.
Let $G$ be a finite abelian group, and $H$ a subgroup of $G$. We define the
_extended subgroup sum graph_ $\Gamma^{+}_{G,H}$ to have vertex set $G$ and
edges $\\{x,y\\}$ whenever $x+y\in H$; and the _subgroup sum graph_
$\Gamma_{G,H}$ to have the same vertex set and edges $\\{x,y\\}$ whenever
$x+y\in H\setminus\\{0\\}$.

We see that the generalized sum graph $\Gamma_{gsg}(G)$ previously mentioned
is the subgroup sum graph $\Gamma_{G,tG}$, while for any prime $p$, the prime
sum graph $\Gamma_{psg}(G)$ is the subgroup sum graph $\Gamma_{G,pG}$.

The next result deals with the case where the subgroup $H$ is trivial (either
$\\{0\\}$ or $G$).

###### Theorem 3.1

Let $G$ be a finite abelian group.

  1. (a)

If $H=\\{0\\}$, then the subgroup sum graph $\Gamma_{G,H}$ is a null graph on
the vertex set $G$, while the extended subgroup sum graph $\Gamma^{+}_{G,H}$
is a partial matching where elements other than the identity and involutions
are joined to their inverses.

  2. (b)

If $H=G$, then the extended subgroup sum graph $\Gamma^{+}_{G,H}$ is complete,
and the subgroup sum graph $\Gamma_{G,H}$ is obtained by deleting a matching
covering all vertices except the identity and involutions.

###### Proof

If $H=\\{0\\},$ then the only edges in $\Gamma^{+}_{G,H}$ are those of the
form $\\{a,-a\\}$ where $2a\neq 0$; there are no edges in $\Gamma_{G,H}$.

If $H=G,$ then every pair $\\{a,b\\}$ with $a\neq b$ is an edge of
$\Gamma^{+}_{G,G}$, and all those with $b\neq-a$ are edges of $\Gamma_{G,H}$.
$\Box$

The graphs considered in Theorem 3.1 are not very interesting, so where
necessary below we assume that $1<|H|<|G|$.

For a prime $p$ and an abelian group $G,$ we have the following for the prime
sum graph $\Gamma_{psg}(G).$

  1. (a)

$pG=\\{0\\}$ if and only if $G$ is elementary abelian (a direct sum of cyclic
groups $C_{p}$ of order $p$).

  2. (b)

$pG=G$ if and only if $p$ does not divide $|G|$.

Let $S(G)$ denote the set of solutions of $2x=0$ in a group $G$, and
$s(G)=|S(G)|$. If $G=C_{2^{k_{1}}}\times\cdots\times C_{2^{k_{r}}}\times A$,
where $|A|$ is odd and $k_{1},\ldots,k_{r}>0$, then $s(G)=2^{r}$.

The basic structure of these graphs $\Gamma^{+}_{G,H}$ and $\Gamma_{G,H}$ are
given in the next result.

###### Theorem 3.2

Let $H$ be a subgroup of the abelian group $G$, with $|H|=k$ and $|G/H|=m$.

  1. (a)

The extended subgroup sum graph $\Gamma^{+}_{G,H}$ has $(m+s(G/H))/2$
connected components, of which $s(G/H)$ are complete graphs $K_{k}$ (whose
vertex sets are the cosets of $H$ having order $1$ or $2$ in $G/H$), and
$(m-s(G/H))/2$ are complete bipartite graphs $K_{k,k}$ (whose vertex sets are
the union of two cosets $H+a$ and $H-a$ for some $a\in G$ with $2a\notin H$).

  2. (b)

The subgroup sum graph $\Gamma_{G,H}$ is obtained from the extended subgroup
sum graph $\Gamma^{+}_{G,H}$ by deleting a perfect matching from every
component which is complete bipartite, and deleting a matching from a complete
component on a coset $H+a$ covering all elements other than elements of $S(G)$
lying in this coset (if any).

###### Proof

(a) The neighbours of $a$ in $\Gamma^{+}_{G,H}$ are the elements of the coset
$H-a$ (possibly excluding $a$). If $H-a\neq H+a$, then we have a complete
bipartite graph on these two cosets. If $H-a=H+a$, so that this coset has
order $2$ in $G/H$, then we have a complete graph on this coset.

(b) To obtain the subgroup sum graph, we must delete edges of the form
$\\{a,-a\\}$ for which $a\neq-a$ (that is, $a$ is not the identity or an
involution). $\Box$

Theorem 3.2 gives a complete description of graphs $\Gamma^{+}_{G,H}$ and
$\Gamma_{G,H},$ and enables us to determine their properties and parameters,
as we do in the rest of the paper. First, though, we describe the components
in a little more detail, and introduce three parameters we will use throughout
the paper, counting three different types of cosets of $H$ in $G$:

  * •

_Type 1_ , cosets $H+a$ for which $2a\notin H$ (that is, cosets distinct from
their inverses in $G/H$). For such cosets, $(H+a)\cup(H-a)$ is a connected
component of both $\Gamma^{+}_{G,H}$ and $\Gamma_{G,H}$, being complete
bipartite in the first and complete bipartite minus a perfect matching in the
second.

  * •

_Type 2_ , cosets $H+a$ for which $2a\in H$ but $H+a$ does not contain a
solution of $2x=0$. For these, $H+a$ is a connected component of both graphs,
and is complete in the first and complete minus a perfect matching in the
second. (This type can only occur if $|H|$ is even. We have to exclude $|H|=2$
here since in that case $K_{2}$ minus a matching consists of two isolated
vertices.)

  * •

_Type 3_ , cosets $H+a$ containing a solution of $2x=0$. For these, $H+a$ is a
connected component, and is complete in the first graph and complete minus a
matching of size $(k-s(H))/2$ in the second. (This case always occurs, since
the coset $H$ has this form. See below for the proof that every such coset
contains $s(H)$ solutions of $2x=0$.)

For $i=1,2,3$, we let $m_{i}$ be the number of cosets of Type $i$, so that
$m_{1}+m_{2}+m_{3}=m=|G/H|$, and $m_{2}+m_{3}=s(G/H)$.

We claim that the number of solutions of $2x=0$ in a coset is equal to $s(H)$
if the coset has Type 3, $0$ otherwise. This is clear for the coset $H$, so
let $H+a$ be another coset. Clearly there are no solutions of $2x=0$ in the
coset unless it has Type 3, so suppose this is the case. Then $K=H\cup(H+a)$
is a subgroup of $G$, and $S(K)$ is a subgroup of $G$ containing $S(H)$ as a
subgroup of index $2$. Thus $s(K)=2s(H)$, so there are $s(H)$ elements in
$H+a$ satisfying $2x=0$. In particular, we see that $m_{3}s(H)=s(G)$.

Thus, in $\Gamma^{+}_{G,H}$, there are $m_{1}/2$ components which are complete
bipartite $K_{k,k}$, and $m_{2}+m_{3}$ components which are complete graphs
$K_{k}$. In $\Gamma_{G,H}$, there are $m_{1}/2$ components which are a
complete bipartite graph minus a perfect matching, $m_{2}$ components which
are complete graphs $K_{k}$ minus a perfect matching, and $m_{3}$ components
which are $K_{k}$ minus a matching of size $(k-s(H))/2$.

In particular, we see that the numbers $m$, $s(G)$, $s(H)$ and $s(G/H)$
determine the number of cosets of each type.

##  4 Connectedness, diameter, girth and perfectness

We consider first a group of graph properties and parameters.

###### Proposition 4.1

Let $G$ be an abelian group and $H$ be a subgroup of $G.$ Suppose that
$|G|>2$. Then the following are equivalent:

  1. (a)

$\Gamma^{+}_{G,H}$ is connected;

  2. (b)

$\Gamma_{G,H}$ is connected;

  3. (c)

$H=G$.

###### Proof

The number of components of $\Gamma^{+}_{G,H}$ is $(m+s(G/H))/2$. Since each
of $m$ and $s(G/H)$ is at least $1$, the graph is connected if and only if
both are $1$, which implies that $H=G$. The converse is clear from Theorem
3.1.

Since $\Gamma_{G,H}$ has at least as many components as $\Gamma^{+}_{G,H}$, we
see that if it is connected then $H=G$. Conversely, if $H=G$, then we could
only disconnect the graph by deleting a matching if $|G|=2$. $\Box$

###### Corollary 4.2

Suppose that $|G|>2$ and $H\neq G$. Then the complements of $\Gamma^{+}_{G,H}$
and $\Gamma_{G,H}$ are connected and have diameter at most $2$, with equality
except for $\overline{\Gamma}_{G,\\{0\\}}$ (which is complete). If $k>2$, then
these complements have radius equal to diameter, and so are self-centred.

###### Proof

It is clear that the diameter of complements of $\Gamma^{+}_{G,H}$ and
$\Gamma_{G,H}$ is $2$. If a vertex $g$ has eccentricity $1,$ then it is joined
to all other vertices, that is, it is isolated in $\Gamma^{+}_{G,H}$ or
$\Gamma_{G,H}$ as appropriate. This can only occur if $k=|H|=2$. $\Box$

###### Corollary 4.3

  1. (a)

The extended subgroup sum graph $\Gamma^{+}_{G,H}$ has girth $3$ if $|H|>2$,
$4$ if $|H|=2$ and $G/H$ is not an elementary abelian $2$-group, or $\infty$
otherwise.

  2. (b)

The subgroup sum graph $\Gamma(G,H)$ has girth $3$ if $|H|>3$, $6$ if $|H|=3$,
or $\infty$ if $|H|=2$.

###### Proof

(a) There is always at least one component $K_{k}$, since $s(G/H)\geq 1$; if
$k>2,$ this component contains a triangle. Otherwise, there is a component
$K_{k,k}$ unless $s(G/H)=m$.

(b) If we delete a matching which is not perfect from a complete graph on at
least four vertices, what is left contains a triangle. If $k=3,$ then
$s(G)=s(G/H)$ and so there are no cycles of length $3$, but removing a perfect
matching from $K_{3,3}$ produces a $6$-cycle. If $k=2,$ then the graph
consists of isolated vertices and edges. $\Box$

###### Corollary 4.4

The subgroup sum graph and extended subgroup sum graph are perfect graphs.

###### Proof

It suffices to show that each connected component is perfect. For the extended
graph, these components are complete or complete bipartite, which are well
known to be perfect. In the other case, we have to deal with the complement or
bipartite complement of a matching. In the first case, the result holds since
a matching is clearly perfect. The graph obtained by removing a perfect
matching from $K_{k,k}$ is the comparability graph of the partial order on
$\\{a_{1},\ldots,a_{k},b_{1},\ldots,b_{k}\\}$ in which
$\\{a_{1},\ldots,a_{k}\\}$ and $\\{b_{1},\ldots,b_{k}\\}$ are antichains and
$a_{i}<b_{j}$ if and only if $i\neq j$; and the comparability graph of a poset
is perfect, by Dilworth’s Theorem. $\Box$

From the above theorem, we have the following corollary for the cubic power
graph of a finite abelian group.

###### Corollary 4.5

[20, Theorem 4.11] Let $G$ be a finite abelian group. Then the cubic power
graph $\Gamma_{cpg}(G)$ is perfect.

Also, we have the following corollary which is applicable for the complement
of the square graph of a finite abelian group.

###### Corollary 4.6

[19, Theorem 3.2] Let $G$ be a finite abelian group. Then the complement
$\overline{\Gamma}_{sq}(G)$ is perfect.

##  5 Cliques and cocliques

We now compute the clique number and independence number of subgroup sum
graphs $\Gamma_{G,H}$ where $H$ is a proper subgroup of $G.$

###  5.1 General results

We compute the clique number and independence number of the graphs
$\Gamma_{G,H}$ where $H$ is a proper subgroup of $G.$ (By Corollary 4.4, the
chromatic number is equal to the clique number, and the clique cover number is
equal to the independence number, so we get these two further parameters for
free.)

###### Theorem 5.1

Let $G$ be a finite abelian group, and $H$ a non-trivial subgroup of $G$.
Suppose that $|H|=k$, $|G/H|=m$, and let $m_{1},m_{2},m_{3}$ be as above.

  1. (a)

The clique number of the extended subgroup sum graph $\Gamma^{+}_{G,H}$ is
equal to $k$, and the independence number is equal to $km_{1}/2+m_{2}+m_{3}$.

  2. (b)

The clique number of the subgroup sum graph $\Gamma_{G,H}$ is $(k+s(H))/2$.

  3. (c)

The independence number of the subgroup sum graph $\Gamma_{G,H}$ is equal to
$km_{1}/2+2(m_{2}+m_{3})$ if $s(H)<|H|$, and $km_{1}/2+2m_{2}+m_{3}$ if
$s(H)=|H|$.

###### Proof

(a) Clearly $H$ is a maximal clique, while a maximal independent set takes one
bipartite block from each complete bipartite component and one vertex from
each complete component. (By assumption, $k\geq 2$, so the cliques of size $2$
in the complete bipartite graphs are not larger than $k$.)

(b) When deleting edges from the extended subgroup sum graph, the bipartite
components remain bipartite, and so have clique number $2$.

In a complete component, corresponding to a coset of Type 2, we delete a
perfect matching, giving a graph with clique number $k/2$. If there is a coset
of Type 3, it contains a clique of size $(k+s(H))/2$. The second quantity is
larger, and there is always a Type 3 coset, namely $H$ itself. Now since
$k\geq 2$, we have $(k+s(H))/2\geq 2$.

(c) It is easy to see that if we delete a perfect matching from $K_{k,k}$ with
$k\geq 2$, the resulting graph still has independence number $k$.

A Type 2 coset carries a complete graph with a perfect matching removed, so
contains an independent set of size $2$. Similarly, a Type 3 coset contains an
independent set of size $2$ unless all its elements satisfy $2x=0$, in which
case it is complete and has independence number $1$ (this occurs if and only
if $s(H)=|H|$).

Summing over all cosets gives the result. $\Box$

Using the above Theorem 5.1, one can obtain the clique number of the cubic
power graph obtained in [20, Theorem 3.8]. In fact, in the language of the
cubic power graph $\Gamma_{cpg}(G)$ of an abelian group $G,$ $H=3G$ and
$|H|=k=\frac{|G|}{3^{r}}.$ Hence, we have the following corollary.

###### Corollary 5.2

[20, Theorem 3.8] Let $G$ be a finite abelian group. Then the chromatic number
$\omega(\Gamma_{cpg}(G)=s(H)+\left\lceil\frac{\frac{|G|}{3^{r}}-s(H)}{2}\right\rceil=(k+s(H))/2.$

###  5.2 Prime sum graphs

Now we calculate these numbers for the prime sum graph of a finite abelian
group. It is clear from our analysis that the prime $2$ behaves very
differently from odd primes. We will deal with odd primes first. Note that, by
our earlier assumptions, we can assume that $|G|$ is divisible by the prime
$p$ in question, otherwise $pG=G$.

####  5.2.1 Odd prime $p$

Let $G$ be a finite abelian group. Then $H=pG$ is a subgroup of $G$ whose
index is $p^{r}$, where $r$ is the number of cyclic summands of $p$-power
order when $G$ is expressed as a direct sum of cyclic groups; the quotient
$G/pG$ is an elementary abelian $p$-group. So $s(G/H)=1$. Also, all
$2$-elements of $G$ are contained in $pG$, so (in the notation used above) we
have $m_{2}=0$, $m_{3}=1$, and $m_{1}=p^{r}-1$. Also, if $G$ has $q$ cyclic
summands of $2$-power order, then $s(H)=2^{q}$, and $s(H)=|H|$ if and only if
$G\cong C_{2}^{q}\times C_{p}^{r}$.

From our earlier results, we find that $\Gamma^{+}_{G,pG}$ has clique number
$k=|G|/p^{r}$ and independence number $k(p^{r}-1)/2+1$, while $\Gamma_{G,pG}$
has clique number $k/2+2^{q-1}$ and independence number $k(p^{r}-1)/2+2$
unless $G\cong C_{2}^{q}\times C_{p}^{r}$, in which case the independence
number is $k(p^{r}-1)/2+1$. (If $q=0$, then $|G|$ is odd, so $k$ is odd and
the clique number is $(k+1)/2$.)

####  5.2.2 The prime $2$

We can write $G=A\times B$, where $A$ has odd order and $B$ has order a power
of $2$. Suppose that $B$ is the product of $r$ cyclic groups, of which $q$
have order $2$. Then $2G=A\times 2B$, where $B$ is the product of $r-q$ cyclic
groups, We have $G/2G$ elementary abelian of order $2^{r}$; so every coset
$2G+x$ satisfies $2x\in 2G$, and there are $2^{q}$ cosets containing
involutions. Thus $m_{1}=0$, $m_{2}=2^{r}-2^{q}$, and $m_{3}=2^{q}$. Moreover,
$S(2G)$ is an elementary abelian of order $2^{r-q}$, so $S(2G)=2G$ if and only
if $G$ is the product of cyclic groups of orders $2$ and $4$ only.

So $\Gamma^{+}(G,2G)$ has clique number $k=|2G|=|G|/2^{r}$, and independence
number $2^{r}$; and $\Gamma(G,2G)$ has clique number $(k+2^{r-q})/2$, and
independence number $2^{r+1}$ unless $G$ is a product of cyclic groups of
orders $2$ and $4$, in which case the independence number is $2^{r+1}-2^{q}$.

##  6 Spectrum

Since the graphs $\Gamma^{+}_{G,H}$ and $\Gamma_{G,H}$ are disconnected if
$H<G,$ we can compute the spectrum by considering the components separately.
Theorem 3.2 gives the number of components of each type. As before we let
$|H|=k$ and $|G:H|=m$.

For $\Gamma^{+}_{G,H}$, the situation is simple: the components are either
complete bipartite $K_{k,k}$ (with eigenvalues $k$ and $-k$ each with
multiplicity $1$, and $0$ with multiplicity $2k-2$) or complete $K_{k}$ (with
eigenvalues $k-1$ with multiplicity $1$ and $-1$ with multiplicity $k-1$).

For $\Gamma_{G,H}$ things are a little more complicated. There are three types
of components:

  1. (a)

$K_{k,k}$ minus a perfect matching. This is a distance-regular graph; its
eigenvalues are $k-1$ and $-(k-1)$, each with multiplicity $1$, and $1$ and
$-1$, each with multiplicity $k-1$.

  2. (b)

$K_{k}$ minus a perfect matching.

  3. (c)

$K_{k}$ minus a partial matching covering $k-s(H)$ vertices.

Consider the graph $K_{a+b}$, with $a$ even, minus a matching covering $a$
vertices. (We assume that $a>0$ and $a+b\geq 4$ to avoid trivial cases.) This
graph occurs in various contexts. For example, it is a Turán graph, maximizing
the number of edges in a graph containing no complete subgraph of order
$(a/2)+b+1$. More relevant here, it is a generalized line graph in the sense
of Hoffman; if $a>2$, its smallest eigenvalue is $-2$, with multiplicity
$(a/2)-1$ (see [6]). For $a,b>0$, its eigenvalues are as follows:

  1. (a)

the roots of the quadratic $x^{2}-(a+b-3)x-(a+2b-2)$, each with multiplicity
$1$;

  2. (b)

$0$, with multiplicity $a/2$;

  3. (c)

$-2$, with multiplicity $(a/2)-1$;

  4. (d)

$-1$, with multiplicity $b-1$.

These (and the corresponding eigenvectors) can be calculated, using the fact
that the partition into the vertices covered and uncovered by the matching is
equitable, in the sense of Godsil and Royle [11]. In detail: let the adjacency
matrix have the form $A(\Gamma)=\displaystyle{\begin{pmatrix}A&J\\\
J&B\end{pmatrix}}$, where $A$ is the adjacency matrix of $K_{a}$ minus a
matching, $B$ the adjacency matrix of $K_{b}$, and $J$ an all -$1$ matrix of
appropriate size. Then the subspace of $\mathbb{R}^{a+b}$ spanned by
$(1^{a},0^{b})$ and $(0^{a},1^{b})$ is $A(\Gamma)$-invariant, and the
restriction of $(\Gamma)$ to this subspace is
$\displaystyle{\begin{pmatrix}a-2&b\\\ a&b-1\\\ \end{pmatrix}}$, with
eigenvalues as in (a). The orthogonal subspace is spanned by three types of
vectors: those with zero entries in the last $b$ coordinates, and where
entries in positions corresponding to the ends of (deleted) matching edges are
negatives of each other; those with zero entries in the last $b$ coordinates,
and with entries in positions corresponding to the ends of matching edges are
equal and all entries sum to $0$; and those with zero entries in the first $a$
coordinates, and with the remaining entries summing to zero. These are seen to
be eigenvectors with the eigenvalues and multiplicities given in (b)–(d).

##  7 Domination

The domination number of a graph is the least cardinality of a set of vertices
for which the union of their closed neighbourhoods is the whole vertex set.
The domination number of $K_{k}$ is clearly $1$, and that of $K_{k,k}$ is $2$.
So the domination number of $\Gamma^{+}_{G,H}$ is $m=|G:H|$. Similarly the
domination number of $K_{k,k}$ minus a perfect matching is $2$ (two vertices
on one of the deleted edges form a dominating set), while the domination
number of $K_{k}$ minus a matching is $1$ if the matching is not a perfect
matching and $2$ if it is. So the domination number of $\Gamma_{G,H}$ is
$m_{1}+2m_{2}+m_{3}=|G:H|+m_{2}$.

The complement of a disconnected graph $\Gamma$ with no isolated vertices has
domination number $2$: two vertices in different components of $\Gamma$ form a
dominating set in $\overline{\Gamma}$. By Proposition 4.1, provided that
$H<G$, the domination numbers of $\overline{\Gamma}^{+}_{G,H}$ and
$\overline{\Gamma}_{G,H}$ are both $2$.

##  8 Reconstructing the group

In studies of graphs defined on groups, one topic which has been considered is
the extent to which the graph determines the group. For example, Solomon and
Woldar [23] showed that the _commuting graph_ (with $x$ joined to $y$ if
$xy=yx$) of a finite simple group determines the group.

In our situation, things are a bit different: the graphs only determine
certain parameters of the pair $(G,H)$. We note that, in either case, the
number of vertices of the graph is equal to $|G|$. The connected components
have sizes $k$ and $2k$, and the number $k$ occurs at least once (for the
subgroup $H$); so we can also determine $|H|$.

Suppose that we are given $\Gamma^{+}_{G,H}$. Then the number of components of
size $k$ is equal to $s(G/H)$. So this is all the information we get: two
pairs $(G_{1},H_{1})$ and $(G_{2},H_{2})$ with $s(G_{1}/H_{1})=s(G_{2}/H_{2})$
have isomorphic subgroup sum graphs.

For the graph $\Gamma_{G,H}$, we obtain the above information, and also the
numbers $s(H)$ and $s(G)$. For the components of size $k$ are either complete
minus a perfect matching of size $k/2$ ($m_{2}$ of these) or complete minus a
matching of size $(k-s(H))/2$ ($m_{3}$ of these). Since $s(H)\neq 0$, we can
distinguish the two types, and hence find $m_{2}$ and $m_{3}$; and from a Type
3 coset we can recover $s(H)$, and hence $s(G)=m_{3}s(H)$.

##  9 A generalization

Let $H$ and $K$ be subgroups of the abelian group $G$ with $H\neq K.$ We can
extend our previous definition by defining the generalized subgroup sum graph
$\Gamma_{G;H,K}$ to be the graph with vertex set $G$ in which $x$ and $y$ are
joined if $x+y\in H$ but $x+y\notin K$.

We lose no generality by assuming that $K\leq H$, since with the definition
just given, $\Gamma_{G;H,K}=\Gamma_{G;H,H\cap K}$. We shall always make this
assumption. Now our previous subgroup sum graph $\Gamma_{G,H}$ is
$\Gamma_{G;H,\\{0\\}}$. Moreover, $\Gamma_{G;G,H}$ is the complement of the
extended subgroup sum graph $\Gamma^{+}_{G,H}$. We have not investigated these
graphs further.

## Acknowledgments

The research work T. Tamizh Chelvam is supported by CSIR Emeritus Scientist
Scheme (No.21 (1123)/20/EMR-II) of Council of Scientific and Industrial
Research, Government of India.

## References

  * [1] M. Afkhami, K. Khashyarmanesh, K. Nafar, Generalized Cayley graphs associated to commutative rings, Linear Algebra Appl. 437 (2012), 1040–1049.
  * [2] B. Alspach, T. D. Parsons, Isomorphism of Circulant Graphs and Digraphs, Discrete Mathe. 25 (1979), 97–108.
  * [3] B. Biswas, R. Sen Gupta, On the connectedness of square element graphs over arbitrary rings, South East Asian Bull. Math. 43(2) (2019), 153–164.
  * [4] B. Biswas, R. Sen Gupta, M. K. Sen, S. Kar, Some properties of square element graphs over semigroups, AKCE International Journal of Graphs and Combinatorics 17(1) (2020), 118–130.
  * [5] P. J. Cameron and S. Ghosh, The power graph of a finite group, Discrete Math. 311 (2011), 1220–1222.
  * [6] P. J. Cameron, J.-M. Goethals, J. J. Seidel and E. E. Shult, Line graphs, root systems and elliptic geometry, J. Algebra 43 (1976), 305–327.
  * [7] I. Chakrabarty, S. Ghosh and M. K. Sen, Undirected power graphs of semi groups, Semigroup Forum 78 (2009), 410–426.
  * [8] E. Dobson, P. Spiga and G. Verret, Cayley graphs on abelian groups, Combinatorica 36 (4) (2016), 371–393.
  * [9] I. J. Dejter, O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 129 (2003), 319–328
  * [10] Robert P. Dilworth, A decomposition theorem for partially ordered sets, Ann. Math. 51 (1950), 161–166.
  * [11] Chris Godsil and Gordon Royle, Algebraic Graph Theory, Springer, New York, 2001.
  * [12] Q. Huang, A classification of circulant DCI(CI)- digraphs of 2-power order, Discrete Math. 265 (2003), 71– 84.
  * [13] M. Jixiang and H. Qiongxiang, Isomorphisms of circulant diagaphs, Appl. Math. J. Chinese Univ. Ser. A , 9(1994), 405–409.
  * [14] W. Klotz and T. Sander, Integral Cayley graphs over abelian groups, Electron. J. Combin. 17 (2010), # 81.
  * [15] A. V. Kelarev and S. J. Quinn, A combinatorial property and power graph of semigroups, Commentationes Mathematicae Universitatis Carolinae, 45(1), (2004), 1–7.
  * [16] S. Lakshmivarahan and S. K. Dhall, Ring, torus, hypercube architectures algorithms for parallel computing, Parallel Computing, 25 (1999), 1877–1906.
  * [17] J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory 37(4) (2001), 213–219.
  * [18] Lászlo Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Mathematics 2 (1972), 253–267.
  * [19] R. Raveendra Prathap and T. Tamizh Chelvam, Complement graph of the square graph of finite abelian groups, Houston Journal of Mathematics. 46(4), (2020), 845–857.
  * [20] R. Raveendra Prathap and T. Tamizh Chelvam, The cubic power graph of finite abelian groups, AKCE International journal of graphs and combinatorics. 18(1), (2021), 16–24.
  * [21] R. Sen Gupta and M. K. Sen, The square element graph over a finite commutative ring, South East Asian Bull. Math. 39 (3) (2015), 407–428.
  * [22] R. Sen Gupta, M. K. Sen, The square element graph over a ring, Southeast Asian Bull. Math. 41 (5) (2017) 663–682.
  * [23] R. M. Solomon and A. J. Woldar, Simple groups are characterized by their non-commuting graphs, J. Group Theory 16 (2013), 793–824.
  * [24] T. Tamizh Chelvam and S. Anukumar Kathirvel, Generalized unit and unitary Cayley graphs of finite rings, J. Algebra Appl., 18(1) (2019), # 1950006 [21 pages].
  * [25] T. Tamizh Chelvam, S. Anukumar Kathirvel and M. Balamurugan, Domination in generalized unit and unitary Cayley graphs of finite rings, Indian J. Pure Appl. Math. 51(2) (2020), 533–556.
  * [26] T. Tamizh Chelvam, G. Kalaimurugan and Well Y. Chou, Signed star domination number of Cayley graphs, Discrete Math. Algorithms Appl. 4(2) (2012), # 1250017 [10 pages].
  * [27] T. Tamizh Chelvam and S. Mutharasu, Subgroups as efficient dominating set in Cayley Graphs, Discrete Appl. Math. 161(9) (2013), 1187–1190.
  * [28] T. Tamizh Chelvam and S. Mutharasu, Efficient open domination in Cayley graphs, Appl. Math. Lett. 25 (2012), 1560–1564.
  * [29] T. Tamizh Chelvam and S. Raja, Integral circulant graphs with four distinct eigenvalues, Discrete Math. Algorithms Appl. 10(5) (2018), # 1850062 [10 pages].
  * [30] T. Tamizh Chelvam and I. Rani, Independent Domination number of a Cayley Graph on $\mathbb{Z}_{n}$, J. Combin. Math. Combin. Comput. 69(2009), 251–255.
  * [31] T. Tamizh Chelvam and M. Sivagami, Structure and substructure connectivity of Cayley graphs, Arab Journal of Mathematical Science 27(1), (2021), 94–103.
  * [32] T. Tamizh Chelvam, S. Raja and I. Gutman, Strongly regular integral Circulant graphs and their energies, Bulletin of International Mathematical Virtual Institute 2 (2012), 9–16.
  * [33] T. Tamizh Chelvam and M. Sattanathan, Power graph of finite abelian groups, Algebra and Discrete Mathematics 16(1) (2013), 33–41.
  * [34] E. Vatandoost and Y. Golkhandypour, Integral Cayley graph on some of abelian groups, TJEAS Journal 3(6) (2013), 489–492.


# On the Björling problem for Born-Infeld solitons

Sreedev Manikoth BS-MS Programme, Indian Institute of Science, Education and
Research, Pune, Maharashtra, India

###### Abstract

The Björling problem and its solution is a well known result for minimal
surfaces in Euclidean three-space. The minimal surface equation is similar to
the Born-Infeld equation, which is naturally studied in physics. In this semi-
expository article, we ask the question of the Björling problem for Born-
Infeld solitons. This begins with the case of locally Born-Infeld soliton
surfaces and later moves on to graph-like surfaces. We also present some
results about their representation formulae.

##  1 Introduction

In general zero-mean curvature surfaces are called minimal surfaces. The
theory of minimal surfaces in Euclidean 3-space is well studied with several
results. Any non-parametric minimal surface $(x,y,\psi(x,y))$ satisfies the
minimal surface equation,

$(1+\psi_{y}^{2})\psi_{xx}-2\psi_{x}\psi_{y}\psi_{xy}+(1+\psi_{x}^{2})\psi_{yy}=0$

.

This equation is similar to the Born-Infeld equation,

$(1-\psi_{y}^{2})\psi_{xx}+2\psi_{x}\psi_{y}\psi_{xy}-(1+\psi_{x}^{2})\psi_{yy}=0$

This motivates us to ask similar questions about the Born-Infeld solitons. In
particular one can ask, can we find an analog of Weierstrass-Ennepper
representation formulae for the Born-Infeld solitons? This was answered by
Barbishov and Chernikov, which we would shortly see in this article. We can
also ask for an analog of the Björling problem. In this article we give an
answer to that question. We start with the definition of locally Born-Infeld
soliton surfaces.

######  Definition 1.1 (Born-Infeld soliton general surfaces).

A surface is said to be a Born-Infeld soliton general surface if it is locally
of the form $(\psi(y,z),y,z)$ , $(x,\psi(x,z),z)$ or $(x,y,\psi(x,y))$ where
$\psi$ solves the Born-Infeld equation.

in [6], R. Dey and R.K. Singh showed that timelike minimal graphs over $y-z$
plane have Born-Infeld solitons as height function. We show that the same
result holds for timelike minimal graphs over the $x-z$ plane. We also prove
that any timelike minimal surface without singularities is locally a graph
over $x-z$ or $y-z$ plane. Thus we conclude timelike minimal surfaces without
singularities are Born-Infeld general surfaces.

We use the above result to solve Björling problem for Born-Infeld general
surfaces. Björling problem for timelike minimal surfaces has already been
solved in [8] and [10]. For regular space or timelike curves, one gets a
timelike minimal surface without singularities as the solution to the Björling
problem. This implies that for regular space or timelike curves Björling
problem for Born-Infeld general surfaces can be solved.

In [3] E.A Paxton showed that any compact subset of a global properly immersed
timelike minimal surface is a timelike minimal graph over some timelike plane.
We generalize the result in [6] to show timelike minimal graphs over any
timelike plane have Born-Infeld soliton as height function. Moreover, we see
that for regular real analytic curve $c$ and vector field $n$ which have
entire split-holomorphic functions as an analytic extension we get a global
properly immersed timelike surface as the solution to the Björling problem. So
solving timelike Björling problem for such real analytic strips and looking at
their compact subsets is a way to find Born-Infeld solitons. In particular, we
note that for real analytic strips of regular real-analytic curves and unit
vector fields $(c,n)$ with components as polynomials in $t$, one can use the
above result to find Born-Infeld solitons.

Graph-like Born-Infeld solitons are of special interest to physicists and we
try to ask a similar question for them. From [6] we note that spacelike
minimal graphs and timelike minimal graphs over $y-z$ plane are Born-Infeld
soliton graphs. We use this idea and ask for what kind of real analytic strips
$(c,n)$, do we get a spacelike minimal graph or timelike minimal graph as a
solution to the Björling problem. We characterize such curves and normals for
which graphical solutions can or cannot be found.

Lastly, we go through the representation formulae given by Barbishov and
Chernikov. We show that the Barbishov and Chernikov representation formula,
like the Weierstrass-Enneper representation, fails at zero Gauss curvature
points. In [5] L. McNertney showed that any surface in $\mathbb{L}^{3}$ which
can be expressed as the sum of two lightlike curves with linearly independent
velocities is timelike minimal. We see that the Barshiov and Chernikov
representation formula also expresses the surface as a sum of two lightlike
curves with linearly independent velocities, implying these Born-Infeld
solitons are timelike minimal in $\mathbb{L}^{3}$. Also, normal vector fields
of these surfaces parametrized by $r-s$ coordinates are the same.

We note that A. Das also in [1] independently solved the Björling problem for
Born-Infeld solitons, $X(\omega(t))=c(t)$,$N(\omega(t))=n(t)$ where
$\omega(t)$ is a curve in $r-s$ plane determined by $c$ and $n$. They also
shows that Björling problem for Born-Infeld solitons may not have unique
solutions.

Our results here are dependent on plenty of earlier work done by several
mathematicians. We would have a look at those as we go through them. .

As a summary, we aim to describe three results. We would first prove that any
timelike minimal surface without singularities is locally the graph of a Born-
Infeld soliton over $y-z$ or $x-z$ plane. This answers the Björling problem
for surfaces that are locally Born-Infeld solitons, in the special case when
the curve is assumed to be regular. The third section is about some
corollaries of E.A Paxton’s results ([3]). In the fourth section, we deal with
the Björling problem of surfaces that are globally Born-Infeld solitons and
present some results. In the last few sections, we study a special class of
Born-Infeld solitons, given by Barbishov and Chernikov and we would prove some
theorems about them.

Throughout this article we will be using the following definition for the
Lorentz-Minkowski space, $\mathbb{L}^{3}$.

######  Definition 1.2.

$\mathbb{L}^{3}$ is $\mathbb{R}^{3}$ with the metric
$ds^{2}=dx^{2}+dy^{2}-dz^{2}$

##  2 Regular timelike minimal surfaces and Born-Infeld solitons

We will start with defining Born-Infeld solitons.

######  Definition 2.1 (Born-Infeld soliton).

Let $\Omega\subset$ $\mathbb{R}^{2}$ be an open subset. Let $(u,v)$ $\in$
$\Omega$. Now we will denote this subset by $\Omega_{(u,v)}$.A map $\phi$:
$\Omega_{(u,v)}$ $\rightarrow$ $\mathbb{R}$ is said to be a Born-Infeld
soliton if it solves the Born-Infeld equation in the variables $u,v$.

First we will show a lemma about timelike minimal graphs over $x-y$ plane.

######  Lemma 2.1.

Any timelike minimal graph $X(x,y)=(x,y,\phi(x,y))$ without singularities is
locally is a graph of the form $(x,\psi(x,z),z)$ or $(\psi(y,z),y,z)$ for some
Born-Infeld soliton $\psi$.

###### Proof.

Here the Jacobian of the surface $X$ at a point p looks like this,

$\begin{pmatrix}1&0\\\ 0&1\\\ \phi_{x}(p)&\phi_{y}(p)\end{pmatrix}$

Thus note that

$\begin{pmatrix}1&0\\\ \phi_{x}(p)&\phi_{y}(p)\end{pmatrix}$

or

$\begin{pmatrix}0&1\\\ \phi_{x}(p)&\phi_{y}(p)\end{pmatrix}$

has rank 2 only if their determinants $\phi_{x}(p)$ or $\phi_{y}(p)$ is
nonzero . In other words, our surface is always locally a graph over $x-z$ or
$y-z$ plane if $\phi_{x}(p)$ or $\phi_{y}(p)$ is nonzero for any point p. This
is always true for a timelike minimal graphs without singularities over $x-y$
plane as they satisfies

$\phi_{x}^{2}(p)+\phi_{y}^{2}(p)>1$

at all points as the normal of X,

$N=\frac{(-\phi_{x},-\phi_{y},-1)}{\sqrt{|\phi_{x}^{2}+\phi_{y}^{2}-1|}}$

is spacelike. To show height function of local $x-z$ or $y-z$ graph is a Born-
Infeld soliton, one can compute mean curvature and equate it to zero. This
part is similar to R. Dey and R.K. Singh’s proof of height functions of
timelike minimal graphs without singularities over $y-z$ planes are Born-
Infeld solitons(in [6] pages 528 to 530) ∎

Now we will use this lemma to prove that timelike minimal surfaces without
singularities are Born-Infeld soliton general surfaces.

######  Theorem 2.2.

Any timelike minimal surface without singularities is locally a graph of a
function over the x-z or y-z plane with their height function being a Born-
Infeld soliton.

###### Proof.

Any regular timelike minimal surface is locally a graph and it is of the form
$(x,y,\psi(x,y))$, or $(x,\psi(x,z),z)$ or $(\psi(y,z),y,z)$. By lemma 2.1, we
note that the timelike $x-y$ graph without singularities is also locally a
$y-z$ or $x-z$ graph. Using zero-mean curvature condition one can conclude
that height function must be a Born-Infeld soliton. ∎

######  Remark 2.2.1.

Alternatively in [7] proposition 3.3(page 75), R. Lopez proved that any
timelike minimal surface is locally a graph over $x-z$ or $y-z$ plane by
noting that components of the normal are Jacobian of the map from $y-z$,$x-z$
and $x-y$ plane into the image of the surface.

In theorem 3.3 of [10](Page 1091), Y.W Kim, S.E Koh and S-E Yang proved that
if $c$ is a regular spacelike or timelike curve, then there is a timelike
minimal surface without singularities solving the Björling problem. This gives
us the following result.

######  Corollary 2.1.

If $c$ is a regular real analytic spacelike or timelike curve and $n$ a real
analytic spacelike normal vector field, then there exists a Born-Infeld
soliton general surface which solves the Björling problem.

Another corollary of theorem 2.1 is the following.

######  Corollary 2.2.

Let $c:I\rightarrow\mathbb{L}^{3}$ be a regular timelike curve in
$\mathbb{L}^{3}$ such that $c^{{}^{\prime\prime}}(t)$ is spacelike for all
$t\in I$. Then there exist a Born-Infeld soliton general surface containing c
as geodesic(by a geodesic here, we mean a curve such that principal normal
agreeing with surface normal in $\mathbb{L}^{3}$).

###### Proof.

Here since our curve is regular we can give it arc length parametrization
which has a constant speed. Now we refer to corollary 3.2, page 489 of [8]. We
also note that for a regular curve we get a timelike minimal surface without
singularities as solutions to the Björling problem which is also a Born-Infeld
soliton general surface. ∎

##  3 On compact subsets of timelike minimal surfaces

In this section, we get some corollaries of theorem 1.1 in [3]. We would first
prove a lemma.

######  Lemma 3.1.

Let $X:\Omega\rightarrow\mathbb{R}^{3}$ be a timelike minimal surface which is
a smooth graph over a timelike plane $P$. Choose a orthonormal basis
$\\{b_{2},b_{3}\\}$ with respect to $\langle,\rangle_{\mathbb{L}^{3}}$ for the
plane $P$, with $b_{2}$ a spacelike vector ,$b_{3}$ a timelike vector . Also,
let $b_{1}=N$ be the unit spacelike surface normal of the timelike plane
$P$.Then $\\{b_{1},b_{2},b_{3}\\}$ forms a orthonormal basis of
$\mathbb{L}^{3}$. For any $x_{2}b_{2}+x_{3}b_{3}$ in P, we can consider

$\psi(x_{2},x_{3})=\langle X,N\rangle_{\mathbb{L}^{3}}.$

Then such a $\psi$ satisfies the Born-Infeld equation in variables
$x_{2},x_{3}$ and thus is a Born-infield soliton.

###### Proof.

Since $X$ is a smooth graph over plane $P$ we know that the projection map,

$\pi:X(\Omega)\rightarrow R^{2}$

with $\pi(p)$ being the projection of the point $X(p)$ onto the plane
$P$=span$\\{b_{2},b_{3}\\}$ is a diffeomorphism. Let $\Sigma\subset P$ be the
image of this map. Using

$\phi=\pi^{-1}:\Sigma\rightarrow X(\Omega)$

we get a graph $X(x_{2},x_{3})=\psi(x_{2},x_{3})N+x_{2}b_{2}+x_{3}b_{3}$ with
$\psi(x_{2},x_{3})=\langle X(x_{2},x_{3}),N\rangle_{L}$. Here
$X(x_{2},x_{3}):P\rightarrow\mathbb{R}^{3}$ is $X\circ\phi$. To show that such
a map $\psi(x_{2},x_{3})$ satisfies the Born-infield equation, one can compute
the mean curvature in this new parametrization and equate it to zero. ∎

Now we state the main result of this section.

######  Theorem 3.2.

If $(c,n)$ is a smooth real analytic strip with the properties that,

  * •

$c$, a regular curve

  * •

$c$ and $n$ have entire split-holomorphic functions as analytic extension

then any compact subset of the timelike minimal surface solving this Björling
problem is a timelike minimal graph over some timelike plane with height
function a Born-Infeld soliton.

###### Proof.

We first note that since $c$ and $n$ have analytic extensions which are entire
functions, $\Omega$ can be taken to be $\mathbb{R}^{2}$. Since $c$ is regular,
solution to Björling problem is a regular surface(we refer to theorem 3.3 of
[10]). Thus we have a smooth $X$: $\mathbb{R}^{2}$ $\rightarrow$
$\mathbb{R}^{3}$ which is a properly immersed surface, solving this Björling
problem. Now by theorem 1.1 (page 3036) of [3] any compact subset of this
surface is a timelike graph over some timelike plane. Using lemma 3.1, we
conclude that height function is a Born-Infeld soliton. ∎

In fact for any $M>0$, when restricted to a diamond
$D_{M}$=$\\{(u,v)||u|+|v|\leq M\\}$ We would still get a timelike graph over
some timelike plane. This was used in the proof of theorem 1.1 (page 3036) of
[3].

Now we state a special case of theorem 3.2.

######  Corollary 3.1.

If $(c,n)$ is a smooth real analytic strip with the properties that,

  * •

$c$, a regular curve

  * •

$c(t)$ and $n(t)$ have components as polynomials in $t$ with real
coefficients.

for any $M>0$, solution to the time like Björling problem when restricted to a
diamond $D_{M}$=$\\{(u,v)||u|+|v|\leq M\\}$ is a smooth graph over some
timelike plane with height function being a Born-Infeld soliton.

##  4 Björling problem for graph-like Born-Infeld solitons

We first define graphical Born-Infeld solitons.

######  Definition 4.1 (Born-Infeld soliton surface).

A surface $X$ is said to be a Born-Infeld soliton surface if it is of the form
$X(y,z)=(\psi(y,z),y,z)$ for some Born-Infeld soliton .

Let us recall the definition of positive quasidefinite matrix from [2].

######  Definition 4.2.

A matrix $J$ is said to be positive quasidefinite if

$A=\frac{J+J^{T}}{2}$

is positive definite.

We asked for what kind of real-analytic strips $(c,n)$ the Björling problem
gives a graphical solution. We characterized set of real-analytic strips
$(c,n)$ for which one gets a time-like minimal graph as solution to the
Bjorling problem. Note that in the following result, we are using split-
complex analysis instead of complex-analysis. Here $z=x+k^{{}^{\prime}}y$ with
$k^{{{}^{\prime}}^{2}}=1$. We refer to [8] for more about split-complex
analysis.

######  Theorem 4.1.

Given a real analytic curve $c(t)=(c_{1}(t),c_{2}(t),c_{3}(t))$ which is
timelike or spacelike in $L^{3}$ and a real analytic spacelike normal
$n=(n_{1}(t),n_{2}(t),n_{3}(t))$ let,

$J_{(c,n)}(t)=\begin{vmatrix}\frac{c_{2_{u}}(t)}{2}&\frac{c_{2_{v}}(t)}{2}+(n(t)\times
c^{{}^{\prime}}(t))_{2}\\\
\frac{c_{3_{u}}(t)}{2}&\frac{c_{3_{v}}(t)}{2}+(n(t)\times
c^{{}^{\prime}}(t))_{3}\end{vmatrix}$

be a real-valued function defined on $I$.

Fix a real analytic strip $(c,n)$ and let $\Omega_{(c,n)}$ be a domain where
analytic extension of both $c$ and $n$ exists.

1) $t\rightarrow J_{(c,n)}(t)$ has a zero in $I$ $\implies$ there does not
exist a solution for Björling problem of time like Born-Infeld soliton
surfaces without singularities.

2) If $\Omega_{(c,n)}$ is convex, and if

$J_{(c,n)}(z)=\begin{pmatrix}\frac{c_{2_{u}}}{2}+(Im(n(z)\times
c^{{}^{\prime}}(z))_{2}&\frac{c_{2_{v}}}{2}+(Re(n(z)\times
c^{{}^{\prime}}(z))_{2}\\\ \frac{c_{3_{u}}}{2}+(Im(n(z)\times
c^{{}^{\prime}}(z))_{3}&\frac{c_{3_{v}}}{2}+(Re(n(z)\times
c^{{}^{\prime}}(z))_{3})\end{pmatrix}$

has a non-vanishing determinant and is positive quasidefinite for all $z$ in
$\Omega_{(c,n)}$, then there is a timelike Born-Infeld soliton surface without
singularities in $\mathbb{L}^{3}$ as solution to the björling problem and it
is given by

$X(z)=Re\\{c(z)+k^{\prime}\int_{t_{0}}^{z}n(w)\times
c^{{}^{\prime}}(w)\,dw\\}$

if $c$ is timelike and,

$X(w)=Re\\{c(w)+k^{\prime}\int_{t_{0}}^{w}n(\zeta)\times
c^{{}^{\prime}}(\zeta)\,d\zeta\\}$

When $c$ is spacelike(Here $w=k^{{}^{\prime}}z$).

###### Proof.

We present the proof for the case when $c$ is timelike. When $c$ is spacelike,
the proof is similar.

The main idea of the proof is to use the implicit function theorem to
understand when does the timelike minimal surface solution to the Björling
problem becomes a graph over the y-z plane.

For Björling problem for timelike minimal surfaces,we know the solution is

$X(z)=Re\\{c(z)+k^{\prime}\int_{t_{0}}^{z}n(w)\times
c^{{}^{\prime}}(w)\,dw\\}$

(We refer to [8], page 485, theorem 3.1).

Let

$F(z)=c(z)+k^{\prime}\int_{t_{0}}^{z}n(w)\times c^{{}^{\prime}}(w)\,dw$

.

Then

$X(z)=\frac{F(z)+\overline{F(z)}}{2}$

$\frac{\partial X}{\partial z}=\frac{1}{2}\frac{\partial F}{\partial
z}=\frac{1}{2}(\frac{\partial c}{\partial z}+k^{\prime}(n(z)\times
c^{{}^{\prime}}(z))).$

We note that for split complex numbers,

$\frac{\partial X}{\partial z}=\frac{1}{2}\left({\frac{\partial X}{\partial
u}+k^{\prime}\frac{\partial X}{\partial v}}\right).$

Thus

$\frac{\partial X}{\partial u}=Re(2\frac{\partial X}{\partial
z})=\frac{1}{2}\frac{\partial c}{\partial u}+Im(n(z)\times
c^{{}^{\prime}}(z))$

$\frac{\partial X}{\partial v}=Im(2\frac{\partial X}{\partial
z})=\frac{1}{2}\frac{\partial c}{\partial v}+Re(n(z)\times
c^{{}^{\prime}}(z))$

$\begin{pmatrix}X_{u}&X_{v}\end{pmatrix}=\begin{pmatrix}\frac{c_{u}}{2}+Im(n(z)\times
c^{{}^{\prime}}(z)&\frac{c_{v}}{2}+Re(n(z)\times
c^{{}^{\prime}}(z)\end{pmatrix}.$

Which implies,

$\begin{pmatrix}x_{u}&x_{v}\\\ y_{u}&y_{v}\\\
z_{u}&z_{v}\end{pmatrix}=\begin{pmatrix}\frac{c_{1_{u}}}{2}+(Im(n(z)\times
c^{{}^{\prime}}(z))_{1}&\frac{c_{1_{v}}}{2}+(Re(n(z)\times
c^{{}^{\prime}}(z))_{1}\\\ \frac{c_{2_{u}}}{2}+(Im(n(z)\times
c^{{}^{\prime}}(z))_{2}&\frac{c_{2_{v}}}{2}+(Re(n(z)\times
c^{{}^{\prime}}(z))_{2}\\\ \frac{c_{3_{u}}}{2}+(Im(n(z)\times
c^{{}^{\prime}}(z))_{3}&\frac{c_{3_{v}}}{2}+(Re(n(z)\times
c^{{}^{\prime}}(z))_{3})\end{pmatrix}.$

Thus

$\begin{pmatrix}y_{u}&y_{v}\\\
z_{u}&z_{v}\end{pmatrix}=\begin{pmatrix}\frac{c_{2_{u}}}{2}+(Im(n(z)\times
c^{{}^{\prime}}(z))_{2}&\frac{c_{2_{v}}}{2}+(Re(n(z)\times
c^{{}^{\prime}}(z))_{2}\\\ \frac{c_{3_{u}}}{2}+(Im(n(z)\times
c^{{}^{\prime}}(z))_{3}&\frac{c_{3_{v}}}{2}+(Re(n(z)\times
c^{{}^{\prime}}(z))_{3})\end{pmatrix}.$

Let

$J_{(c,n)}(z)=\begin{vmatrix}\frac{c_{2_{u}}}{2}+(Im(n(z)\times
c^{{}^{\prime}}(z))_{2}&\frac{c_{2_{v}}}{2}+(Re(n(z)\times
c^{{}^{\prime}}(z))_{2}\\\ \frac{c_{3_{u}}}{2}+(Im(n(z)\times
c^{{}^{\prime}}(z))_{3}&\frac{c_{3_{v}}}{2}+(Re(n(z)\times
c^{{}^{\prime}}(z))_{3})\end{vmatrix}.$

Thus whenever $J_{(c,n)}(z)$ is non vanishing, by implicit function theorem
one can represent the surface as locally a graph over $y-z$ plane. The real
valued function $t\rightarrow J_{(c,n)}(t)$ mentioned in theorem

$J_{(c,n)}(t)=\begin{vmatrix}\frac{c_{2_{u}}(t)}{2}&\frac{c_{2_{v}}(t)}{2}+(n(t)\times
c^{{}^{\prime}}(t))_{2}\\\
\frac{c_{3_{u}}(t)}{2}&\frac{c_{3_{v}}(t)}{2}+(n(t)\times
c^{{}^{\prime}}(t))_{3}\end{vmatrix}$

is the restriction of this map $z\rightarrow J_{(c,n)}(z)$ to $I$. Using
continuity arguments one can conclude that $J_{(c,n)}(z)$ non-vanishing in a
some allowed domain $\Omega_{(c,n)}$ is equivalent to $J_{(c,n)}(t)$ non-
vanishing on $I$. This completes the proof of the first part of the theorem.

Now if $\psi:(u,v)\rightarrow(y(u,v),z(u,v))$ is injective as well, it would
become a diffeomorphism. In [2] theorem 6 (Page 88) D. Gale and H.Nikaido
shows that if $\Omega$ is a convex domain and if
$\psi:\Omega\rightarrow\mathbb{R}^{2}$ has a positive quasidefinite Jacobian
at all points, then $\psi$ is injective. The second condition ensures this. ∎

Now we would just state when can we get a spacelike minimal graph or a
spacelike Born-Infeld soliton surface without singularities as the solution to
the Bjorling problem. The proof is similar, except one has to use complex-
numbers and complex analysis.

######  Theorem 4.2.

Given a real analytic curve $c(t)=(c_{1}(t),c_{2}(t),c_{3}(t))$ in $L^{3}$ and
a real analytic timelike normal $n=(n_{1}(t),n_{2}(t),n_{3}(t))$ let,

$J_{(c,n)}(t)=\begin{vmatrix}\frac{c_{2_{u}}(t)}{2}&\frac{c_{2_{v}}(t)}{2}-(n(t)\times
c^{{}^{\prime}}(t))_{2}\\\
\frac{c_{3_{u}}(t)}{2}&\frac{c_{3_{v}}(t)}{2}-(n(t)\times
c^{{}^{\prime}}(t))_{3}\end{vmatrix}$

be a real-valued function defined on $I$.

Fix a real analytic strip $(c,n)$ and let $\Omega_{(c,n)}$ be a domain where
analytic extension of both $c$ and $n$ exists.

1) $t\rightarrow J_{(c,n)}(t)$ has a zero in $I$ $\implies$ there does not
exist a solution for Björling problem of space like Born-Infeld soliton
surfaces without singularities.

2) If $\Omega_{(c,n)}$ is convex, and if

$J_{(c,n)}(z)=\begin{pmatrix}\frac{c_{2_{u}}}{2}+(Im(n(z)\times
c^{{}^{\prime}}(z))_{2}&\frac{c_{2_{v}}}{2}-(Re(n(z)\times
c^{{}^{\prime}}(z))_{2}\\\ \frac{c_{3_{u}}}{2}+(Im(n(z)\times
c^{{}^{\prime}}(z))_{3}&\frac{c_{3_{v}}}{2}-(Re(n(z)\times
c^{{}^{\prime}}(z))_{3})\end{pmatrix}$

has a non-vanishing determinant and is positive quasidefinite for all $z$ in
$\Omega_{(c,n)}$ then there is a spacelike Born-Infeld general surface,
without singularities in $\mathbb{L}^{3}$ as solution to the Björling problem
and it is given by

$X(z)=Re\\{c(z)+i\int_{t_{0}}^{z}n(w)\times c^{{}^{\prime}}(w)\,dw\\}$

######  Remark 4.2.1.

A. Das in [1] show that the above positive-quasidefinite condition can be
replaced with J(c,n)(t) being a P-matrix.

##  5 On solutions given by Barbishov and Chernikov

We refer to pages 617 to 619 of [4] for the representation formula of Born-
Infeld soliton surfaces given by Barbishov and Chernikov. We show that it
holds at any non-zero Gauss curvature point.

######  Theorem 5.1.

For any timelike Born infeld soliton surface $(\psi(y,z),y,z)$ without
singularities, for any non-zero Gauss curvature point there is an open
neighbourhood with two $C^{2}$ functions $F$ and $G$ such that the surface can
be represented there as,

$y-z=F(r)-\int s^{2}G^{{}^{\prime}}(s)ds$ $y+z=G(s)-\int
r^{2}F^{{}^{\prime}}(r)dr$ $\psi(y,z)=\int rF^{{}^{\prime}}(r)dr+\int
sG^{{}^{\prime}}(s)ds.$

Conversely, any graph-like surface $(\psi(y,z),y,z)$ represented this way is a
Born-Infeld soliton surface.

###### Proof.

We refer to [4], pages 617-619(Section 17.15) for the proof of the above
representation formulae. Note the proof starts with the assumption

$\psi_{y}^{2}-\psi_{z}^{2}+1>0.$

This implies the surface is timelike. Also Note that in the proof to go from
step 17.89 to 17.90, there was an interchange of the roles of dependent and
independent variables. For this, we want the map

$\psi:(\xi,\eta)\rightarrow(u,v)$

to be a diffeomorphism. So we need the Jacobian of this map $\psi$ to be
nonzero. This implies, at such points $p$

$(\psi_{yy}\psi_{zz}-\psi_{yz}^{2})(p)\neq 0$

.

The above condition is equivalent to $\psi$ being a local-diffeomorphism. Note
that Gauss curvature of $(\psi(y,z),y,z)$ is given by,

$K(p)=\frac{\psi_{yy}\psi_{zz}-\psi_{yz}^{2}}{(\psi_{y}^{2}-\psi_{z}^{2}+1)^{2}}.$

Thus if there are no singularities,

$(\psi_{yy}\psi_{zz}-\psi_{yz}^{2})(p)\neq 0$

is equivalent to saying that Gauss curvature $K(p)$ is nonzero. ∎

Now we state a result about their surface normal.

######  Theorem 5.2.

The surface normal $N(r,s)$ (in $\mathbb{L}^{3}$) of all Born-Infeld soliton
surfaces described by the representation formula of Barbishov and Chernikov
are the same.

###### Proof.

The proof follows by computation.

$X_{r}=\left(rF^{{}^{\prime}}(r),\hskip
7.11317pt\frac{F^{{}^{\prime}}(r)(1-r^{2})}{2},\hskip
7.11317pt\frac{-F^{{}^{\prime}}(r)(1+r^{2})}{2}\right).$
$X_{s}=\left(sG^{{}^{\prime}}(s),\hskip
7.11317pt\frac{G^{{}^{\prime}}(s)(1-s^{2})}{2},\hskip
7.11317pt\frac{G^{{}^{\prime}}(s)(1+s^{2})}{2}\right).$

$N(r,s)=\frac{X_{r}\times X_{s}}{|X_{r}\times
X_{s}|}=\left(\frac{r+s}{1+rs},\hskip 7.11317pt\frac{r-s}{1+rs},\hskip
7.11317pt\frac{rs-1}{1+rs}\right).$

Thus $N(r,s)$ is independent of F and G. ∎

Now we give a geometric interpretation of the above formula.

######  Theorem 5.3.

Graphical surfaces $(\psi(y,z),y,z)$ with $\psi(y,z)$,$y$,$z$ as described by
the representation formula of Barbishov and Chernikov can be written as,

$X(r,s)=\frac{\psi(r)+\phi(s)}{2}$

with

$\psi(r)=\left(2\int rF^{{}^{\prime}}(r)dr,\hskip 7.11317ptF(r)-\int
r^{2}F^{{}^{\prime}}(r)dr,\hskip 7.11317pt-F(r)-\int
r^{2}F^{{}^{\prime}}(r)dr\right),$

$\phi(s)=\left(2\int sG^{{}^{\prime}}(s)ds,\hskip 7.11317ptG(s)-\int
s^{2}G^{{}^{\prime}}(s)ds,\hskip 7.11317ptG(s)+\int
s^{2}G^{{}^{\prime}}(s)ds\right),$

such that $\psi,\phi$ lightlike curves in $\mathbb{L}^{3}$ with
$\psi^{{}^{\prime}}(r)$ and $\phi^{{}^{\prime}}(s)$ are linearly independent
for all values of r and s. This implies these surfaces are timelike minimal.

###### Proof.

It follows from computation that

$X(r,s)=\frac{\psi(r)+\phi(s)}{2}$

and $\psi,\phi$ are lightlike curves. To show $\psi^{{}^{\prime}}(r)$ and
$\phi^{{}^{\prime}}(s)$ are linearly independent for all values of r and s,
note that $\psi^{{}^{\prime}}(r)=2X_{r}$ and $\phi^{{}^{\prime}}(s)=2X_{s}$ .

$X_{r}=\left(rF^{{}^{\prime}}(r),\hskip
7.11317pt\frac{F^{{}^{\prime}}(r)(1-r^{2})}{2},\hskip
7.11317pt\frac{-F^{{}^{\prime}}(r)(1+r^{2})}{2}\right).$
$X_{s}=\left(sG^{{}^{\prime}}(s),\hskip
7.11317pt\frac{G^{{}^{\prime}}(s)(1-s^{2})}{2},\hskip
7.11317pt\frac{G^{{}^{\prime}}(s)(1+s^{2})}{2}\right).$

Since $X(r,s)$ is a given to be the graph of a function, which is a regular
surface, $X_{r}$ and $X_{s}$ are linearly independent for all values of $r$
and $s$.

Fact 2.2 in [9](Page 541) confirms these surfaces are timelike minimal. ∎

## Acknowledgement

I would like to thank my MS thesis supervisor Prof. Rukmini Dey(ICTS
Bangalore) and my friend Arka Das(IISC Bangalore) for all the interesting
conversations we had during the project. I also thank Rukmini Dey for
suggesting the problem to me. I want to express my gratitude to ICTS Bangalore
for their hospitality. This work was done as a part of my master’s thesis
project in IISER Pune.

## References

  * [1] A. Das _Born-Infeld solitons & existence & non-uniqueness of solutions to the Björling problem_, arXiv:2211.03275 , (2022).
  * [2] D. Gale and H.Nikaido, _The Jacobian Matrix and global univalence of mappings_ , Math. Ann. 159, 81-93 (1965).
  * [3] E.A. Paxton, _Embeddedness of timelike maximal surfaces in (1+2) Minkowski space_ , Ann. Henri Poincare, 3035-306, (2020).
  * [4] G.B Whitam, _Linear and nonlinear waves_ , JW/A, 617-619 (1999).
  * [5] L. McNertney, _One-parameter families of surfaces with constant curvature in Lorentz 3-space_ Ph.D. thesis, Brown University (1980).
  * [6] R. Dey and R.K Singh, _Born–Infeld solitons, maximal surfaces, and Ramanujan’s identities_ , Arch math. 108, 527–538 (2017).
  * [7] R. López, _Differential Geometry of Curves and Surfaces in Lorentz-Minkowski space_ , Int. Electron. J. Geom., 44-107, (2014).
  * [8] R.M.B Chaves, M.P. Dussan and M. Magid, _Bjorling problem for timelike surfaces in the Lorentz-Minkowski space_ , J. Math. Anal. Appl. 377, 481-494 (2011).
  * [9] S. Akamine, _Behavior of the Gaussian curvature of timelike minimal surfaces with singularities_ , Hokkaido Math. J, 537-568, (2017).
  * [10] Y.W. Kim, S-E. Koh, H. Shin, and S-D. Yang _Spacelike maximal surfaces, timelike minimal surfaces, and Bjorling representation formulae_ , J. Korean Math. Soc, 1083-1100, (2011).


# PERIDOT Codes: Replacing Identifiers, Sequence Numbers and Nonces with
Permutations

Florian Euchner and Christian Senger  Institute of Telecommunications,
University of Stuttgart, Stuttgart, Germany
Email: {euchner<EMAIL_ADDRESS>
###### Abstract

Identifiers and sequence numbers make up a large part of the protocol overhead
in certain low-power wide-area networks. The requirement for cryptographic
nonces in authentication and encryption schemes often demands excessively long
sequence numbers, which leads to an increase in energy consumption per
transmitted packet. In this paper, the novel PERIDOT coding scheme is
proposed. It replaces identifiers and sequence numbers with a code, based on
which receivers can identify transmitters with high confidence. PERIDOT is
based on specially constructed integer permutations assigned to transmitters.
An upper bound on the performance of PERIDOT codes is provided and methods for
constructing particularly suitable permutations are presented. In practice,
PERIDOT can significantly increase intervals between nonce reuses and, at the
same time, reduce power consumption.

###### Index Terms:

LPWAN, sequence number, permutation, nonce, identification

##  I Introduction

Low-power wide-area network (LPWAN) protocols like LoRaWAN, Sigfox, MIOTY and
others are commonly used to wirelessly transmit packets with very small
application payloads, sometimes as small as a single bit. Devices connected to
such networks are often uplink-only and their transmissions are powered by
small batteries or by energy harvesting.

Nevertheless, since LPWAN devices may transmit sensitive information, the
various protocols define authentication schemes based on message
authentication codes (MACs) and symmetric encryption schemes. These
authentication and encryption methods need nonces, i.e. a number has to be
transmitted alongside the application payload and this number should be reused
as rarely as possible, preferably only once. In practice, the sequence number
(SN) of packets, a counter that is traditionally used to detect packet loss,
gets a dual-use as nonce. Protocol designers have to find a trade-off between
longer SNs (improved security due to longer intervals between nonce reuses)
and low energy consumption: The transmission of every single bit consumes
energy and the device’s overall energy consumption is almost proportional to
the number of bits transmitted, since most other tasks (e.g. reading sensor
values) are negligible in their energy consumption.

For instance, in the case of Sigfox, an uplink packet with a single-bit
application payload has a total length of 112 bit including the preamble, 12
bit of which are used as SN and nonce [1]. This obviously makes replay attacks
feasible since SNs have to be reused every $2^{12}=4096$ packets. LoRaWAN, on
the other hand, employs a 32 bit SN internally, only the 16 least significant
bits of which are transmitted - the receiver has to infer the remaining bits
from observed uplinks [2]. This scheme is stateful and potentially error-
prone.

In our protocol design approach, we replace SNs altogether and merge them with
identifiers into a single number, called code number (CN). The same CN is
guaranteed to recur as rarely as possible, hence it can have a dual-use as
nonce. The gist of the scheme, which we will call Permutation-based
Identification and Order Tracking (PERIDOT), is best explained by two examples
based on the following scenario:

TransmitterCNDataMACPacket Erasure
ChannelErasureReceiver$1-\varepsilon$$\varepsilon$ Figure 1: Channel model: a
single Packet Erasure Channel

We assume that, as shown in Fig. 1, a packet is transmitted over a packet
erasure channel (PEC) with erasure probability $\varepsilon$. In our model,
the receiver is unaware of the occurrence of an erasure. Let the CN be from
the alphabet $Z_{\mathrm{q}}=\\{0,\ldots,q-1\\}$. Our hard requirement is
that, since CNs are used as nonces, once a particular CN has been transmitted,
the following $q-1$ packets must not contain the same CN again. Thus, the
order in which CNs are transmitted has to be a cyclic permutation of the
elements of $Z_{\mathrm{q}}$. That is, the permutation has only a single cycle
whose orbit is $Z_{\mathrm{q}}$. This permutation $\sigma:Z_{\mathrm{q}}\to
Z_{\mathrm{q}}$ maps the previously transmitted CN $u$ to the next CN
$v=\sigma[u]$. We use $\circ$ to denote composition of permutations and
$\sigma^{\beta}$ for $\beta$-fold composition. In both examples, it is assumed
that there is _only a single transmitter_ communicating with a single
receiver.

(a) Permutations in a $(7,3)$-proper set

(b) Permutations in a $(7,1)$-proper set

(c) Permutations in an $(8,2)$-proper set

Figure 2: Illustrations of different permutations (order in which CNs are
sent), one color per permutation

######  Example 1.

For some $q\geq 3$, define an incrementing and a decrementing permutation as

$\sigma_{\mathrm{inc}}:u\mapsto(u+1)\bmod
q\qquad\sigma_{\mathrm{dec}}:u\mapsto(u-1)\bmod q$

and assign the permutations to one of two transmitters each. The permutations
are illustrated in Fig. 2(a) for $q=7$. One of the two transmitters is
selected to send a packet containing an arbitrary CN $u\in Z_{\mathrm{q}}$ and
then a packet with CN $v=\sigma[u]$, where $\sigma$ is its assigned
permutation. The receiver receives the packets in that order. For erasure
probability $\varepsilon=0$, the receiver is always able to identify the
device based on $u$ and $v$ (e.g. $u=5$ and $v=6$ can only stem from
permutation $\sigma_{\mathrm{inc}}$). Even for nonzero $\varepsilon$, the
receiver can still try to identify the transmitter using two non-erased
packets based on which permutation, $\sigma_{\mathrm{inc}}$ or
$\sigma_{\mathrm{dec}}$, the CNs contained in the packets were more likely
drawn from.

######  Example 2.

Suppose $\varepsilon=0$, i.e. there are no erasures. If $q$ is prime and there
are $q-1$ transmitters or less, we can uniquely assign a number $\Delta\in
Z_{\mathrm{q}}\backslash\\{0\\}$, called increment, to each of them, so that
by knowing $\Delta$, the transmitter is identified. The transmitters are
configured to send nonces according to the permutation
$\omega_{\Delta}:u\mapsto(u+\Delta)\bmod q$. Then the receiver can determine a
transmitter’s identity based on two consecutively received nonces $u$ and $v$:
$\Delta=(v-u)\bmod q$. This can also be seen from the illustration for $q=7$
in Fig. 2(b).

For non-prime $q$, $\omega_{\Delta}:u\mapsto(u+\Delta)\bmod q$ is no longer a
permutation of $Z_{\mathrm{q}}$ in case $\gcd(\Delta,q)\neq 1$. For most $q$,
solutions with $q-1$ permutations can nevertheless be found: Formalizing the
requirements, we want to find a set of permutations $P$ such that

$\forall(u,v)\in Z_{\mathrm{q}}^{2}~{}\exists_{\leq 1}\sigma\in
P:~{}v=\sigma[u].$

In other words, the transition from $u$ to $v$ must be unique among all
transmitters. Regarding $Z_{\mathrm{q}}$ as the vertex set of a directed
graph, an equivalent problem is to find a set of edge-disjoint directed
Hamiltonian cycles in the complete directed graph $K^{*}_{q}$, where the
permutations $\sigma\in P$ are given by the order in which cycles visit nodes.
From Walecki’s construction [3] and from Tillson’s paper [4], we find
solutions with $q-1$ directed Hamiltonian cycles and thus permutations for all
$q\in Z_{\mathrm{q}}\backslash\\{1,2,4,6\\}$. The cases $q\in\\{1,2\\}$ are
trivial and, by full search, we find that it is not possible to find $q-1$
directed Hamiltonian cycles for $q\in\\{4,6\\}$.

Other than in Ex. 1, any packet loss between the reception of $u$ and $v$
results in misidentification.

These examples show that CNs may carry both identifying information and
information facilitating the detection of lost packets. In Ex. 1, the receiver
can only discern two devices, but is guaranteed to tolerate up to
$\lfloor(q-1)/2\rfloor-1$ consecutively lost packets whereas in Ex. 2, packet
loss is not tolerable, but the receiver can identify up to $q-1$ devices.
These examples are two extreme ends in a spectrum of conceivable schemes that
permit distinguishing transmitters based on CN permutations assigned to them.
In the following Sec. II, we will formalize this notion, define a necessary
and sufficient criterion for such schemes and provide an upper bound. In Sec.
III, we will provide a particularly suitable construction of sets of
permutations and in Sec. IV and Sec. V we will explore how PERIDOT can be
practically implemented for systems with many transmitters.

##  II $(q,l)$-Proper Sets and Upper Bound

We assume that the receiver detects two packets from the transmitter with CNs
$u,v\in Z_{\mathrm{q}}$ in that order. We count the number of packets that
were transmitted after $u$, including the one containing $v$, and call this
number $\beta$. The number of packets lost between $u$ and $v$ is thus
$\beta-1$ and we always have $\beta\geq 1$. Moreover, we assume that at most
$l-1$ packets are lost over the PEC, such that $\beta$ can be bounded by
$\beta\leq l$.

######  Definition 1 ($(q,l)$-proper sets).

A set $P$ of cyclic permutations with orbit $Z_{\mathrm{q}}$ is called a
$(q,l)$-proper set for $l\in\mathbb{N}_{0},l<q$ if, and only if, we have

$\forall(u,v)\in Z_{\mathrm{q}}^{2}~{}\forall\beta\in\mathbb{N},\beta\leq
l~{}\exists_{\leq 1}\sigma\in P:~{}v=\sigma^{\beta}[u].$

Intuitively, Def. 1 states that a $(q,l)$-proper set $P$ is a set in which we
can _uniquely_ identify each permutation $\sigma\in P$ based on an ordered
pair $(u,v)$, where this ordered pair is generated by arbitrarily choosing
$u\in Z_{\mathrm{q}}$ and then computing $v$ as $v=\sigma^{\beta}[u]$ with
some $\beta\leq l$. This corresponds to a device successfully transmitting the
CN $u$, then loosing $\beta-1\leq l-1$ messages (with CNs $\sigma[u]$,
$\sigma^{2}[u]$, …, $\sigma^{\beta-1}[u]$) and then successfully transmitting
$v=\sigma^{\beta}[u]$. The receiver can identify the permutation $\sigma$ and
thus the transmitter based on $(u,v)$.

We see that the permutations in a $(q,l)$-proper set are suitable sequences of
CNs. In this notation, Ex. 1 provides a construction for a
$(q,\lfloor(q-1)/2\rfloor)$-proper set whereas Ex. 2 describes $(q,1)$-proper
sets. The following is a nontrivial example for a $(q,l)$-proper set (for an
unrealistically small alphabet size of $q=8$):

Figure 3: Transitions from $u=4$ to $v=7$ in a $(8,2)$-proper set

######  Example 3.

A $(8,2)$-proper set is given by
$P=\\{\sigma,{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\rho},{\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}\pi}\\}$
with

$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\sigma}$
$\displaystyle=(0,1,2,3,4,5,6,7)\qquad{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}\rho}=(0,3,7,6,2,5,1,4)$
$\displaystyle{\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}\pi}$
$\displaystyle=(0,6,4,1,7,5,3,2)$

$\sigma$, $\rho$ and $\pi$ are given in cycle notation. There is no
$(8,2)$-proper set containing more than $|P|=3$ permutations. $P$ was found by
computer search and is illustrated in Fig. 2(c). For this exemplary set of
permutations, if the receiver observes $u=4$ and $v=7$ in that order, it would
generate the transition paths that $\sigma$, $\rho$ and $\pi$ would have to
take to get from $u$ to $v$ as drawn in Fig. 3. From the fact that the path
for permutation $\pi$ is shortest, it concludes that the most likely scenario
is that the device to which $\pi$ was assigned transmitted $u$ and $v$, and
that one packet was lost in between (the one with a CN of $1$).

The previous examples suggest that for fixed $l$ and $q$, there appears to be
a maximum number of permutations that fit into a $(q,l)$-proper set, i.e. a
maximum value for $m=|P|$. This has important practical ramifications: For a
an alphabet size $q$, which is predetermined by the number of bits allocated
to a CN, and $l-1$ tolerable packet losses, we can only assign $m$
permutations to transmitters and thus only identify up to $m$ devices using
PERIDOT. Therefore, we now seek to formulate an upper bound that relates $m$,
$l$ and $q$. Such a bound will result as a consequence of an equivalent
condition for $(q,l)$-proper sets based on what we call $l$-follower sets:

######  Definition 2 ($l$-follower sets).

The $l$-follower set of some $u\in Z_{\mathrm{q}}$ in the permutation $\sigma$
of $Z_{\mathrm{q}}$ is given by

$\Omega_{l}^{\sigma}(u)=\left\\{\sigma^{\beta}[u]~{}|~{}1\leq\beta\leq
l\right\\}.$

$7$$6$$9$$4$$5$$2$follower set $\Omega_{3}^{\sigma}(6)$ Figure 4: $3$-follower
set of $6$ in some permutation

Figuratively, $\Omega_{l}^{\sigma}(u)$ contains all the CNs that succeed $u$
in the next $l$ messages, as illustrated in Fig. 4. It is clear that, if we
have a set of alphabet permutations $P$ and all $l$ CNs that succeed $u$ are
distinct from any permutation to another, then we can identify each
permutation $\sigma\in P$ based on $(u,v)$ where $v$ is in the $l$-follower
set of $u$ in the permutation $\sigma$.

Therefore, using the definitions of $(q,l)$-proper sets and follower sets, we
can equivalently say that $P$ is a $(q,l)$-proper set with $l<q$ if, and only
if, $\forall u\in Z_{\mathrm{q}}$ we have

$\forall\sigma,\pi\in
P,~{}\sigma\neq\pi:~{}\Omega_{l}^{\sigma}(u)\cap\Omega_{l}^{\pi}(u)=\emptyset.$
(1)

We can now derive an upper bound on $m=|P|$ from Eq. 1. Since the sets
$\Omega_{l}^{\sigma}$ are disjoint for different $\sigma\in P$ and because
$|\Omega_{l}^{\sigma}(u)|=l$, we have

$\left|\bigcup_{\sigma\in P}\Omega_{l}^{\sigma}(u)\right|=\sum_{\sigma\in
P}|\Omega_{l}^{\sigma}(u)|=|P|l\leq|Z_{\mathrm{q}}\backslash\\{u\\}|=q-1.$ (2)

With $m=|P|$, this means

$lm+1\leq q.$

Adding the restriction that $m$ must be integer and solving for $m$ finally
yields the following upper bound:

######  Theorem 1.

For any $(q,l)$-proper set $P$ holds:

$m=|P|\leq\left\lfloor\frac{q-1}{l}\right\rfloor$

A similar upper bound (but for a more restrictive problem and an entirely
different application) has previously been derived in [5, eq. 1]. On the basis
of Thm. 1, we are now able to assess how “good” a $(q,l)$-proper set
construction is: We will call a $(q,l)$-proper set _quasiperfect_ if it
reaches the upper bound, and _perfect_ if, additionally, $(q-1)/l$ is integer.
We will see in the following that the bound in Thm. 1 is tight.

##  III A Quasiperfect Construction

For some specific values of $q$, $l$ that are also suitable for practical
implementations of PERIDOT, it is possible to construct a quasiperfect
$(q,l)$-proper set. This construction is based on transmitters sending CNs in
an order that is determined by an arithmetic progression modulo $q$, that is,
a sequence of the form

$0,~{}\Delta\bmod q,~{}2\Delta\bmod q,~{}\ldots~{}.$ (3)

As in Ex. 2, the mapping from previous to next CN is given by the permutation
$\omega_{\Delta}$ with _increment_ $\Delta\in Z_{\mathrm{q}}\backslash\\{0\\}$
and

$\omega_{\Delta}:u\mapsto(u+\Delta)\bmod q.$ (4)

For $\omega_{\Delta}$ to be cyclic with orbit $Z_{q}$, we need to have
$\gcd(\Delta,q)=1$. Note that modular arithmetic progressions have the added
benefit of being easy to store (only need to store $q$, $\Delta$ at
transmitter), which makes the implementation of PERIDOT on low-powered LPWAN
end nodes feasible.

######  Theorem 2.

For prime $p$, $l\,|\,(p-1)$ and $\omega_{\Delta}$ as in Eq. 4,

$P=\\{\omega_{1+il}~{}|~{}i=0,\ldots,p-1,~{}i\neq(p-1)/l\\}$

is a quasiperfect $(pl,l)$-proper set with $m=|P|=p-1$.

###### Proof.

We have to prove that

  1. (i)

$P$ is a $(q,l)$-proper set with $q=pl$ (requiring the elements of $P$ to be
cycles with orbit $Z_{q}$) and that

  2. (ii)

$P$ is quasiperfect.

Since we have $\gcd(1+il,q)=1$ for $i=0,\ldots,p-1,~{}i\neq(p-1)/l$, the
elements of $P$ are indeed cyclic permutations with orbit $Z_{q}$. The simple,
but technical proof for this is omitted and we will instead focus on proving
that $P$ is $(l,q)$-proper, which we will prove by contradiction and using
Def. 1.

Assume to the contrary that $P$ is not a $(q,l)$-proper set. Then, there are
some $i_{1},i_{2}\in\\{0,\ldots,p-1\\}\backslash\\{(p-1)/l\\},~{}i_{1}\neq
i_{2}$ such that for some $\beta_{1},\beta_{2}\in\\{1,\ldots,l\\}$, we have

$\omega^{\beta_{1}}_{1+i_{1}l}[u]=\omega^{\beta_{2}}_{1+i_{2}l}[u].$

By the definition of $\omega_{\Delta}$, we obtain Eq. 5, which can be
simplified to Eq. 6:

$\displaystyle u+(1+i_{1}l)\beta_{1}$ $\displaystyle\equiv
u+(1+i_{2}l)\beta_{2}\pmod{q}$ (5)
$\displaystyle\iff\qquad(1+i_{1}l)\,\beta_{1}$
$\displaystyle\equiv(1+i_{2}l)\,\beta_{2}\pmod{q}.$ (6)

Now since $q=pl$, the equivalence in Eq. 6 must also hold modulo $l$, from
which we can conclude that $\beta_{1}\equiv\beta_{2}\pmod{l}$. By the premise,
we have $1\leq\beta_{1},\beta_{2}\leq l$, so $\beta_{1}=\beta_{2}$.
Simplifying Eq. 6 with $\beta_{1}=\beta_{2}$, we get

$i_{1}\equiv i_{2}\pmod{q}$

and, because $i_{1},i_{2}<p\leq q$, we conclude $i_{1}=i_{2}$. This is a
contradiction.

$P$ is quasiperfect, since $m=|P|=p-1$ and $q=pl$, so the upper bound from
Thm. 1 becomes

$p-1\leq\left\lfloor\frac{pl-1}{l}\right\rfloor=\left\lfloor
p-\frac{1}{l}\right\rfloor,$

which is fulfilled with equality, implying quasiperfectness (but not
perfectness in general). ∎

A construction similar to, but more restrictive than Thm. 2 has been
previously described in [5, Theorem 1], but, again, for a different
application. $(q,l)$-proper sets can also be constructed by adapting
techniques applied for the construction of flash memory codes as presented in
[5], [6] and [7].

##  IV Application in Multi-Transmitter Systems

Using the previously described PERIDOT code construction, we can now address
the practical implementation of the scheme for use with LPWANs. In our LPWAN
model, we assume that end devices spontaneously emit uplink-only packets that
one or multiple nearby base stations can pick up. As shown in Fig. 5, the
channels between any device and the base station are modelled as independent
unidirectional packet erasure channels. Furthermore, we assume that all
packets originating from all devices globally are being processed by a central
service, hereafter called _backend_. The assumption of the backend being
centralized is not necessary, but will greatly simplify the subsequent
explanations. The backend has a database of devices, containing the previously
received CNs $u$ for each device as well as each packet’s timestamp and a very
approximate device location. We assume that if the base station picks up a
packet containing the CN $v$,

moved intocoverage areanewlycommissionedPECPECPECPEC Figure 5: Model of LPWAN
base station’s coverage area

  1. (A)

it is very likely that it or a nearby base station has also picked up at least
one of the previous $l$ packets from the same device, which has already been
identified

  2. (B)

or, otherwise, $l$ or more packets were erased by the channel, the device is
newly commissioned or the device is mobile and has moved rapidly.

In all cases, the goal is to identify the transmitter, i.e. find out which
permutation $\sigma$ the CN $v$ was drawn from. The backend can handle all
cases using a probability-based algorithm that is illustrated in Fig. 6 and
which is only briefly outlined and underpinned by some examples in the scope
of this paper. It treats the vast majority of packets that are easy to
identify (case A) in a special way so that the few packets that cannot be
identified so easily (case B) can undergo computationally more complex
treatment.

In an initial processing step for each received packet, the backend iterates
over its database of known, identified devices and, for each device (hereafter
called _candidate_) computes a probability estimate that it was this
particular device that transmitted $v$. In many cases, candidates can be
assigned a zero probability, e.g. in case a device was recently seen in a
completely different geographic region. For the candidates that remain, the
backend computes the number of packet losses that must have occurred to make
the observation of $v$ plausible, given that the last observed packet by the
candidate contained the CN $u$ (from backend’s database). The number of
packets transmitted after $u$, including $v$, is denoted by $\beta$ with
$1\leq\beta$ and we assume $\beta\leq q$. Since the candidate device’s
assigned permutation $\sigma$ is known, this number has to fulfill
$v=\sigma^{\beta}[u]$. For a modular arithmetic progression-based
$(q,l)$-proper set construction where $\sigma=\omega_{\Delta}$ for some
$\Delta$, this simplifies to

$\beta\equiv\Delta^{-1}(v-u)\pmod{q}.$ (7)

Now, using the PEC model assumption with erasure probability $\varepsilon$,
the probability for $\beta$ packet losses is given by

$P_{\beta}=(1-\varepsilon)~{}\varepsilon^{\beta-1}.$

Intuitively, this means that if $v$ appears soon after $u$ in the permutation
$\sigma$, it is reasonable to assume that $u$ and $v$ were transmitted by the
same device. The accuracy of probability estimates may be further augmented
based on methods such as behavioral analyses and signal strength measurements.

Search for matchingidentified devicesOne probablecandidate only?MAC is
valid?Device identified!Treat as Hidden Markov ModelYesYesNoNo Figure 6:
Overview of backend identification algorithm

For the packets that belong to case A, which we expect to be the vast majority
of packets, these criteria will likely let a single device emerge as the only
probable transmitter. For this device, the MAC value is checked (i.e., the MAC
gets a dual-use as both authenticity check and final identity check) and if it
also matches, the packet can be attributed to the transmitter.

All other cases, that is case B (no device matches the packet with high enough
probability) or case A, but multiple devices match, are treated in the same
way: the packet has to be processed by a more sophisticated algorithm that
treats the entirety of all yet unidentified devices as a Hidden Markov Model
(HMM). It is for this that we constructed $(q,l)$-proper sets and assigned
special permutations to devices - thanks to them, the backend will still be
able to identify devices, almost always upon reception of the _second_ packet
by the same device.

A HMM consists of a Markov chain, i.e. a set of states the system can be in,
as well as a set of possible observable values. In our case, the states of the
Markov chain are given by the combined state of the _entirety_ of all the
unidentified LPWAN end devices. This state consists of _all_ the previously
successfully transmitted CNs of _all_ unidentified devices, which is an
integer from the alphabet $Z_{\mathrm{q}}$ for each device. Overall, the state
can thus be described by the vector $\underline{u}\in Z_{\mathrm{q}}^{d}$ for
$d$ unidentified devices in the whole network, so there are a total of $q^{d}$
possible states. In our case, an observation in the HMM is made whenever a
packet is received which could not be unambiguously assigned to a device in
the previous steps.

In this context, the goal of identifying the transmitter of each packet can be
reformulated as guessing the most likely sequence of hidden states from the
observations, since this sequence also automatically reveals which transitions
must have occurred in order to produce it. Trivially, if two state vectors
differ in more than one CN, the transition probability between them is zero
since packet transmissions can be assumed to occur one at a time. Other
transition probabilities between hidden states can be computed as previously
explained (compute $P_{\beta}$, possibly augment with metadata).

The _Viterbi algorithm_ can be employed to find the most likely sequence of
hidden states efficiently. Due to the large number of states in the Markov
chain ($q^{d}$), a practical implementation has to stop tracking unlikely
paths if their probability drops below some threshold. The way the algorithm
works is best explained by example. In order to simplify explanations, we will
use unrealistically small values for $q$.

In Ex. 4 and Ex. 5, we assume a construction as in Thm. 2 with $l=10$ and
$p=11$, so the set of increments is
$\left\\{1,21,31,41,51,61,71,81,91,101\right\\}$ and $q=110$. Furthermore, we
assume that identification is performed only based on CNs and an approximate
(within tens to hundreds of kilometers accuracy) device geolocation.

######  Example 4.

The backend has already identified and located the asset tracker device T with
increment $\Delta_{\mathrm{T}}=31$ in Rotterdam. The last CN known to have
originated from T is $u=12$. Several hours later, a base station in Amsterdam,
$60\,\mathrm{km}$ away, receives a packet with a CN $v=43$, which is a
plausible next CN for T. There are no other identified devices in all of
Europe for which $v=43$ is plausible, so we check the packet’s MAC which is
also valid. It can be assumed that the device has been successfully
identified.

The only reasonable scenario for erroneous identification is, if some other
previously inactive device that was just commissioned happens to have $v=43$
as first CN to transmit, happens to be in the same geographic area as T, and
the MAC happens to be valid, which is extremely unlikely overall.

With large enough values of $p$, $l$ and thereby $q$, we expect the error
scenario in Ex. 4 to hardly ever occur.

######  Example 5.

The backend has not yet identified the devices with increments $1$, $21$ and
$91$. A base station in Singapore receives a packet with CN $77$, which is
implausible for any of the already identified devices in the area (case B
applies). At this point, the packet cannot yet be processed further, because
the transmitter cannot be identified solely based on this one packet. Thirty
minutes later, the same base station receives a packet with CN $9$. The only
plausible increment for the sequence $77\to 9$ is $21$ with $\beta-1=1$
erasure, since, by Eq. 7, we have $\beta\equiv 21^{-1}~{}(9-77)\equiv
2\pmod{q}$. Since the MAC validity checks for both packets succeed, the
backend can now process and deliver the current and previous packet.

An increment of $1$ would have required $41$ erasures ($\beta=42$) and an
increment of $91$ would have required $101$ erasures to go from $77$ to $9$.
Both of these scenarios are extremely unlikely.

In the following example we will use the two trivial incrementing /
decrementing permutations $\sigma_{\mathrm{inc}}$ and $\sigma_{\mathrm{dec}}$
given in Ex. 1 for an (unrealistically small) alphabet size $q=20$.

393757355333Last CN attributedto $\sigma_{\mathrm{inc}}$Last CN attributedto
$\sigma_{\mathrm{dec}}$$\varepsilon(1-\varepsilon)$$\varepsilon(1-\varepsilon)$$\varepsilon(1-\varepsilon)$$\varepsilon^{3}(1-\varepsilon)$$\varepsilon(1-\varepsilon)$“7”“5”“3”
Figure 7: System states $\underline{u}$ with transition probabilities given
observations (blue)

######  Example 6.

The backend receives the following sequence of CNs: $1\to 2\to 10\to 9\to 3\to
7\to 5\to 3\to 4$. It is likely that $1$, $2$ and $3$ originate from
$\sigma_{\mathrm{inc}}$ and $10,9,7$ from $\sigma_{\mathrm{dec}}$. Upon
reception of CN $v_{1}=5$, both $\sigma_{\mathrm{inc}}$ and
$\sigma_{\mathrm{dec}}$ are equally likely sources of $v_{1}$, so the packet
cannot yet be delivered and has to be processed by the HMM for identification.
There are now two equally likely current system states:
$\underline{u}_{\mathrm{1a}}=(5,7)$ and $\underline{u}_{\mathrm{1b}}=(3,5)$,
where the CN attributed to $\sigma_{\mathrm{inc}}$ comes first in the tuple.

The value $v_{2}=3$ that the backend receives just afterwards provides a hint
for identification: the most likely scenario (just a single packet loss) now
is that $v_{2}=3$ came from $\sigma_{\mathrm{dec}}$ and that the previous
system state was $\underline{u}_{\mathrm{1b}}=(3,5)$, i.e. the current system
state is $u_{2}=(3,3)$. So, if the received $v_{2}$ is assumed to belong to
$\sigma_{\mathrm{dec}}$, it is significantly more likely that $v_{1}=5$ was
also transmitted by this device. Therefore, the value of $v_{2}$ that was
received at a later point in time influences the backend’s interpretation of
$v_{1}$ and allows it to deliver the packet with $v_{1}$, though delayed. This
example is also illustrated in Fig. 7, where the most likely path as
determined by the Viterbi algorithm is dashed and marked in red. Fig. 7 does
not show all the extremely unlikely system states and unlikely transitions.
The subsequently received CN $4$ confirms the identification that was made
based on $v_{2}=3$: We conclude that, almost certainly, the device with
$\sigma_{\mathrm{inc}}$ has sent the sequence $1\to 2\to 3\to 4$ and the
device with $\sigma_{\mathrm{dec}}$ has sent $10\to 9\to 7\to 5\to 3$.

The kind of resolution presented in Ex. 6 is not always possible; in case
identification is ambiguous, the better course of action can be to drop the
packet than to risk erroneous identification. Note that this ambiguity occurs
only very rarely if we use a sufficiently large alphabet $Z_{\mathrm{q}}$. The
backend is aware of the ambiguity, and the residual probability of being
unable to identify transmitters and having to discard packets becomes
negligible compared to the PEC’s erasure probability.

##  V Exemplary Case: Sigfox

The French company _Sigfox_ [8] operates a global LPWAN. Their network
protocol uses $32$-bit identifiers and $12$-bit SNs, thus allowing for up to
$2^{32}$ addressable end devices and a nonce reuse after $2^{12}=4096$ packets
[1]. If Sigfox employed PERIDOT in a new protocol revision, they could
increase the theoretical maximum number of devices, prolong nonce reuse cycles
and reduce the number of bits that have to be transmitted all at the same
time.

In order to achieve this, we construct a $(q,l)$-proper set based on Thm. 2.
For instance, we may want to encode the CN on a total of $38$ bits. We assume
that the occurrence of 49 or more consecutive packet losses is extremely
unlikely, so we choose $l=50$. Since we need to have $q=pl\leq 2^{38}$ with
$l\,|\,(p-1)$ and $p$ must be prime, we choose the largest such prime, which
is $p=5\,497\,554\,151$. Thus, we get increments for $m=p-1=5\,497\,554\,150$
different devices.

As a result, compared to the current protocol, we

  * •

reduced packet size by 6 bit, resulting in a 5% reduction in energy
consumption for single-bit payload packets,

  * •

increased the nonce reuse cycle by a factor of $q/2^{12}\approx 67.1\cdot
10^{6}$ making replay attacks infeasible and

  * •

increased the theoretical maximum number of identifiable devices by
approximately $28\%$

with negligible implementation costs on the end device side.

##  VI Conclusion

We introduced the PERIDOT scheme and described how identifiers and SNs can be
completely replaced by transmitting CNs based on specially constructed
permutations. One particularly suitable construction was presented, though
entirely different constructions may also be feasible. We showed that PERIDOT
can reduce uplink packet lengths and thus energy consumption, improve security
and increase the theoretical maximum number of addressable devices.

The basic concept of an algorithm for the backend has been outlined, how
exactly to incorporate geolocation information, behavior analysis and other
metadata into state transition probabilities for the HMM remain open questions
though. Another research avenue would be to simulate a global LPWAN employing
PERIDOT so that the influence of different parameters on the system and its
scalability can be tested.

We found and referenced mathematical concepts that are related to PERIDOT in
the theory of asymmetric error correction codes. Still, PERIDOT remains to be
classified and its relation to error correction codes needs to be better
understood.

## References

  * [1] _Sigfox connected objects: Radio specifications v1.5_ , Sigfox, February 2020\.
  * [2] _LoRaWAN™ 1.1 Specification_ , LoRa Alliance, October 2017.
  * [3] B. Alspach, “The wonderful Walecki construction,” _Bulletin of the Institute of Combinatorics and its Applications_ , vol. 52, pp. 7–19, December 2006.
  * [4] T. W. Tillson, “A Hamiltonian decomposition of $K_{2m}^{*}$, $2m\geq 8$,” _Journal of Combinatorial Theory, Series B_ , vol. 29, no. 1, pp. 68–74, 1980\.
  * [5] T. Kløve, B. Bose, and N. Elarief, “Systematic, single limited magnitude error correcting codes for flash memories,” _IEEE Transactions on Information Theory_ , vol. 57, no. 7, pp. 4477–4487, July 2011\.
  * [6] D. Xie and J. Luo, “Asymmetric single magnitude four error correcting codes,” _CoRR_ , vol. abs/1903.01148, 2019. [Online]. Available: http://arxiv.org/abs/1903.01148
  * [7] T. Kløve, J. Luo, I. Naydenova, and S. Yari, “Some codes correcting asymmetric errors of limited magnitude,” _Information Theory, IEEE Transactions on_ , vol. 57, pp. 7459 – 7472, 12 2011.
  * [8] “Sigfox - The Global Communications Service Provider for the Internet of Things (IoT),” https://www.sigfox.com/en, accessed: 2020-03-20.