Soient p un nombre premier, S un sous-ensemble de
Fp de cardinal inférieur à p/2
et E(d) un ensemble de polynômes de degré
inférieur à d
où d est un entier supérieur à 2 donné.
Quel est le plus grand entier k tel que, pour tous sous-ensembles disjoints
A, B de Fp dont l'union a k
éléments, il existe un polynôme P dans
E(d) satisfaisant aux contraintes suivantes :
P(x) est dans S pour x dans A,
P(x) est en dehors de S si
x appartient à B ?
Cet entier k correspond à la complexité de familles
d'ensembles pseudo-aléatoires construites à partir des
polynômes de
E(d)
et de l'ensemble cible S. Nous montrerons que cette complexité
est bornée indépendamment de p dans le cas où
S est un ensemble d'entiers
consécutifs mais qu'elle est de taille très importante
quand S est l'ensemble des inverses modulo p d'une suite d'entiers
consécutifs.
Nous présenterons également des résultats valables
pour des ensembles S généraux tels que | S | et
| Fp \ S | soient assez grands.
Cet exposé est fondé sur des travaux réalisés avec
R. Balasubramanian, D. Gómez-Pérez, E. Mosaki et
A. Sárközy.