Value a(6) in doubt for a = A101877

[hv at crypt.org]

> -----Original Message-----
> From: Maximilian Hasler [mailto:maximilian.hasler at gmail.com]
> Sent: Monday, January 14, 2008 1:30 PM
> To: David W. Wilson
> Subject: Re: formula for A103314(2pq)
> 
> > No, you are right. Complement is insufficient, you need subset
> difference.
> > Sorry. I was trying to reconstruct an old conjecture from memory.
> 
> after inspection, I conjecture that none of both is needed :
> it is sufficient to start with {} and { e_n^k U_d , d|n, d>1 }
> and repeatedly add disjoint unions (e_n=exp(i2pi/n)).
> 
> I checked this with my explicit ("stupid") code for all n<105 with
> a(n)<10000;
> unfortunately already for the smallest n with >2 prime factors
> (2*3*5=30) it takes too long (for me, impatient).

I am amending my conjecture to the following:

CONJECTURE: Let U_n be the set of nth roots of unity, Then the set Z_n of
zero-sum elements of U_n is the closure of

      P_n = { U_p: p prime, p | n }

With respect to

      (1) r(S) = e_n S = rotation of S by e_n,
      (2) ~S = complement S with respect to U_n, and
      (3) S U T = Union of disjoint S and T.

      ----

It turns out I was right about complement being sufficient after all.  We
can define each of complement, disjoint union, or subset difference (A \ B
where B c A) in terms of the other two, to wit:

      ~A = U_n - A
      A - B = ~(~A U B)
      A U B = ~(~A - B)

So any two of complement, disjoint union, or subset difference can be used
for (2) and (3) in the conjecture. 

      ----

We also have

      r(~S) = ~r(S)
      r(S U T) = r(S) U r(T)

This means that we can build any element of Z_n by applying all rotations
first, then afterwards complements, unions or differences. Thus we can close
P_n with respect to rotation to obtain Q_n, then close Q_n with respect to
complements and disjoint unions to obtain Z_n, which is more efficient
computationally.

Your base set { e_n^k U_d , d|n, d>1 } tacitly includes rotations as the
e_n^k multiplier. From a computational standpoint, you still have to
generate the U_d, then apply the rotations to get your base set. Hiding the
rotations in your base set does not relieve you of the computational burden
of applying them. Your method is in effect closing { U_d } with respect to
rotation, then closing the result (your base set) with respect to the other
operations. You get a computational savings by doing the rotations first,
but you have not dispense with the rotations from a computational or
mathematical standpoint.

And yes, I recognize that your base set {{}} U { U_d: d | n } is a little
different from my { U_p : p prime, p | n }, but with a little work, I can
show that all the elements of your base set are generated from mine, so the
resulting Z_n will be the same.

    ----

However, in regard to your assertion that rotation and disjoint union are
sufficient to generate Z_n without complement or subset difference, that is
wrong. It may be true if n has two or fewer prime divisors, but Z_30
includes the element

    { e_n^k | k in {0,6,12,18,24}U{5,15,25}-{0,15} }

which cannot be generated from { U_p } or { U_d } by rotation and disjoint
union alone. You need something more, my conjecture is that complement or
subset difference suffices.

> Maximilian
> PS: no problem if you can't run my code, it was just for illustration
> of my algorithm (yours simplified) and what I told (storing subsets as
> sum(2^i), doing intersection through bitand(), etc)
> - oh I see it was in fact NOT the simplified version, but still used
> differences...
>
> [code elided]

I'm sorry, I'm not a symbolic math geek, I don't know much about PARI or
Maple or Mma. Looking at your code suggests you are actually modeling your
sets as sets of nth roots of unity. As a programming geek, my approach would
be to model these sets as bit vectors (integers) and use shifts and logical
bit operations to effect rotations, complements and unions. I'm guessing
this would be faster by a significant constant factor. However, I don't see
a way around the apparent O(n^2)-ness of closure with respect to disjoint
union, so Z_30 would still take a while.