  Many problems and conjectures in extremal combinatorics concern polynomial
inequalities between homomorphism densities of graphs where we allow edges to
have real weights. Using the theory of graph limits, we can equivalently
evaluate polynomial expressions in homomorphism densities on kernels $W$, i.e.,
symmetric, bounded, and measurable functions $W$ from $[0,1]^2 \to \mathbb{R}$.
In 2011, Hatami and Norin proved a fundamental result that it is undecidable to
determine the validity of polynomial inequalities in homomorphism densities for
graphons (i.e., the case where the range of $W$ is $[0,1]$, which corresponds
to unweighted graphs, or equivalently, to graphs with edge weights between $0$
and $1$). The corresponding problem for more general sets of kernels, e.g., for
all kernels or for kernels with range $[-1,1]$, remains open. For any $a > 0$,
we show undecidability of polynomial inequalities for any set of kernels which
contains all kernels with range $\{0,a\}$. This result also answers a question
raised by Lov\'asz about finding computationally effective certificates for the
validity of homomorphism density inequalities in kernels.
