Given a projective variety $X$, each of its embeddings $i:X\hookrightarrow \mathbb P^N$ gives rise to an integer valued Hilbert polynomial $P_{X,i}(t)\in \mathbb Q[t]$.
These polynomials depend however on the chosen embedding $i$: for example $\mathbb P^1$ linearly embedded into $\mathbb P^2$ has Hilbert polynomial $H_{\mathbb P^1,\operatorname {lin}}(t)=t+1$ but when embedded as a conic by $i: \mathbb P^1 \hookrightarrow \mathbb P^2: (u:v)\mapsto (u^2:uv:v^2)$ it has Hilbert polynomial $H_{\mathbb P^1,i}(t)=2t+1$.
However, whatever embedding one chooses, all the polynomials $P_{X,i}(t)$ have the same degree, namely $\operatorname {dim} X$, and the same constant term $P_{X,i}(0)$, namely the arithmetic genus $p_a(X)=(1)^{\operatorname {dim} X}(\chi(X,\mathcal O_X)1)$.
My rather naïve question is then: which features of the Hilbert polynomial $P_{X,i}(t)$ are intrinsic to $X$, that is independent of the embedding $i:X\hookrightarrow \mathbb P^N$, apart from the degree and the constant term of that polynomial?
Edit
Another way of explaining what I'm after might be the question:
Given a projective variety $X$, which Hilbert polynomials does one obtain by embedding it into various projective spaces $X\hookrightarrow\mathbb P^N$ in all possible ways?

4$\begingroup$ Maybe useful: by Riemann–Roch, two numerically equivalent divisors give the same Hilbert polynomial $\chi(X,\mathcal O_X(nD_1)) = \chi(X,\mathcal O_X(nD_2))$ (this is very similar to proof 2 of this answer). Choosing a basis $\{D_i\}$ of the Néron–Severi group and using Snapper's lemma, we conclude that all Hilbert polynomials are specialisations of a common multivariate Hilbert polynomial (by suitable monomial substitutions $t = x_1^{e_1} \cdots x_r^{e_r}$ corresponding to $D = \sum e_i D_i$). $\endgroup$ – R. van Dobben de Bruyn Dec 12 '16 at 19:34

$\begingroup$ @R. van Dobben de Bruyn: that sounds promising ! I'd be grateful to you if you posted an answer about some interesting (classes of) examples of varieties of which you could determine explicitly, by specialization, the possible Hilbert polynomials . $\endgroup$ – Georges Elencwajg Dec 12 '16 at 23:41

1$\begingroup$ Oops, I made a mistake with the monomial substitution. The correct version is posted in my answer below. $\endgroup$ – R. van Dobben de Bruyn Dec 13 '16 at 5:35

1$\begingroup$ ChardinMorenoSocias' article is relevant. $\endgroup$ – Georges Elencwajg Sep 9 '17 at 7:32
The OP encouraged me to post my comment, along with some examples, as an answer, so here goes.
Lemma. Let $X$ be a smooth projective variety over an algebraically closed field $k$. Then there exists a numerical polynomial $p \in \mathbb Q[x_1,\ldots,x_r]$ such that for every (ample) divisor $H$ on $X$, there exist $e_1,\ldots,e_r \in \mathbb Z$ such that $$P_H(t) = p(e_1t,\ldots,e_rt).$$
Proof. If $D_1 \equiv D_2$ are numerically equivalent divisors, then Grothendieck–Riemann–Roch gives $$\chi(X,\mathcal O_X(D_i)) = \int_X \operatorname{ch}(\mathcal O_X(D_i)) \cdot \operatorname{Td}(X).$$ Since the right hand side only depends on certain intersection numbers of powers of $c_1(D_i)$, it only depends on the numerical class of $D_i$. Hence so does the left hand side, so $$\chi(X,\mathcal O_X(D_1)) = \chi(X,\mathcal O_X(D_2)).$$ Replacing $D_1$ and $D_2$ by powers, we conclude that $$P_{D_1}(t) = P_{D_2}(t).$$ Now choose a set of generators $D_1,\ldots,D_r$ of $\operatorname{NS}(X)$. By Snapper's lemma (see FGA Explained, Thm B.7), the function \begin{align*} \mathbb Z^r &\to \mathbb Z\\ (m_1,\ldots,m_r) &\mapsto \chi(X,\mathcal O_X(m_1D_1 + \ldots + m_rD_r)) \end{align*} is a numerical polynomial $p \in \mathbb Q[x_1,\ldots,x_r]$. The result follows since any divisor is numerically equivalent to $\sum e_i D_i$ for some $e_i$. $\square$
Remark. Note that we don't need $H$ or the $D_i$ to be ample. This gives some extra flexibility in computations, as we will see in the example below.
Remark. It turns out it's actually pretty hard to compute this $p$, for example because it depends on a choice of generators of $\operatorname{NS}(X)$. Let's carry out a nontrivial example.
Example. Let $X = \mathbb F_n$ be the $n$th Hirzebruch surface. Then we have $\operatorname{Pic}(X) = \mathbb Z H \oplus \mathbb Z F$, with $H^2 = n$, $F^2 = 0$, and $F\cdot H = 1$ (see e.g. Beauville's Complex Algebraic Surfaces, Prop IV.1). Thus, the intersection product is given by the symmetric bilinear form $$\begin{pmatrix} n & 1 \\ 1 & 0 \end{pmatrix}.$$ Moreover, the canonical class is $K = 2H + (n  2)F$ (see loc. cit., Prop III.18). Finally, we have $\chi(X,\mathcal O_X) = 1$, for example since $X$ is rational and $\chi(X,\mathcal O_X)$ is a birational invariant (or: compute).
This allows us to compute everything: by Riemann–Roch, we have \begin{align*} \chi(X,\mathcal O_X(aH+bF)) &= \tfrac{1}{2}(aH+bF)\cdot(aH+bFK) + \chi(X,\mathcal O_X).\\ &= \tfrac{1}{2}\begin{pmatrix}a & b\end{pmatrix}\begin{pmatrix} n & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a+2 \\ b+2n \end{pmatrix} + 1\\ &= \tfrac{1}{2}(na(a+2) + a(b+2n) + b(a+2)) + 1\\ &= \tfrac{1}{2}(na^2 + 2ab + (n+2)a + 2b) + 1. \end{align*} That is, $$p(x,y) = \tfrac{n}{2}x^2 + xy + (\tfrac{n}{2}+1)x + y + 1.$$ Substituting $(x,y) = (at,bt)$ gives $$P_{aH+bF}(t) = (\tfrac{n}{2}a^2+ab)t^2 + (\tfrac{an}{2}+a+b)t + 1.$$ Thus, the polynomials occurring as Hilbert polynomial of some divisor are parametrised by $$P(t) = f_2(a,b)t^2 + f_1(a,b)t + 1,$$ where \begin{align*} f_2(a,b) &= \tfrac{n}{2}a^2+ab\\ f_1(a,b) &= (\tfrac{n}{2}+1)a+b. \end{align*} In general, this method gives $\dim X$ homogeneous polynomials $f_1, \ldots, f_d$ in $\rho(X) = \operatorname{rk} \operatorname{NS}(X)$ variables of degrees $1, \ldots, d$ respectively (as noted, the constant term is always $\chi(X,\mathcal O_X)$).
If one then wishes to restrict to ample divisors only, one firstly has to classify which ones they are (one might try to use Nakai–Moishezon, but one has to think about how to find the effective curve classes algorithmically).
Ample divisors on $\mathbb F_n$. We want to use the Nakai–Moishezon criterion to find the ample divisors. Note that the only irreducible curve in $aH + bF$ for which $a$ or $b$ is negative is $B \in H  nF$ (see loc. cit., proof of Prop IV.1). Note that $B \cdot (aH + bF) = b$ for all $a, b \in \mathbb Z$.
Claim. A divisor $D = aH + bF$ is ample if and only if $a > 0$ and $b > 0$.
Proof. If $D$ is ample, then $a = D \cdot F > 0$ and $b = D \cdot B > 0$.
Conversely, let $D = aH + bF$ with $a > 0$ and $b > 0$. Then $D \cdot B > 0$, and $D \cdot (cH + dF) > 0$ whenever $c \geq 0$ and $d \geq 0$ and $(c,d) \neq (0,0)$. This includes $D^2$ and $D \cdot C$ for $C$ any irreducible curve other than $B$. Thus, the Nakai–Moishezon criterion implies that $D$ is ample. $\square$
(Note in particular that $H$ is not ample.)
Closing remark. While in theory this gives a complete answer to the question which polynomials are Hilbert polynomials of divisors, we already see from this (relatively easy) example that this method is very laborious.
Moreover, it does not work nicely in families, because the Picard rank might jump. Even for nicely behaved varieties like abelian varieties or K3 surfaces, this phenomenon occurs, making it virtually impossible to answer the question in full generality for those varieties.
On the other hand, for surfaces the answer depends only on the Néron–Severi lattice of $X$, together with the canonical class and the effective cone of curves (to find back the ample divisors). In higher dimensions, this picture is complicated a little bit in that it needs the full knowledge of the Todd class (which now contains more data than just the canonical class).

$\begingroup$ Splendid answer, Remy: bravo and thanks a lot. $\endgroup$ – Georges Elencwajg Dec 13 '16 at 6:48

$\begingroup$ By the way, do very ample divisors on $\mathbb F_n$ correspond to $a\gt 0, b\gt 0$ ? $\endgroup$ – Georges Elencwajg Dec 13 '16 at 7:51