User granger - MathOverflow

Asymptotics of a function

2013-05-08T11:17:36Z

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.

Answer by Granger for expected number of shared 1s between two binary strings from a given set

2012-10-02T18:42:20Z

Assuming I've understood the question correctly, this depends entirely on the distribution of 1's amongst the missing $K$ strings.

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

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

Answer by Granger for Flipping coins on a budget

2012-09-26T01:10:20Z

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.

However, the maximum winning-probability function varies over the interval $0 \le b < k$, and given the example computations below, it seems that a general formula may not be so easy to find.

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

$$ 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) \}, $$

since a head (occurring with probability $p$) decrements both $n$ and $k$, while a tail decrements $n$ only.

We define $S_{n,k}(b) = 0$ if $n < 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.

The first non-trivial case is $$ S_{3,2}(b) = \begin{cases} \frac{b^2}{3} - \frac{b^3}{27} & \text{if} \ 0 \le b \le 3/2 & (\text{set} \ p = b/3)\ \newline \frac{3b-2}{4} & \text{if} \ 3/2 \le b \le 2 & (\text{set} \ p = b-1)\ \newline 1 & \text{if} \ b \ge 2, \end{cases} $$ which is obtained by substitution and differentiating w.r.t. $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}& \text{if} \ 0 \le b \le 4/3 & (\text{set} \ p = b/4)\ \newline \frac{19b-11}{27} & \text{if} \ 4/3 \le b \le 2 & (\text{set} \ p = b-1)\ \newline 1 & \text{if} \ b \ge 2. \end{cases} $$

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

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

It would seem that for larger $k$ (and $n$) these computations become increasingly cumbersome (or interesting, depending on one's perspective).

EDIT: 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$.

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.

Answer by Granger for Torus based cryptography

2012-03-20T15:10:24Z

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.

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

$\prod_{d \mid n} T_d(\mathbb{F}_p)$ is faster than using L[1/3] index calculus techniques.

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.

Reference requested for $\lim_{n \rightarrow \infty} \frac{\sum_{i=1}^{n} \bar{s}(i)}{n^2} = \frac{\pi^2}{30}$

2011-06-08T20:35:29Z

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?

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

Many thanks.

Answer by Granger for The phenomena of eventual counterexamples

2011-05-20T10:19:13Z

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

His largest example holds with $k\approx \exp(\exp(\exp(\exp(\exp(\exp(e))))))$.

Identifying the generating function $ G(a,z) = \sum_{n=0}^{\infty} a^n z^{(n+1)(n+2)/2}. $

2011-05-12T17:15:35Z

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?

Many thanks.

Comment by Granger

2013-05-09T11:09:29Z

Thanks everyone :)

Comment by Granger

2013-05-08T15:55:24Z

@Michael: I think your observation will do nicely (having bounded the contribution of the tail $x > n$). Thanks!

Comment by Granger

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.

Comment by Granger

2013-05-08T12:38:49Z

Thanks Didier - that certainly agrees with the data. Would you mind briefly sketching your reasoning?

Comment by Granger

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.

Comment by Granger

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?

Comment by Granger

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.

Comment by Granger

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.

Comment by Granger

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.

Comment by Granger

2012-03-20T15:36:25Z

This is not entirely correct, since native DLP algorithms for algebraic tori are now known; see my answer below.

Comment by Granger

2012-03-20T15:31:55Z

Thanks Gerry, this is just what I was looking for.

Comment by Granger

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.

Comment by Granger

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?

Comment by Granger

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 crosswordtools.com/numbers-game

Comment by Granger

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 (eprint.iacr.org/2008/149), but without success, concluding that the method is probably doomed to fail.