Let $A = {\mathbb F}\_2[X]$, though the following can be adapted to $p \neq 2$ too. Order the elements of $A$ lexicographically. Equivalently, take a polynomial such as $P = X^4 + X + 1$, write its coefficients as binary digits $\mathbf{b}10011$ and find that it is the $19$th polynomial. Let $f$ be the resulting bijection from $A$ to $\mathbb N$, so $f(P) = 19$.


The prime number theorem and Riemann hypothesis are known for the ring $A$. In fact, I learned from Paul Pollack's thesis (<http://alpha.math.uga.edu/~pollack/thesis/thesis-final.pdf>) that it is essentially contained in Gauss's unpublished 8th chapter of the Disquisitiones. But what about in this not-so-natural lexicographic order? In other words, let $\pi(x)$ be the number of irreducible polynomials $P$ in $A$ such that $0 \leq f(P) \leq x$.


Is it known or expected that the prime number theorem or Riemann hypothesis is true for $\pi(x)$? Is $\pi(x) \approx li(x)$ with error $O(\sqrt{x} \cdot \log(x))$?



Lexicographic distribution of irreducible polynomials
This is true.


By Gauss's theorem (the inclusion-exclusion formula for the number of irreducibles of a given degree), we may restrict to polynomials of a fixed degree $r$. A moment of reflection then shows that what is needed for lexicographical PNT is exactly the following: For every $k \in \mathbb{N}$, and every length $k$ binary vector $v$ with first letter $1$, we have as $r \to \infty$ (for $k$ fixed) that the proportion of degree $r$ irreducibles having $f(P)$ beginning with $v$ is $\sim 1/2^{k-1}$. For $k = 2$ this means that about half the polynomials have $f(P) \in [2^{r-1},2^{r-1}+2^{r-2}]$ and about half have $f(P) \in [2^{r-1}+2^{r-2},2^{r}]$, etc.


But, by the involution taking $P$ to its reciprocal, this the same as asking that, asymptotically as $r \to \infty$ for a fixed $k$, the degree $r$ irreducibles equidistribute in the $2^{k-1}$ invertible residue classes of $\mathbb{F}\_2[X]/(X^k)$. This is a particular case of the analog of the PNT in arithmetic progressions, well known to hold in any global field: the modulus $X^k$ here can be replaced by any polynomial element.


I think the RH statement should hold as well: the lexicographical writings of the degree-$r$ irreducible polynomials are uniformly distributed with square root error in $[2^{r-1},2^r]$. You could try looking at what the above outline gives with Weil's RH in global function fields: not the rational field $\mathbb{F}\_2(X)$ itself, but Carlitz's $X$-primary level analogs of the cyclotomic extensions of $\mathbb{Q}$.To put this (very) loosely, just as ERH is known to imply that primes $< x$ begin to equidistribute over $(\mathbb{Z}/q)^{\times}$ as soon as $x \gg q^{2+\epsilon}$, so similarly we should be able to take $r \approx 2k$ in the above, using Weil's theorem. [*Added: This is indeed carried out in Pollack's paper provided by So-called friend Don's comment.* ]


