Which polynomials arise as formulas for a conjugate For any integer $r \geq 2$, et $V_r$ be the set of polynomials $Q \in {\mathbb Q}[X]$ of degree $r-1$ such that there is an algebraic number $\alpha$ of degree $r$ , such that
$Q(\alpha)$ is a conjugate of $\alpha$. 
   It is not hard to see that $V_2$ consists exactly of $X$ and all the polynomials $a_0-X$, for $a_0\in {\mathbb Q}$. Have
the $V_r(r \geq 3)$ been studied? Is anything known about $V_3$ ?
 A: If $f(x)$ is in $V_r$, and $g(x)$ is the minimal polynomial of a corresponding element $\alpha$,
then $f(\alpha)$ is also a root of $g(x)$, so $g(f(\alpha))=0$; hence $g(x)$ divides $g(f(x))$.
Thus, $V_r$ consists of the polynomials $f(x)\in\mathbb{Q}[x]$ of degree $r-1$ for which
there is an irreducible degree-$r$ polynomial $g(x)\in\mathbb{Q}[x]$ satisfying
$g(x)\mid g(f(x))$.  This perspective explains the result for $r=2$: the map $\beta\mapsto f(\beta)$
must permute the two roots of $g(x)$, and the only linear polynomials which permute two numbers are $x$ and $a_0-x$ (this doesn't quite show $a_0-x\in V_2$, one has to finish as Victor did).
A: $\newcommand\Z{\mathbf{Z}}$
$\newcommand\Q{\mathbf{Q}}$
If we replace $\alpha$ by $\alpha + \lambda$ for $\lambda \in \Q$ (translation), we may
replace $Q(X)$ by $Q(X - \lambda) + \lambda$. 
Similarly, if we replace $\alpha$ by $\mu \cdot \alpha$ (dilation), we may replace $Q(X)$ by
$\mu \cdot  Q(X/\mu)$. 
Let's  discuss the case $[\Q(\alpha):\Q] = 3$.
By translation, we may assume that the
coefficient of $X$ is trivial. By dilation, we may assume that
the leading coefficient is $1$ (this specifically
uses the fact that we are in degree $3$).
Hence $Q(X) = X^2 + c$ for some $c \in \Q$.
If a degree $3$ field $K = \Q(\alpha)$  contains at least two conjugates of
$\alpha$ then it contains
all the conjugates, and is therefore Galois with cyclic Galois group.
Thus $Q$ induces an isomorphism of $K$ of order three, and
$\alpha$ must be a root of
$Q(Q(Q(X))) - X$ but not a root of $Q(X)  -X$.
Hence it is a root of $F(X) = (Q(Q(Q(X))) - X)/(Q(X) - X)$, which
is an explicit degree $6$ polynomial.
Suppose that $\beta = u + v \sqrt{d}$ is a root of $F(X)$, where $u$ and $v$ are rational and $d$ is
not a square. We may write $F(u + v \sqrt{d}) = R(u,v) + S(u,v) \sqrt{d}$, where
$R$ and $S$ are polynomials with coefficients in $\Q[a,b]$.
 Since $F(\beta) = 0$, then
$R(u,v) = S(u,v) = 0$. Computing the resultant 
of these polynomials with respect to $c$, we obtain the equation:
$$(1 + 2 u^2 + 4 u^2)(-1 - 18 u + 4u^2 + 8 u^3) v = 0.$$
Since $u$ is rational, it follows that $v = 0$. Thus
$F(X)$ does not have any genuine quadratic solutions,
and hence $F(X)$ has
no factors that are quadratic. 
(If we assume that $F(X)$ has a cubic factor, we can prove this in a slightly cleaner way.
Since $F(X)$ has a cubic factor, it has at most one quadratic factor. Yet $Q(\beta)$ and $Q(Q(\beta))$ are also quadratic roots of $F(X)$, and hence either $Q(\beta) = \beta$ or $Q(\beta) = \sigma \beta$. Both possibilities are impossible.)
We are assuming that $F(X)$ has a cubic factor corresponding to $\alpha$. 
Then either $F(X)$ factors as a product of two cubics, or as a cubic times three linear factors. In either case, the cubics correspond to fields
which are Galois and hence cyclic of degree three. Hence the discriminant of $F(X)$ is a square (easy exercise). We compute explicitly that
$$\Delta_F = - (7 + 4 c)^3 (7 + 4 c + 16 c^2)^2,$$
and hence we deduce the  necessary relation:
$$7 + 4 c = - t^2$$
for some $t \in \Q$. 
Making the substitution $c = (-7 - t^2)/4$, 
the polynomial $2^{6} \cdot F(X)$ factors
as $A(X,t) A(X,-t)$, where
$$A(X,t) = 
1 + 7 t - t^2 + t^3 + 18 x - 4 t x + 2 t^2 x - 4 x^2 - 4 t x^2 - 8 x^3.$$
As long as either this polynomial or its cousin
$A(X,-t)$ are  irreducible, we obtain a cubic
with a root $\alpha$ such that $Q(\alpha)$ is a conjugate of $\alpha$.
The polynomial $A(X,t)$ is reducible in $t$ if and only if there exists a
rational point $A(X,t) = 0$. This turns out to be a rational curve, and
we deduce that it is reducible if and only if there exists a $u \in \Q$
such that
$$t = \frac{1 + 2 u - u^2 - u^3}{u(u+1)}.$$
On the other hand, $A(X,-t)$ is reducible if and only if
there exists a $v \in \Q$ such that
$$-t = \frac{1 + 2 v - v^2 - v^3}{v(v+1)}.$$
Hence any forbidden $t$ corresponds to a solution to
the equation
$$\frac{1 + 2 u - u^2 - u^3}{u(u+1)} = - \frac{1 + 2 v - v^2 - v^3}{v(v+1)},$$
which correspond to points on the curve
$$C:u + u^2 + v + 4 u v + u^2 v - u^3 v + v^2 + u v^2 - 2 u^2 v^2 - u^3 v^2 - u v^3 - u^2 v^3 = 0.$$
This curve is smooth in the affine locus.
The corresponding projective curve has three points at $\infty$, and
two of the corresponding points are singular.
The singularities at these points are nodes (I think),
and thus using Plücker's formula, we deduce that
$C$ has genus:
$$ g = (d-1)(d-2)/2 - n = (4 \cdot 3)/2 - 2 =4.$$
Thus $C$ has finitely many rational points (Faltings). 
(Note: this calculation may have been wrong, but we won't actually use it.)
The curve $C$ has some obvious points at $\infty$ and when 
$u(u+1)v(v+1) = 0$. 
Make the substitution $u = x+y$ and $v = x-y$. Then
the equation becomes:
$$-x - 3 x^2 - x^3 + 2 x^4 + x^5 + y^2 + x y^2 - 2 x^2 y^2 - 
2 x^3 y^2 + x y^4 = 0.$$
This is a quadratic in $y^2$. Hence we obtain a degree two covering
$C \rightarrow E$, where $E$ is the curve 
$$E:-x - 3 x^2 - x^3 + 2 x^4 + x^5 + z + x z - 2 x^2 z - 
2 x^3 z + x z^2 = 0.$$
Given a rational point on this curve, the discriminant
$\Delta$ is rational, and hence $E$ is isomorphic to:
$$\Delta^2 = 4(4 x^4 + 3 x^3 + x^2 + 2 x + 1)
= 4(1+x)(1+2x)(1-x+2x^2)$$
This is birational to an elliptic curve which
turns out to have conductor $112$. Cremona's program
 mwrank tells me has Mordell-Weil group
$\Z/2\Z$. Hence
the only rational points correspond to $x = -1/2$ and $x = -1$,
which pull back to the "obvious" rational points on $C$. Hence
we have determined $C(\Q)$ completely, and we see that
one of $A(X,t)$ or $A(X,-t)$ is always irreducible.
Hence we deduce:
If $\alpha$ is a cubic irrationality with $Q(\alpha) = \sigma \alpha \ne \alpha$,
then, replacing $\alpha$ by $\lambda \alpha + \mu$, 
$Q(X)$ is of the form:
$$Q(X) = X^2 - \frac{7+t^2}{4}$$
with $t \in \Q$.
Conversely, for any such $Q(X)$, there exists
 a cubic irrationality $\alpha$
such that $\sigma \alpha = Q(\alpha)$.
Example: $t = 1$, and $Q(X) = X^2 - 2$. Then $\alpha = 2 \cos(2 \pi/7)$.
For higher degree polynomials, things will be even more of a mess, because
there will be various possibilities corresponding to  what the Galois closure is,
&. &. The answer will have the following flavor: It will correspond
to the rational points on a bunch of varieties minus
 rational points on subvarieties corresponding to
degeneracies (which in this case turn out to be empty).
