0
$\begingroup$

Denote complexity $C(n)$ to be minimum degree of the polynomial in $\Bbb Z[x]$ that maps even integers from $0$ to $2^n-1$ with even $2$-adic valuation to $>2^{n-1}$ integers and odd $2$-adic valuation to $\leq 2^{n-1}$ integers (with $0$ having odd $2$-adic valuation by convention).

Can this be done and if so is there any tool to understand how fast does $C(n)$ grows?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I'm not sure of the meaning of "to $>2^{n-1}$ integers". Should it be understood as "to integers that are $>2^{n-1}$"? Also, out of curiosity, why call this function "complexity"? Do you have an "obvious" upper bound? $\endgroup$
    – YCor
    Commented Dec 26, 2017 at 1:49

1 Answer 1

Reset to default
4
$\begingroup$

Let $k_1,\dotsc,k_r$ be the even integers with even $2$-adic valuation in the range you want. For any polynomial $p$ meeting your condition, $p(x)-2^{n-1}$ has a root between $k_i-2$ and $k_i$, and a root between $k_i$ and $k_i+2$. So $p$ has degree at least $2r$. On the other hand your condition is met by $$ p(x) = 2^{n-1} - \prod (k_i-1-x)(k_i+1-x) $$ which has that same degree.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Turbo Would you be willing to accept this answer? $\endgroup$
    – Zach Teitler
    Commented Aug 21, 2019 at 15:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .