HDTenEightyP/NetNews huggingface dataset:
From: chihy@seas.gwu.edu (Chih-Hsun Yao)
Subject: comparison problem
Organization: George Washington University
Distribution: usa
Date: Wed, 18 Nov 1992 16:10:28 GMT

Hi, everyone:
        I got problem with following question:

Describe an algorithm that finds the largest and second largest integer in a
set of (2^m) integers using at most m+(2^m)-2 comparisons.
(Hint: Consider binary tree tournament)

        My problem is following: if I use the way of binary tree tournament,
there is no doubt I can find the largest number at (2^m)-1 comparisons, but
how can I find the second largest number at (m-1) comparisons?
        My friend give me an example: the set {9,2,4,5,6,3,1,8}
9 compares to 2, 9 stands out. 4 compares to 5, 5 stands out. 6 compares to
3, 6 stands out. 1 compares to 8, 8 stands out. Then 9 compares to 5, 9 
stands out. 6 compares to 8, 8 stands out. The final step, 9 compares to 8,
9 stands out. We get the largest number, and the total comparisons are
7 times = (2^m-1). To get the second largest number, we just use 8 to 
compare to 6 and 5, just 2 comparisons = (m-1).
        I find it only works in this example. If I put the 8 at the second
position such as {9,8,2,4,5,6,3,1}, I can still get the largest number at 
(2^m)-1 comparisons, but I cannot get the second largest number at m-1
comparisons. As you see, I will lose the second largest number 8 at first 
comparison. In that case, I have to recompare form the beginning, and the
result will not be m+(2^m)-2 comparisons.
        Any idea? Thanks in advance.


                                                        Chih-Hsun Yao


Newsgroups: sci.math
From: kekamins@zeno26.math.UWaterloo.ca (kekaminsky)
Subject: Re: Square root
Summary: Analytical method for computing 
Organization: University of Waterloo
Date: Fri, 20 Nov 1992 21:26:17 GMT

In article <n9146070.722056383@waldorf> n9146070@waldorf.cc.wwu.edu (Jacob C Kesinger) writes:
>There was a previous post about ways to find the square root of a number...
>
>Here's my contribution:
>
>Find the Taylor series about a (I used a=1, for simplicity)
>
>(x-1)^.5=1+ (x-1)/2- (x-1)^2/4 +3(x-1)^3/8 -......
>
>This is nasty, messy, ugly, and very likely wrong.  However, it IS
>a method (*grin*)
>
>Jake Kesinger
>n9146070@henson.cc.wwu.edu

This Taylor series is incredibly inefficient (I tried using it once
in a numerical analysis program in BASIC because I wanted double precision
and the version of BASIC I was using had only single precison accuracy on
its square root fct.) so I sought out a better method. 

And yes there is an excellent algorithm for computing the square root that works
similarily to long division.  For square roots you take say 2.0000000 .... and taking
two digits at a time, you perform a process like long division, which I can't remember
right now.  For cube roots you take 3 digits at a time, and so on.  The method is
elaborated upon in CRC Book of Mathematical Functions.  It is a method that is
not taught in schools anymore.

Kirk
From: rgep@emu.pmms.cam.ac.uk (Richard Pinch)
Newsgroups: sci.math
Subject: Re: Help with Algebraic Number Theory
Keywords: hilbert algebraic number
Date: 23 Nov 92 11:54:00 GMT
Organization: Department of Pure Mathematics, University of Cambridge

In article <1epji1INN66u@manuel.anu.edu.au> molrchon@mehta.anu.edu.au writes:
>
>My thesis topic is "Hilbert's 10th Problem and a Generalization to
>Algebraic Integers".  In the course of the year, one of the papers I read
>was:
>
>    Denef & Lipshitz, "Diophantine Sets Over Some Rings of Algebraic Integers",
>	J. London Math. Soc., v18, 1978, pp385-391.
>
>and I am covering the contents of that paper in my thesis.  One of the theorems
>proved in that paper is the following:
>
>Notation:  For a number field L (ie. a field of algebraic numbers, of finite
>  degree over the rationals) the ring of algebraic integers in L will be
>  denoted O(L).  The multiplicative group of units in O(L) will be denoted U_L.
>  The torsion free rank of a group G will be denoted rk G.
>
>THEOREM:
>  Let L be any number field and d \in O(L) such that sqrt(d) \not\in L.
>  Write L' = L(sqrt(d)).  Define
>
>       V_L = {x + y.sqrt(d) : x,y \in O(L) and x^2 - dy^2 = 1}
>
>  Then V_L is a subgroup of U_{L'} and
>
>       rk V_L = rk U_{L'} - rk U_L
>ENDTHEOREM
>
>The proof suggested by Denef & Lipshitz starts as follows:
>
>  Let N:U_{L'} -> U_L be the restriction of the norm from L' to L.  In this case
>  we have N(u + v.sqrt(d)) = u^2 - dv^2, so that V_L is a subgroup of
>  kernel(N).  The claim is that V_L in fact has finite index in kernel(N).
>  Denef & Lipshitz do not explicitly prove this, but say it follows easily from
>  the following lemma:
>
>    Suppose K is a number field, e \in U_K and 0 != t \in O(K).  Then there is
>    m > 0 such that t | e^m - e^{-m}.
>
>  My supervisor and I have been unable to see quite how this implies what we need.
>
We need to show that if  u \in U_{L'} is annihiliated by the
norm map N then some power of u, say u^m, is in V_L.  Now u = x + y sqrt(d)
with x, y \in L, and N(u) = x^2 - dy^2 = 1, so the only question
is about the integrality of x and y.  By the lemma cited, there is an m
such that u^m + u^{-m} is divisible by 2sqrt(d).
Let u^m = X + Y sqrt(d).  Now u^m and u^{-m} are algebraic integers, 
so u^m+u^{-m} = 2X is: but 2X is divisible by 2sqrt(d) and so in particular
X is integral, and even divisible by sqrt(d).  Now Y sqrt(d) = u^m - x is
a difference of integers, each divisible by sqrt(d) and hence an integer
divisible by sqrt(d).  So X and Y are integers and so in O_L.
The finiteness of the index follows from applying this argument to a
set of generators u_i for U_L' and then taking the lcm of the resulting m_i.

Richard Pinch
Xref: sparky sci.math:15448 comp.edu:1940
From: israel@unixg.ubc.ca (Robert B. Israel)
Newsgroups: sci.math
Subject: Re: ODE problem...
Date: 19 Nov 92 23:08:20 GMT
Organization: The University of British Columbia
NNTP-Posting-Host: unixg.ubc.ca

In <1eg9p0INNcbe@master.cs.rose-hulman.edu> goddard@NeXTwork.Rose-Hulman.Edu (Bart E. Goddard) writes:


>following problem.  The solutions still works just fine, but one
>of the constants is different:


>In article <israel.722130237@unixg.ubc.ca> israel@unixg.ubc.ca (Robert  
>B. Israel) writes:
>> >(x and y are functions of t, a is a constant)
>> >x'=(a)(x)cost+(a)(y)sint
>> >y'=(a)(x)sint-(a)(y)cost.
>>  
>> Quite a neat problem!  I hope nobody was sadistic enough to
>> assign it as homework.
>> 
>> First go to polar coordinates: x = r cos(s), y = r sin(s)
>> (I'm too lazy to type "theta").
>> (1)   r' = (x x' + y y')/r = r cos(t-2s)
>     there's a missing "a" here ^

>[....]
>> -- 
>> Robert Israel                            israel@math.ubc.ca

>Bart Goddard

Oops, sorry about that.  So k has a missing factor of "a".  BTW, the
solutions can be written, without using arcsin, as
  x = exp(k t) (cos(t/2) + 2 (a-k) sin(t/2))
  y = exp(k t) (2 (k-a) cos(t/2) + sin(t/2))
where k = +- sqrt(a^2 - 1/4), for |a| > 1/2.

For |a| < 1/2, this still works but these solutions are complex.  Take
real and imaginary parts to get real solutions:
  x = (1/2-m) cos((1/2+m)t) + (1/2+m) cos((1/2-m)t) 
                   + a sin((1/2+m)t) + a sin((1/2-m)t)
  y = - a cos((1/2+m)t) - a cos((1/2-m)t)
                   + (1/2-m) sin((1/2+m)t) + (1/2+m) sin((1/2-m)t)
and
  x = - a cos((1/2+m)t) + a cos((1/2-m)t)
                   + (1/2-m) sin((1/2+m)t) - (1/2+m) sin((1/2-m)t)
  y = -(1/2-m) cos((1/2+m)t) + (1/2+m) cos((1/2-m)t)
                   - a sin((1/2+m)t) + a sin((1/2-m)t)
where m = sqrt(1/4 - a^2).

For a = +-1/2, my formula only gives one solution:
  x = cos(t/2) + 2a sin(t/2)
  y = -2a cos(t/2) + sin(t/2)
A second linearly independent solution can be obtained using a limit
procedure:
  x = t cos(t/2) + (2at-2) sin(t/2)
  y = (2-2at) cos(t/2) + t sin(t/2)

-- 
Robert Israel                            israel@math.ubc.ca
Department of Mathematics             or israel@unixg.ubc.ca
University of British Columbia
Vancouver, BC, Canada V6T 1Y4
Newsgroups: sci.math
From: arvola@sol.acs.unt.edu (Arvola William)
Subject: Re: A Question About Fundamental Group
Organization: University of North Texas
Date: Wed, 18 Nov 1992 17:30:12 GMT

nissim@mary.fordham.edu (Leonard J. Nissim) writes:

>In article <amirishs.722059588@acf9>, 
>amirishs@acf9.nyu.edu (shaahin amiri sharifi) writes...
>>Consider a bunch of infinitely many (countable) circles with a
>>point in common. The radii of these circles make a sequence like
>>{1/n}. What is the fundamental group of this space? Any comments
>>or referenc would be so helpful!

>Sometimes known as the "Hawaiian earing space".
>Its fundamental group has coutably many generators (one for each circle)
>and no relations.  (I.e., it is a free non-Abelian group on countably 
>many generators.)  

I don't think that it is as simple as this.  Take, for example,
a loop running around a subcollection of the circles whose radii
converge like the sequence {1/2^n}.  Since this (sub)sequence is
summable this loop represents an element of the fund group which
is not a finite product of the generators that were proposed.

>"Algebraic Topology: An Introduction" by Massey is a good reference for 
>the definition and early theorems about the fundamental group.

>This is cute:  take the cone over your original space; that is, put all 
>the circles in the xy-plane tangent to the y-axis at (0,0) and connect 
>each point of every circle to the point (0,0,1) in R^3.  
>Now you have a space that is contractable (homotopic to a point), but 
>*not* locally simply connected.  In fact, every small neighborhood of (0,0,a)
>(where 0<=a<1) has a fundamental group with infinitely many generators. 

>-------------------------------------------------------------------------------
>Leonard J. Nissim  (nissim@mary.fordham.edu)   
>Disclaimer:  "I speak only for myself."
>-------------------------------------------------------------------------------
Xref: sparky sci.math:15152 sci.physics:19123
From: butler@rschp2.anu.edu.au (Brent Butler)
Newsgroups: sci.math,sci.physics
Subject: Re: 3-sided coin
Date: 18 Nov 1992 04:33:49 GMT
Organization: Australian National University
NNTP-Posting-Host: 150.203.35.27


>>[I said problem is simple - ... the answer is when the gravitational
>>potential energies are equal.  i.e. t/d=1]

Rob Ryan says:
>Yes, it will come to rest at a minimum, but it doesn't have to be an
>absolute minimum, but rather a local minimum would do as well.  
>Resting on edge is a relative minimum and is therefore possible.  

Yes.  You are right.  I implied that the lowest energy 
state would be the only one possible.  This is of course 
incorrect - all states are possible but with probability that 
depends on the energy of that state above the ground state.  
Higher energy states are of course possible (populated) but less 
likely.  I still contend that this is the best 
back-of-the-envelope (or was that a taxi :) ) method of getting 
at a *reasonable* answer though.  [I should note here that Blair 
H.  made an important factor of 2 correction to this argument that 
I left out (I did not count the number of states correctly) - so 
I'm wrong on more than one count in my original post. t/d should
be =1/2 which is identical to the equal areas hypothesis!] 

And yes, there is much much more to this problem than that but the 
original poster asked for a 20 second answer and the dynamics of
a thick coin toss are beyond the scope of 20 seconds.

-Brent Butler
Newsgroups: sci.math
From: pperez@math.ucla.edu (Pablo A. Perez-Fernandez)
Subject: complex analysis
Organization: Department of Mathematics, UCLA
Distribution: sci
Date: 23 Nov 92 18:35:58

Clarification: This is not homework. This is from Conway's Complex
Analysis, problem 15, page 55, second edition from Springer Verlag.  I
am using Conway's book to supplement Ahlfor's which is the book being
used in my class.

Can you map the open unit disk confomally onto {z:0<|z|<1}?

I believe that this is not true but have not true but have not being
able to prove it. At this point in my course I am not supposed to be
able to use any of the integral formulations of Cauchy's theorem, the
argument principle, etc.

- pablo
From: kohut1@urz.unibas.ch
Newsgroups: sci.math
Subject: Solutions of Lane-Emden-Diff. Eq. ???
Date: 23 Nov 92 13:18:26 MET
Organization: University of Basel, Switzerland

I desperatly lookink for any solution off the Lane-Emden differantial equation.
My problem is, that I even don't found any lectures about this diff.eq. 

So, any help is warmly appreciated !

Thanks in advance...

-Peter-

P.S. By "solution" I mean numerical OR analytical solutions, of course
From: buyskes@lafcol.lafayette.edu (Steve Buyske)
Newsgroups: sci.math
Subject: A source for Polydrons?
Date: 17 Nov 92 16:33:32 GMT
Organization: Lafayette College, Easton PA


Does anyone know a mail-order source for Polydrons? They are hard plastic	polygons that snap together to form polyhedra to your heart's content.
I'd like to supplement my collection of triangle and squares with hexagons
and such, but I can't find a supplier. I'd be grateful for any pointers.
 
Newsgroups: sci.math,sci.physics,sci.astro,sci.bio,sci.chem,misc.education
From: millard@eos.arc.nasa.gov (Millard Edgerton)
Subject: Re: What can we have for an educational system?
Organization: NASA Ames Research Center
Distribution: usa
Date: Mon, 23 Nov 1992 03:47:29 GMT

In 1965 while on a visit to relatives in Lincoln, NE I was talking to my cousin
about something I remember NOT what.  To make my point, I used a simple
algebraic expression, again I do not recall what!  WHAT I do recall is
another cousin's high school daughter almost shouting, "You mean there is
a R*E*A*L USE for algebra!?  

As in almost all education problems, I find the parents MOST responsible,
totally or partly lacking in understanding what their children are or are
not learning, attending PTA, taking an interest in what-who & how their
children are being taught and voting wisely.  The state, ND, with the 
lowest average teacher's salary has the highest percentage of high school 
graduates and then going on to college.

Of inerest when I went to school - '30's 40's, Children were human off spring;
kids that of goats.  Maybe the names are unimportant, then again ????
A rose by any other name ------
***************************************************************************
*  "To be conscious that you are ignorant  | Standard disclaimer(s)       *
*  of the facts is a great step to         | Millard J. Edgerton, WA6VZZ  *
*  knowledge". -Benjamin Disraeli 1804-1881| millard@eos.arc.nasa.gov     *
***************************************************************************
Newsgroups: sci.math
Subject: Re: Looking for name of group of order 12...
From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
Date: 19 Nov 92 17:25:51 GMT
Organization: Beckman Instruments, Inc.

In <1992Nov18.194440.4819@tamsun.tamu.edu> rlm7638@tamsun.tamu.edu (Jack McKinney) writes:


>     Here I go, with yet another group theory question. This one is of
>etymology. There are five groups of order 12: The cyclic group of order
>12 (Z_12), the direct product of the cyclic groups of orders 2 and 6
>(Z_2 x Z_6), The alternating group on 4 objects (A_4), the dihedral
>group of a 6-sided object (D_6), and then one more. This last one
>I have always seen written as just 'T'. Can anyone tell me where this
>name comes from?

>           T={<a,b>: a^6=e, a^3=b^2, ba=a^5 b}

I've never seen "T", but it is also [Z_3]Z_4;

{<a,b>: a^3=b^4=e, ba=a^2 b}

Z_12        = Z_4 x Z_3
Z_2 x Z_6   = K_4 x Z_3  (K_4 = Z_2 x Z_2))
D_6         = S_3 x Z_2 = [Z_3]Z_2 x Z_2
A_4         = [K_4]Z_3
"T"         = [Z_3]Z_4
--
Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
My opinions are my own, and do not represent those of my employer.
My interaction with our news system is unstable; please mail anything important.
From: brock@NeXTwork.Rose-Hulman.Edu (Bradley W. Brock)
Newsgroups: sci.math
Subject: Re: help me take a derivative of this complex function
Date: 17 Nov 1992 19:13:06 GMT
Organization: Computer Science Department at Rose-Hulman
Distribution: usa
Reply-To: brock@NeXTwork.Rose-Hulman.Edu (Bradley W. Brock)
NNTP-Posting-Host: g210b-1.nextwork.rose-hulman.edu

In article <1992Nov17.124151.17533@husc3.harvard.edu> mlevin@husc8.harvard.edu  
(Michael Levin) writes:
Here it is:
> f(c) for a complex c, is equal to c', where the real part of c' is
> equal to the imaginary part of c, and vice versa. In other words, f()
> simply switches the real and imaginary parts of the variable it's
> applied to. so, what would be f'()?

The problem is that this is not an analytic function so the derivative does not  
exist.  The partial derivative in the real direction is i, but the partial  
derivative in the imaginary direction is -i.

--
Bradley W. Brock, Department of Mathematics
Rose-Hulman Institute of Technology  | "Resist not evil.... Love your
brock@nextwork.rose-hulman.edu       |  enemies."--Jesus of Nazareth
Newsgroups: sci.math
From: mab@wdl39.wdl.loral.com (Mark A Biggar)
Subject: Re: Square root
Organization: Loral Western Development Labs
Date: Fri, 20 Nov 1992 22:59:52 GMT

In article <1992Nov19.003129.2915@galois.mit.edu> jbaez@riesz.mit.edu (John C. Baez) writes:
>In article <n9146070.722056383@waldorf> n9146070@waldorf.cc.wwu.edu (Jacob C Kesinger) writes:
>>There was a previous post about ways to find the square root of a number...
>>Here's my contribution:
>>Find the Taylor series about a (I used a=1, for simplicity)
>>(x-1)^.5=1+ (x-1)/2- (x-1)^2/4 +3(x-1)^3/8 -......
>>This is nasty, messy, ugly, and very likely wrong.  However, it IS
>>a method (*grin*)
>It'll work, assuming you got the right coefficients in your Taylor
>series, as long as |x-1| < 1.  It's pretty good if you just want a few
>digits and x is near 1.  
>The best use of this formula is to impress undergraduates by working out
>in your head, for example, that the square root of 1.23 is about 1.115.

This is also not bad for generating the mantissa of an initial guess
when computing square roots of binary floating point numbers.  A binary
floating point number (e.g. IEEE) has a mantissa that is .5<=m<1 which meets
the above inequality.  After renormalizing to make the floating point exponent
even you now have a mantissa that is .25<=m<1 and the inequaltity still
holds, so use the above 3 or 4 terms to get the mantissa of the guess,
then run 2 to 4 interations of the Newton-Raston formula to firm up the 
answer and your done.  

--
Mark Biggar
mab@wdl1.wdl.loral.com

Xref: sparky sci.math:15084 sci.physics:19015
From: bhoughto@sedona.intel.com (Blair P. Houghton)
Newsgroups: sci.math,sci.physics
Subject: Re: Three-sided coin
Date: 16 Nov 1992 22:02:20 GMT
Organization: Intel Corp., Chandler, Arizona
NNTP-Posting-Host: alfalfa.intel.com
Summary: probability is distributed according to entropy, not energy

In article <jim.721702281@st-michael> jim@cs.UAlberta.CA (Jim Easton) writes:
>Given that it is possible to bounce from one state to another it
>is more probable to bounce out of a high energy state to a lower
>energy state than it is the reverse.  I claim that the lowest energy
>state is the most probable and therefore conclude that the three states
>should be equal in energy.

This is fallacious.

Imagine a three-sided "coin" made by bending a very thin
sheet (of something very low-density like titanium) in the
middle at about a 170-degree angle, then adding a thick
bead of gold or lead inside the crease.  The low-energy
states of this object are the two states that occur when
the coin lands with the convex side down (resting flat on
one leaf or the other).  The high-energy state occurs when
the coin lands with the concave side down (like a tent).

The concave and convex sides have nearly the same
probabilities, but there are two states on the convex side,
which splits the probability there; say it's something like
30, 30, 40 for convex/A, convex/B, and concave, respectively.

This is a direct contradiction of the idea that "the lowest
energy state is the most probable."

It's even worse if you make low pyramids with heavy apices
(say a styrofoam body but a unnilquadium capstone, in a
vacuum, to eliminate aerodynamics).

Like 11, 11, 11, 11, 11, 45 for a pentagonal pyramid, for
instance.

The key isn't energy; it's entropy.  The pointy end gets a
larger total of the probability (55%) because it has a
higher entropy because it has a lower energy (this is what
causes the confusion; the low-energy idea works perfectly
for two-state systems).  But the entropies of all of the
five faces of the pentagonal pyramid are equal, just as
their energies are all equal, so the probability for the
pointy end has to be shared among them (11% each).

Conversely, landing on the base has a lower probability
(45%) than landing on the point because it has a lower
entropy because it has a higher energy, but it doesn't have
to share the entropy, so it keeps all of the probability.

To solve the fat-cylinder problem (height H, radius R),
therefore, one considers the faces as similar, then one has
a two-state problem, choosing between a face-landing and an
edge-landing.  Set the probability (entropy) of a
face-landing to 2/3 and an edge landing to 1/3; thus the
energy of the edge-landing is (1 - 1/3)E = 2/3 E and that
of a face-landing is (1 - 2/3)E = 1/3 E.  The edge-landing
therefore has twice the energy of a face-landing.

Since the energy is simply mgh, and m and g are constants,
it follows that the h for an edge-landing is twice the h
for a face-landing, so R=H.

				--Blair
				  "If you catch an edge you
				   will land on your face."
				   -the Bunny-slope paradox
Newsgroups: sci.math
Subject: Re: Solutions of Lane-Emden-Diff. Eq. ???
From: harper@kauri.vuw.ac.nz (John Harper)
Date: Mon, 23 Nov 1992 23:22:06 GMT
Organization: Victoria University of Wellington

In article <1992Nov23.131826.42578@urz.unibas.ch> kohut1@urz.unibas.ch writes:
>I desperatly lookink for any solution off the Lane-Emden differantial equation.
>My problem is, that I even don't found any lectures about this diff.eq. 
>
There's always S Chandrasekhar "An introduction to the study of stellar
structure" Dover 1957 (reprint of 1939 ed. Univ Chgo Press)

John Harper Mathematics Dept. Victoria University Wellington New Zealand
From: burt@aupair.cs.athabascau.ca (Burt Voorhees)
Newsgroups: sci.math
Subject: Re: Bozos Synonymous
Date: 21 Nov 92 19:10:01 GMT
 <burt.722061313@aupair.cs.athabascau.ca> <1eerodINNngi@iskut.ucs.ubc.ca>

>In article <burt.722061313@aupair.cs.athabascau.ca>
>burt@aupair.cs.athabascau.ca (Burt Voorhees) writes:

>>Mathematicians tend to be rather sexist.

>My experience has not suggested this. I hear scarcely any sexist
>comments from fellow mathematicians. I haven't witnessed any
>discriminatory action lately either. If anything, it seems as though
>academics in general, and academic mathematicians included, are
>typically less sexist than the non-academics I've encountered, and are
>interested in women participating in mathematics as equals. I'd *like*
>to think this is true. Of course, this is only loose anecdotal
>evidence, so I could be wrong. On what is your opinion based?

>Keith Ramsay

Mainly on mathematicins I've known.
Admittedly a subjective perception,
but from what I've seen many
mathematicians "talk the talk"
but don't "walk the walk."
So one hears comments about things
like the kinds of mathematics that
women can do (mainly computation,
sorting and arranging, nor _real_
macho stuff)

I don't want to do any disservice
though to the mathematicians who
really are non-sexist, which is
probably a majority.  But there are
the statistics about the numbers of
tenured faculty at major universities
(I think it's something like 5 out of
400 but don't have the data at hand.)
which were reported in several articles
in Science over the past year.

burt voorhees
Newsgroups: sci.math