Counting Strings over $\mathbb{Z}_{2^d}$ with given elementary function evaluations.

Counting Strings with Given Elementary Symmetric Function Evaluations III: Strings over $\mathbb{Z}_{2^d}$

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
C. Robert Miers, Department of Mathematics and Statistics, University of Victoria, Canada.

Abstract:

Let $\alpha$ be a string over $\mathbb{Z}_{q}$, where $q = 2^d$. The $j$-th elementary symmetric function evaluated at $\alpha$ is denoted $e_{j}({\alpha})$. We study the cardinalities $S_{q}(m;\tau_1,\tau_2,\ldots,\tau_t)$ of the set of length $m$ strings for which $e_{i}({\alpha}) = \tau_i$. The profile $\mathbf{k}(\alpha) = \langle k_1,k_2,\ldots,k_{q-1} \rangle$ of a string $\alpha$ is the sequence of frequencies with which each letter occurs. The profile of $\alpha$ determines $e_{j}({\alpha})$, and hence $S_{q}$. Let $h_n : \mathbb{Z}_{2^{n+d-1}}^{(q-1)} \mapsto \mathbb{Z}_{2^d}[z] \bmod{z^{2^n}}$ be the map that takes $\mathbf{k}(\alpha) \bmod{2^{n+d-1}}$ to the polynomial $1+e_{1}({\alpha}) z+ e_{2}({\alpha}) z^2 + \cdots + e_{2^n-1}({\alpha}) z^{2^n-1}$. We show that $h_n$ is a group homomorphism and establish necessary conditions for membership in the kernel for fixed $d$. The kernel is determined for $d = 2,3$. The range of $h_n$ is described for $d = 2$. These results are used to efficiently compute $S_{4}(m;\tau_1,\tau_2,\ldots,\tau_t)$ for $d = 2$ and the number of complete factorizations of certain polynomials.

Accepted as a poster at FPSAC '13, The 25th International Conference on Formal Power Series and Algebraic Combinatorics, Paris, France, June 24-28, 2013.
Conference Proceedings: Discrete Mathematics and Theoretical Computer Science, DMTCS proc. AS, 2013, 927-938 (link).
Lists of kernels of $h_1, h_2, h_3$ over $\mathbb{Z}_8$:
- The links below give the kernel $k[1..7]$ of $h_1$ over $\mathbb{Z}_8$. There are $2^{18} = 262,144$ kernel elements in total. A typical line in this table looks like 5 2 3 0 3 1 7, meaning that the polynomial $(1+z)^5 (1+2z)^2 (1+3z)^3 (1+4z)^0 (1+5z)^3 (1+6z)^1 (1+7z)^7$ (mod 8) is of the form $1 + O(z^2)$.
  The exact value is: $1+z^2+2z^3+4z^6+6z^8+6z^{10}+6z^{11}+4z^{12}+4z^{14}+5z^{16}+z^{18}+2z^{19}+4z^{20}$.
  Links: Z8n1kernel.txt or zipped Z8n1kernel.zip.
- The links below give the kernel $k[1..7]$ of $h_2$ over $\mathbb{Z}_8$. There are $2^{20} = 1,048,576$ kernel elements in total. A typical line in this table looks like 15 4 13 6 5 12 15, meaning that the polynomial $(1+z)^{15} (1+2z)^4 (1+3z)^{13} (1+4z)^6 (1+5z)^5 (1+6z)^{12} (1+7z)^{15}$ (mod 8) is of the form $1 + O(z^4)$.
  The corresponding expansion up to $O(z^{32})$ is: $1+4z^4+2z^8+4z^{12}+7z^{16}+4z^{24}+O(z^{32})$.
  Links: Z8n2kernel.txt or zipped Z8n2kernel.zip.
- Here there are $2^{24} = 16,777,216$ kernel elements in total. In this case the kernel is the interleaved product of $O_3$ and $E_3$. For example, adding the kernel element 24 0 16 0 0 24 from $O_3$ and 0 3 0 1 0 1 0 from $E_3$ gives 24 3 16 1 0 1 24, meaning that the polynomial $(1+z)^{24} (1+2z)^3 (1+3z)^{16} (1+4z) (1+6z) (1+7z)^{24} \bmod{8}$ is of the form $1 + O(z^8)$.
  Links: See $n=3$ below.
Lists of $E_n$ and $O_n$ parts of kernels of $h_1, h_2, h_3$ over $\mathbb{Z}_8$:
- $n=1$: $|E_1| = 2^7 = 128$, $|O_1| = 2^9 = 512$.
  Links: Z8even1.txt, Z8odd1.txt.
- $n=2$: $|E_2| = 2^9 = 512$, $|O_2| = 2^{10} = 1024$.
  Links: Z8even2.txt, Z8odd2.txt.
- $n=3$: $|E_3| = 2^{12} = 4069$, $|O_3| = 2^{12} = 4096$.
  Links: Z8even3.txt, Z8odd3.txt.

Back to list of publications.