

A103314


Total number of subsets of the nth roots of 1 that add to zero.


22



1, 1, 2, 2, 4, 2, 10, 2, 16, 8, 34, 2, 100, 2, 130, 38, 256, 2, 1000, 2, 1156, 134, 2050, 2, 10000, 32, 8194, 512, 16900, 2, 146854, 2, 65536, 2054, 131074, 158, 1000000, 2, 524290, 8198, 1336336, 2, 11680390, 2, 4202500, 54872, 8388610, 2, 100000000, 128
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

The term a(0) = 1 counts the single zerosum subset of the (by convention) empty set of zeroth roots of 1.
I am inclined to believe that if S is a zerosum subset of the nth roots of 1, that n can be built up from (zerosum) cyclically balanced subsets via the following operations: 1. A U B, where A and B are disjoint. 2. A  B, where B is a subset of A.  David W. Wilson, May 19 2005
Lam and Leung's paper, though interesting, does not apply directly to this sequence because it allows repetitions of the roots in the sums.
Observe that 2^n=a(n) (mod n). Sequence A107847 is the quotient (2^na(n))/n.  T. D. Noe, May 25 2005
Every subset of the set U(n) = { 1=r^0, r^1, ..., r^(n1) } of the nth power roots of 1 (where r is a fixed primitive root) defines a binary word w of the length n where the jth bit is 1 iff the root r^j is included in the subset.
If d is the period of w with respect to cyclic rotations (thus dn) then the periodic part of w uniquely defines some binary Lyndon word of the length d (see A001037). In turn, each binary Lyndon word of the length d, where d<n and dn, corresponds to d distinct zerosum subsets of U(n).
The binary Lyndon words of the length n are different in this respect: only some of them correspond to n distinct zerosum subsets of U(n) while the others do not correspond to such subsets at all. A110981(n) gives the number of binary Lyndon words of the length n that correspond to zerosum subsets of U(n). (End)


LINKS



FORMULA

a(2^n) = 2^(2^(n1)).  Dan Asimov and Gareth McCaughan, Mar 11 2005
a(2n) = a(n)^2 if n is even. If p, q are primes, a(pq) = 2^p+2^q2. In particular, if p is prime, a(2p) = 2^p + 2.  Gareth McCaughan, Mar 12 2005
It appears that a(n) = a(s(n))^(n/s(n)) where s(n) = A007947(n) is the squarefree kernel of n. This is true if all zerosum subsets of the nth roots of 1 are formed by set operations on cyclic subsets. If true, A103314 is determined by its values on squarefree numbers (A005117). Some consequences would be a(p^n) = 2^p^(n1), a(p^m q^n) = (2^p+2^q+2)^(p^(m1) q^(n1)) and a(p^2 n) = a(pn)^p for primes p and q.  David W. Wilson, May 08 2005
a(pn) = a(n)^p when p is prime and pn; a(2p) = 2^p+2 when p is an odd prime. More generally a(pq) = 2^p+2^q2 when p, q are distinct primes.  Gareth McCaughan (gareth.mccaughan(AT)pobox.com), Mar 12 2005
For distinct odd primes p and q, a(2pq) = (2^p+2)^q + (2^q+2)^p  2(2^p+1)^q  2(2^q+1)^p + 2^(pq) + SUM[j=0..p] binomial(p,j)(2^j+2^(pj))^q.  Sasha Rybak, Sep 21 2007.


MATHEMATICA

Needs["DiscreteMath`Combinatorica`"]; Table[Plus@@Table[Count[ (KSubsets[ Range[n], k]), q_List/; Chop[ Abs[Plus@@(E^(2.*Pi*I*q/n))]]==0], {k, 0, n}], {n, 15}] (* T. D. Noe *)


PROG

(PARI)
/* This program implements all known results; it works for all n except for 165, 195, 210, 231, 255, 273, 285, 330, 345, ... */
A103314(n) = { local(f=factor(n)); n<2 & return(1); n==f[1, 1] & return(2);
vecmax(f[, 2])>1 & return(A103314(f=prod(i=1, #f~, f[i, 1]))^(n/f));
if( 2==#f=f[, 1], return(2^f[1]+2^f[2]2));
#f==3 & f[1]==2 & return(sum(j=0, f[2], binomial(f[2], j)*(2^j+2^(f[2]j))^f[3])
+(2^f[2]+2)^f[3]+(2^f[3]+2)^f[2]2*((2^f[2]+1)^f[3]+(2^f[3]+1)^f[2])+2^(f[2]*f[3]));
n==105 & return(166093023482); error("A103314(n) is unknown for n=", n) }


CROSSREFS

Cf. A070925, A107753 (number of primitive subsets of the nth roots of unity summing to zero), A107754 (number of subsets of the nth roots of unity summing to one), A107861 (number of distinct values in the sums of all subsets of the nth roots of unity).


KEYWORD

nonn,nice,hard


AUTHOR



EXTENSIONS

Scott Huddleston (scotth(AT)ichips.intel.com) finds that a(30) >= 146854 and conjectures that is the true value of a(30).  Mar 24 2005. Confirmed by Meeussen and Wilson.


STATUS

approved



