Prove that there exists $c>0$ such that for any odd prime $p=2k+1$, the numbers $1^0, 2^1,3^2,\dots,k^{k-1}$ give at least $c\sqrt{p}$ distinct residues modulo $p$. Proposed by M. Turevsky, I. Bogdanov
Problem
Source: All-Russian MO 2024 11.8
Tags: number theory, number theory proposed
math_comb01
28.04.2024 00:33
Probably, a solution based off primitive roots (generators) also works. Here's a one with just careful analysis of the residues.
Assume that the numbers $\{i^{i-1}\}$ gives exactly $s$ residues mod $p$, let $p/4 = u$ now we focus on $f(n)=(2n)^{2n-1}/n^{2(n-1)} = 2^{2n-1} \cdot n$, where $n \leq t$, it is clear that $f$ leaves at most $s^2$ residues, now say $a \sim b$ if $f(a) \equiv f(b) (\mod p)$
Claim 1: There are at most 1 $a,b$ such that $b-a$ is fixed and less than $u$ and $a \sim b$
ProofObvious Now we use C-S to finish, Let $t$ denote the number of pairs for which $a \sim b$. let $f(1),\cdots f(u)$ gives $j$ different remainders mod $p$ each appearing $a_1,a_2 \cdots a_j$ times then by C-S, we have $u-1 \geq t = \sum \binom{a_i}{2} \geq (u^2/j-u)/2$ combining this with $j \leq s^2$ gives us the bound $s \geq \sqrt{p/12}$ which gives us the desired bound.
L.Bill
28.04.2024 02:56
math_comb01 wrote: Probably, a solution based off primitive roots (generators) also works. Here's a one with just careful analysis of the residues.
Assume that the numbers $\{i^{i-1}\}$ gives exactly $s$ residues mod $p$, let $p/4 = u$ now we focus on $f(n)=(2n)^{2n-1}/n^{2(n-1)} = 2^{2n-1} \cdot n$, where $n \leq t$, it is clear that $f$ leaves at most $s^2$ residues, now say $a \sim b$ if $f(a) \equiv f(b) (\mod p)$
Claim 1: There are at most 1 $a,b$ such that $b-a$ is fixed and less than $u$ and $a \sim b$
ProofObvious Now we use C-S to finish, let $f$ gives $j$ different remainders mod $p$ each appearing $a_1,a_2 \cdots a_j$ times then by C-S, we have $2(t-1) \geq (t)(t/j-1)$ combining this with $j \leq s^2$ gives us the bound $s \geq \sqrt{p/12}$ which gives us the desired bound.
what is $t$? $t$ might be $u$ in your solution.
Kingsbane2139
09.05.2024 13:59
math_comb01 wrote: Probably, a solution based off primitive roots (generators) also works. Here's a one with just careful analysis of the residues.
Assume that the numbers $\{i^{i-1}\}$ gives exactly $s$ residues mod $p$, let $p/4 = u$ now we focus on $f(n)=(2n)^{2n-1}/n^{2(n-1)} = 2^{2n-1} \cdot n$, where $n \leq t$, it is clear that $f$ leaves at most $s^2$ residues, now say $a \sim b$ if $f(a) \equiv f(b) (\mod p)$
Claim 1: There are at most 1 $a,b$ such that $b-a$ is fixed and less than $u$ and $a \sim b$
ProofObvious Now we use C-S to finish, Let $t$ denote the number of pairs for which $a \sim b$. let $f(1),\cdots f(u)$ gives $j$ different remainders mod $p$ each appearing $a_1,a_2 \cdots a_j$ times then by C-S, we have $u-1 \geq t = \sum \binom{a_i}{2} \geq (u^2/j-u)/2$ combining this with $j \leq s^2$ gives us the bound $s \geq \sqrt{p/12}$ which gives us the desired bound.
why is claim1 true? if $a \sim b$ then $a+1 \sim b+1$ so there are more than one pair
Randomization
09.05.2024 14:05
math_comb01 wrote: Probably, a solution based off primitive roots (generators) also works. Here's a one with just careful analysis of the residues.
Assume that the numbers $\{i^{i-1}\}$ gives exactly $s$ residues mod $p$, let $p/4 = u$ now we focus on $f(n)=(2n)^{2n-1}/n^{2(n-1)} = 2^{2n-1} \cdot n$, where $n \leq t$, it is clear that $f$ leaves at most $s^2$ residues, now say $a \sim b$ if $f(a) \equiv f(b) (\mod p)$
Claim 1: There are at most 1 $a,b$ such that $b-a$ is fixed and less than $u$ and $a \sim b$
ProofObvious Now we use C-S to finish, Let $t$ denote the number of pairs for which $a \sim b$. let $f(1),\cdots f(u)$ gives $j$ different remainders mod $p$ each appearing $a_1,a_2 \cdots a_j$ times then by C-S, we have $u-1 \geq t = \sum \binom{a_i}{2} \geq (u^2/j-u)/2$ combining this with $j \leq s^2$ gives us the bound $s \geq \sqrt{p/12}$ which gives us the desired bound.
This solutions seems false. Can you please send the fixed version?? I am sure you can do it..., I have seen your other posts...
NO_SQUARES
09.05.2024 14:29
Kingsbane2139 wrote: math_comb01 wrote: Probably, a solution based off primitive roots (generators) also works. Here's a one with just careful analysis of the residues.
Assume that the numbers $\{i^{i-1}\}$ gives exactly $s$ residues mod $p$, let $p/4 = u$ now we focus on $f(n)=(2n)^{2n-1}/n^{2(n-1)} = 2^{2n-1} \cdot n$, where $n \leq t$, it is clear that $f$ leaves at most $s^2$ residues, now say $a \sim b$ if $f(a) \equiv f(b) (\mod p)$
Claim 1: There are at most 1 $a,b$ such that $b-a$ is fixed and less than $u$ and $a \sim b$
ProofObvious Now we use C-S to finish, Let $t$ denote the number of pairs for which $a \sim b$. let $f(1),\cdots f(u)$ gives $j$ different remainders mod $p$ each appearing $a_1,a_2 \cdots a_j$ times then by C-S, we have $u-1 \geq t = \sum \binom{a_i}{2} \geq (u^2/j-u)/2$ combining this with $j \leq s^2$ gives us the bound $s \geq \sqrt{p/12}$ which gives us the desired bound.
why is claim1 true? if $a \sim b$ then $a+1 \sim b+1$ so there are more than one pair No. Let I will prove the claim (replace $a$ with $b$). If $a-b=k$ is fixed number, then $a=b+k$ and so we have $p|2^{2(b+k)-1} \cdot (b+k)-2^{2b-1} \cdot b \Rightarrow 4^k \cdot (b+k) \equiv b \Rightarrow \frac{1}{4^k} \equiv 1+k/b \Rightarrow b \equiv k \cdot \frac{1}{4^k-1}$. So, $b$ (and so $a$) is fixed if $k$ fixed, which is claim. In fact, solution from math_comb01 is similar to official solution and I'm not see reason why it is wrong...
Tintarn
12.05.2024 11:44
By the way, the problem becomes quite a bit easier (but one still needs a nice trick) if one considers all the numbers $1^0,2^1,\dots,(p-1)^{p-2}$.
math_comb01
12.05.2024 11:53
Tintarn wrote: By the way, the problem quite a bit easier (but one still needs a nice trick) if one considers all the numbers $1^0,2^1,\dots,(p-1)^{p-2}$. Also there is a well known version of the problem solved using same idea, the version is for $x^x$ where $x$ varies from $1$ to $p-1$. [here, the bound is $\sqrt{\frac{p-1}{2}}$]
EthanWYX2009
29.07.2024 05:43
Let there are $N$ different residues in $1^0, 2^1,3^2,\dots,k^{k-1},$ define $t=\lfloor p/4\rfloor .$ For all $1\le i\le t$ consider $f(i):=\frac{(2i)^{2i-1}}{(i^{i-1})^2}=i\cdot 2^{2i-1}.$ There are at most $N^2$ distinct residues in $f(1),\ldots ,f(t),$ let the number be $S.$ On the other hand if $f(i)\equiv f(j)\pmod p,$ then $2^{2(i-j)}\equiv j\cdot i^{-1}\pmod p.$ Therefore for fixed $1\le j-i\le t-1,$ $ j\cdot i^{-1}$ is also fixed, so there are at most $t-1$ pairs. For $1\le j\le S,$ let there are $n_j$ number $i$ such that $f(j)$ equiv the $j$-th residue. Then $\sum_{j=1}^Sn_j=t.$ By Jensen Inequality the number of "same residue pair" is at least $$\sum_{j=1}^S\binom{n_j}2\ge S\binom{\frac{t}{S}}{2}$$Now $S\binom{\frac{t}{S}}{2}\le t-1,$ so $S\in\Omega (p).$ By $S\le N^2$ we know $N\in\Omega (\sqrt p),$ done. $\Box$
IMO20222222222222
04.08.2024 05:28
EthanWYX2009 wrote: Let there are $N$ different residues in $1^0, 2^1,3^2,\dots,k^{k-1},$ define $t=\lfloor p/4\rfloor .$ For all $1\le i\le t$ consider $f(i):=\frac{(2i)^{2i-1}}{(i^{i-1})^2}=i\cdot 2^{2i-1}.$ There are at most $N^2$ distinct residues in $f(1),\ldots ,f(t),$ let the number be $S.$ On the other hand if $f(i)\equiv f(j)\pmod p,$ then $2^{2(i-j)}\equiv j\cdot i^{-1}\pmod p.$ Therefore for fixed $1\le j-i\le t-1,$ $ j\cdot i^{-1}$ is also fixed, so there are at most $t-1$ pairs. For $1\le j\le S,$ let there are $n_j$ number $i$ such that $f(j)$ equiv the $j$-th residue. Then $\sum_{j=1}^Sn_j=t.$ By Jensen Inequality the number of "same residue pair" is at least $$\sum_{j=1}^S\binom{n_j}2\ge S\binom{\frac{t}{S}}{2}$$Now $S\binom{\frac{t}{S}}{2}\le t-1,$ so $S\in\Omega (p).$ By $S\le N^2$ we know $N\in\Omega (\sqrt p),$ done. $\Box$ Nice Solution How did you came to the considering such a function