In Theorem 2 of their paper, "Pseudoprime values of the Fibonacci sequence, polynomials and the Euler function", Indagationes Mathematicae, Volume 17, Issue 4, pp. 611--625, Luca and Shparlinski show that for a fixed polynomial $f(x)\in \mathbb{Z}[x]$ and fixed base $a>1$, the number of $1\leq n \leq x$ for which $f(n)$ is pseudoprime to the base $a$ is
$$ \ll x\frac{\log \log x}{\log x}. $$
Is there a lower bound that would allow one to tell whether, for any $f$, any $a>1$ is a base to which infinitely many $f(n)$ are pseudoprime? (If $f(n)=n$ there is a lower bound due to Pomerance.) In the absence of such a lower bound, is there any guide as to how small one may take $a$ relative to $n$, and hence $f(n)$, for general $f$?
If $f$ is a cyclotomic polynomial $\Phi_r(n)$, $r$ an odd prime, and the base $a$ is allowed to vary, i.e., take $a=n$ for $n$ in some congruence class, then a result of Cipolla, mentioned here, gives that
$$ n^{\Phi_r(n)-1} \equiv 1 \bmod \Phi_r(n) $$
provided $n$ is in the right congruence classes. Assuming Bateman-Horn, one then has examples of $a$ of size $n$ to which $f(n)=\Phi_r(n)$ are pseudoprime. Are there any explicit constructions that can give $a=o(n)$ for an arbitrary $f$?
Thank you!
