Mixing
Using Mobius inversion to determine coefficients.
Clash Royale CLAN TAG#URR8PPP
up vote
-1
down vote
favorite
Suppose we have a fixed positive integer $n$ and three functions $f:mathbb N longrightarrow mathbb N$ and $g:mathbb Ntimes mathbb Nlongrightarrow mathbb N$ and $a:mathbb Nrightarrow mathbb N$ with the relation:
$$textfor each;kin mathbb N,;f(k)=a(1),g(1,k)+a(2),g(2,k)+cdots+a(n),g(n,k)$$
can we apply Mobius inversion theorem to determine the coefficients $a(i)$ in terms of the functions $f$ and $g$?
I know that over $(mathbb N,leq)$ the Mobius function has a simple expression, that is, $mu(i,i)=1$ and $mu(i-1,i)=-1$ and all the other $mu(j,i)=0$ for $jnot = i$ and for $jnot = i-1$.
but i could not see how to use this invesion in my situation. Thanks for your help!
real-analysis combinatorics mobius-function mobius-inversion
edited Jul 22 at 19:45
Andrés E. Caicedo
63.2k7151235
asked Jul 22 at 15:18
palio
3,95732454
add a comment |Â
up vote
-1
down vote
favorite
Suppose we have a fixed positive integer $n$ and three functions $f:mathbb N longrightarrow mathbb N$ and $g:mathbb Ntimes mathbb Nlongrightarrow mathbb N$ and $a:mathbb Nrightarrow mathbb N$ with the relation:
$$textfor each;kin mathbb N,;f(k)=a(1),g(1,k)+a(2),g(2,k)+cdots+a(n),g(n,k)$$
can we apply Mobius inversion theorem to determine the coefficients $a(i)$ in terms of the functions $f$ and $g$?
I know that over $(mathbb N,leq)$ the Mobius function has a simple expression, that is, $mu(i,i)=1$ and $mu(i-1,i)=-1$ and all the other $mu(j,i)=0$ for $jnot = i$ and for $jnot = i-1$.
but i could not see how to use this invesion in my situation. Thanks for your help!
real-analysis combinatorics mobius-function mobius-inversion
edited Jul 22 at 19:45
Andrés E. Caicedo
63.2k7151235
asked Jul 22 at 15:18
palio
3,95732454
I am unfamiliar with Mobius inversion theorem, but I see some inconsistencies in your problem statement. Based on your formula for $f$, the domain of $g$ only needs to be $1, 2, ldots, ntimes mathbb N$. Is there any reason you want $g$ to be defined on $mathbb Ntimes mathbb N$?
– BindersFull
Jul 22 at 15:54
Because I want the formula to hold for each fixed $nin mathbb N$. But ok there is no problem in taking the domain you specified for $g$.
– palio
Jul 22 at 20:32
With no further assumptions on $f$, $g$, you will be unable to determine the $a(i)$'s for each $n$. See the answer I've written below where I show that the $a(i)$'s can not even be determined in the case $n = 2$.
– BindersFull
Jul 22 at 21:14
add a comment |Â
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
Suppose we have a fixed positive integer $n$ and three functions $f:mathbb N longrightarrow mathbb N$ and $g:mathbb Ntimes mathbb Nlongrightarrow mathbb N$ and $a:mathbb Nrightarrow mathbb N$ with the relation:
$$textfor each;kin mathbb N,;f(k)=a(1),g(1,k)+a(2),g(2,k)+cdots+a(n),g(n,k)$$
can we apply Mobius inversion theorem to determine the coefficients $a(i)$ in terms of the functions $f$ and $g$?
I know that over $(mathbb N,leq)$ the Mobius function has a simple expression, that is, $mu(i,i)=1$ and $mu(i-1,i)=-1$ and all the other $mu(j,i)=0$ for $jnot = i$ and for $jnot = i-1$.
but i could not see how to use this invesion in my situation. Thanks for your help!
real-analysis combinatorics mobius-function mobius-inversion
edited Jul 22 at 19:45
Andrés E. Caicedo
63.2k7151235
asked Jul 22 at 15:18
palio
3,95732454
Suppose we have a fixed positive integer $n$ and three functions $f:mathbb N longrightarrow mathbb N$ and $g:mathbb Ntimes mathbb Nlongrightarrow mathbb N$ and $a:mathbb Nrightarrow mathbb N$ with the relation:
$$textfor each;kin mathbb N,;f(k)=a(1),g(1,k)+a(2),g(2,k)+cdots+a(n),g(n,k)$$
can we apply Mobius inversion theorem to determine the coefficients $a(i)$ in terms of the functions $f$ and $g$?
I know that over $(mathbb N,leq)$ the Mobius function has a simple expression, that is, $mu(i,i)=1$ and $mu(i-1,i)=-1$ and all the other $mu(j,i)=0$ for $jnot = i$ and for $jnot = i-1$.
but i could not see how to use this invesion in my situation. Thanks for your help!
real-analysis combinatorics mobius-function mobius-inversion
edited Jul 22 at 19:45
Andrés E. Caicedo
63.2k7151235
asked Jul 22 at 15:18
palio
3,95732454
edited Jul 22 at 19:45
Andrés E. Caicedo
63.2k7151235
edited Jul 22 at 19:45
Andrés E. Caicedo
63.2k7151235
edited Jul 22 at 19:45
Andrés E. Caicedo
63.2k7151235
63.2k7151235
asked Jul 22 at 15:18
palio
3,95732454
asked Jul 22 at 15:18
palio
3,95732454
asked Jul 22 at 15:18
palio
3,95732454
3,95732454
I am unfamiliar with Mobius inversion theorem, but I see some inconsistencies in your problem statement. Based on your formula for $f$, the domain of $g$ only needs to be $1, 2, ldots, ntimes mathbb N$. Is there any reason you want $g$ to be defined on $mathbb Ntimes mathbb N$?
– BindersFull
Jul 22 at 15:54
Because I want the formula to hold for each fixed $nin mathbb N$. But ok there is no problem in taking the domain you specified for $g$.
– palio
Jul 22 at 20:32
With no further assumptions on $f$, $g$, you will be unable to determine the $a(i)$'s for each $n$. See the answer I've written below where I show that the $a(i)$'s can not even be determined in the case $n = 2$.
– BindersFull
Jul 22 at 21:14
add a comment |Â
I am unfamiliar with Mobius inversion theorem, but I see some inconsistencies in your problem statement. Based on your formula for $f$, the domain of $g$ only needs to be $1, 2, ldots, ntimes mathbb N$. Is there any reason you want $g$ to be defined on $mathbb Ntimes mathbb N$?
– BindersFull
Jul 22 at 15:54
Because I want the formula to hold for each fixed $nin mathbb N$. But ok there is no problem in taking the domain you specified for $g$.
– palio
Jul 22 at 20:32
With no further assumptions on $f$, $g$, you will be unable to determine the $a(i)$'s for each $n$. See the answer I've written below where I show that the $a(i)$'s can not even be determined in the case $n = 2$.
– BindersFull
Jul 22 at 21:14
I am unfamiliar with Mobius inversion theorem, but I see some inconsistencies in your problem statement. Based on your formula for $f$, the domain of $g$ only needs to be $1, 2, ldots, ntimes mathbb N$. Is there any reason you want $g$ to be defined on $mathbb Ntimes mathbb N$?
– BindersFull
Jul 22 at 15:54
I am unfamiliar with Mobius inversion theorem, but I see some inconsistencies in your problem statement. Based on your formula for $f$, the domain of $g$ only needs to be $1, 2, ldots, ntimes mathbb N$. Is there any reason you want $g$ to be defined on $mathbb Ntimes mathbb N$?
– BindersFull
Jul 22 at 15:54
Because I want the formula to hold for each fixed $nin mathbb N$. But ok there is no problem in taking the domain you specified for $g$.
– palio
Jul 22 at 20:32
Because I want the formula to hold for each fixed $nin mathbb N$. But ok there is no problem in taking the domain you specified for $g$.
– palio
Jul 22 at 20:32
With no further assumptions on $f$, $g$, you will be unable to determine the $a(i)$'s for each $n$. See the answer I've written below where I show that the $a(i)$'s can not even be determined in the case $n = 2$.
– BindersFull
Jul 22 at 21:14
With no further assumptions on $f$, $g$, you will be unable to determine the $a(i)$'s for each $n$. See the answer I've written below where I show that the $a(i)$'s can not even be determined in the case $n = 2$.
– BindersFull
Jul 22 at 21:14
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
In general, you can not determine each $a(i)$ if $f$ and $g$ are known. For example, let $n = 2$ and let $g(i,j)= 1$ for all $ i = 1, 2$ and all $j = 1, 2, ldots$. Then for all $k$ we have $f(k) = a(1) + a(2)$ (in particular $f$ must be constant). If we knew, for example, that $f(k) = 3$ for all $k$ then we could not determine whether $[a(1), a(2)] = [1,2]$ or $[a(1), a(2)] = [2,1]$.
answered Jul 22 at 15:50
BindersFull
498110
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
In general, you can not determine each $a(i)$ if $f$ and $g$ are known. For example, let $n = 2$ and let $g(i,j)= 1$ for all $ i = 1, 2$ and all $j = 1, 2, ldots$. Then for all $k$ we have $f(k) = a(1) + a(2)$ (in particular $f$ must be constant). If we knew, for example, that $f(k) = 3$ for all $k$ then we could not determine whether $[a(1), a(2)] = [1,2]$ or $[a(1), a(2)] = [2,1]$.
answered Jul 22 at 15:50
BindersFull
498110
add a comment |Â
up vote
0
down vote
In general, you can not determine each $a(i)$ if $f$ and $g$ are known. For example, let $n = 2$ and let $g(i,j)= 1$ for all $ i = 1, 2$ and all $j = 1, 2, ldots$. Then for all $k$ we have $f(k) = a(1) + a(2)$ (in particular $f$ must be constant). If we knew, for example, that $f(k) = 3$ for all $k$ then we could not determine whether $[a(1), a(2)] = [1,2]$ or $[a(1), a(2)] = [2,1]$.
answered Jul 22 at 15:50
BindersFull
498110
add a comment |Â
up vote
0
down vote
up vote
0
down vote
In general, you can not determine each $a(i)$ if $f$ and $g$ are known. For example, let $n = 2$ and let $g(i,j)= 1$ for all $ i = 1, 2$ and all $j = 1, 2, ldots$. Then for all $k$ we have $f(k) = a(1) + a(2)$ (in particular $f$ must be constant). If we knew, for example, that $f(k) = 3$ for all $k$ then we could not determine whether $[a(1), a(2)] = [1,2]$ or $[a(1), a(2)] = [2,1]$.
answered Jul 22 at 15:50
BindersFull
498110
In general, you can not determine each $a(i)$ if $f$ and $g$ are known. For example, let $n = 2$ and let $g(i,j)= 1$ for all $ i = 1, 2$ and all $j = 1, 2, ldots$. Then for all $k$ we have $f(k) = a(1) + a(2)$ (in particular $f$ must be constant). If we knew, for example, that $f(k) = 3$ for all $k$ then we could not determine whether $[a(1), a(2)] = [1,2]$ or $[a(1), a(2)] = [2,1]$.
answered Jul 22 at 15:50
BindersFull
498110
answered Jul 22 at 15:50
BindersFull
498110
answered Jul 22 at 15:50
BindersFull
498110
answered Jul 22 at 15:50
BindersFull
498110
498110
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859495%2fusing-mobius-inversion-to-determine-coefficients%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I am unfamiliar with Mobius inversion theorem, but I see some inconsistencies in your problem statement. Based on your formula for $f$, the domain of $g$ only needs to be $1, 2, ldots, ntimes mathbb N$. Is there any reason you want $g$ to be defined on $mathbb Ntimes mathbb N$?
– BindersFull
Jul 22 at 15:54
Because I want the formula to hold for each fixed $nin mathbb N$. But ok there is no problem in taking the domain you specified for $g$.
– palio
Jul 22 at 20:32
With no further assumptions on $f$, $g$, you will be unable to determine the $a(i)$'s for each $n$. See the answer I've written below where I show that the $a(i)$'s can not even be determined in the case $n = 2$.
– BindersFull
Jul 22 at 21:14