# The Frobenius Formula for $A=(a,ha+d,ha+b_{2}d,...,ha+b_{k}d)$

Feihu Liu1, Guoce Xin2,∗, Suting Ye3 and Jingjing Yin4 1,2,3,4School of
Mathematical Sciences, Capital Normal University, Beijing 100048, PR China
<EMAIL_ADDRESS>&<EMAIL_ADDRESS>&<EMAIL_ADDRESS>

&<EMAIL_ADDRESS>
(Date: April 26, 2023)

###### Abstract.

Given relative prime positive integers $A=(a_{1},a_{2},...,a_{n})$, the
Frobenius number $g(A)$ is the largest integer not representable as a linear
combination of the $a_{i}$’s with nonnegative integer coefficients. We find
the “Stable” property introduced for the square sequence
$A=(a,a+1,a+2^{2},\dots,a+k^{2})$ naturally extends for
$A(a)=(a,ha+dB)=(a,ha+d,ha+b_{2}d,...,ha+b_{k}d)$. This gives a parallel
characterization of $g(A(a))$ as a “congruence class function” modulo $b_{k}$
when $a$ is large enough. For orderly sequence $B=(1,b_{2},\dots,b_{k})$, we
find good bound for $a$. In particular we calculate $g(a,ha+dB)$ for
$B=(1,2,b,b+1)$, $B=(1,2,b,b+1,2b)$, $B=(1,b,2b-1)$ and $B=(1,2,...,k,K)$. Our
idea also applies to the case $B=(b_{1},b_{2},...,b_{k})$, $b_{1}>1$.

$*$ This work was partially supported by NSFC(12071311).

_Mathematic subject classification_ : Primary 11D07; Secondary 05A15, 11B75,
11D04.

_Keywords_ : Numerical semigroup; Apéry set; Frobenius number; Orderly
sequence.

##  1\. Introduction

Given relative prime positive integers $A=(a_{1},a_{2},...,a_{n})$, the
Frobenius number $g(A)$ is the largest integer not representable as a linear
combination of the $a_{i}$’s with nonnegative integer coefficients. The
calculation of $g(A)$ has been widely studied. See [18] for a detailed
overview. For $n=2$, Sylvester [24] obtained $g(A)=a_{1}a_{2}-a_{1}-a_{2}$ in
1882. In the general case $n\geq 3$, it is known that $g(A)$ can not be given
by closed formulas of a certain type [6]. For $n=3$, both G. Denham [7] and A.
Tripathi [27] have studied formula $g(A)$. Moreover, many formulas for special
cases have been determined (see [11, 3, 19, 23, 25, 26, 8, 12, 14, 20]).

This work is along the line of the combinatorial approach for Frobenius
numbers developed in [16]. By using this method and the Four-Square Theorem in
number theory, we were able to solve an open problem proposed in [9] by D.
Einstein, D. Lichtblau, A. Strzebonski and S. Wagon. See [15]. The open
problem is to characterize $g(A)$ for the square sequence
$A=(a,a+B)=(a,a+1^{2},a+2^{2},...,a+k^{2})$. In order to solve this open
problem, we introduced a generating function to establish certain bounds,
which allows us to analyze to obtain a full characterization of $g(A)$ as a
congruence class function modulo $k^{2}$ when $a$ is sufficiently large.

We observe that the argument in [15] naturally extends for general
$B=(1,b_{2},\dots,b_{k})$. Similarly we can characterize $g(A)$ where
$A=(a,ha+dB)=(a,ha+db_{1},ha+db_{2},...,ha+db_{k})$, $\gcd(a,d)=1,b_{1}=1$.
The resulting formula is a congruence class function modulo $b_{k}$ when $a$
is sufficiently large. The bound for $a$ might be large for general sequence
$B$, but is good for a special class of $B$, called _orderly sequence_ as we
shall introduce next.

We need to introduce some basic definitions and results in [22, 16].
Throughout this paper, $\mathbb{Z}$, $\mathbb{N}$, and $\mathbb{P}$ denote the
set of all integers, non-negative integers, and positive integers,
respectively.

A subset $S$ is a _submonoid_ of $\mathbb{N}$ if $S\subseteq\mathbb{N}$, $0\in
S$ and $S$ is closed under the sum in $\mathbb{N}$. If $\mathbb{N}\setminus S$
is finite, then we say that $S$ is a _numerical semigroup_ (see [2, 22]). For
the sequence $A=(a,b_{1},b_{2},...,b_{k})$ with $\gcd(A)=1$,
$a<b_{1}<b_{2}\cdots<b_{k}$, $a,b_{i}\in\mathbb{P}$, the set
$\mathcal{R}=\left\\{ax+\sum_{i=1}^{k}b_{i}x_{i}\ \mid
x,x_{i}\in\mathbb{N}\right\\}$ is a numerical semigroup [22]. We denote by

$Ape(A,a)=\\{N_{0},N_{1},N_{2},...,N_{a-1}\\},$

the _Apéry set_ of $A$, where $N_{r}:=\min\\{a_{0}\mid a_{0}\equiv r\mod a,\
a_{0}\in\mathcal{R}\\}$, $0\leq r\leq a-1$.

The following fundamental result of A. Brauer and J. E. Shockley are widely
used.

######  Theorem 1.1 ([4]).

Suppose $A:=(a,B)=(a,b_{1},b_{2},...,b_{k})$, $\gcd(A)=1$, $d\in\mathbb{P}$,
$\gcd(a,d)=1$. Then the Frobenius number is

$g(A)=\max
Ape(A,a)-a=\mathop{\max}\limits_{r\in\\{0,1,...,a-1\\}}\\{N_{r}\\}-a=\mathop{\max}\limits_{r\in\\{0,1,...,a-1\\}}\\{N_{dr}\\}-a.$

Suppose $A=(a,ha+dB)=(a,ha+db_{1},...,ha+db_{k})$. The computation of $N_{dr}$
is reduced to a minimization problem defined by

$O_{B}(M):=\min\left\\{\sum_{i=1}^{k}x_{i}\mid\sum_{i=1}^{k}b_{i}x_{i}=M,\ \
M,x_{i}\in\mathbb{N},1\leq i\leq k\right\\}.$ (1)

######  Lemma 1.2 ([16]).

Let $A=(a,ha+db_{1},...,ha+db_{k})$, $k,h,d,b_{i}\in\mathbb{P}$ and
$\gcd(A)=1$, $\gcd(a,d)=1$. For a given $0\leq r\leq a-1$, we have

$N_{dr}=\min\\{N_{dr}(m)\mid m\in\mathbb{N}\\},\qquad\text{where}\ \ \
N_{dr}(m):=O_{B}(ma+r)\cdot ha+(ma+r)d.$ (2)

Now, let $B=(b_{1},b_{2},...,b_{k})$, $1=b_{1}<b_{2}<\cdots b_{k}$. For given
$B$ and $M\in\mathbb{N}$, determining $O_{B}(M)$ is called _the change-making
problem_ [1]. We always assume $b_{1}=1$ to avoid the absence of the solution.
The greedy strategy is to use as many of the maximum as possible, than as many
of the next one as possible, and so on. We denote $G_{B}(M)$ the number of
elements used in $B$ by the greedy strategy. So we have $O_{B}(M)\leq
G_{B}(M)$. If the greedy solution is always optimal, i.e., $O_{B}(M)=G_{B}(M)$
for all $M$, then we call the sequence $B$ _orderly_ ; Otherwise, we call
sequence $B$ _non-orderly_. We know that $B=(1)$, $B=(1,b_{2})$ are orderly
sequences. The sequence $B=(1,6,13)$ is non-orderly. Because
$18=13+1+1+1+1+1=6+6+6$, we have $3=O_{B}(18)<G_{B}(18)=6$. A representation
of $M$ by exactly $O_{B}(M)$ elements is said to be _optimal_.

In this paper, we characterize the formula $g(A)$ for
$A=(a,ha+dB)=(a,ha+d,ha+db_{2},...,ha+db_{k})$, $\gcd(a,d)=1$. We assume
$k\geq 2$ since the $k=1$ case is known. We find that the “Stable” property
for $O_{B}(M)$ not only holds for the square sequence, but also holds for
general $B$. This leads to a characterization of the Frobenius formula $g(A)$
as a “congruence class function” modulo $b_{k}$, i.e., $g(A(a))$ is divided
into $b_{k}$ classes according to $a\mod b_{k}$. Moreover, each segment is a
quadratic polynomial in $a$ with leading coefficient $\frac{h}{b_{k}}$. This
result holds when $a$ is greater than a certain bound. If $B$ is an orderly
sequence, we obtain a good bound.

The paper is organized as follows. In Section 2, we mainly discuss the
“Stable” property of $O_{B}(M)$ for general $B$. In Section 3, we characterize
the Frobenius formula $g(A(a))=g(a,ha+dB)$, where $B=(1,b_{2},...,b_{k})$. As
special cases, we obtain the Frobenius formula $g(a,ha+dB)$ for
$B=(1,2,b,b+1)$. Section 4 focus on orderly sequences $B$. We obtain good
bounds for the Frobenius formula $g(A(a))$. Furthermore, calculate
$g(a,ha+dB)$ for $B=(1,2,b,b+1,2b)$, $B=(1,b,2b-1)$ and $B=(1,2,...,k,K)$. In
Section 5, we discuss the case $b_{1}>1$.

##  2\. The “Stable” Property

Let $A=(a,ha+dB)=(a,ha+db_{1},ha+db_{2},...,ha+db_{k})$ and $b_{1}=1$. In this
section we mainly focus on characterizing the “Stable” property about
$O_{B}(M)$. Our starting point is Lemma 1.2, which says that we need to
compute the quantity

$N_{dr}=\min\left\\{O_{B}(ma+r)\cdot
ha+(ma+r)d\mid\sum_{i=1}^{k}x_{i}b_{i}=ma+r,\ \ m,x_{i}\in\mathbb{N},1\leq
i\leq k\right\\}$

for each $r$.

In summary, we need to study how to calculate $O_{B}(M)$ efficiently. By
Equation (1), it is natural to consider the generating function:

$F(t,q)=\prod_{i=1}^{k}\frac{1}{1-tq^{b_{i}}}=\sum_{n\geq
0}\left(\sum_{x_{1}+b_{2}x_{2}+\cdots+b_{k}x_{k}=n}t^{x_{1}+x_{2}+\cdots+x_{k}}\right)q^{n}.$

If we call a solution $(x_{1},x_{2},...,x_{k})$ for (1) satisfying
$x_{1}+\cdots+x_{k}=O_{B}(M)$ _optimal_ , then the generating function
$f(t,q)=\sum_{n\geq 0}t^{O_{B}(n)}q^{n}$ extracts only one optimal
representation, weighted by $t^{O_{B}(n)}$, for each $n$. It is easy to see
that

$f(t,q)=\sum_{n\geq 0}t^{O_{B}(n)}q^{n}:=\circledast F(t,q),$

where $\circledast$ is the operator defined as follows.

######  Definition 2.1.

For a power series $G(t,q)$ in $t,q$ with nonnegative coefficients, define
$\circledast G(t,q)$ be the power series obtained from $G(t,q)$ by picking a
minimum degree (in $t$) term in each coefficient (in $q$).

The basic fact $\circledast F(t,q)G(t,q)=\circledast(\circledast
F(t,q))(\circledast G(t,q))$ allows us to use Maple to compute the first $M+1$
terms of $f(t,q)$ quickly for any given reasonably large $M$:

  1. (1)

Start with $f_{1}:=\sum_{n=0}^{M}t^{n}q^{n}$.

  2. (2)

Suppose $f_{i-1}$ has been obtained. Then $f_{i}$ is obtained by: first
compute $\circledast f_{i-1}\cdot\sum_{n=0}^{h_{i}}t^{n}q^{b_{i}n}$ where
$h_{i}=\lfloor M/b_{i}\rfloor$ will be optimized, and then remove all terms
with degree in $q$ larger than $M$.

  3. (3)

Set $f(t,q)|_{q^{\leq M}}=f_{k}$.

Thus we have proved the following result.

######  Lemma 2.2.

Let $B=(1,b_{2},...,b_{k})$, $b_{i}\in\mathbb{N}$, $2\leq i\leq k$. For a
given $M$, the first $M+1$ term $f(t,q)|_{q^{\leq M}}$ of $f(t,q)$ can be
computed in polynomial time in $M$. Consequently, $O_{B}(r),\ r\leq M$ can be
computed in polynomial time in $M$.

We first give an example to facilitate our understanding of the subsequent
results. The following instance says that $O_{B}(r)$ is stable in some sense.

######  Example 2.3.

Let $B=(1,11,14)$. For a given reasonably large $M=140$, we get the following
results by Maple. To see the stable property clearly, we divide by
$f(t,q)=\sum_{i=0}^{13}f^{i}$, where $f^{i}$ extract all terms corresponding
to $q^{14s+i}$. We also bold faced all terms not implied by the stable
property.

$\displaystyle f^{0}$
$\displaystyle=\mathbf{1}+tq^{14}+{t}^{2}{q}^{28}+{t}^{3}{q}^{42}+{t}^{4}{q}^{56}+{t}^{5}{q}^{70}+t^{6}q^{84}+t^{7}q^{98}+t^{8}q^{112}+t^{9}q^{126}+\cdots$
$\displaystyle f^{1}$
$\displaystyle=\mathbf{tq}+t^{2}q^{15}+{t}^{3}{q}^{29}+{t}^{4}{q}^{43}+{t}^{5}{q}^{57}+{t}^{6}{q}^{71}+t^{7}q^{85}+t^{8}q^{99}+t^{9}q^{113}+t^{10}q^{127}+\cdots$
$\displaystyle f^{2}$
$\displaystyle=\mathbf{t^{2}q^{2}+t^{3}q^{16}+{t}^{4}{q}^{30}+t^{4}q^{44}}+{t}^{5}{q}^{58}+{t}^{6}{q}^{72}+{t}^{7}{q}^{86}+t^{8}q^{100}+t^{9}q^{114}+t^{10}q^{128}+\cdots$
$\displaystyle f^{3}$
$\displaystyle=\mathbf{t^{3}q^{3}+t^{4}q^{17}+{t}^{5}{q}^{31}+t^{5}q^{45}}+{t}^{6}{q}^{59}+{t}^{7}{q}^{73}+{t}^{8}{q}^{87}+t^{9}q^{101}+t^{10}q^{115}+t^{11}q^{129}+\cdots$
$\displaystyle f^{4}$
$\displaystyle=\mathbf{t^{4}q^{4}+t^{5}q^{18}+{t}^{6}{q}^{32}+{t}^{6}{q}^{46}+{t}^{7}{q}^{60}+{t}^{8}{q}^{74}+t^{8}q^{88}}+t^{9}q^{102}+t^{10}q^{116}+t^{11}q^{130}+\cdots$
$\displaystyle f^{5}$
$\displaystyle=\mathbf{t^{5}q^{5}+t^{6}q^{19}+{t}^{3}{q}^{33}}+{t}^{4}{q}^{47}+{t}^{5}{q}^{61}+t^{6}q^{75}+{t}^{7}{q}^{89}+t^{8}q^{103}+t^{9}q^{117}+t^{10}q^{131}+\cdots$
$\displaystyle f^{6}$
$\displaystyle=\mathbf{t^{6}q^{6}+t^{7}q^{20}+{t}^{4}{q}^{34}}+{t}^{5}{q}^{48}+{t}^{6}{q}^{62}+{t}^{7}{q}^{76}+t^{8}q^{90}+t^{9}q^{104}+t^{10}q^{118}+t^{11}q^{132}+\cdots$
$\displaystyle f^{7}$
$\displaystyle=\mathbf{t^{7}q^{7}+t^{8}q^{21}+{t}^{5}{q}^{35}+{t}^{6}{q}^{49}+{t}^{7}{q}^{63}+{t}^{7}{q}^{77}}+t^{8}q^{91}+t^{9}q^{105}+t^{10}q^{119}+t^{11}q^{133}+\cdots$
$\displaystyle f^{8}$
$\displaystyle=\mathbf{t^{8}q^{8}+t^{2}q^{22}}+{t}^{3}{q}^{36}+{t}^{4}{q}^{50}+{t}^{5}{q}^{64}+{t}^{6}{q}^{78}+t^{7}q^{92}+t^{8}q^{106}+t^{9}q^{120}+t^{10}q^{134}+\cdots$
$\displaystyle f^{9}$
$\displaystyle=\mathbf{t^{9}q^{9}+t^{3}q^{23}}+{t}^{4}{q}^{37}+{t}^{5}{q}^{51}+{t}^{6}{q}^{65}+{t}^{7}{q}^{79}+t^{8}q^{93}+t^{9}q^{107}+t^{10}q^{121}+t^{11}q^{135}+\cdots$
$\displaystyle f^{10}$
$\displaystyle=\mathbf{t^{10}q^{10}+t^{4}q^{24}+{t}^{5}{q}^{38}+{t}^{6}{q}^{52}+{t}^{6}{q}^{66}}+{t}^{7}{q}^{80}+t^{8}q^{94}+t^{9}q^{108}+t^{10}q^{122}+t^{11}q^{136}+\cdots$
$\displaystyle f^{11}$
$\displaystyle=\mathbf{tq^{11}}+t^{2}q^{25}+{t}^{3}{q}^{39}+{t}^{4}{q}^{53}+{t}^{5}{q}^{67}+{t}^{6}{q}^{81}+t^{7}q^{95}+t^{8}q^{109}+t^{9}q^{123}+t^{10}q^{137}+\cdots$
$\displaystyle f^{12}$
$\displaystyle=\mathbf{t^{2}q^{12}}+t^{3}q^{26}+{t}^{4}{q}^{40}+{t}^{5}{q}^{54}+{t}^{6}{q}^{68}+{t}^{7}{q}^{82}+t^{8}q^{96}+t^{9}q^{110}+t^{10}q^{124}+t^{11}q^{138}+\cdots$
$\displaystyle f^{13}$
$\displaystyle=\mathbf{t^{3}q^{13}+t^{4}q^{27}+{t}^{5}{q}^{41}+{t}^{5}{q}^{55}}+{t}^{6}{q}^{69}+{t}^{7}{q}^{83}+t^{8}q^{97}+t^{9}q^{111}+t^{10}q^{125}+t^{11}q^{139}+\cdots.$

Any $O_{B}(r)$ can be deduced from the bold faced terms. For instance,
$O_{B}(130)=O_{B}(88+3\cdot 14)=O_{B}(88)+3=11$.

Let $c$ be the maximum value of the degree of $t$ in the first $b_{k}$ term of
$f(t,q)$, i.e., $c=\max\\{O_{B}(r)\mid 0\leq r\leq b_{k}-1\\}$. Clearly $c\geq
1$.

######  Lemma 2.4.

Let $B=(1,b_{2},...,b_{k})$, $b_{i}\in\mathbb{N}$, $2\leq i\leq k$. If
$r\in\mathbb{N}$, then

$\left\lceil\frac{r}{b_{k}}\right\rceil\leq
O_{B}(r)\leq\left\lfloor\frac{r}{b_{k}}\right\rfloor+c.$

###### Proof.

Let $r=sb_{k}+r_{1}$, $s\geq 0$, $0\leq r_{1}\leq b_{k}-1$. If $r_{1}=0$, then
clearly $O_{B}(r)=s$. If $1\leq r_{1}\leq b_{k}-1$,

$\left\lceil\frac{r}{b_{k}}\right\rceil=s+1\leq O_{B}(r)\leq
s+O_{B}(r_{1})\leq s+c=\left\lfloor\frac{r}{b_{k}}\right\rfloor+c.$

∎

The following lemma says that $O_{B}(r)$ is “Stable”, and hence reduce the
computation of $O_{B}(r)$ to finitely many $r$’s.

######  Lemma 2.5.

Let $B=(1,b_{2},...,b_{k})$, $b_{i}\in\mathbb{N}$, $2\leq i\leq k$. For any
$r\geq\left\lceil\frac{(c-1)b_{k-1}}{b_{k}-b_{k-1}}\right\rceil\cdot b_{k}$,
$r\in\mathbb{P}$, we have

$O_{B}(b_{k}+r)=O_{B}(r)+1.$

###### Proof.

Obviously $O_{B}(b_{k}+r)\leq O_{B}(r)+1$ always hold. If $b_{k}+r$ has a
minimal representation including a $b_{k}$, then removing the $b_{k}$ leads to
the other side inequality $O_{B}(r)\leq O_{B}(b_{k}+r)-1$ and hence
$O_{B}(b_{k}+r)=O_{B}(r)+1$.

Thus assume to the contrary that $O_{B}(b_{k}+r)<O_{B}(r)+1$. Then $b_{k}+r$
cannot have a minimal representation using $b_{k}$. We prove that this is
impossible under our assumption.

Let $r=mb_{k}+j$, where $0\leq j\leq b_{k}-1$. By definition of $c$, we have
$j=\sum_{i=1}^{c}e_{i}$, $e_{i}\in\\{0,1,b_{2},...,b_{k-1}\\}$ for $1\leq
i\leq c$. By
$r\geq\left\lceil\frac{(c-1)b_{k-1}}{b_{k}-b_{k-1}}\right\rceil\cdot b_{k}$,
we have $m\geq\left\lceil\frac{(c-1)b_{k-1}}{b_{k}-b_{k-1}}\right\rceil$. The
$m$ is chosen so that $mb_{k}\geq(m+c-1)b_{k-1}$. For such $m$, the following
formula holds:

$r=mb_{k}+j=mb_{k}+\sum_{i=1}^{c}e_{i}\geq(m+c-1)b_{k-1}.$

This implies that without using $b_{k}$, we have
$O_{B}(b_{k}+r)\geq(m+c-1)+2$. Then we have $m+c+1\leq
O_{B}(b_{k}+r)<O_{B}(r)+1\leq m+c+1$, a contradiction. ∎

######  Theorem 2.6.

Given a sequence $B=(1,b_{2},...,b_{k})$, there is a polynomial time algorithm
in $b_{k}$ for computing $O_{B}(M)$ for all $M\in{\mathbb{P}}$.

###### Proof.

By Lemma 2.5,For any
$r\geq\left\lceil\frac{(c-1)b_{k-1}}{b_{k}-b_{k-1}}\right\rceil\cdot b_{k}$,
we have $O_{B}(sb_{k}+r)=s+O_{B}(r)$ for $s\in\mathbb{N}$. Thus we only need
to calculate $O_{B}(r)$ for $0\leq
r\leq\left\lceil\frac{(c-1)b_{k-1}}{b_{k}-b_{k-1}}\right\rceil\cdot b_{k}$. By
Lemma 2.2, $O_{B}(r),\ r\leq M$ can be computed in polynomial time in $M$.
This completes the proof. ∎

##  3\. The Frobenius Formula $g(A(a))$

We will characterize the Frobenius formula $g(A)$, where
$A=(a,ha+dB)=(a,ha+d,ha+db_{2},...,ha+db_{k})$. In this section, we always
assume that $c\geq 2$. In Section 4, we will discuss the case $c=1$. We need
some results about $N_{dr}$.

######  Lemma 3.1.

Given a sequence $B=(1,b_{2},...,b_{k})$. If $a\geq(c-1)b_{k}$, then for a
given $r$, we have $N_{dr}=N_{dr}(0)$.

###### Proof.

For a given $r$ and any $m\geq 0$, let $ma+r=sb_{k}+r_{1}$, where $0\leq
r_{1}<b_{k}$. By $a\geq(c-1)b_{k}$, we have
$(m+1)a+r=sb_{k}+a+r_{1}\geq(s+c-1)b_{k}+r_{1}$. If $r_{1}\neq 0$, then we
have $O_{B}((m+1)a+r)\geq(s+c)$. By Lemma 2.4, we have $O_{B}(ma+r)=s+l$ for a
certain $1\leq l\leq c$. Therefore we have

$\displaystyle
N_{dr}(m+1)\geq(s+c)ha+((m+1)a+r)d\geq(s+l)ha+(ma+r)d=N_{dr}(m).$

If $r_{1}=0$, then we have $O_{B}((m+1)a+r)\geq(s+c-1)$ and $O_{B}(ma+r)=s$.
Similarly, we have $N_{dr}(m+1)\geq N_{dr}(m)$.

Then $N_{r}(m)$ is increasing, and hence minimizes at $m=0$. ∎

Now, we show that $N_{dr}$ behave nicely when $a$ is large, by the means of we
have the following result.

######  Lemma 3.2.

Given a sequence $B=(1,b_{2},...,b_{k})$. Let
$u=\max\left\\{c-1,\left\lceil\frac{(c-1)b_{k-1}}{b_{k}-b_{k-1}}\right\rceil\right\\}$.
For any $a\geq(u+c-1)b_{k}$, we have

$\mathop{\max}\limits_{0\leq r\leq
a-1}\\{N_{dr}\\}=\mathop{\max}\limits_{a-b_{k}\leq r\leq a-1}\\{N_{dr}\\}.$

###### Proof.

By Lemma 3.1 and $a\geq(u+c-1)b_{k}$, we have $N_{r}=N_{r}(0)$. By Lemma 2.5,
obviously for a given
$r\geq\left\lceil\frac{(c-1)b_{k-1}}{b_{k}-b_{k-1}}\right\rceil\cdot b_{k}$,
$O_{B}(sb_{k}+r)$ is increasing with $s\geq 0$.

Now, we consider the following case. If $y=mb_{k}+\sum_{i=1}^{c}e_{i}$ where
$m\geq 0$, and $e_{i}\in\\{0,1,b_{2},...,b_{k-1}\\}$ are not all $0$ for
$1\leq i\leq c$. We have $O_{B}(y)\leq m+c$, $O_{B}(y+b_{k})\geq m+2$, …,
$O_{B}(y+(c-1)b_{k})\geq m+c$. So for a given $r\geq ub_{k}+(c-2)b_{k}$, we
must have $O_{B}(r)\geq O_{B}(r-(c-1)b_{k})$. More generally, we have
$O_{B}(r)\geq O_{B}(r-sb_{k}),s\geq 0$. Therefore when
$a\geq(u+c-2)b_{k}+b_{k}$, we have $\mathop{\max}\limits_{0\leq r\leq
a-1}\\{N_{dr}\\}=\mathop{\max}\limits_{a-b_{k}\leq r\leq a-1}\\{N_{dr}\\}$. ∎

For a given sequence $B=(1,b_{2},...,b_{k})$, the following theorem will show
that the Frobenius formula $g(A)$ with $A=(a,ha+dB)$ is a “congruence class
function” with $b_{k}$ classes.

######  Theorem 3.3.

Let $A(a)=(a,ha+dB)=(a,ha+d,ha+db_{2},...,ha+db_{k})$, $\gcd(a,d)=1$,
$u=\max\left\\{c-1,\left\lceil\frac{(c-1)b_{k-1}}{b_{k}-b_{k-1}}\right\rceil\right\\}$
and $h\geq\left\lceil\frac{d}{u+c-1}\right\rceil$, $a,h,d\in\mathbb{P}$. There
exist two nonnegative integer sequences $W_{B}=(w_{j})_{0\leq j\leq b_{k}-1}$
and $R_{B}=(r_{j})_{0\leq j\leq b_{k}-1}$, such that for all
$a\geq(u+c-1)b_{k}$, we have

$g(A(a))=(w_{j}h-1)a+r_{j}d+(ha+b_{k}d)\left(\left\lfloor\frac{a}{b_{k}}\right\rfloor-
u-c+1\right),\ \ \textrm{where }a\equiv j\mod b_{k}.$

Moreover, $W_{B}$ and $R_{B}$ are both increasing, and $w_{b_{k}-1}-w_{0}\leq
1$.

The proof is parallel to the proof of [15, Theorem 4.11], but we need details
to obtain the bounds.

###### Proof.

Let $a=sb_{k}+j\geq(u+c-1)b_{k}$, where $s\geq(u+c-1)$ and $0\leq j\leq
b_{k}-1$. By Lemma 3.2, we have $\mathop{\max}\limits_{0\leq r\leq
a-1}\\{N_{dr}\\}=\mathop{\max}\limits_{a-b_{k}\leq r\leq a-1}\\{N_{dr}\\}$.

By $h\geq\left\lceil\frac{d}{u+c-1}\right\rceil$ and $a\geq(u+c-1)b_{k}$, we
have $h\geq\lceil\frac{b_{k}d}{a}\rceil$. Furthermore, we have $ha-b_{k}d\geq
0$. Therefore $N_{dr}=O_{B}(r)\cdot ha+rd$ is dominated by the coefficient
$O_{B}(r)$. This suggest that we shall first find
$\iota=\mathop{\max}\limits_{a-b_{k}\leq r\leq a-1}O_{B}(r)$ and then find the
largest $a-b_{k}\leq\widehat{r}\leq a-1$ satisfying
$O_{B}(\widehat{r})=\iota$. Then $\max\\{N_{dr}\\}=O_{B}(\widehat{r})\cdot
ha+\widehat{r}d$, and the Frobenius number is $O_{B}(\widehat{r})\cdot
ha+\widehat{r}d-a$.

Now, let $(u+c-1)b_{k}\leq a\leq(u+c)b_{k}-1$ and $a\equiv j\mod b_{k}$. So
$j$ can take all the numbers in $\\{0,1,2,...,b_{k}-1\\}$. For a certain $j$,
according to the above discussion, there is an $a-b_{k}\leq r_{j}\leq a-1$
such that we can get $g(A)=\max\\{N_{dr}\\}-a=w_{j}\cdot ha+r_{j}d-a$, where
$w_{j},r_{j}\in\mathbb{N}$ and $w_{j}=O_{B}(r_{j})$.

For the same $j$, if $a=sb_{k}+j$, $s>(u+c-1)$, then
$a=(s-u-c+1)b_{k}+(u+c-1)b_{k}+j$. By Lemma 4.1, we have
$\overline{r}=(s-u-c+1)b_{k}+r_{j}$ such that
$\max\\{N_{dr}\\}=N_{d\overline{r}}$. Then

$\displaystyle g(A(a))$
$\displaystyle=(s-u-c+1+w_{j})ha+((s-u-c+1)b_{k}+r_{j})d-a$
$\displaystyle=(w_{j}h-1)a+r_{j}d+(ha+db_{k})\cdot\left(\left\lfloor\frac{a}{b_{k}}\right\rfloor-
u-c+1\right).$

Therefore for any $0\leq j\leq b_{k}-1$, all $w_{j}$ and $r_{j}$ form the
sequences $W_{B}$ and $R_{B}$ respectively.

By the calculation process of $w_{j}$ and $r_{j}$, it is easy to see that
$(u+c-2)b_{k}\leq r_{j}<(u+c)b_{k}$. When $a=(u+c-1)b_{k}$, let $\widehat{r}$
be the largest number such that

$(u+c-2)b_{k}\leq\widehat{r}\leq(u+c-1)b_{k}-1\ \ \ \ \ \text{and}\ \ \ \ \
O_{B}(\widehat{r})=\mathop{\max}\limits_{(u+c-2)b_{k}\leq
r\leq(u+c-1)b_{k}-1}O_{B}(r).$

In the next period $(u+c-1)b_{k}$ to $(u+c)b_{k}-1$ corresponding to
$a=(u+c)b_{k}$, $\widehat{r}^{\prime}=\widehat{r}+b_{k}$ satisfies

$(u+c-1)b_{k}\leq\widehat{r}^{\prime}\leq(u+c)b_{k}-1\ \ \ \ \ \text{and}\ \ \
\ \
O_{B}(\widehat{r}^{\prime})=O_{B}(\widehat{r})+1=\mathop{\max}\limits_{(u+c-1)b_{k}\leq
r\leq(u+c)b_{k}-1}O_{B}(r).$

Therefore, in any interval of length $b_{k}$ starting with $a\equiv j\mod
b_{k}$ that lies between $(u+c-2)b_{k}$ and $(u+c)b_{k}-1$, we have two cases:
i) If the interval contains $\widehat{r}^{\prime}$, then
$r_{j}=\widehat{r}^{\prime}$; ii) If the interval contains $\widehat{r}$, then
$r_{j}$ lies between $\widehat{r}$ and $\widehat{r}^{\prime}$ and
$O_{B}(r_{j})$ is either $O_{B}(\widehat{r})$ or $O_{B}(\widehat{r})+1$.
Moreover, $r_{j}$ is increasing with respect to $j$. Obviously, from the above
discussion, we can know that $W_{B}$ is increasing and $w_{b_{k}-1}-w_{0}\leq
1$. ∎

######  Example 3.4.

Let $B=(1,11,14)$. For $A(a)=(ha+dB)=(a,ha+d,ha+11d,ha+14d)$, by Example 2.3,
we have $c=10$, $u=33$, $h\geq\lceil\frac{d}{42}\rceil$ and $a\geq 588$. We
know $574\leq r_{j}<601$.

$\displaystyle\circledast F(t,q)=\cdots$
$\displaystyle+{t}^{41}{q}^{574}+{t}^{42}{q}^{575}+{t}^{42}{q}^{576}+t^{43}q^{577}+{t}^{43}{q}^{578}+{t}^{42}{q}^{579}+{t}^{43}{q}^{580}$
$\displaystyle+{t}^{43}{q}^{581}+{t}^{42}{q}^{582}+{t}^{43}{q}^{583}+t^{43}q^{584}+t^{42}q^{585}+t^{43}q^{586}+\underline{t^{43}q^{587}}$
$\displaystyle+{t}^{42}{q}^{588}+\mathbf{{t}^{43}{q}^{589}}+\mathbf{{t}^{43}{q}^{590}}+\mathbf{{t}^{44}{q}^{591}}+\mathbf{{t}^{44}{q}^{592}}+{t}^{43}{q}^{593}+\mathbf{{t}^{44}{q}^{594}}$
$\displaystyle+\mathbf{{t}^{44}{q}^{595}}+{t}^{43}{q}^{596}+\mathbf{t^{44}q^{597}}+\mathbf{t^{44}q^{598}}+t^{43}q^{599}+\mathbf{t^{44}q^{600}}+\underline{t^{44}q^{601}}$
$\displaystyle+\cdots,$

where we only displayed the necessary part in our proof. Multiplying the first
(second) row by $tq^{14}$ gives the third (fourth) row.

The terms for $\widehat{r}$ and $\widehat{r}^{\prime}$ are underlined in the
two rows with

$O_{B}(\widehat{r})=\mathop{\max}\limits_{574\leq r\leq
587}O_{B}(r)=O_{B}(587)=43\quad\text{ and }\quad
O_{B}(\widehat{r}^{\prime})=44.$

We discuss how to find $r_{j}$ from the above formula.

For $a=588$, $r_{0}=587$ is just $\widehat{r}$ and consequently
$w_{0}=O_{B}(587)=43$, $g(A)=43ha+587d-a$. Furthermore we conclude that if
$a\equiv 0\mod 14$ and $a\geq 588$, then

$g(A(a))=(43h-1)a+587d+(ha+14d)\left(\left\lfloor\frac{a}{14}\right\rfloor-42\right).$

For $a=589$, since $42=O_{B}(588)<O_{B}(587)=43$, we have $r_{1}=587$. For
$a=590$, the situation is different and we have $r_{2}=43$. This is because we
meet the bold faced term, which corresponds to $43=O_{B}(589)\geq
O_{B}(587)=43$. The bold faced terms are left-to-right maximums with respect
to the power of $t$. By a similar reasoning, we obtain

$\displaystyle W_{B}=[43,43,43,43,44,44,44,44,44,44,44,44,44,44],$
$\displaystyle
R_{B}=[587,587,589,590,591,592,592,594,595,595,597,598,598,600],$

from which we can build the following Frobenius formula for $B=(1,11,14)$:

$\displaystyle
g(A(a))=\left\\{\begin{array}[]{lc}(43h-1)a+587d+(ha+14d)(\lfloor\frac{a}{14}\rfloor-42)&\
\text{if}\ \ a\equiv 0,1\mod 14;\\\
(43h-1)a+589d+(ha+14d)(\lfloor\frac{a}{14}\rfloor-42)&\ \text{if}\ \ a\equiv
2\mod 14;\\\ (43h-1)a+590d+(ha+14d)(\lfloor\frac{a}{14}\rfloor-42)&\
\text{if}\ \ a\equiv 3\mod 14;\\\
(44h-1)a+591d+(ha+14d)(\lfloor\frac{a}{14}\rfloor-42)&\ \text{if}\ \ a\equiv
4\mod 14;\\\ (44h-1)a+592d+(ha+14d)(\lfloor\frac{a}{14}\rfloor-42)&\
\text{if}\ \ a\equiv 5,6\mod 14;\\\
(44h-1)a+594d+(ha+14d)(\lfloor\frac{a}{14}\rfloor-42)&\ \text{if}\ \ a\equiv
7\mod 14;\\\ (44h-1)a+595d+(ha+14d)(\lfloor\frac{a}{14}\rfloor-42)&\
\text{if}\ \ a\equiv 8,9\mod 14;\\\
(44h-1)a+597d+(ha+14d)(\lfloor\frac{a}{14}\rfloor-42)&\ \text{if}\ \ a\equiv
10\mod 14;\\\ (44h-1)a+598d+(ha+14d)(\lfloor\frac{a}{14}\rfloor-42)&\
\text{if}\ \ a\equiv 11,12\mod 14;\\\
(44h-1)a+600d+(ha+14d)(\lfloor\frac{a}{14}\rfloor-42)&\ \text{if}\ \ a\equiv
13\mod 14;\\\ \end{array}\right.$

######  Example 3.5.

For $A(a)=(ha+dB)=(a,ha+d,ha+4d,ha+11d,ha+17d)$, similarly, we have $c=4$,
$u=6$, $h\geq\lceil\frac{d}{9}\rceil$ and $a\geq 153$. Therefore we obtain

$\displaystyle
g(A(a))=\left\\{\begin{array}[]{lc}(11h-1)a+150d+(ha+17d)(\lfloor\frac{a}{17}\rfloor-9)&\
\text{if}\ \ a\equiv 0,1,2\mod 17;\\\
(11h-1)a+155d+(ha+17d)(\lfloor\frac{a}{17}\rfloor-9)&\text{if}\ \ a\equiv
3\mod 17;\\\ (11h-1)a+156d+(ha+17d)(\lfloor\frac{a}{17}\rfloor-9)&\text{if}\ \
a\equiv 4,5,6\mod 17;\\\
(11h-1)a+159d+(ha+17d)(\lfloor\frac{a}{17}\rfloor-9)&\text{if}\ \ a\equiv
7\mod 17;\\\ (12h-1)a+160d+(ha+17d)(\lfloor\frac{a}{17}\rfloor-9)&\text{if}\ \
a\equiv 8,9,10,11,12,13\mod 17;\\\
(12h-1)a+166d+(ha+17d)(\lfloor\frac{a}{17}\rfloor-9)&\text{if}\ \ a\equiv
14\mod 17;\\\ (12h-1)a+167d+(ha+17d)(\lfloor\frac{a}{17}\rfloor-9)&\text{if}\
\ a\equiv 15,16\mod 17.\end{array}\right.$

######  Remark 3.6.

The bound $a\geq(u+c-1)b_{k}$ in Theorem 3.3 is not tight. In fact, when
$a\geq 116$, the formula in Example 3.4 holds. If $h=d=1$ and $2\leq a\leq
115$, the formula in Example 3.4 only holds at $a=2,102$. Similarly, the
formula in Example 3.5 holds for $a\geq 42$. If $h=d=1$ and $2\leq a\leq 41$,
the formula in Example 3.5 only holds at $a=3,8,25,26,27,31$.

In the proof of Theorem 3.3, by calculating $O_{B}(r)$, we provide a general
method for computing the coefficients $w_{j},r_{j}$. Finally, an exact
Frobenius formula can be obtained.

######  Theorem 3.7.

Let $A(a)=(a,ha+dB)=(a,ha+d,ha+2d,ha+bd,ha+(b+1)d)$, $\gcd(a,d)=1$, $b\geq 4$
and $a,h,d,b\in\mathbb{P}$. If
$h\geq\left\lceil\frac{2d}{(b-3)(b+1)}\right\rceil$,
$a\geq\frac{(b-3)(b+1)^{2}}{2}$ for odd $b$, or if
$h\geq\left\lceil\frac{2d}{(b-2)(b+1)}\right\rceil$,
$a\geq\frac{(b-2)(b+1)^{2}}{2}$ for even $b$, then we have

$\displaystyle
g(A(a))=\left\\{\begin{array}[]{lc}\lfloor\frac{a}{b+1}\rfloor(ha+(b+1)d)+(j-1)d-a&\
\text{if}\ \ a\equiv j\in\\{0,1\\}\mod b+1;\\\
\lfloor\frac{a}{b+1}\rfloor(ha+(b+1)d)+(j-1)d+(h-1)a&\ \text{if}\ \ a\equiv
j\in\\{2,3,...,b\\}\mod b+1.\end{array}\right.$

###### Proof.

The proof is similar to Example 2.3. If $b$ is odd, then we have

$\displaystyle f^{0}$
$\displaystyle=1+tq^{b+1}+{t}^{2}{q}^{2b+2}\cdots+{t}^{b-3}{q}^{b^{2}-2b-3}+{t}^{b-2}{q}^{b^{2}-b-2}+\cdots+{t}^{\frac{(b-3)(b+1)}{2}}{q}^{\frac{(b-3)(b+1)^{2}}{2}}+\cdots$
$\displaystyle f^{1}$
$\displaystyle=tq+t^{2}q^{b+2}+{t}^{3}{q}^{2b+3}\cdots+{t}^{b-2}{q}^{b^{2}-2b-2}+{t}^{b-1}{q}^{b^{2}-b-1}+\cdots+{t}^{\frac{(b-3)(b+1)}{2}+1}{q}^{\frac{(b-3)(b+1)^{2}}{2}+1}+\cdots$
$\displaystyle f^{2}$
$\displaystyle=tq^{2}+t^{2}q^{b+3}+{t}^{3}{q}^{2b+4}\cdots+{t}^{b-2}{q}^{b^{2}-2b-1}+{t}^{b-1}{q}^{b^{2}-b}+\cdots+{t}^{\frac{(b-3)(b+1)}{2}+1}{q}^{\frac{(b-3)(b+1)^{2}}{2}+2}+\cdots$
$\displaystyle f^{3}$
$\displaystyle=t^{2}q^{3}+t^{3}q^{b+4}+{t}^{4}{q}^{2b+5}\cdots+{t}^{b-2}{q}^{b^{2}-2b}+{t}^{b-1}{q}^{b^{2}-b+1}+\cdots+{t}^{\frac{(b-3)(b+1)}{2}+1}{q}^{\frac{(b-3)(b+1)^{2}}{2}+3}+\cdots$
$\displaystyle f^{4}$
$\displaystyle=t^{2}q^{4}+t^{3}q^{b+5}+{t}^{4}{q}^{2b+6}\cdots+{t}^{b-2}{q}^{b^{2}-2b+1}+{t}^{b-1}{q}^{b^{2}-b+2}+\cdots+{t}^{\frac{(b-3)(b+1)}{2}+1}{q}^{\frac{(b-3)(b+1)^{2}}{2}+4}+\cdots$
$\displaystyle\cdots$ $\displaystyle\cdots$ $\displaystyle f^{b-3}$
$\displaystyle=t^{\frac{b-3}{2}}q^{b-3}+t^{\frac{b+1}{2}}q^{2b-2}+{t}^{\frac{b+3}{2}}{q}^{3b-1}\cdots+{t}^{b-2}{q}^{b^{2}-b-6}+{t}^{b-1}{q}^{b^{2}-5}+\cdots+{t}^{\frac{(b-3)(b+1)}{2}+1}{q}^{\frac{(b-3)(b+1)^{2}}{2}+b-3}+\cdots$
$\displaystyle f^{b-2}$
$\displaystyle=t^{\frac{b-1}{2}}q^{b-2}+t^{\frac{b+1}{2}}q^{2b-1}+{t}^{3}{q}^{3b}\cdots+{t}^{b-2}{q}^{b^{2}-b-5}+{t}^{b-1}{q}^{b^{2}-4}+\cdots+{t}^{\frac{(b-3)(b+1)}{2}+1}{q}^{\frac{(b-3)(b+1)^{2}}{2}+b-2}+\cdots$
$\displaystyle f^{b-1}$
$\displaystyle=t^{\frac{b-1}{2}}q^{b-1}+t^{2}q^{2b}+{t}^{3}{q}^{3b+1}\cdots+{t}^{b-2}{q}^{b^{2}-b-4}+{t}^{b-1}{q}^{b^{2}-3}+\cdots+{t}^{\frac{(b-3)(b+1)}{2}+1}{q}^{\frac{(b-3)(b+1)^{2}}{2}+b-1}+\cdots$
$\displaystyle f^{b}$
$\displaystyle=tq^{b}+t^{2}q^{2b+1}+{t}^{3}{q}^{3b+2}\cdots+{t}^{b-2}{q}^{b^{2}-b-3}+{t}^{b-1}{q}^{b^{2}-2}+\cdots+{t}^{\frac{(b-3)(b+1)}{2}+1}{q}^{\frac{(b-3)(b+1)^{2}}{2}+b}+\cdots.$

Now, we have $c=\frac{b-1}{2}$ and $u=\frac{b(b-3)}{2}$. Similarly, if $b$ is
even, then we have $c=\frac{b}{2}$ and $u=\frac{b(b-2)}{2}$. By Theorem 3.3,
we can get the Frobenius formula $g(A(a))$. ∎

##  4\. A Special Case: Orderly Sequence Formula

In this section, let $B$ be an orderly sequence, i.e, $O_{B}(M)=G_{B}(M)$,
where $G_{B}(M)$ the number of elements used in $B$ by greedy strategy. Now,
for the $A=(a,ha+dB)=(a,ha+d,ha+db_{2},...,ha+d_{k})$, we will obtain a
friendly lower bound for $a$ in Theorem 3.3. For related research on orderly
sequence, see [1, 5, 10, 17].

###  4.1. The Frobenius Formula for Orderly Sequence $B$

The “Stable” property for orderly sequence is obvious.

######  Lemma 4.1.

Let $B=(1,b_{2},...,b_{k})$ be an orderly sequence. For any $r\in\mathbb{P}$,
we have

$O_{B}(b_{k}+r)=O_{B}(r)+1.$

Similarly, Lemma 2.4 and Lemma 3.1 is still correct. For Lemma 3.2, we briefly
describe as follows. Let $c$ be the maximum value of the degree of $t$ in the
first $b_{k}$ term of $f(t,q)$, i.e., $c=\max\\{O_{B}(r)\mid 0\leq r\leq
b_{k}-1\\}$.

######  Lemma 4.2.

Suppose $B=(1,b_{2},...,b_{k})$ is orderly. For any $a\geq(c-1)b_{k}$, $c\geq
2$, we have

$\mathop{\max}\limits_{0\leq r\leq
a-1}\\{N_{dr}\\}=\mathop{\max}\limits_{a-b_{k}\leq r\leq a-1}\\{N_{dr}\\}.$

###### Proof.

By Lemma 3.1 and $a\geq(c-1)b_{k}$, we have $N_{dr}=N_{dr}(0)=O_{B}(r)\cdot
ha+rd$. By Lemma 4.1, for a given $r$, $O_{B}(sb_{k}+r)$ is increasing with
respect to $s\geq 0$. Therefore when $a\geq(c-1)b_{k}$, we have
$\mathop{\max}\limits_{0\leq r\leq
a-1}\\{N_{dr}\\}=\mathop{\max}\limits_{a-b_{k}\leq r\leq a-1}\\{N_{dr}\\}$. ∎

######  Theorem 4.3.

Given an orderly sequence $B=(1,b_{2},...,b_{k})$, $c\geq 2$. Let
$A(a)=(a,ha+dB)=(a,ha+d,ha+db_{2},...,ha+db_{k})$, $\gcd(a,d)=1$ and
$h\geq\left\lceil\frac{d}{c-1}\right\rceil$, $a,h,d\in\mathbb{P}$. There exist
two nonnegative integer sequences $W_{B}=(w_{j})_{0\leq j\leq b_{k}-1}$ and
$R_{B}=(r_{j})_{0\leq j\leq b_{k}-1}$, such that for all $a\geq(c-1)b_{k}$, we
have

$g(A(a))=(w_{j}h-1)a+r_{j}d+(ha+b_{k}d)\left(\left\lfloor\frac{a}{b_{k}}\right\rfloor-c+1\right),\
\ \textrm{where }a\equiv j\mod b_{k}.$

Moreover, $W_{B}$ and $R_{B}$ are both increasing, and $w_{b_{k}-1}-w_{0}\leq
1$.

######  Example 4.4.

Let $B=(1,5,9)$ and $A(a)=(a,ha+d,ha+5d,ha+9d)$. We have

$\displaystyle f(t,q)=$
$\displaystyle(1+tq+t^{2}q^{2}+t^{3}q^{3}+t^{4}q^{4}+tq^{5}+t^{2}q^{6}+t^{3}q^{7}+t^{4}q^{8})\cdot\frac{1}{1-tq^{9}}$
$\displaystyle=\left(\frac{1-(tq)^{5}}{1-tq}+\frac{tq^{5}(1-(tq)^{4})}{1-tq}\right)\cdot\frac{1}{1-tq^{9}}$
$\displaystyle=\frac{1-(tq)^{5}+tq^{5}(1-(tq)^{4})}{(1-tq)(1-tq^{9})}.$

So $h\geq\left\lceil\frac{d}{3}\right\rceil$. The lower bound is $a\geq
3b_{k}=27$. Now, we have

$\displaystyle
g(A(a))=\left\\{\begin{array}[]{lc}(6h-1)a+26d+(ha+9d)(\lfloor\frac{a}{9}\rfloor-3)&\
\text{if}\ \ a\equiv 0,1,2,3\mod 9;\\\
(6h-1)a+30d+(ha+9d)(\lfloor\frac{a}{9}\rfloor-3)&\text{if}\ \ a\equiv 4\mod
9;\\\ (7h-1)a+31d+(ha+9d)(\lfloor\frac{a}{9}\rfloor-3)&\text{if}\ \ a\equiv
5,6,7,8\mod 9.\end{array}\right.$

######  Remark 4.5.

The bound $a\geq(c-1)b_{k}$ in Lemma 4.2 and Theorem 4.3 are friendly. In
fact, when $a\geq 24$, the formula in Example 4.4 holds.

###  4.2. Some Interesting Formulas

In [1, Proposition 4.2], the sequence $B=(1,2,b,b+1,2b)$, $b\geq 4$ is
orderly. A. Adamaszek and M. Adamaszek have discussed the sequence $B$’s
properties in detail in [1]. Note that the partial sequence $(1,2,b,b+1),b\geq
4$ of $B$ is not orderly.

######  Theorem 4.6.

Let $A(a)=(a,ha+dB)=(a,ha+d,ha+2d,ha+bd,ha+(b+1)d,ha+2bd)$, $\gcd(a,d)=1$,
$b\geq 4$ and $a,h,d,b\in\mathbb{P}$. If $b$ is even and
$h\geq\left\lceil\frac{2d}{b-2}\right\rceil$, $a\geq b(b-2)$, then we have

$\displaystyle
g(A(a))=\left\\{\begin{array}[]{lc}\left(\lfloor\frac{a}{2b}\rfloor+\frac{b}{2}-1\right)ha+2bd\lfloor\frac{a}{2b}\rfloor-
a-d&\ \text{if}\ \ a\equiv 0,1,2,...,b-3\mod 2b;\\\
\left(\lfloor\frac{a}{2b}\rfloor+\frac{b}{2}-1\right)ha+2bd\lfloor\frac{a}{2b}\rfloor-a+bd-3d&\
\text{if}\ \ a\equiv b-2\mod 2b;\\\
\left(\lfloor\frac{a}{2b}\rfloor+\frac{b}{2}-1\right)ha+2bd\lfloor\frac{a}{2b}\rfloor-a+bd-2d&\
\text{if}\ \ a\equiv b-1\mod 2b;\\\
\left(\lfloor\frac{a}{2b}\rfloor+\frac{b}{2}\right)ha+2bd\lfloor\frac{a}{2b}\rfloor-a+bd-d&\
\text{if}\ \ a\equiv b,b+1,...,2b-2\mod 2b;\\\
\left(\lfloor\frac{a}{2b}\rfloor+\frac{b}{2}\right)ha+2bd\lfloor\frac{a}{2b}\rfloor-a+2bd-2d&\
\text{if}\ \ a\equiv 2b-1\mod 2b.\end{array}\right.$

If $b$ is odd and $h\geq\left\lceil\frac{2d}{b-1}\right\rceil$, $a\geq
b(b-1)$, then we have

$\displaystyle
g(A(a))=\left\\{\begin{array}[]{lc}\left(\lfloor\frac{a}{2b}\rfloor+\frac{b-1}{2}\right)ha+2bd\lfloor\frac{a}{2b}\rfloor-
a-d&\ \text{if}\ \ a\equiv 0,1,2,...,b-2\mod 2b;\\\
\left(\lfloor\frac{a}{2b}\rfloor+\frac{b-1}{2}\right)ha+2bd\lfloor\frac{a}{2b}\rfloor-a+bd-2d&\
\text{if}\ \ a\equiv b-1\mod 2b;\\\
\left(\lfloor\frac{a}{2b}\rfloor+\frac{b-1}{2}\right)ha+2bd\lfloor\frac{a}{2b}\rfloor-a+bd-d&\
\text{if}\ \ a\equiv b,b+1,...,2b-3\mod 2b;\\\
\left(\lfloor\frac{a}{2b}\rfloor+\frac{b-1}{2}\right)ha+2bd\lfloor\frac{a}{2b}\rfloor-a+2bd-3d&\
\text{if}\ \ a\equiv 2b-2\mod 2b;\\\
\left(\lfloor\frac{a}{2b}\rfloor+\frac{b-1}{2}\right)ha+2bd\lfloor\frac{a}{2b}\rfloor-a+2bd-2d&\
\text{if}\ \ a\equiv 2b-1\mod 2b.\end{array}\right.$

###### Proof.

If $b$ is even, we have

$\displaystyle f(t,q)=$
$\displaystyle\Big{(}1+tq+tq^{2}+t^{2}q^{3}+t^{2}q^{4}+\cdots+t^{\frac{b-2}{2}}q^{b-3}+t^{\frac{b-2}{2}}q^{b-2}+t^{\frac{b}{2}}q^{b-1}$
$\displaystyle+tq^{b}+tq^{b+1}+t^{2}q^{b+2}+t^{2}q^{b+3}+\cdots
t^{\frac{b}{2}}q^{2b-2}+t^{\frac{b}{2}}q^{2b-1}\Big{)}\cdot\frac{1}{1-tq^{2b}}.$

So we have $c=\frac{b}{2}$ and $a\geq(c-1)2b=b(b-2)$. Suppose $a\equiv j\mod
2b$, $0\leq j\leq 2b-1$. In $f(t,q)$, the coefficient before in
$q^{b(b-2)-1}=q^{(\frac{b}{2}-2)\cdot 2b+2b-1}$ is
$t^{\frac{b}{2}-2+\frac{b}{2}}=t^{b-2}$. Therefore we have $w_{j}=b-2$ and
$r_{j}=b^{2}-2b-1$ for $0\leq j\leq b-3$. Similarly, the coefficient before in
$q^{(\frac{b}{2}-1)\cdot 2b+b-3}$ is $t^{b-2}$ in $f(t,q)$. So we have
$w_{b-2}=b-2$ and $r_{b-2}=b^{2}-b-3$. Again because there is
$t^{b-2}q^{(\frac{b}{2}-1)2b+b-2}$ in $f(t,q)$, we have $w_{b-1}=b-2$ and
$r_{b-1}=b^{2}-b-2$. For $b\leq j\leq 2b-2$, there is
$t^{b-1}q^{(\frac{b}{2}-1)2b+b-1}$ in $f(t,q)$. We have $w_{j}=b-1$ and
$r_{j}=b^{2}-b-1$ for $b\leq j\leq 2b-2$. Finally, because there is
$t^{b-1}q^{(\frac{b}{2}-1)2b+2b-1}$ in $f(t,q)$, we have $w_{2b-1}=b-1$ and
$r_{2b-1}=b^{2}-2$. So we obtain the sequences $W_{B}$ and $R_{B}$ in Theorem
4.3. By the formula in Theorem 4.3, we obtain the Frobenius formula $g(A(a))$
in which $b$ is even.

If $b$ is odd, we have

$\displaystyle f(t,q)=$
$\displaystyle\Big{(}1+tq+tq^{2}+t^{2}q^{3}+t^{2}q^{4}+\cdots+t^{\frac{b-1}{2}}q^{b-2}+t^{\frac{b-1}{2}}q^{b-1}$
$\displaystyle+tq^{b}+tq^{b+1}+t^{2}q^{b+2}+t^{2}q^{b+3}+\cdots
t^{\frac{b-1}{2}}q^{2b-3}+t^{\frac{b-1}{2}}q^{2b-2}+t^{\frac{b+1}{2}q^{2b-1}}\Big{)}\cdot\frac{1}{1-tq^{2b}}.$

The calculation process of Frobenius formula $g(A(a))$ is similar to that $b$
is even. This completes the proof. ∎

Obviously, the sequence $(1,b)$, $b\geq 2$ is orderly. By the _One-Point
Theorem_ [5, 10, 17], we know that $B=(1,b,2b-1),b\geq 3$ is an orderly
sequence.

######  Theorem 4.7.

Let $A(a)=(a,ha+dB)=(a,ha+d,ha+bd,ha+(2b-1)d)$, $\gcd(a,d)=1$, $b\geq 3$ and
$a,h,d,b\in\mathbb{P}$. Suppose $h\geq\left\lceil\frac{d}{b-2}\right\rceil$,
$a\geq 2b^{2}-5b+2$, then we have

$\displaystyle
g(A(a))=\left\\{\begin{array}[]{lc}\left(\lfloor\frac{a}{2b-1}\rfloor+b-2\right)ha+(2b-1)d\lfloor\frac{a}{2b-1}\rfloor-
a-d&\ \text{if}\ \ a\equiv 0,1,...,b-2\mod 2b-1;\\\
\left(\lfloor\frac{a}{2b-1}\rfloor+b-2\right)ha+(2b-1)d\lfloor\frac{a}{2b-1}\rfloor-a+(b-2)d&\
\text{if}\ \ a\equiv b-1\mod 2b-1;\\\
\left(\lfloor\frac{a}{2b-1}\rfloor+b-1\right)ha+(2b-1)d\lfloor\frac{a}{2b-1}\rfloor-a+(b-1)d&\
\text{if}\ \ a\equiv b,...,2b-2\mod 2b-1.\end{array}\right.$

###### Proof.

By the sequence $b=(1,b,2b-1)$, $b\geq 3$ is orderly, we have

$\displaystyle f(t,q)=$
$\displaystyle\Big{(}1+tq+t^{2}q^{2}+t^{3}q^{3}+\cdots+t^{b-3}q^{b-3}+t^{b-2}q^{b-2}+t^{b-1}q^{b-1}$
$\displaystyle+tq^{b}+t^{2}q^{b+1}+t^{3}q^{b+2}+\cdots
t^{b-3}q^{2b-4}+t^{b-2}q^{2b-3}+t^{b-1}q^{2b-2}\Big{)}\cdot\frac{1}{1-tq^{2b-1}}.$

By Theorem 4.3, we have $c=b-1$, $h\geq\lceil\frac{d}{b-2}\rceil$ and $a\geq
2b^{2}-5b+2$. The proof of remaining parts are routine. ∎

In [23], E. S. Selmer studies the sequence $A=(a,a+1,a+2,...,a+k,a+K)$ with
$K>k$. In [21], Ö. J. Rödseth further obtains $g(A)$ for
$A=(a,a+d,...,a+kd,a+Kd)$ with an additional term. In [13], there are also
some results about _Sylvester sum_ for$A=(a,a+d,...,a+kd,a+Kd)$. Now, we
obtain the following results by Theorem 4.3.

######  Theorem 4.8.

Let $A(a)=(a,ha+dB)=(a,ha+d,ha+2d,...,ha+kd,ha+Kd)$, $\gcd(a,d)=1$, $K-1>k\geq
2$ and $a,h,d,k,K\in\mathbb{P}$. Let $K=sk+t$, $0\leq t\leq k-1$ and $s\geq
1$. For $2\leq t\leq k-1$, if $h\geq\left\lceil\frac{d}{s}\right\rceil$,
$a\geq sK$, then we have

$\displaystyle
g(A(a))=\left\\{\begin{array}[]{lc}\left(\lfloor\frac{a}{K}\rfloor+s\right)ha+Kd\lfloor\frac{a}{K}\rfloor-
a-d&\ \text{if}\ \ a\equiv j\in\\{0,1,...,(s-1)k+1\\}\mod K;\\\
\left(\lfloor\frac{a}{K}\rfloor+s\right)ha+Kd\lfloor\frac{a}{K}\rfloor-a+(j-1)d&\
\text{if}\ \ a\equiv j\in\\{(s-1)k+2,...,sk+1\\}\mod K;\\\
\left(\lfloor\frac{a}{K}\rfloor+s+1\right)ha+Kd\lfloor\frac{a}{K}\rfloor-a+(j-1)d&\
\text{if}\ \ a\equiv j\in\\{sk+2,...,K-1\\}\mod K.\end{array}\right.$

For $t=0,1$, if $h\geq\left\lceil\frac{d}{s-1}\right\rceil$, $a\geq(s-1)K$,
then we have

$\displaystyle
g(A(a))=\left\\{\begin{array}[]{lc}\left(\lfloor\frac{a}{K}\rfloor+s-1\right)ha+Kd\lfloor\frac{a}{K}\rfloor-
a-d&\ \text{if}\ \ a\equiv j\in\\{0,1,...,(s-2)k+1\\}\mod K;\\\
\left(\lfloor\frac{a}{K}\rfloor+s-1\right)ha+Kd\lfloor\frac{a}{K}\rfloor-a+(j-1)d&\
\text{if}\ \ a\equiv j\in\\{(s-2)k+2,...,(s-1)k+1\\}\mod K;\\\
\left(\lfloor\frac{a}{K}\rfloor+s\right)ha+Kd\lfloor\frac{a}{K}\rfloor-a+(j-1)d&\
\text{if}\ \ a\equiv j\in\\{(s-1)k+2,...,K-1\\}\mod K.\end{array}\right.$

###### Proof.

If $2\leq t\leq k-1$, we have

$\displaystyle f(t,q)=$
$\displaystyle\Big{(}1+\big{(}tq+tq^{2}+\cdots+tq^{k}\big{)}+\big{(}t^{2}q^{k+1}+t^{2}q^{k+2}\cdots+t^{2}q^{2k}\big{)}+\cdots+\big{(}t^{s}q^{(s-1)k+1}$
$\displaystyle+t^{s}q^{(s-1)k+2}+\cdots
t^{s}q^{sk}\big{)}+\big{(}t^{s+1}q^{sk+1}+t^{s+1}q^{sk+2}+\cdots+t^{s+1}q^{sk+t-1}\big{)}\Big{)}\cdot\frac{1}{1-tq^{K-1}}.$

By Theorem 4.3, we have $c=s+1$, $h\geq\lceil\frac{d}{s}\rceil$ and $a\geq
sK$.

If $t=0,1$, by $K>k+1$, we have $s\geq 2$. Therefore we have

$\displaystyle f(t,q)=$
$\displaystyle\Big{(}1+\big{(}tq+tq^{2}+\cdots+tq^{k}\big{)}+\big{(}t^{2}q^{k+1}+t^{2}q^{k+2}\cdots+t^{2}q^{2k}\big{)}+\cdots+\big{(}t^{s-1}q^{(s-2)k+1}$
$\displaystyle+t^{s-1}q^{(s-2)k+2}+\cdots
t^{s-1}q^{(s-1)k}\big{)}+\big{(}t^{s}q^{(s-1)k+1}+\cdots+t^{s}q^{sk+t-1}\big{)}\Big{)}\cdot\frac{1}{1-tq^{K-1}}.$

By Theorem 4.3, we have $c=s$, $h\geq\lceil\frac{d}{s-1}\rceil$ and
$a\geq(s-1)K$.

The proof of remaining parts are routine. ∎

###  4.3. The case $c=1$

Now, suppose $c=1$. We know that $B=(1,2,...,k)$, $k\geq 2$. This is an
orderly sequence. Lemma 2.4, Lemma 3.1 and Lemma 4.1 is still correct. We can
force the assumption that $c=2$. Then Lemma 4.2 and Theorem 4.3 is also holds.
Moreover, there is no restriction between $h$ and $d$. Therefore, we can
obtain the following corollary.

######  Corollary 4.9 ([23]).

Let $A(a)=(a,ha+dB)=(a,ha+d,ha+2d,...,ha+kd)$, $\gcd(a,d)=1$, $a\geq 2$,
$a,h,d,k\in\mathbb{P}$. Then we have

$g(A(a))=ha\left(\left\lfloor\frac{a-2}{k}\right\rfloor+1\right)+(d-1)(a-1)-1.$
(3)

###### Proof.

We first suppose $a\geq k$, i.e., we force that $c=2$. By Theorem 4.3, we have

$\displaystyle w_{j}=\left\\{\begin{array}[]{lc}1&\ \text{if}\ \ j=0,1;\\\ 2&\
\text{if}\ \ 2\leq j\leq k-1.\end{array}\right.$

and

$r_{j}=k+j-1,\ \ 0\leq j\leq k-1.$

Therefore we have

$\displaystyle
g(A(a))=\left\\{\begin{array}[]{lc}(h-1)a+(k+j-1)d+(ha+kd)(\lfloor\frac{a}{k}\rfloor-1)&\
\text{if}\ \ j=0,1\ \ \ \ \ \ \ \ ;\\\
(2h-1)a+(k+j-1)d+(ha+kd)(\lfloor\frac{a}{k}\rfloor-1)&\ \text{if}\ \ 2\leq
j\leq k-1;\end{array}\right.$

where $a\equiv j\mod k$. Furthermore, the above formula also holds for $2\leq
a\leq k-1$. It is easy to verify that the above formula is equivalent to
Equation (3). ∎

For Corollary 4.9, A. Brauer [3] first computed $g(A(a))=g(a,a+1,...,a+k)$. J.
B. Roberts [19] extended this result to $A=(a,a+d,...,a+kd)$. E. S. Selmer
[23] further generalized to the case $A=(a,ha+d,ha+2d,...,ha+kd)$ (also see
[25]).

##  5\. The Case $b_{1}\neq 1$

We believe the ideas developed here also works for general
$B=(b_{1},b_{2},\dots,b_{k})$, i.e., without the restriction $b_{1}=1$.
Indeed, we may assume $\gcd(b_{1},b_{2},\dots,b_{k})=1$ because of the $d$. We
claim that $O_{B}(M)$ also have the “Stable” property. The proof is similar
but much more complicated. We only illustrate the idea by an example.

Let us consider the “Stable” property of $B=(4,8,15,17)$. Similar to Example
2.3, we divide by $f(t,q)=\sum_{i=0}^{16}f^{i}$, where $f^{i}$ extract all
terms corresponding to $q^{17s+i},s\geq 0$. Again we bold faced all terms not
implied by the stable property. We added some underlined $0\cdot q^{*}$ terms
for clarity. For instance, $0\cdot q^{18}$ in $f^{1}$ means that $18$ is not
representable by $B$.

$\displaystyle f^{0}$
$\displaystyle=\mathbf{1}+tq^{17}+{t}^{2}{q}^{34}+{t}^{3}{q}^{51}+{t}^{4}{q}^{68}+{t}^{5}{q}^{85}+t^{6}q^{102}+t^{7}q^{119}+t^{8}q^{136}+t^{9}q^{153}+\cdots$
$\displaystyle f^{1}$ $\displaystyle=\mathbf{\underline{0\cdot q+0\cdot
q^{18}}+{t}^{4}{q}^{35}+{t}^{5}{q}^{52}+{t}^{6}{q}^{69}+{t}^{7}{q}^{86}+t^{8}q^{103}+t^{8}q^{120}}+t^{9}q^{137}+t^{10}q^{154}+\cdots$
$\displaystyle f^{2}$ $\displaystyle=\mathbf{\underline{0\cdot
q^{2}}+t^{2}q^{19}}+{t}^{3}{q}^{36}+t^{4}q^{53}+{t}^{5}{q}^{70}+{t}^{6}{q}^{87}+{t}^{7}{q}^{104}+t^{8}q^{121}+t^{9}q^{138}+t^{10}q^{155}+\cdots$
$\displaystyle f^{3}$ $\displaystyle=\mathbf{\underline{0\cdot
q^{3}}+t^{3}q^{20}+{t}^{4}{q}^{37}+t^{5}q^{54}+{t}^{6}{q}^{71}+{t}^{7}{q}^{88}+{t}^{7}{q}^{105}}+t^{8}q^{122}+t^{9}q^{139}+t^{10}q^{156}+\cdots$
$\displaystyle f^{4}$
$\displaystyle=\mathbf{tq^{4}}+t^{2}q^{21}+{t}^{3}{q}^{38}+{t}^{4}{q}^{55}+{t}^{5}{q}^{72}+{t}^{6}{q}^{89}+t^{7}q^{106}+t^{8}q^{123}+t^{9}q^{140}+t^{10}q^{157}+\cdots$
$\displaystyle f^{5}$ $\displaystyle=\mathbf{\underline{0\cdot q^{5}+0\cdot
q^{22}}+{t}^{4}{q}^{39}+{t}^{5}{q}^{56}+{t}^{6}{q}^{73}+t^{6}q^{90}}+{t}^{7}{q}^{107}+t^{8}q^{124}+t^{9}q^{141}+t^{10}q^{158}+\cdots$
$\displaystyle f^{6}$ $\displaystyle=\mathbf{\underline{0\cdot
q^{6}}+t^{2}q^{23}}+{t}^{3}{q}^{40}+{t}^{4}{q}^{57}+{t}^{5}{q}^{74}+{t}^{6}{q}^{91}+t^{7}q^{108}+t^{8}q^{125}+t^{9}q^{142}+t^{10}q^{159}+\cdots$
$\displaystyle f^{7}$ $\displaystyle=\mathbf{\underline{0\cdot
q^{7}}+t^{3}q^{24}+{t}^{4}{q}^{41}+{t}^{5}{q}^{58}+{t}^{5}{q}^{75}}+{t}^{6}{q}^{92}+t^{7}q^{109}+t^{8}q^{126}+t^{9}q^{143}+t^{10}q^{160}+\cdots$
$\displaystyle f^{8}$
$\displaystyle=\mathbf{tq^{8}}+t^{2}q^{25}+{t}^{3}{q}^{42}+{t}^{4}{q}^{59}+{t}^{5}{q}^{76}+{t}^{6}{q}^{93}+t^{7}q^{110}+t^{8}q^{127}+t^{9}q^{144}+t^{10}q^{161}+\cdots$
$\displaystyle f^{9}$ $\displaystyle=\mathbf{\underline{0\cdot q^{9}+0\cdot
q^{26}}+{t}^{5}{q}^{43}+{t}^{4}{q}^{60}}+{t}^{5}{q}^{77}+{t}^{6}{q}^{94}+t^{7}q^{111}+t^{8}q^{128}+t^{9}q^{145}+t^{10}q^{162}+\cdots$
$\displaystyle f^{10}$ $\displaystyle=\mathbf{\underline{0\cdot
q^{10}}+t^{3}q^{27}}+{t}^{4}{q}^{44}+{t}^{5}{q}^{61}+{t}^{6}{q}^{78}+{t}^{7}{q}^{95}+t^{8}q^{112}+t^{9}q^{129}+t^{10}q^{146}+t^{11}q^{163}+\cdots$
$\displaystyle f^{11}$ $\displaystyle=\mathbf{\underline{0\cdot
q^{11}}+t^{4}q^{28}+{t}^{3}{q}^{45}}+{t}^{4}{q}^{62}+{t}^{5}{q}^{79}+{t}^{6}{q}^{96}+t^{7}q^{113}+t^{8}q^{130}+t^{9}q^{147}+t^{10}q^{164}+\cdots$
$\displaystyle f^{12}$
$\displaystyle=\mathbf{t^{2}q^{12}}+t^{3}q^{29}+{t}^{4}{q}^{46}+{t}^{5}{q}^{63}+{t}^{6}{q}^{80}+{t}^{7}{q}^{97}+t^{8}q^{114}+t^{9}q^{131}+t^{10}q^{148}+t^{11}q^{165}+\cdots$
$\displaystyle f^{13}$ $\displaystyle=\mathbf{\underline{0\cdot
q^{13}}+t^{2}q^{30}}+{t}^{3}{q}^{47}+{t}^{4}{q}^{64}+{t}^{5}{q}^{81}+{t}^{6}{q}^{98}+t^{7}q^{115}+t^{8}q^{132}+t^{9}q^{149}+t^{10}q^{166}+\cdots$
$\displaystyle f^{14}$ $\displaystyle=\mathbf{\underline{0\cdot
q^{14}}+t^{3}q^{31}}+{t}^{4}{q}^{48}+{t}^{5}{q}^{65}+{t}^{6}{q}^{82}+{t}^{7}{q}^{99}+t^{8}q^{116}+t^{9}q^{133}+t^{10}q^{150}+t^{11}q^{167}+\cdots$
$\displaystyle f^{15}$
$\displaystyle=\mathbf{tq^{15}}+t^{2}q^{32}+{t}^{3}{q}^{49}+{t}^{4}{q}^{66}+{t}^{5}{q}^{83}+{t}^{6}{q}^{100}+t^{7}q^{117}+t^{8}q^{134}+t^{9}q^{151}+t^{10}q^{168}+\cdots$
$\displaystyle f^{16}$
$\displaystyle=\mathbf{t^{2}q^{16}}+t^{3}q^{33}+{t}^{4}{q}^{50}+{t}^{5}{q}^{67}+{t}^{6}{q}^{84}+{t}^{7}{q}^{101}+t^{8}q^{118}+t^{9}q^{135}+t^{10}q^{152}+t^{11}q^{169}+\cdots.$

Similarly, any $O_{B}(r)$ can be deduced from the bold faced terms, but
numbers in $\mathcal{NR}(B)=\\{1,2,3,5,6,7,9,10,11,13,14,18,22,26\\}$ are not
representable by $B$.

######  Theorem 5.1.

Let $A(a)=(a,ha+dB)=(a,ha+4d,ha+8d,ha+15d,ha+17d)$, $\gcd(a,d)=1$ and
$a,h,d\in\mathbb{P}$. If $a\geq 90$,
$h\geq\left\lceil\frac{17d}{90}\right\rceil$ and $a\equiv j\mod 17$, $0\leq
j\leq 16$, then we have

$g(A(a))=(\gamma_{j}h-1)a+(26+j)d+(ha+17d)\lfloor\frac{a}{17}\rfloor,$

where
$(\gamma_{0},\gamma_{1},...,\gamma_{17})=(2,3,2,3,2,3,2,3,2,3,3,3,3,3,3,3,3)$.

###### Proof.

By the “Stable” property of $B=(4,8,15,17)$, the $O_{B}(r)$ are determined by
$(O_{B}(r))_{r\leq 121}$. For convenience, we first consider the case $a\geq
136=8\times 17$. Let $\mathcal{R}(B)=\\{r\mid 0\leq r\leq
a-1\\}\setminus\mathcal{NR}(B)$.

By Equation (2), we know that $N_{dr}(m):=O_{B}(ma+r)\cdot ha+(ma+r)d$. For
$a\geq 136=8\times 17$ and $r\in\mathcal{R}(B)$, we have

$\displaystyle N_{dr}(m+1)-N_{dr}(m)=(O_{B}((m+1)a+r)-O_{B}(ma+r))ha+ad\geq
0.$

So we have $N_{dr}=N_{dr}(0)$ for $r\in\mathcal{R}(B)$. For
$r\in\mathcal{NR}(B)$, one can see that $N_{dr}(m)$ only exists for $m\geq 1$.
Therefore we have $N_{dr}=N_{dr}(1)$ in this case.

By $h\geq\left\lceil\frac{17d}{90}\right\rceil$, we have $90h\geq 17d$ and
$ha\geq 17d$. This implies that $N_{dr}$ is dominated by $O_{B}(r)ha$ or
$O_{B}(a+r)ha$. This suggests the following computation of $g(A(a))$. We begin
with the case $a=17s$, $s\geq 8$. The base step is when $a=136=17\times 8$. We
have

$\displaystyle\max_{0\leq r\leq a-1}\\{N_{dr}\\}$
$\displaystyle=\max\left\\{\max_{r\in\mathcal{R}(B)}\\{N_{dr}\\},\max_{r\in\mathcal{NR}(B)}\\{N_{dr}\\}\right\\}$
$\displaystyle=\max\left\\{\max_{119\leq r\leq 135}\\{O_{B}(r)\cdot
ha+rd\\},\max_{r\in\mathcal{NR}(B)}\\{O_{B}(a+r)\cdot ha+(a+r)d\\}\right\\}$
$\displaystyle=\max\left\\{\\{9ha+135d\\},\\{O_{B}(136+26)\cdot
ha+(136+26)d\\}\right\\}$ $\displaystyle=10ha+162d.$

For $s\geq 8$, we write $a=(s-8)\cdot 17+136$. Therefore

$\displaystyle g(A(a))$ $\displaystyle=(s-8+10)ha+((s-8)\cdot 17+(136+26))d-a$
$\displaystyle=(2h-1)a+26d+(ha+17d)\left\lfloor\frac{a}{17}\right\rfloor.$

The computation of $g(A(a))$ where $a=17s+j$, $s\geq 8$, $1\leq j\leq 16$, can
be done similarly. Readers can check that the above formula also holds for
$90\leq a\leq 135$. ∎

For $a=89$, the formula fails because the condition $\max_{0\leq r\leq
a-1}\\{N_{dr}\\}=O_{B}(89+26)\cdot ha+(89+26)d$ is not satisfied:
$O_{B}(89+14)=8>O_{B}(89+26)=7$, and we have
$\max_{r\in\mathcal{NR}}\\{N_{dr}\\}=O_{B}(89+14)\cdot ha+(89+14)d$.

For a specific $B$ with $\gcd(B)=1$ and $b_{1}>1$, the idea in the proof of
Theorem 5.1 still applies to compute the Frobenius formula $g(A(a))$. But the
process is much more complicated. For example, we need to modify the $c$ as in
Lemma 2.4, which is the maximum value of the degree of $t$ in the first
$b_{k}$ term of $f(t,q)$. This has to be modified. We may let $c$ be the
maximum value of the degree of $t$ in the
$\left\lceil\frac{g(B)}{b_{k}}\right\rceil$-th column of
$f(t,q)=\sum_{i=0}^{b_{k}-1}f^{i}$, where $g(B)$ is the Frobenius number for
the sequence $B$. In other words, we have

$c=\max\left\\{O_{B}(r)\mid\left\lceil\frac{g(B)}{b_{k}}\right\rceil\cdot
b_{k}\leq
r\leq\left(\left\lceil\frac{g(B)}{b_{k}}\right\rceil+1\right)b_{k}-1\right\\}.$

Now one can see that the following corollary should be correct.

######  Corollary 5.2.

For a given positive integer sequence $B=(b_{1},b_{2},...,b_{k})$ satisfying
$b_{1}<b_{2}<\cdots<b_{k}$ and $\gcd(B)=1$. Let
$A(a)=(a,ha+dB)=(a,ha+b_{1}d,ha+b_{2}d,...,ha+b_{k}d)$, $\gcd(a,d)=1$ and
$a,h,d\in\mathbb{P}$. When $a$ is greater than a certain bound, the Frobenius
formula $g(A(a))$ is a “congruence class function” modulo $b_{k}$, and each
segment is a quadratic polynomial in $a$ with leading coefficient
$\frac{h}{b_{k}}$.

##  6\. Concluding Remark

Our main results are Theorems 3.3, 4.3 and Corollary 5.2. We give a
characterization of the Frobenius formula for
$A(a)=(a,ha+dB)=(a,ha+d,ha+db_{2},...,ha+db_{k})$ for a general sequence
$B=(1,b_{2},b_{3},...,b_{k})$. This indeed gives a polynomial time algorithm
in $b_{k}$ for the computation of $g(A(a))$. In some special cases, we can
even compute $g(A(a))$ for symbolic $B$.

Acknowledgements: This work was partially supported by the National Natural
Science Foundation of China [12071311].

## References

  * [1] A. Adamaszek, M. Adamaszek, _Combinatorics of the change-making problem_ , European. J. Comb. 31 (2010), 47–63.
  * [2] A. Assi, M. D’Anna, P. A. García-Sánchez _Numerical Semigroups and Applications_ , Second edition. Vol.3, RSMS Springer, Cham (2020).
  * [3] A. Brauer, _On a problem of partitions_ , Amer. J. Math. 64 (1942), 299–312.
  * [4] A. Brauer, J. E. Shockley, _On a problem of Frobenius_ , J. Reine Angew. Math. 211 (1962), 215–220.
  * [5] L. J. Cowen, R. Cowen, A. Steinberg, _Totally greedy coin sets and greedy obstructions_ , Electron. J. Comb. 15 (2008), #R90.
  * [6] F. Curtis, _On formulas for the Frobenius number of a numerical semigroup_ , Math. Scand. 67 (1990), 190–192.
  * [7] G. Denham, _Short generating functions for some semigroup algebras_ , Electron. J. Comb. 10 (2003), #R36.
  * [8] A. L. Dulmage, N. S. Mendelsohn, _Gaps in the exponent set of primitive matrices_ , Illinois J. Math. 8 (1964), 642–656.
  * [9] D. Einstein, D. Lichtblau, A. Strzebonski, S. Wagon, _Frobenius numbers by lattice point enumeration_ , Integers. 7 (2007), A15.
  * [10] T. C. Hu, M. L. Lenard, _Optimality of a Heuristic solution for a class of Knapsack problems_ , Operations Research. 24(1) (1976), 193–196.
  * [11] M. Hujter, _On the lowest value of the Frobenius number_ , Technical Report MN/31 Computer and Automation Inst., Hungarian Academy of Sciences. (1987).
  * [12] T. Komatsu, _Sylvester power and weighted sums on the Frobenius set in arithmetic progression_ , Discrete Appl. Math. 315 (2022), 110–126.
  * [13] T. Komatsu, _Sylvester sums on the Frobenius set in arithmetic progression_ , arXiv:2203.12238v1, (2022)
  * [14] T. Komatsu, _Sylvester sum on the Frobenius set in arithmetic progression with initial gaps_ , Advances in Number Theory and Applied Analysis, (2023).
  * [15] F. Liu, G. Xin, _On Frobenius formulas of power sequences_ , arXiv:2210.02722, (2022).
  * [16] F. Liu, G. Xin, _A combinatorial approach to Frobenius numbers of some special sequences (Complete Version)_ , arXiv:2303.07149. (2023).
  * [17] M. J. Magazine, G. L. Nemhauser, L. E. Trotter Jr, _When the greedy solution solves a class of Knapsack problems_ , Operations Research. 23(2) (1975), 207–217.
  * [18] J. L. Ramírez Alfonsín, _The Diophantine Frobenius Problem_ , Oxford Lecture Series in Mathematics and Its Applications, vol. 30, Oxford University Press. (2005).
  * [19] J. B. Roberts, _Note on linear forms_ , Proc. Amer. Math. Soc. 7 (1956), 465–469.
  * [20] A. M. Robles-Pérez, J. C. Rosales, _The Frobenius number for sequences of triangular and tetrahedral numbers_ , J. Number Theory. 186 (2018), 473–492.
  * [21] Ö. J. Rödseth, _On a linear diophantine problem of Frobenius II_ , J. Reine Angew Math. 307/308 (1979) 431–440.
  * [22] J. C. Rosales, P. A. García-Sánchez, _Numerical Semigroups_ , Developments in Mathematics. Vol.20, Springer, New York (2009).
  * [23] E. S. Selmer, _On the linear Diophantine problem of Frobenius_ , J. Reine Angew. Math. 293/294 (1977), 1–17.
  * [24] J. J. Sylvester, _On sub-invariants, i.e., semi-invariants to binary quanties of an unlimited order_ , Amer. J. Math. 5 (1882), 119–136.
  * [25] A. Tripathi, _The Frobenius problem for modified arithmetic progressions_ , J. Integer Seq. 16(7) (2013), 13.7.4.
  * [26] A. Tripathi, _On the Frobenius problem for $\\{a,ha+d,ha+bd,ha+b^{2}d,…,ha+b^{k}d\\}$_, J. Number Theory. 162 (2016), 212–223.
  * [27] A. Tripathi, _Formulate for the Frobenius number in three variables_ , J. Number Theory. 170 (2017), 368–389.


# Reliable Deep Learning based Localization with CSI Fingerprints and Multiple
Base Stations

Anastasios Foliadis12, Mario H. Castañeda Garcia1, Richard A. Stirling-
Gallacher1, Reiner S. Thomä2  1Munich Research Center, Huawei Technologies
Duesseldorf GmbH, Munich, Germany
2Electronic Measurements and Signal Processing, Technische Universität
Ilmenau, Ilmenau, Germany
{anastasios.foliadis, mario.castaneda<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Deep learning (DL) methods have been recently proposed for user equipment (UE)
localization in wireless communication networks, based on the channel state
information (CSI) between a UE and each base station (BS) in the uplink. With
the CSI from the available BSs, UE localization can be performed in different
ways. One the one hand, a single neural network (NN) can be trained for the UE
localization by considering the CSI from all the available BSs as one overall
fingerprint of the user’s location. On the other hand, the CSI at each BS can
be used to obtain an estimate of the UE’s position with a separate NN at each
BS, and then the position estimates of all BSs are combined to obtain an
overall estimate of the UE position. In this work, we show that UE
localization with the latter approach can achieve a higher positioning
accuracy. We propose to consider the uncertainty in the UE localization at
each BS, such that overall UE’s position is determined by combining the
position estimates of the different BSs based on the uncertainty at each BS.
With this approach, a more reliable position estimate can be obtained in case
of variations in the channel.

###### Index Terms:

Localization, Deep Learning, Neural Network, Uncertainty, Dropout, Ensemble,
Early Fusion, Late Fusion

##  I Introduction

Interest in user positioning has grown significantly in the past few years due
to the increasing demand of applications requiring accurate location
information of the user equipment (UE). The precise location information can
additionally aid and improve the performance of the current (5G mobile
network) and of future communication networks.

User positioning is particularly required in dense urban environments and
indoors where the Global Navigation Satellite System (GNSS) is not available.
In such areas, the use of wireless communication networks like 5G can be
considered for positioning. One of the benefits of 5G networks over previous
standards is the support of multiple antennas and mm-Wave frequencies with
large available bandwidths, which can be leveraged for positioning.

Furthermore the ability to collect large amounts of data makes Deep Learning
(DL) based solutions an attractive possibility. DL based localization in
wireless networks has shown promising results achieving a sub-centimeter
accuracy in some indoor scenarios [1] [2]. The idea behind these approaches is
that the channel state information (CSI) between the UE and a base station
(BS) is considered a fingerprint of the user’s location. A neural network (NN)
can be trained on a database of uplink CSI fingerprints with their respective
UE’s location label, such that the NN can later be used for mapping the CSI of
a UE to the UE’s position.

In the uplink of a communication network, several BSs may be able to measure
the CSI of a UE. With the CSI from the available BSs, the UE localization can
be performed with an early fusion or late fusion approach. In early fusion,
the combined CSI of all the multiple BSs is considered as a single fingerprint
that is used as input of a DL model trained for the UE localization. In late
fusion, the CSI of each BS is taken as an input of a separate DL model, to
obtain an estimate of the UE position at each BS. Afterwards, the position
estimates of all BSs are combined to obtain an overall estimate of the UE
position. For DL based applications, there is no conclusive evidence as to
which type of fusion is better [3], as this is usually problem dependent.

Although typically DL techniques do not provide any information about the
reliability of their estimation, there exist techniques that are able to
address this issue. The authors of [4] use a late fusion approach with a
probabilistic description of the NN’s output which contains information about
the reliability of the estimation. An uncertainty quantification technique
that is based on variational autoencoders (VAE) is used in [5] to determine
the reliability of the estimations. Other simpler techniques to compute the
uncertainty of the estimation include Monte Carlo Dropout (MCD) [6] and deep
ensembles (DE) [7]. DE are based on the observation that when the estimations
of multiple DL models (i.e. multiple NNs) differ significantly then the
estimation is unreliable. MCD is based on a similar idea as explained in [6].

In this work, we show that UE localization with late fusion achieves a higher
positioning accuracy compared to early fusion. We propose to have a separate
DL model to estimate the UE position at each BS and to estimate the
uncertainty of each DL model with the given CSI. The UE’s position is then
obtained by combining the estimates of the different BSs while taking into
account the uncertainty at each BS. In general, the BSs with the most reliable
estimates have a larger impact on determining the UE’s position. We also show
that with our proposed approach, a more reliable position estimate can be
obtained in case of variations in the channel. We model the channel variations
with a random blockage of the line of sight (LOS) path of the channel between
the UE and a BS.

The paper is structured as follows. In section II the considered system model
is described and the late and early fusion approaches are introduced. In
section III the uncertainty estimation methods are explained and in section IV
we describe the simulation setup along with the NN structure. The results and
conclusion are then presented in sections V and VI respectively.

##  II System Model

###  II-A System Model

We consider an uplink setup with $N_{B}$ BSs each with $N_{R}$ Rx antennas and
a single Tx antenna at the UE. The UE transmits a reference signal on $N_{C}$
subcarriers within an orthogonal frequency division multiplexing (OFDM)
symbol. The transmitted reference signal that is received at a BS, is used to
estimate the CSI between the UE and the BS. We assume that each of the $N_{B}$
BSs can estimate the channel from the UE. The estimated CSI between the $n$-th
BS and the UE can be described as:

Figure 1: Early Fusion Block Diagram

$\boldsymbol{H}^{n}=[\boldsymbol{h}_{0}^{n},\boldsymbol{h}_{1}^{n},...,\boldsymbol{h}_{N_{C}-1}^{n}]\in\mathbb{C}^{N_{C}\times
N_{R}},$ (1)

where $\boldsymbol{h}^{n}_{m}\in\mathbb{C}^{N_{R}}$ is the vector with the
estimated uplink channels between the UE and the $N_{R}$ antennas at the
$n$-th BS and at $m$-th subcarrier. The estimated channel $\boldsymbol{H}^{n}$
depends on the multipath between transmitter and receiver and it could be
considered a distinct fingerprint of the position of the UE. The CSI
fingerprints are processed before being inputted to the DL model, mainly due
to the fact that they need to be represented by real values at the input of
the NN. We denote the processed fingerprint input as
$\tilde{\boldsymbol{H}}^{n}$

###  II-B DL Based Positioning with Fingerprints

Deep learning based localization using fingerprint inputs of the environment
is generally divided into two phases. During the first phase, referred to as
training phase, the measurements $\boldsymbol{H}$ that constitute the
fingerprints are gathered and stored into a database along with their
respective $D$-dimensional position label $\boldsymbol{p}\in\mathbb{R}^{D}$.
The data are then used as training inputs to a DL model which learns to map
the measurement to the position label. During the second phase, the testing
phase, every subsequent CSI measurement is passed onto the DL model, which
predicts the location. The DL model $f(\boldsymbol{H})=\tilde{\boldsymbol{p}}$
is trained to minimize the mean squared error (MSE) between the position label
and the estimated position $\tilde{\boldsymbol{p}}$:

$L(\theta)=\frac{1}{D}\sum_{d=1}^{D}|\boldsymbol{p}_{d}-\tilde{\boldsymbol{p}}_{d}|^{2}$
(2)

with respect to the DL model parameters $\theta$.

###  II-C Late and Early Fusion

Figure 2: Late Fusion Block Diagram

With the CSI of a UE available at multiple BSs, there is the choice between
late and early fusion, for performing the UE localization. In early fusion,
the preprocessed CSI matrices of all the $N_{B}$ BSs are concatenated into a
single fingerprint
$[\tilde{\boldsymbol{H}}^{1},\tilde{\boldsymbol{H}}^{2},...,\tilde{\boldsymbol{H}}^{N_{B}}]$
that is used as input of a single DL model
$f([\tilde{\boldsymbol{H}}^{1},\tilde{\boldsymbol{H}}^{2},...,\tilde{\boldsymbol{H}}^{N_{B}}])$.
Based on a database of such fingerprints for different UE positions, the DL
model is trained to determine the UE’s position. Thus, we have that
$f([\tilde{\boldsymbol{H}}^{1},\tilde{\boldsymbol{H}}^{2},...,\tilde{\boldsymbol{H}}^{N_{B}}])=\tilde{\boldsymbol{p}}\in\mathbb{R}^{D}$.
A block diagram of early fusion is shown on Fig. 1.

For late fusion, the preprocessed CSI matrix $\tilde{\boldsymbol{H}}^{n}$ of
the $n$-th BS is taken as input of a DL model
$f^{n}(\tilde{\boldsymbol{H}}^{n})$ and is used to obtain an estimate
$\tilde{\boldsymbol{p}}^{n}$ of the UE position ${\boldsymbol{p}}$ at each BS,
i.e. $f^{n}(\tilde{\boldsymbol{H}}^{n})=\tilde{\boldsymbol{p}}^{n}$. The DL
model at each BS is trained based on a database of preprocessed CSI from that
BS for different UE positions. Afterwards, the position estimates of all BSs
are combined to obtain an estimate of the UE position ${\boldsymbol{p}}^{n}$.
A simple visualization of the late fusion approach is given in Fig. 2. Since
the combination of the predictions from multiple models is performed at the
decision stage, this type of data fusion is called late fusion.

The most straight-forward way to combine the $N_{B}$ different estimates is
using a weighted average for each element $d\in[0,...,D-1]$ of the output
vector with weights $W_{d}=[w_{d,1},w_{d,2},...,w_{d,N}]$ resulting in:

$\tilde{{p}_{d}}=\frac{\sum_{n=1}^{N_{B}}w_{d,n}\tilde{{p}_{d}}^{n}}{\sum_{n=1}^{N_{B}}w_{d,n}}.$
(3)

When $w_{d,1}=w_{d,2}=...=w_{d,N}$, this results in an ordinary average of the
position estimates. Even though this method has shown promising results in
some occasions [2], it may not be robust to environmental changes. To create a
more robust model we propose to determine the weights based on the uncertainty
information. The least certain models should be weighted less and vice-versa.

It should be noted here that from implementation perspective, late fusion has
the advantage that it can be implemented both as a distributed scheme as well
as centrally processed scheme. The disadvantage of a centrally processed
scheme is that a large amount of data has to be transmitted from the BSs to
the central location server. This downside is always present in the early
fusion approach and hence one may have to resort to compression techniques if
this approach is used.

##  III Uncertainty Estimation

For UE localization based on CSI fingerprints, it is expected that for a UE at
a given position, the CSI measured during the training phase and the testing
phase are similar. However, the CSI between the two phases can differ
considerably due to variations in the wireless channel. Movement of objects in
the environment can cause a scatterer to change position or a path to be
blocked, e.g. the LOS path can be blocked.

We propose to address this issue by using the late fusion approach, i.e. by
using a separate DL model at each BS. Furthermore, by adding uncertainty
quantification techniques at each model, the uncertainty in the UE
localization with the CSI at that BS can be estimated. If there is a change in
the CSI for a given UE position at a BS (compared to the training phase), the
proposed approach could report a low certainty. By applying such approach at
each BS, the uncertainty estimation will provide information about the
certainty that each BS has about its position estimate.

Uncertainty estimation with early fusion is also possible to determine whether
an estimate of the UE’s position is reliable or not. This is in contrast to
uncertainty estimation with late fusion where an estimate may be still be
possible even if the estimations from some BSs are unreliable.

###  III-A Aleatoric Uncertainty

There are two main sources of uncertainty, which are called epistemic and
aleatoric uncertainty [8]. Aleatoric uncertainty refers to the uncertainty
which is inherent in the data such as noise or additionally in the case of DL-
based UE localization due to indistinguishable fingerprints.

Aleatoric uncertainty can be further separated into two kinds: homoscedastic
aleatoric uncertainty and heteroscedastic aleatoric uncertainty. The former
describes uncertainty which is constant regardless of the input to the NN,
i.e. every input exhibits the same amount of noise. Heteroscedastic
uncertainty on the other hand is input dependent, meaning that some inputs
contain less information about the output than others. In the context of DL
localization this could be due to variable path loss, which depends on the
distance between UE and BS, or on insufficient information from the multipath.

For the task of localization using CSI fingeprints, the noise affects each
input differently, therefore in this scenario the heteroscedastic aleatoric
uncertainty needs to be considered. Since aleatoric uncertainty is data
dependent the loss function $L(\theta)$ has to be modified to include the
uncertainty of the $d$-th output component in the position estimate. The
uncertainty is given by $s_{d}=\log(\sigma_{d}^{2})$, where $\sigma_{d}^{2}$
is the variance of $d$-th component of the position estimate. In this way, the
NN learns which data provide less information [8]. The modified loss function
is given by:

$L^{\prime}(\theta)=\frac{1}{2D}\sum_{d=1}^{D}\exp(-s_{d})|\boldsymbol{p}_{d}-\tilde{\boldsymbol{p}}_{d}|^{2}+s_{d}.$
(4)

The loss function consists of two components. The first term is a regression
term which increases the uncertainty $s_{d}$ when the MSE becomes larger, i.e.
when there is insufficient information at the input sample, and the last term
is a regularization term which limits an infinite increase of the loss
function. Subsequently the model output is expanded to include the uncertainty
$\boldsymbol{s}\in\mathbb{R}^{D}$ as well, i.e.
$f(\tilde{\boldsymbol{H}})=[\tilde{\boldsymbol{p}},\boldsymbol{s}]$, where
$\boldsymbol{s}=[s_{1},s_{2},...,s_{D}]$.

###  III-B Epistemic Uncertainty

Epistemic uncertainty refers to the uncertainty that the model experiences due
to insufficient training data. For example a DL localization model would
exhibit high epistemic uncertainty for a region in space where no fingerprints
where collected. It can be useful to identify some change in the measured CSI,
which would indicate a change in the environment.

####  III-B1 Monte Carlo Dropout (MCD)

One way to capture the epistemic uncertainty of the model is the MCD
technique. It is a practical approach to obtain Bayesian approximation of the
model posterior distribution. When using dropout, individual neurons of every
weight layer of the DL model are removed with probability $p$. Normally,
dropout is applied only during training but with MC dropout, the same dropout
probability is retained also during testing. Effectively each forward pass
through the NN results in a new configuration (since different neurons are
dropped) and performing multiple forward passes is equivalent to sampling from
the approximate posterior distribution of the model parameters given the
dataset [6]. The variance of the estimates from the different NN
configurations of each of the forward passes is a measure of the uncertainty.

Finally, after $T$ forward passes, the combined aleatoric and epistemic
uncertainty for the $d$-th component of the position estimate of the $n$-th
model can be calculated as [8]:

$(\sigma_{MC,d}^{n})^{2}\approx\frac{1}{T}\sum_{t=1}^{T}\left(\tilde{\boldsymbol{p}}_{t,d}^{n}\right)^{2}-\left(\frac{1}{T}\sum_{t=1}^{T}\tilde{\boldsymbol{p}}_{t,d}^{n}\right)^{2}+\frac{1}{T}\sum_{t=1}^{T}\exp(s_{t,d}^{n})$
(5)

where $t$ indicates the current forward pass. The last term represents the
aleatoric uncertainty, while the first two terms are used to compute the
variance of the estimates from the $T$ forward passes. Having this measure of
uncertainty, the weighted average for late fusion can by calculated by setting
$w_{d,n}=1/(\sigma_{MC,d}^{n})^{2}$ in (3).

####  III-B2 Deep Ensemble (DE)

One other approach to estimate uncertainty is the use of DE. An ensemble of
NNs is a set of models which are trained for the same task. The individual
models are then combined to achieve a better estimation. They consistently
outperform single NNs particularly when there is diversity between the models
[2]. In a DL setting, diversity can be achieved by the randomly initialized
weights of the NN, by modifying the hyperparameters of the algorithm or by
varying the training data.

For UE localization with multiple BSs each BS observes a different CSI for a
UE position and hence, the training data available at each BS is different.
Thus, in the case of late fusion, we obtain different models simply by
training them on the different training data sets from the $N_{B}$ BSs. The
different models would form an ensemble of NNs, whose outputs are combined to
provide an estimate of the UE position.

With the $N_{B}$ trained models, we propose to group the BSs into $N_{B}$ sets
each with $N_{B}-1$ BSs, i.e. in each set one BS is excluded. We define the
$n$-th set as $S_{n}=\\{i\quad|i\in[1,...,N_{B}]\backslash\\{n\\}\\}$. We can
obtain a different ensemble of $N_{B}-1$ NNs by considering the CSI from the
BSs within each set $S_{n}$. For each of those sets, and by including the
aleatoric uncertainty, the variance of the $N_{B}-1$ position estimates from
the BSs within the set is computed as [7]:

$(\sigma_{E,d}^{n})^{2}=\sum_{i\in
S_{n}}\left(\tilde{\boldsymbol{p}_{d}}^{i}\right)^{2}-\left(\sum_{i\in
S_{n}}\tilde{\boldsymbol{p}_{d}}^{i}\right)^{2}+\sum_{i\in
S_{n}}\left(\sigma_{d}^{i}\right)^{2}.$ (6)

This variance can be thought of as the uncertainty of that particular set
which excludes the estimation of the model $n$. For this reason we consider
the variance $(\sigma_{E,d}^{n})^{2}$ divided by the sum of the variances of
all other $N_{B}-1$ sets as a measure of the certainty of the model $n$. Thus,
for the DE approach we set the weights of (3) of the late fusion equal to

$w_{d,n}=\frac{(\sigma_{E,d}^{n})^{2}}{\sum\limits_{i\in[1,...,N_{B}]\backslash\\{n\\}}(\sigma_{E,d}^{i})^{2}}$
(7)

The reasoning behind this measure, is that if the uncertainty of one set is
high compared to all other sets then this means that the excluded BS from that
set is the most certain. The opposite is also true. By setting the weight as
in eq. (7) then we are determining the most certain BSs, by essentially
comparing the uncertainties of the sets.

##  IV Simulation Setup

###  IV-A Database Description

To compare the early fusion and the late fusion approaches, along with the
proposed uncertainty estimation, we used ray-tracing dataset called DeepMIMO
[9]. With the DeepMIMO dataset, the user can define different channel
parameters and simulate a propagation scenario from a UE at a given location
to several BSs in an outdoor scenario. The channel including the path loss is
then generated using accurate ray-tracing data.

For our evaluations, we consider only one segement of a street within the
urban outdoor scenario from the DeepMIMO dataset. Namely, we consider the
street with $N_{B}=6$ BSs as depicted in Fig. 3. Each BS has a uniform linear
array (ULA) in the azimuth plane with $N_{R}=16$ antennas and a half
wavelength spacing between adjacent antenna elements. The area of the
considered scenario is $200\times 36\text{m}^{2}$. The carrier frequency of
this scenario is $f_{c}=3.5\text{GHz}$ and we assume that the bandwidth was
set at $BW=80\text{MHz}$. The number of subcarriers was set at $1024$. We
assume the reference signal is transmitted on every 10th subcarrier,
whichresults in a CSI fingerprint of $N_{C}=103$ subcarriers. We also assume
that the UE’s transmit power is 23 dBm, the noise floor is -174 dBm/Hz and the
receiver’s noise figure is 2 dB.

As already mentioned, in a real environment, the CSI fingerprint at a given UE
location may change due to variations in the wireless channel, i.e. movement
of objects or scatterers, or blockage of a path due to obstacles. We model the
changes in the channel by assuming that the LOS path in the channel between a
UE and a BS can be blocked with a given probability. The blockage probability
of the LOS path usually increases as the distance between the BS and UE
increases, as discussed in [10]. Based on this, we assume that the LOS is
blocked according to the LOS blockage probability in the warehouse scenario in
[10], which is given by:

$P_{NLOS}=1-\exp\left(-\frac{r\log(1-0.05)}{10}\right),$ (8)

where $r$ is the distance between the UE and the BS.

Even though the simulated ray-tracing scenario is an outdoor setting, we
believe that the blockage probability for the LOS path in the warehouse
scenario as described by [10] better captures our intended simulation
environment, i.e. people or objects causing signal blockage.

###  IV-B Neural Network Setup

Figure 3: Early Fusion Block Diagram

We consider a convolutional neural network (CNN) with two convolutional layers
and two max pooling layers followed by three dense layers as shown in Fig. 4 .
The input of the CNN, which is the measured CSI
$\boldsymbol{H}^{n}\in\mathbb{C}^{N_{R}\times N_{C}}$, is processed using the
phase difference between the antennas as described in [1], to resolve any
timing errors between UE and each BS. This results in a real $3$-dimensional
matrix, i.e $\tilde{\boldsymbol{H}}^{n}\in\mathbb{R}^{N_{R}\times N_{C}\times
3}$, where the third dimension consists of the magnitude and the sine and
cosine of the phase difference between adjacent antennas as separate stacked
2D matrices. The two convolutional layers of the NN contain 32 different
kernels with dimensions $4\times 4$ and the dimension of the max pooling
layers is $4\times 1$, only pooling the subcarrier dimension. The outputs of
the second pooling layer are vectorized and inputted into 3 dense layers of
128 neurons each with the rectified linear unit as their activation function.
A last dense layer with 2 neurons is at the output, with no activation
function. Before every dense layer there is a dropout layer with dropout
probability $p_{d}=0.2$. The same NN structure is considered for both early
and late fusion by simply changing the input dimension to correspond to the
considered fingerprint.

The NNs were trained with a batch size of 32 and 64, each for 1000 epochs. The
loss function used for training is the one described in Eq. (4). The training
set was $80\%$ of the database, while the other $20\%$ was used for the
testing. All the input data are normalized in the range $[0,1]$. For the
evaluation of the different schemes, we consider the mean error (ME) of the UE
positioning, given by the Euclidean distance between the estimated postion and
the true position of a UE in the test set.

Figure 4: Neural Network Model

##  V Simulation Results

Based on the setup described in Sec. IV-A and Fig. 3, we consider two
scenarios for the simulation results: a static scenario and a dynamic
scenario. For the static scenario, there is no change in the channel between
the training phase and the test phase, while for the dynamic scenario there
can be a change in the channel between the two phases. For the training phase
in both scenarios and also for the testing phase in the static scenario, CSI
samples for UE positions are taken within the area depicted in Fig. 3, with a
LOS and multipath between each UE position and each BS according to the
DeepMIMO dataset. However, for the testing phase in the dynamic scenario, the
CSI samples are taken assuming that the LOS path to a BS can be blocked
according to the probability given in (8). If this is the case, the LOS path
is simply removed from the channel generated from the DeepMIMO dataset.

TABLE I: Performance with Separate NNs | BS1 | BS2 | BS3 | BS4 | BS5 | BS6
---|---|---|---|---|---|---
Static ME (m) | 2.9227 | 2.8422 | 2.6561 | 2.3191 | 2.5918 | 2.6686
Dynamic ME (m) | 5.5495 | 5.9869 | 3.9249 | 3.7786 | 4.7347 | 4.9414
TABLE II: Performance with Data Fusion | Early Fusion | Late Fusion
---|---|---
| Average | MCD | DE
Static ME (m) | 1.7532 | 1.4137 | 1.2431 | 1.2777
Dynamic ME (m) | 2.5116 | 3.0578 | 1.9864 | 1.9262

We see the results for the NNs trained on each of the 6 BSs in Table I. As
expected the performance of the UE localization at each BS deteriorates when
going from the static scenario to the dynamic scenario, as the CSI in test
data may differ from the CSI in the training data. The variations in the
performance of the separate NNs for each BSs, may result from the different
building layout along the street.

On Table II we see the results for the different data fusion approaches. First
it is interesting to see that in a static environment, the early fusion is
outperformed by the late fusion approaches, including the simple approach with
equal weighting. For late fusion, we consider the combining in (3) with
different weighting, namely: equal weighting (averaging) and weighting based
on the MCD and DE approaches discussed in Sec. III-B. For the static scenario,
it is more beneficial to combine different position estimates from the BSs,
instead of considering one larger CSI fingerprint for the UE localization.
Among the late fusion approaches, better performance is observed with
weighting based on uncertainty estimation, even though there are no changes in
the channel.

On the other hand, when considering the dynamic scenario, early fusion
outperforms late fusion with simple averaging, which implies that the former
is more robust to changes in the channel. In this case, the larger CSI
fingerprint in early fusion is beneficial, as a channel change at one or two
BSs only impacts portions of the large CSI fingerprint, which may allow the NN
to still obtain an estimate of the UE position. In case of late fusion with
simple averaging, a channel change at one BS may lead to a very poor estimate
of the UE position from that BS. Such poor estimate can then dominate the
average when combining the estimates from other BSs.

However, the situation changes when using weights based on uncertainty
estimation. With MCD or DE weighting, late fusion outperforms the early fusion
in the dynamic scenario. With uncertainty estimation, the BSs that have
experienced a channel change have a smaller weight. Hence, their estimate of
the UE position would have a reduced impact for the combination when
determining the overall UE’s position.

Both in the static and the dynamic environment the error becomes smaller when
also considering the uncertainty of each model as described in section III-B.
This makes sense as with uncertainty estimation it is possible to identify
which of the models experiences some environmental change. MCD weighting shows
slightly better performance in a static environment while the opposite is true
for DE weighting.

We finally evaluate the impact of the number of BSs on the different fusion
approaches for the static and dynamic scenario in Fig. 5 and 6, respectively.
The BSs that are considered are selected based on increasing indices, i.e. for
3 BSs, BS 1, BS 2 and BS 3 from Fig. 3 are selected. Based on the description
in Sec. III.B, late fusion with DE weighting needs at least 3 BSs to compute
the certainty. For only one BS, early fusion, simply averaging and using MCD
weighting is exactly the same, although with only 2 BSs the uncertainty
estimation in the MCD weighting is already beneficial for both static and
dynamic scenarios. In the static scenario, MCD weighting is slightly better
than DE weighting for different number of BSs. In the dynamic scenario,
however, DE weighting outperforms MCD weighting, with a larger gap for smaller
number of BSs. This indicates that the DE weighting is better at identifying
the epistemic uncertainty which is higher in the dynamic scenario. Lastly, we
see that early fusion is more robust to variations in the channel compared to
late fusion with simple averaging, regardless of the number of BSs.

##  VI Conclusion

We compared UE localization with multiple BSs using early fusion and late
fusion, and showed that the late fusion achieves a higher positioning
accuracy. We propose to have a separate DL model to estimate the UE position
at each BS and to estimate the uncertainty of each DL model with the given
CSI. Afterwards, the UE’s position is determined by combining the estimates of
the different BS while taking into account the uncertainty at each BS.
Simulations results confirm that our proposed approach is able to deliver a
more reliable position estimate even when considering variations in the
channel.

Figure 5: Error of data fusion techniques on static scenario Figure 6: Error
of data fusion techniques on dynamic scenario

## References

  * [1] A. Foliadis, M. García, R. Stirling-Gallacher, and R. Thomä, “CSI-based localization with CNNs exploiting phase information,” _2021 IEEE Wireless Communications and Networking Conference (WCNC)_ , pp. 1–6, 2021.
  * [2] A. Sobehy, É. Renault, and P. Mühlethaler, “CSI based indoor localization using ensemble neural networks,” in _MLN_ , 2019.
  * [3] D. Ramachandram and G. W. Taylor, “Deep multimodal learning: A survey on recent advances and trends,” _IEEE Signal Processing Magazine_ , vol. 34, pp. 96–108, 2017.
  * [4] E. Gönültaş, E. Lei, J. Langerman, H. Huang, and C. Studer, “CSI-based multi-antenna and multi-point indoor positioning using probability fusion,” _ArXiv_ , vol. abs/2009.02798, 2020.
  * [5] M. Stahlke, S. Kram, F. Ott, T. Feigl, and C. Mutschler, “Estimating TOA reliability with variational autoencoders,” _IEEE Sensors Journal_ , pp. 1–1, 2021.
  * [6] Y. Gal and Z. Ghahramani, “Dropout as a bayesian approximation: Representing model uncertainty in deep learning,” _ArXiv_ , vol. abs/1506.02142, 2016\.
  * [7] B. Lakshminarayanan, A. Pritzel, and C. Blundell, “Simple and scalable predictive uncertainty estimation using deep ensembles,” in _NIPS_ , 2017\.
  * [8] A. Kendall and Y. Gal, “What uncertainties do we need in bayesian deep learning for computer vision?” in _NIPS_ , 2017.
  * [9] A. Alkhateeb, “DeepMIMO: A generic deep learning dataset for millimeter wave and massive MIMO applications,” _ArXiv_ , vol. abs/1902.06435, 2019.
  * [10] 3GPP, “Study on channel model for frequencies from 0.5 to 100 GHz,” 3rd Generation Partnership Project (3GPP), Technical Specification (TS) 38.901, 1 2020, version 16.1.0.