## A new constant?

This is an appeal for help. Has anyone come across the constant 2.648102…?

Here is the background, which connects with my previous posts about graphs on groups. We are interested in the clique number of the power graph of the cyclic group of order n. The generators of the group are joined to everything else; there are φ(n) of them, where φ is Euler’s function. These must be in every maximal clique. To them, we adjoin a maximum-size clique of the subgroup of order n/p, where p is the smallest prime divisor of n. Thus the size f(n) of the largest clique satisfies the recurrence f(1) = 1, f(n) = φ(n)+f(n/p), where as above p is the smallest prime divisor of n. (This was proved by Alireza, Erfanian and Abbas in 2015.)

Now, with f defined as above, I conjecture that the ratio f(n)/φ(n) is bounded, and its lim sup is the constant 2.648102….

As you might expect, the largest values of this ratio are realised by the product of the first so many primes. I count all the things that need to be counted.
This entry was posted in doing mathematics, open problems and tagged , , . Bookmark the permalink.

### 8 Responses to A new constant?

1. Oliver Johnson says:

Inverse symbol calculator doesn’t give anything terrifically exciting http://wayback.cecm.sfu.ca/cgi-bin/isc/lookup?number=2.648102&lookup_type=simple Does it make sense for it to be a ratio of gamma functions (looks like gamma(7/24)/gamma(2/3)^(1/2) starts the right way)?

• Peter Cameron says:

I don’t see why it should be a ratio of gamma functions. I can prove that the number is less than 3, and pushing my argument might give better upper bounds.
I think the next few decimal places are 2.6481017597… If you calculate it from that recursion for the product of the first so many primes, the convergence seems to be very fast.

2. Sean Eberhard says:

Maybe it’s worth saying that it’s $\sum_{k=0}^\infty \prod_{i=1}^k \frac1{p_i-1}$ where $p_1, p_2, p_3, \dots$ are the primes.

• Peter Cameron says:

Sean, I thought this might appeal to you — I was about to send it to you…

• Robin says:

Derived by dividing the recurrence relation through by phi(n) = phi(p)phi(n/p) = (p-1)phi(n/p) and expanding.

3. Peter Cameron says:

I wonder if it is possible to describe all limit points of the set of ratios…

4. efthymios says:

I will give a proof of this “I conjecture that the ratio f(n)/φ(n) is bounded”: A not difficult induction argument shows that if $n=p_1^{a_1} \cdots p_r^{a_r}$ where $a_i>0$ are integers and $p_i<p_{i+1}$ for all $i$ then $$\frac{f(n)}{\phi(n) } =\sum_{i=1}^{\omega(n) } \frac{1}{\phi(p_1^{a_1} \cdots p_{i-1}^{a_{i-1}})} \frac{p_i^{a_i}-1}{\phi(p_i^{a_i} )}.$$ Denoting the sequence of all primes (not just the ones dividing $n$) by $q_1=2, q_2=3, q_3=5$ etc, we see that the sum is at most $$\sum_{i=1}^\infty \frac{1}{\phi(q_1\cdots q_{i-1} )} \frac{1}{1-1/q_i}.$$ Using $1/(q-1) \leq 2 /p$ and $1/(1-1/q) \leq 2$ gives $$\frac{ f(n) }{\phi(n) } \leq 2 \sum_{i=1}^\infty \frac{2^{i} }{ q_1\cdots q_{i-1} } ,$$ where the denominator is $1$ for $i=1$. By the prime number theorem for the Chebychev theta function we have $$\log (\prod_{i=1}^{n} q_i ) =\theta(q_n) \sim q_n \sim n \log n ,$$ hence $$\frac{2^{i} }{ q_1\cdots q_{i-1} } =O(2^{-i } ).$$ This shows that $f(n) /\phi(n)$ is bounded.

• gorodetsky says:

Nice argument!
A small comment: one does not need estimates from analytic number theory, since the ratio test applied to \sum_{i=1}^\infty \frac{2^{i} }{ q_1\cdots q_{i-1} } shows this series converges (as primes are eventually >=3).

This site uses Akismet to reduce spam. Learn how your comment data is processed.