[math-fun] A missing sequence from group theory?
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)
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?
Alex Healy and I think we've worked this out. Let S(n) = Sum t(G) over all abelian groups of order exactly n. Then T(n) is the sequence of partial sums of S. Let n = p1^e1 p2^e2 ... pk^ek and consider any G of order n. For each prime p^e in the factorization, if a unitary factor of G contains a subgroup of order p, then it must contain the entire subgroup of order p^e present in G. So there are 2^k unitary factors -- just choose for each prime whether or not to multiply in the subgroup of order p^e from G. This is no different from the integer unitary divisors of n, which is A034444. The number of abelian groups of order n is given by A000688 and is just p(e1) p(e2) ... p(ek) where p(x) is the number of integer partitions of x. So S(n) = A034444(n) * A000688(n). In slightly sleazy Mathematica (thanks to Alex): S[n] = Apply[Times, 2*Map[PartitionsP, Map[Last, FactorInteger[n]]]] T[n] = Sum[Apply[Times, 2*Map[PartitionsP, Map[Last, FactorInteger[i]]]], {i, n}] I have submitted these as A101113 and A101114. Russ
An obvious threorem in simple graph theory says that no graph with no more than two nodes of odd order can be drawn in one continuous path. Is there a theorem saying that any graph with two, one, or zero nodes of odd order can always be drawn in one continuous path? A yes/no answer would be nice, and a reference would be even nicer. Thanks for any info. Steve Gray
Neat question!
=Steve Gray An obvious threorem in simple graph theory says that no graph with no An extra negation may have slipped in here: ^^ more than two nodes of odd order can be drawn in one continuous path. Is there a theorem saying that any graph with two, one, or zero nodes of odd order can always be drawn in one continuous path? A yes/no answer would be nice,
No, not without also requiring the graph to be connected.
and a reference would be even nicer.
I'll have to leave that to the professionals.
Thanks for any info.
"Enjoy"!
Marc, Thanks for answering. The graphs I am concerned with are all connected. The path I want is called an Eulerian Cycle, according to Eric's Encyclopedia, which does not quite answer my question. Now if I can find my copy of Harary, the answer might be there. ----- Original Message ----- From: "Marc LeBrun" <mlb@fxpt.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, February 03, 2005 3:21 PM Subject: Re: [math-fun] Question about graphs
Neat question!
=Steve Gray An obvious threorem in simple graph theory says that no graph with (no) An extra negation may have slipped in here: (YOU'RE CORRECT) ^^ more than two nodes of odd order can be drawn in one continuous path. Is there a theorem saying that any graph with two, one, or zero nodes of odd order can always be drawn in one continuous path? A yes/no answer would be nice,
No, not without also requiring the graph to be connected.
and a reference would be even nicer.
I'll have to leave that to the professionals.
Thanks for any info.
"Enjoy"!
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A connected graph has an Euler trail if and only if it has at most two vertices of odd degree. See for example, JA Bondy & USR Murty, Graph Theory with Applications, pg 52. If there's no online proof (it's not hard to prove) write one and put it on a web site! Steve Gray wrote:
Marc, Thanks for answering. The graphs I am concerned with are all connected. The path I want is called an Eulerian Cycle, according to Eric's Encyclopedia, which does not quite answer my question. Now if I can find my copy of Harary, the answer might be there.
----- Original Message ----- From: "Marc LeBrun" <mlb@fxpt.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, February 03, 2005 3:21 PM Subject: Re: [math-fun] Question about graphs
Neat question!
=Steve Gray An obvious threorem in simple graph theory says that no graph with
(no)
An extra negation may have slipped in here: (YOU'RE CORRECT) ^^
more than two nodes of odd order can be drawn in one continuous path. Is there a theorem saying that any graph with two, one, or zero nodes
of odd
order can always be drawn in one continuous path? A yes/no answer would be nice,
No, not without also requiring the graph to be connected.
and a reference would be even nicer.
I'll have to leave that to the professionals.
Thanks for any info.
"Enjoy"!
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck http://www.plambeck.org/ehome.htm
Thane, We met, or at least we heard each other's pitch, at the Experimental Math workshop in Oakland about a year ago. Everyone: Thanks for answering. I will quote from Frank Harary's 1969 book "Graph Theory." He gives a one-page proof which I omit. (It's a good thing math proofs don't become wrong with time.) "As we have seen in Chapter 1, Euler's negative solution of the Koenigsberg Bridge problem constituted the first publicized discovery of graph theory. The perambulatory problem of crossing bridges can be abstracted to a graphical one: Given a graph G, is it possible to find a walk that traverses each line exactly once, goes through all points, and ends at the starting point? A graph for which this is possible is called eulerian. Thus, an eulerian graph has an eulerian trail, a closed trail containing all points and lines. Clearly, an eulerian graph must be connected. Theorem 7.1 (page 64): The following statements are equivalent for a connected graph G: 1. G is eulerian; 2. Every point of G has even degree; 3. The set of lines of G can be partitioned into cycles." (end of quote) This is a positive answer to the question I posed (but from which I left out several crucial elements). Steve Gray ----- Original Message ----- From: "Thane Plambeck" <thane@best.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, February 03, 2005 4:45 PM Subject: Re: [math-fun] Question about graphs
A connected graph has an Euler trail if and only if it has at most two vertices of odd degree.
See for example, JA Bondy & USR Murty, Graph Theory with Applications, pg 52.
If there's no online proof (it's not hard to prove) write one and put it on a web site!
Steve Gray wrote:
Marc, Thanks for answering. The graphs I am concerned with are all connected. The path I want is called an Eulerian Cycle, according to Eric's Encyclopedia, which does not quite answer my question. Now if I can find my copy of Harary, the answer might be there.
----- Original Message ----- From: "Marc LeBrun" <mlb@fxpt.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, February 03, 2005 3:21 PM Subject: Re: [math-fun] Question about graphs
Neat question!
=Steve Gray An obvious threorem in simple graph theory says that no graph with
(no)
An extra negation may have slipped in here: (YOU'RE CORRECT) ^^
more than two nodes of odd order can be drawn in one continuous path. Is there a theorem saying that any graph with two, one, or zero nodes
of odd
order can always be drawn in one continuous path? A yes/no answer would be nice,
No, not without also requiring the graph to be connected.
and a reference would be even nicer.
I'll have to leave that to the professionals.
Thanks for any info.
"Enjoy"!
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck http://www.plambeck.org/ehome.htm
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This is easy enough to prove that this thread should include a proof itself, not just a reference to one. If the graph has zero odd-degree vertices, put your pencil down anywhere and just start drawing, always picking any unused edge. Each time you pass through a vertex, you use up two of its edges, so the number of edges available everywhere always remains even, and you will only "get stuck" upon returning to your starting vertex, where you used up one edge in your initial departure. At this point you might be done, but if not, the path you just created must visit some vertex where not all the edges were used up. (That's what "connected" means.) In this case, enlarge your cycle by "splicing in" another cycle, constructed the same way: start at a vertex on your path with an unused edge, and travel any way you want along unused edges; parity shows that you can only get stuck when you return to the vertex where your splice began. Keep splicing until all the edges are used up. If your graph has two odd-degree vertices, start at one of them and do the same; you're guaranteed to eventually "get stuck" at the other one. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
Very nice. You might have mentioned the situation where the path you just created did not visit some vertices at all, but that does not invalidate the argument. Steve Gray ----- Original Message ----- From: "Michael Kleber" <michael.kleber@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Cc: <thane@best.com> Sent: Thursday, February 03, 2005 7:20 PM Subject: Re: [math-fun] Question about graphs
This is easy enough to prove that this thread should include a proof itself, not just a reference to one.
If the graph has zero odd-degree vertices, put your pencil down anywhere and just start drawing, always picking any unused edge. Each time you pass through a vertex, you use up two of its edges, so the number of edges available everywhere always remains even, and you will only "get stuck" upon returning to your starting vertex, where you used up one edge in your initial departure. At this point you might be done, but if not, the path you just created must visit some vertex where not all the edges were used up. (That's what "connected" means.) In this case, enlarge your cycle by "splicing in" another cycle, constructed the same way: start at a vertex on your path with an unused edge, and travel any way you want along unused edges; parity shows that you can only get stuck when you return to the vertex where your splice began. Keep splicing until all the edges are used up.
If your graph has two odd-degree vertices, start at one of them and do the same; you're guaranteed to eventually "get stuck" at the other one.
--Michael Kleber
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This is one example of a problem where a "greedy" algorithm works. At 07:48 PM 2/3/2005, Steve Gray wrote:
Very nice. You might have mentioned the situation where the path you just created did not visit some vertices at all, but that does not invalidate the argument.
Steve Gray
----- Original Message ----- From: "Michael Kleber" <michael.kleber@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Cc: <thane@best.com> Sent: Thursday, February 03, 2005 7:20 PM Subject: Re: [math-fun] Question about graphs
This is easy enough to prove that this thread should include a proof itself, not just a reference to one.
If the graph has zero odd-degree vertices, put your pencil down anywhere and just start drawing, always picking any unused edge. Each time you pass through a vertex, you use up two of its edges, so the number of edges available everywhere always remains even, and you will only "get stuck" upon returning to your starting vertex, where you used up one edge in your initial departure. At this point you might be done, but if not, the path you just created must visit some vertex where not all the edges were used up. (That's what "connected" means.) In this case, enlarge your cycle by "splicing in" another cycle, constructed the same way: start at a vertex on your path with an unused edge, and travel any way you want along unused edges; parity shows that you can only get stuck when you return to the vertex where your splice began. Keep splicing until all the edges are used up.
If your graph has two odd-degree vertices, start at one of them and do the same; you're guaranteed to eventually "get stuck" at the other one.
--Michael Kleber
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
On Thu, 3 Feb 2005 19:48:25 -0800, Steve Gray <stevebg@adelphia.net> wrote:
Very nice. You might have mentioned the situation where the path you just created did not visit some vertices at all, but that does not invalidate the argument.
I'm not sure where a mention would fit into the argument, actually. If your path is not yet complete, then there must be *some* vertex that has both included and excluded edges -- that's what the graph being connected means. But there may (or may not) be lots of vertices that have only path edges, and lots that have only non-path edges, and neither of those types plays any role in the construction. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
Quoting Steve Gray <stevebg@adelphia.net>:
An obvious theorem in simple graph theory says that no graph with no more than two nodes of odd order can be drawn in one continuous path. Is there a theorem saying that any graph with two, one, or zero nodes of odd order can always be drawn in one continuous path? A yes/no answer would be nice, and a reference would be even nicer.
Is that so obvious? Anyway, as to the converse --- think of a zillion nodes, all connected in pairs with no other connections. - hvm ------------------------------------------------- www.correo.unam.mx UNAMonos Comunicándonos
mcintosh@servidor.unam.mx Is that so obvious? Anyway, as to the converse --- think of a zillion nodes, all connected in pairs with no other connections.
Yikes, now nothing's obvious: think of a single node, connected to itself via infinitely many arcs. Now attach two of these to the arms of a "Y" to get an untraceable graph with two odd nodes...
participants (8)
-
Henry Baker -
Marc LeBrun -
mcintosh＠servidor.unam.mx -
Michael Kleber -
N. J. A. Sloane -
Russ Cox -
Steve Gray -
Thane Plambeck