Let $ n$ be a positive integer. Given an integer coefficient polynomial $ f(x)$, define its signature modulo $ n$ to be the (ordered) sequence $ f(1), \ldots , f(n)$ modulo $ n$. Of the $ n^n$ such $ n$-term sequences of integers modulo $ n$, how many are the signature of some polynomial $ f(x)$ if a) $ n$ is a positive integer not divisible by the square of a prime. b) $ n$ is a positive integer not divisible by the cube of a prime.
Problem
Source: USA TST 2008, Day 3, Problem 9
Tags: algebra, polynomial, geometry, 3D geometry, modular arithmetic, algorithm, function
rchlch
28.01.2009 16:17
Here is my idea, and I also get a solution. However my compution is poor so I possibly make it wrong. I think there are 2 keys to queation a). We denote by $ d(n)$ the desired answer, and: 1. If $ m$ and $ n$ are coprime then $ d(mn)=d(m)d(n)$. 2. If for $ x=0,1, \ldots, p-1$, $ f(x) \equiv 0 \pmod p$ then there exists $ g(x)$ and $ r(x)$ with $ \deg r <p$ satisfying $ f(x)=(x^p-x)g(x)+pr(x)$. And my answer to question a) is, if $ n=p_1p_2 \ldots p_t$ then there are $ p_1^{p_1} \ldots p_t^{p_t}$ $ n-$term sequences. Similarly there is 2 keys to question b), saying 1. If $ m$ and $ n$ are coprime then $ d(mn)=d(m)d(n)$. 2. If for $ x=0,1, \ldots, p^2-1$, $ f(x) \equiv 0 \pmod {p^2}$ then there exists $ g(x)$ and $ r_1(x),r_2(x)$ with $ \deg r_1 <p, \deg r_2 <p$ satisfying $ f(x)=(x^p-x)^2g(x)+p(x^p-x)r_1(x)+p^2r_2(x)$. My answer to question b) is, if $ n=p_1p_2 \ldots p_t q_1^2 \ldots q_l^2$ then there are $ p_1^{p_1} \ldots p_t^{p_t} q_1^{3q_1} \ldots q_l^{3q_l}$ $ n-$term sequences.
The QuattoMaster 6000
13.02.2009 02:51
That is the right answer. Here is a proof:
Lemma 1: There is a polynomial for all signatures in $ \bmod p$ for any prime $ p$ (so there are $ p^p$ possible signatures in $ \bmod p$).
Proof: Assume that there is not exactly one polynomial for every signature. First, reduce all of the polynomials down to degree $ p-1$ (notice that $ p|\frac{(x+p-1)!}{(x-1)!}$ for all $ x$, so we can use this to reduce the degree of the polynomial) and all of the coefficients to be between $ 0$ and $ p-1$ inclusive. Now, let us assume that $ f(x) \equiv g(x)\bmod p$ for $ x = 0, 1, 2, \cdots , p-1$. This implies that for all $ x$, $ f(x) - g(x) \equiv 0 \bmod p$. Let $ f(x) - g(x) \equiv h(x)\bmod p$. Then, $ h(x)\equiv 0\bmod p$ where $ h(x)$ is a polynomial of degree $ p-1$, so $ h(x)$ has roots $ 1, 2, 3, \cdots , p$ in $ \mathbb {Z} p$. Thus, $ h(x)$ has $ p$ roots in $ \mathbb {Z}p$, but only a degree of $ p-1$. This is a contradiction by Lagrange's Theorem, so there is exactly one polynomial for each signature and there are $ p^p$ polynomials (in $ \bmod p$), so $ p^p$ signatures.
Lemma 2: If we have a polynomial $ f(x)$ in $ \bmod m$ and a polynomial $ g(x)$ in $ \bmod n$, where $ m$ and $ n$ are coprime, then we can find an $ h(x)\bmod mn$ so that $ h(x)\equiv f(x)\bmod m$ and $ h(x)\equiv g(x)\bmod n$.
Proof: Let $ z$ and $ y$ be integers so that $ mz\equiv 1\bmod n$ and $ ny\equiv 1\bmod m$ (by the coprime condition, this is possible). Now, let $ h(x) \equiv mzg(x) + nyf(x)\bmod mn$, so $ h(x)\equiv f(x)\bmod m$ and $ h(x)\equiv g(x)\bmod n$.
Lemma 3: $ f(x + p) - f(x) \equiv pf'(x)\bmod p^2$.
Proof: Let $ f(x) \equiv \sum_{i = 0}^k {a_kx^k}\bmod p^2$. This gives that \[ f(x+p) - f(x) \equiv \sum_{i=0}^k {a_k[(x+p)^k - x^p]} \equiv\] \[ \sum_{i=0}^k {a_k[pkx^{k-1} + p^2x^{k-2}\binom {k}{2} + \cdots ]} \equiv p\sum_{i=0}^k {ka_kx^{k-1}\bmod p\equiv pf'(x)\bmod p^2}\]
Lemma 4: We can find a polynomial, $ f(x)$ which is congruent to $ 0\bmod p^2$ for $ p = 0, 1, 2, \cdots, p-1$, and having $ f(p+i)\equiv pa_i\bmod p^2$, where $ 0\le i\le p-1$,for any $ \{ a_0, a_1, \cdots, a_{p-1} \}$.
Proof: Let \[ f(x) \equiv g(x)[(x)(x-1)(x-2)\cdots (x-p+1)]\bmod p^2\] where $ g(x)$ is a polynomial of our choosing. Clearly, $ f(x)\equiv 0\bmod p$ for $ x= 0, 1, 2, \cdots, p-1$. Now, notice that \[ f(p+j)\equiv g(p+j)[(p+j)(p+j-1)\cdots (p+1)(p)(p-1)\cdots (j+1)] \bmod p^2\] Now, it suffices to have $ f(p+j)\equiv a_jp\bmod p^2$ for any $ j$ and $ a_j$. Thus, we want for \[ [(p+j)(p+j-1)\cdots (p+2)(p+1)(p-1)(p-2)\cdots (j+1)]g(p+j)\equiv a_j\bmod p\] Let \[ (p+j)(p+j-1)\cdots (p+2)(p+1)(p-1)(p-2)\cdots (j+1)\equiv k\bmod p\] Notice that since $ 0\le j\le p-1$, we have that $ k$ is not a multiple of $ p$. This means that $ k$ and $ p$ are relatively prime, so $ k$ has an inverse $ \bmod p$. Let this inverse be $ i_j$. Thus, $ g(j)\equiv i_ja_j\bmod p$. Let $ i_ja_j\equiv b_j\bmod p$. It suffices to have $ g(j)\equiv b_j\bmod p$, where $ b_j$ is anything $ \bmod p$ and $ j$ ranges from $ 0$ to $ p-1$. However, by Lemma 1, this is true, and so Lemma 4 is proven.
Lemma 5: For any sequence of $ p$ numbers, $ a_0, a_1, \cdots a_{p-1}$, we can find a polynomial, $ f(x)$ that has its signature starting with $ a_0, a_1, \cdots , a_{p-1}\bmod p^2$.
Proof: By Lemma 1, we can find a polynomial congruent to $ a_0, a_1, a_2, \cdots , a_{p-1}\bmod p$, say $ g(x)$. Now, let $ g(i)\equiv b_i\bmod p^2$. Then, notice that $ a_i\equiv b_i\bmod p$, so now consider a polynomial $ h(x)$ so that $ h(i)\equiv \frac{a_i-b_i}{p}\bmod p$ (this is possible by Lemma 1 again). Now, let $ f(x) = ph(x) + g(x)$, which satisfies the conditions.
Lemma 6: There are $ p^{3p}$ signatures in $ \bmod p^2$.
Proof: By Lemma 3, we have that \[ f(x+ip) \equiv f(x+(i-1)p) + pf'(x+(i-1)p)\equiv f(x+(i-1)p) + pf'(x)\bmod p^2\] Therefore, if we fix $ f(x)\bmod p^2$ for $ x=0,1,2,\cdots, 2p-1$, $ f(x)\bmod p^2$ is fixed for all of the other values of $ x$. Since there are $ p^2$ possibilities for the first $ p$ values of $ p$ and then $ p$ values for the next $ p$ values of $ p$ (recall that $ f(p+i)\equiv f(i)+k_ip\bmod p^2$ for some $ k_i$), we have that there is a maximum of $ p^{2p+p}=p^{3p}$ solutions. We now need to show that all of them are attainable. Let us consider a sequence, $ s$, starting with $ a_0, a_1, \cdots , a_{2p - 1}$. By Lemma 5, we can find a polynomial, $ g(x)$, starting with $ a_0, a_1, \cdots, a_{p - 1}$ and then having $ b_p, b_{p+1}, \cdots b_{2p-1}$. By Lemma 4, we can find a polynomial, $ h(x)$, starting with $ 0, 0, 0, \cdots 0, a_p-b_p, a_{p+1}-b_{p+1}, \cdots , a_{2p-1}-b_{2p-1}$ with $ p$ zeroes (this is possible since $ a_{p+i}\equiv a_i\equiv b_i\equiv b_{i+p}\bmod p$). Then, we simply consider $ f(x) = g(x) + h(x)$ as the desired polynomial.
The Problem: For a), let $ n = p_1p_2\cdots p_k$. Notice that $ f(x)\equiv f(p_i+x)\bmod p$. Letting $ y_p$ be the residue of $ y\bmod p$, we have that $ f(y)\equiv f(y_{p_i})\bmod p_i$ for all $ i$. Thus, when the first $ f(x)_{p_i}$ are fixed for $ x=0,1,2,\cdots , p-1$, $ f(x)_{p_i}$ is fixed for $ p\le x \le n-1$. This means that fixing $ f(x)_{p_i}$ for all $ i$ fixes a system of congruencies for $ f(x)\bmod p_i$ for all $ i$, so $ f(x)\equiv f(x)_{p_i}\bmod p_i$ for all $ i$. By Lemma 2 (applied repeatedly), there is a solution to this system of congruencies. It suffices to find the number of signatures for $ f(x)$ in $ \bmod p_i$ for all $ i$. However, this is just $ \prod_{i=1}^k {p_i^{p_i}}$, which is the answer to a).
For b), let $ n = p_1p_2\cdots p_kq_1^2q_2^2\cdots q_l^2$. By similar reasoning as we used in a), the answer will be $ \prod_{i=1}^k {p_i^{p_i}}\prod_{i=1}^l {q_i^{3q_i}}$.
OldMath
17.09.2010 22:07
I think the general case can be solved in this way: As mentioned in other proofs we should solve it for $n=p^{k}$. lemma :let $k$ be a natural number,$p$ a prime and $f(x) \in \mathbb{Z}[x]$. then for all $x\in \mathbb{Z}$ we have$ f (x) \equiv 0 \bmod p^{k}$ $(*)$ iff $f(x)$ is in the form ${{{s_{p}(x)}^{k}g_{k}(x)+p^{1}s_{p}(x)}^{k-1}g_{k-1}(x)+...+p^{k-1}s_{p}(x)}^{1}g_{1}(x)+p^{k}g_{0}(x)$ with $\deg (g_{i})<p$ for $i<k$ and $s_{p}(x)=x(x-1)...(x-(p-1))$ Lemma can be proved by induction. By lemma it is easy to see that if we work in $\mathbb{Z} _{p^{k}}$ number of $f$ with property $(*)$ and degree less than $pk$ will be $(p^{k-1})^{p}.(p^{k-2})^{p}...(p^{0})^{p}=p^{\frac{k(k-1)}{2}p}$ $(**)$ Now the main question:we will work in $\mathbb{Z} _{p^{k}}$. By euclidean algorithm for any $f$ we have $f(x)=(s_{p}(x))^{k}g(x)+r(x),\deg (r)<kp$ and obviously for any $x$ we have $(s_{p}(x))^{k} \equiv 0 \bmod p^{k}$.so we only work on $f$ with $deg(f)<kp$.these $f$ form a group $|G|$ under addition.and the map $\phi :G \rightarrow {(\mathbb{Z} _{p^{k}})}^{p^{k}},\phi (f)=(f(1),f(2),...,f(p^{k}))$ is a homeomorphism.we have $|G|=p^{k^{2}p}$ and by $(**)$ $|ker( \phi )|=p^{\frac{k(k-1)}{2}p}$.so we have $|\phi (G)|=\frac{|G|}{|ker(\phi)|}=p^{\frac{k(k+1)}{2}p}$ and so the answer for $n=p^{k}$ is $p^{\frac{k(k+1)}{2}p}$
math154
21.07.2011 23:47
Another way to show that there are $p^{3p}$ signatures modulo $p^2$ is to write the (eventually terminating) Newton interpolation polynomial \[f(x)=\sum_{k\ge0}\Delta^k[f](0)\binom{x}{k}=\sum_{k\ge0}a_k\binom{x}{k}.\]Clearly $(a_0,a_1,\ldots,a_{p^2-1})\pmod{p^2}\longleftrightarrow(f(0),f(1),\ldots,f(p^2-1))\pmod{p^2}$. Note that $f\in\mathbb{Z}[x]$ if and only if $k!\mid a_k$ for all $k\ge0$ (just consider the $[x^k]$ coefficients in reverse order). Analyzing $v_p(k!)$ for $k\ge0$, we see that for $k\ge 2p$, we have 1 choice for $a_k\pmod{p^2}$, for $p\le k\le 2p-1$, we have $p$ choices, and for $0\le k\le p-1$, we have $p^2$ choices. This gives us a total of $(p^2)^p p^p=p^{3p}$ working sequences, as desired. (It is easy to check such choices of $a_k\pmod{p^2}$ lead to a unique "class" of integer polynomials, as anything not divisible by $p$ is invertible modulo $p^2$). Edit (12/19/2013): Note that OldMath's lemma (and thus solution as well) fails for $k\ge p+1$: OldMath wrote: I think the general case can be solved in this way: As mentioned in other proofs we should solve it for $n=p^{k}$. lemma :let $k$ be a natural number,$p$ a prime and $f(x) \in \mathbb{Z}[x]$. then for all $x\in \mathbb{Z}$ we have$ f (x) \equiv 0 \bmod p^{k}$ $(*)$ iff $f(x)$ is in the form ${{{s_{p}(x)}^{k}g_{k}(x)+p^{1}s_{p}(x)}^{k-1}g_{k-1}(x)+...+p^{k-1}s_{p}(x)}^{1}g_{1}(x)+p^{k}g_{0}(x)$ with $\deg (g_{i})<p$ for $i<k$ and $s_{p}(x)=x(x-1)...(x-(p-1))$ Lemma can be proved by induction. The correct version can be deduced from my Newton interpolation method above; we get a total count of $\prod_{t\ge0}p^{\max(0,r-v_p(t!))}$ for the $p^r$ case.
dibyo_99
19.03.2014 22:31
I am going to evaluate the number of such sequences for all positive integers $n$. Some part of my proof is similar to math154's post above. I'll quantify the problem first. Define $\text{sgn}_n(f)= { (\overline{f(1)}, \overline{f(2)}, \cdots \overline{f(n)}) } $. Define $A_n= { \text{sgn}_n(f) | f \in \mathbb{Z}[x] }$. We need to find $|A_n|$ Lemma: $|A_n|$ is a multiplicative function (not completely) of $n$. Proof of Lemma: We shall equivalently establish a bijection between $ A_{mn}$ and $A_m \times A_n$, where $m$ and $n$ are coprime integers. Consider the map $X:A_{mn} \to A_m \times A_n$ satisfying \[ X(\text{sgn}_{mn}(f))= (\text{sgn}_m(f),\text{sgn}_n(f)) \]First, we show that the map is well-defined. Suppose that $\text{sgn}_{mn}(f)=\text{sgn}_{mn}(g)$ for some polynomials $f$ and $g$. But then, $mn|f(k)-g(k) \forall k \in [1,mn]$. Therefore, $m|f(k)-g(k) \forall k \in [1,m]$ and $n|f(k)-g(k) \forall k \in [1,n]$, implying $(\text{sgn}_m(f),\text{sgn}_n(f))=(\text{sgn}_m(g),\text{sgn}_n(g))$. Next, we show that $f$ is injective. Suppose that, for polynomials with integer coefficients $f$ and $g$, $(\text{sgn}_m(f),\text{sgn}_n(f))=(\text{sgn}_m(g),\text{sgn}_n(g))$. Since $a-b|P(a)-P(b)$ for any polynomial $P$, therefore, $m|f(k)-g(k) \forall k \in \mathbb{N}$ and $n|f(k)-g(k) \forall k \in \mathbb{N}$. Since $(m,n)=1$, we also have $mn|f(k)-g(k) \forall k \in \mathbb{N}$. Consequently, $\text{sgn}_{mn}(f)=\text{sgn}_{mn}(f)$. Finally, we are left to prove that $X$ is surjective. Since $(m,n)=1$, $\exists a,b \in \mathbb{Z}$ such that $am \equiv 1 \pmod{n}$ and $bn \equiv 1 \pmod{m}$. Define $P(x) = bnf(x)+amg(x)$. Then, $P(i) \equiv f(i) \pmod{m}$ and $P(i) \equiv g(i) \pmod{n} \forall i \in \mathbb{N}$. Therefore, $(\text{sgn}_m(f),\text{sgn}_n(g))=(\text{sgn}_m(P),\text{sgn}_n(P))=X(\text{sgn}_{mn}(P))$. Consequently, $X$ is injective and surjective and therefore, bijective. Now, it suffices to find out $|A_{p^k}|$, for primes $p$. Consider the Mahler expansion of a polynomial $f$. Clearly, the coefficients in the Mahler Expansion $(a_0,a_1, \cdots a_{p^k-1})$ uniquely define the values $(f(0),f(1), \cdots f(p^k-1))$ and vice-versa. Since $f \in \mathbb{Z}[x]$, we must have $m!|a_m \forall k \ge 0$. Considering $v_p(m!)$, in $\mathbb{Z}/p^k\mathbb{Z}$, for $j \le k$, and $(j-1)p \le m < jp$, $a_m$ can take over exactly $p^{k-j+1}$ values. For $m \ge kp$, we have only one choice for $a_m$. By Multiplication Principle, the number of such sequences if $p^{0+p+\cdots (k-1)p+kp}=p^{pk(k+1)/2}$. From here, we infer that if the canonical factorisation of $n$ is $\prod_{i=1}^rp_i^{a_i}$, we obtain \[ |A_n|= \prod_{i=1}^rp_i^{p_ia_i(a_i+1)/2} \]
CyclicISLscelesTrapezoid
30.05.2022 21:54
Edit: the last half of the last paragraph is wrong but I'd imagine there being an easy fix. Here's a relatively short elementary proof that there are $p^{\frac{a(a+1)}{2}p}$ signatures modulo $p^a$. The crux of this solution is the following claim. Claim: For any $k=0,1,\ldots,p-1$, if $(x_1,\ldots,x_{p^a})$ is the signature of $f(x)$, then $(y_1,\ldots,y_{p^a})$ is a signature, where $y_i=x_i$ if $i \equiv k \pmod{p}$, and $y_i=0$ otherwise. Proof: Let $S$ be the set of all $i$ in modulo $p^a$ such that $i \not\equiv k \pmod{p}$. Notice that if each element in $S$ was increased by a multiple of $p$, then $S$ would stay the same. Hence, if $r \equiv s \equiv k \pmod{p}$, then \[\prod_{i \in S} (r-i) \equiv \prod_{i \in S} (s-i) \pmod{p^a}.\]Set \[f_k(x)=\frac{\prod_{i \in S} (x-i)}{\prod_{i \in S} (k-i)} \cdot f(x).\]If $x \not\equiv k \pmod{p}$, then $\tfrac{\prod_{i \in S} (x-i)}{\prod_{i \in S} (k-i)} \equiv 0 \pmod{p^a}$, and if $x \equiv k \pmod{p}$, then we already proved that $\tfrac{\prod_{i \in S} (x-i)}{\prod_{i \in S} (k-i)} \equiv 1 \pmod{p^a}$. Therefore, $f_k(x)$ has signature $(y_1,\ldots,y_{p^a})$. $\square$ By this claim, the number of signatures modulo $p^a$ is the product of the number of possible values of \[(f(0),f(p),\ldots,f(p^a-p)),(f(1),f(p+1),\ldots,f(p^a-p+1)),\ldots,(f(p-1),f(2p-1),\ldots,f(p^a-1)).\]By shifting, it suffices to prove that the number of possible values of $(f(0),f(p),\ldots,f(p^a-p))$ is $p^{\frac{a(a+1)}{2}}$. Notice that we only care about the coefficient of $x$ in modulo $p^{a-1}$, the coefficient of $x^2$ in modulo $p^{a-2}$, etc. We use this to define a basic polynomial as a polynomial of degree at most $a-1$ such that the coefficient of $x^n$ is an element of $\{0,1,\ldots,p^{a-n}-1\}$ for all $n=0,1,\ldots,a-1$. By definition, any polynomial can be reduced to a basic polynomial with the same values of $f(0),f(p),\ldots,f(p^a-p)$. There are $p^a \cdot p^{a-1} \cdots p^1=p^{\frac{a(a+1)}{2}p}$ basic polynomials, so it suffices to prove that they all give distinct values of $(f(0),f(p),\ldots,f(p^a-p))$. Assume FTSOC that there exist two basic polynomials that give the same values. Then, we subtract them and shift the coefficient of $x^n$ of their difference by a multiple of $p^{a-n}$ to get a nonzero basic polynomial $f_0$ such that $f_0(0),f_0(p),\ldots,f_0(p^a-p)=0$. It's well known (proven by setting $f_0(x)=(x-k)q(x)+r$ for root $k$, quotient polynomial $q$, and remainder $r$) that $f_0$ must be divisible by $x(x-p) \cdots (x-(p^a-p))$. Suppose $f_0(x) \equiv q(x)x(x-p) \cdots (x-(p^a-p)) \pmod{p^a}$ for some nonzero polynomial $q(x)$ of degree $d$ with coefficients in $\{0,1,\ldots,p^a-1\}$. Then, the expansion of $f_0(x)$ must have a term with nonzero coefficient and degree $p^{a-1}+d$, contradicting the fact that $f_0$ is a basic polynomial (since basic polynomials have degree at most $a-1$ by definition). $\square$