Integer Complexity Generalizations in Various Rings
| Autor: | Kumar, Aarya, Peng, Siyu, Tran, Vincent |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 44 pages, 11 figures, Research Lab from PROMYS |
| Databáze: | arXiv |
| Externí odkaz: |
|