The latest problem from fakalin. Took some wrong turns and hints to solve it…<\/p>\n
Given a polynomial \\(f: \\mathbb{Z}\\to \\mathbb{Z}\\) with positive integer coefficients, how many evaluations of \\(f\\) does it take to obtain the polynomial?<\/p>\n
(An \\(f: \\mathbb{R}\\to \\mathbb{R}\\) polynomial with real coefficients would take the number of degrees plus 1 to specify, which, if it held in this case, would render the answer unbounded. But the correct answer in this case is surprisingly small.)
\n
\nIt takes only 2 evaluations. Suppose in the following that \\(b>0\\). Let us note that a polynomial \\(f(b) = a_n b^n + … + a_0 b^0\\) specifies essentially a base \\(b\\) representation of the number \\(f(b)\\), in that \\(a_n a_{n-1} … a_0\\) is an expansion of \\(f(b)\\) in base \\(b\\). The only problem is this expansion is non-unique, as it is possible for any \\(a_j \\ge b\\).<\/p>\n
However, it is not possible for any \\(a_j \\ge f(b) + 1\\), since for all \\(j\\), \\(f(b) \\ge a_j\\) by the problem statement and assumption on \\(b\\). Then take \\(B = f(b) + 1\\). Now we are guaranteed that \\(a_n a_{n-1} … a_0\\) is the unique (and canonical) base \\(B\\) expansion of \\(f(B)\\), from which the polynomial coefficients immediately obtain.<\/p>\n
So the two evaluations are at \\(f(b)\\) and \\(f(B=f(b)+1)\\).<\/p>\n
Example: \\(f(b) = 3b^2 + 2b + 1\\). Evaluate at, e.g., \\(b=1\\) to get \\(f(1) = 6\\). Then evaluate at \\(B=f(1)+1=7\\) to get \\(f(7)=162=321_{7}\\).<\/p>\n","protected":false},"excerpt":{"rendered":"
The latest problem from fakalin. Took some wrong turns and hints to solve it… Given a polynomial with positive integer coefficients, how many evaluations of does it take to obtain the polynomial? (An polynomial with real coefficients would take the number of degrees plus 1 to specify, which, if it held in this case, would […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[11,8,9,4,5,10,12,6,3,7],"class_list":["post-291","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-answer","tag-expansion","tag-integer","tag-integer-coefficients","tag-math-math","tag-mathbb","tag-number","tag-number-math","tag-polynomial-coefficients","tag-positive-integer"],"_links":{"self":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts\/291","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=291"}],"version-history":[{"count":0,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=\/wp\/v2\/posts\/291\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=291"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=291"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.yhuang.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=291"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}