Re: Enumerating convex polygons in a square
Alex Selby wrote:
....
I make it that f(N) has leading term
f(N) ~= exp(b.N^(2/3))
....
Here is the derivation. Starting with the non-strictly-convex case
(where vertices can be 'inside' line segments), Robert's formula is that
f(N) is the coefficient of x^N.y^N in the bivariate Taylor expansion of
f(x,y) = the product of 1/(1-x^i.y^j) over (i,j) for which i>=0,
j>=0 and (i,j)!=(0,0).
So f(N) is at most the sum of the coefficients of x^i.y^j in f(x,y)
for which i+j=2N. And presumably it is at least (this sum)/(2N+1)
since the largest term is probably at i=j=N. That means for
asymptotics where we don't care about a factor of 2N, we may set x=y
and look at the coefficient of x^(2N) in g(x)=f(x,x).
We have that
g(x) = product over r>=1 of (1-x^r)^(-(r+1))
= sum over n>=0 of c_n.x^n (say)
I don't know if g has any modular properties (which would lead to an
exact formula), but in any case to get just the asymptotics of c_n
we can afford to be more rough.
We need to know that the asymptotics of c_n as n-->infinity is
related to the asymptotics of g(x) as x-->1- (x tending to 1 from
below along the real axis). The relationship is
c_n ~= min over x in (0,1) of g(x)/x^(n+1) as n-->infinity
and
g(x) ~= max over n of c_n.x^n as x-->1-
(though we won't use the second of these)
where ~= means "the logs are asymptotic, and there is a more
accurate relationship which we could get by being more careful".
The above formula for c_n comes from Cauchy's formula:
c_n = (1/2.pi.i)integral over a suitable contour of g(x)/x^(n+1)dx
and the fact that if we choose the contour to go through a
stationary point of the integrand, the contribution to the integral
will come almost entirely from near that point. (This is a standard
method.)
In our case, letting x=exp(-eps) (eps is short for epsilon, small
and positive), we get
log(c_n) ~= min over eps>0 of (sum over r>=1 of
-r.log(1-exp(-eps.r)))+n.eps
where we have replaced r+1 by r and n+1 by n because it won't matter.
Estimating the sum over r by an integral of h(x)=-x.log(1-exp(-x)):
sum over r>=1 of r.log(1-exp(-eps.r)) = Zeta(3).eps^(-2) +
O(eps^(-1)) as eps-->0
since h(x) is monotonic and tends to 0 as x-->0, x-->infinity, and
(integral from 0 to infinity of h(x)dx) = Zeta(3) (by expanding the
log as a series).
The minimum of Zeta(3).eps^(-2)+n.eps is attained at
eps=(2.Zeta(3)/n)^(1/3) and is equal to 3(Zeta(3).(n^2)/4)^(1/3).
Remembering n=2N, we get
f(N) ~= exp(c.N^(2/3)) where c=3.Zeta(3)^(1/3)
.. . .
This was for the non-strictly convex case (vertices can be in
edges). In the strictly convex case, Robert's formula is
f(x,y) = the product of 1/(1-x^i.y^j) over (i,j) for which i>=0,
j>=0 and gcd(i,j)=1.
This leads to
g(x) = product over r>=1 of (1-x^r)^(-phi(r))
where phi(r) = Euler's function = number of numbers <r which are
coprime to r (except that for these purposes phi(1)=2, but that
doesn't make any difference).
There is a sense in which phi(n) is equal to n/Zeta(2) on average.
A true statement, for example, is that
sum_{r<n}phi(r) = sum_{r<n}(r/Zeta(2)) + O(n.log(n))
Because h(x) is sufficiently well-behaved, you can check that it's
OK to replace (sum over r>=1 of -r.log(1-exp(-eps.r))) in the
above non-strictly-convex derivation with (sum over r>=1 of
-r/Zeta(2).log(1-exp(-eps.r))). The same minimisation process as
before will result in
f(N) ~= exp(b.N^(2/3)) where b=3.(Zeta(3)/Zeta(2))^(1/3)
---
Alex
.
Relevant Pages
- Re: factors of (x^n - 1)/(x - 1)
... negative coefficient. ... the sum of the roots of f equals the negative of the ...
(sci.math) - Re: Simplify infinite series with Sines???
... use a square wave as well and I'd get the same result too. ... it makes it easier to simplify; then using a saw/square wave for k=2 ... this that it is equal to a sum. ... the coefficient aof z^i in P is ...
(sci.math) - Re: A set of approximations the central binomial coefficient
... Your approximations are precise for small n, ... coefficient is assymptotically ... Taking derivatives, we find that Psihas only odd powers of m ... Up to some questions of interchanging asymptotics and sums, ...
(sci.math) - Re: Does any one recognize this series?
... The corresponding coefficient in mclaurin expansion of your ... I would appreciate if you could clarify how ... each term in the sum is squared, it is no longer familar to me. ... been the Maclaurin series for I_0, where I is the modified Bessel ...
(sci.math) - Multiplying two rows together
... What's the proper way to have in Cell Asuch that I sum each number in ... the row by the corresponding coefficient ...
(microsoft.public.excel.worksheet.functions) |
|
