Probability that the number of heads is coprime with the number of throws

Let's throw a coin $n$ times. Say that we have obtained heads $k$ times and tails $n-k$ times. I'm interested in the probability that the number of heads is coprime with the total number of throws. Obviously, this probability is described by the formula $$ P=\sum_{\substack{0<k<n,\\gcd(k, n)=1}}\binom{n}{k}p^k(1-p)^{n-k}, $$ where $p\in(0, 1)$ is a probability of throwing heads.

The question. Is it true that this sum is lower bounded by some positive constant for all integers $n > 1$?

My thoughts. I think that it should be true. Take $p=1/2$ for simplicity. Some computer calculations suggest that $P\ge 0.1875$, and this bound is achieved for $n=6$. But I don't know how to prove it.

It's also easy to show that $P\ge c n^{-1/2}$ for some constant $c$ because we can always find such number $k$, which is coprime with $n$ and close to $n/2$. But this bound is too weak.

Update. @donaastor made some interesting comments below and convinced me that for all constant $p$ the lower limit of the probability equals 0. Also, further computer calculations for $p=1/2$ showed that the probability for $n=30030$ is lower than for n=6 and equals $\approx 0.1828$.

Solution 1:

If we define $P_d$ as the sum over $k$ multiples of $d$, one can see that

$$ P_{coprime} = \sum_{d \mid n } \mu(d) P_d $$

Where $\mu$ is the Moebius function. This is sophisticated way of expressing an inclusion-exclusion: first you put all terms via $P_1$; then you subtract all stuff that have a prime in common with $n$ via $-P_q$ for q prime; then you have to add back things that are multiple of two primes... Moebius function implements this in a neat way. Now $P_d$ is a bit easier to describe. Let

$$F_n(z) = (pz + 1-p) ^n$$

his is a polynomial in $z$ which has exactly the terms of your summation in each degree: in particular $F_n(1) =1$ is the total probability. This is also called the generating function of the distribution.

If you average on d-th roots of unity $\zeta_d$ you will get rid of terms which are not divisible by d: this is called root of unity sieve technique. Now let $\zeta$ by a primitive $n$-th root of unity. We have that $\zeta^{nk/d} $ for $k=1, \ldots, d$ enumerates all the d-roots of unity. Thus

$$ P_d = \frac{1}{d} \left ( \sum_{k=1}^d (p \zeta^{nk/d} + 1-p) ^n \right ) $$

Plugging this into $P_{coprime}$ yields

$$ P_{coprime} = \sum_{d \mid n} \mu(d) \frac{1}{d} \left ( \sum_{k=1}^d (p \zeta^{nk/d} + 1-p) ^n \right ) $$

We want to exchange this summation in terms of when a given root of unity appears. A power $( \ldots )^n $ containing the root $\omega = \zeta^r$ appears for $r=nk/d$ with a coefficient of $\mu(d) /d$ in front. In particular, it appears exactly when $n/d \mid r$. Changing variable $d' = n/d$ we can thus write

$$ P_{coprime} = \sum_{r=1}^n (p \zeta^r + 1-p) ^n \sum_{d' \mid r} \mu(d') \frac{1}{d'} = \sum_{r=1}^n (p\zeta^r + 1-p)^n \frac{\varphi(r)}{r} = \sum_{r=1}^n (1+ p(\zeta^r-1))^n \frac{\varphi(r)}{r} $$

For $p << 1$ we get

$$ \simeq \sum_{r=1}^n (1+np(\zeta^r-1)) \frac{\varphi(r)}{r} $$

And I think we can approximate this number by its real part, because it is close in norm to $P_{coprime}$ which is real. This we get

$$\simeq \sum_{r=1}^n (1+np(\cos(2\pi r/n) -1)) \frac{\varphi(r)}{r} = (1-np) \sum_{r=1}^n \frac{\varphi(r)}{r} +np \sum_{r=1}^n \cos(2\pi r/n) \frac{\varphi(r)}{r} $$