## 4 DKI Capacity Region of the BSC
### Upper Bound (Converse Proof)
For any overall/generic selection of the goal message, set \(\mathbb{K}\subseteq\llbracket M\rrbracket\) of size \(K\), as an approaches to infinity, the upper bound on the sort I and sort II error probabilities, or \(e_{1}^{(n)}\) and \(e_{2}^{(n)}\), respectively, tends to zero. That is,  
\[\lim_{n\to\infty}\left[P_{e,1}(i_{1},\mathbb{K})+P_{e,2}(i_{2},\mathbb{K}) \right]=0,\ \forall\mathbb{K}\subseteq\llbracket M\rrbracket. \tag{60}\]  
Next, we will represent a particular class of the goal message sets by \(\mathbb{K}(i_{1},i_{2})\), where \(i_{1}\in\mathbb{K}\) and \(i_{2}\
otin\mathbb{K}\), i.e.,  
\[\mathbb{K}(i_{1},i_{2})\triangleq\big{\{}\mathbb{K}\subseteq\llbracket M \rrbracket;\ |\mathbb{K}|=K;\ i_{1}\in\mathbb{K},\,i_{2}\
otin\mathbb{K}\big{\}}. \tag{61}\]  
Observe that \(|\mathbb{K}(i_{1},i_{2})|\geq 1\); that is, there exists at least one arrangement \(\mathbb{K}^{\prime}\) belonging to \(\mathbb{K}(i_{1},i_{2})\), where \(i_{1}\in\mathbb{K}\), \(i_{2}\
otin\mathbb{K}\). This is valid as the two messages \(i_{1}\) and \(i_{2}\) are different, i.e., \(i_{1}\
eq i_{2}\), in accordance with Lemma 3. The sort I and sort II error probability, so have the subsequent upper bounds:  
\[P_{e,1}(i_{1},\mathbb{K}) =W^{n}(\mathcal{T}_{\mathbb{K}}^{c}\,|\,x^{n}=\mathbf{c}_{i_{1}} )_{i_{1}\in\mathbb{K}}\leq e_{1}^{(n)},\] \[P_{e,2}(i_{2},\mathbb{K}) =W^{n}(\mathcal{T}_{\mathbb{K}}\,|\,x^{n}=\mathbf{c}_{i_{2}})_{i_{ 2}\
otin\mathbb{K}}\leq e_{2}^{(n)}, \tag{62}\]  
where \(\mathcal{T}_{\mathbb{K}}\subseteq\mathbb{H}^{n}\) is the decoding set considered for the set of goal messages \(\mathbb{K}\). This leads to a _contradiction_, since  
\[1 =W^{n}(\mathcal{T}_{\mathbb{K}}^{c}\,|\,x^{n})+W^{n}(\mathcal{T}_{ \mathbb{K}}\,|\,x^{n})\] \[=P_{e,1}(i_{1},\mathbb{K})+P_{e,2}(i_{2},\mathbb{K}) \tag{63}\] \[\leq e_{1}^{(n)}+e_{2}^{(n)},\]where the last inequality exploits the definition of sort I/II error probabilities given in (8) and (9). Therefore, \(e_{1}^{(n)}+e_{2}^{(n)}\geq 1\), which is a contradiction to (60). Put differently, Lemma 3 asserts that every given sequence of BSC DKI codes \((\mathcal{C}^{(n)},\mathcal{T}^{(n)})\) has the below property: The upper limits on the sort I and sort II error probabilities disappear for an arbitrary (generic) choice of \(\mathsf{K}\) of size \(K(n,\kappa)\), meaning that \(e_{1}^{(n)}\) and \(e_{2}^{(n)}\) tend to zero as \(n\to\infty\). Nevertheless, we demonstrate that there are specific options for \(\mathsf{K}\), shown by \(\mathsf{K}(i_{1},i_{2})\), whose elements does not satisfy this property, namely, \(e_{1}^{(n)}\) and \(e_{2}^{(n)}\) do not disappear since the sum of the corresponding upper limits on the sort I and sort II errors is lower bounded by one. This observation is obviously contradictory, as the inequality presented in (59) does not hold. Hence, distinct messages \(i_{1}\) and \(i_{2}\) cannot share the same codeword, and there exist an one-to-one mapping between the message set \(\mathcal{M}\) and the codebook \(\mathcal{C}\). This concludes the proof of Lemma 3. Case 1: with Hamming weight constraint (\(0<A<1\))  
Lemma 3 states that every message has a distinct/unique codeword. As a result, the number of input sequences that meet the input restriction/constraint serves as the maximum number of messages. We divide in two cases, namely, where \(0<A<1/2\) and \(1/2\leq A<1\). For the first case, we obtain the subsequent upper bound on the size of the DKI codebook:  
\[i_{1}\
eq i_{2}\quad\Rightarrow\quad\mathbf{c}_{i_{1}}\
eq\mathbf{c}_{i_{2}}. \tag{58}\]0  
where \((a)\) exploits the upper bound on the volume of the Hamming ball provided in Lemma A2 for \(0<A<1/2\). Thereby, (64) implies  
\[i_{1}\
eq i_{2}\quad\Rightarrow\quad\mathbf{c}_{i_{1}}\
eq\mathbf{c}_{i_{2}}. \tag{58}\]1  
On the other hand, for a given sequence of DKI code in the converse, the size of the goal message set \(\mathsf{K}\) is always upper bounded by the size of the message set \(\mathcal{M}\); that is, \(2^{n\kappa}\leq 2^{nR}\) gives \(\kappa\leq R\).