User granger - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T04:44:42Z http://mathoverflow.net/feeds/user/15056 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/130071/asymptotics-of-a-function Asymptotics of a function Granger 2013-05-08T11:17:36Z 2013-05-09T19:07:10Z <p>I hope this question is not too simple, but I would like to know the asymptotic behaviour of the following function $f: \mathbb{N}^{+} \rightarrow \mathbb{Q}$ where $$f(n) = \sum_{i=1}^{n} \frac{i^n}{n^{4i}}$$ Any references, pointers, or answers would be most appreciated.</p> http://mathoverflow.net/questions/108599/expected-number-of-shared-1s-between-two-binary-strings-from-a-given-set/108657#108657 Answer by Granger for expected number of shared 1s between two binary strings from a given set Granger 2012-10-02T18:42:20Z 2012-10-02T18:42:20Z <p>Assuming I've understood the question correctly, this depends entirely on the distribution of 1's amongst the missing $K$ strings. </p> <p>In particular, let $M = \{m_1,\ldots,m_K\}$ be the missing strings, and for $i \in \{0,\ldots,N-1\}$ let $k_i = \#\{ m \in M \mid m[i] = 1\}$, where $m[i]$ is the $i$-th bit of $m$.</p> <p>Then the probability that two randomly chosen bitstrings from the remaining $2^N - K$ both have their $i$-th bit equal to $1$ is $\binom{2^{N-1} - k_i}{2}/ \binom{2^N - K}{2}$, and since these events are independent, the expected number of indices which are both 1 is $$\sum_{i=0}^{N-1} \binom{2^{N-1} - k_i}{2}/ \binom{2^N - K}{2}.$$ </p> http://mathoverflow.net/questions/107390/flipping-coins-on-a-budget/108127#108127 Answer by Granger for Flipping coins on a budget Granger 2012-09-26T01:10:20Z 2012-09-27T14:55:14Z <p>This problem is ripe for a recursive approach. The method below allows one to compute the maximum probability of winning over all strategies for any $n,k$ recursively, as a function of $b$. These solutions are thus all optimal.</p> <p>However, the maximum winning-probability function varies over the interval $0 \le b &lt; k$, and given the example computations below, it seems that a general formula may not be so easy to find.</p> <p>Let $S_{n,k}(b)$ be the maximum probability of winning the game for the given inputs. Assume $S_{n',k'}(b)$ is known for all $n' &lt; n$ and $k' \le k$. Since at any stage there is only one choice to be made - namely how much of the budget $b$ to assign to $p$, the probability of obtaining a head - all possible strategies are parameterised by $0 \le p \le \text{min}(1,b)$. Hence by the inductive assumption we have the following recurrence relation: </p> <p>$$S_{n,k}(b) = \text{max}_{0 \le p \le \text{min}(1,b)} \ \{p \cdot S_{n-1,k-1}(b-p) + (1-p) \cdot S_{n-1,k}(b-p) \},$$</p> <p>since a head (occurring with probability $p$) decrements both $n$ and $k$, while a tail decrements $n$ only.</p> <p>We define $S_{n,k}(b) = 0$ if $n &lt; k$ and $S_{n,0}(b) = 1$ for $n \ge 1$ and any $b$. Using the recurrence and these base cases it is easy to obtain $S_{n,1}(b) = \text{min}(1,b)$ for $n \ge 1$. It is also easy to show that $S_{2,2}(b) = \text{min}(1,b^2/4)$, setting $p=b/2$ for each toss.</p> <p>The first non-trivial case is $$S_{3,2}(b) = \begin{cases} \frac{b^2}{3} - \frac{b^3}{27} &amp; \text{if} \ 0 \le b \le 3/2 &amp; (\text{set} \ p = b/3)\ \newline \frac{3b-2}{4} &amp; \text{if} \ 3/2 \le b \le 2 &amp; (\text{set} \ p = b-1)\ \newline 1 &amp; \text{if} \ b \ge 2, \end{cases}$$ which is obtained by substitution and differentiating w.r.t. $p$.</p> <p>$S_{3,3}(b) = \text{min}(1,b^3/27)$, by setting $p = b/3$, while the next interesting case is $$S_{4,2}(b) = \begin{cases} \frac{b^4}{256} - \frac{b^3}{16} + \frac{3b^2}{8}&amp; \text{if} \ 0 \le b \le 4/3 &amp; (\text{set} \ p = b/4)\ \newline \frac{19b-11}{27} &amp; \text{if} \ 4/3 \le b \le 2 &amp; (\text{set} \ p = b-1)\ \newline 1 &amp; \text{if} \ b \ge 2. \end{cases}$$</p> <p>It should be possible to prove a (recursive) formula for $S_{n,2}(b)$ based on the above. However, for $k=3$, $n \ge 4$ this may be somewhat harder. In particular for $0 \le b \le 2$ we have $S_{4,3}(b) = b^3/16 - b^4/128$, setting $p = b/4$. </p> <p>For $2 \le b \le \alpha \approx 2.84$ we have $S_{4,3}(b) = r(b) \cdot \frac{3(b-r(b))-2}{4} + (1-r(b))\cdot\frac{(b-r(b))^3}{27}$, where $r(b)$ is the root in $[0,1]$ satisfying $$16r^3 - (36b+12)r^2 +(24b^2 +24b - 162)r -4b^3 -12b^2 + 81b -54 = 0,$$ and $p = r(b)$. For $\alpha \le b \le 3$, setting $p = b-2$ is optimal and gives $S_{4,3}(b) = 19b/27 - 10/9$.</p> <p>It would seem that for larger $k$ (and $n$) these computations become increasingly cumbersome (or interesting, depending on one's perspective).</p> <hr> <p><strong>EDIT:</strong> In contrast to the difficulty of finding an analytic solution, one can alternatively solve for $S_{n,k}(b)$ numerically, by subdividing the relevant $p$-intervals to any desired precision and maximising over $p$. </p> <p>For example, dividing the intervals by $1000$, we find that for the world series example with $n=7$, $k=4$ and assuming a budget of $3.5$, we have $S_{7,4}(3.5) \approx 0.72826$, obtained by setting $p_1 \approx 0.619$ etc. and following the precomputed decision tree. Since the entire decision tree has to be optimised from the leaves to the root prior to the first decision being made, the $p_i$'s are not really chosen dynamically/reactively at all.</p> http://mathoverflow.net/questions/58732/torus-based-cryptography/91726#91726 Answer by Granger for Torus based cryptography Granger 2012-03-20T15:10:24Z 2012-03-20T15:10:24Z <p>Can I refer you to my paper On the Discrete Logarithm Problem on Algebraic Tori', Advances in Cryptology – CRYPTO 2005, Lecture Notes in Computer Science, 2005, Volume 3621/2005, 66-85, in which myself and Frederik Vercauteren studied this very problem.</p> <p>In particular, we showed that the compression mechanism afforded by the birationality of some algebraic tori may be exploited to obtain a faster discrete logarithm algorithm for some cryptographically practical field sizes. In these instances, attacking the discrete logarithm in $\mathbb{F}_{p^n}^{\times}$ via its decomposition </p> <p>$\prod_{d \mid n} T_d(\mathbb{F}_p)$ is faster than using L[1/3] index calculus techniques.</p> <p>Since then, other work has improved the L[1/3] index calculus techniques. However, our work demonstrates that it is naive to argue that the DLP in algebraic tori must be hard purely because the DLP in the multiplicative group of the extension field is hard, precisely because an attack on the former provides an attack on the latter.</p> http://mathoverflow.net/questions/67308/reference-requested-for-lim-n-rightarrow-infty-frac-sum-i1n-bars Reference requested for $\lim_{n \rightarrow \infty} \frac{\sum_{i=1}^{n} \bar{s}(i)}{n^2} = \frac{\pi^2}{30}$ Granger 2011-06-08T20:35:29Z 2012-02-22T03:30:33Z <p>While analysing the average runtime of an algorithm, I came across the following identity, and would like to know if anybody knows of any references for it? </p> <p>For $i \in \mathbb{N}$, let $\bar{s}(i)$ denote the square-free part of $i$, eg., $\bar{s}(12) = 3$ (and $\bar{s}(1)=1$). Then $$\lim_{n \rightarrow \infty} \frac{\sum_{i=1}^{n} \bar{s}(i)}{n^2} = \frac{\pi^2}{30}.$$</p> <p>Many thanks.</p> http://mathoverflow.net/questions/15444/the-phenomena-of-eventual-counterexamples/65518#65518 Answer by Granger for The phenomena of eventual counterexamples Granger 2011-05-20T10:19:13Z 2011-05-20T10:19:13Z <p>Robert Baillie has a paper on arxiv today (http://arxiv.org/abs/1105.3943) which shows how in principle one can construct examples of formulae which hold for $N=0,1,2,\ldots,k$, for arbirtrarily large $k$, then fail for all larger $N$. </p> <p>His largest example holds with $k\approx \exp(\exp(\exp(\exp(\exp(\exp(e))))))$.</p> http://mathoverflow.net/questions/64817/identifying-the-generating-function-ga-z-sum-n0-infty-an-zn1n Identifying the generating function $G(a,z) = \sum_{n=0}^{\infty} a^n z^{(n+1)(n+2)/2}.$ Granger 2011-05-12T17:15:35Z 2011-05-13T12:23:22Z <p>I have computed a generating function for a problem involving a particular series, and would like to know if anyone has any references or a categorisation for it? It's $$G(a,z) = \sum_{n=0}^{\infty} a^n z^{(n+1)(n+2)/2}.$$ It appears to be related to (mock) theta functions, but seems to be simpler. In particular, I would like to know whether $G(a,z)$ satisfies any identities?</p> <p>Many thanks.</p> http://mathoverflow.net/questions/130071/asymptotics-of-a-function/130145#130145 Comment by Granger Granger 2013-05-09T11:09:29Z 2013-05-09T11:09:29Z Thanks everyone :) http://mathoverflow.net/questions/130071/asymptotics-of-a-function/130086#130086 Comment by Granger Granger 2013-05-08T15:55:24Z 2013-05-08T15:55:24Z @Michael: I think your observation will do nicely (having bounded the contribution of the tail $x &gt; n$). Thanks! http://mathoverflow.net/questions/130071/asymptotics-of-a-function Comment by Granger Granger 2013-05-08T15:54:05Z 2013-05-08T15:54:05Z It popped up in the analysis of an algorithm. According to Maple the corresponding integral can be expressed in terms of a Whittaker function. http://mathoverflow.net/questions/130071/asymptotics-of-a-function Comment by Granger Granger 2013-05-08T12:38:49Z 2013-05-08T12:38:49Z Thanks Didier - that certainly agrees with the data. Would you mind briefly sketching your reasoning? http://mathoverflow.net/questions/22624/example-of-a-good-zero-knowledge-proof/22628#22628 Comment by Granger Granger 2012-12-05T23:50:08Z 2012-12-05T23:50:08Z @Tony: well for a non-zero-knowledge proof, you can label each ball according to its colour and give both to your friend, who conceals them and then randomly shows you either ball (so that you can't read the label), and you tell him what label it must have. Repeat. This will convince him that they are different, as before, but also that you know which one is labelled green. However you can't ever convince him that a ball is green as you could simply say the red one is, so he only learns if he believes you. http://mathoverflow.net/questions/109264/optimum-tournament-strategy/109286#109286 Comment by Granger Granger 2012-10-11T00:46:34Z 2012-10-11T00:46:34Z This would seem to show that distributing energy evenly is a Nash equilibrium. But if your opponent does not play evenly, how do you see that this is still the best strategy? http://mathoverflow.net/questions/107390/flipping-coins-on-a-budget Comment by Granger Granger 2012-09-27T14:22:03Z 2012-09-27T14:22:03Z @bobuhito For n=7, k=4 and b=3.5, using the recursion in my answer and maximising over p=i*min(1,b)/1000, for i=0..1000 at each stage, the (approximately) optimal strategy entails setting p_1 = 0.619, not 1/2. If the result is H, then set p_2=0.881, otherwise set p2=0.509, and so on. Using this numerical approach S_{7,4}(3.5) \approx 0.72826. In general I don't think any heuristics will help, since one needs to maximise all the intermediate functions prior to the first decision. In this respect the p_i's are not dynamically chosen; the entire game tree must precomputed from leaves to the root. http://mathoverflow.net/questions/107390/flipping-coins-on-a-budget Comment by Granger Granger 2012-09-26T18:49:52Z 2012-09-26T18:49:52Z @bobuhito Your instinct isn't correct. For example, for n=3, k=2, b =1.5, the optimal strategy gives you a 5/8 chance of winning (see my answer below). The game isn't symmetric because only one side is able to bias the outcome. http://mathoverflow.net/questions/35468/widely-accepted-mathematical-results-that-were-later-shown-wrong/35686#35686 Comment by Granger Granger 2012-08-23T11:52:14Z 2012-08-23T11:52:14Z I believe the error was from the 528th decimal and onwards to the 707th, allowing of course for possible accidentally' correct digits, so it's doubtful that a drool stain could have caused this. http://mathoverflow.net/questions/58732/torus-based-cryptography/58792#58792 Comment by Granger Granger 2012-03-20T15:36:25Z 2012-03-20T15:36:25Z This is not entirely correct, since native DLP algorithms for algebraic tori are now known; see my answer below. http://mathoverflow.net/questions/67308/reference-requested-for-lim-n-rightarrow-infty-frac-sum-i1n-bars/89158#89158 Comment by Granger Granger 2012-03-20T15:31:55Z 2012-03-20T15:31:55Z Thanks Gerry, this is just what I was looking for. http://mathoverflow.net/questions/67308/reference-requested-for-lim-n-rightarrow-infty-frac-sum-i1n-bars/67316#67316 Comment by Granger Granger 2011-06-13T16:50:57Z 2011-06-13T16:50:57Z @GH - I think it is standard etiquette (and saves space) to determine whether or not a result is already in print, before contributing a proof. Therefore whether a result has been considered before is important. I think you and Junkie misunderstood what I was asking. As it is, writing `this is a standard exercise' would have been a sufficient answer, so thank you. http://mathoverflow.net/questions/67308/reference-requested-for-lim-n-rightarrow-infty-frac-sum-i1n-bars/67316#67316 Comment by Granger Granger 2011-06-09T09:35:08Z 2011-06-09T09:35:08Z Thanks guys, but I was only asking if to anyones knowledge this had been considered before (hence reference request). It's sufficiently natural that I thought it must be classical? http://mathoverflow.net/questions/67133/letters-and-numbers-numbers-game Comment by Granger Granger 2011-06-07T14:18:03Z 2011-06-07T14:18:03Z Given 1,1,1,1,1,1, I don't think you can get higher than 9, so no. You can experiment here <a href="http://www.crosswordtools.com/numbers-game/" rel="nofollow">crosswordtools.com/numbers-game</a> http://mathoverflow.net/questions/67025/factoring-integers-using-complex-integrals Comment by Granger Granger 2011-06-06T15:25:28Z 2011-06-06T15:25:28Z Kamel Bentahar studied this very function in his masters thesis in 2004, and Daniel Brown has also thought along these lines (<a href="http://eprint.iacr.org/2008/149" rel="nofollow">eprint.iacr.org/2008/149</a>), but without success, concluding that the method is probably doomed to fail.