Newsgroup sci.math.research 6348

Directory

This is an expository article.  My justification for posting it here is
that I believe that most of us research mathematicians are underinformed
about areas of mathematics other than our own (probably because exposition
is considered an inferior occupation to doing research) and that mathematics
research as a whole suffers because of this.  This article is a small
contribution to overcoming this problem.  I hope it inspires others to
write similar articles.
I am not a number theorist myself and the level of the article is therefore
pretty elementary, but I believe that it contains a fair amount of material
that most non-number theorists do not know (especially in the last part of
the article).
The article is a revision of an article that I posted to sci.math about a
year ago, plus some additional comments.  For those who saw the original
version, the main addition is an explanation of why Artin reciprocity is
called "reciprocity."
======================== Revised article follows ==========================
Prerequisites include familiarity with the elementary concepts of algebra,
e.g., group, ring, and field.  We will also be using the term "finite
algebraic extension" a lot; if F is a subfield of K, then K is a finite
algebraic extension of F if K is finite-dimensional when considered as a
vector space over F.
Number theory may be thought of as the study of the integers, but somewhat
more generally it may be thought of as the study of *algebraic* integers.
An algebraic integer is any number that is the root of some polynomial
equation with integer coefficients whose leading coefficient is 1.  The
definition seems artificial, but it turns out to have many important
properties.  For example, the set of all algebraic integers forms a ring
(with the usual addition and multiplication).  Moreover, if we fix a
finite algebraic extension F of the rationals, the set of all algebraic
integers lying in F forms a subring of F called the "ring of integers" of F.
Rings of algebraic integers have many properties analogous to those of the
usual integers.  For example, one can define the notion of a prime number
in an exactly analogous way.  The big catch is that in general, one does
not have a unique factorization theorem: elements in a ring of integers may
have several essentially distinct factorizations into primes.
There is, however, a way of fixing up the situation to some extent.  Roughly
speaking, we consider certain *subsets* of the ring---the "ideals"---which
we can multiply together in a natural way (more precisely, the product of
the ideal A with the ideal B is the set of all elements of the form
a_1 * b_1 + ... + a_n * b_n with all a_i in A and all b_i in B).  Once we
have a multiplication, it makes sense to talk about factoring ideals into
irreducible or "prime" ideals.  The amazing fact is that in any ring of
integers, every ideal can be uniquely factored into prime ideals.  (The
major architect of this theory was Kummer, who was partially motivated
by trying to fix a certain false proof of Fermat's Last Theorem whose
key false step assumes unique factorization in the naive sense.)
Some rings of integers are "principal ideal domains," i.e., every ideal
just consists of the set of all multiples of x for some element x in the
ring.  This is the case for the ordinary integers: for each integer n,
the set of all multiples of n is an ideal, and these are all the ideals.
In principal ideal domains, the unique factorization theorem for ideals
implies that all *numbers* in the ring have a unique factorization into
*prime numbers* in the ring.  In an arbitrary ring of integers, however,
there may exist ideals that are not principal.
To get a handle on rings of integers where not every ideal is principal,
we would like to have some measure of how far off the ring of integers
is from being a principal ideal domain.  If you've had a fair amount of
algebra you can probably guess that the way to do this is to "mod out"
the set of all ideals by the set of principal ideals.  This is almost
right, except that it turns out to be better to introduce extra ideals
called "fractional ideals" in order to make the set of all ideals a
*group* under multiplication.  Modding out the group of all fractional
ideals by the group of all principal ideals gives an entity called the
"ideal class group" or just the "class group" of the ring of integers
(or of the finite algebraic extension).
It is a fundamental theorem of algebraic number theory that for any
finite algebraic extension of the rationals, the class group is always
a *finite* group.  This is proved using geometric (!) methods.  The order
of the class group is called the *class number* of the algebraic extension.
Two more pieces of background are needed before we go on to class field
theory.  Suppose F and K are finite algebraic extensions of the rationals,
and suppose F sits inside K.  Let their respective rings of integers be
R_F and R_K.  It turns out that there is a natural way to associate an
ideal of R_K with each ideal in R_F (the ideal in R_K is said to be
"generated" by the ideal in R_F).  A natural question to ask is whether
the prime factorization of an ideal I of R_F necessarily "lifts" to a
prime factorization of the ideal of R_K generated by I.  Unfortunately,
things are not that simple.  Even if one takes a prime ideal P of R_F,
the ideal of R_K generated by P might not be prime; for example, it might
be a power of a prime (in which case P is said to "ramify" in K) or it
might be the product of distinct primes (in which case P is said to
"split" in K).  If no primes ramify, K is said to be an unramified
extension of F.  (Here I'm lying slightly, because I really should
include "infinite" or "archimedean" primes when I talk about unramified
extensions, but that would be too much of a digression.)
The other piece of background is Galois theory.  If F and K are as above,
then it turns out that the set of all automorphisms of K that leave every
element of F fixed is an object of fundamental interest.  This set of all
automorphisms actually forms a group under the operation of composition.
In certain special cases, where K is a "normal extension" of F (I won't
define this here), this group is called the "Galois group of K over F,"
written Gal(K/F).  Why the Galois group is important is unfortunately
beyond the scope of this article; let's just take it on faith for now.
O.K., let's take stock.  We have two kinds of groups floating around:
class groups and Galois groups.  It is therefore a natural question to
ask if there is any relationship between them.  Now, since they are
defined in such different ways, it is not at all obvious that there is
any relationship between them at all.  In a nutshell, class field theory
is the amazing fact that there is actually a very close relationship
between the two: certain class groups are actually equal to certain
Galois groups.
Let's make this a little more precise.  First of all, Galois groups
need not be abelian, whereas class groups are always abelian (since
multiplication of ideals is defined in terms of ordinary multiplication
of numbers, which is commutative).  So if F is a finite algebraic
extension of the rationals, the only extensions K of F for which Gal(K/F)
could possibly be equal to the class group of F are those for which
Gal(K/F) is abelian (the "abelian extensions of F").  One of the basic
theorems of class field theory is the claim that given any F, there
exists a unique maximal unramified abelian extension K of F (the
"Hilbert class field of F") and that for this extension K, the class
group of F is isomorphic to Gal(K/F).  Moreover, the isomorphism is
given explicitly by the so-called Artin map, which associates a
"Frobenius element" to each prime ideal in R_F (details omitted).
Class field theory also tells us about extensions that are not unramified.
Given any finite set S of prime ideals in R_F, there exists a unique maximal
abelian extension of F in which only prime ideals in S ramify.  These
extensions are called "ray class fields," and their Galois groups are
isomorphic to certain modified class groups of F.  Again, the isomorphism
is given explicitly by the Artin map.  (I'm being vague here partly because
of my own ignorance and partly because the exact definitions are quite
technical.)
That the Artin map is an isomorphism is the famous "Artin reciprocity
theorem."  (It is usually stated for arbitrary abelian extensions of F
rather than just the Hilbert class field and the ray class fields, but
these maximal class fields embody the essence of the theorem.)
The basic point of this is that by looking only at "internal" invariants
of F such as the class group of F, one gets a great deal of information 
about (one might even say a classification of) the maximal abelian
extensions of F (and Galois theory tells you about the intermediate
abelian extensions), which are "external" to F.
The main limitation of class field theory is that it gives information
only about abelian extensions of F.  The search for an analogue of class
field theory in the nonabelian case is one of the basic motivations of
the Langlands program, about which I know even less than I know about
class field theory, so I'll shut up at this point.
========================= Additional comments ==============================
After the appearance of the original article, Don Kersey emailed me to
point out that I neglected to mention the fundamental example of this
theory:
>I think you should mention the canonical example here - abelian extensions
>of the rationals are all cyclotomic, and the ray class field corresponding
>to the ideal generated by a rational integer m is just the field obtained
>by adjoining the mth roots of unity to Q. 
This is probably a good place for me to insert a couple of historical
remarks.  That every abelian extension of the rationals can be embedded
in a cyclotomic extension (i.e., an extension obtained by adding roots
of unity) is known as the Kronecker-Weber theorem, which was proved in
the 19th century.  The problem of understanding abelian extensions was
the twelfth in the list of Hilbert's famous 23 problems.  The Hilbert
class field case was proved by Furtwangler (1907), the ray class field
case by Takagi (1920) and the description of the isomorphism as the
explicit Artin map by Artin (1927).
Keith Conrad, among others, has remarked to me that even though there
now exist several different proofs of the theorems of class field
theory, none of them fully "explains" the theorems in a psychologically
satisfactory sense.  I would venture to say that even quadratic
reciprocity, despite its 150-odd published proofs, remains quite
an astonishing fact even after you know how to prove it.
Speaking of quadratic reciprocity, let me now try to explain in very
rough terms why the Artin reciprocity law is called a reciprocity law,
and in what sense it generalizes quadratic reciprocity.  I am indebted
to the article "What is a reciprocity law?" by B. F. Wyman, Amer. Math.
Monthly 79 (1972), 571-586 for many helpful insights.
A reciprocity law is a theorem that is (approximately) of the form,
"the behavior of X modulo Y is determined by the behavior of Y modulo X."
For example, quadratic reciprocity tells us that if p and q are odd primes,
then whether q is a square modulo p is (more or less) determined by whether
p is a square modulo q.
To see why the Artin reciprocity law is a reciprocity law that generalizes
quadratic reciprocity, let us begin by restating quadratic reciprocity as
the question of how the polynomial x^2 - q behaves modulo p.  This allows
us to formulate the following more general question: take a finite algebraic
extension F of the rationals, let f(x) be an arbitrary polynomial with
coefficients in the ring of integers R_F of F, let P be a nonzero prime
ideal in R_F, and ask about the behavior of f(x) modulo P.  I now claim that
the Artin reciprocity law tells us that "the behavior of f(x) modulo P"
is essentially determined by "the behavior of P modulo f(x)."
If this claim is correct then it certainly shows that Artin reciprocity
generalizes quadratic reciprocity and that Artin reciprocity deserves the
name "reciprocity."  But there are two questions we must answer.  First,
what does "the behavior of P modulo f(x)" mean?  Second, how does the
Artin reciprocity law as we've stated it (as an isomorphism of groups)
imply the above relationship between "f(x) modulo P" and "P modulo f(x)"?
The answer to the first question is that by "P modulo f(x)" I just
mean "the residue class of P in a certain modified class group that is
determined by f(x)."  This is not standard terminology, but I justify
it by suggesting that the locution "P modulo something" ought to be
reminiscent of class groups.  In the case of quadratic reciprocity,
f(x) = x^2 - q and the relevant class group is just Z/qZ.
Note that this partially answers the second question, too.  Artin
reciprocity gives a relation between Galois groups and modified class
groups, and I've just said that "P modulo f(x)" has to do with class
groups.  It remains to demonstrate that "the behavior of f(x) modulo P"
has to do with Galois groups.  I won't go into full details here,
referring you instead to the abovementioned paper by Wyman, but I will
at least state the relevant fact.  It turns out the factorization of
f(x) in R_F/P is (almost always) the same as the prime factorization
of the ideal in R_K generated by P, and the latter is intimately related
to the way the Galois group Gal(K/F) acts on prime ideals.  (This fact
is not trivial, but its proof is considerably easier than the proofs of
class field theory.)
The one annoying detail in this picture is the assumption that Gal(K/F)
is abelian.  Can we get rid of it?  We can still ask vaguely if there
is a relationship between "f(x) modulo P" and "P modulo f(x)" when f(x)
is arbitrary.  Conjecturally, the answer is yes, provided we interpret
"f(x) modulo P" and "P modulo f(x)" appropriately---namely, each half
of the equation can be represented by a certain kind of "L-function"
and the two L-functions are conjecturally equal.  At this point I've
reached the limits of my competence so I'll stop.
-- 
Tim Chow       tchow@umich.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

Burt Voorhees wrote:
> 
> I have been looking at the properties of a family of polynomials
> generated by the recurrence relation
> 
>                P(n+1) = xP(n) - P(n-1)
> 
>                P(0) = 0,   P(1) = 1
> 
> They have many interesting properties; e.g., P(n) has n-1 real
> roots, all contained in the interval [-2,2], with the apparent
> limit for n going to infinity of the largest root being 2.
> 
> This came up accidentally in some work on fractal generation,
> and is an area of math I have not studied.  Any references for
> recurrence relations defining polynomial families, or even on
> this particular one appreciated.
> 
> BV
You can tell a lot about these polynomials from the generating function
G(t)=\sum_0^\infty P_n(x)t^n/n! whose expression follows from the
recursion for the P_n's. G(t) satisfies G''-xG'+G=0 (in t) and hence
G(t)=\sqrt{x^2-4}^{-1/2}(\exp(t\lambda_1(x))-\exp(t\lambda_2(x)))
where \lambda_i(x) are the two roots of \lambda^2-x\lambda+1=0.
One can now play all sorts of tricks with the generating function 
including checking whether your polys are related to classical ones
thru transformations etc. (cf. Lebedev's book "Special functions
and their applications" for a brief synopsis before leaping into say
the Erdelyi manuscripts or Abramowitz and Stegun for tricks to play.)
Enjoy!
GAL.

In article <57fe3i$mi8@gannett.math.niu.edu>, rusin@vesuvius.math.niu.edu
(Dave Rusin) wrote:
> In article ,
> bonkie  wrote:
> >Question: characterize the statement:'a map f:V -> V of a metric space is
> >a contraction up to a decent choice of the metric (=equivalent metric)'
> 
> I'm not sure what you want here. If you mean
>         "For every map  f: V-> V  of a metric space there is an
>         equivalent metric relative to which  f  is a contraction"
> then this is clearly false, since every contraction has a unique fixed point,
> and every contraction is continuous -- these are properties which can
> expressed with reference to the metric [at least within the equivalence
> class of metrics]. (If your metric space  V  is not complete replace
> "a unique" with "at most one").
> 
> If you mean
>         "Characterize the functions  f: V-> V  of a metric space
>         for which there is an equivalent metric relative to which
>         f  is a contraction"
> then I don't know an answer but as noted above there would have to be
> some restrictions on  f.
> 
> (I'm interpreting "contraction" in the strong sense here:
> d( f(x), f(y) ) <= r * d( x, y)  for some  r < 1. Obviously a weaker
> definition would allow more functions to be contractions relative
> to some metric.)
I don't remember the reference, or even the author, but as I recall there
is a theorem which runs roughly:  given a metric space (M,d) and a
self-mapping f from M to M, a necessary and sufficient condition that there
be an equivalent metric \rho (complete metric?) such that f is a strict
contraction with respect to \rho is:  for each x in M, the sequence
{f^n(x)} converges to the same point u of M.  The NECESSITY is obvious.  I
may be forgetting some details.
Here's a teaser:  suppose a metric space (M,d) has the property that every
strict contraction f:M \to M has a fixed-point (necessarily unique).  Must
M be complete?  (The answer is due to W. A. Kirk.)
--Ron Bruck

Could anyone please tell me who coined the term Galois Connection ?
Names would be fine, references would be even better.
Just to clarify: I mean GC in the purely set-theoretical sense,
not restricted to special algebraic applications,
i.e. simply two sets A, B,
     and two antitonic mappings f:PA -> PB, g:PB -> PA
     (antitonic: larger sets have smaller images),
     such that fog and gof yield images larger than their arguments.
Please e-mail your answers,
as I am, sorry (8-|), not subscribing sci.math.research.
Bernd Baumgarten
baumgart@darmstadt.gmd.de

In article <57i4du$7v6@aurora.cs.athabascau.ca>, burt@cs.athabascau.ca
(Burt Voorhees) wrote:
> I have been looking at the properties of a family of polynomials
> generated by the recurrence relation
> 
>                P(n+1) = xP(n) - P(n-1)
> 
>                P(0) = 0,   P(1) = 1
You can solve this recurrence relation to write P_n explicitly as
P_{n+1} (x) = \sum_{j=0}^{\floor{n/2}}  x^{n-2j} (-1)^j \binomial{n-j}{j}
or if you prefer ASCII:
           [n/2]   n-2j      j   (n-j)
P    (x) =  SUM   x      (-1)    (   )
 n+1        j=0                  ( j )
where [x] denotes the floor of x and
(a)                           a!
( ) denotes "a choose b" = --------
(b)                        b!(a-b)!
Up to a scaling factor, these are Chebyshev polynomials of the first kind
(U), which are usually normalized to
U_0 (x) = 1, U_1(x) = 2x, U_{n+1} (x) = 2x U_n(x) - U_{n-1} (x)
You can read more about them (among other places) in Eric's Treasure Trove
of Mathematics, under "Chebyshev Polynomials of the First Kind U" at
http://www.astro.virginia.edu/~eww6n/math/ctop.html
where they are described with information about their generating polynomial
and the relation to the Chebyshev polynomials of the first kind T (which in
my experience are the more well-known kind).
Cheers,
michael
brundage@ipac.caltech.edu

In article <57i4du$7v6@aurora.cs.athabascau.ca>,
Burt Voorhees  wrote:
>
>I have been looking at the properties of a family of polynomials
>generated by the recurrence relation
>
>               P(n+1) = xP(n) - P(n-1)
>
>               P(0) = 0,   P(1) = 1
>
>They have many interesting properties; e.g., P(n) has n-1 real
>roots, all contained in the interval [-2,2], with the apparent
>limit for n going to infinity of the largest root being 2.
>
>This came up accidentally in some work on fractal generation,
>and is an area of math I have not studied.  Any references for
>recurrence relations defining polynomial families, or even on
>this particular one appreciated.
>
>BV
>
See Lovasz's "Combinatorial Problems and Exercises" 1. 29, and the section
on eigenvalues of graphs.
Siemion Fajtlowicz.

Alan Bain wrote:
> 
> I'm interested in non-Hausdorff topological spaces (other than the trivial one)
> which have some mathematical significance, since most topological works seem
> to confine themselves to considerations of Hausdorff spaces, and their
> properties.   Are there any standard interesting non-Hausdorff spaces?
> 
> Alan Bain
For any locally compact group, the set of (equivalence classes of)
irreducible unitary representations carries a normally
non-Hausdorff topology, the so-called Fell topology.
Hartmut.

Alan Bain wrote:
> 
> I'm interested in non-Hausdorff topological spaces (other than the trivial one)
> which have some mathematical significance, since most topological works seem
> to confine themselves to considerations of Hausdorff spaces, and their
> properties.   Are there any standard interesting non-Hausdorff spaces?
> 
> Alan Bain
One very important example comes from algebraic geometry: if R is an
arbitrary
commutative ring, let Spec(R) be the set of its prime ideals, and put
the
following topology on Spec(R): a set is closed iff it can be written as
{p : p contains A} where A is a subset of R. This topology is called the
``Zariski topology'', and it is quite seldom Hausdorff. In fact, it is
generally not even T1 (it is T0 though). If R is an integral domain,
then the
point corresponding to the prime ideal {0} of R is dense in Spec(R) (it
is
called the ``generic point'').
     David A. Madore
    (david.madore@ens.fr,
     http://www.eleves.ens.fr:8080/home/madore/index.html.en)

Dear colleagues, 
I am currently trying to use Hidden Markov Models (HMMs) for
representing temporal knowledge on mobile robots. In this
context the following question has turned out to be important:
Given a HMM (discrete-time, finite (hidden)state set, finite set of
observables) which is minimal in the number of hidden states, 
do there exist other HMMs with the same minimal number of
hidden states, which are equivalent in the sense of generating
the same distributions of observable events?
If such other HMMs exist, is there a canonical way to transform
them into each other?
In the HMM literature which I have accessed so far, questions of this
kind are not addressed. It seems that mine is a 
"mathematico-theoretical" question, whereas much of the HMM literature
is decidedly application-oriented.  
If you could offer me some information on this question, please 
email it to herbert.jaeger@gmd.de.
Thank you very much in advance.
Cheers, Herbert Jaeger
-----------------------------------------------------------
Dr. Herbert Jaeger                  Phone  +49-2241-14-2253
GMD, FIT.KI                         (home: +49-2244-6990)
Schloss Birlinghoven                Fax    +49-2241-14-2384
D-53754 Sankt Augustin, Germany
email: herbert.jaeger@gmd.de
WWW: http://www.gmd.de/People/Herbert.Jaeger/
-----------------------------------------------------------

Alan Bain wrote:
> Are there any standard interesting non-Hausdorff spaces?
Any reflexive transitive relation induces a non-Hausdorff topology iff
it is different from the identity relation. But this is studied within
the theory of posets and their generalizations.
regards Joachim

In article <57i4du$7v6@aurora.cs.athabascau.ca>,
 burt@cs.athabascau.ca (Burt Voorhees) writes:
|> 
|> I have been looking at the properties of a family of polynomials
|> generated by the recurrence relation
|> 
|>                P(n+1) = xP(n) - P(n-1)
|> 
|>                P(0) = 0,   P(1) = 1
Aka, up to trivial scaling factors, as Chebyshov polynomials or by any
from among several other transcribed spellings of that name.  The Handbook
of Mathematical Functions (Abramowitz-Stegun) is probably the first reference
you may wish to consult.
Enjoy, Gerhard
-- 
* Gerhard Niklasch  *** Some or all of the con-
* http://hasse.mathematik.tu-muenchen.de/~nikl/ ******* tents of the above mes-
* sage may, in certain countries, be legally considered unsuitable for consump-
* tion by children under the age of 18.  Me transmitte sursum, Caledoni...  :^/

The topological spaces that are used as model of the untyped lambda calculus, and
more generally the spaces used in semantics are embedded with the scott topology
which is never hausdorff.
see any book on semantics of lambda calculus for references, or domain theory.
As for authors, Scott, Smyth and Abramsky come to my mind..sorry for the others..
laurent

EUROCONFERENCE ON=20
CONFORMAL GEOMETRY AND  =20
=20
COMPLEX DYNAMICS =20
 =20
SAARISELK=C4, FINLAND, JUNE  9-13, 1997
The conference will take place at a congress and vacation resort in north=
ern
Lappland, well north of the polar circle: latitude 68.6 degrees. The even=
t
is a continuation of the activity of the earlier EC Human Capital and
Mobility network Conformal Geometry and Geometric Function Theory.
The program will consist of about 25 invited lectures 40 min each. A seco=
nd
announcement including prices for accommodation and travel arrangements w=
ill
be delivered by the end of February, 1997. There will be a limited amount=
 of
resources for young participants from EC countries.
Organizers:
=20
Kari Astala             Ilkka Holopainen            Seppo Rickman =20
astala@math.jyu.fi      ih@geom.helsinki.fi         rickman@cc.helsinki.f=
i=20
For more information you can contact either some of the organizers or the
secretary
Riitta Ulmanen
fax: +358-9-19123213  tel: +358-9-19122853
e-mail: ulmanen@sophie.helsinki.fi
Department of Mathematics
P. O. Box 4
00014 University of Helsinki, Finland
Martti Nikunen
Department of Mathematics
University of Helsinki
martti.nikunen@helsinki.fi

Hans Crauel  (which is me) wrote on a 
remark of Peter Flor  
 (PF) If S is a closed subset of [0,1] having measure one, then the 
 (PF) complement has measure zero. Being open, it must be empty. So 
 (PF) the answer to your question is " no". 
 () This does not answer the question. It is not asked for a _closed_ 
 () subset of the unit interval, but for a Borel (or a Lebesgue) set. 
The remark of Peter Flor does answer the question when taking into 
account the fact that a subset of an arbitrary subset of a topolog-
ical space is compact in the relative topology if and only if it is 
compact in the original topology. (Which does not hold when `compact' 
is replaced by `closed'.) 
Applied to the image of the Cantor set under a continuous map to 
[0,1] it follows that the image is compact in the relative topology 
of the image, whence also in the original topology of [0,1]. 
I overlooked that point. 
-- 
		Hans Crauel	crauel@saar.de
		Hellwigstr. 17, 66121 Saarbruecken
		+49-681-64516 

Alan Bain (alanb@chiark.greenend.org.uk) wrote:
: I'm interested in non-Hausdorff topological spaces (other than the trivial one)
: which have some mathematical significance, since most topological works seem
: to confine themselves to considerations of Hausdorff spaces, and their
: properties.   Are there any standard interesting non-Hausdorff spaces?
: 
: Alan Bain
: 
If X is a (non-compact) complex space, and S is a coherent sheaf on X
with an infinite-dimensional cohomology group $H^k(X,S)$, then
often this cohomology group is a non-Hausdorff space, because it
arises as a quotient of an infinite-dimensional Frechet vector space
by some non-closed subvectorspace.
More generally non-Hausdorff spaces often occur as quotient spaces
of Hausdorff spaces by not-too-nice equivalence relations.
Joerg

In article <3294B4EC.475A@nich-nsunet.nich.edu> math-vda@nich-nsunet.nich.edu writes:
>[Let A(n,k) be the (n choose k) x n matrix whose rows are characteristic
>functions of subsets of size k, and let B = A(n,k) A(n,m)^T]
>
>Question: What is the minimum number of rows of B with the property
>that every column contains at least an m?
This is the (n,k,m) covering design problem:  You want a list of
blocks of size k such that each m-tuple is in at least one block.
See the La Jolla Covering Repository,
http://sdcc12.ucsd.edu/~xm3dg/cover.html
for a review and a table of known bounds (which Adolf Muehl
and Uenal Mutlu, among others, keep beating for certain
parameters).
-- 
   /\   Greg Kuperberg        greg@math.ucdavis.edu
  /  \ 
  \  /  Recruiting or seeking a job in math?  Check out my Generic Electronic
   \/   Job Application form, http://www.math.ucdavis.edu/~greg/geja/

Suppose we are given a labelled tree T (acyclic digraph) with n vertices. 
How many connected subgraphs of T are there with m or fewer vertices? 
An upper bound is required, preferably tight.
Any ideas? References?
Progress so far:
The number is in O(n4^{m-2}). If T is linear then the number is (n-m)+1.
It is possible to calculate an expected value, though the formula is
pretty messy.
Thanks,
David Bryant.
-- 
*********************************************
David Bryant
Biomathematics Research Centre
University of Canterbury
Aotearoa/New Zealand

In article <57i4du$7v6@aurora.cs.athabascau.ca>,
Burt Voorhees  wrote:
>
>I have been looking at the properties of a family of polynomials
>generated by the recurrence relation
>
>               P(n+1) = xP(n) - P(n-1)
>
>               P(0) = 0,   P(1) = 1
Take a look into the vast amount of literature on orthogonal
polynomials. Your polynomials are scaled Chebyshev polynomials:
   P(n;x) = U_{n+1}(2x).
Not-too-difficult-to-read (maybe ;-) ):
Szegoe: "Orthogonal Polynomials", AMS Colloquium Publ., Vol. 23
Chihara: "An Introduction to Orthogonal Polynomials", New York 1978
    (out of print)
Freud: "Orthogonal Polynomials" Oxford 1971 (out of print)
Van Assche: "Asymptotics for Orthogonal Polynomials"
    Lecture Notes in Math. 1265, Springer 1987
Thomas

Hartmut Fuehr wrote:
> I am looking for multivariate analogues of Euler-MacLaurin's
> quadrature formula. Has anyone ever come across something
> of that kind ?
> I would appreciate any hints, references etc.
C. Muller and W. Freeden, Multidimensional Euler and Poisson
summation formulas, Resultante der Mathematik 3 (1980) 33-63.
I don't know of anything more recent.
In combinatorial asymptotics, one sometimes needs to approximate
multidimensional summations in the limit, where the quantity
tending to infinity is the number of dimensions.  Typically
the summand has approximately the shape of a multidimensional
gaussian but does not separate.  I have not been able to extract
suitable convergence results from the Muller-Feeden paper for
such problems, so I would very much like to hear from someone
who knows about it.
Brendan.

Hi,
	Does anyone know if there is some way to predict wether all of a given
matrix's eigenvalues will be positive?
					Thanks,
						Paulo C=E9sar Mendes
						cybertech@ax.apc.org

	In article <06n*zxZPm@news.chiark.greenend.org.uk>,
		Alan Bain  wrote:
> Are there any standard interesting non-Hausdorff spaces?
(1)  Posters to this newsgroup often _quote_ far too much.  I offer what
     I have quoted above as an example of how much is appropriate.
     (I don't claim to be an authority on this, so don't hesitate for
     more than 1/10000000000000000000000000000 seconds before expressing
     an opinion contrary to this.)
(2)  Although the extent of my knowledge of algebraic geometry is
     approximately zero, there is one small point that I think I can 
     state more clearly than has been done by the other replies to this
     query that I have seen.  Remember the equation of a hyperbola that
     you learned in kindergarten: x^2 - y^2 - 1 = 0.  The hyperbola is
     the set of all zeros of this second-degree polynomial.  Suppose you 
     decided to consider sets like this -- the zero-sets of polynomials
      -- to be the only _closed_ sets (and their complements to be the
     only _open_ sets).  That gives you a topology -- the Zariski
     topology -- that is used by algebraic geometers.  (Algebraic
     geometers seem to like algebraically closed fields so they might be
     more likely to thing about C^2 than R^2, the latter being where
     the hyperbola you graphed in kindergarten lives.  And they seem to
     like projective spaces because some things become simpler there, so
     some points at infinity would be added to the hyperbola, which would
     then become indistinguishable from an ellipse.)  The space you get
     in any case is a non-Hausdorff space.
	Mike Hardy
Michael Hardy
hardy@stat.umn.edu