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), p. 267-296 / Harvested from Numdam

Résumé

Dans cet article, on s’intéresse au problème suivant. Soient $p$ un nombre premier, $S\subset {\mathbb{F}}_p$ et ${\mathcal{P}}\subset \lbrace P\in {\mathbb{F}}_p [X] : \deg P\le d \rbrace $. Quel est le plus grand entier $k$ tel que pour toutes paires de sous-ensembles disjoints ${\mathcal{A}} ,{\mathcal{B}}$ de ${\mathbb{F}}_p$ vérifiant $|{\mathcal{A}}\cup {\mathcal{B}} |=k$, il existe $P\in {\mathcal{P}}$ tel que $P(x)\in S$ si $x\in {\mathcal{A}}$ et $P(x)\notin S$ si $x\in {\mathcal{B}}$  ? 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 ${\mathcal{P}}$ é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.

Abstract

In this paper we are interested in the following problem. Let $p$ be a prime number, $S\subset {\mathbb{F}}_p$ and ${\mathcal{P}}\subset \lbrace P\in {\mathbb{F}}_p [X] : \deg P\le d\rbrace $. What is the largest integer $k$ such that for all subsets ${\mathcal{A}}, {\mathcal{B}}$ of ${\mathbb{F}}_p$ satisfying ${\mathcal{A}}\cap {\mathcal{B}} =\emptyset$ and $|{\mathcal{A}}\cup {\mathcal{B}} |=k$, there exists $P\in {\mathcal{P}}$ such that $P(x)\in S$ if $x\in {\mathcal{A}}$ and $P(x)\notin S$ if $x\in {\mathcal{B}}$? 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 ${\mathcal{P}}$ 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.

Détail

Publié le : 2014-01-01

MR 3330549 | Zbl 06387274

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

Bibliographie

[1] Adolphson, Alan; Sperber, Steven Exponential sums and Newton polyhedra : cohomology and estimates, Ann. of Math. (2), Tome 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., Tome 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., Tome 121 (1985), pp. 345-350 | Article | MR 786351

[4] Bombieri, Enrico On exponential sums in finite fields, Amer. J. Math., Tome 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., Tome 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, Tome 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., Tome 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, Tome 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., Tome 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., Tome 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), Tome 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., Tome 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), Cambridge Univ. Press, Cambridge (London Math. Soc. Lecture Note Ser.) Tome 56 (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., Tome 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., Tome 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., Tome 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., Tome 82 (1997) no. 4, pp. 365-377 | MR 1483689 | Zbl 0886.11048

[19] Rojas-León, Antonio Purity of exponential sums on $\mathbb{A}^n$. II, J. Reine Angew. Math., Tome 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, Tome 38 (2001), pp. 377-384 | MR 1877793 | Zbl 0997.11062

[21] Schmidt, Wolfgang M. Equations over finite fields. An elementary approach, Springer-Verlag, Berlin, Lecture Notes in Mathematics, Vol. 536 (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