Geodesic
Value Sets of Sparse Polynomials
Canadian mathematical bulletin, Tome 63 (2020) no. 1, pp. 187-196

Voir la notice de l'article provenant de la source Cambridge University Press

We obtain a new lower bound on the size of the value set $\mathscr{V}(f)=f(\mathbb{F}_{p})$ of a sparse polynomial $f\in \mathbb{F}_{p}[X]$ over a finite field of $p$ elements when $p$ is prime. This bound is uniform with respect to the degree and depends on some natural arithmetic properties of the degrees of the monomial terms of $f$ and the number of these terms. Our result is stronger than those that can be extracted from the bounds on multiplicities of individual values in $\mathscr{V}(f)$.
DOI : 10.4153/S0008439519000316
Mots-clés : sparse polynomial, value set, rational point on curve 
Shparlinski, Igor E.; Voloch, José Felipe. Value Sets of Sparse Polynomials. Canadian mathematical bulletin, Tome 63 (2020) no. 1, pp. 187-196. doi: 10.4153/S0008439519000316
@article{10_4153_S0008439519000316,
     author = {Shparlinski, Igor E. and Voloch, Jos\'e Felipe},
     title = {Value {Sets} of {Sparse} {Polynomials}},
     journal = {Canadian mathematical bulletin},
     pages = {187--196},
     year = {2020},
     volume = {63},
     number = {1},
     doi = {10.4153/S0008439519000316},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000316/}
}
TY  - JOUR
AU  - Shparlinski, Igor E.
AU  - Voloch, José Felipe
TI  - Value Sets of Sparse Polynomials
JO  - Canadian mathematical bulletin
PY  - 2020
SP  - 187
EP  - 196
VL  - 63
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000316/
DO  - 10.4153/S0008439519000316
ID  - 10_4153_S0008439519000316
ER  - 
%0 Journal Article
%A Shparlinski, Igor E.
%A Voloch, José Felipe
%T Value Sets of Sparse Polynomials
%J Canadian mathematical bulletin
%D 2020
%P 187-196
%V 63
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/S0008439519000316/
%R 10.4153/S0008439519000316
%F 10_4153_S0008439519000316

[BCR16] Bi, J., Cheng, Q., and Rojas, J. M., Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields. SIAM J. Comput. 45(2016), 1433–1447. https://doi.org/10.1137/140990401 Google Scholar

[BS-D59] Birch, B. J. and Swinnerton-Dyer, H. P. F., Note on a problem of Chowla. Acta Arith. 5(1959), 417–423. https://doi.org/10.4064/aa-5-4-417-423 Google Scholar

[CFKLLS] Canetti, R., Friedlander, J. B., Konyagin, S. V., Larsen, M., Lieman, D., and Shparlinski, I. E., On the statistical properties of Diffie-Hellman distributions. Israel J. Math. 120(2000), 23–46. https://doi.org/10.1007/s11856-000-1270-1 Google Scholar

[CLMS61] Carlitz, L., Lewis, D. J., Mills, W. H., and Strauss, E. G., Polynomials over finite fields with minimal value sets. Mathematika 8(1961), 121–130. https://doi.org/10.1112/S0025579300002230 Google Scholar

[CGRW17] Cheng, Q., Gao, S., Rojas, J. M., and Wan, D., Sparse univariate polynomials with many roots over finite fields. Finite Fields Appl. 46(2017), 235–246. https://doi.org/10.1016/j.ffa.2017.03.006 Google Scholar

[Kel16] Kelley, A., Roots of sparse polynomials over a finite field. LMS J. Comput. Math. 19(2016), suppl. A, 196–204. https://doi.org/10.1112/S1461157016000334 Google Scholar

[Kur09] Kurlberg, P., Poisson spacing statistics for value sets of polynomials. Int. J. Number Theory 5(2009), 489–513. https://doi.org/10.1142/S1793042109002237 Google Scholar

[Lor96] Lorenzini, D., An invitation to arithmetic geometry. Graduate Studies in Mathematics, 9, American Mathematical Society, Providence, RI, 1996. https://doi.org/10.1090/gsm/009 Google Scholar

[Mil64] Mills, W. H., Polynomials with minimal value sets. Pacific J. Math. 14(1964), 225–241. Google Scholar

[MZ13] Mullen, G. and Zieve, M., Value sets of polynomials. In: Handbook of finite fields. CRC Press, Boca Raton, FL, 2013, pp. 232–235. https://doi.org/10.1201/b15006 Google Scholar

[St09] Stichtenoth, H., Algebraic function fields and codes. Graduate Texts in Mathematics, 254, Springer-Verlag, Berlin, 2009. Google Scholar

[SV86] Stöhr, K. O. and Voloch, J. F., Weierstrass points and curves over finite fields. Proc. London Math. Soc. 52(1986), 1–19. https://doi.org/10.1112/plms/s3-52.1.1 Google Scholar

[Vol85] Voloch, J. F., Diagonal equations over function fields. Bol. Soc. Brasil. Mat. 16(1985), 29–39. https://doi.org/10.1007/BF02584799 Google Scholar

[Vol89] Voloch, J. F., On the number of values taken by a polynomial over a finite field. Acta Arith. 52(1989), 197–201. https://doi.org/10.4064/aa-52-2-197-201 Google Scholar

[WSC93] Wan, D., Shiue, P. J.-S., and Chen, C. S., Value sets of polynomials over finite fields. Proc. Amer. Math. Soc. 119(1993), 711–717. https://doi.org/10.2307/2160504 Google Scholar

[Zan07] Zannier, U., On the number of terms of a composite polynomial. Acta Arith. 127(2007), 157–168. https://doi.org/10.4064/aa127-2-5 Google Scholar

Cité par Sources :