Steve Flammia
Reputation
1,273
Next privilege 2,000 Rep.
 Oct 26 awarded Yearling Aug 11 awarded Nice Answer Feb 26 awarded Nice Answer Oct 26 awarded Yearling Jul 2 awarded Curious May 14 awarded Nice Question Apr 7 awarded Popular Question Oct 26 awarded Yearling Aug 20 answered What are some deep theorems, and why are they considered deep? Jan 8 awarded Popular Question Oct 26 awarded Yearling Sep 17 awarded Notable Question Jun 6 revised Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix clarification. Jun 6 answered Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix May 28 awarded Notable Question May 27 accepted Generating a group by randomly sampling generators May 26 answered Generating a group by randomly sampling generators May 24 comment Generating a group by randomly sampling generators A similar linear upper bound is $2^n k$, which is tighter for small $k$. These are all fantastic, but do you think it might be possible to get a strictly concave lower bound? The linear ones are not quite strong enough for my purposes, unfortunately. May 24 comment Generating a group by randomly sampling generators Yes, of course. (I read "with" instead of "without".) In fact, $k \le 3^n$, the number of full elements in $G^n$. Then $N_{3^n} = 4^n \gg 3^n$. In that case, it seems the bound is rather loose, no? Plus one regardless! May 24 comment Generating a group by randomly sampling generators I lost you after the first line... $N_k \le |G|^n = 4^n$ for all k, so the bound your wrote can't always hold.