Abstract: Let $H_0$ be a discrete periodic Schr\"odinger operator on $\Z^d$: $$H_0=-\Delta+V,$$ where $\Delta$ is the discrete Laplacian and $V:\Z^d\to \R$ is periodic. We prove that for any $d\geq3$, the Fermi variety at every energy level is irreducible (modulo periodicity). For $d=2$, we prove that the Fermi variety at every energy level except for the average of the potential is irreducible (modulo periodicity) and the Fermi variety at the average of the potential has at most two irreducible components (modulo periodicity). This is sharp since for $d=2$ and a constant potential $V$, the Fermi variety at $V$-level has exactly two irreducible components (modulo periodicity). In particular, we show that the Bloch variety is irreducible (modulo periodicity) for any $d\geq 2$. As an application, we prove that $H=-\Delta +V+v$ does not have any embedded eigenvalues provided that $v$ decays super-exponentially.