Bounds on the Gaussian Coefficient

Sam Adriaensen recently had a look at several bounds on Gaussian coefficients (or {q}-binomial coefficients). Here I will summarize his investigation for future reference.

The Gaussian coefficient {\binom{n}{k}_q} is defined by

\displaystyle \binom{n}{k}_q = \prod_{i=1}^k \frac{q^{n-i+1}-1}{q^i-1}

if {0 \leq k \leq n} and {\binom{n}{k}_q = 0} otherwise. Note that {\lim_{q \rightarrow 1} \binom{n}{k}_q = \binom{n}{k}}, so it is indeed a generalization of the binomial coefficient. The Gaussian coefficient counts many things. In my case I care about the fact that it counts the number of subspaces of dimension {k} in a vector spaces of dimension {n} over a field with {q} elements. In my work I often need lower and upper bound on {\binom{n}{k}_q}. As I care about the application for when {q} is a prime power, some of the below is restricted to the case that {q > 1}.

1. Lower Bounds

Lower bounds are easy to come by, so I will only write little. One easily sees that for {0 \leq k \leq n}, we have

\displaystyle q^{k(n-k)} \leq \binom{n}{k}_q.

One can vary this depending on application. For instance, in my PhD thesis (many years ago) I write that for {0 < k < n}, we have

\displaystyle (1 + q^{-1}) q^{k(n-k)} \leq \binom{n}{k}_q.

There I also used for {q=2}, that we have

\displaystyle (2 - \frac{1}{q^{n-k}}) q^{k(n-k)} \leq \binom{n}{k}_q.

If I remember correctly, then my PhD supervisor Klaus Metsch suggested the second inequality. In any case, lower bound like these are easy to prove (you just skip some of the factors in the definition) and they are easy to adjust.

2. Upper Bounds

Upper bounds on the Gaussian coefficients are trickier to come by. Many papers include these. I will only mention those which I know (either from my recent discussion with Sam or for some other reason). In P. M. Neumann and C. E. Praeger, Cyclic matrices over finite fields, J. London Math. Soc. 52(2) (1995), 263-284, Lemma 3.5, implies

Lemma [Neumann, Praeger (1995)]

\displaystyle \binom{n}{k}_q < \frac{q^2}{q^2-q-1} q^{k(n-k)}.

It will turn out that this is usually the best bound. Edit 06/08/2023: Igor Pak used the same argument (Euler’s pentagonal number theorem) for the same bound in his paper I. Pak, When and how n choose k, in Randomization methods in algorithm design, AMS, Providence, RI, 1999, 191-238.

In my PhD thesis, Lemma 2.1, we find

Lemma [Ihringer (2015), Ihringer, Metsch (2018)] For {q \geq 2},

\displaystyle \binom{n}{k}_q \leq \frac{111}{32} q^{k(n-k)}.

For {q \geq 3},

\displaystyle \binom{n}{k}_q \leq 2 q^{k(n-k)}.

For {q \geq 4},

\displaystyle \binom{n}{k}_q \leq (1+2q^{-1}) q^{k(n-k)}.

The bounds for {q>2} also occur in Ihringer-Metsch (2018). These bounds did what I wanted to them to do. Note that {\frac{q^2}{q^2-q-1}} is smaller than {2} for {q \geq 3}, so Neumann-Praeger is better except for {q=2}. In T. Héger and Z. L. Nagy, Short Minimal Codes and Covering Codes via Strong Blocking Sets in Projective Spaces, IEEE Transactions on Information Theory, 68(2) (2022), 881–890 we find in Lemma 2.2

Lemma [Héger, Nagy (2022)] For {q > 2},

\displaystyle \binom{n}{k}_q \leq e^{1/(q-2)} q^{k(n-k)} .

For {q=2},

\displaystyle \binom{n}{k}_q \leq e^{2/3} q^{k(n-k)+1}.

The bound for {q>2} is worse than Neumann-Praeger (maybe double check). The bound for {q=2} is worse than my bound above for {q=2}.

In A. Bishnoi, J. D’haeseleer, D. Gijswijt, A. Potukuchi, Blocking sets, minimal codes and trifferent codes, arXiv:2301.09457v2 [math.CO], 2023 we find in Lemma 2.3

Lemma [BDGP (2023)] For {q \geq 2},

\displaystyle \binom{n}{k}_q \leq \frac{q}{q-1} e^{\frac{q}{(q^2-1)(q-1)}} q^{k(n-k)} .

This is strictly better than Héger-Nagy, but still worse than Neumann-Praeger. Hence, for {q=2}, Ihringer (2015) is the best upper bound which I am aware of. And for {q>2}, it is Neumann-Praeger (1995).

So this is all. If you know any other nice upper or lower bounds, then let me know!

Also note that I left out some bounds for certain special cases (as there are too many like that). And, obviously, there is some recency bias going on. Simply because these upper bounds usually occur as small remarks and it is not easy to look for them.

Edit (04/08/2023): Some minor adjustments in the layout of the formulas.

2 comments

  1. I might be confused and this is not what you care about, but you have an easy bound 1> (1-q)(1-q^2)…(1-q^n) > 1-q-q^2, see e.g. Lemma 2.3.2 in my old paper “When and how n choose k” https://www.math.ucla.edu/~pak/papers/nk13.pdf
    You can get an even better bound
    1-q-q^2+q^5+q^7> (1-q)(1-q^2)…(1-q^n) > 1-q-q^2+q^5+q^7-q^12-q^15
    if you wish. Now straight from the definition of Gaussian coefficients you get a really good bound of the type you want, I think.

    Like

    Reply

    1. [I think that it should be 1/q, not q, everywhere. I also edited the comment below slightly because I wrote it before having enough coffee.]

      Thanks! In Lemma 2.3.2 in your paper you use 1 > (1-1/q)(1-1/q^2) > 1-1/q-1/q^2. Lemma 3.5 in Neumann-Praeger also uses 1 > (1-1/q)(1-1/q^2) > 1-1/q-1/q^2 using the same argument, that is Euler’s pentagonal number theorem. That is clearly the best way of doing it. I will add the reference above.

      For the second part of your comment, I did not include any cases which assume k, n-k > 1.

      Like

      Reply

Leave a comment