\section{Introduction}
Massive/ultra-massive multiple-input multiple-output (MIMO) communication has become one of the enabling technologies for 5G and beyond networks owing to the high spectral efficiency and link reliability. Given the increasing size of antenna arrays, efficient MIMO detection algorithms are of significant importance to unleash the full potential of  MIMO systems, and a series of research has been conducted to balance the performance and complexity \cite{SD,AMPJSTSP,EPdetector}. To this end, the maximum likelihood (ML) detector achieves the optimal performance, but its complexity increases exponentially with the number of decision variables because of the exhaustive search. As a result, it cannot be deployed in practical systems. Hence,  many suboptimal linear detectors, such as zero-forcing (ZF) and minimum mean-squared error (MMSE) detectors, have been proposed to reduce the complexity at the cost of performance.

Recently, iterative detectors based on approximate message passing (AMP) \cite{dynamicAMP} and expectation propagation (EP) \cite{EP} have been proposed. The AMP-based detector \cite{AMPJSTSP} is of low complexity and easy to implement in practice because only the matrix-vector multiplication is involved. However, it only favors the scenario when the elements of the MIMO channel matrix follows independent identically distributed (i.i.d.) sub-Gaussian distribution with zero mean. In contrast, the EP-based detector \cite{EPdetector} achieves Bayes-optimal performance when the channel matrix is unitarily invariant, but has a higher complexity than the AMP-based detector owing to involves a matrix inversion.

Owing to its strong ability to extract useful features from data, deep learning (DL) has been recently utilized in the physical layer design of wireless communications \cite{Khlaed_JSAC,6G_khaled,Modeldriven18DL}, such as millimeter-wave channel estimation \cite{DL2018HE}, channel state information (CSI) feedback \cite{DL2018Wen}, and data detection \cite{MIMO_Detection20DL}. For MIMO detection, it has been shown that DL can improve traditional message passing detectors, such as AMP, orthogonal AMP (OAMP) \cite{OAMP}, and EP, with different strategies. Specifically, the OAMP-Net and OAMP-Net2 detectors \cite{MIMO_Detection20DL} were developed by unfolding the OAMP detector and introducing several learnable parameters.
Recently, graph neural networks (GNNs) have been applied to wireless communications \cite{YifeiGNN2}, such as to learn a message-passing solution for  inference problems \cite{Scotti20GNN,Kosasih20DL}. In particular, a GNN-based MIMO detector was developed by utilizing a pair-wise Markov random field (MRF) model \cite{Scotti20GNN}. As GNNs can capture the structure of the data into the feature vectors for the nodes and update them through message-passing methods, they are very promising solutions for enhancing  the performance of the message-passing-based detectors. For example, the GEPNet was developed by incorporating the GNN into the EP detector\cite{Kosasih20DL}.
However, the computational complexity of GEPNet is still high because of the matrix inversion in each layer. An efficient DL-based MIMO detection algorithm, which strikes a good balance between the performance and complexity, is by far not available.

In this paper, we develop a model-driven DL-based MIMO detector, AMP-GNN, where the neural network structure is obtained by unfolding the AMP detector and incorporating the GNN module. In particular, the GNN module receives the equivalent AWGN observation from the AMP as input and outputs a refined version back to AMP at each layer. It can improve the accuracy of the equivalent AWGN observation for AMP algorithm. As a result,  it is helpful for multi-user interference (MUI) cancellation. The AMP-GNN also inherits the low-complexity of the AMP detector and improves the performance with the GNN module. Simulation results shall demonstrate that the proposed AMP-GNN significantly outperforms existing the AMP detector and achieve comparable performance as the state-of-the-art GEPNet detector while reducing the computational complexity.

\emph{Notations}---For any matrix $\mathbf{A}$, $\mathbf{A}^{T}$, $\mathbf{A}^{*}$, and ${ \mathrm{tr}}(\mathbf{A})$ will denote the transpose, conjugate, and  trace of $\mathbf{A}$, respectively. In addition, $\mathbf{I}$ is the identity matrix, $\mathbf{0}$ is the zero matrix, and $\mathbf{1}_n$ is the $n$-dimensional all-ones vector. A proper complex Gaussian distribution with mean $\boldsymbol{\mu}$ and covariance $\boldsymbol{\Omega}$ can be described by the probability density function (pdf):
\begin{equation*}
  \mathcal{N}_{\mathbb{C}}(\mathbf{z};\boldsymbol{\mu},\boldsymbol{\Omega})=\frac{1}{\mathrm{det}(\pi \boldsymbol{\Omega})}
  e^{-(\mathbf{z}-\boldsymbol{\mu})^{H}\boldsymbol{\Omega}^{-1}(\mathbf{z}-\boldsymbol{\mu})}
\end{equation*}

\section{Problem Formulation and Algorithm Review}\label{Problem}
In this section, we first formulate the MIMO detection problem by adopting a Bayesian inference. To better understand the proposed AMP-GNN, we will review the AMP-based MIMO detector.
\subsection{MIMO Detection}
 We assume an uplink multi-user MIMO (MU-MIMO) systems where the base station (BS) equips $M$ antennas sevres $N$ single-antenna users. The symbol vector $\bar{{\mathbf{x}}}\in\mathbb{C}^{M\times1}$ is transmitted over a Rayleigh fading channel $\bar{{\mathbf{H}}} \in \mathbb{C}^{M \times N}$. Each element of $\bar{{\mathbf{H}}}$ and $\bar{{\mathbf{x}}}$ are drawn from an i.i.d. complex Gaussian distribution and the $Q$-QAM constellation, respectively. The received signal $\bar{\mathbf{y}}\in\mathbb{C}^{M\times1}$ is given by
\begin{equation}\label{eq1}
  \bar{\mathbf{y}}=\bar{\mathbf{H}}\bar{\mathbf{x}}+\bar{\mathbf{n}},
\end{equation}
where $\bar{\mathbf{n} }\sim \mathcal{N}_{\mathbb{C}}(0,\sigma^{2}\mathbf{I}_{M})$ is the additive white Gaussian noise (AWGN).

To better implement our proposed AMP-GNN detector, we consider an equivalent real-valued representation for the MIMO detection problem which is obtained by considering the real $\mathfrak{R}(\cdot)$ and imaginary $\mathfrak{I}(\cdot)$ parts separately. Denote $\mathbf{x}=[\mathfrak{R}(\bar{\mathbf{x}})^{T}, \mathfrak{I}(\bar{\mathbf{x}})^{T}]^{T}$, $\mathbf{y}=[\mathfrak{R}(\bar{\mathbf{y}})^{T}, \mathfrak{I}(\bar{\mathbf{y}})^{T}]^{T}$, $\mathbf{n}=[\mathfrak{R}(\bar{\mathbf{n}})^{T}, \mathfrak{I}(\bar{\mathbf{n}})^{T}]^{T}$, and
\begin{equation}\label{eq2}
\mathbf{H}=\left[\begin{array}{c c c}
\mathfrak{R}(\bar{\mathbf{H}}) && -\mathfrak{I}(\bar{\mathbf{H}}) \\
\mathfrak{I}(\bar{\mathbf{H}}) && \mathfrak{R}(\bar{\mathbf{H}})
\end{array}\right].
\end{equation}
Then, the signal model in (\ref{eq1}) can be rewritten in terms of real vectors and matrix form as follows,
\begin{equation}\label{eq3}
\mathbf{y}=\mathbf{H}\mathbf{x}+\mathbf{n}.
\end{equation}

Based on the Bayes' theorem, the posterior probability $\mathcal{P}(\mathbf{x}|\mathbf{y},\mathbf{H})$ can be factorized as
\begin{equation}\label{eq4}
    \mathcal{P}(\mathbf{x}|\mathbf{y},\mathbf{H})=\frac{\mathcal{P}(\mathbf{y}|\mathbf{x},\mathbf{H})\mathcal{P}(\mathbf{x})}{\mathcal{P}(\mathbf{y}|{\mathbf{H}})}
 = \frac{\mathcal{P}(\mathbf{y}|\mathbf{x},\mathbf{H})\mathcal{P}(\mathbf{x})}{\int \mathcal{P}(\mathbf{y}|\mathbf{x},\mathbf{H})\mathcal{P}(\mathbf{x})d\mathbf{x}}.
\end{equation}
Given the posterior probability $\mathcal{P}(\mathbf{x}|\mathbf{y},\mathbf{H})$, the Bayesian MMSE estimate is obtained by
\begin{equation}\label{MMSE_estimate}
\hat{\mathbf{x}}=\int \mathbf{x} \mathcal{P}(\mathbf{x}|\mathbf{y},\mathbf{H})d\mathbf{x}.
\end{equation}

However, the Bayesian MMSE estimator is computationally intractable because the MMSE estimation in (\ref{MMSE_estimate}) involves a high-dimensional integral. In a recent study \cite{OAMP}, the AMP algorithm was proposed as an efficient alternative to recover signal $\mathbf{x}$. We will introduce the AMP-based detector in the following subsection.
\subsection{AMP-Based MIMO Detector}\label{sec:AMP}
\begin{algorithm}[!t]
\caption{AMP-based MIMO detector}
\label{Algorithm:BAMP}
{
\begingroup
\textbf{1. Input:} ${\mathbf{y}}$, ${\mathbf{H}}$, $\sigma^2$, $\mathcal{P}({\mathbf{x}})$. \\
\textbf{2. Initialization:} $\hat{x}_n^{(1)}=0$, $\hat{v}_n^{(1)}=\frac{N}{M}$, $Z_m^{(0)}=y_m$.\\
\textbf{3. Output:} $\hat{{\mathbf{x}}}^{(T)}$.\\
\textbf{4. Iteration:} \\
\For{$t=1,\cdots, T$}
{
 \setlength\abovedisplayskip{0pt}
 \setlength\belowdisplayskip{0pt}
 \begin{subequations}
 \begin{align}
 V_m^{(t)}&=\sum_{n=1}^N |h_{mn}|^2\hat{v}_n^{(t)} \label{Equ:AMP1}\\
 Z_m^{(t)}&=\sum_{n=1}^Nh_{mn}\hat{x}_n^{(t)}-\frac{V_m^{(t)}(y_m-Z_m^{(t-1)})}{\sigma^2+V_m^{(t-1)}} \label{Equ:AMP2}\\
 \Sigma_n^{(t)}&=\left(\sum_{m=1}^M\frac{|h_{mn}|^2}{\sigma^2+V_m^{(t)}}\right)^{-1} \label{Equ:AMP3}\\
 r_n^{(t)}&= \hat{x}_n^{(t)}+\Sigma_n^{(t)}\sum_{m=1}^M\frac{h_{mn}^{*}(y_m-Z_m^{(t)})}{\sigma^2+V_m^{(t)}} \label{Equ:AMP4}\\
 \hat{x}_{n}^{(t+1)}& =\mathbb{E}\{x_n|r_n^{(t)},\Sigma_n^{(t)}\}
 \label{Equ:AMP5}\\
 \hat{v}_{n}^{(t+1)}& =\text{Var}\{x_n|r_n^{(t)}, \Sigma_n^{(t)}\}
 \label{Equ:AMP6}
 \end{align}
 \end{subequations}
}
\endgroup
}
\end{algorithm}
\begin{figure*}
  \centering
  \includegraphics[width=15cm]{AMP_GNN}
  \caption{\small{.~~The structure of the proposed AMP-GNN detector.}}\label{fig:AMPGNN}
\end{figure*}

The AMP algorithm has been proposed to solve sparse linear inverse problems in compressed sensing \cite{OAMP}. In Algorithm \,\ref{Algorithm:BAMP}, we summarize the AMP algorithm for MIMO detection\footnote{Note that we consider a complex-valued AMP-based MIMO detector in  Algorithm \,\ref{Algorithm:BAMP} and the equivalent real-valued form can be derived with the equivalent real-valued representation in (\ref{eq2}) and (\ref{eq3}) accordingly.}, where $m$ and $n$ are the indexes of the antenna in the BS and users, respectively. The main principle of the algorithm is to decouple the posterior probability $\mathcal{P}(\mathbf{x}|\mathbf{y},\mathbf{H})$ into a series of $\mathcal{P}(x_{n}|\mathbf{y},\mathbf{H}), (n=1,2,\ldots,N)$, in an iterative way. In particular, $\mathcal{P}(x_{n}|\mathbf{y},\mathbf{H})$ is assumed to be a Gaussian distribution and obtained from the equivalent AWGN model
\begin{equation}\label{eqAWGN}
    r_{n}^{(t)} = x_{n} + w_{n}^{(t)},
\end{equation}
where  $w_{n}^{(t)}\sim \mathcal{N}_{\mathbb{C}}(w_{n}^{(t)};0,\Sigma_n^{(t)})$.

To better understand Algorithm \ref{Algorithm:BAMP}, we first provide a brief explanation for each equation in Algorithm \ref{Algorithm:BAMP} with the detailed derivation given in \cite{dynamicAMP}. Specifically, (\ref{Equ:AMP1}) and (\ref{Equ:AMP2}) compute the variance and mean estimation for ${\mathbf{z}} ={\mathbf{H}}{\mathbf{x}}$, respectively. Then,  (\ref{Equ:AMP3}) calculates the equivalent noise variance $\Sigma_n^{(t)}$ while
(\ref{Equ:AMP4}) gives the equivalent AWGN observation $r_n^{(t)}$. Finally, (\ref{Equ:AMP5}) and (\ref{Equ:AMP6}) perform the posterior mean and variance estimation for the equivalent AWGN model (\ref{eqAWGN}). As the transmitted symbol is assumed to be drawn from the $Q$-QAM set $\mathcal{S}=\{s_{1}, s_{2}, \ldots, s_{Q}\}$, the results in (\ref{Equ:AMP5}) and (\ref{Equ:AMP6}) are given by
\begin{equation}\label{eqmean}
  \hat{x}^{(t+1)}_{n} = \frac{\sum_{s_{i} \in \mathcal{S}}s_{i}\mathcal{N}_{{\mathbb{C}}}(s_{i};r_n^{(t)}, \Sigma_n^{(t)})p(s_{i})}{\sum_{s_{i} \in \mathcal{S}}\mathcal{N}_{{\mathbb{C}}}(s_{i};r_n^{(t)}, \Sigma_n^{(t)})p(s_{i})},
\end{equation}
\begin{equation}\label{eqvar}
  \hat{v}^{(t+1)}_{n} = \frac{\sum_{s_{i} \in \mathcal{S}}|s_{i}|^{2}\mathcal{N}_{{\mathbb{C}}}(s_{i};r_n^{(t)}, \Sigma_n^{(t)})p(s_{i})}{\sum_{s_{i} \in \mathcal{S}}\mathcal{N}_{{\mathbb{C}}}(s_{i};r_n^{(t)}, \Sigma_n^{(t)})p(s_{i})}
  -|\hat{x}^{(t+1)}_{n}|^{2}.
\end{equation}

As can be observed in Algorithm \,\ref{Algorithm:BAMP}, the performance of the AMP-based MIMO detector is mainly determined by the accuracy of the assumed equivalent AWGN model (\ref{eqAWGN}).  In \cite{dynamicAMP}, it was shown that the equivalent AWGN model is asymptotically accurate when the dimensions of the system tend to infinity, i.e.,  $M, N \rightarrow \infty$. However, in practical MIMO systems especially with high MUI, the performance of the AMP-based MIMO detector is far from optimal and even has an error floor owing to the inaccurate assumption. Furthermore,  the existing state-of-the-art GEPNet detector requires matrix inversion, which is very complex. These observations motivate us to improve the AMP-based MIMO detector with the DL technique.
\section{AMP-GNN Detector}\label{OAMP-Net}
In this section, we propose an AMP-GNN detector for MIMO detection. First, we present the network structure of the AMP-GNN detector and introduce the GNN module in detail. Then, the computational complexity of the AMP-GNN is analyzed and compared with other MIMO detectors.
\subsection{AMP-GNN Architecture}
Given the important advantages of GNN, such as learning to capture the MUI information, here we exploit them to improve the AMP detector in this article. The block diagram of the AMP-GNN is illustrated in Fig.\,\ref{fig:AMPGNN}. Specifically,  the network consists of $T$ cascade layers, and each layer has the same structure that contains a GNN module and a conventional AMP algorithm shown in Algorithm \,\ref{Algorithm:BAMP}. In particular, the input of the AMP-GNN is the received signal $\mathbf{y}$ and the initial value is set as $\hat{\mathbf{x}}^{(1)}=\mathbf{0}$ and $\hat{\mathbf{v}}^{(1)}=\frac{N}{M}\mathbf{1}_N$, and the output is the final estimate $\hat{\mathbf{x}}^{(T)}$ of signal $\mathbf{x}$. For the $t$-th layer of the AMP-GNN, the inputs are the estimated signal $\hat{\mathbf{x}}^{(t-1)}$ and $ \hat{\mathbf{v}}^{(t-1)}$ from the $(t-1)$-th layer and the received signal $\mathbf{y}$.
As we have introduced the AMP-based MIMO in Section \ref{sec:AMP}, we will introduce  the GNN module in the next subsection.
\subsection{The GNN Module}
GNNs have been  recently adopted in wireless communications as they can incorporate the graph topology of the wireless network into the neural network design \cite{YifeiGNN2}. The GNN model adopted in the AMP-GNN is called the message passing neural network (MPNN) and the message passing rules are illustrated in Fig.\,\ref{fig:GNN}. Similar to  \cite{Scotti20GNN}, the GNN in the AMP-GNN is composed of three main modules: a propagation module, an aggregation module, and a readout module. The first two modules operate at all layers while the readout module is involved only after the last layer.

As the pair-wise MRF is used to model the structured dependency of a set of random variables ${\mathbf{x}} = \{x_{1},\cdots,x_{N}\}$ by an undirected graph $G = \{V, E\}$, it can be adopted to model the correlation of the nodes in GNNs. Specifically, the $n$-th variable node is characterized by a self potential $\phi(x_n)$, and the $(n,j)$-th pair of edge is characterized by a pair potential $\psi(x_n,x_j)$, which are given by
\begin{subequations}\label{phi_and_psi}
            \begin{equation}\label{phi}
\phi(x_n) = {\mathsf{e}} {\mathsf{x}} {\mathsf{p}} \left( \frac{1}{\sigma^2} {\mathbf{y}}^T {\mathbf{h}}_n x_n - \frac{1}{2}  {\mathbf{h}}_n^T {\mathbf{h}}_n x_n^2  \right) \mathcal{P}(x_n),
            \end{equation}
            \begin{equation}\label{psi}
\psi(x_n,x_j) = {\mathsf{e}} {\mathsf{x}} {\mathsf{p}} \left(- \frac{1}{\sigma^2} {\mathbf{h}}_n^T {\mathbf{h}}_j x_n x_j\right),
            \end{equation}
\end{subequations}
respectively, where $n,j \in \{1,\ldots, N\}$ and $n \neq j$. The posterior probability $ p_{\mathrm{GNN}}({\mathbf{x}}|{\mathbf{y}})$ corresponding to the pair-wise MRF can be obtained by GNN and written as \cite{Scotti20GNN}
\begin{equation}\label{p_x_y_GNN}
 p_{\mathrm{GNN}}({\mathbf{x}}|{\mathbf{y}})
 =\frac{1}{Z} \prod_{n=1}^N \phi(x_n)
 \prod_{\substack{j=1\\mathrm{j} \neq n}}^N \psi(x_n,x_j),
\end{equation}
where $Z$ is a normalization constant. As the GNN consists of the nodes and edges and is used to infer the posterior probability, we incorporate the mean $r_{n}^{(t)}$ and variance $\Sigma_n^{(t)}$  obtained from  (\ref{Equ:AMP3}) and (\ref{Equ:AMP4}) into the attribute ${\mathbf{a}}_n^{(t)}$  of the variable node $x_n$ by concatenating the mean and variance as
\begin{equation}\label{concat}
{\mathbf{a}}_n^{(t)} = \left[ r_{n}^{(t)}, \Sigma_n^{(t)} \right].
\end{equation}
To compute $p_{\mathrm{GNN}}({\mathbf{x}}|{\mathbf{y}})$ in \eqref{p_x_y_GNN}, we utilize the node and edge feature vectors corresponding to the self and pair potentials in \eqref{phi} and \eqref{psi}, respectively. Denote ${\mathbf{u}}_n^{(\ell)}$ as the node feature vector.  Its initial value is calculated from encoding the information of the received signal ${\mathbf{y}}$, corresponding channel vector ${\mathbf{h}}_n$, and noise variance $\sigma^2$.  The encoding process is implemented by using a single layer neural network given by
\begin{equation}\label{GNN_init}
 {\mathbf{u}}_n^{(0)} = {\mathbf{W}}_1 \cdot [{\mathbf{y}}^T {\mathbf{h}}_n, {\mathbf{h}}_n^T {\mathbf{h}}_n, \sigma^2]^T + {\mathbf{b}}_1,
\end{equation}
where ${\mathbf{W}}_1 \in \mathbb{R}^{N_u \times 3}$ is a learnable matrix, ${\mathbf{b}}_1 \in \mathbb{R}^{N_u}$ is a learnable vector, and $N_u$ is the size of the feature vector.
The edge feature vector  $\mathbf{f}_{jn} \triangleq \left[ {\mathbf{h}}_n^T {\mathbf{h}}_j, \sigma^2 \right] $ is obtained by extracting the pair potential information from \eqref{psi} and  utilized for the message passing of the GNN.
\begin{figure}[t]
  \centering
  \includegraphics[width=7.2cm]{GNN}
  \caption{\small{.~~Message passing and update for GNNs.}}\label{fig:GNN}
\end{figure}
Next, we will elaborate the details of each module in the MPNN, including the propagation, the aggregation, and the readout module.
\subsubsection{\textbf{Propagation module}}
For any pair of variable nodes $x_n$ and $x_j$, there is an edge to connect them. Each edge first concatenates the received feature vectors ${\mathbf{u}}_n^{(\ell-1)}$ and ${\mathbf{u}}_j^{(\ell-1)}$ with its own feature vector $\mathbf{f}_{jn}$ as
${\mathbf{c}}_{n}^{(l-1)} = [{\mathbf{u}}_n^{{(}\ell-1{)}}, {\mathbf{u}}_j^{{(}\ell-1{)}}, \mathbf{f}_{jn}]$. Then, it uses the concatenated features ${\mathbf{c}}_{n}^{(l-1)}$ as the input for the multi-layer perceptron (MLP). Therefore, the output of the MLP is given by
\begin{equation}\label{factor_to_var}
{\mathbf{m}}_{jn}^{(\ell)} = {\mathsf{D}} \left( {\mathbf{c}}_{n}^{(l-1)} \right),
\end{equation}
where  $\mathsf{D}$ is the MLP operation. In the propagation module, each edge has an MLP with two hidden layers of sizes $N_{h_1}$ and $N_{h_2}$ and an output layer of size $N_u$.
Furthermore, the rectifier linear unit (ReLU) activation function is used at the output of each hidden layer. Finally, the outputs ${\mathbf{m}}_{jn}^{(\ell)}$ are fed back to the nodes as shown in Fig.\,\ref{fig:GNN}.
\subsubsection{\textbf{Aggregation  module}}
The $n$-th variable node  sums all the incoming messages ${\mathbf{m}}_{jn}^{(\ell)}$ from its connected edges  and concatenates the sum of the ${\mathbf{m}}_{jn}^{(\ell)}$  with the node attribute ${\mathbf{a}}_n^{(t)}$ as ${\mathbf{m}}_n^{(\ell)}  = \left[\sum_{\substack{j=1\\mathrm{j} \neq n}}^N {\mathbf{m}}_{jn}^{(\ell)},  {\mathbf{a}}_n^{(t)} \right]$. The ${\mathbf{m}}_n^{(\ell)}$ is used to compute the node feature vector ${\mathbf{u}}_n^{(\ell)}$ as
 \begin{subequations}\label{GRU_MLP}
            \begin{equation}\label{GRU}
 {\mathbf{g}}_n^{(\ell)} = {\mathsf{U}} \left( {\mathbf{g}}_n^{(\ell-1)}, {\mathbf{m}}_n^{(\ell)}  \right),
            \end{equation}
            \begin{equation}\label{MLP}
 {\mathbf{u}}_n^{(\ell)}= {\mathbf{W}}_2 \cdot {\mathbf{g}}_n^{(\ell)} + {\mathbf{b}}_2,
            \end{equation}
\end{subequations}
where the function $\mathsf{U}$ is specified by the gated recurrent unit (GRU) network, whose current and previous hidden states are ${\mathbf{g}}_n^{(\ell)} \in \mathbb{R}^{N_{h_1} }$ and  ${\mathbf{g}}_n^{({\ell}-1)} \in \mathbb{R}^{N_{h_1} }$, respectively. ${\mathbf{W}}_2 \in \mathbb{R}^{N_u \times N_{h_1}}$ is a learnable matrix, and  ${\mathbf{b}}_2\in \mathbb{R}^{N_u}$ is a learnable vector. The updated feature vector \eqref{MLP} is then sent to the propagation module for next iterations.
\subsubsection{\textbf{Readout module}}
After $L$ rounds of the message passing between the propagation and aggregation module, a readout module is utilized to output the estimated distribution
$p_{\mathrm{GNN}}^{(t)}(x_n=s_{i}|{\mathbf{y}})$ for the $t$-layer of AMP-GNN and given by
\begin{subequations}\label{Readout}
				\begin{equation}\label{Readout1}
\tilde p^{(t)}_{ \mathrm{GNN}}(x_n=s_{i}|{\mathbf{y}})  = {\mathsf{R}} \left(  {\mathbf{u}}_n^{(L)} \right), s_{i}\in \mathcal{S},
				\end{equation}
            	\begin{equation}\label{Readout2}
p_{\mathrm{GNN}}^{(t)}(x_n=s_{i}|{\mathbf{y}})  = \frac{{{\mathsf{e}} {\mathsf{x}} {\mathsf{p}} } \left(\tilde p^{(t)}_{G\mathrm{NN}}(x_n=s_{i}|{\mathbf{y}}) \right)}  {\sum_{s_{i}\in \mathcal{S}}  {{\mathsf{e}} {\mathsf{x}} {\mathsf{p}}} \left({\tilde p}^{(t)}_{ \mathrm{GNN}}(x_n=s_{i}|{\mathbf{y}}) \right)}, s_{i}\in \mathcal{S}.
           		 \end{equation}
\end{subequations}
The readout function ${\mathsf{R}} $ consists of an MLP with two hidden layers of sizes $N_{h_1}$ and $N_{h_2}$, and ReLU activation is utilized at the output of each hidden layer. The output size of  ${\mathsf{R}} $ is the cardinality of the real-valued constellation set, i.e., $\sqrt{Q}$. Then, we compute
\begin{equation}\label{GNN_reset_index}
 {\mathbf{g}}_n^{(0)}  \leftarrow   {\mathbf{g}}_n^{(L)} \text { and }{\mathbf{u}}_n^{(0)} \leftarrow   {\mathbf{u}}_n^{(L)}, n= 1, \dots,N,
\end{equation}
for the next GNN iteration. Finally, we utilize $p_{\mathrm{GNN}}^{(t)}(x_n=s_{i}|{\mathbf{y}})$ to compute the posterior mean and variance for the AMP, which are given by
\begin{subequations}\label{pyGNN}
            \begin{equation}\label{pyGNN1}
 \hat{x}_{n}^{(t+1)}=\mathbb{E}\{x_n|p_{\mathrm{GNN}}^{(t)}\},
            \end{equation}
            \begin{equation}\label{pyGNN2}
 \hat{v}_{n}^{(t+1)}=\text{Var}\{x_n|p_{\mathrm{GNN}}^{(t)}\}.
            \end{equation}
\end{subequations}
Note that the expectation and variance are computed with respect to $p_{\mathrm{GNN}}^{(t)}$. This is the main difference between AMP and AMP-GNN as $p_{\mathrm{GNN}}^{(t)}(x_n=s_{i}|{\mathbf{y}})$ is not the Gaussian pdf in the AMP-GNN detector. After computing (\ref{pyGNN1}) and (\ref{pyGNN2}), the posterior mean $\hat{x}_{n}^{(t+1)}$ and $\hat{v}_{n}^{(t+1)}$ will be used for the next AMP-GNN iteration. Finally, the AMP-GNN is executed iteratively until terminated by a fixed number of layers.
\begin{table*}[t]
\centering
	\caption{Computational complexity (the number of multiplications) of different detectors.
}
	\label{tab:complexity}
    \begin{tabular}{@{}lcccccc@{}}
    \toprule
    \diagbox{MU-MIMO settings}{Detectors}&OAMP-Net&GNN&GEPNet&AMP&AMP-GNN&RE-MIMO\\
    \midrule
    \midrule
    $64 \times 64$ &$8.22\times10^{6}$&$1.17\times10^{6}$&$5.11\times10^{6}$&$1.78\times10^{5}$&$2.35\times10^{6}$& $4.93\times10^{8}$ \\
    \midrule
    $256 \times 256$ &$5.21\times10^{8}$&$1.27\times10^{7}$&$2.02\times10^{8}$&$2.68\times10^{6}$&$1.93\times10^{7}$& $3.22\times10^{9}$ \\
    \midrule
    $1024 \times 1024$ &$3.33\times10^{10}$&$5.56\times10^{8}$&$1.24\times10^{10}$&$4.22\times10^{7}$&$6.14\times10^{8}$& $4.41\times10^{10}$ \\
    \bottomrule
    \end{tabular}
\end{table*}

\subsection{Complexity Analysis}
We analyze the computational complexity of the AMP-GNN and compare it with existing MIMO detectors. Specifically,
the complexity of the AMP detector is  $\mathcal{O}(MN)$ owing to the matrix-vector multiplication while the complexity for GNN is  $\mathcal{O}(N_{h1}N_{h2})$ accounts for the MLP operation. Therefore, the computational complexity of the AMP-GNN is $\mathcal{O}(MN+N_{h1}N_{h2})$, dominated by the complexity of the AMP and GNN. In contrast, the complexity of the GEPNet is $\mathcal{O}(M{N}^2+N_{h1}N_{h2})$ which includes the computational complexity of the EP and GNN.

To better compare the complexity, we use the the number of multiplication as the metric and show the exact values for different MIMO settings with quadrature phase shift keying (QPSK) symbols in Table.\,\ref{tab:complexity}. The hyperparameters for GNN are set as $N_{h_1}=16$, $N_{h_2}=8$, and $N_u = 8$.  Compared with state-of-the-art DL-based MIMO detectors, such as  GEPNet and RE-MIMO, the AMP-GNN entails a much lower complexity. In particular, the ratio between the complexity of the AMP-GNN and GEPNet is dramatically reduced when the number of user increases. For example, the ratio between the complexity of the AMP-GNN and GEPNet is only $45.99\%$ when $M=N=64$  while the ratio is $4.95\%$ when $M=N=1024$.  This is because the complexity of matrix inversion  in the GEPNet will be the dominant term, which is prohibitively high when the number of antennas is large. In contrast, the AMP-GNN only involves  matrix-vector multiplications, which is a favorable feature for future ultra massive MIMO systems.
\section{Simulation Results}\label{Simulation}
In this section, we provide simulation  results of the AMP-GNN for MIMO detection and compare it with other MIMO detectors. We use the symbol error rate (SER) as the performance metric in our simulations. The signal-to-noise (SNR) of the system, defined as $\mathrm{SNR}=\frac{\mathbb{E}\|\mathbf{H}\mathbf{x}\|^{2}_{2}}{\mathbb{E}\|\mathbf{n}\|^{2}_{2}}$. To illustrate the effectiveness of our proposed AMP-GNN, we adopt several well established MIMO detectors as baselines:
\begin{itemize}
  \item \textbf{MMSE}: A classical linear receiver for MIMO detection which inverts the received signal by applying the channel-noise regularized pseudo-inverse
        of the channel matrix.
  \item \textbf{AMP}: An efficient message passing algorithm for MIMO detection given in Algorithm \ref{Algorithm:BAMP} and implemented with $10$ iterations\footnote{It was found that a  further increase in the number of iterations only offers a negligible performance gain. We set the same number of layers in other DL-based baseline methods for fair comparison.}.

  \item \textbf{OAMP-Net}: The OAMP-based model-driven DL detector developed in \cite{MIMO_Detection20DL}. Each layer requires computing a matrix pseudo-inverse and has 2 learnable parameters.

  \item \textbf{GNN}: The GNN-based MIMO detector  proposed in \cite{Scotti20GNN}.
  \item \textbf{GEPNet}: The GNN-enhanced EP detector proposed in \cite{Kosasih20DL} with $10$ layers.
  \item \textbf{RE-MIMO}: The RE-MIMO detectors  proposed in \cite{REMIMO20DL} based on the RIM with $10$ layers.

\end{itemize}
\begin{figure}
  \centering
  \includegraphics[width=3 in]{Fig1_r1}
  \caption{\small{.~~SER comparison of AMP-GNN with other MIMO detectors under $4\times4$ Rayleigh MIMO
   channels with QPSK symbols.}}\label{fig2}
\end{figure}
\subsection{Implementation Details}
In the simulation, the AMP-GNN is implemented on the PyTorch platform. The number of layers of the AMP-GNN detector  is set to $T=10$ while the number of layers of the GNN is set to $L=2$. The training data consists of a number of randomly generated pairs $(\mathbf{x},\mathbf{y})$. The data $\mathbf{x}$ is generated from QAM modulation symbols. We train the network with $100$ epochs. At each epoch, the training and validation sets contain $100,000$, and $5,000$ samples, respectively. The AMP-Net is trained using the stochastic gradient descent method and Adam optimizer. The learning rate is set to be $0.001$ and the batch size is set to $64$.
We choose the $L_{2}$ loss as the cost function, which is defined by,
\begin{equation}\label{eqloss}
  L_{2}(\mathbf{x},\hat{\mathbf{x}}^{(T)})=\|\mathbf{x}-\hat{\mathbf{x}}^{(T)}\|^{2}.
\end{equation}
\subsection{Performance Comparsion}
Fig.\,\ref{fig2} and Fig.\,\ref{fig2_2} compare the average SER of the AMP-GNN with those of the baseline detectors. As can be observed from the figuresa, the AMP-GNN outperforms almost all other MIMO detectors except for the GEPNet detector. In particular, the AMP-GNN outperforms the AMP detector in all SNRs, which demonstrates that the GNN module can improve the AMP detector significantly. Specifically, if we target an SER=$10^{-2}$, then the performance gain is approximately $3.9$ dB compared to the AMP detector. The reason for the performance improvement is that the GNN can refine the equivalent AWGN model with a more accurate distribution $p_{\mathrm{GNN}}^{(t)}(x_n=s_{i}|{\mathbf{y}})$. Furthermore, the AMP-GNN has only $0.8$ dB performance loss compared to the GEPNet detector in $4\times4$ MIMO systems  when we target at an SER=$10^{-2}$. The performance loss then reduces to $0.3$ dB for $32\times32$ MIMO systems as illustrated in Fig.\,\ref{fig2_2}. Thus, we can conclude the AMP-GNN has a comparable performance to GEPNet but with a remarkably reduced computational complexity, especially for massive and ultra-massive MIMO systems.
\begin{figure}
  \centering
  \includegraphics[width=3 in]{Fig_large}
  \caption{\small{.~~SER comparison of AMP-GNN with other MIMO detectors under $32\times32$ Rayleigh MIMO
   channels with QPSK symbols.}}\label{fig2_2}
\end{figure}
\subsection{Robustness to Dynamic Numbers of Users}
Most of the DL-based MIMO detectors are trained and tested with a fixed number of antennas. However, the number of users in practical MIMO systems may quickly change. For example, new users may access to be served by the BS. As a result, the DL-based MIMO detector should have the ability to handle a varying number of users with a single model. In Fig.\,\ref{fig3}, we train the AMP-GNN in an $8\times4$  and $8\times8$ MIMO systems and test it in an $8\times6$ MIMO system. As shown in the figure, if we target an $\mathrm{SER}=10^{-3}$,  then the AMP-GNN still has $1.7$ dB performance gain compared with the conventional AMP detector even when tested with different number of users. Furthermore, it has a similar performance as the AMP-GNN trained and tested both in the $8\times6$ MIMO system. As a result, the AMP-GNN has strong robustness to different numbers of users in the deployment stage. This is because the GNN has the permutation equivariance property which makes it robust against the dynamic changes of the number of users.
\section{Conclusions}\label{con}
We have developed a novel GNN-enhanced AMP detector for MIMO detection, named AMP-GNN, which is obtained by incorporating the GNN module into the AMP algorithm. The AMP-GNN inherits the respective superiority of the low-complexity AMP detector and efficient GNN module. Simulation results demonstrated that  AMP-GNN improves the performance of the AMP detector significantly and has comparable performance as the state-of-the-art GEPNet detector but with a reduced computational complexity. Furthermore, it is quite robust to the change of the number of users in practice.
\section*{Acknowledgment}
The authors would like to thank Prof. Chao-Kai Wen, from the National
Sun Yat-sen University, for the discussion of neural enhanced message passing
\begin{figure}
  \centering
  \includegraphics[width=3 in]{Fig2_r2}
  \caption{\small{.~~Robustness of the AMP-GNN for dynamic number of users.}}\label{fig3}
\end{figure}


\section{Introduction}
The secret sharing scheme was first proposed independently by Shamir~\cite{SS1} and Blakley~\cite{SS2} in 1979.
Its application scenario is that there is sensitive information that needs to be safely stored,
so the sensitive information is first divided into $n$ shares, and each share is assigned to a party.
When assigning shares, some specific subsets of $n$ parties are set as qualified subsets.
This sensitive information can only be recovered when the parties in the qualified subsets appear together.
Conversely, when $m$ parties cannot form a qualified subset,
they cannot recover the sensitive information, or even obtain any relevant content about the sensitive information.
Secret sharing has been applied in widespread applications, such as verifiable signature sharing~\cite{VSS},
threshold digital signatures~\cite{TC1,TC2} and electronic voting~\cite{EV99}.

The secret sharing schemes first proposed by Shamir~\cite{SS1} and Blakley~\cite{SS2} are $(t,n)$-threshold secret sharing, which means that any $t$ parties among $n$ parties are a qualified subset.
The general secret sharing schemes were introduced by Ito \emph{et al.}~\cite{GSS}.
Traditional secret sharing schemes assume that the number of parties $n$ is known in advance
or that the upper bound of $n$ is estimated.
However, this assumption comes at a cost:
when $n$ is estimated to be too small, secret sharing needs to be re-made;
when $n$ is estimated to be too large, it may cause waste.

Recently, the evolving secret sharing scheme was introduced by Komargodski \emph{et al.}~\cite{ESS0,ESS1}.
This new variant of secret sharing does not require prior knowledge of the upper bound of $n$
and $n$ may be infinitely countable.
Komargodski \emph{et al.} found a one-to-one correspondence between the evolving $2$-threshold secret sharing scheme and  prefix coding of integers.
In 2018, D'Arco \emph{et al.}~\cite{ESS2} reinterpreted the equivalence between the evolving $2$-threshold secret sharing scheme and prefix coding of integers with a new perspective.
In 2020, Okamura and Koga~\cite{ESS3} extended the shared secret from $1$-bit to any $l$-bit based on the work of D'Arco \emph{et al.}, and by combining Shamir's secret sharing scheme,
proposed an evolving 2-threshold secret sharing scheme using $D$-ary prefix codes.
In addition, there are studies on evolving secret sharing schemes for dynamic thresholds and robustness~\cite{RESS},
probabilistic evolving secret sharing~\cite{PESS} and evolving ramp secret sharing~\cite{ERSS1,ERSS2}.

Although the evolving 2-threshold secret sharing scheme can be completely characterized by the prefix coding of integers,
we do not know which prefix code should be chosen to construct the secret sharing scheme better.
We need a metric for judging which evolving 2-threshold secret sharing scheme constructed by the prefix coding of integers works better.

In this paper, we investigate which prefix coding of integers should be chosen to construct
the evolving 2-threshold secret sharing scheme better.
The metric for evolving 2-threshold secret sharing proposed in this paper draws on
the metric minimum expansion factor $K_{\sigma}^{*}$~\cite{yan,yan2} for universal coding of integers~\cite{Elias75}.
The contributions of this paper are enumerated as follows.
\begin{enumerate}
\item The reachable lower bound of the sum of share sizes for $(2,n)$-threshold secret sharing schemes is proved.
\item A new metric for evolving $2$-threshold secret sharing schemes is proposed.
\item Under the new metric, evolving $2$-threshold secret sharing schemes whose effect is close to the optimal scheme are constructed.
\end{enumerate}

The paper is structured as follows.
Section \ref{pre} introduces some background knowledge.
Section \ref{bound} proves the reachable lower bound of the sum of share sizes for $(2,n)$-threshold secret sharing schemes.
Section \ref{metric} proposes a new metric for evolving $2$-threshold secret sharing schemes.
Section \ref{sec_new} constructs evolving $2$-threshold secret sharing schemes whose effect is close to the optimal scheme under the new metric.
Section \ref{sec_con} concludes this work.

\section{Preliminaries}\label{pre}
We establish some necessary notations.
Let $\mathbb{N}$ be the set of positive integers.
Let $\mathbb{B}:=\{0,1\}$, and let $\mathbb{B}^{*}$ be a set consisting of all finite-length binary strings.
$\#S$ denotes the cardinality of the set $S$.
$|\alpha|$ denotes the length of string $\alpha$.
For a positive integer $n$, let $[n]:=\{1,2,\dots,n\}$.
\subsection{Secret Sharing Scheme}
Let $\mathcal{P}=\{P_{1},P_{2},\dots,P_{n}\}$ denote the set of participants,
and let $2^\mathcal{P}$ be the power set of the set $\mathcal{P}$.
$\mathcal{M}\subseteq 2^\mathcal{P}$ is called \emph{monotone}
if for any $S_1\in \mathcal{M}$, and $S_1\subseteq S_2$ it holds that $S_2\in \mathcal{M}$.
Before defining secret sharing scheme, we first define the access structure as follows.
\begin{definition} \label{def1}
$\mathcal{M}\subseteq 2^\mathcal{P}$ is said to be an access structure if $\mathcal{M}$ is non-empty and monotone.
Elements in $\mathcal{M}$ are called qualified, and elements not in $\mathcal{M}$ are called unqualified.
\end{definition}
\begin{definition}\label{def2}
Let $t$ and $n$ both be positive integers, and $1\leq t\leq n$.
The $(t,n)$-threshold access structure $\mathcal{M}$ refers to the set containing only all elements in $2^\mathcal{P}$ of size at least $t$, i.e.
\[
\mathcal{M}=\{ A\in 2^{\mathcal{P}} \,|\,  \#A \geq t \}.
\]
\end{definition}
The definition of secret sharing scheme is given based on the access structure.
\begin{definition} \label{def3}
A secret sharing scheme	$\Sigma$ for an access structure $\mathcal{M}$ consists of a pair of probabilistic algorithms
$(\mathcal{S},\mathcal{R})$.
The sharing algorithm $\mathcal{S}$ generates $n$ shares $sh_{P_1}^{(s)},sh_{P_2}^{(s)},\dots,sh_{P_n}^{(s)}$
according to the secret $s\in S$ and the number of participants $n$.
The recovery algorithm $\mathcal{R}$ outputs a string according to the shares of the subset $A\in2^\mathcal{P}$.
The algorithm is required to satisfy:
\begin{itemize}
\item \textbf{Correctness:} For every qualified set $A\in\mathcal{M}$ and any secret $s\in S$, the recovery algorithm $\mathcal{R}$ can recover the secret $s$ with probability $1$, i.e.
	\[
		Pr[\mathcal{R}(A,\{sh_{j}^{(s)}\}_{j\in A})=s]=1.
	\]
\item  \textbf{Secrecy:} Each unqualified set $A\notin \mathcal{M}$ does not get any information about the secret $s$;
that is, for any two different secrets $s_1,s_2\in S$ and each unqualified set $A\notin \mathcal{M}$, it holds that
the distributions $(\{sh_{j}^{(s_1)} \}_{j\in A})$ and $(\{sh_{j}^{(s_2)}\}_{j\in A})$ are the same.
\end{itemize}
\end{definition}
From Definition~\ref{def3},
it can be reasonably associated that $(t,n)$-threshold secret sharing refers to the secret sharing scheme of $(t,n)$-threshold access structure.
For a secret sharing scheme, it is hoped to generate the sum of share sizes $\sum_{i=1}^{n}|sh_{P_i}^{(s)}|$ is as small as possible, which can make the amount of communication as small as possible.

The following introduces two important conclusions that need to be used.
\begin{theorem}~\cite{UR,ESS4} \label{thm2}
	Suppose that $\Sigma$ is $(t,n)$-thresholded secret sharing scheme for $1$-bit secret, and the $j$-th share size is $m_{j}$ bits, where $2\leq t\leq n$, $j\in[n]$ and $m_j\in \mathbb{N}$. Then, the sum of share sizes
	\[
	\sum_{j=1}^{n}m_{j} \geq n\log_{2}(n-t+2).
	\]
	In particular, when $t=2$, the sum of share sizes for $(2,n)$-threshold secret sharing schemes
	$$\sum_{j=1}^{n}m_{j}\geq n\log_{2}n.$$
\end{theorem}
\begin{lemma}~\cite{UR,ESS4,ESS1}\label{lemma1}
	Suppose that $\Sigma$ is $(2,n)$-thresholded secret sharing scheme for $1$-bit secret, and the $j$-th share size is $m_{j}$ bits, where $j\in[n]$ and $m_j\in \mathbb{N}$. Then,
	\[
	\sum_{j=1}^{n}\frac{1}{2^{m_{j}}}\leq 1 .
	\]
\end{lemma}
\subsection{Evolving Secret Sharing Scheme}
Because the number of participants $n$ is uncertain
and the upper bound of $n$ cannot be estimated in real scenarios,
a class of secret sharing schemes needs to be defined so that $n$ can be infinitely countable.
Naturally, in this scenario, the parties participating in secret sharing will not be present at the same time.
We assume that at the $t$-th moment, the $t$-th person arrives at the scene and asks for the distribution of subsequent shares, the previously distributed shares do not need to be changed, which can most effectively reduce the amount of communication.
Let $\mathcal{PN}=\{P_{1},P_{2},\dots,P_{n},\dots\}$ denote the set of participants.
Definitions~\ref{def1} and~\ref{def2} are naturally extended to the following definitions.
\begin{definition} ~\cite{ESS1}
Suppose that $\mathcal{M}\subseteq 2^{PN}$ is monotone, and for each time $t\in\mathbb{N}$,
$\mathcal{M}_{t}:=\mathcal{M}\cap \{P_{1},P_{2},\dots,P_{t}\}$ is an access structure, then $\mathcal{M}$ is said to be an evolving access structure.
\end{definition}
\begin{definition}~\cite{ESS1}
Let $t$ be a positive integer.
The evolving $t$-threshold access structure $\mathcal{M}$ refers to the set consisting only of all elements in $2^{\mathcal{PN}}$ of size at least $t$, i.e.
	\[
	\mathcal{M}=\{ A\in 2^{\mathcal{PN}}  \,| \, \#A \geq t \}.
	\]
\end{definition}
For simplicity, we use $(t,\infty)$-threshold to represent evolving $t$-threshold.
Now, the formal definition of the evolving secret sharing scheme is as follows.
\begin{definition} \label{def6}~\cite{ESS0,ESS1}
Let $S$ denote a domain of secrets, where $\#S\geq 2$.
Let $\mathcal{M}$ denote an evolving access structure.
An evolving secret sharing scheme $\Sigma$ for $S$ and $\mathcal{M}$ consists of a pair of probabilistic algorithms $(\mathcal{S},\mathcal{R})$.
The sharing algorithm $\mathcal{S}$ and the recovery algorithm $\mathcal{R}$ are required to satisfy:
\begin{itemize}
 \item[1)] At time $t\in \mathbb{N}$, the sharing algorithm $\mathcal{S}$ generates share $sh_{P_t}^{(s)}$ according to the secret $s\in S$ and shares $sh_{P_1}^{(s)},sh_{P_2}^{(s)},\dots,sh_{P_{t-1}}^{(s)}$, i.e.
	\[
		\mathcal{S}(s,\{sh_{P_i}^{(s)}\}_{i\in[t-1]})=sh_{P_t}^{(s)}.
	\]
\item[2)] \textbf{Correctness:} For each time $t\in \mathbb{N}$, every qualified set $A\in \mathcal{M}_t$ and any secret $s\in S$, the recovery algorithm $\mathcal{R}$ can recover the secret $s$ with probability $1$, i.e.
	\[
		Pr[\mathcal{R}(A,\{sh_{i}^{(s)}\}_{i\in A})=s]=1 .
	\]
\item[3)] \textbf{Secrecy:} For each time $t\in \mathbb{N}$, each unqualified set $A\notin \mathcal{M}_t$ does not get any information about the secret $s$;
that is, for each time $t$, any two different secrets $s_1,s_2\in S$ and each unqualified set $A\notin \mathcal{M}_t$, it holds that the distributions $(\{sh_{j}^{(s_1)} \}_{j\in A})$ and $(\{sh_{j}^{(s_2)}\}_{j\in A})$ are the same.
\end{itemize}
\end{definition}
Komargodski \emph{et al.}~\cite{ESS0,ESS1} found the equivalence between the $(2,\infty)$-thresholded secret sharing scheme
and prefix coding of integers.
This interesting conclusion is shown below.
\begin{theorem}~\cite{ESS0,ESS1}\label{thm1}
Let $\sigma: \mathbb{N}\rightarrow \mathbb{B}^{*}$ be a prefix coding of integers.
The length of its $t$-th codeword is $L_\sigma(t)$, where $t\in\mathbb{N}$.
Such an integer code exists if and only if there exists a $(2,\infty)$-threshold secret sharing scheme $\Sigma$ for $1$-bit secret, and the $t$-th share size is $L_\sigma(t)$ bits.
\end{theorem}
An interesting and essential understanding of Theorem~\ref{thm1} can be found in~\cite{ESS2}.

\subsection{The Metric Minimum Expansion Factor $K_{\mathcal{C}}^{*}$ for Universal Coding of Integers}
Universal coding of integers is a class of binary prefix code,
such that the ratio of the expected codeword length to $\max\{1,H(P)\}$
is within a constant for any decreasing probability distribution $P$ of $\mathbb{N}$ (i.e., $\sum_{n=1}^{\infty}P(n)=1$, and $P(m)\geq P(m+1)\geq 0$ for all $m\in \mathbb{N}$), where $H(P):=-\sum_{n=1}^{\infty}P(n)\log_{2}P(n)$ is the entropy of $P$.
The formal definition of universal coding of integers is as follows.
\begin{definition} ~\cite{Elias75,yan}
Let $\sigma: \mathbb{N}\rightarrow \mathbb{B}^{*}$ be a binary prefix coding of integers.
Let $L_{\sigma}(\cdot)$ denote the length function of $\sigma$ so that $L_{\sigma}(m)=|\sigma(m)|$ for all $m\in \mathbb{N}$.
$\sigma$ is called universal if there exists a constant $K_{\sigma}$ independent of $P$, such that
\begin{equation}\label{eq2}
	\frac{E_{P}(L_{\sigma})}{\max\{1,H(P)\}}\leq K_{\sigma},
\end{equation}
for any decreasing probability distribution $P$ with finite entropy, where $$E_{P}(L_{\sigma}):=\sum_{n=1}^{\infty}P(n)L_{\sigma}(n)$$
denotes the expected codeword length for $\sigma$.
Then $K_{\sigma}$ is called the expansion factor.
Let $K_{\sigma}^{*}:=\inf\{K_{\sigma}\}$ be the infimum of the set of expansion factors.
$K_{\sigma}^{*}$ is called the minimum expansion factor.
\end{definition}
The minimum expansion factor $K_{\sigma}^{*}$ is the smallest of the expansion factors.
For any universal coding of integers, its minimum expansion factor $K_{\sigma}^{*}$ is unique.
The minimum expansion factor $K_{\sigma}^{*}$, as a metric, evaluate the compression effect of universal coding of integers.
Therefore, universal coding of integers $\sigma$ is called \emph{optimal} if $\sigma$ achieves the smallest $K_{\sigma}^{*}$.

Finally, we introduce two classes of universal coding of integers, $\iota$ code~\cite{yan2} and $\eta$ code~\cite{yan}, which can achieve smaller expansion factors.
In particular, $\iota$ code is currently the only universal coding of integers that can achieve $K_{\iota}=2.5$.
The two codes are briefly introduced as follows.

The unary code $\alpha$ of the non-negative integer $m$ is constructed as $m$ bits of $0$ followed by a single $1$.
Let $\beta(m)$ denote the standard binary representation of $m\in\mathbb{N}$,
and let $[\beta(m)]$ denote the removal of the most significant bit $1$ of $\beta(m)$.
For example, $\alpha(2)=001$, $\beta(10)=1010$ and $[\beta(10)]=010$.
Note that $[\beta(1)]$ is a null string.
We define $\beta(0)$ as a null string, and the length of the null string is $0$.
\begin{enumerate}
	\item The code $\iota: \mathbb{N}\rightarrow \mathbb{B}^{*}$ can be expressed as
\begin{equation*}
	\iota(m)=\left\{\begin{array}{lll}
		 1,                                                         &\text{if } m=1\text{,}   \\
		\alpha(\frac{|\beta(m)|}{2})0[\beta(m)],                     &\text{if } |\beta(m)| \text{ is even,} \\
		\alpha(\frac{|\beta(m)|-1}{2})\beta(m),                &\text{otherwise,}   \\
	\end{array}\right.
\end{equation*}
	for all $m\in \mathbb{N}$. The codeword length is given by
	\begin{equation*}
	\begin{aligned}
		|\iota(m)|&=1+\lfloor \frac{|\beta(m)|}{2} \rfloor+|\beta(m)|    \\
		&=2+\lfloor \frac{1+\lfloor\log_2(m)\rfloor}{2} \rfloor+\lfloor\log_2(m)\rfloor,         \\
	\end{aligned}
\end{equation*}
for $2\leq m\in \mathbb{N}$ and $|\eta(1)|=1$.
	\item The code $\eta: \mathbb{N}\rightarrow \mathbb{B}^{*}$ can be expressed as
\begin{equation*}
	\eta(m)=\left\{\begin{array}{ll}
		\alpha(\frac{|\beta(m-1)|}{2})\beta(m-1),                     &\text{if } |\beta(m-1)| \text{ is even,} \\
		\alpha(\frac{1+|\beta(m-1)|}{2})0[\beta(m-1)],                &\text{otherwise,}   \\
	\end{array}\right.
\end{equation*}
	for all $m\in \mathbb{N}$. The codeword length is given by
	\begin{equation*}
		\begin{aligned}
			|\eta(m)|&=1+\lfloor \frac{1+|\beta(m-1)|}{2} \rfloor+|\beta(m-1)|    \\
			&=3+\lfloor \frac{\lfloor\log_2(m-1)\rfloor}{2} \rfloor+\lfloor\log_2(m-1)\rfloor,
		\end{aligned}
	\end{equation*}
	for $2\leq m\in \mathbb{N}$ and $|\eta(1)|=1$.
\end{enumerate}
\section{The Reachable Lower Bound of the Sum of Share Sizes for $(2,n)$-Threshold Secret Sharing Schemes}\label{bound}
In this section, the reachable lower bound of the sum of share sizes for $(2,n)$-threshold secret sharing schemes is proved.
Let $\min[sum(2,n)]$ denote the minimum sum of share sizes in all $(2,n)$-threshold secret sharing schemes.
The \emph{optimal $(2,n)$-threshold secret sharing scheme} is defined as the secret sharing scheme
with the sum of share sizes $\min[sum(2,n)]$.

In the early 1990s, Kilian and Nisan first proposed and proved Theorem~\ref{thm2} in an email,
but it was not officially published.
This unpublished result has been mentioned in numerous papers
and the proof by Kilian and Nisan was first published publicly in~\cite{ESS4}.
Theorem~\ref{thm2} shows that the sum of share sizes for $(2,n)$-threshold secret sharing schemes
is greater than or equal to $n\log_{2}n$, i.e.
$$\min[sum(2,n)]\geq n\log_{2}n.$$

This section gives a tighter bound than the lower bound $n\log_{2}n$ and this bound is achievable;
that is, this section gives the exact expression for $\min[sum(2,n)]$.
First, a correspondence similar to Theorem~\ref{thm1} is given.
\begin{theorem}\label{thm3}
Let $\sigma: [n]\rightarrow \mathbb{B}^{*}$ be a prefix code.
The length of its $t$-th codeword is $L_\sigma(t)$, where $t\in[n]$.
Such a prefix code exists if and only if there exists a $(2,n)$-threshold secret sharing scheme $\Sigma$ for $1$-bit secret, and the $t$-th share size is $L_\sigma(t)$ bits.
\end{theorem}
\begin{proof}
\begin{itemize}
\item[(1)] \textbf{Sufficient:}
Suppose that there exists a $(2,n)$-threshold secret sharing scheme $\Sigma$ for $1$-bit secret, and the $t$-th share size is $L_\sigma(t)$ bits.
From Lemma~\ref{lemma1}, we obtain
\[
\sum_{j=1}^{n}\frac{1}{2^{L_\sigma(j)}}\leq 1 .
\]
Due to the Kraft's inequality~\cite{kraft}, we know that there exists a prefix code with codeword lengths $L_\sigma(1),L_\sigma(2),\dots,L_\sigma(n)$.
\item[(2)]\textbf{Necessary:}
Suppose that there is a prefix code with codeword lengths $L_\sigma(1),L_\sigma(2),\dots,L_\sigma(n)$.
Next, we construct a $(2,n)$-threshold secret sharing scheme $\Sigma$ for $1$-bit secret.
Let $s\in\mathbb{B}$ be the secret, and let $M$ denote the maximum value among $L_\sigma(1),L_\sigma(2),\dots,L_\sigma(n)$.
The dealer randomly generates a binary string $Q$ of length $M$.
Let $Q|_{t}$ denote the first $L_\sigma(t)$ bits of the string $Q$.
If $s=0$, then the $t$-th share is $sh(t)=\sigma(t)\oplus Q|_{t}$;
If $s=1$, then the $t$-th share is $sh(t)= Q|_{t}$.
The $t$-th share size is $L_\sigma(t)$ bits.

In the recovery secret stage, let the two different shares be $sh(t_{1})$ and $sh(t_{2})$.
Without loss of generality assume that $|sh(t_1)|\leq|sh(t_2)|$.
If $sh(t_{1})$ is a prefix of $sh(t_{2})$, the output is $1$; otherwise, the output is $0$.
\begin{itemize}
\item[(2.1)]\textbf{Correctness:} If $s=0$, then $sh(t_1)=\sigma(t_1)\oplus Q|_{t_1}$ and
$sh(t_2)=\sigma(t_2)\oplus Q|_{t_2}$. Since $Q|_{t_1}$ is a prefix of $Q|_{t_2}$ and $\sigma(t_1)$ is not a prefix of $\sigma(t_2)$, then $\Pi(t_1)$ is not a prefix of $\Pi(t_2)$.
Therefore, the output is $0$ is correct.
If $s=1$, then $sh(t_1)=Q|_{t_1}$ and $sh(t_2)=Q|_{t_2}$.
Since $Q|_{t_1}$ is a prefix of $Q|_{t_2}$, the output is $1$ is correct.
\item[(2.2)]\textbf{Secrecy:}
Because $Q|_{t}$ is uniformly distributed on $\mathbb{B}^{L_\sigma(t)}$, whether $s=0$ or $s=1$,
there is a share $sh(t)$ uniformly distributed on $\mathbb{B}^{L_\sigma(t)}$.
Therefore, no single party can get any information about the secret $s$.
\end{itemize}
\end{itemize}
\end{proof}

Next, the main theorem of this section is given.
\begin{theorem} \label{thm4}
Let $n$ be an integer greater than $1$, then
\[
\min[sum(2,n)]=nm+2l,
\]
where $m:=\lfloor \log_{2}n \rfloor$ and $l:=n-2^{m}$.
\end{theorem}
\begin{proof}
Suppose that $\Sigma$ is a $(2,n)$-threshold secret sharing scheme for $1$-bit secret, and the $j$-th share size is $m_j$ bits, where $j\in[n]$.
We need to find a scheme $\Sigma$ that minimizes the sum $\sum_{j=1}^{n}m_{j}$;
that is, find the minimum value $\min[sum(2,n)]$ of $\sum_{j=1}^{n}m_{j}$.

Due to Theorem~\ref{thm3}, $\Sigma$ corresponds to a prefix code $\sigma: [n]\rightarrow \mathbb{B}^{*}$,
and the length of its $j$-th codeword is $m_j$, where $j\in[n]$.
To make $\sum_{j=1}^{n}m_{j}$ minimum is equivalent to minimizing the
expected codeword length $L=\sum_{j=1}^{n}P_{6}(j)m_{j} =\frac{1}{n}\sum_{j=1}^{n}m_{j}$
of the prefix code $\sigma$ with probability distribution
\[
P=\left(P(1)=P(2)=\dots=P(n)=\frac{1}{n}\right).
\]
Because given a probability distribution, Huffman code is the prefix code with the smallest expected codeword length.
Therefore, it is only necessary to calculate the expected codeword length
when encoding with Huffman code in the case of the probability distribution $P$.
From $P$ is a uniform distribution and the encoding rule of Huffman code,
it can be known that the code tree obtained by encoding is a full binary tree
and the layers of leaf nodes differ by at most $1$, so the lengths of all codewords differ by at most $1$.
Then, there are $2^{m}-l$ codewords with codeword length $m$ and $2l$ codewords with codeword length of $m+1$.
Therefore, the minimum value of $\sum_{j=1}^{n}m_{j}$ is
\begin{equation*}
	\begin{aligned}
		\min[sum(2,n)]&= m(2^{m}-l)+2l(m+1)    \\
		&= m2^m+ml+2l    \\
		&= nm+2l.
	\end{aligned}
\end{equation*}
\end{proof}
From Theorem~\ref{thm4}, $nm+2l$ is the reachable lower bound of the sum of share sizes
for $(2,n)$-threshold secret sharing scheme.
Since $n\log_{2}n$ is the lower bound, there must be $nm+2l \geq  n\log_{2}n$.
To show that our results are novel,
we compare $nm+2l$ and $n\log_{2}n$ only from a purely mathematical point of view.
\begin{lemma} \label{lemma2}
For any $n=2^{m}+l\in \mathbb{N}$, where $m=\lfloor \log_{2}n \rfloor$. Then
\begin{equation} \label{eq1}
	nm+2l \geq n\log_{2}n .
\end{equation}
\end{lemma}
\begin{proof}
Let $x:=\log_{2}n$ and $y:=x-\lfloor x \rfloor$, then $0\leq y <1$.
We obtain
\begin{equation*}
	\begin{aligned}
		nm+2l \geq n\log_{2}n 	\iff & n\lfloor \log_{2}n \rfloor +2n-2 \cdot 2^{\lfloor \log_{2}n \rfloor} \geq n\log_{2}n    \\
		\iff & n(2+\lfloor \log_{2}n \rfloor-\log_{2}n ) \geq 2 \cdot 2^{\lfloor \log_{2}n \rfloor}   \\
		\iff & 2^{x}(2+\lfloor x \rfloor-x) \geq 2 \cdot 2^{\lfloor x \rfloor}       \\
		\iff & 2^{y}(2-y) \geq 2 .  \\
	\end{aligned}
\end{equation*}
Therefore, it is equivalent to proving that $2^{y}(2-y)\geq 2$ for $y\in [0,1)$.
Let $f(y):=2^{y}(2-y)$.
By calculating the derivative, we know that $f(y)$ is strictly monotonically increasing over the interval $[0,y_{0})$
and strictly monotonically decreasing over the interval $[y_{0},1)$, where $y_{0}=2-\dfrac{1}{\ln2}$.
Therefore, for $y\in [0,1)$, we have
\[
f(y)\geq \min\{f(0),f(1)\}=2.
\]
\end{proof}

From the proof process of Lemma~\ref{lemma2}, we know that when $y=0$, inequality~\eqref{eq1} is equal;
that is, inequality~\eqref{eq1} is equal when $n$ is a power of 2.
Due to the monotonicity of the function $f(y)$,
we reasonably guess that at the midpoint $2^m+2^{m-1}$ of the two powers of 2,
the difference between the two sides of inequality~\eqref{eq1} is large.
Thus, Table~\ref{tab1} lists some values comparing $nm+2l$ and $n\log_{2}n$.
Table~\ref{tab1} confirms the equivalence of inequality~\eqref{eq1} from the side; that is, when $n=2^m$,
there is $nm+2l=m\cdot2^m=n\log_{2}n$.
In addition, it can be found that the difference at $2^m+2^{m-1}$ is larger when $m$ is larger, interestingly, the latter difference is $2$ times the previous difference.
This finding is verified below.
\begin{table}[t]
	\caption{Comparison of some values of $nm+2l$ and $n\log_{2}n$}\label{tab1}
	\centering
	\begin{threeparttable}
	\begin{tabular}{|c|c|c|c||c|c|c|c|}
		\hline
		$n$  &   $nm+2l$   &   $n\log_{2}n$  & difference  &  $n$  &   $nm+2l$   &   $n\log_{2}n$  & difference  \\
		\hline
		$2$   &    2  &   2       &  0     &  	$3$   &     5    &     4.75      &  0.25      \\
		$4$   &    8  &   8      &  0   &   	$6$   &     16     &   15.51     &    0.49  \\
		$8$   &     24  &   24   &  0   &     $12$   &      44      &   43.02      &   0.98  \\
		$16$   &    64  &   64   &  0  &   	  $24$   &      112      &   110.04    &   1.96    \\
		$32$   &   160  &   160  &  0   &  	  $48$   &      272     &   268.08   &   3.92   \\
		$64$   &   384  &   384   &  0   &     $96$   &     640 &    632.16  &  7.84  \\
		$2^7$   &  896  &   896   &  0   &    	$2^7+2^6$   &     1472  & 1456.31   & 15.69     \\
		$2^8$   &  2048  &  2048  &  0  &     	$2^8+2^7$   &  3328   &   3296.63 &   31.37 \\
		$2^9$   &  4608  &  4608  &  0  &      	$2^9+2^8$   &   7424  &   7361.25 &   62.75    \\
		$2^{10}$  &  10240  & 10240  &  0  &    $2^{10}+2^9$  &   16384  &   16258.50  &  125.50  \\
		$2^{11}$  &  22528  & 22528  &  0  &    $2^{11}+2^{10}$  &   35840  &  35589.00  & 251.00   \\
		$2^{12}$  &  49152  & 49152  &  0 &    	$2^{12}+2^{11}$  &   77824 &   77322.01  &  501.99   \\
		$2^{13}$  &  106496 &   106496   &  0 & $2^{13}+2^{12}$  &   167936  &  166932.02  & 1003.98 \\
		$2^{14}$  &  229376 &   229376  &  0 &  $2^{14}+2^{13}$  &  360448  &  358440.04 &   2007.96  \\
		$2^{15}$  &  491520 &   491520  &  0 &  $2^{15}+2^{14}$  &   770048  &  766032.08  &  4015.92    \\
		$2^{16}$  &  1048576 &  1048576 &  0 &	$2^{16}+2^{15}$  &   1638400  & 1630368.15   & 8031.85  \\
		\hline
	\end{tabular}
\begin{tablenotes}
\footnotesize
\item  Note: After rounding $n\log_{2}n$, retain two decimal places.
\end{tablenotes}
\end{threeparttable}
\end{table}

Let $n_1:=2^m+2^{m-1}$ and $n_2:=2^{m-1}+2^{m-2}$.
Let $d(n):=nm+2l-n\log_{2}n$, we obtain
\begin{equation*}
	\begin{aligned}
		d(n_1)& =(2^m+2^{m-1})m+2^{m}-(2^m+2^{m-1})\log_{2}(2^m+2^{m-1})  \\
		&= (2^m+2^{m-1})(m-1)+2^{m}-(2^m+2^{m-1})\log_{2}(2^{m-1}+2^{m-2})         \\
		&= 2\Big[(2^{m-1}+2^{m-2})(m-1)+2^{m-1}-(2^{m-1}+2^{m-2})\log_{2}(2^{m-1}+2^{m-2}) \Big] \\
		&= 2d(n_2). \\
	\end{aligned}
\end{equation*}
This shows that when $m$ tends to infinity, the difference at $2^m+2^{m-1}$ tends to infinity.
Therefore, the reachable lower bound $nm+2l$ proved in this paper is not only a new result, but also very meaningful.

\section{A New Metric for $(2,\infty)$-Threshold Secret Sharing Schemes}\label{metric}
Theorem~\ref{thm1} shows that there is a one-to-one correspondence between the $(2,\infty)$-thresholded secret sharing scheme
and the prefix coding of integers.
For simplicity, integer codes mentioned in this paper refer to the prefix coding of integers.

The question that this section will aim to answer is which integer codes should be chosen to construct secret sharing better;
that is, this section strives to formulate a metric
under which one can judge which of the two integer codes is more suitable for constructing $(2,\infty)$-thresholded secret sharing schemes.

In traditional secret sharing, since shares are distributed at one time, the metric to measure is the sum of share sizes, and it is hoped that the smaller the sum, the better.
In evolving secret sharing, the specific number of parties participating in secret sharing is not known, and even the number of parties may be infinitely countable.
Therefore, it is impossible to calculate the sum of share sizes by distributing the shares all at one time.

The simplest idea of whether it is possible to construct a $(2,\infty)$-threshold secret sharing scheme so that the length of share generated at any $t$ time is the smallest. Unfortunately, such a scheme does not exist.
From Theorem~\ref{thm1}, for any $(2,\infty)$-thresholded secret sharing scheme $\Sigma$,
there exists an integer code $\sigma$, such that the $t$-th codeword length $L_\sigma(t)$ is exactly
the size of share distributed by the scheme $\Sigma$ at the $t$-th moment.
From the theory of prefix codes, it is impossible to have an integer code $\sigma$,
such that for any integer code $\psi$ and any positive integer $t$,
there is $L_\sigma(t)\leq L_\psi(t)$.
An integer code is called \emph{complete} if the integer code makes Kraft's inequality~\cite{kraft} equal.
When two different complete integer codes $\psi$ and $\sigma$ compare the codeword lengths,
if $t$ is sufficiently large, both have $L_\sigma(t)\leq L_\psi(t)$, then there must be a smaller positive integer $t_0$ such that $L_\sigma(t_0) > L_\psi(t_0)$; in other words,
the codeword length advantage of the $\sigma$ at larger integers is at the expense of codeword length at smaller integers.
So this simple idea does not work.

The second common idea only considers sufficiently large moments $t$, if there is a $(2,\infty)$-threshold secret sharing scheme such that the share size $L(t)$ generated at sufficiently large moments $t$ are all the smallest, we think this scheme is the best.
It is known that the codeword length advantage at larger integers is at the expense of codeword length at smaller integers. However, in evolving secret sharing, the share size $L(t)$ of the larger moment $t$ is obviously not as important as the share size of the smaller moment due to the unknown number of parties. Therefore, this idea is unreasonable, and we need to find more reasonable and feasible metrics.

In fact, evolving secret sharing has one thing in common with universal coding of integers: they both face unknowns.
Evolving secret sharing has no prior knowledge of the number of parties, and universal coding of integers has no prior knowledge of probability distributions.
Therefore, it is hoped to propose a metric similar to the metric minimum expansion factor $K_{\sigma}^{*}$ to evaluate the overall effect of $(2,\infty)$-threshold secret sharing schemes.
The new metric is defined as follows.
\begin{definition}
Let $\Sigma$ be a $(2,\infty)$-threshold secret sharing scheme, which corresponds to the integer code $\sigma$,
and the size of the share distributed at $t$-th moment is $L_\sigma(t)$ bits.
The global metric $K_{\Sigma}$ of the scheme $\Sigma$ is defined as follows:
	\begin{equation}\label{eq3}
		\begin{aligned}
		K_{\Sigma}:=& \sup \left\{\dfrac{\sum_{t=1}^{n}L_\sigma(t)}{\min[sum(2,n)]}\,\Bigg|\, \forall n\in \mathbb{N}^{+},n\neq 1 \right\}     \\
		= &\sup \left\{\dfrac{\sum_{t=1}^{n}L_\sigma(t)}{	nm+2l }\,\Bigg|\, \forall n\in \mathbb{N}^{+},n\neq 1 \right\},
		\end{aligned}
	\end{equation}
where $m:=\lfloor \log_{2}n \rfloor$ and $l:=n-2^m$.
\end{definition}

The meaning of the global metric $K_{\Sigma}$ is that no matter how many parties participate in secret sharing
when any fixed number of parties is $n_0$,
the sum of the share sizes for the $(2,\infty)$-threshold secret sharing scheme $\Sigma$ is less than or equal to
$K_{\Sigma}$ times of the sum of the share sizes for the optimal $(2,n_0)$-threshold secret sharing scheme.

Finally, the optimal $(2,\infty)$-threshold secret sharing scheme and the optimal integer code
for $(2,\infty)$-threshold secret sharing schemes are defined below.

\begin{definition}
The $(2,\infty)$-threshold secret sharing scheme with the smallest global metric $K_{\Sigma}$ is called the optimal $(2,\infty)$-threshold secret sharing scheme.
The integer code corresponding to the optimal $(2,\infty)$-threshold secret sharing scheme is called the optimal integer code
for $(2,\infty)$-threshold secret sharing schemes.
\end{definition}

\section{The Value Range of $K_{\Sigma}$ for the Optimal $(2,\infty)$-Threshold Secret Sharing Scheme}\label{sec_new}
In this section, we study the value range of the global metric $K_{\Sigma}$ for the optimal $(2,\infty)$-threshold secret sharing scheme.

First, the lower bound of the global metric $K_{\Sigma}$ is given.
For simplicity, let
\[
\mathcal{L}(n,\sigma):=\dfrac{\sum_{t=1}^{n}L_\sigma(t)}{nm+2l}.
\]
Consider the case where the number of parties $n=2$.
Due to $L_{\sigma}(1)\geq 1$ and $L_{\sigma}(2)\geq 2$ for any integer code $\sigma$, we obtain
\[
\mathcal{L}(2,\sigma)=\dfrac{\sum_{t=1}^{2}L_\sigma(t)}{ 2\times1+2\times0 } \geq \dfrac{3}{2}.
\]
Therefore, the global metric $K_{\Sigma}$ satisfies $K_{\Sigma}\geq 1.5$.

Next, we will construct schemes $\Sigma$ in the following two subsections so that its the global metric $K_{\Sigma}$ is close to the lower bound $1.5$.

\subsection{Panning Code}
In this subsection, we construct $(2,\infty)$-threshold secret sharing schemes
with small $K_{\Sigma}$ using known universal coding of integers.

The length of the second codeword of the currently constructed universal coding of integers
$\sigma$ is strictly greater than $2$; that is, $L_{\sigma}(2)\geq 3$, then
\[
\mathcal{L}(2,\sigma)=\dfrac{\sum_{t=1}^{2}L_\sigma(t)}{2} \geq 2.
\]
At this time, the global metric $K_{\Sigma}$ is far from the lower bound $1.5$.
Therefore, we consider a panning code $\sigma+$ constructed from a known integer code $\sigma$.
The panning code $\sigma+: \mathbb{N}^{+}\rightarrow \mathbb{B}^{*}$ is constructed as follows.
\begin{equation*}
	\sigma+(m):=\left\{\begin{array}{ll}
		1,                               &\text{if } \, m=1\text{,}\\
		0\sigma(m-1),                    &\text{otherwise,}   \\
	\end{array}\right.
\end{equation*}
for all $m\in \mathbb{N}$.
If the length of the first codeword of integer code $\sigma$ is $1$,
then the length of the first codeword of $\sigma+$ is $1$ and the length of the second codeword of $\sigma+$ is $2$.

Before considering which integer code to use to construct the $(2,\infty)$-threshold secret sharing scheme,
we first prove the following lemma.
\begin{lemma} \label{lem3}
Let the integer code $\sigma$ satisfy $L_{\sigma}(1)=1$, $L_{\sigma}(2)=2$ and
\begin{equation} \label{eq4}
	L_{\sigma}(t) \leq a+b\lfloor \log_{2}(t-1) \rfloor,
\end{equation}
for all $3\leq t\in\mathbb{N}$, where $a$ and $b$ are positive constants.
Then
\begin{equation}\label{eq5}
	\lim\limits_{n\to +\infty}\mathcal{L}(n,\sigma)\leq b,
\end{equation}
and when inequality~\eqref{eq4} takes the equal sign, inequality~\eqref{eq5} also takes the equal sign.
\end{lemma}
\begin{proof}
Let $m=\lfloor \log_{2}n \rfloor$ and $l=n-2^m$.
When the integer $n\geq 3$, we have
\begin{equation}  \label{eq6}
\begin{aligned}
	\sum_{t=1}^{n}L_{\sigma}(t)& \leq 3+\sum_{t=3}^{n}\Big( a+b\lfloor \log_{2}(t-1) \rfloor \Big) \\
	&= 3+a(n-2)+b\sum_{t=2}^{n-1}\lfloor \log_{2}t \rfloor         \\
	&= 3+a(n-2)+b\Big(lm+\sum_{d=1}^{m-1}d\cdot2^{d}\Big) \\
	&= 3+a(n-2)+b\Big[lm+(m-2)2^{m}+2\Big]  \\
	&= 3+a(n-2)+b(nm+2l-2n+2). \\
\end{aligned}
\end{equation}
Then, we obtain
\begin{equation*}
	\begin{aligned}
		\lim\limits_{n\to +\infty}\mathcal{L}(n,\sigma)&\leq  \lim\limits_{n\to +\infty}\dfrac{3+a(n-2)+b(nm+2l-2n+2)}{nm+2l} \\
		&= b+\lim\limits_{n\to +\infty}\dfrac{3+an-2a+2b-2bn}{nm+2l}       \\
		&= b+\lim\limits_{n\to +\infty}\dfrac{(a-2b)n}{nm+2l}       \\
		&= b. \\
	\end{aligned}
\end{equation*}
From the above calculation process, it is easy to know that when inequality~\eqref{eq4} takes the equal sign, inequality~\eqref{eq5} also takes the equal sign.
\end{proof}

Lemma~\ref{lem3} shows that the integer code $\sigma$ should be chosen
so that the constant $b$ for the panning code $\sigma+$ in inequality~\eqref{eq4} is as small as possible.
Because the global metric $K_{\Sigma}\leq 1.5$, it is hoped that the constant $b$ in inequality~\eqref{eq4} takes $1.5$.
In this case, when $n=2$ and $n$ tends to infinity, $\mathcal{L}(n,\sigma+)$ is less than or equal to $1.5$, and it is reasonable to guess that the global metric at this time is better.

Both $\iota$ code and $\eta$ code satisfy that the length of the first codeword is $1$,
and the constant $b$ in inequality~\eqref{eq4} can be set to be $1.5$.
Therefore, at the end of this subsection,
we analyze the global metrics for $(2,\infty)$-threshold secret sharing schemes corresponding to
$\iota+$ code and $\eta+$ code respectively.

First, analyse the global metrics $K_{I+}$ corresponding to $\iota+$ code.
The $\iota+$ code satisfy $L_{\iota+}(1)=1$, $L_{\iota+}(2)=2$ and
\begin{equation*}
	L_{\iota+}(t)=L_{\iota}(t-1)+1 \leq \frac{7}{2}+\frac{3}{2}\lfloor \log_{2}(t-1) \rfloor.
\end{equation*}
for all $3\leq t\in\mathbb{N}$.
When $n=4$, we obtain
\[
\mathcal{L}(4,\iota+)=\dfrac{\sum_{t=1}^{4}L_{\iota+}(t)}{ 4\times2+2\times0 } = 1.625.
\]
When $2\leq n<15$, we can directly verify that $\mathcal{L}(n,\iota+)\leq 1.625$.
When $n\geq 16$ (i.e. $m\geq 4$), $a=\frac{7}{2}$ and $b=\frac{3}{2}$ can be substituted into~\eqref{eq6} to get
\begin{equation*}
	\sum_{t=1}^{n}L_{\sigma}(t) \leq \frac{3}{2}(nm+2l)+\frac{1}{2}n-1.
\end{equation*}
Thus, we have
\begin{equation*}
	\begin{aligned}
		\mathcal{L}(n,\iota+)&\leq \dfrac{1.5(nm+2l)+0.5n-1}{nm+2l} \\
		&= 1.5+\dfrac{0.5n-1}{nm+2l}       \\
		&< 1.5+\dfrac{0.5n}{nm}       \\
		&= 1.5+\dfrac{1}{2m}   \\
		&\leq 1.625 . \\
	\end{aligned}
\end{equation*}
Therefore, the global metric corresponding to the $\iota+$ code is $K_{I+}=1.625$.

Second, analyse the global metrics $K_{H+}$ corresponding to $\eta+$ code.
The $\eta+$ code satisfy $L_{\eta+}(1)=1$, $L_{\eta+}(2)=2$ and
\begin{equation*}
	L_{\eta+}(t)=L_{\eta}(t-1)+1 \leq 4+\frac{3}{2}\lfloor \log_{2}(t-2) \rfloor.
\end{equation*}
for all $3\leq t\in\mathbb{N}$.
When $n=32$, we obtain
\[
\mathcal{L}(32,\eta+)=\dfrac{\sum_{t=1}^{32}L_{\eta+}(t)}{ 32\times5+2\times0 } = 1.61875.
\]
When $2\leq n<512$, we can directly verify that $\mathcal{L}(n,\eta+)\leq 1.61875$.
When $n\geq 512$ (i.e. $m\geq 9$), we consider the following two cases.
\begin{enumerate}
\item $n$ is a power of $2$:

In this case, $n=2^m$ and $nm+2l=nm$.
When $m\geq 9$, we obtain
\begin{equation*}
	\begin{aligned}
		\sum_{t=1}^{n}L_{\eta+}(t)& \leq 3+\sum_{t=3}^{n}\Big( 4+\frac{3}{2}\lfloor \log_{2}(t-2) \rfloor \Big) \\
		&  = 4n-5+\frac{3}{2}\sum_{t=2}^{n-2}\lfloor \log_{2}t \rfloor         \\
		&  = 4n-5+\frac{3}{2}\Big(\sum_{d=1}^{m-1}d\cdot2^{d}-(m-1)\Big) \\
		&  = 4n-5+\frac{3}{2}\Big[(m-2)2^{m}-m+3\Big]  \\
		&  = \frac{3}{2}nm+n-\frac{3}{2}m-\frac{1}{2}. \\
	\end{aligned}
\end{equation*}
Thus, we have
\begin{equation*}
	\begin{aligned}
		\mathcal{L}(n,\eta+)&\leq 1.5+\dfrac{n-1.5m-0.5}{nm}       \\
		&< 1.5+\dfrac{n}{nm}       \\
		&= 1.5+\dfrac{1}{m}    \\
		&< 1.61875 . \\
	\end{aligned}
\end{equation*}
\item $n$ is not a power of $2$:

In this case, $n=2^{m}+l$ and $1\leq l \leq 2^{m}-1$.
When $m\geq 9$, we obtain
\begin{equation*}
	\begin{aligned}
		\sum_{t=1}^{n}L_{\eta+}(t)& \leq  4n-5+\frac{3}{2}\sum_{t=2}^{n-2}\lfloor \log_{2}t \rfloor         \\
		&  = 4n-5+\frac{3}{2}\Big[(l-1)m+\sum_{d=1}^{m-1}d\cdot2^{d}\Big] \\
		&  = 4n-5+\frac{3}{2}\Big[lm-m+(m-2)2^{m}+2\Big]  \\
		&  = \frac{3}{2}\Big(nm+2l\Big)+n-1.5m-2. \\
	\end{aligned}
\end{equation*}
Thus, we have
	\begin{equation*}
	\begin{aligned}
		\mathcal{L}(n,\eta+)&\leq 1.5+\dfrac{n-1.5m-2}{nm+2l}       \\
		&< 1.5+\dfrac{n}{nm}       \\
		&= 1.5+\dfrac{1}{m}    \\
		&< 1.61875 . \\
	\end{aligned}
\end{equation*}
\end{enumerate}
In summary, when $m\geq 9$, we obtain $\mathcal{L}(n,\eta+)< 1.61875$.
Therefore, the global metric corresponding to the $\eta+$ code is $K_{H+}=1.61875$.

It can be seen from the calculation that the global metrics $K_{I+}=1.625$ and $K_{H+}=1.61875$
are close to the lower bound 1.5,
so $(2,\infty)$-threshold secret sharing schemes $I+$ and $H+$
corresponding to $\iota+$ code and $\eta+$ code have good overall effects.

\subsection{$\lambda$ code achieves $K_{\Lambda}=1.59375$}

In this subsection, we construct a new integer code, termed $\lambda$ code,
to achieve the global metric $K_{\Lambda}=1.59375$.
In the previous subsection, the panning codes constructed using the existing integer codes achieve good global metrics.
At present, the best effect is the global metric $K_{H+}=1.61875$, which is achieved by $\eta+$ code.
The structure of $\lambda$ code is related to $\eta+$ code, and the specific structure is as follows.

Let $\boldsymbol{a}\in\mathbb{B}^{m}$ denote a codeword of length $m$, then $\boldsymbol{a}0$ and $\boldsymbol{a}1$ are two codewords of length $m+1$.
We call the process from $\boldsymbol{a}$ to $\boldsymbol{a}0$ and $\boldsymbol{a}1$ as \emph{the splitting of $\boldsymbol{a}$}.
If $\boldsymbol{a}$ is a codeword of $\sigma$ code,
and $\boldsymbol{a}$ is replaced by two codewords after $\boldsymbol{a}$ split,
then $\sigma$ code is said to be split at $\boldsymbol{a}$,
and $\sigma$ code after the split is noted as $\sigma[\boldsymbol{a}]$.
Obviously, if $\sigma$ code is a prefix code, then $\sigma[\boldsymbol{a}]$ code is still a prefix code.

$\lambda$ code is essentially the code obtained after $\eta+$ code is splits at $\eta+(5)$, $\eta+(8)$, $\eta+(9)$,
$\eta+(14)$, $\eta+(15)$, $\eta+(16)$ and $\eta+(17)$; that is,
$$\lambda=\eta+[\eta+(5),\eta+(8),\eta+(9),\eta+(14),\eta+(15),\eta+(16),\eta+(17)].$$
Table \ref{tab2} lists the first $24$ codewords of $\eta+$ code and $\lambda$ code.
The underlined part in Table \ref{tab2} is related to the split codeword.
$\sum_{t=1}^{24}L_{\lambda}(t)=174$ can be obtained by simple calculations.
When $n\geq 25$, $\lambda(n)=\eta+(n-7)=0\eta(n-8)$.
Therefore, we obtain
\begin{equation*}
\begin{aligned}
	L_{\lambda}(n)=L_{\eta}(n-8)+1 \leq 4+\frac{3}{2}\lfloor \log_{2}(n-9) \rfloor,
\end{aligned}
\end{equation*}
for all $25\leq n\in\mathbb{N}$.

\begin{table}[t]
	\centering
	\caption{The first $24$ codewords of $\eta+$ code and $\lambda$ code}\label{tab2}
	\begin{tabular}{|c|c|c|}
		\hline
		$n$  &   $\eta+$ code  & $\lambda$ code   \\
		\hline
		$1$   &      1        &  1           \\
		$2$   &     01      &   01      \\
		$3$   &    0010     &  0010     \\
		$4$   &    00110    &  00110    \\
		$5$   &  \underline{00111} &  \underline{00111}0  \\
		$6$   &   0001000   &  \underline{00111}1     \\
		$7$   &   0001001   &  0001000       \\
		$8$   &  \underline{0001010}   &  0001001     \\
		$9$   &  \underline{0001011}   & \underline{0001010}0    \\
		$10$  &   00011000   & \underline{0001010}1    \\
		$11$   &  00011001   & \underline{0001011}0    \\
		$12$   &  00011010   & \underline{0001011}1   \\
		$13$   &  00011011  &  00011000    \\
		$14$   &  \underline{00011100}  &  00011001    \\
		$15$   &  \underline{00011101}  &  00011010     \\
		$16$   &  \underline{00011110}  &   00011011   \\
		$17$   &  \underline{00011111}  &  \underline{00011100}0    \\
		$18$   &  000010000  &  \underline{00011100}1    \\
		$19$   &  000010001  &  \underline{00011101}0   \\
		$20$   &  000010010  &  \underline{00011101}1    \\
		$21$   &  000010011  &  \underline{00011110}0    \\
		$22$   &  000010100  &  \underline{00011110}1   \\
		$23$   &  000010101  &  \underline{00011111}0     \\
		$24$   &  000010110  &  \underline{00011111}1   \\
		\hline
	\end{tabular}
\end{table}
Next, analyse the global metrics $K_{\Lambda}$ corresponding to $\lambda$ code.
When $n=16$, we obtain
\[
\mathcal{L}(16,\lambda)=\dfrac{\sum_{t=1}^{16}L_{\lambda}(t)}{ 16\times4+2\times0 } = 1.59375.
\]
When $2\leq n<2048$, we can directly verify that $\mathcal{L}(n,\lambda)\leq 1.59375$.
When $n\geq 2048$ (i.e. $m\geq 11$), we have
\begin{equation*}
	\begin{aligned}
		\sum_{t=1}^{n}L_{\lambda}(t)& \leq 174+\sum_{t=25}^{n}L_{\lambda}(t) \\
		&  \leq 174+4(n-24)+\frac{3}{2}\sum_{t=25}^{n}\lfloor \log_{2}(t-9) \rfloor         \\
		&  = 78+4n+\frac{3}{2}\sum_{t=16}^{n-9}\lfloor \log_{2}t \rfloor. \\
	\end{aligned}
\end{equation*}
According to the value of $l=n-2^m$, the following two cases are discussed.
\begin{enumerate}
	\item $l\geq 8$:

	When $m\geq 11$, we obtain
	\begin{equation*}
		\begin{aligned}
	\sum_{t=16}^{n-9}\lfloor \log_{2}t \rfloor &  =\sum_{d=4}^{m-1}d\cdot2^{d}+ m(l-8)\\
			&  = (m-2)2^{m}-32+ml-8m . \\
		\end{aligned}
	\end{equation*}
	Thus, we have
	\begin{equation*}
		\begin{aligned}
			\mathcal{L}(n,\lambda)&\leq \dfrac{78+4n+1.5\Big[(m-2)2^{m}-32+ml-8m\Big]}{nm+2l}       \\
			&= 1.5+\dfrac{n-12m+30}{nm+2l}       \\
			&< 1.5+\dfrac{n}{nm+2l}    \\
			&< 1.5+\dfrac{1}{m}    \\
			&< 1.59375. \\
		\end{aligned}
	\end{equation*}
	\item $1\leq l< 8$:

	When $m\geq 11$, we obtain
	\begin{equation*}
	\begin{aligned}
		\sum_{t=16}^{n-9}\lfloor \log_{2}t \rfloor &  =\sum_{d=4}^{m-1}d\cdot2^{d}+ (m-1)(l-8)\\
		&  = (m-2)2^{m}-24+ml-8m-l . \\
	\end{aligned}
\end{equation*}
Thus, we have
\begin{equation*}
	\begin{aligned}
		\mathcal{L}(n,\lambda)&\leq \dfrac{78+4n+1.5\Big[(m-2)2^{m}-24+ml-8m-l\Big]}{nm+2l}       \\
		&= 1.5+\dfrac{n-12m-1.5l+42}{nm+2l}       \\
		&< 1.5+\dfrac{n}{nm+2l}    \\
		&< 1.59375. \\
	\end{aligned}
\end{equation*}
\end{enumerate}
In summary, when $m\geq 11$, we obtain $\mathcal{L}(n,\lambda)< 1.59375$.
Therefore, the global metric corresponding to the $\lambda$ code is $K_{\Lambda}=1.59375$.
Further, we prove that the range of the global metric $K_{\Sigma}$ for the optimal
$(2,\infty)$-threshold secret sharing scheme is $1.5\leq K_{\Sigma}\leq1.59375$.

\section{Conclusions}\label{sec_con}
In this paper, we propose a new metric $K_{\Sigma}$ for evolving $2$-threshold secret sharing schemes $\Sigma$
and study the range of the global metric $K_{\Sigma}$ for the optimal $(2,\infty)$-threshold secret sharing scheme.
First, we show that the global metric $K_{\Sigma}\geq 1.5$ and use the known universal coding of integers to
construct schemes with good global metrics.
Second, we construct a new integer code, termed $\lambda$ code, to achieve the global metric $K_{\Lambda}=1.59375$.
This work shows that the range of the global metric $K_{\Sigma}$ for the optimal
$(2,\infty)$-threshold secret sharing scheme is $1.5\leq K_{\Sigma}\leq1.59375$.
Furthermore, the reachable lower bound of the sum of share sizes for $(2,n)$-threshold secret sharing schemes is proved.
Several issues remain as follows.
\begin{enumerate}
\item Is it possible to construct an integer code whose global metric is strictly less than $1.59375$?
\item The explicit value of $K_{\Sigma}$ of the optimal $(2,\infty)$-threshold secret sharing scheme is still unknown.
\end{enumerate}
\bibliographystyle{IEEEtran}