1
$\begingroup$

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.

$\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$ Apr 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 Groff
    Apr 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$ Apr 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 Groff
    Apr 12, 2020 at 19:49

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.