2022/11/08 by Aarya Kumar, Kumar, Aarya, Siyu Peng +3
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Coding theory and cryptography #Commutative Algebra and Its Applications #FOS: Mathematics #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.2211.04379
openalex publication_date 2022/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we investigate generalizations of the Mahler-Popkens complexity of integers. Specifically, we generalize to k-th roots of unity, polynomials over the naturals, and the integers mod m. In cyclotomic rings, we establish upper and lower bounds for integer complexity, investigate the complexity of roots of unity using cyclotomic polynomials, and introduce a concept of "minimality.'' In polynomials over the naturals, we establish bounds on the sizes of complexity classes and establish a trivial but useful upper bound. In the integers mod m, we introduce the concepts of "inefficiency'', "resilience'', and "modified complexity.'' In hopes of improving the upper bound on the complexity of the most complex element mod m, we also use graphs to visualize complexity in these finite rings.