counting different sums of KSubsets over the Unit Circle

[Max Alekseyev]

On 6/24/07, Max Alekseyev <maxale at gmail.com> wrote:
> On 6/23/07, wouter meeussen <wouter.meeussen at pandora.be> wrote:
> > take the familiar KSubsets of an integer n (say 5) in k parts (say 3):
> > {{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,
> > 4,5}}
> > now, place them on the unit circle as:
> >
> > {{{E^((2*I)/5*Pi), E^((4*I)/5*Pi), E^((-4*I)/5*Pi)},
> > {E^((2*I)/5*Pi), E^((4*I)/5*Pi), E^((-2*I)/5*Pi)}, ...
> >
> > and add each subset of k complex numbers.
> > Now, scan k from 1 to n, and check the count of *different* values you get
> > as function of n.
> > (Needless to say that the sum of sums adds to zero.)
> >
> > In 'linguae mathematicae', you get:
> > Table[r=Table[Apply[Plus,Map[E^(2*I*Pi#/n)&,KSubsets[Range at n,k],{2}],{1}],{k
> > ,n}];Length[Union at Flatten[r]],{n,17}]
> >
> > {1,3,7,9,31,48,127,144,511,768,2047,2304,8191,12288,32767,36864,131071}

Oh, you trusted Mathematica too much. The most of listed numerical
values are incorrect.

For example, for n=6 we have:

E^((2*I)/6*Pi) = 1/2 + I*sqrt(3)/2,
E^((2*I)/6*Pi*2) = -1/2 + I*sqrt(3)/2,
E^((2*I)/6*Pi*3) = -1,
E^((2*I)/6*Pi*4) = -1/2 - I*sqrt(3)/2,
E^((2*I)/6*Pi*5) = 1/2 - I*sqrt(3)/2,
E^((2*I)/6*Pi*6) = 1.

So, there are three pairs of roots summing to 0 (i.e., roots with
opposite signs):
1/2 + I*sqrt(3)/2 and -1/2 - I*sqrt(3)/2;
-1/2 + I*sqrt(3)/2 and 1/2 - I*sqrt(3)/2;
-1 and 1.

Note that if the sum contains k>3 roots then in this sum there exists
a pair of roots summing to 0 (i.e., one of the pairs listed above).
Therefore, the values of the sums of 4 roots coincide with those of
4-2=2 roots, and the values of the sums of 5 roots coincide with those
of 5-2=3 roots.
Therefore, the total number of distinct sums does not exceed
binomial(6,0) + binomial(6,1) + binomial(6,2) + binomial(6,3) +
binomial(6,6) = 43
So, it cannot be equal 48 as it was produced by you Mathematica code.
Actually, the correct number of distinct sums for n=6 is 19 (see
below).

My PARI/GP program from the previous message suffers the very same
problem of numerical instability and also produces incorrect (but
different from yours) results.
The correct PARI/GP code listed below:

{ a(n) = local(S=Set()); forvec(c=vector(n,i,[0,1]),
S=setunion(S,[Pol(c)%polcyclo(n)])); length(S) }

and the correct beginning of your sequence is:

? vector(14,n,a(n))
%33 = [2, 3, 7, 9, 31, 19, 127, 81, 343, 211, 2047, 361, 8191, 2059]

This sequence is present in OEIS under the name A107861, except that
the currently listed value A107861(1)=1 is incorrect. It should be
A107861(1)=2.

Max