User andy juell - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T21:39:42Z http://mathoverflow.net/feeds/user/24681 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/127040/matula-goebel-ordering-of-rooted-trees-intrinsic Matula-Goebel ordering of rooted trees intrinsic? Andy Juell 2013-04-10T04:58:39Z 2013-04-11T15:22:04Z <p>I was somewhat recently introduced to the Matula-Goebel bijection between rooted trees and natural numbers. (nicely illustrated here <a href="http://keithbriggs.info/matula.html" rel="nofollow">http://keithbriggs.info/matula.html</a>) Looking through them, I noticed that smaller integers were repeated as 'terminal subtrees' more often, which led me to wonder whether the MG numbering actually provided a perfect index of how frequently a given rooted tree would appear as such in the set of ALL rooted trees. I already knew that Schenk's Theorem implied that any (rooted) subtree would eventually occur in almost all (rooted) trees, and thus have asymptotic density of 1, but perhaps some subtrees raced to that density reliably faster than others? </p> <p>To find the set of trees containing our subtree of interest, we start with a set containing only the integer representing that subtree.</p> <ol> <li>for every n in the set, find the nth prime.</li> <li>add all multiples of this prime to the set.</li> <li>goto 1</li> </ol> <p>It seems entirely believable that the asymptotic density of all such sets must be 1 regardless of the starting integer...but larger starting n consistently have larger gaps in the final sequence. For two sets starting from different n, clearly there were at most a finite number of x for which the member counts of each set <p>Great! ...except there are infinitely many other bijections which construct a contradictory ordering.</p> <p>Nowhere in the definition of the MG bijection is addition used, only multiplication and ordinal comparison on the set of primes...so taking a page from Beurling's generalized integers, there's no reason we can't use a different list of primes when building the tree bijection, provided they still produce unique factorizations. Let's keep things simple and just remove 2, so we can easily map the resulting odd integers back to (x+1)/2. (unsurprisingly I wasn't the first to think of this, see OEIS A048673)</p> <p>so instead of 1,p1,p2,p1^2,p3,p1p2,p4,p1^3,p2^2,p1p3,p5...</p> <p>we now have 1,p1,p2,p3,p1^2,p4,p5,p1p2,p6,p7,p1p3,p8,p2^2,p1^3...</p> <p>which will clearly put the trees in a different ordering. But even using a different list of primes (and being careful how to interpret 'multiiples'), following the same reasoning would seem to require that this new ordering would also yield strictly decreasing 'densities' in the resulting sets. The pairs reversed by this permutation of the trees cannot both exceed the other's frequency, so I'm guessing I proverbially divided by zero somewhere above. </p> <p>To further deepen the confusion, or perhaps provide a direction toward resolution, a closer reading of Schenk (or at least people quoting him on this side of the paywall) seems to indicate that the number of trees containing a particular 'limb' depends only on the limb's size, not its internal structure, which would seem to make any such ordering within a given tree size dubious, and orderings placing larger trees before smaller (ie 18&lt;19) doubly so. </p> <p>So, to bring that all into a proper question or two:</p> <ol> <li><p>Is there an intrinsic meaning to the MG ordering applicable in the domain of rooted trees without reference to the multiplicative structure of the integers? (or perhaps some other well-ordering of them is more useful/meaningful?)</p></li> <li><p>I understand that bijections between infinite sets can yield rampant paradoxes if not handled with sufficient care...is this just another one, or have I committed a serious logical error in the above?</p></li> </ol> <p>Thanks in advance...</p> http://mathoverflow.net/questions/127030/reals-with-integer-powers-bounded-away-from-integers Reals with integer powers bounded away from integers? Andy Juell 2013-04-10T00:37:26Z 2013-04-10T02:34:17Z <p>Do there exist real numbers whose integer powers are bounded away from integers? More precisely, for an arbitrary constant 0 &lt; $\epsilon$ &lt; 1/2, does there exist real x such that for all positive integer n,<br> $\epsilon &lt; (x^n)$ mod 1 &lt; $1-\epsilon$?</p> <p>Pisot numbers more or less provide the opposite of this behavior, and at first I briefly thought that applying Hurwitz' Theorem to the logs might help...but ln(3)/ln(2) isn't rational, and $2^n$ and $3^n$ seem to keep a minimum unit distance apart. ^_^</p> http://mathoverflow.net/questions/22184/almost-or-probably-complete-graph-invariants/118656#118656 Answer by Andy Juell for Almost or probably complete graph invariants? Andy Juell 2013-01-11T18:02:45Z 2013-01-13T23:57:40Z <p>Though painfully slow to compute, I've yet to find a counterexample to the first invariant proposed in <a href="http://arxiv.org/abs/math/0503316" rel="nofollow">this</a> paper by Mehendale: a vector of integers counting, for each n, the number of labeled subgraphs of G which are trees on n vertices.</p> <p>Update: I've since discovered several counterexamples, perhaps the simplest being</p> <p>S3 U P2 U P2 </p> <p>and</p> <p>P4 U P3 U P1</p> <p>both of which yield the signature (8,5,3,1)</p> http://mathoverflow.net/questions/100554/possible-structures-for-minimal-tiling-sets Possible structures for minimal tiling sets Andy Juell 2012-06-25T00:22:33Z 2012-06-25T00:22:33Z <p>Inspired by Col. Sicherman's results <a href="http://recmath.org/PolyCur/mzuc/mzuc.html" rel="nofollow">here</a>, my speculations have so far outrun my expertise that I thought I might pass my question along to others who might find it equally intriguing, but perhaps somewhat less intimidating. Though I first approached it as a question regarding polyforms, it may be easier to attack in the more general case.</p> <p>Consider the infinite (hyper)graph G, whose vertices correspond to distinct polygonal tiles. A (hyper)edge links each minimal set of polygons which tile the plane. Thus, every polygon which tiles the plane on its own is an isolated vertex with a loop, leaving the remainder of the graph simple.</p> <blockquote> <p>What finite (hyper)graphs exist as induced subgraphs of G?</p> <p>Equivalently, for which finite (hyper)graphs can a set of tiles be constructed such that minimal tiling sets correspond exactly to the edges of the (hyper)graph? </p> </blockquote> <p>Hypergraphs consisting of a single maximal hyperedge (hyperclique?) are easily obtained: take a square, say, and slice it into n radial pieces, then give each adjacent pair a unique nick/bump combination. Complete bipartite graphs can be made by increasingly long unit-width rectangles, with one color class bumped on the unit side, and the other color class nicked. This can be extended to complete k-partite k-hypergraphs for arbitrary k by increasing the variety of nicks and bumps. </p> <p>Anything further I might add would be half-baked speculation, so I'll hope I've lurked here long enough to know what a decent first question is supposed to look like. ^_^ Thanks in advance! </p> http://mathoverflow.net/questions/127190/is-there-an-observer-dependent-mathematics Comment by Andy Juell Andy Juell 2013-04-11T13:53:16Z 2013-04-11T13:53:16Z I have to wonder whether it's entirely safe to refer to Greg Egan's &quot;Luminous&quot; ^_^ http://mathoverflow.net/questions/127030/reals-with-integer-powers-bounded-away-from-integers/127031#127031 Comment by Andy Juell Andy Juell 2013-04-10T02:35:31Z 2013-04-10T02:35:31Z Nifty...thanks! Somewhere between 7.3769347535 and 7.3769347577 lurks a number whose powers never stray within 1/3 of an integer... http://mathoverflow.net/questions/127030/reals-with-integer-powers-bounded-away-from-integers Comment by Andy Juell Andy Juell 2013-04-10T01:56:37Z 2013-04-10T01:56:37Z (was previously ICanChangeThisLaterRight) http://mathoverflow.net/questions/127030/reals-with-integer-powers-bounded-away-from-integers Comment by Andy Juell Andy Juell 2013-04-10T01:54:38Z 2013-04-10T01:54:38Z Duly noted. ^_^ http://mathoverflow.net/questions/11631/complete-graph-invariants/118655#118655 Comment by Andy Juell Andy Juell 2013-01-12T00:06:09Z 2013-01-12T00:06:09Z Yes...after posting I felt the response was if anything more applicable to the other thread [here](<a href="http://mathoverflow.net/questions/22184/almost-or-probably-complete-graph-invariants/118656" rel="nofollow" title="almost or probably complete graph invariants">mathoverflow.net/questions/22184/&hellip;</a>), sorry if this was inappropriate.