MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

By Newton interpolation (or other standard methods), one can easily determine the number and structure (the latter to a lesser extent) of sequences $(a_1,a_2,\ldots,a_n)\pmod{n}$ represented by integer polynomials given the prime factorization of $n$ (note that we can reduce to the prime power case by the Chinese remainder theorem). For instance, see this AoPS thread. However, for such $f\in\mathbb{Z}[x]$ we have strong restrictions like $u-v\mid f(u)-f(v)$ for integers $u,v$.

IMO it's then natural to wonder about (e.g. the new structure of valid $f$) for rational polynomials in general, where standard interpolation methods (in certain mods) aren't as clean. (Mostly copied from my comment below.)

To this end, consider a pair of positive integers $(n,m)$ with $n,m>1$ such that for every sequence $(a_1,a_2,\ldots,a_n)\in(\mathbb{Z}/m\mathbb{Z})^n$, there exists an integer-valued polynomial $f\in\mathbb{Q}[x]$ satisifying $f(x)\equiv a_i\pmod{m}$ whenever $x\equiv i\pmod{n}$.

First, it is easy to show that $n,m$ must be powers of the same prime. Indeed, if there exist distinct primes $p,q$ such that $p\mid n$ and $q\mid m$, then for some sufficiently large integer $\ell$, we have $q\mid f(x+n)-f(x)$ and $q\mid f(x+q^\ell)-f(x)$ for every $x$. But $\gcd(n,q^\ell)\mid n/p$, so by Bézout's identity, $q\mid f(x+n/p)-f(x)$ for all $x$ and thus the $a_{i(n/p)}$ must all be congruent $\pmod{q}$ in order for $f$ to exist.

On the other hand, if $n=p^i$ and $m=p^j$ for some prime $p$ and positive integers $i,j$, then given a sequence $(a_1,a_2,\ldots,a_n)$, consider the polynomial $g(x)=\sum_{k=1}^{n}a_kx^k$. By a simple induction on $d\ge0$, we can show (using finite differences) that a degree $d$ polynomial $f$ (for convenience, say $\deg{0}=-1$) satisfying the desired properties exists iff $d$ is the smallest number such that the division of $(x-1)^{d+1}g(x)$ by $x^n-1$ gives a remainder $r(x)$ with coefficients all divisible by $m$ (call $d+1$ the order of the sequence $(a_1,a_2,\ldots,a_n)$, so the all-zero sequence has order $0$). Since $(x-1)^n=x^n-1$ in $F_p$, we have $(x-1)^{jn}=(x^n-1)u(x)+p^j v(x)$ for some polynomials $u,v$ with integer coefficients, so the order of any sequence is finite and at most $jn$.

However, this leads to the following two questions:

  1. For fixed $p,i,j$, what is the maximum possible order $M$ of a sequence $(a_1,a_2,\ldots,a_n)\in(\mathbb{Z}/m\mathbb{Z})^n$? (Resolved in the update.)
  2. How many sequences are there of order $r$, where $r\in[0,M]$ is a fixed integer?
  3. Is there a reasonably nice way to describe the sequences of a fixed order $r$ (possibly in terms of one of the corresponding polynomials $f,g$)?

Looking at small cases, it seems that the answer to 1 should be $p^i+(j-1)\phi(p^i)$, where $\phi$ denotes Euler's totient function.

Update: OK, I think I have a (messy) proof that the answer to question 1 is indeed $p^i+(j-1)\phi(p^i)$, but it doesn't seem to lend itself to 2 or 3 in any way.

Fix $p,i$. First note that since $(x-1)^{p^k}=x^{p^k}-1$ (in $F_p$) for $k=i$ and $k=i-1$, we have $(x-1)^{\phi(p^i)} = \Phi_{p^i}(x)$ in $F_p$ as well, so $(x-1)^{\phi(p^i)}=\Phi_{p^i}(x)+p T(x)$ for some integer polynomial $T$ of degree at most $\phi(p^i)-1$, where $\Phi_t$ denotes the $t^{th}$ cyclotomic polynomial. Observe that $T(1)=-1$, so $1$ is not a root of $T$ in $F_p$.

Using this key fact, we will induct on $j\ge1$ to construct a sequence of integer polynomials $P_j,Q_j$ such that $$(x-1)^{p^i+(j-1)\phi(p^i)} = (x^{p^i}-1)P_j(x)+p^j(x-1)Q_j(x),$$ $v_p(Q_j(1))=i-1$, and in $F_p$, $(x-1)^{p^{i-1}-1}\| Q_j(x)$ (i.e. $1$ is a root of multiplicity $p^{i-1}-1$).

For $j=1$, we simply take $P_1(x)=1$ and $Q_1(x) = \frac{(x-1)^{p^i}-(x^{p^i}-1)}{p(x-1)}$, where clearly $Q_1(1)=-p^{i-1}\implies v_p(Q_1(1))=i-1$. Showing $(x-1)^{p^{i-1}-1}\| Q_j(x)$ is slightly harder, but not too bad. It's easy to show by counting prime factors that $\binom{p^i}{k}$ is divisible by $p$ for all $1\le k\le p^i-1$ and not divisible by $p^2$ iff $p^{i-1}\mid k$. Furthermore, by Babbage's theorem we have $\binom{p^i}{kp^{i-1}}\equiv\binom{p}{k}\pmod{p^2}$ for $1\le k\le p-1$. Hence for $p=2$, we just need to show that $(x-1)^{p^{i-1}}\| x^{p^{i-1}}-1$ in $F_2$, which is obvious; for $p>2$ odd, we need to show $$(x-1)^{p^{i-1}} \| \sum_{k=1}^{p-1}\frac{x^{kp^{i-1}}}{k} = \left(\sum_{k=1}^{p-1}\frac{x^k}{k}\right)^{p^{i-1}}$$ in $F_p$ (note that $k^p=k$ by Fermat's little theorem). But if $h(x)=\sum_{k=1}^{p-1}\frac{x^k}{k}$, then $h(1)\equiv0\pmod{p}$ while $h'(1)\equiv p-1\pmod{p}$, so $1$ is a simple root of $h$ and we're done with the base case.

Now assuming the result for some $j\ge1$ (so that $\frac{x^{p^{i-1}}-1}{x-1}\mid Q_j(x)$ in $F_p$), we can write $Q_j(x)=\frac{x^{p^{i-1}}-1}{x-1}R(x)+pS(x)$ for two integer polynomials $R,S$ with $\deg{S} < p^{i-1}-1$. (+) Then $$(x-1)^{p^i+j\phi(p^i)} = (x-1)^{p^i+(j-1)\phi(p^i)} (x-1)^{\phi(p^i)}$$ can be written as $$(x^{p^i}-1)P_j(x)(x-1)^{\phi(p^i)}+p^{j+1}(x-1)T(x)Q_j(x)+p^j\Phi_{p^i}(x)(x-1)Q_j(x)$$ or equivalently after substitution, $$(x^{p^i}-1)(P_j(x)(x-1)^{\phi(p^i)}+p^j R(x))+p^{j+1}(S(x)\Phi_{p^i}(x)+T(x)Q_j(x)),$$ so we can take $$P_{j+1}(x) = P_j(x)(x-1)^{\phi(p^i)}+p^j R(x)$$ and $$Q_{j+1}(x) = S(x)\Phi_{p^i}(x)+T(x)Q_j(x).$$ As $$(x-1)^{p^{i-1}}\mid (x-1)^{\phi(p^i)}=\Phi_{p^i}(x)$$ in $F_p$ and $T(1)=-1$, we see that $(x-1)^{p^{i-1}-1}\| Q_{j+1}(x)$.

It remains to show that $v_p(Q_{j+1}(1))=i-1$. By (+) and the definition of $Q_{j+1}$, we find $Q_{j+1}(1)=\Phi_{p^i}(1)S(1)+T(1)Q_j(1)=pS(1)-Q_j(1)=-p^{i-1}R(1)$, so $v_p(Q_{j+1}(1))\ge i-1$. However, if $p^i\mid Q_{j+1}(1)$, then $p\mid R(1)$, so writing (+) in $F_p$ we have $Q_j(x) = (x-1)^{p^{i-1}-1}R(x)$. But then $(x-1)^{p^{i-1}}\mid Q_j(x)$, contradicting our inductive hypothesis.

Thus our induction is complete.

Clearly this construction shows that the order of any sequence is at most $M=p^i+(j-1)\phi(p^i)$. On the other hand, it is easy to show that the order of $(1,0,\ldots,0)$ is $M$. Indeed, note that $g(x)=x$ for this sequence, and suppose $x(x-1)^{M-1}/(x^{p^i}-1)$ leaves a remainder with coefficients all divisible by $p^j$. From the induction statement, we have $$(x-1)^{M-1} = \frac{x^{p^i}-1}{x-1}P_j(x)+p^jQ_j(x),$$ so writing $P_j(x)=(x-1)U(x)+V$ for an integer $V$, we get $p^j\mid V$. But then plugging in $1$ to this equation, $0=(0)U(1)+(p^i)V+p^j Q_j(1)$, whence $p^i\mid Q_j(1)$, contradiction.

share|cite|improve this question
    
I'm curious what's the motivation for this question? – tweetie-bird Jul 15 '12 at 15:33
    
By Newton interpolation, one can easily determine the number and structure (the latter to a lesser extent) of sequences $(a_1,a_2,\ldots,a_n)\pmod{n}$ represented by integer polynomials nicely given the prime factorization of $n$ (esp. for prime powers). However, for such $f$ we have restrictions like $u-v\mid f(u)-f(v)$ for integers $u,v$. IMO it's then natural to wonder about (e.g. the new structure of valid $f$) for rational polynomials in general. Standard interpolation methods aren't as clean, and I don't see a clear connection between sequences and their polynomial representations. – Victor Wang Jul 15 '12 at 16:47
    
Thanks! That makes sense! – tweetie-bird Jul 15 '12 at 20:37
1  
@Victor: just a word of warning (since you mention being new), if you edit your post 8 times then it becomes community wiki. In that case, people who answer your question don't get reputation points for answering. I'm afraid I probably can't help you with answering your question, but just thought I'd let you know how this works. – tweetie-bird Jul 16 '12 at 0:11
    
Oh, I didn't know that. Thanks! – Victor Wang Jul 16 '12 at 0:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.