Bunyakovsky conjecture

The Bunyakovsky conjecture (or Bouniakowsky conjecture) stated in 1857 by the Russian mathematician Viktor Bunyakovsky, asserts when a polynomial $f(x)$ in one variable with positive degree and integer coefficients should have infinitely many prime values for positive integer inputs. Three necessary conditions are

1. the leading coefficient of $f(x)$ is positive,
2. the polynomial is irreducible over the integers, and
3. as $n$ runs over the positive integers, the numbers $f(n)$ should be relatively prime. (Thus, the coefficients of $f(x)$ should be relatively prime.)

Bunyakovsky's conjecture is that these three conditions are sufficient: if $f(x)$ satisfies the three conditions then $f(n)$ is prime for infinitely many positive integers $n$.

For example, all cyclotomic polynomials are irreducible, with positive (in fact, =1) leading coefficient, and as $x$ runs over the positive integers, $\Phi_n(x)$ don't share a common factor greater than 1. Thus, all cyclotomic polynomials are in Bunyakovsky's conjecture, so it is conjectured strongly that for all natural number n, there are infinitely many natural number x such that $\Phi_n(x)$ is prime. In fact, it can be shown that if for all natural number n, there exists a natural number x > 1 such that $\Phi_n(x)$ is prime, then for all natural number n, there are infinitely many natural number x such that $\Phi_n(x)$ is prime.

n	natural number x > 1 such that $\Phi_n(x)$ is prime	OEIS sequence
1	3, 4, 6, 8, 12, 14, 18, 20, 24, 30, 32, 38, 42, 44, 48, 54, 60, 62, 68, 72, 74, 80, 84, 90, 98, 102, 104, 108, 110, 114, 128, 132, ...	A008864
2	2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40, 42, 46, 52, 58, 60, 66, 70, 72, 78, 82, 88, 96, 100, 102, 106, 108, 112, 126, 130, 136, ...	A006093
3	2, 3, 5, 6, 8, 12, 14, 15, 17, 20, 21, 24, 27, 33, 38, 41, 50, 54, 57, 59, 62, 66, 69, 71, 75, 77, 78, 80, 89, 90, 99, 101, 105, 110, ...	A002384
4	2, 4, 6, 10, 14, 16, 20, 24, 26, 36, 40, 54, 56, 66, 74, 84, 90, 94, 110, 116, 120, 124, 126, 130, 134, 146, 150, 156, 160, 170, ...	A005574
5	2, 7, 12, 13, 17, 22, 23, 24, 28, 29, 30, 40, 43, 44, 50, 62, 63, 68, 73, 74, 77, 79, 83, 85, 94, 99, 110, 117, 118, 120, 122, 127, ...	A049409
6	2, 3, 4, 6, 7, 9, 13, 15, 16, 18, 21, 22, 25, 28, 34, 39, 42, 51, 55, 58, 60, 63, 67, 70, 72, 76, 78, 79, 81, 90, 91, 100, 102, 106, ...	A055494
7	2, 3, 5, 6, 13, 14, 17, 26, 31, 38, 40, 46, 56, 60, 61, 66, 68, 72, 73, 80, 87, 89, 93, 95, 115, 122, 126, 128, 146, 149, 156, 158, ...	A100330
8	2, 4, 6, 16, 20, 24, 28, 34, 46, 48, 54, 56, 74, 80, 82, 88, 90, 106, 118, 132, 140, 142, 154, 160, 164, 174, 180, 194, 198, 204, ...	A000068
9	2, 3, 8, 11, 20, 21, 26, 30, 50, 51, 56, 60, 78, 98, 102, 117, 129, 134, 146, 159, 171, 186, 189, 191, 198, 200, 209, 210, 212, ...	A153439
10	2, 3, 5, 10, 11, 12, 16, 20, 21, 22, 33, 37, 38, 43, 47, 48, 55, 71, 75, 76, 80, 81, 111, 121, 126, 131, 133, 135, 136, 141, 155, ...	A246392
11	5, 17, 20, 21, 30, 53, 60, 86, 137, 172, 195, 212, 224, 229, 258, 268, 272, 319, 339, 355, 365, 366, 389, 390, 398, 414, 467, ...	A162862
12	2, 3, 4, 5, 9, 10, 12, 13, 17, 25, 27, 30, 31, 36, 38, 39, 43, 48, 52, 55, 56, 61, 62, 65, 83, 92, 94, 99, 100, 104, 105, 109, 114, ...	A246397
13	2, 3, 5, 7, 34, 37, 43, 59, 72, 94, 98, 110, 133, 149, 151, 159, 190, 207, 219, 221, 251, 260, 264, 267, 282, 286, 291, 319, 355, ...	A217070
14	2, 3, 10, 11, 14, 15, 16, 17, 18, 21, 24, 25, 29, 37, 43, 44, 46, 49, 52, 54, 61, 66, 72, 73, 78, 84, 86, 87, 99, 101, 106, 114, 115, ...	A250174
15	2, 3, 11, 17, 23, 43, 46, 52, 53, 61, 62, 78, 84, 88, 89, 92, 99, 108, 123, 124, 141, 146, 154, 156, 158, 163, 170, 171, 182, 187, ...	A250175
16	2, 4, 118, 132, 140, 152, 208, 240, 242, 288, 290, 306, 378, 392, 426, 434, 442, 508, 510, 540, 542, 562, 596, 610, 664, 680, ...	A006314
17	2, 11, 20, 21, 28, 31, 55, 57, 62, 84, 87, 97, 107, 109, 129, 147, 149, 157, 160, 170, 181, 189, 191, 207, 241, 247, 251, 274, ...	A217071
18	6, 7, 9, 42, 49, 54, 66, 73, 81, 88, 96, 100, 106, 118, 120, 121, 126, 175, 190, 196, 207, 208, 234, 235, 240, 271, 301, 312, 322, ...	A164989
19	2, 10, 11, 12, 14, 19, 24, 40, 45, 46, 48, 65, 66, 67, 75, 85, 90, 103, 105, 117, 119, 137, 147, 164, 167, 179, 181, 205, 220, 235, ...	A217072
20	4, 9, 11, 16, 19, 26, 34, 45, 54, 70, 86, 91, 96, 101, 105, 109, 110, 119, 120, 126, 129, 139, 141, 149, 171, 181, 190, 195, 215, ...	A250176
21	3, 6, 7, 12, 22, 27, 28, 35, 41, 59, 63, 69, 112, 127, 132, 133, 136, 140, 164, 166, 202, 215, 218, 276, 288, 307, 323, 334, 343, ...	A250177
22	2, 6, 12, 13, 23, 24, 26, 35, 62, 69, 91, 105, 147, 160, 163, 183, 185, 193, 229, 232, 233, 236, 248, 262, 269, 280, 294, 303, ...	A250178
23	10, 40, 82, 113, 127, 141, 170, 257, 275, 287, 295, 315, 344, 373, 442, 468, 609, 634, 646, 663, 671, 710, 819, 834, 857, 884, ...	A217073
24	2, 3, 5, 6, 10, 13, 14, 15, 18, 25, 26, 27, 31, 34, 37, 39, 40, 42, 44, 46, 49, 50, 53, 59, 62, 63, 65, 68, 69, 75, 76, 77, 83, 87, 99, ...	A250179
25	22, 33, 39, 43, 62, 74, 134, 142, 167, 212, 238, 287, 313, 335, 369, 414, 415, 418, 432, 509, 604, 679, 697, 770, 782, 815, 859, ...	A250180
26	2, 3, 21, 22, 23, 35, 39, 74, 80, 84, 89, 108, 114, 121, 126, 134, 152, 153, 171, 180, 195, 204, 230, 256, 263, 297, 321, 326, ...	A250181
27	2, 11, 44, 45, 56, 62, 63, 110, 170, 219, 234, 245, 261, 263, 333, 395, 398, 402, 413, 428, 434, 437, 498, 557, 558, 578, 633, ...	A153440
28	4, 5, 7, 13, 25, 33, 41, 63, 74, 80, 88, 94, 96, 104, 116, 144, 149, 151, 154, 165, 167, 174, 183, 191, 197, 208, 231, 241, 262, ...	A250182
29	6, 40, 65, 70, 114, 151, 221, 229, 268, 283, 398, 451, 460, 519, 554, 587, 627, 628, 659, 687, 699, 859, 884, 915, 943, 974, ...	A217074
30	2, 6, 7, 8, 9, 16, 18, 20, 26, 29, 31, 32, 33, 40, 41, 47, 57, 76, 82, 87, 88, 93, 101, 109, 120, 121, 125, 133, 140, 144, 162, 163, ...	A250183
31	2, 14, 19, 31, 44, 53, 71, 82, 117, 127, 131, 145, 177, 197, 203, 241, 258, 261, 276, 283, 293, 320, 325, 379, 387, 388, 406, ...	A217075
32	2, 44, 74, 76, 94, 156, 158, 176, 188, 198, 248, 288, 306, 318, 330, 348, 370, 382, 396, 452, 456, 470, 474, 476, 478, 560, 568, ...	A006313
33	2, 3, 13, 14, 18, 31, 44, 59, 62, 75, 80, 104, 109, 145, 185, 213, 273, 282, 309, 321, 337, 379, 399, 405, 411, 430, 452, 464, ...	A250184
34	2, 7, 13, 17, 19, 41, 48, 58, 59, 66, 86, 129, 133, 139, 143, 146, 149, 166, 167, 231, 268, 270, 299, 328, 359, 387, 397, 408, ...	A250185
35	14, 33, 39, 55, 112, 130, 132, 138, 168, 176, 179, 186, 189, 195, 210, 246, 259, 264, 310, 318, 346, 417, 431, 467, 478, 480, ...	A250186
36	3, 7, 9, 10, 11, 14, 27, 30, 33, 37, 40, 51, 62, 71, 78, 80, 82, 95, 117, 125, 137, 142, 148, 157, 185, 189, 191, 197, 223, 232, ...	A097475

The smallest natural number x > 1 such that $\Phi_n(x)$ is prime are

3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 2, 2, 2, 2, 2, 2, 6, 2, 4, 3, 2, 10, 2, 22, 2, 2, 4, 6, 2, 2, 2, 2, 2, 14, 3, 61, 2, 10, 2, 14, 2, 15, 25, 11, 2, 5, 5, 2, 6, 30, 11, 24, 7, 7, 2, 5, 7, 19, 3, 2, 2, 3, 30, 2, 9, 46, 85, 2, 3, 3, 3, 11, 16, 59, 7, 2, 2, 22, 2, 21, 61, 41, 7, 2, 2, 8, 5, 2, 2, ... (sequence A085398 in OEIS)

(It is conjectured strongly that all the terms of this sequence are defined. However, some terms are very large, for example, the 545th term of this sequence is 2706, the 601st term of this sequence is 2061, and the 943rd term of this sequence is 2042.)

We need the first condition because if the leading coefficient is negative then $f(x) < 0$ for all large $x$, and thus $f(n)$ is not a prime number for large positive integers $n$. If we allow negative primes like -2, -3, -5, ... to count as prime numbers then this first condition can be dropped; the second and third necessary conditions are more substantial, as we will see below, since they imply $f(n)$ can be prime only finitely many times for reasons that are more serious than a sign problem.

We need the second condition because if $f(x) = g(x)h(x)$ where the polynomials $g(x)$ and $h(x)$ have integral coefficients and are not $\pm 1$ then we have $f(n) = g(n)h(n)$ for all integers $n$, so $f(n)$ is composite for all large $n$ (because $g(x)$ and $h(x)$ take the values 0 and $\pm 1$ only finitely many times).

The third condition, that the numbers $f(n)$ have gcd 1, is the most technical sounding and is best understood by an example where it does not hold. Consider the polynomial $f(x) = x^2 + x + 2$. It has a positive leading coefficient and is irreducible, but $f(n)$ is even for all integers $n$, so the values of this polynomial are prime only finitely many times on the positive integers (namely when it takes the value 2, which is actually only at $n = 1$ among positive integers).

In practice, the easiest way to verify the third condition for a polynomial $f(x)$ is to find one pair of positive integers $m$ and $n$ such that $f(m)$ and $f(n)$ are relatively prime: when this happens no integer greater than 1 can divide all values of $f(x)$ on the positive integers because it would have to divide $f(m)$ and $f(n)$.

An example of Bunyakovsky's conjecture is the polynomial f(x) = x² + 1, for which some of the prime values that it has on positive integers are listed below. (sequence A005574 (x) and A002496 (x² + 1) in OEIS)

x	1	2	4	6	10	14	16	20	24	26	36	40	54	56	66	74	84	90	94	110	116	120
x^2 + 1	2	5	17	37	101	197	257	401	577	677	1297	1601	2917	3137	4357	5477	7057	8101	8837	12101	13457	14401

That $n^2+1$ should be prime infinitely often is a problem first raised by Euler, and it is also the fifth Hardy–Littlewood conjecture and the fourth of Landau's problems.

The third condition in Bunyakovsky's conjecture is saying that the set of integers $f(1),f(2), f(3),\dots$ has gcd 1. It is a surprise to most people at first that this is not the same as saying the coefficients of $f(x)$ are relatively prime together, but the example of $x^2 - x + 2$ shows this. If the third condition in Bunyakovsky's conjecture holds then necessarily the coefficients of the polynomial are relatively prime (in fact, if the second condition holds then also the coefficients are relatively prime, since a common factor of the coefficients that is greater than 1 would mean the polynomial is reducible over the integers), but the converse is not true.

As noted above, a practical way to prove the numbers $f(1),f(2), f(3),\dots$ have gcd 1 is to find a single pair of values that are relatively prime. A way of calculating the gcd of all the numbers $f(n)$ when $n \geq 1$, even in the case of this number being greater than 1, is to rewrite $f(x) = c_0 + c_1x + \cdots + c_dx^d$ as a linear combination of the binomial coefficient polynomials $\binom{x}{k}$: $f(x) = a_0 + a_1\binom{x}{1} + \cdots + a_d\binom{x}{d}$. If each $c_i$ is an integer then each $a_i$ is an integer and $\gcd\{f(n) : n \geq 1\} = \gcd(a_0,a_1,\dots,a_d).$ For example, $x^2 - x + 2 = 2\binom{x}{2} + 2$, and the coefficients in the second formula have gcd 2, which is related to the fact that $x^2 - x + 2$ has even values on the integers. Using this gcd formula it can be proved $\gcd\{f(n) : n \geq 1\}$ is 1 if and only if there is some pair of positive integers $m$ and $n$ such that $f(m)$ and $f(n)$ are relatively prime.

To date, the only case of Bunyakovsky's conjecture that has been proved is polynomials of degree 1. This is Dirichlet's theorem, which states that when $a$ and $m$ are relatively prime integers there are infinitely many prime numbers $p \equiv a \!\! \pmod m$. This is Bunyakovsky's conjecture for $f(x) = a + mx$ (or $a - mx$ if $m < 0$). The third necessary condition in Bunyakovsky's conjecture for a linear polynomial $mx + a$ is equivalent to $a$ and $m$ being relatively prime. No single case of Bunyakovsky's conjecture for degree greater than 1 is proved, although numerical evidence in higher degree is consistent with the conjecture.

Generalized Bunyakovsky conjecture

Given n polynomials, (n can be any natural number, when n = 1, this is the original conjecture of Bunyakovsky) that each satisfy all three conditions, and for any prime p there is an x such that the values of all n polynomials at x are not divisible by p (thus, the set of polynomials: {x, x + 2, x + 4} does not work since one of the values of the polynomials must be divisible by 3 for any x, and neither does the set {x, x² + 2} since one of the values of the polynomials must be divisible by 3 for any x.), then there are infinitely many positive integers x such that all values of these n polynomials at x are prime. For example, if this conjecture is true then there are infinitely many positive integers x such that x² + 1, 3x - 1, and x² + x + 41 are all prime. This conjecture includes as special cases the twin prime conjecture (when n = 2, and the two polynomials are x and x + 2) as well as the infinitude of prime quadruplets (when n = 4, and the four polynomials are x, x + 2, x + 6, and x + 8), sexy primes (when n = 2, and the two polynomials are x and x + 6), Sophie Germain primes (when n = 2, and the two polynomials are x and 2x + 1), and Polignac's conjecture (when n = 2, and the two polynomials are x and x + k, with k any even number). When all the polynomials have degree 1 this is Dickson's conjecture.

In fact, this conjecture is the same as the Generalized Dickson conjecture.

With an exception of Dirichlet's theorem (the set contains only one polynomial, and it has degree 1), even there is no other single case of set of polynomials in this conjecture having been proved, including {x² + 1}, {x, x + 2}, and {x, 2x + 1}.

See also

• Integer-valued polynomial
• Cohn's irreducibility criterion
• Schinzel's hypothesis H
• Bateman–Horn conjecture
• Hardy and Littlewood's conjecture F

References

• Ed Pegg, Jr., "Bouniakowsky conjecture", MathWorld.
• Rupert, Wolfgang M. (1998-08-05). "Reducibility of polynomials f(x, y) modulo p". arXiv:math/9808021 [math.NT].
• Bouniakowsky, V. (1857). "Nouveaux théorèmes relatifs à la distinction des nombres premiers et à la décomposition des entiers en facteurs". Mém. Acad. Sc. St. Pétersbourg 6: 305–329.