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.
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)?
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.
Maybe it’s worth saying that it’s
where
are the primes.
Sean, I thought this might appeal to you — I was about to send it to you…
Exactly what I was about to add!
Derived by dividing the recurrence relation through by phi(n) = phi(p)phi(n/p) = (p-1)phi(n/p) and expanding.
I wonder if it is possible to describe all limit points of the set of ratios…
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.
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).