What are phonon frequencies in solids? How are they related to the interaction potentials between the constituent atoms? What are phonon frequencies in solids? How are they related to the interaction potentials between the constituent atoms?
I was reading a paper on self-assembly of colloidal structures (reference below), where it was mentioned that only solids with real phonon frequencies are mechanically stable. The authors then go on to manipulate the interaction potential function to get such values.

Optimized Interactions for Targeted Self-Assembly. MC Rechtsman et al. Phys. Rev. Lett. 95, 228301 (2005), arXiv:cond-mat/0508495.

 A: Although the Wikipedia page gives a good introduction to the concept of phonons,
it very quickly introduces the approximation of nearest-neighbour interactions,
and doesn't give some of the important details 
about how the phonon frequencies are 
calculated in terms of the interaction potentials.
The cited paper by Rechtsman, Stillinger and Torquato
appeared at 
Phys Rev Lett, 95, 228301 (2005)
and also as a preprint.
More details appear in a later paper by the same authors
Phys Rev E, 73, 011406 (2006),
also available as a preprint.
The same group has taken these ideas further in the years since.
The interaction potential depends only on the distance between atoms,
but is of an unconventional form with two minima separated by a maximum.

The idea is to "tailor" the potential to favour 
an open crystal structure
(in this case based on a honeycomb lattice).
In fact, they hope that such a lattice will self assemble,
given such a potential.
So, they need to handle a lattice with several atoms per unit cell,
and the potential extends over more than nearest neighbours
(although there are no truly long-range, electrostatic, terms).
As part of the process of "vetting" the potential, 
they require that all the phonon frequencies are real;
in other words, all the "spring constants" are positive.
Otherwise,
a simple deformation with the corresponding wave-vector would lower the potential energy,
so the proposed crystal structure would be mechanically unstable.
A proper description of "how to calculate the phonons"
is given in several books on solid state physics,
and in that second paper they actually refer to N Ashcroft and ND Mermin Solid State Physics.
The following is just a sketch.
Let the position of atom $k$ in unit cell $m$ be
$$
\mathbf{R}_{mk} = \mathbf{R}_m + \mathbf{r}_k + \mathbf{u}_{mk}
$$
where $\mathbf{u}_{mk}$ is the instantaneous displacement from the ideal lattice position,
the latter being a sum of the basis vector $\mathbf{r}_k$ within the cell,
and the cell position $\mathbf{R}_m$.
The quadratic approximation to the lattice energy is
$$
\Phi = \Phi_0 + \frac{1}{2} \sum_{mk\alpha} \sum_{m'k'\alpha'} 
\Phi_{mkm'k'}^{\alpha\alpha'}\, u_{mk}^\alpha u_{m'k'}^{\alpha'}
$$
where $\alpha,\alpha'=x,y,z$ (or just $x,y$ in 2D) and
$$
\Phi_{mkm'k'}^{\alpha\alpha'} = \left. 
\frac{\partial^2\Phi}{\partial u_{mk}^\alpha \partial u_{m'k'}^{\alpha'}} \right|_{0}
$$
is evaluated at equilibrium, all $u_{mk}^\alpha=0$.
There is no linear term because at equilibrium there are no net forces on any atom.
The summation goes over all pairs of atoms in a large (macroscopic) sample,
but of course the terms $\Phi_{mkm'k'}^{\alpha\alpha'}$ are nonzero only for pairs
within interaction range;
also they depend only on the difference in unit cell positions $\mathbf{R}_m-\mathbf{R}_{m'}$,
so they can be written $\Phi_{kk'}^{\alpha\alpha'}(\mathbf{R}_m-\mathbf{R}_{m'})$. This helps when we Fourier transform.
Introducing Fourier modes $\mathbf{u}_{mk}\propto\sum_{\mathbf{q}}\mathbf{U}_{\mathbf{q}k} \exp(-i\mathbf{q}\cdot\mathbf{R}_m)$
simplifies the energy to
$$
\Phi = \Phi_0 + \frac{1}{2} \sum_{\mathbf{q}}  \sum_{k\alpha} \sum_{k'\alpha'} 
D_{kk'}^{\alpha\alpha'}(\mathbf{q}) \, U_{\mathbf{q}k}^{\alpha} U_{-\mathbf{q}k'}^{\alpha'}
$$
where
$$
D_{kk'}^{\alpha\alpha'}(\mathbf{q}) = \sum_{\mathbf{R}} 
\Phi_{kk'}^{\alpha\alpha'}(\mathbf{R}) \exp(-i\mathbf{q}\cdot\mathbf{R})
$$
This is typically normalized by a term involving the atomic masses to give the dynamical matrix,
but if the atoms all have the same mass this is trivial.
If there are $K$ atoms in the unit cell, 
the terms $D_{kk'}^{\alpha\alpha'}(\mathbf{q})$
are the elements of a matrix $\mathbb{D}(\mathbf{q})$
whose size is $3K\times3K$ (or $2K\times2K$ in 2D).
Determining the eigenvalues of $\mathbb{D}(\mathbf{q})$ 
is the key operation:
if any of them are negative, the corresponding phonon frequency is imaginary,
and the crystal will be unstable.
Calculating $\Phi_{mkm'k'}^{\alpha\alpha'}$ involves looking at all $K$ atoms in the unit cell,
and examining the interaction with every other atom within range of the
potential $v(r)$.
Of course,
$\mathbb{D}(\mathbf{q})$ needs computing for a large number of wavevectors in the Brillouin zone,
but this is tractable.
