Degree of polynomial interpolating the primes
up vote
10
down vote
favorite
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
|
show 1 more comment
up vote
10
down vote
favorite
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
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
|
show 1 more comment
up vote
10
down vote
favorite
up vote
10
down vote
favorite
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
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
number-theory polynomials prime-numbers
edited Nov 25 at 1:46
asked Nov 22 at 13:47
Joseph O'Rourke
17.5k348106
17.5k348106
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
|
show 1 more comment
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
|
show 1 more comment
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.
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
add a comment |
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}$.
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
add a comment |
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.
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
add a comment |
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.
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
add a comment |
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.
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
add a comment |
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.
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.
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
add a comment |
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
add a comment |
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}$.
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
add a comment |
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}$.
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
add a comment |
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}$.
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}$.
edited Nov 23 at 16:32
answered Nov 22 at 17:38
lhf
161k9165384
161k9165384
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
add a comment |
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
add a comment |
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.
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
add a comment |
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.
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
add a comment |
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.
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.
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
add a comment |
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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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