I am working my way through the literature regarding the following conjecture: There is a positive integer $k$ such that for all positive integers $d$,

$$P(\Phi_d(2))^k \gt \Phi_d(2).$$

I am looking at factors of Mersenne numbers $2^d-1$, so using factors from cyclotomic polynomials $\Phi_d(x)$ is a first step. $P(n)$ comes from the literature and represents the largest prime factor of integer $n$ or $1$ if $n$ has no prime factors. Examining the tables at the Cunningham project suggest that $k\gt 3$, but I have not found any theory to resolve the conjecture.

What references address this conjecture? Note that much of the literature focuses on $P(2^d -1)$ and not on the quantity above. Also I am interested in what is known about the number of factors of $\Phi_d(2)$, or the rough size of $P(\Phi_d(p))$ for $p$ prime, so references that come close to prime factors of cyclotomic values are welcome.

Gerhard "Primarily Interested In The References" Paseman, 2016.04.09.

  • 1
    $\begingroup$ I don't think there would be any $k$ for which this holds: one should expect that $\Phi_d(2)$ is pretty smooth every once in a while. What one can prove here is very weak. See my answer to mathoverflow.net/questions/199599/… which links to the paper of Stewart; his Theorem 1 gives the best known lower bounds towards your problem, and it's much weaker than what you want (but as I said what you want is probably false). $\endgroup$ – Lucia Apr 10 '16 at 18:09
  • $\begingroup$ @Lucia, thank you. I guess I am really looking for someone who has focused on $\Phi_d(p)$ and its factors. I would appreciate another literature reference that discusses your expectation ($\Phi_d(2)$ should be pretty smooth occasionally). In the mean time I will follow your link and look at the mentioned paper of Stewart and other papers. Gerhard "Royal Road To Reinventing Wheel?" Paseman, 2016.04.12. $\endgroup$ – Gerhard Paseman Apr 12 '16 at 15:48

Given a positive integer $k$, the natural density of the set of positive integers $n$ whose largest prime factor is smaller than the $k$-th root of $n$ is estimated by the value of the Dickman function $\rho$ at $k$, cf. also Page 106 in

David M. Bressoud, Factorization and Primality Testing. Springer-Verlag, 1989.

For all $k$ the value of this function is strictly positive. Therefore if instead of the numbers $\Phi_d(2)$ you would consider all integers, regardless of which $k$ you choose, the set of counterexamples to your conjecture would have positive natural density.

Now, your numbers $\Phi_d(2)$ are not arbitrary integers. In particular, their prime divisors satisfy certain congruence conditions, which prevents the numbers from having very many very small prime factors. The effect of these congruence conditions is quite big as long as the numbers are relatively small, but it is likely asymptotically negligible when $d$ goes to infinity. -- However, as Lucia already wrote, what is presently really known here does not suffice to disprove your conjecture.

Finally, obtaining evidence for or against your conjecture by means of computation is likely difficult -- already for $k = 6$ one would statistically expect one counterexample every $50000$ values of $d$ or so, hence finding one is likely to require factoring integers with several thousands of decimal digits.

| cite | improve this answer | |
  • $\begingroup$ Thank you for this perspective. I am actually considering if the congruence conditions "outweigh" the statistics enough to decide the conjecture. Also, I wonder if very smooth $d$ leading to relatively low-degree $\Phi_d(x)$ will result in a slowly growing to infinity function $k(d)$ to replace or bound from below the putative constant $k$ in the conjecture. If you know of any other references which get close to this, I would appreciate hearing of them. Gerhard "Constants Aren't And Variables Don't" Paseman, 2016.04.12. $\endgroup$ – Gerhard Paseman Apr 12 '16 at 18:19

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.