User benjamin young - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T09:54:17Z http://mathoverflow.net/feeds/user/20281 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/123890/numbers-of-distinct-products-obtained-by-permuting-the-factors/124913#124913 Answer by Benjamin Young for Numbers of distinct products obtained by permuting the factors Benjamin Young 2013-03-19T01:25:30Z 2013-03-19T01:25:30Z <p>Pedantic answer: take $G$ to be a finitely presented group on $n+1$ generators $x_i$, with relations of the form $x_{n+1}^{-1}x_{\sigma(1)}...x_{\sigma(n)}$. Here, $\sigma$ ranges over your favorite set of $n!-k+1$ permutations. Take $g_i=x_i$.</p> <p>If you really want a <em>finite</em> group $G$, then I don't know.</p> http://mathoverflow.net/questions/124747/tsp-but-for-all-routes-not-all-points/124750#124750 Answer by Benjamin Young for TSP, but for all routes not all points Benjamin Young 2013-03-17T04:53:38Z 2013-03-17T04:53:38Z <p>Pick a spanning tree of the ski trail map, e.g. by depth-first search or something. You can traverse it by always turning left at a junction. As you're doing this, walk out and back along each edge that's not in the tree. This uses each edge exactly twice.</p> http://mathoverflow.net/questions/121575/disjoint-maximum-independent-sets-in-alpha-critical-graphs/124435#124435 Answer by Benjamin Young for Disjoint Maximum Independent Sets in $alpha$-critical graphs Benjamin Young 2013-03-13T16:58:06Z 2013-03-13T17:44:07Z <p>I don't think so. You really mean maxiMUM, not maxiMAL, right?</p> <p>If so, take a complete bipartite graph $K_{m,n}$ with $m$ less than $n$, so the maximum critical set is the big part in the bipartition and is of size n. This graph isn't $\alpha$-critical, clearly, but its maximum independent set is so big that there's a pigeonhole problem with finding a disjoint second one.</p> <p>It seems to me that if you delete edges from G you can only increase the independence number, so (*) do this iteratively without disconnecting G until the result is $\alpha$-critical. </p> <p>This should give you a counterexample unless this last step (*) is flawed somehow, which might well be the case, I confess - I haven't thought it through. But rather than agonizing about whether it's possible, you can implement this randomly with a computer program, for explicit small m,n, until you have either generated an explicit counterexample, or waited for such a long time as to convince yourself that it's worth trying to find the error. I might do it if I have a chance today.</p> <p>EDIT -- I was wrong - step (*) is in fact flawed, because it disconnects the graph before it becomes $\alpha$-critical. Interesting!</p> http://mathoverflow.net/questions/124421/gelfand-yaglom-functional-determinant-of-non-diagonal-operator/124424#124424 Answer by Benjamin Young for Gel'fand Yaglom functional determinant of non-diagonal operator? Benjamin Young 2013-03-13T15:28:34Z 2013-03-13T15:28:34Z <p>Not an expert, but you caught my interest. Looks like you may need to be a little careful in higher dimensions, but there are versions of the theorem which work. See, for example:</p> <p><a href="http://library.msri.org/books/Book57/files/70kirsten.pdf" rel="nofollow">http://library.msri.org/books/Book57/files/70kirsten.pdf</a></p> http://mathoverflow.net/questions/124384/multivariate-functions-whose-value-is-independent-of-the-order-of-the-arguments/124387#124387 Answer by Benjamin Young for Multivariate functions whose value is independent of the order of the arguments Benjamin Young 2013-03-13T05:47:46Z 2013-03-13T05:47:46Z <p>You could symmetrize an arbitrary function by averaging it over the symmetric group.</p> <p>Explicitly: take your favourite function $h$ in $n$ variables, and set $f(r_1, ..., r_n) = \frac{1}{n!}\sum_{\sigma} h(r_{\sigma(1)}, ..., r_{\sigma(n)})$ where the sum is taken over all permutations $\sigma$ of the numbers $1,...,n$. </p> <p>I'd love to hear of an example which <em>isn't</em> obtained by symmetrization! </p> <p>edit: heh. Any such example would <em>be</em> its own symmetrization. So I guess in some sense this is a complete, if overly glib, answer.</p> http://mathoverflow.net/questions/122972/a-recursive-double-sequence-related-to-uniform-cardinal-b-spline/124358#124358 Answer by Benjamin Young for A recursive Double sequence related to uniform Cardinal B-spline Benjamin Young 2013-03-12T23:52:00Z 2013-03-13T04:10:03Z <p>Edit: ok, now that I have more than 5 minutes to spare I can clean this up a bit and add a wikipedia reference.</p> <p>I'm going to write A(n,k) for $A_n(k)$. First of all, note that it's easy to see that A(n,k) = A(n,-k) by induction on n, and that the A(n,k) are zero unless -n &lt;= k &lt;= n. So we may as well just start computing these things (with dynamic programming, for good practice) before we start thinking terribly hard:</p> <p>Sage code:</p> <pre><code>values = {} def A(n,k): if (n,k) in values: return values[(n,k)] if n==0: if k==0: result = 1 else: result = 0 else: result = (n + 1 - k)**2 * A(n-1, k-1) result += 2*(n*(n+1)-k**2) * A(n-1, k) result += (n + 1 + k)**2 * A(n-1, k+1) values[(n,k)]=result return result for n in range(5): print [A(n,k) for k in range(-n, n+1)] </code></pre> <p>Output:</p> <pre><code>[1] [1, 4, 1] [1, 26, 66, 26, 1] [1, 120, 1191, 2416, 1191, 120, 1] [1, 502, 14608, 88234, 156190, 88234, 14608, 502, 1] </code></pre> <p>One glance at the third row will tell any combinatorist that these are Eulerian numbers (at least, for odd n). See sequence A008292 at oeis.org. Also, wikipedia has a perfectly reasonable page on the Eulerian numbers: <a href="http://en.wikipedia.org/wiki/Eulerian_number" rel="nofollow">http://en.wikipedia.org/wiki/Eulerian_number</a>. There you can find a recursive formula. I'll use E(n,m) since A is taken already:</p> <p>$E(n,m) = (n-m)E(n-1,m-1) + (m+1)E(n-1,m)$. </p> <p>Of course this notation is different than yours; I think your numbers are $E(2n+1, m-n)$, You should be able to see this by applying the above recursive formula twice and doing the above change of variables to recover your own formula, though I haven't done it and may have made an error. There's lots of formulas for the Eulerian numbers and there's a lot known about them.</p> http://mathoverflow.net/questions/124292/solution-in-distinct-elements-for-a-system-of-n-equations-over-finite-fields/124330#124330 Answer by Benjamin Young for Solution in distinct elements for a system of $n$ equations over finite fields Benjamin Young 2013-03-12T16:54:18Z 2013-03-12T16:54:18Z <p>Are you sure you've posed the question correctly?</p> <p>You see, sometimes you can't even solve for $x_1$. In particular, this happens if $y_1$ is such that $y_1 + {x_m}^2$ is a quadratic nonresidue. So there is no such maximum $n$; even when $n=1$ there exist situations where there is no solution. That can't be what you meant.</p> <p>In an attempt to discover a version of the question with a more interesting answer, let's further suppose that the $y_i$ are chosen in such a way that $y_i + {x_m}^2$ are all quadratic residues. But this is boring for the opposite reason: you can <em>always</em> solve the system. Since you've forced all the $y_i$ to be distinct, then there is no obstruction to finding solutions until you run out of values of $y_i + {x_m}^2$ which are quadratic residues. The maximum $n$ where there's a solution is when you take $n$ to be the number of distinct nonzero quadratic residues mod $p$... I am still left with the sense that I haven't told you anything you didn't already know.</p> http://mathoverflow.net/questions/123681/invertibility-of-a-certain-matrix-indexed-by-the-hamming-cube/123705#123705 Answer by Benjamin Young for Invertibility of a certain matrix indexed by the Hamming cube Benjamin Young 2013-03-06T05:21:51Z 2013-03-08T04:26:37Z <p>Depends on what you call enlightening. I've got a different viewpoint on this than most other mathematicians I've met.</p> <p>To prove that this matrix A is invertible, you should guess its inverse M explicitly, and then prove that AM=I. This is certainly enough to prove that it's invertible! It's also potentially enlightening (or at least interesting) because now you get to try and think of an interpretation for the elements of the inverse.</p> <p>Anyway, the point is that the guessing part is really, really easy in this instance, because there's an obvious structure in the inverse of the matrix. Here's the inverse for n=3, computed in sage:</p> <pre><code>[ 0 0 0 0 0 -1 1] [ 0 0 0 0 -1 0 1] [ 0 0 0 -1 1 1 -1] [ 0 0 -1 0 0 0 1] [ 0 -1 1 0 0 1 -1] [-1 0 1 0 1 0 -1] [ 1 1 -1 1 -1 -1 1] </code></pre> <p>and for n=4:</p> <pre><code>[ 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1] [ 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 1] [ 0 0 0 0 0 0 0 0 0 0 0 -1 1 1 -1] [ 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 1] [ 0 0 0 0 0 0 0 0 0 -1 1 0 0 1 -1] [ 0 0 0 0 0 0 0 0 -1 0 1 0 1 0 -1] [ 0 0 0 0 0 0 0 -1 1 1 -1 1 -1 -1 1] [ 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1] [ 0 0 0 0 0 -1 1 0 0 0 0 0 0 1 -1] [ 0 0 0 0 -1 0 1 0 0 0 0 0 1 0 -1] [ 0 0 0 -1 1 1 -1 0 0 0 0 1 -1 -1 1] [ 0 0 -1 0 0 0 1 0 0 0 1 0 0 0 -1] [ 0 -1 1 0 0 1 -1 0 0 1 -1 0 0 -1 1] [-1 0 1 0 1 0 -1 0 1 0 -1 0 -1 0 1] [ 1 1 -1 1 -1 -1 1 1 -1 -1 1 -1 1 1 -1] </code></pre> <p>That is, let A(n) be the matrix for sets of size n, where the rows and columns are in lex order, and M(n) be its inverse. Then conjecturally M(n) has the following block structure:</p> <pre><code>[ 0 -v' M(n-1) ] [ -v 0 v ] [ M(n-1) v' -M(n-1) ] </code></pre> <p>where v is the vector [0, 0, ... 0, 1]. I'm pretty sure it'd be easy to prove this inductively, as A itself has a similar block structure - though I confess I haven't done it.</p> <p>EDIT: Here's the sage code that produces the matrix. Obviously it's not the smartest way to go about doing things, but it was adequate. If anyone knows a smarter but equally terse way of iterating over the power set than converting it to a list, let me know!</p> <pre><code>def nonempty_powerset(n): return list(powerset(range(n)))[1:] def A(n): L = nonempty_powerset(n) def entry(i,j): set1 = set(L[i]) set2 = set(L[j]) if len(set1.intersection(set2)) &gt; 0: return 1 else: return 0 return Matrix(2**(n)-1, 2**(n)-1, entry) </code></pre> http://mathoverflow.net/questions/88607/complement-to-part-of-a-permutation-matrix/92824#92824 Answer by Benjamin Young for Complement to part of a permutation matrix Benjamin Young 2012-04-01T17:03:42Z 2012-04-01T17:03:42Z <p>You get all possible $E_2$ by starting with an $(n-m) \times (n-m)$ permutation matrix, and expand it to being $(n-m) \times n$ by inserting columns of zeros under each of the ones of $E_1$. That is, there's an easy bijection between your set and the order $(n-m)$ permutation matrices. I think you knew this already. </p> <p>I guess what I'm driving at is that even if there is some canonical name for this object in some field of mathematics, the set that you want to name is simple enough that you can describe it in one sentence. If you need to give this set a name, just call it $percomp_n(E_1)$, like you wanted to do. People do this all the time. Indeed, most of us would be even <em>more</em> confused if you dig up an obscure, but technically correct, name. </p> http://mathoverflow.net/questions/85346/maximum-number-of-hyperedges-in-a-directed-hypergraph/85361#85361 Answer by Benjamin Young for Maximum number of hyperedges in a directed hypergraph Benjamin Young 2012-01-10T20:06:00Z 2012-01-10T20:06:00Z <p>I doubt there's a completely standard definition. </p> <p>It seems like this is elementary -- an undirected edge is a size-$k$ subset of $[1,n]$, and a directed edge is an undirected edge together with one of the possible $2^k$ labellings of it with "T" and "H". So the number of different edges is (if, say, empty head- and tail-sets are allowed)</p> <p>$\sum_{k=0}^n \binom{n}{k} 2^k = 3^n$</p> <p>Presumably a directed hypergraph consists of any collection of such edges, so there are $2^{3^n}$ of them. If this isn't the precise question you were wondering about, I'd wager that the one you're interested in is just as easy to count.</p> http://mathoverflow.net/questions/78497/arctic-regions-in-higher-dimensional-zonotopes/84611#84611 Answer by Benjamin Young for Arctic regions in higher dimensional zonotopes Benjamin Young 2011-12-30T21:26:27Z 2012-01-09T19:31:49Z <p>Basically nothing is known beyond what you've said, and it doesn't look like that's going to change anytime soon.</p> <p>There is at least one piece of relevant numerical work which I know of: J. Linde, the first author in the paper you mentioned, posted some graphs on his website which suggest that the height function isn't quite flat inside the octahedron. This means that the entropy isn't likely to be constant in there, either. </p> <p><a href="http://www.joakimlinde.se/projects/rhombusTilings/" rel="nofollow">http://www.joakimlinde.se/projects/rhombusTilings/</a> </p> <p>There are some heuristic reasons why we should expect flat facets on the arctic regions for these problems when d>3. For instance, similar problems have been studied with torus boundary conditions and a slightly different lattice, and the height function there is extremely flat. See <a href="http://arxiv.org/abs/1005.4636" rel="nofollow">http://arxiv.org/abs/1005.4636</a>.</p> <p>Other than that, the only other work I know about these higher dimensional tilings is numerical work on solid partitions, counted by volume. MacMahon made some guesses about how many solid partitions there are of a given volume, which Knuth proved to be incorrect in the sixties. It seems that MacMahon might have guessed an asymptotically correct answer, however, according to the results of this project. It uses massively parallel computation to count solid partitions by volume:</p> <p><a href="http://boltzmann.wikidot.com/solid-partitions" rel="nofollow">http://boltzmann.wikidot.com/solid-partitions</a></p> <p>and their project has generated a paper,</p> <p><a href="http://arxiv.org/pdf/1105.6231v3" rel="nofollow">http://arxiv.org/pdf/1105.6231v3</a></p> <p>which I just found and haven't read properly yet. There's also some approximate counting work due to Mustonen and Rajesh, which reaches the same conclusion; it's cited in the above paper.</p> http://mathoverflow.net/questions/84887/mobius-transform-of-a-continuous-possibility-function/84941#84941 Answer by Benjamin Young for Möbius Transform of a Continuous Possibility Function Benjamin Young 2012-01-05T09:57:57Z 2012-01-07T19:28:37Z <p>(edit) Okay, so as far as i can see you want to find a replacement for the mobius transform, but for a $\sigma$-algebra. In fact I'm going to guess that your $\sigma$-algebra is the measurable sets in the unit interval, based on what you've said.</p> <p>The most general setting I know of in which you can define a Möbius function is a locally finite, partially ordered set (see, for example, <a href="http://en.wikipedia.org/wiki/Incidence_algebra" rel="nofollow">http://en.wikipedia.org/wiki/Incidence_algebra</a>). So it sounds like you're out of luck. The measurable sets definitely don't form a locally finite poset.</p> <p>However, I really don't think you've asked the right question yet. You probably would get better answers than mine if you frame your question in terms of measure theory, rather than Möbius inversion. For instance, the wikipedia article seems to imply that I should think of Möbius inversion as "analagous to differentiation", and convolution with the zeta function as "analagous to integration". I don't really find this too helpful, but that's what it says. Maybe you're looking for some kind of derivative? Just a guess.</p> http://mathoverflow.net/questions/85065/unexpected-applications-of-the-fact-that-nth-degree-polynomimals-are-determined-b/85075#85075 Answer by Benjamin Young for Unexpected applications of the fact that nth degree polynomimals are determined by n+1 points Benjamin Young 2012-01-06T18:06:36Z 2012-01-06T20:07:10Z <p>Many computer-generated proofs use this technique. <strike>For instance, there is an entire euclidean geometry textbook written this way! It is available on Doron Zeilberger's web page.</p> <p>It is titled "Plane Geometry: an elementary textbook", and it is attributed thus: "By Shalosh B. Ekhad, XIV (Circa 2050), downloaded from the future by Doron Zeilberger". Zeilberger, it seems, always names his current computer Shalosh B. Ekhad and frequently cites them as his coauthors.</p> <p><a href="http://www.math.rutgers.edu/~zeilberg/GT.html" rel="nofollow">http://www.math.rutgers.edu/~zeilberg/GT.html</a>. </p> <p>All the theorems are proven by computer-generated proofs, and they rely upon this property of polynomials. As such, the proofs are most easily read if one understands Maple's programming language, so whether they'd work as a good math education tool would strongly depend on your audience. </strike></p> <p>okay, that was embarassing. These proofs actually do not use this mechanism at all, they rely instead on the correctness of Maple's symbolic algebra code (specifically the solve function). The proof I was thinking of was in section 1 of A=B, by Marko Petkovsek, Herbert Wilf and Doron Zeilberger; it's a proof that the angle bisectors of a triangle meet in a point. There are other, non-geometric theorems proved there using the same trick.</p> <p>The book is available online: <a href="http://www.math.upenn.edu/~wilf/AeqB.html" rel="nofollow">http://www.math.upenn.edu/~wilf/AeqB.html</a> </p> <p>Remove those upvotes please, people...</p> http://mathoverflow.net/questions/85042/definition-of-orghogonal-orghonormal/85045#85045 Answer by Benjamin Young for Definition of orghogonal / orghonormal Benjamin Young 2012-01-06T11:11:46Z 2012-01-06T11:18:22Z <p>I think it's a typo. It's probably rather more common than other typos, because the letters "t,h,g" are very close to each other on a standard keyboard. As a result, it actually does appear in the literature rather more often than you'd expect, and always without definition. </p> <p>(As such, I believe this post qualifies as a legitimate research question and shouldn't be closed, despite the fact that it's about a trivial typographical error. Hilarious!)</p> <p>For instance, here it is in a google books search result: <a href="http://goo.gl/aDvQR" rel="nofollow">http://goo.gl/aDvQR</a>. It appears in the second page of an article in a collection of proceedings of a conference, without any definition. Elsewhere in the article it seems to be talking about orthogonality.</p> <p>Of course I'd be happy to be proven wrong - probably the best thing to do is to contact someone who's used the word in print. Maybe they know what it means.</p> <p>Edit: More evidence. <a href="http://goo.gl/gnqcl" rel="nofollow">http://goo.gl/gnqcl</a> (compare the title to that of the pdf link), <a href="http://goo.gl/UUONh" rel="nofollow">http://goo.gl/UUONh</a> (previous sentence uses the word "orthogonal")</p> http://mathoverflow.net/questions/40445/implementations-of-domino-shuffling-algorithm/84906#84906 Answer by Benjamin Young for implementations of domino shuffling algorithm Benjamin Young 2012-01-04T21:48:54Z 2012-01-06T08:42:22Z <p>Here is one which produces ASCII art aztec diamond tilings. It's written in perl. As I recall, I wrote it as fast as possible, without making any attempt to do it efficiently, because I needed to make some pictures really quickly.</p> <pre><code>#!/usr/bin/perl -w use strict; #================================================================= sub delete_odd_blocks($) { my$diamond = shift; for my $r (0..scalar @$diamond - 2) { my $c = index($$diamond[r], "--" ); while(c != -1) { if(substr($$diamond[$r+1], $c, 2) eq "==") { substr($$diamond[r], c, 2) = "BB"; substr($$diamond[$r+1], $c, 2) = "BB"; }$c = index($$diamond[r], "--", c + 2); } c = index($$diamond[$r], "!|" ); while($c != -1) { if(substr($$diamond[r+1], c, 2) eq "!|") { substr($$diamond[$r],$c, 2) = "BB"; substr($$diamond[r+1], c, 2) = "BB"; } c = index($$diamond[$r], "!|",$c + 2); } } } #================================================================= sub slide($) { my$diamond = shift; my $N = scalar @$diamond; # $N rows in the diamond die "$N is an odd number" if($N % 2); my (@output); for my$r (0..$N/2) { my$row = " "x$r . "A" x($N - 2*$r+2) . " "x$r; push @output, $row; unshift @output,$row; } push @$diamond, " "x$N; for my $r (0..scalar @$diamond - 1) { my $c = index($$diamond[r], "|" ); while(c != -1) { if(substr($$diamond[$r+1], $c, 1) eq "|") { substr($output[$r+1],$c, 1) = "|"; substr($output[$r+2], $c, 1) = "|"; }$c = index($$diamond[r], "|", c + 1); } c = index($$diamond[$r], "!" ); while($c != -1) { if(substr($$diamond[r+1], c, 1) eq "!") { substr(output[r+1], c+2, 1) = "!"; substr(output[r+2], c+2, 1) = "!"; } c = index($$diamond[$r], "!",$c + 1); } $c = index($$diamond[r], "--" ); while(c != -1) { substr(output[r+2], c+1, 2) = "--"; c = index($$diamond[$r], "--", $c + 2); }$c = index($$diamond[r], "==" ); while(c != -1) { substr(output[r], c+1, 2) = "=="; c = index($$diamond[$r], "==",$c + 2); } } pop @$diamond; \@output; } #================================================================= sub fill_even_blocks($) { my $diamond = shift; for my$r (0..scalar @$diamond - 2) { my$c = index($$diamond[r], "AA" ); while(c != -1) { if(substr($$diamond[$r+1],$c, 2) eq "AA") { if(rand() &lt; 0.5) { substr($$diamond[r],c,2) = "=="; substr($$diamond[$r+1],$c,2)= "--"; } else { substr($$diamond[r],c,2) = "|!"; substr($$diamond[$r+1],$c,2)= "|!"; } } $c = index($$diamond[$r], "AA", $c + 2); } } } my$dimers; if(rand() &lt; 0.5) { $dimers = ["|!", "|!"]; } else {$dimers = ["==", "--"]; } my $n = shift or die "Tell me the order of the diamond please\n"; for(1..$n-1) { delete_odd_blocks($dimers);$dimers = slide($dimers); fill_even_blocks($dimers); } for (@$dimers) { print "$_\n" } </code></pre> <p>Here is a sample of the output (the outcome of running "perl shuffle 5" on the command line, if you called this script shuffle):</p> <pre><code> == ==== |!|!== ||!|!--! |||!|!==!! |||!|!!|!! ||--!!|! ||!!-- |!-- -- </code></pre> <p>The domino shuffling algorithm has four types of dominoes: northbound, southbound, eastbound and westbound. I use "==", "--", for the northbound, southbound ones; two | symbols for the westbound ones and two ! for the eastbound ones. </p> <p>This script, as I recall, was the first link in a tool chain which produced the following image of the height function of an Aztec Diamond (this link will eventually go stale, but it should be good for a year or two anyway):<img src="http://www.math.kth.se/~benyoung/order51.png" alt="Order 51 Aztec Diamond"></p> http://mathoverflow.net/questions/84857/equitable-allocation-of-individuals-to-positions/84896#84896 Answer by Benjamin Young for Equitable Allocation of Individuals to Positions Benjamin Young 2012-01-04T18:22:50Z 2012-01-04T18:57:55Z <p>It seems to me you should be able to work out a formula for $p_{ij}$ explicitly, by solving that system of linear equations you wrote down. More to the point, you can do this before deciding on what algorithm you're going to use to assign the ranks.</p> <p>For this solution to correspond to a real-world solution to your problem, it seems to me that the matrix $P = (p_{ij})$ ought to be doubly stochastic (its rows and columns should sum to 1), because everyone should get a rank, and every rank should get a person. If this doesn't happen, you're out of luck. </p> <p>Once you've done this, your doubly stochastic matrix $P$ can be expressed as a convex combination of permutation matrices (this is the Birkhoff-Von Neumann theorem). Each of these permutation matrices corresponds to a rank assignment. </p> <p>You should be able to come up with your algorithm, then, by finding a constructive proof of Birkhoff-Von Neumann and realizing it with code. I sort of doubt that this would be efficient without further cleverness, but it might be a place to start.</p> http://mathoverflow.net/questions/84824/an-operation-on-binary-strings/84880#84880 Answer by Benjamin Young for an operation on binary strings Benjamin Young 2012-01-04T12:39:42Z 2012-01-04T14:04:42Z <p>Well, it has now, since I just sank my morning into studying it. I sure am a sucker for a naive combinatorics problem. Here's what I know, or can conjecture:</p> <ul> <li>The map you describe is a bijection on words of length $n$, because it's easy to write down its inverse. I've included python code below. </li> <li>Let $B_L$ be the bounce-reading algorithm. Let $B_R$ be the bounce-reading algorithm with the following change: replace the phrase "we start by reading the string at the left" with "we start by reading the string at the right". Then $B_LB_R^{-1}(w)$ seems to shift $w$ cyclically by one letter. Sometimes the shift is the left, and sometimes to the right; which of these things happens depends on $w$ in a manner which I don't understand. I noticed this because the maximal orbit sizes of $B_LB_R^{-1}(w)$ for each $n$ seem to match the OEIS sequence <a href="https://oeis.org/A027375" rel="nofollow">https://oeis.org/A027375</a>.</li> <li>Let $S_n$ be the set of words $w$ of length $n$ for which $B_L(w) = B_R(w)$. Then the sequence ${|S_{n+1}| - |S_n|}$ seems to be the Fibonacci numbers, at least for $n\geq 2$. This probably means $S_n$ has some nice structure.</li> </ul> <p>None of the other obvious statistics that describe this map are in the OEIS yet.</p> <p>Here are naive python implementations of $B_L, B_R, B_L^{-1}, B_R^{-1}$ if you want to check these assertions.</p> <pre><code>def bounce_left(w): if len(w) == 1: return w leftchar = w[0] x = w[1:] if(leftchar == "L"): return leftchar + bounce_left(x) else: return leftchar + bounce_right(x) def bounce_right(w): if len(w) == 1: return w last_index = len(w) - 1 rightchar = w[last_index] x = w[:last_index] if(rightchar == "L"): return rightchar + bounce_left(x) else: return rightchar + bounce_right(x) def unbounce(w): if w == "": return "" output = "" n = len(w) - 1 for index in reversed(range(n)): if w[index] == "L": output = w[index+1] + output else: output = output + w[index+1] return output def unbounce_left(w): return unbounce("L" + w) def unbounce_right(w): return unbounce("R" + w) </code></pre> http://mathoverflow.net/questions/58390/on-macmahons-conjecture-and-a-schur-function-identity/84616#84616 Answer by Benjamin Young for On MacMahon's conjecture and a Schur function identity Benjamin Young 2011-12-30T23:00:56Z 2011-12-30T23:00:56Z <p>I doubt it... as far as I know, the RSK correspondence isn't very well-behaved on the set of Young tableaux that you need. </p> <p>This doesn't entirely rule out the possibility of other "nice" proofs, though with current technology, I think you'll need to do a determinant evaluation at some point for this particular problem. That's not necessarily a bad thing, as there are some rather astonishing modern ways of evaluating determinants, especially those coming from tiling problems, plane partitions and the like. </p> <p>I'd suggest you take a look at C. Krattenthaler's inspiring papers "Advanced Determinant Calculus", <a href="http://arxiv.org/pdf/math.CO/9902004" rel="nofollow">http://arxiv.org/pdf/math.CO/9902004</a>, and "Advanced Determinant Calculus: A Complement", <a href="http://arxiv.org/pdf/math/0503507" rel="nofollow">http://arxiv.org/pdf/math/0503507</a>.</p> http://mathoverflow.net/questions/84364/computing-average-height-functions-for-lozenge-tilings/84609#84609 Answer by Benjamin Young for computing average height-functions for lozenge tilings Benjamin Young 2011-12-30T20:59:07Z 2011-12-30T20:59:07Z <p>David Speyer made a blog post a while back saying how to do this:</p> <p><a href="http://sbseminar.wordpress.com/2009/10/21/rhombus-tilings-and-an-over-constrained-recurrence/" rel="nofollow">http://sbseminar.wordpress.com/2009/10/21/rhombus-tilings-and-an-over-constrained-recurrence/</a></p> <p>It wasn't the main point of the blog post, but he does say how to use Kuo's graphical condensation method to compute such things. In short, if $H(a,b,c)$ is the set of perfect matchings on your hexagon, you're supposed to think of Kuo's beautiful technique as a bijection between the sets</p> <p>$H(a,b,c) \times H(a-1,b-1,c)$</p> <p>and</p> <p>$[H(a-1,b,c) \times H(a,b-1,c)] \cup [H(a,b,c-1) \times H(a-1,b-1,c+1)]$</p> <p>If you're interested in the expected value of some statistic on $H(a,b,c)$ --- he was talking about edge-placement probabilities, but I don't see why it wouldn't work for the height function at a given face --- you should compute this expectation on both sides of Kuo's bijection. In general that'd be tricky, but for the hexagon, it's quite tractable to do, since you know the sizes of all of these sets explicitly. For instance, MacMahon gave a closed formula for $H(a,b,c)$, which can also be found in Kuo's paper; Speyer even works out the relative sizes in his post for you. This gives you a recursive answer to your question, by dividing through by the term which came from the expected height function of $H(a-1,b-1,c)$. The base case is where one of a,b, or c is zero, which is easy.</p> <p>That's not code, obviously. Sorry! I'm rather busy travelling over the next few weeks, but I can try to do it in January sometime. If I forget, and nobody else does it, please remind me.</p> http://mathoverflow.net/questions/123890/numbers-of-distinct-products-obtained-by-permuting-the-factors/124913#124913 Comment by Benjamin Young Benjamin Young 2013-04-25T05:14:06Z 2013-04-25T05:14:06Z Hmm, I guess I don't either, now that you mention it. http://mathoverflow.net/questions/124923/evaluating-an-infinite-product-of-q-exponentials Comment by Benjamin Young Benjamin Young 2013-03-19T20:42:44Z 2013-03-19T20:42:44Z Ah, as I expected, I was being stupid. :) http://mathoverflow.net/questions/124923/evaluating-an-infinite-product-of-q-exponentials Comment by Benjamin Young Benjamin Young 2013-03-19T04:01:58Z 2013-03-19T04:01:58Z I'm not seeing how to write the generating function for plane partitions in terms of the q-exponential. Can you explain, or provide a reference please? Or is it really easy and I'm just being stupid? I guess I'm mainly asking out of personal interest, but it might be helpful. http://mathoverflow.net/questions/123681/invertibility-of-a-certain-matrix-indexed-by-the-hamming-cube/123705#123705 Comment by Benjamin Young Benjamin Young 2013-03-08T04:16:58Z 2013-03-08T04:16:58Z No problem - you're welcome. http://mathoverflow.net/questions/123681/invertibility-of-a-certain-matrix-indexed-by-the-hamming-cube/123934#123934 Comment by Benjamin Young Benjamin Young 2013-03-08T04:08:11Z 2013-03-08T04:08:11Z I am curious, since it turned out so nicely here: In the general setting, is the matrix inverse known? http://mathoverflow.net/questions/97049/comparing-the-edelman-greene-bijection-to-david-littles-bijection/110952#110952 Comment by Benjamin Young Benjamin Young 2012-11-04T16:26:44Z 2012-11-04T16:26:44Z I suppose it's bad form for me to upvote this answer? http://mathoverflow.net/questions/98899/a-conjecture-about-directed-graphs-that-are-the-union-of-two-trees Comment by Benjamin Young Benjamin Young 2012-06-07T16:38:52Z 2012-06-07T16:38:52Z Should the two directed spanning trees comprising D have the same root? http://mathoverflow.net/questions/96782/vector-balancing-problem Comment by Benjamin Young Benjamin Young 2012-05-12T18:32:05Z 2012-05-12T18:32:05Z I too would like to see an example of such a set of vectors $v_i$. http://mathoverflow.net/questions/86546/generating-function-related-to-2-residues-of-partitions Comment by Benjamin Young Benjamin Young 2012-04-01T18:12:28Z 2012-04-01T18:12:28Z why does partial differentiation fail, exactly? It looks like the operator $2y \frac{d}{dy} - 2x \frac{d}{dx} + 1$ might recover your generating function. http://mathoverflow.net/questions/90314/geometric-construction-of-uniform-measure-on-plane-partitions-in-a-box Comment by Benjamin Young Benjamin Young 2012-04-01T16:03:46Z 2012-04-01T16:03:46Z $a \times b \times c$ boxed plane partitions can be described as families of $c$ nonintersecting lattice paths with $a+b$ steps. So a natural guess is to do your random point selection $c$ times, conditioned on the event that the lattice paths you get form a nonintersecting lattice path ensemble in the proper way. Does that work? http://mathoverflow.net/questions/92753/sums-of-powers-mod-p Comment by Benjamin Young Benjamin Young 2012-04-01T15:08:32Z 2012-04-01T15:08:32Z The condition $p&gt;7$ can be removed. Very important. :) http://mathoverflow.net/questions/85657/calculating-enclosing-cubic-volume Comment by Benjamin Young Benjamin Young 2012-01-14T15:21:37Z 2012-01-14T15:21:37Z Uh, volume of the space - number of cubes? What am I missing here? http://mathoverflow.net/questions/84824/an-operation-on-binary-strings/84880#84880 Comment by Benjamin Young Benjamin Young 2012-01-12T20:03:25Z 2012-01-12T20:03:25Z Cool, I knew that worked in perl, good to know I can still get away with it. I'm only just learning python now, so I tend to use a pretty small subset of the language. http://mathoverflow.net/questions/85154/a-question-about-how-far-projective-geometry-can-be-extended Comment by Benjamin Young Benjamin Young 2012-01-07T21:58:24Z 2012-01-07T21:58:24Z Do you mean this by any chance? <a href="http://en.wikipedia.org/wiki/Projective_Hilbert_space" rel="nofollow">en.wikipedia.org/wiki/Projective_Hilbert_space</a> http://mathoverflow.net/questions/84887/mobius-transform-of-a-continuous-possibility-function/84941#84941 Comment by Benjamin Young Benjamin Young 2012-01-07T11:46:23Z 2012-01-07T11:46:23Z That doesn't make sense I'm afraid...