Mixing
Even polynomial having multiple with odd coefficients
up vote
1
down vote
favorite
Let $Q in mathbb{Z}/2mathbb{Z}[X]$ be a non constant polynomial such that all coefficients of odd order are $0$, i.e. $Q = sum a_k X^{2k}$. Show that if $P in mathbb{Z}/2mathbb{Z}[X]$ is such that all the coefficients of $PQ$ are odd, then the degree of $P$ is odd.
This is a conjecture that I made. I believe it is true but have no proof for it.
At first I thought that no multiples of $Q$ could have all coefficients odd. I quickly found counterexamples : $$(1+X^2)*(1+X) = 1+X+X^2+X^3$$
and more generally, for any even $n$, $$Big(sum limits_{k=0}^m X^{kn}Big)cdot Big(sumlimits_{k=0}^{m-1} X^kBig) = sum limits_{k=0}^{(m+1)n-1} X^k$$
I also found weirder counterexamples, like $$(1+X^4+X^6)(1+X+X^2+X^3+X^6+X^7)=sumlimits_{k=0}^{13} X^k + 2X^7+2X^6$$
I could not find polynomials with odd degree. I tried to work in $mathbb{Z}/2mathbb{Z}$ and get information on the coefficients but it was not really conclusive. If $Q$ can be written $sumlimits_{k=0}^m X^{kn}$ for some even $n$, then I have a proof, but in the general case, the coefficients of $Q$ can be quite random (see my last example).
$ $
*Note: this problem arose during a math contest, which ended on 04/11/2018
polynomials modular-arithmetic arithmetic
asked Nov 5 at 12:04
Charles Madeline
3,2571837
|
show 2 more comments
up vote
1
down vote
favorite
Let $Q in mathbb{Z}/2mathbb{Z}[X]$ be a non constant polynomial such that all coefficients of odd order are $0$, i.e. $Q = sum a_k X^{2k}$. Show that if $P in mathbb{Z}/2mathbb{Z}[X]$ is such that all the coefficients of $PQ$ are odd, then the degree of $P$ is odd.
This is a conjecture that I made. I believe it is true but have no proof for it.
At first I thought that no multiples of $Q$ could have all coefficients odd. I quickly found counterexamples : $$(1+X^2)*(1+X) = 1+X+X^2+X^3$$
and more generally, for any even $n$, $$Big(sum limits_{k=0}^m X^{kn}Big)cdot Big(sumlimits_{k=0}^{m-1} X^kBig) = sum limits_{k=0}^{(m+1)n-1} X^k$$
I also found weirder counterexamples, like $$(1+X^4+X^6)(1+X+X^2+X^3+X^6+X^7)=sumlimits_{k=0}^{13} X^k + 2X^7+2X^6$$
I could not find polynomials with odd degree. I tried to work in $mathbb{Z}/2mathbb{Z}$ and get information on the coefficients but it was not really conclusive. If $Q$ can be written $sumlimits_{k=0}^m X^{kn}$ for some even $n$, then I have a proof, but in the general case, the coefficients of $Q$ can be quite random (see my last example).
$ $
*Note: this problem arose during a math contest, which ended on 04/11/2018
polynomials modular-arithmetic arithmetic
asked Nov 5 at 12:04
Charles Madeline
3,2571837
$P$ is non constant also (it is clear that it is understood but......).
– Piquito
Nov 5 at 13:21
@Piquito Actually $P$ cannot be constant : $Q$ is not constant, so it has at least one zero coefficient (the coeff with $X$). $P$ can be either odd or even, the $X$ coefficient of $PQ$ will always be zero. Which is not odd
– Charles Madeline
Nov 5 at 13:40
I don't see any reason why this conjecture or anything similar would be true. There's no link between the parity of the polynomial function $P$ and the parity of the coefficients of $P$. The polynomial $P(x) = 1+x^2$ is even, and yet all its coefficients are odd... What do you base this conjecture on?
– Najib Idrissi
Nov 5 at 13:49
@NajibIdrissi $P = 1 + 0cdot X + X^2$ does not have only odd coefficients. All the coefficients before the terms $X^{2k+1}$ are zero (and thus even) for an even polynomial
– Charles Madeline
Nov 5 at 13:59
Right. But it still has two odd coefficients. There's no connection...
– Najib Idrissi
Nov 5 at 14:01
|
show 2 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let $Q in mathbb{Z}/2mathbb{Z}[X]$ be a non constant polynomial such that all coefficients of odd order are $0$, i.e. $Q = sum a_k X^{2k}$. Show that if $P in mathbb{Z}/2mathbb{Z}[X]$ is such that all the coefficients of $PQ$ are odd, then the degree of $P$ is odd.
This is a conjecture that I made. I believe it is true but have no proof for it.
At first I thought that no multiples of $Q$ could have all coefficients odd. I quickly found counterexamples : $$(1+X^2)*(1+X) = 1+X+X^2+X^3$$
and more generally, for any even $n$, $$Big(sum limits_{k=0}^m X^{kn}Big)cdot Big(sumlimits_{k=0}^{m-1} X^kBig) = sum limits_{k=0}^{(m+1)n-1} X^k$$
I also found weirder counterexamples, like $$(1+X^4+X^6)(1+X+X^2+X^3+X^6+X^7)=sumlimits_{k=0}^{13} X^k + 2X^7+2X^6$$
I could not find polynomials with odd degree. I tried to work in $mathbb{Z}/2mathbb{Z}$ and get information on the coefficients but it was not really conclusive. If $Q$ can be written $sumlimits_{k=0}^m X^{kn}$ for some even $n$, then I have a proof, but in the general case, the coefficients of $Q$ can be quite random (see my last example).
$ $
*Note: this problem arose during a math contest, which ended on 04/11/2018
polynomials modular-arithmetic arithmetic
asked Nov 5 at 12:04
Charles Madeline
3,2571837
Let $Q in mathbb{Z}/2mathbb{Z}[X]$ be a non constant polynomial such that all coefficients of odd order are $0$, i.e. $Q = sum a_k X^{2k}$. Show that if $P in mathbb{Z}/2mathbb{Z}[X]$ is such that all the coefficients of $PQ$ are odd, then the degree of $P$ is odd.
This is a conjecture that I made. I believe it is true but have no proof for it.
At first I thought that no multiples of $Q$ could have all coefficients odd. I quickly found counterexamples : $$(1+X^2)*(1+X) = 1+X+X^2+X^3$$
and more generally, for any even $n$, $$Big(sum limits_{k=0}^m X^{kn}Big)cdot Big(sumlimits_{k=0}^{m-1} X^kBig) = sum limits_{k=0}^{(m+1)n-1} X^k$$
I also found weirder counterexamples, like $$(1+X^4+X^6)(1+X+X^2+X^3+X^6+X^7)=sumlimits_{k=0}^{13} X^k + 2X^7+2X^6$$
I could not find polynomials with odd degree. I tried to work in $mathbb{Z}/2mathbb{Z}$ and get information on the coefficients but it was not really conclusive. If $Q$ can be written $sumlimits_{k=0}^m X^{kn}$ for some even $n$, then I have a proof, but in the general case, the coefficients of $Q$ can be quite random (see my last example).
$ $
*Note: this problem arose during a math contest, which ended on 04/11/2018
polynomials modular-arithmetic arithmetic
polynomials modular-arithmetic arithmetic
asked Nov 5 at 12:04
Charles Madeline
3,2571837
asked Nov 5 at 12:04
Charles Madeline
3,2571837
edited Nov 5 at 13:58
asked Nov 5 at 12:04
Charles Madeline
3,2571837
asked Nov 5 at 12:04
Charles Madeline
3,2571837
asked Nov 5 at 12:04
Charles Madeline
3,2571837
3,2571837
$P$ is non constant also (it is clear that it is understood but......).
– Piquito
Nov 5 at 13:21
@Piquito Actually $P$ cannot be constant : $Q$ is not constant, so it has at least one zero coefficient (the coeff with $X$). $P$ can be either odd or even, the $X$ coefficient of $PQ$ will always be zero. Which is not odd
– Charles Madeline
Nov 5 at 13:40
I don't see any reason why this conjecture or anything similar would be true. There's no link between the parity of the polynomial function $P$ and the parity of the coefficients of $P$. The polynomial $P(x) = 1+x^2$ is even, and yet all its coefficients are odd... What do you base this conjecture on?
– Najib Idrissi
Nov 5 at 13:49
@NajibIdrissi $P = 1 + 0cdot X + X^2$ does not have only odd coefficients. All the coefficients before the terms $X^{2k+1}$ are zero (and thus even) for an even polynomial
– Charles Madeline
Nov 5 at 13:59
Right. But it still has two odd coefficients. There's no connection...
– Najib Idrissi
Nov 5 at 14:01
|
show 2 more comments
$P$ is non constant also (it is clear that it is understood but......).
– Piquito
Nov 5 at 13:21
@Piquito Actually $P$ cannot be constant : $Q$ is not constant, so it has at least one zero coefficient (the coeff with $X$). $P$ can be either odd or even, the $X$ coefficient of $PQ$ will always be zero. Which is not odd
– Charles Madeline
Nov 5 at 13:40
I don't see any reason why this conjecture or anything similar would be true. There's no link between the parity of the polynomial function $P$ and the parity of the coefficients of $P$. The polynomial $P(x) = 1+x^2$ is even, and yet all its coefficients are odd... What do you base this conjecture on?
– Najib Idrissi
Nov 5 at 13:49
@NajibIdrissi $P = 1 + 0cdot X + X^2$ does not have only odd coefficients. All the coefficients before the terms $X^{2k+1}$ are zero (and thus even) for an even polynomial
– Charles Madeline
Nov 5 at 13:59
Right. But it still has two odd coefficients. There's no connection...
– Najib Idrissi
Nov 5 at 14:01
$P$ is non constant also (it is clear that it is understood but......).
– Piquito
Nov 5 at 13:21
$P$ is non constant also (it is clear that it is understood but......).
– Piquito
Nov 5 at 13:21
@Piquito Actually $P$ cannot be constant : $Q$ is not constant, so it has at least one zero coefficient (the coeff with $X$). $P$ can be either odd or even, the $X$ coefficient of $PQ$ will always be zero. Which is not odd
– Charles Madeline
Nov 5 at 13:40
@Piquito Actually $P$ cannot be constant : $Q$ is not constant, so it has at least one zero coefficient (the coeff with $X$). $P$ can be either odd or even, the $X$ coefficient of $PQ$ will always be zero. Which is not odd
– Charles Madeline
Nov 5 at 13:40
I don't see any reason why this conjecture or anything similar would be true. There's no link between the parity of the polynomial function $P$ and the parity of the coefficients of $P$. The polynomial $P(x) = 1+x^2$ is even, and yet all its coefficients are odd... What do you base this conjecture on?
– Najib Idrissi
Nov 5 at 13:49
I don't see any reason why this conjecture or anything similar would be true. There's no link between the parity of the polynomial function $P$ and the parity of the coefficients of $P$. The polynomial $P(x) = 1+x^2$ is even, and yet all its coefficients are odd... What do you base this conjecture on?
– Najib Idrissi
Nov 5 at 13:49
@NajibIdrissi $P = 1 + 0cdot X + X^2$ does not have only odd coefficients. All the coefficients before the terms $X^{2k+1}$ are zero (and thus even) for an even polynomial
– Charles Madeline
Nov 5 at 13:59
@NajibIdrissi $P = 1 + 0cdot X + X^2$ does not have only odd coefficients. All the coefficients before the terms $X^{2k+1}$ are zero (and thus even) for an even polynomial
– Charles Madeline
Nov 5 at 13:59
Right. But it still has two odd coefficients. There's no connection...
– Najib Idrissi
Nov 5 at 14:01
Right. But it still has two odd coefficients. There's no connection...
– Najib Idrissi
Nov 5 at 14:01
|
show 2 more comments
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
It's true in general. It suffices to show that $PQ$ has odd degree. Suppose to the contrary that there exist some $P,Qinmathbb F_2[x]$ subject to the constraints outlined in the OP for which $PQ=1+x+cdots+x^{2n}=frac{x^{2n+1}-1}{x-1}$. Observe by Frobenius that $sum a_kx^{2k}=left(sum a_kx^kright)^2$ in $mathbb F_2[x]$. We shall prove that $1+x+cdots+x^{2n}$ is squarefree; this clearly implies the result. Indeed, begin{align*}gcdleft(1+x+cdots+x^{2n},left(1+x+cdots+x^{2n}right)'right)&=gcdleft(1+x+cdots+x^{2n},1+x^2+cdots+x^{2n-2}right)\&=gcdleft(1+x+cdots+x^{2n},left(1+x+cdots+x^{n-1}right)^2right)\&=gcdleft(tfrac{x^{2n+1}-1}{x-1},left(tfrac{x^{n}-1}{x-1}right)^2right)=1end{align*}
Where the last equality follows from the identity $gcd(x^m-1,x^n-1)=x^{gcd(m,n)}-1$ $blacksquare$
edited 2 days ago
darij grinberg
9,89532961
answered Nov 5 at 18:27
Rafay Ashary
7118
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
It's true in general. It suffices to show that $PQ$ has odd degree. Suppose to the contrary that there exist some $P,Qinmathbb F_2[x]$ subject to the constraints outlined in the OP for which $PQ=1+x+cdots+x^{2n}=frac{x^{2n+1}-1}{x-1}$. Observe by Frobenius that $sum a_kx^{2k}=left(sum a_kx^kright)^2$ in $mathbb F_2[x]$. We shall prove that $1+x+cdots+x^{2n}$ is squarefree; this clearly implies the result. Indeed, begin{align*}gcdleft(1+x+cdots+x^{2n},left(1+x+cdots+x^{2n}right)'right)&=gcdleft(1+x+cdots+x^{2n},1+x^2+cdots+x^{2n-2}right)\&=gcdleft(1+x+cdots+x^{2n},left(1+x+cdots+x^{n-1}right)^2right)\&=gcdleft(tfrac{x^{2n+1}-1}{x-1},left(tfrac{x^{n}-1}{x-1}right)^2right)=1end{align*}
Where the last equality follows from the identity $gcd(x^m-1,x^n-1)=x^{gcd(m,n)}-1$ $blacksquare$
edited 2 days ago
darij grinberg
9,89532961
answered Nov 5 at 18:27
Rafay Ashary
7118
add a comment |
up vote
2
down vote
accepted
It's true in general. It suffices to show that $PQ$ has odd degree. Suppose to the contrary that there exist some $P,Qinmathbb F_2[x]$ subject to the constraints outlined in the OP for which $PQ=1+x+cdots+x^{2n}=frac{x^{2n+1}-1}{x-1}$. Observe by Frobenius that $sum a_kx^{2k}=left(sum a_kx^kright)^2$ in $mathbb F_2[x]$. We shall prove that $1+x+cdots+x^{2n}$ is squarefree; this clearly implies the result. Indeed, begin{align*}gcdleft(1+x+cdots+x^{2n},left(1+x+cdots+x^{2n}right)'right)&=gcdleft(1+x+cdots+x^{2n},1+x^2+cdots+x^{2n-2}right)\&=gcdleft(1+x+cdots+x^{2n},left(1+x+cdots+x^{n-1}right)^2right)\&=gcdleft(tfrac{x^{2n+1}-1}{x-1},left(tfrac{x^{n}-1}{x-1}right)^2right)=1end{align*}
Where the last equality follows from the identity $gcd(x^m-1,x^n-1)=x^{gcd(m,n)}-1$ $blacksquare$
edited 2 days ago
darij grinberg
9,89532961
answered Nov 5 at 18:27
Rafay Ashary
7118
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
It's true in general. It suffices to show that $PQ$ has odd degree. Suppose to the contrary that there exist some $P,Qinmathbb F_2[x]$ subject to the constraints outlined in the OP for which $PQ=1+x+cdots+x^{2n}=frac{x^{2n+1}-1}{x-1}$. Observe by Frobenius that $sum a_kx^{2k}=left(sum a_kx^kright)^2$ in $mathbb F_2[x]$. We shall prove that $1+x+cdots+x^{2n}$ is squarefree; this clearly implies the result. Indeed, begin{align*}gcdleft(1+x+cdots+x^{2n},left(1+x+cdots+x^{2n}right)'right)&=gcdleft(1+x+cdots+x^{2n},1+x^2+cdots+x^{2n-2}right)\&=gcdleft(1+x+cdots+x^{2n},left(1+x+cdots+x^{n-1}right)^2right)\&=gcdleft(tfrac{x^{2n+1}-1}{x-1},left(tfrac{x^{n}-1}{x-1}right)^2right)=1end{align*}
Where the last equality follows from the identity $gcd(x^m-1,x^n-1)=x^{gcd(m,n)}-1$ $blacksquare$
edited 2 days ago
darij grinberg
9,89532961
answered Nov 5 at 18:27
Rafay Ashary
7118
It's true in general. It suffices to show that $PQ$ has odd degree. Suppose to the contrary that there exist some $P,Qinmathbb F_2[x]$ subject to the constraints outlined in the OP for which $PQ=1+x+cdots+x^{2n}=frac{x^{2n+1}-1}{x-1}$. Observe by Frobenius that $sum a_kx^{2k}=left(sum a_kx^kright)^2$ in $mathbb F_2[x]$. We shall prove that $1+x+cdots+x^{2n}$ is squarefree; this clearly implies the result. Indeed, begin{align*}gcdleft(1+x+cdots+x^{2n},left(1+x+cdots+x^{2n}right)'right)&=gcdleft(1+x+cdots+x^{2n},1+x^2+cdots+x^{2n-2}right)\&=gcdleft(1+x+cdots+x^{2n},left(1+x+cdots+x^{n-1}right)^2right)\&=gcdleft(tfrac{x^{2n+1}-1}{x-1},left(tfrac{x^{n}-1}{x-1}right)^2right)=1end{align*}
Where the last equality follows from the identity $gcd(x^m-1,x^n-1)=x^{gcd(m,n)}-1$ $blacksquare$
edited 2 days ago
darij grinberg
9,89532961
answered Nov 5 at 18:27
Rafay Ashary
7118
edited 2 days ago
darij grinberg
9,89532961
edited 2 days ago
darij grinberg
9,89532961
edited 2 days ago
darij grinberg
9,89532961
9,89532961
answered Nov 5 at 18:27
Rafay Ashary
7118
answered Nov 5 at 18:27
Rafay Ashary
7118
answered Nov 5 at 18:27
Rafay Ashary
7118
7118
add a comment |
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2985667%2feven-polynomial-having-multiple-with-odd-coefficients%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
$P$ is non constant also (it is clear that it is understood but......).
– Piquito
Nov 5 at 13:21
@Piquito Actually $P$ cannot be constant : $Q$ is not constant, so it has at least one zero coefficient (the coeff with $X$). $P$ can be either odd or even, the $X$ coefficient of $PQ$ will always be zero. Which is not odd
– Charles Madeline
Nov 5 at 13:40
I don't see any reason why this conjecture or anything similar would be true. There's no link between the parity of the polynomial function $P$ and the parity of the coefficients of $P$. The polynomial $P(x) = 1+x^2$ is even, and yet all its coefficients are odd... What do you base this conjecture on?
– Najib Idrissi
Nov 5 at 13:49
@NajibIdrissi $P = 1 + 0cdot X + X^2$ does not have only odd coefficients. All the coefficients before the terms $X^{2k+1}$ are zero (and thus even) for an even polynomial
– Charles Madeline
Nov 5 at 13:59
Right. But it still has two odd coefficients. There's no connection...
– Najib Idrissi
Nov 5 at 14:01