0

Problem: Consider polynomials with natural coefficients of $n$ natural variables. Prove a computable universal function exists for this class. Prove that any such function is not a polynomial.

Attempt: Consider an ordering of the monomials. The polynomials of $n$ variables can now be represented by their coefficients. That is to each polynomial we assign its list of coefficients in ascending order of the monomials they belong to, a bijection from the polynomials to the lists of natural numbers. If $\gamma$ is an effective coding of the lists, we get a coding of all the polynomials $\{\varphi_i: \quad i=\gamma(<j_0,\dots,j_s>)\}$.

A universal function is now $\Phi(\overline x,i)=\varphi_i(\overline x,i)$

How should I proceed?

superAnnoyingUser
  • 4,379

1 Answers1

0

Not any ordering works, but the graded lexicographical ordering does, for any monomial $x^\alpha$ in it has only finitely many monomials smaller than $x^\alpha$. Now if $x_k$ is the $k$-th monomial in the ordering, $$\Phi(\overline x,i)=\sum_{k<lh(i)}mem(i,k)x_k$$

Now assume $\Phi(\overline x,i)$ is a polynomial. Then $$\Phi(\overline x,i)=\sum_{|\alpha|+a\leq deg(\Phi)}c_\alpha i^a\overline x^\alpha$$

If $\beta$ is a multi-index of length $n$ and if $|\beta|>deg(\Phi)$ then $\overline x^\beta\not=\Phi(\overline x,i)$, for all $i\in\mathbb N$, a contradiction. Therefore, $\Phi(\overline x,i)$ is not a polynomial.

superAnnoyingUser
  • 4,379