From - Wed Jul 16 11:14:14 1997 From: elkies@ramanujan.math.harvard.edu (Noam Elkies) Newsgroups: sci.math.research Subject: Re: Generating function question Date: 15 Jul 1997 21:13:27 GMT Organization: Harvard Math Department Summary: Sorry, it's transcendental In article <5qdt5j$2tp@tierra.santafe.edu>, Cris Moore wrote: >Consider the generating function of the mod-2 Pascal's triangle, >with variables x and y indicating the position of each term: > 1 >+y +xy >+y^2 +x^2y^2 >+y^3 +xy^3 +x^2y^3 +x^3y^3 >+y^4 +x^4y^4 >... > >clearly this is algebraic in Z_2. Is it algebraic in Z? >This would be helpful to me in solving a statistical mechanics problem. It is not even algebraic in C(x,y). This function has the infinite product expansion (1+x+y)(1+x^2+y^2)(1+x^4+y^4)(1+x^8+y^8)(1+x^16+y^16)... in a neighborhood of (0,0), and thus by analytic continuation on its polydisc of convergence |x|<1, |y|<1. In particular, for n=0,1,2,... the function vanishes on the portion of the curve x^(2^n)+y^(2^n)+1=0 contained in that polydisc. But it is not possible for an algebraic function to vanish on infinitely many curves. --Noam D. Elkies (elkies@math.harvard:edu) Dept. of Mathematics, Harvard University From - Wed Jul 16 21:30:14 1997 From: Robin Chapman Newsgroups: sci.math.research Subject: Re: Generating function question Date: Tue, 15 Jul 1997 14:56:02 GMT Organization: University of Exeter Cris Moore wrote: > > Consider the generating function of the mod-2 Pascal's triangle, > with variables x and y indicating the position of each term: > > 1 > +y +xy > +y^2 +x^2y^2 > +y^3 +xy^3 +x^2y^3 +x^3y^3 > +y^4 +x^4y^4 > ... > > clearly this is algebraic in Z_2. Is it algebraic in Z? > This would be helpful to me in solving a statistical mechanics problem. > This has a nice infinite product, i.e., it's the product of 1 + y^(2^j) + (xy)^(2^j) over all integers j >= 0. It is not algebraic though. Calling this sum f(x, y), then g(y) = f(1, y) is the sum of 2^{d(m)} x^m where d(m) is the number of ones in the binary expansion of m. If f is algebraic, then g is too. But 2^{d(m)} <= m + 1 for all m , and so g is analytic in the open unit disc. But g(y) = (1 + 2y)(1 + 2y^2)(1 + 2y^4)... has infinitely many zeros in the open unit disc --- impossible for a rational function. -- Robin Chapman "256 256 256. Department of Mathematics O hel, ol rite; 256; whot's University of Exeter, EX4 4QE, UK 12 tyms 256? Bugird if I no. rjc@maths.exeter.ac.uk 2 dificult 2 work out." http://www.maths.ex.ac.uk/~rjc/rjc.html Iain M. Banks - Feersum Endjinn