Counting prime polynomials and measuring complexity and similarity of information

Files

Rebenich_Niko_PhD_2016.pdf (2.12 MB)

Date

2016-05-02

Authors

Rebenich, Niko

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

This dissertation explores an analogue of the prime number theorem for polynomials over finite fields as well as its connection to the necklace factorization algorithm T-transform and the string complexity measure T-complexity. Specifically, a precise asymptotic expansion for the prime polynomial counting function is derived. The approximation given is more accurate than previous results in the literature while requiring very little computational effort. In this context asymptotic series expansions for Lerch transcendent, Eulerian polynomials, truncated polylogarithm, and polylogarithms of negative integer order are also provided. The expansion formulas developed are general and have applications in numerous areas other than the enumeration of prime polynomials. A bijection between the equivalence classes of aperiodic necklaces and monic prime polynomials is utilized to derive an asymptotic bound on the maximal T-complexity value of a string. Furthermore, the statistical behaviour of uniform random sequences that are factored via the T-transform are investigated, and an accurate probabilistic model for short necklace factors is presented. Finally, a T-complexity based conditional string complexity measure is proposed and used to define the normalized T-complexity distance that measures similarity between strings. The T-complexity distance is proven to not be a metric. However, the measure can be computed in linear time and space making it a suitable choice for large data sets.

Description

Keywords

prime numbers, prime polynomials, finite fields, irreducible polynomials, polylogarithm, Lerch transcendent, Eulerian polynomials, T-codes, NCD, necklaces, string complexity, information distance, divergent series, asymptotic approximation, randomess test, conditional complexity, necklace factorization, prime number theorem, combinatorics, T-complexity, data mining, optimal truncation, function fields, lyndon words, lyndon factorization, similarity measure, asymptotic enumeration

Citation

URI

http://hdl.handle.net/1828/7251

Collections

ETD (Electronic Theses and Dissertations)
Theses (Electrical and Computer Engineering)
 
University of Victoria Libraries

We acknowledge and respect the Lək̓ʷəŋən (Songhees and Esquimalt) Peoples on whose territory the university stands, and the Lək̓ʷəŋən and W̱SÁNEĆ Peoples whose historical relationships with the land continue to this day.