×

Functional graphs of polynomials over finite fields. (English) Zbl 1327.05323

Summary: Given a function \(f\) in a finite field \(\mathbb{F}_q\) of \(q\) elements, we define the functional graph of \(f\) as a directed graph on \(q\) nodes labelled by the elements of \(\mathbb{F}_q\) where there is an edge from \(u\) to \(v\) if and only if \(f(u) = v\). We obtain some theoretical estimates on the number of non-isomorphic graphs generated by all polynomials of a given degree. We then develop a simple and practical algorithm to test the isomorphism of quadratic polynomials that has linear memory and time complexities. Furthermore, we extend this isomorphism testing algorithm to the general case of functional graphs, and prove that, while its time complexity deviates from linear by a (usually small) multiplier dependent on graph parameters, its memory complexity remains linear. We exploit this algorithm to provide an upper bound on the number of functional graphs corresponding to polynomials of degree \(d\) over \(\mathbb{F}_q\). Finally, we present some numerical results and compare function graphs of quadratic polynomials with those generated by random maps and pose interesting new problems.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bach, E., Toward a theory of Pollard’s rho method, Inform. and Comput., 90, 139-155 (1991) · Zbl 0716.11065
[2] Bach, E.; Bridy, A., On the number of distinct functional graphs of affine-linear transformations over finite fields, Linear Algebra Appl., 439, 1312-1320 (2013) · Zbl 1302.37064
[3] Benedetto, R. L.; Ghioca, D.; Hutz, B.; Kurlberg, P.; Scanlon, T.; Tucker, T. J., Periods of rational maps modulo primes, Math. Ann., 355, 637-660 (2013) · Zbl 1317.37111
[4] Brent, R.; Zimmerman, P., Modern Computer Arithmetic (2010), Cambridge Univ. Press
[5] Chou, W.-S.; Shparlinski, I. E., On the cycle structure of repeated exponentiation modulo a prime, J. Number Theory, 107, 345-356 (2004) · Zbl 1060.11059
[6] Crandall, R.; Pomerance, C., Prime Numbers: A Computational Perspective (2005), Springer-Verlag: Springer-Verlag New York · Zbl 1088.11001
[7] Doyle, J. R.; Faber, X.; Krumm, D., Preperiodic points for quadratic polynomials over quadratic fields, New York J. Math., 20, 507-605 (2014) · Zbl 1391.37082
[8] Faber, X., Benedetto’s trick and existence of rational preperiodic structures for quadratic polynomials, Proc. Amer. Math. Soc. (2015), in press · Zbl 1392.37116
[9] Flajolet, P.; Odlyzko, A. M., Random mapping statistics, (Lecture Notes in Comput. Sci., vol. 434 (1990), Springer-Verlag: Springer-Verlag Berlin), 329-354 · Zbl 0747.05006
[10] Flynn, E. V.; Poonen, B.; Schaefer, E. F., Cycles of quadratic polynomials and rational points on a genus-2 curve, Duke Math. J., 90, 435-463 (1997) · Zbl 0958.11024
[11] Flynn, R.; Garton, D., Graph components and dynamics over finite fields, Int. J. Number Theory, 10, 779-792 (2014) · Zbl 1309.37083
[12] Friedlander, J. B.; Pomerance, C.; Shparlinski, I. E., Period of the power generator and small values of Carmichael’s function, Math. Comp., 70, 1591-1605 (2001) · Zbl 1029.11043
[13] Fusco, G.; Bach, E., Phase transition of multivariate polynomial systems, Math. Structures Comput. Sci., 19, 9-23 (2009) · Zbl 1170.68017
[14] Gassert, T. A., Chebyshev action on finite fields, Discrete Math., 315-316, 83-94 (2014) · Zbl 1278.05111
[15] Hopcroft, J. E.; Wong, J. K., Linear time algorithm for isomorphism of planar graphs, (Proc. 6th Ann. ACM Symp. on Theory of Comp. (1974)), 172-184, (preliminary report) · Zbl 0369.05028
[16] Iwaniec, H.; Kowalski, E., Analytic Number Theory (2004), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI · Zbl 1059.11001
[17] Juul, J.; Kurlberg, P.; Madhu, K.; Tucker, T., Wreath products and proportions of periodic points · Zbl 1404.37124
[18] Kelly, P. J., A congruence theorem for trees, Pacific J. Math., 7, 961-968 (1957) · Zbl 0078.37103
[19] Knuth, D. E., The Art of Computer Programming, vol. I: Fundamental Algorithms (1968), Addison-Wesley · Zbl 0191.17903
[20] Knuth, D. E., The Art of Computer Programming, vol. II: Seminumerical Algorithms (1969), Addison-Wesley · Zbl 0191.18001
[21] Knuth, D. E., The Art of Computer Programming, vol. III: Sorting and Searching (1973), Addison-Wesley · Zbl 0302.68010
[22] Kurlberg, P.; Pomerance, C., On the period of the linear congruential and power generators, Acta Arith., 119, 149-169 (2005) · Zbl 1080.11059
[23] Lidl, R.; Niederreiter, H., Finite Fields (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge
[24] MacFie, A.; Panario, D., Random mappings with restricted preimages, (Lecture Notes in Comput. Sci., vol. 7533 (2012), Springer-Verlag: Springer-Verlag Berlin), 254-270 · Zbl 1304.94074
[25] Martin, G.; Pomerance, C., The iterated Carmichael \(λ\)-function and the number of cycles of the power generator, Acta Arith., 118, 305-335 (2005) · Zbl 1109.11046
[26] Mason, R. C., Equations over function fields, (Lecture Notes in Math., vol. 1068 (1984), Springer-Verlag: Springer-Verlag Berlin), 149-157
[27] Miller, G. L., Graph isomorphism, general remarks, J. Comput. System Sci., 2, 128-142 (1979) · Zbl 0403.03029
[28] Morton, P., Arithmetic properties of periodic points of quadratic maps. II, Acta Arith., 87, 89-102 (1998) · Zbl 1029.12002
[29] Morton, P.; Silverman, J. H., Rational periodic points of rational functions, Int. Math. Res. Not. IMRN, 2, 97-110 (1994) · Zbl 0819.11045
[30] Ostafe, A.; Sha, M., Counting Dynamical Systems Over Finite Fields, Contemp. Math. (2015), Amer. Math. Soc., in press
[31] Poonen, B., The classification of rational preperiodic points of quadratic polynomials over \(Q\): a refined conjecture, Math. Z., 228, 11-29 (1998) · Zbl 0902.11025
[32] Sha, M.; Hu, S., Monomial dynamical systems of dimension one over finite fields, Acta Arith., 148, 309-331 (2011) · Zbl 1272.37040
[33] Silverman, J. H., The \(S\)-unit equation over function fields, Proc. Cambridge Philos. Soc., 95, 3-4 (1984) · Zbl 0533.10013
[34] Somer, L.; Křížek, M., The structure of digraphs associated with the congruence \(x^k \equiv y(mod n)\), Czechoslovak Math. J., 61, 337-358 (2011) · Zbl 1249.11006
[35] Snyder, N., An alternate proof of Mason’s theorem, Elem. Math., 55, 93-94 (2000) · Zbl 1031.11012
[36] Stothers, W. W., Polynomial identities and Hauptmoduln, Quart. J. Math., 32, 349-370 (1981) · Zbl 0466.12011
[37] Vasiga, T.; Shallit, J. O., On the iteration of certain quadratic maps over \(GF(p)\), Discrete Math., 277, 219-240 (2004) · Zbl 1045.11086
[38] Zubkov, A. M.; Tarakanov, V. E., Cycle structure of power mappings in a residue classes ring, Discrete Math. Appl., 23, 273-298 (2013) · Zbl 1398.94089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.