[math-fun] better posed problem? (small progress)

[wouter meeussen]

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 at ichips.intel.com>
To: "math-fun" <math-fun at 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 at 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 at 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 at mailman.xmission.com
http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun