Counting Strings with Given Elementary Symmetric Function Evaluations III: Strings over Z2d

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.



Back to list of publications.