5
$\begingroup$

Let $p$ be an odd prime, and let $f=\Phi_p$ be the $p$-th cyclotomic polynomial. Denote by $S_p$ the set of primes $q$ such that there exists a sequence of primes $p_1,\dots, p_g$ such that $p_1=f(1)=p$, $p_g=q$ and $p_{j+1}|f(p_j)$ for all $j=1,\dots,g-1$. If $g$ is the least possible positive integer for this to hold, we say that $q$ has $p$-generation $g$, and we write $g_p(q)=g$.

It's easy to see that all primes in $S_p$ other than $p$ are congruent to 1 mod p. Now, my intuition was telling me that $S_p\setminus \{p\}$ would in fact be the set of all primes $q \equiv 1 \mod p$, and that this prime divisors tree way of constructing the primes was just a way of presenting such primes in a naturally arising order (generationally speaking). However, when I went on and try to prove this, I realize that I could not even prove that $S_p$ was infinite. So I tried and looked up the literature, but could not find anything that I could use to answer this question.

Hence, first of all I wanted to ask if anybody knows any reference related to this sort of problem and or techniques that might be worth trying to get some more insight in the set $S_p$.

In the case the answer of whether $S_p\setminus \{p\}$ is the set of all primes $q\equiv 1 \mod p$ is actually not known, then in my opinion a good starting point would be to first study the behaviour of the sums $$ \mathfrak{s}_p(g):= \underset{g_p(q)\le g}{\sum_{q\in S_p}} \frac{1}{q}$$ as $g\to \infty$.

Clearly, if $S_p$ turns out to be finite, then $\lim_{g\to \infty}\mathfrak{s}_p(g)$ is finite, not very interesting.

On the other hand, if $S_p\setminus \{p\}$ is the set the set of all primes $q\equiv 1 \mod p$, then we know that $\mathfrak{s}_p(g)$ diverges as $g\to \infty$ from Dirichlet's theorem, but it is not clear what the rate of divergence would be, since the sum grows much slowler compared to the sum of the reciprocals of the primes in the usual order. Denoting by $N(g)$ the largest $N\ge 1$ such that for all primes $q\equiv 1 \mod p, q\le N$ one has $g_p(q)\le g$, then we would get a lower bound that is asymptotic to $\frac{1}{p-1}\log\log(N(g))$. However, first of all the problem of determining the growth of $N(g)$ as $g\to \infty$ seems highly non-trivial. Also, the chance of such a bound being asymptotically tight seems very slim, because it ignores the contribution of (too?) many larger primes along the way.

Finally, if $S_p$ happens to be infinite, but $S_p\setminus \{p\}$ is not the set of all primes $q\equiv 1 \mod p$, then the question of whether $\lim_{g\to \infty}\mathfrak{s}_p(g)$ is finite or infinite becomes non-trivial, and would certainly require some interesting non-trivial insight on the structure of the primes in $S_p$.

Therefore, my second question is if anybody has any ideas or tricks to share that can be useful to provide some non-trivial lower bounds for $\mathfrak{s}_p(g)$. I have tried some elementary considerations, but I haven't got any interesting bound that way. Maybe some technique from analytic number theory that could be applied in this case?

$\endgroup$
6
  • $\begingroup$ "...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$). $\endgroup$ Commented Sep 13 at 1:52
  • $\begingroup$ @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 $\endgroup$ Commented Sep 13 at 5:10
  • $\begingroup$ 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. $\endgroup$ Commented Sep 13 at 7:50
  • $\begingroup$ @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? $\endgroup$ Commented Sep 13 at 9:56
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Sep 13 at 12:00

0

You must log in to answer this question.