On étudie les sommes exponentielles de la forme , où sont des entiers premiers entre eux, p est un polynôme à coefficients dans et , avec . On démontre que . Ceci généralise un résultat de J. Bourgain, qui établit cette borne dans le cas où q est impair. Ce théorème a des conséquences dans l'étude de la complexité des circuits booléens.
We study exponential sums of the form , where are relatively prime, p is a polynomial with coefficients in , and for some . We prove an upper bound of the form on . This generalizes a result of J. Bourgain, who establishes this bound in the case where q is odd. This bound has consequences in Boolean circuit complexity.
Accepté le :
Publié le :
@article{CRMATH_2005__341_5_279_0, author = {Green, Frederic and Roy, Amitabha and Straubing, Howard}, title = {Bounds on an exponential sum arising in {Boolean} circuit complexity}, journal = {Comptes Rendus. Math\'ematique}, pages = {279--282}, publisher = {Elsevier}, volume = {341}, number = {5}, year = {2005}, doi = {10.1016/j.crma.2005.07.011}, language = {en}, url = {http://www.numdam.org/articles/10.1016/j.crma.2005.07.011/} }
TY - JOUR AU - Green, Frederic AU - Roy, Amitabha AU - Straubing, Howard TI - Bounds on an exponential sum arising in Boolean circuit complexity JO - Comptes Rendus. Mathématique PY - 2005 SP - 279 EP - 282 VL - 341 IS - 5 PB - Elsevier UR - http://www.numdam.org/articles/10.1016/j.crma.2005.07.011/ DO - 10.1016/j.crma.2005.07.011 LA - en ID - CRMATH_2005__341_5_279_0 ER -
%0 Journal Article %A Green, Frederic %A Roy, Amitabha %A Straubing, Howard %T Bounds on an exponential sum arising in Boolean circuit complexity %J Comptes Rendus. Mathématique %D 2005 %P 279-282 %V 341 %N 5 %I Elsevier %U http://www.numdam.org/articles/10.1016/j.crma.2005.07.011/ %R 10.1016/j.crma.2005.07.011 %G en %F CRMATH_2005__341_5_279_0
Green, Frederic; Roy, Amitabha; Straubing, Howard. Bounds on an exponential sum arising in Boolean circuit complexity. Comptes Rendus. Mathématique, Tome 341 (2005) no. 5, pp. 279-282. doi : 10.1016/j.crma.2005.07.011. http://www.numdam.org/articles/10.1016/j.crma.2005.07.011/
[1] N. Alon, R. Beigel, Lower bounds for approximation by low-degree polynomials over , in: Annual IEEE Conference on Computational Complexity, vol. 16, 2001
[2] Estimation of certain exponential sums arising in complexity theory, C. R. Acad. Sci. Paris, Ser. I, Volume 340 (2005), pp. 627-631
[3] E. Dueñez, S. Miller, A. Roy, H. Straubing, Incomplete quadratic exponential sums in several variables, J. Number Theory, in press
[4] The correlation between parity and quadratic polynomials mod 3, J. Comput. System Sci., Volume 69 (2004) no. 1, pp. 28-44
Cité par Sources :