Functional graphs of polynomials over finite fields

详细信息    查看全文

• 作者：Sergei V. Konyagin^a ; ^{konyagin@mi.ras.ru" class="auth_mail" title="E-mail the corresponding author} ; Florian Luca^b ; ^{florian.luca@wits.ac.za" class="auth_mail" title="E-mail the corresponding author} ; Bernard Mans^c ; ^{bernard.mans@mq.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Luke Mathieson^c ; ^{luke.mathieson@mq.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Min Sha^d ; ^{shamin2010@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Igor E. Shparlinski^d ; ^{igor.shparlinski@unsw.edu.au" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Polynomial maps ; Functional graphs ; Finite fields ; Character sums ; Algorithms on trees
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：116
• 期：Complete
• 页码：87-122
• 全文大小：621 K

文摘

Given a function f   in a finite field class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615000878&_mathId=si1.gif&_user=111111111&_pii=S0095895615000878&_rdoc=1&_issn=00958956&md5=ec09241261e098bfb59c5d489b6eda29" title="Click to view the MathML source">F_qclass="mathContainer hidden">class="mathCode">${\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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615000878&_mathId=si1.gif&_user=111111111&_pii=S0095895615000878&_rdoc=1&_issn=00958956&md5=ec09241261e098bfb59c5d489b6eda29" title="Click to view the MathML source">F_qclass="mathContainer hidden">class="mathCode">${\mathbb{F}}_q$ where there is an edge from u to v   if and only if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615000878&_mathId=si2.gif&_user=111111111&_pii=S0095895615000878&_rdoc=1&_issn=00958956&md5=c03d1d148c087d3e11ffde371a7cd70c" title="Click to view the MathML source">f(u)=vclass="mathContainer hidden">class="mathCode">$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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615000878&_mathId=si1.gif&_user=111111111&_pii=S0095895615000878&_rdoc=1&_issn=00958956&md5=ec09241261e098bfb59c5d489b6eda29" title="Click to view the MathML source">F_qclass="mathContainer hidden">class="mathCode">${\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.