# Number of rational functions with low-degree numerator and denominator

## The problem

Let $$\mathbb F$$ be a finite field and $$d < | \mathbb F |$$. (Can think of the setting $$d \approx |\mathbb F|/2$$)

Let $$A = \left\{ \frac{p(x)}{q(x)} \ \colon \ p,q \in \mathbb F[x] \text{ and } \mathrm{deg}(q), \mathrm{deg}(p) \leq d \right\} \setminus \left\{p(x) \in \mathbb F \colon \mathrm{deg}(p) \leq d\right\}$$ That is, $$A$$ is the set of all univariate rational functions with both numerator and denominator polynomials of degree at most $$d$$, who are not low-degree themselves. Note that the degree of $$q$$ need not be smaller than that of $$p$$; for example, $$1/x$$ is an interesting function to us.

What is the cardinality of $$|A|$$?

## A definitional issue

Since I'm only interested in counting, I'll choose a special symbol $$* \notin \mathbb F$$ and let $$\frac{p(x)}{q(x)} = *$$ whenever $$q(x) = 0$$. If there is a more elegant or correct suggestion for dealing with $$q(x)=0$$ I'm happy to consider it.

• I might declare that $q(x)$ must be monic and of degree at least $1$, leaving $Q^{d+1}$ choices for $p$ and $Q+Q^2+\cdots+Q^{d-1}+Q^d$ choices for $q$, $Q=|\Bbb{F}|$. Still needing to calculate the pairs $(p,q)$ such that $\gcd(p,q)=1$. Not pleasant, but probably somebody has looked at it :-) – Jyrki Lahtonen Sep 17 '19 at 3:28
• What is the role of the subset $L$? – Jyrki Lahtonen Sep 17 '19 at 3:29
• @JyrkiLahtonen : Apologies, it is a remnant from a previous formulation (an attempt to circumvent the definitional issue). Fixed! – 8l2s Sep 17 '19 at 19:32

## 1 Answer

Let $$M_d$$ be the set of all monic polynomials over $$\mathbb{F}$$ of degree (exactly) $$d$$, and let $$M_{\leqslant d}:=\bigcup_{k=0}^{d}M_d,\qquad G_d:=\{(p,q)\in M_{\leqslant d}^2 : \gcd(p,q)=1\}.$$ As any pair $$(p,q)\in M_{\leqslant d}^2$$ is uniquely represented by $$(p'g,q'g)$$, where $$g=\gcd(p,q)$$ is a monic polynomial, and $$\gcd(p',q')=1$$, we have $$|M_{\leqslant d}|^2=\sum\limits_{k=0}^{d}|M_k|\cdot|G_{d-k}|.$$ Denoting $$K:=|\mathbb{F}|$$, we compute $$|M_d|=K^d$$, $$|M_{\leqslant d}|=\frac{K^{d+1}-1}{K-1},\quad|G_d|=|M_{\leqslant d}|^2- K|M_{\leqslant d-1}|^2,\quad|G_0|=1.$$ Returning to your $$A$$, we can make $$p$$ and $$q$$ monic by carrying out leading coefficients, thus $$|A|=(K-1)(|G_d|-|M_{\leqslant d}|)=K^{d+1}(K^d-1).$$