Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/hal-01229695
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:20:05 AM
Last modification on : Friday, June 1, 2018 - 3:24:01 PM
Long-term archiving on: : Thursday, February 18, 2016 - 11:40:32 AM

File

dmAS0176.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229695, version 1

Collections

Citation

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. ⟨hal-01229695⟩

Share

Metrics

Record views

80

Files downloads

717