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

Improve this question
$\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$
    – Gerry Myerson
    Commented 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$
    – Marcos Villagra
    Commented 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$
    – Gerry Myerson
    Commented Jul 22, 2010 at 0:47

1 Answer 1

Reset to default
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}$.

Improve this answer
$\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$
    – darij grinberg
    Commented Jul 21, 2010 at 10:10
  • $\begingroup$ I think that I don't use the assumption that q is comprime to k. $\endgroup$
    – falagar
    Commented 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
    Commented 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$
    – Marcos Villagra
    Commented Jul 21, 2010 at 22:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .