Timeline for Primes generated by cyclotomic polynomials
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 13 at 12:00 | comment | added | Joachim König | You may have more evidence which makes you "highly doubt" it, but for $p=3$ I reached all but one of the relevant primes up to 3000 in a search depth of at most 26, and that's probably not even ideal since I discarded paths containing very large primes to speed up computation, so I assume $N(g)$ actually grows much faster than $g$. That's no miracle, due to the (heuristically to be expected, assuming that new prime divisors occur with sufficient frequency) huge number of ways to choose a path of length $g$. . But this is still all rather speculative. | |
| Sep 13 at 10:33 | comment | added | Maurizio Moreschi | @JoachimKönig btw, the previous comment assuming that $S_p \setminus \{p\}$ is in fact the set of all primes $q\equiv 1 mod p$. Also, I highly doubt that N(g) grows linearly in g, because numerically the growth seems much slower. In theory, we could still have a growth of the order of $\log\log g$, but we would likely need some kind of result telling us that there exists M such that any consecutive M generations you can find prime $q\le Mg+O(1)$ | |
| Sep 13 at 9:56 | comment | added | Maurizio Moreschi | @JoachimKönig I am sorry, I am still not understanding well what you are saying. I mean, to get to all the primes before $\le N$ in our $g$-th partial, you need to have $N\ge N(g)$ by definition, so you get a lower bound asymptotic to $\frac{1}{p-1}\log\log N(g)$ as I already pointed out in the question. Unless you are suggesting that N(g) grows linearly with g, I miss a step of your reasoning. Could you maybe articulate a bit more? | |
| Sep 13 at 7:50 | comment | added | Joachim König | Well the g-th partial sum in the "usual" order is of the order of magnitude of $\log(\log(g))$ (whether you take that partial sum to mean the sum of inverses of primes $\le g$ or of the first $g$ primes doesn't matter for this asymptotic), and at least the summation above shouldn't be slower than that. | |
| Sep 13 at 5:10 | comment | added | Maurizio Moreschi | @JoachimKönig but wouldn't it be O(q/log(q)) in the usual order, from the prime number theorem? For example, the primes of the form 3k+1 less than 3000 are 207, so in the usual order 207 "steps" would suffice | |
| Sep 13 at 1:53 | history | edited | Joachim König | CC BY-SA 4.0 |
edited body
|
| Sep 13 at 1:52 | comment | added | Joachim König | "...since the sum grows much slower compared to the sum of the reciprocals of the primes in the usual order". I don't think that's true. There are so many possible ways to choose length-$g$ sequences that one should probably expect a prime $q$ to be "caught" in $g=O(q)$. I did a quick and dirty search for $p=3$ which caught most prime $q=3k+1<3000$ in a (surely not well-chosen) sequence of $\approx 3000$ steps, and the few remaining $q$ were each caught ad-hoc in 1-2 more steps (this time, specifically targetting at $q$). | |
| Sep 11 at 7:43 | history | edited | Maurizio Moreschi | CC BY-SA 4.0 |
deleted 7 characters in body
|
| Sep 10 at 19:15 | history | asked | Maurizio Moreschi | CC BY-SA 4.0 |