Re: functions not polynomials

Re: functions not polynomials

[Vaughan Pratt]

A couple of days ago, in response to a post to this list by Paul Taylor,
I showed that W: (NxN --> R) --> (N --> R), defined as W(f)(x) = f(x,x),
is bijective on the subset U of NxN --> R consisting of those f: NxN -->
R for which f(-,d) and f(d,-) are polynomials of degree d for each d in
N.  As an afterthought I raised the question, for which g: N --> R can
W^{-1}(g): NxN --> R be extended to RxR --> R?

To get some idea of what could happen I wrote the following program
wttmo.c (W To The Minus One).

=====wttmo.c=====
 > #include <stdlib.h>
 >
 > int main(int argc, char *argv[])
 > {
 >     int i, j, m, n;
 >     double a[100], f[100][100];
 >     n = argc - 1;
 >     for (i = 0; i < n; i++)        /* Input */
 >         f[i][i] = atof(argv[i+1]);
 >     for (m = 0; m < n-1; m++) {    /* Process */
 >         for (i = 0; i <= m; i++)
 >             a[i] = f[m][i];
 >         for (i = 0; i < m; i++)
 >             for (j = 0; j < m-i; j++)
 >                 a[j] = a[j+1] - a[j];
 >         for (i = m+1; i < n; i++) {
 >             for (j = 0; j < m; j++)
 >                 a[j+1] += a[j];
 >             f[i][m] = f[m][i] = a[m];
 >         }
 >     }
 >     for (i = 0; i < n; i++) {     /* Output */
 >         for (j = 0; j < n; j++)
 >             printf("%-7.3f ", f[i][j]);
 >         printf("\n");
 >     }
 > }
=================

(Note that this program gives a well-defined result not just for the
reals but for any group, even a nonabelian one, since the only
operations performed are addition and subtraction.  This generality can
be reconciled with the original problem, and with my proof of
bijectivity of W on U, by saying that a sequence s obeys a polynomial
law of degree (at most) d just when the d-th finite difference D^d(s) is
a constant sequence, where the finite difference operator D(s) replaces
each s_i by s_{i+1}-s_i in s.)

This program is run from the command line with n real parameters
constituting the first n elements g(0), g(1), ..., g(n-1) of a sequence
g.  The output is W^{-1}(g), laid out as an nxn matrix with the entry at
row i and column j (numbering from 0) giving W^{-1}(g)(i,j) for i and j
from 0 to n-1.

Applying it to the polynomial 2 + 3x^2 gives the following result,

$ wttmo 2 5 14 29 50 77 110 149 194
2.000   2.000   2.000   2.000   2.000   2.000   2.000   2.000   2.000
2.000   5.000   8.000   11.000  14.000  17.000  20.000  23.000  26.000
2.000   8.000   14.000  20.000  26.000  32.000  38.000  44.000  50.000
2.000   11.000  20.000  29.000  38.000  47.000  56.000  65.000  74.000
2.000   14.000  26.000  38.000  50.000  62.000  74.000  86.000  98.000
2.000   17.000  32.000  47.000  62.000  77.000  92.000  107.000 122.000
2.000   20.000  38.000  56.000  74.000  92.000  110.000 128.000 146.000
2.000   23.000  44.000  65.000  86.000  107.000 128.000 149.000 170.000
2.000   26.000  50.000  74.000  98.000  122.000 146.000 170.000 194.000

consistent with producing f(x,y) = 2 + 3xy.  This of course extends in
the usual way to RxR --> R.

Nudging the first two elements very slightly

$ wttmo 2.001 5.001 14 29 50 77 110 149 194
2.001   2.001   2.001   2.001   2.001   2.001   2.001   2.001   2.001
2.001   5.001   8.001   11.001  14.001  17.001  20.001  23.001  26.001
2.001   8.001   14.000  19.998  25.995  31.991  37.986  43.980  49.973
2.001   11.001  19.998  29.000  38.015  47.051  56.116  65.218  74.365
2.001   14.001  25.995  38.015  50.000  61.796  73.156  83.740  93.115
2.001   17.001  31.991  47.051  61.796  77.000  96.220  127.420 184.595
2.001   20.001  37.986  56.116  73.156  96.220  110.000 5.480   -531.865
2.001   23.001  43.980  65.218  83.740  127.420 5.480   149.000 4915.055
2.001   26.001  49.973  74.365  93.115  184.595 -531.865 4915.055 194.000

really shakes things up (look at f(i+1)(i), especially the region
38.015,61.796,96.220,5.480,4915.055 which used to be 38,62,92,128,170).
  The prospects for extending this evidently chaotic function NxN --> R
to RxR --> R "nicely" look pretty bad -- at the very least it would seem
to require a very liberal notion of "nice".

In my previous post I claimed that W^{-1} maps polynomials to
polynomials, but realized later that the only polynomials for which this
was the case were those of the form g(x) = a + bx^2 for arbitrary
constants a and b, for which W^{-1}(g) is f(x,y) = a + bxy.  The
simplest polynomial not mapped to a polynomial is the identity function,
g(x) = x:

$ wttmo 0 1 2 3 4 5 6 7
0.000   0.000   0.000   0.000   0.000   0.000   0.000   0.000
0.000   1.000   2.000   3.000   4.000   5.000   6.000   7.000
0.000   2.000   2.000   0.000   -4.000  -10.000 -18.000 -28.000
0.000   3.000   0.000   3.000   24.000  75.000  168.000 315.000
0.000   4.000   -4.000  24.000  4.000   -280.000 -1176.000 -3164.000
0.000   5.000   -10.000 75.000  -280.000 5.000   5910.000 28595.000
0.000   6.000   -18.000 168.000 -1176.000 5910.000 6.000   -171528.000
0.000   7.000   -28.000 315.000 -3164.000 28595.000 -171528.000 7.000

Very unfunctorial of wttmo.  :)

In GF(2) (suitably modifying the program, including writing # for 1 and
space for 0 in the output for better contrast), wttmo maps the identity
polynomial x = 0,1,0,1,0,1,... to xy, which is as one would expect given
that x = x^2 in GF(2).

More interestingly it maps the sequence 1,0,0,0,0,... to the Sierpinski
gasket, shown here for the top left 32x32 elements of f.

################################
# # # # # # # # # # # # # # # #
##  ##  ##  ##  ##  ##  ##  ##
#   #   #   #   #   #   #   #
####    ####    ####    ####
# #     # #     # #     # #
##      ##      ##      ##
#       #       #       #
########        ########
# # # #         # # # #
##  ##          ##  ##
#   #           #   #
####            ####
# #             # #
##              ##
#               #
################
# # # # # # # #
##  ##  ##  ##
#   #   #   #
####    ####
# #     # #
##      ##
#       #
########
# # # #
##  ##
#   #
####
# #
##
#


It is tempting to infer the fractal nature of wttmo from this.  However
the Sierpinski gasket also arises as Pascal's triangle mod 2, so perhaps
one shouldn't read too much into this.


Vaughan Pratt

Re: functions not polynomials

[Vaughan Pratt]

Paul Taylor's example of an f(x,y) that is polynomial separately in x
and y but not jointly was sum_n (x,n)(y,n) (where (x,n) denotes the
binomial coefficient x!/(n!(x-n)!)).  After mulling over that example
some more it occurred to me that it can be analyzed via the observation
that W^{-1} maps the polynomial P_n(x) = (x(x-1)(x-2)...(x-(n-1)))^2 to
the polynomial xy(x-1)(y-1)(x-2)(y-2)...(x-(n-1))(y-(n-1)).  This
contradicts my earlier claim that the only polynomials in x that W^{-1}
maps to polynomials in x and y are the linear combinations of 1 and x^2.
  These two are easily seen to be the only *monomials* so mapped, but
(the linearity of W^{-1} notwithstanding) it does not follow that the
only *polynomials* so mapped are the linear combinations of these two
monomials.

W^{-1} maps sum_n P_n(x)/(n!)^2 to Paul's example.  The coefficient
1/(n!)^2 of P_n(x) seems to play no role here, and any coefficients
should do as long as infinitely many are nonzero (to make f(x,y) not a
polynomial).  To extend the example (as a function on N^2) directly (via
the constituent polynomials) to a function on the positive reals
however, the coefficients would need to grow somewhat slower than 4^n,
|P_n(x)| being bounded above by at best about 1/4^n for 0 < x < n (the
half-integer points for x in that range give a good approximation of the
bound).  1/(n!)^2 is more than slow enough for this purpose.

A simpler example is g(x) = (2x,x) (again the binomial coefficient),
which W^{-1} maps to f(x,y) = (x+y,x), polynomial separately in x and y
but not jointly.  That is, Pascal's triangle is a sufficient
counterexample for Paul's purposes.  Moreover the Gamma function gives a
nicer (log-convex in fact) extension of f(x,y) to the upper right
quadrant of R^2.

Vaughan Pratt

Re: functions not polynomials

[Vaughan Pratt]

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.

functions not polynomials

[Paul Taylor]

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.

None of the web pages that I found about this method was especially
clear, so I'm not going to recommend any, but they are there if you
want to look for them yourself.

The more general method (as described on these pages, which is why
I didn't think they were that good) takes differences from any sequence
of points, not just 0, 1, 2, ....  Hence, given any enumeration of
a countable field K (this probably works for Z too) we can generalise
both the method of fitting polynomials and the counterexample.


Of course, since I'm a categorist, it was the categorical formulation
that interests me.  Any thoughts on that would be appreciated, despite
the above failure of the simple example.

In fact, I'd quite like to hear from any students of universal algebra
out there who also know how monads encode algebraic theories, and might
be willing to help as sparring partners for my present mad scheme.

Paul Taylor