# On Streaming Codes for Burst and Random Errors

Shobhit Bhatnagar and P. Vijay Kumar
Department of Electrical Communication Engineering, IISc Bangalore
<EMAIL_ADDRESS>
This research is supported by the "Next Generation Wireless Research and
Standardization on 5G and Beyond" project funded by MeitY, SERB Grant No.
CRG/2021/008479 and a Qualcomm Innovation Fellowship India 2021.

###### Abstract

Streaming codes (SCs) are packet-level codes that recover erased packets
within a strict decoding-delay deadline. Streaming codes for various packet
erasure channel models such as sliding-window (SW) channel models that admit
random or burst erasures in any SW of a fixed length have been studied in the
literature, and the optimal rate as well as rate-optimal code constructions of
SCs over such channel models are known. In this paper, we study error-
correcting streaming codes ($\text{SC}_{\text{\tiny ERR}}$s), i.e., packet-
level codes which recover erroneous packets within a delay constraint. We
study $\text{SC}_{\text{\tiny ERR}}$s for two classes of SW channel models,
one that admits random packet errors, and another that admits multiple bursts
of packet errors, in any SW of a fixed length. For the case of random packet
errors, we establish the equivalence of an $\text{SC}_{\text{\tiny ERR}}$ and
a corresponding SC that recovers from random packet erasures, thus determining
the optimal rate of an $\text{SC}_{\text{\tiny ERR}}$ for this setting, and
providing a rate-optimal code construction for all parameters. We then focus
on SCs that recover from multiple erasure bursts and derive a rate-upper-bound
for such SCs. We show the necessity of a divisibility constraint for the
existence of an SC constructed by the popular diagonal embedding technique,
that achieves this rate-bound under a stringent delay requirement. We then
show that a construction known in the literature achieves this rate-bound when
the divisibility constraint is met. We further show the equivalence of the SCs
considered and $\text{SC}_{\text{\tiny ERR}}$s for the setting of multiple
error bursts, under a stringent delay requirement.

##  I Introduction

Erasure-correcting streaming codes, or simply streaming codes (abbreviated as
SCs) as they are called in the literature, are packet-level FEC codes that
recover erased packets within a strict decoding-delay constraint. They are
thus relevant to the current emphasis on low-latency communication. Streaming
codes were first studied by Martinian et al. [1, 2] for the setting of a
sliding-window (SW) channel model that allowed a single erasure burst within
any sliding-window of a fixed length. They also introduced the technique of
diagonal embedding (DE) which allows one to construct packet-level codes from
scalar block codes. This work was then extended in [3] where the authors
considered a SW channel model that allowed either a single erasure burst, or
else a few random erasures, in any sliding-window. The optimal rate and rate-
optimal code constructions employing DE for this channel model are known for
all valid parameters [4, 5]. Since scalar block codes can be used to construct
packet-level codes via DE, authors in [6] studied the rate-delay trade-off for
a class of linear block codes that recover from multiple erasure bursts within
a delay constraint. They also presented a code construction that achieves this
trade-off. We refer the reader to [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 23, 24, 25] for the study of streaming codes for various
settings and channel models.

In this paper, we study streaming codes for errors, i.e., packet-level codes
that recover erroneous packets within a decoding-delay deadline. We will refer
to such streaming codes as error-correcting streaming codes (abbreviated as
$\text{SC}_{\text{\tiny ERR}}$s).

_Our Contribution_ : We study $\text{SC}_{\text{\tiny ERR}}$s for burst and
random errors. We establish the equivalence of an $\text{SC}_{\text{\tiny
ERR}}$ for a SW channel model that allows $\leq a$ random packet errors in any
SW of length $w,$ and a corresponding SC for a SW channel model that allows
$\leq 2a$ random packet erasures in any SW of length $w.$ Through this
equivalence, and results known in prior literature, we characterize the
maximum rate of an $\text{SC}_{\text{\tiny ERR}}$ for this setting and also
provide a linear field size, rate-optimal code construction for all
parameters. We then focus on SCs that recover from multiple erasure bursts.
The code construction that achieves the rate-delay trade-off established in
[6] is causal only under a divisibility constraint. We show the necessity of
this divisibility constraint. We then derive an upper-bound to the rate of an
SC for a SW channel model that allows multiple erasure bursts within any SW of
length $w$, and show that under a stringent delay requirement, one can achieve
this bound via DE iff the parameters of the SW channel satisfy the
corresponding divisibility constraint. Then, again for the case of a stringent
delay requirement, we show the equivalence of $\text{SC}_{\text{\tiny ERR}}$s
for SW channels that admit multiple burst errors in any SW of length $w$, and
SCs for SW channels that admit double the number of burst erasures in any SW
of length $w$.

The organization of the paper is as follows. In Section II we provide the
necessary background on SCs and describe the framework for
$\text{SC}_{\text{\tiny ERR}}$s. In Section III we determine the optimal rate
of an $\text{SC}_{\text{\tiny ERR}}$ that recovers from random packet errors.
We discuss $\text{SC}_{\text{\tiny ERR}}$s for multiple bursts of packet
errors Section IV.

##  II Background and Related Prior Work

Notation: Given integers $m,n$, we will use $[m:n]$ to denote the set
$\\{m,m+1,\dots,n\\}$. We will use $\underline{0}_{n}$ to denote the zero
vector of length $n,$ and $I_{n}$ to denote the $(n\times n)$ identity matrix.
For matrix $A\in\mathbb{F}^{m\times n}_{q}$, and
$\mathcal{I}\subseteq[0:m-1],~{}\mathcal{J}\subseteq[0:n-1]$,
$A(\mathcal{I},\mathcal{J})$ denotes the sub-matrix of $A$ consisting of the
rows indexed by $\mathcal{I}$ and the columns indexed by $\mathcal{J}$. For
$i\in[0:m-1]$ and $j\in[0:n-1]$, $A(i,:)$ and $A(:,j)$ denote the $i$-th row
and the $j$-th column of $A,$ respectively. Similarly, $A(\mathcal{I},:)$ and
$A(:,\mathcal{J})$ denote the sub-matrices of $A$ consisting of the rows
indexed by $\mathcal{I}$ and the columns indexed by $\mathcal{J}$,
respectively. We will at times use $A_{j}$ to denote the $j$-th column of $A$.
For a vector
$\underline{v}=[v_{0},v_{1},\dots,v_{n-1}]^{T}\in\mathbb{F}_{q}^{n},$ we will
use $\text{supp}(\underline{v})$ to denote the support of $\underline{v},$
i.e., $\text{supp}(\underline{v})=\\{i~{}|~{}v_{i}\neq 0\\}$. We will use
$w_{H}(\underline{v})$ to denote the Hamming weight of $\underline{v},$ i.e.,
$w_{H}(\underline{v})=|\text{supp}(\underline{v})|$.

We will say that an $[n,k]$ code $\mathcal{C}$ is systematic if its generator
matrix $G$ is of the form $G=[I_{k}\ |\ P]\in\mathbb{F}^{k\times n}_{q}$. We
will call a parity-check matrix $H$ of a systematic code to be in systematic
form if it is of the form $H=[P^{\prime}\ |\
I_{n-k}]\in\mathbb{F}^{(n-k)\times n}_{q}$. An $[n,k]$ code $\mathcal{C}$ is
said to be causal if its generator matrix $G$ is of the form $G=[U_{k\times
k}~{}|~{}P]\in\mathbb{F}^{k\times n}_{q},$ where $U$ is upper-triangular.
Clearly, a systematic code is always causal.

In the context of an $[n,k]$ block code $\mathcal{C}$, an erasure pattern
$\underline{e}=[e_{0},e_{1},\dots,e_{n-1}]^{T}\in\\{0,1\\}^{n}$ signifies that
$c_{i},~{}i\in\text{supp}(\underline{e})$ is erased, and
$c_{i},~{}i\in[0:n-1]\setminus\text{supp}(\underline{e})$ is not erased, from
a codeword $\underline{c}^{T}=[c_{0},c_{1},\dots,c_{n-1}]\in\mathcal{C}.$ Let
$\underline{{c}}^{T}=[{c}_{0},{c}_{1},\dots,{c}_{n-1}]$ be the codeword
corresponding to the message vector
$\underline{{u}}=[{u}_{0},{u}_{1},\dots,{u}_{k-1}]^{T}$. Then, for
$i\in[0:k-1],~{}u_{i}$ is said to be recoverable from $\underline{e}$ within
delay $\tau$ if it can be recovered using the non-erased code symbols in
$\\{{c}_{0},{c}_{1},\dots,{c}_{\min\\{i+\tau,n-1\\}}\\}.$ Similarly, for
$i\in[0:n-1],~{}{c}_{i}$ is said to be recoverable from $\underline{e}$ within
delay $\tau$ if it can be recovered using the non-erased code symbols in
$\\{{c}_{0},{c}_{1},\dots,{c}_{\min\\{i+\tau,n-1\\}}\\}.$ The code
$\mathcal{C}$ is said to be delay-$\tau$ decodable for $\underline{e}$ if for
all $\underline{u}=[u_{0},u_{1},\dots,u_{k-1}]^{T}\in\mathbb{F}^{k}_{q}$ and
for all $i\in[0:k-1],$ $u_{i}$ is recoverable from $\underline{e}$ within
delay $\tau$.

Whenever we talk about an $[n,k]$ systematic code $\mathcal{C}$ being
delay-$\tau$ decodable for an erasure pattern(s), where $\tau\in[k:n-1],$ we
will use the notation $H^{(i)}\triangleq
H([0:\tau-k+i],[0:\tau+i]),~{}i\in[0:n-\tau-2],$ and $H^{(i)}\triangleq
H,~{}i\in[n-\tau-1:n-1]$, where $H$ is the parity-check matrix of
$\mathcal{C}$ in systematic form.

Figure 1: An admissible erasure pattern of the $(3,2,7)$-MBSW channel. Colored
squares denote erasures.

###  II-A Erasure-Correcting Streaming Codes

####  II-A0a Framework [1]

At each time instant $t\in\mathbb{N}\bigcup\\{0\\},$ the encoder of a
streaming code receives a message packet
$\underline{u}(t)=[u_{1}(t),u_{2}(t),\dots,u_{k}(t)]^{T}\in\mathbb{F}^{k}_{q},$
and produces a coded packet
$\underline{x}(t)=[x_{1}(t),x_{2}(t),\dots,x_{n}(t)]^{T}\in\mathbb{F}^{n}_{q}.$
In other words, a message packet contains $k$ symbols from $\mathbb{F}_{q},$
and a coded packet contains $n$ symbols from $\mathbb{F}_{q}.$ We will assume
that $\underline{u}(t)=\underline{0}_{k},$ for $t<0.$ The streaming code
encoder is causal, i.e., $\underline{x}(t)$ is a function of only prior
message packets $\underline{u}(0),\underline{u}(1),\dots,\underline{u}(t)$.
The coded packet $\underline{x}(t)$ is then transmitted over a packet erasure
channel, so that at time $t,$ the receiver receives

$\underline{y}(t)=\begin{cases}\underline{x}(t),~{}\text{if}~{}\underline{x}(t)\text{~{}is
not erased,}\\\ \wedge,~{}\text{if}~{}\underline{x}(t)\text{~{}is
erased.}\end{cases}$

Here, we use the symbol $\wedge$ to denote an erased packet. A delay-
constrained decoder at the receiver must recover $\underline{u}(t)$ using
$\\{\underline{y}(0),\underline{y}(1),\dots,\underline{y}(t+\tau)\\}$ only,
where $\tau$ denotes the decoding-delay constraint, for all $t\geq 0$. Packet-
level codes satisfying this requirement will be called erasure-correcting
streaming codes, or simply, streaming codes (abbreviated as SCs). The rate of
the SC is defined to be $\frac{k}{n}$.

In the context of packet-level codes, an erasure pattern
$\underline{e}=(e_{0},e_{1},\dots),$ where $e_{t}\in\\{0,1\\}$ for all $t,$
denotes that $\underline{x}(t)$ is erased if $e_{t}=1,$ and $\underline{x}(t)$
is not erased if $e_{t}=0$. We will also use the notation
$\text{supp}(\underline{e})$ to denote the set of time indices of erased
packets, i.e., $\text{supp}(\underline{e})=\\{t~{}|~{}e_{t}=1\\}$.

####  II-A0b $(a,w)$-SW Channel

An $(a,w)$-SW channel is a packet erasure channel that produces only those
erasure patterns having the property that any sliding window of $w$ time slots
contains $\leq a$ erased packets, i.e., $\forall t\geq
0,~{}w_{H}([e_{t},e_{t+1},\dots,e_{t+w-1}])\leq a$ for any erasure pattern
$\underline{e}=(e_{0},e_{1},\dots)$ of the $(a,w)$-SW channel. Such erasure
patterns will be called admissible erasure patterns of the $(a,w)$-SW channel.
We will denote a streaming code for the $(a,w)$-SW channel under delay
constraint $\tau$ by an $(a,w,\tau)$-streaming code (abbreviated as
$(a,w,\tau)$-SC). Following the arguments in [3], one can assume
$\tau\geq(w-1)$ w.o.l.o.g., and that an $(a,w,\tau)$-SC of non-zero rate can
be constructed iff $a<w$, which we will assume throughout to be the case. The
optimal rate of an $(a,w,\tau)$-SC is given by $\frac{w-a}{w}$ [3, 4].
Further, the streaming code constructed via diagonal embedding (described
later) of a $[w,w-a]$ MDS code results in a linear field size, rate-optimal
$(a,w,\tau=w-1)$-SC for all valid parameters [3, 4].

####  II-A0c Multiple Burst-Erasure Sliding Window Channel

By a $(z,b,w)$-Multiple Burst-Erasure Sliding-Window channel (abbreviated as
$(z,b,w)$-MBSW channel), we will mean a packet erasure channel that allows
only those erasure patterns having the property that the pattern observed in
any sliding window of length $w$ can be described as a $(z,b)$-burst, by which
we mean that the pattern observed in any sliding window of length $w$ can be
described as consisting of $\leq z$ (non-overlapping) erasure bursts, each of
length $\leq b$. Erasure patterns which satisfy this requirement will be
called admissible erasure patterns of the $(z,b,w)$-MBSW channel (see Fig. 1
for an example). We remark here that the definition of burst erasures
considered in this work does not restrict a burst erasure to necessarily
consist only of consecutive erasures, i.e., there can be unerased packets
within a burst.

We will denote a streaming code for the $(z,b,w)$-MBSW channel under delay
constraint $\tau$ by a $(z,b,w,\tau)$-streaming code (abbreviated as
$(z,b,w,\tau)$-SC). Once again, one can assume w.o.l.o.g. that
$\tau\geq(w-1)$. Rate-optimal $(1,b,w,\tau)$-SC constructions are known for
all valid parameters [1, 2], and hence we will consider the case $z>1$
throughout the paper. Further, a streaming code of non-zero rate over the
$(z,b,w)$-MBSW channel can be constructed only if $w>zb,$ which we will assume
throughout the paper. Finally, we will consider the case $b>1,$ since the case
$b=1$ corresponds to random erasures so that the $(z,1,w)$-MBSW channel
reduces to the $(z,w)$-SW channel.

Prior work on constructing linear codes that recover from multiple erasure
bursts within a delay constraint was done in [6]. The authors showed that one
can construct an $[n=(k+zb),k]$ code $\mathcal{C}$ that is delay-$\tau$
decodable for any $(z,b)$-burst iff
$\tau\geq\tau^{*}\triangleq\max\\{k+(z-1)b,zb\\}.$ They also provided a code
construction that matches this delay bound. However, a close examination of
this construction shows that the constructed code is causal only if
$b|\tau^{*},$ and further that in this case, one can construct a systematic
code. The authors also showed, in particular, that it is not possible to
construct an $[n=k+zb,k]$ causal block code that is delay-$\tau^{*}$ decodable
for all $(z,b)$-bursts, when $z>1$ and $k=(b+1).$ In Theorem 3 below, we will
generalize this result to all $k>b$ such that $b\nmid k$.

####  II-A0d Diagonal Embedding

In diagonal embedding, codewords of an $[n,k]$ systematic code $\mathcal{C}$
are placed diagonally in the coded packet stream. See Fig. 2 for an example.
More formally, if $G=[I_{k}\ |\ P]$ is a generator matrix of $\mathcal{C}$,
then a stream of $n$ packets in a rate $\frac{k}{n}$ streaming code
constructed via DE of $\mathcal{C}$ is of the form
$[x_{1}(t),x_{2}(t+1),\dots,x_{n}(t+n-1)]=[u_{1}(t),u_{2}(t+1),\dots,u_{k}(t+k-1)]G$.
Thus, DE translates packet erasures to codeword symbol erasures. In this
paper, we will mostly focus on DE-based code constructions since it is the
most popular technique in streaming code literature.

$x_{1}(t)$ |  $x_{1}(t+1)$ |  $x_{1}(t+2)$ |  |  |  |
---|---|---|---|---|---|---
|  $x_{2}(t+1)$ |  $x_{2}(t+2)$ |  $x_{2}(t+3)$ |  |  |
|  |  $x_{3}(t+2)$ |  $x_{3}(t+3)$ |  $x_{3}(t+4)$ |  |
|  |  |  $x_{4}(t+3)$ |  $x_{4}(t+4)$ |  $x_{4}(t+5)$ |
|  |  |  |  $x_{5}(t+4)$ |  $x_{5}(t+5)$ |  $x_{5}(t+6)$

Figure 2: DE of a $[5,2]$ systematic code $\mathcal{C}$. Each column is a
coded packet and every diagonal of the same color is a codeword of
$\mathcal{C}$.

###  II-B Error-Correcting Streaming Codes

####  II-B0a Framework

At each time $t\in\mathbb{N}\bigcup\\{0\\},$ the encoder receives a message
packet
$\underline{u}(t)=[u_{1}(t),u_{2}(t),\dots,u_{k}(t)]^{T}\in\mathbb{F}^{k}_{q},$
and produces a coded packet
$\underline{x}(t)=[x_{1}(t),x_{2}(t),\dots,x_{n}(t)]^{T}\in\mathbb{F}^{n}_{q}.$
We will assume that $\underline{u}(t)=\underline{0}_{k},$ for $t<0.$ Once
again, the encoder is causal, i.e., $\underline{x}(t)$ is a function only of
prior message packets
$\underline{u}(0),\underline{u}(1),\dots,\underline{u}(t)$. The coded packet
$\underline{x}(t)$ is then transmitted over a packet error channel, so that at
time $t,$ the receiver receives

$\underline{y}(t)=\underline{x}(t)+\underline{e}(t),$

where $\underline{e}(t)\in\mathbb{F}_{q}^{n}$ (See Fig. 3). A delay-
constrained decoder at the receiver must recover $\underline{u}(t)$ using
$\\{\underline{y}(0),\underline{y}(1),\dots,\underline{y}(t+\tau)\\}$ only,
where $\tau$ denotes the decoding-delay constraint, for all $t\geq 0$. Packet-
level codes that satisfy this requirement will be called error-correcting
streaming codes (abbreviated as $\text{SC}_{\text{\tiny ERR}}$s). The rate of
the $\text{SC}_{\text{\tiny ERR}}$ is defined to be $\frac{k}{n}$.

An error pattern $E=(\underline{e}(0),\underline{e}(1),\dots)$ signifies that
$\underline{y}(t)=\underline{x}(t)+\underline{e}(t),~{}\forall t.$ We will use
the notation $\text{supp}(E)$ to denote the set of time indices at which non-
trivial packet errors occur, i.e.,
$\text{supp}(E)=\\{t~{}|~{}\underline{e}(t)\neq 0\\}$.

####  II-B0b $(a,w)$-Error SW Channel

An $(a,w)$-Error SW channel (abbreviated as $(a,w)$-$\text{SW}_{\text{\tiny
ERR}}$ channel) is a packet error channel that produces only those error
patterns having the property that any sliding window of $w$ time slots
contains $\leq a$ packet errors. Alternatively, one can define an
$(a,w)$-$\text{SW}_{\text{\tiny ERR}}$ channel as a packet error channel that
allows only those error patterns $E$ having the property that the erasure
pattern $\underline{e}=(e_{0},e_{1},\dots)$ defined as $e_{t}=1$ if
$t\in\text{supp}(E),$ and $e_{t}=0,$ otherwise, is admissible in the
$(a,w)$-SW channel.

We will denote a streaming code for the $(a,w)$-$\text{SW}_{\text{\tiny ERR}}$
channel under delay constraint $\tau$ by an $(a,w,\tau)$-error-correcting
streaming code (abbreviated as $(a,w,\tau)$-$\text{SC}_{\text{\tiny ERR}}$).
Following similar arguments as in [3], one can assume w.o.l.o.g. that
$\tau\geq(w-1)$. From the equivalence of an
$(a,w,\tau)$-$\text{SC}_{\text{\tiny ERR}}$ and a $(2a,w,\tau)$-SC that we
will show later in Theorem 1, it follows that one can construct a streaming
code of non-zero rate over the $(a,w)$-$\text{SW}_{\text{\tiny ERR}}$ channel
only if $2a<w,$ which we will assume throughout the paper.

####  II-B0c Multiple Burst-Error Sliding Window Channel

By a $(z,b,w)$-Multiple Burst-Error Sliding-Window channel (abbreviated as
$(z,b,w)$-$\text{MBSW}_{\text{\tiny ERR}}$ channel), we will mean a packet
error channel that allows only those error patterns $E$ having the property
that the erasure pattern $\underline{e}=(e_{0},e_{1},\dots)$ defined as
$e_{t}=1$ if $t\in\text{supp}(E),$ and $e_{t}=0,$ otherwise, is admissible in
the $(z,b,w)$-MBSW channel. We will denote a streaming code for the
$(z,b,w)$-$\text{MBSW}_{\text{\tiny ERR}}$ channel under delay constraint
$\tau$ by a $(z,b,w,\tau)$-error-correcting streaming code (abbreviated as
$(z,b,w,\tau)$-$\text{SC}_{\text{\tiny ERR}}$). Once again, one can assume
w.o.l.o.g. that $\tau\geq(w-1)$. We will also assume $b>1,$ since the case
$b=1$ corresponds to random errors so that the
$(z,1,w)$-$\text{MBSW}_{\text{\tiny ERR}}$ channel reduces to the
$(z,w)$-$\text{SW}_{\text{\tiny ERR}}$ channel.

Figure 3: Setting of error-correcting streaming codes.

###  II-C Preliminaries

We will use the following straightforward lemma.

######  Lemma 1.

Let $\mathcal{C}$ be an $[n,k]$ code and let $H$ be an $(n-k)\times n$ parity-
check matrix of $\mathcal{C}$. Let the coordinates in
$\mathcal{E}\subseteq[0:n-1]$ be erased from $\mathcal{C}$, and let
$i\in\mathcal{E}$. Then, the $i$-th code symbol in any codeword can be
recovered from the code symbols corresponding to the coordinates in
$[0:n-1]\setminus\mathcal{E}$ iff

$H_{i}\notin\textnormal{span}\langle\\{H_{j}\ |\
j\in\mathcal{E}\setminus\\{i\\}\\}\rangle.$

It follows from Lemma 1 that an $[n,k]$ code $\mathcal{C}$ can recover from an
erasure pattern $\underline{e}$ whose support is given by
$\mathcal{E}\subseteq[0:n-1]$ iff $\\{H_{j}\ |\ j\in\mathcal{E}\\}$ is a
linearly independent set, where $H$ is a parity-check matrix of $\mathcal{C}$.
As explained in [4], if $\mathcal{C}$ is a delay-$\tau$ decodable code for an
error pattern(s), and
$\underline{c}^{T}=[c_{0},c_{1},\dots,c_{n-1}]\in\mathcal{C}$, then to recover
code symbol $c_{i}$ such that $i+\tau<n-1$, one must consider the parity-check
matrix of the code obtained by puncturing $\mathcal{C}$ on the coordinates
$[i+\tau+1:n-1],$ i.e., the parity-check matrix of the code obtained from
$\mathcal{C}$ be deleting the coordinates $[i+\tau+1:n-1]$ from every codeword
of $\mathcal{C}$. Since the dual of a punctured code is a shortened code, as
explained in [4], to find a parity-check matrix of the punctured code, we
first find a basis for the subspace of the row-space of $H$ which has the
property that for every $\underline{v}^{T}=[v_{0},v_{1},\dots,v_{n-1}]$ in the
subspace, $v_{\lambda}=0,~{}\lambda\in[i+\tau+1:n-1]$, and then we delete the
coordinates $[i+\tau+1:n-1]$ from every vector in the basis. Specifically, if
$\mathcal{C}$ is a systematic code, and $H$ is its parity-check matrix in
systematic form, then the parity-check matrix of the code obtained from
$\mathcal{C}$ by puncturing $\mathcal{C}$ on the coordinates $[i+\tau+1:n-1]$
is given by $H^{(i)}$, when $\tau\geq k$. Thus, $c_{i}$ is recoverable form
$\underline{e}$ within delay $\tau$ iff
$H^{(i)}_{i}\notin\textnormal{span}\langle\\{H^{(i)}_{j}\ |\
j\in{\mathcal{E}}\setminus\\{i\\}\\}\rangle.$

Lemmas 2 and 3 below are proved in the appendix. Lemma 2 below uses Lemma 1 to
identify certain full-rank sub-matrices of the parity-check matrix in
systematic form, of an $[n=k+zb,k]$ systematic code that can recover from any
$(z,b)$-burst.

######  Lemma 2.

Let $\mathcal{C}$ be an $[n=k+zb,k]$ systematic code that can recover from any
$(z,b)$-burst, and let $H$ be its parity-check matrix in systematic form.
Then, rank$(H([lb:(l+1)b-1],[j:j+b-1]))=b,~{}l\in[0:(z-1)],~{}j\in[0:k-b]$.

The lemma below establishes the equivalence of a class of causal and
systematic codes that are delay-$\tau$ decodable for any $(z,b)$-burst.

######  Lemma 3.

An $[n=k+zb,k]$ causal block code that is delay-$\tau$ decodable for any
$(z,b)$-burst exists iff an $[n=k+zb,k]$ systematic code that is delay-$\tau$
decodable for any $(z,b)$-burst exists.

Lemma 4 below will be useful for establishing a divisibility constraint in
Theorem 3.

######  Lemma 4.

Let $b\geq 2$ and $m\geq 2$ be positive integers. Consider a matrix
$A\in\mathbb{F}^{2\times mb}_{q}$ that satisfies the following properties:

  * •

P1: $A(i,[0:b-2])=\underline{0}^{T}_{b-1},$ $i\in\\{0,1\\}.$

  * •

P2: In any row of $A$, no more than $(b-1)$ consecutive entries can be $0$.

  * •

P3: For $j\in[b-1:(m-1)b],$ rank$(A(:,[j:j+b-1]))=1$.

  * •

P4: For $j\in[0:(m-2)b],$ rank$(A(:,[j:j+2b-1]))=2$.

Then, $A(i,mb-1)\neq 0,\ i\in\\{0,1\\}$.

Proof. From P1 and P2, it follows that $A(i,b-1)\neq 0,~{}i\in\\{0,1\\}$. Let
$A(1,b-1)=\beta\cdot A(0,b-1),$
where$~{}\beta\in\mathbb{F}_{q}\setminus\\{0\\}$. Suppose that
$A(i_{1},j_{1})\neq 0$ for some $i_{1}\in\\{0,1\\}$ and $j_{1}\in[b:2b-2]$.
Then, considering $A(:,[b-1:2b-2]),$ from P3 we have $A(1,j_{1})=\beta\cdot
A(0,j_{1})$. Again, from P3 we have $A(1,[b:2b-1])^{T}=\beta\cdot
A(0,[b:2b-1])^{T}$. Combining $A(1,[b-1:2b-2])^{T}=\beta\cdot
A(0,[b-1:2b-2])^{T}$ and $A(1,[b:2b-1])^{T}=\beta\cdot A(0,[b:2b-1])^{T},$ we
get $A(1,[0:2b-1])=\beta\cdot A(0,[0:2b-1])^{T}$, which violates P4. Thus, we
have $A(i,[b:2b-2])=\underline{0}^{T}_{b-1},~{}i\in\\{0,1\\}$. From P2 we get
$A(i,2b-1)\neq 0,~{}i\in\\{0,1\\}$. Proceeding similarly, the lemma follows.
$\Box$

##  III Optimal Rate of $(a,w,\tau)$-$\text{SC}_{\text{\tiny ERR}}$s

In this section, we will drive the optimal rate of an
$(a,w,\tau)$-$\text{SC}_{\text{\tiny ERR}}$ by establishing the equivalence of
an $(a,w,\tau)$-$\text{SC}_{\text{\tiny ERR}}$ and a $(2a,w,\tau)$-SC. In the
following, at times we will consider error packets in an error pattern as
symbols over $\mathbb{F}_{q^{n}}\cong\mathbb{F}_{q}^{n},$ and define the
vector
$\underline{V}_{E}(t)=[\underline{e}(t),\underline{e}(t+1),\dots,\underline{e}(t+\tau)]^{T}\in\mathbb{F}^{\tau+1}_{q^{n}}$
for an admissible error pattern $E=(\underline{e}(0),\underline{e}(1),\dots)$
of the $(a,w)$-$\text{SW}_{\text{\tiny ERR}}$ channel, where $\tau$ is the
decoding-delay constraint. We remark here that even while considering an error
packet $\underline{e}(t)$ as a symbol over $\mathbb{F}_{q^{n}},$ we will
retain the underline under the letter $e$. However, it will be clear from
context whether we are considering error packets as elements of
$\mathbb{F}_{q^{n}}$ or $\mathbb{F}_{q}^{n}.$

The lemma below (proved in the appendix) relates admissible error patterns of
the $(a,w)$-$\text{SW}_{\text{\tiny ERR}}$ channel to admissible erasure
patterns of the $(2a,w)$-SW channel.

######  Lemma 5.

Let $E=(\underline{e}(0),\underline{e}(1),\dots)$ and
$\tilde{E}=(\underline{\tilde{e}}(0),\underline{\tilde{e}}(1),\dots)$ be two
admissible error patterns of the $(a,w)$-$\text{SW}_{\text{\tiny ERR}}$
channel. Let $\underline{e}^{\prime}=(e^{\prime}_{0},e^{\prime}_{1},\dots)$ be
the erasure pattern defined as $\underline{e}^{\prime}_{t}=1$ iff
$(\underline{e}(t)-\underline{\tilde{e}}(t))\neq 0$. Then
$\underline{e}^{\prime}$ is an admissible erasure pattern of the $(2a,w)$-SW
channel. Conversely, every admissible erasure pattern of the $(2a,w)$-SW
channel can be expressed in this way.

The theorem below establishes the equivalence of an
$(a,w,\tau)$-$\text{SC}_{\text{\tiny ERR}}$ and a $(2a,w,\tau)$-SC.

######  Theorem 1.

An $(a,w,\tau)$-$\text{SC}_{\text{\tiny ERR}}$ is a $(2a,w,\tau)$-SC and the
converse is also true.

###### Proof.

Let $\mathcal{C}_{\text{Str}}$ be an $(a,w,\tau)$-$\text{SC}_{\text{\tiny
ERR}}$. Let $\\{\underline{u}(t)\\}_{t\geq 0}$ be the sequence of message
packets transmitted by the source and $\\{\underline{x}(t)\\}_{t\geq 0}$ be
the corresponding sequence of coded packets. In the following, we will
consider coded packets $\underline{x}(t)$ as scalar symbols over
$\mathbb{F}_{q^{n}}$, and define the vector
$\underline{X}{(t)}\triangleq[\underline{x}(t),\underline{x}(t+1),\dots,\underline{x}(t+\tau)]^{T}\in\mathbb{F}^{\tau+1}_{q^{n}}$.
Let $\mathcal{E}(a,w)=\\{E~{}\mid\ E~{}\text{is admissible in the
$(a,w)$-$\text{SW}_{\text{\tiny ERR}}$ channel}\\}$ denote the set of
admissible error patterns of the $(a,w)$-$\text{SW}_{\text{\tiny ERR}}$
channel.

We will now show that $\underline{u}(0)$ can be recovered from any admissible
erasure pattern of the $(2a,w)$-SW channel by time slot $\tau$. Then, one can
use induction to prove that $\underline{u}(t)$ for any $t>0$ can be recovered
from any erasure pattern admissible in the $(2a,w)$-SW channel by time slot
$\tau,$ since while recovering $\underline{u}(t),$ one can assume that
$\\{\underline{u}(0),\underline{u}(1),\dots,\underline{u}(t-1)\\}$ have been
correctly recovered. We remark here that while we keep the proof general, it
is sufficient to consider only those error and erasure patterns whose support
is a subset of $[0:\tau],$ because while recovering the message packet
$\underline{u}(0)$ the decoder can only access coded packets received until
time slot $\tau.$

A necessary and sufficient condition for recovery of $\underline{u}(0)$ by
time slot $\tau$ is that for any sequence
$\\{\underline{\tilde{x}}(t)\\}_{t\geq 0}$ of coded packets corresponding to
some sequence $\\{\underline{\tilde{u}}(t)\\}_{t\geq 0}$ of message packets
such that $\underline{\tilde{u}}(0)\neq\underline{u}(0),$

$\displaystyle\mathcal{B}(\underline{X}(0))\bigcap\mathcal{B}(\underline{\tilde{X}}(0))=\phi,$

where
$\underline{\tilde{X}}{(t)}\triangleq[\underline{\tilde{x}}(t),\underline{\tilde{x}}(t+1),\dots,\underline{\tilde{x}}(t+\tau)]^{T}\in\mathbb{F}^{\tau+1}_{q^{n}},~{}\mathcal{B}(\underline{X}{(0)})=\\{\underline{X}{(0)}+\underline{V}_{E}(0)~{}|~{}E\in\mathcal{E}(a,w)\\}$
and
$\mathcal{B}(\underline{\tilde{X}}{(0)})=\\{\underline{\tilde{X}}(0)+\underline{V}_{\tilde{E}}(0)~{}|~{}\tilde{E}\in\mathcal{E}(a,w)\\}.$
Equivalently, we must have

$\displaystyle\underline{X}(0)-\underline{\tilde{X}}(0)\notin\\{\underline{V}_{\tilde{E}}(0)-\underline{V}_{E}(0)~{}\mid\
E,\tilde{E}\in\mathcal{E}(a,w)\\}.$ (1)

Now suppose that there exists an admissible erasure pattern
$\underline{e}=(e_{0},e_{1},\dots)$ of the $(2a,w)$-SW channel such that
$\mathcal{C}_{\text{Str}}$ can not recover $\underline{u}(0)$ by time slot
$\tau$. Then, it must be the case that there exists a sequence of message
packets $\\{\underline{\tilde{u}}(t)\\}_{t\geq 0}$ such that
$\underline{\tilde{u}}(0)\neq\underline{u}(0),$ and
$\\{\underline{\tilde{u}}(t)\\}_{t\geq 0}$ yields the same set of unerased
coded packets in the window $[0:\tau]$ when the erasure pattern
$\underline{e}$ occurs, i.e.,
$\underline{\tilde{x}}(t)=\underline{x}(t),~{}t\in[0:\tau]\setminus\text{supp}([e_{0},e_{1},\dots,e_{\tau}])$,
where $\\{\underline{\tilde{x}}(t)\\}_{t\geq 0}$ is the sequence of coded
packets corresponding to $\\{\underline{\tilde{u}}(t)\\}_{t\geq 0}$. Hence,
$\text{supp}(\underline{X}(0)-\underline{\tilde{X}}(0))\in\text{supp}([e_{0},e_{1},\dots,e_{\tau}])$.
Using Lemma 5, one can show that there exist error patterns
$E,\tilde{E}\in\mathcal{E}(a,w)$ such that
$\underline{X}(0)-\underline{\tilde{X}}(0)=\underline{V}_{\tilde{E}}(0)-\underline{V}_{E}(0)$.

Similarly, one can use (1) and Lemma 5 to show that a $(2a,w,\tau)$-SC is an
$(a,w,\tau)$-$\text{SC}_{\text{\tiny ERR}}$. ∎

The theorem below characterizes the optimal rate of an
$(a,w,\tau)$-$\text{SC}_{\text{\tiny ERR}}$, and follows from [3, 4] and
Theorem 1.

######  Theorem 2.

The optimal rate of an $(a,w,\tau)$-$\text{SC}_{\text{\tiny ERR}}$ is given by

$R_{\textnormal{opt}}=\frac{w-2a}{w}.$

Further, DE of a $[w,w-2a]$ MDS code yields a rate-optimal
$(a,w,\tau=w-1)$-$\text{SC}_{\text{\tiny ERR}}$.

Clearly, an $(a,w,\tau=w-1)$-$\text{SC}_{\text{\tiny ERR}}$ is also an
$(a,w,\tau^{\prime}>w-1)$-$\text{SC}_{\text{\tiny ERR}}$. Thus, the theorem
above provides a rate-optimal code construction for all parameters.

##  IV Streaming Codes for Multiple Erasure and Error Bursts

###  IV-A Streaming Codes for Multiple Erasure Bursts

We will first establish the necessity of a divisibility constraint for the
existence of an $[n=k+zb,k]$ causal block code that is delay-$\tau^{*}$
decodable for any $(z,b)$-burst. Recall that $\tau^{*}=(k+(z-1)b)$ if $k\geq
b$.

######  Theorem 3.

It is possible to construct an $[n=k+zb,k]$ causal block code that is
delay-$\tau^{*}$ decodable for any $(z,b)$-burst, where $k\geq b,$ iff
$b|\tau^{*}$.

###### Proof.

(The proof for an illustrative example case is provided here; the general
proof is contained within the appendix.) If $b|\tau^{*},$ one can construct
such a code via the construction provided in [6]. Therefore, we will focus on
necessity here. We will show necessity for an example case. From Lemma 3, it
suffices to show necessity for systematic codes. Let $\mathcal{C}$ be a
$[9,5]$ systematic code that is delay-$\tau^{*}$ decodable for any
$(2,2)$-burst, where $\tau^{*}=7.$ Let
$\underline{c}^{T}=[c_{0},c_{1},\dots,c_{8}]$ be an arbitrary codeword of
$\mathcal{C}$, and let $H$ be the parity-check matrix of $\mathcal{C}$ in
systematic form. We will first identify the rank of certain sub-matrices of
$H.$ Then, we will invoke Lemma 4 to show that a certain entry of $H$ must be
non-zero, using which we will contradict the fact that $\mathcal{C}$ is
delay-$7$ decodable for any $(2,2)$-burst.

Consider the recovery of code symbol $c_{0}$. We focus on $H^{(0)}$, which is
of size $(3\times 8)$. Note that the last 3 columns of $H^{(0)}$ form the
$(3\times 3)$ identity matrix, i.e., $H^{(0)}(:,[5:7])=I_{3}$. Consider the
erasure pattern whose support is given by $[0:1]\bigcup[6:7]$. We must have
$H^{(0)}(0,0)\neq 0$ and $H^{(0)}(0,1)=0,$ because otherwise one could add a
(possibly $0$) scalar multiple of $H^{(0)}_{1}$ to $H^{(0)}_{0}$ to get a
vector $\underline{v}=[v_{0},v_{1},v_{2}]^{T},$ where $v_{0}=0$, and such a
vector lies in the span of $\\{H^{(0)}_{6},H^{(0)}_{7}\\}$. Similarly,
considering the erasure pattern whose support is given by $[0:1]\bigcup[5:6],$
we get that $H^{(0)}(2,0)\neq 0$ and $H^{(0)}(2,1)=0.$

Now consider recovery of the symbol $c_{1}$. Note that $H^{(1)}=H$. Consider
the erasure pattern whose support is given by $[1:2]\bigcup[7:8]$. Noting that
$H^{(1)}(0,1)=0,$ we get $H^{(1)}(1,1)\neq 0$. Similarly, considering the
erasure pattern whose support is given by $[1:2]\bigcup[6:7]$, we get
$H^{(1)}(3,1)\neq 0$.

Once again consider the recovery of symbol $c_{0}$. Note that in $H^{(0)}$,
$H^{(0)}(0,2)\neq 0,$ since from Lemma 2, $H^{(0)}([0:1],[1:2])$ must be full-
rank. Similarly, $H^{(0)}(2,2)\neq 0$. Now suppose that
$H^{(0)}(\\{0,2\\},[2:3])$ is full-rank. Then,
$H^{(0)}(\\{0,2\\},0)\in\text{span}\langle\\{H^{(0)}(\\{0,2\\},2),H^{(0)}(\\{0,2\\},3)\\}\rangle$.
Since $H^{(0)}(\\{0,2\\},1)=\underline{0}_{2}^{T}$ and $H^{(0)}(1,1)\neq 0,$
it follows that
$H^{(0)}_{0}\in\text{span}\langle\\{H^{(0)}_{1},H^{(0)}_{2},H^{(0)}_{3}\\}\rangle.$
Thus, rank$(H^{(0)}(\\{0,2\\},[2:3]))=1$ must hold
(rank$(H^{(0)}(\\{0,2\\},[2:3]))=0$ violates Lemma 2). Similarly,
rank$(H^{(0)}(\\{0,2\\},[3:4]))=1$ must hold. In the proof for the general
case, this argument has been called Argument $1$. We must also have
rank$(H^{(0)}(\\{0,2\\},[1:4]))=2$ from Lemma 1. It follows that
$H^{(0)}(\\{0,2\\},[1:4])$ satisfies all the properties of Lemma 4. Hence we
get $H^{(0)}(2,4)\neq 0$. However, since $H^{(0)}(\\{0,2\\},5)=[1,0]^{T}$, the
rank of $H^{(0)}(\\{0,2\\},\\{4,5\\})$ is $2$, and the code symbol $c_{0}$ can
not be recovered from the $(2,2)$-burst whose support is given by
$[0:1]\bigcup[4:5],$ within delay $7$. ∎

In the following theorem (for proof see appendix), we derive a rate-upper-
bound for a $(z,b,w,\tau)$-SC and show that it can be achieved via DE iff a
divisibility constraint is met.

######  Theorem 4.

The rate $R$ of a $(z,b,w,\tau)$-SC is upper-bounded as

$R\leq\frac{w-1-(z-1)b}{w-1+b}.$ (2)

Furthermore, a $(z,b,w,\tau=w-1)$-SC that achieves the bound (2) can be
constructed via DE iff $b|(w-1)$.

Proof. Consider the periodic erasure pattern shown in Fig. 4. It can be
verified that this erasure pattern is admissible in the $(z,b,w)$-MBSW
channel. A period of this erasure pattern has length $(w-1+b)$, and in each
period there are $(w-1-(z-1)b)$ non-erased packets. Following similar
arguments as in [3], it follows that the rate $R$ of a $(z,b,w,\tau)$-SC is
upper-bounded as (2).

Figure 4: An admissible periodic erasure pattern of the $(z,b,w)$-MBSW
channel.

One can construct a systematic $[w-1+b,w-1-(z-1)b]$ code that is delay-$(w-1)$
decodable for any $(z,b)$-burst using the construction in [6] (since
$\tau^{*}=w-1$ for this case) if $b|(w-1).$ DE of this code yields a
$(z,b,w,\tau=w-1)$-SC whose rate matches (2).

Now suppose that $\mathcal{C}$ is an $[n,k]$ systematic code such that DE of
$\mathcal{C}$ results in a $(z,b,w,\tau=w-1)$-SC $\mathcal{C}_{\text{Str}}$
whose rate matches (2). Since $\mathcal{C}$ recovers from $zb$ erasures, it
follows that $n-k\geq zb$. Since the rate of $\mathcal{C}_{\text{Str}}$
matches (2), we must have $k\geq(w-1-(z-1)b).$ Suppose that a diagonally
embedded codeword
$\underline{c}^{T}=[c_{0},c_{1},\dots,c_{n-1}]\in\mathcal{C}$ is affected by
the $(z,b)$-burst whose support is given by $I=[0:b-1]\bigcup[w-(z-1)b:w-1]$.
Clearly, if $k>(w-1-(z-1)b),$ there are no parity symbols in $[0:w-1]\setminus
I,$ and the code symbol $c_{0}$ can not be recovered within delay $(w-1)$.
Thus, $\mathcal{C}$ is a $[w-1+b,w-1-(z-1)b]$ systematic code that is
delay-$(w-1)$ decodable for any $(z,b)$-burst. From Theorem 3, it follows that
$b|(w-1).$ $\Box$

As mentioned before, $(1,b,w,\tau=w-1)$-SCs whose rate matches the bound (2)
can be constructed by DE for all parameters [1, 2]. Theorem 4 then in
particular shows that a $(1,zb,w,\tau=w-1)$-SC is not necessarily a
$(z,b,w,\tau=w-1)$-SC.

###  IV-B Streaming Codes for Multiple Error Bursts

It can be shown that admissible error patterns of the
$(z,b,w)$-$\text{MBSW}_{\text{\tiny ERR}}$ channel whose support is a subset
of $[0:w-1]$ are related to admissible erasure patterns of the $(2z,b,w)$-MBSW
channel whose support is a subset of $[0:w-1]$ in a way that is similar to the
one described in Lemma 5. It follows that one can construct a
$(z,b,w,\tau=w-1)$-$\text{SC}_{\text{\tiny ERR}}$ of non-zero rate only if
$w>2zb,$ which we will assume in the following. The theorem below establishes
the equivalence of a $(z,b,w,\tau=w-1)$-$\text{SC}_{\text{\tiny ERR}}$ and a
$(2z,b,w,\tau=w-1)$-SC, and can be proved analogous to Theorem 1.

######  Theorem 5.

A $(z,b,w,\tau=w-1)$-$\text{SC}_{\text{\tiny ERR}}$ is a
$(2z,b,w,\tau=w-1)$-SC and the converse is also true.

We can now combine Theorem 4 and Theorem 5 to get the following theorem
analogous to Theorem 2.

######  Theorem 6.

The rate $R^{\prime}$ of a $(z,b,w,\tau=w-1)$-$\text{SC}_{\text{\tiny ERR}}$
is upper-bounded as

$R^{\prime}\leq\frac{w-1-(2z-1)b}{w-1+b}.$ (3)

Furthermore, a $(z,b,w,\tau=w-1)$-$\text{SC}_{\text{\tiny ERR}}$ that achieves
the bound (3) can be constructed via DE iff $b|(w-1)$.

## References

  * [1] E. Martinian and C. W. Sundberg, “Burst erasure correction codes with low decoding delay,” _IEEE Trans. Inf. Theory_ , vol. 50, no. 10, pp. 2494–2502, 2004.
  * [2] E. Martinian and M. Trott, “Delay-Optimal Burst Erasure Code Construction,” in _Proc. IEEE Int. Symp. Inf. Theory, Nice, France, June 24-29, 2007_ , pp. 1006–1010.
  * [3] A. Badr, P. Patil, A. Khisti, W. Tan, and J. G. Apostolopoulos, “Layered Constructions for Low-Delay Streaming Codes,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 1, pp. 111–141, 2017.
  * [4] M. N. Krishnan, D. Shukla, and P. V. Kumar, “Rate-optimal streaming codes for channels with burst and random erasures,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 8, pp. 4869–4891, 2020.
  * [5] E. Domanovitz, S. L. Fong, and A. Khisti, “An explicit rate-optimal streaming code for channels with burst and arbitrary erasures,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 1, pp. 47–65, 2022.
  * [6] Z. Li, A. Khisti, and B. Girod, “Correcting erasure bursts with minimum decoding delay,” in _2011 Conference Record of the Forty Fifth Asilomar Conference on Signals, Systems and Computers (ASILOMAR)_ , 2011, pp. 33–39.
  * [7] V. Ramkumar, S. Bhatnagar, and P. V. Kumar, “Near-optimal streaming codes with linear field size,” in _2023 IEEE International Symposium on Information Theory (ISIT)_ , 2023, pp. 1118–1123.
  * [8] M. Rudow and K. V. Rashmi, “Learning-augmented streaming codes for variable-size messages under partial burst losses,” in _2023 IEEE International Symposium on Information Theory (ISIT)_ , June 2023, pp. 1101–1106.
  * [9] A. Badr, A. Khisti, W.-t. Tan, and J. Apostolopoulos, “Streaming codes with partial recovery over channels with burst and isolated erasures,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 9, no. 3, pp. 501–516, 2015.
  * [10] S. Bhatnagar, B. Chakraborti, and P. V. Kumar, “Streaming codes for handling a combination of burst and random erasures,” in _2021 IEEE Information Theory Workshop (ITW)_ , 2021, pp. 1–6.
  * [11] J. Cloud and M. Médard, “Multi-path low delay network codes,” in _Proc. IEEE Global Communications Conference, GLOBECOM 2016, Washington, DC, USA, December 4-8, 2016_. IEEE, 2016, pp. 1–7.
  * [12] S. L. Fong, A. Khisti, B. Li, W. Tan, X. Zhu, and J. G. Apostolopoulos, “Optimal streaming erasure codes over the three-node relay network,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 5, pp. 2696–2712, 2020.
  * [13] M. Rudow and K. V. Rashmi, “Online versus offline rate in streaming codes for variable-size messages,” in _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 509–514.
  * [14] N. Adler and Y. Cassuto, “Burst-Erasure Correcting Codes With Optimal Average Delay,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 5, pp. 2848–2865, 2017\.
  * [15] M. Haghifam, M. N. Krishnan, A. Khisti, X. Zhu, W. Tan, and J. G. Apostolopoulos, “On streaming codes with unequal error protection,” _IEEE J. Sel. Areas Inf. Theory_ , vol. 2, no. 4, pp. 1165–1179, 2021.
  * [16] P. Su, Y. Huang, S. Lin, I. Wang, and C. Wang, “Random linear streaming codes in the finite memory length and decoding deadline regime,” in _Proc. IEEE International Symposium on Information Theory, ISIT 2021, Melbourne, Australia, July 12-20, 2021_. IEEE, 2021, pp. 730–735.
  * [17] M. N. Krishnan, G. K. Facenda, E. Domanovitz, A. Khisti, W. Tan, and J. G. Apostolopoulos, “High rate streaming codes over the three-node relay network,” in _Proc. IEEE Information Theory Workshop, ITW 2021, Kanazawa, Japan, October 17-21, 2021_. IEEE, 2021, pp. 1–6.
  * [18] V. Ramkumar, M. Vajha, and P. V. Kumar, “Locally recoverable streaming codes for packet-erasure recovery,” in _Proc. IEEE Information Theory Workshop, ITW 2021, Kanazawa, Japan, October 17-21, 2021_. IEEE, 2021, pp. 1–6.
  * [19] M. Rudow and K. Rashmi, “Learning-augmented streaming codes are approximately optimal for variable-size messages,” in _2022 IEEE International Symposium on Information Theory (ISIT)_ , 2022, pp. 474–479.
  * [20] A. Frank, “Delay-optimal coding for secure transmission over parallel burst erasure channels with an eavesdropper,” in _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 960–965.
  * [21] A. Frank, H. Aydinian, and H. Boche, “Delay optimal coding for secure transmission over a burst erasure wiretap channel,” in _2019 IEEE Wireless Communications and Networking Conference (WCNC)_ , 2019, pp. 1–7.
  * [22] A. Badr, D. Lui, and A. Khisti, “Streaming codes for multicast over burst erasure channels,” _IEEE Transactions on Information Theory_ , vol. 61, no. 8, pp. 4181–4208, 2015.
  * [23] R. Mahmood, A. Badr, and A. Khisti, “Streaming codes for multiplicative-matrix channels with burst rank loss,” _IEEE Transactions on Information Theory_ , vol. 64, no. 7, pp. 5296–5311, 2018.
  * [24] M. Vajha, V. Ramkumar, M. N. Krishnan, and P. V. Kumar, “Explicit rate-optimal streaming codes with smaller field size,” in _Proc. IEEE International Symposium on Information Theory, ISIT 2021, Melbourne, Australia, July 12-20, 2021_. IEEE, 2021, pp. 736–741.
  * [25] M. Nikhil Krishnan, V. Ramkumar, M. Vajha, and P. Vijay Kumar, “Simple streaming codes for reliable, low-latency communication,” _IEEE Communications Letters_ , vol. 24, no. 2, pp. 249–253, 2020.

###  -C Proof of Lemma 2

Proof. Since $H$ is the parity-check matrix of $\mathcal{C}$ in systematic
form, $H(:,[k:n-1])=I_{zb}.$ Consider the erasure pattern $\underline{e}$
whose support is given by $\mathcal{E}=[k:n-1]\setminus[lb:(l+1)b-1],$ for
some $l\in[0:z-1]$. It is easy to check that $\underline{e}$ is a
$(z-1,b)$-burst. Also, any vector
$\underline{v}=[v_{0},v_{1},\dots,v_{n-1}]^{T}$ such that
$v_{\lambda}=0,~{}\lambda\in[lb:(l+1)b-1]$ lies in the span of $\\{H_{i}\mid
i\in\mathcal{E}\\}$. Now, if for some $j\in[0:k-b],$
rank$(H([lb:(l+1)b-1],[j:j+b-1]))<b$, one can linearly combine $\\{H_{i}\ |\
i\in[j:j+b-1]\\}$ to get a vector $\underline{v}$ of the form described above.
Then, $\\{H_{i}\ |~{}i\in\mathcal{E}\bigcup\\{j:j+b-1\\}\\}$ becomes a
linearly dependent set, and the code can not recover from the $(z,b)$-burst
$\underline{e}^{\prime}$ whose support is given by
$\mathcal{E}\bigcup\\{j:j+b-1\\}$. $\Box$

###  -D Proof of Lemma 3

Proof. An $[n=k+zb,k]$ systematic block code that is delay-$\tau$ decodable
for any $(z,b)$-burst is also a causal code, hence sufficiency follows. Now
suppose that $\mathcal{C}$ is an $[n=k+zb,k]$ causal block code that is
delay-$\tau$ decodable for any $(z,b)$-burst. Let $G=[U_{k\times k}\ |\ P]$ be
the generator matrix of $\mathcal{C}$. Since $\mathcal{C}$ can recover from
the $(z,b)$-burst whose support is given by $[n-zb:n-1],~{}U_{k\times k}$ must
be full-rank. Let $\underline{c}^{T}=[c_{0},c_{1},\dots,c_{n-1}]$ be the
codeword corresponding to the message vector
$\underline{u}=[u_{0},u_{1},\dots,u_{k-1}]^{T}$. Since $\mathcal{C}$ recovers
message symbol $u_{i},~{}i\in[0:k-1]$ from any $(z,b)$-burst within delay
$\tau$, and $c_{j},~{}j\in[0:k-1]$ is a function of
$\\{u_{0},u_{1},\dots,u_{j}\\}$ only (because $U_{k\times k}$ is upper-
triangular), it follows that $c_{j},~{}j\in[0:k-1]$ is recoverable within
delay $\tau.$ Now consider the systematic code $\hat{\mathcal{C}}$ whose
generator matrix $\hat{G}=[I_{k}\ |\ \hat{P}]$ is obtained by performing row
operations on $G$. Since the code $\hat{\mathcal{C}}$ also has the property
that for any
$\hat{\underline{c}}^{T}=[\hat{c}_{0},\hat{c}_{1},\dots,\hat{c}_{n-1}]\in\hat{\mathcal{C}}$,
$\hat{c}_{j},~{}j\in[0:k-1]$ is recoverable within delay $\tau$, the claim
follows. $\Box$

###  -E Proof of Lemma 5

###### Proof.

Considering the error packets in the admissible error pattern $E$ as symbols
over $\mathbb{F}_{q^{n}}\cong\mathbb{F}_{q}^{n},$ we define the vector
$\underline{U}_{E}(t)=[\underline{e}(t),\underline{e}(t+1),\dots,\underline{e}(t+w-1)]^{T}\in\mathbb{F}^{w}_{q^{n}}$.
Similarly, we define the vector
$\underline{U}_{\tilde{E}}(t)=[\underline{\tilde{e}}(t),\underline{\tilde{e}}(t+1),\dots,\underline{\tilde{e}}(t+w-1)]^{T}\in\mathbb{F}^{w}_{q^{n}}$
for the error pattern $\tilde{E}.$ Now, since $E$ and $\tilde{E}$ are
admissible error patterns of the $(a,w)$-$\text{SW}_{\text{\tiny ERR}}$
channel, we have $w_{H}(\underline{U}_{E}(t))\leq a$ and
$w_{H}(\underline{U}_{\tilde{E}}(t))\leq a,~{}\forall t\geq 0.$ Thus,
$w_{H}([\underline{e}^{\prime}_{t},\underline{e}^{\prime}_{t+1},\dots,\underline{e}^{\prime}_{t+w-1}])=w_{H}(\underline{U}_{E}(t)-\underline{U}_{\tilde{E}}(t))\leq
2a,~{}\forall t\geq 0,$ which implies that $\underline{e}^{\prime}$ is
admissible in the $(2a,w)$-SW channel.

We now prove the converse. Let $\underline{e}^{\prime}$ be an admissible
erasure pattern of the $(2a,w)$-SW channel, and let
$\mathcal{I}=\\{i_{0},i_{1},\dots\\}$ be the (possibly finite) support of
$\underline{e}^{\prime}$. Now define two sets $I_{1}=\\{i_{j}\ |\ j\ \text{is
even}\\}$ and $I_{2}=\\{i_{j}\ |\ j\ \text{is odd}\\}.$ Note that
$I_{1}\bigcap I_{2}=\phi$ and $I_{1}\bigcup I_{2}=\mathcal{I}.$ Define the
error pattern $E=(\underline{e}(0),\underline{e}(1),\dots)$ as
$\underline{e}(t)=[1,0,\dots,0]\in\mathbb{F}_{q}^{n}$ (or any other non-zero
vector in $\mathbb{F}_{q}^{n}$) if $t\in I_{1},$ and
$\underline{e}(t)=\underline{0}_{n},$ otherwise. Define the error pattern
$\tilde{E}=(\underline{\tilde{e}}(0),\underline{\tilde{e}}(1),\dots)$ as
$\underline{\tilde{e}}(t)=[1,0,\dots,0]\in\mathbb{F}_{q}^{n}$ (or any other
non-zero vector in $\mathbb{F}_{q}^{n}$) if $t\in I_{2},$ and
$\underline{\tilde{e}}(t)=\underline{0}_{n},$ otherwise. We will now show that
$E$ is admissible in the $(a,w)$-$\text{SW}_{\text{\tiny ERR}}$ channel, the
proof for $\tilde{E}$ is analogous. Suppose that $E$ is not admissible in the
$(a,w)$-$\text{SW}_{\text{\tiny ERR}}$ channel. Then, there must exist some
$t\geq 0$ such that $w_{H}(\underline{U}_{E}(t))>a.$ In this case, we must
have
$w_{H}([\underline{e}^{\prime}_{t},\underline{e}^{\prime}_{t+1},\dots,\underline{e}^{\prime}_{t+w-1}])>2a,$
which violates the fact that $\underline{e}^{\prime}$ is an admissible erasure
pattern of the $(2a,w)$-SW channel. It is easy to verify that
$\underline{e}^{\prime}$ can be obtained from $E$ and $\tilde{E}$ as described
in the lemma. ∎

###  -F Proof of Theorem 3

Proof. We will now show necessity for the general case. From Lemma 3, it
suffices to show necessity for systematic codes. Let $\mathcal{C}$ be an
$[n=k+zb,k]$ systematic block code that is delay-$\tau^{*}$ decodable for any
$(z,b)$-burst, where $k\geq b,$ and $\tau^{*}=k+(z-1)b.$ It follows
that$~{}b\nmid\tau^{*}\iff b\nmid k$. Let $k=ub+a,~{}a\in[1:b-1]$. Let $H$ be
the parity-check matrix of $\mathcal{C}$ in systematic form, and let
$\underline{c}^{T}=[c_{0},c_{1},\dots,c_{n-1}]$ be any arbitrary codeword of
$\mathcal{C}$. Consider the following two cases:

####  -F0a Case $z=2$

We will first show that $H^{(0)}([0:b-1],[0:b-1])$ is lower triangular with
$H^{(0)}(i,i)\neq 0,~{}i\in[0:b-1]$.

Consider recoverability of code symbol $c_{0}$. Focus on $H^{(0)}$. Note that
$H^{(0)}$ is of size $(b+1)\times(n-b+1)$, and the last $(b+1)$ columns of
$H^{(0)}$ form an identity matrix. Consider the $(2,b)$-burst whose support is
given by $[0:b-1]\bigcup[n-2b:n-b]\setminus\\{n-2b\\}$. We must have
$H^{(0)}(0,0)\neq 0$ and $H^{(0)}(0,[1:b-1])=\underline{0}_{b-1}^{T}$, since
otherwise it will be possible to add a scalar multiple of $H^{(0)}_{l}$ for
some $l\in[1:b-1]$ to $H^{(0)}_{0}$ to get a vector
$\underline{v}=[v_{0},v_{1},\dots,v_{b}]^{T}$ such that $v_{0}=0,$ and such a
vector lies in the span of $\\{H^{(0)}_{j}\ |\
j\in[n-2b:n-b]\setminus\\{n-2b\\}\\}$. Similarly, considering the
$(2,b)$-burst whose support is given by
$[0:b-1]\bigcup[n-2b:n-b]\setminus\\{n-b\\}$, we get $H^{(0)}(b,0)\neq 0$ and
$H^{(0)}(b,[1:b-1])=\underline{0}_{b-1}^{T}$.

Now consider recoverability of the symbol $c_{1}$. Consider the $(2,b)$-burst
whose support is given by $[1:b]\bigcup[n-2b+1:n-b+1]\setminus\\{n-2b+1\\}$.
Following a similar argument as above, and noting that
$H^{(1)}(0,[1:b-1])=\underline{0}_{b-1}^{T}$, we get $H^{(1)}(1,1)\neq 0$,
and, if $b>2$, $H^{(1)}(1,[2:b-1])=\underline{0}_{b-2}^{T}$. Noting that
$H^{(0)}([0:b-1],[0:b-1])=H^{(1)}([0:b-1],[0:b-1]),$ we get
$H^{(0)}([0:1],[0:1])$ is lower-triangular, with $H^{(0)}(i,i)\neq
0,~{}i\in[0:1].$ Proceeding similarly, we consider recoverability of
$c_{2},c_{3},\dots,c_{b-1}$ to get that $H^{(0)}([0:b-1],[0:b-1])$ is lower
triangular, with $H^{(0)}(i,i)\neq 0,~{}i\in[0:b-1]$.

Now, we again focus on recovery of $c_{0}$.

######  Argument 1.

Suppose there exists an index $s\in[b:n-3b+1]$ such that
$H^{(0)}(\\{0,b\\},[s:s+L-1])$ has rank $2$, where $L\leq b$. Then,
$H^{(0)}(\\{0,b\\},0)\in\text{span}\langle\\{H^{(0)}(\\{0,b\\},j)\ |\
j\in[s:s+L-1]\\}\rangle$. Since $H^{(0)}(0,[1:b-1])=\underline{0}^{T}_{b-1},$
$H^{(0)}(b,[1:b-1])=\underline{0}^{T}_{b-1}$ and $H^{(0)}([1:b-1],[1:b-1])$ is
lower triangular with $H^{(0)}(i,i)\neq 0,~{}i\in[1:b-1]$, we get that
$H^{(0)}_{0}\in\text{span}\langle\\{H^{(0)}_{j}\ |\
j\in[1:b-1]\bigcup[s:s+L-1]\\}\rangle$. The erasure pattern whose support is
given by $[0:b-1]\bigcup[s:s+L-1]$ is a $(2,b)$-burst, hence no such $s$
should exist.

We will now show that such an $s$ exists by invoking Lemma 4. Since
$H^{(0)}(0,[1:b-1])=\underline{0}_{b-1}^{T}$, from Lemma 2, it follows that
$H^{(0)}(0,b)\neq 0$. Similarly, $H^{(0)}(b,b)\neq 0$. If $u\geq 2$, from
Argument 1 as well as by noting that $\mathcal{C}$ is an $[n=k+zb,k]$
systematic block code that is delay-$\tau^{*}$ decodable for any
$(2,b)$-burst, it follows that $H^{(0)}(\\{0,b\\},[1:ub])$ satisfies all the
properties stated in Lemma 4, and thus $H^{(0)}(b,ub)\neq 0$. Thus,
$H^{(0)}(b,ub)\neq 0$ for $u\geq 1.$ Observing that
$H^{(0)}(\\{0,b\\},n-2b)=[1,0]^{T}$, we get $H^{(0)}(\\{0,b\\},\\{ub,n-2b\\})$
is full-rank. The burst erasure whose support is given by $[ub:n-2b]$ is of
length $\leq b$.

####  -F0b Case $z>2$

Consider the code $\tilde{\mathcal{C}}$ obtained by puncturing $\mathcal{C}$
on the coordinates $\mathcal{P}=[n-zb:n-2b-1]$, i.e., the code
$\tilde{\mathcal{C}}$ is obtained by deleting all the coordinates in
$\mathcal{P}$ from every codeword of $\mathcal{C}$. Then,
$\tilde{\mathcal{C}}$ is a linear block code of dimension $\tilde{k}=k,$ and
length $\tilde{n}=k+2b$. Let
$\underline{\tilde{c}}^{T}=[\tilde{c}_{0},\tilde{c}_{1},\dots,\tilde{c}_{\tilde{n}-1}]$
be any arbitrary codeword of $\tilde{\mathcal{C}}$. Define a map $f$ from
$[0:\tilde{n}-1]$ to $[0:n-1]$ as follows:

$f(i)=\begin{cases}i,~{}\text{if}~{}i\in[0:\tilde{k}-1],\\\
(z-2)B+i,~{}\text{if}~{}i\in[\tilde{k}:\tilde{n}-1].\end{cases}$ (4)

For a set $I=\\{i_{1},i_{2},\dots,i_{l}\\}\subseteq[0:\tilde{n}-1]$, let
$f(I)$ denote the set $\\{f(i_{1}),f(i_{2}),\dots,f(i_{l})\\}$. Suppose that
for some $i\in[0:\tilde{k}-1]$ there exists a $(2,b)$-burst $\underline{e}$
whose support is given by $J\in[0:\tilde{n}-1],$ such that $\tilde{c}_{i}$ is
not recoverable within delay $(\tilde{n}-b)$ when $\underline{e}$ occurs.
Then, with regard to $\mathcal{C}$ it follows that $c_{f(i)}$ is not
recoverable within delay $(n-b)$ when the $(z,b)$-burst
$\underline{e}^{\prime}$ whose support is given by $f(J)\bigcup\mathcal{P}$
occurs. Since $\mathcal{C}$ is delay-$(n-b)$ decodable for any $(z,b)$-burst,
such an $i$ does not exist. Thus, $\tilde{\mathcal{C}}$ is a causal
$[\tilde{n}=\tilde{k}+2b,\tilde{k}]$ block code that is delay-$(\tilde{n}-b)$
decodable for any $(2,b)$-burst, where $\tilde{k}\geq b,$ which as we have
shown in the previous case can not exist. $\Box$

######  Remark 1.

The proof presented here shows a stronger result than the statement of the
theorem, by showing that the $0$-th code symbol itself can not be decoded
within delay $\tau^{*}$ if $b\nmid\tau^{*}$.


# Characterization and Newton Complementary Dual of Quasi $f$-Ideals ∗

F. U. Rehman 1, H. Hasan 1, H. Mahmood 1, M. A. Binyamin 2

###### Abstract.

The notion of quasi $f$-ideals was first presented in $[14]$ which generalize
the idea of $f$-ideals. In this paper, we give the complete characterization
of quasi $f$-ideals of degree greater or equal to $2$. Additionally, we show
that the property of being quasi $f$-ideals remain the same after taking the
Newton complementary dual of a squarefree monomial ideal $I$ provided that the
minimal generating set of $I$ is perfect.

Key words:  $f$-vector; facet complex; Stanley-Reisner complex; quasi
$f$-ideal;
2010 Mathematics Subject Classification: 13F20, 05E45, 13F55, 13C14.

∗ The third and fourth authors are supported by the Higher Education
Commission of Pakistan for this research (Grant no. 7515).
1Government College University Lahore, Pakistan. 2 Government College
University Faisalabad, Pakistan.
E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
##  1\. Introduction

Throughout this paper, $F$ is a field and $R=F[x_{1},x_{2,}...,x_{n}]$ is a
polynomial ring with $n$ indeterminate. Any squarefree monomial ideal
$I\subset R$ can be associated to two different simplicial complexes over the
finite set of vertices, denoted by $\delta_{\mathcal{F}}(I)$ and
$\delta_{\mathcal{N}}(I)$, called the facet complex of $I$ and the non-face
complex (or Stanley-Reisner complex) of $I$ respectively. The $f$-vectors of
these two simplicial complexes $\delta_{\mathcal{F}}(I)$ and
$\delta_{\mathcal{N}}(I)$ have the accompanying prospects :
1) $f(\delta_{\mathcal{F}}(I))=f(\delta_{\mathcal{N}}(I))$ or
2) $f(\delta_{\mathcal{F}}(I))\neq f(\delta_{\mathcal{N}}(I))$ but
$dim(\delta_{\mathcal{F}}(I))=dim(\delta_{\mathcal{N}}(I))$ or
3) $f(\delta_{\mathcal{F}}(I))\neq f(\delta_{\mathcal{N}}(I))$ but
$dim(\delta_{\mathcal{F}}(I))\neq dim(\delta_{\mathcal{N}}(I))$
A squarefree monomial ideal $I\subset R$ with property that mention in (1) is
called an $f$-ideal of the polynomial ring $R$. This notion has been studied
for various properties of $f$-ideals relevant to combinatorial commutative
algebra in the papers $[3]$, $[4]$, $[11]$, $[12]$, and $[13]$. If we look at
(1) and (2) collectively, there is one thing common, i.e, dimensions of both
$\delta_{\mathcal{F}}(I)$ and $\delta_{\mathcal{N}}(I)$ are same. This means
that the $f$-vectors of $\delta_{\mathcal{F}}(I)$ and
$\delta_{\mathcal{N}}(I)$ can be added or subtracted usually. In this paper we
will think just those squarefree monomial ideal $I$ in the polynomial ring
$R=F[x_{1},x_{2,}...,x_{n}]$ with properties that
$dim(\delta_{\mathcal{F}}(I))=s=dim(\delta_{\mathcal{N}}(I))$ and
$f(\delta_{\mathcal{N}}(I))-f(\delta_{\mathcal{F}}(I))=\left(a_{1},a_{2},\ldots,a_{s}\right)$,
we call it a quasi $f$-ideal of type $(a_{1},a_{2},\ldots,a_{s})$. It is noted
that if $a_{i}=0$ for all $i=1,2,...,r$, then clearly we have the property
(1), and equivalently saying that every $f$-ideal is a quasi $f$-ideal of type
$\mathbf{0}$-vector. It is natural to ask: Is it possible to characterize all
the squarefree monomial quasi $f$-ideals? Mahmood. H. et al, classified all
the pure squarefree monomial quasi $f$-ideals of degree $2$ in two different
approaches in $[14]$. In this paper, we characterize all quasi $f$-ideals of
degree $d\geq 2$. Moreover, we extend this class of quasi $f$-ideal regarding
its Newton complementary dual. In 2013, during the study of Cremona maps;
Costa and Simis $[5]$ introduced the notion of the Newton complementary dual
in general context. After that, Doria and Simis $[6]$ were examined different
properties of Newton complementary dual. Ansaldi, Lin, and Shin $[2]$
investigated the Newton complementary duals of monomial ideals.

In this paper, we use the following outlines. In section 2, we give essential
concepts that help in the expected results. Section 3 focuses on the primary
study of quasi $f$-ideals; Theorem 3.2 characterizes all pure squarefree quasi
$f$-ideals of degree $d\geq 2$, and Theorem 3.2 gives the formulae to compute
the Hilbert function and Hilbert series of the polynomial ring $R$ modulo
squarefree monomial quasi $f$-ideal $I$. The fourth section of this paper is
devoted to the Newton complementary duals of quasi $f$-ideals. We prove that
an ideal $I$ is a quasi $f$-ideal if and only if $\widehat{I}$ is a quasi
$f$-ideal provided that $G(I)$ is perfect, Theorem 4.5.

##  2\. Basic Set Up

Let us review some fundamental ideas to get familiar with simplicial complex
and squarefree monomial ideals. Let $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ be a
vertex set. A subset $\Delta$ of $P(V)$ is said to be a simplicial complex on
$V$ if and only if each one point subset of $V$ lies in $\Delta$ and, if $E$
is any subset of $F\in\Delta$, then $E\in\Delta$. Note that, each element of
$\Delta$ is known as face and the maximal faces under $\subseteq$ are known as
facets. For any face $F$ of $\Delta$, the dimension of $F$ is given by
$dim(F)=|F|-1$. Note that $\emptyset\in\Delta$ and $dim(\emptyset)=-1$. A
simplicial complex $\Delta$ is said to be pure if all of its facets have the
same dimension. The dimension of $\Delta$ is the maximum of the dimension of
all facets of $\Delta$. If $\Delta$ is a $d$-dimensional simplicial complex on
$V$, then the $f$-vector of $\Delta$ is the $d+2$ tuple

$f(\Delta)=(f_{-1}(\Delta),f_{0}(\Delta),f_{1}(\Delta),...,f_{d}(\Delta))$

where $f_{-1}(\Delta)=1$ and
$f_{i}(\Delta)=\left|\left\\{F\in\Delta:\dim(F)=i\right\\}\right|$, $0\leq
i\leq d$,. Note that in $d$-dimensional simplicial complex $\Delta$, we may
assume if needed $f_{i}(\Delta)=0$ for $i>d$. This means that the $f$-vector
of simplicial complex $\Delta$ can be written as
$f(\Delta)=(f_{-1}(\Delta),f_{0}(\Delta),f_{1}(\Delta),...,f_{d}(\Delta),0,0,...,0)$.

Suppose that $I=\langle u_{1},u_{2},...,u_{r}\rangle$ is a squarefree monomial
ideal of a polynomial ring $R=F[x_{1},x_{2},\ldots,x_{n}]$ with
$supp(I)=\\{x_{1},x_{2},\ldots,x_{n}\\}$. We use $G(I)$ to denote the unique
set of minimal generators of $I$. We can associate to $I$ two simplicial
complexes. The facet complex is a simplicial complex denoted by
$\delta_{\mathcal{F}}(I)$ and is defined as $\delta_{\mathcal{F}}(I)=\langle
F_{1},F_{2},...,F_{r}\rangle$ where $F_{i}=\\{v_{j}:x_{j}$ divide $u_{i}\\}$
is the facet on the vertices $v_{1},v_{2},\ldots,v_{n}$, and $i=1,2,3,...,r$.
The non-face complex (or Stanley-Reisner complex) is a simplicial complex on
$V=\\{v_{1},v_{2},\ldots v_{n}\\}$ such that a subset
$\\{v_{i_{1}},v_{i_{2}},...,v_{i_{k}}\\}$ of $V$ is a face of this non-face
complex if and only if the corresponding monomial $x_{i_{1}}x_{i_{2}}\cdots
x_{i_{k}}$ does not belong to $I$. We denote it by $\delta_{\mathcal{N}}(I)$.
In this paper, we are interested in the following family of squarefree
monomial ideals:

######  Definition 2.1.

_A squarefree monomial ideal $I$ in the polynomial ring $R$ with the field $F$
is said to be a quasi $f$-ideal of type
$(a_{1},a_{2},\ldots,a_{r})\in\mathbb{Z}^{r}$ if and only if
$f_{i}(\delta_{\mathcal{N}}(I))-f_{i}(\delta_{\mathcal{F}}(I))=a_{i}$ for all
$i\in\\{1,2,3,...,r\\}.$_

######  Remark 2.2.

_It is noted that, if $a_{i}=0$ for all $i\in\\{1,2,3,...,r\\}$, then
obviously $I$ is an $f$-ideal. This means that every $f$-ideal is a quasi
$f$-ideal whose type is a zero vector, and obviously any quasi $f$-ideal with
type some non-zero vector can not be an $f$-ideal. It is impotent to mention
that the class of quasi $f$-ideals is much more bigger than the class of
$f$-ideals; moreover, unlike $f$-ideals, examples of quasi $f$-ideals can be
found in $R=F[x_{1},x_{2,}...,x_{n}]$, for any $n$._

We would like to recall the [12, Definition 2.1] of perfect sets of $R$. We
use $sm(R)$ and $sm(R)_{d}$ to denote the set of all squarefree monomials and
the set of all squarefree monomials of degree $d$ in $R$ respectively;

######  Definition 2.3.

_Let $R=F[x_{1},x_{2,}...,x_{n}]$, and let $A\subseteq sm(R)$. We define
(i) $\sqcup(A)=\\{gx_{i}\ |\ g\in A,{x_{i}}\text{ does not divide }g,1\leq
i\leq n\\}$ and
(ii) $\sqcap(A)=\\{h\ |\ h=g/x_{i}\text{ for some }g\in A\text{ and some
}x_{i}\text{ with }x_{i}|g\\}$
$A$ is called lower perfect if $\sqcap(A)=sm(R)_{d-1}$ holds. Dually, $A$ is
called upper perfect if $\sqcup(A)=sm(R)_{d+1}$ holds. If $A$ is both lower
perfect and upper perfect, then $A$ is called a perfect set._

##  3\. Characterization of Quasi $f$-Ideals

The purpose of this section is to characterize quasi $f$-ideals of degree
$d\geq 2$ in the polynomial ring $R=F[x_{1},x_{2,}...,x_{n}]$.

The following lemma is key to understanding how to count the number of faces
for particular dimensions of non-face complex of a pure squarefree monomial
ideal for any degree.

######  Lemma 3.1.

_Let $I$ be a pure squarefree monomial ideal of degree $d+1$ in
$R=F[x_{1},x_{2},...,x_{n}]$. Then $f_{i}(\delta_{\mathcal{N}}(I))$ $=$
$n\choose{i+1}$, where $0\leq i<{d}.$_

###### Proof.

If $n_{i}$ is the number of $i$-dimensional non-faces of facet complex of $I$
where $0\leq i<{d}$, then it means that $f_{i}(\delta_{\mathcal{F}}(I))$ $=$
$n\choose{i+1}$ $-$ $n_{i}$ and $\delta_{\mathcal{N}}(I)$ contains at least
$n_{i}$ number of $i$-dimensional faces. The [3, Lemma 3.6] tells us that the
face of dimension less than $d$ of $\delta_{\mathcal{F}}(I)$ is the face of
$\delta_{\mathcal{N}}(I)$. Therefore, we have
${f_{i}(\delta_{\mathcal{N}}(I))}={n\choose{i+1}}-{n_{i}}+{n_{i}}={n\choose{i+1}}$

######  Theorem 3.2.

(Characterization)
_Let $I$ be an equigenerated squarefree monomial ideal of $R$ of degree $d$
and let $G(I)=\\{u_{1},u_{2},\ldots,u_{r}\\}$ be minimal set of generator of
$I$. Then $I$ is quasi $f$-ideal of type
$(a_{0},a_{1},a_{2},...,a_{d-1})\in\mathbb{Z}^{d}$ if and only if the
following conditions hold true:_

  1. (1)

$ht(I)=n-d$;

  2. (2)

${n\choose d}\equiv\begin{cases}0\ (mod\ 2)&\text{if $a_{d-1}$ is even}\\\ 1\
(mod\ 2)&\text{if $a_{d-1}$ is odd}\end{cases},$ and
$r=|G(I)|=\frac{1}{2}({n\choose d}-a_{d-1})$. ;

  3. (3)

$a_{i}$ is the number of $i$-dimensional non-faces of
$\delta_{\mathcal{F}}(I)$, where $i=0,1,2,...,d-2$.

###### Proof.

If $I$ is a quasi $f$-ideal of degree $d$ with type
$(a_{0},a_{1},a_{2},...,a_{d-1})$, then obviously, dimensions of both facet
complex and non-face complex of $I$ are same. By [1, Lemma 3.4] the height of
ideal $I$ must be equal to $n-d$. As $I$ is a squarefree monomial ideal of
degree $d$, using the [1, Lemma 3.2], we have that

(1) $f_{d-1}(\delta_{\mathcal{F}}(I))={n\choose
d}-f_{d-1}(\delta_{\mathcal{N}}(I))$

It is noted that if $I$ is a quasi $f$-ideal of type
$(a_{0},a_{1},a_{2},...,a_{d-1})$, then

(2)
$f_{d-1}(\delta_{\mathcal{N}}(I))=f_{d-1}(\delta_{\mathcal{F}}(I))+a_{d-1}$

From equation (1) and equation (2), we have that
$2f_{d-1}(\delta_{\mathcal{F}}(I))={n\choose d}-a_{d-1}$. It means that the
parity of ${n\choose d}$ is same as the parity of $a_{d-1}$, and
$|G(I)|=f_{d-1}(\delta_{\mathcal{F}}(I))=\frac{1}{2}({n\choose d}-a_{d-1})$.
Now we want to show that $a_{i}$ is the number of $i$-dimensional non-faces of
$\delta_{\mathcal{F}}(I)$, where $i=0,1,2,...,d-2$. Note that for any
squarefree monomial ideal $I$ of degree $d$ the Lemma 3.1, tells us that the
number of $i$-dimensional faces of $\delta_{\mathcal{N}}(I)$ will be equal to
$n\choose{i+1}$ for all $0\leq i<d-1$. As $I$ is a quasi $f$-ideal of degree
$d$ with type $(a_{0},a_{1},a_{2},...,a_{d-1})$. Therefore,
$f_{i}(\delta_{\mathcal{N}}(I))-f_{i}(\delta_{\mathcal{F}}(I))=a_{i}$ which
implies ${n\choose{i+1}}-f_{i}(\delta_{\mathcal{F}}(I))=a_{i}$ for all $0\leq
i<d-1$.

Conversely, suppose that conditions $(1)$, $(2)$ and $(3)$ hold true. For any
squarefree monomial ideal $I$, [15, Proposition 5.3.10] gives
$dim(\delta_{\mathcal{N}}(I))=n-ht(I)-1$ and since height of $I$ is $n-d$, so
we have $dim(\delta_{\mathcal{N}}(I))=dim(\delta_{\mathcal{F}}(I))$. Now, we
will show that
$f(\delta_{\mathcal{N}}(I))-f(\delta_{\mathcal{N}}(I))=(a_{0},a_{1},a_{2},...,a_{d-1}).$
Since $I$ is a squarefree monomial ideal of degree $d$,
$f_{d-1}(\delta_{\mathcal{N}}(I))={n\choose
d}-f_{d-1}(\delta_{\mathcal{F}}(I))$. This implies

(3)
$f_{d-1}(\delta_{\mathcal{N}}(I))-f_{d-1}(\delta_{\mathcal{F}}(I))={n\choose
d}-2f_{d-1}(\delta_{\mathcal{F}}(I))$

As $f_{d-1}(\delta_{\mathcal{F}}(I))=\frac{1}{2}({n\choose d}-a_{d-1})$, this
implies ${n\choose d}-{2f_{d-1}(\delta_{\mathcal{F}}(I))}={a_{d-1}}$.
Therefore, equation (3) becomes
$f_{d-1}(\delta_{\mathcal{N}}(I))-f_{d-1}(\delta_{\mathcal{F}}(I))=a_{d-1}$.
Since $a_{i}$ is the number of $i$-dimensional non-faces of
$\delta_{\mathcal{F}}(I)$ where $i=0,1,2,...,d-2$, this means that
${n\choose{i+1}}-f_{i}(\delta_{\mathcal{F}}(I))=a_{i}$. From Lemma $3.1$, the
number of $i$-dimensional faces of $\delta_{\mathcal{N}}(I))$ are
${n\choose{i+1}}$ therefore, we have
$f_{i}(\delta_{\mathcal{N}}(I))-f_{i}(\delta_{\mathcal{F}}(I))=a_{i}$ for all
$i\in\\{0,1,2,...,d-2\\}$. Thus $I$ is quasi $f$-ideal of type
$(a_{0},a_{1},a_{2},...,a_{d-1})\in\mathbb{Z}^{d}$.

It is worth noting that [3, Theorem 3.9] and [14, Theorem 4.1] can be deduce
by setting $a_{i}=0$ for all $i\in\\{0,1,...,d-1\\}$ in Theorem 3.2 such as
the following corollary:

######  Corollary 3.3.

_Let $I=(u_{1},u_{2},\ldots,u_{r})$ be an equigenerated squarefree monomial
ideal of $R$ of degree $d.$ Then $I$ is quasi $f$-ideal of type
$\mathbf{0}=(0,0,...,0)\in\mathbb{Z}^{d}$ if and only if the following
conditions hold true:_

  1. (1)

$ht(I)=n-d$;

  2. (2)

${n\choose d}\equiv 0\ (mod\ 2),$ and $r=|G(I)|=\frac{1}{2}{n\choose d}$;

  3. (3)

$f_{d-2}(\delta_{\mathcal{F}}(I))={n\choose{d-1}}$

###### Proof.

It is clear from above Theorem. Note that if $a_{d-2}=0$, then
$r=|G(I)|=\frac{1}{2}{n\choose d}$. From Lemma 3.1 and [1, Lemma 3.2],
together implies $f_{d-2}(\delta_{\mathcal{F}}(I))={n\choose{d-1}}.$

######  Corollary 3.4.

_Let $I$ be an equigenerated squarefree monomial ideal of $R$ of degree $2$
and let $G(I)=\\{u_{1},u_{2},\ldots,u_{r}\\}$ be minimal set of generator of
$I$. Then $I$ is quasi $f$-ideal of type $(a_{0},a_{1})\in\mathbb{Z}^{2}$ if
and only if the following conditions hold true:_

  1. (1)

$ht(I)=n-2$;

  2. (2)

${n\choose 2}\equiv\begin{cases}0\ (mod\ 2)&\text{if $a_{1}$ is even}\\\ 1\
(mod\ 2)&\text{if $a_{1}$ is odd}\end{cases},$ and
$r=|G(I)|=\frac{1}{2}({n\choose 2}-a_{1})$. ;

  3. (3)

$a_{0}$ is the number of $i$-dimensional non-faces of
$\delta_{\mathcal{F}}(I)$.

######  Example 3.5.

_Let
$I=(x_{1}x_{2}x_{4},x_{1}x_{2}x_{5},x_{3}x_{4}x_{5},x_{1}x_{4}x_{5},x_{2}x_{3}x_{5})$
be a pure squarefree monomial ideal of degree $3$ in the polynomial ring
$F[x_{1},x_{2},x_{3},x_{4},x_{5}].$ Then the primary decomposition of $I$ is
$(x_{1},x_{3})\bigcap(x_{1},x_{5})\bigcap(x_{2},x_{4})\bigcap(x_{2},x_{5})\bigcap(x_{4},x_{5}).$
The facet complex and the non-face complex of $I$ are_

$\delta_{\mathcal{F}}(I)=\langle\\{1,2,4\\},\\{1,2,5\\},\\{3,4,5\\},\\{1,4,5\\},\\{2,3,5\\}\rangle$

_and_

$\delta_{\mathcal{N}}(I)=\langle\\{1,2,3\\},\\{1,3,4\\},\\{1,3,5\\},\\{2,3,4\\},\\{2,4,5\\}\rangle.$

_As $\\{1,3\\}$ is non-face of $\delta_{\mathcal{F}}(I)$, $ht(I)=2$,
${5\choose 3}\equiv 0\ (mod\ 2)$ and $|G(I)|=5=\frac{1}{2}({5\choose 3}-0).$
Thus $I$ is a quasi $f$-ideal with type $(0,0,1,0).$_

######  Example 3.6.

_Let $I=(x_{1}x_{2}x_{4},x_{1}x_{2}x_{5},x_{3}x_{4}x_{5},x_{1}x_{4}x_{5})$ be
a pure squarefree monomial ideal of degree $3$ in the polynomial ring
$F[x_{1},x_{2},x_{3},x_{4},x_{5}].$ Then the primary decomposition of $I$ is
$(x_{1},x_{3})\bigcap(x_{1},x_{4})\bigcap(x_{1},x_{5})\bigcap(x_{2},x_{4})\bigcap(x_{2},x_{5})\bigcap(x_{4},x_{5}).$
The facet and non-face complexes of $I$ are_

$\delta_{\mathcal{F}}(I)=\langle\\{1,2,4\\},\\{1,2,5\\},\\{3,4,5\\},\\{1,4,5\\}\rangle$

_and_

$\delta_{\mathcal{N}}(I)=\langle\\{1,2,3\\},\\{1,3,4\\},\\{1,3,5\\},\\{2,3,4\\},\\{2,3,5\\},\\{2,4,5\\}\rangle.$

_Then $f(\delta_{\mathcal{F}}(I))=(1,5,8,4)$ and
$f(\delta_{\mathcal{N}}(I))=(1,5,10,6).$ Thus $I$ is a quasi $f$-ideal with
type $(0,0,2,2).$_

In the following theorem, we give the formulae to compute the Hilbert function
and Hilbert series of polynomial ring $R$ modulo a squarefree monomial quasi
$f$-ideal I.

######  Theorem 3.7.

_Let $I$ be a quasi $f$-ideal in a polynomial ring $R$ of type
$(a_{-1},a_{0},a_{1},\\\ ...,a_{d}).$ Then
(1) The Hilbert series of $R/I$ is given by_

$F(R/I,k)=\sum_{i=-1}^{d}{\frac{f_{i}(\delta_{\mathcal{F}}(I))+a_{i}}{{(1-k)}^{i+1}}{k^{i+1}}}$

_(2) The Hilbert function of $R/I$ is given by_

$H(R/I,k)=\sum_{i=0}^{d}{{{k-1}\choose
i}(f_{i}(\delta_{\mathcal{F}}(I))+a_{i})}$

_where $k\geq 1$ and $H(R/I,0)=1$._

###### Proof.

As $I$ is a quasi $f$-ideal in a polynomial $R$ of type
$(a_{-1},a_{0},a_{1},...,a_{d})$. Therefore,
$f_{i}(\delta_{\mathcal{N}}(I))=f_{i}(\delta_{\mathcal{F}}(I))+a_{i}$, this
means that the $f$-vector of $f(\delta_{\mathcal{N}}(I))$ is
$(f_{-1}(\delta_{\mathcal{F}}(I))+a_{-1},f_{0}(\delta_{\mathcal{F}}(I))+a_{0},...,f_{d}(\delta_{\mathcal{F}}(I))+a_{d}).$
Since $I$ is non face ideal of the simplicial complex
$\delta_{\mathcal{N}}(I))$. Now using [15, Theorem 6.7.2] and [15, Theorem
6.7.3], we have that

$F(R/I,k)=\sum_{i=-1}^{d}{\frac{f_{i}(\delta_{\mathcal{F}}(I))+a_{i}}{{(1-k)}^{i+1}}{k^{i+1}}}$

and

$H(R/I,k)=\sum_{i=0}^{d}{{{k-1}\choose
i}(f_{i}(\delta_{\mathcal{F}}(I))+a_{i})}$

as desired.

######  Example 3.8.

_We return to the ideal $I$ in Example 3.6. This ideal $I$ is a quasi
$f$-ideal with type $(0,0,2,2)$ (i.e. $a_{-1}=0,a_{0}=0,a_{1}=2$ and
$a_{2}=2$) and the facet complex of $I$ is_

$\delta_{\mathcal{F}}(I)=\langle\\{1,2,4\\},\\{1,2,5\\},\\{3,4,5\\},\\{1,4,5\\}\rangle$

_clearly, $f(\delta_{\mathcal{F}}(I))=(1,5,8,4)$ (i.e.
$f_{-1}=1,f_{0}=5,f_{1}=8$ and $f_{2}=4$. Thus the Hilbert function and
Hilbert series of $R[x_{1},x_{2},x_{3},x_{4},x_{5}]/I$ are_

$H(R/I,k)={{k-1}\choose 0}(5+0)+{{k-1}\choose 1}(8+2)+{{k-1}\choose 2}(4+2)$

_and_

$F(R/I,k)={\frac{1+0}{{(1-k)}^{-1+1}}{k^{-1+1}}}+{\frac{5+0}{{(1-k)}^{0+1}}{k^{0+1}}}+{\frac{8+2}{{(1-k)}^{1+1}}{k^{1+1}}}+{\frac{4+2}{{(1-k)}^{2+1}}{k^{2+1}}}$

_respectively, where $R=F[x_{1},x_{2},x_{3},x_{4},x_{5}].$_

##  4\. Newton complementary dual of Quasi $f$-Ideal

In [4], Budd and Van Tuyl examined that the property of being $f$-ideals
remain the same after taking the Newton complementary dual of a squarefree
monomial ideal $I$. As quasi $f$-ideal is the generalization of $f$-ideal.
Therefore, it is natural to ask the following question:
When is Newton’s complementary dual of $I$ a quasi $f$-ideal?
In this section, we have tended to this inquiry. Firstly, we recall the [4,
Definition 3.1] of Newton complementary dual of a squarefree monomial ideal.

######  Definition 4.1.

_Let $I$ be a monomial ideal of $R$ with $G(I)=\\{u_{1},u_{2},\ldots,u_{r}\\}$
is a minimal set of generators of $I$. The Newton complementary dual of $I$ is
simply denoted by $\widehat{I}$ and is defined as_

$\widehat{I}=\langle\frac{\prod\limits_{i=1}^{n}{x_{i}}}{u}|u\in G(I)\rangle$

######  Example 4.2.

_The Newton complementary dual of an ideal $I$ in Example 3.5 is
$\widehat{I}=(x_{3}x_{5},x_{3}x_{4},x_{1}x_{2},x_{2}x_{3},x_{1}x_{4}).$_

It is easy to understand that
$\widehat{I}=(x_{3}x_{5},x_{3}x_{4},x_{1}x_{2},x_{2}x_{3},x_{1}x_{4})$ is not
a quasi $f$-ideal. Because the minimal generating set $G(\widehat{I})$ of
$\widehat{I}$ is not upper perfect since $x_{2}x_{4}x_{5}\notin{\sqcup
G(\widehat{I})}$. But keeping in mind that $I$ is a quasi $f$-ideal. It means
that the Newton complementary dual of a quasi $f$-ideal need not be quasi
$f$-ideal. The following remark helps us to overcome the problem of duality of
a squarefree monomial quasi $f$-ideal.

######  Remark 4.3.

_For a squarefree monomial ideal $I$ of degree $d$ in a polynomial ring
$R=F[x_{1},x_{2},...,x_{n}]$, $G(I)$ is lower (upper) perfect set if and only
if $G(\widehat{I})$ is upper (lower) perfect. Indeed, If $G(I)$ is lower
perfect and suppose that there is a squarefree monomial $m\notin{\widehat{I}}$
of degree $n-d+1$. Then we must have a squarefree monomial $u\notin{I}$ of
degree $d-1$ , which is contradiction to the fact that $G(I)$ is lower perfect
set. This means that $G(I)$ is perfect set if and only if $G(\widehat{I})$ is
perfect set. The perfectness of $G(I)$ guaranties that the dimensions of both,
the facet complex of $\widehat{I}$ and the non-face complex of $\widehat{I}$,
coincide._

Now, we recall [4, Corollary 3.6].

######  Corollary 4.4.

_Let $I$ be a squarefree monomial ideal of $R$.
(1) If $f(\delta_{\mathcal{F}}(I))=(f_{-1},f_{0},...,f_{d})$, then_

$f(\delta_{\mathcal{N}}(\widehat{I}))=({n\choose 0}-f_{n-1},...,{n\choose
i}-f_{n-i-1}),...,{n\choose{n-1}}-f_{0},{n\choose n}-f_{-1})$

_(2) If $f(\delta_{\mathcal{N}}(I))=(f_{-1},f_{0},...,f_{d})$, then_

$f(\delta_{\mathcal{F}}(\widehat{I}))=({n\choose 0}-f_{n-1},...,{n\choose
i}-f_{n-i-1}),...,{n\choose{n-1}}-f_{0},{n\choose n}-f_{-1})$

_In both cases, $f_{i}=0$ if $i>d$._

######  Theorem 4.5.

_Let $I$ be a squarefree monomial ideal of degree $d$ in a polynomial ring
$R=F[x_{1},x_{2},...,x_{n}]$ and let the minimal generating set $G(I)$ of $I$
be perfect set. Then $I$ is a quasi $f$-ideal with type
$(a_{-1},a_{0},a_{1},...,a_{d-1})\in\mathbb{Z}^{d+1}$, where $a_{i}=0$ for all
$i\geq d$ if and only if $\widehat{I}$ is a quasi $f$-ideal of type
$(a_{n-1},a_{n-2},a_{n-3},...,a_{-1}).$_

###### Proof.

If $I$ is a quasi $f$-ideal with type
$(a_{-1},a_{0},a_{1},...,a_{d-1})\in\mathbb{Z}^{d+1}$, then
$f_{i}(\delta_{\mathcal{F}}(I))=f_{i}(\delta_{\mathcal{N}}(I))-a_{i}$ for all
$i\in\\{-1.0,1,...,d-1\\}$. This means that the $f$-vector of facet complex of
$I$ will be
$(f_{-1}(\delta_{\mathcal{N}}(I))-a_{-1},(f_{0}(\delta_{\mathcal{N}}(I))-a_{0},...,(f_{d-1}(\delta_{\mathcal{N}}(I))-a_{d-1})$.
Now, using [4, Corollary 3.6], we have

(4)
$f_{j}(\delta_{\mathcal{N}}(\widehat{I}))={n\choose{j+1}}-f_{n-j-2}(\delta_{\mathcal{N}}(I))+a_{n-j-2}$

where $j\in\\{-1.0,1,...,n-1\\}$. It is noted that if
$(f_{-1},f_{0},...,f_{d-1})$ is $f$-vector of $\delta_{\mathcal{N}}(I)$, then
from [4, Corollary 3.6], we get

(5)
$f_{j}(\delta_{\mathcal{F}}(\widehat{I}))={n\choose{j+1}}-f_{n-j-2}(\delta_{\mathcal{N}}(I))$

where $j\in\\{-1.0,1,...,n-1\\}$. From equation (3) and equation (4), we have

(6)
$f_{j}(\delta_{\mathcal{N}}(\widehat{I}))=f_{j}(\delta_{\mathcal{F}}(\widehat{I}))+a_{n-j-2}$

This implies
$f_{j}(\delta_{\mathcal{N}}(\widehat{I}))-f_{j}(\delta_{\mathcal{F}}(\widehat{I}))=a_{n-j-2}$
for all $j\in\\{-1.0,1,...,n-1\\}$. This shows that $\widehat{I}$ is a quasi
$f$-ideal of type $(a_{n-1},a_{n-2},a_{n-3},...,a_{-1}).$ Similarly for
reveres implication, we simply replace $I$ with $\widehat{I}$.

######  Corollary 4.6.

_Let $I$ be a squarefree monomial ideal of a polynomial ring
$R=F[x_{1},x_{2},...,x_{n}]$. Then $I$ is a quasi $f$-ideal of type 0-vector
if and only if $\widehat{I}$ is a quasi $f$-ideal of type 0-vector._

###### Proof.

It is obvious. Since, a quasi $f$-ideal $I$ of type 0-vector is an $f$-ideal.
It implies that the minimal generating set $G(I)$ of $I$ is perfect. Hence, we
have needed to show follows from the above theorem.

######  Example 4.7.

_Let us consider the ideal $I$ in the polynomial ring
$F[x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}]$ given by
$I=(x_{1}x_{2},x_{1}x_{3},x_{2}x_{3},x_{4}x_{5},x_{4}x_{6},x_{5}x_{6},x_{2}x_{4},x_{3}x_{5})$.
It is easy to see that $I$ is a quasi $f$-ideal of type $(0,0,-1)$ $($ or it
can be written as $(0,0,-1,0,0,0,0),$ here $a_{-1}=0$, $a_{0}=0$, $a_{1}=-1$,
$a_{2}=0$, $a_{3}=0$, $a_{4}=0$ and $a_{5}=0)$.
Clearly the Newton complementary dual $\widehat{I}$ of $I$ is generated by the
monomials
$\\{x_{3}x_{4}x_{5}x_{6},x_{2}x_{4}x_{5}x_{6},x_{1}x_{4}x_{5}x_{6},x_{1}x_{2}x_{3}x_{6},x_{1}x_{2}x_{3}x_{5},x_{1}x_{2}x_{3}x_{4},x_{1}x_{3}x_{5}x_{6},x_{1}x_{2}x_{4}x_{6}\\}$.
The primary decomposition of $\widehat{I}$ is
$(x_{2},x_{5})\bigcap(x_{3},x_{4})\bigcap(x_{2},x_{6})\bigcap(x_{3},x_{6})\bigcap(x_{1},x_{4})\bigcap\\\
(x_{1},x_{5})\bigcap(x_{1},x_{6})\bigcap(x_{1},x_{2},x_{3})\bigcap(x_{4},x_{5},x_{6})$.
It is easy to calculate that
$f(\delta_{\mathcal{F}}(\widehat{I}))=(1,6,15,20,8)$ and
$f(\delta_{\mathcal{N}}(\widehat{I}))=(1,6,15,20,7)$. Thus $\widehat{I}$ is a
quasi $f$-ideal with type $(0,0,0,0,-1)$ instead of
$(0,0,0,0,-1,0,0)\leftrightarrow(a_{5},a_{4},a_{3},a_{2},a_{1},a_{0},a_{-1})$_

## References

  * [1] Abbasi, G.Q., Ahmad, S., Anwar, I. and Baig, W.A., 2012. $f$-Ideals of degree 2. Algebra Colloquium, 19 (01) 921-926.
  * [2] K. Ansaldi, K. Lin, Y. Shen, Generalizid Newton complementary duals of monomial ideals. Preprint (2017) . arXive:1702.00519v1
  * [3] Anwar, I., Mahmood, H., Binyamin, M.A. and Zafar, M.K., 2014. On the Characterization of $f$-Ideals. Communications in Algebra, 42(9) 3736-3741.
  * [4] Budd, S., Van Tuyl, A., 2019. Newton Complementary Dual of $f$-ideals. Canad. Math. Bull. 62 (2) 231-241.
  * [5] B. Costa, A. Simis, New constructions of Cremona maps. Math. Res. Lett. 20 (2013), 629 645.
  * [6] A. D oria, A. Simis, The Newton complementary dual revisited. J. Algebra Appl. 17 (2018), 1850004, 16 pp.
  * [7] Faridi, S., 2002. The Facet Ideal of a Simplicial Complex. Manuscripta Mathematica, 109(2) 159-174.
  * [8] Francisco, C. A., Mermin, J., Schweig, J., 2014. A survey of Stanley-Reisner theory. Connections Between Algebra, Combinatorics, and Geometry. Springer Proc. Math. Stat., Springer, New York, 76 209-234.
  * [9] Herzog, J. and Hibi, T., 2018. Binomial Ideals, Springer London.
  * [10] Herzog, J. and Hibi, T., 2011. Monomial ideals, Springer London.
  * [11] Guo, J., Wu, T.,2015. On the $(n,d)^{th}$ $f$-ideals, J. Korean Math. Soc. 52(4), pp.685-697.
  * [12] Guo, J., Wu, T. and Liu, Q., 2017. $f$-Ideals and $f$-Graphs. Communications in Algebra, 45(8) 3207-3220.
  * [13] Mahmood, H., Rehman, F.U., Binyamin, M.A., 2019. A Note on $f$-Graphs. Journal of Algebra and Its Applications Vol. 19, No. 10 (2020) 2050193.
  * [14] Mahmood, H., Rehman, F.U., Binyamin, M.A., 2020. Quasi $f$-ideals of dgree 2. (preprints).
  * [15] R. Villarreal, Monomial Algebra, Marcel Dekker, Inc., New York, 2001.


# Inconsquential results on the Merino-Welsh conjecture for Tutte polynomials

Joseph P.S. Kung

###### Abstract.

The Merino-Welsh conjectures say that subject to conditions, there is an
inequality among the Tutte-polynomial evaluations $T(M;2,0)$, $T(M;0,2)$, and
$T(M;1,1)$. We present three results on a Merino-Welsh conjecture. These
results are “inconsequential” in the sense that although they imply a version
of the conjecture for many matroids, they seem to be dead ends.

##  1\. Merino-Welsh inequalities

There are many variations on the Merino-Welsh conjecture. They are of the form
“subject to conditions, there is an inequality involving the evaluations
$T(M;2,0)$, $T(M;0,2)$, and $T(M;1,1)$ of the Tutte polynomial of the matroid
$M$”. We shall consider the following version.

######  Conjecture 1.1.

If a matroid $M$ has no loops or isthmuses, then

$None$ $T(M;2,0)+T(M;0,2)\geq 2T(M;1,1),$

with equality if and only if $M$ is a direct sum of $U_{1,2}$, the rank-$1$
matroid consisting of two parallel elements.

The focus of this paper is on finding sufficient conditions on a matroid so
that inequality (1.1) holds.

As background, we note that $T(M;2,0)$ is the number of no-broken-circuit or
nbc sets and $T(M;1,1)$ the number of bases in $M$. Hence Conjecture 1.1
asserts that the average number of nbc sets in $M$ and its dual exceeds the
average number of bases in $M$ and its dual. A counting or algebraic-geometry
proof of Conjecture 1.1 is quite possible. From the counting interpretation,
$T(M;2,0)$ and $T(M;0,2)$ are positive integers. We shall tacitly use this
fact, as well as the fact due to Tutte that the coefficients of his polynomial
are non-negative.

##  2\. A density condition

The first result is that a sufficiently dense matroid satisfies Conjecture
1.1.

######  Theorem 2.1.

Let $M$ be an isthmus-free matroid having size $n$ and rank $r$. Then if
$r\geq 4$ and

$n\geq\lceil r(\log r+\log\log r+\log\log\log r)\rceil,$

with the logarithms in base $2$, then $T(M;0,2)\geq 2T(M;1,1)$. In particular,
inequality (1.1) holds for $M$.

The theorem is true for the simple reason that exponential growth beats
polynomial growth in the long run.

######  Proposition 2.2.

If $r\geq 4$ and $n\geq\lceil r(\log r+\log\log r+\log\log\log r)\rceil,$ then
$2^{n-r}\geq 2\binom{n}{r}$.

Consider the function

$f(n,r)=2^{n-r}-2\binom{n}{r}=2^{n-r}-\frac{2n(n-1)\cdots(n-r+1)}{r!},$

where, in spite of the notation, $n$ could be a real number, although $r$ is
always a positive integer. Suppose $n>2r$. Then its forward difference in the
variable $n$ satisfies

$\displaystyle f(n+1,r)-f(n,r)$ $\displaystyle=$
$\displaystyle[2^{n+1-r}-2^{n-r}]-2\left[\binom{n+1}{r}-\binom{n}{r}\right]$
$\displaystyle=$ $\displaystyle 2^{n-r}-2\binom{n}{r-1}$ $\displaystyle>$
$\displaystyle 2^{n-r}-2\binom{n}{r}=f(n,r).$

This yields the following lemma.

######  Lemma 2.3.

If $n>2r$, then $f(n+1,r)>2f(n,r).$ In particular, if $f(n,r)\geq 0,$ then
$f(n+1,r)>0$.

By the lemma, to prove Proposition 2.2, it suffices to find a number $n_{r}$
such that $n_{r}\leq\lceil r(\log r+\log\log r+\log\log\log r)\rceil$ and
$2^{n_{r}-r}\geq 2\binom{n_{r}}{r}$. For small values of $r$, this can be done
by a hand calculation. The results are shown in the following table:

$r$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ | $16$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$n_{r}$ | $4$ | $8$ | $12$ | $16$ | $21$ | $25$ | $29$ | $33$ | $37$ | $42$ | $46$ | $50$ | $54$ | $59$ | $64$ | $68$

This allows us to assume $r\geq 17$. 111There is nothing special about $17$;
it just happens that $16$ entries will fit comfortably in a one-line table.
Any sufficiently large number, like $8$, will work. We begin with the fact
that for $x\geq 17$,

$(\log x)(\log\log x)\geq\log x+\log\log x+\log\log\log x+1.$

This is an easy exercise in calculus. 222To remind myself, with my memory
failing in old age, let $f(x)=(\log x)(\log\log x)$ and $g(x)=\log x+\log\log
x+\log\log\log x+1$. Then $f(17)\geq g(17)>0$ and when we differentiate both
functions, it is evident that  $\frac{\log\log
x}{x}+\frac{1}{x}=f^{\prime}(x)\geq g^{\prime}(x)=\frac{1}{x}+\frac{1}{x\log
x}+\frac{1}{x(\log x)(\log\log x)}>0$ when $x\geq 17$. The added $1$ in $g(x)$
is there so that we can round up. Thus,

$\displaystyle 2^{n-r}\geq\frac{2^{r(\log r+\log\log r+\log\log\log
r)}}{2^{r}}$ $\displaystyle=\frac{[r(\log r)(\log\log
r)]^{r}}{2^{r}}\geq\frac{\lceil r(\log r+\log\log r+\log\log\log
r)\rceil^{r}}{2^{r}}=\frac{n^{r}}{2^{r}}\geq 2\binom{n}{r}.$

In the last step, we use $2^{r+1}\leq r!$ when $r\geq 5$. This completes the
proof of Proposition 2.2.

Returning to the proof of Theorem 2.1, observe that if a matroid $M$ has no
isthmuses, then $T(M;x,y)=y^{n-r}+\cdots,$ where the terms of lower degree in
$y$ have non-negative coefficients. In addition, $T(M;1,1)$ is the number of
bases and is bounded above by $\binom{n}{r}$. Hence, by Proposition 2.2, under
the hypothesis of the theorem,

$T(M;0,2)\geq 2^{n-r}\geq 2\binom{n}{r}\geq 2T(M;1,1).$

We remark that Theorem 2.1 says that for a fixed rank $r$, there are only
finitely many matroids to check to show that Conjecture 1.1 holds at that
rank.

##  3\. Cocircuits

A _cocircuit_ is the complement of a copoint or flat of rank $r-1$. A matroid
is isthmus-free if and only if it has no cocircuits of size $1$; thus, one can
regard the condition that there are no isthmuses as a condition on the minimum
size of a cocircuit. The following theorem says that Conjecture 1.1 holds if
one assumes that all cocircuits are sufficiently large.

######  Theorem 3.1.

Suppose that every cocircuit in a rank-$r$ size-$n$ matroid $M$ has at least
$r+1$ elements. Then $M$ satisfies inequality (1.1).

We begin with an easy binomial identity.

######  Lemma 3.2.

$\displaystyle\sum_{j=0}^{r-1}\binom{r-j-1}{j}y^{r-1-j}$ $\displaystyle=$
$\displaystyle\binom{2r-2}{r-1}+\binom{2r-3}{r-2}y+\cdots+\binom{r}{1}y^{r-2}+y^{r-1}$
$\displaystyle=$ $\displaystyle 2^{2r-2}.$

For example,

$\binom{6}{3}2^{0}+\binom{5}{2}2^{1}+\binom{4}{1}2^{2}+\binom{3}{0}2^{3}=20+10\cdot
2+4\cdot 2^{2}+2^{3}=64=2^{6}.$

Now observe that if every cocircuit in the matroid $M$ has size at least $m$,
then

$T(M;x,y)=y^{n-r}+\binom{r}{1}y^{n-r-1}+\cdots+\binom{r+m-3}{m-2}y^{n-r-m+2}+p(x,y),$

where $p(x,y)$ is a polynomial with non-negative coefficients of degree
$n-r-m+1$ in $y$. In particular, if $m=r+1,$ then

$T(M;0,2)\geq
2^{n-2r+1}\left(\binom{2r-2}{r-1}+\cdots+\binom{r}{1}2^{r-2}+2^{r-1}\right)=2^{n-1}.$

The hypothesis on cocircuits implies that $n\geq 2r$ and under this condition,
$2^{n-1}\geq 2\binom{n}{r}$. We conclude that inequality (1.1) holds.

Theorem 3.1 is not the sharpest possible. It is possible to replace the upper
bound of $r+1$ by a bound of the form $r-c\sqrt{r}$ (with $c$ a constant) for
sufficiently large $r$ using the normal approximation to the binomial
distribution. It is also possible to combine the arguments to obtain
sufficient conditions involving density and size of cocircuits for inequality
(1.1) to hold, but neither refinement would prove the full conjecture. We end
with one further result of this type.

######  Proposition 3.3.

Let $M$ be a rank-$r$ size-$n$ isthmus-free matroid with at least $r-1$ loops.
Then inequality (1.1) holds for $M$.

###### Proof.

Loops are never in a basis. Hence,

$T(M;0,2)\geq 2^{n-r}\geq 2\binom{n-r+1}{r}\geq 2T(M;1,1)$

and inequality (1.1) follows. ∎

## References

  * [1] T. Brylawski, J.G. Oxley, The Tutte polynomial and its applications. In N.L. White,ed., Matroid applications, 123–225, Cambridge University Press, Cambridge, 1992.
  * [2] L.E. Chávez-Lomeli, C. Merino, S.D. Noble, M. Ramírez-Ibáñez, Some inequalities for the Tutte polynomial, European J. Combin. 32 (2011) 422–433.