Is there a combinatoric identity for the multiplicities of the following set?

Are you ready for some psychedelic pictures? Define the multiset$$S_n=\left\{\sum_{j=1}^n(-1)^{\left\lfloor(k-1)/2^{j-1}\right\rfloor}u_n^j\mbox{ for }1\leq k\leq2^n\right\}$$ where $$u_n^j=\left(\begin{array}{cc} \\ \mbox{Cos}\left(\frac{2\pi j}{n}\right) \\ \mbox{Sin}\left(\frac{2\pi j}{n}\right) \end{array}\right)$$ is the unit vector pointing in the $2\pi j/n$-direction.

Here is a picture of $S_0$:

Here is a picture of $S_1$:

Here is a picture of $S_2$:

Here is a picture of $S_3$:

Here is a picture of $S_4$:

Here is a picture of $S_5$:

Here is a picture of $S_6$:

Here is a picture of $S_7$:

Here is a picture of $S_8$:

Here is a picture of $S_9$:

Here is a link to a 1761 x 1761 pixel version.

Here is a picture of $S_{10}$:

Here is a link to a 1941 x 1941 pixel version.

Here is a picture of $S_{11}$:

Here is a link to a 3432 x 3432 pixel version.

Here is a picture of $S_{12}$:

Here is a link to a 3048 x 3048 pixel version.

Here is a picture of $S_{13}$:

Here is a link to a 6683 x 6683 pixel version.

Here is a picture of $S_{14}$:

Here is a link to a 4317 x 4317 pixel version.

Here is a picture of $S_{15}$:

Here is a link to a 7638 x 7638 pixel version.

Here is a picture of $S_{16}$:

Here is a link to a 7946 x 7946 pixel version.

The preceding pictures were obtained by placing a 2D Lorentzian function at the coordinates specified by each element of $S_k$. Because some points occur multiple times in $S_k$, some of the light sources are brighter than others, with bright points being high degeneracy, and dim points being low degeneracy.

This naturally brings about the question:

• What is the distribution of point brightnesses in the preceding photographs?

To get a start, I computed the degeneracy of each vector in $S_n$ for $0\leq n \leq 15$, and then histogrammed the degeneracies (ie, $\mbox{Tally[Tally[}S_n\mbox{][[All,2]]]}$ in Mathematica notation), which yielded the following results: $$\left( \begin{array}{cc} n\text{ = 0} & \left( \begin{array}{cc} 1 & 1 \\ \end{array} \right) \\ n\text{ = 1} & \left( \begin{array}{cc} 1 & 2 \\ \end{array} \right) \\ n\text{ = 2} & \left( \begin{array}{cc} 1 & 2 \\ 2 & 1 \\ \end{array} \right) \\ n\text{ = 3} & \left( \begin{array}{cc} 1 & 6 \\ 2 & 1 \\ \end{array} \right) \\ n\text{ = 4} & \left( \begin{array}{cc} 1 & 4 \\ 2 & 4 \\ 4 & 1 \\ \end{array} \right) \\ n\text{ = 5} & \left( \begin{array}{cc} 1 & 30 \\ 2 & 1 \\ \end{array} \right) \\ n\text{ = 6} & \left( \begin{array}{cc} 1 & 6 \\ 2 & 6 \\ 6 & 6 \\ 10 & 1 \\ \end{array} \right) \\ n\text{ = 7} & \left( \begin{array}{cc} 1 & 126 \\ 2 & 1 \\ \end{array} \right) \\ n\text{ = 8} & \left( \begin{array}{cc} 1 & 16 \\ 2 & 32 \\ 4 & 24 \\ 8 & 8 \\ 16 & 1 \\ \end{array} \right) \\ n\text{ = 9} & \left( \begin{array}{cc} 1 & 216 \\ 2 & 108 \\ 4 & 18 \\ 8 & 1 \\ \end{array} \right) \\ n\text{ = 10} & \left( \begin{array}{cc} 1 & 30 \\ 2 & 70 \\ 4 & 60 \\ 8 & 20 \\ 12 & 20 \\ 18 & 10 \\ 34 & 1 \\ \end{array} \right) \\ n\text{ = 11} & \left( \begin{array}{cc} 1 & 2046 \\ 2 & 1 \\ \end{array} \right) \\ n\text{ = 12} & \left( \begin{array}{cc} 1 & 36 \\ 2 & 72 \\ 4 & 36 \\ 6 & 72 \\ 10 & 12 \\ 12 & 72 \\ 20 & 12 \\ 36 & 36 \\ 60 & 12 \\ 100 & 1 \\ \end{array} \right) \\ n\text{ = 13} & \left( \begin{array}{cc} 1 & 8190 \\ 2 & 1 \\ \end{array} \right) \\ n\text{ = 14} & \left( \begin{array}{cc} 1 & 126 \\ 2 & 434 \\ 4 & 630 \\ 8 & 490 \\ 16 & 210 \\ 24 & 70 \\ 32 & 42 \\ 36 & 42 \\ 66 & 14 \\ 130 & 1 \\ \end{array} \right) \\ n\text{ = 15} & \left( \begin{array}{cc} 1 & 6510 \\ 2 & 4620 \\ 3 & 420 \\ 4 & 1380 \\ 5 & 360 \\ 6 & 360 \\ 8 & 60 \\ 9 & 120 \\ 10 & 180 \\ 12 & 120 \\ 14 & 60 \\ 20 & 30 \\ 38 & 1 \\ \end{array} \right) \\ \end{array} \right)$$ As an example of the notation above, for $n=15$, there were 6510 points of brightness 1, 4620 points of brightness 2, ..., and 1 point of brightness 38.

I tried searching the Sloane OEIS database for the columns of these finite integer sequences to see if they formed the beginning of any sequences, but found no obvious matches.

Question: Has anyone ever seen these sequences before? And is there a combinatorial method to determine the multiplicity of an arbitrary element of $S_n$?

A bit of background: One can show with a little geometry that the vector elements of $S_n$ and their multiplicities are actually the locations and brightnesses of the maxima of the following bivariate function: $$f_n(k_1,k_2)=\left|\int_{-\infty}^\infty dx\int_{-\infty}^\infty dy\mbox{ }e^{2\pi i(k_1x+k_2y)}\prod_{j=1}^ng\left[(1,0)\cdot R\left(\frac{2\pi j}{n}\right)\cdot(x,y)\right]\mbox{Cos}\left[(1,0)\cdot R\left(\frac{2\pi j}{n}\right)\cdot(x,y) \right]\right|$$ where $g$ is any slowly-varying "structure factor" function and $R(\theta)$ is the rotation matrix of angle $\theta$. For example, here is a plot of $\sqrt{f_{11}(k_1,k_2)}$:

A larger and much more beautiful 2000 x 2000 pixel version is available here. The above image is essentially $S_{11}$, but convolved with the Fourier transform of the structure factor (I used $g$ to be a shifted Heaviside theta function $g(x)=\theta(c-x)$). The brightness channels of the image are saturated to show the finer details of the set.

One can also make additional interesting pictures by replacing $\mbox{Cos}\left[(1,0)\cdot R\left(\frac{2\pi j}{n}\right)\cdot(x,y) \right]$ with more complicated frequency-modulated functions like $\mbox{Cos}\left[z\mbox{ }\mbox{Cos}\left[(1,0)\cdot R\left(\frac{2\pi j}{n}\right)\cdot(x,y) \right]\right]$, which according to the Jacobi-Anger expansion will generate higher-order Bessel-weighted harmonics of the lattice, such as shown in the following image of $S_5$:

The image has been computed using an FFT which was purposefully chosen to Nyquist alias the higher harmonics of $S_5$ into the picture frame, generating the constellation-like pattern seen there. Here is a slightly-larger 1000 x 1000 pixel version. And here's another interesting one, which I can't remember how I made, but which might not actually be a picture of an $S_n$ (I was doing random things at the time):

A 2000 x 2000 pixel version is available here. I hope someone finds the posted images as beautiful as I find them, even if a combinatoric solution is not available! :)

Solution 1:

The vectors $u_j^n$ are powers of the primitive $n$-th root of unity $\zeta_n$ in the complex plane. The collection of vectors $S_n$ you are looking at for each fixed $n$ consists of all combinations of sign assignments of $$\pm\zeta_n^1 \pm \zeta_n^2 \pm \cdots \pm \zeta_n^n.$$ This follows from the fact that $\left\lfloor{(k-1)/2^{j-1}}\right\rfloor$ yields the $j$-th digit of the binary expansion of $k$. The $2^n$ choices for $k$ correspond naturally to choices for a subset of $\{1,\ldots,n\}$ that determines a choice of signs.

All calculations take place in $\mathbb{Q}(\zeta_n)$, the $n$-th cyclotomic field. For a given sign assignment, you can divide its corresponding polynomial by the $n$-th cyclotomic polynomial and find the remainder. This determines a vector in $\mathbb{Q}(\zeta_n)$. Since $\mathbb{Q}(\zeta_n)$ is a vector space, two of your vectors are equal if and only if they have the same coefficients in $\mathbb{Q}(\zeta_n)$. For example, for $n=6$, we have $\zeta_6^1 + \zeta_6^2 - \zeta_6^3 + \zeta_6^4 - \zeta_6^5 - \zeta_6^6 = -2 + 2\zeta_6 = \zeta_6^1 + \zeta_6^2 + \zeta_6^3 - \zeta_6^4 + \zeta_6^5 - \zeta_6^6$. The middle vector $-2 + 2\zeta_6$ is expressed in the standard basis for $\mathbb{Q}(\zeta_6)$.

This gives a brute force approach to finding your distribution that relies only on integer (or rational) polynomial division. For your question on how many are equal to a particular given vector, we can reverse the polynomial division to create a tree of possibilities that terminates with a list of equivalent vectors. This is also brute force, though, and there may be a better way.

For prime $p$, the $p$-th cyclotomic polynomial is $x^{p-1} + x^{p-2} + \cdots + x + 1$. Thus, it is not hard to convince ourselves that $S_p$ consists of the zero vector twice, and all other vectors occur exactly once.

For arbitrary $n$, I suspect it can be hard even to determine how many of these are the zero vector, let alone the rest of the distribution. When we ask the simple question of how many of the sign choices yield the zero vector for arbitrary $n$, we arrive at OEIS103314. That OEIS entry has many nice formulae, but I see no formula that would give the correct answer for $n = pqr$, where $p$, $q$, and $r$ are distinct odd primes.

Lastly, your pictures bear a striking resemblance to the Petrie polygon orthographic projections of an $n$-cube into the plane, but only for $n$ odd. (Take an $n$-dimensional hypercube and project its vertices and edges into the plane in a particular way.) Your pictures are nicer, but for reference and comparison, see Wikipedia's hypercube page.