Integral exp(x^2)
Ron Maimon
Prove this integral is not a closed form, and I will be happy
I tried, and I don't know how to do it.
Ron Maimon
Bernhard Muenzer
Integral exp(x^2) = -1/2 * sqrt(pi) * i * erf (i * x)
This still leaves the question whether erf qualifies for a closed form
simply because someone has given this function a name :-)
--
main(){char*c=" _.+=#\n)rezneuM drahnreB(ed.fsg@eum";int x,t,y;float a,
b,d;for(y=0;y<25;y++){for(x=0;x<81;x++){t=b=d=0;do{a=b*b-d*d-2.1+.035*x
;d=2*b*d+.088*y-1.1;b=a;t++;}while(t<32&&b*b+d*d<4);putchar(c[x>79?6:y>
23&&x<28?34-x:t>31?0:t>>4?5:t>>3?4:t>>2?3:t>>1?2:1]);}}} /*m...@gsf.de*/
Timothy Y. Chow
>In article <2cupmt$m...@scunix2.harvard.edu>, rma...@husc9.Harvard.EDU (Ron Maimon) writes:
>|
>| Prove this integral is not a closed form, and I will be happy
>|
>| I tried, and I don't know how to do it.
>|
>| Ron Maimon
>MathCad (invoking Maple) says:
>Integral exp(x^2) = -1/2 * sqrt(pi) * i * erf (i * x)
>This still leaves the question whether erf qualifies for a closed form
>simply because someone has given this function a name :-)
Newsgroups: sci.math
From: ste...@andy.bgsu.edu (Ray Steiner)
Subject: Re: Integrating squareroot(1 + cos^2 x)
Message-ID: <CEwEq...@andy.bgsu.edu>
Organization: Bowling Green State University B.G., Oh.
References: <29g8g6$a...@nwfocus.wa.com> <CEu72...@andy.bgsu.edu> <jfrancoe-1...@jfrancoeur.mitre.org>
Date: Thu, 14 Oct 1993 17:46:42 GMT
jfra...@mitre.org (Joe Francoeur) writes:
>> This is a standard elliptic integral of the second kind.
>> While there is no elementary antiderivative, the definite
>> integral can be looked up in any table of elliptic
>> integrals.
>While we're on the subject of elementary antiderivatives, how is it that
>one proves that integrands like exp(-x^2), et al, cannot have elementary
>antiderivatives? Is it related to group theory? Thanks.
>~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>Opinions expressed are solely mine.
>The MITRE Corporation
>202 Burlington Road, MS R355
>Bedford, MA 01730
Here is (again!) an old post of Matthew Wiener which explains
the relevant theory of Liouville for such problems.
Just a thought:
Shouldn't such questions be in the FAQ? They have been
asked and answered many times previously.
Ray Steiner
>From osu-eddie!cbosgd!clyde!burl!ulysses!ucbvax!brahms!weemba Sun Mar 9 03:16:18 1986
Relay-Version: version B 2.10.2 9/5/84; site bgsuvax.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU
Path: bgsuvax!osu-eddie!cbosgd!clyde!burl!ulysses!ucbvax!brahms!weemba
From: wee...@brahms.BERKELEY.EDU (Matthew P. Wiener)
Newsgroups: net.math
Subject: Integration by Elementary Functions
Message-ID: <12...@ucbvax.BERKELEY.EDU>
Date: 9 Mar 86 08:16:18 GMT
Date-Received: 12 Mar 86 15:51:54 GMT
References: <8...@drux2.UUCP> <3...@bgsuvax.UUCP> <1...@bgsuvax.UUCP>
Sender: use...@ucbvax.BERKELEY.EDU
Reply-To: wee...@brahms.UUCP (Matthew P. Wiener)
Organization: University of California, Berkeley
Lines: 255
>Thanks to all of you who answered my earlier query. Does anyone
>know how to prove that the integral of e**x*sec(x) is not
>expressible in terms of elementary functions?
We give a fairly complete sketch of the proof that certain functions,
including the asked for one, are not integrable in elementary terms. The
central theorem is due to Liouville in 1835. His proof was analytic. The
sketch below is mostly algebraic and is due to Maxwell Rosenlicht. See his
papers in the _Pacific Journal of Mathematics_, 54, (1968) 153-161 and 65,
(1976), 485-492.
WARNING: Prerequisites for understanding the proof is a first year graduate
course in algebra, and a little complex analysis. No deep results are used,
but I cannot take the time to explain standard notions or all the deductions.
Notation: a^n is "a power n", a_n is "a sub n". C is the complex numbers,
for fields F, F[x] is the ring of polynomials in x OR an algebraic extension
of F, F(x) is the field of rational functions in a transcendental x, M is
the field of meromorphic functions in one variable. If f is a complex
function, I(f) will denote an antiderivative of f.
A differential field is a field F of characteristic 0 with a derivation.
Thus, in addition to the field operations + and *, there is a derivative
mapping ':F->F such that (a+b)'=a'+b' and (ab)'=a'b+ab'. Two standard
examples are C(z) and M with the usual derivative map. Notice a basic
identity (logarithmic differentiation) holds:
[(a_1 ^ k_1) * ... * (a_n ^ k_n)]' a_1' a_n'
--------------------------------- = k_1 --- + ... + k_n ---
(a_1 ^ k_1) * ... * (a_n ^ k_n) a_1 a_n
The usual rules like the quotient rule also hold. If a in F satisfies
a'=0, we call a a constant of F. The set of constants of F is called
Con(F), and forms a subfield of F.
The basic idea in showing something has no elementary integral is to
reduce the problem to a sequence of differential fields F_0, F_1, etc.,
where F_0 = C(z), and F_(i+1) is obtained from F_i by adjoining one
new element t. t is obtained either algebraically, because t satisfies
some polynomial equation p(t)=0, or exponentially, because t'/t=s' for
some s in F_i, or logarithmically, because t'=s'/s is in F_i. Notice
that we don't actually take exponentials or logarithms, but only attach
abstract elements that have the appropriate derivatives. Thus a function
f is integrable in elementary terms iff such a sequence exists starting
with C(z).
Just so there is no confusion, there is no notion of "composition" involved
here. If you want to take log s, you adjoin a transcendental t with the
relation t'=s'/s. There is no log function running around, for example,
except as motivation, until we reach actual examples.
We need some easy lemmas. Throughout the lemmas F is a differential field,
and t is transcendental over F.
Lemma 1: If K is an algebraic extension field of F, then there exists a
unique way to extend the derivation map from F to K so as to make K into
a differential field.
Lemma 2: If K=F(t) is a differential field with derivation extending F's,
and t' is in F, then for any polynomial f(t) in F[t], f(t)' is a polynomial
in F[t] of the same degree (if the leading coefficient is not in Con(F))
or of degree one less (if the leading coefficient is in Con(F)).
Lemma 3: If K=F(t) is a differential field with derivation extending F's,
and t'/t is in F, then for any a in F, n a positive integer, there exists
h in F such that (a*t^n)'=h*t^n. More generally, if f(t) is any polynomial
in F[t], then f(t)' is of the same degree as f(t), and is a multiple of
f(t) iff f(t) is a monomial.
These are all fairly elementary. For example, (a*t^n)'=(a'+at'/t)*t^n
in lemma 3. The final 'iff' in lemma 3 is where transcendence of t comes
in. Lemma 1 in the usual case of subfields of M can be proven analytically
using the implicit function theorem.
--------------------------------------------------------------------------
MAIN THEOREM. Let F,G be differential fields, let a be in F, let y be in G,
and suppose y'=a and G is an elementary differential extension field of F,
and Con(F)=Con(G). Then there exist c_1,...,c_n in Con(F), u_1,...,u_n, v
in F such that
u_1' u_n'
a = c_1 --- + ... + c_n --- + v'.
u_1 u_n
In other words, the only functions that have elementary anti-derivatives
are the ones that have this very specific form.
This is a very useful theorem for proving non-integrability. In the usual
case, F,G are subfields of M, so Con(F)=Con(G)=C always holds.
Proof:
By assumption there exists a finite chain of fields connecting F to G
such that the extension from one field to the next is given by performing
an algebraic, logarithmic, or exponential extension. We show that if the
form (*) can be satisfied with values in F2, and F2 is one of the three
kinds of allowable extensions of F1, then the form (*) can be satisfied
in F1. The form (*) is obviously satisfied in G: let all the c's be 0, the
u's be 1, and let v be the original y for which y'=a. Thus, if the form
(*) can be pulled down one field, we will be able to pull it down to F,
and the theorem holds.
So we may assume without loss of generality that G=F(t).
Case 1: t is algebraic over F. Say t is of degree k. Then there are
polynomials U_i and V such that U_i(t)=u_i and V(t)=v. So we have
U_1(t)' U_n(t)'
a = c_1 ------ + ... + c_n ------ + V(t)'.
U_1(t) U_n(t)
Now, by the uniqueness of extensions of derivatives in the algebraic case,
we may replace t by any of its conjugates t_1,..., t_k, and the same equation
holds. In other words, because a is in F, it is fixed under the Galois
automorphisms. Summing up over the conjugates, and converting the U'/U
terms into products using logarithmic differentiation, we have
[U_1(t_1)*...*U_1(t_k)]'
k a = c_1 ----------------------- + ... + [V(t_1)+...+V(t_k)]'.
U_1(t_1)*...*U_n(t_k)
But the expressions in [...] are symmetric polynomials in t_i, and as
they are polynomials with coefficients in F, the resulting expressions
are in F. So dividing by k gives us (*) holding in F.
Case 2: t is logarithmic over F. Because of logarithmic differentiation
we may assume that the u's are monic and irreducible in t and distinct.
Furthermore, we may assume v has been decomposed into partial fractions.
The fractions can only be of the form f/g^j, where deg(f)<def(g) and g
is monic irreducible. The fact that no terms outside of F appear on the
left hand side of (*), namely just a appears, means a lot of cancellation
must be occuring.
Let t'=s'/s, for some s in F. If f(t) is monic in F[t], then f(t)' is also
in F[t], of one less degree. Thus f(t) does not divide f(t)'. In particular,
all the u'/u terms are in lowest terms already. In the f/g^j terms in v,
we have a g^(j+1) denominator contribution in v' of the form -jfg'/g^(j+1).
But g doesn't divide fg', so no cancellation occurs. But no u'/u term can
cancel, as the u's are irreducible, and no (xx)/g^(j+1) term appears in
a, because a is a member of F. Thus no f/g^j term occurs at all in v. But
then none of the u's can be outside of F, since nothing can cancel them.
(Remember the u's are distinct, monic, and irreducible.) Thus each of the
u's is in F already, and v is a polynomial. But v' = a - expression in u's,
so v' is in F also. Thus v = b t + c for some b in con(F), c in F, by lemma
2. Then
u_1' u_n' s'
a = c_1 --- + ... + c_n --- + b --- + c'
u_1 u_n s
is the desired form. So case 2 holds.
Case 3: t is exponential over F. So let t'/t=s' for some s in F. As in
case 2 above, we may assume all the u's are monic, irreducible, and distinct
and put v in partial fraction decomposition form. Indeed the argument is
identical as in case 2 until we try to conclude what form v is. Here lemma
3 tells us that v is a finite sum of terms b*t^j where each coefficient is
in F. Each of the u's is also in F, with the possible exception that one
of them may be t. Thus every u'/u term is in F, so again we conclude v'
is in F. By lemma 3, v is in F. So if every u is in F, a is in the desired
form. Otherwise, one of the u's, say u_n, is actually t, then
u_1'
a = c_1 --- + ... + (c_n s + v)'
u_1
is the desired form. So case 3 holds.
------------------------------------------------------------------QED------
This proof, by the way, is a LOT easier than it looks. Just work out some
examples, and you'll see what's going on. (If this were a real expository
paper, such examples would be provided. Maybe it's better this way. Indeed,
if anybody out there takes the time to work some out and post them, I would
be much obliged.)
So how to you actually go about using this theorem? Suppose you want to
integrate f*exp(g) for f,g in C(z), g non zero. [This isn't yet the asked
for problem.] Let t=exp(g), so t'/t=g'. Let F=C(z)(t), G=any differential
extension field containing an antiderivative of f*t. [Note that t is in
fact transcendental over C(z): g is rational and non-zero, so it has a
pole (possibly at infinity) and so t has an essential singularity and can't
be algebraic over C(z).] Is G an elementary extension? If so, then
u_1' u_n'
f*t = c_1 --- + ... + c_n --- + v'
u_1 u_n
where the c_i, u_i, and v are in F. Now the left hand side can be viewed
as a polynomial in C(z)[t] with exactly one term. We must identify the
coefficient of t in the right hand side and get an equation for f. But
the first n terms can be factored until the u_i's are linear (using the
logarithmic differentiation identity to preserve the abstract from). As
for the v' term, long divide and use partial fractions to conclude v is a
sum of monomials: if v had a linear denominator other than t, raised to
some power in its partial fraction decomposition, its derivative would be
one higher power, and so cannot be cancelled with anything from the u_i
terms. (As in the proof.) If w is the coefficient of t in v, we have
f=w'+wg' with w in C(z). Solving this first order ODE, we find that
w=exp(-g)*I(f*exp(g)). In other words, if an elementary antiderivative
can be found for f*exp(g), where f,g are rational functions, then it is of
the form w*exp(g) for some rational function w. [Notice that the conclusion
would fail for g equal to 0!]
For example, consider f=1 and g=-z^2. Now exp(z^2)*I(exp(-z^2)) has no
poles (except perhaps at infinity), so if it is a rational function, it
must be a polynomial. So let (p(z)*exp(-z^2))'=exp(-z^2). One quickly
verifies that p'-2zp=1. But the only solution to that ODE is the error
function I(exp(-z^2)) itself (within an additive constant somewhere)!
And the error function is NOT a polynomial! (Proof? OK, for one thing,
its Taylor series obtained by termwise integration is infinite. For
another, its derivative is an exponential.)
As an exercise, prove that I(exp(z)/z) is not elementary. Conclude that
neither is I(exp(exp(z))) and I(1/log(z)).
For a slightly harder exercise, prove that I(sin(z)/z) is not elementary.
Conclude that neither is I(sin(exp(z))).
Finally, we settle the case I(exp(z)*sec(z)).
We let s=exp(iz) and t=exp(z). We have
2 t u_1' u_n'
------- = c_1 --- + ... + c_n --- + v'
s + 1/s u_1 u_n
where the u's and v are in C(z,s,t). By reasoning as in the application
above, we equate t coefficients and get
2
------- = w' + w,
s + 1/s
where w is in C(z,s). [To see that t is transcendental over C(z,s), it
suffices to show p(cos(z)) is not rational in z and exp(z) for any non-
trivial polynomial p. But p(cos(z)) oscillates as z approaches infinity
along the real line, whereas any member of C(z,t) approaches a definite,
possibly infinite, limit at infinity along the real line.]
To see that this is impossible, expand w as a Laurent series in C(z)(s).
That is, express w as a sum of terms w_j*s^j, where j ranges through the
integers, and w_j is in C(z). But 2/(s+1/s)=2*s/(1+s^2)=2-2*s^3+2*s^5-....
So we can equate coefficients. In particular, we get the differential
equations w_j'+(1+i*n)*w_j=0 or 2 or -2. But such ODE's don't have
rational function solutions!
---------------------------------------------------------------------------
Liouville's theorem can be generalized. For example, I(J_0) is not
expressible using elementary functions and any of the Bessel functions.
The hard part is finding the appropriate normal form. See Watson _A
Treatise on Bessel Functions_.
In G H Hardy _The Integration of Functions in Finite Terms_ the question
of how useful Liouville's theorem in finding antiderivatives was studied.
The general decision problem raised some subtle algebraic geometry questions
which were not settled until 1970 by R Risch, based on earlier work of J F
Ritt. See J H Davenport _On the Integration of Algebraic Functions_ for a
discussion and further references.
ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720
From galois!bloom-beacon.mit.edu!uhog.mit.edu!wupost!howland.reston.ans.net!news.moneng.mei.com!uwm.edu!rpi!batcomputer!cornell!gries Fri Oct 22 17:07:51 EDT 1993
Article: 38965 of sci.math
Xref: galois comp.edu:4223 comp.theory:5824 sci.logic:4516 sci.math:38965 sci.edu:2939 misc.books.technical:3199
Newsgroups: comp.edu,comp.theory,sci.logic,sci.math,sci.edu,misc.books.technical
Path: galois!bloom-beacon.mit.edu!uhog.mit.edu!wupost!howland.reston.ans.net!news.moneng.mei.com!uwm.edu!rpi!batcomputer!cornell!gries
From: gr...@cs.cornell.edu (David Gries)
Subject: New discrete-math text
Message-ID: <1993Oct22....@cs.cornell.edu>
Summary: Announcing a new book that is oriented towards teaching logic as a tool
Keywords: Logic, Gries, Schneider, discrete
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Fri, 22 Oct 1993 18:32:26 GMT
Lines: 75
Status: RO
A Discrete-Math Text With A New Approach
David Gries and Fred B. Schneider
Our new text "A Logical Approach to Discrete Math" (Springer-Verlag,
1993, ISBN 0-387-94115-0) seems to have generated enough interest that
it makes sense to broadcast a message about it.
The text is targetted for the traditional introductory discrete
mathematics course. It is different, however, because it teaches
logic as a useful tool, using an equational logic, and then uses logic
pervasively in the other topics of the course ---set theory,
induction, relations, functions, a theory of integers, a theory of
sequences, combinatorics, solving recurrence relations, modern
algebra, and graph theory.
This new approach gives students a real skill in proof and the use of
formalism. This comes partly from allocating 5-6 weeks to logic,
rather than the typical 1.5 weeks, partly from the equational logic
that we teach, and partly from our view of logic as a tool rather than
an object of study. The skill students get makes teaching the other
topics more effective and efficient.
We are particularly excited about the approach because undergrads seem
to like it. The following comments are representative of the 65
positive evaluations (for a class of 70) we received last spring from
our course at Cornell that used this text.
I am a math major who never though I would enjoy doing
proofs, until taking this course.
This class dissolved my fear of proving things.
Before, anything written in math syntax intimidated me. Now I
have a much better understanding ... Proof methods learned
in this class have helped me in other courses.
This course taught me the most about how to think logically in
all the many courses I have taken in my Cornell career.
A 300-page intructor's manual can be obtained directly from us (for
$20, made payable to Gries, to cover our costs). The first part of
the manual contains essays that explain the approach and contrasts it
with other approaches in use today. This part is a real help to those
who are more oriented to logic as an object of study rather than as a
real tool. The second part of the instructor's manual contains hints
on teaching the material in each of the chapters of the text. The
third part contains answers to the over-900 exercises.
Because the approach is so different, we are giving day-long tutorials
on it at the SEI Software Engineering Conference in San Antonio in
January and at the SIGCSE conference in Phoenix in March.
If you are seriously interested in using the text in the course,
contact Springer-Verlag's Editor for Computer Science, Martin
Gilchrist, for a complimentary copy.
Martin Gilchrist gilc...@sccm.Stanford.edu
Suite 200, 3600 Pruneridge Ave. (408) 249-9314
Santa Clara, CA 95051
If you are interested in the text but won't be teaching a course,
we understand that Springer-Verlag sells the book, too.
David Gries and Fred B. Schneider
From galois!bloom-beacon.mit.edu!gatech!howland.reston.ans.net!pipex!uknet!mcsun!sun4nl!cwi.nl!pmontgom Wed Nov 3 23:18:00 EST 1993
Article: 40101 of sci.math
Newsgroups: sci.math
Path: galois!bloom-beacon.mit.edu!gatech!howland.reston.ans.net!pipex!uknet!mcsun!sun4nl!cwi.nl!pmontgom
From: pmon...@cwi.nl (Peter L. Montgomery)
Subject: Re: How to proof about Fibonacci..
Message-ID: <CFxLG...@cwi.nl>
Sender: ne...@cwi.nl (The Daily Dross)
Nntp-Posting-Host: gier.cwi.nl
Organization: CWI, Amsterdam
References: <1993Nov3.1...@ousrvr.oulu.fi>
Date: Wed, 3 Nov 1993 19:43:28 GMT
Lines: 64
Status: O
In article <1993Nov3.1...@ousrvr.oulu.fi> ktik...@phoenix.oulu.fi
(Kari Tikkanen) writes:
>You have Fibonacci sequence 1,1,2,3,5,8,13,... (mark. F(1),F(2),F(3),...)
> F(n+1)=F(n)+F(n-1).
>How to proof that there always exist n so that prime p divides F(n) for
>every prime p ?
>(For example 11 divides F(10)=55.)
It is convenient to define F(0) = 0.
The recurrence F(n+1) = F(n) + F(n-1) still holds for all n >= 1.
Let N denote the nonnegative integers.
Let p be a positive integer, not necessarily prime.
Define g : N -> [0, p-1] x [0, p-1] by
g(n) = (F(n) mod p, F(n+1) mod p)
(ordered pair of two remainders). There are only p^2 possible images.
By the Pigeonhole principle. some image is repeated:
there exist n1 and n2 in N with g(n1) = g(n2) and n1 < n2.
By the well-ordering principle, we may assume n1 is chosen
as small as possible (i.e., choose the smallest nonnegative n1
such that there exists n2 > n1 with g(n1) = g(n2)). This means
(F(n1) mod p) = (F(n2) mod p)
and (F(n1+1) mod p) = (F(n2+1) mod p).
That is, both F(n2) - F(n1) are F(n2+1) - F(n1+1) are divisible by p.
If n1 = 0, then F(n2) - F(n1) = F(n2) - F(0) = F(n2)
is a multiple of p and n2 > 0, so the statement is proved.
If n1 > 0, then use the identities
F(n1+1) = F(n1) + F(n1-1)
F(n2+1) = F(n2) + F(n2-1)
to show that F(n2-1) - F(n1-1) = (F(n2+1) - F(n1+1)) - (F(n2) - F(n1))
is a multiple of p. Hence (F(n1-1) mod p) = (F(n2-1) mod p).
Also n1 - 1 >= 0 since we are assuming n1 >= 1.
Therefore g(n1-1) = g(n2-1) and n2 - 1 > n1 - 1. This contradicts
the assumption that n1 is minimal.
COMMENT: We have actually shown that there exists an n > 0
such that F(n) == 0 mod p and F(n+1) == 1 mod p.
It is now straightforward to show that the Fibonacci sequence
is periodic modulo any prime.
COMMENT. When p is prime, we can use its last digit to get
information about the least positive n such that F(n) is divisible by p:
Last digit 1: n divides p-1 (e.g., 11 divides F(10) = 55)
Last digit 2: n = 3 (since p = 2)
Last digit 3: n divides p+1 (e.g., 13 divides F(7) = 13)
Last digit 5: n = 5 (since p = 5)
Last digit 7: n divides p+1 (e.g., 17 divides F(9) = 34)
Last digit 9: n divides p-1 (e.g., 19 divides F(18) = 2584)
In particular, n <= p + 1 if p is prime.
EXERCISE: Find a composite number p for which the least n exceeds p+1.
--
Peter L. Montgomery pmon...@cwi.nl
From galois!bloom-beacon.mit.edu!gatech!howland.reston.ans.net!math.ohio-state.edu!cyber2.cyberstore.ca!nntp.cs.ubc.ca!unixg.ubc.ca!not-for-mail Wed Nov 3 23:33:06 EST 1993
Article: 40140 of sci.math
Path: galois!bloom-beacon.mit.edu!gatech!howland.reston.ans.net!math.ohio-state.edu!cyber2.cyberstore.ca!nntp.cs.ubc.ca!unixg.ubc.ca!not-for-mail
From: isr...@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: Packing disks in a square
Date: 4 Nov 1993 02:09:28 GMT
Organization: The University of British Columbia
Lines: 58
Distribution: world
Message-ID: <2b9o8o$o...@nntp.ucs.ubc.ca>
References: <CFxJ7...@umassd.edu>
Reply-To: isr...@math.ubc.ca
NNTP-Posting-Host: fourier.math.ubc.ca
Status: RO
In article <CFxJ7...@umassd.edu> rud...@cis.umassd.edu (Lee Rudolph) writes:
> In fact, let F_1, F_2, ... be a sequence of non-empty compact sets in
> the plane, such that each F_i is the closure of its interior (for
> instance--for the original question--each F_i could be the unit disk).
> Denote the closed unit square by Q. Then there is a sequence G_1, G_2,...
> of subsets of Q such that (1) G_i is similar to F_i (in fact, a translate
> of a homothetic image of F_i), (2) for i not equal to j the interiors of
> G_i and G_j are disjoint, and (3) the union of the G_i contains
> the interior of Q. Proof: let P_1, P_2,... be a sequence of points
> interior to Q which are dense in Q. Let G_1 be any subset of Q similar
> to F_1 containing P_1 in its interior.
> If G_1,...,G_N satisfy (1) and (2), then their
> union is compact, and if it doesn't already cover the interior of Q,
> there is a least index M such that P_M isn't in it and therefore is
> some non-zero distance from it; so there's no difficulty in finding
> G_{N+1} such that G_1,...,G_{N+1} satisfy (1) and (2) and the union of
> their interiors contains P_1,...,P_M. The sequence G_1, G_2, ... so
> constructed satisfies (1), (2) and (3), QED.
Whoa there! All you know is that the union of the G_i contains the sequence
(P_j) and is therefore dense. I could go through your method taking G_j
of area < epsilon * 2^(-j) and end up with a set of measure < epsilon.
In fact, if the F_i are convex with no line segments in their boundaries,
you can never get all of the interior of Q. Sketch of proof: inductively
find a nested sequence of compact sets C_i such that C_i is the closure of its
interior, is disjoint from G_i, and is not contained in any single G_j
(which will be true if it is very close to the boundary of some G_k
and its diameter is not too small). The intersection of all C_i is
disjoint from all G_i. In fact, you can use this method to show that
the complement of the union of the G_i is a perfect set.
With all F_i = F, you can get a packing of full measure, by the following
inductive procedure. At stage N we will have chosen a finite number of
sets G_1, ..., G_M, and R_N = Q \ (G_1 union ... G_M) is the region
remaining. You can find a sequence of disjoint open squares (S_j) whose union
is almost all of R_N. There is some c > 0 such that a square of side 1
contains a set similar to F with area c. By taking such a set in each
square, you would get at least a fraction c of the area of R_N. A finite
number of these will cover at least a fraction c/2 of the area. Thus we
will have area(R_(N+1)) <= (1 - c/2) area(R_N), so area(R_N) -> 0 as
N -> infinity.
If the F_i can be different, there are cases
where you can't get all the area. For example, suppose each F_i is shaped
like two equal hollow unit squares, one on top of the other (a figure "8"),
with finite thickness going to 0 as i -> infinity, say area(F_i) < f(i).
If h_i is the width of G_i, the union of the G_i has area at most
sum_i f(i) h_i^2. But since the "holes" of the G_i with width between 2^(-k)
and 2^(1-k) are disjoint, sum {h_i^2: 2^(-k) <= h_i < 2^(1-k)} <= 1/2 and
sum_i f(i) h_i^2 <= 1/2 sum_k sup{ f(i): 2^(-k) <= h_i < 2^(1-k) }
<= 1/2 sum_i f(i) (since each f(i) is the sup at most once)
and this can be made arbitrarily small by appropriate choice of f.
--
Robert Israel isr...@math.ubc.ca
Department of Mathematics
University of British Columbia
Vancouver, BC, Canada V6T 1Y4
From galois!bloom-beacon.mit.edu!usc!elroy.jpl.nasa.gov!decwrl!concert!lester.appstate.edu!cs.cs.appstate.edu!tga Wed Nov 3 23:41:44 EST 1993
Article: 40145 of sci.math
Path: galois!bloom-beacon.mit.edu!usc!elroy.jpl.nasa.gov!decwrl!concert!lester.appstate.edu!cs.cs.appstate.edu!tga
From: t...@cs.cs.appstate.edu (Terry Anderson)
Newsgroups: sci.math
Subject: >Recurrence Relation Problem
Date: 4 Nov 1993 03:39:41 GMT
Organization: Appalachian State University
Lines: 67
Message-ID: <2b9tht$g...@lester.appstate.edu>
NNTP-Posting-Host: cs.cs.appstate.edu
Summary: Connection between nonlinear difference eqns and series
Keywords: nonlinear difference equations, series convergence
Status: O
KRAMER BRIAN M (kram...@cs.uidaho.edu) wrote:
: Does anyone know how to derive the closed form of:
: -1
: f = f + f
: n+1 n n
: Or for that matter, RRs with negative powers in general.
: Somebody in the UK helped on this problem. I lost the mail, but I remember
: what you've said.
This recurrence is discussed in the _American Mathematical Monthly_,
problem E 1994 [1967, 591], p. 903, October 1968. The problem is:
"Let { a[n] } be a sequence of positive real numbers. Put
f[1] = 1
and
f[n+1] = f[n] + a[n] / f[n], n >= 1.
Prove that as n -> oo, limit( f[n] ) exists iff
sum( a[n], n = 1..oo ) is finite."
The solution given proves that
S <= L ( L - 1 ),
where L = limit( f[n], n = oo ) and S = sum( a[n], n = 1..oo ), and
L <= 1 + S.
In your situation, a[n] = 1 so that S = oo and hence L = oo (from
the first inequality above). For what sequences a[n] can we explicitly
find L and a closed form solution for f[n] ? If a[n] = 1/n^3, then
S = Zeta(3) = 1.2020569... and L = 2.0996241... Can the above bounds
on S be made sharper?
For more on nonlinear difference equations, some good reference
books are
_Modern Nonlinear Equations_ by Thomas L. Saaty (Ch. 4) (Dover Pub.)
and
_Theory of Difference Eqns: Numerical Methods & Applications_
by V. Lakshmikantham & D. Trigiante.
(QA 431 .L28 1988).
For some fascinating reading on the difference eqn
z[n+1] = a z[n] + b z[n] / | z[n] |,
where a and b are complex numbers and | . | is complex modulus, check
out the new book
_Spirals: From Theodorus to Chaos_ by Philip J. Davis,
with contributions by Walter Gautschi & Arieh Iserles
(QA 567 .D38 1993) A.K. Peters Pub., ISBN 1-56881-010
Please post or send what you've learned about the difference eqn
f[n+1] = f[n] + 1 / f[n].
Regards,
--
Terry Anderson t...@math.appstate.edu
Math Sciences Dept. Appalachian State University
Boone, NC 28608 USA (704) 262 - 2357
t...@flyer.ncsc.org t...@cardinal.ncsc.org
--
Terry Anderson t...@math.appstate.edu
Math Sciences Dept. Appalachian State University
Boone, NC 28608 USA (704) 262 - 2357
t...@flyer.ncsc.org t...@cardinal.ncsc.org
From galois!bloom-beacon.mit.edu!news.kei.com!ub!penny!mary!kwong Fri Nov 5 14:57:46 EST 1993
Article: 40273 of sci.math
Newsgroups: sci.math
Path: galois!bloom-beacon.mit.edu!news.kei.com!ub!penny!mary!kwong
From: kw...@mary.cs.fredonia.edu (Harris Kwong)
Subject: Re: Fibonacci mod p periodic
Message-ID: <1993Nov5.1...@penny.cs.fredonia.edu>
Sender: ne...@penny.cs.fredonia.edu (News Administrator)
Organization: Math / CS, State Univ. of N. Y. College at Fredonia
X-Newsreader: TIN [version 1.2 PL1]
References: <1993Nov3.1...@ousrvr.oulu.fi> <2bc6ns$s...@news.u.washington.edu> <2bci4h$a...@cat.cis.Brown.EDU>
Date: Fri, 5 Nov 1993 14:27:42 GMT
Lines: 41
Status: O
Jay Blumenstein (ST10...@brownvm.brown.edu) wrote:
: To show that we can find n such that p|F(n) we can also note that the
: Fibonacci series mod p must be periodic; we can also prove that it must
: repeat at 1,1 again; hence the entry before the second appearance of 1,1
: must have been a 0 mod p, hence the result.
: Another interesting question is, how does the period and p relate?
: Jay Blumenstein
The problem, and its extension to various generalizations, have indeed
been extensively studied. The earliest paper is probably [1]. The
period modulo n, denoted u(n), is the LCM of the periods modulo the
prime powers that exactly divide n. Periods modulo specific prime
powers are known. For example [2], u(2^e) = 3 2^e and u(5^e) = 5 4^e.
But the problem remains unsolved in general.
If p \equiv 1,4 (mod 5), it can be shown that u(p) is the LCM of the
orders of (1+\sqrt{5})/2 and (1-\sqrt{5})/2 modulo p, and is a divisor
of p-1. If p \equiv 2,3 (mod 5), Vince [3] showed that u(p) is the
order of (1+\sqrt{5})/2 modulo p, and is a divisor of 2(p+1).
It is known that if u(p) \ne u(p^2), then u(p^e) = u(p) p^{e-1}.
However, it is still unknown whether u(p) = u(p^2) for some p. One
condition is known [3]: if c and p are relatively prime and cp occurs
in the Fibonacci sequence, then u(p) \ne u(p^2).
[1] D.D. Wall, Fibonacci series modulo m, Amer. Math. Monthly 67
(1960), 525--532.
[2] J. Kramer and V. E. Hoggatt, Jr., Special cases of Fibonacci
periodicity, Fibonacci Quarterly 10 (1972), 519--530.
[3] S. E. Mamangakis, Remarks on the Fibonacci series modulo m, Amer.
Math. Montly 68 (1961), 648--649.
--
Harris Kwong
Dept. of Math. & Comp. Sci.
SUNY College at Fredonia
Fredonia, NY 14063
E-mail: kw...@cs.fredonia.edu
From galois!bloom-beacon.mit.edu!news.kei.com!eff!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!math.ohio-state.edu!cyber2.cyberstore.ca!nntp.cs.ubc.ca!unixg.ubc.ca!not-for-mail Sun Nov 21 15:09:48 EST 1993
Article: 41410 of sci.math
Path: galois!bloom-beacon.mit.edu!news.kei.com!eff!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!math.ohio-state.edu!cyber2.cyberstore.ca!nntp.cs.ubc.ca!unixg.ubc.ca!not-for-mail
From: isr...@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: Problem: Doorcodes
Date: 19 Nov 1993 19:29:56 GMT
Organization: The University of British Columbia
Lines: 40
Distribution: world
Message-ID: <2cj6rk$5...@nntp.ucs.ubc.ca>
References: <HANCHE.93N...@chanur.imf.unit.no>
Reply-To: isr...@math.ubc.ca
NNTP-Posting-Host: descartes.math.ubc.ca
In article <HANCHE.93N...@chanur.imf.unit.no> han...@imf.unit.no (Harald
Hanche-Olsen) writes:
> This is a classic example of the use of graph theory. Create a
> directed graph whose nodes are all three digit combinations (1000 of
> them). For any four digit sequence A-B-C-D there is a corresponding
> edge from the node A-B-C to B-C-D. You need to traverse all edges of
> the graph. Since the graph is connected and every node in the graph
> has the same in degree as out degree, a closed path exists which
> traverses every path exactly once. Thus you need only 10003 key
> presses (three to get started (define the initial node), then 10000 to
> traverse the edges).
>
> As to a pattern to follow, well, the usual proof of the existence
> theorem does not yield any pattern. Your best bet is probably to
> precompute a solution and bring a printout.
Actually it does provide a method of finding a pattern.
Start from any three-digit combination and delete edges as you traverse
them. Suppose you started at x and you are now at y, and G is the graph you
now have. Then all nodes except x and y still have the same out-degree as
in-degree, while (if x is not y) x has one more in than out and y the reverse.
If you added an edge from x to y you would again have a graph (G') where every
node has the same in-degree as out-degree. If G' is connected, then by the
theorem it is possible to traverse every edge once in a closed path, and thus
to go from y to x traversing every edge except the added x -> y once. On the
other hand, in a graph that is not connected (except for isolated nodes) you
obviously can't traverse all the edges. So the theorem guarantees us that
there is an edge y -> z such that the graph obtained from G by deleting y -> z
and adding x -> z is connected except for isolated nodes. By choosing such an
edge for your next step at each stage, you construct the required tour.
e.g. (to make a smaller example) with binary digits, you can get all possible
4-tuples as follows: 0000100111101011000
--
Robert Israel isr...@math.ubc.ca
Department of Mathematics
University of British Columbia
Vancouver, BC, Canada V6T 1Y4
From galois!bloom-beacon.mit.edu!gatech!howland.reston.ans.net!agate!library.ucla.edu!news.mic.ucla.edu!unixg.ubc.ca!not-for-mail Mon Nov 22 16:11:41 EST 1993
Article: 41555 of sci.math
Path: galois!bloom-beacon.mit.edu!gatech!howland.reston.ans.net!agate!library.ucla.edu!news.mic.ucla.edu!unixg.ubc.ca!not-for-mail
From: isr...@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: Problem: Doorcodes
Date: 22 Nov 1993 18:37:14 GMT
Organization: The University of British Columbia
Lines: 36
Distribution: world
Message-ID: <2cr0sq$i...@nntp.ucs.ubc.ca>
References: <2cj6rk$5...@nntp.ucs.ubc.ca>
Reply-To: isr...@math.ubc.ca
NNTP-Posting-Host: descartes.math.ubc.ca
In article <2cj6rk$5...@nntp.ucs.ubc.ca> isr...@math.ubc.ca (Robert Israel)
writes:
> In article <HANCHE.93N...@chanur.imf.unit.no> han...@imf.unit.no
(Harald
> Hanche-Olsen) writes:
> > This is a classic example of the use of graph theory. Create a
> > directed graph whose nodes are all three digit combinations (1000 of
> > them). For any four digit sequence A-B-C-D there is a corresponding
> > edge from the node A-B-C to B-C-D. You need to traverse all edges of
> > the graph. Since the graph is connected and every node in the graph
> > has the same in degree as out degree, a closed path exists which
> > traverses every path exactly once. Thus you need only 10003 key
> > presses (three to get started (define the initial node), then 10000 to
> > traverse the edges).
> >
> > As to a pattern to follow, well, the usual proof of the existence
> > theorem does not yield any pattern. Your best bet is probably to
> > precompute a solution and bring a printout.
>
> Actually it does provide a method of finding a pattern.
You can traverse the edges of this graph with a very simple algorithm:
start with (000), and when the last three digits are (ABC) take the next
digit to be the largest digit D such that (ABCD) has not yet appeared.
Harald might not count this as a "pattern", however, since it requires
remembering which 4-digit combinations have appeared, or at least
for every 3-tuple (ABC) the largest D such that (ABCD) has not appeared.
With d possible digits this is d^3 log_2(d) bits of information. This
suggests an interesting question: Is there an algorithm that, given d,
traverses the edges and uses less memory (say, O(d) bits)?
--
Robert Israel isr...@math.ubc.ca
Department of Mathematics
University of British Columbia
Vancouver, BC, Canada V6T 1Y4
From galois!bloom-beacon.mit.edu!usc!howland.reston.ans.net!pipex!sunic!news.funet.fi!nntp.hut.fi!nntp!lounesto Wed Nov 24 11:29:05 EST 1993
Article: 41747 of sci.math
Path: galois!bloom-beacon.mit.edu!usc!howland.reston.ans.net!pipex!sunic!news.funet.fi!nntp.hut.fi!nntp!lounesto
From: loun...@dopey.hut.fi (Pertti Lounesto)
Newsgroups: sci.math
Subject: Re: MvS erred (along with Princeton, Oxford, Cambridge)
Date: 24 Nov 1993 08:32:01 GMT
Organization: Helsinki University of Technology
Lines: 65
Distribution: world
Message-ID: <LOUNESTO.93...@dopey.hut.fi>
References: <1993Nov23.1...@cc.gatech.edu>
<1993Nov23.1...@tjhsst.vak12ed.edu>
<1993Nov23....@galois.mit.edu>
NNTP-Posting-Host: dopey.hut.fi
In-reply-to: tyc...@kronecker.mit.edu's message of Tue, 23 Nov 93 19:21:07 GMT
tyc...@kronecker.mit.edu (Timothy Y. Chow) writes:
> I have yet to meet someone who unwittingly chooses unusual tacit
> assumptions, correctly reasons from those tacit assumptions to a
> probability of 1/2, and is unaware that the tacit assumptions most
> people make lead to a probability of 2/3. In all cases that I am
> aware of, people who come up with the value of 1/2 reason *incorrectly*
> from the *standard* assumptions rather than *correctly* from *unusual*
> assumptions. Can anyone offer any solid evidence to the contrary?
Tim Chow writes very nicely. I cannot offer him evidence to the contrary
but I can tell that his experience is in the same line as mine. People
just make errors - even when they pretend they are right. Here are some
examples of mathematical errors made by professional mathematicians in
their published works. The following false statements have been mostly
presented as theorems and supported by proofs. The counterexamples below
invalidate the theorems (that is, the counterexamples satisfy all the
assumptions made by the authors):
F.R. Harvey: Spinors and Calibrations, Academic Press 1990, p. 272, l. -12
H.B. Lawson, M.-L. Michelsohn: Spin Geometry, Princeton 1989, p. 56, l. -12
M. G"ockeler, T. Sch"ucker: Differential Geometry, Gauge Theories, and
Gravity, Cambridge UP 1987, p. 190, l. 17
Statement: Spin+(3,3) is simply connected and Spin+(3,3)/{1,-1}=SL(4,R)
Counterexample: The maximal compact subgroup SO+(3,3) is SO(3)xSO(3) which
has a four-fould universal cover Spin(3)xSpin(3), thereby the two-fold
cover Spin+(3,3) of SO+(3,3) cannot be simply connected.
H.B. Lawson, M.-L. Michelsohn: Spin Geometry, Princeton 1989, p. 10, l. 15-16
Statement: In characteristic 2 the vectors v and w in the vector space V
satisfy the multiplication rule vw+wv = 0 in the Clifford algebra Cl(V)
Counterexample: Let V be of dimension 2 over K={0,1} with quadratic form
Q(xe1+ye2)=xy. Then Q(e1)=0, Q(e2)=0, Q(e1+e2)=1 and e1e2+e2e1=1 not 0.
J. Gilbert, M. Murray: Clifford Algebras and Dirac Operators in Harmonic
Analysis, Cambridge UP 1991, p. 41, l. 19 and p. 42, l. 2-3
F.R. Harvey: Spinors and Calibrations, Academic Press 1990, p. 202, l. 4-5
Statement: For an element u in the Clifford algebra Cl_p,q and its conjugate
u~ we have u~u=0 (which is real) implies uu~=0.
Counterexample: Take u=1+e1+e234+e1234 in Cl_3,1 (e1e1=e2e2=e3e3=1, e4e4=-1)
Then u~u=0 (which is real), but uu~=4e234+4e1234 (which is not real).
R. Delanghe, F. Sommen, V. Soucek: Clifford Algebra and Spinor Valued
Functions, Kluwer 1992, p. 126, l. 16-17
Statement: Pin+(n,C) and Spin+(n,C) are connected (as defined by authors)
Counterexample: Pin+(1,C)={1,-1,ie1,-ie1}, Spin+(1,C)={1,-1} and each
Pin+(n,C) with n>2 has two components (as defined by the authors).
S. Salamon (from Oxford): Riemannian Geometry and Holonomy Groups,
Longman/Wiley 1989, p. 170 . l. 1
Statement: For a k-vector x and an l-vector y, with k<l, xy=x^y+x_|y
where x_|y is an (l-k)-vector (and x^y is an (l+k)-vector)
Counterexample: In the Clifford algebra Cl_0,4 take x=e12 (k=2) and
y=e134 (l=3). Then xy=e12e134=-(e1e1)e2e3e4=e234 is a 3-vector.
In spite of the mathematical errors, all these books are excellent
readings on Clifford algebras and spinors. At the for-front of science
it is just true that we make a lot of errors (= our cognitive charts
do not yet describe accurately the territory we are about to conquer)
and this is contrary to what laymen believe about science-making.
When laymen become aware about the fact that scientists make errors,
somehow their belief in science is shattered.
--Pertti Lounesto <loun...@dopey.hut.fi>
--
Tim Chow tyc...@math.mit.edu
Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
only 1 1/2 tons. ---Popular Mechanics, March 1949
Timothy Y. Chow
>|
>| Prove this integral is not a closed form, and I will be happy
>|
>| I tried, and I don't know how to do it.
>|
>| Ron Maimon
>MathCad (invoking Maple) says:
>Integral exp(x^2) = -1/2 * sqrt(pi) * i * erf (i * x)
>This still leaves the question whether erf qualifies for a closed form
>simply because someone has given this function a name :-)
Newsgroups: sci.math
jfra...@mitre.org (Joe Francoeur) writes:
Bob Agnew
Sure -- Just show that this integral evaluated on [0,x] has a McLaurin expansion
of:
x - x^2/3 + (1/2!)x^5/5 - (1/3!)x^7/7 + ....
Then simply prove that this is not the series expansion of any elementary function.
---
"Those who cannot cope with mathematics are not fully human. At best they
are tolerable sub-humans who have been taught to bathe and not make messes
in the house." From the Notebook of Lazarus Long (Robert Heinlein)