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.
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ How, precisely, is $A$ chosen at random? Is there any reason to think that the modulus being one less than a prime is important? $\endgroup$– Greg MartinApr 12, 2020 at 17:58
-
2$\begingroup$ @GregMartin: I'm really trying to determine the iterated product set modulo a prime, but this is equivalent, AFAIK. You can assume that the values in $A$ are evenly distributed. In essence, this is the question I came up with when trying to answer math.stackexchange.com/questions/3619521/… $\endgroup$– Matt GroffApr 12, 2020 at 18:03
-
1$\begingroup$ "the values in $A$ are evenly distributed" is not specific enough. Is the number of elements of $A$ fixed, or is the probability that each $n\in A$ fixed? Is $A$ chosen with respect to the prime $p$, or as a set of integers? $\endgroup$– Greg MartinApr 12, 2020 at 19:16
-
$\begingroup$ @GregMartin: Oh, sorry. The number of elements of $A$ is fixed. $A$ is chosen with respect to the prime $p$. Every element is chosen independently of all other elements. $\endgroup$– Matt GroffApr 12, 2020 at 19:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.