1
$\begingroup$

Let $p$ be a prime number and $[p-1]=\{1, 2, \ldots, p-1\}$.
The following proposition is proved: (but I cannot find out where)

Proposition: The non-empty subset sums of $[p-1]$ are equally distributed $\pmod{p}$.

In other words, if $N(a)$ denotes the number of non-empty subset sums which are $\equiv a\pmod{p}$ then $N(a)=\frac{2^{p-1}-1}{p}$, for every integer $0\le a\le p-1$.

I can prove it on my own in many ways, but I thought since this is already known, to put just a reference next to this result.

Can anybody give me some reference (paper or book) where I can find a proof of this proposition?

Improve this question
$\endgroup$
8
  • $\begingroup$ crossposted math.stackexchange.com/q/4543208/87355 $\endgroup$
    – Carlo Beenakker
    Commented Oct 18, 2022 at 10:51
  • $\begingroup$ @CarloBeenakker Yes, but before 16 days with no response. I hope this is ok. $\endgroup$
    – Konstantinos Gaitanas
    Commented Oct 18, 2022 at 11:01
  • 2
    $\begingroup$ it's OK, but best practice is to disclose the crossposting on both ends; just to avoid any duplication of efforts. $\endgroup$
    – Carlo Beenakker
    Commented Oct 18, 2022 at 11:03
  • 1
    $\begingroup$ Let $g$ be a primitive root modulo $p$. If the elements of a subset $S$ add up to $a\ne0$, then the elements of $g^rS$ add up to $g^ra$. This runs through all the nonzero elements modulo $p$. $\endgroup$
    – Gerry Myerson
    Commented Oct 18, 2022 at 11:55
  • $\begingroup$ @GerryMyerson I said I know how to prove it. I just asked for a reference. If there is any. $\endgroup$
    – Konstantinos Gaitanas
    Commented Oct 18, 2022 at 12:39

0

Reset to default

You must log in to answer this question.