Directed graphs defined by prime divisors of polynomial values

Abstract

Let L be the class of all nonconstant polynomials f(x) == Ax2 + Bx + C ∈ Z[x], which are not of the forms Ax2, Bx. We consider the directed graph Gf whose vertex set is P and p → q iff q | f(p), p ̸= q. Let Lf (p) be the set of simple directed paths starting at p and ℓf (p) = sup{|L| : L ∈ Lf (p)}, where |L| is the number of vertices in L. We prove supp∈P ℓf (p) = ∞. We study linear polynomials f(x) = Bx + C ∈ Z[x], BC ̸= 0, in connection with Cunningham chains. For f(x) = x 2+1, we explicitly construct a simple directed path with 130 vertices starting from 2, hence ℓx2+1(2) ≥ 130. It remains open whether ℓx2+1(2) is finite or infinite. For these topics, we refer to works of C. Frayer [1], A.J. Pollington [6], C. Pomerance [7] and M. van RossumWijsmuller [8].