Estimating the number of roots of trinomials over finite fields

详细信息    查看全文

• 作者：Zander Kelley¹ ; ^{zander_k@tamu.edu" class="auth_mail" title="E-mail the corresponding author} ; Sean W. Owen¹
• 关键词：Finite field ; Sparse polynomial ; Trinomial ; Poisson distribution ; Chebotarev density
• 刊名：Journal of Symbolic Computation
• 出版年：2017
• 出版时间：March-April 2017
• 年：2017
• 卷：79
• 期：part_P1
• 页码：108-118
• 全文大小：488 K

文摘

We show that univariate trinomials hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si1.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=c8a647fda00722e0a713ccb2135dfa40" title="Click to view the MathML source">xⁿ+ax^s+b∈F_q[x]hContainer hidden">hCode">h altimg="si1.gif" overflow="scroll">w>xw>w>nw>+aw>xw>w>sw>+b∈w>hvariant="double-struck">Fw>w>qw>hy="false">[xhy="false">]h> can have at most hmlsrc">w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si2.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=123851bdcb7adab2ddac3ec01e463fac">height="30" width="84" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0747717116300876-si2.gif">hContainer hidden">hCode">h altimg="si2.gif" overflow="scroll">δhy="true" maxsize="3.8ex" minsize="3.8ex">⌊w>1w>2+w>q−1w>δhy="true" maxsize="3.8ex" minsize="3.8ex">⌋h> distinct roots in hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si17.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=093fb036c4a1c93572d56ed2613b59d4" title="Click to view the MathML source">F_qhContainer hidden">hCode">h altimg="si17.gif" overflow="scroll">w>hvariant="double-struck">Fw>w>qw>h>, where hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si4.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=832f517b99766a04ff068f8ac8c8b651" title="Click to view the MathML source">δ=gcd⁡(n,s,q−1)hContainer hidden">hCode">h altimg="si4.gif" overflow="scroll">δ=hvariant="normal">gcd⁡hy="false">(n,s,q−1hy="false">)h>. We also derive explicit trinomials having hmlsrc">w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si5.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=e2997cf0b577637472ec9142eb3a2130">height="15" width="22" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0747717116300876-si5.gif">hContainer hidden">hCode">h altimg="si5.gif" overflow="scroll">qh> roots in hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si17.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=093fb036c4a1c93572d56ed2613b59d4" title="Click to view the MathML source">F_qhContainer hidden">hCode">h altimg="si17.gif" overflow="scroll">w>hvariant="double-struck">Fw>w>qw>h> when q   is square and hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si6.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=d21d80729b3e4cdb7b638c4a188d3371" title="Click to view the MathML source">δ=1hContainer hidden">hCode">h altimg="si6.gif" overflow="scroll">δ=1h>, thus showing that our bound is tight for an infinite family of finite fields and trinomials. Furthermore, we present the results of a large-scale computation which suggest that an hmlsrc">hImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0747717116300876&_mathId=si7.gif&_user=111111111&_pii=S0747717116300876&_rdoc=1&_issn=07477171&md5=76a84985418a8429e9b111a78d62b3c4" title="Click to view the MathML source">O(δlog⁡q)hContainer hidden">hCode">h altimg="si7.gif" overflow="scroll">Ohy="false">(δhvariant="normal">log⁡qhy="false">)h> upper bound may be possible for the special case where q is prime. Finally, we give a conjecture (along with some accompanying computational and theoretical support) that, if true, would imply such a bound.