User bobuhito - MathOverflow

Fastest Digit Extraction for Any Irrational Number

2013-04-27T02:31:19Z

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).

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}$).

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.

Non-Constant-Sum Blotto Game for Only 2 Players and 2 Battlefields

2013-05-12T14:19:40Z

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?

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.

2D Problems Which are Easier to Solve in 3D

2012-09-09T03:12:40Z

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...

So, are any 2D problems easier to solve in even higher dimensions? I can't think of any.

special primes with p'=4p+1

2013-04-21T07:35:37Z

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?

"Box Nodes" in Directed Graphs with Paired IO Symmetry

2013-04-11T12:00:42Z

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.

Here are two graph examples to help show what I'm looking for:

Optimum Tournament Strategy

2012-10-10T00:58:28Z

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.

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.)

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)?

[this is a tangent from http://mathoverflow.net/questions/107390/flipping-coins-on-a-budget]

Inter-Kissing Number for Non-Spheres

2012-09-02T07:33:50Z

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.

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).

Inter-Kissing Number for Spheres of Different Sizes

2012-09-01T17:47:22Z

What is the maximum number of spheres that can be placed in 3D such that all inter-touch?

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.

[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.]

Non-linear Perturbation Operator Examples

2012-07-29T04:46:01Z

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).

Magma Coercion Syntax

2012-02-01T14:53:32Z

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!

PP<x,y,z>:=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<y>:=PolynomialRing(Rationals());
fy:=y^3-8;
Roots(fy);

Specific Elliptic Curves: Rank

2012-02-03T08:48:12Z

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):

 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

Can anybody definitely say if any of their ranks are zero?

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:

 ( s^2 - t^2 )^2   =   25*( 2*( s^2 + t^2 ) - 509 )

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.

Inertia/Gravity in Distance Geometry

2012-02-17T03:24:22Z

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.

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?

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!

http://mathworld.wolfram.com/Cayley-MengerDeterminant.html

Impossible Heronian Triangles (Ratio of 2 Sides)

2012-01-20T08:08:34Z

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?

Here are the impossible ratios I've come across in researching this: 1/2, 2/5, 2/3, 62/63, 6/7

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?

I have a hunch that these impossible ratios have a neat pattern...so please help! Thanks!

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): https://picasaweb.google.com/107800252627134603876/Math#5702303639089321090 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.

Comment by bobuhito

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 "weak prime"), 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.

Comment by bobuhito

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).

Comment by bobuhito

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.

Comment by bobuhito

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).

Comment by bobuhito

2013-05-12T23:51:46Z

Maybe I shouldn't have used the words "non-constant-sum". All I mean is that the two players start with a non-equal number of total soldiers and use them all ("use it or lose it") 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).

Comment by bobuhito

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

Comment by bobuhito

2013-04-21T13:07:18Z

Just knowing that, it becomes easier to search the web. I found that this sequence is documented at oeis.org/A023212 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.

Comment by bobuhito

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.

Comment by bobuhito

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 "black box" where this whole construction is like a node with many inputs and outputs.

Comment by bobuhito

2012-10-11T00:13:34Z

Great proof! I now see that this is different from "flipping coins on a budget" 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>2 also has a boring evenly-distributed solution?

Comment by bobuhito

2012-10-10T00:59:42Z

Thanks again. For the symmetric problem, I started a new question: mathoverflow.net/questions/109264/…

Comment by bobuhito

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 "piling on after he gets ahead"...he almost always wins the tournament...I wonder if this can really apply to baseball.

Comment by bobuhito

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?

Comment by bobuhito

2012-09-09T15:58:03Z

I'd say level set methods are not really adding a dimension; they trade a parameter for an extra "spatial" dimension. I admit, though, that I'm not very familiar with them and my goal is not so clear from my question.

Comment by bobuhito

2012-09-03T05:09:23Z

@Ilya, what do you mean by translates? It would help if you fully specified an example shape...