## Prime divisors of polynomials

A heuristic model from the last post suggests that the “expected” order of the Galois group associated to a weight one modular form of projective type $A_5$ is infinite. And when one tries to solve the inverse Galois problem for central extensions of this group, one is lead to problems concerning the prime divisors of polynomials and their properties modulo 2. But I don’t know how to answer this type of problems! Here is an analogous question that seems a little tricky to me:

Problem: Show that there are infinitely many integers $n$ such that all the odd prime divisors of $n^2 + 1$ are of the form 5 modulo 8.

To make the problem slightly easier, one can replace (5 modulo 8) by not (1 modulo 2^m) for any fixed m.

Is this an open problem?

This entry was posted in Mathematics and tagged , , , . Bookmark the permalink.

### 5 Responses to Prime divisors of polynomials

1. Ben Green says:

Frank, I believe this is a half-dimensional sieve problem and so one expects an answer of the form: the number of $n \leq X$ for which $n^2 + 1$ has all its odd prime factors $5 \pmod 8$ is asymptotic to $cX(\log X)^{-1/2}$ for some $c$, which you can specify explicitly. Details of the half-dimensional sieve can be found in Friedlander and Iwaniec, Opera Cribro, which I don’t have to hand.

The reason this is a half-dimensional sieve problem is that you can locate such $n$ by “sieving out” the conditions $n \equiv \pm a_p \pmod{p}$ for all $p \equiv 3 \pmod{8}$, where $a_p$ is one of the roots of $a^2_p \equiv -1 \pmod{p}$. So that’s two congruences classes mod $p$ for $\frac{1}{4}$ of the primes, i.e. on average you’re sieving by half a residue class for each prime.

Another example of a half-dimensional sieve problem is counting sums-of-two-squares, where now you sieve by the condition $n \equiv 0 \pmod{p}$ for all $p \equiv 3 \pmod{4}$. To find such $n$ up to $X$, you only need to sieve by those $p$ with $p \leq \sqrt{X}$.

Your problem is more difficult because you need to sieve by all $p$ up to about $X$, which is very large. I’d have to look at the details of the half-dimensional sieve to figure out whether this is fatal in terms of finding infinitely many $n$ with your property – or, better, ask an expert on the subject.

2. Emmanuel Kowalski says:

As Ben says, this is a semi-linear sieve problem, and the best reference for that is probably the book of Friedlander and Iwaniec (chapter 14). They explain that the semilinear sieve is capable of producing asymptotic formulas (as in the “sums of two squares” problem), under two basic conditions:

(1) a parity restriction: one must sieve integers in a sequence A by primes in a set P, with the property that elements of A have an even number of divisors from P — this holds for sums of two squares if A is taken to be integers = 1 mod 4 and P the primes which are 3 mod 4, but not in your case if one starts with A = {values of n^2+1 } and P = {primes = 1 mod 8} [which are those to remove, Ben has a typo with a 3 instead of 1] . (See Section 14.4 in F-I).

(2) a level of distribution condition: the sum of error terms in the sieve, up to the bound on p that you impose, must be under control.

Condition (1) seems very intrinsic to the method (e.g., I don’t see how to get a lower bound with the sieve for the integers where all prime factors are 3 mod 4).

Concretely, if instead of your problem one wants to have n^2+1 only be divisible by primes that are 1 mod 8, one could take A = { n^2 +1 with n divisible by 4 } and P = { primes = 5 mod 8 }; the parity condition is then true (since n^2+1 will be 1 mod 8). Moreover, you only need to sieve n<x by primes up to sqrt(x); the level of distribution of A is just a bit smaller (by a log or so), so there's a chance that it works by applying the semilinear sieve up to x^{1/2}/(log x), and then separately counting the integers that remain unsieved but are not of the type you want, which are very restricted, and should be fewer in number I think.

3. Ben Green says:

Emmanuel, why is it enough to sieve only by primes up to $\sqrt{x}$? For example, $145 = 5 \times 29$ is not divisible by an prime $\leq \sqrt{12}$.

• Emmanuel Kowalski says:

You’re right, I was too hasty by analogy with the sums of two squares. Then even that case seems to be hard, unless special properties of levels of distribution for n^2+1 enter the picture (e.g, with bilinear forms and such). I have a student who studied some of these papers, maybe I’ll ask him to have a closer look…