probability that a random element of Z/NZ can be written as a subset sum of others

Question

How could one calculate the probability that any element in $\mathbb{Z}/N\mathbb{Z}$ can be written as a subset sum of $n$ random elements in $\mathbb{Z}/N\mathbb{Z}$?

In other words, say I pick $n$ random elements $x_1,\ldots,x_n$ for $n << N$ (for example, if $N = 2^k$ then $n=k$). Then for a random element $r\in{\mathbb{Z}/N\mathbb{Z}}$, what is the probability that $r$ can be written as $\sum_i b_ix_i$, where the $b_i$ values are restricted to be either $0$ or $1$?

In theory, I expect the probability for the case of $n=k$ and $N=2^k$ to be close to $1$, since if $n=k$ there are $2^k$ choices for the sum, so if $N=2^k$ we could expect this to hit every element. The obvious problem is that there might be some collisions (for example, $x_1 = x_2 + x_5 + x_8$), and I'm running into trouble bounding the probability of these collisions (which again should be low if the $x_i$ are picked truly at random); it may be totally easy but I'm not seeing it. It would also be nice to have a more general formula for any choice of $N$ and $n$.

Anyway, any help would be great. Thanks!

P.S. I suppose one other way of thinking about this is asking, for a random subset $A\subset \mathbb{Z}/N\mathbb{Z}$ such that $|A| = n$, what is the probability that $\mathbb{Z}/N\mathbb{Z}$ can be thought of as a $\mathbb{Z}/2\mathbb{Z}$-module free on $A$. Not sure if this will make more or less sense (it seems overly complicated at least to me), but it should be the same thing.

Answer 1

Use the second moment method. Let $\bar{b}=(b_1,\ldots,b_n)$ be a coefficients vector like in your question. Let $I_{\bar{b}}$ be the indicator of the event $r=<\bar{b},x>$. Then its easy to see that $\mathbb{E}(I_{\bar{b}})=1/N$. Its also pretty easy to check that $\mathbb{E}(I_{\bar{b}}I_{\bar{b'}})=1/N$ for distinct $\bar{b}$ and $\bar{b'}$. In other words, they are pairwise independent.

Let $X=\sum_{\bar{b}\in\{0,1\}^n} I_{\bar{b}}$. Then $\mathbb{E}(X)=2^n/N$ and $Var(X)=2^n(N-1)/N^2$ and using Chebyshev's inequality gives you that $\mathbb{P}(X=0)$ is small when $2^n \gg N$.

Gideon Amir and I use a similar method in this paper.

When $2^n \approx N$ I believe the probability does not go to 1, but I don't have the time right now to think about this.

Answer 2

later For $k=1,2,3,4,5$ the number of ways to get all $2^k$ elements is $2^{\binom{k}{2}}.$ Here is the reason that you can get at least that many for any $k:$ To get a set which generates (in our sense) $\mathbb{Z}/2^{k+1}\mathbb{Z},$ start with a set which generates $\mathbb{Z}/2^{k}\mathbb{Z},$ double all the members, and add one new odd member. It might not be hard to prove that nothing else works, but I haven't done so.

It would also appear that, for $k>1$, the number of ways to get all but one element is just $2^{2k-3}.$ I haven't explained that.

---

Here is some small data: Let $N=2^k$ and consider the $\binom{2^k-1}{k}$ ways to choose a set $S$ of $k$ distinct non-zero members of $\mathbb{Z}/N\mathbb{Z}.$ For each such choice find the number of distinct values among the $2^k$ sums ($\mod N$) of a subset of the members of $S$.

For $k=2,$ the choice $\lbrace 1,3 \rbrace$ gives the sums $0,1,3,0.$ However the choices $\lbrace 1,2 \rbrace$ and $\lbrace 2,3 \rbrace$ give the sums $0,1,2,3$. This is sumarised by the list $[3, 1], [4, 2].$ Similarly,

for $k=3$: $[4, 1], [5, 4], [6, 14], [7, 8], [8, 8]$

for $k=4$: $[7, 6], [8, 67], [9, 44], [10, 224], [11, 128], [12, 432], [13, 160], [14, 208], [15, 32], [16, 64]$

and for $k=5$: $\small{[8, 21], [10, 30], [11, 48], [12, 348], [13, 288], [14, 1568], [15, 1124], [16, 7540], [17, 2624]}$ $\small{ [18, 8960], [19, 5408],20, 23840], [21, 6880], [22, 24448], [23, 11808], [24, 31840], [25, 8576], [26, 17536] }$ $\small{[27, 4416], [28, 9024], [29, 1152], [30, 1280], [31, 128], [32, 1024]}$

Answer 3

If you pick $n$ elements at random, then you get $2^n$ subset sums, unless there is a collision, just as you said. There are $N^n/n! + O(N^{n-1})$ choices for your $x_1,\ldots,x_n$ if you ignore permutations. There are $O(2^{2n})$ possible ways of getting a collision and, for each kind of collision $O(N^{n-1})$ possible $x_1,\ldots,x_n$, since one of them is determined by the others. So, your probability is at most $2^n/N$ and at least $2^n/N(1+O(2^{2n}n!/N)$. This estimate is not so good when $n$ is about $\log N$ (as in your example) but is good for smaller $n$. You can probably refine my estimates.