데이터에듀PT

잠시 후에 퍼즐을 하나 물어보겠습니다. 그리고 퍼즐은 꽤나 어렵습니다. 하지만 그 전에,저는 스포일러로 시작하려 합니다. 우리가 이 퍼즐을 풀려고 할 때 복소수를 사용할 거 라는사실입니다. 그리고 여러분이 이 스포일러를 듣자마자, 퍼즐과 완전히 별개의 질문일 것이기 때문에,퍼즐이 터무니없어 보일거라고 생각할 것 입니다. 문제는 단지 정수와그 합에 대해서만 물을 뿐이며, 지평선 어디에도 허수의 낌새가 나타나지 않습니다.

여러분 중 일부는 이것이 유명한 리만 가설의 대부분이라는것을 알고 있을겁니다. 기본적으로 특수함수가 있으며,표면적으로는 소수의 이산 세계와 무관해 보입니다. 하지만 부드럽고, 복잡한 가치를 가집니다.

그러나 내부적으로는 소수에 대한 모든 정보를 암호화합니다.

그리고 가장 중요한 것은 소수에 대한 특정 질문은 소수에 대한 직접적인 분석보단이 함수를 분석함으로써 대답하기가 더 쉽다는 것입니다.

물론 잠시 후에 제가 공유할 우리의 퍼즐은 리만의 가설보다

훨씬 더 순수합니다. 그저 장난감 수준의 문제입니다.

하지만 영상의 마지막 부분에서, 우리가 이 문제를 해결하기 위해 사용하는 기술들,우리가 여기에 있는 진짜 이유는 리만 가설과 소수 정리와 그 주변의 모든 생각의순환을 이끌어내는 구성과 정신적으로 매우 유사하다는 것을 공유하겠습니다.

오늘의 퍼즐은 Titu Andreescu와 Zuming Feng의 책에서 나왔습니다. 이 책은기본적으로 국제 수학 올림피아드의 미국 팀을 훈련시키는 데 사용되는 문제집입니다.

그리고 제 2장의 고급 문제로 눈을 돌리면, 문제 10번은 "1에서 2000까지 있는 집합에서,원소의 합이 5로 나눠지는 부분집합의 개수를 구하여라" 라는순수한 질문을 합니다. 좋아요, 그럼 해석하는데 시간이 좀 걸릴 수도 있겠네요.

예를 들어, {3, 1, 4}와 같은 부분집합 원소들은 또한 전체집합의 원소들 입니다.

그리고 이것의 합은 3+1+4=8입니다. 그러므로 이 집합은 고려하지 않습니다.

즉, 우리의 계산에 포함되지 않습니다. 반면, {2, 3, 5}와 같은 부분집합은5로 나눌 수 있는 10을 합으로 가지고 있기 때문에 우리가 세고자 하는 것입니다.

제가 처음에 보여드렸던 애니메이션은 기본적으로 이 질문에 답을 구하려는 무차별 대입 프로그램입니다.

이것은 모든 가능한 부분집합에서 각각의 합을 찾는 것을 반복할 것이고,5의 배수를 찾을 때마다 카운트를 증가시킬 겁니다. 자, 여기서좋은 워밍업 질문은 영상을 잠시 멈추고 전체적으로 얼마나 많은 부분집합이 있는지생각해 보는 것입니다. 5배수는 생각하지 마세요. 이 프로그램이 종료되는 데 얼마나 걸릴까요?

여러분 중 다수는 답이 2의 2000제곱 이라는 것을 알고 있을 것입니다. 기본적인 아이디어는부분집합을 구성할 때 2,000가지의 다른 이진 선택을 할 수 있다는 것입니다.

원소를 포함할까요? 아니면 안 할까요? 그리고 그 모든 선택들은 서로 독립적입니다.

그래서 부분집합을 구성할 때 여러분이 가진 선택들의 총 수는 2 * 2 * 2 * 2… 계속해서 2000 번입니다.

그리고 우리의 프로그램을 생각해보면, 그것은 엄청나게 큰 숫자입니다. 그래서 우리가 우주에서,우주가 제공할 수 있는 모든 물리적 자원과 함께, 이런 무차별 대입을 한다고 해도,이것의 값은 가까이 오지도 않을 것이고, 심지어 표면을 긁지도 않을 것입니다.

분명히 우리는 이것보다 훨씬 더 현명해야 합니다. 그리고 여러분이대략적인 근사값을 추측한다면, 여러분은 아마 전체 부분집합들의5분의 1이 될거라고 추측할 것입니다. 이 모든 합들의 대한 대략적인균등한 분포가 있을 것입니다. 네, 이것은 적절한 근사치인 것은 사실입니다. 하지만여기서 질문의 핵심은 정확한 답을 얻는 것입니다. 이것은 정수가 아니기 때문에실제 답이 될 수 없지만, 진답은 조금 많거나 또는 조금 더 적거나 혹은 훨씬 더 많거나적거나 할 수 있습니다. 이 오차를 알아내기 위해 어떤 전술을 사용할 수 있을까요?

분명히 말하지만, 이 수업은 목적지보다는 여정에 관한 것 입니다.

여러분은 이러한 방식으로 부분집합을 필터링하고 개수를 셀 건가요? 거의 확실히,저는 그렇게 생각하지 않습니다. 하지만 장난감 문제이든 아니든, 이것은 합법적으로도전적인 질문이고, 도전은 다른 종류의 도전적인 질문들과 관련된 기술을 개발합니다.

여러분들과 저에겐, 제가 여러분과 나누고자 하는 해결책은 적어도 두 개의 매우 놀랍고,아름다운 우여곡절이 있습니다. 저는 이미 복소수가 깜짝 등장할 것이라고 알려 주었지만,우리가 그 과정까지 도달하기 전에 분명히 더 이상하고예상치 못한 변화가 있습니다. 과정을 준비하기 위해서, 퍼즐로 우리의 방향을 잡고,모든 좋은 문제 해결사들이 해야 할 일을 하고, 더 간단한 예시로 시작합시다.

아마도 {1, 2, 3, 4, 5}인 집합으로 함께 해보는 것이 좋을 것 같습니다.

여러분이 연필과 종이로 이 문제를 해결한다면, 여러분도 IMO를 훈련하고 있는 아이들 중 한 명입니다.

단순히 다섯 개의 부분집합을 나열하는 것은 그렇게 많지는 않습니다. 32개 뿐이죠.

여러분이 이 모든 것을 마음속으로 정리하고 싶을 수 있는 다른 방법들이 있습니다.

하지만 우리가 관심을 갖는 것은 그들의 합이기 때문에, 그 모든 것을하나씩 살펴보고그 합을 계산하는 것이 자연스러울 것입니다. 여기 유튜브에서전 컴퓨터를 가지고 있습니다, 제가 편법으로 합이 얼마인지 보여드리겠습니다.

저는 또한 약간의 편법을 써서 이 모든 것들을 모두 같은 합을 가진 컬렉션으로정리할 것입니다. 예를 들어, 합이 6이 되는 세 개의 서로 다른 부분집합이 있습니다. 그리고 이들은모두 이 작은 상자에 있습니다. 그리고 합이 10이 되는 세 개의 부분 집합은 모두 이 작은 상자에 있습니다.

그리고 우리가 관심을 갖는 합이 5로 나누어지는 부분집합은 여기왼쪽에 놓였고 총 8개가 있는 것처럼 보입니다. 아, 그런데,공집합을 센다고 해야겠네요. 우리는 그 합을 0으로 간주하고,5의 배수라고 생각해야 합니다. 마지막에는, 이 모든 것들이 아주 자연스러운선택이라는 것에 동의하길 바랍니다. 잠시 시간을 내어 이 답을 여러분이휴리스틱하게 예측한 것과 비교해 보세요. 총 32개의 부분 집합 중 5분의 1은 6.4개이므로 이 작은 예에서 적어도 진답은 6.4 보다 조금 더 큽니다. 이 결과는 아마도 여러분의 마음한구석에 넣고 싶을 것입니다. 자, 이 부분은 제가 여러분께솔직히 말씀드리자면, 개인적으로 어떻게 동기부여를 해야 할지 모르겠습니다. 저는 수학을여러분이 스스로 발견할 수 있었던 것처럼 느낄 때를 좋아하고, 만약 여러분과 제가 함께 앉아서이 문제를 풀고 있다면, 저는 여러분이 취할 수 있는 모든 종류의 자연스러운 단계들이 있다고 생각합니다.

여러분이 부분집합에 어떤 구조가 있는지 이해하려고 할 수도 있고, 이 합들이 다른 예시에서도,어떻게 분배되는지 알고 싶을 수도 있습니다. 그리고 그것으로부터 귀납법을 통해어떤 종류의 증명을 얻으려고 할 수도 있습니다. 제가 이 수업의초기 버전을 몇몇 후원자들과 공유했을 때, 사람들은 멋진 선형 대수 접근법을 제안했습니다.

이 모든 것들은 괜찮고 좋으며, 문제될 것이 없습니다. 하지만 제 목표는 생성 함수라고불리는 것을 여러분에게 가르치는 것입니다. 그리고 이것은 여러분이 생각할 수 있는 전술 중 하나입니다. 좋아요, 저는 이것이 효과가 있다는 것을 알지만, 여러분은 어떻게 생각하나요?

솔직히, 저도 모릅니다. 여러분의 삶에는 생성함수를 이해하기 전, 그리고 그 후의 시간이 있습니다. 그리고 저는 믿음의 도약 이외에는 그것들을 연결하는 어떤 것도 생각할 수 없습니다.

저는 여러분에게 (1+엑스)(1+엑스²)(1+엑스³)(1+엑스⁴)(1+엑스⁵) 인 다항식을 물어볼 겁니다.

이제 저는 여러분이 이게 어디서 왔는지에 대해서 물어볼 것을 압니다.

다항식이 이것과 무슨 상관일까요? 변수 엑스는지금 무엇을 나타내야 할까요? 기본적으로 엑스는 순전히 기호입니다.

여기서 다항식을 쓰는 유일한 이유는 대수적으로 확장되는 93 동작이 부분집합을 구성하는 동작을 완전히 반영하기 때문입니다. 그리고중요한 것은, 같은 합을 가진 부분집합들이 모두 뭉쳐져 있는 이 그룹입니다.

이건 제가 무슨 뜻인지 보여드리겠습니다. 이 표현을 전개하면 기본적으로5개의 이진 선택으로 요약됩니다. 각 괄호 안에서 어떤 항을 선택할까요?

만약 여러분이 각각의 괄호 안에서 1를 선택한다면, 그것은 어떤 원소도 선택하지 않은 공집합에 해당할 것입니다. 반면에, 만약 제가 엑스를 하나의 항으로 선택하고다른 모든 항에서 1을 선택한다면, 그것은 숫자 1을 포함하는 한원소 집합과 대응할 것입니다.

마찬가지로, 엑스² 항을 선택하고, 다른 모든 항에서 1을 선택하면 2만 포함된 집합에해당합니다. 엑스³ 항을 선택하는 것은 숫자 3을 포함하는 집합에 해당합니다.

하지만 흥미롭게도, 제가 엑스¹항, 엑스²항, 그리고 다른 모든 항에서 1을선택하면 어떻게 되는지 보세요. 이것은 {1, 2}인 부분집합과 대응하고다른 모든 것들로부터 대응하지 않습니다. 하지만 다항식에서는 전개하면 엑스³처럼 보입니다.

그래서 우리는 두 개의 다른 엑스³항을 가지고 있는데, 각각의 항은 합이 3인 부분집합에서 나온 것입니다.

그리고 솔직히, 제가 여기서 하는 것은 아마도 가장 쉬운 패턴일 것입니다. 만약 여러분이시간을 내서 여기서 모든 것을 전개했을 때 어떤 일이 일어나는지 스스로 생각해 보세요.

기본적으로 모든 가능한 부분집합은 이 전개식의 항 중 하나에 대응하며,중요한 것은 해당 전개에서 얻은 항에서의 지수가 해당 부분집합의 합과 같다는 것입니다.

큰 소리로 말할 때는 좀 헷갈리지만, 다시 한 번 생각해보면제 말이 무슨 뜻인지 알 수 있을 것 같습니다.

예를 들어, 모든 일이 끝나고, 32개의 항을 모두 모으면,이 항들 중 3개는 엑스¹⁰ 항이며, 각 항은 합이 10인 원소의선택에서 나온 것입니다. 보통 다항식을 쓸 때, 우리는 모두 같은 항을 모아서 세 개의 엑스¹⁰의 복사본을 보는 대신 엑스¹⁰ 앞에 있는 계수 3을 보게 됩니다. 따라서 이러한 각 계수는 특정 합이 있는 부분집합의 수를 표현하는 방법입니다. 이것은 제가 처음에 말씀드린 것처럼, 생성 함수라고 불리는 것의 한 예시입니다. 여기서 아이디어는 각각의 양의 정수와 관련된답을 가진 질문을 하는 것입니다. 그렇다면, 우리의 경우, 몇 개의 부분집합이 특정 값에 더해질까요?

그 질문에 대한 답변에 대응하는 계수를 가진 다항식을 구성할 때, 이 다항식의 속성을 수학적으로 조작하고 분석함으로써 원래의 질문으로부터놀라운 양의 통찰력을 얻을 수 있습니다. 함수를 생성하는 예는 많고 많지만, 특히 재미있는 것은 같은 아이디어를 사용하여 피보나치 수를 연구할 수 있으므로이 다항식의 모든 계수를 피보나치 수로 만드는 것입니다.

그리고, 이 경우, 이것은 무한 다항식이기 때문에, 저는 이것을 멱급수라고 불러야 합니다.

자세한 건 여기서 설명하지 않고 궁금하신 분들을 위해서 화면에 남겨두겠습니다.

기본 아이디어는 피보나치 수를 정의하는 데 사용되는 규칙이이 함수의 관점에서 방정식으로 표현될 수 있다는 것입니다.

이 방정식을 사용하면 해당 함수를 대체 형식으로 작성할 수 있습니다.

그리고 다음은 제가 건너뛰는 대부분의 세부정보입니다.

알고 있는 부분을 조작하는 경우 여기에 약간의 기하급수에 지수의 확장을사용하면 각 개별 피보나치 수에 대해 정확한 닫힌 표현 형식을 얻을 수 있습니다.

정말 멋지죠. 저는 이것을 빙산의 일각에서 보여드리기 위해 언급했습니다.

생성 함수의 개념은 우리의 특정한 예시보다 훨씬 뛰어넘는다는 사실입니다.

이제 우리의 특정 문제에서 {1, 2, 3, 4, 5}가 있는 간단한 예제에서최대 2,000까지의 모든 숫자가 있는 큰 예제로 확장하면해당 생성 함수에는 이러한 2,000개의 서로 다른 항이 포함됩니다. (1+엑스)(1+엑스²)...(1+엑스²⁰⁰⁰) 처럼요 그리고 이 아이디어는 만약 여러분이식을 전개한다면, 계수는 우리가 원하는 모든 정보를 우리에게 알려준다는 것입니다.

자, 실제로 그것을 전개하는 것은 미친 짓이겠지만, 원칙적으로 그것이 어떻게 보일지 여러분의마음 한구석에 새겨두는 것이 도움이 됩니다. 예를 들어, 원칙적으로 식을 전개한 경우엑스²⁵ 항의 계수가 142라는 것을 알 수 있으며, 이는 합이 25인 142개의 서로 다른부분집합이 있다는 사실과 대응합니다. 그래서, 여기서 생성 함수를 분석하는 기술은 실제로 식을 전개하지 않고 이러한 계수를 추론하는 것입니다.

앞으로 나아가서, 이 전개를 좀 더 추상적으로 쓰려고 합니다.

𝒏=0에서 대문자 𝑵까지의 합으로 말이죠. 여기서 𝒄_𝒏은 우리가 모르는 계수를 알려 줍니다.

이 모든 것은 우리에게 블랙박스로 시작됩니다. 그리고 앞으로 나아가, 우리는 이것을실제 함수로 다루기 시작할 것입니다. 엑스를 대입하면 값이 무엇인지 알 수 있습니다.

그런 다음 이 값이 계수에 대해 무엇을 알려줄까요? 예를 들어, 매우 쉬운 입력은 엑스가 0일 때 입니다.

이 경우 중요한 것은 위의 인수분해 형식을 사용하여 계산하는 방법을 알고 있다는 것입니다.

엑스=0을 대입하면 모든 항이 1과 같으므로 답은 1입니다.

그리고 전개된 형태에서 엑스와 관련된 모든 항이 제거되고, 즉, 0이 되고첫 번째 항 𝒄_0만 남습니다. 자, 이 경우, 그것이 우리에게 그렇게 흥미로운 것을 말해주는 것은 아닙니다. 그것은 본질적으로 하나의 공집합이 있다는 것을 의미하지만,우리는 단지 우리의 발을 적시고 있다는 것을 의미합니다. 다음 예시로, 𝒇를 한번에 알아내는 방법에 대해 생각해 봅시다.

이것은 우리가 알고 있는 표현으로 우리가 할 수 있는 것입니다.

이 엑스의 모든 항에 1을 대입하면 모든 항은 2가 됩니다. 그래서 결과적으로 우리는 2를 2000번 곱하게 됩니다.

반면에, 전개된 형식에서 엑스에 1을 대입하면 엑스의 모든 거듭제곱은 1이 됩니다.

그래서 우리는 기본적으로 모든 계수를 더합니다.

생각해보면 아주 멋진데요, 함수를 하나의 숫자로 계산하면모든 계수의 합이 얼마인지 추론할 수 있습니다.

자, 다시 말씀드리지만, 이 예에서는 그다지 흥미로운 것은 아닙니다. 왜냐하면 우리는 이미 이 계수들의 합이 얼마인지 알고 있기 때문입니다.

각 계수는 특정 합을 갖는 부분집합의 수를 센다는 것을 기억하세요. 따라서 이들을 더하면 2²⁰⁰⁰개인 부분 집합의 수를 모두 세는 것입니다. 하지만 이 함수를 -1로 계산한다면정말 새로운 사실을 알 수 있습니다. 이 함수가 무엇을 의미하는지 잠시 생각해 봅시다.

-1을 대입하면 다시 우리가 알고 있는 것부터 시작하면, 인수분해된 표현식이 맨 위에 있고, 여기서 필요한 것은 엑스를 대입할 때 첫 번째 항을 보는 것뿐입니다.

첫 번째 괄호는 0이 되므로 전체 표현식은 0이어야 합니다.

하지만 모든 계수를 사용하는 전개된 표현식에 적용할 때 이는 무엇을 알게될까요?

그리고 이 해법이 취하는 이상한 관점을 최대한 암시적으로 나타내기 위해,이 표현식에서 회전의 관점으로 여러번의 -1 거듭제곱을 실제로 시각화하기를 바랍니다.

첫 번째 항은 (-1)⁰으로, 우리는 0에서 1까지의 벡터로 그릴 것입니다.

그리고 (-1)¹ 은 그냥 -1 그 자체입니다.

그전의 항에서 180°로 회전된 거라고 생각하시길 바랍니다.

그리고 (-1)²을 하면, 다시 180° 회전하고, 일반적으로 여기서 연속되는 각 항은 180° 씩 회전하는 것처럼 보입니다. 대수적으로, 이것이 의미하는 것은짝수 계수와 홀수 계수 사이에 진동하는 합이 있다는 것입니다.

여러분의 마음 한구석에 이런 시각적인 것을 담아두세요. 이 식은 모든 생성 함수에 해당하지만,특수 생성 함수에 대해서도 이 값(엑스=-1), 즉, 이 교대 합이 0과 같아야한다는 것을 알고 있습니다. 그리고 여러분이 해석할 수 있는 방법은짝수 계수와 홀수 계수 사이에 균형이 있다는 것입니다.

그리고, 기억하세요. 이 작은 예제에서, 이 계수들은 부분 집합에 대한 사실들을암호화하고 있습니다. 그래서 만약 모든 짝수 계수와 홀수 계수 사이에동일한 균형이 있다면, 모든 부분 집합의 절반은 짝수의 합을 가지고 있고, 나머지 절반은 홀수 합을가지고 있다는 것을 의미합니다. 이런 결과는 아마도 당신이 기대하는 것입니다.

하지만 처음에는 어떻게 그것을 보여줄지는 분명하지 않지만, 생성함수을 통해 기대하는 것이 바로 튀어나옵니다.

그리고, 우리가 어디로 가고 있는지 암시하기 위해, 우리가 계산한 마지막 두 식을 다시 쓰고,그 두 식을 더하고 나서 반으로 나누도록 하겠습니다.

생각해보면, 이것은 모든 짝수 계수를 걸러내고 모든 홀수 계수를 없애는 방법입니다.

그래서 모든 짝수 계수의 합이 전체 합계의 절반처럼 보인다는 사실을적는 것이 특히 깔끔한 방법이 될 겁니다. 여러분 마음 한구석에서 다시 말씀드리자면,짝수 계수의 합은 전체 합계의 절반처럼 보일 것입니다. 이것은 말할 필요도 없이, 우리가 대답하고자 하는실제 질문에 감질나게 가깝습니다. 우리가 하고 싶은 것은,   5의 배수에 해당하는 모든 계수를 얻을 수 있도록잘 선택된 숫자를 𝒇 함수에 계산 하는, 영리한 일을 찾는 것입니다.

다시 말하지만, 이 계수가 우리에게서 무엇을 암호화하는지 다시 생각해보면,합이 5로 나눌 수 있는 부분 집합의 총 수를 계산하는 최종 질문에 대한 답이 될 것입니다.

이것을 할 수 있는 방법은 연속된 거듭제곱이 앞뒤로 회전하는 것을 일반화하는 것입니다.

하지만 이번에는 매 다른 때 마다 회전하는 것을 원치 않습니다. 우리는 그것들이 어떻게든 5의 주기로회전하는 것을 원하기 때문에, 우리는 복소평면으로 확장을 합니다.

위쪽에 보시면 값을 찾을 수 있습니다. 이 값을 연속해서 거듭제곱을 하면 5분의 1 회전하여 5의 주기를 갖는 과정을 얻을 수 있습니다. 만약 여러분이뒤로 물러서서 본다면, 제가 여러분에게 복소수에 대해 생각해보라고 하는 것은좀 터무니없다는 것을 압니다.

제 말은, 우리는 개수 세기 질문으로 시작했다는 것입니다. 이산적인 수학이지만, 그렇게 생소하지 않기를 바랍니다.

그리고 다시, 제가 솔루션의 다양하고 이상한 관점을 보여주기 위해 무언가를 조정하는 이유는사실 이 과정들이 실제로 더 넓은 수학 체계에서는 그다지 이상하지 않기 때문입니다.

우리가 적용하고자 하는 기술은 복소수를 사용하여 정수의 이산적인 질문을 더 잘 이해하는다른 많은 사례들과 상당히 유사합니다. 그래서 여러분이 스스로 발견할 수 있었던 "무언가"로 느껴질수록, 여러분이 이 원에서 미래의 어떤 문제에 대해 연구할 때 스스로 발견하게 될 거라고 느낄 수 있습니다.

구체적으로 말씀드리면, 제가 신경 쓰는 복소수는 제가 ζ라고 말할 것이고,이것은 단위원 둘레의 5분의 1 회전입니다. 그래서 ζ의 각도는 2파이/5 라디안이고 크기는 1입니다. 즉, 오일러 공식을 사용하여 𝒆^(2파이𝒊/5) 으로 명시적으로 표기합니다. 만약 여러분이 이 표기법에 익숙하지 않다면,여러분은 이것을 실수 부분의 코사인(72°) 그리고 허수 부분은 사인(72°) 라고생각할 수 있습니다. 그리고 72°는 전체 회전(360°)의 5분의 1입니다. 217 00:18:02,400 --> 00:18:06,160  하지만, 솔직히 말해서, 여러분은 실제로 정확한 값에 대해 생각할 필요가 없습니다.

대신, 중요한 것은 이 수가 가지고 있는 속성입니다.

예를 들어, 제곱을 했을 때, ζ의 크기가 1이므로 그 크기의 제곱 또한 1이 됩니다.

하지만 단위 원을 중심으로 5분의 1 회전합니다. 결과적으로 단위원의 5분의 2를 회전합니다.

비슷하게, 세제곱을 하면 5분의 3 회전 하고,네제곱을 하면 5분의 4 회전 하고,5제곱은 다시 1로 돌아갑니다. 마치 0제곱을 했듯이, 5번마다 순환합니다.

이것들이 우리가 주의해서 봐야할 것 입니다.

이 숫자들은 "1의 다섯제곱근" 이라는 특별한 이름을 가지고 있습니다.

왜냐하면 이것들은 방정식 𝒛⁵=1 을 풀고, 실제로 1의 다섯제곱근이기 때문입니다.

만약 여러분이 누군가에게 이 방정식을 보여준다면, 그들은 아마도 그 답이 분명히𝒛=1이라고 말할 것입니다. 하지만 복소평면에는 4개의 다른 답이 있다는 것입니다.

4개의 다른 숫자를 다섯제곱으로 할 1를 얻고 이를 집합체로 간주하는 것은종종 매우 유용합니다. 그 방정식을 기억하세요. 조금 후에 우린 다시 볼 겁니다.

그래서 우리가 이전에 했던 것과 유사하게, 우리가 이 홀수 항들을 소거하기 위해 𝒇(1)와 𝒇(-1)를 더한 것과 같이, 우리가 할 일은 이 다섯 개의 숫자 모두에서𝒇를 계산한 다음 그것들을 합친 다음, 우리는 어떤 소거가 있기를 바랍니다.

좀 복잡해 보일 수도 있지만, 𝒇엑스=엑스와 같은 아주 간단한 예를 들어 보겠습니다.

이 경우, 이 다섯 가지 항을 더하면,우리는 단지 ζ⁰ + ζ¹ + ... + ζ⁴ 와 같은 거듭제곱근를 더하는 것입니다.

복소수를 더하면, 어... 꼬리물기와 같은 벡터의 덧셈처럼 생각할 수 있습니다.

ζ⁰ + ζ는 이렇게 보일 것입니다. 그리고 만약 제가 ζ의 제곱을 더하면,그 벡터의 꼬리를 마지막 것의 끝으로 가져갑니다 그리고 비슷하게, 만약 제가 ζ³의 꼬리를ζ⁴의 꼭짓점까지 가져간다면, 여러분은 어떻게 전체 합이 0이되는지를 볼 수 있을 것입니다. 이것에 대해 생각하는 또 다른 방법은이 다섯 개의 항 모두 0을 중심으로 균등하게 균형을 이루고 있다는 것입니다. 이 ζ들의 중심은 원점에 있습니다. 이제 𝒇엑스가 엑스²이라면 조금 덜 사소한 예를생각해 보는 것이 도움이 됩니다. ζ⁰을 제곱하면 ζ⁰으로 유지합니다.

이것은 단지 숫자 1을 말하는 화려한 방법일 뿐입니다. ζ를 제곱하면 ζ²를 얻습니다.

그래서 여기 위에 있는 이 점이 우리가 ζ²의 점으로 이동하는 것을 상상할 수 있습니다.

ζ²은 ζ⁴로 이동합니다. 그래서 여러분은 이 점이 ζ⁴로 이동하는 것을 상상할 수 있습니다.

ζ³는 ζ⁶까지 이동하는데, 5번 마다 한 바퀴씩 돌기 때문에ζ³는 ζ¹까지 움직입니다. 그래서 이 점이 위로 이동하게 됩니다.

마지막으로 ζ⁴의 제곱은 ζ⁸이 됩니다. 즉, ζ³으로줄여지고, 이렇게 그릴 수 있습니다. 생각해보면 좀 헷갈리겠지만, 특히 제가 여기서 그린 모든 화살표들을 생각해볼 가치가 있습니다. 왜냐하면 여기의 아이디어는 우리가 이 모든 다른 항들을 제곱할 때, 저는 모든 항들이 가지고 있는 각도를 두 배로 늘리도록 프로그래밍을 하기 때문입니다. 전체적인 결과는 그냥 섞이는 것입니다.

우리는 다른 순서로 쓰지만 같은 수를 얻기에, 그들의 합은 여전히 0이 될 것입니다.

비슷하게, 여러분이 엑스³ 으로 연습할 때, 여러분이 이 점들의 끝점을 따라간다면,우리가 이 점들을 세제곱할 때, 즉, 우리가 각각의 점들이 가지고 있는 각도를 3배를 할 때,우리는 단지 같은 항들을 섞어서 다른 순서로 나타내는 거와 같습니다. 놀랄 것도 없이, 우리의 함수가 엑스⁴ 이어도 같은 일이 일어납니다.

하지만 중요한 것은 엑스⁵인 함수를 고려했을 때 상황이 변하는 것입니다.

이 경우 ζ를 5제곱 하면, 정의상 1이 됩니다.  마찬가지로, ζ²을 5제곱 하면 1이 됩니다. 이 모든 것이 1로 이어지는데, 이들은 거듭제곱근이기 때문입니다. 결국, 이것이 그들이 존재하는 목적입니다.

그래서 이 경우, 우리가 이 함수를 적용하고 모두 더하면, 0으로 가서 소거하는 대신 일종의 간섭을 받게 됩니다.

모두 1이므로 합은 5가 됩니다. 따라서 뒤로 물러나서,이 모든 예가 의미하는 바를 생각해보면, 본질적으로 이 표현은 5로 나눌 수 없는 엑스의거듭제곱에 대해서는 0이 될 것이지만, 5로 나눌 수 있는 엑스의 거듭제곱에 대해서는0이 아닌 것으로 이동합니다. 그리고 이것은 정확히 우리가 찾고 있는 종류의 필터입니다.

만약 여러분이 우리의 실제 함수가 단순한 엑스의 거듭제곱보다 훨씬 더 복잡하다는 것을 걱정해도,기본적으로 모든 것이 선형이기 때문에 모든 것이 괜찮습니다.

만약 𝒇가 어떤 거대한 다항식이고 우리가 이 큰 합을 계산하기를 원한다면,여러분은 열과 열로 분류하는 것을 생각할 수 있습니다. 매번 여러분은 ζ의 거듭제곱을 더하고 대부분의 경우 그 모든 거듭제곱이 서로 소거되고 0이 됩니다. 하지만 그 모든 거듭제곱이 5의 배수일 때,그것들은 구조적으로 간섭합니다. 즉, 해당 계수가 무엇이든 간에 5배를 얻을 수 있습니다.

잡초 속 깊은 곳에서는 우리가 왜 여기 있는지 잊기 쉽지만,각각의 계수는 우리에게 얼마나 많은 부분집합의 개수가 특정 값에 있는 지를 알려줍니다.

그래서 우리가 원하는 것은 5의 배수인 모든 계수를 더하는 것이고, 우리가 지금해야 하는 것은 그것을 명시적으로 하는 방법입니다. 만약 우리가 이 다섯 가지의서로 다른 거듭제곱근에서 이 함수를 계산한다면, 약간 이상하게 보이지만, 우리가 해야 할 일은 5로 나누는 것입니다.

그러면 우리가 원하는 합을 얻을 수 있습니다. 정말 멋지네요. 우리는 단지 부분집합에 관한 질문을가지고 있습니다. 이산적인 수학 문제이지만, 우리가 질문에 대답할 수 있는 방법은우리가 현명하게 선택한, 일반적이지 않은 복소수에 관한 다항식을 계산하는 것입니다.

수학을 더 많이 할수록 덜 미친 것처럼 보입니다. 왜냐하면 복소수들은 이산 수학과기이한 관계를 가지고 있기 때문입니다. 그런데도 이 관계에 대해 다른 방법이 없다는 것은 정말 멋진 일입니다.

그러나 여러분 중 일부는 우리가 이러한 거친 표현을 다항식에서 계산하는 방법이 유일한 방법이란 것에 대해 불평할 수 있습니다. 자, 기억하세요. 우리가 알고 있는 다항식의 편한 형태는 인수분해된 형태입니다. (1+엑스)(1+엑스²)...(1+엑스²⁰⁰⁰)처럼 말이죠.

지금까지의 모든 것은 우리가 실제로 소매를 걷어붙이고 정직한 계산을 하지 않는 한,하나의 어려운 문제를 다른 문제로 밀어넣는 무의미한 상징적 놀이에 불과합니다.

이것이 우리 주장의 마지막 요지이므로, 뒤로 물러나 심호흡을 헤보세요. 292 사실 여러분이 생각하는 것만큼 나쁘지는 않지만, 여러분이 우리가필요로 하는 거듭제곱근 중 하나, 즉 ζ 그 자체를 계산할 수 있을지 생각해 봅시다.

그래서 이 모양은 (1+ζ)(1+ζ²)(1+ζ³)... 을 계속해서 반복하는 것입니다.

단, 처음 5개 항 이후에는 모든 것이 반복되기 시작합니다.

왜냐하면 ζ의 2000까지의 거듭제곱은, 전체 식이 기본적으로 그냥 이 표현을400번 복사하는 거와 같기 때문입니다. 이 식을 계산하는 것은 여전히 어려워 보이지만,2,000개의 다른 항을 곱하는 것보다 훨씬 쉽습니다. 여러분이 이것을 시각화할 수 있는 방법은우리가 각각의 거듭제곱근에 기본적으로 하나를 더한다면, 그것들을 모두 오른쪽으로 옮기는 것입니다.

이 그림은 우리가 예상할 수 있는 숫자에 대한 기하학적인 직관을 제공해줍니다.

우리가 원하는 것은 이 다섯 개의 서로 다른 복소수들, 즉, 이 다섯 개의 노란 점들의 곱 입니다.

그리고 만약 여러분이 복소수에 대해 한 두 개 알고 있다면, 이들은 켤레복소수 이기 때문에우리가 정말로 필요한 것은 이 다섯 개의 노란 선들의 길이를 곱하는 것입니다.

예를 들어, 가장 오른쪽에 있는 점은 1+ζ⁵ 에 해당합니다.

그래프에서 저는 ζ⁰ + 1 로 표기하고 있습니다. 하지만 두 경우 모두숫자 2를 쓰는 멋진 방법일 뿐입니다.

그 옆에는 1+ζ, 1+ζ⁴ 가 있고 모두 같은 크기를 가지고 있습니다.

이 선들의 길이는 같으며 𝑳₁이라는 이름을 붙이도록 하죠.

따라서 길이 𝑳₁²에 그 개수인 2를 곱해야 합니다. 마찬가지로,나머지 두 값은 ζ²+1과 ζ³+1입니다. 이 두 값은 길이가 같고켤레이므로 𝑳₂라고 부르겠습니다. 그래서 우리의 곱은 그 𝑳₂와, 그 복사본 두 개를 포함해야 합니다.

만약 우리가 느슨한 휴리스틱 추측을 하고 있다면, 여러분은 𝑳₁이 1보다 조금 더 긴 길이이고 𝑳2가1보다 조금 더 짧은 길이라는 것을 알아차릴 수 있을 것입니다. 그래서여기의 마지막 답은 거의 2일 것입니다. 우리가 그 값을 잘 알지는 못해도, 2 근처인 것은 압니다. 이것을 정확한 답으로 알아내려면 전체 식을 전개하면 됩니다. 항이 32개나 되는 것은 솔직히 그렇게 나쁘진 않아요.

좋아요, 당신은 지금까지 이 영상을 오래 보고있고, 저는 시간이 많이 됐다는 걸 압니다

하지만 이 모든 논증에서 우리의 마지막 단계를 여러분이 생각하는 것보다 훨씬 더 단순하게만드는 마지막 요령이 하나 있습니다

이제 우리가 어디에 있는지 다시 한번 말해보겠습니다. 우리는 합이5로 나누어지는 1에서 2000까지의 부분집합의 수를 세어보라는 질문으로 시작했습니다.

그런 다음 각각의 계수가 값 𝒏에 대해 특정 합을 갖는 부분 집합의 수를 나타내는 다항식을 구성했습니다.

그래서 우리가 원하는 것은 그 다항식의 매 5번째의 계수를 더하는 것입니다.

그리고 우리는 어떻게 이 다항식을 다섯제곱근에 대한 함수로 계산하는지, 그리고 그것들을 더하면우리가 원하는 필터를 얻을 수 있는지를 보았습니다. 여기서 우리는 단지 그 항들 중 하나𝒇(ζ)를 계산하고 있습니다. 𝒇(ζ)는 본질적으로 5개의 복소수의 곱으로 나타나게 됩니다.

그 곱을 실제로 계산하는 아주 교묘한 방법으로, 여기 마지막 요령이 있습니다. 기억하세요,저는 이 숫자들을 "거듭제곱근" 이라고 표현했습니다. 이 숫자들은 방정식 𝒛⁵=1 를 풀죠.

그것에 대해 생각할 수 있는 또 다른 방법은 다항식 𝒛⁵-1의 근이라는 것입니다.

이것이 의미하는 바는 다항식 𝒛⁵-1을 인수로 대응시켜서 이렇게 볼 수 있다는 것입니다.

여기서 각각의 거듭제곱근에 해당하는 하나의 인자가 있습니다.

여러분은 각각의 𝒛에서 거듭제곱근을 빼면 됩니다.

이 식은 모든 것을 전개했을 때 발생되는 모든 소거는 마법과 같은느낌이겠지만, 하지만 실제로 계산되고, 지금 우리에게 매우 유용합니다. 왜냐하면 오른쪽에있는 표현은 우리가 위에서 계산해야 하는 것과 거의 비슷하게 보이기 때문입니다.

기본적으로 마이너스 부호가 있습니다. 플러스 부호가 있었으면 하는 곳에 마이너스 부호가 있습니다.

비결은 𝒛에 -1을 대입하는 것 입니다. 만약 그렇게 한다면, 기본적으로 우리가원하는 것의 음수를 가지게 됩니다. 그래서 만약 -1을 곱하면여기 왼쪽에 -1에서 1을 뺀것, 즉 -2는 결국 2가 됩니다.

그리고 나서 오른쪽이 우리가 계산하고자 하는 것으로 바뀝니다.

우리의 기하학적인 직관이 앞서 언급했던 것처럼,답은 2에 가까울 뿐만 아니라, 마법처럼 정확하게 2로 밝혀졌습니다.

그것은 사실 매우 훌륭하고, 매우 사랑스럽습니다. 왜냐하면 우리가 계산하고자 하는이런 큰 식을 뜻하기 때문입니다. 우리가 거듭제곱근에 𝒇를 더하면,우리는 ζ¹에 대한 값을 알게 됩니다. 2⁴⁰⁰ 이죠.

본질적으로 동일한 추론으로 다음 세 개의 거듭제곱근에 대한 값도 2⁴⁰⁰ 라는 것을 보여줍니다.

왜냐하면, 여러분이 ζ² 또는 ζ³와 같은 거듭제곱을 할 때,여러분은 같은 수의 목록을 얻게 되고, 그것들은 단지 다른 순서로 섞이게 됩니다.

유일하게 다른 점은 ζ⁰ 을 계산했을 때입니다. 하지만 ζ⁰ 은 숫자 1을 표현하는멋진 방법이고, 우리는 이것을 한 번에 계산하는 방법을 알고 있습니다. 아주 쉬운 일 중 하나죠. 우린 이미 했었죠. 이 모든 괄호들은 2로 변합니다. 그래서 2를 2000번 곱한 것처럼 됩니다. 마지막으로, 우리는 계산 질문에 대해 매우 분명한 답을 가지고 있습니다.

5로 나눌 수 있는 이 모든 계수를 더하면, 즉 5로 나눌 수 있는 총 부분집합이얼마나 되는지 세는 방법입니다. 답은 이 기묘하고 복잡한 식의5분의 1입니다. 그니까, 방금 계산한 값인2²⁰⁰⁰+4×2⁴⁰⁰의 5분의 1입니다.

여기서 이 답이 타당한지, 간단한 검사를 해 봅시다.

예를 들어, {1, 2, 3, 4, 5}와 같은 작은 예시에서방금 설명한 것과 동일한 작업을 수행하면,답은 2⁵ +4×2¹의 5분의 1인 부분집합의 수,즉 (32+8)의 5분의 1인 8이 된다는 것을 알 수 있습니다.

그리고 우리가 그것들을 분명히 봤을 때를 기억한다면, 8은 정답이 맞습니다.

보세요, 이것은 어려운 퍼즐이고, 어려운 문제를 해결하기 위해 시간을 들일 가치가 있을 때,그것은 또한 곰곰이 생각해 볼 가치가 있습니다. 이걸로 뭘 얻을 수 있죠? 뭐를 가져갈 수 있죠?

여러분은 어떻게 지배적인 부분이 우리가 추측했던 것처럼 실제로 전체 부분집합들의 5분의 1이 되는지, 그리고 어떻게 우리가 생각 못 한 항이거듭제곱근의 간섭으로부터 생겨났는지를 생각해 볼 수 있습니다.

하지만 이 질문을 흥미롭게 만드는 것은 답이 아니라 우리가 그것을 푸는 방법입니다.

즉, 우리가 이해하고자 하는 이산적인 수열을 가지고,다항식의 계수처럼 생각한 다음, 복소수 값에 대해 다항식을 계산합니다.

이 두 단계 모두 처음에는 매우 예상치 못한 것일 수 있습니다.

하지만 이 두 단계는 수학의 다른 곳에서 볼 수 있는 매우 일반적이고 강력한 기술과 관련이 있습니다.

예를 들어, 수업의 맨 처음에, 저는 우리가 사용할 기술은소수가 연구되는 방법과 리만 가설과 그와 비슷한 것들을 이끌어내는 아이디어와 유사할 것이라고 약속했습니다.

자, 이건 아주 아름다운 주제입니다. 그래서 어떤 버전을 성급하게 영상 끝에넣는 것은 작은 범죄처럼 보일 정도입니다. 제가 생각하는 옳은 일은,제가 얼마 전에 약속했던 ζ 함수에 대한 영상을 만드는 것입니다.

시간을 내서, 한번 해보세요. 하지만 궁금하신다면, 제가 설명하지 않고 화면 위에 몇 가지를올려놓을 수 있도록 허락해 주신다면, 다음은 두 문장이 어떻게 유사한지에 대한 두세 문장 버전입니다.

우리의 부분집합 퍼즐처럼, 리만이 소수를 연구하는 방법은 우리가 이해하고자하는 이산 수열을 포함합니다. 소수에 대한 정보를 담고 있는 무엇인가가 있고,그 수열의 항이 계수인 함수를 고려합니다.

이 경우, 이것은 다항식이 아니라, 디리클레 급수 (혹은 Dir-ick-ley 급수,사람마다 다르게 발음함)로 알려진 구조이지만, 같은 본질적인 아이디어입니다.

그런 다음, 이러한 계수에 대한 정보를 알아내는 방법은이 함수가 복소수 값에 대해 어떻게 작용하는지를 연구하는 것입니다.

리만의 경우 기술은 훨씬 더 정교해졌습니다. 결국, 리만은 복소해석의 선구자가 됐습니다.

하지만 사실, 정의역을 실수 이상으로 확장하면, 수학자들은 계수에 대한추론을 할 수 있는 훨씬 더 많은 힘을 가질 수 있습니다.

일부 시청자들에게, 이 모든 것은 왜 정확히 복소수들이이런 식으로 지나치게 유용한지에 대한 궁금증을 남길 수 있습니다.

정확히 답하기 어려운 질문이지만, 퍼즐을 생각해보면 우리가 방금까지했던 모든 것들은 서로 다른 입력들을 대입하면 계수에 대한숨겨진 정보가 드러나는 것처럼, 더 많은 입력을 할 수록 더 좋습니다.

그래서 여러분은 복소평면과 같이 더 풍부한 숫자의 공간으로 자신을 개방할 수 있습니다.

하지만 여기서 벗어나길 바라는 더 구체적인 직관이 있습니다.

우리의 퍼즐에서, 우리가 원했던 관련 사실, 매 5번째 계수의 합은 일종의 주기 질문이었습니다. 그리고 다른 구조와 달리, 복소수가 우리에게유용한 것으로 입증된 실제 이유는 연속적인 곱이, 이러한 순환 동작을하는 값을 찾을 수 있기 때문입니다. 특히 주기 정보를 알아내기 위해단위원과 거듭제곱근에 대한 값을 사용하는 것은 매우 효과적입니다.

이 아이디어가 얼마나 도움이 되는지 과장하는 것은 거의 불가능합니다.

수천개의 예들 중 하나를 들어보자면, 1990년대에 Peter Shor는 양자 컴퓨터가일반 컴퓨터보다 훨씬 빠른 방식으로 큰 숫자를 소인수분해하는 방법을 발견했습니다.

우리가 "쇼어 알고리즘"이라고 부르는 것이 어떻게 작동하는지 자세히 살펴보면,아이디어는 본질적으로 일종의 주기를 찾기 위해 거듭제곱근을 사용하는 것입니다.

더 일반적으로, 이것은 푸리에 변환과 푸리에 급수의 기초가 되는 핵심 아이디어이며, 그것들로부터 오는 무한한 주제의 팽창입니다.

함수 생성에 관한 주제에 대해서는, 우리는 여기서 단지 표면만 긁었습니다.

만약 여러분이 더 배우고 싶다면, 저는 Herbert Wilf의 책인생성함수론(재밌는 이름이네요)을 강력히 추천합니다. 저는 또한 이 아이디어로 근육을 좀 더유연하게 하고 싶은 사람들을 위해 몇 가지 재미있는 퍼즐을 여기 스크린에 남기겠습니다.