For a polynomial $ P(x)$ with integer coefficients, $ r(2i - 1)$ (for $ i = 1,2,3,\ldots,512$) is the remainder obtained when $ P(2i - 1)$ is divided by $ 1024$. The sequence \[ (r(1),r(3),\ldots,r(1023)) \] is called the remainder sequence of $ P(x)$. A remainder sequence is called complete if it is a permutation of $ (1,3,5,\ldots,1023)$. Prove that there are no more than $ 2^{35}$ different complete remainder sequences.
Problem
Source: USA Team Selection Test 2007
Tags: algebra, polynomial, algorithm, modular arithmetic, counting, distinguishability, induction
Rust
08.12.2007 08:06
I think you are wrong. There are $ 2^{45}$ different complete remainder sequences.
MellowMelon
08.12.2007 13:13
The problem as listed in the book I was given has 35. It's possibly the book I have has a typo... I should note that at least one person (and possibly 2 or 3) got near-perfect scores on this test, so this problem was solved; on the TST itself, the given problem must have been correct. I think the first thing to do is to check your proof again.
Rust
08.12.2007 14:05
Yes, I am wrong. My solution. We can consider $ x_k = 2^k - 1,k = 1,2,3,4$ and consruct $ P(x) = a_0 + a_1(x - x_1) + a_2(x - x_1)(x - x_2) +a_3(x-x_1)(x-x_2)(x-x_3) + P_1(x)(x-x_1)(x-x_2)(x-x_3)(x-x_4)$. For all odd x $ 1024|P_1(x)(x-1)(x-3)(x-7)(x-15).$ If $ P(x)$ give complete remainders, then $ aP(x)+b$ give complete remainders too, if a -odd,b - even. It reduce to case, when $ P(x)=x+(x-1)(x-3)(a_2+a_3(x-7))$. We have $ 2^{18}$ variants to reduce. If $ a_2=a_2'\mod 128, a_3=a_3'\mod 16$, then $ P(x)=x+(x-1)(x-3)(a_2'+a_3'(x-7))\mod 1024$. If $ a_3\not =0$, then $ P(x)=P(2^k-x)$ for some x and some k>1. Therefore we had not completely remainders. For any $ a_2$ (128 variants) $ P(x)=x+a_2(x-1)(x-3)$ had completely remainders. Therefore exactly $ 2^{25}$ different completely remainders sequence.
jacques
16.03.2008 19:21
still, the exponent is 35...so the problem is not solved yet
Fedor Petrov
31.03.2008 17:31
Rust wrote: For all odd x $ 1024|P_1(x)(x - 1)(x - 3)(x - 7)(x - 15).$ Why? Take $ x=5$.
Rust
31.03.2008 17:56
Yes. It is my mistake. For all odd x $ 2^{11}|(x-1)(x-3)(x-5)(x-7)(x-9)(x-11).$ Therefore P(x) equavalent to $ x+(x-1)(x-3)[a_2'+a_3'(x-5)+a_4'(x-5)(x-7)+a_5'(x-5)(x-7)(x-9)].$ $ 0\le a_2'<2^7,0\le a_3'<2^6,0\le a_4<2^3,0\le a_5'<2^1$. Therefore number of complete remainders no more than $ 2^{18}*2^{7+6+3+1}=2^{35}.$ But all variants don't give complete remainders.
jiahan
12.04.2009 12:14
Rust wrote: $ 0\le a_5' < 2^1$. Shouldn't it be $ a_5' < 2^2$?
alkjash
17.04.2010 01:17
Using the division algorithm, we have:
$ P(x) = b_1 + (x-1)(b_3 + (x-3)(b_5+(x-5)(b_7 + \cdots$
$ + (x-1021)(b_{1023} + (x-1023)(R(x)))\cdots)$
For some integers $ b_1, b_3, ... b_{1023}$ and $ R(x)$ a polynomial with integer coefficients. Now, we have the following congruences $ \pmod{1024}$:
$ b_1 \equiv r(1)$
$ 2b_3+b_1 \equiv r(3)$
$ 4\cdot 2 b_5 + 4 b_3 + b_1 \equiv r(5)$
$ \cdots$
$ 2^n n! b_{2n+1} +$ terms with $ b_i$ with $ i < 2n+1$ $ \equiv r(2n+1)$
$ \cdots$
Now, for every occurrence of $ b_{2k+1}$ in the above equations, it occurs as
$ 2^{k} \frac{n!}{(n-k)!} b_{2k+1}$
It is easy to show $ k! | \frac{n!}{(n-k)!}$ (i.e. the binomial coefficients are integers). Therefore, the above expression always has as many powers of 2 as $ 2^k \cdot k!$. On the other hand, for $ k > 5$ this power exceeds $ 1024$, so it makes no contribution to the congruence $ \pmod{1024}$!
Therefore the total number of complete remainder sequences is at most the number of ways to choose $ b_1$ through $ b_{11}$ that give distinct remainder sequences. Since the powers of $ 2$ associated with each of these is $ 0, 1, 3, 4, 7, 8$, respectively (that is, whenever $ b_i$ occurs it has at least that many powers of 2 in its coefficient), $ b_1$ through $ b_{11}$ have $ 2^{10}, 2^{9}, 2^{7},2^6, 2^3,2^2$ different choices respectively that gives distinguishable remainder sequences.
For example, since $ b_5$ always goes with at least $ 2^3$, any $ b_5 ' \equiv b_5 \pmod{2^7}$ will give the same remainder sequence, so there are at most $ 2^7$ distinguishable choices for $ b_5$.
Now, at this point we have at most $ 2^{10+9+7+6+3+2} = 2^{37}$ distinct complete remainder sequences. To show that there are only at most $ 2^{35}$, we need two improvements.
First, $ b_1$ must be odd, since $ a_1$ is odd. There are thus only $ 2^9$ choices for $ b_1$.
Next, note that $ b_3$ is the only other term in any of the sums that is ever multiplied by no more than a factor of 2. So, if $ b_3$ is even, then all $ r(2i+1)$ are congruent to $ b_1$ $ \pmod{4}$, which contradicts completeness. Therefore $ b_3$ is odd and there are only $ 2^8$ choices for $ b_3$.
We have made the desired improvements and are done.
Note: this interpolation method is pretty useful for modular problems. For example, see http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=344711
math154
22.07.2011 00:52
I think we can strengthen this to $2^{32}$.
First note that $P(x+2^5 k)\equiv P(x)+2^5 k P'(x)\pmod{2^{10}}$. If $x$ is an odd integer, then because the numbers $P(x+2^5 k)\pmod{2^{10}}$ are distinct for $1\le k\le 2^5$, $P'(x)$ must be odd (and we only care about its value $\pmod{2^5}$).
Furthermore, suppose we know what $P'(1),P'(3),\ldots,P'(2^5-1)\pmod{2^5}$ are. If we also know $P(1)\pmod{2^{10}}$, then by induction on $1\le j\le5$ we know what $P(1),P(3),\ldots,P(2^j-1)$ are modulo $2^j$. Indeed, the base case is trivial, and if we know $P(1),P(3),\ldots,P(2^j-1)\pmod{2^j}$ then
\[P(x+2^j k)\equiv P(x)+2^j k P'(x)\pmod{2^{j+1}}\]for all $0\le k\le1$ and odd $1\le x\le 2^j-1\le 2^5-1$. Thus we know $P(1),P(3),\ldots,P(2^5-1)\pmod{2^5}$ and $P'(1),P'(3),\ldots,P'(2^5-1)\pmod{2^5}$, so by the first paragraph we know $P(1),P(3),\ldots,P(2^{10}-1)\pmod{2^{10}}$ by taking all $1\le k\le 2^5$ and odd $1\le x\le 2^5-1$.
Clearly there are $2^9$ ways to choose $P(1)$, and the number of ways to choose a sequence $P'(1),P'(3),\ldots,P'(2^5-1)\pmod{2^5}$ for $P'\in\mathbb{Z}[x]$ is just the number of ways to choose $P'(1),P'(2),\ldots,P'(2^5)\pmod{2^5}$ divided by $2$ (since we know that $2|P'(a)-P'(b)$ if $a,b$ are both odd, and there are clearly just as many sequences with $P'(1)$ odd as with $P'(1)$ even). Writing the Newton interpolation polynomial
\[P'(x)=\sum_{k=0}^{2^5-1}\Delta^k[P'](0)\binom{x}{k}\equiv\sum_{k=0}^{2^5-1}a_k\binom{x}{k}\pmod{2^5}\forall x\in\mathbb{Z},\]we need $v_2(a_k)\ge v_2(k!)$ for all $0\le k\le 2^5-1$ (all other terms in the denominators are invertible; we can see the equivalence to being in $\mathbb{Z}[x]$ by considering the $[x^k]$ coefficients in reverse order), so for $0\le k\le1$ we have $2^5$ choices for $a_k\pmod{2^5}$, for $2\le k\le3$ we have $2^4$ choices, for $4\le k\le 5$ we have $2^2$ choices, for $6\le k\le 7$ we have $2^1$ choices, and for $8\le k\le 2^5-1$ we have $2^0=1$ choice. Thus we have an upper bound of
\[2^9\cdot\frac{1}{2}\cdot 2^{2(5+4+2+1)}=2^{32}.\]
Edit. This is wrong; see below.
math154
08.09.2011 05:09
Now I think we can even strengthen this to $2^{20}$, but this feels pretty fishy so hopefully people can check it.
Lemma: If $Q\in\mathbb{Z}[x]$, there are at most (actually, exactly, but this is unnecessary for the problem) $2^{12}=2^{5+4+2+1}$ possible sequences $(Q(1),Q(3),\ldots,Q(2^5-1))\pmod{2^5}$.
Proof: Let $R(x)=Q(2x+1)$, so Newton interpolation yields
\[Q(x)=R\left(\frac{x-1}{2}\right)=\sum_{k\ge0}\Delta^k[R](0)\binom{\frac{x-1}{2}}{k}=\sum_{k\ge0}a_k\binom{\frac{x-1}{2}}{k},\]where it's clear that
\begin{align*}
(a_0,a_1,\ldots,a_{2^4-1})\pmod{2^5}
&\longleftrightarrow (R(0),R(1),\ldots,R(2^4-1))\pmod{2^5} \\
&\longleftrightarrow(Q(1),Q(3),\ldots,Q(2^5-1))\pmod{2^5}.
\end{align*}Suppose for the sake of contradiction that $v_2(a_k)<v_2(k!)+k$ for some $k\ge0$, and let $k_0$ be the largest such $k$. Then $[x^{k_0}]Q(x)\not\in\mathbb{Z}$, which is impossible. Thus $v_2(a_k)\ge v_2(k!)+k$ for all $k\ge0$, so we have $2^5$ choices for $a_k\pmod{2^5}$ for $k=0$, $2^4$ choices for $a_k\pmod{2^5}$ for $k=1$, $2^2$ choices for $a_k\pmod{2^5}$ for $k=2$, $2^1$ choices for $a_k\pmod{2^5}$ for $k=3$, and $2^0$ choices for $a_k\pmod{2^5}$ for $k\ge4$, for a total of at most $2^{5+4+2+1}=2^{12}$ possibilities.$\blacksquare$
As proven in the first half of my previous post, there's a bijection between complete remainder systems and $2^4+1$-tuples
\[(P(1)\pmod{2^{10}},P'(1)\pmod{2^5},P'(3)\pmod{2^5},\ldots,P'(2^5-1)\pmod{2^5})\]such that $P(1),P'(1)$ are odd (and thus $P'(3),\ldots,P'(2^5-1)$ are also odd).
Hence there are $2^9$ choices for $P(1)\pmod{2^{10}}$ and at most $\frac{2^{12}}{2}$ choices for $(P'(1)\pmod{2^5},P'(3)\pmod{2^5},\ldots,P'(2^5-1)\pmod{2^5})$ by the lemma and symmetry (since $Q(1)$ is obviously equally often odd as even over all polynomials with integer coefficients), so finally, there are at most $2^{9+12-1}=2^{20}$ complete remainder systems in total.
Edit. This is wrong; see below.
math154
14.02.2013 10:01
math154 wrote: Furthermore, suppose we know what $P'(1),P'(3),\ldots,P'(2^5-1)\pmod{2^5}$ are. If we also know $P(1)\pmod{2^{10}}$, then by induction on $1\le j\le5$ we know what $P(1),P(3),\ldots,P(2^j-1)$ are modulo $2^j$. Indeed, the base case is trivial, and if we know $P(1),P(3),\ldots,P(2^j-1)\pmod{2^j}$ then \[P(x+2^j k)\equiv P(x)+2^j k P'(x)\pmod{2^{j+1}}\]for all $0\le k\le1$ and odd $1\le x\le 2^j-1\le 2^5-1$. Wow, this is one of the stupidest things I've ever written. Fortunately, we can use the same Newton interpolation method to prove that $2^{35}$ is in fact the best bound possible. Shift everything by $1$ so that we're working with $(r(0),r(2),\ldots,r(2^{10}-2))$ and complete remainder sequences are instead permutations of $(0,2,\ldots,2^{10}-2)$. (More concretely, take $P(x)\to P(x+1)-1$.) This isn't very important but it simplifies Lemma 1 slightly. Let $C$ denote the set of polynomials yielding complete remainder sequences. For any $P\in\mathbb{Z}[x]$, let $R(P)$ be the remainder sequence of $P$ and for convenience, let $R(S)=\{R(P):P\in S\}$ for any set $S$. Lemma 1. $P(x) = a_0+a_1x+\cdots+a_dx^d\in\mathbb{Z}[x]$ lies in $C$ iff $2\mid a_0$ and $2\nmid a_1$. Proof. First we note that $P$ maps even integers to even integers iff $P(0)$ is even, so $P$ yields a complete remainder sequence iff $2\mid a_0$ and $P$ is injective mod $2^{10}$ over even residues. But \[ \frac{P(2u) - P(2v)}{2u-2v} = \sum_{k=1}^{d}a_k \frac{(2u)^k-(2v)^k}{2u-2v}\equiv a_1\pmod{2} \] for distinct integers $u,v$, so $P$ is injective iff $2\nmid a_1$ (if $2^{10}\mid P(a)-P(b)$ for two distinct even residues $a,b$, we must have $2\mid a_1$, while if $2\mid a_1$, we get $2^{10}\mid P(2^{n-1})-P(0)$), as desired. $\blacksquare$ Lemma 2. Call a polynomial $P\in\mathbb{Z}[x]$ reduced if $0\le [x^k]P<2^{10-k-v_2(k!)}$ for all nonnegative integers $k$. If $T$ denotes the set of reduced polynomials, then every remainder sequence is achieved by a unique polynomial $P\in T$. As a simple consequence, $R:T\to R(\mathbb{Z}[x])$ is a bijection. Proof. Take a remainder sequence $\alpha\in R(\mathbb{Z}[x])$ and polynomial $P(x) = a_0+a_1x+\cdots+a_dx^d\in\mathbb{Z}[x]$ of degree $d$ such that $\alpha=R(P)$. Define the two-step finite differences $b_k = \Delta^k_2[P](0) \equiv \Delta^k_2[\alpha](0) \pmod{2^{10}}$. By Newton interpolation, $P(x) = \sum_{k=0}^{d} b_k \binom{x/2}{k}$. Since $a_d\in\mathbb{Z}$, we must have $2^d d!\mid b_d$; by a simple reverse induction, we get $2^k k!\mid b_k$ for all $k$. Let $c_k = b_k/(2^k k!)$, extend indices so that $a_k,b_k,c_k=0$ for $k>d$, and note that $\alpha$ uniquely determines $(b_k\pmod{2^{10}})_{k\ge0}$ (and vice versa). It thus suffices to show that exactly one choice of $(c_k)_{k\ge0}$ leads to a reduced polynomial $P\in T$. But $v_2(2^k k!) = k+v_2(k!)$, so for fixed $k$, $b_k\pmod{2^{10}}$ uniquely determines $c_k\pmod{2^{10-k-v_2(k!)}}$ (and vice versa). Yet the polynomials $2^k k! \binom{x/2}{k} = x(x-2)\cdots(x-2k+2)$ form a basis of $\mathbb{Z}[x]$, so for fixed $\alpha$, exactly one sequence $(c_k)_{k\ge0}$ corresponds to $(a_k)_{k\ge0}$ with $P\in T$, and we're done. $\blacksquare$ Combining the two lemmas, we see that $|R(C)|$ is equal to the number of $P\in T$ with $2\mid a_0$ and $2\nmid a_1$, or equivalently, \[ \frac{1}{2}\frac{1}{2}\prod_{k\ge0}2^{\max(10-k-v_2(k!),0)} = 2^{-1-1+10+9+7+6+3+2} = 2^{35}, \]as desired. Comment. It's not hard to find the number of distinct $(r(1),r(2),r(3),\ldots,r(2^{10}-1))\pmod{2^{10}}$ by writing $P(x) = P_0(x)(x-1)^{2^{10}}+P_1(x) x^{2^{10}}$---we can work with $P_0$ and $P_1$ separately for the even and odd residues, respectively, to get $(2^{37})^2$ sequences.
bumjoooon
18.11.2020 15:57
Brilliant Problem. It is same as Rust's proof, but I'm writing this proof hoping this is more readable. Following terms are divided $2^{10}=1024$ when $x$ is odd. \begin{align*} (x-1)(x-3)(x-5)(x-7)(x-9)(x-11)\\ 2^2 \times (x-1)(x-3)(x-5)(x-7)(x-9)\\ 2^3 \times (x-1)(x-3)(x-5)(x-7)\\ 2^6 \times (x-1)(x-3)(x-5)\\ 2^7 \times (x-1)(x-3)\\ 2^9 \times (x-1) \end{align*}Thus we can reduce any polynomial into $a_5 x^5 + a_4 x^4 + a_3 x^3 +a_2 x^2 + a_1 x^1 + a_0$ with \begin{align*} 0 \le a_5 < 2^2, \; 0 \le a_4 < 2^3 ,\; &0\le a_3 < 2^6\\ 0 \le a_2 < 2^7, \;0 \le a_1 < 2^9 ,\; &0\le a_0 < 2^{10} \end{align*}Since $P($odd$)$ is odd, $a_0+a_1+...+a_5$ is odd. Also, you can easily see that $P(x+512)-P(x)$ is $2$ times odd number. This gives $a_5+a_3+a_1$ even. Here we get $2^{2+3+6+7+9+10} / 2^2 = 2^{35}$ possibility at most. (Note that not every polynomial gives such nice remainders.)