August 2004 - mathfun@mailman.xmission.com

[math-fun] A too-short sequence based on Property B
by N. J. A. Sloane 17 Aug '04

17 Aug '04

Sequence needing more terms, related to "Property B" ===================================================== The following is a sequence that at the present time is too short to include in the OEIS: m(1) = 1, m(2) = 3, m(3) = 7, m(4) = 21, 22 or 23? m(n) is the smallest number of sets of size n that do not have Property B. It would nice if the resources of the math-fun list, the seq-fan list and the Web could be harnessed to determine m(4)! -------------------------------------------------------- Here are more details (though I'm not an expert on the problem, so some of what follows may be incorrect or out-of-date). Definition: We work inside a finite set X of unspecified size. A collection C of subsets of X, all of size n, has Property B if we can partition X into two disjoint subsets X = Y union Z such that every set in C meets both Y and Z. Illustrations for n = 1, 2, 3: n=1: take X = {1}. Then the collection C = { {1} } does not have Property B. n=2, X={1,2,3}, C = { {1,2}, {1,3}, {2,3} } does not have Property B. C={ {1,2}, {1,3} } does, because we can take Y = {1}, Z={2,3}. n=3: take X={1..7}, C={ the 7 Steiner triples } = cyclic shifts of {1, 2, 4} does not have Property B. If any subset is omitted from C then that subset can be taken as Y and the 6 subsets do have Prop. B. References: The problem of finding m(4) was mentioned by E C Milner in his address at the 1974 Internat. Congress of Mathematicians in Vancouver. Donovan Hare tells me that the upper bound of 23 was found by Seymour (A Note on a Combinatorial Problem of Erdos and Hajnal. Bull. London Math. Soc. 2:8 (174), 681-682) and independently Toft (On Colour-critical Hypergraphs, in Infinite and Finite Sets, ed. A. Hajnal et al, North Holland Publishing Co., 1975, 1445-1457). According to Harvey Abbott (I am indebted to Donovan Hare for passing on this information), the lower bound of 21 is due to G.M. Manning: "Some results on the m(4) problem of Erdos and Hajnal", Electron. Research Announcements of the American Mathematical Society, 1(1995) 112-113. --------------------------------------------------------------- Other references for background: >From MathSciNet: MR1849460 (2002f:05156) Abbott, H. L.; Hare, D. R. Families of 4-sets without property B. Ars Combin. 60 (2001), 239--245. 05D05 MR1088279 (91j:05075) Exoo, Geoffrey On constructing hypergraphs without Property B. Ars Combin. 30 (1990), 3--12. 05C65 MR1045053 (91i:54020) Jiang, Ji Guang Paracompactness and the property $b\sb 1$. (Chinese) Acta Math. Sinica 32 (1989), no. 4, 551--555. 54D20 MR0982108 (90c:05001) Abbott, H. L.; Liu, A. On property $B(4)$ of families of sets. Ars Combin. 26 (1988), 59--68. (Reviewer: E. C. Milner) 05A05 MR0944353 (89e:51009) Boros, Endre ${\rm PG}(2,p\sp s),\;p>2,$ has property $B(p+2)$. Ars Combin. 25 (1988), 111--113. (Reviewer: Anne Delandtsheer) 51E20 (05B25) MR0918392 (89a:05006) Abbott, H. L.; Liu, A. On a problem of Erdös concerning property $B$. Combinatorica 7 (1987), no. 3, 215--219. (Reviewer: G. F. Clements) 05A05 MR0429593 (55 #2604) de Vries, Hans Ludwig On property B and on Steiner systems. Math. Z. 153 (1977), no. 2, 155--159. (Reviewer: N. S. Mendelsohn) 05B05 (05A05) MR0392583 (52 #13400) Johnson, David S. On property $B\sb{r}$. J. Combinatorial Theory Ser. B 20 (1976), no. 1, 64--66. 05A05 MR0340086 (49 #4842) Woodall, D. R. Property $B$ and the four-colour problem. Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pp. 322--340. Inst. Math. Appl., Southend-on-Sea, 1972. (Reviewer: F. Bernhart) 05C15 Google gave many hits, one of which is a related paper by Peter Erdos: www.renyi.hu/~elp/prop-b.pdf Neil Sloane (njas(a)research.att.com) Aug 17 2004

1 0

[math-fun] Mersenne footnote
by Joerg Arndt 17 Aug '04

17 Aug '04

Let M:=2^e-1, if M prime then phi(M)=2*(2^{e-1}-1) Now, observationally (tested all exponents e up to 5000 and some regions with e>5000): if ( 3^{2^{e-1}}==-3 mod M ) <==> M is prime Notation: [TS] <==> [P] The direction [P] ==> [TS] is easy excluding even exponents: 3 does not divide M and is a nonresidue. I cannot prove [TS] ==> [P]. I tried hard and failed with all ideas. Even additional assumptions (like that none of the 2^k powers of 3 in the test before the -3 equals minus -3) didn't lead to a proof. Before I waste time trying to prove something that is just false: Can ( [TS] ==> [P] ) be true? I'd be surprised to see a false hit or miss with the implied test but someone one this list may know better. I consider the test (if valid) a nice footnote because it consists of just squaring, no additions/subtractions. Further, a proof might give insight to primality tests for less restricted candidates. clueless, jj -- p=2^q-1 prime <== q>2, cosh(2^(q-2)*log(2+sqrt(3)))%p=0 Life is hard and then you die.

1 0

[math-fun] deformed derivative
by Mike Stay 15 Aug '04

15 Aug '04

Has anyone seen this deformation before: d_s f(x) = f(x^s) - f(x) ? It's not generally linear, but if s=p^k for some prime p, integer k, then it's linear mod p. -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

1 0

RE: [math-fun] OEIS 100K Party
by Daniel Asimov 12 Aug '04

12 Aug '04

<< I know a lot of people who are on the math-fun list use the OEIS sporadically - everyone is invited to the e-party! Neil Subject: OEIS 100K Party To everyone who uses the OEIS! Sometime this year the sequence count will reach 100000. It's too bad we are spread out over the world, or we could have a party. But I have a suggestion: An e-party! Everyone send in a digital photo of themselves holding a drink and making a toast to the OEIS. These picture will be collected into a special web page posted on the OEIS web site. >> Even better, why don't those local collections of folks who appreciate the OEIS get together in the old analogue way, and photos of these could be put online later, or even during. Also, a real-time computer link might enable the local parties to communicate globally. --Dan ----------------------------------------------------------------------

1 0

[math-fun] OEIS 100K Party
by N. J. A. Sloane 12 Aug '04

12 Aug '04

I know a lot of people who are on the math-fun list use the OEIS sporadically - everyone is invited to the e-party! Neil Subject: OEIS 100K Party To everyone who uses the OEIS! Sometime this year the sequence count will reach 100000. It's too bad we are spread out over the world, or we could have a party. But I have a suggestion: An e-party! Everyone send in a digital photo of themselves holding a drink and making a toast to the OEIS. These picture will be collected into a special web page posted on the OEIS web site. The page now exists: see http://www.research.att.com/~njas/sequences/100k.html Under each picture it would give your name, city, date and perhaps a brief message. Also, if you like, your home page. Example: --------------------------------------------- | | Photo of XXX holding a glass of beer | | --------------------------------------------- Heinz Meyer, Berlin, Aug 20 2004 (Home Page: http://www.aaa.bbb.ccc/~meyer/ ) "Best Wishes to the OEIS upon reaching 100K sequences!" If you think this is a good idea, start sending me photos and I will post them as they arrive. Since I will probably have to shrink them, tell me the original size of the photo: 6 inches by 9 inches, or 20 cm by 30 cm, etc.) -------------------------------- Another thing: sequence A100000 should be special. Please look at all the new sequences in the next few months - if you see one that is worthy of being A100000, send me a message. I will pick the winner and change its number to A100000. Regards Neil Sloane (njas(a)research.att.com)

1 0

[math-fun] Are Mersenne primes random?
by Eugene Salamin 11 Aug '04

11 Aug '04

Are Mersenne primes randomly distributed? If so, then Prob(Mn is a Mersenne prime) = Prob(n is prime) * Prob(Mn is prime|n is prime). The first factor is 1/log(n), and the second factor is 2/log(2^n-1) = (2/log 2)*(1/n), where the extra factor of 2 comes from knowing that Mn is odd. Thus Prob(Mn is prime) = (2/log 2)*(1/(n log(n)), and the expected number of Mersenne primes Mp for n1 < p < n2 is (2/log 2)*int(1/(x log(x)), x=n1..n2) = (2/log 2)*(loglog(n2)-loglog(n1)). Since each Mp has a small probability of being prime, the variance equals the mean. So the expected standard deviation of the number of Mersenne primes equals the square root of the expected number of Mersenne primes. The known Mersenne primes are listed at http://www.utm.edu/research/primes/mersenne/index.html . Take n1 = 100 to avoid small number glitches, and n2 = 10^6 since 10^7 would take us into an incompletely explored gap region. Then the expected number of Mersenne primes is 3.17, while the actual number is 23. On the other hand, if we ignore the factor log(x) in the denominator of the integrand, then loglog is replaced by log, and then the expected number of Mersenne primes is 26.6 +/- 5.2. So it appears that the Mersenne numbers Mp = 2^p - 1 possess an enhanced likelihood of being prime by a factor of log(p) over randomly chosen odd numbers of similar size. Gene __________________________________ Do you Yahoo!? New and Improved Yahoo! Mail - Send 10MB messages! http://promotions.yahoo.com/new_mail

2 1

[math-fun] Infinitely many primes, maybe
by David Gale 11 Aug '04

11 Aug '04

In the excellent article on Mersenne primes http://www.utm.edu/research/primes/mersenne/ I found the following, to me, cryptic passage "Are there infinitely many Mersenne primes? The answer is probably[ital] yes (because the harmonic series diverges). Could someone please explain the "because"? Does the same argument work for Fermat primes? for primes of the form 10^n + 3? for (a^ n)+b, gcd[a,b]=1?

3 4

RE: [math-fun] Re: More innumeracy in high places
by The Purple Streak, Hilarie Orman 10 Aug '04

10 Aug '04

>From a future news story: Some very smart researchers today announced an interesting result in mathematics. Reporters at the press conference took a qualifying exam to determine which of them would be admitted to the closed door session. The mathematicians revealed that the result involved at least one prime number. All but one of the few reporters who qualified to hear the result balked at the administration of a second qualifying exam, several suggesting that the mathematicians suffered from an obscure topological condition. This reporter passed both the second and third exams, and learned the exact nature of the result. It would be a disservice to the general public and to the mathematicians to refer to the information in any further detail, however, because the former only would be misled into life-threatening errors and the latter need to cling to a belief that nobody understands them. Hilarie

1 0

RE: [math-fun] Re: More innumeracy in high places
by Andy Latto 09 Aug '04

09 Aug '04

> -----Original Message----- > From: David Gale > Sent: Monday, August 09, 2004 6:05 PM > To: math-fun > Subject: RE: [math-fun] Re: More innumeracy in high places > > > >Theorem: For any N, there is a prime > N. > >Proof: Consider any prime factor of N!+1 > > > This is very nice, but recall, we started out talkng about the > > man/woman on the street and if I know them they may not find it > > completely obvious that, > > Corollary: There are infinitely many primes In my experience, even mathematically unsophisticated people do find this part to be obvious. Even if they don't, the proof by contradiction that starts > Proof: Hmm.?? We don't want to back down at his point and say > "If there > were only a finite number then. . .". seems to me to be a bit of a cheat. After all, why should it follow from the fact that the set S of primes is finite (that is, cannot be put into 1-1 correspondence with a proper subset) that there exists an N that is greater than any element of S? > I think the solution would be for Socrates to show up > just in the nick > of time and say "Look, John/Mary, What does it mean to say > that there are > an INFINITE number of whatevers?" Perhaps using his > celebrated method he > could get them to agree that infinite MEANS more than N for any N. Right. And I don't think this is a cheat. if we want to express the statement that "there are infinitely many n such that P(n)" in the language of the Peano postulates, rather than in the language of set theory, the standard way to do so is "For all N there exists an M such that M > N and P(M)" Andy Latto andy.latto(a)pobox.com >

1 0

RE: [math-fun] Re: More innumeracy in high places
by David Gale 09 Aug '04

09 Aug '04

At 11:38 AM 8/9/2004 -0400, you wrote: > > > > >Third, give the proof. It would make > > >for an interesting experiment to see what finally appears in print. > > > > Probably something like this: > > > > "The proof is based on the method of self-contradiction, > > in which an assertion is assumed to be both true and false > > at the same time." > >I'm sure the press could find some other way to garble the proof, but >this particular garbling could be avoided by using a direct, constructive, >proof, rather than a completely unnecessary proof by contradiction. > >Theorem: For any N, there is a prime > N. >Proof: Consider any prime factor of N!+1 > >What does the traditional insertion of "first suppose there are no >primes > N" add to this proof, other than the possibility of confusion? > > Andy Latto > andy.latto(a)pobox.com > > > This is very nice, but recall, we started out talkng about the > man/woman on the street and if I know them they may not find it > completely obvious that, Corollary: There are infinitely many primes Proof: Hmm.?? We don't want to back down at his point and say "If there were only a finite number then. . .". I think the solution would be for Socrates to show up just in the nick of time and say "Look, John/Mary, What does it mean to say that there are an INFINITE number of whatevers?" Perhaps using his celebrated method he could get them to agree that infinite MEANS more than N for any N. >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0