For $p$ prime, $n \geq 1$ and $r \equiv 1 \mod{p}$, let $f(p,n,r)$ be the smallest possible value of $f_p(G)$ among groups $G$ where the largest power of $p$ dividing $|G|$ is $p^n$ and $n_p(G) = r$. This only makes sense if at least one such group exists, so when we talk about $f(p,n,r)$ we assume that this is the case.
Using this notation, the original question could be formulated as follows:
For fixed $p$ and $n$, find a good lower bound for $f(p,n,r)$ in terms of $r$. How does $f(p,n,r)$ grow as $r \rightarrow \infty$?
According to Miller's theorem, $f(p,n,1) = p^n$, $f(p,n,p+1) = p^{n+1}$ and $f(p,n,r) \geq (2p-1)p^n$ when $r \geq 2p+1$. It is also possible to show that $f(p,n,2p+1) = (2p-1)p^n$. See my answer to this question on MO. Also, it's easy to show that $f(p,1,r) = (p-1)r + 1$. Calculating the exact value (even finding a better lower bound) for $f(p,n,r)$ seems difficult in other cases.
Here is an example which suggests that the growth of $f(p,n,r)$ is slow in general. It implies that the growth is slower than linear when $p = 2$ and $n > 1$.
Let $q \equiv 3 \mod{8}$ be prime and let $G = \operatorname{PSL}(2,q)$. Then the Sylow $2$-subgroups of $G$ have order $4$. In this case $n_2(G) = \frac{q(q-1)(q+1)}{24}$ and
$$f_2(G) = \frac{q(q-1)}{2} + 1 = 4 \cdot (n_2(G)\frac{3}{q+1} + \frac{1}{4})$$
For $n \geq 2$, define $H = G \times C_{2^{n-2}}$. Now $n_2(H) = n_2(G)$ and $f_2(H) = 2^{n-2} f_2(G) = 2^n (n_2(G) \frac{3}{q+1} + \frac{1}{4})$.
This shows that $f(2,n,r) \leq 2^n(\frac{3r}{q+1} + \frac{1}{4})$ when $r = \frac{q(q-1)(q+1)}{24}$.
Hence there is no constant $C > 0$ such that $f(2,n,r) \geq Cr$ for all $r \equiv 1 \mod{p}$, since there are infinitely many primes $\equiv 3 \mod{8}$.
Questions: Is there a similar example for $p > 2$? For $n > 1$, is it possible to do any better than $$f(p,n,r) \geq r^{p^{-n}}$$
in general? That is, can we find a lower bound that grows faster than $r^{p^{-n}}$?
(The above inequality follows from the fact that every Sylow $p$-subgroup contains $p^n$ elements from the union of Sylow $p$-subgroups, so $f_p(G)^{p^n} \geq n_p(G)$.)
It has to do with the fact that every (non-empty) fiber of a homomorphism is a coset of the kernel. That is, if $\varphi:G\to H$ is a homomorphism, and $h\in\operatorname{im}\varphi,$ then the fiber of $h$ under $\varphi$ is the set $$\{g\in G:\varphi(g)=h\},$$ and is a coset of $\ker\varphi$ in $G$. I outline the proof of this fact (from a linear algebra standpoint) in my answer here, and not much changes in the more general case.
Since $\ker f$ has order two, then for any $\sigma\in S_4,$ we have $f^{-1}(\sigma)$ has cardinality either $2$ or $0$. Since we're assuming that $A_4=\operatorname{im}f,$ then for each $\sigma\in A_4$ (and in particular for each $\sigma\in P_2$) we have $f^{-1}(\sigma)$ has cardinality $2$. Since $P_2$ has $4$ elements by the referenced exercise, then $f^{-1}(P_2)$ is a union of $4$ pairwise disjoint sets of cardinality $2$, meaning that $f^{-1}(P_2)$ has order $8$.
Does that help?
Best Answer
There is a proof of this fact in Theory and Applications of Finite Groups by G. A. Miller, H .F. Blichfeldt and L. E. Dickson, in the chapter about Frobenius' theorem (pages 79-80). They actually prove a stronger result as well: when there are $> p+1$ Sylow $p$-subgroups, then the number of elements in the union of Sylow $p$-subgroups is $> p^{n+1}$. But here's a proof of just the fact asked about, using the ideas in Miller/Blichfeldt/Dickson (See here and here for the relevant pages from the book).
Let $P_1$ and $P_2$ be distinct Sylow $p$-subgroups such that their intersection $D = P_1 \cap P_2$ has largest possible order, say $|D| = p^k$. Let $g \in N_{P_1}(D)$ such that $g \not\in D$. The existence of such $g$ is guaranteed since $p$-groups satisfy the normalizer condition.
Then $g$ has order $\geq p$ and $g \not\in P_2$, so there are at least $p$ distinct conjugates of the form $g^i P_2 g^{-i}$. Each of these conjugates contains $D$ since $g^i D g^{-i} = D$, thus by the maximality of $D$ the intersection of these conjugates is equal to $D$.
When we include $P_1$ among these conjugates, we get a family of at least $p+1$ distinct Sylow subgroups which have the common intersection $D$. Thus there are $$(p+1)(p^n - p^k) + p^k = p^{n+1} + p^n - p^{k+1} \geq p^{n+1}$$ elements among this family.