* Re: functions not polynomials
@ 2007-03-29 3:47 Vaughan Pratt
0 siblings, 0 replies; 4+ messages in thread
From: Vaughan Pratt @ 2007-03-29 3:47 UTC (permalink / raw)
To: categories list
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: functions not polynomials
@ 2007-03-26 19:26 Vaughan Pratt
0 siblings, 0 replies; 4+ messages in thread
From: Vaughan Pratt @ 2007-03-26 19:26 UTC (permalink / raw)
To: categories
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: functions not polynomials
@ 2007-03-22 5:56 Vaughan Pratt
0 siblings, 0 replies; 4+ messages in thread
From: Vaughan Pratt @ 2007-03-22 5:56 UTC (permalink / raw)
To: categories
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.
^ permalink raw reply [flat|nested] 4+ messages in thread
* functions not polynomials
@ 2007-03-21 16:39 Paul Taylor
0 siblings, 0 replies; 4+ messages in thread
From: Paul Taylor @ 2007-03-21 16:39 UTC (permalink / raw)
To: categories
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
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2007-03-29 3:47 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-03-29 3:47 functions not polynomials Vaughan Pratt
-- strict thread matches above, loose matches on Subject: below --
2007-03-26 19:26 Vaughan Pratt
2007-03-22 5:56 Vaughan Pratt
2007-03-21 16:39 Paul Taylor
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).