October 2008 - mathfun@mailman.xmission.com

Re: [math-fun] what's the best way of finding n unknown integers from their sums taken k at a time
by Dan Asimov 17 Oct '08

17 Oct '08

Er, 17 is prime, too: > * The ring of integers of the cyclotomic field > Z(exp(2pi i/p) has non-unique factorization for > all primes p except 2,3,5,7,11,13,17,19. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] what's the best way of finding n unknown integers from their sums taken k at a time
by Dan Asimov 17 Oct '08

17 Oct '08

Richard Guy wrote [as slightly reformatted]: << The corresponding problem where sums of {\em triples} of elements of a set are given has been settled by Boman & Linusson. The exceptions are precisely 3, 6, 27, 486. For n=27 they give five examples of which the simplest is {-4,-1^{10},2^{16}} and its negative, where exponents denote repetitions. For n=486 they give {-7,-4^{56},-1^{231},2^{176},5^{22}} and its negative. >> This is so cool! I love results like this, where a simply stated problem has a straightforward answer, except for some small and/or strange set. (It is surely no coincidence that these are 3, 2*3, 3^3, 2*3^5.) I am interested to hear of mathematical results that have a small and strange set of exceptions. A few I can think of are these: * Any differentiable structure on n-space is equivalent to any other for all n except 4. * The alternating group A_n is simple for all n except 4 (Hmmm, is there a connection here?) * The automorphism group Aut(S^n) is isomorphic to S_n for all n except 2, 6. * The ring of integers of the imaginary quadratic field Z(sqrt(-n)) has non-unique factorization except for n = 1, 2, 3, 7, 11, 19, 43, 67, 163. * The ring of integers of the cyclotomic field Z(exp(2pi i/p) has non-unique factorization for all primes p except 2,3,5,7,11,13,19. * There exists no real division algebra R^k for k = 2^n for all n except 0, 1, 2, 3. Other such examples are solicited. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

5 4

[math-fun] Old cute math problem
by Dan Asimov 16 Oct '08

16 Oct '08

Somehow I was recently reminded of this old and very cute math problem, which some of you may enjoy tackling: ----------------------------------------- Let x_n be a dense sequence in [0,1]. x_1 divides [0,1] into a left piece of length a_1 and a right piece b_1. Inductively, x_(n+1) divides one of the subintervals that {x_1,...,x_n} divide [0,1] into a left piece of length a_n and a right piece of length b_n. Prove that Sum_1^oo (a_n * b_n * (a_n + b_n)) = 1/3. ----------------------------------------- --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Graphics chips used to crack wireless keys 100x faster
by Henry Baker 16 Oct '08

16 Oct '08

>From comp.risks -- Apparently, the "CUDA" parallel language is good for something mathematical, after all. I understand that (at least) one of these ;nVidia chips is found in every Macbook Pro laptop, so perhaps this cracking can be done sitting in a Starbucks or an airport. --- Date: Sun, 12 Oct 2008 18:21:47 -0400 From: Monty Solomon <monty(a)roscom.com> Subject: Russian researchers achieve 100-fold increase in WPA2 cracking speed Russian security company Elcomsoft posted a press release on 12 Oct 2008 detailing a new method to crack WPA and WPA2 keys: With the latest version of Elcomsoft Distributed Password Recovery, it is now possible to crack WPA and WPA2 protection on Wi-Fi networks up to 100 times quicker with the use of massively parallel computational power of the newest NVIDIA chips. Elcomsoft Distributed Password Recovery only needs a few packets intercepted in order to perform the attack. ... http://securityandthe.net/2008/10/12/russian-researchers-achieve-100-fold-i… http://www.prweb.com/releases/wi-fi/cracking/prweb1405954.htm http://securityandthe.net/wp-content/uploads/2008/10/elcom_pressrelease_wpa…

1 0

Re: [math-fun] what's the best way of finding n unknown integers from their sums taken k at a time
by Michael Reid 15 Oct '08

15 Oct '08

> I have the book in front of me. It is called Mathematical Mind Benders and > is by Peter Winkler. On page 22 there's a problem called "Getting the > numbers back" that states: > > For which positive integers n is it the case that, given the C(n, 2) > pairwise sums of n distinct positive integers, you can recover the integers > uniquely? > > I must say that this is a really good "puzzle" book. The puzzles are > refreshingly original and the difficulty level is significantly higher than > most books of this type. There are many problems that I would place at the > USAMO/IMO level of difficulty. Consider this an unqualified recommendation! thanks! it seems like an interesting book. i see that they state the problem carefully (although not allowing repeats in the original collection), while avoiding the term "multi-set". yesterday i asked: ) is the usual-set case of any (further) interest? probably not. for example, if A = {0, 1, 2, 4, 5, 6, 7} , then its 2-at-a-time sumset is {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} , and the same for the reflected set A' = {0, 1, 2, 3, 5, 6, 7} . the same technique shows that for all n >= 7 , there are distinct usual-sets that have the same 2-at-a-time sum-(usual)-sets. moreover, it is possible to have distinct usual-sets of different cardinalities, with the same 2-at-a-time sum-(usual)-sets. so it seems natural to consider only the multi-set version of the question. mike

1 0

Re: [math-fun] 'Manifest' transcendental number?
by Eugene Salamin 15 Oct '08

15 Oct '08

----- Original Message ---- From: Guy Haworth <g.haworth(a)reading.ac.uk> To: math-fun(a)mailman.xmission.com Sent: Wednesday, October 15, 2008 6:38:55 AM Subject: [math-fun] 'Manifest' transcendental number? Apologies if this is trivial, but what is the easiest transcendental number to demonstrate _is_ a transcendental number? G ______________________________________________ A real number r is said to be approximable to order n if there exists a positive constant c, depending on r, such that are infinitely many rational numbers (h/k) satisfying | r - h/k | < c / k^n . A theorem of Liouville states that an algebraic number of degree n is not approximable to order n+1 or higher. A Liouville number L is a number that possesses rational approximations of arbitrarily high order. For every positive integer n, there exists a rational h[n] / k[n] such that | L - h[n] / k[n] | < 1 / k[n]^n . Liouville numbers are therefore transcendental. These were the first transcendental numbers to be explicitly constructed. Example: sum( 2^(-n!), n=1..infinity). The numbers e and pi can also be easily shown to be transcendental. Proofs of all this can be found in Niven's Carus Monograph, "Irrational Numbers". Niven also states without proof that according to Roth's theorem, an algebraic number is not approximable to order greater than 2. Gene

1 0

Re: [math-fun] what's the best way of finding n unknown integers from their sums taken k at a time
by Michael Reid 15 Oct '08

15 Oct '08

> Interestingly enough, the 2-at-a-time sum problem for n=4 isn't necessarily > unique! For example, {1, 2, 3, 6} and {0, 3, 4, 5} produce the same sum > set, {3, 4, 5, 7, 8, 9}, when the sums are taken 2 at a time. and there's an easy bootstrapping to produce such an example for n = 2^k+1 , starting from an example for n = 2^k . this is basically part (a) of the proposed theorem. it appears that the bootstrapping can be arranged to get the starting multisets to be actual sets (no repeats). i do not see if it is possible to also get the same for the 2-at-a-time sums multiset by the bootstrapping method i have in mind. perhaps another method can accomplish that. part (c*) of the problem, which is starred, meaning its solution is unknown, asks if there are 3 distinct multisets that have the same 2-at-a-time sums multiset. > I have a book (at home, alas) that talks about this problem. Basically, for > n a power of 2, the numbers are not necessarily determined by the sums taken > two at a time. If n is not a power of 2, then the numbers are uniquely > determined. I can dig up the reference later, if anyone is interested. count me interested! mike

3 2

[math-fun] 'Manifest' transcendental number?
by Guy Haworth 15 Oct '08

15 Oct '08

Apologies if this is trivial, but what is the easiest transcendental number to demonstrate _is_ a transcendental number? G

2 1

Re: [math-fun] Infinite dimensional division algebras
by Dan Asimov 15 Oct '08

15 Oct '08

<< There are lots of infinite dimensional fields over the real or complex numbers, but what about infinite dimensional noncommutative or nonassociative division algebras? What is known about such creatures? >> Years ago when Conway was active here, he stated that there are no infinite-dimensional real division algebras, unless I'm remembering wrong. That would seem to rule out complex ones as well, would you agree? --Dan ________________________________ Well there are lots of infinite dimensional fields, e.g. function fields, F extended by one or more transcendentals. Are you you saying that there is a Wedderburn type theorem here, that all infinite dimensional (real or complex) division algebras are fields? Is there such an animal as a free division algebra? >> Division algebras as I use the term can be commutative or non. By an infinite-dimensional real division algebra I mean a multiplication on the structure of an infinite-dimensional real vector space like R^(oo) (all sequences of reals with only finitely many nonzero terms), with the usual added axioms. (Actually I don't recall if Conway said anything about dimensions > aleph_0.) Hmm, let's see. Is there a way to show that the field of rational functions in X over the reals with its addition and scalar multiplication is a real vector space isomorphic to R^(oo) ? It certainly seems so (even if it requires AC to get a basis). Then field multiplication sure seems to give a division algebra structure. Am I missing something? (It may be significant that neither plain googling, nor Google Scholar, nor MathSciNet gives any hits at all for the phrase "infinite-dimensional real division algebra", with or without the hyphen. But even if they don't exist, I'd expect some math paper to say so.) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Infinite dimensional division algebras
by Eugene Salamin 14 Oct '08

14 Oct '08

----- Original Message ---- From: Dan Asimov <dasimov(a)earthlink.net> To: Eugene Salamin <gene_salamin(a)yahoo.com> Sent: Tuesday, October 14, 2008 3:42:36 PM Subject: To Gene Re: [math-fun] what's the best way of finding n unknown integers from their sums taken k at a time Gene, Thanks for the correction (but I beat ya to it). << There are lots of infinite dimensional fields over the real or complex numbers, but what about infinite dimensional noncommutative or nonassociative division algebras? What is known about such creatures? >> Years ago when Conway was active here, he stated that there are no infinite-dimensional real division algebras, unless I'm remembering wrong. That would seem to rule out complex ones as well, would you agree? --Dan ________________________________ Well there are lots of infinite dimensional fields, e.g. function fields, F extended by one or more transcendentals. Are you you saying that there is a Wedderburn type theorem here, that all infinite dimensional (real or complex) division algebras are fields? Is there such an animal as a free division algebra? Gene

1 0