# Counting strings over $\mathbb{Z}2^d$ with Given Elementary Symmetric Function Evaluations

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;\mathcal{T} _1,\mathcal{T} _2,\ldots,\mathcal{T} _t)$ of the set of length $m$ strings for which $e_j(\alpha) = \tau _i$. The $\textit{profile}$ k$(\alpha) = ⟨k_1,k_2,\ldots,k_(q-1) ⟩$ 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]$ mod $z^{2^n}$ be the map that takes k$(\alpha)$ mod $2^{n+d-1}$ to the polynomial $1+ e_1(\alpha) z + e_2(\alpha) z^2 + ⋯+ 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;\mathcal{T} _1,\mathcal{T} _2,\ldots,\mathcal{T} _t)$ for $d$ = 2 and the number of complete factorizations of certain polynomials.
Keywords :
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.897-908, 2013, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [4 références]

https://hal.inria.fr/hal-01229695
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:20:05
Dernière modification le : mardi 7 mars 2017 - 15:23:42
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:40:32

### Fichier

dmAS0176.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01229695, version 1

### Citation

Charles Robert Miers, Franck Ruskey. Counting strings over $\mathbb{Z}2^d$ with Given Elementary Symmetric Function Evaluations. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.897-908, 2013, DMTCS Proceedings. 〈hal-01229695〉

### Métriques

Consultations de la notice

## 37

Téléchargements de fichiers