4
$\begingroup$

It $\let\epsilon\varepsilon\let\leq\leqslant\let\geq\geqslant$is a well known result that for every $n\in\mathbb N$, $x^n+1\equiv y^n\pmod p$ is non-trivially solvable for sufficiently large primes $p$. Let $P_n$ denote the largest prime for which it is unsolvable. Ramsey theory gives (I think the proof was first given by Schur, if I'm not mistaking) $$P_n<R(\underset{n\;3\text{'s}}{\underbrace{3,\ldots,3}}),$$ where $R(\ldots)$ denotes the Ramsey number. Since $$R(\underset{n\;3\text{'s}}{\underbrace{3,\ldots,3}})\leq2-n+n\cdot R(\underset{n-1\;3\text{'s}}{\underbrace{3,\ldots,3}})\leq n\cdot R(\underset{n-1\;3\text{'s}}{\underbrace{3,\ldots,3}})$$ for $n\geq2$ and $R(3,3,3)=17$, the best explicit bound I can get from this is $P_n<\frac{17}6\cdot n!$.

A heuristic approach goes as follows: there are at least $\frac{p-1}n$ nonzero $n$th powers modulo primes $p$. The 'probability' that none of these yields a solution to the congruence is thus at most $\left(1-\frac{\frac{p-1}n}p\right)^{\frac{p-1}n}$, if we assume the $n$th powers to be distributed uniformly. If we want to bound this from above by a fixed $\epsilon>0$, we have $$\begin{align*}\left(1-\frac{\frac{p-1}n}p\right)^{\frac{p-1}n}&\leq\epsilon\\ \frac{p-1}n\log\left(1-\frac1n\right)\approx\frac{p-1}n\log\left(1-\frac{p-1}{np}\right)&\leq\log\epsilon\\ p-1&\lessapprox\frac{n\log\epsilon}{\log\left(1-\frac1n\right)}=n^2\log\epsilon+O(n).\end{align*}$$ I'm not sure if these calculations make any sense at all, but from this I would conjecture that $P_n=O(n^2)$.

Finally, my question:

Is it known that $P_n=O(n^2)$? If not, what is the best known bound, or what do heuristics tell us?

$\endgroup$
4
$\begingroup$

From the Hasse Weil Bound, it follows that the number of solutions $N_p$ to $x^n + y^n = z^n$ in $\mathbb{F}_p$ satisfies $$|N_p - (p + 1)|\le 2g\sqrt{p}$$

where $g$ is the genus. By the genus degree formula, $g\le\frac{(n - 1)(n - 2)}{2}$

Therefore, for all $p> \left((n - 1)(n - 2)\right)^2$, $N_p>0$. This doesn't give your bound of $O(n^2)$ and instead gives $O(n^4)$

$\endgroup$
  • $\begingroup$ That's a notable improvement indeed. Would it be difficult to improve it even more? I can't estimate how advanced the Hasse-Weil bound is, see. $\endgroup$ – punctured dusk Sep 5 '14 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.