TAOCP 2.2.6 Exercise 22
For $k=2$, the classical Cantor polynomial p(i_1,i_2)=\frac{(i_1+i_2)(i_1+i_2+1)}2+i_2 has the required property.
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 22. [**] [M25] (P. Chowla, 1961.) Find a polynomial $p(i_1,\ldots,i_k)$ that assumes each nonnegative integer value exactly once as the indices $(i_1,\ldots,i_k)$ run through all $k$-dimensional nonnegative integer vectors, with the additional property that $i_1 + \cdots + i_k < j_1 + \cdots + j_k$ implies $p(i_1,\ldots,i_k) < p(j_1,\ldots,j_k)$.
Verified: no
Solve time: 35s
For $k=2$, the classical Cantor polynomial
$$ p(i_1,i_2)=\frac{(i_1+i_2)(i_1+i_2+1)}2+i_2 $$
has the required property. If $s=i_1+i_2$, then all pairs with sum $s$ are assigned the consecutive values
$$ \frac{s(s+1)}2,\ \frac{s(s+1)}2+1,\ \ldots,\ \frac{s(s+1)}2+s, $$
so every nonnegative integer occurs exactly once, and larger values of $s$ correspond to larger values of $p$.
For general $k$, let
$$ S_r=i_1+\cdots+i_r, $$
and define recursively
$$ p_1(i_1)=i_1,\qquad p_r(i_1,\ldots,i_r) = \frac{(p_{r-1}+i_r)(p_{r-1}+i_r+1)}2+i_r \quad (r\ge2). $$
Since the Cantor polynomial is a bijection from pairs of nonnegative integers to the nonnegative integers, induction on $r$ shows that $p_k$ is a polynomial that assumes each nonnegative integer value exactly once as $(i_1,\ldots,i_k)$ ranges over all nonnegative integer vectors. Furthermore, $p_r\ge p_{r-1}+i_r$, hence $p_r\ge S_r$ for all $r$. Therefore all vectors with total sum $<t$ are mapped into values $<p_k$ for every vector having total sum $t$. Consequently,
$$ i_1+\cdots+i_k<j_1+\cdots+j_k $$
implies
$$ p_k(i_1,\ldots,i_k)<p_k(j_1,\ldots,j_k). $$
Thus $p_k$ satisfies both required conditions. ∎