Early and exclusive videos for Channel Members, consider joining to help support the yapfest! ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin More math chats: ruclips.net/p/PLztBpqftvzxXQDmPmSOwXSU9vOHgty1RO
Shouldn't you state, obvious though it may seem, "non-constant polynomials"? Since f(x) = 2 always generates a prime number; and such exceptions can mess up the logic of seemingly bullet proof proofs.
f(x) = 2 doesn’t generate prime number*s*; it returns a single prime number, and one that was already known prior to setting up the formula (and which is thus, not “generated” by the formula).
Neglecting to include some trivial qualifier is only a problem on math exams, not real math. There’s no problem with the actual logic of the proof, and it’s clearly demonstrating an interesting result. I actually think it’s clever to skip the qualifier, because it saves a couple seconds and you can delegate that part to the inevitable nitpickers in the comments. It’s like an automatically generated footnote.
@@matta5749neglecting to account for trivial cases invalidates the proof. it is critical to be precise in real math, much more important than on a math exam. i have a feeling you have never done any actual real math
i mean yeah if you trivially set the function equal to a prime constant i guess it won't change _but why would you do that? why would you do any of that?_
Doesn’t this proof only work assuming the polynomial has integer coefficients? I mean it is possible, though a bit subtle, for the polynomial to have rational coefficients, yet still produce integers. Ex: Triangular T(n)=1/2*n^2+1/2*n. This would invalidate some step where we factor p+p*stuff. The stuff could actually be a rational number with a factor of p in the denominator
You can extend it to include rational coefficients, since if you take the lcm of the coefficients’ denominators, let’s call it k, and multiply your prime generating polynomial f(x) by k, you get a polynomial g(x)=kf(x) that generates prime numbers multiplied by k and has integer coefficients. So you do the same thing and prove that g(b+mkp) is kp(1+stuff). Now divide both sides by k to get f(b+mkp) = p(1+stuff), which is not prime.
@@jonathangrube1183 true, but for some values, you won’t get an integer as a result. Ex: f(3)=1.5 since it’s not an integer, it can’t possibly be a prime polynomial
6:50 before you start, my conjecture is that if you pick the lowest common multiple of all numbers up to n it will cancel crap out a lot and evventually give x to the power of smth that isn't prime
Since the Putnam-Davis-Robinson-Matiyasevic theorem, we do have (multivariate) polynomials who positive values are all prime. This does not diminish the value of this video, which gives a very elegant proof that polynomials cannot generate primes and *only* primes.
This result can be extended even for multivariate polynomials, though the proof is of course much more complicated. But a polynomial can still generate prime numbers for the appropriate meaning of "generate." A polynomial can't _only_ have prime values, but it can have every prime value. In fact, Ribenboim's polynomial in 10 variables not only takes on every prime value, but _every_ positive value of the polynomial is prime. It just also has nonpositive values. And that result can probably be improved.
It is actually easy. It follows directly from this proof. Let f=f(x_1, ..., x_n) be such a polynomial. Fix any a_2, ..., a_n and set g(x) = f(x, a_2, ..., a_n). Then g(x) must be costant, so f has only on n-1 variables. By induction, f is constant
@@mokshnihalani1679 I gave the wrong name, sorry. It's Yuri Matiyasevich, which figures. The polynomial has degree 1.6 × 10⁴⁵, and the article is written in Russian, so idk much about it, except that it's listedi n Ribenboim's book. Jones, Sato, Wada, and Wiens discovered a qunitic polynomial in 42 variables that does the same thing, as well as a degree-25 polynomial in 26 variables in the paper "Diophantine representation of the set of prime numbers," which is available on ResearchGate for free.
No, this is FALSE for multivariate polynomials. In fact, a set S of natural numbers can be attained as the set of positive output values of some multivariate polynomial if and only if S is a "computably enumerable" set [formerly called "recursively enumerable"] -- that is, the elements of S can be listed out by a computer program. This is a consequence of the (negative) solution to Hilbert's 10th problem, which was proved by showing the (positive) result that every computably enumerable set is "Diophantine" --- that is, the set of (first coordinates of) solutions of a system of polynomial equations. For a good exposition of Hilbert's Tenth Problem, I recommend Martin Davis's paper "Hilbert's Tenth Problem is Unsolvable". If you want to see how this works for the prime numbers, Google "DIOPHANTINE REPRESENTATION OF THE SET OF PRIME NUMBERS" to find a paper by JAMES P. JONES, DAIHACHIRO SATO, HIDEO WADA AND DOUGLAS WIENS that produces a 25th degree polynomial in 26 variables that generates the set of prime numbers.
It’s an elegant proof, but wouldn’t it be much simpler to just evaluate f(x) at x=a0, which then gives a factor of a0 in all cases where a0 is not 0 and a factor of x in all cases where a0 is 0?
Yes this is what I thought of immediately while watching. I was surprised it wasn’t the proof used. It’s a bit more complex though: Assume f(n) is always prime. Note that a0 must be prime because f(0) = a0. And f(k*a0) is obviously divisible by a0 for all k. Since f is always prime this means f(k*a0) = a0 for all k. Which means f(n) = a0, ie it the constant function. Hence the only such polynomials are constant.
The proof seems to be valid only for a finite polynomial. An infinite polynomial would still work. Which is perhaps kind of obvious. But what is the convergence of the optimal prime number generator? Eg how many terms are needed in the polynomial to produce 1000 primes.
An infinite polynomial is not a polynomial, it is a power series. Edit: Actually not quite, I'm wrong. The prime counting function approximation is not representable with a power series (though maybe it's still possible?) I'm pretty sure there exists a power series for the inverse of the prime counting function (which would be the nth prime function, and thus all values of the function is prime). I suspect this because there's a power series that converges to the prime counting function which uses the zeros of the Riemann zeta function. I imagine there's some way to invert it, to make a power series that """"""generates"""""" all primes.
@@minerscale”An infinite polynomial is not a polynomial, it is a power series.” You aren’t wrong at all. One natural way to define a power series is a sequence of real numbers (or elements of a ring for that matter). In which case, a polynomial is merely a power series that is nonzero for only finitely many entries.
On a tangent, following up on the example polynomial f(x) which produces 40 prime numbers for x from 1 to 40, in fact you can in principle construct a polynomial that passes through any given finite set of points. So for example, if you have a finite set of n points (1,2) , (2,3), (3,5), (4,7), etc, where for x=k you have the kth prime, then you can construct a polynomial which passes through all those points and thus get a polynomial which generates the first n primes by plugging in x from 1 to n. (To see a method for constructing such a polynomial, look up Lagrange interpolating polynomials which are the unique polynomials of lowest degree that pass through a given set of points.)
Whoaa! I never realized you can do this with Lagrange interpolation. Question, as you increase k ( you get higher and higher order polynomials that generate up to the kth prime) do the polynomials converge to a certain infinite polynomial? As in, there exists a power series that passes through all the primes?
Cool! I was just thinking that even if you can’t generate an infinite set of primes with a polynomial, you should in principle be able to create one for any arbitrarily large finite set of primes.
P.S. In case anybody is curious, the Langrange interpolating polynomial that generates the first four primes is: -(1/6)x³ + (3/2)x² - (7/3)x + 3 If you plug in x=1,2,3, and 4 above you'll get 2,3,5, and 7 respectively. And in general the Langrange interpolating polynomial that consecutively generates the first n primes will be of degree n-1.
@@quantumgaming9180 Not really in any meaningful manner. Like, you can take g_p as the product of (x-q) for q prime not equal to p, and consider f as the sum over primes of p*g_p/g_p(p), and technically (of course, you need to do this rigorously. Really, you're working in the extended reals with formal power series) it will equal p at any prime, but at any other point, it's not properly defined (there's not an even or odd amount of primes, so your sum is not zero, but also neither positive or negative). You also can't do any p-adic things as your working over all the primes, so you just end up with your sum "ignoring" whatever p you p-adic evaluation is at.
i think a more interesting question is: even if a polynomial can’t generate primes forever, they can still generate an infinite amount of them (f(x)=x is a valid albeit boring polynomial which generates every prime number eventually), like the mersenne numbers are believed to. is it possible for a polynomial to generate primes more frequently than those functions?
Alternate proof: Assume f(n) is always prime. Then a0 must be prime because f(0) = a0. And f(k*a0) is obviously divisible by a0 for all k. Since f is always prime this means f(k*a0) = a0 for all k. Which means f(n) = a0, ie it the constant function. Hence the only such polynomials are constant.
@@sensei9767 You can note that by a translation, you can assume f(0) is prime. If f is prime for all integers k>=N, then f(n+N) is a polynomial that is prime for every n+N>=N or n>=0. If you stipulate positive primes (ring-theoretically, we say -2,-3,-5, etc. are also prime/irreducible), then this proof works.
You said a polynomial with real coefficients. But i suspect that it should be a polynomial with rational coefficients, as the irrational coefficients could not generate integers with integer inputs of x, lest so prime integers.
Mersenne primes are prime numbers which are one less than a power of 2, which is what I said. It just so happens that the only powers of 2 for which this happens are prime powers, but that doesn't contradict what I said.
@WrathofMath huh... I want to say thanks for the rectification, but I guess the definition could be either if it necessarily has to be a prime? So I guess instead I'll say sorry for being so unjustifiably aggressive in my "correction".
@@AbelShields Yes that's right, either definition would describe the same set of numbers. The fact that n will be prime for each Mersenne prime is a good thing to know - but I just didn't bother mentioning it as the Mersenne primes are not really an important part of this video.
@@WrathofMath Similarly, you could also define the Fermat primes as primes of the form 2^n + 1. It just turns out that if this is prime then n must be a power of 2.
it seems we can't have a polynomial that generates infinitely many primes, but a more interesting question is: is there a simple method of generating a polynomial that generates up to n primes? how does one casually come up with f(x) = x^2-x+41? if the method for creating these functions is generalizable we could maybe have something useful?
What you're looking for is the Lagrange interpolation polynomial. It gives the lowest degree polynomial that passes through a given set of points in the plane, so consider the Lagrange polynomial for the set { (1, p_1), (2, p_2), ..., (n, p_n) }. This only works for a finite set of points tho.
The real question then becomes, do polynomials exist that can output arbitrarily large amounts of primes. Obviously, constructing such polynomials, if they exist, would almost certainly be orders of magnitude more difficult than simply finding a prine generating function. But it feels like proving whether they exist or not would be attainable.
What if the stuff are in the form of k/p then p(1+stuff)=p+k such that p+k is always prime for some polynomial Or are we assuming that a_i is an integer for 0
No, there are easy counterexamples like f(x)=x, the image of every prime is prime. But this video establishes that a polynomial can't output ONLY primes for integer inputs.
An other missing detail (but not a difficult one to handle) is that the [stuff] could be equal to -2. Then, again, you would end up with the equivalent prime -p. Of course, this could only happen n times, so you have no more than 2n values of m (including 0) which produce prime numbers.
This proof only holds for a finite polynomial right? For an infinite polynomial the ‘stuff’ could equal -1 or 0 for all ‘m’, so the function could spit out primes infinitely.
Polynomials are defined to be finite. If we consider power series, “infinite polynomials”, then we are working with much a more general set of functions, so who knows. However, we would also need to worry about the domain of convergence. It would be amazing if there were a function which produced a unique prime number for each integer, even if the function isn’t algebraic.
@@27FoldandLumm There are plenty such functions if you let go of the polynomial requirement. Like the function f(x) that returns the nth prime if x = n is an integer. Duh. (And different formulas exist that achieve this less trivially; see Willan's formula for instance.)
I originally had “continuous function that generates unique primes”. I wasn’t sure if that was what I really wanted to say or the relevant way of extending from polynomials. Still not sure what that would be but it’s fun to think about.
The proof is good, but I thought it was kinda misleading. Like I don't think that a series needs to have all of its constituents be prime to be considered a prime generator. That isn't the case for the Mersenne primes. I'm curious about a proof whenever like for any given polynomial p, if there exists some x_0 for which all x higher than x_0, p(x) is never prime. I'd say that's a more interesting question & more informative on whenever you've got yourself a prime generator.
I feel like in order to get a prime number generator we'd need to do something different to the integer we add to a polynomial so that it isn't fixed, and that way the overall function may avoid hitting a composite every so often. I realise you can't vary the integer in a way that directly relates to the variable (Say 'n'), for example adding 'one more than n' or 'seven less than n' or 'one more than three lots of n' or whatever, as that will just cancel down into a very slightly different polynomial. My idea is that the integer added could be the nth prime number, which brings some psuedo-randomness to what gets added, whilst still using n to decide what the added integer should be for each step. I tried (n*n) + n + the nth prime, and it worked for the first seven terms. I can't help wondering if tweaking the degree of that type of expression, the individual exponents, and/or exactly which prime is being added (eg. 'n-2'th prime or 'n+1'th prime etc) might yield a prime number generator somewhere along the lines. Of course for it to be any use you'd probably want it to only use for input those primes that had already been found earlier by the same function, and ideally if it could find all of the primes that would be truly something.
@@YunxiaoChu If you are implying that you disagree with me then give me some constructive criticism to work with. Or was that just a sigh of pleasure at reading an interesting mathematical hypothesis?
@@polygonc4538Yes, But this same problem happens in the video solution, if "stuff"=1 The case of f(a0) is a particular case of b=0 and m=1. To correct this, we can say that f(x)-a0 has at most n roots*, then there exists m such that f(ma0) ≠ a0. *Considering that n≥1
I already knew that polinomial that generates primes up to f(40) so my mind instantly tried to prove this case by case on a_0. If |a_0| > 1, then a_0 is clearly a factor. If a_0 = 0, then you can factor out x. I wonder if there is a simple enough argument for |a_0| = 1
Early and exclusive videos for Channel Members, consider joining to help support the yapfest!
ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin
More math chats: ruclips.net/p/PLztBpqftvzxXQDmPmSOwXSU9vOHgty1RO
Shouldn't you state, obvious though it may seem, "non-constant polynomials"? Since f(x) = 2 always generates a prime number; and such exceptions can mess up the logic of seemingly bullet proof proofs.
f(x) = 2 doesn’t generate prime number*s*; it returns a single prime number, and one that was already known prior to setting up the formula (and which is thus, not “generated” by the formula).
Neglecting to include some trivial qualifier is only a problem on math exams, not real math. There’s no problem with the actual logic of the proof, and it’s clearly demonstrating an interesting result. I actually think it’s clever to skip the qualifier, because it saves a couple seconds and you can delegate that part to the inevitable nitpickers in the comments. It’s like an automatically generated footnote.
That's a monomial
@@nagisa5848which is a type of polynomial
@@matta5749neglecting to account for trivial cases invalidates the proof. it is critical to be precise in real math, much more important than on a math exam.
i have a feeling you have never done any actual real math
y=0x+3
i mean yeah if you trivially set the function equal to a prime constant i guess it won't change
_but why would you do that? why would you do any of that?_
@@matthewbertrand4139this was to show that he made a mistake in his proof. otherwise he would have caught this exception.
ok but that is not a polynomial
highest degree of x has a coefficient of zero so it's not a polynomial
@QwertzIsTired y=c is a constant function
I did it boys. I found such polinomial: f(x) = 0x + 7
Wow this such a elegant proof I’ve only seen much harder proofs thanks for this
no
I feel like he could have made it a lot simpler by just setting b=0.
@@globalincident694 YouFeeAreIrr
Can’t you just evaluate at a_0 for a contradiction?
I discovered this channel today and already in love with it. This is my first video of this channel abd hopeful for all the rest too.
Thank you!
Doesn’t this proof only work assuming the polynomial has integer coefficients? I mean it is possible, though a bit subtle, for the polynomial to have rational coefficients, yet still produce integers. Ex: Triangular T(n)=1/2*n^2+1/2*n. This would invalidate some step where we factor p+p*stuff. The stuff could actually be a rational number with a factor of p in the denominator
On second thought, maybe this could be fixed if the polynomial is written with binomial coefficients like a*(n choose 3)+b*(n choose 2) +c*n+d
You can extend it to include rational coefficients, since if you take the lcm of the coefficients’ denominators, let’s call it k, and multiply your prime generating polynomial f(x) by k, you get a polynomial g(x)=kf(x) that generates prime numbers multiplied by k and has integer coefficients. So you do the same thing and prove that g(b+mkp) is kp(1+stuff). Now divide both sides by k to get f(b+mkp) = p(1+stuff), which is not prime.
Yeah isn't f(x) = x/2 a counter example since f(4) = 2 but f(6) is not a multiple of 2, i.e. take b = 4, p = 2 and m = 1 from the proof
@@jonathangrube1183 true, but for some values, you won’t get an integer as a result. Ex: f(3)=1.5 since it’s not an integer, it can’t possibly be a prime polynomial
@@pokemonjourneysfan5925 ah I see. Was only taking integer values part of the definition of this poly? I missed it then
6:50 before you start, my conjecture is that if you pick the lowest common multiple of all numbers up to n it will cancel crap out a lot and evventually give x to the power of smth that isn't prime
Since the Putnam-Davis-Robinson-Matiyasevic theorem, we do have (multivariate) polynomials who positive values are all prime. This does not diminish the value of this video, which gives a very elegant proof that polynomials cannot generate primes and *only* primes.
This result can be extended even for multivariate polynomials, though the proof is of course much more complicated.
But a polynomial can still generate prime numbers for the appropriate meaning of "generate." A polynomial can't _only_ have prime values, but it can have every prime value. In fact, Ribenboim's polynomial in 10 variables not only takes on every prime value, but _every_ positive value of the polynomial is prime. It just also has nonpositive values. And that result can probably be improved.
f(x) = x can generate all the primes. We just have to filter through the range of f to find them.
could you cite a source for this polynomial? I couldn't find anything for it online.
It is actually easy. It follows directly from this proof. Let f=f(x_1, ..., x_n) be such a polynomial. Fix any a_2, ..., a_n and set g(x) = f(x, a_2, ..., a_n). Then g(x) must be costant, so f has only on n-1 variables. By induction, f is constant
@@mokshnihalani1679 I gave the wrong name, sorry. It's Yuri Matiyasevich, which figures. The polynomial has degree 1.6 × 10⁴⁵, and the article is written in Russian, so idk much about it, except that it's listedi n Ribenboim's book. Jones, Sato, Wada, and Wiens discovered a qunitic polynomial in 42 variables that does the same thing, as well as a degree-25 polynomial in 26 variables in the paper "Diophantine representation of the set of prime numbers," which is available on ResearchGate for free.
No, this is FALSE for multivariate polynomials. In fact, a set S of natural numbers can be attained as the set of positive output values of some multivariate polynomial if and only if S is a "computably enumerable" set [formerly called "recursively enumerable"] -- that is, the elements of S can be listed out by a computer program.
This is a consequence of the (negative) solution to Hilbert's 10th problem, which was proved by showing the (positive) result that every computably enumerable set is "Diophantine" --- that is, the set of (first coordinates of) solutions of a system of polynomial equations.
For a good exposition of Hilbert's Tenth Problem, I recommend Martin Davis's paper "Hilbert's Tenth Problem is Unsolvable".
If you want to see how this works for the prime numbers, Google "DIOPHANTINE REPRESENTATION OF THE SET OF PRIME NUMBERS" to find a paper by JAMES P. JONES, DAIHACHIRO SATO, HIDEO WADA AND DOUGLAS WIENS that produces a 25th degree polynomial in 26 variables that generates the set of prime numbers.
It’s an elegant proof, but wouldn’t it be much simpler to just evaluate f(x) at x=a0, which then gives a factor of a0 in all cases where a0 is not 0 and a factor of x in all cases where a0 is 0?
You have to account for f(a0) = a0 where a0 is prime
What if a0 = +-1?
Yes this is what I thought of immediately while watching. I was surprised it wasn’t the proof used.
It’s a bit more complex though: Assume f(n) is always prime. Note that a0 must be prime because f(0) = a0. And f(k*a0) is obviously divisible by a0 for all k. Since f is always prime this means f(k*a0) = a0 for all k. Which means f(n) = a0, ie it the constant function. Hence the only such polynomials are constant.
The proof seems to be valid only for a finite polynomial. An infinite polynomial would still work. Which is perhaps kind of obvious. But what is the convergence of the optimal prime number generator? Eg how many terms are needed in the polynomial to produce 1000 primes.
An infinite polynomial is not a polynomial, it is a power series.
Edit: Actually not quite, I'm wrong. The prime counting function approximation is not representable with a power series (though maybe it's still possible?)
I'm pretty sure there exists a power series for the inverse of the prime counting function (which would be the nth prime function, and thus all values of the function is prime). I suspect this because there's a power series that converges to the prime counting function which uses the zeros of the Riemann zeta function. I imagine there's some way to invert it, to make a power series that """"""generates"""""" all primes.
@@minerscale”An infinite polynomial is not a polynomial, it is a power series.”
You aren’t wrong at all.
One natural way to define a power series is a sequence of real numbers (or elements of a ring for that matter). In which case, a polynomial is merely a power series that is nonzero for only finitely many entries.
On a tangent, following up on the example polynomial f(x) which produces 40 prime numbers for x from 1 to 40, in fact you can in principle construct a polynomial that passes through any given finite set of points. So for example, if you have a finite set of n points (1,2) , (2,3), (3,5), (4,7), etc, where for x=k you have the kth prime, then you can construct a polynomial which passes through all those points and thus get a polynomial which generates the first n primes by plugging in x from 1 to n. (To see a method for constructing such a polynomial, look up Lagrange interpolating polynomials which are the unique polynomials of lowest degree that pass through a given set of points.)
Whoaa! I never realized you can do this with Lagrange interpolation. Question, as you increase k ( you get higher and higher order polynomials that generate up to the kth prime) do the polynomials converge to a certain infinite polynomial? As in, there exists a power series that passes through all the primes?
Cool! I was just thinking that even if you can’t generate an infinite set of primes with a polynomial, you should in principle be able to create one for any arbitrarily large finite set of primes.
P.S. In case anybody is curious, the Langrange interpolating polynomial that generates the first four primes is:
-(1/6)x³ + (3/2)x² - (7/3)x + 3
If you plug in x=1,2,3, and 4 above you'll get 2,3,5, and 7 respectively.
And in general the Langrange interpolating polynomial that consecutively generates the first n primes will be of degree n-1.
@@quantumgaming9180 Not really in any meaningful manner. Like, you can take g_p as the product of (x-q) for q prime not equal to p, and consider f as the sum over primes of p*g_p/g_p(p), and technically (of course, you need to do this rigorously. Really, you're working in the extended reals with formal power series) it will equal p at any prime, but at any other point, it's not properly defined (there's not an even or odd amount of primes, so your sum is not zero, but also neither positive or negative). You also can't do any p-adic things as your working over all the primes, so you just end up with your sum "ignoring" whatever p you p-adic evaluation is at.
May I say, "very nice proof". Easy to understand.
Thank you!
i think a more interesting question is: even if a polynomial can’t generate primes forever, they can still generate an infinite amount of them (f(x)=x is a valid albeit boring polynomial which generates every prime number eventually), like the mersenne numbers are believed to. is it possible for a polynomial to generate primes more frequently than those functions?
see the bateman-horn conjecture
Alternate proof: Assume f(n) is always prime. Then a0 must be prime because f(0) = a0. And f(k*a0) is obviously divisible by a0 for all k. Since f is always prime this means f(k*a0) = a0 for all k. Which means f(n) = a0, ie it the constant function. Hence the only such polynomials are constant.
f(0) doesn't have to be prime, since 0 is not a natural number
@@sensei9767 You can note that by a translation, you can assume f(0) is prime. If f is prime for all integers k>=N, then f(n+N) is a polynomial that is prime for every n+N>=N or n>=0. If you stipulate positive primes (ring-theoretically, we say -2,-3,-5, etc. are also prime/irreducible), then this proof works.
You said a polynomial with real coefficients. But i suspect that it should be a polynomial with rational coefficients, as the irrational coefficients could not generate integers with integer inputs of x, lest so prime integers.
Very nice proof. You are a good teacher
Thank you!
Finally someone is asking the right questions
what about a power series? Your proof relies on the FTA so if it were a power series then it could output the same number an infinite number of times?
What about a degree 0 polynomial? for example f(x) = 7
That's the one exception!
0:52 mersenne primes are actually 2^p -1, where p is a prime number.
Mersenne primes are prime numbers which are one less than a power of 2, which is what I said. It just so happens that the only powers of 2 for which this happens are prime powers, but that doesn't contradict what I said.
@WrathofMath huh... I want to say thanks for the rectification, but I guess the definition could be either if it necessarily has to be a prime? So I guess instead I'll say sorry for being so unjustifiably aggressive in my "correction".
@@AbelShields Yes that's right, either definition would describe the same set of numbers. The fact that n will be prime for each Mersenne prime is a good thing to know - but I just didn't bother mentioning it as the Mersenne primes are not really an important part of this video.
@@WrathofMath Similarly, you could also define the Fermat primes as primes of the form 2^n + 1. It just turns out that if this is prime then n must be a power of 2.
it seems we can't have a polynomial that generates infinitely many primes, but a more interesting question is: is there a simple method of generating a polynomial that generates up to n primes? how does one casually come up with f(x) = x^2-x+41? if the method for creating these functions is generalizable we could maybe have something useful?
What you're looking for is the Lagrange interpolation polynomial. It gives the lowest degree polynomial that passes through a given set of points in the plane, so consider the Lagrange polynomial for the set { (1, p_1), (2, p_2), ..., (n, p_n) }. This only works for a finite set of points tho.
The real question then becomes, do polynomials exist that can output arbitrarily large amounts of primes. Obviously, constructing such polynomials, if they exist, would almost certainly be orders of magnitude more difficult than simply finding a prine generating function. But it feels like proving whether they exist or not would be attainable.
Can you make a similar argument by substituting N*A0 into the polynomial?
ao < 0 ?
I also think that the arbitrariness of b is unnecessary
@@derekcouzens9483 Then the polynomial is not a prime at x=0
What if the stuff are in the form of k/p then p(1+stuff)=p+k such that p+k is always prime for some polynomial
Or are we assuming that a_i is an integer for 0
is this true that the image of integer under every polynomial has a finite number of primes?
No, there are easy counterexamples like f(x)=x, the image of every prime is prime. But this video establishes that a polynomial can't output ONLY primes for integer inputs.
An other missing detail (but not a difficult one to handle) is that the [stuff] could be equal to -2. Then, again, you would end up with the equivalent prime -p. Of course, this could only happen n times, so you have no more than 2n values of m (including 0) which produce prime numbers.
Very elegant proof. Almost as elegant as the existence of infinite primes.
It's not the only way to genrate numbers out of a polynomial. First, doing an operation and then setting to a value.
This proof only holds for a finite polynomial right? For an infinite polynomial the ‘stuff’ could equal -1 or 0 for all ‘m’, so the function could spit out primes infinitely.
Polynomials are defined to be finite. If we consider power series, “infinite polynomials”, then we are working with much a more general set of functions, so who knows. However, we would also need to worry about the domain of convergence. It would be amazing if there were a function which produced a unique prime number for each integer, even if the function isn’t algebraic.
@@27FoldandLumm There are plenty such functions if you let go of the polynomial requirement. Like the function f(x) that returns the nth prime if x = n is an integer. Duh. (And different formulas exist that achieve this less trivially; see Willan's formula for instance.)
I originally had “continuous function that generates unique primes”. I wasn’t sure if that was what I really wanted to say or the relevant way of extending from polynomials. Still not sure what that would be but it’s fun to think about.
what about riemann zeta function?
If P(n)=k is prime then P(n+km) is divisible by k
P(n+km)=P(n) mod k , P(n)=0 mod k so P(n+km)=0 mod k.
my favorite prime generating function is f(x) = 3
wouldn't an easier proof just to be to calculate f(a0)?
Now let's change the function so that we apply the floor operation on the (real-value) result of the polynomial to get the integer.
The proof is good, but I thought it was kinda misleading.
Like I don't think that a series needs to have all of its constituents be prime to be considered a prime generator. That isn't the case for the Mersenne primes.
I'm curious about a proof whenever like for any given polynomial p, if there exists some x_0 for which all x higher than x_0, p(x) is never prime.
I'd say that's a more interesting question & more informative on whenever you've got yourself a prime generator.
"whenever like for any given polynomial p, if there exists some x_0 for which all x higher than x_0, p(x) is never prime"
A counterexample is p(x) = x
I feel like in order to get a prime number generator we'd need to do something different to the integer we add to a polynomial so that it isn't fixed, and that way the overall function may avoid hitting a composite every so often. I realise you can't vary the integer in a way that directly relates to the variable (Say 'n'), for example adding 'one more than n' or 'seven less than n' or 'one more than three lots of n' or whatever, as that will just cancel down into a very slightly different polynomial. My idea is that the integer added could be the nth prime number, which brings some psuedo-randomness to what gets added, whilst still using n to decide what the added integer should be for each step. I tried (n*n) + n + the nth prime, and it worked for the first seven terms. I can't help wondering if tweaking the degree of that type of expression, the individual exponents, and/or exactly which prime is being added (eg. 'n-2'th prime or 'n+1'th prime etc) might yield a prime number generator somewhere along the lines. Of course for it to be any use you'd probably want it to only use for input those primes that had already been found earlier by the same function, and ideally if it could find all of the primes that would be truly something.
Hmm
@@YunxiaoChu If you are implying that you disagree with me then give me some constructive criticism to work with.
Or was that just a sigh of pleasure at reading an interesting mathematical hypothesis?
@@MrDannyDetail just find it interesting
@@YunxiaoChu Oh fair enough. I guess I'm just slightly worried that I may have overlooked some obvious reason why my idea wouldn't work.
Nice proof and love the Nintendo music in the background!
Thank you!
this is such a perfect clickbait bc i definitely thought he was implying P ≠ NP at a glance
x^0+1.
Literally cannot refute this.
f(x) = 1 + 2x + 3x²/2! + 5x³/3! + ...
d^n/dx^n f(0) = p_n
Well duh, just take P(x) = 1 + (p_1)x +(p_2)x² + … where p_i is the ith prime.
f(x)=2
Another prime number vid, perfect for taking break between studies lol.
1:05 hear me out, hear me out: probabilistic theorem, lucas lehmer
y=2 would work
Yeah, constant functions are the only exception
7:38, what an excessively convoluted proof. f(a_0) is clearly a multiple of a_0, proof complete
But what if a_0 is prime and f(a_0) = a_0*1? For example: f(x) = 3 - 3x + x^2. Then f(3) = 3-3*3+3^2 = 3-9+9 = 3 = 3*1.
or a_0 is 1. f(x) = 1 + x, f(1) = 2
@@stormy4171f(0)=1 not prime
@@polygonc4538Yes, But this same problem happens in the video solution, if "stuff"=1
The case of f(a0) is a particular case of b=0 and m=1.
To correct this, we can say that f(x)-a0 has at most n roots*, then there exists m such that f(ma0) ≠ a0.
*Considering that n≥1
*non-constant polynomials
yes
I already knew that polinomial that generates primes up to f(40) so my mind instantly tried to prove this case by case on a_0.
If |a_0| > 1, then a_0 is clearly a factor. If a_0 = 0, then you can factor out x.
I wonder if there is a simple enough argument for |a_0| = 1
Not with that attitude
too confusing
Which part?
@Fire_Axus
For you, maybe.