User bobuhito - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T00:20:07Z http://mathoverflow.net/feeds/user/20757 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/128882/fastest-digit-extraction-for-any-irrational-number Fastest Digit Extraction for Any Irrational Number bobuhito 2013-04-27T02:31:19Z 2013-05-25T21:22:00Z <p>I believe the current lowest-memory algorithm for computing the $n^{th}$ binary digit of $\pi$ requires $O(log(n))$ bytes and $O(n^2 log(n))$ days (I pick Bellard over Bailey–Borwein–Plouffe for speed).</p> <p>Can any of the common irrational constants be currently computed with the same low memory, but in faster time? Please consider constants which combine integers and $\pi$, natural exponential functions, and/or root functions (e.g., $\pi$, $\pi^2$, $e$, $e^{-\pi}$, $\sqrt2$, $\sqrt{2\pi}$).</p> <p>For any such constant, I am also curious about the randomness in its binary tail. These digit extraction constraints cause correlations in the constant's tail bits which probably go to zero for high $n$ (but, for $\pi$, the Bellard/BBP constraints are too subtle for me to conclude anything). If anyone has a low-memory method to distinguish a tail of some common irrational number from random bits (with the same speed in the limit of high $n$), please comment.</p> http://mathoverflow.net/questions/130413/non-constant-sum-blotto-game-for-only-2-players-and-2-battlefields Non-Constant-Sum Blotto Game for Only 2 Players and 2 Battlefields bobuhito 2013-05-12T14:19:40Z 2013-05-13T03:49:16Z <p>In the simplest asymmetric Colonel Blotto game with 2 players, dividing their given Ni soldiers (i=1,2) over 2 battlefields, what are their expected utilities, Ui (i.e., expected number of battlefield victories), in a Nash Equilibrium?</p> <p>If the continuum Ni case is significantly easier to solve, you can consider the individual soldiers to be divisible. I’d also like to see an explicit Nash Equilibrium strategy for the two players, but it seems that there might be many cases, so it can’t be written down simply.</p> http://mathoverflow.net/questions/106705/2d-problems-which-are-easier-to-solve-in-3d 2D Problems Which are Easier to Solve in 3D bobuhito 2012-09-09T03:12:40Z 2013-04-27T04:18:20Z <p>It sometimes happens that 1D problems are easier to solve by somehow adding a dimension. For example, we convert linear differential equations for a real unknown to a complex unknown (to use complex exponentials), or we compute a power series' radius of convergence by thinking in the complex plane (or use complex analytic properties in path integrals), or we evaluate $\int^\infty_{-\infty} e^{-x^2}\ dx$ by squaring it...</p> <p>So, are any 2D problems easier to solve in even higher dimensions? I can't think of any.</p> http://mathoverflow.net/questions/128212/special-primes-with-p4p1 special primes with p'=4p+1 bobuhito 2013-04-21T07:35:37Z 2013-04-21T20:39:14Z <p>How can I most quickly find a big prime, p, for which 4p+1 is also prime? For example, p=37 works. I wonder if these special primes have been researched and some characteristics are known. Are there infinitely many of these primes?</p> http://mathoverflow.net/questions/127228/box-nodes-in-directed-graphs-with-paired-io-symmetry "Box Nodes" in Directed Graphs with Paired IO Symmetry bobuhito 2013-04-11T12:00:42Z 2013-04-12T01:22:42Z <p>Consider directed graphs where all nodes have 2 inputs and 2 outputs. If we design a box with N inputs and N outputs, what is the smallest number of nodes it must contain to satisfy “pair symmetry” (i.e., each input is paired with some output, but relabeling the N pairs does not change the graph). Please specify the corresponding minimal graph solutions for N=3 and N=4.</p> <p>Here are two graph examples to help show what I'm looking for: <img src="http://sites.google.com/site/bobuhito/graphs/examples.PNG" alt="alt text"></p> http://mathoverflow.net/questions/109264/optimum-tournament-strategy Optimum Tournament Strategy bobuhito 2012-10-10T00:58:28Z 2012-10-10T09:59:45Z <p>Consider a symmetric N-player game in which all players partition one total unit of energy among individual games. The probability of winning each game is simply proportional to the spent energy (player #1 wins with probability $\frac{E_1}{E_1+E_2+...+E_N}$). The winner is the first player to win G games.</p> <p>Before each game, players know both "how much energy each person has left" and "how many games each person has won" to choose the energy to spend in the next game. (I'm additionally interested in game theory if these are not both known, but that's a bonus.)</p> <p>A full game-tree solution for all cases would be nice, but maybe too much to ask for...instead, how much energy should be spent on the first game if N=2 and G=4 (World Series)?</p> <p>[this is a tangent from http://mathoverflow.net/questions/107390/flipping-coins-on-a-budget]</p> http://mathoverflow.net/questions/106163/inter-kissing-number-for-non-spheres Inter-Kissing Number for Non-Spheres bobuhito 2012-09-02T07:33:50Z 2012-09-02T09:08:34Z <p>In 3D, the maximum number of spheres which can inter-touch is 5 (mathoverflow.net/questions/106120). This maximum reduces to 4 for unit spheres.</p> <p>Is there a different shape (e.g., an egg, or a pyramid) for which these maximums are not 5 and 4? If so, what shape has the highest maximum? To avoid "corner touching" (e.g., 8 cubes could all touch at one corner), please additionally require that every "touch-point" have only 1 "official connection" (e.g., only 2 of the 8 cubes can be declared as touching at the corner).</p> http://mathoverflow.net/questions/106120/inter-kissing-number-for-spheres-of-different-sizes Inter-Kissing Number for Spheres of Different Sizes bobuhito 2012-09-01T17:47:22Z 2012-09-01T20:22:50Z <p>What is the maximum number of spheres that can be placed in 3D such that all inter-touch?</p> <p>One can of course place four unit spheres tetrahedrally and then add a smaller sphere in the middle, so this number must be at least 5.</p> <p>[By the way, I was trying to extend the "five points in 2D cannot be inter-connected without a crossing" limitation to 3D with a simple statement, but this was sadly the best I could do. If anyone knows a better simple extension, please comment.]</p> http://mathoverflow.net/questions/103424/non-linear-perturbation-operator-examples Non-linear Perturbation Operator Examples bobuhito 2012-07-29T04:46:01Z 2012-07-29T04:46:01Z <p>Consider a non-linear operator $\cal H$ which maps a function to a function (e.g., a map from a starting wave function $f(x,y,z)$ to a later wave function according to some non-linear PDE) and an $\epsilon$-perturbation on the input function. All real-world examples that i can think of can then be linearized (to some non-zero linear operator $\cal A$ with some order $m$) for small $\epsilon$: $$\cal H[f+\epsilon g]-\cal H[f]=\epsilon^m \cal A[g] \qquad +O(\epsilon^{m+1})$$ Are there any real-world counter-examples which stay non-linear in this limit? I know I haven't defined "real-world"; I'd ideally like a non-linear PDE, but would settle for anything that comes up in some application (e.g., integral equations, or system-control vectors).</p> http://mathoverflow.net/questions/87234/magma-coercion-syntax Magma Coercion Syntax bobuhito 2012-02-01T14:53:32Z 2012-03-27T18:42:04Z <p>Any Magma experts who know what I should write below in place of "Roots(ysoln)"? I basically want the roots of a FldFunRatMElt (variable here happens to show as "$.2"). I would guess there's some simple coercion needed, but I've had no luck finding examples for this on the internet. I really just need to know the rational roots. Thanks!</p> <pre><code>PP&lt;x,y,z&gt;:=ProjectiveSpace(Rationals(),2); CU:=Curve(PP, (z + x - y)*(z - x + y)*(-z + x + y)*(z + x + y)); curve:=DefiningPolynomials(CU)[1]; ysoln:=Evaluate(curve,[1,y,1]); ysoln; Type(ysoln); ysoln:=Evaluate(ysoln,[1,y,1])/y; ysoln:=Evaluate(ysoln,[1,y,1])*y; // Other things really happen above, but denominator becomes 1 ysoln; Type(ysoln); // I would like to just do this Roots(ysoln); // but Magma refuses... // I know the Roots function works if set-up properly: R&lt;y&gt;:=PolynomialRing(Rationals()); fy:=y^3-8; Roots(fy); </code></pre> http://mathoverflow.net/questions/87410/specific-elliptic-curves-rank Specific Elliptic Curves: Rank bobuhito 2012-02-03T08:48:12Z 2012-03-22T06:02:37Z <p>Here's a challenge for elliptic curve descenders/programmers. It seems no public software or public tables can determine if the rank is zero for the following curves (over rational x,y):</p> <pre><code> y^2 = x^3 - 9122*x + 106889 y^2 = x^3 - x^2 - 42144*x + 66420 y^2 = x^3 - x^2 - 168615*x + 21827700 y^2 = x^3 - 210386*x + 32627329 </code></pre> <p>Can anybody definitely say if any of their ranks are zero?</p> <p>By the way, these arose from Heronian triangles for a given base and height, so there are equivalent quartic forms which might be easier to analyze...for example, the rank of the first curve above is zero iff there are no rational s,t solutions to this equation:</p> <pre><code> ( s^2 - t^2 )^2 = 25*( 2*( s^2 + t^2 ) - 509 ) </code></pre> <p>Also, I have tried both Magma and Sage. Sage seems to be better at determining the rank in about 20% of similar cases. For example, "y^2 = x^3 + x^2 - 58055*x + 4135350" has rank 0 according to Sage, but Magma only bounds the rank from 0 to 2 (limited to one minute). Anyway, these 4 cases are unsolved.</p> http://mathoverflow.net/questions/88683/inertia-gravity-in-distance-geometry Inertia/Gravity in Distance Geometry bobuhito 2012-02-17T03:24:22Z 2012-02-17T08:55:20Z <p>The Cayley-Menger Determinant, D(N), slickly calculates the N-dimensional simplex volume of any N+1 points. One constraint in our 3D world is that D(4)=0.</p> <p>Give each point a mass (Mi) and dynamic interdistances (i.e., Rij(t) are functions of "time") according to inertia and non-relativistic "Newtonian gravity". Is there a simple mathematical way to express the resulting dynamic constraints in these terms?</p> <p>I'm basically wondering if these interdistances are somehow superior to normal coordinates in multi-body problems, but gravity doesn't appear to fit nicely...sorry for the vague question!</p> <p><a href="http://mathworld.wolfram.com/Cayley-MengerDeterminant.html" rel="nofollow">http://mathworld.wolfram.com/Cayley-MengerDeterminant.html</a></p> http://mathoverflow.net/questions/86182/impossible-heronian-triangles-ratio-of-2-sides Impossible Heronian Triangles (Ratio of 2 Sides) bobuhito 2012-01-20T08:08:34Z 2012-01-27T13:56:33Z <p>There is no Heronian triangle (or simply consider triangles on an integer lattice which also have integer side lengths) for which one side is half the length of another side. What other "side-side ratios" are impossible?</p> <p>Here are the impossible ratios I've come across in researching this: 1/2, 2/5, 2/3, 62/63, 6/7</p> <p>There seem to be infinitely more from the generation method given by Fine in his "On Rational Triangles" paper. But, I would like a general check for any given ratio. For example, I've used Matlab to evaluate this ratio for millions of triangles and never seen the ratios 1/3, 1/4, or 1/5; so, does anybody know if these are truly impossible?</p> <p>I have a hunch that these impossible ratios have a neat pattern...so please help! Thanks!</p> <p>ADDED 1/27/2012: From the answers of Alan and Jamie, I've learned that most ratios can quickly be checked with Sage (using descents in elliptic curves): <a href="https://picasaweb.google.com/107800252627134603876/Math#5702303639089321090" rel="nofollow">https://picasaweb.google.com/107800252627134603876/Math#5702303639089321090</a> From the plotted summary, you can see that all the ratios I mentioned truly are impossible. I'm guessing that the few uncheckable ratios in the plot could be checked with some new creative descent method if that were one's lifetime goal... it even sounds like Magma already has the capability to clarify some of these points.</p> http://mathoverflow.net/questions/132379/will-discrete-log-problem-be-solved Comment by bobuhito bobuhito 2013-05-31T17:23:48Z 2013-05-31T17:23:48Z I didn't think this would get closed if I used Community Wiki, but I guess there is no good place for challenges like this. For the record, there is a solution because I did raise the power myself. Since my mod has only 75 digits (and perhaps simple to work with because it is a &quot;weak prime&quot;), I guess this should be a piece of cake for Joux or Kleinjung to do alone in an hour...if anybody finds the answer, please comment. Anyway, it seems our current technology barely saves the human race for 170 digits, so I wish I had posed the question originally with 200-digit numbers. http://mathoverflow.net/questions/128882/fastest-digit-extraction-for-any-irrational-number/128898#128898 Comment by bobuhito bobuhito 2013-05-26T14:28:58Z 2013-05-26T14:28:58Z For those that upvoted this, it's clearly ruled out in my question (I know it makes my question a little artificial, but this Liousville construction is even more artificial). http://mathoverflow.net/questions/130413/non-constant-sum-blotto-game-for-only-2-players-and-2-battlefields/130451#130451 Comment by bobuhito bobuhito 2013-05-13T20:01:49Z 2013-05-13T20:01:49Z Yep, sorry, first time I've seen that notation. I'll mark your$m/\lfloor B/(B-E)\rfloor \$ as the answer in a moment. By the way, is there a generalization of this formula to more than 2 players and/or more than 2 battlefields? I’m just looking for the value/utility formula, not a full strategy like you graciously gave here. http://mathoverflow.net/questions/130413/non-constant-sum-blotto-game-for-only-2-players-and-2-battlefields/130451#130451 Comment by bobuhito bobuhito 2013-05-13T16:05:13Z 2013-05-13T16:05:13Z Thanks. I'm trying to follow this, but you have some mistakes throwing me off. Please take a look at your definition of r and your example's calculation of m (I get m=8/3). http://mathoverflow.net/questions/130413/non-constant-sum-blotto-game-for-only-2-players-and-2-battlefields Comment by bobuhito bobuhito 2013-05-12T23:51:46Z 2013-05-12T23:51:46Z Maybe I shouldn't have used the words &quot;non-constant-sum&quot;. All I mean is that the two players start with a non-equal number of total soldiers and use them all (&quot;use it or lose it&quot;) on the two battlefields. So, utility is the number of battlefields won (you can say ties are split half-half, so technically the possible utility outcomes are 0, 0.5, 1.0, 1.5, or 2.0, but tie treatment is not statistically important if there are many soldiers). http://mathoverflow.net/questions/128282/calculate-the-inverse-of-a-matrix Comment by bobuhito bobuhito 2013-04-21T21:00:23Z 2013-04-21T21:00:23Z If A is a simple scalar matrix (1x1) of 1, this equation will not have a stable equilibrium, so I would say no http://mathoverflow.net/questions/128212/special-primes-with-p4p1 Comment by bobuhito bobuhito 2013-04-21T13:07:18Z 2013-04-21T13:07:18Z Just knowing that, it becomes easier to search the web. I found that this sequence is documented at <a href="http://oeis.org/A023212" rel="nofollow">oeis.org/A023212</a> and, from the graphs, guess that about 1 in 14 prime numbers might meet this requirement in the infinite limit. But, if primes were truly random, the prime number theorem makes me think that this ratio should go to zero. I'm leaning towards it going to zero. http://mathoverflow.net/questions/127228/box-nodes-in-directed-graphs-with-paired-io-symmetry Comment by bobuhito bobuhito 2013-04-13T12:59:48Z 2013-04-13T12:59:48Z Yes, but marking 2*n independent vertices is probably required (as in the left example above) since I really wanted to mark the lines from the vertices. There are really n labels for permutation because of my pairing. The automorphism then needs to induce the same pairs. If you're curious, this is a practical application for building a network with many inter-communicating IOs from small primitive routers. http://mathoverflow.net/questions/127228/box-nodes-in-directed-graphs-with-paired-io-symmetry Comment by bobuhito bobuhito 2013-04-12T23:14:34Z 2013-04-12T23:14:34Z Each node has two lines with arrows indicating inward flow and two lines with arrows indicating outward flow; these are the two inputs and two outputs (this should be natural to people familiar with directed graphs). To draw this fast, I didn't show arrows on some lines, but please consider all lines to have a flow arrow. Both of my examples have 3 inputs and 3 outputs which are unconnected which can be itemized in pairs by writing in1, out1, in2, out2, in3, out3. Box is more like &quot;black box&quot; where this whole construction is like a node with many inputs and outputs. http://mathoverflow.net/questions/109264/optimum-tournament-strategy/109286#109286 Comment by bobuhito bobuhito 2012-10-11T00:13:34Z 2012-10-11T00:13:34Z Great proof! I now see that this is different from &quot;flipping coins on a budget&quot; because the win probability is less sensitive to spent energy (and I now think my question would have been more dynamic if the win probability were proportional to the square of the spent energy, instead of the linear energy, which might be more realistic in more-skilled competitions like track sprinting, instead of baseball). Would you guess N&gt;2 also has a boring evenly-distributed solution? http://mathoverflow.net/questions/107390/flipping-coins-on-a-budget Comment by bobuhito bobuhito 2012-10-10T00:59:42Z 2012-10-10T00:59:42Z Thanks again. For the symmetric problem, I started a new question: <a href="http://mathoverflow.net/questions/109264/optimum-tournament-strategy" rel="nofollow" title="optimum tournament strategy">mathoverflow.net/questions/109264/&hellip;</a> http://mathoverflow.net/questions/107390/flipping-coins-on-a-budget Comment by bobuhito bobuhito 2012-09-26T23:22:21Z 2012-09-26T23:22:21Z @Granger Thanks. To generalize for any n (and b=n/2), it seems that the manager budgets 0.5 on every flip until he leads, and then he clinches by budgeting ones. Since the probability of eventually leading goes to 1 for big n, my insight was totally wrong. The surprising skill of the manager here is in &quot;piling on after he gets ahead&quot;...he almost always wins the tournament...I wonder if this can really apply to baseball. http://mathoverflow.net/questions/107390/flipping-coins-on-a-budget Comment by bobuhito bobuhito 2012-09-26T17:45:42Z 2012-09-26T17:45:42Z I'm curious about the World Series example where both teams are equal (n=7, k=4, b=3.5). My instinct tells me that there is a 50% chance of winning no matter how I budget things (provided only that I don't waste any of the budget). Right? http://mathoverflow.net/questions/106705/2d-problems-which-are-easier-to-solve-in-3d/106707#106707 Comment by bobuhito bobuhito 2012-09-09T15:58:03Z 2012-09-09T15:58:03Z I'd say level set methods are not really adding a dimension; they trade a parameter for an extra &quot;spatial&quot; dimension. I admit, though, that I'm not very familiar with them and my goal is not so clear from my question. http://mathoverflow.net/questions/106163/inter-kissing-number-for-non-spheres/106168#106168 Comment by bobuhito bobuhito 2012-09-03T05:09:23Z 2012-09-03T05:09:23Z @Ilya, what do you mean by translates? It would help if you fully specified an example shape...