Showing that $\prod_i{\frac{qi-1}{qi}}=\exp(-\frac{\log n- \log q +O(1)}{q})$

31 Views Asked by At

I'm currently making my way through Dixon's paper 'The Probability of Generating the Symmetric Group'. (It can be found here.) In the proof of lemma 3 it is asserted that $$\prod_i{\frac{qi-1}{qi}}=\exp(-\frac{\log n- \log q +O(1)}{q})$$ where $i$ runs between $1$ and $\frac{n-q}{q}$, $q$ is a fixed prime, and $n$ is tending to infinity.

If anyone can help me to see why I'd be very grateful :)

I've noticed these points. Hopefully some are useful!:

  • I don't think that the fact that $q$ is prime is relevant.

  • the term $\log n- \log q=\log\frac{n}{q}=\log\frac{n-q}{q}+O(1)$. I would think that this comes from the upper bound in the product. So we can probably reduce to showing that for positive integers $d$ and $n$, where $d$ is fixed and $n$ tends to infinity, $$\prod_{i=1}^n(1-\frac{1}{id})=\exp(-\frac{\log n+O(1)}{d})$$

  • Viewing the left hand side as a polynomial in $\frac{1}{d}$, the coefficient of $\frac{1}{d}$ is $$-\frac{1}{d}\sum_{i=1}^n\frac{1}{i}$$ $\sum_{i=1}^n\frac{1}{i} = \log n +O(1)$ by the integral test. So viewing the right hand side as a power series in $\frac{1}{d}$, we see that the linear terms match.

  • On the left hand side, the coefficient of $\frac{1}{d}^k$ is $(-1)^k\sum\frac{1}{i_1\dots i_k}$ where the sum is over distinct integers $i_1,\dots, i_k$ between $1$ and $n$. It may be useful to note that this is $(-1)^k\frac{1}{k!}(\sum_{i=1}^n\frac{1}{i})^k=(-1)^k\frac{1}{k!}(\log n+O(1))^k$ minus some cross terms, but I think that getting terms like $O(\log n)$ is probably unhelpful.

Any help would be much appreciated!