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.

  • 2
    $\begingroup$ 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 :-) $\endgroup$ – Jyrki Lahtonen Sep 17 '19 at 3:28
  • $\begingroup$ What is the role of the subset $L$? $\endgroup$ – Jyrki Lahtonen Sep 17 '19 at 3:29
  • $\begingroup$ @JyrkiLahtonen : Apologies, it is a remnant from a previous formulation (an attempt to circumvent the definitional issue). Fixed! $\endgroup$ – 8l2s Sep 17 '19 at 19:32

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).$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.