Directed graphs defined by prime divisors of polynomial values

Abstract. Let \({\mathcal L}\) be the class of all nonconstant polynomials \(f(x)=Ax^2+Bx+C\in {\mathbb Z} [x]\), which are not of the forms \( Ax^2, Bx\). We consider the directed graph \({\mathcal G}_f\) whose vertex set is \({\mathcal P}\) and \(p\to q\) iff \(q\mid f(p), p\neq q\). Let \({\mathbb L}_f(p)\) be the set of simple directed paths starting at \( p\) and \(\ell_f(p)=\sup\{ |L|: L\in {\mathbb L}_f(p)\}\), where \(\vert L\vert\) is the number of vertices in \( L\). We prove \(\sup_{p\in {\mathcal P}}\ell_f(p)=\infty\). We study linear polynomials \( f(x)=Bx+C\in {\mathbb Z}[x], BC\neq 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 \(\ell_{x^2+1}(2)\ge 130\). It remains open whether \(\ell_{x^2+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 Rossum-Wijsmuller [8].

Key words and phrases. Primes, directed graph, Cunningham chain.