Newsgroup sci.math.research 6164

Directory

"Paul Erdos Remembered"
	The regular Mathematics Department Colloquium of the
University of Illinois at Urbana-Champaign on November 7, 1996
will be "Paul Erdos Remembered". It will consist of short personal
rembrances. We invite prospective speakers to contact one of us. The
Colloquium will meet at 4:00 pm in 314 Altgeld Hall, with Coffee and Tea
at 3:15 pm in 321 Altgeld Hall.
Paul T. Bateman
Harold G. Diamond
Bruce Reznick

As part of the 1996-97 Emphasis Year in Homotopy Theory and its
Applications at Northwestern University, a workshop will be held from March
28-30 on interactions between higher-category theory and mathematical
physics. Talks will be presented by the following speakers:
J. Baez (UC-Riverside), L. Breen (Paris-Villetaneuse), J.L. Brylinski
(Penn. State), D. Freed (Texas-Austin), R. Street (Macquarie), J. Stasheff
(UNC) and D. Yetter (Kansas State).
This workshop will follow a conference "Current trends in algebraic
topology, with applications to algebraic geometry and theoretical physics"
to be held at Northwestern University from March 23-27.
For further information on the workshop, please contact the organizers Ezra
Getzler  and Misha Kapranov .

In article <55ksgt$o3j@rzsun02.rrz.uni-hamburg.de>, fc3a501@GEO.math.uni-hamburg.de (Hauke Reddmann) writes:
|> Suppose you have something like
|> 
|> p=y^2+1 q=2*y^2+3*y
|> , 
|> where y stands short for x^2-1.
|> 
|> You eliminate x to get f(p,q)=0. Am I right that
|> the resultant factors into two equal factors?
All that is happening here is that p and q are even functions, therefore
you can write p(x) = P(x^2), q(x) = Q(x^2).  If a_i and b_i are the roots
of P and Q respectively, c and d the leading coefficients, m and n the
degrees then the resultant of P and Q is
c^n d^m product_{i,j} (a_i - b_j)
The roots of p and q are (+/-) sqrt(a_i) and (+/-) sqrt(b_i), so each
factor (a_i - b_j) in the resultant of P and Q becomes 
(sqrt(a_i) - sqrt(b_j)) (sqrt(a_i)+sqrt(b_j)) (-sqrt(a_i)-sqrt(b_j))  
  (-sqrt(a_i)+sqrt(b_j)) = (a_i - b_j)^2
and the resultant of p and q is the square of the resultant of P and Q.
So if p and q have rational or integer coefficients, resultant(p,q) is the 
square of a rational or of an integer.
More generally if p and q are both functions of a k-th degree polynomial h(x),
(a_i - b_j) becomes product(r_k - s_l) where r_k are the roots of h(x)-a_i
and s_l are the roots of h(x)-b_j.  But this is (a_i - b_j)^k/L^k where
L is the leading coefficient of h.  So the resultant of p and q is
a k'th power.
|> And the other way, suppose I only known that
|> this happens, how can I compute the polynome in x
|> on which p and q depend on?
"This happens" meaning the resultant of p and q is a square?
Of course you can't.  For example, the resultant of 2 x + 1 and x + 5
is 9 = 3^2, but there is no nonlinear polynomial in x that these depend
on.
Robert Israel                            israel@math.ubc.ca
Department of Mathematics             (604) 822-3629
University of British Columbia            fax 822-6074
Vancouver, BC, Canada V6T 1Y4

If p(x) is a polnomial, \Sigma a_n x^n  of degree N, then
the reciprocal polnomial is q(x)=x^N p(x^-1).
Define r(x)=p(x)/q(x)
If z if on the unit circle in C, then z^{-1}=z^*, the conjugate of z in C.
Hence r(z) is also on the unit circle in C.
So r maps S^1 in C to S^1 in C.
Can anything more easily be said about r restricted on S^1 ?
Has anyone studied these in any detail ?
If we now consider r over the N^th cyclotomic field, if q is coprime to
(x^N-1)/(x-1), then r maybe written as a polynomial function on
the roots of unity in this field. Can anything nice be said about the
form of this polynomial ?
Cheers,
Robin

Dave Rusin (rusin@vesuvius.math.niu.edu) wrote:
: 
: I take it you mean you wish to compute what I called  r. I don't see in 
: general why there needs to be an  r  of the appropriate degree. The
: resultant of  p=x  and  q=x-4  is  4, a square, but there is no possibility
: of composites here. Arguably, the source of the problem is that your
: calculations are being done over too small a ring. If your  p  and  q
: had symbolic coefficients and a resultant which was a square in the
: corresponding polynomial ring, that would perhaps tell you something.
: 
Yes, I have some symbolic coefficients in my computation.
I better give an (longish) example:
I have u=(x^8+44x^6+192x^5+646x^4-1344x^3+2156x^2+2401)/
(8x(x^6+4x^5-19x^4-133x^2-196x+343)) and
v=(-x^8+4x^7+28x^6+412x^5+746x^4-2884x^3+1372x^2-1372x-2401)/
(16x(x^6+6x^5+7x^4+84x^3-49x^2+294x-343))
and want to write polynome(u,v)=0 by eliminating x.
So p=x^8+...-u*8*x*(...) etc. and the resultant
is some number*(32u^4v-16u^4-...)^2. I conclude that
I can write y=(x^2+...)/(f*x^2+...) and u,v will be
rational functions of y too. How do I find y? 
-- 
Hauke Reddmann <:-EX8 
fc3a501@math.uni-hamburg.de              PRIVATE EMAIL 
fc3a501@rzaixsrv1.rrz.uni-hamburg.de     BACKUP 
reddmann@chemie.uni-hamburg.de           SCIENCE ONLY

Right now I'm leafing through a 42-page paper by Luis de Branges
titled "A proof of the Riemann Hyptothesis". There is also a 23-page
companion "Apology for the proof of the Riemann hypothesis",
containing some autobiography and history of the problem.
My research field is far removed from de Branges' (my mathematical
ability even more so :-). Given the importance of the problem, I find
it strange that there has been no comment on s.m.r. What is the word
of the analysis experts? de Branges had some difficulty getting his
proof of the Bieberbach conjecture accepted, as I recall.
-- 
Stein A. Stromme ---  Matematisk institutt, Universitetet i Bergen
epost: stromme@mi.uib.no   telefon: 5558 4825   telefax: 5558 9672

Greg Stein wrote:
> Let p and r be distinct primes, d the order of p mod r, that is, p^d=1 mod
> r.  Let {i_1,...,i_k} be a k element subset of Z/dZ.  I know that if there
> is a number 0 then p^i1+...+p^ik=0 mod r, but I believe that this is iff and can't seem
> to get it the other way.  I'd be very greatful for any suggestions.
I don't think it's true. For instance, take r=17, p=3. Then the powers
of p mod r are
    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
    1  3  9 10 13  5 15 11 16 14  8  7  4 12  2  6
and we can take, for instance, the equation 1+2+3+11=0 (mod 17)
and translate that into p^0 + p^1 + p^7 + p^14 = 0, so that
your set of {ik} is {0,1,7,14}, and that's not invariant under
any translation mod 16.
-- 
Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
gjm11@pmms.cam.ac.uk Cambridge University, England.

Consider n distinct points in the d-dimensional unit cube. Of all 
(n-1)!/2 closed paths (or tours) passing through each point precisely 
once, what is the length L(n,d) of the shortest such path? 
Determining L(n,d), the minimum tour-length, is known as the 
traveling salesman problem (TSP). This is one of the best known 
combinatorial optimization problems, dominating fields like operations
research, algorithm development and complexity theory. Its solution is 
difficult because it cannot be computed in polynomial time, i.e., 
the problem is NP-hard. 
I'm interested in the case d=3 and the constant A, defined to be the
smallest constant such that
    		    L(n,3)
   lim sup      ---------------     <=    A
 n --> infty	   2
		  ---
		   3
		 n   * sqrt(3)
for *all* optimal tours in the cube.  According to Beardwood, Halton 
and Hammersley[1], a lower bound for A is given by
		2^(1/2) * 3^(-1/2) ~ 0.81649
This is their equation (7) and they claim the result follows by a
sphere packing argument.
But someone has recently told me that this should instead be
		2^(1/6) * 3^(-1/2) ~ 0.64805
since the best known sphere packing in 3-space has density
pi/(2*sqrt(3)).
Not being an expert in this field, I ask: who is right?  
Is the Beardwood, Halton and Hammersley result simply in 
error?  Or did they know something we don't?
For more background, please visit the web page
   http://www.mathsoft.com/asolve/constant/sales/sales.html
(Note that A is usually denoted by \alpha(3).)
					Thank you!
						Steve Finch
						sfinch@mathsoft.com
[1]J. Beardwood, J. H. Halton and J. M. Hammersley, The shortest 
path through many points, Proc. Cambridge Philos. Soc. 55 (1959) 
299-327. 

[ this is being posted on behalf of Lee Jacobi, who wrote it -- [drg] ]
I am concerned with non-trivial (non-zero) integer solutions to this 
problem. As far as I know, there are no previous (to mine) algebraic 
results or derivations for this problem, except for an incomplete 
derivation of the smallest solution by Norrie (1911), just 88 known 
solutions from computer search listed in Rose and Brudno, Mathematics 
of Computation Vol. 27, Number 123, 1973.
I am trying to obtain references to either more computer search 
solutions or any algebraic results or derivations. I have a method, 
sort of similar to Elkies' for his problem, which takes a specific 
known solution and algebracially derives another, i.e., an ever 
increasing infinite set of new solutions. This is not a general method 
yet, but this result is the only algebraic contribution to this 
problem as far as I know. I'm preparing a paper. What I wish here are 
any relevant references and signs of interest in my result.
Lee W. Jacobi

  ln (1 + x) = x - x^2 /2 + x^3 / 3 - ...
   so if f(0)=0, we have:
   ln (1 + f(x)) = f(x) - f(x)^2/2 + ...
 In particular, if f vanishes to order k at x=0, then
ln (1 + f(x)) = f(x) up to order 2(k+1).  
 Translating back to the original question, we see that
if f(x)>0 for all x, g(x)=ln f(x), we have
             (n)
     (n)    f  (c)
    g  (c)= ------
             f(c)
 for any c where the first (n-1)/2 (rounded down) derivatives 
of f vanish.  This means, as has been pointed out, that the 
original claim hold through n=3, but fails for n=4.  
 Kevin

In article <55l93p$trb@mikasa.iol.it>,
paolo cascini  wrote:
>> >can you find two space that are diffeomorph of class Cn for each n, but 
>> >that are not diffepmorph of class c-inf.
>
>I didn't speak about manifolds, but more generally 
>about subsets of R^n.
>I know that such example exists, but I don't know it.
Suppose you regard sets A and B in R^d as C^n diffeomorphic when
there is homeomorphism f : A -> B that extends to a C^n map
in a neighborhood of f.  Then one can make examples in R^d, d>1,
that are C^n but not C^{n+1} diffeomorphic, as follows.
First, choose sequences a_i -> 0, b_i -> 0 such that 
the map f(a_i)=b_i is C^n but not C^{n+1} (use Taylor's theorem).
Then, replace a_i and b_i each by a very tiny bouquet of i circles.
Let A, B be the union of these bouquets and the origin.
Then any homeomorphism f : A -> B must send the bouquet near the a_i
to the one near b_i, so it will fail to be C^{n+1} at the origin.
If the bouquets are chosen small enough and individually diffeomorphic,
we will however have A and B C^n equivalent.

Jason L. Russ wrote:
> 
> Hello,  I am considering doing my Master's research on
> computational issues in modeling a chaotic phenomenon
> and  am looking for suggestions.
> 
One of the newer, more practical areas in chaos research is
related to fluid mixing.  A simple experiment is to look at
a particle in an analytic two vortex system, as in the work of Aref [1]
with the blinking vortex.  
What's interesting is that in 2d flows where the velocity field
is deterministic and simple, particles subjected to the flowfield
exhibit chaos.  There are lots of excellent application areas for
chemical engineering [2].  
Consider taking a good look at this promising new field.
[1] Aref, H., "Stirring by Chaotic Advection", J. Fluid Mech., 
    vol. 143, p. 1, 1984.
[2] Ottino, J.M., "The Kinematics of Mixing: Stretching, Chaos,
and          Transport", Cambridge University Press., 1989.

let A,B be real n*n matrices and P the plane they span
It is easy to see that if AB=BA and A,B are diagonalizable then
every M in P is diagonalizable.
Is the converse true?

The trading arm of a major investment firm is seeking a quantitative
specialist for its New York based Analytical Equity Trading Group to
work with its senior professionals in the on-going development of
sophisticated statistical/econometric trading models and strategies. 
QUALIFICATIONS:
The successful candidate will have in-depth knowledge of financial
economics,  time series econometrics, stochastic processes and the
requisite skills necessary to design and implement strategies in a
sophisticated computer environment. Comfort in dealing with
Probabilistic notions such as Random Walk, Brownian Motion and
Martingale Theory, combined with Econometric ideas such as Stationarity,
Cointegration and Error-Correction Models is desirable.
This position would be ideal for someone with prior experience in a
related field, and/or academic training near or at the Ph.D. level.
CONTACT:
E-mail: nyrtd@ny.ubs.com
Please reply via email with either a resume or a short informal
description of yourself.  Please include a day & evening phone number.  
We are an Equal Opportunity employer.

In article  sfinch@math28.skiles.gatech.edu (Steven Finch -Rs. Calkin) writes:
>Consider n distinct points in the d-dimensional unit cube. Of all 
>(n-1)!/2 closed paths (or tours) passing through each point precisely 
>once, what is the length L(n,d) of the shortest such path? 
>
>[In particular, find A = lim n->infty L(n,3)/n^(2/3)]
There is a fairly simple argument that A >= 2^(1/6) which,
as suggested, uses sphere packing.
Take an fcc arrangement of points consisting of a cubic lattice with
edge length s and three face-centered translates.  Then (up to
small corrections), n = 4/s^3.  At the same time, the length
of a segment of a circuit is at least the minimum distance between
a pair of points, which is s/sqrt(2).  Thus,
L >= n*s/sqrt(2)
L/n^(2/3) >= 4^(1/3)/2^(1/2) = 2^(1/6)
-- 
   /\   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/

In article <55lr4f$pkt@geraldo.cc.utexas.edu>, robin@naomi.ma.utexas.edu (Robin Michaels) writes:
|> If p(x) is a polnomial, \Sigma a_n x^n  of degree N, then
|> the reciprocal polnomial is q(x)=x^N p(x^-1).
|> 
|> Define r(x)=p(x)/q(x)
|> 
|> If z if on the unit circle in C, then z^{-1}=z^*, the conjugate of z in C.
|> 
|> Hence r(z) is also on the unit circle in C.
|> 
|> So r maps S^1 in C to S^1 in C.
|> 
|> Can anything more easily be said about r restricted on S^1 ?
|> Has anyone studied these in any detail ?
I think you mean q(x) = x^N p(1/x^*)^*.  Thus if p(x) = sum(a_n x^n),
q(x) = sum(a_n^* x^(N-n)).  Of course you have to assume p(x) has no
zeros on S^1.
One thing that can be said is: 
Any meromorphic function taking S^1 to S^1 will be of the form c x^n p(x)/q(x)
where c is a constant in S^1, and n is an integer.  (We can absorb the x^n into
p(x) if n > 0) 
Proof: if f takes S^1 to S^1, then by analytic continuation
f(x) = 1/f(1/x^*)^*.  This implies that f(x) has a pole at x=w if and only
if it has a zero at x=1/w^* (with the same multiplicity).  Multiplying
by a suitable power of x, we may assume 0 is neither a pole nor a zero of f.
Since there are only a finite number of poles and zeros inside the circle, 
there are only a finite number in all, and f(x) is a rational function.
If p(x) is the product of x-w for all the zeros w (counting multiplicity), 
then q(x) is a constant times the product of x-1/w* for all zeros.  
Thus f(x) q(x)/p(x) is a rational function with no poles or zeros, therefore a constant.
Robert Israel                            israel@math.ubc.ca
Department of Mathematics             (604) 822-3629
University of British Columbia            fax 822-6074
Vancouver, BC, Canada V6T 1Y4

In article <55n5m3$acm@rzsun02.rrz.uni-hamburg.de>,
Hauke Reddmann  wrote:
>Yes, I have some symbolic coefficients in my computation.
>I better give an (longish) example:
>
>I have u=(x^8+44x^6+192x^5+646x^4-1344x^3+2156x^2+2401)/
>(8x(x^6+4x^5-19x^4-133x^2-196x+343)) and
>
>v=(-x^8+4x^7+28x^6+412x^5+746x^4-2884x^3+1372x^2-1372x-2401)/
>(16x(x^6+6x^5+7x^4+84x^3-49x^2+294x-343))
>
>and want to write polynome(u,v)=0 by eliminating x.
>So p=x^8+...-u*8*x*(...) etc. and the resultant
>is some number*(32u^4v-16u^4-...)^2. I conclude that
>I can write y=(x^2+...)/(f*x^2+...) and u,v will be
>rational functions of y too. How do I find y? 
I'm not quite sure I agree with everything you're saying here, but I think
I can answer the final question.
So you have two rational functions  u(x)  and  v(x)  and wish to find a
rational function  y(x)  for which it is possible to express
	u = u' o y
	v = v' o y
for some rational functions  u'  and  v'. That is, you are looking for
a common right-factor to  u  and  v  in the semigroup of all rational 
functions (where the product is  composition).
Of course one could take  y  to be any invertible element in this
semigroup, that is, you could take  y  to be a Moebius transformation,
but I expect you mean you want a nontrivial factorization. Indeed, you
have suggested taking   y  to be a quotient of quadratics.
I'd like to point out first that this is essentially the only way to
factorize your  u  and  v. Define the _degree_ of a rational function to
be the maximum of the degrees of its numerator and denominator. It's
easily seen to be the same as the degree of that function viewed topologically
as a map  f: S^2 -> S^2, that is, it's the cardinality of the inverse image
of a generic point (here  S^2  is the Riemann sphere). Since your  u  and  v
are of degree  8, and since degree of composites multiply, the only
nontrivial factorizations  u = u' o y  which would be possible would have
{degree u', degree y} = {2,4}.
Next let me observe that given any factorization one could adjust it to
u = (u' o h^(-1)) o (h o y)  where  h  is any unit, i.e., any Moebius
transformation. If we had such a factorization, then, we could choose  h
to send  y(0)  to 0, y(1)  to  1, and  y(\infty) to \infty, so that
y  can be assumed to have the simpler forms
	y = x ( 1 + a(x-1) )/( 1 + b(x-1) ).
(One must be careful here: such an  h  can be found assuming  y(0), y(1),
and y(\infty) are distinct. The exceptional cases can likewise be reduced
to the special forms  y =  x(x-1)/(x-a), x/(x-1)/(x-a), or  (x-1)/x/(x-a).)
Thus in general if you wish to factor a rational function you can reduce
the size of your search by normalizing the choices.
Next I will show how to identify possible factors.
Consider the effect of a composite  u = u' o y  on the Riemann sphere. As I
noted, the inverse images of most points under this map will have  8  points,
as can be seen by clearing denominators in the equation  u(x) = c. There
are values of  c  for which  u^(-1)(c)  has fewer points; these require that
the previous polynomial equation have a common solution with its derivative.
Eliminating  x  from this equation shows precisely which values of  c  are
singular: these  c's  are the roots of a certain degree-8 rational polynomial.
(Actually it's a polynomial in  c^2, and has  (c^2-625/56) as a factor).
Eliminating  c  between this equation and  u(x)=c  gives a necessary
condition on  x  that it be a singular point; another condition comes from
eliminating  c  from the derivative. The GCD of these equations is then the
minimal polynomial of the singular points: it factors as (x^2+14x-7)*
(x^12 -6 x^11 + ... 117649). Computing roots gives the singular points: 
	-14.483, -3.72,  -0.693, 0.4833, 1.88, 10.09, 
	-1.88 +- 5.46 I, -1.26 +- 1.70I,  .395+- 1.145 I, 1.97+-2.66I
Now, the point of all this computation is that the degree-2 map  y  _also_
has two singular points, which it must share with any composite  u' o y. 
Moreover, the other singular points of  u  should be the points  
y^(-1)(y0),where  y0  is one of the singular points of  u'.
Suppose for example there was a factor of the form  y(x)=x(x-1)/(x-a).
Its two singular points must be among the singular points listed above.
For each of the 14 values of  x  listed above, we can determine what  a
must be. As it turns out, each of the values of  x  yields a different  a
(contradicting the statement that _both_ critical points of  y(x)
are to be on the above list) unless a=-7; thus this is the only possible
choice for a factor.
Checking further, we see that the other  12  points  x  fall into pairs
for which  x(x-1)/(x+7)  has the same value. Thus this function  y(x)
passes the critical-point test.
Indeed, we then eliminate  x  from the equations  u(x)=u  and  y(x)=y,
we find that
                                         2      3    4
                            1 + 4 y + 22 y  + 4 y  + y
                        u = ---------------------------
                               8 y (y - 1) (y + 1)
so that, yes,  u  does have  y  as a factor in this semigroup.
Now, you had hoped to find a _common_ factor with  v. As luck would have it,
one can similarly eliminate  x  from the defining formula for  v  and deduce
                          2              2
                        (y  + 6 y + 1) (y  - 6 y + 1)
                  y = - -----------------------------
                                           2
                               16 y (y + 1)
Thus a choice for the substitution you seek is
	y(x) = x (x+1) / (x+7).
Notice that the method I have proposed for finding a common factor of
two rational functions requires actually factoring one of them first.
By comparison with the factorization in Euclidean domains, one might
hope for something quicker; I'm not sure how this would be possible,
although it does save some time by reducing the collection of candidates
for the singular points of  y  and so on.
Surely someone has previously considered the question of factorization
in this semigroup, but I have no idea where to find such algorithms.
dave

In article , stromme@mi.uib.no (Stein A.
Stromme) wrote:
> My research field is far removed from de Branges' (my mathematical
> ability even more so :-). Given the importance of the problem, I find
> it strange that there has been no comment on s.m.r. What is the word
> of the analysis experts? de Branges had some difficulty getting his
> proof of the Bieberbach conjecture accepted, as I recall.
The reason he had trouble with the Bieberbach conjecture was that he had
frequently announced proofs of difficult problems (the invariant subspace
problem is another example) but most of the time the proofs turned out to
be wrong.  This is far from the only purported proof of the Riemann
hypothesis that de Branges has produced.
This does not mean, of course, that the proof is wrong.  But it does mean
that it can take some time before an expert in the field summons up enough
energy to check his proof carefully.
-- 
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

I wrote
>let A,B be real n*n matrices and P the plane they span
>It is easy to see that if AB=BA and A,B are diagonalizable >then
>every M in P is diagonalizable.
>Is the converse true?
The conjecture I submitted can easily be proven false for real matrices,
but perhaps it is true for complex ones.