title

Olympiad level counting (Generating functions)

description

A lesson on generating functions, and clever uses of complex numbers for counting
Help fund future projects: https://www.patreon.com/3blue1brown
An equally valuable form of support is to simply share the videos.
Special thanks: https://3b1b.co/lessons/subsets-puzzle#thanks
Artwork by Kurt Burns
Music by Vince Rubinetti
Nice writeup and video giving solutions to the exercises at the end, by Benjamin Hackl
https://benjamin-hackl.at/blog/2022/06/generating-functions-3b1b.html
https://youtu.be/9SzwfM-S9sk
102 Combinatorial problems, by Titu Andreescu and Zuming Feng
https://amzn.to/3wAPoNq
Generatingfunctionology by Herbert Wilf
https://amzn.to/3sPJ8Al
Visualizing the Riemann zeta function
https://youtu.be/sD0NjbwqlYw
Fourier series
https://youtu.be/r6sGWTCMz2k
Timestamps
0:00 - Puzzle statement and motivation
4:31 - Simpler example
6:51 - The generating function
11:52 - Evaluation tricks
17:24 - Roots of unity
26:31 - Recap and final trick
30:13 - Takeaways
------------------
These animations are largely made using a custom python library, manim. See the FAQ comments here:
https://www.3blue1brown.com/faq#manim
https://github.com/3b1b/manim
https://github.com/ManimCommunity/manim/
You can find code for specific videos and projects here:
https://github.com/3b1b/videos/
Music by Vincent Rubinetti.
https://www.vincentrubinetti.com/
Download the music on Bandcamp:
https://vincerubinetti.bandcamp.com/album/the-music-of-3blue1brown
Stream the music on Spotify:
https://open.spotify.com/album/1dVyjwS8FBqXhRunaG5W5u
------------------
3blue1brown is a channel about animating math, in all senses of the word animate. And you know the drill with YouTube, if you want to stay posted on new videos, subscribe: http://3b1b.co/subscribe
Various social media stuffs:
Website: https://www.3blue1brown.com
Twitter: https://twitter.com/3blue1brown
Reddit: https://www.reddit.com/r/3blue1brown
Instagram: https://www.instagram.com/3blue1brown
Patreon: https://patreon.com/3blue1brown
Facebook: https://www.facebook.com/3blue1brown

detail

{'title': 'Olympiad level counting (Generating functions)', 'heatmap': [{'end': 1662.656, 'start': 1640.476, 'weight': 0.786}, {'end': 1833.143, 'start': 1804.76, 'weight': 0.938}, {'end': 2053.341, 'start': 2029.301, 'weight': 1}], 'summary': 'Explores the utility of complex numbers in discrete math, math olympiad training, natural choices and generating functions, fifth roots of unity and polynomial evaluation, and a method to count the number of subsets of 1 to 2000 whose sum is divisible by 5.', 'chapters': [{'end': 99.381, 'segs': [{'end': 36.794, 'src': 'embed', 'start': 0.169, 'weight': 0, 'content': [{'end': 3.631, 'text': "In a moment, I will ask you a puzzle, and it's a pretty hard puzzle actually.", 'start': 0.169, 'duration': 3.462}, {'end': 10.855, 'text': "But before I do, I want to lead with a spoiler, which is the fact that the way we're going to solve this involves the use of complex numbers.", 'start': 4.131, 'duration': 6.724}, {'end': 17.478, 'text': 'And once you hear it, you will agree that that seems absurd, given that the puzzle is going to be purely a discrete question.', 'start': 11.515, 'duration': 5.963}, {'end': 20.239, 'text': 'It only asks about whole numbers and their sums.', 'start': 17.818, 'duration': 2.421}, {'end': 24.522, 'text': "There's not a whiff of the imaginary or even continuity anywhere on the horizon.", 'start': 20.64, 'duration': 3.882}, {'end': 30.688, 'text': "It's certainly not the only time that complex numbers are unreasonably useful for discrete math, to borrow a phrase.", 'start': 25.302, 'duration': 5.386}, {'end': 36.794, 'text': 'The more famous example that I could bring up would be how the modern way that mathematicians understand prime numbers you know,', 'start': 31.148, 'duration': 5.646}], 'summary': 'The puzzle involves complex numbers in discrete math.', 'duration': 36.625, 'max_score': 0.169, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric169.jpg'}], 'start': 0.169, 'title': 'The utility of complex numbers in discrete math', 'summary': 'Explores the unexpected usefulness of complex numbers in solving discrete math problems, exemplified by their relevance in understanding prime numbers and a specially designed function related to the riemann hypothesis.', 'chapters': [{'end': 99.381, 'start': 0.169, 'title': 'Utility of complex numbers in discrete math', 'summary': 'Explores the unexpected usefulness of complex numbers in solving discrete math problems, exemplified by their relevance in understanding prime numbers and a specially designed function related to the riemann hypothesis.', 'duration': 99.212, 'highlights': ['The relevance of complex numbers in solving discrete math problems, demonstrated by their unexpected usefulness in understanding prime numbers and specially designed functions related to the Riemann hypothesis and prime number theorem.', 'The surprise factor in using complex numbers to solve a purely discrete puzzle, despite its seeming absurdity given the nature of the puzzle being about whole numbers and their sums.']}], 'duration': 99.212, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric169.jpg', 'highlights': ['The relevance of complex numbers in solving discrete math problems, demonstrated by their unexpected usefulness in understanding prime numbers and specially designed functions related to the Riemann hypothesis and prime number theorem.', 'The surprise factor in using complex numbers to solve a purely discrete puzzle, despite its seeming absurdity given the nature of the puzzle being about whole numbers and their sums.']}, {'end': 343.918, 'segs': [{'end': 125.37, 'src': 'embed', 'start': 99.701, 'weight': 1, 'content': [{'end': 104.243, 'text': "It's basically a collection of problems used in training the USA team for the International Math Olympiad.", 'start': 99.701, 'duration': 4.542}, {'end': 110.225, 'text': 'And if we turn to chapter 2, Advanced Problems, problem number 10 asks this seemingly innocent question.', 'start': 104.903, 'duration': 5.322}, {'end': 119.184, 'text': 'Find the number of subsets of the set 1 up to 2000, the sum of whose elements is divisible by 5.', 'start': 110.905, 'duration': 8.279}, {'end': 121.386, 'text': 'Okay, so that might take a little bit of a moment to parse.', 'start': 119.184, 'duration': 2.202}, {'end': 125.37, 'text': 'For example, something like the set 3, 1, 4, that would be a subset.', 'start': 121.646, 'duration': 3.724}], 'summary': 'Transcript discusses training problems for usa team in math olympiad, including a question about finding subsets divisible by 5.', 'duration': 25.669, 'max_score': 99.701, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric99701.jpg'}, {'end': 177.723, 'src': 'embed', 'start': 141.718, 'weight': 0, 'content': [{'end': 147.101, 'text': 'The preview animation that I had at the start is essentially a brute force program trying to answer this question.', 'start': 141.718, 'duration': 5.383}, {'end': 153.084, 'text': 'It will iterate through all of the different possible subsets, finding the sum of each one along the way,', 'start': 147.661, 'duration': 5.423}, {'end': 156.026, 'text': 'and it increments a counter each time that it finds a multiple of five.', 'start': 153.084, 'duration': 2.942}, {'end': 157.207, 'text': 'And you know what?', 'start': 156.706, 'duration': 0.501}, {'end': 162.59, 'text': 'A nice warm-up question here would be to pause and think about how many total subsets are there overall?', 'start': 157.287, 'duration': 5.303}, {'end': 164.091, 'text': 'Forget this multiple of five stuff.', 'start': 162.73, 'duration': 1.361}, {'end': 170.877, 'text': 'How long will it take for this program to terminate? Many of you may know the answer is 2 to the power 2, 000.', 'start': 164.531, 'duration': 6.346}, {'end': 177.723, 'text': "The basic idea there is that when you're constructing a subset, you have 2, 000 different binary choices you can make.", 'start': 170.877, 'duration': 6.846}], 'summary': 'Brute force program iterates through subsets, finding multiples of five. total subsets: 2^2000.', 'duration': 36.005, 'max_score': 141.718, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric141718.jpg'}, {'end': 351.305, 'src': 'embed', 'start': 323.313, 'weight': 2, 'content': [{'end': 326.514, 'text': 'And the three subsets adding up to ten will all live in this little box.', 'start': 323.313, 'duration': 3.201}, {'end': 333.257, 'text': 'And, all in all, the ones that we care about the subsets with a sum divisible by five have been put over here on the left,', 'start': 327.275, 'duration': 5.982}, {'end': 335.098, 'text': "and it looks like there's a total of eight of them.", 'start': 333.257, 'duration': 1.841}, {'end': 343.918, 'text': 'Oh, and by the way, I should say, we are counting the empty set, we consider its sum to be 0, and we consider that to be a multiple of 5.', 'start': 336.331, 'duration': 7.587}, {'end': 347.221, 'text': "By the end, I hope you'll agree all of those are abundantly natural choices to make.", 'start': 343.918, 'duration': 3.303}, {'end': 351.305, 'text': 'Take a moment to compare this answer to what you might expect heuristically.', 'start': 348.082, 'duration': 3.223}], 'summary': 'In the given set, there are eight subsets with a sum divisible by five.', 'duration': 27.992, 'max_score': 323.313, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric323313.jpg'}], 'start': 99.701, 'title': 'Math olympiad training', 'summary': 'Discusses finding subsets of a set of 1 to 2000 with a sum divisible by 5, presenting a total of 2^2000 subsets and revealing 8 out of 32 subsets have a sum divisible by five.', 'chapters': [{'end': 193.196, 'start': 99.701, 'title': 'Math olympiad training: subset sum', 'summary': 'Discusses an advanced math problem from the international math olympiad training, asking to find the number of subsets of the set 1 up to 2000, the sum of whose elements is divisible by 5, with a total of 2^2000 subsets and a brute force program to iterate through them.', 'duration': 93.495, 'highlights': ['There are 2^2000 total subsets for the set 1 up to 2000, making it a monstrously huge number and posing a challenge for computation.', 'The problem involves finding the number of subsets of the set 1 up to 2000, the sum of whose elements is divisible by 5, which requires iterating through all possible subsets and checking the sum of each one.', 'The preview animation demonstrates a brute force program that iterates through all possible subsets, finding the sum of each one and incrementing a counter each time it finds a multiple of five.']}, {'end': 343.918, 'start': 193.576, 'title': 'Counting subsets and sums', 'summary': 'Explores the challenge of counting subsets with a sum divisible by five, revealing that out of 32 subsets, there are eight with a sum divisible by five, and it requires a more sophisticated approach than brute force to find the precise answer.', 'duration': 150.342, 'highlights': ['Out of 32 subsets, there are eight with a sum divisible by five.', 'It requires a more sophisticated approach than brute force to find the precise answer.', 'The chapter explores the challenge of counting subsets with a sum divisible by five.']}], 'duration': 244.217, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric99701.jpg', 'highlights': ['There are 2^2000 total subsets for the set 1 up to 2000, posing a challenge for computation.', 'The problem involves finding the number of subsets of the set 1 up to 2000, the sum of whose elements is divisible by 5.', 'Out of 32 subsets, there are eight with a sum divisible by five.', 'The preview animation demonstrates a brute force program that iterates through all possible subsets.']}, {'end': 1032.353, 'segs': [{'end': 395.376, 'src': 'embed', 'start': 343.918, 'weight': 1, 'content': [{'end': 347.221, 'text': "By the end, I hope you'll agree all of those are abundantly natural choices to make.", 'start': 343.918, 'duration': 3.303}, {'end': 351.305, 'text': 'Take a moment to compare this answer to what you might expect heuristically.', 'start': 348.082, 'duration': 3.223}, {'end': 358.111, 'text': 'Out of all 32 total subsets, a fifth of that would have been 6.4, so at least in this small example,', 'start': 351.805, 'duration': 6.306}, {'end': 359.952, 'text': 'the true answer is a little bit bigger than that.', 'start': 358.111, 'duration': 1.841}, {'end': 362.435, 'text': "That's maybe something you want to tuck in the back of your mind.", 'start': 360.413, 'duration': 2.022}, {'end': 368.609, 'text': "Okay, and this is the part of the video where, I'll be honest with you, I have no idea how to motivate it.", 'start': 363.883, 'duration': 4.726}, {'end': 372.373, 'text': 'Personally, I like it when math feels like something you could have discovered yourself.', 'start': 369.129, 'duration': 3.244}, {'end': 377.659, 'text': "And if you and I were sitting down together solving this problem, I think there's all sorts of natural steps that you might take.", 'start': 372.653, 'duration': 5.006}, {'end': 381.284, 'text': "Maybe you try to understand if there's some sort of structure to the subsets.", 'start': 378.22, 'duration': 3.064}, {'end': 387.13, 'text': 'or you play around with how these sums are distributed mod five at many different iterations for other small examples.', 'start': 381.826, 'duration': 5.304}, {'end': 390.292, 'text': 'And from that, maybe you try to eke out some kind of proof by induction.', 'start': 387.57, 'duration': 2.722}, {'end': 395.376, 'text': 'When I shared an early version of this lesson with some patrons, people brought up some nice linear algebra approaches.', 'start': 391.013, 'duration': 4.363}], 'summary': 'Natural problem-solving approaches lead to mathematical insights.', 'duration': 51.458, 'max_score': 343.918, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric343918.jpg'}, {'end': 596.528, 'src': 'embed', 'start': 570.356, 'weight': 0, 'content': [{'end': 575.338, 'text': 'So this, like I said at the start, is an example of something called a generating function, where the idea is,', 'start': 570.356, 'duration': 4.982}, {'end': 580.7, 'text': 'if you have some question with an answer associated with each positive integer in our case,', 'start': 575.338, 'duration': 5.362}, {'end': 588.123, 'text': 'how many subsets add up to a particular value when you construct a polynomial whose coefficients correspond to the answers to that question?', 'start': 580.7, 'duration': 7.423}, {'end': 596.528, 'text': 'you can get a surprising amount of insight from your original question by mathematically manipulating and analyzing the properties of this polynomial.', 'start': 588.803, 'duration': 7.725}], 'summary': 'Generating functions provide insight by analyzing subsets and their values through a constructed polynomial.', 'duration': 26.172, 'max_score': 570.356, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric570356.jpg'}, {'end': 911.383, 'src': 'embed', 'start': 884.286, 'weight': 4, 'content': [{'end': 891.853, 'text': 'This expression is true for any generating function, but again, for our special generating function, we know that this value, this alternating sum,', 'start': 884.286, 'duration': 7.567}, {'end': 892.594, 'text': 'should equal zero.', 'start': 891.853, 'duration': 0.741}, {'end': 898.899, 'text': "And a way you can interpret that is that it's telling you there's an equal balance between the even coefficients and the odd coefficients.", 'start': 892.994, 'duration': 5.905}, {'end': 906.382, 'text': 'And remember, maybe in the context of our smaller example, these coefficients are encoding for us facts about subsets.', 'start': 899.66, 'duration': 6.722}, {'end': 911.383, 'text': "So, if there's an equal balance between all those even coefficients and the odd coefficients,", 'start': 906.702, 'duration': 4.681}], 'summary': "Generating function's alternating sum equals zero, representing balance between even and odd coefficients encoding subset facts.", 'duration': 27.097, 'max_score': 884.286, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric884286.jpg'}, {'end': 1001.805, 'src': 'embed', 'start': 972.765, 'weight': 2, 'content': [{'end': 979.212, 'text': 'That will be counting the total number of subsets whose sum is divisible by 5.', 'start': 972.765, 'duration': 6.447}, {'end': 985.31, 'text': 'The trick to doing this is to generalize what we just did, where the successive powers of the input were rotating back and forth.', 'start': 979.212, 'duration': 6.098}, {'end': 988.597, 'text': "But this time, we don't want them to rotate every other time.", 'start': 986.155, 'duration': 2.442}, {'end': 991.378, 'text': "We'd like them to somehow rotate with a period of five.", 'start': 988.897, 'duration': 2.481}, {'end': 994.2, 'text': 'And to do that, we extend into the complex plane.', 'start': 991.739, 'duration': 2.461}, {'end': 1001.805, 'text': 'You see, up there we can find a value so that, as we take successive powers of it, it will rotate by a fifth of a turn,', 'start': 994.601, 'duration': 7.204}], 'summary': 'Count total subsets divisible by 5 using complex plane rotation', 'duration': 29.04, 'max_score': 972.765, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric972765.jpg'}], 'start': 343.918, 'title': 'Natural choices and generating functions in math', 'summary': 'Covers natural choices in math, exploring subsets and sums with heuristics and linear algebra, and introduces generating functions with applications in constructing subsets, analyzing coefficients, and evaluating subsets with even and odd sums, including a technique using complex numbers to count subsets with sums divisible by 5.', 'chapters': [{'end': 395.376, 'start': 343.918, 'title': 'Finding natural choices in math', 'summary': 'Discusses the natural choices in solving a math problem, exploring subsets and sums, with a focus on heuristics and linear algebra approaches.', 'duration': 51.458, 'highlights': ['The chapter emphasizes the natural choices in solving a math problem, including exploring subsets and sums, with a focus on heuristics and linear algebra approaches.', 'Out of all 32 total subsets, a fifth of that would have been 6.4, so at least in this small example, the true answer is a little bit bigger than that.', 'The video emphasizes the importance of making natural steps and exploring structures in subsets when solving math problems.']}, {'end': 1032.353, 'start': 395.737, 'title': 'Generating functions in math', 'summary': 'Introduces the concept of generating functions, demonstrating its application in constructing subsets, analyzing coefficients, and evaluating subsets with even and odd sums, leading to a technique using complex numbers to count subsets with sums divisible by 5.', 'duration': 636.616, 'highlights': ['Generating functions are a powerful tool in math, used to construct subsets and analyze coefficients, providing insights into the properties of subsets and their sums.', 'Evaluating the generating function at specific values like 0, 1, and -1 helps deduce the sum of coefficients, leading to understanding subsets with even and odd sums.', "The technique of using complex numbers to rotate powers of the input with a frequency of five extends the understanding of evaluating subsets with sums divisible by 5, providing a deeper insight into the generating function's applications."]}], 'duration': 688.435, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric343918.jpg', 'highlights': ['Generating functions are a powerful tool in math, used to construct subsets and analyze coefficients, providing insights into the properties of subsets and their sums.', 'The chapter emphasizes the natural choices in solving a math problem, including exploring subsets and sums, with a focus on heuristics and linear algebra approaches.', "The technique of using complex numbers to rotate powers of the input with a frequency of five extends the understanding of evaluating subsets with sums divisible by 5, providing a deeper insight into the generating function's applications.", 'Out of all 32 total subsets, a fifth of that would have been 6.4, so at least in this small example, the true answer is a little bit bigger than that.', 'Evaluating the generating function at specific values like 0, 1, and -1 helps deduce the sum of coefficients, leading to understanding subsets with even and odd sums.', 'The video emphasizes the importance of making natural steps and exploring structures in subsets when solving math problems.']}, {'end': 1605.321, 'segs': [{'end': 1062.034, 'src': 'embed', 'start': 1032.813, 'weight': 2, 'content': [{'end': 1036.513, 'text': 'So the more it feels like something that you could have discovered yourself,', 'start': 1032.813, 'duration': 3.7}, {'end': 1043.097, 'text': "the more it might actually be the case that when you're working on some future problem in this circle of thoughts, you will discover it yourself.", 'start': 1036.513, 'duration': 6.584}, {'end': 1056.35, 'text': "To be specific, the complex number that I care about is one that I'm going to label zeta, and it sits a fifth of a turn around the unit circle.", 'start': 1048.925, 'duration': 7.425}, {'end': 1062.034, 'text': 'So its angle is 2 pi fifths radians, and its magnitude is 1.', 'start': 1056.67, 'duration': 5.364}], 'summary': 'Discovering complex number zeta, 2π/5 radians, magnitude 1.', 'duration': 29.221, 'max_score': 1032.813, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1032813.jpg'}, {'end': 1141.731, 'src': 'embed', 'start': 1112.903, 'weight': 1, 'content': [{'end': 1115.584, 'text': "It's the same thing as if you had raised it to the zeroth power.", 'start': 1112.903, 'duration': 2.681}, {'end': 1117.566, 'text': 'We get this cycling every five terms.', 'start': 1115.805, 'duration': 1.761}, {'end': 1119.067, 'text': "That's the thing that we care about.", 'start': 1117.866, 'duration': 1.201}, {'end': 1121.047, 'text': 'These numbers have a special name.', 'start': 1119.767, 'duration': 1.28}, {'end': 1127.128, 'text': "They're called the fifth roots of unity, essentially because they solve the equation z to the fifth equals one.", 'start': 1121.127, 'duration': 6.001}, {'end': 1129.189, 'text': 'They are fifth roots of the number one.', 'start': 1127.488, 'duration': 1.701}, {'end': 1134.69, 'text': 'If you just presented someone with this equation, they would probably say the answer is clearly z equals one.', 'start': 1129.769, 'duration': 4.921}, {'end': 1138.43, 'text': 'But the idea is that there are four other answers in the complex plane.', 'start': 1135.31, 'duration': 3.12}, {'end': 1141.731, 'text': 'Four other numbers where when you raise them to the fifth, you get one.', 'start': 1138.89, 'duration': 2.841}], 'summary': 'Fifth roots of unity cycle every five terms, solving z^5 = 1 in complex plane.', 'duration': 28.828, 'max_score': 1112.903, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1112903.jpg'}, {'end': 1335.59, 'src': 'embed', 'start': 1295.148, 'weight': 0, 'content': [{'end': 1298.131, 'text': 'Unsurprisingly, the same thing happens if our function was x to the fourth.', 'start': 1295.148, 'duration': 2.983}, {'end': 1306.356, 'text': 'But critically, where things change is if we consider the function x to the fifth.', 'start': 1301.874, 'duration': 4.482}, {'end': 1311.779, 'text': 'In that case, when you raise zeta to the fifth power, by definition, it goes to one.', 'start': 1307.117, 'duration': 4.662}, {'end': 1315.161, 'text': 'Similarly, zeta squared raised to the fifth power goes to one.', 'start': 1312.46, 'duration': 2.701}, {'end': 1316.702, 'text': 'All of these go to one.', 'start': 1315.681, 'duration': 1.021}, {'end': 1317.963, 'text': 'They are the roots of unity.', 'start': 1316.762, 'duration': 1.201}, {'end': 1319.824, 'text': 'This is, after all, their whole purpose in life.', 'start': 1318.023, 'duration': 1.801}, {'end': 1326.526, 'text': 'So in this case, when we apply the function and add them all up instead of going to 0 and getting cancellation,', 'start': 1320.484, 'duration': 6.042}, {'end': 1328.447, 'text': 'we get a kind of constructive interference.', 'start': 1326.526, 'duration': 1.921}, {'end': 1332.049, 'text': 'All of them equal 1, so their sum is equal to 5.', 'start': 1328.747, 'duration': 3.302}, {'end': 1335.59, 'text': 'So if you step back and think about what all those examples mean,', 'start': 1332.049, 'duration': 3.541}], 'summary': 'When considering the function x to the fifth power, the roots of unity result in a sum of 5, indicating constructive interference.', 'duration': 40.442, 'max_score': 1295.148, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1295148.jpg'}], 'start': 1032.813, 'title': 'Fifth roots of unity and polynomial evaluation', 'summary': 'Delves into the properties of fifth roots of unity, cancellation phenomenon, and evaluating polynomials on roots of unity to simplify calculations and find specific coefficients, with a noteworthy example of the sum of fifth roots of unity resulting in constructive interference with the sum equaling 5.', 'chapters': [{'end': 1335.59, 'start': 1032.813, 'title': 'Fifth roots of unity and cancellation phenomenon', 'summary': 'Discusses the concept of fifth roots of unity, their properties, and the phenomenon of cancellation and constructive interference when evaluating functions at these roots, exemplified by the sum of fifth roots of unity resulting in constructive interference with the sum equaling 5.', 'duration': 302.777, 'highlights': ['The fifth roots of unity have a property where their powers cycle every five terms, resulting in cancellation when evaluated with certain functions, but constructive interference when evaluated with x to the fifth, yielding a sum of 5.', 'The complex number representing the fifth roots of unity is labeled zeta, with an angle of 2 pi fifths radians around the unit circle, and its powers exhibit rotational behavior and magnitude of 1.', 'When evaluating functions at the fifth roots of unity, such as f(x) = x, the sum of these evaluations results in cancellation, as the overall sum loops back to zero, indicating balanced distribution around the origin.']}, {'end': 1605.321, 'start': 1335.59, 'title': 'Evaluating polynomial on roots of unity', 'summary': 'Explains how to evaluate a polynomial function on roots of unity to find the sum of coefficients that are multiples of five, using geometric intuition and complex number properties, ultimately simplifying a complex calculation into a manageable one.', 'duration': 269.731, 'highlights': ['The polynomial function evaluates to 2-ish when multiplied with five different roots of unity, providing a geometric intuition for the numerical answer.', 'The function can be explicitly evaluated on five different roots of unity, providing a method to obtain the desired sum by dividing the result by five.', 'A method to evaluate the function on roots of unity and simplify the calculation by considering the geometric properties of complex numbers is presented.']}], 'duration': 572.508, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1032813.jpg', 'highlights': ['The sum of fifth roots of unity equals 5, exhibiting constructive interference', 'The powers of the fifth roots of unity cycle every five terms, resulting in cancellation', 'The complex number representing the fifth roots of unity is labeled zeta, with an angle of 2 pi fifths radians', 'The sum of function evaluations at the fifth roots of unity results in cancellation, looping back to zero', 'The polynomial function evaluates to 2-ish when multiplied with five different roots of unity']}, {'end': 2056.995, 'segs': [{'end': 1631.031, 'src': 'embed', 'start': 1605.341, 'weight': 1, 'content': [{'end': 1611.882, 'text': 'So we started with this question asking us, count the number of subsets of 1 up to 2000 whose sum is divisible by 5.', 'start': 1605.341, 'duration': 6.541}, {'end': 1618.904, 'text': 'We then constructed this polynomial whose coefficients tell us how many subsets have a particular sum for each value n.', 'start': 1611.882, 'duration': 7.022}, {'end': 1623.606, 'text': 'So what we want is to add up every fifth coefficient of that polynomial.', 'start': 1619.924, 'duration': 3.682}, {'end': 1631.031, 'text': 'Then we saw how evaluating this polynomial as a function on all of the fifth roots of unity, then adding them up,', 'start': 1624.867, 'duration': 6.164}], 'summary': 'Count subsets from 1 to 2000 whose sum is divisible by 5 using polynomial coefficients.', 'duration': 25.69, 'max_score': 1605.341, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1605341.jpg'}, {'end': 1667.079, 'src': 'heatmap', 'start': 1640.476, 'weight': 0.786, 'content': [{'end': 1644.518, 'text': "As a super slick way to actually evaluate that product, here's the final trick.", 'start': 1640.476, 'duration': 4.042}, {'end': 1647.84, 'text': 'Remember, I described these numbers as roots of unity.', 'start': 1645.258, 'duration': 2.582}, {'end': 1650.521, 'text': 'They solve the equation z to the fifth equals one.', 'start': 1648.04, 'duration': 2.481}, {'end': 1656.084, 'text': 'Another way to think about that is that they are roots of the polynomial z to the fifth minus one.', 'start': 1651.061, 'duration': 5.023}, {'end': 1662.656, 'text': 'Now, what that means is we can factor the polynomial z to the fifth minus one to look like this,', 'start': 1656.892, 'duration': 5.764}, {'end': 1665.238, 'text': "where there's one factor corresponding to each one of the roots.", 'start': 1662.656, 'duration': 2.582}, {'end': 1667.079, 'text': 'You take z minus each one of the roots.', 'start': 1665.398, 'duration': 1.681}], 'summary': 'The roots of the polynomial z to the fifth minus one can be factored to correspond to each of the roots, solving the equation z to the fifth equals one.', 'duration': 26.603, 'max_score': 1640.476, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1640476.jpg'}, {'end': 1797.037, 'src': 'embed', 'start': 1774.779, 'weight': 0, 'content': [{'end': 1785.652, 'text': 'the answer is 1, fifth of this weird, complex expression which we just computed to be 2 to the 2000 plus 4 different copies of 2 to the 400..', 'start': 1774.779, 'duration': 10.873}, {'end': 1788.053, 'text': 'And here you might want to do just a quick sanity check on.', 'start': 1785.652, 'duration': 2.401}, {'end': 1789.294, 'text': 'does this answer make any sense??', 'start': 1788.053, 'duration': 1.241}, {'end': 1797.037, 'text': 'For example, if you do it in the smaller case, with the set 1, 2, 3, 4, 5, and you walk through all the same reasoning that we just did,', 'start': 1790.074, 'duration': 6.963}], 'summary': 'The answer is 1, fifth of a complex expression including 2 to the 2000 and 4 copies of 2 to the 400.', 'duration': 22.258, 'max_score': 1774.779, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1774779.jpg'}, {'end': 1833.143, 'src': 'heatmap', 'start': 1804.76, 'weight': 0.938, 'content': [{'end': 1808.401, 'text': 'which is a fifth of 32 plus 8,, which is 8..', 'start': 1804.76, 'duration': 3.641}, {'end': 1812.143, 'text': "And if you'll remember when we explicitly looked at them all, that was in fact the answer.", 'start': 1808.401, 'duration': 3.742}, {'end': 1824.176, 'text': "Look, this is a hard puzzle, and when it's worth putting in the time to solve a hard problem, it's also worth taking some time to reflect on it.", 'start': 1817.711, 'duration': 6.465}, {'end': 1825.157, 'text': 'What do you get out of this??', 'start': 1824.376, 'duration': 0.781}, {'end': 1825.977, 'text': "What's the takeaway?", 'start': 1825.237, 'duration': 0.74}, {'end': 1833.143, 'text': 'Now you could reflect on the answer itself how the dominant part is indeed one-fifth of all the total subsets, like we might have guessed,', 'start': 1826.798, 'duration': 6.345}], 'summary': 'The answer is one-fifth of all the total subsets.', 'duration': 28.383, 'max_score': 1804.76, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1804760.jpg'}, {'end': 1859.496, 'src': 'embed', 'start': 1833.143, 'weight': 2, 'content': [{'end': 1839.267, 'text': 'and how this error term came about from the not-quite-destructive interference in a massive combination of roots of unity.', 'start': 1833.143, 'duration': 6.124}, {'end': 1843.729, 'text': 'But again, what makes this question interesting is not the answer.', 'start': 1840.228, 'duration': 3.501}, {'end': 1851.753, 'text': "it's the way that we solved it, namely taking a discrete sequence that we want to understand and treating it as the coefficients on a polynomial,", 'start': 1843.729, 'duration': 8.024}, {'end': 1855.094, 'text': 'then evaluating that polynomial on complex values.', 'start': 1851.753, 'duration': 3.341}, {'end': 1859.496, 'text': 'Both of those steps are probably highly unexpected at the outset,', 'start': 1855.854, 'duration': 3.642}], 'summary': 'Error term from interference in roots of unity, solved by polynomial evaluation on complex values.', 'duration': 26.353, 'max_score': 1833.143, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1833143.jpg'}, {'end': 1931.364, 'src': 'embed', 'start': 1900.626, 'weight': 5, 'content': [{'end': 1903.888, 'text': 'the way that Riemann studied primes involved a discrete sequence.', 'start': 1900.626, 'duration': 3.262}, {'end': 1912.294, 'text': 'we want to understand something carrying information about prime numbers and then considering a function whose coefficients are the terms in that sequence.', 'start': 1903.888, 'duration': 8.406}, {'end': 1914.888, 'text': "In that case, it's not quite a polynomial.", 'start': 1913.186, 'duration': 1.702}, {'end': 1920.133, 'text': "Instead, it's a related structure known as a Dirichlet series, or Dirichlet series, depending on who you ask.", 'start': 1915.008, 'duration': 5.125}, {'end': 1921.695, 'text': "But it's the same essential idea.", 'start': 1920.373, 'duration': 1.322}, {'end': 1931.364, 'text': 'Then the way to suss out information about those coefficients comes from studying how this function behaves with you guessed it complex valued inputs.', 'start': 1922.155, 'duration': 9.209}], 'summary': 'Riemann studied prime numbers using dirichlet series and complex-valued inputs.', 'duration': 30.738, 'max_score': 1900.626, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1900626.jpg'}, {'end': 2018.257, 'src': 'embed', 'start': 1980.093, 'weight': 3, 'content': [{'end': 1986.557, 'text': 'In our puzzle, the relevant fact that we wanted, the sum of every fifth coefficient, was a kind of frequency question.', 'start': 1980.093, 'duration': 6.464}, {'end': 1990.839, 'text': 'And the real reason the complex numbers, as opposed to some other structure,', 'start': 1987.157, 'duration': 3.682}, {'end': 1996.702, 'text': 'proved to be useful for us is that we could find a value so that successive products have this cycling behavior.', 'start': 1990.839, 'duration': 5.863}, {'end': 2004.146, 'text': 'This use of values on the unit circle, and roots of unity in particular, to suss out frequency information is extremely fruitful.', 'start': 1997.122, 'duration': 7.024}, {'end': 2007.829, 'text': 'It is almost impossible to overstate how helpful that idea is.', 'start': 2004.366, 'duration': 3.463}, {'end': 2012.152, 'text': 'Just to give one out of thousands of examples in the 1990s,', 'start': 2008.609, 'duration': 3.543}, {'end': 2018.257, 'text': 'Peter Shor found a way for quantum computers to factor large numbers way way faster than classical computers can.', 'start': 2012.152, 'duration': 6.105}], 'summary': "Using complex numbers, frequency information can be sussed out, leading to breakthroughs like peter shor's quantum factorization in the 1990s.", 'duration': 38.164, 'max_score': 1980.093, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1980093.jpg'}, {'end': 2053.341, 'src': 'heatmap', 'start': 2029.301, 'weight': 1, 'content': [{'end': 2036.027, 'text': 'More generally, this is the core idea that underlies Fourier transforms and Fourier series, and the infinite swell of topics that follow from those.', 'start': 2029.301, 'duration': 6.726}, {'end': 2042.852, 'text': "As to the topic of generating functions themselves, we've really only just scratched the surface here, and if you want to learn more,", 'start': 2037.027, 'duration': 5.825}, {'end': 2048.097, 'text': 'I highly recommend this kind of hilariously named book Generating Functionology by Herbert Wilf.', 'start': 2042.852, 'duration': 5.245}, {'end': 2053.341, 'text': "And I'll also leave up a few fun puzzles on the screen here for anyone who wants to flex their muscles a bit with the idea.", 'start': 2048.536, 'duration': 4.805}], 'summary': 'Fourier transforms, generating functions, and book recommendation for further learning.', 'duration': 24.04, 'max_score': 2029.301, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric2029301.jpg'}], 'start': 1605.341, 'title': 'Counting subsets with divisible sums by 5', 'summary': 'Discusses a method to count the number of subsets of 1 up to 2000 whose sum is divisible by 5, revealing that the answer is 1/5th of 2 to the power 2000 plus 4 different copies of 2 to the power 400.', 'chapters': [{'end': 1855.094, 'start': 1605.341, 'title': 'Counting subsets with divisible sums by 5', 'summary': 'Discusses a method to count the number of subsets of 1 up to 2000 whose sum is divisible by 5, revealing that the answer is 1/5th of 2 to the power 2000 plus 4 different copies of 2 to the power 400.', 'duration': 249.753, 'highlights': ['The answer to counting the subsets, whose sum is divisible by 5, involves evaluating a polynomial with coefficients representing the number of subsets having a particular sum for each value n.', 'The value of the expression, obtained by adding up f on all of the different roots of unity, is found to be 1/5th of 2 to the power 2000 plus 4 different copies of 2 to the power 400.', 'The method of solving the puzzle involves treating a discrete sequence as coefficients on a polynomial and evaluating it on complex values, providing insight into the nature of the answer and the error term in the solution.']}, {'end': 2056.995, 'start': 1855.854, 'title': 'Analyzing dirichlet series and the use of complex numbers', 'summary': "Discusses the connection between studying primes and riemann's work, the importance of complex numbers in uncovering frequency information, and the broad applications of these concepts, including shor's algorithm for quantum computers.", 'duration': 201.141, 'highlights': ["The use of roots of unity to detect frequency information is extremely fruitful, with applications like Shor's algorithm for quantum computers.", "Studying primes and Riemann's work involves understanding a function with coefficients from a discrete sequence, using a related structure known as a Dirichlet series.", 'The importance of complex numbers in uncovering frequency information, demonstrated through the use of values on the unit circle and roots of unity, underlies concepts like Fourier transforms and Fourier series.']}], 'duration': 451.654, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/bOXCLR3Wric/pics/bOXCLR3Wric1605341.jpg', 'highlights': ['The value of the expression is 1/5th of 2 to the power 2000 plus 4 different copies of 2 to the power 400.', 'The answer to counting the subsets involves evaluating a polynomial with coefficients representing the number of subsets.', 'The method involves treating a discrete sequence as coefficients on a polynomial and evaluating it on complex values.', "The use of roots of unity to detect frequency information is extremely fruitful, with applications like Shor's algorithm for quantum computers.", 'The importance of complex numbers in uncovering frequency information underlies concepts like Fourier transforms and Fourier series.', "Studying primes and Riemann's work involves understanding a function with coefficients from a discrete sequence."]}], 'highlights': ['The relevance of complex numbers in solving discrete math problems, demonstrated by their unexpected usefulness in understanding prime numbers and specially designed functions related to the Riemann hypothesis and prime number theorem.', 'Generating functions are a powerful tool in math, used to construct subsets and analyze coefficients, providing insights into the properties of subsets and their sums.', "The technique of using complex numbers to rotate powers of the input with a frequency of five extends the understanding of evaluating subsets with sums divisible by 5, providing a deeper insight into the generating function's applications.", 'The sum of fifth roots of unity equals 5, exhibiting constructive interference', 'The method involves treating a discrete sequence as coefficients on a polynomial and evaluating it on complex values.']}