On subword decomposition and balanced polynomials (Q868909)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On subword decomposition and balanced polynomials |
scientific article |
Statements
On subword decomposition and balanced polynomials (English)
0 references
26 February 2007
0 references
Let \(H(x)\) be a monic polynomial over the finite field \(\mathbb{F}=\text{GF}(q)\), let \(\mathcal{N}_{a}(n)\) be the number of coefficients in the polynomial \(H(x)^n\) equal to a given element \(a\in\mathbb{F}\) and let \(G=\{a\in\mathbb{F}^\times : \mathcal{N}_{a}(n)>0\;\text{for some } n\}\). The relationship between the numbers \(\mathcal{N}_a(n)\), \(a\in G\), and the pattern of digits in the representation of \(n\) to the base \(q\) is studied. It is shown that for `most' \(n\), \(\mathcal{N}_a(n)\) is asymptotic to \(\mathcal{N}_b(n)\), improving on the known average result and allowing the extension to any \(H^n(x)\) the known result that asymptotic frequency of each \(a\in (\mathbb Z/p\mathbb Z)^{\times}\) in Pascal's triangle (corresponding to \(H(x)=x+1\)) is \(1/(p-1)\). The polynomial \(H^n(x)\) is totally balanced if \(\mathcal{N}_a(n)=\mathcal{N}_b(n)\) for all \(a,b\in G\). The general distribution of the maximum of the distance of the above ratio from \(1\) and the properties of \(\mathcal{N}_a(n)\) and related functions are investigated. Results for Pascal's triangle and some analogous ones for Stirling numbers are obtained and some related questions are raised.
0 references
linear cellular automata
0 references
Pascal's triangle
0 references
Stirling numbers
0 references
asymptotic frequency
0 references