## 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}$.
• 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})$.
• 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$: