Borne de Gilbert–Varshamov

Une borne inférieure existentielle sur la taille maximale M d'un code en blocs q-aire de longueur n et distance minimale d : il existe un code d'au moins M ≥ q^n / V_q(n,d-1) mots, où V_q(n,d-1)=∑_{i=0}^{d-1} binom(n,i)(q-1)^i (dérivable également par une construction gloutonne). La borne garantit l'existence sans assurer la constructibilité efficace.