# A sufficient condition for a set of primes to be the set of reducibility of an integer polynomial

Let $$P$$ be the set of all positive primes. Let $$S$$ an arbitrary infinite subset of $$P$$ satisfying the following assumption: there exists a finite Galois extension $$K$$ of $$\mathbb{Q}$$ and a conjugacy class $$C\subset \mathrm{Gal}(K/\mathbb{Q})$$ such that $$P\setminus S$$ is exactly the set of primes unramified in $$K/\mathbb{Q}$$ whose Frobenius conjugacy class is equal to $$C$$.

Must there exist a non-constant monic polynomial over $$\mathbb{Z}$$ that is reducible modulo the primes in $$S$$ and only those primes?

The above assumption is necessary. To see why, take the splitting field of the polynomial and note that the primes modulo which it is reducible are exactly the ramified primes and the unramified primes whose Frobenius conjugacy class does not contain $$n$$-cycles under the usual embedding of the Galois group into $$S_n$$ ($$n$$ is the degree of the polynomial).

• – user145520 Feb 7 '20 at 2:13
• Is there a polynomial which is reducible modulo every prime of the form $4k+1$ except $5$ and $11$? – user6976 Feb 7 '20 at 2:34
• @MarkSapir so, just except 5? (maybe $5$ and $13$?) – user44191 Feb 7 '20 at 2:38
• Yes, $5, 13$. Using a phone to type leads to misprints. – user6976 Feb 7 '20 at 2:40
• $(65 x + 1)(x + 1)$? – Robert Israel Feb 7 '20 at 20:27

No. The set of subsets of $$P$$ satisfying the OP conditions is of cardinality continuum while the set of polynomials with integer coefficients is countable.
• "Not always". The OP's question is ambiguous on whether it means "does it exist for every $S$" or "does it exist for some $S$" (without thinking I actually understood the second meaning and the first meaning doesn't make a serious question according to your remark). – YCor Feb 7 '20 at 18:46
• To make things somewhat less trivial, what if we restrict to $S$ that is decidable, i.e. such that there exists an algorithm for determining whether or not a given integer is in $S$? – Robert Israel Feb 7 '20 at 20:08
• Answer: no. There must be an algorithm for deciding membership in $S$ of time complexity no worse than that for determining whether the given polynomial factors mod $p$. – Robert Israel Feb 7 '20 at 20:40
• @RobertIsrael: The OP does not know much about the question. It could be that there is no polynomial reducble mod $p$ iff $p$ is 1 mod 4 except 5 and 13. – user6976 Feb 7 '20 at 20:57
• I haven't yet seen any serious textbook choosing the convention that a nonzero constant polynomial is irreducible (or that $1$ is prime). – YCor Feb 16 '20 at 3:58