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.

• 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).
• Relevant tables:
• The links below give the kernel $k[1..7]$ of $h_1$ over $\mathbb{Z}_8$ with the restrictions 0 < k[2],k[6] < 4 and 0 < k[4] < 2. The missing members of the kernel may be obtained by incrementing k[2] by {4}; k[4] by {2,4,6}; k[6] by {4}. That is, each of the 16384 lines in the file line in the file corresponds to $2 \cdot 4 \cdot 2 = 16$ kernel elements. 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(z2).
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$ with the restrictions 0 < k[2],k[6] < 4 and 0 <= k[4] < 2. The missing members of the kernel may be obtained by incrementing k[2] by {4,8,12}; k[4] by {2,4,6,8,10,12,14}; k[6] by {4,8,12}. That is, each of the 4096 = 212 lines in the file corresponds to $4 \cdot 8 \cdot 4 = 128 = 2^7$ kernel elements, for a total of $2^{19}$ elements in the kernel. 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+4z4+2z8+4z12+7z16+4z24+O(z32).
• The links below give the kernel $k[1..7]$ of $h_3$ over $\mathbb{Z}_8$ with the restrictions $0 \le k[2],k[6] < 4$ and $0 \le k[4] < 2$. The missing members of the kernel may be obtained by incrementing $k[2]$ by $\{4,8,12,16,20,24,28\}$; $k[4]$ by $\{2,4,6,8,10,12,14,16,18,20,22,24,28,30\}$; $k[6]$ by $\{4,8,12,16,20,24,28\}$; That is, each of the $4096 = 2^{12}$ lines in the file corresponds to $8 \cdot 16 \cdot 8 = 2^{10}$ kernel elements, for a total kernel size of $2^{22}$. A typical line in this table looks like 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)$.