Suite de van der Corput

Illustration du remplissage de l'intervalle unité (axe horizontal) par les n premiers termes de la suite de Van der Corput décimale, pour n de 0 à 999 (axe vertical)

Une suite de van der Corput est un des exemples les plus simples de suite à discrépance faible en dimension 1, sur l'intervalle unité. Ces suites ont été décrites pour la première fois en 1935 par le mathématicien néerlandais Johannes van der Corput. Elles sont construites en inversant la représentation en base n de la suite des nombres naturels (1, 2, 3,…).

On se donne un entier $b\ge 2$. Pour tout entier positif $n\ge 1$, on considère son écriture en base $b$ :$$n=\sum _{k=0}^{L-1}{d}_k(n)b^k=d_0(n)b^0+\cdots +d_{L-1}(n)b^{L-1},$$où $0\le d_k(n)<b$ est le $k$-ième chiffre de $n$ en base $b$. Le $n$-ième nombre de la suite de van der Corput associée à $b$ est$$g_b(n)=\sum _{k=0}^{L-1}{d}_k(n)b^{-k-1}=d_0(n)b^{-1}+\cdots +d_{L-1}(n)b^{-L}.$$

Exemples

Par exemple, pour obtenir la suite de van der Corput décimale, on commence par diviser les nombres 1 à 9 par dix ($x/10$). Pour un nombre à deux chiffres, on inverse l'ordre des chiffres et on divise par cent. On obtient ainsi les numérateurs, regroupés par leur dernier chiffre : d'abord, tous les numérateurs à deux chiffres qui se terminent par 1, c'est-à-dire 01, 11, 21, 31, 41, 51, 61, 71, 81, 91, puis les numérateurs se terminent par 2, à savoir 02, 12, 22, 32, 42, 52, 62, 72, 82, 92, et ainsi de suite...

La suite commence donc de la façon suivante :

$\frac{1}{10},\frac{2}{10},\frac{3}{10},\frac{4}{10},\frac{5}{10},\frac{6}{10},\frac{7}{10},\frac{8}{10},\frac{9}{10},\frac{1}{100},\frac{11}{100},\frac{21}{100},\frac{31}{100},\frac{41}{100},\frac{51}{100},\frac{61}{100},\frac{71}{100},\frac{81}{100},\frac{91}{100},\frac{2}{100},\frac{12}{100},\frac{22}{100},\frac{32}{100}\dots$

ou, en écriture décimale :

0,1 ; 0,2 ; 0,3 ; 0,4 ; 0,5 ; 0,6 ; 0,7 ; 0,8 ; 0,9 ; 0,01 ; 0,11 ; 0,21 ; 0,31 ; 0,41 ; 0,51 ; 0,61 ; 0,71 ; 0,81 ; 0,91 ; 0,02 ; 0,12 ; 0,22 ; 0,32…

On peut faire de même en base deux, ce qui donne la suite de van der Corput binaire :

0,1₂ ; 0,01₂ ; 0,11₂ ; 0,001₂ ; 0,101₂ ; 0,011₂ ; 0,111₂ ; 0,0001₂ ; 0,1001₂ ; 0,0101₂ ; 0,1101₂ ; 0,0011₂ ; 0,1011₂ ; 0,0111₂ ; 0,1111₂...

ou, de façon équivalente,$$\frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{5}{8},\frac{3}{8},\frac{7}{8},\frac{1}{16},\frac{9}{16},\frac{5}{16},\frac{13}{16},\frac{3}{16},\frac{11}{16},\frac{7}{16},\frac{15}{16}\dots$$

Propriétés : densité, équirépartition, discrépance étoile faible

Les termes d'une suite de van der Corput $(g_b(n){)}_{n\ge 1}$ (dans n'importe quelle base $b$) forment une partie dense de l'intervalle unité. Cela signifie que pour tout nombre réel dans $[0,1]$, il existe une sous-suite de la suite de van der Corput qui converge vers ce nombre.

Plus précisément, ils sont équirépartis sur l’intervalle unité : étant donné un sous-intervalle $J$ de $[0,1]$, la proportion d'entiers $k\le n$ tels que $g_b(k)\in J$ tend vers la longueur de $J$ lorsque $n$ tend vers l'infini.

Cette propriété étant acquise, on peut raffiner la répartition des termes à l'aide de la notion de discrépance. On peut démontrer qu'il existe une constante C dépendant uniquement de b telle que (g_b(n))_{n ≥ 1} vérifie

$D_N^{*}(g_b(1),\dots ,g_b(N))\le C\frac{\log N}{N}.$

Implémentation en C

double corput(int n, int base){
  double q=0, bk=(double)1/base;

  while (n > 0) {
   q += (n % base)*bk;
   n /= base;
   bk /= base;
  }

  return q;
}

Articles connexes

• Suites à discrépance faible
• Modèle:Lien
• Modèle:Lien : type de suite numérique utilisée en statistique qui généralise les suites de van der Corput en dimension supérieure.

Notes et références

• Modèle:Article
• Modèle:Ouvrage

Liens externes

• Suite de Van der Corput sur MathWorld
• Modèle:MathWorld