mm-3209 === Subject: ANN: An XML format for block designs A standard format for block designs and their properties (A proposal and an invitation for public debate) At DesignTheory.org we are developing a web-based Design Theory Resource Server for combinatorial and statistical design theory. These resources will include an online database of designs, an Encyclopaedia of Design Theory, and software packages for the generation and analysis of designs. We hope to address the needs of both researchers and practitioners of design theory. One critical element is our XML format to represent designs and their properties in a standard platform-independent manner. This will allow for the straightforward exchange of designs and their properties between various computer systems, including databases and web servers, and combinatorial, group theoretical and statistical packages. The XML format will also be used for outside submissions to our design database and to store designs in perpetuity. Our initial development is in the area of block designs, and we invite you to read and comment on our proposal for the External Representation of Block Designs, available online at: http://designtheory.org/ Please send your comments (and follow-ups) exclusively to: developers@designtheory.org This is a mailing list to which you are welcome, although not required, to join. Alternatively, you can follow the discussions through the public archives of the list. For further details, please visit: http://designtheory.org/mailing.html We will finalize the XML format for block designs after sufficient public debate, after which we shall release GAP [1], R [2], and Python [3] software for block designs. We are committed to the open source model and all products of our development will be released to the public free of charge. We shall also start developing a database of block designs, and look forward to your contributions (in the XML format) to this database. Please feel free to forward this announcement to anyone you think may be interested. [1] GAP - Groups, Algorithms and Programming http://www.gap-system.org/ [2] The R Project for Statistical Computing http://www.r-project.org/ [3] The Python programming language http://www.python.org/ === Subject: Re: High-dimensional Fredholm problems Epigone-thread: reurunvy >Hi. >Can anybody point me to examples of linear Fredholm equations of the >second kind that occur over domains of very high (even better, of >arbitrary) dimension? The examples with which I'm familiar occur >over intervals, curves, and boundaries of three-dimensional regions. I'm quite sure that the following textbook might be worthwhile to you to find what you are looking for: Sobolev, S.L. Nekotorye primeneniya funktsional'nogo analiza v matematicheskoj fizike. 'Some applications of functional analysis to mathematical physics' 3rd ed., rev. and compl., ed. by O. A. Olejnik. Moskva: Nauka. 334 p. (1988). You may order the english translation of this book at http://www.amazon.com If you do not want to buy it, I'm sure you'll find a translated copy in some university library that is within reach of a sufficiently small vicinity of the place you reside. Hope this helps M. Doerfner === Subject: Is this a famous problem? Here's a puzzle which made the rounds in 1967. Is it still well known? To me it seems more elegant and interesting than the Goldbach or Collatz Conjecture, To state the problem, one definition is needed: Y(S) = max (n / gcd(n,m)) n,m in S Problem: Find every finite subset S of the positive integers such that Y(S) = |S| or Y(S) < |S|. (|S| is the size of S.) Demonstrate that no satisfactory S has been overlooked. James Dow A (at yahoo) (This, run all together, is my e-mail address. === Subject: Number of cyclic digraphs without sources nor sinks Epigone-thread: clangshedi > A cyclic digraph is a digraph in which every vertex is in a cycle. In > other words, cyclic digraps are non-acyclic digraphs. > In a digraph, a source is a vertex with in-set of size zero; a sink is > a vertex with out-set of size zero. > I would like to know the number of labeled cyclic digraphs on n > vertices without sources nor sinks. Here is a way to count labelled digraphs in which every node belongs to a directed cycle (clearly they have neither sources nor sinks). Let K be a class of strongly connected digraphs (closed wrt relabelling the nodes) and s_n(K) denote the number of digraphs with n labelled nodes in it. a_n(K) denotes the number of all digraphs with n nodes whose strong components belong to K. Introduce the following formal generating functions: s(z,K):= sum_{n>0}s_n(K)z^n/n!, a(z,K):= sum_{n>0}a_n(K)z^n/(n!2^{n(n-1)/2}), u(z,K):= sum_{n>0}u_n(K)z^n/n! := 1-1/(1+a(z,K)) and v(z,K):= sum_{n>0}v_n(K)z^n/n!, where v_n(K):= 2^{n(n-1)/2}u_n(K). Then the following general equation takes place: s(z,K) = -log(1-v(z,K)) (*) (see V.A.Liskovets, On a general enumerative scheme for labelled graphs, Dokl. AN BSSR, 21:6 (1977), 496-499 (in Russian); MR58#21797). In particular for the class K = D of ALL strongly connected digraphs (without loops and multiple edges), _including_ the 1-node digraph [.], we have s(z,D) = -log(1-v(z,D)) and a_n(D) = 2^{n(n-1)} = #(all digraphs). Thus, a(z,D) = sum_{n>0}2^{n(n-1)/2}z^n/n!, u(z,D) = sum_{n>0}u(n)z^n/n! = 1-1/(1+a(z,D)) and v(z,D) = sum_{n>0}2^{n(n-1)/2}u_n(D)z^n/n!. s_n(D) for n=1,2,3,... is the OEIS sequence A003030 =_1_,1,18,1606,... The digraph [.] is the ONLY type of strong components whose nodes do not belong to any cycle. In order to exclude such nodes, let us eliminate [.] from D and denote C:= D-{[.]}. Then we have s(z,C) = s(z,D)-z. By (*), s(z,C) = -log(1-v(z,C)), whence v(z,C) = 1-exp(z-s(z,D)) = 1-exp(z+log(1-v(z,D))) = 1-exp(z)(1-v(z,D)). Now knowing v(z,C), we obtain u(z,C) = sum_{n>0}v_n(C)z^n/(n!2^{n(n-1)/2}) and a(z,C) = 1/(1-u(z,C))-1 = sum_{n>0}a_n(C)z^n/(n!2^{n(n-1)/2}). The coefficients a_n(C) are the desired numbers of cyclic digraphs: the ones in which all n labelled nodes belong to (directed) cycles. Numerically a_n(C) for n=1,2,3,... are 0,1,18,1699,587940, 750744901,... The difference a_4(C)-s_4(D) = 93 is verifiable easily by hand, as well as A086193(5)-a_5(C) = 5*6*9*16 = 4320 (it's evident that a_4(C) = A086193(4)). Btw, the acyclic digraphs can be counted in the same way with 1-node components only: K:= {[.]}. Besides (curiously), u_n(D) is the number of strong tournaments (A054946). Valery Liskovets === Subject: a question on probability distributions and generating functions Epigone-thread: frumgomwerl Hey, Let X and Y be two discrete nonnegative random variables. We say that X>Y, if Pr(X > t) >= Pr(Y > t), for all t>=0 Let z>0 be an arbitrary constant. Clearly, we get also : Pr(z^X > z^Y) >= Pr(z^Y > z^t) for all t, therefore z^X > z^Y. Since this is true for all z, we get that E(z^X) >= E(z^Y) for all z<1, so the generating function of X is greater than the generating function of Y for 0= E z^y for 0<=z<=1, can we conclude that X > Y? Thanx for your time, Dan === Subject: Re: a question on probability distributions and generating functions >Hey, >Let X and Y be two discrete nonnegative random variables. >We say that X>Y, if Pr(X > t) >= Pr(Y > t), for all t>=0 >Let z>0 be an arbitrary constant. Clearly, we get also : Pr(z^X > z^Y) >>= Pr(z^Y > z^t) for all t, therefore z^X > z^Y. Since this is true ??? Note that t -> z^t is _decreasing_ if 0 < z < 1 but increasing if z > 1. I think what you mean is Pr(z^X < z^t) >= Pr(z^Y < z^t) for 0 < z < 1 so z^Y > z^X >for all z, we get that E(z^X) >= E(z^Y) for all z<1, so the generating >function of X is greater than the generating function >of Y for 0= E[z^X] for 0 < z < 1. The generating function of Y is greater than that of X for 0 < z < 1. >My question is, is the other way around also true ? That is, >if E z^X >= E z^y for 0<=z<=1, can we conclude that X > Y? No. For example, let X = 1 with probability 1, while Y = 0 with probability 1/2 and 2 with probability 1/2. Since Pr(X<1) < Pr(Y<1) while Pr(X<2) > Pr(Y<2), neither XY --> E(z^X) <= E(z^Y) for z < 1, and E(z^X) >= E(z^Y) for z > 1. (Clearly at 1 we have an equality : E(1^X) = E(1^Y) = 1). So is the other way around true? I mean , i would like to know if it is true that : ---| E(z^X) <= E(z^Y) for z < 1, and | E(z^X) >= E(z^Y) for z > 1. |---> X>Y ---| (As was mentioned in your counter example we had E(z^X) <= E(z^Y) for all z, so it is not a counterexample to the rephraised quesion). Thanx, Dan >Hey, >Let X and Y be two discrete nonnegative random variables. >We say that X>Y, if Pr(X > t) >= Pr(Y > t), for all t>=0 >Let z>0 be an arbitrary constant. Clearly, we get also : Pr(z^X > z^Y) >>= Pr(z^Y > z^t) for all t, therefore z^X > z^Y. Since this is true > ??? Note that t -> z^t is _decreasing_ if 0 < z < 1 but increasing if > z > 1. I think what you mean is > Pr(z^X < z^t) >= Pr(z^Y < z^t) for 0 < z < 1 so z^Y > z^X >for all z, we get that E(z^X) >= E(z^Y) for all z<1, so the generating >function of X is greater than the generating function >of Y for 0 ... and E[z^Y] >= E[z^X] for 0 < z < 1. The generating function of > Y is greater than that of X for 0 < z < 1. >My question is, is the other way around also true ? That is, >if E z^X >= E z^y for 0<=z<=1, can we conclude that X > Y? > No. For example, let X = 1 with probability 1, while Y = 0 with > probability 1/2 and 2 with probability 1/2. Since Pr(X<1) < Pr(Y<1) > while Pr(X<2) > Pr(Y<2), neither X generating functions E[z^X] = z and E[z^Y] = (1+z^2)/2 satisfy > E[z^X] <= E[z^Y] for all z. > Robert Israel israel@math.ubc.ca > Department of Mathematics http://www.math.ubc.ca/~israel > University of British Columbia > Vancouver, BC, Canada V6T 1Z2 === Subject: Re: Rephraising of the question >We know that X>Y --> E(z^X) <= E(z^Y) for z < 1, and > E(z^X) >= E(z^Y) for z > 1. >(Clearly at 1 we have an equality : E(1^X) = E(1^Y) = 1). >So is the other way around true? I mean , i would like to know if it >is true that : > ---| >E(z^X) <= E(z^Y) for z < 1, and | >E(z^X) >= E(z^Y) for z > 1. |---> X>Y > ---| No. Consider the case where X = 1 with probability 3/4, 3 with probability 1/4 Y = 0 with probability 1/4, 2 with probability 3/4 E[z^X]-E[z^Y] = -1/4 + 3/4 z - 3/4 z^2 + 1/4 z^3 = -(1-z)^3/4 < 0 for z < 1 and > 0 for z > 1. But Pr(X<2) > Pr(Y<2), so it's not true that X>Y Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 === Subject: Re: Polynomials times a Gaussian are dense in L^2 > What's an easy low-brow way to prove that polynomial > functions times the Gaussian exp(-x^2) are dense in L^2(R)? The way we were given in lectures was as follows. Since the trigonometric polynomials are uniformly dense in C[a,b] it is easy to see that the space of finite linear combinations of functions of the form: e^(iax)e^(-x^2/2) (a = 0,1,2,...) is uniformly dense in C_0(R) (the space of continuous functions on R functions of the form p(x)e^(-x^2/2) (where p is a polynomial) is uniformly dense in C_0(R). Now given f in L^2(R) first approximate it in L^2 by continuous g with compact support (as in previous messages) then uniformly approximate g(x)e^(x^2/2) by functions of the form p(x)e^(-x^2/2) where p is a polynomial. It is easy to see this gives an L^2 approximation of g by functions of the form p(x)e^(-x^2) so we're done. Michael === Subject: Re: Polynomials times a Gaussian are dense in L^2 >> What's an easy low-brow way to prove that polynomial >> functions times the Gaussian exp(-x^2) are dense in L^2(R)? >The way we were given in lectures was as follows. Since the >trigonometric polynomials are uniformly dense in C[a,b] it is easy to >see that the space of finite linear combinations of functions of the >form: >e^(iax)e^(-x^2/2) (a = 0,1,2,...) >is uniformly dense in C_0(R) (the space of continuous functions on R >tending to 0). That's clear. >functions of the form p(x)e^(-x^2/2) (where p is a polynomial) is >uniformly dense in C_0(R). How does one deduce that, exactly? >Now given f in L^2(R) first approximate it in L^2 by continuous g with >compact support (as in previous messages) then uniformly approximate >g(x)e^(x^2/2) by functions of the form p(x)e^(-x^2/2) where p is a >polynomial. It is easy to see this gives an L^2 approximation of g by >functions of the form p(x)e^(-x^2) so we're done. >Michael ************************ David C. Ullrich === Subject: Re: Polynomials times a Gaussian are dense in L^2 >>The way we were given in lectures was as follows. Since the >>trigonometric polynomials are uniformly dense in C[a,b] it is easy to >>see that the space of finite linear combinations of functions of the >>form: >>e^(iax)e^(-x^2/2) (a = 0,1,2,...) Oops, meant to say a is an integer rather than non-negative integer. In fact the rest of the proof goes through fine if you only restrict a to being in R. >>is uniformly dense in C_0(R) (the space of continuous functions on R >>tending to 0). >That's clear. >>functions of the form p(x)e^(-x^2/2) (where p is a polynomial) is >>uniformly dense in C_0(R). >How does one deduce that, exactly? Well it suffices to prove e^(iax)e^(-x^2/2) can be uniformly approximated on R by p(x)e^(-x^2/2). Let p_n be the first n terms of the Taylor series of e^(iax). By the triangle inequality: |e^(iax)e^(-x^2/2)-p_n(x)e^(-x^2/2)| <= e^(|a||x| - x^2/2) so this is < epsilon outside some compact interval I, for all n. But p_n(x) -> e^(iax) uniformly on I so we're done. Michael === Subject: Re: Polynomials times a Gaussian are dense in L^2 >The way we were given in lectures was as follows. Since the >trigonometric polynomials are uniformly dense in C[a,b] it is easy >see that the space of finite linear combinations of functions of the >form: >e^(iax)e^(-x^2/2) (a = 0,1,2,...) >Oops, meant to say a is an integer rather than non-negative integer. >In fact the rest of the proof goes through fine if you only restrict a >to being in R. >is uniformly dense in C_0(R) (the space of continuous functions on R >tending to 0). >>That's clear. >functions of the form p(x)e^(-x^2/2) (where p is a polynomial) is >uniformly dense in C_0(R). >>How does one deduce that, exactly? >Well it suffices to prove e^(iax)e^(-x^2/2) can be uniformly >approximated on R by p(x)e^(-x^2/2). Let p_n be the first n terms of >the Taylor series of e^(iax). By the triangle inequality: >|e^(iax)e^(-x^2/2)-p_n(x)e^(-x^2/2)| <= e^(|a||x| - x^2/2) Well duh. Took me a second to see why that inequality was true, but yes, it's clear. This is the simple proof I was coming to think didn't exist. Keen. >so this is < epsilon outside some compact interval I, for all n. But >p_n(x) -> e^(iax) uniformly on I so we're done. >Michael ************************ David C. Ullrich === Subject: Re: Polynomials times a Gaussian are dense in L^2 >> What's an easy low-brow way to prove that polynomial >> functions times the Gaussian exp(-x^2) are dense in L^2(R)? The problem is harder than it looks. The property of the function exp(-x^2) which is needed is that the corresponding moment problem must have a unique solution. This looks like an L_1 condition, but everything between 1 and 2 is equivalent for this problem, and the usual nasc conditions can easily be obtained by L_2 arguments. This is easy, but lengthy, so I do not think it is what is being desired. It can be done with only real analysis, but using complex numbers. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Department of Statistics, Purdue University hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558 === Subject: Re: Polynomials times a Gaussian are dense in L^2 >What's an easy low-brow way to prove that polynomial >functions times the Gaussian exp(-x^2) are dense in L^2(R)? >I know a general-purpose L^2 Stone-Weierstrass theorem >that does the job, but it requires knowing the Fourier >transform is unitary, which takes a while to prove. >I also know the eigenfunctions of the harmonic oscillator >Hamiltonian are an orthonormal basis of L^2(R), and this >also does the job, but again it relies on some stuff that >takes work to prove. >For a class I plan to teach, I'd like a quick proof >that doesn't use much machinery, if one exists. It's possible that there is no proof as elementary as what you want. The following fact surprised me: Fact: There exists a function G such that (*) G > 0, G is continuous, and x^n G(x) -> 0 as x -> infinity, for n = 0, 1, ..., such that the functions P(x) G(x) are _not_ dense in L^2(R) (note that the fact that x^n G(x) -> 0 for all n shows that P(x) G(x) is in L^2 for every P.) My point is that thinking about a totally low-brow proof of what you want I assumed it would follow just from the fact that G(x) = exp(-x^2) satisfies (*). But it doesn't follow from (*), so any proof must use some more special property of exp(-x^2). (In particular it's not clear that, for example, Nemo's argument can be fixed - that was the sort of argument I was looking for for a while...) Proof of the Fact: Let phi be infinitely differentiable on R, with support(phi) contained in [1,2] (and phi not identically 0.) Let F^ = phi (where F^ is the Fourier transform of F.) Then F is a Schwarz function, so in particular F(x) (1 + |x|^n) is in L^2 for n = 0, 1, ... . So we can choose numbers c_n > 0 such that f is in L^2(R), where f(x) = F(x) sum(c_n (1 + |x|^n)) (and also such that sum(c_n (1 + |x|^n)) is continuous, in case that doesn't follow.) Let G(x) = 1 / sum(c_n (1 + |x|^n)). It's clear that G satisfies (*). But the P(x) G(x) are not dense in L^2, because f is orthogonal to all of them: = = linear combination of derivatives of F^ at the origin = 0. ************************ David C. Ullrich === Subject: Re: Polynomials times a Gaussian are dense in L^2 >> What's an easy low-brow way to prove that polynomial >> functions times the Gaussian exp(-x^2) are dense in L^2(R)? >Suppose that f is in L^2(R) and is orthogonal to all such products. >Expanding exp(zx) in a power series and using Fubini's theorem, check >that >int_R f(x) exp(zx) exp(-x^2) dx = 0, >first for all complex z of sufficiently small modulus, then for all >complex z by analytic continuation. In particular, >int_R f(x) exp(-itx) exp(-x^2) dx = 0, >for all real t. As f(x)exp(-x^2) is clearly an element of L^1(R), >this last display means that the Fourier transform of f vanishes. >Thus f = 0, almost everywhere. Yeah, I thought of suggesting more or less that (don't see why we need to restrict to z of small modulus.) But it uses the uniqueness theorem for the Fourier transform; since the OP specified he didn't want to use the Plancherel theorem I decided this was insufficiently low-brow. There must be a proof that doesn't depend on anything remotely non-trivial about the Fourier transform, along the lines of Nemo's almost-proof. Not that I see what it is... ************************ David C. Ullrich === Subject: category question Is there a term for a category whose morphisms can be expressed in terms of composion through a single object? Namely, there's an object A in the category such that for objects B and C, Hom(B,C) is Hom(B,A) composed with Hom(A,C). Ie, the morphisms to and from A generate all morphisms in the category. I'm also looking for a more general version, a category where the morphisms to and from a finite set of objects generate the morphisms in the category. Any help included you. Karl Hallowell khallow@hotmail.com === Subject: Re: category question |Is there a term for a category whose morphisms can be expressed in |terms of composion through a single object? Namely, there's an object |A in the category such that for objects B and C, Hom(B,C) is Hom(B,A) |composed with Hom(A,C). Ie, the morphisms to and from A generate all |morphisms in the category. I'm also looking for a more general |version, a category where the morphisms to and from a finite set of |objects generate the morphisms in the category. Any help included |you. when every morphism in category d factors through an object in full subcategory e, d is called a full subcategory of the karoubi envelope of e. -- [e-mail address jdolan@math.ucr.edu] === Subject: Re: Goldbach-Idea - probably dumb! I remember reading in a book, I think Recreations in the Theory of Numbers by Dover, about lucky numbers, which are derived using something like the Sieve of Eratosthenes, but with a different rule to strike out the numbers. The numbers surviving the sieve are lucky and include some primes and some composites. If I remember correctly, the book said that the lucky numbers have properties similar to the primes as far as their distribution, twin lucky numbers, and also obey a Goldbach-like Conjecture. > Just thought I'd throw in my 2 cents on Goldbach. Not my area, but the > thread made me think of the following. > If you were to generate a set of false primes by insisting that in > any interval they are distributed amongst the odd numbers with the > same frequency as the real ones (we can forget about 2), > What is the probability that such a set has the Goldbach property > (i.e. any even number can be expressed as the sum of two false > primes)? Is it non-zero? What would the limit of this probability be > if one only had to start looking after an arbitrarily large n? > My really stupid idea was that if (subject to some reasonable > verification method for sets of false primes being stated) the > probability was non-zero, then the Goldbach conjecture could be true > by accident. > If however the probability does tend to zero, then surely the > conjecture is equally fascinating! > I'm no number theorist, but would love to know if anyone's thought > along these lines. === Subject: Re: Goldbach-Idea - probably dumb! > I remember reading in a book, I think Recreations in the Theory of > Numbers by Dover, about lucky numbers, which are derived using > something like the Sieve of Eratosthenes, but with a different rule to > strike out the numbers. The numbers surviving the sieve are lucky > and include some primes and some composites. If I remember correctly, > the book said that the lucky numbers have properties similar to the > primes as far as their distribution, twin lucky numbers, and also obey > a Goldbach-like Conjecture. Indeed for a whole class of sieve generated sequences one can prove a prime number theorem. See some papers (from the 70s, I think) by Wunderlich, et al. I seem to recall (and this just may be wishful thinking) that there is even a Riemann hypothesis that goes along with this that is true. Don > Just thought I'd throw in my 2 cents on Goldbach. Not my area, but the > thread made me think of the following. If you were to generate a set of false primes by insisting that in > any interval they are distributed amongst the odd numbers with the > same frequency as the real ones (we can forget about 2), What is the probability that such a set has the Goldbach property > (i.e. any even number can be expressed as the sum of two false > primes)? Is it non-zero? What would the limit of this probability be > if one only had to start looking after an arbitrarily large n? My really stupid idea was that if (subject to some reasonable > verification method for sets of false primes being stated) the > probability was non-zero, then the Goldbach conjecture could be true > by accident. If however the probability does tend to zero, then surely the > conjecture is equally fascinating! I'm no number theorist, but would love to know if anyone's thought > along these lines. === Subject: when gcd does not exist? Epigone-thread: roahaithang I started reading Ireland and Rosen's A Classical Introduction to Modern Number Theory and noticed a remark that in an arbitrary ring the greatest common divisor not necessarily exists. I couldn't exhibit an example. Could you give an example of integral domain such that there exist two elements a,b, but there is no their greatest common divisor? An element d in R is called the greatest common divisor (gcd) of elements a and b from R, if (a) d|a and d|b; (b) d'|a and d'|b implies d'|d. If R is integral domain, then any two gcd's of a and b are associated (differ by a unit). === Subject: Re: when gcd does not exist? [student] | Could you give an example of integral domain such that there exist two | elements a,b, but there is no their greatest common divisor? Magidin gave you one example, here is a similar one, which you may like better, depending on your taste: Let k be a field and consider the integral domain k[x,y,z,w] = k[X,Y,Z,W]/(XY-ZW). Let a = xy = zw and b = xz. Then both x and z are common divisors, they are both of maximal degree, and they are distinct. Both are maximal, but none of them is greatest. (Since the relation is homogeneous, the ring has an obvious grading which we can use for the same purpose as the norms in Magidin's example.) -- Stein Arild Strmme +47 55584825, +47 95801887 Universitetet i Bergen Fax: +47 55589672 Matematisk institutt www.mi.uib.no/stromme/ Johs Brunsg 12, N-5008 BERGEN stromme@mi.uib.no === Subject: Re: when gcd does not exist? >I started reading Ireland and Rosen's A Classical Introduction to >Modern Number Theory and noticed a remark that in an arbitrary ring >the greatest common divisor not necessarily exists. I couldn't exhibit >an example. >Could you give an example of integral domain such that there exist two >elements a,b, but there is no their greatest common divisor? Not that it matters, as there are examples with integral domains, but you do notice the difference between arbitrary ring and integral domain? >An element d in R is called the greatest common divisor (gcd) of >elements a and b from R, if >(a) d|a and d|b; >(b) d'|a and d'|b implies d'|d. >If R is integral domain, then any two gcd's of a and b are associated >(differ by a unit). Let R = Z[sqrt(-5)], a=6, b=2+2*sqrt(-5). The elements of R are of the form x+y*sqrt(-5) with x and y integers, and with the obvious addition and multiplication. Both a and b are multiples of both 2 and 1+sqrt(-5). So a gcd for a and b would have to be a common multiple of 2 and 1+sqrt(-5). Consider the norm function, N:Z[sqrt(-5)] -> Z, given by N( x+y*sqrt(-5) ) = x^2 + 5y^2. It is an easy exercise to verify that: (i) N is multiplicative: N(r*s) = N(r)N(s) for all r,s in Z[sqrt(-5)]. (ii) If r divides s in Z[sqrt(-5)], then N(r) divides N(s) in Z. (iii) r is a uni in Z[sqrt(-5)] if and only if N(r)=1, if and only if r=1 or r=-1. N(6) = 36 and N(2+2*sqrt(-5))=24. So a gcd would have norm dividing gcd(36,24)=12. Since N(2)=4 and N(1+sqrt(-5))=6, any common multiple of 2 and 1+sqrt(-5) has norm a multiple of 12. So if a gcd exists for a and b, then its norm must be exactly equal to 12. However, there is no integer solution to x^2+5y^2 = 12; clearly we need |y|<=1; if y=0 then we would need x^2=12, impossible, and if |y|=1 we would need x^2=7, also impossible. So a and b have no gcd in Z[sqrt(-5)]. (A bit more complicated: since x+y*sqrt(-5) is a multiple of 2, you can write (2n) + (2m)*sqrt(-5); the norm would then be 4n^2 + 20m^2, so m=0, n^2 = 3, impossible) It's not denial. I'm just very selective about what I accept as reality. --- Calvin (Calvin and Hobbes) Arturo Magidin magidin@math.berkeley.edu === Subject: a question on probability distributions and generating functions Epigone-thread: frumgomwerl Dan asks (after corrections): Let X and Y be two discrete nonnegative random variables. We say that X>Y, if Pr(X > t) >= Pr(Y > t), for all t>=0 (*) Let z>0 be an arbitrary constant. Clearly, we get also : Pr(z^X > z^t) >= Pr(z^Y > z^t) for all t if z>1, Pr(z^X > z^t) <= Pr(z^Y > z^t) for all t if z<1. So E(z^X)>=E(z^Y) if z>1 and E(z^X)<=E(z^Y) if 0Y (look at t=1.5). Don Coppersmith === Subject: Minimising near diagonal terms in a matrix Message-id: <3F576391.2090403@cui.unige.ch> Here is a pb I'd like to submit, which I guess is close to the Metric TSP and wonder whether some of you may know a solution (exact or approx). Given an interdistance matrix (Aij=d(Xi,Xj) for some Xi's), what is the best permutation so that given r>0 the sum, for every line of the matrix, of the r terms around the diagonal is minimum? I have experimented with the greedy algo and a DP procedure for r=1 (which gives good result) but would like to extend to the case r>1. I that a well-known problem? I gess so but cannot find any good reference... Stephane -- Dr. Stephane Marchand-Maillet (MER) Head of the Viper group marchand@cui.unige.ch http://viper.unige.ch/ Computer Vision and Multimedia Lab, CUI, University of Geneva 24 Rue du General-Dufour - 1211 Geneva 4 - Switzerland Tel: +41 (0)22 705 7631 / +41 (0)22 705 7660 Fax: +41 (0)22 705 7780 http://www.mrml.net/ http://www.benchathlon.net/ === Subject: Re: Q: Norm of difference of fractional powers of operators I found a reference for this inequality: Rajendra Bhatia Perturbation Inequalities for the Absolute Value Map in Norm Ideals of Operators J. Operator Theory 19 (1988), 129-136 where the inequality is actually proven. Markus === Subject: Re: Think Small game > In the three-player case, there is a Nash equilibrium with player 1 > always choosing 1, player 2 choosing 2 and player 3 choosing 3. For that matter, it's also an equilibrium if Player 1 always chooses 1, Player 2 always chooses 2, and Player 3 always chooses 17. > This shows one of the pitfalls of the notion of Nash equilibrium in > multi-player games. Well, you can also ask whether the equilibrium is stable, which this one isn't. The stable equilibria for this game are more interesting, I think. David desJardins