[seqfan] Additive combination of unique cyclotomic polynomials

[Jack Brennen]

A little problem I've been working on for my own amusement:

For some fixed n, express x^n as an additive combination
of unique cyclotomic polynomials...  By additive combination,
we mean that each polynomial is either added or subtracted
once.

For instance, using the PARI notation where polcyclo(n) is
the nth cyclotomic polynomial, we can express x^3:

   x^3 = polcyclo(5)-polcyclo(1)-polcyclo(4)-polcyclo(8)

         (x^4+x^3+x^2+x+1) - (x-1) - (x^2+1) - (x^4+1)

Note that this problem is sort of in the vein of Goldbach,
because it takes things which are normally used for their
multiplicative properties (like primes or cyclotomic
polynomials), and then adds (or subtracts) them and
considers the set of possible sums.


At least one open question comes out of this:  can every
x^n be expressed as an additive combination of unique
cyclotomic polynomials?

Also, two possible integer sequences:

- For x^n, what is the minimum number of unique cyclotomic
   polynomials required to express x^n?

- For x^n, what is the minimum integer A such that x^n can
   be expressed using only some subset of the first A
   cyclotomic polynomials?

The first sequence seems to begin (with n=0):

3,2,2,4,4,6,...

The second sequence seems to begin (with n=0):

4,4,3,8,8,10,12,...


Is there an efficient search strategy to find such
representations of x^n?  For instance, I only have
one representation of x^9:

    polcyclo(13)+polcyclo(8)+polcyclo(3)+polcyclo(2)
   -polcyclo(42)-polcyclo(20)-polcyclo(11)-polcyclo(6)
   -polcyclo(5)-polcyclo(1)

And that one was found by hand.  Can x^9 be done with
fewer than 10 terms, and can it be done without going
out to the 42nd cyclotomic polynomial?  Note that
x^9 can be easily shown to require going out to at
least the 21st cyclotomic polynomial, because in each
of the first 20 cyclotomic polynomials, the coefficients
of x^9 and x^10 have the same parity, so no possible sum
from just the first 20 could possibly have an odd coefficient
for x^9 and an even coefficient for x^10.

You can then show that 21 isn't enough, because if it contains
the 21st cyclotomic polynomial:

   x^12 - x^11 + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1

then in order to cancel the x^12 term, it must also contain
the 13th cyclotomic polynomial:

   x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6
        + x^5 + x^4 + x^3 + x^2 + x + 1


However, if you take these two polynomials with opposite
signs, you end up canceling the x^12 terms, but introducing
an x^11 term which can't be canceled using the remaining
subset of the first 21 cyclotomic polynomials.

All of which is quite interesting, but perhaps difficult to
automate in an algorithm...