Sums of powers of elements in a subset and polynomial with $-1,0,1$ coefficients
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Recently, I came across the following problem:
It is known that $k$ and $n$ are positive integers, and that $k+1 le sqrtfracn+1ln(n+1).$ Prove that we can find a polynomial $P$ of degree $n$, whose coefficients belong to $-1,0,1,$ such that $(x-1)^k$ divides $P$
(Some background: This was proposed to me by a colleague, who stated it was from an Ukrainian IMO team selection test. I have taken a look around, but never succeeded in the task of finding an actual solution. Also, the colleague who proposed it to me did not know himself how to solve it either.)
At first, I thought a simple construction would suffice: namely, one relatively 'naive' idea is to consider products of the form
$$ (x^alpha_1 - 1)(x^alpha_2 -1) cdots (x^alpha_k -1),$$
where $alpha_1 + alpha_2 + cdots + alpha_k = n.$ Indeed, this works and yields a non-trivial result through an algorithmic method, but only when $k lesssim ln(n).$ One can improve $ln(n)$ slightly in the construction - which is not at all sophisticated -, but not so that one can reach the $n^1/2/ln(n)^1/2$ type of upper bound, which is asked.
Therefore, I guess the 'hint' here is that we should not be looking for a 'constructive' proof, but rather for an 'existence' one. Therefore, with that in mind, we write our desired polynomial as
$$P(x) = sum_a in A x^a - sum_b in B x^b.$$
Then, $(x-1)^k$ dividing $P$ means that $P(1) = P'(1) = cdots = P^(k-1)(1) = 0.$ But this implies, after some manipulations, that
$$ sum_a in A 1 = sum_b in B 1, $$
$$ sum_a in A a = sum_b in B b, $$
$$ sum_a in A a^2 = sum_b in B b^2,$$
$$ vdots $$
$$ sum_a in A a^k-1 = sum_b in B b^k-1.$$
Let then $s_k(A) = sum_a in A a^k,$ where $A subset 0,1,...,n.$ The problem can therefore be restated as follows:
There are two subsets $A,B subset 0,1,...,n$ such that $|A| = |B|$ and $s_j(A) = s_j(B), ,j=1,...,k-1.$
Notice that $A$ and $B$ need not necessarily be disjoint, as any possible overlap is 'cancelled' in the definition of $P.$
In order to solve this problem, I have been trying to use continuity arguments, like 'keep the sum unchanged by changing two elements, and the difference between the squares decreases' or something of this kind. This might indeed be helpful, but I cannot see how to take it on further than that, that is, how to use this construction for $k > 2.$
combinatorics polynomials contest-math
asked Sep 10 at 10:04
João Ramos
1,236719
add a comment |Â
up vote
3
down vote
favorite
Recently, I came across the following problem:
It is known that $k$ and $n$ are positive integers, and that $k+1 le sqrtfracn+1ln(n+1).$ Prove that we can find a polynomial $P$ of degree $n$, whose coefficients belong to $-1,0,1,$ such that $(x-1)^k$ divides $P$
(Some background: This was proposed to me by a colleague, who stated it was from an Ukrainian IMO team selection test. I have taken a look around, but never succeeded in the task of finding an actual solution. Also, the colleague who proposed it to me did not know himself how to solve it either.)
At first, I thought a simple construction would suffice: namely, one relatively 'naive' idea is to consider products of the form
$$ (x^alpha_1 - 1)(x^alpha_2 -1) cdots (x^alpha_k -1),$$
where $alpha_1 + alpha_2 + cdots + alpha_k = n.$ Indeed, this works and yields a non-trivial result through an algorithmic method, but only when $k lesssim ln(n).$ One can improve $ln(n)$ slightly in the construction - which is not at all sophisticated -, but not so that one can reach the $n^1/2/ln(n)^1/2$ type of upper bound, which is asked.
Therefore, I guess the 'hint' here is that we should not be looking for a 'constructive' proof, but rather for an 'existence' one. Therefore, with that in mind, we write our desired polynomial as
$$P(x) = sum_a in A x^a - sum_b in B x^b.$$
Then, $(x-1)^k$ dividing $P$ means that $P(1) = P'(1) = cdots = P^(k-1)(1) = 0.$ But this implies, after some manipulations, that
$$ sum_a in A 1 = sum_b in B 1, $$
$$ sum_a in A a = sum_b in B b, $$
$$ sum_a in A a^2 = sum_b in B b^2,$$
$$ vdots $$
$$ sum_a in A a^k-1 = sum_b in B b^k-1.$$
Let then $s_k(A) = sum_a in A a^k,$ where $A subset 0,1,...,n.$ The problem can therefore be restated as follows:
There are two subsets $A,B subset 0,1,...,n$ such that $|A| = |B|$ and $s_j(A) = s_j(B), ,j=1,...,k-1.$
Notice that $A$ and $B$ need not necessarily be disjoint, as any possible overlap is 'cancelled' in the definition of $P.$
In order to solve this problem, I have been trying to use continuity arguments, like 'keep the sum unchanged by changing two elements, and the difference between the squares decreases' or something of this kind. This might indeed be helpful, but I cannot see how to take it on further than that, that is, how to use this construction for $k > 2.$
combinatorics polynomials contest-math
asked Sep 10 at 10:04
João Ramos
1,236719
There must be something missing. The polynomial $(x-1)^n$ has degree $n$, and is divisible by $(x-1)^k$ provided only $nge k$.
– Gerry Myerson
Sep 10 at 10:12
1
Anyway, the direction you are going is essentially what's known as the Tarry-Escott problem, on which there is much literature.
– Gerry Myerson
Sep 10 at 10:13
@GerryMyerson Sorry, it slipped my mind to add the condition that $-1,0,1$ are all of its coefficients. Thanks for the reminder/suggestion!
– João Ramos
Sep 10 at 10:14
So, have you checked out Tarry-Escott?
– Gerry Myerson
Sep 11 at 13:10
2
@GerryMyerson I have briefly looked into it, and even found some interesting things that could lead to a solution, but it does not seem to be a 'simple consequence' of any of the most famous theorems. Maybe there is something explicitly written about it I'm missing out on, but I still have not found it...
– João Ramos
Sep 11 at 13:12
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Recently, I came across the following problem:
It is known that $k$ and $n$ are positive integers, and that $k+1 le sqrtfracn+1ln(n+1).$ Prove that we can find a polynomial $P$ of degree $n$, whose coefficients belong to $-1,0,1,$ such that $(x-1)^k$ divides $P$
(Some background: This was proposed to me by a colleague, who stated it was from an Ukrainian IMO team selection test. I have taken a look around, but never succeeded in the task of finding an actual solution. Also, the colleague who proposed it to me did not know himself how to solve it either.)
At first, I thought a simple construction would suffice: namely, one relatively 'naive' idea is to consider products of the form
$$ (x^alpha_1 - 1)(x^alpha_2 -1) cdots (x^alpha_k -1),$$
where $alpha_1 + alpha_2 + cdots + alpha_k = n.$ Indeed, this works and yields a non-trivial result through an algorithmic method, but only when $k lesssim ln(n).$ One can improve $ln(n)$ slightly in the construction - which is not at all sophisticated -, but not so that one can reach the $n^1/2/ln(n)^1/2$ type of upper bound, which is asked.
Therefore, I guess the 'hint' here is that we should not be looking for a 'constructive' proof, but rather for an 'existence' one. Therefore, with that in mind, we write our desired polynomial as
$$P(x) = sum_a in A x^a - sum_b in B x^b.$$
Then, $(x-1)^k$ dividing $P$ means that $P(1) = P'(1) = cdots = P^(k-1)(1) = 0.$ But this implies, after some manipulations, that
$$ sum_a in A 1 = sum_b in B 1, $$
$$ sum_a in A a = sum_b in B b, $$
$$ sum_a in A a^2 = sum_b in B b^2,$$
$$ vdots $$
$$ sum_a in A a^k-1 = sum_b in B b^k-1.$$
Let then $s_k(A) = sum_a in A a^k,$ where $A subset 0,1,...,n.$ The problem can therefore be restated as follows:
There are two subsets $A,B subset 0,1,...,n$ such that $|A| = |B|$ and $s_j(A) = s_j(B), ,j=1,...,k-1.$
Notice that $A$ and $B$ need not necessarily be disjoint, as any possible overlap is 'cancelled' in the definition of $P.$
In order to solve this problem, I have been trying to use continuity arguments, like 'keep the sum unchanged by changing two elements, and the difference between the squares decreases' or something of this kind. This might indeed be helpful, but I cannot see how to take it on further than that, that is, how to use this construction for $k > 2.$
combinatorics polynomials contest-math
asked Sep 10 at 10:04
João Ramos
1,236719
Recently, I came across the following problem:
It is known that $k$ and $n$ are positive integers, and that $k+1 le sqrtfracn+1ln(n+1).$ Prove that we can find a polynomial $P$ of degree $n$, whose coefficients belong to $-1,0,1,$ such that $(x-1)^k$ divides $P$
(Some background: This was proposed to me by a colleague, who stated it was from an Ukrainian IMO team selection test. I have taken a look around, but never succeeded in the task of finding an actual solution. Also, the colleague who proposed it to me did not know himself how to solve it either.)
At first, I thought a simple construction would suffice: namely, one relatively 'naive' idea is to consider products of the form
$$ (x^alpha_1 - 1)(x^alpha_2 -1) cdots (x^alpha_k -1),$$
where $alpha_1 + alpha_2 + cdots + alpha_k = n.$ Indeed, this works and yields a non-trivial result through an algorithmic method, but only when $k lesssim ln(n).$ One can improve $ln(n)$ slightly in the construction - which is not at all sophisticated -, but not so that one can reach the $n^1/2/ln(n)^1/2$ type of upper bound, which is asked.
Therefore, I guess the 'hint' here is that we should not be looking for a 'constructive' proof, but rather for an 'existence' one. Therefore, with that in mind, we write our desired polynomial as
$$P(x) = sum_a in A x^a - sum_b in B x^b.$$
Then, $(x-1)^k$ dividing $P$ means that $P(1) = P'(1) = cdots = P^(k-1)(1) = 0.$ But this implies, after some manipulations, that
$$ sum_a in A 1 = sum_b in B 1, $$
$$ sum_a in A a = sum_b in B b, $$
$$ sum_a in A a^2 = sum_b in B b^2,$$
$$ vdots $$
$$ sum_a in A a^k-1 = sum_b in B b^k-1.$$
Let then $s_k(A) = sum_a in A a^k,$ where $A subset 0,1,...,n.$ The problem can therefore be restated as follows:
There are two subsets $A,B subset 0,1,...,n$ such that $|A| = |B|$ and $s_j(A) = s_j(B), ,j=1,...,k-1.$
Notice that $A$ and $B$ need not necessarily be disjoint, as any possible overlap is 'cancelled' in the definition of $P.$
In order to solve this problem, I have been trying to use continuity arguments, like 'keep the sum unchanged by changing two elements, and the difference between the squares decreases' or something of this kind. This might indeed be helpful, but I cannot see how to take it on further than that, that is, how to use this construction for $k > 2.$
combinatorics polynomials contest-math
combinatorics polynomials contest-math
asked Sep 10 at 10:04
João Ramos
1,236719
asked Sep 10 at 10:04
João Ramos
1,236719
edited Sep 10 at 10:13
asked Sep 10 at 10:04
João Ramos
1,236719
asked Sep 10 at 10:04
João Ramos
1,236719
asked Sep 10 at 10:04
João Ramos
1,236719
1,236719
There must be something missing. The polynomial $(x-1)^n$ has degree $n$, and is divisible by $(x-1)^k$ provided only $nge k$.
– Gerry Myerson
Sep 10 at 10:12
1
Anyway, the direction you are going is essentially what's known as the Tarry-Escott problem, on which there is much literature.
– Gerry Myerson
Sep 10 at 10:13
@GerryMyerson Sorry, it slipped my mind to add the condition that $-1,0,1$ are all of its coefficients. Thanks for the reminder/suggestion!
– João Ramos
Sep 10 at 10:14
So, have you checked out Tarry-Escott?
– Gerry Myerson
Sep 11 at 13:10
2
@GerryMyerson I have briefly looked into it, and even found some interesting things that could lead to a solution, but it does not seem to be a 'simple consequence' of any of the most famous theorems. Maybe there is something explicitly written about it I'm missing out on, but I still have not found it...
– João Ramos
Sep 11 at 13:12
add a comment |Â
There must be something missing. The polynomial $(x-1)^n$ has degree $n$, and is divisible by $(x-1)^k$ provided only $nge k$.
– Gerry Myerson
Sep 10 at 10:12
1
Anyway, the direction you are going is essentially what's known as the Tarry-Escott problem, on which there is much literature.
– Gerry Myerson
Sep 10 at 10:13
@GerryMyerson Sorry, it slipped my mind to add the condition that $-1,0,1$ are all of its coefficients. Thanks for the reminder/suggestion!
– João Ramos
Sep 10 at 10:14
So, have you checked out Tarry-Escott?
– Gerry Myerson
Sep 11 at 13:10
2
@GerryMyerson I have briefly looked into it, and even found some interesting things that could lead to a solution, but it does not seem to be a 'simple consequence' of any of the most famous theorems. Maybe there is something explicitly written about it I'm missing out on, but I still have not found it...
– João Ramos
Sep 11 at 13:12
There must be something missing. The polynomial $(x-1)^n$ has degree $n$, and is divisible by $(x-1)^k$ provided only $nge k$.
– Gerry Myerson
Sep 10 at 10:12
There must be something missing. The polynomial $(x-1)^n$ has degree $n$, and is divisible by $(x-1)^k$ provided only $nge k$.
– Gerry Myerson
Sep 10 at 10:12
1
1
Anyway, the direction you are going is essentially what's known as the Tarry-Escott problem, on which there is much literature.
– Gerry Myerson
Sep 10 at 10:13
Anyway, the direction you are going is essentially what's known as the Tarry-Escott problem, on which there is much literature.
– Gerry Myerson
Sep 10 at 10:13
@GerryMyerson Sorry, it slipped my mind to add the condition that $-1,0,1$ are all of its coefficients. Thanks for the reminder/suggestion!
– João Ramos
Sep 10 at 10:14
@GerryMyerson Sorry, it slipped my mind to add the condition that $-1,0,1$ are all of its coefficients. Thanks for the reminder/suggestion!
– João Ramos
Sep 10 at 10:14
So, have you checked out Tarry-Escott?
– Gerry Myerson
Sep 11 at 13:10
So, have you checked out Tarry-Escott?
– Gerry Myerson
Sep 11 at 13:10
2
2
@GerryMyerson I have briefly looked into it, and even found some interesting things that could lead to a solution, but it does not seem to be a 'simple consequence' of any of the most famous theorems. Maybe there is something explicitly written about it I'm missing out on, but I still have not found it...
– João Ramos
Sep 11 at 13:12
@GerryMyerson I have briefly looked into it, and even found some interesting things that could lead to a solution, but it does not seem to be a 'simple consequence' of any of the most famous theorems. Maybe there is something explicitly written about it I'm missing out on, but I still have not found it...
– João Ramos
Sep 11 at 13:12
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Actually we can prove this by the pigeon-hole principle and some (rather loose) estimation.
As written in your post, $(x-1)^k | P(x)$ if and only if $P(1) = P'(1) = cdots = P^(k-1)(1) = 0$. Therefore, the original problem holds true if we can guarantee that, denoting $mathcal S = a_i text is 0 or 1$, there exists $P_1$ and $P_2$ in $mathcal S$ such that $P^(i)_1(1) = P^(i)_2(1)$ for $i = 0, 1, cdots, k-1$.
How many elements are there in $mathcal S$? Clearly, there are $2^n+1$ of them.
How many possible values can those $P^(i)(1)$ take? Well, that is a bit more subtle. Let us look at different $i$'s. In particular, since $P$ has integral coefficient, denote by $P_0(x) = x^n + x^n-1 + cdots + x + 1 in mathcal S$ the "greediest polynomial", then $P^(i)(1)$ has to take integral value in the region $[0, P_0^(i)(1)]$.
So, we need to compute $P^(1)_0(1)$. It is not hard to show (by induction or some combinatoric equality) that
$$
beginaligned
P^(0)_0(1) &= 1 + 1 + cdots + 1 = n+1;\
P^(1)_0(1) &= n + (n-1) + cdots + 1 = frac(n+1)n2;\
P^(2)_0(1) &= n(n-1) + (n-1)(n-2) + cdots + 2cdot 1 = frac(n+1)n(n-1)3;\
&vdots\
P^(k-1)_0(1) &= frac(n+1)ncdots(n-k+2)k.
endaligned
$$
So there are at most
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right)
$$
possibilities in the combination of the derivatives.
So, in order to use the pigeon-hole, it suffices to prove that
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right) < 2^n+1.
$$
Somehow I am too lazy and sloppy to prove this, but I hope you believe that "trading the $+1$'s in the products with the denominator" is fair enough, that is:
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right) leq\
left(n+1right)Big((n+1)nBig)cdotsBig((n+1)ncdots(n-k+2)Big) = (n+1)^kn^k-1cdots(n-k+2).
$$
Therefore, it suffices to prove that
$$
(n+1)^kn^k-1cdots(n-k+2) < 2^n+1.
$$
Taking natural logarithm, it suffices to prove that
$$
lnBig((n+1)^kn^k-1cdots(n-k+2)Big) leq (n+1)ln 2.
$$
This is true, since
$$
beginaligned
lnBig((n+1)^kn^k-1cdots(n-k+2)Big) &leq lnBig((n+1)^k(n+1)^k-1cdots(n+1)Big)\
&= ln (n+1)^frac(k+1)k2 = frac(k+1)k2ln(n+1)\
&< frac(k+1)^22ln(n+1) leq fracln(n+1)2fracn+1ln(n+1)\
&= fracn+12 < 0.69(n+1) < (n+1)ln2.
endaligned
$$
answered Sep 17 at 23:28
Hw Chu
2,705416
Awesome answer, thank you very much!
– João Ramos
Sep 18 at 7:16
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Actually we can prove this by the pigeon-hole principle and some (rather loose) estimation.
As written in your post, $(x-1)^k | P(x)$ if and only if $P(1) = P'(1) = cdots = P^(k-1)(1) = 0$. Therefore, the original problem holds true if we can guarantee that, denoting $mathcal S = a_i text is 0 or 1$, there exists $P_1$ and $P_2$ in $mathcal S$ such that $P^(i)_1(1) = P^(i)_2(1)$ for $i = 0, 1, cdots, k-1$.
How many elements are there in $mathcal S$? Clearly, there are $2^n+1$ of them.
How many possible values can those $P^(i)(1)$ take? Well, that is a bit more subtle. Let us look at different $i$'s. In particular, since $P$ has integral coefficient, denote by $P_0(x) = x^n + x^n-1 + cdots + x + 1 in mathcal S$ the "greediest polynomial", then $P^(i)(1)$ has to take integral value in the region $[0, P_0^(i)(1)]$.
So, we need to compute $P^(1)_0(1)$. It is not hard to show (by induction or some combinatoric equality) that
$$
beginaligned
P^(0)_0(1) &= 1 + 1 + cdots + 1 = n+1;\
P^(1)_0(1) &= n + (n-1) + cdots + 1 = frac(n+1)n2;\
P^(2)_0(1) &= n(n-1) + (n-1)(n-2) + cdots + 2cdot 1 = frac(n+1)n(n-1)3;\
&vdots\
P^(k-1)_0(1) &= frac(n+1)ncdots(n-k+2)k.
endaligned
$$
So there are at most
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right)
$$
possibilities in the combination of the derivatives.
So, in order to use the pigeon-hole, it suffices to prove that
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right) < 2^n+1.
$$
Somehow I am too lazy and sloppy to prove this, but I hope you believe that "trading the $+1$'s in the products with the denominator" is fair enough, that is:
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right) leq\
left(n+1right)Big((n+1)nBig)cdotsBig((n+1)ncdots(n-k+2)Big) = (n+1)^kn^k-1cdots(n-k+2).
$$
Therefore, it suffices to prove that
$$
(n+1)^kn^k-1cdots(n-k+2) < 2^n+1.
$$
Taking natural logarithm, it suffices to prove that
$$
lnBig((n+1)^kn^k-1cdots(n-k+2)Big) leq (n+1)ln 2.
$$
This is true, since
$$
beginaligned
lnBig((n+1)^kn^k-1cdots(n-k+2)Big) &leq lnBig((n+1)^k(n+1)^k-1cdots(n+1)Big)\
&= ln (n+1)^frac(k+1)k2 = frac(k+1)k2ln(n+1)\
&< frac(k+1)^22ln(n+1) leq fracln(n+1)2fracn+1ln(n+1)\
&= fracn+12 < 0.69(n+1) < (n+1)ln2.
endaligned
$$
answered Sep 17 at 23:28
Hw Chu
2,705416
Awesome answer, thank you very much!
– João Ramos
Sep 18 at 7:16
add a comment |Â
up vote
2
down vote
accepted
Actually we can prove this by the pigeon-hole principle and some (rather loose) estimation.
As written in your post, $(x-1)^k | P(x)$ if and only if $P(1) = P'(1) = cdots = P^(k-1)(1) = 0$. Therefore, the original problem holds true if we can guarantee that, denoting $mathcal S = a_i text is 0 or 1$, there exists $P_1$ and $P_2$ in $mathcal S$ such that $P^(i)_1(1) = P^(i)_2(1)$ for $i = 0, 1, cdots, k-1$.
How many elements are there in $mathcal S$? Clearly, there are $2^n+1$ of them.
How many possible values can those $P^(i)(1)$ take? Well, that is a bit more subtle. Let us look at different $i$'s. In particular, since $P$ has integral coefficient, denote by $P_0(x) = x^n + x^n-1 + cdots + x + 1 in mathcal S$ the "greediest polynomial", then $P^(i)(1)$ has to take integral value in the region $[0, P_0^(i)(1)]$.
So, we need to compute $P^(1)_0(1)$. It is not hard to show (by induction or some combinatoric equality) that
$$
beginaligned
P^(0)_0(1) &= 1 + 1 + cdots + 1 = n+1;\
P^(1)_0(1) &= n + (n-1) + cdots + 1 = frac(n+1)n2;\
P^(2)_0(1) &= n(n-1) + (n-1)(n-2) + cdots + 2cdot 1 = frac(n+1)n(n-1)3;\
&vdots\
P^(k-1)_0(1) &= frac(n+1)ncdots(n-k+2)k.
endaligned
$$
So there are at most
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right)
$$
possibilities in the combination of the derivatives.
So, in order to use the pigeon-hole, it suffices to prove that
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right) < 2^n+1.
$$
Somehow I am too lazy and sloppy to prove this, but I hope you believe that "trading the $+1$'s in the products with the denominator" is fair enough, that is:
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right) leq\
left(n+1right)Big((n+1)nBig)cdotsBig((n+1)ncdots(n-k+2)Big) = (n+1)^kn^k-1cdots(n-k+2).
$$
Therefore, it suffices to prove that
$$
(n+1)^kn^k-1cdots(n-k+2) < 2^n+1.
$$
Taking natural logarithm, it suffices to prove that
$$
lnBig((n+1)^kn^k-1cdots(n-k+2)Big) leq (n+1)ln 2.
$$
This is true, since
$$
beginaligned
lnBig((n+1)^kn^k-1cdots(n-k+2)Big) &leq lnBig((n+1)^k(n+1)^k-1cdots(n+1)Big)\
&= ln (n+1)^frac(k+1)k2 = frac(k+1)k2ln(n+1)\
&< frac(k+1)^22ln(n+1) leq fracln(n+1)2fracn+1ln(n+1)\
&= fracn+12 < 0.69(n+1) < (n+1)ln2.
endaligned
$$
answered Sep 17 at 23:28
Hw Chu
2,705416
Awesome answer, thank you very much!
– João Ramos
Sep 18 at 7:16
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Actually we can prove this by the pigeon-hole principle and some (rather loose) estimation.
As written in your post, $(x-1)^k | P(x)$ if and only if $P(1) = P'(1) = cdots = P^(k-1)(1) = 0$. Therefore, the original problem holds true if we can guarantee that, denoting $mathcal S = a_i text is 0 or 1$, there exists $P_1$ and $P_2$ in $mathcal S$ such that $P^(i)_1(1) = P^(i)_2(1)$ for $i = 0, 1, cdots, k-1$.
How many elements are there in $mathcal S$? Clearly, there are $2^n+1$ of them.
How many possible values can those $P^(i)(1)$ take? Well, that is a bit more subtle. Let us look at different $i$'s. In particular, since $P$ has integral coefficient, denote by $P_0(x) = x^n + x^n-1 + cdots + x + 1 in mathcal S$ the "greediest polynomial", then $P^(i)(1)$ has to take integral value in the region $[0, P_0^(i)(1)]$.
So, we need to compute $P^(1)_0(1)$. It is not hard to show (by induction or some combinatoric equality) that
$$
beginaligned
P^(0)_0(1) &= 1 + 1 + cdots + 1 = n+1;\
P^(1)_0(1) &= n + (n-1) + cdots + 1 = frac(n+1)n2;\
P^(2)_0(1) &= n(n-1) + (n-1)(n-2) + cdots + 2cdot 1 = frac(n+1)n(n-1)3;\
&vdots\
P^(k-1)_0(1) &= frac(n+1)ncdots(n-k+2)k.
endaligned
$$
So there are at most
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right)
$$
possibilities in the combination of the derivatives.
So, in order to use the pigeon-hole, it suffices to prove that
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right) < 2^n+1.
$$
Somehow I am too lazy and sloppy to prove this, but I hope you believe that "trading the $+1$'s in the products with the denominator" is fair enough, that is:
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right) leq\
left(n+1right)Big((n+1)nBig)cdotsBig((n+1)ncdots(n-k+2)Big) = (n+1)^kn^k-1cdots(n-k+2).
$$
Therefore, it suffices to prove that
$$
(n+1)^kn^k-1cdots(n-k+2) < 2^n+1.
$$
Taking natural logarithm, it suffices to prove that
$$
lnBig((n+1)^kn^k-1cdots(n-k+2)Big) leq (n+1)ln 2.
$$
This is true, since
$$
beginaligned
lnBig((n+1)^kn^k-1cdots(n-k+2)Big) &leq lnBig((n+1)^k(n+1)^k-1cdots(n+1)Big)\
&= ln (n+1)^frac(k+1)k2 = frac(k+1)k2ln(n+1)\
&< frac(k+1)^22ln(n+1) leq fracln(n+1)2fracn+1ln(n+1)\
&= fracn+12 < 0.69(n+1) < (n+1)ln2.
endaligned
$$
answered Sep 17 at 23:28
Hw Chu
2,705416
Actually we can prove this by the pigeon-hole principle and some (rather loose) estimation.
As written in your post, $(x-1)^k | P(x)$ if and only if $P(1) = P'(1) = cdots = P^(k-1)(1) = 0$. Therefore, the original problem holds true if we can guarantee that, denoting $mathcal S = a_i text is 0 or 1$, there exists $P_1$ and $P_2$ in $mathcal S$ such that $P^(i)_1(1) = P^(i)_2(1)$ for $i = 0, 1, cdots, k-1$.
How many elements are there in $mathcal S$? Clearly, there are $2^n+1$ of them.
How many possible values can those $P^(i)(1)$ take? Well, that is a bit more subtle. Let us look at different $i$'s. In particular, since $P$ has integral coefficient, denote by $P_0(x) = x^n + x^n-1 + cdots + x + 1 in mathcal S$ the "greediest polynomial", then $P^(i)(1)$ has to take integral value in the region $[0, P_0^(i)(1)]$.
So, we need to compute $P^(1)_0(1)$. It is not hard to show (by induction or some combinatoric equality) that
$$
beginaligned
P^(0)_0(1) &= 1 + 1 + cdots + 1 = n+1;\
P^(1)_0(1) &= n + (n-1) + cdots + 1 = frac(n+1)n2;\
P^(2)_0(1) &= n(n-1) + (n-1)(n-2) + cdots + 2cdot 1 = frac(n+1)n(n-1)3;\
&vdots\
P^(k-1)_0(1) &= frac(n+1)ncdots(n-k+2)k.
endaligned
$$
So there are at most
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right)
$$
possibilities in the combination of the derivatives.
So, in order to use the pigeon-hole, it suffices to prove that
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right) < 2^n+1.
$$
Somehow I am too lazy and sloppy to prove this, but I hope you believe that "trading the $+1$'s in the products with the denominator" is fair enough, that is:
$$
left((n+1)+1right)left(frac(n+1)n2+1right)cdotsleft(frac(n+1)ncdots(n-k+2)k + 1right) leq\
left(n+1right)Big((n+1)nBig)cdotsBig((n+1)ncdots(n-k+2)Big) = (n+1)^kn^k-1cdots(n-k+2).
$$
Therefore, it suffices to prove that
$$
(n+1)^kn^k-1cdots(n-k+2) < 2^n+1.
$$
Taking natural logarithm, it suffices to prove that
$$
lnBig((n+1)^kn^k-1cdots(n-k+2)Big) leq (n+1)ln 2.
$$
This is true, since
$$
beginaligned
lnBig((n+1)^kn^k-1cdots(n-k+2)Big) &leq lnBig((n+1)^k(n+1)^k-1cdots(n+1)Big)\
&= ln (n+1)^frac(k+1)k2 = frac(k+1)k2ln(n+1)\
&< frac(k+1)^22ln(n+1) leq fracln(n+1)2fracn+1ln(n+1)\
&= fracn+12 < 0.69(n+1) < (n+1)ln2.
endaligned
$$
answered Sep 17 at 23:28
Hw Chu
2,705416
answered Sep 17 at 23:28
Hw Chu
2,705416
answered Sep 17 at 23:28
Hw Chu
2,705416
answered Sep 17 at 23:28
Hw Chu
2,705416
2,705416
Awesome answer, thank you very much!
– João Ramos
Sep 18 at 7:16
add a comment |Â
Awesome answer, thank you very much!
– João Ramos
Sep 18 at 7:16
Awesome answer, thank you very much!
– João Ramos
Sep 18 at 7:16
Awesome answer, thank you very much!
– João Ramos
Sep 18 at 7:16
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2911757%2fsums-of-powers-of-elements-in-a-subset-and-polynomial-with-1-0-1-coeffici%23new-answer', 'question_page');
);
Post as a guest
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
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
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
There must be something missing. The polynomial $(x-1)^n$ has degree $n$, and is divisible by $(x-1)^k$ provided only $nge k$.
– Gerry Myerson
Sep 10 at 10:12
1
Anyway, the direction you are going is essentially what's known as the Tarry-Escott problem, on which there is much literature.
– Gerry Myerson
Sep 10 at 10:13
@GerryMyerson Sorry, it slipped my mind to add the condition that $-1,0,1$ are all of its coefficients. Thanks for the reminder/suggestion!
– João Ramos
Sep 10 at 10:14
So, have you checked out Tarry-Escott?
– Gerry Myerson
Sep 11 at 13:10
2
@GerryMyerson I have briefly looked into it, and even found some interesting things that could lead to a solution, but it does not seem to be a 'simple consequence' of any of the most famous theorems. Maybe there is something explicitly written about it I'm missing out on, but I still have not found it...
– João Ramos
Sep 11 at 13:12