# Zero-error network information theory: graphs, coding for computing and source-channel duality

Nicolas Charpenay

► To cite this version:

Nicolas Charpenay. Zero-error network information theory: graphs, coding for computing and source-channel duality. Information Theory [math.IT]. Université de Rennes, 2023. English. NNT: 2023URENS085. tel-04523591

HAL Id: tel-04523591

https://theses.hal.science/tel-04523591

Submitted on 27 Mar 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
THÈSE DE DOCTORAT DE

L'UNIVERSITÉ DE RENNES

ÉCOLE DOCTORALE N° 601
Mathématiques, Télécommunications, Informatique, Signal, Systèmes, Électronique

Spécialité : Signal, Image, Vision

Par
Nicolas CHARPENAY

Théorie de l'information zéro-erreur dans les réseaux :
graphes, codage pour le calcul de fonctions et dualité source-canal

Thèse présentée et soutenue à Rennes, le mardi 28 novembre 2023

Unité de recherche : IRISA UMR 6074 et Centre Inria de l'Université de Rennes

Rapporteurs avant soutenance :

Mikael SKOGLUND Professeur à KTH

Michèle WIGGER Professeure à Telecom Paris

Composition du Jury :

Président : Jean-Marie GORCE

Rapporteurs :
Mikael SKOGLUND
Michèle WIGGER

Examinatrice : Derya MALAK

Dir. de thèse : Aline ROUMY

Co-dir. de thèse : Maël LE TREUST

Invité : Tristan TOMALA

Professeur des Universités à INSA Lyon (à préciser après la soutenance)

Professeur à KTH

Professeure à Telecom Paris

Maître de Conférences à EURECOM

Directrice de Recherche Inria

Chargé de Recherche CNRS

Professeur à HEC Paris
<figure><img src="image_2.png" /></figure>
# TABLE OF CONTENTS

## 1 Résumé 7

1.1 Problèmes zéro-erreur basés sur la correction 8

1.2 Problèmes zéro-erreur basés sur les graphes 10

1.3 Problèmes zéro-erreur pour le calcul de fonction 11

1.4 Organisation du manuscrit 11

## Glossary 13

## 2 Introduction 15

2.1 Correction-based zero-error problems 16

2.2 Graph-based zero-error problems 17

2.3 Coding for computing zero-error problems 18

2.4 Organization of the manuscript 19

## 3 State of the art 21

3.1 Source coding 21

3.2 Channel coding 23

3.2.1 Channel coding in the vanishing error regime 25

3.2.2 Zero-error channel coding 25

3.2.3 Related works 28

3.3 Slepian-Wolf problem 28

3.3.1 Zero-error Slepian-Wolf problem 30

## 4 Contributions for correction-based zero-error problems 33

4.1 Correction-based zero-error problems 33

4.1.1 Zero-error source coding when side information may be present at the decoder 33

4.1.2 Gray-Wyner problem 36

4.1.3 Zero-error source coding for a Gray-Wyner network when side information may be present at the decoder 38
TABLE OF CONTENTS

<table>
  <tbody>
    <tr>
      <td>4.2</td>
      <td>Main results for the zero-error source coding problem when side information may be present at the decoder</td>
      <td>41</td>
    </tr>
    <tr>
      <td>4.2.1</td>
      <td>Definitions for the achievability proof</td>
      <td>43</td>
    </tr>
    <tr>
      <td>4.2.2</td>
      <td>Coding scheme</td>
      <td>44</td>
    </tr>
    <tr>
      <td>4.2.3</td>
      <td>Zero-error property and rate analysis</td>
      <td>46</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Main results for the zero-error source coding problem for a Gray-Wyner network when side information may be present at the decoder</td>
      <td>46</td>
    </tr>
    <tr>
      <td>4.3.1</td>
      <td>Comparison with previous results</td>
      <td>48</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Contributions for graph-based zero-error problems</td>
      <td>51</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Graph-based zero-error problems</td>
      <td>52</td>
    </tr>
    <tr>
      <td>5.1.1</td>
      <td>Zero-error channel coding with typical input constraint</td>
      <td>52</td>
    </tr>
    <tr>
      <td>5.1.2</td>
      <td>Linearization in the zero-error Slepian-Wolf problem</td>
      <td>54</td>
    </tr>
    <tr>
      <td>5.1.3</td>
      <td>Linearization in zero-error channel coding</td>
      <td>57</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Main results on the linearization of H and C(·, P<sub>V</sub>)</td>
      <td>62</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Main results on capacity-achieving distributions</td>
      <td>64</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Linking the linearizations of C<sub>0</sub> and C(·, P<sub>V</sub>)</td>
      <td>66</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Main examples and counterexamples of linearization</td>
      <td>67</td>
    </tr>
    <tr>
      <td>5.5.1</td>
      <td>Perfect graphs</td>
      <td>67</td>
    </tr>
    <tr>
      <td>5.5.2</td>
      <td>The Schläfli graph</td>
      <td>70</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Contributions for coding for computing zero-error problems</td>
      <td>73</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Coding for computing problems</td>
      <td>73</td>
    </tr>
    <tr>
      <td>6.1.1</td>
      <td>Coding for computing in the vanishing error regime</td>
      <td>73</td>
    </tr>
    <tr>
      <td>6.1.2</td>
      <td>Zero-error coding for computing with side information at the encoder</td>
      <td>75</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>General case</td>
      <td>77</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>Pairwise shared side information</td>
      <td>78</td>
    </tr>
    <tr>
      <td>6.4</td>
      <td>Example</td>
      <td>80</td>
    </tr>
    <tr>
      <td colspan="2">Conclusion</td>
      <td>83</td>
    </tr>
    <tr>
      <td colspan="2">A Proofs for correction-based zero-error results</td>
      <td>85</td>
    </tr>
    <tr>
      <td>A.1</td>
      <td>Proof of Lemma 4.2.5</td>
      <td>85</td>
    </tr>
    <tr>
      <td>A.1.1</td>
      <td>Preliminaries</td>
      <td>85</td>
    </tr>
    <tr>
      <td>A.1.2</td>
      <td>Probability of decoding ambiguity</td>
      <td>85</td>
    </tr>
    <tr>
      <td>A.1.3</td>
      <td>Rate on the common channel</td>
      <td>87</td>
    </tr>
  </tbody>
</table>
<table><tbody><tr><td>A.1.4</td><td>Rate on the secondary channel</td><td>88</td></tr><tr><td>A.2</td><td>Proof of Theorem 4.3.1</td><td>90</td></tr><tr><td>A.2.1</td><td>Outline</td><td>90</td></tr><tr><td>A.2.2</td><td>Encoding algorithm</td><td>91</td></tr><tr><td>A.2.3</td><td>Decoding algorithm and zero-error property</td><td>92</td></tr><tr><td>A.2.4</td><td>Probability of a decoding ambiguity</td><td>93</td></tr><tr><td>A.2.5</td><td>Rate analysis</td><td>93</td></tr><tr><td>A.3</td><td>Proof of Theorem 4.3.2</td><td>94</td></tr><tr><td>A.4</td><td>Proof of Lemma 4.3.3</td><td>96</td></tr><tr><td><b>B</b></td><td><b>Proofs for graph-based zero-error results</b></td><td><b>99</b></td></tr><tr><td>B.1</td><td>Proof dependencies</td><td>99</td></tr><tr><td>B.2</td><td>Main proofs for the linearization of $\overline{H}$ and $C(\cdot, P_V)$</td><td>99</td></tr><tr><td>B.2.1</td><td>Proof of Lemma 5.2.1</td><td>99</td></tr><tr><td>B.2.2</td><td>Proof of Theorem 5.2.4</td><td>100</td></tr><tr><td>B.2.3</td><td>Proof of Lemma B.2.1</td><td>101</td></tr><tr><td>B.2.4</td><td>Proof of Proposition 5.2.5</td><td>104</td></tr><tr><td>B.3</td><td>Main proofs for the capacity-achieving distributions</td><td>105</td></tr><tr><td>B.3.1</td><td>Proof of Lemma 5.1.3</td><td>105</td></tr><tr><td>B.3.2</td><td>Proof of Theorem 5.1.4</td><td>106</td></tr><tr><td>B.3.3</td><td>Proof of Proposition 5.3.2</td><td>109</td></tr><tr><td>B.3.4</td><td>Proof of Theorem 5.3.3</td><td>110</td></tr><tr><td>B.3.5</td><td>Proof of Lemma 5.3.7</td><td>114</td></tr><tr><td>B.4</td><td>Main proofs for the link between linearizations of $C(\cdot, P_V)$ and $C_0$</td><td>115</td></tr><tr><td>B.4.1</td><td>Proof of Theorem 5.4.1</td><td>115</td></tr><tr><td>B.4.2</td><td>Proof of Lemma B.4.1</td><td>116</td></tr><tr><td>B.4.3</td><td>Proof of Lemma B.4.2</td><td>117</td></tr><tr><td>B.4.4</td><td>Proof of Theorem 5.4.2</td><td>118</td></tr><tr><td>B.4.5</td><td>Proof of Lemma B.4.3</td><td>120</td></tr><tr><td>B.4.6</td><td>Proof of Lemma B.4.4</td><td>121</td></tr><tr><td>B.5</td><td>Main proofs for the examples and counterexamples</td><td>122</td></tr><tr><td>B.5.1</td><td>Proof of Theorem 5.5.8</td><td>122</td></tr><tr><td>B.6</td><td>Secondary proofs</td><td>123</td></tr><tr><td>B.6.1</td><td>Proof of Lemma B.2.2</td><td>123</td></tr></tbody></table>
TABLE OF CONTENTS

<table><tbody><tr><td>B.6.2</td><td>Proof of Lemma B.2.3</td><td>125</td></tr><tr><td>B.6.3</td><td>Proof of Lemma B.2.4</td><td>126</td></tr><tr><td>B.6.4</td><td>Proof of Lemma B.2.5</td><td>126</td></tr><tr><td>B.6.5</td><td>Proof of Lemma B.2.7</td><td>127</td></tr><tr><td>B.6.6</td><td>Proof of Lemma B.2.8</td><td>128</td></tr><tr><td>B.6.7</td><td>Proof of Lemma B.3.1</td><td>129</td></tr><tr><td>B.6.8</td><td>Proof of Lemma B.4.5</td><td>130</td></tr><tr><td>B.6.9</td><td>Proof of Lemma B.5.2</td><td>131</td></tr><tr><td>B.6.10</td><td>Proof of Lemma B.6.1</td><td>131</td></tr><tr><td>B.6.11</td><td>Proof of Lemma B.6.2</td><td>132</td></tr><tr><td>B.6.12</td><td>Proof of Lemma B.6.4</td><td>133</td></tr><tr><td>B.6.13</td><td>Proof of Lemma B.6.5</td><td>133</td></tr><tr><td>C</td><td>Proofs for coding for computing zero-error results</td><td>135</td></tr><tr><td>C.1</td><td>Proof of Theorem 6.3.2</td><td>135</td></tr><tr><td>C.2</td><td>Proof of Theorem 6.3.6</td><td>137</td></tr><tr><td>C.3</td><td>Proof of Lemma C.2.2</td><td>138</td></tr><tr><td>C.4</td><td>Proof of Lemma C.2.3</td><td>139</td></tr><tr><td>Bibliography</td><td></td><td>141</td></tr></tbody></table>
# RÉSUMÉ

Le codage de source zéro-erreur regroupe une grande variété de problèmes en théorie de l’information, où une source doit être compressée par un encodeur avec un débit à minimiser, puis doit être retrouvée par le décodeur avec probabilité d’erreur zéro. Dans tous les problèmes étudiés ici, la distribution de source est connue et le décodeur a accès à une information adjacente, i.e. une variable aléatoire corrélée à la source qui aide au décodage et à minimiser le débit. L’étude de tels problèmes trouve son utilité dans des applications demandant une garantie forte sur la qualité de reconstruction de la source, en particulier la télédétection et le calcul distribué. Dans un problème de codage de source zéro-erreur, trouver une formule pour le débit optimal permet d’établir une borne théorique sur les performances de tous les schémas de codage possibles. De plus, si cette formule est à une seule lettre (i.e. ne fait pas apparaître de limite), elle peut être facilement calculée. On a aussi l’existence d’un schéma de codage qui permet d’atteindre asymptotiquement ce débit optimal. Pour ces raisons, notre premier objectif dans ce manuscrit sera de trouver des expressions à une seule lettre pour les débits optimaux des problèmes de codage de source zéro-erreur.

La contrainte zéro-erreur diffère de la contrainte d’erreur asymptotiquement nulle, cette dernière ne demandant qu’une limite nulle pour la probabilité d’erreur au décodage quand la longueur du bloc codant tend vers l’infini. Dans les cadres où le décodeur n’a pas d’information adjacente, on peut facilement montrer que les débits optimaux sous les contraintes zéro-erreur et erreur asymptotiquement nulle coïncident. Toutefois, lorsqu’on impose la contrainte zéro-erreur quand le décodeur a une information adjacente – ce sera le cas dans les problèmes étudiés ici, la nature de certains problèmes passe de statistique à combinatoire (e.g. le problème de Slepian-Wolf zéro-erreur). Il s’ensuit que les outils adéquats pour de tels problèmes sont à la fois tirés de la théorie de l’information et de la combinatoire ; et peuvent aller d’un dispositif de correction qui donne la propriété zéro-erreur à des codes existants, à des codes zéro-erreur entièrement bâtis avec des contraintes tirées de la théorie des graphes.
La nature combinatoire des problèmes zéro-erreur est liée à l’incertitude de l’encodeur sur l’information adjacente du décodeur. Dans les problèmes à erreur asymptotiquement nulle, on peut supposer que la suite des réalisations de l’information adjacente du décodeur sera typique par rapport à la distribution de source, avec grande probabilité ; même si l’encodeur n’a pas accès à ces réalisations. En revanche, la contrainte zéro-erreur rend ce manque d’information plus difficile à gérer ; en particulier, il faut que les codes utilisés permettent une reconstruction parfaite de la source pour *n’importe quelle* réalisation de l’information adjacente du décodeur.

Par conséquent, nous classifions les problèmes zéro-erreur étudiés ici en trois catégories ; selon l’information que possède l’encodeur sur l’information adjacente du décodeur, et selon ce que le décodeur lui-même doit retrouver :

- Les problèmes zéro-erreur basés sur la correction, dans lesquels l’encodeur a accès à toutes les informations adjacentes du problème, et peut simuler chaque décodage ;

- Les problèmes zéro-erreur basés sur les graphes, dans lesquels l’encodeur est “moins informé” sur l’information adjacente du décodeur ;

- Les problèmes zéro-erreur pour le calcul de fonction, dans lesquels le décodeur doit calculer une fonction de la source et de son information adjacente ; au lieu de simplement reconstruire la source.

## 1.1 Problèmes zéro-erreur basés sur la correction

Le problème zéro-erreur basés sur la correction peuvent être abordés avec l'aide d'un dispositif de correction qui garantit la propriété zéro-erreur. Il consiste en l'utilisation d'un livre-code adapté à la contrainte d'erreur asymptotiquement nulle, la simulation de chaque décodage, et l'envoi de toute les suite de source s'il y a erreur dans l'un des décodages. Ce dispositif de correction a un impact négligeable sur le débit en raison de la faible probabilité d'erreur, et permet la conversion des codes à erreur asymptotiquement nulle en codes zéro-erreur. Pour cette raison, les outils que nous utilisons avec le dispositif de correction sont la typicalité, et les codes aléatoires et de parité.

Dans le premier problème de cette classe, présenté en Figure 4.1, l’information adjacente peut être présente au décodeur. Dans ce cadre, l’encodeur dispose d’une information adjacente, mais ignore si le décodeur y a accès aussi ; l’encodage est divisé en deux étapes. À la première étape, l’encodeur envoie de l’information sans savoir si l’information adjacente est présente au décodeur. Le message envoyé à la première étape doit être exploitable
indépendamment de l'éventuelle présence de l'information adjacente. De plus, un décodage zéro-erreur doit être réalisé si le décodeur a accès à l'information adjacente. À la deuxième étape, un supplément d'information est envoyé par l'encodeur dans le cas où l'information adjacente n'est pas présente au décodeur, et ce dernier doit ensuite retrouver la source avec zéro-erreur. Ces deux étapes sont modélisées par deux décodeurs différents et deux canaux parfaits. Nous voulons répondre à la question suivante : quelles sont les paires de débits réalisables pour les deux étapes d'encodage, qui permettent un décodage zéro-erreur ? Notre première contribution consiste à déterminer la région réalisable, à l'aide d'une partition en cosets des suites de source, couplée à un dispositif de correction ; prouvant de ce fait que cette région réalisable en zéro-erreur coïncide avec la région réalisable en erreur asymptotiquement nulle.

Le deuxième problème basé sur la correction est illustré en Figure 4.3 et est une généralisation du premier. Dans ce problème où l'encodeur connaît deux sources différentes et leurs informations adjacentes respectives, deux incertitudes se présentent : la première est que l'encodeur ignore quelle source sera demandée par le décodeur, et la deuxième est que l'information adjacente de la source demandée peut être présente au décodeur. L'encodage est alors divisé en trois étapes. À la première étape, l'encodeur envoie de l'information sans savoir quelle source sera demandée ; nous cherchons à envoyer l'information commune aux deux différentes sources, d'où l'appellation "réseau de Gray-Wyner" pour ce problème. À la deuxième étape, l'encodeur est informé de la source demandée par le décodeur, mais ignore toujours si ce dernier dispose d'une information adjacente ; si tel est le cas, alors un décodage zéro-erreur doit être réalisé. La troisième étape est un supplément d'information envoyé par l'encodeur dans le cas où le décodeur ne dispose pas de l'information adjacente ; le décodeur doit ensuite retrouver la source avec zéro-erreur. Pour ce problème, notre deuxième contribution consiste en une borne interne et une borne externe sur la région réalisable. Pour la borne interne, nous utilisons le schéma de codage suivant : des suites auxiliaires sont utilisées pour capturer l'information commune entre les suites de réalisations des deux sources, ensuite nous effectuons un étiquetage aléatoire de ces suites, et les ensembles de suites de source sont partitionnées en cosets. Les algorithmes de décodages sont basés sur les V-enveloppes des suites d'information adjacente, et la propriété zéro-erreur est garantie par un dispositif de correction.
1.2 Problèmes zéro-erreur basés sur les graphes

Dans les problèmes zéro-erreur basés sur les graphes, les contraintes zéro-erreur sont représentées par un graphe caractéristique, et déterminer le débit optimal dans de tels problèmes revient à résoudre des questions difficiles de théorie des graphes. Le problème de Slepian-Wolf zéro-erreur illustré en Figure 3.4 est l’un d’eux, son débit optimal est donné par l’entropie complémentaire $\overline{H}$ de son graphe caractéristique, et trouver une expression à une seule lettre pour $\overline{H}$ est une question ouverte. Toutefois, afin de mieux comprendre la nature du problème Slepian-Wolf zéro-erreur, nous donnons de nouveaux résultats structurels qui lient ce problème avec d’autres, en particulier la capacité zéro-erreur d’un canal $C_0$ (voir la Figure 3.2).

Notre étude principale concerne le problème de “linéarisation”. Dans le cadre du problème Slepian-Wolf zéro-erreur, si l’encodeur est en train de réaliser plusieurs tâches de compression indépendantes avec leurs informations adjacentes respectives, alors le débit optimal est donné par $\overline{H}(\wedge \cdot)$, i.e. $\overline{H}$ d’un graphe avec une structure de produit ET. Comme illustré par Tuncel et al. dans [71], “séparer” les tâches indépendantes donne un schéma d’atteignabilité, d’où $\overline{H}(\wedge \cdot) \le \sum \overline{H}(\cdot)$. Un autre cas d’intérêt est celui où l’encodeur dispose d’une information partielle $g(Y)$ sur l’information adjacente du décodeur. Le débit optimal est donné par $\overline{H}(\sqcup \cdot)$, i.e. $\overline{H}$ d’un graphe avec une structure d’union disjointe. “Séparer” les réalisations de la source selon les valeurs de l’information adjacente de l’encodeur donne aussi un schéma d’atteignabilité, d’où $\overline{H}(\sqcup P_{g(Y)} \cdot) \le \sum_z P_{g(Y)}(z)\overline{H}(\cdot)$. Lorsqu’on a égalité dans l’un ou l’autre de ces cas, on dit qu’on a “linéarisation” de $\overline{H}$.

Notre contribution consiste à prouver les équivalences des linéarisations de $C_0(\wedge \cdot)$, $C_0(\sqcup \cdot)$, $C(\wedge \cdot, P_V)$, $C(\sqcup \cdot, P_V)$, $\overline{H}(\wedge \cdot)$, et $\overline{H}(\sqcup \cdot)$; où $C(\cdot, P_V)$ est le débit optimal du problème de codage canal zéro-erreur où l’encodeur doit utiliser des mots de codes typiques par rapport à la distribution $P_V$. Par conséquent, le schéma de codage “séparé” est optimal dans le problème de codage canal zéro-erreur, si et seulement si il est optimal dans le problème de Slepian-Wolf zéro-erreur avec le même graphe caractéristique. De plus, dans chacun de ces problèmes, les optimalités des schémas de codage “séparés” respectifs pour le produit $\wedge$ et pour l’union disjointe $\sqcup$ sont équivalentes. Pour prouver cela, nous définissons les distributions atteignant la capacité d’un canal en régime zéro-erreur, et nous déterminons plusieurs résultats sur celles-ci ; cela nous permet de lier $C_0$ avec $C(\cdot, P_V)$ et $\overline{H}$. De plus, nous donnons des exemples et contre-exemples de linéarisation pour toutes ces équivalences. Tout d’abord, cela nous donne une formule à une seule lettre pour $\overline{H}$
dans des cas où elle manquait ; en particulier pour les produits de graphes parfaits, qui ne
sont pas nécessairement parfaits. Enfin, les contre-exemples développés illustrent que les
schémas de codage “séparés” ne sont pas toujours optimaux: dans le problème de Slepian-
Wolf zéro-erreur, le débit peut strictement décroître quand on compresse ensemble des
sources indépendantes.

1.3 Problèmes zéro-erreur pour le calcul de fonction

Les problèmes zéro-erreur *pour le calcul de fonction* sont une généralisation des prob-
lèmes basés sur les graphes, et font aussi usage des graphes caractéristiques. Toutefois, la
fonction à retrouver impacte aussi les outils adéquats de la théorie des graphes à utiliser.
Dans le problème illustré en Figure 6.2, le décodeur doit retrouver une fonction *f* de la
source et de son information adjacente. L'encodeur ne connaît pas les réalisations de cette
dernière, mais en observe une version déterministiquement dégradée, représentée par la
fonction *g*.

Notre première contribution est de donner une expression asymptotique pour le débit
optimal de ce problème. Notre deuxième contribution est de formuler une hypothèse que
nous appelons “information adjacente partagée deux-à-deux” qui nous permet, lorsqu’elle
est satisfaite, d’obtenir une expression à une seule lettre pour le débit optimal. Cette
hypothèse est satisfaite si chaque paire de symboles de source “partage” au moins un
symbole d’information adjacente pour tout résultat de *g*. Cette condition a des interprét-
tations en termes de théorie des graphes, car les formules à une seule lettre que nous
trouvons émanent de la structure particulière du graphe caractéristique : ce dernier est
une union disjointe de produits OU. De plus, ce résultat est d’intérêt pratique car il
couvre toutes les instances où la distribution de source est à support plein, sans aucune
hypothèse sur *f*, *g*. Enfin, nous donnons une interprétation de cette condition, en termes
de plus mauvais débit optimal dans un problème auxiliaire de Slepian-Wolf zéro-erreur.

1.4 Organisation du manuscrit

Ce manuscrit est organisé comme suit. Dans le Chapitre 3, nous détaillons la présen-
tation de chacun des problèmes étudiés et l'état de l'art pour chacun d'eux, ainsi que les
définitions utilisées dans ce manuscrit. Dans le Chapitre 4, le Chapitre 5, et le Chapitre 6,
nous présentons respectivement nos résultats pour les problèmes zéro-erreur basés sur la
correction, basés sur les graphes, et pour le calcul de fonction. Les preuves de ces résultats se trouvent respectivement en Appendice A, Appendice B, et Appendice C.
GLOSSARY

For reader's convenience we give here a table of the notations and concepts used throughout this manuscript.

<table><tr><td>N*, ℝ</td><td>set of positive integers, real numbers</td></tr><tr><td>M<sub>n,k</sub>(A)</td><td>set of matrices of size n × k with coefficients in A</td></tr><tr><td>|S|, S<sup>c</sup></td><td>cardinality, complement of the set S</td></tr><tr><td>Im</td><td>image set of a mapping</td></tr><tr><td>Ker</td><td>kernel of a matrix</td></tr><tr><td>{0, 1}<sup>*</sup></td><td>set of binary words</td></tr><tr><td>l(·)</td><td>length of a word</td></tr><tr><td>x<sup>n</sup></td><td>sequence (x<sub>1</sub>, ..., x<sub>n</sub>)</td></tr><tr><td>Δ(X)</td><td>probability distributions over X</td></tr><tr><td>P<sub>X</sub></td><td>probability distribution of the random variable X</td></tr><tr><td>supp P<sub>X</sub></td><td>support of P<sub>X</sub></td></tr><tr><td>Unif(·)</td><td>uniform distribution</td></tr><tr><td>P<sub>X,Y</sub></td><td>joint distribution of (X, Y)</td></tr><tr><td>P<sub>X|Y</sub></td><td>conditional distribution of X knowing Y</td></tr><tr><td>P<sub>X</sub> ⊗ P<sub>Y</sub></td><td>product distribution</td></tr><tr><td>· → · → ·</td><td>Markov chain</td></tr><tr><td>T<sub>x<sup>n</sup></sub></td><td>type of x<sup>n</sup> (1/n |{t ≤ n | x<sub>t</sub> = x'}|)<sub>x'∈X</sub></td></tr><tr><td>Δ<sub>n</sub>(X)</td><td>set of types of sequences from X<sup>n</sup></td></tr><tr><td>T<sub>ε</sub><sup>n</sup>(P<sub>X</sub>)</td><td>typical set {x<sup>n</sup> ∈ X<sup>n</sup> | ||T<sub>x<sup>n</sup></sub> - P<sub>X</sub>||<sub>∞</sub> ≤ ε}</td></tr><tr><td>P(·)</td><td>probability of an event</td></tr><tr><td>E[·]</td><td>expected value of a random variable</td></tr><tr><td>H(·), H(· | ·)</td><td>entropy, conditional entropy</td></tr><tr><td>I(·;·)</td><td>mutual information</td></tr><tr><td>I(·; · | ·)</td><td>conditional mutual information</td></tr></table>
<table>
  <tr>
    <td>C<sub>n</sub>, K<sub>n</sub>, N<sub>n</sub></td>
    <td>cycle, complete, empty graph with n vertices</td>
    <td></td>
  </tr>
  <tr>
    <td>&phi;<sub>e</sub>, &phi;<sub>d</sub></td>
    <td>encoding, decoding function</td>
    <td></td>
  </tr>
  <tr>
    <td>&and;</td>
    <td>AND product</td>
    <td>Definition 3.2.6</td>
  </tr>
  <tr>
    <td>&alpha;</td>
    <td>independence number</td>
    <td>Definition 3.2.7</td>
  </tr>
  <tr>
    <td>C<sub>0</sub></td>
    <td>zero-error capacity</td>
    <td>Definition 3.2.8</td>
  </tr>
  <tr>
    <td>(&#x1d4ab;, &#x1d4ac;, P<sub>V</sub>)</td>
    <td>probabilistic graph</td>
    <td>Definition 3.2.5</td>
  </tr>
  <tr>
    <td>&chi;</td>
    <td>chromatic number</td>
    <td>Definition 3.3.4</td>
  </tr>
  <tr>
    <td><span style="text-decoration: overline;">H</span></td>
    <td>complementary graph entropy</td>
    <td>Definition 3.3.6</td>
  </tr>
  <tr>
    <td>H<sub>&chi;</sub></td>
    <td>chromatic entropy</td>
    <td>Definition 3.3.8</td>
  </tr>
  <tr>
    <td>T<sub>0</sub><sup>n</sup>(Q<sub>X</sub>)</td>
    <td>type class for the type Q<sub>X</sub></td>
    <td>Definition 4.2.2</td>
  </tr>
  <tr>
    <td>T<sub>V</sub>(x<sup>n</sup>)</td>
    <td>V-shell of the sequence x<sup>n</sup></td>
    <td>Definition 4.2.2</td>
  </tr>
  <tr>
    <td>G[S]</td>
    <td>subgraph of G induced by &#x1d4ac;</td>
    <td>Definition 3.3.5</td>
  </tr>
  <tr>
    <td>C(&middot;, P<sub>V</sub>)</td>
    <td>zero-error capacity relative to P<sub>V</sub></td>
    <td>Definition 5.1.1</td>
  </tr>
  <tr>
    <td>&square;</td>
    <td>disjoint union</td>
    <td>Definition 5.1.8</td>
  </tr>
  <tr>
    <td><span style="text-decoration: overline;">G</span></td>
    <td>graph complement of G</td>
    <td>Definition 5.5.1</td>
  </tr>
  <tr>
    <td>&omega;</td>
    <td>clique number</td>
    <td>Definition 5.5.1</td>
  </tr>
  <tr>
    <td>H<sub>&kappa;</sub></td>
    <td>Körner graph entropy</td>
    <td>Definition 5.5.3</td>
  </tr>
  <tr>
    <td>&or;</td>
    <td>OR product</td>
    <td>Definition 6.3.3</td>
  </tr>
  <tr>
    <td>&asymp;</td>
    <td>isomorphic (probabilistic) graphs</td>
    <td>Definition B.2.6</td>
  </tr>
</table>

A set of words $\mathcal{W} \subseteq \{0,1\}^*$ is *prefix-free* if for all $w, w' \in \mathcal{W}$, $w$ is not a prefix of $w'$ and *vice-versa*.
INTRODUCTION

Zero-error source coding encompasses a variety of problems from information theory, where a source is compressed by an encoder with rate to be minimized, then has to be retrieved at the decoder with probability of error zero. In all the problems studied here, the source distribution is known and the decoder has access to a side information, i.e. a random variable correlated to the source that helps minimizing the rate and decoding. Studying such settings is useful in applications that require a strong guarantee on the quality of reconstruction of the source, such as remote sensing networks and distributed computing. In a zero-error source coding problem, finding a formula for the optimal rate means finding the strongest theoretic limit on all compression schemes. Furthermore, if the formula is single-letter, then it becomes easily computable. One also has the existence of an optimal zero-error compression scheme that asymptotically achieves this optimal rate. Therefore, finding single-letter expressions for optimal rates in zero-error source coding problems is our main objective in this manuscript.

The zero-error constraint differs from the vanishing-error constraint, the latter only requires the probability of error to go to zero when the block length of the code goes to infinity. In the settings where the decoder does not have a side information, it can be easily shown that the optimal rates in the vanishing error and zero-error regimes coincide. However, when imposing the zero-error constraint when the decoder has a side information, as in the settings studied here, many problems change from a statistical nature to a combinatorial one (e.g. the Slepian-Wolf setting). Therefore, the adequate tools for zero-error problems are drawn from both information theory and combinatorics; and vary from a correcting device that strengthens vanishing-error codes into zero-error ones, to zero-error codes entirely built with graph-theoretic constraints.

The combinatorial nature of zero-error problems is tied to the encoder's lack of knowl-
edge of the decoder's side information. In vanishing-error problems one can assume that
the decoder's side information sequence will be typical w.r.t. the source distribution with
high probability; even if the encoder does not have access to it. However, the zero-error
constraint makes the encoder’s uncertainty on decoder’s side information harder to be
delt with; in particular it is required to build codes that enable for a perfect reconstruc-
tion of the source for *any* realization of the decoder’s side information.

For this reason, we classify the zero-error problems studied here into three categories,
depending on what the encoder knows about the decoder’s side information and what the
decoder has to retrieve:

- The *correction-based* zero-error problems, in which the encoder has access to all side information and can simulate every decoding.

- The *graph-based* zero-error problems, in which the encoder is “less informed” about the realizations of decoder’s side information.

- The *coding for computing* zero-error problems, in which the decoder has to compute a function of the source and its side information; instead of only recovering the source.

## 2.1 Correction-based zero-error problems

The *correction-based* problems can be tackled with a correcting device that guarantees the zero-error property. It consists in using a vanishing-error codebook, simulating each decoding, and sending all the source sequences if any decoding fails. This correcting device has a negligible impact on the rate because of the low probability of error, and allows for the conversion of vanishing error coding schemes into zero-error ones. For this reason, the tools we use are typicality, random coding and parity check codes, with correcting device.

In the first problem from this class, which is depicted in Figure 4.1, side information
may be present at the decoder. In this setting, the encoder has access to a side information
but does not know whether the decoder has access to it; and the encoding is divided into
two steps. In the first step, the encoder sends information without knowing whether
side information is available at the decoder. The message sent in the first step must be
exploitable independently from the presence of the side information; furthermore, a zero-
error decoding must be done if the decoder has access to the side information. In the
second step, an information complement is sent by the encoder in the case where the
decoder has no side information, and the decoder must be able to retrieve the source
with zero-error. The two steps are modeled by two decoders and two noiseless channels.
We aim at answering the following question: what are the feasible pairs of rates for the
two encoding steps, that allow for a zero-error decoding? Our first contribution consists
in determining the feasible rate region, thanks to a coset partition of source sequences coupled with a correcting device; therefore showing that it coincides with the feasible rate region in the vanishing error regime.

The second correction-based zero-error problem is depicted in Figure 4.3 and is a generalization of the first one, in which there are two uncertainties: firstly, the encoder has access to two sources and their respective side information but does not know which one will be requested by the decoder; and secondly, the side information may be present at the decoder. The encoding is divided into three steps. In the first step, the encoder sends information without knowing which source is requested; we aim at sending the common information between the two sources, hence the “Gray-Wyner network” name for this problem. In the second step, the encoder knows which source is requested but does not know if the decoder has access to the side information; if the latter is present at the decoder, then a zero-error decoding must be done. The third step is an information complement sent by the encoder in the case where the decoder does not have the side information; and the decoder must be able to retrieve the source with zero-error. In this setting, our second contribution consists in an inner and an outer bound on the feasible rate region. For the inner bound we use the following coding scheme: auxiliary sequences are used to capture the common information between the two sources sequences, then we do a random binning on them; and the sets of source sequences are partitioned into cosets. Decoding algorithms are based on V-shells of side information sequences, and the zero-error property is ensured by a correcting device.

## 2.2 Graph-based zero-error problems

In graph-based problems, zero-error constraints are captured by a characteristic graph, and determining the optimal rate requires to solve hard graph-theoretic questions. The zero-error Slepian-Wolf problem depicted in Figure 3.4 is one of them, its optimal rate is given by the complementary graph entropy $\bar{H}$ of the characteristic graph, and finding a single-letter formula for $\bar{H}$ is an open question. However, in order to understand better the nature of the zero-error Slepian-Wolf problem, we provide new structural results that link it with other problems, such as the zero-error capacity of a channel $C_0$ (see Figure 3.2).

Our main study concerns the “linearization” problem. In the zero-error Slepian-Wolf setting, if the encoder is doing several independent compression tasks with their respective
independent side information, then the optimal rate is given by $\overline{H}(\wedge \cdot)$, i.e. $\overline{H}$ of a graph with an AND product structure. As shown by Tuncel et al. in [71], “separating” the independent tasks yields an achievability scheme, hence $\overline{H}(\wedge \cdot) \le \sum \overline{H}(\cdot)$. Another interesting case of zero-error Slepian-Wolf problem is when the encoder has a partial information $g(Y)$ on the decoder’s side information. The optimal rate is given by $\overline{H}(\sqcup \cdot)$, i.e. $\overline{H}$ of a graph with a disjoint union structure. “Separating” the source realizations w.r.t. the encoder’s side information also yields an achievability scheme, hence $\overline{H}(\sqcup P_{g(Y)} \cdot) \le \sum_z P_{g(Y)}(z)\overline{H}(\cdot)$. When equality holds in either case we say that “linearization” of $\overline{H}$ holds.

Our contribution is to prove the equivalences of linearizations between $C_0(\wedge \cdot)$, $C_0(\sqcup \cdot)$, $C(\wedge \cdot, P_V)$, $C(\sqcup \cdot, P_V)$, $\overline{H}(\wedge \cdot)$, and $\overline{H}(\sqcup \cdot)$; where $C(\cdot, P_V)$ is the optimal rate in the zero-error channel coding problem where the encoder has to use codewords that are typical w.r.t. $P_V$. Therefore, the “separated” coding scheme is optimal in the zero-error channel coding problem, if and only if it is optimal in the zero-error Slepian-Wolf setting with the same characteristic graph. Furthermore, in each of these settings, the optimalities of the respective “separated” coding strategies for the product $\wedge$ and the disjoint union $\sqcup$ are equivalent. In order to prove that, we define the zero-error capacity achieving distributions of a channel, and derive several results on them; which enables us to link $C_0$ with $C(\cdot, P_V)$ and $\overline{H}$. Furthermore, we give examples and counterexamples of linearization for all these equivalences. Firstly, this yields a single-letter formula for $\overline{H}$ in cases where it was unknown: product of perfect graphs, which are not necessarily perfect. Secondly, the counterexamples developed illustrate that the “separated” coding schemes are not always optimal: in the zero-error Slepian-Wolf setting, the rate may strictly decrease when compressing together independent sources.

## 2.3 Coding for computing zero-error problems

The coding for computing problems are a generalization of graph-based problems, and also make use of characteristic graphs. However, the function to be retrieved also impacts the adequate graph-theoretic tools to be used. In the setting depicted in Figure 6.2, the decoder has to retrieve a function $f$ of its side information and of the source; the encoder does not know the realizations of the decoder’s side information but observes a deterministically degraded version of them, represented by the function $g$.

Our first contribution is to give an asymptotic formula for the optimal rate in this setting. Our second contribution is to formulate an hypothesis that we call “pairwise
shared side information” that allows us to derive a single-letter characterization of the
optimal rate. This hypothesis is satisfied if every pair of source symbols “share” at least
one side information symbol for all output of $g$. It has graph-theoretic interpretations, as
the single-letter formula stems from the particular structure of the characteristic graph:
a disjoint union of OR products. Moreover, this result is of practical interest as it covers
the cases where the source distribution is full-support, without any assumption on $f, g$.
Finally, we give an interpretation of this condition, in terms of the worst optimal rate in
an auxiliary zero-error Slepian-Wolf problem.

**2.4 Organization of the manuscript**

This manuscript is organized as follows. In Chapter 3 we provide a detailed presentation of all the problems studied and the definitions used in this manuscript, and we describe the state of the art for each one of them. In Chapter 4, Chapter 5, and Chapter 6, we present our results for the *correction-based*, *graph-based*, and *coding for computing* zero-error problems, respectively. The proofs of these results can be found in Appendix A, Appendix B, and Appendix C, respectively.
<figure><img src="image_3.png" /></figure>
STATE OF THE ART

In this Chapter we give a detailed presentation of the different problems studied in this
manuscript, in both zero-error and vanishing error regime. As illustrated in the following,
the zero-error and the vanishing error regimes may lead to different optimal rates in several
settings; in particular in the channel coding problem, and in the Slepian-Wolf problem.

**3.1 Source coding**

The source coding problem is one of the fundamental settings that appear in data
compression; it is introduced by Shannon in [59].

<figure><img src="image_4.png" /><figcaption>Figure 3.1 – The source coding problem.</figcaption></figure>

**Definition 3.1.1 (Source coding problem)** *The source coding problem of Figure 3.1 is described by:*

- A finite set $\mathcal{X}$, and a source distribution $P_X \in \Delta(\mathcal{X})$;

- For all $n \in \mathbb{N}^*$, $X^n$ is the random sequence of n copies of X, drawn in an i.i.d. fashion using $P_X$.

- An encoder that knows $X^n$ sends binary strings over a noiseless channel to a decoder that wants to retrieve $X^n$ without error.

A coding scheme in this setting is described by:

- A time horizon $n \in \mathbb{N}^*$, and an encoding function $\phi_e : \mathcal{X}^n \to \{0,1\}^*$ such that $\text{Im} \phi_e$ is prefix-free;

- A decoding function $\phi_d : \{0,1\}^* \to \mathcal{X}^n$;
- The rate is the average length of the codeword per source symbol, i.e. $R \doteq \frac{1}{n}\mathbb{E}[\ell \circ \phi_e(X^n)]$.

Depending whether a perfect source reconstruction is required, two different regimes can be considered.

**Definition 3.1.2 (Zero-error regime, vanishing error regime)** In the zero-error regime, the coding schemes $(n, \phi_e, \phi_d)$ must satisfy the zero-error property:

$$ \mathbb{P}(\widehat{X}^n \neq X^n) = 0, \qquad (3.1) $$

where $\widehat{X}^n = \phi_d(\phi_e(X^n))$. The objective is to find the minimal rate among all coding schemes under the zero-error constraint:

$$ R_{SC0}^* \doteq \inf_{\substack{n, \phi_e, \phi_d \\ \text{zero-error}}} \frac{1}{n} \mathbb{E}[\ell \circ \phi_e(X^n)]. \qquad (3.2) $$

In the vanishing error regime, the coding schemes $(n, \phi_e, \phi_d)$ must satisfy the $\epsilon$-error property:

$$ \mathbb{P}(\widehat{X}^n \neq X^n) \leq \epsilon, \qquad (3.3) $$

where $\widehat{X}^n = \phi_d(\phi_e(X^n))$. The objective is to find the minimal rate among all coding schemes under the $\epsilon$-error constraint, with $\epsilon \to 0$:

$$ R_{SC}^* \doteq \lim_{\epsilon \to 0} \inf_{\substack{n, \phi_e, \phi_d \\ \epsilon\text{-error}}} \frac{1}{n} \mathbb{E}[\ell \circ \phi_e(X^n)]. \qquad (3.4) $$

Determining the optimal rate means determining theoretic limit of all possible coding schemes in the source coding problem. The zero-error regime induces stronger constraints on the coding schemes than the vanishing error regime, thus leading to a higher optimal rate.

**Theorem 3.1.3 (from [59])**

$$ R_{SC}^* = H(X). \qquad (3.5) $$
**Theorem 3.1.4 (from [34])**

$$R_{SC0}^* = H(X). \qquad (3.6)$$

The optimal rate is characterized by the entropy of the information source: Theorem 3.1.3 and Theorem 3.1.4 show that the optimal rate in this setting equals $H(X)$, for both vanishing error and zero-error regimes. This stems from the fact that the optimal rate in the vanishing error regime can be achieved with a Huffman algorithm, which also satisfies the zero-error property.

Alternatively by Remark 3.1.5, a possible zero-error coding strategy consists in indexing the typical set w.r.t. $P_X$ following the approach from [59], and using the correcting device.

**Remark 3.1.5 (Correcting device)** In this setting, since the encoder knows the realizations of every random variable in the problem, it can simulate every decoding. Therefore, every coding scheme in the vanishing error regime can be turned into zero-error ones with negligible impact on the rate in the following way: the encoder uses the coding scheme in the vanishing error regime, along with a bit of error. The latter equals 0 in case no decoding error occurs and 1 if any decoding error happens, and all source sequences are sent to the decoder in that case. The correcting device has a negligible additional cost on the rate, due to the negligible cost of the flag bit and the low probability of error of a coding scheme in the vanishing error regime. As a consequence, both optimal rates of this problem in the vanishing error and in the zero-error regime are equal.

## 3.2 Channel coding

The channel coding problem is introduced in [59] in the vanishing error regime; and in [58] in the zero-error regime. It is a well-known example where the respective optimal rates in these regimes are different. In particular, a full-support distribution $P_{Y|X}$ for the channel may yield a positive channel capacity (i.e. optimal rate) in the vanishing error regime, and a zero-error capacity equal to 0.

<figure><img src="image_5.png" /><figcaption>Figure 3.2 – The channel coding problem.</figcaption></figure>
**Definition 3.2.1 (Channel coding problem)** *The channel coding problem of Figure 3.2 is described by:*

- Two finite sets $\mathcal{X}, \mathcal{Y}$;

- A Discrete Memoryless Channel (DMC) with input alphabet $\mathcal{X}$, output alphabet $\mathcal{Y}$ and transition probability $P_{Y|X} \in \Delta(\mathcal{Y})^{|\mathcal{X}|}$;

- An encoder that sends inputs over the DMC, and a decoder that receives the DMC's outputs.

A coding scheme in this setting is described by:

- A time horizon $n \in \mathbb{N}^*$, and a codebook $\mathcal{C}_n \subseteq \mathcal{X}^n$;

- A decoding function $\phi_d: \mathcal{Y}^n \to \mathcal{X}^n$;

- The rate is the average number of messages transmitted per channel use, i.e. $\frac{1}{n} \log |\mathcal{C}_n|$.

The channel coding problem is formally defined for two different regimes, depending whether a positive probability of error is allowed when communicating through the DMC.

**Definition 3.2.2 (Zero-error regime, vanishing error regime)** *In the zero-error regime, the coding scheme $(n, \mathcal{C}_n, \phi_d)$ must satisfy the zero-error property:*

$$ \mathbb{P}(\widehat{X}^n \neq X^n) = 0; \qquad (3.7) $$

where $X^n \sim \text{Unif}(\mathcal{C}_n)$, $\widehat{X}^n = \phi_d(Y^n)$, and $Y^n$ is drawn conditionally w.r.t. $X^n$ using $P_{Y|X}^n$. The objective is to find the maximal rate among all coding schemes that satisfy the zero-error property:

$$ R_{C0}^* \doteq \sup_{\substack{n, \mathcal{C}_n, \phi_d \\ \text{zero-error}}} \frac{1}{n} \log |\mathcal{C}_n|. \qquad (3.8) $$

In the vanishing error regime, the coding schemes $(n, \mathcal{C}_n, \phi_d)$ must satisfy the $\epsilon$-error property:

$$ \mathbb{P}(\widehat{X}^n \neq X^n) \leq \epsilon, \qquad (3.9) $$

where $X^n \sim \text{Unif}(\mathcal{C}_n)$, $\widehat{X}^n = \phi_d(Y^n)$, and $Y^n$ is drawn conditionally w.r.t. $X^n$ using $P_{Y|X}^n$. The objective is to find the maximal rate among all coding schemes that satisfy the $\epsilon$-error property:
property, with $\epsilon \to 0$:

$$R_C^* = \lim_{\epsilon \to 0} \sup_{\substack{n, \mathcal{C}_n, \phi_d \\ \epsilon\text{-error}}} \frac{1}{n} \log |\mathcal{C}_n|. \quad (3.10)$$

### 3.2.1 Channel coding in the vanishing error regime

The channel capacity in the vanishing error regime is defined by $\max_{P_X \in \Delta(\mathcal{X})} I(X;Y)$; and as shown by Shannon in Theorem 3.2.3, this quantity characterizes the optimal rate of communication over a DMC in the vanishing error regime. This comes from the fact that for all $P_X \in \Delta(\mathcal{X})$, the encoder may choose $2^{nI(X;Y)}$ random codewords from $\mathcal{X}^n$ by using $P_X$, and expect a correct decoding with high probability by typicality arguments. Taking the maximum over $P_X$ yields the highest achievable rate.

**Theorem 3.2.3 (from [59])**

$$R_C^* = \max_{P_X \in \Delta(\mathcal{X})} I(X;Y). \quad (3.11)$$

### 3.2.2 Zero-error channel coding

In the zero-error regime, an adequate graph $G_C$ can be associated to a given instance of channel coding problem in Figure 3.2. This graph is called “characteristic graph” of the problem, as it encompasses the problem data in its structure: the vertices are the source alphabet, and two channel input symbols $x, x'$ are adjacent if they are “confusable”, i.e. $P_{Y|X}(y|x)P_{Y|X}(y|x') > 0$ for some channel output symbol $y$. In other words, when $x$ and $x'$ are adjacent, knowing the realization $y$ does not allow to distinguish between the realizations $x$ and $x'$ with probability of error 0.

**Definition 3.2.4 (Characteristic graph)** Let $\mathcal{X}, \mathcal{Y}$ be two finite sets and $P_{Y|X}$ be a conditional distribution from $\Delta(\mathcal{Y})^{|X|}$. The characteristic graph associated to $P_{Y|X}$ is defined by:

- $\mathcal{X}$ as set of vertices,

- $x, x' \in \mathcal{X}$ are adjacent if $P_{Y|X}(y|x)P_{Y|X}(y|x') > 0$ for some $y \in \mathcal{Y}$.

The AND product $\wedge$ is a binary operator on graphs, and is used to build the characteristic graph for more than one channel use. More precisely, two sequences of channel
inputs $x^n, x'^n$ are adjacent in the n-th AND power $G_C^{\wedge n}$ (i.e. iterated AND product of $G_C$) if $P_{Y|X}^n(y^n|x^n)P_{Y|X}^n(y^n|x'^n) > 0$ for some sequence of channel outputs $y^n$.

In Definition 3.2.6, the AND product of graphs with an underlying distribution is defined, as it will be useful for the zero-error source coding problem. In the case of zero-error channel coding, graphs without distribution are considered, but the structure of the AND product is the same regardless of the distribution. The AND product is also called “strong product” or “normal product” in the literature (for example in [44, 47]).

**Definition 3.2.5 (Probabilistic graph)** A probabilistic graph $G$ is a tuple $(\mathcal{V}, \mathcal{E}, P_V)$, where $\mathcal{V}$ and $\mathcal{E}$ are respectively the sets of vertices and edges; and $P_V \in \Delta(\mathcal{V})$ is a probability distribution on the vertices.

**Definition 3.2.6 (AND product ∧)** Let $G_1 = (\mathcal{V}_1, \mathcal{E}_1, P_{V_1})$, $G_2 = (\mathcal{V}_2, \mathcal{E}_2, P_{V_2})$ be two probabilistic graphs, their AND product $G_1 \wedge G_2$ is a probabilistic graph defined by:

- $\mathcal{V}_1 \times \mathcal{V}_2$ as set of vertices,

- $P_{V_1} \otimes P_{V_2}$ as probability distribution on the vertices,

- $(v_1v_2), (v'_1v'_2)$ are adjacent if

$$v_1v'_1 \in \mathcal{E}_1 \text{ AND } v_2v'_2 \in \mathcal{E}_2, \qquad (3.12)$$

with the convention of self-adjacency for all vertices.

We denote by $G_1^{\wedge n}$ the n-th AND power:

$$G_1^{\wedge n} = G_1 \wedge \dots \wedge G_1 \quad (n \text{ times}). \qquad (3.13)$$

The AND product of graphs without probability distribution has the vertex set and edges defined above, without underlying probability distribution.

If there is a pair of codewords $x^n, x'^n$ adjacent in $G_C^{\wedge n}$ in the codebook used by the encoder, then upon receiving the $y^n$ such that $P_{X|Y}^n(x^n|y^n)P_{X|Y}^n(x'^n|y^n) > 0$, the decoder is unable to determine whether the encoder sent $x^n$ or $x'^n$, which prevents zero-error decoding. Therefore, a zero-error decoding at the end of the time horizon $n$ is possible if and only if the encoder uses a codebook formed of pairwise non-adjacent symbols in $G_C^{\wedge n}$, i.e. an independent set, which is formally defined below.
**Definition 3.2.7 (Independent subset, independence number $\alpha$)** Let $G = (\mathcal{V}, \mathcal{E})$ be a graph. A subset $S \subseteq \mathcal{V}$ is independent in $G$ if $xx' \notin \mathcal{E}$ for all $x, x' \in S$. The independence number is the maximal size of an independent set in $G$, and is denoted by $\alpha(G)$.

**Definition 3.2.8 (Zero-error capacity of a graph $C_0$)** Let $G$ be a graph, its zero-error capacity is defined by

$$C_0(G) \doteq \lim_{n \to \infty} \frac{1}{n} \log \alpha(G^{\wedge n}). \qquad (3.14)$$

By construction, the optimal rate for a coding scheme with the zero-error property and time horizon $n$ is $\frac{1}{n} \log \alpha(G_C^{\wedge n})$. As shown in Proposition 3.2.9, the asymptotic optimal rate is $\lim_{n \to \infty} \frac{1}{n} \log \alpha(G_C^{\wedge n})$; this quantity is called the zero-error capacity of a channel (or the zero-error capacity of its characteristic graph), and represents the best zero-error communication rate through a DMC.

Note that, by convention, we define the zero-error capacity with the logarithm. Another existing convention (for example in [44]) for the zero-error capacity is $\Theta(G) \doteq \lim_{n \to \infty} \sqrt[n]{\alpha(G^{\wedge n})}$; which is equivalent in the sense that $C_0 = \log \Theta$.

**Theorem 3.2.9 (from [58])** The optimal rate in the zero-error channel coding setting writes

$$R_{C_0}^* = C_0(G_C), \qquad (3.15)$$

where $G_C$ is the characteristic graph associated to the distribution $P_{Y|X}$.

Determining a single-letter expression for $C_0$ is a wide open problem. We present in Section 5.5 some examples from the literature where $C_0$ is known, in particular perfect graphs. The Lovász $\theta$ function, introduced in [44], is an upper bound on the zero-error capacity. This function is used to show that $C_0(C_5) = \frac{\log 5}{2}$, which makes $C_5$ the minimally non-perfect graph for which $C_0$ is known. Further observations on the $\theta$ function are derived by Sason in [54]. The zero-error capacity of $C_7$ is still unknown. Several existing lower bounds on $C_0(C_7)$ result from an independent set found by a computer program; in particular by Vesel and Žerovnik in [72], by Mathew and Östergård in [48], and by Polak and Schrijver in [51].
<figure><img src="image_6.png" /><figcaption>Figure 3.3 – The cycle graphs $C_5$, $C_7$.</figcaption></figure>

### 3.2.3 Related works

The computability of $C_0$ is investigated in [9] by Boche and Deppe, and they prove that $C_0$ is not computable. An asymptotic expression for $C_0$ using semiring homomorphisms is given by Zuiddam et al. in [78]. In [31], Gu and Shayevitz study the two-way channel case. An extension of $C_0$ for secure communication is developed in [74] by Wiese et al.

Another related setting is zero-error transmission over a discrete channel with memory. The case of binary channels with one memory is studied by Ahlswede et al. in [1], followed by Cohen et al. in [17], and the remaining unsolved cases are solved by Cao et al. in [12]. The case of binary channels with two memories is studied by Zhang et al. in [77].

Finally, the Sperner capacity is an extension of the zero-error capacity to digraphs introduced in [28] by Gargano et al. Upper bounds on the Sperner capacity are developed by Alon in [3] based on the maximum outdegree of the digraph; and by Körner et al. in [40] based on an adaptation to digraphs of the local chromatic number.

The interested reader may refer to Körner and Orlitsky's survey in [38], and Simonyi's survey in [63].

## 3.3 Slepian-Wolf problem

The Slepian-Wolf problem is introduced in [64] by Slepian and Wolf, in the vanishing error regime; and the zero-error variant of this problem is presented by Alon and Orlitsky, in [5]. This problem corresponds to a situation in data compression where the decoder has a side-information $Y$ about the source $X$ that has to be retrieved. Its optimal rate in the zero-error regime is given by the complementary graph entropy $\bar{H}$ of the characteristic graph, and finding a single-letter formula for $\bar{H}$ is an open question. As presented in Theorem 3.3.7 and Theorem 3.3.3, the respective optimal rates in the zero-error regime and in the vanishing error regime are different, in particular when the source distribution is full-support. Note that the correcting device described in Remark 3.1.5 cannot be used here for the zero-error regime, as the encoder does not know the realizations of $Y$.
<figure><img src="image_7.png" /><figcaption>Figure 3.4 – The zero-error Slepian-Wolf problem.</figcaption></figure>

**Definition 3.3.1 (Zero-error Slepian-Wolf problem)** *The zero-error source coding problem of Figure 3.4 is described by:*

- Two finite sets $\mathcal{X}, \mathcal{Y}$, and a source distribution $P_{X,Y} \in \Delta(\mathcal{X} \times \mathcal{Y})$;

- For all $n \in \mathbb{N}^*$, $(X^n, Y^n)$ is the random sequence of $n$ copies of $(X, Y)$, drawn in an i.i.d. fashion using $P_{X,Y}$.

- An encoder that knows $X^n$ sends binary strings over a noiseless channel to a decoder that knows $Y^n$, and that wants to retrieve $X^n$ without error.

A coding scheme in this setting is described by:

- A time horizon $n \in \mathbb{N}^*$, and an encoding function $\phi_e : \mathcal{X}^n \to \{0,1\}^*$ such that $\mathrm{Im} \, \phi_e$ is prefix-free;

- A decoding function $\phi_d : \mathcal{Y}^n \times \{0,1\}^* \to \mathcal{X}^n$;

- The rate is the average length of the codeword per source symbol, i.e. $R \doteq \frac{1}{n}\mathbb{E}[\ell \circ \phi_e(X^n)]$.

**Definition 3.3.2 (Zero-error regime, vanishing error regime)** *In the zero-error regime, the coding schemes $(n, \phi_e, \phi_d)$ must satisfy the zero-error property:*

$$ \mathbb{P}(\hat{X}^n \neq X^n) = 0, \qquad (3.16) $$

where $\hat{X}^n = \phi_d(Y^n, \phi_e(X^n))$. The objective is to find the minimal rate among all coding schemes under the zero-error constraint:

$$ R_{SW0}^* \doteq \inf_{\substack{n, \phi_e, \phi_d \\ \text{zero-error}}} \frac{1}{n} \mathbb{E}[\ell \circ \phi_e(X^n)]. \qquad (3.17) $$

In the vanishing error regime, the coding schemes $(n, \phi_e, \phi_d)$ must satisfy the $\epsilon$-error property:

$$ \mathbb{P}(\hat{X}^n \neq X^n) \leq \epsilon, \qquad (3.18) $$
where $\hat{X}^n = \phi_d(Y^n, \phi_e(X^n))$. The objective is to find the minimal rate among all coding schemes under the $\epsilon$-error constraint, with $\epsilon \to 0$:

$$R_{SW}^* = \lim_{\epsilon \to 0} \inf_{\substack{n, \phi_e, \phi_d \\ \epsilon\text{-error}}} \frac{1}{n} \mathbb{E}[\ell \circ \phi_e(X^n)]. \quad (3.19)$$

**Theorem 3.3.3 (from [64])** The optimal rate in the Slepian-Wolf setting in the vanishing error regime writes

$$R_{SW}^* = H(X|Y). \quad (3.20)$$

In the vanishing error regime, the optimal rate $H(X|Y)$ in Theorem 3.3.3 remains the same if the encoder also observes the sequence $Y^n$.

### 3.3.1 Zero-error Slepian-Wolf problem

In a similar way to zero-error channel coding, the characteristic graph $G_{SW}$ of an instance of zero-error Slepian-Wolf problem in Figure 3.4 is defined in Definition 3.2.4, with the conditional source distribution $P_{Y|X}$. This graph was first used by Witsenhausen in [75]. However in the zero-error Slepian-Wolf setting it is a probabilistic graph, as it has the underlying distribution $P_X$ on its vertices.

Assume that $\phi_e(x^n) = \phi_e(x'^n)$ for some $x^n, x'^n$ adjacent in $G_{SW}^{\wedge n}$, then upon receiving the $y^n$ such that $P_{X|Y}^{\wedge n}(x^n|y^n)P_{X|Y}^{\wedge n}(x'^n|y^n) > 0$, the decoder is unable to determine whether the encoder sent $x^n$ or $x'^n$, which prevents zero-error decoding. Therefore, the source sequences that are adjacent in the characteristic graph must be mapped to different codewords; hence the use of graph colorings, which map adjacent vertices to different colors.

**Definition 3.3.4 (Coloring, chromatic number $\chi$)** Let $G = (\mathcal{V}, \mathcal{E})$ be a graph. A mapping $c: \mathcal{V} \to \mathcal{C}$ is a coloring if $c^{-1}(i)$ is independent for all $i \in \mathcal{C}$. The chromatic number $\chi(G)$ is the smallest $|\mathcal{C}|$ such that there exists a coloring $c: \mathcal{V} \to \mathcal{C}$ of $G$.

**Definition 3.3.5 (Induced subgraph $G[S]$)** Let $G = (\mathcal{V}, \mathcal{E})$ be a graph, and let $S \subseteq \mathcal{V}$ be a subset of vertices. The subgraph of $G$ induced by $S$ is the graph denoted by $G[S]$ with $S$ as set of vertices, and $vv'$ are adjacent in $G[S]$ if and only if they are adjacent in $G$.

In the case where $G$ is a probabilistic graph with underlying distribution $P_V$, we give $G[S]$ the normalized underlying distribution $P_V/P_V(S)$.
With high probability, the source sequence $X^n$ will be typical w.r.t. $P_X$, therefore one can consider only the subgraph of $G_{SW}^{\wedge n}$ induced by the set of typical sequences $\mathcal{T}_{\epsilon}^n(P_X)$. Then the encoder colors this induced subgraph $G_{SW}^{\wedge n}[\mathcal{T}_{\epsilon}^n(P_X)]$ with a coloring that has the minimum number of colors, and sends the color index to the decoder if $X^n$ is typical, or the index of $X^n$ in $\mathcal{X}^n$ otherwise. This coding strategy has a rate upper-bounded by

$$ \frac{1}{n} + \mathbb{P}(X^n \notin \mathcal{T}_{\epsilon}^n(P_X)) \log |\mathcal{X}| + \frac{1}{n} \log \chi(G_{SW}^{\wedge n}[\mathcal{T}_{\epsilon}^n(P_X)]); \quad (3.21) $$

where $\chi$ is the chromatic number and the decoder is able to retrieve $X^n$ thanks to the color and $Y^n$. Koulgi et al. have shown in [41, Theorem 1] that taking the limit when $n$ goes to infinity and $\epsilon$ goes to 0 yields the best achievable rate in the zero-error Slepian Wolf problem. This quantity is called complementary graph entropy, and is defined by Körner and Longo in [37].

**Definition 3.3.6 (Complementary graph entropy $\overline{H}$)** For all probabilistic graph $G = (\mathcal{V}, \mathcal{E}, P_V)$, the quantity $\overline{H}(G)$ is defined by:

$$ \overline{H}(G) = \lim_{\epsilon \to 0} \limsup_{n \to \infty} \frac{1}{n} \log \chi(G^{\wedge n}[\mathcal{T}_{\epsilon}^n(P_V)]). \quad (3.22) $$

**Theorem 3.3.7 (from [41, Theorem 1])** The optimal rate in the zero-error Slepian-Wolf setting writes

$$ R_{SW0}^* = \overline{H}(G_{SW}), \quad (3.23) $$

where $G_{SW}$ is the probabilistic graph formed of the characteristic graph associated to the distribution $P_{Y|X}$, with the underlying distribution $P_X$ on its vertices.

The zero-error Slepian Wolf setting that we study is called “restricted inputs” by Alon and Orlitsky in [5] where they give another characterization of the optimal rate with chromatic entropies. The chromatic entropy $H_{\chi}(G_{SW}^{\wedge n})$ corresponds to the minimal entropy of a coloring of $G_{SW}^{\wedge n}$. Therefore, after normalization, it characterizes the best rate at a fixed number $n$ of source uses with a perfect compression of the color. As stated in Theorem 3.3.9, by taking the limit when $n$ goes to infinity, one obtains the optimal rate; and also, another expression for $\overline{H}$.

A stronger notion of zero-error coding, called “unrestricted inputs”, is also introduced in [5]. It requires the zero-error property to be satisfied even for the sequences of symbols
$(X^n, Y^n)$ that take values out of the support of $P_{X,Y}^n$. Alon and Orlitsky provide in [5], a single-letter formula for the optimal rate.

**Definition 3.3.8 (Chromatic entropy $H_\chi$)** Let $G = (\mathcal{V}, \mathcal{E}, P_V)$ be a probabilistic graph, its chromatic entropy is defined by

$$H_{\chi}(G) = \inf\{H(c(V)) \mid c \text{ is a coloring of } G\}. \qquad (3.24)$$

**Theorem 3.3.9 (from [5, Lemma 6])** For all probabilistic graph $G$,

$$R_{SW0}^* = \lim_{n \to \infty} \frac{1}{n} H_{\chi}(G_{SW}^{\wedge n}). \qquad (3.25)$$

The two distinct asymptotic expressions are equal to the optimal rate.

$$R_{SW0}^* = \lim_{\epsilon \to 0} \limsup_{n \to \infty} \frac{1}{n} \log \chi(G^{\wedge n}[\mathcal{T}_{\epsilon}^n(P_V)]) = \lim_{n \to \infty} \frac{1}{n} H_{\chi}(G_{SW}^{\wedge n}). \qquad (3.26)$$

**Proposition 3.3.10 (Full support)** If the distribution $P_{X,Y}$ has full support, then $R_{SW0}^* = H(X)$.

The case of $P_{X,Y}$ with full support is a worst case for the zero-error regime, for which the optimal rate is $H(X)$, instead of $H(X|Y)$ in the vanishing error regime.

There is no known single letter expression for the optimal rate $R_{SW0}^*$ except for a few special cases; in particular for perfect graphs and $(C_5, \text{Unif}(\{1, \dots, 5\}))$.
# CONTRIBUTIONS FOR CORRECTION-BASED ZERO-ERROR PROBLEMS

In Section 4.1, we present the source coding problems considered in this chapter. We call these problems “correction-based” as they can be tackled with a correcting device which gives the zero-error property to coding schemes designed for the vanishing error regime. As a result, for this class of problems, the optimal rate in the zero-error regime coincides with the optimal rate in the vanishing error regime.

We determine in Section 4.2 the feasible rate region of the zero-error source coding problem when side information may be present at the decoder, presented in Section 4.1.1. In Section 4.3 we give an inner and an outer bound on the feasible rate region of the zero-error source coding problem for a Gray-Wyner network, presented in Section 4.1.3. We show that these bounds coincide in several cases of interest.

## 4.1 Correction-based zero-error problems

### 4.1.1 Zero-error source coding when side information may be present at the decoder

This scenario arises in interactive compression, where the user can randomly access part of the data directly in the compressed domain. A source sequence $X^n$ models the smallest entity that can be requested, for instance a file of a database, a frame of a video, or a block of an omnidirectional image [8, 49, 53].

In this setting, the encoder has access to a side information but does not know whether the decoder has access to it; and the encoding is divided into two steps. In the first step, the encoder sends information without knowing whether side information is available at
the decoder. The message sent in the first step must be exploitable independently from the presence of the side information; furthermore, a zero-error decoding must be done if the decoder has access to the side information. In the second step, an information complement is sent by the encoder in the case where the decoder has no side information, and the decoder must be able to retrieve the source with zero-error. The two steps are modeled by two decoders and two noiseless channels.

<figure><img src="image_8.png" /><figcaption>Figure 4.1 – Source coding when side information may be present.</figcaption></figure>

**Definition 4.1.1** The setting of Figure 4.1 is described by:

- Two finite sets $\mathcal{X}, \mathcal{Y}$, and a source distribution $P_{X,Y} \in \Delta(\mathcal{X} \times \mathcal{Y})$;

- For all $n \in \mathbb{N}^*$, $(X^n, Y^n)$ is the random sequence of n copies of $(X, Y)$, drawn in an i.i.d. fashion using $P_{X,Y}$.

- An encoder that knows $(X^n, Y^n)$ sends binary strings over two noiseless channels to two decoders that want to retrieve $X^n$ without error. Decoder 1 has $Y^n$ as side information.

A coding scheme in this setting is described by:

- A time horizon $n \in \mathbb{N}^*$,

- Two encoding functions and two decoding functions

$$ \phi_e^{(1)} : \mathcal{X}^n \times \mathcal{Y}^n \to \{0,1\}^*, \quad \phi_e^{(2)} : \mathcal{X}^n \times \mathcal{Y}^n \to \{0,1\}^*, \qquad (4.1) $$

$$ \phi_d^{(1)} : \{0,1\}^* \times \mathcal{Y}^n \to \mathcal{X}^n, \quad \phi_d^{(2)} : (\{0,1\}^*)^2 \to \mathcal{X}^n, \qquad (4.2) $$

such that Im $\phi_e^{(1)}$ and Im $\phi_e^{(2)}$ are prefix-free;

- The rates over each channel are the average length of the codeword per source symbol:

$$ R_1 \doteq \frac{1}{n} \mathbb{E}[\ell \circ \phi_e^{(1)}(X^n, Y^n)] \quad R_2 \doteq \frac{1}{n} \mathbb{E}[\ell \circ \phi_e^{(2)}(X^n, Y^n)]; \qquad (4.3) $$
- $n, \phi_e^{(1)}, \phi_e^{(2)}, \phi_d^{(1)}, \phi_d^{(2)}$ must satisfy the zero-error property:

$$ \mathbb{P}(\hat{X}_1^n \neq X^n) = \mathbb{P}(\hat{X}_2^n \neq X^n) = 0; \qquad (4.4) $$

where

$$ \hat{X}_1^n = \phi_d^{(1)}(\phi_e^{(1)}(X^n, Y^n), Y^n), \qquad (4.5) $$

$$ \hat{X}_2^n = \phi_d^{(2)}(\phi_e^{(1)}(X^n, Y^n), \phi_e^{(2)}(X^n, Y^n)). \qquad (4.6) $$

The objective is to find the feasible rate region $\mathcal{R}_{SI}$, which is the closure of the set

$$ \{(R_1, R_2) \in \mathbb{R}^2 \mid \exists (n, \phi_e^{(1)}, \phi_e^{(2)}, \phi_d^{(1)}, \phi_d^{(2)}) \text{ zero-error, with rates } (R_1, R_2)\}. \qquad (4.7) $$

A way to achieve zero-error coding in the setting of Figure 4.1 is to use conditional Huffman coding of $X$ knowing $Y$; and send the source $X$ to decoder 1 at rate $R_1 = H(X|Y)$. Then, to recover the source $X$, decoder 2 needs to obtain the side information $Y$, which requires a rate of $R_2 = H(Y) \ge I(X;Y)$.

In order to be exploitable by both decoders, part of the information sent through the common channel must be independent from $Y$. For this reason the setting of Figure 4.1 is closely related to the Slepian and Wolf (SW) problem in [64], seen as lossless source coding with side information at the decoder only. In this work, it is shown that the corner point $(R_1, R_2) = (H(X|Y), I(X;Y))$ is achievable in the vanishing probability of error regime. In [19], Csiszar proved in that linear codes achieve the optimal SW rate region. Several works in [13, 14, 73] investigate the duality between SW setting and channel coding using linear codes, as the side information $Y$ can be seen as the output of a virtual channel with input $X$. However these tools cannot be straightforwardly adapted to the zero-error setting, as the linear codes proposed also present a vanishing probability of error.

The setting of Figure 4.1 can be seen as a zero-error variant with side informations known at the encoder of the successive refinement problem proposed by Kaspi in [35]; later generalized by Timo et al. in [67] for more than two decoders. Even if the lossy reconstruction of the source makes it fundamentally different from the zero-error setting, there are notable examples that present the same tools as in SW. The side information scalable source coding (i.e. the decoder 2 has a side information $Y'$ s.t. $X \to Y \to Y'$) in [66] for instance uses nested random binning. This random binning approach was further developed in [2] to give a unified coding scheme that works for both scalable source coding
and Wyner-Ziv successive refinement in [65] (i.e. the decoder 2 has a side information $Y'$ s.t. $X \rightarrow Y' \rightarrow Y$).

In [45], Ma and Cheng use linear codes in a zero-error SW restriction, under symmetry assumptions on the source. However, a zero-error SW coding scheme in our setting does not use at all the side information knowledge at the encoder. A more in-depth review of the literature for the zero-error SW setting can be found in Section 3.3.1.

In Section 4.2, we characterize the feasible rate region. More precisely, we show that the pair of rates $(R_1, R_2) = (H(X|Y), I(X;Y))$ is achievable in the zero-error regime and moreover, it is the corner-point of the feasible rate region.

### 4.1.2 Gray-Wyner problem

The problem built by Gray and Wyner in [30], aims at capturing the common information between two random variables $X$ and $Y$.

<figure><img src="image_9.png" /><figcaption>Figure 4.2 – The Gray-Wyner source coding problem.</figcaption></figure>

**Definition 4.1.2** The setting of Figure 4.2 is described by:

- Two finite sets $\mathcal{X}, \mathcal{Y}$, and a source distribution $P_{X,Y} \in \Delta(\mathcal{X} \times \mathcal{Y})$;

- For all $n \in \mathbb{N}^*$, $(X^n, Y^n)$ is the random sequence of $n$ copies of $(X, Y)$, drawn in an i.i.d. fashion using $P_{X,Y}$.

- An encoder that knows $(X^n, Y^n)$ sends binary strings over three noiseless channels to the decoder $\times$ (resp. $\times$) that wants to retrieve $X^n$ (resp. $Y^n$) without error.

A coding scheme in this setting is described by:

- A time horizon $n \in \mathbb{N}^*$,
- Three encoding functions and two decoding functions

$$ \phi_e^{(0)}, \phi_e^{(x)}, \phi_e^{(y)} : \mathcal{X}^n \times \mathcal{Y}^n \to \{0, 1\}^*, \qquad (4.8) $$

$$ \phi_d^{(x)} : (\{0, 1\}^*)^2 \to \mathcal{X}^n, \qquad (4.9) $$

$$ \phi_d^{(y)} : (\{0, 1\}^*)^2 \to \mathcal{Y}^n, \qquad (4.10) $$

such that $\mathrm{Im} \phi_e^{(i)}$ is prefix-free for all $i \in \{0, x, y\}$;

- The rates over each channel are the average length of the codeword per source symbol:

$$ R_i \doteq \frac{1}{n} \mathbb{E}[\ell \circ \phi_e^{(i)}(X^n, Y^n)] \qquad (4.11) $$

for all $i \in \{0, x, y\}$;

- $n, (\phi_e^{(i)})_{i \in \{0, x, y\}}, (\phi_d^{(j)})_{j \in \{x, y\}}$ must satisfy the $\epsilon$-error property:

$$ \mathbb{P}(\widehat{X}^n \neq X^n) \leq \epsilon \qquad (4.12) $$

$$ \mathbb{P}(\widehat{Y}^n \neq Y^n) \leq \epsilon; \qquad (4.13) $$

where

$$ \widehat{X}^n = \phi_d^{(x)}(\phi_e^{(0)}(X^n, Y^n), \phi_e^{(x)}(X^n, Y^n)), \qquad (4.14) $$

$$ \widehat{Y}^n = \phi_d^{(y)}(\phi_e^{(0)}(X^n, Y^n), \phi_e^{(y)}(X^n, Y^n)). \qquad (4.15) $$

The objective is to find the feasible rate region $\mathcal{R}$, which is the closure of the set

$$ \bigcap_{\epsilon>0} \left\{ (R_0, R_x, R_y) \in \mathbb{R}^3 \mid \exists n, (\phi_e^{(i)})_{i \in \{0, x, y\}}, (\phi_d^{(j)})_{j \in \{x, y\}} \text{ } \epsilon\text{-error, with rates } (R_0, R_x, R_y) \right\}. \qquad (4.16) $$

In [30], Gray and Wyner have determined the feasible rate region in the vanishing error regime, as illustrated in Theorem 4.1.3.
**Theorem 4.1.3** The feasible rate region is the closure of the following set:

$$ \bigcup_{W \text{ finite set,} \atop P_{W|X,Y} \in \Delta(W) |X||Y|} \left\{ (R_0, R_X, R_Y) \in \mathbb{R}^3 \middle| \begin{array}{l} R_0 \ge I(W; X, Y), R_X \ge H(X|W), R_Y \ge H(Y|W) \end{array} \right\}. \qquad (4.17) $$

Following the same idea as in Remark 3.1.5, this region is also the feasible rate region in the zero-error regime (i.e. $\mathbb{P}(\hat{X}^n \neq X^n) = \mathbb{P}(\hat{Y}^n \neq Y^n) = 0$).

### 4.1.3 Zero-error source coding for a Gray-Wyner network when side information may be present at the decoder

The following setting is an extension of both problems presented in Section 4.1.2 and Section 4.1.1, in which there are two uncertainties: firstly, the encoder has access to two sources and their respective side information but does not know which one will be requested by the decoder; and secondly, the side information may be present at the decoder. The encoding is divided into three steps. In the first step, the encoder sends information without knowing which source is requested; we aim at sending the common information between the two sources, hence the “Gray-Wyner network” name for this problem. In the second step, the encoder knows which source is requested but does not know if the decoder has access to the side information; if the latter is present at the decoder, then a zero-error decoding must be done. The third step is an information complement sent by the encoder in the case where the decoder does not have the side information; and the decoder must be able to retrieve the source with zero-error.

**Definition 4.1.4** The setting of Figure 4.3 is described by:

- Four finite sets $U, V, X, Y$, and a source distribution $P_{U,V,X,Y} \in \Delta(U \times V \times X \times Y)$;

- For all $n \in \mathbb{N}^*$, $(U^n, V^n, X^n, Y^n)$ is the random sequence of n copies of $(U, V, X, Y)$, drawn in an i.i.d. fashion using $P_{U,V,X,Y}$.

- An encoder that knows $(U^n, V^n, X^n, Y^n)$ sends binary strings over four noiseless channels to three decoders that want to retrieve $X^n$ or $Y^n$ without error. Decoder $x_1$ (resp. $y$) has $U^n$ (resp. $V^n$) as side information.

A coding scheme in this setting is described by:

- A time horizon $n \in \mathbb{N}^*$,
<figure><img src="image_10.png" /><figcaption>Figure 4.3 – Zero-error source coding for a Gray-Wyner network when side information may be present.</figcaption></figure>

- Four encoding functions and three decoding functions

$$ \phi_e^{(0)}, \phi_e^{(x_1)}, \phi_e^{(x_2)}, \phi_e^{(y)} : \mathcal{U}^n \times \mathcal{V}^n \times \mathcal{X}^n \times \mathcal{Y}^n \to \{0, 1\}^*, \quad (4.18) $$

$$ \phi_d^{(x_1)} : (\{0, 1\}^*)^2 \times \mathcal{U}^n \to \mathcal{X}^n, \quad \phi_d^{(x_2)} : (\{0, 1\}^*)^3 \to \mathcal{X}^n, \quad (4.19) $$

$$ \phi_d^{(y)} : (\{0, 1\}^*)^2 \times \mathcal{V}^n \to \mathcal{Y}^n, \quad (4.20) $$

such that $\mathrm{Im} \phi_e^{(i)}$ is prefix-free for all $i \in \{0, x_1, x_2, y\}$;

- The rates over each channel are the average length of the codeword per source symbol:

$$ R_i \doteq \frac{1}{n} \mathbb{E}[\ell \circ \phi_e^{(i)}(U^n, V^n, X^n, Y^n)] \quad (4.21) $$

for all $i \in \{0, x_1, x_2, y\}$;

- $n, (\phi_e^{(i)})_{i \in \{0, x_1, x_2, y\}}, (\phi_d^{(j)})_{j \in \{x_1, x_2, y\}}$ must satisfy the zero-error property:

$$ \mathbb{P}(\widehat{X}_1^n \neq X^n) = \mathbb{P}(\widehat{X}_2^n \neq X^n) = \mathbb{P}(\widehat{Y}^n \neq Y^n) = 0; \quad (4.22) $$

where

$$ \widehat{X}_1^n = \phi_d^{(1)}(\phi_e^{(0)}(S^n), \phi_e^{(x_1)}(S^n), U^n), \quad (4.23) $$

$$ \widehat{X}_2^n = \phi_d^{(2)}(\phi_e^{(0)}(S^n), \phi_e^{(x_1)}(S^n), \phi_e^{(x_2)}(S^n)), \quad (4.24) $$

$$ \widehat{Y}^n = \phi_d^{(y)}(\phi_e^{(0)}(S^n), \phi_e^{(y)}(S^n), V^n), \quad (4.25) $$
and $S^n = (U^n, V^n, X^n, Y^n)$.

The objective is to find the feasible rate region $\mathcal{R}_{GW}$, which is the closure of the set

$$ \left\{ (R_0, R_{x_1}, R_{x_2}, R_y) \in \mathbb{R}^4 \mid \right. \tag{4.26} $$

$$ \exists n, (\phi_e^{(i)})_{i \in \{0, x_1, x_2, y\}}, (\phi_d^{(j)})_{j \in \{x_1, x_2, y\}} \text{ zero-error, with rates } (R_0, R_{x_1}, R_{x_2}, R_y) \right\}. \tag{4.27} $$

This scenario can be likened to zero-error source coding problems with side information at the decoders, but not at the encoder. In such problems, the encoder has partial or no knowledge of the side information, and zero-error and vanishing error constraints do not lead to the same rate, in general. The zero-error constraint leads to the use of graph theoretical concepts for the characterization of the optimal rate. Witsenhausen first studied in [75] whether Slepian and Wolf's results can be extended to the zero-error case, using the chromatic number of the characteristic graph of the source distribution. In [62], Simonyi studied the generalization to more than one decoder with different side information, and proved that the optimal rate is the one associated to the worst side information (in the sense of Witsenhausen). Tuncel and Rose later extended this result to variable-length codes in [70]. A more in-depth review of the literature for the zero-error Slepian-Wolf setting can be found in Section 3.3.1.

A second class is the zero-error source coding problems with an encoder that has access to all side information, and decoders have access to the different side information. In these problems, the characterization of the optimal rates can be done using a packing lemma in type classes and the following correcting argument: the source sequence can be fully transmitted to each decoder whenever a decoding fails. This correcting argument allows for the extension of lossless results into zero-error results with same rates. A particular case of Sgarro's problem in [57] when side information are fully transmitted by the helpers can be extended to the zero-error case when the side information is also available at the encoder. In Section 4.2, we characterize the feasible rate region of a problem in this class presented in Section 4.1.1, where conditional coding does not achieve optimal rates.

Finally, the setting of Figure 4.3 is closely related to several problems in the literature, with different side information at the decoders and different desired source random variable, which have been studied under a vanishing error hypothesis. A covering lemma in type classes can be used to characterize the optimal rates in such problems, for example the lossless Gray and Wyner's (GW) problem [30]. In [68], Timo et al. study the GW setting with side information at the decoders only and give an inner bound on the
feasible rate region. In [7], Benammar and Zaidi consider a lossy GW setting with side information at the decoders only and with an hypothesis on the variables requested at the decoders. Laich and Wigger study in [43] the influence of the side information at the encoder in the lossless Kaspi/Heegard-Berger problem. They show that, for some source distributions, adding side information at the encoder lowers the minimal required rate to decode without loss.

In Section 4.3 we give an inner bound and an outer bound on the feasible rate region of the setting in Figure 4.3.

## 4.2 Main results for the zero-error source coding problem when side information may be present at the decoder

We now determine the feasible rate region of the zero-error source coding problem when side information may be present at the decoder, presented in Section 4.1.1

**Theorem 4.2.1**

$$ \mathcal{R}_{SI} = \{ (R_1, R_2) \in \mathbb{R}^2 \mid R_1 \ge H(X|Y), R_1 + R_2 \ge H(X) \}. \quad (4.28) $$

<figure><img src="image_11.png" /><figcaption>Figure 4.4 – Zero-error achievable rate region $\mathcal{R}_{SI}$.</figcaption></figure>
Proof. [Converse of Theorem 4.2.1] In this setting, each decoder must retrieve X with zero-error. Using Shannon lossless source coding result [18, Theorem 5.3.1], we have $R_1 + R_2 \ge H(X)$.

Now let us prove $R_1 \ge H(X|Y)$

Let $M_0 \doteq \phi_e^{(1)}(S^n)$, where $S^n = (S_1, ..., S_n)$ is sequence of n iid copies of the source random variables $(X, Y)$. Let $R_0 = \frac{1}{n}\mathbb{E}[\ell \circ \phi_e^{(1)}(S^n)]$.

Firstly, we can use Kraft inequality as the set $\text{Im} \phi_e^{(1)}$ is prefix-free, we have

$$ \sum_{w \in \text{Im} \phi_e^{(1)}} 2^{-\ell(w)} \le 1. \qquad (4.29) $$

Let $\kappa \doteq \sum_{w \in \text{Im} \phi_e^{(1)}} 2^{-\ell(w)}$, we have $\kappa \le 1$ and $(\frac{2^{-\ell(w)}}{\kappa})_{w \in \text{Im} \phi_e^{(1)}}$ is a probability distribution.

Secondly,

$$ nR_0 = \mathbb{E}[\ell \circ \phi_e^{(1)}(S^n)] \qquad (4.30) $$

$$ = \sum_{w \in \text{Im} \phi_e} \mathbb{P}(\phi_e^{(1)}(S^n) = w) \ell(w) \qquad (4.31) $$

$$ = - \sum_{w \in \text{Im} \phi_e} \mathbb{P}(\phi_e^{(1)}(S^n) = w) \log 2^{-\ell(w)} \qquad (4.32) $$

$$ = - \log \kappa - \sum_{w \in \text{Im} \phi_e^{(1)}} \mathbb{P}(\phi_e^{(1)}(S^n) = w) \log \frac{2^{-\ell(w)}}{\kappa} \qquad (4.33) $$

$$ \geq - \sum_{w \in \text{Im} \phi_e} \mathbb{P}(\phi_e^{(1)}(S^n) = w) \log \frac{2^{-\ell(w)}}{\kappa} \qquad (4.34) $$

$$ \geq - \sum_{w \in \text{Im} \phi_e} \mathbb{P}(\phi_e^{(1)}(S^n) = w) \log \mathbb{P}(\phi_e^{(1)}(S^n) = w) \qquad (4.35) $$

$$ = H(\phi_e^{(1)}(S^n)) = H(M_0) \qquad (4.36) $$

where (4.34) and (4.35) respectively come from $\kappa \le 1$ and Gibbs inequality.
Therefore,

$$nR_0 \geq H(M_0) \qquad (4.37)$$

$$\geq H(M_0|Y^n) \qquad (4.38)$$

$$= H(M_0, Y^n) - H(Y^n) \qquad (4.39)$$

$$= H(X^n, Y^n) - H(Y^n) \qquad (4.40)$$

$$= nH(X|Y), \qquad (4.41)$$

where (4.40) comes from the zero-error property. □

Our achievability result relies on a random coding argument. We use Csiszar and Körner's method of types [20, Chapter 2] in order to calibrate a linear code which is used to partition the set of source sequences. The encoder sends the coset of the source sequence to all decoders and the index of the source sequence in its coset to decoder 2. We show that the zero-error property is satisfied and the corresponding rates converge to the pair of target rates $(H(X|Y), I(X;Y))$.

In order to prove Theorem 4.2.1, we show that

$$(H(X|Y), I(X;Y)) \in \mathcal{R}_{SI}. \qquad (4.42)$$

In order to complete the achievability result we use a time sharing with the point $(H(X), 0)$, which is known to be achievable by compressing $X$ using a Huffman code and sending the resulting binary sequence via $\phi_e^{(1)}$.

## 4.2.1 Definitions for the achievability proof

**Definition 4.2.2 (Type class, V-shell)** Let $Q_{X,Y} \in \Delta_n(\mathcal{X} \times \mathcal{Y})$, its type class is the set $\mathcal{T}_0^n(Q_{X,Y}) = \{(x^n, y^n) \in \mathcal{X}^n \times \mathcal{Y}^n | T_{x^n, y^n} = Q_{X,Y}\}$. The $Q_{X|Y}$-shell of a sequence $y^n \in \mathcal{Y}^n$ is the set $\mathcal{T}_{Q_{X|Y}}(y^n) = \{x^n \in \mathcal{X}^n | T_{x^n, y^n} = Q_{X,Y}\}$.

**Definition 4.2.3 (Generator/parity matrix, syndrome, coset)** Let $\mathcal{A}$ be a finite set such that $|\mathcal{A}|$ is prime, so we can give $\mathcal{A} \simeq \mathbb{Z}/|\mathcal{A}|\mathbb{Z}$ a field structure. For all $n, k \in \mathbb{N}^*$, we denote by $\mathcal{M}_{n,k}(\mathcal{A})$ the set of $n \times k$ matrices over the finite field $\mathcal{A}$.

Let $k \in \mathbb{N}^*$, a generator matrix is a matrix $\mathbf{G} \in \mathcal{M}_{n,k}(\mathcal{A})$. An associated parity matrix is a matrix $\mathbf{H} \in \mathcal{M}_{n-k,n}(\mathcal{A})$ such that $\mathrm{Im} \, \mathbf{G} = \mathrm{Ker} \, \mathbf{H}$, where $\mathrm{Im}$ and $\mathrm{Ker}$ denote the image and the kernel, respectively.
<figure><img src="image_12.png" /><figcaption>Figure 4.5 – An illustration of type classes and $Q_{X|Y}$-shells. Edges correspond to jointly typical sequences with $\epsilon = 0$, i.e. $T_{x^n, y^n} = Q_{X,Y}$. At most $2^{nI(X;Y)+o(n)}$ disjoint $Q_{X,Y}$-shells can be packed in $\mathcal{T}_0^n(Q_X)$, as $\frac{|\mathcal{T}_0^n(Q_Y)|}{|\mathcal{T}_{Q_{X|Y}}(y^n)|} = \frac{2^{nH(X)+o(n)}}{2^{nH(X|Y)+o(n)}} = 2^{nI(X;Y)+o(n)}$.</figcaption></figure>

The syndrome of a sequence $a^n \in \mathcal{A}^n$ is $\mathbf{H}a^n$. The coset associated to the syndrome $\mathbf{H}a^n$ is the set $\mathrm{Im} \, \mathbf{G} + a^n = \{a'^n \in \mathcal{A}^n \mid \mathbf{H}a'^n = \mathbf{H}a^n\}$.

### 4.2.2 Coding scheme

For all $n \in \mathbb{N}^*$, we show the existence of a sequence of $(n, R_1^{(n)}, R_2^{(n)})$-zero-error source codes that achieves the corner-point $(H(X|Y), I(X;Y))$ of the zero-error rate region $\mathcal{R}_{SI}$. Our proof is based on a linear code adjusted depending on the random type $T_{X^n, Y^n}$, and coset partitioning of the Hamming space.

We assume w.l.o.g. that $P_{X,Y} \neq P_X \otimes P_Y$. We also assume w.l.o.g. that $|\mathcal{X}|$ is prime number by padding (i.e. extending with zeros) $P_{X,Y}$ if necessary. We fix the block-length $n$ and a constant parameter $\delta \in (0; \log |\mathcal{X}| - H(X|Y))$ that will represent a rate penalty.

- Random code generation: For each pair of sequences $(x^n, y^n)$, we define the parameter

$$k \doteq \left[ n - n \frac{H(T_{x^n, y^n}) - H(T_{y^n}) + \delta}{\log |\mathcal{X}|} \right]^+. \quad (4.43)$$

where $[\cdot]$ denotes the ceiling function and $(\cdot)^+$ denotes $\max(\cdot, 0)$. We denote by $K$ the random variable induced by $k$ defined in (4.43), for the random sequences $(X^n, Y^n)$. A generator matrix $\mathbf{G} \in \mathcal{M}_{n,n}(\mathcal{X})$ is randomly drawn, with i.i.d. entries drawn according to the uniform distribution on $\mathcal{X}$. If $k \neq 0$, let $\mathbf{G}_k$ be the matrix obtained by extracting the $k$ first lines of $\mathbf{G}$, and $\mathbf{H}_k$ a parity matrix associated to $\mathbf{G}_k$.

The random code $\mathcal{C}$ consists of the set of random matrices $\mathcal{C} = (\mathbf{G}_k, \mathbf{H}_k)_{k \le n}$. Before the transmission starts, a code realization is chosen and revealed to the encoder and both decoders.
- Encoding function $\phi_e^{(1)}$: Let $E \in \{0, 1\}$ be such that $E = 0$ if $K \neq 0$ and $(\operatorname{Im} \mathbf{G}_K + X^n) \cap \mathcal{T}_{T_{X^n|Y^n}}(Y^n) = \{X^n\}$, $E = 1$ otherwise; where $T_{X^n|Y^n}$ is the conditional distribution obtained from $T_{X^n,Y^n}$. Then we define

$$ \phi_e^{(1)}(X^n, Y^n) = \begin{cases} b(T_{X^n,Y^n}, E, \mathbf{H}_K X^n) & \text{if } E = 0, \\ b(T_{X^n,Y^n}, E, X^n) & \text{if } E = 1, \end{cases} \quad (4.44) $$

where $b(\cdot)$ denotes the binary expansion.

- Encoding function $\phi_e^{(2)}$: If $E = 0$, the index of $X^n$ in its coset $\operatorname{Im} \mathbf{G}_K + X^n$ is compressed using a Huffman code with the distribution $P_{X^n}$. Let $\iota(\mathbf{G}_K, X^n, Y^n)$ be the resulting binary sequence, then we set

$$ \phi_e^{(2)}(X^n, Y^n) = \iota(\mathbf{G}_K, X^n, Y^n). \quad (4.45) $$

Otherwise, $\phi_e^{(2)}(X^n, Y^n) = 0$.

- Decoding function $\phi_d^{(1)}$: It observes $\phi_e^{(1)}(X^n, Y^n)$ and extracts $E$ and $T_{X^n,Y^n}$. If $E = 1$,

$$ \phi_d^{(1)}(\phi_e^{(1)}(X^n, Y^n), Y^n) = X^n. \quad (4.46) $$

Otherwise $E = 0$, it extracts $\mathbf{H}_K X^n$ and determines the coset $\operatorname{Im} \mathbf{G}_K + X^n$. Moreover, by using $T_{X^n,Y^n}$ and $Y^n$ it determines the $T_{X^n|Y^n}$-shell $\mathcal{T}_{T_{X^n|Y^n}}(Y^n)$, and therefore returns an element

$$ \phi_d^{(1)}(\phi_e^{(1)}(X^n, Y^n), Y^n) \in (\operatorname{Im} \mathbf{G}_K + X^n) \cap \mathcal{T}_{T_{X^n|Y^n}}(Y^n). $$

- Decoding function $\phi_d^{(2)}$: It observes $\phi_e^{(1)}(X^n, Y^n)$ and extracts $E$ and $T_{X^n,Y^n}$. If $E = 0$, it extracts $\mathbf{H}_K X^n$ and determines the coset $\operatorname{Im} \mathbf{G}_K + X^n$, and it returns $\phi_d^{(2)}(\phi_e^{(1)}(X^n, Y^n), \phi_e^{(2)}(X^n, Y^n))$, the element of $\operatorname{Im} \mathbf{G}_K + X^n$ with index $\phi_e^{(2)}(X^n, Y^n)$. If $E = 1$, it returns

$$ \phi_d^{(2)}(\phi_e^{(1)}(X^n, Y^n), \phi_e^{(2)}(X^n, Y^n)) = X^n. $$

**Remark 4.2.4** The parameter $K$ is selected so that when $K > 0$, the number of parity bits of the linear code asymptotically matches the conditional entropy.
### 4.2.3 Zero-error property and rate analysis

We now prove that the code built in Section 4.2.2 satisfies the zero-error property. It is clear that both decoders retrieve $X^n$ with zero-error when $E = 1$.

If $E = 0$, then by definition of $E$ we have $(\mathrm{Im} \mathbf{G}_K + X^n) \cap \mathcal{T}_{T_{X^n|Y^n}}(Y^n) = \{X^n\}$, hence $\phi_d^{(1)}(\phi_e^{(1)}(X^n, Y^n), Y^n) = X^n$ with probability 1. On the other hand, $\phi_e^{(2)}(X^n, Y^n) = \iota(\mathbf{G}_K, X^n, Y^n)$, so the element of $\mathrm{Im} \mathbf{G}_K + X^n$ with index $\phi_e^{(2)}(X^n, Y^n)$ is $X^n$. Thus, $\phi_d^{(2)}(\phi_e^{(1)}(X^n, Y^n), \phi_e^{(2)}(X^n, Y^n)) = X^n$ with probability 1.

**Lemma 4.2.5 (Rate analysis)** For all parameter $\delta > 0$, the sequence of rates of the codes built in Section 4.2.2 satisfy

$$R_1^{(n)} \rightarrow H(X|Y) + \delta, \quad R_2^{(n)} \rightarrow I(X;Y). \qquad (4.47)$$

The proof can be found in Appendix A.1.

## 4.3 Main results for the zero-error source coding problem for a Gray-Wyner network when side information may be present at the decoder

We first give an inner bound on the feasible rate region in Theorem 4.3.1, based on the following coding strategy. For all realization $(x^n, y^n)$ of the source, an auxiliary sequence $w^n$ is used to capture the common information between the source sequences, and the sets of possible sequences $x^n$ and $y^n$ are partitioned into cosets. As the side information is available at some decoders, random binning is done so that less information is transmitted on $w^n$ through the common channel. Decoding algorithms are based on V-shells of side information sequences, and the zero-error property is ensured by an error bit that is accompanied by all source sequences if set to 1. We also give an outer bound on the feasible rate region in Theorem 4.3.2, and we show in Section 4.3.1 that the inner and outer bound coincide in several cases of interest.
**Theorem 4.3.1 (Inner bound)** The rate tuples $(R_0, R_{x_1}, R_{x_2}, R_y)$ that satisfy

$$R_0 \geq I(U, V, X, Y; W) - \min(I(U; W), I(V; W)), \qquad (4.48)$$

$$R_{x_1} \geq H(X|U, W), \qquad (4.49)$$

$$R_{x_2} \geq I(X; U|W) + \min(I(U; W), I(V; W)), \qquad (4.50)$$

$$R_y \geq H(Y|V, W), \qquad (4.51)$$

for some finite set $\mathcal{W}$ and distribution $P_{U,V,W,X,Y} = P_{U,V,X,Y}P_{W|U,V,X,Y}$ are achievable.

**Theorem 4.3.2 (Outer bound)** The rate tuples $(R_0, R_{x_1}, R_{x_2}, R_y)$ that are achievable must satisfy

$$R_0 \geq I(X, Y; W|U, V), \qquad (4.52)$$

$$R_{x_1} \geq H(X|U, W), \qquad (4.53)$$

$$R_y \geq H(Y|V, W), \qquad (4.54)$$

$$R_0 + R_{x_1} + R_{x_2} \geq H(X), \qquad (4.55)$$

for some finite set $\mathcal{W}$ and distribution $P_{U,V,W,X,Y} = P_{U,V,X,Y}P_{W|U,V,X,Y}$.

The proofs of Theorem 4.3.1 and Theorem 4.3.2 are respectively given in Appendix A.2 and in Appendix A.3. These proofs are based on the following Lemma 4.3.3 and Lemma 4.3.5. Lemma 4.3.3 is a covering/packing lemma for type classes. It is different from the packing lemma in [20, Lemma 10.1], as the latter states the existence of a family of codewords that satisfy the packing property, instead of drawing them at random following a given distribution.

**Lemma 4.3.3 (Covering/Packing lemma in type classes)** Let $k \in \mathbb{N}^*$, $P_{A,B} \in \Delta_k(\mathcal{A} \times \mathcal{B})$, $P_{\bar{A}} \in \Delta(\mathcal{A})$, and

$$R_c \doteq I(A; B) + D(P_A \| P_{\bar{A}}). \qquad (4.56)$$

Let $R > 0$ such that $R \neq R_c$. For all $n \in k\mathbb{N}^*$, let $C^{(n)} \doteq (\bar{A}_{[1]}^n, \dots, \bar{A}_{[2^nR]}^n)$ be a codebook of random sequences, drawn with a joint distribution that satisfies the marginal condition $\bar{A}_{[i]}^n \sim P_{\bar{A}}^{\otimes n}$ for all $i \in \{1, \dots, 2^nR\}$.
- If $R < R_c$, then we have for all $b^n \in \mathcal{T}_0^n(P_B)$:

$$ \mathbb{P}(\exists a^n \in \mathcal{C}^{(n)}, T_{a^n, b^n} = P_{A,B}) \le 2^{-n(R_c-R)+o(n)}. \quad (4.57) $$

- If $R > R_c$, assuming that the sequences in $\mathcal{C}^{(n)}$ are iid, we have for all $b^n \in \mathcal{T}_0^n(P_B)$:

$$ \begin{aligned} & \mathbb{P}(\exists a^n \in \mathcal{C}^{(n)}, \text{ s.t. } T_{a^n, b^n} = P_{A,B}) \tag{4.58} \\ & = 1 - \exp \left[ -2^{n(R-R_c)+o(n)} \right]. \end{aligned} $$

The proof of Lemma 4.3.3 can be found in Appendix A.4.

**Remark 4.3.4** For $P_{\tilde{A}} = P_A$, we have $R_c = I(A; B)$. For $P_{\tilde{A}} = \text{Unif}(\mathcal{X})$, we have $R_c = \log |\mathcal{A}| - H(A|B)$.

**Lemma 4.3.5 (Coset partition)** Assume that $|\mathcal{A}|$ is prime. Let $k \in \mathbb{N}$, $P_{A,B} \in \Delta_k(\mathcal{A} \times \mathcal{B})$, $R_c = \log |\mathcal{A}| - H(A|B)$ and $R < R_c$ such that $kR/\log |\mathcal{A}| \in \mathbb{N}$. For all $n \in \mathbb{N}$, let $\mathbf{G}^{(n)} \in \mathcal{M}_{n,nR/\log|\mathcal{X}|}(\mathcal{A})$ be a generator matrix whose entries are iid random variables drawn with the distribution $\text{Unif}(\mathcal{A})$. Then we have for all $(a^n, b^n) \in \mathcal{T}_0^n(P_{A,B})$:

$$ \mathbb{P}(\exists \tilde{a}^n \in \text{Im} \mathbf{G}^{(n)} + a^n \setminus \{a^n\}, T_{\tilde{a}^n, b^n} = P_{A,B}) \le 2^{-n(R_c-R)+o(n)}. \quad (4.59) $$

*Proof.* For all $a^n$, we have by construction that the coset $\text{Ker} \mathbf{H}^{(n)} + a^n \setminus \{a^n\}$ is formed of $|\mathcal{A}|^{nR/\log|\mathcal{X}|} - 1 = 2^{nR} - 1$ random codewords, which are pairwise independent and identically distributed: they follow the distribution $\text{Unif}(\mathcal{A})^{\otimes n}$. The result follows from Lemma 4.3.3. $\square$

### 4.3.1 Comparison with previous results

In this section, we derive the zero-error achievable rate region for several special cases, in which our inner bound is optimal.

First, consider the zero-error variant of Gray-Wyner problem [30] by setting $U$ and $V$ constant, and removing the decoder $\chi_2$. Our inner bound allows to derive the zero-error rate achievable region for this problem:

$$ R_0 \ge I(X, Y; W), \qquad R_{\chi_1} \ge H(X|W), \quad (4.60) $$

$$ R_y \ge H(Y|W), \qquad R_{\chi_2} \ge 0, \quad (4.61) $$
for some distribution $P_{U,V,W,X,Y} = P_{U,V,X,Y}P_{W|U,V,X,Y}$. Due to the converse from [30, Theorem 4], this bound is optimal.

Another scheme of interest is when $Y$ and $V$ are constant, which gives the problem presented in Section 4.1.1. We obtain the following

$$ \begin{array}{ll} \text{Inner bound:} & \text{Outer bound:} \\ R_0 \ge I(X; W|U), & R_0 \ge I(X; W|U), \qquad (4.62) \\ R_{x_1} \ge H(X|U, W), & R_{x_1} \ge H(X|U, W), \qquad (4.63) \\ R_{x_2} \ge I(U; X, W), & R_0 + R_{x_1} + R_{x_2} \ge H(X), \qquad (4.64) \\ R_y \ge 0, & R_y \ge 0, \qquad (4.65) \end{array} $$

for some distribution $P_{U,V,W,X,Y} = P_{U,V,X,Y}P_{W|U,V,X,Y}$. By choosing $W$ constant (resp. $W = X$) we retrieve the achievability of the tuple $(R_0, R_{x_1}, R_{x_2}, R_y) = (0, H(X|U), I(U; X), 0)$ (resp. $(H(X|U), 0, I(U; X), 0)$). It proves that the bound is optimal as the outer bound gives $R_0 + R_{x_1} \ge H(X|U)$ and $R_0 + R_{x_1} + R_{x_2} \ge H(X)$.

We obtain the problem of Timo et al. [68] by removing the side information at the encoder, and removing the decoder $x_2$. Then the possible distributions $P_{U,V,W,X,Y}$ must satisfy the Markov chain $(U, V) \to (X, Y) \to W$, and we obtain the same inner bound as them:

$$ \begin{array}{ll} R_0 \ge \max(I(X, Y; W|U), I(X, Y; W|V)), & (4.66) \\ R_{x_1} \ge H(X|U, W), & (4.67) \\ R_{x_2} \ge 0, & (4.68) \\ R_y \ge H(Y|V, W), & (4.69) \end{array} $$

for some distribution $P_{U,V,W,X,Y} = P_{U,V,X,Y}P_{W|X,Y}$.
<figure><img src="image_13.png" /></figure>
CONTRIBUTIONS FOR GRAPH-BASED
ZERO-ERROR PROBLEMS

In the zero-error problems that we call “graph-based”, zero-error constraints are cap-
tured by a characteristic graph, and determining the optimal rate requires to solve hard
graph-theoretic questions. For instance, the zero-error Slepian-Wolf problem presented in
Section 3.3.1 is one of them, its optimal rate is given by the complementary graph entropy
$\overline{H}$ of the characteristic graph, and finding a single-letter formula for $\overline{H}$ is an open ques-
tion. However, in order to understand better the nature of the zero-error Slepian-Wolf
problem, we provide new structural results that link it with other problems, such as the
zero-error capacity of a channel $C_0$ (see Figure 3.2).

Our approach for these structural results is the following. If the encoder is doing several
independent compression tasks with their respective independent side information, then
the optimal rate is given by $\overline{H}(\wedge \cdot)$, i.e. $\overline{H}$ of a graph with an AND product structure. As
shown by Tuncel et al. in [71], “separating” the independent tasks yields an achievability
scheme, hence $\overline{H}(\wedge \cdot) \le \sum \overline{H}(\cdot)$. An important question is to determine whether this
equation is satisfied with equality. When equality holds we say that “linearization” of
$\overline{H}(\wedge \cdot)$ holds. Similarly, we define the linearization of optimal zero-error capacities $C(\cdot, P_V)$
and $C_0$. Although, linearization always holds in the vanishing error regime, it does not
hold anymore in the zero-error regime.

Another interesting case of zero-error Slepian-Wolf problem is when the encoder has
a partial information $g(Y)$ on the decoder’s side information. The optimal rate is given
by $\overline{H}(\sqcup \cdot)$, i.e. $\overline{H}$ of a graph with a disjoint union structure. “Separating” the source
realizations w.r.t. the encoder’s side information also yields an achievability scheme, hence
$\overline{H}(\sqcup P_{g(Y)} \cdot) \le \sum_z P_{g(Y)}(z) \overline{H}(\cdot)$. Similarly, we question the “linearization” of $\overline{H}(\sqcup P_{g(Y)} \cdot)$.

In this Chapter, we show the equivalences of the linearizations of the optimal source
and channel zero-error rates $\overline{H}$, $C(\cdot, P_V)$ and $C_0$, when considering the AND product
and the disjoint union of graphs, as depicted in Figure 5.1. More details are given about
existing results in Section 5.1, where we also present formally the linearization problems. The equivalence of linearizations between $\overline{H}$ and $C(\cdot, P_V)$ is proved in Section 5.2. In order to link the linearizations of $C_0$ and $C(\cdot, P_V)$, it is necessary to study the capacity-achieving distributions of a graph; the results needed are given in Section 5.3. In Section 5.4 we show the equivalence of linearizations between $C_0$ and $C(\cdot, P_V)$. In Section 5.5 we develop examples and counterexamples of linearization for $C_0$, $C(\cdot, P_V)$ and $\overline{H}$. The linearization problems and the zero-error channel coding problem with typical input constraint are formally presented in Section 5.1. The proofs of all results in this Chapter can be found in Appendix B.

<figure><img src="image_14.png" /><figcaption>Figure 5.1 – Equivalences of linearizations between the zero-error capacity $C_0(\cdot)$, the zero-error capacity relative to a distribution $C(\cdot, P_V)$, and the complementary graph entropy $\overline{H}(\cdot)$. Our results are represented in the dashed rectangles.</figcaption></figure>

# 5.1 Graph-based zero-error problems

## 5.1.1 Zero-error channel coding with typical input constraint

In the channel coding problem in the vanishing error regime, $I(X;Y)$ is the best rate one can achieve with codebooks formed of typical codewords w.r.t. $P_X$; and the channel capacity is the maximum of $I(X;Y)$ taken over $P_X$.

Similarly, we can think of a more constrained version of the zero-error channel coding problem, where the channel inputs have to be typical w.r.t. some distribution. The zero-error capacity of a graph relative to a distribution $C(\cdot, P_V)$ was introduced by Csiszar and Körner in [21].
**Definition 5.1.1 (Zero-error capacity of a graph relative to $P_V$)** The zero-error capacity of a graph $G = (\mathcal{V}, \mathcal{E})$ relative to $P_V \in \Delta(\mathcal{V})$ is defined by

$$C(G, P_V) = \lim_{\epsilon \to 0} \limsup_{n \to \infty} \frac{1}{n} \log \alpha(G^{\wedge n}[T_{\epsilon}^{n}(P_V)]). \quad (5.1)$$

**Remark 5.1.2** We show in Lemma B.3.1 that the superior limit when $n \to \infty$ in the definition of $C(\cdot, P_V)$ can be replaced with a regular limit, thanks to the superadditivity of the sequence $(\frac{1}{n} \log \alpha(G^{\wedge n}[T_{\epsilon}^{n}(P_V)])_{n \in \mathbb{N}^{*}}$.

We show in Lemma 5.1.3 that $C(\cdot, P_V)$ characterizes the optimal rate in the zero-error channel coding problem with typical inputs. We use this alternative characterization of $C(\cdot, P_V)$ to prove several other results, in particular for capacity achieving distributions. We define capacity achieving distributions in Section 5.3, and derive several results on them.

**Lemma 5.1.3** Let $G = (\mathcal{V}, \mathcal{E})$ be a graph and $P_V \in \Delta(\mathcal{V})$. Then there exists a sequence $(C_n)_{n \in \mathbb{N}^*}$ such that

$$\forall n \in \mathbb{N}^*, C_n \subseteq \mathcal{V}^n \text{ is an independent set in } G^{\wedge n}, \quad (5.2)$$

$$\max_{v^n \in C_n} \|T_{v^n} - P_V\|_{\infty} \xrightarrow{n \to \infty} 0, \quad (5.3)$$

$$\frac{\log |C_n|}{n} \xrightarrow{n \to \infty} C(G, P_V). \quad (5.4)$$

Furthermore, any sequence $(C_n)_{n \in \mathbb{N}^*}$ that satisfies (5.2) and (5.3) also satisfies

$$\limsup_{n \to \infty} \frac{\log |C_n|}{n} \le C(G, P_V). \quad (5.5)$$

The proof of Lemma 5.1.3 is developed in Appendix B.3.1. Theorem 5.1.4 from Si-monyi's survey [63, Theorem 20] states that $C_0$ is equal to the maximum of $C(\cdot, P_V)$, taken over the channel input distributions $P_V$, paralleling the channel capacity in the vanishing error regime.

**Theorem 5.1.4 (from [63, Theorem 20])** For all graph $G = (\mathcal{V}, \mathcal{E})$,

$$C_0(G) = \max_{P_V \in \Delta(\mathcal{V})} C(G, P_V). \quad (5.6)$$

Theorem 5.1.4 is obtained from [63, Theorem 20] when the family of graph has only
one element. The result of [63, Theorem 20] is proved in [29, Sec. 2] for a more general setting that involves the Sperner capacity of directed graphs. For the sake of completeness, we provide a proof for Theorem 5.1.4 in Appendix B.3.2 that does not rely on directed graphs.

The complementary graph entropy is closely related to the zero-error capacity relative to a distribution. The link between these two quantities is provided by Marton in [47, Lemma 1], see Theorem 5.1.5 below. This formula is the cornerstone of our results that extend the properties of $\overline{H}$ to $C(G, \cdot)$. As stated in Corollary 5.1.6 which makes the link between $\overline{H}$ and $C_0$, a single letter formula for $\overline{H}$ would also yield a single-letter formula for $C_0$. It is worth noting that, similarly to $C_0$, $\overline{H}$ has a known single-letter expression for perfect graphs (see Section 5.5).

**Theorem 5.1.5 (from [47, Lemma 1])** For all graph $G = (\mathcal{V}, \mathcal{E})$ and $P_V \in \Delta(\mathcal{V})$,

$$C(G, P_V) + \overline{H}(G, P_V) = H(V). \qquad (5.7)$$

**Corollary 5.1.6** For all graph $G = (\mathcal{V}, \mathcal{E})$,

$$C_0(G) = \max_{P_V \in \Delta(\mathcal{V})} \left( H(V) - \overline{H}(G, P_V) \right). \qquad (5.8)$$

We can interpret the formula in Theorem 5.1.5 the following way. The quantities $\overline{H}(G, P_V)$ and $C(G, P_V)$ are respectively the minimum number of colors, and the maximum size of an independent set. A color class (i.e. vertices of the same color) is an independent subset of vertices: in the case with same-sized color classes we would need $\log \alpha(G)$ bits to describe the source sequence in its color. Therefore, $C(G, P_V)$ can be seen as the information needed to describe the index of the source sequence in its color class. These two quantities sum up to $H(V)$, which is the information needed to describe the source sequence without loss; thus 5.1.5 can be seen as an analog for zero-error regime of the formula $I(X; Y) + H(X|Y) = H(X)$.

## 5.1.2 Linearization in the zero-error Slepian-Wolf problem

Let us consider the particular instances of zero-error Slepian-Wolf source coding depicted in Figure 5.2; where $g: \mathcal{Y} \to \mathcal{Z}$ is a deterministic function, $\mathcal{Z}$ is a finite set, and the pairs $((X_z, Y_z))_{z \in \mathcal{Z}}$ are mutually independent. They present a practical interest, as Figure 5.2a models the case where the encoder carries several independent compression
tasks with different respective distributions; and Figure 5.2b models the case where the encoder has partial information on the realizations of the decoder’s side information.

$$X_1^n, \dots, X_{|Z|}^n \rightarrow \boxed{\text{Encoder}} \xrightarrow{R} \boxed{\text{Decoder}} \rightarrow \left(\hat{X}_1^n, \dots, \hat{X}_{|Z|}^n\right) = \left(X_1^n, \dots, X_{|Z|}^n\right)$$
$$Y_1^n, \dots, Y_{|Z|}^n$$

(a) Zero-error Slepian-Wolf problem with several independent sources.

$$X^n \rightarrow \boxed{\text{Encoder}} \xrightarrow{R} \boxed{\text{Decoder}} \rightarrow \hat{X}^n = X^n$$
$$\left(g(Y_t)\right)_{t \le n}$$

(b) Zero-error Slepian-Wolf problem with side information at the encoder.

Figure 5.2 – Two particular instances of zero-error Slepian-Wolf source coding problem.

As shown in Proposition 5.1.7 and Proposition 5.1.9, in these cases the optimal rate is the complementary graph entropy of a graph with a particular structure: disjoint union $\sqcup$, and AND product $\land$ respectively. Note that the setting in Figure 5.2b is a particular case of Figure 3.4, as it is equivalent to a setting with source $(X, g(Y))$ that must be retrieved by the decoder, and side information $Y$ at the decoder; and also, Figure 3.4 is a particular case of Figure 5.2b by removing the encoder’s side information.

**Proposition 5.1.7** The optimal rate in Figure 5.2a writes

$$\overline{H}\left(\bigwedge_{z \in \mathcal{Z}} G_z\right); \qquad (5.9)$$

where for all $z \in \mathcal{Z}$, $G_z$ is the characteristic graph associated to the conditional distribution $P_{X_z|Y_z}$, with the underlying probability distribution $P_{X_z}$ on its vertices.

**Definition 5.1.8 (Disjoint union of probabilistic graphs $\sqcup$)** Let $\mathcal{A}$ be a finite set, and let $P_A \in \Delta(\mathcal{A})$. For all $a \in \mathcal{A}$, let $G_a = (\mathcal{V}_a, \mathcal{E}_a, P_{V_a})$ be probabilistic graphs, their disjoint union w.r.t. $P_A$ is a probabilistic graph $(\mathcal{V}, \mathcal{E}, P_V)$ denoted by $\sqcup_{a \in \mathcal{A}}^{P_A} G_a$ and defined by:

- $\mathcal{V} = \sqcup_{a \in \mathcal{A}} \mathcal{V}_a$ is the disjoint union of the sets $(\mathcal{V}_a)_{a \in \mathcal{A}}$;

- For all $v, v' \in \mathcal{V}$, $vv' \in \mathcal{E}$ iff they both belong to the same $\mathcal{V}_a$ and $vv' \in \mathcal{E}_a$;

- $P_V = \sum_{a \in \mathcal{A}} P_A(a)P_{V_a}$, note that the $(P_{V_a})_{a \in \mathcal{A}}$ have disjoint support in $\mathcal{V}$.
The disjoint union of graphs without probability distribution has the vertex set and edges defined above, without underlying probability distribution. Therefore we do not specify a distribution $P_A$ when considering a disjoint union of such graphs.

The disjoint union is also called “sum of graphs" in [71]. An example of disjoint union and AND product of probabilistic graphs can be found in Figure 5.3.

$$
\begin{align*}
G_1 &= \textcircled[1]{4} \quad \textcircled[1]{2} \quad \textcircled[1]{4} & G_2 &= \textcircled[1]{3} \textcircled[2]{3} \\
G_1 \wedge G_2 &= \textcircled[1]{12} \quad \textcircled[1]{6} \quad \textcircled[1]{12} & G_1 \sqcup G_2 &= \textcircled[1]{16} \quad \textcircled[1]{8} \quad \textcircled[1]{16} \\
& \textcircled[1]{6} \quad \textcircled[1]{3} \quad \textcircled[1]{6} & & \textcircled[1]{4} \textcircled[1]{2} \quad \textcircled[1]{4} \textcircled[1]{2}
\end{align*}
$$

Figure 5.3 – An empty graph $G_1 = (N_3, (\frac{1}{4}, \frac{1}{2}, \frac{1}{4}))$ and a complete graph $G_2 = (K_2, (\frac{1}{3}, \frac{2}{3}))$, along with their AND product $G_1 \wedge G_2$ and their disjoint union $G_1 \sqcup G_2$ w.r.t. $(\frac{1}{4}, \frac{3}{4})$. The underlying distributions are represented by the numbers on each vertex.

**Proposition 5.1.9** *The optimal rate in Figure 5.2b writes*

$$
\overline{H} \left( \left( \bigcap_{z \in \mathcal{Z}}^{P_{g(Y)}} G_z \right) \middle| \right); \qquad (5.10)
$$

where for all $z \in \mathcal{Z}$, $G_z$ is the characteristic graph associated to the conditional distribu-
tion $(P_{X|Y}(x,y))_{(x,y)\in X \times g^{-1}(z)}$, with the underlying probability distribution $P_{X|g(Y)=z}$ on its
vertices.

A natural coding strategy for the setting in Figure 5.2a consists in separating the problem into $|\mathcal{Z}|$ source coding sub-problems, where the random variable $X_z$ has to be transmitted to the decoder that knows $Y_z$. Concatenating the optimal coding strategies in each sub-problem yields a zero-error coding scheme for the problem in Figure 5.2a, with rate $\sum_{z \in \mathcal{Z}} \overline{H}(G_z)$.

**Definition 5.1.10** The linearization with respect to the AND product $\wedge$ of the optimal rate $\overline{H}$ is satisfied when

$$
\overline{H} \left( \bigwedge_{z \in \mathcal{Z}} G_z \right) = \sum_{z \in \mathcal{Z}} \overline{H}(G_z). \qquad (5.11)
$$
The linearization with respect to the disjoint union of graphs ⋃ of the optimal rate $\overline{H}$ is satisfied when

$$ \overline{H} \left( \bigsqcup_{z \in \mathcal{Z}}^{P_{g(Y)}} G_z \right) = \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) \overline{H}(G_z). \qquad (5.12) $$

Similarly, a natural coding strategy for the setting in Figure 5.2b consists in separating the source realizations depending on the value of $g(Y)$, and use the optimal coding scheme designed for the distribution $P_{X,Y|g(Y)=z}$ for all $z$. The associated rate is $\sum_{z \in \mathcal{Z}} P_{g(Y)}(z) \overline{H}(G_z)$. When this coding strategy is optimal, the following holds:

$$ \overline{H} \left( \bigsqcup_{z \in \mathcal{Z}}^{P_{g(Y)}} G_z \right) = \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) \overline{H}(G_z), \qquad (5.13) $$

i.e. $\overline{H}$ can be linearized w.r.t. ⋃.

These natural coding schemes are both zero-error. For this reason, inequality always holds in (5.11) and (5.13), as captured in Tuncel et al.'s formulae in Theorem 5.1.11.

**Theorem 5.1.11 (from [71, Theorem 2])** For all probabilistic graphs $G, G'$ and $s \in [0, 1]$,

$$ \overline{H}(G \wedge G') \leq \overline{H}(G) + \overline{H}(G'); \qquad (5.14) $$

$$ \overline{H}(G \bigsqcup^{(s,1-s)} G') \leq s\overline{H}(G) + (1-s)\overline{H}(G'). \qquad (5.15) $$

In the vanishing error regime, these natural approaches are always optimal. However in the zero-error regime they are not: we develop a counterexample in Theorem 5.5.13. We also show in Section 5.5 that for some classes of graphs (5.11) and (5.13) hold for all underlying distributions on the vertices. This enables us to derive a single-letter characterization of $\overline{H}$ for a new class of graphs. We will see in the following that the linearization of (5.14) is equivalent to the linearisation of (5.15).

### 5.1.3 Linearization in zero-error channel coding

In the zero-error channel coding setting, a case of interest is when encoder can use multiple independent channels to communicate with the decoder, depicted in Figure 5.4. We can think of two transmission regimes in this setting:
<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /><figcaption>Figure 5.4 – Two particular instances of zero-error channel coding problem.</figcaption></figure>

- **Product of channels**: all the channels are used by the encoder at each time step, and the decoder observes all channel outputs.

- **Sum of channels**: at each time step $t \le n$, the encoder has to use exactly one channel $z_t$ among the $|\mathcal{Z}|$ channels. The decoder observes the chosen channel index and its output, and has to retrieve the input of the chosen channel.

In the vanishing error regime, the respective optimal rates for these settings depend on the channel capacities $C_z \doteq \max_{P_{X_z} \in \Delta(\mathcal{X})} I(X_z; Y_z): \sum_{z \in \mathcal{Z}} C_z$ for the product of channels, and $\log (\sum_{z \in \mathcal{Z}} 2^{C_z})$ for the sum of channels. However, in the zero-error regime, the optimal rates for the sum and product of channels are respectively given by the zero-error capacities of a product graph and a disjoint union graph; as shown in Proposition 5.1.12 and Proposition 5.1.13.

**Proposition 5.1.12 (from [58])** The optimal rate in Figure 5.4a writes

$$C_0 \left( \bigwedge_{z \in \mathcal{Z}} G_z \right); \qquad (5.16)$$

where for all $z \in \mathcal{Z}$, $G_z$ is the characteristic graph associated to the conditional distribution $P_{X_z|Y_z}$.
**Proposition 5.1.13 (from [58]) The optimal rate in Figure 5.4b writes**

$$C_0\left(\bigcup_{z \in \mathcal{Z}} G_z\right); \qquad (5.17)$$

where for all $z \in \mathcal{Z}$, $G_z$ is the characteristic graph associated to the conditional distribution $P_{X_z|Y_z}$.

A possible zero-error coding scheme in Figure 5.4 in the product of channels consists in separately using optimal codebooks, designed respectively for each channel. The associated rate is $\sum_{z \in \mathcal{Z}} C_0(G_z)$ and satisfies

$$C_0\left(\bigwedge_{z \in \mathcal{Z}} G_z\right) \geq \sum_{z \in \mathcal{Z}} C_0(G_z). \qquad (5.18)$$

There are cases where equality holds in (5.18), i.e.

$$C_0\left(\bigwedge_{z \in \mathcal{Z}} G_z\right) = \sum_{z \in \mathcal{Z}} C_0(G_z), \qquad (5.19)$$

which we call “linearization” of $C_0$ w.r.t. $\wedge$; and cases where inequality in (5.18) is strict, for instance the Schläfli graph and its complement (see Section 5.5.2).

For the sum of channels, we can use the optimal codebooks designed for each channel, with a time-sharing w.r.t. the following distribution:

$$P_Z^* \doteq \left( \frac{2^{C_0(G_z)}}{\sum_{z' \in \mathcal{Z}} 2^{C_0(G_{z'})}} \right)_{z \in \mathcal{Z}}. \qquad (5.20)$$

The distribution $P_Z^*$ represents the optimal time-sharing between the different codebooks, as we prove in Lemma B.4.5 that $P_Z^*$ defined in (5.20) is the maximizer of the function $P_Z \mapsto H(P_Z) + \sum_{z \in \mathcal{Z}} P_Z(z)C_0(G_z)$.

The rate writes

$$H(P_Z^*) + \sum_{z \in \mathcal{Z}} P_Z^*(z)C_0(G_z) = \sum_{z \in \mathcal{Z}} P_Z^*(z) \left( \log \left( \frac{\sum_{z' \in \mathcal{Z}} 2^{C_0(G_{z'})}}{2^{C_0(G_z)}} \right) + C_0(G_z) \right) \qquad (5.21)$$

$$= \log \left( \sum_{z' \in \mathcal{Z}} 2^{C_0(G_{z'})} \right). \qquad (5.22)$$
and if this strategy is optimal, then the following holds:

$$C_0 \left( \bigsqcup_{z \in \mathcal{Z}} G_z \right) = \log \left( \sum_{z \in \mathcal{Z}} 2^{C_0(G_z)} \right), \qquad (5.23)$$

i.e. $C_0$ can be linearized w.r.t. $\sqcup$.

**Definition 5.1.14** The linearization with respect to the AND product $\wedge$ of the optimal rate $C_0$ is satisfied when

$$C_0 \left( \bigwedge_{z \in \mathcal{Z}} G_z \right) = \sum_{z \in \mathcal{Z}} C_0(G_z). \qquad (5.24)$$

The linearization with respect to the disjoint union of graphs of the optimal rate $C_0$ is satisfied when

$$C_0 \left( \bigsqcup_{z \in \mathcal{Z}} G_z \right) = \log \left( \sum_{z \in \mathcal{Z}} 2^{C_0(G_z)} \right). \qquad (5.25)$$

**Remark 5.1.15** Linearization always holds in the vanishing error regime, in the sense that the optimal coding strategy for communicating over several independent channels consists in using respective optimal codebooks for each channel. In other words,

$$\max_{P_{X_1, \dots, X_{|\mathcal{Z}|} \in \Delta(\mathcal{X}^{|\mathcal{Z}|})}} I(X_1, \dots, X_{|\mathcal{Z}|}; Y_1, \dots, Y_{|\mathcal{Z}|}) = \sum_{z \in \mathcal{Z}} \max_{P_{X_z \in \Delta(\mathcal{X})}} I(X_z; Y_z). \qquad (5.26)$$

**Remark 5.1.16** Note that $P_Z^*$ is full-support: it can be observed $P_Z \mapsto H(P_Z)$ has an infinite slope at the frontier of $\Delta(\mathcal{Z})$, consequently the maximizer of $P_Z \mapsto H(P_Z) + \sum_{z \in \mathcal{Z}} P_Z(z)C_0(G_z)$ is always an interior point. In other words, the information carried by the channel index $H(P_Z)$ offsets the loss in rate, if the channels with smaller capacities are not chosen too often. Therefore, in the sum of channels setting, always choosing the channel with highest capacity is suboptimal; and never choosing a channel is also suboptimal, even if this channel has zero-error capacity 0.

These natural coding schemes are both zero-error. For this reason, inequality always holds in (5.19) and (5.23), as captured in Shannon's formulae in Theorem 5.1.17.
**Theorem 5.1.17 (from [58, Theorem 4])** For all graphs G, G',

$$C_0(G \sqcup G') \le \log(2^{C_0(G)} + 2^{C_0(G')}); \qquad (5.27)$$

$$C_0(G \wedge G') \le C_0(G) + C_0(G'). \qquad (5.28)$$

The Schläfli graph S is a counterexample of linearization of $C_0$ used by Haemers in [33] (see [15, Section 6.1] for an explicit construction), as stated in Theorem 5.1.18. To prove this result, Haemers uses a bound on the zero-error capacity based on the rank of the adjacency matrix of the graph. Refinements of this bound are developed by Bukh and Cox in [10], and by Gao et al. in [26]. Corollary 5.1.19 follows from Schrijver's result in Theorem 5.1.20.

**Theorem 5.1.18 (from [33])** Let S be the Schläfli graph and $\bar{S}$ its complementary graph, then $C_0(S \wedge \bar{S}) > C_0(S) + C_0(\bar{S})$.

**Corollary 5.1.19** $C_0(S \sqcup \bar{S}) > \log(2^{C_0(S)} + 2^{C_0(\bar{S})})$.

In [36], Keevash and Long study the maximal value of $C_0(G \sqcup G')$ under the assumption $C_0(G), C_0(G') < \epsilon$.

As stated in Theorem 5.1.20, Schrijver has shown that the cases of equality in Theorem 5.1.17 coincide. In Section 5.2, we show the equivalence of the linearization for $\bar{H}$ and $C(\cdot, P_V)$, this requires new proof techniques. Furthermore, as we point out in Section 5.3 and Section 5.4, studying the capacity achieving distributions is necessary in order to link $C_0$ and $C(\cdot, P_V)$ and their linearizations.

**Theorem 5.1.20 (from [55, Theorem 2])** For all graphs G, G',

$$C_0(G \sqcup G') = \log(2^{C_0(G)} + 2^{C_0(G')}); \qquad (5.29)$$

$$\iff C_0(G \wedge G') = C_0(G) + C_0(G'). \qquad (5.30)$$

In Section 5.4 and Section 5.2, we show that the graphs that allow for a linearization of $C_0$, $C(\cdot, P_V)$, and $\bar{H}$ are the same, when $P_V$ is a capacity-achieving distribution.
<figure><img src="image_17.png" /><figcaption>Figure 5.5 – The 2-discretized probability simplex $\Delta_2(\mathcal{X} \times \mathcal{Y})$ for $\mathcal{X} = \mathcal{Y} = \{0,1\}$.</figcaption></figure>

## 5.2 Main results on the linearization of $\overline{H}$ and $C(\cdot, P_V)$

In this Section we show the equivalence between the linearizations of $\overline{H}(\sqcup \cdot)$, $\overline{H}(\wedge \cdot)$, $C(\sqcup \cdot, P_V)$ and $\overline{H}(\wedge \cdot, P_V)$. In the following $\mathcal{A}$ is a finite set and $(G_a)_{a \in \mathcal{A}} = (\mathcal{V}_a, \mathcal{E}_a, P_{V_a})_{a \in \mathcal{A}}$ is an arbitrary finite family of probabilistic graphs.

A crucial result for several linearization proofs is Lemma 5.2.1, which give an expression for the complementary graph entropy of a disjoint union w.r.t. a type; the proof is given in Appendix B.2.1. The main reasons why $\wedge$ appears in (5.31) in Lemma 5.2.1 are the AND powers used in $\overline{H}$, and the distributivity of $\wedge$ w.r.t. $\sqcup$ (see Lemma B.2.4).

**Lemma 5.2.1** If $P_A \in \Delta_k(\mathcal{A})$ for some $k \in \mathbb{N}^*$ then

$$ \overline{H} \left( \bigsqcup_{a \in \mathcal{A}}^{P_A} G_a \right) = \frac{1}{k} \overline{H} \left( \bigwedge_{a \in \mathcal{A}} G_a^{\wedge k P_A(a)} \right). \qquad (5.31) $$

When $P_A = \text{Unif}(\mathcal{A})$, we show in Corollary 5.2.2 that $\overline{H}(\sqcup \cdot)$ and $\overline{H}(\wedge \cdot)$ are equal up to a multiplicative constant.

**Corollary 5.2.2**

$$ \overline{H} \left( \bigsqcup_{a \in \mathcal{A}}^{\text{Unif}(\mathcal{A})} G_a \right) = \frac{1}{|\mathcal{A}|} \overline{H} \left( \bigwedge_{a \in \mathcal{A}} G_a \right). \qquad (5.32) $$

**Remark 5.2.3** In Lemma 5.2.1, if $P_A \in \Delta_k(\mathcal{A})$, then $P_A \in \Delta_{ik}(\mathcal{A})$ for all $i \in \mathbb{N}^*$.
However, this does not change the expression (5.31) as

$$ \frac{1}{ik} \overline{H} \left( \bigwedge_{a \in \mathcal{A}} G_a^{\wedge ik P_A(a)} \right) = \frac{1}{ik} \overline{H} \left( \left( \bigwedge_{a \in \mathcal{A}} G_a^{\wedge k P_A(a)} \right)^i \right) = \frac{1}{k} \overline{H} \left( \bigwedge_{a \in \mathcal{A}} G_a^{\wedge k P_A(a)} \right). \quad (5.33) $$

In Theorem 5.2.4, we show that the cases of equality coincide in Tuncel et al.'s inequalities in Theorem 5.1.11.

**Theorem 5.2.4** Let $P_A \in \Delta(\mathcal{A})$ with full-support, then the following equivalence holds:

$$ \overline{H} \left( \bigsqcup_{a \in \mathcal{A}}^{P_A} G_a \right) = \sum_{a \in \mathcal{A}} P_A(a) \overline{H}(G_a) \quad (5.34) $$

$$ \Leftrightarrow \overline{H} \left( \bigwedge_{a \in \mathcal{A}} G_a \right) = \sum_{a \in \mathcal{A}} \overline{H}(G_a). \quad (5.35) $$

The proof of Theorem 5.2.4 is given in Appendix B.2.2. The key results of this proof are Lemma 5.2.1 which gives the equivalence between linearizations of $\overline{H}(\wedge \cdot)$ and $\overline{H}(\sqcup^{P_A} \cdot)$; and Lemma B.2.2, Lemma B.2.3 that extend this equivalence to all distributions $P_A$ with full-support.

As a consequence of Marton's formula $\overline{H}(G) + C(G, P_V) = H(P_V)$, and the fact that the entropy $H(\cdot)$ always behaves additively w.r.t. independent random variables, we show with Proposition 5.2.5 the equivalence of linearizations between $\overline{H}$ and $C(\cdot, P_V)$. We also show superadditivity inequalities on $C(\wedge \cdot, P_V)$ and $C(\sqcup \cdot, P_V)$ based on Tuncel et al's subadditivity inequalities on $\overline{H}$ in Theorem 5.1.11. The proof of Proposition 5.2.5 is given in Appendix B.2.4.

The symmetric behaviors of $\overline{H}$ and $C(\cdot, P_V)$ lead to the equivalence between the linearizations of $C(\wedge \cdot, P_V)$ and $C(\sqcup \cdot, P_V)$ stated in Theorem 5.2.6, as a direct consequence of Theorem 5.2.4 and Proposition 5.2.5.

**Proposition 5.2.5** Let $P_A \in \Delta(\mathcal{A})$, then

$$ C \left( \bigsqcup_{a \in \mathcal{A}}^{P_A} G_a, \sum_{a \in \mathcal{A}} P_A(a) P_{V_a} \right) \geq H(P_A) + \sum_{a \in \mathcal{A}} P_A(a) C(G_a, P_{V_a}), \quad (5.36) $$

$$ C \left( \bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a} \right) \geq \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}); \quad (5.37) $$
and the following equivalences hold:

$$C\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a, \sum_{a \in \mathcal{A}} P_A(a)P_{V_a}\right) = H(P_A) + \sum_{a \in \mathcal{A}} P_A(a)C(G_a, P_{V_a}) \quad (5.38)$$

$$\iff \overline{H}\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a\right) = \sum_{a \in \mathcal{A}} P_A(a) \overline{H}(G_a); \qquad (5.39)$$

$$C\left(\bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}\right) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}) \qquad (5.40)$$

$$\iff \overline{H}\left(\bigwedge_{a \in \mathcal{A}} G_a\right) = \sum_{a \in \mathcal{A}} \overline{H}(G_a). \qquad (5.41)$$

A natural question is about the equivalence between (5.38) and (5.40). In the next Theorem (which follows from Theorem 5.2.4), we show that this equivalence holds.

**Theorem 5.2.6** Let $P_A \in \Delta(\mathcal{A})$ with full-support, then the following equivalence holds:

$$C\left(\bigcup_{a \in \mathcal{A}}^{P_A} G_a, \sum_{a \in \mathcal{A}} P_A(a)P_{V_a}\right) = H(P_A) + \sum_{a \in \mathcal{A}} P_A(a)C(G_a, P_{V_a}) \quad (5.42)$$

$$\iff C\left(\bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}\right) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}). \qquad (5.43)$$

In this Section we proved that the equivalence of the linearisations between $\overline{H}$ and $C(\cdot, P_V)$ holds. In the next Sections, we investigate the linearisation of the zero-error capacity $C_0$.

## 5.3 Main results on capacity-achieving distributions

In this Section, we define the set of capacity-achieving distributions of a graph, which are the distributions $P_V$ such that $C(\cdot, P_V)$ is equal to $C_0$. We give results on the capacity-achieving distributions when the graph is a product, and when the graph is vertex-transitive. Furthermore, understanding the capacity-achieving distributions is a necessary step towards the equivalence of linearization between $C_0$ and $C(\cdot, P_V)$, which is presented in Section 5.4. In the following, $\mathcal{A}$ is a finite set and $(G_a)_{a \in \mathcal{A}} = (\mathcal{V}_a, \mathcal{E}_a)_{a \in \mathcal{A}}$ is an arbitrary finite family of graphs.
**Definition 5.3.1 (Set of capacity-achieving distributions $\mathcal{P}^*$)** Let $G = (\mathcal{V}, \mathcal{E})$ be a graph. The set of capacity-achieving distributions of $G$ is the subset of $\Delta(\mathcal{V})$ denoted by $\mathcal{P}^*(G)$ and is defined by

$$ \mathcal{P}^*(G) = \underset{P_V \in \Delta(\mathcal{V})}{\operatorname{argmax}} C(G, P_V). \qquad (5.44) $$

**Proposition 5.3.2** For all graph $G$, the mapping $P_V \mapsto C(G, P_V)$ is concave. The set of capacity-achieving distributions $\mathcal{P}^*(G)$ defined in Definition 5.3.1 is convex, nonempty, and satisfies

$$ \forall P_V \in \mathcal{P}^*(G), C_0(G) = C(G, P_V). \qquad (5.45) $$

The proof of Proposition 5.3.2 is developed in Appendix B.3.3; the key result used in the proof is the formula $\max_{P_V} C(G, P_V) = C_0(G)$ from Theorem 5.1.4.

In Theorem 5.3.3, we show that if a joint distribution is capacity-achieving for a product of graphs, then the product of its marginals is also capacity-achieving. The proof of Theorem 5.3.3 is given in Appendix B.3.4, and is based on a codebook shifting argument: with a given zero-error codebook for $G \wedge G'$ with average type $P_{V,V'}$, one can build a shifted zero-error codebook (for an increased number of channel uses) with the same rate and average type $P_V \otimes P_{V'}$.

**Theorem 5.3.3** If $P_{V_1, \dots, V_{|\mathcal{A}|}} \in \mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a)$, then $\otimes_{a \in \mathcal{A}} P_{V_a} \in \mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a)$.

**Corollary 5.3.4**

$$ C_0 \left( \bigwedge_{a \in \mathcal{A}} G_a \right) = \max_{\substack{(P_{V_a})_{a \in \mathcal{A}} \\ \prod_{a \in \mathcal{A}} \Delta(\mathcal{V}_a)}} C \left( \bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a} \right). \qquad (5.46) $$

We show in Lemma 5.3.7 that the uniform distribution achieves the zero-error capacity for vertex-transitive graphs, i.e. a graph in which all the vertices play the same “role”. The proof of Lemma 5.3.7 is given in Appendix B.3.5.

**Definition 5.3.5 (Group of automorphisms Aut)** An automorphism of a graph $G = (\mathcal{V}, \mathcal{E})$ is a bijection $\psi : \mathcal{V} \to \mathcal{V}$ such that for all $v, v' \in \mathcal{V}$, $vv' \in \mathcal{E}$ if and only if $\psi(v)\psi(v') \in \mathcal{E}$. The group of automorphisms of $G$ is denoted by Aut($G$).
**Definition 5.3.6 (Vertex-transitive graph)** A graph $G = (\mathcal{V}, \mathcal{E})$ is vertex-transitive if Aut($G$) acts transitively on its vertices, i.e. for all $v, v' \in \mathcal{V}$, there exists $\psi \in \text{Aut}(G)$ such that $\psi(v) = v'$.

**Lemma 5.3.7** If $G = (\mathcal{V}, \mathcal{E})$ is vertex-transitive, then

$$ \mathrm{Unif}(\mathcal{V}) \in \mathcal{P}^*(G). \qquad (5.47) $$

**Corollary 5.3.8** Let $(G_a)_{a \in \mathcal{A}} = (\mathcal{V}_a, \mathcal{E}_a)_{a \in \mathcal{A}}$ be vertex-transitive graphs, their product is also vertex-transitive and

$$ \mathrm{Unif}\left(\prod_{a \in \mathcal{A}} \mathcal{V}_a\right) = \bigotimes_{a \in \mathcal{A}} \mathrm{Unif}(\mathcal{V}_a) \in \mathcal{P}^*\left(\bigwedge_{a \in \mathcal{A}} G_a\right). \qquad (5.48) $$

## 5.4 Linking the linearizations of $C_0$ and $C(\cdot, P_V)$

In this Section, we show the equivalences of linearizations between $C_0$ and $C(\cdot, P_V)$. In the following, $\mathcal{A}$ is a finite set and $(G_a)_{a \in \mathcal{A}} = (\mathcal{V}_a, \mathcal{E}_a)_{a \in \mathcal{A}}$ is an arbitrary finite family of graphs.

Theorem 5.4.1 states that $C_0(\wedge \cdot)$ can be linearized if and only if $C(\wedge \cdot, P_V)$ can be linearized for some distribution $P_V$ which is capacity-achieving for the product. When the linearisation of $C(\wedge \cdot, P_V)$ holds, we also show that the marginals of such a distribution are capacity-achieving for the respective graphs in the product. A similar result is derived for the disjoint union in Theorem 5.4.2; this result makes use of the optimal distribution $P_A(a) = \frac{2^{C_0(G_a)}}{\sum_{a' \in \mathcal{A}} 2^{C_0(G_{a'})}}$, which is the maximizer of $P_A \mapsto H(P_A) + \sum_{a \in \mathcal{A}} P_A(a)C_0(G_a)$ as stated in Lemma B.4.5. The proof of Theorem 5.4.1 and Theorem 5.4.2 are respectively given in Appendix B.4.1 and Appendix B.4.4.

**Theorem 5.4.1** The following holds

$$ C_0\left(\bigwedge_{a \in \mathcal{A}} G_a\right) = \sum_{a \in \mathcal{A}} C_0(G_a) \qquad (5.49) $$

$$ \iff \exists P_{V_1, \dots, V_{|\mathcal{A}|}} \in \mathcal{P}^*\left(\bigwedge_{a \in \mathcal{A}} G_a\right), \quad C\left(\bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}\right) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}). \qquad (5.50) $$

Furthermore, any distribution $\otimes_{a \in \mathcal{A}} P_{V_a} \in \mathcal{P}^*(\wedge_{a \in \mathcal{A}} G_a)$ that satisfies (5.50) also satisfies the following: $\forall a \in \mathcal{A}, P_{V_a} \in \mathcal{P}^*(G_a)$.
**Theorem 5.4.2** The following equivalence holds

$$C_0\left(\bigsqcup_{a \in \mathcal{A}} G_a\right) = \log\left(\sum_{a \in \mathcal{A}} 2^{C_0(G_a)}\right) \qquad (5.51)$$

$$\iff \exists P_V \in \mathcal{P}^*\left(\bigsqcup_{a \in \mathcal{A}} G_a\right), \qquad (5.52)$$

$$C\left(\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a, \sum_{a \in \mathcal{A}} P_A(a)P_{V_a}\right) = H(P_A) + \sum_{a \in \mathcal{A}} P_A(a)C(G_a, P_{V_a}), \qquad (5.53)$$

where $P_{V_a} = P_{V|_{V \in \mathcal{V}_a}}$ and $P_A(a) = P_V(\mathcal{V}_a)$ for all $a \in \mathcal{A}$. Furthermore, any $\sum_{a \in \mathcal{A}} P_A(a)P_{V_a}$ that satisfies (5.53) also satisfies the following for all $a \in \mathcal{A}$:

$$P_A(a) = \frac{2^{C_0(G_a)}}{\sum_{a' \in \mathcal{A}} 2^{C_0(G_{a'})}}, \quad \text{and} \quad P_{V_a} \in \mathcal{P}^*(G_a). \qquad (5.54)$$

**Remark 5.4.3** One could think of a possible proof strategy for Theorem 5.4.2, which is successively using the equivalences in Theorem 5.1.20, Theorem 5.4.1, and Theorem 5.2.6. However, doing so yields the following statement

$$C_0(\bigsqcup_{a \in \mathcal{A}} G_a) = \log\left(\sum_{a \in \mathcal{A}} 2^{C_0(G_a)}\right) \qquad (5.55)$$

$$\iff \exists P_A \in \Delta(\mathcal{A}) \text{ full-support, } \exists P_{V_1, \dots, V_{|\mathcal{A}|}} \in \mathcal{P}^* (\bigwedge_{a \in \mathcal{A}} G_a), \qquad (5.56)$$

$$C\left(\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a, \sum_{a \in \mathcal{A}} P_A(a)P_{V_a}\right) = H(P_A) + \sum_{a \in \mathcal{A}} P_A(a)C(G_a, P_{V_a});$$

a missing step consists in linking $\mathcal{P}^*(\bigsqcup_{a \in \mathcal{A}} G_a)$ with $\mathcal{P}^*(\bigwedge_{a \in \mathcal{A}} G_a)$.

# 5.5 Main examples and counterexamples of linearization

## 5.5.1 Perfect graphs

In this Section, we show that perfect graphs allow for linearization of $C_0$, $C(\cdot, P_V)$ and $\bar{H}$ w.r.t. both $\sqcup$ and $\wedge$ with any underlying distribution. Perfect graphs are one of the only known examples of graphs with a single-letter formula for $\bar{H}$ and $C_0$, as stated in Theorem 5.5.4 and Theorem 5.5.5. We also give single-letter formulae for $C_0$, $C(\cdot, P_V)$ and $\bar{H}$ for products of perfect graphs, which are not perfect in general. Therefore, our
results yield new examples of single-letter formulae $C_0$, $C(\cdot, P_V)$ and $\bar{H}$ for cases where such formulae were previously unknown.

**Definition 5.5.1 (Graph complement, clique number $\omega$)** For all $G = (\mathcal{V}, \mathcal{E})$, the complementary graph of $G$ is defined by $\bar{G} \doteq (\mathcal{V}, \mathcal{E}^c)$. The clique number of $G$ is defined by $\omega(G) \doteq \alpha(\bar{G})$.

**Definition 5.5.2 (Perfect graph)** A graph $G = (\mathcal{V}, \mathcal{E})$ is perfect if $\forall S \subseteq \mathcal{V}$, $\chi(G[S]) = \omega(G[S])$. A probabilistic graph $(\mathcal{V}, \mathcal{E}, P_V)$ is perfect if $(\mathcal{V}, \mathcal{E})$ is perfect.

**Definition 5.5.3 (Körner graph entropy $H_\kappa$)** For all $G = (\mathcal{V}, \mathcal{E}, P_V)$, let $\Gamma(G)$ be the collection of independent sets of vertices in $G$. The Körner graph entropy of $G$ is defined by

$$H_{\kappa}(G) = \min_{V \in W \in \Gamma(G)} I(W; V), \qquad (5.57)$$

where the minimum is taken over all distributions $P_{W|V} \in \Delta(W)^V$, with $W = \Gamma(G)$ and with the constraint that the random vertex $V$ belongs to the random independent set $W$ with probability one, i.e. $V \in W \in \Gamma(G)$ in (5.57).

**Theorem 5.5.4 (from [22, Corollary 12])** Let $G$ be a perfect probabilistic graph, then

$$\bar{H}(G) = H_{\kappa}(G). \qquad (5.58)$$

Shannon proved in [58, Theorem 3] that a graph $G$ whose vertex set can be partitioned into $\alpha(G)$ cliques (i.e. complete induced subgraphs) satisfies $C_0(G) = \alpha(G)$. Perfect graphs are an example of that, as their complementary is also perfect, and satisfy $\chi(\bar{G}) = \omega(\bar{G}) = \alpha(G)$, where $\chi(\bar{G})$ is the clique cover number.

**Theorem 5.5.5 (from [58, Theorem 3])** If $G$ is a perfect graph, then $C_0(G) = \log \alpha(G)$.

As stated in Proposition 5.5.6, perfect graphs are an example of linearization for $C_0$: since $C_0(G \sqcup G') = \log \alpha(G \sqcup G') = \log(\alpha(G) + \alpha(G')) = \log(2^{C_0(G)} + 2^{C_0(G')})$ holds for all perfect $G, G'$, we obtain $C_0(G \wedge G') = C_0(G) + C_0(G')$ by Schrijver's result in Theorem 5.1.20.
**Proposition 5.5.6** Let G and G' be perfect graphs, then

$$C_0(G \sqcup G') = \log(2^{C_0(G)} + 2^{C_0(G')}) = \log(\alpha(G) + \alpha(G')); \qquad (5.59)$$

$$C_0(G \wedge G') = C_0(G) + C_0(G') = \log \alpha(G) + \log \alpha(G'). \qquad (5.60)$$

<figure><img src="image_18.png" /><figcaption>Figure 5.6 – A non-perfect AND product of perfect graphs: $C_6 \wedge C_8$ with an induced $C_7$.</figcaption></figure>

AND products of perfect graphs are not perfect in general; see for example Figure 5.6 where a product of two perfect graphs contains an induced $C_7$, which makes it non-perfect by Theorem 5.5.7. However, a disjoint union of perfect graphs is always perfect, as stated in Lemma B.5.2; therefore the results on equivalence of linearizations are useful to extend the linearization properties and single-letter expressions to the AND product of perfect graphs. In Theorem 5.5.8 we show that perfect graphs allow for the linearization of $C(\cdot, P_V)$ and $\bar{H}$, for all underlying probability distributions; and we also give a single-letter expression for $\bar{H}$ and $C(\cdot, P_V)$ in that case. The proof of Theorem 5.5.8 is given in Appendix B.5.1.

**Theorem 5.5.7 (Strong perfect graph theorem, from [16, Theorem 1.2])** A graph G is perfect if and only if neither G nor $\bar{G}$ have an induced odd cycle of length at least 5.

**Theorem 5.5.8** When $(G_a)_{a \in A} = (\mathcal{V}_a, \mathcal{E}_a, P_{V_a})_{a \in A}$ is a family of perfect probabilistic
graphs, the following single-letter characterizations hold:

$$ \overline{H}\left(\bigwedge_{a \in \mathcal{A}} G_a\right) = \sum_{a \in \mathcal{A}} \overline{H}(G_a) = \sum_{a \in \mathcal{A}} H_{\kappa}(G_a), \qquad (5.61) $$

$$ \overline{H}\left(\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a\right) = \sum_{a \in \mathcal{A}} P_A(a) \overline{H}(G_a) = \sum_{a \in \mathcal{A}} P_A(a) H_{\kappa}(G_a), \qquad (5.62) $$

$$ C\left(\bigwedge_{a \in \mathcal{A}} G_a, \bigotimes_{a \in \mathcal{A}} P_{V_a}\right) = \sum_{a \in \mathcal{A}} C(G_a, P_{V_a}) = \sum_{a \in \mathcal{A}} (H(V_a) - H_{\kappa}(G_a)), \qquad (5.63) $$

$$ \begin{aligned} C\left(\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a, \sum_{a \in \mathcal{A}} P_A(a) P_{V_a}\right) &= H(P_A) + \sum_{a \in \mathcal{A}} P_A(a) C(G_a, P_{V_a}) \\ &= H(P_A) + \sum_{a \in \mathcal{A}} P_A(a) (H(V_a) - H_{\kappa}(G_a)). \end{aligned} \qquad (5.64) $$

Another interesting example is the graph $C_5 \sqcup G$ where $G$ is perfect, which is an example of linearization of $\overline{H}$ with single-letter formula developed by Tuncel et al. in [71]. The pentagon graph $C_5$ is not perfect, and makes non-perfect any disjoint union or AND product that is made with it. However we can use Theorem 5.2.4, and derive in Corollary 5.5.10 another non-perfect example of linearization with single-letter formula for $\overline{H}$: $C_5 \wedge G$ with $G$ perfect.

**Theorem 5.5.9 (from [71, Lemma 3])** Let $s \in [0, 1]$, let $G$ be a perfect probabilistic graph, and let $G_5 \doteq (C_5, \text{Unif}(\{0, ..., 4\}))$, we have

$$ \overline{H}(G_5 \sqcup G) = s\overline{H}(G_5) + (1-s)\overline{H}(G) \qquad (5.65) $$

$$ = \frac{s}{2}\log 5 + (1-s)H_{\kappa}(G). \qquad (5.66) $$

**Corollary 5.5.10** For all perfect probabilistic graph $G$,

$$ \overline{H}(G \wedge G_5) = \overline{H}(G) + \overline{H}(G_5) = H_{\kappa}(G) + \frac{1}{2} \log 5. \qquad (5.67) $$

## 5.5.2 The Schläfli graph

In order to use the Schläfli graph $S$ as a counterexample for $C(\cdot, P_V)$ and $\overline{H}$, we need a capacity-achieving distribution of $S \wedge \overline{S}$. As stated in Lemma 5.5.11, the Schläfli graph
is vertex transitive. By Lemma 5.3.7 and Corollary 5.5.12, the uniform distribution is capacity-achieving for $S$, $\bar{S}$, and $S \wedge \bar{S}$.

**Lemma 5.5.11 (from [11, Lemma 3.7])** The Schläfli graph is vertex-transitive.

**Corollary 5.5.12** The sets $P^*(S)$, $P^*(\bar{S})$, and $P^*(S \wedge \bar{S})$ all contain the uniform distribution.

In Theorem 5.5.13 we adapt the Schläfli graph counterexample to $C(\cdot, P_V)$ and $\bar{H}$ by using our results from the previous sections.

**Theorem 5.5.13** Let $s \in (0, 1)$, let $S = (\mathcal{V}_S, \mathcal{E}_S, \text{Unif}(\mathcal{V}_S))$ be the Schläfli graph and let $\bar{S} = (\mathcal{V}_S, \mathcal{E}_{\bar{S}}, \text{Unif}(\mathcal{V}_S))$ be the complementary of the Schläfli graph with uniform distribution on their vertices. Then

$$C(S \wedge \bar{S}, \text{Unif}(\mathcal{V}_S) \otimes \text{Unif}(\mathcal{V}_{\bar{S}})) > C(S, \text{Unif}(\mathcal{V}_S)) + C(\bar{S}, \text{Unif}(\mathcal{V}_{\bar{S}})), \quad (5.68)$$

$$C(S \sqcup \bar{S}, s \text{Unif}(\mathcal{V}_S) + (1-s) \text{Unif}(\mathcal{V}_{\bar{S}})) > h_b(s) + sC(S, \text{Unif}(\mathcal{V}_S)) \\ + (1-s)C(\bar{S}, \text{Unif}(\mathcal{V}_{\bar{S}})), \quad (5.69)$$

$$\bar{H}(S \wedge \bar{S}) < \bar{H}(S) + \bar{H}(\bar{S}), \quad (5.70)$$

$$\bar{H}(S^{(s,1-s)} \sqcup \bar{S}) < s\bar{H}(S) + (1-s)\bar{H}(\bar{S}); \quad (5.71)$$

where $h_b$ is the binary entropy.

We obtain the first inequality from Theorem 5.4.1 and Corollary 5.5.12; the second one from Theorem 5.2.6; the third one comes from Proposition 5.2.5; and the last one from Theorem 5.2.4.

**Remark 5.5.14** Alon has built in [4] infinite families of graphs that satisfy $C_0(G \sqcup G') > \log(2^{C_0(G)} + 2^{C_0(G')})$. Similar results as in Theorem 5.5.13 can be derived for these graphs, by using their respective capacity-achieving distributions.
<figure><img src="image_19.png" /></figure>
# CONTRIBUTIONS FOR CODING FOR COMPUTING ZERO-ERROR PROBLEMS

In this Chapter, we study the zero-error coding for computing problem with side information at the encoder, presented in Section 6.1. We first give an asymptotic expression for the optimal rate in the general case, then we formulate an hypothesis on $P_{X,Y}$ and $g$ that we call “pairwise shared side information” that allows us to derive a single-letter characterization of the optimal rate. In particular it covers the cases with $P_{X,Y}$ full-support, without any assumption on $f, g$.

This hypothesis is satisfied if every pair of source symbols “share” at least one side information symbol for all output of $g$. It has graph-theoretic interpretations, as the single-letter formula stems from the particular structure of the characteristic graph of the problem: a disjoint union of OR products. We also prove that this condition is equivalent to the worst optimal rate in an auxiliary Slepian-Wolf problem.

## 6.1 Coding for computing problems

### 6.1.1 Coding for computing in the vanishing error regime

The coding for computing problem is defined in [50] by Orlitsky and Roche. In this setting the decoder wants to retrieve a function of both encoder's and decoder's data.

<figure><img src="image_20.png" /><figcaption>Figure 6.1 – Coding for computing.</figcaption></figure>

**Definition 6.1.1** The source coding problem of Figure 6.2 is described by:
- Finite sets $\mathcal{U}$, $\mathcal{X}$, $\mathcal{Y}$ and a source distribution $P_{X,Y} \in \Delta(\mathcal{X} \times \mathcal{Y})$;

- For all $n \in \mathbb{N}^*$, $(X^n, Y^n)$ is the random sequence of n copies of $(X, Y)$, drawn in an i.i.d. fashion using $P_{X,Y}$.

- Two deterministic functions

$$f: \mathcal{X} \times \mathcal{Y} \to \mathcal{U}. \qquad (6.1)$$

- An encoder that knows $X^n$ sends binary strings over a noiseless channel to a decoder that knows $Y^n$, and that wants to retrieve $(f(X_t, Y_t))_{t \le n}$ without error.

A coding scheme in this setting is described by:

- A time horizon $n \in \mathbb{N}^*$, and an encoding function $\phi_e : \mathcal{X}^n \to \{0,1\}^*$ such that $\mathrm{Im} \, \phi_e$ is prefix-free;

- A decoding function $\phi_d : \mathcal{Y}^n \times \{0,1\}^* \to \mathcal{U}^n$;

- The rate is the average length of the codeword per source symbol, i.e. $R \doteq \frac{1}{n}\mathbb{E}[\ell \circ \phi_e(X^n)]$;

- $n, \phi_e, \phi_d$ must satisfy the $\epsilon$-error property:

$$\mathbb{P}\left(\phi_d(Y^n, \phi_e(X^n)) \neq (f(X_t, Y_t))_{t \le n}\right) \le \epsilon. \qquad (6.2)$$

The objective is to find the minimal rate among all coding schemes under the vanishing error constraint:

$$R_{CFC}^* \doteq \lim_{\epsilon \to 0} \inf_{\substack{n, \phi_e, \phi_d \\ \epsilon\text{-error}}} \frac{1}{n} \mathbb{E}[\ell \circ \phi_e(X^n, (g(Y_t))_{t \le n})]. \qquad (6.3)$$

As illustrated in Theorem 6.1.4, Orlitsky and Roche give in [50] a single-letter expression of the optimal rate. This optimal rate is characterized with a characteristic graph $G_{CFC}$ defined below, and a conditional version of Körner's graph entropy (the latter is defined in Definition 5.5.3).

**Definition 6.1.2 (Conditional Körner graph entropy)** For all $G = (\mathcal{V}, \mathcal{E}, P_V)$, let $\Gamma(G)$ be the collection of independent sets of vertices in $G$. Let $P_{Y|V} \in \Delta(\mathcal{Y})^{|\mathcal{V}|}$, the
conditional Körner graph entropy of G is defined by

$$H_{\kappa}(G|Y) = \min_{\substack{W \to V \\ V \in W \\ W \in \Gamma(G)}} I(W; V|Y), \qquad (6.4)$$

where the minimum is taken over all distributions $P_{W|V,Y} \in \Delta(W)^V$, with $W \to V \to Y$ (i.e. $P_{W|V,Y} = P_{W|V}$), $W = \Gamma(G)$ and with the constraint that the random vertex V belongs to the random independent set W with probability one, i.e. $V \in W \in \Gamma(G)$ in (6.4).

**Definition 6.1.3 (Characteristic graph $G_{CFC}$)** The auxiliary graph $G_{CFC}$ is defined by

- $\mathcal{X}$ as set of vertices with distribution $P_X$,

- $xx'$ are adjacent if $f(x, y) \neq f(x', y)$ for some $y \in \text{supp } P_{Y|X=x} \cap \text{supp } P_{Y|X=x'}$.

**Theorem 6.1.4 (from [50])**

$$R_{CFC}^* = H_{\kappa}(G_{CFC}|Y).$$

## 6.1.2 Zero-error coding for computing with side information at the encoder

<figure><img src="image_21.png" /><figcaption>Figure 6.2 – Zero-error coding for computing with side information at the encoder.</figcaption></figure>

The problem of Figure 6.2 is a zero-error setting that relates to Orlitsky and Roche's coding for computing problem from [50]. This coding problem appears in video compression [23, 27], where $X^n$ models a set of images known at the encoder. The decoder does not always want to retrieve each image, but has instead a sequence $Y^n$ of particular requests for each image, e.g. detection: cat, dog, car, bike; or scene recognition: street/city/mountain, etc... The encoder does not know the decoder's exact request but has prior information about it (e.g. type of request), which is modeled by $(g(Y_t))_{t \le n}$. This problem also relates to the zero-error Slepian-Wolf open problem presented in Section 3.3.1, as it is obtained as a special case by taking $g$ constant and $f(X, Y) = X$.
**Definition 6.1.5** The zero-error source coding problem of Figure 6.2 is described by:

- Four finite sets $\mathcal{U}$, $\mathcal{X}$, $\mathcal{Y}$, $\mathcal{Z}$ and a source distribution $P_{X,Y} \in \Delta(\mathcal{X} \times \mathcal{Y})$;

- For all $n \in \mathbb{N}^*$, $(X^n, Y^n)$ is the random sequence of n copies of $(X, Y)$, drawn in an i.i.d. fashion using $P_{X,Y}$.

- Two deterministic functions

$$f: \mathcal{X} \times \mathcal{Y} \to \mathcal{U}, \qquad (6.5)$$

$$g: \mathcal{Y} \to \mathcal{Z}. \qquad (6.6)$$

- An encoder that knows $X^n$ and $(g(Y_t))_{t \le n}$ sends binary strings over a noiseless channel to a decoder that knows $Y^n$, and that wants to retrieve $(f(X_t, Y_t))_{t \le n}$ without error.

A coding scheme in this setting is described by:

- A time horizon $n \in \mathbb{N}^*$, and an encoding function $\phi_e: \mathcal{X}^n \times \mathcal{Z}^n \to \{0, 1\}^*$ such that $\mathrm{Im} \, \phi_e$ is prefix-free;

- A decoding function $\phi_d: \mathcal{Y}^n \times \{0, 1\}^* \to \mathcal{U}^n$;

- The rate is the average length of the codeword per source symbol, i.e. $R \doteq \frac{1}{n} \mathbb{E}[\ell \circ \phi_e(X^n, (g(Y_t))_{t \le n})]$;

- $n, \phi_e, \phi_d$ must satisfy the zero-error property:

$$\mathbb{P}\left(\phi_d\left(Y^n, \phi_e\left(X^n, (g(Y_t))_{t \le n}\right)\right) \neq \left(f(X_t, Y_t)\right)_{t \le n}\right) = 0. \qquad (6.7)$$

The objective is to find the minimal rate among all coding schemes under the zero-error constraint:

$$R_{CFC0}^* \doteq \inf_{\substack{n, \phi_e, \phi_d \\ \text{zero-error}}} \frac{1}{n} \mathbb{E}[\ell \circ \phi_e(X^n, (g(Y_t))_{t \le n})]. \qquad (6.8)$$

Now the scheme of Figure 6.2 has been studied with different coding constraints than zero-error, and the optimal rate has been characterized in each case: the lossless case by Orlitsky and Roche in [50], the lossy case by Yamamoto in [76], and the zero-error “unrestricted inputs” case by Shayevitz in [60]. These results can only be used as bounds here: the zero-error problem depicted in Figure 6.2 does not have a characterization of the optimal rate.
Numerous extensions of the problem depicted in Figure 6.2 have been studied recently. The distributed context, for instance, has an additional encoder which encodes Y before transmitting it to the decoder. Achievability schemes have been proposed for this setting by Krithivasan and Pradhan in [42] using abelian groups; by Basu et al. in [6] using hypergraphs for the case with maximum distortion criterion; and by Malak and Médard in [46] using hyperplane separations for the continuous lossless case.

Another related context is the network setting, where the function of source random variables from source nodes has to be retrieved at the sink node of a given network. For tree networks, the feasible rate region is characterized by Feizi and Médard in [24] for networks of depth one; and by Sefidgaran and Tchamkerten in [56] under a Markov source distribution hypothesis. In [52], Ravi and Dey consider a bidirectional relay with zero-error “unrestricted inputs” and characterize the rate region for a specific class of functions. In [32], Guang et al. study zero-error function computation on acyclic networks with limited capacities, and give an inner bound based on network cut-sets. For both distributed and network settings, the zero-error coding for computing problem with encoder side information remains open.

In Chapter 6, we formulate an hypothesis on $P_{X,Y}$ and $g$ that we call “pairwise shared side information” that allows us to derive a single-letter characterization of the optimal rate. In particular it covers the cases with $P_{X,Y}$ full-support, without any assumption on $f, g$.

## 6.2 General case

We first build the characteristic graph $G_{[n]}$, which is a probabilistic graph that captures the zero-error encoding constraints on a given number $n$ of source uses. It differs from the graphs used in [60], as we do not need a cartesian representation of these graphs to study the optimal rates. Furthermore, it has a vertex for each possible realization of $(X^n, (g(Y_t))_{t \le n})$ known at the encoder, instead of $\mathcal{X}^n$ as in the zero-error Slepian-Wolf problem presented in Section 3.3.1.

**Definition 6.2.1 (Characteristic graph $G_{[n]}$)** The characteristic graph $G_{[n]}$ is defined by:

$$ - \mathcal{X}^n \times \mathcal{Z}^n \text{ as set of vertices with distribution } P_{X,g(Y)}^n, $$
- $(x^n, z^n)(x'^n, z'^n)$ are adjacent if $z^n = z'^n$ and there exists $y^n \in g^{-1}(z^n)$ such that:

$$ \forall t \le n, P_{X,Y}(x_t, y_t)P_{X,Y}(x'_t, y_t) > 0, \qquad (6.9) $$

$$ \text{and } \exists t \le n, f(x_t, y_t) \ne f(x'_t, y_t); \qquad (6.10) $$

$$ \text{where } g^{-1}(z^n) = \{y^n \in \mathcal{Y}^n \mid (g(y_t))_{t \le n} = z^n\}. $$

The characteristic graph $G_{[n]}$ is designed with the same core idea as in [75]: $(x^n, z^n)$ and $(x'^n, z'^n)$ are adjacent if there exists a side information symbol $y^n$ compatible with the observation of the encoder (i.e. $z^n = z'^n$ and $y^n \in g^{-1}(z^n)$), such that $f(x^n, y^n) \ne f(x'^n, y^n)$. In order to prevent erroneous decodings, the encoder must map adjacent pairs of sequences to different codewords; hence the use of graph colorings.

**Theorem 6.2.2 (Optimal rate) The optimal rate writes:**

$$ R_{CFC0}^* = \lim_{n \to \infty} \frac{1}{n} H_X(G_{[n]}). \qquad (6.11) $$

*Proof.* By construction the following holds: for all encoding function $\phi_e$, $\phi_e$ is a coloring of $G_{[n]}$ if and only if there exists a decoding function $\phi_d$ such that $(n, \phi_e, \phi_d)$ satisfies the zero-error property. Thus the best achievable rate writes

$$ R_{CFC}^* = \inf_n \inf_{\phi_e \text{ coloring of } G_{[n]}} H\left(\phi_e\left(X^n, \left(g(Y_t)\right)_{t \le n}\right)\right) \qquad (6.12) $$

$$ = \lim_{n \to \infty} \frac{1}{n} H_X(G_{[n]}). \qquad (6.13) $$

where (6.13) comes from Fekete's lemma and from the definition of $H_X$. □

A general single-letter expression for $R_{CFC}^*$ is missing, due to the lack of intrinsic structure of $G_{[n]}$. In Section 6.3, we introduce a hypothesis that gives structure to $G_{[n]}$ and allows us to derive a single-letter expression for $R_{CFC}^*$.

## 6.3 Pairwise shared side information

**Definition 6.3.1** The distribution $P_{X,Y}$ and the function $g$ satisfy the “pairwise shared side information” condition if

$$ \forall z \in \mathcal{Z}, \forall x, x' \in \mathcal{X}, \exists y \in g^{-1}(z), P_{XY}(x, y)P_{XY}(x', y) > 0. \qquad (6.14) $$
This means that for all z output of g, every pair $(x, x')$ "shares" at least one side information symbol $y \in g^{-1}(z)$.

Note that any full-support distribution $P_{X,Y}$ satisfies the "pairwise shared side information" hypothesis. In Theorem 6.3.2 we give an interpretation of the "pairwise shared side information" condition in terms of the optimal rate in an auxiliary zero-error Slepian-Wolf problem. The proof of Theorem 6.3.2 is given in Appendix C.1

**Theorem 6.3.2** The tuple $(P_{X,Y}, g)$ satisfies the condition "pairwise shared side information" (6.14)

$\iff R^* = H(X|g(Y))$ in the case $f(X,Y) = X$, and for all $z \in \mathcal{Z}$, $P_{X|g(Y)=z}$ is full-support.

In the zero-error Slepian-Wolf problem presented in Section 4.1.1, the optimal rate $\lim_{n \to \infty} \frac{1}{n} H_X(G^{\wedge n})$ does not have a single-letter expression. However, as shown in Proposition 6.3.4, there exists such a formula for $\lim_{n \to \infty} \frac{1}{n} H_X(G^{\vee n})$: the Körner graph entropy introduced in [39]. By using a convex combination of Körner graph entropies, we provide a single-letter expression in Theorem 6.3.6 for the optimal rate $R_{CFC}^*$.

**Definition 6.3.3 (OR product)** Let $G_1 = (\mathcal{V}_1, \mathcal{E}_1, P_{V_1})$, $G_2 = (\mathcal{V}_2, \mathcal{E}_2, P_{V_2})$ be two probabilistic graphs; their OR product denoted $G_1 \vee G_2$ is defined by: $\mathcal{V}_1 \times \mathcal{V}_2$ as set of vertices, $P_{V_1} P_{V_2}$ as probability distribution on the vertices, and $(v_1 v_2), (v'_1 v'_2)$ are adjacent if

$$ (v_1 v'_1 \in \mathcal{E}_1 \text{ and } v_1 \neq v'_1) \text{ OR } (v_2 v'_2 \in \mathcal{E}_2 \text{ and } v_2 \neq v'_2); $$

with the convention that all vertices are self-adjacent. We denote by $G_1^{\vee n}$ the n-th OR power.

**Proposition 6.3.4 (Properties of $H_\kappa$)** [5, Theorem 5] For all probabilistic graphs G and $G'$,

$$ H_{\kappa}(G) = \lim_{n \to \infty} \frac{1}{n} H_{\chi}(G^{\vee n}), \qquad (6.15) $$

$$ H_{\kappa}(G \vee G') = H_{\kappa}(G) + H_{\kappa}(G'). \qquad (6.16) $$

**Definition 6.3.5 (Auxiliary graph $G_z^f$)** For all $z \in \mathcal{Z}$, we define the auxiliary graph $G_z^f$ by

- $\mathcal{X}$ as set of vertices with distribution $P_{X|g(Y)=z}$,
- $xx'$ are adjacent if $f(x, y) \neq f(x', y)$ for some $y \in g^{-1}(z) \cap \text{supp } P_{Y|X=x} \cap \text{supp } P_{Y|X=x'}$.

**Theorem 6.3.6 (Pairwise shared side information)** If $P_{X,Y}$ and $g$ satisfy (6.14), the optimal rate writes:

$$R_{CFC0}^* = \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z^f). \qquad (6.17)$$

The proof is in Section C.2, the keypoint is the particular structure of $G_{[n]}$: a disjoint union of OR products.

**Remark 6.3.7** The “pairwise shared side information” assumption (6.14) implies that the adjacency condition (6.9) is satisfied, which makes $G_{[n]}$ a disjoint union of OR products. Moreover, Körner graph entropies appear in the final expression for $R_{CFC}^*$, even if $G_{[n]}$ is not an n-th OR power.

Now consider the case where $P_{X,Y}$ is full-support. This is a sufficient condition to have (6.14). The optimal rate in this setting is derived from Theorem 6.3.6, which leads to the analytic expression in Theorem 6.3.8.

**Theorem 6.3.8 (Optimal rate when $P_{X,Y}$ is full-support)** When $P_{X,Y}$ is full-support, the optimal rate writes:

$$R_{CFC0}^* = H(j(X, g(Y))|g(Y)), \qquad (6.18)$$

where the function $j$ returns a word in $\mathcal{U}^*$, defined by

$$j: \mathcal{X} \times \mathcal{Z} \to \mathcal{U}^* \qquad (6.19) \\ (x, z) \mapsto (f(x, y'))_{y' \in g^{-1}(z)}.$$

*Proof.* By Theorem 6.3.6, $R_{CFC}^* = \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z^f)$. It can be shown that $G_z^f$ is complete multipartite for all $z$ as $P_{X,Y}$ is full support; and it satisfies $H_{\kappa}(G_z^f) = H(j(X, g(Y))|g(Y) = z)$. $\square$

## 6.4 Example

In this example, the “pairwise shared side information” assumption is satisfied and $R_{CFC}^*$ is strictly less than a conditional Huffman coding of $X$ knowing $g(Y)$; and also strictly less than the optimal rate without exploiting $g(Y)$ at the encoder.
<table><thead><tr><th rowspan="2">P<sub>X,Y</sub></th><th colspan="7">Y</th></tr><tr><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr><tr><th></th><th colspan="8">g(Y) = 0</th></tr></thead><tbody><tr><th>0</th><td>0.1</td><td>0.05</td><td>*</td><td>*</td><td>0.05</td><td>0.05</td><td>*</td><td>*</td></tr><tr><th>1</th><td>0.1</td><td>*</td><td>0.05</td><td>*</td><td>0.05</td><td>0.05</td><td>0.05</td><td>*</td></tr><tr><th>2</th><td>0.1</td><td>*</td><td>*</td><td>0.05</td><td>*</td><td>0.05</td><td>*</td><td>*</td></tr><tr><th>3</th><td>*</td><td>0.05</td><td>0.05</td><td>0.05</td><td>*</td><td>0.05</td><td>*</td><td>0.05</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">f(·, ·)</th><th colspan="7">Y</th></tr><tr><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr><tr><th></th><th colspan="8">g(Y) = 0</th></tr></thead><tbody><tr><th>0</th><td>a</td><td>b</td><td>*</td><td>*</td><td>b</td><td>a</td><td>*</td><td>*</td></tr><tr><th>1</th><td>a</td><td>*</td><td>b</td><td>*</td><td>a</td><td>a</td><td>b</td><td>*</td></tr><tr><th>2</th><td>b</td><td>*</td><td>*</td><td>c</td><td>*</td><td>b</td><td>*</td><td>*</td></tr><tr><th>3</th><td>*</td><td>c</td><td>c</td><td>c</td><td>*</td><td>c</td><td>*</td><td>c</td></tr></tbody></table>

Figure 6.3 – An example of $P_{X,Y}$ and $g$ that satisfy (6.14); along with the outcomes $f(X, Y)$. The elements outside supp $P_{X,Y}$ are denoted by *.

Consider the probability distribution and function outcomes depicted in Figure 6.3, with $\mathcal{U} = \{a, b, c\}$, $\mathcal{X} = \{0, \dots, 3\}$, $\mathcal{Y} = \{0, \dots, 7\}$, and $\mathcal{Z} = \{0, 1\}$. Let us show that the “pairwise shared side information” assumption is satisfied. The source symbols $0, 1, 2 \in \mathcal{X}$ share the side information symbol 0 (resp. 5) when $g(Y) = 0$ (resp. $g(Y) = 1$). The source symbol 3 $\in \mathcal{X}$ shares the side information symbols 1, 2, 3 with the source symbols 0, 1, 2, respectively, when $g(Y) = 0$; and the source symbol 3 shares the side information symbol 5 with all other source symbols when $g(Y) = 1$.

Since the “pairwise shared side information” assumption is satisfied, we can use Theorem 6.3.6; the optimal rate writes

$$R_{CFC0}^* = P_{g(Y)}(0)H_{\kappa}(G_0^f) + P_{g(Y)}(1)H_{\kappa}(G_1^f). \quad (6.20)$$

First we need to determine the probabilistic graphs $G_0^f$ and $G_1^f$. In $G_0^f$, the vertex 0 is adjacent to 2 and 3, as $f(0,0) \neq f(2,0)$ and $f(0,1) \neq f(3,1)$. The vertex 1 is also adjacent to 2 and 3 as $f(1,0) \neq f(2,0)$ and $f(1,2) \neq f(3,2)$. Furthermore $P_{X|g(Y)=0}$ is uniform, hence $G_0^f = (C_4, \text{Unif}(\mathcal{X}))$ where $C_4$ is the cycle graph with 4 vertices.

In $G_1^f$, the vertices 1, 2, 3 are pairwise adjacent as $f(1,5)$, $f(2,5)$ and $f(3,5)$ are pairwise different; and 0 is adjacent to 1, 2 and 3 because of the different function outputs generated by $Y=4$ and $Y=5$. Thus, $G_1^f = (K_4, P_{X|g(Y)=1})$ with $P_{X|g(Y)=1} = (\frac{1}{4}, \frac{3}{8}, \frac{1}{8}, \frac{1}{4})$
and $K_4$ is the complete graph with 4 vertices.

Now let us determine $H_κ(G_0^f)$ and $H_κ(G_1^f)$. On one hand,

$$H_κ(G_0^f) = H(V_0) - \max_{V_0 \in W \in \Gamma(G_0^f)} H(V_0|W) \quad (6.21)$$

$$= 2 - 1 = 1, \quad (6.22)$$

with $V_0 \sim P_{X|g(Y)=0} = \text{Unif}(\mathcal{X})$; and where $H(V_0|W)$ in (6.21) is maximized by taking $W = \{0, 1\}$ when $V \in \{0, 1\}$, and $W = \{2, 3\}$ otherwise.

On the other hand,

$$H_κ(G_1^f) = \min_{V_1 \in W \in \Gamma(G_1^f)} I(W; V_1) \quad (6.23)$$

$$= H(V_1) \approx 1.906, \quad (6.24)$$

with $V_1 \sim P_{X|g(Y)=1}$; where (6.24) follows from $\Gamma(G_1^f) = \{\{0\}, \dots, \{3\}\}$, as $G_1^f$ is complete. Hence $R_{CFC}^* \approx 1.362$.

The rate that we would obtain by transmitting $X$ knowing $g(Y)$ at both encoder and decoder with a conditional Huffman algorithm writes: $R_{\text{Huff}} = H(X|g(Y)) \approx 1.962$.

The rate that we would obtain without exploiting $g(Y)$ at the encoder is $R_{\text{No } g} = H(X) \approx 1.985$, because of the different function outputs generated by $Y = 4$ and $Y = 5$.

Finally, $H(f(X, Y)|Y) \approx 0.875$.

In this example we have

$$H(X) = R_{\text{No } g} > R_{\text{Huff}} > R_{\text{CFC0}}^* > H(f(X, Y)|Y). \quad (6.25)$$

This illustrates the impact of the side information at the encoder in this setting, as we can observe a large gap between the optimal rate $R_{\text{CFC}}^*$ and $R_{\text{No } g}$.
CONCLUSION

We have shown the equivalences of linearization between $C_0$, $C(\cdot, P_V)$, and $\overline{H}$. Therefore, we proved the equivalence between the suboptimality of separated zero-error coding on independent channels; and the suboptimality of separated compression of independent sources in the zero-error Slepian-Wolf setting, with same characteristic graph and capacity-achieving distribution.

We also state the following open questions:

- As pointed out in Lemma 5.3.3, for all capacity-achieving distribution of a product graph, the product of its marginals is also capacity-achieving. Are these marginals capacity-achieving for the respective graphs in the product; and conversely, if we consider the product of capacity-achieving distributions of graphs, is this distribution capacity-achieving for the product of graphs? In other words,

$$ \mathcal{P}^*\left(\bigwedge_{a \in \mathcal{A}} G_a\right) \cap \bigotimes_{a \in \mathcal{A}} \Delta(\mathcal{V}_a) \stackrel{?}{=} \bigotimes_{a \in \mathcal{A}} \mathcal{P}^*(G_a). \qquad (6.26) $$

We gave a partial answer in Theorem 5.4.1, in the sense that inclusion holds when the linearization of the product holds.

- We have shown in Theorem 5.4.1 and Theorem 5.4.2 that the linearization of $C_0$ holds if and only if the linearization of $C(\cdot, P_V)$ holds, where $P_V$ is any capacity-achieving distribution. Can we find graphs such that the linearization of $C(\cdot, P_V)$ holds when $P_V$ is capacity-achieving, but does not hold for some $P_V$ that is not capacity-achieving? A negative answer would imply that the linearization of $C_0$ is equivalent to the linearization of $C(\cdot, P_V)$ and $\overline{H}$ for all $P_V$, similarly to perfect graphs.

- Finally, we have seen in Corollary 5.5.10 that $\overline{H}(G \wedge (C_5, \text{Unif}(\{1, \dots, 5\})))$ with $G$ perfect is an example of linearization. Is the non-linearization of $\overline{H}(\wedge \cdot)$ tied to specific non-perfect induced subgraphs in each graph in the product? And if so, can we find a minimal family of these graphs?
<figure><img src="image_22.png" /></figure>
# PROOFS FOR CORRECTION-BASED
ZERO-ERROR RESULTS

## A.1 Proof of Lemma 4.2.5

Let us prove that

$$R_1^{(n)} \underset{n \to \infty}{\to} H(X|Y) + \delta, \quad R_2^{(n)} \underset{n \to \infty}{\to} I(X;Y). \qquad (A.1)$$

### A.1.1 Preliminaries

**Lemma A.1.1** Let $X'$ be a random variable such that $P_{X'} = \text{Unif}(\mathcal{X})$. Then for all $(x^n, y^n) \in \mathcal{X}^n \times \mathcal{Y}^n$, we have:

$$\mathbb{P}(T_{X^n, y^n} = T_{x^n, y^n}) = 2^{nH(T_{x^n, y^n}) - nH(T_{y^n}) - n \log |\mathcal{X}| + o(n)} \qquad (A.2)$$

*Proof.* Since $P_{X'}$ is uniform:

$$\begin{align}
\mathbb{P}(T_{X^n, y^n} = T_{x^n, y^n}) &= |\mathcal{X}|^{-n} |\mathcal{T}_{Q_{x^n|y^n}}(y^n)| \tag{A.3} \\
&= 2^{-n \log |\mathcal{X}|} 2^{nH(T_{x^n, y^n}) - nH(T_{y^n}) + o(n)}, \nonumber
\end{align}$$

as [20, Lemma 2.5] gives the asymptotic size of the $T_{x^n|y^n}$-shell $\mathcal{T}_{T_{x^n|y^n}}(y^n)$.

<figure><img src="image_23.png" /></figure>

### A.1.2 Probability of decoding ambiguity

We need to estimate $\mathbb{P}(E = 1)$. We have $E = 1$ iff $K = 0$ or there exists $(a_1, ..., a_K) \in \mathcal{X}^K \setminus \{0, ..., 0\}$ such that $T_{(X^n + \sum_{i \le K} a_i \mathbf{G}_K^{(i)}, Y^n)} = T_{X^n, Y^n}$, where $\mathbf{G}_K^{(i)}$ denotes the $i$-th
column of the matrix $G_K$. Thus

$$ \mathbb{P}(E=1) \le \mathbb{P}(K=0) + \mathbb{P}\left( \bigcup_{\substack{a^k \in \mathcal{X}^K \\ a \ne 0}} \left[ T\left(X^{n+\sum_{i \le K} a_i G_K^{(i)}\right), Y^n\right] = T_{X^n, Y^n} \bigg| K \ne 0 \right). \quad (A.4) $$

We provide an upper bound on the second term in (A.4). For all $(x^n, y^n)$ such that $k \ne 0$, we have:

$$ \mathbb{P}\left( \bigcup_{\substack{a^k \in \mathcal{X}^k \\ a \ne 0}} \left[ T\left(x^n + \sum_{i \le k} a_i G_K^{(i)}\right), y^n \right] = T_{x^n, y^n} \right) \le \sum_{\substack{a^k \in \mathcal{X}^k \\ a \ne 0}} \mathbb{P}\left( T\left(x^n + \sum_{i \le k} a_i G_K^{(i)}\right), y^n \right) \quad (A.5) $$

$$ \le \left|\mathcal{X}\right|^k 2^{nH(T_{x^n, y^n}) - nH(T_{y^n}) - n \log |\mathcal{X}| + o(n)} \quad (A.6) $$

$$ \le 2^{n \log |\mathcal{X}| - nH(T_{x^n, y^n}) + nH(T_{y^n}) - \delta n + o(n)} $$

$$ \cdot 2^{nH(T_{x^n, y^n}) - nH(T_{y^n}) - n \log |\mathcal{X}| + o(n)} \quad (A.7) $$

$$ \le 2^{-\delta n + o(n)}, \quad (A.8) $$

where (A.6) comes from Lemma A.1.1 and (A.8) comes from (4.43). Therefore,

$$ \mathbb{P}\left( \bigcup_{\substack{a^K \in \mathcal{X}^K \\ a \ne 0}} \left[ T\left(X^n + \sum_{i \le K} \alpha_i G_K^{(i)}\right), Y^n \right] = T_{X^n, Y^n} \bigg| K \ne 0 \right) \le \sum_{x^n, y^n} \mathbb{P}\left( (X^n, Y^n) = (x^n, y^n) \bigg| K \ne 0 \right) \quad (A.9) $$

$$ \cdot \mathbb{P}\left( \bigcup_{\substack{a^K \in \mathcal{X}^K \\ a \ne 0}} \left[ T\left(X^n + \sum_{i \le K} \alpha_i G_K^{(i)}\right), Y^n \right] = T_{X^n, Y^n} \bigg| K \ne 0, (X^n, Y^n) = (x^n, y^n) \right) \le \sum_{x^n, y^n} \mathbb{P}\left( (X^n, Y^n) = (x^n, y^n) \bigg| K \ne 0 \right) 2^{-\delta n + o(n)} \quad (A.10) $$

$$ \le 2^{-\delta n + o(n)}, \quad (A.11) $$

where (A.10) comes from (A.8) and the fact that $G$ is independent of $(X, Y)$.
We now provide an upper bound on the first term in (A.4).

$$ \mathcal{S} \doteq \left\{ P_{X',Y'} \in \Delta(\mathcal{X} \times \mathcal{Y}) \;\middle|\; 1 - \frac{H(X'|Y') + \delta}{\log |\mathcal{X}|} \le 0 \right\}. \quad (A.12) $$

Then we have:

$$ \mathbb{P}(K = 0) \quad (A.13) $$

$$ = \sum_{(x^n, y^n) \in \mathcal{X}^n \times \mathcal{Y}^n} \mathbb{P} \left( n - n \frac{H(T_{x^n, y^n}) - H(T_{y^n}) + \delta}{\log |\mathcal{X}|} \le 0 \right) P_{X,Y}^{\otimes n} (x^n, y^n) \quad (A.14) $$

$$ = \mathbb{P}(T_{X^n, Y^n} \in \mathcal{S}) \quad (A.15) $$

$$ = \sum_{P_{X',Y'} \in \mathcal{S} \cap \Delta_n(\mathcal{X} \times \mathcal{Y})} \mathbb{P}(T_{X^n, Y^n} = P_{X',Y'}) \quad (A.16) $$

$$ \le |\mathcal{S} \cap \Delta_n(\mathcal{X} \times \mathcal{Y})| \sup_{P_{X',Y'} \in \mathcal{S} \cap \Delta_n(\mathcal{X} \times \mathcal{Y})} \mathbb{P}(T_{X^n, Y^n} = P_{X',Y'}) \quad (A.17) $$

$$ \le |\mathcal{S} \cap \Delta_n(\mathcal{X} \times \mathcal{Y})| \sup_{P_{X',Y'} \in \mathcal{S} \cap \Delta_n(\mathcal{X} \times \mathcal{Y})} 2^{-nD(P_{X',Y'} \| P_{X,Y})} \quad (A.18) $$

$$ \le |\mathcal{S} \cap \Delta_n(\mathcal{X} \times \mathcal{Y})| \sup_{P_{X',Y'} \in \mathcal{S}} 2^{-nD(P_{X',Y'} \| P_{X,Y})} \quad (A.19) $$

$$ \le 2^{-n \inf_{P_{X',Y'} \in \mathcal{S}} D(P_{X',Y'} \| P_{X,Y}) + o(n)}, \quad (A.20) $$

where (A.18) comes from [20, Lemma 2.6]. Since $P_{X,Y} \notin \mathcal{S}$ by definition of $\delta$, we have $\inf_{P_{X',Y'} \in \mathcal{S}} D(P_{X,Y} \| P_{X',Y'}) > 0$. Thus there exists a positive constant $\beta > 0$ such that

$$ \mathbb{P}(K = 0) \le 2^{-\beta n + o(n)}. \quad (A.21) $$

Thus by combining (A.4), (A.11), (A.21), we have:

$$ \mathbb{P}(E = 1) \le 2^{-\delta n + o(n)} + 2^{-\beta n + o(n)}. \quad (A.22) $$

### A.1.3 Rate on the common channel

The encoding function $\phi_e^{(1)}$ defined in (4.44) returns $T_{X^n, Y^n}$ and $E$. When $E = 0$, it sends the syndrome $\mathbf{H}_K X^n$ at rate $\frac{n-K}{n} \log |\mathcal{X}|$, otherwise, it sends $X^n$. Therefore,

$$ nR_1^{(n)} \quad (A.23) $$

$$ = 1 + |\mathcal{X}| |\mathcal{Y}| \log(n+1) + \mathbb{P}(E=1) n \log |\mathcal{X}| \quad (A.24) $$
$$ + \mathbb{P}(E=0) \sum_{x^n, y^n} \mathbb{P}((X^n, Y^n) = (x^n, y^n) | E=0) \cdot (n-k) \log |\mathcal{X}| \\ \le 1 + |\mathcal{X}||\mathcal{Y}| \log(n+1) + \mathbb{P}(E=1) n \log |\mathcal{X}| + (n - \mathbb{E}[K]) \log |\mathcal{X}| \quad (A.25) $$

$$ \le 1 + |\mathcal{X}||\mathcal{Y}| \log(n+1) + \mathbb{P}(E=1) n \log |\mathcal{X}| + n \mathbb{E} \left[ H_{T_{X^n, Y^n}}(X|Y) \right] + n\delta + 1, \quad (A.26) $$

where $H_{T_{X^n, Y^n}}(X|Y)$ denotes a random variable, which is the conditional entropy computed with the distribution $T_{X^n, Y^n}$; (A.25) comes from $n-k \ge 0$ for all $(x^n, y^n)$, and (A.26) comes from (4.43).

By the law of large numbers [18, Theorem 11.2.1] $\mathbb{E}[H_{T_{X^n, Y^n}}(X|Y)] \xrightarrow{n \to \infty} H(X|Y)$, and by using (A.22), we obtain

$$ \lim_{n \to \infty} R_1^{(n)} \le H(X|Y) + \delta. \quad (A.27) $$

### A.1.4 Rate on the secondary channel

The encoding function $\phi_e^{(2)}$ is defined in (4.45). If $E=0$, then $K \ne 0$ and the encoder transmits the index of $X^n$ in its coset. The Huffman algorithm has an average output length $R_2^{(n)}$ that satisfies

$$ R_2^{(n)} \le \frac{1}{n} \left( 1 + \sum_{k \ne 0} \mathbb{P}(K=k|E=0) \cdot H(X^n|\mathbf{H}_k X^n, K=k, \mathcal{C}, E=0) \right) \quad (A.28) $$

$$ = \frac{1}{n} + \frac{1}{n} H(X^n|K, \mathcal{C}, E=0) - \frac{1}{n} H(\mathbf{H}_K X^n|K, \mathcal{C}, E=0), \quad (A.29) $$

where (A.29) follows from the fact that $\mathbf{H}_K X^n$ is a deterministic function of $X^n$, given a random code $\mathcal{C}$.

We now provide an upper bound to the last term $-\frac{1}{n}H(\mathbf{H}_K X^n|K, \mathcal{C}, E=0)$ in (A.29). To do so, we introduce a new encoding scheme that first encodes the sequences $X^n$ and $Y^n$ with the encoding function $\phi_e^{(1)}$, and then encode the output by using an entropy coder. The rate of this code $r$ is upperbounded by $H(\phi_e^{(1)}(X^n, Y^n)|\mathcal{C}) + 1$.

Moreover, the decoder 1 retrieves $X^n$ with zero error (see Section 4.2.3), and the entropy coder is also lossless. Thus $r$ is greater than the rate achieved by a conditional entropy coder that compresses $X^n$ knowing the side information $Y^n$, whose rate is lower bounded by $nH(X|Y)$.
Therefore, we have

$$nH(X|Y) \le r \qquad (A.30)$$

$$< H(\phi_e^{(1)}(X^n, Y^n)|\mathcal{C}) + 1 \qquad (A.31)$$

$$= 1 + H(T_{X^n, Y^n}, E|\mathcal{C}) + \mathbb{P}(E = 0)H(\mathbf{H}_K X^n|T_{X^n, Y^n}, \mathcal{C}, E = 0) \\ + \mathbb{P}(E = 1)H(X^n|T_{X^n, Y^n}, \mathcal{C}, E = 1) \qquad (A.32)$$

$$\le H(\mathbf{H}_K X^n|T_{X^n, Y^n}, \mathcal{C}, E = 0) + o(n) \qquad (A.33)$$

$$= H(\mathbf{H}_K X^n|T_{X^n, Y^n}, K, \mathcal{C}, E = 0) + o(n) \qquad (A.34)$$

$$\le H(\mathbf{H}_K X^n|K, \mathcal{C}, E = 0) + o(n) \qquad (A.35)$$

where $o(n)$ in (A.33) corresponds to the term $1+H(T_{X^n, Y^n}, E|\mathcal{C})+\mathbb{P}(E = 1)H(X^n|T_{X^n, Y^n}, \mathcal{C}, E = 1)$, and (A.34) follows from the fact that $K$ is a deterministic function of $T_{X^n, Y^n}$.

We now provide an upper bound on the second term of (A.29).

$$\frac{1}{n}H(X^n|K, \mathcal{C}, E = 0) \le \frac{1}{n\mathbb{P}(E = 0)} \left( H(X^n|K, \mathcal{C}, E) - \mathbb{P}(E = 1)H(X^n|K, \mathcal{C}, E = 1) \right) \\ \le \frac{1}{n}H(X^n|K, \mathcal{C}, E) + o(1) \qquad (A.36)$$

$$\le H(X) + o(1). \qquad (A.37)$$

By combining (A.29), (A.35) and (A.37), we obtain

$$\lim_{n \to \infty} R_2^{(n)} \le I(X; Y). \qquad (A.38)$$

**Conclusion.** The rates in (A.27) and (A.38) are evaluated on average over the random code $\mathcal{C}$ with a parameter $\delta > 0$ arbitrarily small. This shows that there exists a sequence of $(n, R_1^{(n)}, R_2^{(n)})$-zero-error source codes, such that

$$(R_1^{(n)}, R_2^{(n)}) \underset{n \to \infty}{\to} (H(X|Y), I(X; Y)). \qquad (A.39)$$
<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

Coset of $x^n$: ♦

Coset of $y^n$: ◇

$Q_{U,W|X}$- and $Q_{V,W|Y}$-shells of sequences in cosets: —

<caption>Figure A.1 – An illustration of the encoding algorithm.</caption>

**A.2 Proof of Theorem 4.3.1**

**A.2.1 Outline**

The encoding algorithm is depicted in Figure A.1. First, for all realization $(x^n, y^n)$ of the source, a codeword $w^n$ is selected from a random codebook that captures the common information between X and Y. Then the bin index of $w^n$ is sent on the channel with encoding function $\phi_e^{(0)}$; the number of bins is adjusted to the worst side information. Using the V-shells of their respective side information $u^n$ and $v^n$, both decoders retrieve $w^n$. Finally, the coset of $x^n$ sent on the channel with encoding function $\phi_e^{(x_1)}$, and the pair $(w^n, u^n)$ (resp. $(w^n, v^n)$ and the coset of $y^n$) enables the decoder $\mathbf{x}_1$ (resp. $\mathbf{Y}$) to recover $x^n$ (resp. $y^n$). An information complement is sent to the decoder $\mathbf{x}_2$ so that it can recover
$x^n$ as well.

## A.2.2 Encoding algorithm

Let $P_{W|U,V,X,Y} \in \Delta(\mathcal{W})^{|U \times V \times X \times Y|}$, let $\delta > 0$, and let $n \in \mathbb{N}^*$. For all type $Q_{U,V,X,Y} \in \Delta_n(\mathcal{U} \times \mathcal{V} \times \mathcal{X} \times \mathcal{Y})$, let $Q_{U,V,W,X,Y}$ be the type from $\Delta_n(\mathcal{U} \times \mathcal{V} \times \mathcal{W} \times \mathcal{X} \times \mathcal{Y})$ that has $Q_{U,V,X,Y}$ as marginal distribution and minimizes $D(P_{U,V,W,X,Y} || Q_{U,V,W,X,Y})$, so we have

$$Q_{U,V,W,X,Y} \xrightarrow{Q_{U,V,X,Y} \to P_{U,V,X,Y}} P_{U,V,W,X,Y}. \qquad (A.40)$$

In the following, we denote by $H_Q(\cdot)$ and $I_Q(\cdot; \cdot)$ the entropy and mutual information that are computed w.r.t. $Q$, instead of the true distribution of $P_{U,V,W,X,Y}$.

Now, for a fixed type $Q_{U,V,W,X,Y}$, partition $\mathcal{T}_0^n(Q_X)$ (resp. $\mathcal{T}_0^n(Q_Y)$) into $2^{nH_Q(X|U,W)+n\delta}$ (resp. $2^{nH_Q(Y|V,W)+n\delta}$) cosets, using adequate generator and parity matrices $\mathbf{G}_X$ and $\mathbf{H}_X$ (resp. $\mathbf{G}_Y$ and $\mathbf{H}_Y$), cf. Lemma 4.3.5. This is possible as $|\mathcal{X}|$ and $|\mathcal{Y}|$ can be assumed prime w.l.o.g. by padding (i.e. completing with zeros) $Q$ if necessary.

Let $\mathcal{C}_W$ be a set of codewords formed with $2^{nI_Q(U,V,X,Y;W)+n\delta}$ random sequences drawn from $\mathcal{W}^n$ independently and following the distribution $Q_W$. Let $\mathcal{Z}$ be a finite set such that

$$|\mathcal{Z}| = \frac{|\mathcal{C}_W|}{2^{n \min(I_Q(U;W), I_Q(V;W))-n\delta}} \qquad (A.41)$$

$$= 2^{nI_Q(U,V,X,Y;W)-n \min(I_Q(U;W), I_Q(V;W))+2n\delta}. \qquad (A.42)$$

A bin label $b(\bar{w}^n)$ drawn uniformly in $\mathcal{Z}$ is assigned to each sequence $\bar{w}^n \in \mathcal{C}_W$, so we have $2^{n \min(I_Q(U;W), I_Q(V;W))-n\delta+o(n)}$ sequences in each bin. In the following we will denote by $\mathcal{C}_W^{[b(w^n)]}$ the subset of sequences from $\mathcal{C}_W$ in the bin labelled $b(w^n)$.

Now let $(u^n, v^n, x^n, y^n)$ be a realization of the source, and $Q_{U,V,X,Y}$ the corresponding type. Let $Q_{U,V,W,X,Y}$ be the completed type as described above. The encoder determines a sequence $w^n \in \mathcal{T}_{Q_{U,V,X,Y}}(u^n, v^n, x^n, y^n)$ and its bin label $b(w^n)$; if no such sequence exists then the decoding ambiguity $\mathcal{E}_1$ is declared.

The encoder sends:

$$\phi_e^{(x_1)}(u^n, v^n, x^n, y^n) = B(\mathbf{H}_X x^n), \qquad (A.43)$$

$$\phi_e^{(x_2)}(u^n, v^n, x^n, y^n) = \iota, \qquad (A.44)$$
$$ \phi_e^{(y)}(u^n, v^n, x^n, y^n) = B(\mathbf{H}_Y y^n), \qquad (A.45) $$

$$ \phi_e^{(0)}(u^n, v^n, x^n, y^n) \qquad (A.46) $$

$$ = B \left( Q_{U,V,W,X,Y}, b(w^n), \begin{cases} E, & x^n, y^n \quad \text{if } E = 1 \\ E, & \text{if } E = 0 \end{cases} \right), $$

where $B(\cdot)$ denotes the binary expansion, and $\iota$ denotes the index of $x^n$ in $(\text{Ker } \mathbf{H}_X + x^n) \cap \bigcup_{\tilde{w}^n \in C_W^{[b(w^n)]}} \mathcal{T}_{Q_{X|W}}(\tilde{w}^n)$.

The error bit $E$ is set to 1 iff there is a decoding ambiguity, i.e. one of the following events occur:

$$ \mathcal{E}_1 = \{ \nexists w^n \in C_W, \text{ s.t. } T_{u^n, v^n, w^n, x^n, y^n} = Q_{U,V,W,X,Y} \}, $$

$$ \mathcal{E}_2 = \{ \exists \tilde{w}^n \neq w^n, \tilde{w}^n \in C_W^{[b(w^n)]} \cap \mathcal{T}_{Q_{W|U}}(u^n) \}, $$

$$ \mathcal{E}_3 = \{ \exists \tilde{w}^n \neq w^n, \tilde{w}^n \in C_W^{[b(w^n)]} \cap \mathcal{T}_{Q_{W|V}}(v^n) \}, $$

$$ \mathcal{E}_4 = \{ \exists \tilde{x}^n \neq x^n, \tilde{x}^n \in \mathcal{T}_{Q_{X|U,W}}(u^n, w^n) \cap (\text{Ker } \mathbf{H}_X + x^n) \}, $$

$$ \mathcal{E}_5 = \{ \exists \tilde{y}^n \neq y^n, \tilde{y}^n \in \mathcal{T}_{Q_{Y|V,W}}(v^n, w^n) \cap (\text{Ker } \mathbf{H}_Y + y^n) \}. $$

### A.2.3 Decoding algorithm and zero-error property

All decoders determine whether there is a decoding ambiguity. If so, they recover their respective source sequence from the channel with encoding function $\phi_e^{(0)}$. If not, then the following procedure is followed.

The decoder $x_1$ recovers $b(w^n)$ from the channel with encoding function $\phi_e^{(0)}$ ($\mathcal{E}_1^c \Rightarrow w^n$ is defined), and using the side information $u^n$, it searches the $V$-shell $\mathcal{T}_{Q_{W|U}}(u^n)$ to find the sequences with label $b(w^n)$, and retrieves $w^n$ ($\mathcal{E}_2^c \Rightarrow w^n$ is retrieved at decoder $x_1$). The coset $(\text{Ker } \mathbf{H}_X + x^n)$ is then extracted from the channel with encoding function $\phi_e^{(x_1)}$, the decoder $x_1$ then searches the set $\mathcal{T}_{Q_{X|U,W}}(u^n, w^n) \cap (\text{Ker } \mathbf{H}_Y + y^n)$ and retrieves $x^n$ with zero-error ($\mathcal{E}_4^c \Rightarrow x^n$ is retrieved).

The decoder $y$ proceeds symmetrically and recovers $y^n$ with the help of $v^n$ as $\mathcal{E}_1, \mathcal{E}_3, \mathcal{E}_5$ are not realised.

The decoder $x_2$ determines $(\text{Ker } \mathbf{H}_X + x^n) \cap \bigcup_{\tilde{w}^n \in C_W^{[b(w^n)]}} \mathcal{T}_{Q_{X|W}}(\tilde{w}^n)$ using the syndrome $\mathbf{H}_X x^n$ transmitted in the channel with encoding function $\phi_e^{(x_1)}$, and $Q_{U,V,W,X,Y}, b(w^n)$ sent through the channel with encoding function $\phi_e^{(0)}$. Then by using the index sent on the
channel with encoding function $\phi_e^{(x_2)}$, the decoder $x_2$ recovers $x^n$ with zero-error.

### A.2.4 Probability of a decoding ambiguity

Let us bound $\mathbb{P}(\mathcal{E}_1)$. We have $\mathbb{P}(\mathcal{E}_1) \le 2^{-n\delta+o(n)}$ by using Lemma 4.3.3, with $\mathcal{A} = \mathcal{W}$, $\mathcal{B} = \mathcal{U} \times \mathcal{V} \times \mathcal{X} \times \mathcal{Y}$, $P_{A,B} = Q_{W,(U,V,X,Y)}$ and $P_{\bar{A}} = Q_W$.

Now let us bound $\mathbb{P}(\mathcal{E}_2)$. The set $C_W^{[b(w^n)]} \setminus \{w^n\}$ is composed of $2^{n \min(I_Q(U;W),I_Q(V;W))-n\delta+o(n)}$ sequences drawn with the same distribution $Q_W$. We can use Lemma 4.3.3 with $\mathcal{A} = \mathcal{W}$, $\mathcal{B} = \mathcal{U}$, $P_{A,B} = Q_{W,U}$ and $P_{\bar{A}} = Q_W$:

$$ \mathbb{P}(\mathcal{E}_2) \le 2^{n \min(I_Q(U;W),I_Q(V;W))-n\delta-nI_Q(U;W)+o(n)} \quad (A.47) $$

$$ \le 2^{-n\delta+o(n)}. \quad (A.48) $$

Symmetrically, we have $\mathbb{P}(\mathcal{E}_3) \le 2^{-n\delta+o(n)}$.

In order to bound the remaining probabilities we use Lemma 4.3.5 with $\mathcal{A} = \mathcal{X}$, $\mathcal{B} = \mathcal{U} \times \mathcal{W}$, $P_{A,B} = Q_{X,(U,W)}$:

$$ \begin{aligned} \mathbb{P}(\mathcal{E}_4) & \le 2^{n(\log |\mathcal{X}| - H_Q(X|U,W) - \delta - \log |\mathcal{X}| + H_Q(X|U,W)) + o(n)} \\ & \le 2^{-n\delta+o(n)}, \end{aligned} \quad (A.49) $$

and symmetrically, we have $\mathbb{P}(\mathcal{E}_5) \le 2^{-n\delta+o(n)}$. Thus, $\mathbb{P}(E=1) \le 5 \cdot 2^{-\delta n+o(n)}$.

### A.2.5 Rate analysis

Let $\mathcal{S} = \mathcal{U} \times \mathcal{V} \times \mathcal{W} \times \mathcal{X} \times \mathcal{Y}$, the rate on the channel with encoding function $\phi_e^{(0)}$ writes:

$$ \begin{aligned} R_0^{(n)} = & \frac{1}{n} \log |\mathcal{Z}| + \frac{1}{n} \left( 1 + \mathbb{P}(E=1) n \log (|\mathcal{X}| |\mathcal{Y}|) \right) \\ & + \frac{1}{n} \log |\Delta_n(\mathcal{S})| \end{aligned} \quad (A.50) $$

$$ \begin{aligned} & \le I_Q(U, V, X, Y; W) - \min(I_Q(U; W), I_Q(V; W)) + 2\delta \\ & + \frac{1}{n} + 5 \log (|\mathcal{X}| |\mathcal{Y}|) 2^{-n\delta+o(n)} + \frac{1}{n} \log |\Delta_n(\mathcal{S})| \end{aligned} \quad (A.51) $$

$$ \rightarrow_{n \to \infty} I(U, V, X, Y; W) - \min(I(U; W), I(V; W)) + 2\delta. $$

The following rates are the exponent of the number of cosets:
$R_{x_1}^{(n)} = \frac{1}{n} \log (2^{nH_Q(X|U,W)+n\delta}) \underset{n\to\infty}{\to} H(X|U,W) + \delta$, and symmetrically, $R_y^{(n)} \underset{n\to\infty}{\to} H(Y|V,W) + \delta$.

The rate $R_{x_2}^{(n)}$ on the channel with encoding function $\phi_e^{(x_2)}$ writes:

$$ \frac{1}{n} \log \left| (\text{Ker } \mathbf{H}_X + x^n) \cap \bigcup_{\bar{w}^n \in \mathcal{C}_W^{[b(w^n)]}} \mathcal{T}_{Q_{X|W}}(\bar{w}^n) \right| \quad (A.52) $$

$$ = \frac{1}{n} \log \left| \bigcup_{\bar{w}^n \in \mathcal{C}_W^{[b(w^n)]}} \mathcal{T}_{Q_{X|W}}(\bar{w}^n) \right| + \frac{1}{n} \log |\text{Ker } \mathbf{H}_X + x^n| - \log |\mathcal{X}| + o(1) \quad (A.53) $$

$$ \leq \frac{1}{n} \log |\mathcal{C}_W^{[b(w^n)]}| + \frac{1}{n} \log |\mathcal{T}_{Q_{X|W}}(w^n)| + (\log |\mathcal{X}| - H_Q(X|U,W) - \delta) - \log |\mathcal{X}| + o(1) \quad (A.54) $$

$$ = \min(I_Q(U; W), I_Q(V; W)) - \delta + H_Q(X|W) - H_Q(X|U, W) - \delta + o(1) \quad (A.55) $$

$$ = \min(I_Q(U; W), I_Q(V; W)) + I_Q(X; U|W) - 2\delta + o(1) \quad (A.56) $$

$$ \underset{n\to\infty}{\to} \min(I(U; W), I(V; W)) + I(X; U|W) - 2\delta \quad (A.57) $$

where (A.53) follows from the independence of the sequences in $\mathcal{C}_W$ and the entries of $\mathbf{G}_X$.

These equations hold for all $\delta > 0$ small enough, thus the rate tuple

$$ \left( \begin{array}{l} I(X, Y, U, V; W) - \min(I(U; W), I(V; W)), \\ H(X|U, W), \\ I(X; U|W) + \min(I(U; W), I(V; W)), \\ H(Y|U, W) \end{array} \right), \quad (A.58) $$

is achievable. By taking the union over all distributions $P_{U,V,W,X,Y}$ we obtain the desired result.

## A.3 Proof of Theorem 4.3.2

Let $S^t = (U^t, V^t, X^t, Y^t)$, for all $t \le n$. For all $i \in \{0, x_1, y\}$ $M_i \doteq \phi_e^{(i)}(S^n)$.
Firstly, we can use Kraft inequality as the set $\mathrm{Im} \phi_e^{(0)}$ is prefix-free, we have

$$ \sum_{w^n \in \mathrm{Im} \phi_e^{(0)}} 2^{-\ell(w^n)} \le 1. \qquad (A.59) $$

Let $\kappa \doteq \sum_{w^n \in \mathrm{Im} \phi_e^{(0)}} 2^{-\ell(w^n)}$, we have $\kappa \le 1$ and $(\frac{2^{-\ell(w^n)}}{\kappa})_{w^n \in \mathrm{Im} \phi_e^{(0)}}$ is a probability distribution.

Secondly,

$$ nR_0 = \mathbb{E}[\ell \circ \phi_e^{(0)}(S^n)] \qquad (A.60) $$

$$ = \sum_{w^n \in \mathrm{Im} \phi_e^{(0)}} \mathbb{P}(\phi_e^{(0)}(S^n) = w^n) \ell(w^n) \qquad (A.61) $$

$$ = - \sum_{w^n \in \mathrm{Im} \phi_e^{(0)}} \mathbb{P}(\phi_e^{(0)}(S^n) = w^n) \log 2^{-\ell(w^n)} \qquad (A.62) $$

$$ = -\log \kappa - \sum_{w^n \in \mathrm{Im} \phi_e^{(0)}} \mathbb{P}(\phi_e^{(0)}(S^n) = w^n) \log \frac{2^{-\ell(w^n)}}{\kappa} \qquad (A.63) $$

$$ \geq - \sum_{w^n \in \mathrm{Im} \phi_e^{(0)}} \mathbb{P}(\phi_e^{(0)}(S^n) = w^n) \log \frac{2^{-\ell(w^n)}}{\kappa} \qquad (A.64) $$

$$ \geq - \sum_{w^n \in \mathrm{Im} \phi_e^{(0)}} \mathbb{P}(\phi_e^{(0)}(S^n) = w^n) \log \mathbb{P}(\phi_e^{(0)}(S^n) = w^n) \qquad (A.65) $$

$$ = H(\phi_e^{(0)}(S^n)) = H(M_0) \qquad (A.66) $$

where (A.64) and (A.65) respectively come from $\kappa \le 1$ and Gibbs inequality.

In the following, $T \sim \mathrm{Unif}(\{1, ..., n\})$ is a random variable independent from the other random variables of the model, $W_t \doteq (M_0, S^{t-1}, U_{t+1}^n, V_{t+1}^n)$ for all $t \le n$. We identify $W \doteq (W_T, T)$, $(U, V, X, Y) \doteq (U_T, V_T, X_T, Y_T)$. We have

$$ nR_0 \ge H(M_0) \qquad (A.67) $$

$$ \ge I(M_0; X^n, Y^n | U^n, V^n) \qquad (A.68) $$

$$ = \sum_{t \le n} I(M_0; X_t, Y_t | U^n, V^n, X^{t-1}, Y^{t-1}) \qquad (A.69) $$

$$ = \sum_{t \le n} I(M_0, S^{t-1}, U_{t+1}^n, V_{t+1}^n; X_t, Y_t | U_t, V_t) \qquad (A.70) $$

$$ - I(S^{t-1}, U_{t+1}^n, V_{t+1}^n; X_t, Y_t | U_t, V_t) $$
$$= \sum_{t \le n} I(W_t; X_t, Y_t | U_t, V_t) \qquad (A.71)$$

$$= nI(W_T; X_T, Y_T | U_T, V_T, T) \qquad (A.72)$$

$$= nI(W; X, Y | U, V), \qquad (A.73)$$

where (A.67) comes from (A.60) to (A.66); (A.69) comes from the chain rule, (A.71) comes from the independence of $S_1, ..., S_n$, and (A.73) comes from the independence of $T$ and $S^n$.

Let us bound $R_{x_1}$:

$$nR_{x_1} \ge H(M_{x_1}) \qquad (A.74)$$

$$\ge I(M_{x_1}; X^n | M_0, U^n) \qquad (A.75)$$

$$= H(X^n | M_0, U^n) - H(X^n | M_{x_1}, M_0, U^n) \qquad (A.76)$$

$$= \sum_{t \le n} H(X_t | M_0, U^n, X^{t-1}) \qquad (A.77)$$

$$\ge \sum_{t \le n} H(X_t | W_t, U_t) \qquad (A.78)$$

$$= nH(X_T | W_T, U_T, T) \qquad (A.79)$$

$$= nH(X | W, U), \qquad (A.80)$$

where (A.77) comes from the zero-error constraint. Symmetrically we obtain $R_y \ge H(Y|W, V)$.

Now, the decoder $x_2$ must retrieve $X$ with zero-error. Using Shannon lossless source coding result [18, Theorem 5.3.1], we have $R_0 + R_{x_1} + R_{x_2} \ge H(X)$.

## A.4 Proof of Lemma 4.3.3

We use the following result, which is a consequence of [20, Lemma 2.6].

**Lemma A.4.1 (Large deviations)** Let $n \in \mathbb{N}$, and $P_{A,B} \in \Delta_n(\mathcal{A} \times \mathcal{B})$. Let $P_{\bar{A}} \in \Delta(\mathcal{A})$ and $\bar{A}^n \sim (P_{\bar{A}})^{\otimes n}$, then we have for all $b^n \in \mathcal{T}_0^n(P_B): \mathbb{P}(T_{\bar{A}^n, b^n} = P_{A,B}) = 2^{-n(I(A;B)+D(P_A||P_{\bar{A}}))+o(n)}$.

$$\text{If } R > R_c: \mathbb{P}(\exists \tilde{a}^n \in \mathcal{C}^{(n)}, \text{ s.t. } T_{\tilde{a}^n, \tilde{b}^n} = P_{A,B}) \qquad (A.81)$$

$$= 1 - \mathbb{P} \left( T_{A^n[1], \tilde{b}^n} \neq P_{A,B} \right)^{2^{nR}} \qquad (A.82)$$
$$ = 1 - \exp \left[ 2^{nR} \ln \left( 1 - 2^{-nR_c+o(n)} \right) \right] \quad (A.83) $$

$$ = 1 - \exp \left[ -2^{n(R-R_c)+o(n)} \right], \quad (A.84) $$

where (A.82) comes from the fact that the random variables ($A_{[i]}^n$) are iid, and (A.83) is a consequence of Lemma A.4.1.

$$ \text{If } R < R_c: \quad \mathbb{P} \left( \exists \tilde{a}^n \in \mathcal{C}^{(n)}, \text{ s.t. } T_{\tilde{a}^n, \tilde{b}^n} = P_{A,B} \right) \quad (A.85) $$

$$ \leq \sum_{i \leq 2^{nR}} \mathbb{P} \left( T_{A_{[i]}^n, \tilde{b}^n} \neq P_{A,B} \right) \quad (A.86) $$

$$ = 2^{nR} 2^{-nR_c+o(n)}. \quad (A.87) $$

The last equation comes from Lemma A.4.1, and from the fact that the variables ($A_{[i]}^n$) are identically distributed.
<figure><img src="image_26.png" /></figure>
# PROOFS FOR GRAPH-BASED ZERO-ERROR RESULTS

## B.1 Proof dependencies

An illustration of the dependencies between the results can be found in Figure B.1. Note that Theorem 5.1.4 already exists in the literature, but we provide a proof based on Lemma 5.1.3 for the sake of completeness.

## B.2 Main proofs for the linearization of $\overline{H}$ and $C(\cdot, P_V)$

### B.2.1 Proof of Lemma 5.2.1

In order to prove Lemma 5.2.1, we prove an asymptotic version stated in Lemma B.2.1. The proof of Lemma B.2.1 is developed in Appendix B.2.3.

**Lemma B.2.1** Let $(\bar{a}_n)_{n \in \mathbb{N}^*} \in \mathcal{A}^{\mathbb{N}^*}$ be any sequence such that $T_{\bar{a}^n} \to P_A$ when $n \to \infty$. Then we have

$$ \overline{H} \left( \bigsqcup_{a \in \mathcal{A}}^{P_A} G_a \right) = \lim_{n \to \infty} \frac{1}{n} H_X \left( \bigwedge_{a \in \mathcal{A}} G_a^{\wedge n T_{\bar{a}^n}(a)} \right). \quad (B.1) $$

Now let us prove Lemma 5.2.1. Let $(\bar{a}_n)_{n \in \mathbb{N}^*}$ be a $k$-periodic sequence such that $T_{\bar{a}^k} = P_A$, then $T_{\bar{a}^{nk}} = T_{\bar{a}^k}$ for all $n \in \mathbb{N}^*$, and $T_{\bar{a}^n} \xrightarrow{n \to \infty} P_A$. We can use Lemma B.2.1 and consider every $k$-th term in the limit:

$$ \overline{H} \left( \bigsqcup_{a \in \mathcal{A}}^{P_A} G_a \right) = \lim_{n \to \infty} \frac{1}{kn} H_X \left( \bigwedge_{a \in \mathcal{A}} G_a^{\wedge kn T_{\bar{a}^k}(a)} \right) \quad (B.2) $$

$$ = \lim_{n \to \infty} \frac{1}{kn} H_X \left( \left( \bigwedge_{a \in \mathcal{A}} G_a^{\wedge k T_{\bar{a}^k}(a)} \right)^{\wedge n} \right) \quad (B.3) $$
<figure><img src="image_27.png" /><figcaption>Figure B.1 – An arrow from A to B means that A is used in the proof of B. Results from the literature are represented with a dashed outline.</figcaption></figure>

$$ = \frac{1}{k} \bar{H} \left( \bigwedge_{a \in \mathcal{A}} G_a^{\wedge k P_A(a)} \right). \qquad (B.4) $$

## B.2.2 Proof of Theorem 5.2.4

In order to prove Theorem 5.2.4, we will need Corollary 5.2.2, Lemma B.2.2 and Lemma B.2.3. In Lemma B.2.2 we give regularity properties of $P_A \mapsto \bar{H}(\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a)$. The proof of Lemma B.2.2 is developed in Appendix B.6.1. Lemma B.2.3 states that if a convex function $\gamma$ of $\Delta(\mathcal{A})$ meets the linear interpolation of $(\gamma(\mathbb{1}_a))_{a \in \mathcal{A}}$, where $(\mathbb{1}_a)_{a \in \mathcal{A}}$ are the extreme points of $\Delta(\mathcal{A})$, then $\gamma$ is linear. We use it for proving the equivalence in Theorem 5.2.4, by considering $\gamma = P_A \mapsto \bar{H}(\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a)$. The proof of Lemma B.2.3 is given in Appendix B.6.2.

**Lemma B.2.2** The function $P_A \mapsto \bar{H}(\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a)$ is convex and $(\log \max_a |V_a|)$-Lipschitz.
**Lemma B.2.3** Let $\mathcal{A}$ be a finite set, and $\gamma: \Delta(\mathcal{A}) \to \mathbb{R}$ be a convex function, and for all $a \in \mathcal{A}$, let $\mathbb{1}_a$ be the distribution that assigns 1 to the symbol $a$ and 0 to the others. Then the following holds:

$$ \exists P_A \in \mathrm{int}(\Delta(\mathcal{A})), \gamma(P_A) = \sum_{a \in \mathcal{A}} P_A(a)\gamma(\mathbb{1}_a) \quad (B.5) $$

$$ \iff \forall P_A \in \Delta(\mathcal{A}), \gamma(P_A) = \sum_{a \in \mathcal{A}} P_A(a)\gamma(\mathbb{1}_a) \quad (B.6) $$

where $\mathrm{int}(\Delta(\mathcal{A}))$ is the interior of $\Delta(\mathcal{A})$ (i.e. the full-support distributions on $\mathcal{A}$).

Now let us prove Theorem 5.2.4:

$$ (\implies) \text{ Assume that } \overline{H}(\Lambda_{a \in \mathcal{A}} G_a) = \sum_{a \in \mathcal{A}} \overline{H}(G_a). $$

We can use Corollary 5.2.2, which states that $\overline{H}(\bigsqcup_{a \in \mathcal{A}}^{\mathrm{Unif}(\mathcal{A})} G_a) = \frac{1}{|\mathcal{A}|} \overline{H}(\Lambda_{a \in \mathcal{A}} G_a)$; hence $\overline{H}(\bigsqcup_{a \in \mathcal{A}}^{\mathrm{Unif}(\mathcal{A})} G_a) = \sum_{a \in \mathcal{A}} \frac{1}{|\mathcal{A}|} \overline{H}(G_a)$. Thus, the function $P_A \mapsto \overline{H}(\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a)$ satisfies (B.5) with the interior point $P_A = \mathrm{Unif}(\mathcal{A})$, and is convex by Lemma B.2.2: by Lemma B.2.3 we have

$$ \forall P_A \in \Delta(\mathcal{A}), \overline{H}(\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a) = \sum_{a \in \mathcal{A}} P_A(a) \overline{H}(G_a). \quad (B.7) $$

(\iff) Conversely, assume (B.7), then $P_A \mapsto \overline{H}(\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a)$ is linear. We can use Corollary 5.2.2, and we have $\overline{H}(\Lambda_{a \in \mathcal{A}} G_a) = |\mathcal{A}| \overline{H}(\bigsqcup_{a \in \mathcal{A}}^{\mathrm{Unif}(\mathcal{A})} G_a) = \sum_{a \in \mathcal{A}} \overline{H}(G_a)$.

## B.2.3 Proof of Lemma B.2.1

We need several lemmas for this result. Lemma B.2.4 establishes the distributivity of $\wedge$ w.r.t. $\sqcup$ for probabilistic graphs, similarly as in [78] for graphs without underlying distribution. Lemma B.2.5 states that $\overline{H}$ can be computed with subgraphs induced by sets that have an asymptotic probability one, in particular we will use it with typical sets of vertices. Lemma B.2.7 gives the chromatic entropy of a disjoint union of isomorphic probabilistic graphs. The proofs of Lemma B.2.4, Lemma B.2.5 and Lemma B.2.7 are respectively given in Appendix B.6.3, Appendix B.6.4, and Appendix B.6.5.

**Lemma B.2.4** Let $\mathcal{A}, \mathcal{B}$ be finite sets, let $P_A \in \Delta(\mathcal{A})$ and $P_B \in \Delta(\mathcal{B})$. For all $a \in \mathcal{A}$ and
$b \in \mathcal{B}$, let $G_a = (\mathcal{V}_a, \mathcal{E}_a, P_{V_a})$ and $G_b = (\mathcal{V}_b, \mathcal{E}_b, P_{V_b})$ be probabilistic graphs. Then

$$ \left( \bigsqcup_{a \in \mathcal{A}}^{P_A} G_a \right) \wedge \left( \bigsqcup_{b \in \mathcal{B}}^{P_B} G_b \right) = \bigsqcup_{(a,b) \in \mathcal{A} \times \mathcal{B}}^{P_A P_B} G_a \wedge G_b. \qquad (B.8) $$

**Lemma B.2.5** Let $G = (\mathcal{V}, \mathcal{E}, P_V)$, and $(S_n)_{n \in \mathbb{N}^*}$ be a sequence of sets such that for all $n \in \mathbb{N}^*$, $S_n \subseteq \mathcal{V}^n$, and $P_V^n(S_n) \to 1$ when $n \to \infty$. Then $\overline{H}(G) = \lim_{n \to \infty} \frac{1}{n} H_X(G^{\wedge n}[S_n])$.

**Definition B.2.6 (Isomorphic probabilistic graphs)** Let $G_1 = (\mathcal{V}_1, \mathcal{E}_1, P_{V_1})$ and $G_2 = (\mathcal{V}_2, \mathcal{E}_2, P_{V_2})$ be two probabilistic graphs. We say that $G_1$ is isomorphic to $G_2$ (denoted by $G_1 \cong G_2$) if there exists an isomorphism between them, i.e. a bijection $\psi: \mathcal{V}_1 \to \mathcal{V}_2$ such that:

- For all $v_1, v'_1 \in \mathcal{V}_1$, $v_1v'_1 \in \mathcal{E}_1 \iff \psi(v_1)\psi(v'_1) \in \mathcal{E}_2$,

- For all $v_1 \in \mathcal{V}_1$, $P_{V_1}(v_1) = P_{V_2}(\psi(v_1))$.

**Lemma B.2.7** Let $\mathcal{B}$ be a finite set, let $P_B \in \Delta(\mathcal{B})$ and let $(G_b)_{b \in \mathcal{B}}$ be a family of isomorphic probabilistic graphs, then $H_X(\bigsqcup_{b' \in \mathcal{B}}^{P_B} G_{b'}) = H_X(G_b)$ for all $b \in \mathcal{B}$.

Now let us prove Lemma B.2.1. Let $P_A \in \Delta(\mathcal{A})$, and let $G = \bigsqcup_{a \in \mathcal{A}}^{P_A} G_a$. Let $(\bar{a}_n)_{n \in \mathbb{N}^*} \in \mathcal{A}^{\mathbb{N}^*}$ be a sequence such that $T_{\bar{a}^n} \to P_A$ when $n \to \infty$.

Let $\epsilon > 0$, and for all $n \in \mathbb{N}^*$ let

$$ \mathcal{T}_{\epsilon}^{n}(P_{A}) \doteq \{a^{n} \in \mathcal{A}^{n} \mid \|T_{a^{n}} - P_{A}\|_{\infty} \le \epsilon\}, \qquad (B.9) $$

$$ P'^n \doteq \frac{P_A^n}{P_A^n(\mathcal{T}_\epsilon^n(P_A))}, \quad \mathcal{S}_{n,\epsilon} \doteq \bigsqcup_{a^n \in \mathcal{T}_\epsilon^n(P_A)} \prod_{t \le n} \mathcal{V}_{a_t}. $$

Since $P_V^n(S_{n,\epsilon}) \to 1$ when $n \to \infty$, we have by Lemma B.2.5

$$ \overline{H}(G) = \lim_{n \to \infty} \frac{1}{n} H_X(G^{\wedge n}[S_{n,\epsilon}]), \qquad (B.10) $$

Let us study the limit in (B.10). For all $n$ large enough, $\bar{a}^n \in \mathcal{T}_\epsilon^n(P_A)$ as $T_{\bar{a}^n} \to P_A$. Therefore, for all $a^n \in \mathcal{T}_\epsilon^n(P_A)$, $a' \in \mathcal{A}$, and $n$ large enough, we have

$$ |T_{\bar{a}^n}(a') - T_{a^n}(a')| \le 2\epsilon. \qquad (B.11) $$
We have on one hand

$$ H_{\chi}((\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a)^{\wedge n} [S_{n,\epsilon}]) = H_{\chi}((\bigsqcup_{a^n \in \mathcal{T}_{\epsilon}^n(P_A)}^{P^n} G_{a_t}) [S_{n,\epsilon}]) \quad (B.12) $$

$$ = H_{\chi} (\bigsqcup_{a^n \in \mathcal{T}_{\epsilon}^n(P_A)}^{P^n} \Lambda_{t \le n} G_{a_t}) \quad (B.13) $$

$$ = H_{\chi} (\bigsqcup_{a^n \in \mathcal{T}_{\epsilon}^n(P_A)}^{P^n} \Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge n T_{\bar{a}}^n(a')}) \quad (B.14) $$

$$ \le H_{\chi} (\bigsqcup_{a^n \in \mathcal{T}_{\epsilon}^n(P_A)}^{P^n} \Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge n T_{\bar{a}}^n(a') + [2n\epsilon]}) \quad (B.15) $$

$$ = H_{\chi} (\Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge n T_{\bar{a}}^n(a') + [2n\epsilon]}) \quad (B.16) $$

$$ \le H_{\chi} (\Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge n T_{\bar{a}}^n(a')}) + H_{\chi} (\Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge [2n\epsilon]}) \quad (B.17) $$

$$ \le H_{\chi} (\Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge n T_{\bar{a}}^n(a')}) + [2n\epsilon] |\mathcal{A}| \log |\mathcal{V}|; \quad (B.18) $$

where (B.12) comes from Lemma B.2.4; (B.13) comes from the definition of $S_{n,\epsilon}$ and $P^n$ in (B.9); (B.14) is a rearrangement of the terms inside the product; (B.15) comes from (B.11); (B.16) follows from Lemma B.2.7, the graphs $(\Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge n T_{\bar{a}}^n(a') + [2n\epsilon]})_{a^n \in \mathcal{T}_{\epsilon}^n(P_A)}$ are isomorphic as they do not depend on $a^n$; (B.17) follows from the subadditivity of $H_{\chi}$; and (B.18) is the upper bound on $H_{\chi}$ given by the highest entropy of a coloring.

On the other hand, we obtain with similar arguments

$$ H_{\chi}((\bigsqcup_{a \in \mathcal{A}}^{P_A} G_a)^{\wedge n} [S_{n,\epsilon}]) \ge H_{\chi} (\Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge n T_{\bar{a}}^n(a') - [2n\epsilon]}) \quad (B.19) $$

$$ \ge H_{\chi} (\Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge n T_{\bar{a}}^n(a')}) - H_{\chi} (\Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge [2n\epsilon]}) \quad (B.20) $$

$$ \ge H_{\chi} (\Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge n T_{\bar{a}}^n(a')}) - [2n\epsilon] |\mathcal{A}| \log |\mathcal{V}|. \quad (B.21) $$

Note that (B.20) also comes from the subadditivity of $H_{\chi}$, as $H_{\chi}(G_2) \ge H_{\chi}(G_1 \wedge G_2) - H_{\chi}(G_1)$ for all $G_1, G_2$.

By combining (B.18) and (B.21) we obtain

$$ \left| \lim_{n \to \infty} \frac{1}{n} H_{\chi}(G^{\wedge n}[S_{n,\epsilon}]) - \lim_{n \to \infty} \frac{1}{n} H_{\chi}(\Lambda_{a' \in \mathcal{A}} G_{a'}^{\wedge n T_{\bar{a}}^n(a')}) \right| \le 2\epsilon |\mathcal{A}| \log |\mathcal{V}|. \quad (B.22) $$

As this holds for all $\epsilon > 0$, combining (B.10) and (B.22) yields the desired result.