Find all integers $n > 4$ st for every two subsets $A,B$ of $\{0,1,....,n-1\}$ , there exists a polynomial $f$ with integer coefficients st either $f(A) = B$ or $f(B) = A$ where the equations are considered mod n. We say two subsets are equal mod n if they produce the same set of reminders mod n. and the set $f(X)$ is the set of reminders of $f(x)$ where $x \in X$ mod n.
Problem
Source: Iran MO 3rd round 2023 NT exam , P1
Tags: algebra, polynomial
17.08.2023 22:37
We'll show that the answer is all prime numbers $p$. Case 1: There exist coprime natural numbers $x , y > 1$ such that $n=xy$. Define sets $A$ and $B$ as $A=\{0,1,...,xy-1\}$ and $B=\{x,y\}$. While $|A|>|B|$ , then it's enough to show that there doesn't exist a polynomial $f \in \mathbb{Z}[x]$ such that $f(A) \equiv B \pmod n$. Considering the counterexample , there exist natural numbers $i , j \in \mathbb{N}$ such that $f(i) \equiv x \pmod y $ and $f(j) \equiv y \pmod x $ ; thus since $gcd(x , y)=1$ , by CRT there exist a natural number $a$ such that : $$f(a) \equiv x \pmod y $$$$f(a) \equiv y \pmod x $$And while $f(a)$ equals to $x$ or $y$ modulo $xy$ , we can get that $x|y$ or $y|x$ which is a contradiction. Case 2: There exist an odd prime number $p$ such that $n=p^2$. Define $A=\{0,1,...,p^2-1\}$ and $B=\{1,2,...,p,p+1\}$. Then if there exist a proper polynomial $f(x)$ , since this polynomial produce a complete residue system modulo $p$ , there exist a unique number $i \in \mathbb{N}$ such that $f(i) \equiv 1 \pmod p $ and for each natural number $k$ we have : $$f(i+pk) \equiv f(i)+pkf'(i) \pmod {p^2} $$and if $p|f'(i)$ , all of the $f(i+pk)$ values are $1$ modulo $p^2$ and they don't produce $p+1$. Also if $gcd(p , f'(i))=1$ , values of $f(i+pk)$ produce all numbers $1 , p+1 , 2p+1 , ... , (p-1)p+1$ modulo $p^2$ which is a contradiction again. Obviously by considering same sets for each $n=p^k$ , we can get the contradiction too. Case 3: $n=8$. Define $A=\{0,1,4,5\}$ and $B=\{0,1,2\}$. Thus if $f(A) \equiv B \pmod 8 $ , without losing the generality we can assume that $f(0)$ and $f(4)$ are even and while these numbers are equal modulo $4$ , they can't be $0 , 2$ modulo $8$ which is a contradiction.Obviously by considering same sets for each $n=2^k > 4$ , we can get the contradiction too. Case 4: $n$ equals to a prime number $p$. Since for arbitrary natural numbers $a_1 , ... , a_p$, by Lagrange interpolation there exist a polynomial $f(x)$ with integer coefficients such that $f(i) \equiv a_i \pmod p $ for each $i$ , these numbers are suitable. So we're done.
18.08.2023 11:40
Another solution for composite numbers set $N = ab$ when $a$ and $b$ both greater than $1$. $ X =\{ 1 , 2 , .... , a-1 , a+1 , ..... , 2a - 1 , 2a +1 , ........., ab - 1\}$ $ Y = \{ 0 , 1 , 2 , ..... , a-1\} $ It's easy to check this two sets works though the $f(X)$ can't produce all the remainders of $a$.
07.09.2023 05:51
Shayan-TayefehIR wrote: We'll show that the answer is all prime numbers $p$. Case 1: There exist coprime natural numbers $x , y > 1$ such that $n=xy$. Define sets $A$ and $B$ as $A=\{0,1,...,xy-1\}$ and $B=\{x,y\}$. While $|A|>|B|$ , then it's enough to show that there doesn't exist a polynomial $f \in \mathbb{Z}[x]$ such that $f(A) \equiv B \pmod n$. Considering the counterexample , there exist natural numbers $i , j \in \mathbb{N}$ such that $f(i) \equiv x \pmod y $ and $f(j) \equiv y \pmod x $ ; thus since $gcd(x , y)=1$ , by CRT there exist a natural number $a$ such that : $$f(a) \equiv x \pmod y $$$$f(a) \equiv y \pmod x $$And while $f(a)$ equals to $x$ or $y$ modulo $xy$ , we can get that $x|y$ or $y|x$ which is a contradiction. Case 2: There exist an odd prime number $p$ such that $n=p^2$. Define $A=\{0,1,...,p^2-1\}$ and $B=\{1,2,...,p,p+1\}$. Then if there exist a proper polynomial $f(x)$ , since this polynomial produce a complete residue system modulo $p$ , there exist a unique number $i \in \mathbb{N}$ such that $f(i) \equiv 1 \pmod p $ and for each natural number $k$ we have : $$f(i+pk) \equiv f(i)+pkf'(i) \pmod {p^2} $$and if $p|f'(i)$ , all of the $f(i+pk)$ values are $1$ modulo $p^2$ and they don't produce $p+1$. Also if $gcd(p , f'(i))=1$ , values of $f(i+pk)$ produce all numbers $1 , p+1 , 2p+1 , ... , (p-1)p+1$ modulo $p^2$ which is a contradiction again. Obviously by considering same sets for each $n=p^k$ , we can get the contradiction too. Case 3: $n=8$. Define $A=\{0,1,4,5\}$ and $B=\{0,1,2\}$. Thus if $f(A) \equiv B \pmod 8 $ , without losing the generality we can assume that $f(0)$ and $f(4)$ are even and while these numbers are equal modulo $4$ , they can't be $0 , 2$ modulo $8$ which is a contradiction.Obviously by considering same sets for each $n=2^k > 4$ , we can get the contradiction too. Case 4: $n$ equals to a prime number $p$. Since for arbitrary natural numbers $a_1 , ... , a_p$, by Lagrange interpolation there exist a polynomial $f(x)$ with integer coefficients such that $f(i) \equiv a_i \pmod p $ for each $i$ , these numbers are suitable. So we're done. But how about $n=4$? I wrote a program and see that there exists $f$ with its degree $\leq 3$ that satisfy the condition for every $A,B$. However, how can we prove it mathematically?
07.09.2023 12:46
It is not hard to show that $n=4$ is also a solution. Two facts: 1. If $f(A) = B$, then for $\tilde{A} = A+a, \tilde{B} = B+b$, let $\tilde{f}(x) = f(x-a)+b$, we'll have $\tilde{f}(\tilde{A}) = \tilde{B}$. 2. If $f_1(A)=B, f_2(B)=C$, then let $f_3(x) = f_2(f_1(x))$, we'll have $f_3(A)=C$. Based on these facts, it's sufficient to consider the following five subsets of $\{0,1,2,3\}$: $\{0\},\{0,2\},\{0,1\},\{0,1,2\},\{0,1,2,3\}$. 1) $A=\{0,2\}, B=\{0\}$, $f(x) = 0$. 2) $A=\{0,1\}, B=\{0,2\}$, $f(x) = 2x$. 3) $A=\{0,1,2\}, B=\{0,1\}$, $f(x) = x^2$. 4) $A=\{0,1,2,3\}, B=\{0,1,2\}$, $f(x) = x^3+1$. Therefore, the proposition is true for $n=4$ as well.
12.09.2023 14:16
Anan_PZ wrote: It is not hard to show that $n=4$ is also a solution. Two facts: 1. If $f(A) = B$, then for $\tilde{A} = A+a, \tilde{B} = B+b$, let $\tilde{f}(x) = f(x-a)+b$, we'll have $\tilde{f}(\tilde{A}) = \tilde{B}$. 2. If $f_1(A)=B, f_2(B)=C$, then let $f_3(x) = f_2(f_1(x))$, we'll have $f_3(A)=C$. Based on these facts, it's sufficient to consider the following five subsets of $\{0,1,2,3\}$: $\{0\},\{0,2\},\{0,1\},\{0,1,2\},\{0,1,2,3\}$. 1) $A=\{0,2\}, B=\{0\}$, $f(x) = 0$. 2) $A=\{0,1\}, B=\{0,2\}$, $f(x) = 2x$. 3) $A=\{0,1,2\}, B=\{0,1\}$, $f(x) = x^2$. 4) $A=\{0,1,2,3\}, B=\{0,1,2\}$, $f(x) = x^3+1$. Therefore, the proposition is true for $n=4$ as well. Thank you for mentioning that , actually the problem says to find all proper number $n>4$ on the exam. ( Surely for avoiding this messy case. )