4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It seems to me like the question in the postscript asks for the probability that every element of $\mathbb{Z}/ N \mathbb{Z}$ can be written as a sum of some elements of $A$, whereas the original question asks for the probability that a particular element in $\mathbb{Z}/ N \mathbb{Z}$ can be written as a sum of some elements of $A$; which question are you really interested in? $\endgroup$ – JBL Apr 5 '11 at 0:16
  • $\begingroup$ I'd actually be interested in both, although I suppose the latter is more relevant to what I'd be using this for. But thanks for pointing out the difference! $\endgroup$ – Jenn Apr 5 '11 at 0:30
  • $\begingroup$ Re: PS. $\mathbb{Z}/N$ is never a $\mathbb{Z}/2$-module, unless $N=2$, at least in the standard definition. $\endgroup$ – Felipe Voloch Apr 5 '11 at 0:32
  • $\begingroup$ This is very similar to the phase transition for the Number Partition Problem. See Gent and Walsh's paper (citeseerx.ist.psu.edu/viewdoc/…) or Brian Hayes's article (arxiv.org/pdf/cond-mat/0310317) for an introduction. Borgs, Chayes and Pittel (citeseerx.ist.psu.edu/viewdoc/…) give a thorough analysis of what the parameterization looks like and how many solutions you can expect. Perhaps you can use their results and analysis for this problem. $\endgroup$ – dorkusmonkey Apr 5 '11 at 7:39
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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]}$

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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