I am going to #trymathslive with this question from @jamestanton
(Just to clarify: I will be tweeting my whole thought process including questions I ask to myself, and do not need suggestions or corrections unless I explicitly say I want outside help.)
(Just to clarify: I will be tweeting my whole thought process including questions I ask to myself, and do not need suggestions or corrections unless I explicitly say I want outside help.)
https://twitter.com/jamestanton/status/1323607322304737280
The problem was intriguing because it seemed like it wasn’t much information that has to be true to force the whole function to behave a certain way.
And now I say that I guess it’s maybe not all that unexpected considering k+1 points of a degree k polynomial are enough to determine the exact formula of the polynomial.
Does’t mean I know where to go yet, of course.
I probably don’t know actually need to find the formula for the polynomial, but it’s the thought in my head right now, so I’m going to chase down where it goes.
If I have a polynomial p(x)a= a0+a1 x + a2 x^2 etc, and some points on its graph, then I could sub the points in to get a set of linear equations in a0, a1, ... that I could solve to find the coefficients.
This is all too general for me right now.
If I had a quadratic p(x)=a0+a1x+a2x^2 and three points (2,19), (3,72), (4,10), then my equations would be
a0+2a1+4a2=19
a0+3a1+9a2=72
a0+4a1+16a2=10.
And I’d have to solve them to find the values of a0, a1, a2.
If I had a quadratic p(x)=a0+a1x+a2x^2 and three points (2,19), (3,72), (4,10), then my equations would be
a0+2a1+4a2=19
a0+3a1+9a2=72
a0+4a1+16a2=10.
And I’d have to solve them to find the values of a0, a1, a2.
(Of course then I’d have to somehow tell that whatever formula I do get produces only integer outputs, but I choose not to worry about that right now.)
So I’ve got three equations
a0+2a1+4a2=19... (1)
a0+3a1+9a2=72... (2)
a0+4a1+16a2=10... (3)
If I subtract (2)-(1) I get
a1 +5a2=53
If I subtract (3)-(2) I get
a1+7a2=-62
That’s interesting. They both start with a1.
a0+2a1+4a2=19... (1)
a0+3a1+9a2=72... (2)
a0+4a1+16a2=10... (3)
If I subtract (2)-(1) I get
a1 +5a2=53
If I subtract (3)-(2) I get
a1+7a2=-62
That’s interesting. They both start with a1.
That would always happen with inputs that were 1 apart, wouldn’t it?
It occurs to me I don’t need to find the coefficients per se. I just need to be able to combine these equations so I can get a0+ma1+m^2a2 for any integer m and as long as I know for sure I always get an integer I’ll be good.
Hmm.
Different track...
Let me write out some maths notation.
p(x) is of degree k.
p(m), p(m+1),...,p(m+k) are all integers.
Need to show p(x) is an integer for integer x.
I’m thinking this is the same as showing p(k+d) is an integer for all integer d.
Let me write out some maths notation.
p(x) is of degree k.
p(m), p(m+1),...,p(m+k) are all integers.
Need to show p(x) is an integer for integer x.
I’m thinking this is the same as showing p(k+d) is an integer for all integer d.
If p(k+d)-p(k) has a whole lot of terms like
a3((k+d)^3-k^3)
=a3(k+d-k)((k+d)^2+(k+d)k+k^2)
=a3(d)(quadratic)
That’s a multiple of d.
Does that help?
a3((k+d)^3-k^3)
=a3(k+d-k)((k+d)^2+(k+d)k+k^2)
=a3(d)(quadratic)
That’s a multiple of d.
Does that help?
Wait, that subtracting thing was what I was doing back in my linear equations, really, wasn’t it? I did p(m+1)-p(m) and p(m+2)-p(m).
Oh wait. p(x+1)-p(x) is one degree less isn’t it? Exactly because of the argument I did earlier with the difference of two cubes.
So that provides a way to step down to the previous degree, and THAT way lies induction!
So that provides a way to step down to the previous degree, and THAT way lies induction!
Ok so suppose it’s true that if a polynomial of degree n and has integer output for n+1 consecutive integer inputs, then it always produces an integer output for every integer input.
And let p(x) be a degree n+1 polynomial with integer outputs for p(m), p(m+1),...,p(m+n+1).
And let p(x) be a degree n+1 polynomial with integer outputs for p(m), p(m+1),...,p(m+n+1).
Let q(x)=p(x+1)-p(x).
This is a degree n polynomial.
Wait. Is it? Maybe it will be degree LESS than n, because stuff happens to cancel out.
Ok then we do STRONG induction where I suppose that the thing works for all degrees up to and including n.
This is a degree n polynomial.
Wait. Is it? Maybe it will be degree LESS than n, because stuff happens to cancel out.
Ok then we do STRONG induction where I suppose that the thing works for all degrees up to and including n.
Ok. So q(x) is a polynomial of degree up to n.
And q(m)=p(m+1)-p(m) is an integer because both p(m+1) and p(m) are.
And q(m+1)=p(m+2)-p(m+1) is an integer because both p(m+2) and p(m+1) are.
And so on.
And q(m)=p(m+1)-p(m) is an integer because both p(m+1) and p(m) are.
And q(m+1)=p(m+2)-p(m+1) is an integer because both p(m+2) and p(m+1) are.
And so on.
So I know that q(m),...,q(m+n) are all integers.
Now q is degree at most n and has n+1 consecutive integer inputs that have integer outputs, so definitely one more than its degree. And that means every integer input for q(x) produces an integer output.
Now q is degree at most n and has n+1 consecutive integer inputs that have integer outputs, so definitely one more than its degree. And that means every integer input for q(x) produces an integer output.
Oh crap. This doesn’t tell me about the values of p does it?!
Hmm.
Hmm.
I know q(x)=p(x+1)-p(x).
So p(x)=p(x+1)-q(x).
Does that help?
So p(x)=p(x+1)-q(x).
Does that help?
Yes! If p(x+1) is an integer then p(x) will have to be. And that means that we can show p(m-1) is an integer and so on down to all integers below m.
Technically that’s another induction inside this induction, which is cool.
Technically that’s another induction inside this induction, which is cool.
I need to go upwards too. How do I arrange that?
q(x)=p(x+1)-p(x)
p(x+1)=q(x)+p(x)
So p(x+1) is an integer if p(x) is (for integer x).
And now I can show each integer above m+n+1 produces and integer output too.
So p always produces an integer output for an integer input.
q(x)=p(x+1)-p(x)
p(x+1)=q(x)+p(x)
So p(x+1) is an integer if p(x) is (for integer x).
And now I can show each integer above m+n+1 produces and integer output too.
So p always produces an integer output for an integer input.
Is that it?
Scanning through the tweets, no it isn’t because I haven’t done the base case of my induction.
Let p(x) be a polynomial of degree 0. Then p(x)=a for some number a.
And if p(m) is an integer for some m, then a is an integer, so p(x) is an integer for all x, including the integers.
Let p(x) be a polynomial of degree 0. Then p(x)=a for some number a.
And if p(m) is an integer for some m, then a is an integer, so p(x) is an integer for all x, including the integers.
Yes!!
It’s true for polynomials of degree 0.
If it’s true for polynomials of degree up to n, then it’s true for polynomials of degree n+1.
Therefore it’s true for all polynomials.
It’s true for polynomials of degree 0.
If it’s true for polynomials of degree up to n, then it’s true for polynomials of degree n+1.
Therefore it’s true for all polynomials.
Yay!
Thanks for the fun, @jamestanton!
I feel like applying some of the reasoning to what I was doing back there with my specific example.
I had a quadratic p(x)=a0+a1x+a2x^2 and three points (2,19), (3,72), (4,10).
My argument went that q(x)=p(x+1)-p(x) is of lower degree and all its outputs are integers for integer inputs.
q(2)=p(3)-p(2)=72-19=53
q(3)=p(4)-p(3)=10-72=-62
My argument went that q(x)=p(x+1)-p(x) is of lower degree and all its outputs are integers for integer inputs.
q(2)=p(3)-p(2)=72-19=53
q(3)=p(4)-p(3)=10-72=-62
Also p(x)=p(x+1)-q(x).
So p(1)=p(2)-q(1).
Ah. I don’t know what q(1) is.
So p(1)=p(2)-q(1).
Ah. I don’t know what q(1) is.
Wait. I *do* know what q(1) is! It’s p(2)-p(1). Nope that’s just removing everything and getting q(1)=q(1). Damnit.
What about the other way?
q(x)=p(x+1)-p(x)
p(x+1)=q(x)+p(x)
p(x)=q(x-1)+p(x-1)
So p(5)=q(4)+p(4).
Ah but I don’t know what q(4) is.
There’s no way around having to figure out the actual formula for the function q.
q(x)=p(x+1)-p(x)
p(x+1)=q(x)+p(x)
p(x)=q(x-1)+p(x-1)
So p(5)=q(4)+p(4).
Ah but I don’t know what q(4) is.
There’s no way around having to figure out the actual formula for the function q.
Oh except I could go down another layer until I got to a constant function, right?
r(x)=q(x+1)-q(x) is constant.
And r(2)=q(3)-q(2)=-62-53=-115.
And r(anything)=-115.
So now
q(4)=r(3)+q(3)=-62-115=-177
and
p(5)=q(4)+p(4)=-117+10=-107
r(x)=q(x+1)-q(x) is constant.
And r(2)=q(3)-q(2)=-62-53=-115.
And r(anything)=-115.
So now
q(4)=r(3)+q(3)=-62-115=-177
and
p(5)=q(4)+p(4)=-117+10=-107
I got Desmos to find the function for me to see if it’s right. Crap. That’s not the answer I got. 
Whoops! I said p(5)=-117+10, but actually p(5)=-177+10=-167, which is what Desmos says too.
Phew!
Ok so that’s pretty cool that the induction proof shows me a way to actually calculate values of the function without finding a formula for the function per se.
Phew!
Ok so that’s pretty cool that the induction proof shows me a way to actually calculate values of the function without finding a formula for the function per se.
Ok. Really have to to now. Thanks again @jamestanton!
Ooh! After not thinking about this all day, it occurs to me that this theorem means that a function whose graph passes through (1,8),(2,10),(3,20),(7,59.6) can’t be a quadratic, no calculations required.
Also, I reckon that the argument above hinges on the fact that the integers are closed under addition and subtraction. So I should be able to apply it to the situation where the outputs are in any set closed under addition.
That is, if a polynomial of degree k has values in [set closed under addition and subtraction] at k+1 consecutive integer inputs, then it will have values in [set closed under addition and subtraction] for all integer inputs.
For example, suppose I have a quadratic with this table of values
x, f(x)
1,2.6
2,3.7
3,7.5
Then the values of f for *all* integer inputs will be numbers with at most one decimal place too.
This appeals to me for some reason.
x, f(x)
1,2.6
2,3.7
3,7.5
Then the values of f for *all* integer inputs will be numbers with at most one decimal place too.
This appeals to me for some reason.
And what about numbers in between the integers?
So what if p(x) has integer outputs for all integer inputs. What about integer-and-a-half?
So what if p(x) has integer outputs for all integer inputs. What about integer-and-a-half?
If p(x)=a0+a1x+a2x^2+...
then p(x+1/2) = a0 + a1(x+1/2)+a2(x+1/2)^2+...
= a0 + a1x+1/2 a1+ a2(x^2+2*1/2x+1/4)+...
Yeah I don’t have much of an idea of what’s happening there!
then p(x+1/2) = a0 + a1(x+1/2)+a2(x+1/2)^2+...
= a0 + a1x+1/2 a1+ a2(x^2+2*1/2x+1/4)+...
Yeah I don’t have much of an idea of what’s happening there!
I can see the p(x) in there if I expand out a bit. But it’s going to be p(x+1/2)=p(x)+crap of degree less than k. But I don’t know what that crap is all about.
Trying it out in Desmos with some specific examples to see what happens:
So it seems there are these options for what the -and-a-halfs will produce when the integers produce integers:
* all whole integers
* all integers-and-a-half
* all integers-and-some-quarters
* all integers-and-some-eighths
* all whole integers
* all integers-and-a-half
* all integers-and-some-quarters
* all integers-and-some-eighths
I notice that when it's integers-and-some-quarters, it always seems to be +1/4 or +3/4.
And when it's integers-and-some-eights, it always seems to be +1/8, +3/8, +5/8 or +7/8.
What is the deal with that, I wonder?
And when it's integers-and-some-eights, it always seems to be +1/8, +3/8, +5/8 or +7/8.
What is the deal with that, I wonder?
But this is an investigation for another day (or never). I am now happy for other people to take this up if they feel inspired. I give it to whoever wants to take it now.
Actually, I have now gone to look at what other people have said about the problem, and this approach of @jamestanton might solve the -and-a-half problem.
https://twitter.com/jamestanton/status/1323972498497523712?s=20
If a quadratic passes through points (k, a), (k+1, b), (k+2,c) for integers k, a, b, c, then it will be
p(x)=c(x-k)(x-k-1)/[(k+2-k)(k+2-k-1)]
+ b(x-k)(x-k-2)/[(k+1-k)(k+1-k-2)]
+ a(x-k-1)(x-k-2)/[(k-k-1)(k-k-2)]
= c(x-k)(x-k-1)/2 - b(x-k)(x-k-2) + a(x-k-1)(x-k-2)/2
p(x)=c(x-k)(x-k-1)/[(k+2-k)(k+2-k-1)]
+ b(x-k)(x-k-2)/[(k+1-k)(k+1-k-2)]
+ a(x-k-1)(x-k-2)/[(k-k-1)(k-k-2)]
= c(x-k)(x-k-1)/2 - b(x-k)(x-k-2) + a(x-k-1)(x-k-2)/2
So if I do p(k+d+1/2) I get
p(m+1/2) = c(d+1/2)(d-1+1/2)/2 - b(d+1/2)(d-2+1/2) + a(d-1+1/2)(d-2+1/2)/2
= c(d+1/2)(d-1/2)/2 - b(d+1/2)(d-3/2) + a(d-1/2)(d-3/2)/2
= c(2d+1)(2d-1)/8 - b(2d+1)(2d-3) + a(2d-1)(2d-3)/8
p(m+1/2) = c(d+1/2)(d-1+1/2)/2 - b(d+1/2)(d-2+1/2) + a(d-1+1/2)(d-2+1/2)/2
= c(d+1/2)(d-1/2)/2 - b(d+1/2)(d-3/2) + a(d-1/2)(d-3/2)/2
= c(2d+1)(2d-1)/8 - b(2d+1)(2d-3) + a(2d-1)(2d-3)/8
p(k+d+1/2)
= 1/8 ( c(2d+1)(2d-1) - 8b(2d+1)(2d-3) + a(2d-1)(2d-3))
This is always an integer number of eighths!
= 1/8 ( c(2d+1)(2d-1) - 8b(2d+1)(2d-3) + a(2d-1)(2d-3))
This is always an integer number of eighths!
Also, if a is odd and c is even, then it will always be an ODD number of eighths! Which is what I observed in the Desmos earlier.
How satisfying.
How satisfying.
Ok. Actually finished now. Thanks one last time @jamestanton
• • •
Missing some Tweet in this thread? You can try to
force a refresh
