Soit X un ensemble fini. Une application booléenne sur X est une application de X dans F₂ = {0,1} , le corps à deux éléments. L'ensemble des antécédents de 1 par l'application booléenne f s'appelle le support de f. L'ensemble des applications booléennes est muni d'une métrique : la distance de Hamming. La distance entre f et g est égale au cardinal du support de f + g.

Lorsque X est un F₂ espace vectoriel, disons de dimension m, l'ensemble des applications booléennes s'identifie à l'algèbre des polynômes de m variables F₂[x,y, ...], réduite modulo x²-x, y²-y, ... On peut parler du degré d'une application et, en particulier, les fonctions affines forment un espace de dimension m + 1; C'est le code de Reed-Muller du premier ordre dont on connaît les paramètres classiques : poids minimum, distribution de poids, groupe d'automorphismes. Si m est pair le rayon de recouvrement est parfaitement déterminé et curieusement, lorsque m est impair, on sait peu de choses !

Le degré de non-linéarite d'une application f, noté d( f ) , est égal à la distance de f au code de Reed-Muller du premier ordre. La valeur maximale du degré de non-linéarité est égale au rayon de recouvrement du code de Reed-Muller du premier ordre. Les applications de degré de non-linearité maximale sont dites courbes; Elles sont recherchées pour des applications cryptographiques. Combien y-a-t-il de fonctions courbes ? Quelle est la non-linéarité d'une fonction courbe ? La théorie des codes ne donne pas encore de réponse à ces questions. Le but de mon exposé est de présenter trois nouvelles pistes dans le langage des fonctions booléennes, des graphes et des mots infinis.