Le théorème de périodicité de de Bruijn

Théorème 3 (de Bruijn, Hajòs, vers 1950)
Si A,B sont deux parties de Z telles que A est fini et A⊕B=Z alors il existe un entier n et une partie finie tels que A⊕⊕n Z = Z.
Cela revient à dire que A⊕ modulo n recouvre exactement Z/n Z, ou encore que A⊕ constitue un canon rythmique de période n.

Ça se démontre par récurrence et le principe des tiroirs. J'aime à voir ce résultat comme le théorème du chef d'orchestre: quand le chef a fait rentrer plusieurs fois la même voix à des instruments différents, il est bien obligé à partir d'un moment de répéter la séquence !

Ceci dit, on ignore encore quelle est la taille de n relativement au cardinal de A, ce qui est frustrant (on a une majoration en n≤ ce qui paraît énorme par rapport aux exemples connus, où n est linéaire en #A).

Created by Mathematica  (February 6, 2006)