# Integer Complexity Generalizations in Various Rings

Aarya Kumar, Siyu Peng, Vincent Tran

###### Abstract

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.

##  1 Introduction

Integer complexity is a system that attempts to quantify our intuitions on how
‘complex’ a number is.

######  Definition.

The complexity of a number $n$, denoted as $||n||$ is equal to the smallest
number of 1’s needed to write $n$ as an equation using addition and
multiplication.

For example,

$6=(1+1)(1+1+1)$

which implies $||6||\leq 5$. In fact, this is the complexity of 6. Here is
another example for 7.

$7=(1+1)(1+1+1)+1$

Though the following definitions are somewhat pedantic, they are necessary to
reduce ambiguity. We take the definition of expression presented in [4], where
the idea is defined more rigorously.

######  Definition.

An expression refers to a sequence of $x$’s, which are joined together by
$+,\cdot,$ and $()$ in the usual sense.

For example, a valid expression is

$(x+x+x)\cdot(x+x)+x\cdot x\cdot x$

As shorthand, we would write

$3x\cdot 2x+x^{3}$

for the above. Keep in mind that this is merely shorthand and not a valid
expression.

######  Definition.

The representation of a base $k$ is an expression with $x=\zeta_{k}$ which
evaluates to be $n$.

Note that the examples that we’ve provided have $x=1$ and $k=1$.

######  Definition.

A representation is optimal when $||n||$ is equal to the number of $x$’s used
in the expression.

There is some pre-existing literature on the subject, but none has yet
explored the potential of integer complexity in other rings. In this paper, we
will begin by generalizing the idea of integer complexity into cyclotomic
fields. Then, we will investigate integer complexity in polynomial rings, an
application that arises naturally from the definition of an expression.
Finally, we shall look into complexity in the integers mod $m$ and the
integers mod $p$, where $p$ is prime.

Much of this exploration shall consist of establishing upper and lower bounds
on complexity and the size of complexity classes, often by means of Horner’s
method. When investigating complexity in cyclotomic rings, we will
additionally focus on finding some integers $k$ for which $||1||_{k}=k$ in the
$k$th cyclotomic field, and some integers $k$ for which this is not the case.
When dealing with finite (quotients of integers) rings and fields, we will
explore the idea that, by well-ordering, there exists an element(s) with the
largest complexity, and that the complexity of elements changes depending on
what unit is used as a base in place of 1.

##  2 Cyclotomic Fields

As one studies the complexity of some integers, they will sometimes wish that
they could subtract. For example, Mersenne primes would generally have a much
smaller complexity if one could subtract 1. The logical next step in integer
complexity would be to use roots of unity. For instance when we let
$k=\zeta_{2}=-1$, we can now subtract and add. However, note that
$||1||_{2}=k$ as we change $k$. Through numerical calculation, we have
observed that most numbers increase in complexity while others decrease.

######  Definition.

While we are working with cyclotomic fields, let $\zeta_{k}=e^{2\pi i/k}$. The
complexity of $n$ with base $\zeta_{k}$ is denoted as $||n||_{k}$.

We are familiar with $\zeta_{4}$, also known as $i$. Let us consider integer
complexity when we use $i$ as the base. We have easy access to subtraction
with $i^{2}$. However in other $k$, subtracting may not be so easy, but is
still doable.

Figure 1: A plot of the real component ($x$) and imaginary component ($y$) vs.
the complexity of that complex number (on the $z$ axis) using $\zeta_{4}$.

######  Proposition 2.1.

We can construct a representation of all elements of $\mathbb{Z}[\zeta_{k}]$
with $\zeta_{k}$.

###### Proof.

We know we can represent any element $a\in\mathbb{N}[\zeta_{k}]$ as
$a_{0}+a_{1}\zeta+a_{2}\zeta^{2}+\cdots$. For some arbitrary positive integer
$j$, we can say

$-\zeta_{k}^{j}=\sum_{\begin{subarray}{c}\ell\in\mathbb{Z}\\\ 0\leq\ell<k\\\
\ell\neq j\end{subarray}}^{k}\zeta_{k}^{\ell}$

Thus we can obtain any negative coefficients for each root of unity through
the repeated addition of this above representation. We can represent 0 by
summing all the roots of unities. ∎

We can replace the $1$’s in the $k=1$ representation of a natural number with
$\zeta_{k}^{k}$ and find that $\forall n\in\mathbb{N},||n||_{k}\leq k||n||$.
In most cases, this is not the optimal representation. To create bounds for
$k\geq 1$, we take inspiration from pre-existing bounds of integer complexity
when $k=1$ and attempt to generalize them for higher $k$.

######  Lemma 2.2.

Let $f(x)$ be an arbitrary expression that uses the input as the symbol. Then,
for all $f,|f(\zeta_{k})|\leq f(1)$.

###### Proof.

Let $f(x),g(x)$ be an arbitrary expression that uses the input as the symbol.
For example, if $f(x)=x(x+x)$, then $f(1)=1(1+1)$ and $f(i)=i(i+i)$. We prove
by induction. As our inductive step, consider $f(1),|f(\zeta_{k})|$, and
$|g(\zeta_{k})|$. If $|f(\zeta_{k})|\leq f(1)$ and $|g(\zeta_{k})|\leq g(1)$,
Then, we can see that

$|f(\zeta_{k})+g(\zeta_{k})|\leq f(1)+g(1)$

which we know is true, considering the geometry of vector addition in the
complex plane/the triangle inequality, and note that

$|f(\zeta_{k})g(\zeta_{k})|\leq f(1)g(1)$

which is also true since magnitude is multiplicative.

Then for our base case, we can check that for $f(x)=g(x)=x$, that
$|f(\zeta_{k})|=1=f(1)$ and $|f(\zeta_{k})+g(\zeta_{k})|=|2\zeta_{k}|$, which
satisfies our hypotheses. We can build all other expressions from these, by
definition. Thus, by induction, we can say that for all functions $f$,

$|f(\zeta_{k})|\leq f(1)$

∎

######  Theorem 2.3.

$3\log_{3}|n|\leq||n||_{k}$

###### Proof.

We know that the lower bound is true for when $k=1$ by Altman, [1]. This is
obtained from the representation

$n=(1+1+1)(1+1+1)\cdots$

having the largest value for its complexity.

Let $g(x)=(x+x+x)(x+x+x)\cdots$. Since we know that $g(1)$ has the largest
magnitude for its complexity, then we can say that any other expression $f(x)$
with the same complexity as $g(x)$ satisfies that $g(1)\geq f(1)$.

We can see that $|g(\zeta_{k})|=g(1),\forall k\in\mathbb{N}.$ By Lemma 2.2,
for all expressions $f$, we have $|f(\zeta_{k})|\leq f(1).$ But by Altman,
$f(1)\leq g(1)=|g(\zeta_{k})|$, so by transitivity, we can say that
$|f(\zeta_{k})|\leq|g(\zeta_{k})|$. Then, for $n$ with complexity $k$, we have
$|n|\leq 3^{\frac{k}{3}}$. This implies that $3\log_{3}|n|\leq||n||_{k}$.
Thus, we obtain our lower bound. ∎

######  Remark.

Note that as in the $k=1$ case, this lower bound is the best lower log bound
possible, as the lower bound is obtained by $g(\zeta_{k})=3^{k}=g(1)$. Also
note that it is obtained infinitely often, by $3^{ki}\,\forall
i\in\mathbb{N}$.

######  Proposition 2.4.

$||n||_{k}\leq\frac{k(k+5)}{2}\cdot\left\lceil\frac{\lceil\log_{2}n\rceil+1}{k}\right\rceil$

###### Proof.

Again, we take inspiration from the proof of the upper bound by Altman, [1],
which involves representing a natural number $n$ in binary. We use Horner’s
method. For an example of an application of this method, see Altman, [1].
Then, we can see that the ‘worst case scenario’ would arise in the case when
$n$ in binary is represented as a string of all 1’s. We can represent that in
$k=1$ as

$(((1+1)+1)(1+1)+1)(1+1)+\ldots$

It is tempting to generalize this to all $k$’s by replacing the 1’s with
$\zeta_{k}$. However, we run into a big problem. Consider $k=4$, so
$\zeta_{4}=i$. Then, consider the following:

$\displaystyle((i+i)+i)(i+i)+i$ $\displaystyle=$ $\displaystyle((2i)+i)(2i)+i$
$\displaystyle=$ $\displaystyle(3i)(2i)+i$ $\displaystyle=$
$\displaystyle-6+i$

To salvage this system, we posit the following representation:

$(((((x+x)+x)(x+x)+x^{2})(x+x)+x^{3})\ldots(x+x)+x^{k})(x+x)+x^{1}+\ldots$ (1)

This way, we do not run into the problem of adding different powers of
$\zeta_{k}$. Note that because $x^{k+c}=x^{c}$ when $x=\zeta_{k}$, we can
consider the binary expansion in groups of $k$ $x$’s. Then we can use the sum
of an arithmetic sequence to see that to get each group of $k$ digits, we need
$\frac{k(k+5)}{2}$ number of $x$’s.

Recall that there are at most
$\left\lceil\frac{\lceil\log_{2}(n)\rceil+2}{k}\right\rceil$ groups of $k$
digits. Thus it will take at most
$\left\lceil\frac{\lceil\log_{2}(n)\rceil+1}{k}\right\rceil\times\frac{k(k+5)}{2}$
$x$’s, our proposition. ∎

We can attempt to use a similar method of generalizing base expansions to find
an upper bound for the complexity of any element of $\mathbb{Z}[\zeta_{k}]$,
not just natural numbers. We shall start by finding such a bound in the
Gaussian Integers.

######  Proposition 2.5.

For all $\alpha\in\mathbb{Z}[i]$,

$||z||_{4}\leq 7\log_{2}|z|+5$

###### Proof.

This can be found by writing $\alpha$ in base $2i$, which has a complexity of
2. Meanwhile, the remainder with the maximum complexity is $1-i$, which has a
complexity of 5.

Every time we divide $\alpha$ by 2i, we can get a quotient with a magnitude
that is at most half of the magnitude of $\alpha$. Therefore, we can divide no
more than $\log_{2}|\alpha|$ times. Meanwhile, the base $2i$ expansion has at
most $\log_{2}|\alpha|+1$ digits, and each of these digits/remainders has a
maximum complexity of 5. Thus, our base 2i expansion of $\alpha$ will use at
most $2\log_{2}|\alpha|+5(\log_{2}|\alpha|+1)=7\log_{2}|\alpha|+5$. ∎

######  Remark.

It should be noted that although there are associates of $1-i$ that have less
complexity (for example, $||i-1||=3$), it is necessary to consider all
associates. For example, if we are trying to divide $1-5i$ by $2i$, we could
write it as $-2(2i)+(1-i)$, but we could also write it as $(-3-i)(2i)+(i-1)$.
Even though the latter option has a less complex remainder, we would still
have to utilize the former instead because we need our quotient to have a
magnitude less than half of the magnitude of $1-5i$ for this technique to
work.

Unfortunately, if we attempt to use this method to create an upper bound for
all elements of $\mathbb{Z}[\zeta_{k}]$, we run into a problem in that a
division algorithm does not exist for most cyclotomic rings, since the
remainder could be ‘larger’ than the divisor. Furthermore, it is possible to
add units in cyclotomic rings to get elements with magnitudes less than 1, so
it is difficult to find a most complex remainder for a given element.
Therefore, we shall define an alternative division algorithm in
$\mathbb{Z}[\zeta_{k}]$. For the purposes of this proof, we will be using
$b\zeta_{k}$, for some $b\in\mathbb{N}$, as the divisor and define this
alternative division algorithm only for non-multiplex numbers (see Definition
Definition).

More rigorously, for
$n\in\mathbb{Z}[\zeta_{k}],n=a_{1}\zeta_{k}+a_{2}\zeta_{k}^{2}+\ldots+a_{k}\zeta_{k}^{k}$.
Then, dividing by $b\zeta_{k}$ will give us a quotient of:

$q=\sum_{i=1}^{k}\left\lfloor\frac{a_{i}}{b}\right\rfloor\zeta_{k}^{i-1}$

Then, the remainder would be the difference between $n$ and $q\cdot
b\zeta_{k}$. It is okay for the magnitude of the remainder to be more than the
divisor; what is important is that the coefficient for each power of
$\zeta_{k}$ in the remainder is less than $b$.

Using this, we can create an alternative Euclidean algorithm to reduce $n$. We
can see that this algorithm terminates by applying the well-ordering principle
on the constants.

######  Observation.

We acknowledge that terms in the expansion
$n=a_{1}\zeta_{k}+a_{2}\zeta_{k}^{2}+\ldots+a_{k}\zeta_{k}^{k}$ may cancel
each other out in certain places. However, this is still a valid
representation, as the coefficients may be 0.

######  Theorem 2.6.

For any element of $n\in\mathbb{Z}[\zeta_{k}]$ and for $a_{i}\in\mathbb{N}$,
we can express $n$ as:

$n=a_{1}\zeta_{k}+a_{2}\zeta_{k}^{2}+\ldots+a_{k}\zeta_{k}^{k}$

Then the upper bound for the complexity of $n$ is:

$||n||_{k}\leq(2k-\frac{k}{p}+1)(\log_{2}|a_{m}|+1)-2$

where $p$ is the smallest prime divisor of $k$ and
$a_{m}=\max(a_{1},a_{2},\ldots,a_{k})$.

###### Proof.

Consider applying the alternative Euclidean algorithm to $n$ with divisor
$2\zeta_{k}$. For some $b_{i},r_{i}\in\mathbb{Z}[\zeta_{k}]$ satisfying the
conditions of our alternative division algorithm, we have:

$\displaystyle n$ $\displaystyle=2\zeta_{k}\cdot b_{1}+r_{1}$ $\displaystyle
b_{1}$ $\displaystyle=2\zeta_{k}\cdot b_{2}+r_{2}$ $\displaystyle\vdots$
$\displaystyle b_{s-1}$ $\displaystyle=2\zeta_{k}\cdot b_{s}+r_{s}$
$\displaystyle b_{s}$ $\displaystyle=2\zeta_{k}\cdot 0+b_{s}$

Since the reduction ends when all the coefficients of $\zeta_{k}^{i}$ of
$b_{s}$ are less than 2, we can conclude that we will need $\log_{2}a_{m}+1$
such equations.

We can see that we can write

$n=2\zeta_{k}(\ldots 2\zeta_{k}(2\zeta_{k}(2\zeta_{k}\cdot
b_{s}+r_{s})+r_{s-1})+r_{s-2})\ldots)+r_{1}$

Each time we multiply by $2\zeta_{k}$, we also add by the remainder, $r_{i}$.
The coefficients for the roots of unity must be 1 or 0. Since we are looking
for the ‘worst case scenario’, we want to maximize the number of $\zeta_{k}$’s
involved. However, if we sum all the roots of unity, they will cancel and we
will end up with 0. Thus there is a limit to the number of roots of unity that
we can include.

Let $p$ be the smallest prime divisor of $k$. Consider taking the powers mod
$p$. Then, there would be $\frac{k}{p}$ elements in each residue class modulo
$p$. If we sum every element of each residue class, we will obtain 0.
Therefore, we must leave out one of these elements. Then, the maximal
complexity we can obtain for $b_{s}$ (established later with the
representation with Horner’s algorithm, and note that this can obtain all
possible most complex remainders) would be if we removed the first element in
each residue class, namely $\zeta_{k},\zeta_{k}^{2},\ldots,\zeta_{k}^{k/p}$.
We can see that once we remove these $p-1$ roots of unity, no other
cancellation will occur.

Just representing this sum of roots of unity by multiplying $\zeta_{k}$ many
times itself is inefficient. Instead, we can represent $r_{i}$ with Horner’s
algorithm again, namely

$r_{i}=\zeta_{k}^{\frac{k}{p}}(\zeta_{k}+\zeta_{k}(\zeta_{k}+\zeta_{k}(\ldots+\zeta_{k}(\zeta_{k}+\zeta_{k}\zeta_{k})))),$

which uses $(k-\frac{k}{p}-1)2+\frac{k}{p}+1=2k-\frac{k}{p}-1$. So, at each
reduction (of which there will be $\log_{2}a_{m}+1-1$), we will need
$(2k-\frac{k}{p}-1)+2$ $\zeta_{k}$’s, in addition to another
$(2k-\frac{k}{p}-1)$ $\zeta_{k}$’s for the final coefficient. Thus, we are
able to represent any element $n\in\mathbb{Z}[\zeta_{k}]$ with at most
$(2k-\frac{k}{p}+1)(\log_{2}|a_{m}|+1)-2$ elements, simplifying these terms. ∎

Trivially, we can also see the following corollary for prime values of $k$:

######  Corollary 2.6.1.

For any element of $n\in\mathbb{Z}[\zeta_{k}]$ such that $k$ is prime, and for
$a_{i}\in\mathbb{N}$, the upper bound for the complexity of $n$ is:

$||n||_{k}\leq 2k(\log_{2}|a_{m}|+1)-2$

where $a_{m}$ is the $\max(a_{1},a_{2},\ldots,a_{k})$.

######  Remark.

In the case where $k=4$, using our bound from alternative division, which
turns out to be $7\log_{2}|a_{m}|+5$, is more effective than using the earlier
bound based on the magnitude: $a_{m}$ is always at most equal to the magnitude
of a Gaussian Integer, and in most cases, it is smaller. This is because it is
impossible to add multiples of distinct roots of unity in a non-reducible
manner in the Gaussian Integers such that their sum has a smaller magnitude
than one of the components. The same is also true for $k=2,k=3$, and,
trivially, $k=1$, but it is not true for larger values of $k$. This can be
proven using the law of cosines, noting that the smallest angle between
elements of $\mathbb{Z}[\zeta_{k}]$ on the complex plane is $\frac{2\pi}{k}$.
In these cases, it would have been more valuable to have a magnitude-based
upper bound.

Using the idea of multiplying and adding to construct a representation for
$n$, we attempt to create a tighter bound for the naturals. We take
inspiration from Zelinsky’s work in normal integer complexity and employ a
method called “switching bases.”

Figure 2: A plot of the complexity with $k=4$ ($y$) vs a natural number ($x$)
up to complexity 18. The weak upper bound is shown in red, the stronger upper
bound (inspired by Zelinsky) in green, and the lower bound in blue.

######  Proposition 2.7.

$||n||_{k}\leq\frac{k(k-1)}{2}\cdot\left\lceil\frac{\lceil\log_{2}n\rceil+1}{k}\right\rceil+\dfrac{5}{\ln(2)+\frac{1}{2}\ln(3)}\ln(n)$

###### Proof.

We attempt to generalize Zelinsky’s ‘switching bases’ method for higher $k$.
This method still relies on expressing the number in a base representation,
but instead of using only $2\zeta_{k}$ as a base, we switch bases when it is
optimal. Let us use $2\zeta_{k},3\zeta_{k},5\zeta_{k}$. We claim that their
complexities are 2, 3, and 5 respectively.

We can see that $||2\zeta_{k}||=2$ and $||3\zeta_{k}||=3$, which can be
verified quickly since the only numbers of complexity 2 are $2\zeta_{k}$ and
$\zeta_{k}^{2}$. For $5\zeta_{k}$, we can quickly check that the magnitude of
anything with complexity 4 or less does not exceed 4.

In order to create an analogue to the natural numbers, we need to make sure
that in the base expression, the remainder combines with the correct power of
$\zeta_{k}$. Consider the base 2 representation of $n$. This expression will
be the upper bound for the number of digits in the base $b$ expansion, thereby
providing an upper bound for the number of times we need to account for
different powers of $\zeta_{k}$ not simplifying into the same power of
$\zeta_{k}$. This is analogous to how the powers of $x$ may not combine with
the other addend in Equation 1. There are $\lceil\log_{2}n\rceil+1$ digits
total. Then, we partition the digits into groups of length $k$, where we group
$a_{1}\zeta_{k}+a_{2}\zeta_{k}^{2}+\ldots+a_{k-1}\zeta_{k}^{k-1}+a_{k}$
together. We count the number of extra $\zeta_{k}$’s we will have to multiply
to the remainder in order to add the coefficients, which is
$\frac{k(k-1)}{2}$. This process is similar to the proof of Proposition 2.4.
Let us momentarily ignore the $2\zeta_{k}$ that we multiply at each step. Thus
the upper bound for the number of extra $\zeta_{k}$’s needed is
$\frac{k(k-1)}{2}\left\lceil\frac{\lceil\log_{2}n\rceil+1}{k}\right\rceil$.

Now to account for the complexity needed to do a bitshift in the multibase
representation of $n$, we can simply consider the expression of $n$ as if it
was in $k=1$, as we have accounted for extra powers of $\zeta_{k}$. Thus we
add $\frac{5}{\ln(2)+\frac{1}{2}\ln(n)}\ln(n)$, as obtained by Zelinsky in his
currently unpublished paper (used with permission) [7]. ∎

######  Proposition 2.8.

$||1||_{k}=k$ for prime $k$.

###### Proof.

Suppose we have an expression $f(x)$ such that $f(\zeta_{k})=1$. Then
$\zeta_{k}$ is a root of the polynomial $f(x)-1$. Since $f(x)$ is an
expression, it has natural (a subset of the integers) coefficients and is
divisible by $x$ (so the constant coefficient of $f(x)-1$ is $-1$). The
minimal polynomial of an algebraic integer $\alpha$ divides all polynomials
over $\mathbb{Z}$ with $\alpha$ as a root ([5]), so the minimal polynomial of
$\zeta_{k}$ must divide $f(x)-1$.

Now consider when $k$ is prime. Then let $k=p$, where $p$ is prime. Then the
minimal polynomial of $\zeta_{p}$ is the $p$-th cyclotomic polynomial, which
is $x^{p-1}+x^{p-2}+\cdots+1$, by [6]. Thus, for some polynomial
$h\in\mathbb{Z}[x]$, we have:

$(x^{p-1}+x^{p-2}+\cdots+1)h=f(x)-1.$

Then note that if $f$ has complexity at most $p$, then the largest degree of
$f(x)$ is at most $p$, so $\deg h\leq 1$. But the degree of $h$ can’t be 0,
because then $f(x)$ would equal $-x^{p-1}-x^{p-2}\cdots$, which isn’t an
expression 111 Note the parallels between this proof and the other proof: they
both used the fact that a representation of 1 (and in this case all rationals)
using $\zeta_{p}$’s must have equal coefficients of the primitive root’s
powers. . But, since the constant term must be $-1$ after the multiplication
(and $f(x)$ has natural coefficients), $h$ has to be $ax-1$ for
$a\in\mathbb{N}$. Thus $f(x)-1=x^{p}-1+(a-1)(x^{p-1}+\ldots)\implies
f(x)=x^{p}+(a-1)(x^{p-1}+\ldots)$. But then, in order to have a degree of $p$,
there has to be at least $p$ multiplications. Thus the complexity of $f$ is at
least $p$, but the obvious expression has complexity $p$, so $||1||_{k}=k$. ∎

We have also found a second proof for this proposition, inspired by [3].

######  Lemma 2.9.

Let $k$ be prime. Let $g$ be a generator in $\mathbb{Z}/k\mathbb{Z}$. Then if

$S=a_{0}+a_{1}\zeta_{k}^{g}+a_{2}\zeta_{k}^{g^{2}}+\ldots+a_{k-1}\zeta_{k}^{g^{k-1}}=a_{0}+a_{1}\zeta_{k}^{g^{2}}+a_{2}\zeta_{k}^{g^{3}}+\ldots+a_{k-1}\zeta_{k}^{g^{k}},$

then $a_{1}=a_{2}=a_{3}=\ldots=a_{k-1}$, for $a_{i}\in\mathbb{Z}.$

###### Proof.

First, move all terms of the equation to the same side. Then, noting that
$\zeta_{k}^{g^{k}}=\zeta_{k}^{g}$ we have that

$(a_{1}-a_{k-1})\zeta_{k}^{g}+(a_{2}-a1)\zeta_{k}^{g^{2}}+\ldots+(a_{k-1}-a_{k-2})\zeta^{g^{k-1}}=0.$

Since $\\{g,g^{2},\cdots,g^{k-1}\\}=\\{1,2,\cdots,k-1\\}$, we can then reorder
this equation to

$b_{1}+b_{2}\zeta_{k}+b_{3}\zeta_{k}^{2}+\ldots+b_{k-2}\zeta_{k}^{k-2},$

where each $b_{i}$ is some coefficient of a power of $\zeta_{k}$ from the
equation prior (and note that each $b_{i}$ is a difference of 2 “consecutive”
coefficients $a_{j}$ and $a_{j+1}$ where there is looping around) and from
dividing both sides by $\zeta_{k}$. Thus $\zeta_{k}$ is a root of
$g(x)=b_{1}+b_{2}x+b_{3}x^{2}+\ldots+b_{k-2}x^{k-2}$.

Then by [5], $\phi_{k}$ divides $g(x)$. If $g\neq 0$, a contradiction arises
as $\deg g<\deg\phi_{k}$. Thus $g=0$. Since the coefficients of $g$ are
pairwise differences of “consecutive” coefficients of powers of $\zeta_{k}$ in
$S$ and each coefficient of $g$ is 0 (as $g=0$), all the coefficients $a_{i}$
for $k\geq i\geq 1$ are equal to each other. ∎

Now the alternate proof that $||1||_{k}=k$ for prime $k$ begins.

###### Proof.

Let $k$ be prime. Let $g$ be a generator in $\mathbb{Z}/k\mathbb{Z}$. Suppose
$||1||_{k}<k$. Then there will be no $\zeta_{k}^{k}$’s in the expanded
representation for $1$. Let the representation with all multiplication
expanded be
$a_{1}\zeta_{k}^{g}+a_{2}\zeta_{k}^{2}+\ldots+a_{k-1}\zeta_{k}^{g^{k-1}}$,
noting that $\\{g,g^{2},\cdots,g^{k-1}\\}=\\{1,2,\cdots,k-1\\}.$

Now consider the mapping $\zeta\rightarrow\zeta^{g}$ (which is a Galois
automorphism, thus taking $1\rightarrow 1$).

Then

$1=a_{1}\zeta_{k}^{g}+a_{2}\zeta_{k}^{g^{2}}+\ldots+a_{k-1}\zeta_{k}^{g^{k-1}}=a_{1}\zeta_{k}^{g^{2}}+a_{2}\zeta_{k}^{g^{3}}+\ldots+a_{k-1}\zeta_{k}^{g^{k}}.$

By Lemma 2.9, $a_{1}=a_{2}=\cdots=a_{k-1}$. But since this is an expanded
representation, all the coefficients are non-negative. If they are 0, then we
get a contradiction $(1=0)$. If they were positive, then since
$\zeta_{k}+\zeta_{k}^{2}+\ldots+\zeta_{k}^{k-1}=-1$, we have have that
$1=-a_{1}<0$, a contradiction††footnotemark: . ∎

######  Remark.

Using Galois automorphisms, we can trivially see that for an optimal
representation of an integer, that representation is also optimal if we used
other primitive roots of unity instead as the base. Furthermore, we can
describe exactly what happens to the number represented if we switch the base
to a different primitive root of unity.

######  Proposition 2.10.

$||1||_{k}=k$ for $k=2p$.

###### Proof.

Note that $j=1$ in this case (building on the idea from the proof of 2.12. Now
suppose that $||1||_{k}<k$. Then by Proposition 2.12, $g_{p-1}\geq 1$. Thus,
since $g_{p}=0$ by Proposition 2.12, the degree of $xf$ (the expression for
$1$ is at least $2p-1$ if we expand the multiplications). Thus there are at
least $2p-1$ multiplications to get such a degree. Therefore $||1||_{k}\geq
2p-1=k-1$.

Since $||1||_{k}\leq k$, if $||1||_{k}<k$, $||1||_{k}=k-1$. But since the
degree of the expression for 1 is at least $k-1$, the only element st the
degree is at least $k-1$ and complexity of $k-1$ is $x^{k-1}$. This leads to a
contradiction, as clearly $\zeta_{k}^{k-1}\neq 1$.

∎

######  Theorem 2.11.

$||1||_{k}=k$ for prime power $k$.

###### Proof.

Let $k=p^{m+1}$ for $p$ prime and $m\in\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$.
Furthermore, let $\mathbb{N}_{0}[x]$ be the set of polynomials with
coefficients in $\mathbb{N}_{0}$. As before, the optimal expression for $1$
with $\zeta_{k}$ as a base implies that $\zeta_{k}$ is a root of $xf-1$, for
$f\in\mathbb{Z}[x]$. Then, since $xf-1\in\mathbb{Z}[x],\phi_{k}|xf-1$ ([5]),
where $\phi_{k}$ is the $k$-th cyclotomic polynomial (which just as a
remainder, $k=p^{m+1}$).

Thus there exists $g\in\mathbb{Q}[x]$ such that $\phi_{k}g=xf-1$. It is well
known that

$\phi_{k}=\phi_{p^{m+1}}=1+x^{p^{m}}+x^{2p^{m}}+\ldots+x^{(p-1)p^{m}};$

therefore, the constant term is $1$, so the constant term of $g$ is $-1$.
Thusly we can write $g=xg^{\prime}-1$ for $g^{\prime}\in\mathbb{Q}[x]$. Then
let $g^{\prime}=g_{0}+g_{1}x+g_{2}x^{2}+\ldots,\,g_{i}\in\mathbb{Q}$. Note
that $\deg g^{\prime}\leq p^{m}-1$, since otherwise, $\deg xf\geq p^{m+1}$,
and then there would be at least $p^{m+1}$ multiplications, which has a
complexity greater than or equal to $p^{m+1}$ (and thus no counter-example to
the claim can have this condition). Thus

$\displaystyle\phi_{k}(xg^{\prime}-1)=$
$\displaystyle\,x\phi_{k}g^{\prime}-\phi_{k}$
$\displaystyle=x(1+x^{p^{m}}+x^{2p^{m}}+\ldots+x^{(p-1)p^{m}})(g_{0}+g_{1}x+g_{2}x^{2}+\ldots)$
$\displaystyle+-(1+x^{p^{m}}+x^{2p^{m}}+\ldots+x^{(p-1)p^{m}}).$

Then,

$xf=x(1+x^{p^{m}}+x^{2p^{m}}+\ldots+x^{(p-1)p^{m}})(g_{0}+g_{1}x+g_{2}x^{2}+\ldots)-x^{p^{m}}-x^{2p^{m}}-\ldots.$

Clearly, $xf\in\mathbb{N}_{0}[x]$, since its an expression. Thus all the
coefficients of the RHS should be in $\mathbb{N}_{0}$ once simplified. Thus
the coefficient of $x^{p^{m}}$ in the first/left term has to be greater than
or equal to 1 (to account for the first subtraction). We find that this
coefficient is $g_{p^{m}-1}$.

Thus $g^{\prime}=x^{p^{m}-1}+h,h\in\mathbb{Q}[x],\deg h\leq p^{m}-1$ and the
coefficient of $x^{p^{m}-1}$ in $h$ is non-negative. Then

$\displaystyle\phi_{k}(xg^{\prime}-1)$
$\displaystyle=\phi_{k}(x^{p^{m}}-1+xh)$
$\displaystyle=\phi_{p^{m+1}}\left(\prod_{a|p^{m}}(\phi_{a})+xh\right)$

(This last step uses a well-known property of cyclotomic polynomials, [6]).

$\displaystyle\phi_{k}\left(\prod_{a|p^{m}}(\phi_{a})+xh\right)$
$\displaystyle=x^{p^{m+1}}-1+xh\phi_{p^{m+1}}$ $\displaystyle=xf-1$
$\displaystyle\iff xf=x^{p^{m+1}}+xh\phi_{p^{m+1}}$

Thus the expression for $1$ using $\zeta_{p^{m+1}}$’s has to have a
$\zeta_{p^{m+1}}^{p^{m+1}}$ term in it (as the coefficient of $x^{p{m+1}}$ is
$g_{p^{m}-1}$, and this is positive) after all multiplication is distributed.
Then suppose there is an expression of complexity less than $p^{m+1}$ for 1.
Then the highest power of $\zeta_{p^{m+1}}$ explicitly in the expression is
obviously less than $p^{m+1}$. But the condition shown before contradicts
this, since this expression won’t explicitly have a
$\zeta_{p^{m+1}}^{p^{m+1}}$ term in it. ∎

######  Remark.

Considering polynomials not just over integers but over the cyclotomic rings
might be fruitful in expanding the technique above.

######  Remark.

It may be possible to generalize this technique to the other powers of
$\zeta_{k}$ by considering the expression for $\zeta_{k}^{d}$ for $1\leq d<k$
to be $xf$, and $\zeta_{k}$ to be a root of $xf-x^{d}$ instead of subtracting
$n$.

######  Proposition 2.12.

If $||1||_{k}<k$, then

$\displaystyle g_{pj+j-1}$ $\displaystyle=0,$ (2) $\displaystyle g_{j-1}$
$\displaystyle\geq 0,$ (3) $\displaystyle g_{wj-1}$
$\displaystyle\in\mathbb{N}_{0}$ $\displaystyle\forall w\in\mathbb{N},w\leq
p-1,\text{ and}$ (4) $\displaystyle g_{pj-1}$ $\displaystyle\in\mathbb{N},$
(5)

where $xg^{\prime}-1=\frac{xf-1}{\phi_{k}}$, $g_{a}$ is the coefficient of
$x^{a}$ in $g^{\prime}$, $k=2^{a}p^{b}$ for natural $a,b$, and
$j=2^{a-1}p^{b-1}$ and $g^{\prime}$ satisfies this system of inequalities:

$\begin{split}g_{j-1}+1&\geq 0\\\ g_{2j-1}-g_{j-1}-1&\geq 0\\\
g_{3j-1}-g_{2j-1}+g_{j-1}+1&\geq 0\\\ \vdots\\\ g_{(p-1)j}-g_{(p-2)j}+\cdots-
g_{j-1}-1&\geq 0\\\ g_{pj-1}-g_{(p-1)j}+\cdots+g_{j-1}&\geq 0\\\
-g_{pj-1}+\cdots+g_{2j-1}&\geq 0\end{split}$ (6)

###### Proof.

The following work is from a (failed) attempt to generalize the previous proof
to $k$ a power of 2 times an odd prime power and a salvage to get the
proposition above. The key step in the last proof was to find a condition
necessary for $g\in\mathbb{Q}[x]$, one that would guarantee that
$\phi_{k}g=x^{k}-1$. So if

$\displaystyle(xg^{\prime}-1)\phi_{k}$ $\displaystyle=xf-1$
$\displaystyle=x^{k}-1,$

then

$\displaystyle xg^{\prime}-1$ $\displaystyle=\frac{x^{k}-1}{\phi_{k}}$
$\displaystyle=\prod_{\begin{subarray}{c}c\mid k\\\ c\neq
k\end{subarray}}\phi_{c}$
$\displaystyle=\prod_{d^{\prime}|p^{b}}(\phi_{d^{\prime}})\prod_{d|p^{b}}(\phi_{2d})\prod_{d|p^{b}}(\phi_{4d})\ldots\prod_{d|p^{b-1}}(\phi_{2^{a}d})$

First we consider when $d=1$ in each of the products above. We can turn
$\phi_{2}(x)$ to $-\phi_{1}(-x)$. Thus the product turns into

$\prod_{d^{\prime}|p^{b}}(\phi_{d^{\prime}})\left(-\phi_{1}(-x)\prod_{\begin{subarray}{c}d|p^{b}\\\
d\neq
1\end{subarray}}(\phi_{2d})\right)\left(-\phi_{1}(-x)\prod_{\begin{subarray}{c}d|p^{b}\\\
d\neq
1\end{subarray}}(\phi_{4d})\right)\ldots\left(-\phi_{1}(-x)\prod_{\begin{subarray}{c}d|p^{b-1}\\\
d\neq 1\end{subarray}}(\phi_{2^{a-1}d})\right).$

Since the remaining $d>2$, we can apply the identity that
$\phi_{2\ell}(x)=\phi_{\ell}(x^{2}),\ell\in\mathbb{N}$ [6] repeatedly to
reduce all powers of 2 times $d$ to $2d$, resulting in

$\prod_{d^{\prime}|p^{b}}(\phi_{d^{\prime}})\left(-\phi_{1}(-x)\prod_{\begin{subarray}{c}d|p^{b}\\\
d\neq
1\end{subarray}}(\phi_{2d})\right)\left(-\phi_{1}(-x)\prod_{\begin{subarray}{c}d|p^{b}\\\
d\neq
1\end{subarray}}(\phi_{2d}(x^{2}))\right)\ldots\left(-\phi_{1}(-x)\prod_{\begin{subarray}{c}d|p^{b-1}\\\
d\neq 1\end{subarray}}(\phi_{2d}(x^{2^{a-1}}))\right).$

Finally, we can convert $\phi_{2d}$ to $\phi_{d}(-x)$ to get

$\left(\prod_{d^{\prime}|p^{b}}(\phi_{d^{\prime}})\right)\left((-1)\prod_{d|p^{b}}(\phi_{d}(-x))\right)\left((-1)\prod_{d|p^{b}}(\phi_{d}(-x^{2}))\right)\ldots\left((-1)\prod_{d|p^{b-1}}(\phi_{d}(-x^{2^{a-1}}))\right).$

Then, noting that $\prod_{d|p^{b}}\phi_{d}(-x^{2^{i}})=(-x^{2^{i}})^{p^{b}}-1$
by the product identity, we can substitute and obtain:

$xg^{\prime}-1=(x^{p^{b}}-1)(x^{p^{b}}+1)((x^{2})^{p^{b}}+1)\ldots((x^{2^{a-1}})^{p^{b-1}}+1).$

Then using the difference of squares factorization (and letting
$j=2^{a-1}p^{b-1}$), we have

$\displaystyle(x^{2^{a-1}p^{b}}-1)(x^{2^{a-1}p^{b-1}}+1)$
$\displaystyle=(x^{pj}-1)(x^{j}+1)$ $\displaystyle=x^{pj+j}+x^{pj}-x^{j}-1$

Hence we want

$xg^{\prime}-1=x^{pj+j}+x^{pj}-x^{j}-1\iff
g^{\prime}=x^{pj+j-1}+x^{pj-1}-x^{j-1},x\neq 0\text{ (trivially not the
case)}.$

Thus the condition that we want for $g^{\prime}$ is the coefficients of
$x^{pj+j-1},x^{pj-1}$ in $g^{\prime}$ are greater than or equal to $1$ and the
coefficient of $x^{j-1}$ is greater than or equal to $-1$. This is sufficient
to show that the optimal expression for $1$ is $x^{k}-1$ since if, for
$h\in\mathbb{Q}[x]$

$g^{\prime}=x^{pj+j-1}+x^{pj-1}-x^{j-1}+h,$

then

$xg^{\prime}-1=x^{pj+j}+x^{pj}-x^{j}-1+hx.$

Hence

$\displaystyle\phi_{k}(x)(xg^{\prime}-1)$
$\displaystyle=(x^{pj+j}+x^{pj}-x^{j}-1+hx)\phi_{k}$
$\displaystyle=x^{k}-1+hx\phi_{k}.$

Thusly $xf=x^{k}+hx\phi_{k}$. Therefore $\zeta_{k}^{k}$ is in the
representation of $1$ after all the multiplication is expanded. Thus at least
$k$ multiplications are required, forcing the complexity of 1 to be greater
than or equal to $k$. Since $\zeta_{k}^{k}=1$, the complexity is in fact $k$.
Thus this condition is all we need to show.

Now to show this condition is true on the coefficients. As before, we know
that

$xf\in\mathbb{N}_{0}[x]\implies\phi_{k}(x)(xg^{\prime}-1)+1\in\mathbb{N}_{0}[x].$

Thus $\phi_{k}(x)xg^{\prime}-\phi_{k}(x)$ have coefficients in
$\mathbb{N}_{0}$. Let $g^{\prime}=g_{0}+g_{1}x+\ldots$ as before. Since
$k=2pj$,

$\displaystyle\phi_{k}$ $\displaystyle=\phi_{p^{b}}(-x^{2^{a-1}})$
$\displaystyle=\phi_{p}(-x^{j})$ $\displaystyle=1-x^{j}+x^{2\cdot j}-x^{3\cdot
j}+\ldots$

Since we subtract $\phi_{k}$, the coefficient of $x^{j}$ in
$\phi_{k}(x)xg^{\prime}$ has to be greater than or equal to $-1$, one of the
conditions we need. Thus $a_{j-1}\geq-1$.

Next distribute the $g^{\prime}$ across $x\phi_{k}$ to obtain

$g^{\prime}x\phi_{k}=xg^{\prime}-x^{j+1}g^{\prime}+x^{2j+1}g^{\prime}-x^{3j+1}g^{\prime}+\ldots.$

Let $n=1+\deg g^{\prime}$. Since the optimal expression for $1$ is going to
have a degree less than or equal to $k=2pj$ (using the obvious expression),
the highest possible degree of $\phi_{k}(x)(xg^{\prime}-1)$ is $(p-1)j+n$,
which is less than or equal to $2pj$.

Thus $n\leq pj+j$.

Now consider finding the coefficients of
$x^{j},x^{2j},x^{3j},\ldots,x^{(p+1)j}$ in
$\phi_{k}(x)(xg^{\prime}-1)-\phi_{k}$. Since these coefficients are in
$\mathbb{N}_{0}$, we get the following system of inequalities:

$\displaystyle g_{j-1}+1$ $\displaystyle\geq 0$ $\displaystyle
g_{2j-1}-g_{j-1}-1$ $\displaystyle\geq 0$ $\displaystyle
g_{3j-1}-g_{2j-1}+g_{j-1}+1$ $\displaystyle\geq 0$ $\displaystyle\vdots$
$\displaystyle g_{(p-1)j}-g_{(p-2)j}+\cdots-g_{j-1}-1$ $\displaystyle\geq 0$
$\displaystyle g_{pj-1}-g_{(p-1)j}+\cdots+g_{j-1}$ $\displaystyle\geq 0$
$\displaystyle g_{pj+j-1}-g_{pj-1}+\cdots+g_{2j-1}$ $\displaystyle\geq 0$

This gives us conditions 6. Adding the third to last and second to last
inequalities, we can see that $g_{pj-1}\geq 1$. We can also note that adding
two adjacent inequalities up to the third to last line shows that for all
$w\in\mathbb{N}$, $w\leq p-1$, $g_{wj-1}\geq 0$.

Now, if the expression for $1$ has a degree less than $k$, then by the
contrapositive, $g_{pj+j-1}\not\geq 1$. Then note that the LHS of each
inequality above is equal to the coefficient of $x^{j},\ldots$. Thus they must
be integers, as they correspond to a coefficient in an expression. This gives
us Equation 4. Since $g_{pj-1}\geq 1$, this gives us Equation 5. Then we can
use induction to conclude that $g_{wj-1}\in\mathbb{Z}\,\forall
w\in\mathbb{N},w\leq p+1$. Then, $g_{pj+j-1}$ is non-negative since it equals
a coefficient of an expression (namely the highest degree one), and it is not
greater than or equal to 1, so $g_{pj+j-1}=0$. This gives us Equation 2. ∎

Note that this proposition provides a sufficient condition for generating
expressions for $1$: we can simply find
$g_{j-1},g_{2j-1},g_{3j-1},\ldots,g_{(p-1)j-1}$ with the conditions in
Proposition 2.12 and let the other coefficients be 0, and we get that
$\phi_{k}(x)\cdot(xg^{\prime}-1)$ corresponds to an expression for 1. For
instance, if $k=6$, we get this system of inequalities:

$\displaystyle g_{0}+1\geq 0$ $\displaystyle g_{1}-g_{0}-1\geq 0$
$\displaystyle g_{2}-g_{1}+g_{0}\geq 0$ $\displaystyle g_{3}-g_{2}+g_{1}\geq
0$

Then if $||1||_{k}<k$, we get this:

$\displaystyle g_{0}+1\geq 0$ $\displaystyle g_{1}-g_{0}-1\geq 0$
$\displaystyle g_{2}-g_{1}+g_{0}\geq 0$ $\displaystyle-g_{2}+g_{1}\geq 0$

Then we can see that $g_{0},g_{1},g_{2}=0,1,1$, among other solutions,
satisfies the system. This corresponds to $xf=x+x^{5}$. This is an expression
for $1$ with $k=6$.

For another example, consider $k=50$. We get this:

$\displaystyle\vdots$ $\displaystyle g_{19}-g_{14}+g_{9}-g_{4}-1$
$\displaystyle\geq 0$ $\displaystyle g_{24}-g_{19}+g_{14}-g_{9}+g_{4}$
$\displaystyle\geq 0$ $\displaystyle-g_{24}+g_{19}-g_{14}+g_{9}$
$\displaystyle\geq 0$

Then note that if $g_{9},g_{14},g_{19},g_{24}=1$ and the rest are 0, we get
that $xf=x^{5}+x^{15}+x^{35}+x^{45}$. This has a complexity less than or equal
to $47<50$, since it can be written as $x^{4}(x+x^{10}(x+x^{20}(x+x^{11})))$.

######  Remark.

In the optimal expression for $n$, we can get a polynomial $g^{\prime}$ as
above, and with some algebra we can get that $g^{\prime}=x^{q^{b-1}-1}$ for
$k=q^{b}$.

As before, if we have an expression $\zeta_{k}f(\zeta_{k})=n$ for
$f\in\mathbb{N}_{0}[x]$, then $\phi_{k}\mid xf-n$. Thus $\exists
g\in\mathbb{Q}[x]$ such that $\phi_{k}(x)(xg-n)=xf-n$. Then we note that
$\phi_{q^{b}}=\sum_{0\leq a\leq p-1}x^{aq^{b-1}}$, and let
$g=\sum_{i=0}g_{i}x^{i}$. Then from distributing and equating to $xf$, we can
see that $n+x\phi_{k}(x)g-n\phi_{k}\in\mathbb{N}_{0}[x]$. Substituting (and
doing a little cancellation), we get

$x\left(\sum_{0\leq a\leq
p-1}x^{aq^{b-1}}\right)\sum_{i=0}g_{i}x^{i}-n\sum_{1\leq a\leq
p-1}x^{aq^{b-1}}.$

Doing more distributing, we get

$\sum_{0\leq a\leq p-1}\sum_{i=0}g_{i}x^{1+aq^{b-1}+i}-n\sum_{1\leq a\leq
p-1}x^{aq^{b-1}}.$

Then the coefficient of $x^{q^{b-1}}$ in the first addend has to be greater
than or equal to $n$ for the polynomial to be in $\mathbb{N}_{0}[x]$. Thus
$g_{q^{b-1}-1}\geq n$.

######  Corollary 2.12.1.

The above remark fairly immediately implies that $||n||_{q^{b}}\geq q^{b}$
based on degree analysis.

######  Remark.

By applying a similar technique to $k=1$ of keeping track of the coefficients
and forcing them to be in the naturals, we can easily see that (although note
that $nx=n$ in this case, there is no subtraction, and a sum of
$x+x^{2}+\ldots+x^{n}=n$ in this case as well, forcing the degree of $xf$ to
be $\leq n$).

$n\geq g_{0}\geq g_{1}\geq g_{2}\ldots g_{n}\geq 0.$

######  Proposition 2.13.

We originally had the conjecture that for all $a,k\in\mathbb{N},a\leq k$,

$||\zeta_{k}^{a}||_{k}=a.$

But this turns out to be false.

Though this seems to be correct intuitively, there seems to be increasingly
more counterexamples as $k$ increases in the number of distinct prime factors
(since cyclotomic polynomials underline the structure of the expression and
having more factors makes them messier). A counterexample is $||1||_{12}\leq
11$ if we consider $(\zeta_{12}^{9}+\zeta_{12})\zeta_{12}=1$.

######  Proposition 2.14.

$||\zeta_{k}^{a}||_{k}=a$ for $a\leq\frac{k}{2}+1$.

###### Proof.

We will use induction. First we assume that $\forall b\in\mathbb{N},b\leq a$
for a fixed natural $a$ with our condition, the vector in the complex plane
with the largest angle and complexity $b$ is $e^{2\pi ib/k}$. We can see that
for $a=1$, this is true.

Then, we can show this is true for $a+1$ through contradiction. Suppose that
there was a vector with an angle greater than $\frac{2\pi i(a+1)}{k}$ with
complexity $a+1$, call it $\alpha$. Then, the final operation performed must
be a multiplication, since adding two vectors results in a vector with an
angle between the addend’s angles and the angle between the two vectors is
less than $\pi$ radians, as we can’t get a vector with an angle less than
$\frac{2\pi i}{k}$ (multiplication can only increase the angle; angle addition
can also only produce a vector with an angle larger than the smallest angle of
these addends).

Thus let $\alpha=\beta\gamma$. Since multiplication adds angles,
$\arg\beta+\arg\gamma>\frac{2\pi(a+1)}{k}$. Let $b=||\beta||_{k}$ and
$c=||\gamma||_{k}$. Note that $b+c=a+1$ since $\alpha=\beta\gamma$ in its
optimal expression. Thus the largest angles that $\beta$ and $\gamma$ can have
are $\frac{2\pi b}{k}$ and $\frac{2\pi c}{k}$ respectively. This leads to a
contradiction as $\arg\alpha=\arg\beta+\arg\gamma=\frac{2\pi(b+c)}{k}$ and
$b+c=a+1$. ∎

######  Remark.

We can also get $a=\lfloor\frac{k}{2}\rfloor+2$ by considering that two
vectors must once again add to have an angle of $\frac{2\pi ia}{k}$, but there
are no vectors with complexity less than $a$ with an angle of $\pi$ between it
and $\zeta_{k}$ going counter-clockwise from $\zeta_{k}$.

######  Proposition 2.15.

If $k$ is even, $||0||_{k}=\frac{k}{2}+2$.

###### Proof.

Clearly, the last operation in the optimal representation for $0$ isn’t
multiplication. Thus there must be at least two vectors that add up to 0 in
the representation of 0. Clearly, these vectors aren’t all in quadrant 1 or 2
(or on the $x$-axis, unless $k=2$). Thus there is a vector in quadrant 3 or 4.
By Proposition 2.14, the complexity of such a vector is at least
$\frac{k}{2}+1$. The least complex vector in the first or second quadrant has
a complexity of 1. Thus $\zeta_{k}+-\zeta_{k}$ is the least complex
representation for $0$ at a complexity of $k$, which has a complexity of
$\frac{k}{2}+2$. ∎

######  Proposition 2.16.

For even $k$, let $p$ be the smallest odd prime factor of $k$. Then

$||1||_{k}\leq k-\frac{k}{2p}+p-2$

and if $k>2p^{2}-4p$,

$||1||_{k}\leq k-\frac{k}{2p}+p-2<k$

###### Proof.

Since $k$ is even, let $2m=\frac{k}{p}$ for $m\in\mathbb{N}$. The following is
then true:

$\zeta_{2p}+\zeta_{2p}^{3}+\dots+\zeta_{2p}^{2p-1}=0.$

Then, to get 1, we can simply leave out $\zeta_{2p}^{p}=-1$.

$\zeta_{2p}+\zeta_{2p}^{3}+\dots+\zeta_{2p}^{2p-1}-\zeta_{2p}^{p}=1.$

Note that this is an expression. If we were to translate this to base
$k=(2p)m$, we would have

$\zeta_{k}^{m}+\zeta_{k}^{3m}+\dots+\zeta_{k}^{k-m}-\zeta_{k}^{mp}=1$

By Horner’s algorithm, the complexity of this is at most $k-m+p-2$ (follows
from Proposition 3.11):. Then if $||1||_{k}<k$,

$\displaystyle k-\frac{k}{2p}+p-2$ $\displaystyle<k$
$\displaystyle\frac{k}{2p}$ $\displaystyle>p-2$ $\displaystyle k$
$\displaystyle>2p^{2}-4p.$

Since Horner’s algorithm is an upper bound, we also obtain

$||1||_{k}\leq k-\frac{k}{2p}+p-2.$

∎

######  Corollary 2.16.1.

If $k=2^{a}p^{b}$ for $a\geq 1,b>1$, then
$k-\frac{k}{2p}+p-2=2^{a}p^{b}-2^{a-1}p^{b-1}+p-2$. Since $a\geq
1,b>1,\,p-2-2^{a-1}p^{b-1}<0\implies k-\frac{k}{2p}+p-2<k\implies||1||_{k}<k$.

######  Remark.

Interestingly, for even k, when we represent
$\zeta_{k}^{m}+\zeta_{k}^{3m}+\dots+\zeta_{k}^{k-m}-\zeta_{k}^{mp}=1$ using
Horner’s method, the highest power of $\zeta_{k}$ used in the expression is
$\zeta_{k}^{2m}$, which according to Proposition 2.14 indeed has a complexity
of $2m$ (as $2m=\frac{k}{p}\leq\frac{k}{2}$).

######  Corollary 2.16.2.

If $k=2^{a}p^{b}$ for an odd prime $p$, $a,b\in\mathbb{N}$, and $||1||_{k}=k$,
then $p>2^{a-2}$.

###### Proof.

If $k=2^{a}p^{b}$, then when $||1||_{k}=k$, $k=2^{a}p^{b}\leq 2p^{2}-4p$ by
Proposition 2.16. Therefore $2^{a-1}p^{b-1}\leq p-2$. Thus
$p(2^{a-1}p^{b-2}-1)\leq-2$, and then $2^{a-1}p^{b-2}-1\leq\frac{-2}{p}\leq
0\implies 2^{a-1}p^{b-2}\leq 1$. Therefore $2^{a-2}\leq p^{2-b}$. If $b=2$,
then for Corollary 2.16.1 applies (since $a\in\mathbb{N}$), and we get a
contradiction. Thus $b\neq 2$. Thus $b=1$. Thus we have that $2^{a-2}\leq p$.
∎

######  Conjecture 2.17.

If $k=2^{a}p^{b}$, $||1||_{k}=k\iff a=1,b=1$ or $a=0$.

Notice that the above conjecture has only the case in which $b=1$ and $a\neq
1$ as unestablished as to what the complexity of 1 is.

######  Conjecture 2.18.

For even $k>2p^{2}-4p$ where $p$ is the smallest odd prime divisor of $k$,

$||1||_{k}=k-\frac{k}{2p}+p-2.$

######  Conjecture 2.19.

For even $k\leq 2p^{2}-4p$ where $p$ is the smallest odd prime divisor of $k$,

$||1||_{k}=k.$

This conjecture essentially states that Lemma 2.16 is a double implication.

To further explore complexity in cyclotomic rings, let us define the following
set:

######  Definition.

A number is minimal when there is an optimal representation that does not
contain the multiplication of two multiplex numbers. The set of all minimal
numbers is denoted by $\mathbb{M}$.

Where multiplex is defined as follows:

######  Definition.

For the purposes of this paper, a multiplex number is an element of the set
$\mathbb{Z}[\zeta_{k}]\setminus\\{a\zeta_{k}^{n}:a\in\mathbb{N},n\in\mathbb{N}\\}$.

The intuition for this is that there are at least 2 non-zero coefficients.

For example, these are some minimal numbers in $k=4$:

$\displaystyle 2$ $\displaystyle=i^{3}\cdot 2i$ $\displaystyle 2+2i$
$\displaystyle=2i+2i\cdot i^{3}.$

Most numbers are minimal, but there are still numbers that are nonminimal. For
example, the two least complex nonminimal numbers for $k=4$ are

$\displaystyle 3-4i$ $\displaystyle=(i-2)^{2}=(i+i(i+i))^{2}$ $\displaystyle
3-5i$ $\displaystyle=(i-1)(i-4)=(i+i\cdot i)(i+(i+i)(i+i)),$

both with complexity 8, which one can verify with a little bit of coding.

Investigating minimal numbers, we come up with the following propositions and
conjectures.

######  Proposition 2.20.

$\mathbb{M}$ is closed under “optimal addition”:
For $a,b\in\mathbb{M}$ and their optimal representations $A,B$ respectively,
if $A+B$ is an optimal representation of $a+b$, then $a+b\in\mathbb{M}$

###### Proof.

This follows from the definition. ∎

######  Remark.

It is important to note that the converse might not be true.

######  Conjecture 2.21.

All non-multiplex numbers are minimal.

######  Remark.

By testing the first 16 complexities for the Gaussian Integers, we have yet to
find a counterexample to this, or to the more specific conjecture that all
natural numbers are minimal. However, it should be noted that the first non-
minimal Gaussian Integer has complexity 8, so we may have not tested enough
complexities to find one that happens to be a natural number.

######  Conjecture 2.22.

The largest value of $\frac{||n||_{k}}{\ln n}$ for a fixed $k>1$ is
$\frac{||2||_{k}}{\ln 2}$.

######  Remark.

We have verified this for $k=2$ up to complexity 26, $k=4$ for complexities up
to $26$, and $k=3$ for complexities up to 10. This is the analogue of
$\frac{26}{\ln 1439}\ln n$ as the best theoretical upper log bound for $k=1$.

######  Conjecture 2.23.

$||n||_{p^{k}}\leq||n||_{p^{k+1}}$

for $p$ a prime and $k$ a natural.

######  Remark.

Some proof approaches we have attempted is to assume Conjecture 2.21, replace
an optimal representation using $\zeta_{p^{k+1}}$ with $\zeta_{p^{k}}$. The
primary issue with this approach is that while this forces addends to have the
same power of $\zeta_{p^{k+1}}$, this doesn’t guarantee that we can have an
expression of the proper associate of $n$ using the $\zeta_{p^{k}}$. For
instance, $7=i(i+(i+i)^{3})$ but $7=-1+-1\cdot(-1+-1)^{3}$ (the first
expression ‘passes through’ an associate of 7, but the second obtains it
directly).

Another approach is to show that the extra degrees of freedom granted by
allowing the vectors corresponding to powers of $\zeta_{p^{k+1}}$ can’t allow
for a “shorter” path.

######  Remark.

It may also be interesting to look at cyclotomic rings in terms of
rationality. If a representation represents a natural number, the sum of the
imaginary components must be 0. For most $k$ and $p$, this imaginary component
will be irrational, specifically outputs of the sine function on a rational
multiple of $2\pi$. Thus the sum of the imaginary components of the vectors
composing the optimal expression may have structure that can be analyzed. It
also may be true that if $a$ is in the expression for a natural, the conjugate
must also, since we need the sum of the imaginary components to equal 0 and
they are irrational. This would then imply the minimality conjecture (2.21).

##  3 Polynomial Rings

The next step for generalization is to turn into the polynomial ring
$\mathbb{Z}[x]$. Since our expressions are written by summing and multiplying
$x$’s, it would assist our exploration to investigate this ring.

######  Observation.

We can see that for $k\in\mathbb{N}$,

$\displaystyle||x^{k}||$ $\displaystyle=k$ $\displaystyle||kx||$
$\displaystyle=k$

An important application of polynomial rings is to quickly convert expression
to a representation. Turning an expression to a representation can be done by
substituting a base $k$ for $x$.

For some example data, see Table 1.

$k$ | $n$
---|---
1 | $x$
2 | $x^{2},2x$
3 | $x^{3},x^{2}+x,2x^{2},3x$
4 | $x^{4},x^{3}+x,x^{3}+x^{2},x^{2}+2x,2x^{3},2x^{2}+x,3x^{2},4x,4x^{2}$
5 | $\cdots 5x$
⋮ |
Table 1: A table of expressions $n$ with complexities $k$.

We investigate the bounds, not on a specific polynomial, but for the number of
polynomials with complexity $k$. For each polynomial of complexity $a$ and
complexity $b$, it is not always possible to create a new polynomial of
complexity $a+b$ just by adding or multiplying the two simpler polynomials.
For example, $2x+2x=4x$, but this is a repeat of the expression $x+3x$, a sum
that also implies a complexity of 4. In general, it is difficult to calculate
the size of the complexity classes because of these repeats.

######  Definition.

Let the $k$th complexity class (denoted by $K_{k}$) be the set of all
polynomials with complexity $k$

$n$ | $|K_{n}|$ | $n$ | $|K_{n}|$
---|---|---|---
1 | 1 | 8 | 252
2 | 2 | 9 | 652
3 | 4 | 10 | 1554
4 | 9 | 11 | 3967
5 | 19 | 12 | 10280
6 | 45 | 13 | 27008
7 | 104 | 14 | 71738
Table 2:  Table of first few complexity classes $K_{n}$, where $n$ is the
complexity value and $|K_{n}|$ is the number of elements in the complexity
class.

######  Proposition 3.1.

For all $n\in\mathbb{Z}$,

$|K_{n}|\leq n^{n-1}$

###### Proof.

In order to find an upper bound on these complexity classes, we may simplify
our counting and over estimate by treating it as if none of the combinations
of elements are repeats. Using this, it can be seen that

$|K_{n}|\leq
2\Bigl{(}|K_{1}|\cdot|K_{n-1}|+|K_{2}|\cdot|K_{n-2}|+\ldots+|K_{n/2}|\cdot|K_{n/2}|\Bigr{)}$

or $|K_{(n-1)/2}|\cdot|K_{(n+1)/2}|$ depending on the parity of $n$. Observe
that the RHS can be rewritten as
$\displaystyle\sum_{i=1}^{n-1}\Bigl{(}|K_{i}|\cdot|K_{n-i}|\Bigr{)}$.

The proof will be conducted by induction. Firstly, observe that $|K_{1}|=1\leq
1^{1-1}$ as a base case.

From here, we shall assume that for all $1\leq i<n,|K_{i}|\leq i^{i-1}$. Then
it follows that $|K_{i}|\leq n^{i-1}$. Then, we can substitute to find that

$|K_{n}|\leq\sum_{i=1}^{n-1}n^{i-1}\cdot
n^{n-i-1}=\sum_{i=1}^{n-1}n^{n-2}=(n-1)\cdot n^{n-2}\leq n^{n-1}.$

∎

Here we have proved the trivial bound. Admittedly, this is a very weak bound,
considering that for the most part, in our experience, the size of complexity
classes seem to grow exponentially with a fixed base. For example, letting
$||n||=c$ and using our upper and lower bounds of $\frac{3}{\ln 3}\ln n\leq
c\leq\frac{3}{\ln 2}\ln n$ for the natural numbers, we can find that any $n$
with complexity $c$ must satisfy the inequality $2^{c/3}\leq n\leq 3^{c/3}$,
giving us a restriction of $3^{c/3}-2^{c/3}+1$ on the size of the $c$-th
complexity class.

We can attempt to take inspiration from this idea by utilizing the bounds on
polynomials with complexity $c$. The following two lemmas, in particular, may
be of use:

######  Lemma 3.2.

A polynomial of complexity $c$ must have a degree of at most $c$.

###### Proof.

This is trivial, since any polynomial of degree $d$ must have at least $d$
$x$’s multiplied together. ∎

######  Lemma 3.3.

A polynomial of complexity $c$ whose sum of coefficients is $s$ satisfies
$s\leq 3^{c/3}$.

###### Proof.

This can be seen from the fact that the sum of coefficients of a polynomial
$f(x)$ is equal to $f(1)$. We can then treat this polynomial as a complexity
expression. We know from regular integer complexity that the maximum number
with complexity $c$ is $3^{c/3}$. ∎

While we are proving such restrictions, we can also verify the following upper
bound on complexity, although we won’t use it to find a restriction on the
size of complexity classes:

######  Lemma 3.4.

If $f(x)$ has degree $d,\,||f(x)||\leq f(1)+d-1$

###### Proof.

This result can be obtained by writing $f(x)$ in “base $x$” using Horner’s
method. For example:

$3x^{4}+2x^{3}+4x^{2}+2x=x+x+x\left(x+x+x+x+x\left(x+x+x\left(x+x+x\right)\right)\right).$

Recall that $f(1)$ is equal to the sum of the coefficients. ∎

######  Remark.

Note that using Horner’s algorithm shows that complexity in terms of $x$ is
defined for all polynomial functions of $x$ with positive integral
coefficients that doesn’t have a constant term.

Now, we can use the lemmas 3.2 and 3.3 to find a restriction on how many
polynomials could have a complexity of $n$. That process leads us to the
following bound:

######  Proposition 3.5.

Let $K_{n}$ be the class of polynomials with complexity $n$. Then

$\sum_{j=1}^{n}|K_{j}|\leq\sum_{i=1}^{\lceil 3^{n/3}\rceil}\binom{i+n}{n}.$

###### Proof.

Any polynomial with a complexity up to $n$ can have at most degree $n$ and sum
of coefficients $3^{\frac{n}{3}}$. Therefore, in order to find the number of
polynomials with positive integral coefficients and no constant term, we need
to find the number of ways to “distribute” $i$ “ones” among $n$ coefficients
for $i\leq 3^{n/3}$. As we range $i$ from 1 to $\leq 3^{n/3}$, we end up
counting all the different polynomials that we could obtain. Using the stars
and bars method, we get a maximum of $\binom{i+n}{n}$ possible polynomials and
we need to sum all the possible $i$’s. ∎

Admittedly, there are many setbacks to this method that makes it a weak bound.
It severely overcounts possible polynomials. For example, the only polynomial
with degree $n$ and complexity $n$ is $x^{n}$ itself, but our method considers
all $n$th degree polynomials with coefficients summing to at most
$3^{\frac{n}{3}}$.

Furthermore, it turns out that for sufficiently large $n$, this bound is
weaker than $\sum_{i=1}^{n}i^{i-1}$, our previous bound. Verifying this will
be left as an exercise to the reader.

Meanwhile, we can much more effectively attempt to create a lower bound for
$|K_{n}|$ by considering a modified version of complexity that is easier to
count:

######  Definition.

Let the modified complexity of a polynomial $f(x)\in S$ be the number of $x$’s
it takes to write $f(x)$. $S$ is defined as the following

  * •

$x\in S$.

  * •

If $f(x)\in S$, then $f(x)+x\in S$

  * •

If $f(x)\in S$, then $f(x)\cdot x\in S$

Denote the modified complexity of $f(x)$ as $|||f(x)|||$.
Note $S$ is a set of expressions, not a set of polynomials. They look similar,
but they are not the same.

For example,

$x(x\cdot x+x\cdot x+(x+x+x))$

is not a valid modified complexity expression because it has a non-nested
multiplication (namely two $x\cdot x$’s), but

$x(x+x+x+x(x+x))$

is. Though they evaluate to be the same polynomial, the latter is in a valid
form while the former is not.

######  Remark.

Following from the definition, we can see that any expression of modified
complexity is equivalent to Horner’s method, which only adds or multiplies
$x$’s to expressions, but does not add or multiply together two subexpressions
that both have complexity greater than 1.

######  Lemma 3.6.

Every polynomial with positive integral coefficients and no constant term has
a unique modified complexity expression.

###### Proof.

We already know that Horner’s method is able to express all polynomials with
positive integral coefficients and no constant term in terms of $x$.
Therefore, we can conclude that every such polynomial has a modified
complexity expression, which is equivalent to the Horner’s method expression.
Furthermore, since Horner’s method amounts to writing a polynomial in base
$x$, it follows that there is only one modified complexity expression for each
polynomial since there is a unique base $x$ expression for each polynomial. ∎

######  Lemma 3.7.

Let $K^{\prime}_{n}$ be the $n$-th modified complexity class. Then

$|K^{\prime}_{n}|=2^{n-1}$

###### Proof.

Trivially, the only member of the first modified complexity class is $x$, so
$K^{\prime}_{1}=1$.

Next, assume that $K^{\prime}_{n}=2^{n-1}$. From each polynomial $f(x)$ in
that complexity class, we get two polynomials in $K^{\prime}_{n+1}$: $f(x)+x$
and $f(x)\cdot x$. From the above lemma, we know that each one of these
polynomials is unique, so there is no possibility of any of them having
appeared in any earlier complexity class.

Meanwhile, FTSOC suppose there was a polynomial of modified complexity $n+1$
not in this list. By WOP, let $n+1$ be the smallest such. But then, that
polynomial can be reduced to a polynomial of complexity $n$ by just undoing
the last operation in the expression. Therefore, we can be sure that the
$2^{n}$ polynomials in $K^{\prime}_{n+1}$ are the only polynomials in that
modified complexity class.

Thus, by induction, $K^{\prime}_{n}=2^{n-1}$. ∎

With this in mind, we have enough to find a bound on the cumulative sum of the
sizes of the first $n$ complexity classes, although this doesn’t imply a bound
on the exact number of elements per complexity class.

######  Proposition 3.8.

For $n\geq 1$,

$2^{n}-1\leq\sum_{i=1}^{n}|K_{n}|$

###### Proof.

First note that $|K^{\prime}_{n}|\leq|K_{n}|$, since given an element of
$K^{\prime}_{n}$, it has complexity less than or equal to $n$, as the modified
complexity express is still an expression, it just may not be optimal. Thus
every element of $K^{\prime}_{n}\subset K_{n}$. Thus the size of $K_{n}$ is
greater than or equal to the size of $K^{\prime}_{n}$. Since the size of
$K^{\prime}_{n}$ equals $2^{n-1}$, our hypothesis is easily obtained with a
geometric sum.

∎

Even though we cannot find a bound for each of the complexity classes by this
method, we can still conjecture one:

######  Conjecture 3.9.

For $n\geq 1$,

$2^{n-1}\leq|K_{n}|$

In addition to this, plotting the first fourteen values of $|K_{n}|$ supports
the conclusion that the class size grows exponentially, approximately. We can
also gain insight by looking at the ratios $\dfrac{|K_{n}+1|}{|K_{n}|}$:

$n$ | $\dfrac{|K_{n+1}|}{|K_{n}|}$ | $n$ | $\dfrac{|K_{n}+1|}{|K_{n}|}$
---|---|---|---
1 | 2 | 7 | 2.423
2 | 2 | 8 | 2.460
3 | 2.25 | 9 | 2.506
4 | 2.111 | 10 | 2.553
5 | 2.368 | 11 | 2.591
6 | 2.311 | 12 | 2.627

If this sequence of terms ends up converging to a constant value, the class
size function will approach an exponential function, and this exponential
function could be used as an upper bound. It is not unreasonable to guess that
perhaps this is the case, and it may even be possible that the constant in
question is $e$.

######  Conjecture 3.10.

For $n\geq 1$,

$e^{n-1}\geq|K_{n}|$

Figure 3: A logarithmicly scaled plot with the size of $K_{n}$ ($y$), against
the value of $n$ ($x$). Plotted are the points in Table 2, the lower bound in
blue, the upper bound in green, and the conjectured upper bound in dotted
black.

Meanwhile, the notion of modified complexity in the polynomial ring offers a
variety of avenues of exploration. One useful tool to explore them is to
notate modified complexity expressions using a list as shorthand, partially
inspired by our recursive algorithm for using computers to generate optimal
expressions in a variety of other rings (see Appendix).

######  Definition.

Let the shorthand list $L$ of a modified complexity expression $f(x)$ be an
ordered list consisting of 1’s and $-1$’s and define it recursively as
follows:

  * •

$x=\\{1\\}$

  * •

$f(x)+x$ is represented by appending 1 to the end of the list $L$ which
represents $f(x)$

  * •

$f(x)\cdot x$ is represented by appending -1 to the end of the list $L$ which
represents $f(x)$

For example,

$(((x+x)x)+x)x+x=\\{1,1,-1,1,-1,1\\}.$

We can observe the following trivial properties of a polynomial and its
shorthand list:

For a modified complexity expression $f(x)$ represented by $L$,

  * •

$\deg(f(x))$ is one more than the number of $-1$’s in $L$.

  * •

The sum of the coefficients of $f(x)$ is the number of $1$’s in $L$, which is
equal to $f(1)$.

  * •

$|||f(x)|||=\text{len}(L)$

######  Proposition 3.11.

$|||f(x)|||=\deg(f(x))+f(1)-1$

###### Proof.

This follows from the properties listed above. ∎

######  Remark.

Note that this is a special case of Lemma 3.4.

######  Proposition 3.12.

The number of unique $f(x)$’s that satisfies that $|||f(x)|||=k$ and
$\deg(f(x))=a$ for positive integers $k,a\neq 1$ is exactly
$\binom{k-1}{a-1}$.

###### Proof.

We know that for $\deg(f(x))=a$, there must be $a-1$ occurrences of $-1$’s in
$L$. We also know that for $|||f(x)|||=k$, the length of $L$ is $k$. Since the
first element of $L$ is always 1, we are looking for the amount of ways we can
arrange $a-1$ occurrences of $-1$’s and $k-(a-1)$ occurrences of 1’s, which is
$\binom{k-1}{a-1}$. ∎

##  4 Integers Modulo $m$

We also looked into integer complexity in a finite ring $\mathbb{Z}_{m}$ for
integral $m$. Note that we are no longer restricted to using 1 as our base. In
this section, we shall denote the base as $s$.

######  Observation.

The representations with base $s$ span every element of
$\mathbb{Z}/m\mathbb{Z}$ if and only if $s\in U_{m}$.

######  Observation.

Different values of $s$ yield different complexities for the same number.
There are some $s$’s that yield larger complexities than others.

We can no longer place bounds on the complexity of a certain element as it
varies based on $s$. We define the following term to aid us in our
investigation.

######  Definition.

The inefficiency $E$ of an element, which will be used as a base,
$s\in\mathbb{Z}/m\mathbb{Z}$ is defined as

$E(m,s)=\max(||0||,||1||,||2||,\ldots||m-1||)$

In other words, the maximum complexity of an element of
$\mathbb{Z}/m\mathbb{Z}$ with $x=s$.

Certain questions arise after investigating inefficiency. We will use these
questions to guide our investigation of complexity in a finite ring.

  1. 1.

Which values of $s$ are the least inefficient?

  2. 2.

Which values of $s$ are the most inefficient?

  3. 3.

Is there a formula to determine which $s$ are the least inefficient?
Alternatively, what are the properties of the least inefficient $s$?

  4. 4.

Is 0 always the most complex number?

Through computation, we know that 4 is false. One counterexample is with a
base of 9 in $\mathbb{Z}/11\mathbb{Z}$. There is also the obvious
counterexamples with a base of $-1$, since $(-1)(-1)+(-1)=0$ is an expression
of complexity 3.

######  Conjecture 4.1.

The inefficiencies have a logarithmic upper and lower bound, as appears to be
true in Figure 10.

After looking at some numerical examples, we also conjecture the following:

######  Conjecture 4.2.

For all $m$, when $s=1,E(m,s)$ is the highest out of all the possible $s$
values.

This conjecture could be explained by the fact that multiplying by 1 does not
yield new values, whereas other bases $s$ can be multiplied to obtain other
numbers (thus exhausting all the integers in $\mathbb{Z}/m\mathbb{Z}$ earlier,
reduing the inefficiency).

######  Conjecture 4.3.

$E(m,-1)$ is the second or tied third most inefficient for sufficiently large
$m$.

A similar heuristic for Conjecture 4.2 applies here to provide an intuition as
to why this is likely true.

######  Conjecture 4.4.

$E(m,2)$ is the third most inefficient for odd $m$.

The general idea here is that since $x=2$ allows the two expressions $x^{2}$
and $2x$ to evaluate to the same value, we only have one element of complexity
2, which allows us to produce fewer values of certain greater complexities.

######  Observation.

Other than our conjectures above, inefficiency seems to be unrelated to the
order of $s$ or how large $s$ is.

######  Observation.

There always seems to be a “dominant” inefficiency. As in, there is a value
$n_{m}$ where there exists many $s$ values such that $E(m,s)=n_{m}$. There are
certain $m$’s where this dominant value is much more dominant, and there are
some values where the distribution of inefficiency is more equal. Furthermore,
sometimes the dominant inefficiency seems to be the smallest possible
inefficiency, but this not always the case.

######  Observation.

For varying $s$ in $\mathbb{Z}/m\mathbb{Z}$, we noticed that most $E(43,s)$
output around the same value, namely 7.

######  Observation.

It seems like the $x$ such that $\mathbb{Z}/x\mathbb{Z}$ have a high
proportion of bases with inefficiencies equal $n$, the least inefficiency,
correspond to the lowest $x$-value in the set of all $x$ with an equal minimum
inefficiency.

Figure 4: A plot of the inefficiencies ($y$) using a certain base ($x$) in
$\mathbb{Z}_{44}$. In most cases, plotting $x$ and $y$ yields a plot similar
to this one.

Figure 5: A plot of the inefficiencies ($y$) using a certain base ($x$) in
$\mathbb{Z}_{43}$.

Figure 6: A plot of the resilience ($x$) vs. inefficiency ($y$) for
$\mathbb{Z}/1009\mathbb{Z}$.

For example, in Figure 6, there are a lot of bases with an inefficiency of 7,
and this corresponds to 44 being the first mod with no inefficiencies of 6.
The intuition for this is that as the modulo increases, the inefficiencies of
a given base tend to increase as there are more elements that need to be
reached with combinations of that base. Thus at the point in which there are
no more inefficiencies of $n-1$, there are a lot of other points which will
have already increased up to $n$. Thus going up enough to ‘lose’ the
inefficiency of $n-1$ will result in more bases $s$ with inefficiency $n$.

We attempt to investigate the minimum inefficiency of a certain
$\mathbb{Z}/m\mathbb{Z}$.

Figure 7: A plot of the minimum inefficiency ($y$) of
$\mathbb{Z}/x\mathbb{Z}$.

Let us consider the outliers that have a higher minimum inefficiency than
others around it. Looking at Figure 7, we create the following data table:

$m$’s with low inefficiencies
---
$m$ | 12 | 24 | 30 | 48 | 60 | 70 | 72 | 120 | 144 | 240 | 288 | 290
Inefficiency | 5 | 7 | 7 | 8 | 8 | 8 | 8 | 9 | 9 | 10 | 10 | 10

The $m$’s are most of the time a multiple of 12, and generally seem to have
many factors. Then, $\mathbb{Z}/m\mathbb{Z}$ would have many zero divisors.
This could potentially explain why these numbers have such great
inefficiencies: the abundance of factors results in them having less units
than usual, so the ring has less ’tries’ at having a unit base $s$ with a
lower inefficiency.

######  Definition.

The resilience of $s$, (denoted $r(s)$) is the least $k$ such that for
distinct modified complexity expressions $f(x),g(x)$ with complexity less than
or equal to $k,f(s)=g(s)$.

For example, in $\mathbb{Z}_{10},r(3)=3$ because $3\cdot 3=3+3+3$ and this is
the first instance where two expressions are equal when evaluated at 3.

######  Proposition 4.5.

If $k$ is the resilience of $s$, then $s\geq k$.

###### Proof.

We know that $s$ added to itself $s$ times, which has complexity $s$, is a
repeat of $s^{2}$. Therefore, the latest possible occurrence of the first
repeat has complexity $s$.

∎

######  Observation.

For all $m>1$, in $\mathbb{Z}/m\mathbb{Z},r(1)=r(2)=2$. This occurs because
the expressions $x$ and $x^{2}$ are equal whenever $x$ is 1, and $x^{2}=2x$
whenever $x$ is 2.

In order to visually gain intuition about the importance of resilience, we can
use graphs to represent modified complexity in $\mathbb{Z}/m\mathbb{Z}$:

######  Definition.

A modified complexity tree with base $s$ (denoted by $\operatorname{mct}(s)$)
is a binary tree with $s$ as the root. The left child of a node $t$ is $t+s$
and the right child is $t\cdot s$. For an example, see Figure 8.

362564052511624 Figure 8: Weak complexity tree for $\mathbb{Z}/7\mathbb{Z}$
and base $3$

######  Observation.

It seems as though the more resilient a base is, the less inefficient it is.
See 6. This isn’t always the case: for example, in many
$\mathbb{Z}/x\mathbb{Z}$, there are elements with resilience 2 that are more
inefficient than elements with resilience 3, but it generally seems to be
“likely” that given two elements, the one with the higher resilience has the
lower inefficiency.

This follows from the intuition that one may get trying to make an MCT: having
a repeat earlier gets rid of an entire potential branch of the tree, requiring
potentially more levels of complexity to supplement for the loss.

######  Definition.

A modified complexity graph with base $s$, (denoted by
$\operatorname{mcg}(s)$), is a mct(s) without repeated nodes. For an example,
see Figure 9.

3406521 Figure 9: Connected weak complexity graph with base 3 in
$\mathbb{Z}/7\mathbb{Z}$.

######  Remark.

Note that every node of this connected graph has two arrows leading out and
two arrows leading in, since every node has an additive and multiplicative
inverse.

Figure 10: A plot of all of the inefficiencies ($y$) in
$\mathbb{Z}/x\mathbb{Z}$.

From here, we return to the question of what values of $s$ are most and least
efficient. Observing Figure 10, we notice a distinct group of outliers that
have higher inefficiencies than the rest. Through observation, we know that
these have base $s=1$. At one point, we conjectured that perhaps this is a
reflection of integer complexity in the naturals. To be precise, we once
conjectured that for all $a\in\mathbb{Z}/m\mathbb{Z}$

$E(m,1)=\max(||a||).$

Note that $||a||$ refers to integer complexity in the naturals.

This would imply that inefficiency for $s=1$ increments when $m$ is the least
element of a complexity class. This is the explanation for the presence of
mostly continuous line segments making up the inefficiencies for $s=1$.

However, there are counterexamples for this. One such counterexample is
$107\in\mathbb{Z}_{109}$. We computed that $||107||_{1}=15$, since $107\equiv
216\equiv 2^{3}\cdot 3^{3}\pmod{109}$ but $||107||=16$.

Other than a small number of counterexamples, this conjecture generally seems
to hold true. These counterexamples happen in $\mathbb{Z}/m\mathbb{Z}$
whenever for all naturals $a\leq m$, there is another integer $a^{\prime}$
such that $a\equiv a^{\prime}\mod m$ and $a^{\prime}$ has an unusually low
complexity.

In the case of $m=109$, there were two factors that contributed to this being
a counterexample. Firstly, 109 is barely larger than 107, the first element
with complexity 16, so 107 was the only natural number up to 109 with a
complexity of 16. Secondly, $107\equiv 216\mod 109$, and since 216 is “very
composite” ($216=2^{3}\cdot 3^{3}$), it happens to have a lower-than-ordinary
complexity.

######  Theorem 4.6.

For a base $s>1$,

$E(m,s)\leq\frac{s}{\ln s}\ln(m)+s-1$

###### Proof.

Since $E(m,s)$ is the largest complexity of an element $n$ in $\mathbb{Z}$
with base $s$, it is sufficient to prove an upper bound for $||n||_{s}$. In a
similar fashion to our previous proofs, we want to express $n$ in base $s$
using Horner’s method. However, we run into a problem if $s$ does not divide
$n$ because we would get a remainder with unknown complexity.

Multiplying all elements of $\mathbb{Z}/m\mathbb{Z}$ by $s$ is a permutation
since we already established that $s$ and $m$ are coprime. Therefore, the
question is reduced to: what is the maximum number of $s$’s needed to express
an element of the set $\\{s,2s,\ldots,(m-1)s\\}$? Since all of these elements
are divisible by $s$ in the naturals, we can use Horner’s method to express
them.

Suppose the base $s$ expansion of $n$ is:

$n=s_{1}+s(s_{2}+s(s_{3}+s(\ldots$

Then, multiplying $s$ to both sides,

$ns=s\cdot s_{1}+s(s\cdot s_{2}+s(s\cdot s_{3}+s(\ldots$

The base $s$ representation of $n$ for some integer $n$ has
$\lfloor\log_{s}{n}\rfloor+1$ digits, in the naturals. Each digit $s_{i}$ is
at most $s-1$, so worst case scenario, each $s\cdot s_{i}$ takes at most $s-1$
$s$’s. There are also $\lfloor\log_{s}{n}\rfloor$ $s$’s being multiplied.

Thus, adding these together, we get an upper bound of
$(s-1)\left(\lfloor\log_{s}{n}\rfloor+1\right)+\lfloor\log_{s}{n}\rfloor$.
This is less than $s\log_{s}{n}+s-1=\frac{s}{\ln s}\ln(n)+s-1$.

This is maximized when $n$ is set to $m$ (we don’t have a way to obtain 0 with
Horner’s algorithm). ∎

######  Remark.

Note that this bound has a linear component, and for large $s$, this bound
becomes very loose. It also falsely implies that inefficiency is correlated to
the size of the base. We want to find a way to reduce $s$ if possible. This
following corollary provides us with a powerful tool to reduce the upper bound
in certain cases.

######  Corollary 4.6.1.

For a base $s>1$,

$||n||_{s}\leq||a||_{s}\left(\frac{a}{\ln a}\ln(m)+a-1\right)$

###### Proof.

We can instead write the $n$ in base $a$; then this bound follows. ∎

######  Remark.

We would want to choose an $a$ such that both $a$ and $||a||_{s}$ is small.
Then, this would successfully reduce our bound.

######  Corollary 4.6.2.

$\frac{3}{\ln 3}\ln(m)+2$ acts as an upper bound on the minimum inefficiency
for any base $s$ in $\mathbb{Z}/m\mathbb{Z}$.

###### Proof.

This can be seen by simply plugging in 3 for the value of $s$ in the bound
described in Theorem 4.6. 3 is the positive integral value that causes
$\frac{s}{\ln s}$ to have its lowest value. ∎

######  Remark.

This proof can also be seen geometrically. We can consider a mc-graph in which
all the multiples of $s$ are arranged in a circle for a
$\mathbb{Z}/p\mathbb{Z},p$ a prime. For an example, see Figure 11. Then we can
index each multiple $as$ as $a$.

Then the operations of modified complexity are directly analogous to the
operations in the base representation (addition of $s$ is the addition of $1$
on the graph, shifting one node counterclockwise; multiplication by $s$
multiplies the index by $s$).

As a result, the index of our base $s$ is 1, and these operations make
expressing any node of the graph in terms of $s$ equivalent to expressing
their index in terms of 1 using Horner’s rule.

$1\cdot 5$$2\cdot 5$$3\cdot 5$$4\cdot 5$$5\cdot 5$$6\cdot 5$$7\cdot 5$$8\cdot
5$$9\cdot 5$$10\cdot 5$$11\cdot 5$ Figure 11: A subgraph (excluding
multiplication by $s$) of an mc-graph for $\mathbb{Z}/11\mathbb{Z}$ with $s=5$

######  Observation.

From trying some examples, it appears that every mc-graph has a cycle of
length $r$ for all $r$, a natural up to $x$, the modulo.

We are interested in strengthening the upper bound on the lowest possible
inefficiency for a given field (not a ring, as will be clarified below)
$\mathbb{Z}/m\mathbb{Z}$ from our already established bound of $\frac{3}{\ln
3}\ln{m}+2.$ Although we were unsuccessful in this endeavor so far, we shall
outline our general method for attempting this.

The general idea is to guarantee the existence of a certain number of distinct
elements with complexity under a certain value (for an existing value of $s$).

We shall go about this by trying to find the base $s$ with the maximum
“resilience” in terms of modified complexity. If this resilience is equal to
$r$, then there are $2^{r-1}-1$ distinct elements with modified complexity
under $r$. Since modified complexity is an overestimate of actual complexity,
these $2^{r-1}-1$ elements all have complexity under $r$.

We will “determine” what base $s$ to choose by means of elimination. For
example, we know that if $s=1$, then the polynomials $x$ and $x^{2}$ will
repeat each other, so we won’t let $s$ be 1. Similarly, $s=2\Rightarrow
x^{2}=2x$, so $s\neq 2$. Generally, we shall pair and set equal polynomials
$f(x),g(x).$ $f(x)-g(x)$ has $\deg(f)$ roots if, WLOG, we let $f$ have the
higher degree (importantly, this is only true if there are no zero-divisors in
$\mathbb{Z}/m\mathbb{Z}$, so we are only considering fields); both polynomials
are divisible by $x$ since they are expressions, so we will find a maximum of
$\deg(f)-1$ new roots $s$ to be thrown out. This process will be repeated
until we have thrown out more than $p$ roots.

Note that this strategy does end up under-counting $r$ severely since it does
not account for repeated roots whatsoever. However, this does not impact the
existence of those undercounted elements with complexity under $r$.

######  Lemma 4.7.

The highest resilience in modified complexity among those of all bases in
$\mathbb{Z}/p\mathbb{Z}$ is greater than or equal to the largest $k$ such that
$\left(k-2\right)4^{k}-\left(k-4\right)2^{k}\leq 2p$.

###### Proof.

First, we begin by showing that this expression

$\sum_{D_{1}=1}^{k}(D_{1}-1)\sum_{D_{2}=1}^{D_{1}}\sum_{k_{1}=D_{1}}^{k}\binom{k_{1}-1}{D_{1}-1}\sum_{k_{2}=D_{2}}^{k}\binom{k_{2}-1}{D_{2}-1}$

is an upper bound for the number of integers that the base can’t be if the
modified resilience of the base is greater than $k$. In other words, within
$k$ complexities, with the strategy detailed above, we will have eliminated
this many possibilities for the value of $s$.

Suppose that we are setting equal two polynomials $f$ and $g$ with complexity
up to $k$ and eliminating all of the resulting roots (other than 0). Then let
$D_{1},D_{2}$ be the respective degrees of $f$ and $g$ and $k_{1},k_{2}$ be
their respective modified complexities.

WLOG, suppose $D_{1}\geq D_{2}$. Then for each pair $f$ and $g$, we would need
to eliminate $D_{1}$ roots for each pair.

Next given specific values of $D_{1},D_{2},k_{1},k_{2}$, there are
$\binom{k_{1}-1}{D_{1}-1}\cdot\binom{k_{2}-1}{D_{2}-1}$ polynomials $f$ and
$g$ with those degrees and modified complexities.

The degree $D_{1}$ can range anywhere from 1 to $k$, whereas $D_{2}$ can be
anything from 1 to $D_{1}$. The modified complexities $k_{1}$ and $k_{2}$ can
go up to $k$ but must be greater than the degrees of the respective
polynomials associated with them. Therefore, in total, the number of possible
values of $s$ we are eliminating is:

$\sum_{D_{1}=1}^{k}\sum_{D_{2}=1}^{D_{1}}\sum_{k_{1}=D_{1}}^{k}\sum_{k_{2}=D_{2}}^{k}\binom{k_{1}-1}{D_{1}-1}\cdot\binom{k_{2}-1}{D_{2}-1}\cdot(D_{1}-1),$

which can be rewritten as

$\sum_{D_{1}=1}^{k}(D_{1}-1)\sum_{D_{2}=1}^{D_{1}}\sum_{k_{1}=D_{1}}^{k}\binom{k_{1}-1}{D_{1}-1}\sum_{k_{2}=D_{2}}^{k}\binom{k_{2}-1}{D_{2}-1}.$

Then, we can show that this is less than or equal to
$(2^{k}-1)(2^{2k-1}-2^{k}+1)$ with some algebra:

$\displaystyle\sum_{D_{1}=1}^{k}(D_{1}-1)\left(\sum_{D_{2}=1}^{D_{1}}\left(\sum_{k_{1}=D_{1}}^{k}\binom{k_{1}-1}{D_{1}-1}\left(\sum_{k_{2}=D_{2}}^{k}\binom{k_{2}-1}{D_{2}-1}\right)\right)\right)$
$\displaystyle=\sum_{D_{1}=1}^{k}(D_{1}-1)\left(\sum_{k_{1}=D_{1}}^{k}\binom{k_{1}-1}{D_{1}-1}\left(\sum_{D_{2}=1}^{D_{1}}\left(\sum_{k_{2}=D_{2}}^{k}\binom{k_{2}-1}{D_{2}-1}\right)\right)\right)$

Then let $k_{1}-1=a,D_{1}-1=b,k_{2}-1=c,D_{2}-1=d$ to get:

$\sum_{b=0}^{k-1}b\left(\sum_{a=b}^{k-1}\binom{a}{b}\left(\sum_{d=0}^{b}\left(\sum_{c=d}^{k-1}\binom{c}{d}\right)\right)\right)$
(7)

Then note that

$\sum_{d=0}^{b}\sum_{c=d}^{k-1}\binom{c}{d}=\begin{tabular}[]{P{0.55cm}P{0.55cm}P{0.55cm}P{0.55cm}P{0.55cm}P{0.55cm}P{0.55cm}P{0.55cm}}$\binom{0}{0}$\@add@centering&+\@add@centering&$\binom{1}{0}$\@add@centering&+\@add@centering&$\binom{2}{0}$\@add@centering&$\cdots$\@add@centering&+\@add@centering&$\binom{k-1}{0}$\@add@centering\\\
\@add@centering&+\@add@centering&$\binom{1}{1}$\@add@centering&+\@add@centering&$\binom{2}{1}$\@add@centering&$\cdots$\@add@centering&+\@add@centering&$\binom{k-1}{1}$\@add@centering\\\
\@add@centering&\@add@centering&\@add@centering&+\@add@centering&$\binom{2}{2}$\@add@centering&$\cdots$\@add@centering&+\@add@centering&$\binom{k-1}{2}$\@add@centering\\\
\@add@centering&\@add@centering&\@add@centering&\@add@centering&\@add@centering&\@add@centering&$\ddots$\@add@centering&$\vdots$\@add@centering\\\
\@add@centering&\@add@centering&\@add@centering&\@add@centering&$\binom{b}{b}$\@add@centering&$\cdots$\@add@centering&+\@add@centering&$\binom{k-1}{b}$\@add@centering\end{tabular}$

This then is less than $0+2^{1}+2^{2}+\cdots+2^{k-1}$. Using the geometric sum
formula, this equals $2^{k}-1$. Thus Equation 7 is
$\leq(2^{k}-1)\sum_{b=0}^{k-1}b\sum_{a=b}^{k-1}\binom{a}{b}$ (distributive
law).

Then see that

$\sum_{b=0}^{k-1}b\sum_{a=b}^{k-1}\binom{a}{b}=\begin{tabular}[]{P{0.55cm}P{0.55cm}P{0.55cm}P{0.55cm}P{0.55cm}P{0.55cm}p{2cm}}$\binom{1}{1}$\@add@centering&+\@add@centering&$1\binom{2}{1}$\@add@centering&+\@add@centering&$\cdots$\@add@centering&+\@add@centering&$1\binom{k-1}{1}$\\\
\@add@centering&+\@add@centering&$2\binom{2}{2}$\@add@centering&+\@add@centering&$\cdots$\@add@centering&+\@add@centering&$2\binom{k-1}{2}$\\\
\@add@centering&\@add@centering&\@add@centering&\@add@centering&\@add@centering&$\ddots$\@add@centering&$\vdots$\\\
\@add@centering&\@add@centering&\@add@centering&\@add@centering&\@add@centering&\@add@centering&$(k-1)\binom{k-1}{k-1}$\end{tabular}$

Consider an arbitrary $i$th column of this triangle, the sum of which
evaluates to:

$C_{i}=\binom{i}{1}+2\binom{i}{2}+\cdots+(i-1)\binom{i}{i-1}+i\binom{i}{i}$

Then:

$\displaystyle 2C_{i}=$ $\displaystyle
i\binom{i}{i}+\left(\binom{i}{1}+(i-1)\binom{i}{i-1}\right)+\left(2\binom{i}{2}+(i-2)\binom{i}{i-2}\right)+\cdots$
$\displaystyle+\left((i-1)\binom{i}{i-1}+\binom{i}{1}\right)+i\binom{i}{i}$
$\displaystyle=$ $\displaystyle
i\binom{i}{0}+\left(\binom{i}{1}+(i-1)\binom{i}{1}\right)+\left(2\binom{i}{2}+(i-2)\binom{i}{2}\right)+\cdots$
$\displaystyle+\left((i-1)\binom{i}{i-1}+\binom{i}{i-1}\right)+i\binom{i}{i}$
$\displaystyle=$ $\displaystyle
i\left(\binom{i}{0}+\binom{i}{1}+\cdots+\binom{i}{i}\right)$ $\displaystyle=$
$\displaystyle i\cdot 2^{i}$ $\displaystyle C_{i}=$ $\displaystyle i\cdot
2^{i-1}$

By adding all the columns together, we get:

$\displaystyle\sum_{b=0}^{k-1}b\sum_{a=b}^{k-1}\binom{a}{b}$
$\displaystyle=1\cdot 2^{0}+2\cdot 2^{1}+\cdots(k-1)\cdot 2^{k-2}$
$\displaystyle=\sum_{i=1}^{k-1}\left(\sum_{j=i-1}^{k-2}2^{j}\right)$
$\displaystyle=\sum_{i=1}^{k-1}\left(2^{k-1}-2^{i-1}\right)$
$\displaystyle=\left((k-1)\cdot 2^{k-1}-\left(2^{k-1}-1\right)\right)$
$\displaystyle=\left((k-2)\cdot 2^{k-1}+1\right)$

by the geometric sequence sum formula.

Therefore, plugging back in, we get an upper bound of
$(2^{k}-1)\left((k-2)\cdot 2^{k-1}+1\right)$.

Since we are trying to eliminate as many bases as possible until we run out,
we need our value of $r$ to be the greatest value of $k$ such that

$(2^{k}-1)\left((k-2)\cdot 2^{k-1}+1\right)\leq p-1.$

This can be simplified to state that we need our value of $r$ to be the
greatest value of $k$ such that

$(k-2)2^{2k-1}+2^{k}-(k-2)2^{k-1}\leq p.$

This further simplifies to

$\left(k-2\right)4^{k}-\left(k-4\right)2^{k}\leq 2p.$

∎

######  Remark.

It may be possible to improve this upper bound by noting that in the shorthand
lists for two expressions, if the ending numbers are the same, after setting
the polynomials equal to each other, undoing that last operation would reduce
the equality to an equality of two simpler polynomials. For example, if we
have already found the values of $x$ such that $2x^{3}=x^{2}+x$, we need not
check the values for which $2x^{3}+x=x^{2}+2x$ or $2x^{4}=x^{3}+x^{2}$ since
these equations could be reduced to the former. This means that we could
drastically cut down the number of starting values $s$ needing to be thrown
out; however, doing so makes the counting more difficult, so we have not done
it above.

From here, we can further simplify (while also loosening) the bound to an
exponential one: observing graphs of these functions reveals to us that for
all integral values, we saw that
$\left(k-2\right)4^{k}-\left(k-4\right)2^{k}<b^{x}$ for
$b=(4^{7}-2^{7})^{\frac{1}{6}}$ (note that these two functions are equal at
$k=6$, and choosing a smaller value of $b$ will cause the inequality not to
hold). The following proof will arrive at this result algebraically.

######  Lemma 4.8.

The highest resilience in modified complexity among those of all bases in
$\mathbb{Z}/p\mathbb{Z}$ is greater than or equal to
$\lfloor\log_{b}(2p)\rfloor$, for $b=(4^{7}-2^{7})^{\frac{1}{6}}$.

###### Proof.

Let $f(k)=\left(k-2\right)4^{k}-\left(k-4\right)2^{k}$. We shall start by
showing that $f(k)<b^{k}$ for all natural values of $k$. This will be proved
by induction. As a base case, this can be shown to hold true computationally
for 1, 2, 3, 4, 5, 6, and 7.

Next, consider the function:

$\frac{f(k+1)}{f(k)}=\frac{(k-1)4^{k+1}-(k-3)2^{k+1}}{(k-2)4^{k}-(k-4)2^{k}}=\frac{4(k-1)4^{k}-2(k-3)2^{k}}{(k-2)4^{k}-(k-4)2^{k}}=\frac{4(k-1)-\frac{2(k-3)}{2^{k}}}{(k-2)-\frac{(k-4)}{2^{k}}}.$

For $k\geq 3$, this is less or equal to
$\frac{4(k-1)}{(k-2)-\frac{(k-4)}{2^{k}}}$. Furthermore, for $k\geq 6$, the
denominator is greater than or equal to $(k-2)-\frac{2}{2^{6}}$, so the
function will be less than $\frac{4(k-1)}{(k-2)-\frac{1}{32}}$.

Thus, since $7>6>3$, for $k\geq
7,\frac{f(k+1)}{f(k)}<\frac{128(k-1)}{32(k-2)-1}$. Furthermore, it can be seen
by computation that $\frac{128(k-1)}{32(k-2)-1}<b$ at $k=7$. Since
$\frac{128(k-1)}{32(k-2)-1}$ is a hyperbola and can easily be seen to be
decreasing after 7, we can also conclude that $\frac{128(k-1)}{32(k-2)-1}<b$
for all $k\geq 7$. Then, by the transitive property, we get that
$\frac{f(k+1)}{f(k)}<b$ for all $k\geq 7$.

Now, assume that $f(k)<b^{k}$ for some natural number $k$ greater than 7.
Since $\frac{f(k+1)}{f(k)}<b$, we know $f(k+1)<f(k)\cdot b$, and using our
inductive assumption, we get that $f(k+1)<b^{k+1}.$

This means that by the transitive property, $b^{k}\cdot\frac{1}{2}-1$ is also
an overestimate for the number of possible values of $s$ we eliminate within
the first $k$ modified complexities. We can keep eliminating values of $s$
until we run out and have eliminated more than $p-1$ values of $s$, so the
maximum modified resilience is largest value of $k$ such that
$b^{k}\cdot\frac{1}{2}-1\leq p-1$. Therefore, simplifying, we need the largest
value of $k$ such that $k\leq\log_{b}(2p)$, which is just
$\lfloor\log_{b}(2p)\rfloor+1$. ∎

Essentially, what we have stated is that there exists a value
$s\in\mathbb{Z}/p\mathbb{Z}$ such that all polynomial expressions of the first
$\lfloor\log_{b}(2p)\rfloor$ modified complexities are distinct when evaluated
at $s$. This means that for each complexity $i<\lfloor\log_{b}(2p)\rfloor+1$,
we have $2^{i-1}$ elements with that modified complexity (whose real
complexities could be even less). This gives us
$2^{\lfloor\log_{b}(2p)\rfloor}-1$ elements in total, which turns out to be a
root expression of $p$ between $p^{\frac{1}{2}}$ and $p^{\frac{1}{3}}$. We
have not succeeded in doing this yet, but the task of finding a lower bound
may be accomplished by finding a way to optimally combine all of these
elements, for which an upper bound on complexity is known, to generate any
element.

##  5 Directions for Future Work

In the course of this paper, we have opened new cans of worms regarding
integer complexity. Let us close our paper with the following remarks and
questions.

###  5.1 Cyclotomic Fields

Working in cyclotomic fields has yielded us some surprising results. We still
have many unresolved questions.

  * •

Our conjectures: 2.18, 2.19, 2.21, 2.22, and 2.23

  * •

How tight are our bounds for larger $k$ values? (Due to computational
restrictions, we have not been able to compute significant amounts of data.)

  * •

Is there a bound on cyclotomic complexity that is tighter than ours for
sufficiently large $n$?

  * •

The set of minimal numbers $\mathbb{M}$ is a promising set and more
investigation should be done.

  * •

What are the relationships between the different $k$ values as its base? Some
interesting things to explore include looking at the size of the complexity
classes and computatability of complexities for “nicer” $k$, such as
$k=2,4,8,$ etc.

  * •

(These problems were given to us by Zelinsky as guiding problems): Do any of
the following exist, and if so what is the value?

$\displaystyle\lim_{k\rightarrow\infty}\frac{||n||_{k}}{k}$
$\displaystyle\lim_{k\rightarrow\infty}\frac{||n||_{p^{k}}}{p^{k}}$
$\displaystyle\lim_{k\rightarrow\infty}\frac{||n||_{k!}}{k!}$

Note that for $n=1$, we have done the first two limits, by Theorem 2.11 (first
doesn’t, second equals 1).

  * •

We noticed that we can use minimal polynomials in cyclotomic complexity (see
Subsection 5.2). Perhaps we can apply more advanced properties of minimal
polynomials to aid research in cyclotomic complexity.

  * •

The connection between Galois theory and integer complexity in cyclotomic
rings is interesting in that it produced a proof that $||1||_{p}=p$
(Proposition 2.8). But if there was a generalization of this proof to prime
powers (the obvious approach since they have a generator and Theorem 2.11
proves it) there should be analogous parallels in the proof of Theorem 2.11
and the generalization, as was the case for Proposition 2.8 in Footnote 1. But
the integers mod powers of $2$ don’t have generators (except for 2,4), whereas
a Galois theory proof for Theorem 2.11 might suggest they have generators.
Furthermore, Corollary 2.16.2 raises the possibility that $||1||_{2^{a}p^{b}}$
might equal $k$.

###  5.2 Polynomial Rings

  * •

Our conjectures: 3.9, 3.10

  * •

We have applied complexity classes $K_{k}$ to $\mathbb{Z}/m\mathbb{Z}$. Can we
apply this concepts elsewhere to prove other conjectures and better bounds?

  * •

Can we find better bounds with modified complexity? Can we use these results
and generalize them to normal polynomial complexity?

  * •

What results can we transfer from the polynomial ring to the naturals and
using a base in general?

  * •

Can we find results pertaining to our questions in finite polynomial rings?

  * •

What other results can be obtained from analyzing the minimal polynomials and
properties of every expression having coefficients in $\mathbb{N}_{0}$?

  * •

Furthermore, what structure could be used if we expanded the polynomials to
allow coefficients in Cyclotomic Rings? This is especially related to
Conjecture 2.13, but may also reveal insights in power lifting like in
Conjecture 2.23.

  * •

It would also be interesting to consider the relation between optimal
expression of a natural $n$, say $xf$, using the solutions of $xf=n$ as the
base.

  * •

It may be fruitful to search for/classify all functions $f,h$ and a sequence
of polynomials $g_{0},g_{1},\ldots$ such that $g_{n+1}=f(g_{n})$ and
$||g_{n+1}||=h(||g_{n}||)$. This may provide deeper insight as to why using
powers of $3x$ in the Cyclotomic Rings was so effective, how to generalize
this, and a deeper understanding of why it has to be true. Finding some may
also provide a proof and measure for computational “tricks” and their
effectiveness. For instance, multiplying by 10 has a “trick” of doing a
bitshift. This is represented by $f(g)=gx$ and $h(x)=1+x$ having this
condition. Other tricks like multiplying by 11 are represented by $f(g)=xg+g$
(this doesn’t satisfy this for lack of an $h$). Note that these tricks are
base agnostic, like $x$ being any natural we want. Then if $f,h$ don’t work,
can we define an analogue to the deficit and bound the difference between the
real complexity and the predicted complexity (from a $h$)? Thereby a measure
for the effectiveness of computational “tricks” can be made.

  * •

Are we able to generalize the more efficient algorithms in the current
literature, such as in [2], to the Cyclotomic Rings?

  * •

If so, such an algorithm and an exact condition for Conjecture 2.13 (perhaps
the condition is that $k=2^{a}p$ and $2^{a-2}<p$ as suggestive by Corollary
2.16.2) being true could provide a test for a natural being a prime power or 2
times a prime power.

  * •

Considering the minimality conjecture 2.19 in the light of the technique in
Theorem 2.11 may also lead to some progress.

###  5.3 Integers Modulo $m$

  * •

Our conjectures: 4.1, 4.2, 4.3, 4.4

  * •

Is there a way to determine the least inefficient $s$ in
$\mathbb{Z}/m\mathbb{Z}$?

  * •

Can we generalize the techniques using in Theorem 2.11 to be in finite fields
in which a $k$-th root of unity exists?

  * •

It may be possible to do further research through applying graph theory on a
mc-graph to learn more about the structure of integer complexity in a finite
field. Furthermore, this is a subset of the vehicle routing problem in which
the directed edges are one-way equal length streets and we wish to find an
optimal route between a home position and a customer. Analyzing further
examples of mc-graphs with the complexity of a node replacing it may also
reveal more insights.

  * •

Another possible direction is to consider mc-graphs in the non-modified
complexity. However, this loses the nice property of having every node having
two edges going in and two edges going out of it.

  * •

We could also try to approximate the growth of complexity classes with
probabilities using something like the logistic growth model.

##  6 Acknowledgements

We would like to thank our mentor Joshua Zelinsky for acquainting us with the
project and showing us resources that help with our project. We would also
like to thank our counselor Aaryan Sukhadia for listening to and verifying our
proofs and giving insightful comments. We thank John Sim and David Fried for
running research labs, and also the Clay Mathematical Institute for
cosponsoring this project.

## References

  * [1] Harry Altman and Joshua Zelinsky  In _Integers_ 12.6, 2012, pp. 1093–1125  DOI: doi:10.1515/integers-2012-0031
  * [2] Katherine Cordwell et al.  “On algorithms to calculate integer complexity”  In _arXiv_ , 2017  DOI: 10.48550/arXiv.1706.08424
  * [3] Ben Lynn  “Number Theory - Gaussian Periods” [Online; accessed 27. Sep. 2022], 2022  URL: https://crypto.stanford.edu/pbc/notes/numbertheory/gaussperiod.html
  * [4] J. Reyna  “Complexity of natural numbers”  arXiv, 2021  DOI: 10.48550/ARXIV.2111.03345
  * [5] Eric W. Weisstein  “Algebraic Number Minimal Polynomial”  In _Wolfram Research, Inc._ Wolfram Research, Inc., 2002  URL: https://mathworld.wolfram.com/AlgebraicNumberMinimalPolynomial.html
  * [6] Eric W. Weisstein  “Cyclotomic Polynomial”  In _Wolfram Research, Inc._ Wolfram Research, Inc., 2002  URL: https://mathworld.wolfram.com/CyclotomicPolynomial.html
  * [7] Joshua Zelinsky  “Upper Bounds on Integer Complexity”  arXiv, 2022  DOI: 10.48550/ARXIV.2211.02995

##  7 Appendix

###  7.1 Algorithm

We created various programs to compute complexities of elements for us. The
general approach can be described as follows:

  1. 1.

Let $x$ be associated with the empty ordered list $()$.

  2. 2.

Store all of the expressions that we have in a set

  3. 3.

Create a new expression by adding or multiplying two other expressions and
check that this expression is not already in our set of expressions. Let us
define the ordered list associated with this new expression as follows:

    1. (a)

Concatenate (expression of the first ordered list, n, expression of the second
ordered list)

    2. (b)

Let n be the length of this list. Note that $n$ is one less than the
complexity since the length of the list is one less than the complexity.

    3. (c)

If we are multiplying, then make n negative

  4. 4.

Add this new expression to our set of expressions

Here is the algorithm in pseudocode.

⬇

k = #maximum complexity we are looking for

#we wish to associate an optimal expression with an ordered list.

#The length of the ordered list is the complexity of the expression.

expressions = {[x, ()]}

for i in range k:

for a in range i:

for all element1s in expressions with length a:

for all element2s in expressions with length i-a:

#this one tests addition

newexpression = element1[0] + element2[0]

if newexpression not in expressions:

newlist = element1[1] + (length(element1[1]) \+

length(element2[1]) + 1) + element2[1]

#this addition is list concatenation

append [newexpression, newlist] to expressions

#this one tests multiplication

newexpression = element1[0] * element2[0]

if newexpression not in expressions:

newlist = element1[1] - (length(element1[1]) \+

length(element2[1]) + 1) + element2[1]

append [newexpression, newlist] to expressions

For example, $1,2,-6,1,-2,1,9,1,-2$ correponds to
$((x+x+x)\times((x+x)\times(x+x)))((x+x)\times x)$.

Here is a link to the data and programs used in this paper:
https://gitlab.com/partridgetrai
toruntangled/integer-complexity-generalizations-in-various-rings/-/tree/main.