Indexed on: 01 Jun '96Published on: 01 Jun '96Published in: Theory of Computing Systems
HereR andN denote respectively the real numbers and the nonnegative integers. Also 0 <n εN, ands(x) =x1+...+xn when x = (x1,...,xn) εRn. Adiagonal function of dimensionn is a mapf onNn (or any larger set) that takesNn bijectively ontoN and, for all x, y inNn, hasf(x) <f(y) whenevers(x) <s(y). We show that diagonalpolynomials f of dimensionn all have total degreen and have the same terms of that degree, so that the lower-degree terms characterize any suchf. We call two polynomialsequivalent if relabeling variables makes them identical. Then, up to equivalence, dimension two admits just one diagonal polynomial, and dimension three admits just two.