In this paper we are interested in the following problem. Let be a prime number, and . What is the largest integer such that for all subsets of satisfying and , there exists such that if and if ? 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 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.
Dans cet article, on s’intéresse au problème suivant. Soient un nombre premier, et . Quel est le plus grand entier tel que pour toutes paires de sous-ensembles disjoints de vérifiant , il existe tel que si et si ? 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 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.
Mot clés : Sous-ensembles pseudo-aléatoires, complexité, sommes d’exponentielles, sommes de caractères
Keywords: pseudo-random subsets, complexity, exponential sums, character sums
Balasubramanian, Ramachandran 1; Dartyge, Cécile 2; Mosaki, Élie 3
@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 = {https://aif.centre-mersenne.org/articles/10.5802/aif.2847/} }
TY - JOUR AU - Balasubramanian, Ramachandran AU - Dartyge, Cécile AU - Mosaki, Élie TI - Sur la complexité de familles d’ensembles pseudo-aléatoires JO - Annales de l'Institut Fourier PY - 2014 SP - 267 EP - 296 VL - 64 IS - 1 PB - Association des Annales de l’institut Fourier UR - https://aif.centre-mersenne.org/articles/10.5802/aif.2847/ DO - 10.5802/aif.2847 LA - fr ID - AIF_2014__64_1_267_0 ER -
%0 Journal Article %A Balasubramanian, Ramachandran %A Dartyge, Cécile %A Mosaki, Élie %T Sur la complexité de familles d’ensembles pseudo-aléatoires %J Annales de l'Institut Fourier %D 2014 %P 267-296 %V 64 %N 1 %I Association des Annales de l’institut Fourier %U https://aif.centre-mersenne.org/articles/10.5802/aif.2847/ %R 10.5802/aif.2847 %G fr %F AIF_2014__64_1_267_0
Balasubramanian, Ramachandran; Dartyge, Cécile; Mosaki, Élie. Sur la complexité de familles d’ensembles pseudo-aléatoires. Annales de l'Institut Fourier, Volume 64 (2014) no. 1, pp. 267-296. doi : 10.5802/aif.2847. https://aif.centre-mersenne.org/articles/10.5802/aif.2847/
[1] Exponential sums and Newton polyhedra : cohomology and estimates, Ann. of Math. (2), Volume 130 (1989) no. 2, pp. 367-406 | DOI | MR | Zbl
[2] A complexity measure for families of binary sequences, Period. Math. Hungar., Volume 46 (2003) no. 2, pp. 107-118 | DOI | MR | Zbl
[3] Appendix : On some exponential sums, Annals of Math., Volume 121 (1985), pp. 345-350 | DOI | MR
[4] On exponential sums in finite fields, Amer. J. Math., Volume 88 (1966), pp. 71-105 | DOI | MR | Zbl
[5] On large families of subsets of the set of the integers not exceeding , Ramanujan J., Volume 18 (2009) no. 2, pp. 209-229 | DOI | MR | Zbl
[6] Large families of pseudorandom subsets formed by power residues, Unif. Distrib. Theory, Volume 2 (2007) no. 2, pp. 73-88 | MR | Zbl
[7] On pseudo-random subsets of the set of the integers not exceeding , Period. Math. Hungar., Volume 54 (2007) no. 2, pp. 183-200 | MR | Zbl
[8] On the pseudo-randomness of subsets related to primitive roots, Combinatorica, Volume 30 (2010) no. 2, pp. 139-162 | DOI | MR | Zbl
[9] La conjecture de Weil. I, Inst. Hautes Études Sci. Publ. Math. (1974) no. 43, pp. 273-307 | DOI | Numdam | MR | Zbl
[10] On the rationality of the zeta function of an algebraic variety, Amer. J. Math., Volume 82 (1960), pp. 631-648 | DOI | MR | Zbl
[11] Bounds for exponential sums and their applications to pseudorandom numbers, Acta Arith., Volume 67 (1994) no. 3, pp. 269-281 | MR | Zbl
[12] 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] Sum-free sets in abelian groups, Israel J. Math., Volume 147 (2005), pp. 157-188 | DOI | MR | Zbl
[14] 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] On -pseudorandom binary sequences, Period. Math. Hungar., Volume 49 (2004) no. 1, pp. 73-91 | DOI | MR | Zbl
[16] Number of points of varieties in finite fields, Amer. J. Math., Volume 76 (1954), pp. 819-827 | DOI | MR | Zbl
[17] Construction of pseudorandom binary sequences using additive characters, Monatsh. Math., Volume 141 (2004) no. 3, pp. 197-208 | DOI | MR | Zbl
[18] 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] Purity of exponential sums on . II, J. Reine Angew. Math., Volume 603 (2007), pp. 35-53 | DOI | MR | Zbl
[20] A finite pseudorandom binary sequence, Studia Sci. Math. Hungar, Volume 38 (2001), pp. 377-384 | MR | Zbl
[21] Equations over finite fields. An elementary approach, Lecture Notes in Mathematics, Vol. 536, Springer-Verlag, Berlin, 1976, pp. ix+276 | MR | Zbl
[22] 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] Algebraic curves, Springer-Verlag, New York, 1978, pp. x+201 (Reprint of the 1950 edition) | MR | Zbl
Cited by Sources: