From: hagman on 5 Jun 2010 17:37 On 5 Jun., 15:30, hanrahan...(a)yahoo.co.uk wrote: > On Jun 5, 6:20 am, Stephen Montgomery-Smith > > <step...(a)math.missouri.edu> wrote: > > hanrahan...(a)yahoo.co.uk wrote: > > > On Jun 4, 4:12 pm, hanrahan...(a)yahoo.co.uk wrote: > > >> Does f(x,y) have to be a polynomial function of x and y, if for > > >> constant x it is a polynomial in y and for constant y it is a > > >> polynomial in x? I haven't been able to prove this. > > > > I should have specified: x and y are real, so is f(x,y), and the > > > function is a polynomial in y for EVERY constant x, and also in x for > > > EVERY constant y. > > > > Michael > > > I solved this problem many years ago. It isn't totally straightforward. > > You have to use the fact that the reals are uncountable. > > Hi Stephen. Thanks for this. I haven't yet worked out how the > uncountability of the reals can be used, but do you remember whether > the answer is yes or no to whether f(x,y) must be a polynomial? > > Michael yes. And the answer is "no" for a similar function Q x Q -> RR. Assume f: R x R -> R is a function such that for all x in R ,the function y |-> f(x,y) is a polynomial and for all y in R ,the function x |-> f(x,y) is a polynomial. If n in N let X_n := { x in R | deg( y |-> f(x,y) ) < n} and Y_n := { y in R | deg( x |-> f(x,y) ) < n}. Since U X_n = R, the X_n cannot all be finite. (This is where "uncountable" is used) And of course if X_n is infinite, so are all X_k with k>n. The same holds for the sets Y_n. Hence there exists n in N such that X_n and Y_n are infinite. Select an n-element subset A of X_n and an n-element subset B of Y_n. There exists a (unique) polynomial g(x,y) = sum_{i<n} sum {j<n} a_{i,j} x^i y^j that agrees with f for all (x,y) in A x B. For x in A, the functions y |-> g(x,y) and y |-> f(x,y) agree on at least n points (namely for y in B). Since both are polynomials of degree <n, they are the same. Thus for y in Y_n, the functions x |-> g(x,y) and x |-> f(x,y) agree on at least n points (namely for x in A). Since both are polynomials of degree <n, they are the same. Thus for x in R, the funtions y |-> g(x,y) and y |-> f(x,y) agree on infinitely many points (namely for y in Y_n). Since both are polynomials, they are the same. In total f(x,y) = g(x,y) for all (x,y) in R x R. Next I define a counterexample for the countable case: Let F: N -> R be a function that is not a polynomial, e.g. F(n) = 2^n. Define f: N x N -> R recursively as follows: On thediagonal, let f(n,n) := F(n). If n<m, let f(n,m) = p(m) where p is the unique polynomial of degree <n satisfying p(k) = f(k,m) for k in {0, ..., n-1} If n>m, let f(n,m) = p(n) where p is the unique polynomial of degree <m satisfying p(k) = f(n,k) for k in {0, ..., m-1} The resulting function f: N x N -> R has the following properties: For n in N, the function m |-> f(n,m) is a poylnomial of degree <n For m in N, the function n |-> f(n,m) is a poylnomial of degree <m f is not a polynomial becaus n |-> f(n,n) is not polynomial. The same construction is possible for Q x Q -> R using an enumeration of Q and again an arbitrary function on the diagonal. hagman
From: hagman on 6 Jun 2010 04:24 On 5 Jun., 23:37, hagman <goo...(a)von-eitzen.de> wrote: > On 5 Jun., 15:30, hanrahan...(a)yahoo.co.uk wrote: > > > > > On Jun 5, 6:20 am, Stephen Montgomery-Smith > > > <step...(a)math.missouri.edu> wrote: > > > hanrahan...(a)yahoo.co.uk wrote: > > > > On Jun 4, 4:12 pm, hanrahan...(a)yahoo.co.uk wrote: > > > >> Does f(x,y) have to be a polynomial function of x and y, if for > > > >> constant x it is a polynomial in y and for constant y it is a > > > >> polynomial in x? I haven't been able to prove this. > > > > > I should have specified: x and y are real, so is f(x,y), and the > > > > function is a polynomial in y for EVERY constant x, and also in x for > > > > EVERY constant y. > > > > > Michael > > > > I solved this problem many years ago. It isn't totally straightforward. > > > You have to use the fact that the reals are uncountable. > > > Hi Stephen. Thanks for this. I haven't yet worked out how the > > uncountability of the reals can be used, but do you remember whether > > the answer is yes or no to whether f(x,y) must be a polynomial? > > > Michael > > yes. And the answer is "no" for a similar function Q x Q -> RR. > > Assume f: R x R -> R is a function such that > for all x in R ,the function y |-> f(x,y) is a polynomial and > for all y in R ,the function x |-> f(x,y) is a polynomial. > > If n in N let > X_n := { x in R | deg( y |-> f(x,y) ) < n} and > Y_n := { y in R | deg( x |-> f(x,y) ) < n}. > Since U X_n = R, the X_n cannot all be finite. > (This is where "uncountable" is used) > And of course if X_n is infinite, so are all X_k with k>n. > The same holds for the sets Y_n. > Hence there exists n in N such that X_n and Y_n are infinite. > Select an n-element subset A of X_n and an n-element subset B of Y_n. > There exists a (unique) polynomial > g(x,y) = sum_{i<n} sum {j<n} a_{i,j} x^i y^j > that agrees with f for all (x,y) in A x B. > For x in A, the functions y |-> g(x,y) and y |-> f(x,y) agree > on at least n points (namely for y in B). > Since both are polynomials of degree <n, they are the same. > Thus for y in Y_n, the functions x |-> g(x,y) and x |-> f(x,y) agree > on at least n points (namely for x in A). > Since both are polynomials of degree <n, they are the same. > Thus for x in R, the funtions y |-> g(x,y) and y |-> f(x,y) agree > on infinitely many points (namely for y in Y_n). > Since both are polynomials, they are the same. > In total f(x,y) = g(x,y) for all (x,y) in R x R. > > Next I define a counterexample for the countable case: > Let F: N -> R be a function that is not a polynomial, e.g. F(n) = 2^n. > Define f: N x N -> R recursively as follows: > On thediagonal, let f(n,n) := F(n). > If n<m, let f(n,m) = p(m) where p is the unique polynomial of degree > <n > satisfying p(k) = f(k,m) for k in {0, ..., n-1} Oops, this should have been: If n<m, let f(n,m) = p(m) where p is the unique polynomial of degree <n satisfying p(k) = f(n,k) for k in {0, ..., n-1} > If n>m, let f(n,m) = p(n) where p is the unique polynomial of degree > <m > satisfying p(k) = f(n,k) for k in {0, ..., m-1} and here If n>m, let f(n,m) = p(n) where p is the unique polynomial of degree <m satisfying p(k) = f(k,m) for k in {0, ..., m-1} In other words: Once we have defined f(x,y) for the case min(x,y)<n, we define f(n,n) arbitrarily with the aim "non-polynomial" in mind and then define f(x,n) by a polynomial suiting the finitely many prescribed values at x=0, ..., n. Same for f(n,y) > The resulting function f: N x N -> R has the following properties: > For n in N, the function m |-> f(n,m) is a poylnomial of degree <n > For m in N, the function n |-> f(n,m) is a poylnomial of degree <m > f is not a polynomial becaus n |-> f(n,n) is not polynomial. > > The same construction is possible for Q x Q -> R using an enumeration > of Q > and again an arbitrary function on the diagonal. > > hagman
From: hanrahan398 on 23 Jun 2010 13:41 On Jun 6, 9:24 am, hagman <goo...(a)von-eitzen.de> wrote: > On 5 Jun., 23:37, hagman <goo...(a)von-eitzen.de> wrote: > > On 5 Jun., 15:30, hanrahan...(a)yahoo.co.uk wrote: > > > > On Jun 5, 6:20 am, Stephen Montgomery-Smith > > > > <step...(a)math.missouri.edu> wrote: > > > > hanrahan...(a)yahoo.co.uk wrote: > > > > > On Jun 4, 4:12 pm, hanrahan...(a)yahoo.co.uk wrote: > > > > >> Does f(x,y) have to be a polynomial function of x and y, if for > > > > >> constant x it is a polynomial in y and for constant y it is a > > > > >> polynomial in x? I haven't been able to prove this. Many thanks for this. I don't quite follow these three lines: > > There exists a (unique) polynomial > > g(x,y) = sum_{i<n} sum {j<n} a_{i,j} x^i y^j > > that agrees with f for all (x,y) in A x B. Why does such a polynomial exist? Many thanks! Michael
From: Dave L. Renfro on 4 Jul 2010 09:37 Michael wrote: >> Does f(x,y) have to be a polynomial function of x and y, if for >> constant x it is a polynomial in y and for constant y it is a >> polynomial in x? I haven't been able to prove this. Stephen Montgomery-Smith wrote: > I solved this problem many years ago. It isn't totally straightforward. > You have to use the fact that the reals are uncountable. If anyone is still interested in this, and for those who might later stumble on this thread through a search of the sci.math archives in the future, a solution is given by E. Grassmann (University of Calgary) in Canadian Mathematical Bulletin Volume 19, Number 2 (June 1976), pp. 252-253 (solution to Problem 238). The solution makes use of these two facts (that hopefully I've stated correctly -- I'm verbalizing a lot of math expressions): (1) There exists an integer m and an infinite subset E of the reals R such that the (m+1)'st difference operator with respect to x vanishes on R x E. (2) There exists an integer n and an infinite subset F of the reals R such that the (n+1)'st difference operator with respect to y vanishes on F x R. Reference is also made to the following paper: Stephen A. Andrea, "Algebraic addition theorems", Advances in Mathematics 13 (1974), 20-30. Dave L. Renfro
First
|
Prev
|
Pages: 1 2 Prev: Maximum of a function of one variable over a region Next: 2^q mod (p) calculation |