Sur la complexité de familles d’ensembles pseudo-aléatoires
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𝔽 p et 𝒫{P𝔽 p [X]:degPd}. Quel est le plus grand entier k tel que pour toutes paires de sous-ensembles disjoints 𝒜, de 𝔽 p vérifiant |𝒜|=k, il existe P𝒫 tel que P(x)S si x𝒜 et P(x)S si x  ? 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𝔽 p and 𝒫{P𝔽 p [X]:degPd}. What is the largest integer k such that for all subsets 𝒜, of 𝔽 p satisfying 𝒜= and |𝒜|=k, there exists P𝒫 such that P(x)S if x𝒜 and P(x)S if x? 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.

DOI : https://doi.org/10.5802/aif.2847
Classification : 11K45,  11L07,  05B10
Mots clés : Sous-ensembles pseudo-aléatoires, complexité, sommes d’exponentielles, sommes de caractères
@article{AIF_2014__64_1_267_0,
     author = {Balasubramanian, Ramachandran and Dartyge, C\'ecile and Mosaki, \'Elie},
     title = {Sur la complexit\'e de familles d{\textquoteright}ensembles pseudo-al\'eatoires},
     journal = {Annales de l'Institut Fourier},
     pages = {267--296},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {64},
     number = {1},
     year = {2014},
     doi = {10.5802/aif.2847},
     mrnumber = {3330549},
     zbl = {06387274},
     language = {fr},
     url = {http://archive.numdam.org/articles/10.5802/aif.2847/}
}
Balasubramanian, Ramachandran; Dartyge, Cécile; Mosaki,  Élie. Sur la complexité de familles d’ensembles pseudo-aléatoires. Annales de l'Institut Fourier, Tome 64 (2014) no. 1, pp. 267-296. doi : 10.5802/aif.2847. http://archive.numdam.org/articles/10.5802/aif.2847/

[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 | Article | MR 1014928 | Zbl 0723.14017

[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 | Article | MR 2004667 | Zbl 1050.11069

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

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

[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 | Article | MR 2475937 | Zbl 1226.05006

[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 2377457 | Zbl 1140.05004

[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 2337317 | Zbl 1174.05001

[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 | Article | MR 2676832 | Zbl 1259.11072

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

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

[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 1292739 | Zbl 0957.11050

[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) | Article | MR 786351 | Zbl 0572.10029

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

[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 697259 | Zbl 0488.10041

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

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

[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 | Article | MR 2042211 | Zbl 1110.11024

[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 1483689 | Zbl 0886.11048

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

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

[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 429733 | Zbl 0329.12001

[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 513824 | Zbl 0399.14016