1
$\begingroup$

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$?

$\endgroup$
3
  • $\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$ Jul 21, 2010 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$ Jul 21, 2010 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$ Jul 22, 2010 at 0:47

1 Answer 1

5
$\begingroup$

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

$\endgroup$
4
  • 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$ Jul 21, 2010 at 10:10
  • $\begingroup$ I think that I don't use the assumption that q is comprime to k. $\endgroup$
    – falagar
    Jul 21, 2010 at 10:45
  • 1
    $\begingroup$ Falagar: $q = 4$, $k = 2$, $\frac{1}{q} \binom{q}{k} \not\in \mathbb{N}$. $\endgroup$
    – JBL
    Jul 21, 2010 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$ Jul 21, 2010 at 22:28

Your Answer

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

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