Average size of iterated sumset modulo $p-1$,

Question

Given a prime $p$, what is the average size of the iterated sumset, $|kA|$, modulo $p-1$, with $p$ a prime, and $k$ given, with $A$ chosen at random? You can pick any type of prime you like for $p$, but we must be able to get arbitrarily large $p$'s of this type. Note that the elements are chosen independently from the uniform distribution over $\mathbb{Z}_p$, and we assume that the size of $A$ is fixed.

Answer 1

There is some ambiguity about how $A$ is chosen at random so I will define $\Omega$ to be the set of

$$A\subseteq \mathbb{Z}/(p-1)\mathbb{Z} \ : \ |A|=K$$

where $K$ is some fixed integer and assume $A$ is chosen uniformly from $\Omega$. In this case the expected size of $kA$ is $$|kA|\sim \frac{|A|^k}{k!}.$$ We may be able to say a little more about the distribution. I'll sketch the ideas. For each $1\le z \le p-1$ let $X_z$ denote the random variable

$$X_z= 1 \quad \text{if} \quad z\in kA, \ \quad 0 \quad \text{otherwise}$$ so we want to calculate the expected value of $$X=X_1+\dots+X_{p-1}.$$ Using linearlity $$\mathbb{E}(X)=\mathbb{E}(X_1)+\dots+\mathbb{E}(X_{p-1}).$$ Fix some $1\le z \le p-1$ and consider $X_z$. We have $$X_z=1$$ if and only if there exists $a_1,\dots,a_k\in \mathbb{Z}/(p-1)\mathbb{Z}$ such that $$a_1+\dots+a_{k}=z,$$ Since the number of solutions to the above with $a_i=a_j$ for some $i\neq j$ is $O(p^{k-2})$, we may approximate $$\mathbb{E}(X_z)\sim \frac{1}{k!}\frac{1}{|\Omega|}\sum_{a_1,\dots,a_{k-1}\in \mathbb{Z}/(p-1)\mathbb{Z}}\sum_{\substack{A\in \Omega \newline a_1,\dots,a_{k-1},z-(a_1+\dots+a_{k-1})\in A}}1$$ where the $k!$ accounts for all possible rearrangements of $a_1,\dots,a_{k-1},z-(a_1+\dots+a_{k-})$. Simplifying \begin{align*} \mathbb{E}(X_z)&\sim \frac{1}{k!}\frac{1}{|\Omega|}\sum_{a_1,\dots,a_{k-1}\in \mathbb{Z}/(p-1)\mathbb{Z}}\binom{p-1-k}{K-k} \newline &\sim \frac{p^{k-1}}{k!}\frac{\binom{p-1-k}{K-k}}{\binom{p-1}{K}}, \end{align*} then simplifying some more \begin{align*} \mathbb{E}(X_z)\sim \frac{K^k}{k!(p-1)}. \end{align*} Summing over expectations $$\mathbb{E}(X)\sim \frac{K^k}{k!}.$$ Combined with the central limit theorem, the above argument suggests the size of $kA$ may have normal distribution.