The previous post looked at the probability that a random n by n matrix over a finite field of order q is invertible. This works out to be
This function of q and n comes up in other contexts as well and has a name that we will get to shortly.
Pochhammer symbols
Leo August Pochhammer (1841–1920) defined the kth rising power of x by
Rising and falling powers come up naturally in combinatorics, finite difference analogs of calculus, and in the definition of hypergeometric functions.
q-Pochhammer symbols
The q-analog of the Pochhammer symbol is defined as
Like the Pochhammer symbol, the q-Pochhammer symbol also comes up in combinatorics.
In general, q-analogs of various concepts are generalizations that reduce to the original concept in some sort of limit as q goes to 1. The relationship between the q-Pochhammer symbol and the Pochhammer symbol is
For a simpler introduction to q-analogs, see this post on q-factorial and q-binomial coefficients.
Back to our probability problem
The motivation for this post was to give a name to the function that gives probability a random n by n matrix over a finite field of order q is invertible. In the notation above, this function is (1/q; 1/q)n.
There’s a confusing notational coincidence here. The number of elements in a finite field is usually denoted by q. The q in q-analogs such as the q-Pochhammer symbol has absolute value less than 1. It’s a coincidence that they both use the letter q, and the q in our application of q-Pochhammer symbols is the reciprocal of the q representing the order of a finite field.
I mentioned in the previous post that the probability of the matrix being invertible is a decreasing function of n. This probability decreases to a positive limit, varying with the value of q. This limit is (1/q; 1/q)∞. Here the subscript ∞ denotes that we take the limit in (1/q; 1/q)n as n goes to infinity. There’s no problem here because the infinite product converges.
Mathematica and plotting
The q-Pochhammer symbol (a; q)n is implemented in Mathematica as QPochhammer[a, q, n]
and the special case (q; q)∞ is implemented as QPochhammer[q]
. We can use the latter to make the following plot.
Plot[QPochhammer[q], {q, -1, 1}]
Recall that the q in our motivating application is the reciprocal of the q in the q-Pochhhammer symbol. This says for large fields, the limiting probability that an n by n matrix is invertible as n increases is near 1, but that for smaller fields the limiting probability is also smaller. For q = 2, the probability is 0.288788.
Plot[QPochhammer[1/q], {q, 2, 100}, PlotRange -> All]
Related posts