Mobius inversion is used in combinatorics. Richard Stanley book has a chapter on mobius inversion. It is a very very very very beautiful chapter. It is so divine and beautiful.
One of my favorite applications is finding an explicit formula for cyclotomic polynomials. Let Φ_n(x) be the minimal polynomial of exp(2πi/n). With some thought you can convince yourself that x^n-1 is the product of Φ_d(x) over all d dividing n. But then log(x^n-1) = sum log Φ_d(x), so by Möbius inversion we get log Φ_n(x) = sum μ(n/d) log(x^d-1), or Φ_n(x) = prod (x^d-1)^μ(n/d). As an example, Φ_30(x) = (x^30-1) (x^5-1) (x^3-1) (x^2-1) / (x^15-1) (x^10-1) (x^6-1) (x-1) = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1.
super excited for this! i’ve been playing with some numerical sequences and discovered the Mobius function in my quest to understand them but this is gonna help me out much more than what i could glean on my own
It is… he just writes the coefficient as addition or subtraction. g(6) = f(6) - f(3) - f(2) + f(1) = 1*f(6) + -1*f(3) + -1*f(2) + 1*f(1) = μ(1)f(6) + μ(2)f(3) + μ(3)f(2) + μ(6)f(1) = Σμ(d)f(n/d) for all d | n when n = 6
It should probably be noted that these Möbius pairs are ordered pairs. We can restate what's happening in the following way: the first condition on f and g is equivalent to saying f is equal to the Dirichlet convolution of g with the constant function 1, where Dirichlet convolution is this sum over divisors d of n of one function at d and the other at n/d. Then what Möbius inversion allows us to do is say that g is the Dirichlet convolution of f with μ, that is, 1 and μ are Dirichlet inverses, their Dirichlet convolution is ε, the unit function with ε(n) = δ_n,1. So from any arithmetic function f, we can compute a sequence, infinite in both directions, by computing Dirichlet convolution with 1 to go in one direction, and with μ to go in the other. This shows how the Möbius pairs link up. Convolving φ with 1 first gives id_N, then convolving again gives σ. If one instead started with μ, convolving with 1 first gives ε, then 1, then d. Another neat fact is that because Dirichlet convolution preserves multiplicativity, and the Möbius inverse is just Dirichlet convolution with μ, the Möbius inverse of any multiplicative function is also multiplicative.
Nice video. Perhaps another video on ANT would be on Dirichlet series. Using a theorem that you can turn Dirichlet series of multiplicative functions into products (like the prime product form of the zeta function), you can evaluate many dirichlet series in terms of zeta functions. For example, the sum over n of mu(n)/n^s is 1/zeta(s).
8:05 aren't you renaming the same stuffs twice? it's not clear to me Also, does the Mobius pair is transitive? It would be cool! Lastly, are the unexplained parts related with Phi, at the end, related to the properties of the Phi function? Anyway, that's fantastic! nice and clean (except for my doubt expressed in the first sentence of this comment), easy to follow and a majestic correlation :D thank you for sharing!
You can remove the doubt by looking up the properties of the Euler Phi function you don't understand. Figuring out some of the details on your own will be a better learning experience. Much more preferable than begging Dr Penn for "room service" in the comment section.
@@MyOneFiftiethOfADollar Yes, being autonomous is better for many reasons, like improving learning. Do you know how to improve the experience even further? Not mocking. Simple.
@@Chris-5318 what did you think I was referring to? At the timestamp I wrote, Michael writes the fraction d/n. That is likely not even an integer in many cases, and I think it should be n/d.
@@Cloud88Skywalker It seems that you are not familiar with the standard notation that is used in number theory (and combinatorics). He wrote " d | n " that literally means "d divides n". He did not write " d / n " which means "d divided by n". In the first example where n = 6, the divisors of 6 are 1, 2, 3 and 6 that's written as 1 | 6, 2 | 6, 3 | 6 and 6 | 6, but 4 ∤ 6 and 5 ∤ 6 i.e. 4 does not divide 6 and 5 does not divide 6. Division is not defined for the integers. E.g., neither 6 / 4 nor 6 / 5 (or their reciprocals) are integers. The notation Michael used meant that the sum is over all values of d where d is a divisor of n (i.e. d divides n). You should have realised that you were misunderstanding when he wrote f(6) = g(1) + g(2) + g(3) + g(6) at around 3:32. It would make no sense with n / d.
@@Chris-5318 Listen. This is not that difficult. The very first thing I wrote in my first comment is a timestamp to the precise moment Michael writes a FRACTION multiplying *μ(d).* I know what *d | n* means. I'm not speaking about that. The original statement's right-hand side ends with *μ(d)f(n/d).* That, inside function *f,* is a FRACTION. In the last example of the video (my timestamp), *f* is the identity function, so *f(n/d)* becomes... *n/d* I'd expect. But Michael wrote *d/n.* And that's what I'm talking about.
I prefer the proof involving the Partially ordered sets theory. There re much more examples of POSes then the division one and also arithmetic functions such as zeta and mu which is its inverse
@@synaestheziac As I hadn't come across the term "arithmetic function" before, I gave a "definition" that used more familiar terms so that more people could understand what I was saying.
@@Chris-5318 I also hadn’t come across it until Michael used it in this video. But first thought was: isn’t that the same thing as a sequence? I looked it up and found the following answer to my question on stack exchange: “In some sense there's no difference, but in practice when you call something an arithmetic function as opposed to a sequence you are paying attention to the multiplicative structure of N and the examples you care about will be attuned to that multiplicative structure. Examples include the totient function φ(n), the divisor function d(n), etc. This is particularly clear in the definition of a multiplicative arithmetic function, which is one satisfying f(mn)=f(m)f(n) where gcd(m,n)=1.” Which is basically what I was thinking, so I’m satisfied with that.
@@synaestheziac It seems that an AF should be at least multiplicative or additive (as suggested by Hardy & Wright), whereas a general sequence or general number-theoretic function needn't be either. So I stand by my first response and now add that in general a sequence is NOT required to represent an AF (if you defer to H & W). Obviously an AF may be represented as a sequence.
@@MyOneFiftiethOfADollar I’m not native English so maybe I misused the word wait here, I meant it as an interjection ! I noticed it as soon as I saw the thumbnail
At about 8:46 he sort of lost me, because what he was saying didn't exactly seem to hold, but what I think he's doing isn't exactly what he's saying (i.e. sum(where: d|m; mu(dp)) ≠ sum(where: d|(m*p); mu(d), as for instance the second sum contains mu(1), where the first doesn't), but instead he's grouping the divisors into separate sums based on what power of p the respective ’d's contain. From there, it mostly seems to make sense, though I had to watch a second time once I understood what he was getting at with the sums.
sum of mu(d) where d are divisors of n = sum of mu(d) where d are divisors of mp^r = sum of mu(dp^r) where d are divisors of m, so where did he get all of the sums with dp, dp^2,...?
@@MyOneFiftiethOfADollar It really is quite astonishing to see someone troll Michael Penn's comments just to insult everyone. My deepest sympathies to anyone who has the displeasure of knowing you.
@@BudgieJane well, because the pictures on it seem to suggest that the surface is not orientable even though it is and because the video already mentions Möbius.
So many claims that a term is "so called". Faintly condescending OR do you doubt name is historically factual/accurate? For example, do you believe that Mobius had nothing to do with creating the famous function that bears his name? Perhaps it is as simple that tons of math lecturers just think it sounds cool and erudite/informed. Also the claim that something is "interesting" often means "I don't quite understand it yet".
Possibly the first time I saw this inversion was related to the prime zeta function. It's the Riemann zeta function but only summed over the primes en.wikipedia.org/wiki/Prime_zeta_function. The series for this converges for Real(z)>1. But inversion gives a series that converges faster, and for Real(z)>0 !!! en.wikipedia.org/wiki/Prime_zeta_function Worth another video, with some other properties of the primezeta function?
my favorite part of number theory is when michael penn said its mobin time and then inverted all over the place
Sounds like just about anything Michael Penn does is your favorite part
Mobius inversion is used in combinatorics. Richard Stanley book has a chapter on mobius inversion. It is a very very very very beautiful chapter. It is so divine and beautiful.
And see the original paper by Rota.
What are pre requisites
One of my favorite applications is finding an explicit formula for cyclotomic polynomials. Let Φ_n(x) be the minimal polynomial of exp(2πi/n). With some thought you can convince yourself that x^n-1 is the product of Φ_d(x) over all d dividing n. But then log(x^n-1) = sum log Φ_d(x), so by Möbius inversion we get log Φ_n(x) = sum μ(n/d) log(x^d-1), or Φ_n(x) = prod (x^d-1)^μ(n/d).
As an example, Φ_30(x) = (x^30-1) (x^5-1) (x^3-1) (x^2-1) / (x^15-1) (x^10-1) (x^6-1) (x-1) = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1.
it’s mobin time
i was thinking the same
super excited for this! i’ve been playing with some numerical sequences and discovered the Mobius function in my quest to understand them but this is gonna help me out much more than what i could glean on my own
micheal penn
picheal menn
@@erpaninozzobeat me to it...
12:30 very cool, I've never seen a summation that defines two dummy variables at once in this way.
5:25 it should be mobius of 1 before f(6), mobius of 2 before f(3) and so on...
It is… he just writes the coefficient as addition or subtraction. g(6) = f(6) - f(3) - f(2) + f(1) = 1*f(6) + -1*f(3) + -1*f(2) + 1*f(1) = μ(1)f(6) + μ(2)f(3) + μ(3)f(2) + μ(6)f(1) = Σμ(d)f(n/d) for all d | n when n = 6
@@thelocalsage look carefully, he writes 1*f(6) and writes that 1
Very glad to see such a searchable title. Please keep it up 👍
The strip on the thumbnail has two twists... so it is not a Moebius strip! 😂
This is a great mathematics channel!
Last line: d/n, when d | n ? n/d would be integer... probably not a coincidence, that it is the last line...
22:30 if d = 1, the set contains all numbers relatively prime to n. This isn't the same as the set {d, 2d, 3d,... nd} (?)
Indeed. And in fact, when d=1, {d, 2d,...} = {1,...,n}, which IS already n. So the sum over all d|n will be strictly greater than n.
10:33 Inducton hypothesis is not used. Simply saying case n > 1 is enough.
It should probably be noted that these Möbius pairs are ordered pairs. We can restate what's happening in the following way: the first condition on f and g is equivalent to saying f is equal to the Dirichlet convolution of g with the constant function 1, where Dirichlet convolution is this sum over divisors d of n of one function at d and the other at n/d. Then what Möbius inversion allows us to do is say that g is the Dirichlet convolution of f with μ, that is, 1 and μ are Dirichlet inverses, their Dirichlet convolution is ε, the unit function with ε(n) = δ_n,1.
So from any arithmetic function f, we can compute a sequence, infinite in both directions, by computing Dirichlet convolution with 1 to go in one direction, and with μ to go in the other. This shows how the Möbius pairs link up. Convolving φ with 1 first gives id_N, then convolving again gives σ. If one instead started with μ, convolving with 1 first gives ε, then 1, then d.
Another neat fact is that because Dirichlet convolution preserves multiplicativity, and the Möbius inverse is just Dirichlet convolution with μ, the Möbius inverse of any multiplicative function is also multiplicative.
Proof by Induction! Yay! (The fewer BWOC, the better, if you ask me)
Nice video. Perhaps another video on ANT would be on Dirichlet series. Using a theorem that you can turn Dirichlet series of multiplicative functions into products (like the prime product form of the zeta function), you can evaluate many dirichlet series in terms of zeta functions. For example, the sum over n of mu(n)/n^s is 1/zeta(s).
Nice derivation of the phi-function!
8:05 aren't you renaming the same stuffs twice? it's not clear to me
Also, does the Mobius pair is transitive? It would be cool!
Lastly, are the unexplained parts related with Phi, at the end, related to the properties of the Phi function?
Anyway, that's fantastic! nice and clean (except for my doubt expressed in the first sentence of this comment), easy to follow and a majestic correlation :D thank you for sharing!
You can remove the doubt by looking up the properties of the Euler Phi function you don't understand.
Figuring out some of the details on your own will be a better learning experience. Much more preferable than begging Dr Penn for "room service" in the comment section.
@@MyOneFiftiethOfADollar Yes, being autonomous is better for many reasons, like improving learning.
Do you know how to improve the experience even further? Not mocking.
Simple.
Amazing Thumbnail!
You kept my attention from the beginning to the end.
Outstanding! You said that just as though Michael values your opinion.
@@MyOneFiftiethOfADollar You seem to assume much.
Fascinating! Thank you for sharing. It is like having an excellent knowledgeable guide through the land called mathematics (fourth to comments 🙂 )
23:36
23:19 shouldn't it be *n/d* instead of *d/n* ?
No, d divides n.
@@Chris-5318 No, he's right! d | n => d
@@Chris-5318 what did you think I was referring to?
At the timestamp I wrote, Michael writes the fraction d/n. That is likely not even an integer in many cases, and I think it should be n/d.
@@Cloud88Skywalker It seems that you are not familiar with the standard notation that is used in number theory (and combinatorics). He wrote " d | n " that literally means "d divides n". He did not write " d / n " which means "d divided by n".
In the first example where n = 6, the divisors of 6 are 1, 2, 3 and 6 that's written as 1 | 6, 2 | 6, 3 | 6 and 6 | 6, but 4 ∤ 6 and 5 ∤ 6 i.e. 4 does not divide 6 and 5 does not divide 6.
Division is not defined for the integers. E.g., neither 6 / 4 nor 6 / 5 (or their reciprocals) are integers.
The notation Michael used meant that the sum is over all values of d where d is a divisor of n (i.e. d divides n). You should have realised that you were misunderstanding when he wrote f(6) = g(1) + g(2) + g(3) + g(6) at around 3:32. It would make no sense with n / d.
@@Chris-5318 Listen. This is not that difficult. The very first thing I wrote in my first comment is a timestamp to the precise moment Michael writes a FRACTION multiplying *μ(d).*
I know what *d | n* means. I'm not speaking about that. The original statement's right-hand side ends with *μ(d)f(n/d).* That, inside function *f,* is a FRACTION. In the last example of the video (my timestamp), *f* is the identity function, so *f(n/d)* becomes... *n/d* I'd expect. But Michael wrote *d/n.* And that's what I'm talking about.
I prefer the proof involving the Partially ordered sets theory. There re much more examples of POSes then the division one and also arithmetic functions such as zeta and mu which is its inverse
cool theorem
Is there any difference between arithmetic functions and sequences?
A sequence is a function over the domain of the naturals or the integers.
@@Chris-5318 right, and isn't an arithmetic function also a function over the naturals or integers?
@@synaestheziac As I hadn't come across the term "arithmetic function" before, I gave a "definition" that used more familiar terms so that more people could understand what I was saying.
@@Chris-5318 I also hadn’t come across it until Michael used it in this video. But first thought was: isn’t that the same thing as a sequence? I looked it up and found the following answer to my question on stack exchange:
“In some sense there's no difference, but in practice when you call something an arithmetic function as opposed to a sequence you are paying attention to the multiplicative structure of N and the examples you care about will be attuned to that multiplicative structure. Examples include the totient function φ(n), the divisor function d(n), etc. This is particularly clear in the definition of a multiplicative arithmetic function, which is one satisfying
f(mn)=f(m)f(n)
where gcd(m,n)=1.”
Which is basically what I was thinking, so I’m satisfied with that.
@@synaestheziac It seems that an AF should be at least multiplicative or additive (as suggested by Hardy & Wright), whereas a general sequence or general number-theoretic function needn't be either. So I stand by my first response and now add that in general a sequence is NOT required to represent an AF (if you defer to H & W). Obviously an AF may be represented as a sequence.
Wait it’s not a mobius strip on the thumbnail !
@@Kreypossukr how long did you have to “Wait” to notice that?
@@MyOneFiftiethOfADollar I’m not native English so maybe I misused the word wait here, I meant it as an interjection ! I noticed it as soon as I saw the thumbnail
@@Kreypossukr just teasing, was an alert observation. 😀
At about 8:46 he sort of lost me, because what he was saying didn't exactly seem to hold, but what I think he's doing isn't exactly what he's saying (i.e. sum(where: d|m; mu(dp)) ≠ sum(where: d|(m*p); mu(d), as for instance the second sum contains mu(1), where the first doesn't), but instead he's grouping the divisors into separate sums based on what power of p the respective ’d's contain. From there, it mostly seems to make sense, though I had to watch a second time once I understood what he was getting at with the sums.
sum of mu(d) where d are divisors of n = sum of mu(d) where d are divisors of mp^r = sum of mu(dp^r) where d are divisors of m, so where did he get all of the sums with dp, dp^2,...?
Am I the first one here to complain that the thumbnail doesn't actually show a Möbius strip?
I was thinking the same
Why should it?
@@MyOneFiftiethOfADollar Why are you so angry all the time?
@@MyOneFiftiethOfADollar It really is quite astonishing to see someone troll Michael Penn's comments just to insult everyone. My deepest sympathies to anyone who has the displeasure of knowing you.
@@BudgieJane well, because the pictures on it seem to suggest that the surface is not orientable even though it is and because the video already mentions Möbius.
So many claims that a term is "so called". Faintly condescending OR do you doubt name is historically factual/accurate? For example, do you believe that Mobius had nothing to do with creating the famous function that bears his name?
Perhaps it is as simple that tons of math lecturers just think it sounds cool and erudite/informed.
Also the claim that something is "interesting" often means "I don't quite understand it yet".
Morbius?
Possibly the first time I saw this inversion was related to the prime zeta function. It's the Riemann zeta function but only summed over the primes en.wikipedia.org/wiki/Prime_zeta_function. The series for this converges for Real(z)>1. But inversion gives a series that converges faster, and for Real(z)>0 !!! en.wikipedia.org/wiki/Prime_zeta_function Worth another video, with some other properties of the primezeta function?