Infinitely many irreducible polynomials of the form f(X^2) + X mod 3? Are there infinitely many polynomials $f \in \mathbb{F}_3[X]$ for which $f(X^2) + X$ is irreducible?
 A: (Not an answer, just too long for a comment.)
Let $A_{2n, a,q} := \{ x^{2n} + a_1 x^{2n-2} + a_2 x^{2n-4} +\cdots + a_{n-1} x^{2} + ax + a_n \mid a_i \in \mathbb{F}_{q} \} \cap \{f \in \mathbb{F}_{q}[x], \text{ irreducible}\}$.
You are considering the infinitude of $A:=\cup_{n\ge 1} \cup_{a \neq 0} A_{2n,a,3}$ (actually, you force $a=1$ but don't require monic; I reversed the roles of these 2 properties).
There's extensive literature on counting irreducibles with coefficients coming from affine varieties, where your example is actually one of the simplest (you just prescribe certain coefficients). The first 3 pages of this paper offer a nice survey.
In short, algebraic geometry counting methods give asymptotic information on sizes of sets like $A_{2n,a,q}$, with a very accurate main term but a rather big error term, which allows one to extract information only for big $q$, i.e. bounded from below by a function of $n$. This means that for any $q$, you can bound the size of $\cup_{n\ge 1} \cup_{a \neq 0} A_{2n,a,q}$ from below, and that size will grow to infinity as $q$ does. 
(Hence, one reason that your problem is especially hard is that your $q$ is the smallest possible apart from $2$, and $2$ was at least studied w.r.t applications.)
It seems that the only known case where the error term is much better than described is when you count irreducibles in an arithmetic progression, as you can use the machinery of L-functions (theorem 1.2 in the paper). For instance, the results concerning your polynomials, and results concerning counting the sparser set of irreducible trinomials $x^{2n}+ax+b$ are basically the same, although the 2nd problem seems much harder (theorem 1.3 in the paper). But prescribing instead the $m$ consecutive lower coefficients instead of odd-indexed-coefficients gives asymptotic information as $q^{n-2m} \to \infty$, not just $q \to \infty$.
(Here we see another reason for your problem being very difficult: you prescribe half of the coefficients to be 0. Even the better error term of the arithmetic progression case gives information only when prescribing slightly less than half of the coefficients, otherwise you get the "worse" error-term of theorem 1.3.)
There are 3 standard routes you can take now: 


*

*Use the above methods for your specific set, but perform a much more delicate calculation (by using, for example, the explicit formula for $\mathbb{F}_{q}$-points on a variety instead of Lang-Weil estimates). 

*Try to find an ad-hoc construction of a family of the form you seek. You won't get them all, but there's a chance of finding infinitely many. A good starting point is page 60 in this handbook.

*Relax some of the conditions, and try again :)


Good luck!
A: $\def\FF\mathbb{F}$Lemma The following are equivalent:
(1) $f(x^2)+x$ is prime in $\FF_3[x]$ 
(2) $f(x^2)^2-x^2$ is prime in $\FF_3[x^2]$
(3) $f(y)^2-y$ is prime in $\FF_3[y]$.
Proof (2) and (3) simply differ by the change of variable $y=x^2$, and are thus equivalent. Set $g=f(x^2)+x$, $\overline{g} = f(x^2)-x$ and $h=g \overline{g}=f(x^2)^2-x^2$. We see that $h$ is the norm of $g$ from $\FF_3[x]$ to $\FF_3[x^2]$. An element with prime norm must be prime, so (2) implies (1).
Conversely, suppose (1). So $h=g \overline{g}$ is the prime factorization of $h$ in the PID $\FF_3[x]$. It is easy to see that $g$ and $\overline{g}$ are not associate to elements of $\FF_3[x^2]$, so $h$ is irreducible (and hence prime) in $\FF_3[x^2]$. $\square$
Bunyakovsky's conjecture states that, if $a(T)$ is a polynomial obeying certain natural conditions, then $a(T)$ is prime for infinitely integers $T$. This is widely believed, but has not been proved for any $a$ of degree $\geq 2$.
Similarly, you want to know whether $T^2-y$ is prime for infinitely many $T \in \FF_3[y]$. 
People have made conjectures analogous to Bunyakovsky in function fields (see Conrad, Conrad and Gross, conjecture 6.2). However, Conrad, Conrad and Gross (first page) also write 

The only proved instance of this asymptotic conjecture is the case where $\deg_T a=1$, just as in the classical case.

Some brief literature searches suggest that little has changed since that statement was written in 2008. So you are probably out of luck to prove this result.
