A110981 -id:A110981 - cp's OEIS frontend

A103314 Total number of subsets of the n-th roots of 1 that add to zero.

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

Offset: 0

Wouter Meeussen, Mar 11 2005

The term a(0) = 1 counts the single zero-sum subset of the (by convention) empty set of zeroth roots of 1.
I am inclined to believe that if S is a zero-sum subset of the n-th roots of 1, that n can be built up from (zero-sum) 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^n-a(n))/n. - T. D. Noe, May 25 2005
From Max Alekseyev, Jan 31 2008: (Start)
Every subset of the set U(n) = { 1=r^0, r^1, ..., r^(n-1) } of the n-th power roots of 1 (where r is a fixed primitive root) defines a binary word w of the length n where the j-th 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 d|n) 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 dThe binary Lyndon words of the length n are different in this respect: only some of them correspond to n distinct zero-sum 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 zero-sum subsets of U(n). (End)

Max Alekseyev and M. F. Hasler, Table of n, a(n) for n = 0..164
T. Y. Lam and K. H. Leung, On vanishing sums for roots of unity, arXiv:math/9511209 [math.NT], 1995.
T. D. Noe, Sums of Roots of Unity Plots
T. D. Noe, Proof a(n)=a(s(n))^(n/ s(n))
Sasha Rybak, Zero sums of roots of unity (in Russian), forum dxdy.ru.
Gary Sivek, On vanishing sums of distinct roots of unity, #A31, Integers 10 (2010), 365-368.

Equals A070894 + 1. A107847(n) = (2^n - A103314(n))/n, A110981 = A001037 - A107847.
Row sums of A103306. See also A006533, A006561, A006600, A007569, A007678.
Cf. A070925, A107753 (number of primitive subsets of the n-th roots of unity summing to zero), A107754 (number of subsets of the n-th roots of unity summing to one), A107861 (number of distinct values in the sums of all subsets of the n-th roots of unity).
Cf. A322366.

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 *)

/* 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) }
/* Max Alekseyev and M. F. Hasler, Jan 31 2008 */

a(n) = A070894(n)+1.
a(2^n) = 2^(2^(n-1)). - 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^q-2. In particular, if p is prime, a(2p) = 2^p + 2. - Gareth McCaughan, Mar 12 2005
a(n) == 2^n (mod n), a(p) = 2 (p prime). - David W. Wilson, May 08 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 zero-sum subsets of the n-th 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^(n-1), a(p^m q^n) = (2^p+2^q+2)^(p^(m-1) q^(n-1)) 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 p|n; a(2p) = 2^p+2 when p is an odd prime. More generally a(pq) = 2^p+2^q-2 when p, q are distinct primes. - Gareth McCaughan, 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^(p-j))^q. - Sasha Rybak, Sep 21 2007.
a(n) = n*A110981(n) + 2^n - n*A001037(n). - Max Alekseyev, Jan 14 2008

More terms from David W. Wilson, Mar 12 2005
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.
More terms from T. D. Noe, May 25 2005
Further terms from Max Alekseyev and M. F. Hasler, Jan 07 2008
Edited by M. F. Hasler, Feb 06 2008
Duplicate Mathematica program deleted by Harvey P. Dale, Jun 28 2021

A164896 Number of subsets (up to cyclic shifts) of the n-th roots of 1 with zero sum.

Original entry on oeis.org

1, 2, 2, 3, 2, 5, 2, 6, 4, 9, 2, 19, 2, 21, 10, 36, 2, 94, 2, 117, 22, 189, 2, 618, 8, 633, 60, 1203, 2, 6069, 2, 4116, 190, 7713, 26, 35324, 2, 27597, 634, 59706, 2, 328835, 2, 190935, 2728, 364725, 2, 2435780, 20, 1579884, 7714, 2582061, 2, 21013770, 194, 9894294, 27598, 18512793, 2, 377367015, 2, 69273669, 104832, 134219796, 638, 1678410951

Offset: 1

Joerg Arndt, Aug 30 2009

nonn

Cyclic shifts correspond to multiplication by a root of unity.

a(n)=2 for n prime, corresponding to the empty and the full subset. - Joerg Arndt, Jun 10 2011

			a(6) = 5 because these subsets add to zero: (left: as bitstring, right: subset)
  ......  (empty sum)
  ..1..1  0 3
  .1.1.1  0 2 4
  .11.11  0 1 3 4
  111111  0 1 2 3 4 5 (all roots of unity)

Andrew Howroyd, Table of n, a(n) for n = 1..164
Joerg Arndt, Matters Computational (The Fxtbook), section 18.4 "Sums of roots of unity that are zero", p. 383.

Cf. A066656, A103314, A110981 (counts subsets with bitstrings being Lyndon words).

a(n) = A110981(n) + Sum_{d|n,dA001037(d) = A110981(n) + A000031(n) - A001037(n). - Max Alekseyev, Apr 08 2013

a(n) = A110981(n) + A066656(n). - Andrew Howroyd, Mar 22 2023

a(32)-a(39) from Joerg Arndt, Jun 10 2011

Terms a(40) onward from Max Alekseyev, Apr 08 2013

A107847 Related to sums of the n-th roots of unity: sums in a circular wedge (excluding the origin).

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 333, 630, 1161, 2182, 4080, 7710, 14508, 27594, 52371, 99858, 190557, 364722, 698634, 1342176, 2580795, 4971008, 9586377, 18512790, 35786499, 69273666, 134215680, 260300986, 505286415, 981706806

Offset: 1

T. D. Noe, May 25 2005

nonn

Consider the 2^n sums formed from all the subsets of the n-th roots of unity. The number A103314(n) tells how many of these sums are zero. The remaining sums fall into n wedges centered at the origin. The number a(n) gives the number of sums that fall into each wedge. Interestingly, a(n) coincides with A059966(n) when n is either p^k or pq for primes p and q.

Max Alekseyev and M. F. Hasler, Table of n, a(n) for n = 1..164
T. D. Noe, Sums of Roots of Unity Plots

Cf. A103314 (number of subsets of the n-th roots of unity summing to zero), A107848 (number of subsets of the n-th roots of unity summing to a real number).

Cf. also A110981.

a(n) = (2^n - A103314(n))/n.

a(n) = A001037(n) - A110981(n). - Max Alekseyev, Jan 14 2008

A273096 Number of rotationally inequivalent minimal relations of roots of unity of weight n.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 3, 3, 4, 6, 18, 69

Offset: 0

Christopher E. Thompson, May 15 2016

In this context, a relation of weight n is a multiset of n roots of unity which sum to zero, and it is minimal if no proper nonempty sub-multiset sums to zero. Relations are rotationally equivalent if they are obtained by multiplying each element by a common root of unity.

Mann classified the minimal relations up to weight 7, Conway and Jones up to weight 9, and Poonen and Rubinstein up to weight 12.

			Writing e(x) = exp(2*Pi*i*x), then e(1/6)+e(1/5)+e(2/5)+e(3/5)+e(4/5)+e(5/6) = 0 and this is the unique (up to rotation) minimal relation of weight 6.

J. H. Conway and A. J. Jones, Trigonometric diophantine equations (On vanishing sums of roots of unity), Acta Arithmetica 30(3), 229-240 (1976).
Henry B. Mann, On linear relations between roots of unity, Mathematika 12(2), 107-117 (1965).
Bjorn Poonen and Michael Rubinstein, The Number of Intersection Points Made by the Diagonals of a Regular Polygon, SIAM J. Discrete Math. 11(1), 135-156 (1998). Also at arXiv:math/9508209 [math.MG] with some typos corrected.

Cf. A103314, A110981, A164896.

Showing 1-4 of 4 results.

cp's OEIS Frontend

A103314 Total number of subsets of the n-th roots of 1 that add to zero.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A164896 Number of subsets (up to cyclic shifts) of the n-th roots of 1 with zero sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A107847 Related to sums of the n-th roots of unity: sums in a circular wedge (excluding the origin).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A273096 Number of rotationally inequivalent minimal relations of roots of unity of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs