Re: functions not polynomials

[Vaughan Pratt <pratt@cs.stanford.edu>]

The counterexample Paul cites of a function f(x,y) that is a univariate
polynomial in x and y separately but not a bivariate polynomial in x and
y jointly has the following "degree growth" property:

(*)  For each d in N, f(-,d) and f(d,-) are polynomials of degree <= d.

As anyone who's played around with bicubic patches for computer graphics
knows, the degree has to grow for such a counterexample since any global
bound on the degree of f(x,-) and f(-,y) separately suffices for f(x,y)
to be a polynomial in x and y jointly with the same degree bound (taking
the degree of x^3 y^2 to be 3 rather than 5).

The class of all functions of the above degree-growing form has the
following nice characterization if we take real-valued rather than
integer-valued functions (or any other algebraically closed field),
still defined on N and NxN however.  Let U be that subset of NxN --> R
whose functions enjoy the above degree growth property (*).  Define W:
(NxN --> R) --> (N --> R) by Wf(x) = f(x,x) for all x in N.

Theorem.  The restriction of W to U is a bijection.

(So if W is in some sense natural we have a natural bijection, about as
close as I'm going to get to anything sounding at all categorical here.)

Proof.  Let g: N --> R be an arbitrary sequence of reals.  We show by
induction on the d in (*) that there exists a unique f in U for which Wf
= g.  Take the induction hypothesis to be that f(-,i) and f(i,-) are
uniquely determined polynomials of degree at most d for all natural
numbers i <= d.  If the induction hypothesis holds for all d in N we
have completely determined f.

Base case.  f(-,0) and f(0,-) are constant functions, whence for all
natural numbers x,y, necessarily f(x,0) = f(0,y) = f(0,0) = g(0).

Inductive step.  Assuming the induction hypothesis for d, take
f(d+1,d+1) = g(d+1).  This determines f(i,d+1) and f(d+1,i) for all i
from 0 to d+1, which in turn uniquely determines f(-,d+1) and f(d+1,-)
as polynomials of degree d+1 (exactly one polynomial of degree d+1
passes through d+2 points).  The induction hypothesis therefore holds
for d+1.  QED

Corollary.  The members of U are symmetric: f(x,y) = f(y,x).

So the symmetry in Paul's example was not just an isolated artifact but
an inevitable consequence of his rate of degree growth.

QUESTION: For which g does W^{-1}(g) (of type NxN --> R) extend "nicely"
to RxR --> R, for any given notion of niceness?  For example if g is a
polynomial of degree d then so is W^{-1}(g), giving the obvious
extension to RxR as the same polynomial.  What if g is periodic,
ultimately constant, ultimately periodic, etc.?

Vaughan

Paul Taylor wrote:
> Let  f: Z x Z -> Z  be a binary FUNCTION (in the sense of sets)
> on the integers, with the property that
>
>  - for each x:Z,  f(x,-) : Z -> Z is a (agrees with a unique)
>    POLYNOMIAL, whose coefficients are functions of x; and similarly
>
>  - for each y:Z,  f(-,y) : Z -> Z is also a polynomial.
>
> Then  f(x,y)  was itself a polynomial in two variables.
>
> "You just use Newton's difference method to find the co..."
>
> .... unterexample.
>
> Taking N for simplicity first, consider the binomial coefficient
> (x,n) as an nth degree polynomial in x, ie
> (x,0) = 1
> (x,1) = x
> (x,2) = x(x-1)/2
> (x,3) = x(x-1)(x-2)/3!
> and so on.  Newton's finite difference method provides the coefficients
> of these generating polynomials by taking successive differences (the
> finite analogue of successive derivatives).
>
> But then    sum_n (x,n)(y,n)
> is a function NxN->N that is a polynomial in x for each y and vice versa
> but isn't itself a polynomial.