January 2005 - mathfun@mailman.xmission.com

[math-fun] (Fwd) [NOBNET 4625] Mathematical Games
by Bernie Cosell 09 May '05

09 May '05

I know that in addition to your likely being interested in this, I know that several of you have contributed to Mathematical Games over the years and so might want to get in touch with Ed... /Bernie\ ------- Forwarded message follows ------- Date: Mon, 8 Nov 2004 06:30:37 -0800 (PST) From: ed pegg <ed(a)mathpuzzle.com> Subject: [NOBNET 4625] Mathematical Games To: nobnet(a)iijnet.or.jp Martin Gardner just recently celebrated his 90th birthday. Also, maa.org is *finally* releasing the entire collection of Mathematical Games on CD rom next month. There were frightening amounts of copyright issues to work out, but they have been resolved. Catalog Code: TDG/FW04 ISBN 0-88385-545-3 List Price: $54.95 This is all 15 Mathematical Games books on a CD-Rom. I'd like to do a "behind the scenes" look at Mathematical Games for an article. Martin did lots, but he avidly used a lot of help from hundreds of people. I'd like to write an article about the background help. If you ever assisted in one of Martin's columns, I'd like to hear from you -- a note about what you did. I'll use these notes in my article. Ed Pegg Jr http://www.maa.org columnist http://www.mathpuzzle.com ------- End of forwarded message ------- -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--

3 2

[math-fun] A missing sequence from group theory?
by N. J. A. Sloane 04 Feb '05

04 Feb '05

To MathFun and SeqFans: A possibly new sequence? Could someone calculate it? Let t(G) = no. of unitary factors of the abelian group G, and let T(n) = Sum t(G) taken over all abelian groups of order <= n. There are several papers giving estimates for T(n), e.g. T(x) = c_1 x (log x + 2 gamma - 1) + c_2 x + ... My question is, how does the sequence T(n) begin? References and definitions follow, from MSN. NJAS MR1850168 Zhai, Wen Guang On the average number of unitary factors of finite abelian groups. II [MR1813450 (2001j:11092)]. (Chinese) Acta Math. Sinica 44 (2001), no. 4, 667--672. 11N45 MR1813450 (2001j:11092) Zhai, Wenguang On the average number of unitary factors of finite abelian groups. II. Acta Math. Sin. (Engl. Ser.) 16 (2000), no. 4, 549--554. (Reviewer: R. C. Baker) 11N45 (11L07 20K01) MR1641042 (99e:11124) Zhai, Wenguang; Cao, Xiaodong On the average number of unitary factors of finite abelian groups. Acta Arith. 85 (1998), no. 4, 293--300. (Reviewer: R. C. Baker) 11N45 MR1613290 (99f:11124) Wu, J. On the average number of unitary factors of finite abelian groups. Acta Arith. 84 (1998), no. 1, 17--29. (Reviewer: R. C. Baker) 11N45 (11L07 20K01) 1225427 (94k:11108) Schmidt, Peter Georg(D-MRBG) Zur Anzahl unitrer Faktoren abelscher Gruppen. (German) [On the number of unitary factors in abelian groups] Acta Arith. 64 (1993), no. 3, 237--248. Part of this review follows: Let $\scr A$ denote the set of all abelian groups. Under the operation of direct product, $\scr A$ is a semigroup with identity element $E$, the group with one element. $G_1$ and $G_2$ are relatively prime (German: teilerfremd) if the only common direct factor of $G_1$ and $G_2$ is $E$. We say that $G_1$ and $G_2$ are unitary factors of $G$ if $G=G_1\times G_2$ and $G_1,G_2$ are relatively prime. Let $t(G)$ denote the number of unitary factors of $G$, and let $T(x)=\sum_{G\in {\scr A}, |G|\le x} t(G).$ There are constants $A,B,$ and $C$ such that $\Delta(x)\colon =H(x)-Ax\log x - Bx -C\sqrt x=o(\sqrt x).$ In this paper, the author shows that $\Delta(x)\ll x^{3/8} \log^{7/2}x.$ The previous best estimate for $\Delta(x)$ had been $\Delta(x)\ll x^{31/82} \log^2 x$; this was given by H. Menzer \ref["Exponentialsummen und verallgemeinerte Teilerprobleme", Habilitationsschrift, Friedrich-Schiller-Univ., Jena, 1992; per bibl.]. Further references from the Wu (1998) paper: Many accented letters have been dropped! # R. C. Baker and G. Harman, Numbers with a large prime factor, Acta Arith. 73 (1995), 119--145. MR1358192 (97a:11138) # E. Cohen, On the average number of direct factors of a finite abelian group, ibid. 6 (1960), 159--173. MR0118764 (22 #9535) # E. Fouvry and H. Iwaniec, Exponential sums with monomials, J. Number Theory 33 (1989), 311--333. MR1027058 (91b:11097) # S. W. Graham and G. Kolesnik, Van der Corput's Method of Exponential Sums, Cambridge Univ. Press, Cambridge, 1991. MR1145488 (92k:11082) # C. H. Jia, The distribution of square-free numbers, Sci. China Ser. A 36 (1993), 154--169. MR1223084 (94f:11095) # G. Kolesnik, On the number of abelian groups of a given order, J. Reine Angew. Math. 329 (1981), 164--175. MR0636451 (83b:10055) # E. Krtzel, On the average number of direct factors of a finite abelian group, Acta Arith. 51 (1988), 369--379. MR0971087 (89m:11091) # H.-Q. Liu, The greatest prime factor of the integers in an interval, ibid. 65 (1993), 302--328. MR1259341 (95d:11117) # H.-Q. Liu, On some divisor problems, ibid. 68 (1994), 193--200. MR1305200 (96a:11089) # H.-Q. Liu, Divisor problems of 4 and 3 dimensions, ibid. 73 (1995), 249--269. MR1364462 (96k:11118) # P. G. Schmidt, Zur Anzahl unit\"arer Faktoren abelscher Gruppen, ibid. 64 (1993), 237--248. MR1225427 (94k:11108) # P. Sargos and J. Wu, Multiple exponential sums with monomials and their applications in number theory, Prpublications 97/ n37 de l'Institut lie Cartan, Universit Henri Poincar (Nancy 1). # J. Wu, On the distribution of square-full and cube-full integers, Monatsh. Math., to appear. cf. MR1657818 (2000a:11125)

8 12

RE: [math-fun] Re: covering all N with squares (2nd degree polynomialswith integer coeffs.).
by Daniel Asimov 28 Jan '05

28 Jan '05

1. Are there any restrictions on the cocefficients, or can they be arbitrary complex numbers? 2. As long as each natural number occurs somewhere in the array, does it matter what else is in the array? --Dan ------------------------------------------------------ Simon says: << ... let my try to restate the problem let's make a square array of numbers from wich each row is a 2nd degree pol. : apart from the first column, does the array covers ALL natural numbers with possibly some overlap? >>

2 1

[math-fun] Re: Marriage theorem generalization
by Andy Latto 27 Jan '05

27 Jan '05

> -----Original Message----- > From: math-fun-bounces+andy.latto=pobox.com(a)mailman.xmission.com > [mailto:math-fun-bounces+andy.latto=pobox.com@mailman.xmission.com]On > Behalf Of Thomas Colthurst > Sent: Thursday, January 27, 2005 1:24 PM > To: michael.kleber(a)gmail.com; math-fun(a)mailman.xmission.com > Cc: thomasc(a)bbn.com > Subject: [math-fun] Re: Marriage theorem generalization > > > > Well, here's a reduction to what is hopefully a well-studied > graph theory problem. > > Add two special sets: S, which contains only the interval [0,0], > and E, which contains only [n+1,n+1]. Now make a graph G with > a vertex for every interval and an edge between two intervals > iff (1) the union of the two intervals is itself an interval > and (2) the two intervals come from different sets. Thus, if > there were k sets of intervals in the beginning, G is (k+2)-partite > graph. The problem now becomes: find a path in G from > [0,0] in S to [n+1,n+1] in E that visits each part of G > at most once. > > As I said, I hope this is a well-studied problem, because all > I know are bad solutions to it. Well, it's a more difficult problem than finding Hamiltonian circuits in a graph, so it's NP-complete. Given a graph G with N vertices, you can construct a new graph G', with vertices in G X {1, 2,...,n} If G has an edge from x to y, then G' has an edge from {x, i} to {y, i+1} for all i. G' is n-partite, with projection to G giving the parts. Now G has a hamiltonian path starting at x and ending at y just if G' (an n-partite graph) has a path from {x, 1} to {y, n} that visits each part of G' at most once. So you've reduced what might be a hard problem, but might be an easy one, to a problem that's definitely hard. Andy Latto andy.latto(a)pobox.com

1 0

[math-fun] Re: Marriage theorem generalization
by Thomas Colthurst 27 Jan '05

27 Jan '05

Well, here's a reduction to what is hopefully a well-studied graph theory problem. Add two special sets: S, which contains only the interval [0,0], and E, which contains only [n+1,n+1]. Now make a graph G with a vertex for every interval and an edge between two intervals iff (1) the union of the two intervals is itself an interval and (2) the two intervals come from different sets. Thus, if there were k sets of intervals in the beginning, G is (k+2)-partite graph. The problem now becomes: find a path in G from [0,0] in S to [n+1,n+1] in E that visits each part of G at most once. As I said, I hope this is a well-studied problem, because all I know are bad solutions to it. (For example: starting at [0,0] and continually growing a list of valid paths to each vertex until you grow a valid path to [n+1,n+1].) Speaking of bad solutions, here's an algorithm for your general problem that isn't at all guaranteed to find a solution, but might often do so in practice. Let c(i) be the number of sets that don't contain i in one of the set's subsets. Pick the subset that maximizes sum_{j in subset} c(j)^N for some N >> k, and then recalculate all the c(i) with the picked set removed and c(i)=0 if i was in the picked subset. Repeat. (The exponent is there simply to turn sum into a "soft max" function, and can be replaced with an equivalent ordering on vectorized counts if you like.) -Thomas C

1 0

RE: [math-fun] covering all N with squares (2nd degree polynomialswithinteger coeffs.).
by Daniel Asimov 27 Jan '05

27 Jan '05

What I wrote is nonsense, but what does make sense is the following: Let Q_k(x) = x^2 + kx for all k in Z. Then: S+ = {Q_k(p) : p prime, k = 1,2,3,... } contains for each prime p all multiples of p greater than p^2, S- = {Q(-k)(p) : p prime, k = 1,2,3,...} contains for each prime p all multiples of p less than p^2, and S0 = {Q_0(n) : n = 1,2,3,...} contains all squares. So S- u S0 u S+ = Z. So I'm guessing that Simon wants a family of polynomials { P_k(x) : k = 1,2,3,... } with all coefficients positive integers with { P_k(n) : k = 1,2,3,... and n = 1,2,3,...} = Z+ exactly. -------------------------------------------------------------------------------- Of course, as long as we can use countably many polynomials, for each k we can always design P_k(x) so that P_k(1) = [the least positive integer not contained in the union of {P_j(n) : n = 1,2,3,...} for 1 <= j < k.] But I suppose this would be considered too trivial. --Dan ------------------------------------------------------------------ I wrote: << Let Sq denote {1,4,9,16,...}. But if say for each k in Z, we let P_k(x) = x^2 + kx , then . . . . . . . . . >>

2 1

[math-fun] Marriage theorem generalization
by Michael Kleber 27 Jan '05

27 Jan '05

Suppose you have a collection of sets of integers from the range [1,n]. Then the question "Can you cover all of [1,n] by choosing one integer from each set?" is answered by Hall's Marriage Theorem -- yes, provided any size k subset of [1,n] intersects at least k of the sets in my collection. Moreover it is computationally efficient to make an actual choice of which integer to use from each set, or to list all the possible choice functions: the proof of Hall's is essentially an argument that if you pick one a a time without doing anything stupid, you never need to backtrack. What if instead you start with a collection of sets of *intervals of integers* in [1,n]? I want to know whether it's possible to pick one interval from each set in such a way that their union is all of [1,n]. And if so, I'd like to know the same constructiveness facts: can I find one or all such assignments efficiently? The full generalization, of course, is where you start with a collection of sets of *subsets* of [1,n]. But without thinking about it much at all, it seems overwhelmingly likely to me that this will turn out to be NP-complete. So the question is, does restricting to intervals tame the situation enough to make it feasible? --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

1 0

RE: [math-fun] covering all N with squares (2nd degree polynomials withinteger coeffs.).
by Daniel Asimov 27 Jan '05

27 Jan '05

Simon asks: << Here is the problem. How to cover all N (natural numbers) with simple poynomials of the second degree even with some overlaps. We all know that it is possible to do it with a beatty sequence when 1/a + 1/b = 1, with a,b irrationals. [a*n] and [b*n] covers N with no overlab and no holes. if a = 1/2 + sqrt(5)/2 and b = 0.38196601125 then it works. Of course it is possible to do it with 2 or more ordinary arithmetical progressions. But how to do it with 2nd degree polynomials? Is it possible? For example (a tentative sieve that does not work), n^2 = 1, 4, 9, 16, 25, ... n^2+1 = 2, 5, 10, 17, 26, ... n^2+2 = 3, 6, 11, 18, 27, ... etc does cover many integers but I do not think it does work. It does not matter if there are some overlaps. of course, in the above example, n^2+k at n=1 will eventually reach any number but let's say : can it be done non-trivially? I am just wondering if the problem has a solution. >> I'm not sure I understand just what the question is. Since for any polynomial P(x) over Z of degree > 1 we have density( { P(n) : n = 1,2,3,... } ) = 0, this clearly can't be done with finitely many polynomials. ---------------------------------------------------------------------- Let Sq denote {1,4,9,16,...}. But if say for each k in Z, we let P_k(x) = x^2 + kx , then { P_k(n) : n,k = 1,2,3,... } = Sq + { kn : k,n = 1,2,3,... } then since every positive integer is a square plus a number of the form kn, this is certainly Z (with abundant overlap). So, I'm not sure if I'm understanding the question. --Dan

1 0

[math-fun] covering all N with squares (2nd degree polynomials with integer coeffs.).
by Simon Plouffe 27 Jan '05

27 Jan '05

Hello, the title is a little short and not fully descriptible, Here is the problem. How to cover all N (natural numbers) with simple poynomials of the second degree even with some overlaps. We all know that it is possible to do it with a beatty sequence when 1/a + 1/b = 1, with a,b irrationals. [a*n] and [b*n] covers N with no overlab and no holes. if a = 1/2 + sqrt(5)/2 and b = 0.38196601125 then it works. Of course it is possible to do it with 2 or more ordinary arithmetical progressions. But how to do it with 2nd degree polynomials? Is it possible? For example (a tentative sieve that does not work), n^2 = 1, 4, 9, 16, 25, ... n^2+1 = 2, 5, 10, 17, 26, ... n^2+2 = 3, 6, 11, 18, 27, ... etc does cover many integers but I do not think it does work. It does not matter if there are some overlaps. of course, in the above example, n^2+k at n=1 will eventually reach any number but let's say : can it be done non-trivially? I am just wondering if the problem has a solution. simon plouffe

3 3

[math-fun] Re: Rotor-router article
by James Propp 25 Jan '05

25 Jan '05

If folks are interested in finding out more about the topics discussed in Michael's very nice article, check out http://www.math.wisc.edu/~propp/quasirandom.html and the links contained therein. Jim Propp

1 0