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

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

doi:10.5802/aif.2847

Balasubramanian, Ramachandran ¹ ; Dartyge, Cécile ² ; Mosaki, Élie ³

¹ Institute of Mathematical Sciences C.I.T. Campus Taramani, Chennai 600113 (India)
² Université de Lorraine Institut Élie Cartan BP 70239 54506 Vandœuvre-lès-Nancy Cedex (France)
³ Université de Lyon Université Lyon 1 Institut Camille Jordan CNRS UMR 5208 43, boulevard du 11 Novembre 1918 69622 Villeurbanne (France)

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

Résumé
Abstract

Dans cet article, on s’intéresse au problème suivant. Soient $p$ un nombre premier, $S \subset 𝔽_{p}$ et $𝒫 \subset {P \in 𝔽_{p} [X] : deg P \leq 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 (x) \in S$ si $x \in 𝒜$ et $P (x) \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} [X] : deg P \leq d}$ . What is the largest integer $k$ such that for all subsets $𝒜, ℬ$ of $𝔽_{p}$ satisfying $𝒜 \cap ℬ = \emptyset$ and $| 𝒜 \cup ℬ | = k$ , there exists $P \in 𝒫$ such that $P (x) \in S$ if $x \in 𝒜$ and $P (x) \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.

MR Zbl

DOI : 10.5802/aif.2847

Classification : 11K45, 11L07, 05B10
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

Affiliations des auteurs :

Balasubramanian, Ramachandran ¹ ; Dartyge, Cécile ² ; Mosaki, Élie ³

@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, Tome 64 (2014) no. 1, pp. 267-296. doi : 10.5802/aif.2847. https://aif.centre-mersenne.org/articles/10.5802/aif.2847/

Bibliographie
Cité par

[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

Cité par Sources :

ANNALES DE L'INSTITUT FOURIER

ARTICLES À PARAÎTRE

FEUILLETER

PRESENTATION

COMITÉ DE RÉDACTION

SOUMETTRE UN ARTICLE

ABONNEMENT