Let $p$ be a prime number and $f$ be a bijection from $\left\{0,1,\ldots,p-1\right\}$ to itself. Suppose that for integers $a,b \in \left\{0,1,\ldots,p-1\right\}$, $|f(a) - f(b)|\leqslant 2024$ if $p \mid a^2 - b$. Prove that there exists infinite many $p$ such that there exists such an $f$ and there also exists infinite many $p$ such that there doesn't exist such an $f$.
Problem
Source: 2025 China Mathematical Olympiad Day 2 Problem 5
Tags: number theory, prime numbers
28.11.2024 10:39
It's that one antiproblem First, take any sufficently large $p$ such that $K = 2^{1434} \mid \varphi(p)$ by Dirichlet's and let $g$ be a primitive root. Then there exists some $k = g^{K}$ such that $x^{K} - k$ has $K$ roots, $r_1, r_2, \dots, r_{K}$. Each $r_i$ has a chain \[ r_i \mapsto r_i^2 \mapsto r_i^4 \dots \mapsto r_i^K = k \]which means that $|f(r_i) - f(k)| < 2024 \cdot 1434$. However, there are $K > 2024 \cdot 1434$ elements $r_i$, which gives a contradiction by size, so this $p$ does not work. Next, take $p \equiv 3 \pmod{4}$. This means that $x^{2^k} - k$ has only two solutions for all $k$ so the graph formed by $a$ whose eventually square is $k$ is locally a binary tree with one leaf for each nonleaf parent. Eventually this cycles so we get a subgraph of the arrow graph $a \mapsto a^2$ consists of $k_0, k_1, \dots, k_{n-1}$ and $-k_0, -k_1, \dots, -k_{n-1}$ which are leaves, where $\pm k_i \mapsto k_{i+1}$ cyclically. We can embed this in $f$ in $2n$ consecutive elements $0, 1, 2, \dots, 2n-1$ by having $f(k_0) = 0, f(k_1) = 4, f(k_2) = (8), \dots$ and $f(k_{n-1}) = 2, f(k_{n-2}) = 6, \dots$ with a jump near $2n-2$ so each $f(k_i)$ is even and $|f(k_i) - f(k_{i+1})| \in \{2, 4\}$ with exactly one occurence of $2$, and then take $f(-k_i) = f(k_i) + 1$. Repeat this for all nonzero $k$, and then put $f(0)$ as the remaining residue.
28.11.2024 14:45
Elegant but a bit easy as P5. Construction is $p\equiv 3\pmod 4$ and the graph is several "sunflowers". Proof is take $2^{10000}\mid p-1$ to get a binary tree, getting contradiction by $2^k>>2024k$
29.11.2024 19:57
Consider the undirected graph $G$ over $\mathbb F_p$ where two points are connected iff one of them is the square of the other. Define the distance between two numbers in $\mathbb F_p$ to be the minimal number of edges in a path between them in $G$. Note that two adjacent edges have a difference in $f$ values at most $2024$, and this holding true is equivalent to the problem condition. Let $t = \nu_2(p-1)$ and $g$ be a primitive root of $p$. Additionally, let $p - 1 = 2^t \cdot c$ and $S$ be the set of $x\in \mathbb F_p $ so that $x^c \equiv 1 \pmod p$, and $T = f(S)$. Note that every $a \in \mathbb F_p$ is at most a "distance" of $t$ between some value in $S$. This means that every $a\in \mathbb F_p$ satisfies $f(a)$ is at most $2024t$ different from some element in $T$. However, this means that $\sum_{i\in T} (4048t + 1) \ge p$, so $c(4048t + 1) \ge p$, so $4049ct \ge p > 2^t \cdot c$, meaning that $4049t > 2^t$, obviously false for $t > 16$. Therefore, there are infinitely many $p$ where $f$ doesn't exist. Now we prove there are infinitely many $p$ where $f$ exists (Dirichlet guarantees infinitely many $p$ where $t > 16$) Consider any $p\equiv 3\pmod 4$ and let $d$ be the order of $2$ modulo $p$. We show that such a function exists. Also choose $f(0) = 0$. Since $0$ isn't connected to any vertex in $G$ other than itself, we may just eliminate $0$ from $G$ and try to find a bijection on $\{1,2,\ldots, p - 1\}$ to itself that satisfies the condition. Note that $d\mid \frac{p-1}{2}$ (and this also implies that $d$ is odd). Also call a point in $G$ not equal to $1$ an outsider if it has degree $1$. Claim: The outsiders of $G$ are exactly the quadratic non-residues modulo $p$. Proof: Note that every quadratic non-residue is an outsider because it can only be connected to it's square (as it has no square roots). However, a quadratic residue $r \ne 1$ can be connected to both its square and two square roots (note that these are all distinct from $r$ and at least two of these are distinct modulo $p$) so $r$ is not an outsider. $\square$ Claim: Every non-outsider of $G$ is connected to exactly one outsider of $G$ Proof: Take the square root of this non-outsider and choose the sign to make it a NQR (because $p \equiv 3 \pmod 4$). $\square$ Let $G'$ be the subgraph of $G$ consisting of all the non-outsiders. Notice that $G$ is just $G'$ except every vertex in $G'$ is connected to a vertex not in $G'$ (however any vertex not in $G'$ is only connected to one other vertex). Claim: Every vertex in $G$ is connected to at most three other points in $G$. Proof: Follows because each number has at most one square and two square roots in $\mathbb F_p$. $\square$ Claim: Every connected component of $G$ consists of a cycle between some number of non-outsiders, each connected to one different outsider. Proof: We show that every connected component in $G'$ is a cycle, which will clearly finish. Let $v$ be a nonzero quadratic residue modulo $p$. Note that $v$ is a non-outsider. The path $v \to v^2 \to v^4 \to v^8 \cdots$ will eventually come back to $v$ in modulo $p$. Suppose $k$ is the smallest positive integer so that $v^{2^k} \equiv v \pmod p$ ($k$ must exist). We claim that $v \to v^2 \to v^4 \to \cdots v^{2^{k-1}} \to v$ is the connected component of $v$ in $G'$. Note that this is clearly part of the connected component of $v$. Now suppose some other vertex $V$ in $G'$ was in the connected component of $v$. Let $w$ be a vertex in $\{v, v^2, v^4, \ldots, v^{2^{k-1}} \}$ connected to $V$. Note that $V$ is not an outsider of $G$, nor is it $w^2$ or a square root of $w$ in $\mathbb F_p$, so it cannot be connected to $w$, a contradiction. $\square$ Claim: For any connected component of $G$, we can assign a mapping so that every vertex maps to a number in $\{n, n+1, n+2,\ldots, n + (2d-1)\}$, satisfying the following conditions: $2d$ is the number of elements in the connected component of $G$ (it must be even by our previous claim), no two vertices map to the same number, and the mappings between two adjacent numbers don't differ by more than $4$ Proof: WLOG that $n = 1$, as at the end we can add everything by $n - 1$. Write the vertices of the component be $v_1, v_2, \ldots, v_d$ and $w_1, w_2, \ldots, w_d$, where the $v_i$ are in $G'$ ,the $w_i$ are outsiders, $v_i$ is connected to $w_i, v_{i+1}, v_{i - 1}$ for each $i$ (indices are taken modulo $d$). Case 1: $d$ is even Let $d = 2x$. For $1 \le i \le x$, write $v_i = 4i - 3$ and for $x < j \le d$, write $v_j = 2d - 1 - 4(j - (x+1))$. Note that this covers all odd numbers in $\{1, 3, \ldots, 2d\}$. Now for each $i$, let $w_i = v_i + 1$. This construction clearly works. Case 2: $d$ is odd Let $d = 2x + 1$. For $1 \le i \le x+1$, let $v_i = 4i - 3$ and for $x+1 < j \le d$, write $v_j = 2d - 1 - 4(j - (x+1))$. This covers all odd numbers in $\{1,3,\ldots, 2d\}$. Now, for each $i$, let $w_i = v_i + 1$. This construction clearly works. $\square$ Now let $C_1, C_2, \ldots, C_l$ be the connected components of $G$ and suppose they have lengths $2d_1, 2d_2, \ldots, 2d_l$. Let $s_i = 2(d_1 + d_2 + \cdots + d_i)$, where $s_0 = 0, s_l = p - 1$. For any $0\le k< l$, map the vertices $C_k$ to the numbers in $\{s_k + 1, s_k + 2, \ldots, s_k +2 d_k \} = \{s_k +1 , s_k + 2, \ldots, s_{k+1}\}$ so that no two adjacent vertices are mapped to numbers differing by more than $4$ and no two vertices map to the same number. Now define $f$ over the described mappings of $\{C_i\}$. To see that $f$ works, note that any two $a,b$ with $p\mid a^2 - b$ must be adjacent in $C_i$ for some $i$, so $|f(a) - f(b)| \le 4 \le 2024$, as desired. Additionally, $f$ must be a bijection because the sets $\{s_k + 1, s_k + 2, \ldots, s_{k + 1}\}$ over $0 \le k < l$ are disjoint and their union is exactly $\{1, 2, 3, \ldots, p -1\}$. Therefore $f$ works for all primes $p \equiv 3 \pmod 4$.
10.12.2024 14:08
To prove that there are infinetly many which are not possible take any prime $p$ such that $p\equiv 1\pmod 2^{10000000}$. Thus we get that there are $2^{9999999}$ values that have order $2^{10000000}$, however we can get by repeated application of the requirements they are at most $2024\cdot 10000000$ away from $1$ which clearly is not possible for all of them. To see the other direction take a prime $3\pmod 4$. Clearly raising all the qrs forms a bijection, and each nqr maps to one qr so we get a number of furry cycles and clearly we can form a bijection using those.