<table><thead><tr><th>|G|</th><th>D(G)</th><th>k</th><th>s<sub>≤k</sub>(G)</th><th>Le groupe</th></tr></thead><tbody><tr><td>27</td><td>7</td><td>3</td><td>17</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>3</sub></td></tr><tr><td>27</td><td>7</td><td>4</td><td>10</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>3</sub></td></tr><tr><td>27</td><td>7</td><td>5</td><td>9</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>3</sub></td></tr><tr><td>27</td><td>7</td><td>6</td><td>8</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>3</sub></td></tr><tr><td>27</td><td>7</td><td>∀k ≥ 7</td><td>7</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>3</sub></td></tr><tr><td>27</td><td>11</td><td>∀k ≥ 11</td><td>11</td><td>C<sub>3</sub> ⊕ C<sub>9</sub></td></tr><tr><td>27</td><td>11</td><td>10</td><td>12</td><td>C<sub>3</sub> ⊕ C<sub>9</sub></td></tr><tr><td>27</td><td>11</td><td>9</td><td>13</td><td>C<sub>3</sub> ⊕ C<sub>9</sub></td></tr><tr><td>32</td><td>7</td><td>4</td><td>10</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub></td></tr><tr><td>32</td><td>7</td><td>5</td><td>9</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub></td></tr><tr><td>32</td><td>7</td><td>6</td><td>8</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub></td></tr><tr><td>32</td><td>7</td><td>∀k ≥ 7</td><td>7</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub></td></tr><tr><td>32</td><td>10</td><td>8</td><td>12</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>8</sub></td></tr><tr><td>32</td><td>10</td><td>9</td><td>11</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>8</sub></td></tr><tr><td>32</td><td>10</td><td>10</td><td>10</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>8</sub></td></tr><tr><td>32</td><td>8</td><td>4</td><td>14</td><td>C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>32</td><td>8</td><td>5</td><td>11</td><td>C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>32</td><td>8</td><td>6</td><td>10</td><td>C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>32</td><td>8</td><td>7</td><td>9</td><td>C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>32</td><td>8</td><td>∀k ≥ 8</td><td>8</td><td>C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>32</td><td>6</td><td>2</td><td>32</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub></td></tr><tr><td>32</td><td>6</td><td>3</td><td>17</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub></td></tr><tr><td>32</td><td>6</td><td>4</td><td>7</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub></td></tr><tr><td>32</td><td>6</td><td>5</td><td>7</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub></td></tr><tr><td>32</td><td>6</td><td>∀k ≥ 6</td><td>6</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub></td></tr><tr><td>48</td><td>9</td><td>6</td><td>12</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>6</sub></td></tr><tr><td>48</td><td>9</td><td>7</td><td>11</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>6</sub></td></tr><tr><td>48</td><td>9</td><td>8</td><td>10</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>6</sub></td></tr><tr><td>48</td><td>9</td><td>∀k ≥ 9</td><td>9</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>6</sub></td></tr><tr><td>40</td><td>12</td><td>10</td><td>14</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>10</sub></td></tr><tr><td>40</td><td>12</td><td>11</td><td>13</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>10</sub></td></tr><tr><td>40</td><td>12</td><td>∀k ≥ 12</td><td>12</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>10</sub></td></tr><tr><td>48</td><td>14</td><td>12</td><td>16</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>12</sub></td></tr><tr><td>48</td><td>14</td><td>13</td><td>15</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>12</sub></td></tr><tr><td>48</td><td>14</td><td>∀k ≥ 14</td><td>14</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>12</sub></td></tr><tr><td>54</td><td>10</td><td>6</td><td>14</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>6</sub></td></tr><tr><td>54</td><td>10</td><td>7</td><td>13</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>6</sub></td></tr><tr><td>54</td><td>10</td><td>8</td><td>12</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>6</sub></td></tr><tr><td>54</td><td>10</td><td>9</td><td>11</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>6</sub></td></tr><tr><td>54</td><td>10</td><td>∀k ≥ 10</td><td>10</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>6</sub></td></tr><tr><td>64</td><td>8</td><td>4</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>8</td><td>5</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>8</td><td>6</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>8</td><td>7</td><td>9</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>8</td><td>∀k ≥ 8</td><td>8</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>11</td><td>8</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>8</sub></td></tr><tr><td>64</td><td>11</td><td>9</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>8</sub></td></tr><tr><td>64</td><td>11</td><td>10</td><td>12</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>8</sub></td></tr><tr><td>64</td><td>11</td><td>∀k ≥ 11</td><td>11</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>8</sub></td></tr></tbody></table>
<table><caption>TABLEAU V.1 – Tableau récapitulatif des valeurs des constantes $D(G)$ et $s_{≤k}(G)$</caption><thead><tr><th>|G|</th><th>D(G)</th><th>k</th><th>s<sub>≤k</sub>(G)</th><th>Le groupe</th></tr></thead><tbody><tr><td>64</td><td>9</td><td>4</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>9</td><td>5</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>9</td><td>6</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>9</td><td>7</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>9</td><td>8</td><td>10</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>9</td><td>∀k ≥ 9</td><td>9</td><td>C<sub>2</sub> ⊕ C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>10</td><td>4</td><td>22</td><td>C<sub>4</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>10</td><td>5</td><td>?</td><td>C<sub>4</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>10</td><td>6</td><td>?</td><td>C<sub>4</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>10</td><td>7</td><td>?</td><td>C<sub>4</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>10</td><td>8</td><td>?</td><td>C<sub>4</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>10</td><td>9</td><td>11</td><td>C<sub>4</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>10</td><td>∀k ≥ 10</td><td>10</td><td>C<sub>4</sub> ⊕ C<sub>4</sub> ⊕ C<sub>4</sub></td></tr><tr><td>64</td><td>12</td><td>8</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>8</sub></td></tr><tr><td>64</td><td>12</td><td>9</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>8</sub></td></tr><tr><td>64</td><td>12</td><td>10</td><td>?</td><td>C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>8</sub></td></tr><tr><td>64</td><td>12</td><td>11</td><td>13</td><td>C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>8</sub></td></tr><tr><td>64</td><td>12</td><td>∀k ≥ 12</td><td>12</td><td>C<sub>2</sub> ⊕ C<sub>4</sub> ⊕ C<sub>8</sub></td></tr><tr><td>81</td><td>13</td><td>9</td><td>?</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>9</sub></td></tr><tr><td>81</td><td>13</td><td>10</td><td>?</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>9</sub></td></tr><tr><td>81</td><td>13</td><td>11</td><td>?</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>9</sub></td></tr><tr><td>81</td><td>13</td><td>12</td><td>14</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>9</sub></td></tr><tr><td>81</td><td>13</td><td>∀k ≥ 13</td><td>13</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>9</sub></td></tr><tr><td>108</td><td>16</td><td>12</td><td>?</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>12</sub></td></tr><tr><td>108</td><td>16</td><td>13</td><td>?</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>12</sub></td></tr><tr><td>108</td><td>16</td><td>14</td><td>?</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>12</sub></td></tr><tr><td>108</td><td>16</td><td>15</td><td>17</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>12</sub></td></tr><tr><td>108</td><td>16</td><td>∀k ≥ 16</td><td>16</td><td>C<sub>3</sub> ⊕ C<sub>3</sub> ⊕ C<sub>12</sub></td></tr></tbody></table>
d) Description de l’algorithme

Dans cette sous-section nous décrivons une adaptation de l’algorithme présenté
au chapitre précédent pour calculer ces constantes.

Soit $\ell$ un entier supérieur ou égal à l'exposant du groupe.

Rappelons que nous cherchons à déterminer le plus petit entier $t$ tel que toute séquence de longueur au moins $t$ contienne une sous-séquence de somme nulle et de longueur au plus égale à $\ell$.

Notons que l'entier $\ell$ doit être supérieur ou égal à l'exposant du groupe. Sinon comme nous l'avons vu, la valeur de la constante sera infinie.

En effet, si l'entier $\ell$ est inférieur que l'exposant du groupe, il existera toujours des séquences pour lesquelles la somme n'est pas nulle.

Le principe général de l'algorithme est le suivant :

Soit $E_k(i)$ : L'ensemble des séquences de longueur $k$ et de somme $i$.

Et soit $S(E_k(i))$ l'ensemble des successeurs de l'ensemble $E_k(i)$.

Dans un premier temps, nous considérons l'ensemble des séquences de somme nulle et de longueur au plus $\ell$.

Pour cela, nous suivons les étapes suivantes :

— On commence par l'élément neutre {0} représentant $E_1(0)$, l'ensemble des séquences de longueur 1 et de somme nulle.

— Puis, nous calculons $S(E_1(0))$ les successeurs de 0 avec la méthode décrite dans la section 2-, page 65 et on rajoute $E_2(0)$, l'ensemble des séquences de longueur 2 et de somme nulle. Appelons la réunion d'ensembles $S(E_1(0)) \cup E_2(0)$ l'ensemble $R_2$.

— L'ensemble $R_2$ est alors l'ensemble de toutes les séquences de longueur 2 qui ont une sous-séquence de somme nulle.

— Nous calculons ensuite les successeurs de l'ensemble $R_2$ auquel on ajoute l'ensemble $E_3(0)$, l'ensemble des séquences de longueur 3 et de somme nulle. Appelons la réunion de l'ensemble $S(R_2) \cup E_3(0)$ l'ensemble $R_3$.

— L'ensemble $R_3$ est alors l'ensemble de toutes les séquences qui ont une sous-séquence de longueur au plus 3 et de somme nulle.

— Nous répétons successivement l'opération précédente, jusqu'à ce que nous obtenions $R_\ell$, l'ensemble de toutes les séquences de longueur $\ell$ qui ont une sous-séquence de somme nulle. Notons que forcément ces sous-séquences sont de longueur plus petite ou égale à $\ell$.
Nous calculons, ensuite les successeurs des séquences jusqu'à ce que nous obtenions comme successeurs l'ensemble des toutes les séquences possibles d'une longueur donnée.

Si nous prenons n'importe quelle séquence de cette longueur-là, alors par la relation d'inclusion, cette séquence est forcément le successeur d'une séquence de somme nulle et de longueur au plus égale à $\ell$.

Pour calculer l'ensemble des suites croissantes de longueurs $k$ et de somme $0$, nous avons appliqué une formule de récurrence permettant d'éviter la recherche exhaustive.

Nous décrivons dans la sous-section suivante cette formule et le détail des calculs.

## e) Le calcul des séquences de somme $i$ et de longueur $k$

Nous avons développé un algorithme permettant de calculer pour tout $k \le \ell$ les séquences de somme nulle et de longueur $k$ à chaque étape.

L'idée de cet algorithme est de créer une table qui contient les séquences de somme nulle et de longueur $k$, pour tout $k \le \ell$.

Puis nous appliquons la formule récursive qui dit qu'une séquence de longueur $k+1$ et de somme $i$ s'obtient comme une séquence de longueur $k$ et de somme $u$ dont on lui rajoute le terme $i-u$.

$$E_{k+1}(i) = \cup_{u \in G} E_k(u) \cdot (i-u) \quad (2.1)$$

**Exemple 2.4.** Soit $G = C_3$.

En appliquant la formule de récurrence 2.1, nous obtenons :

$$ 
\begin{aligned}
E_3(0) &= (E_2(0) \cdot 0) \cup (E_2(1) \cdot 2) \cup (E_2(2) \cdot 1) \\
&= [(E_1(0) \cdot 0 \cup E_1(1) \cdot 2 \cup E_1(2) \cdot 1)] \cdot 0 \cup [(E_1(0) \cdot 1 \cup E_1(1) \cdot 0 \cup E_1(2) \cdot 2)] \cdot 2 \\
&\quad \cup [(E_1(0) \cdot 2 \cup E_1(1) \cdot E_1(2) \cdot 0)] \cdot 1
\end{aligned}
$$

Si on veut appliquer la formule de récurrence 2.1, on s'aperçoit qu'on calcule plusieurs fois les mêmes données, ce qui engendre une perte de temps de calcul, dans l'exemple 2.4, les données $E_1(0)$, $E_1(1)$ et $E_1(2)$, se répètent plusieurs fois. Pour éviter de les recalculer, nous mémorisons chacune de ces valeurs déjà calculées.

Ce qui donne l'algorithme 5

Soient $\rho_{i,u,k}$ l'ensemble des numéros de suites croissantes de somme $i-u$ et de longueur $k$ et $\nu_{i,u,k}$ l'ensemble des numéros de suites croissantes de somme $i$
<table><caption>TABLEAU V.2 – Détails des calculs de la formule de récurrence pour le groupe $C_3$</caption><thead><tr><th>i</th><th>u</th><th>k</th><th>E<sub>k</sub>(i-u)</th><th>ρ<sub>i,u,k</sub></th><th>E<sub>k+1</sub>(i)</th><th>ν<sub>i,u,k</sub></th></tr></thead><tbody><tr><td>0</td><td>0</td><td>1</td><td>0</td><td>[0]</td><td>{00}</td><td>[0]</td></tr><tr><td>0</td><td>1</td><td>1</td><td>2</td><td>[2]</td><td>{12}</td><td>[4]</td></tr><tr><td>0</td><td>2</td><td>1</td><td>1</td><td>[1]</td><td>0</td><td>[]</td></tr><tr><td>1</td><td>0</td><td>1</td><td>1</td><td>[1]</td><td>{01}</td><td>[1]</td></tr><tr><td>1</td><td>1</td><td>1</td><td>0</td><td>[0]</td><td>0</td><td>[]</td></tr><tr><td>1</td><td>2</td><td>1</td><td>2</td><td>[2]</td><td>{22}</td><td>[5]</td></tr><tr><td>2</td><td>0</td><td>1</td><td>2</td><td>[2]</td><td>{02}</td><td>[2]</td></tr><tr><td>2</td><td>1</td><td>1</td><td>1</td><td>[1]</td><td>{11}</td><td>[3]</td></tr><tr><td>2</td><td>2</td><td>1</td><td>0</td><td>[0]</td><td>0</td><td>[]</td></tr><tr><td>0</td><td>0</td><td>2</td><td>{00,12}</td><td>[0] &cup; [4]</td><td>{000,012}</td><td>[0] &cup; [4]</td></tr><tr><td>0</td><td>1</td><td>2</td><td>{02,11}</td><td>[2,3]</td><td>{012,111}</td><td>[6]</td></tr><tr><td>0</td><td>2</td><td>2</td><td>{01,22}</td><td>[1] &cup; [5]</td><td>{012,222}</td><td>[9]</td></tr></tbody></table>

et de longueur $k+1$. Notons que l'ensemble $E_{k+1}(i)$ est obtenu en rajoutant à l'ensemble $E_k(i-u)$ le terme $u$.

Le tableau ci-dessous donne le détail du calcul de la formule de récurrence 2.1 appliquée pour le groupe $G = C_3$.

Nous avons observé que l'ensemble translaté $\nu_{i,u,k}$ se calcule à partir de l'ensemble $\rho_{i,u,k}$, ce qui permet d'accélérer les calculs.

En traduisant le numéro de la suite croissante de longueur $k+1$ et de somme $i$ en un bitmap de longueur $n+k$ et de poids $k+1$ et en parcourant le triangle de Pascal modifié comme expliqué dans 1-), page 23, il est clair que ce parcours n'est qu'un décalage du parcours du bitmap de la suite croissante de longueur $k+1$ et de somme $i-u$ comme l'illustre la table V.1, en prenant comme exemple un élément $x=5$ de l'ensemble $\rho_{0,2,2}$ de la dernière linge du tableau V.2

Pour cet exemple : le numéro 5 correspond au bitamp 11001, son bitmap translaté est 11100 qui correspond au numéro $y=9$ qui est un élément de l'ensemble $\nu_{0,2,2}$.

Ces bitmaps sont schématisés dans la table V.1 ci-dessous.
<figure><img src="image_19.png" /><figcaption>FIGURE V.1 – Le décalage du parcours dans le triangle de Pascal modifié</figcaption></figure>

Dans cet exemple, l'élément $y$ est obtenu en rajoutant à l'élément $x$ la quantité suivante :

$$ (a_{2,2} - a_{2,1}) + (a_{3,2} - a_{3,1}) = \binom{2}{2} + \binom{3}{2} $$

De manière générale, cette translation du parcours dans le triangle de Pascal d'un élément $x$ de l'ensemble $\rho_{i,u,k}$ correspond à rajouter à l'élément $x$ une certaine quantité de coefficients binomiaux donnés par la formule suivante :

$$ y = x + \sum_{j=1}^{u} \binom{n+k-j-1}{k} = \sum_{s=k-2}^{k-u-1} \binom{n+s}{k} \quad (2.2) $$

Pour l'exemple 2.4, en utilisant la propriété 2.4, page 22 du triangle de Pascal modifié on a :

$$ (a_{2,2} + a_{3,2}) - (a_{2,1} + a_{3,1}) = (a_{4,3} - a_{2,3}) - (a_{4,2} - a_{2,2}) = \binom{4}{3} - \binom{2}{3} $$

La formule 2.2 peut alors être simplifié par la formule suivante :

$$ \sum_{s=k-2}^{k-u-1} \binom{n+s}{k} = \binom{n+k-1}{k+1} - \binom{n+k-1-u}{k+1} \quad (2.3) $$

f) Pseudo code : le calcul de la constante $s_{\le k}(G)$

Le code source est disponible sur https://github.com/Zerdoum/EGZ-infval/tree/master
**Algorithme 5** Le calcul de la constante $s_{\le k}(G)$

**Entrée**

$n$: l'ordre du groupe $G$

$k$: un entier tel que $k$ est supérieur ou égal à l'exposant du groupe

**Sortie**

$e-1$

**Variables**

$p, q, r, S$: des ensembles

$M, N$: des tableaux

$i, u, v, e$: des entiers

**Initialisation**

$N[0] \leftarrow 0$

1. **procédure**

Calculer $R_ℓ$ :

initialiser le tableau $M$

2. **pour** ($i = 0; i < n; i++$) **faire**

3. $M[u] = u$

initialiser l'ensemble $p$

Au départ $p$ contient les suites croissantes de longueur 1 et de somme $u \in G$ :

4. **pour** ($u = 0; u < n; u++$) **faire**

5. inclure l'élément $i$ dans $p[i]$

6. **pour** ($e = 0; e \le k; e++$) **faire**

7. **pour** ($u = 1; u \le n; u++$) **faire**

8. $N[u] = N[u-1] + \binom{n+k-u-1}{k-1}$

calculer $E_e(u)$ en appliquant la formule de récurrence :

$$E_e(u) = \cup_{u \in G} E_{e-1}(u) + (i-u)$$

l'ensemble $p$ contient $E_{e-1}(u)$ et l'ensemble $q$ contiendra $E_e(u)$

9. **pour** ($i = 0; i < n; i++$) **faire**

10. **pour** ($u = 0; u < n; u++$) **faire**

11. $v = i - u$

12. $r = p[v]$

13. **si** $u > 0$ **alors**

14. Exclure l'intervalle $[0, M[u] - 1]$ de l'ensemble $r$

15. ainsi nous ne prenons en comptes que les nouvelles suites croissantes

16. On translate $r$ par $N[u] - M[u]$ pour obtenir le numéro de la suite de

17. longueur $e$ et de somme $u$

18. Inclure l'ensemble $r$ dans l'ensemble $q[i]$

19. **si** $e = k$ **alors**

20. break

21. inclure dans l'ensemble $q[0]$ l'ensemble $S_1$

22. calculer les successeurs de $S_1$

23. l'ensemble $p$ deviendra l'ensemble $q$

24. l'ensemble $q$ deviendra l'ensemble $p$

25. $N$ deviendra $M$

26. $M$ deviendra $N$

27. **tant que** tant que l'ensemble $S_1$ n'est pas rempli **faire**

28. nous calculons seulement successeurs $S_1$

29. $e \leftarrow e + 1$
g) Résultats et perspectives

Nous avons pu déterminer les valeurs suivantes de la constante $s_{\le k}(G)$ :

$$ \text{— } s_{\le 5}(C_2 \oplus C_2 \oplus C_2 \oplus C_4) = 9. $$

$$ \text{— } s_{\le 5}(C_2 \oplus C_4 \oplus C_4) = 11. $$

$$ \text{— } s_{\le 6}(C_2 \oplus C_4 \oplus C_4) = 10. $$

$$ \text{— } s_{\le 6}(C_2 \oplus C_2 \oplus C_2 \oplus C_6) = 12. $$

$$ \text{— } s_{\le 7}(C_2 \oplus C_2 \oplus C_2 \oplus C_6) = 11. $$

$$ \text{— } s_{\le 6}(C_3 \oplus C_3 \oplus C_6) = 14. $$

$$ \text{— } s_{\le 7}(C_3 \oplus C_3 \oplus C_6) = 13. $$

$$ \text{— } s_{\le 8}(C_3 \oplus C_3 \oplus C_6) = 12. $$

Nous avons vu dans le chapitre précédent qu'à l'étape d'initialisation de la détermination de la constante Erdős-GinzBurg-Ziv, nous parcourons de manière exhaustive, l'ensemble de toutes les suites croissantes de longueur exposant du groupe et nous ne retenons que celles qui ont une somme nulle, c'est-à-dire nous ne retenons que l'ensemble $E_e(0)$.

Nous avons alors essayé d'appliquer la formule de récurrence 2.1 en disant :

$$ E_e(0) = \bigcup_{u \in G} E_{e-1}(u) \cdot (-u) \qquad (2.4) $$

pour tenter de gagner en temps de calcul lors de l'initialisation, or on s'est rendu compte que le temps de calcul était plus long.

En effet, nous avons deux types de complexités, une complexité absolue qui se mesure avec le temps de calcul et dépend de toutes les opérations utilisées, et une complexité relative qui dépend du nombre d'opérations ensemblistes.

La complexité de la méthode de recherche exhaustive est exponentielle, c'est la recherche exhaustive de toutes les suites croissantes de longueur $e$.

Notons que le nombre d'opérations ensembliste est le nombre d'éléments de $G$, car d'après la formule de récurrence 2.4 nous faisons une réunion sur tous les éléments de $G$.

On s'attendait à constater une accélération des calculs en appliquant la formule 2.4 mais ce n'est pas le cas; car la complexité de chaque réunion dépend du nombre d'intervalles, or le nombre d'intervalles croit.

Pour conclure, en pratique la recherche exhaustive est plus rapide que la méthode de la formule de récurrence.
# CHAPITRE VI

## CONCLUSION ET PERSPECTIVES

### Sommaire

<table><tr><td>1</td><td>Le bilan des constantes étudiées</td><td>108</td></tr><tr><td>2</td><td>La représentation informatique des ensembles</td><td>109</td></tr><tr><td>3</td><td>Description de l'application web</td><td>112</td></tr></table>
Les problèmes des suites de somme nulle sur les groupes abéliens fini sont des problèmes de la théorie additive des nombres. Ces problèmes consistent à étudier le nombre minimal d'éléments avec ou sans répétitions d'éléments du groupe qu'il faut considérer pour être certain d'en extraire une suite de somme nulle, potentiellement avec des restrictions sur la longueur de cette suite. Ceci définit des constantes associées à chaque groupe abélien fini.

Dans cette conclusion, nous allons présenter un bilan des constantes étudiées en donnant la liste des nouveaux résultats obtenus. Nous renvoyons aux chapitres précédents pour la définition précise de ces constantes. Nous focalisons ensuite sur la partie algorithmique de notre travail, en particulier, nous présentons les différentes façons de représenter les ensembles dans un programme, notre choix de représentation ainsi que quelques perspectives envisageables. Et enfin, nous décrivons notre application web.

# 1 Le bilan des constantes étudiées

Le tableau suivant donne un récapitulatif des résultats trouvés durant cette thèse.

<table><caption>TABLEAU VI.1 – Nos résultats trouvés</caption><thead><tr><th>La constante</th><th>La valeur trouvé</th></tr></thead><tbody><tr><td>La constante de Harborth</td><td>g(C<sub>3</sub> ⊕ C<sub>3p</sub>) = 3p + 3 où p est un nombre premier différent de 3.<br>g(C<sub>3</sub> ⊕ C<sub>9</sub>) = 13</td></tr><tr><td>La constante Erdős-Ginzburg-Ziv</td><td>s(C<sub>2</sub><sup>3</sup> ⊕ C<sub>4</sub>) = 13<br>s(C<sub>2</sub><sup>3</sup> ⊕ C<sub>6</sub>) = 17</td></tr><tr><td>La constante s<sub>≤k</sub>(G)</td><td>s<sub>≤5</sub>(C<sub>2</sub><sup>3</sup> ⊕ C<sub>4</sub>) = 9<br>s<sub>≤5</sub>(C<sub>2</sub> ⊕ C<sub>4</sub><sup>2</sup>) = 11<br>s<sub>≤6</sub>(C<sub>2</sub> ⊕ C<sub>4</sub><sup>2</sup>) = 10<br>s<sub>≤6</sub>(C<sub>2</sub><sup>3</sup> ⊕ C<sub>6</sub>) = 12<br>s<sub>≤7</sub>(C<sub>2</sub><sup>3</sup> ⊕ C<sub>6</sub>) = 11<br>s<sub>≤6</sub>(C<sub>2</sub><sup>3</sup> ⊕ C<sub>6</sub>) = 14<br>s<sub>≤7</sub>(C<sub>2</sub><sup>3</sup> ⊕ C<sub>6</sub>) = 13<br>s<sub>≤8</sub>(C<sub>2</sub><sup>3</sup> ⊕ C<sub>6</sub>) = 12</td></tr></tbody></table>

Deux approches ont étés menées au cours de cette étude. Une approche calculatoire et une approche théorique.

L'approche calculatoire consiste à développer des algorithmes pour trouver les constantes. Ils ont permis d'en trouver les valeurs pour certains groupes pour lesquels elles n'étaient pas connues. Et d'autre part, ils nous ont donné des idées pour
déterminer certaines bornes inférieures de constantes étudiées. En effet, examiner les sous-ensembles les plus grands qui n'ont pas de somme nulle, nous a conduits à des idées sur un minorant. C'est ce qui a été fait au troisième chapitre pour la constante de Harborth.

Dans le paragraphe qui suit nous présentons certains détails de notre travail pour la partie algorithmique ainsi que des problèmes d'implémentation informatique.

Un des problèmes à résoudre est la représentation des ensembles. Nous avons considéré plusieurs types de représentations. Les ensembles interviennent à plusieurs niveaux dans notre travail. Pour le premier niveau, nous avons l'ensemble sous-jacent des groupes dont les éléments sont numérotés arbitrairement.

Par exemple $C_2 \oplus C_2 = \{e_0, e_1, e_2, e_3\}$.

Pour le deuxième niveau, nous devons aussi considérer des suites d'éléments de ces groupes avec ou sans répétition. Une suite sans répétition d'éléments n'est rien d'autre qu'un sous-ensemble du groupe. Lorsque les répétitions sont admises, on se ramène comme décrit à la section 2, page 19 à un sous-ensemble d'un ensemble plus grand.

Notons que dans les deux cas, on se ramène toujours à des sous-ensembles.

Pour le deuxième niveau, il nous a fallu travailler avec une numérotation des séquences compatible avec la taille de la séquence. Plus précisément, le numéro d'une séquence de $k$ termes sera toujours inférieur à celui d'une séquence de $k + 1$ termes. Voir la section 2, page 19.

Examinons maintenant les façons de représenter un ensemble de numéros de séquence dans un programme.

## 2 La représentation informatique des ensembles

Dans le paragraphe suivant, nous présentons quelques façons classiques de représenter un ensemble dans un programme avec ses avantages et ses inconvénients. Nous justifierons le choix de la représentation que nous avons adoptée.

1. **Le bitmap** : un sous-ensemble $F$ d'un ensemble $E$ de $n$ éléments est représenté par un mot binaire de $n$ termes. Chaque position désigne un élément de $E$. La valeur 1 signifie que cet élément appartient à $F$ et la valeur 0 signifie que qu'il n'y appartient pas. L'avantage de cette représentation est la simplicité. En contrepartie, la complexité des opérations est constante et nécessite de parcourir tout le bitmap, ce qui peut s'avérer très complexe. En effet, explorer les suites croissantes de $k$ termes d'un ensemble de $n$ éléments, nécessite des bitmaps de taille $(n+k-1)$. Il n'est pas raisonnable
d'utiliser cette représentation quand cette taille dépasse, par exemple $2^{40}$. Notons que $2^{40}$ est égale à mille milliards, avec un milliards d'opération par seconde, le temps est milles secondes soit environs vingt minutes.

2. **La liste des éléments** : Un sous-ensemble est représenté par la liste chainée de ses éléments. Cette représentation peut être avantageuse lorsque les sous-ensembles contiennent peu d'éléments, mais ne l'est absolument pas pour les sous-ensembles de taille importante. Il faut en effet, ajouter les données nécessaires à la gestion des listes. Par exemple, sur l'hypothèse d'un entier codé sur 64 chiffres binaires et des pointeurs de la même taille, la taille peut aller jusqu'à 128 fois celle du bitmap. La complexité des opérations n'est pas constante mais proportionnelle au nombre d'éléments des sous-ensembles. Comme nous ne disposons d'aucune information sur la taille à priori des sous-ensembles, cette représentation n'a pas été retenue.

3. **La réunion en intervalles disjoints** : Cette représentation a été retenue car nous avons réussi à concilier d'une part, la compacité de la représentation et d'autres part, l'efficacité. Nous avons trouvé une manière efficace de calculer les successeurs d'un intervalle de séquences en n'explorant que les bornes des intervalles. La complexité des opérations s'en trouve proportionnelle au nombre d'intervalles et non pas au nombre d'éléments.

**Exemple 2.1.** Considérons l'ensemble $E = \{1, \dots, 29\}$ de sous-ensemble $F = \{1, 2, 3, 4, 5, 6, 7, 8, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29\}$

$F$ est la liste des éléments représentée par le bitmap :

$$F = 1111111000000011111111111111$$

Cette représentation correspond à la réunion d'intervalle suivante :

$$F = [1, 8] \cup [16, 29].$$

Pour manipuler ces réunions d'intervalles, la structure qui s'impose est celle d'arbre de recherche équilibré. Elle permet de :

- tester simplement l'appartenance d'un élément à un sous-ensemble en temps logarithmique.

- d'insérer et d'ôter des éléments ou des intervalles également en temps logarithmique.

Pour rester efficace, l'arbre doit demeurer équilibré.

Il existe plusieurs façon d'équilibrer les arbres. Nous avons tout d'abord testé une structure appelée B-tree. Les œufs parents peuvent posséder plus de deux nœuds enfants. Cette structure s'est avérée moins efficace pour notre besoin car dans la majorité des cas, deux nœuds ne comportaient que deux
successeurs. En conséquence, la mémoire n'était pas utilisée d'une manière optimale.

Nous nous sommes repliés sur la structure d'arbre AVL. [AVL62] qui forme une famille particulière des arbres binaires de recherche équilibrés. La dénomination « arbre AVL » provient des noms respectifs de ses deux inventeurs, respectivement Georgii Adelson-Velsky et Evguenii Landis.

La recherche, l'insertion et la suppression sont toujours logarithmique en le nombre d'éléments $O(\log_2(N))$ où N désigne le nombre de nœuds de l'arbre, c'est-à-dire ici le nombre d'intervalles du sous-ensemble.

Notons qu'il aurait été possible d'envisager d'utiliser d'autres structures de données pour représenter les réunions d'intervalles, comme par exemple les tables de hachage.

La représentation des ensembles comme une réunion d'intervalles consécutifs, peut s'interpréter comme une compression des données binaires avec l'algorithme RLE (Run-Lenght-Encoding) [RC67].

Le principe du codage RLE est d'indiquer le nombre de répétions d'un élément puis le compléter par l'élément à répéter. Sur l'exemple ci-dessus, l'ensemble F est représenté par l'unique intervalle $[min, max]$, ce codage est donc très efficace lorsqu'il existe plusieurs symboles consécutifs dans un ensemble. Mais il est inefficace lorsqu'il ya beaucoup de variation. Le pire des cas est celui de la réunion de singleton non consécutive comme par exemple l'ensemble des nombres pairs :

**Exemple 2.2.** Soit F le bitmap donné par :

$$F = 1010101010101010$$

F se décrit par la réunion d'intervalle suivante :

$$F = [0] \cup [2] \cup [4] \cup [6] \cup [8] \cup [10] \cup [12] \cup [14], \text{ ce qui est très inefficace.}$$

À titre de perspectives, il est possible d'explorer d'autres types d'algorithmes de compression des données binaires pour avoir une représentation compacte et efficace des ensembles.

Une perspective envisageable serait de développer ce type de représentation pour dépasser les limites en complexité et en mémoire de la présente représentation.

Citons par exemple :

— l'algorithme de Ziv-Lempel [Wel84].

Cet algorithme est plus efficace en terme de compacité car on arrive à réduire d'avantage la taille par rapport à l'algorithme RLE. En revanche, il reste moins efficace lors de la compression car il faut un dictionnaire. De
plus, l'effectivité n'est pas résolue car il reste à implémenter les opérations ensemblistes sur ce type de modèle.

Rappelons que les opérations ensemblistes sont :

- test d'appartenance d'un élément à un sous-ensemble.

- réunion, comme ajouter un élément à un sous-ensemble.

- intersection, comme retirer un élément d'un sous-ensemble.

- complémentaire.

- le codage de Huffman [Huf52].

Le principe de ce codage est de coder avec des séquences binaires très courtes les mots les plus fréquents et avec des séquences binaires plus longues les mots les moins fréquents.

- le codage arithmétique [MMK03].

Ce codage représente une autre façon de coder les mots les plus fréquents avec des séquences binaires très courtes, et les mots les moins fréquents avec des séquences binaires plus longues.

Mais le problème à résoudre pour chacun de ces codages est de pouvoir répondre à ces questions :

- Est-ce que cela permet de réaliser efficacement les opérations ensemblistes ?

- Est ce que cela permet de réaliser le calculs des successeurs, de façon que la complexité dépende uniquement de la taille des données sans avoir à explorer exhaustivement tout le sous-ensemble ?

## 3 Description de l'application web

Comme nous l'avons vu, il existe de nombreux résultats pour les différentes constantes étudiées. Afin de faciliter la recherche pour la communauté scientifique, nous avons développé une application web. Concrètement, notre site web permet de récupérer des valeurs connues pour les constantes suivantes :

- La constante de Harborth

- La constante de Davenport

- La constante d'Erdős-Ginzburg-Ziv

- La constante $s_{\le k}(G)$

L'utilisateur demande la valeur de la constante pour un groupe abélien fini donné.

L'application vérifie si la constante de ce groupe est connue d'après les résultats
existant dans la littérature ou bien selon nos nouveaux résultats trouvés dans le cadre de cette thèse. Si c'est le cas, elle retourne le résultat de cette constante sinon elle envoie un message nous informant que la constante pour ce groupe n'est pas encore connue ou implémentée.

Notons qu'il est tout à fait envisageable d'enrichir cette application pour l'étude d'autres constantes. Nous prévoyons aussi de la mettre à jour lorsque de nouveaux résultats seront obtenus.

Cette application implémente plusieurs pages web :

— La page d'accueil présente des liens vers les descriptions de chaque constante.

<figure><img src="image_20.png" /><figcaption>FIGURE VI.1 – Capture d'écran de la page d'accueil</figcaption></figure>

— Les pages de description définit chaque constante et présente les valeurs connues.

— Une page de recherche contient un formulaire pour calculer une constante spécifique en introduisant le groupe souhaité.
<figure><img src="image_21.png" /><figcaption>FIGURE VI.2 – Capture d'écran de la page de description de la constante de Davenport</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>FIGURE VI.3 – Capture d'écran de la page du calcul</figcaption></figure>

— Une fois la recherche lancée, une page affiche le résultat demandé.

L'application est implémentée en utilisant le framework flask. Flask est un framework python qui permet de développer des applications web. Il se base sur le modèle d'implémentation RESTfull. Le framework offre un ensemble de packages qui implémentent les fonctionnalités de base pour faire fonctionner l'application.

Les packages python utilisés sont :

— Flask, render_template, url_for, flash, redirect, request

— forms, RegistrationForm, LoginForm, SearchForm, SearchOneForm

— wtforms validators, DataRequired, Length, Email, EqualTo

Pour plus de détails de ce framework (voir [Fla]).
<figure><img src="image_23.png" /><figcaption>FIGURE VI.4 – Capture d'écran des cases de recherche remplies</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>FIGURE VI.5 – Capture d'écran du résultat final</figcaption></figure>

L'application est en cours de développement et n'est pas encore accessible au public. Cependant, il est possible de la lancer depuis son poste local (de préférence depuis MacOS ou Linux) en téléchargeant le code source disponible sur https://github.com/Zerdoum/sommeNulle et en suivant les étapes d'installation comme décrit dans le fichier README, voir https://github.com/Zerdoum/sommeNulle/blob/master/README.md

Le dossier racine contient les fichiers python suivants :

- main.py : c'est le premier fichier qui sera appelé par l'application. Il crée une instance d'application et définit toutes les routes (les URL) qui appellent les différentes fonctions et pages de l'application.

- core.py : est appelé par le fichier main.py. Ce fichier vérifie quelle constante
est appelée par le formulaire de recherche. Il fait appel aux différents fichiers
python qui implémentent le calcul des constantes. : davenPort.py, egz.py,
harborth.py, others.py.

- forms.py : définit la structure des classes d'objets utilisés pour l'affichage des différentes pages, comme : forme texte, liste, buttons de validations etc.

- davenPort.py, egz.py, harborth.py, others.py : ces fichiers implémentent les différentes fonctions qui font le calcul des constantes selon un paramétrage saisi par l'utilisateur. Ces paramètres sont : le nom de la constante et le groupe abélien fini. Ce dernier doit être saisi sous forme d'une liste numérique séparée par des virgules. De plus, on impose la contrainte qu'un nombre doit être divisible par le suivant. Prenant l'exemple de la liste numérique, 2, 2, 4, cette liste représente le groupe $G = C_2 \oplus C_2 \oplus C_4$. Il serait sans doute aisé de compléter ce travail par une saisie moins contraignante.

- Les dossiers /static, /templates contiennent les différents fichiers .html, .css etc, qui implémentent la partie visuelle de l'application web, c'est-à-dire, les pages web, les formulaires dont celui de la recherche, les boutons, les couleurs, etc.

- run.sh est le fichier à lancer pour démarrer l'application. Il définit quelques paramètres qui permettent le lancement de l'application.

Le dessin suivant visualise le plan du site.
<figure><img src="image_25.png" /><figcaption>FIGURE VI.6 – Le plan du site</figcaption></figure>
<figure><img src="image_26.png" /></figure>
LISTE DES FIGURES

<table><tbody><tr><td>II.1</td><td>Le triangle de Pascal modifié</td><td>22</td></tr><tr><td>II.2</td><td>Exemple de la propriété 2.3 page 22</td><td>22</td></tr><tr><td>II.3</td><td>Exemple de la propriété 2.4 page 22</td><td>23</td></tr><tr><td>II.4</td><td>Transformer le bitmap 10110 en numéro</td><td>24</td></tr><tr><td>IV.1</td><td>Les différentes bifurcations pour le calcul des successeurs d'un numéro</td><td>64</td></tr><tr><td>IV.2</td><td>Exemple d'arborescence sur un niveau</td><td>66</td></tr><tr><td>IV.3</td><td>Exemple d'arborescence entière</td><td>67</td></tr><tr><td>IV.4</td><td>Rangement des noeuds dans une table</td><td>67</td></tr><tr><td>IV.5</td><td>Exemple de recherche dans l'arborescence</td><td>71</td></tr><tr><td>IV.6</td><td>Exemple du parcours pour déterminer les successeurs d'un entier a</td><td>84</td></tr><tr><td>IV.7</td><td>Exemple du parcours pour déterminer les successeur d'un entier b</td><td>85</td></tr><tr><td>V.1</td><td>Le décalage du parcours dans le triangle de Pascal modifié</td><td>104</td></tr><tr><td>VI.1</td><td>Capture d'écran de la page d'accueil</td><td>113</td></tr><tr><td>VI.2</td><td>Capture d'écran de la page de description de la constante de Da-venport</td><td>114</td></tr><tr><td>VI.3</td><td>Capture d'écran de la page du calcul</td><td>114</td></tr><tr><td>VI.4</td><td>Capture d'écran des cases de recherche remplies</td><td>115</td></tr><tr><td>VI.5</td><td>Capture d'écran du résultat final</td><td>115</td></tr><tr><td>VI.6</td><td>Le plan du site</td><td>117</td></tr></tbody></table>
<figure><img src="image_27.png" /></figure>
LISTE DES TABLEAUX

<table><tbody><tr><td>IV.1</td><td>Les suites croissantes d'entiers de deux termes choisis parmi {0, 1, 2, 3}</td><td>59</td></tr><tr><td>IV.2</td><td>La liste complète des séquences de longueur 3 sur un groupe d'ordre 4</td><td>61</td></tr><tr><td>IV.3</td><td>Numéros des séquences de paramètre n = 3 et k = 3</td><td>83</td></tr><tr><td>IV.4</td><td>L'évolution du nombre d'intervalle lorsque k varie</td><td>89</td></tr><tr><td>V.1</td><td>Tableau récapitulatif des valeurs des constantes D(G) et s<sub>≤k</sub>(G)</td><td>100</td></tr><tr><td>V.2</td><td>Détails des calculs de la formule de récurrence pour le groupe C<sub>3</sub></td><td>103</td></tr><tr><td>VI.1</td><td>Nos résultats trouvés</td><td>108</td></tr></tbody></table>
<figure><img src="image_28.png" /></figure>
TOUTE LA BIBLIOGRAPHIE

[AVL62] George M ADEL'SON-VEL'SKII et Evgenii Mikhailovich LANDIS. « An algorithm for organization of information ». In : Doklady Akademii Nauk. T. 146. 2. Russian Academy of Sciences. 1962, p. 263-266.

[AD93] Noga ALON et Moshe DUBINER. « Zero-sum sets of prescribed size ». In : Combinatorics, Paul Erdos is Eighty 1 (1993), p. 33-50.

[Baa69] P.C. BAAYEN. « ($C_2 \oplus C_2 \oplus C_2 \oplus C_{2n}$)! » In : ZW 6/69 (1969).

[Baj18] Bela BAJNOK. Additive Combinatorics : A Menu of Research Problems. Chapman et Hall/CRC, 2018.

[BHSP09] Gautami BHOWMIK, Immanuel HALUPCZOK et Jan-Christoph SCHLAGE-PUCHTA. « Inductive methods and zero-sum free sequences ». In : Integers 9.5 (2009), p. 515-536.

[BSP07] Gautami BHOWMIK et Jan-Christoph SCHLAGE-PUCHTA. « Davenport's constant for groups of the form $Z_3 \oplus Z_3 \oplus Z_{3d}$ ». In : Additive combinatorics 43 (2007), p. 307-326.

[Boa69] Peter vanEmde BOAS. « A combinatorial problem on finite abelian groups, 2 ». In : Stichting Mathematisch Centrum. Zuivere Wiskunde ZW 7/69 (1969).

[Cha+02] ST CHAPMAN et al. « On Davenport's constant of finite abelian groups ». In : FAR EAST JOURNAL OF MATHEMATICAL SCIENCES 5.1 (2002), p. 47-54.

[CS14] Fang CHEN et Svetoslav SAVCHEV. « Long minimal zero-sum sequences in the groups $C_{r-1}^2 \oplus C_{2k}$ ». In : Integers 14 (2014), A23.

[CLP17] Ernie CROOT, Vsevolod F LEV et Péter Pál PACH. « Progression-free sets in are exponentially small ». In : Annals of Mathematics (2017), p. 331-337.

[DOQ01] Charles DELORME, Oscar ORDAZ et Domingo QUIROZ. « Some remarks on Davenport constant ». In : Discrete Mathematics 237.1-3 (2001), p. 119-128.

[Ede+02] Yves EDEL et al. « The classification of the largest caps in AG (5, 3) ». In : Journal of Combinatorial Theory, Series A 99.1 (2002), p. 95-110.
[Ede+07] Yves EDEL et al. « Zero-sum problems in finite abelian groups and af-fine caps ». In : *Quarterly journal of mathematics* 58.2 (2007), p. 159-186.

[EG17] Jordan S ELLENBERG et Dion GIJSWIJT. « On large subsets of with no three-term arithmetic progression ». In : *Annals of Mathematics* (2017), p. 339-343.

[EGZ61] Paul ERDOS, Abraham GINZBURG et Abraham ZIV. « Theorem in the additive number theory ». In : *Bull. Res. Council Israel F* 10 (1961), p. 41-43.

[FGZ11] Yushuang FAN, Weidong GAO et Qinghai ZHONG. « On the Erdős–Ginzburg–Ziv constant of finite abelian groups of high rank ». In : *Journal of Number Theory* 131.10 (2011), p. 1864-1874.

[FZ16] Yushuang FAN et Qinghai ZHONG. « On the Erdős–Ginzburg–Ziv constant of groups of the form $C_2^r \oplus C_n$ ». In : *International Journal of Number Theory* 12.04 (2016), p. 913-943.

[FLP14] Robert FAURE, Bernard LEMAIRE et Christophe PICOULEAU. *Précis de recherche opérationnelle-7e éd. : Méthodes et exercices d'application*. Dunod, 2014.

[Fla] FLASK. https://flask.palletsprojects.com/en/1.1.x/.

[GGS07] WD GAO, Alfred GEROLDINGER et Wolfgang A SCHMID. « Inverse zero-sum problems ». In : *ACTA ARITHMETICA-WARSZAWA* 128.3 (2007), p. 245.

[GT04] WD GAO et R THANGADURAI. « A variant of Kemnitz conjecture ». In : *Journal of Combinatorial Theory, Series A* 107.1 (2004), p. 69-86.

[Gao+07] WD GAO et al. « On short zero-sum subsequences II ». In : *Integers* 7.1 (2007), Paper-A21.

[GG06] Weidong GAO et Alfred GEROLDINGER. « Zero-sum problems in finite abelian groups : a survey ». In : *Expositiones Mathematicae* 24.4 (2006), p. 337-369.

[GHK06] Alfred GEROLDINGER et Franz HALTER-KOCH. *Non-unique factorizations : Algebraic, combinatorial and analytic theory*. Chapman et Hall/CRC, 2006.

[GS19] Benjamin GIRARD et Wolfgang A SCHMID. « Direct zero-sum problems for certain groups of rank three ». In : *Journal of Number Theory* 197 (2019), p. 297-316.

[Gry13] David J GRYNKIEWICZ. *Structural additive theory*. T. 30. Springer Science & Business Media, 2013.

[Gui] Philippe GUILLOT. « Communication privée ». In : ( ).

[Gui+19] Philippe GUILLOT et al. « On the Harborth constant of $C_3 \oplus C_{3p}$ ». In : *Journal de Théorie des Nombres de Bordeaux* 31.3 (2019), p. 613-633.

[Har73] Heiko HARBORTH. « Ein Extremalproblem für Gitterpunkte. » In : *Journal für die reine und angewandte Mathematik* 262 (1973), p. 356-360.

[Huf52] David A HUFFMAN. « A method for the construction of minimum-redundancy codes ». In : *Proceedings of the IRE* 40.9 (1952), p. 1098-1101.
[Kem83] Arnfried KEMNITZ. « On a lattice point problem ». In : *Ars Combin* 16 (1983), p. 151-160.

[Kie16] C KIEFER. « Examining the maximum size of zero-h-sum-free subsets ». In : *Research Papers in Mathematics (B. Bajnok, ed.), Gettysburg College* 19 (2016).

[Luo17] Sammy LUO. « Short zero-sum sequences over abelian p-groups of large exponent ». In : *Journal of Number Theory* 177 (2017), p. 28-36.

[MMK03] David JC MACKAY et David JC MAC KAY. *Information theory, inference and learning algorithms*. Cambridge university press, 2003.

[Mar+13] Luz E MARCHAN et al. « Some exact values of the Harborth constant and its plus-minus weighted analogue ». In : *Archiv der Mathematik* 101.6 (2013), p. 501-512.

[Mor17] Joy MORRIS. *Combinatorics : An Upper-level Introductory Course in Enumeration, Graph Theory, and Design Theory*. Joy Morris, 2017.

[Nar13] Wladyslaw NARKIEWICZ. *Elementary and analytic theory of algebraic numbers*. Springer Science & Business Media, 2013.

[Ols69a] John E OLSON. « A combinatorial problem on finite abelian groups, I ». In : *Journal of number theory* 1.1 (1969), p. 8-10.

[Ols69b] John E OLSON. « A combinatorial problem on finite abelian groups, II ». In : *Journal of Number Theory* 1.2 (1969), p. 195-199.

[PVEB69] D. KRUYSWIJK P. VAN EMDE BOAS. « A combinatorial problem on finite abelian groups, 3 ». In : *Stichting Mathematisch Centrum. Zuivere Wiskunde* (1969).

[Pot08] Aaron POTECHIN. « Maximal caps in AG (6, 3) ». In : *Designs, Codes and Cryptography* 46.3 (2008), p. 243-259.

[RST08] P RATH, K SRILAKSHMI et R THANGADURAI. « On Davenport's constant ». In : *International Journal of Number Theory* 4.01 (2008), p. 107-115.

[Rei07] Christian REIHER. « On Kemnitz' conjecture concerning lattice-points in the plane ». In : *The Ramanujan Journal* 13.1-3 (2007), p. 333-337.

[RC67] AH ROBINSON et Colin CHERRY. « Results of a prototype television bandwidth compression scheme ». In : *Proceedings of the IEEE* 55.3 (1967), p. 356-364.

[Rog63] Kenneth ROGERS. « A combinatorial problem in Abelian groups ». In : *Mathematical Proceedings of the Cambridge Philosophical Society*. T. 59. 3. Cambridge University Press. 1963, p. 559-562.

[Rón00] Lajos RÓNYAI. « On a conjecture of Kemnitz ». In : *Combinatorica* 20.4 (2000), p. 569-573.

[SC05] Svetoslav SAVCHEV et Fang CHEN. « Kemnitz' conjecture revisited ». In : *Discrete mathematics* 297.1-3 (2005), p. 196-201.

[Sch11] Wolfgang A. SCHMID. « The inverse problem associated to the Davenport constant for $C_2 \oplus C_2 \oplus C_{2n}$, and applications to the arithmetic characterization of class groups ». In : *Electron. J. Combin.* 18.1 (2011), Paper 33, 42.

[SZ10] Wolfgang A SCHMID et JJ ZHUANG. « On short zero-sum subsequences over p-groups ». In : *Ars Combin.*, to appear (2010).
[WZ17] Chunlin WANG et Kevin ZHAO. « On zero-sum subsequences of length not exceeding a given number ». In : *Journal of Number Theory* 176 (2017), p. 365-374.

[Wel84] Terry A. WELCH. « A technique for high-performance data compression ». In : *Computer* 6 (1984), p. 8-19.