Root of unity filterEvaluation of ratio of two binomial expressionCounting some vanishing polynomials in $mathbbZ_n[X]$Sum of every $k$th binomial coefficient.Sixth Root of UnityRoot of unity paradox$x^n+a_n-1x^n-1+cdots +a_1x+a_0=0$ has real coefficients which satisfy $0<a_0 le a_1 le cdots le a_n-1 le 1$ prove that $z$ is a rootWhat is the sum of ALL of the nth powers of the qth roots of unity?Confusion regarding logic in paper, “A NOTE ON THE INVERSION OF POWER SERIES,” published in the AMS journalProve that if B(0) = 0, then A(B(x)) is a formal power seriesFinding a polynomial with rational coefficients that has the reciprocal of a complex number as its rootfind $a_1+a_3+a_5+cdots+a_37+a_39$
Understanding Python syntax in lists vs series
Can my American children re-enter the USA by International flight with a passport card? Being that their passport book has expired
Is there an academic word that means "to split hairs over"?
Why are goodwill impairments on the statement of cash-flows of GE?
What color to choose as "danger" if the main color of my app is red
Would life always name the light from their sun "white"
What metal is most suitable for a ladder submerged in an underground water tank?
How will the lack of ground stations affect navigation?
How might a landlocked lake become a complete ecosystem?
Why did Varys remove his rings?
Slice a list based on an index and items behind it in python
Why did the metro bus stop at each railway crossing, despite no warning indicating a train was coming?
c++ conditional uni-directional iterator
Meaning of "legitimate" in Carl Jung's quote "Neurosis is always a substitute for legitimate suffering."
Does the Rogue's Reliable Talent feature work for thieves' tools, since the rogue is proficient in them?
How to not get blinded by an attack at dawn
Developers demotivated due to working on same project for more than 2 years
How could it be that 80% of townspeople were farmers during the Edo period in Japan?
What is the effect of the Feeblemind spell on Ability Score Improvements?
Holding rent money for my friend which amounts to over $10k?
Are there microwaves to heat baby food at Brussels airport?
Single word that parallels "Recent" when discussing the near future
the correct order of manual install WP and SSL on server
How did the horses get to space?
Root of unity filter
Evaluation of ratio of two binomial expressionCounting some vanishing polynomials in $mathbbZ_n[X]$Sum of every $k$th binomial coefficient.Sixth Root of UnityRoot of unity paradox$x^n+a_n-1x^n-1+cdots +a_1x+a_0=0$ has real coefficients which satisfy $0<a_0 le a_1 le cdots le a_n-1 le 1$ prove that $z$ is a rootWhat is the sum of ALL of the nth powers of the qth roots of unity?Confusion regarding logic in paper, “A NOTE ON THE INVERSION OF POWER SERIES,” published in the AMS journalProve that if B(0) = 0, then A(B(x)) is a formal power seriesFinding a polynomial with rational coefficients that has the reciprocal of a complex number as its rootfind $a_1+a_3+a_5+cdots+a_37+a_39$
$begingroup$
Can some one help me understand the technique called "Root of unity filter" . I just know how to use it. It's as follow:
For series $f(x)=a_0+a_1x+a_2x^2 cdots a_nx^n$ we need to find the sum of coefficient of terms in which the power is a multiple of any number say $k$ for finding the same we have $omega $ as $mathrmk^th$ of unity and write
$$ dfracf(1)+f(omega)+f(omega ^2) cdots (omega^k-1)k=(a_0 + a_k + a_2k cdots)$$
please help me understand why and how this works , I tried googling but didn't get any satisfactory answer
combinatorics complex-numbers binomial-theorem
$endgroup$
add a comment |
$begingroup$
Can some one help me understand the technique called "Root of unity filter" . I just know how to use it. It's as follow:
For series $f(x)=a_0+a_1x+a_2x^2 cdots a_nx^n$ we need to find the sum of coefficient of terms in which the power is a multiple of any number say $k$ for finding the same we have $omega $ as $mathrmk^th$ of unity and write
$$ dfracf(1)+f(omega)+f(omega ^2) cdots (omega^k-1)k=(a_0 + a_k + a_2k cdots)$$
please help me understand why and how this works , I tried googling but didn't get any satisfactory answer
combinatorics complex-numbers binomial-theorem
$endgroup$
$begingroup$
Never heard of this, so I'm just curious. But what's the utility of this theorem when we know the polynomial directly? Isn't it better to directly sum the coefficients than to evaluate the entire polynomial at every root of unity up to the $k$th?
$endgroup$
– Allawonder
May 4 at 9:43
$begingroup$
I was doing a question which is as follow : $$(1+x)(1+x^2) cdots (1+x^2070)$$ we have to find the sum of coefficients of $x^9k$ to get the answer here we can easily find the answer using this tool , can you suggest another method @Allawonder
$endgroup$
– Advil Sell
May 4 at 9:50
$begingroup$
I now see how it may be used for facility in some cases. I had been simply thinking of a polynomial strictly in the form $sum a_nx^n.$
$endgroup$
– Allawonder
May 4 at 9:52
add a comment |
$begingroup$
Can some one help me understand the technique called "Root of unity filter" . I just know how to use it. It's as follow:
For series $f(x)=a_0+a_1x+a_2x^2 cdots a_nx^n$ we need to find the sum of coefficient of terms in which the power is a multiple of any number say $k$ for finding the same we have $omega $ as $mathrmk^th$ of unity and write
$$ dfracf(1)+f(omega)+f(omega ^2) cdots (omega^k-1)k=(a_0 + a_k + a_2k cdots)$$
please help me understand why and how this works , I tried googling but didn't get any satisfactory answer
combinatorics complex-numbers binomial-theorem
$endgroup$
Can some one help me understand the technique called "Root of unity filter" . I just know how to use it. It's as follow:
For series $f(x)=a_0+a_1x+a_2x^2 cdots a_nx^n$ we need to find the sum of coefficient of terms in which the power is a multiple of any number say $k$ for finding the same we have $omega $ as $mathrmk^th$ of unity and write
$$ dfracf(1)+f(omega)+f(omega ^2) cdots (omega^k-1)k=(a_0 + a_k + a_2k cdots)$$
please help me understand why and how this works , I tried googling but didn't get any satisfactory answer
combinatorics complex-numbers binomial-theorem
combinatorics complex-numbers binomial-theorem
asked May 4 at 9:16
Advil SellAdvil Sell
1509
1509
$begingroup$
Never heard of this, so I'm just curious. But what's the utility of this theorem when we know the polynomial directly? Isn't it better to directly sum the coefficients than to evaluate the entire polynomial at every root of unity up to the $k$th?
$endgroup$
– Allawonder
May 4 at 9:43
$begingroup$
I was doing a question which is as follow : $$(1+x)(1+x^2) cdots (1+x^2070)$$ we have to find the sum of coefficients of $x^9k$ to get the answer here we can easily find the answer using this tool , can you suggest another method @Allawonder
$endgroup$
– Advil Sell
May 4 at 9:50
$begingroup$
I now see how it may be used for facility in some cases. I had been simply thinking of a polynomial strictly in the form $sum a_nx^n.$
$endgroup$
– Allawonder
May 4 at 9:52
add a comment |
$begingroup$
Never heard of this, so I'm just curious. But what's the utility of this theorem when we know the polynomial directly? Isn't it better to directly sum the coefficients than to evaluate the entire polynomial at every root of unity up to the $k$th?
$endgroup$
– Allawonder
May 4 at 9:43
$begingroup$
I was doing a question which is as follow : $$(1+x)(1+x^2) cdots (1+x^2070)$$ we have to find the sum of coefficients of $x^9k$ to get the answer here we can easily find the answer using this tool , can you suggest another method @Allawonder
$endgroup$
– Advil Sell
May 4 at 9:50
$begingroup$
I now see how it may be used for facility in some cases. I had been simply thinking of a polynomial strictly in the form $sum a_nx^n.$
$endgroup$
– Allawonder
May 4 at 9:52
$begingroup$
Never heard of this, so I'm just curious. But what's the utility of this theorem when we know the polynomial directly? Isn't it better to directly sum the coefficients than to evaluate the entire polynomial at every root of unity up to the $k$th?
$endgroup$
– Allawonder
May 4 at 9:43
$begingroup$
Never heard of this, so I'm just curious. But what's the utility of this theorem when we know the polynomial directly? Isn't it better to directly sum the coefficients than to evaluate the entire polynomial at every root of unity up to the $k$th?
$endgroup$
– Allawonder
May 4 at 9:43
$begingroup$
I was doing a question which is as follow : $$(1+x)(1+x^2) cdots (1+x^2070)$$ we have to find the sum of coefficients of $x^9k$ to get the answer here we can easily find the answer using this tool , can you suggest another method @Allawonder
$endgroup$
– Advil Sell
May 4 at 9:50
$begingroup$
I was doing a question which is as follow : $$(1+x)(1+x^2) cdots (1+x^2070)$$ we have to find the sum of coefficients of $x^9k$ to get the answer here we can easily find the answer using this tool , can you suggest another method @Allawonder
$endgroup$
– Advil Sell
May 4 at 9:50
$begingroup$
I now see how it may be used for facility in some cases. I had been simply thinking of a polynomial strictly in the form $sum a_nx^n.$
$endgroup$
– Allawonder
May 4 at 9:52
$begingroup$
I now see how it may be used for facility in some cases. I had been simply thinking of a polynomial strictly in the form $sum a_nx^n.$
$endgroup$
– Allawonder
May 4 at 9:52
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Theorem: (Root of Unity Filter)
Define $omega=e^2pi i/n$ for a positive integer $n$. For any polynomial $F(x)=a_0+a_1x+a_2x^2+dots$(where we take $a_k=0$ if $k>deg(F)$), the sum $a_0+a_n+a_2n+...$ is given by $$a_0+a_n+a_2n+dots=frac1n(F(1)+F(omega)+dots+F(omega^n-1)$$
Proof: Let $s_k=1+omega^k+dots+omega^(n-1)k$
If $n$ divides $k$, then $omega^k=1$ and so $s_k=1+1+1dots+1=n$ otherwise $s_k=frac1-omega^nk1-omega^k=0$. So
$(F(1)+F(omega)+dots+F(omega^n-1)=a_0s_0+a_1s_1+a_2s_2+dots=n(a_0+a_n+a_2n+dots)$
Divide the both sides of the equation by $n$ and the proof is complete.
Source of my knowledge: http://zacharyabel.com/papers/Multi-GF_A06_MathRefl.pdf
There are some examples also which may help you. Please have a look at Problem $2 $ on page $3$.
$endgroup$
add a comment |
$begingroup$
Hint: This technique is called series multisection.
Some instructive examples can be found in H.S. Wilf's book generatingfunctionology (2.4.5) to (2.4.9).
Setting $omega_r=expleft(frac2pi irright), rgeq 1$ an integral value, the formula
beginalign*
sum_k=0^leftlfloorfracn-arrightrfloorbinomna+krx^a+kr=frac1rsum_k=1^rleft(omega_r^kright)^-aleft(1+xomega_r^kright)^n, qquad 0leq aleq n,aleq r-1
endalign*
is stated as (6.20) in Binomial Identities Derived from Trigonometric and Exponential Series by H.W. Gould.
An application proving a binomial identity can be found e.g. in this MSE answer.
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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%2f3213142%2froot-of-unity-filter%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Theorem: (Root of Unity Filter)
Define $omega=e^2pi i/n$ for a positive integer $n$. For any polynomial $F(x)=a_0+a_1x+a_2x^2+dots$(where we take $a_k=0$ if $k>deg(F)$), the sum $a_0+a_n+a_2n+...$ is given by $$a_0+a_n+a_2n+dots=frac1n(F(1)+F(omega)+dots+F(omega^n-1)$$
Proof: Let $s_k=1+omega^k+dots+omega^(n-1)k$
If $n$ divides $k$, then $omega^k=1$ and so $s_k=1+1+1dots+1=n$ otherwise $s_k=frac1-omega^nk1-omega^k=0$. So
$(F(1)+F(omega)+dots+F(omega^n-1)=a_0s_0+a_1s_1+a_2s_2+dots=n(a_0+a_n+a_2n+dots)$
Divide the both sides of the equation by $n$ and the proof is complete.
Source of my knowledge: http://zacharyabel.com/papers/Multi-GF_A06_MathRefl.pdf
There are some examples also which may help you. Please have a look at Problem $2 $ on page $3$.
$endgroup$
add a comment |
$begingroup$
Theorem: (Root of Unity Filter)
Define $omega=e^2pi i/n$ for a positive integer $n$. For any polynomial $F(x)=a_0+a_1x+a_2x^2+dots$(where we take $a_k=0$ if $k>deg(F)$), the sum $a_0+a_n+a_2n+...$ is given by $$a_0+a_n+a_2n+dots=frac1n(F(1)+F(omega)+dots+F(omega^n-1)$$
Proof: Let $s_k=1+omega^k+dots+omega^(n-1)k$
If $n$ divides $k$, then $omega^k=1$ and so $s_k=1+1+1dots+1=n$ otherwise $s_k=frac1-omega^nk1-omega^k=0$. So
$(F(1)+F(omega)+dots+F(omega^n-1)=a_0s_0+a_1s_1+a_2s_2+dots=n(a_0+a_n+a_2n+dots)$
Divide the both sides of the equation by $n$ and the proof is complete.
Source of my knowledge: http://zacharyabel.com/papers/Multi-GF_A06_MathRefl.pdf
There are some examples also which may help you. Please have a look at Problem $2 $ on page $3$.
$endgroup$
add a comment |
$begingroup$
Theorem: (Root of Unity Filter)
Define $omega=e^2pi i/n$ for a positive integer $n$. For any polynomial $F(x)=a_0+a_1x+a_2x^2+dots$(where we take $a_k=0$ if $k>deg(F)$), the sum $a_0+a_n+a_2n+...$ is given by $$a_0+a_n+a_2n+dots=frac1n(F(1)+F(omega)+dots+F(omega^n-1)$$
Proof: Let $s_k=1+omega^k+dots+omega^(n-1)k$
If $n$ divides $k$, then $omega^k=1$ and so $s_k=1+1+1dots+1=n$ otherwise $s_k=frac1-omega^nk1-omega^k=0$. So
$(F(1)+F(omega)+dots+F(omega^n-1)=a_0s_0+a_1s_1+a_2s_2+dots=n(a_0+a_n+a_2n+dots)$
Divide the both sides of the equation by $n$ and the proof is complete.
Source of my knowledge: http://zacharyabel.com/papers/Multi-GF_A06_MathRefl.pdf
There are some examples also which may help you. Please have a look at Problem $2 $ on page $3$.
$endgroup$
Theorem: (Root of Unity Filter)
Define $omega=e^2pi i/n$ for a positive integer $n$. For any polynomial $F(x)=a_0+a_1x+a_2x^2+dots$(where we take $a_k=0$ if $k>deg(F)$), the sum $a_0+a_n+a_2n+...$ is given by $$a_0+a_n+a_2n+dots=frac1n(F(1)+F(omega)+dots+F(omega^n-1)$$
Proof: Let $s_k=1+omega^k+dots+omega^(n-1)k$
If $n$ divides $k$, then $omega^k=1$ and so $s_k=1+1+1dots+1=n$ otherwise $s_k=frac1-omega^nk1-omega^k=0$. So
$(F(1)+F(omega)+dots+F(omega^n-1)=a_0s_0+a_1s_1+a_2s_2+dots=n(a_0+a_n+a_2n+dots)$
Divide the both sides of the equation by $n$ and the proof is complete.
Source of my knowledge: http://zacharyabel.com/papers/Multi-GF_A06_MathRefl.pdf
There are some examples also which may help you. Please have a look at Problem $2 $ on page $3$.
edited May 4 at 9:49
answered May 4 at 9:35
StammeringMathematicianStammeringMathematician
3,0511326
3,0511326
add a comment |
add a comment |
$begingroup$
Hint: This technique is called series multisection.
Some instructive examples can be found in H.S. Wilf's book generatingfunctionology (2.4.5) to (2.4.9).
Setting $omega_r=expleft(frac2pi irright), rgeq 1$ an integral value, the formula
beginalign*
sum_k=0^leftlfloorfracn-arrightrfloorbinomna+krx^a+kr=frac1rsum_k=1^rleft(omega_r^kright)^-aleft(1+xomega_r^kright)^n, qquad 0leq aleq n,aleq r-1
endalign*
is stated as (6.20) in Binomial Identities Derived from Trigonometric and Exponential Series by H.W. Gould.
An application proving a binomial identity can be found e.g. in this MSE answer.
$endgroup$
add a comment |
$begingroup$
Hint: This technique is called series multisection.
Some instructive examples can be found in H.S. Wilf's book generatingfunctionology (2.4.5) to (2.4.9).
Setting $omega_r=expleft(frac2pi irright), rgeq 1$ an integral value, the formula
beginalign*
sum_k=0^leftlfloorfracn-arrightrfloorbinomna+krx^a+kr=frac1rsum_k=1^rleft(omega_r^kright)^-aleft(1+xomega_r^kright)^n, qquad 0leq aleq n,aleq r-1
endalign*
is stated as (6.20) in Binomial Identities Derived from Trigonometric and Exponential Series by H.W. Gould.
An application proving a binomial identity can be found e.g. in this MSE answer.
$endgroup$
add a comment |
$begingroup$
Hint: This technique is called series multisection.
Some instructive examples can be found in H.S. Wilf's book generatingfunctionology (2.4.5) to (2.4.9).
Setting $omega_r=expleft(frac2pi irright), rgeq 1$ an integral value, the formula
beginalign*
sum_k=0^leftlfloorfracn-arrightrfloorbinomna+krx^a+kr=frac1rsum_k=1^rleft(omega_r^kright)^-aleft(1+xomega_r^kright)^n, qquad 0leq aleq n,aleq r-1
endalign*
is stated as (6.20) in Binomial Identities Derived from Trigonometric and Exponential Series by H.W. Gould.
An application proving a binomial identity can be found e.g. in this MSE answer.
$endgroup$
Hint: This technique is called series multisection.
Some instructive examples can be found in H.S. Wilf's book generatingfunctionology (2.4.5) to (2.4.9).
Setting $omega_r=expleft(frac2pi irright), rgeq 1$ an integral value, the formula
beginalign*
sum_k=0^leftlfloorfracn-arrightrfloorbinomna+krx^a+kr=frac1rsum_k=1^rleft(omega_r^kright)^-aleft(1+xomega_r^kright)^n, qquad 0leq aleq n,aleq r-1
endalign*
is stated as (6.20) in Binomial Identities Derived from Trigonometric and Exponential Series by H.W. Gould.
An application proving a binomial identity can be found e.g. in this MSE answer.
answered May 5 at 20:34
Markus ScheuerMarkus Scheuer
65.3k461155
65.3k461155
add a comment |
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.
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%2f3213142%2froot-of-unity-filter%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
$begingroup$
Never heard of this, so I'm just curious. But what's the utility of this theorem when we know the polynomial directly? Isn't it better to directly sum the coefficients than to evaluate the entire polynomial at every root of unity up to the $k$th?
$endgroup$
– Allawonder
May 4 at 9:43
$begingroup$
I was doing a question which is as follow : $$(1+x)(1+x^2) cdots (1+x^2070)$$ we have to find the sum of coefficients of $x^9k$ to get the answer here we can easily find the answer using this tool , can you suggest another method @Allawonder
$endgroup$
– Advil Sell
May 4 at 9:50
$begingroup$
I now see how it may be used for facility in some cases. I had been simply thinking of a polynomial strictly in the form $sum a_nx^n.$
$endgroup$
– Allawonder
May 4 at 9:52