Exercise 4.7, I. Martin Isaacs' Character Theory
I think the following works, but it doesn't "feel" right. Perhaps because this is surely not the intended solution. I am hoping someone who knows some character theory will come along and enlighten us!
So let $P$ be a finite $p$-group, and let the set $X=\lbrace x\in P\ |\ x^p=1\rbrace$. Suppose there is an $\alpha$ such that $[P:\Phi(P)]\ge p^{2\alpha-1}$ and yet $|X|\not\equiv0\pmod{p^\alpha}$. This is the same as saying \begin{equation} \sum_{\chi\in Irr(P)} \nu_p(\chi)\chi(1)\not\equiv 0\pmod{p^\alpha}.\qquad \qquad (*)\end{equation}
Now let $C$ be the group of linear characters of $P$ such that for all $\lambda\in C$, $\lambda^p=1_P$. $C$ is just the set of characters in $Irr(P)$ such that $\Phi(P)\subset \ker\lambda$. Thus $C$ is isomorphic to $P/\Phi(P)$. Now $C$ will act on $Irr(P)$, by sending $\chi$ to $\lambda\chi$, and we can decompose this action into orbits. Both $\nu_p(\chi)$ and $\chi(1)$ are invariant under this action. But by $(*)$, there must be an irreducible character $\chi$ such that \begin{equation} \chi(1)\cdot |C\chi|\le p^{\alpha-1}.\qquad\qquad (**)\end{equation}
Here $C\chi$ is the orbit of $C$ acting on $\chi$. Of course, this implies the crucial fact that \begin{equation} \chi(1)\le p^{\alpha-1}.\qquad \qquad (\ast\ast\ast)\end{equation}
Let's break the rest of the proof into steps.
Step 1: We know that $\chi(1)\ge p^{\beta_0}$, where $\beta_0=0$. We also know (by equation $(**)$) that $|C\chi|\le p^{\gamma_0}$, where $\gamma_0=\alpha-1-\beta_0$.
Step 2: By the orbit-stabilizer theorem, $|C_\chi|\ge p^{\mu_0}$, where $\mu_0=2\alpha-1-\gamma_0$.
Step 3: Let $\lbrace\lambda_1,\cdots,\lambda_{2\alpha-1},\cdots\rbrace$ be a basis for $C$, and choose $g_1,\cdots,g_{2\alpha-1},\cdots$ to be the corresponding basis for $P/\Phi(P)$, such that $\lambda_i(g_j)=\epsilon^{\delta_{ij}}$, with $\epsilon$ a $p^\text{th}$ root of unity. We can suppose that $\lambda_1,\cdots,\lambda_{\mu_0}$ stabilize $\chi$.
Step 4: Now this means that $\chi(g_i)=\lambda_i(g_i)\chi(g_i)=\epsilon\chi(g_i)$ for $i\le\mu_0$. Thus $\chi(g_i)=0$ for $i\le\mu_0$.
Step 5: Thus if $H_0=\langle g_1,\cdots,g_{\mu_0},\Phi(P)\rangle$, then we have by Lemma 2.29 that \begin{equation} \chi(1)^2\ge [\chi_{\Phi(P)},\chi_{\Phi(P)}]=[H_0:\Phi(P)]\cdot [\chi_{H_0},\chi_{H_0}]\ge [H_0:\Phi(P)]=p^{\mu_0}.\qquad (\dagger)\end{equation}
Step 6: Since we now know $\chi(1)^2\ge p^{\mu_0}$, we get that $\chi(1)\ge p^{\beta_1}$, where $\beta_1=\lceil \frac{\mu_0}{2} \rceil$, because $\chi(1)$ divides $|P|$.
We can now go back to step 1, using $\beta_1$ instead of $\beta_0$, to get new $\gamma_1$ and $\mu_1$. Note that after the first run through, $\beta_1=\lceil \frac{\alpha}{2}\rceil$. This means $\gamma_1=\lfloor\frac{\alpha}{2}\rfloor-1$ and $\mu_1=\lceil\frac{3\alpha}{2}\rceil$. Thus after a second run-through, $\beta_2=\lceil\frac{3\alpha}{4}\rceil$, and so on. In general, $\beta_k=\lceil\alpha-\frac{\alpha}{2^k}\rceil$.
We thus get a $k$ eventually large enough that $\beta_k=\alpha-1$. This implies $\gamma_k=0$ and $C_\chi=C$, and thus $H_k=P$. Using $(\ast\ast\ast)$, we see that in fact $\chi(1)=p^{\alpha-1}$, and thus plugging in one last time to $(\dagger)$, we get
\begin{equation} p^{2\alpha-2}=\chi(1)^2\ge [\chi_{\Phi(P)},\chi_{\Phi(P)}]=[P:\Phi(P)]\cdot [\chi,\chi]\ge [P:\Phi(P)]\ge p^{2\alpha-1},\end{equation} the final contradiction.