That blog post is specifically about the question about whether a polynomial taking integer values on positive integers (or any sufficiently large subset thereof) necessarily is an integer-valued polynomial (the answer is yes).
Among other things, as mentioned, “every integer-valued polynomial can be written as an integer linear combination of binomial coefficients” [in exactly one way].
The conjecture in the OP post, that every polynomial everywhere divisible by k counts {something}, is intriguing, and I wouldn't be surprised if it were true.
There is a genre of undergraduate polynomial divisibility problems which look like this: Show that f(n) is divisible by some integer k.
These problems often appear to be (elementary) number theory problems. However, often there is a rather elegant proof associated with them which is based on combinatorics.
The crux of this proof is that the polynomial counts the number of equivalence classes of a certain kind.
The easy way of seeing the first part is to do the prime factorization. The 7 doesn't matter since it's prime. If n has a 2 in its factorization it now has 2^3. But if it doesn't have a 2 it won't suddenly acquire one.
All the symbol soup proofs aren't wrong but I don't think they satisfyingly explain the why.
I vote this the best proof. All you need to know to understand it is to know how multiplication, addition and exponentiation works. You could probably show this to a child in a sixth grade or so, and have them understand it. This is really good!
If n is even, we can choose some m such that n = 2m, and p(n) = p(2m) = 7 * 8m^3 + 2m = 2 * (7 * 4m^3 + m), which is divisible by 2 since we could factor out the 2 at the start.
If n is odd, similarly we can say n = 2m + 1. p(2m) = 7 * (2m + 1)^3 + (2m + 1) = 56m^3 + 84m^2 + 44m + 8 = 2 * (28m^3 + 42m^2 + 22m + 4), which is also divisible by 2 per the 2 at the start.
>> Apparently I'm good enough at math to do the proofs, but not to write the exercises.
Took a look on it, seems like a highly particular / specialized area of mathematics. It's like computer science, can't know them all. If you work all day with some area, say compilers or databases or financial software or what else, you'd be a whizz at it while it's unreasonable to expect someone from a different domain be able of more than a superficial understanding of what you write.
I'm pretty good at math but like with computers, I don't have the compulsion to dive deep into an unfamiliar domain just for the sake of it. So commenting on the article: cool, now I know how these problems are formed and in the very unlikely domain I'll need to produce one, I know where to look. Likely this will never happen, though.
> seems like a highly particular / specialized area of mathematics. It's like computer science, can't know them all
As a non-mathy, I'm interested in whether the idea that being good/able to provide proofs in one area, automagically makes one proficient in another is customary in the field or rejected quite early on when choosing a math specialisation?
It is not typical that being good in one area of mathematics makes one proficient in another — mathematics has a lot of depth, and to reach the frontier in any specialization requires years of study. However:
- There is a story/legend told about Erdős, where he was so good at problem-solving/proofs that he once solved a problem in another area after asking for the definitions of the terms in the problem. (The fact that this story is told illustrates that it is not commonplace.)
Well there is common stuff that one must be familiar with to be proficient and marginal stuff that you can get by without knowing because chances is you're not going to need it.
Like take for instance financial mathematics where I had some special interest, it's totally oblivious to areas such as geometry or number theory. I never had to figure out if a polynomial is divisible by 6 for instance :)
Like computer science, there's the common algorithms stuff but being an expert in web development doesn't help you much in writing high frequency trading server code, and the other way around.
n = 0 or 1 modulo 2. So we have to check out only two cases module 2, and these cases trivial. To prove the problem note that 6 = 2 * 3 and then is trivial to see that the polynomial is=0 modulo 2 if n=0,1 modulo 6and then check it is =0 modulo 3 for n=0,1,2 modulo 3 and you are done.
As the post mentions in passing, the integer-valued polynomials are completely characterized by the property that when written as a sum of {c_i (x choose i)}, all the coefficients c_i are integers. I imagine this is where most of the exercises actually come from. For example, using [3 1 4 1 5 9], the polynomial {3 + 1·x + 4·x(x-1)/2 + 1·x(x-1)(x-2)/6 + 5·x(x-1)(x-2)(x-3)/24 + 9·x(x-1)(x-2)(x-3)(x-4)/120} simplifies to 1/120 (9x^5 - 65x^4 + 185x^3 + 5x^2 - 14x + 360), so you could use it to generate exercises like:
- Prove that 9x^5 - 65x^4 + 185x^3 + 5x^2 - 14x + 360 is always a multiple of 120
Oh this is nothing. One of my colleagues does that and adds random colour changes, underlines and font face changes. It's like working with a serial killer.
Ahh. I honestly miss that amount of self-expression, garish as it was. Or rather, I intensely dislike the mono-culture where every vertical video with one-word subtitles looks the same.
You're the second commenter, so far, to mention exclamation marks. What do they mean to you that would bother you so much to point it out, or anyone for that matter? I haven't even noticed them until I read the comments here on hn.
Not gp, but I feel similarly. For me, I can't help read it with emphasis. As in, the voice in my head gets all fancy in an annoying way. If you imagine someone in person reading it out-loud with exaggerated emphasis, that's what it feels like. Same thing with comic books for me, the sprinkled bolded words in dialog are really grating.
To me it's fairly similar to someone making excessive use of CAPS LOCK. It can be used as a stylistic choice at times, but use it TOO MUCH and it just becomes DISTRACTING.
I DON'T SEE A PROBLEM WITH THIS EITHER! BUT I EMPATHIZE! I GET COMMENTS FROM PEOPLE SAYING THAT I'M SOMEHOW YELLING AT THEM ALL THE TIME BUT I'M ACTUALLY SITTING IN SILENCE, TYPING QUIETLY ON A MEMBRANE KEYBOARD! LOL???
More on integer valued polynomials: https://cameroncounts.wordpress.com/2017/01/31/polynomials-t...
That blog post is specifically about the question about whether a polynomial taking integer values on positive integers (or any sufficiently large subset thereof) necessarily is an integer-valued polynomial (the answer is yes).
The OP blog post here actually links to / points out there's an Wikipedia article on integer-valued polynomials: https://en.wikipedia.org/wiki/Integer-valued_polynomial
Among other things, as mentioned, “every integer-valued polynomial can be written as an integer linear combination of binomial coefficients” [in exactly one way].
The conjecture in the OP post, that every polynomial everywhere divisible by k counts {something}, is intriguing, and I wouldn't be surprised if it were true.
My daily dose of inferiority: done. :-) Perfect sentences which are complete gobblede-gook to me.
TLDR Summary:
There is a genre of undergraduate polynomial divisibility problems which look like this: Show that f(n) is divisible by some integer k.
These problems often appear to be (elementary) number theory problems. However, often there is a rather elegant proof associated with them which is based on combinatorics.
The crux of this proof is that the polynomial counts the number of equivalence classes of a certain kind.
This is closely related to https://en.wikipedia.org/wiki/Burnside%27s_lemma
The question at the end of the post is whether _all_ such problems must come this way
Well I was curious, but there's a lot there I didn't understand. Apparently I'm good enough at math to do the proofs, but not to write the exercises.
Exercise left to the reader:
Prove 7*n^3 + n is divisible by 2
7n^3 +n (mod 2) = 1 n^3 + n = n + n = 2*n = 0*n = 0
7*n^3 is even when n is even and odd otherwise.
odd + odd is even, as is even + even.
The easy way of seeing the first part is to do the prime factorization. The 7 doesn't matter since it's prime. If n has a 2 in its factorization it now has 2^3. But if it doesn't have a 2 it won't suddenly acquire one.
All the symbol soup proofs aren't wrong but I don't think they satisfyingly explain the why.
All of these "always divisible by n" proofs are asking you to solve them case by case in modular arithmetic.
For divisibility by two, there are only two cases. So if n is 1, then n³ is 1, and if n is 0, n³ is 0. 0+0 = 0; 1+1 = 0; and this completes the proof.
I am not actually sure that doing a prime factorization on 7n³ for unknown n is easier than knowing that 1³ = 1.
I vote this the best proof. All you need to know to understand it is to know how multiplication, addition and exponentiation works. You could probably show this to a child in a sixth grade or so, and have them understand it. This is really good!
Given p(n) = 7n^3 + n:
If n is even, we can choose some m such that n = 2m, and p(n) = p(2m) = 7 * 8m^3 + 2m = 2 * (7 * 4m^3 + m), which is divisible by 2 since we could factor out the 2 at the start.
If n is odd, similarly we can say n = 2m + 1. p(2m) = 7 * (2m + 1)^3 + (2m + 1) = 56m^3 + 84m^2 + 44m + 8 = 2 * (28m^3 + 42m^2 + 22m + 4), which is also divisible by 2 per the 2 at the start.
>> Apparently I'm good enough at math to do the proofs, but not to write the exercises.
Took a look on it, seems like a highly particular / specialized area of mathematics. It's like computer science, can't know them all. If you work all day with some area, say compilers or databases or financial software or what else, you'd be a whizz at it while it's unreasonable to expect someone from a different domain be able of more than a superficial understanding of what you write.
I'm pretty good at math but like with computers, I don't have the compulsion to dive deep into an unfamiliar domain just for the sake of it. So commenting on the article: cool, now I know how these problems are formed and in the very unlikely domain I'll need to produce one, I know where to look. Likely this will never happen, though.
> seems like a highly particular / specialized area of mathematics. It's like computer science, can't know them all
As a non-mathy, I'm interested in whether the idea that being good/able to provide proofs in one area, automagically makes one proficient in another is customary in the field or rejected quite early on when choosing a math specialisation?
It is not typical that being good in one area of mathematics makes one proficient in another — mathematics has a lot of depth, and to reach the frontier in any specialization requires years of study. However:
- There are skills that carry over; these are usually known by the name "mathematical maturity" https://en.wikipedia.org/w/index.php?title=Mathematical_matu...
- There is a story/legend told about Erdős, where he was so good at problem-solving/proofs that he once solved a problem in another area after asking for the definitions of the terms in the problem. (The fact that this story is told illustrates that it is not commonplace.)
Well there is common stuff that one must be familiar with to be proficient and marginal stuff that you can get by without knowing because chances is you're not going to need it.
Like take for instance financial mathematics where I had some special interest, it's totally oblivious to areas such as geometry or number theory. I never had to figure out if a polynomial is divisible by 6 for instance :)
Like computer science, there's the common algorithms stuff but being an expert in web development doesn't help you much in writing high frequency trading server code, and the other way around.
n = 0 or 1 modulo 2. So we have to check out only two cases module 2, and these cases trivial. To prove the problem note that 6 = 2 * 3 and then is trivial to see that the polynomial is=0 modulo 2 if n=0,1 modulo 6and then check it is =0 modulo 3 for n=0,1,2 modulo 3 and you are done.
And a proof by "counting something":
1 + 2 + ... + n = n(n+1)/2
2 divides n(n+1), n(n+1) = 2m
7 * n^3 + n =
2*(3*n^3 + n) + n^3 - n =
2*(3*n^3 + n) + n(n+1)(n-1) =
2*(3*n^3 + n + m(n-1))
> but not to write the exercises
As the post mentions in passing, the integer-valued polynomials are completely characterized by the property that when written as a sum of {c_i (x choose i)}, all the coefficients c_i are integers. I imagine this is where most of the exercises actually come from. For example, using [3 1 4 1 5 9], the polynomial {3 + 1·x + 4·x(x-1)/2 + 1·x(x-1)(x-2)/6 + 5·x(x-1)(x-2)(x-3)/24 + 9·x(x-1)(x-2)(x-3)(x-4)/120} simplifies to 1/120 (9x^5 - 65x^4 + 185x^3 + 5x^2 - 14x + 360), so you could use it to generate exercises like:
- Prove that 9x^5 - 65x^4 + 185x^3 + 5x^2 - 14x + 360 is always a multiple of 120
(or 5, or any divisor of 120).
i couldnt come up with a proof for the initial problem (n^6+n^3+2n^2 is a multiple of 6 for every n)
because it's not true (simply insert 1, 2, 4 or 5)
You’re missing a term: n^6+n^3+2n^2+2n
i just computed the solution mod 2 and mod 3 a la chinese remainder theorem
the polynomial is =0 mod2 and =0 mod3 so its =0 mod6
n^6 + n^3 + 2n^2 + 2n (mod 2) = n^6 + n^3 + 0 + 0 = n^3(n^3+1) = 0*1 or 1*0 = 0
because consecutive numbers are even then odd then even ....
for mod3 you can make a table
you could also factor the polynomial and see the solution easily
n(n+1)(n^2-2n+2)(n^2+n+1)
[stub for offtopicness]
I feel silly saying this, but I wish the author would use more periods and fewer exclamation marks.
Elaine Benes would be proud of their writing...
I was in the pool!
Oh this is nothing. One of my colleagues does that and adds random colour changes, underlines and font face changes. It's like working with a serial killer.
Maybe he was a teenager on IRC in the late 90s or early 00s and decided to never change
Thinking about it I guess MSN messenger and My Space also allowed/encouraged font shenanigans? My memory falters
Ahh. I honestly miss that amount of self-expression, garish as it was. Or rather, I intensely dislike the mono-culture where every vertical video with one-word subtitles looks the same.
You're the second commenter, so far, to mention exclamation marks. What do they mean to you that would bother you so much to point it out, or anyone for that matter? I haven't even noticed them until I read the comments here on hn.
Not gp, but I feel similarly. For me, I can't help read it with emphasis. As in, the voice in my head gets all fancy in an annoying way. If you imagine someone in person reading it out-loud with exaggerated emphasis, that's what it feels like. Same thing with comic books for me, the sprinkled bolded words in dialog are really grating.
To me it's fairly similar to someone making excessive use of CAPS LOCK. It can be used as a stylistic choice at times, but use it TOO MUCH and it just becomes DISTRACTING.
I DON'T SEE A PROBLEM WITH THIS EITHER! BUT I EMPATHIZE! I GET COMMENTS FROM PEOPLE SAYING THAT I'M SOMEHOW YELLING AT THEM ALL THE TIME BUT I'M ACTUALLY SITTING IN SILENCE, TYPING QUIETLY ON A MEMBRANE KEYBOARD! LOL???