Let $\mathbb{F}_q$ be a finite field with characteristic $p$ and $p < q$ (i.e. not a prime field). Let $D\subseteq \mathbb{F}_q$ be a some set with $|D|=n$. Find a non-empty subset $\{x_1,\dots,x_k\} \subseteq D$ such that $x_1+\cdots+x_k=s$ for some given $s\in\mathbb{F}_q$. This is the definition of the subset sum problem.

What I cannot understand is how do you count the number of solutions for a given $s$. In this paper, in page 2 it says

heuristically should be approximately $\frac{1}{q}\binom{n}{k}$.

A more concrete questions is, given $s$ how many summands does it have given that we select $D$ randomly from $\mathbb{F}_q$?

  • $\begingroup$ What do you mean, "how many summands does it have"? Do you mean, what is the value of $k$? But if there are many solutions, presumably there will be different values of $k$. $\endgroup$ – Gerry Myerson Jul 21 '10 at 10:32
  • $\begingroup$ What I mean is how many summations with $k$ terms equals $s$? So $k$ is fixed, and clearly $k < n$. $\endgroup$ – Marcos Villagra Jul 21 '10 at 11:05
  • $\begingroup$ @Marcos, OK, so when you wrote, "A more concrete question is," you meant, "Another way of asking the same question is," and when you used the word, "summands," that's not really what you meant. $\endgroup$ – Gerry Myerson Jul 22 '10 at 0:47

There are $\binom{n}{k}$ ways to choose $k$ elements from $n$ elements. If we consider their sum it is "expected" to be equal to every element of the field with the same probability. Hence we get $\frac{1}{q}\binom{n}{k}$ for the number of solutions of $x_1 + x_2 + \cdots + x_k = s$. This is the first part of your question.

Now there are $\binom{q}{k}$ ways to choose $k$ different elements of the field. And $\frac{1}{q}$ of them have sum equal to $s$. In other words number of solutions of $x_1 + x_2 + \cdots + x_k = s$ is equal to $\frac{1}{q}\binom{q}{k}$.

If we choose random $D$ with $|D|=n$ every solution will have all $x_i \in D$ with the same probability $p$:

$$p = \frac{\binom{q-k}{n-k}}{\binom{q}{n}}$$

Hence the expected number of solutions is equal to $\frac{1}{q}\binom{q}{k} \cdot p$ which is equal to $\frac{1}{q}\binom{n}{k}$.

So the expected number of solutions is equal to $\frac{1}{q}\binom{n}{k}$.

| cite | improve this answer | |
  • 1
    $\begingroup$ I think that, for the sake of hasty readers, you should put more "approximately" and "heuristically" throughout your post, or require $q$ to be coprime to $k$ for your equalities to hold exactly. $\endgroup$ – darij grinberg Jul 21 '10 at 10:10
  • $\begingroup$ I think that I don't use the assumption that q is comprime to k. $\endgroup$ – falagar Jul 21 '10 at 10:45
  • 1
    $\begingroup$ Falagar: $q = 4$, $k = 2$, $\frac{1}{q} \binom{q}{k} \not\in \mathbb{N}$. $\endgroup$ – JBL Jul 21 '10 at 11:57
  • $\begingroup$ that number is not necessarily a natural, because it is a ratio like approximate number of solutions per random $D$. Maybe you can take the floor or ceiling of that. $\endgroup$ – Marcos Villagra Jul 21 '10 at 22:28

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.