# Covid-19 Spread Detection and Controlling with Fog-based Infection
Probability Evaluation Model

Suraj Mahawar, and Ajay Pratap S. Mahawar and A. Pratap are with the
Department of Computer Science and Engineering, Indian Institute of Technology
(Banaras Hindu University) Varanasi 221005 India. E-mail:
{suraj.mahawar.cse19<EMAIL_ADDRESS>
###### Abstract

COVID-19 has created a pandemic around the world, paused the path of building
the future, and still ongoing without having any long-term solution shortly.
The time taken in vaccine distribution is too slow compared to the spread of
COVID-19. Hence, it is important to aware and take precautions on time without
delaying and waiting for long-duration after getting infected with the virus.
Currently used technology is more advanced than ever before. Almost everyone
has access to at least one mobile device with an Internet connection.
Therefore, we propose a Fog Server (FS) based system that can be used to
create awareness about the spread of COVID-19 within the surroundings of
individuals utilizing the concept of Hidden Markov Models (HMM) and Bluetooth
contact tracing, in polynomial computational time complexity. Moreover, we
evaluate the effectiveness of the proposed model through real-world data
analysis on different simulation parameter settings.

###### Index Terms:

COVID-19 Identification, Pandemic, Fog Server, HMM, Probability.

##  I Introduction

The COVID-19 disease started to spread in 2019 and has spread to over 180
countries. Some countries are facing the second wave of the virus spread right
now. As of the 18th May 2021, a total of 164,355,605 cases and 3,406,601
deaths were reported [1]. The virus spreads through respiratory droplets or
air from one person to another. These droplets spread when an infected person
sneezes, coughs, or speaks to one or many. Infection can also spread if a
person touches a contaminated surface and then eyes, nose, or mouth. Most
common symptoms of COVID-19 include fever, dry cough, tiredness etc. If the
lungs get completely infected the chances of death become high.

The COVID-19 is an infectious disease caused by the coronavirus which is a
group of Ribonucleic Acid (RNA) viruses. Many people, if gather at places
tends to get infected with COVID-19 in a short time and can experience
respiratory illness and possibly recover without the need for special
treatment. Elderly people tend to have more impact on COVID-19 as they have
weaker immune systems and most have underlying medical problems such as
diabetes, cancer and some other respiratory-related diseases. These medical
problems can develop more weakness and increase the sickness along with
COVID-19. It is known that COVID-19 affects different people in different
ways, most people who are infected will develop illness and possibly recover
without any special medication treatment. It is observed that fever, dry
cough, and tiredness are the most common symptoms among infected people and
symptoms like pains, soreness throat, diarrhea, dizziness, headache, loss of
taste and smell, rashes over the skin are less common among the infected
people. Serious symptoms are such as difficulty in breathing, chest pain, loss
of speech and few other symptoms can be noticed among the infected people. On
average it takes 2-14 days for the symptoms to show after meeting the infected
person [2]. Therefore early identification of an infected person is very
important to stop the further spread of the virus by imposing certain
measures.

With the help of Fog Servers (FS), our system will make people aware of their
health conditions and their surroundings [3]. Those who live in crowded areas
like urban cities, mostly have access to at least one mobile device with
internet, so it is possible to set up an application into their device to
track their movements and their contact with others using Bluetooth options.
It can be efficient to design an algorithm that works with this technology to
aware people from time to time. Thus, motivated by the above-mentioned
scenarios, this paper evolves the technique to create awareness among people
by using contact traced data and their data with an algorithm framework that
can find accurate results and track COVID-19 spread. We have designed the
spread of the COVID-19 virus phenomenon by applying Hidden Markov Model (HMM)
and Bluetooth contact tracing framework. This statistical tool is used for
modeling the generative sequences characterized by a set of observable
sequences. However, HMM framework is used to model all stochastic processes in
real time problems. In our proposed model, the non-observable state of the
system is controlled by a Markov process and the observable sequences of the
system have underlying probabilistic dependencies.

In the current situation of the COVID-19 pandemic, a solution is needed to
prevent and control virus spread. In this regard, the proposed framework can
be used to aware people of the COVID situation around them. In nutshell, the
main contributions of the work are summarised in the following:

  * •

FS to detect COVID-19 spread: An FS framework is used with HMM and Bluetooth
contact tracing enabled to track every individual user. Fog interacts with all
users and serves them with the best precautions and guidance needed as per the
user’s conditions.

  * •

Detect initial infected users: Exponential spread of virus needs a solution to
stop the spread in early stages. A chain starts from one user but may last up
to million users, which means breaking the chain initially will help control
virus spread. The proposed solution helps detecting initial infected users and
prevent them to meet others so that their contribution to virus spread can be
reduced.

  * •

Evaluate individual’s infection probability: Evaluation of individual’s
infection probability as well as risk levels. Probability helps identifying
the user’s status if a user is allowed to get in touch with others or not.
Risk levels help creating health reports of users containing the best
precautions needed and all necessary guidance from health exports according to
the user’s conditions.

  * •

Future prediction: Future prediction is done with current data based on
_meetups_ , fixed thresholds of time of contact, Bluetooth signal strength and
threshold infection probability, which helps to get prepared for future
conditions in advance and to fight against the virus with pre-planned
strategies.

The rest of the paper is organized as follows: Section II reviews the relevant
work. The system model and the problem definition are introduced in Sections
III. The proposed solution and performance study are given in Sections IV and
V, respectively. Finally, Section VI offers conclusions and future research
directions.

##  II Related Works

Recently researchers at SMU have come up with a ’Lab on a Chip’ test which can
identify COVID-19 immune response faster than current antibody tests [4]. When
someone gets infected, his body produces some antibodies to fight the virus,
in that case, if these antibodies are present, it means that the person is
infected with virus. This test is done by applying a blood drop to a micro-
fluid chip and once applied a filter embedded in that chip extracts plasma
from the sample of blood. This chip is then placed in an electronic instrument
to detect the presence of specific antibodies in plasma. While the Defense
Advanced Research Projects Agency (DARPA) developed a microchip to detect
COVID-19 [5]. This microchip is used to constantly check an individual’s blood
for virus and once it detects COVID-19, it will alert the patient and the
patient is advised to go for a blood test to confirm if the virus is present
in the blood. But, it is hard to implant chips in everyone’s body. It can take
much time to do such operations. Thus, it is necessary to aware people of
their surroundings. People these days are carrying smartphones everywhere they
go and they use the internet which can be an opportunity for us in utilizing
the power of technology to aware of the COVID-19 situation. It is possible to
add an application into millions of mobile phones than implanting microchips
into million people. There are still many other kind of researches going on,
but taking advantage of technology, we would like to use mobile phones with
internet connection and Bluetooth contact tracing to identify whether a person
is infected with COVID-19 or not. Our method utilizes an algorithmic approach
and contact tracing mechanism. Bluetooth is used in contact tracing. FS
interacts with all users from time to time and serves them with the best
precautions and guidance needed as per the user’s conditions.

HMM [6] has been used in many fields and applications, such as speech
recognition, visual speech recognition, to identify contamination in water
networks [7], predicting traffic conditions [8], analyzing nosocomial
pathogens transmission [9], predicting transmembrane helices [10], analyzing
evolutionary rates in molecular sequences [11], etc. Contact tracing [12] can
drastically improve the analysis of the COVID-19 virus spread. It can tell
people if they come into contact with an infected person. Then the person can
quickly take action so that spread of the virus to their surroundings slows
down/stops. Contact tracing is very useful and is being used in controlling
infectious diseases [13], impact of delays on virus spread de-escalation
strategies [14], Bluetooth-based contact tracing [15], person-to-person
covid-19 tracing [16]. In the case of COVID-19, we have a hidden state and an
observable state in virus spread, thus, the use of HMM is a better approach in
finding COVID-19 spread.

##  III System Model and Problem Definition

To detect and control the spread of COVID-19, we use FSs which utilize
algorithms for detecting and controlling virus spread as well as prediction of
future conditions. We further consider use of contact tracing for monitoring
each user, that helps in predicting the chances of a user being infected with
COVID-19 so that necessary actions can be taken in advance like the government
imposing guidelines such as lockdown, strict use of masks or early
distribution of vaccines in those locations to prevent further spread of the
virus.

Figure 1: Fog based system model for COVID-19 spread identification.

The system model represented in Fig. 1 shows the mechanism of user data
collection, user-given data uploading, data computation, storing the results
and reporting, and further reporting the final results to the respective user
and cloud server. The whole procedure is described in three sub-processes as
follows:

  * •

Data collection and uploading to FS.

  * •

Data computation at FS.

  * •

Result analysis and reporting.

Details of the above-mentioned sub-processes are discussed in the following
sections:

####  III-1 Data collection and uploading to FS

Our first aim is to collect user-given data. Initially, our system model
registers a new user in the database with some identity as contact number, his
current location, age, etc. Now user is asked to fill in some healthcare
details, such as if the user has any symptoms related to COVID-19, if he had
traveled to other infected countries/places within the last two weeks, and if
user had any previous diseases. One more important input is the number of
infected users, a user gets in touch with. It’s obvious that a user can’t
predict whether the person near to him is infected with COVID-19 or not. In
such a situation the system model needs some better way to find out the number
of positive users, a person has got in touch with. Therefore, contact tracing
is the best solution here to trace a person. Thus, we use Bluetooth
connectivity for tracing other users near a particular user. When two persons
come in the range of Bluetooth connectivity, it is called a _meetup_. After a
meetup, both user’s devices connect and exchange some digital signatures. If
any one of them is COVID-19 positive, our model sends an alert message to the
user so that the user can get out of that particular location otherwise the
user can also be infected. Thus, in this way, user given data and contact
traced data are collected from users at the FS.

Figure 2: HMM model.

####  III-2 Data computation at FS

In this section, we compute the probability of infection by user-given data
and contact traced data. The spreading of the virus can be modeled as an
exponential problem as shown in Fig. 2, which shows two states $h(t_{1})$ and
$h(t_{2})$. Here state means scenario of virus spread at a particular time
slot. State $h(t_{1})$ shows spreading of virus on time slot containing time
$t_{1}$ and state $h(t_{2})$ shows further spreading of virus on time slot
containing time $t_{2}$. Fig. 2 contains a table having hidden state and
observed state named two states for each of $h(t_{1})$ and $h(t_{2})$ where
$H$ is a set of infected users and $O$ is a set of each user’s observations or
set of all user given data and contact traced data. It is obvious that future
conditions depend only on the current rate of virus spread and on the actions,
we take today to control it. So, we have an exponential problem with some
states and all the data (user-given data as well as contact tracing data) of
those states. Now, we need to work on the current state’s data and predict the
most probable next state and also to analyze the results and provide the
reports to users with all necessary precautions, medication and current
conditions of particular user. Hence, we need to formulate algorithms, which
work on user-given data as well as traced data to calculate probabilities of
users being infected. Since the model works on previous states with all of
their observed data (user given and traced data) and finds the most probable
next state, so we formulate this future prediction as an HMM inference
problem.

####  III-3 Result analysis and reporting

After computing the user given and contact traced data at FS, system upload
the results in a centralized cloud server for all users. After that, results
are analyzed and reports are generated for each user and are sent to
respective users. A report contains the risk level (in the form of low,
moderate, high, very high) of a user being infected, all necessary precautions
and medications based on user’s conditions. The results are containing the
probability of a user being infected which was computed at FS, contact traced
data, user’s previous diseases and current symptoms.

##  IV Proposed Solution

As discussed in the above subsection III-2, we use HMM modeling the problem.
In order to achieve that, let there be $N$ users represented using a set
$\mathbb{U}=\\{U_{1},\cdots,U_{N}\\}$. Further, we define three sets as
follows: The first set having $M$ users represented in a set of infected users
$\mathbb{I}=\\{I_{1},\cdots,I_{M}\\}$ which contains all the users having
probability more than some threshold probability value $\Theta$ or have been
tested positive and second one is a set of the traced number of users
$\mathbb{T}=\\{T_{1},\cdots,T_{N}\\}$ where $T_{n}$ means $n^{th}$ user
$U_{n}$ has met $T_{n}$ number of users with some infection probability till
time $t$ or in other words, user $U_{n}$ had $T_{n}$ number of _meetups_ with
other infected users and the third one is set of symptom status
$\mathbb{S}=\\{S_{1},\cdots,S_{N}\\}$ where $S_{n}$ $\in$ $\\{0,1\\}$, which
means if $n^{th}$ user $U_{n}$ is having any virus related serious symptoms,
then $S_{n}=1$ otherwise $S_{n}=0$. All of these sets may change their data
according to the changes in time/states.

The proposed algorithmic solution is divided into three parts as follows:

  * •

Probability calculation with contact traced data.

  * •

Probability calculation with user’s symptoms and evaluating total probability
of infection.

  * •

Result analysis and reporting to users and cloud.

Figure 3: Probability calculations.

####  IV-1 Probability calculation with contact traced data.

In this part, we aim to compute the probability of each user according to the
previous state’s results and current state’s traced data. The basic idea and
derivation of the equations are described with help of one example below.

An illustrative example: As given in Fig. 3, there is a non-infected user
$U_{i}$ and three infected users $U_{1}$, $U_{2}$, $U_{5}$ with probability of
more than some fixed threshold value $\Theta$. When user $U_{i}$ gets in touch
with user $U_{1}$, then $U_{i}$ gains some probability, and if $U_{i}$ meets
$U_{2}$, then also $U_{i}$ gets some more probability and so on. For further
calculation, let probabilities of infection of users $U_{1}$, $U_{2}$, $U_{5}$
be $p_{1}$, $p_{2}$, $p_{5}$, respectively. Now, we aim to find that how much
part of these probabilities should be added to the probability of user
$U_{i}$. An optimal solution to this problem should be a variable that is
dependent on several conditions like time for which two devices get connected
($\tau$), connection strength ($\nu$) (to get the space between two users
based on signal strength), and some more measurements can also be used. For
having an ideal solution and assuming ideal conditions, we use time of contact
($\tau$) and signal strength ($\nu$) as variables to define $\mu$, which would
be called infection transition fraction and value of $\mu$ increases as the
time of contact and signal strength increases. So, let
$\mu_{i}(t)=\\{\mu_{1},\mu_{2},\mu_{5}\\}$, part of their probability is added
to $U_{i}$, where $0\leq\mu\leq 1$ which means that if user $U_{i}$ meets user
$U_{1}$, then $U_{i}$ can only get maximum of $p_{1}$ probability from user
$U_{1}$. Obviously, the probability can be at most 1, so if user meets so many
infected users, then, at last, his probability gets 1 but it could also be
greater than 1, so to prevent this condition, we use a boundary condition
$0\leq p_{i,t}\leq 1$, and if $p_{i,t}>1$, then $p_{i,t}\leftarrow 1$.

For using HMM, we need two states, the first one is the hidden state ($H_{t}$)
and the second one is the observed state ($O_{t}$) at time $t$. The set of
infected users, described above as $\mathbb{I}=\\{I_{1},\cdots,I_{M}\\}$ is
used as a hidden state because the model can’t ensure whether a user is
COVID-19 positive or not since our model can only predict some probability, as
it can only be ensured after a lab test, that’s why it can be called a hidden
state. For the observed state, it should be directly observed by the model, as
we can directly get the data by contact tracing then it is considered as an
observed state. In our case, we use the set
$\mathbb{T}=\\{T_{1},\cdots,T_{N}\\}$ as observed state.

Let’s calculate probability for $n^{th}$ user $U_{n}$ at time $t$. Let, at
time $t$, hidden state is $H_{t}$ and observed state is $O_{t}$ and next
future hidden state is $H_{t+1}$, then $p_{n}(H_{t+1}|O_{t})$ represents next
state’s probability of infection of user $U_{n}$ due to meeting infected users
of current state. Here we introduce a new set of sets of probabilities of
traced infected users as $\mathbb{C}=\\{C_{1},\cdots C_{N}\\}$ which contains
sets of probabilities of traced infected users, where $C_{n}$ is set,
containing all infected user’s probability, who were traced within range of
$n^{th}$ user and $C_{n,k}$ is $k^{th}$ user’s probability of infection, who
got in contact with $n^{th}$ user.

When user $U_{n}$ meets $T_{n}$ number of infected users, he gets some amount
of each infected user’s probability of infection. Let, $\mu$ distribution for
$n^{th}$ user is $\mu_{n}=\\{\mu_{n,1},\cdots,\mu_{n,T_{n}}\\}$. Thus,
probability of user $U_{n}$ of being infected can be:

$\displaystyle p_{n}(H_{t+1}|O_{t})$ $\displaystyle=(\mu_{n,1}\times
C_{n,1})+(\mu_{n,2}\times C_{n,2})$ (1)
$\displaystyle+\cdots+(\mu_{n,T_{n}}\times C_{n,T_{n}})$
$\displaystyle=\sum_{k=1}^{T_{n}}\mu_{n,k}\times C_{n,k}$

Now, we aim to find values of $\mu_{n,k}$ $\forall$ $1$ $\leq$ $k$ $\leq$
$T_{n}$. As we have discussed the dependencies of $\mu$ over time of contact
and signal strength, we’ll calculate $\mu$ with help of those dependencies.
Let, $\tau_{0}$ be threshold time for a user to be infected after being in
touch with infected user, $\nu_{0}$ be the threshold signal strength (after
certain experiments, we have $\mu_{0}=-0.55$ $dBm$ Received Signal Strength
Indicator (RSSI) value, which is calculated for two meter distance between two
users), and if signal strength is more than threshold, then only a user can be
infected by meeting an infected user. Let $\tau_{n,k}$ be the time for which
users $U_{n}$ and $U_{k}$ get connected and $\nu_{n,k}$ is signal strength. If
signal strength $\nu_{n,k}$ is less than threshold $\nu_{0}$, means they are
at a distance of more than two meters, and user cannot be infected (in ideal
cases, when there is not any other reason), and in that case value of
$\mu_{n,k}$ will directly be assumed $0$, but if the signal strength is more
than or equal to threshold then only we can say that in this case a user gets
more infected as time of contact increases. So, in the case of more than
threshold signal strength, infection spread to user is directly dependent on
time of contact. Therefore we write:

$\mu_{n,k}=\\{$

$0$: $\nu_{n,k}<\nu_{0}$

$\mu_{n,k}\propto\tau_{n,k}$: $\nu_{n,k}\geq\nu_{0}$

$\\}$

Now, for dealing with signal strength, we need a new variable, let
$\lambda\in\\{0,1\\}$, such that if the signal strength is less than the
threshold, then $\lambda=0$, otherwise, $\lambda=1$. For the time of contact,
where we have assumed that if time of contact is less than or equal to the
threshold, then user gains some part of infected user’s probability,
otherwise, if time of contact exceeds threshold limit, then user gains whole
part of infected user’s probability. Here also, we need a new variable, let
$\omega$, where $0\leq\omega\leq 1$, which deals with the time of contact and
provides a fraction value which is the fraction of infected user’s
probability. So,

$\omega_{n,k}=\\{$

$\frac{\tau_{n,k}}{\tau_{0}}$: $\tau_{n,k}\leq\tau_{0}$

$1$: $\tau_{n,k}>\tau_{0}$

$\\}$

Here, $\omega$ is the fraction value of infection probability which needs to
be added to not-infected user, when he meets an infected user. So, keeping in
mind all of the above constraints, we come to a solution given below:

$\mu_{n,k}=\lambda_{n,k}\times\omega_{n,k}$ (2)

From the above Eqs. (1) and (2), we get:

$p_{n}(H_{t+1}|O_{t})=\sum_{k=1}^{T_{n}}\left(\lambda_{n,k}\times\omega_{n,k}\times
C_{n,k}\right).$ (3)

Algorithm 1 calculates probability of infection which a user gets after
getting in contact with infected users. As input, it takes contact traced data
as time of contact, Bluetooth signal strength and probabilities of infected
users. Here, probability is calculated for an individual user, based on their
meetups with other users. For each user, first the signal strength is
evaluated and if it passes the threshold, then time of contact is used to
calculate probability. Finally, probability due to meeting infected users, for
each user is calculated. In the worst case, time complexity for algorithm 1
would be O($N\times T_{n}$), where $N$ is the total number of user in the
database and $T_{n}$ is the maximum number of meetups among all users.

Algorithm 1 Probability calculation with traced data

1:Input: Contact traced data $T_{t}$ or set of _meetups_ of each user, time of
contact set $\tau_{t}$, signal strength set $\nu_{t}$, contact traced
probabilities set $C_{t}$.

2:Output: Probability distribution $p(H_{t+1}|O_{t})$, Eq. (3).

3:Initialize: Initializing Probability Distribution $p_{n}(H_{t+1}|O_{t})$ =
$0$ $\forall$ 0 $\leq$ $n$ $\leq$ $N$, $\mu_{n,k}=0$ $\forall$ 1 $\leq$ $k$
$\leq$ $T_{n}$

4:for $n$ = $1,\cdots,N$ do

5: for $k=1,\cdots,T_{n,t}$

6: if $\nu_{n,k}\geq\nu_{0}$ then

7: $\lambda_{n,k}=1$

8: if $\tau_{n,k}\leq\tau_{0}$ then

9: $\omega_{n,k}=\frac{\tau_{n,k}}{\tau_{0}}$

10: else

11: $\omega_{n,k}=1$

12: else

13: $\lambda_{n,k}=0$

14: $\omega_{n,k}=0$

15: $\mu_{n,k}=\lambda_{n,k}\times\nu_{n,k}$

16: $p_{n}(H_{t+1}|O_{t})=p_{n}(H_{t+1}|O_{t})+\left(\mu_{n,k}\times
C_{n,k}\right)$

17: if $p_{n}(H_{t+1}|O_{t})>1$ then

18: $p_{n}(H_{t+1}|O_{t})=1$

####  IV-2 Probability calculation from user’s symptoms and evaluating total
probability of infection

Since, it may be the case that without even being in touch with any other
infected user, a user can be infected by the virus. When we talk about the
COVID-19 virus, we shouldn’t neglect that this virus can live for hours and
days on some surfaces or objects. As it is obvious that after having some
symptoms only, a user goes for a health checkup, and then he finds the
results. So, it is also important to keep track of user symptoms for better
results. For example: let us take two users $U_{1}$ and $U_{2}$ and both are
having some symptoms of the virus, but user $U_{1}$ didn’t meet any infected
user means $T_{1}=0$ for user $U_{1}$ and user $U_{2}$ has met $T_{2}$ number
of infected users. In this case, obviously user $U_{2}$ has more probability
of being infected but we can’t neglect user $U_{1}$ also. So, we need a
probability function that calculates the probability of infection a user gets
due to his symptoms.

Further, we use a symptom status of each user as set
$\mathbb{S}=\\{S_{1},\cdots,S_{N}\\}$, which was described in above Section
III. Its obvious that in situations like COVID-19, no one wants to get in
touch with a user having any of the symptoms which are related to COVID-19
even if the user is really positive or not, and it would also be very helpful
if we prevent users to meet those users who are having any COVID-19 related
symptoms. So, if a user is having any symptoms then we are directly assuming
the user infected and prevent other users to meet him. In other words, we are
adding all users with symptoms in the set of infected users $\mathbb{I}$,
because then only we can prevent other users to meet them.

Now, we aim to derive a probability equation such that it works on symptom
status for each user and results in a probability that shows additional
chances of infection due to symptoms. In the previous example of two users
$U_{1}$ and $U_{2}$, both have serious symptoms but contact traced data for
user $U_{1}$ is $T_{1}=0$ and for user $U_{2}$ is $T_{2}>0$. Now, we want to
add both of them to the set of infected users, even if any one of them didn’t
meet a single infected user. Their current probabilities of being infected
according to contact traced data are:

$(i)$ $U_{1}$: $p_{1}=0$, since he didn’t meet any infected user.

$(ii)$ $U_{2}$: $p_{2}=\sum_{k=1}^{T_{2}}\mu_{2,k}\times C_{2,k}$ for traced
data $T_{2}$ and $C_{2}$.

Let the threshold probability for assuming a user infected is $\Theta$, then
we need an equation which calculates probability in such a way that after
adding that probability in $p_{1}$ and $p_{2}$, both of these users $U_{1}$
and $U_{2}$ gain more than $\Theta$ probability.

Let, probability due to symptoms is $\alpha_{n}$ and total probability of
infection is $P_{n}$ (probability due to contact tracing ($p_{n,t}$) +
probability due to symptoms ($\alpha_{n,t}$)) for $n^{th}$ user $U_{n}$ at
time $t$.

$(i)$ For user $U_{1}$, contact tracing data as $T_{1}=0$, total probability
of infection is: $P_{1}=p_{1}+\alpha_{1}$; where $P_{1}\geq\Theta$ and
$p_{1}=0$, so $\alpha_{1}\geq\Theta$.

$(ii)$ For user $U_{2}$, contact tracing data as $T_{2}>0$, total probability
of infection is: $P_{2}=p_{2}+\alpha_{2}$; where $P_{2}\geq\Theta$ and
$p_{2}>0$, so $\alpha_{2}\geq\Theta-p_{2}$.

$(iii)$ For users having no symptoms as such: symptom status is $S=0$ and
probability due to symptoms is $\alpha=0$.

So, at last we come to an optimal solution which is satisfying each of the
above constraints as well as probability constraints, is derived below as:

$\alpha_{n,t}=S_{n,t}\times(1-p_{n,t})\times\Theta$ (4)

where Eq. (4) shows the probability of infection of $n^{th}$ user due to his
symptoms. Hence, total probability can be calculated as:

$P_{n,t}=p_{n,t}+\alpha_{n,t}$ (5)

From above Eqs. (3), (4) and (5) we can write:

$\displaystyle P_{n,t}$
$\displaystyle=\left(\sum_{i=1}^{T_{n}}\lambda_{n,i}\times\omega_{n,i}\times
C_{n,i}\right)\texttt{+}$ (6)
$\displaystyle\left(S_{n,t}\times\left(1-\left(\sum_{i=1}^{T_{n}}\lambda_{n,i}\times\omega_{n,i}\times
C_{n,i}\right)\right)\times\Theta\right).$

We use number of newly infected users of each day as a result to compare
model’s work with real world data. In the following Algorithm 2, we evaluate
newly infected users of each day, where $f_{d}$ shows number of newly infected
users on day $d$.

1:Input: probability distribution $p_{n,t}$ (from algorithm 1), symptom status
$\mathbb{S}$, threshold probability $\Theta$

2:Output: probability due to symptoms $\alpha_{n,t}$, total probability
$P_{n,t}$, $\forall$ $n\in\\{1,\cdots,N\\}$, time $t$ and number of infected
users $f_{d}$ on day $d$

3:Initialize: initialize $\alpha_{n,t}=0$ $\forall$ $n$ $\in$
$\\{1,\cdots,N\\}$, $f_{d}=0$

4:for $n$ = $1,\cdots,N$ do

5: if symptoms are there then

6: $S_{n,t}=1$

7: else

8: $S_{n,t}=0$

9: $\alpha_{n,t}$ = $S_{n,t}\times(1-p_{n,t})\times\Theta$

10: $P_{n,t}=p_{n,t}+\alpha_{n,t}$

11: if $P_{n,t}\geq\Theta$ then

12: $f_{d}=f_{d}+1$

Algorithm 2 Probability calculation due to symptoms and evaluating total
probability of infection

In algorithm 2, probability due to the user’s symptoms is calculated. First,
symptom distribution is calculated, then with the proposed Eq. (4), symptoms
probability is calculated and total probability via adding both probabilities
(probability due to traced infected users and probability due to symptoms) is
calculated. After that, the number of newly infected users (total probability
more than $\Theta$) is evaluated, and based on these results, graphs are
plotted. Time complexity for Algorithm 2 with total of $N$ users in the
database is O($N$).

####  IV-3 Result analysis and reporting

Now, aim is to analyze the results, create reports for each user and send the
reports to respective users. Results are also sent to the cloud to keep track
of each user’s health history and based on these results, reports are
generated for individual user and reports are sent to them. These reports
contain infection level of the respective users, precautions, medication and
all necessary guidelines based on user’s infection level, which help preparing
the users to fight against the virus. The infection levels are initially
divided into 4 parts: low, moderate, high, very high. Obviously, a low
infection level means very few chances of being infected, moderate infection
level means average chances of infection, high infection level means high
chances of infection, and very high infection level means a user is infected.
Moreover, the risk levels of all users are computed as follows:

$Infection$ $level$ = $\\{$

”Low” : $0\leq P_{n,t}<P_{l}$

”Moderate” : $P_{l}\leq P_{n,t}<P_{avg}$

”High” : $P_{avg}\leq P_{n,t}<P_{h}$

”Very High” : $P_{h}$ $\leq$ $P_{n,t}$ $\leq$ 1

$\\}$

where thresholds for low is $P_{l}$, for moderate is $P_{avg}$, for high is
$P_{h}$ and for very high is $1$, which helps creating a report based on
user’s current risk levels.

1:Input: Probability $P_{t}$ of all users being infected at time $t$, $P_{l}$,
$P_{avg}$, $P_{h}$ thresholds

2:Output: Infection level $L_{t}=\\{L_{1,t},\cdots,L_{N,t}\\}$ at time $t$

3:Initialize: initialize $L_{t}=[\phi]$

4:for $n$ = $1,\cdots,N$ do

5: if $0$ $\leq$ $P_{n,t}$ $<$ $P_{l}$ then

6: $L_{n,t}$ = ”low”

7: if $P_{l}$ $\leq$ $P_{n,t}$ $<$ $P_{avg}$ then

8: $L_{n,t}$ = ”moderate”

9: if $P_{avg}$ $\leq$ $P_{n,t}$ $<$ $P_{h}$ then

10: $L_{n,t}$ = ”high”

11: else

12: $L_{n,t}$ = ”very high”

Algorithm 3 Infection level calculation

Let, at time $t$, $L_{t}$ be a set of $N$ elements, having values ”low”,
”moderate”, ”high” or ”very high”, which means that user $U_{n}$ is having
$L_{n,t}$ chances of being infected at time $t$. This result is provided to
each user to make them ensure whether or not they are infected with virus or
what are the chances or risks of infection. Separating users according to
their risk levels is important because in this case a user is directly
provided a report which tells him his current condition and the ways to be
safe in the form of precautions, medications and many more healthcare benefits
and help a user to make him aware of his condition.

Finally, FS has a set of infection levels, which helps FS creating reports for
each user in an efficient way according to their infection level.

In Algorithm 3, aim is to get each user’s risk levels based on their
probability of infection. Each user is categorized in one of the four risk
levels, and according to the user’s risk level, reports containing
precautions, healthcare medications, needed guidelines are generated and sent
to respective users. Time complexity for Algorithm 3 is O($N$).

If we talk about overall time complexity of our proposed scheme, then in worst
case, it would be O($N\times T_{n}$), where $N$ is the total number of users
in the database and $T_{n}$ is the maximum number of meetups among all users,
as described before.

##  V Performance Study

In this section, we illustrate the proposed scheme with help of different
simulation parameters on real-time data. Here, we use two place’s data of
virus spread of 15 days. So, first, we evaluate those place’s results with our
model and then we compare them with real-world data. The data we are going to
use are of two places, one is Pinal, Arizona, USA and the second one is
Maricopa, Arizona, USA [17].

We have taken 15 days of data of virus spread. For Pinal, the data is from the
20th March 2020 to 4th April 2020, and for Maricopa, it is from 15th March
2020 to 30th March 2020. The data shows the number of new COVID-19 confirmed
cases on each day and are shown below in Fig. 5 for Pinal and Maricopa.

###  V-A Model Setup

In the simulation environment, 10,000 users are considered. Out of them, some
may be suffering from the COVID-19 virus. On the first day, there will be a
number of _meetups_ , and after each meetup between two users, if any one of
them is infected, then the second user will gain some amount of infected
user’s infection probability according to the signal strength and time of
contact which was described in Algorithms 1. After that, if the second user’s
probability of infection gets more than the fixed threshold ($\Theta$), then
that user will also be assumed infected for future evaluations. Likewise, our
model will evaluate for each day, for each meetup, and for each user. One more
thing that is very important, is the distribution of the symptoms of users. As
described in Algorithm 2, if someone gets any kind of COVID-19 related
symptoms, probability due to that particular symptom is evaluated and added in
the probability due to contact tracing. And finally, based on the results,
reports are generated for each user with the help of Algorithm 3. So, this is
how the infection spreads between several users and our model calculates each
user’s probability so that a user can be informed on early stages, which will
help a user to take necessary precautions in advance and to fight easily
against COVID-19.

One most dangerous situation that is prevented by our model is that it helps
in breaking the chain. For example, as given in Fig. 4, if a single user can
be prevented from being infected in the early stages, then users who got
infected by that user, can be saved and this can help to control the spread of
the virus. So, our model alerts each user if he is going to meet an infected
user which helps in breaking the chain and to control virus spread on the
initial stage itself.

Figure 4: Infection chain

###  V-B Evaluation of Results

As given in Algorithm 1, first probability of infection due to traced infected
users is calculated then according to Algorithm 2, if symptoms are there for a
particular user then probability due to those symptoms is added to that user
and total probability is calculated. After applying both Algorithm 1 and
Algorithm 2 on data of Pinal and Maricopa, the evaluated and real results are
discussed below:

Figure 5: Real time results of virus spread at Pinal and Maricopa.

Fig. 5 show the real-world data in form of a graph showing each day’s number
of newly infected users in Pinal and Maricopa. For example, in Pinal, on the
first day (20th March 2020), the number of newly infected patients is 10, on
the next day 14, and so on and in Maricopa, on the first day (15th March
2020), the number of newly infected patients are 8, on next day 9, and so on.
Since, virus-infected users normally show symptoms after a long time of around
1 week to 2 weeks, which means that the results which are shown by graph are
of 1 to 2 weeks earlier, means users had been infected 1 or 2 weeks before but
it took some time for the virus to be exposed. In that case, if a user would
be using the proposed model, then just after having some probability of
infection, that user could be informed so that the user can easily fight
against COVID-19 in earlier stages only.

Now, in the evaluation of results with our model, we use the term meetups,
which was described above. Obviously, we can’t know how many times a user will
meet another user, in that case, we assume different cases but we can’t only
be dependent on just one case. So, here we work on 8 cases, from that 4 cases
are for Pinal and 4 cases are for Maricopa. We use the different number of
average meetups for each case and then finally for each case, graphs are
plotted and comparisons are done. Moreover, the simulation parameters are
shown in Table I. In Table I, rows 1-4 represents the simulation setup for the
Pinal data set whereas the remaining rows are set up for the Maricopa data set
for finding out the simulation results.

TABLE I: Simulation Parameters Cases |  theta $\Theta$ |  $\tau_{0}$ (minutes) |  $\nu_{0}$ (dBm) |  Meetups a day
---|---|---|---|---
1 |  0.9 |  2 |  -0.55 |  1225 and 1250
2 |  0.9 |  2 |  -0.55 |  1275 and 1300
3 |  0.9 |  1 |  -0.50 |  1225 and 1250
4 |  0.9 |  1 |  -0.50 |  1275 and 1300
5 |  0.9 |  2 |  -0.55 |  2300 and 2330
6 |  0.9 |  2 |  -0.55 |  2345 and 2360
7 |  0.9 |  1 |  -0.50 |  2300 and 2330
8 |  0.9 |  1 |  -0.50 |  2345 and 2500

Here a question arises about the number of meetups like why only these number
of meetups are assumed and why there is a difference between them. In answer
to this question, we say that without deploying the system between people, we
can’t know which users are going to meet which and how many other users. So,
here we have assumed that on an average day, there is an average of 1225 to
1300 meetups a day in Pinal and 2300 to 2360 meetups in Maricopa. The main
reason behind the selection of these numbers is that these parameters are
providing very good and satisfying results. If we talk about the difference
between these meetups, then the reason is the population of both Pinal and
Maricopa. With a population of 0.49 million in Pinal, it has less number of
meetups compared to Maricopa with a 4.5 million population as it’s obvious
that highly populated areas will have a high number of meetups.

With all the parameters in the above simulation Table I and for each case, we
evaluate results which are in form of several infected users of all days,
after that a graph is plotted for each day’s number of newly infected users.
Each case having its separate parameters and data as given in the above table.
So, evaluated results for each case are shown below in graphs.

Case-I: In case-I, we work on Pinal dataset with threshold probability of
infection $\Theta=0.9$, threshold time of contact $\tau_{0}=2$ minutes,
threshold signal strength $\nu_{0}=-0.55$ dBm and assuming number of meetups
as 1225 and 1250. As given in Fig. 6, three curves are plotted, first is for
1225 meetups, the second is for 1250 meetups and the third is for real-world
results of Pinal.

Figure 6: Case-1

Case-II: In this case, we work on Pinal dataset with threshold probability of
infection $\Theta=0.9$, threshold time of contact $\tau_{0}=2$ minutes,
threshold signal strength $\nu_{0}=-0.55$ dBm and assuming number of meetups
as 1275 and 1300. As given in Fig. 7, three curves are plotted, first is for
1275 meetups, the second is for 1300 meetups and the third is for real-world
results of Pinal.

Figure 7: Case-2

Case-III: In this case, we work on Pinal dataset with threshold probability of
infection $\Theta=0.9$, threshold time of contact $\tau_{0}=1$ minutes,
threshold signal strength $\nu_{0}=-0.50$ dBm and assuming number of meetups
as 1225 and 1250. As given in Fig. 8, three curves are plotted, first is for
1225 meetups, the second is for 1250 meetups and the third is for real-world
results of Pinal.

Figure 8: Case-3

Case-IV: In this case, we work on Pinal dataset with threshold probability of
infection $\Theta=0.9$, threshold time of contact $\tau_{0}=1$ minutes,
threshold signal strength $\nu_{0}=-0.50$ dBm and assuming number of meetups
as 1275 and 1300. As given in Fig. 9, three curves are plotted, first is for
1275 meetups, the second is for 1300 meetups and the third is for real-world
results of Pinal.

Figure 9: Case-4

Case-V: In this case, we work on Maricopa dataset with threshold probability
of infection $\Theta=0.9$, threshold time of contact $\tau_{0}=2$ minutes,
threshold signal strength $\nu_{0}=-0.55$ dBm and assuming number of meetups
as 2300 and 2330. As given in Fig. 10, three curves are plotted, first is for
2300 meetups, the second is for 2330 meetups and the third is for real-world
results of Maricopa.

Figure 10: Case-5

Case-VI: In this case, we work on Maricopa dataset with threshold probability
of infection $\Theta=0.9$, threshold time of contact $\tau_{0}=2$ minutes,
threshold signal strength $\nu_{0}=-0.55$ dBm and assuming number of meetups
as 2345 and 2360. As given in Fig. 11, three curves are plotted, first is for
2345 meetups, the second is for 2360 meetups and the third is for real-world
results of Maricopa.

Figure 11: Case-6

Case-VII: In this case, we work on Maricopa dataset with threshold probability
of infection $\Theta=0.9$, threshold time of contact $\tau_{0}=1$ minutes,
threshold signal strength $\nu_{0}=-0.50$ dBm and assuming number of meetups
as 2300 and 2330. As given in Fig. 12, three curves are plotted, first is for
2300 meetups, the second is for 2330 meetups and the third is for real-world
results of Maricopa.

Figure 12: Case-7

Case-VIII: In this case, we work on Maricopa dataset with threshold
probability of infection $\Theta=0.9$, threshold time of contact $\tau_{0}=1$
minutes, threshold signal strength $\nu_{0}=-0.50$ dBm and assuming number of
meetups as 2345 and 2360. As given in Fig. 13, three curves are plotted, first
is for 2345 meetups, the second is for 2360 meetups and the third is for real-
world results of Maricopa.

Figure 13: Case-8

As we can see that the accuracy of the graphs is very good for some parameters
like in case-1 and case-4 etc, but it doesn’t mean that they always provide
the right solution because meetups are directly dependent on people but in
case, maybe with some government-imposed guidelines like lockdown, curfew can
also be used to reduce the number of meetings between people. So, our model is
used to track every user, so that the next chains can be broken and the spread
of the virus can be reduced in the early stages only. It also takes care of
each user individually by sending them their reports and all the needed
precautions according to the risk levels of the individual user. And one more
important thing to be noticed is that if at a certain day, according to the
conditions of that day, future cases can also be calculated roughly just by
taking the average number of meetups according to the condition, like in the
condition of lockdown or curfew, the average number of meetups will be
decreased and on a normal day, meetups can be more. So, with a rough idea of
the current situation ( number of meetups nowadays), future prediction can
also be done with our model. After having an average number of meetups,
randomly two users are selected for each meetup and if any one of them is
infected then with the help of algorithms, probabilities are calculated and
finally, the rate of virus spread can be calculated and based on the results,
actions can be taken like lockdown, curfew, vaccination, etc so that
disastrous situations can be avoided. This also helps us get prepared for
future conditions.

##  VI Conclusion and Future Work

In this work, we present a fog support framework, which can help individuals
by keeping them safe and away from infected people and by advising them with
the best precautions, guidelines, and medications. It also helps us predicting
future conditions according to the present scenario of virus spread. In this
model, we have used HMM and contact tracing via Bluetooth, and finally,
implemented the framework with real-world data. From the real-world data
analysis, we have concluded the effectiveness of the proposed model on
different simulation settings for helping out taking precautionary steps in
advance to stop the spread of the virus.

In the future, we’ll propose a mechanism that can also take care of
asymptomatic scenarios of COVID-19 infection. Moreover, we are also targeting
to include the wider real-world data set from different countries to see the
effectiveness of our proposed domain. Furthermore, the proposed model can also
be extended to post real-time monitoring, prediction, and treatment of
COVID-19 patients remotely with the involvement of doctors. To avoid the
different drawbacks of Bluetooth, we also believe that the connectivity of the
devices over cellular 5G technology [18, 19] could further improve the
transmission and the computation latencies in the networking model.

Acknowledgments: The authors thank Mr. Tanay Jonwal and Mr. Lali Akhil Raj for
their insightful discussions.

## References

  * [1] “Worldometer Coronavirus.” https://www.worldometers.info/coronavirus/?utm_campaign=homeAdvegas1? Accessed: 2021-05-18.
  * [2] “Symptoms of COVID-19.” https://www.cdc.gov/coronavirus/2019-ncov/symptoms-testing/symptoms.html.  Accessed: 2021-05-01.
  * [3] I. Yasser, A. Twakol, A. El-Khalek, A. Samrah, A. Salama, et al., “COVID-X: Novel Health-Fog Framework Based on Neutrosophic Classifier for Confrontation Covid-19,” Neutrosophic Sets and Systems, vol. 35, no. 1, p. 1, 2020.
  * [4] “’lab on a chip’ test has potential to detect covid-19 immune response faster than current antibody testing.” https://www.smu.edu/News/2021/Research/Lab-on-a-Chip-test-has-potential-to-detect-COVID-19-immune-response-faster.  Accessed: 2021-05-16.
  * [5] “COVID-19.” https://www.darpa.mil/work-with-us/covid-19.  Accessed: 2021-05-16.
  * [6] L. Rabiner and B. Juang, “An introduction to hidden markov models,” ieee assp magazine, vol. 3, no. 1, pp. 4–16, 1986.
  * [7] Q. Han, S. Mehrotra, and N. Venkatasubramanian, “Aquaeis: Middleware support for event identification in community water infrastructures,” in Proceedings of the 20th International Middleware Conference, pp. 293–305, 2019\.
  * [8] Y. Qi and S. Ishak, “A hidden markov model for short term prediction of traffic conditions on freeways,” Transportation Research Part C: Emerging Technologies, vol. 43, pp. 95–111, 2014.
  * [9] B. Cooper and M. Lipsitch, “The analysis of hospital infection data using hidden markov models,” Biostatistics, vol. 5, no. 2, pp. 223–237, 2004\.
  * [10] A. Krogh, B. Larsson, G. Von Heijne, and E. L. Sonnhammer, “Predicting transmembrane protein topology with a hidden markov model: application to complete genomes,” Journal of molecular biology, vol. 305, no. 3, pp. 567–580, 2001.
  * [11] J. Felsenstein and G. A. Churchill, “A hidden markov model approach to variation among sites in rate of evolution.,” Molecular biology and evolution, vol. 13, no. 1, pp. 93–104, 1996.
  * [12] K. T. Eames and M. J. Keeling, “Contact tracing and disease control,” Proceedings of the Royal Society of London. Series B: Biological Sciences, vol. 270, no. 1533, pp. 2565–2571, 2003.
  * [13] B. Armbruster and M. L. Brandeau, “Contact tracing to control infectious disease: when enough is enough,” Health care management science, vol. 10, no. 4, pp. 341–355, 2007.
  * [14] M. E. Kretzschmar, G. Rozhnova, M. C. Bootsma, M. van Boven, J. H. van de Wijgert, and M. J. Bonten, “Impact of delays on effectiveness of contact tracing strategies for covid-19: a modelling study,” The Lancet Public Health, vol. 5, no. 8, pp. e452–e459, 2020.
  * [15] E. Hernández-Orallo, C. T. Calafate, J.-C. Cano, and P. Manzoni, “Evaluating the effectiveness of covid-19 bluetooth-based smartphone contact tracing applications,” Applied Sciences, vol. 10, no. 20, p. 7113, 2020\.
  * [16] S. Ojagh, S. Saeedi, and S. H. Liang, “A person-to-person and person-to-place covid-19 contact tracing system based on ogc indoorgml,” ISPRS International Journal of Geo-Information, vol. 10, no. 1, p. 2, 2021.
  * [17] “CSSEGISandData/COVID-19.” https://github.com/CSSEGISandData/COVID-19/blob/master/csse_covid_19_data/csse_covid_19_time_series/time_series_covid19_confirmed_US.csv.  Accessed: 2021-05-18.
  * [18] A. Pratap and S. K. Das, “Stable Matching based Resource Allocation for Service Provider’s Revenue Maximization in 5G Networks,” IEEE Transactions on Mobile Computing, pp. 1–1, 2021.
  * [19] A. Pratap, R. Gupta, V. S. Siddhardh Nadendla, and S. K. Das, “On Maximizing Task Throughput in IoT-Enabled 5G Networks Under Latency and Bandwidth Constraints,” in 2019 IEEE International Conference on Smart Computing (SMARTCOMP), pp. 217–224, 2019.

|  Suraj Mahawar is B.Tech 2nd year student in the Department of Computer
Science and Engineering, Indian Institute of Technology (BHU) Varanasi, India.
His interests include Algorithm Design and Mathematical modeling of real time
problems.
---|---
|  Ajay Pratap is an Assistant Professor with the Department of Computer
Science and Engineering, Indian Institute of Technology (BHU) Varanasi, India.
Before joining IIT (BHU), he was associated with the Department of Computer
Science and Engineering, National Institute of Technology Karnataka (NITK)
Surathkal, India, as an Assistant Professor from December 2019 to May 2020. He
worked as a Postdoctoral Researcher in the Department of Computer Science at
Missouri University of Science and Technology, USA, from August 2018 to
December 2019. He completed his Ph.D. degree in Computer Science and
Engineering from the Indian Institute of Technology Patna, India, in July
2018. His research interests include Cyber-Physical Systems, IoT-enabled Smart
Environments, Mobile Computing and Networking, Statistical Learning, Algorithm
Design for Next-generation Advanced Wireless Networks, Applied Graph Theory,
and Game Theory. His current work is related to HetNet, Small Cells, Fog
Computing, IoT, and D2D communication underlaying cellular 5G and beyond. His
papers appeared in several international journals and conferences including
IEEE Transactions on Mobile Computing, IEEE Transactions on Parallel and
Distributed Systems, and IEEE LCN, etc. He has received several awards
including the Best Paper Candidate Award and NSF travel grant for IEEE
Smartcom’19 in the USA.
---|---


#  Totally Positive Functions and Gabor Frames over Rational Lattices

Karlheinz Gröchenig  Faculty of Mathematics
University of Vienna
Oskar-Morgenstern-Platz 1
A-1090 Vienna, Austria<EMAIL_ADDRESS>
###### Abstract.

We show that for an arbitrary totally positive function $g\in
L^{1}(\mathbb{R})$ and $\alpha\beta$ rational, the Gabor family $\\{e^{2\pi
i\beta lt}g(t-\alpha k):k,l\in\mathbb{Z}\\}$ is a frame for
$L^{2}(\mathbb{R})$, if and only if $\alpha\beta<1$.

###### Key words and phrases:

Totally positive function, Gabor frame, spectral invariance, invertibility of
totally positive matrices

###### 2010 Mathematics Subject Classification:

42C15 , 42C40 , 94A20, 42A82

K. G. was supported in part by the project P31887-N32 of the Austrian Science
Fund (FWF)

##  1\. Introduction

Ever since J. von Neumann and D. Gabor claimed that the family of time-
frequency shifts (phase-space shifts) $\\{e^{2\pi
ilt}e^{-\pi(t-k)^{2}}:k,l\in\mathbb{Z}\\}$ spans $L^{2}(\mathbb{R})$, the
spanning properties of time-frequency shifts have sparked the curiosity of
mathematicians, physicists, and engineers. Modern versions of this problem
replace the Gaussian by arbitrary generators and the time-frequency shift over
the lattice $\mathbb{Z}^{2}$ by general lattices or even non-uniform sets.

To be specific, the time-frequency shift of $g\in L^{2}(\mathbb{R})$ by
$(x,\xi)\in\mathbb{R}^{2}$ is defined as

(1) $M_{\xi}T_{x}f(t)=e^{2\pi i\xi t}g(t-x)\,.$

Given lattice parameters $\alpha,\beta>0$ the set
$\mathcal{G}(g,\alpha,\beta)=\\{M_{\beta l}T_{\alpha k}g:k,l\in\mathbb{Z}\\}$
is called Gabor family over the lattice
$\alpha\mathbb{Z}\times\beta\mathbb{Z}$ with window $g$. Gabor analysis
studies the question under which conditions on $\alpha,\beta$, and $g$ there
exist constants $A,B>0$, such that

(2) $A\|f\|_{2}^{2}\leq\sum_{k,l\in\mathbb{Z}}|\langle f,M_{\beta l}T_{\alpha
k}g\rangle|^{2}\leq B\|f\|_{2}^{2}\qquad\forall f\in L^{2}(\mathbb{R})\,.$

If (2) holds, $\mathcal{G}(g,\alpha,\beta)$ is called a Gabor frame. The set

$\mathcal{F}(g)=\\{(\alpha,\beta)\in\mathbb{R}_{+}^{2}:\mathcal{G}(g,\alpha,\beta)\,\text{
is a frame }\\}$

is called the frame set of $g$. Knowing $\mathcal{F}(g)$ amounts to a complete
characterization of all (rectangular) lattices
$\alpha\mathbb{Z}\times\beta\mathbb{Z}$ that generate a Gabor frame with a
given window $g$.

Our understanding of the frame set is still very limited. The prototypical
result is due to Lyubarski [28] and Seip-Wallsten [33, 34] and determines the
frame set of the Gaussian to be $\mathcal{F}(e^{-\pi
t^{2}})=\\{(\alpha,\beta)\in\mathbb{R}_{+}^{2}:\alpha\beta<1\\}$. This is
usually formulated by saying that $\mathcal{G}(e^{-\pi t^{2}},\alpha,\beta)$
is a frame if and only if $\alpha\beta<1$. Subsequently, further examples of
frame sets were found by Janssen and Strohmer [22, 23, 25]. It was noted in
[19] that all examples known until 2010 were based on a totally positive
window $g$. This observation led to a more systematic approach to study the
frame set for totally positive windows.

To explain the state-of-the-art we recall that a measurable function $g$ on
$\mathbb{R}$ is totally positive, if for every $n\in\mathbb{N}$ and every two
sets of increasing numbers $x_{1}<x_{2}<\dots<x_{n}$ and
$y_{1}<y_{2}<\dots<y_{n}$ the matrix
$\big{(}g(x_{j}-y_{k})\big{)}_{j,k=1,\dots,n}$ has non-negative determinant:

(3) $\det(g(x_{j}-y_{k})\Big{)}_{j,k=1,\dots,n}\geq 0\,.$

If in addition $g$ is integrable, then $g$ possesses already exponential decay
[31, Lemma 2]. Often an integrable totally positive function is called a Polya
frequency function, but we will not make this distinction here.

By a deep theorem of Schoenberg [31] the Fourier transform of an integrable
totally positive function $g$ possesses the factorization

(4) $\hat{g}(\xi)=ce^{-\gamma\xi^{2}}e^{2\pi i\nu\xi}\prod_{j=1}^{N}(1+2\pi
i\nu_{j}\xi)^{-1}e^{-2\pi i\nu_{j}\xi}$

with $c>0$, $\nu,\nu_{j}\in\mathbb{R}$, $\gamma\geq 0$,
$N\in\mathbb{N}\cup\\{\infty\\}$ and $0<\gamma+\sum_{j}\nu_{j}^{2}<\infty$.

Among the totally positive functions are the Gaussian $e^{-\gamma t^{2}}$ for
$\gamma>0$ and the one-sided exponential functions
$\eta_{\gamma}(t)=e^{-\gamma t}\chi_{\mathbb{R}^{+}}(\gamma t)$ with
$\gamma\in\mathbb{R},\gamma\neq 0$.

For the subclass of totally positive functions, for which the factorization
(4) is a finite product, the results of [19, 18] can be summarized as follows:

######  Theorem 1.1.

Let $g\in L^{2}(\mathbb{R})$ be a totally positive function with a finite
factorization (4) with $N\in\mathbb{N}$ other than the one-sided exponentials
$\eta_{\gamma}$, then

$\mathcal{F}(g)=\\{(\alpha,\beta)\in\mathbb{R}_{+}^{2}:\alpha\beta<1\\}\,.$

In other words, the lattice $\alpha\mathbb{Z}\times\beta\mathbb{Z}$ generates
a frame with totally positive window $g$, if and only if $\alpha\beta<1$.

Remarkly the proof of Theorem 1.1 required different methods for the cases
$\gamma=0$ (no Gaussian factor) and $\gamma>0$ (with Gaussian factor). In the
former case total positivity and the Schoenberg-Whitney conditions were used,
in the latter case only the factorization was used in conjunction with complex
analysis.

The frame set of the one-sided exponential $\eta_{\gamma}$ is slightly
different, since $\eta_{\gamma}$ is not smooth enough and the Balian-Low
theorem does not apply [20]. In this case the frame set is
$\mathcal{F}(\eta_{\gamma})=\\{(\alpha,\beta)\in\mathbb{R}_{+}^{2}:\alpha\beta\leq
1\\}$, as was already known by Janssen [22].

Theorem 1.1 suggests that the characterization of Gabor frames holds for _all_
totally positive generators. Our goal is to prove the following theorem which
is a step towards the full conjecture formulated in [16].

######  Theorem 1.2.

Assume that $g$ is totally positive other than a one-sided exponential
function $\eta_{\gamma}$. Further assume that $\alpha\beta$ is rational. Then
$\mathcal{G}(g,\alpha,\beta)$ is a frame for $L^{2}(\mathbb{R})$, if and only
if $\alpha\beta<1$.

Theorem 1.2 implies that the frame set $\mathcal{F}(g)$ is an _open, dense_
subset of $\\{(\alpha,\beta)\in\mathbb{R}_{+}^{2}:\alpha\beta<1\\}$. This
follows from a deformation result of Feichtinger and Kaiblinger [11].

Since every totally positive function is a limit of a totally positive with a
finite factorization, one would hope that some kind of limiting procedure
would work. However, so far all our “proofs” contained a gap. Except for the
example of the hyperbolic secant $(e^{at}+e^{-at})^{-1}$ [25], Theorem 1.2 is
the first general statement about Gabor frames with a totally positive
generator with an infinite factorization (4).

In this paper we present a new approach that is independent of Schoenberg’s
factorization (4) and uses only the definition of total positivity. The new
proof idea comes from a deep theorem of [8] about invertibility of infinite
totally positive matrices. We also use methods from spectral invariance of
matrix algebras and the important fact that the Zak transform of a totally
positive function has only one zero. For rational lattices this method leads
also to a new proof of Theorem 1.1.

To finish the discussion, we mention the superb work [3], which determines the
frame set of rational functions (Hurwitz functions)
$g(t)=\sum_{j=1}^{N}\frac{a_{j}}{t-iw_{j}}$ for $w_{j}\in\mathbb{C}$. If
$a_{j}>0$ and $w_{j}>0$, then
$\mathcal{F}(g)=\\{(\alpha,\beta)\in\mathbb{R}_{+}^{2}:\alpha\beta\leq 1\\}$,
for general coefficients the frame set contains
$\\{(\alpha,\beta)\in\mathbb{R}_{+}^{2}:\alpha\beta\leq
1\\}\cap\mathbb{Q}^{c}$. Interestingly and in contrast to our work, the
authors show that all irrational lattices belong to the frame set!

Other than this the complete frame set has been determined only for the
characteristic function of an interval $\chi_{[0,1]}$ [5] and the Haar
function [6]. In contrast to the results for totally positive windows and
rational functions, the frame set is extremely complicated and depends on
subtle number theoretic properties of the product $\alpha\beta$.

The case of irrational lattices remains open. There is some evidence that
generically a lattice $\alpha\mathbb{Z}\times\beta\mathbb{Z}$ with irrational
$\alpha\beta$ generates a Gabor frame. Important results pointing in this
direction are contained in [3] and in [6]. In each case an underlying
dynamical system and some ergodicity are at work. Currently we do not know how
this works for totally positive windows.

Of course, much more is known and relevant about Gabor frames. As we are
interested only in the complete characterization of Gabor frames for a given
window, we refer to the surveys [15, 17, 20] and monographs [14, 9] for the
general theory of Gabor frames.

The paper is organized as follows: In Section 2 we review the tools underlying
Gabor analysis. These are Zak transform methods, Banach algebra methods
concerning spectral invariance, and general characterizations of Gabor frames.
All these characterizations amount to showing that some (infinite) matrix is
invertible. In our approach the matrix $G$ under consideration will a sub-
matrix of the so-called pre-Gramian. This is a technical novelty. In Section 3
we show that this matrix is onto $\ell^{1}(\mathbb{Z})$ by using heavily the
properties of spectral invariance and a theorem from [8]. In Section 4 we will
show that $G$ is also one-to-one. It is only here that we will use the
rationality of the lattice. Ultimately the proof boils down to the fact that a
square matrix is invertible, if and only if it is onto.

Acknowledgement. I am deeply indebted to Jose Luis Romero and Joachim Stöckler
for comments on earlier versions of this manuscript.

##  2\. Tools

###  2.1. Reduction.

Let $g_{\beta}(x)=\beta^{-1/2}g(x/\beta)$. Then
$\mathcal{G}(g,\alpha\mathbb{Z}\times\beta\mathbb{Z})$ is a frame, if and only
if $\mathcal{G}(g_{\beta},\alpha\beta\mathbb{Z}\times\mathbb{Z})$ is a frame.
It is immediate from (3) that the set of totally positive functions is
invariant under dilations. Thus, if $g$ is totally positive, then so is
$g_{\beta}$. We may therefore always replace $g$ by $g_{\beta}$, $\alpha$ by
$\alpha\beta$ and $\beta$ by $1$ and thus assume without generality that
$\beta=1$.

We note that we may always assume that $\alpha\beta<1$ and, after the
reduction, that $\alpha<1,\beta=1$ because of the density theorem for Gabor
frames [20].

###  2.2. Spectral invariance.

Spectral invariance refers to the phenomenon that an invertible, infinite
matrix with sufficiently strong off-diagonal decay possesses an inverse with
the same off-diagonal decay. This topic has a long history with many
contributions and variations. See [1, 2, 36, 37, 35, 38] for a sample of
contributions and the survey [15]. The following version can be attributed to
Shin-Sun [35] and Tessera [38, Thm. 1.8].

######  Proposition 2.1 (Stability Theorem).

Let $G=(G_{kl})_{k,l\in\mathbb{Z}}$ be a bi-infinite matrix with off-diagonal
decay

$|G_{kl}|\leq C(1+|k-l|)^{-\sigma}\qquad k,l\in\mathbb{Z}\,,$

for some $\sigma>1$.

(i) Spectral invariance: If $G$ is invertible on some
$\ell^{p_{0}}(\mathbb{Z})$, then $G$ is invertible on all
$\ell^{p}(\mathbb{Z})$ for $1\leq p\leq\infty$.

(ii) Stability: If $G$ is stable on some $\ell^{p_{0}}(\mathbb{Z})$, i.e., if
$G$ satisfies

$\|Gc\|_{p_{0}}\geq A\|c\|_{p_{0}}\qquad\text{ for all
}c\in\ell^{p_{0}}(\mathbb{Z}),$

then $G$ is stable on all $\ell^{p}(\mathbb{Z})$ for $1\leq p\leq\infty$.

We will need a slight variation of the stability (ii) for surjective maps.

######  Proposition 2.2.

Let $G=(G_{kl})_{k,l\in\mathbb{Z}}$ with off-diagonal decay

$|G_{kl}|\leq C(1+|k-l|)^{-\sigma}\qquad k,l\in\mathbb{Z}\,,$

for some $\sigma>1$. If $G$ maps $\ell^{\infty}(\mathbb{Z})$ onto
$\ell^{\infty}(\mathbb{Z})$, then $G$ also maps $\ell^{1}(\mathbb{Z})$ onto
$\ell^{1}(\mathbb{Z})$

###### Proof.

Note that the off-diagonal decay implies that $G$ defines a bounded operator
on all $\ell^{p}(\mathbb{Z}),1\leq p\leq\infty$.

By the closed range theorem [30, p. 102], the adjoint operator (matrix) on the
pre-dual $G^{*}:\ell^{1}(\mathbb{Z})\to\ell^{1}(\mathbb{Z})$ is one-to-one
with closed range in $\ell^{1}(\mathbb{Z})$. Consequently, $G^{*}$ satisfies
an inequality of the form

(5) $\|G^{*}c\|_{1}\geq A\|c\|_{1}\qquad\text{ for all
}c\in\ell^{1}(\mathbb{Z})$

with a positive constant $A>0$.

The stability part of Proposition 2.1 then implies that (5) holds for all
$p$-norms, in particular, for some $A^{\prime}>0$ we have

$\|G^{*}c\|_{\infty}\geq A^{\prime}\|c\|_{\infty}\qquad
c\in\ell^{\infty}(\mathbb{Z})\,.$

Since $G^{*}$ is one-to-one with norm-closed range in
$\ell^{\infty}(\mathbb{Z})$, we conclude that
$G:\ell^{1}(\mathbb{Z})\to\ell^{1}(\mathbb{Z})$ must be onto
$\ell^{1}(\mathbb{Z})$.

###  2.3. Characterizations of Gabor frames.

We use the following characterization of Gabor frames that goes back to
Janssen [21] and the duality theory of Gabor frames [29]. This is one of the
most successful criteria to verify that a Gabor system over a rectangular
lattice generates a frame and has been applied many times. We refer to [17]
for a survey of the known characterizations of Gabor frames and some of their
uses.

######  Theorem 2.3.

Assume that $g:\mathbb{R}\to\mathbb{R}$ is continuous and satisfies the
condition $\sum_{k\in\mathbb{Z}}\sup_{x\in[0,1]}|g(x+k)|<\infty$. Then the
following are equivalent.

  * (i)

The family $\mathcal{G}(g,\alpha\mathbb{Z}\times\mathbb{Z})$ is a frame for
$L^{2}(\mathbb{R})$.

  * (ii)

For every $x\in[0,1)$, there exist $A_{x},B_{x}>0$ such that

(6)
$A_{x}\|c\|_{2}^{2}\leq\sum_{j\in\mathbb{Z}}\Big{|}\sum_{k\in\mathbb{Z}}c_{k}g(x+\alpha
j-k)\Big{|}^{2}\leq B_{x}\|c\|_{2}^{2}\qquad\mbox{for all
}c\in\ell^{2}(\mathbb{Z}).$

  * (iii)

There exist $A,B>0$ such that, for all $x\in[0,1)$,

$A\|c\|_{2}^{2}\leq\sum_{j\in\mathbb{Z}}\Big{|}\sum_{k\in\mathbb{Z}}c_{k}g(x+\alpha
j-k)\Big{|}^{2}\leq B\|c\|_{2}^{2}\qquad\mbox{for all
}c\in\ell^{2}(\mathbb{Z}).$

The matrix $P(x)=\big{(}g(x+\alpha j-k)\big{)}_{j,k\in\mathbb{Z}}$ is often
called the pre-Gramian of the Gabor family.

Using spectral invariance, we deduce the following sufficient condition for
Gabor frames.

######  Proposition 2.4.

Let $g$ be a function on $\mathbb{R}$ with polynomial decay $|g(t)|\leq
C(1+|t|)^{-\sigma}$ for some $\sigma>1$. Assume that for every
$x\in\mathbb{R}$ the set $x+\alpha\mathbb{Z}$ contains a subset
$\\{k+\delta_{k}:k\in\mathbb{Z}\\}$ with the perturbation
$\delta_{k}=\delta_{k}(x)$ depending on $x$, such that the matrix $G$ with
entries $G_{kl}=g(k+\delta_{k}-l)$ is invertible on
$\ell^{\infty}(\mathbb{Z})$. Then $\mathcal{G}(g,\alpha,1)$ is a Gabor frame.

###### Proof.

The decay of $g$ implies that $G$ has sufficient off-diagonal decay to apply
Proposition 2.1(i). Thus spectral invariance asserts that the invertibility of
$G$ on $\ell^{\infty}(\mathbb{Z})$ implies that $G$ is also invertible on
$\ell^{2}(\mathbb{Z})$. Since
$x+\alpha\mathbb{Z}\supseteq\\{k+\delta_{k}:k\in\mathbb{Z}\\}$, we have

$\displaystyle\sum_{j\in\mathbb{Z}}\big{|}\sum_{l\in\mathbb{Z}}c_{l}g(x+\alpha
j-l)|^{2}$
$\displaystyle\geq\sum_{k\in\mathbb{Z}}\big{|}\sum_{l\in\mathbb{Z}}c_{l}g(k+\delta_{k}-l)|^{2}$
$\displaystyle=\|Gc\|_{2}^{2}\geq A_{x}\|c\|_{2}^{2}\,.$

The upper bound in (6) always holds due to the decay of $g$. This holds for
all $x$, therefore the condition (ii) of Theorem 2.3 implies that
$\mathcal{G}(g,\alpha,1)$ is a frame.

Proposition 2.4 says that a suitable submatrix of the pre-Gramian $P(x)$ is
invertible. Proposition 2.4 is related to the characterizations via sampling
in shift-invariant spaces that figure prominently in [18]. (In an equivalent
formulation, every set $x+\alpha\mathbb{Z}$ contains a perturbation of
$\mathbb{Z}$ that is interpolating in the shift-invariant space associated to
$g$.)

To prove the main theorem (Theorem 1.2), we will verify the conditions of
Proposition 2.4.

###  2.4. The Zak transform.

We recall the definition of the Zak transform
$Zg(x,\xi)=\sum_{k\in\mathbb{Z}}g(x-k)e^{2\pi ik\xi}$ of a function $g\in
L^{1}(\mathbb{R})$. More generally, the Zak transform with period $p>0$ is
defined by

$Z_{p}g(x,\xi)=\sum_{k\in\mathbb{Z}}g(x-pk)e^{2\pi ipk\xi}\,.$

The Zak transform is $\tfrac{1}{p}$-periodic in the second variable and quasi-
periodic in the first variable, i.e., for all $x,\xi\in\mathbb{R}$

$Z_{p}f\big{(}x+pk,\xi+\tfrac{l}{p}\big{)}=e^{2\pi ipk\xi}Z_{p}g(x,\xi)\,.$

Zak transforms of totally positive function possess only few zeros. This
important property was discovered only recently [27, 26, 39] and is crucial
for our arguments.

######  Proposition 2.5.

The Zak transform of a totally positive function $g$ possesses a unique zero
in $[0,1)^{2}$ that is assumed at $(x_{0},1/2)$ for some $x_{0}\in[0,1)$.

##  3\. Surjectivity.

For the proof of Theorem 1.2 we verify the sufficient condition of Proposition
2.4 for a totally positive function $g$. First we prove the surjectivity.
Notice that the arguments in this section hold for arbitrary values of
$\alpha\in(0,1)$.

######  Proposition 3.1.

Let $g$ be an arbitrary totally positive function in $L^{1}(\mathbb{R})$ and
assume that its Zak transform has its unique zero at $(x_{0},1/2)$. Let
$\epsilon\in(0,1/2)$, $M\in\mathbb{Z}$, and
$(\delta_{k})_{k\in\mathbb{Z}}\subseteq[x_{0}+M-1+\epsilon,x_{0}+M-\epsilon]$
be a sequence of perturbations. Then the matrix $G$ with entries
$G_{kl}=g(k+\delta_{k}-l),k,l\in\mathbb{Z}$, maps $\ell^{\infty}(\mathbb{Z})$
_onto_ $\ell^{\infty}(\mathbb{Z})$ and $\ell^{1}(\mathbb{Z})$ _onto_
$\ell^{1}(\mathbb{Z})$.

###### Proof.

For the proof we use the following fundamental result of de Boor, Friedland,
and Pinkus [8, Cor. 1]. _Assume that $G$ is an totally positive matrix that is
bounded on $\ell^{\infty}(\mathbb{Z})$111The original results are formulated
for sign-regular matrices and more general index sets.. If the range of $G$
contains a uniformly alternating vector, then $G$ is onto
$\ell^{\infty}(\mathbb{Z})$. _ This result is the key tool in our proofs.
Related results on the invertibility of infinite totally positive matrices can
be found in [4, 7, 10].

Uniformly alternating means that we need to find a sequence
$c\in\ell^{\infty}(\mathbb{Z})$ such that $u=Gc$ satisfies $u(k)u(k+1)<0$ for
all $k\in\mathbb{Z}$ and $\inf_{k\in\mathbb{Z}}|u(k)|>0$.

To accomplish this, we take $c_{l}=(-1)^{l}$ and compute $(Gc)_{k}$. This is

$\displaystyle(Gc)_{k}$
$\displaystyle=\sum_{l\in\mathbb{Z}}g(k+\delta_{k}-l)(-1)^{l}$
$\displaystyle=Zg(k+\delta_{k},\tfrac{1}{2})$
$\displaystyle=(-1)^{k}Zg(\delta_{k},\tfrac{1}{2})\,,$

where the last identity comes from the quasi-periodicity of $Zg$. Since
$Zg(x,\tfrac{1}{2})$ is real-valued and by assumption $Zg(x,\tfrac{1}{2})$
does not have any zeros on the interval $[x_{0}-1+\epsilon,x_{0}-\epsilon]$,
the numbers $Zg(\delta_{k},\tfrac{1}{2})$ all have the same sign and
$|Zg(\delta_{k},\tfrac{1}{2})|\geq\nu>0$ for all $k$. Consequently $u=Gc$ is
uniformly alternating.

To apply the result of [8], we observe that the matrix $G$ with entries
$g(k+\delta_{k}-l)$ is indeed totally positive in the sense that all minors of
$G$ of arbitrary dimension have a non-negative determinant. But this follows
from the definition (3) of total positivity.

Thus by [8, Cor. 1] the matrix $G$ is onto $\ell^{\infty}(\mathbb{Z})$. By
Proposition 2.2 $G$ is also onto $\ell^{1}(\mathbb{Z})$.

To apply the above proposition, we need to select a suitable subset of
$x+\alpha\mathbb{Z}$. This can always be done with the following lemma.

######  Lemma 3.2.

Let $\alpha<1$, $\epsilon<(1-\alpha)/2$, $M\in\mathbb{Z}$, $x_{0}\in[0,1]$
fixed, and $x\in[0,1]$ arbitrary.

(i) Then $x+\alpha\mathbb{Z}$ contains a subset
$\\{k+\delta_{k}:k\in\mathbb{Z}\\}$ with
$\delta_{k}\in[x_{0}+M-1+\epsilon,x_{0}+M-\epsilon]$ for all $k\in\mathbb{Z}$.

(ii) If $\alpha$ is rational, $\alpha=p/q$, then the perturbation $\delta_{k}$
can be chosen to be $p$-periodic, $\delta_{k+np}=\delta_{k}$ for all
$k,n\in\mathbb{Z}$.

###### Proof.

(i) For arbitrary $k\in\mathbb{Z}$ the interval
$[k+x_{0}-1+\epsilon,k+x_{0}-\epsilon]$ has length $1-2\epsilon>\alpha$ and
thus contains at least one point of $x+\alpha\mathbb{Z}$, which we can write
as $k+\delta_{k}$.

(ii) Let $\alpha=p/q\in\mathbb{Z}$. For $l=0,\dots,p-1$ choose an integer
$j_{l}\in\\{0,\dots,q-1\\}$ such that

$x+\tfrac{p}{q}j_{l}\in[l+x_{0}-1+\epsilon,l+x_{0}-\epsilon]$

and set

$\delta_{l}=x+\tfrac{p}{q}j_{l}-l\,.$

Clearly, $0\leq j_{0}<j_{1}<\dots<j_{p-1}<q$. Now let $m=l+np$ with
$l\in[0,p-1]\cap\mathbb{Z}$ and $n\in\mathbb{Z}$. Then
$x+\tfrac{p}{q}(j_{l}+nq)=x+\tfrac{p}{q}j_{l}+np\in[l+np+x_{0}-1+\epsilon,l+np+x_{0}-\epsilon]=[m+x_{0}-1+\epsilon,m+x_{0}-\epsilon]$,
and
$\delta_{m}=x_{0}+\tfrac{p}{q}(j_{l}+nq)-m=x_{0}+\tfrac{p}{q}(j_{l}+nq)-(l+np)=\delta_{l}$.
Thus $\delta_{k}$ is $p$-periodic.

##  4\. Injectivity.

For the surjectivity of $G$ we have used the fact that $g$ is totally
positive, but nothing about the parameter $\alpha$. Now we impose in addition
that $\alpha=p/q$ is rational. In this case the action of $G$ is unitarily
equivalent to a $p\times p$-matrix-valued function. This facilitates the
analysis, as for square matrices surjectivity is equivalent to injectivity and
to invertibility.

Let again $G$ be the matrix with entries $G_{kl}=g(k+\delta_{k}-l)$. Since
$\alpha=p/q\in\mathbb{Q}$, the sequence of perturbations can be chosen to be
$p$-periodic by Lemma 3.2. We now use the periodicity of $\delta_{k}$ to bring
in a variant of the Zibulski-Zeevi matrices [41]. We write $k=r+mp$ and
$l=s+np$ with $r,s=0,1,\dots,p-1$, and $m,n\in\mathbb{Z}$. Then
$\delta_{k}=\delta_{r}$ and for all $m\in\mathbb{Z}$ and $r=0,1,\dots,p-1$ we
have

$\displaystyle(Gc)_{k}$
$\displaystyle=\sum_{l\in\mathbb{Z}}c_{l}g(k+\delta_{k}-l)$ (7)
$\displaystyle=\sum_{s=0}^{p-1}\sum_{n\in\mathbb{Z}}c_{s+np}g(r+mp+\delta_{r}-s-np)=d_{r+mp}\,.$

For fixed $r,s$ the sum over $n$ is a convolution, so we may take Fourier
series and obtain a matrix-valued equation of functions. Write
$x_{s}(\xi)=\sum_{n\in\mathbb{Z}}c_{s+pn}e^{2\pi inp\xi}$ for the Fourier
series of the coefficient in the residue class $s$ and
$x(\xi)=(x_{0}(\xi),\dots,x_{p-1}(\xi))$ for the associated vector-valued
function. Likewise $y_{r}(\xi)=\sum_{m\in\mathbb{Z}}d_{r+pm}e^{2\pi imp\xi}$
and $y(\xi)=(y_{0}(\xi),\dots,y_{p-1}(\xi))$. The Fourier series of the
sequence involving $g$ is precisely the Zak transform of $g$, namely,

$\sum_{n\in\mathbb{Z}}g(r+\delta_{r}-s-np)e^{2\pi
inp\xi}=Z_{p}g(r+\delta_{r}-s,\xi)\,.$

Consequently, after taking Fourier series, (7) can be recast as

(8)
$\sum_{s=0}^{p-1}x_{s}(\xi)Z_{p}g(r+\delta_{r}-s,\xi)=y_{r}(\xi)\qquad\text{
for }r=0,1,\dots,p-1\,.$

Since $c\in\ell^{1}(\mathbb{Z})$ and $G$ is bounded on $\ell^{1}(\mathbb{Z})$,
(8) holds pointwise for all $\xi\in[0,1/p]$. Let $A(\xi)$ be the $p\times
p$-matrix-valued function with entries

$A_{rs}(\xi)=Z_{p}g(r+\delta_{r}-s,\xi)\qquad r,s=0,1,\dots,p-1\,.$

This matrix is related to the Zeevi-Zibulski matrix that occurs in many
criteria for Gabor frames over rational lattices [17, 41, 40]. The pointwise
identity (8) can be written as

(9) $A(\xi)x(\xi)=y(\xi)\,.$

We now translate the surjectivity of the infinite matrix $G$ to a property of
the matrix-valued function $\det A(\xi)$.

######  Proposition 4.1.

Assume that $\alpha=p/q$ is rational, $|g(t)|\leq C(1+|t|)^{-\sigma}$ for some
$C,\sigma>1$, and that $G$ maps $\ell^{1}(\mathbb{Z})$ _onto_
$\ell^{1}(\mathbb{Z})$. Then $G$ is one-to-one on $\ell^{1}(\mathbb{Z})$ and
thus invertible on $\ell^{1}(\mathbb{Z})$.

###### Proof.

The surjectivity of $G$ on $\ell^{1}(\mathbb{Z})$ implies in particular that
every vector $d=(d_{0},d_{1},\dots,d_{p-1})\in\mathbb{C}^{p}$, i.e,
$d\in\ell^{1}(\mathbb{Z}),d_{k}=0$ for $k<0$ and $k\geq p$ is in the range of
$G$. In this case $y_{r}(\xi)=\sum_{m\in\mathbb{Z}}d_{r+pm}e^{2\pi
imp\xi}=d_{r}$ and the vector-valued function $y(\xi)=d$ is constant. Due to
the surjectivity of $G$ there exists a sequence
$c=c(d)\in\ell^{1}(\mathbb{Z})$ with associated Fourier series $x^{(d)}(\xi)$,
such that $Gc=d$. In view of (9)

$A(\xi)x^{(d)}(\xi)=d\quad\quad\text{ for all }\xi\in[0,1/p]\,.$

Since $d\in\mathbb{C}^{p}$ was arbitrary, this means that for fixed $\xi$ the
$p\times p$-matrix is onto $\mathbb{C}^{p}$. Consequently, $A(\xi)$ is one-to-
one and thus invertible for every $\xi\in[0,1/p]$.

Now assume that $Gc=0$ for some $c\in\ell^{1}(\mathbb{Z})$. Then
$A(\xi)x(\xi)=0$ for all $\xi\in[0,1]$. Since $A(\xi)$ is invertible, this
implies that $x(\xi)\in\mathbb{C}^{p}$ must be the zero vector for all $\xi$.
Consequently, $x\equiv 0$ and thus $c=0$. We have proved that $G$ is one-to-
one on $\ell^{1}(\mathbb{Z})$, whence $G$ is invertible on
$\ell^{1}(\mathbb{Z})$.

We finally summarize the steps that yield the proof of our main theorem.

###### Proof of Theorem 1.2.

By Lemma 3.2 we can extract a set $\\{k+\delta_{k}:k\in\mathbb{Z}\\}$ from
every $x+\alpha\mathbb{Z}$, such that $\delta_{k}$ avoids the zero $x_{0}$ of
the Zak transform $Zg$. Then by Proposition 3.1 the matrix
$G=\big{(}g(k+\delta_{k}-l)\big{)}_{k,l\in\mathbb{Z}}$ is onto
$\ell^{1}(\mathbb{Z})$.

For rational values of $\alpha$ the matrix $G$ is also one-to-one on
$\ell^{1}(\mathbb{Z})$ by Proposition 4.1. Consequently, $G$ is invertible on
$\ell^{1}(\mathbb{Z})$.

Finally, the spectral invariance guaranteed by Proposition 2.1(i) implies that
$G$ is invertible on $\ell^{\infty}(\mathbb{Z})$. This is precisely the
sufficient condition of Proposition 2.4 to guarantee that
$\mathcal{G}(g,\alpha,1)$ is a frame.

We are done!

Alternatively, one could give Proposition 4.1 a more structural touch. We use
$T_{p}$ for the translation operator on sequences defined by
$(T_{p}c)_{k}=c_{k-p}$ and observe that the underlying matrix $G$ of
Proposition 4.1 commutes with $T_{p}$.

######  Proposition 4.2.

Let $G=(G_{kl})_{k,l\in\mathbb{Z}}$ be a bi-infinite matrix with off-diagonal
decay

$|G_{kl}|\leq C(1+|k-l|)^{-\sigma}\qquad k,l\in\mathbb{Z}\,,$

for some $\sigma>1$. Assume that $G$ commutes with the translation operator
$T_{p}$ for some $p\in\mathbb{N}$. If $G$ is onto $\ell^{1}(\mathbb{Z})$, then
$G$ is one-to-one on $\ell^{1}(\mathbb{Z})$ and thus invertible.

The proof is similar to the proof of Proposition 4.1.

## References

  * [1] A. Aldroubi, A. G. Baskakov, and I. A. Krishtal.  Slanted matrices, Banach frames, and sampling.  J. Funct. Anal., 255:1667–1691, 2008.
  * [2] A. G. Baskakov.  Wiener’s theorem and asymptotic estimates for elements of inverse matrices.  Funktsional. Anal. i Prilozhen., 24(3):64–65, 1990.
  * [3] Y. Belov, A. Kulikov, and Y. Lyubarskii.  Gabor frames for rational functions.  Invent. Math., 2022.  doi.org/10.1007/s00222-022-01151-8.
  * [4] A. S. Cavaretta, Jr., W. Dahmen, C. A. Micchelli, and P. W. Smith.  On the solvability of certain systems of linear difference equations.  SIAM J. Math. Anal., 12(6):833–841, 1981.
  * [5] X.-R. Dai and Q. Sun.  The $abc$-problem for Gabor systems.  Mem. Amer. Math. Soc., 244(1152):ix+99, 2016.
  * [6] X.-R. Dai and M. Zhu.  Frame set for Gabor systems with Haar window.  Preprint, 2022.  arXiv:2205.06479.
  * [7] C. de Boor.  The inverse of a totally positive bi-infinite band matrix.  Trans. Amer. Math. Soc., 274(1):45–58, 1982.
  * [8] C. de Boor, S. Friedland, and A. Pinkus.  Inverses of infinite sign regular matrices.  Trans. Amer. Math. Soc., 274(1):59–68, 1982.
  * [9] E. Cordero and L. Rodino.  Time-frequency analysis of operators, volume 75 of De Gruyter Studies in Mathematics.  De Gruyter, Berlin, [2020] ©2020.
  * [10] S. Demko.  Surjectivity and invertibility properties of totally positive matrices.  Linear Algebra Appl., 45:13–20, 1982.
  * [11] H. G. Feichtinger and N. Kaiblinger.  Varying the time-frequency lattice of Gabor frames.  Trans. Amer. Math. Soc., 356(5):2001–2023 (electronic), 2004.
  * [12] H. G. Feichtinger and T. Strohmer, editors.  Gabor analysis and algorithms: theory and applications.  Birkhäuser Boston, Boston, MA, 1998.
  * [13] H. G. Feichtinger and T. Strohmer, editors.  Advances in Gabor analysis.  Applied and Numerical Harmonic Analysis. Birkhäuser Boston Inc., Boston, MA, 2003.
  * [14] K. Gröchenig.  Foundations of time-frequency analysis.  Birkhäuser Boston Inc., Boston, MA, 2001.
  * [15] K. Gröchenig.  Wiener’s lemma: Theme and variations. An introduction to spectral invariance.  In B. Forster and P. Massopust, editors, Four Short Courses on Harmonic Analysis, Appl. Num. Harm. Anal. Birkhäuser, Boston, 2010.
  * [16] K. Gröchenig.  The mystery of Gabor frames.  J. Fourier Anal. Appl., 20(4):865–895, 2014.
  * [17] K. Gröchenig and S. Koppensteiner.  Gabor frames: characterizations and coarse structure.  In New trends in applied harmonic analysis. Vol. 2—Harmonic analysis, geometric measure theory, and applications, Appl. Numer. Harmon. Anal., pages 93–120. Birkhäuser/Springer, Cham, [2019] ©2019.
  * [18] K. Gröchenig, J. L. Romero, and J. Stöckler.  Sampling theorems for shift-invariant spaces, Gabor frames, and totally positive functions.  Invent. Math., 211(3):1119–1148, 2018.
  * [19] K. Gröchenig and J. Stöckler.  Gabor frames and totally positive functions.  Duke Math. J., 162(6):1003–1031, 2013.
  * [20] C. Heil.  History and evolution of the density theorem for Gabor frames.  J. Fourier Anal. Appl., 13(2):113–166, 2007.
  * [21] A. J. E. M. Janssen.  Duality and biorthogonality for Weyl-Heisenberg frames.  J. Fourier Anal. Appl., 1(4):403–436, 1995.
  * [22] A. J. E. M. Janssen.  Some Weyl-Heisenberg frame bound calculations.  Indag. Math., 7:165–182, 1996.
  * [23] A. J. E. M. Janssen.  Zak transforms with few zeros and the tie.  In Advances in Gabor Analysis. Birkhäuser Boston, Boston, MA, 2002\.
  * [24] A. J. E. M. Janssen.  On generating tight Gabor frames at critical density.  J. Fourier Anal. Appl., 9(2):175–214, 2003.
  * [25] A. J. E. M. Janssen and T. Strohmer.  Hyperbolic secants yield Gabor frames.  Appl. Comput. Harmon. Anal., 12(2):259–267, 2002.
  * [26] T. Kloos.  Zeros of the Zak transform of totally positive functions.  J. Fourier Anal. Appl., 21(5):1130–1145, 2015.
  * [27] T. Kloos and J. Stöckler.  Zak transforms and Gabor frames of totally positive functions and exponential B-splines.  J. Approx. Theory, 184:209–237, 2014.
  * [28] Y. I. Lyubarskiĭ.  Frames in the Bargmann space of entire functions.  In Entire and subharmonic functions, pages 167–180. Amer. Math. Soc., Providence, RI, 1992.
  * [29] A. Ron and Z. Shen.  Weyl–Heisenberg frames and Riesz bases in ${L}_{2}({\mathbb{R}}^{d})$.  Duke Math. J., 89(2):237–282, 1997.
  * [30] W. Rudin.  Functional analysis.  McGraw-Hill Book Co., New York, 1973.  McGraw-Hill Series in Higher Mathematics.
  * [31] I. J. Schoenberg.  On Pólya frequency functions. I. The totally positive functions and their Laplace transforms.  J. Analyse Math., 1:331–374, 1951.
  * [32] I. J. Schoenberg and A. Whitney.  On Pólya frequence functions. III. The positivity of translation determinants with an application to the interpolation problem by spline curves.  Trans. Amer. Math. Soc., 74:246–259, 1953.
  * [33] K. Seip.  Density theorems for sampling and interpolation in the Bargmann-Fock space. I.  J. Reine Angew. Math., 429:91–106, 1992.
  * [34] K. Seip and R. Wallstén.  Density theorems for sampling and interpolation in the Bargmann-Fock space. II.  J. Reine Angew. Math., 429:107–113, 1992.
  * [35] C. E. Shin and Q. Sun.  Stability of localized operators.  J. Funct. Anal., 256(8):2417–2439, 2009.
  * [36] J. Sjöstrand.  Wiener type algebras of pseudodifferential operators.  In Séminaire sur les Équations aux Dérivées Partielles, 1994–1995, pages Exp. No. IV, 21. École Polytech., Palaiseau, 1995.
  * [37] Q. Sun.  Wiener’s lemma for infinite matrices.  Trans. Amer. Math. Soc., 359(7):3099–3123 (electronic), 2007.
  * [38] R. Tessera.  Left inverses of matrices with polynomial decay.  J. Funct. Anal., 259(11):2793–2813, 2010.
  * [39] O. L. Vinogradov and A. Y. Ulitskaya.  Zeros of the Zak transform of averaged totally positive functions.  J. Approx. Theory, 222:55–63, 2017.
  * [40] Y. Y. Zeevi, M. Zibulski, and M. Porat.  Multi-window Gabor schemes in signal and image representations.  In Gabor analysis and algorithms, pages 381–407. Birkhäuser Boston, Boston, MA, 1998.
  * [41] M. Zibulski and Y. Y. Zeevi.  Analysis of multiwindow Gabor-type schemes by frame methods.  Appl. Comput. Harmon. Anal., 4(2):188–221, 1997.