  In the study of sparse stochastic block models (SBMs) one often needs to
analyze a distributional recursion, known as the belief propagation (BP)
recursion. Uniqueness of the fixed point of this recursion implies several
results about the SBM, including optimal recovery algorithms for SBM (Mossel et
al. (2016)) and SBM with side information (Mossel and Xu (2016)), and a formula
for SBM mutual information (Abbe et al. (2021)). The 2-community case
corresponds to an Ising model, for which Yu and Polyanskiy (2022) established
uniqueness for all cases.
  In this paper we analyze the $q$-ary Potts model, i.e., broadcasting of
$q$-ary spins on a Galton-Watson tree with expected offspring degree $d$
through Potts channels with second-largest eigenvalue $\lambda$. We allow the
intermediate vertices to be observed through noisy channels (side information).
We prove that BP uniqueness holds with and without side information when
$d\lambda^2 \ge 1 + C \max\{\lambda, q^{-1}\}\log q$ for some absolute constant
$C>0$ independent of $q,\lambda,d$. For large $q$ and $\lambda = o(1/\log q)$,
this is asymptotically achieving the Kesten-Stigum threshold $d\lambda^2=1$.
These results imply mutual information formulas and optimal recovery algorithms
for the $q$-community SBM in the corresponding ranges.
  For $q\ge 4$, Sly (2011); Mossel et al. (2022) showed that there exist
choices of $q,\lambda,d$ below Kesten-Stigum (i.e. $d\lambda^2 < 1$) but
reconstruction is possible. Somewhat surprisingly, we show that in such regimes
BP uniqueness does not hold at least in the presence of weak side information.
  Our technical tool is a theory of $q$-ary symmetric channels, that we
initiate here, generalizing the classical and widely-utilized
information-theoretic characterization of BMS (binary memoryless symmetric)
channels.
