Degree of polynomial interpolating the primes











up vote
10
down vote

favorite
3












The polynomial $p_3(x)$ passes through the points
$(1,2), (2,3), (3,5)$, where $2,3,5$ are the first three primes:
$$
p_3(x) = frac{x^2}{2}-frac{x}{2}+2 ;.
$$

Similarly, one can form an interpolating polynomial $p_n(x)$ that
passes through the first $n$ primes.
For example:
$$
p_5(x) = frac{x^4}{8}-frac{17
x^3}{12}+frac{47
x^2}{8}-frac{103 x}{12}+6 ;.
$$

One can check that
begin{eqnarray}
p_5(1) &=& 2 \
p_5(2) &=& 3 \
p_5(3) &=& 5 \
p_5(4) &=& 7 \
p_5(5) &=& 11 ;.
end{eqnarray}



My question is:




Q. Is the degree of $p_n(x)$ ever strictly less than $n{-}1$, for any $n$?




The answer to Q is positive if a "coincidence" occurs,
such that a smaller degree
polynomial captures those $n$ prime points.
Do such coincidences ever occur?










share|cite|improve this question




















  • 1




    See also math.stackexchange.com/questions/577448/…
    – lhf
    Nov 22 at 18:00






  • 1




    It is for $nle 200$.
    – lhf
    Nov 22 at 18:32






  • 1




    The edit helps, but the question might be clearer still if it were phrased as "Is the degree of $p_n(x)$ ever strictly less than $n-1$ for any $n$?", in which case an affirmative answer would constitute a coincidence I know a few people (myself included) misunderstood the question at first.
    – mweiss
    Nov 25 at 1:25






  • 1




    @mweiss: Thanks, I followed your suggestion.
    – Joseph O'Rourke
    Nov 25 at 1:47






  • 1




    Interesting related fact, though probably not helpful towards an answer: The sum of the coefficients of $p_n(x)$ appears to converge. oeis.org/A092894
    – Steve Kass
    Nov 25 at 2:13















up vote
10
down vote

favorite
3












The polynomial $p_3(x)$ passes through the points
$(1,2), (2,3), (3,5)$, where $2,3,5$ are the first three primes:
$$
p_3(x) = frac{x^2}{2}-frac{x}{2}+2 ;.
$$

Similarly, one can form an interpolating polynomial $p_n(x)$ that
passes through the first $n$ primes.
For example:
$$
p_5(x) = frac{x^4}{8}-frac{17
x^3}{12}+frac{47
x^2}{8}-frac{103 x}{12}+6 ;.
$$

One can check that
begin{eqnarray}
p_5(1) &=& 2 \
p_5(2) &=& 3 \
p_5(3) &=& 5 \
p_5(4) &=& 7 \
p_5(5) &=& 11 ;.
end{eqnarray}



My question is:




Q. Is the degree of $p_n(x)$ ever strictly less than $n{-}1$, for any $n$?




The answer to Q is positive if a "coincidence" occurs,
such that a smaller degree
polynomial captures those $n$ prime points.
Do such coincidences ever occur?










share|cite|improve this question




















  • 1




    See also math.stackexchange.com/questions/577448/…
    – lhf
    Nov 22 at 18:00






  • 1




    It is for $nle 200$.
    – lhf
    Nov 22 at 18:32






  • 1




    The edit helps, but the question might be clearer still if it were phrased as "Is the degree of $p_n(x)$ ever strictly less than $n-1$ for any $n$?", in which case an affirmative answer would constitute a coincidence I know a few people (myself included) misunderstood the question at first.
    – mweiss
    Nov 25 at 1:25






  • 1




    @mweiss: Thanks, I followed your suggestion.
    – Joseph O'Rourke
    Nov 25 at 1:47






  • 1




    Interesting related fact, though probably not helpful towards an answer: The sum of the coefficients of $p_n(x)$ appears to converge. oeis.org/A092894
    – Steve Kass
    Nov 25 at 2:13













up vote
10
down vote

favorite
3









up vote
10
down vote

favorite
3






3





The polynomial $p_3(x)$ passes through the points
$(1,2), (2,3), (3,5)$, where $2,3,5$ are the first three primes:
$$
p_3(x) = frac{x^2}{2}-frac{x}{2}+2 ;.
$$

Similarly, one can form an interpolating polynomial $p_n(x)$ that
passes through the first $n$ primes.
For example:
$$
p_5(x) = frac{x^4}{8}-frac{17
x^3}{12}+frac{47
x^2}{8}-frac{103 x}{12}+6 ;.
$$

One can check that
begin{eqnarray}
p_5(1) &=& 2 \
p_5(2) &=& 3 \
p_5(3) &=& 5 \
p_5(4) &=& 7 \
p_5(5) &=& 11 ;.
end{eqnarray}



My question is:




Q. Is the degree of $p_n(x)$ ever strictly less than $n{-}1$, for any $n$?




The answer to Q is positive if a "coincidence" occurs,
such that a smaller degree
polynomial captures those $n$ prime points.
Do such coincidences ever occur?










share|cite|improve this question















The polynomial $p_3(x)$ passes through the points
$(1,2), (2,3), (3,5)$, where $2,3,5$ are the first three primes:
$$
p_3(x) = frac{x^2}{2}-frac{x}{2}+2 ;.
$$

Similarly, one can form an interpolating polynomial $p_n(x)$ that
passes through the first $n$ primes.
For example:
$$
p_5(x) = frac{x^4}{8}-frac{17
x^3}{12}+frac{47
x^2}{8}-frac{103 x}{12}+6 ;.
$$

One can check that
begin{eqnarray}
p_5(1) &=& 2 \
p_5(2) &=& 3 \
p_5(3) &=& 5 \
p_5(4) &=& 7 \
p_5(5) &=& 11 ;.
end{eqnarray}



My question is:




Q. Is the degree of $p_n(x)$ ever strictly less than $n{-}1$, for any $n$?




The answer to Q is positive if a "coincidence" occurs,
such that a smaller degree
polynomial captures those $n$ prime points.
Do such coincidences ever occur?







number-theory polynomials prime-numbers






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 25 at 1:46

























asked Nov 22 at 13:47









Joseph O'Rourke

17.6k348106




17.6k348106








  • 1




    See also math.stackexchange.com/questions/577448/…
    – lhf
    Nov 22 at 18:00






  • 1




    It is for $nle 200$.
    – lhf
    Nov 22 at 18:32






  • 1




    The edit helps, but the question might be clearer still if it were phrased as "Is the degree of $p_n(x)$ ever strictly less than $n-1$ for any $n$?", in which case an affirmative answer would constitute a coincidence I know a few people (myself included) misunderstood the question at first.
    – mweiss
    Nov 25 at 1:25






  • 1




    @mweiss: Thanks, I followed your suggestion.
    – Joseph O'Rourke
    Nov 25 at 1:47






  • 1




    Interesting related fact, though probably not helpful towards an answer: The sum of the coefficients of $p_n(x)$ appears to converge. oeis.org/A092894
    – Steve Kass
    Nov 25 at 2:13














  • 1




    See also math.stackexchange.com/questions/577448/…
    – lhf
    Nov 22 at 18:00






  • 1




    It is for $nle 200$.
    – lhf
    Nov 22 at 18:32






  • 1




    The edit helps, but the question might be clearer still if it were phrased as "Is the degree of $p_n(x)$ ever strictly less than $n-1$ for any $n$?", in which case an affirmative answer would constitute a coincidence I know a few people (myself included) misunderstood the question at first.
    – mweiss
    Nov 25 at 1:25






  • 1




    @mweiss: Thanks, I followed your suggestion.
    – Joseph O'Rourke
    Nov 25 at 1:47






  • 1




    Interesting related fact, though probably not helpful towards an answer: The sum of the coefficients of $p_n(x)$ appears to converge. oeis.org/A092894
    – Steve Kass
    Nov 25 at 2:13








1




1




See also math.stackexchange.com/questions/577448/…
– lhf
Nov 22 at 18:00




See also math.stackexchange.com/questions/577448/…
– lhf
Nov 22 at 18:00




1




1




It is for $nle 200$.
– lhf
Nov 22 at 18:32




It is for $nle 200$.
– lhf
Nov 22 at 18:32




1




1




The edit helps, but the question might be clearer still if it were phrased as "Is the degree of $p_n(x)$ ever strictly less than $n-1$ for any $n$?", in which case an affirmative answer would constitute a coincidence I know a few people (myself included) misunderstood the question at first.
– mweiss
Nov 25 at 1:25




The edit helps, but the question might be clearer still if it were phrased as "Is the degree of $p_n(x)$ ever strictly less than $n-1$ for any $n$?", in which case an affirmative answer would constitute a coincidence I know a few people (myself included) misunderstood the question at first.
– mweiss
Nov 25 at 1:25




1




1




@mweiss: Thanks, I followed your suggestion.
– Joseph O'Rourke
Nov 25 at 1:47




@mweiss: Thanks, I followed your suggestion.
– Joseph O'Rourke
Nov 25 at 1:47




1




1




Interesting related fact, though probably not helpful towards an answer: The sum of the coefficients of $p_n(x)$ appears to converge. oeis.org/A092894
– Steve Kass
Nov 25 at 2:13




Interesting related fact, though probably not helpful towards an answer: The sum of the coefficients of $p_n(x)$ appears to converge. oeis.org/A092894
– Steve Kass
Nov 25 at 2:13










3 Answers
3






active

oldest

votes

















up vote
5
down vote



accepted










The degree of $p_n(x)$ is always $n-1$. The proof is by induction.



Note that $p_1(x) = 2$ has degree $0$. Now assume that $p_{n}(x)$ has degree $n-1$. We want to prove that $p_{n+1}(x)$ has degree $n$. Assume otherwise, so $p_{n+1}(x)$ also had degree at most $n-1$. Then since $p_{n+1}(x)$ and $p_n(x)$ agree on the first $n$ values, it must be the case that $p_{n+1}(x) = p_n(x)$. In particular, to obtain a contradiction, it suffices to show that



$$p_n(n+1) ne^{?} p_{n+1}.$$



In fact, we simply will prove that $p_n(n+1)$ is always even which does the job.



We can write down a formula for $p_n(x)$, namely



$$p_n(x) = sum_{i=1}^{n} p_i cdot
frac{(x-1)(x-2) ldots widehat{(x-i)} ldots (x - n)}{(i-1)(i-2)
ldots widehat{(i-i)} ldots (i - n)},$$



where the hat indicates the term is omitted. This is clearly a polynomial of degree at most $n-1$ and $p_n(i) = p_i$. (This is the general formula for Lagrange interpolation specialized to this case.)



Hence



$$begin{aligned} p_n(n+1) = & sum_{i=1}^{n} p_i cdotfrac{ n!/(n+1-i)}{(i-1)! (n-i)! (-1)^{n-i}}\
= & (-1)^{n-1} sum_{i=1}^{n} p_i cdot frac{ n!}{(i-1)! (n+1-i)!} (-1)^{i-1} \
= & (-1)^{n-1} sum_{i=1}^{n} p_i cdot binom{n}{i-1} (-1)^{i-1}\
= & (-1)^{n-1} sum_{i=0}^{n-1} p_{i+1} binom{n}{i} (-1)^iend{aligned}$$



Now we use the fact that, with the exception of $p_1 = 2$, the primes are all odd. It follows that



$$p_{n}(n+1) equiv sum_{i=1}^{n-1} (-1)^i binom{n}{i} mod 2.$$



But now



$$sum_{i=1}^{n-1} (-1)^i binom{n}{i}
= (1-1)^n - 1 - (-1)^n equiv 0 mod 2,$$



is even for $n > 0$, and hence $p_{n}(n+1)$ is even, and thus $ne p_{n+1}$, as desired.






share|cite|improve this answer





















  • One can simplify this somewhat by noting that we don't need Lagrange interpolation; the method of forward differences is sufficient here and tells us that $n!$ times the coefficient of $x^{n-1}$ in $p_n$ is $sum_{i=0}^{n-1}(-1)^i{n-1choose i}cdot p_{i+1}$ which, similar to your argument, turns out to be odd, so not zero.
    – Milo Brandt
    Nov 25 at 19:01












  • wonderful proof
    – Sandeep Silwal
    Nov 25 at 21:03










  • There's nothing difficult about Lagrange interpolation --- it's an identity that proves itself. It would take longer to write out an argument using discrete derivatives and end up basically being the same, so I disagree it would be any simplification.
    – Lorem Ipsum
    Nov 25 at 21:49


















up vote
0
down vote













Not really an answer, but consider a more general question:




Does the polynomial interpolating $n$ consecutive primes $p_{m+1},dots,p_{m+n}$ always have maximum degree $n-1$?




The answer is a strong no because $3,5,7$ and $251,257,263,269$ are consecutive primes in arithmetic progression.
Small examples are known for $3 le n le 6$. See Wikipedia.



The polynomial interpolating the four consecutive primes $17, 19, 23, 29$ has degree $2$, not $3$. So does the polynomial interpolating the four consecutive primes $p_{m+1},dots,p_{m+4}$ for $m in {6,10,12,17,21,48,57,68,69,74,84,90,103,110,115,121,122,126,131,172,181}$.






share|cite|improve this answer























  • So what? You have answered negatively to a more general question. What about the particular case of $p_1,dots,p_n$?
    – Federico
    Nov 22 at 18:01


















up vote
-1
down vote













Yes. Given $n$ unique data points, there is a unique polynomial of degree $n-1$ that interpolates the data. This is one of the first results in the interpolation section of any numerical analysis/methods course. Using data points constructed with primes is a specific case of this. If you write out the interpolation conditions, you'll see that this is equivalent to solving an $n times n$ linear system.






share|cite|improve this answer

















  • 3




    It is possible that the coefficient(s) of the highest degree term(s) is/are $0$, which would mean that the degree could be less than $n-1$. Actually the standard result is: There is a unique polynomial of degree at most $n-1$ interpolating $n$ points with different $x$-coordinates.
    – paw88789
    Nov 22 at 14:45











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3009163%2fdegree-of-polynomial-interpolating-the-primes%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
5
down vote



accepted










The degree of $p_n(x)$ is always $n-1$. The proof is by induction.



Note that $p_1(x) = 2$ has degree $0$. Now assume that $p_{n}(x)$ has degree $n-1$. We want to prove that $p_{n+1}(x)$ has degree $n$. Assume otherwise, so $p_{n+1}(x)$ also had degree at most $n-1$. Then since $p_{n+1}(x)$ and $p_n(x)$ agree on the first $n$ values, it must be the case that $p_{n+1}(x) = p_n(x)$. In particular, to obtain a contradiction, it suffices to show that



$$p_n(n+1) ne^{?} p_{n+1}.$$



In fact, we simply will prove that $p_n(n+1)$ is always even which does the job.



We can write down a formula for $p_n(x)$, namely



$$p_n(x) = sum_{i=1}^{n} p_i cdot
frac{(x-1)(x-2) ldots widehat{(x-i)} ldots (x - n)}{(i-1)(i-2)
ldots widehat{(i-i)} ldots (i - n)},$$



where the hat indicates the term is omitted. This is clearly a polynomial of degree at most $n-1$ and $p_n(i) = p_i$. (This is the general formula for Lagrange interpolation specialized to this case.)



Hence



$$begin{aligned} p_n(n+1) = & sum_{i=1}^{n} p_i cdotfrac{ n!/(n+1-i)}{(i-1)! (n-i)! (-1)^{n-i}}\
= & (-1)^{n-1} sum_{i=1}^{n} p_i cdot frac{ n!}{(i-1)! (n+1-i)!} (-1)^{i-1} \
= & (-1)^{n-1} sum_{i=1}^{n} p_i cdot binom{n}{i-1} (-1)^{i-1}\
= & (-1)^{n-1} sum_{i=0}^{n-1} p_{i+1} binom{n}{i} (-1)^iend{aligned}$$



Now we use the fact that, with the exception of $p_1 = 2$, the primes are all odd. It follows that



$$p_{n}(n+1) equiv sum_{i=1}^{n-1} (-1)^i binom{n}{i} mod 2.$$



But now



$$sum_{i=1}^{n-1} (-1)^i binom{n}{i}
= (1-1)^n - 1 - (-1)^n equiv 0 mod 2,$$



is even for $n > 0$, and hence $p_{n}(n+1)$ is even, and thus $ne p_{n+1}$, as desired.






share|cite|improve this answer





















  • One can simplify this somewhat by noting that we don't need Lagrange interpolation; the method of forward differences is sufficient here and tells us that $n!$ times the coefficient of $x^{n-1}$ in $p_n$ is $sum_{i=0}^{n-1}(-1)^i{n-1choose i}cdot p_{i+1}$ which, similar to your argument, turns out to be odd, so not zero.
    – Milo Brandt
    Nov 25 at 19:01












  • wonderful proof
    – Sandeep Silwal
    Nov 25 at 21:03










  • There's nothing difficult about Lagrange interpolation --- it's an identity that proves itself. It would take longer to write out an argument using discrete derivatives and end up basically being the same, so I disagree it would be any simplification.
    – Lorem Ipsum
    Nov 25 at 21:49















up vote
5
down vote



accepted










The degree of $p_n(x)$ is always $n-1$. The proof is by induction.



Note that $p_1(x) = 2$ has degree $0$. Now assume that $p_{n}(x)$ has degree $n-1$. We want to prove that $p_{n+1}(x)$ has degree $n$. Assume otherwise, so $p_{n+1}(x)$ also had degree at most $n-1$. Then since $p_{n+1}(x)$ and $p_n(x)$ agree on the first $n$ values, it must be the case that $p_{n+1}(x) = p_n(x)$. In particular, to obtain a contradiction, it suffices to show that



$$p_n(n+1) ne^{?} p_{n+1}.$$



In fact, we simply will prove that $p_n(n+1)$ is always even which does the job.



We can write down a formula for $p_n(x)$, namely



$$p_n(x) = sum_{i=1}^{n} p_i cdot
frac{(x-1)(x-2) ldots widehat{(x-i)} ldots (x - n)}{(i-1)(i-2)
ldots widehat{(i-i)} ldots (i - n)},$$



where the hat indicates the term is omitted. This is clearly a polynomial of degree at most $n-1$ and $p_n(i) = p_i$. (This is the general formula for Lagrange interpolation specialized to this case.)



Hence



$$begin{aligned} p_n(n+1) = & sum_{i=1}^{n} p_i cdotfrac{ n!/(n+1-i)}{(i-1)! (n-i)! (-1)^{n-i}}\
= & (-1)^{n-1} sum_{i=1}^{n} p_i cdot frac{ n!}{(i-1)! (n+1-i)!} (-1)^{i-1} \
= & (-1)^{n-1} sum_{i=1}^{n} p_i cdot binom{n}{i-1} (-1)^{i-1}\
= & (-1)^{n-1} sum_{i=0}^{n-1} p_{i+1} binom{n}{i} (-1)^iend{aligned}$$



Now we use the fact that, with the exception of $p_1 = 2$, the primes are all odd. It follows that



$$p_{n}(n+1) equiv sum_{i=1}^{n-1} (-1)^i binom{n}{i} mod 2.$$



But now



$$sum_{i=1}^{n-1} (-1)^i binom{n}{i}
= (1-1)^n - 1 - (-1)^n equiv 0 mod 2,$$



is even for $n > 0$, and hence $p_{n}(n+1)$ is even, and thus $ne p_{n+1}$, as desired.






share|cite|improve this answer





















  • One can simplify this somewhat by noting that we don't need Lagrange interpolation; the method of forward differences is sufficient here and tells us that $n!$ times the coefficient of $x^{n-1}$ in $p_n$ is $sum_{i=0}^{n-1}(-1)^i{n-1choose i}cdot p_{i+1}$ which, similar to your argument, turns out to be odd, so not zero.
    – Milo Brandt
    Nov 25 at 19:01












  • wonderful proof
    – Sandeep Silwal
    Nov 25 at 21:03










  • There's nothing difficult about Lagrange interpolation --- it's an identity that proves itself. It would take longer to write out an argument using discrete derivatives and end up basically being the same, so I disagree it would be any simplification.
    – Lorem Ipsum
    Nov 25 at 21:49













up vote
5
down vote



accepted







up vote
5
down vote



accepted






The degree of $p_n(x)$ is always $n-1$. The proof is by induction.



Note that $p_1(x) = 2$ has degree $0$. Now assume that $p_{n}(x)$ has degree $n-1$. We want to prove that $p_{n+1}(x)$ has degree $n$. Assume otherwise, so $p_{n+1}(x)$ also had degree at most $n-1$. Then since $p_{n+1}(x)$ and $p_n(x)$ agree on the first $n$ values, it must be the case that $p_{n+1}(x) = p_n(x)$. In particular, to obtain a contradiction, it suffices to show that



$$p_n(n+1) ne^{?} p_{n+1}.$$



In fact, we simply will prove that $p_n(n+1)$ is always even which does the job.



We can write down a formula for $p_n(x)$, namely



$$p_n(x) = sum_{i=1}^{n} p_i cdot
frac{(x-1)(x-2) ldots widehat{(x-i)} ldots (x - n)}{(i-1)(i-2)
ldots widehat{(i-i)} ldots (i - n)},$$



where the hat indicates the term is omitted. This is clearly a polynomial of degree at most $n-1$ and $p_n(i) = p_i$. (This is the general formula for Lagrange interpolation specialized to this case.)



Hence



$$begin{aligned} p_n(n+1) = & sum_{i=1}^{n} p_i cdotfrac{ n!/(n+1-i)}{(i-1)! (n-i)! (-1)^{n-i}}\
= & (-1)^{n-1} sum_{i=1}^{n} p_i cdot frac{ n!}{(i-1)! (n+1-i)!} (-1)^{i-1} \
= & (-1)^{n-1} sum_{i=1}^{n} p_i cdot binom{n}{i-1} (-1)^{i-1}\
= & (-1)^{n-1} sum_{i=0}^{n-1} p_{i+1} binom{n}{i} (-1)^iend{aligned}$$



Now we use the fact that, with the exception of $p_1 = 2$, the primes are all odd. It follows that



$$p_{n}(n+1) equiv sum_{i=1}^{n-1} (-1)^i binom{n}{i} mod 2.$$



But now



$$sum_{i=1}^{n-1} (-1)^i binom{n}{i}
= (1-1)^n - 1 - (-1)^n equiv 0 mod 2,$$



is even for $n > 0$, and hence $p_{n}(n+1)$ is even, and thus $ne p_{n+1}$, as desired.






share|cite|improve this answer












The degree of $p_n(x)$ is always $n-1$. The proof is by induction.



Note that $p_1(x) = 2$ has degree $0$. Now assume that $p_{n}(x)$ has degree $n-1$. We want to prove that $p_{n+1}(x)$ has degree $n$. Assume otherwise, so $p_{n+1}(x)$ also had degree at most $n-1$. Then since $p_{n+1}(x)$ and $p_n(x)$ agree on the first $n$ values, it must be the case that $p_{n+1}(x) = p_n(x)$. In particular, to obtain a contradiction, it suffices to show that



$$p_n(n+1) ne^{?} p_{n+1}.$$



In fact, we simply will prove that $p_n(n+1)$ is always even which does the job.



We can write down a formula for $p_n(x)$, namely



$$p_n(x) = sum_{i=1}^{n} p_i cdot
frac{(x-1)(x-2) ldots widehat{(x-i)} ldots (x - n)}{(i-1)(i-2)
ldots widehat{(i-i)} ldots (i - n)},$$



where the hat indicates the term is omitted. This is clearly a polynomial of degree at most $n-1$ and $p_n(i) = p_i$. (This is the general formula for Lagrange interpolation specialized to this case.)



Hence



$$begin{aligned} p_n(n+1) = & sum_{i=1}^{n} p_i cdotfrac{ n!/(n+1-i)}{(i-1)! (n-i)! (-1)^{n-i}}\
= & (-1)^{n-1} sum_{i=1}^{n} p_i cdot frac{ n!}{(i-1)! (n+1-i)!} (-1)^{i-1} \
= & (-1)^{n-1} sum_{i=1}^{n} p_i cdot binom{n}{i-1} (-1)^{i-1}\
= & (-1)^{n-1} sum_{i=0}^{n-1} p_{i+1} binom{n}{i} (-1)^iend{aligned}$$



Now we use the fact that, with the exception of $p_1 = 2$, the primes are all odd. It follows that



$$p_{n}(n+1) equiv sum_{i=1}^{n-1} (-1)^i binom{n}{i} mod 2.$$



But now



$$sum_{i=1}^{n-1} (-1)^i binom{n}{i}
= (1-1)^n - 1 - (-1)^n equiv 0 mod 2,$$



is even for $n > 0$, and hence $p_{n}(n+1)$ is even, and thus $ne p_{n+1}$, as desired.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Nov 25 at 18:48









Lorem Ipsum

1312




1312












  • One can simplify this somewhat by noting that we don't need Lagrange interpolation; the method of forward differences is sufficient here and tells us that $n!$ times the coefficient of $x^{n-1}$ in $p_n$ is $sum_{i=0}^{n-1}(-1)^i{n-1choose i}cdot p_{i+1}$ which, similar to your argument, turns out to be odd, so not zero.
    – Milo Brandt
    Nov 25 at 19:01












  • wonderful proof
    – Sandeep Silwal
    Nov 25 at 21:03










  • There's nothing difficult about Lagrange interpolation --- it's an identity that proves itself. It would take longer to write out an argument using discrete derivatives and end up basically being the same, so I disagree it would be any simplification.
    – Lorem Ipsum
    Nov 25 at 21:49


















  • One can simplify this somewhat by noting that we don't need Lagrange interpolation; the method of forward differences is sufficient here and tells us that $n!$ times the coefficient of $x^{n-1}$ in $p_n$ is $sum_{i=0}^{n-1}(-1)^i{n-1choose i}cdot p_{i+1}$ which, similar to your argument, turns out to be odd, so not zero.
    – Milo Brandt
    Nov 25 at 19:01












  • wonderful proof
    – Sandeep Silwal
    Nov 25 at 21:03










  • There's nothing difficult about Lagrange interpolation --- it's an identity that proves itself. It would take longer to write out an argument using discrete derivatives and end up basically being the same, so I disagree it would be any simplification.
    – Lorem Ipsum
    Nov 25 at 21:49
















One can simplify this somewhat by noting that we don't need Lagrange interpolation; the method of forward differences is sufficient here and tells us that $n!$ times the coefficient of $x^{n-1}$ in $p_n$ is $sum_{i=0}^{n-1}(-1)^i{n-1choose i}cdot p_{i+1}$ which, similar to your argument, turns out to be odd, so not zero.
– Milo Brandt
Nov 25 at 19:01






One can simplify this somewhat by noting that we don't need Lagrange interpolation; the method of forward differences is sufficient here and tells us that $n!$ times the coefficient of $x^{n-1}$ in $p_n$ is $sum_{i=0}^{n-1}(-1)^i{n-1choose i}cdot p_{i+1}$ which, similar to your argument, turns out to be odd, so not zero.
– Milo Brandt
Nov 25 at 19:01














wonderful proof
– Sandeep Silwal
Nov 25 at 21:03




wonderful proof
– Sandeep Silwal
Nov 25 at 21:03












There's nothing difficult about Lagrange interpolation --- it's an identity that proves itself. It would take longer to write out an argument using discrete derivatives and end up basically being the same, so I disagree it would be any simplification.
– Lorem Ipsum
Nov 25 at 21:49




There's nothing difficult about Lagrange interpolation --- it's an identity that proves itself. It would take longer to write out an argument using discrete derivatives and end up basically being the same, so I disagree it would be any simplification.
– Lorem Ipsum
Nov 25 at 21:49










up vote
0
down vote













Not really an answer, but consider a more general question:




Does the polynomial interpolating $n$ consecutive primes $p_{m+1},dots,p_{m+n}$ always have maximum degree $n-1$?




The answer is a strong no because $3,5,7$ and $251,257,263,269$ are consecutive primes in arithmetic progression.
Small examples are known for $3 le n le 6$. See Wikipedia.



The polynomial interpolating the four consecutive primes $17, 19, 23, 29$ has degree $2$, not $3$. So does the polynomial interpolating the four consecutive primes $p_{m+1},dots,p_{m+4}$ for $m in {6,10,12,17,21,48,57,68,69,74,84,90,103,110,115,121,122,126,131,172,181}$.






share|cite|improve this answer























  • So what? You have answered negatively to a more general question. What about the particular case of $p_1,dots,p_n$?
    – Federico
    Nov 22 at 18:01















up vote
0
down vote













Not really an answer, but consider a more general question:




Does the polynomial interpolating $n$ consecutive primes $p_{m+1},dots,p_{m+n}$ always have maximum degree $n-1$?




The answer is a strong no because $3,5,7$ and $251,257,263,269$ are consecutive primes in arithmetic progression.
Small examples are known for $3 le n le 6$. See Wikipedia.



The polynomial interpolating the four consecutive primes $17, 19, 23, 29$ has degree $2$, not $3$. So does the polynomial interpolating the four consecutive primes $p_{m+1},dots,p_{m+4}$ for $m in {6,10,12,17,21,48,57,68,69,74,84,90,103,110,115,121,122,126,131,172,181}$.






share|cite|improve this answer























  • So what? You have answered negatively to a more general question. What about the particular case of $p_1,dots,p_n$?
    – Federico
    Nov 22 at 18:01













up vote
0
down vote










up vote
0
down vote









Not really an answer, but consider a more general question:




Does the polynomial interpolating $n$ consecutive primes $p_{m+1},dots,p_{m+n}$ always have maximum degree $n-1$?




The answer is a strong no because $3,5,7$ and $251,257,263,269$ are consecutive primes in arithmetic progression.
Small examples are known for $3 le n le 6$. See Wikipedia.



The polynomial interpolating the four consecutive primes $17, 19, 23, 29$ has degree $2$, not $3$. So does the polynomial interpolating the four consecutive primes $p_{m+1},dots,p_{m+4}$ for $m in {6,10,12,17,21,48,57,68,69,74,84,90,103,110,115,121,122,126,131,172,181}$.






share|cite|improve this answer














Not really an answer, but consider a more general question:




Does the polynomial interpolating $n$ consecutive primes $p_{m+1},dots,p_{m+n}$ always have maximum degree $n-1$?




The answer is a strong no because $3,5,7$ and $251,257,263,269$ are consecutive primes in arithmetic progression.
Small examples are known for $3 le n le 6$. See Wikipedia.



The polynomial interpolating the four consecutive primes $17, 19, 23, 29$ has degree $2$, not $3$. So does the polynomial interpolating the four consecutive primes $p_{m+1},dots,p_{m+4}$ for $m in {6,10,12,17,21,48,57,68,69,74,84,90,103,110,115,121,122,126,131,172,181}$.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Nov 23 at 16:32

























answered Nov 22 at 17:38









lhf

162k9166385




162k9166385












  • So what? You have answered negatively to a more general question. What about the particular case of $p_1,dots,p_n$?
    – Federico
    Nov 22 at 18:01


















  • So what? You have answered negatively to a more general question. What about the particular case of $p_1,dots,p_n$?
    – Federico
    Nov 22 at 18:01
















So what? You have answered negatively to a more general question. What about the particular case of $p_1,dots,p_n$?
– Federico
Nov 22 at 18:01




So what? You have answered negatively to a more general question. What about the particular case of $p_1,dots,p_n$?
– Federico
Nov 22 at 18:01










up vote
-1
down vote













Yes. Given $n$ unique data points, there is a unique polynomial of degree $n-1$ that interpolates the data. This is one of the first results in the interpolation section of any numerical analysis/methods course. Using data points constructed with primes is a specific case of this. If you write out the interpolation conditions, you'll see that this is equivalent to solving an $n times n$ linear system.






share|cite|improve this answer

















  • 3




    It is possible that the coefficient(s) of the highest degree term(s) is/are $0$, which would mean that the degree could be less than $n-1$. Actually the standard result is: There is a unique polynomial of degree at most $n-1$ interpolating $n$ points with different $x$-coordinates.
    – paw88789
    Nov 22 at 14:45















up vote
-1
down vote













Yes. Given $n$ unique data points, there is a unique polynomial of degree $n-1$ that interpolates the data. This is one of the first results in the interpolation section of any numerical analysis/methods course. Using data points constructed with primes is a specific case of this. If you write out the interpolation conditions, you'll see that this is equivalent to solving an $n times n$ linear system.






share|cite|improve this answer

















  • 3




    It is possible that the coefficient(s) of the highest degree term(s) is/are $0$, which would mean that the degree could be less than $n-1$. Actually the standard result is: There is a unique polynomial of degree at most $n-1$ interpolating $n$ points with different $x$-coordinates.
    – paw88789
    Nov 22 at 14:45













up vote
-1
down vote










up vote
-1
down vote









Yes. Given $n$ unique data points, there is a unique polynomial of degree $n-1$ that interpolates the data. This is one of the first results in the interpolation section of any numerical analysis/methods course. Using data points constructed with primes is a specific case of this. If you write out the interpolation conditions, you'll see that this is equivalent to solving an $n times n$ linear system.






share|cite|improve this answer












Yes. Given $n$ unique data points, there is a unique polynomial of degree $n-1$ that interpolates the data. This is one of the first results in the interpolation section of any numerical analysis/methods course. Using data points constructed with primes is a specific case of this. If you write out the interpolation conditions, you'll see that this is equivalent to solving an $n times n$ linear system.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Nov 22 at 14:30









Eric

11




11








  • 3




    It is possible that the coefficient(s) of the highest degree term(s) is/are $0$, which would mean that the degree could be less than $n-1$. Actually the standard result is: There is a unique polynomial of degree at most $n-1$ interpolating $n$ points with different $x$-coordinates.
    – paw88789
    Nov 22 at 14:45














  • 3




    It is possible that the coefficient(s) of the highest degree term(s) is/are $0$, which would mean that the degree could be less than $n-1$. Actually the standard result is: There is a unique polynomial of degree at most $n-1$ interpolating $n$ points with different $x$-coordinates.
    – paw88789
    Nov 22 at 14:45








3




3




It is possible that the coefficient(s) of the highest degree term(s) is/are $0$, which would mean that the degree could be less than $n-1$. Actually the standard result is: There is a unique polynomial of degree at most $n-1$ interpolating $n$ points with different $x$-coordinates.
– paw88789
Nov 22 at 14:45




It is possible that the coefficient(s) of the highest degree term(s) is/are $0$, which would mean that the degree could be less than $n-1$. Actually the standard result is: There is a unique polynomial of degree at most $n-1$ interpolating $n$ points with different $x$-coordinates.
– paw88789
Nov 22 at 14:45


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3009163%2fdegree-of-polynomial-interpolating-the-primes%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Probability when a professor distributes a quiz and homework assignment to a class of n students.

Aardman Animations

Are they similar matrix