Sur la complexité de familles d’ensembles pseudo-aléatoires

Balasubramanian, Ramachandran; Dartyge, Cécile; Mosaki, Élie

Annales de l'Institut Fourier, Tome 64 (2014) no. 1, pp. 267-296.

Dans cet article, on s’intéresse au problème suivant. Soient $p$ un nombre premier, $S\subset {𝔽}_p$ et $𝒫\subset \{P\in {𝔽}_p\left[X\right]:degP\le d\}$. Quel est le plus grand entier $k$ tel que pour toutes paires de sous-ensembles disjoints $𝒜,ℬ$ de ${𝔽}_p$ vérifiant $|𝒜\cup ℬ|=k$, il existe $P\in 𝒫$ tel que $P\left(x\right)\in S$ si $x\in 𝒜$ et $P\left(x\right)\notin S$ si $x\in ℬ$  ? Ce problème correspond à l’étude de la complexité de certaines familles d’ensembles pseudo-aléatoires. Dans un premier temps, nous rappelons la définition de cette complexité et resituons le contexte des ensembles pseudo-aléatoires. Ensuite, nous exposons les différents résultats obtenus selon la nature des ensembles $S$ et $𝒫$ étudiés. Certaines preuves passent par des majorations de sommes d’exponentielles ou de caractères sur des corps finis, d’autres combinent des arguments combinatoires avec des résultats de la théorie additive des nombres.

In this paper we are interested in the following problem. Let $p$ be a prime number, $S\subset {𝔽}_p$ and $𝒫\subset \{P\in {𝔽}_p\left[X\right]:degP\le d\}$. What is the largest integer $k$ such that for all subsets $𝒜,ℬ$ of ${𝔽}_p$ satisfying $𝒜\cap ℬ=\varnothing$ and $|𝒜\cup ℬ|=k$, there exists $P\in 𝒫$ such that $P\left(x\right)\in S$ if $x\in 𝒜$ and $P\left(x\right)\notin S$ if $x\in ℬ$? This problem corresponds to the study of the complexity of some families of pseudo-random subsets. First we recall this complexity definition and the context of pseudo-random subsets. Then we state the different results we have obtained according to the shape of the sets $S$ and $𝒫$ considered. Some proofs are based on upper bounds for exponential sums or characters sums in finite fields, other proofs use combinatorics and additive number theory.

[1] Adolphson, Alan; Sperber, Steven Exponential sums and Newton polyhedra : cohomology and estimates, Ann. of Math. (2), Volume 130 (1989) no. 2, pp. 367-406 | DOI | MR | Zbl

[2] Ahlswede, Rudolf; Khachatrian, Levon H.; Mauduit, C.; Sárközy, András A complexity measure for families of binary sequences, Period. Math. Hungar., Volume 46 (2003) no. 2, pp. 107-118 | DOI | MR | Zbl

[3] Birch, B. J.; Bombieri, Enrico Appendix : On some exponential sums, Annals of Math., Volume 121 (1985), pp. 345-350 | DOI | MR

[4] Bombieri, Enrico On exponential sums in finite fields, Amer. J. Math., Volume 88 (1966), pp. 71-105 | DOI | MR | Zbl

[5] Dartyge, Cécile; Mosaki, Elie; Sárközy, András On large families of subsets of the set of the integers not exceeding $N$, Ramanujan J., Volume 18 (2009) no. 2, pp. 209-229 | DOI | MR | Zbl

[6] Dartyge, Cécile; Sárközy, András Large families of pseudorandom subsets formed by power residues, Unif. Distrib. Theory, Volume 2 (2007) no. 2, pp. 73-88 | MR | Zbl

[7] Dartyge, Cécile; Sárközy, András On pseudo-random subsets of the set of the integers not exceeding $N$, Period. Math. Hungar., Volume 54 (2007) no. 2, pp. 183-200 | MR | Zbl

[8] Dartyge, Cécile; Sárközy, András; Szalay, Mihály On the pseudo-randomness of subsets related to primitive roots, Combinatorica, Volume 30 (2010) no. 2, pp. 139-162 | DOI | MR | Zbl

[9] Deligne, Pierre La conjecture de Weil. I, Inst. Hautes Études Sci. Publ. Math. (1974) no. 43, pp. 273-307 | DOI | Numdam | MR | Zbl

[10] Dwork, Bernard On the rationality of the zeta function of an algebraic variety, Amer. J. Math., Volume 82 (1960), pp. 631-648 | DOI | MR | Zbl

[11] Eichenauer-Herrmann, Jürgen; Niederreiter, Harald Bounds for exponential sums and their applications to pseudorandom numbers, Acta Arith., Volume 67 (1994) no. 3, pp. 269-281 | MR | Zbl

[12] Friedlander, John B.; Iwaniec, Henryk Incomplete Kloosterman sums and a divisor problem, Ann. of Math. (2), Volume 121 (1985) no. 2, pp. 319-350 (With an appendix by Bryan J. Birch and Enrico Bombieri) | DOI | MR | Zbl

[13] Green, Ben; Ruzsa, Imre Z. Sum-free sets in abelian groups, Israel J. Math., Volume 147 (2005), pp. 157-188 | DOI | MR | Zbl

[14] Hooley, C. On exponential sums and certain of their applications, Number theory days, 1980 (Exeter, 1980) (London Math. Soc. Lecture Note Ser.), Volume 56, Cambridge Univ. Press, Cambridge, 1982, pp. 92-122 | MR | Zbl

[15] Hubert, Pascal; Sárközy, András On $p$-pseudorandom binary sequences, Period. Math. Hungar., Volume 49 (2004) no. 1, pp. 73-91 | DOI | MR | Zbl

[16] Lang, Serge; Weil, André Number of points of varieties in finite fields, Amer. J. Math., Volume 76 (1954), pp. 819-827 | DOI | MR | Zbl

[17] Mauduit, Christian; Rivat, Joël; Sárközy, András Construction of pseudorandom binary sequences using additive characters, Monatsh. Math., Volume 141 (2004) no. 3, pp. 197-208 | DOI | MR | Zbl

[18] Mauduit, Christian; Sárközy, András On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol, Acta Arith., Volume 82 (1997) no. 4, pp. 365-377 | MR | Zbl

[19] Rojas-León, Antonio Purity of exponential sums on ${𝔸}^n$. II, J. Reine Angew. Math., Volume 603 (2007), pp. 35-53 | DOI | MR | Zbl

[20] Sárközy, András A finite pseudorandom binary sequence, Studia Sci. Math. Hungar, Volume 38 (2001), pp. 377-384 | MR | Zbl

[21] Schmidt, Wolfgang M. Equations over finite fields. An elementary approach, Lecture Notes in Mathematics, Vol. 536, Springer-Verlag, Berlin, 1976, pp. ix+276 | MR | Zbl

[22] Waldschmidt, M. Le théorème de Bézout et le résultant de deux polynômes, Revue de Mathématiques Spéciales, 2003–2004 (Numéro 114-1)

[23] Walker, Robert J. Algebraic curves, Springer-Verlag, New York, 1978, pp. x+201 (Reprint of the 1950 edition) | MR | Zbl