Suite de van der Corput

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\geq 2$ . Pour tout entier positif $n\geq 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\leq 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 :

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

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, ${\tfrac {1}{2}},{\tfrac {1}{4}},{\tfrac {3}{4}},{\tfrac {1}{8}},{\tfrac {5}{8}},{\tfrac {3}{8}},{\tfrac {7}{8}},{\tfrac {1}{16}},{\tfrac {9}{16}},{\tfrac {5}{16}},{\tfrac {13}{16}},{\tfrac {3}{16}},{\tfrac {11}{16}},{\tfrac {7}{16}},{\tfrac {15}{16}}\ldots$

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

Les termes d'une suite de van der Corput $(g_{b}(n))_{n\geq 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\leq 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))\leq 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
Permutation d'inversion des chiffres binaires (en)
Suite de Halton (en) : 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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Van der Corput sequence » (voir la liste des auteurs).

(de) J. G. van der Corput, « Verteilungsfunktionen (Erste Mitteilung) », Proceedings of the Koninklijke Akademie van Wetenschappen te Amsterdam, vol. 38,‎ 1935, p. 813-821 (zbMATH 0012.34705, lire en ligne)
L. Kuipers et H. Niederreiter, Uniform distribution of sequences, Dover Publications, 2005 (1^re éd. 1974), xiv+390 p. (ISBN 0-486-45019-8, zbMATH 0281.10001), p. 129, 158

Liens externes

Suite de Van der Corput sur MathWorld
(en) Eric W. Weisstein, « Van der Corput sequence », sur MathWorld

Portail des mathématiques