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$













3












$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










share|cite|improve this question









$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
















3












$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










share|cite|improve this question









$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














3












3








3


1



$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










share|cite|improve this question









$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






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










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

















  • $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











2 Answers
2






active

oldest

votes


















6












$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$.






share|cite|improve this answer











$endgroup$




















    1












    $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.






    share|cite|improve this answer









    $endgroup$













      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
      );



      );













      draft saved

      draft discarded


















      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









      6












      $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$.






      share|cite|improve this answer











      $endgroup$

















        6












        $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$.






        share|cite|improve this answer











        $endgroup$















          6












          6








          6





          $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$.






          share|cite|improve this answer











          $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$.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited May 4 at 9:49

























          answered May 4 at 9:35









          StammeringMathematicianStammeringMathematician

          3,0511326




          3,0511326





















              1












              $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.






              share|cite|improve this answer









              $endgroup$

















                1












                $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.






                share|cite|improve this answer









                $endgroup$















                  1












                  1








                  1





                  $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.






                  share|cite|improve this 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.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered May 5 at 20:34









                  Markus ScheuerMarkus Scheuer

                  65.3k461155




                  65.3k461155



























                      draft saved

                      draft discarded
















































                      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.




                      draft saved


                      draft discarded














                      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





















































                      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







                      Popular posts from this blog

                      Wikipedia:Vital articles Мазмуну Biography - Өмүр баян Philosophy and psychology - Философия жана психология Religion - Дин Social sciences - Коомдук илимдер Language and literature - Тил жана адабият Science - Илим Technology - Технология Arts and recreation - Искусство жана эс алуу History and geography - Тарых жана география Навигация менюсу

                      Bruxelas-Capital Índice Historia | Composición | Situación lingüística | Clima | Cidades irmandadas | Notas | Véxase tamén | Menú de navegacióneO uso das linguas en Bruxelas e a situación do neerlandés"Rexión de Bruxelas Capital"o orixinalSitio da rexiónPáxina de Bruselas no sitio da Oficina de Promoción Turística de Valonia e BruxelasMapa Interactivo da Rexión de Bruxelas-CapitaleeWorldCat332144929079854441105155190212ID28008674080552-90000 0001 0666 3698n94104302ID540940339365017018237

                      What should I write in an apology letter, since I have decided not to join a company after accepting an offer letterShould I keep looking after accepting a job offer?What should I do when I've been verbally told I would get an offer letter, but still haven't gotten one after 4 weeks?Do I accept an offer from a company that I am not likely to join?New job hasn't confirmed starting date and I want to give current employer as much notice as possibleHow should I address my manager in my resignation letter?HR delayed background verification, now jobless as resignedNo email communication after accepting a formal written offer. How should I phrase the call?What should I do if after receiving a verbal offer letter I am informed that my written job offer is put on hold due to some internal issues?Should I inform the current employer that I am about to resign within 1-2 weeks since I have signed the offer letter and waiting for visa?What company will do, if I send their offer letter to another company