about: A103306 Triangle read by rows: T(n,k) = number of k-subsets of the n-th roots of 1 that add to zero (0 <= k <= n). and: A103314 Total number of subsets of the n-th roots of 1 that add to zero. Hi all, the closest approach to sanity ;-) in this matter was Scott's result below. He came to
#(30) = 146854 with the proviso that More precisely, I find at least that many zero sum subsets. I conjecture that's all the zero sum subsets, but I don't have a proof.
So I undertook to reconstruct row n=30 of A103306 and found confirmation: T[30,k=0..30]= 146854; {1,0,15,10,105,126,525,780,2055,3060,5955,8010,12285,14190,17715,17190} I'll put the table at http://users.pandora.be/Wouter.Meeussen/RootZeros.xls It's still incomplete for n=26, 27 and 28. I'll complete those in due time. Together with Neil, I can only hope that someone comes up with a full & fast calculation technique for this nifty(?) problem. Wouter. ----------------------------------------------------------- Below is for Mathematica buffs only: KSubsets can be split in parts that fit available memory using: g[i_Integer /;(i<10)][low_Integer,(k_Integer)?Positive, o_:{}] := g[i+1][low+1,k-1, Append[o,low]]+g[i+1][low+1,k,o] (Skienna's recursion) using this, a list of 1024 parts is generated by List @@ (g[0][1, 15]) giving: g[10][11, 5, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}] g[10][11, 6, {1, 2, 3, 4, 5, 6, 7, 8, 9}] ... g[10][11, 14, {10}] g[10][11, 15, {}] and on each of these parts, I used: Count[#/. ru,q_List /; Chop[ Plus @@ (E^(2. Pi I q/30))] === 0] with 'ru' being the rule ru=(g[i_][low_,k_,li_List]:>(Flatten[Prepend[#,li]]&/@ KSubsets[Range[low,30],k])) Doing so combines the speed of list processing with low memory use. The expressions like 'g[10][11,6,{1,2,3,4,5,6,7,8,9}]' can be 'read' as: ..all KSubsets[Range[11,30], 6], but each with {1,2,3,4,5,6,7,8,9} prepended. Might come in handy elsewhere. -------------------------------------------------- ----- Original Message ----- From: "Scott Huddleston" <scotth@ichips.intel.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, March 24, 2005 11:27 PM Subject: Re: [math-fun] better posed problem? (small surprise)
From: "Meeussen Wouter (bkarnd)" <wouter.meeussen@vandemoortele.com>
it is a small surprise that, for w = Exp[ 2 Pi I /30 ] alias 1^(1/30) , w+w^7+w^8+w^18+w^19+w^25 = 0 no cancellation of symmetric pairs, triples or quintuples in sight, but w+w^7+w^19+w^25 = -w^13 (* four out of five *) and w^8+w^18 = -w^28 = +w^13 (* two out of three *)
could be called "cancellation by missing parts" ;-))
Let #(N) be the number of zero sum subsets of complex N'th roots of unity. I calculate #(30) = 146854 and more generally #(2.3.p) = 10^p + 6 (6^p + 2^p + 1) for prime p not 2 or 3, and #(2.5.p) = 34^p + 10 (18^p + 2.12^p + 2.8^p + 6.4^p + 7.2^p + 3) for prime p not 2 or 5. More precisely, I find at least that many zero sum subsets. I conjecture that's all the zero sum subsets, but I don't have a proof. When N contains 3 or more distinct prime factors, "cancellation" effects come into play as Wouter noted. This is usefully viewed by treating subsets as 0-1 vectors, and looking for sums and differences with net result a 0-1 vector. If these enumerations and earlier natural conjectures are true, we now know #(N) for N < 42. The techniques I used (and haven't elaborated) appear to generalize to any product of 3 primes, but hand calculation quickly becomes unfeasible. Handling a product of 4 primes looks MUCH harder.
From: Phil Carmody <thefatphil@yahoo.co.uk> (for N = 30) ... {0,1,7,13,19,20} is the symmetry-less set with minimal largest member that cancels.
{0,1,7,13,19,20} lifts to multiple of 30, but it is symmetric about line {9,24}. Adding the right balanced doubleton might give the reverse-lexicographically smallest set satisfying your property. Best, - Scott _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun