Timeline for Large prime factors of n²+1
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 9, 2021 at 11:26 | comment | added | Will Sawin | @user334097 I thought sieves usually give an upper bound of the right order of magnitude (up to a constant factor) when optimized. I was thinking to use the methods of Brun's theorem, and in particular Brun's sieve. | |
| Aug 9, 2021 at 8:12 | comment | added | user334097 | @Will Sawin: would not this approach give a positive proportion of $n\le x$ as an upper bound? | |
| Aug 6, 2021 at 19:30 | comment | added | Will Sawin | I think you get an upper bound of the right order of magnitude by first setting the variable $s = \frac{n^2+1}{pq}$, and summing over $s \leq x^{2 \epsilon}$ a bound for the number of $n\leq x$ where $\frac{n^2+1}{s}$ is an integer and the product of two large primes, and then bounding how often it is the product of two large primes the usual way using a sieve. Is that cheap enough? | |
| Aug 6, 2021 at 4:55 | history | edited | user334097 | CC BY-SA 4.0 |
added 99 characters in body
|
| Aug 5, 2021 at 22:08 | comment | added | user334097 | @Terry Tao: thanks! I was indeed aware of this result and the equidistribution mod pq should in principle be doable. Is there perhaps a cheap way to prove any decent upper bound for my question? | |
| Aug 5, 2021 at 21:48 | comment | added | Terry Tao | This is related to the equidistribution of roots of $n^2+1$ modulo $pq$ as $p,q$ vary. If one replaced $pq$ by a single prime $p$ then there is a famous paper of Duke, Friedlander and Iwaniec in this area mathscinet.ams.org/mathscinet-getitem?mr=1324141 . Perhaps some of the methods in this paper or followup work can be adapted to your question, though I would imagine the specific question itself has not been explicitly addressed in the literature. | |
| Aug 5, 2021 at 19:57 | history | edited | GH from MO | CC BY-SA 4.0 |
edited body
|
| Aug 5, 2021 at 18:39 | comment | added | user334097 | @GH: indeed, that is what I mean. You are of course right that this condition does not imply that $n^2+1\in P_2.$ The example is merely to illustrate that, some lower bound could possibly be given provided one can better localise primes in Iwaniec's proof, say. | |
| Aug 5, 2021 at 18:35 | history | edited | user334097 | CC BY-SA 4.0 |
added 9 characters in body
|
| Aug 5, 2021 at 17:45 | comment | added | GH from MO | Do you mean to count $n\leq x$ such that there exist two primes $p,q\geq x^\alpha$ with $pq\mid n^2+1$? Note that this condition does not imply that $n^2+1$ is $P_2$. | |
| Aug 5, 2021 at 16:50 | comment | added | LSpice | I found it hard to understand some of the quantification, so I edited, I hope in a way that clarified rather than obscuring or changing meaning. | |
| Aug 5, 2021 at 16:49 | history | edited | LSpice | CC BY-SA 4.0 |
Clarifying grammar, I hope
|
| Aug 5, 2021 at 16:33 | review | First posts | |||
| Aug 5, 2021 at 16:44 | |||||
| Aug 5, 2021 at 16:26 | history | asked | user334097 | CC BY-SA 4.0 |