3Blue1Brown
The video introduces the problem of finding the number of subsets of a set whose sum is divisible by five. The presenter explains the concept of generating functions and demonstrates how to use them to solve the problem efficiently. The video also discusses the use of complex numbers and roots of unity to manipulate the coefficients of the generating function, allowing for the deduction of information without expanding the expression. The video concludes with a reflection on the unexpected techniques used to solve the problem and suggests further study of generating functions in the book by Herbert Wilf.
In this section, the narrator introduces a seemingly innocent question posed in a book, which is to find the number of subsets of the set one up to two thousand whose sum of elements are divisible by five. The narrator suggests trying the question with a simpler example using the set one two three four five. The narrator points out that a brute force program could not possibly answer this question, as the total number of subsets is 2 to the power 2,000, an unattainable solution. The answer cannot be approximated to the fifth of all the total subsets either, as the real challenge is to find the precise answer. The narrator hints that there will be two beautiful twists and turns in solving this problem.
In this section of the video, the presenter introduces the concept of generating functions as a way to efficiently count subsets with a certain sum. They demonstrate how to use a polynomial expression with the variable x as a symbol to represent subsets with different sums. When the expression is expanded, each term represents a subset with the exponent of x equal to the sum of the corresponding subset. The coefficients of the exponents correspond to the number of subsets with a certain sum. The presenter explains how analyzing and manipulating the properties of the polynomial can lead to insight into the original problem. They note that generating functions can be applied to a wide range of problems beyond counting subsets, and are a powerful tool in combinatorics.
In this section, the video explains how the rule that is used to define Fibonacci numbers can be expressed as an equation in terms of a function, and the generating function involves 2,000 different binomial terms. By manipulating the generating function, an exact closed form expression for each individual Fibonacci number can be obtained. The art of analyzing a generating function is to deduce facts about the coefficients without actually expanding the expression. The video then goes on to discuss evaluating the function at different inputs, which allows deduction of information about the coefficients. When the function is evaluated at -1, there is an oscillating sum between even coefficients and odd coefficients in an alternating pattern, which forces the balance of even and odd coefficients to be equal.
In this section, the speaker discusses a trick for finding coefficients corresponding to multiples of five in a generating function. By using complex numbers, specifically the fifth roots of unity, which are solutions to the equation z to the fifth equals one, the speaker shows that the powers of this number rotate every five terms. By evaluating the generating function at all five of these numbers and adding them together, a cancellation occurs among the terms, much like what happened when evaluating at one and negative one in the previous section. By adding up these five terms, with zeta to the zero plus zeta up to the fourth, and using vector addition, the overall sum loops back to be zero. Using this trick, the speaker will be able to answer the final question of counting the total number of subsets whose sum is divisible by five.
In this section, the speaker discusses how the roots of unity can be used to solve problems relating to subsets, using complex polynomials that have zeroes evenly balanced around the number zero. The manipulation of these zeroes helps to shuffle the terms of the polynomial and will give a sum of zero for powers of x that are not divisible by 5, while going to something non-zero for powers of x which are divisible by 5. The coefficients of the resulting polynomial tell us how many subsets add up to a certain value, so adding up all of the coefficients that are multiples of 5 will give us the solution we need. To evaluate the polynomial requires some algebra and manipulation; while it appears daunting, the technique is less complicated than expected to evaluate one of the roots of unity that are required.
In this section, the speaker discusses how to evaluate the product of five different complex numbers. They use their geometric intuition to determine that the lengths of these complex numbers are the same, resulting in the product involving two different copies of the length squared. The final step involves evaluating the product through a polynomial whose coefficients tell how many subsets have a particular sum for each value n. To add up every fifth coefficient of that polynomial, they evaluate the polynomial as a function on all of the fifth roots of unity, where the final answer quite magically turns out to be precisely two, meaning the answer is around two and can be evaluated by taking two multiplied by itself two thousand times.
In this section, the speaker reflects on the puzzle that he presented and how it was solved with a discrete sequence, complex valued inputs, and polynomial evaluation, all of which are highly unexpected techniques. He relates these techniques to the study of primes and the Riemann hypothesis, both of which involve discrete sequences and complex valued inputs. Using a richer space of numbers, like the complex plane, offers more power in making deductions about the coefficients, especially when frequency information is involved, as seen in the use of roots of unity to detect frequency information in Shor's algorithm and in the core idea behind Fourier transforms and series. The speaker suggests learning more in the book generatingfunctionology by Herbert Wilf and leaves some fun puzzles on the screen for further practice.
No videos found.
No related videos found.
No music found.