Counting strings over $\mathbb{Z}2^d$ with Given Elementary Symmetric Function Evaluations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2013

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

Résumé

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.
Fichier principal
Vignette du fichier
dmAS0176.pdf (385.11 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01229695 , version 1 (17-11-2015)

Identifiants

Citer

Charles Robert Miers, Franck Ruskey. Counting strings over $\mathbb{Z}2^d$ with Given Elementary Symmetric Function Evaluations. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.897-908, ⟨10.46298/dmtcs.2352⟩. ⟨hal-01229695⟩

Collections

TDS-MACS
33 Consultations
645 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More