8
$\begingroup$

Context: The function $(-1)^n$ alternates between $1,-1$ because $n$ alternates between odd and even, I was trying to find a function $f(n)$ that will give $m$ positives then $m$ negatives and so on i.e the sequence $(-1)^{f(n)}$ will be $+1, +1, \dots(m \text{ times}), +1, -1,-1\dots(m \text{ times}),-1,\dots $ and I did find $\lfloor \frac{n-1}{m}\rfloor$ but I wonder what if we only allow $f$ to be a polynomial? Can we find such a polynomial for all $m$?

Let $f_m(x)$ be polynomial where $f_m(x)$ is odd for the first $m$ natural numbers and $f_m(x)$ is even for the second $m$ natural numbers and so on.

My question is: How to find $f_m \forall m \in \mathbb{N}$? if $f_m$ exist for $m$ then the solution is not unique but I want any solution

I found that $f_2(x)=\frac{x(x+1)}{2}$ which made me check for Faulhaber's polynomials and all of them are solution for $f_2$ (well it is easy to prove that). I couldn't find a solution for $f_3$ or any higher values of $m$. Maybe it is not possible to find such $f_m$ where $m$ is not in the form of $2^r$ but how to prove it?

$\endgroup$
4
  • 1
    $\begingroup$ I don't know the answer, just mentioning that every integer valued polynomial is an integer linear combination of binomial coefficients. The even/odd-ness of binomial coefficients is also well understood: math.stackexchange.com/q/11002/42969 $\endgroup$
    – Martin R
    Commented Jun 15 at 19:27
  • 1
    $\begingroup$ $\binom {x-2^m}{2^m}$ works for $f_{2^m}$. $\endgroup$
    – anankElpis
    Commented Jun 15 at 19:51
  • $\begingroup$ Since $x(1+x)$ is always even, then the oddity of a polynomial with integer coefficients $p(x)$ is the same of its residual of the division by $x(1+x)$. This means that it exists a linear polinomial with that pattern of oddity, that is impossible unless $m=1$ $\endgroup$
    – Exodd
    Commented Jun 15 at 20:38
  • 1
    $\begingroup$ I got $$ f_m(x)=\frac{2x-m-1}{2m}+\frac{1}{2m} \sum_{k=1}^{m-1} \left(1-i \cot\left(\frac{k}{m}\pi\right)\right)e^{\frac{2\pi (x-1)k i}{m}}$$ So you need to find polynomial for $\exp(x i)$ function $\endgroup$
    – Faoler
    Commented Jun 15 at 21:02

1 Answer 1

Reset to default
3
$\begingroup$

As @Martin R mentions in the comments, any integer valued polynomial can be written as an integer linear combination of binomial coefficients. By Lucas's Theorem, the parity of $\binom xn$ is cyclic, and a (not necessarily minimal) period is the smallest power of $2$ larger than $n$. Thus any linear combination of those terms also behaves cyclicly with period a power of $2$. But the $f_m$ you are looking for has a period of $2m$. Therefore, a solution can only exist if $2m$, and hence $m$, is a power of $2$.

If $m=2^n$, then consider $f(x)=\binom{x+m-1}m$. Again by Lucas's Theorem, $f(x)$ is odd if and only if the binary expansion of $x+2^n-1$ has a $1$ at the $n$-th position. Writing $x=k\cdot 2^{n+1}+r$ with $0\leq r<2^{n+1}$, this happens exactly when $1\leq r\leq 2^n$. Therefore $f$ satisfies the requirement for $m=2^n$.

$\endgroup$
2
  • $\begingroup$ I don't understand why "Therefore, a solution can only exist if 2m , and hence m , is a power of 2 ." $\endgroup$
    – pie
    Commented Jun 16 at 11:51
  • 1
    $\begingroup$ $f_m \bmod 2$ has period $2m$ by requirement, but also period $2^r$ for some $r\geq1$ by the argument in my first paragraph. Thus $2m=2^r\ \Rightarrow\ m=2^{r-1}$. $\endgroup$
    – anankElpis
    Commented Jun 16 at 17:18

You must log in to answer this question.

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