  We prove that the redundancy of a $k$-server PIR code of dimension $s$ is
$\Omega(\sqrt{s})$ for all $k \ge 3$. This coincides with a known upper bound
of $O(\sqrt{s})$ on the redundancy of PIR codes. Moreover, for $k=3$ and $k =
4$, we determine the lowest possible redundancy of $k$-server PIR codes
exactly. Similar results were proved independently by Mary Wootters using a
different method.
