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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references