Diameter of the Cayley graph of $\mathbb{Z}_n$

Question

So, I have $G = \mathbb{Z}_n$ and $T_n = \{g\in\mathbb{Z}_n: \operatorname{gcd}(g,n) = 1\} = \mathbb{Z}_n^*$.
I need to find the diameter of $\Gamma(G,T_n)$.

What have I tried: we can obviously try to find the longest distance from $0$-vertex, and there are $\varphi(n)$ vertexes that connected to it, let it be that we go to $x$-vertex, than we need to find what (from $T_n$) we can add to $x$ the way that sum won't be from $T_n$.

And than I lost... I tried some ways how to do it, including to somehow use the CRT, but I think that there's no need to use something this powerful to solve this, and I have a feeling that I missing something very simple there...

The most productive idea for me was to factorize $T_n$ by prime numbers in decomposition of $|G|$ and I believe that answer is connected to it, but...

Answer 1

This is not an answer to the question, but some clarifications that will perhaps remove the issues noted in the comments. However, I will give some partial results here. The question is very interesting in my opinion, so it's probably already been solved somewhere. But I couldn't find the reference.

First a few notations. The set of integers modulo $n$ with the operations of addition and multiplication is a ring. I denote it by $\mathbb{Z}_n$. The additive group of this ring I denote by the same symbol $\mathbb{Z}_n$. The multiplicative group of integers modulo $n$, which is the group of units in this ring, may be written as $\mathbb{Z}_n^*$ The order of $\mathbb{Z}_n$ is $n$ and the order of $\mathbb{Z}_n^*$ is the number of integers in $\{0,1,\dots ,n-1\}$ coprime to $n$. It is given by Euler's totient function: $|\mathbb{Z}_n^*|=\varphi(n)$

Consider a Cayley graph $\Gamma_n=\operatorname{Cay}(\mathbb{Z}_n,T)$, where $T$ can be defined as $T=\mathbb{Z}_n^*$. Recall that two vertices $x$ and $y$ of $\Gamma_n$ are adjacent if $y=x+t$ for some $t\in T$. The graph $\Gamma_n$ has no loops (since $0\not\in T$), is undirected (since $-T=T$), and is connected (since $\mathbb{Z}_n=\langle T\rangle$). The degree of each vertex of $\Gamma_n$ is $\varphi(n)$.

Now about the diameter of the graph $\Gamma_n$ ($\operatorname{diam}\Gamma_n$).

It is clear, that $\operatorname{diam}\Gamma_1=0$.

Lemma 1. If $n$ is prime, then $\operatorname{diam}\Gamma_n=1$. The converse is also true, if $\Gamma_n$ is a graph of diameter $1$, then $n$ is prime.

The proof is obvious.

The following observations will be useful in the future. If $T\cup(T+T)=\mathbb{Z}_n$, then $\operatorname{diam}\Gamma_n\leq2$. If $T\cup(T+T)\cup(T+T+T)=\mathbb{Z}_n$, then $\operatorname{diam}\Gamma_n\leq3$. In both cases the converse is also true.

Well indeed, for example in the first statement if the distance from $0$ to $x$ is $2$, then it follows from the definition of the Cayley graph $\Gamma_n$ that $x\in T+T$ and vice versa.

Lemma 2. If $n$ is odd and not prime and $\dfrac{n}{\varphi(n)}<3$, then $\operatorname{diam}\Gamma_n=2$.

Proof. It is obvious that $\operatorname{diam}\Gamma_n\geq2$. Suppose that $\operatorname{diam}\Gamma_n\geq3$. This means that there exists $x\in\mathbb{Z}_n$ such that $x\not\in T$ and $x\not\in T+T$. Hence, since $x$ is odd, it follows $$ x+T\cap T=\varnothing, 2x+T\cap T=\varnothing, \text{ and } x+T\cap 2x+T=\varnothing. $$ We therefore have $T\cup (x+T)\cup(2x+T)\subset\mathbb{Z}_n$ and $$ n\geq|T\cup (x+T)\cup(2x+T)|=|T|+|x+T|+|2x+T|=3\varphi(n), $$ i.e. $n/\varphi(n)\geq3$. The contradiction proving our lemma.

Note that if $n$ is an odd number less than $10^7$, then $n/\varphi(n)<3$.

Lemma 3. If $n>2$ is even but not a power of two and $\dfrac{n}{\varphi(n)}<4$, then $\operatorname{diam}\Gamma_n=3$.

Proof. Let us first consider the case $n=2m$ with odd $m$. In this case, every element of $T$ is odd, hence $m\not\in T+T$ (since $m$ divides $n$, $m\not\in T$) and consequently $\operatorname{diam}\Gamma_n\geq3$.

To prove that $\operatorname{diam}\Gamma_n<4$ it is enough to check that $(T+T)\cup(T+T+T)=\mathbb{Z}_n$. First prove that $T+T=2\mathbb{Z}_n$. If $x\in2\mathbb{Z}_n$ and $x\not\in T+T$, then $$ x+T\cap T=\varnothing, $$ and $$ 2\mathbb{Z}_n\supset x+T\cup T. $$ We have $$ m\geq |x+T\cup T|=2\varphi(n)\Rightarrow\ n/\varphi(n)\geq4. $$ Contradiction.

Now since $|\mathbb{Z}_n:2\mathbb{Z}_n|=2$ we obtain $$ (T+T)\cup(T+T+T)=2\mathbb{Z}_n\cup(T+T)+T=2\mathbb{Z}_n\cup(2\mathbb{Z}_n+1)=\mathbb{Z}_n. $$

The case $n=2^km$ with odd $m$ and $k>1$ is simpler than the considered case and I omit it.

Lemma 4. If $n>2$ is a power of two, then $\operatorname{diam}\Gamma_n=2$.

Proof. In this case $T$ consists exactly of all odd elements of $\mathbb{Z}_n$, i.e. $T=2\mathbb{Z}_n+1$ hence $T+T=2\mathbb{Z}_n$. It follows $\operatorname{diam}\Gamma_n=2$.

PS.1 It is possible that in general it is always $\operatorname{diam}\Gamma_n\leq3$.

PS.2 I did find a reference Theorem 9.