On the complexity of families of pseudo-random subsets

Ramachandran Balasubramanian[1]; Cécile Dartyge[2]; Élie Mosaki[3]

  • [1] Institute of Mathematical Sciences C.I.T. Campus Taramani, Chennai 600113 (India)
  • [2] Université de Lorraine Institut Élie Cartan BP 70239 54506 Vandœuvre-lès-Nancy Cedex (France)
  • [3] 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 (2014)

  • Volume: 64, Issue: 1, page 267-296
  • ISSN: 0373-0956

Abstract

top
In this paper we are interested in the following problem. Let p be a prime number, S ⊂ 𝔽 p and 𝒫 ⊂ { P ∈ 𝔽 p [ X ] : deg P ≤ d } . 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.

How to cite

top

Balasubramanian, Ramachandran, Dartyge, Cécile, and Mosaki, Élie. "Sur la complexité de familles d’ensembles pseudo-aléatoires." Annales de l’institut Fourier 64.1 (2014): 267-296. <http://eudml.org/doc/275591>.

@article{Balasubramanian2014,
abstract = {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.},
affiliation = {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)},
author = {Balasubramanian, Ramachandran, Dartyge, Cécile, Mosaki, Élie},
journal = {Annales de l’institut Fourier},
keywords = {pseudo-random subsets; complexity; exponential sums; character sums},
language = {fre},
number = {1},
pages = {267-296},
publisher = {Association des Annales de l’institut Fourier},
title = {Sur la complexité de familles d’ensembles pseudo-aléatoires},
url = {http://eudml.org/doc/275591},
volume = {64},
year = {2014},
}

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
PB - Association des Annales de l’institut Fourier
VL - 64
IS - 1
SP - 267
EP - 296
AB - 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.
LA - fre
KW - pseudo-random subsets; complexity; exponential sums; character sums
UR - http://eudml.org/doc/275591
ER -

References

top
  1. Alan Adolphson, Steven Sperber, Exponential sums and Newton polyhedra : cohomology and estimates, Ann. of Math. (2) 130 (1989), 367-406 Zbl0723.14017MR1014928
  2. Rudolf Ahlswede, Levon H. Khachatrian, C. Mauduit, András Sárközy, A complexity measure for families of binary sequences, Period. Math. Hungar. 46 (2003), 107-118 Zbl1050.11069MR2004667
  3. B. J. Birch, Enrico Bombieri, Appendix : On some exponential sums, Annals of Math. 121 (1985), 345-350 MR786351
  4. Enrico Bombieri, On exponential sums in finite fields, Amer. J. Math. 88 (1966), 71-105 Zbl0171.41504MR200267
  5. Cécile Dartyge, Elie Mosaki, András Sárközy, On large families of subsets of the set of the integers not exceeding N , Ramanujan J. 18 (2009), 209-229 Zbl1226.05006MR2475937
  6. Cécile Dartyge, András Sárközy, Large families of pseudorandom subsets formed by power residues, Unif. Distrib. Theory 2 (2007), 73-88 Zbl1140.05004MR2377457
  7. Cécile Dartyge, András Sárközy, On pseudo-random subsets of the set of the integers not exceeding N , Period. Math. Hungar. 54 (2007), 183-200 Zbl1174.05001MR2337317
  8. Cécile Dartyge, András Sárközy, Mihály Szalay, On the pseudo-randomness of subsets related to primitive roots, Combinatorica 30 (2010), 139-162 Zbl1259.11072MR2676832
  9. Pierre Deligne, La conjecture de Weil. I, Inst. Hautes Études Sci. Publ. Math. (1974), 273-307 Zbl0287.14001MR340258
  10. Bernard Dwork, On the rationality of the zeta function of an algebraic variety, Amer. J. Math. 82 (1960), 631-648 Zbl0173.48501MR140494
  11. Jürgen Eichenauer-Herrmann, Harald Niederreiter, Bounds for exponential sums and their applications to pseudorandom numbers, Acta Arith. 67 (1994), 269-281 Zbl0957.11050MR1292739
  12. John B. Friedlander, Henryk Iwaniec, Incomplete Kloosterman sums and a divisor problem, Ann. of Math. (2) 121 (1985), 319-350 Zbl0572.10029MR786351
  13. Ben Green, Imre Z. Ruzsa, Sum-free sets in abelian groups, Israel J. Math. 147 (2005), 157-188 Zbl1158.11311MR2166359
  14. C. Hooley, On exponential sums and certain of their applications, Number theory days, 1980 (Exeter, 1980) 56 (1982), 92-122, Cambridge Univ. Press, Cambridge Zbl0488.10041MR697259
  15. Pascal Hubert, András Sárközy, On p -pseudorandom binary sequences, Period. Math. Hungar. 49 (2004), 73-91 Zbl1073.11054MR2092784
  16. Serge Lang, André Weil, Number of points of varieties in finite fields, Amer. J. Math. 76 (1954), 819-827 Zbl0058.27202MR65218
  17. Christian Mauduit, Joël Rivat, András Sárközy, Construction of pseudorandom binary sequences using additive characters, Monatsh. Math. 141 (2004), 197-208 Zbl1110.11024MR2042211
  18. Christian Mauduit, András Sárközy, On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol, Acta Arith. 82 (1997), 365-377 Zbl0886.11048MR1483689
  19. Antonio Rojas-León, Purity of exponential sums on 𝔸 n . II, J. Reine Angew. Math. 603 (2007), 35-53 Zbl1214.11090MR2312553
  20. András Sárközy, A finite pseudorandom binary sequence, Studia Sci. Math. Hungar 38 (2001), 377-384 Zbl0997.11062MR1877793
  21. Wolfgang M. Schmidt, Equations over finite fields. An elementary approach, (1976), Springer-Verlag, Berlin Zbl0329.12001MR429733
  22. M. Waldschmidt, Le théorème de Bézout et le résultant de deux polynômes, Revue de Mathématiques Spéciales (2003–2004) 
  23. Robert J. Walker, Algebraic curves, (1978), Springer-Verlag, New York Zbl0399.14016MR513824

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.