Are there infinitely many polynomials $f \in \mathbb{F}_3[X]$ for which $f(X^2) + X$ is irreducible?
$\def\FF\mathbb{F}$Lemma The following are equivalent:
(1) $f(x^2)+x$ is prime in $\FF_3[x]$
(2) $f(x^2)^2x^2$ is prime in $\FF_3[x^2]$
(3) $f(y)^2y$ 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)^2x^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^2y$ 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.

$\begingroup$ Very interesting! What if we replace 'irreducible' by 'squarefree' ? The lemma seems to be still correct, and for squarefree values more is known, as can be seen from m.qjmath.oxfordjournals.org/content/early/2015/07/04/… $\endgroup$ – Pablo Jul 11 '15 at 7:39

3$\begingroup$ It is important to add that Chris Hall, in his PhD, showed that there are infinitely many $f$ with both $f$ and $f+1$ irreducible (his argument used the the field has at least 4 elements, I think) $\endgroup$ – Lior BarySoroker Jul 11 '15 at 11:13

$\begingroup$ I should probably point also out that this statement is about known cases of the full asymptotic conjecture, not about cases where there are simply known to be infinitely many examples. $\endgroup$ – David E Speyer Jul 11 '15 at 17:42

$\begingroup$ @DavidSpeyer are there (nonlinear) cases in which we know an infinite family of irreducible examples? $\endgroup$ – Pablo Jul 12 '15 at 8:30

$\begingroup$ Suppose that $\ell$ and $q$ are odd primes, with $q \equiv 1 \bmod \ell$ and $a \in \mathbb{F}_Q$ is not an $\ell$th power. Then $x^{\ell^n}  a$ is irreducible for every $n$. In particular, $T^{\ell}  a$ is irreducible infinitely often. See math.stackexchange.com/a/413065/448 , and also other answers there. $\endgroup$ – David E Speyer Jul 13 '15 at 19:09
(Not an answer, just too long for a comment.)
Let $A_{2n, a,q} := \{ x^{2n} + a_1 x^{2n2} + a_2 x^{2n4} +\cdots + a_{n1} 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 Lfunctions (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 oddindexedcoefficients gives asymptotic information as $q^{n2m} \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" errorterm 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 LangWeil estimates).
 Try to find an adhoc 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!

$\begingroup$ Ofir, thank you very much for all this information! The point is that I have already thought about some of this things, and came to the conclusion that treating this problem as restrictions on coefficients is not the right way. The reason for this is that it seems not so difficult to prove that there are infinitely many irreducible polynomials of the form $f(X^2)$ directly, but doing this with the methods of saying "all the odd coefficients = 0" is probably hopeless. I do agree that taking half of the coefficients to be zero and hoping for an irreducible polynomial is too much to ask for. $\endgroup$ – Pablo Jul 11 '15 at 8:13

2$\begingroup$ I see :) Then I suggest trying to find a suitable family. What about $a\cdot X^{3^k+1}+X+b$? The following paper of Agou, in French, studies the irreducibility of that family: matwbn.icm.edu.pl/ksiazki/aa/aa44/aa4444.pdf (MR number is MR0777011). If you delve into this, I would be glad to see an update later! $\endgroup$ – Ofir Gorodetsky Jul 11 '15 at 8:21

$\begingroup$ Do you understand their conclusion? Sadly enough, my French is not perfect yet... $\endgroup$ – Pablo Jul 11 '15 at 8:28

1$\begingroup$ Mine neither. But I think that the obstruction for such polynomials to be irreducible comes from certain possible quadratic factors only (proposition 3.1.2). If you can rule out those factors (for infinitely many $(a,b)$'s), it establishes irreducibility. It also might be of use to read other papers by Agou, or to contact him. $\endgroup$ – Ofir Gorodetsky Jul 11 '15 at 8:34

$\begingroup$ x^i + x  1 with i even is irreducible mod 3 for i = 2,4,6,14,30,54,364,446,638,1382,1478,2726, and ??. $\endgroup$ – Dracula Jul 11 '15 at 18:28