## 4 DKI Capacity Region of the BSC
### Inner Bound (Achievability Proof)
According to the greedy construction, the center \(\mathbf{c}_{i}\) of each small Hamming hyper ball corresponds to a codeword. Since the volume of each hyper ball is equal to \(\mathrm{Vol}(\mathcal{B}_{\mathbf{c}_{1}}(n,r_{0}))\), the centers of all balls lie inside the space \(\mathbf{H}^{n}\), and the Hamming hyper balls _overlap_ with each other, the total number of balls is bounded from below by  
\[d_{\min}\triangleq\min_{(i,j)\in[\![M]\!]\times[\![M]\!]}d_{\mathrm{H}}( \mathbf{c}_{i},\mathbf{c}_{j}). \tag{28}\]3  
where \((a)\) holds since the Hamming hyper balls may have, in general, an _intersection_, and \((b)\) follows, since \(\mathrm{Vol}(\mathbf{H}^{n})=|\mathcal{X}^{n}|=|\mathcal{X}|^{n}\). Now, the bound in (45) can be further simplified as follows  
\[d_{\min}\triangleq\min_{(i,j)\in[\![M]\!]\times[\![M]\!]}d_{\mathrm{H}}( \mathbf{c}_{i},\mathbf{c}_{j}). \tag{28}\]4  
where \((a)\) exploits Lemma (A76) with \(\varepsilon=\beta\). Now, for \(\beta\in(0,\beta_{\max})\) being an arbitrary small positive constant, we obtain  
\[d_{\min}\triangleq\min_{(i,j)\in[\![M]\!]\times[\![M]\!]}d_{\mathrm{H}}( \mathbf{c}_{i},\mathbf{c}_{j}). \tag{28}\]5  
where the dominant term has an order of \(n\). Therefore, in order to obtain finite value for the lower bound on the DKI coding rate, \(R\), (38) induces the scaling law of codebook size, \(M\), to be \(2^{nR}\). Hence, we obtain  
\[d_{\min}\triangleq\min_{(i,j)\in[\![M]\!]\times[\![M]\!]}d_{\mathrm{H}}( \mathbf{c}_{i},\mathbf{c}_{j}). \tag{28}\]6  
which tends to \(1-H(\beta)\) as \(n\to\infty\). \[d_{\min}\triangleq\min_{(i,j)\in[\![M]\!]\times[\![M]\!]}d_{\mathrm{H}}( \mathbf{c}_{i},\mathbf{c}_{j}). \tag{28}\]7  
where  
\[d_{\min}\triangleq\min_{(i,j)\in[\![M]\!]\times[\![M]\!]}d_{\mathrm{H}}( \mathbf{c}_{i},\mathbf{c}_{j}). \tag{28}\]8  
is known as the _decoding metric_ assessed for the individual codeword \(\mathbf{c}_{j}\) and the observation vector \(\mathbf{y}\), with the _Kronecker delta_ being \(\delta_{\beta}(\cdot,\cdot)\). In other words, given the channel output vector \(\mathbf{y}\in\mathbf{H}^{n}\), the decoder indicates that the message \(j\) was sent if there is at least one \(j\in\mathsf{K}\), such that \(d_{\mathrm{H}}(\mathbf{y},\mathbf{c}_{j})\leq\Big{\lfloor}n\delta_{\beta} \Big{\rfloor}\). In the alternative scenario, wherein the inequality \(d_{\mathrm{H}}(\mathbf{y},\mathbf{c}_{j})>\Big{\lfloor}n\delta_{\beta}\Big{\rfloor}\) applies for every index \(j\in\mathsf{K}\), the decoder determines that \(j\) was not sent. **Remark 2**. : _Adopted decoder For the achievability proof, we use a decoder that, given an output sequence \(\mathbf{y}\), states that if the output vector \(\mathbf{y}\) is in the subsequent set, then the message \(j\in\mathsf{K}\) was sent_  
\[d_{\min}\triangleq\min_{(i,j)\in[\![M]\!]\times[\![M]\!]}d_{\mathrm{H}}( \mathbf{c}_{i},\mathbf{c}_{j}). \tag{28}\]9  
_where \(\delta_{\beta}\) is a decoding threshold and \(\mathbf{c}_{j}=[c_{j,1},\ldots,c_{j,n}]\) is the codeword linked to message \(j\). We notice that the decoder in (53) combines the elements of set \(\mathsf{K}\) through a fundamental union operator. Such a simple operator may feature a penalty with respect to the error exponents for the sort I/II error probabilities or the obtained attainable rates. Therefore, we recall that in principle a more optimum decoder for the \(K\)-Identification scheme, which guarantees vanishing sort I/II error probabilities, might demand a more complicated algebraic operators between the realization of members for each specific set \(\mathsf{K}\), and entails advanced dependencies on the elements of set \(\mathsf{K}\)._  
In the subsequent, we examine the error probabilities of sort I and sort II. In particular, the sort I error analysis is less involved and exploiting known bounds related to the upper tail of the Binomial CDF we guarantee its vanishing. The sort II error analysis is more complicated, where we combines techniques from JJA[33] and certain Hamming distance property for the binary alphabet.