Mixing
A divisibility of q-binomial coefficients combinatorially
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let a and b be coprime positive integers. Then the number a+b divides the binomial coefficient $a+b choose a$. I know how to prove this combinatorially - for example after choosing an ordered set of a+b elements, there is a free action of a cyclic group of order a+b on the set of a-element subsets (and you can even choose a distinguished representative of each orbit if you so wish).
Passing to q-binomial coefficients, the quantum number $[a+b]_q$ divides the q-binomial coefficient $beginbmatrixa+b\ aendbmatrix_q$.
My question today is whether this divisibility fact has a combinatorial proof or interpretation.
I remark that one can also ask whether or not
$$frac1[a+b]_qbeginbmatrixa+b\ aendbmatrix_qin mathbbN[q],$$
which would likely follow from any such combinatorial argument. When a+b=p is prime, I know this is the case by constructing algebraically a free $mathbbF_p[d]/(d^p)$-module structure on the cohomology of the Grassmannian. I haven't done enough numerical experiments for non-prime values of a+b to be confident that this polynomial has non-negartive coefficients in general.
co.combinatorics binomial-coefficients q-analogs combinatorial-proofs
asked 1 hour ago
Peter McNamara
5,2862453
add a comment |Â
up vote
2
down vote
favorite
Let a and b be coprime positive integers. Then the number a+b divides the binomial coefficient $a+b choose a$. I know how to prove this combinatorially - for example after choosing an ordered set of a+b elements, there is a free action of a cyclic group of order a+b on the set of a-element subsets (and you can even choose a distinguished representative of each orbit if you so wish).
Passing to q-binomial coefficients, the quantum number $[a+b]_q$ divides the q-binomial coefficient $beginbmatrixa+b\ aendbmatrix_q$.
My question today is whether this divisibility fact has a combinatorial proof or interpretation.
I remark that one can also ask whether or not
$$frac1[a+b]_qbeginbmatrixa+b\ aendbmatrix_qin mathbbN[q],$$
which would likely follow from any such combinatorial argument. When a+b=p is prime, I know this is the case by constructing algebraically a free $mathbbF_p[d]/(d^p)$-module structure on the cohomology of the Grassmannian. I haven't done enough numerical experiments for non-prime values of a+b to be confident that this polynomial has non-negartive coefficients in general.
co.combinatorics binomial-coefficients q-analogs combinatorial-proofs
asked 1 hour ago
Peter McNamara
5,2862453
When $a,b$ are not necessarily coprime, I would look at $frac1[(a+b)/gcd(a,b)]_qbeginbmatrixa+b\ aendbmatrix_q$. The usual proofs of ($q$-)integrality work for this more general form.
– Ofir Gorodetsky
39 mins ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let a and b be coprime positive integers. Then the number a+b divides the binomial coefficient $a+b choose a$. I know how to prove this combinatorially - for example after choosing an ordered set of a+b elements, there is a free action of a cyclic group of order a+b on the set of a-element subsets (and you can even choose a distinguished representative of each orbit if you so wish).
Passing to q-binomial coefficients, the quantum number $[a+b]_q$ divides the q-binomial coefficient $beginbmatrixa+b\ aendbmatrix_q$.
My question today is whether this divisibility fact has a combinatorial proof or interpretation.
I remark that one can also ask whether or not
$$frac1[a+b]_qbeginbmatrixa+b\ aendbmatrix_qin mathbbN[q],$$
which would likely follow from any such combinatorial argument. When a+b=p is prime, I know this is the case by constructing algebraically a free $mathbbF_p[d]/(d^p)$-module structure on the cohomology of the Grassmannian. I haven't done enough numerical experiments for non-prime values of a+b to be confident that this polynomial has non-negartive coefficients in general.
co.combinatorics binomial-coefficients q-analogs combinatorial-proofs
asked 1 hour ago
Peter McNamara
5,2862453
Let a and b be coprime positive integers. Then the number a+b divides the binomial coefficient $a+b choose a$. I know how to prove this combinatorially - for example after choosing an ordered set of a+b elements, there is a free action of a cyclic group of order a+b on the set of a-element subsets (and you can even choose a distinguished representative of each orbit if you so wish).
Passing to q-binomial coefficients, the quantum number $[a+b]_q$ divides the q-binomial coefficient $beginbmatrixa+b\ aendbmatrix_q$.
My question today is whether this divisibility fact has a combinatorial proof or interpretation.
I remark that one can also ask whether or not
$$frac1[a+b]_qbeginbmatrixa+b\ aendbmatrix_qin mathbbN[q],$$
which would likely follow from any such combinatorial argument. When a+b=p is prime, I know this is the case by constructing algebraically a free $mathbbF_p[d]/(d^p)$-module structure on the cohomology of the Grassmannian. I haven't done enough numerical experiments for non-prime values of a+b to be confident that this polynomial has non-negartive coefficients in general.
co.combinatorics binomial-coefficients q-analogs combinatorial-proofs
co.combinatorics binomial-coefficients q-analogs combinatorial-proofs
asked 1 hour ago
Peter McNamara
5,2862453
asked 1 hour ago
Peter McNamara
5,2862453
asked 1 hour ago
Peter McNamara
5,2862453
asked 1 hour ago
Peter McNamara
5,2862453
asked 1 hour ago
Peter McNamara
5,2862453
5,2862453
When $a,b$ are not necessarily coprime, I would look at $frac1[(a+b)/gcd(a,b)]_qbeginbmatrixa+b\ aendbmatrix_q$. The usual proofs of ($q$-)integrality work for this more general form.
– Ofir Gorodetsky
39 mins ago
add a comment |Â
When $a,b$ are not necessarily coprime, I would look at $frac1[(a+b)/gcd(a,b)]_qbeginbmatrixa+b\ aendbmatrix_q$. The usual proofs of ($q$-)integrality work for this more general form.
– Ofir Gorodetsky
39 mins ago
When $a,b$ are not necessarily coprime, I would look at $frac1[(a+b)/gcd(a,b)]_qbeginbmatrixa+b\ aendbmatrix_q$. The usual proofs of ($q$-)integrality work for this more general form.
– Ofir Gorodetsky
39 mins ago
When $a,b$ are not necessarily coprime, I would look at $frac1[(a+b)/gcd(a,b)]_qbeginbmatrixa+b\ aendbmatrix_q$. The usual proofs of ($q$-)integrality work for this more general form.
– Ofir Gorodetsky
39 mins ago
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
2
down vote
A proof of nonnegativity appears in https://arxiv.org/pdf/0912.1578.pdf. The number $frac1a+ba+bchoose a$ is called a rational Catalan number by
Drew Armstrong. See for instance http://www.math.miami.edu/~armstrong/Talks/RCC_AIM.pdf. The $q$-analogue appears on page 200. I don't know whether a combinatorial interpretation of the coefficients is known.
answered 52 mins ago
Richard Stanley
27.9k8112183
add a comment |Â
up vote
1
down vote
This divisibility can be deduced from a $q$-analogue of Lucas's Theorem, which enjoys a group-action proof, see Theorem 2.2 and its proof in this elegant paper paper of Sagan.
The $q$-Lucas Theorem states that
$$beginbmatrixn\ kendbmatrix_q equiv binomn_1k_2beginbmatrixn_0\ k_0endbmatrix_q bmod phi_d(q),$$
where: $n=n_1d +n_0$, $k=k_1 d + k_0$, $0 le k_0, n_0 < d$, and $phi_d$ is the $d$-th cyclotomic polynomial. Applying the theorem with $n=a+b$, $k=a$ and $d$ an arbitrary divisor of $n$ greater than $1$, the coprimality condition ensures that $k_0 neq 0$ while $n_0=0$, so that we obtain
$$beginbmatrixa+b \ a endbmatrix_q equiv 0 bmod phi_d(q)$$
for all $d mid a+b$ ($d >1$). Since $ phi_q(d) _d mid a+b,, d>1$ are distinct, monic polynomials whose product is $[a+b]_q$, it follows that
$$beginbmatrixa+b \ a endbmatrix_q equiv 0 bmod [a+b]_q.$$
The only non-combinatorial ingredient is the fact that we deal with each $d$ separately. It is interesting to see if there is a way around it, by modifying Sagan's proof. Sagan's proof uses the representation
$$beginbmatrixn \ k endbmatrix_q = sum_w in W_n,k q^textinv(w),$$
where $W_n,k$ is the set of binary strings of length $n$ and $k$ zeros, and $textinv$ counts inversions.
answered 48 mins ago
Ofir Gorodetsky
5,30712136
add a comment |Â
up vote
1
down vote
Assume $q$ is a prime power. Then there is a straightforward combinatorial interpretation.
Consider the group action of $mathbb F_q^a+b^times / mathbb F_q^times$ on the space of $a$-dimensional subspaces of $mathbb F_q^a+b$, viewed as an $a+b$-dimensional vector space over $mathbb F_q$. We have $| mathbb F_q^a+b^times / mathbb F_q^times| = frac q^ a+b-1q-1 = [a+b]_q$ and the cardinality of the space of $a$-dimensional subspaces of $mathbb F_q^a+b$ is $a+b choose a_q$. To show the divisibility, it suffices to show that this action is free. If any element of $mathbb F_q^a+b$ fixes a subspace, by linearity the field it generates fixes that subspace, so the dimension of the subspace is divisible by the degree of the field it generates, which divides $a+b$.
This shows the ratio is a rational function in q which takes integer values on prime powers, which I believe some number theory shows is a polynomial in q that takes integer values on prime powers, which unfortunately is not an integral polynomial in q.
answered 20 mins ago
Will Sawin
65.2k6131273
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
A proof of nonnegativity appears in https://arxiv.org/pdf/0912.1578.pdf. The number $frac1a+ba+bchoose a$ is called a rational Catalan number by
Drew Armstrong. See for instance http://www.math.miami.edu/~armstrong/Talks/RCC_AIM.pdf. The $q$-analogue appears on page 200. I don't know whether a combinatorial interpretation of the coefficients is known.
answered 52 mins ago
Richard Stanley
27.9k8112183
add a comment |Â
up vote
2
down vote
A proof of nonnegativity appears in https://arxiv.org/pdf/0912.1578.pdf. The number $frac1a+ba+bchoose a$ is called a rational Catalan number by
Drew Armstrong. See for instance http://www.math.miami.edu/~armstrong/Talks/RCC_AIM.pdf. The $q$-analogue appears on page 200. I don't know whether a combinatorial interpretation of the coefficients is known.
answered 52 mins ago
Richard Stanley
27.9k8112183
add a comment |Â
up vote
2
down vote
up vote
2
down vote
A proof of nonnegativity appears in https://arxiv.org/pdf/0912.1578.pdf. The number $frac1a+ba+bchoose a$ is called a rational Catalan number by
Drew Armstrong. See for instance http://www.math.miami.edu/~armstrong/Talks/RCC_AIM.pdf. The $q$-analogue appears on page 200. I don't know whether a combinatorial interpretation of the coefficients is known.
answered 52 mins ago
Richard Stanley
27.9k8112183
A proof of nonnegativity appears in https://arxiv.org/pdf/0912.1578.pdf. The number $frac1a+ba+bchoose a$ is called a rational Catalan number by
Drew Armstrong. See for instance http://www.math.miami.edu/~armstrong/Talks/RCC_AIM.pdf. The $q$-analogue appears on page 200. I don't know whether a combinatorial interpretation of the coefficients is known.
answered 52 mins ago
Richard Stanley
27.9k8112183
answered 52 mins ago
Richard Stanley
27.9k8112183
answered 52 mins ago
Richard Stanley
27.9k8112183
answered 52 mins ago
Richard Stanley
27.9k8112183
27.9k8112183
add a comment |Â
add a comment |Â
up vote
1
down vote
This divisibility can be deduced from a $q$-analogue of Lucas's Theorem, which enjoys a group-action proof, see Theorem 2.2 and its proof in this elegant paper paper of Sagan.
The $q$-Lucas Theorem states that
$$beginbmatrixn\ kendbmatrix_q equiv binomn_1k_2beginbmatrixn_0\ k_0endbmatrix_q bmod phi_d(q),$$
where: $n=n_1d +n_0$, $k=k_1 d + k_0$, $0 le k_0, n_0 < d$, and $phi_d$ is the $d$-th cyclotomic polynomial. Applying the theorem with $n=a+b$, $k=a$ and $d$ an arbitrary divisor of $n$ greater than $1$, the coprimality condition ensures that $k_0 neq 0$ while $n_0=0$, so that we obtain
$$beginbmatrixa+b \ a endbmatrix_q equiv 0 bmod phi_d(q)$$
for all $d mid a+b$ ($d >1$). Since $ phi_q(d) _d mid a+b,, d>1$ are distinct, monic polynomials whose product is $[a+b]_q$, it follows that
$$beginbmatrixa+b \ a endbmatrix_q equiv 0 bmod [a+b]_q.$$
The only non-combinatorial ingredient is the fact that we deal with each $d$ separately. It is interesting to see if there is a way around it, by modifying Sagan's proof. Sagan's proof uses the representation
$$beginbmatrixn \ k endbmatrix_q = sum_w in W_n,k q^textinv(w),$$
where $W_n,k$ is the set of binary strings of length $n$ and $k$ zeros, and $textinv$ counts inversions.
answered 48 mins ago
Ofir Gorodetsky
5,30712136
add a comment |Â
up vote
1
down vote
This divisibility can be deduced from a $q$-analogue of Lucas's Theorem, which enjoys a group-action proof, see Theorem 2.2 and its proof in this elegant paper paper of Sagan.
The $q$-Lucas Theorem states that
$$beginbmatrixn\ kendbmatrix_q equiv binomn_1k_2beginbmatrixn_0\ k_0endbmatrix_q bmod phi_d(q),$$
where: $n=n_1d +n_0$, $k=k_1 d + k_0$, $0 le k_0, n_0 < d$, and $phi_d$ is the $d$-th cyclotomic polynomial. Applying the theorem with $n=a+b$, $k=a$ and $d$ an arbitrary divisor of $n$ greater than $1$, the coprimality condition ensures that $k_0 neq 0$ while $n_0=0$, so that we obtain
$$beginbmatrixa+b \ a endbmatrix_q equiv 0 bmod phi_d(q)$$
for all $d mid a+b$ ($d >1$). Since $ phi_q(d) _d mid a+b,, d>1$ are distinct, monic polynomials whose product is $[a+b]_q$, it follows that
$$beginbmatrixa+b \ a endbmatrix_q equiv 0 bmod [a+b]_q.$$
The only non-combinatorial ingredient is the fact that we deal with each $d$ separately. It is interesting to see if there is a way around it, by modifying Sagan's proof. Sagan's proof uses the representation
$$beginbmatrixn \ k endbmatrix_q = sum_w in W_n,k q^textinv(w),$$
where $W_n,k$ is the set of binary strings of length $n$ and $k$ zeros, and $textinv$ counts inversions.
answered 48 mins ago
Ofir Gorodetsky
5,30712136
add a comment |Â
up vote
1
down vote
up vote
1
down vote
This divisibility can be deduced from a $q$-analogue of Lucas's Theorem, which enjoys a group-action proof, see Theorem 2.2 and its proof in this elegant paper paper of Sagan.
The $q$-Lucas Theorem states that
$$beginbmatrixn\ kendbmatrix_q equiv binomn_1k_2beginbmatrixn_0\ k_0endbmatrix_q bmod phi_d(q),$$
where: $n=n_1d +n_0$, $k=k_1 d + k_0$, $0 le k_0, n_0 < d$, and $phi_d$ is the $d$-th cyclotomic polynomial. Applying the theorem with $n=a+b$, $k=a$ and $d$ an arbitrary divisor of $n$ greater than $1$, the coprimality condition ensures that $k_0 neq 0$ while $n_0=0$, so that we obtain
$$beginbmatrixa+b \ a endbmatrix_q equiv 0 bmod phi_d(q)$$
for all $d mid a+b$ ($d >1$). Since $ phi_q(d) _d mid a+b,, d>1$ are distinct, monic polynomials whose product is $[a+b]_q$, it follows that
$$beginbmatrixa+b \ a endbmatrix_q equiv 0 bmod [a+b]_q.$$
The only non-combinatorial ingredient is the fact that we deal with each $d$ separately. It is interesting to see if there is a way around it, by modifying Sagan's proof. Sagan's proof uses the representation
$$beginbmatrixn \ k endbmatrix_q = sum_w in W_n,k q^textinv(w),$$
where $W_n,k$ is the set of binary strings of length $n$ and $k$ zeros, and $textinv$ counts inversions.
answered 48 mins ago
Ofir Gorodetsky
5,30712136
This divisibility can be deduced from a $q$-analogue of Lucas's Theorem, which enjoys a group-action proof, see Theorem 2.2 and its proof in this elegant paper paper of Sagan.
The $q$-Lucas Theorem states that
$$beginbmatrixn\ kendbmatrix_q equiv binomn_1k_2beginbmatrixn_0\ k_0endbmatrix_q bmod phi_d(q),$$
where: $n=n_1d +n_0$, $k=k_1 d + k_0$, $0 le k_0, n_0 < d$, and $phi_d$ is the $d$-th cyclotomic polynomial. Applying the theorem with $n=a+b$, $k=a$ and $d$ an arbitrary divisor of $n$ greater than $1$, the coprimality condition ensures that $k_0 neq 0$ while $n_0=0$, so that we obtain
$$beginbmatrixa+b \ a endbmatrix_q equiv 0 bmod phi_d(q)$$
for all $d mid a+b$ ($d >1$). Since $ phi_q(d) _d mid a+b,, d>1$ are distinct, monic polynomials whose product is $[a+b]_q$, it follows that
$$beginbmatrixa+b \ a endbmatrix_q equiv 0 bmod [a+b]_q.$$
The only non-combinatorial ingredient is the fact that we deal with each $d$ separately. It is interesting to see if there is a way around it, by modifying Sagan's proof. Sagan's proof uses the representation
$$beginbmatrixn \ k endbmatrix_q = sum_w in W_n,k q^textinv(w),$$
where $W_n,k$ is the set of binary strings of length $n$ and $k$ zeros, and $textinv$ counts inversions.
answered 48 mins ago
Ofir Gorodetsky
5,30712136
edited 25 mins ago
answered 48 mins ago
Ofir Gorodetsky
5,30712136
answered 48 mins ago
Ofir Gorodetsky
5,30712136
answered 48 mins ago
Ofir Gorodetsky
5,30712136
5,30712136
add a comment |Â
add a comment |Â
up vote
1
down vote
Assume $q$ is a prime power. Then there is a straightforward combinatorial interpretation.
Consider the group action of $mathbb F_q^a+b^times / mathbb F_q^times$ on the space of $a$-dimensional subspaces of $mathbb F_q^a+b$, viewed as an $a+b$-dimensional vector space over $mathbb F_q$. We have $| mathbb F_q^a+b^times / mathbb F_q^times| = frac q^ a+b-1q-1 = [a+b]_q$ and the cardinality of the space of $a$-dimensional subspaces of $mathbb F_q^a+b$ is $a+b choose a_q$. To show the divisibility, it suffices to show that this action is free. If any element of $mathbb F_q^a+b$ fixes a subspace, by linearity the field it generates fixes that subspace, so the dimension of the subspace is divisible by the degree of the field it generates, which divides $a+b$.
This shows the ratio is a rational function in q which takes integer values on prime powers, which I believe some number theory shows is a polynomial in q that takes integer values on prime powers, which unfortunately is not an integral polynomial in q.
answered 20 mins ago
Will Sawin
65.2k6131273
add a comment |Â
up vote
1
down vote
Assume $q$ is a prime power. Then there is a straightforward combinatorial interpretation.
Consider the group action of $mathbb F_q^a+b^times / mathbb F_q^times$ on the space of $a$-dimensional subspaces of $mathbb F_q^a+b$, viewed as an $a+b$-dimensional vector space over $mathbb F_q$. We have $| mathbb F_q^a+b^times / mathbb F_q^times| = frac q^ a+b-1q-1 = [a+b]_q$ and the cardinality of the space of $a$-dimensional subspaces of $mathbb F_q^a+b$ is $a+b choose a_q$. To show the divisibility, it suffices to show that this action is free. If any element of $mathbb F_q^a+b$ fixes a subspace, by linearity the field it generates fixes that subspace, so the dimension of the subspace is divisible by the degree of the field it generates, which divides $a+b$.
This shows the ratio is a rational function in q which takes integer values on prime powers, which I believe some number theory shows is a polynomial in q that takes integer values on prime powers, which unfortunately is not an integral polynomial in q.
answered 20 mins ago
Will Sawin
65.2k6131273
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Assume $q$ is a prime power. Then there is a straightforward combinatorial interpretation.
Consider the group action of $mathbb F_q^a+b^times / mathbb F_q^times$ on the space of $a$-dimensional subspaces of $mathbb F_q^a+b$, viewed as an $a+b$-dimensional vector space over $mathbb F_q$. We have $| mathbb F_q^a+b^times / mathbb F_q^times| = frac q^ a+b-1q-1 = [a+b]_q$ and the cardinality of the space of $a$-dimensional subspaces of $mathbb F_q^a+b$ is $a+b choose a_q$. To show the divisibility, it suffices to show that this action is free. If any element of $mathbb F_q^a+b$ fixes a subspace, by linearity the field it generates fixes that subspace, so the dimension of the subspace is divisible by the degree of the field it generates, which divides $a+b$.
This shows the ratio is a rational function in q which takes integer values on prime powers, which I believe some number theory shows is a polynomial in q that takes integer values on prime powers, which unfortunately is not an integral polynomial in q.
answered 20 mins ago
Will Sawin
65.2k6131273
Assume $q$ is a prime power. Then there is a straightforward combinatorial interpretation.
Consider the group action of $mathbb F_q^a+b^times / mathbb F_q^times$ on the space of $a$-dimensional subspaces of $mathbb F_q^a+b$, viewed as an $a+b$-dimensional vector space over $mathbb F_q$. We have $| mathbb F_q^a+b^times / mathbb F_q^times| = frac q^ a+b-1q-1 = [a+b]_q$ and the cardinality of the space of $a$-dimensional subspaces of $mathbb F_q^a+b$ is $a+b choose a_q$. To show the divisibility, it suffices to show that this action is free. If any element of $mathbb F_q^a+b$ fixes a subspace, by linearity the field it generates fixes that subspace, so the dimension of the subspace is divisible by the degree of the field it generates, which divides $a+b$.
This shows the ratio is a rational function in q which takes integer values on prime powers, which I believe some number theory shows is a polynomial in q that takes integer values on prime powers, which unfortunately is not an integral polynomial in q.
answered 20 mins ago
Will Sawin
65.2k6131273
answered 20 mins ago
Will Sawin
65.2k6131273
answered 20 mins ago
Will Sawin
65.2k6131273
answered 20 mins ago
Will Sawin
65.2k6131273
65.2k6131273
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%2fmathoverflow.net%2fquestions%2f313551%2fa-divisibility-of-q-binomial-coefficients-combinatorially%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
When $a,b$ are not necessarily coprime, I would look at $frac1[(a+b)/gcd(a,b)]_qbeginbmatrixa+b\ aendbmatrix_q$. The usual proofs of ($q$-)integrality work for this more general form.
– Ofir Gorodetsky
39 mins ago