On the Pseudorandomness of the Liouville Function of Polynomials over a Finite Field

László Mérai; Arne Winterhof

doi:10.1515/udt-2016-0004

.blurhash-client-img { display: none !important; }

On the Pseudorandomness of the Liouville Function of Polynomials over a Finite Field

Uniform distribution theory

Volume 11 (2016): Issue 1 (June 2016)

By: László Mérai and Arne Winterhof

Open Access

|Jan 2017

Abstract

We study several pseudorandom properties of the Liouville function and the Möbius function of polynomials over a finite field. More precisely, we obtain bounds on their balancedness as well as their well-distribution measure, correlation measure, and linear complexity profile.

References

[1] BRANDSTÄTTER, N.—WINTERHOF, A.: Linear complexity profile of binary sequences with small correlation measure, Period. Math. Hungar. 52 (2006), no. 2, 1–8.10.1007/s10998-006-0008-1
Open DOI Search in Google Scholar Back to article
[2] CARLITZ, L.: The arithmetic of polynomials in a Galois field, Amer. J.Math. 54 (1932), no. 1, 39-50.
Search in Google Scholar Back to article
[3] CARMON, D.—RUDNICK, Z.: The autocorrelation of the Möbius function and Chowla’s conjecture for the rational function field, Q. J. Math. 65 (2014), no. 1, 53–61.10.1093/qmath/has047
Open DOI Search in Google Scholar Back to article
[4] CASSAIGNE J.—FERENCZI, S.—MAUDUIT, C.—RIVAT, J.—SÁRKÖZY, A.: On finite pseudorandom binary sequences. III. The Liouville function. I, Acta Arith. 87 (1999), no. 4, 367–390.
Search in Google Scholar Back to article
[5] CASSAIGNE J.—FERENCZI, S.—MAUDUIT, C.—RIVAT, J.—SÁRKÖZY, A.: On finite pseudorandom binary sequences. IV. The Liouville function. II, Acta Arith. 95 (2000), no. 4, 343–359.
Search in Google Scholar Back to article
[6] CONRAD, K.: Irreducible values of polynomials: a non-analogy, Number fields and function fields-two parallel worlds, Progr. Math. Vol. 239, Birkhäuser Boston, Boston, MA, 2005. pp. 71–85.10.1007/0-8176-4447-4_5
Search in Google Scholar Back to article
[7] IWANIEC, H.—KOWALSKI, E.: Analytic Number Theory, Amer. Math. Soc. Colloq. Publ., Vol. 53, Amer. Math. Soc., Providence, RI, 2004.
Search in Google Scholar Back to article
[8] LIDL, R.—NIEDERREITER, H.: Finite fields (Second ed.), Encyclopedia of Mathematics and its Applications. Vol. 20, Cambridge University Press, Cambridge, 1997.
Search in Google Scholar Back to article
[9] MAUDUIT, C.—SÁRKÖZY, A.: On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol, Acta Arith. 82 (1997), no. 4, 365–377.
Search in Google Scholar Back to article
[10] MÉRAI, L.—YAYLA, O.: Improving results on the pseudorandomness of sequences generated via the additive order, Discrete Math. 338 (2015), no. 11, 2020–2025.10.1016/j.disc.2015.04.015
Open DOI Search in Google Scholar Back to article
[11] PELLET, A. E.: Sur la décomposition dune fonction entiére en facteurs irréductibles suivant un module premier, Comptes Rendus de l’Académie des Sciences Paris 86 (1878), 1071–1072.
Search in Google Scholar Back to article
[12] ROSEN, M.: Number Theory in Function Fields, Graduate Texts in Mathematics, Vol. 210. Springer-Verlag, New York, 2002.10.1007/978-1-4757-6046-0
Search in Google Scholar Back to article
[13] SCHMIDT, W. M.: Equations over finite fields: An Elementary Approach (Second ed.), Kendrick Press, Heber City, UT, 2004.
Search in Google Scholar Back to article
[14] SKOLEM, T.: On a certain connection between the discriminant of a polynomial and the umber of its irreducible factors modp, Norsk. Mat. Tidsskr. 34 (1952), 81–85.
Search in Google Scholar Back to article
[15] STICKELBERGER, L.: Über eine neue Eigenschaft der Diskriminanten algebraischer Zahlkörper Verh. 1. Internat. Math.-Kongress. Zürich, 1897, Teubner, Leipzig, 1898, 182–193.
Search in Google Scholar Back to article
[16] SWAN, R. G.: Factorization of polynomials over finite fields Pacific J. Math. 12 (1962), 1099–1106.
Search in Google Scholar Back to article
[17] TOPUZOĞLU, A.—WINTERHOF, A.: Pseudorandom sequences Topics in Geometry, Coding Theory and Cryptography, Algebr. Appl., Vol. 6, Springer, Dordrecht, 2007, pp. 135–166.10.1007/1-4020-5334-4_4
Search in Google Scholar Back to article
[18] WINTERHOF, A.: Some estimates for character sums and applications, Des. Codes Cryptogr. 22 (2001), no. 2, 123–131.
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.1515/udt-2016-0004 | Journal eISSN: 2309-5377 | Journal ISSN: 1336-913X

Journal RSS Feed

Language: English

Page range: 47 - 58

Submitted on: Apr 27, 2015

Accepted on: Aug 31, 2015

Published on: Jan 13, 2017

Published by: Slovak Academy of Sciences, Mathematical Institute

In partnership with: Paradigm Publishing Services

Publication frequency: 2 issues per year

Keywords:

polynomials,

finite fields,

irreducible factors,

pseudorandom sequence,

polynomial Liouville function,

polynomial Möbius function

Related subjects:

Mathematics,

Algebra and number theory,

Discrete mathematics,

Probability and statistics,

Numerical and computational mathematics

© 2017 László Mérai, Arne Winterhof, published by Slovak Academy of Sciences, Mathematical Institute
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 11 (2016): Issue 1 (June 2016)