# Polynomials over Ring of Integers of Global Fields that have Roots Modulo
Every Finite Indexed Subgroup

Bhawesh Mishra

###### Abstract

A polynomial with coefficients in the ring of integers $\mathcal{O}_{K}$ of a
global field $K$ is called intersective if it has a root modulo every finite-
indexed subgroup of $\mathcal{O}_{K}$. We prove two criteria for a polynomial
$f(x)\in\mathcal{O}_{K}[x]$ to be intersective. One of these criteria is in
terms of the Galois group of the splitting field of the polynomial, whereas
the second criterion is verifiable entirely in terms of constants which depend
upon $K$ and the polynomial $f$. The proofs use the theory of global field
extensions and upper bound on the least prime ideal in the Chebotarev density
theorem.

###### keywords:

Intersective Polynomials over Global Fields , Polynomial with Local Roots ,
Intersective Sets

###### MSC:

[2020] 12E10 , 12E05 , 11S05 , 11C08

††journal: Journal of Algebra

[1]organization=Department of Mathematics, The Ohio State
University,addressline=$231$ W $18^{th}$ Ave, city=Columbus, postcode=43210,
state=OH, country=USA

##  1 Introduction

###  1.1 Motivation

Let $q=p^{r}$ be power of a prime $p$ and $T$ be transcendental over
$\mathbb{F}_{q}$. Let $\mathbb{F}_{q}(T)$ denote the field of rational
functions with constant field $\mathbb{F}_{q}$ and $\mathbb{F}_{q}[T]$ denote
the ring of polynomials with coefficients in $\mathbb{F}_{q}$. Recall that an
extension $K$ of a field $M$ is said to be separable if for every $\alpha\in
K$, the minimal polynomial $p_{\alpha}$ has distinct roots in the algebraic
closure. For the ease of discussion, we will say that $K$ is a global field
when $K$ is either of the following:

  * •

An algebraic number field.

  * •

A finite and separable extension of $\mathbb{F}_{q}(T)$, where $p$ is a prime
and $q=p^{r}$ for some $r\geq 1$.

Let $\mathcal{O}_{K}$ be the ring of integers of $K$ when $K$ is a number
field, whereas let $\mathcal{O}_{K}$ be the integral closure of the
$\mathbb{F}_{q}[T]$ in $K$ in the function field case. This article is about
polynomials $f(x)\in\mathcal{O}_{K}[x]$ such that for every subgroup $\Gamma$
of $\mathcal{O}_{K}$ of finite index, there exists $x\in\mathcal{O}_{K}$ with

$f(x)\equiv 0\hskip 2.84526pt(\text{mod }\Gamma).$ (1.1)

Obviously, any $f$ that has a root in $\mathcal{O}_{K}$ satisfies (1.1) for
trivial reasons. The more interesting case is when $f$ satisfies (1.1) but
does not have a root in $K$. Each such $f$ constitutes a counterexample to the
local-global principle.

Another motivation for studying polynomials $f$ that satisfy (1.1) comes from
combinatorial number theory. A set $S\subset\mathcal{O}_{K}$ is said to be
intersective if given any subset $T\subset\mathcal{O}_{K}$ with positive upper
density, one has $(T-T)\cap S\not\subseteq\\{0\\}$. The upper density of
$S\subset\mathcal{O}_{K}$ is given by

$\overline{d}(S)=\limsup_{N\rightarrow\infty}\frac{|S\cap\Phi_{N}|}{|\Phi_{N}|},$

where the sequence of sets $\Phi_{N}$ are defined as :

$\displaystyle\Phi_{N}=\begin{cases}\\{\alpha\in\mathcal{O}_{K}:\text{Norm}(\alpha)\leq
N\\}\text{ ; when $K$ is a number field }\\\
\\{\alpha\in\mathcal{O}_{K}:\text{ deg}(\alpha)\leq N\\}\text{ ; when $K$ is a
finite separable extension of }\mathbb{F}_{q}(T).\end{cases}$

For example, when $K=\mathbb{Q}$, the sequence $\Phi_{N}$ can be taken to be
$[-N,N]\cap{Z}$ for every $N\geq 1$. When $K$ is a finite separable extension
of $\mathbb{F}_{q}(T)$, the sequence $\Phi_{N}$ is the set of divisors of
degree $\leq N$.

A polynomial $f(x)\in\mathcal{O}_{K}[x]$ is said to be intersective if
$\\{f(\alpha):\alpha\in\mathcal{O}_{K}\\}$ is an intersective set. It was
shown in [9] that a polynomial $f(x)\in\mathbb{Z}[x]$ is intersective if and
only if $f$ satisfies (1.1). A far reaching extension of this result was
obtained in [4], a special instance of which implies that for a polynomial
$f(x)\in\mathbb{Z}[x]$ every subset of positive density in $\mathbb{Z}$
contains arbitrarily long polynomial progressions of the form

$a,a+f(n),a+2f(n),\ldots,a+kf(n)$

if and only if $f(x)$ is an intersective polynomial. A polynomial $f(x)$ in
$\mathcal{O}_{K}[x]$ is intersective if and only if it satisfies
$\eqref{defn1}$. This is implied by a very special case of Theorem $1.6$ in
[5] when $K$ is a number field, and Theorem $1.15$ in [1] gives the analogous
result when $K$ is a finite separable extension of $\mathbb{F}_{q}(T)$. The
same results in [1] and [5] also imply that intersectivity of polynomial
$f(x)\in\mathcal{O}_{K}[x]$ is equivalent to the fact that for every
$\alpha\in\mathcal{O}_{K}$, there exists $\beta\in\mathcal{O}_{K}$ such that
$f(\beta)\equiv 0\hskip 2.84526pt(\text{mod }\alpha)$, i.e., $f(\beta)$ is in
the ideal generated by $\alpha$.

Berend and Bilu, in [3], proved a criterion to decide whether a polynomial
$f(x)\in\mathbb{Z}[x]$ is intersective. In this article, we generalize the
results in [3] to polynomials $f(x)\in\mathcal{O}_{K}[x]$ when $K$ is a global
field. The methods in this article are generalizations of those in [3] in the
settings of number fields and function fields respectively. In the process of
proving the main result, we also derive an effective upper bound on the least
prime ideal in the Chebotarev density theorem for function fields (see
Proposition 7).

###  1.2 Global Field Extensions and the Artin Symbols

Let $L$ be a Galois extension of a global field $K$. We will denote the set of
primes in $\mathcal{O}_{K}$ by $\mathbb{P}(K)$. When $K$ is an extension of
$\mathbb{F}_{q}(T)$, its field of constants is $\mathbb{F}_{q^{l}}$ for some
$l\geq 1$. We will denote the set of primes of degree $n$ by
$\mathbb{P}_{n}(K)$. Given a prime $\mathfrak{p}\in\mathbb{P}(K)$,
$K_{\mathfrak{p}}$ will denote the corresponding completion of $K$ and
$|\cdot|_{\mathfrak{p}}$ will denote the corresponding absolute value. If
$\mathfrak{p}\in\mathbb{P}(K)$ is unramified and $\beta\in\mathbb{P}(L)$ lies
over $\mathfrak{p}$ then the Frobenius symbol
$\big{(}\frac{L/K}{\beta}\big{)}$ denotes the unique automorphism
$\varphi_{\beta}\in$ Gal$(L/K)$ such that

$\varphi_{\beta}(\alpha)\equiv\alpha^{N\mathfrak{p}}\hskip 2.84526pt(\text{mod
}\beta)$ (1.2)

for every $\alpha\in\mathcal{O}_{L}$ and
$N\mathfrak{p}=[\mathcal{O}_{K}:\mathfrak{p}]$.

Let $L$ be the splitting field of a polynomial $f(x)\in\mathcal{O}_{K}[x]$,
all of whose irreducible factors are separable, and $G$ be the Galois group of
this extension $L/K$. Note that when the characteristic of $K$ is $p>0$, an
irreducible polynomial $f(x)\in\mathcal{O}_{K}[x]$ is not separable if and
only if $f(x)=g(x^{p^{n}})$ for some polynomial $g$ and some integer $n\geq
1$. Any prime $\mathfrak{p}$ in $\mathcal{O}_{K}$ that does not divide the
discriminant of $f$, is unramified and hence splits as
$\mathfrak{p}=\beta_{1}\cdot\beta_{2}\cdots\beta_{l}$ for some primes
$\beta_{1},\beta_{2},\ldots,\beta_{l}$ in $L$. We use the Artin symbol
$\big{[}\frac{L/K}{\mathfrak{p}}\big{]}$ to denote the set of conjugacy class
of automorphisms

$\bigg{[}\frac{L/K}{\mathfrak{p}}\bigg{]}=\bigg{\\{}\bigg{(}\frac{L/K}{\beta_{1}}\bigg{)},\bigg{(}\frac{L/K}{\beta_{2}}\bigg{)},\ldots,\bigg{(}\frac{L/K}{\beta_{l}}\bigg{)}\bigg{\\}}.$

Let $M$ be a subfield of $L$ and $\mathfrak{p}^{\prime}$ be a prime in $M$
that lies above $\mathfrak{p}$. Then, for any $1\leq i\leq l$ we have

$\bigg{(}\frac{L/M}{\beta_{i}}\bigg{)}=\bigg{(}\frac{L/K}{\beta_{i}}\bigg{)}^{f_{\mathfrak{p}}},$

where $f_{\mathfrak{p}}=[M_{\mathfrak{p}^{\prime}}:K_{\mathfrak{p}}]$. We also
have the natural inclusion of the groups

$\text{Gal }(L_{\beta_{i}}/M_{\mathfrak{p}^{\prime}})\leq\text{Gal
}(L/M)\leq\text{Gal }(L/K),$

which gives that

$\bigg{(}\frac{L/K}{\beta_{i}}\bigg{)}^{m}\in\text{Gal }(L/M)\text{ if and
only if }f_{\mathfrak{p}}\mid m.$ (1.3)

Readers may consult [7, Section 6.2] for more details on Artin Symbols for
global field extensions. When $L$ and $K$ are number fields, $d_{L}$ will
denote the absolute discriminant of $L$ and $d_{L/K}$ will denote the relative
discriminant of the extension $L/K$. Furthermore, $N_{L/K}$ will denote the
corresponding norm. Given fields $M_{1},M_{2}$, we denote by $M_{1}M_{2}$ the
compositum of $M_{1}$ and $M_{2}$. The genus of a separable and finite
extension $M$ of $\mathbb{F}_{q}(T)$ is denoted by $g_{M}$. The resultant of a
polynomial $f(x)\in\mathcal{O}_{K}[x]$ is the resultant of $f$ and its
derivative $f^{\prime}$.

###  1.3 Setup and the Main Result

Let $f(x)\in\mathcal{O}_{K}[x]$ such that no non-unit divides all the
coefficients of $f$. If some non-unit $\beta$ does divide every coefficient of
$f(x)$, we can replace $f(x)$ by $\frac{1}{\beta}f(x)$. Let
$g_{1}(x),g_{2}(x),\ldots,g_{m}(x)$ be the irreducible factors of $f(x)$. When
$K$ is an extension of $\mathbb{F}_{q}(T)$, we further assume that each of the
irreducible factors of $f$ are separable polynomials.

Let $L$ be the splitting field of $f$ over $K$ and $G=$ Gal $(L/K)$ be the
Galois group of this extension. For every $i\in\\{1,2,\ldots,m\\}$, let
$\alpha_{i}$ be a root of $g_{i}$ that is fixed. Let $L_{i}:=K(\alpha_{i})$,
which is an intermediate field between $K$ and $L$, let $H_{i}:=$
Gal$(L/L_{i})\leq G$, and finally let $U:=\bigcup_{i=1}^{m}H_{i}\subseteq G$.
For every $1\leq i\leq m$, let

$g_{i}(x)=\sum_{j=0}^{n_{i}}a_{ij}x^{j}$

for some $a_{i0},\ldots,a_{in_{i}}\in\mathcal{O}_{K}$. Also, let

  * •

$\mathfrak{q}_{i}$ be the discriminant ideal of the irreducible polynomial
$g_{i}$, which is non-zero because each of the $g_{i}$ is separable.

  * •

$\mathfrak{r}_{i}=$ resultant of $g_{i}$ and $g_{i}^{\prime}$,

  * •

$\mathfrak{q}=\mathfrak{r}_{1}\cdots\mathfrak{r}_{m}$,

  * •

$\mathfrak{q}=\mathfrak{p}_{1}^{b_{1}}\cdots\mathfrak{p}_{\nu}^{b_{\nu}}$ be
the unique prime factorization of $\mathfrak{q}$ in $\mathcal{O}_{K}$ and

  * •

Define

$\Delta:=\mathfrak{p}_{1}^{2b_{1}+1}\cdots\mathfrak{p}_{\nu}^{2b_{\nu}+1}.$

  * •

If $K$ is a number field, define

$D:=\prod_{i=1}^{m}\big{(}\mathfrak{q}_{i}\big{)}^{(n_{1}!\cdots
n_{m}!)(1-\frac{1}{n_{i}})}.$

  * •

If $K$ is extension of $\mathbb{F}_{q}(T)$, define

$\Delta^{\prime}:=\sum_{i=1}^{\nu}b_{i}\text{
deg}(\mathfrak{p}_{i})\in\mathbb{Z},$

$D^{\prime}:=\prod_{i=1}^{m}n_{i}!$

and

$\text{ and }d=[K:\mathbb{F}_{q}(T)].$

Our main result gives two equivalent conditions for the polynomial $f(x)$ to
be intersective.

######  Theorem 1.

Let $K$ be a global field and $f(x)\in\mathcal{O}_{K}[x]$ be a polynomial such
that all of its irreducible factors are separable. Then, the following three
statements are equivalent:

  1. 1.

$f(x)$ is an intersective polynomial, i.e. $f$ satisfies (1.1).

  2. 2.

The congruence $f(x)\equiv 0\hskip 2.84526pt(\text{mod }\Delta)$ is solvable
in $\mathcal{O}_{K}$ and

$\bigcup_{\sigma\in G}\sigma^{-1}U\sigma=G.$

  3. 3.

$f(x)\equiv 0\hskip 2.84526pt(\text{mod }\Delta)$ is solvable in
$\mathcal{O}_{K}$ and

$f(x)\equiv 0\hskip 2.84526pt(\text{mod }\mathfrak{p})\hskip 5.69054pt\text{is
solvable for primes }\mathfrak{p}\in\mathcal{O}_{K}$

with

$\begin{cases}\text{deg }(\mathfrak{p})\leq\lceil
2\log_{q}(2\Delta^{\prime}+2dD^{\prime}+8g_{K}D^{\prime}+4)\rceil\hskip
5.69054pt;\text{ if $K$ is extension of $\mathbb{F}_{q}(T)$ }\\\
N_{K/\mathbb{Q}}(\mathfrak{p})\leq\big{(}N_{K/\mathbb{Q}}(D)\big{)}^{12577};\text{
if $K$ is a number field and }L\neq\mathbb{Q}.\end{cases}$

If $L=\mathbb{Q}$, then solvability of $f(x)\equiv 0\hskip 2.84526pt(\text{mod
}\Delta)$ is the only condition to check.

Readers may note that the condition $(2)$ in the above theorem involves Galois
group of the splitting field. This condition is useful in creating families of
examples of polynomials satisfying (1.1), for instance, as in Section $4$. On
the other hand, the condition $(3)$ is feasible for checking intersectivity of
a polynomial since it only involves constants $\Delta,D,\Delta^{\prime}$ and
$D^{\prime}$, all of which can be calculated from the polynomial $f$ itself.

The rest of this article is organized into three more sections. The second
section contains statements and proofs of results that are required to prove
Theorem $1$. Section $3$ contains the proof of Theorem $1$. Section $4$
contains some examples, consequences and discussions pertaining to the main
result.

##  2 Some Preliminary Results

###  2.1 Roots Modulo Primes and the Artin Symbol

Proposition $1$ gives a necessary and sufficient condition for an irreducible
polynomial to have roots in $K_{\mathfrak{p}}$ for primes $\mathfrak{p}$ that
do not divide the resultant of the polynomial $f$. Although this proposition
can be proved using the decomposition and inertia subgroups of $\text{Gal
}(L/K)$, we choose to provide a more accessible and elementary proof.

######  Proposition 1.

Let $K$ be a global field and $g(x)\in\mathcal{O}_{K}[x]$ be a separable
irreducible polynomial. Let $L$ be the splitting field of $g$ and $G$ be the
Galois group of $L$ over $K$. Also, let $\mathfrak{p}\in\mathcal{O}_{K}$ be a
prime that does not divide the resultant $\mathfrak{r}$ of the polynomial $g$.
Then $g$ has a root modulo $\mathfrak{p}$ if and only if there exists an
automorphism in $\big{[}\frac{L/K}{\mathfrak{p}}\big{]}$ that fixes some root
of $g$.

###### Proof.

Let $\theta_{1},\theta_{2},\ldots,\theta_{n}$ be the distinct roots of $g(x)$
in $L$ and $\beta\in\mathbb{P}(L)$ be a prime that lies above $\mathfrak{p}$.
Assume that $g(\alpha)\equiv 0\hskip 2.84526pt(\text{mod }\mathfrak{p})$ for
some $\alpha\in\mathcal{O}_{K}$. We will show that the Frobenius automoprhism
$\varphi_{\beta}\in\big{[}\frac{L/K}{\mathfrak{p}}\big{]}$ fixes one of the
roots of $g$. Let us write $\varphi$ for $\varphi_{\beta}$ to avoid too many
subscripts.

Since

$g(\alpha)=\prod_{i=1}^{n}(\alpha-\theta_{i})\equiv 0\hskip
2.84526pt(\text{mod }\mathfrak{p}),$

we have that
$\mathfrak{p}\mathcal{O}_{K}\mid\big{(}\prod_{i=1}^{n}\alpha-\theta_{i}\big{)}\mathcal{O}_{K}$,
and hence
$\mathfrak{p}\mathcal{O}_{L}\mid\big{(}\prod_{i=1}^{n}\alpha-\theta_{i}\big{)}\mathcal{O}_{L}$.

Since $\beta$ is a prime above $\mathfrak{p}$, we also have
$\beta\mathcal{O}_{L}\mid\mathfrak{p}\mathcal{O}_{L}$, which along with
$\mathfrak{p}\mathcal{O}_{L}\mid\big{(}\prod_{i=1}^{n}\alpha-\theta_{i}\big{)}\mathcal{O}_{L}$
gives
$\beta\mathcal{O}_{L}\mid\big{(}\prod_{i=1}^{n}\alpha-\theta_{i}\big{)}\mathcal{O}_{L}$.
Therefore, $\beta\mathcal{O}_{L}\mid(\alpha-\theta_{j})$ for some
$j\in\\{1,2,\ldots,n\\}$, i.e.,

$\theta_{j}\equiv\alpha\hskip 2.84526pt(\text{mod }\beta).$

The reduction of $\theta_{j}$ modulo $\beta$ is well-defined because $\beta$
is a prime above $\mathfrak{p}$, and $\mathfrak{p}$ is a prime that does not
divide the resultant and hence, the leading coefficient of $g$. Since
$\alpha\in\mathcal{O}_{K}$, by definition of the Frobenius automorphism we
have,

$\varphi(\alpha)=\alpha\equiv\alpha^{N\mathfrak{p}}\hskip 2.84526pt(\text{mod
}\beta).$

Therefore, we have from (1.2) that,

$\varphi(\theta_{j})\equiv\theta_{j}^{N\mathfrak{p}}\equiv\alpha^{N\mathfrak{p}}\equiv\alpha\equiv\theta_{j}\hskip
2.84526pt(\text{mod }\beta)$

and hence

$\theta_{j}\equiv\varphi^{-1}(\theta_{j})\hskip 2.84526pt(\text{mod
}\varphi^{-1}(\beta)).$ (2.1)

Using $T:=\varphi^{-1}\in G$, (2.1) becomes

$\theta_{j}\equiv T(\theta_{j})\hskip 2.84526pt(\text{mod }T(\beta)).$

Since $T$ is an automorphism, $T(\theta_{j})=\theta_{l}$ for some
$l\in\\{1,2,\ldots,n\\}$ and hence we have

$(\theta_{j}-\theta_{l})\equiv 0\hskip 2.84526pt(\text{mod }T(\beta)).$ (2.2)

Here, reduction of $(\theta_{j}-\theta_{l})$ modulo $T(\beta)$ is well-defined
because $\theta_{j}$ is equivalent to
$\alpha\in\mathcal{O}_{K}\subseteq\mathcal{O}_{L}$ modulo $\beta$ and hence
$\theta_{l}=T(\theta_{j})$ is also equivalent to an integral element of $L$.
Recall that the resultant $\mathfrak{r}$ is defined to be

$a^{2n-1}\prod_{1\leq r\neq s\leq n}(\theta_{r}-\theta_{s}),$

where $a$ is the leading coefficient of $g$. Since
$\theta_{1},\theta_{2},\ldots,\theta_{n}$ are distinct roots of $g(x)$, if
$j\neq l$ then from (2.2) we have that

$\mathfrak{r}\equiv 0\hskip 2.84526pt(\text{mod }T(\beta)),$ (2.3)

i.e., $\mathfrak{r}\mathcal{O}_{L}\subseteq T(\beta)\mathcal{O}_{L}$, which
implies $\mathfrak{r}\mathcal{O}_{K}\subseteq\mathfrak{p}\mathcal{O}_{K}$
because $\beta$, and hence $T(\beta)$, is a prime above $\mathfrak{p}$.
However, $\mathfrak{r}\mathcal{O}_{K}\subseteq\mathfrak{p}\mathcal{O}_{K}$ is
a contradiction to the fact that $\mathfrak{p}$ is a prime in
$\mathcal{O}_{K}$ that does not divide the resultant $\mathfrak{r}$ of $g$.
Therefore, we must have $j=l$ and hence
$T(\theta_{j})=\varphi^{-1}_{\beta}(\theta_{j})=\theta_{j}$ i.e. the
automorphism $\varphi_{\beta}$ in $\big{[}\frac{L/K}{\mathfrak{p}}\big{]}$
fixes the root $\theta_{j}$.

For the other direction, assume that $\theta$ is a root of $g(x)$ which is
fixed by some Frobenius automorphism
$\varphi_{\beta}\in\big{[}\frac{L/K}{\mathfrak{p}}\big{]}$, where $\beta$ is a
prime in $\mathcal{O}_{L}$ dividing $\mathfrak{p}$. Therefore, we have

$\varphi_{\beta}(\theta)=\theta\equiv\theta^{N\mathfrak{p}}\hskip
2.84526pt(\text{mod }\beta).$

Since $\theta^{N\mathfrak{p}}\equiv\theta\hskip 2.84526pt(\text{mod }\beta)$
we must have that $\theta\equiv\alpha\hskip 2.84526pt(\text{mod }\beta)$ for
some $\alpha\in\mathcal{O}_{K}$. Since $\theta$ was a root of $g$, we have
$g(\alpha)\equiv g(\theta)\equiv 0\hskip 2.84526pt(\text{mod }\beta)$ and
hence $g(\alpha)\equiv 0\hskip 2.84526pt(\text{mod }\mathfrak{p})).$ ∎

###  2.2 Relating the Absolute Discriminant and the Ideal D in the Number
Field Case

We will prove two propositions that relate the ideal $D$ defined in Theorem
$1$ to the absolute discriminant $d_{L}$ of the splitting field $L$ of $f$, in
the case when $K$ is a number field. The first proposition in this subsection
is known but we include the proof for the sake of keeping the presentation
largely self-contained. A proof of the second proposition when $K=\mathbb{Z}$
appears in [3], which we adapt for number fields.

######  Proposition 2.

Let $M_{1},M_{2},\ldots,M_{\gamma}$ be finitely many finite algebraic
extensions of a number field $K$ and $M$ be the composite of these finitely
many extensions. Let $d_{1},d_{2},\ldots,d_{\gamma}$ be the relative
discriminant of $M_{1},M_{2},\ldots,M_{\gamma}$ respectively and $d$ be that
of $M$. Then

$d\mid\bigg{(}\prod_{i=1}^{\gamma}d_{i}^{[M:M_{i}]}\bigg{)}.$

###### Proof.

We will prove the proposition by induction on $\gamma$; let $\gamma=2$. Let
$\mathfrak{D}$, $\mathfrak{D}_{1}$, $\mathfrak{D}_{2}$ and
$\mathfrak{D}^{(1)}$ respectively denote the relative different of the field
extensions $M/K$, $M_{1}/K$, $M_{2}/K$ and $M/M_{1}$. Note that the different
$\delta_{L/K}(\alpha)$ of an element $\alpha\in\mathcal{O}_{L}$ is defined in
terms of its minimal polynomial $m(x)\in\mathcal{O}_{K}[x]$ as

$\delta_{L/K}(\alpha)=\begin{cases}m^{\prime}(\alpha)\text{ ; if
}L=K(\alpha)\\\ 0\text{ ; if }L\neq K(\alpha)\end{cases}$

We will also use the fact that the different $\mathfrak{D}_{L/K}$ of a field
extension $L/K$ is the ideal generated by the set of all the element-wise
differents $\\{\delta_{L/K}(\alpha):\alpha\in\mathcal{O}_{L}\\}$ ( see [11,
pp. 198, Theorem (2.5)]). First, we want to show that
$\mathfrak{D}^{(1)}\mid\mathfrak{D}_{2}$, i.e.,
$\mathfrak{D}_{2}\subseteq\mathfrak{D}^{(1)}$.

Let $\zeta\in\mathcal{O}_{M_{2}}$ and $M_{2}=K(\zeta)$ without loss of
generality (since $\delta_{M_{2}/K}(\zeta)=0$ otherwise). By definition, we
have that $\delta_{M_{2}/K}(\zeta)=m^{\prime}(\zeta)$ where
$m(x)\in\mathcal{O}_{K}[x]$ is the minimal polynomial of $\zeta$ over $K$. On
the other hand, the minimal polynomial $p(x)\in\mathcal{O}_{M_{1}}[x]$ of
$\zeta$ over the field $M_{1}$ divides $m(x)$. Therefore,
$\delta_{M/M_{1}}(\zeta)=p^{\prime}(\zeta)\mid
m^{\prime}(\zeta)=\delta_{M_{2}/K}(\zeta)$ which according to definition of
different gives that
$\delta_{M_{2}/K}(\zeta)\in\mathfrak{D}_{M/M_{1}}=\mathfrak{D}^{(1)}$.
Therefore, we have that $\mathfrak{D}^{(1)}\mid\mathfrak{D}_{2}$.

Now, using the the multiplicativity of the relative differents over the tower
of field extension $M/M_{1}/K$ (for instance, see [11, pp. 195, propostion 2])
we also have

$\mathfrak{D}=\mathfrak{D}^{(1)}\mathfrak{D}_{1},$

which together with $\mathfrak{D}^{(1)}\mid\mathfrak{D}_{2}$ implies that
$\mathfrak{D}\mid\mathfrak{D}_{1}\mathfrak{D}_{2}$. Upon applying $N_{M/K}$ we
have that $d=N_{M/K}(\mathfrak{D})$ divides

$N_{M/K}(\mathfrak{D}_{1}\mathfrak{D}_{2})=N_{M_{1}/K}\big{(}N_{M/M_{1}}(\mathfrak{D}_{1})\big{)}\cdot
N_{M_{2}/K}\big{(}N_{M/M_{2}}(\mathfrak{D}_{2})\big{)}$

Since $N_{M/M_{i}}(\mathfrak{D_{i}})=\mathfrak{D}_{i}^{[M:M_{i}]}$, we have
that
$N_{M_{i}/K}\big{(}N_{M/M_{i}}(\mathfrak{D_{i}})\big{)}=d_{i}^{[M:M_{i}]}$,
which proves the proposition for $\gamma=2$.

In the general case, given any $\gamma\geq 3$, let $\widetilde{M}$ be the
composite of $M_{1},\ldots,M_{\gamma-1}$. Since $M$ is the composite of
$\widetilde{M}$ and $M_{\gamma}$, we have

$d\mid\big{(}e^{[M:\widetilde{M}]}\cdot d_{\gamma}^{[M:M_{\gamma}]}\big{)},$

where $e$ is the relative discriminant of $\widetilde{M}$. By inductive
assumption, we have that

$e\mid\prod_{i=1}^{\gamma-1}d_{i}^{[\widetilde{M}:M_{i}]},$

which upon using the fact that
$[M:M_{i}]=[M:\widetilde{M}]\cdot[\widetilde{M}:M_{i}]$ proves the
proposition. ∎

######  Proposition 3.

When $K$ is a number field, Using the notations defined for Theorem $1$, the
absolute discriminant $d_{L}$ divides $N_{K/\mathbb{Q}}(D)$.

###### Proof.

It suffices to prove that relative discriminant $d_{L/K}$ of $L$ divides $D$
in $K$; then the result follows by taking norm $N_{K/\mathbb{Q}}$ to the
ensuing divisibility relation. For every $i\in\\{1,2,\ldots,m\\}$:

  * •

Let $\alpha_{i}^{(1)}=\alpha_{i},\alpha_{i}^{(2)},\ldots,\alpha_{i}^{(n_{i})}$
be the $K$-conjugates of $\alpha_{i}$. Here $\alpha_{i}$ is the fixed root of
the irreducible factor $g_{i}$ of $f$.

  * •

For every $j\in\\{1,2,\ldots,n_{i}\\}$, let $L_{i}^{(j)}$ be the field
$K(\alpha_{i}^{(j)})$. Since each of the $\alpha_{i}^{(j)}$ are the roots of
the same irreducible polynomial $g_{i}$, we have that the relative
discriminant of each of the $L_{i}^{(j)}$ is equal to the relative
discriminant $d_{i}$ of $L_{i}$.

  * •

Let
$\widetilde{L_{i}}=K(\alpha_{i}^{(1)},\alpha_{i}^{(2)},\ldots,\alpha_{i}^{(n_{i}-1)},\alpha_{i}^{(n_{i})})$
be the splitting field of $g_{i}$, which is the composite of the fields
$L_{i}^{(1)},L_{i}^{(2)},\ldots$ , $L_{i}^{(n_{i})}$.

Therefore, the relative discriminant $\widetilde{d_{i}}$ of
$\widetilde{L_{i}}$ is such that

$\widetilde{d_{i}}\mid\prod_{j=1}^{n_{i}}d_{i}^{[\widetilde{L_{i}}:L_{i}^{(j)}]}=d_{i}^{(n_{i}-1)[\widetilde{L_{i}}:L_{i}^{(j)}]}\mid
d_{i}^{(n_{i}-1)(n_{i}-1)!}\mid\mathfrak{q}_{i}^{(n_{i}-1)(n_{i}-1)!}$ (2.4)

The first divisibility is from Proposition $2$ and the last divisibility
relation in (2.4) is a consequence of the fact that the discriminant
$\mathfrak{q}_{i}$ of the polynomial $g_{i}$ is always divisible by the
relative discriminant $d_{i}$ of $L_{i}=K(\alpha_{i})$, which we explain
below.

For a fixed $i$, let $n=n_{i}$ which is the degree of the irreducible factor
$g_{i}$, $a_{j}=a_{ij}$ and $\alpha=\alpha_{i}$. Consider the basis
$\\{\beta_{1},\beta_{2},\ldots,\beta_{n}\\}$ of $L_{i}$ over $K$:

$\\\ \beta_{1}=1\\\ \beta_{2}=a_{n}\alpha\\\ \ldots\\\
\beta_{i}=a_{n}\alpha^{i-1}+a_{n-1}\alpha^{i-2}+\ldots+a_{n-i+1}\alpha\\\
\ldots\\\
\beta_{n}=a_{n}\alpha^{n-1}+a_{n-1}\alpha^{n-2}+\ldots+a_{1}\alpha\\\ $

We claim that $\beta_{j}$ are integral for every $j=1,2,\ldots,n$. Note that
we have

$\beta_{n}a_{n}\alpha^{n-1}+a_{n-1}\alpha^{n-2}+\ldots+a_{n}\alpha=\frac{-a_{0}}{\alpha}-a_{1}$

and for every $1\leq i\leq(n-2)$ one has

$\\\
\beta_{n-i}=a_{n}\alpha^{n-i-1}a_{n-1}\alpha^{n-i-2}+\ldots+a_{i+2}\alpha\\\
=-\frac{a_{0}}{\alpha^{i+1}}-\frac{a_{1}}{\alpha}-\ldots-\frac{a_{i}}{\alpha}-a_{i+1}\\\
=\frac{\beta_{n-i+1}}{\alpha}-a_{i+1}\\\ $ (2.5)

Therefore, we will show that $\beta_{n-i}$ is integral for every $0\leq
i\leq(n-1)$ by induction. For $i=0$, note that since
$\beta_{n}=\frac{-a_{0}}{\alpha}-a_{1}$ it suffices to prove that
$y:=\frac{a_{0}}{\alpha}$ is integral. Consider the following series of
equivalent statements.

$\\\ a_{n}\alpha^{n}+a_{n-1}\alpha^{n-1}+\ldots+a_{1}\alpha+a_{0}=0\\\
\Leftrightarrow
a_{n}\alpha^{n-1}+a_{n-1}\alpha^{n-2}+\ldots+a_{1}+\frac{a_{0}}{\alpha}=0\\\
\Leftrightarrow\frac{a_{n}a_{0}^{n-1}}{y^{n-1}}+\frac{a_{n-1}a_{0}^{n-2}}{y^{n-2}}+\ldots+\frac{a_{2}a_{0}}{y}+a_{1}+y=0\\\
\Leftrightarrow y^{n}+a_{1}y^{n-1}+a_{2}a_{0}y^{n-2}+\ldots
a_{n-1}a_{0}^{n-2}y+a_{n}a_{0}^{n-1}=0,\\\ $

which shows that $y$ and hence $\beta_{n}$ is integral. Now, we assume that
$\beta_{n-i+1}$ is integral and show that $z:=\frac{\beta_{n-i+1}}{\alpha}$ is
also integral. Again, consider the following series of equivalent statements.

$\\\ a_{n}\alpha^{n}+a_{n-1}\alpha^{n-1}+\ldots+a_{1}\alpha+a_{0}=0\\\
\vspace{1mm}\Leftrightarrow
a_{n}\alpha^{n-i}+a_{n-1}\alpha^{n-i-1}+\ldots+a_{i+1}\alpha+\Big{(}a_{i}+\frac{a_{i-1}}{\alpha}+\ldots+\frac{a_{1}}{\alpha^{i-1}}+\frac{a_{0}}{\alpha^{i}}\Big{)}=0\\\
\vspace{1mm}\Leftrightarrow
a_{n}\frac{(\beta_{n-i+1})^{n-i}}{z^{n-i}}+a_{n-1}\frac{(\beta_{n-i+1})^{n-i-1}}{z^{n-i-1}}+\ldots+a_{i+1}\frac{(\beta_{n-i+1})}{z}-\beta_{n-i+1}=0\\\
\vspace{1mm}\Leftrightarrow
a_{n}\frac{(\beta_{n-i+1})^{n-i-1}}{z^{n-i}}+a_{n-1}\frac{(\beta_{n-i+1})^{n-i-2}}{z^{n-i-1}}+\ldots+a_{i+1}\frac{1}{z}-1=0\\\
\vspace{1mm}\Leftrightarrow-z^{n-i}+a_{i+1}z^{n-i-1}+a_{i+2}(\beta_{n-i+1})z^{n-i-2}+\ldots+a_{n-1}\big{(}\beta_{n-i+1}\big{)}^{n-i-2}z+a_{n}\big{(}\beta_{n-i+1}\big{)}^{n-i-1}=0,\\\
$

which shows that $z=\frac{\beta_{n-i+1}}{\alpha}$ and hence
$\beta_{n-i}=z-a_{i+1}$ is also integral. Since
$\beta_{1},\beta_{2},\ldots,\beta_{n}$ are integral in $L_{i}$, we have that
$\mathcal{O}[\beta_{1},\beta_{2},\ldots,\beta_{n}]\subseteq\mathcal{O}_{L_{i}}$.
However, we note that
$d(\beta_{1},\beta_{2},\ldots,\beta_{n})=\Big{|}\text{det}[\beta_{ij}]\Big{|}=\mathfrak{q}_{i}$,
where $\beta_{ij}$ is defined exactly similarly as $\beta_{i}$ but with the
$K$-conjugate $\alpha^{(j)}$ of $\alpha$.Therefore, from a well-known
relationship between the discriminants of $\mathcal{O}_{K}$-submodules (for
instance, see [11, pp. 11, Proposition 2.12]) we have that

$d(\beta_{1},\beta_{2},\ldots,\beta_{n})=\mathfrak{q}_{i}=\Big{[}\mathcal{O}_{L_{i}}:\mathcal{O}[\beta_{1},\ldots,\beta_{n}]\Big{]}^{2}d_{i},$

i.e, $d_{i}\mid\mathfrak{q}_{i}$.

On the other hand, the splitting field $L$ of the polynomial $f$ is the
composite of the splitting fields
$\widetilde{L_{1}},\widetilde{L_{2}},\ldots,\widetilde{L_{m}}$ of the
irreducible factors $g_{1},g_{2},\ldots,g_{m}$ respectively. Hence if
$d_{L/K}$ is the relative discriminant of $L$ then, Proposition $4$ gives

$d_{L/K}\mid\prod_{i=1}^{m}(\widetilde{d_{i}})^{[L:\widetilde{L_{i}}]}\mid\prod_{i=1}^{m}\bigg{(}\big{(}\widetilde{d_{i}}\big{)}^{n_{1}!n_{2}!\ldots
n_{i-1}!n_{i+1}!\ldots n_{m}!}\bigg{)}.$ (2.6)

From (2.4) and (2.6), we have that

$d_{L/K}\mid\prod_{i=1}^{m}\big{(}\mathfrak{q}_{i}\big{)}^{(n_{1}!\cdots
n_{m}!)(1-\frac{1}{n_{i}})}=D.$

∎

###  2.3 Least Prime Ideal in the Chebotarev Density Theorem

To show that the condition $(3)$ in Theorem $1$ is equivalent to the condition
$(2)$, we will employ upper bounds on the prime ideal in the Chebotarev
density theorem. The upper bound is well known in the number field case and we
use the following version that is taken from [2].

######  Proposition 4.

For every finite extension $K$ of $\mathbb{Q}$, for every finite Galois
extension $L(\neq\mathbb{Q})$ of $K$ and every conjugacy class $\mathcal{C}$
of Gal$(L/K)$, there exists a prime ideal $\mathfrak{p}$ of $K$ that is
unramified in $L$ such that:

  * •

$\bigg{[}\frac{L/K}{\mathfrak{p}}\bigg{]}=\mathcal{C}$ and

  * •

$N_{K/\mathbb{Q}}(\mathfrak{p})$ is a rational prime which satisfies

$N_{K/\mathbb{Q}}(\mathfrak{p})\leq|d_{L}|^{12577}.$

We also need a similar upper bound on the degree of the least prime ideal in
the Chebotarev density theorem, when $K$ is a finite separable extension of
$\mathbb{F}_{q}(T)$. Such an upper bound should ideally depend only upon the
field $K$ and the given polynomial $f$. Assume that $\mathbb{F}_{q^{l}}$ is
the integral closure of $\mathbb{F}_{q}$ in $L$, for some $l\geq 1$. The map

$\varphi:\mathbb{F}_{q^{l}}\longrightarrow\mathbb{F}_{q^{l}}\text{ given by
}\varphi(x)=x^{q}$

is the generator of the Gal$(\mathbb{F}_{q^{l}}/\mathbb{F}_{q})$. On the other
hand, we also have the surjective restriction Gal$(L/K)\rightarrow\rightarrow$
Gal$(\mathbb{F}_{q^{l}}/\mathbb{F}_{q})$. Since
Gal$(\mathbb{F}_{q^{l}}/\mathbb{F}_{q})$ is abelian, the image of a conjugacy
class $\mathcal{C}\subset$ Gal$(L/K)$ is a singleton set in
Gal$(\mathbb{F}_{q^{l}}/\mathbb{F}_{q})$. Let
$\varphi_{\mathcal{C}}:=\varphi^{n}\in$Gal$(\mathbb{F}_{q^{l}}/\mathbb{F}_{q})$
be the image of every element of $\mathcal{C}$ under this restriction map.
Given a conjugacy class $\mathcal{C}$ in $G=$ Gal$(L/K)$, define

$\pi_{\mathcal{C},n}:=\\{\mathfrak{p}\in\mathbb{P}_{n}(K):\bigg{[}\frac{L/K}{\mathfrak{p}}\bigg{]}=\mathcal{C}\\}.$

In addition, define $C_{1}=[L:K\mathbb{F}_{q}^{l}]$. We will use the following
effective version of the Chebotarev density theorem in function fields (see
[7, Proposition 6.4.8]).

######  Proposition 5.

Let $\mathcal{C}$ be a conjugacy class in $G=\text{Gal }(L/K)$ and
$n\in\mathbb{N}$. If $\varphi_{\mathcal{C}}=\varphi^{n}$, then

$\bigg{\lvert}\pi_{\mathcal{C},n}-\frac{|\mathcal{C}|}{C_{1}}\frac{q^{n}}{n}\bigg{\rvert}<\frac{2|\mathcal{C}|}{C_{1}\cdot
n}\Big{[}(C_{1}+g_{L})q^{n/2}+C_{1}(2g_{K}+1)q^{n/4}+g_{L}+C_{1}d\Big{]}.$
(2.7)

Here, $d=[K:\mathbb{F}_{q}(T)]$. On the other hand, if
$\varphi_{\mathcal{C}}\neq\varphi^{n}$ then $\pi_{\mathcal{C},n}$ is empty.

Given a Galois extension $L$ of $K$, which is a finite separable extension of
$\mathbb{F}_{q}(T)$, we have $K\subseteq K\mathbb{F}_{q^{l}}\subseteq L$.
Here, $K\mathbb{F}_{q^{l}}/K$ is a constant field extension and
$L/K\mathbb{F}_{q^{l}}$ is a geometric field extension. To obtain the upper
bound on the least prime ideal, we will use the Riemann-Hurwitz theorem (see
[12, Theorem 7.16]).

######  Proposition 6.

Let $E_{1}/E_{2}$ be a finite, separable and geometric extension of functions
fields. Then,

$2g_{E_{2}}-2=[E_{2}:E_{1}](2g_{E_{1}}-2)+\text{deg}_{E_{2}}(D_{E_{2}/E_{1}}),$
(2.8)

where $D_{E_{2}/E_{1}}$ is the different divisor of $E_{2}/E_{1}$.

Now, we are ready to prove an upper bound on the least prime ideal in the
Chebotarev density theorem for function fields.

######  Proposition 7.

Let $q$ be a prime power, $K$ be a finite separable extension of
$\mathbb{F}_{q}(T)$. Using notations defined in Theorem $1$, for any conjugacy
class $\mathcal{C}\subset\text{Gal }(L/K)$ with
$\varphi_{\mathcal{C}}=\varphi^{n}$, there exists an unramified prime
$\mathfrak{p}$ in $K$ such that

  * •

$\bigg{[}\frac{L/K}{\mathfrak{p}}\bigg{]}=\mathcal{C}$ and

  * •

$\text{deg}(\mathfrak{p})\leq\lceil
2\log_{q}\big{(}2\Delta^{\prime}+2dD^{\prime}+8g_{K}D^{\prime}+4\big{)}\rceil$.

###### Proof.

Equation (2.7) implies that $\pi_{\mathcal{C},n}$ is positive as soon as
$\frac{|\mathcal{C}|}{C_{1}}\frac{q^{n}}{n}$ is greater than or equal to the
RHS of (2.7). Note that the RHS of (2.7) is smaller than

$\frac{2|\mathcal{C}|}{C_{1}\cdot
n}\bigg{(}2C_{1}+2g_{L}+2C_{1}g_{K}+dC_{1}\bigg{)}q^{n/2}.$

Therefore, an upper bound on the smallest $n$ such that
$\pi_{\mathcal{C},n}>0$ is the least $n$ such that

$\frac{|\mathcal{C}|}{C_{1}}\frac{q^{n}}{n}\geq\frac{2|\mathcal{C}|}{C_{1}\cdot
n}\bigg{(}2C_{1}+2g_{L}+2C_{1}g_{K}+dC_{1}\bigg{)}q^{n/2},$

i.e.

$n=\lceil 2\log_{q}\bigg{(}4C_{1}+4g_{L}+4C_{1}g_{K}+2dC_{1}\bigg{)}\rceil.$
(2.9)

Consider the tower of field extensions $K\subseteq
K\mathbb{F}_{q^{l}}\subseteq L$. Since genus does not change in a constant
field extension over a perfect field (for instance, using [12, Proposition
8.9]), we have that the genus of $K\mathbb{F}_{q^{l}}$ is equal to genus
$g_{K}$ of $K$. On the other hand, using the Riemann-Hurwitz formula (2.8) for
the geometric extension $L/K\mathbb{F}_{q^{l}}$ with $E_{2}=L$ and
$E_{1}=K\mathbb{F}_{q^{l}}$ gives us

$2g_{L}-2=(2g_{K}-2)C_{1}+\text{deg}_{E_{2}}(D_{E_{2}/E_{1}}),$

and hence

$4g_{L}=4g_{K}C_{1}-4C_{1}+4+2\cdot\text{deg}_{E_{2}}(D_{E_{2}/E_{1}}).$
(2.10)

The degree of the different divisor is
$\sum_{\mathfrak{p}\in\mathbb{P}(K)}\delta(\mathfrak{p})\text{
deg}(\mathfrak{p})$, where $\delta(\mathfrak{p})$ is the highest power of
$\mathfrak{p}$ dividing the discriminant and the sum is taken over the primes
$\mathfrak{p}$ that are ramified. Since the relative discriminant
$\mathfrak{q}=\mathfrak{p}_{1}^{b_{1}}\cdots\mathfrak{p}_{\nu}^{b_{\nu}}$ is
the relative norm of the different, the set of primes of $\mathbb{F}_{q}[T]$
that ramify in $L$ are a subset of
$\\{\mathfrak{p_{1}},\ldots,\mathfrak{p_{\nu}}\\}$. Therefore,

$\text{deg}_{E_{2}}(D_{E_{2}/E_{1}})\leq\sum_{i=1}^{\nu}b_{i}\text{
deg}(\mathfrak{p}_{i}).$ (2.11)

Using (2.10) and (2.11), we have that,

$4g_{L}\leq 4g_{K}C_{1}-4C_{1}+4+2\cdot\sum_{i=1}^{\nu}b_{i}\text{
deg}(\mathfrak{p}_{i})=4g_{K}C_{1}-4C_{1}+4+2\Delta^{\prime},$

which implies that

$(4C_{1}+4g_{L}+4C_{1}g_{K}+2dC_{1})\leq
8g_{K}C_{1}+2dC_{1}+4+2\Delta^{\prime}.$ (2.12)

Since the splitting field of the polynomial $f$ is the compositum of the
splitting fields of its individual irreducible factors, we have that
$[L:K]\leq\prod_{i=1}^{\nu}n_{i}!$. Therefore,

$C_{1}=[L:K\mathbb{F}_{q^{l}}]\leq[L:K]\leq\prod_{i=1}^{\nu}n_{i}!=D^{\prime}$
(2.13)

Using (2.9), (2.12) and (2.13), we have that an upper bound for the degree $n$
of the prime ideal in the Chebotarev density theorem is given by

$\lceil
2\log_{q}\big{(}2\Delta^{\prime}+2dD^{\prime}+8g_{K}D^{\prime}+4\big{)}\rceil$

which proves the proposition. ∎

##  3 Proof of Theorem 1

We will show that $(2)\longrightarrow(1)\longrightarrow(3)\longrightarrow(2)$,
among which the implication $(1)\longrightarrow(3)$ follows trivially from
definition of an intersective polynomial.

Proof of (2) implies (1).

If a prime $\mathfrak{p}\in\mathcal{O}_{K}$ does not divide $\mathfrak{q}$
then $f$ has a root in $K_{\mathfrak{p}}$, as a consequence of Proposition
$1$. To see this, we note that

$\text{Gal}(L/K)=G=\bigcup_{\sigma\in G}\sigma^{-1}U\sigma$

implies that every conjugacy class of $G$ intersects
$U=\bigcup_{i=1}^{m}H_{i}$. Using the notation $H_{i}=$ Gal
$(L/K(\alpha_{i}))$ defined for Theorem $1$, we have that every conjugacy
class $\bigg{[}\frac{L/K}{\mathfrak{p}}\bigg{]}$ intersects Gal
$(L/K(\alpha_{j}))$ for some $j\in\\{1,2,\ldots,m\\}$. In other words, some
element of $\bigg{[}\frac{L/K}{\mathfrak{p}}\bigg{]}$ fixes root of some
irreducible factor $g_{j}$ of $f$. Therefore, Proposition $1$ implies that
$g_{j}$, and hence $f$, has a root modulo $\mathfrak{p}$.

If $\mathfrak{p}$ divides $\mathfrak{q}$ (i.e.
$\mathfrak{p}=\mathfrak{p}_{i}$) then, pick a $\gamma\in\mathcal{O}_{K}$ such
that $f(\gamma)\equiv 0\hskip 2.84526pt(\text{mod }\Delta)$. Since
$\mathfrak{p}=\mathfrak{p}_{i}$ we have
$|\mathfrak{q}|_{\mathfrak{p}}=\mathfrak{p}_{i}^{-b_{i}}$. Furthermore, since
$|\Delta|_{\mathfrak{p}}=\mathfrak{p}_{i}^{-2b_{i}-1}$,

$|f(\gamma)|_{\mathfrak{p}}\leq\mathfrak{p}_{i}^{-2b_{i}-1}<\mathfrak{p}^{-2b_{i}}=|\mathfrak{q}^{2}|_{\mathfrak{p}}.$

Since $|f(\gamma)|_{\mathfrak{p}}<|\mathfrak{q}^{2}|_{\mathfrak{p}}$, we have
that $|g_{j}(\gamma)|_{\mathfrak{p}}<|\mathfrak{r}_{j}|^{2}_{\mathfrak{p}}$
for some $j\in\\{1,2,\ldots,m\\}$. On the other hand, by definition of the
resultant $\mathfrak{r}_{j}$, there exists $A(x),B(x)\in\mathcal{O}_{K}[x]$
such that

$A(x)g_{j}(x)+B(x)g_{j}^{\prime}(x)=\mathfrak{r}_{j}.$

Therefore, we have

$|g_{j}^{\prime}(\gamma)|_{\mathfrak{p}}=|g_{j}^{\prime}(\gamma)B(\gamma)|_{\mathfrak{p}}=|\mathfrak{r}_{j}-A(\gamma)g_{j}(\gamma)|_{\mathfrak{p}}\\\
=\text{max
}\\{|\mathfrak{r}_{j}|_{\mathfrak{p}},|A(\gamma)g_{j}(\gamma)|_{\mathfrak{p}}\\}=\text{max
}\\{|\mathfrak{r}_{j}|_{\mathfrak{p}},|g_{j}(\gamma)|_{\mathfrak{p}}\\}=|\mathfrak{r}_{j}|_{\mathfrak{p}}.$

We have used above that
$|A(\gamma)|_{\mathfrak{p}}=|B(\gamma)|_{\mathfrak{p}}=1$ because
$A(x),B(x)\in\mathcal{O}_{K}[x]$ and $\gamma\in\mathcal{O}_{K}$ and also the
fact that $g_{j}(x)$ is a separable polynomial and hence its derivative is not
identically zero. Therefore,
$|g_{j}^{\prime}(\gamma)|_{\mathfrak{p}}^{2}=|\mathfrak{r}_{j}|_{\mathfrak{p}}^{2}>|g_{j}(\gamma)|_{\mathfrak{p}}$.
Then, $g_{j}$ has a root in $K_{\mathfrak{p}}$ by the Hensel’s lemma (for
example, see [7, Proposition 3.5.2]). Now the result follows from the standard
application of the Chinese Remainder Theorem. $\square$

Proof of (3) implies (2). For primes $\mathfrak{p}$ dividing $\mathfrak{q}$,
start by picking a $\gamma\in\mathcal{O}_{K}$ such that $f(\gamma)\equiv
0\hskip 2.84526pt(\text{mod }\Delta)$. We can show exactly similarly as in the
proof of $(2)$ implies $(1)$ that $f$ has a root in $K_{\mathfrak{p}}$. For
the primes $\mathfrak{p}$ that do not divide $\mathfrak{q}$, lets prove the
result in the number field case first. We first assume that $L\neq\mathbb{Q}$.
Proposition $4$ implies that there exists an unramified prime
$\mathfrak{p}^{\prime}$ such that

  1. (a)

$\big{[}\frac{L/K}{\mathfrak{p}}\big{]}=\big{[}\frac{L/K}{\mathfrak{p}^{\prime}}\big{]}$
and

  2. (b)

$N_{K/\mathbb{Q}}(\mathfrak{p}^{\prime})\leq|d_{L}|^{12577}$

as long as $L\neq\mathbb{Q}$. First note that the condition $(b)$ above can be
replaced by

$N_{K/\mathbb{Q}}(\mathfrak{p}^{\prime})\leq|N_{K/\mathbb{Q}}(D)|^{12577},$
(3.1)

because $d_{L}$ divides $N_{K/\mathbb{Q}}(D)$ as proved in Proposition $3$.
Both $(a)$ and $(b)$ together imply that

$\big{[}\frac{L/K}{\mathfrak{p}}\big{]}\cap U\neq\emptyset$

if and only if

$\big{[}\frac{L/K}{\mathfrak{p}^{\prime}}\big{]}\cap U\neq\emptyset$

for $\mathfrak{p}^{\prime}$ satisfying (3.1). In other words, $f$ has a root
in $K_{\mathfrak{p}}$ if and only if $f$ has a root in
$K_{\mathfrak{p}^{\prime}}$ satisfying (3.1). By assumption of $(3)$, along
with Proposition $3$, we have that the set of
$\big{[}\frac{L/K}{\mathfrak{p}^{\prime}}\big{]}$ as $\mathfrak{p}^{\prime}$
runs through

$N_{K/\mathbb{Q}}(\mathfrak{p}^{\prime})\leq|N_{K/\mathbb{Q}}(D)|^{12577}$

is all of $G$. In other words, every conjugacy class in $G$ intersects $U$ and
hence $\cup_{\sigma\in G}\big{(}\sigma^{-1}U\sigma\big{)}=G$. When
$L=\mathbb{Q}$, $f$ splits into linear factors and all the roots of $f$ are
rational. Therefore, the Galois group only contains identity, which fixes the
root of every linear polynomial. Therefore, the Galois-theoretic condition in
$(2)$ is trivially satisfied.

In the case when $K$ is an extension of $\mathbb{F}_{q}(T)$, the proof follows
from exactly the same argument; except using the bound on the degree of least
prime ideal as given in Proposition 7. $\square$

##  4 Corollaries, Examples and Discussion.

######  Corollary 1.

Let $f(x)\in\mathcal{O}_{K}[x]$ be a polynomial with separable irreducible
factors. If $f$ is irreducible and of degree $\geq 2$, then $f$ cannot be
intersective. On the other hand, if $f$ is intersective but does not have a
root in $K$, then degree of $f$ must be at least $5$.

###### Proof.

We will use the notation defined before Theorem $1$. Assume that $f$ is
irreducible and of degree $\geq 2$. From irreducibility of $f$, we have
$U=H_{1}$ and since $\text{deg }(f)>1$, we also have $G\neq U$. Since
$U=H_{1}$ is a proper subgroup of $G$, we have that
$G/U=\\{g_{1}U,g_{2}U,\ldots,g_{k}U\\}$ for $k=\frac{|G|}{|U|}\geq 2$.
Therefore we have,

$\big{|}\bigcup_{\sigma\in
G}\sigma^{-1}U\sigma\big{|}=\big{|}\bigcup_{i=1}^{k}g_{i}^{-1}Ug_{i}\big{|}<k|U|-(k-1)=|G|-(k-1)<|G|$

because $k\geq 2$. Therefore, we have $G\neq\bigcup_{g\in G}g^{-1}Ug$ and
hence Theorem $1$ implies that $f$ cannot have a root modulo every ideal of
$\mathcal{O}_{K}$.

Now, assume that $\text{deg }(f)\leq 4$ and that $f$ has no roots in $K$. We
will prove that $f$ cannot have root modulo every ideal in $\mathcal{O}_{K}$.
Since $f$ satisfies (1.1), $f$ must be reducible by Corollary $1$. The
reducibility of $f$, along with the fact that $f$ has no roots in $K$, implies
that

$f(x)=\begin{cases}g_{1}(x)g_{2}(x)\hskip 5.69054pt\text{ or }\\\
g_{1}(x)^{2}\hskip 5.69054pt\text{ or }\\\ g_{1}(x)\end{cases},$

where $g_{1}$ and $g_{2}$ are irreducible quadratic polynomials in
$\mathcal{O}_{K}[x]$. In the first case, the splitting field $L$ of $f$ has
degree $4$ over $K$, whereas the splitting field of $L$ has degree $2$ in the
latter two cases.

We first deal with the case when the splitting field has degree $4$. Let
$\alpha_{i},\beta_{i}$ be roots of $g_{i}$, for $i=1,2$. Then the splitting
field of $f$ is $L=K(\alpha_{1},\alpha_{2})$ and the Galois group of splitting
field of $f$ is $G=\\{e,\sigma_{1},\sigma_{2},\sigma_{1}\sigma_{2}\\}$. Here,
$e$ is the identity map and

$\sigma_{i}(\alpha_{i})=\beta_{i}\hskip 5.69054pt\text{ and
}\sigma_{i}(\beta_{i})=\alpha_{i}\hskip 5.69054pt\text{ and $\sigma_{i}$ fixes
the roots of the other quadratic factor}.$

In other words, $G$ is isomorphic to the Klein $4$-group. Then, in the
notation of Theorem $1$ we have,

$H_{1}=\text{ Gal}(L/K(\alpha_{1}))=\\{e,\sigma_{2}\\}\hskip 5.69054pt\text{
and }H_{2}=\text{ Gal}(L/K(\alpha_{2}))=\\{e,\sigma_{1}\\}.$

Therefore, $U=H_{1}\cup H_{2}=\\{e,\sigma_{1},\sigma_{2}\\}$ and hence
$\cup_{g\in G}g^{-1}Ug=U\neq G$ i.e. $f$ does not satisfy condition $(2)$ of
Theorem $1$. Therefore, $f$ cannot be intersective.

Now we deal with the case when splitting field $L$ of $f$ has degree $2$ over
$K$. In this case, let $\alpha$ be the root of only irreducible quadratic
factor $g_{1}$. The splitting field is $L=K(\alpha)$ with $[L:K]=2$ and the
Galois group $G=$ Gal $(L/K)\simeq\mathbb{Z}/2\mathbb{Z}$ is generated by
$\sigma(\alpha)=-\alpha$. In the notation of Theorem $1$, the only element of
Gal $(L/K)$ that fixes the root $\alpha$ is the identity element, i.e.,
$U=\\{e\\}$. Therefore,

$\\{e\\}=\bigcup_{\sigma\in G}\big{(}\sigma^{-1}U\sigma\big{)}\neq G$

and hence $f$ cannot be intersective. ∎

###  4.1 An Example.

In this subsection, we will use Theorem $1$ to construct a family of examples
of intersective polynomials. Let $q$ be a power of some odd prime,
$K=\mathbb{F}_{q}(T)$ and let

$f(x)=(x^{2}-\theta_{1})(x^{2}-\theta_{2})(x^{2}-\theta_{1}\theta_{2})\in\mathcal{O}_{K}[x],$

where $\theta_{1}$ and $\theta_{2}$ are primes in
$\mathcal{O}_{K}=\mathbb{F}_{q}[T]$ that are non-associates. Recall that we
require $q$ to be odd here to ensure that the irreducible factors of $f$ are
all separable. To use the notations defined for Theorem $1$ we denote the
irreducible factors of $f$ as:

$g_{1}(x)=(x^{2}-\theta_{1}),\hskip
5.69054ptg_{2}(x)=(x^{2}-\theta_{2}),\hskip
5.69054ptg_{3}(x)=(x^{2}-\theta_{1}\theta_{2}).$

Since none of the $\theta_{i}$ can be square in $\mathcal{O}_{K}$, the
splitting field of the polynomial $f$ is

$L=K(\sqrt{\theta_{1}},\sqrt{\theta_{2}}).$

Fix the roots $\alpha_{1}=\sqrt{\theta_{1}}$, $\alpha_{2}=\sqrt{\theta_{2}}$ ,
$\alpha_{3}=\sqrt{\theta_{1}\theta_{2}}$ of $g_{1},g_{2}$ and $g_{3}$
respectively. Note that the Galois group of this extension is given by

$G=\\{e,\sigma_{1},\sigma_{2},\sigma_{1}\sigma_{2}\\}.$

Here $e$ is the identity map and for every $i,j\in\\{1,2\\}$

$\sigma_{i}(\sqrt{\theta_{j}})=\begin{cases}-\sqrt{\theta_{j}}\hskip
5.69054pt;i=j\\\ \sqrt{\theta_{j}}\hskip 5.69054pt;i\neq j.\end{cases}$

So, $G$ is isomorphic to the Klein four-group, where each non-identity element
has order $2$. As in Theorem $1$, let $H_{i}$ be the subgroup of $G$ that
fixes the root $\alpha_{i}$ of $g_{i}$. Then,

  * •

$H_{1}=\text{ Gal}(L/K(\sqrt{\alpha_{1}})=\\{e,\sigma_{2}\\}\leq G$,

  * •

$H_{2}=\text{ Gal}(L/K(\sqrt{\alpha_{2}})=\\{e,\sigma_{1}\\}\leq G$,

  * •

$H_{3}=\text{ Gal}(L/K(\sqrt{\alpha_{3}})=\\{e,\sigma_{1}\sigma_{2}\\}\leq G$.

Therefore,

$\bigcup_{\sigma\in G}\big{(}\sigma^{-1}U\sigma\big{)}=U=H_{1}\cup H_{2}\cup
H_{3}\cup H_{4}=\\{e,\sigma_{1},\sigma_{2},\sigma_{1}\sigma_{2}\\}=G.$

In addition, we also have that
$\mathfrak{q}=\mathfrak{q}_{1}\cdot\mathfrak{q}_{2}\cdot\mathfrak{q}_{3}$
where $\mathfrak{q}_{1},\mathfrak{q}_{2}\text{ and }\mathfrak{q}_{3}$ are
ideals generated by $\theta_{1},\theta_{2}$ and $\theta_{1}\theta_{2}$ in
$\mathbb{F}_{q}[T]$ (since $q$ is odd). Therefore,
$\mathfrak{q}=\langle\theta_{1}^{2},\theta_{2}^{2}\rangle$ and hence
$\Delta=\langle\theta_{1}^{5},\theta_{2}^{5}\rangle$. Since $\theta_{1}$ and
$\theta_{2}$ are non-associates, using the Chinese Remainder Theorem and $(2)$
of Theorem $1$, we have that $f(x)$ is intersective if and only if $f(x)\equiv
0\hskip 2.84526pt(\text{mod }\langle\theta_{i}^{5}\rangle)$ is solvable for
$i=1,2$.

In fact, a similar argument also gives the same result when the above
polynomial $f(x)$ has coefficients over the ring of integers of a number
field. Hence, we have the following corollary, where $\langle x\rangle$ is
used to denote the ideal $x\mathcal{O}_{K}$.

######  Corollary 2.

Let $K$ either be a number field or $\mathbb{F}_{q}(T)$ for an integer $q$
that is a power of an odd prime. Let $\theta_{1}$ and $\theta_{2}$ be non-
associate primes in $\mathcal{O}_{K}$. Then the polynomial

$f(x)=(x^{2}-\theta_{1})(x^{2}-\theta_{2})(x^{2}-\theta_{1}\theta_{2})\in\mathcal{O}_{K}[x]$

is intersective if and only if $\theta_{1}$ is a square modulo
$\langle\theta_{2}^{5}\rangle$ and $\theta_{2}$ is a square modulo
$\langle\theta_{1}^{5}\rangle$.

###### Proof.

From the explanation in 4.1, we have that $f(x)$ is intersective if and only
if $f(x)\equiv 0\hskip 2.84526pt(\text{mod }\langle\theta_{i}^{5}\rangle)$ is
solvable for $i=1,2$. It suffices to show that $f(x)\equiv 0\hskip
2.84526pt(\text{mod }\langle\theta_{1}^{5}\rangle)$ is solvable if and only if
$\theta_{2}$ is a square modulo $\langle\theta_{1}^{5}\rangle$. Analogously,
the same fact will hold when the roles of $\theta_{1}$ and $\theta_{2}$ is
reversed.

Now, we will show that neither $\theta_{1}$ nor $\theta_{1}\theta_{2}$ can be
a square modulo $\langle\theta_{1}^{5}\rangle$. In fact, we will only show
that $\theta_{1}\theta_{2}$ cannot be a square modulo
$\langle\theta_{1}^{5}\rangle$. An exactly analogous proof, with
$\theta_{1}\theta_{2}$ replaced by $\theta_{1}$, that $\theta_{1}$ is not a
square modulo $\langle\theta_{1}^{5}\rangle$.

Assume that $y^{2}\equiv\theta_{1}\theta_{2}\hskip 2.84526pt(\text{mod
}\langle\theta_{1}^{5}\rangle)$ for some $y\in\mathcal{O}_{K}$, i.e., $\
y^{2}-\theta_{1}\theta_{2}\in\langle\theta_{1}^{5}\rangle\subseteq\langle\theta_{1}\rangle$.
Since, $y^{2}-\theta_{1}\theta_{2}\in\langle\theta_{1}\rangle$, we have that
$\langle\theta_{1}\rangle\mid\langle y^{2}-\theta_{1}\rangle$ which implies
that $\langle\theta_{1}\rangle\mid\langle y^{2}\rangle$ and hence
$\langle\theta_{1}^{2}\rangle\mid\langle y^{2}\rangle$. However,
$\langle\theta_{1}^{2}\rangle\mid\langle y^{2}\rangle$ along with
$y^{2}-\theta_{1}\theta_{2}\in\langle\theta_{1}^{5}\rangle$ gives that
$\langle\theta_{1}^{2}\rangle\mid\langle\theta_{1}\theta_{2}\rangle$. This is
a contradiction because $\theta_{1}$ and $\theta_{2}$ are non-associates.
Therefore, the corollary is established. ∎

###  4.2 Optimality of the Upper Bound in Theorem 1

The Proposition 4, and hence upper bound in $(3)$ of Theorem $1$, can be
improved in the case when $K$ is a number field, under the Generalized Riemann
Hypothesis (GRH) for the Dedekind zeta function

$\zeta_{L}(s)=\sum_{I\in\mathcal{O}_{L}}\frac{1}{N_{L/\mathbb{Q}}(I)}.$

For example, assuming validity of the GRH for $\zeta_{L}(s)$, the upper bound
in Proposition $6$, can be replaced by $C(\log|d_{L}|)^{2}$ for some constant
$C$ (see comments on Corollary $1.2$ in [10, pp. 461–462]). Furthermore, it
was demonstrated in [6] that this is the best possible bound for a general
$L$. Therefore, under GRH we can replace the upper bound in $(3)$ of Theorem
$1$ by

$N_{K/\mathbb{Q}}(\mathfrak{p})\leq
C\big{(}\log|N_{K/\mathbb{Q}}(D)|\big{)}^{2}$

in the number field case. The upper bound in Proposition 4 admits significant
asymptotic improvements (for large enough $d_{L}$) (see [8] and [13]).
However, due to our interest in Theorem $1$ for a general polynomial, we
cannot use those results.

## Acknowledgement

The author would like to thank Dr. Ofir Gorodetsky for an illuminating email
conversation regarding the Chebotarev density theorem in global function
fields.

## References

  * [1] Ackelsberg, E. and Bergelson, V. (2021). A dynamical approach to bracket polynomials in finite characteristic and applications. Preprint. https://drive.google.com/file/d/1jqHeiYqQoShr_OiiDW6VUmbIJdMtlcd8/view.
  * [2] Ahn, J-H. and Kwon, S-H. (2019). An explicit upper bound for the least prime ideal in the Chebotarev density theorem. Ann. Inst. Fourier (Grenoble). 69 (3). 1411–1458.
  * [3] Berend, D. and Bilu, Y. (1996). Polynomials with Roots Modulo Every Integer. Proc. Amer. Math. Soc. 124 (6). 1663–1671.
  * [4] Bergelson, V., Leibman, A. and Lesigne, E. (2008). Intersective Polynomials and Polynomial Szemeredi Theorem. Adv. Math. 219\. 369–388.
  * [5] Bergelson, V. and Robertson, D. (2016). Polynomial Multiple Recurrence Over Rings of Integers. Ergodic Theory Dynam. Systems. 36 (5). 1354–1378.
  * [6] Fiori, A. (2019). Lower Bounds for the Least Prime in Chebotarev. Algebra Number Theory. 13 (9). 2199–2203.
  * [7] Fried, M. D. and Jarden, M. Field Arithmetic, 2nd Ed. Ergenbnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics. vol. 11. Springer-Verlag, Berlin. 2005.
  * [8] Kadiri, H., Ng, N. and Wong, P-J. (2019). The Least Prime Ideal in the Chebotarev Density Theorem. Proc. Amer. Math. Soc. 147 (6). 2289–2303.
  * [9] Kamae, T. and Mendés-France, M. (1978). Van der Corput’s Difference Theorem. Israel J. Math. 31 (3-4). 335–342.
  * [10] Lagarias, J.C. and Odlyzko, A. M. (1977). Effective Versions of the Chebotarev Density Theorem. Algebraic Number Fields: L-functions and Galois properties (Proc. Sympos. Univ. Durham, Durham, 1975). Academic Press, London, 409–464.
  * [11] Neukrich, J. Algebraic Number Theory. (Translated from German by Norbert Schappacher). A Series of Comprehensive Studies in Mathematics Springer-Verlag, New York. 1999.
  * [12] Rosen, M. Number Theory in Function Fields. Graduate Texts in Mathematics. Springer-Verlag, New York. 2002.
  * [13] Zaman, A. (2017). Bounding the Least Prime Ideal in the Chebotarev Density Theorem. Funct. Approx. Comment. Math. 57 (1). 115–142.


Harnessing  Coding Theory for Reliable Network Quantum Communication

Ching-Yi Lai, Senior Member, IEEE,
and Kao-Yueh Kuo, Member, IEEE

This article explores the application of coding techniques for fault-tolerant quantum computation and extends their usage to fault-tolerant quantum communication. We review repeater-based quantum networks, emphasizing the roles of coding theory and fault-tolerant quantum operations, particularly in the context of quantum teleportation. We highlight that fault-tolerant implementation of the Bell measurement enables reliable quantum communication without requiring a universal set of quantum gates. Finally, we discuss various quantum code candidates for achieving higher transmission rates.

§ INTRODUCTION

The field of quantum computing has revolutionized the computational landscape by offering unprecedented computing power compared to classical computers. The establishment of a quantum network, consisting of interconnected local quantum processors, opens up new horizons for applications beyond the realm of traditional Internet, including secure classical and quantum communications, delegated quantum computation, and distributed quantum computing [1].

Quantum Internet with quantum host nodes and repeater nodes.

Figure <ref> depicts the concept of a future quantum internet, where multiple distributed hosts are interconnected through direct quantum channels, predominantly implemented using optical fibers.
In situations where a direct quantum channel is limited by physical resources, several repeaters are employed to establish connections between distant host nodes. Each  host node possesses the capability to process general quantum information, while a repeater node specializes in specific quantum functions.
Moreover, reliable quantum memories are assumed to be present in each node, ensuring the availability of quantum resources for communication tasks.
We assume that two-way classical communication is feasible between any two nodes in the network. This means that each node can transmit classical bits to any other node, utilizing channels such as the classical Internet. Additionally, quantum communication through satellites is also a viable means of connecting two distant quantum networks.

The quantum internet involves two types of quantum communication: the transmission of quantum information and quantum-assisted communication of classical information.
The transmission of quantum messages is a fundamental aspect that goes beyond the capabilities of the traditional Internet, enabling various advanced tasks. However, there are scenarios where high-rate classical communication is required via the quantum internet.
In this article we discuss how   to reliably implement these two types of quantum communication.

Quantum information is encoded and processed using delicate quantum states, which are highly vulnerable to disturbances.
We would like to transmit quantum information using such quantum states through lossy quantum channels.
Moreover, local quantum operations are susceptible to imperfections. Nonetheless, we would like to have reliable quantum communication.
To address these challenges, extensive research has focused on fault-tolerant quantum operations through quantum error-correcting codes [2].

This article aims to review the concept of coding theory and elucidate how to  implement   a fault-tolerant quantum internet [3]. Each quantum function involved in the quantum internet, including quantum teleportation, superdense coding,  and entanglement swapping, can be integrated with quantum error correction techniques and will be explained in the following. Specifically, we focus on the utilization of teleportation-based error correction. Furthermore, we compare and analyze different quantum codes for achieving reliable teleportation-based quantum communication.
Effective sparse-graph quantum codes, particularly when nonlocal qubit connectivity is accessible, have the potential to generate EPR pairs at notably high rates. These advancements present promising opportunities to enhance the efficiency of quantum communication systems.

§ NETWORK QUANTUM COMMUNICATION

A qubit serves as the fundamental unit of quantum information. Similar to a classical bit, a qubit has two basis states denoted as $\ket{0}$ and $\ket{1}$. However,  qubits can also exist in a superposition state, which is a linear combination of $\ket{0}$ and $\ket{1}$. When measuring a qubit, we obtain a one-bit outcome that provides information about its value. The probability distribution of this outcome is determined by the coefficients associated with the $\ket{0}$ and $\ket{1}$ basis states in the qubit's superposition.

Entanglement is a notable quantum phenomenon that can occur between multiple qubits. One example of a two-qubit entangled state is the  Einstein–Podolsky–Rosen (EPR) pair, where there is an equal probability of both qubits being in the state $\ket{0}$ or both qubits being in the state $\ket{1}$. Remarkably, this entanglement remains regardless of the distance between the qubits. Thus EPR pairs shared between two distant parties allow  them to perform  protocols involving local operations and classical communication (LOCC) that are essential  for quantum communication.

(a)                                                            (b)

(a) Superdense coding. (b) Quantum teleportation.

Figure <ref> (a) illustrates the concepts of superdense coding [4], where two parties Alice and Bob share preexisting EPR pairs. By locally operating on  Alice's half of the EPR pair, it can be evolved into one of the four Bell states. Thus two classical bits are encoded in the two-qubit state.
To be more precise, the encoding process applies quantum bit-flip and quantum phase-flip operations based on the values of the two bits. At this stage, Bob learns nothing if he measures his half of the EPR pair. Then, Alice sends her qubit to Bob through a qubit channel and Bob performs a Bell measurement to determine which Bell state on his hand. Overall, two classical bits are transmitted
using one qubit channel and one pre-shared EPR pair.

Figure <ref> (b) illustrates the concepts of   quantum teleportation [5], where Alice and Bob once again share preexisting EPR pairs. In this scenario, Alice intends to transmit a qubit to Bob. Alongside her half of the EPR pair, she performs a Bell measurement on the two qubits. Consequently, Bob's half of the EPR pair is transformed into one of the four altered states corresponding to Alice's target qubit, but Bob remains unaware of the specific state until Alice discloses the two-bit measurement outcome. Subsequently, Bob applies a recovery operation, which involves quantum bit-flip and quantum phase-flip operations determined by the values of the two bits. In summary, this protocol enables the transmission of a qubit using two classical bit channels and one pre-shared EPR pair.

variablenode = [draw,fill=white, shape=circle,minimum size=1.em]
[fill=black,inner sep=1.5pt,shape=circle,label=above:Alice] (n0) at (-2,1.5)  ;
[fill=black,inner sep=1.5pt,shape=circle,label=above:Bob] (n1) at (6,1.5)  ;
[fill=black,inner sep=1.5pt,shape=circle,label=above:$R_{1,1}$] (n21) at (0,2)  ;
[fill=black,inner sep=1.5pt,shape=circle,label=below:$R_{1,2}$] (n22) at (0,1)  ;
[fill=black,inner sep=1.5pt,shape=circle,label=above:$R_{2,1}$] (n31) at (2,2)  ;
[fill=black,inner sep=1.5pt,shape=circle,label=below:$R_{2,2}$] (n32) at (2,1)  ;

[fill=black,inner sep=1.5pt,shape=circle,label=above:$R_{3,1}$] (n71) at (4,2)  ;
[fill=black,inner sep=1.5pt,shape=circle,label=below:$R_{3,2}$] (n72) at (4,1)  ;

[decorate,decoration=coil,aspect=0] (n0) – (n21);
[decorate,decoration=coil,aspect=0] (n22) – (n31); 		 		[decorate,decoration=coil,aspect=0] (n32) – (n71);
[decorate,decoration=coil,aspect=0] (n72) – (n1);
[green,thick]  (-2.9,-0.5) rectangle (-1.3,3.5);
[green,thick]  (5.2,-0.5) rectangle (6.8,3.5);
[blue!80]  (1.4,-0.5) rectangle (2.6,3.5);
[blue!80]  (-0.6,-0.5) rectangle (0.6,3.5);

[blue!80]  (3.4,-0.5) rectangle (4.6,3.5);

variablenode = [draw,fill=white, shape=circle,minimum size=1.em]
[fill=black,inner sep=1.5pt,shape=circle,label=above:Alice] (n0) at (-2,1.5)  ;
[fill=black,inner sep=1.5pt,shape=circle,label=above:Bob] (n1) at (6,1.5)  ;
[fill=lightgray,inner sep=1.5pt,shape=circle,label=above:$ $] (n21) at (0,2)  ;
[fill=lightgray,inner sep=1.5pt,shape=circle,label=below:$ $] (n22) at (0,1)  ;
[fill=black,inner sep=1.5pt,shape=circle,label=above:$R_{2,1}$] (n31) at (2,2)  ;
[fill=black,inner sep=1.5pt,shape=circle,label=below:$R_{2,2}$] (n32) at (2,1)  ;

[fill=lightgray,inner sep=1.5pt,shape=circle,label=above:$ $] (n71) at (4,2)  ;
[fill=lightgray,inner sep=1.5pt,shape=circle,label=below:$ $] (n72) at (4,1)  ;

[decorate,decoration=coil,aspect=0] (n0) – (n31);

[decorate,decoration=coil,aspect=0] (n32) – (n1);
[green,thick]  (-2.9,-0.5) rectangle (-1.3,3.5);
[green,thick]  (5.2,-0.5) rectangle (6.8,3.5);
[blue!80]  (1.4,-0.5) rectangle (2.6,3.5);
[blue!80]  (-0.6,-0.5) rectangle (0.6,3.5);

[blue!80]  (3.4,-0.5) rectangle (4.6,3.5);

variablenode = [draw,fill=white, shape=circle,minimum size=1.em]
[fill=black,inner sep=1.5pt,shape=circle,label=above:Alice] (n0) at (-2,1.5)  ;
[fill=black,inner sep=1.5pt,shape=circle,label=above:Bob] (n1) at (6,1.5)  ;
[fill=lightgray,inner sep=1.5pt,shape=circle,label=above:$ $] (n21) at (0,2)  ;
[fill=lightgray,inner sep=1.5pt,shape=circle,label=below:$ $] (n22) at (0,1)  ;
[fill=lightgray,inner sep=1.5pt,shape=circle,label=above:$ $] (n31) at (2,2)  ;
[fill=lightgray,inner sep=1.5pt,shape=circle,label=below:$ $] (n32) at (2,1)  ;

[fill=lightgray,inner sep=1.5pt,shape=circle,label=above:$ $] (n71) at (4,2)  ;
[fill=lightgray,inner sep=1.5pt,shape=circle,label=below:$ $] (n72) at (4,1)  ;

[decorate,decoration=coil,aspect=0] (n0) – (n1);

[green,thick]  (-2.9,-0.5) rectangle (-1.3,3.5);
[green,thick]  (5.2,-0.5) rectangle (6.8,3.5);
[blue!80]  (1.4,-0.5) rectangle (2.6,3.5);
[blue!80]  (-0.6,-0.5) rectangle (0.6,3.5);

[blue!80]  (3.4,-0.5) rectangle (4.6,3.5);

Repeater-based quantum channel.

To establish shared EPR pairs, one party generates local EPR pairs and transmits half of them to the other party via quantum channels. Subsequently, both parties engage in an LOCC  entanglement purification protocol to extract a small number of clean EPR pairs. These EPR pairs need to be consistently prepared and stored in quantum memory, ensuring their availability for future applications.

Long-distance quantum communication presents challenges due to noise interference and energy dissipation in quantum channels, which can lead to the destruction of quantum information. Quantum repeaters, similar to classical relays, are typically employed to enhance long-distance communication. However,
an arbitrary unknown quantum state cannot be cloned [2], limiting the reproduction and amplification of certain quantum states. Fortunately, for quantum communication, the preparation of   EPR pairs is sufficient, regardless of the messages to be transmitted. Through the entanglement swapping technique, it is possible to create long-distance EPR pairs for communication, rendering the quantum internet repeater-based.

Figure <ref> illustrates the concept of a repeater-based quantum channel, which enables the creation of a long-distance EPR pair between Alice and Bob. The process involves generating EPR pairs between adjacent nodes along the path from Alice to Bob.

Let us consider Repeater 1, which shares an EPR pair with Alice and another EPR pair with Repeater 2. By utilizing the principle of quantum teleportation, Repeater 1 can teleport one half of the EPR pair shared with Alice to Repeater 2, resulting in the creation of a shared EPR pair between Alice and Repeater 2. This procedure is known as an entanglement swapping. Consequently, through a series of entanglement swappings facilitated by transmitting classical bits from Alice to Bob, a long-distance EPR pair can be established between them.

§ CODING THEORY

We briefly introduce the coding theory. In digital systems, information is typically represented using a string of bits. When transmitting a data string through a communication channel, there is a probability that each bit may be flipped due to the presence of noise and imperfections in the channel.

An error-correcting code is an encoding algorithm that adds redundancy to digital information to protect it from noise. By introducing additional bits, the code allows for the detection or correction of a certain number of errors. While it is not possible to eliminate all errors, an effective error-correcting code reduces the error rate below the original physical error rate, making it valuable in practical applications.

In general, a code is a collection of bit strings, called codewords, which satisfy specific parity check conditions. A parity check involves verifying that the number of ones in a certain subset of a codeword is even. If a bit string passes all the parity checks, it is considered a valid codeword. Conversely, for invalid words, the outcomes of parity checks provide meaningful information about the error operation, called error syndrome. Based on the error syndrome, a decoding algorithm is employed to determine the most probable error and its corresponding recovery operation.

The minimum distance of a code represents the smallest number of errors that can transform a codeword into another codeword, which characterizes the code's error correction capability.
Meanwhile, the code rate is the ratio of the number of information bits to the code length.
An ideal code exhibits both a high rate and a high minimum distance.

One of the simplest error-correcting codes is the three-bit repetition (3-rep) code, which encodes 0 as 000 and 1 as 111.  The valid  codewords in the 3-rep code are 000 and 111, while 001, 010, 100, 011, 101, and 110 are considered invalid. It is evident that the parity of any two bits in a codeword is always even.
Using a majority vote, the 3-rep code can be decoded, enabling the correction of any single-bit error.
This code has rate $1/3$ and minimum distance $3$.

We next explain how the concepts of coding theory extended for quantum error correction [2].
In the quest to protect quantum information from errors, traditional coding techniques face obstacles due to the continuous nature of quantum noises and the limitations imposed by the no-cloning theorem.
Fortunately,   orthogonal basis states can be cloned using elementary quantum gates. Additionally, by correcting a discrete set of quantum errors, it becomes feasible to correct their linear combinations.  This enables the development of coding theory specifically tailored to address quantum bit-flip and phase-flip errors.

Among the various quantum codes, Calderbank–Shor–Steane (CSS) stabilizer codes are particularly valuable. They serve as the quantum counterpart to the parity-check codes. In these codes, information qubits are combined with ancillary qubits to form quantum codewords that satisfy certain bit parity-checks and phase parity-checks. Notably, these parity checks can be performed through stabilizer measurements on the quantum state without disturbing its encoded information. The measurement outcomes provide the error syndrome, which can be utilized to deduce the most likely error.

An example of a simple CSS stabilizer code is the 9-qubit Shor code, which employs two instances of the 3-rep code to independently check for bit-flips and phase-flips [2].

A  quantum code can be defined by a graph with parity-check nodes and qubit variable nodes.
Each parity-check node   examines the parity of qubit variable nodes which it is  connected to.
When the number of edges in the graph is relatively small,   the resultant quantum code is termed a sparse-graph or low-density parity-check (LDPC) quantum code.

A two-dimensional (2D) code structure is typically defined on a 2D lattice [6], while the framework for 3D/4D codes follows a similar approach. In contrast, a general sparse-graph quantum code may not inherently possess such a defined topology.
This distinction necessitates nonlocal interactions for its implementation.
However, sparse-graph  quantum codes possess the potential for high code rates and considerable code distance.

To illustrate, Fig. <ref> provides  examples of both a nine-qubit 2D surface code and the nine-qubit Shor code. In this representation, a circle represents a data qubit, a dark gray box represents a bit-flip check node, and a light gray box represents a phase-flip check node. Interactions between a qubit and a check node are depicted by connecting edges.

2D topological code						    sparse-graph code

0.1!	    0.2!

Examples of code structures, with circles representing qubit nodes and squares representing check nodes.

When devising a quantum code,  two crucial aspects come into play: Firstly, a code should allow feasible syndrome measurements. These measurements ideally involve only a small subset of qubits within a parity check. Sparse qubit interactions are preferred, as   multiple-qubit interactions can be challenging to implement. Furthermore, parity checks involving qubits in close proximity are more favorable as they are easier to implement.
Secondly, an efficient decoder is essential. Its decoding time should ideally be polynomial (preferably linear) in the code size. This becomes crucial as errors accumulate at the speed of gate operating times.

There are many decoding algorithms.
For decoding of topological codes, the minimum-weight perfect matching (MWPM) algorithm has been successfully applied [6]. In the case of  sparse-graph quantum codes, belief propagation (BP) decoding is commonly employed  due to its nearly linear complexity [7]. Notably, BP decoding can be extended to correct a combination of data and measurement errors [8]. Moreover, this approach shows promise in addressing other error types, such as gate errors.

§ FAULT-TOLERANT QUANTUM OPERATIONS

When Alice and Bob aim to employ encoded qubit communication, Alice needs to utilize an encoding circuit that involves single-qubit and two-qubit gates, state preparations, and possibly qubit measurements. However, in practice, all of these components are susceptible to faults, making it challenging to create the target qubit in the desired encoded state.

Upon receiving a channel-corrupted state, Bob is required to execute a decoding circuit and perform recovery operations. Nevertheless, the syndrome measurement outcomes will be affected by measurement imperfections. Moreover, the decoding quantum circuit itself, used for syndrome extraction, is subject to noise.

To achieve reliable quantum communication, the realization of fault-tolerant quantum operations, particularly the error correction block, becomes necessary. The fundamental concept is to replace each quantum operation with its encoded counterpart, and quantum error correction is continually applied to mitigate errors.
Since errors may propagate through two-qubit gates, each encoded operation has to be carefully designed  to be fault-tolerant so that
a small amount of errors will not evolve into an uncorrectable error for the underlying quantum error-correcting code.

(left) Bell measurement. (right) Fault-tolerant implementation of the Bell measurement based on the nine-qubit Shor code.
Each EC block denotes an error correction for the nine-qubit code.

Figure <ref> illustrates the circuit implementation of the Bell measurement and its corresponding encoded version. In each circuit, qubits are represented by horizontal wires, and the gates are applied from left to right.
There are three types of gates: two-qubit controlled-NOT (CNOT) gates, Hadamard (H) gates, and single-qubit measurements.

In this particular example, a single qubit is encoded into nine physical qubits using the 9-qubit Shor code. As a result, the encoded version of the CNOT, Hadamard gates, and qubit measurements are implemented in a bitwise fashion. Note that any single component error will not propagate  within the same codeword, highlighting the fault-tolerant nature of this encoded circuit. The bitwise style of implementation is particularly significant for CSS stabilizer codes with equal bit-flip and phase-flip checks.

The error correction blocks (ECs) shown in Fig. <ref> consist of syndrome measurements, syndrome-based decodings, and recovery operations.  There are various methods for performing syndrome measurements. In this context, we will focus on the Knill syndrome extraction method [9], which is based on quantum teleportation in Fig. <ref> (b).

Suppose that Alice possesses an $n$-qubit encoded state and shares $n$ EPR pairs with Bob. In this scenario, Alice can utilize teleportation to transmit her $n$-qubit state to Bob. To complete the teleportation process, Bob needs to deduce a logical recovery operation based on Alice's Bell measurement outcomes.
Remarkably, these outcomes encapsulate the  information regarding the logical bit-flip and phase-flip operations required for teleportation. Furthermore, the error syndromes pertaining to the errors present in the transmitted encoded state are also incorporated into the Bell measurement outcomes. As a result, Bob can execute a logical recovery operation and perform error correction based on the information obtained from the Bell measurements.

Moreover, this  teleportation-based error correction technique  can be locally implemented, provided that a local node can generate a sufficient number of EPR pairs. The process relies solely on shared EPRs and Bell measurements, as shown in Fig. <ref>, which can be fault-tolerantly implemented (without the ECs). Given that each host or repeater node within the quantum internet needs to consistently generate numerous EPR pairs, its quantum memory can be effectively maintained through the utilization of this teleportation-based error correction mechanism.

§ RELIABLE TELEPORTATION-BASED QUANTUM COMMUNICATION

In long-distance quantum communication or repeater-based quantum networks, repeater nodes play a crucial role in generating and distributing entangled pairs of qubits, as well as performing entanglement swapping and teleportation.

To ensure the high quality of the shared entangled pairs, entanglement purification techniques are employed.
The  process begins with one node generating a large number of EPR pairs and sending half   to the other node. Both nodes independently perform bit-flip and phase-flip checks on their respective qubits, and exchange the outcomes of these checks. By analyzing the outcomes, they   identify and recover errors, thereby purifying a subset of the shared EPR pairs. This procedure resembles the decoding process of an error-correcting code, but it requires two-way classical communication between the nodes. Consequently, the rate of EPR generation is primarily limited by the delay in exchanging classical messages.

Entanglement purification utilizes basic quantum gates and two-qubit EPR states. However, it demands significant resources due to its continuous requirement.
For more efficient and reliable quantum communication, encoded EPR pairs are preferred. This allows for active quantum error correction to be executed while utilizing fewer resources.

An advanced approach assumes  that the host nodes possess the capability to encode and decode specific CSS stabilizer codes.    Two adjacent nodes first generate   high-quality EPR pairs using entanglement purification with two-way classical communication. Subsequently, one node locally encodes an EPR pair, and teleports half of it to the other node using one-way classical communication.
Errors in the encoded EPR are corrected locally, allowing the creation of encoded entangled pairs between adjacent nodes.
This method eliminates the need for two-way classical communication during quantum communication, resulting in a higher communication rate [10].

Another advanced approach involves direct quantum communication, assuming robust quantum computation capabilities with large CSS stabilizer codes and reliable quantum channels [11]. Here, one host node directly transmits encoded qubits through quantum channels, and the receiver node employs fault-tolerant teleportation-based error correction to recover the state. This process bypasses the need for prior entanglement purification and effectively handles channel losses through the quantum code.

Both advanced approaches enable the creation of an encoded version of the repeater-based quantum channel  in Fig. <ref>, facilitating fault-tolerant quantum communication. However,  their effectiveness relies on maintaining a physical error rate lower than the error threshold of the underlying CSS stabilizer code.
Consequently, the hardware requirements for achieving fault-tolerant quantum communication using CSS stabilizer codes remain quite demanding in current technology. The need to maintain a low physical error rate poses significant challenges for practical implementation.

§ RELIABLE QUANTUM-ASSISTED CLASSICAL COMMUNICATION

Similarly to the previous discussion, the central component of superdense coding is the Bell measurement, which can be fault-tolerantly implemented using a CSS stabilizer code. In the scenario where Alice and Bob share an EPR pair, Alice encodes her half of the pair into a CSS code and performs logical bit-flip and phase-flip operations based on the two bits to be transmitted. Bob then performs a half-logical Bell measurement on his half of the EPR pair and the received qubits to decode the classical bits.

This scenario falls under the realm of entanglement-assisted quantum coding theory [12], focusing on the transmission of classical bits.  It can be assumed that the error rate on Bob's halves of the EPR pairs can be lower due to quantum memory protection, using teleportation-based error correction with local EPR pairs.

While all the components in this setting can be fault-tolerantly implemented, a thorough discussion on resource tradeoff analysis is necessary to ascertain the quantum advantage of a fault-tolerant implementation of quantum-assisted classical communication. Without such analysis, the benefits might not justify the costs, particularly in instances demanding ultra-high rate communication.

§ CANDIDATES OF QUANTUM CODES FOR PRACTICAL IMPLEMENTATION

In fault-tolerant quantum computing, it is important to consider various error sources during the error-correction procedure. These include  data errors, gate errors, ancilla preparation errors, and measurement errors. Accounting for these errors in every error syndrome extraction round establishes the circuit noise model.
Moreover, the practical complexity of decoding a quantum code is contingent on the fault-tolerant error correction procedure.
Consequently, quantum codes that enable simple fault-tolerant error correction implementations and efficient decoding are highly desirable.

Many near-term quantum systems exhibit high-fidelity quantum operations primarily for locally-connected qubits.
For instance, in superconducting qubits, interaction between nearby qubits is feasible, while establishing connections between distant qubits presents considerable challenges. Trapped-ion qubits or neutral-atom qubits permit some degree of nonlocal interaction. However, establishing long-distance interactions between qubits often incurs high costs, leading to inevitable fidelity loss.
Photonic qubits, also known as flying qubits, possess the potential for long-distance entanglement generation and transmission due to their inherent mobility. Yet, establishing connectivity between distant flying qubits is more challenging and may necessitate specialized techniques for efficient long-range interactions.

In such scenarios,  2D topological codes offer suitable solutions. These codes can be realized on a planar layout, necessitating minimal qubit interactions. Surface codes, a prominent example, exhibit a rectangular grid structure and employ small parity checks on four qubits. This design choice balances gate density and expedites syndrome extraction. However, their code rate diminishes as the code length increases.

In future quantum systems with enhanced qubit connectivity, the adoption of higher-dimensional topological codes or more generalized sparse-graph quantum codes becomes feasible. These advancements unlock the potential for single-shot decoding, enabling effective error correction through every round of noisy syndrome extraction. This immediate error treatment prevents severe error accumulation and simplifies error analysis.

Specifically, the aforementioned teleportation-based error correction allows for single-shot decoding [13]. It relies on an equivalent number of EPR pairs as the code size, and the outcomes of Bell measurements constitute all the error syndromes. Thus, the decoding complexity for this single-shot error-correction method remains within the same order of complexity.

Conversely, when each parity check is individually measured (utilizing raw syndrome extraction or Shor-type syndrome extraction [2]), multiple rounds of noisy syndrome measurements, typically proportional to the minimum distance, are necessary to obtain reliable error syndromes.
This effectively increases the number of error variables, which significantly amplifies the decoding complexity. However, this  can be circumvented if certain nonlocal interactions are allowed, facilitating teleportation-based quantum error correction.

Numerous technologies assume local connections as the foundation for establishing accurate quantum memories and facilitating nonlocal logical connections. Within this framework, topological codes serve as the foundational correction mechanism, upon which sparse-graph quantum codes are implemented. This setup can be considered as a concatenated coding system. Exploring cross-layer optimization for overhead and performance is a future research focus.

§.§ EPR generation rate

Utilizing high code-rate quantum codes  presents notable advantages in boosting  EPR generation rates, particularly in large-scale quantum systems featuring arbitrary qubit connectivity.
To illustrate, let us consider the EPR generation rate when a host node receives half of the logical EPR pairs, protected by a specific quantum code, and uses teleportation-based error correction to rectify these pairs. For simplicity, we will exclude the overhead involved in encoding EPR states at the source node.

The rate of EPR generation at the receiving node hinges on the speed of error correction, where local EPR pairs are initially generated, followed by Bell measurements on halves of these local pairs and the received qubits. A round of error correction, comprising an ancilla preparation step, two CNOT steps, and one measurement step, typically takes approximately $4T$ time units. Here, $T$ represents the time unit for elementary gate operations or qubit measurements determined by the underlying quantum technology.

In this model, errors occurring in gates and measurements can  translate into data errors, leading to a higher effective  data error rate [13]. We perform a rough estimation of this effective data error rate, assuming all gates and measurements have the same error rate $p_g$, while the EPR communication error rate is $p_c$. In teleportation-based error correction, the outcome of a single-qubit measurement in the Bell measurement is impacted by two ancillary state preparations, two CNOT gates, one single-qubit measurement, and the communication error in the EPR pair. A pessimistic estimate of the effective error rate could be $p_c+5p_g$.

We compare the EPR generation rates between topological codes and sparse-graph codes. Assuming communication errors are dominant with an error rate of $p_c=5\%$, while gates have a less severe error rate of $p_g=0.1\%$, the effective data error rate roughly amounts to $5.5\%$. Our target is to achieve a decoding logical error rate of around $10^{-4}$.

Let us consider a scenario where the receiving node has a large-scale quantum device capable of processing 68,200 physical qubits. In teleportation-based error correction of an $n$-qubit code, $2n$ ancillary qubits are required. Thus the host node can process roughly $68200/3n$ code blocks.

First, consider the 2D rotated surface codes, where one information qubit is encoded in a code block. To meet our criteria, a surface code with  minimum distance   $d=17$ is needed <cit.>, and its code length is $n=d^2=289$. Consequently, the host node can simultaneously process approximately $78$ code blocks. Decoding this many blocks every $4T$ yields an EPR generation rate of $78/4 = 19.5$ units per $T$ time.

Next, let us examine a random sparse-graph code with a length of $n=3786$ and a rate of $1/4$, which meets our performance criteria <cit.>.
This code has low density of parity checks, where each parity-check operates on an average of 16 qubits. The receiving node can process roughly six code blocks. However, each code block encodes 946 information qubits. Therefore, the EPR generation rate becomes $946 \times 6 / 4 = 1419$ units every $T$. This represents an approximate 72-fold improvement compared to the surface code case.

This demonstrates how nonlocal connectivity enables efficient utilization of system resources, resulting in a significantly enhanced EPR generation rate.

§ CONCLUSION

In this article, we have explored repeater-based quantum networks and provided an overview of coding theory and fault-tolerant quantum operations. We have discussed the fault-tolerant implementation of Bell measurements and teleportation, along with their combination with error correction techniques. Various code schemes designed for fault-tolerant quantum computation can be extended for fault-tolerant quantum communication, with a focus on transmission rates. Importantly, the requirement of universality for quantum communication is not necessary. We have compared different quantum codes for teleportation-based quantum communication.

Continuous-variable quantum error-correcting codes, such as those based on Gottesman–Kitaev–Preskill (GKP) states [14], can be employed in quantum communication. GKP qubits enable the measurement of phase displacement errors as continuous variables while preserving the quantum information. This property facilitates decoding techniques similar to classical received vector decoding with soft information. Additionally, one can explore the concatenation of GKP codes with general CSS stabilizer codes for improved performance and error correction capabilities.

In an advanced packet-based quantum network, the transmission of quantum messages is divided into packets, similar to classical data packets in the internet, which are routed through various nodes. However,  quantum packets cannot be cloned and the packet loss problem may put inherent limitations in packet switching network.   To overcome the challenges of packet loss, one approach is to encode the quantum message using a quantum secret sharing scheme, where each packet is assigned a share [15]. This encoding scheme ensures that the arrival of quantum packets can be verified through heralding. In the event of packet loss, the remaining shares can be utilized to regenerate the missing packet. This procedure can be seen as a variant of quantum error-correcting codes, tailored specifically for packet-based quantum networks.
One may develop a systematic method for addressing packet loss by exploring different coding schemes and studying their theoretical limits.

§ ACKNOWLEDGMENTS

CYL was supported by the National Science and Technology Council in Taiwan, under Grant
111-2628-E-A49-024-MY2, 112-2119-M-A49-007, and 112-2119-M-001-007.

[1]
S. Wehner, D. Elkouss, and R. Hanson, “Quantum internet: A vision for the road
ahead,” Science, vol. 362, no. 6412, 2018.

[2]
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum
Information.1em plus 0.5em minus 0.4emCambridge University
Press, 2000.

[3]
S. Muralidharan, J. Kim, N. Lütkenhaus, M. D. Lukin, and L. Jiang,
“Ultrafast and fault-tolerant quantum communication across long distances,”
Phy. Rev Lett., vol. 112, p. 250501, 2014.

[4]
C. H. Bennett and S. J. Wiesner, “Communication via one- and two-particle
operators on Einstein-Podolsky-Rosen states,” Phys. Rev. Lett.,
vol. 69, pp. 2881–2884, 1992.

[5]
C. H. Bennett, G. Brassard, C. Crepeau, R. Jozsa, A. Peres, and W. K. Wootters,
“Teleporting an unknown quantum state via dual classical and
Einstein-Podolsky-Rosen channels,” Phys. Rev. Lett., vol. 70, pp.
1895–1899, 1993.

[6]
E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, “Topological quantum
memory,” J. Math. Phys., vol. 43, pp. 4452–4505, 2002.

[7]
K.-Y. Kuo and C.-Y. Lai, “Exploiting degeneracy in belief propagation decoding
of quantum codes,” npj Quantum Inf., vol. 8, 2022, article no. 111.
See also https://arxiv.org/abs/2104.13659.

[8]
A. Ashikhmin, C.-Y. Lai, and T. A. Brun, “Quantum data-syndrome codes,”
IEEE J. Sel. Areas Commun., vol. 38, pp. 449–462, 2020.

[9]
E. Knill, “Quantum computing with realistically noisy devices,”
Nature, vol. 434, p. 39, 2005.

[10]
L. Jiang, J. M. Taylor, K. Nemoto, W. J. Munro, R. Van Meter, and M. D. Lukin,
“Quantum repeater with encoding,” Phys. Rev. A, vol. 79, p. 032325,

[11]
A. G. Fowler, D. S. Wang, C. D. Hill, T. D. Ladd, R. Van Meter, and L. C.
Hollenberg, “Surface code quantum communication,” Phys. Rev. Lett.,
vol. 104, p. 180503, 2010.

[12]
T. Brun, I. Devetak, and M.-H. Hsieh, “Correcting quantum errors with
entanglement,” Science, vol. 314, p. 436, 2006.

[13]
Y.-C. Zheng, C.-Y. Lai, T. A. Brun, and L.-C. Kwek, “Constant depth
fault-tolerant clifford circuits for multi-qubit large block codes,”
Quantum Sci. Technol., vol. 5, p. 045007, 2020.

[14]
D. Gottesman, A. Kitaev, and J. Preskill, “Encoding a qubit in an
oscillator,” Phys. Rev. A, vol. 64, p. 012310, 2001.

[15]
N. Yu, C.-Y. Lai, and L. Zhou, “Protocols for packet quantum network
intercommunication,” IEEE Trans. Quantum Eng., vol. 2, 2021, article
no. 4103709.